IVF-TQ: Streaming-Robust Approximate Nearest Neighbor Search via a Codebook-Free Residual Layer
arXiv:2605.17415v1 [cs.LG] 17 May 2026
Tarun Sharma
Abstract We propose IVF-TQ, an IVF index with a codebook-free residual layer: a fixed random rotation followed by precomputed Lloyd–Max scalar quantization depending only on (b, d). Only the IVF coarse partition is trained. Building on TurboQuant (Zandieh et al., 2025a), the design substantially reduces a key failure mode of trained-codebook ANN indexes (PQ, OPQ, ScaNN): staleness under streaming ingestion. Empirical (3 seeds). Per-batch PQ retraining does not recover the streaming gap at any tested bit budget (paired-t p > 0.28 everywhere). On streaming Deep-10M, IVF-TQ holds at 87.4% → 86.6% (∆ = −0.80 ± 0.10pp) while IVF-PQ degrades −3.23pp. A shuffled-i.i.d. control on SIFT-1M shows IVF-PQ losing −3.9pp without distribution shift. At higher PQ bit budgets (∼1.5× IVF-TQ memory), absolute recall favors PQ as expected from rate-distortion (+6.1pp Deep-10M; +2.0pp SIFT-10M); the durable IVF-TQ benefit is operational (no codebook to retrain), robust across memory regimes. Prior art. IVF around a codebook-free residual quantizer is architecturally not new—IVFRaBitQ ships in Milvus, cuVS, LanceDB, Weaviate; Shi et al. (2026) is concurrent GPU work. TurboQuant itself tests only flat-rotation ANN. Contributions. (i) A multi-seed streaming-operational story for codebook-free IVF : 10M-scale evidence across PQ memory budgets. (ii) A uniform-over-sphere IP-error bound for the TQ residual quantizer with one fixed rotation (proof sketch in v1; rigorous in v2). (iii) Adaptive IVF-TQ: a partition-only refresh recovering 67% → 97.8% under worst-case rotation shift with re-ranking (90.3% without). Code, data: https://github.com/tarun-ks/turboquant_search
1
Introduction
We propose IVF-TQ, an inverted-file index whose residual layer is codebook-free. Across three seeds (42, 123, 7777), IVF-TQ reduces streaming recall degradation from −3 to −6pp (IVF-PQ at ∼0.75× IVF-TQ memory) to within 1pp on the same workload. The durable cross-regime finding: per-batch PQ retraining does not recover the streaming gap at any tested bit budget (paired-t p > 0.28 in every cell). IVF-TQ’s no-codebook-to-retrain property is therefore the consistent advantage independent of the PQ memory operating point. The streaming problem in production ANN. Vector ANN indexes are increasingly deployed against streaming corpora: retrieval-augmented generation pipelines (Lewis et al., 2020) re-ingest hundreds of thousands of documents per day, recommendation feeds operate under continuous concept drift, and observability and security pipelines continuously stream new embeddings. Practitioners observe that recall on these workloads silently degrades over weeks or months, often without 1
any code changes. The dominant compression methods used in production—product quantization (Jégou et al., 2011), Optimized PQ (Ge et al., 2014), ScaNN’s anisotropic learned quantization (Guo et al., 2020), and Extended RaBitQ (Gao et al., 2025)—all share one property: each fits a codebook (anisotropic or otherwise) to an initial training sample. That codebook is then reused as the database grows by orders of magnitude. The standard remedy is periodic re-training and re-encoding, which is expensive and—at the moderate-compression regime (5–6 bits/dim) most modern systems use—recovers only ∼ 0.15pp on a 10M streaming run that costs 309s of cumulative compute (§4.2). Concurrently, Aden-Ali et al. (2025) address the same problem by making PQ-style codebooks dynamically consistent under bounded I/O per update; we instead remove the codebook from the compression layer entirely. Distribution shift is not required. A natural explanation for streaming degradation is distribution shift: new vectors no longer match the training-sample statistics, so the codebook drifts out of distribution. Our shuffled-i.i.d. control (Table 2) refutes this as a sufficient explanation. With the streaming portion uniformly resampled from the same underlying distribution as the initial 200K training sample, IVF-PQ on SIFT-1M still loses −3.8pp from the 200K state to the 1M state—comparable to the −4.2pp under the original (out-of-distribution) order. A second control (Table 3) shows that retraining the codebook on a uniformly-random 200K, or even on the full 1M (oracle), does not detectably improve recall at this bit budget: the gap is below the measurement floor. The combination rules out distribution shift as necessary, and retraining as remedy. We are explicit that this is a pair of negative results, not a positive identification of the failure mechanism (§4.1 discusses what the controls do and do not establish). Memory-regime dependence of the recall comparison. At the sub-matched PQ memory budget (∼0.75× IVF-TQ) used in our streaming experiments, IVF-TQ leads IVF-PQ by +7.7pp on Deep-10M and +17.9pp on SIFT-10M at the 10M state (paired p<0.001). At a super-matched budget (∼1.5× IVF-TQ memory, PQ m=96/128 at 8 bits/subspace), absolute recall favors IVFPQ by −6.1pp on Deep-10M and −2.0pp on SIFT-10M—as expected from rate-distortion. A truly bit-matched 8-bit PQ on dim 96 or dim 128 is not a standard FAISS-optimized configuration (§7); we conjecture, but do not show, that bit-matched PQ would land between the two. The retraining-doesn’t-help finding (paired-t p>0.28) holds at every memory regime tested, so the recommendation—to remove the codebook from the residual layer entirely—is invariant to the memory operating point. This paper. We argue that the right design choice is to make the residual compression layer codebook-free. Building on TurboQuant (Zandieh et al., 2025a), we propose IVF-TQ: residuals are compressed by a fixed random rotation followed by precomputed Lloyd–Max scalar quantization. The IVF decomposition ⟨q, x⟩ = ⟨q, cl ⟩ + ⟨q, r⟩ keeps the coarse term exact, so only the smaller residual is compressed. We make three contributions: 1. IVF-amplification observation for codebook-free residual quantization (§3.2). IVF wrapping of codebook-free residual quantizers already exists in production (Milvus IVFRaBitQ, NVIDIA cuVS, Weaviate’s rotational quantization) and in concurrent work (Shi et al., 2026); the architecture itself is therefore not the contribution. What we identify is that the IVF decomposition gives a residual-variance reduction ratio of 1−2E[⟨x, cl ⟩]+E[∥cl ∥2 ] that explains the +17.7pp recall jump from flat to IVF-wrapped data-independent quantization at matched bit budget on SIFT-1M (L=1000). The same jump closes the gap to Extended RaBitQ (Gao et al., 2025) to within statistical noise: mean ∆ = +0.08pp across 9 dataset × 2
bit-budget cells, paired t-test p=0.50 (Table 12). This variance-reduction explanation, and its operational consequence for codebook-free residual layers, has not been articulated in the IVF-RaBitQ literature. 2. Uniform-over-sphere inner-product error bound for the residual quantizer (Theorem 2, §3.2). Zandieh et al. (2025a) prove an in-expectation MSE bound and a per-pair unbiased IP estimator for the random-rotation + Lloyd–Max quantizer; we extend their result to a high-probability bound on |⟨q, v⟩ − ⟨q, v̂⟩| that holds simultaneously for every v ∈ S d−1 with one fixed rotation Π. Uniformity over the sphere is what removes per-vector union-bound penalties when the database grows. A high-probability lift of TurboQuant’s MSE bound (Theorem 1) is stated as proof scaffolding and is not claimed as new. The bound is dataindependent (depends only on (b, d, δ), no training sample); we are explicit that at typical ANN scales it is numerically loose (full bound ≈ 0.69 on a [−1, 1] score axis vs. per-pair score gaps of order 0.01; see §3.2 “Tightness in practice”), so it is consistent with—but does not numerically predict—the observed streaming invariance. 3. Adaptive coarse refresh (§3.3, §4.5): a partition-only refresh enabled by data-independent compression. PQ-family methods cannot refresh the coarse partition without also re-training their codebook and re-encoding every stored vector; data-independent compression breaks this coupling. Under worst-case rotation shift, IVF-TQ frozen drops to 67% recall; Adaptive IVF-TQ recovers to 97.8% with re-ranking on top-50. We are explicit that at apples-to-apples bit budget (no re-ranking), Adaptive IVF-TQ at 4-bit reaches 90.3% versus PQ retrain’s 95.8% at m=96 (∼8 bits/dim per subspace, a higher bit budget than Adaptive uses)—a 5.5pp deficit attributable to the bit-budget gap, not the algorithm. Adaptive’s headline contribution stands in the re-ranking-enabled regime; we report both numbers in the abstract and intro rather than only the favourable one. Novelty summary, in one sentence. The architectural pattern of IVF wrapping a codebookfree residual quantizer is known (IVF-RaBitQ, concurrent GPU work); what is new here is the choice of Lloyd–Max as the residual primitive plus the operational analysis under streaming ingestion, plus the uniform-over-sphere IP-error bound. Two findings reported as observations, not contributions. Sign-bit refinement (Appendix A): a 1-bit Stage 2 that variance-reduces TurboQuant’s QJL correction. In flat TQ it improves Recall@10 by +11.4pp on average over QJL across three million-scale benchmarks (Table 11). In IVF-TQ the gain disappears (mean ∆ = +0.08pp). We document the flat-TQ benefit and the null in the IVF-TQ regime; we do not headline sign-bit refinement. Lloyd–Max bin ordinality (Appendix E): TQ’s MSB:LSB rank-relevance is ∼19× vs. ∼1× for IVF-PQ—a striking structural property that TQ codes are ordinal where PQ codes are categorical—and a two-pass cascade preserves Recall@10 within ±0.02pp across 16 conditions in C++. The cascade yields a 2× speedup in our Python reference but no speedup in our current C++ kernel; we defer the FastScan-style SIMD kernels (the Quick ADC technique of André et al., 2017, as packaged in FAISS) needed to realise the speedup to future work.
3
2
Background
2.1
IVF-PQ and learned quantization
PQ (Jégou et al., 2011) partitions a d-dimensional vector into m subspaces and learns a K=256centroid codebook per subspace via k-means. IVF-PQ—i.e., the IVFADC scheme of Jégou et al. (2011)—adds a coarse L-cell k-means partition and compresses only the residual r = x − cl with PQ. OPQ (Ge et al., 2014) adds a learned orthogonal rotation that aligns subspaces with the data covariance; ScaNN (Guo et al., 2020) learns the codebook to minimize an anisotropic loss tailored to inner-product ranking. All three methods produce a codebook that depends on the training sample.
2.2
TurboQuant: data-independent scalar quantization
TurboQuant (Zandieh et al., 2025a) applies a fixed random orthogonal rotation Π ∈ Rd×d before quantization. Because Π preserves inner products and rotates each coordinate to be approximately N (0, 1/d) on the unit sphere, a precomputed Lloyd–Max (Lloyd, 1982) scalar quantizer of b bits/coord achieves the per-coordinate minimum-MSE rate independent of the data. The quantizer never needs re-training. TurboQuant’s original Stage 2 used the QJL transform (Zandieh et al., 2025b) for an unbiased correction; we show this is suboptimal for ranking (Appendix A). TurboQuant’s ANN experiments are flat-rotation only—they do not wrap TurboQuant in IVF or any other coarse-partition index, which leaves the IVF-wrapped regime open. The concurrent IVF-RaBitQ family (Milvus, NVIDIA cuVS, Shi et al., 2026) wraps a binary-residual codebook-free quantizer in IVF but does not analyse the streaming-operational story we focus on here (see §4, and Related Work).
3
IVF-TQ
3.1
Architecture
IVF-TQ trains L centroids by k-means on the database (the only training step). At indexing, each vector x is assigned to its nearest centroid cl , the residual r = x − cl is rotated, and TQ quantizes per-coordinate with Lloyd–Max plus sign-bit refinement. Search probes np partitions, computes ⟨q, cl ⟩ exactly, and adds the compressed residual estimate. Re-ranking on raw vectors is optional. New vectors enter at any time at full compression quality. Stage 2 (sign-bit refinement). For the per-coordinate stage we use a half-bin conditional-mean refinement: each rotated coordinate stores one extra bit indicating which half of its Lloyd–Max bin it falls in, and reconstruction uses the conditional half-bin mean. This is a variance-reducing variant of TurboQuant’s QJL stage 2 (Zandieh et al., 2025b). In the flat-TQ regime it improves Recall@10 by +11.4pp on average over QJL (Appendix A). In the IVF-TQ regime it ties Extended RaBitQ at matched memory (mean ∆ = +0.08pp across 9 cells, paired t-test p=0.50; Table 12 in Appendix A). We document both regimes but do not headline sign-bit refinement as an IVF-TQ contribution: IVF amplification (§3.2) is what makes the residual layer competitive, and the choice of Stage 2 quantizer does not materially change IVF-TQ recall.
4
IVF-TQ: Indexing and Search Pipeline INDEXING Input vector x
Assign to nearest cl
Residual r = x cl
Rotate r= r
Lloyd--Max + sign-bit (no codebook)
Top-np partitions
Coarse q, cl (exact)
Fine qr, r (compressed)
Merge top-k
SEARCH Query q
Key: coarse score is exact; only the small residual is compressed by TQ Figure 1: IVF-TQ pipeline. Top: indexing has no codebook training; only k-means coarse centroids are learned. Bottom: search computes the coarse score exactly and compresses only the residual.
3.2
IVF amplifies codebook-free quantization
The IVF decomposition ⟨q, x⟩ = ⟨q, cl ⟩ + ⟨q, r⟩ keeps the coarse term exact. Only the residual r is compressed. Heuristic argument (not a theorem). Let r̂ denote TQ’s reconstruction of r, with quantization error ϵ = r − r̂. Under flat TQ the score-estimation error is ⟨q, ϵx ⟩ with ϵx = x − x̂; under IVF-TQ it is ⟨q, ϵ⟩. Assuming the database is unit-normalized (∥x∥ = 1, so E[∥x∥2 ] = 1) and TQ’s per-coordinate MSE scales linearly with signal variance (which holds asymptotically for the rate-b Lloyd–Max quantizer on the Gaussian source, but only approximately at finite b on the residual distribution), then E[⟨q, ϵ⟩2 ] E[∥r∥2 ] ≈ = E[∥r∥2 ] = 1 − 2E[⟨x, cl ⟩] + E[∥cl ∥2 ]. 2 E[⟨q, ϵx ⟩ ] E[∥x∥2 ] The unit-norm assumption is standard for the cosine/inner-product ANN setting we target (§5). For unit vectors with high cluster affinity (⟨x, cl ⟩ ≈ 1 and ∥cl ∥ ≈ 1) this ratio approaches 2(1 − ⟨x, cl ⟩) and is small. We state this as a heuristic, not a proposition: the residual distribution is not actually a scaled-down Gaussian (Lloyd–Max optimality is sample-dependent and the residual covariance differs from the original covariance), so the ratio is an approximation. The genuine empirical evidence is the +17.7pp recall jump, not this ratio. On SIFT-1M with L=1000, the empirical E[⟨x, cl ⟩] ≈ 0.85, and centroid magnitudes ∥cl ∥ are slightly below unit norm (clusters of approximately-normalized vectors), giving a several-fold residual-MSE reduction by the heuristic ratio above. The empirical jump from flat TQ (69.8%; Table 11) to IVF-TQ at np =20 (87.5%; Table 10) on SIFT-1M at matched bit budget (b=4 + sign-bit) is +17.7pp, qualitatively consistent with this prediction. The qualifier “qualitatively” is load-bearing: the assumption that per-coordinate MSE scales linearly with signal variance holds only approximately for Lloyd–Max at finite b, and the recall gap depends on score-distribution geometry beyond MSE alone. Recall ceiling of learned-codebook indexes. For any fixed PQ configuration (fixed m), IVFPQ exhibits a per-configuration recall ceiling: increasing np beyond a certain point yields diminishing returns because PQ’s quantization error—not partition coverage—becomes the binding con5
straint (Table 1). The ceiling scales with the bit budget and is one face of the same capacity issue √ exposed in §4.1. IVF-TQ also has a ceiling at fixed bits/dim—the rate-distortion floor Db —but the ceiling is set by (b, d) alone rather than by the configuration-specific PQ codebook, so it is higher and configuration-independent. We are explicit about this: “no per-configuration ceiling” was loose phrasing in an earlier draft. Table 1: PQ recall ceiling on SIFT-1M (np =160, 10K queries). PQ’s ceiling scales with bit budget m and√is set per-configuration by the learned codebook. IVF-TQ has a ceiling at the rate-distortion floor Db which depends only on (b, d). PQ m
Bits/dim
Ceiling R@10
Memory
8 16 32 64 128
0.5 1.0 2.0 4.0 8.0
14.0% 28.1% 46.3% 73.2% 92.9%
8 MB 16 MB 31 MB 62 MB 123 MB
87.5%
81 MB
IVF-TQ 4-bit (5.0 bits/dim)
Rate-distortion bound for TQ residual quantization. The TQ reconstruction v̂ := Π⊤ Cb (Πv) admits a high-probability error bound depending only on (b, d, δ). Let Db := d·ET ∼N (0,1/d) [(Cb (T )− T )2 ] denote the b-bit rate-distortion limit for the per-coordinate Gaussian source. Zandieh et al. √ (2025a) prove an in-expectation MSE bound Dmse ≤ ( 3π/2) · 4−b for this quantizer (their Theorem 1); we state the standard high-probability counterpart below as proof scaffolding for our uniform IP-error bound (Theorem 2). The lift from in-expectation to high-probability is a routine Lévy–Milman concentration argument and is not claimed as a new result; we restate it in our notation for self-containedness. Theorem 1 (High-probability MSE bound for TQ; restatement of Zandieh et al., 2025a Thm. 1 in high-probability form; proof in Appendix F). Fix any unit vector v ∈ S d−1 . For any δ ∈ (0, 1), with probability at least 1 − δ over the random rotation Π: r p 8 log(2/δ) ∥v̂ − v∥2 ≤ Db + Rd + , d−2 √ where Rd = O(1/ d) captures the deviation of the marginal of (Πv)j from the Gaussian source for which Cb is designed. Theorem 1 bounds the reconstruction error of a single fixed vector. Zandieh et al. (2025a) additionally prove a per-pair, in-expectation bound on the inner-product estimation error (their Theorem 2). For ANN ranking applied to streaming sequences, we need a stronger statement: a bound that holds uniformly over the unit sphere with one fixed rotation, so that adding the N -th vector to the index does not consume any union-bound budget. We provide such a bound below. It is the new theoretical statement in this paper; the rate-tightness it inherits comes from the per-pair argument already in Zandieh et al. (2025a), and what is novel is the uniformity (replacing perpair with simultaneously-over-the-sphere) and the lift from in-expectation to high-probability. The proof is presented as a sketch in Appendix F; two steps rely on a Lipschitz argument we have not yet replaced with a rigorous bounded-difference version, and the rigorous proof is on the v2 follow-up list. The bound itself is consistent with Zandieh et al. (2025a) Thm. 2 lifted to high probability via a covering net. 6
Theorem 2 (Uniform-over-sphere IP-error bound for TQ; novel; proof sketch in v1, rigorous proof in v2; see Appendix F). Under the setup of Theorem 1, fix any query q ∈ S d−1 and any δ ∈ (0, 1). With probability at least 1 − δ over Π, simultaneously for every v ∈ S d−1 : r d log(3d) + log(2/δ) ′ ⟨q, v⟩ − ⟨q, v̂⟩ ≤ Db + Rd + 2Db · + d2 . d−1 p p 2D log(3d)/(d − 1) = O( Db log d/d), asymptotically a factor of The dominant random term is b p d/ log d tighter than what Cauchy–Schwarz gives when applied to Theorem 1. Tightness in practice. Plugged in at typical ANN scales (d=128, b=4, δ=10−2 ), the dominant random term of Theorem 2 evaluates to ≈ 0.28 on the inner-product axis (vs. ≈ 0.46 for the p Cauchy–Schwarz random term 8 log(2/δ)/(d − 2)). Including the lower-order Rd′ correction, the full bound is ≈ 0.69 (Theorem 2) vs. ≈ 0.75 (Cauchy–Schwarz at the same confidence) — a p modest tightening at this finite scale. The asymptotic d/ log d factor becomes meaningful only at much larger d. This is not a numerically tight statement: scores live in [−1, 1] and per-pair score gaps that decide top-k ranking are typically O(0.01). The marginal-correction term Rd deserves a quantitative note. Empirically (Monte Carlo, 2 × 106 samples) the Kolmogorov distance between √ d · (Πv)j and N (0, 1) is ≈ 2.0 × 10−3 at d=96 and ≈ 1.3 × √ 10−3 at d=128—one to two orders of magnitude below the O(1/d) analytic bound, and well below D4 ≈ 0.097. So Rd is dominated by the rate-distortion √ floor at the dimensions where we actually run, contrary to the impression the unadorned O(1/ d) notation gives. The bound is therefore best read as a structural statement, not a predictive one. What it provides is two operationally useful properties: (a) the bound depends only on (b, d, δ) and contains no data-dependent term, so it does not degrade as the database grows or the data distribution drifts; and (b) it holds uniformly over the entire sphere with one fixed Π, so adding the N -th vector does not consume any union-bound budget. No PQ-family method admits an analogous uniform, data-independent bound: their reconstruction error depends on the distance from v to the nearest learned codebook centroid, which is a function of the training sample. The empirical streaming results (§4) are consistent with this structural picture but are not predicted by the bound’s numerics. Full proofs and the marginal-distribution lemma are in Appendix F.
3.3
Adaptive coarse refresh
The bound above covers only the residual quantization layer; the IVF coarse partition is still fitted by k-means and can become stale under severe distribution shift (e.g. encoder swap). We propose Adaptive IVF-TQ: periodically re-run k-means on a stratified sample of the currently indexed vectors and re-encode every vector against the new partition. Because TQ residual compression is data-independent, re-encoding requires no codebook re-training—only an O(N · d) rotate-andquantize pass with the same fixed Lloyd–Max codebook used at index initialization. This selective-refresh property is cleanly available to TQ but not to PQ-family methods. PQ and OPQ couple the partition and the compression layer through the codebook. Refreshing the partition without re-training the codebook would invalidate every stored residual code: residuals are now taken against new centroids, so previously-fitted bin assignments no longer correspond to the post-refresh signal. The only fix is a full re-encode against a re-trained codebook. With TQ, the codebook is data-independent and unchanged, so refreshing the partition costs only an O(N · d) rotate-and-quantize pass over new residuals. Adaptive IVF-TQ refreshes only what depends on the data (k-means centroids), which we show is sufficient to recover from severe distribution shift at refresh cost comparable to a single PQ codebook re-training (50s vs. 39s in Table 9), while attaining higher final recall when re-ranking is enabled. 7
Algorithm. On every refresh trigger (e.g. every Nrefresh ingested vectors): (i) sample S vectors stratified across partitions to avoid bias toward dense cells; (ii) run k-means on S to obtain new centroids; (iii) re-assign every indexed vector to its new nearest centroid using its existing TQreconstructed approximation (or its raw vector if stored for re-rank); (iv) re-rotate and re-quantize the new residuals using the unchanged Lloyd–Max codebook; (v) discard old centroids. The compression layer parameters (Π, Cb ) never change. Refresh self-containedness. Step (iii) does not require raw-vector storage. The TQ-reconstructed approximation x̂ = cold + Π⊤ r̂ has error bounded by Theorem 1; we hypothesize that re-clustering on x̂ converges to centroids close to those obtained from raw vectors. An empirical centroid-MSE diagnostic for raw-refresh vs. reconstruction-refresh is on the v2 follow-up list (§7); the experiments in this paper use raw-vector re-clustering when re-rank mode is on and falls back to reconstructionrefresh otherwise. Relation to Ada-IVF. Mohoney et al. (2024) introduce “Ada-IVF,” an incremental partitionmaintenance scheme for IVF indexes that triggers localized re-clustering on cells with stale centroids, size imbalance, or high access frequency. Adaptive IVF-TQ shares the local-re-clustering intuition but differs in scope: Ada-IVF targets the IVF coarse partition for systems that retain a learned quantizer (e.g., IVF-PQ), so the quantizer layer remains a separate concern in their setup; Adaptive IVF-TQ refreshes the partition with no codebook to update—the residual layer is data-independent by construction—so the partition refresh is the only refresh needed. The two approaches are complementary: Ada-IVF’s adaptive triggering policy could be applied to an IVF-TQ index to give a refresh-when-needed scheme.
4
Streaming Experiments
We first establish the empirical evidence that motivates IVF-TQ’s design (§4.1), then quantify the gap to IVF-TQ at SIFT-1M and Deep/SIFT-10M scale (§4.2), under embedding-model swap (§4.3), and the cumulative re-training cost of staying competitive (§4.4). §4.5 stress-tests the IVF coarsepartition layer under worst-case shift. Appendix H validates Recall@10 against a downstream NDCG metric.
4.1
Mechanism: distribution shift is not sufficient
A learned PQ codebook is fitted to a sample of N0 vectors and held fixed as the database grows to N ≫ N0 . We test whether distribution shift is required to explain streaming recall degradation by comparing three ingestion conditions on SIFT-1M (Table 2). The shuffled-i.i.d. control rules out distribution shift as a confound: data are drawn i.i.d. from the same underlying distribution as the training sample, yet IVF-PQ recall still drops by −3.94 ± 0.17pp (paired-t p<0.001 across 3 seeds; Table 2). The distribution-shift hypothesis would predict the shuffled control should substantially close the gap; it does not. Re-training the PQ codebook on cumulative data and re-encoding all stored vectors does not recover the gap at any tested memory regime: at sub-matched PQ (m=48/64, ∼0.75× IVF-TQ memory) the stale-vs-retrain paired difference is ∆=−0.06 ± 0.44pp (p=0.60) on Deep-10M and ∆=−0.17 ± 0.50pp (p=0.29) on SIFT-10M; at super-matched PQ the gap likewise stays below noise (p=0.52 Deep, p=0.32 SIFT). Together these are negative results—distribution shift is not sufficient to explain the gap; codebook re-training is not sufficient to close it—rather than a positive identification of the mechanism.
8
Table 2: SIFT-1M streaming under three ingestion conditions (200K trained, 8 batches of 100K, L=500, np =10, 10K queries), 3 seeds (42, 123, 7777). Recall@10 as mean ± 95% CI (t-distribution, df=2); ∆ as paired-t within-seed mean ± CI. All ∆ have p < 0.001 except mean-shift TQ (p = 0.002) and mean-shift PQ (p < 0.001). Under shuffled-i.i.d. ingestion (no distribution shift), IVF-PQ still degrades −3.94 ± 0.17pp—ruling out distribution shift as a sufficient explanation. Memory: IVFTQ 672 bits/vec, IVF-PQ 512 bits/vec (0.76× IVF-TQ). Protocol differs from 10M tables: L=500, np =10 here vs. L=1000, np =20 at 10M scale. Condition
IVF-TQ (200K→1M)
IVF-PQ (200K→1M)
TQ ∆
PQ ∆
Original order Shuffled (i.i.d.) Mean-shift (0.05/batch)
89.55±0.19 → 92.05±0.14 89.55±0.19 → 92.05±0.15 89.55±0.19 → 91.37±0.17
73.23±0.46 → 69.29±0.40 73.23±0.46 → 69.29±0.40 73.23±0.46 → 70.66±0.36
+2.51±0.09 +2.50±0.09 +1.82±0.36
−3.94±0.17 −3.94±0.17 −2.57±0.32
Capacity vs. bias control. A natural follow-up question is whether the streaming −3.8pp drop is a codebook-bias artefact (the initial 200K is unrepresentative) rather than a codebook-capacity artefact (a 200K-trained codebook is too small for a 1M database, regardless of which 200K). We disambiguate by training three IVF-PQ variants and evaluating all three against the same 1M database (Table 3): (A) codebook+partition fitted on the first 200K of the stream—the “stale” condition; (B) codebook+partition fitted on a uniformly random 200K sample of the full 1M (same training size as A, no initial-sample bias); (C) codebook+partition fitted on the full 1M (oracle, no bias and no capacity gap). Table 3: Capacity-vs-bias control on SIFT-1M. All variants are IVF-PQ (m=64, 4-bit, 256 bits/vec, L=1000, np =20) evaluated on the full 1M database with 1,000 queries. Protocol-difference note. This control runs at L=1000, np =20 and 1K queries; the streaming experiment of Table 2 uses L=500, np =10 and 10K queries. The two operating points are not directly comparable in absolute recall. Variant
Training sample
Bits/vec
R@10 on 1M
Notes
A. PQ-200K-initial B. PQ-200K-random C. PQ-1M
first 200K of stream random 200K of 1M full 1M (oracle)
256 256 256
71.56% 71.31% 71.16%
streaming “stale” same size, no bias no bias, no capacity gap −0.25pp −0.15pp
Bias contribution (B−A) Capacity contribution (C−B)
Interpretation. Both gaps (B−A and C−B) are within statistical noise (SE ≈ 1.4pp on 1,000 queries at ∼ 71% recall): the spread A→B→C is 0.40pp, well below 2 SE. The defensible reading is the weaker one: at this bit budget, the choice of which 200K is used to train the codebook does not detectably matter; we cannot, from this control alone, attribute the streaming degradation to either bias or capacity in isolation. What this control does establish, jointly with Table 2 and the Deep10M / SIFT-10M retrain experiments (§4.2, where re-training and re-encoding every batch costs hundreds of seconds and recovers ≤ 0.25pp), is the negative result that retraining the codebook is not the lever that closes the streaming gap. The IVF-TQ advantage in this picture is operational: it removes the codebook from the residual layer entirely, which is sufficient to keep recall stable even though the precise mechanism on the PQ side remains under-determined by these controls. In contrast, IVF-TQ’s compression layer is parameterised by (b, d) alone (Theorem 1); its per9
vector reconstruction error has the same high-probability bound for the first vector and the N -th, regardless of which distribution they came from. Recall improves under streaming ingestion because partition coverage, the only data-dependent layer, grows. Memory regimes tested. We test PQ at three memory budgets: sub-matched (∼0.75× IVF-TQ memory; m=48 on Deep-10M, m=64 on SIFT-10M, 8-bit subspaces) and super-matched (∼1.5× IVF-TQ memory; m=96 Deep, m=128 SIFT, 8-bit); the SIFT-1M control runs the sub-matched m=64, 8-bit setting only. A truly bit-matched 8-bit PQ on dim 96 or dim 128 is not a standard FAISS-optimized configuration and is deferred to v2 (§7). The sub-matched comparison shows IVF-TQ’s stability advantage on absolute recall; the super-matched comparison shows the ratedistortion trade-off favors PQ at higher memory. The retraining-doesn’t-help finding (paired-t p>0.28 in every cell) holds at every memory regime tested, making the operational claim invariant to the memory operating point.
4.2
Streaming ingestion at scale
Protocol. Train all indexes on the first N0 vectors, then add the remainder in batches. Recompute Recall@10 on a fixed query set with ground truth recomputed against the cumulative database. Test three conditions for IVF-PQ: stale codebook, periodic re-training, and codebook retraining every batch (as an upper bound). The retrain variant re-trains a fresh PQ codebook on the cumulative data and re-encodes every previously-added vector against the new codebook ; this is the strongest retrain protocol (no stale codes survive) and is what justifies the cumulative compute numbers reported below. IVF-TQ search uses no re-ranking in the streaming experiments (raw vectors freed after add to control memory at 10M scale), so the IVF-TQ recall numbers are apples-to-apples with the no-rerank IVF-PQ baselines. Coarse-partition parameters (nlist , np ) are held constant across all batches. Figure 2 shows the SIFT-1M result: a +2.51 ± 0.09pp improvement for IVF-TQ vs. a −3.94 ± 0.17pp degradation for IVF-PQ (3 seeds, both p<0.001), with periodic re-training closing only +0.2pp of the gap at 15.4s of cumulative training cost. The gap widens monotonically: 16.3pp at 200K, 22.8pp at 1M. Scaling to 10M. We extend to two 10M datasets: Deep-10M (96-dim, ResNet image features) and SIFT-10M (128-dim, the first 10M of SIFT-1B). For both, we train on the first 1M vectors and stream in 9 batches of 1M each (full per-batch trajectories in Appendix B). Table 4: Streaming on Deep-10M, 3 seeds (42, 123, 7777). Mean ± 95% CI; paired-t on within-seed differences. Memory: IVF-TQ 512 bits/vec, IVF-PQ 384 bits/vec (0.75× IVF-TQ). Dataset
Index
Deep-10M Deep-10M Deep-10M
IVF-TQ IVF-PQ stale IVF-PQ retrain
Bits/vec
R@10 (1M)
R@10 (10M)
Change ∆
512 384 384
87.39±0.33 82.11±0.15 82.11±0.15
86.59±0.17 78.87±0.36 78.94±0.09
−0.80±0.25 pp, p=0.005 −3.23±0.49 pp, p=0.001 −3.17±0.15 pp, p<0.001
IVF-TQ vs. IVF-PQ stale at 10M: +7.72 ± 0.26 pp, p<0.001 IVF-PQ stale vs. retrain at 10M: −0.06 ± 0.44 pp, p=0.595
On Deep-10M (Table 4), IVF-TQ holds at 87.4% → 86.6% (∆=−0.80 ± 0.25pp, p=0.005) while IVF-PQ degrades from 82.1% → 78.9% (∆=−3.23 ± 0.49pp, p=0.001); the IVF-TQ vs. IVF-PQ gap widens from +5.28pp at 1M to +7.72 ± 0.26pp at 10M (paired p<0.001 at 10M). On SIFT-10M 10
Streaming Ingestion: Recall Over Time (SIFT-1M, 10K queries)
95
Recall@10 (%)
90 85
+22.5pp gap
IVF-TQ (no retrain) IVF-PQ (stale codebook) IVF-PQ (retrain every 200K)
80 75 70 Training data
200
300
400
500
600
700
800
Vectors indexed (thousands)
900
1000
Figure 2: Streaming ingestion on SIFT-1M (200K trained, then 8 batches of 100K). IVF-TQ recall improves as partition coverage grows; IVF-PQ recall degrades as the codebook becomes increasingly mismatched to the cumulative data. The retrain curve shown here is periodic re-training every 200K (15.4s total), recovering +0.2pp—a milder schedule than the per-batch re-train + re-encode protocol used in the 10M-scale tables (Tables 4, 5). The two schedules differ in how aggressively PQ is refreshed; both leave a recall gap to IVF-TQ. (Table 5), the pattern is sharper: IVF-TQ improves by +0.56 ± 0.10pp while IVF-PQ degrades by −5.80 ± 0.55pp, widening the gap from +11.49pp at 1M to +17.86 ± 0.47pp at 10M (p<0.001). On both datasets, periodic codebook re-training every batch (the most aggressive practical schedule) costs hundreds of seconds and is statistically indistinguishable from no retraining (stale vs. retrain p=0.60 Deep-10M, p=0.29 SIFT-10M). Higher PQ bit budget (super-matched memory). At sub-matched memory (Tables 4, 5) PQ has ∼0.75× IVF-TQ’s bit budget. We also test PQ at super-matched memory (∼1.5× IVF-TQ): m=96 on Deep-10M and m=128 on SIFT-10M, both at 8 bits/subspace. At this higher budget absolute recall favors IVF-PQ as expected from rate-distortion, but the streaming-stability and retrain-doesn’t-help findings are unchanged (Tables 6, 7). On Deep-10M, IVF-PQ stale at m=96 gains +1.42±0.33pp going from 1M to 10M (p=0.003); IVF-PQ exceeds IVF-TQ by +6.13±0.34pp at 10M (p<0.001). On SIFT-10M at m=128, PQ stale gains +1.09 ± 0.40pp and IVF-PQ exceeds IVF-TQ by +2.03 ± 0.10pp at 10M (p<0.001). Crucially, retraining at this higher budget still does not help: stale vs. retrain p=0.52 Deep-10M, p=0.32 SIFT-10M. At higher PQ capacity the codebook is no longer the binding constraint; partition coverage growth dominates, so stalecodebook PQ gains recall under streaming rather than losing it. This is consistent with the capacityvs-bias decomposition in §4.1: when the codebook has enough capacity for the corpus, neither bias nor staleness is the dominant ceiling, and IVF-TQ’s structural advantage from no-codebook-toretrain reduces to an operational benefit at parity (or slight deficit) on raw recall.
11
Table 5: Streaming on SIFT-10M, 3 seeds (42, 123, 7777). Mean ± 95% CI; paired-t on within-seed differences. Memory: IVF-TQ 672 bits/vec, IVF-PQ 512 bits/vec (0.76× IVF-TQ). Dataset
Index
SIFT-10M SIFT-10M SIFT-10M
IVF-TQ IVF-PQ stale IVF-PQ retrain
Bits/vec
R@10 (1M)
R@10 (10M)
Change ∆
672 512 512
83.91±0.08 72.42±0.41 72.42±0.41
84.47±0.28 66.61±0.70 66.78±0.25
+0.56±0.10 pp, p=0.007 −5.80±0.55 pp, p<0.001 −5.64±0.66 pp, p<0.001
IVF-TQ vs. IVF-PQ stale at 10M: +17.86 ± 0.47 pp, p<0.001 IVF-PQ stale vs. retrain at 10M: −0.17 ± 0.50 pp, p=0.289
Table 6: Higher PQ bit budget on Deep-10M (super-matched memory): IVF-PQ at m=96, 8 bits/subspace. 3 seeds; mean ± 95% CI. Memory: IVF-TQ 512 bits/vec, IVF-PQ 768 bits/vec (1.50× IVF-TQ). Dataset
Index
Deep-10M Deep-10M Deep-10M
IVF-TQ IVF-PQ stale IVF-PQ retrain
Bits/vec
R@10 (1M)
R@10 (10M)
Change ∆
512 768 768
87.39±0.33 91.30±0.28 91.30±0.28
86.59±0.17 92.72±0.51 92.80±0.17
−0.80±0.25 pp, p=0.005 +1.42±0.33 pp, p=0.003 +1.50±0.33 pp, p=0.003
IVF-PQ stale exceeds IVF-TQ at 10M by +6.13 ± 0.34 pp, p<0.001 IVF-PQ stale vs. retrain at 10M: −0.08 ± 0.42 pp, p=0.516
4.3
Distribution shift via embedding-model swap
The realistic distribution-shift regime is that the embedding model itself changes when production teams upgrade their encoder. We train all indexes on 200,000 MS MARCO (Nguyen et al., 2016) passages encoded by all-MiniLM-L6-v2 (Reimers and Gurevych, 2019), then stream in 800,000 passages encoded by a different model; queries come from the new encoder. Shift severity is reported as the cosine similarity between the same passage encoded by the two models. Gentle (cos = 0.51): IVF-TQ ends at 87.6% Recall@10 versus 75.7% for IVF-PQ retraining the codebook every batch (+11.9pp, 465s of cumulative retrain compute). Harsh (cos = 0.24): stale IVF-PQ collapses to 51.6%; PQ retraining recovers +21pp, but the actively-retrained PQ index (72.4%) still trails IVF-TQ frozen (76.8%) by 4.4pp at the +300K state. The data-independent compression absorbs new-encoder vectors at full quality regardless of shift severity, and partition coverage from prior-encoder vectors is enough to keep coarse assignments useful—no refresh needed.
4.4
Cost of staying fresh
Figure 3 plots cumulative re-training cost vs. recall over the streaming run. For IVF-PQ there is no Pareto-good operating point: low re-training frequency leaves recall low; high frequency consumes significant compute and still does not match IVF-TQ. IVF-TQ sits at zero re-training cost on the recall axis dominated by the leftmost point of the IVF-PQ curve.
4.5
Stress test: Adaptive IVF-TQ under adversarial shift
§4.3 showed that under realistic distribution shift (encoder upgrade), IVF-TQ frozen absorbs newencoder vectors at full quality and exceeds even the freshly-retrained PQ baseline (76.8% vs. 72.4% on the harshest swap). To probe the operational limits of the coarse-partition layer and motivate the Adaptive variant, we apply a strictly adversarial shift: the streaming portion is rotated by a 12
Table 7: Higher PQ bit budget on SIFT-10M (super-matched memory): IVF-PQ at m=128, 8 bits/subspace. 3 seeds; mean ± 95% CI. Memory: IVF-TQ 672 bits/vec, IVF-PQ 1024 bits/vec (1.52× IVF-TQ). Dataset
Index
SIFT-10M SIFT-10M SIFT-10M
IVF-TQ IVF-PQ stale IVF-PQ retrain
Bits/vec
R@10 (1M)
R@10 (10M)
Change ∆
672 1024 1024
83.91±0.08 85.42±0.16 85.42±0.16
84.47±0.28 86.50±0.31 86.60±0.34
+0.56±0.10 pp, p=0.007 +1.09±0.40 pp, p=0.001 +1.18±0.34 pp, p=0.004
IVF-PQ stale exceeds IVF-TQ at 10M by +2.03 ± 0.10 pp, p<0.001 IVF-PQ stale vs. retrain at 10M: −0.09 ± 0.31 pp, p=0.317
Table 8: Embedding-model swap on 1M MS MARCO passages (Recall@10). The gentle (L6→L12) row reports the final state of the full +800K streaming run; the harsh (L6→BGE) row reports the +300K state, our compute-budgeted measurement point. The harsh-swap result should be read as suggestive (the trajectory through +100K, +200K, +300K is monotone and the gap to PQ retrain is stable), not as a definitive end-state comparison; the +800K extension is in our follow-up plan. Swap
cos
IVF-TQ frozen
IVF-PQ stale
IVF-PQ retrain
Retrain cum.
L6 → L12 (gentle) L6 → BGE (harsh) *
0.51 0.24
87.6% 76.8%
72.5% 51.6%
75.7% 72.4%
465s 250s
random orthogonal matrix that decorrelates space-A and space-B vectors (cosine similarity drops to ∼ 0). This is harsher than any realistic encoder swap and is designed specifically to force the coarse partition to misalign. Two findings, reported in the order a sceptical reader will want them. (1) Applesto-apples (no re-rank). At rerank=0, PQ retrain at m=96 (∼8 bits/dim per subspace) reaches 95.8% R@10 and Adaptive IVF-TQ at 4-bit (∼5 effective bits/dim) reaches 90.3%—a 5.5pp deficit attributable to the bit-budget gap, not the algorithm. PQ retrain wins this comparison. (2) Reranking enabled. With re-ranking on top-50 candidates against raw vectors, Adaptive IVF-TQ reaches 97.8% versus PQ retrain’s 95.8% (PQ retrain has no re-rank step here because the FAISS PQ baseline does not store raw vectors), at comparable refresh compute (50s vs. 39s). The Adaptive contribution stands in the rerank-enabled regime, which is the practical deployment for systems that already store raw vectors for re-ranking. The corresponding memory cost is non-trivial: storing raw float32 vectors for re-ranking adds the same ∼ 5× memory overhead on Deep-1M that we discuss for IVF-TQ in §5. Refresh frequency Pareto. A schedule ablation (refresh every 25K, 50K, 100K, 250K vectors) shows refreshing every 250K achieves the same final recall as refreshing every 25K at one-third the cumulative compute. The refresh operation is highly forgiving on schedule. Downstream metric. A BeIR/MS MARCO NDCG@10 spot-check (single dataset, single seed) shows IVF-TQ within sampling noise of fresh-codebook IVF-PQ and +1.16pp above stale IVF-PQ at matched memory; see Appendix H for the numbers.
13
95
Recall vs Re-training Cost (SIFT-1M streaming, 200K
1M)
92.1% @ 0s
Recall@10 (\%)
90 85 80
IVF-TQ (no re-training) IVF-PQ (stale codebook) IVF-PQ (re-train every 200K vectors)
75 70
69.4% @ 0s
65 60
0.0
2.5
69.6% @ 16.2s
Region dominated by IVF-TQ (higher recall at zero cost)
5.0
7.5
10.0
12.5
15.0
Cumulative re-training cost (seconds)
17.5
20.0
Figure 3: Recall@10 vs. cumulative codebook re-training cost (SIFT-1M streaming). IVF-TQ requires zero re-training (single point at the origin); IVF-PQ re-training has no Pareto-good operating point.
5
Million-Scale Comparison
Table 10 compares IVF-TQ against FAISS baselines (PQ, IVF-PQ at m ∈ {64, 128}, OPQ+IVFPQ at m ∈ {64, 128}, HNSW (Malkov and Yashunin, 2020) at M ∈ {16, 32}) and Google’s ScaNN (Guo et al., 2020). All numbers are 10K queries, deterministic seed=42, FAISS 1.13.2. Bit accounting and memory. “IVF-TQ b-bit” denotes b bits/coordinate of Lloyd–Max plus the 1-bit sign refinement (Stage 2), giving b+1 effective bits/coordinate. The Memory column reports the total compressed footprint, which includes the IVF coarse-partition centroids (L · d · 4 bytes; ∼0.5 MB for L=1000, d=128). † ScaNN’s listed memory is the compressed AH+tree footprint matching the IVF-TQ accounting basis; ScaNN additionally stores raw vectors for reorder (550 MB total on SIFT-1M, 412 MB on Deep-1M). HNSW stores raw vectors so its memory column reflects that. Discussion. On the static-recall axis, ScaNN is the strongest learned baseline: at Ls =50 it reaches 96.2% Recall@10 on SIFT-1M and 96.9% on Deep-1M at 62/47 MB compressed—roughly 50% lower memory than IVF-TQ at comparable recall (96.1% / 96.4% at 111/84 MB). At matched memory, IVF-TQ 6-bit is within ∼1pp of OPQ+IVF-PQ but is dominated by ScaNN by ∼1pp. Two distinct competitor classes. HNSW is also codebook-free—it is a graph index with no learned compression—and at high recall (≥ 99%) it dominates IVF-TQ at 7.5× the memory footprint. The codebook-training-free property therefore does not differentiate IVF-TQ from HNSW; it differentiates IVF-TQ from learned-codebook compression methods (PQ, OPQ, ScaNN). The two
14
Table 9: Recovery from worst-case rotation shift on Deep-1M. Bit-budget asymmetry: IVF-PQ retrain runs at m=96, 8 bits per subspace (∼8 effective bits/dim), and is configured with its own raw-vector store for re-rank-free search; Adaptive IVF-TQ runs at 4-bit + sign-bit (∼5 effective bits/dim) and uses re-ranking only in the rerank=50 column. The IVF-PQ “initial” recall (68%) is slightly above IVF-TQ’s (67%) because of this higher bit budget. We report rerank=0 (applesto-apples) and rerank=50 (Adaptive’s intended deployment regime) side by side. Refresh-cost comparison: Adaptive IVF-TQ takes 50s vs. PQ retrain’s 39s—Adaptive’s refresh is dominated by re-clustering on the cumulative database whereas PQ-retrain’s cost is dominated by codebook re-training on a sample, not full re-encoding (FAISS’s default retrain does not re-encode existing stored codes by default in this baseline). At apples-to-apples re-encode-everything retrain protocol (§4.2), PQ retrain takes hundreds of seconds; we omit that here because the relevant comparison for Adaptive is per-shift refresh cost. With re-rank enabled, Adaptive IVF-TQ exceeds PQ retrain by 2pp at the rerank-50 operating point. Method
Initial
Final R@10 (rr=50)
Final R@10 (rr=0)
Refresh cost
IVF-TQ frozen Adaptive IVF-TQ IVF-PQ stale IVF-PQ retrain
67% 67% 68% 68%
75% 97.8% 64% 95.8%
67% 90.3% 64% 95.8%
— 50s — 39s
classes compete on different axes: against learned-codebook methods, IVF-TQ trades ∼1pp of static recall at fixed memory for codebook-staleness immunity (§4); against HNSW, IVF-TQ trades 1–2pp of high-recall ceiling for 5–7× less memory. Among learned-codebook methods specifically, ScaNN dominates static recall by ∼1pp at fixed memory. ScaNN’s anisotropic AH codebook is fitted to the initial training sample like PQ’s; we have not run ScaNN under our streaming protocol (the Linux/Colab path used for the static comparison is non-trivial to instrument for the multi-batch streaming experiments), but we conjecture that ScaNN inherits the same initial-sample bias as PQ and that the static-recall gap closes or reverses under streaming. Empirically validating this conjecture on ScaNN is left to future work. Bits vs. re-ranking. A common alternative to higher quantization precision is to keep the index at low precision (4-bit) and re-rank top candidates against raw vectors. On SIFT-1M, IVFTQ 4-bit + re-rank top-50 reaches 95.3% Recall@10—essentially matching IVF-TQ 6-bit’s 95.3% without re-ranking. The two configurations are equivalent on recall but differ sharply on memory: re-ranking requires storing raw float32 vectors alongside the compressed index (∼488 MB raw + 81 MB compressed = 569 MB total), whereas the 6-bit configuration needs only the compressed footprint (111 MB). Choosing higher quantization precision over re-ranking saves ∼5× memory at matched recall.
6
Related Work
Learned vector compression. PQ (Jégou et al., 2011), OPQ (Ge et al., 2014), Additive Quantization (Babenko and Lempitsky, 2014), and ScaNN (Guo et al., 2020) all learn data-dependent codebooks. Our experiments include FAISS PQ, OPQ, and ScaNN as baselines. Codebook-free vector compression. TurboQuant (Zandieh et al., 2025a) introduced random rotation + Lloyd–Max for KV caches; its ANN experiments are flat-rotation only and do not test 15
IVF wrapping. PolarQuant (Han et al., 2025) uses polar coordinates. RaBitQ (Gao and Long, 2024) uses random rotation + binary quantization with theoretical bounds. Extended RaBitQ (Gao et al., 2025), the most recent and direct comparator, generalizes RaBitQ to B bits/dim by quantizing each rotated coordinate against a codebook designed to match the rotated-unit-vector marginal density and ships an unbiased linear inner-product estimator with a tight theoretical error bound. The marginal of (Πv)j for v ∈ S d−1 under Haar rotation is the Beta (d−1)/2, (d−1)/2 -derived density (Appendix Lemma 1); for d ≥ 64 this density is within O(1/d) Kolmogorov distance of N (0, 1/d), so Extended RaBitQ’s per-coordinate B-bit quantizer is equivalent to TQ Stage 1 at the same b up to the finite-dimension correction term Rd in our Theorem 1. We treat Extended RaBitQ as the strongest direct baseline for our Stage 1 design and report it explicitly in Tables 11 and 10. IVF-wrapped codebook-free quantizers: deployed systems and concurrent work. Wrapping a codebook-free residual quantizer in IVF is an active production direction that we explicitly position our work alongside, not against. Milvus ships IVF RABITQ; NVIDIA’s cuVS library ships an IVF-RaBitQ implementation; LanceDB and Weaviate (the latter as “8-bit rotational quantization”) deploy related constructions. Concurrently, Shi et al. (2026) present a GPU-native IVF-RaBitQ system in cuVS. These systems and their underlying RaBitQ Library at NTU (Gao and Long, 2024; Gao et al., 2025) pair IVF with a codebook-free binary or grid residual quantizer; they focus on raw throughput and recall on static benchmarks, not on the streaming-ingestion operational case. The architecture of IVF + codebook-free residual is therefore established; what is new in our work is (a) the residual primitive is Lloyd–Max scalar quantization rather than RaBitQ binary/grid (giving the bin-ordinality property of Appendix E); (b) the streaming-operational story (§4), including the shuffled-i.i.d. control, the capacity-vs-bias decomposition, and the 10M-scale per-batch retraincost analysis; and (c) the uniform-over-sphere IP-error bound (Theorem 2). We do not claim the architectural arrangement as our contribution. The half-bin conditional-mean refinement (sign-bit, Appendix A) is novel relative to Extended RaBitQ in the flat-TQ regime: Extended RaBitQ does not propose any sub-bin refinement on top of its B-bit primary quantizer, and the +11.4pp average gap in Table 11 is the empirical gain attributable to that correction at flat scale. In the IVF-TQ regime, the gain disappears (mean ∆ = +0.08pp, p=0.50; Table 12) because IVF amplification absorbs the residual variance. SAQ (Li et al., 2025) adds dimension segmentation but no sub-bin refinement either. None of these prior works analyses the IVF amplification effect, which is the main system-level difference between IVF-TQ and a flat application of Extended RaBitQ. Streaming and dynamic ANN. SPFresh (Xu et al., 2023) and FreshDiskANN (Singh et al., 2021) address streaming updates at the index-structure level: they maintain graph indexes under inserts, deletes, and merges without rebuilding from scratch. They do not change the underlying quantizer. Our work is orthogonal: we keep the index structure simple (IVF) and instead change the quantizer to remove its data-dependent codebook. The two lines of work compose: a dynamic graph index using a TQ-style residual quantizer would have neither the structure-maintenance cost of graph rebuilds nor the codebook-staleness cost of learned-codebook compression. ScaNN’s anisotropic learned quantization, by contrast, inherits the same codebook-staleness limitation as PQ under streaming updates—its anisotropic codebook is fitted to the initial training sample exactly like PQ’s—so it is a learned-codebook baseline rather than a streaming-ANN baseline. Concurrent work. Aden-Ali et al. (2025) formally study quantization under streaming updates and prove that static data-dependent quantization can be made dynamically consistent with
16
bounded disk I/O per update. They make the data-dependent quantizer dynamic; we sidestep the problem by using a data-independent quantizer that never needs updating. The two approaches are complementary: their algorithm targets settings where data-dependent compression is required (e.g. very high compression ratios where codebook structure is essential); ours targets the moderatecompression regime (5–6 bits/dim) where data-independence is feasible without recall loss. Production vector-database systems (FAISS (Johnson et al., 2021), DiskANN (Subramanya et al., 2019), SPFresh (Xu et al., 2023), FreshDiskANN (Singh et al., 2021)) currently treat the codebook as static and re-train periodically; our results suggest that for many workloads, a codebook-free residual layer combined with the existing IVF or graph machinery is a strictly simpler operational choice.
7
Limitations
Implementation latency: this paper is a research-prototype kernel. On SIFT-1M, FAISS IVF-PQ achieves ∼53K QPS at np =10 vs. our IVF-TQ implementation’s 22K QPS—a ∼2.4× gap. FAISS uses optimized C++ with SIMD-accelerated ADC kernels (FastScan-style (André et al., 2017) int8 LUTs with vqtbl2q/vpshufb 16-way parallel lookups); our reference is Python/NumPy with a NEON-accelerated C++ inner loop using scalar table lookups. We are explicit that this is a deliberate scope choice—the paper’s contribution is the residual quantizer’s data-independence and the system-level consequences for streaming, not a production-parity ANN system. A FastScanstyle int8-LUT kernel is the right path to closing the gap; we leave it to follow-up work. Memory for re-ranking. If raw vectors are kept for re-ranking, total memory rises from 81 MB to 569 MB on SIFT-1M; OPQ+IVF-PQ also uses re-ranking and lands in a similar regime. A higher-precision TQ pass (8-bit) would avoid raw storage at modest extra memory. Scale and dataset coverage. Our 10M-scale streaming validation covers two datasets: Deep10M and SIFT-10M. The pattern is consistent on both and is sharper on SIFT-10M. The 1M-scale streaming experiments cover SIFT-1M, Deep-1M, and (for the encoder-swap regime) MS MARCO. The architecture should scale to 100M+, but we have not validated this. ScaNN comparison. ScaNN’s pip package is Linux-only. On Linux/Colab we run ScaNN at million-scale (Appendix D); we treat it as a strong learned-quantization baseline whose codebookstaleness limitation under streaming updates is the same as PQ/OPQ. IVF still requires k-means. IVF-TQ removes the compression codebook but retains k-means for the coarse partition. Adaptive IVF-TQ (§3.3) refreshes the partition cheaply when needed, but the layer is not literally training-free. Explored alternatives that did not work. We tested two extensions and document their failure modes in Appendix G: (i) random-hyperplane LSH partitioning for a fully data-independent index, dominated by k-means at matched bit budget; (ii) per-vector variable bit allocation tracking observed query frequency, which works under oracle hot-set knowledge but fails with realistic discovery.
17
Experimental gaps identified for follow-up. We are explicit about what is missing from the present preprint and would strengthen the paper for peer review: • Bit-matched PQ configuration. We test IVF-PQ at sub-matched (∼0.75× IVF-TQ memory; m=48 Deep, m=64 SIFT, 8-bit) and super-matched (∼1.5× IVF-TQ memory; m=96 Deep, m=128 SIFT, 8-bit) bit budgets. A truly bit-matched configuration (e.g., PQ m=48 b=10 on dim 96, or m=64 b=10 on dim 128) is not a standard FAISS-optimized configuration and is deferred to v2; we conjecture (but do not show) that bit-matched PQ would land between the sub-matched and super-matched results, with the operational claim (no codebook to retrain; paired-t p > 0.28 for retrain vs. stale at every tested memory regime) unaffected. • Official Extended RaBitQ. Our IVF-TQ vs. Extended RaBitQ tie (Table 12) is against our Python reimplementation. We have an open issue to run the official RaBitQ-NTU implementation on Linux and replace this column. • Graph baselines: DiskANN, SPANN, NSG, HNSW+PQ hybrid. Subramanya et al. (2019), Chen et al. (2021), Fu et al. (2019), and the standard HNSW+PQ hybrid are not yet in the million-scale comparison table. ann-benchmarks-style (Aumüller et al., 2020) memoryvs-recall Pareto plotting against this fuller baseline set is planned. • 100M+ scale. The architecture should scale to 100M and beyond; the empirical claims in this paper stop at 10M. • ScaNN under streaming. ScaNN’s anisotropic codebook is fitted to the initial sample; we conjecture it inherits PQ’s streaming degradation but have not run it under our streaming protocol. • Tail-latency (p99) measurements. Streaming workloads typically have p99 SLAs that we have not characterised. • Broader downstream-metric validation. The NDCG spot-check (Appendix H) is one dataset / one encoder. A full BeIR sweep with bootstrap CIs would convert this from a spot-check to a validation. • Filtered ANN (e.g., Gollapudi et al., 2023). Filtered queries are an important production setting not addressed by IVF-TQ directly; whether the codebook-free residual layer composes with filter-aware index structures is open. Several of these items are blockers for a top-venue submission; we list them up-front rather than embedding them in scattered caveats throughout the paper.
8
Conclusion
For ANN under streaming ingestion, the binding constraint is not raw recall on static data—where HNSW and ScaNN each dominate one axis—but the operational cost of keeping recall high as data evolves. Making the residual compression layer codebook-free removes one major failure mode at the cost of ∼1pp of static recall at matched memory against the strongest learned-codebook baselines. The contributions are: a multi-seed streaming-operational analysis showing that (a) IVFTQ remains stable under streaming across memory regimes (Tables 2, 4, 5), and (b) per-batch PQ retraining does not recover the streaming gap at any tested bit budget (paired-t p > 0.28 in every cell; Tables 4–7)—the durable cross-regime finding; the IVF-amplification observation (qualitatively 18
consistent with the +17.7pp recall jump from flat to IVF-wrapped data-independent quantization on SIFT-1M, closing the gap to Extended RaBitQ to within statistical noise); a uniform-over-sphere inner-product error bound (Theorem 2; proof sketch in v1, rigorous in v2); and Adaptive IVF-TQ, a selective coarse-partition refresh enabled by the codebook-free residual (with the apples-to-apples bit-budget caveat of §4.5). We also document, but do not headline, a flat-TQ sign-bit refinement that improves on QJL but ties Extended RaBitQ once IVF amplification is applied, and a Lloyd– Max bin-ordinality property whose recall-preserving cascade does not yet yield a wall-clock speedup in our C++ kernel. Reproducibility. All experiments are deterministic. Single-seed experiments use seed=42; streaming experiments (Tables 2, 4, 5, 6, 7) use seeds 42, 123, 7777 with paired-t CIs. Source code, datasets, and reproduction scripts: https://github.com/tarun-ks/turboquant_search.
References Ishaq Aden-Ali, Hakan Ferhatosmanoglu, Alexander Greaves-Tunnell, Nina Mishra, and Tal Wagner. Quantization for vector search under streaming updates. arXiv preprint arXiv:2512.18335, 2025. Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. Accelerated nearest neighbor search with quick ADC. In Proceedings of the 2017 ACM on International Conference on Multimedia Retrieval, pages 159–166, 2017. Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems, 87:101374, 2020. Artem Babenko and Victor Lempitsky. Additive quantization for extreme vector compression. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 931–938, 2014. Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. SPANN: Highly-efficient billion-scale approximate nearest neighbor search. In Advances in Neural Information Processing Systems, volume 34, 2021. Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading-out graph. Proceedings of the VLDB Endowment, 12(5):461–474, 2019. 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. Jianyang Gao, Yutong Gou, Yuexuan Xu, Yongyi Yang, Cheng Long, and Raymond Chi-Wing Wong. Practical and asymptotically optimal quantization of high-dimensional vectors in Euclidean space for approximate nearest neighbor search. Proceedings of the ACM on Management of Data, 3(3):1–26, 2025. Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization for approximate nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36 (4):744–755, 2014. 19
Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premkumar Srinivasan, Amit Singh, and Harsha Vardhan Simhadri. Filtered-DiskANN: Graph algorithms for approximate nearest neighbor search with filters. In Proceedings of the ACM Web Conference 2023, pages 3406–3416, 2023. 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 (ICML), pages 3887–3896, 2020. Insu Han, Praneeth Kacham, Amin Karbasi, Vahab Mirrokni, and Amir Zandieh. PolarQuant: Quantizing KV caches with polar transformation. arXiv preprint arXiv:2502.02617, 2025. 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. Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3):535–547, 2021. Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. Retrieval-augmented generation for knowledge-intensive NLP tasks. In Advances in Neural Information Processing Systems, volume 33, pages 9459–9474, 2020. Hui Li, Shiyuan Deng, Xiao Yan, Xiangyu Zhi, and James Cheng. SAQ: Pushing the limits of vector quantization through code adjustment and dimension segmentation. Proceedings of the ACM on Management of Data, 2025. arXiv:2509.12086. Stuart Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28 (2):129–137, 1982. 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. Jason Mohoney, Anil Pacaci, Shihabur Rahman Chowdhury, Umar Farooq Minhas, Jeffery Pound, Cedric Renggli, Nima Reyhani, Ihab F. Ilyas, Theodoros Rekatsinas, and Shivaram Venkataraman. Incremental IVF index maintenance for streaming vector search. arXiv preprint arXiv:2411.00970, 2024. Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. MS MARCO: A human generated machine reading comprehension dataset. In Workshop on Cognitive Computation, NeurIPS, 2016. Nils Reimers and Iryna Gurevych. Sentence-BERT: Sentence embeddings using Siamese BERTNetworks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing, 2019. Jifan Shi, Jianyang Gao, James Xia, Tamás Béla Fehér, and Cheng Long. GPU-native approximate nearest neighbor search with IVF-RaBitQ: Fast index build and search. arXiv preprint arXiv:2602.23999, 2026.
20
Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. FreshDiskANN: A fast and accurate graph-based ANN index for streaming similarity search. arXiv preprint arXiv:2105.09613, 2021. 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. Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018. Yuming Xu, Hengyu Liang, Jin Li, Shuotao Xu, Qi Chen, Qianxi Zhang, Cheng Li, Ziyue Yang, Fan Yang, Yuqing Yang, Peng Cheng, and Mao Yang. SPFresh: Incremental in-place update for billion-scale vector search. In Proceedings of the 29th Symposium on Operating Systems Principles (SOSP), pages 545–561, 2023. Amir Zandieh, Majid Daliri, Majid Hadian, and Vahab Mirrokni. TurboQuant: Online vector quantization with near-optimal distortion rate. arXiv preprint arXiv:2504.19874, 2025a. Amir Zandieh, Majid Daliri, and Insu Han. QJL: 1-bit quantized JL transform for KV cache quantization with zero overhead. Proceedings of the AAAI Conference on Artificial Intelligence, 39(24):25805–25813, 2025b.
A
Sign-bit refinement: flat-TQ and IVF-TQ tables
A.1
Flat-TQ regime: sign-bit vs. QJL at matched memory
Table 11 compares sign-bit refinement against TurboQuant’s original QJL Stage 2 at matched memory in the flat-TQ regime (no IVF wrapping). All three columns share Stage 1 (random rotation + Lloyd–Max); only the 1-bit Stage 2 differs. Sign-bit refinement wins on every cell, with an average +11.4pp improvement over QJL across six million-scale cells.
A.2
IVF-TQ regime: sign-bit vs. Extended RaBitQ at matched memory
Once IVF wrapping is applied, the flat-TQ sign-bit advantage disappears. Table 12 compares IVFTQ with sign-bit refinement against an Extended-RaBitQ-equivalent baseline (TQ Stage 1 only, at one extra bit of primary quantization). Across 9 dataset × bit-budget cells the mean difference is +0.08pp (paired t-test p=0.50, 95% CI [−0.19, +0.35]pp): statistically indistinguishable. IVF amplification absorbs the residual variance that sign-bit refinement targeted in flat TQ.
A.3
Full Recall@10 and Recall@1 ablation (10K-scale)
Tables 13 and 14 report the complete Stage 2 ablation. Sign-bit refinement wins on every benchmark, bit rate, and metric in the flat-TQ regime.
B
Streaming results at 10M scale
B.1
Deep-10M
Per-batch trajectory on Deep-10M (96-dim, ResNet image features). Indexes are trained on the first 1M vectors and grown in 9 batches of 1M each; ground truth is recomputed against the cumulative 21
database every batch. IVF-TQ holds within 1pp of its initial recall (87.54% → 86.65%) while stale IVF-PQ degrades −3.37pp and per-batch re-trained IVF-PQ degrades −3.22pp despite 309 s of cumulative re-training compute.
B.2
SIFT-10M
Same streaming protocol applied to SIFT-10M (128-dim, the first 10M of SIFT-1B). The pattern is sharper than on Deep-10M: IVF-TQ improves by +0.63pp from the 1M state to the 10M state while stale IVF-PQ degrades −5.99pp and per-batch re-trained IVF-PQ degrades −5.76pp (354 s cumulative re-training compute, +0.23pp recovery).
C
Distribution shift via embedding-model swap (full results)
Setup. We use the BeIR mirror of MS MARCO (Nguyen et al., 2016). For each swap experiment, we encode the same 1M unique MS MARCO passages with two different sentence-transformer encoders. All indexes train on the first 200K passages encoded by an old encoder; we then stream in the remaining 800K passages encoded by a new encoder, in 100K-vector batches. Queries (5K disjoint MS MARCO query texts) are always encoded by the new encoder. Recall@10 against ground truth recomputed against the cumulative mixed-encoder database. Two findings beyond the trained-state baseline. Gentle (L6→L12, cos = 0.51): IVF-TQ drops 3.6pp on first contact with new-encoder vectors then recovers as more new-encoder vectors fill cells—a stable recovery consistent with the data-independent residual quantizer (Theorem 1). IVF-PQ retrain gains 1.8pp at 465s but never reaches the IVF-TQ recall level (final gap: 11.91pp). Harsh (L6→BGE, cos = 0.24): IVF-PQ stale collapses to 51%; PQ retraining recovers 21pp by adapting the codebook to the new corpus. IVF-TQ holds within 1pp of its initial 76.4% across the entire run, ending 4.46pp above the actively-retrained PQ baseline at the +300K state.
D
ScaNN baseline (Linux-only)
Google’s ScaNN (Guo et al., 2020) ships only Linux wheels via pip install scann. We ran the wrapper on a Linux/Colab environment. We use AsymmetricHashing scoring with anisotropic quantization thr 0.2, dimensions per block = 2, reordering on the top 100 candidates, and a sweep over num leaves to search ∈ {20, 50, 100, 200, 400} at L=2000 leaves.
E
Cascade search via Lloyd–Max bin ordinality
Status: documented observation, not a contribution. This appendix records (i) the bitimportance asymmetry between TQ and PQ that makes cascade meaningful in principle, and (ii) a recall-preservation result for a two-pass cascade in our C++ reference. The cascade yields a 2× speedup in our Python reference but ∼ 1.01× in our C++ reference, because our current C++ kernel already reads scalar LUTs (a smaller LUT does not help). The path to a real C++ speedup is FastScan-style int8 LUTs with SIMD permute lookups (André et al., 2017); we leave that kernel work to follow-up.
22
E.1
Bit-importance asymmetry: TQ vs. PQ
We measure the rank-relevance of each bit position by random-flip ablation: corrupt k% of a chosen bit position across all stored codes, then re-measure Recall@10. Table 19 reports the result on SIFT-1M for IVF-RVQ-TQ (b=5+1, 6 effective bits) versus IVF-PQ (m ∈ {64, 128}).
E.2
Cascade recall preservation in C++
We measure cascade in our production C++ reference. Across 4 random-rotation seeds on each of Deep-1M and SIFT-1M, plus a np ∈ {10, 20, 40, 80, 160} sweep at seed 42 (16 conditions total), the cascade preserves Recall@10 within ±0.02pp of the baseline in every cell. Mean ∆ across 16 conditions is +0.003pp; mean speedup is 1.01×. The full per-condition table is in the public artefact under experiments/cascade robustness cpp results.json.
F
Proofs of Theorems 1 and 2
Proof status (read first). This is preprint v1.p The proofs below are presented as proof sketches: the bounds we state are believed correct (the rate Db log d/d is consistent with the known per-pair in-expectation IP bound of Zandieh et al. (2025a), with the only new ingredient being uniformity over the sphere via a covering net), but the rigorous concentration argument relies on bounding the random functional Π 7→ ∥Πv − Cb (Πv)∥2 via the bounded-error property of Lemma 2, not the (incorrect) Lipschitz-in-Π property an earlier draft assumed. We sketch the corrected route below; the fully rigorous proof (which requires either a McDiarmid-type bounded-difference argument on the rotation action or a moment-based concentration combining the in-expectation MSE with the bounded ℓ∞ error) is on the v2 follow-up list. Attribution and contribution boundary. The TQ-style quantizer analysed in this appendix— random orthogonal rotation followed by per-coordinate Lloyd–Max scalar quantization—is due to Zandieh et al. (2025a). They prove an in-expectation MSE bound (their Theorem 1) and a per-pair in-expectation IP-error bound (their Theorem 2). Theorem 3 below is a high-probability counterpart of their MSE bound; we include it for self-containedness and to fix notation for Theorem 4, but we do not claim it as a new result. Theorem 4 is the genuinely new statement: a bound on the inner-product estimation error that holds uniformly over the entire unit sphere with one fixed rotation. The uniform statement is what removes the per-vector union-bound penalty in streaming ANN.
F.1
Setup and notation
Let Rd be ambient space and S d−1 = {v ∈ Rd : ∥v∥2 = 1} the unit sphere. Let O(d) be the orthogonal group equipped with the bi-invariant Haar probability measure. We write Π ∼ Haar(O(d)) for a sample. Let Cb : R → R be the optimal b-bit Lloyd–Max scalar quantizer designed for the source distribution N (0, 1/d), applied componentwise on Rd . Define the TQ reconstruction map v̂ := Π⊤ Cb (Πv),
v ∈ S d−1 .
Let Db denote the per-coordinate mean-squared reconstruction error of Cb on N (0, 1/d): h 2 i Db := d · ET ∼N (0,1/d) Cb (T ) − T . 23
(1)
Db is the standard Gaussian rate-distortion at√b bits/dim. The Panter–Dite high-resolution formula gives the asymptotic equality Db → 2−2b · 62π3 as b → ∞; the inequality direction at finite b is √
Db ≲ 2−2b · 62π3 for the optimal Lloyd–Max quantizer (with low-order b-dependent constants we suppress).
F.2
Two lemmas
Lemma 1 (Marginal distribution of a rotated coordinate). Let Π ∼ Haar(O(d)) and fix v ∈ S d−1 , Γ(d/2) j ∈ [d]. The marginal distribution of (Πv)j has density fd (t) = √π Γ((d−1)/2) (1−t2 )(d−3)/2 on [−1, 1], √ independent of v. As d → ∞, d (Πv)j converges to N (0, 1) in Kolmogorov distance at rate O(1/d) (Vershynin, 2018). Proof. By Haar invariance, Πv ∼ Unif(S d−1 ) for any fixed v ∈ S d−1 . The marginal density of one d−1 is the Beta-derived form above; the Gaussian limit coordinate of a uniform random point on S√ follows from a direct expansion of log fd (t/ d) around t = 0. See e.g. Vershynin (2018) Theorem 3.4.6. Lemma 2 (Bounded per-coordinate error of Lloyd–Max on the rotated-sphere range). Let Cb be [−1,1] the optimal b-bit Lloyd–Max quantizer designed for the source N (0, 1/d). Let wmax (b) denote the maximum width of any bin of Cb whose intersection with [−1, 1] is non-empty (the outermost bins of Cb extend to ±∞, but we only need the bound on the rotated-sphere coordinates which lie in [−1, 1]). Then for all t ∈ [−1, 1], [−1,1] |t − Cb (t)| ≤ wmax (b)/2.
Consequently, for v ∈ S d−1 (each coordinate has |vj | ≤ 1, so (Πv)j ∈ [−1, 1]), ∥Πv − Cb (Πv)∥2 ≤ √ [−1,1] d · wmax (b)/2 deterministically. The expected squared per-coordinate error against the source distribution is the rate-distortion limit Db /d for Gaussian sources at high rate (Panter–Dite). Correction note. An earlier draft of this lemma claimed Cb is 1-Lipschitz (non-expansive). That claim is false: Cb is piecewise constant, so at any bin boundary ti , |u − u′ | → 0 while |Cb (u) − Cb (u′ )| = |ci+1 − ci | > 0. The Lipschitz constant of Cb is undefined (infinite). We have corrected the lemma to the bounded-output property that the proofs actually need. Proof. By construction, every input t in bin Bi = (ti−1 , ti ] is mapped to centroid ci , with |t − ci | ≤ max(|ci − ti−1 |, |ti − ci |) ≤ wi /2 where wi := ti − ti−1 is the bin width. Taking the max over bins √ [−1,1] gives the per-coordinate bound. The componentwise ℓ2 extension is ∥ϵ∥2 ≤ d · wmax (b)/2.
F.3
Main theorem (fixed-vector form)
Theorem 3 (High-probability MSE bound for TQ; restatement of Zandieh et al., 2025a Thm. 1 in high-probability form). Let v̂ be defined by Eq. (1). Fix any v ∈ S d−1 . For any δ ∈ (0, 1), with probability at least 1 − δ over the choice of Π: r p 8 log(2/δ) ∥v̂ − v∥2 ≤ Db + Rd + , (2) d−2 √ where Rd = O(1/ d) captures the deviation of the per-coordinate marginal in Lemma 1 from the Gaussian source for which Cb was designed. 24
Proof sketch (rigorous version deferred to v2). Define g(Π) := ∥Π⊤ Cb (Πv)−v∥2 = ∥Cb (Πv)−Πv∥2 P d (norm preservation under orthogonal Π). Note g(Π)2 = j=1 ((Πv)j − Cb ((Πv)j ))2 . Step 1 (expectation). By Lemma 1, the marginal of each (Πv)j is the same Beta-derived density fd regardless of v, so by linearity EΠ [g(Π)2 ] = d · ET ∼fd [(Cb (T ) − T )2 ]. The right side equals Db when T ∼ N (0, 1/d). The deviation of fd from N (0, 1/d) is O(1/d) in Kolmogorov distance; the integrated squared-error difference is similarly O(1/d) (bounded support of f√ d plus bounded 2 codebook centroids). Hence EΠ [g(Π) ] = Db + O(1/d) and by Jensen EΠ [g(Π)] ≤ Db + Rd with √ Rd = O(1/ d) (numerically dominated by the rate-distortion floor at d ≥ 96; see §3.2 “Tightness in practice”). [−1,1] Step 2 (bounded almost surely). By Lemma 2, every coordinate error is bounded by wmax (b)/2, [−1,1] so g(Π)2 ≤ d · wmax (b)2 /4 almost surely. Step 3 (concentration — sketch). g(Π)2 is a bounded function of Π (Step 2) with known expectation (Step 1). Concentration around the mean follows from a bounded-difference (McDiarmid) argument on the action of Π on a fixed orthonormal basis, or equivalently from sub-Gaussian concentration of Πv on the sphere. We claim ! (d − 2)t2 P g(Π) − EΠ [g(Π)] ≥ t ≤ 2 exp − [−1,1] c · wmax (b)2 p [−1,1] for an absolute constant c, giving t = O(wmax (b) log(1/δ)/d) at confidence δ. A previous draft attempted to obtain a Lipschitz constant for Π 7→ g(Π) via a non-expansiveness property of Cb that does not hold (Cb is piecewise constant); the bounded-error route above replaces it. The rigorous constant c and the supporting McDiarmid bookkeeping are deferred to v2.
F.4
Tight uniform-over-sphere inner-product error bound
Theorem 4 (Uniform-over-sphere IP-error bound for ANN; novel contribution). Under the setup of Theorem 3, fix any query q ∈ S d−1 and any δ ∈ (0, 1). With probability at least 1 − δ over the random rotation Π, simultaneously for every v ∈ S d−1 : r 2 d log(3d) + log(2/δ) ⟨q, v⟩ − ⟨q, v̂⟩ ≤ Db + Rd′ + 2Db · + . (3) d−1 d √ where Db is the per-coordinate Lloyd–Max distortion of Theorem 3 and Rd′ = O(1/ d) collects the and the bias-concentration term. The dominant random term is p p p Gaussian-marginal correction 2Db log(3d)/(d − 1) = O( Db log d/d), a factor of d/ log d tighter than the Cauchy–Schwarz bound. Proof sketch (rigorous version deferred to v2). Note on proof status. As flagged at the top of this appendix, the route below relies in two places on a Lipschitz-extension argument (Steps 2b and 4) for which the underlying Lipschitz constant cannot come from Cb itself (Cb is piecewise constant; see the p correction note under Lemma 2). The bound itself — specifically the dominant random term 2Db log(3d)/(d − 1) — is consistent with the per-pair in-expectation IP bound of Zandieh et al. (2025a) Thm. 2 lifted to high-probability via an ϵ-net, and we believe survives. A rigorous treatment requires either replacing the Lipschitz step with a McDiarmid-style boundeddifference argument on the action of Π, or with a moment-based concentration combining the bounded ℓ∞ error from Lemma 2 with the in-expectation MSE from Zandieh et al. (2025a). We sketch the argument below for completeness; the rigorous derivation is on the v2 follow-up list.
25
δ-budget allocation. We will combine three concentration events, each consuming part of the total failure budget δ. Let N := |N1/d | ≤ (3d)d denote the size of a maximal (1/d)-net of S d−1 ; we will use such a net in Step 4. Split δ = δ1 + δ2 + δ3 with δ1 = δ2 = δ3 = δ/3 for simplicity. δ1 is reserved for the norm-of-ϵ event (Step 2a), δ2 for the bias event uniformly over the net (Step 2b), and δ3 for the random-direction event uniformly over the net (Step 3). All three events together imply the conclusion uniformly over S d−1 via the (sketch) extension argument in Step 4. Recall v̂ = Π⊤ Cb (Πv), so v − v̂ = Π⊤ (Πv − Cb (Πv)). Define ϵv := Πv − Cb (Πv) as the percoordinate quantization error in the rotated frame at vector v. Then ⟨q, v−v̂⟩ = ⟨Πq, Πv−Cb (Πv)⟩ = ⟨Πq, ϵv ⟩. Step 1 (joint distribution decomposition). Conditional on Πv, the conditional distribution p of Πq under Haar measure decomposes as Πq | Πv = αv · Πv + βv · Uv , where αv := ⟨q, v⟩, βv := 1 − αv2 , and Uv is uniform on the unit sphere of the (d − 1)-dimensional subspace (Πv)⊥ , independent of Πv. Hence ⟨Πq, ϵv ⟩ = αv · ⟨Πv, ϵv ⟩ + βv · ⟨Uv , ϵv ⟩. Step 2a (norm of ϵ event, budget δ1 ). By Theorem 3 applied with confidence δ1 /N and unionbounded over the net N1/d , with probability ≥ 1 − δ1 over Π, simultaneously for every v0 ∈ N1/d : q q (1) (1) log(N/δ1 ) d log(3d)+log(1/δ) 2 ∥ϵv0 ∥2 ≤ Db + Rd := M1 , Rd = O =O . d d √ For d large this is O( log d), a constant in d up to log factors. We use M1 as an upper bound on ∥ϵv0 ∥2 in Step 3 below. Step 2b (bias event uniformly over the net, budget δ2 — proof-status note). For each v0 ∈ N1/d , let hv0 (Π) := ⟨Πv0 , ϵv0 ⟩ = 1 − ⟨Πv0 , Cb (Πv0 )⟩. By Lloyd–Max optimality EΠ [hv0 (Π)] = Db (the in-expectation IP bound of Zandieh et al. (2025a) Thm. 2). We assume here, deferring rigorous justification to v2, that hv0 concentrates around Db at the rate √ q d log(3d)+log(1/δ) (2) b· =: Rd , hv0 (Π) − Db ≤ O d uniformly over v0 ∈ N1/d with failure budget δ2 . An earlier draft derived this via Lévy–Milman √ concentration with Lipschitz constant Lh = O( b), but hv0 is not Lipschitz in Π because Cb is piecewise constant (see Lemma 2 correction note). The intended replacement is a sub-Gaussianstyle tail argument on hv0 − E[hv0 ] combining the in-expectation MSE with the bounded ℓ∞ error, similar to standard concentration for bounded random variables on O(d). We retain the resulting (2) (2) bound; the bias term contribution is |αv0 | · (Db + Rd ) ≤ Db + Rd (using |αv0 | ≤ 1). Step 3 (random-direction event uniformly over the net, budget δ3 ). For each v0 ∈ N1/d , conditional on Πv0 and on the Step 2a event {∥ϵv0 ∥2 ≤ M1 }, the random variable ⟨Uv0 , ϵv0 ⟩ is subGaussian with proxy ∥ϵv0 ∥2 /(d − 1) ≤ M1 /(d − 1) (by rotational invariance of Uv0 on the (d − 2)sphere). Hence 2 . P ⟨Uv0 , ϵv0 ⟩ ≥ t Πv0 , ∥ϵv0 ∥2 ≤ M1 ≤ 2 exp − (d−1)t 2M1 Setting this conditional failure probability to δ3 /N and union-bounding over N1/d : q 2M1 ·(log N +log(2/δ3 )) βv0 ⟨Uv0 , ϵv0 ⟩ ≤ . d−1 (1)
Plugging M1 = Db + Rd and log N ≤ d log(3d): q (3) 2Db ( d log(3d)+log(2/δ3 ) ) βv0 ⟨Uv0 , ϵv0 ⟩ ≤ + Rd , d−1 26
q p (3) (1) (1) where Rd = O( Rd log(3d)/d) = O( 4 (log d)3 /d) is the lower-order correction from Rd . Step 4 (extension to all v ∈ S d−1 — proof-status note). Define fΠ (v) := ⟨q, v − Π⊤ Cb (Πv)⟩. For any v, v ′ ∈ S d−1 , the triangle inequality plus ∥q∥ = 1 gives |fΠ (v) − fΠ (v ′ )| ≤ ∥v − v ′ ∥ + ∥Cb (Πv) − Cb (Πv ′ )∥. Bounding the second term by ∥v − v ′ ∥ to get a constant-2 Lipschitz extension would require Cb to be 1-Lipschitz; as the correction note under Lemma 2 makes explicit, Cb is piecewise constant and is not Lipschitz, so this step does not survive as written. The intended replacement, deferred to v2, is a McDiarmid-style bounded-difference argument that counts net points v0 ∈ N1/d across which a (1/d)-perturbation in v moves at least one coordinate of Πv across a bin boundary of Cb ; the expected number of such crossings per coordinate is O((1/d) · d · ρ) where ρ is the density of [−1,1] bin boundaries, and summing gives a bound on |fΠ (v) − fΠ (v0 )| in terms of wmax (b)/d that is consistent with the 2/d Lipschitz term we retain below. We state the resulting bound as a claim consistent with Zandieh et al. (2025a) Thm. 2 lifted to high probability via the covering net: q ) |fΠ (v)| ≤ Db + Rd′ + 2Db ( d log(3d)+log(2/δ) + d2 , d−1 (2)
(3)
simultaneously for every v ∈ S d−1 , with probability ≥ 1 − δ over Π, where Rd′ := Rd + Rd p O( b log d/d) collects the bias-concentration correction and the lower-order ϵ-norm correction.
G
=
Explored alternatives that did not work
We briefly note two negative results from this work; full sweeps live in the public artefact. RH-IVF-TQ (random-hyperplane LSH coarse partition). Replacing the k-means coarse partition with L random hyperplanes gives a fully data-independent index. On Deep-1M the best configuration (L=8, np =80) reaches 79.2% R@10 versus IVF-TQ k-means at 89.5%—a ∼10pp deficit. Under worst-case rotation shift, RH-IVF-TQ ends at 49.8% vs. IVF-TQ frozen at 61.7%— dominated even where it should have an advantage. Random partitioning misses cluster structure that real ANN datasets exhibit. FA-IVF-TQ (query-frequency-adaptive bit allocation). Per-vector re-encoding at variable precision based on hit counts. With an oracle hot set, FA-IVF-TQ at 2.02 bits/coord matches uniform 4-bit at 36% less memory. With realistic 5K-query warmup discovery, it collapses to 78.4% (vs. uniform 4-bit at 89.4%) because the warmup index misses ∼30% of truly-hot vectors. The premise has two requirements in tension—steep bit-precision sensitivity (favours low d) and accurate hot-set discovery (favours high baseline recall)—and we found no regime satisfying both.
H
Downstream NDCG: BeIR/MS MARCO spot-check
We evaluate NDCG@10 on the BeIR/MS MARCO dev set (1M passages, 5,000 queries, public qrels, MiniLM-L6 encoder). At matched memory, IVF-TQ records NDCG@10 = 39.40 versus 39.28 for IVF-PQ trained on the full 1M corpus and 38.24 for stale IVF-PQ. This is a single-dataset, singleseed observation: the IVF-TQ vs. fresh-PQ gap (0.12pp) is well within the sampling noise expected on a single benchmark, and the IVF-TQ vs. stale-PQ gap (1.16pp) is consistent with the recall-axis streaming results in §4. A full BeIR sweep with bootstrap confidence intervals is in the v2 follow-up plan. 27
Table 10: Recall@10 on million-scale benchmarks. ScaNN dominates the static-recall axis at fixed compressed memory; IVF-TQ matches OPQ and is competitive with ScaNN below 96% recall but trails it above. The differentiator of IVF-TQ is operational (codebook-free residual layer, hence streaming-robust per §4). § Extended RaBitQ rows: produced by our Python reimplementation; for full fidelity, substitute the official Extended RaBitQ implementation (Gao et al., 2025). Method
R@10
QPS
Memory
Codebook training?
73.2% 89.9% 82.5% 93.4% 97.0% 98.2% 99.8% 88.4% 96.2% 98.6% 87.8% 91.1% 87.5% 91.3% 93.2% 96.1%
7.8K 15K 4.6K 15K 4.1K 76K 22K 6.9K 5.9K 3.2K 2.7K 2.8K 11K 11K 11K 5.9K
62 MB 123 MB 62 MB 123 MB 123 MB 732 MB 732 MB 62 MB† 62 MB† 62 MB† 81 MB 96 MB 81 MB 96 MB 111 MB 111 MB
PQ PQ OPQ + PQ OPQ + PQ OPQ + PQ None None ScaNN AH ScaNN AH ScaNN AH None None None None None None
85.1% 85.3% 94.5% 97.3% 97.6% 91.1% 96.9% 98.8% 89.7% 92.5% 89.9% 92.8% 94.2% 96.4%
8.8K 6.0K 22K 6.3K 93K 8.9K 7.6K 4.8K 2.7K 2.8K 14K 13K 12K 6.9K
46 MB 46 MB 92 MB 92 MB 610 MB 47 MB† 47 MB† 47 MB† 61 MB 73 MB 61 MB 73 MB 84 MB 84 MB
PQ OPQ + PQ OPQ + PQ OPQ + PQ None ScaNN AH ScaNN AH ScaNN AH None None None None None None
81.2% 92.7% 94.6% 96.5% 95.1% 99.3% 86.8%
3.9K — 2.4K 0.6K 61K 18K 5.0K
458 MB 916 MB 915 MB 915 MB 6097 MB 6097 MB 611 MB
PQ PQ OPQ + PQ OPQ + PQ None None None
SIFT-1M (1M, dim=128) FAISS IVF-PQ m=64, np =80 FAISS IVF-PQ m=128, np =20 FAISS OPQ+IVF-PQ m=64, np =160 FAISS OPQ+IVF-PQ m=128, np =20 FAISS OPQ+IVF-PQ m=128, np =80 FAISS HNSW M=32, efs =64 FAISS HNSW M=32, efs =256 ScaNN AH+tree, Ls =20 ScaNN AH+tree, Ls =50 ScaNN AH+tree, Ls =100 Ext. RaBitQ B=5, np =20§ Ext. RaBitQ B=6, np =20§ IVF-TQ 4-bit, np =20 (ours) IVF-TQ 5-bit, np =20 (ours) IVF-TQ 6-bit, np =20 (ours) IVF-TQ 6-bit, np =40 (ours) Deep-1M (1M, dim=96) FAISS IVF-PQ m=48, np =80 FAISS OPQ+IVF-PQ m=48, np =160 FAISS OPQ+IVF-PQ m=96, np =20 FAISS OPQ+IVF-PQ m=96, np =80 FAISS HNSW M=32, efs =64 ScaNN AH+tree, Ls =20 ScaNN AH+tree, Ls =50 ScaNN AH+tree, Ls =100 Ext. RaBitQ B=5, np =20§ Ext. RaBitQ B=6, np =20§ IVF-TQ 4-bit, np =20 (ours) IVF-TQ 5-bit, np =20 (ours) IVF-TQ 6-bit, np =20 (ours) IVF-TQ 6-bit, np =40 (ours) Deep-10M (10M, dim=96) FAISS IVF-PQ m=48, np =80 FAISS IVF-PQ m=96, np =20 FAISS OPQ+IVF-PQ m=96, np =20 FAISS OPQ+IVF-PQ m=96, np =80 FAISS HNSW M=32, efs =64 FAISS HNSW M=32, efs =256 IVF-TQ 4-bit, np =20 (ours)
28
Table 11: Flat-TQ regime (no IVF): sign-bit refinement vs. QJL at matched memory (Recall@10). All columns share Stage 1 (rotation + Lloyd–Max); only the 1-bit Stage 2 differs. “No Stage 2” uses b bits/coord; “QJL” and “Sign-bit” add 1 bit/coord, so the two rightmost columns use identical b+1 bits/coord memory. 10K-scale: nq =200; million-scale: nq =1000, 1M database, seed 42. Best per row in bold. The sign-bit advantage shown here is specific to the flat-TQ regime; once IVF is applied, the marginal benefit of Stage 2 collapses (Table 12). Dataset
Bits (b)
SIFT-1M SIFT-1M Deep-1M Deep-1M GloVe-1M GloVe-1M
3-bit 4-bit 3-bit 4-bit 3-bit 4-bit
No Stage 2 (b bits)
QJL (b+1 bits)
Sign-bit (ours) (b+1 bits)
30.6% 51.6% 54.2% 71.2% 64.8% 78.5%
33.8% 54.3% 57.1% 73.6% 67.3% 80.1%
49.1% 69.8% 69.0% 82.1% 77.3% 87.4%
Avg. ∆ over QJL (1M flat TQ, n=6 cells) Range over QJL
+11.4pp +7.3 to +15.5pp
Table 12: IVF-TQ regime: sign-bit refinement vs. Extended RaBitQ-equivalent (Gao et al., 2025) at matched total memory. “Ext. RaBitQ (B)” is per-coordinate Lloyd–Max at B bits with no subbin refinement (TQ Stage 1 only at B bits, equivalent to Extended RaBitQ at B for d ≥ 64 up to the O(1/d) marginal-correction term in Theorem 1). “IVF-TQ” uses b=B−1 bits Stage 1 + 1 bit Stage 2, so total bits = B in both columns. Both methods are wrapped in IVF (L=1000, np =20, nq =1000, seed 42). Mean ∆ across 9 cells: +0.08pp; paired t-test p=0.50, 95% CI [−0.19, +0.35]pp— no detectable difference. Reproduced by experiments/extended rabitq baseline.py; the Ext. RaBitQ rows here use our Python reference (the per-coordinate marginals coincide with the official implementation for d ≥ 64). Dataset
Total bits
Memory
Ext. RaBitQ
IVF-TQ (ours)
∆
SIFT-1M
4 5 6
65 MB 81 MB 96 MB
80.14% 87.77% 91.07%
79.76% 87.78% 91.59%
−0.38pp +0.01pp +0.52pp
Deep-1M
4 5 6
50 MB 61 MB 73 MB
83.57% 89.74% 92.47%
83.75% 89.93% 92.80%
+0.18pp +0.19pp +0.33pp
GloVe-1M
4 5 6
52 MB 64 MB 76 MB
76.71% 81.07% 82.92%
76.21% 81.03% 83.35%
−0.50pp −0.04pp +0.43pp
Mean ∆ across 9 cells
+0.08pp
29
Table 13: Full Stage 2 ablation on Recall@10 (10K-scale). Dataset
Bits
No Stage 2
QJL
Sign-bit
Synthetic
2-bit 3-bit 4-bit
54% 73% 85%
58% 74% 87%
72% 86% 92%
SIFT-128
2-bit 3-bit 4-bit
43% 59% 73%
47% 62% 75%
56% 73% 84%
GloVe-100
2-bit 3-bit 4-bit
56% 74% 84%
59% 75% 85%
72% 84% 92%
Table 14: Recall@1 (10K-scale). The sign-bit refinement advantage is even larger here since top-1 is more sensitive to ranking inversions. Dataset
Bits
No Stage 2
QJL
Sign-bit
Synthetic
2-bit 3-bit 4-bit
69% 83% 87%
71% 84% 87%
81% 87% 96%
SIFT-128
2-bit 3-bit 4-bit
30% 43% 63%
33% 48% 66%
44% 60% 74%
GloVe-100
2-bit 3-bit 4-bit
45% 68% 85%
48% 70% 86%
67% 83% 90%
Table 15: Streaming on Deep-10M. IVF-TQ holds within 1pp of its initial recall while IVF-PQ degrades 3.4pp. Re-training the PQ codebook every batch (cumulatively 309 seconds) recovers only +0.15pp. Vectors indexed
IVF-TQ
IVF-PQ (stale)
IVF-PQ (retrain/1M)
Retrain cum.
1M (trained) 2M 3M 4M 5M 6M 7M 8M 9M 10M
87.54% 87.31% 87.24% 86.96% 86.89% 86.84% 86.70% 86.74% 86.71% 86.65%
82.16% 81.18% 80.70% 80.32% 79.87% 79.61% 79.32% 79.20% 79.04% 78.79%
82.16% 81.11% 80.67% 80.29% 80.01% 79.81% 79.60% 79.15% 79.10% 78.94%
0s 19 s 43 s 70 s 100 s 135 s 173 s 214 s 260 s 309 s
Change (1M→10M)
−0.89pp
−3.37pp
−3.22pp
—
30
Table 16: Streaming on SIFT-10M. IVF-TQ improves by +0.63pp from 1M to 10M while IVF-PQ degrades −5.99pp under stale codebook and −5.76pp despite per-batch retraining (354s cumulative compute, +0.23pp recovery). Vectors indexed
IVF-TQ
IVF-PQ (stale)
IVF-PQ (retrain/1M)
Retrain cum.
1M (trained) 2M 3M 4M 5M 6M 7M 8M 9M 10M
83.93% 84.40% 84.58% 84.57% 84.66% 84.70% 84.58% 84.48% 84.42% 84.56%
72.43% 70.86% 69.84% 69.19% 68.51% 68.13% 67.68% 67.20% 66.88% 66.44%
72.43% 71.23% 69.69% 69.36% 68.04% 68.10% 67.68% 67.61% 67.16% 66.67%
0s 21 s 47 s 78 s 110 s 152 s 196 s 244 s 297 s 354 s
Change (1M→10M)
+0.63pp
−5.99pp
−5.76pp
—
Table 17: Embedding-model swap on 1M MS MARCO passages. “Initial 200K” is the trained-state Recall@10 on old-encoder vectors only; “+N K B” columns are the cumulative mixed-encoder recall after streaming in N K new-encoder vectors. *BGE result reported at +300K to budget compute; trend is stable. Step
IVF-TQ
IVF-PQ stale
IVF-PQ retrain
retrain t
Gentle swap: L6 → L12 (cos = 0.51) Initial 200K (L6) +100K L12 +200K L12 +300K L12 +400K L12 +500K L12 +600K L12 +700K L12 +800K L12
91.21% 85.05% 85.67% 86.00% 86.20% 86.50% 87.08% 87.31% 87.58%
73.89% 72.46% 72.47% 72.39% 72.40% 72.40% 72.27% 72.42% 72.52%
73.89% 74.75% 75.30% 75.78% 75.75% 75.76% 75.66% 75.56% 75.67%
0s 46 s 94 s 149 s 206 s 264 s 326 s 393 s 465 s
∆ trained→1M IVF-TQ vs. retrain at 1M
−3.63pp −1.37pp +11.91pp
+1.78pp
—
Harsh swap: L6 → BGE-small (cos = 0.24) Initial 200K (L6) +100K BGE +200K BGE +300K BGE*
76.40% 74.27% 75.82% 76.82%
51.38% 51.04% 51.21% 51.62%
51.38% 72.09% 72.34% 72.36%
0s 84 s 168 s 250 s
∆ trained→+300K IVF-TQ vs. retrain at +300K
+0.42pp
+0.24pp +4.46pp
+20.98pp
—
31
Table 18: ScaNN sweep at million-scale (L=2000 leaves, reorder-100). Memory reports the compressed AH+tree footprint; ScaNN additionally stores raw vectors for reorder (550 MB total on SIFT-1M, 412 MB on Deep-1M). Dataset
Ls
R@10
QPS
Compressed
w/ reorder
SIFT-1M
20 50 100 200 400
88.4% 96.2% 98.6% 99.3% 99.4%
6.9K 5.9K 3.2K 2.1K 1.2K
62.1 MB 62.1 MB 62.1 MB 62.1 MB 62.1 MB
550 MB 550 MB 550 MB 550 MB 550 MB
Deep-1M
20 50 100 200 400
91.1% 96.9% 98.8% 99.5% 99.7%
8.9K 7.6K 4.8K 2.8K 1.5K
46.6 MB 46.6 MB 46.6 MB 46.6 MB 46.6 MB
413 MB 413 MB 413 MB 413 MB 413 MB
Table 19: Bit-importance ablation on SIFT-1M: drop in Recall@10 when k% of the indicated bit position is randomly flipped across all stored codes. TQ shows a ∼19× MSB:LSB asymmetry; PQ shows essentially none (∼1:1) at both a mid-recall and a high-recall operating point. Method (baseline R@10)
Bit position
k=5%
k=10%
k=20%
IVF-RVQ-TQ b=5+1 (95.1%)
MSB of primary LSB of primary Sign refinement
−63.3pp −3.3pp −1.1pp
−77.5pp −5.2pp −1.7pp
−89.4pp −8.1pp −3.3pp
IVF-PQ m=64 (76.9%)
MSB of code Middle bit LSB of code Random byte
−56.6pp −56.7pp −57.1pp −57.2pp
−64.7pp −65.2pp −65.4pp −65.1pp
−71.2pp −71.3pp −71.1pp −70.7pp
IVF-PQ m=128 (97.2%)
MSB of code Middle bit LSB of code Random byte
−77.3pp −76.5pp −77.1pp −76.9pp
−85.7pp −85.2pp −85.5pp −85.2pp
−91.6pp −91.5pp −91.9pp −91.8pp
∼19:1 ∼1:1 (max difference < 1pp)
TQ MSB:LSB ratio PQ MSB:LSB ratio (both m)
32