arXiv CSopen access

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

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

[email protected]

Astrmira Tech.

Xu Cao

[email protected]

arXiv:2609.09854v1 [cs.DB] 9 Sep 2026

Astrmira Tech.

Abstract The same two-bit coordinate code that recovers 95% of exact nearest neighbours on Cohere text embeddings recovers 2% on GIST image descriptors. Average distortion does not explain the gap. A graph-based search algorithm never consumes a distance estimate on its own; it consumes comparisons, and a comparison fails only when quantization noise crosses the specific decision boundary that the comparison sits on. We develop a theory of low-bit vector search at this level. The first result is a distribution-free decomposition: the probability that a comparison flips is at most the probability mass of exact margins near zero plus the tail probability of the calibrated residual. Global fidelity metrics average over both quantities and therefore cannot separate them. The second result treats residual dependence induced by shared structure. In the inspected Cohere selected-pair population, residuals sharing a query have strong pooled correlation, and the measured variance of their difference is 7.4 times smaller than the sum of their marginal variances. The third result is a deterministic coupling theorem for the neighbour-selection call of Vamana: for a frozen candidate permutation, the approximate replay produces the same neighbour list exactly when every candidatelevel pruning action agrees with the exact one, and the first disagreement identifies the edge at which the outputs diverge. We connect these decision-level results to representation geometry through an exact Gaussian oracle. Stein’s lemma gives a closed-form sign–linear covariance identity and shows how off-diagonal covariance enters the ranking signal; an aligned bilinear model yields a strict correlation gain from a deterministic magnitude bit; and a rare-contamination construction proves that marginal Gaussianity, thin-shell concentration, and regular spectra cannot by themselves imply the exponential tails the bounds require. For representations outside the analytical regime, a held-out block certificate bounds the selective failure risk of a frozen quantized rule from data alone. On learned, classical, and synthetic embeddings, standardized exact margins predict held-out flip rates with Spearman correlation 0.97 for ranking and 0.99 for pruning, against 0.74 and 0.05 for global rank correlation. The coupling identity holds in all 960 sampled selection calls. Direct-ratio selective certificates at 512 blocks average 16.7% for ranking and 18.7% for pruning; no selected empirical validation risk exceeds its certificate. A random rotation raises Cohere’s global rank fidelity from 0.58 to 0.93 while leaving one held-out flip rate unchanged and raising another by half, so fidelity does not determine the sign of the change in decision risk. The framework covers coordinate binary codes, RaBitQ, Lucene BBQ, and product quantizers through a common decision interface. Keywords: vector search, binary quantization, decision stability, concentration inequalities, contrastive representations ©2026 Wenxuan Xiao and Xu Cao. License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/.

Xiao and Cao

1 Introduction Binary quantization compresses a 768-dimensional float vector to 96 bytes and replaces most floating-point distance arithmetic with packed integer operations. Two recent systems exploit low-bit codes with opposite strategies. QuIVer (Xiao et al., 2026) keeps the coordinate axes of the encoder and builds and searches a proximity graph directly on twobit scores; RaBitQ (Gao and Long, 2024) applies a random rotation before one-bit coding and corrects the estimate. Both reach competitive recall on their benchmarks. Yet the two-bit coordinate index of QuIVer reaches 95% recall at ten neighbours on Cohere-768 embeddings and 2% on GIST-960 descriptors (Xiao et al., 2026), and the classical analysis of sign codes does not predict either number: the SimHash collision law (Charikar, 2002) describes random projection directions, not the fixed coordinate axes of a trained encoder, and it says nothing about how the training objective shapes those axes. The right level of analysis. Prior work measures score fidelity: how well approximate distances track exact ones, summarized by mean squared error, Spearman correlation, or end-to-end recall. A graph algorithm does not consume scores in this form. It executes a sequence of binary comparisons (sort these candidates, prune that edge, advance along this path), and a comparison has consequences only when it crosses its decision boundary. Two features of this setting are invisible to fidelity metrics. First, the comparisons that matter have small margins, because candidate sets are selected to be close to the query. Second, the two residuals entering a comparison can be dependent because the corresponding distances share a query or graph node, so the variance of their difference includes a covariance term. Example 1 (Shared error cancels in a comparison) On Cohere embeddings with twobit codes, the calibrated errors of the two distances in a nearest-neighbour comparison have standard deviations 0.024 and 0.027 in cosine-distance units. Their measured difference has standard deviation 0.013, compared with 0.036 after omitting the empirical covariance term; the pooled residual correlation is 0.87. A metric that averages individual distance errors does not expose this difference residual. This paper develops the theory at the level of individual comparisons: their exact margins, their correlated residuals, and the way they compose inside a graph algorithm. Contributions.

The results form four layers.

1. A decision-level risk decomposition (§3). For any comparison with exact value Ψ and calibrated residual R, P(flip) ≤ P(0 < |Ψ| ≤ τ ) + P(|R| ≥ cτ ) | {z } | {z } boundary mass

residual tail

for every τ > 0, with no distributional assumption. Instantiated for ranking and for Vamana pruning, the difference residual has an exact covariance-aware secondmoment identity and admits a tail bound under a joint MGF proxy. On the inspected Cohere selected pairs, omitting empirical covariance overstates the measured difference variance by a factor of 7.4. 2

Low-Bit Decision Stability in Vector Search

2. Frozen-trace composition (§4). A Vamana selection call is a deterministic state machine: a candidate ordering, a sequence of pruning actions, and a neighbour list. For a frozen ordering, the approximate replay returns the exact list if and only if every candidate-level action evaluated on the frozen exact state agrees, and the first disagreement is the exact point of divergence. Local bounds therefore compose into trace-, edge-, and path-level certificates. 3. The representation bridge and its limits (§5). Under an exact Gaussian oracle, Stein’s lemma gives a sign–linear covariance identity, and an aligned bilinear model gives a strict correlation gain from a magnitude bit. A rare-contamination construction proves that fixed-dimensional Gaussianity, thin-shell concentration, and an isotropic spectrum are jointly insufficient for useful exponential tails; concentration needs one of three additional ingredients, which we supply. 4. Operational certificates and quantizer scope (§6, §7). A held-out block certificate bounds the selective risk of a frozen quantized rule with finite-sample validity and no analytical assumption. RaBitQ, Lucene BBQ, and product quantizers enter the same decision interface through family-specific residual mechanisms. Scope. The theory covers fixed candidate sets and frozen execution traces. End-to-end recall additionally depends on candidate coverage, which requires separate graph-expansion arguments and is outside this paper. Notation. Throughout, d(·, ·) is an exact distance or dissimilarity and dˆQ its quantized approximation; Ψ is a signed decision functional whose sign selects an action; Γ = |Ψ| is the exact margin; R is the calibrated residual; cQ > 0 is the calibration scale; and v is a residual-tail parameter. For G ∼ N (µ, Σ) we write σi2 = Σii , ρij = Σij /(σi σj ), and φ for the standard normal density.

2 Related Work Binary codes and random projections. SimHash (Charikar, 2002) shows that randomhyperplane sign bits preserve angular similarity, with collision probability 1 − arccos⟨x, y⟩/π for fixed vectors. The randomness lives in the projection directions; the result does not describe the fixed coordinate axes of a learned encoder, whose per-coordinate variances differ by an order of magnitude. RaBitQ (Gao and Long, 2024) gives a sharp pointwise error bound for a randomized ratio estimator of a single inner product. Product quantization (Jégou et al., 2011; Ge et al., 2014) and ScaNN (Guo et al., 2020) operate with learned codebooks at 4 to 64 bits. These methods characterize individual distance estimates; our decision analysis studies differences of estimates with shared structure. Graph-based nearest-neighbour search. HNSW (Malkov and Yashunin, 2020) and Vamana (Subramanya et al., 2019) build navigable graphs by iterated candidate sorting and diversity pruning, and QuIVer (Xiao et al., 2026) runs both operations on two-bit scores. Existing theory studies navigability under random-graph or geometric assumptions. We ask a different question, whether quantization preserves the local decisions made during construction and traversal, and answer it with a deterministic composition theorem for the selection state machine. 3

Xiao and Cao

Contrastive representation geometry. Betser et al. (2026) prove asymptotic Gaussianity of fixed-dimensional projections under stated alignment and concentration assumptions, with a second regime that adds a vanishing regularizer. We use this result to motivate an exact Gaussian oracle; approximate Gaussian diagnostics alone do not transfer its identities or tails without error control. Concentration and margin conditions. The boundary-plus-tail split is the low-noise condition of Tsybakov (2004) transported to algorithmic comparisons. The residual side is supplied by sub-Gaussian and sub-gamma tail bounds (Vershynin, 2018; Boucheron et al., 2013), by Efron–Stein replacement bounds (Efron and Stein, 1981), and by empirical Bernstein inequalities (Maurer and Pontil, 2009). The new element is the combination of rolespecific quantization residuals, covariance-aware scales, and frozen algorithmic traces in one framework.

3 Decisions, Boundaries, and Residual Tails Every step of graph-based vector search reduces to the question “is Ψ positive or negative?”, where Ψ is a difference of distances (ranking), a scaled comparison (pruning), or a threshold b Q , and the step fails when test (stopping). Quantization replaces Ψ by an approximation Ψ the two disagree in sign. Table 1 summarizes what each result in the paper assumes and what it delivers; the rest of the paper fills in the rows. Table 1: The results of the paper, the source of randomness each one conditions on, and the object each one controls. Result

Randomness

Key assumption

Controls

Does not control

Boundary– residual split (Thm. 2) Covariance-aware tails (Props. 5, 6)

any common probability space

positive calibration scale; exact ties handled separately joint sub-Gaussian proxy and bias term

flip probability of one comparison

residual concentration

one-sided ranking and pruning flip risk

MGF control from sample covariance alone

shared permutation, append-only selection, one tie rule stated target, scorer, threshold

equality of neighbour lists; first divergence

candidate generation, navigability, or recall arbitrary scorers or decision risk

Trace coupling (Thm. 8)

quantizer or data randomness with the compared objects fixed none: deterministic state machine

Gaussian oracle (Thm. 11, Prop. 12) Necessity (Thm. 13)

exact joint Gaussian representation explicit construction

Selective certificate (Thm. 14)

i.i.d. blocks given a frozen fit

none

positive coverage; prespecified grid

4

sign–linear covariance; aligned Pearson gain impossibility of tails from low-order diagnostics ratio of expected failure to expected coverage

behavior of every real embedding

distribution shift or end-to-end recall

Low-Bit Decision Stability in Vector Search

3.1 Setup and the main decomposition b Q be the exact and approxiDefinition 1 (Decision residual and margin) Let Ψ and Ψ mate decision functionals on a common probability space. For a calibration constant cQ > 0 define b Q − cQ Ψ, R=Ψ Γ = |Ψ|. (1) b Q ≤ 0, Ψ ̸= 0}: an approximate tie against a The conservative flip event is E = {ΨΨ non-tied exact decision counts as a failure. The constant cQ absorbs multiplicative distortion and is fitted by least squares on an independent sample. A through-origin fit makes R orthogonal to Ψ in the sample, but it does not make R mean zero; the risk bounds below therefore carry an explicit bias term, and in practice we use affine calibration. Theorem 2 (Boundary–residual decomposition) For every τ > 0, P(E) ≤ P(0 < Γ ≤ τ ) + P(|R| ≥ cQ τ ) . | {z } | {z } boundary mass

(2)

residual tail

No independence between R and Ψ is required. Proof On E the residual opposes the sign of Ψ with magnitude at least cQ Γ > 0. Split according to whether Γ ≤ τ or Γ > τ ; in the second case |R| ≥ cQ Γ > cQ τ . The two terms are the two failure mechanisms that fidelity metrics merge. High average fidelity coexists with large boundary mass on a hard candidate set, and poor average fidelity is harmless when every margin of interest is large. Rank correlation and boundary crossings are different functionals of the same joint law, which is why a Spearman coefficient computed on random pairs does not determine the flip rate on selected pairs (§8 gives an explicit construction in which the two are decoupled). Corollary 3 (Sub-Gaussian instantiation) If P(0 < Γ ≤ τ ) ≤ Cτ β for 0 < τ ≤ τ0 and P(|R| ≥ z) ≤ 2 exp(−z 2 /2v 2 ), then " !# 2 τ2 c Q P(E) ≤ inf Cτ β + 2 exp − 2 , (3) 0<τ ≤τ0 2v and the minimizing τ ⋆ scales as (v/cQ )[log(1/v)]1/2 . The resulting rate is of order (v/cQ )β [log(cQ /v)]β/2 (Appendix A). Remark 4 (The boundary exponent belongs to the embedding) Fitting the empirical margin distribution on logarithmic axes over the inspected quantile window gives β = 1.526 on Cohere (R2 = 0.994), 1.500 on MiniLM (R2 = 0.979), and 1.595 on GIST (R2 = 0.989), identical for one- and two-bit codes on the same data. The boundary-mass term can therefore be estimated from the embedding before any quantizer is chosen, and it tells a practitioner how much residual control a given decision population will demand. 5

Xiao and Cao

3.2 Ranking: the shared-query correlation For a query q and candidates x, y with d(q, x) < d(q, y), the ranking functional and its residual are Ψrank = d(q, y) − d(q, x) > 0, Rrank = ξy − ξx , (4) where ξx = dˆQ (q, x)−cQ d(q, x) is the calibrated error on the edge (q, x). Both errors involve the same quantized query, so they share a common component. Proposition 5 (Covariance-aware ranking) Fix q, x, y before drawing the approximation randomness, and let (ξx , ξy ) have mean m and joint sub-Gaussian proxy matrix K. The ranking residual is sub-Gaussian with scale 2 νrank = Kxx + Kyy − 2Kxy ,

(5)

and for exact margin γ > 0 and bias µR = E(ξy − ξx ),   (cQ γ + µR )2+ PQ (rank flip) ≤ exp − . 2 2νrank

(6)

b ξ )xy measures shared-query covariance in the selected-pair The empirical cross term (Σ b ξ is the sample covariance of (ξx , ξy ). It gives the exact second-moment population, where Σ identity d y − ξx ) = (Σ b ξ )xx + (Σ b ξ )yy − 2(Σ b ξ )xy . Var(ξ (7) This empirical covariance is distinct from the joint MGF proxy K in Proposition 5. Table 2: Empirical residual correlation on fixed 32-neighbour candidate sets (top candidate against each competitor), pooled over queries and competitors. The independence d x ) + Var(ξ d y ))/Var(ξ d y − ξx ). ratio is (Var(ξ

†

Dataset

Quantizer

Residual corr. ρxy

Independence ratio

Flip rate

Cohere-768 Cohere-768 Cohere-768 MiniLM-384 MiniLM-384 GIST-960†

1-bit 2-bit rotated 2-bit 1-bit 2-bit 2-bit

0.794 0.870 0.435 0.047 0.093 0.832

4.71× 7.42× 1.77× 1.05× 1.10× 5.70×

8.89% 5.83% 8.81% 11.21% 4.19% 35.83%

The eligibility gate of §6 rejects this configuration (calibration slope near zero, left tail 7.8× Gaussian); the row is included for comparison.

Two facts about this correlation matter. First, it belongs to the selected-pair population rather than the i.i.d. endpoint model. For i.i.d. endpoints and a single symmetric kernel, the Hoeffding decomposition bounds shared-endpoint correlation by 1/2 and the independence ratio by 2 (Appendix B). Second, substituting empirical covariance into the Gaussian-tail expression gives an informative plug-in diagnostic on the inspected eligible configurations: 6

Low-Bit Decision Stability in Vector Search

it is below one and covers the observed flip rate in each case (0.55 against an observed 5.8% for Cohere two-bit codes), whereas omitting the cross term makes the expression equal one on every Cohere configuration. This substitution is not the analytical assumption itself; the concentration routes of §5 provide tail control under their stated conditions, and the held-out route of §6 provides an independent alternative. A six-bin margin-conditional scale changes predictive correlation by at most 0.002, so we retain one global scale in the reported experiments. 3.3 Pruning: role-specific residuals Vamana’s RobustPrune rule declares candidate c dominated by an already selected neighbour s of target t when Ψα (t, c, s) = d(t, c) − α d(s, c) ≥ 0,

α ≥ 1.

(8)

The residual combines two distances that share the node c rather than a query: Zα = ξtc − α ξsc ,

να2 = Ktc,tc + α2 Ksc,sc − 2αKtc,sc .

(9)

A shared additive intercept in the edge calibration cancels in the ranking difference but survives in Zα as (1 − α)b, so pruning needs its own bias term. Proposition 6 (Fixed-triple pruning) Fix the triple (t, c, s) before drawing the approximation randomness, and let Zα have joint sub-Gaussian scale να and mean µZ . For exact margin γ = |Ψα | > 0: • a false keep (missed prune, Ψα > 0) has probability at most exp[−(cQ γ +µZ )2+ /(2να2 )]; • a false prune (Ψα < 0) has the same form with effective margin cQ γ − µZ ; • at a structural tie (Ψα = 0) disagreement is the event Zα < 0, whose probability must be carried explicitly; a no-atom condition on Zα does not control it. The two orientations behave very differently on real data: across all sampled configurations in §8.4, every observed pruning disagreement is a false keep. 3.4 Fixed top-K on a frozen candidate set For a candidate set C frozen before approximate scoring, with exact top-K subset A ⊂ C, X X b ̸= A) ≤ PQ (A PQ (rank flip on (x, y)), (10) x∈A y∈C\A

and any deterministic sufficient comparison set may replace the full cross product.

4 From Local Decisions to Algorithmic Traces A Vamana selection call makes dozens of comparisons in sequence, each depending on the outcome of earlier ones. This section shows that local bounds compose into a statement about the whole call once the exact execution state is frozen. 7

Xiao and Cao

4.1 The selection call as a state machine Fix a target t, a candidate permutation π = (c(1) , . . . , c(N ) ) sorted by exact distance with deterministic tie-breaking, a degree budget M , and α ≥ 1. Starting from S = (), scan π until it is exhausted or |S| = M . At candidate c form the candidate-level action _ D(c; S) = 1{d(t, c) − α d(s, c) ≥ 0}, (11) s∈S

and append c exactly when D(c; S) = 0. This is the standard non-saturated RobustPrune call. Any deterministic refill applied afterwards is a separate post-processing map. Definition 7 (Semantic trace) The semantic trace T records the shared permutation, each visited candidate, its selected prefix, its candidate-level action, and the termination state. It does not record implementation-dependent short-circuit order among witnesses. 4.2 The coupling theorem Theorem 8 (Trace coupling) Let the approximate replay use the same candidate permutation, unique candidate labels, degree budget, and tie convention. For each exact visited candidate j, evaluate the approximate candidate-level action on the frozen exact prefix Sj and let Ej be the event that it differs from the exact action. Then, for the append-only non-saturated call, [ {Tb ̸= T } = {Sbout ̸= Sout } = Ej , (12) j∈V

and consequently P(Sbout ̸= Sout ) ≤

XX

P(triple action disagreement at (j, s)).

(13)

j∈V s∈Sj

The second inequality is generally strict, because several witnesses enter one candidate-level OR. Proof If no Ej occurs, induction from the empty prefix makes states, actions, and termination identical. Otherwise let j⋆ be the first occurring event. Both executions have the same prefix and visit the same candidate before j⋆ , so Ej⋆ is an actual action disagreement; that candidate is appended in exactly one run and, since selection is append-only with unique labels, the final sets differ. The identity is deterministic for a shared permutation. When approximate scoring also changes the permutation, its disagreement event is added before applying the theorem conditionally on equal order. Probability enters only through the local action bounds; no independence across comparisons is used anywhere. 4.3 Dependency slicing, edge certificates, and what they show Full-trace equality is often more than an application needs. For a single diversity-selected edge, a backward slice keeps only the sorting and pruning atoms sufficient for that edge’s survival. 8

Low-Bit Decision Stability in Vector Search

Corollary 9 (Edge and path certificates) For an exact output edge e selected at scan position je , agreement of all candidate actions in the exact prefix through je is sufficient for e to survive. For a fixed path P composed of such edges, XX X P(some edge of P is lost) ≤ P(triple action disagreement at (j, s)). (14) e∈P j≤je s∈Sj 2 The condition Mmin > 2 log NP , with NP the number of listed terms and Mmin the smallest standardized margin among them, indicates when the additive bound can stay below one.

In the non-saturated experiments of §8.4, an edge’s prefix certificate contains 21 to 25 triple comparisons on average, and the plug-in additive bound saturates at one on 89 to 92% of tested edges. The certificate nevertheless carries information in two ways. Its logical half is exact: in every tested case a passing certificate implied edge survival. Its numerical half remains a useful ranking: the plug-in risk sum orders edges by observed failure with Spearman correlation 0.81, 0.69, and 0.73 on Cohere, MiniLM, and GIST. Remark 10 (Failure concentrates on few decisions) The union bound weights all decisions equally, but query-level failure is driven by a few of them. Ranking the 31 comparisons of a candidate set by individual risk and summing only the r largest improves the correlation with observed query failure up to r = 3 to 5 (Cohere two-bit 0.471 → 0.480; MiniLM one-bit 0.460 → 0.500; MiniLM rotated two-bit reaches 0.589), after which further terms add noise. The full sum remains the valid upper bound; the top-r score is an empirical predictor, and we keep the two named separately.

5 From Representations to Residual Laws Sections 3 and 4 are quantizer-agnostic: any source of residual control feeds them. This section develops the analytically richest instance, coordinate-preserving one- and two-bit codes on representations with Gaussian coordinate structure, and locates the boundary of that analysis. 5.1 The Gaussian model and its empirical support Assumption 1 (Coordinate Gaussianity) Let G ∈ RD be the encoder output before L2 normalization. (a) For any fixed k coordinates I, dBL (L(GI ), L(ZI )) ≤ εD with Z ∼ N (µ, Σ). (b) Thin shell: E ∥G∥ − rD /rD ≤ δD with δD → 0. Betser et al. (2026) prove asymptotic Gaussianity of fixed-dimensional projections under alignment and concentration assumptions on the InfoNCE objective. Empirically, all eleven learned representations we inspected, produced by eight different encoders, have coordinatewise QQ-plot R2 ≥ 0.9959 and norm coefficient of variation at most 0.09; the classical GIST and SIFT descriptors fail both diagnostics. The joint law is a stronger statement than these marginal checks, and §8.7 measures how far each dataset satisfies it. The identities below are exact for the Gaussian model and are used as an oracle; the held-out route of §6 covers representations for which the model is not credible. 9

Xiao and Cao

5.2 The Stein covariance identity P P Let G ∼ N (µ, Σ), S0 = i sign(Gi ), and T0 = j dj Gj . Theorem 11 (Stein covariance identity) Cov(S0 , T0 ) =

X

ai Σij dj ,

ai =

i,j

2φ(µi /σi ) . σi

(15)

P Proof By bilinearity Cov(S0 , T0 ) = i,j dj Cov(sign(Gi ), Gj ). For jointly Gaussian (Gi , Gj ) the conditional mean is E[Gj | Gi ] = µj + (Σij /σi2 )(Gi − µi ), whence Cov(sign(Gi ), Gj ) =

Σij · 2σi φ(µi /σi ) = ai Σij . σi2

The full matrix Σ enters, not only its P diagonal,2 and the off-diagonal contribution is measured by the Frobenius energy Ioff = i̸=j (ai Σij ) . Table 3 shows that this term carries 31 to 38% of the predicted ranking signal even though individual coordinate √ P correlations are small (mean |ρij | between 0.04 and 0.11): with |ρij | ≍ κ/ D the sum i̸=j ρ2ij ≍ κ2 D is of constant order relative to the diagonal. Table 3: Spearman ranking fidelity F of the one-bit code, measured and predicted from the Gaussian model with the full covariance and with its diagonal only. Gap explained is (Ffull−Σ − Fdiag )/(Factual − Fdiag ). Dataset

Factual

Ffull−Σ

Fdiag

Gap explained

Cohere Arxiv CodeSearch Random

0.681 0.897 0.823 0.907

0.688 0.886 0.837 0.899

0.474 0.546 0.542 0.560

103% 97% 105% 98%

5.3 The magnitude bit under an aligned bilinear model Let G, H be independent with independent coordinates Gi , Hi ∼ N (0, σi2 ), and for a deterministic threshold τ > 0 define X X X T = Gi Hi , S1 = sign(Gi ) sign(Hi ), S2 = qi (G)qi (H), (16) i

i

i

with qi (g) = sign(gi )(1 + 1{|gi | > τ }). Proposition 12 (Aligned magnitude-bit gain) For every D ≥ 1, every σi > 0, and every finite τ > 0, the Pearson correlations satisfy ρ(S2 , T ) > ρ(S1 , T ). 10

Low-Bit Decision Stability in Vector Search

The closed forms and the proof are in Appendix E. The alignment between target and scorer is essential: in a linear-target model whose scorer weights do not match the target weights, the same second bit lowers the correlation (by 0.163 in the eight-dimensional example of Appendix E). More code information improves the best readout, not every fixed readout. Empirically the second bit raises global ranking fidelity by +0.071 to +0.132 on the contrastive embeddings we inspected, and on Cohere it brings the 3σ residual survival ratio from 2.09 times Gaussian to 1.05 and lowers pairwise flip rates by 34.5%. 5.4 Rotation duality By Lévy concentration and a union bound, a Haar-random orthogonal rotation equalizes the coordinate variances to ! r tr(Σ) log D . ± O ∥Σ∥op D D This single fact has two opposite design consequences. It destroys the coordinate variance and sign-entropy structure that a coordinate code exploits, so its effect on a fixed two-bit scorer depends on the representation. It also creates exactly the coordinate uniformity that RaBitQ’s randomized codebook and corrected estimator rely on. The two strategies are dual uses of the same representation. Across 12 datasets the sign-entropy gap 1 − Hsign predicts the global two-bit response to rotation with Spearman correlation 0.909, against 0.657 for coordinate-variance heterogeneity alone, and the interaction (1 − Hsign ) × CV(σ) reaches 0.930. Section 8.6 shows what rotation does to local decisions, which is a different question with a different answer. 5.5 Oracle decomposition of the residual For a fixed ranking or pruning role, let Ra◦ be the oracle residual computed with the population magnitude threshold and radius. Its Hoeffding decomposition has exact variance X X V = κ1 d2u + κ2 A2p , (17) u

p

where du are node incidences and Ap are unordered-pair edge coefficients (Appendix E). The replacement (Efron–Stein) proxy satisfies V ≤ VES ≤ 2V , with equality at two when the first-order Hoeffding component vanishes. The actual residual adds a threshold remainder and a shell remainder, Ra = Ra◦ + ∆thr + ∆shell , (18) and their sizes are measurable. On Cohere and MiniLM the threshold remainder is 1.3 to 4.7% of the role variance; on unrotated GIST it is essentially all of it, and it falls to 2.3% after rotation. The remainder is therefore itself a diagnostic of whether the oracle describes a representation. 5.6 Necessity: what weak Gaussianity cannot prove Theorem 13 (Counterexample) There is a sequence of distributions GD whose fixedk standardized marginals converge to Gaussian in total variation at rate Ok (D−1 ), whose 11

Xiao and Cao

relative shell mean-square error is O(D−1 ), whose covariance is isotropic, and whose average threshold-boundary occupancy vanishes, yet whose fixed-threshold oracle ranking residual satisfies ◦ ◦ VD = Var(RD ) = Θ(D−1 ), κ4 (RD ) = Ω(D2 ). (19) Consequently a cumulant condition of Bernstein type, or a two-sided sub-gamma bound with √ variance proxy vD = O(VD ), requires bD / VD = Ω(D2 ). Proof [Construction] Take GD = (1 − JD )ZD + JD D3/2 SD with JD ∼ Bernoulli(D−4 ), ZD ∼ N (0, ID ), and SD Rademacher. The event that two of the three nodes in a ranking triple are contaminated and one is clean has probability Θ(D−8 ); after oracle normalization its bilinear term contributes Θ(D2 ) to the fourth moment. The bounded-code component has fourth moment O(D−2 ) and cannot cancel this in L4 , while the total variance stays Θ(D−1 ). Appendix H verifies the diagnostic properties and derives the cumulant and MGF consequences. The theorem identifies what must be added to reach exponential concentration. Any route must control one of three things: individual-coordinate influence (bounded codes), conditional cumulants (Doob increments), or the range after truncation. 5.7 Three routes to concentration 1. Conditional MGF. If the three Doob increments of Ra◦ satisfy deterministic subgamma bounds with parameters (vj , bj ), then  −

P(|Ra◦ − ERa◦ | ≥ z) ≤ 2 exp

 z2 , 2(v⋆ + b⋆ z)

v⋆ =

X

vj , b⋆ = max bj .

j

j

(20)

2. Stable truncation. If a clipped functional RL agrees with Ra◦ outside an event of probability εL , has bias |ERa◦ − ERL | ≤ dL , and is sub-gamma with (vL , bL ), then   z2 ◦ ◦ P(|Ra − ERa | ≥ z + dL ) ≤ 2 exp − + εL . (21) 2(vL + bL z) 3. Held-out calibration (§6), which needs no analytical tail at all. Section 8.8 measures the parameters of the first two routes on real embeddings.

6 Selective Certificates from Held-Out Blocks When the analytical route is not available, because Gaussian diagnostics fail, residual tails are heavy, or calibration is degenerate, the decision framework still applies; only the source of the residual tail changes. This section bounds decision risk from held-out data alone. The natural form is a selective guarantee: retain the decisions whose standardized margin exceeds a cutoff, route the rest to exact verification, and bound the failure rate on the retained set. This is how a deployed system would use the theory. 12

Low-Bit Decision Stability in Vector Search

Theorem 14 (Direct selective block certificate) Condition on an independent fit split, so that nuisance parameters, selectors, thresholds, and tie rules are fixed. For i.i.d. blocks Z1 , . . . , Zn let Ci,s be the fraction of decisions in block i accepted by selector s, Ui,s,τ the accepted fraction that lies in the boundary-or-residual union event at threshold τ , and Fi,s the accepted fraction that actually fails, so that 0 ≤ Fi,s ≤ Ui,s,τ ≤ Ci,s ≤ 1. (22) p For a prespecified grid G of (s, τ ) pairs set ϵn = log(|G|/δ)/(2n). With probability at least bs > 0, 1 − δ, simultaneously for every grid pair with C ( ) bs,τ + ϵn EUi,s,τ EFi,s U ≤ qs,τ := ≤ min 1, ps := . (23) bs ECi,s ECi,s C The ratios are defined when ECi,s > 0; zero empirical coverage yields no certificate. Proof Fix a grid pair and write q = qs,τ . Since 0 ≤ Ui ≤ Ci ≤ 1, the variable Wi = Ui −qCi has mean zero and lies in [−q, 1 − q], an interval of length one. One-sided Hoeffding gives b − qC b ≥ −ϵn except with probability δ/|G|; a union bound over the grid and division by U b C > 0 finish the proof. Dependence among decisions inside a block is arbitrary.

Corollary 15 (Direct accepted-failure certificate) Replacing Ui by Fi and paying only for the selector family S gives, simultaneously over s ∈ S, ( ) p Fbs + log(|S|/δ)/(2n) ps ≤ min 1, . (24) bs C The two certificates bound the same quantity ps but through different events. The union certificate keeps the boundary-plus-residual mechanism of Theorem 2 visible and is what one reports when the mechanism is the object of interest; the direct certificate targets the observed failure of the frozen rule and is tighter. p A conservative alternative that controls numerator and denominator separately costs log(2|G|/δ)/(2n) in both and is pointwise looser; Appendix F.1 also gives a variance-adaptive empirical-Bernstein version obtained by inverting a single-crossing function. Protocol. We condition on an independent coefficient-fit split, then use prespecified prefixes of 128, 256, 512, and 1,024 i.i.d. certification blocks and 1,024 independent validation blocks; each block is one query or target with 32 sampled candidates. Every method and sample size is fixed in advance, so each reported point carries its own marginal 1 − δ guarantee. Results are in §8.5.

7 Quantizer Instantiations The decision shell is quantizer-agnostic; each family enters through its own residual mechanism. 13

Xiao and Cao

Coordinate binary codes. The analytical instance of §5: covariance structure, threshold effects, magnitude-bit gain, rotation duality, and the conditional-MGF route are all specific to this family. RaBitQ. A randomized ratio estimator (Gao and Long, 2024) with a per-rotation error radius. For a fixed query q and data directions x, y sharing one random rotation P , P{|εR (x, q) − εR (y, q)| > ρx + ρy } ≤ 4 exp(−c0 ϵ20 ),

(25)

where ρx , ρy are the random radii. The shared rotation couples the two edges, so ranking and pruning statements go through joint events and the triangle inequality rather than independence. For pruning on raw squared distances the distance rule squares to an α2 rule with edge-specific radial factors (Appendix G); a rule stated directly in squared distance or cosine dissimilarity keeps its own parameter. Lucene BBQ. A role-asymmetric design (Trent, 2024): stored vectors are one-bit while query-role vectors are int4. During HNSW construction Lucene keeps temporary int4 queryrole vectors, scores candidates against existing one-bit vectors, and uses the int4 representations for diversity and reverse-link scoring; the temporary file is removed afterwards. Each scorer role therefore needs its own affine calibration, dbA→B = bA→B + aA→B d + ξA→B .

(26)

Our reference scorer reproduces the role semantics, not Lucene’s metric-specific corrections. Block estimators. Product quantization (Jégou et al., 2011; Ge et al., 2014) decomposes the residual over codebook blocks and enters through bounded-block concentration or heldout survival laws; the coordinate-sign Stein identity does not transfer. Table 4: Cross-quantizer validation on the decision interface, averaged over Cohere, MiniLM, SIFT, and GIST with 60,000 held-out ranking and 60,000 pruning triples per dataset. “Hard” restricts to the 20% smallest exact margins. All calibration slopes are positive. The PQ reference stores 64 index bits per vector.

Quantizer family Sign (1-bit) Shared 2-bit RaBitQ reference BBQ-like Scalar int4 PQ (16 blocks × 4 bits)

Edge ρ .373 .789 .939 .923 .997 .801

Rank flip all hard 35.9% 18.5% 11.8% 12.8% 2.1% 22.4%

47.1% 41.5% 37.2% 37.3% 10.1% 43.3%

Prune flip all hard 20.1% 12.8% 6.5% 9.0% 1.2% 11.0%

36.5% 33.9% 27.1% 30.7% 5.8% 33.1%

Table 4 makes one point that no bit budget removes. Scalar int4 has the best interface metrics of the inspected references, with edge correlation 0.997 and 2.1% ranking flips, yet on the hardest fifth of margins it still flips 10.1% of ranking decisions. A larger budget changes the residual law and shrinks the boundary crossings; it does not move the boundary. 14

Low-Bit Decision Stability in Vector Search

8 Experiments The experiments test each link of the argument: boundary mass, residual covariance and its origin, trace composition, held-out certification, the analytical regime and its edge, and the decoupling of fidelity from decision risk. All protocols use disjoint data splits, and every experiment is a numbered, non-interactive Python module with fixed seeds. 8.1 Datasets and protocols Table 5: Representation regimes. “Learned” means contrastive or self-supervised training; “classical” means hand-crafted or dimensionality-reduced features. Group

Datasets

Contrastive text

Cohere, MiniLM, BGE-M3, Jina, MSMARCO Wolt-CLIP, Landmark-DINO SIFT, GIST, GloVe Gaussian, sphere, random, contaminated

Vision Classical Synthetic

D

Role

384–1024

primary regimes

512–768 100–960 64–2048

modality transfer negative controls mechanism tests

Each dataset contributes a fixed random sample of vectors (seed 42), L2 -normalized. Local decision experiments use fixed 32-neighbour candidate sets with 80 calibration and 160 held-out queries per dataset; held-out certificate experiments use the block protocol of §6; the cross-quantizer study uses 1,200 fit and 2,000 held-out vectors per dataset. Pruning uses the standard non-saturated RobustPrune rule with α = 1.2 and M = 32 unless stated otherwise. 8.2 Standardized margins predict local failures On Cohere two-bit decisions the flip rate falls monotonically with the standardized margin M = cQ Γ/v over more than two orders of magnitude (Table 6), and no flips are observed above M = 5. Table 6: Flip rate by standardized-margin bin on Cohere-768 two-bit codes, n = 4,960 heldout decisions. Margin bin

M < 0.25

0.25–1

1–2

2–3

3–5

M >5

Flip rate Decisions

48.6% 70

25.7% 381

9.50% 1210

2.54% 1577

0.14% 1413

0.00% 309

Across 24 held-out dataset–quantizer configurations (12 datasets, two-bit codes with and without rotation), the calibrated boundary-plus-tail predictor tracks unseen ranking flip rates with Spearman correlation 0.970 and unseen pruning flip rates with 0.992. Using each configuration’s global distance Spearman correlation as the predictor instead gives 0.739 for ranking and 0.053 for pruning; using its distance mean squared error gives 0.184 15

Xiao and Cao

and 0.447. Fidelity is a weak predictor of ranking risk and no predictor of pruning risk; the standardized margin predicts both. 8.3 Where the shared-query covariance comes from Table 2 reports correlations far above the 1/2 bound that holds for i.i.d. endpoints and a symmetric kernel. To locate the source we keep one globally fitted affine edge scorer fixed and vary only how pairs are generated (Table 7). Table 7: Pooled shared-query residual correlation under different pair-generation regimes with one fixed edge scorer. “Anchor” pairs the exact top candidate with each remaining top-32 candidate. Dataset

Scorer

i.i.d.

Random cand.

Top-256

Top-32 / anchor

Cohere Cohere Cohere MiniLM GIST GIST

1-bit 2-bit rotated 2-bit 2-bit 1-bit 2-bit

.361 .391 .259 .010 .386 .405

.312 .346 .212 .020 .370 .422

.524 .571 .324 .067 .925 .576

.525 / .544 .599 / .613 .340 / .364 .111 / .118 .934 / .870 .640 / .616

Local selection, not identity collisions, drives the increase: an i.i.d. control with replacement and a distinct-triple control differ by at most 0.003, while moving from random candidates to the top-32 roughly doubles the correlation on Cohere and more than doubles it on GIST. The exact weighted within/between identity of Appendix B holds to floatingpoint precision in every regime, and most pooled covariance in this experiment comes from variation in query-specific residual means, while weighted within-query covariance is small on average. This describes the selected-pair population with a random query; conditioning on a fixed query removes the between-query term. Moreover, this experiment uses a global affine edge calibration, whereas Table 2 uses ranking-margin calibration. It therefore identifies query-level heterogeneity under this protocol without quantitatively attributing the earlier independence ratios. 8.4 Trace coupling and its consequences All 960 sampled selection calls (three datasets, two quantizers, 160 targets each) satisfy the identity of Theorem 8: the approximate output differs from the exact output exactly when some candidate-level action differs, and never otherwise. Table 8 shows what the identity implies for output agreement. Output disagreement is large even where local disagreement is modest, because each candidate action is an OR over its whole selected prefix, and the first action difference persists in an append-only output. Every one of the sampled triple disagreements is a false keep; no false prune occurs at α = 1.2. When a saturating refill step is added after the standard call, it contributes 34.1% of the final edges on Cohere, none on MiniLM, and 28.8% 16

Low-Bit Decision Stability in Vector Search

Table 8: Standard non-saturated RobustPrune replay with exact candidate pools, two-bit codes, α = 1.2, M = 32. Fixed-order replay reuses the exact permutation; free replay also re-sorts candidates by quantized distance. Dataset Cohere-768 MiniLM-384 GIST-960

Local prune flip

Fixed-order Jaccard

Free replay Jaccard

13.06% 1.92% 7.91%

0.322 0.654 0.458

0.395 0.529 0.260

on GIST; these shares belong to the refill variant, not to RobustPrune itself, and the local pruning analysis is unaffected by them. 8.5 Held-out selective certificates Table 9 reports the certificates of §6 at 512 and 1,024 blocks, averaged over 24 dataset– quantizer configurations per role. Every method issued a certificate on every configuration, and on every one the empirical risk of the selected policy on 1,024 independent validation blocks was below its certificate. Table 9: Selective block certificates (δ = 0.05), averaged over 24 configurations per role. Coverage is the fraction of validation decisions retained by the selected policy and risk is their observed flip rate; each method optimizes its own policy, so coverages differ. Ranking / pruning. Blocks

Method

Certificate

Validation coverage

Validation risk

512 512 512 512

two-event Hoeffding direct union empirical-Bernstein union direct failure

20.59% / 22.95% 16.74% / 18.65% 9.49% / 10.91% 9.07% / 10.45%

67.0% / 67.6% 64.6% / 63.5% 61.2% / 56.8% 87.8% / 80.2%

0.42% / 0.86% 0.33% / 0.75% 0.26% / 0.72% 1.34% / 2.01%

1,024 1,024 1,024 1,024

two-event Hoeffding direct union empirical-Bernstein union direct failure

15.13% / 17.36% 12.74% / 14.65% 6.13% / 7.27% 6.75% / 7.99%

63.7% / 61.0% 61.2% / 61.0% 57.7% / 51.1% 81.9% / 75.2%

0.32% / 0.75% 0.26% / 0.75% 0.22% / 0.44% 0.94% / 1.44%

For a fixed selector at the same confidence level, the direct ratio removes the denominator slack of the two-event bound without changing the accepted set. The policies in Table 9 are optimized separately by method, so their retained fractions differ. The empirical-Bernstein union certificate is tighter with lower coverage, while the direct-failure certificate retains about four fifths of decisions because it does not carry the structural gap between the union event and actual failure. Certificate values must therefore be read together with retained coverage. A cutoff targeting the highest-margin fifth is frozen on calibration data and then applied to a separate validation pool. Across the 24 configurations, the mean validation retention 17

Xiao and Cao

is 19.9% for ranking and 20.9% for pruning; mean empirical flip rates fall from 8.58% to 5.27% and from 3.84% to 0.12%, respectively. This is a held-out empirical reduction, while the population guarantee is provided separately by the block certificates above. 8.6 Rotation: global fidelity does not determine decision risk A Haar-random rotation is the cleanest intervention on a coordinate code: it changes the representation’s coordinate structure and nothing else. On Cohere it raises the Spearman correlation between quantized and exact distances from 0.576 to 0.926 and lowers the distance mean squared error by a factor of four. What happens to local decisions depends on which decisions are asked. Table 10: Rotation on Cohere codes under two decision protocols. The distance Spearman correlation is measured on the calibration pairs of the block protocol. Protocol

Quantity

Unrotated

Rotated

32-neighbour anchor pairs

one-bit flip rate two-bit flip rate shared-query residual correlation difference residual s.d. (cosine units)

8.89% 5.83% 0.870 0.0134

15.58% 8.81% 0.435 0.0148

48-candidate held-out blocks

distance Spearman ranking flip rate pruning flip rate

0.576 4.43% 10.25%

0.926 4.48% 6.93%

On the anchor protocol, which compares the exact nearest neighbour against each of its 31 competitors, rotation raises the two-bit flip rate by half and nearly doubles the onebit rate. The mechanism is visible in the residual structure. Rotation shrinks each edge’s error variance by a factor of three to four, which is why global fidelity improves, but it also cuts the shared-query correlation from 0.870 to 0.435. At fixed marginal variances a smaller positive correlation raises the variance of a difference, and here the two effects net out to an 11% larger standard deviation for the comparison residual together with a more negative bias relative to the margin (from −0.26 to −0.36 standard deviations). On the block protocol, whose candidate sets are larger and whose pairs are not anchored on the top candidate, the ranking flip rate is unchanged and the pruning flip rate falls. A fidelity statistic that moves by +0.35 cannot predict an effect whose sign depends on the decision population; quantizer choices for graph search must be evaluated on the decisions the graph actually makes. 8.7 The analytical regime and its edge Coordinate-wise diagnostics are broadly compatible with Gaussian marginals in the inspected learned representations. The joint law is where datasets separate. Testing k = 8 coordinate subsets with a Kolmogorov–Smirnov test on the Mahalanobis radius at the 1% level (24 random subsets per dataset), BGE-M3 and GloVe reject none, Landmark-DINO rejects 8%, MiniLM 13%, Cohere 29%, and Wolt-CLIP 58%; SIFT and GIST reject every subset. The exact Gaussian oracle is therefore partially supported on the primary dataset, 18

Low-Bit Decision Stability in Vector Search

which is the reason the analytical route is paired with the model-free one rather than offered alone. Where the oracle applies it is accurate. The incidence-covariance identity (17) reproduces the measured ranking and pruning residual variances within 4.6% across twelve role configurations, with median error 1.2%. The variance route is also tight in a way the worstcase constant does not reveal. Over 28 dataset–coordinate–role configurations, a componentwise Cauchy–Schwarz proxy exceeds the measured variance by a median factor of 40.8, while the replacement proxy exceeds it by a median factor of 1.67 (range 1.21 to 2.04), consistent with the analytical factor of at most two. The reason the combined kernel behaves so much better than the sum of its parts is that in all 28 configurations the bounded-code and bilinear components have negative covariance, with a median cancellation ratio of 0.947. The GIST descriptors show the same machinery diagnosing and repairing a failure. Unrotated GIST has calibration slope near zero, zero margin correlation, residual kurtosis 26, a left tail 7.7 times Gaussian, and a threshold remainder equal to the whole role variance; every one of these is observable without a search run. A random rotation raises the margin correlation to 0.510 and 0.669 for one- and two-bit codes, brings the kurtosis to 3.5 and 2.8, the left tail to 1.88 and 0.76 times Gaussian, and the threshold remainder to 2.3%, and the flip rates fall from 100% to 14.80% (one-bit) and from 35.83% to 9.33% (two-bit). 8.8 Conditional-MGF and truncation parameters Across 24 role configurations (six datasets, two quantizers, two roles) the untruncated increment parameter b⋆ /sd has minimum 0.133, median 0.158, and maximum 0.324; the Doob variance sum exceeds the total variance by 5 to 10%; and the calibration-to-validation variance transfer ratio lies between 0.945 and 1.075. Clipping at the 1% exceptional-mass cutoff brings b⋆ /sd to a median of 0.147 and a maximum of 0.258. Every configuration admits a clipped-functional bound below one, and no held-out tail exceeded its reported bound. These are the measured inputs to the two analytical routes of §5; a uniform conditionalMGF assumption over the population is a hypothesis these measurements are consistent with, not one they establish. 8.9 Necessity and falsifiability Two constructions show that the framework’s ingredients are necessary. At exact margin zero, residuals of arbitrarily small norm select opposite decisions, so the boundary-mass term cannot be dropped. And two perturbations of the same exact scores, one light-tailed and one coupled to the decision boundary, have Spearman correlation 0.9860282 with the exact scores to seven digits, yet flip 5.09% against 10.00% of all decisions and 23.91% against 50.00% of the hardest fifth. Mean squared error does not rescue the comparison: it is lower for the boundary-coupled perturbation (0.0170 against 0.0251), so a practitioner selecting by either global metric would pick the quantizer with twice the failure rate. Standardized margins separate the two immediately. The framework also abstains where it should: on nonpositive calibration, heavy tails, failed Gaussian diagnostics, and saturated certificates it reports an uncertified decision rather than a number. 19

Xiao and Cao

9 Discussion: Practical Guidance A per-decision reliability score. Given an embedding and a quantizer, fit the affine calibration and residual scale on independent blocks and evaluate M = cQ Γ/v wherever the exact margin is available. In Table 6, M > 5 has no observed flips in 309 decisions and M < 1 flips more than a quarter of the time. Because Γ is the exact margin, this is an offline audit; an online router additionally needs an observable lower bound on the margin or a residual envelope. Select quantizers on decisions, not on fidelity. Section 8.6 shows a rotation that raises global fidelity by +0.35 while raising one local flip rate by half and leaving another unchanged, and §8.9 shows two quantizers with identical rank fidelity, opposite ordering by mean squared error, and a factor of two in failure rate. Pilot the candidate quantizers on the decision population of the intended index, measure standardized margins and flip rates there, and choose on those. Two diagnostics, not one. Sign entropy is the natural single routing statistic and it is insufficient. Cohere (Hsign = 0.747) and SIFT (0.746) are indistinguishable by it, and their global rotation responses are nearly identical (+0.170 and +0.200), yet coordinate binary quantization is usable on Cohere and useless on SIFT. The entropy gap 1 − Hsign predicts how much rotation changes a code (ρ = 0.909 over 12 datasets). Whether the unrotated code is usable at all is answered by the eligibility gate (calibration slope, margin correlation, residual tail), which passes Cohere and rejects SIFT. Run the gate first; if it passes, rotation is an optimization to be evaluated on decision metrics, and if it fails, rotation is a repair whose size the entropy gap predicts. Two levels of assurance. Union-event certificates keep the boundary-plus-residual mechanism visible; direct-failure certificates bound the frozen rule’s observed failure and are tighter at higher coverage. Both are population statements for the block distribution they were calibrated on, and neither transfers across a distribution shift without recalibration. Open directions. Whether the trace-length saturation boundary can be characterized from representation geometry alone; whether adaptive candidate sets (beam search) admit a martingale extension of the coupling argument; and whether a pilot selector choosing rotation, bit width, and verification cutoff from covariance statistics alone recovers exactscore topology.

10 Conclusion Low-bit vector search cannot be understood through a single fidelity number. The decisions that flip are concentrated at the boundary, and their noise depends on shared structure that global metrics erase. A distribution-free boundary–residual decomposition localizes the risk, covariance-aware role analysis captures the shared structure, and a deterministic frozen-trace coupling connects local decisions to the neighbour lists a graph algorithm produces. Under an exact Gaussian model of contrastive representations the residual covariance is explicit and a magnitude bit provably helps an aligned scorer; a rare-contamination construction shows exactly why low-order Gaussian diagnostics cannot by themselves de20

Low-Bit Decision Stability in Vector Search

liver exponential tails; and held-out block certificates bound selective risk for any quantizer whose analytical description is out of reach. Limitations. The trace certificates saturate on long paths and say nothing about candidate generation or graph navigability. The Gaussian identities are oracle results, and approximate Gaussian diagnostics do not come with a transfer theorem. The held-out certificates require representative independent blocks, use exact margins in the selector, and do not transfer under distribution shift. End-to-end recall additionally depends on candidate coverage, which is outside this analysis.

Reproducibility All experiments are implemented as numbered, non-interactive Python modules with fixed seeds, disjoint data pools, and machine-readable JSON or NPZ outputs. Negative and vacuous results are preserved in the result files. Appendix I lists the protocol of each experiment.

Acknowledgments and Disclosure of Funding No external funding was received for this work.

Appendix A. The Decision Shell: Proofs and Rates A.1 Conservative ties and event inclusion b Q = cQ Ψ + RΨ,Q with cQ > 0. If Ψ > 0 and the conservative failure event occurs, Write Ψ b Q ≤ 0 and then Ψ RΨ,Q ≤ −cQ Ψ = −cQ ΓΨ . (27) If Ψ < 0, failure gives RΨ,Q ≥ cQ ΓΨ . Hence EΨ ⊆ {ΓΨ > 0, |RΨ,Q | ≥ cQ ΓΨ },

(28)

and splitting the right-hand side according to 0 < ΓΨ ≤ τ or ΓΨ > τ proves Theorem 2. If only strict sign reversal counts as failure, the residual event may use a strict inequality. If exact ties are part of the target risk, one adds P(Ψ = 0) together with the exact and approximate tie actions. A.2 Explicit small-ball rate Under√Corollary 3 write r = v/cQ and A = Crβ . When 0 < A < 2, let L = log(2/A) and τr = r 2L. If τr ≤ τ0 , substitution into (3) gives P(EΨ ) ≤ Crβ (2L)β/2 + Crβ ,

(29)

so the worst-case consequence of marginal small-ball and residual-tail assumptions is   O rβ [log(1/r)]β/2 . (30) 21

Xiao and Cao

The logarithm is a feature of the worst case over the assumed class, not a lower bound for each fixed distribution: a margin-conditional residual tail removes it and yields O(rβ ) by direct integration. A.3 Necessity at the boundary b + = ϵ and Ψ b − = −ϵ have residual magnitudes tending to At Ψ = 0, the approximations Ψ zero with ϵ yet select opposite actions. Every orientation theorem therefore needs a positive margin, a boundary-mass term, or an explicit tie policy.

Appendix B. Covariance-Aware Ranking B.1 Difference residual and bias Let X = (ξx , ξy )⊤ , m = EX, and u = (−1, 1)⊤ . The joint MGF proxy gives E exp{λu⊤ (X − m)} ≤ exp{λ2 u⊤ KQ u/2},

(31)

so Rrank − µR is sub-Gaussian with µR = u⊤ m,

2 = u⊤ KQ u = Kxx + Kyy − 2Kxy . νrank

(32)

For a fixed positive exact margin γ the failure event is Rrank ≤ −cQ γ, and Chernoff’s method gives Proposition 5. For the negative orientation the relevant right tail has effective margin cQ γ − µR . If νrank = 0, Jensen’s inequality and the MGF bound give Rrank = µR almost surely and the decision is deterministic. B.2 Shared-endpoint covariance for i.i.d. and selected populations Let X, Y, Z be i.i.d. and h ∈ L2 (P ⊗ P ) symmetric, with Hoeffding decomposition h(x, y) − µ = h1 (x) + h1 (y) + h2 (x, y),

(33)

where h2 is degenerate in each argument. Put a = Var(h1 (X)) and b = Var(h2 (X, Y )). Orthogonality gives Var(h(X, Y )) = 2a + b,

Cov(h(X, Y ), h(X, Z)) = a,

(34)

so that, when the marginal variance is positive, a 1 ≤ , 2a + b 2

Var(R1 ) + Var(R2 ) 2a + b = ≤ 2. Var(R1 − R2 ) a+b (35) The lower bounds are attained at a = 0, b > 0 and the upper bounds at b = 0, a > 0; if a = b = 0 both ratios are undefined. For query-conditioned roles let ma (Q) = E[Ra | Q], va (Q) = Var(Ra | Q), and c(Q) = Cov(RL , RR | Q). The laws of total covariance and total variance give 0 ≤ Corr(h(X, Y ), h(X, Z)) =

1≤

Cov(RL , RR ) = Ec(Q) + Cov(mL (Q), mR (Q)),

(36)

Var(RL − RR ) = E[vL (Q) + vR (Q) − 2c(Q)] + Var(mL (Q) − mR (Q)).

(37)

22

Low-Bit Decision Stability in Vector Search

When candidates are conditionally independent draws from a frozen selection kernel KQ , c(Q) = 0, and the pooled correlation is driven entirely by the second term; it can approach one when query-specific means dominate the conditional variance. Selection changes the candidate law, hence conditional means and variances; it changes the query mixture weights only if query sampling, retention, or row weighting also changes. For uniform sampling without replacement from a pool of size M , Cov(fI , gJ | Q) = −

cf g (Q) . M −1

(38)

A fixed anchor has zero conditional covariance because its residual is constant given the frozen state, so its within-query correlation is undefined. These identities describe second moments; the MGF proxy K is a separate input. B.3 Exact empirical within/between identity P For query group g with ng observed pairs (ℓgi , rgi ), let N = g ng , let ℓ̄g , r̄g be group means, and ℓ̄, r̄ row-weighted grand means. Expanding each centered product gives the deterministic identity X X X (ℓgi − ℓ̄)(rgi − r̄) = (ℓgi − ℓ̄g )(rgi − r̄g ) + ng (ℓ̄g − ℓ̄)(r̄g − r̄), (39) g,i

g

g,i

so that, with the pooled N − 1 denominator, spool =

X ng − 1 1 X sg + ng (ℓ̄g − ℓ̄)(r̄g − r̄). N −1 N −1 g

(40)

g:ng ≥2

The same matrix identity decomposes both marginal variances and therefore Var(RL − RR ). It holds for any row dependence; reading its two pieces as unbiased estimators of the population terms in (37) requires a sampling model. B.4 Fixed top-K Let C be fixed before the approximation randomness, let A be the exact top-K subset, and suppose no exact tie crosses the boundary. Exact top-K preservation follows if every x ∈ A stays ahead of every y ∈ C \ A, so XX b ̸= A) ≤ PQ (A PQ {dbQ (q, y) ≤ dbQ (q, x)}, (41) x∈A y ∈A /

and any deterministic sufficient comparison set may replace the full cross product.

Appendix C. Standard Vamana Pruning The RobustPrune rule declares candidate c dominated by selected neighbour s when αd(s, c) ≤ d(t, c) with α ≥ 1. Define Ψα = d(t, c) − αd(s, c),

b α,Q = cQ Ψα + Zα,Q , Ψ 23

Zα,Q = ξtc − αξsc ,

(42)

Xiao and Cao

with action D = 1{Ψα ≥ 0}. For nonzero margins the false-keep and false-prune events are b α,Q < 0}, {Ψα > 0, Ψ

b α,Q ≥ 0}, {Ψα < 0, Ψ

(43)

and at an exact structural tie disagreement is {Ψα = 0, Zα,Q < 0}. A no-atom property of Zα,Q rules out exact approximate ties but says nothing about this directional probability, which must be carried as its own term. With w = (1, −α)⊤ a joint MGF proxy gives (3)

2 να,Q = w⊤ KQ w = Ktc,tc + α2 Ksc,sc − 2αKtc,sc .

(44)

Writing µZ = EZα,Q , the two orientations have effective one-sided margins cQ γ + µZ and cQ γ−µZ . A through-origin calibration does not make µZ vanish, and a shared edge intercept b enters Zα,Q as (1 − α)b. If both edge residual magnitudes are deterministically at most ϵ, then |Zα,Q | ≤ (1 + α)ϵ.

Appendix D. Frozen Semantic Trace Coupling D.1 Candidate-level state machine Fix unique candidate labels in an exact-distance-sorted permutation π = (c(1) , . . . , c(N ) ) with deterministic tie-breaking, a target t, a degree budget M , and α ≥ 1. Starting from S1 = (), define at each visited position _ Di = 1{d(t, c(i) ) − αd(s, c(i) ) ≥ 0}. (45) s∈Si

Append c(i) exactly when Di = 0 and stop when the permutation is exhausted or the degree cap is reached. The call is append-only and has no refill; for a fixed sorted permutation it is equivalent to repeatedly selecting the nearest remaining candidate and deleting the candidates dominated by a selected point. b ∗ on the For each exact visited state evaluate the approximate counterfactual action D i b ∗ ̸= Di }. A first-divergence induction gives the determinexact prefix Si and write Ei = {D i istic identity [ {Tbsem ̸= Tsem } = {Sbout ̸= Sout } = Ei . (46) i∈V

The implication from output difference back to some Ei uses unique labels, append-only selection, and the absence of refill: the first action-disagreement candidate belongs to exactly one final set. D.2 Witness and conservative-event inclusions For s ∈ Si let  b i,s ≥ 0} . Ai,s = 1{Ψi,s ≥ 0} ̸= 1{Ψ

(47)

S

Then Ei ⊆ s∈Si Ai,s , and the inclusion can be strict because another witness may preserve b = γΨ + R with γ > 0, then for nonzero margins the OR. If Ψ b ≤ 0} ⊆ {Ψ ̸= 0, |R| ≥ γ|Ψ|}, A ∩ {Ψ ̸= 0} ⊆ {Ψ ̸= 0, ΨΨ 24

(48)

Low-Bit Decision Stability in Vector Search

b = 0. For exact ties, actual where the first inclusion can be strict when Ψ > 0 and Ψ disagreement is R < 0 and is added separately. Consequently, after fixing the data and the exact trace, P(Sbout ̸= Sout ) ≤

X X

1{Ψi,s > 0}P(−Ri,s ≥ γΨi,s )

i∈V s∈Si

+1{Ψi,s < 0}P(Ri,s ≥ γ|Ψi,s |)  +1{Ψi,s = 0}P(Ri,s < 0) ,

(49)

with no independence between comparisons. D.3 Edge, path, sorting, and saturation If the exact output edge (t, c) is selected at position jc , agreement of all candidate actions in the exact prefix through jc is sufficient for its survival. Source-scoped prefix certificates for a fixed path may be union-bounded without cross-source independence; the resulting statement is about retention of the listed edges. If approximate scoring changes the permutation, the ordering event is added: P(output divergence) ≤ P(b π ̸= π) +

X

P(Ei ).

(50)

i∈V

A deterministic saturation map that appends unselected candidates after RobustPrune satisfies {saturated-output divergence} ⊆ {standard-trace divergence}, (51) and the reverse inclusion fails in general, because distinct diversity traces can saturate to the same list. Saturation is therefore analysed as a post-processing map applied to the standard call.

Appendix E. Gaussian Residual Transfer E.1 Oracle decomposition i.i.d.

Let Gu ∼ N (µD , ΣD ) and Xu = Gu /∥Gu ∥. Define T (g) = D−1

X

|gi |,

qi (g) = sign(gi )[1 + 1{|gi | > T (g)}].

(52)

i

Positive scale invariance gives qi (X) = qi (G). Replacing T (G) by T D = ET (G) and ∥G∥ by rD = E∥G∥ defines the oracle kernel, and for every fixed edge combination Ra = Ra◦ + ∆a,thr + ∆a,shell .

(53)

The threshold remainder is supported on threshold deviation or coordinate boundary occupancy; the shell remainder is the difference between exact cosine normalization and the fixed-radius bilinear surrogate. 25

Xiao and Cao

E.2 Aligned magnitude-bit theorem p Let G, H be independent with independent coordinates Gi , Hi ∼ N (0, σi2 ). Put m = 2/π, zi = τ /σi , pi = 2[1 − Φ(zi )], ki = m + 2φ(zi ), and vi = 1 + 3pi . Coordinate independence gives Var(T ) =

X

σi4 ,

Cov(S1 , T ) = m2

X

i

Cov(S2 , T ) =

X

σi2 ,

Var(S1 ) = D,

(54)

i

σi2 ki2 ,

Var(S2 ) =

i

X

vi2 .

(55)

i

For every finite z > 0, k(z)2 > m2 v(z).

(56)

2

To see this write a = e−z /2 and h(z) = k(z)2 /m2 − v(z) = 2a + a2 − 6[1 − Φ(z)]. Then h(0) = limz→∞ h(z) = 0 and h′ (z) = a{3m−2z(1+a)}; since 2z(1+a) is strictly increasing, h rises and then falls and stays strictly positive on (0, ∞). Now set ti = σi2 and regard vi = v(ti ). Both v(t) and t/v(t) increase because tv ′ (t) = 3zφ(z) < 1 ≤ v(t). Pairwise expansion and Cauchy–Schwarz give P P 2 s X ti vi v 1 i P ≥ Pi i ≥ vi2 , t v D i i i i

(57)

i

and combining this with (56) proves ρ(S2 , T ) > ρ(S1 , T ). The alignment between P target and scorer is what makes the inequality hold. In the linear-target model T = i wi Gi with a fixed equally weighted scorer, take D = 8, w = (1, 1, 1, 1, 0, 0, 0, 0), coordinate standard deviations (1, 1, 1, 1, L, L, L, L), and τ = m(1 + L)/2. For L = 8 the two-bit minus one-bit Pearson correlation is −0.162687 . . .: the second bit amplifies four coordinates the target ignores, and a fixed readout loses. For equalP variance independent coordinates and the random threshold D−1 i |Gi |, the strong law and dominated convergence recover the deterministic-threshold correlation as D → ∞. E.3 Oracle covariance For the symmetric oracle kernel HD let h1,D (u) = E[HD (u, V )] − θD ,

h2,D (u, v) = HD (u, v) − θD − h1,D (u) − h1,D (v),

(58)

and κj = Eh2j . AggregatePdirected or repeated edges into unordered-pair coefficients Ap and node incidences du = p∋u Ap . Hoeffding orthogonality gives Var(Ra◦ ) = κ1

X u

d2u + κ2

X

A2p .

(59)

p

Disjoint edges have zero covariance, edges sharing exactly one node have covariance κ1 , and identical or reversed edges have variance 2κ1 + κ2 . 26

Low-Bit Decision Stability in Vector Search

E.4 Three analytical routes The coarse route combines a Gaussian quadratic-form MGF with a bounded score range; it needs no coordinate independence and is loose by four orders of magnitude on real embeddings (Appendix I). The exact-covariance route keeps (59) and adds a cumulant or conditional-MGF condition. The empirical route calibrates the fitted role residual on independent blocks. The three routes bound the same residual tail with different inputs; the decision shell of Theorem 2 accepts any of them.

Appendix F. Held-Out Certificates Condition on nuisance parameters fitted on an independent split. Let Z1 , . . . , Zn be independent blocks with arbitrary dependence among decisions inside a block. For threshold τ let u(Z, τ ) be the block-average indicator that a decision lies in the boundary event or the residual event, so that pointwise 0 ≤ f (Z) ≤ u(Z, τ ) ≤ 1 with f (Z) the block-average failure. For fixed τ , one-sided Hoeffding gives r log(1/δ) blk b pF ≤ Un (τ ) + (60) 2n with probability at least 1 − δ. For a prespecified grid T of size M , a union bound replaces δ by δ/M and licenses any calibration-measurable minimizer τb ∈ T . F.1 Selective ratio certificates Condition on the fit split. For selector s and threshold τ let Ci,s , Ui,s,τ , and Fi,s be the block fractions accepted, accepted and in the union event, and accepted and failed; empty blocks contribute zero, and pointwise 0 ≤ Fi,s ≤ Ui,s,τ ≤ Ci,s ≤ 1. The target is the ratio of expectations EFi,s EUi,s,τ ps = , qs,τ = , (61) ECi,s ECi,s which is the block-uniform selective risk, not the average of within-block ratios; it requires positive population coverage. The proof of Theorem 14 fixes q = qs,τ and uses Wi (q) = Ui,s,τ − qCi,s ∈ [−q, 1 − q] with EWi (q) = 0. The interval has length one, so a one-sided Hoeffding bound and a union bound over G = |G| pairs give qs,τ ≤

bs,τ + U

p log(G/δ)/(2n) bs C

(62)

bs > 0. Replacing U by F and paying only for the selector family simultaneously whenever C proves Corollary 15. No comparison-level independence is assumed. The p two-event baseline controls EU from above and EC from below separately. With ϵ2 = log(2G/δ)/(2n) it yields bs,τ + ϵ2 U qs,τ ≤ (63) bs − ϵ2 C 27

Xiao and Cao

when the denominator is positive; if only S0 distinct selectors occur, 2G may be replaced by G + S0 . Using log(G/δ) for both separate events would only establish failure probability 2δ. The direct-ratio event dominates: whenever its denominator is positive, the two-event expression is a looser consequence of (23). F.2 Empirical-Bernstein ratio inversion Let n ≥ 2, let VbW (t) be the unbiased sample variance of Wi (t) = Ui − tCi , and define L = log(2G/δ),

a=

p 2L/n,

q b − tC b + a VbW (t) + b, H(t) = U

b=

7L , 3(n − 1)

t ∈ [0, 1].

(64) (65)

Set ( inf{t ∈ [0, 1] : H(t) ≤ 0}, BEB = 1,

if the set is nonempty, otherwise.

(66)

Then qs,τ ≤ BEB,s,τ simultaneously over the grid with probability at least 1 − δ. At the population truth q, the range-one empirical Bernstein inequality gives P{H(q) < 0} ≤ δ/G. q The function H need not be monotone, but it has a single-crossing property. b − asU . Since 0 ≤ Ui ≤ 1, Write sU = VbU and η = b + U s2U ≤

n b U, n−1

b≤ asU − U

L , 2(n − 1)

(67)

so η ≥ 11L/[6(n − 1)] > 0. For 0 < r < t ≤ 1 put λ = t/r. From W (t) = λW (r) − (λ − 1)U and the triangle inequality for sample standard deviations, H(t) ≤ λH(r) − (λ − 1)η,

(68)

so H(r) ≤ 0 implies H(t) < 0 for every t > r. Since H(0) > 0 and H is continuous, the first crossing in (66) is a valid upper confidence endpoint and no grid over t is needed. Numerically, if H(1) ≥ 0 the implementation returns one; otherwise bisection returns the upper bracket endpoint. F.3 Independent selection and multiplicity If the block budget is split before observation into selection and certification blocks, a grid pair and certificate family may be chosen on the first part and, p conditionally on that choice, certified on the second part with the single-policy width log(1/δ)/(2ncert ) and no grid factor. Choosing again after viewing several certification results requires a common simultaneous guarantee. Likewise each prespecified method and sample size carries a marginal guarantee, and selecting the smallest certificate across a curve requires a confidence allocation across the points eligible for selection. 28

Low-Bit Decision Stability in Vector Search

Appendix G. Cross-Quantizer Instantiations G.1 RaBitQ For a fixed unit data direction o and query direction q, RaBitQ uses sbR (o, q) =

⟨ō(P ), q⟩ , ⟨ō(P ), o⟩

(69)

√ ⊤ o∥ / D ≥ whose denominator is positive for every orthogonal P because ⟨ō(P ), o⟩ = ∥P 1 √ 1/ D. The random-radius event is measurable under a fixed tie rule. A shared rotation couples the edges, so ranking and pruning statements go through the triangle inequality and a union bound over the joint event rather than through independence, and observing the realized radius does not create conditional coverage. For raw squared distance, 2

d ξR (ur , vr ) = −2ru rv εR (u, v),

(70)

and a pruning rule stated in Euclidean distance becomes an α2 rule after squaring, with the two edges keeping distinct radial factors. A rule stated directly in squared distance or cosine dissimilarity keeps its own parameter. G.2 BBQ and block estimators Lucene BBQ defines asymmetric scorer roles that determine graph topology: stored vectors are one-bit, temporary int4 query-role vectors support graph construction, and candidate collection as well as diversity and reverse-link scoring each need role-specific residual calibration. Our reference scorer implements the role semantics. Product quantizers and related block estimators enter through block residual sums, whose survival laws come from bounded blocks, block covariance, or held-out calibration. Native binary embeddings without a float teacher metric fall outside the latent-float residual formulation.

Appendix H. Necessity and Replacement Concentration H.1 Rare-contamination counterexample Let εD = D−4 , AD = D3/2 , and GD = (1 − JD )ZD + JD AD SD ,

(71)

where JD ∼ Bernoulli(εD ), ZD ∼ N (0, ID ), and SD has independent Rademacher coordinates; independent nodes use independent copies. Then Cov(GD ) = (1 + D−1 − D−4 )ID . For every fixed coordinate block of size k, mixture decomposition and Gaussian scale comparison give total-variation distance Ok (D−1 ) from the standardized Gaussian law. With √ rD = E∥GD ∥ ∼ D,  2 ∥GD ∥ E − 1 = O(D−1 ), (72) rD a relative mean-square statement whose L2 norm is O(D−1/2 ). At the population magnitude threshold the expected fraction of coordinates in a shrinking boundary band tends to zero. 29

Xiao and Cao

Fix 0 < η ≤ 1/8, βD = η/D, and define the fixed-threshold oracle residual RD = QD + BD ,

(73)

G⊤ 1 (G3 − G2 ) , 2 rD η X ◦ BD = − qi (G1 ){qi◦ (G3 ) − qi◦ (G2 )}. D

QD =

(74) (75)

i

Conditioning on the three contamination indicators and combining the two shared-endpoint edges coordinatewise gives independent centred coordinate summands, whence 2 EBD ≤ 32η 2 /D,

4 EBD ≤ 3072η 4 /D2 ,

(76)

4 /r 4 ∼ 2/D. The L2 reverse triangle inequality gives V while Var(QD ) = 2DσD D = D −1 Var(RD ) = Θ(D ). On AD = {J1 = J2 = 1, J3 = 0}, whose probability is ε2D (1 − εD ) = Θ(D−8 ),

QD =

AD S1⊤ Z3 − A2D S1⊤ S2 . 2 rD

(77)

Since E(S1⊤ S2 )4 = 3D2 − 2D, E[Q4D ; AD ] ≥

ε2D (1 − εD )A8D (3D2 − 2D) = (3 + o(1))D2 . 8 rD

(78)

4 = Ω(D 2 ), hence The L4 reverse triangle inequality and the bound on BD give ERD

κ4 (RD ) = Ω(D2 ),

κ4 (RD )/VD2 = Ω(D4 ).

(79) √ For a cumulant condition |κm (RD )| ≤ (m!/2)VD bm−2 D , the case m = 4 forces bD / VD = Ω(D2 ). For a two-sided MGF bound λ2 v , |λ| < 1/b, (80) 2(1 − b|λ|) √ evaluating both signs at λ = [2 max{ v, b}]−1 and√using cosh y − 1 ≥ y 4 /24 gives EX 4 ≤ 192v max{v, b2 }, so vD = O(VD ) again forces bD / VD = Ω(D2 ). The construction uses a fixed threshold, fixed normalization, and the oracle slope; it is a logical obstruction, and §8.7 measures how far real embeddings sit from it. log EeλX ≤

H.2 Replacement variance For the Hoeffding decomposition of Fa , independent replacement of node u gives (u) 2 1 2 E(Fa − Fa ) = E Var(Fa | G−u ).

(81)

Summing over nodes counts every first-order component once and every degenerate pair component twice, X X VES = κ1 d2u + 2κ2 A2p , (82) u

p

hence V ≤ VES ≤ 2V with equality at two when h1 = 0 and h2 ̸= 0. 30

Low-Bit Decision Stability in Vector Search

Table 11: Representation regimes. Each result file records the subset of datasets it uses. Group

Datasets

Contrastive text

Cohere, MiniLM, BGE-M3, Jina, MSMARCO Wolt-CLIP, Landmark-DINO GloVe, SIFT, GIST Gaussian, sphere, random, contaminated

Vision Classical Synthetic

D

Role

384–1024

primary regimes

512–768 100–960 64–2048

modality transfer negative controls mechanism and stress

H.3 Conditional MGF and stable truncation Let Dj be the three Doob increments. If deterministic vj , bj satisfy λ2 vj , (83) 2(1 − bj |λ|) P iterated conditioning gives the tail (20) with v⋆ = j vj and b⋆ = maxj bj . The expectation of a replacement proxy alone cannot be inserted into Freedman’s inequality; the conditional bounds must hold almost surely. A truncation route constructs a functional FL on the full input space with log E[eλDj | Fj−1 ] ≤

P(FL ̸= Fa ) ≤ εL ,

|EFa − EFL | ≤ dL .

(84)

If FL has a sub-gamma tail with (vL , bL ), then  z2 P(|Fa − EFa | ≥ z + dL ) ≤ 2 exp − + εL . 2(vL + bL z) 

(85)

Bounding replacements only on a good event suffices only when that event is stable under every single-node replacement, which is what the construction of FL on the full space provides. H.4 Negative component covariance For zero-mean Gaussian nodes of arbitrary covariance define Mij = E[qi◦ (G)Gj ]. Endpoint independence gives β1 X 2  (86) A ∥M ∥2F ≤ 0, Cov(Ba , Qa ) = − 2 rD p p with no symmetry or positive-semidefiniteness of M required. At nonzero mean, first-order projections reappear and the sign depends on separate cross-Hoeffding conditions.

Appendix I. Datasets, Protocols, and Experiment Inventory Every experiment draws a bounded sample from a memory-mapped source artifact rather than loading a full million-vector file. Calibration, validation, reference-integration, and stress pools are disjoint whenever the estimand requires it. Table 12 maps each experiment in the paper to its script and result file; script numbers refer to the numbered modules of the code release, and result files are named by experiment number with a suffix identifying the standard non-saturated RobustPrune rule where it is involved. 31

Xiao and Cao

Table 12: Experiment inventory. Section

Object

Scripts

Results

§8.2

margin bins, boundary exponent, held-out predictor shared-query covariance, selection regimes pruning replay, trace, edge, path, refill variant selective certificates, sample-size curves joint Gaussianity, oracle remainders, variance proxies conditional-MGF and truncation parameters margin-zero and matched-Spearman constructions cross-quantizer interface representation diagnostics, magnitude bit, rotation

07, 08, 16

24, 25, 33

09, 29

26, 46

10–14

27–31

17, 28

34, 45

15, 19, 21, 22

32, 36, 38, 39

23

40

18

35

20 01–06

37 1–23

§8.3 §8.4 §8.5 §8.7 §8.8 §8.9 §7 §5

Table 13: Geometry diagnostics. d90 is the PCA dimension explaining 90% of the variance; ∆θNN is a representative nearest-neighbour angular gap. Dataset

D

d90 /D

Mean angle

NN angle

∆θNN

Cohere BGE-M3 MiniLM GIST Random

768 1024 384 960 768

.309 .091 .497 .181 .268

45.8◦ 55.4◦ 88.8◦ 40.7◦ 87.6◦

35.4◦ 34.5◦ 65.6◦ 28.9◦ 67.9◦

.125◦ .248◦ .277◦ .091◦ .117◦

Appendix J. Representation Diagnostics The diagnostics in this section motivated the Gaussian model of §5 and the eligibility gate. Intrinsic dimension and average angle do not separate the regimes: GIST has the most concentrated geometry and the smallest local angular gap yet is the worst coordinatesign regime, while random vectors have regular high-dimensional geometry and no usable neighbour structure. The final theory conditions on decision margins and residual placement instead. The GIST row is the key negative control: almost all coordinate signs agree regardless of angular relation, whereas random hyperplanes keep an angular collision law. This is the origin of both the rotation mechanism and the eligibility gate. In the same-dimensional survey of nine 768-dimensional regimes, eight had R2 ≥ .9965; the near-isotropic RoBERTa regime had low R2 because its entropy variance is close to 32

Low-Bit Decision Stability in Vector Search

Table 14: Coordinate-sign versus random-hyperplane diagnostics. GW is the angular collision prediction and Hsign the normalized sign entropy. Dataset

Coord. sign

Random HP

GW

KL(coord∥HP)

Hsign

Cohere BGE-M3 MiniLM GIST Random

.650 .677 .508 .9999 .513

.744 .701 .506 .768 .513

.746 .692 .506 .774 .513

.0229 .0022 .0021 .2648 .0010

.747 .700 .987 .0004 .981

Table 15: Anisotropic Gaussian sign-entropy model. Sign entropy is predicted from coordinate SNR; R2 is unstable when entropy has almost no variance across coordinates, so MAE is reported alongside. Dataset Cohere BGE-M3 MiniLM Random GIST MSMARCO-Cohere

D

R2

MAE

Mean |SNR|

Measured / predicted entropy

768 1024 384 768 960 1024

.9996 .9989 .9222 .9967 failure .9995

.004 .007 .002 .001 .240 .0019

.884 .908 .127 .164 1.763 .370

.747 / .748 .700 / .699 .987 / .988 .981 / .982 .000 / .240 .910 / .910

zero, with MAE .00166. These are coordinate-wise checks; the joint Gaussianity audit of §8.7 is the stronger test.

Appendix K. Representation Mechanisms Tables 16 to 19 collect the representation-level measurements behind §5: the fidelity and recall gain of the magnitude bit, a controlled intervention on coordinate heterogeneity, the rotation response of the two-bit code, and the predictors of that response. In Table 19, excluding the one non-Gaussian outlier (Landmark-Nomic) raises the entropy-gap correlation to .964 and the heterogeneity correlation to .746; the response is independent of dimension. In the intervention study of Table 17, the correlation between heterogeneity and magnitude gain was +1.0 in four of five datasets. Rotation response and eligibility are different questions. Cohere (Hsign = .747, ∆Frot = +.170) and SIFT (Hsign = .746, ∆Frot = +.200) are nearly identical on both statistics, yet coordinate binary quantization is usable on Cohere and not on SIFT. The entropy gap predicts how much rotation changes a code; the eligibility gate (calibration slope, margin correlation, residual tail) decides whether the unrotated code was usable at all. This pair of datasets is why the paper reports two diagnostics rather than one routing statistic. 33

Xiao and Cao

Table 16: Magnitude-bit gain in global ranking fidelity and simulated recall across representations. Dataset MiniLM Cohere CodeSearch Landmark Arxiv Random

CV(σ)

∆F

∆ Recall

.118 .182 .098 .110 .108 .070

+.132 +.091 +.088 +.088 +.071 +.049

+.174 +.144 +.143 +.110 +.159 +.210

Table 17: Controlled coordinate-heterogeneity intervention on Cohere. Absolute fidelity and the magnitude-bit gain move in opposite directions. Intervention Amplify γ = 2 Amplify γ = 1.5 Original Whiten .50 Flatten

CV(σ)

F1bit

F2bit

∆Fmag

.316 .252 .182 .091 .002

.682 .694 .706 .720 .736

.719 .728 .738 .746 .757

.036 .034 .032 .026 .022

Appendix L. Local Ranking and Boundary Diagnostics The last two rows are the operational summary: on eligible two-bit configurations, two thirds to three quarters of decisions lie in the low-risk region M ≥ 2 and 7 to 9% fall below M = 1.

Appendix M. Pruning and Trace Composition Every observed triple disagreement is a false keep. Fixed-order output divergence occurs on 99.4 to 100% of sampled calls although local triple disagreement rates are 1.9 to 13.1%, as the first-divergence theorem permits: one candidate-level action disagreement changes an append-only output. In this experiment rotation leaves the fixed-order pruning statistics nearly unchanged, while the free-order replay also reflects candidate re-sorting. The implication “certificate passes ⇒ edge survives” held in every tested case. The numerical saturation reflects the conservativeness of witness-level additive probabilities, while the risk sum still orders edges by their observed failure. Path certificates saturate within two hops, and the observed path failure rate grows with length as the union of its edge failures. The certificate sufficiency implication held on every path. 34

Low-Bit Decision Stability in Vector Search

Table 18: Rotation responses of the two-bit code. Recall changes follow the original experiment reports. Dataset GIST Wolt-CLIP Cohere MiniLM

Sign entropy before → after

Recall response

.000 → .511 .836 → .616 .747 → .563 approximately unchanged

+307% +3.2 pp −0.5 pp approximately zero

Regime degenerate signs over-spread coordinate signal near-isotropic

Table 19: Predictors of the global two-bit rotation response ∆Frot over 12 datasets. Predictor

Spearman ρ

p

+.657 −.909 +.909 +.930 −.080

.020 < .001 < .001 < .001 .805

CV(σ) Hsign 1 − Hsign (1 − Hsign ) × CV(σ) log D

Appendix N. Analytical Eligibility and Variance Proxies The MiniLM and GIST source artifacts are stored unit-normalized, so their pre-normalization shell is not identifiable; Cohere retains radial information, with norm coefficient of variation 4.4% and 2.03% of vectors beyond a 10% relative shell. All 28 component cross-covariances are negative, with median cancellation ratio .947. In dimension stress tests from D = 64 to 2048, clean, equicorrelated, and block-correlated Gaussian regimes keep the oracle b⋆ /sd near .19 to .25; a dense global shock raises it towards .88 and is detected at the same time by the Gaussian, shell, and spectrum diagnostics. The rare-contamination construction of Theorem 13 is designed to pass those diagnostics, which is what makes it the relevant obstruction.

Appendix O. Held-Out Certificates This protocol uses 128 coefficient-fit, 512 risk-calibration, 512 validation, 256 stress-cutoff, and 512 stress-evaluation blocks per configuration. The prespecified grid has five selector cutoffs and seven thresholds plus the accept-all case, so |G| = 40; with n = 512 the width b + ϵn )/(C b − ϵn ), which Appendix F.1 is ϵn = .0808. The certificate is the two-event form (U shows to be a looser consequence of the direct-ratio event whenever its denominator is positive. Ranking certificates range from 11.23 to 58.25% and pruning certificates from 11.17 to 46.46%. The stress columns evaluate the frozen cutoff on the hardest fifth of margins from a separate pool. All 48 role configurations satisfy the block-level invariant 0 ≤ Fi ≤ Ui ≤ Ci ≤ 1, and every prespecified method and sample size showed validation risk below its certificate on all configurations. Certificate values decrease as the number of certification blocks grows; validation risks change little, while each method may select a different policy at each sam35

Xiao and Cao

Table 20: Fixed-local-set decision study on 32-neighbour candidate sets. The eligibility column is the empirical gate of §6. Dataset

Quantizer

Cohere Cohere MiniLM MiniLM GIST GIST

1-bit 2-bit 1-bit 2-bit 1-bit 2-bit

Eligible

Flip

Query failure

Boundary exponent

yes yes yes yes no no

8.89% 5.83% 11.21% 4.19% 100.00% 35.83%

63.12% 47.50% 59.38% 43.75% 100.00% 91.88%

1.526 1.526 1.500 1.500 1.595 1.595

Table 21: Standardized-margin bins, n = 4,960 decisions per configuration, with counts in parentheses; Table 6 pools these into six bins. On the ineligible GIST configuration the flip rate is flat in the margin, so no cutoff separates safe from unsafe decisions. Bin

Cohere 1-bit

Cohere 2-bit

MiniLM 1-bit

MiniLM 2-bit

GIST 2-bit

[0, .25) [.25, .5) [.5, .75) [.75, 1) [1, 1.5) [1.5, 2) [2, 3) [3, 5) [5, ∞)

33.3% (93) 31.3% (150) 30.2% (182) 21.3% (286) 13.2% (832) 8.49% (1083) 3.02% (1458) 0.12% (804) 0.00% (72)

48.6% (70) 35.3% (102) 24.8% (121) 20.3% (158) 11.9% (520) 7.68% (690) 2.54% (1577) 0.14% (1413) 0.00% (309)

48.1% (104) 36.0% (125) 37.4% (227) 24.7% (312) 15.8% (991) 10.2% (1064) 2.53% (1227) 0.28% (718) 0.00% (192)

50.0% (72) 39.6% (53) 29.5% (78) 23.9% (138) 11.5% (355) 5.95% (571) 1.29% (1393) 0.13% (1531) 0.00% (769)

41.1% (158) 37.5% (301) 39.2% (551) 35.7% (762) 28.2% (1389) 34.2% (803) 40.8% (622) 42.9% (231) 63.6% (143)

47.1% 14.3%

66.5% 9.1%

43.1% 15.5%

74.5% 6.9%

20.1% 35.7%

Share M ≥ 2 Share M < 1

ple size. The ranking failure label uses the same lexicographic tie-breaking as candidate ordering, and pruning uses the nonnegative-is-dominated convention.

Appendix P. Candidate-Selection Covariance This experiment holds one global affine edge scorer fixed and varies the pair-generation law, using 6,000 sampled vectors, 60,000 independent fit pairs, 160 query blocks, and 128 candidate pairs per query. The i.i.d. control samples all three endpoint identities independently with replacement; a distinct-triple control rejects identity collisions. In every regime the weighted within/between identity (39) reproduces the pooled covariance and the difference variance to floating-point precision. Query-block bootstrap intervals accompany the grouped regimes, and the 5th, 50th, and 95th percentiles of query-specific within covariance are retained because a small weighted average need not describe every query. The anchor’s left residual is constant within a query, so its within-query correlation is reported as undefined. 36

Low-Bit Decision Stability in Vector Search

Table 22: Shared-query covariance audit on 32-neighbour anchor pairs. “Ind./true” is the independence variance divided by the observed difference variance. Dataset

Quantizer

Cohere Cohere Cohere Cohere MiniLM MiniLM GIST GIST GIST GIST

1-bit 2-bit rotated 1-bit rotated 2-bit 1-bit 2-bit 1-bit 2-bit rotated 1-bit rotated 2-bit

Flip

Residual corr.

Ind./true

Tail gate

8.89% 5.83% 15.58% 8.81% 11.21% 4.19% 100.00% 35.83% 14.80% 9.33%

.794 .870 .465 .435 .047 .093 .902 .832 .585 .529

4.71 7.42 1.87 1.77 1.05 1.10 8.89 5.70 2.34 2.09

pass pass pass pass pass pass abstain abstain pass pass

Table 23: Standard non-saturated RobustPrune replay with exact candidate pools (α = 1.2, M = 32, 64 candidates, 160 targets). Free-order divergence includes the sorting change. Dataset

Quantizer

Local flip

Fixed-order divergence

Fixed Jaccard

Free Jaccard

Cohere Cohere MiniLM MiniLM GIST GIST

2-bit rotated 2-bit 2-bit rotated 2-bit 2-bit rotated 2-bit

13.06% 13.07% 1.92% 1.92% 7.91% 7.90%

100.0% 100.0% 100.0% 100.0% 99.4% 99.4%

.322 .322 .654 .656 .458 .458

.395 .289 .529 .529 .260 .359

Appendix Q. Cross-Quantizer and Conditional-MGF Audits Table 4 averages over Cohere, MiniLM, SIFT, and GIST. Each family uses 1,200 fit vectors and 2,000 held-out vectors per dataset, generating 60,000 ranking and 60,000 pruning triples. The RaBitQ reference uses a seeded signed-DCT orthogonal transform without query scalar quantization; the BBQ-like reference implements centroid-centred one-bit storage with an int4 query role and omits Lucene’s metric-specific corrections; the PQ reference uses 16 subspaces with 16 centroids each, for 64 index bits per vector excluding codebooks. The four disjoint pools contain 900 fit, 1,200 reference, 1,200 calibration, and 1,200 validation vectors. Nested integration uses 160 first-node groups, 16 second nodes, 12 observed third nodes, and separate reference completions; clipping cutoffs are the .95, .975, and .99 calibration quantiles. No held-out tail exceeded its hybrid bound.

Appendix R. Negative Controls The framework’s failure modes are distinct and each is observable: nonpositive calibration, heavy residual tails, high boundary mass, a saturated trace or path certificate, a postprocessing map that merges distinct traces, an unidentifiable shell, and deployment blocks 37

Xiao and Cao

Table 24: Exact-prefix edge certificates under standard RobustPrune (two-bit codes). “Saturation” is the fraction of plug-in additive bounds at least one; the last column is the Spearman correlation between the plug-in risk sum and observed edge failure. Dataset

Edges

Mean prefix terms

Fixed-order failure

Saturation

Risk–failure ρ

Cohere MiniLM GIST

3,054 5,118 3,701

24.7 21.0 21.7

34.3% 21.5% 24.7%

89.0% 89.4% 91.6%

.81 .69 .73

Table 25: Saturating refill applied after the standard call (α = 1.2, M = 32). The refill is a post-processing variant and not part of RobustPrune. Dataset

Diversity-selected

Refill-added

Refill share

Cohere MiniLM GIST

21.07 32.00 22.80

10.93 0.00 9.20

34.14% 0.00% 28.75%

that differ from calibration blocks. Each produces either an empirically high risk or an uncertified decision.

Appendix S. Code Release The release consists of numbered, non-interactive Python modules with fixed seeds and machine-readable outputs: modules 01–06 compute the representation diagnostics of Appendices J and K; 07–09 the decision-stability and covariance experiments; 10–14 the pruning replay, trace, edge, refill, and path experiments; 15, 19, 21, and 22 the Gaussian eligibility audits; 16, 17, and 28 the held-out certificates; 18 the necessity constructions; 20 the cross-quantizer interface; 23 the conditional-MGF parameters; 24–27 the semantic and numerical audits of the pruning rule, calibration, Stein identity, and contamination formulas; and 29 the candidate-selection covariance experiment. Samples are drawn without loading complete artifacts, no validation outcome is used to retune a frozen certificate, and negative results, ineligible configurations, and saturated bounds remain in the result files.

References Roy Betser, Eyal Gofer, Meir Yossef Levi, and Guy Gilboa. Infonce induces gaussian distribution. In International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=BlSH7gNQSq. Oral presentation. Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013. Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pages 380–388, 38

Low-Bit Decision Stability in Vector Search

Table 26: Fixed-order diversity-path composition for the unrotated two-bit scorer, 600 paths per length. “Fail” is the observed path failure rate and “sat.” the fraction of saturated plug-in certificates, both in percent.

Dataset

1 hop fail sat.

2 hops fail sat.

3 hops fail sat.

4 hops fail sat.

Cohere MiniLM GIST

33.8 17.7 24.0

50.0 35.5 46.0

68.2 46.3 60.8

78.7 58.7 72.3

88.2 89.5 84.7

98.8 98.3 98.7

99.8 99.8 99.8

100.0 100.0 100.0

Table 27: Oracle remainder and covariance audit (two-bit codes). “Oracle error” is the relative error of the incidence-covariance prediction against the measured role variance for ranking / pruning; coarse looseness is the coarse proxy divided by the empirical oracle role variance. Dataset

Coordinates

Cohere Cohere MiniLM MiniLM GIST GIST

original rotated original rotated original rotated

Mag. flips

Remainder share

Oracle error (R / P)

Coarse loose.

1.834% .313% .509% .516% 3.446% .267%

4.66% 2.09% 1.31% 1.37% 100.73% 2.30%

3.1% / 4.6% 0.7% / 2.1% 0.3% / 1.0% 0.9% / 1.5% 0.0% / 0.7% 2.3% / 1.4%

11,420 51,130 13,876 13,969 19,016 77,414

2002. Bradley Efron and Charles Stein. The jackknife estimate of variance. The Annals of Statistics, 9(3):586–596, 1981. Jianyang Gao and Cheng Long. Rabitq: Quantizing high-dimensional vectors with a theoretical error bound for approximate nearest neighbor search. Proceedings of the ACM on Management of Data, 2(3):1–27, 2024. doi: 10.1145/3654970. Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(4):744–755, 2014. Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning, pages 3887–3896, 2020. Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33 (1):117–128, 2011. Yu A Malkov and D A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4):824–836, 2020. 39

Xiao and Cao

Table 28: Looseness of the variance proxies over 28 dataset–coordinate–role configurations (seven datasets, two coordinate systems, two roles). Proxy

Minimum

Median

Mean

Maximum

403 5.91 1.21

22,044 40.84 1.67

27,109 47.59 1.72

73,572 93.13 2.04

Coarse range Componentwise Cauchy–Schwarz Replacement (Efron–Stein)

Table 29: Five-pool selective certificate protocol at 512 certification blocks (δ = .05). “No exceedance” counts configurations whose validation risk stayed below the frozen certificate. Role Ranking Pruning

Issued

No exceedance

Retained

Validation risk

Certificate

Stress risk

24 24

24 24

66.54% 67.26%

.370% .848%

19.76% 22.75%

13.02% 21.47%

Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. In Conference on Learning Theory, pages 115–124, 2009. Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnaswamy, and Rohan Kadekodi. Diskann: Fast accurate billion-point nearest neighbor search on a single node. In Advances in Neural Information Processing Systems, volume 32, 2019. Benjamin Trent. Better binary quantization (BBQ) in Lucene and Elasticsearch. Elastic Search Labs, 2024. URL https://www.elastic.co/search-labs/blog/ better-binary-quantization-lucene-elasticsearch. Accessed 2026-09-08. Alexandre B. Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135–166, 2004. Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018. Wenxuan Xiao, Zhiyou Wang, and Chengcheng Li. Quiver: Rethinking ann graph topology via training-free binary quantization, 2026. URL https://arxiv.org/abs/2605.02171.

40

Low-Bit Decision Stability in Vector Search

Table 30: Selective certificate comparison over prespecified sample sizes (δ = .05). Each entry averages 24 dataset–quantizer configurations; each method optimizes its own policy. Validation coverage and risk are measured on 1,024 independent blocks. Entries are ranking / pruning. Blocks

Method

Certificate

Validation coverage

Validation risk

128 128 128 128

two-event Hoeffding direct union empirical-Bernstein union direct failure

40.22% / 43.96% 29.08% / 31.32% 28.60% / 29.52% 16.29% / 18.62%

76.8% / 73.4% 70.4% / 68.4% 67.9% / 68.4% 95.1% / 88.5%

0.99% / 1.91% 0.45% / 0.94% 0.37% / 0.94% 2.18% / 3.31%

256 256 256 256

two-event Hoeffding direct union empirical-Bernstein union direct failure

28.58% / 31.39% 22.26% / 24.07% 16.44% / 17.64% 12.18% / 13.96%

70.4% / 70.1% 66.2% / 67.6% 62.0% / 61.0% 93.5% / 82.7%

0.45% / 1.26% 0.35% / 0.86% 0.26% / 0.75% 1.95% / 2.32%

512 512 512 512

two-event Hoeffding direct union empirical-Bernstein union direct failure

20.59% / 22.95% 16.74% / 18.65% 9.49% / 10.91% 9.07% / 10.45%

67.0% / 67.6% 64.6% / 63.5% 61.2% / 56.8% 87.8% / 80.2%

0.42% / 0.86% 0.33% / 0.75% 0.26% / 0.72% 1.34% / 2.01%

1,024 1,024 1,024 1,024

two-event Hoeffding direct union empirical-Bernstein union direct failure

15.13% / 17.36% 12.74% / 14.65% 6.13% / 7.27% 6.75% / 7.99%

63.7% / 61.0% 61.2% / 61.0% 57.7% / 51.1% 81.9% / 75.2%

0.32% / 0.75% 0.26% / 0.75% 0.22% / 0.44% 0.94% / 1.44%

Table 31: Pooled residual correlation across candidate-selection regimes. Dataset

Scorer

i.i.d.

Distinct

Random

Top-256

Top-32

Anchor

Cohere Cohere Cohere MiniLM GIST GIST

1-bit 2-bit rotated 2-bit 2-bit 1-bit 2-bit

.361 .391 .259 .010 .386 .405

.364 .393 .259 .010 .387 .405

.312 .346 .212 .020 .370 .422

.524 .571 .324 .067 .925 .576

.525 .599 .340 .111 .934 .640

.544 .613 .364 .118 .870 .616

Table 32: Conditional-MGF and stable-clipping parameters over 24 role configurations (six datasets, two quantizers, two roles). Quantity Untruncated b⋆ /sd Doob variance sum / total variance Validation / calibration variance Clipped b⋆ /sd (1% exceptional mass)

41

Minimum

Median

Maximum

.133 1.047 .945 .130

.158 1.086 .994 .147

.324 1.102 1.075 .258

Xiao and Cao

Table 33: Matched-Spearman construction (n = 500,000). The two perturbations share the exact scores and the same rank fidelity; mean squared error orders them the wrong way. Perturbation Light-tail Gaussian Boundary-coupled

Spearman

MSE

Global flip

Hardest-20% flip

.9860281863 .9860281863

.02514 .01700

5.09% 10.00%

23.91% 50.00%

42

Related documents

• Databases with Missing Values that are Governed by Missingness Mechanisms#1043177
• Proof-of-Retention: A Framework for Auditable Cross-Organization Data Sharing#1043178
• AkasicMEM: Governed Enterprise Memory for Agents#1043179
• Spend Classification Without Leakage: An Evaluation Harness and What It Changed in a Deployed System#1043180
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#1043181