# Monarch: Expressive Structured Matrices for Efficient and Accurate Training

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

## Key facts

- Cited by 106 papers in the map (data through 14 Oct 2026).
- Builds on 73 of its 123 references that are in the map.
- First posted on arXiv 1 Apr 2022.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Fourier Neural Operator for Parametric Partial Differential Equations](https://mlsanity.com/paper/2010.08895/) (2020)
- [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)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [MLP-Mixer: An all-MLP Architecture for Vision](https://mlsanity.com/paper/2105.01601/) (2021)
- [Calibrate Before Use: Improving Few-Shot Performance of Language Models](https://mlsanity.com/paper/2102.09690/) (2021)
- [Transformer Feed-Forward Layers Are Key-Value Memories](https://mlsanity.com/paper/2012.14913/) (2020)
- [Pruning Filters for Efficient ConvNets](https://mlsanity.com/paper/1608.08710/) (2016)
- [Tokens-to-Token ViT: Training Vision Transformers from Scratch on ImageNet](https://mlsanity.com/paper/2101.11986/) (2021)
- [Aligning Books and Movies: Towards Story-like Visual Explanations by Watching Movies and Reading Books](https://mlsanity.com/paper/1506.06724/) (2015)
- [Linear Mode Connectivity and the Lottery Ticket Hypothesis](https://mlsanity.com/paper/1912.05671/) (2019)
- [HiPPO: Recurrent Memory with Optimal Polynomial Projections](https://mlsanity.com/paper/2008.07669/) (2020)
- [To prune, or not to prune: exploring the efficacy of pruning for model compression](https://mlsanity.com/paper/1710.01878/) (2017)
- [Neural Controlled Differential Equations for Irregular Time Series](https://mlsanity.com/paper/2005.08926/) (2020)
- [Pruning neural networks without any data by iteratively conserving synaptic flow](https://mlsanity.com/paper/2006.05467/) (2020)
- [The State of Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1902.09574/) (2019)
- [Picking Winning Tickets Before Training by Preserving Gradient Flow](https://mlsanity.com/paper/2002.07376/) (2020)
- [Machine learning accelerated computational fluid dynamics](https://mlsanity.com/paper/2102.01010/) (2021)
- [Movement Pruning: Adaptive Sparsity by Fine-Tuning](https://mlsanity.com/paper/2005.07683/) (2020)
- [Universal Differential Equations for Scientific Machine Learning](https://mlsanity.com/paper/2001.04385/) (2020)
- [Learning a Variational Network for Reconstruction of Accelerated MRI Data](https://mlsanity.com/paper/1704.00447/) (2017)

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

- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Gated Linear Attention Transformers with Hardware-Efficient Training](https://mlsanity.com/paper/2312.06635/) (2023)
- [Hungry Hungry Hippos: Towards Language Modeling with State Space Models](https://mlsanity.com/paper/2212.14052/) (2022)
- [Hyena Hierarchy: Towards Larger Convolutional Language Models](https://mlsanity.com/paper/2302.10866/) (2023)
- [Language Model Cascades: Token-level uncertainty and beyond](https://mlsanity.com/paper/2404.10136/) (2024)
- [Parameter-Efficient Orthogonal Finetuning via Butterfly Factorization](https://mlsanity.com/paper/2311.06243/) (2023)
- [Learning to Grow Pretrained Models for Efficient Transformer Training](https://mlsanity.com/paper/2303.00980/) (2023)
- [Efficient Methods for Natural Language Processing: A Survey](https://mlsanity.com/paper/2209.00099/) (2022)
- [Multi-Grid Tensorized Fourier Neural Operator for High-Resolution PDEs](https://mlsanity.com/paper/2310.00120/) (2023)
- [Simple Hardware-Efficient Long Convolutions for Sequence Modeling](https://mlsanity.com/paper/2302.06646/) (2023)
- [Hydra: Bidirectional State Space Models Through Generalized Matrix Mixers](https://mlsanity.com/paper/2407.09941/) (2024)
- [MambaMixer: Efficient Selective State Space Models with Dual Token and Channel Selection](https://mlsanity.com/paper/2403.19888/) (2024)
- [Log-Linear Attention](https://mlsanity.com/paper/2506.04761/) (2025)
- [Compute-Efficient Deep Learning: Algorithmic Trends and Opportunities](https://mlsanity.com/paper/2210.06640/) (2022)
- [FlashFFTConv: Efficient Convolutions for Long Sequences with Tensor Cores](https://mlsanity.com/paper/2311.05908/) (2023)
- [On the Efficacy of Eviction Policy for Key-Value Constrained Generative Language Model Inference](https://mlsanity.com/paper/2402.06262/) (2024)
- [Adaptable Butterfly Accelerator for Attention-based NNs via Hardware and Algorithm Co-design](https://mlsanity.com/paper/2209.09570/) (2022)
- [SPDF: Sparse Pre-training and Dense Fine-tuning for Large Language Models](https://mlsanity.com/paper/2303.10464/) (2023)
- [Compute Better Spent: Replacing Dense Layers with Structured Matrices](https://mlsanity.com/paper/2406.06248/) (2024)
- [The Efficiency Spectrum of Large Language Models: An Algorithmic Survey](https://mlsanity.com/paper/2312.00678/) (2023)
- [Ten Lessons We Have Learned in the New "Sparseland": A Short Handbook for Sparse Neural Network Researchers](https://mlsanity.com/paper/2302.02596/) (2023)
- [Cuttlefish: Low-Rank Model Training without All the Tuning](https://mlsanity.com/paper/2305.02538/) (2023)
- [Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Models](https://mlsanity.com/paper/2407.18158/) (2024)
- [Guiding continuous operator learning through Physics-based boundary constraints](https://mlsanity.com/paper/2212.07477/) (2022)
- [Mixture of Parrots: Experts improve memorization more than reasoning](https://mlsanity.com/paper/2410.19034/) (2024)
- [Structured Linear CDEs: Maximally Expressive and Parallel-in-Time Sequence Models](https://mlsanity.com/paper/2505.17761/) (2025)
- [TensorGPT: Efficient Compression of Large Language Models based on Tensor-Train Decomposition](https://mlsanity.com/paper/2307.00526/) (2023)
- [Sparsifiner: Learning Sparse Instance-Dependent Attention for Efficient Vision Transformers](https://mlsanity.com/paper/2303.13755/) (2023)
- [Memory Caching: RNNs with Growing Memory](https://mlsanity.com/paper/2602.24281/) (2026)
- [Searching for Efficient Linear Layers over a Continuous Space of Structured Matrices](https://mlsanity.com/paper/2410.02117/) (2024)

## Abstract (arXiv)

Large neural networks excel in many domains, but they are expensive to train and fine-tune. A popular approach to reduce their compute or memory requirements is to replace dense weight matrices with structured ones (e.g., sparse, low-rank, Fourier transform). These methods have not seen widespread adoption (1) in end-to-end training due to unfavorable efficiency--quality tradeoffs, and (2) in dense-to-sparse fine-tuning due to lack of tractable algorithms to approximate a given dense weight matrix. To address these issues, we propose a class of matrices (Monarch) that is hardware-efficient (they are parameterized as products of two block-diagonal matrices for better hardware utilization) and expressive (they can represent many commonly used transforms). Surprisingly, the problem of approximating a dense weight matrix with a Monarch matrix, though nonconvex, has an analytical optimal solution. These properties of Monarch matrices unlock new ways to train and fine-tune sparse and dense models. We empirically validate that Monarch can achieve favorable accuracy-efficiency tradeoffs in several end-to-end sparse training applications: speeding up ViT and GPT-2 training on ImageNet classification and Wikitext-103 language modeling by 2x with comparable model quality, and reducing the error on PDE solving and MRI reconstruction tasks by 40%. In sparse-to-dense training, with a simple technique called "reverse sparsification," Monarch matrices serve as a useful intermediate representation to speed up GPT-2 pretraining on OpenWebText by 2x without quality drop. The same technique brings 23% faster BERT pretraining than even the very optimized implementation from Nvidia that set the MLPerf 1.1 record. In dense-to-sparse fine-tuning, as a proof-of-concept, our Monarch approximation algorithm speeds up BERT fine-tuning on GLUE by 1.7x with comparable accuracy.