# The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networks

arXiv: https://arxiv.org/abs/2203.04466 · HTML: https://mlsanity.com/paper/2203.04466/

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- Builds on 75 of its 112 references that are in the map.
- First posted on arXiv 9 Mar 2022.

## Builds on (most cited first, 30 of 75)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications](https://mlsanity.com/paper/1704.04861/) (2017)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Pruning Filters for Efficient ConvNets](https://mlsanity.com/paper/1608.08710/) (2016)
- [Visualizing the Loss Landscape of Neural Nets](https://mlsanity.com/paper/1712.09913/) (2017)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [Channel Pruning for Accelerating Very Deep Neural Networks](https://mlsanity.com/paper/1707.06168/) (2017)
- [Rethinking the Value of Network Pruning](https://mlsanity.com/paper/1810.05270/) (2018)
- [What is the State of Neural Network Pruning?](https://mlsanity.com/paper/2003.03033/) (2020)
- [Pruning neural networks without any data by iteratively conserving synaptic flow](https://mlsanity.com/paper/2006.05467/) (2020)
- [Picking Winning Tickets Before Training by Preserving Gradient Flow](https://mlsanity.com/paper/2002.07376/) (2020)
- [ThiNet: A Filter Level Pruning Method for Deep Neural Network Compression](https://mlsanity.com/paper/1707.06342/) (2017)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Exploiting Linear Structure Within Convolutional Networks for Efficient Evaluation](https://mlsanity.com/paper/1404.0736/) (2014)
- [Speeding up Convolutional Neural Networks with Low Rank Expansions](https://mlsanity.com/paper/1405.3866/) (2014)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Comparing Rewinding and Fine-tuning in Neural Network Pruning](https://mlsanity.com/paper/2003.02389/) (2020)
- [What's Hidden in a Randomly Weighted Neural Network?](https://mlsanity.com/paper/1911.13299/) (2019)
- [Adversarial Neuron Pruning Purifies Backdoored Deep Models](https://mlsanity.com/paper/2110.14430/) (2021)
- [NISP: Pruning Networks using Neuron Importance Score Propagation](https://mlsanity.com/paper/1711.05908/) (2017)
- [Predicting Parameters in Deep Learning](https://mlsanity.com/paper/1306.0543/) (2013)
- [Learning to Prune Deep Neural Networks via Layer-wise Optimal Brain Surgeon](https://mlsanity.com/paper/1705.07565/) (2017)
- [Dataset Distillation with Infinitely Wide Convolutional Networks](https://mlsanity.com/paper/2107.13034/) (2021)
- [Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask](https://mlsanity.com/paper/1905.01067/) (2019)
- [Speeding-up Convolutional Neural Networks Using Fine-tuned CP-Decomposition](https://mlsanity.com/paper/1412.6553/) (2014)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)

## Built on by (most cited first, 30 of 41)

- [LoRAPrune: Structured Pruning Meets Low-Rank Parameter-Efficient Fine-Tuning](https://mlsanity.com/paper/2305.18403/) (2023)
- [MoDeGPT: Modular Decomposition for Large Language Model Compression](https://mlsanity.com/paper/2408.09632/) (2024)
- [Fast as CHITA: Neural Network Pruning with Combinatorial Optimization](https://mlsanity.com/paper/2302.14623/) (2023)
- [Pruning's Effect on Generalization Through the Lens of Training and Regularization](https://mlsanity.com/paper/2210.13738/) (2022)
- [Why Random Pruning Is All We Need to Start Sparse](https://mlsanity.com/paper/2210.02412/) (2022)
- [LeanQuant: Accurate and Scalable Large Language Model Quantization with Loss-error-aware Grid](https://mlsanity.com/paper/2407.10032/) (2024)
- [ALPS: Improved Optimization for Highly Sparse One-Shot Pruning for Large Language Models](https://mlsanity.com/paper/2406.07831/) (2024)
- [OSSCAR: One-Shot Structured Pruning in Vision and Language Models with Combinatorial Optimization](https://mlsanity.com/paper/2403.12983/) (2024)
- [MULTIFLOW: Shifting Towards Task-Agnostic Vision-Language Pruning](https://mlsanity.com/paper/2404.05621/) (2024)
- [FALCON: FLOP-Aware Combinatorial Optimization for Neural Network Pruning](https://mlsanity.com/paper/2403.07094/) (2024)
- [Preserving Deep Representations In One-Shot Pruning: A Hessian-Free Second-Order Optimization Framework](https://mlsanity.com/paper/2411.18376/) (2024)
- [Recall Distortion in Neural Network Pruning and the Undecayed Pruning Algorithm](https://mlsanity.com/paper/2206.02976/) (2022)
- [SInGE: Sparsity via Integrated Gradients Estimation of Neuron Relevance](https://mlsanity.com/paper/2207.04089/) (2022)
- [How Sparse Can We Prune A Deep Network: A Fundamental Limit Perspective](https://mlsanity.com/paper/2306.05857/) (2023)
- [Jointly Training and Pruning CNNs via Learnable Agent Guidance and Alignment](https://mlsanity.com/paper/2403.19490/) (2024)
- [Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regions](https://mlsanity.com/paper/2301.07966/) (2023)
- [The Iterative Optimal Brain Surgeon: Faster Sparse Recovery by Leveraging Second-Order Information](https://mlsanity.com/paper/2408.17163/) (2024)
- [SNP: Structured Neuron-level Pruning to Preserve Attention Scores](https://mlsanity.com/paper/2404.11630/) (2024)
- [MINI-LLM: Memory-Efficient Structured Pruning for Large Language Models](https://mlsanity.com/paper/2407.11681/) (2024)
- [Signal Collapse in One-Shot Pruning: When Sparse Models Fail to Distinguish Neural Representations](https://mlsanity.com/paper/2502.15790/) (2025)
- [SparseSSM: Efficient Selective Structured State Space Models Can Be Pruned in One-Shot](https://mlsanity.com/paper/2506.09613/) (2025)
- [UPSCALE: Unconstrained Channel Pruning](https://mlsanity.com/paper/2307.08771/) (2023)
- [Influence Function Based Second-Order Channel Pruning-Evaluating True Loss Changes For Pruning Is Possible Without Retraining](https://mlsanity.com/paper/2308.06755/) (2023)
- [A Rescaling-Invariant Lipschitz Bound Based on Path-Metrics for Modern ReLU Network Parameterizations](https://mlsanity.com/paper/2405.15006/) (2024)
- [Free Lunch in the Forest: Functionally-Identical Pruning of Boosted Tree Ensembles](https://mlsanity.com/paper/2408.16167/) (2024)
- [Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver](https://mlsanity.com/paper/2301.01913/) (2023)
- [Optimal Brain Apoptosis](https://mlsanity.com/paper/2502.17941/) (2025)
- [Model-based feature selection for neural networks: A mixed-integer programming approach](https://mlsanity.com/paper/2302.10344/) (2023)
- [SWAP: Sparse Entropic Wasserstein Regression for Robust Network Pruning](https://mlsanity.com/paper/2310.04918/) (2023)
- [Data-Free Pruning of Self-Attention Layers in LLMs](https://mlsanity.com/paper/2512.20636/) (2025)

## Abstract (arXiv)

Neural networks tend to achieve better accuracy with training if they are larger -- even if the resulting models are overparameterized. Nevertheless, carefully removing such excess parameters before, during, or after training may also produce models with similar or even improved accuracy. In many cases, that can be curiously achieved by heuristics as simple as removing a percentage of the weights with the smallest absolute value -- even though magnitude is not a perfect proxy for weight relevance. With the premise that obtaining significantly better performance from pruning depends on accounting for the combined effect of removing multiple weights, we revisit one of the classic approaches for impact-based pruning: the Optimal Brain Surgeon(OBS). We propose a tractable heuristic for solving the combinatorial extension of OBS, in which we select weights for simultaneous removal, as well as a systematic update of the remaining weights. Our selection method outperforms other methods under high sparsity, and the weight update is advantageous even when combined with the other methods.