TL;DR
While Approximate Nearest Neighbor (ANN) search is highly optimized for retrieving a small number of results ($k \le 100$), performance plummets when applications require thousands of neighbors ($k \ge 5,000$). This paper introduces BBC (Bucket-based Result Collector), a novel framework that replaces traditional binary heaps with a cache-efficient, bucketed result buffer and introduces optimized re-ranking algorithms. This approach achieves up to a 3.8× speedup for large-$k$ queries without sacrificing accuracy.
What Problem Does This Paper Address?
Vector search and ANN algorithms are foundational to modern AI applications like Retrieval-Augmented Generation (RAG). Typically, these systems are evaluated under small-$k$ settings (e.g., finding the top 10 or 100 matches). However, emerging real-world workflows—such as retrieve-and-rerank pipelines (e.g., ColBERT), industrial recommendation engines, and machine learning dataset curation—frequently demand large-$k$ queries where $k \ge 5,000$.
Under these large-$k$ conditions, existing quantization-based ANN methods suffer severe performance degradation due to two primary bottlenecks:
- Collector Inefficiency: Standard ANN implementations use a binary-heap priority queue to track the top-$k$ candidates. When $k$ is large, the heap size balloons past the 32 KB capacity of the CPU's L1 cache, causing rampant cache misses and high maintenance overhead.
- Declining Pruning Effectiveness: Quantization methods rely on estimated distances to quickly filter out distant vectors. As $k$ increases, the distance threshold loosens, forcing the system to perform expensive exact-distance re-ranking on a massive, linearly growing pool of candidates.
Methods
To bypass these bottlenecks, the authors propose the Bucket-based Result Collector (BBC), which features two core innovations:
- Bucket-based Result Buffer: Instead of maintaining a strictly ordered top-$k$ heap, BBC partitions the estimated distance range into non-overlapping sub-ranges (buckets) using one-dimensional quantization. Each bucket contains two linear buffers that sequentially store candidate IDs and distances. This design eliminates per-object replacement overhead and maximizes L1 cache efficiency by leveraging hardware prefetching. It maintains a relaxed threshold at the bucket level, deferring exact sorting until a lightweight final selection step.
- Tailored Re-ranking Algorithms:
- For Bounded Quantization (e.g., RaBitQ): A greedy re-ranking algorithm that uses probabilistic distance bounds to skip objects guaranteed to be safely inside or outside the top-$k$ set, only re-ranking ambiguous candidates near the threshold bucket boundaries.
- For Unbounded Quantization (e.g., Product Quantization / PQ): An early re-ranking strategy that predicts whether an object will enter the final re-ranking pool at the moment its data is accessed, interleaving distance estimation and exact computation to minimize cache misses from random memory access.
Datasets
The authors evaluated BBC across four large-scale, real-world vector datasets:
- Wiki: 10 million vectors (1,536 dimensions) generated via the
gte-Qwen2-1.5B-instructmodel. - C4: 14.2 million vectors (1,024 dimensions) generated using the T5 model for natural language pre-training.
- MSMARCO: 18 million vectors (768 dimensions) sampled from MSMARCO-V2.1 using Snowflake's Arctic embed model.
- Deep100M: 100 million image descriptor vectors (96 dimensions) produced by the GoogLeNet model.
Key Insights and Ideas
- Ditch the Strict Order: Traditional top-$k$ collectors waste massive CPU cycles keeping candidates perfectly sorted during the entire search. BBC realizes that bucket-level ordering is sufficient during candidate collection; you only need to sort the boundary bucket at the very end.
- Exploit Distance Concentration: In high-dimensional spaces, distances between vectors naturally concentrate around a mean value with tight variance. The authors mathematically prove (Theorem 3.1) that under an equal-depth partition, the error between BBC's relaxed bucket threshold and the exact threshold is incredibly small (on the order of $10^{-2}$), ensuring that the candidate superset remains compact.
- Hardware-Aware Software Design: By structuring buckets as sequential linear buffers rather than pointer-heavy trees or heaps, BBC perfectly aligns with modern CPU hardware prefetchers, turning a chaotic memory access pattern into a highly predictable, cache-friendly stream.
Key Results
- Throughput Boost: BBC delivers a 1.4× to 3.8× speedup over state-of-the-art quantization methods (IVF+PQ and IVF+RaBitQ) at a high accuracy target of
recall@k = 0.95. - Scalability with $k$: The performance gap widens dramatically as $k$ scales up. On the Deep100M dataset, the acceleration ratio of IVF+PQ+BBC over standard IVF+PQ jumps from 2.9× at $k=5,000$ to 3.8× at $k=100,000$.
- Cache Miss Reduction: Profiling showed that BBC reduces the L1 cache miss count during re-ranking by up to 1.45× (dropping from $7.61 \times 10^5$ to $5.23 \times 10^5$ on C4 when $k=100,000$).
- Collector Efficiency: The bucket-based result buffer itself is up to an order of magnitude faster than a standard binary heap or lazy-sorting alternatives.
Limitations and Future Work
- Graph-Based Index Integration: The current implementation focuses primarily on quantization-based inverted file (IVF) indexes. While the authors discuss how BBC could theoretically optimize graph-based methods (like HNSW) by replacing their internal min-heaps during greedy beam search, this integration was not implemented or evaluated.
- GPU Acceleration: BBC is currently designed and optimized for CPU architectures (utilizing SIMD/AVX instructions). Adapting the bucketed collection strategy to massive parallel GPU architectures (e.g., extending FAISS's WarpSelect) remains an open challenge.
Summary updated