# When does compositional structure yield compositional generalization? A kernel theory

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

## Key facts

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

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models](https://mlsanity.com/paper/2206.04615/) (2022)
- [Shortcut Learning in Deep Neural Networks](https://mlsanity.com/paper/2004.07780/) (2020)
- [CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoning](https://mlsanity.com/paper/1612.06890/) (2016)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [OK-VQA: A Visual Question Answering Benchmark Requiring External Knowledge](https://mlsanity.com/paper/1906.00067/) (2019)
- [Challenging Common Assumptions in the Unsupervised Learning of Disentangled Representations](https://mlsanity.com/paper/1811.12359/) (2018)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation](https://mlsanity.com/paper/2008.03703/) (2020)
- [Does Learning Require Memorization? A Short Tale about a Long Tail](https://mlsanity.com/paper/1906.05271/) (2019)
- [Neural Module Networks](https://mlsanity.com/paper/1511.02799/) (2015)
- [The Pitfalls of Simplicity Bias in Neural Networks](https://mlsanity.com/paper/2006.07710/) (2020)
- [Gradient Descent Maximizes the Margin of Homogeneous Neural Networks](https://mlsanity.com/paper/1906.05890/) (2019)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [Measuring Compositional Generalization: A Comprehensive Method on Realistic Data](https://mlsanity.com/paper/1912.09713/) (2019)
- [Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss](https://mlsanity.com/paper/2002.04486/) (2020)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the Neural Tangent Kernel](https://mlsanity.com/paper/2010.15110/) (2020)
- [CREPE: Can Vision-Language Foundation Models Reason Compositionally?](https://mlsanity.com/paper/2212.07796/) (2022)
- [Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks](https://mlsanity.com/paper/2006.13198/) (2020)
- [Understanding the Failure Modes of Out-of-Distribution Generalization](https://mlsanity.com/paper/2010.15775/) (2020)
- [What shapes feature representations? Exploring datasets, architectures, and training](https://mlsanity.com/paper/2006.12433/) (2020)

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

- [Interaction Asymmetry: A General Principle for Learning Composable Abstractions](https://mlsanity.com/paper/2411.07784/) (2024)
- [A Complexity-Based Theory of Compositionality](https://mlsanity.com/paper/2410.14817/) (2024)
- [Does Data Scaling Lead to Visual Compositional Generalization?](https://mlsanity.com/paper/2507.07102/) (2025)
- [Task Generalization With AutoRegressive Compositional Structure: Can Learning From D Tasks Generalize to DT Tasks?](https://mlsanity.com/paper/2502.08991/) (2025)
- [On the Ability of Deep Networks to Learn Symmetries from Data: A Neural Kernel Theory](https://mlsanity.com/paper/2412.11521/) (2024)
- [Scaling can lead to compositional generalization](https://mlsanity.com/paper/2507.07207/) (2025)
- [Quantifying artificial intelligence through algorithmic generalization](https://mlsanity.com/paper/2411.05943/) (2024)
- [Compositional Generalization via Forced Rendering of Disentangled Latents](https://mlsanity.com/paper/2501.18797/) (2025)
- [Systematic Generalization in Language Models Scales with Information Entropy](https://mlsanity.com/paper/2505.13089/) (2025)
- [Learning interpretable positional encodings in transformers depends on initialization](https://mlsanity.com/paper/2406.08272/) (2024)
- [Memorizing Long-tail Data Can Help Generalization Through Composition](https://mlsanity.com/paper/2510.16322/) (2025)
- [Extrapolation Guarantees for Perturbation Modeling Under the Additive Latent Shift Assumption](https://mlsanity.com/paper/2504.18522/) (2025)
- [A Theoretical Analysis of Provable Compositional Generalization in Neural Networks: A Necessary and Sufficient Condition](https://mlsanity.com/paper/2505.02627/) (2025)
- [Generalization in LLM Problem Solving: The Case of the Shortest Path](https://mlsanity.com/paper/2604.15306/) (2026)
- [A mathematical theory of balancing relational generalization and memorization](https://mlsanity.com/paper/2605.22972/) (2026)
- [How can embedding models bind concepts?](https://mlsanity.com/paper/2605.31503/) (2026)
- [ConTraIRL: Factorized Contrastive Abstractions for Transferable IRL](https://mlsanity.com/paper/2606.03017/) (2026)
- [Hierarchical Compositionality for An Assistive AI Agent](https://mlsanity.com/paper/2608.10330/) (2026)
- [Distributional Extrapolation for Interactions](https://mlsanity.com/paper/2608.19849/) (2026)
- [Predicting Unseen Scientific Interactions: Conditional Flow Models Hallucinate Non-Additive Effects](https://mlsanity.com/paper/2610.20288/) (2026)

## Abstract (arXiv)

Compositional generalization (the ability to respond correctly to novel combinations of familiar components) is thought to be a cornerstone of intelligent behavior. Compositionally structured (e.g. disentangled) representations support this ability; however, the conditions under which they are sufficient for the emergence of compositional generalization remain unclear. To address this gap, we present a theory of compositional generalization in kernel models with fixed, compositionally structured representations. This provides a tractable framework for characterizing the impact of training data statistics on generalization. We find that these models are limited to functions that assign values to each combination of components seen during training, and then sum up these values ("conjunction-wise additivity"). This imposes fundamental restrictions on the set of tasks compositionally structured kernel models can learn, in particular preventing them from transitively generalizing equivalence relations. Even for compositional tasks that they can learn in principle, we identify novel failure modes in compositional generalization (memorization leak and shortcut bias) that arise from biases in the training data. Finally, we empirically validate our theory, showing that it captures the behavior of deep neural networks (convolutional networks, residual networks, and Vision Transformers) trained on a set of compositional tasks with similarly structured data. Ultimately, this work examines how statistical structure in the training data can affect compositional generalization, with implications for how to identify and remedy failure modes in deep learning models.