# A Theoretical Analysis of Provable Compositional Generalization in Neural Networks: A Necessary and Sufficient Condition

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 46 references that are in the map.
- First posted on arXiv 5 May 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Neural Module Networks](https://mlsanity.com/paper/1511.02799/) (2015)
- [Towards a Definition of Disentangled Representations](https://mlsanity.com/paper/1812.02230/) (2018)
- [Inductive Biases for Deep Learning of Higher-Level Cognition](https://mlsanity.com/paper/2011.15091/) (2020)
- [A Meta-Transfer Objective for Learning to Disentangle Causal Mechanisms](https://mlsanity.com/paper/1901.10912/) (2019)
- [The Consciousness Prior](https://mlsanity.com/paper/1709.08568/) (2017)
- [Consciousness in Artificial Intelligence: Insights from the Science of Consciousness](https://mlsanity.com/paper/2308.08708/) (2023)
- [Efficient Neural Causal Discovery without Acyclicity Constraints](https://mlsanity.com/paper/2107.10483/) (2021)
- [Compositional generalization in a deep seq2seq model by separating syntax and semantics](https://mlsanity.com/paper/1904.09708/) (2019)
- [Causal Reasoning from Meta-reinforcement Learning](https://mlsanity.com/paper/1901.08162/) (2019)
- [Compositional Generalization in Unsupervised Compositional Representation Learning: A Study on Disentanglement and Emergent Language](https://mlsanity.com/paper/2210.00482/) (2022)
- [Provable Compositional Generalization for Object-Centric Learning](https://mlsanity.com/paper/2310.05327/) (2023)
- [Discrete-Valued Neural Communication](https://mlsanity.com/paper/2107.02367/) (2021)
- [Discovering modular solutions that generalize compositionally](https://mlsanity.com/paper/2312.15001/) (2023)
- [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)
- [ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis](https://mlsanity.com/paper/2307.13883/) (2023)
- [On The Specialization of Neural Modules](https://mlsanity.com/paper/2409.14981/) (2024)
- [Compositional Risk Minimization](https://mlsanity.com/paper/2410.06303/) (2024)
- [GAMR: A Guided Attention Model for (visual) Reasoning](https://mlsanity.com/paper/2206.04928/) (2022)
- [Compositional Generalization Across Distributional Shifts with Sparse Tree Operations](https://mlsanity.com/paper/2412.14076/) (2024)

## Abstract (arXiv)

Compositional generalizationunicodex2013the ability to systematically process novel combinations of known componentsunicodex2013is a hallmark of human intelligence; however, its theoretical foundation in neural networks is not yet well understood. This paper establishes a necessary and sufficient condition for provable compositional generalization, precisely characterizing its boundary. Conceptually, the condition consists of two principles: (i) structural alignment, where a model's computational graph aligns with a task's true compositional hierarchy, and (ii) unambiguous minimized representations, where each component encodes adequate but not redundant information on the training data. The result is fully proved and machine-verified in Lean 4 and holds even in few-shot and one-shot regimes. The necessity direction establishes that provable compositional generalization cannot circumvent these requirements, while the sufficiency direction yields a unified inductive bias that jointly governs architectural design, training data properties, and regularization strategies. Building on this condition, we develop an example algorithmic approach, illustrate it through a controlled minimal example, and further demonstrate the condition on the SCAN jump task. All conclusions are derived mathematically without reliance on empirical validation. Our work provides a theoretical characterization of provable compositional generalization.