ruvnet / ruvnet/RuVector

performance(mincut): replace O(m) edge scans in LocalKCut::check_cut with indexed lookup

Open
#942 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

Confirmed defect

LocalKCut::check_cut currently handles each boundary adjacency by calling self.graph.edges() and linearly searching the returned full-edge Vec by edge_id:

self.graph.edges().iter().find(|e| e.id == edge_id)

This is reachable on the default branch in crates/ruvector-mincut/src/localkcut/mod.rs. DynamicGraph already maintains edge_index and exposes get_edge(u, v), an endpoint-indexed lookup.

Evidence

PR #941 isolated the effect while testing min-cut-guided HNSW deletion repair:

  • individual find_cut calls: 24.8–158.0 seconds at HNSW construction density m0=32
  • completed three-deletion run: 318,024.78 ms for LocalCutGuided versus 0.78 ms for EagerRepair
  • the same order of magnitude appeared in three independent attempts

The broader HNSW repair hypothesis remains rejected because small-world topology also violates the local algorithm's bounded-degree assumptions. This issue concerns only the independent full-edge scan defect.

Minimal candidate

Use the existing endpoint lookup for each boundary adjacency, preserving edge weight and cut-edge semantics:

if let Some(edge) = self.graph.get_edge(v, neighbor) {
    cut_edges.push((v, neighbor));
    cut_value += edge.weight;
}

Acceptance criteria

  • Existing ruvector-mincut correctness tests remain green.
  • Add a regression that verifies identical cut membership and weight before/after the lookup change on weighted undirected graphs.
  • Add a fixed seeded dense-graph benchmark comparing the current scan implementation with the indexed implementation.
  • Indexed lookup is at least 100× faster on the recorded dense fixture without changing the returned LocalCutResult.
  • cargo test -p ruvector-mincut, cargo clippy -p ruvector-mincut --all-targets -- -D warnings, and the relevant workspace CI shard pass.
  • Do not revive or claim acceptance of the rejected min-cut-guided HNSW repair design without a separate preregistered experiment.

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-mincut/src/localkcut/mod.rs, focusing on LocalKCut::check_cut and DynamicGraph's existing get_edge lookup. Run cargo test -p ruvector-mincut and inspect the correctness tests before adding the weighted undirected regression and fixed-seed dense-graph benchmark. Done means unchanged LocalCutResult values, at least a 100× benchmark improvement, and passing the specified clippy and workspace CI checks.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
performance
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.