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(xa,xb→x):=K(mx∣mxa,mxb) (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(mx) ). 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(mx) ). 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
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.
log10(1+#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 studies how to combine objects, attributes, spatial relations, and visual references into coherent, controllable images.
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.
Compositional generalization\unicodex2013the ability to systematically process novel combinations of known components\unicodex2013is a hallmark of human intelligence; however, its theoretical foundation in neural networks is not yet well understood. This paper establishes a necessary and sufficient condition for provable compositional generalization, precisely characterizing its boundary. Conceptually, the condition consists of two principles: (i) structural alignment, where a model's computational graph aligns with a task's true compositional hierarchy, and (ii) unambiguous minimized representations, where each component encodes adequate but not redundant information on the training data. The result is fully proved and machine-verified in Lean 4 and holds even in few-shot and one-shot regimes. The necessity direction establishes that provable compositional generalization cannot circumvent these requirements, while the sufficiency direction yields a unified inductive bias that jointly governs architectural design, training data properties, and regularization strategies. Building on this condition, we develop an example algorithmic approach, illustrate it through a controlled minimal example, and further demonstrate the condition on the SCAN jump task. All conclusions are derived mathematically without reliance on empirical validation. Our work provides a theoretical characterization of provable compositional generalization.
Compositionality is believed to be the foundation for generalization, enabling models to reuse meaningful primitives in novel combinations. Yet, models trained with standard gradient-based optimization rarely, and often only weakly, exhibit compositional internal structure, and it remains unclear how or why such compositionality forms. In this work, we show that compositionality emerges in a narrow connectivity-depth sweet spot. Along the connectivity axis, compositionality only appears in some specifically sparse networks, heavily depends on which connections remain rather than on weights' sparsity alone. Along the depth axis, compositionality emerges within a narrow, target-dependent regime, peaking at specific depths, while both shallower and deeper networks fail. When either the depth or connectivity condition is violated, gradient descent silently converges to fractured solutions rather than compositional ones. To discover and exploit this emergence, we introduce (i) similarity-based pruning (SP) to recover compositional connectivity and (ii) a heuristic depth predictor to estimate where compositionality is most likely to appear. Finally, we support these empirical findings with a theoretical framework based on compositional sparsity, volume-ratio arguments, and feature-interference bounds, explaining why compositional solutions are reachable only in a narrow depth-connectivity regime.
Dat H. Do, Rushi Shah, Duc V. Le +1
National University of Singapore1 · University of Twente2