Select every symptom that points to tombstone bloat in a long running HNSW index.

Multi-select·Medium·4.0 · 0·~1 min·Asked atAdobe Robinhood Xai

Attempt it

**Tombstones** are logical deletions. The vector engine marks the node as deleted but does not remove it from the graph, because physically removing it would mean rebuilding every neighbor pointer that points to it. The symptoms that follow from that mechanism are about presence without visibility: - **Latency creeps up.** The graph keeps growing in walk-time terms even when the live data is flat. Search has to traverse dead nodes that contribute nothing to results. - **Memory does not shrink.** Deletes return the id to the user but do not free the underlying graph storage. Heap and resident memory hold steady or grow. - **Recall dips in churned regions.** When many neighbors of a live node are tombstoned, the live node's effective neighborhood shrinks. The ANN walk loses connectivity, and the candidate set degrades. The two distractors point at things that are not symptoms of tombstones. Write throughput is not improved by deletes; the write path adds new nodes regardless of how many are tombstoned. Score signs are a function of the metric and the vectors, not of deletion state; cosine over unit-normalized vectors lives in `[-1, 1]` whether the corpus has tombstones or not.

Tombstones are the standard delete mechanism in graph-based vector indexes (HNSW, DiskANN, NSG). A delete marks the node as logically removed but leaves it in the graph structure because rewriting incoming neighbor pointers from every node that references it would be prohibitively expensive at delete time. The three real symptoms follow directly from the mechanism: - **Latency creep.** Search traverses the graph using `ef_search` candidate expansion. Tombstoned nodes are still visited, still consume the exploration budget, and still contribute to traversal cost. Live vector count can stay flat while walk-time grows linearly with cumulative deletes. - **Memory persistence.** Deletes return success at the client level but do not deallocate the underlying graph node, neighbor list, or vector storage. Heap holds steady or grows. RSS does not drop after large delete jobs. - **Recall sag in churned regions.** When a live node has many tombstoned neighbors, its effective connectivity drops. The small-world property of HNSW relies on a saturated neighborhood; tombstones starve it. Recall sags worst in regions where churn concentrated (active user accounts, retracted news stories, expired listings). The two distractors are diagnostic for a strong answer. Write throughput is independent of deletion state; inserts add new nodes to the graph regardless of tombstone count. Score signs are functions of the distance metric and the vector values; cosine over unit-normalized vectors lives in `[-1, 1]` and L2 is non-negative, neither of which changes when deletions accumulate. Production mitigation is background compaction (Vespa, Milvus, Qdrant, Weaviate all run this) sized against the actual delete rate.

TL;DR

Tombstones bloat memory, slow traversal, and sag recall in churned regions. They do not speed up writes or change score signs.

Memory aid

Easy to grasp

Imagine a city where buildings cannot be demolished, only marked condemned. The streets still wind through them, the map still lists them, the postal carrier still walks past them. The city has the same number of living residents but takes longer to navigate, takes the same amount of land, and gets confusing in neighborhoods that have been condemned often. New buildings still go up at the same speed; the condemned signs do not help construction. And the GPS coordinates of any address are unchanged by condemnations. That is exactly what tombstones do to a vector index.

Key concepts

Vector Databases

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.

Tombstones are one of those topics where the mechanism is simple but the consequences are everywhere. A delete in a graph-based vector index does not remove the node; it marks it. That single design choice produces a whole family of production symptoms, and recognizing them quickly is the difference between a team that runs healthy long-lived indexes and a team that quietly degrades for months.

This deep dive explains the mechanism, quantifies the three real symptoms, dispatches the two common distractors, and walks through the production monitoring and mitigation story. The goal is to leave the reader with a clear picture of when to suspect tombstones and how to confirm it before reaching for a fix.

Why HNSW deletes are logical, not physical

HNSW (hierarchical navigable small world) is a graph where each node has a small set of neighbors at each level. A physical delete would require rewriting incoming neighbor pointers from every node that references the deleted one. In a graph with average degree M = 16 across multiple levels, that is many pointer rewrites per delete, each requiring lookups and disk writes.

The engineering compromise is to mark the node deleted and leave the structure alone. Search walks the graph as before, encounters the tombstone, sees the deleted flag, and discards the candidate. The node still occupies its vector storage, its neighbor lists, and its bookkeeping.

This is the same pattern as Cassandra and other LSM systems use for deletes, where the term tombstone originated. The metaphor is exact: a marker that says 'something was here' without freeing the underlying space.

The consequence is that deletes are cheap at delete time but expensive at search time. The cost shifts from the writer to the reader, and accumulates until compaction reclaims it.

Quantifying the three real symptoms

Why the two distractors fail

Production monitoring and mitigation

Tombstone arithmetic and the 2026 compaction playbook

Situations where this technique stops working.

2–4 min · Everything important, quickly.

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

Weaviate emits a tombstone-count metric per shard and triggers cleanup based on a configurable threshold so operators can monitor proactively
Vespa's content nodes run continuous compaction on attribute and document stores with explicit tombstone-aware logic for write-heavy feeds

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

QWhat is the relationship between tombstone ratio and recall, quantitatively?

Recall in HNSW depends on neighborhood saturation. If a fraction p of neighbors are tombstoned, effective M drops to M(1-p). Below the saturation threshold (engine-specific, typically M >= 8), recall drops sharply. Plotting recall vs tombstone ratio shows a knee around 30-40% for typical configs.

1 more follow-up 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 a delete frees memory or speeds up the next query. Logical deletes are still in the graph; only compaction or rebuild reclaims them.

60 second bullets to scan on the way to the call.

Why HNSW deletes are logical, not physical, and what that means for memory and walk time
How tombstone ratio relates to walk-time cost and recall sag in churned regions

Primary sources. Browse if you want the original framing.