PaperlayerView exact revision on arXiv

Source-linked AI summary

Defining and Generating Compositional Structure

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

arXiv:2610.20922v1cs.AIcs.ITcs.LGmath.IT

TL;DR

General quantitative accounts of compositional structure remain limited, especially for arbitrary objects whose parts and modes of combination are not specified in advance. The paper defines it through structure revealed by modeling parts together, formalizes the comparison using algorithmic information theory, and generates strings and images with recognizable hierarchical reuse and part–whole organization.

  • Problem

    General quantitative accounts of compositional structure remain limited, particularly for arbitrary objects without prespecified parts or composition rules.

    Source: §1 · p. 2

  • Method

    The paper uses algorithmic information theory to compare the structure-bearing models of wholes and parts, then optimizes strings and images for desired compositional profiles.

    Source: §1 · p. 2

  • Results

    Optimizing strings and images for prescribed profiles produced recognizable nested reuse and coherent organization across scales.

    Source: §1 · p. 2, §5 · p. 14

  • Takeaways & Limitations

    The discussion connects compositional structure to depth in neural architectures and proposes scoring curricula by the structure introduced as experience builds on prior experience.

    Source: §5 · p. 14

    The ideal quantities are uncomputable, empirical scores depend on approximate methods whose robustness is unestablished, and the intrinsic decomposition remains an open problem.

    Source: §3.2 · p. 6, §5 · p. 14

Abstract

from arXiv · show

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.

1 Introduction

The introduction frames compositional structure as reused and recombined parts, while noting that general quantitative accounts remain limited. It proposes identifying structure that appears when parts are considered together and uses this idea to generate objects with recognizable organization.

1 Introduction

  • Compositionality arises when reused and recombined parts form new structures across natural and abstract domains.The introduction presents it as a source of interesting complexity in both natural and artificial systems.Source: §1 · p. 1
  • Existing quantitative accounts often rely on known semantic parts or restricted composition rules, leaving intrinsic structure in arbitrary objects an open question.The broader question is what compositional structure emerges across parts and scales, and how much is present.Source: §1 · p. 2
  • Novel compositional structure is shared structure revealed by modeling parts together that is absent from their separate models.Repeated comparisons across locations and scales produce a profile of where such structure emerges.Source: §1 · p. 2
  • Algorithmic information theory compares structure-bearing models of parts and wholes using description length and compression, without prescribing the structure in advance.The quantities describe where and how structure is composed while remaining agnostic to its particular content.Source: §1 · p. 2
  • Optimizing strings and images for desired compositional profiles yields recognizable reuse, hierarchy, and part–whole organization rather than mere randomness or repetition.The framework specifies the form of organization without prescribing particular content.Source: §1 · p. 2
  • The paper connects multiscale compositional structure to deep architectures and proposes curricula that build on prior structure as experience grows.It also discusses gathering new data that continually expands what a learner can represent.Source: §1 · p. 2

2 Intuition for compositional structure

The program example uses compression to identify compositionality: a joint library can reveal a reusable abstraction or refactoring absent from separate libraries. Comparing libraries recursively locates where structure emerges, while contrasting cases distinguish composition from reuse alone or unrelated complexity.

2 Intuition for compositional structure

  • A program's reusable structure can be represented by a library of functions, classes, and data structures chosen to shorten its complete description.A varied repertoire reused and recombined into higher-level components is more compositional than either a tiny library or unrelated local functions.Source: §2 · pp. 2–3
  • Compression provides a reference point for comparing libraries, since the optimal library accounts for both its own description and the code expressed through it.The comparison tracks how that library changes as increasingly large parts of the program are considered together.Source: §2 · p. 3
  • Joining fragments can make a shared code block worth extracting as a function, or enable one routine to be refactored in terms of another.The joint library then contains a structural account of their interaction that neither part-library required on its own.Source: §2 · p. 3
  • More uses of an existing library add no new abstraction, while unrelated programs merely place independent contents side by side.Compositional structure instead requires a joint library that cannot be obtained merely by selecting or merging the part-libraries.Source: §2 · p. 3
  • Recursive comparisons locate where library structure grows or is reorganized across program segments and scales.Each join captures only the additional structure introduced by combining those parts; structure within a smaller segment is attributed to its earlier joins.Source: §2 · p. 3
  • For arbitrary objects, models play the role of program libraries: the question is whether the whole's best model contains structural information unrecoverable from the part-models.The raw whole adds no information beyond concatenating its parts; combining them can instead change the best account of their structure.Source: §2 · p. 3

3 Defining compositional structure

This section defines compositional structure as novel structure in a whole that is not recoverable from models of its parts, formalizing it with algorithmic information theory and two-part coding. It applies the measure recursively across decompositions to describe structure at multiple scales and discusses symbiogenesis as a plausible mechanism for its emergence, without requiring parts or wholes to be self-encoding.

3.1 Preliminaries: algorithmic information theory

  • Kolmogorov complexity measures shortest-program description length but entangles meaningful structure with irreducible randomness, motivating two-part MDL codes that separate a model’s structural information from residual data.The Occam’s razor model is the minimum-description-length model with minimal Kolmogorov complexity within the model class; its model cost captures exploitable structure and its residual cost captures unstructured information.Source: §3.1 · pp. 4–5

3.2 Formal definition

  • Novel compositional structure is the additional description length of a whole’s model given the models of its parts, capturing structure revealed only by considering the parts jointly.The quantity is near zero when the whole’s structure is recoverable from the parts’ models, and the measure for one decomposition does not capture structure already present within the parts.Source: §3.2 · p. 5
  • Recursively measuring novel structure at each node of a chosen decomposition tree produces a profile showing where and at what scales structure emerges.The profile distinguishes negligible novelty, novelty limited to a characteristic scale, structure across nested scales, and continually accumulating structure; its interpretation depends on the chosen tree, whose intrinsic form remains an open problem.Source: §3.2 · pp. 6–7

3.3 Approximating compositional structure

  • Exact evaluation is infeasible because Kolmogorov complexity is uncomputable and searching for an optimal model may require an uncertifiable search over infinitely many models.Empirical coding and search schemes approximate description lengths and model selection, while a conditional coding scheme measures the added cost of describing the whole’s fitted model from the parts’ models; the resulting estimate depends on the coding strategy.Source: §3.3 · p. 7

3.4 Relationship to other measures of compositionality

  • Unlike algorithmic mutual information, which can reflect either shared existing structure or novel joint structure, the proposed measure isolates only the latter (Agüera y Arcas, 2025; Schmidhuber, 1997).It therefore separates newly emerging structure from the accumulation of more data that already share a structure.Source: §3.4 · p. 7
  • The measure is an algorithmic analogue of synergistic information, but unlike partial information decomposition it directly measures a whole’s structural model and avoids choosing among non-unique information allocations.PID concerns sources and a target; with the whole as target, its synergy is zero and cannot detect structure emerging from combining the sources.Source: §3.4 · pp. 7–8
  • Kolmogorov’s structure-function account characterizes emergent explanations across model-complexity budgets, whereas this definition identifies novel structure at particular composition steps.Changes in model complexity need not correspond to progressively larger collections of parts.Source: §3.4 · p. 8
  • The definition complements syntax-based compositionality and assembly theory by quantifying intrinsic structure from arbitrary data without requiring specified composition rules, a physical construction space, or observed copies.A grammar or program can itself be the model, making the measure akin to the cost of a reusable abstraction revealed by combining parts; assembly theory instead describes construction paths and reuse.Source: §3.4 · pp. 8–9
  • Agüera y Arcas (2025) describes symbiogenesis as smaller replicators combining into larger replicators, while C(xa, xb →x) measures novel joint structure without requiring self-encoding.The account treats symbiogenesis as a plausible mechanism for the structure measured by C(xa, xb →x).Source: §3.4 · p. 9

4 Generating compositional structure

The section turns a desired multi-scale compositional profile into an optimization reward and searches for strings and images that exhibit it. Compared with structure-only optimization, the resulting objects show more hierarchical reuse and more unified organization.

4 Generating compositional structure

  • The inverse framework defines a reward from a decomposition tree, coding schemes, and a scalar functional, then searches a domain for objects with the desired profile.The experiments use symbolic strings and images as their search domains.Source: §4 · p. 9

4.1 Compositional strings

  • For strings, a balanced binary decomposition scores conditional grammar costs at five scales, with a power mean that places extra pressure on weaker scales.The coding comparison aligns part grammars with the combined grammar, so reused rules cost less than newly useful rules.Source: §4.1 · pp. 10–11
  • Compositionality-optimized strings produce deeper grammars than structure-optimized strings, despite the latter having more rules and longer rule expansions.The comparison distinguishes hierarchical reuse from structural complexity alone.Source: Figure 2 · p. 10, §4.1 · p. 11
  • String dot plots show denser repeated patterns and sub-patterns under compositionality optimization, whereas structure-only repeats tend to be longer, sparser, and less hierarchical.The dot plots encode repeated substrings as off-diagonal lines and nested repeats as shorter lines within the same block.Source: Figure 2 · p. 10, §4.1 · p. 11

4.2 Compositional images

  • For images, coordinate-based CPPNs generate quantized 64 × 64 three-channel images, and the search targets spatial structure recognizable by the chosen coding scheme.The authors explicitly limit the claim to forms of image structure that this coding scheme can recognize.Source: §4.2 · pp. 11, 13
  • Image patch models use held-out pixels for early stopping and are retained only if they outperform a constant marginal-intensity model.The fallback is intended to prevent assigning spurious spatial structure to patches better described without spatial dependence.Source: §4.2 · p. 12
  • Compositionality-optimized CPPNs have more distinct input-to-output paths and greater feature reuse, despite comparable network size and depth.These statistics suggest more interconnected feature recombination under the compositionality reward.Source: Figure 3 · p. 12, §4.2 · p. 13
  • Compositionality-optimized images look more unified, while structure-optimized images are more disjoint, often packing independent color bands.The authors note that visual evidence for feature hierarchies is difficult to establish objectively.Source: Figure 3 · p. 12, §4.2 · pp. 13–14

5 Discussion

The discussion connects the definition of compositionality to deep architectures, curricula, and agents selecting their own experience. It also identifies approximation robustness and the choice of decomposition as open questions.

5 Discussion

  • Optimizing strings and images for prescribed compositionality profiles produced recognizable nested reuse and coherent organization across scales, rather than merely complexity, regularity, or shared information.The objective constrains organizational form while remaining agnostic to particular content.Source: §5 · p. 14

The success of deep learning

  • Deep architectures fit the proposed inductive bias because later layers can combine and reorganize earlier features into larger-scale structure.For streams whose structure grows across temporal scales, the framework motivates architectures with expandable effective depth or hierarchy.Source: §5 · p. 14

Curricula and open-ended learning

  • Curricula could be scored by the compositional structure introduced at each step, testing whether high-scoring orderings yield more reusable and factorized representations.The discussion relates this hypothesis to Kumar et al. (2025), where human-guided open-ended evolution produced more unified and factorized representations than endpoint-only training.Source: §5 · p. 14
  • An agent could select new experience to maximize its empirical compositionality with the learner’s history, favoring novelty useful through its relation to prior experience.The discussion distinguishes this objective from novelty or learnability alone.Source: §5 · p. 14

Future work and limitations

  • The ideal quantities are uncomputable, and empirical scores rely on restricted model classes, imperfect MDL search, and conditional-code surrogates.The experiments do not establish score stability across compressors or optimization procedures.Source: §5 · p. 14
  • Profiles depend on the chosen decomposition tree, so identifying useful, robust decompositions rather than artifact-producing ones remains open.The framework makes decomposition choice explicit as an object of study, and maximizing summed compositionality is proposed only as a candidate for a canonical tree.Source: §5 · pp. 14–15

Appendix A Practical approximation of compositional structure

The appendix replaces uncomputable algorithmic-information quantities with empirical coding procedures. The resulting compositionality score is an operational, procedure-dependent estimate, not a formal bound.

Practical approximation of compositional structure

  • The ideal quantities require uncomputable model and conditional complexities, plus searching a potentially infinite model class for the shortest two-part description.Practical approximations instead use empirical compressors, model classes, learning algorithms, and MDL procedures.Source: Appendix A · p. 17
  • Finite search yields a best-so-far model without a computable certificate of optimality; continued search can reveal better models and shorter descriptions.The practical search replaces open-ended theoretical search with a specified model class, optimization method, and finite budget.Source: Appendix A · p. 17
  • The empirical procedure uses a two-part MDL scheme to fit models, with the ideal empirical model minimizing total code length and, among ties, model-code length.The definition of an ideal empirical Occam’s razor model assumes a unique model with minimal model-code length among the total-code minimizers.Source: Appendix A · p. 17
  • The empirical estimate measures the additional conditional code length for describing the whole’s fitted model given the parts’ fitted models, under a chosen coding strategy.It is an operational notion relative to procedures for fitting models and conditionally coding the whole-model, not a formal upper or lower bound.Source: Appendix A · p. 18

Appendix B The maximal decomposition

The appendix motivates maximal decompositions as a way to capture intrinsic compositional structure, while contrasting them with minimal decompositions that can collapse to trivial solutions. It also discusses unresolved validation questions and properties of the maximizing tree.

Appendix B The maximal decomposition

  • The authors conjecture that maximizing the sum of novel compositional structure across a tree is a promising way to select an intrinsic decomposition.The appendix introduces initial arguments motivating this conjecture.Source: Appendix B · p. 18
  • A maximal decomposition preferentially joins objects sharing novel structure and parts, whereas minimal decompositions can merge every bit in one join and yield a trivial score.The minimal-tree solution is independent of the string and therefore cannot capture its intrinsic compositional structure.Source: Appendix B · p. 18
  • The maximal score is lower-bounded by sophistication, but whether it separates intuitively compositional from uncompositional objects remains to be established theoretically and empirically.Strings exist for which the maximal score exceeds sophistication, so it measures something different.Source: Appendix B · p. 18
  • A maximizing decomposition is recursively consistent: each substring appearing as a node has a subtree that maximizes the decomposition score for that substring.This supports treating compositionality as an intrinsic rather than context-dependent property.Source: Appendix B · p. 18
  • In maximal decompositions, novel structure from joining three substrings is no greater than that from two successive binary joins, resolving the choice of joining arity.Minimal decompositions instead admit a trivial solution that merges every bit in one join.Source: Appendix B · p. 18

C.1 Proof of the relationship between compositionality and algorithmic mutual information

This section establishes a conditional relationship between novel compositional structure and algorithmic mutual information. The implication holds under a no-tie assumption, but the reverse implication does not hold in general.

C.1 Proof of the relationship between compositionality and algorithmic mutual information

  • Under the no-tie assumption, positive novel compositional structure implies that the whole’s two-part description length differs from the separate descriptions of its parts.The theorem explains that joint-only structure generally makes the whole more compressible, implying positive algorithmic mutual information.Source: §C.1 · p. 19
  • The theorem is an idealized description-length argument, not a literal prefix Kolmogorov-complexity theorem without further qualifications.Suppressed coding overheads and decomposition-boundary side information can alter strict tests; rigorous variants need thresholds exceeding relevant overheads.Source: §C.1 · p. 19
  • The proof starts from the fact that the whole can always be described by concatenating separate model descriptions and residual codes, then uses the no-tie condition to make the bound strict.The whole’s optimal model gives a description length no greater than that separate encoding.Source: §C.1 · p. 19
  • Positive algorithmic mutual information does not imply novel compositional structure, because parts can share structure already present in them.The reverse implication does not hold in general.Source: §C.1 · p. 19

C.2 Proofs of the relationships between ST (x) and K(mx)

The section proves bounds linking total compositionality to model complexity and describes consequences for maximal and minimal decomposition trees. The results distinguish fully refined maximizing trees from trivial minimizing solutions.

C.2 Proofs of the relationships between ST (x) and K(mx)

  • The appendix summarizes that maximal trees can be refined to single-bit leaves, while complete and unrestricted minimal decompositions admit distinct trivial solutions.The unrestricted root-only tree has score zero because its score is an empty sum and decomposition scores are nonnegative.Source: §C.2 · pp. 20–21
  • Model complexity bounds total compositionality: for complete decompositions, the minimum score is bounded below by K(mx) − O(n) and above by K(mx | n) + O(1).The stated idealized equality suppresses leaf-description and accumulated coding terms.Source: §C.2 · pp. 20–21
  • The proof encodes a decomposition by its tree shape and leaf models, then describes each internal-node model conditionally on its children to bound the root model’s complexity.The node programs are processed in postorder so child models are available when reconstructing each parent.Source: §C.2 · p. 20
  • There exists a maximizing decomposition whose leaves are individual bits, and maximal compositionality lower-bounds model complexity under the fixed-empty-model assumption.The lower bound suppresses an additive O(log(n + 2)) term.Source: §C.2 · p. 20
  • For complete minimal decompositions with fixed empty models for individual bits, a single-join tree provides a trivial minimizer.The section also states that unrestricted minimal decompositions have a zero-score root-only minimizer.Source: §C.2 · p. 21

C.3 Recursive consistency of maximal decompositions

The theorem establishes recursive consistency for maximizing decompositions: every subtree rooted at a node of a maximizing tree also maximizes the score for its substring. Replacing it with another maximizing decomposition preserves maximality of the full tree.

C.3 Recursive consistency of maximal decompositions

  • Every subtree of a maximizing decomposition maximizes the score for the substring at its root, and replacing it with another maximizing subtree preserves maximality of the full decomposition.The result assumes a fixed universal machine, tuple encoding, and uniquely selected Occam’s razor model for each nonempty substring.Source: §C.3 · p. 22
  • Replacing a subtree leaves all scores outside it unchanged because the surrounding nodes retain their substrings and immediate child substrings.This invariance underlies the proof that a maximizing full tree must contain a maximizing subtree.Source: §C.3 · p. 22

C.4 Binary refinement of maximal decompositions

Theorem 4 shows that any admissible decomposition tree can be refined into a binary tree with the same ordered leaves. Under the paper’s convention of suppressing accumulated additive coding terms, a maximizing decomposition can be chosen to be entirely binary.

C.4 Binary refinement of maximal decompositions

  • Under suppressed additive coding terms, a maximizing decomposition can be chosen to consist entirely of binary joins.Theorem 4 establishes a binary refinement for every admissible tree; its score decreases by at most a constant per nonbinary join, with the constant independent of the tree and string.Source: §C.4 · pp. 22–23
  • A decoder reconstructs the whole model from the part models by successively running programs that describe each intermediate join.Prefix-freeness lets the decoder parse the concatenated programs without extra delimiters, and the additive simulation constant does not depend on the number of children.Source: §C.4 · p. 22
  • Each join with more than two children can be replaced by a left-associated binary chain while preserving the original child subtrees and ordered leaves.The refinement incurs at most a fixed additive cost per replaced join.Source: §C.4 · pp. 22–23

D.1 Compositional strings

The string experiments use grammar induction and conditional grammar compression to approximate structure in parts and wholes. The appendix details how candidate repeats are found, scored, aligned, and used in the compositionality reward.

D.1 Compositional strings

  • The grammar code pools rule symbols, rule names, and residual symbols to estimate their shared symbol costs, but its lengths are surrogate codelengths, not calibrated file lengths.Adding a rule changes both stream length and symbol codelengths, so the full two-part code is evaluated.Source: §D.1 · p. 23
  • The fitter adds a grammar rule only when its exact minimum-description-length gain is positive, rather than accepting every repeated pattern.Accepted steps therefore strictly shorten the surrogate two-part code.Source: §D.1 · pp. 23–24
  • A global suffix-array search supplements pair extension because unrelated occurrences can stop local extension even when a valuable repeated subset exists.Longest-common-prefix intervals propose shared patterns, ranked by h(r −1); candidates are then checked for non-overlapping occurrences and evaluated using the same exact gain.Source: §D.1 · p. 24
  • Conditional compression aligns part-grammar rules with the combined grammar, then charges for writing, modifying, or reusing each aligned rule.Small grammars use exhaustive relabelling; larger ones use 64-dimensional descriptors and Hungarian assignment, while final costs are computed from symbolic differences.Source: §D.1 · pp. 25–26
  • The conditional score is an operational approximation: it does not transmit inferred alignments, encode rule boundaries, or calibrate a fixed per-symbol cost.These choices focus the score on structural differences between grammars.Source: §D.1 · p. 27
  • The string reward aggregates normalized conditional costs across joins at multiple scales, using a p = 0.75 power mean.The experiment evolves 10,000 strings over a vocabulary of eight symbols, with 5,000 offspring per generation and elite retention of 10,000.Source: §D.1 · p. 27
  • The appendix reports top-reward strings for all 10 seeds after optimizing both compositionality and structure rewards.It refers readers to the main text for dot-plot generation and interpretation.Source: §D.1 · p. 27

D.2 Compositional images

The image experiments approximate structure with coordinate-based probabilistic models and compare parent-patch models with models of their quadrants. An evolutionary search then optimizes CPPNs using a reward aggregated across image scales.

D.2 Compositional images

  • Each image patch is modeled by a coordinate network that predicts categorical channel distributions, while a coordinate-independent baseline captures channel frequencies without spatial relationships.The network is retained only when its validation loss beats the constant baseline by at least 0.02 bits per symbol and 2%.Source: §D.2 · pp. 27–28
  • The model-description term estimates learnable structure from excess training loss over the selected checkpoint’s loss, integrated across processed coordinates.This learning-curve proxy is a surrogate, not the actual codelength of final weights; validation selection and residual likelihood complement it to avoid crediting noise memorization.Source: §D.2 · p. 29
  • At each quadtree join, the method tests whether a parent model can be reproduced by routing among quadrant models or requires functional adaptation.The parent teaches the copied child models; adaptation is kept only if validation divergence improves by the stated margins, and the conditional score includes remaining divergence.Source: §D.2 · pp. 29–30
  • Image fitness aggregates normalized conditional complexity across joins at widths 16, 32, and 64, giving the three scales equal overall status.A power mean is more sensitive than an arithmetic mean to weaker scales.Source: §D.2 · p. 30
  • The coordinate networks used to score images are distinct from evolved CPPNs, which map full-image coordinates to the three output intensities.The CPPNs are evolved with feed-forward NEAT, using settings close to those used in Picbreeder.Source: §D.2 · p. 30
  • The appendix provides additional generated images for both compositionality and structure rewards, and records CPPN structural statistics across the evolving population.The caption says each statistic is summarized by its mean and maximum, but these passages do not report the values.Source: §D.2 · p. 31, Table D.2 · p. 32

Related papers

Loading 2610.20922v1…