🤖 AI

OPTIMA: Optimal One-shot Pruning for LLMs via Quadratic Programming Reconstruction

OPTIMA is a scalable, one-shot post-training pruning method for large language models that formulates layer-wise weight reconstruction as independent column-wise quadratic programs with a shared Hessian, achieving superior accuracy over heuristic approaches while maintaining computational efficiency on modern accelerators.

Original authors: Mohammad Mozaffari, Samuel Kushnir, Maryam Mehri Dehnavi, Amir Yazdanbakhsh

Published 2026-10-21✓ Author reviewed ⓘ

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Mohammad Mozaffari, Samuel Kushnir, Maryam Mehri Dehnavi, Amir Yazdanbakhsh

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 by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Large language models are powerful computer programs that have learned to understand and generate human language by studying vast amounts of text. They can write stories, answer complex questions, and solve problems, but they come with a significant drawback: they are enormous. These models contain billions of parameters, which are the internal numbers the system adjusts to make sense of language. Because of their size, running them requires expensive, powerful hardware, making them difficult to use for everyday tasks or on smaller devices. To make these models more practical, researchers look for ways to shrink them without losing their ability to think clearly. One popular method is called pruning, which involves removing the least important numbers from the model to reduce its size. However, this process is tricky. If you simply delete the numbers, the model often becomes much worse at its job. If you try to fix the model by recalculating all the numbers at once to compensate for the loss, the math becomes so heavy that it is impossible to do on modern computers.

A team of researchers has developed a new approach called OPTIMA to solve this specific problem. Their goal was to find a middle ground between the fast but inaccurate method of simply deleting numbers and the too-slow method of trying to fix everything at once. They realized that after deciding which numbers to remove, the task of fixing the remaining numbers could be broken down into many tiny, independent problems. Instead of trying to solve the entire model's math in one giant, impossible step, they treated each column of numbers in the model separately. They discovered that while each column had its own specific constraints based on which numbers were removed, they all shared a common underlying structure. This allowed them to use a specialized mathematical tool, known as a quadratic program, to find the perfect replacement values for each column. Because the structure was the same for every column, they could solve thousands of these tiny problems at the same time on a single computer chip, rather than one by one.

The researchers tested this method on several different families of large language models, including popular ones like LLaMA and Gemma. They applied their technique to models that had already been pruned by other existing methods, essentially acting as a final polish to improve the results. In most cases, this extra step made the models significantly more accurate. For example, when they tested the models on a variety of standard tasks, the new method improved the average score by up to nearly four points in some difficult scenarios, particularly when the models were made very small. The method worked well across different types of pruning patterns and model sizes, from smaller one-billion-parameter models up to very large ones with billions of parameters. It is worth noting that while the method improved accuracy, it did take longer to run than the fastest existing methods, requiring about forty hours to process an eight-billion-parameter model on a single high-end graphics card. However, the researchers emphasized that this is a one-time cost done before the model is used, and the resulting model runs just as fast as the original pruned version.

The study also highlighted that this approach is not a magic fix for every situation. In a few specific cases, the new method did not improve the model's performance and occasionally made it slightly worse, suggesting that the interaction between the pruning method and the correction step can be complex. Furthermore, the researchers found that the method works best when the initial pruning leaves a lot of room for improvement, such as when the model is made very sparse. They also observed that the method's success depends on the specific type of model and how the pruning was originally done. Despite these limitations, the work demonstrates that it is possible to use rigorous mathematical optimization to repair pruned models in a way that is both practical and scalable. By breaking a massive, impossible problem into thousands of small, parallel tasks, the researchers showed that we can keep large language models small and efficient without sacrificing their intelligence. This opens the door for more capable artificial intelligence to run on hardware that is currently too weak to support it, bringing powerful language tools closer to everyday use.

Technical Summary: OPTIMA: Optimal One-Shot Pruning for LLMs via Quadratic Programming Reconstruction

Problem Statement

Post-training one-shot pruning aims to reduce the inference costs of Large Language Models (LLMs) by removing parameters using only a small calibration dataset, avoiding the expense of full fine-tuning. However, the field faces a fundamental trade-off:

Heuristic methods (e.g., Wanda) are computationally cheap but often degrade accuracy significantly because they simply zero out weights without updating the remaining ones.
Principled joint optimization methods (e.g., Optimal Brain Surgeon) can recover accuracy by solving for optimal weight updates but are computationally infeasible at the scale of modern LLMs due to the complexity of inverting large Hessians.
Existing approximations (e.g., SparseGPT, Thanos) attempt to bridge this gap but sacrifice reconstruction optimality, leaving "headroom" in accuracy that could be recovered.

The core challenge is to develop a method that balances accuracy (by solving the reconstruction problem optimally) and scalability (by being computationally feasible on modern accelerators).

Methodology

The paper introduces OPTIMA, a framework that reformulates the layer-wise weight reconstruction step following mask selection as a set of independent, column-wise Quadratic Programs (QPs).

1. Mathematical Reformulation:
After a binary mask $M_l$ is selected for a weight matrix $W_l$ , the goal is to find updated weights $\hat{W}_l$ that minimize the output reconstruction error $\|X_l W_l - X_l (M_l \odot \hat{W}_l)\|_F^2$ .

OPTIMA decomposes this problem column-wise. For each column $j$ , the update $\Delta w_j$ is formulated as a QP:
$\min_{\Delta w_j} \Delta w_j^T H \Delta w_j \quad \text{subject to} \quad (\Delta w_j)_i = -(w_j)_i, \forall i \in S_j$
where $H = X_l^T X_l$ is the Hessian (covariance of input activations) and $S_j$ represents the indices of pruned weights.
Key Insight: All columns of the same weight matrix share the same Hessian $H$ . Only the linear constraints (determined by the mask) differ per column. This shared structure allows for efficient batching.

2. Solver and Implementation:

Algorithm: OPTIMA employs a first-order primal-dual solver, specifically rAPDHG (restarted accelerated primal-dual hybrid gradient), which is well-suited for constrained problems and relies on matrix-vector products with the shared Hessian.
Accelerator Optimization:
- Batching: Thousands of small QPs are solved in parallel on a single accelerator (GPU/TPU).
- Memory Efficiency: Instead of storing the full dense activation matrix, the Hessian is accumulated incrementally from calibration sequences.
- Constraint Handling: Pruned entries are enforced via tight variable bounds rather than explicit equality matrices, avoiding the overhead of large constraint matrices.
- Fallback Mechanism: If a column's QP does not converge within the iteration budget (checked via a convergence certificate), the update is discarded, and the original weights (with pruned entries zeroed) are retained. This ensures the method never performs worse than the baseline mask selector's update.

Key Contributions

QP Reformulation: Casting post-training reconstruction as batched, column-wise QPs sharing a single Hessian per weight matrix, enabling per-column global optimality for the reconstruction objective.
Scalable Solver Pipeline: Designing an accelerator-friendly pipeline that accumulates Hessians incrementally, enforces constraints via bounds, and solves thousands of QPs in parallel using rAPDHG.
Modularity: Demonstrating that OPTIMA acts as a "drop-in" weight update step compatible with existing mask selectors (Wanda, SparseGPT, Thanos, ProxSparse, ADMM).
Empirical Validation: Providing extensive results across LLaMA, Gemma, and Qwen families, showing consistent accuracy improvements without fine-tuning.

Results

The authors evaluated OPTIMA on LLaMA 3.1/3.2, Gemma 2/3, and Qwen 2.5 models across unstructured (50%, 60%) and semi-structured (2:4) sparsity regimes.

Accuracy Gains: OPTIMA improved average zero-shot accuracy in 40 out of 49 (model, mask selector, sparsity) settings.
- Mean gains: +0.61 points at 50% unstructured, +0.56 at 2:4, and +1.01 at 60% unstructured sparsity.
- Maximum gain: +3.97 points (LLaMA 3.2 3B at 60% sparsity).
- On Qwen 2.5, gains reached +4.19 points.
Comparison to Baselines:
- OPTIMA consistently outperformed the "no update" baseline (Wanda).
- It improved upon the updates of SparseGPT and Thanos in most settings, though gains were smaller when the baseline already performed weight updates.
- On its own masks, OPTIMA matched or slightly exceeded ADMM-based exact reconstruction (Boža, 2024).
Perplexity vs. Accuracy: The paper notes that perplexity and downstream accuracy do not always correlate; OPTIMA prioritizes downstream accuracy, which is the primary metric for pruning quality in this context.
Efficiency:
- Pruning an 8B parameter model on a single NVIDIA H100 takes 40 hours (peak 60 GB memory).
- Pruning a 70B model takes approximately 350 hours.
- While slower than heuristic methods (Wanda/SparseGPT) per layer, it remains a one-time offline cost.

Significance and Claims

The paper claims that principled column-wise QP reconstruction is a practical alternative to heuristic weight updates in one-shot post-training pruning.

Bridging the Gap: OPTIMA closes the gap between fast, inaccurate heuristics and slow, infeasible exact methods by leveraging the shared Hessian structure to enable parallel, certified solving on accelerators.
No Fine-Tuning Required: The method achieves these gains without any post-pruning fine-tuning, making it a pure inference-cost reduction technique.
Scalability: By solving the problem on a single accelerator without requiring distributed training infrastructure, OPTIMA demonstrates that exact reconstruction is feasible for large models.
Modularity: The approach is orthogonal to mask selection, meaning it can enhance any existing pruning strategy that relies on a fixed mask.

The authors acknowledge limitations, noting that OPTIMA is slower than closed-form updates and that minimizing layer-wise reconstruction error does not always perfectly align with end-to-end task performance. However, they argue that the method provides a robust, theoretically grounded approach to maximizing the utility of pruned models.