Reusable Codebooks

    Hierarchical TurboQuant Quantization for Two-Tier Approximate Nearest-Neighbor Retrieval

    Shashwat Saket · New York University · advised by Prof. Ainesh Bakshi · May 2026
    +2.2
    Recall@1 over PQ + rerank on GloVe-200
    1 vs 2
    codebooks: one shared instead of two trained
    660–1300×
    faster index construction (Table 4)
    ±0.005
    Recall@1 vs unconstrained, over 5 seeds

    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.

    Step 1 · Setup · once

    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 x
    Shared codebook (b_exp = 4 → 16 levels)
    2-bit cheap tier (4 levels) 4-bit rerank tier
    Per-query funnel
    Database
    100,000 vectors
    Prefilter (2-bit)
    top-100 candidates
    Rerank (4-bit)
    top-k results

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

    -3-2-101232b=2, level 1: -3.260b=2, level 2: -1.049b=2, level 3: 0.066b=2, level 4: 1.2123b=3, level 1: -3.260b=3, level 2: -1.787b=3, level 3: -1.049b=3, level 4: -0.467b=3, level 5: 0.066b=3, level 6: 0.605b=3, level 7: 1.212b=3, level 8: 2.0294b=4, level 1: -3.260b=4, level 2: -2.318b=4, level 3: -1.787b=4, level 4: -1.386b=4, level 5: -1.049b=4, level 6: -0.747b=4, level 7: -0.467b=4, level 8: -0.198b=4, level 9: 0.066b=4, level 10: 0.331b=4, level 11: 0.605b=4, level 12: 0.895b=4, level 13: 1.212b=4, level 14: 1.576b=4, level 15: 2.029b=4, level 16: 2.6915b=5, level 1: -3.260b=5, level 2: -2.691b=5, level 3: -2.318b=5, level 4: -2.029b=5, level 5: -1.787b=5, level 6: -1.576b=5, level 7: -1.386b=5, level 8: -1.212b=5, level 9: -1.049b=5, level 10: -0.895b=5, level 11: -0.747b=5, level 12: -0.605b=5, level 13: -0.467b=5, level 14: -0.331b=5, level 15: -0.198b=5, level 16: -0.066b=5, level 17: 0.066b=5, level 18: 0.198b=5, level 19: 0.331b=5, level 20: 0.467b=5, level 21: 0.605b=5, level 22: 0.747b=5, level 23: 0.895b=5, level 24: 1.049b=5, level 25: 1.212b=5, level 26: 1.386b=5, level 27: 1.576b=5, level 28: 1.787b=5, level 29: 2.029b=5, level 30: 2.318b=5, level 31: 2.691b=5, level 32: 3.260
    Levels at b
    4
    MSE (computed live)
    0.170
    MSE (paper, Table 1)
    0.170
    Penalty vs native
    +44.6%

    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.

    Per-coordinate MSE by bit-width (log scale)
    Pick a strategy to highlight it. Lower is better.

    Results on real embeddings

    Three datasets of 100,000 unit-normalized vectors each. Choose a dataset to update all four charts.

    Stanford GloVe (subsampled) · d = 200 · N = 100,000 · 10,000 queries
    Two-tier Recall@1 vs prefilter size T
    Shared top-down codebook vs two independent PQ codebooks (Table 9).
    At T = 100: +0.021 R@1 for top-down
    Recall@1 ceiling at b = 4 by nesting strategy
    Mean ± std over 5 rotation seeds (Table 8).
    Single-tier baselines
    PQ vs TurboQuant vs Extended-RaBitQ at 2 and 4 bits (Table 6).
    PQTurboQuantExtended-RaBitQlighter = 2-bit
    Index construction time
    k-means for two PQ codebooks vs one Lloyd-Max codebook (Table 4).
    PQ-2 k-means360 s
    PQ-4 k-means427 s
    Top-down Lloyd-Max< 1 s
    Speedup on GloVe-200: over 787× (787 s of k-means vs under 1 s)

    Storage

    Same per-vector codes, half the codebooks.

    Database size N105 vectors
    Dimension d

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

    ApproachCodebooksCodebook sizeAll codes
    Independent PQ-2 + PQ-42160 B110 MB
    Top-down shared (ours)1128 B110 MB
    1,152 bytes of codes per vector at d = 1536.

    Why it works: three results

    The theory behind the experiments, in plain language.

    Theorem 1

    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.

    Table 1: exactly one zero-penalty entry per strategy.
    Theorem 2

    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.

    Table 1: top-down penalty grows from 0% at b=5 to 44.6% at b=2.
    Theorem 3

    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.

    Table 7: middle-anchor +0.002 R@1 over native on both OpenAI datasets.

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