Keeping RAG Indexes Fresh: Incremental Updates, Deletes and Tombstones

Three ways an index lies

An index can be wrong about a document in three distinct ways, and each has a different cause and fix:

• Stale: the document was updated, but the index still holds the old version. The assistant answers with yesterday's facts.
• Missing: the document is new and not indexed yet, or was re-indexed and the new chunks are not searchable yet. The assistant says it does not know, or answers from something less relevant.
• Undead: the document was deleted, but its chunks are still searchable. This is the dangerous one: deleted content often means retracted, confidential or legally removed content.

There is a fourth, subtler failure: the index holds the new version and fragments of the old one. That happens when chunk identifiers are assigned by position and a document shrinks, and it produces answers that quote paragraphs which no longer exist anywhere in the source. Freshness work is mostly about bounding the time a document can spend in each of these states and making sure the last two cannot happen at all.

From nightly rebuilds to change capture

A nightly full rebuild re-embeds every chunk, builds a new index and swaps it in. It is easy to reason about and guarantees that the index matches a snapshot. Its freshness is terrible by construction: a change made just after the snapshot waits almost 24 hours, so the p95 lag of all changes is close to a full day. It is also wasteful. If 2% of documents change per day, 98% of the embedding work recomputes vectors that already exist.

An incremental pipeline processes only what changed. Change events come from the source: database change-data-capture (Debezium and similar tools read the transaction log), webhooks from a document system, or a periodic diff against modification timestamps. Events are buffered into micro-batches, chunked, embedded and written to the index as upserts and deletes:

for batch in change_stream.micro_batches(max_wait_s=60, max_docs=500):
    for event in batch:
        index.delete(filter={"doc_id": event.doc_id})          # remove every old chunk of this document
        if event.type in ("create", "update"):
            doc = source.fetch(event.doc_id, version=event.version)
            chunks = chunker.split(doc)
            vectors = embedder.embed([c.text for c in chunks])
            index.upsert([
                {"id": f"{doc.id}:{doc.version}:{i}", "vector": v,
                 "payload": {"doc_id": doc.id, "version": doc.version, "acl": doc.acl}}
                for i, v in enumerate(vectors)])
    change_stream.commit(batch)                                  # only after the index write succeeded

The batch interval is the main freshness knob: a change waits on average half an interval before it is even picked up. Shorter intervals mean more, smaller writes, which some engines handle worse (many tiny segments, more frequent index refreshes). Commit the stream offset only after the index write succeeds, so a crash replays changes instead of losing them, and make the write idempotent, which deterministic chunk IDs give you.

Queueing arithmetic: when embedding becomes the bottleneck

Between the change stream and the index sits the embedding step, and its throughput decides whether the pipeline keeps up. The arithmetic is simple and worth writing down for your own numbers:

steady load   : (2 creates + 3.5 updates) per minute x ~5 chunks   = ~27.5 chunks/min
capacity      : 2 workers x 200 chunks/min                        = 400 chunks/min (7% busy)

bulk re-import: 13,500 docs x ~5 chunks in 30 minutes              = ~67,500 chunks
drain time    : 67,500 / (400 - 27.5)                              = ~180 minutes with 2 workers
                67,500 / (800 - 27.5)                              = ~87 minutes with 4 workers

Little's law  : backlog = arrival rate x waiting time

In steady state the pipeline is nearly idle and lag is dominated by the batch interval. During a burst the queue, not the batch interval, sets the lag, and every ordinary edit made during the burst waits behind it. Two practical consequences follow. First, size embedding capacity for the bursts you can predict (re-imports, migrations, backfills) and schedule them, rather than for the average. Second, give interactive edits a priority lane: a separate queue or a priority field, so that a user fixing a typo in a policy page is not stuck behind 67,000 catalogue rows. All numbers here are illustrative, matching the lab's model rather than any measured system.

Deletes, updates and tombstones

Neither HNSW graphs nor Lucene segments delete in place cheaply. Removing a node from an HNSW graph would leave its neighbours with dangling or missing links and could disconnect parts of the graph, so libraries mark the node as deleted instead: hnswlib's mark_deleted keeps the node for navigation and skips it in results, and can later reuse the slot for a new vector. Lucene-based engines write immutable segments; a delete sets a bit in a live-documents bitmap, and an update is a delete plus an insert into a new segment. Qdrant similarly marks points deleted and lets background optimizers rewrite segments. PostgreSQL with pgvector follows MVCC: an update writes a new tuple, and the old one stays until VACUUM removes it and its index entries.

These markers are tombstones, and they cost something until they are cleaned up:

• Latency: the search still visits tombstoned nodes or scans past deleted documents, then throws them away. With 20% tombstones, roughly a fifth of the graph work is wasted.
• Recall: a search that collects ef candidates and then drops the deleted ones returns fewer live candidates than it should, and heavily deleted regions of the graph navigate worse.
• Memory and disk: deleted vectors still occupy RAM and storage until segments are rewritten.

Doc-scoped updates make this visible quickly. If each update deletes a document's five old chunks and inserts five new ones, 3.5 updates a minute create about 25,000 tombstones a day; on an index of 100,000 live chunks, that is about a fifth of the index by evening.

Compaction: reclaiming the dead

Compaction (merging in Lucene terms, vacuuming or optimizing in vector databases) rewrites segments without their deleted entries and rebuilds the affected graph parts. It restores latency and recall and frees memory, and it costs CPU, I/O and a period of reduced query performance while it runs. Engines trigger it with a threshold on the deleted share:

The threshold is a genuine trade-off. Compact too rarely and tombstones accumulate, slowing every search. Compact too eagerly and the index spends much of the day in compaction, during which queries are slower. In the lab, latency against the compaction threshold forms a U: the best value is somewhere in the middle, and it moves when the update rate changes. Check the defaults and units for your engine version; they differ between systems and releases.

Chunk IDs decide whether old text survives

The most common freshness bug is not a slow pipeline but an ID scheme. If chunks are stored as doc_id#0, doc_id#1 and so on, and an update simply upserts the new chunks under the same positional IDs, then a document that shrinks from eight chunks to five overwrites the first five and leaves chunks five to seven untouched. Those orphan chunks keep the old text, keep matching queries and keep appearing in answers, indefinitely, because nothing will ever overwrite them.

The fix is to scope every write by document: delete all chunks whose doc_id matches before inserting the new set, or include the version in the chunk ID and delete older versions after the new ones are written (which avoids a window with no chunks at all). Store doc_id and version as filterable payload fields so these deletes are cheap. Framework helpers exist (LangChain's indexing API with a record manager tracks which chunk IDs came from which source and can clean up stale ones), but check their cleanup modes carefully: some only clean up documents seen in the current batch.

Deletes need the same discipline. A pipeline that only handles upserts, which is what many first versions do because the source only exposes "modified since", never learns about deletions. Use a source that emits delete events, or periodically reconcile the set of document IDs in the index against the source and delete the difference.

Takedowns, model upgrades and other special cases

Some deletes have deadlines. A legal or privacy request to remove content may need to be honoured quickly, and "the next nightly job" is unlikely to be acceptable; check the actual requirement with your legal team. Treat these as priority deletes: apply them through a fast path that bypasses the batch buffer, verify with a retrieval probe that the content no longer comes back, and remember the other copies: caches of retrieved passages or answers, conversation logs, evaluation sets and backups.

Embedding model upgrades are the one case where incremental updates do not work, because vectors from different models live in different spaces and cannot be mixed in one index. Build a new index alongside the old one, backfill it, dual-write changes to both during the backfill, compare retrieval quality, and switch with an alias (collection aliases in Qdrant, index aliases in Elasticsearch, a view or table rename in Postgres). Budget the backfill like a re-import: it is the largest burst your embedding pipeline will see.

A worked example: the Belgavi's Book Store catalogue

Suppose the hypothetical Belgavi's Book Store indexes 20,000 catalogue and policy documents, about 100,000 chunks. Over a day there are about 2,900 new documents, 5,000 edits and 700 deletions. With a nightly rebuild starting at 02:00 and two embedding workers, the rebuild takes over four hours, and the p95 lag of a change is about 22 hours. Because 40% of questions are about recently changed items, only about half of answers come from current content in the lab's model.

Moving to change capture with 15-minute batches on the same two workers costs the same per day and cuts p95 lag to about 14 minutes, but the first incremental version handles only upserts with positional IDs. Deleted titles keep appearing in answers and shrunken descriptions keep their old tails. Switching to doc-scoped IDs and propagating deletes fixes both, at the price of tombstones reaching about a fifth of the index by evening; a compaction threshold around 10 to 20% keeps p95 search latency in check. When the quarterly catalogue re-import rewrites 13,500 documents in half an hour, two workers leave the queue draining for about three hours; four workers and a compaction threshold near 20% keep lag under 40 minutes and latency in budget. Every figure is a calculated estimate from the synthetic model; the sequence of fixes is the transferable part.

Monitoring freshness

Freshness needs its own service-level objectives, separate from search latency and quality:

• Change-to-searchable lag at p50 and p95, measured from the source change timestamp to the moment a probe can retrieve the new version.
• Queue depth and drain time for the embedding pipeline, with alerts on sustained growth.
• Tombstone share per collection or index, and time since the last compaction.
• Reconciliation drift: documents present in the index but not the source (undead), and the reverse (missing), from a daily ID comparison.
• Canary documents: create, update and delete a synthetic document on a schedule and check that retrieval reflects each step within the SLO.

Common mistakes: measuring lag only for creates (updates and deletes are usually slower), ignoring deletes entirely, positional chunk IDs, letting a backfill share a queue with interactive edits, and never compacting because nothing failed yet.

How the lab maps to production

The lab simulates one day minute by minute on a synthetic corpus of 20,000 documents with two to eight chunks each. Creates, updates and deletes arrive as Poisson streams; the pipeline either rebuilds nightly or captures changes into micro-batches drained by embedding workers. The index tracks versions, orphan chunks and tombstones per document, compaction runs when tombstones pass your threshold, and one synthetic query per minute asks about a document, biased toward recent changes. Mission one replaces the nightly rebuild. Mission two fixes ghost chunks and undead documents. Mission three handles a takedown of 1,600 documents without letting tombstones blow the latency budget. Mission four sizes workers and compaction for a bulk re-import under a daily budget.

Run the lab: Keep the index fresh: batches, deletes, tombstones and compaction

The lab below replays one synthetic day of document changes through an index pipeline. The blue bars show changes waiting to be indexed, the amber line shows the share of the index that is tombstones, violet shading marks a full rebuild and pink shading marks compaction. The strip at the bottom splits the day's synthetic queries into answers from current content, stale or missing answers, and deleted documents that were still served. Start with the nightly rebuild, then load mission one.

Prefer a full-width view? Open the standalone lab. Your stars are saved in this browser and shown on the series hub.

What to do next

1. Measure p95 change-to-searchable lag for creates, updates and deletes separately, using probe queries rather than pipeline logs.
2. Check your chunk ID scheme: make every write delete or version all chunks of the document, so shrinking documents cannot leave orphans.
3. Confirm that deletes in every source system reach the index, and add a daily ID reconciliation between source and index.
4. Find your engine's tombstone and compaction settings, chart the deleted share over a week, and set a threshold deliberately.
5. Calculate how long your embedding pipeline takes to drain your largest predictable burst, and add a priority lane for interactive edits.
6. Write a runbook for urgent takedowns that covers the index, caches, logs and evaluation sets, and test it with a canary document.

Sources and further reading

• Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (HNSW)
• FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search (2021)
• Qdrant documentation: Optimizer (vacuum and deleted_threshold)
• hnswlib README (mark_deleted and allow_replace_deleted)
• Elasticsearch reference: Merge settings
• pgvector README (HNSW indexing and vacuuming)

Related in this series:

• Permission-Aware RAG: Filtering by Access Control Without Destroying Recall
• Chunking Strategies Compared: Fixed, Recursive, Semantic and Late Chunking
• HNSW Tuning for RAG: M, efSearch and the Recall Versus Latency Trade

Diagrams, examples and the lab model are original educational material. Lab numbers are calculated by a synthetic model, not measured on real hardware or services.

Views are my own and do not represent any employer, past or present.