Embedding freshness and index rebuild without downtime

What it is

An embedding index has two clocks running at different speeds, and this page is about what happens when they disagree.

Document freshness is how quickly a new or changed document becomes retrievable. A product goes on sale, a document is edited, a listing is created: how long until a query can find it?

Model freshness is which version of the embedding model produced the vectors in the index. When you train a better encoder, every vector in the index was produced by the old one, and a query encoded with the new model is being compared against vectors from the old model. Those are different vector spaces, and cosine similarity between them is not merely degraded, it is meaningless.

That second point is the one that surprises people, so state it plainly: you cannot partially roll out an embedding model. With a lexical index you can reindex 10 percent of documents with a new analyzer and things degrade gracefully. With embeddings, a partially reindexed corpus means the index contains two incomparable coordinate systems, and the ranking between them is arbitrary. The similarity numbers still come out as floats between -1 and 1, which is why this failure is silent.

The related confusion: freshness is not the same as index build latency. A system can build an HNSW graph in 40 minutes and still have four-hour freshness, because the bottleneck is the pipeline around the build (change capture, embedding inference, batching, swap orchestration), not the build itself.

The problem it solves

Three concrete failures, each of which happens to teams that treat the vector index as a static artifact.

Stale content is invisible or wrong. On a marketplace, a listing created at 09:00 that is not searchable until 15:00 has lost the day's traffic. In a RAG system over internal documents, an updated policy document that still returns the old text is a correctness problem, not a latency problem, and the user has no indication that what they read is superseded.

Model upgrades are blocked. A team trains a better retrieval model, measures +6 percent recall offline, and then discovers that shipping it means re-encoding 80 million documents and rebuilding a 200 GB index, with no obvious way to do that without either downtime or a period of mixed-space nonsense. The improvement sits on a branch for two quarters. This is extremely common and it is an infrastructure failure masquerading as a modelling constraint.

Deletes linger. A document removed from the source system remains in the graph. For HNSW specifically, deletion is a soft-delete plus filtering at query time, because you cannot cheaply remove a node from a navigable small-world graph without damaging its connectivity. Accumulated tombstones degrade both recall and latency until a rebuild, and a compliance deletion that is only soft is not a deletion.

Mechanics

The two-tier architecture

The standard answer to document freshness is the same one Lucene arrived at decades ago and for the same reason: a large immutable base plus a small mutable delta, searched together, merged periodically.

                    query
                      │
              ┌───────┴────────┐
              ▼                ▼
     ┌─────────────────┐  ┌──────────────┐
     │  base index     │  │ delta index  │
     │  HNSW / IVF-PQ  │  │ flat, brute  │
     │  80M vectors    │  │ force, <200k │
     │  rebuilt nightly│  │ seconds old  │
     └────────┬────────┘  └──────┬───────┘
              │                  │
              └────────┬─────────┘
                       ▼
              merge top-k, apply
              tombstone filter

The delta index is brute force on purpose. A flat scan of 200,000 vectors at 768 dimensions is about 150 million floating point multiply-adds, which with SIMD is a few milliseconds on one core, and it needs no graph construction so a new vector is searchable the moment it is written. Building an HNSW graph for the delta would add index-time latency for no query-time benefit at that size.

The merge is a k-way merge on distance, which is only valid because both indexes use the same model. That constraint is worth flagging in the code, because it is the invariant that a model rollout breaks.

def search(query_vec, k, base, delta, tombstones):
    # Both indexes MUST be from the same model version. Enforced at swap time.
    assert base.model_version == delta.model_version

    hits = base.search(query_vec, k * 2) + delta.search(query_vec, k * 2)
    hits = [h for h in hits if h.doc_id not in tombstones]

    # Dedup: a doc updated after the base build appears in both. Delta wins.
    best = {}
    for h in sorted(hits, key=lambda h: (h.doc_id, -h.generation)):
        best.setdefault(h.doc_id, h)

    return sorted(best.values(), key=lambda h: -h.score)[:k]

The generation field and the delta-wins rule handle updates: an edited document appears in the base with its old vector and in the delta with its new one, and without that rule you would return both or return the stale one.

Over-fetching k * 2 from each tier is not optional. If you fetch exactly k from each and the true top-k is concentrated in one tier, the merge is still correct, but tombstone filtering after retrieval can drop you below k results. Fetching k + expected_deletes from each is the tighter version if you track deletion rates.

Model rollout: blue-green over the whole index

Since vector spaces cannot be mixed, the model rollout is an atomic swap of the entire index, which means blue-green:

Build green offline. Re-encode the full corpus with the new model, build the new index. This is an offline batch job, and it is the expensive step.
Dual-write during the build. New and changed documents are encoded by both models and written to both the blue delta and the green delta. Without this, the green index is stale by however long the build took, which for a large corpus is hours.
Shadow the queries. Encode each query with both models, query both indexes, log both result sets. Serve blue. This gives you a comparison on live traffic before any user is affected, and it is where you catch a normalisation bug or a dimension mismatch.
Swap by pointer. An alias or a routing config flips from blue to green. The query encoder version and the index version must flip together and atomically, which usually means the alias points at a tuple of (encoder version, index name).
Keep blue for a rollback window. Storage for two full indexes for a day or two is the price of a fast rollback, and it is cheap compared to the alternative of rebuilding under pressure.

The coupling in step 4 is the part that bites. If the query encoder deploys before the index alias flips, every query for that interval is encoded in the new space and searched against the old space, and the results are noise. Two common ways to make this safe: put the encoder version in the index alias resolution so they cannot disagree, or have the query path read the index's declared model version and select the matching encoder.

# The index declares its model; the query path follows it. No independent deploys.
index = registry.resolve("products")          # -> {name: "products_v7", model: "e5-large-v2"}
encoder = encoders[index.model]               # fails loudly if unavailable
qv = encoder.encode(query)
hits = vector_store.search(index.name, qv, k=100)

Making the rebuild cheaper: the two-stage decoupling

The expensive part of a rebuild is usually inference, not graph construction. Encoding 80 million documents at 2,000 documents per second per GPU is 11 GPU-hours; building HNSW over 80 million vectors is a few hours of CPU. This suggests separating them, and the separation is what makes frequent rebuilds affordable:

Store the vectors, not just the index. Keep the encoded vectors in durable columnar storage (Parquet on S3, or a table) keyed by document ID and model version. Then:

Rebuilding the index (new HNSW parameters, new shard layout, tombstone compaction) reads vectors from storage: cheap, no GPU.
Rebuilding the vectors (new model) is the expensive path and is the only one that needs inference.
A document whose content did not change does not need re-encoding when you re-shard.

Additionally, content-hash the encoder input. On a nightly refresh most documents are unchanged, and if you key the vector cache by hash(model_version, normalised_text) you re-encode only the delta. On a corpus with 2 percent daily churn this turns 11 GPU-hours into about 15 GPU-minutes, which is the difference between a quarterly reindex and a nightly one.

Tombstone compaction

HNSW soft-deletes. Each query filters deleted IDs from its results, which means a graph with 20 percent tombstones is doing roughly 20 percent wasted traversal work and, worse, the deleted nodes still act as routing hubs, so recall degrades because paths run through nodes that contribute no results.

The operational rule: track the tombstone ratio as a first-class metric and trigger a rebuild on a threshold, typically 10 to 20 percent. Lucene-based systems (Elasticsearch, OpenSearch) do this automatically through segment merges, and their deleted_docs percentage per segment drives merge policy. A hand-rolled vector service needs the equivalent, and forgetting it is a slow, invisible recall regression.

A worked example: an eight-hour freshness problem

A documentation RAG system over 4.2 million internal documents. Single HNSW index, rebuilt nightly at 02:00, taking 6 hours end to end. Effective freshness for a document edited at 09:00 was about 17 hours, and the reported symptom was "the assistant quotes the old version of the runbook."

Breakdown of the 6-hour build:

change capture + text extraction     0h 25m
embedding inference (4.2M docs)      3h 40m   ← the cost
HNSW construction (M=32, efC=200)    1h 20m
index upload + validation            0h 35m

Change one: content-hash the encoder cache. Daily churn was measured at 1.8 percent, roughly 76,000 documents. Encoding only changed documents took inference from 3h 40m to about 4 minutes. Note that this required storing 4.2M × 768 × 4 bytes of float32 vectors, roughly 12.9 GB, in Parquet on object storage, which cost a trivial amount per month.

change capture + text extraction     0h 25m
embedding inference (76k changed)    0h 04m
HNSW construction (full)             1h 20m
index upload + validation            0h 35m
                                     2h 24m

Change two: add a delta tier. New and changed documents go to a flat in-memory index within seconds of the change event. Freshness for a changed document dropped from 17 hours to under 90 seconds. The delta held about 76,000 vectors at end of day, and a brute-force scan of 76,000 × 768 floats added 3.1 milliseconds at p50 and 7 milliseconds at p99 to query latency, which was acceptable against a 180 millisecond budget.

Change three: full rebuild moved to weekly, with the nightly job doing only tombstone compaction and merging the previous day's delta into the base. The full rebuild remained necessary because HNSW's incremental insertion degrades graph quality over time (nodes inserted late have their connections chosen against a graph that no longer resembles the final one).

Results:

                             before        after
document freshness           17h           <90s
nightly job duration         6h 00m        1h 55m
GPU-hours per week           25.7          1.2
recall@10 vs exact           0.941         0.947   (fresher content, fewer tombstones)
p50 query latency            41ms          44ms
p99 query latency            118ms         127ms

Query latency got measurably worse, by about 8 percent, and that was the accepted trade: the delta scan is real work. It was worth stating in the design doc as the price rather than discovering it in a latency alert.

The model upgrade, six weeks later, then took the blue-green path. Re-encoding all 4.2M documents with the new model was a one-time 3h 40m GPU job (the content hash cache does not help across model versions, by construction, since the model version is part of the key). Dual-writing to both deltas during the build, shadow queries for 48 hours, then an atomic alias flip. Total elapsed time from decision to 100 percent traffic was four days, of which three were the shadow observation window rather than compute.

Production evidence

Lucene's segment architecture is the origin of the two-tier pattern: an in-memory buffer plus immutable on-disk segments plus background merges, with refresh_interval (default 1 second in Elasticsearch) controlling visibility. The tradeoff Lucene makes explicit, that more frequent refreshes mean more small segments and more merge pressure, is exactly the tradeoff a vector delta tier makes. See Lucene segments for the full mechanics.

Elasticsearch and OpenSearch apply the same model to their HNSW support: vectors live in Lucene segments, and HNSW graphs are built per segment, so segment merges rebuild graphs. This gives near-real-time vector search for free but means a merge is a graph rebuild, which is why merge policy tuning matters more for vector fields than for text fields.

Vespa supports real-time HNSW updates with concurrent read and write, and documents the tradeoff explicitly: incremental insertion is supported, and they still recommend periodic rebuilds because graph quality drifts.

Milvus and Qdrant both implement the growing-segment plus sealed-segment split (Milvus's terminology) which is the two-tier pattern under a different name: a growing segment is searched by brute force, and it is sealed and indexed once it reaches a size threshold.

Pinecone published on their approach to handling deletes and the recall degradation from tombstone accumulation, which is the clearest public statement that soft-delete has a quality cost rather than just a space cost.

The debate

Incremental updates versus periodic rebuild. Every vector database now supports incremental insertion into HNSW, so the question is whether you still need rebuilds. The argument for pure incremental is operational simplicity: no batch job, no swap orchestration, no double storage. The argument against is that HNSW's construction is greedy and order-dependent, so a graph built by inserting 80 million vectors one at a time has measurably worse connectivity than one built with the full set available, and tombstones accumulate.

My position: incremental for freshness, periodic rebuild for quality, and instrument the gap so you know when the rebuild is due. Concretely, run a nightly recall check against a brute-force baseline on a fixed query set. When measured recall drops more than 1 to 2 points below the post-rebuild figure, rebuild. That turns "how often should we rebuild" from a guess into a measurement, and it is the single most useful piece of instrumentation on a vector index.

How fresh does freshness need to be? Push back on "real time" as a requirement, because it is expensive and usually unexamined. The variables that decide it: how soon after creation does a document get its first query (measure this from logs), what does a user do when they cannot find something they just created (retry, or file a ticket, or leave), and is there a compliance deadline on deletion. A marketplace with sellers refreshing their own listing page needs seconds. A documentation corpus needs minutes. A quarterly financial filings archive needs hours. Committing to seconds when minutes would do buys a delta tier, a change-capture pipeline and a permanent latency tax.

Should you keep the raw vectors in object storage? Yes, essentially always. The storage cost is small relative to the GPU cost it saves, and it decouples "rebuild the index" from "re-run inference," which is what makes index-parameter experimentation affordable. Teams that do not do this find that trying M=48 instead of M=32 costs a full re-encoding run, so they never try it.

Where the two-tier pattern is the wrong answer: when the corpus is small enough that a full rebuild is minutes. Below roughly a million vectors, rebuilding the whole HNSW graph takes single-digit minutes on a normal machine, and rebuild-and-swap every 5 minutes is simpler than a delta tier, a merge path and a tombstone filter. Do not build the sophisticated version until the arithmetic says you need it.

Follow-up Q&A

"Why can't you mix vectors from two model versions in one index?"

Because the models learned independent coordinate systems. Nothing constrains the new model's dimension 37 to mean what the old model's dimension 37 meant; training is invariant to rotations and permutations of the embedding space, and two runs of the same architecture on the same data produce incomparable spaces. So a cosine similarity between an old-model document vector and a new-model query vector is a similarity between arbitrary directions in unrelated spaces. It returns a number, which is what makes this dangerous: there is no error, just quietly wrong rankings. The narrow exception is a model trained with an explicit alignment objective against its predecessor, which some teams do specifically to allow rolling migration, and it is a real technique but you have to build for it deliberately.

"How do you validate a new index before swapping?"

Four gates, in order of cost. (1) Structural: vector count matches the source of truth, dimension is right, no NaNs, norms are in the expected range (a normalisation bug shows up here and nowhere else). (2) Recall against brute force: sample 1,000 queries, compute exact top-10 by full scan, measure recall of the index's top-10. This catches a bad graph. (3) Golden query set: a fixed set of query-to-expected-document pairs that must still return the right answer, which catches semantic regressions the recall check misses because both indexes can be internally consistent and differently wrong. (4) Shadow traffic: live queries against both, compare result-set overlap and rank correlation. A sudden drop in overlap on a subset of queries localises the problem. Only then flip.

"What is the tombstone ratio and what do you do about it?"

Deleted-but-still-present vectors as a fraction of the index. It costs traversal work and, more importantly, recall: deleted nodes remain in the graph as routing hops, so search paths pass through nodes that yield nothing. Track it per shard, alert above about 10 percent, and rebuild or compact. The subtle version of this problem is a high-churn corpus where documents are updated rather than deleted: each update is a delete plus an insert, so a corpus with 5 percent daily updates accumulates tombstones faster than its deletion rate suggests.

"How do you handle a rollback after the swap?"

Keep blue alive and keep dual-writing to blue's delta for the rollback window. That second part is what people forget: if you stop writing to blue at swap time, then rolling back four hours later means blue is four hours stale, and you have traded a quality problem for a freshness problem. Dual-writing for 24 to 48 hours costs a second embedding inference per changed document, which at 2 percent churn is negligible.

"A document is updated. Walk me through what happens."

Change event lands (CDC, a queue message, a webhook). The pipeline fetches the new content, hashes the normalised text, finds no cache entry, so it runs inference. The new vector goes to the delta index with a generation number and the document ID goes into the tombstone set so the base index's stale copy is filtered out. The document is now searchable with its new vector, and the old vector is suppressed, within seconds. At the next merge, the base index absorbs the delta and the tombstone is retired. If the update was a deletion instead, the tombstone is added with no corresponding delta entry, and the actual removal from the graph happens at the next rebuild, which matters for compliance deletions where you may need to prove the data is gone rather than filtered.

Common misconceptions

"Vector databases handle freshness for you." They handle insertion. The pipeline that detects a change, extracts the text, runs inference, and gets the vector to the database is yours, and it is where the hours go. A database that accepts an upsert in 5 milliseconds does not help if your change-capture job runs hourly.

"Rebuilding an index means downtime." Only if you rebuild in place. Build beside, validate, swap an alias. The genuine cost is storage for two indexes and the orchestration to keep both fed during the build, not availability.

"Incremental HNSW insertion is free." Insertion cost is comparable to a search (the algorithm searches for neighbours in order to link the new node), so a heavy write rate competes with query traffic for the same CPU. And the graph quality drift is real: a graph built purely incrementally over a long period will show measurably lower recall than a rebuilt one at the same parameters.

"Soft delete is fine, the documents are filtered out." Filtered from results, present in the graph, degrading recall and traversal, and still on disk. For a GDPR erasure request, "filtered at query time" is not deletion.

"We should just make the index real-time and stop rebuilding." You still need periodic rebuilds for graph quality and tombstone compaction, so you would be adding real-time complexity without removing the batch path. The two-tier design exists because both are necessary.

Interview delivery note

The line to say verbatim: "Embeddings from two model versions live in different coordinate systems, so a model upgrade is an atomic swap of the whole index, not a rolling deploy, and the query encoder version has to flip with the index in one operation or every query in between is nonsense." That is the non-obvious constraint that shapes the entire design, and stating it early tells the interviewer you have done this rather than read about it.

The senior-versus-staff separator is separating the two clocks. A senior engineer answers "how do you keep the index fresh" with a two-tier index and a delta, which is correct and is half the answer. A staff engineer notices there are two independent freshness problems with different mechanisms and different frequencies: document freshness solved by a delta tier at seconds, and model freshness solved by blue-green at quarters. Conflating them produces a design that does neither well.

The second signal is the cost decoupling: storing raw vectors so that re-indexing does not mean re-inferring, and content-hashing so a nightly refresh re-encodes 2 percent rather than 100 percent. Being able to say "that took the nightly job from 25 GPU-hours a week to 1.2" is the kind of specific that lands.

The Staff & Team Lead Interview Reference