# A General Theory for Compositional Generalization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 63 references that are in the map.
- First posted on arXiv 20 May 2024.

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

- [WILDS: A Benchmark of in-the-Wild Distribution Shifts](https://mlsanity.com/paper/2012.07421/) (2020)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [The Option-Critic Architecture](https://mlsanity.com/paper/1609.05140/) (2016)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Neural Style Transfer: A Review](https://mlsanity.com/paper/1705.04058/) (2017)
- [Deep Learning for Text Style Transfer: A Survey](https://mlsanity.com/paper/2011.00416/) (2020)
- [Generalization in Deep Learning](https://mlsanity.com/paper/1710.05468/) (2017)
- [Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1709.01953/) (2017)
- [Extending the WILDS Benchmark for Unsupervised Adaptation](https://mlsanity.com/paper/2112.05090/) (2021)
- [SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data](https://mlsanity.com/paper/1710.10174/) (2017)
- [Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate](https://mlsanity.com/paper/1806.01796/) (2018)
- [Compositional Generalization from First Principles](https://mlsanity.com/paper/2307.05596/) (2023)
- [Human few-shot learning of compositional instructions](https://mlsanity.com/paper/1901.04587/) (2019)
- [Improving Compositional Generalization with Latent Structure and Data Augmentation](https://mlsanity.com/paper/2112.07610/) (2021)
- [Provably Learning Object-Centric Representations](https://mlsanity.com/paper/2305.14229/) (2023)
- [Tighter expected generalization error bounds via Wasserstein distance](https://mlsanity.com/paper/2101.09315/) (2021)
- [Improving Compositional Generalization in Semantic Parsing](https://mlsanity.com/paper/2010.05647/) (2020)
- [Provable Compositional Generalization for Object-Centric Learning](https://mlsanity.com/paper/2310.05327/) (2023)
- [On the Compositional Generalization Gap of In-Context Learning](https://mlsanity.com/paper/2211.08473/) (2022)
- [First Steps Toward Understanding the Extrapolation of Nonlinear Models to Unseen Domains](https://mlsanity.com/paper/2211.11719/) (2022)
- [Solving Compositional Reinforcement Learning Problems via Task Reduction](https://mlsanity.com/paper/2103.07607/) (2021)
- [Learning to Extrapolate: A Transductive Approach](https://mlsanity.com/paper/2304.14329/) (2023)
- [The no-free-lunch theorems of supervised learning](https://mlsanity.com/paper/2202.04513/) (2022)
- [Improving Compositional Generalization Using Iterated Learning and Simplicial Embeddings](https://mlsanity.com/paper/2310.18777/) (2023)
- [What is important about the No Free Lunch theorems?](https://mlsanity.com/paper/2007.10928/) (2020)
- [Learning Trajectories are Generalization Indicators](https://mlsanity.com/paper/2304.12579/) (2023)
- [Generativity and Interactional Effects: an Overview](https://mlsanity.com/paper/1911.10406/) (2019)
- [On the Mathematical Structure of Cascade Effects and Emergent Phenomena](https://mlsanity.com/paper/1911.10376/) (2019)

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

- [Learning to Substitute Components for Compositional Generalization](https://mlsanity.com/paper/2502.20834/) (2025)
- [Tool Use Reduces Depth-Induced Collapse in OOD Reasoning](https://mlsanity.com/paper/2602.21061/) (2026)
- [Generalization in LLM Problem Solving: The Case of the Shortest Path](https://mlsanity.com/paper/2604.15306/) (2026)
- [Distributional Extrapolation for Interactions](https://mlsanity.com/paper/2608.19849/) (2026)

## Abstract (arXiv)

Compositional Generalization (CG) embodies the ability to comprehend novel combinations of familiar concepts, representing a significant cognitive leap in human intellectual advancement. Despite its critical importance, the deep neural network (DNN) faces challenges in addressing the compositional generalization problem, prompting considerable research interest. However, existing theories often rely on task-specific assumptions, constraining the comprehensive understanding of CG. This study aims to explore compositional generalization from a task-agnostic perspective, offering a complementary viewpoint to task-specific analyses. The primary challenge is to define CG without overly restricting its scope, a feat achieved by identifying its fundamental characteristics and basing the definition on them. Using this definition, we seek to answer the question "what does the ultimate solution to CG look like?" through the following theoretical findings: 1) the first No Free Lunch theorem in CG, indicating the absence of general solutions; 2) a novel generalization bound applicable to any CG problem, specifying the conditions for an effective CG solution; and 3) the introduction of the generative effect to enhance understanding of CG problems and their solutions. This paper's significance lies in providing a general theory for CG problems, which, when combined with prior theorems under task-specific scenarios, can lead to a comprehensive understanding of CG.