Tombstones, Merges, and the Cost of Keeping a Vector Index Current

An index that cannot absorb updates is a batch artifact. Documents change, records are deleted for legal reasons, embeddings are regenerated when a model is replaced, and the collection’s composition shifts continuously. Every one of those operations invalidates part of the index, and the structures that make approximate search fast are precisely the ones that resist in-place modification. A proximity graph’s edges encode a global property, reachability, that a local edit cannot preserve. A quantizer’s codebooks encode the distribution of the whole collection, and a record outside that distribution is encoded badly no matter how carefully it is inserted.

Why deletion is the hard case

Insertion into a graph index is well defined: find neighbors, link both ways, prune any list that overflows. Deletion is not, because removing a node severs paths. Every neighbor that linked to the deleted node now holds a dangling identifier, and simply dropping the link can disconnect a region that used that node as its only bridge.

The straightforward repair is to rewire: for each neighbor of the deleted node, search for replacement neighbors among the deleted node’s other neighbors. That is a local search with a local candidate set, and it can fail to find a suitable replacement when the deleted node was the sole connection between two clusters. The rewire then produces a graph that is connected in the sense of having no dangling links and disconnected in the sense that matters, and the recall loss is invisible until a query happens to need the severed path. The link structure being repaired is the one described in HNSW Layer Assignment and the Greedy Descent, where the same edges serve both to route and to bound the result set.

Most implementations take the cheaper route: mark the node deleted and leave its edges in place. The node continues to participate in traversal as an intermediate hop, and it is filtered out of the result set. This preserves reachability exactly and costs nothing at deletion time.

The cost is deferred and compounding. A tombstoned node still occupies its adjacency list, still occupies its vector, and still consumes a page read on every traversal that passes through it. If a collection turns over at a rate of a few percent per month, then after a year a substantial fraction of the graph is routing traffic for records that no longer exist, and both memory and latency have grown while the logical collection has not. Worse, the live records’ neighbor lists contain many tombstones, so a node’s effective degree, meaning the number of live neighbors reachable in one hop, is lower than its configured degree, and the graph’s navigability degrades in a way no parameter setting reveals.

The metric that exposes this is the ratio of live records to stored nodes. It should be tracked explicitly, and the index should be rebuilt or compacted when the ratio falls below a threshold chosen from the recall target rather than from a round number.

Segment-and-merge

The alternative to in-place modification is to treat the index as a set of immutable segments, each built once over a batch of records, with deletions represented as a separate tombstone set that is consulted at query time. This is the log-structured merge pattern applied to vector search, and it makes every operation cheap by deferring the expensive part.

An insert creates a small new segment or appends to a mutable in-memory one. A delete adds the identifier to a tombstone set. A query searches every segment, unions the candidates, removes tombstoned identifiers, and reranks. The union is exact in the sense that a record present in any segment is found, provided the query reaches it in that segment’s own search.

The query cost grows with the number of segments, because each segment’s search has its own fixed overhead: an entry point, a descent, a candidate list. With many small segments, the fixed overhead dominates and the system performs many shallow searches instead of one deep one. That is why the segment count must be bounded by merging: when the count exceeds a threshold, the smallest segments are combined into a larger one, rebuilt from their live records.

The merge is where the work happens. Rebuilding a segment from scratch costs a full construction over its records: for a graph, that is one insertion per record with the full efConstruction search, which is the expensive part of any build. The amortized cost per insertion over the index’s lifetime depends on the merge policy, exactly as in log-structured merge trees. A policy that merges segments of similar size keeps the number of merges per record logarithmic, at the cost of write amplification proportional to the number of levels.

Deletions are handled by the merge rather than by the tombstone set, once a segment’s dead fraction crosses a threshold. Merging a segment whose records are half dead produces a new segment half the size, and the tombstone set shrinks accordingly. A segment that is entirely dead can be dropped without any rebuild at all, which is the cheapest possible compaction.

import math

def should_merge(sizes: list[int], dead: list[int], max_segments: int = 8,
                 dead_fraction: float = 0.3) -> list[tuple[int, ...]]:
    """Return groups of segment indices to merge.

    Two triggers: too many segments, or one segment mostly dead.
    The first keeps query overhead bounded; the second reclaims space.
    """
    plan = []
    for i, (n, d) in enumerate(zip(sizes, dead)):
        if n and d / n >= dead_fraction:
            plan.append((i,))
    if len(sizes) - len(plan) > max_segments:
        order = sorted(range(len(sizes)), key=lambda i: sizes[i])
        group = tuple(order[: max(2, len(order) - max_segments + 1)])
        plan.append(group)
    return plan

The policy above is deliberately crude; production policies weight by size and by age, and choose the merge group to keep the size ratio between merged segments bounded. What matters structurally is that the decision is made from segment metadata alone, without inspecting records.

The cost of a rebuild, and when it is right

A full rebuild discards the graph and constructs a new one from the current live records. Its cost is one construction pass, which for a graph index is dominated by the neighbor searches performed during insertion: each insertion performs efConstruction-wide searches at every layer, so the total is roughly proportional to $n \cdot \text{efConstruction} \cdot \log n$ distance computations. At a million records with efConstruction around 200 and five layers, that is on the order of a billion distance computations, each involving a vector fetch.

That cost is why rebuilds are scheduled rather than triggered casually, and why the segment approach exists. But a rebuild has a property no incremental repair has: the resulting graph is constructed against the final collection, so every node’s links were chosen knowing all the records it could connect to. Incremental insertion cannot do that, because a record inserted early never sees the records inserted later, and its links reflect only the collection as it was. The difference is measurable as a recall gap between an incrementally built index and a bulk-built one over the same records, and it grows with the fraction of the collection that arrived after the index was created.

The practical rule: incrementally maintained indexes should be periodically rebuilt from a bulk construction, and the interval should be set by how much the collection has changed rather than by a calendar. A collection where ten percent of records are new since the last rebuild has a graph whose early records are connected to a collection that no longer exists.

Bulk construction can also exploit parallelism in ways incremental insertion cannot. Building separate graph partitions in parallel and then stitching them with cross-partition links is a standard technique, and the stitching is a bounded number of insertions rather than a full pass. The result is not identical to a single-threaded build but is close enough that the recall difference is smaller than the parameter noise.

Quantizer drift, which rebuilds do not fix

The graph is only one of the structures that goes stale. Product quantization codebooks are trained on a sample of the collection, and every record is encoded against those centroids forever. If the collection’s distribution shifts, through new topics, a new language, or a new document type, the new records fall outside the region the codebooks cover, and their codes carry more error than the training records’. The index still returns them, because the code exists, but their approximate distances are unreliable and their ranking within a candidate set is noisy.

Retraining the codebooks is not a local operation. Every stored code is relative to the codebook that produced it, so a new codebook invalidates every code in the collection. There is no way to re-encode a record without its full vector, and if the full vectors were discarded to save space, which is a reasonable choice for a codes-only index, retraining is impossible without re-embedding the source documents.

The design decision that follows is whether to retain full vectors. Keeping them costs 32 times the code size at the parameters given for Product Quantization and the Asymmetric Distance Computation, and it is the only thing that makes re-encoding, exact reranking, and model migration possible. A system that discards them has committed to the current codebook and the current embedding model permanently, and its only migration path is a full rebuild from source.

The same argument applies to the embedding model itself. A model change invalidates every vector, not just the index structure, and the new vectors occupy a different space that is not comparable with the old ones. Mixing vectors from two models in one index produces distances that are meaningless across the boundary, and the failure is silent because both are valid vectors of the same width. Model migration requires a parallel index and a cutover, with both served during the transition, or a full rebuild with a window in which the old index is read-only.

What to measure

Three quantities tell whether maintenance is keeping up.

The live-to-stored ratio, as above, captures tombstone accumulation. It should be monitored per segment, since an aggregate number hides one segment that is entirely dead.

The recall of the current index against exact search over the current collection captures everything else: stale links, drifted codebooks, and the incremental-versus-bulk gap. It is the only measurement that reflects the system as it actually is rather than as it was designed, and it must be run against the live collection because a recall figure computed at build time says nothing about the index a month later.

The segment count and the merge backlog capture the maintenance process itself. A backlog that grows means merges are not keeping pace with inserts, and the query cost will rise as the segment count does. The steady state has a bounded number of segments and a merge rate proportional to the insert rate.

None of these are exotic, and all three are cheap to compute relative to the cost of discovering the problem through user-visible result quality. The structural point is that a vector index is not a static artifact that is built once; it is a structure with a maintenance cost that grows unless it is actively compacted, and the compaction is expensive enough that its scheduling is a design decision rather than an operational afterthought.