# Compositional Generalization from First Principles

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

## Key facts

- Cited by 64 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 37 references that are in the map.
- First posted on arXiv 10 Jul 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoning](https://mlsanity.com/paper/1612.06890/) (2016)
- [Object-Centric Learning with Slot Attention](https://mlsanity.com/paper/2006.15055/) (2020)
- [Towards Out-Of-Distribution Generalization: A Survey](https://mlsanity.com/paper/2108.13624/) (2021)
- [MONet: Unsupervised Scene Decomposition and Representation](https://mlsanity.com/paper/1901.11390/) (2019)
- [Multi-Object Representation Learning with Iterative Variational Inference](https://mlsanity.com/paper/1903.00450/) (2019)
- [Self-Supervised Learning with Data Augmentations Provably Isolates Content from Style](https://mlsanity.com/paper/2106.04619/) (2021)
- [Measuring Compositional Generalization: A Comprehensive Method on Realistic Data](https://mlsanity.com/paper/1912.09713/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Conditional Object-Centric Learning from Video](https://mlsanity.com/paper/2111.12594/) (2021)
- [Contrastive Learning Inverts the Data Generating Process](https://mlsanity.com/paper/2102.08850/) (2021)
- [On the Fairness of Disentangled Representations](https://mlsanity.com/paper/1905.13662/) (2019)
- [Are Disentangled Representations Helpful for Abstract Visual Reasoning?](https://mlsanity.com/paper/1905.12506/) (2019)
- [Learning to Recombine and Resample Data for Compositional Generalization](https://mlsanity.com/paper/2010.03706/) (2020)
- [Visual Representation Learning Does Not Generalize Strongly Within the Same Domain](https://mlsanity.com/paper/2107.08221/) (2021)
- [Compositional generalization in a deep seq2seq model by separating syntax and semantics](https://mlsanity.com/paper/1904.09708/) (2019)
- [Rearranging the Familiar: Testing Compositional Generalization in Recurrent Networks](https://mlsanity.com/paper/1807.07545/) (2018)
- [Complex-Valued Autoencoders for Object Discovery](https://mlsanity.com/paper/2204.02075/) (2022)
- [Exploiting Semantics in Neural Machine Translation with Graph Convolutional Networks](https://mlsanity.com/paper/1804.08313/) (2018)
- [Embrace the Gap: VAEs Perform Independent Mechanism Analysis](https://mlsanity.com/paper/2206.02416/) (2022)
- [First Steps Toward Understanding the Extrapolation of Nonlinear Models to Unseen Domains](https://mlsanity.com/paper/2211.11719/) (2022)
- [Learning to Extrapolate: A Transductive Approach](https://mlsanity.com/paper/2304.14329/) (2023)
- [Learning and generalization of compositional representations of visual scenes](https://mlsanity.com/paper/2303.13691/) (2023)

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

- [WebSailor: Navigating Super-human Reasoning for Web Agent](https://mlsanity.com/paper/2507.02592/) (2025)
- [Compositional Abilities Emerge Multiplicatively: Exploring Diffusion Models on a Synthetic Task](https://mlsanity.com/paper/2310.09336/) (2023)
- [Provable Compositional Generalization for Object-Centric Learning](https://mlsanity.com/paper/2310.05327/) (2023)
- [Compositional Generative Modeling: A Single Model is Not All You Need](https://mlsanity.com/paper/2402.01103/) (2024)
- [Does CLIP's Generalization Performance Mainly Stem from High Train-Test Similarity?](https://mlsanity.com/paper/2310.09562/) (2023)
- [Closing the Gap between TD Learning and Supervised Learning -- A Generalisation Point of View](https://mlsanity.com/paper/2401.11237/) (2024)
- [On Provable Length and Compositional Generalization](https://mlsanity.com/paper/2402.04875/) (2024)
- [When does compositional structure yield compositional generalization? A kernel theory](https://mlsanity.com/paper/2405.16391/) (2024)
- [Interaction Asymmetry: A General Principle for Learning Composable Abstractions](https://mlsanity.com/paper/2411.07784/) (2024)
- [Mechanisms of Projective Composition of Diffusion Models](https://mlsanity.com/paper/2502.04549/) (2025)
- [Deciphering the Role of Representation Disentanglement: Investigating Compositional Generalization in CLIP Models](https://mlsanity.com/paper/2407.05897/) (2024)
- [How Diffusion Models Learn to Factorize and Compose](https://mlsanity.com/paper/2408.13256/) (2024)
- [Compositional Risk Minimization](https://mlsanity.com/paper/2410.06303/) (2024)
- [A Complexity-Based Theory of Compositionality](https://mlsanity.com/paper/2410.14817/) (2024)
- [Task Generalization With AutoRegressive Compositional Structure: Can Learning From D Tasks Generalize to DT Tasks?](https://mlsanity.com/paper/2502.08991/) (2025)
- [MetaSlot: Break Through the Fixed Number of Slots in Object-Centric Learning](https://mlsanity.com/paper/2505.20772/) (2025)
- [On the Ability of Deep Networks to Learn Symmetries from Data: A Neural Kernel Theory](https://mlsanity.com/paper/2412.11521/) (2024)
- [Visual Data-Type Understanding does not emerge from Scaling Vision-Language Models](https://mlsanity.com/paper/2310.08577/) (2023)
- [When and How Does CLIP Enable Domain and Compositional Generalization?](https://mlsanity.com/paper/2502.09507/) (2025)
- [Skews in the Phenomenon Space Hinder Generalization in Text-to-Image Generation](https://mlsanity.com/paper/2403.16394/) (2024)
- [CoInD: Enabling Logical Compositions in Diffusion Models](https://mlsanity.com/paper/2503.01145/) (2025)
- [Scaling can lead to compositional generalization](https://mlsanity.com/paper/2507.07207/) (2025)
- [Adversarial D'ej`a Vu: Jailbreak Dictionary Learning for Stronger Generalization to Unseen Attacks](https://mlsanity.com/paper/2510.21910/) (2025)
- [From Isolation to Entanglement: When Do Interpretability Methods Identify and Disentangle Known Concepts?](https://mlsanity.com/paper/2512.15134/) (2025)
- [Circuit Stability Characterizes Language Model Generalization](https://mlsanity.com/paper/2505.24731/) (2025)
- [SUB: Benchmarking CBM Generalization via Synthetic Attribute Substitutions](https://mlsanity.com/paper/2507.23784/) (2025)
- [What makes Models Compositional? A Theoretical View: With Supplement](https://mlsanity.com/paper/2405.02350/) (2024)
- [Swing-by Dynamics in Concept Learning and Compositional Generalization](https://mlsanity.com/paper/2410.08309/) (2024)
- [Position: We Need An Algorithmic Understanding of Generative AI](https://mlsanity.com/paper/2507.07544/) (2025)
- [A General Theory for Compositional Generalization](https://mlsanity.com/paper/2405.11743/) (2024)

## Abstract (arXiv)

Leveraging the compositional nature of our world to expedite learning and facilitate generalization is a hallmark of human perception. In machine learning, on the other hand, achieving compositional generalization has proven to be an elusive goal, even for models with explicit compositional priors. To get a better handle on compositional generalization, we here approach it from the bottom up: Inspired by identifiable representation learning, we investigate compositionality as a property of the data-generating process rather than the data itself. This reformulation enables us to derive mild conditions on only the support of the training distribution and the model architecture, which are sufficient for compositional generalization. We further demonstrate how our theoretical framework applies to real-world scenarios and validate our findings empirically. Our results set the stage for a principled theoretical study of compositional generalization.