ruvector-delta-index: delete() of the entry point leaves search anchored to a phantom node — the rest of the graph becomes unreachable
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 4.5k
- Forks
- 603
- Avg merge
- 23h 32m
- Merged PRs (30d)
- 59
Description
Defect
DeltaHnsw::delete() (crates/ruvector-delta-index/src/lib.rs) blanks the node (id = String::new(), clears vector and neighbors) and removes it from every other node's neighbor list — but never touches entry_point. If the deleted node is the entry point, every subsequent search starts from a node whose id is empty, whose distance is defined as f32::MAX, and whose neighbor lists are empty.
Verified failure (probe run on the post-#825 code)
let mut index = DeltaHnsw::new(4, DeltaHnswConfig::default());
index.insert("a", vec[1.0, 0.0, 0.0, 0.0]).unwrap();
index.insert("b", vec[0.0, 1.0, 0.0, 0.0]).unwrap();
index.delete("a").unwrap(); // "a" is the entry point
let results = index.search(&[1.0, 0.0, 0.0, 0.0], 2).unwrap();
Observed output:
result: id="" dist=340282350000000000000000000000000000000
Two distinct consequences, both worse than a stale row:
- Phantom results. The deleted node is returned as a
SearchResultwith an empty id andf32::MAXdistance —search_layerunconditionally seeds its result heap with the start node. - Total recall loss. Because
delete()cleared the deleted node's own neighbor lists, the entry point now has no outgoing edges.greedy_search/search_layercannot leave it, so every live vector in the index becomes unreachable. In the probe, "b" is simply gone: the search returns only the phantom.
The same dangling reference corrupts inserts: connect_node navigates from entry_point, so new nodes connect to nothing until one of them happens to be assigned a level higher than the dead entry point's.
Suggested fix
In delete(), after blanking the node, check entry_point:
- if the deleted index is the entry point, re-seat it on any live node (e.g. scan for the highest-level node with a non-empty vector), or
Noneif the index is now empty; - have
search_layerskip nodes with empty vectors when seeding/collecting results (defense-in-depth — tombstones should never be returnable); - regression tests: delete-the-entry-point then search (must return only live ids, and must reach all live nodes), and delete-then-insert (new node must be reachable).
Related, same file
random_level() computes (-r.ln() * level_mult).floor() as usize with r: f64 = rng.gen() in [0, 1). At r == 0.0 (probability ~2⁻⁵³ per insert) -ln(0) = +inf, the cast saturates to usize::MAX, and HnswNode::new's vec[SmallVec::new(); level + 1] overflows/aborts. A r.max(f64::MIN_POSITIVE) clamp (or capping the level at e.g. 64) closes it. Worth folding into the same fix PR.
Found during the ADR-340 hardening pass (the #825 fix touched the adjacent code). Per ADR-340 invariant 6, the regression tests should use a seeded RNG.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start in crates/ruvector-delta-index/src/lib.rs by tracing DeltaHnsw::delete(), search_layer, connect_node, and random_level(). Add seeded regression coverage for deleting the entry point before searching, and deleting then inserting; done means no empty-id or infinite-distance results, live nodes remain reachable, and new nodes can be found. Also verify the random-level edge case described in the issue.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- databases, search
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 68/100