Spin first, quantize later: how TurboQuant gets nearly-optimal vector compression for free

A 2025 paper from Google Research walks the long path back to a beautifully simple idea — rotate your vectors at random before you compress them, and the math gets a lot easier. The result is a quantizer that is information-theoretically near-optimal, runs online, and compresses LLM caches by 5× with no measurable quality loss.

Original paper: Zandieh, Daliri, Hadian, Mirrokni. TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate. arXiv:2504.19874 (April 28, 2025). https://arxiv.org/abs/2504.19874

@misc{zandieh2025turboquantonlinevectorquantization,
      title={TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate},
      author={Amir Zandieh and Majid Daliri and Majid Hadian and Vahab Mirrokni},
      year={2025},
      eprint={2504.19874},
      archivePrefix={arXiv},
      primaryClass={cs.LG},
      url={https://arxiv.org/abs/2504.19874},
}

I want to walk through this paper in plain English, keeping every equation that matters, and explaining each one carefully enough that a reader who hasn't held a math textbook in a decade can still follow what's happening. The ideas are good ones; they deserve to land somewhere wider than the people who already know how to parse Lloyd-Max quantization on sight.

What the paper is solving

Modern AI systems run on vectors. Every word, every token, every paragraph an embedding model has ever seen gets turned into a list of numbers — typically 768, 1536, or 4096 of them. These lists, called embeddings, are how the system represents meaning. A nearest-neighbor search looks for vectors that are close to each other; an LLM's attention mechanism multiplies vectors against vectors. They're the lingua franca of the field.

The trouble is that there are a lot of them. A modern LLM holds tens of millions of these vectors in its KV cache during a long conversation. A vector database for a search engine might store billions. At 4 bytes per number times 1536 numbers per vector times a billion vectors, you're looking at six terabytes just to store them once. Doing math against them at that scale is even more expensive.

The natural response is to compress. Replace each 32-bit floating point number in the vector with something much smaller — say, 4 bits, or 2 bits, or even 1 bit. The question is which small thing to replace it with so that the compressed vector still behaves almost like the original when you do math against it.

This is vector quantization, and it has been studied for sixty years. What the TurboQuant paper does is take a method that's been quietly known to information theorists for decades and show that — for the specific shape of the problem that AI workloads produce — it's not just good, it's nearly optimal. And the algorithm is so simple it fits on a napkin.

The classical problem: it's hard to know where to put the bins

Imagine you have a list of 1536 numbers, each one some real value between, say, $-1$ and $+1$. You want to compress each number down to 4 bits, which means each compressed number can take only one of $2^4 = 16$ values. You need to pick those 16 values — call them $c_1, c_2, \ldots, c_{16}$, the centroids — such that when you replace each original number with its closest centroid, you lose as little information as possible.

The thing that makes this hard is that the optimal choice of centroids depends entirely on how the numbers are distributed. If most of your numbers cluster near zero, you want most of your 16 bins concentrated near zero too — wasting bins on the tails would mean the bins near zero are too coarse, and most numbers get rounded badly. If your numbers are uniformly spread across the range, then evenly-spaced bins are best.

The technical name for "the smallest possible reconstruction error you can achieve given the distribution" is the distortion-rate function, and the classic algorithm to find the optimal bins for a known distribution is Lloyd-Max iteration. It works, but it has a catch: you have to know what the distribution looks like before you can pick your bins. If the data shifts, your bins are wrong. If you don't know the data ahead of time — e.g. an LLM serving requests it has never seen — Lloyd-Max can't help you in real time.

This is the cliff that earlier methods like Product Quantization (PQ) and RabitQ fall off. PQ trains its bins on a representative sample, which means it has to be retrained when the distribution drifts. RabitQ is more clever but still has heavy per-vector preprocessing.

TurboQuant's trick: rotate first, and the data becomes predictable

Here is the core insight, and it's the kind of insight that, once you see it, feels almost unfair:

If you rotate your vector by a uniformly random rotation before quantizing, every coordinate of the rotated vector follows the same distribution — and that distribution is well-known and well-behaved.

The rotation doesn't change the geometry of the vectors relative to each other. Two vectors that were close before the rotation are still close after; two that were orthogonal stay orthogonal. So we lose no information by rotating.

What we gain is that no matter what bizarre distribution the original data had, the rotated coordinates are guaranteed to look the same way every time. The paper makes this concrete:

"For any $j \in [d]$ the coordinate $x_j$ follows the (scaled/shifted) Beta distribution: $$f_X(x) := \frac{\Gamma(d/2)}{\sqrt{\pi}\cdot\Gamma((d-1)/2)} \cdot (1-x^2)^{(d-3)/2}$$ *In high dimensions this Beta distribution converges to the normal distribution $\mathcal{N}(0, 1/d)$."*

That looks intimidating. Let me unpack what each piece is doing.

The function $f_X(x)$ is a probability density — for any value $x$ between $-1$ and $+1$, it tells you how likely a random rotated coordinate is to land near that value. The fraction $\Gamma(d/2) \,/\, (\sqrt{\pi} \cdot \Gamma((d-1)/2))$ is just a normalizing constant whose only job is to make the area under the curve equal to 1 (so it's a valid probability density). The $\Gamma$ is Euler's gamma function, which is a generalization of factorial; you can ignore the specifics — it's a number that depends only on the dimension $d$.

The shape of the curve is controlled by $(1 - x^2)^{(d-3)/2}$. When $x = 0$ this term equals 1, which is its maximum. When $|x| = 1$ this term equals 0. So the density is peaked in the middle and drops to zero at the edges. The exponent $(d-3)/2$ controls how sharply it peaks — for our typical AI dimensions like $d = 1536$, that exponent is about $766$, which makes the peak extraordinarily sharp.

The second sentence — "in high dimensions this Beta distribution converges to the normal distribution $\mathcal{N}(0, 1/d)$" — is the punchline of the rotation trick. It says: once you've rotated your vector in 1536 dimensions, every single coordinate behaves as if it were drawn from a Gaussian bell curve centered at zero with standard deviation $1/\sqrt{1536} \approx 0.025$. Predictable. Concentrated. Identical for every coordinate. Identical regardless of what the original vector looked like.

This is the gift that makes everything else possible. We can now precompute the optimal Lloyd-Max bins for that one Gaussian and use them on every coordinate of every rotated vector forever.

The optimal scalar quantizer

Once we know our rotated coordinates follow this concentrated Beta distribution, picking the bins is a one-time offline computation. The paper writes the objective as:

In English: among all possible choices of centroids $c_1 < c_2 < \cdots < c_{2^b}$, find the choice that minimizes the total expected squared error when each value $x$ is replaced by its nearest centroid. The integral $\int_{R_i} \cdots dx$ is the contribution from the $i$-th bin; $|x - c_i|^2$ is the squared distance from $x$ to its assigned centroid; $f_X(x)$ is the probability of $x$ — so we're weighting the error by how often it happens.

This optimization is the classical Lloyd-Max problem, and for a fixed distribution it has a unique optimum that can be computed by alternating between "given the centroids, pick the boundaries" and "given the boundaries, pick the centroids." For 1, 2, 3, and 4 bits per coordinate, the authors precompute the optimal centroids once, ship them as a lookup table, and that table is the entire learned state of the algorithm. Every vector everywhere from now on uses the same 16 centroids (for 4 bits) regardless of where it came from.

That's why the algorithm is data-oblivious and online — there's no training, no warmup, no distribution-fitting. A new vector arrives, you rotate it, you bin each coordinate to its nearest precomputed centroid, you write down the bin index. Done.

How well does it actually compress?

The paper proves a clean upper bound on the reconstruction error. After quantization with $b$ bits per coordinate, the mean-squared error per coordinate is bounded by:

The $\sqrt{3}\pi/2$ is just a constant — about $2.72$. The really important factor is $1/4^b$. Each additional bit of precision reduces the error by a factor of 4. So:

These numbers are normalized — they tell you the error as a fraction of the original vector's magnitude squared. At 4 bits per coordinate, the average error is less than 1% of the signal — which means a vector compressed to 4 bits per number is essentially indistinguishable from the original for most practical purposes.

For a 1536-dimensional vector at 4 bits per coordinate, that's $1536 \times 4 = 6144$ bits per vector, or 768 bytes — compared to the original 6144 bytes (1536 numbers × 4 bytes/number). 8× compression with under 1% reconstruction error. Without any training data, without any per-vector tuning, online and oblivious.

The inner-product fix: a two-stage trick

There's a subtle problem with using MSE-optimal quantization for AI workloads. Most of what AI systems do with vectors isn't reconstruct them — it's compute inner products between them. Attention is an inner product. Nearest-neighbor search ranks by inner product. The actual quantity you care about is $\langle x, y \rangle$ where $x$ has been quantized and $y$ might or might not be.

If you naively use the MSE-optimal quantizer, the inner product estimate $\langle Q^{-1}(Q(x)), y \rangle$ is biased. On average it's slightly off — sometimes consistently too high, sometimes too low, depending on the data. For ranking-style queries that often doesn't matter; for arithmetic-style queries (compute the attention output and feed it to the next layer) it's a problem.

The TurboQuant fix is elegant. Apply the MSE quantizer at $b - 1$ bits — keeping one bit of budget in reserve. Then look at the residual $r = x - Q^{-1}(Q(x))$ — the part the MSE quantizer didn't capture — and apply a separate compression scheme called Quantized Johnson-Lindenstrauss (QJL) to it, using the saved bit. Glue everything back together as:

The first piece is the main quantization. The second is a 1-bit-per-coordinate sketch of the leftover. The third is a single scalar — the magnitude of the residual — that lets you renormalize when you decode.

The clever bit is that the Quantized JL transform happens to be unbiased in expectation — the QJL sketch's inner-product estimate is correct on average. So the compound estimator $\langle Q_{\text{mse}}^{-1}(Q_{\text{mse}}(x)), y \rangle + \|r\|_2 \cdot \langle Q_{\text{qjl}}^{-1}(Q_{\text{qjl}}(r)), y \rangle$ has zero bias, and the squared error is bounded by:

The $\|y\|_2^2 / d$ is the variance of $y$'s coordinates after rotation — small for high-dimensional vectors. The $1/4^b$ factor is the usual exponential improvement per bit. So you get unbiased inner-product estimates with the same exponential bit-precision scaling as the MSE quantizer, at the cost of one extra bit out of your bit budget. A surprisingly cheap fix.

How close to "perfect" is "near-optimal"?

The paper does the full information-theoretic homework, proving that no quantizer can do better than this by more than a constant factor. Specifically:

Theorem 3. For any randomized quantizer $Q: \mathbb{S}^{d-1} \to \{0,1\}^{b \cdot d}$: $$D_{\text{mse}}(Q) \ge \frac{1}{4^b}, \quad D_{\text{prod}}(Q) \ge \frac{1}{d \cdot 4^b}$$

In English: the universe sets a floor at $1/4^b$. Nothing can do better than that by more than the constant. TurboQuant comes within roughly a factor of 2.7 of that floor (and at low bit rates, only 1.45× — the gap closes as you compress harder). For an algorithm with no training, no tuning, no data-fitting, that's about as close to "free lunch" as information theory allows.

This is what makes the paper notable: most quantizers in the literature have asymptotic guarantees that hide arbitrary constants, or work only in some restricted regime. TurboQuant has tight non-asymptotic bounds that match the lower bound to within a small constant for every bit-width that matters.

What it does in real systems

The experimental section earns the algorithm its name. Two workloads are tested:

KV cache compression for LLMs. When a large language model processes a long conversation, it caches the keys and values from earlier tokens so it doesn't have to recompute them. This cache grows linearly with context length, and at million-token contexts it dominates GPU memory. TurboQuant compresses it by 5× at 3.5 bits per channel without any measurable quality drop on long-context retrieval tasks (needle-in-a-haystack benchmarks score perfectly). At 2.5 bits per channel — a 6.4× compression — the degradation is "marginal," meaning small enough to be tolerable for many applications.

That 5× compression is the difference between a model that runs on one GPU and a model that requires five. For inference cost, that's the difference between profitable and not.

Approximate nearest-neighbor search. On standard embedding benchmarks (DBpedia at 1536 and 3072 dimensions, GloVe at 200 dimensions), TurboQuant beats both Product Quantization and RabitQ on recall@k — the percentage of true nearest neighbors found in the top-$k$ results. The training time comparison is the kicker: where PQ takes between 37 seconds and 66 minutes to train its codebooks on the dataset, TurboQuant takes between 0.0007 and 0.0021 seconds — essentially instant, because there's nothing to train. Just rotate and bin.

For a vector database serving billions of vectors with continuously updating data, "no training time" is an order-of-magnitude operational simplification. A new dataset doesn't need a fitting pass; new vectors don't need to be added to an evolving codebook; concept drift isn't a problem because the algorithm doesn't depend on the concept distribution at all.

What it doesn't do, and what's still open

The paper is candid about the limits. Random rotation in $d$ dimensions costs $O(d^2)$ time per vector if done naively, which can be prohibitive for very high-dimensional vectors. The authors recommend using structured rotations like the Subsampled Randomized Hadamard Transform (SRHT), which run in $O(d \log d)$ and behave almost like a true random rotation in practice — but the theoretical guarantees are slightly weaker, and the gap between theory and practice for SRHT-based versions is something the field is still working out.

The paper also focuses on inner-product and reconstruction objectives. For workloads that care about other distances — Hamming, KL divergence, edit distance — the random rotation trick doesn't directly help, and the "predictable distribution" gift evaporates.

And one philosophical limit worth noting: the algorithm is information-theoretically near-optimal in the data-oblivious regime. If you're willing to spend training time studying a particular dataset's structure — and many production systems are — you can in principle beat TurboQuant by exploiting that structure. The paper's claim is that the cost of being data-oblivious is small (a factor of 2.7×, fixed) compared to the benefit (no training, no drift, online deployment). For large parts of the AI infrastructure stack, that's the right trade.

Why I find this paper worth a long read

There's a recurring pattern in the parts of mathematics that turn out to be useful: a problem that looks impossibly data-dependent can become trivial if you change the basis you're looking at it in. Fourier transforms work because periodic data is sparse in the frequency basis. Compressed sensing works because natural signals are sparse in some basis you can find by random projection. TurboQuant works because data on the high-dimensional sphere is uniform-on-the-sphere in every basis if you spin first, and uniformity is the easiest distribution to quantize against.

It's the same idea three times. It works each time. And the practical consequence — a 5× compression of LLM KV caches with no quality loss, no training, no per-deployment tuning — is the kind of result that quietly makes a difference in how this stuff actually runs in production. Worth reading the paper end-to-end if you have the appetite; the proofs are unusually clean for an information-theory paper, and the experimental section has more receipts than most theoretical works.

For now, my own takeaway is that random rotation as a first preprocessing step before any quantization is approximately free advice. If your system is doing approximate nearest neighbor search, attention with KV cache compression, or any other workload where vectors live on a high-dimensional sphere and get compressed, you can probably get a meaningful quality improvement for almost no engineering cost just by adding a rotation matrix to the front of your existing pipeline. The TurboQuant paper is the rigorous justification for an idea that, in retrospect, feels like it should always have been the default.