# Learning Best Combination for Efficient N:M Sparsity

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 56 references that are in the map.
- First posted on arXiv 14 Jun 2022.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Mask R-CNN](https://mlsanity.com/paper/1703.06870/) (2017)
- [Training data-efficient image transformers & distillation through attention](https://mlsanity.com/paper/2012.12877/) (2020)
- [Fast R-CNN](https://mlsanity.com/paper/1504.08083/) (2015)
- [Rich feature hierarchies for accurate object detection and semantic segmentation](https://mlsanity.com/paper/1311.2524/) (2013)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [To prune, or not to prune: exploring the efficacy of pruning for model compression](https://mlsanity.com/paper/1710.01878/) (2017)
- [Learning Sparse Neural Networks through L0 Regularization](https://mlsanity.com/paper/1712.01312/) (2017)
- [Rigging the Lottery: Making All Tickets Winners](https://mlsanity.com/paper/1911.11134/) (2019)
- [ThiNet: A Filter Level Pruning Method for Deep Neural Network Compression](https://mlsanity.com/paper/1707.06342/) (2017)
- [Filter Pruning via Geometric Median for Deep Convolutional Neural Networks Acceleration](https://mlsanity.com/paper/1811.00250/) (2018)
- [Soft Filter Pruning for Accelerating Deep Convolutional Neural Networks](https://mlsanity.com/paper/1808.06866/) (2018)
- [HRank: Filter Pruning using High-Rank Feature Map](https://mlsanity.com/paper/2002.10179/) (2020)
- [MetaPruning: Meta Learning for Automatic Neural Network Channel Pruning](https://mlsanity.com/paper/1903.10258/) (2019)
- [Incremental Network Quantization: Towards Lossless CNNs with Low-Precision Weights](https://mlsanity.com/paper/1702.03044/) (2017)
- [Learning N:M Fine-grained Structured Sparse Neural Networks From Scratch](https://mlsanity.com/paper/2102.04010/) (2021)
- [Soft Threshold Weight Reparameterization for Learnable Sparsity](https://mlsanity.com/paper/2002.03231/) (2020)
- [Accelerated Sparse Neural Training: A Provable and Efficient Method to Find N:M Transposable Masks](https://mlsanity.com/paper/2102.08124/) (2021)
- [Channel Pruning via Automatic Structure Search](https://mlsanity.com/paper/2001.08565/) (2020)
- [Sparse Training via Boosting Pruning Plasticity with Neuroregeneration](https://mlsanity.com/paper/2106.10404/) (2021)
- [Top-KAST: Top-K Always Sparse Training](https://mlsanity.com/paper/2106.03517/) (2021)
- [AutoPruner: An End-to-End Trainable Filter Pruning Method for Efficient Deep Model Inference](https://mlsanity.com/paper/1805.08941/) (2018)
- [Global Sparse Momentum SGD for Pruning Very Deep Neural Networks](https://mlsanity.com/paper/1909.12778/) (2019)
- [DSA: More Efficient Budgeted Pruning via Differentiable Sparsity Allocation](https://mlsanity.com/paper/2004.02164/) (2020)
- [Approximated Oracle Filter Pruning for Destructive CNN Width Optimization](https://mlsanity.com/paper/1905.04748/) (2019)

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

- [Dynamic Sparse No Training: Training-Free Fine-tuning for Sparse LLMs](https://mlsanity.com/paper/2310.08915/) (2023)
- [MaskLLM: Learnable Semi-Structured Sparsity for Large Language Models](https://mlsanity.com/paper/2409.17481/) (2024)
- [BESA: Pruning Large Language Models with Blockwise Parameter-Efficient Sparsity Allocation](https://mlsanity.com/paper/2402.16880/) (2024)
- [MaskGaussian: Adaptive 3D Gaussian Representation from Probabilistic Masks](https://mlsanity.com/paper/2412.20522/) (2024)
- [STBLLM: Breaking the 1-Bit Barrier with Structured Binary LLMs](https://mlsanity.com/paper/2408.01803/) (2024)
- [Progressive Gradient Flow for Robust N:M Sparsity Training in Transformers](https://mlsanity.com/paper/2402.04744/) (2024)
- [SparseDM: Toward Sparse Efficient Diffusion Models](https://mlsanity.com/paper/2404.10445/) (2024)
- [Bi-directional Masks for Efficient N:M Sparse Training](https://mlsanity.com/paper/2302.06058/) (2023)
- [A Survey on Inference Engines for Large Language Models: Perspectives on Optimization and Efficiency](https://mlsanity.com/paper/2505.01658/) (2025)
- [Preserving Deep Representations In One-Shot Pruning: A Hessian-Free Second-Order Optimization Framework](https://mlsanity.com/paper/2411.18376/) (2024)
- [Optimizing LLMs for Resource-Constrained Environments: A Survey of Model Compression Techniques](https://mlsanity.com/paper/2505.02309/) (2025)
- [Enabling Unstructured Sparse Acceleration on Structured Sparse Accelerators](https://mlsanity.com/paper/2403.07953/) (2024)
- [Data-independent Module-aware Pruning for Hierarchical Vision Transformers](https://mlsanity.com/paper/2404.13648/) (2024)
- [Increasing Model Capacity for Free: A Simple Strategy for Parameter Efficient Fine-tuning](https://mlsanity.com/paper/2407.01320/) (2024)
- [Efficient Deep Learning Infrastructures for Embedded Computing Systems: A Comprehensive Survey and Future Envision](https://mlsanity.com/paper/2411.01431/) (2024)
- [Neural Architecture Codesign for Fast Physics Applications](https://mlsanity.com/paper/2501.05515/) (2025)
- [Symmetric Pruning of Large Language Models](https://mlsanity.com/paper/2501.18980/) (2025)
- [MaskPro: Linear-Space Probabilistic Learning for Strict (N:M)-Sparsity on LLMs](https://mlsanity.com/paper/2506.12876/) (2025)
- [ELSA: Exploiting Layer-wise N:M Sparsity for Vision Transformer Acceleration](https://mlsanity.com/paper/2409.09708/) (2024)
- [EvoP: Robust LLM Inference via Evolutionary Pruning](https://mlsanity.com/paper/2502.14910/) (2025)
- [Spatial Re-parameterization for N:M Sparsity](https://mlsanity.com/paper/2306.05612/) (2023)
- [SUBP: Soft Uniform Block Pruning for 1xN Sparse CNNs Multithreading Acceleration](https://mlsanity.com/paper/2310.06218/) (2023)
- [Torch2Chip: An End-to-end Customizable Deep Neural Network Compression and Deployment Toolkit for Prototype Hardware Accelerator Design](https://mlsanity.com/paper/2405.01775/) (2024)
- [One-Cycle Structured Pruning via Stability-Driven Subnetwork Search](https://mlsanity.com/paper/2501.13439/) (2025)
- [From 2:4 to 8:16 sparsity patterns in LLMs for Outliers and Weights with Variance Correction](https://mlsanity.com/paper/2507.03052/) (2025)
- [PermLLM: Learnable Channel Permutation for N:M Sparse Large Language Models](https://mlsanity.com/paper/2510.10136/) (2025)
- [Revisiting Implicit Models: Sparsity Trade-offs Capability in Weight-tied Model for Vision Tasks](https://mlsanity.com/paper/2307.08013/) (2023)
- [Neural Architecture Codesign for Fast Bragg Peak Analysis](https://mlsanity.com/paper/2312.05978/) (2023)
- [ELSA: Partial Weight Freezing for Overhead-Free Sparse Network Deployment](https://mlsanity.com/paper/2312.06872/) (2023)
- [MaxQ: Multi-Axis Query for N:M Sparsity Network](https://mlsanity.com/paper/2312.07061/) (2023)

## Abstract (arXiv)

By forcing at most N out of M consecutive weights to be non-zero, the recent N:M network sparsity has received increasing attention for its two attractive advantages: 1) Promising performance at a high sparsity. 2) Significant speedups on NVIDIA A100 GPUs. Recent studies require an expensive pre-training phase or a heavy dense-gradient computation. In this paper, we show that the N:M learning can be naturally characterized as a combinatorial problem which searches for the best combination candidate within a finite collection. Motivated by this characteristic, we solve N:M sparsity in an efficient divide-and-conquer manner. First, we divide the weight vector into CMN combination subsets of a fixed size N. Then, we conquer the combinatorial problem by assigning each combination a learnable score that is jointly optimized with its associate weights. We prove that the introduced scoring mechanism can well model the relative importance between combination subsets. And by gradually removing low-scored subsets, N:M fine-grained sparsity can be efficiently optimized during the normal training phase. Comprehensive experiments demonstrate that our learning best combination (LBC) performs consistently better than off-the-shelf N:M sparsity methods across various networks. Our project is released at urlhttps://github.com/zyxxmu/LBC.