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

Abstract

GPTQ is Babai's nearest-plane algorithm on the lattice of the Cholesky factor of the layer's input second moment $\Sigma$. In the high-rate, entropy-coded regime it needs $\tfrac12\log_2(\AM/\GM)$ of its Cholesky pivots more bits than WaterSIC, which is within $0.255$ bit of the rate-distortion limit for every $\Sigma$; 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 $k$-th pivot converges almost surely, uniformly in $k\ge \delta n$ and over spectra $\nu$ of bounded condition number, to $1/S_{\nu }(-k/n)$, a classical formula from the theory of Lyapunov exponents, and use it to answer the question. Over spectra with condition number $\kappa$ the worst rotated gap is $\frac{1}{2}{\log }_2\kappa -{\log }_2\ln \kappa +\frac{1}{2}-\frac{1}{\ln 2}+o(1)$ bits, attained only by two-point spectra, just $\frac{1}{2}{\log }_2\ln \kappa +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 $\eta$-fraction of outlier eigenvalues of size $\mu$ from about $\eta \mu$ to ${\eta }^2\mu /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 $96$ Hessians of Qwen3 and Llama-3.1 the rotated gap has median $0.04$ bit and maximum $0.36$ bit, against $2$--$5$ bits in the worst case for the same condition numbers, and the limit matches it to within $0.009$ bit.

arXiv comment28 pages, 3 figures