Loading...
Online Vector Quantization with Near-Optimal Distortion Rate
Amir Zandieh, Majid Daliri, Majid Hadian, Vahab Mirrokni
Read the Paper on arXivTurBoQuant 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 layers, attention heads, head dimension , at a 128K context window. The KV cache alone requires 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 and zero-points — stored in full precision (FP32 = 4 bytes) for every block of values. This overhead adds 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.
Click any topic to jump in
Uniform bit allocation wastes capacity on anisotropic neural activations; a distribution-aware definition is needed.
Recursive random rotation + polar coordinate transform uniformizes the angle distribution for efficient quantization.
1-bit sign quantization of the angular residual yields an unbiased inner-product estimator.
Applies TurBoQuant to LLM inference, cutting K/V memory by 5x while preserving attention scores in expectation.
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.
When quantizing a vector into bits per coordinate, standard methods (GPTQ, AWQ, SmoothQuant, absmax quantization) divide coordinates into blocks of size and compute data-dependent statistics per block:
Symmetric quantization: stores one scale factor per block in FP32 (32 bits) Asymmetric quantization: stores both a scale and zero-point per block — 64 bits of overhead per block
The effective bits per value becomes:
where for symmetric (one FP32 constant) or for asymmetric (two FP32 constants).
Concrete examples of the overhead problem:
| Target bits | Block size | Overhead | 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 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.
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 by a random orthogonal matrix . The resulting vector has coordinates that, in high dimensions (), are approximately independent and follow a known distribution that depends only on the norm and the dimension — not on the specific values in .
2. Polar coordinates separate magnitude from direction. Converting to polar coordinates yields one radius (preserved by orthogonal rotation) and angles . After random rotation, these angles follow specific Beta distributions 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 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 exactly — true zero overhead at any bit width, any dimension, any input distribution. The random rotation matrix 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.
Traditional quantization adds 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 , overhead exceeds the data (100%)
TurBoQuant achieves exactly 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)
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.
Zero overhead — angle distributions after random rotation are known Beta distributions with analytically determined parameters. Optimal quantization boundaries are precomputed, not stored per-block.
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.