HnswGraph.DenseNodesIterator.consume() does not advance: reading HNSW level 0 in chunks returns the first chunk forever

HnswGraph#getNodesOnLevel(level) returns a NodesIterator, a PrimitiveIterator.OfInt over the node ids of one graph level with a bulk method consume(int[] dest) documented as "Consume integers from the iterator and place them into the dest array", returning the number written. For level 0, which holds every node, every Lucene graph that enumerates level 0 returns a DenseNodesIterator over [0, size): the in-memory OnHeapHnswGraph, the default codec's stored graph (through HnswGraphProvider#getGraph), the lucene91-lucene95 back-compat readers and getSortedNodes(0) (the lucene90 back-compat graphs throw UnsupportedOperationException instead). Its consume (HnswGraph.java:241-251) writes cur, cur+1, ... and returns the count but never runs cur += numToCopy, while nextInt() and hasNext() use the same cur. So a second consume returns the same block, hasNext() stays true, a while (hasNext()) consume(buf) loop never ends, and nextInt() after consume() starts again at 0. The two sibling classes, used for upper levels, advance. Lucene's only production consume() call (Lucene99HnswVectorsWriter.writeMeta) reads upper levels in one full-size call, so the bug is latent: only code outside Lucene that reads level 0 with consume() is hit. It came with consume() in #11860 (9.5.0, 2022) and is in every release up to 10.6.0 and on main. The fix is one line.

• NodesIterator (HnswGraph.java:161-186): "Iterator over the graph nodes on a certain level"; it implements PrimitiveIterator.OfInt (:166) and declares consume(int[] dest): "Consume integers from the iterator and place them into the dest array. @return The number of integers written to dest" (:179-185).
• DenseNodesIterator (:230-265): "NodesIterator that enumerates [0, size)", with one cursor cur shared by consume, nextInt (return cur++;) and hasNext (cur < size).
• Who returns it: getNodesOnLevel(0) of OnHeapHnswGraph (OnHeapHnswGraph.java:272-273), of the default codec's stored graph (Lucene99HnswVectorsReader.java:663-664) and of the back-compat readers (the lucene91, lucene92, lucene94 and lucene95 formats), and HnswGraph#getSortedNodes(0) (HnswGraph.java:149-150). Upper levels get ArrayNodesIterator or CollectionNodesIterator. getNodesOnLevel itself is abstract (HnswGraph.java:101): the lucene90 back-compat graphs throw UnsupportedOperationException, and a custom HnswGraph picks its own iterator.

1. DenseNodesIterator.consume(dest) (HnswGraph.java:241-251) computes numToCopy = Math.min(size - cur, dest.length), writes dest[i] = cur + i and returns numToCopy. It never runs cur += numToCopy.
2. So cur is where it was: the next consume copies the same block, hasNext() stays true, and nextInt() returns an id consume already handed out.
3. The siblings move their cursor: ArrayNodesIterator.consume has the same body plus cur += numToCopy; (:212), and CollectionNodesIterator.consume fills dest through nextInt() (:277-289). Upper levels are therefore correct.
4. Lucene never notices: its only production consume() call, Lucene99HnswVectorsWriter.writeMeta (:629-637), runs only if (level > 0), makes one call with a buffer of size() and drops the iterator. Every in-tree reader of level 0 uses hasNext() / nextInt().

• new DenseNodesIterator(4) consumed twice into an int[2]: [0, 1] and [0, 1] (expected [0, 1], [2, 3]).
• Stored graph of a 2,000-vector default-codec index, level 0 read with consume(int[7]) in a while (hasNext()) loop: every call returns 0-6; the test's bound stops it after 286 calls and 2,002 ids (expected 2,000 distinct ids, then hasNext() false). Level 1 of the same graph returns every node once.
• 1,000-document index, buffer 64: hasNext() is still true after 16 calls that returned 1,024 ids.
• consume(new int[3]) returns 0, 1, 2; the next nextInt() returns 0 instead of 3.

• Who is hit. Code outside Lucene that reads level 0 of an HNSW graph with consume() in more than one call, or mixes consume() with nextInt() / hasNext(). The iterator is public API in the exported package org.apache.lucene.util.hnsw (module-info.java:50): the stored graph through HnswGraphProvider#getGraph (@lucene.experimental, in the exported package org.apache.lucene.codecs.hnsw, :76), a completed OnHeapHnswGraph from HnswGraphBuilder (which a custom KnnVectorsWriter holds during flush and merge; while it is still being built, getNodesOnLevel throws IllegalStateException), getSortedNodes(0) on any graph, or new HnswGraph.DenseNodesIterator(n).
• What happens. A while (hasNext()) consume(buf) loop never ends on any non-empty level with any non-empty buffer; if it collects the ids, memory grows until the heap runs out. A loop that stops when the counts add up to size() ends, but when the buffer is smaller than the level it returns the first block repeatedly and misses the rest (by reading the code; with a buffer of at least size() such a loop is correct). consume() then nextInt() returns duplicates. One consume() into a size() buffer returns the right ids but leaves hasNext() true. A custom vectors writer that wrote level 0 from such a loop would hang on flush or write wrong graph data (by reading the code); Lucene's own writer does not do this.
• Lucene is not affected. Its only production consume() call reads upper levels in one full-size call; every in-tree reader of level 0 uses nextInt(); the query-time searcher does not use these iterators. Stored graphs are correct: a public-API test reads level 1 of a stored graph in chunks and gets every node once. This covers Lucene's own code; a custom HnswGraph implementation chooses its own level-0 iterator.
• The downstream code that was read is safe (a handful of repositories read during the prior-report search, not a survey). An Elasticsearch GPU HNSW writer, a cuVS helper and lucene-knn-oxide call consume only on upper levels with one full-size call; OpenSearch k-NN and cuVS have their own iterators that advance (read, not executed).
• How likely. Rare: no report since 9.5.0 (2023), and the callers found use the one-shot pattern. A caller that drains level 0 with while (hasNext()) consume(buf) hits it on any non-empty graph; how many such callers exist is not known.

The test sits in org.apache.lucene.util.hnsw next to the upstream HNSW tests; HnswGraph.DenseNodesIterator and its constructor are public, so it needs no package-private access. It is the class getNodesOnLevel(0) returns for Lucene's in-memory and stored graphs, so the realistic path (a stored graph through HnswGraphProvider#getGraph, read with a while (hasNext()) consume(buf) loop) fails for exactly the same reason; that longer test was run by the verifiers and is described in the steps above.

As the regression test: the same test unchanged, as a new class next to the other HNSW tests in lucene/core/src/test/org/apache/lucene/util/hnsw/. It fails on stock main and passes with fix A, with assertions on and off (gradle).

cp TestDenseNodesIteratorConsume.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/hnsw/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.hnsw.TestDenseNodesIteratorConsume -Ptests.seed=DEADBEEF -Ptests.asserts=true
# assertions off: -Ptests.asserts=false instead (same result)

# gradle, main 645d4fe14a20, -Ptests.seed=DEADBEEF -Ptests.asserts=true (the same with =false, and on 10.6.0)
TestDenseNodesIteratorConsume > testSecondConsumeReturnsNextChunk FAILED
    java.lang.AssertionError: expected:<[2, 3]> but was:<[0, 1]>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:69937511A3D822AF]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.failNotEquals(Assert.java:835)
        at org.junit.Assert.assertEquals(Assert.java:120)
        at org.junit.Assert.assertEquals(Assert.java:146)
        at org.apache.lucene.util.hnsw.TestDenseNodesIteratorConsume.testSecondConsumeReturnsNextChunk(TestDenseNodesIteratorConsume.java:30)

1 test completed, 1 failed

# with fix A (cur += numToCopy): 1 test completed, 0 failed (assertions on and off)

# realistic path, verifier's public-API test (stored graph of 2,000 vectors, level 0 read with consume(int[7]))
java.lang.AssertionError: level 0 via consume: first 14 returned [0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6] expected:<2000> but was:<2002>

• Contract. NodesIterator implements PrimitiveIterator.OfInt (HnswGraph.java:166); consume: "Consume integers from the iterator and place them into the dest array. @return The number of integers written to dest" (:179-185). Consuming from an iterator removes what was consumed; a method that leaves the cursor in place would be a peek or a copy, and nothing documents it that way.
• The code expects chunks. The array and dense versions compute Math.min(size - cur, dest.length) and copy from cur, not from 0; the collection version fills until dest is full; all return the count written. A partial fill points to callers that call again.
• History. #11860 (d0be9ab57c9, 2022-12-07) added consume as one method with two branches: the array branch ran cur += numToCopy, the dense branch (nodes == null) returned before it. The review on HnswGraph.java went in three steps: jpountz objected that "It's awkward to have a method that returns the entire set of data on an iterator" (2022-12-02); benwtrent first asked whether a one-shot copy from index 0 would do ("Would you prefer: public void consume(int[] dest) { System.arraycopy(nodes, 0, dest, 0, dest.length); } Or something?", the same day); then wrote "I added a "consume" method to this iterator. Seems to fit nicer to the iterator model." (2022-12-05). The merged method copies from cur, not from 0, returns how many it wrote and advances in its array branch. #12050 and #15425 moved the dense branch unchanged; git log -G'cur \+= numToCopy' shows no commit ever added the advance there.
• Tests and docs. #11860 added no test that calls consume; no upstream test calls consume on a level-0 iterator today; no comment, CHANGES.txt or MIGRATE.md entry describes a non-advancing consume.
• Independent implementations advance. cuVS, OpenSearch k-NN and a Go port implement consume with an advance (read).

The case for intended (the strongest version, from the intended-behaviour verifier and the cross-model reviews):

• (a) "Internal": the #15425 CHANGES entry (lucene/CHANGES.txt:1399, 10.4.0) says "Refactoring internal HnswGraph.NodesIterator", and the org.apache.lucene.util package-info says "APIs in this package are primarily internal and may change between releases" (util/package-info.java:35).
• (b) The consume javadoc never literally says "advances".
• (c) Every known caller does one full-size consume() on levels above 0, where the result is right, so consume is a one-shot bulk copy in practice.
• (d) In the #11860 review, benwtrent's first proposal was exactly such a one-shot copy from index 0, with no cursor: public void consume(int[] dest) { System.arraycopy(nodes, 0, dest, 0, dest.length); } (2022-12-02).
• (e) The stored graph is handed out through HnswGraphProvider#getGraph, and HnswGraphProvider is @lucene.experimental; stock Lucene is not affected at all.

Why it fails:

• (a) "Internal" in CHANGES is prose, not an API tag. The package-info sentence covers org.apache.lucene.util, a different Java package; the org.apache.lucene.util.hnsw package-info says nothing about internal use. HnswGraph, NodesIterator, DenseNodesIterator and its constructor are public, have no @lucene.internal or @lucene.experimental tag, and sit in an exported package.
• (b, c) The count, the copy from cur and the two advancing siblings strongly indicate cursor semantics. The one-shot callers explain why the bug stayed latent, not what was intended: the array branch written in the same commit advances.
• (d) That was a question in review ("Would you prefer: ... Or something?"). What was merged copies from cur, returns how many it wrote and advances in its array branch, and its author described it as fitting "the iterator model", so the design moved from a one-shot copy to iterator semantics.
• (e) @lucene.experimental says the API may change, not that it may return repeated ids. This point does make a "won't fix, internal" reply plausible.

How strong the case is: the adjudication records that all verifiers judged it weak, and the cross-model reviews rated it weak. A later cross-model fact check of the brief (OpenAI GPT-5.6) rated it moderate, because the contract is implied rather than written, HnswGraphProvider is experimental, the #15425 entry says "internal" and stock Lucene is unaffected; it still called it a narrow, latent correctness bug. It lowers the impact (minor, latent), not the validity.

Fix A and fix B were run through gradle in a scratch worktree of 645d4fe14a20. A is the fix; B adds one javadoc sentence so the contract is written down for the next implementation.

HnswGraph.java:247-250 on main. Backports to 9.5-10.3 put the same line in the nodes == null branch of NodesIterator.consume (9.5) or ArrayNodesIterator.consume (9.6-10.3).

       for (int i = 0; i < numToCopy; i++) {
         dest[i] = cur + i;
       }
+      cur += numToCopy;
       return numToCopy;
     }

Trade-offs

• Makes the class behave like its two siblings and like the method's own javadoc; no change for Lucene's callers, none of which reads level 0 with consume.
• The shared DenseNodesIterator.EMPTY (size 0) still throws on consume before touching cur.
• No cost: one addition per call.

What the checks validated

• Gradle in a scratch worktree of 645d4fe14a20 (2026-11-01, removed afterwards): the repro fails on stock main and passes with A, each with -Ptests.asserts=true and =false.
• With A: 16 core test classes, 321 tests, 0 failures, 12 skipped (6 @Nightly, 6 that apply only to scalar-quantized formats): the repro, every class of org.apache.lucene.util.hnsw (TestOnHeapHnswGraph, TestHnswUtil, TestHnswFloatVectorGraph, TestHnswByteVectorGraph, TestHnswFloat16VectorGraph, TestFilteredHnswGraphSearcher, TestIncrementalHnswGraphMergerBaseSelection, TestNeighborArray, TestNeighborQueue, TestFloatHeap), TestKnnGraph, TestHnswMergeAbort, TestLucene99HnswVectorsFormat, TestLucene99HnswVectorsFormatV0 and TestLucene104HnswScalarQuantizedVectorsFormat.
• With A: the back-compat HNSW tests (:lucene:backward-codecs:test --tests '*Hnsw*'; those readers also return DenseNodesIterator for level 0): 9 classes, 578 tests, 0 failures, 66 skipped (8 @Nightly, 16 scalar-quantized-only, 42 tests, 3 each for the 14 index versions 9.0.0-9.9.2 that TestInt7HnswBackwardsCompatibility does not support). The full core suite was not run.
• Earlier, the same line shadowed in: the finder's, the independent reproduction's, the cross-model review's and the intended-behaviour check's tests pass, and so do 17 existing tests the refute-lens reviewer ran (TestOnHeapHnswGraph, TestHnswUtil, TestKnnGraph); the same line in 9.5.0's dense branch passes the history test.

Adds to the consume javadoc (HnswGraph.java:180): "These are the next integers that {@link #nextInt()} would return, and the iterator advances past them." All three classes then follow the written contract.

Trade-offs

Documentation only on top of A; worth it because the missing sentence is how the dense branch slipped through.

What the checks validated

• Gradle, same worktree: the repro passes with B (-Ptests.asserts=true), and :lucene:core:check -x test (google-java-format, ecj lint of main and test sources, forbidden APIs, generated-file checksums) passes with B and the repro test in place, so the javadoc sentence and the test are correctly formatted.

State that consume does not advance and may be called only once, with a buffer of size().

Trade-offs

Not recommended, not tested: it contradicts the two advancing implementations and PrimitiveIterator.OfInt, and keeps the chunked-loop trap.

Method: non-formal (code reading during modelling). The hunt unit on the HNSW graph format modelled HnswGraph.NodesIterator as a cursor over a finite sequence: nextInt() returns the element at the cursor and advances it, and consume(dest) copies up to dest.length elements from the cursor and advances it by the returned count. Checking that model against the three implementations showed that ArrayNodesIterator and CollectionNodesIterator follow it and DenseNodesIterator, the level-0 iterator of Lucene's in-memory and stored graphs, does not.

The finder wrote a JUnit on the stock main jars (a drain loop, a consume-then-nextInt check and an ArrayNodesIterator control): 2 of 3 failed with assertions on and off. It was then reviewed by a reviewer from another model family (OpenAI GPT-5.6), reproduced by independent verifiers (one through the stored graph of real indexes, from a package outside Lucene), judged, traced through every release since 9.5.0, and cut to the one-test repro on 645d4fe14a20.