← 研踪 PaperTrailarXiv:2609.09854 · v2
When Does Low-Bit Quantization Preserve the Decisions of Vector Search?
首次提交 2026-09-09 16:06
版本更新 2026-11-11 22:23
雷达观测 2026-11-13 11:11
摘要
An orthogonal rotation improves the distance rank correlation of two-bit Cohere codes from 0.75 to 0.91, yet increases nearest-neighbour comparison flips by 51%. We analyse quantization through the comparisons made by graph search. A comparison changes only when its quantization error exceeds its exact margin, giving a flip bound that separates close calls from large errors. Shared endpoints induce correlated distance errors that partly cancel within a comparison. An exact replay identity connects candidate-level actions to the output of neighbour selection. A Gaussian model gives coordinate-code errors in closed form, and a rare-spike construction exposes heavy tails in the population-radius error. Held-out blocks give model-free certificates for acceptance rules based on exact or quantized margins. Across 24 dataset-code configurations, calibration-estimated risk correlates with held-out ranking and pruning flips at 0.97 and 0.99, compared with 0.91 and 0.99 for a margin-to-noise summary and 0.74 and 0.05 for distance rank correlation. Paired builds of 200,000-vector graphs connect rotation, query scoring, and topology to end-to-end recall and search work.
作者备注：51 pages, 5 figures; substantially revised with expanded theory, calibration controls, and graph-search experiments
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-11 22:23 · 最新观测版本
When Does Low-Bit Quantization Preserve the Decisions of Vector Search?
An orthogonal rotation improves the distance rank correlation of two-bit Cohere codes from 0.75 to 0.91, yet increases nearest-neighbour comparison flips by 51%. We analyse quantization through the comparisons made by graph search. A comparison changes only when its quantization error exceeds its exact margin, giving a flip bound that separates close calls from large errors. Shared endpoints induce correlated distance errors that partly cancel within a comparison. An exact replay identity connects candidate-level actions to the output of neighbour selection. A Gaussian model gives coordinate-code errors in closed form, and a rare-spike construction exposes heavy tails in the population-radius error. Held-out blocks give model-free certificates for acceptance rules based on exact or quantized margins. Across 24 dataset-code configurations, calibration-estimated risk correlates with held-out ranking and pruning flips at 0.97 and 0.99, compared with 0.91 and 0.99 for a margin-to-noise summary and 0.74 and 0.05 for distance rank correlation. Paired builds of 200,000-vector graphs connect rotation, query scoring, and topology to end-to-end recall and search work.
查看此版本解读 →查看此版本原文 ↗