HNSW graph reuse at merge can leave the entry node with no neighbours

When a merge reuses a segment's HNSW graph that has deletions, the node every search starts from can end up with no links at all. kNN search on the merged segment then returns about one hit, the entry itself: recall@10 drops from 0.906 to 0.000 in the repro, the damage survives commit, reopen and later merges, and CheckIndex reports the index clean. It ships in 10.5.1 and 10.5.2 with the default codec.

• HNSW graph: Lucene's index for kNN vector search. Each vector is a node with a number, its ord, and links to a few nearby nodes, its neighbours. A search only follows a node's own outgoing links. Level 0 holds every node; each higher level holds a random, shrinking subset (about 1 in 16 per level with the default M = 16).
• Entry node: the top-level node where every search starts. The search walks along links towards the query, then drops a level. If the entry has no links, the search cannot go anywhere. On disk, the reader always uses the lowest-ord node of the top level.
• Merge-time graph reuse: a merge can start from an existing segment's graph instead of building one from scratch. Reuse of graphs without deletions dates from 9.6.0; #15003 (10.4.0) added reuse of a graph with deletions: copy it without the deleted nodes and their links, repair nodes that lost neighbours, rebalance levels that became too small, then insert the other segments' vectors.

1. While the graph is copied, the first surviving top-level node becomes the entry (InitializedHnswGraphBuilder.java:363 on main, hnsw.trySetNewEntryNode(newOrd, level)). Nobody checks how many neighbours it kept.
2. If the deletes removed all its neighbours on a level, the node is flagged for repair, and a node with no neighbours goes to addConnections ("Node has no neighbors, add connections from scratch", HnswGraphBuilder.java:757-759).
3. addConnections seeds its search with the entry node, int[] eps = {hnsw.entryNode()}; (HnswGraphBuilder.java:789), and the entry is the node itself. The search has no links to follow, so its only candidate is the node, and that candidate is skipped because a node may not link to itself (if (node == cNode) continue;, :510). The node keeps 0 neighbours. Rebalancing seeds its own addConnections calls the same way, and in the repro it promotes nothing.
4. Searches start at this node (on disk too, unless rebalancing promotes a lower ord onto the top level) and return only it, or only what is linked to it. Vectors inserted later, by this merge or a later one, are also placed by searching from it, so they attach only to it and to each other: an island.

Default codec, 1,450 documents, 16 dimensions, 31 documents deleted (2.1%), forceMerge(1): KnnFloatVectorQuery(k=10) returns 1 hit, the entry doc 171, far from every query, and recall@10 goes from 0.906 to 0.000. After 200 more documents and a second forceMerge(1), reopened from the directory, recall is 0.106 and queries return only new documents. The fix gives 0.906, then 0.912. On main, CheckIndex at level 2 or higher prints level 0: 1419 nodes, 1/1419 connected and then "No problems were detected".

• Who is exposed. Default-codec users on 10.5.1, 10.5.2, branch_10_6 and main whose merges reuse a graph with deletions: a singleton forceMerge(1), forceMergeDeletes(), or ordinary background merges (with the default TieredMergePolicy and ConcurrentMergeScheduler, deleting a cluster and then making 40 commits of 20 documents gave recall 0.386). 10.4.0 and 10.5.0 are affected only with a codec whose vectors format is not wrapped per field. The opt-in concurrent merger fails the same way.
• Silent and lasting. No error, CheckIndex clean, and the damage survives commit, reopen and later merges, growing into an island of later vectors.
• What it takes. Deletes that remove the links of the first (lowest-ord) surviving top-level node: all links give the full collapse, all upper-level links can be enough. In practice that means deletes clustered around that node (for example a delete-by-query on a tenant, topic or time range whose embeddings sit together), or an entry with very few links. And rebalancing must promote no node onto its levels, which happens in narrow, size-dependent windows.
• How likely. A well-connected entry is effectively safe from random deletes: on 20,000 real Cohere vectors the entry had 32/16/12/1 links on levels 0-3. An independent tenant-shaped repro (5 tenants on an arc, delete-by-query of a 13-14% tenant, 32-dimensional DOT_PRODUCT) collapsed from 0.932 to 0.000.
• Partial form on real data. When rebalancing promotes a lower ord, the on-disk entry moves there and the bad node stays a level-0 dead end: on the first 20k Cohere v3 vectors, deleting exactly the entry's 57 neighbours (0.29%) left 7 of 100 queries with fewer than 10 hits and recall 0.853 to 0.785; the fix gives 0 of 100.
• Release behaviour can vary. In 10.4.0-10.5.x, rebalanceGraph uses an unseeded random, so results can differ between runs whenever rebalancing promotes nodes.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: kNN hits among 1419 live docs expected:<10> but was:<1>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:647)
       org.apache.lucene.index.TestHnswMergeReuseIsolatedEntry.testForceMergeAfterDeletingAllNeighboursOfEntryNode(TestHnswMergeReuseIsolatedEntry.java:60)

• The code handles this exact case on purpose. fixDisconnectedNodes sends a node with zero neighbours to addConnections with the comment "Node has no neighbors, add connections from scratch" (main HnswGraphBuilder.java:757-759; there since #15003, spelled "nighbors" in 10.5.2 InitializedHnswGraphBuilder.java:344-346). #16627 (main and branch_10_6) rewrote the javadoc to "A node with no neighbors is instead connected from scratch via addConnections".
• The class javadoc says the builder "Identifies and repairs disconnected nodes".
• Tests in TestHnswFloatVectorGraph assert the goal: "flagged node ... has no neighbors after repair on level" must not happen, "graph should be a single rooted component after repair", and "KNN search should return k results" (10). Their deletes are not clustered in vector space (every third ord, or the first N doc ids, over random vectors).
• #16627's PR body assumes the node is not the entry: "nodes with no surviving neighbors have no entry point to search from, so it walks from the entry node to reach the current level".
• Effect size. 2.1% deletes, far below the 40% reuse limit, turn recall 0.906 into 0.000 and k = 10 into 1 hit. The same data rebuilt from scratch (10.4.0, 10.5.0) gives 0.910. That is not an approximation trade-off.
• Precedent. #16552, a recall loss from graph reuse, was filed as type:bug and fixed in 10.5.2.

The intended-behaviour checker built the strongest case for "known limitation": in 10.4.0 through 10.5.2 the private fixDisconnectedNodes javadoc says "If a node has no neighbors at all, it cannot be repaired at this level and will rely on the rebalancing phase", and in the failing window rebalancing promotes nothing; connectivity is best effort (connectComponents() is commented out because of #14214, and CheckIndex treats connectedness as information only); reuse past 40% deletes "may have degraded connectivity"; and the repro geometry is artificial.

Why it fails: the code right under that javadoc does try to connect the node from scratch, and the method is private, so users never see the sentence; rebalancing cannot do the repair either (same seed, nothing promoted); the tests and the PR body state the goal; the effect is far beyond a trade-off. Verdict: not intended, a defect. Not security: correct use of public APIs, and accepted-docs filtering still applies.

One fix sketch was built and checked; it has a known gap. The alternatives come from the brief and the checkers.

Branches hnsw-entry-node-isolation-main-fix (3bd0c584d88) and -106-fix (3108980e63e), each one commit on its test commit, +27/-2 in HnswGraphBuilder.java. Inside addConnections, when hnsw.entryNode() is the node itself, it seeds from every other node of the highest level that has any (otherNodesOnLevel); if the node is alone on the target level it returns.

int startLevel = hnsw.numLevels() - 1;
int[] eps = {hnsw.entryNode()};
if (eps[0] == node) {
  // seed from all other nodes of the highest level that has any
  eps = otherNodesOnLevel(node, startLevel);
  while (eps.length == 0 && startLevel > targetLevel) {
    eps = otherNodesOnLevel(node, --startLevel);
  }
  if (eps.length == 0) {
    return; // the node is alone on the target level
  }
}

Trade-offs

• Known gap in the serial merger (hand-built graphs): if another node W with a lower ord also lost all its level-0 links, W is repaired first, its descent ends on the outlier entry X (the descent keeps the worst candidate), so W links only to X; X then has one neighbour and is repaired from W only. On the fix: level 0 reachable from the entry 2/196, a query near the entry gets 2 hits. The same on unfixed main, so a remaining gap, not a regression.
• Changing the descent to "take the best" lands on the node itself and re-breaks the repair; any change there must take the best candidate other than the node.
• Cost: only when the node is the entry; worst case one O(n) brute-force pass, and the searcher's scratch arrays stay grown to n.
• The 10.5.x backport needs a different patch (addConnections is private in InitializedHnswGraphBuilder there). No recall or latency benchmark was run; open PR #16815 changes the same code.

What the checks validated

• main-fix: the 2 tests pass (20/20 with iters=10, 10/10 with iters=5, and with assertions off); util.hnsw.*, codecs.lucene99.*, TestKnnGraph, TestHnswMergeAbort and TestKnnFloatVectorQuery: 19 classes, 382 tests, 0 failures; codecs.*, search.*Knn*, *Vector* and TestCheckIndex: 92 classes, 2,088 tests, 0 failures; :lucene:core:check -x test passes; CheckIndex prints 5/5, 101/102 and 1419/1419 connected.
• 106-fix: the 2 tests pass; 18 classes, 357 tests, 0 failures.
• The independent repros, the natural-merge probe and the Cohere probes are fixed too.

Choose a top-level node that kept neighbours as the entry.

Trade-offs

Does not work on its own: the format does not store the entry, and the reader uses the lowest-ord top-level node (Lucene99HnswVectorsReader.java:572 on main b83101cdd2, :578 on ea57360912ed), which stays the isolated one unless it is repaired or the reader rule changes.

A targeted second pass.

Trade-offs

Misses the serial-merger gap above, where the entry ends with exactly one neighbour.

Suggested by a checker; untested.

Trade-offs

Touches the descent too, so it needs benchmarks; fixes for a related descent issue lowered recall before.

Main's CheckIndex already computes 1/1419 connected but does not flag it; it could.

Trade-offs

Reports the damage instead of preventing it.

Method: TLA+ model checking (TLC) of the concurrent HNSW build, merge and repair (the study's "formal" tier: the tool's own counterexample). Run 3, experiment "hnsw-concurrent-merge" (2026-10-22, main 7cecf79523).

• The task text for this area asked for a P or TLA+ model that treats "the shared graph and entry point faithfully", with properties such as "every inserted node is linked at all its levels". It named the merge and repair classes and the entry node in general, and did not mention deletes, repair of a node with no neighbours, or this case.
• An AI modeller read the code and wrote a TLA+ model of the concurrent HNSW build, merge and repair (HnswConc.tla, 555 lines), with the invariant RepairLinked: a repaired node has at least one neighbour wherever another node exists on its level.
• It hand-picked the start state of configuration R1: 4 nodes on one level, where entry node 0 has already lost all its neighbours. TLC explored that configuration completely (18 distinct states, 0 left on the queue) in 1 s and reported the RepairLinked violation with a 9-state trace (2026-10-22). So the AI tool chose the scenario, and TLC showed that the repair cannot fix it; it is not a blind discovery.
• The same AI tool wrote small Java repros (14 vectors). A separate AI verifier, which had read the finder's write-up but not its test code (self-reported), wrote its own end-to-end repro with the default codec and 1,450 documents, ran it on 10.5.2 and main, and scanned segment sizes. On 2026-10-23 a third AI tool found that 10.4.0 and 10.5.0 do not reproduce with the default codec, and wrote the JUnit tests, the plain-Java repro and the fix sketch.