NVIDIA / NVIDIA/cuvs

[BUG] bitset-filter result- padding quirk in cuvs::neighbors::ivf_pq::search

Open
#2,082 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug
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 run commands used

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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.