HNSW merge repair (addConnections) walks down from the farthest upper-level candidate, not the closest one its javadoc describes

Since 10.4.0 (#15003) a merge can reuse a segment's HNSW graph that has deletions: it copies the graph without the deleted nodes, re-links every node left with no neighbours on a level, and promotes nodes to keep the upper levels populated. Both steps call HnswGraphBuilder.addConnections, whose javadoc says it will "Navigate down from the top level to find the closest node at the target level". The loop instead collects up to beamWidth (default 100) candidates per upper level in a min-heap GraphBuilderKnnCollector and continues from popNode(), the top of that heap, which is the farthest of the candidates it kept. Normal insertion does the same walk with a size-1 collector.

The minimal test shows the choice directly: X (at 1) is re-linked to P (at 100) instead of E (at 0). On the real merge path, with the default codec, every walk step started from a non-best node in the random-delete runs, and 40-100% of them in the others. With random deletes the effect is negligible. After deletes concentrated in vector space, the documented walk would cut the merge's graph-search work by 14-29%, but recall@10 near the deleted regions was 2.6-8.2 points lower with it in synthetic probes. So this is a mismatch between code and documented intent with a measured trade-off; no recall loss from the current code is claimed, and the remedy (change the walk after a benchmark, or document it) is for the maintainers to choose.

// HnswGraphBuilder.java:774 (javadoc): Navigate down from the top level to find the closest node at the target level
int beamWidth = beamCandidates.k();                                              // :787
GraphBuilderKnnCollector candidates = new GraphBuilderKnnCollector(beamWidth);   // :788
int[] eps = {hnsw.entryNode()};                                                  // :789
// Navigate down from top to target level, greedily moving toward the new node   // :791
for (int level = hnsw.numLevels() - 1; level > targetLevel; level--) {
  graphSearcher.searchLevel(candidates, scorer, level, eps, hnsw, null);         // :793
  eps[0] = candidates.popNode();                                                 // :794
  candidates.clear();
}

1. GraphBuilderKnnCollector wraps new NeighborQueue(k, false) (HnswGraphBuilder.java:822), which is Order.MIN_HEAP (NeighborQueue.java:59-62); pop() "Removes the top element" (:127-130). The top of a min-heap is the lowest score.
2. HnswGraphSearcher.searchLevel documents the order: "the most distant neighbor of the topK found, i.e. the one with the lowest score/comparison value, will be at the top of the heap, while the closest neighbor will be the last to be popped" (HnswGraphSearcher.java:272-277). popToScratch says the same for this collector: "sorted from worst to best" (HnswGraphBuilder.java:546-547).
3. So at each upper level the walk continues from the farthest of up to beamWidth (default 100) candidates; on a small top level, from the farthest reachable node of the level.
4. Normal insertion (addGraphNodeInternal) does the same walk with entryCandidates = new GraphBuilderKnnCollector(1) (HnswGraphBuilder.java:193, :334-340, "for levels > nodeLevel search with topk = 1"), so its pop is the best node.

• fixDisconnectedNodes, for a node with no surviving neighbours on a level: "Node has no neighbors, add connections from scratch" (HnswGraphBuilder.java:757-759).
• rebalanceGraph, for every promoted node that is not the first on its level (InitializedHnswGraphBuilder.java:472-478).
• Both run whenever the reused graph has deletes (InitializedHnswGraphBuilder.java:303-316). Among the input graphs with at most 40% deleted vectors (an integer percentage), a merge reuses the one with the most live vectors (IncrementalHnswGraphMerger.java:65, :133-139), via MergingHnswGraphBuilder.fromGraphs (MergingHnswGraphBuilder.java:107-109), the default single-worker merger (Lucene99HnswVectorsWriter.java:688); the concurrent merger calls the same two methods (HnswConcurrentMergeBuilder.java:199, :427). Flush-time building and query-time search do not call addConnections.

Default vs opt-in. In 10.4.0 and 10.5.0 a guard tested the per-field wrapper, "so every merge rebuilt the graph from scratch" (CHANGES.txt, GITHUB#16400 under 10.5.1); there the repair runs only with a codec whose knnVectorsFormat() is not the per-field wrapper. From 10.5.1 on it runs with the default codec.

Measured on the real merge path. IndexWriter with the default codec and HNSW format (M = 16, beamWidth = 100, one merge worker); segment A with deletes plus segment B (1,000 docs) without; forceMerge(1) reuses A's graph. Paired runs, current code vs the documented (size-1) walk, synthetic 50-cluster Gaussian data, 500 queries, recall@10 with k = 10:

• "Region cores": cluster centres are taken in turn and every vector within sqrt(1.5 x dim) of the centre is deleted until the target count is reached (the last centre may be only partly cleared), a stress case for deletes concentrated in vector space (for example a delete-by-query of one tenant, topic or time range whose embeddings sit together). Other queries were unchanged (within 0.0004).
• Read the other way: after such deletes the current code does 16%, 20%, 21% and 41% more merge graph-search work, and keeps 2.6-8.2 points better recall@10 near the deleted regions.
• "Search work" counts nodes scored in graph-builder searches, not wall time. CheckIndex was clean in all 19 runs. In the two configurations also run on the plain stock jar (20% region cores, and 40% region cores seed 1), recall matched the instrumented stock runs exactly.
• Calls and walk steps are those of the current-code run; the documented-walk run made the same or slightly fewer repair calls (34/34, 65/66, 9/9, 166/173, 338/348, 355/365, 528/552).
• An earlier study measurement of initGraph alone points the same way: the documented walk cut its score() calls by 11.7-30.2% in 8 region-delete configurations and lowered recall@10 in all 8 (-0.9 to -7.4 points); with random deletes it cut them by under 0.1%, with identical recall. Its unverified explanation: far entry points give orphaned nodes long-range links that act as bridges in a fragmented graph.
• Not measured: real embeddings, luceneutil, wall-clock merge time.

The source graph: E at 0 (the entry, levels 0 and 1), P at 100 (levels 0 and 1), X at 1 and D (level 0); level-1 link E -> P, level-0 link X -> D. D is deleted (ord map {0, 1, 2, -1}, 3 surviving vectors, beamWidth 100).

• X kept 0 of its 1 level-0 neighbours, so the repair calls addConnections(X, 0). The level-1 search from E finds E (score 0.5) and P (score 0.000102); popNode() returns P.
• E and P have no level-0 links, so the level-0 search finds only the node it starts from: the start shows up directly as X's neighbour. On a connected level 0 the beam search usually recovers, and the cost is extra work instead.
• With 3 nodes and M = 16, rebalanceGraph promotes nothing. Nothing is randomized; the seed only fixes the test framework's own choices.
• Access: the package-private OnHeapHnswGraph(int, int) constructor, from the same package as Lucene's own HNSW tests; everything else is public (some of it @lucene.internal or @lucene.experimental). The test compiles unchanged against 10.4.0-10.6.0 and main.
• As a regression test: the same test, but only if the maintainers choose the greedy walk.

# gradle, main 645d4fe14a20, seed DEADBEEF (same with -Ptests.asserts=false)
TestAddConnectionsRepairDescent > testRepairDescendsFromClosestUpperLevelNode FAILED
    java.lang.AssertionError: X's level-0 neighbor (E=0, P=1) expected:<0> but was:<1>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:36C37F5C40E3DE23]:0)
        ...
        at org.apache.lucene.util.hnsw.TestAddConnectionsRepairDescent.testRepairDescendsFromClosestUpperLevelNode(TestAddConnectionsRepairDescent.java:47)
1 test completed, 1 failed

# with the size-1 walk (fix option B): :lucene:core:test (SUCCESS): 1 test, then BUILD SUCCESSFUL (assertions on and off)

# instrumented copy of the stock code (print statements only)
TRACE node 2 has 0 neighbors on level 0 -> addConnections(2, 0)
TRACE level 1 searchLevel from eps [0]: size 2 k 100 best-first [score:node] [0.50000000:0, 0.00010202:1] heap top (popNode returns it) node 1 score 0.00010202
TRACE level 1 popNode() -> eps[0] = 1
TRACE node 2 level 0 neighbors after addDiverseNeighbors [1]

# release jars, same test: 10.4.0, 10.5.0, 10.5.1, 10.5.2, 10.6.0 fail with the same message

• Own documentation: "Navigate down from the top level to find the closest node at the target level" (HnswGraphBuilder.java:774) and "greedily moving toward the new node" (:791).
• The primitive documents its order: "the most distant neighbor ... will be at the top of the heap" (HnswGraphSearcher.java:272-277); "sorted from worst to best" (HnswGraphBuilder.java:546-547).
• The sibling walk in normal insertion uses a size-1 collector for this exact step (HnswGraphBuilder.java:193, :334-340).
• Other code and PR text describe it as a descent from the entry node to the level: the concurrent merger orders repairs "because addConnections descends through the already-repaired upper levels" (HnswConcurrentMergeBuilder.java:435-436); #16627's PR body says the zero-neighbour path "walks from the entry node to reach the current level". Neither says which candidate the descent continues from.
• History: #15003 wrote the method with this loop, javadoc and comment; #16627 moved it unchanged. Neither PR's discussion (#15003: 48 comments, 19 review comments; #16627: 8 comments, 36 review comments) mentions which candidate the walk starts from, and CHANGES.txt and MIGRATE.md document nothing about it.
• Tests check that repaired nodes have neighbours and that the graph stays rooted and searchable; none pins where the walk starts.

The reviewer from another model family (OpenAI GPT-5.6) built the strongest case for "intended", which it rated moderate: the repair is a heuristic, and a non-closest seed can add exploration or diversity; the public builders are @lucene.experimental and promise a usable approximate graph, not particular links; tests check only rootedness and searchability; the failing graph is hand-built; and the documented walk lowered recall in the region-delete measurements.

Why it fails: the method's own javadoc and comment are the contract the code contradicts, and @lucene.experimental does not make a contradiction intended. The same choice, with changed links, shows on the public IndexWriter.forceMerge path. Tests that check only rootedness are missing coverage, not a statement of intent. Nobody designed or documented a farthest-candidate start, and its recall benefit is measured here, not explained anywhere upstream. The recall result is why the remedy is open (document it, or change it after benchmarks), not a sign that the mismatch is intended. Verdict: a real mismatch, low priority; which side to fix is the maintainers' call. Limits: the javadoc and comment are internal documentation, not a public contract, and the silence of the PR threads is absence of evidence; so this shows a mismatch between the code and its local documentation, not what the repair was meant to do.

Four options. The greedy walk was validated with gradle; none was benchmarked for recall or merge time with luceneutil.

Which behaviour is intended is the maintainers' choice. Benchmark the greedy walk against main with luceneutil on real embeddings, with random deletes and with deletes concentrated in vector space, measuring merge time and recall. If the greedy walk holds recall, take it; if not, document the current walk.

Trade-offs

Slower than a patch, but the only measurements so far (synthetic data) point in opposite directions for cost and recall, so a patch either way would be a guess.

What the checks validated

Not run (no luceneutil benchmark was done).

+4/-3 lines in HnswGraphBuilder.addConnections: the upper-level searches go into their own GraphBuilderKnnCollector(1), so popNode() returns the closest candidate.

     // Navigate down from top to target level, greedily moving toward the new node
+    GraphBuilderKnnCollector entry = new GraphBuilderKnnCollector(1);
     for (int level = hnsw.numLevels() - 1; level > targetLevel; level--) {
-      graphSearcher.searchLevel(candidates, scorer, level, eps, hnsw, null);
-      eps[0] = candidates.popNode();
-      candidates.clear();
+      entry.clear();
+      graphSearcher.searchLevel(entry, scorer, level, eps, hnsw, null);
+      eps[0] = entry.popNode();
     }

Trade-offs

• Matches the javadoc and the sibling walk; each upper-level search keeps 1 result instead of up to 100.
• Measured: with random deletes -0.1% to -0.3% merge graph-search work and recall within 0.0002; after region-concentrated deletes it cuts the merge's graph-search work by 14-29% but lowers recall@10 near the deleted regions by 2.6-8.2 points (synthetic data). The study's initGraph-only runs agree: -11.7% to -30.2% score() calls, recall -0.9 to -7.4 points in 8 of 8 region-delete configurations.
• The change alters two things at once: which candidate the walk continues from, and how far each upper-level search explores (1 result kept instead of up to 100). So the cost and recall differences cannot be credited to the nearest-versus-farthest choice alone; the beam-search variant below separates the two in part.
• Changes repaired links only in merges that reuse a graph with deletes.

What the checks validated

• Gradle in a scratch worktree of 645d4fe14a20 (removed afterwards), seed DEADBEEF: without the change the repro fails with assertions on and off; with it, it passes with assertions on and off.
• The 16 closest suites pass: 339 tests, 0 failures, 9 skipped (340 tests in 17 classes with the repro itself; all of org.apache.lucene.util.hnsw.*, including the repair and merge-reuse tests of TestHnswFloatVectorGraph; TestLucene99HnswVectorsFormat, TestLucene99HnswVectorsFormatV0, TestKnnGraph, TestHnswMergeAbort, TestKnnFloatVectorQuery, TestKnnByteVectorQuery).
• ./gradlew :lucene:core:check -x test passes with the repro test in place.
• These suites check correctness, not recall or merge cost.

Change the javadoc (HnswGraphBuilder.java:774) and the loop comment (:791) to say the walk continues from the farthest of the candidates it kept, and why.

Trade-offs

No behaviour change, so no runtime risk; the remaining risk is documenting behaviour that may be accidental as intended. But it keeps the 16-41% extra merge graph-search work after region-concentrated deletes, and nobody has shown why the far start helps recall (the study's bridge explanation is unverified). If the benefit is real, a cheaper way to get it could be explored.

Pop all but the last candidate before taking eps[0] (the study's second patch).

Trade-offs

Same rule as the greedy walk (continue from the best candidate found), but over a full beamWidth search per level, so it can pick a different entry than the greedy walk, and it saves less (-9.6% to -27.4% initGraph score() calls) and lost more recall (-2.4 to -10.3 points) in the study's 8 region-delete configurations. The greedy walk is the simpler form.

What the checks validated

Only by the study's own tests (classpath shadowing, 2026-10-22).

Method: TLA+ model checking (TLC) of the HNSW build, merge and repair code (the formal verification study, 2026-10-22, main 7cecf79523).

• An AI modeller wrote a TLA+ model of the concurrent HNSW build, merge and repair, with a mapping table from model actions to Java lines (the action that takes eps[0] = candidates.popNode() maps to line 794).
• Among its properties, DescentGreedy ("addConnections descends to the best candidate") was written before looking for this bug. On configuration R3 (2 levels, one node with no neighbours) TLC reported its violation in a 7-step trace: the level-1 search finds nodes 0 and 1 and the walk continues from 0, the worse one (16 distinct states, 1 s).
• An independent AI verifier wrote its own tests on the stock jars (main and 10.5.2), measured reach in real IndexWriter merges and the effect of two candidate fixes. The hunt later cut the repro to one 4-node test and re-checked it on main 645d4fe14a20 and releases; a tie-breaker added the paired merge probe.