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

From distance error to a concrete choice

Vector search repeatedly chooses which candidate is closer and which edge should remain. Average error and global rank correlation do not explain why these local decisions fail, so this work analyzes the comparisons executed by the algorithm itself.

The key quantities are the original margin between candidates and whether quantization error can cross it. The analysis separates risk near the decision boundary from the tail behavior of calibrated residuals, including correlations induced by a shared query or graph node.

Connecting local decisions to a graph trace

For Vamana neighbor selection under a fixed candidate order, the paper connects agreement on individual pruning decisions with agreement of the final neighbor list on a frozen exact state.

When distributional assumptions are unreliable, independent held-out blocks provide risk estimates for a fixed quantization rule. Binary codes, RaBitQ, Lucene BBQ, and product quantization can be studied through the same decision interface.

Choosing quantization for the search process

Across learned, classical, and synthetic representations, normalized comparison margins predict ranking and pruning flips better than global rank correlation. The scope covers fixed candidate sets and frozen traces; end-to-end recall also depends on candidate coverage.