Quantization & Compression2025

TurBoQuant

Online Vector Quantization with Near-Optimal Distortion Rate

Amir Zandieh, Majid Daliri, Majid Hadian, Vahab Mirrokni

Paper Overview

TurBoQuant is a training-free, data-oblivious vector quantization method that achieves near-optimal compression for high-dimensional vectors — the first method to deliver zero quantization overhead at any target bit width. It tackles a fundamental problem in deploying large language models: the KV cache, which stores all previous key-value pairs during autoregressive generation, grows linearly with sequence length and dominates GPU memory at long contexts.

Consider a 70B parameter model (Llama-2-70B) with $L = 80$ layers, $H = 64$ attention heads, head dimension $d_h = 128$ , at a 128K context window. The KV cache alone requires $2 \times 80 \times 64 \times 128 \times 131{,}072 \times 2$ bytes (FP16) = ~43 GB — exceeding the model weights themselves on a single GPU. This memory bottleneck limits context length, batch size, and serving throughput.

Traditional quantization methods reduce this by storing values in fewer bits (INT8 = 1 byte, INT4 = 0.5 bytes), but they require quantization constants — scale factors $s$ and zero-points $z$ — stored in full precision (FP32 = 4 bytes) for every block of $B$ values. This overhead adds $32/B$ extra bits per value: at 2-bit quantization with block size 32, the overhead is 1 full bit per value — a 50% penalty that undermines the compression goal. Methods like GPTQ, AWQ, and SmoothQuant all suffer from this overhead because they compute data-dependent statistics that must be stored alongside the compressed data.

TurBoQuant eliminates this overhead entirely through a two-stage approach: PolarQuant converts vectors from Cartesian to polar coordinates after random rotation, exploiting the fact that randomly rotated high-dimensional vectors have angle distributions that are known analytically (Beta distributions) — no per-block constants needed. QJL (Quantized Johnson-Lindenstrauss) then corrects the residual quantization error using only sign bits (+1/-1), the most extreme form of quantization.

The result: 3-bit quantization with zero accuracy loss on LongBench, Needle In A Haystack, ZeroSCROLLS, and RULER benchmarks, achieving 5.3x memory reduction (6x practical) and 8x speedup in attention computation on H100 GPUs using custom JAX kernels. Presented at ICLR 2026, TurBoQuant operates within a constant factor of approximately 2.7x of the Shannon rate-distortion lower bound — provably near-optimal for Gaussian sources at any bit width and any dimension.

Chapter Roadmap

Click any topic to jump in

Quantization Overhead

Uniform bit allocation wastes capacity on anisotropic neural activations; a distribution-aware definition is needed.

addressed by Stage 1

PolarQuant (Stage 1)

Recursive random rotation + polar coordinate transform uniformizes the angle distribution for efficient quantization.

QJL (Stage 2)

1-bit sign quantization of the angular residual yields an unbiased inner-product estimator.

followed by Stage 2

KV Cache Compression

Applies TurBoQuant to LLM inference, cutting K/V memory by 5x while preserving attention scores in expectation.

Optimality Bound

TurBoQuant's distortion matches the Shannon rate-distortion lower bound — provably optimal compression.

Every existing quantization method must store metadata — scale factors, zero points, or codebook indices — alongside the compressed data. For extreme low-bit quantization (2-4 bits), this overhead can consume as much storage as the compressed data itself, fundamentally limiting compression ratios.

The Problem

When quantizing a vector $\mathbf{x} \in \mathbb{R}^d$ into $b$ bits per coordinate, standard methods (GPTQ, AWQ, SmoothQuant, absmax quantization) divide coordinates into blocks of size $B$ and compute data-dependent statistics per block:

Symmetric quantization: stores one scale factor $s = \max(|x_i|) / (2^{b-1} - 1)$ per block in FP32 (32 bits) Asymmetric quantization: stores both a scale $s$ and zero-point $z$ per block — 64 bits of overhead per block

The effective bits per value becomes:

$b_{\text{effective}} = b + \frac{c}{B}$

where $c = 32$ for symmetric (one FP32 constant) or $c = 64$ for asymmetric (two FP32 constants).

Concrete examples of the overhead problem:

Target bits $b$	Block size $B$	Overhead $32/B$	Effective bits	Overhead %
4	128	0.25	4.25	6%
4	32	1.0	5.0	25%
2	128	0.25	2.25	12.5%
2	32	1.0	3.0	50%
1	32	1.0	2.0	100%

At 2-bit quantization with a typical block size of 32, the overhead doubles the effective storage from 2 to 3 bits per value. At 1-bit, the overhead exceeds the data itself. Increasing block size $B$ reduces overhead but increases quantization error because a single scale factor must represent a wider range of values.

This overhead is fundamentally unavoidable in traditional approaches because each block's value distribution is arbitrary — the quantizer must observe the data to determine the optimal mapping from floating-point values to integer codes. These data-dependent constants (scale, zero-point) must be stored and transmitted alongside the quantized values.

Methods like per-channel quantization (one scale per output channel) and per-group quantization (GPTQ with group size 128) trade off granularity vs overhead, but all exist on the same overhead curve.

The Solution

TurBoQuant eliminates quantization overhead entirely by exploiting a deep property of high-dimensional geometry: randomly rotated vectors have coordinates with known, analytically computable distributions — no data observation required.

The core insight has three parts:

1. Random rotation makes distributions predictable. Multiply the input vector $\mathbf{x} \in \mathbb{R}^d$ by a random orthogonal matrix $\mathbf{R}$ . The resulting vector $\mathbf{y} = \mathbf{R}\mathbf{x}$ has coordinates that, in high dimensions ( $d \gg 1$ ), are approximately independent and follow a known distribution that depends only on the norm $\|\mathbf{x}\|$ and the dimension $d$ — not on the specific values in $\mathbf{x}$ .

2. Polar coordinates separate magnitude from direction. Converting $\mathbf{y}$ to polar coordinates yields one radius $r = \|\mathbf{y}\| = \|\mathbf{x}\|$ (preserved by orthogonal rotation) and $d-1$ angles $\theta_1, \ldots, \theta_{d-1}$ . After random rotation, these angles follow specific Beta distributions $\text{Beta}(a_i, b_i)$ with known parameters that depend only on the coordinate index and dimension.

3. Known distributions enable optimal quantization without calibration. Since the distribution of each angle $\theta_i$ is known analytically, TurBoQuant can precompute the optimal quantization boundaries (Lloyd-Max quantizer) for each angle once at initialization — no per-block scale factors, no data-dependent statistics, no overhead storage.

This achieves $b_{\text{effective}} = b$ exactly — true zero overhead at any bit width, any dimension, any input distribution. The random rotation matrix $\mathbf{R}$ needs to be shared between encoder and decoder, but it can be regenerated from a single random seed (a few bytes), making its amortized cost negligible.

Key Points

Traditional quantization adds $32/B$ bits of overhead per value for storing FP32 scale/zero-point constants — 50% overhead at 2-bit with block size 32

The overhead becomes proportionally worse at lower bit widths: at 1-bit with $B = 32$ , overhead exceeds the data (100%)

TurBoQuant achieves exactly $b$ effective bits by exploiting the analytically known angle distributions of randomly rotated vectors

No per-block constants, no codebook indices, no data-dependent statistics — just a shared random seed for the rotation matrix

This is the first method to achieve true zero-overhead quantization at any bit width and any dimension

The approach is data-oblivious: the same algorithm works for any input distribution, unlike GPTQ (requires calibration data) or AWQ (requires activation statistics)

Mathematical Formulation

Traditional Effective Bit Rate

$b_{\text{eff}} = b + \frac{c}{B}, \quad c \in \{32, 64\}$

Where b is the target bit width, B is the block size, and c is the overhead per block (32 bits for symmetric, 64 for asymmetric quantization). Increasing B reduces overhead but increases quantization error.

TurBoQuant Effective Bit Rate

$b_{\text{eff}} = b + 0 = b$

Zero overhead — angle distributions after random rotation are known Beta distributions with analytically determined parameters. Optimal quantization boundaries are precomputed, not stored per-block.

Mathematical Intuition

Traditional quantizers assign equal bits per dimension regardless of signal distribution. Neural activations are highly anisotropic — most energy lives in a few directions — so uniform quantization wastes bits on low-variance dimensions. The effective bit rate needs a distribution-aware definition that accounts for spectral concentration.

Back to All Papers

Study Plans

LLM Study Plan ML Study Plan All Papers Practice Problems