Repository navigation
[FEA] Roaring Bitmap support #1972
Description
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
Activity
maxwbuckley commentedon May 23, 2026
Made much more progress on this one and ready to share a WIP approach and some good progress.
I use the roaring bitmap structure to specify which kernels to launch
For empty containers we just skip
For array containers I do a CSR gather of the rows and then GEMM
For bitmap containers I do a GEMM and post filter
For run length encodings we use a dense GEMM (not always used)
When the roaring bitmaps are apriori available this means transfering H2D a tiny roaring bitmap versus a larger bitset
The roaring bitmap knows its own cardinality, while the bitset requires a count kernel to check its cardinality (universe size is known). As of today there is no way to specify the cardinality here and skip the count as there is in CAGRA (#1960). We should fix this gap as it will make things faster when you know the cardinality and fairer in side by side comparisons. #2120
The bitset path has an optimization set at 10% density where it switches to a CSR, my analysis suggests (at least on my hardware) that this is way too high and should be 3% at least in my evals. With it at 10% my roaringBitmap numbers really dominate (unfairly) in the 3-10% range
maxwbuckley commentedon May 26, 2026
I noticed that we were also unnecessarily computing csr_to_coo on inner-product filtered search #2128. It is only needed for L2 and Cosine. Can remove. This is removed in #2128
maxwbuckley commentedon Jul 14, 2026
I would like to land a sequence of PRs here to fix many of these issues
This one is trivial perf(brute_force): skip csr_to_coo on inner-product filtered search #2128 makes dot product a tiny bit cheaper by not computing normalization constants we need only for cosine/L2. - pure improvement.
Add a filtering_rate hint to brute_force::search_params #2120 is a little more discussable. Specifically I want to be able to pass the cardinality explicitly and skip the popcount checking consistently. This will make the later comparisons with roaringBitmap fairer (as it knows its cardinality) and it also brings things into line with CAGRA which can pass its cardinality and skip its popcount. This is also useful in production if you know the cardinality, why bother recomputing it all the time.
Reduce the threshold for the SDDMM optimization (can be its own PR or merged with the next) at present this optimization is strictly worse than baseline for most values between 1 and 10 %. Reducing to 3% for now and probably even lower (1% in some cases perhaps also with a minimum size, see analysis charts 1 below)
Add a ScatterGather middle path - This would for SDDMM threshhold to some new ScatterGather threshhold (~10%) gather the rows being filtered for and do a small dense GEMM on those. This should make the optimized below chart all better than the dense bassline. I.e. you only SDDMM at very small sizes <3% with n>=1M say and then you do Gather and small dense GEMM from there to middle and then big GEMM and post filter above ( This can potentially go higher depending on dim of the vectors, but I need more analysis perf(brute_force): add scatter-gather path and fix filtered-search dispatch thresholds #2321
Once these are landed the RoaringBitmap changes can come in with a fairer, optimized baseline to compete against
Once I add the middle path
maxwbuckley commentedon Sep 23, 2026
This isn't complete yet. One of the PRs listed above #2120 is still open, also the actual roaring bitmap PRs have not gone in (unless they went in under someone else). The reason I wanted to fix the above first was to ensure a fair comparison for performance purposes
divyegala commentedon Sep 30, 2026
We added Roaring Bitmap filters and support for it in CAGRA here #2446
2120 does not seem related specifically to Roaring Bitmap. Do you either want to create a new issue(s) to capture work that you wish to pursue?