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

Wenxuan Xiao; Xu Cao

Source-linked AI summary

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

Wenxuan Xiao, Xu Cao

arXiv:2609.09854v1Sep 9, 2026cs.DBcs.IRcs.LG

TL;DR

The paper argues that low-bit vector-search quality depends on decision-boundary margins and shared residual structure, not a single global fidelity measure. It develops boundary–residual, covariance-aware, geometric, and held-out certificate analyses, showing why quantizer selection should use decision-level diagnostics.

Problem
Low-bit vector search cannot be understood through a single fidelity number because global metrics erase boundary concentration and shared noise structure in flipping decisions.
Method
The paper combines a distribution-free boundary–residual decomposition, covariance-aware residual analysis, frozen-trace coupling, geometric models, rare-contamination analysis, and held-out selective certificates.
Results
Standardized margins and decision-level flip rates distinguish quantizers and representations that global fidelity metrics cannot, while rotation can improve global fidelity yet worsen local decision risk.
Takeaways & Limitations
Select and evaluate quantizers on the decision population of the intended index using standardized margins and flip rates, with held-out certificates when analytical assumptions are unavailable.
Takeaways & Limitations
Weak Gaussian diagnostics alone do not establish the residual tails required by the analysis, so the analytical route is paired with a model-free held-out approach.

Abstract

from arXiv · show

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.

1 Introduction

Low-bit quantization preserves vector-search decisions unevenly because algorithms consume boundary-crossing comparisons, not aggregate score fidelity. The paper analyzes exact margins, calibrated residuals, their dependence, and frozen graph traces, while covering multiple quantizer families and fixed-candidate scope.

Motivation: 95% versus 2% recall at ten neighbours shows that the same two-bit coordinate index behaves sharply differently on Cohere-768 and GIST-960 embeddings.Classical sign-code analysis does not predict either result.
Motivation: Small-margin comparisons govern ranking and pruning outcomes, so mean squared error, rank correlation, and end-to-end recall do not expose the relevant decision risk.The paper therefore studies binary comparisons and their decision boundaries.
Contributions: 0.013 versus 0.036 measured difference-error standard deviation shows how shared residual covariance can reduce comparison noise despite individual errors of 0.024 and 0.027.The pooled residual correlation is 0.87, while omitting covariance produces the larger value.
Contributions: The framework decomposes flips into exact-margin mass near zero and calibrated-residual tails, then adds covariance-aware bounds and deterministic frozen-trace composition.The theory requires no distributional assumption for the initial decomposition and supports ranking, pruning, and Vamana traces.
Scope: A held-out block certificate provides finite-sample selective-risk bounds without analytical assumptions, while RaBitQ, Lucene BBQ, and product quantizers share the decision interface.The scope is fixed candidate sets and frozen execution traces; end-to-end candidate coverage remains outside the paper.

2 Related Work

Related work studies binary-code similarity, graph navigability, representation geometry, and concentration, whereas this paper focuses on whether quantization preserves the local decisions consumed by search algorithms. It combines established concentration tools with covariance-aware residual analysis and model-free certification.

Binary codes and random projections: SimHash analyzes random-hyperplane sign codes, while this paper targets fixed coordinate axes whose learned-encoder variances can differ substantially.RaBitQ instead provides a pointwise bound for a randomized ratio estimator.
Graph-based nearest-neighbour search: HNSW, Vamana, and QuIVer use candidate sorting and diversity pruning, but the paper analyzes preservation of those local decisions through a deterministic selection-state coupling.This differs from navigability theory based on random-graph or geometric assumptions.
Contrastive representation geometry: An exact Gaussian oracle motivates the representation analysis, while approximate Gaussian diagnostics alone do not transfer its identities or tail guarantees without error control.The related representation result supplies motivation rather than an automatic justification for the paper’s conclusions.
Concentration and margin conditions: The framework combines boundary-plus-tail analysis with sub-Gaussian, sub-gamma, Efron–Stein, and empirical Bernstein tools, adding role-specific residuals and covariance-aware scales.The stated novelty is their combination for algorithmic comparisons.

3 Decisions, Boundaries, and Residual Tails

Vector-search failures occur when quantized decision functionals disagree in sign, especially near small exact margins. The paper separates boundary mass from residual tails, models shared-query and shared-node dependence, and compares analytical and empirical routes for ranking and pruning.

Setup: A quantized search step fails when the exact and approximate decision functionals disagree in sign, covering ranking, pruning, and stopping tests.The same interface supports the paper’s different theoretical results.
3.1 Setup and the main decomposition: The boundary–residual decomposition separates flip risk into probability mass near zero exact margins and calibrated-residual tail probability without requiring independence between residual and margin.The conservative flip event treats an approximate tie against a non-tied exact decision as failure.
Margin geometry: Margin fits give β = 1.526 on Cohere, 1.500 on MiniLM, and 1.595 on GIST, with the boundary exponent identical for one- and two-bit codes on each dataset.This allows boundary mass to be estimated before selecting a quantizer.
Ranking and pruning: Ranking residuals share a quantized query, whereas pruning residuals share a graph node; covariance-aware identities and joint sub-Gaussian proxies therefore use role-specific scales and bias terms.A shared additive calibration intercept cancels in ranking differences but survives pruning as (1 −α)b.
Covariance-aware analysis: On inspected selected pairs, omitting empirical covariance overstates difference variance by 7.4×, while a plug-in bound of 0.55 covers the observed 5.8% Cohere two-bit flip rate.The plug-in diagnostic is distinct from the analytical MGF assumption.
3.3 Pruning: role-specific residuals: Every observed pruning disagreement in the sampled configurations is a false keep, showing that the two pruning error orientations behave differently on real data.Structural ties require explicit treatment because a no-atom condition does not control disagreement there.

4 From Local Decisions to Algorithmic Traces

The paper lifts local comparison guarantees to frozen Vamana executions by treating selection as a deterministic state machine. Exact edge and path certificates then retain only the comparisons needed for the output, although numerical additive bounds can be loose.

4.1 Frozen traces: A semantic trace records the shared permutation, visited candidates, selected prefixes, candidate actions, and termination state, separating logical coupling from implementation-specific short-circuit order.The standard non-saturated call is analyzed before any deterministic refill map.
4.2 The coupling theorem: For a frozen candidate permutation, approximate Vamana replay returns the exact neighbour list if and only if every candidate-level pruning action agrees on the frozen exact state.The first disagreement identifies the exact divergence point, and no cross-comparison independence is needed.
4.3 Dependency slicing, edge certificates, and what they show: An edge survives when all candidate actions in its exact prefix agree, and fixed paths obtain certificates by composing such edge-level conditions.Backward slicing removes comparisons irrelevant to the selected edge.
4.3 Dependency slicing, edge certificates, and what they show: 0.81, 0.69, and 0.73 Spearman correlations show that plug-in risk sums rank observed edge failures on Cohere, MiniLM, and GIST.The logical certificate was exact in every tested case, although the additive bound saturated at one for 89–92% of edges.
4.3 Dependency slicing, edge certificates, and what they show: Keeping only the r largest individual risks improves query-failure correlation up to r = 3 to 5, but the full sum remains the valid upper bound.Examples include Cohere two-bit 0.471 → 0.480, MiniLM one-bit 0.460 → 0.500, and rotated MiniLM two-bit 0.589.

5 From Representations to Residual Laws

The section develops a Gaussian oracle for quantization residuals, identifies covariance and representation structure as important, and shows why weak Gaussian diagnostics alone cannot guarantee useful tails.

Gaussian representation bridge: 31–38% of predicted ranking signal comes from off-diagonal covariance, despite mean coordinate correlations of only 0.04–0.11.The full covariance matrix, rather than only its diagonal, is needed for the Gaussian ranking prediction.
Magnitude-bit gain: ρ(S2, T) > ρ(S1, T) for every D ≥1, σ_i > 0, and finite τ > 0 in the aligned bilinear model.The gain applies to the best aligned readout; a mismatched fixed scorer instead loses 0.163 correlation in an eight-dimensional example.
Magnitude-bit gain: +0.071 to +0.132 global ranking fidelity accompanies the second bit, while Cohere’s 3σ residual survival ratio falls from 2.09 to 1.05 and pairwise flips decrease 34.5%.These empirical effects are reported for the inspected contrastive embeddings and Cohere data.
Oracle limits: The threshold remainder is 1.3–4.7% of role variance on Cohere and MiniLM but essentially all of it on unrotated GIST, falling to 2.3% after rotation.The remainder serves as a diagnostic of whether the Gaussian oracle describes the representation.
Oracle limits: Fixed-dimensional Gaussian marginals, thin-shell concentration, isotropic covariance, and vanishing boundary occupancy still permit residuals without useful exponential tails.The counterexample shows that concentration requires control of coordinate influence, conditional cumulants, or truncated range.

6 Selective Certificates from Held-Out Blocks

This section provides held-out certificates for selective quantized decisions when analytical residual-tail assumptions are unavailable, using independent blocks and frozen selectors.

Selective certification: Held-out certificates bound selective failure risk for retained decisions and route low-standardized-margin cases to exact verification.The approach remains applicable when Gaussian diagnostics fail, residual tails are heavy, or calibration is degenerate.
Certificate limits: Zero empirical coverage yields no certificate because the accepted-coverage denominator must be positive.The ratio-based guarantee is defined only when empirical accepted coverage is nonzero.
Certificate forms: The direct certificate targets observed failures of the frozen rule and is tighter than the union certificate, which preserves the boundary-plus-residual mechanism.Both certificates bound the same selective failure quantity through different events.
Protocol: Each reported point uses an independent fit split, prespecified certification prefixes, and 1,024 independent validation blocks with 1−δ marginal validity.Blocks contain one query or target with 32 sampled candidates, and methods and sample sizes are fixed in advance.

7 Quantizer Instantiations

The quantizer instantiations share one decision interface while supplying family-specific residual mechanisms, and cross-quantizer results show that high interface fidelity does not eliminate hard-margin flips.

Coordinate binary codes: Coordinate binary codes use covariance, threshold, magnitude-bit, rotation, and conditional-MGF analyses specific to that family.These analytical components do not automatically transfer to other quantizers.
RaBitQ: RaBitQ handles shared-rotation dependence through joint events and triangle inequalities rather than independence assumptions.For raw squared distances, radial factors modify the corresponding distance rule.
Lucene BBQ: Lucene BBQ requires role-specific affine calibration because stored vectors are one-bit while query-role vectors are int4 during HNSW construction.The reference scorer reproduces these role semantics rather than Lucene’s metric-specific corrections.
Product quantization: Product quantization enters through bounded-block concentration or held-out survival laws, while the coordinate-sign Stein identity does not transfer.Its residual is decomposed over codebook blocks.
Cross-quantizer validation: 10.1% of ranking decisions still flip in the hardest fifth of margins for scalar int4, despite edge correlation of 0.997 and 2.1% overall ranking flips.Increasing the bit budget shrinks residuals but does not move the decision boundary.

8 Experiments

Experiments show that standardized exact margins, residual dependence, and frozen-trace analysis explain quantized decision failures better than global fidelity, while held-out certificates and Gaussian diagnostics reveal both reliable regimes and analytical limits.

8.2 Standardized margins predict local failures: Flip rates declined monotonically with standardized margin on Cohere, with no observed flips above M = 5.The relationship held across more than two orders of magnitude in standardized margin.
8 Experiments: Spearman correlations of 0.970 for ranking and 0.992 for pruning predicted held-out flip rates, versus 0.739 and 0.053 for global distance Spearman correlation.Distance mean squared error correlations were 0.184 for ranking and 0.447 for pruning.
8.4 Trace coupling and its consequences: All 960 sampled selection calls obeyed the frozen-trace identity: output disagreement occurred exactly when some candidate-level pruning action differed.Every sampled triple disagreement was a false keep, while no false prune occurred at α = 1.2.
8.5 Held-out selective certificates: Held-out certificates were issued for every configuration, while selective retention reduced mean ranking flips from 8.58% to 5.27% and pruning flips from 3.84% to 0.12%.The certificate guarantee was evaluated separately from the empirical validation reduction.
8.6 Rotation: global fidelity does not determine decision risk: Rotation improved Cohere distance fidelity from 0.576 to 0.926 but increased anchor-protocol two-bit flips by half, while block-protocol pruning flips decreased.Rotation reduced marginal error variance but also reduced shared-query correlation, increasing comparison-residual standard deviation by 11% on the anchor protocol.
8.7 The analytical regime and its edge: The Gaussian oracle matched measured residual variances within 4.6% across twelve configurations, but joint-law diagnostics only partially supported its applicability.GIST exposed a failure regime with residual kurtosis 26 and a left tail 7.7 times Gaussian before rotation.
8.9 Necessity and falsifiability: The rare-contamination construction separated global fidelity from decision risk: lower mean squared error still accompanied 10.00% rather than 5.09% decision flips.The two perturbations had Spearman correlation 0.9860282 with exact scores, while the hardest fifth flipped 50.00% versus 23.91%.

9 Discussion: Practical Guidance

The paper recommends selecting and certifying quantizers on the decisions an index actually makes, using standardized margins and covariance-aware or held-out risk estimates rather than global fidelity alone.

Practical guidance: A per-decision score M = cQΓ/v provides an offline reliability audit: M > 5 had no observed flips, whereas M < 1 flipped more than a quarter of the time.An online router would additionally need an observable margin lower bound or residual envelope.
Practical guidance: Quantizers should be piloted on the intended decision population because a rotation can improve global fidelity while changing local flip rates in opposite directions across protocols.The paper specifically recommends measuring standardized margins and flip rates before choosing a quantizer.
Practical guidance: Sign entropy alone cannot determine code usability: Cohere and SIFT have nearly identical entropy and rotation responses despite sharply different coordinate-code outcomes.The paper pairs the entropy gap with an eligibility diagnostic rather than treating sign entropy as sufficient.
Practical guidance: Block certificates are population statements for their calibration distribution and do not transfer across distribution shift without recalibration.Union-event certificates expose the boundary-plus-residual mechanism, while direct-failure certificates are tighter at higher coverage.
Practical guidance: Open questions include characterizing trace-length saturation from representation geometry, extending coupling to adaptive candidate sets, and selecting quantizer settings from covariance statistics alone.

10 Conclusion

The framework explains decision stability through boundary margins, residual structure, and frozen algorithmic traces rather than a single fidelity metric. It also provides held-out certificates when analytical assumptions fail, while clearly delimiting what remains outside the analysis.

10 Conclusion: The framework combines a boundary–residual decomposition, covariance-aware analysis, frozen-trace coupling, Gaussian representation models, and held-out selective-risk certificates.These components connect local quantization errors to ranking and pruning decisions across analytical and empirical regimes.
10 Conclusion: Held-out block certificates bound selective risk when analytical residual-tail assumptions are unavailable.The certificate applies to a frozen quantized rule and supports routing uncertain decisions to exact verification.
10 Conclusion: The analysis does not cover candidate generation, graph navigability, or distribution shift, and its Gaussian identities remain oracle results.Trace certificates can also saturate on long paths, while held-out certificates require representative independent blocks and exact margins for selection.

Reproducibility

The paper’s reproducibility materials expose the mathematical assumptions, deterministic replay conditions, covariance identities, and certificate procedures needed to audit decision-level claims. These results distinguish exact identities from assumptions required for statistical interpretation or concentration.

Reproducibility: The released experiments use fixed seeds, disjoint data pools, numbered non-interactive modules, and machine-readable outputs, preserving negative and vacuous results.The protocol is organized across representation diagnostics, covariance, pruning replay, Gaussian audits, certificates, and quantizer interfaces.
Reproducibility: Covariance identities hold deterministically for observed row dependence, but interpreting their components as population estimators requires a sampling model.A fixed anchor has zero conditional covariance and undefined within-query correlation, while the MGF proxy is a separate input.
Reproducibility: Pruning disagreements include false keeps, false prunes, and a separate directional event at exact structural ties.A no-atom residual condition rules out exact approximate ties but does not control disagreement at an exact structural tie.
Reproducibility: For frozen permutations, approximate Vamana replay matches the exact list exactly when every candidate-level action agrees on the corresponding frozen exact state.The first action disagreement identifies the divergence point, enabling composition from local actions to traces, edges, and paths.
Reproducibility: The residual-tail routes include analytical concentration, exact-covariance conditions, and empirical calibration on independent blocks.The decision theorem accepts any route, but the routes require different inputs and the coarse Gaussian quadratic-form route can be loose on real embeddings.

E.2 Aligned magnitude-bit theorem

The aligned magnitude-bit analysis relates representation geometry to scorer correlation through an oracle kernel and covariance decomposition. It shows that the magnitude bit can help under alignment, but the gain is not universal and certificate guarantees remain separately empirical.

E.2 Aligned magnitude-bit theorem: The Gaussian oracle uses coordinate thresholds and truncated-normal quantities to analyze the magnitude-bit scorer’s covariance and variance.The kernel is decomposed through first-order and degenerate Hoeffding components, while shared-node edges contribute covariance.
E.2 Aligned magnitude-bit theorem: The aligned model’s strict magnitude-bit correlation gain depends on alignment between the target and scorer.A fixed readout can lose when the added magnitude bit amplifies coordinates ignored by the target.
E.2 Aligned magnitude-bit theorem: For L = 8, the two-bit minus one-bit Pearson correlation is −0.162687 when the second bit amplifies four target-irrelevant coordinates.This counterexample establishes that the magnitude-bit benefit is not representation-independent.
E.2 Aligned magnitude-bit theorem: The three residual-tail routes bound the same decision residual with different assumptions, and held-out empirical calibration avoids requiring an analytical tail.Selective certificates still require independent blocks and positive population coverage.
E.2 Aligned magnitude-bit theorem: Shared rotations couple ranking and pruning residuals, so their guarantees use joint events and union bounds rather than independence.Distance transformations can also change pruning parameters when rules are expressed in squared Euclidean distance.

H.1 Rare-contamination counterexample

The rare-contamination construction shows that strong marginal Gaussian diagnostics and concentrated geometry do not guarantee the residual tails needed by the oracle. The broader experiments separate replacement variance, representation regimes, certification behavior, and operational failure modes.

H.1 Rare-contamination counterexample: Rare contamination can remain close to Gaussian in every fixed coordinate block while producing a large normalized fourth moment and violating the required residual-tail behavior.The construction uses contamination probability vanishing with dimension, preserving covariance and marginal diagnostics while creating rare high-impact ranking events.
H.1 Rare-contamination counterexample: The contamination construction is a logical obstruction: marginal Gaussianity, thin-shell concentration, and isotropic spectra are insufficient without additional concentration ingredients.Approximate Gaussian diagnostics therefore cannot transfer the oracle’s identities or tails without error control.
H.1 Rare-contamination counterexample: Replacement variance is controlled through first-order and degenerate components, with the Efron–Stein quantity lying between the variance and twice the variance.The bound is tight at the extreme cases where only degenerate pair structure remains.
H.1 Rare-contamination counterexample: Representation diagnostics distinguish rotation response from code eligibility: similar entropy gaps can coexist with different usability of coordinate binary quantization.Cohere and SIFT have nearly identical entropy-gap and rotation-response statistics, yet only Cohere is reported as usable for the unrotated code.
H.1 Rare-contamination counterexample: Operational tests find that local action disagreements can cause nearly universal fixed-order output divergence in append-only pruning, while certificates remain sufficient but conservative.Path certificates saturate within two hops, and certificate values must be interpreted alongside retained coverage.