Concurrent HNSW build retries a lost entry-node promotion with the wrong query vector

With concurrent HNSW merging (numMergeWorkers > 1 plus an executor; the default is 1 worker), several workers insert vectors into one graph. A worker that inserts a node taller than the graph links it on the existing levels and then tries to make it the new entry node. If another worker raised the graph first, the promotion fails and HnswGraphBuilder.addGraphNodeInternal repeats the search and linking for the new levels. Since 10.2.0 (#14181) the builder reuses one mutable UpdateableRandomVectorScorer instead of creating a scorer per node (on main, one per worker), pointed at the inserted node once before the insert; linking re-points that same scorer at every candidate, and the retry never points it back. So the retry searches, scores and applies the diversity rule with another node's vector. No exception is thrown and the index is not corrupted; per hit one node's links on one or two top levels are affected. A one-line fix re-points the scorer before the retry.

• addGraphNode (HnswGraphBuilder.java:392-402) calls scorer.setScoringOrdinal(node) once (:394 / :400) and then addGraphNodeInternal(node, scorer, ...). In a concurrent merge each worker is its own builder with its own scorer (HnswConcurrentMergeBuilder.java:153-165).
• addGraphNodeInternal runs do { ... } while (true) (:323-389): greedy descent with scorer as the query (:338), beam search per level (:353), popToScratch keeps those scores (:356), addDiverseNeighbors links with them (:360-362), then tryPromoteNewEntryNode (:372). On failure the loop repeats for the new levels. Nothing in the loop re-points the scorer at node.
• Linking moves the scorer: selectAndLinkDiverse calls scorer.setScoringOrdinal(cNode) for every candidate (:515), and NeighborArray re-points it when a neighbour array overflows (NeighborArray.java:141, :301).
• OnHeapHnswGraph.tryPromoteNewEntryNode (:249-256) fails only when another thread promoted first (the entry level changed, or its compareAndSet lost to a concurrent promotion), so single-threaded builds (flush, the default merger) never retry.
• Every worker draws its levels from a random generator seeded with the same HnswGraphBuilder.randSeed (HnswConcurrentMergeBuilder.java:160, HnswGraphBuilder.java:185), one draw per node it inserts, so the k-th node each worker inserts (e.g. the same position in each worker's first batch) gets the same level, and workers tend to raise the graph at the same moment.

Four 1-d vectors 0, 1, 3, 7; M = 2; two workers with batch size 2 and randSeed 42, so each worker's first node gets level 0 and its second level 2.

1. Worker 0 inserts node 0 (level 0); it becomes the entry.
2. Worker 0 inserts node 1 (level 2): setScoringOrdinal(1), searches level 0 and finds node 0 (score 0.5).
3. While linking level 0, selectAndLinkDiverse calls setScoringOrdinal(0). At that moment worker 1 inserts node 2 (level 0) and node 3 (level 2); node 3's promotion succeeds and the graph now has 3 levels.
4. Worker 0's tryPromoteNewEntryNode(1, 2, 0) fails, and the retry searches levels 1-2 from entry 3 with the scorer still on node 0: it stores 0.02 = sim(0, 3) instead of 0.027027028 = sim(1, 3), on levels 1 and 2, in both directions (4 wrong entries; the test stops at the first).

In this tiny graph node 3 is the only candidate, so only the scores differ; in larger graphs the wrong query can also select different neighbours (see Who is affected).

• Who is exposed. Applications that enable concurrent HNSW merging: numMergeWorkers > 1 with an executor on Lucene99HnswVectorsFormat, Lucene104HnswScalarQuantizedVectorsFormat or another writing format with that setting (e.g. HnswBitVectorsFormat). Lucene99HnswVectorsWriter.createGraphMerger (:668-689) uses the concurrent merger only then; DEFAULT_NUM_MERGE_WORKER = 1 (Lucene99HnswVectorsFormat.java:120). Merges of segments that already have graphs can take the same retry: since #16794 the concurrent merger's join inserts also go through addGraphNodeInternal (HnswConcurrentMergeBuilder.java:566-571, :582-604; read, not executed).
• What changes. On the retried levels the node is searched with another node's vector: (a) the stored neighbour scores are wrong; they stay in memory, but overflow pruning later in the same build reads them; (b) the beam search and the diversity rule can keep different neighbours, and neighbour ids are what the writer persists.
• How often (executed). Study verifier, production HnswConcurrentMergeBuilder.build(), 4 workers, 16,384 random 16-d vectors, M 16, beamWidth 100: 3 of 200 builds had 1-2 wrong upper-level entries; 0 of 200 with the fix. Public IndexWriter.forceMerge of 33 graph-less segments into one (16,384 vectors), counters added to a copy of the builder: 8 workers, 9 of 200 and 5 of 200 merges took the retry, every retry stale; 16 workers, 19 of 400 merges, 21 of 22 retries stale; 1 worker, 0 retries in 30 merges; with the fix, 0 stale in 38 retries. Example: node 2219's retry scored its entry 171 as 0.233 instead of 0.351.
• Changed neighbours (supporting). In the 16-worker probe a dry run of each retry with the stale and the correct query selected different neighbours in 4 of 22 retries (node 2052 on level 1: [4] instead of [4, 4100]); 0 of 28 with the fix. The study's forced 3-worker probe on stock main: level-1 neighbours 3=[2] 4=[2] instead of 3=[2, 4] 4=[2, 3].
• Not measured. Recall. Upper levels are where every search descends, but each hit touches one node, so the impact is rated low.

Put the file at lucene/core/src/test/org/apache/lucene/util/hnsw/TestHnswConcurrentMergeRetryScorer.java. Worker 0 runs on the test thread; the scorer runs worker 1's stored task inside selectAndLinkDiverse, where worker 0 holds no lock, which stands in for the OS pausing worker 0 there. randSeed is pinned to its default 42 and restored, because other tests change it; setBatchSize(2) gives worker 0 nodes 0-1 and worker 1 nodes 2-3. The entryNode() precondition keeps a fixed build from passing vacuously. The seed does not matter.

On 10.2.0-10.6.0 the public constructor still takes M: new HnswConcurrentMergeBuilder(new TaskExecutor(r -> forkedWorker1 = r), 2, supplier, 2, 10, graph, null). Releases before 10.4.0 also need older accessors for nodeExistAtLevel / getScores.

As a regression test, use this same test unchanged.

# from a Lucene checkout ($LUCENE), with the test in lucene/core/src/test/org/apache/lucene/util/hnsw/
./gradlew :lucene:core:test --tests org.apache.lucene.util.hnsw.TestHnswConcurrentMergeRetryScorer -Ptests.seed=DEADBEEF
# assertions off fails the same way: add -Ptests.asserts=false

# main 645d4fe14a20, Gradle, -Ptests.seed=DEADBEEF (assertions on; the same with -Ptests.asserts=false)
TestHnswConcurrentMergeRetryScorer > testLostPromotionRetryScoresAgainstInsertedNode FAILED
    java.lang.AssertionError: level 1: 1 -> 3 expected:<0.027027028> but was:<0.02>
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.failNotEquals(Assert.java:835)
        at org.junit.Assert.assertEquals(Assert.java:577)
        at org.apache.lucene.util.hnsw.TestHnswConcurrentMergeRetryScorer.testLostPromotionRetryScoresAgainstInsertedNode(TestHnswConcurrentMergeRetryScorer.java:92)
BUILD FAILED

# the entry-node precondition (line 83, entry = 3) passed; 0.027027028 = 1/(1 + 6^2), 0.02 = 1/(1 + 7^2)
# with the one-line fix: BUILD SUCCESSFUL, assertions on and off
# release jars, same assertion: 10.2.0, 10.2.1, 10.2.2, 10.3.0, 10.3.1, 10.3.2 (API ports of the test), 10.4.0, 10.5.0, 10.5.1, 10.5.2, 10.6.0

• Contract. HnswGraphBuilder.java:282-295: the path is "thread safe when the graph size is fixed (e.g. when merging)", and when the entry node changed meanwhile "we need to reinsert the node to the newly introduced levels (repeating step 2,3 for new levels)", step 2 being this node's own search. NeighborArray.java:29: "encodes the neighbors of a node and their mutual scores". UpdateableRandomVectorScorer.java:31-37: "Changes the scoring ordinal to the given node ... @param node the node to score against", so the ordinal is caller state.
• It worked before. The retry loop dates from #12660 (2023, 9.9.0), when addGraphNode created a fixed scorer per node (scorerSupplier.scorer(node), still in 10.1.0 at HnswGraphBuilder.java:237). #14181 (48884e76e08, 2025-02-06) switched to a reused, mutable scorer that linking re-points. Executed: 10.1.0 passes, 10.2.0 fails.
• #14181 meant no behaviour change. In review its author reported recall dropping with multiple indexing and merging threads ("indicating I have a silly bug somewhere"), then "recall numbers all checkout and the API is nicer" before merging. Nobody discussed the retry.
• Supported option. numMergeWorkers is documented (Lucene99HnswVectorsFormat.java:215-223); no javadoc, CHANGES or MIGRATE entry allows a retry to score with another node's vector.
• Untested. No upstream test forces a lost promotion or checks what the retry scores or links. testConcurrentMergeBuilder checks only that no exception is thrown and "by no means guarantees the true correctness of the concurrent merge" (HnswGraphTestCase.java:1160-1164). The concurrent-merge tests added by #16794 compare vector-comparison counts, a one-worker build (which cannot retry) and recall with the serial merge, within a tolerance (concurrentRecall > 0.8 and > serialRecall - 0.05, :1318-1319).

Strongest case: HNSW is approximate, the concurrent builder never promised the same graph as a sequential build, and the scores the test checks are in-memory bookkeeping that is never written, reached through package-private hooks.

Why it fails: the javadoc defines the retry as this node's own search and 10.1.0 did exactly that, so this is a regression from a refactor that meant no behaviour change, not a designed trade-off. The query is not a coarser approximation but another node's vector, and in some retries it changes the persisted neighbour ids. The stored scores feed later pruning in the same build. The test uses the same same-package access as Lucene's own testConcurrentMergeBuilder (public constructor, the "test only" setBatchSize, OnHeapHnswGraph(int, int)), and a public-API merge probe reaches the stale retry with real threads and the production scorer. The fix costs nothing on the normal path.

Option A was built and validated; B and C are alternatives that were not built.

At the top of the do loop in addGraphNodeInternal (HnswGraphBuilder.java:323). lowestUnsetLevel > 0 only on a retry, which needs a lost promotion, so sequential builds and the normal concurrent path run no extra code (if open PR #16915 lands first, its connectNode(...) starts at lowestUnsetLevel = minLevel, so the guard may also fire on a first pass: one redundant, harmless call). The study's model, its verifier and a later check wrote the same change independently.

    do {
      if (lowestUnsetLevel > 0) {
        // a lost promotion: linking re-pointed the scorer, so point it at the inserted node again
        scorer.setScoringOrdinal(node);
      }
      curMaxLevel = hnsw.numLevels() - 1;

Trade-offs

None known. Calling it right after a failed tryPromoteNewEntryNode, before the loop repeats, is equivalent. No recall or speed benchmark was run; the hot path is unchanged.

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20, OpenJDK 25.0.3, seed DEADBEEF: stock, the repro fails with assertions on and off; with the fix it passes, on and off.
• With the fix: org.apache.lucene.util.hnsw.*, codecs.lucene99.*, codecs.lucene104.* and TestKnnGraph of lucene/core, the repro included: 26 suites, 526 tests, 0 failures, 0 errors, 18 skipped.
• checkGoogleJavaFormat, ecjLintMain, ecjLintTest, forbiddenApisMain, forbiddenApisTest of lucene/core: pass.
• Earlier, standalone with the fix shadowed in: the topology probe keeps 3=[2, 4] 4=[2, 3], and the public-API merge probes show 0 stale retries in 38.

Have addDiverseNeighbors point the scorer back at the node when it returns.

Trade-offs

Protects any future code that scores after linking, but adds a setScoringOrdinal per level for every inserted node on the hot path, and the default scorer copies the node's vector on each call (DefaultFlatVectorScorer.java:128-130). Not built.

Keep the query scorer fixed on the node and give linking its own scorer, as before 10.2.0.

Trade-offs

One more scorer per worker and changed signatures of the NeighborArray diversity methods; it touches the same calls that open issue #16903 discusses for a performance reason. Not built.

Method: semi-formal (the hypothesis came from reading the code while modelling the scorer ordinal; TLC then witnessed it).

• The model HnswConc.tla tracks the ordinal of each worker's UpdateableRandomVectorScorer at every setScoringOrdinal call site. TLC configuration C1 (3 nodes, 2 workers) violates the invariant ScorerQueryOK (every search's query is the node being inserted or repaired) in 33 steps, 1,317 distinct states, 1 s. The model with the fix holds over 1,695 states; a merge-reuse configuration (C6bug) is violated too.
• A separate verifier wrote its own tests on the real code (forced schedule, a topology probe and an unforced 200-build audit), reproduced it on main and 10.5.2 and wrote the same one-line fix.
• On 2026-10-29 the evidence was cut to the one deterministic test; on 2026-10-31 it was re-run on 645d4fe14a20 and the releases, and the reach was measured through IndexWriter.forceMerge.