TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate

TL;DR

TurboQuant is a data-oblivious online vector quantization scheme designed for KV-cache compression and large-scale vector search. It quantizes individual high-dimensional vectors (keys, values, embeddings) to 3–4 bits without any per-block calibration constants, training, or fine-tuning, by combining a Johnson-Lindenstrauss-style random rotation (QJL — sign-bit quantization with provable inner-product preservation) with a polar-coordinate decomposition (PolarQuant — separate radius/angle quantization on a fixed spherical grid that needs no per-block normalization). On long-context needle-in-haystack tasks with Gemma and Mistral it reports lossless downstream accuracy at ≥6× KV memory reduction, and on H100 4-bit TurboQuant runs attention up to 8× faster than unquantized 32-bit keys.

Key claims

Standard vector quantization for KV cache and vector search wastes 1–2 bits per number on storing per-block quantization constants (scale + zero-point); TurboQuant removes this overhead by using data-oblivious transforms whose output statistics are known a priori [§1, blog “memory overhead”].
QJL (Quantized Johnson-Lindenstrauss) applies a random JL projection then keeps only the sign of each coordinate — zero memory overhead, near-optimal distortion rate for inner-product preservation, with a paired high-precision-query / low-precision-key estimator [§3, blog “QJL”].
PolarQuant converts each vector to (radius, direction) and quantizes the direction against a fixed spherical lattice; because the angular distribution after random rotation is known and concentrated, no per-block normalization is needed [§4, blog “PolarQuant”].
TurboQuant composes QJL + PolarQuant to achieve provably near-optimal distortion rate at 3–4 bits per coordinate in a data-oblivious online setting (no codebook training, no calibration data) [Abstract, §5].
Empirically, on long-context “needle-in-haystack” benchmarks with Gemma and Mistral, TurboQuant achieves lossless downstream accuracy while shrinking the KV cache by a factor of at least 6× [blog “needle-in-haystack” figure, §6].
On LongBench, ZeroSCROLLS, RULER, and L-Eval (aggregated across QA, code generation, summarization), TurboQuant matches PolarQuant and beats the KIVI baseline on the distortion-vs-memory frontier [blog “aggregated performance” figure].
4-bit TurboQuant attains up to 8× speedup over 32-bit unquantized attention-logit computation on H100, while quantizing the KV cache to 3 bits with no measurable accuracy loss and no fine-tuning [blog “speedup” figure, §6].
For high-dimensional ANN search (1@k recall ratio), TurboQuant beats Product Quantization (PQ) and RabbiQ at smaller code sizes, even though those baselines use large dataset-tuned codebooks [blog ANN-search figure].

Method

The pipeline has two stages. Stage 1 (QJL — bit budget for the sign part). Apply a random orthogonal Johnson-Lindenstrauss projection to the input vector and retain only the sign of each output coordinate (one bit per dim). Inner products are estimated by pairing the 1-bit keys with full-precision queries through an unbiased estimator that exploits the known statistics of JL projections — distortion is concentrated near the information-theoretic lower bound and there is no per-block quantization constant to store. Stage 2 (PolarQuant — bit budget for the magnitude part). Decompose the post-rotation vector into (radius, unit-direction). Quantize the direction against a fixed spherical lattice (think: a 3-bit “compass” with known angular bins) whose boundaries are universal because the angular distribution after random rotation is data-independent. Quantize the radius scalar separately. TurboQuant composes the two: QJL handles the orientation-only inner-product term, PolarQuant adds the magnitude refinement. Because both stages are oblivious to the data distribution, the encoder runs in a single pass with no calibration set, supporting online quantization as new keys/values are appended to the cache. The decoder is symmetric and Flash-Attention-compatible (no materialized scale vectors), and the same primitive works for vector-search inverted indices with no separate codebook training.

Results

KV-cache memory at fixed accuracy (Gemma, Mistral): TurboQuant quantizes the KV cache to 3 bits per number with zero accuracy loss and ≥6× memory reduction on needle-in-haystack [blog “needle-in-haystack” figure].
Aggregate long-context score: TurboQuant Pareto-dominates the KIVI baseline on LongBench / ZeroSCROLLS / RULER / L-Eval at matched bit budget [blog “aggregated performance” figure].
Attention compute speedup: 4-bit TurboQuant computes attention logits up to 8× faster than the 32-bit unquantized baseline on H100 [blog “speedup” figure].
Vector search: TurboQuant exceeds PQ and RabbiQ in 1@k recall ratio across high-dimensional ANN datasets at small code sizes, despite the baselines using large dataset-specific codebooks [blog ANN-search figure].
Runtime overhead: encode + decode add negligible wall-clock cost to a Gemma/Mistral forward pass — total runtime is faster than the un-quantized baseline because the attention-logit speedup dominates [blog “runtime” claim, §6].

Why it’s interesting

TurboQuant is the quantization sibling of Inference-Time Hyper-Scaling with KV Cache Compression‘s eviction approach to the same problem (KV-cache pressure is the inference-time bottleneck for long-context decoding): DMS shrinks the cache by dropping tokens with a learned per-head Gumbel-sigmoid policy that needs ~1K distillation steps, whereas TurboQuant shrinks the cache by quantizing every retained token’s vector to 3–4 bits in a fully data-oblivious online pass with no training at all. The two are orthogonal — DMS’s compressed token set could be stored in TurboQuant bits — and the “no calibration, no fine-tuning” property is what makes TurboQuant cheap to deploy in a serving stack the way PagedAttention-style cache layouts are. The Johnson-Lindenstrauss + polar-lattice composition also generalizes beyond LLM KV caches to embedding indices (vector search, retrieval), which is the second application emphasized in the Google blog and is relevant to any retrieval-augmented system the team runs.