Executive Summary

Key Numbers

Deletion worked flawlessly, and the search results changed anyway.

Source: Mukkuzhi et al., arXiv:2608.20352

The paper opens in a hospital. A patient named Alice has an insulin prescription sitting inside a RAG system, and Alice invokes her right to erasure under GDPR Article 17. The operator sends a deletion request to the vector database and the API confirms completion within milliseconds. From every observable standpoint, the deletion looks complete. Yet a third party using the same query interface can tell that Alice's record was there, without ever retrieving it. The method is to watch how its absence reshapes what the system retrieves in its place.

The cause sits in the data structure vector databases use to make search fast. Most of them today rely on a proximity-graph index called HNSW. Every time a document is inserted, the nodes it will treat as neighbors get fixed, and those links become the traversal path for every query that follows. Deletion is usually closer to attaching a marker that says this node is gone. The node drops out of the results, but the neighbor links that were drawn when it arrived, and the older paths those links pushed aside, stay where they are. The authors call what remains a topological crater left behind by the deleted node.

The authors give this mismatch between logical deletion and true semantic erasure a name: the Verification Gap. If an audit of deletion compliance stops at the identifier level, a state becomes possible in which the audit passes while a trace remains in the retrieval topology. The authors write: "The user was told the data is gone, but the system is still shaped by it."

The adversary they assume is a narrow one. No storage access, no index file inspection, no view inside the model, just the same query API every other user has. The goal is not document recovery either. Issuing the same query before and after deletion and comparing the returned document lists, scores, and text is the whole of it. That setting matters because most organizations running a managed cloud vector database can see exactly that much and no more. The window available to the operator and the window available to an outsider are the same window.

Proving a claim like this needs a point of comparison. The ideal one is the index as it would look had the document never been inserted at all, a world no deployed system lets you observe. So the authors set up a stand-in: deleting a non-target neighbor from the same cluster. Same query, same target identity, same surrounding neighborhood structure, with only the record being removed swapped out. Whatever rises above that line is the trace specific to the target document.

There are three controls. One deletes nothing and measures the index's own noise. One deletes an unrelated record from a distant cluster. The third, the strict baseline, deletes a neighbor inside the same cluster. That third one is the demanding comparison because it separates movement caused by the cluster shifting as a whole from movement caused by one specific document. If removing any neighbor already moves things that far, only the excess above it belongs to the target.

The corpus is 500 short paragraph-length records that resemble personal data. These are not real patient records but synthetic data the researchers generated, built from unique alias tokens instead of names, categorical medical markers, and demographic attribute phrases, to approximate the structure of a health-repository document. Each record becomes a 384-dimensional embedding, the space is partitioned into ten semantic clusters, and six targets are drawn from each of the dense, medium, and sparse density bands for 18 deletion targets in total. Multiply that by three random seeds controlling index construction order and you get 54 paired comparisons. Every figure that follows comes from these 54 pairs.

Before measuring anything, the authors checked that deletion itself works. Across 270 trials spanning 18 targets, five backends, and three seeds, they first confirmed that the target document ranked first for its induced query, deleted it through the standard API, re-issued the same query, and checked that the identifier was absent from the top 40 results. Cloud backends got synchronization waits to account for asynchronous propagation. All 270 trials came back at 100% exclusion. This is the groundwork that makes it impossible to write off the drift values that follow as an implementation bug or a caching artifact.

Nor was the verification procedure itself a loose one. Rather than trusting the HTTP status code the deletion API returns, the authors parsed the raw vendor payload directly to confirm the identifier was excluded. They also anchored reference vectors in a separate store to reduce floating-point variance when comparing coordinates. The bar the paper sets for erasure is correspondingly strict. It is not enough that the deleted record fails to come back. Erasure counts as confirmed only when the search accuracy, neighborhood relevance, and retrieved semantic context for innocent users issuing non-target queries are indistinguishable from the counterfactual baseline in which the document was never inserted.

Two things get measured. One is centroid drift. Average the embeddings of the top five documents returned for a query and you get a single coordinate for the meaning that query landed on. The distance between that coordinate before deletion and after it is the centroid drift. The other is vocabulary shift. Concatenate the body text of the five returned documents into a token set and measure how much the two sets fail to overlap. The second value needs nothing but the returned text, so it requires no internal access whatsoever.

When one document drops out, a sixth document fills the slot. The remaining four stay put while the newcomer pulls on the average of the five.

The table below holds the ChromaDB results at a retrieval depth of five. Deleting the target moved the centroid by 0.1522, with a 95% confidence interval of 0.1415 to 0.1629. Deleting a neighbor in the same cluster reached only 0.0412. Deleting an unrelated distant document and deleting nothing at all both came in at exactly zero. Vocabulary shift traces the same ordering: 0.285 for target deletion, 0.095 for neighbor deletion, zero for the other two. Four of the five returned documents can be unchanged and the text composition still differs noticeably.

In the paper's own worked example, the token pool gathered from the pre-deletion top results held insulin and dosage; once the target dropped out and a replacement moved in, generic clinical vocabulary such as glucose and monitoring filled the space. The two pools share five tokens across a nine-token union, so the vocabulary shift in this example is 0.44. Back in the Alice scenario, that is a specific clue about an insulin prescription giving way to ordinary diabetes phrasing. The authors note that these target-proximal evidence tokens evaporate into generic clinical distractors without requiring raw coordinate extraction. Counting the text that comes back is all it takes.

More striking than the median is the consistency. In 53 of the 54 paired comparisons, target deletion exceeded the matched same-cluster deletion. The two-sided Wilcoxon signed-rank p-value is below 0.001. The ordering did not flip in dense clusters or sparse ones, and it held when retrieval depth was varied from 1 to 20. The gap narrows as depth grows, which is the expected direction, since one deleted document contributes less to a larger average. A separate FAISS replication showed the same ordering. Only one backend, ChromaDB, has been quantitatively characterized end to end.

3.1Five Queries Are Enough to Read It

A large measurement and a noticeable one are different things. The authors shrank the query budget step by step to measure detection accuracy, and five target-relevant queries produced 61.1%. The curve is already flattening around that point. Adding queries does not help much, which read the other way means the signal is large enough that no high-volume querying is needed to pick it up.

Those five, though, are the detection stage alone. Before them comes a separate process of constructing a query that lands precisely in the target's semantic neighborhood. The authors issued probe queries near that neighborhood to gather rank signals, then perturbed a population of ten candidates and refined the query toward maximizing the target's rank, for at most twenty iterations. This stage also runs on nothing but the ranks and results the API hands back, so internal access is still unnecessary, but it is not a matter of throwing five arbitrary queries at the system.

These are not the only channels the signal leaks through. The authors classify the other two as exploratory observations. Purely passive observation, watching rank changes without inducing queries, stayed negligible at the 500-record scale, but at 5,000 records it surfaced as a mean vocabulary shift of 0.18. Pooled across the cloud backends, traversals that hit the structural residue of a deleted node also showed a response-time increase of 15.69 milliseconds.

The vanished vocabulary has a slightly different property. Collecting the tokens that were present in the pre-deletion results and gone from the post-deletion ones, the authors found that these sets overlapped by less than 3% across different target documents. The observation is that without reconstructing what the deleted document said, the residue can act as a fingerprint distinguishing which document was removed. This is the point to be clear about the paper's scope. What is established here is retrieval-context drift, not plaintext reconstruction or vector recovery. Ghost Vectors, an earlier paper from the same lab, dealt with embeddings physically surviving on disk; this study deals with the topology that survives after those embeddings are genuinely gone. Storage and retrieval are different layers.

Any operator will reach for a few obvious responses. Rebuild the index from scratch, add a little noise to the vector before deleting it, run the vendor's maintenance routines, or overwrite the vector with an entirely different value before deleting it. The authors tested all four in turn, and none of them eliminated the measured drift.

The most decisive-looking option, a full rebuild, does nothing at all. It produces a structurally correct graph for the surviving documents, but it cannot restore the counterfactual index layout that would have existed had the target never been inserted. The neighbor relationships fixed at the moment of insertion are already baked into the coordinates and links of other nodes long before the deletion. Vendor maintenance fails for the same reason. Those routines function as storage hygiene, not as erasure primitives, as the authors put it.

Perturbation offered no setting where privacy and retrieval quality both hold. With small noise the drift barely moves; with larger noise the drift falls to 0.1089 while retrieval quality degrades sharply. Overwrite-then-delete came out pointing the wrong way entirely. Overwriting changes the stored coordinates but cannot remove the neighbor lists and entry-point slots written at insertion, and the deletion that follows propagates a larger disturbance than an unmitigated deletion would have.

Time does not resolve it either. When the authors inserted 2,500 new documents near the deleted target's neighborhood and let the index grow, the trace deepened rather than faded. The arriving nodes inherited the already distorted paths and aligned themselves around the crater. Search utility for the original neighborhood collapsed from 1.00 to 0.00. A boundary case involving abuse of deletion rights was reported alongside it. Deleting six high-degree hub nodes within a single cluster dropped search utility by 74%, down to 0.26, for innocent users querying that neighborhood.

All four failures point at one cause. Proximity-graph indices write insertion-time routing decisions directly into their edge structure, and that structure persists no matter what happens to the coordinates or the identifier afterward. This is not a bug in any particular product. The authors ran responsible disclosure with the evaluated vendors in early 2026, and the vendors replied that the observed behavior is a semantic-layer consequence of correct logical deletion in proximity-graph indices rather than a defect in their current implementations. For an organization on a cloud service, that puts the gap outside the reach of tenant-side writes and squarely in provider territory.

The two directions the authors propose are both future work. An index topology erasure primitive would log the neighbor lists and entry-point slots at insertion time and replay that layout during deletion to restore the prior routing. They report cutting drift from 0.1522 to 0.0012, a 99.21% reduction, in a controlled local evaluation, though it cannot be implemented inside the black-box boundary of current cloud APIs. The remaining approach divides the index lifecycle into epochs, encrypts coordinates with a per-epoch key, and destroys the key on deletion. That approach does not repair the distortion in the graph; it makes the content of the surviving coordinates unreadable.

Regulations such as GDPR Article 17 and HIPAA prescribe deletion workflows, but validation typically stops at the API level. Request sent, response received, record no longer retrievable: those three make the evidence. What this paper shows is that all three can be true while a measurable trace remains in the retrieval topology. The authors close with this: "In retrieval-backed systems, the right-to-erasure question is not whether a record can be hidden, but whether its influence on retrieval can be removed."

They also set their work beside machine unlearning. Research on removing specific data from model weights generally starts by assuming direct write access to the model state. A tenant on a managed vector database has no such access to the graph topology. Interface-level verification is therefore a weaker guarantee than what stronger erasure-oriented interpretations of the right to deletion require, as the authors write. The weight carried by the word deleted turns out to differ from layer to layer for the very same document.

Two things carry over into practice: the scope of deletion evidence, and the language used in contracts and customer notices. If today's evidence covers identifier exclusion and nothing further, the documentation should say what that guarantees and what it leaves open. When the layer a provider means by deleted differs from the layer a user hears, even a technically flawless deletion becomes hard to explain later.

The paper's limits belong in the same frame. ChromaDB is the only backend with complete quantitative characterization, and FAISS goes as far as confirming the same tendency. Pinecone, Weaviate, and Milvus were used for deletion-correctness verification and some mitigation experiments rather than drift quantification. The corpus is synthetic data at 500 and 5,000 records, unlike the size or diversity of a production corpus. How much retrieval-context drift actually changes an LLM's answers is left as a separate question that depends on the model and the deployment. An exploratory evaluation on a small model in a deterministic setting put the risk of a final answer adopting the context that filled the vacated slot at 59.6%, with the resulting incorrect patient instructions generated at 91.82% confidence. The authors themselves classify these as exploratory observations rather than primary results.

The paper is available at arXiv:2608.20352.

References

Academic Papers

• 1.Mukkuzhi, A., Uwayisenga, N., Bizualem, Y., Kammerzell, J., & Chakraborttii, C. (2026). "Ghost Echoes: Semantic Erasure Failure in Retrieval-Backed Applications." arXiv:2608.20352.
• 2.Chakraborttii, C., Alvarado, J.G., Abdulofizova, S., & Dwivedi, S. (2026). "Ghost Vectors: Soft-Deleted Embeddings Remain Reconstructible in HNSW Vector Databases." arXiv:2606.18497.
• 3.Lewis, P. et al. (2020). "Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks." NeurIPS 2020.
• 4.Malkov, Y.A., & Yashunin, D.A. (2020). "Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs." IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4).

Official Documents

• 5.European Union (2016). "Regulation (EU) 2016/679, Article 17 — Right to Erasure ('Right to be Forgotten')."