lance-format / lance-format/lance

bug: align mem_wal HNSW construction with the reference algorithm

Open
#8,236 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug
Dominant language
Rust
Stars
7.1k
Forks
852
Avg merge
3d 18h
Merged PRs (30d)
272

Description

Summary

rust/lance/src/dataset/mem_wal/hnsw/graph.rs implements a third, independent HNSW construction path, alongside the offline HnswBuilder and the OnlineHnswBuilder in lance-index. It did not benefit from the reference-alignment audit in #8036, which #8188 applied to the other two builders.

This issue tracks applying the same reference alignment to the mem_wal builder so that all three construction paths share one tested set of invariants.

Deviations to audit and fix (mirroring #8036 / #8188)

  1. New-node degree limit. max_neighbors(m, level) returns 2 * m at level 0 for all pruning, including a newly inserted node's initial neighbor selection. Per Algorithm 1 and hnswlib, a new node selects M neighbors; Mmax0 = 2M only bounds reciprocal edges on existing level-0 nodes.
  2. Reciprocal edges vs. diversity pruning. Verify that reciprocal candidates join the complete old-plus-new candidate set before SELECT-NEIGHBORS, with no distance-only cutoff gate (the failure mode #8188 removed from the other two builders).
  3. Algorithm 4 configuration. select_neighbors should document and implement the chosen options — extendCandidates = false, keepPrunedConnections = true (refill from pruned candidates up to the degree limit), matching #8188. The refill is load-bearing: correcting the new-node limit to M without refill fragmented the graph enough to make HNSW-PQ recall fluctuate stochastically (0.902–0.987) in #8188's CI.
  4. Entry point / level assignment. mem_wal already uses random levels plus entry-point promotion; verify the semantics match the reference (the first globally highest node is the fixpoint of sequential strict promotion) and that to_lance_hnsw_batch stays consistent with the serialized level_offsets contract (configured level count, empty trailing ranges) expected by lance-index's HNSW::load.
  5. Construction parameter validation. mem_wal uses its own BuildParams; apply the same preconditions as HnswBuildParams::validate() from #8188 (max_level > 0, m >= 4, ef_construction >= m, overflow guard) at its boundary, with descriptive errors.

Acceptance criteria

  • Per-role degree limits (M for a new node, Mmax0 for reciprocal capacity) with structural tests.
  • Reciprocal candidates participate in the diversity heuristic with the complete candidate set.
  • keepPrunedConnections refill implemented and Algorithm 4 options documented.
  • Entry-point semantics verified against the reference model.
  • Parameter validation with descriptive errors and tests.
  • Existing mem_wal HNSW tests and the HNSW::load round-trip test keep passing; recall does not regress.

References

  • #8036 — umbrella audit of HNSW deviations from the reference algorithm
  • #8188 — reference alignment for the offline and online lance-index builders
  • #5156, #5183 — related root causes fixed there

Contributor guide

Open the contributing guide

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 with rust/lance/src/dataset/mem_wal/hnsw/graph.rs and compare its construction logic with the reference-alignment changes in #8036 and #8188. Review HnswBuildParams::validate() and the HNSW::load level_offsets contract, then run the existing mem_wal HNSW tests and load round-trip test. Done means the listed degree, pruning, entry-point, validation, and recall criteria pass.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
machine-learning
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.