How does an HNSW index handle deletes and updates under a heavy write workload?

Attempt it

HNSW does not physically remove nodes on delete, it marks them with a tombstone bit. Search visits tombstoned nodes during graph traversal but filters them from the returned results. Updates are encoded as insert-new + tombstone-old.

Under heavy churn this fragments the graph in two ways. First, tombstoned nodes still consume RAM and still cost a hop during traversal, so query latency and memory drift upward. Second, the graph's local connectivity degrades because the new nodes' edges were built against a partially-stale neighborhood, lowering recall over time.

Production systems schedule periodic full or partial rebuilds to compact tombstones and restore graph quality. Pinecone, Qdrant, and Weaviate all expose this either as automatic background optimization or as an admin-triggered compaction job. The operational rule: monitor delete-ratio and recall@K together, and rebuild when either drifts.

Your answer

Quick reference

TL;DR

Deletes leave tombstoned nodes in the graph (still traversed, filtered from results). Heavy churn bloats memory, slows queries, and degrades recall.

Memory aid

Sign in for the mnemonic that makes this stick. See Pro pricing.

Easy to grasp

Imagine a phone book where every entry is connected by little arrows to a few similar entries. When someone moves out, you do not actually rip the page out (that would shred all the arrows pointing to that page and you'd have to redraw them). Instead, you put a sticker on their entry that says 'gone'. People searching the phone book still wander past their entry, follow their arrows for a few hops, then realize the entry is marked and move on. The book gets thicker with stickered entries over time, paths get muddled, and eventually a librarian has to sit down and rebuild the whole book to make searches fast again.

Key concepts

HNSW index operations

Quick scan · 2–4 min

Everything important, quickly.

4 min: why tombstones rather than real deletes + three failure modes (memory, latency, recall) + compaction strategies + DiskANN as an improvement + 2026 vendor maintenance patterns + monitoring rubric.

Side-by-side

Operation	What HNSW does internally	Visible cost
Delete	Sets tombstone bit; node stays in graph	RAM and traversal cost until compaction
Update	Tombstones old, inserts new with fresh edges	Doubles per-vector storage until compaction
Insert (no churn)	Standard HNSW build: pick M neighbors via greedy descent	Comparable to ground-up build cost per vector
Insert (heavy churn)	Picks neighbors from a graph polluted with stale nodes	Recall degradation over time
Compaction / rebuild	Drop tombstones, repair edges, or build fresh graph	Expensive but restores all properties

Real-world examples

Real products, models, and research that use this idea.

Pinecone runs continuous background optimization on managed indexes; users observe the effect on recall and memory without configuring the compaction directly.
Qdrant exposes `optimizers_config.deleted_threshold` and related knobs; compaction triggers automatically when tombstone ratios cross those thresholds.
Weaviate provides async deletes with an explicit `flush` API for batch jobs; production teams typically schedule daily flushes during off-peak hours.
Milvus uses a segment-based architecture similar to LSM-tree compaction: sealed segments are immutable, updates create new segments, a background compactor merges and reclaims tombstones.
Microsoft's FreshDiskANN paper (Singh et al., 2021) describes the Vamana variant that handles streaming inserts and deletes with bounded recall degradation, the foundation of several 2026 disk-based ANN systems.

Interviewer follow-ups

What an interviewer would ask next. Try answering before peeking at the approach.

QWhy does graph quality degrade even with no deletes, just heavy inserts?

Sign in or go Pro to see the approach for this follow-up.

QWhat is the cost of a full HNSW rebuild for 100M vectors?

Sign in or go Pro to see the approach for this follow-up.

QHow does segment-based architecture (Milvus, Vespa) avoid the rebuild bottleneck?

Sign in or go Pro to see the approach for this follow-up.

60-second cheat sheet

The night-before-the-interview bullets. Scan these on the way to the call.

Sign in for 5 unlocks/day or go Pro for unlimited revision sheets. See Pro pricing.

References

Primary sources. Skim if you want the original framing.