# RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search

arXiv: https://arxiv.org/abs/2405.12497 · HTML: https://mlsanity.com/paper/2405.12497/

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 May 2024.

## Built on by (most cited first, 30 of 48)

- [Streaming Attention Approximation via Discrepancy Theory](https://mlsanity.com/paper/2502.07861/) (2025)
- [PDX: A Data Layout for Vector Similarity Search](https://mlsanity.com/paper/2503.04422/) (2025)
- [A Note on TurboQuant and the Earlier DRIVE/EDEN Line of Work](https://mlsanity.com/paper/2604.18555/) (2026)
- [Provable Quantization with Randomized Hadamard Transform](https://mlsanity.com/paper/2605.13810/) (2026)
- [VIBE: Vector Index Benchmark for Embeddings](https://mlsanity.com/paper/2505.17810/) (2025)
- [Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven](https://mlsanity.com/paper/2605.06014/) (2026)
- [RaanA: A Fast, Flexible, and Data-Efficient Post-Training Quantization Algorithm](https://mlsanity.com/paper/2504.03717/) (2025)
- [LEANN: A Low-Storage Vector Index](https://mlsanity.com/paper/2506.08276/) (2025)
- [Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search](https://mlsanity.com/paper/2508.01405/) (2025)
- [Nearly Optimal Attention Coresets](https://mlsanity.com/paper/2605.05602/) (2026)
- [Revisiting RaBitQ and TurboQuant: A Symmetric Comparison of Methods, Theory, and Experiments](https://mlsanity.com/paper/2604.19528/) (2026)
- [HAKES: Scalable Vector Database for Embedding Search Service](https://mlsanity.com/paper/2505.12524/) (2025)
- [Probabilistic Kernel Function for Fast Angle Testing](https://mlsanity.com/paper/2505.20274/) (2025)
- [Benchmarking Filtered Approximate Nearest Neighbor Search Algorithms on Transformer-based Embedding Vectors](https://mlsanity.com/paper/2507.21989/) (2025)
- [Approximating Uniform Random Rotations by Two-Stage Structured Hadamard Rotations in High Dimensions](https://mlsanity.com/paper/2604.23418/) (2026)
- [eOptShrinkQ: Near-Lossless KV Cache Compression Through Optimal Spectral Denoising and Quantization](https://mlsanity.com/paper/2605.02905/) (2026)
- [FibQuant: Universal Vector Quantization for Random-Access KV-Cache Compression](https://mlsanity.com/paper/2605.11478/) (2026)
- [VikingMem: A Memory Base Management System for Stateful LLM-based Applications](https://mlsanity.com/paper/2605.29640/) (2026)
- [RaBitQCache: Rotated Binary Quantization for KVCache in Long Context LLM Inference](https://mlsanity.com/paper/2606.31519/) (2026)
- [SuperLocalMemory 4.0: The Governed Memory Operating System for AI Agents](https://mlsanity.com/paper/2608.08253/) (2026)
- [Machine learning and high dimensional vector search](https://mlsanity.com/paper/2502.16931/) (2025)
- [GPU-Accelerated ANNS: Quantized for Speed, Built for Change](https://mlsanity.com/paper/2601.07048/) (2026)
- [GEM: A Native Graph-based Index for Multi-Vector Retrieval](https://mlsanity.com/paper/2603.20336/) (2026)
- [From Volume to Value: Preference-Aligned Memory Construction for On-Device RAG](https://mlsanity.com/paper/2605.18271/) (2026)
- [A Geometric Lens on Physics-Aligned Data Compression](https://mlsanity.com/paper/2606.03279/) (2026)
- [Cost-Governed RAG: Unified Per-Tenant Cost Attribution Across Retrieval and Generation in Multi-Tenant LLM Systems](https://mlsanity.com/paper/2607.12188/) (2026)
- [KV-COBRA: KV Cache Compression via Co-Optimized Bit-Rank Allocation](https://mlsanity.com/paper/2609.24298/) (2026)
- [MINT: Multi-Vector Search Index Tuning](https://mlsanity.com/paper/2504.20018/) (2025)
- [Approximate Diverse k-nearest Neighbor Search in Vector Database](https://mlsanity.com/paper/2510.27243/) (2025)
- [Graph-based Nearest Neighbors with Dynamic Updates via Random Walks](https://mlsanity.com/paper/2512.18060/) (2025)

## Abstract (arXiv)

Searching for approximate nearest neighbors (ANN) in the high-dimensional Euclidean space is a pivotal problem. Recently, with the help of fast SIMD-based implementations, Product Quantization (PQ) and its variants can often efficiently and accurately estimate the distances between the vectors and have achieved great success in the in-memory ANN search. Despite their empirical success, we note that these methods do not have a theoretical error bound and are observed to fail disastrously on some real-world datasets. Motivated by this, we propose a new randomized quantization method named RaBitQ, which quantizes D-dimensional vectors into D-bit strings. RaBitQ guarantees a sharp theoretical error bound and provides good empirical accuracy at the same time. In addition, we introduce efficient implementations of RaBitQ, supporting to estimate the distances with bitwise operations or SIMD-based operations. Extensive experiments on real-world datasets confirm that (1) our method outperforms PQ and its variants in terms of accuracy-efficiency trade-off by a clear margin and (2) its empirical performance is well-aligned with our theoretical analysis.