# Fast as CHITA: Neural Network Pruning with Combinatorial Optimization

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 42 references that are in the map.
- First posted on arXiv 28 Feb 2023.

## Builds on (most cited first, 21 of 21)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [To prune, or not to prune: exploring the efficacy of pruning for model compression](https://mlsanity.com/paper/1710.01878/) (2017)
- [What is the State of Neural Network Pruning?](https://mlsanity.com/paper/2003.03033/) (2020)
- [Rigging the Lottery: Making All Tickets Winners](https://mlsanity.com/paper/1911.11134/) (2019)
- [The State of Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1902.09574/) (2019)
- [PyHessian: Neural Networks Through the Lens of the Hessian](https://mlsanity.com/paper/1912.07145/) (2019)
- [Variational Dropout Sparsifies Deep Neural Networks](https://mlsanity.com/paper/1701.05369/) (2017)
- [Learning to Prune Deep Neural Networks via Layer-wise Optimal Brain Surgeon](https://mlsanity.com/paper/1705.07565/) (2017)
- [Sparse Networks from Scratch: Faster Training without Losing Performance](https://mlsanity.com/paper/1907.04840/) (2019)
- [Compressing BERT: Studying the Effects of Weight Pruning on Transfer Learning](https://mlsanity.com/paper/2002.08307/) (2020)
- [Soft Threshold Weight Reparameterization for Learnable Sparsity](https://mlsanity.com/paper/2002.03231/) (2020)
- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [Discovering Neural Wirings](https://mlsanity.com/paper/1906.00586/) (2019)
- [M-FAC: Efficient Matrix-Free Approximations of Second-Order Information](https://mlsanity.com/paper/2107.03356/) (2021)
- [Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms](https://mlsanity.com/paper/1803.01454/) (2018)
- [Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization](https://mlsanity.com/paper/2004.06152/) (2020)
- [On the interplay between noise and curvature and its effect on optimization and generalization](https://mlsanity.com/paper/1906.07774/) (2019)
- [Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions](https://mlsanity.com/paper/1709.10029/) (2017)
- [The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networks](https://mlsanity.com/paper/2203.04466/) (2022)
- [Cardinality Minimization, Constraints, and Regularization: A Survey](https://mlsanity.com/paper/2106.09606/) (2021)

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

- [A Simple and Effective Pruning Approach for Large Language Models](https://mlsanity.com/paper/2306.11695/) (2023)
- [Scaling Laws for Sparsely-Connected Foundation Models](https://mlsanity.com/paper/2309.08520/) (2023)
- [Everybody Prune Now: Structured Pruning of LLMs with only Forward Passes](https://mlsanity.com/paper/2402.05406/) (2024)
- [OATS: Outlier-Aware Pruning Through Sparse and Low Rank Decomposition](https://mlsanity.com/paper/2409.13652/) (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)
- [How Sparse Can We Prune A Deep Network: A Fundamental Limit Perspective](https://mlsanity.com/paper/2306.05857/) (2023)
- [The Iterative Optimal Brain Surgeon: Faster Sparse Recovery by Leveraging Second-Order Information](https://mlsanity.com/paper/2408.17163/) (2024)
- [LayerMerge: Neural Network Depth Compression through Layer Pruning and Merging](https://mlsanity.com/paper/2406.12837/) (2024)
- [Signal Collapse in One-Shot Pruning: When Sparse Models Fail to Distinguish Neural Representations](https://mlsanity.com/paper/2502.15790/) (2025)
- [SAFE: Finding Sparse and Flat Minima to Improve Pruning](https://mlsanity.com/paper/2506.06866/) (2025)
- [SparseSSM: Efficient Selective Structured State Space Models Can Be Pruned in One-Shot](https://mlsanity.com/paper/2506.09613/) (2025)
- [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)
- [HASSLE-free: A unified Framework for Sparse plus Low-Rank Matrix Decomposition for LLMs](https://mlsanity.com/paper/2502.00899/) (2025)
- [Optimal Brain Apoptosis](https://mlsanity.com/paper/2502.17941/) (2025)
- [Scaling Up Efficient Small Language Models Serving and Deployment for Semantic Job Search](https://mlsanity.com/paper/2510.22101/) (2025)
- [SWAP: Sparse Entropic Wasserstein Regression for Robust Network Pruning](https://mlsanity.com/paper/2310.04918/) (2023)
- [Less is KEN: a Universal and Simple Non-Parametric Pruning Algorithm for Large Language Models](https://mlsanity.com/paper/2402.03142/) (2024)
- [Scaling Down, Serving Fast: Compressing and Deploying Efficient LLMs for Recommendation Systems](https://mlsanity.com/paper/2502.14305/) (2025)
- [An Optimization Framework for Differentially Private Sparse Fine-Tuning](https://mlsanity.com/paper/2503.12822/) (2025)
- [Data-Free Pruning of Self-Attention Layers in LLMs](https://mlsanity.com/paper/2512.20636/) (2025)
- [Relaxation-Informed Training of Neural Network Surrogate Models](https://mlsanity.com/paper/2604.22746/) (2026)
- [Is On-Device AI Broken and Exploitable? Assessing the Trust and Ethics in Small Language Models](https://mlsanity.com/paper/2406.05364/) (2024)
- [Confident magnitude-based neural network pruning](https://mlsanity.com/paper/2408.04759/) (2024)
- [A Granger-Causal Perspective on Gradient Descent with Application to Pruning](https://mlsanity.com/paper/2412.03035/) (2024)
- [LiteLMGuard: Seamless and Lightweight On-Device Prompt Filtering for Safeguarding Small Language Models against Quantization-induced Risks and Vulnerabilities](https://mlsanity.com/paper/2505.05619/) (2025)
- [Theoretical Compression Bounds for Wide Multilayer Perceptrons](https://mlsanity.com/paper/2512.06288/) (2025)

## Abstract (arXiv)

The sheer size of modern neural networks makes model serving a serious computational challenge. A popular class of compression techniques overcomes this challenge by pruning or sparsifying the weights of pretrained networks. While useful, these techniques often face serious tradeoffs between computational requirements and compression quality. In this work, we propose a novel optimization-based pruning framework that considers the combined effect of pruning (and updating) multiple weights subject to a sparsity constraint. Our approach, CHITA, extends the classical Optimal Brain Surgeon framework and results in significant improvements in speed, memory, and performance over existing optimization-based approaches for network pruning. CHITA's main workhorse performs combinatorial optimization updates on a memory-friendly representation of local quadratic approximation(s) of the loss function. On a standard benchmark of pretrained models and datasets, CHITA leads to significantly better sparsity-accuracy tradeoffs than competing methods. For example, for MLPNet with only 2% of the weights retained, our approach improves the accuracy by 63% relative to the state of the art. Furthermore, when used in conjunction with fine-tuning SGD steps, our method achieves significant accuracy gains over the state-of-the-art approaches.