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

Jiale Chen, Torsten Hoefler, Dan AlistarharXiv 2026 · arXiv

This paper introduces GPTQ-2D, an algorithmic breakthrough that makes two-sided adaptive rounding for matrix quantization computationally practical. By reducing the complexity from quartic to cubic time, the authors enable more sophisticated quantization techniques that could improve the compression of large-scale neural networks.

TL;DR

GPTQ-2D brings two-sided adaptive rounding—a powerful but previously slow technique for matrix quantization—down to the same $O(N^3)$ complexity as standard one-sided GPTQ. By exploiting the Kronecker structure of error feedback, the algorithm enables parallel rounding along anti-diagonals without sacrificing the exactness of the rounding trajectory.

What Problem Does This Paper Address?

Quantizing neural network weights (converting high-precision floats to low-bit integers) is essential for deploying large models on edge devices. GPTQ is a popular "one-sided" method that rounds weights while propagating errors to subsequent entries in the same row or column.

However, "two-sided" rounding—which considers dependencies across both rows and columns simultaneously—could theoretically yield better results. The catch? A naive implementation requires vectorizing the matrix, turning an $N \times N$ problem into a $N^2$ vector problem. This leads to a computational cost of $O(N^4)$, which is prohibitively expensive for modern LLM weight matrices (e.g., $4096 \times 4096$). The authors aim to bridge this gap, making two-sided rounding as efficient as the one-sided version.

Methods

The authors recast two-sided matrix rounding as a vector rounding problem under a Kronecker-factored metric. Their key technical contributions include:

  1. Rank-One Feedback: They derive a formula showing that a rounding error at entry $(i, j)$ produces a rank-one update that only affects the "lower-right" rectangle of the matrix (rows $\ge i$, columns $\ge j$).
  2. Anti-Diagonal Parallelism: Because of this specific dependency structure, entries on the same anti-diagonal do not depend on each other. This allows them to be rounded in parallel.
  3. GPTQ-2D Algorithm: Instead of applying dense updates, the algorithm maintains auxiliary buffers and propagates errors "lazily." It pushes errors only along their own rows and columns, while the rest of the matrix is updated in bulk later.
  4. Padded Skew Layout: To make this efficient on modern hardware (like GPUs), they propose a specialized memory layout. This layout ensures that anti-diagonals, rows, and columns can all be accessed as efficient memory slices with fixed strides.

Datasets

Not discussed in the paper. This is a purely algorithmic and theoretical paper focused on proving the equivalence and complexity of the new rounding method. It does not include empirical evaluations on specific LLM benchmarks.

Key Insights and Ideas

  • Order Invariance (Theorem 1): The authors prove that the final rounded result is identical regardless of the processing order, as long as the order respects the underlying dependency graph. This justifies moving from a sequential column-major sweep to a parallel anti-diagonal sweep.
  • Exploiting the Kronecker Structure: The "aha moment" is realizing that the feedback matrix for two-sided rounding is a Kronecker product of two smaller triangular matrices. This structure is what allows the $O(N^4)$ to $O(N^3)$ reduction.
  • The Dependency Graph: The flow of information is strictly top-to-bottom and left-to-right. As shown in Figure 1, this creates "wavefronts" of independent entries.
The dependency graph shows that entries on the same anti-diagonal (red) are independent and can be processed in parallel.

Key Results

  • Complexity Reduction: The rounding sweep cost is reduced from $O(m^2 n^2)$ to $O(mn \max(m, n))$. For a square $N \times N$ matrix, this is a leap from quartic ($N^4$) to cubic ($N^3$) time.
  • Exact Equivalence: Theorem 2 proves that GPTQ-2D produces the exact same rounded matrix as the much slower vectorized version.
  • Asymptotically "Free" Extension: For cases where the number of rows $m$ is greater than or equal to the number of columns $n$, the two-sided extension adds no asymptotic cost over standard one-sided GPTQ in terms of setup, sweep, or sequential depth.

Limitations and Future Work

  • Fixed Basis Assumption: The proof of equivalence assumes that the basis matrices (which define the rounding metric) are fixed. If these matrices were to adapt dynamically during the rounding process, the $O(N^3)$ shortcut might not hold.
  • Greedy Nature: Like the original GPTQ, this is a greedy algorithm (a variant of Babai’s nearest plane algorithm). It does not guarantee a globally optimal rounding, which remains an NP-hard problem.
  • Modeling vs. Algorithm: The paper provides the how (an efficient algorithm) but not the what (how to choose the best basis matrices $A$ and $B$ for a specific neural network). The authors suggest this as a separate modeling challenge for the community.

Summary updated

Abstract

Adaptive rounding methods such as GPTQ, or equivalently Babai's nearest plane algorithm, round a real matrix to integers under a quadratic metric. They process the entries in a fixed order, one at a time, propagating each rounding error to the entries not yet processed through a triangular feedback matrix. We study the two-sided version of this task, in which fixed nonsingular basis matrices act on both the left and the right of the residual; the familiar one-sided case is the special case of an identity right basis. Vectorizing the matrix turns the two-sided objective into a quadratic metric whose Gram matrix is a Kronecker product, so the one-dimensional algorithm applies verbatim, but takes quartic time in the matrix dimension. We present GPTQ-2D, which produces the identical rounded matrix in cubic time. It rounds the entries anti-diagonal by anti-diagonal; entries on the same anti-diagonal are independent and are rounded in parallel.
BibTeX
@misc{chen2026gptq,
  author = {Jiale Chen and Torsten Hoefler and Dan Alistarh},
  title = {{GPTQ-2D: Cubic-Time Two-Sided Adaptive Rounding}},
  year = {2026},
  eprint = {2607.27042},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.27042},
}
Figure