Random-Rotation Quantization

A family of quantization schemes that compresses high-dimensional vectors (KV-cache entries, embeddings, attention keys) to 2–4 bits per coordinate with no calibration set, no per-block scale factors, and no training. The construction:

1. Apply a uniformly random orthogonal transform Π to the input vector.
2. Quantize each rotated coordinate independently against a fixed codebook designed once for the post-rotation marginal distribution.
3. At decode time, dequantize and apply Π⊤ to recover an approximation of the original vector.

The interesting property is that step 2's codebook is the same for every input. Production-quantization alternatives (GPTQ, AWQ, KIVI, KVQuant) store per-block scale + zero-point in full precision because real embeddings have outlier channels that a fixed grid either clips or wastes resolution on. The random rotation makes the outliers dissolve: after rotation, every coordinate of every input vector follows the same known distribution.

Why the rotation works

A uniformly random rotation in d dimensions sends any vector $\mathbf{x}$ to a uniform point on the sphere of radius $|\mathbf{x}|$. By rotational symmetry and the unit-sphere constraint $\sum_i X_i^2 = 1$, every coordinate of a unit sphere point has:

• mean 0
• standard deviation $1/\sqrt{d}$
• a known Beta marginal density: $f_X(x) = \dfrac{\Gamma(d/2)}{\sqrt{\pi},\Gamma((d-1)/2)},(1-x^2)^{(d-3)/2}$

This Beta density converges to $\mathcal{N}(0,,1/d)$ as d grows. At d = 1000, the standard deviation of any single coordinate is ~0.032, and the marginal is visually Gaussian by d ≈ 30. This is measure concentration — the core fact the construction exploits.

A practical rotation is the Randomized Hadamard Transform, which can be applied in $O(d \log d)$ time and approximates a uniform orthogonal transform well enough for the analysis.

The lineage

The construction was introduced in pieces:

• DRIVE (Vargaftik et al., NeurIPS 2021) — one-bit federated mean estimation. Sender rotates, sends signs of rotated coordinates plus a scale scalar. Two scale formulas: $S = |R(x)|_1 / d$ (MSE-optimal biased) and $S = |x|_2^2 / |R(x)|_1$ (unbiased).
• EDEN (Vargaftik et al., ICML 2022) — generalizes DRIVE to b bits per coordinate. Normalizes the rotated vector so each coordinate is approximately $\mathcal{N}(0,1)$, then quantizes with a Lloyd–Max codebook designed once for the standard normal. The 1-bit codebook is ${\pm\sqrt{2/\pi}} \approx {\pm 0.798}$; the 2-bit codebook is ${\pm 0.453, \pm 1.510}$.
• RaBitQ (Gao & Long, SIGMOD 2024) — independently develops the rotate-then-sign idea in the ANN search literature. The extended paper (Gao et al. 2024) proves asymptotic optimality against the Alon–Klartag bound for inner-product quantization.
• QJL (Zandieh et al. 2024) — one-bit DRIVE-style construction applied to attention key compression, with residual unbiasing.
• TurboQuant (Zandieh et al. 2025) — EDEN with the per-vector scale fixed to a constant, plus a residual chain (biased b−1-bit + unbiased 1-bit) and a KV-cache application framing.

The relationship between the DRIVE/EDEN line and the RaBitQ line is the subject of ongoing public discussion (arXiv 2604.18555 and 2604.19528, both 2026).

See interactive-turboquant for arkaung's visual walkthrough of the construction.

Three decoders, one rotation

The rotation is the shared encoder. The decoder is what changes by application:

• Mean decoder (DRIVE) — store signs + scalar; recover $\hat{\mathbf{x}} = S , \Pi^\top \mathrm{sign}(\Pi \mathbf{x})$, an unbiased estimate of $\mathbf{x}$.
• Inner-product decoder (RaBitQ, QJL) — store signs + norm; recover $\widehat{\langle q, x\rangle}$ from $\langle \Pi q, \mathrm{sign}(\Pi x)\rangle$ with a normalizing scalar. The right shape for nearest-neighbor retrieval and attention key compression.
• MSE decoder (EDEN, TurboQuant) — snap each $(\Pi x)_i$ to the nearest of $2^b$ Lloyd–Max centroids; recover $\tilde{\mathbf{x}}$ by applying $\Pi^\top$. The right shape for KV-cache compression.

Empirical result on KV cache

Needle-in-a-Haystack recall on Llama-3.1-8B-Instruct at 4× memory compression (TurboQuant paper Fig. 4):

TurboQuant matches full-precision recall at 4× compression. On LongBench-V1, TurboQuant at 3.5 bits per channel matches the full-precision average (50.06); at 2.5 bits per channel (6.4× compression) it stays within ~1% of full precision.

The bias-vs-unbias trade

MSE-optimal quantizers store the conditional mean of each codebook cell, which is smaller in magnitude than the cell's extremes. Reconstructed vectors are shrunken versions of the input, so inner products against reconstructions come out smaller than the true inner products. If you need unbiased inner products (which most retrieval applications do), you have to either correct the shrinkage analytically (TurboQuant-prod) or use a residual chain — quantize at b−1 bits with the biased MSE codebook, then quantize the residual at 1 bit with the unbiased sign code (TurboQuant's §7-8).

Practical use in llama.cpp

The llama-cpp-turboquant fork ships TurboQuant codebooks as KV-cache types: --cache-type-k turbo4 --cache-type-v turbo3. This is what the Reddit thread's GTX 1070 8GB setup uses to fit 128K context on 8 GB of VRAM — KV cost drops to ~590 MB at 131K vs ~720 MB on q4_0.

Standard llama.cpp ships q4_0 / q8_0 / f16 KV-cache types. TurboQuant is the next step on quality at the same byte budget; ik_llama is adding similar Q6-KV quantization through a different code path.

Cross-references

• interactive-turboquant — arkaung's visual walkthrough
• llm-quantization — survey of all the quantization families
• kv-cache-sizing — q8_0 vs q4_0 vs turbo4; the byte-budget axis
• reddit-qwen3-6-mtp-12gb — practitioner use of turbo4/turbo3
• mixture-of-experts — different kind of quantization concern (router sensitivity), separate from this line