cs.ITNov 1, 2026

How Much Does Random Rotation Help GPTQ? Sharp Worst-Case Rate Gaps in the High-Rate Regime

Authors: Runguo Li

Organizations: University of Illinois Urbana-Champaign (UIUC)

Abstract

GPTQ is Babai's nearest-plane algorithm on the lattice of the Cholesky factor of the layer's input second moment ΣΣ. In the high-rate, entropy-coded regime it needs 12log⁡2(\AM/\GM)\tfrac12\log_2(\AM/\GM) of its Cholesky pivots more bits than WaterSIC, which is within 0.2550.255 bit of the rate-distortion limit for every ΣΣ; random rotations close most of this gap in practice, and Ordentlich and Polyanskiy asked for the worst-case gap between rotated GPTQ and WaterSIC. We show that after a Haar rotation the kk-th pivot converges almost surely, uniformly in k≥δnk\geδn and over spectra νν of bounded condition number, to 1/Sν(−k/n)1/S_ν(-k/n), a classical formula from the theory of Lyapunov exponents, and use it to answer the question. Over spectra with condition number κκ the worst rotated gap is 12log⁡2κ−log⁡2ln⁡κ+12−1ln⁡2+o(1)\tfrac12\log_2κ-\log_2\lnκ+\tfrac12-\tfrac1{\ln2}+o(1) bits, attained only by two-point spectra, just 12log⁡2ln⁡κ+O(1)\tfrac12\log_2\lnκ+O(1) bits below the worst case without rotation, so rotation cannot replace waterfilling in general. It nearly can on real layers: rotation cuts the cost of an ηη-fraction of outlier eigenvalues of size μμ from about ημημ to η2μ/2η^2μ/2 to leading order, but cannot remove spectral spread on a logarithmic scale; for non-Gaussian weights it also adds a weight-side rate cost, which we characterize exactly under a standard high-rate assumption. On 9696 Hessians of Qwen3 and Llama-3.1 the rotated gap has median 0.040.04 bit and maximum 0.360.36 bit, against 22--55 bits in the worst case for the same condition numbers, and the limit matches it to within 0.0090.009 bit.

Figures & tables

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

May 13, 2026

High-Rate Quantized Matrix Multiplication II

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Σ_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Σ_X and, thus, unlike existing schemes, is immune to applying random rotations); and (b) within a multiplicative factor of 2πe12\frac{2π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Σ_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.
Mar 5, 2026

WaterSIC: Information-Theoretically (Near) Optimal Linear Layer Quantization

This paper considers the problem of converting a given dense linear layer to low precision. The tradeoff between compressed length and output discrepancy is analyzed information theoretically (IT). It is shown that a popular GPTQ algorithm may have an arbitrarily large gap to the IT limit. To alleviate this problem, a novel algorithm, termed ``WaterSIC'', is proposed and is shown to be within a rate gap of 0.255 bits to the IT limit, uniformly over all possible covariance matrices of input activations. The key innovation of WaterSIC's is to allocate different quantization rates to different columns (in-features) of the weight matrix, mimicking the classical IT solution known as "waterfilling". Applying WaterSIC to the Llama and Qwen family of LLMs establishes new state-of-the-art performance for all quantization rates from 1 to 4 bits. Our code is available at https://github.com/egorlifar/watersic.
Jul 29, 2026

GPTQ-2D: Cubic-Time Two-Sided Adaptive Rounding

Adaptive rounding methods such as GPTQ quantize the weights of a large language model (LLM) one at a time, propagating each rounding error to the weights not yet rounded. YAQA lowers the KL divergence from the original model with two-sided adaptive rounding under a Kronecker-factored Hessian, but its error feedback takes quartic work in the size of a square layer. We present GPTQ-2D, which provably computes the same rounding with cubic work, while still rounding the entries of each anti-diagonal in parallel. Its GPU implementation uses two levels of blocking to improve hardware utilization. We also extend the algorithm to Hessians with any number of Kronecker factors. In our experiments, GPTQ-2D is as accurate as YAQA and cuts the time to quantize Llama-3.1-70B-Instruct on a single NVIDIA RTX A6000 GPU from 8.6 days to 1.6 hours. Source code is available at https://github.com/IST-DASLab/GPTQ-2D.