mlsanityData to 14 Oct 2026

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

arXiv 2405.12497 ↗First posted 21 May 2024cs.DB cs.DS cs.IRcited by 48

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 13; 2026: 35.

48 papers.

Sort:

By area:

  1. 2025Streaming Attention Approximation via Discrepancy Theorycited by 11
  2. 2025PDX: A Data Layout for Vector Similarity Searchcited by 8
  3. 2026A Note on TurboQuant and the Earlier DRIVE/EDEN Line of Workcited by 8
  4. 2026Provable Quantization with Randomized Hadamard Transformcited by 8
  5. 2025VIBE: Vector Index Benchmark for Embeddingscited by 6
  6. 2026Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Provencited by 6
  7. 2025RaanA: A Fast, Flexible, and Data-Efficient Post-Training Quantization Algorithmcited by 5
  8. 2025LEANN: A Low-Storage Vector Indexcited by 4
  9. 2025Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Searchcited by 4
  10. 2026Nearly Optimal Attention Coresetscited by 4
  11. 2026Revisiting RaBitQ and TurboQuant: A Symmetric Comparison of Methods, Theory, and Experimentscited by 3
  12. 2025HAKES: Scalable Vector Database for Embedding Search Servicecited by 2
36 more
  1. 2025Probabilistic Kernel Function for Fast Angle Testingcited by 2
  2. 2025Benchmarking Filtered Approximate Nearest Neighbor Search Algorithms on Transformer-based Embedding Vectorscited by 2
  3. 2026Approximating Uniform Random Rotations by Two-Stage Structured Hadamard Rotations in High Dimensionscited by 2
  4. 2026eOptShrinkQ: Near-Lossless KV Cache Compression Through Optimal Spectral Denoising and Quantizationcited by 2
  5. 2026FibQuant: Universal Vector Quantization for Random-Access KV-Cache Compressioncited by 2
  6. 2026VikingMem: A Memory Base Management System for Stateful LLM-based Applicationscited by 2
  7. 2026RaBitQCache: Rotated Binary Quantization for KVCache in Long Context LLM Inferencecited by 2
  8. 2026SuperLocalMemory 4.0: The Governed Memory Operating System for AI Agentscited by 2
  9. 2025Machine learning and high dimensional vector searchcited by 1
  10. 2026GPU-Accelerated ANNS: Quantized for Speed, Built for Changecited by 1
  11. 2026GEM: A Native Graph-based Index for Multi-Vector Retrievalcited by 1
  12. 2026From Volume to Value: Preference-Aligned Memory Construction for On-Device RAGcited by 1
  13. 2026A Geometric Lens on Physics-Aligned Data Compressioncited by 1
  14. 2026Cost-Governed RAG: Unified Per-Tenant Cost Attribution Across Retrieval and Generation in Multi-Tenant LLM Systemscited by 1
  15. 2026KV-COBRA: KV Cache Compression via Co-Optimized Bit-Rank Allocationcited by 1
  16. 2025MINT: Multi-Vector Search Index Tuningcited by 0
  17. 2025Approximate Diverse k-nearest Neighbor Search in Vector Databasecited by 0
  18. 2025Graph-based Nearest Neighbors with Dynamic Updates via Random Walkscited by 0
  19. 2026FaTRQ: Tiered Residual Quantization for LLM Vector Search in Far-Memory-Aware ANNS Systemscited by 0
  20. 2026Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approachcited by 0
  21. 2026The Virtuous Cycle: AI-Powered Vector Search and Vector Search-Augmented AIcited by 0
  22. 2026IVF-TQ: Calibration-Free Streaming Vector Search via a Codebook-Free Residual Layercited by 0
  23. 2026Covariance Structure and Coordinate Heterogeneity Govern Binary Quantization of Contrastive Embeddingscited by 0
  24. 2026Block-Sphere Vector Quantizationcited by 0
  25. 2026NasZip: Software and Hardware Co-Design to Accelerate Approximate Nearest Neighbor Search with DIMM-Based Near-Data Processingcited by 0
  26. 2026Fast-TurboQuant: A Multiplier-Free Online Vector Quantization Approachcited by 0
  27. 2026HAKARI-Bench: A Lightweight Benchmark for Comparing Retrieval Architectures and Efficiency Settings under Unified Conditionscited by 0
  28. 2026TurboVec: A Case Study in Cost-Efficient Private Retrieval for Enterprise RAG via Codebook-Oblivious Quantizationcited by 0
  29. 2026Error-bounded Point Cloud Compression Using Truncated Octahedron Quantizationcited by 0
  30. 2026SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuantcited by 0
  31. 2026VQ-bench: A Composable Vector Quantization Frameworkcited by 0
  32. 2026When Does Low-Bit Quantization Preserve the Decisions of Vector Search?cited by 0
  33. 2026Self-Indexing Attention for Compression-Compatible Sparse Long-Context LLM Inferencecited by 0
  34. 2026TORQUE: Optimizing What (not) to Quantize Before and After Rotationcited by 0
  35. 2026MRVQ: One Resident Index for Dimension- and Rate-Elastic Vector Searchcited by 0
  36. 2026Fast Quantized Johnson-Lindenstrauss Transformscited by 0