An empty OnHeapHnswGraph reports 2 levels, but listing level 1 throws NullPointerException

The finding in 30 seconds

An empty graph reports 2 levels because it starts with a placeholder entry node on level 1. Its upper-level node lists are cached and rebuilt only when size() differs from the size at the last rebuild. On a new graph both are 0, so the lists are never built and level 1 reads a null array.

Background: levels and the node-list cache

An HNSW graph has levels: level 0 holds every node, each higher level a shrinking subset. numLevels() says how many there are, and getNodesOnLevel(level) lists the nodes on one of them.
OnHeapHnswGraph is the in-memory graph that HnswGraphBuilder builds and a vectors writer then writes level by level. It lists level 0 directly and keeps the lists of the higher levels in a cache that it fills on the first such call.

On the left, a graph of 8 vectors is drawn as two stacked levels, all 8 nodes and their links on level 0 and nodes 2, 3 and 4 also on level 1, next to a grey box holding the node list of each upper level (level 1: 2, 3, 4), so getNodesOnLevel(1) returns 2, 3, 4; on the right, the empty graph built from 0 vectors still shows two levels, level 1 a dashed placeholder with no node, and its red box says the level-1 list was never built because the node count 0 equals the count at the last build, which starts at 0, so getNodesOnLevel(1) throws; below, the expected panel says level 1 of the empty graph lists no nodes, as level 0 does, and the actual panel says NullPointerException because the list it reads was never built. — An empty HNSW graph still reports a placeholder top level, but its cache of upper-level node lists looks up to date because the node count never moved from 0, so listing level 1 throws instead of returning an empty list. Generated with AI, checked against the code.

Diagram of the bug: an OnHeapHnswGraph built from 0 vectors reports numLevels() = 2 and size() = 0. getNodesOnLevel(0) returns 0 nodes. getNodesOnLevel(1) calls generateLevelToNodes, whose check lastFreezeSize (0) == size() (0) returns early, so levelToNodes stays null and reading levelToNodes[1] throws NullPointerException. A fix strip below says to also rebuild when levelToNodes is null or its length is not numLevels(), and that with it level 1 lists 0 nodes and the repro passes. — The repro's graph from 0 vectors: `numLevels()` is 2, `size()` is 0. Level 0 lists 0 nodes; for level 1 the cache check sees 0 nodes now and 0 at the last build, skips the build, and reads a list that was never made. Select the still to open it at full size. Generated with AI, checked against the code.

The finding, step by step

Build a graph from 0 vectors: HnswGraphBuilder.create(scorers, 8, 20, 1L).build(0) over an empty 2-dimensional FloatVectorValues. The graph has 0 nodes, and numLevels() returns 2.
List every level it reports, the loop a vectors writer runs when it writes a graph: getNodesOnLevel(0), then getNodesOnLevel(1).
You expect 0 nodes on both levels, which is what HnswGraph.EMPTY returns for any level.
Level 0 lists 0 nodes, but level 1 throws NullPointerException: Cannot load from object array because "this.levelToNodes" is null at OnHeapHnswGraph.java:276, with assertions on and off. getSortedNodes(1) fails the same way.
Why: the graph builds its upper-level node lists on first use and skips that when the node count equals the count at the last build. A new graph has 0 nodes and remembers 0, so the lists are never built.

Who is affected

Only code that builds HNSW graphs itself with the public HnswGraphBuilder over a vector set that can be empty, then lists an upper level, such as a custom vectors format or an offline graph tool. Lucene's own writer never builds an empty graph. In 9.12.0, 9.12.1, 10.0.0 and 10.1.0 build(0) itself throws. The failure is loud.

Mechanism, terms and numbers341 words

HnswGraphBuilder.create(...).build(0) over an empty vector set returns an OnHeapHnswGraph with 0 nodes whose numLevels() is 2, because every new graph starts with the placeholder entry node EntryNode(-1, 1) (OnHeapHnswGraph.java:77, :199-202). getNodesOnLevel(0) returns an empty iterator, but getNodesOnLevel(1), and getSortedNodes(1) which calls it, throw NullPointerException at :276. The upper-level node lists are built on first use and counted as up to date whenever lastFreezeSize == size() (:281-283); on a new graph both are 0, so the lists stay null.

On main, Lucene's own vectors writer builds a graph only when a field has vectors, so indexing, merging and search never reach it; only code that drives the public util.hnsw builder itself over a possibly empty vector set is hit. In 9.12.0, 9.12.1, 10.0.0 and 10.1.0 the builder walks every level itself when it finishes (connectComponents()), so there build(0) already throws. The fix is a two-line change in generateLevelToNodes().

The mechanism (main `5adff78bb168`, `lucene/core/src/java/org/apache/lucene/util/hnsw/`)

Two levels on an empty graph. The constructor sets entryNode = new EntryNode(-1, 1) (OnHeapHnswGraph.java:77); numLevels() returns entryNode.get().level + 1 (:199-202), so a graph with 0 nodes reports 2 levels.
A cache keyed on the node count. The upper-level lists levelToNodes are "only generated on demand" (:48-51) and start null; lastFreezeSize starts at its default 0 (:52-54).
The listing call. getNodesOnLevel(level) first checks that the build is complete, size() != maxNodeId() + 1 (:268-271): 0 == -1 + 1, so it passes. Level 0 returns new DenseNodesIterator(size()) (:272-273); any other level calls generateLevelToNodes() and then reads levelToNodes[level] (:275-276).
The early return (the fix site). generateLevelToNodes() returns at once when lastFreezeSize == size() (:281-283). Both are 0, so levelToNodes stays null and :276 throws. getSortedNodes(level > 0) goes through the same call (HnswGraph.java:148-152). The failing call changes no state.

Executed alongside: getSortedNodes(1) of the same graph throws the same exception, while getNodesOnLevel(0) of it and HnswGraph.EMPTY.getNodesOnLevel(1) are empty.

Exposure and likelihood342 words

Who. Code that calls HnswGraphBuilder.create(...).build(maxOrd) over a vector set that can be empty and then lists a level from 1 to numLevels() - 1 of the result with getNodesOnLevel or getSortedNodes, for example in a loop over every reported level to write or check the graph. It fails every time the set is empty.
Default vs opt-in. Opt-in. On main, the flush path returns no graph unless a vector was added (Lucene99HnswVectorsWriter.java:880-887, node > 0), the merge path builds a graph only for numVectors > 0 (:453, :712-713), and a missing graph is written as 0 levels (:560, :623-625). CheckIndex lists levels of graphs read from the index, not of an OnHeapHnswGraph; Word2VecSynonymProvider can build an empty graph but on main only searches it.
Older releases: build(0) itself throws in four of them. In 9.12.0, 9.12.1, 10.0.0 and 10.1.0, HnswGraphBuilder.finish() calls connectComponents(), which walks every level the graph reports and, for level 0, lists level 1 through HnswUtil.components. There build(0) throws the same NPE before it returns a graph: executed on 10.0.0 (getNodesOnLevel at OnHeapHnswGraph.java:247 <- HnswUtil.components <- connectComponents <- finish <- getCompletedGraph <- build), by reading for the other three. In those releases the in-tree Word2VecSynonymProvider, which builds with build(word2VecModel.size()), would hit it in its constructor when given an empty model (by reading; not run). The call is absent in 9.9.x to 9.11.x and commented out in 9.12.2, 9.12.3, 10.2.0 and later and on main (HnswGraphBuilder.java:587); the vectors writer is guarded in those four releases as on main.
Effect. A NullPointerException in the caller's thread, with assertions on and off. No wrong result, no change to the graph or to any index.
Scale. Zero vectors. For valid (positive) M and beam width, neither they nor the seed play a part (by reading; the runs used M 8 and 16).
Workaround. Treat an empty vector set as "no graph", as Lucene's writer does, or check graph.size() == 0 before walking the upper levels.

Minimal repro

One JUnit test method: build a graph from 0 vectors and list every level it reports. Public API only (HnswBuilder and DefaultFlatVectorScorer are tagged @lucene.experimental), single-threaded, deterministic; it fails with assertions on and off.

TestEmptyOnHeapGraphLevels.java (one JUnit test)38 lines

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.lucene.util.hnsw;

import java.util.List;
import org.apache.lucene.codecs.hnsw.DefaultFlatVectorScorer;
import org.apache.lucene.index.FloatVectorValues;
import org.apache.lucene.index.VectorSimilarityFunction;
import org.apache.lucene.tests.util.LuceneTestCase;

public class TestEmptyOnHeapGraphLevels extends LuceneTestCase {

  // Expected: every level an empty graph reports lists 0 nodes; actual: NullPointerException on
  // level 1.
  public void testEmptyGraphListsEveryLevel() throws Exception {
    RandomVectorScorerSupplier scorers =
        DefaultFlatVectorScorer.INSTANCE.getRandomVectorScorerSupplier(
            VectorSimilarityFunction.EUCLIDEAN, FloatVectorValues.fromFloats(List.of(), 2));
    OnHeapHnswGraph graph = HnswGraphBuilder.create(scorers, 8, 20, 1L).build(0);
    for (int level = 0; level < graph.numLevels(); level++) {
      assertEquals(0, graph.getNodesOnLevel(level).size());
    }
  }
}

Command

cp $REPRO/TestEmptyOnHeapGraphLevels.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/hnsw/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.hnsw.TestEmptyOnHeapGraphLevels -Ptests.seed=DEADBEEF
# and with -Ptests.asserts=false: the same failure

Expected: Every level below numLevels() (levels 0 and 1) lists 0 nodes.
Observed: Level 1 throws NullPointerException: Cannot load from object array because "this.levelToNodes" is null at OnHeapHnswGraph.getNodesOnLevel(OnHeapHnswGraph.java:276).

All files of this repro: repro/LFV-1234/

More files, environment, full output111 words

TestEmptyOnHeapGraphLevels (one method, extends LuceneTestCase, package org.apache.lucene.util.hnsw of the lucene/core tests). Under 2 s. It does not hard-code the level count, so it still holds if a maintainer prefers to make an empty graph report fewer levels. It is the minimal repro after the code formatter, which only re-wrapped the comment; it passes checkGoogleJavaFormat and serves as the regression test.

Environment

lucene	`main 5adff78bb168 (12.0.0-SNAPSHOT): fails; 9.9.0 to 10.6.0 (5 releases run): the same scenario fails; 9.8.0: passes`
jdk	`OpenJDK 25.0.3 (build 25.0.3+9-LTS)`
os	`Linux aarch64 (nothing platform-specific)`

Observed output

TestEmptyOnHeapGraphLevels > testEmptyGraphListsEveryLevel FAILED
    java.lang.NullPointerException: Cannot load from object array because "this.levelToNodes" is null
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:5F11917B9F7645E1]:0)
        at org.apache.lucene.util.hnsw.OnHeapHnswGraph.getNodesOnLevel(OnHeapHnswGraph.java:276)
        at org.apache.lucene.util.hnsw.TestEmptyOnHeapGraphLevels.testEmptyGraphListsEveryLevel(TestEmptyOnHeapGraphLevels.java:35)

Why it looks unintended

numLevels() "Returns the number of levels of the graph"; getNodesOnLevel gets "all nodes on a given level". Neither excludes empty graphs.
build(0) returns a completed graph that passes its own completeness check; HnswGraph.EMPTY lists 0 nodes for any level.
An accidental interaction: #12651 keyed the cache on size when an empty graph had 1 level; #12660 then gave it 2.

The full argument232 words

Contract. HnswGraph.numLevels(): "Returns the number of levels of the graph" (HnswGraph.java:85-86); getNodesOnLevel(level): "Get all nodes on a given level" (:94-101). HnswBuilder.build(maxOrd): "Adds all nodes to the graph up to the provided maxOrd", no positive-only precondition (HnswBuilder.java:32-37); build(0) is accepted.
The class's own checks accept the call. build returns getCompletedGraph(), which finishes and freezes the builder (HnswGraphBuilder.java:200-210, :236-242, :583-589), so the javadoc NOTE "calling this method while the graph is still building is prohibited" (OnHeapHnswGraph.java:264) does not apply. The completeness check passes (:268-271), and the same javadoc presents the cache as a speed-up ("only the first non-zero level call will pay the cost", :259-262), not as a precondition.
History. #12651 (a1cf22e6a94, 2023-10-16) added the size-keyed cache when an empty graph still had one level (9.8.0: this.numLevels = 1; // Implicitly start the graph with a single level). #12660 (a8c52e2e19c, 2023-10-28) replaced that with EntryNode(-1, 1). Neither review thread discusses empty graphs or the cache key. 9.9.0 with only EntryNode(-1, 0) put back passes the test.
Upstream relies on the 2 levels. TestOnHeapHnswGraph.testIncompleteGraphThrow adds nodes to a graph whose entry node was never set and expects getNodesOnLevel(1) to list one node (TestOnHeapHnswGraph.java:37-44); so the level count is relied on, and the broken part is the cache key.

The devil's-advocate check153 words

The strongest case for "not a bug", which the cross-model reviews (OpenAI GPT-5.6) rated moderate before rejecting it: the HnswBuilder interface is @lucene.experimental (HnswBuilder.java:28), and so is the scorer the repro uses (DefaultFlatVectorScorer.java:33); Lucene's codec never builds an empty graph; HnswGraph.EMPTY reports 0 levels; and the package javadoc calls the graph "nominally Hierarchical but currently only has a single layer" (package-info.java:19), so the placeholder level may not read as a promise. Callers, on this view, should not build an empty on-heap graph at all.

Why it does not settle it: HnswGraphBuilder and OnHeapHnswGraph are public, untagged classes in the exported package org.apache.lucene.util.hnsw (module-info.java:50); "experimental" speaks to API stability, not to an NPE on an object the builder itself returns; and the graph reports the very level it then cannot list. A maintainer may still call it too minor, a fair outcome for a Low bug.

Suggested fix

Recommended Rebuild when the cache is missing or has the wrong number of levels (fix A)

In generateLevelToNodes(), also rebuild when the cache is missing or has the wrong number of levels, not only when size() changed (a two-line change). With it the repro passes with assertions on and off, and 132 tests of the closest HNSW suites pass.

  private void generateLevelToNodes() {
    int maxLevels = numLevels();
    if (levelToNodes != null && levelToNodes.length == maxLevels && lastFreezeSize == size()) {
      return;
    }
    levelToNodes = new IntArrayList[maxLevels];

All options and trade-offs3 options · 494 words

Fix A was built and checked through gradle on 5adff78bb168; B was run by an independent fact check (the repro and TestOnHeapHnswGraph pass); C was run and breaks an upstream test. Open PR #16815 would move EntryNode(-1, 1) into a new base class and copy the same size-keyed cache into a new graph class; if it lands first, a fix should cover both.

Rebuild when the cache is missing or has the wrong number of levels (fix A) (validated by the checks) (recommended)

In OnHeapHnswGraph.generateLevelToNodes() (OnHeapHnswGraph.java:280-284), return early only when the lists exist, have numLevels() entries and the size is unchanged.

  private void generateLevelToNodes() {
    int maxLevels = numLevels();
    if (levelToNodes != null && levelToNodes.length == maxLevels && lastFreezeSize == size()) {
      return;
    }
    levelToNodes = new IntArrayList[maxLevels];

Trade-offs

Each upper-level call now reads numLevels() before the check instead of after it and adds a null check and a length check (short-circuited); the rebuild still runs only when the graph changed or the lists were never built. On non-empty graphs behaviour changes only if the level count changed since the last build, and then the lists are rebuilt instead of reused. Scope: fix A covers a missing cache and a changed level count; like the current code, it does not detect a change that keeps both size() and the level count.

What the checks validated

Gradle in a scratch worktree at 5adff78bb168, seed DEADBEEF: the repro fails without the fix (assertions on and off: 1 test, 1 failure) and passes with it (assertions off).
With the fix and assertions on: the repro (1), TestOnHeapHnswGraph (4), TestHnswUtil (7), TestHnswFloatVectorGraph (33), TestHnswByteVectorGraph (27) and TestLucene99HnswVectorsFormat (60): 132 tests, 0 failures, 5 skipped (nightly-only, or not applicable to this format). checkGoogleJavaFormat passes. The full core suite was not run; only OpenJDK 25.0.3 on Linux aarch64.
Earlier: shadow-class runs of the same change pass the repro with -ea and -da, and TestOnHeapHnswGraph plus TestHnswUtil (11 tests); cross-model reviews confirmed it with their own tests.

Start lastFreezeSize at -1 (fix B) (validated by the checks)

Initialise lastFreezeSize to -1 (OnHeapHnswGraph.java:52-53), so a never-built cache never counts as fresh.

Trade-offs

One line and fixes the empty graph, but unlike A it still trusts the size alone after the first build. The one-line form is over 100 columns, so the formatter would re-wrap its trailing comment.

What the checks validated

Not run for this doc; an independent fact check ran it on 5adff78bb168 (lastFreezeSize = -1;): the repro plus TestOnHeapHnswGraph pass with assertions on, 5 tests.

Make an empty graph report fewer levels: EntryNode(-1, 0) (fix C) (validated by the checks)

Start a new graph with the entry level 0, as before #12660.

Trade-offs

Not recommended: upstream TestOnHeapHnswGraph.testIncompleteGraphThrow relies on an entry-less graph reporting 2 levels.

What the checks validated

Run by the devil's-advocate verifier: testIncompleteGraphThrow then fails (1 of 4, ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1).

Downstream note

Downstream products are affected only if their own code builds HNSW graphs with this builder over a possibly empty vector set and (on main) lists its upper levels; in 9.12.0, 9.12.1, 10.0.0 and 10.1.0 build(0) alone throws, which an application could also reach by giving Word2VecSynonymProvider an empty model. Documents, queries and index files alone never reach it.

How it was found

A proof-obligation audit of OnHeapHnswGraph's contract: every level below numLevels() must be listable, including on the empty graph the builder returns. The size-keyed cache check fails that obligation; a public-API JUnit test then witnessed the exception.

The method in full113 words

Method: semi-formal (a proof-obligation audit of a class's contract, witnessed by an executable repro).

The finder set the level count of an empty graph against the freshness rule of the upper-level node cache in getNodesOnLevel, and found that the rule treats a never-built cache as fresh when the graph has 0 nodes.
The finder then wrote a public-API JUnit test and the two-line fix that makes it pass.
An independent reproducer and two executed cross-model reviews reproduced it with their own tests; a devil's-advocate verifier re-ran the finder's test (main with assertions on and off, 10.6.0), and an adjudication re-ran the reproducer's test with a fresh seed ("Prior reports, history and checks").

Prior reports, history and checks

Prior reports

No prior report found in apache/lucene issues, PRs and commits, the mailing lists, the JIRA archive, downstream trackers or the web (searched 2026-11-03). Nearest: #12651 and #12660, the two changes that interact, and open PR #16815, which copies the same cache.

Searches3 searches

No matching public report was found in the documented searches. Nearest items, none a report of this bug: #12651 (added the size-keyed cache) and #12660 (gave an empty graph 2 levels), whose discussions never mention empty graphs or the cache key; #14963 (how a segment with no graph is written, 0 levels); open #16815 (copies the cache pattern into a new class without mentioning the defect). Limits: keyword search; private reports are not visible.

What was searched, when, and what turned up
Where	When	How	Found
GitHub issues, PRs and commits (apache/lucene incl. the migrated JIRA archive)	2026-11-03; re-checked the same day	two scripted prior-report searches (51 queries each, 227 distinct hits) and about 20 manual searches: getNodesOnLevel with NullPointerException or empty, levelToNodes, lastFreezeSize, generateLevelToNodes, the exception text, getSortedNodes, build(0), HnswGraph.EMPTY, EntryNode	no report; #12651, #12660, #14963 and #16815 are the nearest
Open PRs	2026-11-03	the changed files of all 410 open apache/lucene PRs and the 42 updated since 2026-11-01	only #16815 and #13113 touch OnHeapHnswGraph.java; neither fixes this
Mailing lists, downstream, web	2026-11-03	dev@, java-user@, issues@ and commits@; Elasticsearch, OpenSearch, OpenSearch k-NN and Solr; 3 web queries	nothing about this bug

History

Introduced in 9.9.0 by #12660 (a8c52e2e19c, 2023-10-28), which gave an empty graph 2 levels on top of #12651's size-keyed cache (2023-10-16). 9.8.0 passes; every executed release from 9.9.0 to 10.6.0 and main fails (10.0.0 already inside build(0)). Not fixed upstream.

Versions tested8 rows

Introduced by a8c52e2e19c on main (#12660 "Concurrent HNSW Merge", Patrick Zhai, merged 2023-10-28; branch_9x 5fe48424a25), on top of a1cf22e6a94 (#12651 "Optimize OnHeapHnswGraph's data structure", same author, merged 2023-10-16; branch_9x ba26abcaee9). Both first shipped in 9.9.0, so no release has only one of them. 9.9.0 with only EntryNode(-1, 0) put back passes, which pins the trigger to #12660.

The 9.9.0 and 9.12.3 runs used a copy of the same test written against those releases' vector API. By reading, every release tag from 9.9.0 to 10.6.0 has both new EntryNode(-1, 1) and lastFreezeSize == size(), and so do upstream main 1c2072f0284 and branch_10_6. Not new in 10.6.

In 9.12.0, 9.12.1, 10.0.0 and 10.1.0 the failure comes earlier: HnswGraphBuilder.finish() calls connectComponents(), which lists level 1 through HnswUtil.components, so build(0) throws before it returns a graph (executed on 10.0.0; by reading for the other three, which were not run). In 9.12.2, 9.12.3, 10.2.0 and later and on main that call is commented out, and the NPE comes when the caller lists level 1.

Versions and branches executed, with results
Version or commit	Verdict	Result
9.8.0	not affected	passes: an empty graph has 1 level, and there is no cache
9.9.0	API copy	fails, same NPE (OnHeapHnswGraph.java:245)
9.9.0 + EntryNode(-1, 0)	counterfactual	passes
9.12.0, 9.12.1, 10.1.0	by reading	not run; finish() calls connectComponents() as in 10.0.0, so build(0) throws
10.0.0	inside build(0)	fails, same NPE (OnHeapHnswGraph.java:247), already inside build(0): finish() -> connectComponents() -> HnswUtil.components -> getNodesOnLevel(1)
9.12.3, 10.5.2	affected	fail, same NPE (OnHeapHnswGraph.java:270, :269)
10.6.0	affected	fails, same NPE (OnHeapHnswGraph.java:269)
main 5adff78bb168	-ea and -da	fails, same NPE (OnHeapHnswGraph.java:276)

Independent checks

A finder, an independent reproducer, two executed cross-model reviews (OpenAI GPT-5.6), a devil's-advocate verifier and an adjudication all found it real; an audit kept it and a final repro check reproduced it. This doc's gradle runs reproduced it on main and validated the fix.

Checks and verdicts283 words

The cross-model reviews ran on main ea57360912ed, where OnHeapHnswGraph.java and HnswGraph.java are identical to 5adff78bb168; one reviewer's test was re-run on 5adff78bb168 and fails there too. Every other main run used 5adff78bb168.

Each independent check and its verdict
Check	Verdict	What it found
finder	reproduced	Own test fails on main (assertions on and off) and 10.6.0; fix A makes it pass.
independent reproducer	real	Own fix-agnostic test (the repro is a trimmed copy) fails on main, 10.6.0, 10.5.2 and 9.12.3 (API copy), and on 9.9.0 through a same-package constructor check; passes with fix A.
cross-model review, refute lens (OpenAI GPT-5.6, executed)	real (high)	Own test (`build(0)` over a one-vector scorer) fails with `-ea` and `-da`; a `build(1)` control passes; fix A passes its test and 11 upstream tests.
cross-model review, intended lens (OpenAI GPT-5.6, executed)	real (high)	Own test fails on main and 10.6.0 while `build(1)` and `HnswGraph.EMPTY` controls pass; rated the works-as-designed case moderate and rebutted it.
devil's-advocate verifier	real	Re-ran the finder's test on main (assertions on and off) and 10.6.0: fails. Five intended or misuse arguments rebutted; showed that fix C breaks `testIncompleteGraphThrow`.
adjudication	confirmed (high), Low	Re-ran the reproducer's test with a fresh seed, assertions on and off: fails.
separate re-run, audit and final repro check	reproduced; confirmed, Low; impact minor	Fresh seeds fail on main and pass with fix A; the audit kept the finding; a final repro check kept the one-test repro and set the impact to minor.
this doc's gradle fix check	reproduced; fix A validated	Fails without the fix (on, off); passes with it; 132 tests of 5 closest suites pass.

Diagram file

The diagram as a still image, generated with AI and checked against the code. It is under 10 MB, the limit for a GitHub attachment.

PNG 516 KB

Sources and provenance

Finding record, Lucene and upstream sources, repro files and diagram notes1,582 words

Finding record

LFV-1234, snapshot of 2026-11-06

Registry title: OnHeapHnswGraph.getNodesOnLevel(1) throws NullPointerException on the empty graph that HnswGraphBuilder.build(0) returns, although that graph reports numLevels() == 2, because the upper-level node cache counts as up to date whenever lastFreezeSize == size(), and both start at 0, so it is never built (since 9.9.0)
Area: core / util/hnsw: OnHeapHnswGraph (upper-level node cache of getNodesOnLevel and getSortedNodes)
Priority: Low, rank 697: OnHeapHnswGraph.getNodesOnLevel(1) throws NullPointerException on the empty graph that HnswGraphBuilder.build(0) returns, although that graph reports two levels, in every release since 9.9.0. Only custom code that builds graphs itself over a vector set that may be empty and then walks the upper levels hits it. Lucene's own writer never does, and the failure is loud.
Impact class: minor
Impact note: Only code that builds an HNSW graph itself with the public util.hnsw builder (HnswGraphBuilder.create(...).build(maxOrd)) over a vector set that can be empty, and then lists an upper level of the returned graph (getNodesOnLevel or getSortedNodes for a level from 1 to numLevels() - 1, for example in a loop over every reported level to write or check the graph), is hit, every time the set is empty, with -ea and -da, in every release since 9.9.0 and on main; it fails loudly with NullPointerException, returns no wrong result and changes no graph or index state; Lucene's own vectors writer builds a graph only when a field has vectors and never walks an empty one, so IndexWriter, merges, search and the default codec never reach it.
Summary: You build an HNSW graph with HnswGraphBuilder.create(...).build(0) over an empty vector set and list the nodes of every level the returned OnHeapHnswGraph reports (numLevels() is 2), the same loop Lucene's own vectors writer runs over a graph. You expect level 1 to list no nodes, as level 0 of the same graph does and as HnswGraph.EMPTY does for every level. Instead getNodesOnLevel(1) (and getSortedNodes(1)) throws NullPointerException 'Cannot load from object array because "this.levelToNodes" is null', because the upper-level node cache is rebuilt only when size() differs from the size at its last build, both are 0 on a new graph, so the cache is never created.
Introduced: a8c52e2e19c4ca9bdf71cf476d69d36d3ca9ae52 (apache/lucene#12660 'Concurrent HNSW Merge', by zhaih; branch_9x cherry-pick 5fe48424a25dc5e3084beb02593484120adeabdf): it replaced the empty graph's 'numLevels = 1' with the placeholder entry node EntryNode(-1, 1), so an empty graph reports numLevels() == 2. That exposed the size-keyed upper-level cache (levelToNodes, null, and lastFreezeSize, 0, on a new graph) that #12651 ('Optimize OnHeapHnswGraph's data structure', a1cf22e6a94 on main, ba26abcaee9 on branch_9x, same author) had added 12 days earlier, when level 1 of an empty graph was still out of range [read: git log -S lastFreezeSize and git log -S 'new EntryNode(-1, 1)' in the full history clone each find only that commit; blame on main 5adff78bb168: :77 and :201 from a8c52e2e19c, :52-53 and :268-283 from a1cf22e6a94; exec: 9.9.0 with only the empty graph's entry level reverted to EntryNode(-1, 0) passes the test] (2023-10-28 (#12660: author date 2023-10-28T11:03:22-07:00, merged 2023-10-28T18:03:23Z; branch_9x commit 2023-10-28T11:11:40-07:00); the size-keyed cache of #12651 dates from 2023-10-16 (merged 2023-10-16T20:13:37Z))
First affected version: 9.9.0 [exec: the test, in a copy written against the 9.8-9.10 vector API, fails on 9.9.0 with the same NullPointerException at OnHeapHnswGraph.java:245 and passes on 9.8.0, where an empty graph has one level and there is no cache]; #12651 and #12660 both first shipped in 9.9.0, so no release has only one of them
Affected versions: 9.9.0 through 10.6.0 (released 2026-10-29, 4ae946e5a9b) and main 5adff78bb168 (12.0.0-SNAPSHOT); never fixed. [exec, JDK 25.0.3, Linux aarch64] main (-ea and -da: finder, the independent reproduction, the cross-model reviews, the intended-behaviour check, adjudication, registration check), 10.6.0 (-da: finder, the independent reproduction, the intended-behaviour check, history step; -ea: the intended-lens review's re-check), 10.5.2 (-da, the independent reproduction), 10.0.0 (-da, history step), 9.12.3 (-da, with a 9.x vector-API copy of the test, the independent reproduction and history step) and 9.9.0 (-da, history step; the independent reproduction through a same-package range check) all fail with the same NullPointerException (at OnHeapHnswGraph.java:276 on main, :269 on 10.6.0, :247 on 10.0.0, :270 on 9.12.3, :245 on 9.9.0); 9.8.0 passes. [read] every release tag from 9.9.0 to 10.6.0 contains both 'new EntryNode(-1, 1)' and 'lastFreezeSize == size()' in OnHeapHnswGraph.java, and git log -L shows no later change to the entry node, numLevels() or the cache key. Not new in 10.6 (10.5.2 and older releases fail). Not fixed upstream: upstream main 1c2072f0284 (:77, :281) and branch_10_6 (:77, :274) still have both lines; the newest commit on the file is #15590 (3b8a0cdbcc6 on main, author date 2026-02-26) [read: GitHub API, 2026-11-03].
Status: documented (brief, checks and a per-finding doc exist)
Verification: Confirmed by AI-run checks: an independent repro, a cross-model review that agreed, an intended-behaviour check, a prior-report search and a skeptical audit; not yet triaged by a person.
Found by: semi-formal: proof-obligation audit
Upstream and prior reports: none found (2026-11-03, on top of the finder's, the independent reproduction's, the intended-behaviour check's and the adjudication's searches; rechecked the same day): two scripted prior-report searches (51 queries each: GitHub issues and PRs, commits, downstream repositories, the dev@, java-user@, issues@ and commits@ lists, the JIRA archive and the web; 227 distinct hits together, none high, none a report), about 20 manual GitHub searches on apache/lucene ('getNodesOnLevel' with NullPointerException or empty, levelToNodes, lastFreezeSize, generateLevelToNodes, 'OnHeapHnswGraph' with NullPointerException or empty graph, the exception text, getSortedNodes, HnswGraphBuilder 'build(0)', HnswGraph.EMPTY, EntryNode, zero vectors), GitHub-wide and on Elasticsearch, OpenSearch, OpenSearch k-NN and Solr, the changed files of all 410 open apache/lucene PRs (OnHeapHnswGraph.java is touched only by #16815 and #13113, neither a fix), the 42 PRs updated since 2026-11-01, the file's commit history on main, branch_10_6 and branch_10x (author dates) and 3 web queries: no report of the empty graph's upper-level NullPointerException or of the size-only cache key. Re-check: 'levelToNodes' and 'getNodesOnLevel NullPointerException' return nothing; 'getNodesOnLevel empty graph', 'OnHeapHnswGraph empty' and '"empty graph" numLevels' return only the already-classified #16806, #15003, #12660, #12050 and #14963; no apache/lucene HNSW item was created since 2026-11-02; upstream main 1c2072f0284 and branch_10_6 still have the cache key and the placeholder entry node; #16815 is still open. Related history, not reports: #12651 (added the size-keyed cache), #12660 (made an empty graph report 2 levels), open PR #16815 (would move EntryNode(-1, 1) into a new base class and copy the same cache pattern into a new graph class).
Lucene commit tested: main 5adff78bb168 (2026-11-02) through gradle on 2026-11-03 in a scratch worktree, seed DEADBEEF: the repro without the fix (assertions on and off: fails) and with fix A (assertions off: passes; assertions on, with 5 closest suites: 132 tests, 0 failures), plus checkGoogleJavaFormat (passes). The same scenario ran on 9.8.0 (passes), 9.9.0 and 9.12.3 (with a copy for those releases' vector API), 10.0.0, 10.5.2 and 10.6.0 (fail). Upstream main 1c2072f0284 and branch_10_6 were read on 2026-11-03. Only Linux aarch64 with OpenJDK 25.0.3 was run.

Lucene and upstream sources

Finding record: lucene/core/src/java/org/apache/lucene/util/hnsw/OnHeapHnswGraph.java:48-53 (at 5adff78bb168) (levelToNodes, generated on demand; lastFreezeSize, default 0), :77 (constructor: entryNode = new EntryNode(-1, 1)), :199-202 (numLevels() = entryNode.level + 1, so 2 on an empty graph), :259-266 (getNodesOnLevel javadoc: the cache as a speed-up, 'only the first non-zero level call will pay the cost'; NOTE 'calling this method while the graph is still building is prohibited'), :267-278 (completeness check size() != maxNodeId() + 1 passes for 0 and -1; :276 levelToNodes[level], the throw), :280-304 (generateLevelToNodes: :281-283 'if (lastFreezeSize == size()) return;', fix site; :303 lastFreezeSize = size())
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraph.java:85-101 (at 5adff78bb168) (numLevels 'Returns the number of levels of the graph'; getNodesOnLevel 'Get all nodes on a given level'), :142-145 (HnswGraph.EMPTY: an empty iterator for every level), :148-160 (getSortedNodes calls getNodesOnLevel for level > 0); lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java:114-118 (public static create), :200-211 (build(maxOrd) returns getCompletedGraph()); lucene/core/src/java/org/apache/lucene/util/hnsw/HnswBuilder.java:24-37 (@lucene.experimental interface; build(maxOrd) 'Adds all nodes to the graph up to the provided maxOrd', no positive-only precondition)
lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99HnswVectorsWriter.java:316, (at 5adff78bb168) :453, :560-566, :623-631, :712-713, :880-887 (no graph is built for an empty field; writeGraph/writeMeta walk levels 0..numLevels()-1 with getNodesOnLevel/getSortedNodes; a null graph is written as 0 levels); lucene/core/src/test/org/apache/lucene/util/hnsw/TestOnHeapHnswGraph.java (testIncompleteGraphThrow relies on an entry-less graph reporting 2 levels)
Two Lucene main checkouts: git diff ea57360912ed 5adff78bb168 on OnHeapHnswGraph.java and HnswGraph.java is empty; HnswGraphBuilder.java differs only in the visited set of #16806 (2026-11-03)
https://github.com/apache/lucene/pull/12651, https://github.com/apache/lucene/pull/12660, https://github.com/apache/lucene/pull/16815, https://github.com/apache/lucene/pull/14963, https://github.com/apache/lucene/pull/16806, read 2026-11-03
The finding in 30 seconds: lucene/core/src/java/org/apache/lucene/util/hnsw/OnHeapHnswGraph.java:48-54, (at 5adff78bb168) :77, :199-202, :258-304
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraph.java:85-101, (at 5adff78bb168) :142-145, :148-159
Who is affected: lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99HnswVectorsWriter.java:453, (at 5adff78bb168) :560-566, :623-631, :712-713, :880-887
lucene/analysis/common/src/java/org/apache/lucene/analysis/synonym/word2vec/Word2VecSynonymProvider.java:60-67, (at 5adff78bb168) :83
a Lucene clone releases/lucene/9.12.0, 9.12.1, 10.0.0, 10.1.0: HnswGraphBuilder.java finish() calls connectComponents() (:407, :407, :416, :420); HnswUtil.java components() getNodesOnLevel(level + 1); Word2VecSynonymProvider.java:66 builder.build(word2VecModel.size()); Lucene99HnswVectorsWriter.java node > 0 and totalVectorCount() > 0 guards. Commented out in 9.12.2, 9.12.3, 10.2.0 to 10.6.0 and main (HnswGraphBuilder.java:587)
Why it looks unintended: lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraph.java:85-101, (at 5adff78bb168) :142-145
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswBuilder.java:25-37 (at 5adff78bb168)
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java:200-210, (at 5adff78bb168) :236-242, :583-589
lucene/core/src/java/org/apache/lucene/util/hnsw/OnHeapHnswGraph.java:258-278 (at 5adff78bb168)
lucene/core/src/java/module-info.java:50 (at 5adff78bb168)
lucene/core/src/test/org/apache/lucene/util/hnsw/TestOnHeapHnswGraph.java:37-44 (at 5adff78bb168)
a Lucene clone releases/lucene/9.8.0 OnHeapHnswGraph.java:57 ('this.numLevels = 1')
https://github.com/apache/lucene/pull/12651, https://github.com/apache/lucene/pull/12660
lucene/core/src/java/org/apache/lucene/codecs/hnsw/DefaultFlatVectorScorer.java:33 (at 5adff78bb168) (@lucene.experimental); lucene/core/src/java/org/apache/lucene/util/hnsw/package-info.java:19; HnswGraph.java:123-125 (EMPTY.numLevels() 0)
Suggested fix: https://github.com/apache/lucene/pull/16815
Prior reports: https://github.com/apache/lucene/pull/12651, https://github.com/apache/lucene/pull/12660, https://github.com/apache/lucene/pull/14963, https://github.com/apache/lucene/pull/16815
Diagrams: lucene/core/src/java/org/apache/lucene/util/hnsw/OnHeapHnswGraph.java:77, (at 5adff78bb168) :199-202, :267-304

Other statements trace to the hunt's working files (models, logs, reviews and briefs), which are not published.

Repro files

TestEmptyOnHeapGraphLevels.java (one JUnit test): repro/LFV-1234/TestEmptyOnHeapGraphLevels.java (38 lines)

About the diagrams

The diagram follows the repro's graph and the code at 5adff78bb168 (OnHeapHnswGraph.java:77, :199-202, :267-304).

assets/LFV-1234/bug.png (516 KB)

Built 2026-11-06 from the hunt's record of this finding and its doc file. Lucene main under test in this hunt: ea57360912ed. Every listed finding was re-run on Lucene main e1faeba08bde on 2026-11-02.

The finding in 30 seconds

Background: levels and the node-list cache

The finding, step by step

Who is affected

The mechanism (main 5adff78bb168, lucene/core/src/java/org/apache/lucene/util/hnsw/)

Minimal repro

Environment

Observed output

Why it looks unintended

Suggested fix

Rebuild when the cache is missing or has the wrong number of levels (fix A) (validated by the checks) (recommended)

Start lastFreezeSize at -1 (fix B) (validated by the checks)

Make an empty graph report fewer levels: EntryNode(-1, 0) (fix C) (validated by the checks)

Downstream note

How it was found

Prior reports, history and checks

Prior reports

History

Independent checks

Diagram file

Sources and provenance

Finding record

Lucene and upstream sources

Repro files

About the diagrams

The mechanism (main `5adff78bb168`, `lucene/core/src/java/org/apache/lucene/util/hnsw/`)