Monarch: Expressive Structured Matrices for Efficient and Accurate Training

1 Introduction

• Structured matrices have seen limited adoption because end-to-end training can have unfavorable efficiency–quality tradeoffs and dense-to-sparse fine-tuning lacks tractable approximation algorithms.Existing structured matrices may also be hardware-inefficient or insufficiently expressive.Source: §1 · p. 1
• Monarch matrices are products of two permuted block-diagonal matrices, leveraging GPU batch-matrix-multiply routines while representing transforms such as Fourier, sine/cosine, Chebyshev, and convolution.The class contains butterfly matrices, whose expressiveness supports representation of many fast transforms.Source: §1 · p. 2
• Reverse sparsification trains with Monarch weights for most of training, then transitions to dense weights, using Monarch as an intermediate representation for dense-model training.The approach is presented for settings where sparse training has representation or optimization difficulties, or a dense model is needed.Source: §1 · p. 2
• The Monarch projection algorithm finds an optimal approximation to a dense matrix, unlike prior projection heuristics that lack theoretical guarantees.The paper also derives an algorithm to factorize products of Monarch matrices.Source: §1 · pp. 2–3
• Across tasks, Monarch offers favorable efficiency–accuracy tradeoffs: 2× faster ViT/GPT-2 sparse training at comparable quality, up to 40% lower PDE/MRI error, and faster GPT-2 and BERT pretraining.GPT-2 pretraining is 2× faster; BERT pretraining is 23% faster than the cited Nvidia implementation that set the MLPerf 1.1 record.Source: §1 · p. 3
• On GLUE, Monarch projection yields 2× fewer parameters and 1.7× faster BERT fine-tuning with similar average accuracy to the dense model.The authors describe this as a proof of concept.Source: §1 · p. 3

2.1 Related Work

• Monarch emphasizes overall efficiency, whereas pruning methods mostly target inference efficiency and may disregard the cost of finding the smaller model.The paper describes Monarch as roughly a class of manually constructed lottery tickets.Source: §2.1 · p. 3
• Structured matrices use subquadratic parameters and runtime, and include sparse, low-rank, and fast-transform matrices used in place of dense weights.Other structured classes can represent common fast transforms, but butterfly matrices remain hardware-inefficient and pixelated butterfly reduces expressiveness.Source: §2.1 · p. 3

2.2 Butterfly Matrices

• Butterfly matrices encode divide-and-conquer multiplication structure; prior work shows all structured matrices can be expressed as products of butterfly matrices with near-optimal memory and runtime complexity.Butterfly matrices are products of butterfly factor matrices.Source: §2.2 · p. 4
• The related definitions describe butterfly factors as blocks assembled into butterfly factor matrices, and introduce the kaleidoscope hierarchy as products of butterfly matrices.The hierarchy can represent matrices whose vector multiplication is a linear arithmetic circuit, with depth governing the number of hierarchy levels.Source: §2.2 · p. 4

3 Monarch: Definition & Algorithms

• The section presents Monarch as an expressive, efficient parameterization and develops projection and factorization algorithms for its use.These algorithms support approximating dense matrices and recovering factors of products of Monarch matrices.Source: §3 · p. 4

3.1 Monarch Parametrization for Square Matrices

• Monarch matrices are products of two block-diagonal matrices up to permutation, a structure that also subsumes butterfly matrices.For square matrices, each block-diagonal factor has m blocks of size m × m, with n = m^2.Source: §3.1 · pp. 4–5, §3.2.1 · p. 5

3.2 Expressiveness and Efficiency

• Monarch matrices extend butterfly matrices, and their products include many commonly used structured transforms.The section frames this expressiveness alongside practical efficiency and provides algorithms for projection and factorization.Source: §3 · p. 4, §3.2.1 · pp. 5–6

3.2.1 Expressiveness

• Products of Monarch matrices represent convolution, Hadamard transforms, Toeplitz matrices, and AFDF matrices; products of two such products also represent Fourier, sine and cosine transforms, and other classes.The latter include (HD)3, Fastfood, and ACDC matrices.Source: §3.2.1 · p. 6

3.2.2 Efficiency

• Monarch multiplication uses O(n√n) FLOPs and is reported as 2× faster than dense multiplication in practice.A Monarch matrix has 2n√n parameters; its block-diagonal multiplications can use batch matrix multiply.Source: §3.2.2 · p. 6

3.3 Projection on the Set M of Monarch Matrices

• The nonconvex projection onto Monarch matrices has an analytical optimal solution computable in O(n^5/2) time.The algorithm reshapes the matrix into a 4D tensor and takes independent rank-1 approximations of its blocks using the SVD.Source: §3.3 · pp. 6–7

3.4 Factorization of MM∗Matrices

• Under stated assumptions, an O(n^5/2)-time algorithm recovers Monarch factors for matrices in the class of products of two Monarch matrices.The input matrix must be invertible and admit the specified factorization with no zero entries in the blocks of R.Source: §3.4 · p. 7

End-to-end sparse training

• End-to-end sparse training replaces dense model weight matrices with randomly initialized Monarch matrices and trains them with autodifferentiation and first-order methods.For Transformer baselines, the replacement covers attention projection matrices and feed-forward network weights.Source: §4 · p. 8

Sparse-to-dense training

• Sparse-to-dense training uses Monarch weights for about 90% of iterations, converts them to dense weights, then trains for the remaining 10%.The total iteration count matches dense end-to-end training; the initial Monarch phase is faster due to hardware efficiency.Source: §4 · p. 8

Dense-to-sparse fine-tuning

• Dense-to-sparse fine-tuning projects a pretrained model’s dense weights onto Monarch matrices before fine-tuning on downstream tasks.The approach uses the projection algorithm and first-order methods; block counts are typically set between 2 and 4 based on parameter budgets of 25%–50% of the dense model.Source: §4 · p. 8

5 Experiments

• Across image and language benchmarks, Monarch trains 2× faster at comparable quality; PDE error falls up to 40%, while MRI results report up to 15% higher pSNR and 3.8% higher SSIM.The experiments also report 2× faster GPT-2 pretraining without an upstream or downstream quality drop, 23% faster BERT pretraining than Nvidia’s MLPerf 1.1 implementation, and 1.7× faster BERT fine-tuning on GLUE.Source: §5 · p. 9

5.1.1 Benchmark Tasks: Image Classification, Language Modeling

• On ImageNet and WikiText-103, Monarch replaces dense weights in ViT, MLP-Mixer, and GPT-2, achieving up to 2× faster training without sacrificing model quality.The reported measures include Top-1 accuracy and training-time speedup on ImageNet, and similar perplexity at 2.0× faster training on WikiText-103.Source: §5.1.1 · p. 9, Table 1 · p. 9, Table 2 · p. 9

5.1.2 PDE solving and multi-coil MRI reconstruction

• For Navier–Stokes, Monarch neural operators improve solution accuracy by up to 40% over U-Net, TF-Net, ResNet, and FNO baselines, and can learn non-periodic or unknown boundary conditions.The comparison fixes training and test resolution at 64 × 64; the text notes that lower viscosity makes the dynamics more chaotic.Source: §5.1.2 · p. 10, Table 3 · p. 10
• On clinically acquired 3D MRI, mSENSE improves pSNR by over 1.5dB and SSIM by 2.5% over zero-filled SENSE, and by up to 4.4dB and 3.8% over U-Net in data-limited settings.mSENSE replaces standard SENSE’s IFFT with learnable Monarch matrices that preserve Fourier structure while reweighting frequencies to suppress aliasing artifacts.Source: §5.1.2 · p. 10, Table 4 · p. 10
• In few-shot MRI reconstruction at 2× acceleration, mSENSE outperforms U-Net by +4.4dB (≈15%) and 3.8% SSIM.The experiments describe this as evidence that mSENSE can be trained efficiently with limited supervised examples.Source: §5.1.2 · p. 10, Table 5 · p. 11

5.2 Sparse-to-Dense Training (reverse sparsification)

• Reverse sparsification makes BERT-large pretraining 23% faster than Nvidia’s MLPerf 1.1 implementation while yielding the same pretraining loss as conventional dense training.This was not an official MLPerf submission; the reported timing includes both training phases, whereas MLPerf measures phase 2 only.Source: §5.2 · p. 11, §5.3 · p. 11, Table 7 · p. 12

5.3 Dense-to-Sparse Fine-tuning

• After pretrained BERT weights are approximated with Monarch matrices, fine-tuning on nine GLUE tasks is 1.7× faster with similar quality to dense BERT.Table 8 reports the performance of Monarch matrices in BERT fine-tuning on GLUE.Source: §5.3 · p. 11, Table 8 · p. 12

5.2 Sparse-to-Dense Training (reverse sparsification)

• On OpenWebText, training GPT-2 with Monarch matrices for 90% of iterations before switching to dense weights reaches the same perplexity in 2× less time.The downstream zero-shot generation and classification performance is reported as comparable to dense counterparts.Source: §5.2 · p. 11, Figure 5 · p. 12

• Monarch inherits butterfly-matrix expressiveness, represents many fast transforms, and uses GPU batch-matrix-multiply routines for up to 2× speedup over dense matrix multiplication.The paper also derives an efficient algorithm for projecting arbitrary dense matrices onto Monarch factors.Source: §6 · p. 12

A Extended Related Work

• Sparse-training methods often optimize FLOP counts that may not predict GPU wall-clock time; reverse sparsification instead uses sparsity to speed dense training, not regularize it.The discussion also distinguishes this focus from pruning work aimed mainly at inference efficiency.Source: A Extended Related Work · p. 20
• Structured matrices include sparse, low-rank, and fast-transform families; prior work relates arithmetic circuits and butterfly products to efficient representations of such matrices.The section also surveys MRI reconstruction approaches and neural operators for PDEs, including their respective data, runtime, and design challenges.Source: A Extended Related Work · pp. 20–21
• Monarch-based neural operators can approximate all fast transforms, allowing automated optimization toward a suitable transform for a given PDE problem.The related-work discussion contrasts this flexibility with neural operators that mostly rely on FFTs or dense architectures.Source: A Extended Related Work · p. 21
• For MRI, an FFT-initialized factorized Monarch matrix combines a linearized FFT transformation with learnable removal of aliasing artifacts.The smaller learnable parameter set may reduce overfitting in data-limited settings while preserving Fourier structure.Source: A Extended Related Work · p. 21

B Notation Review

• The notation review distinguishes scalars, vectors, and matrices by typographic style, defines transpose and conjugate transpose, and uses 1-indexing except where stated.Results apply over real or complex numbers.Source: B Notation Review · p. 21

C General Monarch Matrix Parametrization

• The general square parametrization allows different block sizes, defining Monarch matrices from products of permuted block-diagonal factors and extending the base definition.The section introduces classes DB(b,n), BD(b,n), and M(b,n); when b = √n, M(b,n) recovers the original M(n) notation.Source: C General Monarch Matrix Parametrization · p. 22, §C.1.1 · p. 22

• Permuting a matrix in DB(b,n) yields a block-diagonal matrix in BD(n/b,n).The proof characterizes this as converting the permuted DB form to ordinary block-diagonal form.Source: §C.1.2 · pp. 23–24
• For divisors b and c of n with b dividing c, BD(b,n) is contained in BD(c,n), while DB(c,n) is contained in DB(b,n).Source: §C.1.2 · p. 25
• For n ≥ 4 a power of 2, every butterfly matrix belongs to M(b,n) for each divisor b in (1,n), and the inclusion is strict when n ≥ 512.The appendix attributes strictness to the greater parameter count available in the Monarch class for sufficiently large n.Source: §C.1.2 · pp. 25–26
• The appendix states that the Monarch matrix class strictly contains the butterfly class for sufficiently large power-of-two dimensions.This follows from the theorem's inclusion result and its strictness condition.Source: §C.1.2 · p. 25
• A matrix-vector map representable by a depth-d, s-gate linear arithmetic circuit belongs to a Monarch hierarchy with O(d) factors for power-of-two block size b.The appendix states that this representation has O(ds^1.5) parameters and is at most an O(d√s) factor larger than the kaleidoscope representation.Source: §C.1.2 · p. 26

C.2 General rectangular matrices

• The rectangular parametrization defines a Monarch matrix as a product of DB and BD factors with potentially different dimensions and block sizes.It assumes the block sizes divide their corresponding dimensions and that n1/b1 = n2/b2.Source: §C.2 · pp. 26–27
• A wrapped diagonal matrix has nonzeros constrained by matching indices modulo the smaller block dimension; rectangular DB blocks are built from these matrices.When the dimensions are reversed, the definition is applied to the transpose.Source: §C.2 · p. 27
• The section proves that permuting the rows and columns of a rectangular DB matrix converts it into the corresponding rectangular block-diagonal form.The theorem requires the common block size b to divide both matrix dimensions.Source: §C.2 · p. 27

D.1 Expressiveness of M

• Monarch matrices represent convolution, Hadamard, Toeplitz, AFDF, Fourier, discrete sine/cosine, (HD)3, Fastfood, and ACDC transforms or matrices through their containment of butterfly classes.The first four follow from Monarch containing the butterfly class; the latter set follows for the squared classes.Source: §D.1 · p. 28

D.2 Projection onto M

• The projection objective decomposes into m × m independent rank-1 approximation problems, one for each corresponding slice of the reshaped input matrix.The optimal rank-1 factors come from each slice’s SVD by the Eckart–Young theorem.Source: §D.2 · p. 29
• O(n^5/2) is the projection algorithm’s total time complexity, from m · m SVDs of size m × m.Each SVD takes O(m^3) time.Source: §D.2 · p. 29

D.3 Monarch Factorizations for Matrices in MM∗

• Assumption D.1 requires an invertible M with an R factor whose diagonal blocks have no zero entries; the proof notes that invertibility of M can be weakened.The proof says it suffices for all blocks f Mij to be invertible, given the nonzero-block assumption on R.Source: §D.3 · pp. 29, 32
• The algorithm forms matrices F(i, j) from the blocks of M and chooses C1 to simultaneously diagonalize them, then recovers the remaining factors.A matrix Q simultaneously diagonalizes the set when QGiQ−1 is diagonal for every member Gi.Source: §D.3 · p. 30
• Algorithm 2 finds Monarch factors for an n × n matrix in MM∗(b,n) satisfying Assumption 3.3.The theorem states that the returned factors are valid.Source: §D.3 · pp. 30–31
• Simultaneous diagonalization of k matrices takes O(kn^3) time in the described procedure.The passage notes that iterative simultaneous diagonalization methods could speed up this step in practice.Source: §D.3 · p. 32

E.1.1 Image Classification

• Image-classification Monarch models replace dense attention projections and FFN linear layers, use four blocks, and reduce stochastic depth because the models are smaller.The reported wall-clock training time is measured on V100 GPUs.Source: §E.1.1 · p. 32

E.1.2 Language Modeling

• Language-model Monarch variants replace dense attention projections and FFN linear layers, use four blocks, and reduce dropout because the models are smaller.Training uses effective batch size 512 with gradient accumulation; wall-clock time is measured on V100 GPUs.Source: §E.1.2 · p. 33

E.2 Details for PDE Solving

• The PDE experiments adopt FNO’s Navier–Stokes setting and data generation, using 1,000 training pairs across viscosities 1e−3, 1e−4, and 1e−5.The corresponding time intervals are T = 50, 30, and 20, respectively.Source: §E.2 · p. 33

E.3 Details for GPT-2 Downstream Tasks

• GPT-2-medium trained with Monarch reverse sparsification achieves comparable or better performance than the dense model on zero-shot generation and five classification tasks.The classification tasks are SST2, Trec, CB, Agnews, and Dbpedia; Table 12 reports their accuracy.Source: §E.3 · p. 33, Table 12 · p. 34

E.4 Details for BERT Pretraining

• BERT pretraining uses DeepSpeed ZeRO stage 1 to shard optimizer states and applies the optimizations used in Nvidia’s MLPerf 1.1 implementation.The setup uses LAMB, mixed precision, and gradient accumulation to reach effective batch sizes of 64k sequences in phase 1 and 32k in phase 2.Source: §E.4 · p. 34

E.5.1 Background

• The accelerated multi-coil MRI forward model maps the image through coil sensitivities and a Fourier transform, then undersamples k-space and adds complex Gaussian noise.Because sampling is below the Nyquist rate, reconstructing the underlying image is ill-posed.Source: §E.5.1 · p. 34

E.5.2 Experimental Details

• The SKM-TEA Raw Data Track uses dual-echo 3D MRI scans with Poisson Disc undersampling masks to simulate accelerated scans.Scans were filtered to the most frequent shape, 512 × 512 × 160, dropping 3 of 155 scans because Monarch matrices have an explicit shape constraint.Source: §E.5.2 · p. 35
• mSENSE makes the SENSE inverse Fourier transform learnable by parameterizing it with a Monarch matrix initialized to the IFFT.It has 137× fewer trainable parameters than U-Net.Source: §E.5.2 · p. 35
• Reconstruction performance is evaluated with pSNR and SSIM separately on each echo, computed over each echo’s 3D volume.The baselines are SENSE and U-Net; the supplied table caption identifies their configurations but provides no configuration values.Source: §E.5.2 · p. 35, Table 13 · p. 35
• mSENSE recovers fine structures with higher fidelity than SENSE and U-Net, and avoids overblurring the lower-SNR second echo.The sample reconstructions use one training scan for mSENSE and U-Net; SENSE is untrained.Source: §E.5.2 · p. 35, Figure 6 · p. 36, Figure 7 · p. 37