# Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search

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

## Key facts

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

## Built on by (most cited first, 21 of 21)

- [TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate](https://mlsanity.com/paper/2504.19874/) (2025)
- [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)
- [Hierarchical vs. Flat Iteration in Shared-Weight Transformers](https://mlsanity.com/paper/2604.14442/) (2026)
- [Revisiting RaBitQ and TurboQuant: A Symmetric Comparison of Methods, Theory, and Experiments](https://mlsanity.com/paper/2604.19528/) (2026)
- [SNIP: An Adaptive Mixed Precision Framework for Subbyte Large Language Model Training](https://mlsanity.com/paper/2602.01410/) (2026)
- [GEM: A Native Graph-based Index for Multi-Vector Retrieval](https://mlsanity.com/paper/2603.20336/) (2026)
- [MINT: Multi-Vector Search Index Tuning](https://mlsanity.com/paper/2504.20018/) (2025)
- [Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach](https://mlsanity.com/paper/2603.06660/) (2026)
- [Semantic Recall for Vector Search](https://mlsanity.com/paper/2604.20417/) (2026)
- [Direction-Preserving Number Representations](https://mlsanity.com/paper/2605.07662/) (2026)
- [FAVOR: Efficient Filter-Agnostic Vector ANNS Based on Selectivity-Aware Exclusion Distances](https://mlsanity.com/paper/2605.07770/) (2026)
- [IVF-TQ: Calibration-Free Streaming Vector Search via a Codebook-Free Residual Layer](https://mlsanity.com/paper/2605.17415/) (2026)
- [Block-Sphere Vector Quantization](https://mlsanity.com/paper/2605.19972/) (2026)
- [Inner Product Aware Quantization: Provably Fast, Accurate, and Adaptive Algorithms](https://mlsanity.com/paper/2606.00289/) (2026)
- [VQ-bench: A Composable Vector Quantization Framework](https://mlsanity.com/paper/2608.11240/) (2026)
- [TORQUE: Optimizing What (not) to Quantize Before and After Rotation](https://mlsanity.com/paper/2609.36032/) (2026)
- [MRVQ: One Resident Index for Dimension- and Rate-Elastic Vector Search](https://mlsanity.com/paper/2610.03651/) (2026)
- [Fast Quantized Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2610.16289/) (2026)

## Abstract (arXiv)

Approximate nearest neighbor (ANN) query in high-dimensional Euclidean space is a key operator in database systems. For this query, quantization is a popular family of methods developed for compressing vectors and reducing memory consumption. Recently, a method called RaBitQ achieves the state-of-the-art performance among these methods. It produces better empirical performance in both accuracy and efficiency when using the same compression rate and provides rigorous theoretical guarantees. However, the method is only designed for compressing vectors at high compression rates (32x) and lacks support for achieving higher accuracy by using more space. In this paper, we introduce a new quantization method to address this limitation by extending RaBitQ. The new method inherits the theoretical guarantees of RaBitQ and achieves the asymptotic optimality in terms of the trade-off between space and error bounds as to be proven in this study. Additionally, we present efficient implementations of the method, enabling its application to ANN queries to reduce both space and time consumption. Extensive experiments on real-world datasets confirm that our method consistently outperforms the state-of-the-art baselines in both accuracy and efficiency when using the same amount of memory.