组合结构的定义与生成

# Defining and Generating Compositional Structure
Source: [https://arxiv.org/html/2610.20922](https://arxiv.org/html/2610.20922)
## Defining and Generating Compositional StructureThanks:Correspondence to:eric\.elmoznino@gmail\.com Code is provided at[https://github\.com/EricElmoznino/defining\_and\_generating\_compositional\_structure](https://github.com/EricElmoznino/defining_and_generating_compositional_structure)

Tejas KasettyAffiliation:Mila – Quebec AI InstituteAffiliation:Université de MontréalBlaise Agüera y ArcasAffiliation:Google Paradigms of Intelligence TeamYoshua BengioAffiliation:Mila – Quebec AI InstituteAffiliation:Université de MontréalAffiliation:LawZeroGuillaume LajoieAffiliation:Mila – Quebec AI InstituteAffiliation:Université de MontréalAffiliation:Google Paradigms of Intelligence Team

###### 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\.

*Keywords*compositionality, complexity, structure, compression, machine learning

## 1Introduction

“Each portion of matter can be conceived as a garden full of plants, and as a pond full of fish\. But each branch of the plant, each member of the animal, each drop of its humors, is also such a garden or such a pond\.” — Gottfried Wilhelm Leibniz,\([Leibniz, 1898](https://arxiv.org/html/2610.20922#bib.bib1)\)

Compositional structure is everywhere, and at every scale\. Atoms combine into molecules, molecules into cells, cells into organs, and organs into organisms\. Each of these levels in turn contains further rich hierarchies; cells and organs, too, are intricately organized assemblies of interacting parts\. Compositionality applies to more abstract spaces as well: music develops motifs into phrases and movements; programs build modules from modules and functions from functions; concepts are built from other concepts; technologies are built from more granular technologies\([Arthur, 2009](https://arxiv.org/html/2610.20922#bib.bib2)\); scientific theories inherit and reorganize earlier ideas; and a well\-designed curriculum continually recombines prior knowledge into more sophisticated skills\. Across all these examples, complexity does not arise from an undifferentiated collection of elements, but from parts being reused and recombined into new structures\. In this broad sense, compositionality is a signature of both life and intelligence, and arguably one of the principal sources of interesting complexity in the universe\([Agüera y Arcas, 2025](https://arxiv.org/html/2610.20922#bib.bib3)\)\.

Despite how readily we recognize such examples, it remains difficult to say precisely what makes them compositional\. Familiar descriptions — that the whole is more than the sum of its parts, or that the meaning of a complex expression depends on its structure and the meanings of its constituents — are suggestive but do not by themselves provide a general quantitative measure\([Pagin and Westerståhl, 2010](https://arxiv.org/html/2610.20922#bib.bib27)\)\. More formal approaches in machine learning typically begin with a prescribed set of semantic constituents and a rule for reconstructing the whole from them\. Some define these constituents using known generative factors or object slots\([Wiedemer et al\., 2023](https://arxiv.org/html/2610.20922#bib.bib7);[Wiedemer et al\., 2024](https://arxiv.org/html/2610.20922#bib.bib8)\), while others restrict their combination to a particular operation, such as a linear map or a prescribed hierarchy\([Trager et al\., 2023](https://arxiv.org/html/2610.20922#bib.bib6);[Andreas, 2019](https://arxiv.org/html/2610.20922#bib.bib5)\)\. These approaches are useful when the parts and their modes of combination are already known, but they make compositionality relative to externally supplied semantics or a restricted form of composition\([Elmoznino et al\., 2024](https://arxiv.org/html/2610.20922#bib.bib4)\)\. They therefore do not fully answer the broader question: for an arbitrary object, what intrinsic compositional structure emerges across its parts, how much of it is present, and how is it organized across scales?

Our starting point is that compositional structure emerges when parts, considered together, reveal shared structure that is not captured when those parts are modeled separately\. Here, a model represents the structure in an object: the regularities and patterns that provide a shorter explanation of the data\. If the model of the whole contains something genuinely new beyond the models of the parts, then those parts share some pattern or organization that becomes apparent only through their combination\. This is what we call*novel compositional structure*\. A cell viewed in isolation reveals its internal organization; a collection of cells viewed together may additionally reveal a tissue, with spatial arrangements and collective mechanisms absent from any one cell\. The same principle can be applied recursively: tissues form organs, motifs form phrases, and functions form higher\-level functions\. Repeating the comparison at different locations and scales produces a profile of where an object’s compositional structure emerges\.[Section2](https://arxiv.org/html/2610.20922#S2)develops this idea and tests it against several intuitive cases\.

To make this precise, we use algorithmic information theory: a mathematics of information expressed through description length and compression\. The shortest two\-part description of an object separates a model, which captures its compressible structure, from the residual information needed to specify the object given that model\. We compare these structure\-bearing models across parts and wholes, measuring how much additional information is needed to describe the model of the whole from the models of its parts\. This lets us speak rigorously about parts, structure, and novelty without specifying in advance what the structure must be\. The distinction is between*form*and*content*: our quantities describe where and how structure is composed while remaining agnostic to the particular structures or patterns involved\.[Section3](https://arxiv.org/html/2610.20922#S3)formalizes the definition, extends it to multiscale compositional structure profiles, and develops tractable approximations\.

A quantitative definition also lets us look at the problem in reverse: instead of measuring the compositional structure of a given object, we can specify a desired profile and search for objects that exhibit it\. We demonstrate this in[Section4](https://arxiv.org/html/2610.20922#S4)by optimizing directly over strings and images\. Without prescribing their particular content, the objective produces strings with nested patterns and images with coherent, hierarchical visual organization reminiscent of abstract art\. These experiments serve both as a method for generating structured data and as a concrete test of the definition\. The generated objects display recognizable reuse, hierarchy, and part–whole organization rather than mere randomness or repetition\.

Finally, we consider what this perspective suggests for machine learning\. Natural data often builds structure on top of structure across many scales, matching the inductive bias of deep architectures whose successive layers build increasingly abstract features from earlier ones\. Compositional structure can also grow through time: new data may reuse, extend, or reorganize what came before\. This suggests principles not only for choosing architectures, but for ordering experience into curricula in which each stage builds maximally on prior structure, and for gathering new data that continually expands what a learner can represent\. We close by developing these connections between depth, curricula, and open\-ended learning to our definition of compositional structure in[Section5](https://arxiv.org/html/2610.20922#S5)\.

## 2Intuition for compositional structure

Before introducing the formal machinery, we build intuition through a running concrete example based on computer programs\. We use computer programs because they are familiar and paradigmatic compositional objects: programmers explicitly define reusable parts and combine them to construct more complex ones, making the relevant structure unusually easy to see\. A self\-contained program can be separated conceptually into a*library*of reusable functions, classes, and data structures, and the remaining code written using that library\. When the library is designed to make the complete program as short as possible, it captures the program’s reusable structure\. A richly compositional program should then have a modular library containing a varied repertoire of components that are reused throughout the program and recombined to define higher\-level components\. A library with very few distinct components provides little material to compose\. Conversely, a large collection of functions used only within separate portions of the code is better understood as several unrelated programs placed beside one another; size alone does not make a library compositional\.

The same program can be organized around many different libraries, so inspecting an arbitrary implementation would make this intuition depend on choices made by its programmer\. Compression provides a less arbitrary reference point: consider the library that yields the shortest overall description after accounting for both the library and the code expressed through it\. Our strategy is to track how this optimal library changes as increasingly large parts of the program are considered together\. If two snippets contain related logic, their joint description may justify a reusable abstraction that was not economical for either snippet alone\. Compositionality then depends on whether the library of the whole contains something genuinely new: not new raw code, since the relevant code already occurred in the parts, but a new*structural description*of what those parts share\.

More concretely, letxax\_\{a\}andxbx\_\{b\}denote two program fragments and letx=\[xa,xb\]x=\[x\_\{a\},x\_\{b\}\]denote their combination, with each expressed directly as code without factoring reusable pieces into a library\. Writemxam\_\{x\_\{a\}\},mxbm\_\{x\_\{b\}\}, andmxm\_\{x\}for the optimal libraries that compress the corresponding fragments or whole\. Suppose the same block of code occurs once in each fragment and is long enough that extracting it into a function becomes worthwhile only after the fragments are joined\. The function need not appear inmxam\_\{x\_\{a\}\}ormxbm\_\{x\_\{b\}\}, since defining it for a single use would not shorten either fragment individually\. For the whole, however, extracting the shared block into a function can shorten the total program\. The librarymxm\_\{x\}has grown because a common part becomes reusable structure only at the level of the whole\. The same phenomenon can involve refactoring rather than simply adding a function\. For example, one fragment may justify a matrix\-multiplication routine while another justifies a vector\-norm routine; considered together, the shortest library may redefine the norm in terms of the existing multiplication routine\. In both cases, combining the fragments changes how their structure is optimally represented and reveals a novel interaction between them\.

Two contrasting cases clarify why this is more specific than either reuse or structural complexity alone\. First,xbx\_\{b\}might simply provide more uses of a library that was already optimal forxax\_\{a\}\. The whole is then compressed using the same library as the parts: there is shared structure and a compression benefit, but no new abstraction or refactoring is required\. Second,xax\_\{a\}andxbx\_\{b\}might be entirely unrelated programs\. The optimal library of the whole may be larger than either part\-library, but only because it places their independent contents side by side\. Givenmxam\_\{x\_\{a\}\}andmxbm\_\{x\_\{b\}\}, constructingmxm\_\{x\}requires essentially nothing novel\. Both of these cases differ from the compositional one: in the first, all the structure needed to compress both parts is already encoded in one of their libraries; in the second, there is no shared structure to exploit\. Compositional structure lies in a different space, where the best joint library cannot be obtained merely by selecting or merging the libraries of the parts\.

This comparison can be applied recursively\. A program may reveal one abstraction when short fragments are joined, another when larger segments of code are combined, and still others when those segments form the complete program\. Recording where the optimal library grows or is reorganized therefore describes not just whether the program is compositional, but where its compositional structure emerges across locations and scales\. The comparison at each join is local: it asks what additional library structure emerges when those particular parts are combined\. Structure already captured within a smaller segment is therefore attributed to the earlier joins inside that segment, while later joins capture only the further structure introduced by combining it with other segments\.

Programs and libraries provide a concrete example of a more general idea\. For an arbitrary object, a*model*plays the role of the library: it captures regularities that allow the object to be described more concisely, while the remaining description specifies details not captured by the model\. The object may represent music, an image, aniiddataset, or a nonstationary data stream\. In every case, we ask the same question of a chosen division into parts: does the best model of the whole contain structural information that cannot be recovered from the best models of the parts? The next section makes “best model” and “cannot be recovered” precise using algorithmic information theory\. Importantly, the claim is not that the raw whole contains information absent from its parts: by construction, it is simply their concatenation\. Rather, combining the parts can change the best account of their structure\. It is in this precise sense that the description of a compositional whole is more than the sum of the descriptions of its parts\.

The preceding intuition suggests that compositional structure can be identified by comparing the structure\-bearing descriptions of parts and wholes\. We now make this idea precise using algorithmic information theory\. We first use optimal two\-part codes\([Grünwald, 2007](https://arxiv.org/html/2610.20922#bib.bib19)\)to define the model that captures an object’s compressible structure; we then measure the novel structure that emerges at a composition step, apply this comparison recursively to obtain multiscale compositional structure profiles, and describe how the resulting quantities can be approximated in practice\.

### 3\.1Preliminaries: algorithmic information theory

#### Kolmogorov complexity\.

Kolmogorov complexity\([Li et al\., 2008](https://arxiv.org/html/2610.20922#bib.bib10);[Kolmogorov, 1965](https://arxiv.org/html/2610.20922#bib.bib9);[Fortnow, 2000](https://arxiv.org/html/2610.20922#bib.bib11)\)is a notion of information quantity that serves as the foundations for algorithmic information theory\. Intuitively, the Kolmogorov complexity of an objectxx, denotedK⁡\(x\)K\(x\), is the length of the shortest program \(in some programming language\) that outputsxx\. A related notion is the conditional Kolmogorov complexity ofxxgiven another objectyy, denotedK⁡\(x∣y\)K\(x\\mid y\), which is the length of the shortest program that takesyyas input and outputsxx\. Kolmogorov complexity has many intuitive properties as a measure of information quantity that generalize equivalent properties from Shannon information theory\([Grünwald and Vitányi, 2003](https://arxiv.org/html/2610.20922#bib.bib12)\), and is deeply rooted in the idea of*compression*\.

Formally, throughout this paperKKdenotes*prefix*Kolmogorov complexity relative to a fixed universal prefix Turing machineUU\. A prefix Turing machine is one in which valid programs are self\-delimiting; they are commonly\-used in algorithmic information theory for technical convenience\. For a finite stringxx,K⁡\(x\)K\(x\)is the lengthl⁡\(r\)l\(r\)\(in bits\) of the*shortest*binary programrrthat printsxxand halts:

K\(x\)=minr\{l\(r\):U\(r\)=x,r∈\{0,1\}∗\},\\displaystyle K\(x\)=\\min\_\{r\}\\\{l\(r\):U\(r\)=x,r\\in\\\{0,1\\\}^\{\*\}\\\},\(1\)and given a separate stringyy, the conditional Kolmogorov complexityK⁡\(x∣y\)K\(x\\mid y\)is defined analogously as:

K\(x∣y\)=minr\{l\(r\):U\(r,y\)=x,r∈\{0,1\}∗\}\.\\displaystyle K\(x\\mid y\)=\\min\_\{r\}\\\{l\(r\):U\(r,y\)=x,r\\in\\\{0,1\\\}^\{\*\}\\\}\.\(2\)For tuples, let⟨x,y⟩\\langle x,y\\rangledenote a fixed computable self\-delimiting encoding ofxxandyy, and useK⁡\(x,y\)K\(x,y\)as shorthand forK⁡\(⟨x,y⟩\)K\(\\langle x,y\\rangle\); conditioning on several objects is interpreted similarly\. The particular choices of universal machine and tuple encoding affect these quantities by at most an additive constant independent of the objects\. In general,K⁡\(⋅\)K\(\\cdot\)is incomputable\. However, the quantity can still be useful and approximated\.

Note 1\. Suppression of lower\-order termsKolmogorov\-complexity relationships generally hold only up to small additive terms\. Changing the universal machine or a fixed encoding contributes an𝒪⁡\(1\)\\mathcal\{O\}\(1\)constant, while recording lengths, boundaries, or other auxiliary information can contribute𝒪⁡\(log⁡n\)\\mathcal\{O\}\(\\log n\)bits for objects of lengthnn\. Throughout the paper, we suppress these terms and write the corresponding equalities and inequalities directly\. This convention keeps the description\-length arguments transparent without changing their qualitative content\. Accordingly, statements involving zeros, strict inequalities, or exact ties should be understood up to these suppressed terms: the relevant differences are assumed to be large enough that coding overheads cannot change the comparison\.

#### Structure and Occam’s razor\.

Although Kolmogorov complexity provides a canonical notion of information quantity, it does not separate structural complexity from randomness\. A regular string has low complexity because it can be generated by a short program, whereas a random string has high complexity because no substantially shorter description exists than the string itself\. However, the latter form of complexity does not reflect elaborate internal organization; it reflects the absence of compressible structure\. In this sense,K⁡\(x\)K\(x\)entangles two distinct contributions to description length: one arising from meaningful structure, and one arising from irreducible randomness\. This motivates finer notions that aim to measure structure rather than mere incompressibility\.

This distinction between structural and random information was important to Kolmogorov himself, who quantified it through a new metric\([Kolmogorov, 1973](https://arxiv.org/html/2610.20922#bib.bib13)\)that was later generalized under various formulations and termed*sophistication*or*meaningful information*\([Grünwald et al\., 2008](https://arxiv.org/html/2610.20922#bib.bib14);[Gács et al\., 2001](https://arxiv.org/html/2610.20922#bib.bib15);[Vitányi, 2006](https://arxiv.org/html/2610.20922#bib.bib16);[Koppel and Atlan, 1989](https://arxiv.org/html/2610.20922#bib.bib18)\)\. Intuitively, measuring structural information involves compressing an object using two\-part coding schemes that follow the minimum description length \(MDL\) principle\([Grünwald, 2007](https://arxiv.org/html/2610.20922#bib.bib19)\)and Occam’s razor\.

Letℳ\\mathcal\{M\}be a model class, and denote the two\-part code length ofxxunder a modelm∈ℳm\\in\\mathcal\{M\}as:

Lm​\(x\)=K⁡\(m\)\+lm​\(x\),\\displaystyle L\_\{m\}\(x\)=K\(m\)\+l\_\{m\}\(x\),\(3\)wherelm​\(x\)l\_\{m\}\(x\)is the model\-to\-data code length \(i\.e\., the cost of describing the data given the model\)\. The form oflm​\(x\)l\_\{m\}\(x\)depends on the model class under consideration\. For instance, in the case of computable probability distributions,lm​\(x\)=−log2⁡m⁡\(x\)l\_\{m\}\(x\)=\-\\log\_\{2\}m\(x\), wherem⁡\(x\)m\(x\)is the probability mass thatmmassigns toxx\.

We define the set of minimum description length models by:

ℳ∗​\(x\):=arg​minm∈ℳ⁡Lm​\(x\)\.\\displaystyle\\mathcal\{M\}^\{\*\}\(x\):=\\argmin\_\{m\\in\\mathcal\{M\}\}L\_\{m\}\(x\)\.\(4\)
Assuming there is a unique model inℳ∗​\(x\)\\mathcal\{M\}^\{\*\}\(x\)with minimal Kolmogorov complexity, we define theOccam’s razor modelofxx, denotedmxm\_\{x\}, by:

mx:=arg​minm∈ℳ∗​\(x\)⁡K​\(m\)\.\\displaystyle m\_\{x\}:=\\argmin\_\{m\\in\\mathcal\{M\}^\{\*\}\(x\)\}K\(m\)\.\(5\)The modelmxm\_\{x\}relates to what has been called the*minimal algorithmic sufficient statistic*ofxxin prior literature\([Grünwald et al\., 2008](https://arxiv.org/html/2610.20922#bib.bib14);[Gács et al\., 2001](https://arxiv.org/html/2610.20922#bib.bib15);[Vereshchagin and Shen, 2016](https://arxiv.org/html/2610.20922#bib.bib17)\)\.K⁡\(mx\)K\(m\_\{x\}\)captures the structural information inxxthat can be exploited for compression within the model classℳ\\mathcal\{M\}, while the residual termlmx​\(x\)l\_\{m\_\{x\}\}\(x\)represents the remaining incompressible, unstructured, and random information inxxrelative to that model class\. For sufficiently expressive model classes, one hasLmx​\(x\)=K⁡\(mx\)\+lmx​\(x\)=K⁡\(x\)L\_\{m\_\{x\}\}\(x\)=K\(m\_\{x\}\)\+l\_\{m\_\{x\}\}\(x\)=K\(x\), so thatmxm\_\{x\}decomposes Kolmogorov complexity into structured and unstructured components\.

### 3\.2Formal definition

#### Novel compositional structure\.

Using the notion of an Occam’s razor model defined in[Equation5](https://arxiv.org/html/2610.20922#S3.E5), we provide our formal definition for novel compositional structure\.

Definition 1\. Novel compositional structureLetx=\[xa,xb\]x=\[x\_\{a\},x\_\{b\}\]denote a decomposition of a stringxxinto two substringsxax\_\{a\}andxbx\_\{b\}, where\[xa,xb\]\[x\_\{a\},x\_\{b\}\]denotes concatenation\. Letm⋅m\_\{\\cdot\}denote an Occam’s razor model as defined in[Equation5](https://arxiv.org/html/2610.20922#S3.E5), and assume that it is uniquely defined for each ofxx,xax\_\{a\}, andxbx\_\{b\}\. We define the amount of*novel compositional structure*inxxrelative to this decomposition as:C\(xa,xb→x\):=K\(mx∣mxa,mxb\)\.\\displaystyle C\(x\_\{a\},x\_\{b\}\\to x\):=K\(m\_\{x\}\\mid m\_\{x\_\{a\}\},m\_\{x\_\{b\}\}\)\.\(6\)

This quantity measures the additional information required to describe the model of the whole string,mxm\_\{x\}, given the models of the parts,mxam\_\{x\_\{a\}\}andmxbm\_\{x\_\{b\}\}\. In particular,C\(xa,xb→x\)≈0C\(x\_\{a\},x\_\{b\}\\to x\)\\approx 0in cases where the structure of the whole is already recoverable from the structures of the parts\. For example, this holds whenmxm\_\{x\}is identical to one ofmxam\_\{x\_\{a\}\}ormxbm\_\{x\_\{b\}\}, or whenmxm\_\{x\}is a trivial combination of the pair\(mxa,mxb\)\(m\_\{x\_\{a\}\},m\_\{x\_\{b\}\}\)with only minor overhead \(e\.g\.,mxm\_\{x\}compressesxxby usingmxam\_\{x\_\{a\}\}to compressxax\_\{a\}and usingmxbm\_\{x\_\{b\}\}to compressxbx\_\{b\}\)\.

Thus,C\(xa,xb→x\)C\(x\_\{a\},x\_\{b\}\\to x\)is intended to quantify structure present in the whole that is not recoverable from the models of the parts alone\. Intuitively,C\(xa,xb→x\)C\(x\_\{a\},x\_\{b\}\\to x\)is large when jointly consideringxax\_\{a\}andxbx\_\{b\}reveals a novel compression strategy that does not arise when they are modeled separately, such as when a pattern repeats across the boundary betweenxax\_\{a\}andxbx\_\{b\}but not within either substring individually\. More broadly, it measures the extent to which the structure of the whole is*different*from the structures of the parts\.

Note that[Section3\.2](https://arxiv.org/html/2610.20922#S3.SS2.SSS0.Px1)measures only*novel*compositional structure from the decomposition ofxxintoxax\_\{a\}andxbx\_\{b\}; it does not quantify the compositional structure that is already present in the parts themselves\.

#### Compositional structure profiles\.

The quantityC\(xa,xb→x\)C\(x\_\{a\},x\_\{b\}\\to x\)measures novel compositional structure relative to a single decomposition of a string\. More generally, ifx=\[x1,…,xk\]x=\[x\_\{1\},\\dots,x\_\{k\}\], we define:

C\(x1,…,xk→x\):=K\(mx∣mx1,…,mxk\)\.\\displaystyle C\(x\_\{1\},\\dots,x\_\{k\}\\to x\):=K\(m\_\{x\}\\mid m\_\{x\_\{1\}\},\\dots,m\_\{x\_\{k\}\}\)\.\(7\)This definition can be applied recursively with respect to any chosen decomposition strategy, which allows us to characterize a string’scompositional structure profile\.

Definition 2\. Compositional structure profileLetTTbe a rooted decomposition tree for a stringxx, where each nodevvis associated with a substringxvx\_\{v\}and childrenv1,…,vkvv\_\{1\},\\dots,v\_\{k\_\{v\}\}satisfyingxv=\[xv1,…,xvkv\]x\_\{v\}=\[x\_\{v\_\{1\}\},\\dots,x\_\{v\_\{k\_\{v\}\}\}\]\. For each such node and children, we define its local compositionality by:CT,x\(v\):=C\(xv1,…,xvkv→xv\)=K\(mxv∣mxv1,…,mxvk\)\.\\displaystyle C\_\{T,x\}\(v\):=C\(x\_\{v\_\{1\}\},\\dots,x\_\{v\_\{k\_\{v\}\}\}\\to x\_\{v\}\)=K\(m\_\{x\_\{v\}\}\\mid m\_\{x\_\{v\_\{1\}\}\},\\dots,m\_\{x\_\{v\_\{k\}\}\}\)\.\(8\)We define a stringxx’s*compositional structure profile*with respect to a rooted decomposition treeTTas:𝒫T​\(x\):=\(CT,x​\(v\)\)v∈Int⁡\(T\)∈ℝ≥0Int⁡\(T\),\\displaystyle\\mathcal\{P\}\_\{T\}\(x\):=\\left\(C\_\{T,x\}\(v\)\\right\)\_\{v\\in\\mathrm\{Int\}\(T\)\}\\in\\mathbb\{R\}\_\{\\geq 0\}^\{\\mathrm\{Int\}\(T\)\},\(9\)whereInt⁡\(T\)\\mathrm\{Int\}\(T\)denotes the set of internal nodes ofTT\.

Intuitively,[Section3\.2](https://arxiv.org/html/2610.20922#S3.SS2.SSS0.Px2)says that we can consider a hierarchical decomposition of a string into a tree and record how much novel compositional structure appears at each composition step in that tree’s hierarchy\. For example, one may chooseTTto be a balanced binary tree obtained by recursively splittingxxinto two halves until a prescribed minimum substring length is reached\. In that case,CT,x​\(v\)C\_\{T,x\}\(v\)is measured at every join operation in the recursive decomposition, and𝒫T​\(x\)\\mathcal\{P\}\_\{T\}\(x\)captures the emergence of novel compositional structure inxxat multiple scales and locations\.

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\)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 structurediiddata, structure distributed across nested scales for hierarchical objects, and continually accumulating structure for open\-ended processes\.[Figure1](https://arxiv.org/html/2610.20922#S3.F1)visually illustrates how compositional structure profiles provide signatures not only of how much structure an object contains, but of how that structure is organized\. Random or trivially regular objects exhibit little novel structure throughout the decomposition\. For structurediiddata, novel structure appears only up to a characteristic scale: once enough observations determine the shared data\-generating process, additional samples introduce no new model structure since the arrangement of the samples is arbitrary and random\. Hierarchical objects such as music and art instead exhibit novel structure across many nested scales, as smaller patterns compose into progressively larger ones\. Under a left\-to\-right decomposition, open\-ended processes such as curricula, lifetime experience, or evolution produce a different signature, with each new segment extending or refactoring the structure accumulated so far\. These qualitatively distinct profiles make the organization and growth of an object’s structure apparent\.

An image dataset makes the connection between hierarchical compositional structure and scale concrete\. A single image of a cat contains many edge segments, textures, and simple shapes, so these recurring structures may already justify their place in its optimal model; with only one cat, however, introducing a reusable concept of a cat may not yet repay its description length cost\. Across many images, cats recur often enough for the joint model to represent them as compositions of lower\-level structures; with still more data, rarer regularities can justify further distinctions such as breeds or recurring relations between cats and indoor or outdoor scenes\. Larger datasets therefore expose progressively higher levels of the hierarchy, since rarer combinations involving more parts require more observations before they improve compression\. The compositional structure profile records the scales at which these new abstractions become worthwhile, and for non\-stationary data additionally records the locations\.

#### The choice of decomposition\.

Up to this point,[Section3\.2](https://arxiv.org/html/2610.20922#S3.SS2.SSS0.Px2)has defined a compositional structure profile in a way that depends on the choice of decomposition treeTT\. However, intuitions about compositionality strongly suggest that a given object has an*intrinsic*, or “true” decomposition\. We think of a compositional object has having parts that combine to form wholes in a particular way, and capturing those intrinsic hierarchies is an important part of defining compositional structure\. We leave this as an open problem for future work, which bears on several important questions\. For instance, if one were to use a*different*decomposition from this intrinsic one, would the resulting compositionality structure profile still be meaningful? Do there exist objects which are intuitively non\-compositional, but erroneously appear as if they were under the wrong decomposition? For an object that was originally constructed through a series of compositions, as is the case in the evolution of life\([Agüera y Arcas, 2025](https://arxiv.org/html/2610.20922#bib.bib3)\)and technology\([Arthur, 2009](https://arxiv.org/html/2610.20922#bib.bib2)\), would the intrinsic decomposition recover this true history?

Although we leave these questions unanswered in the present work, we conjecture that an object’s intrinsic decomposition is the one that maximizes the sum of scoresC\(xv1,…,xvkv→xv\)C\(x\_\{v\_\{1\}\},\\dots,x\_\{v\_\{k\_\{v\}\}\}\\to x\_\{v\}\)across the tree \(i\.e\., the sum of[Equation9](https://arxiv.org/html/2610.20922#S3.E9)\)\. We justify this more extensively in[AppendixB](https://arxiv.org/html/2610.20922#A2), but the intuition is that this would result in joins that maximally privilege the emergence of shared parts throughout the decomposition, capturing the object’s natural hierarchy\.

### 3\.3Approximating compositional structure

The preceding definitions cannot be computed exactly\. In addition to the uncomputability of the Kolmogorov complexities used to describe models and measure conditional novelty, identifying an Occam’s razor model requires searching a potentially infinite class of computable models\. Even if progressively better descriptions are found, there is generally no way to certify that no unexamined model would yield a shorter two\-part code\.

In practice, we replace these quantities with empirical coding and search procedures\. Letffdenote an empirical two\-part coding scheme, together with an associated model class and fitting procedure, that assigns the code length:

Lmf​\(x\):=Lmodelf​\(m\)\+Ldataf​\(x∣m\)\\displaystyle L\_\{m\}^\{f\}\(x\):=L\_\{\\mathrm\{model\}\}^\{f\}\(m\)\+L\_\{\\mathrm\{data\}\}^\{f\}\(x\\mid m\)\(10\)and returns an empirical MDL modelmxfm\_\{x\}^\{f\}\. Letggdenote an empirical conditional coding scheme for describing one fitted model given others\. We then define the empirical compositionality ofx=\[x1,…,xk\]x=\[x\_\{1\},\\dots,x\_\{k\}\]by:

Cf,g\(x1,…,xk→x\):=Lcondg\(mxf∣mx1f,…,mxkf\)\.\\displaystyle C^\{f,g\}\(x\_\{1\},\\dots,x\_\{k\}\\to x\):=L\_\{\\mathrm\{cond\}\}^\{g\}\\bigl\(m\_\{x\}^\{f\}\\mid m\_\{x\_\{1\}\}^\{f\},\\dots,m\_\{x\_\{k\}\}^\{f\}\\bigr\)\.\(11\)Thus,ffapproximates both the description lengths and the search involved in constructing the models, whileggmeasures the additional cost of describing the fitted model of the whole from those of its parts\. The resulting quantity is an operational, coding\-strategy\-dependent notion of compositionality, rather than a formal bound on the corresponding algorithmic\-information quantity\. Further details are provided in[AppendixA](https://arxiv.org/html/2610.20922#A1)\.

### 3\.4Relationship to other measures of compositionality

The literature on compositionality has a long history spanning many fields, so we do not aim to exhaustively survey it here\. Instead, we focus on formal definitions of compositionality that have been proposed \(at times under different names\), with a particular emphasis on approaches leveraging algorithmic or Shannon information theory\.

#### Algorithmic mutual information\.

For an objectx=\[xa,xb\]x=\[x\_\{a\},x\_\{b\}\], algorithmic mutual information \(AMI\) quantifies the degree to which the whole is more compressible than the parts:

I⁡\(xa:xb\)=K⁡\(xa\)\+K⁡\(xb\)−K⁡\(xa,xb\)\.\\displaystyle I\(x\_\{a\}:x\_\{b\}\)=K\(x\_\{a\}\)\+K\(x\_\{b\}\)\-K\(x\_\{a\},x\_\{b\}\)\.AMI has been proposed as a measure for what we here call novel compositional structure\([Agüera y Arcas, 2025](https://arxiv.org/html/2610.20922#bib.bib3);[Schmidhuber, 1997](https://arxiv.org/html/2610.20922#bib.bib20)\), and indeed it bears many similarities to the definition we have proposed\. In particular, under very mild assumptions it can be shown that:

C\(xa,xb→x\)\>0⟹I\(xa:xb\)\>0,\\displaystyle C\(x\_\{a\},x\_\{b\}\\to x\)\>0\\implies I\(x\_\{a\}:x\_\{b\}\)\>0,but that the reverse does not hold \(proof in[SectionC\.1](https://arxiv.org/html/2610.20922#A3.SS1)\)\. Intuitively, two objects can share AMI for one of two reasons: \(i\) they share existing structure inmxam\_\{x\_\{a\}\}andmxbm\_\{x\_\{b\}\}that need not be redundantly encoded inmxm\_\{x\}, or \(ii\) they share novel structure inmxm\_\{x\}that only appears when they are considered jointly and does not exist in eithermxam\_\{x\_\{a\}\}ormxbm\_\{x\_\{b\}\}alone\.C\(xa,xb→x\)C\(x\_\{a\},x\_\{b\}\\to x\)measures only the latter case, disentangling the emergence of novel compositional structure from simply the accumulation of more data with the same structure\.

#### Partial information decomposition\.

Partial information decomposition \(PID\) separates the information that two sourcesXaX\_\{a\}andXbX\_\{b\}provide about a targetYYinto redundant, unique, and synergistic components\([Williams and Beer, 2010](https://arxiv.org/html/2610.20922#bib.bib21)\):

I⁡\(Xa,Xb,Y\)\\displaystyle I\(X\_\{a\},X\_\{b\};Y\)=Red⁡\(Xa,Xb,Y\)\+Unqa​\(Xa,Xb,Y\)\\displaystyle=\\mathrm\{Red\}\(X\_\{a\},X\_\{b\};Y\)\+\\mathrm\{Unq\}\_\{a\}\(X\_\{a\},X\_\{b\};Y\)\+Unqb​\(Xa,Xb,Y\)\+Syn⁡\(Xa,Xb,Y\)\.\\displaystyle\\quad\+\\mathrm\{Unq\}\_\{b\}\(X\_\{a\},X\_\{b\};Y\)\+\\mathrm\{Syn\}\(X\_\{a\},X\_\{b\};Y\)\.The synergistic term measures information aboutYYthat is available from\(Xa,Xb\)\(X\_\{a\},X\_\{b\}\)jointly but from neither source individually\. It is therefore the closest Shannon\-theoretic analogue ofC\(xa,xb→x\)C\(x\_\{a\},x\_\{b\}\\to x\): both notions aim to isolate information that becomes available only when the parts are considered jointly\.

The two quantities nevertheless address different settings\. PID is a property of a joint distribution over sources and a target, whereasC\(xa,xb→x\)C\(x\_\{a\},x\_\{b\}\\to x\)is an algorithmic property of the internal structure of an individual object\. This distinction is particularly important in the intrinsic part–whole setting\. If the PID target is chosen to be the whole,Y=\(Xa,Xb\)Y=\(X\_\{a\},X\_\{b\}\), then we trivially have that:

Red⁡\(Xa,Xb,\(Xa,Xb\)\)\\displaystyle\\mathrm\{Red\}\(X\_\{a\},X\_\{b\};\(X\_\{a\},X\_\{b\}\)\)=I⁡\(Xa,Xb\),\\displaystyle=I\(X\_\{a\};X\_\{b\}\),Syn⁡\(Xa,Xb,\(Xa,Xb\)\)\\displaystyle\\mathrm\{Syn\}\(X\_\{a\},X\_\{b\};\(X\_\{a\},X\_\{b\}\)\)=0\.\\displaystyle=0\.Consequently, such a PID cannot detect structure that emerges when the sources are combined into the target\. PID\-based measures of linguistic compositionality instead introduce an external target, such as a word form generated from multiple semantic features\([Socolof et al\., 2022](https://arxiv.org/html/2610.20922#bib.bib22)\)\. These measures characterize the compositionality of a mapping between variables, rather than the compositional structure intrinsic to an object\.

Finally, although PID requires its components to sum to the corresponding mutual information quantities, it does not uniquely determine how information should be allocated among the redundant, unique, and synergistic terms\. Consequently, there is no generally accepted decomposition, and existing proposals satisfy different, sometimes incompatible, auxiliary axioms\([Harder et al\., 2013](https://arxiv.org/html/2610.20922#bib.bib23);[Matthias et al\., 2025](https://arxiv.org/html/2610.20922#bib.bib24)\)\. Our definition does not attempt a complete information decomposition and therefore avoids selecting among these alternatives: it directly measures the conditional description lengthK⁡\(mx∣mxa,mxb\)K\(m\_\{x\}\\mid m\_\{x\_\{a\}\},m\_\{x\_\{b\}\}\)of the whole’s structural model, thereby quantifying structural information that emerges only when the parts are considered jointly — an algorithmic analogue of synergistic information\.

#### Emergence and Kolmogorov’s structure function\.

Emergence is commonly understood as the appearance of system\-level properties that are novel relative to those of the system’s constituents, making it conceptually close to compositionality\.[Bédard and Bergeron \(2022\)](https://arxiv.org/html/2610.20922#bib.bib25)propose an algorithmic formalization based on Kolmogorov’s structure function\([Kolmogorov, 1973](https://arxiv.org/html/2610.20922#bib.bib13);[Vereshchagin and Vitányi, 2004](https://arxiv.org/html/2610.20922#bib.bib26)\)\. Intuitively, the structure function considers increasingly large complexity budgets for describing a model of an object and, at each budget, identifies the modelmmthat minimizes the remaining model\-to\-data codelengthlm​\(x\)l\_\{m\}\(x\)\. A substantial drop indicates that permitting a more complex model reveals a new explanatory strategy that shortens the overall two\-part description\. Their definition associates emergence with the presence of several such drops, corresponding to multiple useful models of increasing complexity\. For example, a physical system may admit a relatively simple thermodynamic description in terms of macroscopic variables, while larger model budgets permit more detailed descriptions involving microscopic dynamics and initial conditions\.

However, the complexity of a model is not itself a scale in a decomposition of the observed object\. Consequently, successive drops need not correspond to structure within progressively larger collections of parts: they may instead reflect different explanatory strategies for the same data\. The framework therefore characterizes emergence across a hierarchy of model complexities, but does not specifically isolate structure that emerges when constituent objects are combined asC\(xa,xb→x\)C\(x\_\{a\},x\_\{b\}\\to x\)does\. The two approaches are thus complementary: the structure function captures the plurality of emergent explanations available at different levels of model complexity, whereas our definition quantifies emergent structure arising at particular composition steps\.

#### Formal grammars and compositional semantics\.

In formal semantics and programming\-language theory, compositionality is conventionally defined relative to a specified syntax and interpretation: the meaning of a compound expression is determined by the meanings of its constituents and the rules by which they are combined\([Pagin and Westerståhl, 2010](https://arxiv.org/html/2610.20922#bib.bib27)\)\. Ifffis a syntactic composition rule andMMis an interpretation, this principle can be expressed as:

M⁡\(f⁡\(a,b\)\)=Ff​\(M⁡\(a\),M⁡\(b\)\),\\displaystyle M\(f\(a,b\)\)=F\_\{f\}\(M\(a\),M\(b\)\),whereFfF\_\{f\}is the corresponding operation in the semantic domain\. Category\-theoretic formulations express the same principle through structure\-preserving maps, such as functors, between syntactic and semantic structures\. These frameworks characterize compositionality only once the constituents, composition rules, and semantic domain have been specified; they do not by themselves quantify how much compositional structure an object intrinsically contains, nor do they identify that structure from arbitrary data\.

Our definition addresses these complementary questions\. A grammar or functional program may itself constitute the modelmxm\_\{x\}, in which caseC\(xa,xb→x\)C\(x\_\{a\},x\_\{b\}\\to x\)measures the additional information required to describe the grammar or library of the whole from those of its parts\. In functional\-programming terms, this resembles the cost of refactoring: combiningxax\_\{a\}andxbx\_\{b\}may reveal a reusable abstraction that was not justified by either part separately\. In this way,C\(xa,xb→x\)C\(x\_\{a\},x\_\{b\}\\to x\)is complementary to these more traditional views of compositionality: it can describe the emergence of compositional structure in a formal grammar\.

#### Assembly theory\.

Assembly theory grew out of origins\-of\-life research as an attempt to differentiate living from non\-living objects\([Sharma et al\., 2023](https://arxiv.org/html/2610.20922#bib.bib28)\)\. It treats a living object as something that exists in large numbers of copies and is built from simpler pieces through a sequence of allowed physical events\. Once a piece has been built, it can be reused, so the object’s*assembly index*is the length of its shortest construction path\. Assembly theory is therefore an MDL\-based framework for characterizing living systems in which composition and hierarchy are central\. In more technical ways, however, it differs substantially from our definition of compositionality\. Among other things, our definition measures novel structure in the model of an individual object relative to the models of its parts, without requiring a physical construction space or observed copies\. It also extends to more abstract forms of composition and distinguishes structure from random detail within an individual object\.

#### Symbiogenesis\.

Symbiogenesis is the evolutionary idea that new kinds of organisms can arise when previously separate living systems join and become interdependent\([Sagan, 1967](https://arxiv.org/html/2610.20922#bib.bib29)\)\. The familiar example is the bacterial ancestor of mitochondria becoming part of a host cell, giving rise to eukaryotic cells\.[Agüera y Arcas \(2025\)](https://arxiv.org/html/2610.20922#bib.bib3)casts this as a general route to hierarchical complexity in which smaller replicators combine into a larger replicator, which can then combine with others; the total structure involves describing both the parts as well as how they fit together into the larger whole\. Interestingly, in this computational account, the parts and whole carry instructions for their own reproduction — i\.e\., they are*self\-encoding*\. Our definition places no such requirement on an object’s parts or whole; it measures the novel structure that appears when the parts are considered together, however it arose\. Thus, symbiogenesis offers a plausible mechanism for the emergence of the structure thatC\(xa,xb→x\)C\(x\_\{a\},x\_\{b\}\\to x\)measures, and for its prevalence in the natural world\.

## 4Generating compositional structure

The previous section described a rigorous framework for quantifying compositionality and characterizing an object’s compositional structure profile\. We now turn to the inverse problem: given a pre\-specified compositional structure profile, can we*generate*objects that satisfy it?

For the remainder of this section, we consider restricted and tractable coding schemesffandggas described in[Section3\.3](https://arxiv.org/html/2610.20922#S3.SS3), which define an empirical compositionality scoreCf,g\(x1,…,xk→x\):=Lcondg\(mxf∣mx1f,…,mxkf\)C^\{f,g\}\(x\_\{1\},\\dots,x\_\{k\}\\to x\):=L\_\{\\mathrm\{cond\}\}^\{g\}\\bigl\(m\_\{x\}^\{f\}\\mid m\_\{x\_\{1\}\}^\{f\},\\dots,m\_\{x\_\{k\}\}^\{f\}\\bigr\)that we can compute\. For an objectxx, a particular decomposition treeTTgives us the empirical compositional structure profile:

𝒫Tf,g​\(x\):=\(CT,xf,g​\(v\)\)v∈Int⁡\(T\)∈ℝ≥0Int⁡\(T\)\.\\displaystyle\\mathcal\{P\}\_\{T\}^\{f,g\}\(x\):=\\left\(C\_\{T,x\}^\{f,g\}\(v\)\\right\)\_\{v\\in\\mathrm\{Int\}\(T\)\}\\in\\mathbb\{R\}\_\{\\geq 0\}^\{\\mathrm\{Int\}\(T\)\}\.\(12\)This profile is an indexed family of local compositionality values, one for each composition step in the tree\. From this profile, we may define any scalar functionals:ℝ≥0Int⁡\(T\)→ℝs:\\mathbb\{R\}\_\{\\geq 0\}^\{\\,\\mathrm\{Int\}\(T\)\}\\to\\mathbb\{R\}, where the quantitys⁡\(𝒫Tf,g​\(x\)\)s\\left\(\\mathcal\{P\}\_\{T\}^\{f,g\}\(x\)\\right\)then defines a scalar summary of the compositional structure ofxxunderTT\. This summary quantity, if well behaved, can define a goal to be maximized by learning algorithms operating over the space ofxx’s\.

This allows us to generate objects with desired compositional structure profiles by defining the reward:

R⁡\(x,T,f,g,s\)=s⁡\(𝒫Tf,g​\(x\)\)\.\\displaystyle R\(x\\ ;\\ T,f,g,s\)=s\\left\(\\mathcal\{P\}\_\{T\}^\{f,g\}\(x\)\\right\)\.\(13\)and then using any optimization or sampling procedure to search for objects with high reward\. In sum, each of our below experiments is fully characterized by:

- •A domain𝒳\\mathcal\{X\}over which we can search for objects with high reward\. Here, we consider two domains: symbolic strings and images\.
- •A pre\-specified decomposition treeTT, coding schemesffandgg, and scalar functionalsswhich jointly define the rewardR⁡\(x,T,f,g,s\)R\(x\\ ;\\ T,f,g,s\)\.
- •An optimization or search algorithm capable of discovering objectsx∈𝒳x\\in\\mathcal\{X\}with high reward\.

### 4\.1Compositional strings

We first consider a deliberately minimal domain: fixed\-length symbolic strings with no externally specified semantics\. Concretely, the domain is𝒳=\{0,…,7\}128\\mathcal\{X\}=\\\{0,\\dots,7\\\}^\{128\}; strings of length128128with a vocabulary of88symbols\. Methods are briefly described below and illustrated in[Figure2](https://arxiv.org/html/2610.20922#S4.F2)a;[SectionD\.1](https://arxiv.org/html/2610.20922#A4.SS1)contains further details\.

![Refer to caption](https://arxiv.org/html/2610.20922v1/strings.png)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;[Equation14](https://arxiv.org/html/2610.20922#S4.E14)\) or \(ii\) an alternative reward that just maximizes structure without any pressure for compositionality \(orange;K⁡\(mx\)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 across1010seeds\. Panel \(d\) shows results for one representative seed only; dot plots for all seeds are provided in[SectionD\.1](https://arxiv.org/html/2610.20922#A4.SS1)\.#### MDL algorithm\.

For the two\-part codeff, we represent a string using a deterministic context\-free grammar together with a residual sequence expressed through that grammar\. Here, a grammar is simply a collection of named replacement rules: a rule assigns a name to a sequence symbols, which can also contain the names of previously defined rules\. For example, the rulesA→01A\\to 01andB→A​AB\\to AAallowBBto stand for01010101\. In standard terminology, the original symbols are*terminals*and the rule names are*non\-terminals*\. Because rules may invoke other rules, the grammar resembles a dictionary whose entries can themselves be defined from earlier entries, allowing repeated patterns to be represented hierarchically\. The grammar serves as the model, while the residual specifies how its reusable components and any remaining terminal symbols are assembled into the complete string\. We measure the two code components using an entropy code over all terminal symbols and rule names appearing in the grammar and residual\. To fit a short grammar without introducing unjustified structure, we use an MDL\-guided extension of RePair and MR\-RePair\([Larsson and Moffat, 2000](https://arxiv.org/html/2610.20922#bib.bib34);[Furuya et al\., 2018](https://arxiv.org/html/2610.20922#bib.bib35)\): it greedily replaces repeated maximal substrings with new rule names, but introduces a rule only when its estimated compression gain exceeds the cost of describing the rule itself\.

#### Conditional model compression\.

At each join in a decomposition tree, two adjacent substrings are combined into a larger substring\. We fit grammars separately to the two parts and to their combination, and use the conditional codeggto measure how much of the combined grammar cannot be recovered from the grammars fitted to the parts\. Since rule names are arbitrary, we first relabel the rules in each part grammar to find a low\-cost alignment with the combined grammar, using the nested structure of the rules to determine which ones correspond\. Each rule in the combined grammar is then either encoded directly or by describing its differences from the best\-matching aligned rule in either part grammar, whichever is shorter\. Thus, carrying an existing rule from a part into the combined model costs little, whereas a new rule that becomes economical only after the parts are combined incurs a large cost\.

#### Reward\.

Our reward is designed to favour strings that reveal novel grammar structure throughout the hierarchy, rather than concentrating it at a single scale\. We therefore choose the decomposition treeTTto be a balanced binary tree: the complete string is recursively bisected into contiguous halves until reaching substrings of length four\. Its internal nodes form five join scales, ranging from combinations of length\-four substrings to the combination of the two length\-64 halves of the complete string\. At every join, we compute the conditional grammar cost described above and normalize it by the length of the combined substring\. We then average these scores within each scale, so that scales containing many small joins do not dominate those containing a few large joins\. Finally, we combine these scale averages using a power mean withp=0\.75p=0\.75\. Choosingp<1p<1places greater pressure on the weakest scales than an arithmetic mean would, encouraging compositional structure to emerge more evenly across the hierarchy\.

Formally, let𝒱ℓ\\mathcal\{V\}\_\{\\ell\}be the joins at scaleℓ\\ell, letrℓ​\(x\)r\_\{\\ell\}\(x\)denote their mean size\-normalized compositionality, and letLLdenote the total number of scales\. Then:

rℓ​\(x\)\\displaystyle r\_\{\\ell\}\(x\)=1\|𝒱ℓ\|​∑v∈𝒱ℓCT,xf,g​\(v\)\|xv\|,\\displaystyle=\\frac\{1\}\{\|\\mathcal\{V\}\_\{\\ell\}\|\}\\sum\_\{v\\in\\mathcal\{V\}\_\{\\ell\}\}\\frac\{C\_\{T,x\}^\{f,g\}\(v\)\}\{\|x\_\{v\}\|\},\(14\)R⁡\(x\)\\displaystyle R\(x\)=\(1L​∑ℓ=1Lrℓ​\(x\)p\)1/p,p=0\.75\.\\displaystyle=\\left\(\\frac\{1\}\{L\}\\sum\_\{\\ell=1\}^\{L\}r\_\{\\ell\}\(x\)^\{p\}\\right\)^\{1/p\},\\quad p=0\.75\.\(15\)

#### Optimization\.

We maximize this reward with a single\-objective use of NSGA\-II\([Deb et al\., 2002](https://arxiv.org/html/2610.20922#bib.bib36)\)\. Starting from10,00010\{,\}000uniformly random strings, each generation produces5,0005\{,\}000offspring through tournament selection and two\-point crossover, followed by independently resetting each symbol with probability2/1282/128\. Duplicate strings are removed, and elitist selection retains the best population from parents and offspring\.

#### Results\.

We ran the evolutionary optimization for2,0002\{,\}000generations across1010seeds\. In addition to our compositionality reward in[Equation14](https://arxiv.org/html/2610.20922#S4.E14), we also compared to a structure\-based reward that optimizes forLmodelf​\(mxf\)L\_\{\\text\{model\}\}^\{f\}\(m\_\{x\}^\{f\}\): the empirical estimate of stringxx’s final structural complexityK⁡\(mx\)K\(m\_\{x\}\)\. This comparison serves as an empirical test of our claim that compositionality captures a specific*kind*of structure based on the interactions between parts at multiple scales, rather than simply the total amount of structure\. We used identical hyperparameters to optimize both rewards\.[Figure2](https://arxiv.org/html/2610.20922#S4.F2)b shows the time\-course of the rewards, both of which steadily grow before reaching a plateau, indicating they were successfully optimized\.

To demonstrate the properties of our compositionality reward, we analyze the nested repeated structure present within the strings by computing summary statistics of their grammars, shown in[Figure2](https://arxiv.org/html/2610.20922#S4.F2)c\. Here, we fit these grammars using the MR\-RePair algorithm\([Furuya et al\., 2018](https://arxiv.org/html/2610.20922#bib.bib35)\), which recursively creates a rule whenever a pattern repeats at least once\. Compared to structure\-optimized strings, we find that compositionality\-optimized strings result in substantially*deeper*grammars, where the depth of a grammar rule denotes the number of recursive non\-terminal symbol expansions needed before the flattened rule contains only terminal symbols\. For example, a grammar describing a string with purely “flat” structure would consist entirely of depth\-00rules that each expand to a sequence of terminal symbols\. Despite this, structure\-optimized strings still result in highly complex grammars; in fact, these grammars tend to have*more*rules and longer rule expansions than those of the compositionality\-optimized strings\. This illustrates the core property of our compositionality definition\. In general, an object can be structured in multiple ways that do not require a rich and interconnected hierarchy of patterns — this structure can be flat \(as in long but low\-depth grammar rules\) and independent across the object \(as in grammar rules that are only used in distinct regions of the object\)\.

We provide a more visual demonstration of these distinct forms of structure in[Figure2](https://arxiv.org/html/2610.20922#S4.F2)d, which shows “dot plots” for the highest\-reward string using each reward function, as well as for a random string\. Dot plots are commonly used in DNA analysis to identify repeated structures within a string\([Gibbs and Mcintyre, 1970](https://arxiv.org/html/2610.20922#bib.bib47)\), and build a symmetric binary\|x\|×\|x\|\|x\|\\times\|x\|matrix where a given cell at index\(i,j\)\(i,j\)is11ifx⁡\[i\]=x⁡\[j\]x\[i\]=x\[j\]and00otherwise\. A repeated pattern appears in the plot as diagonal lines off of the main diagonal, making it easy to visually inspect the number, length, and locations of these patterns\. Furthermore, if a pattern contains a smaller sub\-pattern that appears elsewhere in the string, it will show up as a smaller diagonal line in the same block of rows spanned by the larger pattern \(or, equivalently, block of columns due to the matrix’s symmetry\)\. For compositionality\-optimized strings, we find that the dot plots contain a more dense distribution of patterns and sub\-patterns than those of structure\-optimized or random strings\. Structure\-optimized strings do still exhibit repeated patterns, but they tend to be longer, more sparse, and less hierarchical\. Overall, the dot plots of structure\-optimized strings look more similar to those of random strings, but the addition of a few long diagonals\.

### 4\.2Compositional images

We next consider a more complex domain in which humans can readily recognize compositional structure: images\. We generate33\-channel images of size64×6464\\times 64, with values discretized to44possible intensities, resulting in a domain𝒳=\{0,…,3\}64×64×3\\mathcal\{X\}=\\\{0,\\dots,3\\\}^\{64\\times 64\\times 3\}\. Since nothing in our reward prescribes these images to be “natural”, we expect them only to contain abstract compositional structure\. Methods are briefly described below;[SectionD\.2](https://arxiv.org/html/2610.20922#A4.SS2)contains further details\.

![Refer to caption](https://arxiv.org/html/2610.20922v1/images.png)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;[Equation14](https://arxiv.org/html/2610.20922#S4.E14)\) or \(ii\) an alternative reward that just maximizes structure without any pressure for compositionality \(orange;K⁡\(mx\)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[SectionD\.2](https://arxiv.org/html/2610.20922#A4.SS2)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[SectionD\.2](https://arxiv.org/html/2610.20922#A4.SS2)\.Seeds\.Shaded regions in panels \(b, c\) reflect the standard error of the mean across33seeds\.#### MDL algorithm\.

Fixed\-pattern grammars are too restrictive to capture the shapes, textures, and spatial relationships that make images interesting\. We therefore use a coordinate\-based neural representation, following the general approach used by neural radiance fields and compositional pattern\-producing networks \(CPPNs\)\([Mildenhall et al\., 2020](https://arxiv.org/html/2610.20922#bib.bib40);[Stanley, 2007](https://arxiv.org/html/2610.20922#bib.bib41)\)\. For every image patchxvx\_\{v\}, we fit a fixed\-architecture network that maps a normalized two\-dimensional coordinate to a categorical distribution over the four possible intensities in each channel\. Because one set of weights must account for every coordinate, spatial regularities can be represented by the network while idiosyncratic pixels remain in the model\-to\-data code\.

Merely training a flexible network to reproduce a single patch can lead it to memorize idiosyncratic pixels rather than capture structure that genuinely compresses the image\. We therefore regularize the fitting procedure, most importantly by training with maximum likelihood on a random half of the patch’s pixels and using the remaining half as held\-out data for early stopping\. The selected network is the checkpoint with the lowest held\-out cross\-entropy, and we retain it only if it improves upon a constant model that predicts the marginal intensity distribution of each channel\. This fallback prevents the network from attributing spurious spatial structure to a patch that is better described without spatial dependence\.

To complete the two\-part code, we must estimate both the information stored in the fitted network and the information left unexplained by it\. Following learning\-curve estimates of neural\-network description length\([Blier and Ollivier, 2018](https://arxiv.org/html/2610.20922#bib.bib39)\), we estimate the first quantity from the cumulative training loss incurred while learning the network\. At each point in training, we subtract the loss of the final selected model: the remainder measures predictive errors caused by not yet having learned the model, rather than errors that remain even after it has been learned\. Accumulating this excess over training therefore provides a proxy for the number of bits absorbed into the network’s weights\. The model\-to\-data term is the selected model’s negative log\-likelihood over the complete patch\. Together, these terms form our empirical two\-part coding schemeff\.

#### Conditional model compression\.

Directly describing one neural network given several others is complicated by the many parameter settings that implement the same function\. Instead, we use the intuition that the conditional complexity of a target model is reflected by how much must be learned to fine\-tune the given models into it\. We implement this comparison at the level of predictions rather than parameters\. At a join, the modelmxvfm\_\{x\_\{v\}\}^\{f\}fitted to the parent patch acts as a teacher\. The four child models are combined into a routed student: each coordinate is sent to the model fitted to its quadrant, using that child’s local coordinates\. This unmodified student represents the hypothesis that the parent model is merely the juxtaposition of the four child models\.

We then fine\-tune copies of the child models to match the teacher’s predictive distributions across the parent patch, again using held\-out coordinates for early stopping\. We retain the adapted student only when it improves upon the unmodified routed student on these coordinates\. Our conditional codegghas two terms: a learning\-curve estimate of the information required for this adaptation, computed by accumulating the distillation loss attributable to the student not yet having reached its selected state, and the remaining divergence between the selected student and teacher across the complete patch\. If the structure of the whole consists only of the independent structures of its quadrants, with no novel structure revealed by considering them jointly, routing among the child models already reproduces the parent and both costs are near zero\. Conversely, structure that becomes useful only when the quadrants are modeled together changes the parent’s predictions in a way that requires substantial adaptation, producing a large conditional code\. This gives a function\-level surrogate forLcondg​\(mxvf∣mxv1f,…,mxv4f\)L\_\{\\mathrm\{cond\}\}^\{g\}\(m\_\{x\_\{v\}\}^\{f\}\\mid m\_\{x\_\{v\_\{1\}\}\}^\{f\},\\dots,m\_\{x\_\{v\_\{4\}\}\}^\{f\}\)without requiring the independently fitted networks to have aligned parameters\.

#### Reward\.

Whereas a string has one spatial axis and can naturally be bisected, an image has two, so we recursively divide both axes to obtain a quadtree decomposition\. Each patch is split into four quadrants until reaching8×88\\times 8patches\. The resulting joins combine8×88\\times 8patches into16×1616\\times 16patches, then16×1616\\times 16patches into32×3232\\times 32patches, and finally the four32×3232\\times 32patches into the complete image\. As in the string experiment, we normalize each conditional code by the number of spatial locations in its parent patch, average within each join scale, and combine the three scale averages with a power mean usingp=0\.75p=0\.75\. This gives equal overall weight to each spatial scale while placing greater pressure on the weakest ones\.

#### Optimization\.

The image space is far too large to search directly, so we search over compact procedures that generate images\. Specifically, we use compositional pattern\-producing networks \(CPPNs\): coordinate\-based neural networks that specify a single image by mapping each normalized spatial coordinate to its channel values\([Stanley, 2007](https://arxiv.org/html/2610.20922#bib.bib41)\)\. We can thus treat a CPPN’s topology and parameters as a genotype and the image obtained by evaluating it across the coordinate grid as its phenotype\. Its three continuous outputs are quantized to the four intensity levels in each channel\.

We optimize a population of200200such genomes for600600generations using the NeuroEvolution of Augmenting Topologies \(NEAT\)\([Stanley and Miikkulainen, 2002](https://arxiv.org/html/2610.20922#bib.bib44);[Stanley and Miikkulainen, 2004](https://arxiv.org/html/2610.20922#bib.bib45)\)algorithm\. NEAT applies crossover and mutations to network weights, activation functions, nodes, and connections while maintaining species of related networks, allowing the complexity of the image\-generating process to grow during search\. This resembles the Picbreeder study\([Secretan et al\., 2008](https://arxiv.org/html/2610.20922#bib.bib42);[Secretan et al\., 2011](https://arxiv.org/html/2610.20922#bib.bib43)\)\(and we use very similar hyperparameters for the evolutionary algorithm\), except that our compositionality reward replaces human selection\. Both the generator and the empirical coding scheme use coordinate networks; the experiment therefore searches for spatial structure that the chosen coding scheme is capable of recognizing, rather than claiming to cover every possible form of image structure\.

#### Results\.

We ran the evolutionary optimization for600600generations and only33seeds, given the higher computational cost of this experiment\. As in our string generation experiments, we compared compositionality\-optimized images to structure\-optimized ones\.[Figure3](https://arxiv.org/html/2610.20922#S4.F3)b shows that both rewards increase over the course of generations before stabilizing\.

We quantitatively analyze the structure of the resulting images by computing simple network summary statistics of the CPPN genomes that produce them in[Figure3](https://arxiv.org/html/2610.20922#S4.F3)c\. We find that the average number of nodes in the evolved networks, as well as the connections between them, is comparable for the two rewards throughout the evolutionary process\. The average network depth — which measures the longest path \(in connections\) from an input to an output node — also evolves similarly\. The CPPNs instead seem to differ along more fine\-grained metrics that suggest the compositionality reward produces more interconnected networks\. For instance, the number of distinct input\-to\-output paths is greater when optimizing the compositionality reward\. Features represented by hidden nodes are also reused by more than one downstream node more often, and fan\-out to a greater number of nodes\. The same is true for the inputs to these hidden units: multiple inputs are in general combined to form downstream features more often, and in greater number\. Taken together, these results suggest that our compositionality reward results in unified structures and feature recombinations rather than independent structures, in line with our expectations\.

Our generated images themselves produce further evidence along these lines;[Figure3](https://arxiv.org/html/2610.20922#S4.F3)d shows some representative examples, and more are provided in[SectionD\.2](https://arxiv.org/html/2610.20922#A4.SS2)\. Compositionality\-optimized images reliably look more unified: they have distinct central themes involving repeated motifs, shapes, and colour palettes \(although it is difficult to visually establish the presence of feature hierarchies in an objective way\)\. In contrast, structure\-optimized images appear significantly more disjoint: a common trend is that they simply pack many bands of distinct horizontal and vertical colours into the image\. While these bands provide learnable information, they are structurally independent from one another\. These differences are precisely what our definition of compositional structure is intended to capture\.

## 5Discussion

We defined compositionality as the novel shared structure revealed when parts are modeled together\. Formally, it is the information in the best model of a whole that cannot be recovered from the best models of its parts\. Applying this comparison at successive nodes of a decomposition tree yields a profile that reflects the locations and scales at which novel compositional structure emerges\. We tested this definition by using it as a generative objective\. Optimizing strings and images for prescribed profiles produced objects with recognizable nested reuse and coherent organization across scales\. Because the objective constrains the form of this organization while remaining agnostic to its particular content, these results suggest that the definition isolates the intended part–whole organization rather than merely rewarding complexity, regularity, or shared information\.

#### The success of deep learning\.

This view provides one explanation for why depth is a useful inductive bias\. If natural data reveals novel structure whenever smaller regions are combined into larger ones, then an effective model should likewise build representations of larger\-scale structure from those available at smaller scales\. Successive layers of a deep network provide exactly this form of capacity: later features can represent combinations and reorganizations of earlier ones, without requiring the same composition rule at every scale\. Standard architectures nevertheless impose a fixed maximum depth and are usually trained oniiddatapoints of a fixed extent\. For nonstationary streams whose structure continues to grow across temporal scales, the framework instead motivates more flexible architectures whose effective depth or hierarchy can expand whenever larger contexts reveal additional compositional structure\. Reasoning methods\([Wei et al\., 2022](https://arxiv.org/html/2610.20922#bib.bib48)\)and looped layers\([Dehghani et al\., 2019](https://arxiv.org/html/2610.20922#bib.bib49)\)provide potential building blocks towards this goal\.

#### Curricula and open\-ended learning\.

The same idea shifts emphasis from specifying a compositional model directly to constructing data whose compression requires compositional structure\. Letxax\_\{a\}be a learner’s history andxbx\_\{b\}a new segment of experience\. A largeC\(xa,xb→x\)C\(x\_\{a\},x\_\{b\}\\to x\)means thatxbx\_\{b\}does more than repeat known structure, but also does more than contribute an unrelated fact: considered with the history, it induces a new joint account that reuses or reorganizes earlier structure\. A curriculum can therefore be scored by the local compositionality introduced at each step, or by a functional of the resulting left\-to\-right compositional structure profile\. Searching over orderings could then test whether curricula with high scores produce representations that are more reusable and factorized\. This interpretation is consistent with the finding of[Kumar et al\. \(2025\)](https://arxiv.org/html/2610.20922#bib.bib30)that networks evolved through human\-guided, open\-ended search develop more unified and factorized representations than networks trained only to reproduce their endpoints\. Our framework gives a precise hypothesis for this difference: the evolutionary history contributes substantial compositional structure that is absent from the endpoint alone\.

This objective can also guide an agent that chooses its own experience\. A policy could be rewarded for selectingxbx\_\{b\}that maximizes an empirical approximation toC\(xa,xb→x\)C\(x\_\{a\},x\_\{b\}\\to x\), thereby constructing a curriculum through interaction\. This is closely related to intrinsic curiosity based on compression progress\([Schmidhuber, 2009](https://arxiv.org/html/2610.20922#bib.bib31);[Schmidhuber, 2010](https://arxiv.org/html/2610.20922#bib.bib32)\)and to objectives that seek learnable structure such as Epiplexity\([Finzi et al\., 2026](https://arxiv.org/html/2610.20922#bib.bib33)\)\. The difference is the constraint placed on*how*the learner’s model changes: the reward favours novel structure that becomes useful through its relationship to prior experience, rather than novelty or learnability alone\. Repeated over time, this provides an operational criterion for open\-ended learning in which knowledge continues to grow by building on itself\.

#### Future work and limitations\.

The ideal quantities in our definition are uncomputable, and the empirical version depends on restricted model classes, imperfect MDL search, and conditional codes that provide only operational surrogates for algorithmic complexity\. Our experiments show that useful approximations are possible, but not how stable the resulting scores are across compressors or optimization procedures\. Establishing this robustness, and identifying which approximation errors preserve comparisons between objects, are important next steps\.

A second, crucial open question that we highlighted in[Section3](https://arxiv.org/html/2610.20922#S3)is: which decompositions should be considered for a particular object? The compositional structure profiles we defined here are relative to a decomposition tree, and different trees can expose different structures in the same object\. However, is there any sense in which an object admits an “intrinsic” decomposition, and if so how can it be defined? A systematic account should determine which decompositions expose useful, robust structure and which merely introduce artifacts\. We conjectured that the tree which maximizes the sum of compositionality scores is a particularly good candidate for a canonical decomposition, but this must be further investigated\. Ultimately, these questions reflect a broader feature of compositionality: any claim about how a whole is composed must identify its constituent parts\. Traditional accounts often fix these constituents in advance through a syntax, a set of semantic factors, or an object decomposition; our framework makes the choice explicit, allowing the decomposition itself to become an object of study\.

## References

- Agüera y Arcas \(2025\)B\. Agüera y ArcasWhat is intelligence?: lessons from ai about evolution, computing, and minds\.MIT Press\.Cited by:[§1](https://arxiv.org/html/2610.20922#S1.p2.1),[§3\.2](https://arxiv.org/html/2610.20922#S3.SS2.SSS0.Px3.p1.1),[§3\.4](https://arxiv.org/html/2610.20922#S3.SS4.SSS0.Px1.p1.2),[§3\.4](https://arxiv.org/html/2610.20922#S3.SS4.SSS0.Px6.p1.1)\.
- Andreas \(2019\)J\. AndreasMeasuring compositionality in representation learning\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=HJz05o0qK7)Cited by:[§1](https://arxiv.org/html/2610.20922#S1.p3.1)\.
- Arthur \(2009\)W\. B\. ArthurThe nature of technology: what it is and how it evolves\.Simon and Schuster\.Cited by:[§1](https://arxiv.org/html/2610.20922#S1.p2.1),[§3\.2](https://arxiv.org/html/2610.20922#S3.SS2.SSS0.Px3.p1.1)\.
- Bédard and Bergeron \(2022\)C\. A\. Bédard and G\. BergeronAn algorithmic approach to emergence\.Entropy24\(7\),pp\. 985\.Cited by:[Appendix A](https://arxiv.org/html/2610.20922#A1.p3.1),[§3\.4](https://arxiv.org/html/2610.20922#S3.SS4.SSS0.Px3.p1.1)\.
- Blank and Deb \(2020\)J\. Blank and K\. DebPymoo: multi\-objective optimization in python\.IEEE Access8\(\),pp\. 89497–89509\.Cited by:[§D\.1](https://arxiv.org/html/2610.20922#A4.SS1.SSS0.Px5.p1.1)\.
- Blier and Ollivier \(2018\)L\. Blier and Y\. OllivierThe description length of deep learning models\.Advances in Neural Information Processing Systems31\.Cited by:[§D\.2](https://arxiv.org/html/2610.20922#A4.SS2.SSS0.Px3.p1.2),[§4\.2](https://arxiv.org/html/2610.20922#S4.SS2.SSS0.Px1.p3.1)\.
- Debet al\.\(2002\)K\. Deb, A\. Pratap, S\. Agarwal, and T\. MeyarivanA fast and elitist multiobjective genetic algorithm: nsga\-ii\.IEEE transactions on evolutionary computation6\(2\),pp\. 182–197\.Cited by:[§D\.1](https://arxiv.org/html/2610.20922#A4.SS1.SSS0.Px5.p1.1),[§4\.1](https://arxiv.org/html/2610.20922#S4.SS1.SSS0.Px4.p1.1)\.
- Dehghaniet al\.\(2019\)M\. Dehghani, S\. Gouws, O\. Vinyals, J\. Uszkoreit, and L\. KaiserUniversal transformers\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=HyzdRiR9Y7)Cited by:[§5](https://arxiv.org/html/2610.20922#S5.SS0.SSS0.Px1.p1.1)\.
- Elmozninoet al\.\(2024\)E\. Elmoznino, T\. Jiralerspong, Y\. Bengio, and G\. LajoieA complexity\-based theory of compositionality\.arXiv preprint arXiv:2410\.14817\.Cited by:[§1](https://arxiv.org/html/2610.20922#S1.p3.1)\.
- Finziet al\.\(2026\)M\. Finzi, S\. Qiu, Y\. Jiang, P\. Izmailov, J\. Z\. Kolter, and A\. G\. WilsonFrom entropy to epiplexity: rethinking information for computationally bounded intelligence\.External Links:2601\.03220,[Link](https://arxiv.org/abs/2601.03220)Cited by:[§D\.2](https://arxiv.org/html/2610.20922#A4.SS2.SSS0.Px3.p1.2),[§5](https://arxiv.org/html/2610.20922#S5.SS0.SSS0.Px2.p2.1)\.
- Fortnow \(2000\)L\. FortnowKolmogorov complexity\.InAspects of Complexity, Minicourses in Algorithmics, Complexity, and Computational Algebra, NZMRI Mathematics Summer Meeting, Kaikoura, New Zealand,pp\. 73–86\.Cited by:[§3\.1](https://arxiv.org/html/2610.20922#S3.SS1.SSS0.Px1.p1.1)\.
- Furuyaet al\.\(2018\)I\. Furuya, T\. Takagi, Y\. Nakashima, S\. Inenaga, H\. Bannai, and T\. KidaMR\-repair: grammar compression based on maximal repeats\.arXiv preprint arXiv:1811\.04596\.Cited by:[§D\.1](https://arxiv.org/html/2610.20922#A4.SS1.SSS0.Px2.p1.1),[§4\.1](https://arxiv.org/html/2610.20922#S4.SS1.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2610.20922#S4.SS1.SSS0.Px5.p2.1)\.
- Gácset al\.\(2001\)P\. Gács, J\. T\. Tromp, and P\. M\. VitányiAlgorithmic statistics\.IEEE Transactions on Information Theory47\(6\),pp\. 2443–2463\.Cited by:[§3\.1](https://arxiv.org/html/2610.20922#S3.SS1.SSS0.Px2.p2.1),[§3\.1](https://arxiv.org/html/2610.20922#S3.SS1.SSS0.Px2.p5.2)\.
- Gibbs and Mcintyre \(1970\)A\. J\. Gibbs and G\. A\. McintyreThe diagram, a method for comparing sequences\.European Journal of Biochemistry16\(1\),pp\. 1–11\.External Links:[Document](https://dx.doi.org/10.1111/j.1432-1033.1970.tb01046.x),[Link](https://febs.onlinelibrary.wiley.com/doi/abs/10.1111/j.1432-1033.1970.tb01046.x)Cited by:[§4\.1](https://arxiv.org/html/2610.20922#S4.SS1.SSS0.Px5.p3.1)\.
- Grünwaldet al\.\(2008\)P\. D\. Grünwald P\. M\. Vitányiet al\.Algorithmic information theory\.Handbook of the Philosophy of Information,pp\. 281–320\.Cited by:[§3\.1](https://arxiv.org/html/2610.20922#S3.SS1.SSS0.Px2.p2.1),[§3\.1](https://arxiv.org/html/2610.20922#S3.SS1.SSS0.Px2.p5.2)\.
- Grünwald and Vitányi \(2003\)P\. D\. Grünwald and P\. M\. VitányiKolmogorov complexity and information theory\. with an interpretation in terms of questions and answers\.Journal of Logic, Language and Information12,pp\. 497–529\.Cited by:[§3\.1](https://arxiv.org/html/2610.20922#S3.SS1.SSS0.Px1.p1.1)\.
- Grünwald \(2007\)P\. D\. GrünwaldThe minimum description length principle\.MIT press\.Cited by:[§3\.1](https://arxiv.org/html/2610.20922#S3.SS1.SSS0.Px2.p2.1),[§3](https://arxiv.org/html/2610.20922#S3.p1.1)\.
- Harderet al\.\(2013\)M\. Harder, C\. Salge, and D\. PolaniBivariate measure of redundant information\.Physical Review E—Statistical, Nonlinear, and Soft Matter Physics87\(1\),pp\. 012130\.Cited by:[§3\.4](https://arxiv.org/html/2610.20922#S3.SS4.SSS0.Px2.p3.1)\.
- Kolmogorov \(1965\)A\. N\. KolmogorovThree approaches to the quantitative definition of information’\.Problems of information transmission1\(1\),pp\. 1–7\.Cited by:[§3\.1](https://arxiv.org/html/2610.20922#S3.SS1.SSS0.Px1.p1.1)\.
- Kolmogorov \(1973\)A\. N\. KolmogorovTalk at the information theory symposium\.Note:Presented at the Information Theory Symposium, Tallinn, EstoniaCited by:[§3\.1](https://arxiv.org/html/2610.20922#S3.SS1.SSS0.Px2.p2.1),[§3\.4](https://arxiv.org/html/2610.20922#S3.SS4.SSS0.Px3.p1.1)\.
- Koppel and Atlan \(1989\)M\. Koppel and H\. AtlanProgram\-length complexity, sophistication and induction\.Inform\. Sci\.Cited by:[§3\.1](https://arxiv.org/html/2610.20922#S3.SS1.SSS0.Px2.p2.1)\.
- Kumaret al\.\(2025\)A\. Kumar, J\. Clune, J\. Lehman, and K\. O\. StanleyQuestioning representational optimism in deep learning: the fractured entangled representation hypothesis\.External Links:2505\.11581,[Link](https://arxiv.org/abs/2505.11581)Cited by:[§5](https://arxiv.org/html/2610.20922#S5.SS0.SSS0.Px2.p1.1)\.
- Larsson and Moffat \(2000\)N\. J\. Larsson and A\. MoffatOff\-line dictionary\-based compression\.Proceedings of the IEEE88\(11\),pp\. 1722–1732\.Cited by:[§D\.1](https://arxiv.org/html/2610.20922#A4.SS1.SSS0.Px2.p1.1),[§4\.1](https://arxiv.org/html/2610.20922#S4.SS1.SSS0.Px1.p1.1)\.
- Leibniz \(1898\)G\. W\. LeibnizThe monadology and other philosophical writings\.Clarendon Press,Oxford\.Cited by:[§1](https://arxiv.org/html/2610.20922#S1.p1.1)\.
- Leman and Weisfeiler \(1968\)A\. Leman and B\. WeisfeilerA reduction of a graph to a canonical form and an algebra arising during this reduction\.Nauchno\-Technicheskaya Informatsiya2\(9\),pp\. 12–16\.Cited by:[§D\.1](https://arxiv.org/html/2610.20922#A4.SS1.SSS0.Px3.p5.1)\.
- Liet al\.\(2008\)M\. Li P\. Vitányiet al\.An introduction to kolmogorov complexity and its applications\.Vol\.3,Springer\.Cited by:[§3\.1](https://arxiv.org/html/2610.20922#S3.SS1.SSS0.Px1.p1.1)\.
- Matthiaset al\.\(2025\)P\. H\. Matthias, A\. Makkeh, M\. Wibral, and A\. J\. GutknechtNovel inconsistency results for partial information decomposition\.arXiv preprint arXiv:2512\.16662\.Cited by:[§3\.4](https://arxiv.org/html/2610.20922#S3.SS4.SSS0.Px2.p3.1)\.
- McIntyreet al\.\(2026\)A\. McIntyre, M\. Kallada, C\. G\. Miguel, C\. Feher de Silva, and M\. L\. Nettoneat\-python\.External Links:[Document](https://dx.doi.org/10.5281/zenodo.19024753),[Link](https://github.com/CodeReclaimers/neat-python)Cited by:[§D\.2](https://arxiv.org/html/2610.20922#A4.SS2.SSS0.Px6.p2.1)\.
- Mildenhallet al\.\(2020\)B\. Mildenhall, P\. P\. Srinivasan, M\. Tancik, J\. T\. Barron, R\. Ramamoorthi, and R\. NgNeRF: representing scenes as neural radiance fields for view synthesis\.InECCV,Cited by:[§4\.2](https://arxiv.org/html/2610.20922#S4.SS2.SSS0.Px1.p1.1)\.
- Pagin and Westerståhl \(2010\)P\. Pagin and D\. WesterståhlCompositionality i: definitions and variants\.Philosophy Compass5\(3\),pp\. 250–264\.External Links:[Document](https://dx.doi.org/10.1111/j.1747-9991.2009.00228.x),[Link](https://compass.onlinelibrary.wiley.com/doi/abs/10.1111/j.1747-9991.2009.00228.x)Cited by:[§1](https://arxiv.org/html/2610.20922#S1.p3.1),[§3\.4](https://arxiv.org/html/2610.20922#S3.SS4.SSS0.Px4.p1.1)\.
- Sagan \(1967\)L\. SaganOn the origin of mitosing cells\.Journal of theoretical biology14\(3\),pp\. 225–IN6\.Cited by:[§3\.4](https://arxiv.org/html/2610.20922#S3.SS4.SSS0.Px6.p1.1)\.
- Schmidhuber \(1997\)J\. SchmidhuberLow\-complexity art\.Leonardo30\(2\),pp\. 97–103\.Cited by:[§3\.4](https://arxiv.org/html/2610.20922#S3.SS4.SSS0.Px1.p1.2)\.
- Schmidhuber \(2009\)J\. SchmidhuberDriven by compression progress: a simple principle explains essential aspects of subjective beauty, novelty, surprise, interestingness, attention, curiosity, creativity, art, science, music, jokes\.InAnticipatory Behavior in Adaptive Learning Systems,G\. Pezzulo, M\. V\. Butz, O\. Sigaud, and G\. Baldassarre \(Eds\.\),Berlin, Heidelberg,pp\. 48–76\.External Links:ISBN 978\-3\-642\-02565\-5Cited by:[§5](https://arxiv.org/html/2610.20922#S5.SS0.SSS0.Px2.p2.1)\.
- Schmidhuber \(2010\)J\. SchmidhuberFormal theory of creativity, fun, and intrinsic motivation \(1990–2010\)\.IEEE Transactions on Autonomous Mental Development2\(3\),pp\. 230–247\.External Links:[Document](https://dx.doi.org/10.1109/TAMD.2010.2056368)Cited by:[§5](https://arxiv.org/html/2610.20922#S5.SS0.SSS0.Px2.p2.1)\.
- Secretanet al\.\(2008\)J\. Secretan, N\. Beato, D\. B\. D Ambrosio, A\. Rodriguez, A\. Campbell, and K\. O\. StanleyPicbreeder: evolving pictures collaboratively online\.InSIGCHI conference on human factors in computing systems,pp\. 1759–1768\.Cited by:[§D\.2](https://arxiv.org/html/2610.20922#A4.SS2.SSS0.Px6.p2.1),[§4\.2](https://arxiv.org/html/2610.20922#S4.SS2.SSS0.Px4.p2.1)\.
- Secretanet al\.\(2011\)J\. Secretan, N\. Beato, D\. B\. D’Ambrosio, A\. Rodriguez, A\. Campbell, J\. T\. Folsom\-Kovarik, and K\. O\. StanleyPicbreeder: a case study in collaborative evolutionary exploration of design space\.Evolutionary computation19\(3\),pp\. 373–403\.Cited by:[§D\.2](https://arxiv.org/html/2610.20922#A4.SS2.SSS0.Px6.p2.1),[§4\.2](https://arxiv.org/html/2610.20922#S4.SS2.SSS0.Px4.p2.1)\.
- Sharmaet al\.\(2023\)A\. Sharma, D\. Czégel, M\. Lachmann, C\. P\. Kempes, S\. I\. Walker, and L\. CroninAssembly theory explains and quantifies selection and evolution\.Nature622\(7982\),pp\. 321–328\(en\)\.External Links:ISSN 1476\-4687,[Link](https://www.nature.com/articles/s41586-023-06600-9),[Document](https://dx.doi.org/10.1038/s41586-023-06600-9)Cited by:[§3\.4](https://arxiv.org/html/2610.20922#S3.SS4.SSS0.Px5.p1.1)\.
- Socolofet al\.\(2022\)M\. Socolof, J\. H\. Vigly, R\. Futrell, A\. Sordoni, and T\. O’DonnellMeasuring morphological fusion using partial information decomposition\.In29th International Conference on Computational Linguistics,pp\. 44–54\.Cited by:[§3\.4](https://arxiv.org/html/2610.20922#S3.SS4.SSS0.Px2.p2.2)\.
- Stanley and Miikkulainen \(2002\)K\. O\. Stanley and R\. MiikkulainenEvolving neural networks through augmenting topologies\.Evolutionary computation10\(2\),pp\. 99–127\.Cited by:[§D\.2](https://arxiv.org/html/2610.20922#A4.SS2.SSS0.Px6.p2.1),[§4\.2](https://arxiv.org/html/2610.20922#S4.SS2.SSS0.Px4.p2.1)\.
- Stanley and Miikkulainen \(2004\)K\. O\. Stanley and R\. MiikkulainenCompetitive coevolution through evolutionary complexification\.Journal of artificial intelligence research21,pp\. 63–100\.Cited by:[§D\.2](https://arxiv.org/html/2610.20922#A4.SS2.SSS0.Px6.p2.1),[§4\.2](https://arxiv.org/html/2610.20922#S4.SS2.SSS0.Px4.p2.1)\.
- Stanley \(2007\)K\. O\. StanleyCompositional pattern producing networks: a novel abstraction of development\.Genetic programming and evolvable machines8\(2\),pp\. 131–162\.Cited by:[§4\.2](https://arxiv.org/html/2610.20922#S4.SS2.SSS0.Px1.p1.1),[§4\.2](https://arxiv.org/html/2610.20922#S4.SS2.SSS0.Px4.p1.1)\.
- Trageret al\.\(2023\)M\. Trager, P\. Perera, L\. Zancato, A\. Achille, P\. Bhatia, and S\. SoattoLinear spaces of meanings: compositional structures in vision\-language models\.InIEEE/CVF International Conference on Computer Vision,pp\. 15395–15404\.Cited by:[§1](https://arxiv.org/html/2610.20922#S1.p3.1)\.
- Vereshchagin and Vitányi \(2004\)N\. K\. Vereshchagin and P\. M\. VitányiKolmogorov’s structure functions and model selection\.IEEE Transactions on Information Theory50\(12\),pp\. 3265–3290\.Cited by:[§3\.4](https://arxiv.org/html/2610.20922#S3.SS4.SSS0.Px3.p1.1)\.
- Vereshchagin and Shen \(2016\)N\. Vereshchagin and A\. ShenAlgorithmic statistics: forty years later\.InComputability and Complexity: Essays Dedicated to Rodney G\. Downey on the Occasion of His 60th Birthday,pp\. 669–737\.Cited by:[§3\.1](https://arxiv.org/html/2610.20922#S3.SS1.SSS0.Px2.p5.2)\.
- Vitányi \(2006\)P\. M\. VitányiMeaningful information\.IEEE Transactions on Information Theory52\(10\),pp\. 4617–4626\.Cited by:[§3\.1](https://arxiv.org/html/2610.20922#S3.SS1.SSS0.Px2.p2.1)\.
- Weiet al\.\(2022\)J\. Wei, X\. Wang, D\. Schuurmans, M\. Bosma, F\. Xia, E\. Chi, Q\. V\. Le, D\. Zhou,et al\.Chain\-of\-thought prompting elicits reasoning in large language models\.Advances in neural information processing systems35,pp\. 24824–24837\.Cited by:[§5](https://arxiv.org/html/2610.20922#S5.SS0.SSS0.Px1.p1.1)\.
- Wiedemeret al\.\(2024\)T\. Wiedemer, J\. Brady, A\. Panfilov, A\. Juhos, M\. Bethge, and W\. BrendelProvable compositional generalization for object\-centric learning\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=7VPTUWkiDQ)Cited by:[§1](https://arxiv.org/html/2610.20922#S1.p3.1)\.
- Wiedemeret al\.\(2023\)T\. Wiedemer, P\. Mayilvahanan, M\. Bethge, and W\. BrendelCompositional generalization from first principles\.InAdvances in Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=LqOQ1uJmSx)Cited by:[§1](https://arxiv.org/html/2610.20922#S1.p3.1)\.
- Williams and Beer \(2010\)P\. L\. Williams and R\. D\. BeerNonnegative decomposition of multivariate information\.arXiv preprint arXiv:1004\.2515\.Cited by:[§3\.4](https://arxiv.org/html/2610.20922#S3.SS4.SSS0.Px2.p1.1)\.

## Appendix APractical approximation of compositional structure

The definitions in the main text are uncomputable, since they are rooted in algorithmic information theory\. In practice, however, they can be approximated using empirical compressors, model classes, learning algorithms, and minimum description length procedures\.

Estimating compositionality empirically involves three distinct difficulties:

1. 1\.K⁡\(m\)K\(m\)is uncomputable, yet is required to define the Occam’s razor modelmxm\_\{x\}in[Equation5](https://arxiv.org/html/2610.20922#S3.E5)\.
2. 2\.K⁡\(mx∣mx1,…,mxk\)K\(m\_\{x\}\\mid m\_\{x\_\{1\}\},\\dots,m\_\{x\_\{k\}\}\), which defines the amount of novel compositional structure in[Section3\.2](https://arxiv.org/html/2610.20922#S3.SS2.SSS0.Px1), is likewise uncomputable\.
3. 3\.Identifyingmxm\_\{x\}requires searching over the potentially infinite model classℳ\\mathcal\{M\}and determining that no unexamined model yields a shorter two\-part description\.

The third difficulty is distinct from evaluating the complexity of any particular candidate model\. Kolmogorov complexity is upper semicomputable: by running candidate programs in parallel and retaining the shortest description found so far, one obtains successively tighter upper bounds that eventually reach the optimal value, although there is no general way to recognize when this has occurred\.[Bédard and Bergeron \(2022\)](https://arxiv.org/html/2610.20922#bib.bib25)make the analogous observation for Kolmogorov’s structure function\. This gives the theoretical search an*anytime*interpretation: continued search can reveal better models and shorter descriptions, but it does not provide a computable certificate that the current model is optimal\. A practical MDL procedure replaces this open\-ended search with a specified model class, optimization method, and finite search budget\.

We replace the uncomputable quantities with empirical code lengths induced by practical coding schemes\. Letffdenote an empirical two\-part coding scheme used to fit models by minimum description length, together with its associated model representation and search procedure\. Letggdenote an empirical conditional coding scheme used to measure the additional cost of describing the model of the whole given the models of the parts\. These coding schemes may be specialized to the particular data modality, model class, and training procedure under consideration\.

Using the two\-part coding schemeff, the Occam’s razor modelmxm\_\{x\}is replaced by an empirical MDL model\. Let:

Lmf​\(x\):=Lmodelf​\(m\)\+Ldataf​\(x∣m\),\\displaystyle L\_\{m\}^\{f\}\(x\):=L\_\{\\mathrm\{model\}\}^\{f\}\(m\)\+L\_\{\\mathrm\{data\}\}^\{f\}\(x\\mid m\),\(16\)whereLmodelf​\(m\)L\_\{\\mathrm\{model\}\}^\{f\}\(m\)is the code length of the modelmm, andLdataf​\(x∣m\)L\_\{\\mathrm\{data\}\}^\{f\}\(x\\mid m\)is the code length of the dataxxgiven that model\. The ideal empirical minimum\-description\-length models are:

ℳf,∗​\(x\):=arg​minm∈ℳ⁡Lmf​\(x\)\.\\displaystyle\\mathcal\{M\}^\{f,\*\}\(x\):=\\argmin\_\{m\\in\\mathcal\{M\}\}L\_\{m\}^\{f\}\(x\)\.\(17\)Assuming there is a unique model inℳf,∗​\(x\)\\mathcal\{M\}^\{f,\*\}\(x\)with minimal model\-code length, define the ideal empirical Occam’s razor model by:

mxf,∗:=arg​minm∈ℳf,∗​\(x\)⁡Lmodelf​\(m\)\.\\displaystyle m\_\{x\}^\{f,\*\}:=\\argmin\_\{m\\in\\mathcal\{M\}^\{f,\*\}\(x\)\}L\_\{\\mathrm\{model\}\}^\{f\}\(m\)\.\(18\)
Thus,mxf,∗m\_\{x\}^\{f,\*\}first minimizes the total two\-part code length underffand then, among ties, minimizes the model\-description part of the code\. This is the empirical analogue of the theoretical construction in[Equation5](https://arxiv.org/html/2610.20922#S3.E5)\. In practice, a finite run of the search procedure generally returns a best\-so\-far modelmxfm\_\{x\}^\{f\}, without guaranteeing thatmxf=mxf,∗m\_\{x\}^\{f\}=m\_\{x\}^\{f,\*\}\. If the procedure retains its incumbent, increasing the search budget cannot worsen the best observed two\-part code length, although it may change both the selected model and the allocation of bits between its model and residual descriptions\.

The tie\-breaking distinction remains conceptually important even when exact ties in total code length are rare\. Depending on the coding scheme, information may be shifted between the model\-description term and the data\-given\-model term, so different models can represent different allocations of complexity even when their total description lengths are similar or identical\. Rather than explicitly solving the two\-stage optimization above, a practical implementation may use a single two\-part MDL algorithm that simultaneously accounts for model\-description length, residual code length, and the search for a suitable model\. The choice of optimizer and search budget is therefore part of the empirical procedureff\. For brevity, the main text writesmxfm\_\{x\}^\{f\}for the model returned by this procedure\.

Given the resulting empirical modelsmxf,mx1f,…,mxkfm\_\{x\}^\{f\},m\_\{x\_\{1\}\}^\{f\},\\dots,m\_\{x\_\{k\}\}^\{f\}, the corresponding empirical estimate of compositionality under the conditional coding schemeggis:

Cf,g\(x1,…,xk→x\):=Lcondg\(mxf∣mx1f,…,mxkf\),\\displaystyle C^\{f,g\}\(x\_\{1\},\\dots,x\_\{k\}\\to x\):=L\_\{\\mathrm\{cond\}\}^\{g\}\\bigl\(m\_\{x\}^\{f\}\\mid m\_\{x\_\{1\}\}^\{f\},\\dots,m\_\{x\_\{k\}\}^\{f\}\\bigr\),\(19\)whereLcondg\(⋅∣⋅\)L\_\{\\mathrm\{cond\}\}^\{g\}\(\\cdot\\mid\\cdot\)denotes the conditional code length induced bygg\. Thus,Cf,g\(x1,…,xk→x\)C^\{f,g\}\(x\_\{1\},\\dots,x\_\{k\}\\to x\)should be interpreted as a coding\-strategy\-dependent estimate of compositional structure: it measures how many additional bits are required, undergg, to describe the empirically fitted model of the whole given the empirically fitted models of the parts\.

This is not an estimate in the sense of providing formal upper or lower bounds on the underlying algorithmic\-information quantities\. Rather, it yields an operational notion of compositionality relative to a chosen pair of empirical procedures: a procedurefffor fitting two\-part MDL models through a finite search, and a procedureggfor conditionally compressing the whole\-model given the part\-models\.

## Appendix BThe maximal decomposition

In[Section3\.2](https://arxiv.org/html/2610.20922#S3.SS2.SSS0.Px2), we introduced the concept of a compositional structure profile𝒫T​\(x\):=\(CT,x​\(v\)\)v∈Int⁡\(T\)\\mathcal\{P\}\_\{T\}\(x\):=\\left\(C\_\{T,x\}\(v\)\\right\)\_\{v\\in\\mathrm\{Int\}\(T\)\}, which is defined with respect to a rooted decomposition treeTT\. We then asked whether or not a given objectxxadmits an “intrinsic”, “true”, or “canonical” decomposition that reflects its genuine compositional structure\. We conjectured that the decomposition which maximizes the sum of novel compositional structure quantities throughout the tree was a promising candidate\. Here, we provide some initial arguments that motivate this conjecture\.

Denote the sum of novel compositional structure quantities under a given decompositionTTas:

ST​\(x\):=∑v∈Int⁡\(T\)CT,x​\(v\),\\displaystyle S\_\{T\}\(x\):=\\sum\_\{v\\in\\mathrm\{Int\}\(T\)\}C\_\{T,x\}\(v\),\(20\)and define the maximal decomposition of an objectxxas:

Txmax:=arg​maxT⁡ST​\(x\)\.\\displaystyle T\_\{x\}^\{\\mathrm\{max\}\}:=\\argmax\_\{T\}S\_\{T\}\(x\)\.\(21\)
Intuitively, what the maximal tree accomplishes is that it preferentially joins objects that share novel structure and parts, which maps on to how we intuitively think about compositionality\. In contrast, if we were considering*minimal*decompositions, we would be joining objects that are either structurally identical or algorithmically independent\. At a high level, this is the strongest motivation for our conjecture\.

Second, whileSTxmax​\(x\)S\_\{T\_\{x\}^\{\\mathrm\{max\}\}\}\(x\)is lower\-bounded byK⁡\(mx\)K\(m\_\{x\}\)\(it provides*a*possible strategy for compressing the final model, but not necessarily the optimal one; see[SectionC\.2](https://arxiv.org/html/2610.20922#A3.SS2)for theorem and proof\), there are strings for whichSTxmax​\(x\)\>K⁡\(mx\)S\_\{T\_\{x\}^\{\\mathrm\{max\}\}\}\(x\)\>K\(m\_\{x\}\)\. This means thatSTxmax​\(x\)S\_\{T\_\{x\}^\{\\mathrm\{max\}\}\}\(x\)does not simply reduce to sophistication but rather quantifies something different\. It remains to be shown, theoretically and empirically, thatSTxmax​\(x\)\>K⁡\(mx\)S\_\{T\_\{x\}^\{\\mathrm\{max\}\}\}\(x\)\>K\(m\_\{x\}\)for objects we intuitively consider compositional, and conversely thatSTxmax​\(x\)≈K⁡\(mx\)S\_\{T\_\{x\}^\{\\mathrm\{max\}\}\}\(x\)\\approx K\(m\_\{x\}\)for objects we believe to be uncompositional\. In contrast, it is trivial to show that if we were to instead consider*minimal*decompositionsTxminT\_\{x\}^\{\\mathrm\{min\}\}, there would always exist a trivial solution that merges every individual bit of a string in a single join and results inSTxmin​\(x\)=K⁡\(mx\),∀xS\_\{T\_\{x\}^\{\\mathrm\{min\}\}\}\(x\)=K\(m\_\{x\}\),\\;\\forall x\(see[SectionC\.2](https://arxiv.org/html/2610.20922#A3.SS2)for theorem and proof\) — in other words, the minimal decomposition would be independent ofxxand would thus never capture its intrinsic compositional structure\.

Third, we should hope that if a string is measured to be “compositional” according to some decomposition, it remains compositional under that same decomposition when it is embedded as a*substring*within a larger structure\. If this were not the case, it would mean that the compositional structure of an object is context\-dependent, and we would not be able to say that compositionality is an intrinsic and objective property of the object\.TxmaxT\_\{x\}^\{\\mathrm\{max\}\}happens to have this property, so we can say that it is a recursively\-consistent metric\. In particular, whenever a substring occurs as a node of a maximizing tree, the subtree rooted at that node is itself a maximizing decomposition of the substring \(see[SectionC\.3](https://arxiv.org/html/2610.20922#A3.SS3)for theorem and proof\)

Fourth, considering the maximal tree solves a technical problem: why consider binary joining operations as we have primarily focused on here? Why not join triplets, or quadruplets of substrings? While this choice may seem arbitrary, it is cleanly resolved if we only consider maximal decompositions\. The reason is that the novel structure generated from joining a triplet is guaranteed to be less than or equal to what is generated from a pair of binary joining operations, where we first join two of the substrings, and then join the result with the remaining substring \(see[SectionC\.4](https://arxiv.org/html/2610.20922#A3.SS4)for theorem and proof\)\. Once again, minimal decompositions give the opposite result because they always admit a trivial solution that merges every individual bit of the string in a single join\.

## Appendix CProofs

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

###### 1Compositionality implies algorithmic mutual information\.

Adopt the notation from[Section3](https://arxiv.org/html/2610.20922#S3)\. Suppose that a conditionally novel model of the whole does not tie the separate two\-part descriptions of the parts; that is:

C\(xa,xb→x\)\>0⟹K\(mx\)\+lmx\(x\)≠K\(mxa\)\+lmxa\(xa\)\+K\(mxb\)\+lmxb\(xb\)\.\\displaystyle C\(x\_\{a\},x\_\{b\}\\to x\)\>0\\quad\\implies\\quad K\(m\_\{x\}\)\+l\_\{m\_\{x\}\}\(x\)\\neq K\(m\_\{x\_\{a\}\}\)\+l\_\{m\_\{x\_\{a\}\}\}\(x\_\{a\}\)\+K\(m\_\{x\_\{b\}\}\)\+l\_\{m\_\{x\_\{b\}\}\}\(x\_\{b\}\)\.\(22\)Then:

C\(xa,xb→x\)\>0⟹I\(xa:xb\)\>0,\\displaystyle C\(x\_\{a\},x\_\{b\}\\to x\)\>0\\implies I\(x\_\{a\}:x\_\{b\}\)\>0,\(23\)but reverse implication does not hold in general\.

Intuitively, the theorem states that novel structure appearing only when the parts are modeled jointly generally makes the whole more compressible than the parts considered separately, and therefore implies positive algorithmic mutual information\. The no\-tie assumption excludes the exceptional case in which changing to a novel model of the whole reduces the model\-description cost but increases the residual code length by exactly the same amount, leaving the total two\-part description length unchanged\. This is a mild assumption: changing the model will ordinarily change the total two\-part compression cost, whereas an exact cancellation between its model and residual components requires a precise tie\. The formal proof of the theorem follows\.

Note 2\. Technical status of the mutual information resultThe above theorem and proof below use the paper\-wide convention of suppressing additive coding terms and are therefore an idealized description\-length argument, not a literal theorem about prefix Kolmogorov complexity without further qualifications\. With full bookkeeping, combining independent descriptions, identifying an optimal two\-part code withK⁡\(x\)K\(x\), and writingK⁡\(mx∣mxa,mxb\)=0K\(m\_\{x\}\\mid m\_\{x\_\{a\}\},m\_\{x\_\{b\}\}\)=0each introduce machine\-dependent overheads; the relevant bounds may also contain logarithmic terms when lengths or boundaries must be encoded\. Moreover, becausex=\[xa,xb\]x=\[x\_\{a\},x\_\{b\}\]denotes raw concatenation, identifyingK⁡\(x\)K\(x\)with the joint complexityK⁡\(xa,xb\)K\(x\_\{a\},x\_\{b\}\)assumes that the decomposition boundary is available as side information\. Consequently, the strict testsC\>0C\>0andI\>0I\>0can be altered by the suppressed terms\. A fully rigorous variant would replace zero by significance thresholds exceeding the relevant overheads and strengthen the no\-tie assumption to require a compression margin exceeding them\. The idealized result is retained because it isolates the intended qualitative relationship: novel joint structure ordinarily yields a compression advantage, whereas mutual information can also arise merely from reusing structure already present in the parts\.

###### Proof\.

The two parts can always be compressed independently by concatenating their model descriptions and residual codes\. Becausemxm\_\{x\}is an optimal model of the whole, we have that:

K⁡\(mx\)\+lmx​\(x\)≤K⁡\(mxa\)\+lmxa​\(xa\)\+K⁡\(mxb\)\+lmxb​\(xb\)\.\\displaystyle K\(m\_\{x\}\)\+l\_\{m\_\{x\}\}\(x\)\\leq K\(m\_\{x\_\{a\}\}\)\+l\_\{m\_\{x\_\{a\}\}\}\(x\_\{a\}\)\+K\(m\_\{x\_\{b\}\}\)\+l\_\{m\_\{x\_\{b\}\}\}\(x\_\{b\}\)\.\(24\)IfC\(xa,xb→x\)\>0C\(x\_\{a\},x\_\{b\}\\to x\)\>0, the no\-tie assumption in[Equation22](https://arxiv.org/html/2610.20922#A3.E22)makes this inequality strict\. Therefore:

K⁡\(x\)\\displaystyle K\(x\)=K⁡\(mx\)\+lmx​\(x\)\\displaystyle=K\(m\_\{x\}\)\+l\_\{m\_\{x\}\}\(x\)\(25\)<K⁡\(mxa\)\+lmxa​\(xa\)\+K⁡\(mxb\)\+lmxb​\(xb\)\\displaystyle<K\(m\_\{x\_\{a\}\}\)\+l\_\{m\_\{x\_\{a\}\}\}\(x\_\{a\}\)\+K\(m\_\{x\_\{b\}\}\)\+l\_\{m\_\{x\_\{b\}\}\}\(x\_\{b\}\)\(26\)=K⁡\(xa\)\+K⁡\(xb\)\.\\displaystyle=K\(x\_\{a\}\)\+K\(x\_\{b\}\)\.\(27\)Hence:

I⁡\(xa:xb\)=K⁡\(xa\)\+K⁡\(xb\)−K⁡\(x\)\>0\.\\displaystyle I\(x\_\{a\}:x\_\{b\}\)=K\(x\_\{a\}\)\+K\(x\_\{b\}\)\-K\(x\)\>0\.\(28\)
For the reverse direction, consider a case in which the same modelmmis the Occam’s razor model ofxax\_\{a\},xbx\_\{b\}, andxx, and writec=K⁡\(m\)\>0c=K\(m\)\>0\. The whole can reuse this model description:

K⁡\(x\)\\displaystyle K\(x\)≤c\+lm​\(xa\)\+lm​\(xb\)\\displaystyle\\leq c\+l\_\{m\}\(x\_\{a\}\)\+l\_\{m\}\(x\_\{b\}\)\(29\)<2​c\+lm​\(xa\)\+lm​\(xb\)\\displaystyle<2c\+l\_\{m\}\(x\_\{a\}\)\+l\_\{m\}\(x\_\{b\}\)\(30\)=K⁡\(xa\)\+K⁡\(xb\)\.\\displaystyle=K\(x\_\{a\}\)\+K\(x\_\{b\}\)\.\(31\)ThusI⁡\(xa:xb\)\>0I\(x\_\{a\}:x\_\{b\}\)\>0\. Nevertheless, we have that:

C\(xa,xb→x\)=K\(m∣m,m\)=0\.\\displaystyle C\(x\_\{a\},x\_\{b\}\\to x\)=K\(m\\mid m,m\)=0\.\(32\)Therefore, positive algorithmic mutual information does not imply novel compositional structure\. ∎

### C\.2Proofs of the relationships betweenST​\(x\)S\_\{T\}\(x\)andK⁡\(mx\)K\(m\_\{x\}\)

This section establishes the bounds used in[AppendixB](https://arxiv.org/html/2610.20922#A2)\.[Theorem2](https://arxiv.org/html/2610.20922#Thmtheorem2)relatesST​\(x\)S\_\{T\}\(x\)toK⁡\(mx\)K\(m\_\{x\}\)for an arbitrary decomposition, accounting explicitly for the tree shape and leaf models\.[Corollaries2\.1](https://arxiv.org/html/2610.20922#Thmtheorem2.Thmcorollary1)and[2\.2](https://arxiv.org/html/2610.20922#Thmtheorem2.Thmcorollary2)show that a maximizing decomposition can be chosen with single\-bit leaves and, assuming a common empty model for individual bits, establish the corresponding lower bound on maximal compositionality\. Finally,[Corollary2\.3](https://arxiv.org/html/2610.20922#Thmtheorem2.Thmcorollary3)describes the trivial single\-join solution for complete minimal decompositions, while[Corollary2\.4](https://arxiv.org/html/2610.20922#Thmtheorem2.Thmcorollary4)shows that allowing incomplete decompositions yields a zero minimum\.

###### 2Model complexity bounds total compositionality\.

LetTTbe a finite rooted, ordered decomposition tree forxx, and suppose that the Occam’s razor modelmxvm\_\{x\_\{v\}\}is well\-defined at every nodevv\. LetτT\\tau\_\{T\}denote the unlabeled ordered tree shape, and letMleaf:=\(mxℓ\)ℓ∈Leaves⁡\(T\)M\_\{\\mathrm\{leaf\}\}:=\(m\_\{x\_\{\\ell\}\}\)\_\{\\ell\\in\\mathrm\{Leaves\}\(T\)\}list the leaf models in left\-to\-right order\. Then:

ST​\(x\)≥K⁡\(mx\)−K⁡\(τT,Mleaf\)−O⁡\(1\),\\displaystyle S\_\{T\}\(x\)\\geq K\(m\_\{x\}\)\-K\(\\tau\_\{T\},M\_\{\\mathrm\{leaf\}\}\)\-O\(1\),\(33\)where the constant is independent ofxxandTT\.

###### Proof\.

For each internal nodevvwith ordered childrenv1,…,vkvv\_\{1\},\\ldots,v\_\{k\_\{v\}\}, choose a shortest prefix programpvp\_\{v\}that outputsmxvm\_\{x\_\{v\}\}given\(mxv1,…,mxvkv\)\(m\_\{x\_\{v\_\{1\}\}\},\\ldots,m\_\{x\_\{v\_\{k\_\{v\}\}\}\}\)\. By definition,

\|pv\|=K⁡\(mxv∣mxv1,…,mxvkv\)=CT,x​\(v\)\.\\displaystyle\|p\_\{v\}\|=K\(m\_\{x\_\{v\}\}\\mid m\_\{x\_\{v\_\{1\}\}\},\\ldots,m\_\{x\_\{v\_\{k\_\{v\}\}\}\}\)=C\_\{T,x\}\(v\)\.\(34\)Construct a description consisting of a shortest prefix program for\(τT,Mleaf\)\(\\tau\_\{T\},M\_\{\\mathrm\{leaf\}\}\), followed by the programspvp\_\{v\}in postorder, so that children precede their parents\.

A fixed decoder first recovers the tree shape and leaf models\. It then processes the internal nodes in postorder, running eachpvp\_\{v\}with the already reconstructed child models as its auxiliary input\. Since the programs are prefix\-free and the tree determines their number and order, no additional delimiters are required\. At the root, the decoder outputsmxm\_\{x\}\. Consequently,

K⁡\(mx\)\\displaystyle K\(m\_\{x\}\)≤K⁡\(τT,Mleaf\)\+∑v∈Int⁡\(T\)\|pv\|\+O⁡\(1\)\\displaystyle\\leq K\(\\tau\_\{T\},M\_\{\\mathrm\{leaf\}\}\)\+\\sum\_\{v\\in\\mathrm\{Int\}\(T\)\}\|p\_\{v\}\|\+O\(1\)\(35\)=K⁡\(τT,Mleaf\)\+ST​\(x\)\+O⁡\(1\)\.\\displaystyle=K\(\\tau\_\{T\},M\_\{\\mathrm\{leaf\}\}\)\+S\_\{T\}\(x\)\+O\(1\)\.\(36\)Rearranging proves the result\. ∎

###### 2\.1Maximal decompositions can be fully refined\.

Letx∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\}, withn≥1n\\geq 1\. Consider all rooted, ordered decomposition trees ofxxwhose internal nodes have at least two children and whose nodes represent nonempty substrings\. There exists a tree maximizingST​\(x\)S\_\{T\}\(x\)whose leaves are individual bits\.

###### Proof\.

Letℓ\\ellbe a leaf of a decomposition treeTT, and letRRbe a decomposition tree ofxℓx\_\{\\ell\}\. Replacingℓ\\ellbyRRproduces a refinementT′T^\{\\prime\}satisfying

ST′​\(x\)=ST​\(x\)\+SR​\(xℓ\)≥ST​\(x\)\.\\displaystyle S\_\{T^\{\\prime\}\}\(x\)=S\_\{T\}\(x\)\+S\_\{R\}\(x\_\{\\ell\}\)\\geq S\_\{T\}\(x\)\.\(37\)Indeed, every existing internal node retains the same substring and immediate child substrings, so its score is unchanged, while all newly introduced scores are nonnegative\.

There are finitely many admissible decomposition trees, so a maximizer exists\. Starting from any maximizer, recursively split each leaf of length greater than one\. The resulting tree has individual bits as leaves and cannot have a smaller score\. Since the original tree was maximal, the refined tree is also maximal\. ∎

###### 2\.2Maximal compositionality bounds model complexity\.

Suppose that the Occam’s razor models of both one\-bit strings coincide with a fixed empty model:

m0=m1=m∅\.\\displaystyle m\_\{0\}=m\_\{1\}=m\_\{\\varnothing\}\.\(38\)For every nonempty binary stringxxof lengthnn, any maximizing decompositionTxmaxT\_\{x\}^\{\\mathrm\{max\}\}satisfies

STxmax​\(x\)≥K⁡\(mx\)−K⁡\(n\)−O⁡\(1\)\.\\displaystyle S\_\{T\_\{x\}^\{\\mathrm\{max\}\}\}\(x\)\\geq K\(m\_\{x\}\)\-K\(n\)\-O\(1\)\.\(39\)Consequently, suppressing an additiveO⁡\(log⁡\(n\+2\)\)O\(\\log\(n\+2\)\)term givesSTxmax​\(x\)≥K⁡\(mx\)S\_\{T\_\{x\}^\{\\mathrm\{max\}\}\}\(x\)\\geq K\(m\_\{x\}\)\.

###### Proof\.

LetBnB\_\{n\}be the binary decomposition obtained by recursively splitting each substring into two parts whose lengths differ by at most one, stopping at individual bits\. Its ordered tree shape is computable fromnn, and its leaf\-model tuple consists ofnncopies of the fixed modelm∅m\_\{\\varnothing\}\. Hence

K⁡\(τBn,Mleaf\)≤K⁡\(n\)\+O⁡\(1\)\.\\displaystyle K\(\\tau\_\{B\_\{n\}\},M\_\{\\mathrm\{leaf\}\}\)\\leq K\(n\)\+O\(1\)\.\(40\)Applying[Theorem2](https://arxiv.org/html/2610.20922#Thmtheorem2)gives

SBn​\(x\)≥K⁡\(mx\)−K⁡\(n\)−O⁡\(1\)\.\\displaystyle S\_\{B\_\{n\}\}\(x\)\\geq K\(m\_\{x\}\)\-K\(n\)\-O\(1\)\.\(41\)Finally, maximality impliesSTxmax​\(x\)≥SBn​\(x\)S\_\{T\_\{x\}^\{\\mathrm\{max\}\}\}\(x\)\\geq S\_\{B\_\{n\}\}\(x\), which proves the claim\. ∎

###### 2\.3Minimal complete decompositions\.

Letx∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\}, withn≥2n\\geq 2, and supposem0=m1=m∅m\_\{0\}=m\_\{1\}=m\_\{\\varnothing\}for a fixed empty model\. Let𝒯complete​\(x\)\\mathcal\{T\}\_\{\\mathrm\{complete\}\}\(x\)consist of all rooted, ordered decomposition trees with single\-bit leaves and at least two children per internal node\.

The single\-join treeT⋆T\_\{\\star\}, whose root has allnnbits as its immediate children, satisfies

ST⋆​\(x\)=K⁡\(mx∣n\)\+O⁡\(1\)\.\\displaystyle S\_\{T\_\{\\star\}\}\(x\)=K\(m\_\{x\}\\mid n\)\+O\(1\)\.\(42\)Moreover,

K⁡\(mx\)−O⁡\(n\)≤minT∈𝒯complete​\(x\)⁡ST​\(x\)≤K⁡\(mx∣n\)\+O⁡\(1\)\.\\displaystyle K\(m\_\{x\}\)\-O\(n\)\\leq\\min\_\{T\\in\\mathcal\{T\}\_\{\\mathrm\{complete\}\}\(x\)\}S\_\{T\}\(x\)\\leq K\(m\_\{x\}\\mid n\)\+O\(1\)\.\(43\)Under the convention of suppressing leaf\-description and accumulated coding terms, these bounds give

minT∈𝒯complete​\(x\)⁡ST​\(x\)=K⁡\(mx\),\\displaystyle\\min\_\{T\\in\\mathcal\{T\}\_\{\\mathrm\{complete\}\}\(x\)\}S\_\{T\}\(x\)=K\(m\_\{x\}\),\(44\)with the single\-join tree providing a trivial minimizer in this idealized accounting\.

###### Proof\.

The only internal node ofT⋆T\_\{\\star\}is its root, so

ST⋆​\(x\)=K⁡\(mx∣m∅,…,m∅⏟n​copies\)=K⁡\(mx∣n\)\+O⁡\(1\)\.\\displaystyle S\_\{T\_\{\\star\}\}\(x\)=K\\bigl\(m\_\{x\}\\mid\\underbrace\{m\_\{\\varnothing\},\\ldots,m\_\{\\varnothing\}\}\_\{n\\text\{ copies\}\}\\bigr\)=K\(m\_\{x\}\\mid n\)\+O\(1\)\.\(45\)The final equality holds because the tuple determinesnn, and converselynndetermines the tuple using the fixed modelm∅m\_\{\\varnothing\}\. This proves the upper bound\.

For the lower bound, every complete tree hasnnleaves and at mostn−1n\-1internal nodes\. Its ordered shape can therefore be encoded inO⁡\(n\)O\(n\)bits\. Since all leaf models equalm∅m\_\{\\varnothing\}, the shape also determines their tuple, giving

K⁡\(τT,Mleaf\)=O⁡\(n\)\.\\displaystyle K\(\\tau\_\{T\},M\_\{\\mathrm\{leaf\}\}\)=O\(n\)\.\(46\)By[Theorem2](https://arxiv.org/html/2610.20922#Thmtheorem2), uniformly over complete trees,

ST​\(x\)≥K⁡\(mx\)−O⁡\(n\)\.\\displaystyle S\_\{T\}\(x\)\\geq K\(m\_\{x\}\)\-O\(n\)\.\(47\)Taking the minimum proves the stated bounds\. Suppressing the indicated coding terms yields the idealized equality\. ∎

###### 2\.4Minimal unrestricted decompositions\.

If decomposition trees may terminate at arbitrary nonempty substrings, then for every nonempty stringxx,

minT⁡ST​\(x\)=0\.\\displaystyle\\min\_\{T\}S\_\{T\}\(x\)=0\.\(48\)A minimizer is the tree consisting only of the root, labelled byxx\.

###### Proof\.

The root\-only tree has no internal nodes, so its score is an empty sum and equals zero\. Every decomposition score is a sum of nonnegative conditional complexities and is therefore nonnegative\. ∎

### C\.3Recursive consistency of maximal decompositions

###### 3Recursive consistency of maximal decompositions\.

Fix the universal machine, the tuple encoding, and a uniquely selected Occam’s razor modelmym\_\{y\}for every nonempty substringyyofxx\. Let𝒯⁡\(y\)\\mathcal\{T\}\(y\)be the set of finite rooted, ordered decomposition trees ofyywhose nodes represent nonempty substrings and whose internal nodes have at least two children\. Define

Smax​\(y\):=maxR∈𝒯⁡\(y\)⁡SR​\(y\)\.\\displaystyle S^\{\\mathrm\{max\}\}\(y\):=\\max\_\{R\\in\\mathcal\{T\}\(y\)\}S\_\{R\}\(y\)\.\(49\)IfT∈𝒯⁡\(x\)T\\in\\mathcal\{T\}\(x\)maximizesST​\(x\)S\_\{T\}\(x\), then, for every nodevvofTT, the subtreeTvT\_\{v\}rooted atvvsatisfies

STv​\(xv\)=Smax​\(xv\)\.\\displaystyle S\_\{T\_\{v\}\}\(x\_\{v\}\)=S^\{\\mathrm\{max\}\}\(x\_\{v\}\)\.\(50\)Moreover, replacingTvT\_\{v\}by any maximizing decomposition ofxvx\_\{v\}produces another maximizing decomposition ofxx\.

###### Proof\.

Each set𝒯⁡\(y\)\\mathcal\{T\}\(y\)is finite and nonempty, so its maximum exists\. Fix a nodevvofTTand anyR∈𝒯⁡\(xv\)R\\in\\mathcal\{T\}\(x\_\{v\}\)\. ReplaceTvT\_\{v\}byRR, identifying the root ofRRwithvv, and denote the resulting tree byT′T^\{\\prime\}\. This is an admissible decomposition ofxx\.

Every internal node outside the replaced subtree retains the same substring and the same ordered list of immediate child substrings\. In particular, the parent ofvv, if present, still hasxvx\_\{v\}as the same child substring\. Since each model depends only on its substring, all local scores outside the replaced subtree remain unchanged\. Consequently,

ST′​\(x\)=ST​\(x\)−STv​\(xv\)\+SR​\(xv\)\.\\displaystyle S\_\{T^\{\\prime\}\}\(x\)=S\_\{T\}\(x\)\-S\_\{T\_\{v\}\}\(x\_\{v\}\)\+S\_\{R\}\(x\_\{v\}\)\.\(51\)Maximality ofTTimpliesST′​\(x\)≤ST​\(x\)S\_\{T^\{\\prime\}\}\(x\)\\leq S\_\{T\}\(x\), and henceSR​\(xv\)≤STv​\(xv\)S\_\{R\}\(x\_\{v\}\)\\leq S\_\{T\_\{v\}\}\(x\_\{v\}\)\. SinceRRwas arbitrary,TvT\_\{v\}is a maximizing decomposition ofxvx\_\{v\}\. IfRRis also maximizing, the displayed identity givesST′​\(x\)=ST​\(x\)S\_\{T^\{\\prime\}\}\(x\)=S\_\{T\}\(x\), proving the final claim\. ∎

### C\.4Binary refinement of maximal decompositions

###### 4Binary refinement of maximal decompositions\.

Fix the universal prefix machine, the tuple encoding, and a uniquely selected Occam’s razor modelmym\_\{y\}for every nonempty substringyyof a nonempty stringxx\. Let𝒯⁡\(x\)\\mathcal\{T\}\(x\)consist of the finite rooted, ordered decomposition trees ofxxwhose nodes represent nonempty substrings and whose internal nodes have at least two children\. Write

ST​\(x\)\\displaystyle S\_\{T\}\(x\):=∑v∈Int⁡\(T\)K⁡\(mxv∣mxv1,…,mxvkv\),\\displaystyle:=\\sum\_\{v\\in\\mathrm\{Int\}\(T\)\}K\(m\_\{x\_\{v\}\}\\mid m\_\{x\_\{v\_\{1\}\}\},\\ldots,m\_\{x\_\{v\_\{k\_\{v\}\}\}\}\),\(52\)N\>2​\(T\)\\displaystyle N\_\{\>2\}\(T\):=\|\{v∈Int⁡\(T\):kv\>2\}\|\.\\displaystyle:=\\bigl\|\\\{v\\in\\mathrm\{Int\}\(T\):k\_\{v\}\>2\\\}\\bigr\|\.\(53\)There is a constantc≥0c\\geq 0, independent ofxxandTT, such that everyT∈𝒯⁡\(x\)T\\in\\mathcal\{T\}\(x\)admits a binary refinementBBwith the same ordered leaves and

SB​\(x\)≥ST​\(x\)−c​N\>2​\(T\)\.\\displaystyle S\_\{B\}\(x\)\\geq S\_\{T\}\(x\)\-cN\_\{\>2\}\(T\)\.\(54\)Consequently, under the convention of suppressing these accumulated additive coding terms, a maximizing decomposition can be chosen to consist entirely of binary joins\.

###### Proof\.

First consider a single joiny=\[y1,…,yk\]y=\[y\_\{1\},\\ldots,y\_\{k\}\], wherek≥3k\\geq 3, and setzj=\[y1,…,yj\]z\_\{j\}=\[y\_\{1\},\\ldots,y\_\{j\}\]for1≤j≤k1\\leq j\\leq k\. Its left\-associated binary refinement joinszj−1z\_\{j\-1\}withyjy\_\{j\}to formzjz\_\{j\}, successively forj=2,…,kj=2,\\ldots,k\. We claim that

K⁡\(my∣my1,…,myk\)≤∑j=2kK⁡\(mzj∣mzj−1,myj\)\+c\.\\displaystyle K\(m\_\{y\}\\mid m\_\{y\_\{1\}\},\\ldots,m\_\{y\_\{k\}\}\)\\leq\\sum\_\{j=2\}^\{k\}K\(m\_\{z\_\{j\}\}\\mid m\_\{z\_\{j\-1\}\},m\_\{y\_\{j\}\}\)\+c\.\(55\)For eachjj, choose a shortest prefix programpjp\_\{j\}that outputsmzjm\_\{z\_\{j\}\}given\(mzj−1,myj\)\(m\_\{z\_\{j\-1\}\},m\_\{y\_\{j\}\}\)\. Given the tuple\(my1,…,myk\)\(m\_\{y\_\{1\}\},\\ldots,m\_\{y\_\{k\}\}\), a fixed decoder reads the concatenated programsp2⋯pkp\_\{2\}\\cdots p\_\{k\}\. It starts withmz1=my1m\_\{z\_\{1\}\}=m\_\{y\_\{1\}\}and recursively runspjp\_\{j\}with the previously recovered modelmzj−1m\_\{z\_\{j\-1\}\}and the supplied modelmyjm\_\{y\_\{j\}\}\. The final output ismzk=mym\_\{z\_\{k\}\}=m\_\{y\}\. The input tuple determineskk, and prefix\-freeness permits the programs to be parsed successively without additional delimiters\. Thus their total length, plus a fixed simulation constantcc, bounds the conditional complexity ofmym\_\{y\}, proving equation[55](https://arxiv.org/html/2610.20922#A3.E55)\. In particular,ccdoes not depend onkk\. This construction does not require computing an Occam’s razor model from its substring: each intermediate model is supplied by its corresponding program\.

Now recursively refine the original tree\. At each node with more than two children, replace its join by the left\-associated binary chain just described, preserving the original child subtrees\. The node still represents the same substring, so its parent’s score is unchanged; scores within the original child subtrees are also unchanged\. Equation[55](https://arxiv.org/html/2610.20922#A3.E55)shows that the replacement decreases the total score by at mostcc\. Nodes already having two children need no replacement\. After replacing allN\>2​\(T\)N\_\{\>2\}\(T\)nonbinary joins, the resulting treeBBis binary and has the same ordered leaves\. Summing the local bounds proves equation[54](https://arxiv.org/html/2610.20922#A3.E54)\.

There are finitely many admissible trees, so a maximizer exists\. In the idealized accounting that suppresses the indicated coding terms, refining a maximizer cannot decrease its score, and maximality prevents an increase beyond the maximum\. Its binary refinement is therefore also a maximizer in that accounting\. ∎

## Appendix DExperiment details

### D\.1Compositional strings

#### Grammar representation and codelength\.

For a substringxvx\_\{v\}, the two\-part compressor returns a grammarG=\(Ai→αi\)i=1MG=\(A\_\{i\}\\to\\alpha\_\{i\}\)\_\{i=1\}^\{M\}and a residual sequencezz\. Each right\-hand sideαi\\alpha\_\{i\}is a sequence of original symbols and rule namesAjA\_\{j\}withj<ij<i, so the rules form an acyclic hierarchy\. Recursively expanding every rule name inzzrecoversxvx\_\{v\}exactly\. The empirical modelmxvfm\_\{x\_\{v\}\}^\{f\}is the grammarGGalone;zzis the data\-given\-model component and is consequently not passed to the conditional model compressor\.

We use a shared zero\-order entropy code for the grammar and residual\. Let𝒮⁡\(G,z\)\\mathcal\{S\}\(G,z\)be the pooled stream containing every symbol on the right\-hand side of every rule, one occurrence of each rule name on its left\-hand side, and every symbol inzz\. Ifnsn\_\{s\}is the number of occurrences of symbolssin this stream andN=∑snsN=\\sum\_\{s\}n\_\{s\}, its codelength isλ⁡\(s\)=−log2⁡\(ns/N\)\\lambda\(s\)=\-\\log\_\{2\}\(n\_\{s\}/N\)\. We separate the resulting description into:

Lmodelf​\(G\)\\displaystyle L\_\{\\mathrm\{model\}\}^\{f\}\(G\)=∑i=1M\[λ⁡\(Ai\)\+∑s∈αiλ⁡\(s\)\],\\displaystyle=\\sum\_\{i=1\}^\{M\}\\left\[\\lambda\(A\_\{i\}\)\+\\sum\_\{s\\in\\alpha\_\{i\}\}\\lambda\(s\)\\right\],\(56\)Ldataf​\(xv∣G\)\\displaystyle L\_\{\\mathrm\{data\}\}^\{f\}\(x\_\{v\}\\mid G\)=∑s∈zλ⁡\(s\),\\displaystyle=\\sum\_\{s\\in z\}\\lambda\(s\),\(57\)LGf​\(xv\)\\displaystyle L^\{f\}\_\{G\}\(x\_\{v\}\)=Lmodelf​\(G\)\+Ldataf​\(xv∣G\)\.\\displaystyle=L\_\{\\mathrm\{model\}\}^\{f\}\(G\)\+L\_\{\\mathrm\{data\}\}^\{f\}\(x\_\{v\}\\mid G\)\.\(58\)Including one left\-hand\-side occurrence charges for introducing each rule, while occurrences of its name in other rules or inzzcapture the savings from reuse\. Because the empirical symbol probabilities are estimated from the pooled stream, adding a rule changes both the sequence length and all symbol codelengths; rule induction must therefore evaluate the change in the complete two\-part code rather than count replaced symbols alone\. We treat rule boundaries and the empirical distribution as part of the agreed coding convention and do not encode their additional overhead\. Thus, as in our broader empirical framework, these quantities should be interpreted as consistently applied surrogate codelengths rather than calibrated lengths of a particular binary file format\.

#### MDL grammar induction\.

Standard RePair maintains the current residual sequencezz, finds its most frequent adjacent pair of symbols, introduces a new rule for that pair, and replaces the pair’s non\-overlapping occurrences by the new rule name\([Larsson and Moffat, 2000](https://arxiv.org/html/2610.20922#bib.bib34)\)\. It repeats this process until no pair occurs twice\. For example, replacing0101byAAchanges0101001010toA​A​0AA0and adds the ruleA→01A\\to 01\. Since the symbols ofzzcan include previously introduced rule names, later replacements can build a hierarchy of rules\. Two features of standard RePair are undesirable for our purpose\. First, it discovers a long repeated substring through several pair replacements, even when one rule for the entire substring would be shorter and easier to interpret\. MR\-RePair addresses this problem by starting from a repeated pair and extending all of its occurrences to the left and right for as long as their surrounding symbols agree, then introducing a rule for the resulting longer repeat\([Furuya et al\., 2018](https://arxiv.org/html/2610.20922#bib.bib35)\)\. Second, RePair and MR\-RePair ordinarily add a rule whenever a suitable repetition exists\. They do not ask whether the saved occurrences outweigh the cost of storing the rule, and can therefore assign substantial grammars even to random strings for which the empty grammar gives a shorter two\-part code\.

Our fitter retains MR\-RePair’s long\-repeat search but chooses among its candidates by the resulting change inLGf​\(xv\)L\_\{G\}^\{f\}\(x\_\{v\}\);[Algorithm1](https://arxiv.org/html/2610.20922#alg1)gives the complete procedure\. At each iteration, it considers every distinct adjacent pair with at least two non\-overlapping occurrences inzz\. For one such pair, it collects all of the pair’s occurrences and extends them simultaneously: it prepends a symbol only if the same symbol appears immediately before every occurrence, and appends a symbol only if the same symbol appears immediately after every occurrence\. This continues until neither extension is possible\. The result is maximal relative to this set of occurrences; it need not be the longest repeat anywhere inzz\. As in MR\-RePair, if the result has length greater than two and its first and last symbols are equal, we remove its final symbol\. This boundary adjustment prevents shifted, self\-overlapping copies from inducing inconsistent replacements\. We then greedily retain the leftmost possible non\-overlapping occurrences\. If at least two remain, the resulting patternqqbecomes a candidate right\-hand side for a new ruleA→qA\\to q\. Its exact gain is

Δ\(q\)=LGf\(xv\)−LG∪\{A→q\}f\(xv\),\\displaystyle\\Delta\(q\)=L\_\{G\}^\{f\}\(x\_\{v\}\)\-L\_\{G\\cup\\\{A\\to q\\\}\}^\{f\}\(x\_\{v\}\),\(59\)where the second term is evaluated after replacing those occurrences byAA\. The selected candidate is the one with greatest gain, and a rule is added only if this gain is positive\. Thus, every accepted step strictly shortens the surrogate two\-part code\.

More concretely, the pooled entropy length can be written asN​log2​N−∑sns​log2​nsN\\log\_\{2\}N\-\\sum\_\{s\}n\_\{s\}\\log\_\{2\}n\_\{s\}\. If a candidateqqhas lengthmm, contains symbolssexactlycs​\(q\)c\_\{s\}\(q\)times, and is replaced atkknon\-overlapping occurrences, then introducing its new rule nameAAgives:

N′\\displaystyle N^\{\\prime\}=N\+\(m\+1\)−k⁡\(m−1\),\\displaystyle=N\+\(m\+1\)\-k\(m\-1\),\(60\)ns′\\displaystyle n\_\{s\}^\{\\prime\}=ns−\(k−1\)​cs​\(q\),nA′=k\+1\.\\displaystyle=n\_\{s\}\-\(k\-1\)c\_\{s\}\(q\),\\qquad n\_\{A\}^\{\\prime\}=k\+1\.\(61\)Themmright\-hand\-side symbols and one left\-hand\-side occurrence account for them\+1m\+1added model symbols, while replacingkkcopies of anmm\-symbol pattern bykkrule names accounts for the residual reduction\. Substituting these counts into the entropy expression yieldsΔ⁡\(q\)\\Delta\(q\)without rebuilding the candidate grammar\.

The pair\-extension procedure has an important blind spot\. It extends a pair only while*all*occurrences of that pair have the same neighbouring symbols\. Suppose, for example, that several copies of a long pattern contain the pair0101, but0101also occurs elsewhere in unrelated contexts\. Those extra occurrences can stop the simultaneous extension immediately, even though the subset inside the long pattern would yield a valuable rule\. We therefore supplement the local pair search with a global repeat search based on a suffix array\. This second search can isolate a subset of starting positions that share a long pattern\.

A*substring*is any contiguous segment of a sequence\. A*prefix*is a substring that begins at the first position, while the suffix beginning at positioniiis the substringzi,zi\+1,…z\_\{i\},z\_\{i\+1\},\\ldotsthat runs fromiito the end\. The suffix array does not store these suffixes themselves: it stores their starting positions, ordered so that the corresponding suffixes are in lexicographic, or dictionary, order\. For example, the suffixes ofz=𝚌𝚊𝚋𝚍𝚊𝚋z=\\mathtt\{cabdab\}, shown in sorted order, are

𝚊𝚋\(5\),𝚊𝚋𝚍𝚊𝚋\(2\),𝚋\(6\),𝚋𝚍𝚊𝚋\(3\),𝚌𝚊𝚋𝚍𝚊𝚋\(1\),𝚍𝚊𝚋\(4\),\\displaystyle\\mathtt\{ab\}\_\{\(5\)\},\\quad\\mathtt\{abdab\}\_\{\(2\)\},\\quad\\mathtt\{b\}\_\{\(6\)\},\\quad\\mathtt\{bdab\}\_\{\(3\)\},\\quad\\mathtt\{cabdab\}\_\{\(1\)\},\\quad\\mathtt\{dab\}\_\{\(4\)\},\(62\)where each subscript is the suffix’s starting position inzz\. The suffix array is therefore\(5,2,6,3,1,4\)\(5,2,6,3,1,4\)\. Its first two suffixes begin with the same length\-two prefix𝚊𝚋\\mathtt\{ab\}, revealing occurrences of𝚊𝚋\\mathtt\{ab\}at positions22and55\. More generally, suffixes with a long shared prefix become neighbours in this ordering, even if other occurrences of the prefix’s shorter symbol pairs appear elsewhere inzz\.

We summarize this shared\-prefix information with a longest\-common\-prefix \(LCP\) array\. For each suffix after the first in sorted order, its LCP value is the number of initial symbols it shares with the preceding suffix\. A block ofrrconsecutive suffixes for which ther−1r\-1intervening LCP values are all at leasthhrepresentsrroccurrences of the same length\-hhsubstring\. We enumerate the maximal such blocks at the prefix lengths present in the LCP array; these are the*LCP intervals*in[Algorithm2](https://arxiv.org/html/2610.20922#alg2)\. An interval is only a quick proposal, since its occurrences may overlap and replacing overlapping copies is impossible\. We rank an interval containingrrsuffixes with shared\-prefix lengthhhbyh⁡\(r−1\)h\(r\-1\), which approximates the number of repeated symbols beyond the first copy\. This ranking is used only to decide which proposals receive further evaluation, not to accept a grammar rule\.

For each retained interval, we truncate its shared prefix to the maximum permitted rule length and use that prefix as the candidate patternqq\. We then search the entire residual for every exact occurrence ofqq, rather than using only the starting positions in the interval\. Scanning from left to right, we keep an occurrence whenever it begins after the preceding retained occurrence ends; because all occurrences have equal length, this produces a maximum\-cardinality non\-overlapping set\. Patterns with fewer than two retained occurrences are discarded, and duplicate patterns proposed by different intervals are evaluated only once\. Every surviving suffix\-array pattern is finally scored with the same exact MDL gainΔ⁡\(q\)\\Delta\(q\)as every pair\-derived pattern\.

Algorithm 1MDL\-guided maximal\-repeat grammar inductionInput:String

xx; suffix\-search interval

τ\\tau; suffix parameters

θSA=\(ℓmin,ℓmax,KSA,ρ,I0\)\\theta\_\{\\mathrm\{SA\}\}=\(\\ell\_\{\\min\},\\ell\_\{\\max\},K\_\{\\mathrm\{SA\}\},\\rho,I\_\{0\}\)
G←∅G\\leftarrow\\varnothing,

z←xz\\leftarrow x, and

r←0r\\leftarrow 0;

while*true*do

𝒞←\\mathcal\{C\}\\leftarrowmaximal\-repeat candidates obtained from every repeated pair;

if*KSA\>0K\_\{\\mathrm\{SA\}\}\>0and either𝒞\\mathcal\{C\}has no positive\-gain candidate or\[τ\>0\[\\tau\>0and\(r\+1\)modτ=0\]\(r\+1\)\\bmod\\tau=0\]*then

𝒞←𝒞∪SuffixCandidates⁡\(z;θSA\)\\mathcal\{C\}\\leftarrow\\mathcal\{C\}\\cup\\operatorname\{SuffixCandidates\}\(z;\\theta\_\{\\mathrm\{SA\}\}\)using[Algorithm2](https://arxiv.org/html/2610.20922#alg2);

end if

if*𝒞=∅\\mathcal\{C\}=\\varnothing*then

break;

end if

q⋆←arg⁡maxq∈𝒞⁡Δ⁡\(q\)q^\{\\star\}\\leftarrow\\arg\\max\_\{q\\in\\mathcal\{C\}\}\\Delta\(q\);

if*Δ⁡\(q⋆\)≤0\\Delta\(q^\{\\star\}\)\\leq 0*then

break;

end if

Add

A→q⋆A\\to q^\{\\star\}to

GGand replace the non\-overlapping occurrences of

q⋆q^\{\\star\}in

zzby

AA;

r←r\+1r\\leftarrow r\+1;

end while

return

GGand

zz;

Algorithm 2Suffix\-array repeat candidatesInput:Residual

zz; length bounds

ℓmin,ℓmax\\ell\_\{\\min\},\\ell\_\{\\max\}; base interval budget

KSAK\_\{\\mathrm\{SA\}\}; oversampling factor

ρ\\rho; minimum interval pool

I0I\_\{0\}
Output:A set of repeated\-pattern candidates

𝒞SA\\mathcal\{C\}\_\{\\mathrm\{SA\}\}
SA←\\mathrm\{SA\}\\leftarrowstarting positions of all suffixes of

zz, sorted lexicographically;

LCP←\\mathrm\{LCP\}\\leftarrowlongest\-common\-prefix lengths of adjacent suffixes in

SA\\mathrm\{SA\};

B←max⁡\{ρ​KSA,I0\}B\\leftarrow\\max\\\{\\rho K\_\{\\mathrm\{SA\}\},I\_\{0\}\\\};

Enumerate maximal LCP intervals with common\-prefix length

h≥ℓminh\\geq\\ell\_\{\\min\}and rank each interval containing

rrsuffixes by

h⁡\(r−1\)h\(r\-1\);

ℐ←\\mathcal\{I\}\\leftarrowthe

BBhighest\-ranked intervals;

𝒞SA←∅\\mathcal\{C\}\_\{\\mathrm\{SA\}\}\\leftarrow\\varnothing;

foreach*I∈ℐI\\in\\mathcal\{I\}, in decreasing score order*do

m←min⁡\{hI,ℓmax\}m\\leftarrow\\min\\\{h\_\{I\},\\ell\_\{\\max\}\\\}and

q←q\\leftarrowthe length\-

mmprefix represented by

II;

if*qqhas not already been examined*then

Find every exact occurrence of

qqin

zzand greedily retain a left\-to\-right non\-overlapping subset;

if*at least two non\-overlapping occurrences remain*then

Add

qqand its occurrence spans to

𝒞SA\\mathcal\{C\}\_\{\\mathrm\{SA\}\};

end if

end if

end foreach

return

𝒞SA\\mathcal\{C\}\_\{\\mathrm\{SA\}\};

The interval pool in[Algorithm2](https://arxiv.org/html/2610.20922#alg2)is deliberately larger thanKSAK\_\{\\mathrm\{SA\}\}: different high\-ranked intervals can collapse to the same pattern after truncation, and other patterns fail the non\-overlap test\. Accordingly,KSAK\_\{\\mathrm\{SA\}\}sets the scale of the search rather than imposing a hard cap on its output\. The routine can return as many asBBdistinct patterns when all retained intervals survive, and every returned pattern is evaluated exactly before a rule is accepted\.

Constructing and sorting the suffix array, computing the LCP values, and matching the retained patterns against all ofzzis more expensive than updating the local pair index\. We therefore invoke the global search only on iterations selected byτ\\tau, or whenever the pair\-derived candidates have no positive gain\. The scheduled calls allow global candidates to compete before the local search stalls, while the fallback call prevents the pair\-extension blind spot from terminating induction prematurely\.

For the reported experiment, we setτ=4\\tau=4,ℓmin=2\\ell\_\{\\min\}=2,ℓmax=128\\ell\_\{\\max\}=128,KSA=24K\_\{\\mathrm\{SA\}\}=24,ρ=8\\rho=8, andI0=16I\_\{0\}=16\. Ties between equal\-gain candidates are resolved by the earliest occurrence in the residual\.

#### Conditional model compression\.

At a binary joinxv=\[xa,xb\]x\_\{v\}=\[x\_\{a\},x\_\{b\}\], the conditional compressor receives the grammarGGfitted to the combined substring and the two grammarsGa,GbG\_\{a\},G\_\{b\}fitted independently to its parts\. It does not receive their residual sequences: the target quantity is the cost of describing the modelmxvm\_\{x\_\{v\}\}given the part models, not the cost of reconstructingxvx\_\{v\}\. Operationally, the compressor tries to describe each rule ofGGas either a copy of, a modification of, or an addition to the rules already available inGaG\_\{a\}andGbG\_\{b\}\. A copied rule should cost zero, a modified rule should cost according to the changed symbols, and a genuinely new rule should be charged in full\.

The first problem is determining which rules correspond\. Rule names are arbitrary identifiers: for example, the two grammars\(A→01,B→AA\)\(A\\to 01,B\\to AA\)and\(C→01,D→CC\)\(C\\to 01,D\\to CC\)have the same structure even though their names differ\. Directly comparing their serialized symbol sequences would incorrectly charge for this relabelling\. We therefore seek a consistent relabelling of each part grammar, meaning that we both reorder its rule definitions and replace every reference to an old rule name by the corresponding new name\. Only after this alignment do we compare rule contents\.

To handle grammars with different numbers and lengths of rules, we place them in arrays with a common number of rows and columns and fill unused rows and positions with a distinguished padding symbol\. When this common number of rule rows is at most66, we can try every possible relabelling of a part grammar and retain the one with the smallest symbolic difference fromGG\. This exhaustive procedure compares the actual rules and therefore finds the minimum\-cost relabelling under the difference measure defined below\.

For larger grammars, trying every relabelling is infeasible because the number of permutations grows factorially\. We instead give each rule a fixed\-length numerical descriptor, or*embedding*, constructed from its terminal symbols, their positions, and the rules that it references\. These features depend on the rule’s role in the grammar rather than its integer name\. Rules with similar descriptors can then be treated as candidate counterparts\.

Mechanistically, each rule is represented by a6464\-dimensional vector\. Every terminal symbol is assigned a fixed random vector generated with seed00and shared across all three grammars\. At initialization, a reference to another rule contributes no content beyond its position, so a rule’s descriptor summarizes its terminals and overall layout\. We then refine all rule descriptors simultaneously for three rounds\. In each round, every rule reference is replaced by the preceding\-round descriptor of the referenced rule before the enclosing rule is summarized again\. One round therefore incorporates the contents of directly referenced rules, and successive rounds incorporate progressively deeper nested structure\. This procedure is analogous to Weisfeiler–Lehman refinement\([Leman and Weisfeiler, 1968](https://arxiv.org/html/2610.20922#bib.bib37)\), and a consistent relabelling of rule names leaves the resulting descriptors unchanged\.

Because a rule’s right\-hand side is an ordered sequence, we add a sinusoidal position vector to the vector at each symbol position\. Before averaging the position vectors into one descriptor for the rule, we replace the vectoruku\_\{k\}at positionkkby0\.25​uk−1\+0\.5​uk\+0\.25​uk\+10\.25u\_\{k\-1\}\+0\.5u\_\{k\}\+0\.25u\_\{k\+1\}, repeating the endpoint vector when a neighbour lies beyond the rule boundary\. This local smoothing makes the descriptor less sensitive to a one\-position displacement caused by a small insertion or deletion\. We compute the squared Euclidean distance between every rule descriptor inGGand every descriptor in a part grammar, then use the Hungarian assignment algorithm to find the one\-to\-one correspondence with minimum total descriptor distance\. This is only a tractable heuristic for choosing a relabelling: the final conditional score is computed from the aligned symbolic rules, not from their embedding distances\.

Letαj\\alpha\_\{j\}be a right\-hand side inGGand letα~i​j\\widetilde\{\\alpha\}\_\{ij\}be the rule aligned to it from part grammarGiG\_\{i\}\. Once the alignment is fixed, we charge the same number of bits for every terminal or rule reference on a right\-hand side:

b=log2⁡max⁡\{1,M\+\|ΣG\|\},\\displaystyle b=\\log\_\{2\}\\max\\left\\\{1,M\+\|\\Sigma\_\{G\}\|\\right\\\},\(63\)whereMMis the number of rules inGGandΣG\\Sigma\_\{G\}is the set of distinct terminal symbols appearing in it\. Thus,M\+\|ΣG\|M\+\|\\Sigma\_\{G\}\|is the number of symbol types that may need to be named in the target grammar\. The name on the left\-hand side of a rule is implicit in its aligned row, so we charge only for symbols on right\-hand sides\. To avoid treating a short insertion at the beginning or end as a change to every subsequent position, we compare each pair of rules under several relative shifts:

d⁡\(α,β\)=b​minδ∈\{−S,…,S\}​dH​\(padS⁡\(α\),shiftδ⁡\(padS⁡\(β\)\)\),S=10,\\displaystyle d\(\\alpha,\\beta\)=b\\min\_\{\\delta\\in\\\{\-S,\\ldots,S\\\}\}d\_\{\\mathrm\{H\}\}\\\!\\left\(\\operatorname\{pad\}\_\{S\}\(\\alpha\),\\operatorname\{shift\}\_\{\\delta\}\(\\operatorname\{pad\}\_\{S\}\(\\beta\)\)\\right\),\\qquad S=10,\(64\)where padding adds empty positions at both ends,shiftδ\\operatorname\{shift\}\_\{\\delta\}moves the second padded rule byδ\\deltapositions, and the Hamming distancedHd\_\{\\mathrm\{H\}\}simply counts positions containing different symbols\. We select the cheapest shift from−10\-10to1010and multiply its mismatch count bybb\. Identical aligned rules therefore cost zero\. Comparing a rule with an entirely empty row costsb​\|α\|b\|\\alpha\|, the same as writing every symbol ofα\\alphadirectly\. After aligning each part grammar separately, each rule of the combined grammar independently chooses among three descriptions: write it directly, describe its differences from the aligned rule inGaG\_\{a\}, or describe its differences from the aligned rule inGbG\_\{b\}:

Lcondg​\(G∣Ga,Gb\)=∑j=1Mmin⁡\{b​\|αj\|,d⁡\(αj,α~a​j\),d⁡\(αj,α~b​j\)\}\.\\displaystyle L\_\{\\mathrm\{cond\}\}^\{g\}\(G\\mid G\_\{a\},G\_\{b\}\)=\\sum\_\{j=1\}^\{M\}\\min\\left\\\{b\|\\alpha\_\{j\}\|,d\(\\alpha\_\{j\},\\widetilde\{\\alpha\}\_\{aj\}\),d\(\\alpha\_\{j\},\\widetilde\{\\alpha\}\_\{bj\}\)\\right\\\}\.\(65\)
Algorithm 3Conditional compression of a combined grammarInput:Combined grammar

GG; part grammars

Ga,GbG\_\{a\},G\_\{b\}; exact\-alignment threshold

MexactM\_\{\\mathrm\{exact\}\}
Pad all grammars to a common shape and compute

bb;

foreach*i∈\{a,b\}i\\in\\\{a,b\\\}*do

if*the padded grammars have at mostMexactM\_\{\\mathrm\{exact\}\}rules*then

Find the minimum\-difference relabelling of

GiG\_\{i\}by exhaustive permutation;

else

Embed the rules, then find a one\-to\-one alignment using Hungarian assignment;

end if

end foreach

foreach*ruleαj\\alpha\_\{j\}inGG*do

cj←min⁡\{b​\|αj\|,d⁡\(αj,α~a​j\),d⁡\(αj,α~b​j\)\}c\_\{j\}\\leftarrow\\min\\\{b\|\\alpha\_\{j\}\|,d\(\\alpha\_\{j\},\\widetilde\{\\alpha\}\_\{aj\}\),d\(\\alpha\_\{j\},\\widetilde\{\\alpha\}\_\{bj\}\)\\\};

end foreach

return

min⁡\{b​∑j\|αj\|,∑jcj\}\\min\\\{b\\sum\_\{j\}\|\\alpha\_\{j\}\|,\\sum\_\{j\}c\_\{j\}\\\};

This design targets three desired behaviours\. First, exact alignment assigns zero cost to a grammar conditioned on an isomorphic relabelling of itself\. Second, if the combined grammar is a union of rules inherited from the two parts, the per\-rule minimum permits each rule to select the part from which it came and therefore permits a zero total cost\. Third, small changes to an inherited rule are charged in proportion to their symbolic differences, while a genuinely unmatched rule pays its full raw cost\. We use the difference\-based strategy described above, with exhaustive alignment threshold66, maximum shift1010, embedding dimension6464, and three message\-passing rounds\.

This procedure is intentionally an operational approximation to conditional model complexity, not a complete lossless coding protocol\. In particular, the inferred alignment is not transmitted separately, the rule boundaries are treated as known, and the fixed per\-symbol cost is only a relative complexity scale\. These choices remove arbitrary rule identities and focus the score on structural differences between grammars, which is the property needed by the reward\.

#### Decomposition and reward\.

The balanced decomposition contains3232,1616,88,44,22, and11substrings of lengths44,88,1616,3232,6464, and128128, respectively\. Evaluating one candidate therefore fits6363grammars and computes the conditional cost at each of the3131binary joins\. Conditional costs are divided by the length of the combined substring, averaged over the1616,88,44,22, and11joins at their respective scales, and aggregated with thep=0\.75p=0\.75power mean given in the main text\.

#### Optimization\.

We implemented the evolutionary search withpymoo\([Blank and Deb, 2020](https://arxiv.org/html/2610.20922#bib.bib38)\), using NSGA\-II\([Deb et al\., 2002](https://arxiv.org/html/2610.20922#bib.bib36)\)with a single objective equal to the negative reward\. Although NSGA\-II is formulated for multi\-objective optimization, in this setting its tournament selection and parent–offspring survival reduce to an elitist genetic search over a scalar score; we refer readers to the original work for details of ranking and survival\.

The initial population contains10,00010\{,\}000strings sampled independently and uniformly from the eight\-symbol vocabulary\. Each generation produces5,0005\{,\}000offspring\. Selected parent pairs undergo two\-point crossover with probability0\.90\.9\. Mutation is then applied to every offspring: each of its128128positions is independently selected with probability2/1282/128, and a selected position is reset to a uniformly sampled vocabulary symbol, possibly the symbol already present\. Thus, each offspring has two attempted symbol resets in expectation\. Duplicate strings are eliminated\. Parents and offspring are scored, and NSGA\-II retains an elite population of10,00010\{,\}000strings for the next generation\.

#### Additional results\.

[FigureD\.1](https://arxiv.org/html/2610.20922#A4.F1)shows the dot plot of the top\-reward string for all1010seeds after optimizing both the compositionality and structure rewards\. Methods for dot plot generation and its interpretation are described in the main text\.

![Refer to caption](https://arxiv.org/html/2610.20922v1/generated_string_dot_all.png)Figure D\.1:Dot plots for all seeds\.Compositionality\-optimized strings haveblueborders, and structure\-optimized strings haveorangeborders\.

### D\.2Compositional images

#### Coordinate\-network model\.

For every patchxv∈\{0,…,3\}H×W×3x\_\{v\}\\in\\\{0,\\ldots,3\\\}^\{H\\times W\\times 3\}, the two\-part compressor fits a separate probabilistic coordinate network\. Letui​j∈\[−1,1\]2u\_\{ij\}\\in\[\-1,1\]^\{2\}be the coordinate of pixel\(i,j\)\(i,j\), normalized within the patch so that its two axes span\[−1,1\]\[\-1,1\]\. The network outputs1212real\-valued scores, or logits, arranged as four logits for each of the three channels, and thereby defines a categorical distributionqθ,c\(⋅∣ui​j\)q\_\{\\theta,c\}\(\\cdot\\mid u\_\{ij\}\)for channelcc\. Its likelihood factorizes over coordinates and channels:

qθ​\(xv\)=∏i=1H∏j=1W∏c=13qθ,c​\(xv,i​j​c∣ui​j\)\.\\displaystyle q\_\{\\theta\}\(x\_\{v\}\)=\\prod\_\{i=1\}^\{H\}\\prod\_\{j=1\}^\{W\}\\prod\_\{c=1\}^\{3\}q\_\{\\theta,c\}\(x\_\{v,ijc\}\\mid u\_\{ij\}\)\.\(66\)This factorization does not make pixels independent in the model’s description: the same parameters determine the distribution at every coordinate, so spatially related pixels can share structure through the network\.

The network has three hidden layers\. Each layer contains four groups of3232units, to which we respectively apply the functionszz,σ⁡\(5​z\)\\sigma\(5z\),tanh⁡\(2\.5​z\)\\tanh\(2\.5z\), andexp⁡\(−5​z2\)\\exp\(\-5z^\{2\}\)\. Concatenating the four groups gives a hidden width of128128\. The mixture of monotone, saturating, and localized nonlinearities is standard for CPPNs and gives a small fixed architecture several biases for representing smooth regions, boundaries, symmetries, and repeated spatial patterns\.

Alongside this spatial model, we fit a coordinate\-independent baselineq0q\_\{0\}\. For each channelcc,q0,cq\_\{0,c\}is its empirical categorical distribution in the training pixels, with an additive pseudocount of10−310^\{\-3\}for each intensity\. This baseline can encode colour frequencies but no relationship between a value and its position\. We assign it zero model complexity, making it the empty\-model analogue against which learned spatial structure must justify itself\.

#### Training and model selection\.

We randomly divide the spatial coordinates of each patch equally into training and validation sets\. The coordinate network is trained only on the training half by minimizing mean categorical cross\-entropy over coordinates and channels\. We use full\-batch AdamW with initial learning rate4×10−34\\times 10^\{\-3\}, weight decay10−410^\{\-4\}, gradient\-norm clipping at11, and cosine annealing to4×10−44\\times 10^\{\-4\}\. Training runs for at most250250gradient steps\. We evaluate after the first step and every five steps thereafter, retain the checkpoint with the lowest validation cross\-entropy, and stop after at least1010steps once eight consecutive evaluations fail to improve validation loss by at least10−410^\{\-4\}bits per symbol\.

Held\-out selection serves two roles\. First, early stopping restricts how much pixel\-level detail the network can memorize\. Second, we compare the selected checkpoint with the constant baseline on validation coordinates\. We retain the coordinate network only if it reduces validation loss by at least0\.020\.02bits per symbol and by at least2%2\\%relative to the baseline; otherwise, the empirical modelmxvfm\_\{x\_\{v\}\}^\{f\}is the constant model\. These margins prevent random fluctuations from turning weak coordinate dependence into apparent structure\. Network initialization and the train–validation division are resampled when a patch model is fitted\.

#### Two\-part complexity estimates\.

Letℓr\\ell\_\{r\}be the training cross\-entropy in bits per pixel\-channel at evaluationrr, and letsrs\_\{r\}be the cumulative number of training coordinates processed by that point\. Ifr⋆r^\{\\star\}is the validation\-selected checkpoint, writeℓ⋆=ℓr⋆\\ell\_\{\\star\}=\\ell\_\{r^\{\\star\}\}ands⋆=sr⋆s\_\{\\star\}=s\_\{r^\{\\star\}\}\. We estimate the model\-description term by the trapezoidal approximation to:

L^modelf​\(qθ\)=3​∫0s⋆\[ℓ⁡\(s\)−ℓ⋆\]\+​𝑑s,\\displaystyle\\widehat\{L\}\_\{\\mathrm\{model\}\}^\{f\}\(q\_\{\\theta\}\)=3\\int\_\{0\}^\{s\_\{\\star\}\}\\left\[\\ell\(s\)\-\\ell\_\{\\star\}\\right\]\_\{\+\}\\,\\mathrm\{d\}s,\(67\)whereℓ⁡\(s\)\\ell\(s\)linearly interpolates the recorded training losses and\[a\]\+=max⁡\{a,0\}\[a\]\_\{\+\}=\\max\\\{a,0\\\}\. The factor33converts coordinates seen into channel symbols seen\. Intuitively,ℓ⁡\(s\)−ℓ⋆\\ell\(s\)\-\\ell\_\{\\star\}removes the uncertainty that remains even after the selected model has been learned; the remaining excess is the predictive cost paid because its structure has not yet been absorbed by the weights\. Integrating this excess over learning gives a cheap learning\-curve proxy for the information acquired by the network\. This follows the same principle as online, or prequential, estimates of neural\-network description length, which accumulate predictive codelength as training examples become available sequentially\([Blier and Ollivier, 2018](https://arxiv.org/html/2610.20922#bib.bib39)\), and the computationally inexpensive learning\-complexity proxy used by Epiplexity\([Finzi et al\., 2026](https://arxiv.org/html/2610.20922#bib.bib33)\)\.

The model\-to\-data term is the selected model’s negative log\-likelihood on the complete patch, including both the training and held\-out coordinates:

L^dataf\(xv∣q\)=−∑i,j,clog2qc\(xv,i​j​c∣ui​j\)\.\\displaystyle\\widehat\{L\}\_\{\\mathrm\{data\}\}^\{f\}\(x\_\{v\}\\mid q\)=\-\\sum\_\{i,j,c\}\\log\_\{2\}q\_\{c\}\(x\_\{v,ijc\}\\mid u\_\{ij\}\)\.\(68\)If the constant baseline is selected, we setL^modelf​\(q0\)=0\\widehat\{L\}\_\{\\mathrm\{model\}\}^\{f\}\(q\_\{0\}\)=0and use its full\-patch negative log\-likelihood in[Equation68](https://arxiv.org/html/2610.20922#A4.E68)\. Otherwise, the two\-part length is the sum of[Equations67](https://arxiv.org/html/2610.20922#A4.E67)and[68](https://arxiv.org/html/2610.20922#A4.E68)\.

Unlike a true prequential/online code,[Equation67](https://arxiv.org/html/2610.20922#A4.E67)does not directly estimate the actual codelength of the final weights\. We use it as a cheap and consistently applied surrogate expected to increase with the amount of learnable structure stored in the network\. The validation split, constant fallback, and residual likelihood are therefore essential complements: they prevent a network from receiving structural credit merely for taking a long time to memorize noise\.[Algorithm4](https://arxiv.org/html/2610.20922#alg4)summarizes the complete procedure\.

Algorithm 4Neural two\-part compression of an image patchInput:Patch

xvx\_\{v\}and normalized coordinates

\{ui​j\}\\\{u\_\{ij\}\\\}
Randomly split the coordinates equally into training set

ItrI\_\{\\mathrm\{tr\}\}and validation set

IvalI\_\{\\mathrm\{val\}\};

Fit the coordinate\-independent channel marginals

q0q\_\{0\}on

ItrI\_\{\\mathrm\{tr\}\};

Randomly initialize the fixed coordinate network

qθq\_\{\\theta\};

for*t=1,…,tmaxt=1,\\ldots,t\_\{\\text\{max\}\}*do

Update

θ\\thetaon the full training set using AdamW;

At scheduled evaluations, record

\(st,ℓt\)\(s\_\{t\},\\ell\_\{t\}\)and the validation loss, and save the best checkpoint;

Stop if the validation patience criterion is met;

end for

Restore the validation\-selected checkpoint

qθ⋆q\_\{\\theta^\{\\star\}\};

if*qθ⋆q\_\{\\theta^\{\\star\}\}improves onq0q\_\{0\}by both validation margins*then

q←qθ⋆q\\leftarrow q\_\{\\theta^\{\\star\}\}and compute

L^modelf​\(q\)\\widehat\{L\}\_\{\\mathrm\{model\}\}^\{f\}\(q\)using[Equation67](https://arxiv.org/html/2610.20922#A4.E67);

else

q←q0q\\leftarrow q\_\{0\}and

L^modelf​\(q\)←0\\widehat\{L\}\_\{\\mathrm\{model\}\}^\{f\}\(q\)\\leftarrow 0;

end if

Compute

L^dataf​\(xv∣q\)\\widehat\{L\}\_\{\\mathrm\{data\}\}^\{f\}\(x\_\{v\}\\mid q\)on every coordinate using[Equation68](https://arxiv.org/html/2610.20922#A4.E68);

return

mxvf=qm\_\{x\_\{v\}\}^\{f\}=q,

L^modelf​\(q\)\\widehat\{L\}\_\{\\mathrm\{model\}\}^\{f\}\(q\), and

L^dataf​\(xv∣q\)\\widehat\{L\}\_\{\\mathrm\{data\}\}^\{f\}\(x\_\{v\}\\mid q\);

#### Conditional model compression\.

At each quadtree join, the target model is the networkqvq\_\{v\}fitted to the parent patch, while the four given modelsq1,…,q4q\_\{1\},\\ldots,q\_\{4\}were fitted independently to its quadrants\. Direct parameter comparison would be arbitrary: hidden units can be permuted, rescaled, or otherwise reparameterized without changing the represented function\. We instead ask how much function\-level adaptation is required to turn the children into the parent\.

We first construct an unadapted*routed student*\. Every coordinate in the parent is assigned to its quadranta⁡\(i,j\)∈\{1,…,4\}a\(i,j\)\\in\\\{1,\\ldots,4\\\}and converted to that quadrant’s local normalized coordinatesu~i​j\\widetilde\{u\}\_\{ij\}\. The student’s prediction is:

qS\(0\)\(⋅∣ui​j\)=qa⁡\(i,j\)\(⋅∣u~i​j\)\.\\displaystyle q\_\{S\}^\{\(0\)\}\(\\cdot\\mid u\_\{ij\}\)=q\_\{a\(i,j\)\}\(\\cdot\\mid\\widetilde\{u\}\_\{ij\}\)\.\(69\)Thus,qS\(0\)q\_\{S\}^\{\(0\)\}represents the null hypothesis that the model of the parent is only a spatial juxtaposition of the four child models\. No new routing parameters are learned or charged: the quadrant routing is fixed by the decomposition tree\.

The parent acts as a teacher\. We cache its categorical distributions at every parent coordinate, copy the four child models, and fine\-tune all copied coordinate networks to minimize the forward divergence:

d\(qv,qS;I\)=13​\|I\|∑\(i,j\)∈I∑c=13DKL\(qv,c\(⋅∣ui​j\)∥qS,c\(⋅∣ui​j\)\)\\displaystyle d\(q\_\{v\},q\_\{S\};I\)=\\frac\{1\}\{3\|I\|\}\\sum\_\{\(i,j\)\\in I\}\\sum\_\{c=1\}^\{3\}D\_\{\\mathrm\{KL\}\}\\\!\\left\(q\_\{v,c\}\(\\cdot\\mid u\_\{ij\}\)\\,\\\|\\,q\_\{S,c\}\(\\cdot\\mid u\_\{ij\}\)\\right\)\(70\)in bits per symbol\. A child that fell back to the constant model has no trainable parameters and remains fixed; all other child weights are adapted\. We again use a random50%50\\%training–validation split, the optimizer and stopping schedule above, and validation checkpointing\. The adapted student is retained only if its validation divergence is lower than that of the unadapted routed student by at least0\.020\.02bits per symbol and by at least2%2\\%\. Otherwise, we revert all four components to their original child models\.

The conditional model term uses the same learning\-curve construction as[Equation67](https://arxiv.org/html/2610.20922#A4.E67), with the training cross\-entropyℓ\\ellreplaced by the training distillation lossddand its selected valued⋆d\_\{\\star\}:

L^model,condg=3​∫0s⋆\[d⁡\(s\)−d⋆\]\+​𝑑s\.\\displaystyle\\widehat\{L\}\_\{\\mathrm\{model,cond\}\}^\{g\}=3\\int\_\{0\}^\{s\_\{\\star\}\}\[d\(s\)\-d\_\{\\star\}\]\_\{\+\}\\,\\mathrm\{d\}s\.\(71\)If adaptation is rejected, this term is zero\. The conditional residual is the remaining teacher–student divergence over every coordinate and channel:

L^resid,condg=∑i,j,cDKL\(qv,c\(⋅∣ui​j\)∥qS,c\(⋅∣ui​j\)\),\\displaystyle\\widehat\{L\}\_\{\\mathrm\{resid,cond\}\}^\{g\}=\\sum\_\{i,j,c\}D\_\{\\mathrm\{KL\}\}\\\!\\left\(q\_\{v,c\}\(\\cdot\\mid u\_\{ij\}\)\\,\\\|\\,q\_\{S,c\}\(\\cdot\\mid u\_\{ij\}\)\\right\),\(72\)and our estimate of the conditional model complexity is their sum:

Lcondg​\(mxvf∣mxv1f,…,mxv4f\)=L^model,condg\+L^resid,condg\.\\displaystyle L\_\{\\mathrm\{cond\}\}^\{g\}\(m\_\{x\_\{v\}\}^\{f\}\\mid m\_\{x\_\{v\_\{1\}\}\}^\{f\},\\ldots,m\_\{x\_\{v\_\{4\}\}\}^\{f\}\)=\\widehat\{L\}\_\{\\mathrm\{model,cond\}\}^\{g\}\+\\widehat\{L\}\_\{\\mathrm\{resid,cond\}\}^\{g\}\.\(73\)This construction gives the desired limiting behaviour\. If the parent model is reproduced by simply routing among the children, no adaptation is needed and the residual divergence is zero\. If modeling the quadrants together changes the useful spatial structure, reproducing the parent requires either a nontrivial learning trajectory, a remaining functional correction, or both\. As with the two\-part model term,[Equation71](https://arxiv.org/html/2610.20922#A4.E71)is a surrogate rather than a complete bitstream; the purpose of the residual is to ensure that cheap adaptation is not mistaken for exact recovery\. The full procedure is given in[Algorithm5](https://arxiv.org/html/2610.20922#alg5)\.

Algorithm 5Conditional compression of a parent coordinate modelInput:Parent model

qvq\_\{v\}; quadrant models

q1,…,q4q\_\{1\},\\ldots,q\_\{4\}; parent coordinate grid

Cache the teacher distributions produced by

qvq\_\{v\}on the parent grid;

Construct the unadapted routed student

qS\(0\)q\_\{S\}^\{\(0\)\}using[Equation69](https://arxiv.org/html/2610.20922#A4.E69);

Randomly split parent coordinates equally into training set

ItrI\_\{\\mathrm\{tr\}\}and validation set

IvalI\_\{\\mathrm\{val\}\};

Copy the child models to obtain

qSq\_\{S\};

for*t=1,…,tmaxt=1,\\ldots,t\_\{\\text\{max\}\}*do

Fine\-tune the trainable child copies on

ItrI\_\{\\mathrm\{tr\}\}using[Equation70](https://arxiv.org/html/2610.20922#A4.E70);

At scheduled evaluations, record

\(st,dt\)\(s\_\{t\},d\_\{t\}\)and validation divergence, and save the best checkpoint;

Stop if the validation patience criterion is met;

end for

Restore the validation\-selected student

qS⋆q\_\{S\}^\{\\star\};

if*qS⋆q\_\{S\}^\{\\star\}improves onqS\(0\)q\_\{S\}^\{\(0\)\}by both validation margins*then

qS←qS⋆q\_\{S\}\\leftarrow q\_\{S\}^\{\\star\}and compute

L^model,condg\\widehat\{L\}\_\{\\mathrm\{model,cond\}\}^\{g\}using[Equation71](https://arxiv.org/html/2610.20922#A4.E71);

else

qS←qS\(0\)q\_\{S\}\\leftarrow q\_\{S\}^\{\(0\)\}and

L^model,condg←0\\widehat\{L\}\_\{\\mathrm\{model,cond\}\}^\{g\}\\leftarrow 0;

end if

Compute

L^resid,condg\\widehat\{L\}\_\{\\mathrm\{resid,cond\}\}^\{g\}on the complete parent grid using[Equation72](https://arxiv.org/html/2610.20922#A4.E72);

return

L^model,condg\+L^resid,condg\\widehat\{L\}\_\{\\mathrm\{model,cond\}\}^\{g\}\+\\widehat\{L\}\_\{\\mathrm\{resid,cond\}\}^\{g\};

#### Decomposition and reward\.

The64×6464\\times 64image yields6464patches of size8×88\\times 8,1616patches of size16×1616\\times 16, four patches of size32×3232\\times 32, and one complete\-image patch\. We therefore fit8585two\-part models and evaluate2121four\-child joins per image\. For a join with anH×WH\\times Wparent, we divide[Equation73](https://arxiv.org/html/2610.20922#A4.E73)byH​WHW, giving conditional complexity per spatial location\. Letr16r\_\{16\},r32r\_\{32\}, andr64r\_\{64\}be the mean normalized conditional complexities among joins whose parent widths are1616,3232, and6464, respectively\. The scalar fitness is the power mean:

R⁡\(x\)=\(r16p\+r32p\+r64p3\)1/p,p=0\.75\.\\displaystyle R\(x\)=\\left\(\\frac\{r\_\{16\}^\{p\}\+r\_\{32\}^\{p\}\+r\_\{64\}^\{p\}\}\{3\}\\right\)^\{1/p\},\\qquad p=0\.75\.\(74\)Averaging within a scale prevents the more numerous small patches from dominating, while the power mean gives the three scales equal overall status and is more sensitive than the arithmetic mean to weaker scales\.

#### Evolutionary optimization\.

The coordinate networks above are fitted probabilistic models used only to evaluate the reward\. The CPPNs used to generate each candidate image are separate networks whose architectures and parameters are evolved\. Each receives the full\-image coordinate\(ux,uy\)∈\[−1,1\]2\(u\_\{x\},u\_\{y\}\)\\in\[\-1,1\]^\{2\}and produces three scalar outputsyc∈\[−1,1\]y\_\{c\}\\in\[\-1,1\]\. We convert each output to an intensity by:

xi​j​c=round⁡\(\(yc​\(ui​j\)\+1\)​\(4−1\)2\),\\displaystyle x\_\{ijc\}=\\operatorname\{round\}\\\!\\left\(\\frac\{\(y\_\{c\}\(u\_\{ij\}\)\+1\)\(4\-1\)\}\{2\}\\right\),\(75\)so a single deterministic CPPN genome specifies all64×64×364\\times 64\\times 3values\.

We evolve these genomes with feed\-forward NEAT\([Stanley and Miikkulainen, 2002](https://arxiv.org/html/2610.20922#bib.bib44);[Stanley and Miikkulainen, 2004](https://arxiv.org/html/2610.20922#bib.bib45)\), implemented usingneat\-pythonversion2\.1\.02\.1\.0\([McIntyre et al\., 2026](https://arxiv.org/html/2610.20922#bib.bib46)\)\. NEAT begins with simple networks, introduces nodes and connections through mutation, crosses over related genomes, and groups similar genomes into species so that newly complexified structures can compete primarily with close relatives\. We defer the precise crossover, speciation, and offspring\-allocation rules to the original papers\. Our settings, summarized in[TableD\.1](https://arxiv.org/html/2610.20922#A4.T1), are close to those used for CPPN evolution in Picbreeder\([Secretan et al\., 2008](https://arxiv.org/html/2610.20922#bib.bib42);[Secretan et al\., 2011](https://arxiv.org/html/2610.20922#bib.bib43)\)\.

Table D\.1:NEAT hyperparameters for the image experiment\. Mutation probabilities are applied byneat\-pythonduring genome reproduction\.SettingValuePopulation and initialization200200feed\-forward genomes; initially no hidden nodes, with both coordinate inputs fully connected to all three outputsActivationsHidden\-node default tanh; mutation options identity, sigmoid, tanh, and Gaussian; activation mutation probability0\.120\.12; output activations fixed to tanhStructural mutationAdd connection0\.350\.35; delete connection0\.080\.08; add node0\.250\.25; delete node0\.050\.05Weights and biasesGaussian initialization with mean00and standard deviation11; weight mutation probability0\.80\.8; bias mutation probability0\.70\.7; replacement probability0\.10\.1; additive\-mutation standard deviation0\.750\.75; values clipped to\[−30,30\]\[\-30,30\]SpeciationCompatibility threshold2\.82\.8; coefficient1\.01\.0for nodes or connections present in only one genome; coefficient0\.80\.8for weight differencesStagnationSpecies considered stagnant after3030generations without improvement; the three highest\-fitness species protected from stagnation removalReproductionTwo top genomes copied unchanged per species; top25%25\\%of each species eligible to reproduce; minimum species size22
#### Image\-generating CPPN network statistics\.

To quantitatively analyze the structure of the evolved images, we compute summary statistics of the CPPN networks that generated them, summarized in[TableD\.2](https://arxiv.org/html/2610.20922#A4.T2)\.

Table D\.2:CPPN structural statistics recorded during evolution\. Each metric is summarized across the population using its mean and maximum\.MetricDescriptionNodesNumber of hidden nodes\.ConnectionsNumber of connections between nodes\.DepthLongest input\-to\-output path length, measured in connections\.log10⁡\(1\+\#​Paths\)\\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\.Reused nodes \(%\)Fraction of hidden nodes with fan\-out greater than one\.Combining nodes \(%\)Fraction of hidden nodes with fan\-in greater than one\.
#### Additional example images\.

[FigureD\.2](https://arxiv.org/html/2610.20922#A4.F2)shows additional generated images using compositionality reward, and[FigureD\.3](https://arxiv.org/html/2610.20922#A4.F3)for the structure reward\.

![Refer to caption](https://arxiv.org/html/2610.20922v1/generated_images_hierarchical_all.png)Figure D\.2:Additional images generated from compositionality\-optimized CPPNs\.![Refer to caption](https://arxiv.org/html/2610.20922v1/generated_images_sophistication_all.png)Figure D\.3:Additional images generated from structure\-optimized CPPNs\.