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.
Figures & tables
Figure 1: Returned vs. visited leakage. A deleted memory entry d is filtered from the returned top- k under both regimes, so an output-level audit sees zero leakage in each. Left: soft-delete still visits and scores d (dashed red), so the retrieval process reads erased data on nearly every query—invisible to an output audit. Right: the alive -before-scoring invariant never admits d to the candidate pool and an offline repair edge restores connectivity, driving visited leakage to zero and yielding an externally checkable certificate.
Condition
ndis (targeted)
returned leak
verifier
A. soft-delete (output filter)
1,535,152
0
FAIL
B. native IDSelectorBatch
1,535,152
0
FAIL
C. clean rebuild (live only)
2,124,533
0
PASS
Traversal-safe (ours)
—
0
PASS
Table 1: External-validity audit on unmodified faiss (70% deletion, 3 seeds). The native selector leaves distance work unchanged; the released verifier fails soft-delete and passes the traversal-safe and rebuild certificates. Take-away: output filtering does not stop the memory from reading deleted entries.