Price of metric universality in vector quantization is at most 0.11 bit

2026/02/05 by Alina Harbuzova, Or Ordentlich, Yury Polyanskiy · 1 voice
Computer Science · Mathematics · #cs.IT #cs.LG #stat.ML

paper · pdf

arxiv published 2026/02/05 · arxiv updated 2026/06/15

Abstract

Fast computation of a matrix product W^\top X is a workhorse of modern LLMs. To make their deployment more efficient, a popular approach is that of using a low-precision approximation \widehat W in place of true W (``weight-only quantization''). Information theory demonstrates that an optimal algorithm for reducing precision of W depends on the (second order) statistics of X and requires a careful alignment of vector quantization codebook with PCA directions of X (a process known as ``waterfilling allocation''). Dependence of the codebook on statistics of X, however, is highly impractical. This paper proves that there exist a universal codebook that is simultaneously near-optimal for all possible statistics of X, in the sense of being at least as good as an X-adapted waterfilling codebook with rate reduced by 0.11 bit per dimension in the case when W is Gaussian. Such universal codebook would be an ideal candidate for the low-precision storage format, a topic of active modern research, but alas the existence proof is non-constructive. Equivalently, our result shows existence of a net in ℝⁿ that is a nearly-optimal covering of a sphere simultaneously with respect to all Hilbert norms.

Citations

• WUSH: Near-Optimal Adaptive Transforms for LLM Quantization
• Pretraining Large Language Models with NVFP4
• The Lattice Geometry of Neural Network Quantization -- A Short Equivalence Proof of GPTQ and Babai's Algorithm
• The Geometry of LLM Quantization: GPTQ as Babai's Nearest Plane Algorithm
• NestQuant: Nested Lattice Quantization for Matrix Products and LLMs
• Optimal Quantization for Matrix Multiplication
• QTIP: Quantization with Trellises and Incoherence Processing
• SpinQuant: LLM quantization with learned rotations
• QuaRot: Outlier-Free 4-Bit Inference in Rotated LLMs
• QuIP#: Even Better LLM Quantization with Hadamard Incoherence and Lattice Codebooks
• QuIP: 2-Bit Quantization of Large Language Models With Guarantees
• SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models
• GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers
• New bounds on the density of lattice coverings
• Incremental Refinement using a Gaussian Test Channel

Discussions

• arxiv.org/abs/2602.05790 [bsky, 2 points, 0 comments]

Related

• Optimal Quantization for Matrix Multiplication
• Pyramid Vector Quantization for LLMs
• Ultra-Quantisation: Efficient Embedding Search via 1.58-bit Encodings
• QuIP#: Even Better LLM Quantization with Hadamard Incoherence and Lattice Codebooks
• Formal Verification of TurboQuant: Machine-Checked Proofs and Gap Closures