Describe the bug
GPUKnnFloatVectorQuery overrides rewrite() and routes multi-segment queries through its own multi-partition CAGRA path. That path never consults the filter's cardinality, so it bypasses Lucene's exact-search fallback for highly selective filters.
Lucene's AbstractKnnVectorQuery intentionally falls back to exactSearch() when a filter leaves few enough candidates relative to k, so a sufficiently selective filter is guaranteed to return its matching documents. The GPU path instead runs an approximate CAGRA search, which can legitimately miss those candidates and return fewer hits than expected.
This surfaces today as an intermittent failure in the existing TestCuVSGaps.testVectorSearchWithFilterAndAlternatingDocuments:
java.lang.AssertionError: Should return exactly 1 result expected:<1> but was:<0>
The test filters to exactly one document (id=8) and queries with an unrelated vector (dataset[0]). Under Lucene's contract that must return document 8; under approximate search it may not. datasetSize, dimension and topK are all seed-randomized, so it only reproduces on some seeds, which is why it has not shown up consistently.
Note that there is nothing special about a single matching document here. A filter matching 2, or any number of candidates up to k, has the same failure mode, and it applies to multi-segment indexes as well.
Steps/Code to reproduce bug
cd java/cuvs-lucene
mvn test -Dtest=TestCuVSGaps -Dtests.seed=8D88CBDC65B02C93
On a machine with a supported GPU this fails deterministically for that seed. Other seeds pass.
Confirmed reproducing on a clean checkout of main (9c9d359) with no other changes applied, so this is independent of any in-flight PR.
A second seed, E959E678C7574BA7, reproduces the same failure and was confirmed the same way: with the single-segment guard below the seed passes, without it it fails. Both seeds were observed in real CI runs rather than constructed.
That the miss is caused by the rewrite path (and not by the test) can be confirmed by adding an early return super.rewrite(indexSearcher); for the single-segment case: with that guard the seed passes, without it the same expected:<1> but was:<0> failure reproduces every run.
Expected behavior
A filter selective enough that Lucene would switch to exact search should return its matching documents, matching AbstractKnnVectorQuery's behavior. The GPU path should not silently weaken that guarantee.
Possible approaches
The general condition is the one Lucene already applies: when the filter leaves few enough candidates relative to k, the search needs to be exact. A complete fix likely means evaluating the filter's cardinality against k in rewrite() and routing to Lucene's exact path whenever the filter is selective enough, regardless of segment count.
For reference, a much narrower change -- skipping the multi-partition path when the index has a single segment -- is enough to make the failing seed above pass:
if (leaves.size() == 1) {
return super.rewrite(indexSearcher);
}This only defers to Lucene for single-segment indexes and leaves the multi-segment case unaddressed, so it is a workaround for the observed symptom rather than a fix for the underlying problem.
Worth noting when deciding the threshold: Lucene's exact fallback (AbstractKnnVectorQuery.exactSearch) is a CPU brute-force scan over the flat vector values. GPUKnnFloatVectorQuery only overrides approximateSearch, so routing selective filters to the exact path trades GPU execution for exactness on those queries.
Environment details (please complete the following information):
- Environment location: Bare-metal
- Method of cuVS install: from source (branch-26.10)
Additional context
Frequency, measured across 36 completed conda-lucene-build-and-tests jobs in recent CI runs: TestCuVSGaps failed 5 times, or 13.9% per job. Each full run executes the class twice (cu12 and cu13), which works out to roughly 26% of runs hitting it. Observed on PRs #2249, #2429, #2438, #2481 and #2520, so it is not specific to any one change.
Worth noting those 5 failures are not all the same thing. Four are the filtered case described above. The fifth, on #2520, is TestCuVSGaps.testVectorSearchWithAlternatingDocuments failing with Should return exactly 63 results expected:<63> but was:<52>. That test passes filter = null, so the exact-search fallback is not involved. It asks for topK results with itopk_size = topK and search_width = 1 and then asserts it gets exactly topK back, which is asking for perfect recall from an approximate search on a tight budget. That may be a separate problem, and possibly a test-expectation issue rather than a code one, but it shares this class and shows up in the same runs.
Found while investigating a CI failure on #2515. That PR does not touch this code path, and the fix has been kept out of it so this can be handled separately.
Relevant code: java/cuvs-lucene/src/main/java/com/nvidia/cuvs/lucene/GPUKnnFloatVectorQuery.java (rewrite(), around lines 132-160) and java/cuvs-lucene/src/test/java/com/nvidia/cuvs/lucene/TestCuVSGaps.java (around line 146).
Describe the bug
GPUKnnFloatVectorQueryoverridesrewrite()and routes multi-segment queries through its own multi-partition CAGRA path. That path never consults the filter's cardinality, so it bypasses Lucene's exact-search fallback for highly selective filters.Lucene's
AbstractKnnVectorQueryintentionally falls back toexactSearch()when a filter leaves few enough candidates relative tok, so a sufficiently selective filter is guaranteed to return its matching documents. The GPU path instead runs an approximate CAGRA search, which can legitimately miss those candidates and return fewer hits than expected.This surfaces today as an intermittent failure in the existing
TestCuVSGaps.testVectorSearchWithFilterAndAlternatingDocuments:The test filters to exactly one document (
id=8) and queries with an unrelated vector (dataset[0]). Under Lucene's contract that must return document 8; under approximate search it may not.datasetSize,dimensionandtopKare all seed-randomized, so it only reproduces on some seeds, which is why it has not shown up consistently.Note that there is nothing special about a single matching document here. A filter matching 2, or any number of candidates up to
k, has the same failure mode, and it applies to multi-segment indexes as well.Steps/Code to reproduce bug
On a machine with a supported GPU this fails deterministically for that seed. Other seeds pass.
Confirmed reproducing on a clean checkout of
main(9c9d359) with no other changes applied, so this is independent of any in-flight PR.A second seed,
E959E678C7574BA7, reproduces the same failure and was confirmed the same way: with the single-segment guard below the seed passes, without it it fails. Both seeds were observed in real CI runs rather than constructed.That the miss is caused by the rewrite path (and not by the test) can be confirmed by adding an early
return super.rewrite(indexSearcher);for the single-segment case: with that guard the seed passes, without it the sameexpected:<1> but was:<0>failure reproduces every run.Expected behavior
A filter selective enough that Lucene would switch to exact search should return its matching documents, matching
AbstractKnnVectorQuery's behavior. The GPU path should not silently weaken that guarantee.Possible approaches
The general condition is the one Lucene already applies: when the filter leaves few enough candidates relative to
k, the search needs to be exact. A complete fix likely means evaluating the filter's cardinality againstkinrewrite()and routing to Lucene's exact path whenever the filter is selective enough, regardless of segment count.For reference, a much narrower change -- skipping the multi-partition path when the index has a single segment -- is enough to make the failing seed above pass:
This only defers to Lucene for single-segment indexes and leaves the multi-segment case unaddressed, so it is a workaround for the observed symptom rather than a fix for the underlying problem.
Worth noting when deciding the threshold: Lucene's exact fallback (
AbstractKnnVectorQuery.exactSearch) is a CPU brute-force scan over the flat vector values.GPUKnnFloatVectorQueryonly overridesapproximateSearch, so routing selective filters to the exact path trades GPU execution for exactness on those queries.Environment details (please complete the following information):
Additional context
Frequency, measured across 36 completed
conda-lucene-build-and-testsjobs in recent CI runs:TestCuVSGapsfailed 5 times, or 13.9% per job. Each full run executes the class twice (cu12 and cu13), which works out to roughly 26% of runs hitting it. Observed on PRs #2249, #2429, #2438, #2481 and #2520, so it is not specific to any one change.Worth noting those 5 failures are not all the same thing. Four are the filtered case described above. The fifth, on #2520, is
TestCuVSGaps.testVectorSearchWithAlternatingDocumentsfailing withShould return exactly 63 results expected:<63> but was:<52>. That test passesfilter = null, so the exact-search fallback is not involved. It asks fortopKresults withitopk_size = topKandsearch_width = 1and then asserts it gets exactlytopKback, which is asking for perfect recall from an approximate search on a tight budget. That may be a separate problem, and possibly a test-expectation issue rather than a code one, but it shares this class and shows up in the same runs.Found while investigating a CI failure on #2515. That PR does not touch this code path, and the fix has been kept out of it so this can be handled separately.
Relevant code:
java/cuvs-lucene/src/main/java/com/nvidia/cuvs/lucene/GPUKnnFloatVectorQuery.java(rewrite(), around lines 132-160) andjava/cuvs-lucene/src/test/java/com/nvidia/cuvs/lucene/TestCuVSGaps.java(around line 146).