Low-bit quantization accuracy depends on exact margin distributions
When Does Low-Bit Quantization Preserve the Decisions of Vector Search?
DatabasesInformation RetrievalMachine Learning
Summary
Low-bit quantization is a way to make searching large sets of vectors faster by using fewer bits per number. The authors found that average distortion and overall ranking similarity don’t fully explain why quantization works well sometimes and fails badly other times. They developed new mathematical tools to understand when decisions in vector search stay the same after quantization, focusing on how small differences between vectors and their neighbors affect errors. Their framework helps predict when quantization will keep the right search order by looking at exact margins rather than just rough rank correlations.
What this means in practice
- •For search engine developers: Design quantization schemes that reliably preserve search result order to maintain high recall in large-scale vector retrieval.
- •For machine learning engineers: Use margin-based diagnostics to select or tune low-bit vector representations for retrieval tasks with fewer rank order errors.
Authors
Wenxuan Xiao, Xu Cao
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.