Towards a Formal Theory of Representational Compositionality

Compositionality is believed to be fundamental to intelligence. In humans, it underlies the structure of thought and language. 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, we lack satisfying formal definitions for it. Here, we propose such a definition called representational compositionality that 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 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 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.

Compositionality is the human ability to combine simple concepts into complex ideas—such as forming new sentences from known words or imagining novel scenes from familiar objects. In artificial intelligence (AI), compositionality helps models adapt quickly to new situations they have never directly experienced. However, despite its importance, scientists haven't agreed on a clear, quantitative way to measure or even define compositionality.We developed a formal definition of compositionality called "representational compositionality" grounded in a mathematical framework known as algorithmic information theory. Simply put, representational compositionality defines a representation as compositional if complex ideas can be easily and concisely described using combinations of simpler parts. We tested our definition with both artificial and real-world data and found it aligns closely with intuitions from cognitive science and AI research.Our work provides researchers with a precise tool to measure compositionality, opening avenues for designing smarter AI systems capable of more human-like learning and reasoning.