PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Rastislav Lenhardt, Teodora Dobos, Thomas Vecchiato, Jiri Isa, Igor Ginzburg

arXiv:2608.30384v1cs.LGcs.IR

TL;DR

Large-scale ANN systems need compact embeddings without offline training while preserving recall and throughput. RSLM uses training-free residual quantization with final-vector norm correction, matching or exceeding data-dependent standards and reducing memory resources and bandwidth.

  • Problem

    Data-dependent quantizers require offline dataset-specific codebook training, while data-oblivious quantizers avoid that overhead but suffer limitations.

  • Method

    RSLM applies training-free 1–4-bit quantization to ANN residual vectors and corrects the norm of the final reconstructed vector for MIPS.

  • Results

    RSLM matches or exceeds Faiss PQ and ScaNN AH semantic recall while eliminating offline k-means training, with reported 2× to 4× system improvements.

  • Takeaways & Limitations

    Training-free codecs can simplify and lower the cost of production vector databases across both approximate-scoring and rescoring stages.

  • Takeaways & Limitations

    The end-to-end evaluation focuses on tree-based IVF indexes, while graph-based HNSW may achieve lower single-query latency at a given recall target.

Abstract

from arXiv · show

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.

1 Introduction

Rslm addresses low-bit quantization challenges in large-scale ANN systems with training-free residual codecs, efficient rotations, norm correction, and zero-byte metadata. Across approximate scoring and rescoring, it targets lower memory and bandwidth costs while preserving or improving recall.

  • Motivation: Vector quantization reduces ANN memory footprint, latency, and DRAM-to-CPU transfer by compressing embeddings for candidate rescoring.ANN systems first prune candidates using partitions, then rescore selected vectors.
  • Motivation: Below 3 bits per dimension, data-oblivious quantizers can suffer recall degradation, while data-dependent methods require offline codebook training.Rotation-based data-oblivious methods address this trade-off using analytical distributions and fixed codebooks.
  • Rslm: Rslm provides training-free 1- to 4-bit codecs for full vectors and ANN-specific residual vectors in clustering-based and tree-based search.Residual quantization is intended to deliver near-lossless recall without dataset-specific training.
  • Rslm: Rslm’s cascaded block-FWHT has O(D) encoding complexity because fixed blocks make O(Dlog B) effectively linear.The implementation uses hardware-optimized blocks with B≤128.
  • Rslm: Rslm corrects the L2 norm of the final reconstructed vector, matching or exceeding anisotropic-loss recall without offline codebook training.This extends prior approaches that corrected only residual norms and targets MIPS sensitivity to vector norms.
  • Implementation: Rslm4Lite embeds its norm scale factor in the quantized vector, reducing per-vector metadata overhead to exactly zero.The design also enables perfect cacheline alignment for SIMD register lookups.
  • Evaluation: The evaluation covers full and relative quantization across five datasets and end-to-end comparisons with Faiss and ScaNN on glove and openai.The codecs match or exceed trained-codec quality in approximate scoring and rescoring.
  • Results: 4-bit rescoring causes no recall@20@30 loss across five datasets, while 2-bit variants achieve 99%+ recall@20@40.These codecs reduce rescoring memory footprint and bandwidth relative to ScaNN’s default 8-bit representation.

2 Background and Related Work

ANN quantization trades representation fidelity against memory and bandwidth constraints. Rslm is positioned as a training-free, residual-aware alternative that combines linear-complexity rotation with final-vector norm preservation.

  • ANN systems: Billion-scale ANN search uses coarse partitioning followed by quantized in-memory scanning to manage DRAM costs and memory bandwidth.Partitioning structures prune the search space before approximate distance evaluation and rescoring.
  • Quantization: Vector quantization maps high-dimensional vectors to discrete codebook codes to reduce memory footprint, commonly minimizing squared L2 reconstruction error.Data-dependent codebooks are learned offline, often with k-means.
  • Quantization: Data-oblivious methods eliminate offline training by deriving transformation parameters analytically or per vector at runtime.Scaled Scalar Quantization stores or hides a per-vector scale factor alongside low-bit coordinates.
  • Related methods: Aggressive low-bit data-oblivious quantization can degrade recall because coordinate variance skew and outliers reduce quantization effectiveness.Rotation-based methods precondition embeddings to homogenize coordinate variance without k-means training.
  • Rslm positioning: Rslm quantizes both full vectors and residuals relative to coarse tree or IVF partitions, unlike classical oblivious quantizers focused on full vectors.This residual-space design is central to its ANN-specific positioning.
  • Rslm positioning: Rslm uses block-wise cascaded Block-FWHT with O(D) complexity instead of quadratic dense rotations or O(Dlog D) projections.It also scales the reconstructed vector length to preserve the original L2 norm.

3 Rslm codec family

The Rslm codec family combines variance-uniformizing transformations, analytical Lloyd-Max codebooks, and per-vector scaling across 1- to 4-bit rates.

  • Codec pipeline: Rslm provides vector quantization codecs at 4-, 3-, 2-, and 1-bit rates per dimension.The family is designed to span multiple compression levels.
  • Codec pipeline: Each codec first transforms coordinates to achieve uniform variance before quantization.This is the pre-quantization stage of the codec pipeline.
  • Codec pipeline: Rotated coordinates are mapped to pre-computed Lloyd-Max codebooks calibrated for the standard normal distribution.The codebooks avoid dataset-specific codebook training.
  • Codec pipeline: A 2-byte per-vector scale restores vector length after quantization.The scale is appended to restore the reconstructed vector’s length.

3.1 Pre-Quantization Transformations

Rslm preconditions embeddings with a cascaded, block-wise FWHT pipeline augmented by fixed pseudo-random sign flips and permutations. The design preserves orthogonality while handling arbitrary dimensions efficiently.

  • Purpose: Orthogonal transformations distribute energy across coordinates and shape transformed embeddings toward a standard normal distribution while preserving inner products.This improves codebook utilization when raw embeddings have uneven variance and outliers.
  • Pipeline: Rslm combines FWHT, static sign flipping, and block-wise coordinate permutations in a fast cascaded two-pass rotation.These components form the pre-quantization transformation.
  • FWHT: FWHT applies the orthonormal Walsh-Hadamard transform in O(nlog n) time using additions, subtractions, and one final scaling factor.Its recursive structure enables in-place computation without auxiliary memory.
  • Block-wise implementation: Block-wise FWHT with B=128 reduces total complexity to O(Dlog B), which is linear in embedding dimension D.SIMD vector instructions such as AVX2 are used to maximize throughput.
  • Arbitrary dimensions: For non-multiple dimensions, Rslm overlaps a final block; for dimensions below 128, it shrinks the active block to a fitting power of two.These rules avoid requiring global power-of-two dimensions.
  • Randomization: Fixed sign-flip and permutation tables add pseudo-randomness while keeping transformations orthogonal and adding no metadata overhead.The pipeline uses 256 pseudo-random signs and a 128-element within-block permutation.
  • Pipeline variants: For Rslm4 and Rslm4Lite with D≤256, a single-pass optimization bypasses permutation, transpose, and the second FWHT pass.Larger dimensions and Rslm1/2/3 use the complete two-pass cascade.

3.2 Quantization Using Lloyd-Max Codebook

RSLM normalizes transformed coordinates using vector-adaptive scaling before assigning them to fixed Lloyd-Max codebooks calibrated for Gaussian inputs. Bit rate determines sub-vector dimensionality and centroid count, with small codebooks supporting SIMD acceleration.

  • Transformed coordinates approximate N(0, σ^2), so RSLM scales them before assignment to codebooks calibrated for N(0, 1).
  • EVT-based scaling uses the observed maximum coordinate magnitude to control dynamic range and reduce clipping from heavy-tailed peaks.Sample-variance scaling can saturate extreme coordinates at codebook boundaries.
  • The initial scale requires one pass to find max_i|z_i|, followed by multiplication with precomputed 1/E_max(D).Normalizing by 1/s_initial anchors the codebook range to the vector’s peak coordinate.
  • At 1, 2, 3, and 4 bits per dimension, RSLM uses respectively 4D K=16, 2D K=16, 1D K=8, and 1D K=16 codebooks.Vectors whose dimensions do not divide evenly by the sub-vector size are zero-padded.
  • Codebooks use at most 16 centroids for SIMD acceleration and are learned from synthetic standard-normal samples using k-means.The resulting centroids minimize mean squared error under the Gaussian assumption.

3.3 Norm Correction

RSLM restores each reconstructed vector’s original L2 norm through a per-vector scale factor, addressing norm distortion that particularly affects MIPS ranking. This correction removes the inflation or deflation observed in conventional low-bit codecs.

  • RSLM reconstructs x as x̃=s·x̂ with s=||x||_2/||x̂||_2, guaranteeing the reconstructed vector matches the original L2 norm.
  • Standard scaled scalar quantization inflates expected norms, whereas product quantization deflates them and introduces norm variance across vectors.
  • On the 1536-dimensional openai dataset, SSQ4Lite reconstructs norms with mean 1.82 and σ=0.03, while 4-bit PQ yields 0.72 and σ=0.01.The original vectors are unit-normalized; RSLM enforces exact norm alignment.
  • Float32 provides range and recall but costs 4 bytes, while BFloat16 loses recall and Float16 limits range.
  • UE7M9 uses the redundant sign bit of non-negative scales and provides a practical range–precision compromise without subnormals.

3.4 Codecs Description

RSLM variants share a four-stage compression pipeline and include a Lite design that embeds scale metadata into otherwise unused bits. The resulting packing removes separate scale storage for supported dimensions.

  • All RSLM variants transform the vector, estimate an initial scale, quantize, refine the scale for L2 preservation, and pack codes with the scale factor.
  • Table 2 summarizes the technical specifications of the RSLM codec variants.
  • Rslm4Lite targets D≥64 and embeds a 16-bit UE7M9 scale into 16 freed bits among the first 16 encoded dimensions.
  • Rslm4Lite packs a vector into exactly ⌈D/2⌉ bytes by using K=8 three-bit centroids in its first 16 dimensions.

3.5 Relative Quantization

Relative quantization applies RSLM to residuals between original vectors and approximate vectors, enabling score reuse in ANN pipelines. Local scaling preserves residual norms, while global scaling restores the final reconstructed vector’s norm.

  • 3.5 Relative Quantization: Relative quantization encodes the residual r=x−a, where a is the approximation from the initial quantization stage.
  • 3.5.1 Local Scaling: In RelApprox, the residual is quantized independently and preserves its own norm with a local scale factor.
  • 3.5.1 Local Scaling: RelApprox reuses the query–approximation dot product because ⟨q,a+ r̃⟩=⟨q,a⟩+⟨q,r̃⟩.Rslm4Lite has zero storage overhead for the residual scale; other variants store one 2-byte scale per vector.
  • 3.5.2 Global Scaling: RelApproxGlobal scales the combined approximation to correct accumulated error and restore the original vector length.
  • 3.5.2 Global Scaling: Global scaling stores s=||x||_2/||a+r̃||_2 and uses a 2-byte UE4M12 float, with zero metadata overhead in the Lite variant.The final score is s(⟨q,a⟩+⟨q,r̃⟩).

4 Evaluation

The evaluation uses ranking-centric recall metrics, with Recall@20@30 as the default, and tests codecs across diverse datasets under a brute-force protocol that isolates quantization effects. Comparisons include established rescoring and approximate-vector codecs, including Faiss and ScaNN systems.

  • 4.1 Quality Metrics Used: The evaluation reports Recall@20@30, Recall@20@40, Recall@20@20, and 1%-Tolerant Recall@20.Recall@20@40 is described as more lenient and useful for downstream post-processing.
  • 4.1 Quality Metrics Used: Recall@20@30 is the default metric, chosen to tolerate benign ranking perturbations while capturing genuine quality failures.The paper contrasts it with strict Recall@20@20 and 1%-Tolerant Recall@20.
  • 4 Evaluation: Codecs are evaluated on five standardized datasets spanning dimensionalities, dataset sizes, and coordinate distributions.The quality protocol uses 500 queries per dataset and evaluates ranking on each query’s ground-truth top-500 candidate pool.
  • 4 Evaluation: The brute-force evaluation decouples quantization loss from index partitioning errors by scoring isolated ground-truth candidate pools.The authors also verify in practice that limited quantization error rarely promotes candidates outside the top-500 into the top 20 or 30.
  • 4 Evaluation: Comparisons include SQ8, SSQ4Lite, 4-bit Turboquant, and reference algorithms EDEN, TurboQuant, and BlockQuant.The study also compares end-to-end against Faiss and ScaNN on glove and openai, where approximate vectors are encoded.

5 Results

Across full-vector and residual quantization, Rslm maintains high recall at low bitrates, with residualization substantially reducing recall loss. Its norm correction, training-free design, and implementation choices support efficient ANN scoring and rescoring.

  • Full Vector Quantization: Rslm4 and TurboQuant exceed 99% recall on wiki_full and openai, while exceeding 92% on bigann; unrotated codecs suffer severe drops.The unrotated Slm44 and SSQ4Lite results are especially poor on wiki_full, bigann, and openai, where coordinate means and variance skew hurt recall.
  • Full Vector Quantization: On wiki_full (D=3072), 3-bit and 2-bit codecs achieve 99% and 94% recall, respectively, as higher dimensionality reduces quantization-noise impact.The reported signal-to-noise relationship supports reducing one bit per dimension when dimensionality is quadrupled, on average.
  • Relative Vector Quantization: Relativized 2-bit Rslm achieves 99.3%+ recall@20@40 on four of five datasets, while 1-bit reaches 100% on wiki_full and 99.4% on openai.The lowest-dimensional glove dataset is the exception at 97.7% recall@20@40 for the relativized 2-bit encoding.
  • Relative Vector Quantization: Fixing the norm of the full reconstructed vector is critical for MIPS ranking, with RelApproxGlobal significantly outperforming RelApprox encodings.The full reconstructed vector combines the partition center and decoded residual before further residual quantization.
  • End-to-End Comparison: Rslm matches or exceeds trained Faiss and ScaNN codecs while avoiding k-means training, and its low-bit codecs outperform them in end-to-end comparisons.At nprobe = 4096, Rslm1_Global reaches 54.0% recall, versus 45.6% for ScaNN AVQ and 42.1% for Faiss PQ.

6 Conclusions

Rslm combines residual-focused, training-free quantization with final-vector norm correction to reduce ANN resource demands while preserving or improving recall. Its hardware-efficient implementation and empirical results support simpler, lower-cost ANN architectures.

  • 1–4 bits per dimension and residual encoding reduce memory resources and address memory-bandwidth bottlenecks in large-scale ANN search.The codecs are optimized for residual vectors, with reported 2× to 4× improvements available as direct savings or as capacity for other optimizations.
  • Final reconstructed-vector L2 norm correction preserves MIPS geometric integrity and experimentally outperforms complex anisotropic loss formulations at low bitrates.Rslm corrects the final reconstructed vector rather than only the residual.
  • Block-wise cascaded FWHT, codebooks of at most 16 entries, and hidden 16-bit scale factors provide hardware-efficient processing and cache-line alignment.The implementation targets linear-like transform complexity, AVX SIMD execution, and production throughput.
  • Training-free codecs match or exceed the semantic recall of Faiss PQ and ScaNN AH without offline k-means training.The result applies to both approximate scoring and rescoring phases of ANN systems.
Loading 2608.30384v1…