Source-linked AI summary
TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate
Amir Zandieh, Majid Daliri, Majid Hadian, Vahab Mirrokni
TL;DR
Vector quantization seeks low-distortion compression of high-dimensional vectors, but existing approaches can be slow, poorly suited to accelerators, or suboptimal across bit-widths. TurboQuant uses rotation-based scalar quantization for MSE and a residual QJL stage for unbiased inner-product estimation, achieving distortion within about 2.7× of the information-theoretic lower bound. Its supported scope includes worst-case, data-oblivious quantization, with existing accelerator limitations motivating the design.
Problem
Existing vector quantizers can lack accelerator compatibility or online speed and can have suboptimal distortion bounds across bit-widths.
Method
TurboQuant randomly rotates vectors for coordinatewise MSE quantization and applies 1-bit QJL quantization to the residual for unbiased inner-product estimation.
Results
3π^2 ≈ 2.7 is the maximum reported factor between TurboQuant's MSE distortion and the information-theoretic lower bound, while small-bit inner-product distortion is reported as Dprod ≈ 1.57.
Takeaways & Limitations
TurboQuant provides data-oblivious quantizers intended for online applications across bit-widths and dimensions, with near-optimal distortion rates.
Takeaways & Limitations
The analysis considers worst-case vectors and makes no assumptions about the input vector dataset; prior accelerator limitations are also identified for existing algorithms.
Abstract
from arXiv · showhide
Vector quantization, a problem rooted in Shannon's source coding theory, aims to quantize high-dimensional Euclidean vectors while minimizing distortion in their geometric structure. We propose TurboQuant to address both mean-squared error (MSE) and inner product distortion, 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. TurboQuant 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 approach: 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 quantizer, demonstrating that TurboQuant closely matches these bounds, differing only by a small constant ($\approx 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 marginal quality degradation with 2.5 bits per channel. Furthermore, in nearest neighbor search tasks, our method outperforms existing product quantization techniques in recall while reducing indexing time to virtually zero.
1 Introduction
TurboQuant targets efficient, low-distortion quantization of high-dimensional vectors for AI, KV-cache, and nearest-neighbor workloads. It combines MSE-optimal and unbiased inner-product quantization, with provable near-optimal distortion rates and reported gains in low-bit settings.
- Motivation: Vector quantization compresses high-dimensional vectors for AI, deep learning, and search while preserving geometric properties such as MSE and inner products.These properties support low-latency inner-product queries with reduced computational and communication resources.
- Problem: Existing methods trade off accelerator compatibility and online speed against distortion quality, motivating a lightweight, online, accelerator-friendly algorithm.The stated objective is to address both computational and distortion-rate limitations.
- Inner Product TurboQuant: TurboQuant's two-stage inner-product quantizer applies MSE quantization to minimize residual norm, then 1-bit QJL quantization to obtain unbiased estimates.The MSE stage uses one fewer bit than the target budget, reserving one bit for QJL.
- MSE-Optimized TurboQuant: TurboQuant uses random rotations and near-independent coordinates to apply optimal scalar quantizers, achieving near-optimal MSE distortion.The rotation induces concentrated coordinate distributions, allowing coordinatewise quantization while retaining near-optimal distortion.
- Theory and Results: For small bit-widths b = 1, 2, 3, 4, inner-product distortion is reported as Dprod ≈ 1.57.The supplied passage gives this value without a complete accompanying expression.
- Theory and Results: 3π^2 ≈ 2.7 is the maximum factor separating TurboQuant's MSE distortion from the information-theoretic lower bound, decreasing to approximately 1.45 at b = 1.For b = 1, 2, 3, 4, the reported MSE distortions are approximately 0.36, 0.117, 0.03, and 0.009, respectively.
2 Preliminaries
The preliminaries define the notation and information-theoretic framework for analyzing quantization distortion, including random hypersphere coordinates, Shannon lower bounds, and QJL-based inner-product estimation. They also introduce the two quantization objectives: MSE minimization and unbiased inner-product estimation.
- Notation: Vectors and matrices use boldface notation; x_i:j denotes an inclusive vector slice, while M_i denotes matrix row i.
- Random hypersphere coordinates: Uniform coordinates of a random point on the unit hypersphere follow a scaled/shifted Beta distribution and converge to N(0, 1/d) in high dimensions.This distribution underpins the analysis of random rotations and coordinate-wise quantization.
- Shannon Lower Bound: The Shannon Lower Bound gives a universal lower bound on achievable lossy-compression distortion rates, including MSE distortion for arbitrary d-dimensional sources.For finite differential entropy, the stated bound is D(pX, B) ≥ d/(2πe) · 2^(2(h(x)−B)/d).
- Shannon Lower Bound: For uniformly distributed points on the unit hypersphere, the SLB specializes to a distortion lower bound obtained by substituting the hypersphere’s entropy and area into the general result.The hypersphere entropy is expressed through the logarithm of its surface area, with Stirling’s approximation used in the derivation.
- QJL inner-product quantization: QJL maps vectors to d sign bits using a Gaussian random matrix and provides unbiased inner-product estimates with a variance bound.The paper uses QJL as the 1-bit stage of its inner-product quantization approach.
3 TurboQuant: High Performance Quantization
TurboQuant develops two vector quantizers tailored to MSE and unbiased inner-product estimation, using random rotations and scalar quantization. It establishes near-optimal distortion guarantees through matching upper and information-theoretic lower bounds.
- TurboQuant overview: TurboQuant provides separate algorithms optimized for MSE and unbiased inner-product estimation.The inner-product method addresses bias introduced by MSE-optimal quantizers.
- MSE-optimal TurboQuant: Random rotations make coordinates follow a Beta distribution and become nearly independent in high dimensions, enabling coordinate-wise scalar quantization.The scalar quantizers are based on continuous one-dimensional k-means and Lloyd-Max centroids.
- MSE-optimal TurboQuant: TurboQuant_mse quantizes rotated coordinates using nearest centroids and rotates the reconstructed vector back to the original basis.The codebook is constructed by solving the scalar MSE optimization problem for the chosen bit-width.
- MSE-optimal TurboQuant: Dmse ≈0.36, 0.117, 0.03, 0.009 for b = 1, 2, 3, 4, respectively.For general bit-widths, the theorem gives an upper bound proportional to 1/4^b.
- Inner-product-optimal TurboQuant: The inner-product quantizer combines an MSE quantizer at b −1 bits with a 1-bit QJL quantizer on the residual.This construction yields an unbiased inner-product estimator while using total bit-width b.
4 Experiments
TurboQuant is evaluated against theoretical predictions and competing methods for inner-product estimation, long-context KV-cache compression, and nearest-neighbor search. Across these settings, the experiments show method-specific distortion behavior, strong long-context performance, and higher recall than PQ and RabitQ.
- 4.1 Empirical Validation: Increasing bit width reduces inner-product error variance for both TurboQuant methods, while TurboQuantmse introduces bias that converges toward zero at higher bit widths.TurboQuantprod remains unbiased across bit widths, whereas TurboQuantmse is MSE-oriented and becomes more accurate for inner-product estimation as bit width increases.
- 4.1 Empirical Validation: At b = 2, TurboQuantprod maintains constant inner-product-error variance, while TurboQuantmse bias increases with the average inner product.The variance behavior is reported specifically for 2-bit quantization.
- 4.1 Empirical Validation: TurboQuantprod performs better at lower bit ratios, while TurboQuantmse achieves superior inner-product estimation as increasing bit count reduces its bias.The experiments compare average inner-product error and MSE against theoretical upper and lower bounds.
- 4.2 Needle-In-A-Haystack: At 4× compression, TurboQuant achieves identical performance to the full-precision model on the Llama-3.1-8B-Instruct Needle-In-A-Haystack evaluation.The test varies document lengths from 4k to 104k tokens and measures recall of a hidden sentence.
- 4.3 End-to-end Generation on LongBench: TurboQuant outperforms competing KV-cache compression methods on LongBench for Llama-3.1-8B-Instruct and Ministral-7B-Instruct, while using 2.5-bit and 3.5-bit quantization.The reported setup applies quantization during streaming generation and compresses quantized vectors by at least 4.5×.
- 4.4 Near Neighbour Search Experiments: TurboQuant consistently achieves higher recall ratios than Product Quantization and RabitQ across the nearest-neighbor experiments.The comparison uses recall ratio at top-k across datasets and embedding dimensions.