1
High-Rate Quantized Matrix Multiplication II
arXiv:2605.13768v1 [cs.LG] 13 May 2026
Or Ordentlich and 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 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 and, thus, unlike existing schemes, is immune to applying random rotations); and (b) within a multiplicative factor of 2πe (or 0.25 bit/entry) of the information-theoretic 12 distortion limit. GPTQ’s performance, in turn, is affected by the choice of basis, but for a random rotation and actual Σ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. I NTRODUCTION 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 [1] 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 [2], 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 O. Ordentlich is with the Hebrew University of Jerusalem, Israel ([email protected]). Y. Polyanskiy is with the MIT, USA ([email protected]). The work of OO was supported by the Israel Science Foundation (ISF), grant No. 2878/25. The work of YP was supported in part by the MIT-IBM Watson AI Lab and by the National Science Foundation under Grant No CCF-2131115.
variation [3], [4]. 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 ⊤ W and only W needs to be quantized to Ŵ , 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 ΣX of (the columns of) X. We show that, in essence, using standard “isotropic” codebook and ΣX -oblivious quantization, one attains distortion D ≈ ( n1 tr ΣX )2−2R . At the same time, the classical waterfilling formula says that optimal codebook (with optimal quantization) can attain D ≈ |ΣX |1/n 2−2R , with the difference given by the gap in AM-GM inequality for eigenvalues of ΣX . It turns out that even with isotropic codebook, but Σ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 [5] (a ΣX -oblivious rounding to nearest integer), [3], and GPTQ [4]. The latter was originally derived from [6], 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 Pnentry)2 attains 1 −2R ( , distortion decaying as D ≈ 2πe i=1 Ui,i )2 12 n ⊤ where U U = ΣX is the upper-triangular (Cholesky) decomposition of ΣX . At the same time, by adjusting rate per-coordinate algorithm Q [7]) one can Qn(“WaterSIC” 1 n 2 n −2R attain D ≈ 2πe ( U ) 2 . Since i,i i=1 i=1 Ui,i = 12
2
p
|Σ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. W EIGHT QUANTIZATION : T HEORY Let us restrict attention to a particular linear layer in the network with weight matrix W ∈ Rn×a . The linear layer operates by taking (a vector of) input activations X and producing Y = X ⊤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 Ŵ , which can be loaded much faster, with the target of minimizing expected distortion over random inputs X, that is we aim to minimize 1 D = E∥X ⊤ (W − Ŵ )∥2F n 1 = tr(W − Ŵ )⊤ ΣX (W − Ŵ ) , (1) n where ΣX = E[XX ⊤ ] (This objective is by far the most popular one, though, others exist [8], [9], [10].) Since only the second order statistics Σ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 [1]). See e.g. [11], [12, Section 4.5], [13], [14]. 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 [7, 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 (1) 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 ≫ 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 ∼ N (0, In ) to Ŵ belonging to the universe of 2nR possibilities, with the goal of minimizing D=
1 (W − Ŵ )⊤ ΣX (W − Ŵ ) . n
(2)
One important aspect of the weight only quantization problem worth pointing out from the outset is the asymmetry between encoding and decoding. The encoding (quantization) is done offline, once for each model, and may therefore be computationally demanding. The decoding (de-quantization), on the other hand, is executed online every time a weight matrix is used, and must therefore be highly efficient. (This is in contrast with activation quantization, which is done online and has to be extremely computationally efficient.) In particular, while information about ΣX is available to the encoder (recall that it operates offline and can be quite slow), the decoder’s online operation requires all information about ΣX be packaged inside the rate-constrained description of W . Thus, assuming decoder knows ΣX or its SVD basis (rather than only its spectrum) is not reflecting the practical constraints adequately. Nevertheless, below we will start by treating the impractical fully informed case, which will provide a firm lower bound to the more practical version of uninformed/oblivious decoder case. We initiate our discussion with a simple heuristic demonstration of the main points on the example of scalar quantization.
A. Scalar quantization and waterfilling Before discussing information theoretic results, let us consider a very simple case of X with uncorrelated coordinates, i.e. ΣX = diag{λ1 , . . . , λn }. Suppose, in addition, that the weights satisfy Wi ∈ Uniform[−1/2, 1/2). Consider, first, the case of usual uniform quantization using ϵ-grid, where ϵ = 2−R . The resulting distortion (in accordance with additive noise approximation discussed in Part I [?]) will be n
D1 (R) =
λ̄A −2R 1 X ϵ2 λi = 2 , n i=1 12 12
P where λ̄A = n1 i λi is the arithmetic mean of λ’s. Now, given that different coordinates of W contribute differently to D, one may naturally try to allocate rate more judiciously. Specifically, let us solve the problem of n 1 X 2 D2 = min λ i ϵi , 12n i=1
3
Q 1 nR subject to rate constraint . Using Lagrange ϵi ≤ 2 multipliers we can easily find a parametric formula for the optimizer, given in terms of parameter τ > 0: n 1X min(τ, λi /12) D2 = n i=1 n
1 X λi log max(1, ), 2n i=1 12τ q where the grid spacings ϵi = min( 12τ λi , 1). This kind of allocation is traditionally called (reverse) waterfilling solution, due to interpretation of τ as water level that reduces i’th coordinate baseline distortion (equal to λi /12) down to τ . Those coordinates that are so insignificant (“below waterlevel”) get zero rate allocation and are quantized to zero. In accordance with our focus on high-rate case, we can assume that τ < mini λi and get a simplified expression: R=
λ̄G −2R 2 , 12 Q where λ̄G = ( i λi )1/n is the geometric mean of λi ’s. In all, we conclude that when quantizing vectors under weighted quadratic metric, one should choose quantization grid spacing ϵi ∝ √1λ with coefficient of i proportionality chosen depending on the target required rate R. How much does one win from this optimization is given by the AM-GM inequality λ̄G < λ̄A . Another way to put this is that optimizing per-coordinate quantizers A one wins about 12 log λ̄λ̄G bits of rate. We will return to this idea below, when we describe a practical WaterSIC algorithm for weight-only quantization in Section III-D. There the role of λi ’s is played by the diagonal elements of the Cholesky decomposition of (non-diagonal) ΣX . Fig. 1 illustrates rate-advantage for input activations to various linear layers of Llama-3-8B. D2 (R) =
B. WMSE Quantization: information theoretic limit The waterfilling solution derived heuristically in the previous section can be in fact made rigorous, at least 2 for the case of Gaussian weights W ∼ N (0, σW In ), which we consider here. Another assumption we make is that the covariance matrix ΣX ∈ PSDn (the set of all n × n PSD matrices) is fixed and known to both encoder and decoder. 2 The formal problem is this: given W ∼ N (0, σW In ), n nR encoder f : R → [2 ] produces a rate-R description of W . Subsequently, decoder g : [2nR ] → Rn converts this description into the estimate Ŵ . The informationtheoretic question is to determine the value of the smallest distortion attainable by the best pair (f, g), i.e. 1 D∗ (ΣX , R) = min E[(W − Ŵ )⊤ ΣX (W − Ŵ )] . f,g n
The naive (suboptimal) solution is to use a standard isotropic Gaussian codebook of rate R, which results in error covariance given by E[(W − Ŵ )(W − Ŵ )⊤ ] = 2 −2R σW 2 In . Note that the previous result is simple if we understand E as averaging over the Gaussian codebook, but is rather non-trivial if we want to demonstrate existence of a codebook with nearly-white covariance matrix of errors. This was the main technical difficulty behind the results of [2], cf. Theorem 13 there. Nevertheless, under this assumption on the error distribution, we get Diso (R) = 2−2R
2 σW tr ΣX . n
(3)
Although this is generally very far from D∗ (ΣX , R), such scheme works simultaneously for all ΣX and does not require knowledge thereof. Scheme that is allowed to fully exploit knowledge of ΣX can first compute W ′ = V ⊤ W , where V is the orthogonal matrix in the SVD decomposition of ΣX = V ⊤ ΛV . If decoder can estimate Ŵ ′ , then it can also set Ŵ = V Ŵ ′ . Then, the distortion can be expressed in terms of (W ′ , Ŵ ′ ) as n
D=
1X λi E[(Ŵi′ − Wi′ )2 ] . n i=1
We see that after this change of coordinates, the problem indeed becomes that of weighted mean-squared error (WMSE), justifying the name. To relate distortion and rate, we consider a standard data-processing argument, see [15, Section 23.4]: nR ≥ I(W ′ ; Ŵ ′ ) ≥
n X
I(Wi′ ; Ŵi′ ) ,
i=1
where the second inequality is due to independence of 2 coordinates of W ′ ∼ N (0, σW In ), cf. [15, Theorem 6.1]. Now, given value Di = E[(Ŵi′ −Wi′ )2 ] the smallest σ2 I(Wi′ ; Ŵi′ ) = 12 log DWi is attained under Gaussian coupling, cf. [15, Section 26.1.2]. Overall, we get n
R≥
1 X σ2 log W 2n i=1 Di
D=
1X λi Di . n i=1
n
Minimizing the value of D given R can be done via Lagrange multipliers, resulting in the (reverse) waterfilling solution parameterized by τ > 0: n 2 X σW min{λi , τ }, D (τ ) = n i=1 n 1X1 λi ∗ R (τ ) = log max 1, . n i=1 2 τ ∗
(4)
4
(a) Scatter plot illustrating gap in AM-GM inequality for eigenvalues of ΣX .
(b) Rate advantage (in high-rate regime) of waterfilling over Diso (which corresponds to the case of ΣX -oblivious encoder and decoder). Squares correspond to (skipped) layers with singular ΣX .
Fig. 1: Illustrating ΣX of activations entering various layers of Llama-3-8B when processing Wikitext-2 dataset. Note that this is an estimate of the rate advantage assumes weight matrices are well modeled by N (0, In ). In particular, actual weight matrices were never used for this plot.
Note that, while our argument only gives a lower bound on the minimal distortion, it can be shown to be achievable asymptotically for large n, even in the single vector setting [16, Proposition 2.1]. Thus, in the remainder of this paper, we will consider the value D∗ (R) given by waterfilling to be the actual fundamental limit, ignoring small non-asymptotic penalty. Just like in the previous heuristic section, we see that optimal codebook allocates rate unequally: the PCA direction corresponding to high values of λi should get quantized more finely with Di ∝ λ1i . In the high-rate regime we get ∗ 2 −2R DHigh−Rate (R) = |ΣX |1/n σW 2 ,
(5)
and the advantage compared to uninformed isotropic coding is again given by the gap in the AM-GM inequality, or 1 tr ΣX 1 log n 2 | det ΣX |1/n bits in effective rate. C. ΣX -oblivious decoder In the setup above, we have allowed the decoder to depend on ΣX (in particular, to apply SVD decomposition). However, in LLM applications this would require communicating ΣX (or the SVD basis matrix V ) to GPU’s compute devices, which would be very costly.
Instead, we would like to use a very lean decoder, that only uses those bits provided with the description of W to produce its reconstruction, universally for all ΣX . We will therefore require that while the encoder f (W, ΣX ) may depend on ΣX , the decoder g : [2nR ] → Rn depends only on the bits it receives from the encoder. With this constraint, the quantization problem consists of a codebook C ⊂ Rn with |C| ≤ 2nR codewords, agreed upon by the encoder and decoder, where the encoder’s job is to solve, or approximately solve, the problem Ŵ ∗ = argmin[(W − c)⊤ ΣX (W − c)].
(6)
c∈C
The encoder then describes Ŵ ∗ using nR bits, and the decoder can reconstruct Ŵ ∗ from those bits. We know from the previous section that in order to achieve the informed (waterfilling) D∗ (R) optimal codebook needs to be anisotropic: the “grids” need to be denser along the PCA directions corresponding to higher values of λi . In the uninformed case, we are not able to do such adaptation (since ΣX is unknown at the time of the codebook design). Thus, we are forced to use isotropic codebook. In [16] a somewhat surprising result is shown: if one generates C iid from isotropic Gaussian distribution, then simultaneously for all ΣX the adaptive encoder (6) achieves the following (parametric)
5
rate-distortion: Drc (R) =
n 2 X σW
n
λi 1 + λi T i=1 n
R=
1 X log(1 + λi T ) . 2n i=1
First, observe that in the high-rate regime R ≫ 1 (i.e. T ≫ 1), we get 2 −2R Drc (R) = |ΣX |1/n σW 2 + O(2−4R ) .
Comparing this to (5), we observe that in the high-rate regime this scheme attains the optimal waterfilling distortion (upto higher order corrections), despite decoder not knowing ΣX . Furthermore, analysis in [16] shows that universally over all possible ΣX the gap between waterfilling solution D∗ (R) and Drc (R) is never more than 0.11 bit. This result demonstrates that the most significant part of the gap between (3) and (4) is not due to suboptimal codebook design, but rather due to suboptimal rounding to that codebook. In other words, one must focus on implementing better rounding schemes rather than optimizing codebooks. Unfortunately, as we will see in the next section, even for the uniform quantization (Zn codebook), solving (6) is computationally hard. Thus, despite theoretical near-optimality of isotropic codebooks, the algorithmic difficulty makes ΣX -oblivious quantization very interesting and rather underexplored. A practical low-complexity algorithm, known variously as successive-interference cancellation (SIC), Babai’s algorithm, GPTQ or LDLQ, will be discussed in the next section. III. W EIGHT QUANTIZATION : P RACTICE In this section we discuss approximate solutions for the WMSE quantization problem, that can be computed efficiently. We will describe several variants of the GPTQ/LDLQ algorithms [4], [17], and propose novel improvements based on our information theoretic analysis. The schemes we discuss rely on a reformulation of the “optimal rounding” problem (6) using the Cholesky decomposition [18], [19]. We develop this reformulation in Subsection III-A. The analysis of the quantization schemes that follow requires some background in highresolution quantization using lattices. We provide this background in Subsection III-B, and then in Subsection III-C we explain and analyze the SIC rounding algorithm. In its most basic form, this algorithm is equivalent to the canonical GPTQ/LDLQ [4], [17], as was recently observed in [18], [19]. In light of the information theoretic analysis above, and the analysis of the SIC algorithm, it immediately becomes clear that a simple variation of GPTQ/LDLQ called WaterSIC, that
we develop in Subsection III-D, provides an improved distortion and is provably quite close to the lower bound (5) we developed on the WMSE. The WaterSIC algorithm is further developed in [7], and is also shown to perform remarkably well for low-rate weight only quantization of LLMs. A. Reformulation of (6) via Cholesky Decomposition Using the Cholesky decomposition, we can decompose ΣX as ΣX = U ⊤ U where U ∈ Rn×n is an upper triangular matrix. Plugging this into (6) we obtain that given a fixed codebook C the optimal quantization problem becomes Ŵ ∗ = argmin ∥Y − U · c∥2 , where Y = U W ∈ Rn . c∈C
(7) Denote eY = Y − U Ŵ ∗ ,
eW = W − Ŵ ∗ ,
(8)
and note that Ŵ ∗ = W + eW = W + U −1 eY .
(9)
2 In ), N (0, σW
we have that Recall thatpsince W ∼ 2 B) → 0 for any ε > 0, as n(1 + ε)σW Pr(W ∈ / n → ∞, where B = {x ∈ Rn : ∥x∥ ≤ 1}. For high-resolution quantization, where eY is so small that U −1 eY can also be assumed small, this will imply that ∗ Ŵ p will typically also fall inside a ball with radius 2 B, where ε n(1 + εR )σW R vanishes with R (and n). This fact will be useful in the analysis below. Before proceeding further, we note that the diagonal entries of the Cholesky matrix U will play here the same role as eigenvalues of ΣX did in Section II. In particular, we will see that algorithms whose codebooks have equal density in each direction (SIC/GPTQ) attain error ! 2πe 2 1X 2 DGPTQ (R) ≈ σ U 2−2R , (10) 12 W n i i,i which depends on arithmetic mean of squared entries of diagonal of U (which is highly dependent on permutation of columns of ΣX and application of random rotations). Our new scheme (“WaterSIC”) spends rate more judiciously (more bits to coordinates with higher Ui,i and attains !1/n 2πe 2 Y 2 DWaterSIC (R) ≈ σ Ui,i 2−2R . (11) 12 W i On a first sight, we only get the same AM-GM improvement as with / without waterfilling. However, what is remarkable and much is the fact that since |ΣX | = Q deeper 2 1/n |U |2 , we have ( i Ui,i ) = |ΣX |1/n , thus recovering 2πe (within factor 12 , which corresponds to Koshelev’s famous 0.254 bit gap [15, Section 24.1.5]) the information∗ theoretic optimal waterfilling rate DHigh−Rate , see (5).
6
B. Preliminaries on High-resolution quantization via shaped/entropy coded lattice quantizers Lattices: We review some basic lattice definitions. See [20] for a comprehensive treatment of lattices in information theory. Any lattice L ⊂ Rn has a (nonunique) generating matrix G ∈ Rn×n such that L = GZn . The covolume of the lattice L, denoted covol(L)) is defined as |G|. The point density of a lattice is γ(L) = covol−1 (L) = |G|−1 . For a lattice L ⊂ Rn we define the nearest neighbor quantizer QL : Rn → L as QL (x) = argmin ∥x − λ∥,
(12)
λ∈L
where ties are broken arbitrarily, but in systematic manner. The Voronoi region VL is defined as the set of all points in Rn that are closer to 0 than to any other lattice point VL = {x ∈ Rn : QL (x) = 0} .
(13)
The volume of the Voronoi region (as well as any other fundamental cell of L) is Vol(VL ) = covol(L) = |G|. We define the second moment of the lattice L as 1 (14) σ 2 (L) = E∥Z∥2 , n where Z ∼ Uniform(VL ) is a random vector uniformly distributed over the Voronoi region of L. High-resolution lattice quantizers: Designing a quantizer for the WMSE problem with ΣX -oblivious decoder entails choosing the codebook C, which consists of 2nR vectors in Rn . One way to construct such a codebook is to start with an infinite constellation, in our case a lattice L ⊂ Rn , and then choose from L only 2nR points [20]. This can be done by choosing a shaping region S ⊂ Rn , e.g. S = rB for some r > 0, and taking C = L∩S where S is dilated such that |L ∩ S| = 2nR . Correspondingly, this way of thinking about vector quantization splits the problem into design of good infinite constellations (with prescribed point density) and shaping regions that chop off a finite part of it. Many practical solutions for weight-only quantization that were considered in the literature fall under the shaped lattice quantization paradigm: GPTQ with INT constellations [4] as well as LDLQ with E8 -based codebooks as in QuIP# [17], [21], and many more. Assume the point Ŵ ∗ ∈ L that minimizes (7) with respect to the entire lattice L (rather than L ∩ S) is within the shaping region S. In this case, eY ∈ VU L and if we further assume eY ∼ Uniform(VU L ) the distortion is σ 2 (U L). However, whenever the overload event Ŵ ∗ ∈ / S occurs, the squared error may significantly exceed σ 2 (U L). In high-resolution quantization, we may assume Ŵ ∗ ≈ W , and the overload probability
is well approximatedpby Pr(W ∈ / S). As mentioned 2 B, with some small above, taking S = n(1 + ε)σW ε > 0 (or any other S that contains this ball) suffices for achieving vanishing overload probability. Thus, for such choice of S we have that D ≈ σ 2 (U L). If L is “sufficiently dense” with respect to S, it holds that |L ∩ S| ≈ γ(L) · Vol(S) where γ(L) is the point density of L (see [22, Lemma 3.3] for precise bounds on |L ∩ S|). This approximation becomes accurate in the high-resolution limit (as high-resolution corresponds to large γ(L)). We can therefore approximate the rate as 1 1 1 R = log |L ∩ S| ≈ log(Vol(S)) + log γ(L). n n n (15) It follows that in the high-resolution regime the quantization rate R and the normalized log point-density 1 n log γ(L) are equal up to a constant. Furthermore, recalling that D ≈ σ 2 (U L) provided that Pr(W ∈ / S) is sufficiently small, we can express D in the form familiar to us. Specifically, we get from (15) 2 2 2 D ≈ σ 2 (U L) · γ n (U L) |U | n · Vol n (S) · 2−2R 2 2 1 = σ 2 (U L) · γ n (U L) |ΣX | n · Vol n (S) · 2−2R , (16) where we also used the fact γ(U L) = |U |−1 γ(L). The term in (·) is a famous and extremely well-studied quantity [20] known as the normalized second moment 2 (NSM) of U L, defined as σ 2 (U L) · γ n (U L). From (16) we see that the tradeoff between rate and distortion is determined by: 1)The volume of the shaping region (which is required to satisfy Pr(W ∈ / S) ≪ 1); 2)The NSM of U L. We stress that σ 2 (U L) is the WMSE distortion when the argminc∈L in (7) is solved exactly. As we discuss below, finding the exact solution to this problem is generally infeasible for large n, and one must resort to approximate solutions. In the case where a sub-optimal quantizer q : Rn → L is used, the NSM is replaced with 2 1 2 n n E∥Y − U · q(Y )∥ · γ (U L) in (16). An alternative approach for shaping is entropy coding (EC). If quantization with variable rate is allowed, and only the expected quantization rate is constrained to be at most R, one can quantize the source to the point Ŵ ∗ ∈ L that minimizes (7) (assuming C = L), and then describe the resulting point in bits using EC. A sequence of classic works [23], [24], [25], [26] have considered the case of high-resolution entropy coded quantization with infinite constellation, and subsequent work restricted attention to the case where the infinite constellation is taken as a lattice [27], [28], [20]. Those works considered the MSE case with ΣX = In , but their conclusion adapted to the WMSE case is that for highresolution quantization and large n the tradeoff between
7
distortion and average quantization rate also obeys (16) 2 2 , where h(·) with Vol n (S) replaced by 22h(W ) = 2πeσW denotes differential entropy. Namely, for entropy coded high-resolution lattice quantization 1 2 2 D ≈ σ 2 (U L) · γ n (U L) 2πe · |ΣX | n σW · 2−2R . (17) Since rate and normalized lattice point density are equivalent under either shaped or entropy coded lattice quantization, it suffices to consider the tradeoff between WMSE distortion and γ(L). To that end, we now provide a lower bound on σ 2 (U L) that depends only on |U | and on γ(L). This bound is due to Zador [25] (See also [29, eq. (82)]). It follows from the fact that σ 2 (U L) is the power of a random vector uniformly distributed over VU L ⊂ Rn , which is a convex body of volume V = |U | · γ −1 (L). Among all bodies in Rn of volume V , the power of a uniform random vector is minimized when the body is a ℓ2 ball.1 Proposition 1 (Zador): For any full-rank lattice L ⊂ Rn and any full-rank matrix U ∈ Rn×n 2 2 Γ n2 + 1 2 2 γ(L)− n |U | n −n 2 n γ(L) |U | ≈ . σ (U L) ≥ (n + 2)π 2πe (18) In (18), Γ(·) is the gamma function. The last approximation can be replaced with a lower bound at the expense of multiplying the right-hand side term by a n factor of n+2 . Note that substituting (18) in (17), gives ∗ ∗ D ≳ DHigh−Rate (R), where DHigh−Rate (R) is given in (5). Even without relying on the validity of (17), Proposition 1 provides a simple lower bound on the WMSE distortion of any high-resolution quantization scheme for which the reconstruction satisfies Ŵ ∈ L, for a lattice L ⊂ Rn . This follows since for any such quantization scheme we have (due to (7)) D≥
1 1 min E∥Y − U · c∥2 = ∥Y − QU L (Y )∥2 , c∈L n n
where QU L : Rn → U L is the nearest neighbor (optimal) quantizer for the lattice U L ⊂ Rn . Under the high-resolution assumption eY = Y − QU L (Y ) ∼ Uniform(VU L ) and consequently 2
D ≥ σ 2 (U L) ≳
2
2
− 1 γ(L) n γ(L)− n |U | n = |ΣX | n , 2πe 2πe (19)
1 In fact, it is known [30] that for almost all lattices (with respect to the natural measure on the space of lattices) σ 2 (L) is only (1 + O(1/n)) greater than the second moment of the corresponding ℓ2 ball. Thus, this lower bound is asymptotically attained by a “typical” lattice.
where we have used Proposition 1 and the fact that |U |2 = |ΣX |. For example, in GPTQ/LDLQ it is common to take L = αZn as the base lattice, whose density is γ(L) = α−n . From (19) we see that its attained distortion must |1/n satisfy D ≳ α2 |ΣX 2πe . Note that (19) relies on the assumption e = U W − QU L (U W ) ∼ Uniform(VU L ). This holds asymptotically in the limit of high resolution (γ(L) → ∞) for all full-rank matrices U ∈ Rn×n . If one uses dithered lattice quantization [20], this assumption holds exactly for all γ(L). However, in the case of dithered lattice quantization the resulting estimate Ŵ ∗ would not be in L. Instead, under dithered lattice quantization we have Ŵ ∗ = Y + e where e ∼ Uniform(VU L ), e ⊥ ⊥ Y. Consequently, one can benefit by setting Ŵ = β Ŵ ∗ with β < 1 as the estimate for W , as in this case 1 E(X T (W − Ŵ ))2 = E((1 − β)X ⊤ W − βe)2 n 2 tr(ΣX ) + β 2 σ 2 (U L). (20) = (1 − β)2 σW n This is the same shrinkage effect that we discussed in [1, Section I.b] Note that β → 1 as σ 2 (U L) decreases, which is the case for high-resolution quantization.
C. Product Codebooks, Codebook Spacing, and Successive Cancellation This section discusses efficient quantization schemes via successive interference cancellation (SIC). The discussion is not restricted to lattice quantizers, and we will see that SIC can be applied for any product code. Afterwards, we will specialize the discussion to lattice quantizers. In Section II we argued that the relevant setup for LLMs is the uninformed/ΣX -oblivious decoder case. We introduced there the problem of quantizing a single column of the weight matrix. In practice, however, a weight matrix will typically have a ≫ 1 column vectors, and the WMSE matrix ΣX is common to all of them (as they all operate on the same activations). If the number of column vectors is of the same order as n, it is possible for the decoder to send an O(n) bits description of ΣX to the uninformed decoder with only a negligible effect on the quantization rate. In particular, the encoder can apply a diagonal matrix A = diag(α1 , . . . , αn ) ∈ Rn×n , whose spacing coefficients {αi } are chosen based on ΣX , and quantize W using the codebook A · C rather than the codebook C. The cost of reporting (α1 , . . . , αn ) to the decoder, is amortized over the a columns of the weight matrix, which makes it negligible provided that a is not too small. In fact, spacing the codebook C used for the reconstruction of W to the codebook A · C is
8
equivalent to changing X ⊤ to X ⊤ A. Consequently, in LLMs it is sometimes the case that A can be absorbed in the activations using the layer-norm with no additional cost associated with describing the scales [11]. Our focus is on obtaining efficient approximate solution to the optimization in equation (6), which becomes equivalent to the optimization in (7) when ΣX = U ⊤ U is decomposed using the Cholesky decomposition. Assume the codebook C ⊂ Rn is a product codebook of the form C = C1 × · · · × Cn , where Ci ⊂ R ∀i ∈ [n].
(21)
Product codebooks are a common practical choice as it allows for fast (and parallel) decoding. Under the MSE criterion (corresponding to ΣX = In ) they also result in fast optimal encoding, as in this case U = In and (7) becomes n X ŴMSE = argmin (Wi − ci )2 c1 ∈C1 ,...,cn ∈Cn i=1
=⇒ ŴMSE,i = argmin(Wi − ci )2 ,
∀i ∈ [n]. (22)
ci ∈Ci
Under the WMSE criterion, corresponding to nondiagonal ΣX , product codebooks do not in general lend themselves to fast optimal encoding algorithms. In particular, if C = Zn = Z × · · · × Z, then exactly solving the optimization in (7) requires solving the closest vector problem (CVP) in the lattice L̃ = U Zn , as observed in [18], [19]. This problem is known to be NP-hard. Consequently, one must resort to sub-optimal algorithms. Here, we restrict attention to successive interference cancellation (SIC). The most general form of this algorithm is provided in Algorithm 1 and illustrated in Figure 2. In generalSIC the n codebooks C1 , . . . , Cn ⊂ R whose product is C ⊂ Rn can be arbitrary, and each of them is further scaled by the corresponding αi . This scaling can in general be absorbed in the codebooks definition. However, since we allow A to depend on ΣX through the matrix U ∈ Rn×n while the codebooks C1 , . . . , Cn are not allowed to depend on ΣX , we do not absorb A into the codebooks. In generalSIC, we first filter the vector Y using the feedforward filter F ∈ Rn×n . Any matrix F ∈ Rn×n can be used here. Then, the vector Ŵ is generated sequentially, starting from Ŵn up to Ŵ1 . At every step i the scalar (F Y )i is fed to the quantizer to generate Ŵi , and then the vector F Y is updated to F Y − Ŵi B:,i . The feedback matrix B ∈ Rn×n is strictly lowertriangular, due to causality. We have that Ŵ = AQ A−1 (F Y − B Ŵ ) . If the quantizer is modeled as adding independent quantization noise Z, we therefore obtain Ŵ = (In + B)−1 F Y + (In + B)−1 AZ. Finally, the estimate Ŵ is further scaled by β > 0.
(23)
Let us temporarily fix the spacing matrix A. The choices of F and B and β, should strike a balance between two quantities. First, we want the ℓ2 norm of eY = Y − βU Ŵ = In − βU (In + B)−1 F Y − βU (In + B)−1 AZ (24) to be as small as possible. On the other hand, we also want Ŵ to have differential entropy as small as possible, as this will dictate the volume of the shaping region required for capturing it (or equivalently, the average rate of encoding the quantizer’s output using entropy coding). However, in the limit of large quantization rate, where the energy of Z vanishes, the optimal choice of F, B, β tends to the solution for which In − βU (In + B)−1 F = 0. This corresponds to choosing βHigh−Rate = 1, FHigh−Rate = (diag(U ))−1 , BHigh−Rate = (diag(U ))−1 U − In .
(25)
If we use the generalSIC algorithm with F, B, β from (25), and use the same scalar codebook C0 for quantizing all coordinates, the algorithm simplifies to Algorithm 2 which we simply call the SIC algorithm. As we shall see below, the choice of A has an important impact on the scheme’s performance. In the special case where A = αIn for some α > 0, the SIC algorithm becomes completely equivalent to the canonical GPTQ algorithm (which in turn, is equivalent to the LDLQ algorithm [17]). This equivalence was recently shown in [18], [19]. Thus, in the sequel, we refer to SIC with A = αIn as the GPTQ algorithm. Note however that the GPTQ algorithm was originally presented in [4] from a noise-shaping point of view, where the quantization noise is filtered and fed to the next quantizer. In the SIC point of view, it is the signal Y , rather than the quantization noise, that is filtered and fed to the next quantizer. We find the SIC point of view of [18], [19] more intuitive than the original noise-filtering perspective. Furthermore, under the SIC point of view, the problem is also similar to V-BLAST decoding for the Gaussian MIMO channel [31]. In practice, the sub-codebook C0 is often taken as the constellations corresponding to data-type FP8, FP4, INT8, etc., resulting in Ŵ that can be used in fast MatMul hardware. For the remainder of our discussion we will assume C0 = Z, such that the product codebook is a lattice. In this case, the SIC algorithm is merely a low-complexity sub-optimal algorithm for the closest vector problem, which is often also referred to as Babai’s nearest plane algorithm [32]. For small n the spheredecoder [33], [34] can be used, and for large n other
9
Algorithm 1 generalSIC Inputs: Y ∈ Rn , feed-forward filter F ∈ Rn×n , strictly upper triangular feedback filter B ∈ Rn×n , diagonal spacing matrix A = diag(α1 , . . . , αn ) ∈ Rn×n + , scaling coefficient β > 0 and codebooks C1 , . . . , Cn ⊂ R Outputs: Ŵ ∈ C1 × · · · × Cn . Y ← FY for i = n : 1 do Ŵi ← αi Qi αYii
▷ Qi (x) = argminci ∈Ci (x − ci )2
Y ← Y − Ŵi · B:,i end for Ŵ ← β Ŵ
▷ B:,i is the ith column of B
Algorithm 2 SIC Inputs: Y ∈ Rn , upper triangular U ∈ Rn×n , diagonal matrix A = diag(α1 , . . . , αn ) ∈ Rn×n and scalar + codebook C0 ⊂ R Outputs: cSIC ∈ C0⊗n for i = n : 1 do cSIC,i ← αi Q αiYUii,i ) Y ← Y − cSIC,i · U:,i end for
Y
F
+ -
▷ Q(x) = argminc∈C0 (x − c)2 ▷ U:,i is the ith column of U
A−1
Q(·)
A
Ŵ
β
U
Ŷ
+ -
eY
B Fig. 2: Illustration of the generalSIC quantization algorithm. The matrix F ∈ Rn×n is unrestricted, whereas the matrix B ∈ Rn×n must be strictly upper triangular due to causality. The matrix A ∈ Rn×n is positive diagonal, and determines the spacing of the quantizer in each coordinate. The parameter β > 0 is a scaling parameter. The GPTQ algorithm is obtained as a special case for B, F, β taken as in (25), and A = αIn . The WaterSIC algorithm is obtained with the same F, B, β, but with A = diag(α1Water , . . . , αnWater ) and αiWater are given in (29) sub-optimal algorithms can equally be used instead of SIC. We now analyze the distortion attained by the SIC algorithm, with C0 = Z. The resulting Ŵ is in the lattice AZn , whose cardinality is unbounded. The description of Ŵ in bits will be handled via shaping or entropy coding, and for now we only constrain the point Qn density of L = (α1 Z) × · · · × (αn Z) to γ(L)−1 = ( i=1 αi ) = αn . Recall that from Proposition 1 and (19) we have that even if the optimal solution to (7) is found, the distortion |2/n must satisfy D ≳ α2 |ΣX 2πe . Note that for C0 = Z, the quantizer Q used in the SIC algorithm takes the simple form Q(x) = round(x) so that the execution of the SIC algorithm is particularly simple. The next result can be deduced from [32], and we bring the simple proof for completeness.
Lemma 1: Assume we apply the SIC Algorithm with y ∈ Rn , upper triangular U ∈ Rn×n , and Ci = αi Z for all i ∈ [n]. Then eSIC = y − U · cSIC ∈ P{Ui,i ,αi }ni=1 , where P{Ui,i ,αi }ni=1 =
n Y |αi Ui,i | |αi Ui,i | , . − 2 2 i=1
If in addition eSIC ∼ Uniform(P{Ui,i ,αi }ni=1 ) we have that 1 DSIC ≜ E∥Y − U · cSIC ∥2 n n 1 1X · (αi Ui,i )2 . (26) = 12 n i=1
10
Proof. Let cSIC (y, U ) be the result of applying the SIC algorithm with inputs y ∈ Rn and U ∈ Rn×n . Denote A = diag(α1 , . . . , αn ) ∈ Rn×n . The lemma follows from combining the two following observations: 1) P{Ui,i ,αi }ni=1 = {y ∈ Rn : cSIC (y, U ) = 0}; 2) For any z ∈ Zn it holds that cSIC (y + U Az, U ) = Az + cSIC (y, U ). Thus the SIC algorithm induces the partition of space to decision regions Dz = U Az + P{Ui,i ,αi }ni=1 , ∀z ∈ Zn
(27)
and cSIC (y, U ) = Az iff y ∈ Dz . Consequently, eSIC = y − U · cSIC (y, U ) ∈ P{Ui,i ,αi }ni=1 . The claim on DSIC immediately follows from the product structure of P{Ui,i ,αi }ni=1 . It follows from (26) that the distortion for the GPTQ algorithm followed by entropy coding is as given in (10). By the arithmetic-mean geometric-mean inequality (AM-GM) and (26) we have DSIC =
≥
1 12
n 1 1X (αi Ui,i )2 · 12 n i=1 ! n2 ! n2 n n Y Y 2 α2 αi |ΣX | n . Ui,i = 12 i=1 i=1
(28)
The inequality above is achieved with equality iff the scaling factors are of the form 1
|U | n , ∀i ∈ [n]. αiWater ≜ α · |Ui,i |
(29)
D. WaterSIC algorithm Motivated by (28) and (29), we propose Algorithm 3: the WaterSIC weight-only quantization algorithm for a weight matrix W ∈ Rn×a . The properties of the resulting reconstruction Ŵ are provided in Lemma 2. Lemma 2: The reconstruction Ŵ = diag(α1 , . . . , αn )ZSIC produced by the WaterSIC weight-only quantization algorithm satisfies: 1) Any column Ŵ:,j of Ŵ belongs to the lattice L = (α1 Z) × · · · × (αn Z) whose density is γ(L) = α−n n×a 2) U (W − Ŵ ) ∈ α|ΣX |1/2n · − 21 , 21 3) If we further assume U (W − Ŵ ) ∼ n×a Uniform α|ΣX |1/2n · − 12 , 12 then α2 |ΣX |1/n 1 DWaterSIC = E∥X ⊤ (W − Ŵ )∥2 = . an 12 n×a 4) Ŵ ∈ W + α|ΣX |1/2n · U −1 − 21 , 12 n×a 5) ZSIC ∈ A−1 W + Ũ − 21 , 12 where A = diag(α1 , · · · , αn ) and Ũ = α|ΣX |1/2n · (U A)−1 is an upper triangular matrix with unit determinant.
Fig. 3: Illustration of the quantization regions for the optimal lattice quantizer (blue) and for the WaterSIC T lattice quantizer √ (red) for ΣX = V ΛV where V = [1 1; 1 − 1]/ 2 and Λ = diag(3, 1). The lattice used for quantization is L = (α1 Z) × (α2 Z) where α1 , α2 are determined via (29), with α = 1. The proof is immediate in light of Lemma 1. Using (15), we see that if the resulting output ZSIC is encoded to bits via ball-shaping or entropy coding, the relation between α and quantization rate R is q 2 2−2R . α ≈ 2πeσW (30) Substituting this into item 3 of Lemma 2, gives (11). See [7, Theorem 3.3] for a precise statement. Remarkably, the waterfilling choice of scaling factors (29) result in a lattice whose distortion under the very simple SIC algorithm is only a factor of 2πe 12 ≈ 1.4233 from the lower bound (19). The loss of this factor is due to the fact that, while the weighted error U (W − Ŵ ) lies within a convex set in isotropic position, this set is a cube. The lower bound (19) on the other hand is achieved with equality only if the convex set supporting the weighted error is a ℓ2 -ball. The decision regions for the WaterSIC algorithm, as well as for the optimal lattice quantizer corresponding to L = (α1 Z) × (α2 Z) are illustrated in Figure 3. Shaping: There are several ways to represent ZSIC in bits. One way that is simple, but quite inefficient, is using the shaping region Srect = [−q1 , q1 ] × · · · × [−qn , qn ] where qi = ∥ZSICi,: ∥∞ , ∀i ∈ [n].
(31)
By definition, all entries of the ith row of ZSIC are in [−qi , qi ], so overload never occurs. Furthermore, the encoder can describe the shaping region to the decoder by sending {qi }ni=1 , with negligible rate if the number of rows is large. And the quantization rate using S̃rect is
11
Algorithm 3 WaterSIC weight-only quantization Inputs: W ∈ Rn×a , PSD matrix ΣX and point density α > 0. Outputs: ZSIC ∈ Zn×a and (α1 , . . . , αn ) ∈ Rn+ such that Ŵ = diag(α1 , . . . , αn )ZSIC . Compute upper-triangular U ∈ Rn×n such that ΣX = U ⊤ U ▷ Using the Cholesky decomposition Y ← UW 1 |U | n , ∀i ∈ [n] αi ← α · |U i,i | ZSIC ← 0n×a ▷ Initialize ZSIC with zeros for i = n : 1 do Y ▷ Yi,: and ZSIC,i,: is the ith row of Y and ZSIC , respectively ZSIC,i,: ← round αi Ui,:i,i W ← Y − αi U:,i · ZSIC,i,: ▷ U:,i is the ith column of U end for corresponding to this scheme is Zn ∩ S̃Lattice-Shaping where n n X X αi2 (yi − ti )2 αi2 yi2 ≤ S̃Lattice-Shaping = y ∈ Rn : i=1 ∀t ∈ LShaping . i=1
Fig. 4: Performance of several weight-only quantization schemes against benchmark. Here W ∼ N (0, In ) where n = 4096 and ΣX is the empirical covariance matrix computed from activation samples corresponding to Wv in the 15th layer of Llama3-8B.
(32)
The difficulty here is that the decoder needs to find the coset member that minimizes the scaled energy, which may be computationally intensive unless LShaping admits special properties. Some progress in finding LShaping that admit efficient decoding on GPUs was made in [36], [37]. There are many other options one can consider for shaping, which we did not list here. Finally, the encoder may simply use entropy coding (implemented via any lossless compression package. Note that modern GPU already include dedicated hardware for fast lossless compression/decompression) to describe the entries of ZSIC . E. Quantizing Llama-3-8B
Pn Rrect = n1 i=1 log(1 + 2qi ). Here, we have used the same reconstruction alphabet for an entire row of W . In general, one can decide on different ways to group elements that are described using the same reconstruction alphabet. While using the optimal group size can significantly boost performance, here we do not explore this. A better, but more complicated, way to perform shaping is via partitioning to cosets, much like in Forney’s trellis shaping [35], [27]. In particular, one can use a lattice LShaping ⊂ Zn , with covol(LShaping ) = 2nR , such that |Zn /LShaping | = 2nR . In other words, LShaping partitions Zn to 2nR cosets {zi + LShaping }, where z1 , . . . , z2nR ∈ Zn are coset representatives. In order to encode ZSIC,:,j (the jth column of ZSIC ) the encoder describes the coset it belongs to, using nR bits. The Pndecoder outputs the coset member z ∈ Zn for which i=1 αi2 zi2 is minimal. It is easy to verify that the reconstruction constellation
In Figure 4 we plot the rate-distortion curves attained by WaterSIC and GPTQ without tailored spacing (that is, with αi = α) under entropy coding or rectangular shaping corresponding to shaping with Srect from (31). We see that for high rates the ratio between WaterSIC EC and the fundamental limit D∗ (R) from (4) is indeed quite close to 2πe 12 ≈ 1.4233 (or 0.25 bit in rate). We also see that for this particular ΣX , at high resolution WaterSIC EC offers only limited gain with respect to GPTQ EC. However, the former is provably close to D∗ (R) at high-resolution, whereas the latter is not, and therefore the gap between them may be bigger for other layers, other LLMs, other calibration sets etc. Let us investigate difference between GPTQ and WaterSIC (entropy coded versions of both) further. Recall that in the high-rate regime, the rate advantage of WaterSIC over GPTQ is estimated as half logarithm of the ratio between arithmetic and geometric mean of squared diagonal entries of U , cf. (10) and (11). We illustrate this
12
(a) No random rotation.
(b) With random rotation.
Fig. 5: Illustrating rate advantage of WaterSIC over SIC for ΣX of activations entering various layers of Llama-38B when processing Wikitext-2 dataset. Squares correspond to layers with singular ΣX which we skip. Note that WaterSIC achieves (on random gaussian W ) identical performance with or without rotation.
rate advantage on Fig. 5 for all layers of Llama-3-8B. We compare both the case of using (Cholesky decomposition of the) original ΣX as well as V T ΣX V for a random orthogonal V . Recall that WaterSIC’s performance is independent of rotation, and hence identical in both figures, but the improvement over SIC is much smaller with random rotation. Let us consider implications of this finding. Cholesky factor interpretation. Recall that k-th diagonal entry Uk,k can be interpreted as follows. Think of activations (X1 , . . . , Xn ) as a stochastic process. Then, each sample Xk can be decomposed as ∥
Xk = Xk + Xk⊥ , ∥
where Xk is the component that is a linear combination of (X1 , . . . , Xk−1 ) (expressible in terms of Uk,j , j = 1, . . . , k − 1) and Xk⊥ is the orthogonal innovation con2 tained in Xk compared to previous coordinates. Uk,k = E[(Xk⊥ )2 ] is simply the energy of this innovation. Now, applying trace to the identity ΣX = U ⊤ U we get X
2 Uk,j =
n X
λj .
is somehow priviliged among all other possible ones, an effect whose origins are most likely due to operation of Adam [38], which introduces axis aligned outliers in activations. P 2 Cholesky in random basis. Can we estimate k Uk,k from knowing the spectrum {λj } of ΣX ? The answer is affirmative if one considers applying random rotation. One such estimate was offered (for a restricted class of ΣX ) by [17, Lemma 2]. However, one can get a more precise information about this sum. Indeed, when we take V to be a random orthogonal matrix and set ΣX = V T diag{λj }V , quantities {Uk,k } become functions of a random matrix V . One can show that2 (k) |ΣX | 2 Uk,k = (k−1) , |ΣX | (k)
where |ΣX | is a determinant of a k × k principal minor of ΣX . In dimensions of interest, these random quantities concentrate quickly around their expectations, which can be computed as3 1 X Y (k) E[|ΣX |] = n λi .
j=1
k,j
P 1
2 , that governs SIC’s Therefore, the average n k Uk,k P 1 performance (10), equals n j λj minus the sum of squares of off-diagonal entries of U . This implies, that GPTQ’s performance is the worst in the PCA basis (where U becomes diagonal), which is counter-intuitive. We also see that the gap between Diso (ΣX -oblivious encoder and decoder) and the waterfilling D∗ , which operates in the PCA-basis, is much higher than for GPTQ vs WaterSIC (compare gaps on Fig. 1 vs Fig. 5). Privileged basis. On the other hand, as we see from comparing two figures on on Fig. 5 applying random rotation clearly P 2improves performance of GPTQ, thus decreasing k Uk,k . This implies that the original basis is “closer” to the diagonalizing PCA basis than a randomly rotated one. This suggests that the standard basis for X
k
|S|=k i∈S
Thus, we can approximate: P Q k |S|=k i∈S λi P Q . (33) n − k + 1 |S|=k−1 i∈S λi Pn 2 2 In particular, U1,1 ≈ n1 j=1 λj and Un,n ≈ Pn n λ−1 j=1 j and the intermediate values smoothly decrease from the arithmetic mean to harmonic mean. This fact is numerically illustrated on Fig. 6. Consequently, performance of 2 Uk,k ≈
2 Simply notice that Σ(k) = U (k)⊤ U (k) . X 3 To see this, let Ṽ be a n × k matrix consisting of first k columns (k)
1
1
of V , then from Cauchy-Binet |ΣX | = |(Λ 2 Ṽ )⊤ (Λ 2 Ṽ )| = P Q 2 |S|=k i∈S λi |ṼS×[k] | . Taking expectation over V we have from 2 symmetry E[|ṼS×[k] | ] = c for all subsets S ⊂ [n]. When all λi = 1 −1 (k) . we must have |ΣX | = 1 and hence c = n k
13
2 Fig. 6: Illustrating Cholesky diagonals Uk,k for a randomly rotated V ⊤ ΣX V and accuracy of approximation (33) in terms of spectrum of ΣX .
GPTQ with random rotation can be accurately estimated from combining (10) and (33). It is an interesting open problem to estimate worst possible gap (over possible spectra λj ≥ ϵ) between GPTQ with rotation and WaterSIC (which in turn is 0.25-bit away from informationtheoretically optimal waterfilling). WaterSIC vs “universal codebook”. We note that theoretical results from [16], discussed in Section II-C, demonstrated that solving (6) optimally essentially attains full waterfilling solution even in low rates, and furthermore does so with a fully ΣX -oblivious codebook. Note that WaterSIC chooses per-coordinate scales −1 αi ∝ Ui,i (Cholesky decomposition of) ΣX and, thus, requires large a ≫ 1 to amortize sending of αi ’s in high precision (usually BF16). The results in [16] on the other hand, are valid for any a ≥ 1.
F. Future of weight-only quantization The high-resolution approximations (16) and (17) in Subsection III-B, combined with the analysis of WaterSIC in Subsection III-D, show that when WaterSIC followed by EC or close-to-optimal spherical shaping is used, we attain the optimal information theoretic distortion from (5) up to a multiplicative gap of 2πe 12 . Figure 4 numerically confirms the accuracy of the highresolution approximations. Furthermore, Figure 5 shows that with random rotation even the vanilla GPTQ algorithm, which is completely equivalent to the widely used GPTQ/LDLQ algorithms, achieves distortion only slightly greater than WaterSIC, and is therefore nearly optimal. In light of this, one may wonder whether the practical schemes are already so good that there is no further room for improvement. We claim that this is not the case, and list several important directions for improved quantization schemes: First, in this survey paper we restricted attention to the high-rate regime. At small quantization rates (say 0.5−2
bits per entry) many other effects will become important: necessity of Johnson-Lindenstrauss dimensionality reduction, as shown in [2], shrinkage and other lowrate effects. Proper shaping and exploiting structure of W matrices will be paramount. Indeed, at low rates [7] shows WaterSIC to have massive advantage over GPTQ, even if the latter is Huffman coded. Second, even our analysis for the high-resolution regime relied on applying EC or near-optimal spherical shaping after quantization. While EC over Z can be efficiently implemented, even on modern GPUs EC decompression is about an order of magnitude slower than loading the uncompressed entries. Thus, the usefulness of EC for running quantized models on a GPU is somewhat questionable. On the other hand, simple shaping methods that can be easily made efficient, e.g. rectangular shaping, may be highly suboptimal (see Figure 4). The problem of shaping schemes that are amenable to fast GPU implementation is at its infancy [12]. Third, while the 2πe 12 high-resolution gap-to-optimality of WaterSIC+EC is relatively small, reducing it further is of interest. This gap stems from the sub-optimality of the integer lattice Zn as a quantizer. Generally, we can decrease this gap by combining WaterSIC with jointly quantizing d entries from the same row of W to a lattice L′ ⊂ Rd , followed by EC. If we use the optimal lattice ′ quantizer in Rd we can reduce the 2πe 12 gap to optimality to 2πe · Gd where Gd is the optimal normalized second moment in dimension d. See [39, Table I] for a list of the best known NSM for 1 ≤ d ≤ 48 as of 2023 (some improvements were reported in certain dimensions since then). The downside of replacing Z with a higherdimensional lattice is that EC of the quantizer’s output becomes more challenging as its cardinality is much larger. Fourth, implementation of WaterSIC relies on the fact that sending per-channel scales αi can be amortized freely, which is only the case when one has many output
14
neurons in a linear layer (large a ≫ 1). ACKNOWLEDGMENT We thank Alina Harbouzova, Egor Lifar, and Semyon Savkin (MIT EECS) for numerous discussions and help with obtaining calibration matrices for Llama-3-8B. R EFERENCES [1] O. Ordentlich and Y. Polyanskiy, “High-rate quantized matrix multiplication I,” 2026. [2] ——, “Optimal quantization for matrix multiplication,” arXiv preprint arXiv:2410.13780, 2024. [3] M. Nagel, R. A. Amjad, M. Van Baalen, C. Louizos, and T. Blankevoort, “Up or down? adaptive rounding for post-training quantization,” in International conference on machine learning. PMLR, 2020, pp. 7197–7206. [4] E. Frantar, S. Ashkboos, T. Hoefler, and D. Alistarh, “OPTQ: Accurate quantization for generative pre-trained transformers,” in The Eleventh International Conference on Learning Representations, 2023. [Online]. Available: https: //openreview.net/forum?id=tcbBPnfwxS [5] T. Dettmers, M. Lewis, Y. Belkada, and L. Zettlemoyer, “Gpt3. int8 (): 8-bit matrix multiplication for transformers at scale,” Advances in Neural Information Processing Systems, vol. 35, pp. 30 318–30 332, 2022. [6] B. Hassibi, D. G. Stork, and G. J. Wolff, “Optimal brain surgeon and general network pruning,” in IEEE international conference on neural networks. IEEE, 1993, pp. 293–299. [7] E. Lifar, S. Savkin, O. Ordentlich, and Y. Polyanskiy, “Watersic: information-theoretically (near) optimal linear layer quantization,” arXiv preprint arXiv:2603.04956, 2026. [8] Y. Li, R. Gong, X. Tan, Y. Yang, P. Hu, Q. Zhang, F. Yu, W. Wang, and S. Gu, “Brecq: Pushing the limit of posttraining quantization by block reconstruction,” arXiv preprint arXiv:2102.05426, 2021. [9] A. Tseng, Z. Sun, and C. De Sa, “Model-preserving adaptive rounding,” arXiv preprint arXiv:2505.22988, 2025. [10] H. Badri and A. Shaji, “Half-quadratic quantization of large machine learning models,” November 2023. [Online]. Available: https://mobiusml.github.io/hqq_blog/ [11] G. Xiao, J. Lin, M. Seznec, H. Wu, J. Demouth, and S. Han, “Smoothquant: Accurate and efficient post-training quantization for large language models,” in International Conference on Machine Learning. PMLR, 2023, pp. 38 087–38 099. [12] S. Savkin, E. Porat, O. Ordentlich, and Y. Polyanskiy, “NestQuant: Nested lattice quantization for matrix products and LLMs,” arXiv preprint arXiv:2502.09720, 2025. [13] S. Zhang, H. Zhang, I. Colbert, and R. Saab, “Qronos: Correcting the past by shaping the future... in post-training quantization,” arXiv preprint arXiv:2505.11695, 2025. [14] H. Zhang, S. Zhang, I. Colbert, and R. Saab, “Provable posttraining quantization: Theoretical analysis of optq and qronos,” arXiv preprint arXiv:2508.04853, 2025. [15] Y. Polyanskiy and Y. Wu, Information theory: From coding to learning. Cambridge university press, 2024. [16] A. Harbuzova, O. Ordentlich, and Y. Polyanskiy, “Price of metric universality in vector quantization is at most 0.11 bit,” arXiv preprint arXiv:2602.05790, 2026. [17] J. Chee, Y. Cai, V. Kuleshov, and C. M. De Sa, “Quip: 2bit quantization of large language models with guarantees,” Advances in Neural Information Processing Systems, vol. 36, pp. 4396–4429, 2023. [18] J. Chen, Y. Shabanzadeh, E. Crnčević, T. Hoefler, and D. Alistarh, “The geometry of llm quantization: Gptq as babai’s nearest plane algorithm,” arXiv preprint arXiv:2507.18553, 2025. [19] J. Birnick, “The lattice geometry of neural network quantization– a short equivalence proof of gptq and babai’s algorithm,” arXiv preprint arXiv:2508.01077, 2025.
[20] R. Zamir, Lattice Coding for Signals and Networks: A Structured Coding Approach to Quantization, Modulation, and Multiuser Information Theory. Cambridge University Press, 2014. [21] A. Tseng, J. Chee, Q. Sun, V. Kuleshov, and C. De Sa, “Quip#: Even better llm quantization with hadamard incoherence and lattice codebooks,” arXiv preprint arXiv:2402.04396, 2024. [22] O. Ordentlich, O. Regev, and B. Weiss, “Bounds on the density of smooth lattice coverings,” arXiv preprint arXiv:2311.04644, 2023. [23] W. R. Bennett, “Spectra of quantized signals,” The Bell System Technical Journal, vol. 27, no. 3, pp. 446–472, 1948. [24] P. Panter and W. Dite, “Quantization distortion in pulse-count modulation with nonuniform spacing of levels,” Proceedings of the IRE, vol. 39, no. 1, pp. 44–48, 1951. [25] P. Zador, “Asymptotic quantization error of continuous signals and the quantization dimension,” IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 139–149, 1982. [26] A. Gersho, “Asymptotically optimal block quantization,” IEEE Transactions on information theory, vol. 25, no. 4, pp. 373–380, 1979. [27] M. V. Eyuboglu and G. D. Forney, “Lattice and trellis quantization with lattice-and trellis-bounded codebooks-high-rate theory for memoryless sources,” IEEE Transactions on Information theory, vol. 39, no. 1, pp. 46–59, 1993. [28] R. Zamir and M. Feder, “On lattice quantization noise,” IEEE Transactions on Information Theory, vol. 42, no. 4, pp. 1152– 1159, 1996. [29] J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, 3rd ed., ser. Grundlehren der mathematischen Wissenschaften. New York: Springer-Verlag, 1999, vol. 290. [30] O. Ordentlich, “The Voronoi spherical cdf for lattices and linear codes: New bounds for quantization and coding,” arXiv preprint arXiv:2506.19791, 2025. [31] P. W. Wolniansky, G. J. Foschini, G. D. Golden, and R. A. Valenzuela, “V-blast: An architecture for realizing very high data rates over the rich-scattering wireless channel,” in 1998 URSI international symposium on signals, systems, and electronics. Conference proceedings (Cat. No. 98EX167). IEEE, 1998, pp. 295–300. [32] L. Babai, “On lovász’lattice reduction and the nearest lattice point problem,” Combinatorica, vol. 6, no. 1, pp. 1–13, 1986. [33] U. Fincke and M. Pohst, “Improved methods for calculating vectors of short length in a lattice, including a complexity analysis,” Mathematics of computation, vol. 44, no. 170, pp. 463– 471, 1985. [34] E. Agrell, T. Eriksson, A. Vardy, and K. Zeger, “Closest point search in lattices,” IEEE transactions on information theory, vol. 48, no. 8, pp. 2201–2214, 2002. [35] G. D. Forney, “Trellis shaping,” IEEE Transactions on Information Theory, vol. 38, no. 2, pp. 281–300, 1992. [36] S. Savkin, E. Porat, O. Ordentlich, and Y. Polyanskiy, “Nestquant: Nested lattice quantization for matrix products and llms,” Proc. International Conference on Machine Learning (ICML), 2025. [37] A. Tseng, Q. Sun, D. Hou, and C. De Sa, “Qtip: Quantization with trellises and incoherence processing,” arXiv preprint arXiv:2406.11235, 2024. [38] N. Elhage, R. Lasenby, and C. Olah, “Privileged bases in the transformer residual stream,” Transformer Circuits Thread, 2023. [Online]. Available: https://transformer-circuits.pub/2023/ privileged-basis/index.html [39] E. Agrell and B. Allen, “On the best lattice quantizers,” IEEE Transactions on Information Theory, vol. 69, no. 12, pp. 7650– 7658, 2023.