diskann: delete() can return deleted ids, injects NaN into result ordering, and degrades recall — tombstone filter + local graph repair

[ohdearquant]

Summary

delete() fills the vector with NaN and removes the id from id_reverse, but leaves the graph adjacency and the id_map entry untouched (index.rs:207-216, distance.rs:46-51). Three concrete consequences, all verified at main c55e9e89:

1. Deleted ids can still be returned by search. search() re-ranks through self.id_map[id as usize] (index.rs:196), which still holds the deleted id. Nothing in the search path consults id_reverse or any tombstone set.
2. NaN distances make result ordering arbitrary. Every distance against a deleted point is NaN, and both the beam search and the re-rank sort use partial_cmp(...).unwrap_or(Ordering::Equal) (index.rs:190, graph.rs), so NaN entries compare Equal to everything and land at arbitrary positions, including inside the top-k.
3. Recall decays as deletes accumulate. Edges into and out of deleted nodes are never repaired, so points whose graph paths ran through deleted nodes become hard or impossible to reach. Long-lived mutating deployments (exactly the browser/edge sessions targeted by @ruvector/diskann-wasm: browser/edge DiskANN via PQ-guided traversal + on-demand vector fetch #676) degrade monotonically with no recovery short of a full rebuild.

Suggested fix, in two independent stages

Stage 1 (correctness, small): keep a tombstone bitset. Beam search may still traverse tombstoned nodes (as routing waypoints) but must never emit them: filter tombstones from the candidate list before re-rank, and skip NaN by construction (distance against tombstoned nodes is only needed for routing, and with a bitset you can keep the original vector data instead of NaN-filling, which also removes the NaN-ordering hazard entirely). Deleted ids never appear in results; ordering stays total.

Stage 2 (quality, medium): local repair on delete. For each in-neighbor u of a deleted node d, splice d's out-neighbors into u's candidate set and robust_prune(u, neighbors(u) + neighbors(d) \ {d}, alpha). This is O(in-degree x degree) per delete, preserves graph connectivity, and avoids any rebuild. The crate already has robust_prune; the only new requirement is an in-neighbor lookup (either a reverse adjacency list or a bounded scan). We ship this two-hop repair in khive's vamana crate (ohdearquant/khive, crates/khive-vamana), along with a batch tombstone-only escape hatch for callers that prefer deferred repair, and can port both as a PR.

Measurable impact / acceptance

• After deleting any id, a search for its exact vector never returns the deleted id (today it can).
• With vector data preserved and tombstones filtered, no NaN ever enters a distance computation; sorts are total.
• Recall@10 after deleting a random 20% of a 100k index stays within 1-2 points of a fresh build over the surviving 80% (with stage 2 repair); tombstone-only (stage 1) documents its measured degradation instead of corrupting silently.
• count() and persisted state reflect deletions consistently.