# A Complexity-Based Theory of Compositionality

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 62 of its 103 references that are in the map.
- First posted on arXiv 18 Oct 2024.

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

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Neural Discrete Representation Learning](https://mlsanity.com/paper/1711.00937/) (2017)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [Generating Diverse High-Fidelity Images with VQ-VAE-2](https://mlsanity.com/paper/1906.00446/) (2019)
- [No Language Left Behind: Scaling Human-Centered Machine Translation](https://mlsanity.com/paper/2207.04672/) (2022)
- [Object-Centric Learning with Slot Attention](https://mlsanity.com/paper/2006.15055/) (2020)
- [Making Monolingual Sentence Embeddings Multilingual using Knowledge Distillation](https://mlsanity.com/paper/2004.09813/) (2020)
- [Flow Network based Generative Models for Non-Iterative Diverse Candidate Generation](https://mlsanity.com/paper/2106.04399/) (2021)
- [Neural Module Networks](https://mlsanity.com/paper/1511.02799/) (2015)
- [GFlowNet Foundations](https://mlsanity.com/paper/2111.09266/) (2021)
- [Inductive Biases for Deep Learning of Higher-Level Cognition](https://mlsanity.com/paper/2011.15091/) (2020)
- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning](https://mlsanity.com/paper/2006.08381/) (2020)
- [Disentanglement via Mechanism Sparsity Regularization: A New Principle for Nonlinear ICA](https://mlsanity.com/paper/2107.10098/) (2021)
- [Weakly supervised causal representation learning](https://mlsanity.com/paper/2203.16437/) (2022)
- [CITRIS: Causal Identifiability from Temporal Intervened Sequences](https://mlsanity.com/paper/2202.03169/) (2022)
- [Transformer visualization via dictionary learning: contextualized embedding as a linear superposition of transformer factors](https://mlsanity.com/paper/2103.15949/) (2021)
- [The Consciousness Prior](https://mlsanity.com/paper/1709.08568/) (2017)
- [Does CLIP Bind Concepts? Probing Compositionality in Large Image Models](https://mlsanity.com/paper/2212.10537/) (2022)
- [Amortizing intractable inference in large language models](https://mlsanity.com/paper/2310.04363/) (2023)
- [Measuring Compositionality in Representation Learning](https://mlsanity.com/paper/1902.07181/) (2019)
- [Modular Deep Learning](https://mlsanity.com/paper/2302.11529/) (2023)
- [Compositional Languages Emerge in a Neural Iterated Learning Model](https://mlsanity.com/paper/2002.01365/) (2020)
- [Neural Production Systems: Learning Rule-Governed Visual Dynamics](https://mlsanity.com/paper/2103.01937/) (2021)
- [The Description Length of Deep Learning Models](https://mlsanity.com/paper/1802.07044/) (2018)
- [Ease-of-Teaching and Language Structure from Emergent Communication](https://mlsanity.com/paper/1906.02403/) (2019)
- [Weakly Supervised Representation Learning with Sparse Perturbations](https://mlsanity.com/paper/2206.01101/) (2022)
- [Compositional Generalization from First Principles](https://mlsanity.com/paper/2307.05596/) (2023)

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

- [Does Data Scaling Lead to Visual Compositional Generalization?](https://mlsanity.com/paper/2507.07102/) (2025)
- [Scaling can lead to compositional generalization](https://mlsanity.com/paper/2507.07207/) (2025)
- [Position: We Need An Algorithmic Understanding of Generative AI](https://mlsanity.com/paper/2507.07544/) (2025)
- [Foundations of Interpretable Models](https://mlsanity.com/paper/2508.00545/) (2025)
- [AI in a vat: Fundamental limits of efficient world modelling for agent sandboxing and interpretability](https://mlsanity.com/paper/2504.04608/) (2025)
- [TRACE for Tracking the Emergence of Semantic Representations in Transformers](https://mlsanity.com/paper/2505.17998/) (2025)
- [Systematic Generalization in Language Models Scales with Information Entropy](https://mlsanity.com/paper/2505.13089/) (2025)
- [Semantic Communication meets System 2 ML: How Abstraction, Compositionality and Emergent Languages Shape Intelligence](https://mlsanity.com/paper/2505.20964/) (2025)
- [Quantifying Compositionality of Classic and State-of-the-Art Embeddings](https://mlsanity.com/paper/2509.19332/) (2025)
- [Genomic Next-Token Predictors are In-Context Learners](https://mlsanity.com/paper/2511.12797/) (2025)
- [Disassociating performance from compositional feature learning](https://mlsanity.com/paper/2505.09716/) (2025)
- [Semantic-based Distributed Learning for Diverse and Discriminative Representations](https://mlsanity.com/paper/2604.18237/) (2026)
- [Investigating More Explainable and Partition-Free Compositionality Estimation for LLMs: A Rule-Generation Perspective](https://mlsanity.com/paper/2604.27340/) (2026)

## Abstract (arXiv)

Compositionality is believed to be fundamental to intelligence. In humans, it underlies the structure of thought, language, and higher-level reasoning. In AI, compositional representations can enable a powerful form of out-of-distribution generalization, in which a model systematically adapts to novel combinations of known concepts. However, while we have strong intuitions about what compositionality is, we lack satisfying formal definitions for it that are measurable and mathematical. Here, we propose such a definition, which we call representational compositionality, that accounts for and extends our intuitions about compositionality. The definition is conceptually simple, quantitative, grounded in algorithmic information theory, and applicable to any representation. Intuitively, representational compositionality states that a compositional representation satisfies three properties. First, it must be expressive. Second, it must be possible to re-describe the representation as a function of discrete symbolic sequences with re-combinable parts, analogous to sentences in natural language. Third, the function that relates these symbolic sequences to the representation, analogous to semantics in natural language, must be simple. Through experiments on both synthetic and real world data, we validate our definition of compositionality and show how it unifies disparate intuitions from across the literature in both AI and cognitive science. We also show that representational compositionality, while theoretically intractable, can be readily estimated using standard deep learning tools. We hope that our definition can inspire the design of novel, theoretically-driven models that better capture the mechanisms of compositional thought. We make our code available at https://github.com/EricElmoznino/complexity_compositionality.