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

Flashcard·Medium·4.0 · 0·~30s·Asked atQdrant Unity Vellum·Relevant atMicrosoft NVIDIA

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)

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

Concept explanation~2 min read

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

HNSW is a beautifully simple data structure when the corpus is static. The complications come from how it handles change. The standard HNSW build algorithm assumes you have all the vectors in hand and constructs the graph in one pass. Real production indexes never have that luxury: documents arrive, get updated, get deleted, embedding models change. How HNSW handles those changes determines whether the index degrades silently or stays healthy.

This question is about a specific failure mode that does not appear in academic ANN benchmarks (which are static) but bites every production HNSW deployment eventually.

Why deletes are tombstones

An HNSW graph stores, for each node, a list of M neighbors per layer. Deleting a node means removing it from every neighbor list that mentions it. With M = 32 neighbors per layer and 2-3 layers per node on average, that is 64 to 96 incoming-edge references to find and repair for each deletion. Worst case, repairing requires a scan; with a reverse-index it is bounded, but the repaired neighbors then need new neighbors to replace the deleted one, which triggers more partial rebuilds.

Doing this synchronously on every delete kills write throughput. So every production HNSW implementation uses tombstones: a 1-bit-per-node flag that says 'logically deleted, do not return in results'. The node, its vector, and its edges remain in memory and remain part of the graph. Searches still traverse through tombstoned nodes; they are filtered only at the top-K collection step before returning to the caller.

This trades O(1) per-delete cost for deferred maintenance. Every tombstone is a small lien against future compaction. Without compaction, the liens accumulate until the graph degrades.

Updates are tombstone-plus-insert

The three failure modes under heavy write workloads

Compaction and the production maintenance pattern

Why DiskANN / Vamana does better

Situations where this technique stops working.

2–4 min · Everything important, quickly.

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 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.

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?

New inserts pick neighbors greedily from the existing graph; the greedy algorithm tends to over connect to high degree nodes (hub formation). Periodic rebuild rebalances the degree distribution.

2 more follow-ups an interviewer would ask next. Sign in to reveal them.

Red flags & common mistakes

The phrases 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 bullets to scan on the way to the call.

Tombstone mechanism: logical delete, physical node persists
Update = tombstone-old + insert-new (no in place update)

Primary sources. Browse if you want the original framing.