Towards a formal theory of compositionality
Lists
Only you see this
Abstract
Compositionality is believed to be fundamental to intelligence. In humans, it underlies the structure of thought, language, and higher-level reasoning. In AI, it enables 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, there currently exists no formal definition for it that is measurable and mathematical. Here, we propose such a definition, which we call representational compositionality. The definition is conceptually simple, quantitative, and grounded in algorithmic information theory. Intuitively, representational compositionality states that a compositional representation is both expressive and describable as a simple function of discrete parts. We validate our definition on both real and synthetic data, 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. Our definition has the potential to inspire the design of novel, theoretically-driven models that better capture the mechanisms of higher-level human thought.
BibTeX
@misc{elmoznino2025towards,
author = {Eric Elmoznino and Thomas Jiralerspong and Yoshua Bengio and Guillaume Lajoie},
title = {{Towards a formal theory of compositionality}},
year = {2025},
url = {https://openreview.net/forum?id=hKMPz3wkPV},
howpublished = {OpenReview},
note = {Submitted to ICLR 2025},
}