GPTQ › Mathematical Details of the Update

The inverse Hessian update is a necessary mathematical component that lets efficient processing. After quantizing column $q$, we need to update the inverse Hessian to reflect that column $q$ is no longer a free variable. The weight at column $q$ has been fixed to its quantized value; it can no longer be adjusted to compensate for future quantization errors. Mathematically, we need to compute a new inverse Hessian that covers only the remaining unquantized weights $F \setminus \{q\}$.

Let $\mathbf{H}_F^{-1}$ denote the inverse Hessian restricted to the remaining (unquantized) weights. After removing column and row $q$, the new inverse is given by the Schur complement formula:

where:

• $[\mathbf{H}_{F \setminus q}^{-1}]_{ij}$: the updated inverse Hessian element at row $i$, column $j$, after removing weight $q$
• $[\mathbf{H}_F^{-1}]_{ij}$: the current inverse Hessian element before the update
• $[\mathbf{H}_F^{-1}]_{iq}, [\mathbf{H}_F^{-1}]_{qj}$: elements from the $q$-th column and row of the current inverse Hessian
• $[\mathbf{H}_F^{-1}]_{qq}$: the diagonal element corresponding to weight $q$
• $i, j$: indices ranging over the remaining unquantized weights in $F \setminus \{q\}$

This formula is a rank-one update, subtracting an outer product that corresponds to removing the degree of freedom at position $q$. The intuition is that by fixing weight $q$, we eliminate one dimension from our optimization space. The remaining weights must "account for" the fact that they can no longer rely on $w_q$ to absorb any future compensation. The Schur complement formula computes exactly how the correlations between remaining weights change when one weight is removed from consideration.

Computing this update naively as a dense matrix operation would cost $O(d^2)$ per column. Over all $d$ columns, this would total $O(d^3)$, which is the same as just re-inverting the Hessian from scratch each time. The Cholesky decomposition gives the escape from this cost.

The Cholesky factorization gives us $\mathbf{H}^{-1} = \mathbf{L}\mathbf{L}^T$ where $\mathbf{L}$ is lower triangular. This factorization is particularly useful because the triangular structure directly encodes the sequential dependencies between weights. For column $q$, the required compensation coefficients $[\mathbf{H}^{-1}]_{q+1:,q}$ are exactly the entries in the $q$-th column of $\mathbf{L}$ (below the diagonal). The update formula simplifies to reading off the next column of $\mathbf{L}$ rather than performing a full matrix update, reducing the per-column cost to $O(d)$ after the initial $O(d^3)$ Cholesky factorization. This is why the total complexity of GPTQ is $O(d_{in}^3)$ per layer: dominated by the one-time Cholesky factorization, with all subsequent operations being linear in $d_{in}$.