# Accelerated Sparse Neural Training: A Provable and Efficient Method to Find N:M Transposable Masks

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

## Key facts

- Cited by 103 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 56 references that are in the map.
- First posted on arXiv 16 Feb 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [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)
- [Pruning Filters for Efficient ConvNets](https://mlsanity.com/paper/1608.08710/) (2016)
- [MnasNet: Platform-Aware Neural Architecture Search for Mobile](https://mlsanity.com/paper/1807.11626/) (2018)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [Up or Down? Adaptive Rounding for Post-Training Quantization](https://mlsanity.com/paper/2004.10568/) (2020)
- [Rethinking the Value of Network Pruning](https://mlsanity.com/paper/1810.05270/) (2018)
- [Learning Sparse Neural Networks through L0 Regularization](https://mlsanity.com/paper/1712.01312/) (2017)
- [Learning Structured Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1608.03665/) (2016)
- [Rigging the Lottery: Making All Tickets Winners](https://mlsanity.com/paper/1911.11134/) (2019)
- [FBNet: Hardware-Aware Efficient ConvNet Design via Differentiable Neural Architecture Search](https://mlsanity.com/paper/1812.03443/) (2018)
- [ThiNet: A Filter Level Pruning Method for Deep Neural Network Compression](https://mlsanity.com/paper/1707.06342/) (2017)
- [Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations](https://mlsanity.com/paper/1609.07061/) (2016)
- [Scalable Training of Artificial Neural Networks with Adaptive Sparse Connectivity inspired by Network Science](https://mlsanity.com/paper/1707.04780/) (2017)
- [Sparse Networks from Scratch: Faster Training without Losing Performance](https://mlsanity.com/paper/1907.04840/) (2019)
- [Parameter Efficient Training of Deep Convolutional Neural Networks by Dynamic Sparse Reparameterization](https://mlsanity.com/paper/1902.05967/) (2019)
- [Learning N:M Fine-grained Structured Sparse Neural Networks From Scratch](https://mlsanity.com/paper/2102.04010/) (2021)
- [Scalable Methods for 8-bit Training of Neural Networks](https://mlsanity.com/paper/1805.11046/) (2018)
- [Sparse GPU Kernels for Deep Learning](https://mlsanity.com/paper/2006.10901/) (2020)
- [Deep Rewiring: Training very sparse deep networks](https://mlsanity.com/paper/1711.05136/) (2017)
- [Loss Aware Post-training Quantization](https://mlsanity.com/paper/1911.07190/) (2019)
- [Improving Post Training Neural Quantization: Layer-wise Calibration and Integer Programming](https://mlsanity.com/paper/2006.10518/) (2020)
- [Fast Sparse ConvNets](https://mlsanity.com/paper/1911.09723/) (2019)
- [Fighting Quantization Bias With Bias](https://mlsanity.com/paper/1906.03193/) (2019)
- [Sparse Systolic Tensor Array for Efficient CNN Hardware Acceleration](https://mlsanity.com/paper/2009.02381/) (2020)

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

- [SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot](https://mlsanity.com/paper/2301.00774/) (2023)
- [A Simple and Effective Pruning Approach for Large Language Models](https://mlsanity.com/paper/2306.11695/) (2023)
- [SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification](https://mlsanity.com/paper/2305.09781/) (2023)
- [Optimal Brain Compression: A Framework for Accurate Post-Training Quantization and Pruning](https://mlsanity.com/paper/2208.11580/) (2022)
- [Accelerating Sparse Deep Neural Networks](https://mlsanity.com/paper/2104.08378/) (2021)
- [REST: Retrieval-Based Speculative Decoding](https://mlsanity.com/paper/2311.08252/) (2023)
- [Not All Experts are Equal: Efficient Expert Pruning and Skipping for Mixture-of-Experts Large Language Models](https://mlsanity.com/paper/2402.14800/) (2024)
- [More ConvNets in the 2020s: Scaling up Kernels Beyond 51x51 using Sparsity](https://mlsanity.com/paper/2207.03620/) (2022)
- [Sparse Training via Boosting Pruning Plasticity with Neuroregeneration](https://mlsanity.com/paper/2106.10404/) (2021)
- [Dynamic Sparse No Training: Training-Free Fine-tuning for Sparse LLMs](https://mlsanity.com/paper/2310.08915/) (2023)
- [ZipLM: Inference-Aware Structured Pruning of Language Models](https://mlsanity.com/paper/2302.04089/) (2023)
- [RoSA: Accurate Parameter-Efficient Fine-Tuning via Robust Adaptation](https://mlsanity.com/paper/2401.04679/) (2024)
- [A Survey on Transformer Compression](https://mlsanity.com/paper/2402.05964/) (2024)
- [Scaling Laws for Sparsely-Connected Foundation Models](https://mlsanity.com/paper/2309.08520/) (2023)
- [Mixture Compressor for Mixture-of-Experts LLMs Gains More](https://mlsanity.com/paper/2410.06270/) (2024)
- [SPDY: Accurate Pruning with Speedup Guarantees](https://mlsanity.com/paper/2201.13096/) (2022)
- [Learning Best Combination for Efficient N:M Sparsity](https://mlsanity.com/paper/2206.06662/) (2022)
- [STBLLM: Breaking the 1-Bit Barrier with Structured Binary LLMs](https://mlsanity.com/paper/2408.01803/) (2024)
- [Compress, Then Prompt: Improving Accuracy-Efficiency Trade-off of LLM Inference with Transferable Prompt](https://mlsanity.com/paper/2305.11186/) (2023)
- [STEP: Learning N:M Structured Sparsity Masks from Scratch with Precondition](https://mlsanity.com/paper/2302.01172/) (2023)
- [Gradient-Free Structured Pruning with Unlabeled Data](https://mlsanity.com/paper/2303.04185/) (2023)
- [SparseLLM: Towards Global Pruning for Pre-trained Language Models](https://mlsanity.com/paper/2402.17946/) (2024)
- [CAP: Correlation-Aware Pruning for Highly-Accurate Sparse Vision Models](https://mlsanity.com/paper/2210.09223/) (2022)
- [SLoPe: Double-Pruned Sparse Plus Lazy Low-Rank Adapter Pretraining of LLMs](https://mlsanity.com/paper/2405.16325/) (2024)
- [Pruning Large Language Models with Semi-Structural Adaptive Sparse Training](https://mlsanity.com/paper/2407.20584/) (2024)
- [EvoPress: Accurate Dynamic Model Compression via Evolutionary Search](https://mlsanity.com/paper/2410.14649/) (2024)
- [Pruning Foundation Models for High Accuracy without Retraining](https://mlsanity.com/paper/2410.15567/) (2024)
- [Compresso: Structured Pruning with Collaborative Prompting Learns Compact Large Language Models](https://mlsanity.com/paper/2310.05015/) (2023)
- [Accelerating Transformer Pre-training with 2:4 Sparsity](https://mlsanity.com/paper/2404.01847/) (2024)
- [Effective Interplay between Sparsity and Quantization: From Theory to Practice](https://mlsanity.com/paper/2405.20935/) (2024)

## Abstract (arXiv)

Unstructured pruning reduces the memory footprint in deep neural networks (DNNs). Recently, researchers proposed different types of structural pruning intending to reduce also the computation complexity. In this work, we first suggest a new measure called mask-diversity which correlates with the expected accuracy of the different types of structural pruning. We focus on the recently suggested N:M fine-grained block sparsity mask, in which for each block of M weights, we have at least N zeros. While N:M fine-grained block sparsity allows acceleration in actual modern hardware, it can be used only to accelerate the inference phase. In order to allow for similar accelerations in the training phase, we suggest a novel transposable fine-grained sparsity mask, where the same mask can be used for both forward and backward passes. Our transposable mask guarantees that both the weight matrix and its transpose follow the same sparsity pattern; thus, the matrix multiplication required for passing the error backward can also be accelerated. We formulate the problem of finding the optimal transposable-mask as a minimum-cost flow problem. Additionally, to speed up the minimum-cost flow computation, we also introduce a fast linear-time approximation that can be used when the masks dynamically change during training. Our experiments suggest a 2x speed-up in the matrix multiplications with no accuracy degradation over vision and language models. Finally, to solve the problem of switching between different structure constraints, we suggest a method to convert a pre-trained model with unstructured sparsity to an N:M fine-grained block sparsity model with little to no training. A reference implementation can be found at https://github.com/papers-submission/structured_transposable_masks.