RSLM: Training-Free Vector Quantization for Approximate Nearest Neighbor Search
2026-08-31 • Machine Learning
Machine LearningInformation Retrieval
AI summaryⓘ
The authors introduce RSLM, a new way to compress data vectors into very small sizes (1 to 4 bits per dimension) without training. This helps reduce the memory and complexity in systems that quickly find similar data, like search engines, while keeping or improving accuracy. They improve the process by focusing on encoding the differences (residuals) between vectors and adjusting their lengths to better match the original data. Their method is simpler and more efficient than previous ones and uses fast math tricks and special coding to run quickly on modern computers.
Vector QuantizationApproximate Nearest Neighbor (ANN) SearchResidual VectorsMaximum Inner Product Search (MIPS)L2 Norm CorrectionFast Walsh-Hadamard Transform (FWHT)AVX SIMDCodebooksMemory BandwidthCache-line Alignment
Authors
Rastislav Lenhardt, Teodora Dobos, Thomas Vecchiato, Jiri Isa, Igor Ginzburg
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.