Keeping a Vector Index Current Without Rebuilding It

An index built once from a frozen corpus is a solved problem: encode everything, build the structure, serve it read-only. A corpus that changes is a different problem, because the structures that make vector search fast are the structures that make it hard to modify. A graph index derives its adjacency from the global neighbourhood relation, so inserting a vector changes the correct neighbours of nearby vectors, and deleting one invalidates paths that other vectors route through. A cluster index derives its cells from a k-means fit over the whole corpus, so adding data shifts the centroids that every existing assignment was computed against.

Rebuilding is the honest answer, and it is unaffordable for anything but a small corpus. A corpus of ten million chunks re-embedded and re-indexed takes hours of accelerator time, and during that time the index is either stale or double-provisioned. The structures that solve this in text search are the same ones that solve it here, and they are borrowed from log-structured merge trees: write immutable segments, never modify one in place, and merge segments in the background.

Segments make writes append-only

The base arrangement is a set of immutable segments, each a self-contained index over a subset of the corpus. A new document is encoded and written into a small new segment, which is built entirely in memory and flushed when it reaches a size threshold. Nothing existing is touched, so an insert costs one encode plus one small build, and the write is atomic from the reader’s perspective: either the new segment is in the visible set or it is not.

Queries fan out across all segments. Each segment is searched with its own budget, and the per-segment results are merged by score into a global top k. The merge is a k-way merge over sorted candidate lists, so its cost is proportional to the number of segments times the depth requested, which is small. The cost that grows is the fan-out itself: with twenty segments, a query does twenty searches, and each has its own fixed overhead of setup, entry-point selection, and result collection.

The segment count is therefore the parameter that trades write cost against read cost. Flushing rarely produces large segments and fewer of them, which lowers fan-out and raises the amount of work lost on a crash before the flush. Flushing often produces small segments and high fan-out. The mechanism that reconciles the two is compaction.

Compaction and the write amplification it introduces

Compaction merges several segments into one, discarding tombstoned entries and rebuilding the merged structure over the surviving vectors. It runs in the background, writes a new segment, and then atomically swaps the input segments out of the visible set.

The cost is write amplification. A vector written once may be rewritten on every compaction that includes its segment. With a levelled policy that merges segments of similar size, a vector is rewritten a logarithmic number of times in its lifetime, and the constant depends on the size ratio between levels. With a tiered policy that merges segments of similar age, the amplification is lower and the number of segments at any moment is higher. The trade is the same one the LSM tree makes for key-value stores, and the same conclusion applies: levelled minimises space amplification and read cost at the price of write cost, tiered does the reverse.

For a vector index the write cost is not just bytes. A merged segment must be rebuilt, and building a graph index over the merged vectors is the expensive part: it requires constructing adjacency, which is a nearest-neighbour problem over the segment’s own contents. Merging two segments of a million vectors each is not a copy of two million vectors, it is a fresh build over two million vectors. That is why compaction for vector indexes is scheduled conservatively and why the per-segment build is often done with a cheaper construction parameter than a full rebuild would use.

Deletion is where the asymmetry shows. A deleted vector cannot be removed from an immutable segment, so it is marked in a tombstone bitmap, and searches skip it. The vector still occupies its bytes, still appears in the graph, and still influences the adjacency of its neighbours, which means it can still act as a routing waypoint. A segment with 40 percent tombstones costs the same to read as a full segment while returning 60 percent of the results, and its graph quality degrades because the deleted nodes were not chosen as waypoints for a graph that excludes them. Compaction is the only way to reclaim that space, and until it runs, deletion has made the index worse without making it smaller.

def merge(segments, tombstone_of, build):
    keep = []
    for seg in segments:
        dead = tombstone_of(seg)
        for i, vec_id in enumerate(seg.ids):
            if vec_id not in dead:          # survivors keep their attributes
                keep.append((vec_id, seg.vectors[i], seg.meta[i]))
    merged = build(keep)                    # fresh adjacency over survivors only
    return merged                           # caller swaps visible set atomically

The build step is where the cost lives, and the reason compaction is throttled by a budget rather than run to completion.

The visibility window

Between a document being written to the corpus and its vector being searchable, several delays accumulate, and each is a distinct source of staleness.

The first is encoding lag: the document waits in a queue for the encoder. Encoding is batched for throughput, so a document may wait for a batch to fill or for a timer to expire. The second is flush lag: the encoded vector sits in memory until the segment is flushed, which may be triggered by size or by time. The third is the search-time visibility of the new segment, which is usually immediate after the flush. The fourth is deletion visibility, which is immediate if the tombstone is applied synchronously, and the fifth is compaction, which affects space and graph quality rather than visibility.

The total lag is what a caller observes, and it must be bounded by an explicit policy. A common arrangement sets a maximum flush interval so that a document becomes searchable within a known window, accepting small segments in exchange for the bound. The alternative, flushing only on size, gives better read performance and an unbounded lag for a corpus that receives a trickle of updates.

There is a correctness edge case in the window: a document updated twice before either version is flushed. The second write must either supersede the first in memory or produce two segments with the same logical identifier, in which case the query merge must prefer the newer and the tombstone must be applied to the older. If the identifier used for deduplication is derived from content rather than from a stable document key, the two versions look like distinct documents and both are returned. The identifier choice is therefore part of the index schema, not an implementation detail.

Re-embedding is a different operation from re-indexing

Two kinds of change look similar and have very different costs.

A content change requires a new vector: the document text differs, so the encoder must run again. The old vector is tombstoned, the new one is written, and the rest of the pipeline is unaffected. This is the ordinary write path.

An encoder change requires every vector to be recomputed, because the new model’s space is not comparable to the old one. Mixing vectors from two encoder revisions in one index produces distances that are meaningless: a pair of vectors from different revisions has no consistent geometric relationship, and the resulting ranking is arbitrary. The only correct handling is a full re-encode, which is the rebuild the segment structure was designed to avoid.

The standard technique for making that rebuild non-disruptive is a parallel index: build the new index under a new name while the old one serves traffic, then switch. The switch is atomic from the caller’s perspective if queries carry an index version and the router maps versions to indexes. The cost is double the storage and double the encoding work for the duration of the build, and the duration is set by the corpus size and the encoder’s throughput, not by anything the index can improve. For a corpus large enough that the build takes longer than the acceptable staleness of the content, the parallel build must itself absorb content updates, which means the new index needs its own incremental write path running during the build. That is a real engineering constraint and it is the reason encoder upgrades are planned rather than routine.

The layout that keeps both paths honest

The arrangement that survives contact with a changing corpus separates the bulk from the delta. A large immutable index holds the corpus as of the last compaction or rebuild, built with full construction parameters. A small mutable index holds recent additions, built cheaply, and is queried alongside the bulk index. Merging results across the two requires comparable scores, which is why both must use the same encoder, the same metric, and the same normalisation; the score comparability problem is the same one that appears when fusing lexical and dense results, covered in Hybrid Lexical and Dense Retrieval.

The delta index has a bounded size by construction: once it exceeds a threshold, it is merged into the bulk index or promoted to a second bulk segment. That bound is what keeps the query fan-out and the per-query overhead predictable, and it is also what makes the compaction scheduling tractable, since the work is proportional to the delta rather than to the corpus.

Two properties of this layout are easy to get wrong. The first is that the delta index needs the same metadata filtering support as the bulk index, or queries with restrictive predicates will behave differently depending on whether the matching document happens to be recent; the predicate handling described in Metadata Filtering Inside Vector Search must be implemented once and applied to both. The second is that deletion must be applied to the delta as well as the bulk, and a deletion that arrives for a document still sitting in the encoder queue must cancel that work rather than race it, or the document will be indexed after being deleted.

The remaining limitation is inherent: an index is a snapshot with a write path attached, and the snapshot’s age is a number the system must publish. Queries that depend on the newest material need to know the lag, and the honest interface reports it rather than implying that search reflects the corpus as of the moment of the request.