TurboQuant — KV Cache Compression Skill
A skill for implementing, using, and explaining Google's TurboQuant algorithm — a data-oblivious
vector quantization framework that achieves 6x memory reduction and up to 8x speedup for LLM
KV caches with zero accuracy loss.
What TurboQuant Does
TurboQuant compresses the key-value (KV) cache in transformer-based LLMs. During inference,
the KV cache grows linearly with sequence length and becomes the primary memory bottleneck
for long-context generation. TurboQuant compresses each cache vector from 32-bit floats down
to 3-4 bits per coordinate — without retraining, without calibration data, and without
measurable accuracy loss.
How It Works (Two Stages)
Stage 1: PolarQuant (MSE Minimization)
Random Orthogonal Rotation: Multiply the input vector by a random orthogonal matrix Π.
This "isotropizes" the vector — after rotation, each coordinate of a unit vector follows
a Beta(d/2, d/2) distribution (shifted to [-1, 1]), regardless of the original
vector's structure.
Lloyd-Max Scalar Quantization: Quantize each rotated coordinate independently using
a Lloyd-Max quantizer optimized for the Beta(d/2, d/2) distribution. Because the
distribution is known analytically (data-oblivious), the codebook is computed once offline
and reused for all vectors.
Stage 2: QJL (Unbiased Inner Products)
Residual Computation: Compute the quantization residual r = y - ŷ (difference between
rotated vector and its quantized reconstruction).
1-bit Sign Quantization: Project the residual through a random Rademacher matrix S
and store only the signs: sign(S @ r). This uses the Quantized Johnson-Lindenstrauss
transform to preserve inner product information in just 1 bit per dimension.
Inner Product Estimation: To compute <query, key>, combine the PolarQuant
reconstruction with a QJL correction term that uses the stored signs to unbias the estimate.
When to Use Each Variant
| Variant |
Use Case |
Bits |
Accuracy |
TurboQuant_mse |
Reconstruction (nearest neighbor search) |
b bits |
MSE-optimal |
TurboQuant_prod |
Inner products (attention computation) |
b + 1 bits |
Unbiased IP |
For KV cache compression in transformers, use TurboQuant_prod — attention requires inner
products between queries and keys, and the QJL correction ensures these estimates are unbiased.
Implementation Reference
A complete Python implementation is bundled at scripts/turboquant.py. It includes:
build_lloyd_max_codebook() — Offline codebook construction via Lloyd-Max iteration
generate_rotation_matrix() — Random orthogonal matrix via QR decomposition
TurboQuant class — Compress, decompress, and estimate inner products
TurboQuantKVCache class — Simulated KV cache with compressed storage
run_self_test() — Validation suite with MSE, cosine similarity, and IP correlation metrics
Quick Start
from scripts.turboquant import TurboQuant, TurboQuantConfig
config = TurboQuantConfig(dimension=128, bits=3, qjl_enabled=True)
tq = TurboQuant(config)
# Compress a vector
compressed = tq.compress(my_vector)
# Decompress (MSE reconstruction)
reconstructed = tq.decompress(compressed)
# Estimate inner product (unbiased, with QJL correction)
ip_estimate = tq.inner_product(query_vector, compressed)
# Check compression ratio
print(f"Compression: {tq.compression_ratio():.1f}x")
KV Cache Usage
from scripts.turboquant import TurboQuantKVCache, TurboQuantConfig
config = TurboQuantConfig(dimension=128, bits=3, qjl_enabled=True)
cache = TurboQuantKVCache(config)
# During generation — append each new KV pair
cache.append(key_vector, value_vector)
# Compute attention scores for a query
scores = cache.attention_scores(query_vector)
Key Mathematical Properties
- Data-oblivious: No calibration data needed. The codebook depends only on dimension
d
and bit-width b, not on the data distribution.
- Near-optimal distortion: Achieves rate-distortion performance within constant factors
of the theoretical optimum for Euclidean vectors.
- Unbiased inner products: The QJL stage ensures
E[<q, k̂>] = <q, k> — critical for
attention computation where biased estimates shift the softmax distribution.
- O(d) compression/decompression: Linear in dimension. No codebook search.
Performance Benchmarks (from the paper)
| Metric |
Result |
| KV cache compression |
3 bits/value, 6x reduction |
| Attention speedup (H100) |
Up to 8x on 4-bit keys |
| Needle-in-Haystack (104k tokens) |
100% retrieval accuracy at 4x compression |
| Accuracy loss |
Zero measurable loss on LongBench, ZeroSCROLLS, RULER, L-Eval |
Technical Details
For deeper mathematical treatment, see references/algorithm_details.md:
- Proof sketch for why random rotation produces Beta-distributed coordinates
- Lloyd-Max convergence properties
- QJL guarantee: the Johnson-Lindenstrauss lemma for quantized projections
- Bit-rate analysis and comparison to Product Quantization
Dependencies
- Python 3.10+
- NumPy
- SciPy (for
beta distribution and minimize_scalar)
Paper Reference
Zandieh et al., "TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate,"
ICLR 2026. arXiv: 2504.19874.
1---2name: turboquant3description: >4 Implement, use, or explain TurboQuant — Google's data-oblivious vector quantization algorithm5 for LLM KV cache compression (ICLR 2026). Use this skill when the user asks about KV cache6 compression, TurboQuant, PolarQuant, QJL (Quantized Johnson-Lindenstrauss), Lloyd-Max7 quantization for high-dimensional vectors, reducing LLM memory usage, compressing attention8 keys/values, or implementing any component of the TurboQuant pipeline. Also trigger when9 the user mentions vector quantization for inference optimization, 3-4 bit KV cache quantization,10 or inner product preserving compression.11metadata:12 source: https://skillmd.com/skills/ryuketsukami/turboquant13---1415# TurboQuant — KV Cache Compression Skill1617A skill for implementing, using, and explaining Google's TurboQuant algorithm — a data-oblivious18vector quantization framework that achieves 6x memory reduction and up to 8x speedup for LLM19KV caches with zero accuracy loss.2021## What TurboQuant Does2223TurboQuant compresses the key-value (KV) cache in transformer-based LLMs. During inference,24the KV cache grows linearly with sequence length and becomes the primary memory bottleneck25for long-context generation. TurboQuant compresses each cache vector from 32-bit floats down26to 3-4 bits per coordinate — without retraining, without calibration data, and without27measurable accuracy loss.2829## How It Works (Two Stages)3031### Stage 1: PolarQuant (MSE Minimization)32331. **Random Orthogonal Rotation**: Multiply the input vector by a random orthogonal matrix `Π`.34 This "isotropizes" the vector — after rotation, each coordinate of a unit vector follows35 a `Beta(d/2, d/2)` distribution (shifted to `[-1, 1]`), regardless of the original36 vector's structure.37382. **Lloyd-Max Scalar Quantization**: Quantize each rotated coordinate independently using39 a Lloyd-Max quantizer optimized for the `Beta(d/2, d/2)` distribution. Because the40 distribution is known analytically (data-oblivious), the codebook is computed once offline41 and reused for all vectors.4243### Stage 2: QJL (Unbiased Inner Products)44453. **Residual Computation**: Compute the quantization residual `r = y - ŷ` (difference between46 rotated vector and its quantized reconstruction).47484. **1-bit Sign Quantization**: Project the residual through a random Rademacher matrix `S`49 and store only the signs: `sign(S @ r)`. This uses the Quantized Johnson-Lindenstrauss50 transform to preserve inner product information in just 1 bit per dimension.51525. **Inner Product Estimation**: To compute `<query, key>`, combine the PolarQuant53 reconstruction with a QJL correction term that uses the stored signs to unbias the estimate.5455## When to Use Each Variant5657| Variant | Use Case | Bits | Accuracy |58|---------|----------|------|----------|59| `TurboQuant_mse` | Reconstruction (nearest neighbor search) | b bits | MSE-optimal |60| `TurboQuant_prod` | Inner products (attention computation) | b + 1 bits | Unbiased IP |6162For KV cache compression in transformers, use `TurboQuant_prod` — attention requires inner63products between queries and keys, and the QJL correction ensures these estimates are unbiased.6465## Implementation Reference6667A complete Python implementation is bundled at `scripts/turboquant.py`. It includes:6869- `build_lloyd_max_codebook()` — Offline codebook construction via Lloyd-Max iteration70- `generate_rotation_matrix()` — Random orthogonal matrix via QR decomposition71- `TurboQuant` class — Compress, decompress, and estimate inner products72- `TurboQuantKVCache` class — Simulated KV cache with compressed storage73- `run_self_test()` — Validation suite with MSE, cosine similarity, and IP correlation metrics7475### Quick Start7677```python78from scripts.turboquant import TurboQuant, TurboQuantConfig7980config = TurboQuantConfig(dimension=128, bits=3, qjl_enabled=True)81tq = TurboQuant(config)8283# Compress a vector84compressed = tq.compress(my_vector)8586# Decompress (MSE reconstruction)87reconstructed = tq.decompress(compressed)8889# Estimate inner product (unbiased, with QJL correction)90ip_estimate = tq.inner_product(query_vector, compressed)9192# Check compression ratio93print(f"Compression: {tq.compression_ratio():.1f}x")94```9596### KV Cache Usage9798```python99from scripts.turboquant import TurboQuantKVCache, TurboQuantConfig100101config = TurboQuantConfig(dimension=128, bits=3, qjl_enabled=True)102cache = TurboQuantKVCache(config)103104# During generation — append each new KV pair105cache.append(key_vector, value_vector)106107# Compute attention scores for a query108scores = cache.attention_scores(query_vector)109```110111## Key Mathematical Properties112113- **Data-oblivious**: No calibration data needed. The codebook depends only on dimension `d`114 and bit-width `b`, not on the data distribution.115- **Near-optimal distortion**: Achieves rate-distortion performance within constant factors116 of the theoretical optimum for Euclidean vectors.117- **Unbiased inner products**: The QJL stage ensures `E[<q, k̂>] = <q, k>` — critical for118 attention computation where biased estimates shift the softmax distribution.119- **O(d) compression/decompression**: Linear in dimension. No codebook search.120121## Performance Benchmarks (from the paper)122123| Metric | Result |124|--------|--------|125| KV cache compression | 3 bits/value, 6x reduction |126| Attention speedup (H100) | Up to 8x on 4-bit keys |127| Needle-in-Haystack (104k tokens) | 100% retrieval accuracy at 4x compression |128| Accuracy loss | Zero measurable loss on LongBench, ZeroSCROLLS, RULER, L-Eval |129130## Technical Details131132For deeper mathematical treatment, see `references/algorithm_details.md`:133- Proof sketch for why random rotation produces Beta-distributed coordinates134- Lloyd-Max convergence properties135- QJL guarantee: the Johnson-Lindenstrauss lemma for quantized projections136- Bit-rate analysis and comparison to Product Quantization137138## Dependencies139140- Python 3.10+141- NumPy142- SciPy (for `beta` distribution and `minimize_scalar`)143144## Paper Reference145146Zandieh et al., "TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate,"147ICLR 2026. arXiv: 2504.19874.