# Beyond Private Training: The New Landscape of AI Privacy

arXiv: https://arxiv.org/abs/2609.19456 · HTML: https://mlsanity.com/paper/2609.19456/

## 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.

## Placed in

- Retrieval-augmented generation / [Privacy and security of RAG](https://mlsanity.com/rag/privacy-and-security-of-rag/)

## Builds on (most cited first, 10 of 10)

- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search](https://mlsanity.com/paper/2105.09613/) (2021)
- [ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data](https://mlsanity.com/paper/2403.04871/) (2024)
- [Results of the Big ANN: NeurIPS'23 competition](https://mlsanity.com/paper/2409.17424/) (2024)
- [Enhancing HNSW Index for Real-Time Updates: Addressing Unreachable Points and Performance Degradation](https://mlsanity.com/paper/2407.07871/) (2024)
- [In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2502.13826/) (2025)
- [Auditing Forgetting in Limited Memory Language Models](https://mlsanity.com/paper/2607.00605/) (2026)
- [How Should We Evaluate Data Deletion in Graph-Based ANN Indexes?](https://mlsanity.com/paper/2512.06200/) (2025)
- [Ghost Vectors: Soft-Deleted Embeddings Remain Reconstructible in HNSW Vector Databases](https://mlsanity.com/paper/2606.18497/) (2026)

## 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.