cs.DBSep 9, 2026

When Does Low-Bit Quantization Preserve the Decisions of Vector Search?

Authors: Wenxuan Xiao, Xu Cao

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Low-bit quantization can achieve high recall on some vector representations and fail sharply on others, while average distortion and global rank correlation do not explain the difference. We study quantized vector search at the level of the comparisons consumed by ranking and graph-pruning algorithms. Our first result is a distribution-free decomposition: the probability that a comparison flips is bounded by the probability mass of exact margins near zero plus the tail probability of the calibrated residual. We then account for dependence between residuals that share a query or graph node, and derive covariance-aware second-moment identities and tail bounds under a joint MGF proxy. For a frozen candidate permutation, we prove a deterministic coupling theorem for Vamana neighbour selection: the approximate replay returns the exact neighbour list exactly when all candidate-level pruning actions agree on the frozen exact states. We connect these results to representation geometry through an exact Gaussian oracle, establish a strict correlation gain from a deterministic magnitude bit in an aligned bilinear model, and give a rare-contamination construction showing why marginal Gaussian diagnostics do not imply the required residual tails. When analytical assumptions are unavailable, a held-out block certificate bounds the selective failure risk of a frozen quantized rule. Across learned, classical, and synthetic embeddings, standardized exact margins predict held-out ranking and pruning flip rates substantially better than global rank correlation. The framework applies to coordinate binary codes, RaBitQ, Lucene BBQ, and product quantizers through a common decision interface.

Explore similar work

CardsList
Aug 31, 2026cs.LG

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

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 L2L_2 norms of quantized vectors. Our major innovation is that we correct the L2L_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.
Rastislav Lenhardt, Teodora Dobos, Thomas Vecchiato +2
Calibration-Free Low-Bit Vector QuantizationApproximate Nearest-Neighbor SearchVector DatabaseEmbedding DimensionLow-Rank FactorizationCodec+1
AskPDF
May 17, 2026cs.LG

Covariance Structure and Coordinate Heterogeneity Govern Binary Quantization of Contrastive Embeddings

Binary quantization (BQ) compresses high-dimensional embeddings into one or two bits per coordinate, enabling nearest neighbor search at extreme speed. Yet a striking puzzle persists: BQ achieves competitive recall on contrastive embeddings but fails on others -- and two leading systems adopt diametrically opposite strategies (random rotation vs. preserving coordinate axes) without a common theory explaining when each is appropriate. We address this puzzle by connecting the Gaussian structure recently established for InfoNCE-trained representations to a statistical framework for BQ quality. Our analysis reveals two distinct roles of the covariance matrix. First, the full covariance structure -- not merely its diagonal -- determines the absolute level of ranking fidelity, with off-diagonal correlations contributing 30--50% of the signal. Second, coordinate heterogeneity (the non-uniformity of per-coordinate variances) governs key design choices: how much each additional bit contributes, and whether random rotation helps or hurts. We derive approximate expressions for ranking fidelity under a Gaussian model, show that the magnitude bit carries information proportional to heterogeneity, and show that random rotation destroys precisely the signal that one paradigm exploits while creating the isotropy that the other requires. A phenomenological scaling law predicts fidelity across models and dimensions. Experiments on 18 datasets spanning 9 embedding families support the main predictions and provide, to our knowledge, the first principled design guide for binary quantization systems.
Wenxuan Xiao
QuantizerEmbedding DimensionCovariance EstimationLow-Rank FactorizationHeterogeneity
AskPDF
Jun 10, 2026cs.IR

What Limits Does Quantization Place on Dense Top-kk Retrieval? A Theoretical Study

We establish conditions for embedding a corpus of NN documents as dd-dimensional vectors such that every kk-subset S⊆[N]S \subseteq [N] is realizable as a result of top-kk retrieval by some query vector. Recent work shows that d=O(k)d = O(k) suffices for such embeddings to exist in Rd\mathbb{R}^d, independently of NN. We theoretically prove that this corpus-independent bound is specific to infinite precision. With BB bits per coordinate, perfect top-kk retrieval requires Bd=Ω(kln⁡N)Bd = Ω(k \ln N); thus, at any fixed precision, the dimension must grow at least logarithmically with NN. Specializing to a ℓ2\ell_2-normalized BB-bit uniform scalar quantization model, we also identify a threshold on the precision B∗=O(ln⁡ln⁡N)B^{*} = O(\ln \ln N) below which no dimension suffices, together with two further regimes that bound the feasible (B,d)(B, d) pairs. Our result implies that in practical vector databases and dense retrieval systems where quantization is standard, the embedding dimension and possibly the precision must grow with the corpus size.
Koki Okajima, Tsukasa Yoshida
Vector DatabaseTop-KQuantizationText Corpora
AskPDF