lance-format / lance-format/lance
bug: align mem_wal HNSW construction with the reference algorithm
Nobody has claimed this yet.
- 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)
- New-node degree limit.
max_neighbors(m, level)returns2 * mat level 0 for all pruning, including a newly inserted node's initial neighbor selection. Per Algorithm 1 and hnswlib, a new node selectsMneighbors;Mmax0 = 2Monly bounds reciprocal edges on existing level-0 nodes. - 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). - Algorithm 4 configuration.
select_neighborsshould 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. - 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_batchstays consistent with the serializedlevel_offsetscontract (configured level count, empty trailing ranges) expected bylance-index'sHNSW::load. - Construction parameter validation. mem_wal uses its own
BuildParams; apply the same preconditions asHnswBuildParams::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::loadround-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-indexbuilders - #5156, #5183 — related root causes fixed there
Contributor guide
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 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