PaperlayerView exact revision on arXiv

Source-linked AI summary

Ghost Echoes: Semantic Erasure Failure in Retrieval-Backed Applications

Allan Mukkuzhi, Noella Uwayisenga, Yeabsira Bizualem, Jacob Kammerzell, Chandranil Chakraborttii

arXiv:2608.20352v1cs.DBcs.CRcs.DC

TL;DR

Retrieval-backed systems may satisfy API-visible deletion while retaining semantic influence from deleted records in their retrieved evidence. Ghost Echoes uses black-box API attacks and same-cluster controls to measure this gap, finding substantial target-specific retrieval drift that remains detectable under the evaluated settings.

  • Problem

    API-visible identifier exclusion does not establish semantic erasure for retrieval-backed applications, where downstream behavior depends on the retrieved evidence base.

  • Method

    Ghost Echoes uses black-box API queries, same-cluster non-target deletion controls, and retrieval-context metrics to compare post-delete behavior with the never-inserted counterfactual.

  • Results

    0.1522 median retrieval-centroid drift followed target deletion on ChromaDB, exceeding the same-cluster baseline in 53/54 paired comparisons (p < 0.001), with 61.1% detection at q = 5.

  • Takeaways & Limitations

    The Verification Gap shows that deletion guarantees must address residual retrieval influence and topology, not only stored identifiers.

  • Takeaways & Limitations

    Under the evaluated cloud settings, closing the erasure gap cannot be achieved using standard tenant-level write operations and remains a provider-level responsibility.

Abstract

from arXiv · show

Although vector databases correctly implement API-visible deletion, this does not guarantee complete semantic erasure for retrieval-backed applications. We present Ghost Echoes, a black-box attack framework showing that deleted records can leave measurable residual influence on downstream retrieval contexts. Our primary finding is the RAG retrieval-context drift effect where even when a target record is correctly excluded from query results, its prior presence perturbs the semantic centroid and textual composition of the Top-K evidence base. We approximate the unobservable never-inserted counterfactual using a same-cluster non-target deletion control that preserves local neighborhood structure while isolating target-specific effects from generic local drift. Evaluation on ChromaDB confirms target deletion produces a median retrieval-centroid drift of 0.1522, exceeding the same-cluster baseline in 53/54 paired comparisons (p < 0.001), and the signal remains detectable with 61.1% accuracy at a query budget of q = 5. We verify API-visible deletion correctness across evaluated backends and observe the same qualitative drift ordering in matched FAISS replication. Under the evaluated settings, tested operational mitigations such as full index rebuilds fail to eliminate the measured drift. These results establish a measurable 'verification gap' between interface-level deletion compliance and true semantic erasure, and motivate erasure primitives that act not only on stored identifiers, but also on the retrieval topology of the system.

1 Introduction

Ghost Echoes shows that API-confirmed deletion can leave measurable semantic influence on retrieval-backed applications. The framework detects this Verification Gap through changes in the retrieved evidence context, even when deleted identifiers are excluded.

  • Core contribution: Ghost Echoes defines a Verification Gap between logical deletion and true semantic erasure.A deleted record may remain detectable through how its absence reshapes retrieved context.
  • Threat model: The framework targets a black-box API-only adversary without storage access, index inspection, or white-box model knowledge.It tests whether correct identifier exclusion also removes structural influence from retrieval.
  • Primary findings: 0.1522 median retrieval-centroid drift followed target deletion in the primary ChromaDB evaluation at K = 5.The 95% confidence interval was [0.1415, 0.1629].
  • Primary findings: 53/54 paired trials showed greater drift after target deletion than after same-cluster non-target deletion (p < 0.001).The same-cluster comparison isolates target-specific effects from generic local movement.
  • Detection: 61.1% detection accuracy remained achievable with a query budget of q = 5 target-relevant queries.The same qualitative drift pattern was also observed in matched FAISS replication.
  • Mitigation: Tested tenant-visible mitigations, including local rebuilds and overwrite procedures, did not eliminate retrieval-context drift under the evaluated settings.The paper therefore motivates erasure mechanisms that address retrieval topology rather than stored identifiers alone.

2 Threat Model

The threat model considers an API-only adversary probing a managed vector database before and after a known deletion. The goal is to determine whether identifier exclusion also removes residual semantic influence from retrieval.

  • Access model: Managed-cloud users can test deletion through the same structured query and standard APIs exposed to tenants.They need not access storage, index files, or backend internals.
  • Attacker capabilities: The Tier 2 attacker submits targeted queries designed to land in a specific record’s semantic neighborhood.The attacker observes retrieval outputs before and after an API deletion event.
  • Attacker capabilities: The attacker does not need the exact target vector, because query induction uses API-visible rank signals and returned results.The attacker also does not attempt to recover the deleted content or identify the exact document.
  • Attacker goal: The evaluation measures target exclusion, retrieval-context drift, and downstream vocabulary shift in the Top-K evidence base.The broader metric set also includes Vanish Token residue, Hallucination Adoption Potential, and differential query latency.

3 Background

RAG applications depend on retrieved Top-K context, so API-level identifier deletion is weaker than semantic erasure. In HNSW, insertion-time graph changes can persist as a ghost neighborhood after logical deletion.

  • RAG background: RAG combines a parametric language model with non-parametric retrieval over an external corpus to ground generated outputs.The pipeline embeds a query, retrieves the Top-K documents, and supplies them as the evidence base.
  • Deletion semantics: API-visible deletion correctness removes a deleted identifier from subsequent results but does not itself establish true semantic erasure.Semantic erasure requires post-delete retrieval to match the never-inserted counterfactual.
  • Deletion semantics: Semantic erasure requires post-delete retrieval behavior to be statistically indistinguishable from the never-inserted retrieval distribution.The criterion applies to relevant query classes and includes search accuracy, neighborhood relevance, and retrieved semantic context.
  • HNSW background: HNSW insertion changes local neighbor lists and path-routing structure, which logical deletion generally does not restore to the never-inserted state.This topology mismatch is the architectural basis of the semantic erasure problem.
  • HNSW background: A ghost neighborhood is the residual post-delete structure that leaves the neighborhood different from the counterfactual neighborhood.Figure 1 maps the path-routing distortion between pre-deletion retrieval and post-deletion ghost paths.

4 Methodology

The methodology combines synthetic clustered records, API-only query induction, same-cluster controls, and geometric and textual retrieval metrics. It compares target deletion against structured controls to isolate target-specific drift.

  • Data and setup: The study uses synthetic privacy-sensitive person records, with N = 500 for the primary evaluation and N = 5,000 for scale evaluation.Synthetic records avoid exposing real personally identifiable information.
  • Data and setup: Records are embedded into 384-dimensional vectors, partitioned into ten semantic clusters, and sampled across dense, medium, and sparse regimes.The design selects 18 target documents, with six targets per density band.
  • Controls: Same-cluster non-target controls are sampled outside the original Top-K within a matched local proximity band.This preserves local neighborhood structure while isolating target-specific effects from generic cluster movement.
  • Metrics: Centroid drift is the Euclidean distance between the pre- and post-deletion centroids of the Top-K retrieved embedding sets.Under semantic erasure, it should be statistically indistinguishable from background drift.
  • Metrics: Vocabulary shift is the Jaccard distance between token sets from concatenated Top-K documents before and after deletion.Because it uses returned text, the metric requires neither internal model access nor storage access.
  • Query induction: Warm-start aggregation and NES induce target-relevant queries using only API-visible rank signals.The NES configuration uses population size m = 10, perturbation scale σ = 0.05, and at most 20 iterations.
  • Controls and analysis: Target-delete drift is compared separately with no-delete, unrelated-delete, and same-cluster non-target-delete controls.The analysis uses 54 paired observations per condition, medians with 95% bootstrap intervals, and a two-sided Wilcoxon signed-rank test.

5 API-Visible Deletion Verification

The study verifies identifier-level deletion before attributing later retrieval drift to semantic-erasure failure. Across evaluated backends, deleted IDs were consistently excluded from post-delete results.

  • The protocol verifies target rank-1 retrieval, issues standard delete-by-ID calls, and checks absence from post-delete Top-40 results.
  • 100% exclusion was achieved across 270 verification trials, with no deleted identifier returned post-delete.
  • Because identifier-level deletion was confirmed, the reported retrieval drift is limited to the evaluated setting rather than attributed to caching, propagation, or implementation errors.

6 Main Results

In the primary ChromaDB evaluation, target deletion measurably shifts retrieval contexts beyond same-cluster controls, changing both geometric and textual evidence composition. The signal persists across query volumes, K values, semantic-density regimes, and matched FAISS replication, while exploratory tests identify downstream and operational effects.

  • 6.1 Primary Findings: ∆centroid = 0.1522 [0.1415, 0.1629], 3.7× larger than the same-cluster baseline of 0.0412 [0.0321, 0.0503].Across 54 paired observations, 53 target-delete trials exceeded their same-cluster controls (p < 0.001).
  • 6.1 Primary Findings: ∆vocab = 0.285 after target deletion, compared with 0.095 for the same-cluster baseline.Unrelated-delete and no-delete conditions remained at zero, showing that the Top-5 evidence base changed textually after deletion.
  • 6.2 Secondary Findings: Detection reaches 61.1% at q = 5, with target-delete drift exceeding the same-cluster baseline across dense, medium, and sparse regimes.The ordering persists for K ∈{1, 3, 5, 10, 20}, although the gap narrows as K increases.
  • 6.2 Secondary Findings: Matched FAISS replication preserves the qualitative ordering in which target deletion exceeds same-cluster drift while unrelated-delete and no-delete controls remain negligible.ChromaDB remains the paper’s most complete quantitative characterization.
  • 6.2 Secondary Findings: Passive rank disruption is negligible at N = 500 but becomes detectable at larger corpus sizes with a mean Jaccard shift of 0.18.Active probing detects the effect at small scale, whereas passive observation requires significantly more data.
  • 6.3 Exploratory Findings: Exploratory evaluations observed 59.6% HAP, 91.82% high-confidence incorrect instructions, +15.69 ms latency, and 74% utility collapse after six hub deletions.These findings span downstream textual effects, latency, and coordinated deletion stress tests.

7 Mitigation Analysis

The evaluation finds that tested operational mitigations do not remove retrieval-context drift, while effective erasure requires interventions on retrieval topology rather than stored coordinates or identifiers.

  • Baseline persistence: Natural index growth amplifies structural residue instead of repairing it, and neighborhood search utility falls from 1.00 to 0.00 NDCG.The evaluation inserts 2,500 nearby records after deletion and observes distorted routing paths inherited by arriving nodes.
  • M1: Full Index Rebuild: A full index rebuild restores a graph for surviving documents but cannot recreate the counterfactual layout that would have existed without target insertion.
  • M2: Lightweight Perturbation: Lightweight embedding perturbation is evaluated as a way to break immediate graph connections while tracking residual drift against RAG utility.The perturbation uses isotropic Gaussian noise across ϵ ∈[0.001, 0.10] and evaluates utility with NDCG@5.
  • Structural limitation: Proximity-graph edges preserve insertion-time routing decisions, so tenant-level vector modification, maintenance, and deletion calls do not repair the neighbor lists.
  • Defense direction: True semantic erasure therefore requires explicit topology repair or architectural reconstruction rather than coordinate-level modification alone.

8 Related Work

Related work establishes the importance of retrieval context, graph structure, and model unlearning, but does not address semantic erasure in non-parametric retrieval under black-box API constraints. Ghost Echoes targets this gap by jointly checking API deletion and post-deletion context drift.

  • RAG context: RAG behavior depends on the composition of retrieved evidence, making Top-K context a stronger deletion-verification target than identifier exclusion alone.
  • Graph indexing: Prior HNSW research explains insertion-driven neighborhood changes and connectivity-dependent search quality without treating true semantic erasure as a prerequisite.
  • Machine unlearning: Machine unlearning targets parametric model weights, whereas Ghost Echoes studies non-parametric retrieval behavior shaped by graph edge configurations.
  • Related privacy attacks: Membership inference and embedding inversion show that black-box outputs or dense embeddings can reveal information, but address different exposure questions.
  • Positioning: The paper claims to be the first to combine cross-backend API-deletion verification with statistically stable, query-efficient measurement of post-delete retrieval-context drift.

9 Discussion

The discussion frames the observed behavior as a semantic-layer consequence of correct logical deletion in proximity-graph indices, while limiting direct drift quantification to the evaluated systems and API-only setting.

  • Interpretation: Vendor feedback characterizes the observed behavior as a semantic-layer consequence of correct logical deletion rather than an implementation bug.
  • Study setting: The experiments use publicly available or synthetic datasets and require only black-box API access, avoiding exposure of sensitive user records.
  • Verification boundary: The evaluated architectures can pass identifier-level deletion audits while retaining measurable structural influence and vocabulary voids in surrounding topology.
  • Scope: Direct drift quantification on additional systems remains outside the current evaluation scope beyond the primary ChromaDB study, matched FAISS replication, and four-backend cloud audit.

10 Conclusion

The conclusion shows that API-correct identifier exclusion does not ensure semantic erasure: deletion shifts retrieved context despite excluding the target, and the measured gap persists across evaluated mitigations.

  • Core conclusion: API-correct identifier exclusion does not constitute semantic erasure in vector database retrieval.
  • Retrieval-context drift: Deleting a target shifts the Top-K semantic centroid and textual composition even when the target is absent from every returned result.
  • Evidence: The drift exceeds the same-cluster baseline at p < 0.001, remains detectable with q = 5 target-relevant queries, and is not eliminated by evaluated mitigation families.
  • Concept: The Verification Gap names the divergence between interface-level API compliance and true semantic erasure.
  • Implication: Closing the gap requires erasure primitives that operate on retrieval topology rather than only on identifiers or storage footprints.
Loading 2608.20352v1…