RSLM: Training-Free Vector Quantization for Approximate Nearest Neighbor Search
cs.LG, cs.IR
Submitted: 2026-08-31
Updated: 2026-08-31
Comments: 14 Pages, 3 Figures, Preprint
Code: https://github.com/facebookresearch/faiss
License: http://creativecommons.org/licenses/by/4.0/
The gist: By introducing RSLM (Rotated Scaled Lloyd-Max), a family of training-free vector quantization codecs compressing embeddings to 1--4 bits per dimension, we reduce memory cost and memory bandwidth of a
Terminology
Abstract
By introducing RSLM (Rotated Scaled Lloyd-Max), a family of training-free vector quantization codecs compressing embeddings to 1--4 bits per dimension, we reduce memory cost and memory bandwidth of a typical large-scale Approximate Nearest Neighbor (ANN) search system, while reducing its complexity and keeping or improving recall across multiple benchmark datasets. State-of-the-art systems filter candidates using coarse partitions, approximately score them to narrow the set, and then rescore the best with higher precision representations (often >=8 bits per dimension). Our relativized codecs can bring this down to 2--4 bits per dimension. We use the properties of the ANN system to encode residual vectors instead of full vectors, both for the approximate scoring phase and the rescoring phase. Since Maximum Inner Product Search (MIPS) is very sensitive to vector norms, we correct the L 2 norms of quantized vectors. Our major innovation is that we correct the L 2 norm of the final reconstructed vector rather than just the residual. Our rescaling replaces more complicated schemes, such as Anisotropic loss. The residualization scheme gives us a more favorable quality vs size trade-off than generic quantization methods. Our high-performance implementation leverages a block-wise cascaded Fast Walsh-Hadamard Transform (FWHT) with linear-like complexity, AVX SIMD-optimized codebooks, and a steganographic encoding of scaling factors for perfect cache-line alignment.
Sources
- Block-Sphere Vector Quantization
- Clustering is Efficient for Approximate Maximum Inner Product Search
- Retrieval-Augmented Generation for Large Language Models: A Survey
- LiftQuant: Continuous Bit-Width LLM via Dimensional Lifting and Projection
- Dense Passage Retrieval for Open-Domain Question Answering
- OrbitQuant: Data-Agnostic Quantization for Image and Video Diffusion Transformers
- Recent Developments in Recommender Systems: A Survey
- KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache
- A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challenge
- VectorSearch: Enhancing Document Retrieval with Semantic Embeddings and Optimized Search
- AlphaEvolve: A coding agent for scientific and algorithmic discovery
- A Comprehensive Review of Recommender Systems: Transitioning from Theory to Practice
- Retrieval-Augmented Generation: A Comprehensive Survey of Architectures, Enhancements, and Robustness Frontiers
- GPU-Native Approximate Nearest Neighbor Search with IVF-RaBitQ: Fast Index Build and Search
- Learning Cluster Representatives for Approximate Nearest Neighbor Search
- PolarQuant: Leveraging Polar Transformation for Efficient Key Cache Quantization and Decoding Acceleration
- HARP: Hadamard-Preconditioned Adaptive Rotation Processor for Extreme LLM Quantization
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: Local-Consistency Optimisation for Bayesian Neural Networks
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks