High-Rate Quantized Matrix Multiplication II

Or Ordentlich, Yury Polyanskiy · 2026

Read High-Rate Quantized Matrix Multiplication II by Or Ordentlich, Yury Polyanskiy (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13768.txt.

Introduction

Or Ordentlich and Yury Polyanskiy study high-rate rounded matrix multiplication with spread data, part two of a work whose part one covered tuning-free rounding. They show waterfilling lifts real GPTQ rounding, which currently allocates rate equally. A recent WaterSIC scheme using only scalar INT rounders is basis free, marked by the value of the spread matrix. GPTQ scores depend on basis choice, but with random spin and Llama-3-8B spread it sits within 0.1 bit of WaterSIC, hinting near-best at high rates.

Catalog record

CREATOROr Ordentlich, Yury Polyanskiy
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65853
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.13768

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

High-Rate Quantized Matrix Multiplication II Or Ordentlich, Yury Polyanskiy Abstract This is the second part of the work investigating quantized matrix multiplication (MatMul). In part I we considered the case of calibration-free quantization, whereas here we discuss the setting where covariance matrix Σ X \Sigma_{X} of the columns of the second factor is available. This setting arises in the ubiquitous task of weight-only post-training quantization of LLMs. Weight-only quantization is related to the problem of weighted mean squared error (WMSE) source coding, whose classical (reverse) waterfilling solution dictates how one should distribute rate between coordinates of the vector. We show how waterfilling can be used to improve practical LLM quantization algorithms (GPTQ), which at present allocate rate equally. A recent scheme (known as “WaterSIC”) that only uses scalar INT quantizers is analyzed and its high-rate performance is shown to be (a) basis free (i.e., characterized by the determinant of Σ X \Sigma_{X} and, thus, unlike existing schemes, is immune to applying random rotations); and (b) within a multiplicative factor of 2 ​ π ​ e 12 \frac{2\pi e}{12} (or 0.25 bit/entry) of the information-theoretic distortion limit. GPTQ’s performance, in turn, is affected by the choice of basis, but for a random rotation and actual Σ X \Sigma_{X} from Llama-3-8B we find it to be within 0.1 bit (depending on the layer type) of WaterSIC, suggesting that GPTQ with random rotation is also near optimal, at least in the high-rate regime. I Introduction Matrix multiplication (MatMul) constitutes the main building block of AI, and quantization for matrix multiplication has become a central technique for increasing its efficiency. In Part I [ 23 ] we discussed the problem of quantizing two generic matrices with the goal of approximating their product with minimal distortion. The fundamental limits for this assumptions-free setup were derived in [ 22 ] , which we compared with the performance of popular generic quantization schemes for MatMul (such as ubiquitous absmax round-to-nearest with INT or FP arithmetic). Generic quantized MatMul schemes require no prior assumptions on the matrices to be multiplied, and their performance is consequently robust. However, in LLMs activations often have a rather special low-dimensional structure, obviating the need for orthogonalizing quantization errors with the principal directions of activation variation [ 21 , 15 ] . The process of collecting statistics of activation is known as calibration , and thus we can think of Part I as focusing on calibration-free and Part on calibration-aided methods. Clearly, the goal of such methods is to improve matrix product approximation by leveraging calibration statistics. Furthermore, in this paper we focus on the case where arithmetic (actual matmul) is executed and activations loaded in full precision. The goal, thus, is to load weight matrices in compressed (low-resolution) format from the high bandwidth memory (HBM) and then dequantize them into full-precision matrix before executing the actual matmul. Compared to full-precision (BF16) weights, quantizing those to R bits per parameter reduces the required HBM storage and bandwidth capacity by factor 16/R . In Section II we study the fundamental limits of weight-only quantization where we are interested in the matrix product X^{\top}W and only W needs to be quantized to \hat{W} , whereas X is given in full resolution. The problem is made interesting through the fact that while quantization of W cannot know X , it has access to covariance matrix \Sigma_{X} of (the columns of) X . We show that, in essence, using standard “isotropic” codebook and \Sigma_{X} -oblivious quantization, one attains distortion D\approx({1\over n}\mathop{\mathrm{tr}}\Sigma_{X})2^{-2R} . At the same time, the classical waterfilling formula says that optimal codebook (with optimal quantization) can attain D\approx|\Sigma_{X}|^{1/n}2^{-2R} , with the difference given by the gap in AM-GM inequality for eigenvalues of \Sigma_{X} . It turns out that even with isotropic codebook, but \Sigma_{X} -aware encoding one can still attain the same performance. In Section III we discuss the practical aspects of the weights-only quantization problem. Low-complexity algorithms for weight-only quantization in LLMs have been pioneered by [ 10 ] (a \Sigma_{X} -oblivious rounding to nearest integer), [ 21 ] , and GPTQ [ 15 ] . The latter was originally derived from [ 18 ] , but was soon found to be equivalent to classical algorithms known as successive interference cancellation (SIC) in communication and Babai’s algorithm in computer science, cf. Section III . We show that GPTQ (that uses constant rate per entry) attains distortion decaying as D\approx{2\pi e\over 12}({1\over n}\sum_{i=1}^{n}U_{i,i}^{2})2^{-2R} , where U^{\top}U=\Sigma_{X} is the upper-triangular (Cholesky) decomposition of \Sigma_{X} . At the same time, by adjusting rate per-coordinate (“WaterSIC” algorithm [ 20 ] ) one can attain D\approx{2\pi e\over 12}(\prod_{i=1}^{n}U_{i,i}^{2})^{1\over n}2^{-2R} . Since \prod_{i=1}^{n}U_{i,i}=\sqrt{|\Sigma_{X}|} this performance is only a factor away from information-theoretically optimal, or within a rate gap of at most 0.25 bit. Figures 1 and 5 exemplify rate gains for all these four (two theoretical and two practical) algorithms on the example of layers of Llama-3-8B and wiki2 calibration data. II Weight quantization: Theory Let us restrict attention to a particular linear layer in the network with weight matrix W\in\mathbb{R}^{n\times a} . The linear layer operates by taking (a vector of) input activations X and producing Y=X^{\top}W\,. For that, W needs to be loaded from memory and this results in the crucial bottleneck during generation/reasoning part of the LLM operation. Thus, our job is to replace W with quantized version \hat{W} , which can be loaded much faster, with the target of minimizing expected distortion over random inputs X , that is we aim to minimize \displaystyle D \displaystyle={1\over n}\mathbb{E}\|X^{\top}(W-\hat{W})\|_{F}^{2} \displaystyle=\frac{1}{n}\mathop{\mathrm{tr}}(W-\hat{W})^{\top}\Sigma_{X}(W-\hat{W})\,, (1) where \Sigma_{X}=\mathbb{E}[XX^{\top}] (This objective is by far the most popular one, though, others exist [ 19 , 32 , 4 ] .) Since only the second order statistics \Sigma_{X} affect this objective, in practice one uses a set of samples (known as calibration data ) from the underlying distribution in order to estimate it. With the second order statistics at hand, the problem of quantizing W becomes a weighted mean squared error (WMSE) quantization problem. We note that calibration data about X is also useful for quantization of both weights and activations (i.e. the setting of [ 23 ] ). See e.g. [ 34 ] , [ 28 , Section 4.5] , [ 39 ] , [ 38 ] . Weight matrices start life as iid Gaussian and evolve during training. However, in many ways their statistics are still largely very similar to iid Gaussian [ 20 , Appendix] and that is how we will model them in this (theoretical) section. Some (mostly older) LLMs have peculiar aspects of weight matrices, such as existence of outliers and rank deficiencies, that need to be exploited/mitigated in practical algorithms, though. Notice also that objective ( II ) treats distortion across columns of W in an additive manner. Consequently, analyzing the case of a=1 (single column, or single output neuron) can be done without loss of generality, at least as long as n\gg 1 and full advantage of vector quantization can be exploited already in dimension n , without needing to do joint vector quantization across all na dimensions. So in summary, the goal of this section is to understand theoretically the problem of mapping W\sim\mathcal{N}(0,I_{n}) to \hat{W} belonging to

Read the complete text