SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot

In plain words

Large language models are expensive to run, and one way to shrink them is to remove many of their weights. The usual way to do this well is to retrain the model afterwards, which is too costly for models this large. This paper asks whether the weights can be removed in one go, with no retraining at all.

The method works one layer at a time. For each layer it runs a small set of generic text through the model and measures how the layer responds. When a weight is removed, the nearby weights are nudged so that the layer's output stays close to what it was. The removal order and the choice of which weights to remove are both made on the fly, using these measurements.

The authors report that half of the weights in the largest open GPT-style models can be removed this way with only a small loss in quality, and that the same procedure works for two hardware-friendly sparsity patterns. It can also be combined with reducing the precision of the remaining weights. All numbers in the paper are the authors' own measurements.

TL;DR

SparseGPT prunes each linear layer of a GPT-family model in one pass, with no retraining §1. For each layer it chooses a mask and updates the surviving weights to compensate for the removed ones, using a Hessian of the layer's inputs estimated from 128 calibration segments of 2048 tokens from C4 §3 §4. Author-reported: at 50% unstructured sparsity, OPT-175B reaches raw-WikiText2 perplexity 8.21 against 8.35 dense, and a full pruning run takes about 4 hours on one A100 80GB tab. 1 §4. The same method handles 2:4 and 4:8 patterns and combines with 4-bit weight quantization §3.3 §3.5 §4.1.

Problem

The strongest pruning methods need extensive retraining to recover accuracy, which is very costly at GPT scale §1 §5. One-shot methods that prune without retraining existed, but the accurate ones were too slow for billion-parameter models. The authors state that AdaPrune takes about 1.3 hours on a 350M model and about 4.3 hours on a 1.3B model, and extrapolate linearly to several hundred hours for 175B §2 §4.1.

The per-layer problem asks for a binary mask and updated weights that together minimise the squared output error on calibration inputs eq. 1 §2. Mask and weights are coupled, so the exact problem is NP-hard §2. Once the mask is fixed, each row of the weight matrix has a closed-form best reconstruction, but computing it row by row needs one matrix inversion per row, which costs O(d_row · d_col³) per layer eq. 2 §3.1.

The method assumes the trained model is fixed and a small amount of generic calibration text is available. No task data and no gradients are used during pruning §2 §4.

Method

Layer-wise objective. Each linear layer with weights \mathbf{W} and calibration inputs \mathbf{X} is pruned by solving

\operatorname{argmin}_{\mathbf{M},\,\widehat{\mathbf{W}}}\; \left\|\mathbf{W}\mathbf{X} - (\mathbf{M}\odot\widehat{\mathbf{W}})\mathbf{X}\right\|_2^2

where \mathbf{M} is a binary mask (0 = pruned) eq. 1 §2. The full model is compressed by processing blocks in order. Inputs to a block are the outputs of the already-pruned earlier blocks §4 opt.py.

Exact reconstruction, row by row. For a fixed mask, row i has the closed form below, where \mathbf{M}_i selects the unpruned inputs for that row eq. 2 §3.1:

\mathbf{w}^i_{\mathbf{M}_i} = \left(\mathbf{X}_{\mathbf{M}_i}\mathbf{X}_{\mathbf{M}_i}^\top\right)^{-1} \mathbf{X}_{\mathbf{M}_i}\left(\mathbf{w}_{\mathbf{M}_i}\mathbf{X}_{\mathbf{M}_i}\right)^\top

Different rows have different masks, so their inverses differ. This is the "different row-Hessian" problem §3.1 fig. 3.

Removing one weight at a time. The optimal brain surgeon (OBS) update removes weight m and adjusts the remaining weights by \boldsymbol{\delta}_m, at error \varepsilon_m eq. 3 §3.1:

\boldsymbol{\delta}_m = -\frac{w_m}{[\mathbf{H}^{-1}]_{mm}}\,\mathbf{H}^{-1}_{:,m}, \qquad \varepsilon_m = \frac{w_m^2}{[\mathbf{H}^{-1}]_{mm}}

Here \mathbf{H} = \mathbf{X}\mathbf{X}^\top. For a row, the loss is quadratic, so this update is exact. Removing weights one after another, each followed by its OBS update, ends at the same solution as the full reconstruction §3.1.

Sharing inverse Hessians across rows. SparseGPT fixes one column order j = 1, \ldots, d_\text{col}. It defines nested index sets U_j, where each U_{j+1} drops the smallest index of U_j eq. 4 §3.1:

U_{j+1} = U_j - \{j\}, \qquad U_1 = \{1,\ldots,d_\text{col}\}

The inverse for U_{j+1} follows from the inverse for U_j with one Gaussian elimination step, so the whole sequence costs O(d_col³) eq. 5 §3.1:

(\mathbf{H}_{U_{j+1}})^{-1} = \Big(\mathbf{B} - \tfrac{1}{[\mathbf{B}]_{11}}\,\mathbf{B}_{:,1}\mathbf{B}_{1,:}\Big)_{2:,\,2:}, \qquad \mathbf{B} = (\mathbf{H}_{U_j})^{-1}

Each of these inverses is computed once and reused for every row where the column being removed is in the mask §3.1. Columns are processed in order. Once a weight is pruned, it is frozen and not updated again. Each column's pruning error is pushed onto the columns to its right, which are still unprocessed, so error compensation uses as many free weights as possible §3.1. The paper calls this view "weight freezing" and notes that it is an exact column-wise greedy scheme eq. 6 §3.1.

Adaptive mask selection. Choosing the mask in advance, for example by magnitude, ignores the correlations that updates introduce §3.2. Instead, the mask is chosen in blocks of B_s = 128 columns, from the weights as they are at that point, by the OBS error score w^2 / [\mathbf{H}^{-1}]_{cc}^2. Within each block the lowest-scoring p\% are pruned §3.2 alg. 1. Sparsity can therefore differ between columns, which a fixed per-column rule cannot do §3.2.

Semi-structured patterns. For n:m sparsity, the block size is B_s = m. In each row, every group of m consecutive weights keeps the m-n highest scores and prunes n weights. A larger B_s is not useful here, because zeros cannot be spread unevenly across groups of size m §3.3.

Lazy batch updates and Cholesky. Following GPTQ, the method applies the updates for a block of B = 128 columns at once, and updates the columns after the block with one matrix product. It precomputes the inverse-Hessian information as a Cholesky factor for numerical robustness §3.4 alg. 1. Algorithm 1 is the authors' full unstructured version alg. 1.

Joint quantization. Frozen weights can also be quantized. The rounding error then takes the place of the pruning error eq. 7 §3.5:

\mathbf{E}_{:,\,j-i} \leftarrow \frac{\mathbf{W}_{:,\,j} - \mathbf{M}_{:,\,j}\cdot\text{quant}(\mathbf{W}_{:,\,j})} {[\mathbf{H}^{-1}]_{jj}}

Here \text{quant}(\cdot) rounds to the nearest level of the quantization grid. Pruning and quantization happen in one pass, so later pruning decisions see earlier rounding errors and the reverse §3.5.

Algorithm. The following transcribes the unstructured procedure of alg. 1 in Python-like form. Notes on the paper's and code's exact behaviour are in the Paper vs code section.

# SparseGPT, unstructured pruning of one linear layer  [alg. 1] [§3.4]
# Input:  weights (d_row, d_col); calibration inputs (d_col, n_tokens)
# Output: pruned weights, zero where the mask removes them

def sparsegpt_prune(weights, inputs, sparsity, block_size, mask_size, damp):
    # Hessian of the layer input, H = X X^T  [§3.1]
    # The code scales this by 2/n_seq; damping is relative, so the scale
    # cancels  [code: sparsegpt.py#L43-L46]
    hessian = inputs @ inputs.T              # (d_col, d_col)

    # Inputs that never fire: unit curvature and zero weights
    # (not described in the paper)  [code: sparsegpt.py#L66-L68]
    dead = diagonal(hessian) == 0
    hessian[dead, dead] = 1
    weights[:, dead] = 0

    # Add damp times the mean diagonal, here 1%  [app. A]
    # [code: sparsegpt.py#L72-L74]
    hessian = hessian + damp * mean(diagonal(hessian)) * identity

    # Upper Cholesky factor of H^-1; its rows supply the update terms and
    # its diagonal supplies the mask scores  [alg. 1] [§3.4]
    # [code: sparsegpt.py#L75-L78]
    chol_inv = cholesky_upper(inverse(hessian))  # (d_col, d_col)

    # 1 = kept, 0 = pruned  [alg. 1]
    keep = ones(d_row, d_col)
    for block_start in range(0, d_col, block_size):
        block_end = block_start + block_size
        # Errors of this block, applied lazily to the later columns
        # [alg. 1] [code: sparsegpt.py#L86-L89]
        errors = zeros(d_row, block_size)
        for column in range(block_start, block_end):
            # Every mask_size columns, prune the sparsity fraction with the
            # smallest w^2 / [H^-1]_cc^2 in that group  [§3.2] [alg. 1]
            # [code: sparsegpt.py#L96-L98]
            if column % mask_size == 0:
                group = range(column, column + mask_size)
                score = weights[:, group] ** 2
                score = score / diagonal(chol_inv)[group] ** 2
                keep[:, group] = score > low_fraction_threshold(score,
                                                               sparsity)
            # Target value: zero if pruned, quantized weight if kept
            # (quantize is the identity without quantization)  [eq. 7]
            target = keep[:, column] * quantize(weights[:, column])
            error = (weights[:, column] - target) / chol_inv[column, column]
            errors[:, column - block_start] = error
            # Error compensation on the rest of the block  [eq. 3] [alg. 1]
            # [code: sparsegpt.py#L121-L122]
            update = outer(error, chol_inv[column, column:block_end])
            weights[:, column:block_end] -= update
        # Lazy update of all columns after the block  [alg. 1]
        # [code: sparsegpt.py#L125-L128]
        later = chol_inv[block_start:block_end, block_end:]
        weights[:, block_end:] -= errors @ later
    # Zero the pruned weights  [alg. 1]
    return weights * keep

Hyperparameters

Results

Author-reported. Setup: OPT family from 125M to 175B and BLOOM-176B, one A100 80GB, pruning uniform per layer, perplexity on raw-WikiText2 §4 §4.1. Numbers below are copied from the paper's tables.

Perplexity, OPT, 50% sparsity, small models tab. 1

Perplexity, OPT family, raw-WikiText2 tab. 1

Zero-shot accuracy, OPT-175B tab. 2

PTB and C4 subset perplexity tab. 3 tab. 4

Partial 2:4 pruning, OPT-175B and BLOOM-176B tab. 5 tab. 6. Columns are the fraction of leading blocks pruned to 2:4, with the rest dense.

Joint sparsity and quantization, OPT-175B §4.1 app. C: 50% sparsity with 4-bit weights gives 8.29, against 8.68 for GPTQ 3-bit (same storage). 2:4 with 4-bit gives 8.55 and 4:8 with 4-bit gives 8.85. With 3-bit weights, 50% sparsity gives 8.60, against 8.94 for GPTQ at 2.5 bits; 4:8 with 3-bit gives 8.93 app. C.

Ablations, OPT-2.7B at 50% app. A: calibration samples flatten out fig. 8; Hessian damping of 0.001 to 0.1 gives similar results fig. 9; the mask block size of a few hundred is best, and column-wise (1) or near-full blocks are much worse fig. 10. Layer-wise error relative to exact reconstruction is about 20% higher on average, and about 10% on the later FC2 layers app. A fig. 11.

Sensitivity of layer types and positions, partial 2:4 on OPT-175B and BLOOM-176B §4.1 fig. 7: later layers are more sensitive than earlier ones. Leaving the last third dense gave the best accuracy §4.1.

Speed app. E. On CPU with DeepSparse, OPT-2.7B speeds up by 1.57× at 40% sparsity, 1.82× at 50% and 2.16× at 60% tab. 7. On an Ampere GPU with CUTLASS, 2:4 matrix products of the OPT-175B shapes run 1.54× to 1.79× faster than cuBLAS dense tab. 8. The paper says end-to-end speedups will likely be lower §4.1 app. E; no end-to-end GPU numbers are given.

Paper vs code

Official code: IST-DASLab/sparsegpt, commit 147d2159dc4f3e9f73e47b32c04d7b3708f44436, Apache-2.0. The repository is linked from the paper's abstract, and its owner is the lab of author D. Alistarh. Checked files: sparsegpt.py, opt.py, datautils.py, quant.py, modelutils.py, README.md.

Differences found:

• Sequential granularity inside a block. The paper says "we sparsify Transformer layers sequentially in order" §4. The code collects Hessians for all linear modules of a block in one forward pass before pruning any of them, and prunes them afterwards opt.py. So the attention output projection and FC2 get Hessians from the dense block, not from already-pruned siblings. Only the block outputs propagate pruning forward opt.py.
• Hessian inverse in the algorithm. Eq. 3 and §3.2 write entries of \mathbf{H}^{-1}. Algorithm 1 and the code use the upper Cholesky factor of \mathbf{H}^{-1} for both the mask scores and the errors alg. 1 sparsegpt.py. This is a discrepancy inside the paper.
• Quantization grid. The per-channel grid is fitted once, on the dense weights, before any pruning sparsegpt.py. The paper does not say when the grid is fitted §3.5.
• Dead inputs. Zero-diagonal columns are set to curvature 1 and zero weight sparsegpt.py. The paper does not mention this case.
• Mask block tied to lazy block. The code computes masks at the start of each lazy block of blocksize columns, and uses that same argument as the mask block sparsegpt.py. The paper treats B_s and B as separate parameters §3.2 alg. 1. With both set to 128 the two agree, but changing blocksize also changes the mask block.
• Mask ties. The threshold is taken from a sorted array at index int(numel * sparsity) and pruning uses <= sparsegpt.py. Ties can therefore prune slightly more than the target fraction. The paper says nothing about ties.
• Hessian scale. The code scales each sample's contribution by 2/n_seq and averages over sequences sparsegpt.py. The paper does not state a scale. Inferred from the code, not run: this scale does not change the result, because damping is relative to the mean diagonal and the update is invariant to global scale.
• PTB and C4 evaluation text. The code joins PTB test sentences with spaces datautils.py and the C4 validation documents with spaces datautils.py. Appendix B says PTB is "concatenated directly, without separators" and the C4 subset is "directly concatenated" app. B. WikiText2 uses "\n\n" as stated datautils.py app. B.
• C4 calibration sampling. The code redraws documents until one is longer than the sequence length datautils.py. The paper says only "randomly chosen" §4.

No discrepancy was found for the dampening (1% of the mean diagonal, app. A against sparsegpt.py), the lazy and mask block sizes of 128 alg. 1 opt.py, or the choice of pruned layers §4.1 opt.py.

Pitfalls

• Cholesky factor, not the inverse. An implementation that follows eq. 3 literally, with entries of \mathbf{H}^{-1}, does not match Algorithm 1 or the code. Use the upper Cholesky factor of \mathbf{H}^{-1} in the update and in the mask score alg. 1 sparsegpt.py.
• Order of Hessian and update. The code computes all Hessians for a block from the dense block (see Paper vs code). An implementer who re-collects activations after each linear module gets different masks and errors. The paper's text does not settle this.
• Damping is required for stability. The 1% damping is chosen "to be on the safe side" for the inverse computations at the largest scale app. A. Without it the Cholesky steps can fail. The paper's ablation shows that 0.001 to 0.1 give similar results app. A.
• Calibration variance is small but not zero. Five seeds gave a standard deviation of 0.075 perplexity around 13.52 at 50% on OPT-2.7B app. A. The paper reports seed variance only for this one setting.
• Perplexity hides noise in zero-shot. The zero-shot numbers are noisy. 2:4 pruning beats dense on Lambada §4.1 tab. 2. The authors call the 175B 50% result a slight gain that is dataset specific §4.1 app. C.
• Hessian memory. Each linear layer needs a d_col × d_col Hessian, held in float32 in the code sparsegpt.py. The paper's complexity is O(d_col³ + d_row · d_col²) per layer §3.1. Memory cost is not analysed in the paper.
• Mask boundaries and n:m. The n:m code counts group boundaries from the start of each lazy block sparsegpt.py. Inferred: the block size must be a multiple of m, which 128 satisfies for m = 2, 4 and 8. Other block sizes are untested.
• Quantization of masked zeros. The code applies quantize after zeroing the pruned entries sparsegpt.py. A pruned zero stays exactly zero only when the integer zero-point lies in the grid range quant.py quant.py. Keep this in mind for any reimplementation.
• Sensitive layers. Later layers tolerate sparsity worse than earlier ones §4.1 fig. 7. A uniform per-layer rule is the paper's default and is not tuned per layer.
• Speed is not end-to-end. The GPU speed-ups are for individual matrix products of OPT-175B shapes tab. 8, and the CPU end-to-end numbers are for OPT-2.7B only app. E tab. 7. No end-to-end speed for the large models is reported.
• Runtime is hardware-specific. The 4-hour figure is for one A100 80GB §4; the abstract says "under 4.5 hours" [abstract].
• Assumed, not stated: the paper does not give a random seed, a quantization grid rule, or how to handle dead inputs.

Lineage

• Builds on: Optimal Brain Surgeon / the OBS update [hassibi1993optimal], used in eq. 3 §3.1. The OBC framework [frantar2022obc] (arXiv:2208.11580 in the paper's bibliography, no card here) gives the greedy column-wise idea and the accurate mask choice that the paper builds on §2 §3.2.
• Builds on: GPTQ [frantar2022gptq] for the column-wise greedy scheme, lazy batch updates and Cholesky reformulation §3.4 §3.5. See GPTQ.
• Compared against: layer-wise magnitude pruning [zhu2017prune] §4; AdaPrune [hubara2021accelerated], up to 1.3B parameters §4; GPTQ at 2.5 to 3 bits for joint compression §4.1 app. C.
• Superseded by: not known from content in this wiki.