# Searching for Efficient Linear Layers over a Continuous Space of Structured Matrices

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Placed in MoE theory and gating functions, one of 12 directions in Mixture-of-experts.
- Builds on 23 of its 31 references that are in the map.
- First posted on arXiv 3 Oct 2024.

## Placed in

- Mixture-of-experts / [MoE theory and gating functions](https://mlsanity.com/moe/moe-theory-and-gating-functions/)

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (2017)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [Mixtral of Experts](https://mlsanity.com/paper/2401.04088/) (2024)
- [Scaling Laws for Autoregressive Generative Modeling](https://mlsanity.com/paper/2010.14701/) (2020)
- [Explaining Neural Scaling Laws](https://mlsanity.com/paper/2102.06701/) (2021)
- [Tensor Programs V: Tuning Large Neural Networks via Zero-Shot Hyperparameter Transfer](https://mlsanity.com/paper/2203.03466/) (2022)
- [ReLoRA: High-Rank Training Through Low-Rank Updates](https://mlsanity.com/paper/2307.05695/) (2023)
- [Feature Learning in Infinite-Width Neural Networks](https://mlsanity.com/paper/2011.14522/) (2020)
- [A Kronecker-factored approximate Fisher matrix for convolution layers](https://mlsanity.com/paper/1602.01407/) (2016)
- [Tensor Ring Decomposition](https://mlsanity.com/paper/1606.05535/) (2016)
- [A Spectral Condition for Feature Learning](https://mlsanity.com/paper/2310.17813/) (2023)
- [Monarch: Expressive Structured Matrices for Efficient and Accurate Training](https://mlsanity.com/paper/2204.00595/) (2022)
- [Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations](https://mlsanity.com/paper/1903.05895/) (2019)
- [Monarch Mixer: A Simple Sub-Quadratic GEMM-Based Architecture](https://mlsanity.com/paper/2310.12109/) (2023)
- [JetMoE: Reaching Llama2 Performance with 0.1M Dollars](https://mlsanity.com/paper/2404.07413/) (2024)
- [Tensor Programs IVb: Adaptive Optimization in the Infinite-Width Limit](https://mlsanity.com/paper/2308.01814/) (2023)
- [Compute Better Spent: Replacing Dense Layers with Structured Matrices](https://mlsanity.com/paper/2406.06248/) (2024)
- [CoLA: Exploiting Compositional Structure for Automatic and Efficient Numerical Linear Algebra](https://mlsanity.com/paper/2309.03060/) (2023)
- [Differentiable Learning of Generalized Structured Matrices for Efficient Deep Neural Networks](https://mlsanity.com/paper/2310.18882/) (2023)

## Built on by (most cited first, 13 of 13)

- [Deep Learning is Not So Mysterious or Different](https://mlsanity.com/paper/2503.02113/) (2025)
- [Position: Curvature Matrices Should Be Democratized via Linear Operators](https://mlsanity.com/paper/2501.19183/) (2025)
- [Scaling Probabilistic Circuits via Monarch Matrices](https://mlsanity.com/paper/2506.12383/) (2025)
- [Calibrating and Rotating: A Unified Framework for Weight Conditioning in PEFT](https://mlsanity.com/paper/2511.00051/) (2025)
- [EUGens: Efficient, Unified, and General Dense Layers](https://mlsanity.com/paper/2601.22563/) (2026)
- [How Model Growth, Recursion, and Boundary Operators Influence Scaling Exponents](https://mlsanity.com/paper/2609.19107/) (2026)
- [On Information Geometry and Iterative Optimization in Model Compression: Operator Factorization](https://mlsanity.com/paper/2507.09428/) (2025)
- [EUGens: Efficient, Unified, and General Dense Layers](https://mlsanity.com/paper/2410.09771/) (2024)
- [NdLinear: Preserving Multi-Dimensional Structure for Parameter-Efficient Neural Networks](https://mlsanity.com/paper/2503.17353/) (2025)
- [Customizing the Inductive Biases of Softmax Attention using Structured Matrices](https://mlsanity.com/paper/2509.07963/) (2025)
- [Sparsely gated tiny linear experts](https://mlsanity.com/paper/2606.07414/) (2026)
- [DyRA: Dynamic Residual Approximation for Efficient Matrix Multiplication in DNNs](https://mlsanity.com/paper/2610.02882/) (2026)
- [Rationally Linearized MLPs](https://mlsanity.com/paper/2610.13568/) (2026)

## Abstract (arXiv)

Dense linear layers are the dominant computational bottleneck in large neural networks, presenting a critical need for more efficient alternatives. Previous efforts focused on a small number of hand-crafted structured matrices and neglected to investigate whether these structures can surpass dense layers in terms of compute-optimal scaling laws when both the model size and training examples are optimally allocated. In this work, we present a unifying framework that enables searching among all linear operators expressible via an Einstein summation. This framework encompasses many previously proposed structures, such as low-rank, Kronecker, Tensor-Train, Block Tensor-Train (BTT), and Monarch, along with many novel structures. To analyze the framework, we develop a taxonomy of all such operators based on their computational and algebraic properties and show that differences in the compute-optimal scaling laws are mostly governed by a small number of variables that we introduce. Namely, a small ω (which measures parameter sharing) and large psi (which measures the rank) reliably led to better scaling laws. Guided by the insight that full-rank structures that maximize parameters per unit of compute perform the best, we propose BTT-MoE, a novel Mixture-of-Experts (MoE) architecture obtained by sparsifying computation in the BTT structure. In contrast to the standard sparse MoE for each entire feed-forward network, BTT-MoE learns an MoE in every single linear layer of the model, including the projection matrices in the attention blocks. We find BTT-MoE provides a substantial compute-efficiency gain over dense layers and standard MoE.