GPTQ-2D: Cubic-Time Two-Sided Adaptive Rounding Jiale Chen
Institute of Science and Technology Austria (ISTA)
Torsten Hoefler Dan Alistarh
ETH Zürich Institute of Science and Technology Austria (ISTA) & Red Hat AI
arXiv:2607.27042v1 [cs.DS] 29 Jul 2026
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.
1 Introduction Adaptive rounding methods, such as GPTQ (Frantar et al., 2023) or equivalently Babai’s nearest plane algorithm (Babai, 1986), round a real matrix X ∈ Rm×n to an integer matrix Z ∈ Zm×n under a quadratic (squared) metric. In the one-sided case the metric is ∥A(Z − X)∥2F for a fixed nonsingular basis matrix A ∈ Rm×m . These methods do not exactly minimize that objective; they greedily process the entries in a fixed order, one at a time, rounding each entry to the nearest integer given the entries already rounded. After an entry is rounded, its rounding error is propagated to the not-yet-processed entries through a triangular feedback matrix obtained from an O(m3 ) factorization of the inverse of the m × m Gram matrix. Because this one-sided metric couples only the entries within each column, the n columns are then rounded independently in an O(m2 n) sweep. The total work is O(m2 max(m, n)), cubic in the dimension for a square matrix. This paper studies a two-sided version, adding a second fixed nonsingular basis matrix B ∈ Rn×n on the right, so that the metric becomes ∥A(Z − X)B∥2F = ∥(B ⊤ ⊗ A)(vec(Z) − vec(X))∥2 ,
(1)
where the second form uses the identity vec(A(Z − X)B) = (B ⊤ ⊗ A) vec(Z − X) with ⊗ denoting the Kronecker product and vec(·) denoting the vectorization operator.1 A one 1. We use column-major vectorization: the entry Xij of an m × n matrix becomes the (j − 1)m + i -th mn entry of vec(X) ∈ R .
1
dimensional adaptive rounding algorithm therefore applies to the mn vectorized coordinates. Now the right basis B couples the columns too, so they no longer decouple, and a direct sweep over all mn coordinates costs O(m2 n2 ), quartic for a square matrix. The Kronecker structure offers a shortcut. A rounding error at entry (i, j) contributes a rank-one update supported only on the lower-right rectangle anchored at (i, j) (rows ≥ i, columns ≥ j), so entries on the same anti-diagonal are independent and can be rounded in parallel. Our algorithm, which we call GPTQ-2D, exploits this: rather than applying each error’s rank-one update densely over its rectangle, it maintains the corrected matrix together with a buffer of accumulated feedback and pushes each error only along its own row and column as soon as it is produced. The rest of the rectangle is filled in lazily by the pushes of later entries. This reproduces the exact same rounding trajectory in only O(mn max(m, n)) sweep work, versus quartic for the direct sweep. With the one-time O((max(m, n))3 ) Gram factorization shared by both approaches, GPTQ-2D runs in O((max(m, n))3 ) work in total, cubic for square matrices, with a rounding sweep of m + n − 1 parallel stages. GPTQ-2D extends GPTQ rather than competing with it. One-sided adaptive rounding is the special case B = I. The question is what the extension costs. Reaching the same two-sided trajectory by vectorizing and sweeping costs O(m2 n2 ), a factor Θ(min(m, n)) more than the O(mn max(m, n)) sweep of GPTQ-2D. Removing that factor is what brings the two-sided problem down to the cost of the one-sided one: for m ≥ n both GPTQ and GPTQ-2D run in O(m3 ) work in total. Contributions. We recast two-sided matrix rounding as vector rounding under a Kronecker metric, and show that the resulting feedback is rank-one and separable, so entries on a shared anti-diagonal are independent. Building on that independence, we reduce the rounding sweep from the O(m2 n2 ) of a dense realization to O(mn max(m, n)). The resulting algorithm reproduces the exact one-dimensional adaptive rounding trajectory in O((max(m, n))3 ) work, which for m ≥ n matches the asymptotic cost of one-sided GPTQ on the same matrix. We prove the exact equivalence (Theorem 2) and describe a blocked, GPTQ-style implementation that turns the feedback into a few band-like matrix products (Section 4.3).
2 Related Work Adaptive rounding via second-order information. Pruning and quantization guided by second-order information originate with Optimal Brain Surgeon (Hassibi et al., 1993), which ranks weights by inverse-Hessian saliencies and applies a closed-form error-feedback update to the remaining weights. Optimal Brain Compression (Frantar & Alistarh, 2022) ports this exact one-at-a-time scheme to the layer-wise post-training objective whose per-row Hessian is the input second moment. GPTQ (Frantar et al., 2023) fixes a single column order shared across all rows. This lets the inverse Hessian be precomputed once as a Cholesky factor, which reduces the cost from quartic to cubic for a square layer and enables LLM-scale quantization. QuIP (Chee et al., 2023) recasts this triangular error feedback as LDLQ and proves it is equivalent to GPTQ. All of these methods are one-sided : a single Gram matrix acts on one side of the weight matrix.
2
Lattice and nearest-plane view. Rounding under a quadratic metric is exactly a sweep of Babai’s nearest plane algorithm for the closest vector problem on the lattice induced by the metric (Babai, 1986). This connection was made precise for GPTQ by Chen et al. (2026) and Birnick (2026): GPTQ’s column-sequential rounding with Cholesky error feedback coincides with Babai’s projection sweep. In this view a Kronecker Gram defines a tensorproduct lattice whose Cholesky factor is the Kronecker product of the per-axis Cholesky factors, and the nearest plane on each axis is the classical primitive. The lattice view also provides an error bound for GPTQ. However, it makes no global-optimality claim. Computing an exact closest lattice point is NP-hard in general (Dinur et al., 2003). Two-sided and Kronecker-factored rounding. Closest to our setting is YAQA (Tseng et al., 2026), which rounds under a Kronecker-factored Hessian by generalizing the LDLQ fixed-point iteration to a left and a right factor. Exploiting the Kronecker structure, it bounds the number of sweeps by at most m + n − 1, and its reference implementation already sweeps the block anti-diagonals of the weight matrix. Each sweep applies the feedback as dense matrix products, so the iteration amounts to O(mn(max(m, n))2 ) work, quartic for a square matrix. Up to the direction of the sweep, the two compute the same rounding: YAQA rounds in reverse order, from the last row and column, where GPTQ-2D rounds forward. GPTQ-2D computes it in O(mn max(m, n)) sweep work, cubic for a square matrix, so it can be dropped in as YAQA’s rounding step, leaving its Kronecker-factored Hessian sketch untouched.
3 Preliminaries This section recalls one-dimensional adaptive rounding (Section 3.1) and then states the two-sided problem (Section 3.2). 3.1 One-Dimensional Adaptive Rounding We first recall the standard one-dimensional adaptive rounding primitive. Let x ∈ Rd be an input vector, ⌊·⌉ the nearest-integer rounding operator, and F ∈ Rd×d a unit lower triangular feedback matrix. Adaptive rounding maintains a corrected vector y, initialized to y = x, and sweeps the coordinates in a fixed order. At coordinate k (k = 1, . . . , d) it rounds zk = ⌊yk ⌉,
(2)
Ek = zk − yk ,
(3)
records the local rounding error and propagates it to the remaining coordinates through the k-th column of F , y ← y + F:,k Ek .
(4)
Because F is unit lower triangular, this update affects only coordinates k, k + 1, . . . , d, so a single forward sweep suffices (Algorithm 1), at a cost of O(d2 ) arithmetic operations. Equivalently, if E ∈ Rd collects the local errors of the already-processed coordinates and is 3
zero elsewhere, the implicit corrected vector is y = x + F E.
(5)
The feedback matrix is fixed by the metric: for the one-sided objective ∥A(z − x)∥22 with a nonsingular basis A ∈ Rd×d and Gram A⊤ A, GPTQ takes F to be the unit lower triangular factor of the LDL decomposition of the inverse Gram, (A⊤ A)−1 = F ΛF F ⊤ (Chen et al., 2026). We keep F abstract in Algorithm 1 and specialize this construction to the Kronecker metric in Section 4.1. The two-dimensional algorithm developed below is the exact matrix analogue of Algorithm 1. Algorithm 1: One-dimensional adaptive rounding Input: input vector x ∈ Rd , unit lower triangular feedback F ∈ Rd×d Output: rounded vector z ∈ Zd 1: y ← x 2: for k = 1, . . . , d do 3: zk ← ⌊yk ⌉ 4: Ek ← zk − yk 5: yk:d ← yk:d + Fk:d,k Ek ▷ F unit lower triangular 6: end for 7: return z
3.2 Two-Sided Matrix Rounding We now pose the two-dimensional problem. Let X ∈ Rm×n be an input matrix and A ∈ Rm×m ,
B ∈ Rn×n
(6)
nonsingular basis matrices. We round X to an integer matrix Z ∈ Zm×n under the two-sided objective, written in terms of the residual R = Z − X as ∥A(Z − X)B∥2F = ∥ARB∥2F .
(7)
G = A⊤ A,
(8)
Define the two Gram matrices H = BB ⊤ .
Using the column-major vectorization identity vec(ARB) = (B ⊤ ⊗ A) vec(R) and the Kronecker mixed-product property (B ⊤ ⊗ A)⊤ (B ⊤ ⊗ A) = (BB ⊤ ) ⊗ (A⊤ A) = H ⊗ G, we obtain ∥ARB∥2F = vec(R)⊤ (H ⊗ G) vec(R). (9) Thus two-sided matrix rounding is exactly vector rounding of vec(X) under the Kronecker Gram matrix H ⊗ G, and the one-dimensional primitive of Section 3.1 applies with d = mn. The remainder of the paper develops an implementation that exploits the Kronecker structure to avoid the O(m2 n2 ) cost of a dense mn-dimensional sweep. 4
4 Theoretical Results We now lift the one-dimensional sweep of Section 3.1 to the two-sided problem. Section 4.1 specializes the feedback representation of Eq. (5) to the Kronecker metric, derives the rank-one matrix update, and shows that entries on a common anti-diagonal are independent and that the anti-diagonal sweep reproduces the vectorized trajectory (Theorem 1), giving a parallel but quartic dense implementation. Section 4.2 refines this into GPTQ-2D, a cubic-time algorithm that we prove reproduces the vectorized trajectory. Section 4.3 blocks that sweep so its many short updates collapse into a few band-like matrix products. Section 4.4 collects equivalent variants and compares their complexity. 4.1 Two-Sided Feedback and the Rank-One Update We apply the one-dimensional template to vec(X) ∈ Rmn under the Kronecker Gram H ⊗ G. By the one-dimensional construction of Section 3.1 applied along each axis, the row Gram G yields the unit lower triangular L ∈ Rm×m with G−1 = LΛL L⊤ , and the column Gram H yields the unit upper triangular U ∈ Rn×n whose transpose satisfies H −1 = U ⊤ ΛU U . Because the vectorized metric is the Kronecker product H ⊗ G, its inverse H −1 ⊗ G−1 is again a Kronecker product, and the LDL factor of a Kronecker product is the Kronecker product of the per-axis LDL factors; hence the vectorized feedback matrix is F = U ⊤ ⊗ L.
(10)
Let E ∈ Rm×n collect the local rounding errors. Combining the feedback representation of Eq. (5) with F = U ⊤ ⊗ L and the vectorization identity vec(LEU ) = (U ⊤ ⊗ L) vec(E), the implicit corrected matrix is Y = X + LEU. (11) Suppose the algorithm rounds entry (i, j) and produces local error Eij . Let J ij ∈ Rm×n be the matrix with a single one at entry (i, j) and zeros elsewhere. The contribution of this error to the corrected matrix is L(Eij J ij )U = L:,i Eij Uj,: ,
(12)
so a scalar rounding error at (i, j) produces the rank-one feedback update Y ← Y + L:,i Eij Uj,: .
(13)
This is the central two-dimensional feedback formula. Because L is lower triangular, the column L:,i is supported only on rows i, . . . , m; because U is upper triangular, the row Uj,: is supported only on columns j, . . . , n. Hence the rank-one update of Eq. (13) is supported only on the lower-right rectangle {i, . . . , m} × {j, . . . , n}. Grouping the entries by anti-diagonal, Is = {(i, j) ∈ {1, . . . , m} × {1, . . . , n} : i + j = s}, 5
s = 2, . . . , m + n,
(14)
X11
X12
X13
X14
X21
X22
X23
X24
X31
X32
X33
X34
Figure 1: The dependency graph of the two-sided sweep, for the 3 × 4 example. An arrow marks an immediate dependency; entry (i, j) receives feedback only from entries that reach it along the arrows (i′ ≤ i, j ′ ≤ j). Any topological order is admissible for Theorem 1. Entries of a common anti-diagonal, such as I4 (red), are mutually unreachable and round in parallel; the anti-diagonal sweep processes the graph in m + n − 1 such wavefronts. an update from (i, j) ∈ Is can reach (p, q) only if p ≥ i and q ≥ j; on the same anti-diagonal p+q = i+j forces (p, q) = (i, j). Thus entries on a common anti-diagonal are independent and may be rounded in parallel, once all previous anti-diagonals have been processed (Figure 1). Rounding by anti-diagonals deviates from the column-major order of the vectorized sweep, so we record that adaptive rounding is insensitive to any reordering that respects the feedback dependencies. Theorem 1 (Order invariance) Fix x ∈ Rd , a unit lower triangular feedback matrix F ∈ Rd×d , and a deterministic tie-breaking rule for ⌊·⌉. Say that coordinate k depends on coordinate k ′ , written k ′ ≺ k, if Fkk′ ̸= 0 and k ′ ̸= k, and call a visitation order admissible if it rounds k ′ before k whenever k ′ ≺ k. Adaptive rounding under every admissible order produces the same corrected values, the same local errors, and the same rounded vector z as the forward sweep of Algorithm 1. P Proof When coordinate k is rounded, its corrected value is yk = xk + k′ Fkk′ Ek′ , summed over the already-rounded coordinates k ′ . Already-rounded coordinates with k ′ ̸≺ k have Fkk′ = 0 and contribute nothing, while in an admissible order every k ′ ≺ k is already rounded; P hence yk = xk + k′ ≺k Fkk′ Ek′ , a fixed function of the errors of the ≺-predecessors of k. Because F is unit lower triangular, k ′ ≺ k implies k ′ < k, so strong induction on k gives the same errors, hence the same yk , zk = ⌊yk ⌉, and Ek , under every admissible order. The forward sweep of Algorithm 1 is itself admissible. Under the vectorized feedback of Eq. (10), the coefficient coupling coordinate (i, j) to (i′ , j ′ ) is F(j−1)m+i, (j ′ −1)m+i′ = Lii′ Uj ′ j , the coefficient of the rank-one update in Eq. (13); it is nonzero only if i′ ≤ i and j ′ ≤ j, and every such (i′ , j ′ ) other than (i, j) itself lies on an earlier anti-diagonal. The anti-diagonal sweep is therefore admissible, and by Theorem 1 it reproduces the exact trajectory of the column-major forward sweep of vec(X). The most direct realization keeps the corrected matrix Y = X + LEU explicitly, rounding each anti-diagonal in parallel and then applying the rank-one update of Eq. (13) for all of its entries (Algorithm 2). The additive updates commute, so the updates of each anti-diagonal 6
fuse into one dense update. Its anti-diagonal parallel depth is O(max(m, n)), but each of the mn rank-one updates touches a block of size up to mn, for O(m2 n2 ) work. Algorithm 2: Direct anti-diagonal dense updates Input: input matrix X ∈ Rm×n , nonsingular basis matrices A ∈ Rm×m and B ∈ Rn×n Output: rounded matrix Z ∈ Zm×n 1: L ← LDL (A⊤ A)−1 ▷ unit lower triangular row feedback ⊤ 2: U ← LDL (BB ⊤ )−1 ▷ unit upper triangular column feedback 3: Initialize Z ∈ Zm×n 4: Y ← X 5: for s = 2, . . . , m + n do 6: Is ← {(i, j) : 1 ≤ i ≤ m, 1 ≤ j ≤ n, i + j = s} 7: for all (i, j) ∈ Is in parallel do 8: Zij ← ⌊Yij ⌉ 9: Eij ← Zij − Yij 10: end for P ▷ fused dense rank-one updates 11: Y ← Y + (i,j)∈Is L:,i Eij Uj,: 12: end for 13: return Z
4.2 GPTQ-2D Algorithm Algorithm 3 (GPTQ-2D) is our main algorithm: it produces the same rounded matrix as the dense Algorithm 2 (Theorem 2) but in cubic instead of quartic time. Like Algorithm 2 it maintains the corrected matrix Y , but it also carries an auxiliary C = LE and propagates each rounding error only along its own row (through U ) and column (through L) rather than over the entire lower-right block. It rounds one anti-diagonal at a time, same as Algorithm 2. Note that there also exists a symmetric mirror algorithm that maintains D = EU instead. In Algorithm 3, each entry does an O(1) rounding and O(max(m, n)) feedback (a fold of length m − i + 1 into C and a downward push of length m − i that reuse one product M = L:,i Eij , plus a rightward push of length n − j), so the sweep costs O(mn max(m, n)) work in m + n − 1 parallel stages, cubic for a square matrix against the O(m2 n2 ) of the dense Algorithm 2. The one-time computation of L and U , which inverts the two Gram matrices and LDL-factorizes the inverses, costs O((max(m, n))3 ) and dominates, so the end-to-end cost is O((max(m, n))3 ). For a square matrix, it is the same order as the sweep itself. The working storage is O((max(m, n))2 ) for the factors and O(mn) for the sweep buffers.
Theorem 2 (Trajectory equivalence) Fix X, L, U , and a deterministic tie-breaking rule for ⌊·⌉. Algorithms 2 and 3 produce exactly the same rounded matrix Z as one-dimensional adaptive rounding of vec(X) under the feedback matrix U ⊤ ⊗ L. 7
Algorithm 3: GPTQ-2D Input: input matrix X ∈ Rm×n , nonsingular basis matrices A ∈ Rm×m and B ∈ Rn×n Output: rounded matrix Z ∈ Zm×n 1: L ← LDL (A⊤ A)−1 ⊤ 2: U ← LDL (BB ⊤ )−1 3: Initialize Z ∈ Zm×n 4: Y ← X 5: C ← 0 ∈ Rm×n ▷ buffer C = LE 6: for s = 2, . . . , m + n do 7: Is ← {(i, j) : 1 ≤ i ≤ m, 1 ≤ j ≤ n, i + j = s} 8: for all (i, j) ∈ Is in parallel do 9: Zij ← ⌊Yij ⌉ 10: Eij ← Zij − Yij 11: Mi:m,j ← Li:m,i Eij ▷ the error scaled down column i of L 12: Ci:m,j ← Ci:m,j + Mi:m,j ▷ fold the error into C = LE 13: Yi+1:m,j ← Yi+1:m,j + Mi+1:m,j ▷ push down 14: end for 15: for all (i, j) ∈ Is in parallel do 16: Yi,j+1:n ← Yi,j+1:n + Cij Uj,j+1:n ▷ push right 17: end for 18: end for 19: return Z
Proof The anti-diagonal sweep is admissible for Theorem 1 (Section 4.1). In this order, by vec(LEU ) = (U ⊤ ⊗ L) vec(E), the corrected value of adaptive rounding at entry (i, j) is Xij + (LEU )ij , where E collects the local errors (Line 10) of the entries rounded on earlier anti-diagonals (and is zero at (i, j) and beyond). By Theorem 1, it therefore suffices to show that each algorithm rounds every entry (i, j) at exactly this value. Algorithm 2 maintains Y explicitly and, after rounding each anti-diagonal, applies the rank-one updates of exactly its entries, so Y = X + LEU holds before every stage by construction. For Algorithm 3 we argue by induction on the anti-diagonal index s that every entry (i, j) ∈ Is is rounded (Line 9) at Yij = Xij + (LEU )ij . The auxiliary carries the invariant C = LE: each rounded entry folds its error down its own column of C through Line 12, which (since Lii = 1) adds the final i′ = i term of (LE)ij to Cij and propagates the error to the later rows at once. Two kinds of update have reached Yij by stage s: the rightward pushes (Line 16) of the rounded entries (i, j ′ ) with j ′ < j, each adding Cij ′ Uj ′ j , and the downward pushes (Line 13) of (i′ , j) with i′ < i, each adding Lii′ Ei′ j , so Yij = Xij +
X
Cij ′ Uj ′ j +
j ′ <j
X i′ <i
8
Lii′ Ei′ j .
(15)
Each Cij ′ denotes its value at push time (stage i + j ′ ), and that value is already final: since L is lower triangular, (LE)ij ′ involves only the errors Ei′ j ′ with i′ ≤ i, all produced by stage i + j ′ , and later folds into column j ′ modify only rows below i. The downward sum is exactly the missing j ′ = j term: since Eij = 0 before (i, j) is rounded and Lii = Ujj = 1, the invariant C = LE gives X
Lii′ Ei′ j =
i′ <i
X
Lii′ Ei′ j = (LE)ij = Cij = Cij Ujj .
(16)
i′ ≤i
Substituting into Eq. (15) and using C = LE, Yij = Xij +
X j ′ ≤j
Cij ′ Uj ′ j = Xij +
X
(LE)ij ′ Uj ′ j = Xij + (LEU )ij ,
(17)
j ′ ≤j
as required.
4.3 Blocked GPTQ-2D The feedback in Algorithm 3 consists of many short row and column updates. Such memorybound updates are far slower than dense matrix products on parallel hardware. GPTQ owes its practical speed to lazy block updates (Frantar et al., 2023): cheap updates within a block, then one dense matrix product that flushes the block’s accumulated error to all remaining coordinates. We port this idea to the anti-diagonal sweep. We process the sweep in blocks of w consecutive anti-diagonals, keeping a single global buffer C = LE across blocks (Algorithm 4). Within a block, we run Algorithm 3 with the fold and both pushes clipped at the block boundary, so every in-block update touches only the block’s w anti-diagonals. Index ranges outside the matrix bounds are skipped. After the block, two band-like matrix products deliver the remaining feedback to all later entries: a down flush of the band of E through L along the matrix columns, and a right flush of the block’s anti-diagonal band of C through U along the matrix rows. The down flush does double duty: the product it adds to a later entry Yij is exactly the part of the fold deferred past the block boundary, so the same product also completes the buffer C = LE below the block, at no extra matrix product. This is GPTQ’s lazy block update on anti-diagonals: many small updates collapse into two band-like matrix products per block. Since the w-wide windows of U and L shift with the receiving row or column, each flush runs efficiently as a batched matrix-vector multiplication with overlapping windows. Every feedback contribution of Algorithm 3, from one rounded entry to one later entry, is applied exactly once, either by a clipped push inside the block or by a flush; the buffer C = LE is maintained by the clipped fold within the block and completed for the later entries by the down flush, and all feedback from a block lands before the next block starts. Algorithm 4 therefore produces the same Z as Algorithm 3. The total feedback work is O(mn max(m, n)) for any block width w, as in Algorithm 3. 9
Algorithm 4: Blocked GPTQ-2D Input: input matrix X ∈ Rm×n , nonsingular basis matrices A ∈ Rm×m and B ∈ Rn×n , block width w Output: rounded matrix Z ∈ Zm×n 1: L ← LDL (A⊤ A)−1 ⊤ 2: U ← LDL (BB ⊤ )−1 3: Initialize Z ∈ Zm×n 4: Initialize E ∈ Rm×n 5: Y ← X 6: C ← 0 ∈ Rm×n ▷ buffer C = LE 7: for s0 = 2, 2 + w, 2 + 2w, . . . , 2 + ⌊(m + n − 2)/w⌋w do 8: s1 ← min(s0 + w − 1, m + n) 9: for s = s0 , . . . , s1 do 10: for all (i, j) ∈ Is in parallel do 11: Zij ← ⌊Yij ⌉ 12: Eij ← Zij − Yij 13: Mi:s1 −j, j ← Li:s1 −j, i Eij ▷ the error scaled down column i of L 14: Ci:s1 −j, j ← Ci:s1 −j, j + Mi:s1 −j, j ▷ fold within block into C = LE 15: Yi+1:s1 −j, j ← Yi+1:s1 −j, j + Mi+1:s1 −j, j ▷ push down, within block 16: end for 17: for all (i, j) ∈ Is in parallel do 18: Yi, j+1:s1 −i ← Yi, j+1:s1 −i + Cij Uj, j+1:s1 −i ▷ push right, within block 19: end for 20: end forS 21: I>s1 ← m+n ▷ all entries after the block s=s1 +1 Is 22: for all (i, j) ∈ I>s1 in parallel do 23: Mij ← Li, s0 −j:s1 −j Es0 −j:s1 −j, j ▷ band-like matrix product 24: Cij ← Cij + Mij ▷ outer fold: complete C = LE below the block 25: Yij ← Yij + Mij ▷ flush down 26: end for 27: for all (i, j) ∈ I>s1 in parallel do 28: Yij ← Yij + Ci, s0 −i:s1 −i Us0 −i:s1 −i, j ▷ flush right: band-like matrix product 29: end for 30: end for 31: return Z
4.4 Other Variants Beyond Algorithms 3 and 4, two further equivalent variants are deferred to the appendices. Appendix A gives a sequential nested form that sweeps column by column rather than by anti-diagonal, and Appendix B gives implicit-Y realizations that keep a single feedback buffer and reconstruct the corrected entries on demand. Both produce the same rounded matrix Z 10
(Theorem 1) and match the O(mn max(m, n)) sweep bound of GPTQ-2D. Table 1 compares the cost of all realizations. Table 1: Cost of computing the rounding trajectory, with µ = max(m, n). Setup forms the LDL factors of Gram inverses, sweep is the rounding pass, and depth counts sequential stages. GPTQ is listed for reference: it rounds under the one-sided objective, the special case B = I. For m ≥ n every entry of its row is matched by GPTQ-2D, at O(m3 ) setup, O(m2 n) sweep, and O(m) depth, so the two-sided extension is asymptotically free in all three costs. Method
Setup
Sweep
Depth
Algorithm
One-sided objective ∥A(Z − X)∥2F GPTQ
O(m3 )
O(m2 n)
O(m)
1
Two-sided objective ∥A(Z − X)B∥2F Vectorized adaptive rounding Direct anti-diagonal dense updates GPTQ-2D, buffered anti-diagonal Nested sequential sweep
O(µ3 ) O(µ3 ) O(µ3 ) O(µ3 )
O(m2 n2 ) O(m2 n2 ) O(mnµ) O(mnµ)
O(mn) O(µ) O(µ) O(mn)
1 2 3, 4, 6 5
5 Padded Skew Layout The blocked sweep of Section 4.3 touches three different access patterns: an anti-diagonal Is , a matrix column Y:,j , and a matrix row Yi,: . In an array-level framework (e.g., PyTorch) an update is efficient only when the entries it touches form a slice with a fixed stride and a fixed length; otherwise it degenerates into a gather. Anti-diagonals are not such slices in either the row-major or the column-major layout, so we store the working matrices in a layout in which all three patterns are. This layout is a property of the framework rather than of the algorithm: a kernel-level implementation can keep the natural layout and mask the out-of-range lanes of each anti-diagonal instead, in which case none of the padding below is needed. The construction. We store Y , Z, C, and E in a padded array of m + n − 1 rows with a common row stride r = 2m + n − 2 (Figure 2). Entry (i, j) is placed in row s = i + j at intra-row position m − 1 + j. Since s = i + j is constant along an anti-diagonal while the intra-row position increases with j, each anti-diagonal Is is a contiguous segment of one row, with its columns in the same left-to-right order as in the matrix. The three views. The same cells then serve the other two access patterns at fixed strides. Stepping down one matrix row within a fixed matrix column advances s by one and leaves the intra-row position unchanged, so a matrix column Y:,j is a vertical stride-r line; this is the view used by the downward push and by the down flush. Stepping right one matrix column within a fixed matrix row advances both s and the intra-row position by one, so a matrix row Yi,: is a diagonal stride-(r+1) line; this is the view used by the rightward push and by the right flush. Every access of the sweep is therefore a slice with a fixed stride and a fixed length. 11
◦
X11
∅
∅
∅
◦
X21 X12
∅
∅
s=4
X31 X22 X13
∅
s=5
∅
X32 X23 X14
s=6
∅
∅
X33 X24
◦
s=7
∅
∅
∅
X34
◦
s=2 s=3
◦
block w=2
◦
anti-diagonal Is : contiguous row (round) matrix column Y:,j : stride r (push down, flush) matrix row Yi,: : stride r+1 (push right, flush) a block of w anti-diagonals (flushed together)
Figure 2: The padded skew array, for a 3 × 4 example (rows = anti-diagonals; row stride r = 2m + n − 2 = 8). Entry (i, j) sits in row s = i + j at intra-row position m − 1 + j. Read with three strides, the same cells serve every access: an anti-diagonal is a contiguous row (red, stride 1); a matrix column Y:,j is a vertical stride-r line (blue); a matrix row Yi,: is a diagonal stride-(r+1) line (green). The dashed box marks a block of w consecutive anti-diagonals updated together, then closed by two flushes. The ∅ and ◦ cells hold no data. The padding. Two kinds of cell hold no data. The ∅ cells are positions that an anti-diagonal leaves empty because it has fewer than n entries. The ◦ cells at the upper left and lower right are where the two ends of a stride-(r+1) row line overhang. A row line can overhang by up to m − 1 positions at either end, so each row reserves m − 1 positions on each side of the band, giving the row stride r = 2(m − 1) + n = 2m + n − 2. Neither kind is ever read as data, since Algorithm 4 skips index ranges outside the matrix bounds, but both are allocated: a buffer occupies (m + n − 1)(2m + n − 2) cells to hold mn entries of data. That is Θ((max(m, n))2 ), so the overhead is mild for square matrices and grows with the aspect ratio. Since rounding X ⊤ under the swapped bases B ⊤ and A⊤ is equivalent, one may transpose the problem to the orientation with smaller m to reduce it.
6 Applications and Discussion The formulation separates two questions that applications often conflate. The first is algorithmic. Given a two-sided quadratic objective ∥A(Z − X)B∥2F , how does one efficiently compute the fixed-order rounding trajectory induced by its Kronecker metric? This paper answers that with an exact algorithm whose rounding sweep takes O(mn max(m, n)) work, a factor Θ(min(m, n)) below the vectorized sweep and, for m ≥ n, the same total order as one-sided GPTQ on the same matrix (Table 1). The second is about modeling. How should A and B be chosen in a given application? That question is separate. In neural network quantization, for instance, A and B may come from factors of Kronecker Hessian approximations. This paper does not address that estimation problem. The method should be read as a work-efficient way to carry out a given Kronecker-factored rounding, not as a new rounding rule. 12
There are two caveats. First, the equivalence guarantee assumes the basis matrices A and B, hence the feedback factors L and U , are fixed throughout the sweep; if they adapt to intermediate rounding decisions, for instance through data-dependent scaling, exact equivalence to the fixed vectorized procedure need not hold. Second, GPTQ-2D computes a fixed-order trajectory and makes no global-optimality claim; this is inherited from onedimensional adaptive rounding, and in particular from GPTQ, rather than introduced by the two-sided setting. Computing an exact closest rounding is NP-hard in general.
References László Babai. On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica, 6(1):1–13, March 1986. ISSN 1439-6912. doi: 10.1007/BF02579403. URL https://link.springer.com/article/10.1007/BF02579403. 1, 3 Johann Birnick. The lattice geometry of neural network quantization: A short equivalence proof of GPTQ and Babai’s algorithm. In The Fourteenth International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=L4SwHIZEaJ. 3 Jerry Chee, Yaohui Cai, Volodymyr Kuleshov, and Christopher M De Sa. QuIP: 2bit quantization of large language models with guarantees. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 4396–4429. Curran Associates, Inc., 2023. URL https://proceedings.neurips.cc/paper_files/paper/2023/file/0df38cd13520747 e1e64e5b123a78ef8-Paper-Conference.pdf. 2 Jiale Chen, Yalda Shabanzadeh, Elvir Crnčević, Torsten Hoefler, and Dan Alistarh. The geometry of LLM quantization: GPTQ as Babai’s nearest plane algorithm. In The Fourteenth International Conference on Learning Representations, 2026. URL https: //openreview.net/forum?id=NFB4QGGS65. 3, 4 I. Dinur, G. Kindler, R. Raz, and S. Safra. Approximating CVP to within almost-polynomial factors is NP-hard. Combinatorica, 23(2):205–243, April 2003. ISSN 1439-6912. doi: 10.1007/s00493-003-0019-y. URL https://link.springer.com/article/10.1007/s004 93-003-0019-y. 3 Elias Frantar and Dan Alistarh. Optimal brain compression: A framework for accurate posttraining quantization and pruning. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 4475–4488. Curran Associates, Inc., 2022. URL https://proceedings.neurips.cc /paper_files/paper/2022/file/1caf09c9f4e6b0150b06a07e77f2710c-Paper-Confe rence.pdf. 2 Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. OPTQ: Accurate quantization for generative pre-trained transformers. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?i d=tcbBPnfwxS. 1, 2, 9 13
Babak Hassibi, David G. Stork, and Gregory J. Wolff. Optimal brain surgeon and general network pruning. In IEEE International Conference on Neural Networks, volume 1, pp. 293–299, 1993. doi: 10.1109/ICNN.1993.298572. URL https://ieeexplore.ieee.org/ document/298572. 2 Albert Tseng, Zhaofeng Sun, and Christopher De Sa. Model-preserving adaptive rounding. In Forty-third International Conference on Machine Learning, 2026. URL https://open review.net/forum?id=PKFilPWjMI. 3
14
Appendix A. Nested Algorithm A sequential, column-major variant maintains the corrected matrix Y (initialized to X) and rounds it column by column. Column j is rounded top to bottom by the one-dimensional primitive of Section 3.1 under the row factor L, yielding the rounded-and-corrected column y; its accumulated error is then propagated to the not-yet-processed columns through the j-th row of U , Y ← Y + (y − Y:,j ) Uj,: .
(18)
Because U is unit upper triangular, this leaves columns 1, . . . , j − 1 untouched and sets column j to y. Algorithm 5 is the column-major form; the row-major mirror (rounding along rows under U , propagating through L) is symmetric. Visiting the entries in column-major order realizes the forward sweep of vec(X) itself, applying the identical rank-one feedback of Eq. (13), so the same Z is produced (Theorem 1). Each column costs an O(m2 ) inner sweep and an O(m(n − j)) propagation, so the total is O(mn max(m, n)) work in mn sequential steps. Algorithm 5: Nested form (column-major) Input: input matrix X ∈ Rm×n , nonsingular basis matrices A ∈ Rm×m and B ∈ Rn×n Output: rounded matrix Z ∈ Zm×n 1: L ← LDL (A⊤ A)−1 ⊤ 2: U ← LDL (BB ⊤ )−1 3: Initialize Z ∈ Zm×n 4: Y ← X 5: for j = 1, . . . , n do 6: y ← Y:,j 7: for i = 1, . . . , m do 8: Zij ← ⌊yi ⌉ 9: Eij ← Zij − yi 10: yi:m ← yi:m + Li:m,i Eij 11: end for 12: Y ← Y + (y − Y:,j )Uj,: ▷ propagate column error via U 13: end for 14: return Z
Appendix B. Implicit-Y Realizations The algorithms of Section 4.2 and Appendix A maintain the corrected matrix Y = X + LEU directly. An equivalent family instead keeps a single triangular-feedback buffer and reconstructs the corrected entries on demand. Grouping the rank-one feedbacks of Eq. (13) along columns accumulates the errors through L into the left buffer C = LE, so that 15
Y = X + CU and a current entry reads Yij = Xij + (CU )ij = Xij + Ci,1:j U1:j,j ;
(19)
after rounding, setting Eij changes only column j of C, giving the suffix update Ci:m,j ← Ci:m,j + Li:m,i Eij .
(20)
Sweeping anti-diagonal by anti-diagonal gives Algorithm 6; grouping along rows instead yields the symmetric right buffer D = EU with Y = X + LD. Both apply the identical feedback of Eq. (13), so they produce the same rounded matrix Z. The cost matches that of Algorithm 3: reading Ci,1:j U1:j,j costs O(j) for entry (i, j) and updating Ci:m,j costs O(m − i + 1), for a total of O(mn max(m, n)). Algorithm 6: Implicit-Y form (anti-diagonal) Input: input matrix X ∈ Rm×n , nonsingular basis matrices A ∈ Rm×m and B ∈ Rn×n Output: rounded matrix Z ∈ Zm×n 1: L ← LDL (A⊤ A)−1 ⊤ 2: U ← LDL (BB ⊤ )−1 3: Initialize Z ∈ Zm×n 4: C ← 0 ∈ Rm×n ▷ buffer C = LE 5: for s = 2, . . . , m + n do 6: Is ← {(i, j) : 1 ≤ i ≤ m, 1 ≤ j ≤ n, i + j = s} 7: for all (i, j) ∈ Is in parallel do 8: Yij ← Xij + Ci,1:j U1:j,j 9: Zij ← ⌊Yij ⌉ 10: Eij ← Zij − Yij 11: end for 12: for all (i, j) ∈ Is in parallel do 13: Ci:m,j ← Ci:m,j + Li:m,i Eij 14: end for 15: end for 16: return Z
16