mlsanityData to 14 Oct 2026

Beyond Private Training: The New Landscape of AI Privacy

arXiv 2609.19456 ↗First posted 16 Sep 2026cs.CR cs.AI cs.IRcited by 0

On the map: Retrieval-augmented generation → Privacy and security of RAG

Abstract (arXiv)

Retrieval-augmented systems increasingly rely on vector indexes that may retain deleted items in their search graph. Existing deletion interfaces can prevent deleted identifiers from appearing in returned results while still computing distances to their embeddings during graph traversal. We formalize this distinction as output safety versus traversal safety, and introduce TSD-AUDIT, a framework for auditing and enforcing traversal-safe deletion in graph-based approximate nearest-neighbor retrieval. On Faiss IndexHNSWFlat, native filtering leaves the number of distance computations unchanged relative to unfiltered search; at a 70% deletion rate, trace-faithful replay detects deleted-vector scoring in all 100 audited queries. Code inspection of hnswlib's mark_deleted path reveals the same scoring-before-liveness pattern. TSD-AUDIT enforces an alive-before-scoring invariant, repairs connectivity using only live candidates, and emits per-query scored-trace certificates that an independent verifier can check against the deletion snapshot. Under region-targeted deletion, TSD-AUDIT improves Recall@10 over native filtering by 4.3--42.2 percentage points across deletion fractions from 0.5 to 0.9, while remaining comparable under random deletion. These results show that output-only deletion audits can miss process-level exposure: auditing deletion in vector retrieval requires accounting for the vectors scored during search, not only the identifiers returned.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Privacy and security of RAG, one of 15 directions in Retrieval-augmented generation. Builds on 10 of its 13 references that are in the map. First posted on arXiv 16 Sep 2026.

Builds on

10 of 13 references.

Closest ancestors · 1

Same direction, newest first

  1. 2026Ghost Vectors: Soft-Deleted Embeddings Remain Reconstructible in HNSW Vector Databases16 Jun

Other references · 9

  1. 2019Machine Unlearningcited by 1,061
  2. 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 861
  3. 2021FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Searchcited by 38
  4. 2024ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Datacited by 32
  5. 2024Results of the Big ANN: NeurIPS'23 competitioncited by 22
  6. 2024Enhancing HNSW Index for Real-Time Updates: Addressing Unreachable Points and Performance Degradationcited by 8
  7. 2025In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Searchcited by 4
  8. 2026Auditing Forgetting in Limited Memory Language Modelscited by 2
  9. 2025How Should We Evaluate Data Deletion in Graph-Based ANN Indexes?cited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Ghost Echoes: Semantic Erasure Failure in Retrieval-Backed Applications ↗
  2. 2026MERIT: Efficient In-Place Deletion for Dynamic Graph-Based Approximate Nearest Neighbor Indexes
  3. 2026Mind the Hook: Source-Level Auditing of Privacy Defenses in Retrieval-Augmented Generation
  4. 2026Graphs Don't Stay Secret: Practical Subgraph Reconstruction Attacks on Defended Graph RAG
  5. 2026V3DB: Audit-on-Demand Zero-Knowledge Proofs for Verifiable Vector Search over Committed Snapshots
  6. 2025Graph-based Nearest Neighbors with Dynamic Updates via Random Walks
  7. 2026Coverage Is Not Containment: A Fundamental Limit of Admission-Time Defenses Against Coordinated Poisoning of Vector Retrieval
  8. 2025Exploiting Instruction-Following Retrievers for Malicious Information Retrieval