TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate

Quantize high-dimensional Euclidean vectors to minimize MSE and inner product distortion with near-optimal rates.

Existing VQ algorithms lack accelerator compatibility, are slow, or have suboptimal distortion bounds; TurboQuant overcomes these.

KV cache quantization, nearest neighbor search, training/deploying large-scale AI models.

Vector quantization, a problem rooted in Shannon’s source coding theory, aims to quantize high-dimensional Euclideanvectorswhileminimizingdistortionintheirgeometricstructure. We propose Turbo Quant to address both mean-squared error (MSE) and inner product distor- tion, overcoming limitations of existing methods that fail to achieve optimal distortion rates. Our data-oblivious algorithms, suitable for online applications, achieve near-optimal distortion rates (within a small constant factor) across all bit-widths and dimensions. Turbo Quant achieves this by randomly rotating input vectors, inducing a concentrated Beta distribution on coordinates, and leveraging the near-independence property of distinct coordinates in high dimensions to simply apply optimal scalar quantizers per each coordinate. Recognizing that MSE-optimal quantizers introduce bias in inner product estimation, we propose a two-stage ap- proach: applying an MSE quantizer followed by a 1-bit Quantized JL (QJL) transform on the residual, resulting in an unbiased inner product quantizer. We also provide a formal proof of the information-theoretic lower bounds on best achievable distortion rate by any vector quan- tizer, demonstratingthat Turbo Quantcloselymatchesthesebounds, differingonlybyasmall constant ( ≈ 2.7) factor. Experimental results validate our theoretical findings, showing that for KV cache quantization, we achieve absolute quality neutrality with 3.5 bits per channel and marginalqualitydegradationwith 2.5 bitsperchannel. Furthermore, innearestneighborsearch tasks, ourmethodoutperformsexistingproductquantizationtechniquesinrecallwhilereducing indexing time to virtually zero.