GPTQ › The GPTQ Algorithm

The naive OBQ approach would quantize weights one at a time, choosing at each step the weight whose quantization causes the smallest loss increase $\Delta\mathcal{L}_q$. While this greedy strategy seems sensible, its computational cost is prohibitive. Each step requires examining all remaining weights to find the best candidate, and after quantizing each weight, we must update the inverse Hessian. This requires $O(d_{in}^2)$ operations per weight, yielding $O(d_{in}^3)$ complexity per row and $O(d_{in}^4)$ for the entire layer. For a model where $d_{in}$ can be 4096 or larger, $O(d_{in}^4)$ operations are completely impractical.

GPTQ makes three key modifications that reduce the total complexity to $O(d_{in}^3)$ while maintaining nearly identical accuracy. The central observation is that the optimal quantization order matters less than one might expect. The compensation mechanism is powerful enough that processing weights in a fixed sequential order yields results almost as good as the optimal greedy order. What matters most is performing the compensation correctly after each quantization step.

Think of the three optimizations as different aspects of making the same core algorithm more efficient, like optimizing a factory assembly line. Column-wise processing batches the work across all output neurons simultaneously (vectorization). Lazy batch updates reduce the number of times we touch memory by accumulating changes before applying them (cache efficiency). Cholesky-based inverse updates replace a naive matrix inversion with a factorization that can be maintained cheaply as we process each column (algorithmic efficiency).

Column-wise processing. Instead of quantizing weights one at a time in optimal order, GPTQ processes all weights in a fixed left-to-right column order. The important insight is that all rows of the weight matrix share the same Hessian, because all output neurons see the same inputs. This means we can process all rows simultaneously for a given column, quantizing column $q$ of every output neuron at once. This vectorization turns a sequential loop over rows into a single matrix operation, achieving a large constant-factor speedup.

Lazy batch updates. Rather than updating all remaining weights after each individual column quantization, GPTQ accumulates updates in blocks (typically of size 128) and applies them all at once when the block is complete. This improves cache efficiency sharply because memory access patterns become more localized. Weight matrix rows are stored contiguously in memory, and processing a full block before writing updates means each memory location is accessed sequentially rather than randomly.

Cholesky-based inverse updates. Computing and maintaining the full inverse Hessian naively would cost $O(d_{in}^2)$ per column after the initial $O(d_{in}^3)$ inversion, yielding $O(d_{in}^3)$ total work just for the updates. GPTQ instead precomputes the Cholesky decomposition $\mathbf{H}^{-1} = \mathbf{L}\mathbf{L}^T$ where $\mathbf{L}$ is lower triangular. The triangular structure of $\mathbf{L}$ directly encodes the sequential dependencies between weights: the $q$-th column of $\mathbf{L}$ gives the compensation coefficients needed when processing column $q$. After processing column $q$, we simply move to the next column of $\mathbf{L}$ without any additional update. This reduces the per-column cost from $O(d_{in}^2)$ to $O(d_{in})$ after the initial factorization.

Here is the complete GPTQ procedure in detail:

1. Collect calibration data. Run a small set of representative examples through the model, using forward hooks to record each layer's inputs $\mathbf{X}$ as the data flows through.

2. Compute the Hessian. For each layer, compute $\mathbf{H} = 2\mathbf{X}\mathbf{X}^T$ and add a small diagonal dampening term $\lambda \mathbf{I}$ for numerical stability. Compute the inverse $\mathbf{H}^{-1}$ via Cholesky decomposition.

3. Process each row of the weight matrix. For each row $\mathbf{w}$:

   a. For each column $q$ from 0 to $d_{in} - 1$:

   • Quantize: $\hat{w}_q = \text{quantize}(w_q)$
   • Compute error: $\delta_q = w_q - \hat{w}_q$
   • Update remaining weights: $w_{q+1:} \leftarrow w_{q+1:} - \frac{\delta_q}{[\mathbf{H}^{-1}]_{qq}} \cdot [\mathbf{H}^{-1}]_{q+1:,q}$

   b. Store the quantized row $\hat{\mathbf{w}}$ along with per-group scale and zero-point parameters.

4. Replace the layer's weights with their quantized integer values plus the associated dequantization metadata.

The order in which columns are processed affects accuracy. The default left-to-right order works reasonably well, but ActOrder (processing columns in decreasing order of Hessian diagonal) often improves results by quantizing the most important weights first, when there are still many remaining weights available to absorb compensation. We will explore ActOrder in detail later in this chapter.