🤖 machine learning

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

This paper introduces GPTQ-2D, a cubic-time algorithm that efficiently performs two-sided adaptive rounding on matrices by processing entries in parallel along anti-diagonals, thereby reducing the computational complexity from the quartic time required by standard vectorization methods while producing identical results.

Original authors: Jiale Chen, Torsten Hoefler, Dan Alistarh

Published 2026-07-30

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Jiale Chen, Torsten Hoefler, Dan Alistarh

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to pack a massive, wobbly tower of Jenga blocks into a neat, rigid box. In the world of artificial intelligence, these "blocks" are numbers inside a giant spreadsheet (a matrix) that teaches a computer how to think. To make these computers run faster and use less energy, engineers try to shrink these numbers down to simple whole numbers (integers), a process called "quantization." But here's the catch: if you just chop off the decimals randomly, the tower collapses, and the computer starts making silly mistakes.

To fix this, scientists use a clever trick called "adaptive rounding." Think of it like a game of dominoes. When you knock over one domino (round a number), it creates a tiny wobble. Instead of ignoring that wobble, adaptive rounding catches it and pushes it forward to the next domino in line, adjusting it slightly so the whole line stays straight. This method, known as GPTQ, has been a superstar for years, but it only works well when the dominoes are arranged in a single, long line. However, modern AI models are more like a giant, two-dimensional grid of dominoes, where knocking one over affects its neighbors both to the right and below. Trying to fix this 2D grid with the old "one-line" method is like trying to untangle a knot by pulling on just one end—it works, but it takes forever and gets stuck in a loop that is four times slower than necessary.

This paper introduces a new way to untangle that knot, called GPTQ-2D. The authors, Jiale Chen, Torsten Hoefler, and Dan Alistarh, discovered that you don't need to pull the dominoes one by one in a long line. Instead, you can grab entire diagonal rows of dominoes and fix them all at the same time. By realizing that the "wobble" from one block only travels down and to the right, they found a shortcut that lets them process the whole grid in a fraction of the time. They proved mathematically that this new method produces the exact same perfect tower as the slow, old way, but it does it in "cubic" time (which is fast) rather than "quartic" time (which is painfully slow). This means we can now shrink these giant AI brains much more efficiently without breaking them, making powerful AI more accessible on everyday devices.

The Story of the Two-Sided Puzzle

Let's dive into the mechanics of this puzzle. In the old one-sided method (GPTQ), imagine you have a row of people passing a heavy backpack. If the first person drops a coin, they tell the next person to carry a little extra weight to compensate. This happens one person at a time, moving down the line. It works great for a single file line.

But in the real world of AI, the "people" are arranged in a grid, like a checkerboard. Now, if a person in the middle drops a coin, that weight needs to be shared with everyone standing below them and everyone standing to the right of them. If you try to fix this grid by walking through every single square one by one (the "vectorized" approach), you end up doing a massive amount of redundant work. It's like trying to clean a whole room by wiping every single inch of the floor, even the parts you've already cleaned, over and over again. The math shows this takes a huge amount of time, growing so fast that if you double the size of the grid, the work quadruples (or even more).

The authors of this paper looked at this grid and realized something magical: the "wobble" or error from any single square only travels in a specific direction—down and to the right. This creates a dependency graph that looks like a staircase. If you look at the grid diagonally (from top-right to bottom-left), you'll see that all the squares on the same diagonal line are independent of each other. They don't affect one another!

This is the "Aha!" moment. Because they are independent, you can round all the numbers on a single diagonal line at the same time, like a wave crashing across the board. This is the core of GPTQ-2D.

The Magic of the "Lazy" Buffer

So, how do they make this fast? In the old "slow" way, every time you fixed a number, you would immediately go and update every single square in the huge rectangle below and to the right of it. That's a lot of busy work.

The new GPTQ-2D algorithm is much lazier (in a good way). Instead of updating the whole rectangle immediately, it just pushes the error down its own column and across its own row, leaving a "note" in a buffer. It's like a teacher who, instead of walking to every student's desk to correct a mistake, just writes the correction on the student's own desk and on the desk of the student to their right. The students further down the line will eventually see these notes and fix themselves.

By using this "lazy" approach, the algorithm avoids the heavy lifting of updating the entire grid constantly. It processes the grid in "waves" (the anti-diagonals). Each wave takes a tiny bit of time, and because the waves can happen in parallel, the whole process speeds up dramatically.

The paper proves that this lazy, diagonal approach produces the exact same result as the slow, one-by-one method. It's not an approximation; it's a mathematical guarantee. The authors show that whether you fix the dominoes one by one or in diagonal waves, the final tower stands exactly the same.

Why This Matters

The paper doesn't just guess that this is faster; they did the math to prove it. For a square grid (where the number of rows equals the number of columns), the old method takes time proportional to the size of the grid to the fourth power ( $O(m^2n^2)$ ). The new GPTQ-2D method takes time proportional to the size to the third power ( $O(m^3)$ ).

To put that in perspective: if you have a grid that is 1,000 by 1,000, the old method is doing a billion times more work than necessary compared to the new method. The new method brings the cost of fixing a two-sided grid down to the same level as fixing a simple one-sided line.

The authors also describe a "blocked" version of this algorithm (Algorithm 4), which groups these diagonal waves into chunks. This is designed to work even better on modern computer chips, which love to do big chunks of math all at once rather than tiny, scattered bits. This makes the theory ready for real-world use.

In short, this paper takes a problem that was too slow to be practical for large, complex AI models and gives it a speed boost that makes it feasible. It shows that by changing the order in which we look at the data—swapping a straight line for a diagonal wave—we can solve a two-sided puzzle as easily as a one-sided one, without losing any accuracy. It's a reminder that sometimes, the fastest way to fix a problem isn't to work harder, but to look at the problem from a different angle.

Technical Summary of "GPTQ-2D: Cubic-Time Two-Sided Adaptive Rounding"

1. Problem Statement

The paper addresses the problem of two-sided adaptive rounding, a generalization of the standard one-sided matrix rounding used in quantization methods like GPTQ (Frantar et al., 2023) and Babai's nearest plane algorithm (Babai, 1986).

One-Sided Case: Given a real matrix $X \in \mathbb{R}^{m \times n}$ and a fixed nonsingular basis matrix $A \in \mathbb{R}^{m \times m}$ , the goal is to find an integer matrix $Z$ minimizing $\|A(Z - X)\|_F^2$ . This is solved greedily by processing entries in a fixed order (e.g., column-major), propagating rounding errors via a triangular feedback matrix. This approach runs in $O(m^2 \max(m, n))$ time (cubic for square matrices).
Two-Sided Case: The paper introduces a second fixed nonsingular basis matrix $B \in \mathbb{R}^{n \times n}$ acting on the right, changing the objective to:
$\|A(Z - X)B\|_F^2 = \|(B^\top \otimes A)(\text{vec}(Z) - \text{vec}(X))\|_2^2$
Here, $\otimes$ denotes the Kronecker product. While this can be solved by vectorizing the matrix into a length-$mn$ vector and applying standard 1D adaptive rounding, the resulting Gram matrix is $H \otimes G$ (where $H=BB^\top, G=A^\top A$ ). A direct sweep over all $mn$ coordinates incurs $O(m^2 n^2)$ time complexity (quartic for square matrices), which is computationally prohibitive for large matrices.

The core challenge is to achieve the exact same rounding trajectory as the vectorized 1D approach but with reduced computational complexity, ideally matching the cubic cost of the one-sided case.

2. Methodology

The authors propose GPTQ-2D, an algorithm that exploits the specific structure of the Kronecker product to reduce complexity from quartic to cubic.

Key Theoretical Insights:

Kronecker Feedback Structure: The feedback matrix for the vectorized problem is $F = U^\top \otimes L$ , where $L$ and $U$ are the unit lower/upper triangular factors derived from the inverses of the Gram matrices $G$ and $H$ .
Rank-One Updates: A rounding error at entry $(i, j)$ generates a feedback update of the form $L_{:,i} E_{ij} U_{j,:}$ . This is a rank-one update supported only on the lower-right rectangle $\{i, \dots, m\} \times \{j, \dots, n\}$ .
Anti-Diagonal Independence: Because the update from $(i, j)$ only affects entries $(p, q)$ where $p \ge i$ and $q \ge j$ , entries on the same anti-diagonal ( $i+j = s$ ) are mutually independent. They can be processed in parallel once all preceding anti-diagonals are completed.

Algorithmic Approach:

Anti-Diagonal Sweep: Instead of a column-major or row-major sweep, the algorithm processes the matrix in $m+n-1$ stages, corresponding to anti-diagonals.
Lazy Propagation (The "Buffer" Trick):
- A naive implementation of the anti-diagonal sweep would still require $O(m^2 n^2)$ work because applying the rank-one update $L_{:,i} E_{ij} U_{j,:}$ densely touches a large block of the matrix.
- GPTQ-2D avoids this by maintaining an auxiliary buffer $C = LE$.
- When an entry $(i, j)$ is rounded, the error $E_{ij}$ is propagated only along its specific column (via $L$ ) and row (via $U$ ) immediately.
- The "bulk" of the rectangle update is deferred. The algorithm pushes the error down the column into the buffer $C$ , and later, the buffer values are pushed rightward along the rows.
- This "push" strategy ensures that each entry is updated exactly once per dependency, reducing the sweep cost to $O(mn \max(m, n))$ .
Blocked Implementation: To improve practical performance on parallel hardware, the authors introduce a blocked variant (Algorithm 4). This processes $w$ anti-diagonals at a time, accumulating errors in a block and flushing them to the rest of the matrix using band-like matrix products, similar to the lazy block updates in GPTQ.

3. Key Contributions

Formulation: The paper recasts two-sided matrix rounding as vector rounding under a Kronecker metric, proving that the resulting feedback is rank-one and separable.
Complexity Reduction: It demonstrates that the two-sided problem can be solved in $O((\max(m, n))^3)$ time, matching the asymptotic cost of one-sided GPTQ, rather than the $O(m^2 n^2)$ cost of a direct vectorized sweep.
Exact Equivalence: Theorem 2 proves that GPTQ-2D produces the identical rounded matrix as the standard 1D adaptive rounding algorithm applied to the vectorized input, provided a deterministic tie-breaking rule is used.
Order Invariance: The paper establishes (Theorem 1) that adaptive rounding is invariant to the order of processing, provided the order respects the feedback dependencies (i.e., a topological sort of the dependency graph). This justifies the anti-diagonal parallel sweep.

4. Results and Complexity Analysis

Time Complexity:
- Factorization: Computing the LDL decompositions of the inverse Gram matrices takes $O((\max(m, n))^3)$ .
- Sweep: The rounding sweep takes $O(mn \max(m, n))$ .
- Total: For square matrices ( $m=n$ ), the total complexity is $O(m^3)$ , a significant improvement over the $O(m^4)$ of the direct dense approach.
Parallelism: The algorithm naturally supports parallelism with $m+n-1$ stages. Within each stage (anti-diagonal), all entries can be processed simultaneously.
Memory: The working storage is $O((\max(m, n))^2)$ for the factors and $O(mn)$ for the sweep buffers.

5. Significance and Claims

The paper positions GPTQ-2D not as a competitor to one-sided GPTQ, but as a necessary extension for scenarios requiring two-sided metrics (e.g., Kronecker-factored Hessians in quantization).

Extension of GPTQ: The authors state that one-sided rounding is the special case where $B=I$ . GPTQ-2D extends this capability to the two-sided case without incurring a $\Theta(\min(m, n))$ factor increase in computational cost.
Practical Utility: The algorithm is designed to be a drop-in replacement for the rounding step in existing two-sided methods like YAQA (Tseng et al., 2026). While YAQA also utilizes anti-diagonal sweeps, its reference implementation uses dense matrix products, resulting in quartic complexity. GPTQ-2D provides the same rounding trajectory with cubic complexity, making it feasible for large-scale applications.
Modest Scope: The paper explicitly avoids claims of global optimality (noting that finding the exact closest lattice point is NP-hard) and focuses strictly on the efficiency of the greedy, adaptive rounding trajectory defined by the metric. It does not propose new applications but rather optimizes the computational cost of existing two-sided rounding formulations.