TSD-Audit: Traversal-Safe Deletion in RAG Vector Memory

Retrieval-augmented systems increasingly store sensitive data in vector indexes queried at inference time. Yet deleting an item from returned results does not imply that the search process stops accessing its embedding. We introduce TSD-Audit, a process-level framework for auditing and enforcing traversal-safe deletion in approximate nearest-neighbour retrieval. TSD-Audit distinguishes output safety, which excludes deleted identifiers from the top-$k$ results, from traversal safety, which additionally excludes deleted vectors from query-vector distance computations. Ghost Vectors established that soft-deleted HNSW nodes remain in the graph and are recoverable at rest; we show the gap survives the interface a compliant operator must use. Under Faiss's own IDSelectorBatch on the default IndexHNSWFlat path, hnsw_stats.ndis is bit-identical to unfiltered search, and at a $70\%$ deletion rate trace-faithful replay detects deleted-vector scoring in $100$ out of $100$ audited queries; hnswlib's mark_deleted path has the same structure, so this is a property of graph-ANN deletion design, not of one library. TSD-Audit closes the gap by enforcing an alive-before-scoring invariant, repairing connectivity using only live candidates, and emitting scored-trace certificates checkable against the deletion snapshot by an independent verifier. Under targeted deletion TSD-Audit improves Recall@10 over native filtering by $4.3$ to $42.2$ percentage points across deletion fractions of $0.5$ to $0.9$, and is comparable under random deletion. Output-only audits can miss process-level exposure: the scored set must itself become deletion evidence.