Beyond Private Training: The New Landscape of AI Privacy
TSD-AUDIT reveals graph-based vector indexes like Faiss HNSW still score deleted embeddings during search, exposing process-level privacy leaks beyond output-filtering audits.
The paper formalizes output safety versus traversal safety in graph-based approximate nearest-neighbor retrieval, where deleted identifiers are filtered from results but their embeddings still get scored during graph traversal. On Faiss IndexHNSWFlat, native filtering leaves distance computations unchanged, and trace-faithful replay detected deleted-vector scoring in all 100 audited queries at a 70% deletion rate; hnswlib's mark_deleted path shows the same scoring-before-liveness pattern. TSD-AUDIT enforces an alive-before-scoring invariant, repairs connectivity using live candidates, and emits per-query scored-trace certificates, improving Recall@10 by 4.3 to 42.2 percentage points under region-targeted deletion.
- Distinguishes output safety from traversal safety in graph-based approximate nearest-neighbor retrieval.
- Trace-faithful replay detected deleted-vector scoring in all 100 audited Faiss queries.
- hnswlib's mark_deleted path exhibits the same scoring-before-liveness pattern.
- TSD-AUDIT enforces alive-before-scoring and emits independently verifiable scored-trace certificates.
- Recall@10 improves 4.3-42.2 points over native filtering under region-targeted deletion.
Full article187 words · extracted from arxiv.org · click to collapse
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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.19456