# Position: A Theory of Deep Learning Must Include Compositional Sparsity

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 70 references that are in the map.
- First posted on arXiv 3 Jul 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [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)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Analyzing the Structure of Attention in a Transformer Language Model](https://mlsanity.com/paper/1906.04284/) (2019)
- [Deep Learning without Poor Local Minima](https://mlsanity.com/paper/1605.07110/) (2016)
- [Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review](https://mlsanity.com/paper/1611.00740/) (2016)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks](https://mlsanity.com/paper/2202.08658/) (2022)
- [Online stochastic gradient descent on non-convex losses from high-dimensional inference](https://mlsanity.com/paper/2003.10409/) (2020)
- [How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model](https://mlsanity.com/paper/2307.02129/) (2023)
- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)
- [Superposition of many models into one](https://mlsanity.com/paper/1902.05522/) (2019)
- [The Implicit Bias of Depth: How Incremental Learning Drives Generalization](https://mlsanity.com/paper/1909.12051/) (2019)
- [The staircase property: How hierarchical structure can guide deep learning](https://mlsanity.com/paper/2108.10573/) (2021)
- [Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit](https://mlsanity.com/paper/2406.01581/) (2024)
- [Characterizing Intrinsic Compositionality in Transformers with Tree Projections](https://mlsanity.com/paper/2211.01288/) (2022)
- [The Impact of Depth on Compositional Generalization in Transformer Language Models](https://mlsanity.com/paper/2310.19956/) (2023)
- [Symmetry Induces Structure and Constraint of Learning](https://mlsanity.com/paper/2309.16932/) (2023)
- [Hardness of Learning Neural Networks under the Manifold Hypothesis](https://mlsanity.com/paper/2406.01461/) (2024)
- [How Sparse Attention Approximates Exact Attention? Your Attention is Naturally nC-Sparse](https://mlsanity.com/paper/2404.02690/) (2024)
- [Learning Invariant Weights in Neural Networks](https://mlsanity.com/paper/2202.12439/) (2022)
- [Survey on Algorithms for multi-index models](https://mlsanity.com/paper/2504.05426/) (2025)
- [How Diffusion Models Learn to Factorize and Compose](https://mlsanity.com/paper/2408.13256/) (2024)
- [Fast Feedforward Networks](https://mlsanity.com/paper/2308.14711/) (2023)

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

- [Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets](https://mlsanity.com/paper/2511.20888/) (2025)
- [Towards Worst-Case Guarantees with Scale-Aware Interpretability](https://mlsanity.com/paper/2602.05184/) (2026)
- [Learning Sparse Compositional Functions with Norm-Constrained Neural Networks](https://mlsanity.com/paper/2605.25608/) (2026)
- [The Advantage of Fine-Grained Training](https://mlsanity.com/paper/2509.05130/) (2025)
- [A Compositional Kernel Model for Feature Learning](https://mlsanity.com/paper/2509.14158/) (2025)
- [A Deep Risk Estimator for Known Operator Learning](https://mlsanity.com/paper/2605.08517/) (2026)
- [From Mechanistic to Compositional Interpretability](https://mlsanity.com/paper/2605.08934/) (2026)
- [Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximation](https://mlsanity.com/paper/2606.26705/) (2026)
- [Tool Use Reduces Depth-Induced Collapse in OOD Reasoning](https://mlsanity.com/paper/2602.21061/) (2026)
- [Compositional Sparsity as an Inductive Bias for Neural Architecture Design](https://mlsanity.com/paper/2605.14764/) (2026)
- [Compositionality Emerges in a Narrow Depth-Connectivity Regime: Architecture Constraints and Solution Manifolds](https://mlsanity.com/paper/2606.19941/) (2026)
- [Hierarchical Compositionality for An Assistive AI Agent](https://mlsanity.com/paper/2608.10330/) (2026)
- [An Investigation of the NeurIPS and ICML 2025 Position Tracks](https://mlsanity.com/paper/2608.16894/) (2026)
- [Transfer Learning in Nonparametric Regression with Deep ReLU Networks](https://mlsanity.com/paper/2608.20255/) (2026)

## Abstract (arXiv)

Overparametrized Deep Neural Networks (DNNs) have demonstrated remarkable success in a wide variety of domains too high-dimensional for classical shallow networks subject to the curse of dimensionality. However, open questions about fundamental principles, that govern the learning dynamics of DNNs, remain. In this position paper we argue that it is the ability of DNNs to exploit the compositionally sparse structure of the target function driving their success. As such, DNNs can leverage the property that most practically relevant functions can be composed from a small set of constituent functions, each of which relies only on a low-dimensional subset of all inputs. We show that this property is shared by all efficiently Turing-computable functions and is therefore highly likely present in all current learning problems. While some promising theoretical insights on questions concerned with approximation and generalization exist in the setting of compositionally sparse functions, several important questions on the learnability and optimization of DNNs remain. Completing the picture of the role of compositional sparsity in deep learning is essential to a comprehensive theory of artificial, and even general, intelligence.