TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate

A random rotation turns any vector into the same easy problem.

Compressing a high-dimensional vector to a couple of bits per number sounds like it should need a model of your data. TurboQuant uses none. One random rotation makes every input look the same, and a fixed per-coordinate quantizer lands within a small constant of the information-theoretic best.

Compress a high-dimensional vector to a couple of bits per number, with no training and no look at the data first, and a single random rotation still lands you near the theoretical best.

Modern AI runs on vectors. A language model's key/value cache is a pile of them, one per token per layer, growing without bound as the context gets longer. A vector database is millions or billions of them, sitting in memory waiting to be searched. Every one of those vectors is a list of floating-point numbers, sixteen or thirty-two bits each, and the bill comes due twice: in the memory to store them and in the time to move them between fast and slow memory on an accelerator. You can spend fewer bits per number, but throwing away bits throws away accuracy, and you kept those vectors precisely because their geometry, their lengths and the angles between them, carried the answer.

TurboQuant, from Google Research, DeepMind, and NYU, spends those bits close to the information-theoretic limit. It compresses each coordinate to a handful of bits while provably staying within a small constant factor of the least distortion any scheme could achieve, at every bit budget. And it does this online: no training pass, no calibration on your data, a fixed recipe you apply the instant a vector arrives. The argument is short and mostly geometric: a random rotation removes the hard case, a fixed per-coordinate quantizer is solved once, and inner products take one extra stage.

Storing a vector in a few bits

Pin the goal down precisely first. We have a $d$-dimensional vector $\mathbf{x}$ and a budget of $b$ bits per coordinate, the bit-width. A quantizer is a pair of maps: an encoder $Q$ that turns $\mathbf{x}$ into a short binary code, and a decoder $Q^{-1}$ that turns the code back into a reconstructed vector $\tilde{\mathbf{x}}$. The reconstruction is never exact (you spent fewer bits than the original floats held), so the only question is how much you lose. The paper tracks two different losses, because the two things people do with these vectors care about different errors.

The first is plain reconstruction error, the mean-squared error (MSE): how far the reconstructed vector sits from the original, squared and averaged over the quantizer's own randomness.

The second is about inner products. Most of what these vectors are for is dot products: attention scores a query against every key by their inner product, and a similarity search ranks database vectors by their inner product with the query. So what you really want preserved is $\langle \mathbf{y}, \mathbf{x}\rangle$ for a query $\mathbf{y}$, even after $\mathbf{x}$ has been crushed to a few bits:

And for inner products there is a second, sharper demand than being close. The estimate should be unbiased: averaged over the quantizer's randomness, it should equal the truth exactly, with no systematic tilt.

Unbiasedness matters when you sum or average many estimates, which is exactly what a search or an attention head does. A small random error in each term washes out across the sum; a small bias in each term, all pointing the same way, accumulates instead of cancelling, and shifts every score by the same amount. Because of that distinction, the paper needs two algorithms instead of one.

Two constraints define the problem. First, no assumptions about the data: the vector $\mathbf{x}$ is worst-case, an adversary's choice, not a draw from some friendly distribution. Second, and this is the constraint that rules out most prior work, the quantizer must be data-oblivious, also called online. It cannot study your dataset first. Why insist on that? Because the alternative, a data-dependent quantizer that learns a codebook from your vectors (the standard move, usually k-means), needs a slow preprocessing pass and falls apart the moment the data shifts, which for a streaming KV cache is every single token. A data-oblivious quantizer applies the same fixed map to whatever arrives, instantly, so it can ride along with generation. In exchange, it has to be good against the worst case, with no chance to adapt. TurboQuant meets that worst case with a single matrix multiply.

Rotate the worst case away

A worst-case vector causes a concrete problem. Suppose $\mathbf{x}$ is a spike: one coordinate near 1, the rest near 0. A per-coordinate quantizer that spends its bits assuming values are spread out will waste almost all of them on the zeros and badly mangle the one coordinate that mattered. Some other input might be spread evenly. There is no single fixed per-coordinate scheme that is good for both, because the inputs don't agree on what a typical coordinate looks like.

There is one step: multiply $\mathbf{x}$ by a random rotation $\boldsymbol{\Pi}$ before quantizing. A random rotation is an orthogonal matrix drawn uniformly (you build one by taking the QR decomposition of a matrix of i.i.d. Gaussians, exactly as the paper does). Rotation preserves all the geometry that matters, every length and every angle, so it changes nothing about the inner products we are trying to keep. What it changes is the coordinates. Whatever $\mathbf{x}$ looked like, the rotated vector $\boldsymbol{\Pi}\mathbf{x}$ is a uniformly random point on the sphere of the same radius, and a uniformly random point has no special coordinates at all. The spike is gone, smeared evenly across all $d$ directions. One matrix multiply converts every worst-case input into the same average-case input, so one fixed quantizer can be near-optimal for all of them, and a data-oblivious scheme works.

And the resulting coordinates are not merely spread out vaguely; they follow an exact, known law. For a unit vector, each coordinate of $\boldsymbol{\Pi}\mathbf{x}$ has the density

which is a (rescaled) Beta distribution, and the derivation is one line of geometry: a point at coordinate value $x$ on the unit sphere lives on a sub-sphere of radius $\sqrt{1-x^2}$ in one lower dimension, so the density is the surface area of that sub-sphere, which is where the $(1-x^2)^{(d-3)/2}$ comes from. In high dimensions this bell concentrates and converges to a Gaussian $\mathcal{N}(0, 1/d)$: mean zero (the coordinates of a sphere point are symmetric about zero, so a coordinate is as likely positive as negative), variance $1/d$ (the $d$ coordinate-squares are symmetric and sum to 1, so each averages $1/d$).

Figure 1 shows it. For any input shape, a spike, a few spikes, a ramp, the coordinates after a real random rotation follow the same bell, no matter what went in, and raising the dimension sharpens that bell toward the Gaussian. The histogram tracks the curve regardless of the input.

One caveat matters for the per-coordinate quantization: in high dimensions, distinct coordinates of a sphere point become nearly independent, not merely spread the same way. That is a real theorem, the Diaconis-Freedman result that the first few coordinates of a high-dimensional sphere point look like independent Gaussians, though it is a high-dimensional approximation, tightest when you look at far fewer coordinates than the dimension. Independence allows the coordinates to be quantized one at a time and still be near-optimal overall.

Quantize one number at a time

Near-independence collapses a hard $d$-dimensional problem into the same easy one-dimensional problem, repeated $d$ times. Each coordinate is a draw from the bell $f_X$; quantize it on its own and add up the errors. The design reduces to one question. Given the bell and a budget of $b$ bits, where do you put the $2^b$ reconstruction values, the code pointsor centroids, to minimize squared error?

This is a standard problem, solved by the Lloyd-Max quantizer, one-dimensional $k$-means. Its solution obeys two conditions that lock together. Each value should map to its nearest code point, so the cells are intervals split at the midpoints between neighbouring centroids (a Voronoi partition of the line). And each code point should sit at the mean of its cell, because the mean is the value that minimizes squared error within the cell. Written as the optimization the paper solves once and stores:

Because the bell is the same for every coordinate and every input, this is solved once, offline, for each bit-width $b$, and the resulting code points are baked into a tiny lookup table. Quantizing is then two steps: rotate, then for each coordinate find the nearest table entry. No per-data work, and it vectorizes cleanly on a GPU, so it runs efficiently on an accelerator.

The simplest case is the one-bit quantizer: at $b=1$ you get a single bit per number: two code points, and by symmetry they sit at $\pm\sqrt{2/\pi}$ times the coordinate's scale (the average magnitude of a Gaussian is $\sqrt{2/\pi}$). One bit keeps only the sign of each rotated coordinate and a fixed magnitude. Even that recovers most of the vector: the per-vector MSE at one bit is $1 - 2/\pi \approx 0.36$ of the vector's squared length, so the reconstruction keeps the other 64%. As $b$ rises the cells multiply and the error falls.

# TurboQuant (MSE): quantize unit vector x to b bits / coordinate
Pi   = random_rotation(d)         # QR of a Gaussian matrix; fixed, shared
y    = Pi @ x                     # now every coordinate ~ N(0, 1/d)
idx  = nearest(y, codebook[b])    # Lloyd-Max table, precomputed once
# dequantize: look up the centroids, rotate back to the original basis
x_hat = Pi.T @ codebook[b][idx]   # idx is b bits per coordinate

That is the MSE quantizer end to end: a shared random rotation, a precomputed codebook, a nearest-neighbour lookup per coordinate, and the transpose rotation to decode. The open question is how close to optimal it is.

How close to optimal?

Adding up the per-coordinate errors gives the vector's total distortion, $D_{\tt mse} = d\cdot\mathcal{C}(f_X, b)$, and the paper bounds it in closed form. For larger bit-widths the classical high-resolution (Panter-Dite) formula for a Gaussian-shaped source gives the clean result:

The shape of that bound matters. The distortion falls like $1/4^b$, so every extra bit divides the error by four. The factor is four rather than two because one more bit halves the width of every cell, and squared error scales with width squared, so halving the width quarters the error. Four bits per number already drives the reconstruction error below 1% of the vector's squared length.

A small error is only part of the claim. The rest is that you cannot do meaningfully better with any quantizer. The Shannon Lower Bound, the rate-distortion floor from information theory, says that at $b$ bits per coordinate no scheme on this sphere can beat

TurboQuant reaches at most $\frac{\sqrt{3}\pi}{2}\cdot\frac{1}{4^b}$; nothing can beat $\frac{1}{4^b}$. The gap is the constant $\sqrt{3}\pi/2 \approx 2.7$, the same at every bit-width. So this fixed, training-free, one-rotation-and-a-lookup scheme is never worse than $2.7\times$ the unbeatable optimum, and at one bit, where the bound is sharpest, only $1.45\times$. The figure plots both bounds on a log scale, where the constant gap is a fixed vertical offset between two parallel lines, and drops TurboQuant's actual distortion between them.

This is the "near-optimal distortion rate" in the title, and it is the part that was open. Data-oblivious methods used to pay for their convenience with much looser bounds; TurboQuant gets the convenience and the near-optimal rate at once. Two caveats apply: the clean $1/4^b$ floor and the Gaussian-shaped bound are both high-dimensional limits (at finite $d$ the coordinate bell is exactly Beta, only approximately Gaussian), so "within $2.7\times$" is an asymptotic statement, not a finite-size equality. It matches experiment closely all the same.

Inner products need a second stage

Everything so far minimizes reconstruction error. A vector that is close in MSE does give close inner products, but not unbiased ones, and bias is the error that accumulates across a sum. The problem is clearest at one bit, where the MSE quantizer keeps only the sign: $Q_{\tt mse}(\mathbf{x}) = \mathrm{sign}(\boldsymbol{\Pi}\mathbf{x})$ and decodes to $\sqrt{2/(\pi d)}\,\boldsymbol{\Pi}^{\!\top}\mathrm{sign}(\boldsymbol{\Pi}\mathbf{x})$. The expected inner product of that reconstruction with a query is:

The estimate is systematically too small, shrunk by $2/\pi$. The shrinkage traces back to exactly the property MSE optimizes for: a Lloyd-Max code point is the mean of its cell, the conditional average of the values that land there, and an average is pulled in from the extremes toward the center. Replacing each coordinate by its cell-mean keeps the direction but systematically underestimates the magnitude. The shrinkage has an exact form at every bit-width. Because the optimal reconstruction is the mean of its cell, the quantization error is orthogonal to the code, so the expected product of a coordinate and its code equals the code's variance, which is the coordinate's variance minus the MSE. With unit-variance coordinates that makes the slope exactly $\alpha(b) = 1 - D_{\tt mse}(b)$, and the bias is whatever the MSE threw away. At one bit $\alpha = 1 - 0.36 = 2/\pi$; by four bits $\alpha = 0.99$ and the bias is nearly gone. The figure shows the amber estimates lying along that shallow line, fanning further below the diagonal as the true inner product grows, which is the bias accumulating.

TurboQuant pays for the bias directly, with a separate one-bit tool built for inner products. That tool is QJL, the Quantized Johnson-Lindenstrauss transform (by two of the same authors). It sketches a vector, builds a tiny lossy summary that still answers an inner-product query, against random Gaussian directions, the rows of a matrix $\mathbf{S}$, and keeps only the sign of each projection, $Q_{\tt qjl}(\mathbf{x}) = \mathrm{sign}(\mathbf{S}\mathbf{x})$; each row produces one sign bit, so the sketch costs one bit per direction. It then decodes with a precise scale:

That $\sqrt{\pi/2}$ is the exact inverse of the $\sqrt{2/\pi}$ shrinkage a sign introduces, so it cancels the bias and leaves an unbiased estimator. QJL is unbiased but noisy (a single bit per direction carries little information), with variance $\frac{\pi}{2d}\lVert\mathbf{y}\rVert^2$. Using QJL alone is unbiased but high-variance; using MSE alone is low-variance but biased. TurboQuant's inner-product quantizer combines them in two stages.

Stage one: run the MSE quantizer, but at $b-1$ bits, saving one bit from the budget. This captures the bulk of $\mathbf{x}$ cheaply and accurately, and what it misses is a small residual $\mathbf{r} = \mathbf{x} - Q_{\tt mse}^{-1}(Q_{\tt mse}(\mathbf{x}))$, a vector with small norm. Stage two: spend the last bit applying QJL to that residual. The estimate adds the two pieces:

The sum is unbiased because the second term's expectation is exactly the piece the first term dropped. QJL is unbiased on the residual, so on average the second term equals $\langle\mathbf{y}, \mathbf{r}\rangle$, the missing piece, and the two add back to the whole:

The biased main term plus the unbiased correction of its own leftover is unbiased. And because QJL's variance scales with the norm of what it sketches, and the residual's norm is small, the noise it adds is small too: the inner-product distortion comes out to $D_{\tt prod} = \frac{\pi}{2d}\lVert\mathbf{y}\rVert^2\,D_{\tt mse}(b-1)$, which, for a unit-norm query, lands at $1.57/d,\, 0.56/d,\, 0.18/d,\, 0.047/d$ for $b=1,2,3,4$ and again sits within a small constant of the inner-product lower bound.

# Inner-product TurboQuant: unbiased, b bits / coordinate
idx   = quant_mse(x, bits = b - 1)         # coarse code (b-1 bits)
r     = x - dequant_mse(idx)               # leftover residual, small norm
signs = sign(S @ r)                        # sign ignores scale: sketches r/||r||
store  = (idx, signs, norm(r))             # (b-1) + 1 bits + one scalar

# estimate <y, x> from the stored code:
est_mse = dot(y, dequant_mse(idx))
est_qjl = norm(r) * (sqrt(pi / 2) / d) * dot(y, S.T @ signs)
est     = est_mse + est_qjl                # unbiased: E[est] = <y, x>

The two algorithms share one core. For small reconstruction error, use the MSE quantizer; for unbiased inner products, spend one bit on a QJL correction to its residual and the bias is gone.

What it buys

The theory gives near-optimal distortion at any bit-width with no preprocessing. The experiments test it in the two places these vectors actually live.

The KV cache. A decoder model stores a key and value vector for every past token; at long context that cache dominates memory and the cost of moving it dominates latency. Quantizing it has to be online (tokens stream in one at a time) and has to preserve inner products (attention is a softmax over query-key dot products), both of which TurboQuant handles. On the needle-in-a-haystack test, hide one fact in a long document and ask the model to retrieve it, Llama-3.1-8B scores 0.997 out of a perfect 1.0 even with the cache squeezed to a quarter of its size ($4\times$, about 4 bits per number), matching the uncompressed model, while methods without distortion guarantees lose tokens and degrade recall. On the broader LongBench-E suite quality survives down to roughly 2.5 bits per channel (a channel is one coordinate of the per-token vector), effectively lossless by 3.5 bits, using a small twist: a handful of high-magnitude "outlier" channels are kept at higher precision and the rest lower, averaging to the target budget (for a clean 2.5-bit head, 64 of the 128 channels at 3 bits and 64 at 2). This delivers long-context quality at a quarter to a sixth of the KV-cache memory.

Nearest-neighbour search. A vector database compresses its vectors with "product quantization" (PQ), which learns a k-means codebook over the dataset, and RaBitQ, a recent binary scheme with guarantees. Both spend real time building an index: PQ runs k-means, RaBitQ does heavier per-vector work with no GPU-friendly kernel. TurboQuant has no codebook to learn, so its indexing is a rotation and a lookup, and the timing gap is large. The figure shows quantization time on a log scale, because otherwise TurboQuant's bar would be invisible: tens of thousands of times faster than the baselines, and it still wins on recall.

The rotation enables everything else. Once every input is a uniform point on the sphere, every coordinate obeys the same bell, and the optimal scalar quantizer for that bell is solved once and read from a table, landing within $2.7\times$ of the information-theoretic floor at every bit-width. The inner-product case needs the one extra repair: MSE-optimal codes shrink dot products by a fixed factor, and a one-bit QJL sketch of the leftover residual adds back exactly what was shrunk away. It needs no training, no calibration, and no codebook, relying only on the geometry the vectors already carry.