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

Multi-select·Medium·4.0 · 0·~1 min

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.

Quick reference

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

Detailed answer & 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.

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.

5 minutes: explain why HNSW deletes are logical, walk through the three real symptoms with quantitative grounding, then dispatch the two distractors and finish with the production monitoring story.

Real-world examples

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
Milvus 2.x exposes growing, sealed, and flushed segment states; deletes accumulate as bitmap entries until segments are compacted
Qdrant's optimizer reclaims tombstoned vectors during background segment merges and exposes the cadence as a tunable in production configs

Interviewer follow-ups

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

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

QHow do tombstones interact with the LSM-style segment architecture used by Milvus, Qdrant, and Pinecone serverless?

Don't say this

Red flags and common mistakes 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 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.