Defining and Generating Compositional Structure

Eric Elmoznino; Tejas Kasetty; Blaise Agüera y Arcas; Yoshua Bengio; Guillaume Lajoie

cs.AIOct 14, 2026

Defining and Generating Compositional Structure

Authors: Eric Elmoznino, Tejas Kasetty, Blaise Agüera y Arcas, Yoshua Bengio, Guillaume Lajoie

Organizations: Mila – Quebec AI Institute · Université de Montréal · Google Paradigms of Intelligence Team · LawZero

Abstract

Compositional structure is pervasive in nature and across scales: atoms combine into molecules, molecules into cells, and cells into organisms, while further compositional hierarchies appear within each level. More broadly, compositionality, the reuse and recombination of parts into novel structures, is a fundamental source of interesting complexity in both natural and artificial systems. Yet despite its importance, and despite our apparent ease in recognizing it, mathematical accounts capturing what we intuitively mean by compositional structure remain limited. Here, we fill this gap by formalizing a simple idea: compositional structure emerges when parts, considered together, reveal shared structure that is not captured when those parts are modeled separately. We express this idea using algorithmic information theory, the mathematics of information and compression, which provides a natural way to identify structure in arbitrary data without specifying in advance what that structure must look like. Applied across scales, our definition informs where and how compositional structure emerges within an object. Using tractable approximations, we then invert the framework to generate compositional objects: we specify the desired form of their compositional structure without prescribing their particular content, and optimize directly over strings and images. The resulting objects exhibit readily recognizable hierarchical reuse and part-whole organization, suggesting that the definition captures compositional structure rather than merely complexity, regularity, or shared information. Finally, we discuss implications for machine learning, including a new perspective on depth in neural architectures and principles for constructing compositional data curricula capable of supporting open-ended learning.

Figures & tables

Figure 1: Visual illustration of compositional structure profiles. A profile records where novel structure emerges along a hierarchical decomposition of an object. At each merge, the vertical increment represents the additional information required to describe the model of the whole from the models of its parts,

C(x_{a},x_{b}\to x):=K(m_{x}\mid m_{x_{a}},m_{x_{b}})

(top left). Different distributions of these increments produce characteristic signatures: negligible novel structure for uncompositional objects, structure confined to bounded scales for structured iid data, structure distributed across nested scales for hierarchical objects, and continually accumulating structure for open-ended processes.

Figure 2: Generating compositional strings. a. We evolve a population of strings using either (i) a reward that maximizes multi-scale compositional structure using our definition ( blue ; Equation 14 ) or (ii) an alternative reward that just maximizes structure without any pressure for compositionality ( orange ; $K(m_{x})$ ). b. Growth of the average population reward over time. Both the compositionality and structure rewards are successfully optimized. We plot in arbitrary units (a.u.) on the y-axis normalized based on the top score for each reward. c. Statistics of grammars fit to strings over time, when optimizing each reward. Grammars fit to strings generated by the compositionality reward are significantly deeper, with more nested levels of hierarchy, despite being shorter than those of strings generated from the structure reward in terms of rule length, number of rules, and number of symbols. d. Dot plots of the highest-reward string optimized using the compositionality and structure rewards, and for a random string. Strings generated from the compositionality reward have substantial repeated patterns, corresponding to contiguous diagonal lines off of the main diagonal. These patterns themselves contain repeated substrings, corresponding to shorter diagonal lines appearing within the same block of rows/columns. In contrast, strings generated from the structure reward exhibit more random segments, and when repeats do occur they tend to be longer and less hierarchical. Seeds. Shaded regions in panels (b, c) reflect the standard error of the mean across $10$ seeds. Panel (d) shows results for one representative seed only; dot plots for all seeds are provided in Section D.1 .

Figure 3: Generating compositional images. a. We evolve a population of images using either (i) a reward that maximizes multi-scale compositional structure using our definition ( blue ; Equation 14 ) or (ii) an alternative reward that just maximizes structure without any pressure for compositionality ( orange ; $K(m_{x})$ ). Evolved genomes are Compositional Pattern-Producing Networks (CPPNs) that generate image phenotypes. b. Growth of the average population reward over time. Both the compositionality and structure rewards are successfully optimized. We plot in arbitrary units (a.u.) on the y-axis normalized based on the top score for each reward. c. Statistics of image-generating CPPNs over time, when optimizing each reward. Both rewards produce CPPNs of similar size (nodes and connections), but compositionality-optimized CPPNs exhibit greater feature recombination. See main text and Section D.2 for descriptions of each statistic. d. Example images generated as a result of optimizing each reward. Optimizing for compositionality results in images with unified features, whereas optimizing for structure results in more disjoint images. More examples are provided in Section D.2 . Seeds. Shaded regions in panels (b, c) reflect the standard error of the mean across $3$ seeds.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Figure D.1: Dot plots for all seeds. Compositionality-optimized strings have blue borders, and structure-optimized strings have orange borders.

Setting	Value
Population and initialization	$200$ feed-forward genomes; initially no hidden nodes, with both coordinate inputs fully connected to all three outputs
Activations	Hidden-node default tanh; mutation options identity, sigmoid, tanh, and Gaussian; activation mutation probability $0.12$ ; output activations fixed to tanh
Structural mutation	Add connection $0.35$ ; delete connection $0.08$ ; add node $0.25$ ; delete node $0.05$
Weights and biases	Gaussian initialization with mean $0$ and standard deviation $1$ ; weight mutation probability $0.8$ ; bias mutation probability $0.7$ ; replacement probability $0.1$ ; additive-mutation standard deviation $0.75$ ; values clipped to $[-30,30]$
Speciation	Compatibility threshold $2.8$ ; coefficient $1.0$ for nodes or connections present in only one genome; coefficient $0.8$ for weight differences
Stagnation	Species considered stagnant after $30$ generations without improvement; the three highest-fitness species protected from stagnation removal

Appendix

Table D.1: NEAT hyperparameters for the image experiment. Mutation probabilities are applied by neat-python during genome reproduction.

Metric	Description
Nodes	Number of hidden nodes.
Connections	Number of connections between nodes.
Depth	Longest input-to-output path length, measured in connections.
$\log_{10}(1+\#\text{Paths})$	Number of distinct input-to-output paths.
Fan-out (max)	Maximum number of connections going out of a hidden node.
Fan-in (max)	Maximum number of connections going in to a hidden node.

Appendix

Table D.2: CPPN structural statistics recorded during evolution. Each metric is summarized across the population using its mean and maximum.

Figure D.2: Additional images generated from compositionality-optimized CPPNs.

Figure D.3: Additional images generated from structure-optimized CPPNs.

Compositional Image Generation

Compositional image generation studies how to combine objects, attributes, spatial relations, and visual references into coherent, controllable images.

See all 85 papers

A Spectral Theory of Compositional Learning
Sep 27, 2026Hugo RydelComputational Cognitive Modeling Compositional Reasoning
University of Manchester
A Theoretical Analysis of Provable Compositional Generalization in Neural Networks: A Necessary and Sufficient Condition
May 5, 2025Yuanpeng LiCompositional Generalization
Compositionality Emerges in a Narrow Depth-Connectivity Regime: Architecture Constraints and Solution Manifolds
Jun 18, 2026Dat H. Do, Rushi Shah, Duc V. Le +1Sparse Neural Networks Compositional Representation Learning
National University of Singapore1 · University of Twente2

Sep 27, 2026J/K move · Enter open · S save

A Spectral Theory of Compositional Learning

Hugo Rydel

University of Manchester

Computational Cognitive Modeling Compositional Reasoning Statistical Learning Theory Compositional Representation Learning

Open paper AskPDF arXiv

How does compositional reasoning emerge during learning? We address this question by mathematically analyzing the learning dynamics of deep linear networks. We train these networks in structured synthetic environments and derive a theory linking the structure of experience to compositional learning. Our theory predicts when compositional inferences emerge, whether they are identifiable from the available evidence, and how new linking evidence can rapidly unlock previously unavailable inferences. These results provide a qualitative explanation for several phenomena observed in human cognition. They account for why a composition can fail despite knowing its premises, why similar compositions can emerge at different times, and how a single linking fact can suddenly enable many new inferences. Taken together, these findings establish a mathematical link between the statistical structure of experience and the development of compositional reasoning.

Abstract

Compositional Image Generation

Explore similar work

A Spectral Theory of Compositional Learning

A Theoretical Analysis of Provable Compositional Generalization in Neural Networks: A Necessary and Sufficient Condition

Compositionality Emerges in a Narrow Depth-Connectivity Regime: Architecture Constraints and Solution Manifolds