# What makes Models Compositional? A Theoretical View: With Supplement

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 40 references that are in the map.
- First posted on arXiv 2 May 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [A Survey of Transformers](https://mlsanity.com/paper/2106.04554/) (2021)
- [Measuring Compositional Generalization: A Comprehensive Method on Realistic Data](https://mlsanity.com/paper/1912.09713/) (2019)
- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [Sparse Sinkhorn Attention](https://mlsanity.com/paper/2002.11296/) (2020)
- [Neural-Symbolic Learning and Reasoning: A Survey and Interpretation](https://mlsanity.com/paper/1711.03902/) (2017)
- [The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformers](https://mlsanity.com/paper/2108.12284/) (2021)
- [Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networks](https://mlsanity.com/paper/1810.09536/) (2018)
- [Compositional Semantic Parsing with Large Language Models](https://mlsanity.com/paper/2209.15003/) (2022)
- [Measuring Compositionality in Representation Learning](https://mlsanity.com/paper/1902.07181/) (2019)
- [Learning Compositional Rules via Neural Program Synthesis](https://mlsanity.com/paper/2003.05562/) (2020)
- [Making Transformers Solve Compositional Tasks](https://mlsanity.com/paper/2108.04378/) (2021)
- [Compositional Generalization from First Principles](https://mlsanity.com/paper/2307.05596/) (2023)
- [Memory-efficient Transformers via Top-k Attention](https://mlsanity.com/paper/2106.06899/) (2021)
- [Neural Language Modeling by Jointly Learning Syntax and Lexicon](https://mlsanity.com/paper/1711.02013/) (2017)
- [Compositional generalization in a deep seq2seq model by separating syntax and semantics](https://mlsanity.com/paper/1904.09708/) (2019)
- [Compositional Generalization by Learning Analytical Expressions](https://mlsanity.com/paper/2006.10627/) (2020)
- [Routing Networks and the Challenges of Modular and Compositional Computation](https://mlsanity.com/paper/1904.12774/) (2019)
- [Compositional Generalization for Primitive Substitutions](https://mlsanity.com/paper/1910.02612/) (2019)
- [A Fast Unified Model for Parsing and Sentence Understanding](https://mlsanity.com/paper/1603.06021/) (2016)
- [Learning Algebraic Recombination for Compositional Generalization](https://mlsanity.com/paper/2107.06516/) (2021)
- [When Can Transformers Ground and Compose: Insights from Compositional Generalization Benchmarks](https://mlsanity.com/paper/2210.12786/) (2022)
- [A Study of Compositional Generalization in Neural Models](https://mlsanity.com/paper/2006.09437/) (2020)

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

- [A Survey on Compositional Learning of AI Models: Theoretical and Experimental Practices](https://mlsanity.com/paper/2406.08787/) (2024)
- [A Complexity-Based Theory of Compositionality](https://mlsanity.com/paper/2410.14817/) (2024)
- [Quantifying artificial intelligence through algorithmic generalization](https://mlsanity.com/paper/2411.05943/) (2024)
- [Topos Theory for Generative AI and LLMs](https://mlsanity.com/paper/2508.08293/) (2025)
- [Compositional Models for Estimating Causal Effects](https://mlsanity.com/paper/2406.17714/) (2024)

## Abstract (arXiv)

Compositionality is thought to be a key component of language, and various compositional benchmarks have been developed to empirically probe the compositional generalization of existing sequence processing models. These benchmarks often highlight failures of existing models, but it is not clear why these models fail in this way. In this paper, we seek to theoretically understand the role the compositional structure of the models plays in these failures and how this structure relates to their expressivity and sample complexity. We propose a general neuro-symbolic definition of compositional functions and their compositional complexity. We then show how various existing general and special purpose sequence processing models (such as recurrent, convolution and attention-based ones) fit this definition and use it to analyze their compositional complexity. Finally, we provide theoretical guarantees for the expressivity and systematic generalization of compositional models that explicitly depend on our proposed definition and highlighting factors which drive poor empirical performance.