Is your feature request related to a problem? Please describe.
Filtered vector search optimization
Describe the solution you'd like
Adding Roaring Bitmap Support directly to cuVS.
Describe alternatives you've considered
Using the existing bitset implementation
Additional context
Original Roaring Bitmap paper: https://arxiv.org/abs/1402.6407
Follow on paper that introduced run encoding: https://arxiv.org/abs/1603.06549
Summary
I'd like to propose contributing https://roaringbitmap.org/ support on Exa's behalf as an alternative filter representation for cuVS's prefiltered search APIs (for CAGRA, IVF-Flat, brute-force, etc).
Motivation
cuVS currently supports bitset_filter for prefiltered search, backed by a flat bit array. This works, but has two
limitations:
- Memory scaling. A flat bitset for N vectors requires N/8 bytes regardless of how many bits are set. At 10M vectors
this is 1.2 MB; at 100M it's 12 MB; at 1B it's 120 MB. For sparse filters (e.g., 1% pass rate at 100M scale), a
compressed representation could reduce this by 10-100x or even more.
- Cache pressure. During CAGRA graph traversal and IVF-Flat list scanning, filter checks access random positions
in the bitset. When the bitset exceeds L1 cache (128 KB per SM on Blackwell), every check incurs an L2 round-trip
(~200 cycles vs ~28 cycles for L1). Roaring's two-level structure (small key index + 8 KB containers) keeps the
working set in L1.
- Interoperability. Roaring Bitmaps are the standard compressed bitmap format across the database and search
ecosystem (Lucene, Elasticsearch, Apache Spark, ClickHouse, Redis, etc.). Accepting roaring filters directly avoids a decompress-to-bitset step on the ingestion path and allows for the copying of a tiny roaring bitmap filter to the GPU, potentially one per query vector.
I have already prototype some of the parts of this and it performs extremely well in specific cases, sparse data, clustered or multitenant indexes. It can also work very well in cases where we can presort our data so common filters are contigous so Roaring Bitmap containers store them using run encoding
I spoke with @cjnolet, Nathan Stephens, and Manas Singh earlier today. Filing this PR to kick off the discussion and will share more details next week
Is your feature request related to a problem? Please describe.
Filtered vector search optimization
Describe the solution you'd like
Adding Roaring Bitmap Support directly to cuVS.
Describe alternatives you've considered
Using the existing bitset implementation
Additional context
Original Roaring Bitmap paper: https://arxiv.org/abs/1402.6407
Follow on paper that introduced run encoding: https://arxiv.org/abs/1603.06549
Summary
I'd like to propose contributing https://roaringbitmap.org/ support on Exa's behalf as an alternative filter representation for cuVS's prefiltered search APIs (for CAGRA, IVF-Flat, brute-force, etc).
Motivation
cuVS currently supports bitset_filter for prefiltered search, backed by a flat bit array. This works, but has two
limitations:
this is 1.2 MB; at 100M it's 12 MB; at 1B it's 120 MB. For sparse filters (e.g., 1% pass rate at 100M scale), a
compressed representation could reduce this by 10-100x or even more.
in the bitset. When the bitset exceeds L1 cache (128 KB per SM on Blackwell), every check incurs an L2 round-trip
(~200 cycles vs ~28 cycles for L1). Roaring's two-level structure (small key index + 8 KB containers) keeps the
working set in L1.
ecosystem (Lucene, Elasticsearch, Apache Spark, ClickHouse, Redis, etc.). Accepting roaring filters directly avoids a decompress-to-bitset step on the ingestion path and allows for the copying of a tiny roaring bitmap filter to the GPU, potentially one per query vector.
I have already prototype some of the parts of this and it performs extremely well in specific cases, sparse data, clustered or multitenant indexes. It can also work very well in cases where we can presort our data so common filters are contigous so Roaring Bitmap containers store them using run encoding
I spoke with @cjnolet, Nathan Stephens, and Manas Singh earlier today. Filing this PR to kick off the discussion and will share more details next week