Tombstoned vectors keep spending search budget until compaction runs

A tombstone is a mark saying that a record has been deleted, written in place of removing the record. Vector stores use them for almost every delete: an id goes into a side structure listing what must never be returned, and the vector itself stays exactly where it was written, with all of its neighbours still pointing at it. A store that has accepted a million deletes and returned success on every one of them can be holding a million more vectors than it will admit to, and every gauge that counts what the store will return shows nothing at all.

The reason that gap costs money is the structure underneath it. HNSW — hierarchical navigable small world — is the graph index most vector stores build by default: every vector is a node, each node keeps a short list of edges to nearby nodes, and a query walks from node to node looking for the closest ones. ef_search is the size of the working shortlist that walk keeps as it goes, the pool of best-so-far candidates from which the final results are drawn. A tombstoned node behaves like any other node during that walk — it is visited, the distance from the query to it is computed, and it takes a place on the shortlist — and only at the very end is it dropped for being deleted. The bill arrives as p95 retrieval latency, the figure that 95% of queries come in under, drifting upward; as resident memory rising with no new content; and as recall falling on a corpus whose live contents have not changed at all.

Why a graph will not let go of a node#

Start from what a node actually holds. An HNSW index is a layered proximity graph, and in it each node stores a list of out-edges — the neighbours it points at — and nothing else about its connectivity. The graph does not store in-edges, so a node carries no record of who points at it. Removing a node therefore begins by hunting for its in-edges, and the only place they exist is inside other nodes' out-edge lists, which means scanning the neighbour lists of an entire layer. Each node found holding an edge to the doomed one is then left with a hole in its list, and a hole makes the graph less connected, so each of those nodes needs a replacement neighbour — which means running a small search to find one.

Put a size on that chain. M = 32 is the number of out-edges each node keeps, so on a 40-million-node graph at M = 32 the layer-zero neighbour lists hold well over a billion edges, and one pass over them to find the in-edges of a batch of doomed nodes is tens of millions of edge-list scans. Repairing what that pass turns up is millions of local searches, one per broken edge, to remove a few million vectors. All of it has to run while the index is serving, on the same cores and against the same memory bandwidth as the queries.

Only one link in that chain is a design decision rather than a consequence. Storing out-edges and not in-edges is a choice, and the reason to make it is insertion: a new vector finds a good entry point, wires up its own edge list and prunes a few neighbours' lists, and nothing else in the graph has to be told anything. A structure that also kept back-pointers would make deletion tractable and would pay for it with a second edge list per node, maintained on every single insert, in a workload where inserts vastly outnumber deletes. Everything after that first link follows from the structure rather than from taste.

Every production engine therefore does the same thing in different clothes: it records the deletion in a side structure — a bitset, a delete map, a liveDocs array — and filters deleted ids out of the result set at the end of a search. The vector stays. The edges stay. The memory stays.

What a dead node costs a search#

The cost shows up in three places, and they arrive in a specific order: memory first, latency second, recall third and worst. Only the third one is about answers being wrong, and it is the one that moves earliest.

Memory goes first because it is arithmetic rather than behaviour, which makes it the easiest of the three to see and the easiest to misread. A raw vector at 1024 dimensions in float32 is 1024 components at four bytes each, which is 4,096 bytes, and an M = 32 HNSW node costs roughly another 260 bytes for its edge list at layer 0. Add the two and one tombstoned vector occupies about four and a third kilobytes of resident memory, exactly as a live one does, because it is byte for byte the same object with a flag set somewhere else. Eighteen million of them is about 78 GB, and a capacity dashboard, which measures bytes and knows nothing about intent, attributes all of it to growth.

Latency goes second. A traversal that expands ef_search candidates spends a distance computation on every node it visits, and a dead node is indistinguishable from a live one until the filter at the very end, so the arithmetic is done in full and then thrown away. With 31% of the graph tombstoned, roughly 31% of the distance work is discarded. That proportion holds as long as the tombstones are spread through the graph in about the same proportion as the live vectors; a delete pattern that removes whole neighbourhoods at once concentrates the waste on the queries that happen to land near them, and leaves the rest untouched.

Recall goes third and matters most, and it is the one worth deriving rather than asserting. The search keeps a candidate heap of size ef_search. A dead node that gets visited takes a slot in that heap exactly as a live one does, since nothing has told the traversal it is dead. Only the survivors can become results. So the number of slots doing work that can end up in an answer is not ef_search but ef_search less the share of them holding dead nodes, which to a first approximation is ef_search × (1 − tombstone_ratio) — the tombstone ratio being the count of deleted-but-resident vectors over total resident vectors. Work one instance: at ef_search = 64 and a tombstone ratio of 31%, sixty-four times sixty-nine hundredths is a little over forty-four. You are searching with an effective width of 44 while your configuration file says 64, and nothing in the configuration file is wrong.

The plain-words version of that is worth holding on to, because it is what makes the rest predictable. Tombstones shrink the search rather than degrading it: the traversal is exactly as good as it ever was at exploring a heap of a given width, and the width is the thing that has quietly been taken away. Every number tuned against a width of 64 — recall at a given k, the point at which raising ef_search stopped paying for itself — was tuned against a width the index no longer has.

Tombstones compound with metadata filters rather than adding to them, and the compounding is the case worth being able to predict. A query restricted to one publisher already narrows the candidate pool, and when the filter is applied after the graph traversal — which is the common implementation for low-selectivity filters, because filtering during the walk can cut the traversal off from regions it needs to cross — then dead nodes and filtered-out nodes both consume heap slots before anything survives. Two independent shares of the same heap are being lost, so the factors multiply instead of adding: sixty-four, times sixty-nine hundredths for the tombstones, times two tenths for a filter that admits 20% of a corpus, lands near nine. An effective width near 9 out of a configured 64 is how a system that measures fine on unfiltered benchmark queries returns four results for a limit=10 request in production.

That last step also names the condition under which a recall check is blind. Recall checks run only on unfiltered queries will not see this, because neither factor is present in an unfiltered query — the filter term is absent by construction, and the tombstone term alone leaves a width of 44, which is enough to look healthy. The frozen query set is worth building with the same filter distribution the application actually issues.

What happens to the ratio next is the engine's decision rather than yours, and the four engines most people meet record a delete in much the same way while reclaiming it on quite different terms.

The common structure across all four is that reclamation is a rewrite, and rewrites are scheduled by the engine according to thresholds you can usually configure but frequently have not. That is how a system reaches 31%: every default in that table reclaims lazily, on the assumption that deletes are rare, and a rolling-window corpus violates the assumption continuously.

Measuring it before the capacity alarm#

The gauge that fails here is the live-vector count, and it fails in the way defences usually do. A gauge reporting how many vectors a store will return is constant in exactly the period when the quantity it has to discriminate — how many vectors the store contains — is varying. The mistake is tempting because on a rolling-window corpus the live count is the business quantity: it is the number every other team asks for, it is the one that belongs on a status page, and through a period like the one below it behaves perfectly, reading essentially the same figure month after month while the resident count climbs by nearly half. Every delete that produced the divergence was a correct API call that returned success, so there is no error rate to watch either. What discriminates the two situations is the deleted count graphed beside the live one, and a recall measurement against exact search.

Those are the two numbers, and neither is on a default dashboard. The first is the tombstone ratio, and most engines expose it, though rarely under that name — Qdrant reports deleted_vectors_count alongside vectors_count per collection, Lucene-based stores report docs.deleted next to docs.count, and in Postgres you read it from pg_stat_user_tables as dead tuples against live ones. It belongs on the same dashboard as latency, with an alert well below the engine's own compaction threshold, because by the time the engine decides to act you have already been serving degraded recall for weeks.

Picking that alert threshold is a question about your delete rate rather than about the engine, and it is a division you can do on paper. A corpus that deletes 5% of its vectors a month and reclaims none of them adds 5% to the ratio every month, so it arrives at an engine's default 20% trigger after four months of accumulation. An alert at 10% therefore sits two months in from a clean index and two months short of the engine acting on its own, which is roughly two months of warning. If each alert is answered by reclaiming, the ratio resets and takes another two months to climb back, so the alert fires a handful of times a year — which is the rate at which an alert still gets read rather than muted.

The opposite regime inverts the reasoning rather than rescaling it. A corpus with almost no deletes should alert far lower, at 3% or so, because on a store whose ratio should sit near zero a jump to 3% is not accumulation at all. It means a delete path has started running when it should not — a retention job with a wrong date filter, or the reconciliation from chapter 2, where an update is treated as a reconciliation against the chunks a previous revision left behind, deleting far more than it should. The property that makes the low threshold work is that the gauge is doing double duty as a correctness alarm on the write path, and an alarm on a write path wants to fire on the first day rather than the fortieth. That is the reason to graph the absolute deleted count next to the ratio: a ratio moves slowly on a large index, while a count jumps the moment a bad job runs.

The second number is recall against exact search, and it has to be measured rather than inferred. Take a frozen set of a few hundred production-shaped queries, run each through the approximate index and through a brute-force scan over the same collection, and compute the overlap of the top-k.

def recall_at_k(queries: list[list[float]], k: int = 10) -> float:
    hits = 0
    for q in queries:
        approx = {p.id for p in vectors.search(q, limit=k, params={"hnsw_ef": 64})}
        exact = {p.id for p in vectors.search(q, limit=k, params={"exact": True})}
        hits += len(approx & exact)
    return hits / (k * len(queries))

Exact search on 40 million vectors is a full scan and costs somewhere between 400 ms and several seconds per query depending on hardware and on whether the vectors are quantized into a compressed form, which is why this runs as a scheduled job over a sample rather than as a per-query check. Three hundred queries nightly is roughly five minutes of compute and produces a time series that moves before anything else does.

One media company running a 40-million-vector index over article chunks went back and reconstructed its own series from monthly snapshots, and the ordering of the columns is the whole argument for measuring recall at all.

Recall had lost eight points before latency had moved enough for anyone to open a ticket, and the capacity alarm — set at 80% of a 320 GB ceiling — had still not fired in October. That ordering is the practical argument for the recall check: the two signals that page you are lagging indicators of a quality problem that started in the spring, and the third one, which nobody was running, had been falling since April.

The tempting remedy, once latency and recall are both visibly wrong, is to raise ef_search, and it does work in the narrow sense. Going from 64 to 128 on the October index brought recall@10 back to 0.955 and pushed p95 to 89 ms. The mechanism is the width algebra run backwards: doubling the configured heap doubles the slots, the tombstones still take their same share of them, and the number left over for live candidates roughly doubles with it. What that buys back is the search width the tombstones took, and what it pays is doing the wasted distance computations twice over, which is where the 89 ms comes from. The trade is occasionally the right emergency action — it is a configuration change, it takes effect immediately, and it needs no maintenance window — and it is a compensation rather than a repair. The repair is to reclaim.

Forcing reclamation, and what it costs#

Reclamation is available in three grades. The gentlest is to tune the engine's own thresholds so that compaction runs more eagerly — dropping Qdrant's deleted_threshold from 0.2 to 0.05, or lowering Lucene's allowed deleted percentage — which keeps the ratio in a band without any manual operation and spends a background CPU budget continuously. The middle grade is a scheduled optimize or force-merge during a quiet window, which is a bulk rewrite of segments and behaves like a short, intense background job. The heaviest is a full rebuild of the index from the stored vectors, which produces the best graph and takes the longest.

# Qdrant: make the vacuum optimizer act at 5% deleted instead of 20%
curl -X PATCH "$QDRANT/collections/articles" \
  -H 'content-type: application/json' \
  -d '{"optimizers_config": {"deleted_threshold": 0.05, "vacuum_min_vector_number": 10000}}'

-- Postgres/pgvector: reclaim entries, then rebuild the graph without blocking reads
VACUUM (ANALYZE) article_chunks;
REINDEX INDEX CONCURRENTLY article_chunks_embedding_hnsw;

None of these are free, and the specific cost that surprises people is transient space. A merge or a concurrent reindex writes the new structure before dropping the old one, so peak disk and, for memory-resident indexes, peak RAM can approach double the steady-state footprint of whatever is being rewritten. The 251 GB index that media company was running needed headroom it did not have, which is why the rebuild happened on a fresh node rather than in place.

Planning the window needs a rate. Build throughput for HNSW at M = 32, ef_construction = 200 runs on the order of 3,000 to 8,000 vectors per second on commodity hardware, so 40 million vectors is roughly two to four hours on 16 cores, and that number is worth measuring on your own data before you plan a window around it. The rate is an aggregate for the whole build rather than a figure per core, and the hours fall straight out of it: 40 million divided by three thousand a second is a bit under four hours at the slow end, and divided by eight thousand a second is under an hour and a half at the fast end. ef_construction is the width of the candidate list used while building, the construction-time counterpart of ef_search, and raising it buys graph quality with build time — which is why a throughput figure means nothing unless the value it was measured at comes with it.

Live orphans, drift and a change of model#

A tombstone ratio of zero does not mean the index is healthy, and the clearest counterexample is the one chapter 2 describes, where a shortened revision leaves its later chunks behind in the index. Those orphaned chunks were never deleted, so no tombstone was ever written for them, and they are live vectors by every definition the engine has. They survive every compaction and every rebuild, and they arrive in the new graph as first-class citizens with fresh edges — if anything slightly easier to retrieve than they were before. Reclamation is a fix for deletes you issued, not for deletes you failed to issue, and neither of the two gauges above can see the second kind.

Nor does the tombstone ratio explain drift on a corpus with few deletions. An index that only ever grows can still lose recall as the graph's neighbourhoods stop reflecting a shifting distribution of content, because each node's neighbourhood was chosen against the distribution that existed when that node was inserted, and a shifting one leaves the early nodes wired to neighbours that are no longer among their nearest. Chapter 8, which walks the ordered diagnosis for a search that has degraded with no deploys behind it, puts tombstones first in that order for a reason that is about cost rather than likelihood: they are the cheapest thing on the list to rule out. They are the first thing you check and rarely the whole answer.

The last row of that table settles a question in a way that does not generalise, and generalising it is expensive. It was a rebuild: the same vectors, the same model, the same dimensionality, reconstructed into a better graph, so the only thing at risk was the operation — the spare node, the window, the transient headroom. Nothing about what the numbers mean changed, which is the only reason the recall figure from after the rebuild could be compared against April's at all.

Everything above is one identity read two ways. A delete that a graph index accepts is a mark on a node that stays, so the memory a store loses and the search width it loses are the same population of vectors counted twice, and both are invisible to a gauge that reports what the store will return. Eighteen million tombstones were about seventy-five gigabytes of capacity growth that nobody could source, and twenty of the sixty-four candidate slots the configuration file promised, and neither figure existed anywhere on a dashboard until somebody counted the vectors the store contained rather than the ones it would hand back.

The two gauges that would have caught it are cheap: the deleted count graphed beside the live count, and recall against exact search on a frozen query set that carries the same filters production issues. Both point at the same repair, which is to reclaim on a schedule you chose rather than one the engine's defaults chose for you. That repair holds for as long as the vectors themselves stay put. The moment they have to change — because the embedding model has been replaced — none of this applies, and treating that as a bigger rebuild is the single most expensive misconception in index maintenance. Two generations of embeddings cannot occupy one index at all, for reasons that have nothing to do with graphs or compaction, which is where the next chapter, on why two embedding generations cannot share one namespace even at equal dimensionality, starts.