It's a new flavor of a recurrent problem; it's hard to test
probabilistic data structures since every now and then you get a wonky
case. I think we can make it more reliable by reducing the number of
requested vectors relative to the size of the test index. It's
currently:
int k = random().nextInt(size / 10 + 1) + 1; // size is maxdoc
if we make it divide by 50 instead of 10 that should help.
While I was looking I also happened to notice:
@Override
protected boolean mergeIsStable() {
// suppress this test from base class: merges for knn graphs are
not stable due to connected
// components
// logic
return false;
}
But I think we removed the "connected components logic" so perhaps we
can add back the stable merges checking?
On Fri, Jun 19, 2026 at 4:58 AM Dawid Weiss <[email protected]> wrote:
>
>
> This does reproduce for:
>
> gradlew :lucene:backward-codecs:test --tests
> "org.apache.lucene.backward_codecs.lucene99.TestLucene99HnswScalarQuantizedVectorsFormat.testRandomWithUpdatesAndGraph"
> -Ptests.asserts=true -Ptests.file.encoding=ISO-8859-1 -Ptests.gui=true
> -Ptests.haltonfailure=false -Ptests.jvmargs= -Ptests.jvms=5
> -Ptests.seed=23B608638D19F83 -Ptests.vectorsize=256
>
> I've ran claude/opus on this is here's what it says:
>
> This is not a correctness bug in the codec — it's an over-strict assertion
> colliding with approximate, filtered HNSW search:
>
> 1. The test (testRandomWithUpdatesAndGraph) re-adds documents under random
> ids drawn from [0, numDoc), so many docs get overwritten → lots of deleted
> docs in the segment.
> 2. The search runs with AcceptDocs.fromLiveDocs(liveDocs, …). In
> Lucene99HnswVectorsReader.search, since the graph is large enough relative to
> k, it takes the HNSW path (doHnsw
> == true), not the exhaustive fallback that would guarantee k.
> 3. In HnswGraphSearcher.search, the live-doc ratio matters
> (KnnSearchStrategy.Hnsw.useFilteredSearch): when fewer than 60% of docs pass
> the filter
> (DEFAULT_FILTERED_SEARCH_THRESHOLD = 60), it switches to
> FilteredHnswGraphSearcher (ACORN-1 style). The Lucene99 graph reports a known
> maxConn, so this path is eligible. With
> this seed's heavy deletions, the live ratio falls below 60% and the
> filtered searcher is used.
> 4. FilteredHnswGraphSearcher.searchLevel does bounded 1–2-hop exploration
> (maxExplorationMultiplier, minToScore, a capped visited bitset of
> ~log(graphSize)*k / filterRatio). Only
> accepted (live) ordinals become candidates; deleted nodes are only used for
> a single extra exploration hop. When the candidate queue drains before k live
> neighbors are
> collected, the loop at line 134 (while (candidates.size() > 0 …)) exits —
> legitimately returning fewer than k.
>
> I am not familiar with how hnsw searches run so I'd like somebody with more
> insight to take a look - even if the above analysis is right and it only
> requires test assertion relaxation.
>
> Dawid
>
>
> On Fri, Jun 19, 2026 at 10:47 AM Policeman Jenkins Server via builds
> <[email protected]> wrote:
>>
>> Build: https://jenkins.thetaphi.de/job/Lucene-main-Windows/19864/
>> Java: 64bit/hotspot/jdk-27-ea+23 -XX:+UseCompressedOops -XX:+UseParallelGC
>>
>> 3 tests failed.
>> FAILED:
>> org.apache.lucene.backward_codecs.lucene102.TestLucene102HnswBinaryQuantizedVectorsFormat.testRandomWithUpdatesAndGraph
>>
>> Error Message:
>> java.lang.AssertionError: expected:<5> but was:<2>
>>
>> Stack Trace:
>> java.lang.AssertionError: expected:<5> but was:<2>
>> at
>> __randomizedtesting.SeedInfo.seed([23B608638D19F83:7CE6A59B8FBA37E0]:0)
>> at
>> [email protected]/org.apache.lucene.tests.index.BaseKnnVectorsFormatTestCase.testRandomWithUpdatesAndGraph(BaseKnnVectorsFormatTestCase.java:1696)
>> at java.base/java.lang.reflect.Method.invoke(Method.java:583)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner.invoke(RandomizedRunner.java:1780)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$8.evaluate(RandomizedRunner.java:959)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$9.evaluate(RandomizedRunner.java:995)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$10.evaluate(RandomizedRunner.java:1009)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleSetupTeardownChained$1.evaluate(TestRuleSetupTeardownChained.java:48)
>> at
>> [email protected]/org.apache.lucene.tests.util.CallbacksToRuleAdapter$1.evaluate(CallbacksToRuleAdapter.java:35)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleThreadAndTestName$1.evaluate(TestRuleThreadAndTestName.java:45)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleIgnoreAfterMaxFailures$1.evaluate(TestRuleIgnoreAfterMaxFailures.java:60)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleMarkFailure$1.evaluate(TestRuleMarkFailure.java:47)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.StatementAdapter.evaluate(StatementAdapter.java:36)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.ThreadLeakControl$StatementRunner.run(ThreadLeakControl.java:390)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.ThreadLeakControl.forkTimeoutingTask(ThreadLeakControl.java:843)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.ThreadLeakControl$3.evaluate(ThreadLeakControl.java:490)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner.runSingleTest(RandomizedRunner.java:968)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$5.evaluate(RandomizedRunner.java:853)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$6.evaluate(RandomizedRunner.java:904)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$7.evaluate(RandomizedRunner.java:915)
>> at
>> [email protected]/org.apache.lucene.tests.util.CallbacksToRuleAdapter$1.evaluate(CallbacksToRuleAdapter.java:35)
>> at
>> [email protected]/org.apache.lucene.tests.util.CallbacksToRuleAdapter$1.evaluate(CallbacksToRuleAdapter.java:35)
>> at
>> [email protected]/org.apache.lucene.tests.util.CallbacksToRuleAdapter$1.evaluate(CallbacksToRuleAdapter.java:35)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.StatementAdapter.evaluate(StatementAdapter.java:36)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleStoreClassName$1.evaluate(TestRuleStoreClassName.java:38)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.NoShadowingOrOverridesOnMethodsRule$1.evaluate(NoShadowingOrOverridesOnMethodsRule.java:40)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.NoShadowingOrOverridesOnMethodsRule$1.evaluate(NoShadowingOrOverridesOnMethodsRule.java:40)
>> at
>> [email protected]/org.apache.lucene.tests.util.CallbacksToRuleAdapter$1.evaluate(CallbacksToRuleAdapter.java:35)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.StatementAdapter.evaluate(StatementAdapter.java:36)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleAssertionsRequired$1.evaluate(TestRuleAssertionsRequired.java:31)
>> at
>> [email protected]/org.apache.lucene.tests.util.AbstractBeforeAfterRule$1.evaluate(AbstractBeforeAfterRule.java:43)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleMarkFailure$1.evaluate(TestRuleMarkFailure.java:47)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleIgnoreAfterMaxFailures$1.evaluate(TestRuleIgnoreAfterMaxFailures.java:60)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.StatementAdapter.evaluate(StatementAdapter.java:36)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleIgnoreTestSuites$1.evaluate(TestRuleIgnoreTestSuites.java:47)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.StatementAdapter.evaluate(StatementAdapter.java:36)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.ThreadLeakControl$StatementRunner.run(ThreadLeakControl.java:390)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.ThreadLeakControl.lambda$forkTimeoutingTask$0(ThreadLeakControl.java:850)
>> at java.base/java.lang.Thread.run(Thread.java:1527)
>>
>>
>> FAILED:
>> org.apache.lucene.backward_codecs.lucene95.TestLucene95HnswVectorsFormat.testRandomWithUpdatesAndGraph
>>
>> Error Message:
>> java.lang.AssertionError: expected:<5> but was:<2>
>>
>> Stack Trace:
>> java.lang.AssertionError: expected:<5> but was:<2>
>> at
>> __randomizedtesting.SeedInfo.seed([23B608638D19F83:7CE6A59B8FBA37E0]:0)
>> at
>> [email protected]/org.apache.lucene.tests.index.BaseKnnVectorsFormatTestCase.testRandomWithUpdatesAndGraph(BaseKnnVectorsFormatTestCase.java:1696)
>> at java.base/java.lang.reflect.Method.invoke(Method.java:583)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner.invoke(RandomizedRunner.java:1780)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$8.evaluate(RandomizedRunner.java:959)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$9.evaluate(RandomizedRunner.java:995)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$10.evaluate(RandomizedRunner.java:1009)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleSetupTeardownChained$1.evaluate(TestRuleSetupTeardownChained.java:48)
>> at
>> [email protected]/org.apache.lucene.tests.util.CallbacksToRuleAdapter$1.evaluate(CallbacksToRuleAdapter.java:35)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleThreadAndTestName$1.evaluate(TestRuleThreadAndTestName.java:45)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleIgnoreAfterMaxFailures$1.evaluate(TestRuleIgnoreAfterMaxFailures.java:60)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleMarkFailure$1.evaluate(TestRuleMarkFailure.java:47)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.StatementAdapter.evaluate(StatementAdapter.java:36)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.ThreadLeakControl$StatementRunner.run(ThreadLeakControl.java:390)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.ThreadLeakControl.forkTimeoutingTask(ThreadLeakControl.java:843)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.ThreadLeakControl$3.evaluate(ThreadLeakControl.java:490)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner.runSingleTest(RandomizedRunner.java:968)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$5.evaluate(RandomizedRunner.java:853)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$6.evaluate(RandomizedRunner.java:904)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$7.evaluate(RandomizedRunner.java:915)
>> at
>> [email protected]/org.apache.lucene.tests.util.CallbacksToRuleAdapter$1.evaluate(CallbacksToRuleAdapter.java:35)
>> at
>> [email protected]/org.apache.lucene.tests.util.CallbacksToRuleAdapter$1.evaluate(CallbacksToRuleAdapter.java:35)
>> at
>> [email protected]/org.apache.lucene.tests.util.CallbacksToRuleAdapter$1.evaluate(CallbacksToRuleAdapter.java:35)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.StatementAdapter.evaluate(StatementAdapter.java:36)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleStoreClassName$1.evaluate(TestRuleStoreClassName.java:38)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.NoShadowingOrOverridesOnMethodsRule$1.evaluate(NoShadowingOrOverridesOnMethodsRule.java:40)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.NoShadowingOrOverridesOnMethodsRule$1.evaluate(NoShadowingOrOverridesOnMethodsRule.java:40)
>> at
>> [email protected]/org.apache.lucene.tests.util.CallbacksToRuleAdapter$1.evaluate(CallbacksToRuleAdapter.java:35)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.StatementAdapter.evaluate(StatementAdapter.java:36)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleAssertionsRequired$1.evaluate(TestRuleAssertionsRequired.java:31)
>> at
>> [email protected]/org.apache.lucene.tests.util.AbstractBeforeAfterRule$1.evaluate(AbstractBeforeAfterRule.java:43)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleMarkFailure$1.evaluate(TestRuleMarkFailure.java:47)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleIgnoreAfterMaxFailures$1.evaluate(TestRuleIgnoreAfterMaxFailures.java:60)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.StatementAdapter.evaluate(StatementAdapter.java:36)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleIgnoreTestSuites$1.evaluate(TestRuleIgnoreTestSuites.java:47)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.StatementAdapter.evaluate(StatementAdapter.java:36)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.ThreadLeakControl$StatementRunner.run(ThreadLeakControl.java:390)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.ThreadLeakControl.lambda$forkTimeoutingTask$0(ThreadLeakControl.java:850)
>> at java.base/java.lang.Thread.run(Thread.java:1527)
>>
>>
>> FAILED:
>> org.apache.lucene.backward_codecs.lucene99.TestLucene99HnswScalarQuantizedVectorsFormat.testRandomWithUpdatesAndGraph
>>
>> Error Message:
>> java.lang.AssertionError: expected:<5> but was:<2>
>>
>> Stack Trace:
>> java.lang.AssertionError: expected:<5> but was:<2>
>> at
>> __randomizedtesting.SeedInfo.seed([23B608638D19F83:7CE6A59B8FBA37E0]:0)
>> at
>> [email protected]/org.apache.lucene.tests.index.BaseKnnVectorsFormatTestCase.testRandomWithUpdatesAndGraph(BaseKnnVectorsFormatTestCase.java:1696)
>> at java.base/java.lang.reflect.Method.invoke(Method.java:583)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner.invoke(RandomizedRunner.java:1780)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$8.evaluate(RandomizedRunner.java:959)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$9.evaluate(RandomizedRunner.java:995)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$10.evaluate(RandomizedRunner.java:1009)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleSetupTeardownChained$1.evaluate(TestRuleSetupTeardownChained.java:48)
>> at
>> [email protected]/org.apache.lucene.tests.util.CallbacksToRuleAdapter$1.evaluate(CallbacksToRuleAdapter.java:35)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleThreadAndTestName$1.evaluate(TestRuleThreadAndTestName.java:45)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleIgnoreAfterMaxFailures$1.evaluate(TestRuleIgnoreAfterMaxFailures.java:60)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleMarkFailure$1.evaluate(TestRuleMarkFailure.java:47)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.StatementAdapter.evaluate(StatementAdapter.java:36)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.ThreadLeakControl$StatementRunner.run(ThreadLeakControl.java:390)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.ThreadLeakControl.forkTimeoutingTask(ThreadLeakControl.java:843)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.ThreadLeakControl$3.evaluate(ThreadLeakControl.java:490)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner.runSingleTest(RandomizedRunner.java:968)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$5.evaluate(RandomizedRunner.java:853)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$6.evaluate(RandomizedRunner.java:904)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.RandomizedRunner$7.evaluate(RandomizedRunner.java:915)
>> at
>> [email protected]/org.apache.lucene.tests.util.CallbacksToRuleAdapter$1.evaluate(CallbacksToRuleAdapter.java:35)
>> at
>> [email protected]/org.apache.lucene.tests.util.CallbacksToRuleAdapter$1.evaluate(CallbacksToRuleAdapter.java:35)
>> at
>> [email protected]/org.apache.lucene.tests.util.CallbacksToRuleAdapter$1.evaluate(CallbacksToRuleAdapter.java:35)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.StatementAdapter.evaluate(StatementAdapter.java:36)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleStoreClassName$1.evaluate(TestRuleStoreClassName.java:38)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.NoShadowingOrOverridesOnMethodsRule$1.evaluate(NoShadowingOrOverridesOnMethodsRule.java:40)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.NoShadowingOrOverridesOnMethodsRule$1.evaluate(NoShadowingOrOverridesOnMethodsRule.java:40)
>> at
>> [email protected]/org.apache.lucene.tests.util.CallbacksToRuleAdapter$1.evaluate(CallbacksToRuleAdapter.java:35)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.StatementAdapter.evaluate(StatementAdapter.java:36)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleAssertionsRequired$1.evaluate(TestRuleAssertionsRequired.java:31)
>> at
>> [email protected]/org.apache.lucene.tests.util.AbstractBeforeAfterRule$1.evaluate(AbstractBeforeAfterRule.java:43)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleMarkFailure$1.evaluate(TestRuleMarkFailure.java:47)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleIgnoreAfterMaxFailures$1.evaluate(TestRuleIgnoreAfterMaxFailures.java:60)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.StatementAdapter.evaluate(StatementAdapter.java:36)
>> at
>> [email protected]/org.apache.lucene.tests.util.TestRuleIgnoreTestSuites$1.evaluate(TestRuleIgnoreTestSuites.java:47)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.rules.StatementAdapter.evaluate(StatementAdapter.java:36)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.ThreadLeakControl$StatementRunner.run(ThreadLeakControl.java:390)
>> at
>> [email protected]/com.carrotsearch.randomizedtesting.ThreadLeakControl.lambda$forkTimeoutingTask$0(ThreadLeakControl.java:850)
>> at java.base/java.lang.Thread.run(Thread.java:1527)
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: [email protected]
>> For additional commands, e-mail: [email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
