bug: track HNSW deviations from the reference algorithm

[u70b3]

Summary

Track and resolve the remaining places where Lance's HNSW construction and
search behavior differs from Algorithms 1–5 in the HNSW paper.

This audit was inspired by #5208, whose comparison against the paper exposed
the level-0 query-entry discrepancy addressed by #8035. Reviewing the adjacent
construction and search paths with the same paper-driven method revealed the
additional differences collected here.

This is an umbrella issue. Some differences below are likely correctness or
graph-quality bugs; others may be intentional engineering variants. Each item
should be explicitly classified, tested, and either aligned with the reference
algorithm or documented with benchmark evidence.

Reference:

• HNSW paper: Malkov and Yashunin, Algorithms 1–5
• Maintained reference implementation: nmslib/hnswlib at d9b3608
• Query descent through level 0 is being addressed separately by feat(index): stop HNSW greedy descent before level 0 #8035, fixing Bug: HNSW::search_inner incorrectly sets the entry point for the bottom level #5208.

Confirmed differences and evidence

1. Reciprocal edges are rejected before the diversity heuristic

Algorithm 1 first adds the reciprocal connection and, when the existing node
exceeds Mmax, applies SELECT-NEIGHBORS to the complete old-plus-new
candidate set.

Lance instead rejects the reciprocal edge unless its distance is below
cutoff:

• offline builder
• online builder

The cutoff is also not reliably the furthest distance. Reciprocal edges are
appended with push, while lists at or below capacity are not sorted, and
cutoff reads last():

• add_neighbor appends and cutoff reads last()
• prune returns without sorting at or below capacity

Lists produced by beam search (into_sorted_vec) and by the selection
heuristic are sorted, so the unsorted tail is introduced specifically when a
reciprocal edge is appended and prune then takes the len <= m_max early
return without re-sorting. Because last() can only read an element closer
than or equal to the true furthest neighbor, the cutoff errs in the
over-rejection direction: reciprocal edges that a correct implementation
would keep are dropped, compounding the link loss described below.

Even with a sorted list, a distance-only cutoff is not equivalent to Algorithm
4: a more distant but directionally diverse candidate may replace a closer,
redundant neighbor.

For comparison, hnswlib always inserts the new reciprocal candidate into the
heuristic when the existing list is full:

• reciprocal connection and pruning

Potential impact: missing reciprocal links, weaker cross-cluster connectivity,
and lower recall.

2. A new level-0 node may retain 2 * M neighbors instead of M

Algorithm 1 selects M neighbors for the newly inserted node.
Mmax0 ~= 2 * M is the capacity used when pruning reciprocal connections on
existing level-0 nodes.

Lance uses the same pruning limit for both roles, so a newly inserted level-0
node can retain 2 * M neighbors:

• new-node candidates are pruned through the shared function
• the shared level-0 limit is 2 * M

hnswlib separates the two concepts: it selects M_ connections for the new
node while using maxM0_ for an existing node's reciprocal capacity:

• new-node M_ versus reciprocal Mcurmax

Potential impact: different degree distribution, index size, distance
computations, and M parameter semantics.

3. The offline builder forces node 0 into every configured level

The paper randomly assigns each node's level and updates the entry point when a
new maximum level appears.

The offline builder instead fixes entry_point = 0 and gives node 0 all
configured levels:

• fixed entry point and full-height node 0

The online builder uses dynamic entry-point promotion, so offline and online
construction do not have the same hierarchy semantics.

This also feeds the existing level_count / persisted level_offsets
misalignment tracked by #5156:

• only level 0 is initially counted
• the regression test explicitly records surplus rows and off-by-one upper-level slices

The dedicated parity assertion queries fsl.value(0), which is the fixed entry
point itself and therefore does not strongly exercise upper-level traversal:

• entry-point query in the offset regression

The misalignment is reproduced behavior on the pinned commit: the regression
test above passes by asserting the surplus rows and off-by-one upper slices.
Its docstring references the closed load-side issue #6746, while the open
root-cause counting bug is #5156.

Potential impact: unnecessary empty/singleton upper levels, offline/online graph
differences, and persisted upper-level boundaries that do not describe the
emitted rows.

4. SEARCH-LAYER uses a per-expanded-node static furthest bound

Already tracked by #5183.

Algorithm 2 refreshes the furthest member of W after W changes. Lance
captures furthest once before processing all neighbors of the current node:

• static bound in beam_search_loop!

Because the captured bound can only be looser than the updated one, this is
primarily expected to admit extra candidates and distance computations rather
than reduce recall. It should still be measured and resolved or documented.

5. Algorithm 4 options are hard-coded

The paper exposes extendCandidates and keepPrunedConnections. Lance's
heuristic sorts the supplied candidates and selects diverse neighbors, but does
not extend candidates through their adjacency and does not refill from rejected
candidates:

• Lance neighbor-selection heuristic

Both flags being false is a valid Algorithm 4 configuration, but the choice
should be explicit because the paper reports candidate extension as important
for clustered data.

6. Construction parameters do not enforce algorithm preconditions

The offline builder does not validate at its boundary that:

• max_level > 0 — max_level = 0 underflows max_level - 1 in
  random_level
  and desynchronizes node heights from the zero-sized level_count, so it
  panics instead of returning a descriptive error
• M > 1, required by mL = 1 / ln(M) — M = 1 makes mL infinite and
  saturates every node to the maximum level; M = 0 collapses the graph to
  a single level
• ef_construction >= M, required to discover enough candidates to establish
  M connections — a smaller ef_construction silently caps the new node's
  degree at ef_construction

hnswlib, for example, normalizes construction ef to at least M:

• ef_construction_ = max(ef_construction, M_)

Supporting evidence that this boundary is unmaintained: the HnswBuildParams
builder docs state defaults of max_level = 8, num_edges = 30, and
ef_construction = 100, while the actual defaults are 7, 20, and 150:

• stale default-value docs

Validation status

Each item above was re-verified against b29e602fd (current main at the
time of writing, and the commit pinned by all Lance links above):

• hnswlib d9b3608 confirms the reference behaviors cited in items 1, 2, and
  6: getNeighborsByHeuristic2(top_candidates, M_) for the new node,
  Mcurmax for reciprocal capacity, ef_construction_ = max(ef_construction, M_), and dynamic enterpoint_node_ promotion on a new maximum level.
• The level_offsets misalignment in item 3 reproduces today: the in-tree
  regression test passes by asserting the surplus rows and off-by-one upper
  slices.

Related issues

• Bug: HNSW::search_inner incorrectly sets the entry point for the bottom level #5208 / feat(index): stop HNSW greedy descent before level 0 #8035 — query greedy descent must stop before level 0
• Potential Bug: HNSW beam_search incorrectly uses a static furthest variable #5183 — static furthest bound in SEARCH-LAYER
• Potential Bug: HNSW level_count should start from 1 for all levels #5156 — incorrect upper-level counts for the fixed entry node
• Track HNSW related indices to make sure it works fine #5621 — broad HNSW verification tracker

Proposed implementation checklist

• Classify each difference above as a bug, an intentional variant, or
  obsolete behavior.
• Make reciprocal-edge pruning evaluate the complete candidate set; add a
  structural test where a farther but diverse edge must be retained.
• Separate M for a new node from Mmax / Mmax0 for reciprocal
  capacity; assert per-role degree limits in offline and online builders.
• Decide the intended offline entry-point / level assignment model and
  make offline and online semantics explicit.
• Resolve Potential Bug: HNSW level_count should start from 1 for all levels #5156 and make persisted level_offsets match emitted level
  boundaries. Preserve stable-format compatibility if this index format is
  stable; otherwise avoid compatibility machinery for an unstable format.
• Resolve or explicitly document Potential Bug: HNSW beam_search incorrectly uses a static furthest variable #5183 with a distance-computation
  regression test.
• Decide whether Algorithm 4 candidate extension should be configurable or
  remain disabled with benchmark justification.
• Validate construction parameters at API boundaries with descriptive
  errors and tests.
• Add built-versus-loaded parity coverage over multiple non-entry-point
  queries on a multi-level graph.
• Benchmark recall, latency, build time, and graph degree distribution
  before and after changes on SIFT and clustered data, at low and high
  ef.

Completion criteria

• All differences are either aligned with the selected reference semantics or
  documented as intentional variants with evidence.
• Offline, online, and loaded HNSW paths have consistent tested invariants.
• Structural regression tests fail on the old behavior for each correctness
  fix.
• Recall does not regress, and any build/search/index-size tradeoff is reported
  with reproducible benchmark settings.