GPTQ-2D Cuts Two-Sided Weight Quantization to Cubic Time

Adaptive rounding is the workhorse behind most post-training LLM quantization, and GPTQ is the version that most open source stacks actually ship. A new arXiv preprint from Jiale Chen, Torsten Hoefler, and Dan Alistarh, out of the IST Austria and ETH Zürich groups, extends the same idea to a two-sided objective, where fixed nonsingular basis matrices act on both the left and the right of the residual, and does it in cubic rather than quartic time.

The setup matters because rotation and calibration transforms keep getting wrapped around weight matrices in modern quantization pipelines. If you write the two-sided objective out via vectorization, the Gram matrix becomes a Kronecker product and the standard one-dimensional Babai-style sweep still works, but it takes quartic time in the matrix dimension, which for real weight tensors is prohibitive. GPTQ-2D processes entries anti-diagonal by anti-diagonal instead, exploits the Kronecker structure so that each rounding error is a rank-one update to the residual, and lands at O(max(m,n)³). The authors also prove, in what they label Theorem 2, that the trajectory reproduces the naive vectorized nearest-plane sweep exactly.

The practical hook is that entries on the same anti-diagonal are independent, so the sweep parallelizes. A literature review write-up on The Moonlight describes the blocked implementation the paper proposes: a window of anti-diagonals processed together, band-like matrix products for error propagation, and a padded skewed array layout aimed at GPU memory access patterns.

The honest caveat is that this is an algorithms paper. There are no LLM accuracy numbers in the material, no wall-clock kernels benchmarked against existing GPTQ / AWQ / QuIP implementations, and no reference to a shipped kernel. Take the complexity result and the equivalence theorem as the settled part, and the deployment story as an open question.

Where this could land, if an implementation follows, is in the rotation-heavy and mixed-precision stacks where the two-sided formulation was the natural fit but the quartic cost made it uneconomical. The Alistarh group's prior work has tended to make it into open-source quantizers reasonably quickly, which is the part worth watching.