Metraipolis › archive › dc_b0add188ef09

When Does Low-Bit Quantization Preserve the Decisions of Vector Search? — arXiv:2609.09854

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.09854
License (as archived)
CC0-1.0
Archived
2026-10-16T10:56:52.272Z
SHA-256 of the archived text
5c9b19690f883a027eb7ef06252956d423966c842ef824a446cd3ce423b5c46b
Stable URL of this page
https://metraipolis.com/documento/dc_b0add188ef09

How to cite

When Does Low-Bit Quantization Preserve the Decisions of Vector Search? — arXiv:2609.09854 — arXiv (en), https://arxiv.org/abs/2609.09854 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b0add188ef09 (Metraipolis archive dc_b0add188ef09, sha256 5c9b19690f883a027eb7ef06252956d423966c842ef824a446cd3ce423b5c46b)
BibTeX
@misc{dcb0add188ef09,
  title = {When Does Low-Bit Quantization Preserve the Decisions of Vector Search? — arXiv:2609.09854},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.09854},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b0add188ef09; sha256 5c9b19690f883a027eb7ef06252956d423966c842ef824a446cd3ce423b5c46b},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.09854. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-10 in cs.IR).
Categorie arXiv: Databases (cs.DB) ; Information Retrieval (cs.IR); Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.09854 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T10:02:15.211Z dalla pagina https://arxiv.org/catchup/cs.IR/2026-09-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).