Reusable Codebooks
Hierarchical TurboQuant Quantization for Two-Tier Approximate Nearest-Neighbor Retrieval
How two-tier retrieval works here
Production ANN search scores everything with cheap low-bit codes, then reranks a shortlist with expensive high-bit codes. Usually that means training two separate Product Quantization codebooks. This paper makes the cheap codebook a subset of the expensive one.
Random rotation
Rotate every database vector with one Haar-random orthogonal matrix R and scale by √d. After rotation, every coordinate looks like a standard Gaussian N(0,1) — for any dataset.
r = √d · R xExplore the codebooks
Switch between native and top-down codebooks and pick a bit-width. Each dot is a quantization level for a standard Gaussian coordinate.
These levels are computed in your browser with Lloyd-Max iteration on N(0,1). Row numbers are bit-widths; vertical lines show a level that is kept at the next bit-width. Native codebooks shift every level when the bit-width changes, so they can't share storage. Top-down keeps every lower bit-width inside the 5-bit master codebook. That is free at b = 5 and costs MSE as you go lower (Theorem 2).
Every strategy gets one free bit-width
Each nesting strategy is MSE-optimal at exactly one bit-width (its anchor) and pays a penalty at the others. For two-tier retrieval you want the rerank tier to be free, which is why top-down is anchored at the expensive bit-width.
Results on real embeddings
Three datasets of 100,000 unit-normalized vectors each. Choose a dataset to update all four charts.
Storage
Same per-vector codes, half the codebooks.
Per-vector codes cost the same either way: (2 + 4)·d / 8 bytes. What changes is the codebook. Top-down keeps one 16-level codebook and derives the 2-bit one on the fly, instead of storing and training two (Table 3).
| Approach | Codebooks | Codebook size | All codes |
|---|---|---|---|
| Independent PQ-2 + PQ-4 | 2 | 160 B | 110 MB |
| Top-down shared (ours) | 1 | 128 B | 110 MB |
Why it works: three results
The theory behind the experiments, in plain language.
Conservation of MSE Penalty
No nested family of codebooks can be MSE-optimal at two different bit-widths at the same time.
Every strategy gets exactly one “free” bit-width (its anchor) and pays a penalty everywhere else.
Monotone Penalty of Top-Down
For top-down decimation, the penalty only grows as you move further below the anchor bit-width.
Set the master codebook size equal to the expensive tier (b_max = b_exp), not larger.
Retrieval–MSE Divergence
Recall@1 depends on the signed score-error tails, not on average MSE, so lower MSE does not guarantee better recall.
Explains why middle-anchor (higher MSE) can beat native in recall on high-dimensional data.
Limitations
- Three datasets only — CLIP, audio and multi-modal embeddings may behave differently.
- All experiments use N = 100,000 vectors; behaviour at billion scale is untested.
- The three theorems are stated with proof sketches; full proofs are future work.
- No formal lower bound yet on the total penalty summed across bit-widths.
Cite
@unpublished{saket2026reusable,
title={Reusable Codebooks: Hierarchical TurboQuant Quantization for Two-Tier Approximate Nearest-Neighbor Retrieval},
author={Saket, Shashwat},
note={Manuscript, New York University},
year={2026}
}