ruvnet / ruvnet/RuVector

ruvector-delta-index: delete() of the entry point leaves search anchored to a phantom node — the rest of the graph becomes unreachable

Open
#930 0 comments 0 reactions 0 assignees View on GitHub

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:

  1. Phantom results. The deleted node is returned as a SearchResult with an empty id and f32::MAX distance — search_layer unconditionally seeds its result heap with the start node.
  2. Total recall loss. Because delete() cleared the deleted node's own neighbor lists, the entry point now has no outgoing edges. greedy_search/search_layer cannot 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 None if the index is now empty;
  • have search_layer skip 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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.