pith. sign in

arxiv: 2605.17415 · v1 · pith:WXYHVGU7new · submitted 2026-05-17 · 💻 cs.LG · cs.AI· cs.DB· cs.IR

IVF-TQ: Streaming-Robust Approximate Nearest Neighbor Search via a Codebook-Free Residual Layer

Tarun Sharma This is my paper

Pith reviewed 2026-05-20 13:58 UTC · model grok-4.3

classification 💻 cs.LG cs.AIcs.DBcs.IR
keywords approximate nearest neighbor searchstreaming ingestioninverted file indexresidual quantizationcodebook-free designrecall stabilityscalar quantization
0
0 comments X

The pith

A codebook-free residual layer in IVF indexes limits recall loss to under one percentage point during streaming data ingestion.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that an IVF index can remain stable when new data arrives continuously by replacing trained residual codebooks with a fixed random rotation plus a precomputed scalar quantizer that depends only on bit budget and dimension. Only the coarse partition is learned from data, so no per-batch retraining is required. If the claim holds, systems that ingest streams would avoid the operational cost and performance drop that come from keeping a trained codebook up to date. A sympathetic reader would care because many real-world nearest-neighbor workloads, such as recommendation or search, receive data in continuous batches rather than in one static collection.

Core claim

The central claim is that equipping 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)—eliminates codebook staleness as a source of degradation. On a streaming Deep-10M workload the design drops from 87.4 % to 86.6 % recall while a comparable IVF-PQ index loses 3.23 pp; retraining the PQ codebook after each batch does not close the gap at any tested budget. The same pattern appears on a shuffled i.i.d. control, showing that the gap is not solely due to distribution shift.

What carries the argument

The codebook-free residual layer: a single fixed random rotation followed by precomputed Lloyd-Max scalar quantization whose levels depend only on bit budget and dimension. It carries the argument by removing any need to adapt the residual quantizer to incoming data.

If this is right

  • Recall remains within 0.8 pp of the static baseline across the tested streaming regime while standard PQ-based indexes lose several points.
  • At memory budgets where PQ can use roughly 1.5 times more bits, absolute recall can favor PQ, yet the operational advantage of never retraining the residual layer persists.
  • Partition-only refresh restores most performance (up to 97.8 % with re-ranking) when the initial rotation becomes misaligned with later data.
  • The design works across multiple bit budgets and across both Deep-10M and SIFT-1M collections.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the uniform-over-sphere inner-product error bound for the fixed rotation holds in practice, the same residual layer could be dropped into other partition-based indexes without further tuning.
  • Long-running production systems that must serve queries while ingesting new vectors would see lower maintenance cost because only the coarse index, not the residual quantizer, needs periodic updates.
  • The approach suggests a broader separation between coarse partitioning (which must adapt) and residual encoding (which can remain static) for any streaming similarity search workload.

Load-bearing premise

That the observed performance gap under streaming is caused mainly by staleness of the trained codebook rather than by changes in partition quality or sensitivity to the particular rotation chosen.

What would settle it

Run the same streaming protocol on a new dataset where the rotation is deliberately mismatched to the data distribution; if IVF-TQ recall then drops by more than one percentage point while the partition-only refresh still recovers most of the loss, the claim that the fixed residual layer is the decisive factor would be weakened.

Figures

Figures reproduced from arXiv: 2605.17415 by Tarun Sharma.

Figure 1
Figure 1. Figure 1: IVF-TQ pipeline. Top: indexing has no codebook training; only [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Streaming ingestion on SIFT-1M (200K trained, then 8 batches of 100K). IVF-TQ recall [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Recall@10 vs. cumulative codebook re-training cost (SIFT-1M streaming). IVF-TQ re [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
read the original 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., 2025), 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% (Delta = -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.5x 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 -- IVF-RaBitQ 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

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces IVF-TQ, an IVF-based approximate nearest neighbor index that pairs a trained coarse partition with a codebook-free residual quantizer consisting of a single fixed random rotation followed by a precomputed Lloyd-Max scalar quantizer whose parameters depend only on bit budget b and dimension d. The central claim is that this architecture substantially reduces recall degradation under streaming ingestion compared with IVF-PQ, because no data-dependent codebook must be maintained or retrained. Supporting evidence includes multi-seed streaming experiments on Deep-10M (IVF-TQ drops 0.80 pp while IVF-PQ drops 3.23 pp), a shuffled-i.i.d. control on SIFT-1M, a uniform-over-sphere inner-product error bound, and an adaptive partition-refresh variant that recovers most performance under rotation shift.

Significance. If the reported deltas and bound hold under the stated experimental controls, the work supplies a concrete operational advantage for maintaining ANN indexes on continuously arriving data without periodic full retraining. The codebook-free residual and the explicit comparison against per-batch PQ retraining across memory budgets are the most load-bearing contributions; the bound and the adaptive refresh are useful but secondary.

major comments (2)
  1. [§4] §4 (Streaming Experiments), Deep-10M and SIFT-1M tables: the shuffled-i.i.d. control shows IVF-PQ losing 3.9 pp even with no distribution shift. This result weakens the attribution of the observed streaming gap primarily to codebook staleness and indicates that batch-handling mechanics, residual computation after the fixed rotation, or IVF-partition interaction may be contributing factors; a quantitative decomposition isolating these effects is needed to support the central robustness claim.
  2. [§3.2] §3.2 (Uniform-over-sphere IP-error bound): the proof sketch is referenced but the manuscript does not state the precise assumptions on the random rotation matrix or the exact form of the Lloyd-Max quantizer used in the bound derivation; without these, it is unclear whether the bound applies directly to the implemented IVF-TQ or only to the idealized flat-TQ case.
minor comments (2)
  1. [Tables 1-3] Table captions and axis labels should explicitly state the number of seeds and whether error bars represent standard deviation or standard error.
  2. [§5] The description of the adaptive IVF-TQ variant should clarify whether the re-ranking step uses the same fixed rotation or an additional data-dependent step.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on the streaming experiments and the error bound. We address each major comment below and indicate the planned revisions.

read point-by-point responses

  1. Referee: [§4] §4 (Streaming Experiments), Deep-10M and SIFT-1M tables: the shuffled-i.i.d. control shows IVF-PQ losing 3.9 pp even with no distribution shift. This result weakens the attribution of the observed streaming gap primarily to codebook staleness and indicates that batch-handling mechanics, residual computation after the fixed rotation, or IVF-partition interaction may be contributing factors; a quantitative decomposition isolating these effects is needed to support the central robustness claim.

    Authors: We agree that the shuffled-i.i.d. control on SIFT-1M, where IVF-PQ loses 3.9 pp without distribution shift, indicates that the streaming performance gap cannot be attributed solely to codebook staleness. Factors such as batch-handling mechanics and IVF-partition interactions likely contribute as well. To strengthen the central claim, we will add a quantitative decomposition in the revised §4 that separates the degradation due to distribution shift from other effects. This will include direct comparison of recall drops in the streaming versus shuffled-i.i.d. settings, along with the impact of per-batch PQ retraining in both regimes, to better isolate the operational robustness benefit of the codebook-free residual layer. revision: yes

  2. Referee: [§3.2] §3.2 (Uniform-over-sphere IP-error bound): the proof sketch is referenced but the manuscript does not state the precise assumptions on the random rotation matrix or the exact form of the Lloyd-Max quantizer used in the bound derivation; without these, it is unclear whether the bound applies directly to the implemented IVF-TQ or only to the idealized flat-TQ case.

    Authors: We thank the referee for this clarification request. The bound derivation assumes a random rotation matrix drawn from the Haar measure on the orthogonal group, which ensures that the rotated vectors remain uniformly distributed on the sphere. The Lloyd-Max scalar quantizer is the optimal (minimum mean-squared-error) scalar quantizer for the resulting coordinate-wise marginal distributions, with parameters precomputed solely from bit budget b and dimension d as in the TurboQuant construction. We will revise §3.2 to state these assumptions explicitly and confirm that the bound applies directly to the IVF-TQ residual layer, which employs the identical fixed rotation and precomputed quantizer as the flat-TQ case (the coarse IVF partition affects only the search procedure, not the per-vector residual error bound). revision: yes

Circularity Check

0 steps flagged

Minor self-citation to TurboQuant; core design and empirical claims remain independent

full rationale

The paper defines IVF-TQ via a fixed random rotation plus precomputed Lloyd-Max scalar quantizer depending only on (b, d), with training limited to the IVF coarse partition. The uniform-over-sphere IP-error bound is supplied directly (proof sketch in v1, rigorous in v2) rather than derived from fitted data. Streaming robustness is demonstrated via multi-seed empirical deltas against IVF-PQ baselines and a shuffled-i.i.d. control, not by renaming fitted quantities as predictions. The TurboQuant citation supplies architectural precedent but is not load-bearing for the staleness-reduction claim, which rests on external benchmarks and per-batch retraining experiments. No self-definitional reduction, fitted-input prediction, or uniqueness theorem imported from overlapping prior work appears in the derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The design rests on standard properties of random rotations and Lloyd-Max optimality for scalar quantization after rotation; no new free parameters are introduced beyond standard IVF training.

axioms (1)
  • domain assumption Lloyd-Max scalar quantization after fixed rotation yields near-optimal rate-distortion for the residual under the uniform-over-sphere assumption.
    Invoked to justify the codebook-free residual layer depending only on (b, d).

pith-pipeline@v0.9.0 · 5951 in / 1406 out tokens · 70216 ms · 2026-05-20T13:58:16.725470+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages · 1 internal anchor

  1. [1]

    Quantization for vector search under streaming updates.arXiv preprint arXiv:2512.18335,

    Ishaq Aden-Ali, Hakan Ferhatosmanoglu, Alexander Greaves-Tunnell, Nina Mishra, and Tal Wag- ner. Quantization for vector search under streaming updates.arXiv preprint arXiv:2512.18335,

    work page arXiv

  2. [2]

    Accelerated nearest neighbor search with quick ADC

    Fabien Andr´ e, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. Accelerated nearest neighbor search with quick ADC. InProceedings of the 2017 ACM on International Conference on Multi- media Retrieval, pages 159–166,

    work page 2017

  3. [3]

    Filtered-DiskANN: Graph algorithms for approximate nearest neighbor search with filters

    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. InProceedings of the ACM Web Conference 2023, pages 3406–3416,

    work page 2023

  4. [4]

    PolarQuant: Quantizing KV caches with polar transformation.arXiv preprint arXiv:2502.02617,

    Insu Han, Praneeth Kacham, Amin Karbasi, Vahab Mirrokni, and Amir Zandieh. PolarQuant: Quantizing KV caches with polar transformation.arXiv preprint arXiv:2502.02617,

    work page arXiv

  5. [5]

    Stuart Lloyd

    arXiv:2509.12086. Stuart Lloyd. Least squares quantization in PCM.IEEE Transactions on Information Theory, 28 (2):129–137,

    work page arXiv

  6. [6]

    Ilyas, Theodoros Rekatsinas, and Shivaram Venkataraman

    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,

    work page arXiv

  7. [7]

    Sentence-BERT: Sentence embeddings using Siamese BERT- Networks

    Nils Reimers and Iryna Gurevych. Sentence-BERT: Sentence embeddings using Siamese BERT- Networks. InProceedings of the 2019 Conference on Empirical Methods in Natural Language Processing,

    work page 2019

  8. [8]

    GPU-native approx- imate nearest neighbor search with IVF-RaBitQ: Fast index build and search.arXiv preprint arXiv:2602.23999,

    Jifan Shi, Jianyang Gao, James Xia, Tam´ as B´ ela Feh´ er, and Cheng Long. GPU-native approx- imate nearest neighbor search with IVF-RaBitQ: Fast index build and search.arXiv preprint arXiv:2602.23999,

    work page arXiv

  9. [9]

    FreshDiskANN: A fast and accurate graph-based ANN index for streaming similarity search.arXiv preprint arXiv:2105.09613,

    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,

    work page arXiv

  10. [10]

    TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate

    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...

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  11. [11]

    We ran the wrapper on a Linux/Colab environment

    ships only Linux wheels viapip install scann. We ran the wrapper on a Linux/Colab environment. We use AsymmetricHashing scoring withanisotropic quantization threshold= 0.2,dimensions per block= 2, reordering on the top 100 candidates, and a sweep overnum leaves to search∈ {20,50,100,200,400}atL=2000 leaves. E Cascade search via Lloyd–Max bin ordinality St...

    work page 2000

  12. [12]

    and a per-pair in-expectation IP-error bound (their Theorem 2). Theorem 3 below is a high-probability counter- part of their MSE bound; we include it for self-containedness and to fix notation for Theorem 4, butwe 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 o...

    work page 2018

  13. [13]

    Tightness in practice

    See e.g. Vershynin (2018) Theorem 3.4.6. Lemma 2(Bounded per-coordinate error of Lloyd–Max on the rotated-sphere range).LetC b be the optimalb-bit Lloyd–Max quantizer designed for the sourceN(0,1/d). Letw [−1,1] max (b)denote the maximum width of any bin ofC b whose intersection with[−1,1]is non-empty (the outermost bins ofC b extend to±∞, but we only nee...

    work page 2018

  14. [14]

    No Stage 2

    ) d−1 +R (3) d , 26 whereR (3) d =O( q R(1) d log(3d)/d) =O( 4 p (logd) 3/d) is the lower-order correction fromR (1) d . Step 4 (extension to allv∈S d−1 — proof-status note).Definef Π(v) :=⟨q, v−Π ⊤Cb(Πv)⟩. For anyv, v ′ ∈S d−1, the triangle inequality plus∥q∥= 1 gives |fΠ(v)−f Π(v′)| ≤ ∥v−v ′∥+∥C b(Πv)−C b(Πv′)∥. Bounding the second term by∥v−v ′∥to get ...

    work page 2025

  15. [15]

    Ext. RaBitQ (B)

    at matched total memory. “Ext. RaBitQ (B)” is per-coordinate Lloyd–Max atBbits with no sub- bin refinement (TQ Stage 1 only atBbits, equivalent to Extended RaBitQ atBford≥64 up to theO(1/d) marginal-correction term in Theorem 1). “IVF-TQ” usesb=B−1 bits Stage 1 + 1 bit Stage 2, so total bits =Bin both columns. Both methods are wrapped in IVF (L=1000,n p=2...

    work page 2000