[BUG] bitset-filter result- padding quirk in cuvs::neighbors::ivf_pq::search
Nobody has claimed this yet.
- Dominant language
- Cuda
- Stars
- 854
- Forks
- 236
- Avg merge
- 3d 3h
- Merged PRs (30d)
- 62
Description
Describe the bug
When the number of rows passing the bitset filter is strictly less than the
requested top-k, IVF-PQ does not write the (-1, +inf) sentinel into the
remaining result slots. Instead it pads them with filter-EXCLUDED nearest
neighbors (rows whose bit in the filter bitset is 0). The caller cannot tell
these padding entries apart from real, filter-passing matches.
IVF-Flat and CAGRA on the same input correctly emit the sentinel for the
excluded slots — so this looks specific to the IVF-PQ search kernel's
handling of popcount(filter) < k.
Observation: in our run the distance slot is already FLT_MAX (+inf) for
the leaked entries — cuVS evidently knows those slots are empty and writes
the sentinel distance, but it forgets to also overwrite the matching
neighbor index with -1. So the fix on the cuVS side may be a single store
in the same kernel codepath that already writes the sentinel distance.
Steps/Code to reproduce bug
Follow this guide http://matthewrocklin.com/blog/work/2018/02/28/minimal-bug-reports to craft a minimal bug report. This helps us reproduce the issue you're having and resolve the issue more quickly.
reproducer program attached.
Expected behavior
A clear and concise description of what you expected to happen.
invalid results should be filtered out.
Environment details (please complete the following information):
- Environment location: [Bare-metal, Docker, Cloud(specify cloud provider)]
- Method of RAFT install: [conda, Docker, or from source]
- If method of install is [Docker], provide
docker pull&docker runcommands used
- If method of install is [Docker], provide
Reproduces on libcuvs / libraft 26.02.000 + CUDA 13.0 against an
RTX 5070 Laptop GPU.
Additional context
Add any other context about the problem here.
./test_ivfpq_filter
==============================================================
cuVS IVF-PQ bitset-filter padding reproducer
rows=200 dim=8 n_lists=4 pq_dim=4 n_probes=4 top_k=5
filter popcount = 2 (passing IDs: 0 2)
query = (1,1,...,1). Distance from query to each row:
row 0 (passing): 0.0 row 1 (excluded): 8.0 row 2 (passing): 32.0
row 3+ (excluded): ~10000+
--------------------------------------------------------------
Expected (correct): neighbors = [ 0, 2, -1, -1, -1]
--------------------------------------------------------------
raw cuVS: neighbors = [ 0, 2, 1, 40, 41] distances = [ 0.0, 32.0, inf, inf, inf]
==> 3 filter-excluded id(s) leaked into the result. <-- bug
after host post-filter: neighbors = [ 0, 2, -1, -1, -1] distances = [ 0.0, 32.0, +inf, +inf, +inf]
--------------------------------------------------------------
RESULT: bug reproduced; host post-filter recovers the expected sentinel-padded result.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the attached test_ivfpq_filter reproducer and trace the cuVS IVF-PQ search kernel path used when popcount(filter) is less than top-k. Compare its handling with IVF-Flat and CAGRA, then verify that excluded result slots contain neighbor index -1 alongside the existing +inf distance in the reproducer output.
Written by the indexing model from the issue text.
Assessment
- Domain
- data
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 52/100