IVF-TQ: Calibration-Free Streaming Vector Search via a Codebook-Free Residual Layer
Tarun Sharma · 2026
Read IVF-TQ: Calibration-Free Streaming Vector Search via a Codebook-Free Residual Layer by Tarun Sharma (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-17415.txt.
Introduction
Sharma presents IVF-TQ, a streaming vector-search index whose residual compression needs no codebook and no retraining. A fixed random rotation plus a precomputed Lloyd-Max scalar quantizer, set only by bit width and dimension, replaces codebooks fitted to early samples that silently lose recall as data grows. A sphere-uniform error bound gives a structural guarantee learned methods lack. Across nine controlled cells it holds steady at one fixed configuration while per-batch retraining never closes the gap.
Catalog record
| CREATOR | Tarun Sharma |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93530 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.17415
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
IVF-TQ: Calibration-Free Streaming Vector Search via a Codebook-Free Residual Layer Tarun Sharma Abstract . Approximate nearest neighbor (ANN) indexes deployed against streaming corpora silently lose recall over weeks. The standard diagnosis is distribution shift, but under shuffled-i.i.d. ingestion — no shift at all — product quantization still degrades − 3.8 -3.8 pp at sub-matched bit budgets. The dominant production compression methods (PQ, OPQ, ScaNN) all fit a codebook to an initial sample and reuse it as the database grows by orders of magnitude. This paper presents IVF-TQ, an inverted-file index whose residual compression layer is data-independent: a fixed random rotation followed by a precomputed Lloyd–Max scalar quantizer parameterised only by the bit width b b and dimension d d . Only the IVF coarse k k -means partition is trained. A uniform-over-sphere inner-product error bound (Theorem 2 ) depending only on ( b , d , δ ) (b,d,\delta) provides a structural guarantee no learned-codebook method admits. The same codebook-free design enables an IVF-amplification effect that closes the gap to Extended RaBitQ to within statistical noise ( + 17.7 +17.7 pp over flat TQ at matched bit budget), and an Adaptive variant that refreshes the partition without touching the compression layer. Across nine controlled cells (three 10M datasets, three PQ memory regimes, three seeds), per-batch PQ codebook retraining never recovers the streaming gap; IVF-PQ streaming stability requires per-dataset bit-budget tuning, while IVF-TQ holds at one fixed ( b , d ) (b,d) configuration on all three datasets with Δ ∈ [ − 0.80 , + 0.56 ] \Delta\in[-0.80,+0.56] pp. The contribution is operational: no codebook to train, no per-dataset bit-budget tuning, no retraining cycle that ever closes the gap. 1. Introduction 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 from heterogeneous sources. Practitioners observe that recall on these workloads silently degrades over weeks or months, often without any code changes. The dominant compression methods used in production—product quantization ( Jégou et al. 2011 ) , Optimized PQ ( Ge et al. 2014 ) , and ScaNN’s anisotropic learned quantization ( Guo et al. 2020 ) —all share the same property: each fits a codebook to the initial training sample. The standard remedy is periodic re-training, which is computationally expensive and, at the bit-matched memory regime most modern systems use, recovers no measurable recall on 10M streaming runs (paired- t indistinguishable from no retraining in 8 of 9 cells) while costing 667 – 1328 s of cumulative compute per run (§ 4 , Tables 2 – 4 ). Concurrently, ( Aden-Ali et al. 2025 ) address the same problem by making PQ-style codebooks dynamically consistent with bounded I/O per update; we instead remove the codebook from the compression layer entirely. The standard explanation for the streaming-recall drop is distribution shift. We make a different and more nuanced argument: PQ’s streaming recall behavior is governed by bit budget in a dataset-dependent way. Across 9 controlled cells (three 10M datasets \times three PQ memory budgets, three seeds each), shuffled-i.i.d. ingestion still produces material degradation at sub-matched bit budget, ruling out distribution shift as a sufficient explanation. What changes the picture is the bit budget itself: at sufficient capacity (dataset-dependent), PQ is streaming-stable; below it, even retraining cannot close the gap (§ 4.1 ). IVF-TQ’s residual layer is governed by (b,d) alone and avoids the calibration entirely. This paper. We propose IVF-TQ , an inverted-file index whose residual compression layer is data-independent: a fixed random rotation followed by a precomputed Lloyd–Max scalar quantizer that depends only on the bit width and dimension. Only the IVF coarse partition is trained (by k -means); the residual quantizer never needs re-training. Building on TurboQuant ( Zandieh et al. 2025b ) , we trade \sim 1pp of static recall at matched memory against the strongest learned-codebook baselines for streaming stability without per-dataset bit-budget tuning. We make three contributions: (1) IVF-TQ index architecture (§ 3 ): an inverted-file index in which residuals are compressed by a fixed random rotation + precomputed Lloyd–Max scalar quantization (data-independent residual layer; the IVF coarse partition is still trained by k -means), paired with a uniform-over-sphere inner-product error bound (Theorem 2 ) depending only on (b,d,\delta) — a structural guarantee no learned-codebook method (PQ, OPQ, ScaNN) admits. The bound is structural rather than numerically tight (full discussion in § 3.2 ); multi-seed empirical evidence supports the structural claim across nine controlled cells (§ 4 ). (2) IVF amplification of codebook-free quantization (Section 3.2 ): the IVF decomposition reduces the squared error of the inner-product estimate by a factor of 1-2\mathbb{E}[\langle x,c_{l}\rangle]+\mathbb{E}[\|c_{l}\|^{2}] , explaining a +17.7 pp recall jump from flat TQ to IVF-TQ at matched bit budget on SIFT-1M. This amplification is what makes a data-independent residual layer viable at IVF scale at all : without it, codebook-free Lloyd–Max remains in the \sim 70% recall regime where production systems would not adopt it. The amplification also closes the residual-variance gap to Extended RaBitQ to within statistical noise (Table 1 ). (3) Adaptive coarse refresh (Sections 3.3 , 4.5 ): a partition-only refresh that PQ-family indexes structurally cannot perform, enabled by data-independent compression. Under worst-case rotation shift, IVF-TQ frozen drops to 67% recall. At matched bit budget (no re-ranking), Adaptive IVF-TQ at 4-bit reaches 90.3% versus PQ retrain’s 95.8% at \sim 8 bits/dim per subspace ( m{=}96 )—a 5.5pp deficit attributable to the bit-budget gap, not the algorithm. With re-ranking on top-50 candidates, Adaptive IVF-TQ reaches 97.8% , exceeding PQ retrain by 2pp at comparable refresh compute. Adaptive’s contribution is therefore the rerank-enabled regime; we report both numbers up front rather than burying the comparison. Empirical headline. IVF-TQ delivers streaming stability at one fixed (b,d) configuration on all three 10M datasets we test, with \Delta\in[-0.80,+0.56] pp (range across all 9 cells at the 10M state; per-cell CIs \pm 0.4 pp). Across nine controlled cells (three 10M datasets \times three PQ memory budgets, three seeds each), IVF-PQ does not: its streaming stability is dataset-dependent in the bit budget. At bit-matched memory ( \sim 0.95 \times IVF-TQ), IVF-PQ is stable on Deep-10M ( \Delta=-0.84\pm 0.26 pp) and on T2I-10M ( \Delta=-0.89\pm 0.32 pp) but still degrades on SIFT-10M ( \Delta=-2.31\pm 0.42 pp, gap +6.79\pm 0.25 pp behind IVF-TQ); only at super-matched ( \sim 1.5 \times ) memory is IVF-PQ stable on all three datasets. Per-batch PQ codebook retraining never recovers the streaming gap (full statistics in Tables 2 – 4 ; § 4.2 ). Under encoder-model swap (§ 4.3 ), 3-seed paired- t on the harshest swap (L6 \to BGE-small) shows IVF-TQ frozen exceeding actively-retrained IVF-PQ by +14.72\pm 0.43 pp ( p<0.001 ) at the +300K compute-budgeted state, with a similar +13.27\pm 0.77 pp gap on the gentle L6 \to L12 swap. IVF-TQ delivers streaming stability without per-dataset tuning at one fixed (b,d) compression configuration (the IVF coarse partition L is still tuned per dataset, as is standard for IVF). This is consistent with the structural data-independence guarantee of Theorem 2 (§ 3.2 ). To match this with IVF-PQ, a practitioner would need