RSLM: Training-Free Vector Quantization for Approximate Nearest Neighbor Search

• URL: http://arxiv.org/abs/2608.30384v1
• Date: Mon, 31 Aug 2026 07:40:57 GMT
• Title: RSLM: Training-Free Vector Quantization for Approximate Nearest Neighbor Search
• Abstract summary: RSLM is a family of training-free vector quantization codecs compressing embeddings to 1--4 bits per dimension.<n>We reduce memory cost and memory bandwidth of a typical large-scale Approximate Nearest Neighbor (ANN) search system.<n>Our major innovation is that we correct the $L$ norm of the final reconstructed vector rather than just the residual.
• Score: 0.4077787659104315
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant [79.24089819400126]
  Subsampled TurboQuant (SSTQ) is a framework that combines overcomplete equal-width tight frames, coordinate subsampling, and privacy-aware quantization.<n>SSTQ achieves mean squared error scaling while using only $lceil log N il + b$ bits per client, where $N = (d)$ is the frame size.<n>We also derive a surrogate privacy-aware codebook objective that reduces the codebook-dependent MSE scaling from $O(4b)$ to $O(2b)$.
  arXiv  Detail & Related papers  (2026-08-05T17:51:25Z)
• No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval [51.43543998583709]
  Single-stage Sparse Retrieval (SSR) is a paradigm shift that replaces expensive clustering with efficient sparse coding.<n>It reduces indexing time by 15x compared to ColBERTv2, halves retrieval latency, and simultaneously improves retrieval performance.
  arXiv  Detail & Related papers  (2026-05-28T15:53:34Z)
• ITQ3_S: High-Fidelity 3-bit LLM Inference via Interleaved Ternary Quantization with Rotation-Domain Smoothing [0.0]
  We present ITQ3_S (Interleaved Ternary Quantization -- Specialized), a novel 3-bit weight quantization format for LLMs integrating TurboQuant (TQ)<n>Conventional 3-bit methods suffer precision loss from heavy-tailed weight distributions and inter-channel outliers.<n>ITQ3_S pre-rotates the weight space via FWHT before quantization, spreading energy across the vector and inducing a near-Gaussian distribution.
  arXiv  Detail & Related papers  (2026-03-30T00:03:22Z)
• Learning Grouped Lattice Vector Quantizers for Low-Bit LLM Compression [57.54335545892155]
  We introduce a Grouped Lattice Vector Quantization (GLVQ) framework that assigns each group of weights a customized lattice codebook.<n>Our approach achieves a better trade-off between model size and accuracy compared to existing post-training quantization baselines.
  arXiv  Detail & Related papers  (2025-10-23T20:19:48Z)
• SBVR: Summation of BitVector Representation for Efficient LLM Quantization [3.7018544730078413]
  Quantization compression by limiting the number of representable points in the data is key to efficient quantization.<n>Existing Post-Training Quantization (PTQ) solutions adopt two major approaches to this problem: Round-To-Nearest (RTN)-based methods and codebook-based methods.<n>We propose SBVR (Summation of Bitplex Representation), that enables Gaussian-like code representation in a hardware-friendly manner for fast inference.
  arXiv  Detail & Related papers  (2025-09-17T13:51:27Z)
• FFT-based Dynamic Subspace Selection for Low-Rank Adaptive Optimization of Large Language Models [49.397861654088636]
  We propose a two-step procedure to approximate SVD/QR-based gradient projections into lower-dimensional spaces.<n>We show that our strategy achieves faster runtime and reduced memory usage by up to $25%$ across different model sizes.
  arXiv  Detail & Related papers  (2025-05-23T14:37:00Z)
• Qinco2: Vector Compression and Search with Improved Implicit Neural Codebooks [23.598010051403225]
  We introduce QINCo2, which improves the state-of-the-art reconstruction MSE by 34% for 16-byte vector compression on BigANN, and search accuracy by 24% with 8-byte encodings on Deep1M.<n>We conduct experiments on four datasets to evaluate QINCo2 for vector compression and billion-scale nearest neighbor search.
  arXiv  Detail & Related papers  (2025-01-06T15:20:22Z)
• Residual vector quantization for KV cache compression in large language model [2.3094645821058735]
  KV cache compression methods have mainly relied on scalar quantization techniques to reduce the memory requirements during decoding. In this work, we apply residual vector quantization, which has been widely used for high fidelity audio compression, to compress KV cache in large language models (LLM) We learn the codebook using exponential moving average and there are no other learnable parameters including the input and output projections normally used in a vector quantization set up.
  arXiv  Detail & Related papers  (2024-10-21T07:20:41Z)
• Extreme Compression of Large Language Models via Additive Quantization [59.3122859349777]
  Our algorithm, called AQLM, generalizes the classic Additive Quantization (AQ) approach for information retrieval. We provide fast GPU and CPU implementations of AQLM for token generation, which enable us to match or outperform optimized FP16 implementations for speed.
  arXiv  Detail & Related papers  (2024-01-11T18:54:44Z)
• Factorizers for Distributed Sparse Block Codes [45.29870215671697]
  We propose a fast and highly accurate method for factorizing distributed block codes (SBCs) Our iterative factorizer introduces a threshold-based nonlinear activation, conditional random sampling, and an $ell_infty$-based similarity metric. We demonstrate the feasibility of our method on four deep CNN architectures over CIFAR-100, ImageNet-1K, and RAVEN datasets.
  arXiv  Detail & Related papers  (2023-03-24T12:31:48Z)
• Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization [60.91600465922932]
  We present an approach that avoids the use of a dual-encoder for retrieval, relying solely on the cross-encoder. Our approach provides test-time recall-vs-computational cost trade-offs superior to the current widely-used methods.
  arXiv  Detail & Related papers  (2022-10-23T00:32:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.