Vector Index Tombstones: How Deleted Files Remain Searchable Until Compaction
Deleted files can remain discoverable when an index records a logical tombstone but older segments, replicas, caches, or derived chunks still serve searches.
Removing a PDF from a home NAS does not necessarily remove its embedding, thumbnail text, OCR output, or cached retrieval result. Many storage engines first mark records as deleted and reclaim their bytes later during compaction. Correct query paths should honor the marker immediately, but incomplete propagation or a bypassed filter can let stale evidence surface.
A Tombstone Separates Logical Deletion From Physical Reclamation
In append-oriented storage, rewriting a large segment for every deletion would be expensive. A tombstone records that an identifier is no longer live. Queries consult this state, while background compaction later merges segments and drops both the obsolete record and its marker when it is safe.
An explanation of database logical tombstones notes that tombstones prevent deleted rows from being returned before compaction removes their physical data. The same principle matters for vector systems even when their segment and deletion-map implementations differ.
This distinction explains why disk usage may not fall after deletion. It does not, by itself, explain a visible search result: a correct current query must exclude the tombstoned vector even while its bytes remain on disk.
A Deleted File Can Leave Several Independent Derivatives
One source file may produce chunks, embeddings, keyword postings, summaries, OCR text, thumbnails, and answer-cache entries. Deleting only the vector IDs leaves other retrieval paths intact. Re-ingestion under a new identifier can also create duplicates that the original deletion list does not cover.
Database guidance on compaction cleanup explains that reclamation occurs during compaction because rewriting data continually is costly. Until coordinated cleanup completes, physical storage and logical visibility must be treated as separate states. That distinction changes the resulting household decision.
A reliable deletion ledger therefore maps the source identity to every derivative and namespace. It also records the generation being removed, preventing a delayed delete event from accidentally hiding a newer replacement with the same filename.
Where Stale Replicas and Caches Break Deletion Semantics
Distributed or multi-process search adds propagation delay. One worker may honor the tombstone while another serves an older segment; a response cache may return a previously composed answer without querying the index at all. Backups can later restore the deleted derivative unless retention rules include it.
DataStax describes replica tombstones as markers propagated across replicas before eventual removal. The grace period protects against resurrection in distributed storage, but it also shows why premature cleanup and inconsistent replicas require careful coordination. This boundary remains visible during later evidence review.
The failure boundary is query visibility, not occupied bytes. If any supported search route can still return the deleted evidence after the promised deletion window, the system has not completed deletion even if a dashboard reports success.
Prove Deletion Across Every Search Path
Before deletion, record the source ID, derived chunk IDs, a unique phrase, and one cached question. Delete the file, then query by phrase, semantic paraphrase, metadata filter, source ID, and the cached question before and after compaction.
Use the same current-file discipline described in incremental indexing state: the test should distinguish logical visibility, physical storage, and historical retention. Inspect every configured replica or worker rather than trusting one successful query. The dependency must therefore be measured separately in practice.
Pass only when no current-mode route returns the source or its derivatives, caches are invalidated, and compaction eventually reclaims the expected storage. If historical recovery is intentional, isolate it behind separate authorization and make it unavailable to ordinary RAG queries.
Recommended products
Tech & AI HUB
More to Read
Multilingual Embeddings: How One Vector Space Connects Household Documents Across Languages
See how aligned embeddings connect documents across languages, why retrieval quality varies, and how to test cross-language evidence coverage locally.
Agent Memory Conflicts: Why Recent Corrections Can Lose to Repeated Older Facts
Learn how duplicate old memories overpower corrections, where recency rules fail, and how to test supersession in a private agent memory store.
Private Search Reranking: How a Second Model Changes the Final Evidence Order
See why first-stage similarity and second-stage relevance disagree, when reranking helps private RAG, and how to evaluate reordered evidence.
