TestHnswFloatVectorGraph.testBuildingJoinSet failure

[vsop-479]

Description

TestHnswFloatVectorGraph > testBuildingJoinSet FAILED
java.lang.AssertionError: Join set size [111] is not less than graph size [111]

Gradle command to reproduce

gradlew :lucene:core:test --tests "org.apache.lucene.util.hnsw.TestHnswFloatVectorGraph.testBuildingJoinSet" -Ptests.asserts=false -Ptests.file.encoding=ISO-8859-1 -Ptests.gui=true -Ptests.jvmargs= -Ptests.jvms=4 -Ptests.seed=8B08865AA8BAB759 -Ptests.vectorsize=128

[venkateshwaracholan]

@vsop-479 dug into this a bit further and was able to reproduce the behavior outside of the failing HNSW seed.

Using the reported seed (8B08865AA8BAB759:E27CE1241E7C9A82), the generated graph has 111 nodes, with most nodes having degree 1 and two high-degree hubs (58 and 53). computeJoinSet() returns all 111 nodes and stops because gTot >= gExit.

To understand whether this was specific to the seed or HNSW construction, I built a few graphs manually with OnHeapHnswGraph and traced computeJoinSet(). In particular, simple hub-and-spoke graphs (one hub with many degree-1 leaves) also produce joinSet == graph, even without random vectors or HNSW graph construction.

Smallest handcrafted case I found is a 3-node hub-and-spoke graph (hub + 2 leaves). The trace is attached, but the short version is:

• gExit = 6
• hub contributes gain = 4
• both leaves become stale and are re-evaluated with gain = 1
• the algorithm reaches gTot >= gExit only after selecting all three nodes

Result: joinSet = 3/3.

By contrast, graphs with more overlap (e.g. two hubs with shared leaves) produce much smaller join sets.

From the traces, it looks like computeJoinSet() is optimizing for reaching the coverage budget (gExit) rather than minimizing join-set size. On hub-and-spoke topologies, the hubs contribute a large initial gain, but after stale recalculation the leaves contribute only 1 each, so the algorithm ends up selecting nearly every node in order to reach gExit.

This makes me wonder whether the failing seed is exposing a graph topology where joinSet == graph is expected behavior of the current heuristic, rather than a merge correctness issue. The test currently asserts j.size() < graph.size(), but I couldn't find a corresponding guarantee in computeJoinSet() itself.

Curious what the intended behavior is here. Should the test be relaxed, or is a full join set considered a bug in the heuristic?

joinset-handcrafted-3node.log

[benchaplin]

We saw a few more of these failures:

TestHnswByteVectorGraph > testBuildingJoinSet FAILED
--
  | java.lang.AssertionError: Join set size [111] is not less than graph size [111]
  | at __randomizedtesting.SeedInfo.seed([1A7B4702F1314EA5:730F207C47F7637E]:0)
  | at org.junit.Assert.fail(Assert.java:89)
  | at org.junit.Assert.assertTrue(Assert.java:42)
  | at org.apache.lucene.util.hnsw.HnswGraphTestCase.testBuildingJoinSet(HnswGraphTestCase.java:610)
  | at org.apache.lucene.util.hnsw.TestHnswByteVectorGraph.testBuildingJoinSet(TestHnswByteVectorGraph.java:35)


NOTE: reproduce with: gradlew test --tests TestHnswByteVectorGraph.testBuildingJoinSet -Dtests.seed=1A7B4702F1314EA5 -Dtests.locale=kgp -Dtests.timezone=Etc/GMT-7 -Dtests.asserts=true -Dtests.file.encoding=UTF-8
NOTE: test environment is: codec=Asserting(Lucene104): {}, knn_vectors:{}, docValues:{}, maxPointsInLeafNode=597, maxMBSortInHeap=5.310574189919605, sim=Asserting(RandomSimilarity(queryNorm=false): {}), locale=kgp, timezone=Etc/GMT-7

TestHnswFloatVectorGraph > testBuildingJoinSet FAILED
--
  | java.lang.AssertionError: Join set size [111] is not less than graph size [111]
  | at __randomizedtesting.SeedInfo.seed([1A7B4702F1314EA5:730F207C47F7637E]:0)
  | at org.junit.Assert.fail(Assert.java:89)
  | at org.junit.Assert.assertTrue(Assert.java:42)
  | at org.apache.lucene.util.hnsw.HnswGraphTestCase.testBuildingJoinSet(HnswGraphTestCase.java:610)
  | at org.apache.lucene.util.hnsw.TestHnswFloatVectorGraph.testBuildingJoinSet(TestHnswFloatVectorGraph.java:39)


NOTE: reproduce with: gradlew test --tests TestHnswFloatVectorGraph.testBuildingJoinSet -Dtests.seed=1A7B4702F1314EA5 -Dtests.locale=ms-SG -Dtests.timezone=America/Port-au-Prince -Dtests.asserts=true -Dtests.file.encoding=UTF-8
overlap=1.0 totalMatches=500
NOTE: test environment is: codec=Asserting(Lucene104): {}, knn_vectors:{}, docValues:{}, maxPointsInLeafNode=1586, maxMBSortInHeap=7.950179431534489, sim=Asserting(RandomSimilarity(queryNorm=false): {}), locale=ms-SG, timezone=America/Port-au-Prince

[vsop-479]

Thanks @venkateshwaracholan -- matches what I found independently on the original failing seed (111-node graph): two hubs (gain 73/65) satisfy half of each leaf's coverage quota k, but with little overlap between leaves, nothing else can supply the second unit, so every leaf is eventually forced to self-select. Heap drains fully, gTot exactly hits gExit. Your hand-built hub-and-spoke case confirms this is topology-driven, not seed- or HNSW-specific.

computeJoinSet() is optimizing to satisfy a coverage budget, not to minimize the join set size, and there's no guarantee in the method itself that joinSetSize < graphSize -- it only holds incidentally when there's enough overlap between low-degree nodes. Sparse/hub-and-spoke regions break it, and these could plausibly show up in real merges too, not just this test seed.

@mayya-sharipova -- could you weigh in on intended behavior here? Should the test assertion be relaxed (< → <=), or is forcing joinSetSize < graphSize actually load-bearing for merge quality, in which case the k threshold for low-degree nodes might need adjusting instead?

[mayya-sharipova]

Thanks for looking into this issue everyone.
I've created a fix for it: #16435