TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate

Abstract

Vector quantization, a problem rooted in Shannon's source coding theory, aims to quantize high-dimensional Euclidean vectors while minimizing distortion in their geometric structure. We propose TurboQuant to address both mean-squared error (MSE) and inner product distortion, overcoming limitations of existing methods that fail to achieve optimal distortion rates. Our data-oblivious algorithms, suitable for online applications, achieve near-optimal distortion rates (within a small constant factor) across all bit-widths and dimensions. TurboQuant achieves this by randomly rotating input vectors, inducing a concentrated Beta distribution on coordinates, and leveraging the near-independence property of distinct coordinates in high dimensions to simply apply optimal scalar quantizers per each coordinate. Recognizing that MSE-optimal quantizers introduce bias in inner product estimation, we propose a two-stage approach: applying an MSE quantizer followed by a 1-bit Quantized JL (QJL) transform on the residual, resulting in an unbiased inner product quantizer. We also provide a formal proof of the information-theoretic lower bounds on best achievable distortion rate by any vector quantizer, demonstrating that TurboQuant closely matches these bounds, differing only by a small constant (≈ 2.7) factor. Experimental results validate our theoretical findings, showing that for KV cache quantization, we achieve absolute quality neutrality with 3.5 bits per channel and marginal quality degradation with 2.5 bits per channel. Furthermore, in nearest neighbor search tasks, our method outperforms existing product quantization techniques in recall while reducing indexing time to virtually zero.

DarcStar commentary

Our perspective on this work and how it informs our research — not part of the original paper.

This one sits squarely in territory we actively work in: compressing what a model has to keep in memory, with random rotations and Johnson–Lindenstrauss-style projections doing the heavy lifting. TurboQuant is by the author of the Quantized-JL transform and uses a 1-bit QJL step as one of its parts, so it's a mature entry in exactly the line of work that matters for keeping long-context models affordable.

Give it credit for the thing we value most: it doesn't just report a good compression ratio, it proves the floor. The paper derives the information-theoretic lower bound on distortion that any vector quantizer can achieve, then shows TurboQuant lands within a small constant (≈ 2.7×) of it. That's how a claim like this should be made — not “our quantizer is strong,” but “here's the best any quantizer can be, and here's how close we get.” A result measured against a proven bound is worth ten measured against a baseline.

The construction is clean in a way we appreciate. It's data-oblivious and online: randomly rotate the vector, which concentrates the coordinates into a Beta distribution and makes them near-independent, then apply an optimal scalar quantizer per coordinate — no training, no calibration pass. And there's a sharp detail we've had to reckon with in our own work on these methods: an MSE-optimal quantizer quietly biases inner-product estimates — the dot products attention actually consumes — so they add a second stage, a 1-bit QJL transform on the residual, to make the estimator unbiased. That's the correctness-in-the-seams work that separates a scheme that looks right from one that is.

It aims at a wall the rest of this shelf circles: KV cache is the memory bottleneck at long context, and reaching 2.5–3.5 bits per channel with near-neutral quality is real headroom — the same problem the distributed-memory work attacks from the other side.

Where we'd push is the usual place: the guarantee is on distortion — MSE and inner-product error — which is a proxy, not the prize. A tight bound on how far the vectors move is not yet a bound on how much the end task degrades; that last step still has to be measured under the real workload, not inferred from the distortion rate. But that's a margin note on a paper doing the hard part right — pairing a construction with the floor it's chasing.