With maxConn = 1, a merge that reuses an HNSW graph with a deleted vector never finishes

When a merge reuses a segment's HNSW graph that lost at least one vector to a delete, Lucene copies the graph, repairs it and calls InitializedHnswGraphBuilder.rebalanceGraph(). That method wants size * (1/M)^level vectors on each level and stops at the first level whose target is 0. For maxConn = 1, a value every HNSW format accepts, 1/M is 1.0: the target is the whole graph on every level, the exit is never taken, and every vector is promoted into one more level per pass, with links. forceMerge and close() cannot complete normally, and the heap grows until OutOfMemoryError closes the IndexWriter as a tragic event (on 10.6.0 and main rollback() can stop the merge first). HnswGraphBuilder itself gives M = 1 the level probability e^-1, and using that probability in rebalanceGraph is a one-line fix. Released in 10.5.1, 10.5.2 and 10.6.0 with the default codec.

InitializedHnswGraphBuilder.initializeFromGraph runs repair and rebalance only when the copy dropped a deleted vector (if (hasDeletes), InitializedHnswGraphBuilder.java:309-315 at 645d4fe14a20). rebalanceGraph() (:435-485):

double invMaxConn = 1.0 / M;                                          // :438
for (int level = 1; ; level++) {                                      // :441
  int maxNodesAtLevel = (int) (size * Math.pow(invMaxConn, level));   // :444
  if (maxNodesAtLevel <= 0) break; // the only exit                   // :445
  ...
  if (random.nextDouble() < invMaxConn && !hnsw.nodeExistAtLevel(level, node)) {   // :467
    maybeAbort();                                                     // :468
    hnsw.addNode(level, node);                                        // :470
    ... addConnections(node, level, scorer);                          // :477

For M = 1, invMaxConn is 1.0 and Math.pow(1.0, level) is 1.0, so maxNodesAtLevel == size on every level and the break is never reached. nextDouble() is always below 1.0, so every vector of level L-1 is promoted into level L, which is new each time (levelToNodes grows by one, :451). OnHeapHnswGraph.addNode grows the vector's level array and allocates a neighbour array per level with no cap. Once the method runs with M = 1 on a non-empty graph, the non-termination is exact: it does not depend on the seed or the vector values.

The repro's flushed graph has 2 levels; after the delete both survivors are on level 1. Level 1 already has its target of 2, so the loop adds level 2 with both, then level 3, and so on. Of the 1,001 merge abort checks before the test's guard fires, 989 come from rebalanceGraph promotions (:468), about 495 new levels. A unit-level probe of the same graph counted 133,541 levels after 10 s, with the heap after GC grown from 4.9 MB to 43.3 MB. With maxConn = 2 the target is (int) (2 * 0.5) = 1 on level 1 and 0 on level 2, so the loop stops; the merge takes 13 abort checks.

The builder assigns levels with ml = M == 1 ? 1 : 1 / Math.log(1.0 * M) (HnswGraphBuilder.java:184) and level = (int) (-log(U) * ml) (:573-578), so P(level >= 1) = exp(-1/ml): exactly 1/M for M >= 2, but e^-1 for M = 1. rebalanceGraph uses 1/M and says it is "matching HNSW's level assignment distribution" (:466). A bounded-exhaustive check of the loop's expressions over every accepted M (1 to 512) finds M = 1 the only value without an exit; every other M exits by level 31 even at the maximum document count.

On 10.6.0 and main the loop polls the merge abort check before each promotion (#16620), so rollback() ends the merge; forceMerge keeps waiting, and close() waits too, because IndexWriter.shutdown calls waitForMerges() (IndexWriter.java:1326). On 10.5.1 and 10.5.2 there is no check in the loop: the merge thread runs until OutOfMemoryError, then forceMerge throws "this writer hit an unrecoverable error; cannot complete forceMerge". The concurrent merger (numMergeWorkers > 1) runs the same rebalanceGraph and hangs the same way.

• Who. Fields whose HNSW format is built with maxConn = 1, e.g. new Lucene99HnswVectorsFormat(1, beamWidth) (executed). Lucene104HnswScalarQuantizedVectorsFormat, HnswBitVectorsFormat and the two sandbox formats DedupHnswVectorsFormat and DedupHnswScalarQuantizedVectorsFormat accept the same 1 to 512 and build their graphs with the same writer code and builders (code reading, not executed). The default is 16. maxConn = 1 is a low-recall setting (reasoned and called degenerate by a maintainer; recall not measured here), and Lucene's random test codecs never pick it (5 to 50).
• Trigger. A segment with a built graph, one delete or update (an update is a delete plus an add) that removes one of its vectors, and a merge that selects that graph as its base (deleted share, as an integer percentage, at most 40) and reuses it. With the default IndexWriterConfig, a plain commit() after the delete returns after about 0.55 s (its 500 ms merge-on-commit wait runs out) and leaves a merge thread running inside rebalanceGraph 3 s later; with maxConn = 2 the commit takes about 20 ms and no merge is left running. That is this input: whether a commit starts such a merge depends on the merge policy and the segments.
• Scale. None: 3 vectors with the tiny-segment threshold set to 0. With the 2-argument constructor (threshold 100) a merged segment needs about 650 live vectors before Lucene builds any graph; the hunt's 1,000-vector test hangs.
• Effect. A merge thread at full CPU, forceMerge and close() that do not return normally, and a heap that grows until OutOfMemoryError closes the writer: after about 13 s at 128 MB on main, 25 to 57 s at 512 MB on 10.5.x (1,000 vectors; times from one machine, they depend on heap size and hardware). Silent: no exception names the setting. By code reading, every later merge that reuses that segment's graph repeats it.
• How likely. Rare: it needs a non-default, degenerate setting; nobody has reported it since 10.4.0.

A finishing merge of this input needs 10 to 13 abort checks (maxConn 16 and 2), so the 1,000-check guard has a wide margin. The guard is an anonymous subclass of MergePolicy.OneMerge through its protected copy constructor (MergePolicy.java:260), and the codec comes from the test framework's TestUtil.alwaysKnnVectorsFormat. The test uses no randomness: for M = 1 the loop has no exit whatever the random draws.

Keep the test as it is. A commit() or an NRT reader open after forceMerge(1) starts a further merge of the same segment, which IndexWriter wraps in its own OneMerge (IndexWriter.java:3959-3964), so the test's guard does not apply and close() then waits for the endless merge (a diagnostic variant hung for 300 s that way). On 10.5.x the loop has no abort check, so the guard cannot work and the test hangs there.

This copy differs from the hunt's minimal test only in one wrapped line, so that it passes :lucene:core:checkGoogleJavaFormat.

cp $REPRO/TestHnswMaxConnOneMerge.java $LUCENE/lucene/core/src/test/org/apache/lucene/codecs/lucene99/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.codecs.lucene99.TestHnswMaxConnOneMerge -Ptests.seed=DEADBEEF
# add -Ptests.asserts=true or -Ptests.asserts=false to choose the assertion mode; it fails both ways

# gradle, fresh worktree at main 645d4fe14a20, -Ptests.seed=DEADBEEF -Ptests.asserts=false
TestHnswMaxConnOneMerge > testForceMergeWithDeletionFinishes FAILED
    java.lang.AssertionError: forceMerge(1) still running after 1,000 abort checks
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:ACBD97A663D25037]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.assertTrue(Assert.java:42)
        at org.apache.lucene.codecs.lucene99.TestHnswMaxConnOneMerge.testForceMergeWithDeletionFinishes(TestHnswMaxConnOneMerge.java:67)
1 test completed, 1 failed
# the same with -Ptests.asserts=true

# where the 1,001st abort check comes from (diagnostic copy of the same input, main, -ea and -da)
    at org.apache.lucene.index.MergeState.checkAborted(MergeState.java:249)
    at org.apache.lucene.util.hnsw.HnswGraphBuilder.maybeAbort(HnswGraphBuilder.java:230)
    at org.apache.lucene.util.hnsw.InitializedHnswGraphBuilder.rebalanceGraph(InitializedHnswGraphBuilder.java:468)
    at org.apache.lucene.util.hnsw.InitializedHnswGraphBuilder.initializeFromGraph(InitializedHnswGraphBuilder.java:314)
abort checks by caller, maxConn = 1: copyAndPruneGraphStructure 5, fixDisconnectedNodes 1, rebalanceGraph 989, merge plumbing 6
maxConn = 2: 13 checks (rebalanceGraph 0), finished; maxConn = 16: 10, finished; maxConn = 1, no delete: 17, finished

# standalone runner, the minimal test (tests_run=1 failures=1 each)
main 645d4fe14a20, 10.6.0   -ea and -da, seed DEADBEEF   the same AssertionError
10.5.2                      -da                          no exit after 60 s; merge thread in rebalanceGraph:405

• Accepted and tested as valid. Lucene99HnswVectorsFormat rejects only maxConn <= 0 or > 512 (Lucene99HnswVectorsFormat.java:271-276; the same check in the other four writable HNSW formats, two of them in the sandbox), and its testLimits asserts that -1 and 0 are rejected, not 1 (TestLucene99HnswVectorsFormat.java:64-70). No javadoc, CHANGES.txt or MIGRATE.md entry restricts maxConn to 2 or more.
• The builder supports M = 1 on purpose. The ml = M == 1 ? 1 : ... branch came with #11781 (07af358f90d, 2022, Lucene 9.4), and upstream tests build M = 1 graphs (HnswGraphTestCase.testDiversityFallback and testDiversity3d, HnswGraphBuilder.create(scorerSupplier, 1, 10, ...)). This shows that M = 1 is handled rather than rejected; it does not by itself promise useful recall.
• The method states the opposite intent. Javadoc: "maintain the expected exponential decay in level sizes according to the HNSW probabilistic model" (InitializedHnswGraphBuilder.java:420-421); comment: "Promote with probability 1/M, matching HNSW's level assignment distribution" (:466).
• History. The loop came with #15003 (2025); its 48 comments and 19 review comments never mention M = 1 or termination, and its benchmarks used maxConn 8 to 64. #16620 later added the abort poll for long but finite phases.

The strongest case for "intended or unsupported": maxConn = 1 is degenerate. Michael Sokolov excluded it from a search test as a "degenerate edge case" (d84925a201a, 2021) and called M=1 "a degenerate case" for connecting graph components in a 2024 review on #13566; Lucene's random codecs use 5 to 50; the classes are @lucene.experimental; and the javadoc formula totalNodes * (1/M)^level, read literally, promises no decay for M = 1.

Why it fails: those remarks are about recall and connectivity in tests, not a restriction of the format. The same test later excluded maxConn = 2 for connectivity too (LUCENE-9819, 9e8207a5587, 2021), and maxConn = 2 merges fine here. A quality trade-off does not explain a merge that never ends and exhausts the heap, and the literal reading of the formula contradicts the method's stated intent. If M = 1 should go, the answer is a clear IllegalArgumentException, not an endless merge. So the case is meaningful but insufficient: reviewers who argued the "intended" side, one from another model family (OpenAI GPT-5.6), rated it weak, and a later cross-model fact check rated it moderate while agreeing that a silent merge that never completes is not acceptable.

Three options; A was validated with gradle in a fresh scratch worktree at 645d4fe14a20, B and C were not executed. Maintainers who want M = 1 gone may prefer C; A and C combine well.

InitializedHnswGraphBuilder.java:438 becomes double invMaxConn = M == 1 ? Math.exp(-1) : 1.0 / M; (in general exp(-1/ml), the builder's P(level >= 1)), plus a two-line comment.

void rebalanceGraph() throws IOException {
  SplittableRandom random = new SplittableRandom(seed);
  int size = hnsw.size();
  // P(level >= 1) of HnswGraphBuilder's level distribution: exp(-1 / ml), which is 1/M for
  // M >= 2 and exp(-1) for M == 1 (where ml = 1)
  double invMaxConn = M == 1 ? Math.exp(-1) : 1.0 / M; // was: 1.0 / M
  for (int level = 1; ; level++) {
    int maxNodesAtLevel = (int) (size * Math.pow(invMaxConn, level));
    if (maxNodesAtLevel <= 0) break; // now reached for every M
    ...

Trade-offs

• No change for M >= 2. The expression is the same 1.0 / M there.
• M = 1 terminates for any input. The targets become size * e^-level, which reach 0 by level 22 even at the maximum document count; termination follows from the target, not from the random draws. In the 3-vector repro the level-1 target is already 0, and the merge finishes after 12 abort checks with no promotion.
• Javadoc. The formula totalNodes * (1/M)^level (:425) should then name the builder's level probability.
• It fixes the loop, not the poor recall of M = 1; that remains a configuration choice.
• Not measured: the recall, graph quality or merge time of a merged M = 1 graph with the fix; the validation covers termination and the existing tests.

What the checks validated

• Gradle, fresh scratch worktree at 645d4fe14a20, JDK 25.0.3, --no-daemon -Ptests.seed=DEADBEEF: without the fix the minimal test fails with -Ptests.asserts=true and false; git apply succeeds; with the fix :lucene:core:checkGoogleJavaFormat and the minimal test pass (assertions on and off).
• --tests 'org.apache.lucene.util.hnsw.*' --tests 'org.apache.lucene.codecs.lucene99.*' --tests TestKnnGraph --tests TestHnswMergeAbort: 19 suites, 352 tests, 12 skipped, 0 failures (TestHnswFloatVectorGraph 32, TestLucene99HnswVectorsFormat 60, TestKnnGraph 6, TestHnswMergeAbort 4).
• Earlier: the hunt's 1,000-vector test, an independent reproducer's test and the cross-model reviewers' tests passed with the same change; on 10.4.0, shadowing only this line makes the failing run pass.

Stop rebalancing at the source graph's top level, or at a fixed maximum level.

Trade-offs

Also guards against any future ratio mistake, but rebalanceGraph may create levels above the source graph's top today (:450-452) for M >= 2, so a bound changes that behaviour and needs a benchmark; it leaves the probability mismatch with the builder for M = 1. Not executed.

Lucene99HnswVectorsFormat, Lucene104HnswScalarQuantizedVectorsFormat, HnswBitVectorsFormat and the two sandbox formats DedupHnswVectorsFormat and DedupHnswScalarQuantizedVectorsFormat throw an IllegalArgumentException that names the setting.

Trade-offs

A clear error instead of a hang, but it breaks applications that configure 1 today, testLimits would need a new boundary case (it tests only -1 and 0 at the lower end), and it leaves HnswGraphBuilder's M == 1 branch and the two upstream M = 1 tests to decide on; the public @lucene.experimental builder classes would still loop for M = 1 unless option A is applied too. Not executed.

• First signal (2026-10-25). While writing a bounded-exhaustive translation-validation harness for the HNSW merge-reuse path, the finder read rebalanceGraph's bound. The harness swept M in {1, 2, 3, 4, 8, 16} x beamWidth in {1, 2, 3, 4, 8, 16, 100} x {one deletion, none}, with a bound on abort-check polls as the termination oracle, and reported non-termination for every M = 1 case with a deletion and beamWidth >= 2, with the serial and the concurrent merger, and for no other M. Every beamWidth = 1 case, M = 1 included, failed earlier with IllegalArgumentException: initialCapacity must be > 0 ... got: 0 (the sibling LFV-1056) and never reached the rebalance. It was confirmed end to end through IndexWriter.forceMerge on the stock main jars.
• Twin. In the same minute, a second finder reading the HNSW graph format found it with an SMT (Z3) obligation: for M == 1 no level satisfies (int) (size * (1/M)^level) <= 0, while for M >= 2 level 32 always does.
• Verification. An adjudication unit re-ran the earliest repro on 645d4fe14a20, reduced it to one public-API test, checked the loop's expressions for every accepted M (1 to 512), and ran controls; an independent reproducer, reviewers from another model family (OpenAI GPT-5.6, executed) and an intended-behaviour devil's advocate confirmed it; the no-noise gate reduced the test to 3 vectors.