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

Flashcard·Medium·4.0 · 0·~30s·Asked atQdrant

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

HNSW is built around a graph: each vector is a node, and each node stores edges to a small set of its neighbors. The graph is what makes search fast (you hop along edges toward the query, finishing in a few dozen hops). Modifying the graph after it is built is expensive, because deleting a node would orphan all the edges pointing into it. **Deletes use tombstones.** Instead of removing a node, HNSW marks it with a tombstone bit. The node and its edges stay in the graph; searches still traverse through it; but when the search collects candidate results, tombstoned nodes are filtered out before returning. From the user's point of view the vector is gone; from the index's point of view it is still there. **Updates are insert-new + tombstone-old.** There is no in place update of a vector. The old version is tombstoned, the new version is inserted as a fresh node with new edges. This means every update doubles the storage cost for that vector until the index is compacted. **The cost of letting tombstones accumulate.** Two problems compound under heavy write workloads. First, query latency drifts upward because the graph keeps growing in node count even as the live count stays flat; every query traverses through dead nodes that contribute nothing. Second, recall drops because new nodes were inserted into a graph that included now-stale neighborhoods, so the local connectivity does not reflect the current data distribution. **The fix is periodic compaction or rebuild.** Pinecone, Qdrant, Weaviate, and Milvus all expose this. Some auto-trigger it when the tombstone ratio crosses a threshold; some require an admin to run a compaction job. The operational practice: monitor the deletion ratio and recall@K together, rebuild when either drifts.

**HNSW's update model is logically simple, operationally subtle.** *Delete:* the engine sets a tombstone bit on the node. The node, its vector data, and all its outgoing edges remain in memory. Searches still traverse through it normally; the result-collection step filters tombstoned nodes out of the top-K before returning. This is sometimes called 'logical delete' or 'soft delete'. *Update:* there is no in place edge rewiring in standard HNSW. An update is implemented as `tombstone(old_id); insert(new_vector_for_id)`. The new node is inserted into the graph using the standard HNSW build algorithm, which selects M neighbors from the current graph (which still includes the old version and all the other tombstones). **Why deletes are tombstones and not real removals.** Removing a node from an HNSW graph requires repairing all incoming edges (other nodes that listed this one as a neighbor must pick a replacement). That repair is expensive (potentially O(M^2 * log N) per delete) and risks degrading graph quality if done greedily. Tombstones make the per-delete cost O(1). **The compounding cost under heavy writes.** 1. *Memory bloat.* Tombstoned nodes still consume their full vector storage and edge list. A workload that does 100M inserts and 100M deletes ends up with 200M nodes in memory, only 100M of which are live. The index is 2x the size it 'should' be. 2. *Query latency drift.* Graph traversal visits tombstones; each visit is a wasted hop. Latency creeps up linearly with the dead-node ratio. A 50% tombstone ratio roughly doubles average traversal length. 3. *Recall degradation.* New nodes' neighborhoods are computed against a graph that includes stale neighborhoods. Over time the graph's local structure no longer reflects the current data distribution. Recall against the live set can drop by 5 to 15 points before anyone notices. **The fix: periodic compaction.** Either a full index rebuild (drop the index, re-insert all live vectors into a fresh graph)

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

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

Detailed answer & concept explanation

~6 min read

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.

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?

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

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

Don't say this

Red flags and common mistakes that signal junior thinking. Click to expand.

Most common mistake

Assuming HNSW deletes are free because they don't change the graph structure. Tombstones are cheap to write but expensive to live with, they cost RAM and traversal hops on every query forever, until you rebuild.

60-second cheat sheet

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

References

Primary sources. Skim if you want the original framing.