A random rotation turns vector quantization into a solved problem, within a factor of 2.7 of perfection

Large language models, vector databases, and nearest neighbor search systems all share a common bottleneck: they must store and compute with enormous collections of high-dimensional vectors. The key-value cache in transformer models grows linearly with context length. Vector databases hold millions of embeddings. In both cases, reducing those vectors from 16-bit or 32-bit floating point down to 2, 3, or 4 bits per coordinate would save memory, bandwidth, and compute.

The trouble is that most existing quantization methods either require expensive data-dependent preprocessing (making them useless for online settings like KV cache quantization, where new vectors arrive continuously) or achieve distortion rates that are far worse than what information theory says is possible. TurboQuant solves both problems simultaneously: it is data-oblivious, works in streaming mode, runs on GPUs with full vectorization, and comes within a small constant factor of the theoretical optimum.

The core insight is deceptively simple. Multiply your input vector by a random rotation matrix. After rotation, each coordinate of a unit-norm vector follows a Beta distribution that, in high dimensions, concentrates tightly around a Gaussian. Better still, distinct coordinates become nearly independent of one another. This near-independence is the crucial property: it means you can quantize each coordinate separately using an optimal scalar quantizer and still get near-optimal performance for the whole vector.

The optimal scalar quantizers are found by solving a one-dimensional k-means problem (the Lloyd-Max algorithm) for the known Beta distribution. These codebooks are precomputed once for each bit-width and stored as a small lookup table. At runtime, the algorithm rotates the vector, finds the nearest codebook entry for each coordinate, and stores the index. Dequantization reverses the process: look up centroids, rotate back.

TurboQuant operates in two stages to handle both MSE and inner product distortion:

1. MSE-optimal quantizationRandomly rotate the input vector, then apply a precomputed Lloyd-Max scalar quantizer to each coordinate independently. This minimizes mean-squared reconstruction error with a distortion of at most (√3π/2) · 4^(-b) for bit-width b.
2. Residual correction via QJLMSE-optimal quantizers are biased for inner product estimation (at 1-bit, the multiplicative bias is 2/π). To fix this, apply the MSE quantizer at bit-width b-1, compute the residual, then apply a 1-bit Quantized Johnson-Lindenstrauss (QJL) transform to the residual. The result is an unbiased inner product estimator at the full b-bit budget.

The paper provides a formal information-theoretic lower bound: no randomized quantization algorithm mapping unit-norm vectors in d dimensions to b·d bits can achieve MSE distortion below 1/4^b. TurboQuant's upper bound is (√3π/2) · 1/4^b, making the gap a factor of roughly 2.7. At low bit-widths the gap shrinks further: at b=1, TurboQuant is only 1.45× away from optimal.

The lower bound proof is elegant. It uses Yao's minimax principle to convert the worst-case-input, randomized-algorithm problem into a randomized-input, deterministic-algorithm problem, then applies Shannon's distortion-rate function for uniform distributions on the hypersphere. The inner product lower bound follows by a pigeonhole argument over coordinates. These bounds hold for any compression scheme whatsoever, not just scalar quantizers.

On KV cache quantization with Llama-3.1-8B-Instruct, TurboQuant at 3.5 bits per channel scores 50.06 on LongBench, identical to the full 16-bit cache. At 2.5 bits it scores 49.44, a marginal drop that still beats KIVI at 3 bits (48.50) and PolarQuant at 3.9 bits (49.78). On the Needle-in-a-Haystack test, TurboQuant achieves a perfect 0.997 recall score across context lengths from 4k to 104k tokens, matching the uncompressed model exactly.

For nearest neighbor search, TurboQuant consistently outperforms both Product Quantization and RabitQ in recall across three datasets (GloVe at d=200, OpenAI embeddings at d=1536 and d=3072) at both 2-bit and 4-bit precision. The speed advantage is even more dramatic: quantizing 100,000 vectors at 4 bits in 3072 dimensions takes 494 seconds for PQ, 3957 seconds for RabitQ, and 0.002 seconds for TurboQuant. That is not a typo.

The Ministral-7B-Instruct results confirm generality. At 2.5 bits TurboQuant scores 49.62 on LongBench, compared to 49.89 for the full 16-bit cache. Compressing by more than 6× for a 0.27-point drop is a trade most practitioners would take happily.

The KV cache is one of the sharpest bottlenecks in serving long-context language models. It scales with both model depth and sequence length, consuming memory that could otherwise allow larger batches or longer contexts. Methods that require calibration data or per-layer Hessian computation are impractical when tokens arrive one at a time during generation. TurboQuant applies instantly, with no data-specific tuning, making it directly compatible with online, streaming inference.

The combination of provable optimality, zero preprocessing, and GPU-friendly vectorized operations puts TurboQuant in a rare position: it is both theoretically satisfying and practically deployable. The two-stage design that bolts an MSE-optimal quantizer onto a QJL residual correction is a clean architectural pattern, and the information-theoretic lower bounds confirm there is not much room left for improvement. At 3.5 bits per channel, you get the full-precision model's quality. At 2.5 bits, you get almost all of it. The search for better vector quantizers at these bit-widths is, for practical purposes, done.