Towards a Formal Theory of Representational Compositionality
Authors: Eric Elmoznino
Thomas Jiralerspong
Yoshua Bengio
Guillaume Lajoie
Venue: ICML 2025 poster (2025)
Keywords: compositionality
complexity
deep learning
representation
generalization
Primary area: theory->deep_learning
TL;DR: We present a formal, mathematically-precise definition of compositionality. We argue that the theory accounts for and extends our intuitions about compositionality, and can inspire novel methods for learning compositional representations.

Abstract: Compositionality is believed to be fundamental to intelligence. In humans, it underlies the structure of thought and language. In AI, it enables a powerful form of out-of-distribution generalization, in which a model systematically adapts to novel combinations of known concepts. However, while we have strong intuitions about what compositionality is, we lack satisfying formal definitions for it. Here, we propose such a definition called representational compositionality that is conceptually simple, quantitative, and grounded in algorithmic information theory. Intuitively, representational compositionality states that a compositional representation is both expressive and describable as a simple function of parts. We validate our definition on both real and synthetic data, and show how it unifies disparate intuitions from across the literature in both AI and cognitive science. We hope that our definition can inspire the design of novel, theoretically-driven models that better capture the mechanisms of compositional thought. We make our code available at https://github.com/EricElmoznino/complexity_compositionality.

Towards a Formal Theory of Representational Compositionality
Eric Elmoznino 12
Thomas Jiralerspong 12 Yoshua Bengio 12 Guillaume Lajoie
Abstract
probabilistic program inference (Lake et al., 2017; Ellis et al., 2023), modular deep neural networks Bengio (2017); Goyal & Bengio (2022); Pfeiffer et al. (2023); Andreas et al. (2016); Goyal et al. (2021; 2020); Schug et al. (2024), disentangled representation learning (Higgins et al., 2017; Lachapelle et al., 2022; Ahuja et al., 2022: Brehmer et al., 2022; Lippe et al., 2022; Sawada, 2018), object-centric learning (Locatello et al.. 2020; Singh al., 2023; Wu et al., 2024), and chain-of-thougle reasoning (Wei et al., 2022; Kojima et al., 2022; Hu et al., 2024), to name only a few. One of the primary appeals of compositionality is that it enables powerful form of diitt--distributtinn generalization (Lake & Baroni, 2018): a model is compositional with respect to a set of features in training data, need not observe all possible combinations of those features in order to generalize to novel ones (Schug et al., 2024; Wiedemer et al., 2024: 2023; Bahdanau et al., 2019; Mittal et al., 2021).
Compositionality is believed to fundamental intelligence. In humans, underlies the structure of thought and language. In AI, it enables a powerful form of out-of-distribution generaliza- tion, in which a model systematically adapts to novel combinations of known concepts. However, while we have strong intuitions about what compositionality is, we lack satisfying formal def- initions for it. Here, we propose such a definition called representational compositionality that is conceptually simple, quantitative, and grounded in algorithmic information theory. Intuitively, representational compositionality states that a compositional representation is both expressive and describable as a simple function of parts. We validate our definition on both real and synthetic data, and show how it unifies disparate intuitions from across the literature in both AI and cognitive science. We hope that our definition can inspire the design of novel, theoretically-diee -riven models that better capture the mechanisms of compositional thought. We make our code available here.
Despite its importance, compositionality remains an elusive concept: there are currently few formal, quantitative defi- nition of compositionality that could be used to measure it, and those that do exist have important theoretical drawbacks. Compositionality is often described in the following way: Definition 1 (Compositionallit- - colloquial)
The meaning of complex expression is determined by its structure and the meanings of its constituents (Szabó, 2022).
1. Introduction
Compositionality is thought to be one of the hallmarks of human cognition. In the domain of language, it lets produce and understand utterances that we have never heard, giving us "infinite use of finite means" (Chomsky, 1956). Beyond this, one of the most influential ideas in cognitive science is the Language of Thought hypothesis (Fodor, 1975; Quilty-Dunn al., 2023), which conjectures that all thought involved in higher-level human cognition compositional. Compositionality has been equally influential in AI from its very origins, motivating efforts in neurosymbolic AI (Garcez& & Lamb, 2023; Sheth et al., 2023; Marcus, 2003),
In the context of neural representations in brains or deep neural networks (DNNs), we can take these "meanings" to be high-dimensional vectors of activations. Definition I lacks formal rigour and breaks down upon inspection.
First, the definition presupposes the existence of a symbolic "complex expression" associated to each meaning. In some cases, this makes sense; for instance, consider human lan- guages and the neural representations they elicit. But where do these expressions and their constituent parts come from when considering neural representations themselves such as the Language of Thought hypothesis. where thoughts are encoded in distributed patterns of neural activity?
'Equal contribution UUniversité de Montréal. Correspondence to: Erie Elmoznino <eric.elmoznn fifiicclloznnooee @ mila. quebec., Guillaume Lajoie <guil- lajoee @ mila.quebec>.
Milla Quebec AI Institute
Second, it is unclear what the expression's 's "structure" should be. The definition is motivated from human language, where sentences have syntactic parses and individual words have types (e.g., noun, verb), but these properties are not intrinsic to the sentences themselves, which are simply strings.
Proceedings of the 4dnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the au)hor(s).

---

Towards Formal Theory of Representational Compositionality
Third, the definition says that meaning is "determined by" the structure and meanings of the constituents, but it does not put any kind of restriction on these semantics for the mean- ings to qualify as compositional: any function qualifies. For instance, functions that arbitrarily map constituents to their meanings (as in the case of idioms like "he kicked the bucket") are functions nonetheless and thus satisfy Definition 1, but is commonly agreed that they are not compositional (Wein- reich, 1969; Mabruroh, 2015; Swinney & Cutler, 1979).
object y, denoted K (xrly), which is the length of the shortest program that takes y as input and outputs x. Kolmogorov complexity has many intuitive properties as measure of information quantity. The more "structure" an object has (regularity, patterns, rules, etc.), the more it can be compressed using a short program.
In the context of ML. an interesting quantity is the Kol- mogorov complexity of a dataset X (Z1,.... where each sample is drawn from a distribution p(x:). If the dataset is sufficiently large, the optimal method for compressing it is to first specify and then encode the data using it, giving (X) = p( + K(p) (Fortnow, 2000). For the first term K ( p), each sample can be optimally encoded using - -log, p(x;) bits, as in the case of Shannon information (Shannon, 2001). The second term K(p) refers to the complexity of the data distribution (i.e., the length of the shortest program that computes the function p: - Rt).
Finally, the colloquial definition of compositionality suggests that it is a binary property of representations, when it should arguably be a matter of degree. For instance, while linguists often model the syntax and semantics of language using hi- erarchical decompositions that are considered compositional (Chomsky, 1956), human language regularly deviates from this idealization. In particular, language has some degree of contexx-sensitivity, where the meanings of words depend on those of others in the sentence. Thus, human language does not satisfy the colloquial binary definition of composi- tionality, even though it is considered largely compositional.
Compressing Z as a function of parts us denote a rep- resentation by a matrix Z ERDDD where each row 2n is ob- tained by sampling iid from some data distribution and model p(z)p(2(rr For instance, p(z:) could be distribution over natural images, 2, p(2 (r) could be the (often deterministic) output some intermediate layer in a trained image classifier, and the resulting representation Z RR.VD would be a ma- trix of these layer activations. We will argue that a natural way to think about compositional representations is that they can be significantly compressed a function of constituent parts. In other words, the shortest program that outputs the repre- sentation, with length K (Z), has particular form: it first de- scribes Z using short barts-based constituents, and then maps these parts to the high-dimensional representation. This pro- gram form is shown Figure I and described in detail below. We also give summary of all program components in Table 1. Crucially, the components of this program will be used in Sec- tion 3 to construct formal definition of compositionality, in which representations that are more compressible as a func- tion of constituent parts are more compositional. Before com- bining them into a definition of compositionality, we now de- scribe the components of this program in the following steps.
The colloquial definition of compositionality is thus flawed if we wish to formalize and measure it quantitatively, moving beyond mere intuitions that are fundamentally limited in their explanatory reach. In this paper, we introduce such a definition, which we call representational compositionality. The definition is grounded in algorithmic information theory, and says that compositional representations are both expressive and easily describable as simple function of symbolic parts. We argue that this definition not only addresses Definition I's flaws, but also accounts for and generalizes our many intuitions about compositionality. Finally, we provide empirical experiments that clarify implications of the definition and validate its agreement with intuition. Since representational compositionality is rigorous and quantitative, we hope that it can inspire new principled methods in AI for learning compositional representations.
2. Compressing a Representation
The definition that we will propose rests on the idea that compositional representations can be described as a simple function of constituent parts. While there may be many ways to describe a representation, a natural and principled way through the lens of optimal compression and Kolmogorov complexity. We provide brief introduction to Kolmogorov complexity below, and give more background Appendix A.
Step 1: describe Z using parts- baats- constituents We assume that every sample of the representation žn of data point x. can be compressed using a sequence of constituent parts, which in practice are discrete tokens. By analogy to natural language, we will call these sequences "sentences", denoted by W V X M where V is the vocabulary and M is the maximum sentence length. Each row in W is a sentence that describes a high-dieeniional vector in the corresponding row of Z. Importantly, these are not sentences in a human lan- guage like English: they are sequences of discrete tokens that best compress the representation. and can be thought of as the representation's 's intrinsic language. For instance, the repre-
Kolmogorov complexity Kolmogorov complexity (Li et al., 2008; Kolmogorov, 1965) is notion of information quantity. Intuitively, the Kolmogorov complexity of an object x, denoted K(x), is the length of the shortest program (in some language) that outputs x. A related notion is the conditional Kolmogorov complexity of given another
2

---

Towards Formal Theory of Representational Compositionality
a. def construct_ 20:
b.
Representation samples from a pretrained model, brain, etc.
A 1. Describe using compressed code W
def P_www); # K (pw) = length of this function
returns probability
w_compressedd = [...] K (W P
Σ log (M))
w= decode w. compressed, P_W) 8 = small constant
Distribution over (w(w) sentences
2. Decode from
M(: (w)
def f(w): (KF))= - length this function
W E P
Z Z
returns mean and stá of a normal distribution
Reconstruction error
def P_normal mu, std): 8 K small constant
returns prohability
Sentences
Semantics
Representation Latent model representation
z_mu. s_d f(w)
small
Discrete symbol sequences describing the representation
Mapping from sentences to the representation
oorrrection = [..] # x (Z (I= Σ log Waani =R)
z decodelz ccooreccionn, p_normal. m_mu. z.sid) # K small constant
( s
min Pw. W.f
(P + x (W.J)
return 2
Figure I. Form of the shortest program outputting compositional representation Z. a. Pseudocode of the program, which describes the representation using sentences W (sequences of discrete tokens) that are compressed using a prior pw( and then maps these sentences to high-dimensional vectors in representation-space using function f(w) that outputs the sufficient statistics of a Normal distribution. decode () is short function that decodes an object compressed using arithmetic coding (Witten et al., 1987). Illustration of the program compressing representation from a pretrained model layer, brain region, etc. The total Kolmogorov complexity of the reprosentation is estimated by the length of the shortest program that has this form.
Name
Symbol
Example (for representations of scene images)
Representation
Z E NXD
Layer activations of CNN in response N scene images Symbol sequence expressing a scene graph for each 2 E Z Distribution over sentences expressing scene graphs Embed & concatenate each object/relation in the scene graph Correct remaining error unaccounted for by the semantics
Sentences
W E VNNM
Language
Pw S (zzf(ww)
Semantics
Recon. error
Table 1. Components of assumed shortest program that outputs a compositional representation
sentation describes visual scenes, the sentences might specify the objects and relations that the scene is composed of.
to encode 2,, is (logp(zn;::(( For simplicity, we take p to be a Normal distribution / whose mean and standard deviation are given by f(w,). In sum, the part of the program in Figure that decodes representations from their sentences contributes total Kolmogorov complexity of:
To encode sentences in their most compressed form, the program should also define distribution over the sentences (w)) This is because optimal coding schemes (c.g.. arithmetic coding Witten et al., 1987) allow us to encode an object using only - log p(æ) bits if p is known (see Equation (7)). Together then, the part of the program in Figure that describes a representation using discrete sentences contributes a total Kolmogorov complexity of:
K())+ - N
n- (zni (w.))
As a small technical note, because Z lives in a continuous space, it would take an infinite number of bits to encode. Thus, in practice, precision and discrete approximation of the Normal distribution can be used (e.g., the Skellam distribution).
must be discretized to some finite
K (< Σ
logp.. (w,)).
Step 2: decode from W Given sentences W, the program must output Z. It must therefore define a function f: M + H Phich we call the semantics in analogy to natural language- that maps discrete tokens sequences to their high-dimensional vector representations. In general, (w.) will not perfectly reconstruct Zn (W,, is discrete but 2n is continuous), and these errors must be corrected. This can be achieved if outputs the sufficient statistics of some distribution in RD. in which case the number of bits needed
Summary The steps above describe program outputting Z. We take representations to be compositional if they are highly compressible as function of constituent parts (justified in Section 3). Under this framework, the total Kol- mogorov complexity of the representation decomposes as:
K(Z)= min K (VV) W.
(1)
3

---

Towards Formal Theory of Representational Compositionality
The minimization above is important: the shortest program is the one in which Pv. W, and are jointly selected so as to minimize the total program length. With (Z) defined, we can provide some more intuition for its components.
is relative to how well it can be compressed as a simple function of parts W that constitute an intrinsic language. In C (Z), however, the language W is externally defined; for instance in a natural language, W are the sentences that a person might utter while Z are the neural activity patterns that those sentences elicit. While C(Z) is more general, C+ C* (Z) can be used to estimate the compositionalities of real- world languages or other mappings between symbolic sequences and representations (e.g. tokenization schemes), making it useful tool for Al development. In addition, CL (Z) can be used to investigate learned representation' 's compositionality with respect to dataset's ' underlying gen- erative factors, as is done in prior work (Ren & Sutherland, 2024; Wiedemer et al., 2023; Ren et al., 2023).
(P.)) ) is the complexity of the language used to describe the representation. For instance, a language in which each word independent of the others would be simpler than language in which each word highly context-sensitive. K K(W] (WIPw) is the complexity of the sentences needed to describe the repre- sentation using the language Pio. If sentences tend to be typi- cal utterances with high probability under the language, they will have low complexity. (f) is the complexity of the se- mantics that define how sentences (discrete token sequences) map to their meanings htigh-dimensional vectors). This term central the definition of compositionality that we will introduce in Section 3. K ff)) arises from imperfect reconstructions of Z, such as errors due to continuous parts of Z that can't 't be modeled as a function of discrete inputs.
In Section 4, we will first illustrate and test properties of C(Z) using synthetic data where computations are tractable. We follow with real-world evaluation of C' (Z) on various language systems. Before doing so, we begin by unpacking our definitions to see how they account for the problems of the colloquial Definition 1 and explain computational properties typically associated with compositionality. We discuss related work around compositionality in Section and limitations of our definition in Section 6.
3. Representational Compositionality
Our definition of compositionality is a ratio of constituent terms in the decomposition of K (Z) in Equation (I):
Definition 2 (Representational compositionality)
Expressivity and compression Representational compo- sitionality says that the compositionality of a representation is a compression ratio that depends on two things: (1) the complexity of the representation (numerator), and (2) the complexity of the semantics which construct the representation from its constituent parts (denominator). When representation is highly expressive (high K (2)) but can nevertheless be compressed as simple function of constituent parts (low K K(Z(W), representational composi- tionality says that the representation is highly compositional. Representational compositionality therefore formalizes a hypothesis in cognitive science that compositionality emerges from competing pressures for expressivity and compression (e.g., Kirby, 1999; Kirby et al., 2004; 2008, and references therein), which has also recently been explored in Al from theoretical perspective (Ren & Sutherland, 2024).
The compositionality of a representation C(Z) is:
K(Z) K(ZW)
K(Z)
C(Z)=
K( K()+K(ZW..))
where W, and f are obtained from the shortest program that compresses Z in Equation (1).
Crucially, Pw. W, and are not free parameters: they are intrinsic to the representation in that they best compress Z (see the minimization in Equation (1)). Like Kolmogorov complexity, C(Z) is intractable to compute, but it can still be tractably estimated using efficient compression and optimiza- tion methods. In Appendix B, we outline a strategy for esti- mating (P,, W) and thus, C(Z) for general cases, though leave precise implementation for future work. Impor- tantly, Definition 2 can also be adapted for language systems where symbolic mapping W (a language) is given and fixed:
Constituent "parts" are intrinsic to Z Unlike the colloquial Definition 1, representational compositionality makes it clear where the constituent parts (tokens in W), complex expressions (W), and structure (f) associated with representation come from: optimal compression. This is a significant difference between Definition 2 and other related ideas in the literature which quantify compositionality in terms of reconstruction from externally-defined parts (c.g.. Andreas, 2019; Trager et al., 2023; Lewis et al., 2022).
Definition 3 (Language system compositionallit)
The compositionality of a language (L)(Z) is:
((Z) Cz) = K(ZIWL) K(Z')
K(Z)
where fr is obtained from the shortest program that com-
presses Z given sentences W
Systematicity and generalization Representational com- positionality formalizes the intuition that the constituent parts
Intuitively, C(Z) measures how expressive a representation
4

---

Towards Formal Theory of Representational Compositionality
of compositional representation determine the meaning of the whole in a systematic way (Szabó, 2022; 2012), where "systematicity" is a term from cognitive science that roughly means "structured" or "non- -ron-arbitrarr". If f arbitrarily maps sentences w to their representations z in a way that does not take the structure or words of the sentence into account (as in the case of idioms), then its complexity K()) is necessar- ily high and compositionaliiyy is low (we demonstrate this through experiments in Section 4.1). In addition, if f is inac- curate in how it maps sentences to their representations, the error ( [ J) is high and the compositionality low. A rep- resentation that is highly compositional according to our def- inition thus benefits from the generalization ability of simple functions (low K( (f) that fit their data well (low K( K(Z) (ZW ))) This ability of f to generalize to novel sentences explains the fundamental relationship between compositionality and no- tions of systematicity from cognitive science (Szabó, 2022).
for representaaion o and its implications, we describe some concrete illustraaiive examples in Appendix D.
4. Empirical Results
In this section, we evaluate our compositionality definitions, (()) and (Z), on both synthetic and real-world datasets to see if they agree with intuitions.
We compare to heuristic metric of compositionality called topological similarity that is commonly used in the literature. For some ( (WZZ). topological similarity computes a distance between all pairs of sentences A = dw (w;,w,) using a distance metric d in W, and a distance between all pairs of representation elements A = z (2,,2, using a distance metric dz (-) in Z. It then computes the Pearson correlation p between the two pairwise distance matrices, quantifying the degree to which the two spaces share linear structure.
baructure-preservinng maps Representational composi- tionality explains the widely-hel intuition that semantics functions/ f which are compositional are structure-pre preeerriig in how they map + (Montague et al., 1970). In structure- prrettuvrrpeerriiggggg. map, each word in the sentence w inde- pendently affects a different subspace of the representation e so that pairwise-din wwwtt---distteesssseeee are similar in sentence-space and representation-space As explained in Ren et al. (2023), structure- prretervigg maps have lower complexity, and thus higher compositionality according to our definition. We support this claim empirically through experiments in Section 4.1.
4.1. Synthetic Representations
We first consider representations Z that are generated syn- thetically using known rules through: 2 ==>( (w)), (w). Since we know the underlying programs that generated the representations in this case, we know the true complexity terms K (Pw), K(W K()), and (Z)) needed to compute C(Z) exactly, allowing us to better validate representational compositionality. We describe our synthetic representations below (details in Appendix I).
Lookup tables The simplest way to construct a represen- tation from sequences of discrete tokens is to assign each token in the vocabulary a fixed embedding in a lookup table, and then concatenate these embeddings across the sequence (Figure 2a). Alternatively, the lookup table could assign each unique n-gram an embedding and we could concatenate the embeddings for consecutive n-sized chunks in the sequence. We call n the "disentanglement" factor because n = 1 corresponds to a representation in which each word fully determines a subset of dimensions in the representation. We generate representations by varying certain parameters of the generative program while keeping others constant, and observe the effects on compositionality in Figure 2b.
Modularity Representational compositionality explains the relationship between compositionality and modularity, which has been difficult to formally articulate in past work (Lepori et al., 2023; Goyal & Bengio, 2022; Mittal et al., 2022). Modularity refers to a system which can be decomposed into interacting sub-parts that can be understood separately (Poole& & Mackworth, 2010); an example in ML is mixture-of-expee ex-eeerss models. A modular ff is simple because it decomposes knowledge into smaller reusable components, each of which only needs to be defined once. This also explains why natural language is highly compositional. Lin- guists model language using context-free grammars (Chom- sky, 1956), in which a sentence decomposes into a parse tree with a "production rule" recursively applied at each node. The production rules are akin to small number of reusable modules in f. giving language simple semantics. We We support these claims empirically through experiments in Section 4.1.
Sentence length: As sentence length increases, compo- sitionality should intuitively increase. For instance, if sentences are of length 1, we are not tempted to call the representation compositional. The more the representation decomposes according to parts, the more compositional it should be. Representational compositionality empirically matches this intuition because K K(2) increases with sentence length (there are more possible values, for instance) and K prrppppotii to the size of the lookup table- decreases with sentence length (embeddings become lower-dimensional, In contrast, topological similarity
Ultimately, a formal definition of compositionality should be judged based on whether it agrees with our intuitions and gen- eralizes them in meaningful ways. Based on the properties listed above, we argue that representational compositionallty satisfies all of these desiderata. To provide further intuition
5

---

Towards Formal Theory of Representational Compositionalit
a.
Lookup table
b.
Lookup table resuits
Repr. comp, (ours) Top. similarity
Compositionalins
f:
20
10
B
Sentence length
Vocabulary size
Representation dim
Disentanglement
C.
Synthetic grammar
d.
Synthetic grammar results
Repr. comp. (ours) Top. similarity
R1 Ad: + -
Compositiona
R2: C.NN+VV VV
R2
f
Rj X214
1
20
30
40
scared A j
cats V
run V
Grammar width
Grammar depth
Number of rules
Figure 2. Compositionality of syntheticalll-geeeraat representations. C(Z) ) is consistent with intuitions about compositionality across all experiments, whereas lopological similarity is not. a. lookup table representations, words (or n-grams) are assigned embeddings which are concatenated to form b. Compositionality as function of ground-truth representation properties. "Disentanglement refers to varying n-gram size. c. grammar representations, sentences are parsed with a context-free grammar, and each production rule is associated with linear projection. Production rules are recursively applied, and the embedding the parse tree's root defines d. Compositionality as a function of ground-truth properties of the grammar. Error bars show a over 10 seeds.
decreases with sentence length, thus violating intuitions.
idioms like "break a leg" are not considered compositional), Compositionality should therefore decrease as a function of disentanglement. Notably, disentanglement of in these experiments corresponds to srructur-pressevving map, which has grounded some longstanding intuitions about compositionality (Montague et al., 1970). Representational compositionality empirically aligns with expectations by decreasing as function of disentanglement because the size of the lookup table defining K ((f) grows exponentially. This supports the claims we made in Section 3 about how our definition encompasses prior intuitions around prructure-preservv maps. Topological similarity follows the same trend definition in this case because it is designed to be maximal for structure- prrettrrrnrreeiinngggg. map.
Vocabulary size: the vocabulary is too small relative to sentence length, then expressivity and compositionality are limited (e.g., with only one word, nothing can be expressed). On the other hand, if the vocabulary is too large relative sen- tence length, then compositionality is low because expressiv- ity doesn't It come from combining constituent parts (e.g., with one-word sentences, there is no notion of parts). For given sentence length, then, compositionality should peak at some intermediate vocabulary size. We observe this empirically with representational compositionality: a sharrp early increase in compositionality followed by a monotonic decrease vo- cabulary size increases further. In Appendix E, confirm that this peak compositionality occurs at larger vocabulary sizes for larger sentence lengths. While topological similar- ity also decreases with vocabulary size, it does not show the carly increase, and is in fact largest for vocabulary size of
Context-free grammars While our lookup table exper- iments provide intuitions for representational compositional- ity, they are unlikely to reflect the structure of representations in DNNs and brains. For instance, The Language of Thought hypothesis (Fodor, 1975) posits that representations under- lying human thought have a hierarchical structure akin to context- free grammars in natural language (Chomsky, 1956). In such grammars, the meanings of sentences decompose according parse trees, where children merge into parents through production rules and leaves correspond to words. For instance, the sentence "scared cats run" decomposes ac- cording to "ADJECTIVE (scared) + NOUN (cats) + NOUN-PHRASE (scared cats)" followed by "NOUN-PHRASE (scared cats) + VERB (run) + VERB-PHRASE (scared cats run)", where symbols such
Representation dimensionality: We increased representation dimensionality by increasing the dimensionality of the word embeddings. The representation grows more expressive with dimensionality, but from increased word complexity rather than word combinations. We should therefore expect com- positionality to decrease. Representational compositionality empirically captures this phenomenon because the only thing increasing in this scenario is the size of the lookup table K(f), so that ((Z) decreases. Topological similarity, in contrast, increases a function of representation dimensionality.
Disentanglement: When the meanings of words are context- dependent, a language is considered less compositional (c.g.,
6

---

Towards Formal Theory of Representational Compositionality
as NOUN-PHRASE are parts of speech (similar to data types) and functions between parts of speech such
2.0
1.0
Topologics similarity
Compositionalit
0.8
+ - VERB- PHRASE are production rules.
1.5
0.6
To model such systems using representational composition- ality, we generated representations using simple synthetic grammars (Figure 2c). First, we assigned each word in vocabulary an embedding and a part of speech, and we defined a grammar with a set of production rules, We then generated dataset of sentences and parsed them using the grammar. Finally, the semantics were defined by embedding each word in the sentence and then applying a rule-specific function at every node in the parse tree until the root was reached, whose value we defined to be the representation. The rule-specific functions concatenated children embeddings and applied a linear projection.
1.0
0.4
0.5
0.2
0.0
0.0
we Itersted leam. Ieersted leam
Training method
Figure 3. Compasitionality of language systems that emerge in multi-agent settings. Our language system compositionality metric C² (2) agrees with topological similarity on the ordering models trained with and without iterated learning, but the numerical values provided by (Z) provide more theoretical insight (see main text). Frror hars show over 5 seeds.
We generated many synthetic representations in this way and measured their resulting representational compositionality (Figure 2d). For representational compositionality to match intuition, the number of rules in the grammar should be inversely proportional to compositionality. For example, in a natural language like English, we can express an infinite number of ideas using relatively small set of grammatical rules and vocabulary, and this is why we believe natural language is compositional. We thus varied two properties of the grammar: its "width" and its "depth". Width refers to the number of rules that are defined for each level of the parse tree's 's hicrarchy. Depth refers to the number of levels in the parse tree's 's hierarchy with unique rules prior to solely recursive application.
learn to communicate. We consider the setting of Li & Bowling (2019); Ren et al. (2020) in which speaker and listener learn to communicate in simple object reference game, where objects have symbolic attributes analogous to color, size, shape, etc. Agents trained using reinforcement learning typically communicate successfully, but often learn non-compositionall language systems that arbitrarily map sentences to objects. However, Li & Bowling (2019); Ren al. (2020) have shown that compositionality can emerge through a multi muutti-eneeation process called iterated learning (Kirby et al., 2015), where the agents' parameters are periodically reset and pretrained on sentence/object pairs from the previous generation. Kirby et al. (2015) hypothesize that this occurs because iterated learning amplifies a model's inductive bias for simpler language systems that are more easily learnable across subsequent generations.
As both width and depth increase the complexity of the grammar, we should expect compositionality to decrease as a function of both. Representational compositionality is empirically consistent with this intuition because K()) increases as a function of the number of rules, each of which was associated with its own linear projection matrix. Topological similarity only loosely correlates with intuition, and has far more noise for different draws of Z from the same grammar. Notably, these experiments support the theoretical claims made in Section 3 on how our definition relates compositionality to modularity, because each production rule serves as an independent module in f.
We trained agents both with and without iterated learning and measured (Z) for the resulting language systems. Training details are provided in Appendix J. After N gener- ations, we obtain a dataset consisting of all possible objects Z and the sentences output by the speaker W L when given those objects as input. To measure CZ)( we need both K (Z) and K (Z]W2) Since 7 consists of set of sym- bolic objects sampled uniformly, K (()) is simply equal to (0lo))((O)) where O is the set of all possible objects. To measure K (Z)W²), we used a compression method called prequential coding (Blier& & Ollivier, 2018) because it pro- vides good estimates in practice when DNNs are used for pre- diction (see Appendix H), but other compression techniques can be used if they provide tighter bounds. Prequential coding compresses Z given W by incrementally encoding individual datapoints zςi and fitting a model 0,- 1 to predict them using Wey as input. The more datapoints are encoded, the better the model becomes by having seen more training data, and the more accurately it can predict the next datapoint 2;. Since prediction error is equivalent to complexity, K K(2a (=/un,;f,-))
4.2. Emergent Languages from Multi-Agent Training
Next, we further validate our compositionality metric by applying it to real-world representations. To avoid having to solve the difficult optimization problem involved in mea- suring C(Z) (which requires a minimization of K (Z) w.r.t. Pw: W, f) we instead consider language systems in which W - W is fixed and measure (2) through Definition 3.
One interesting case of real language systems is those that emerge in multi-agent settings where agents must
7

---

Towards Formal Theory of Representational Compositionality
will decrease as a function i, which means that every sub- sequent datapoint takes fewer bits encode. The total com- plexity K (Z) is estimated by summing all of these terms.
Topological similarity
0.05
Compositionalits (a.
1.25
0.00
-0.05
0.75
Li & Bowling (2019) and Ren et al. (2020) measured com- positionality using topological similarity. Using (Z). we find that we are able to reproduce their results (see Figure 3);
-0.10
0.50
-0.15
0.25
0.20
iterated learning produces languages that are more compo- sitional. However, a desirable property of our definition is that the absolute quantities of the metric are meaningful and interpretable. In particular, language systems trained without iterated learning obtain the lowest possible compositionality score, (Z) = / ( (Z])2) = 1, meaning that the mapping from sentences to representations is entirely arbi- trary. contrast, topological similarity can at best only be used as a relative metric for comparing different languages, as its theoretical link to compositionality is not well understood.
0.00
French
Spanish
Geman
Japaneso
French
Spanish
Geman
Japanesse
Figure 4. Compositionality of natural language systems. We consider language natural systems in which . are sentences in some language and 7 are sentence embeddings obtained from pretrained multilingual model. The relative compositionalitie of languages measured using our definition C² (2) are similar (left). Note that we do not estimate the numerator K of C* and assume that it is constant across languages; as a result we can only compare relative compositionalities but do not know their absolute values (y-axis in arbitrary units, a.u.). c. Using topological similarity as mcasure of compositionality gives counter-intuiitive results (right): most languages have near-zero topological similarity and Japanese a strong outlier with a topological similarity of -0.2. Error bars show a over 3 seeds.
4.3. Natural Languages
While it is commonly accepted that all natural languages roughly equal in their expressive power (their ability to express ideas and thoughts), a highly debated question in linguistics is whether or not they are all equally compo- sitional (Joseph & Newmeyer, 2012). This question has been difficult to answer definitively, partly due to the lack of principled and quantitative definitions of compositionality.
complexity. This means that the relative compositionalities of these languages as measured by our definition C²(Z) are roughly equivalent, with Japanese being slightly more compositional. This result shows that our definition supports the equal compositionality side of the debate in linguistics surrounding natural languages that motivated this experiment at the start of the section (Joseph & Newmeyer, 2012). Using topological similarity as an alternative definition of compositionality gives counter-intuitive results that contradict own: most languages have near-zero topological similarity, except for Japanese which is a strong outlier with a negative topological similarity of -0.2.
To investigate the compositionalities of natural language sys- tems using our definition, we leveraged existing dataset of English sentences describing natural images (COCO, 2024), which we then translated into French, Spanish, German, and Japanese using a large open source model (Costa-jussà et al., 2022). To obtain proxies of meanings" Z for these sentences, we encoded them using multilingual LLM that embeds sentences a dense fixed-size vector (Reimers & Gurevych, 2020). More experimental details well as limitations of this approach can be found in Appendix K. Using these datasets of sentenceerepresentatioo pairs, we measured the composition- alities of each natural language system (2( using the same prequential coding approach as in Section 4.2. However, to estimate C (Z) exactly, we would also have to estimate K ((Z) in the numerator for each language. While this quan- tity can be estimated in principle using compression tech- niques, for the sake of simplicity here we assume that these natural languages are all equally expressive in their abilities to express ideas and identify referents (i.c., equal K (Z)). which is a common assumption in linguistics. As a consequence, however, we cannot estimate the absolute compositionalities of these languages, but only their relative compositionalities: for this reason, compositionality in Figure 4 is measured in ar- bitrary units where we set the compositionality German to 1.
5. Related Work
Communication and simplicity Our definition is most closely related to experimental work in cognitive science which suggests that compositional languages evolve over time in human cultures due to competing pressures for effec- tive communication and simplicity (Kirby. 1999; Kirby et al., 2004; 2008) a result which has also been explored in AI (Li & Bowling, 2019; Ren et al., 2020; 2023; Ren & Suther- land, 2024) through emergent languages games described in Section 4.2. Our work builds on these foundations in several ways. First, we formalize the notions of language (the tu- ple (W,J,2)). the language's is simplicity (simple semantics with low K())), and effective communication (expressive meanings through high K K(Z) with low information loss
Our results are shown in Figure 4. Using prequential coding, we find that K (2) is similar for all languages, indicating that they have semantics fr. of roughly equal
K (Z(W.))) Second, Kirby's work is about the composi- tionality of a language system where W is externally-defined
8

---

Towards Formal Theory of Representational Compositionality
(our Definition 3), whereas we also provide a definition for representational compositionality where W is intrinsically defined through optimal compression of Z. The latter notion is more directly relevant to the Language of Thought hypothe- sis (Fodor, 1 1975) and to the learned representations of DNNs.
such linear semantics (Yun et al., 2021; Trager et al., 2023) might be inherently more stable than our approach, because there are fewer modeling choices to make. However, we also emphasize that the advantage of an abstract definition like ours is precisely that at practitioners to design a breadth of estimators that make different tradeoff's between flexibility and sensitivity to modeling choices. Empirical comparisons between our definition and other reconstruction-bet basedddd mea- sures is important direction for future work. Finally, we defined compositionality with respect to discrete parts, but it may be possible to generalize this to continuous parts as well.
Representation reconstruction Many formal definitions frame compositional representations as those that can be reconstructed as a function of parts-our definition can be seen as an extension or generalization of many of these alternatives. First, reconstruction-basee approaches quan- tiffying compositionality often measure the reconstruction error of a representation Z from externally-defined parts W, where W might be the input to the function that output Z (Andreas, 2019; Ram et al., 2024), paired natural language data (Trager et al., 2023; Lewis et al., 2022), or underlying task latent variables (Wiedemer et al., 2024; 2023) again representational compositionality extends these works by defining a W that is intrinsic to Z in non-arbitrary way through optimal compression.
7. Conclusion
We introduced a novel definition of compositionality grounded in algorithmic information theory. Using theoreti- cal arguments and empirical experiments, showed that this simple definition not only accounts for our many intuitions about compositionality, but also extends them in useful ways.
In virtue of being quantitatively precise, representational compositionality can be used to investigate compositionality in real- systems. We demonstrated this with emergent and natural languages where the sentences describing a representation externally defined. In future work, this quantity can readily be applied to score tokenization schemes producing different representations in downstream models, which may lead to improvements in their design.
Second, prior work measuring compositionality through reconstruction from parts often makes strong assumptions about the form of the reconstruction for instance that it is a linear (Yun et al., 2021; Trager et al.. 2023) or hierarchical (Andreas, 2019; Ram et al., 2024) function of word embeddings. In contrast, our definition makes no such assumptions and abstracts over arbitrary functions through the lens of their complexity K (f),, thereby generalizing prior work. When reconstruction- approaches do not explicitly constrain complexity by imposing functional constraints (e.g., when they instead use use unconstrained DNN decoders), they neither minimize nor measure the complexity of the resulting semantics function, but instead measure the generalization ability of this function to novel sentences (Lewis et al., 2022; Bricken et al., 2023), which can be seen as a proxy for simplicity.
More generally, measuring the compositionalities of repre- sentations without given mapping to sentences is an impor- tant direction for future work, as it will allow us to investigate the compositionalities of representations that emerge from different learning objectives, neural architectures, inductive biases, and brain regions. In turn, we will be able to see how representational compositionality empirically relates to other topics in ML such as compositional generalization, multi- task generalization, and latent space generative models-we give some hypotheses and ideas for future work along these lines in Appendix F. In particular, representational compositionality has the potential to explain the success of varied methods because it defines compositionality through compression, which abstracts across the architecture, learn- ing details, and particular representational format of a model. Representational compositionality can therefore be used to validate or reject diverse hypotheses about compositionality, such as the Language of Thought hypothesis (Fodor, 1975).
6. Limitations
Representational compositionality, while of theoretical in- terest for understanding compositionality, is uncomputable because its terms involve Kolmogorov complexities. Like Kolmogorov complexity, it can be estimated using tractable compression algorithms, but while we did this for C (Z) we did not attempt it for C(Z) in the current paper. We sug- gested one way that C(Z) could potentially be estimated in Appendix B that involves training discrete auto-encoder with a maximum likelihood prior in the latent space, but in practice this approach might be sensitive to modeling choices such as the DNN architectures, the training hyperpa- rameters, and the quantity of training data. Indeed, related reconstruction-butt based approaches to measuring composition- ality (Section 5) that impose tighter modeling constraints
We hope that representational compositionality can also aid in the design of machine learning models with principled inductive biases for compositionality. Namely, in addition to supporting a given task, a compositional representation must be easily describable as a simple function of constituent parts; we describe some approaches for achieving this in Appendix G that can be pursued in future work.

---

Towards Formal Theory of Representational Compositionality
Acknowledgments
Bengio, Y., Lahlou, S., Deleu, T., Hu, E. J., Tiwari, M., and Bengio, E. Gflownet foundations. The Journal of Machine Learning Research, 24()):0006610066 2023.
EE acknowledges support from Vanier Canada Graduate Scholarship #492702. YB acknowledges CIFAR, NSERC and Samsung for research funding. GL acknowledges support from Canada-CIFAN AI Chair and the Canada Research Chair in Neural Computations and Interfacing (CIHR, tier 2) as well as from NSERC Discovery award CEPIN-2018-048211 GL is also a Visiting Researcher at Google's ' Paradigms of Intelligence Team.
Blier, L. and Ollivier, Y.
The description length of deep learning models. Advances in Neural Information
Processing Systems, 31, 2018.
Bornschein, J., Li, Y., and Hutter, M. Sequential learning of neural networks for prequential mdl. arXiv preprint arXiv:2210.09931, 2022.
Impact Statement
Brehmer, J., De Haan, P., Lippe, P., and Cohen, T.S. Weakly supervised causal representation learning. Advances Neural Information Processing Systems, 35:38319-38331, 2022.
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Bricken, T., Templeton, A., Batson, J., Chen, B., Jermyn, A., Conerly, T., Turner, N., Anil, C., Denison, C., Askell, A., Lasenby, R., Wu, Y., Kravee, S., Schiefer, N., Maxwell, T., Joseph, N., Hatfield- Doddds, Z., Tamkin, A., Nguyen, K., McLean, B., Burke, J. E., Hume, T., Carter, S., Henighan, T., and Olah, C. Towards monosemanticity: Decomposing language models with dictionary learning. Transformer Circuits Thread, 2023. https://rransormmrr hea.:///iiieftttttsenenee....ee html.
References
Ahuja, K., Hartford, J. S., and Bengio, Y. Weakly super- vised representation learning with sparse perturbations. Advances in Neural Information Processing Systems, 35: 15516-15528, 2022.
Andreas, J. Measuring compositionality in representation learning. arXiv preprint arXiv: 190000900111... 2019.
Chaitin, G. On the length of programs for computing finite binary sequences. Journal of the ACM (JACM), 13(4): 547-569, 1966.
Andreas, J., Rohrbach, M., Darrell, T., and Klein, D. Neural module networks. In Proceedings of the IEFE conference computer vision and pattern recognition, pp. 39-48, 2016.
Chomsky, N. Three models for the description of language. IRE Transactions on information theory, 2(3):113-124, 1956.
Atanackovic, L. and Bengio, E. Investigating generalization behaviours of generative flow networks. arXiv preprint arXiv:2402.05309, 2024.
COCO.
sentence- sentence-transformeeeee wraneettttttomessoooooaaaaiiiiii
Datasets Hugging Face, July 2024. URL
http:/aaa....coaaaaaaeeeeeeeeees ct/aattets///////////oo/ ht htt.://eeetraaaoomme/////eoooooe
Bahdanau, D., Murty, S., Noukhovitch, M., Nguyen, T. H., de Vries, H., and Courville, A. System- atic generalization: What required and can be learned? In International Conference on Learning Representations, 2019. URL https: //openreview.ro www.aarvviien.nt//orrnen. (i..rrran
Cohen, M., Quispe, G., Corff, S. L., Ollion, C.,, and Moulines, Diffusion bridges vector quantized variational autoencoders. arXiv preprint urXiv2222..48995 2022.
Costa-jussä, M. R., Cross, J., Çelebi, O., Elbayad, M., Heafield, K., Heffernan, K., Kalbassi, E., L., Licht, D., Maillard, J., et al. No language left behind: Scaling human-centered machine translation. arXiv preprint D.Xi:22007.04622,200 2022.
Bengio, E., Jain, M., Korablyov, M., Precup, D., and Bengio, Y. Flow network based generative models for non non-iterative diverse candidate generation. Advances in Neural Information Processing Systems, 11-27381-2739. 2021.
Bengio, Y. The consciousness prior. arXiv preprint arXiv: 1709.08568 2017.
Dehaene, S. Al Roumi, F., Lakretz, Y. Planton, S.. and Sablé-Meyer, M. Symbols and mental programs: a hypothesis about human singularity. Trends in Cognitive Sciences, 26(9):551-766, September 2022. ISSN 1364-6613. doi: 10.10166..ies..022..666 URL
Bengio, Y., Léonard, N., and Courville, A. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv: 2013.
https://ww..cciencce otteaa/eee///eooeeeeeeoeeaaaaaaa
10

---

Towards Formal Theory of Representational Compositionality
Driscoll, L. N., Shenoy, K., and Sussillo, D. Flexible multitask computation in recurrent networks utilizes shared dynamical motifs. Nature Neuroscience, 27(7): 1363, 2024.
Grünwald, P. D. and Vitányi, M. Kolmogorov complexity and information theory. with interpretation in terms of questions and answers. Journal of Logic, Language and Information. 12:497-5299 2003.
Earley, J.
An efficient context-free parsing algorithm. Communications the ACM, 13(2):94-002, 1970.
Higgins, I., Matthey, L.,, Pal, A., Burgess, C., Glorot, X., Botvinick, M., Mohamed, S., and Lerehner, A. beta- VAE: Learning basic visual concepts with constrained variational framework. In International Conference Learning Representations, 2017. URL https:
Ellis, K., Wong, L., Nye, M., Saylé-Meyer, M., Cary, L., Anaya Pozo, L., Hewitt, I.., Solar-Lezama, A., and Tenenbaum, B. Dreamcoder: growing generalizable, interpretable knowledge with wake-sleep bayesian program learning. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, (22(2),), June 2023. ISSN http: 2022. 0050.
/ //openreeieww.. http::/www....tooooo.odaaa/a//aa
Hinton, G. E., Srivastava, N., Krizhevsky, A., Sutskever, I., and Salakhutdinov. R. R. Improving neural networks by preventing co-adaptation of feature detectors. arXiv preprint a20i 200000000 2012.
1471-2962. doi: 10.10998/sta.22222.006 //dx. doi
Hu, E. J., Malkin, N., Jain, M., Everett, K. E., Graikos, A., and Bengio, Y. Gflownet-em for learning compositional latent variable models. In International Conference on Machine Learning, pp. 12528-13544) PMLR, 2023.
Fodor, J. A. The language of thought, volume 5. Harvard university press, 1975.
Fortnow, L. Kolmogorov complexity. In Aspects of Complexity, Minicourses in Algorithmics, Complexity, and Computational Algebru, NZMRI Mathematics Summer Meeting, Kaikoura, New Zealand, pp. 73-86, 2000.
Hu, E. J., Jain, M., Elmoznino, E., Kaddar, Y., Lajoie, G., Ben- gio, Y., and Malkin, N. Amortizing intractable inference in large language models. The Twelfth International Con- ference Learning Representations, 2024. URL https: / /pperevview net / forum?
Garcez, A. d. and Lamb, L. C. Neurosymbolic ai: The 3 rd wave. Artificial Intelligence Reviee,,5((11))12337711 2023.
ca.0.
Hupkes, D., Dankers, V., Mul, M., and Bruni, E. Com- positionality decomposed: How do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795. 2020.
Goldblum, M., Finzi, M., Rowan, K., and Wilson, A. G. The no free lunch theorem, kolmogorov complexity, and the role of inductive biases in machine learning. arXiv preprint arXiv:2304.055. 05366, 2023.
Immer, A., van der Ouderaa, T., Rätsch, G., Fortuin, V., and van der Wilk, M. Invariance learning deep neural networks with differentiable laplace approximations. Advances in Neural Information Processing Systems, 35: 12449-12463, 2022.
Gordon, J., Lopez-Paz, D., Baroni, M., and Bouchacourt, D. Permutation equivariant models for compositional generalization in language. In International Conference Learning Representations, 2020. URL https:
//openreview www.eeww.eeeeeeeee www.nee//ooooo forss//foum2aa Stt.mmmddddyyyyyyyeyyaaae
Jang, E., Gu, S., and Poole, B. Categorical reparam- eterization with gumbel-softmax. arXiv preprint 1rXiv:661.001. 2016.
Goyal, A. and Bengio, Y. Inductive biases for deep learning of higher-level cognition. Proceedings of the Royal Sociity A, 478(2266):202100)))
2022.
Jarvis, D., Klein, R., Rosman, B., and Saxe, A. M. On the specialization of neural modules. arXiv preprint arXiv:2409. 14981, 2024.
Goyal, A., Lamb, A., Gampa, P., Beaudoin, P., Levine, S., Blundell, C., Bengio, Y., and Mozer, Object files and schemata: Factorizing declarative and procedural knowledge in dynamical systems. arXiv preprint arXiv:2006.16225, 2020.
Johnston, W. and Fusi, S. Abstract representations emerge naturally neural networks trained to perform multiple tasks. Nature Communications, 14(1 14(1):1040, 2023.
Goyal, A., Didolkar, A., Ke, N. R., Blundell, C., Beaudoin, P., Heess, N., Mozer, M. C., and Bengio, Y. Neural production systems. Advances in Neural Information Processing Systems, 04:27ms,34::5555 34:25673-25687, 2021.
Jones, H. T. and Moore, J. Is the discrete vac's power stuck in its prior? In "I Can 't Believe It's Not Better!" "etter!"Nerrlie NeurlPS 2020 workshop. 2020.
Grünwald, P. D. The minimum description length principle.
Joseph, J. E. and Newmeyer, F. 'all languages are equally complex', Historiographia linguistica, 39, 2012.
MIT press, 2007.

---

Towards Formal Theory of Representational Compositionality
Kirby, S. Function, selection, and innateness: The emergence of language universals. OUP Oxford, 1999.
Lavoie, S., Tsirigotis, C., Schwarzer, M., Vani, A., Noukhovitch, M., Kawaguchi, K., and Courville, A. Sim- plicial embeddings in self- learning and down- stream classification. In The Eleventh International Con- ference on Learning Representations, 2023. URthttps:: / /ooenneview. net / forum? weerrummid--Ree RWW.d
Kirby, S., Smith, K., and Brighton, H. From ug to universals: Linguistic adaptation through iterated learning. Studies in Language. International Journal sponsored by the Foun- dation "Foundations of Language", 28(3):587-607, 2004.
Lepori, M. A., Serre, T., and Pavlick, Break it down: Evidence for structural compositionality in neural networks. In Thirty-seventh Conference on Neural Information Processing Systems, 2023, URL https: / //openreview net/ www.mmodd:wwbaaiiiii..
Kirby, S., Cornish, H., and Smith, K. Cumulative cultural evolution in the laboratory: An experimental approach to the origins of structure in human language. Proceedings of the National Academy of Sciences, (943)):06881-16683 2008.
Kirby, S., Tamariz, M., Cornish, H., and Smith, K. Com- pression and communication in the cultural evolution of linguistic structur. Cognition, 141:87-102, 2015.
Lewis, M., Nayak, N. V., Yu, P., Yu, Q., Merullo, J., Bach, S. H., and Pavlick, E. Does clip bind concepts? probing compositionality in large image models. arXiv preprint arXiv:2212.10533 2022.
Kojima, T., Gu, S. S., Reid, M., Matsuo, Y., and Iwasawa, Y. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35: 22199,22211, 2022.
Li, F. and Bowling, M. Ease-of-teaching and language structure from emergent communication. Advances in neural information processing systems, 32, 2019.
Kolmogorov, A. N. Three approaches to the quantitative definition of information'. Problems of information iransmission, 1(1):1-7, 1965.
Li, M., Vitányi, P., et al. An introduction to Kolmogorov complexity and its applications, volume Springer. 2008.
Lippe, P., Magliacane, S., Löwe, S., Asano, Y. M., Cohen, T., and Gavves, S. Citris: Causal identifiability from temporal intervened sequences. In International Conference on Machine Learning, pp. 13557-13603, PMLR, 2022.
Lachapelle, S., Rodriguez, P., Sharma, Y., Everett, K. E., Le Priol, R., Lacoste, A., and Lacoste-Julics S. Dis- entanglement via mechanism sparsity regularization: A new principle for nonlinear ica. In Conference on Causal Learning and Reasoning, pp. 428-484. PMLR, 2022.
Lippl. S. and Stachenfeld, K. When does compositional structure yield compositional generalization? kernel theory. arXiv preprint arXiv:2005.163)), 2024.
Lachapelle, S., Deleu, T., Mahajan, D., Mitliagaas, I., Bengio, Y., Lacoste-JJulin, S., and Bertrand, Q. Synergies between disentanglement and sparsity: Generalization and identifi- ability in multi-task learning. In International Conference on Machine Learning, pp. 18171-18206. PMLR, 2023.
Locatello, F., Weissenborn, D., Unterthiner, T., Mahendran,
A., Heigold, G., Uszkoreit, J., Dosovitskiy, A., and Kipf, T. Object-centric learning with slot attention. Advances in neural information processing systems, 33:1 1525-11538, 2020.
Lachapelle, S., Mahajan, D., Mitliagkas, I., and Lacoste- Julien, S. Additive decoders for latent variables identi- fication and cartesian produuct extrapolation. Advances in Neural Information Processing Systems, 36, 2024.
Mabruroh, K. An analysis of idioms and their problems found in the novel the adventures of tom sawyer by mark twain. Rainbow: Journal of Literature, Linguistics and Culture Studies, 4(1,, 2015.
Lake, B. and Baroni, M. Generalization without systematic- ity: On the compositional skills of sequeecc-to-sequeeee recurrent networks. In International conference on machine learning, pp. 2873-283822 2882. PMLR, 2018.
Marcus, G. F. The algebraic mind: Integrating connection- ism and cognitive science. MIT press, 2003.
Lake, M., Ullman, T. D., Tenenbaum, B., and Gershman, S. J. Building machines that learn and think like people. Behavioral and Brain Sciences, 40:e253, 2017. doi: 40500//
Maziarka, ł.., Nowak, A., Wolczyk, M., and Bedychaj, A. On the relationship between disentanglement and multi-task learning. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pp. 021- Springer, 2022.
Lancucki, A., Chorowski, J., Sanchez, G., Marxer, R., Chen, N., Dolfing, H. J., Khurana, S., Alumäe, T., and Laurent, A. Robust training of vector quantized bottleneck models. In 2020 International Joint Conference on Neural Networks (IJCNN, pp. 1-7. IEEE, 2020.
Mittal, S., Raparthy, S. C., Rish, I., Bengio, Y., and Lajoie, G. Compositional attention: Disentangling search and retrieval, arXiv preprint arXiv:2 10.09419, 19, 2021.
12

---

Towards Formal Theory of Representational Compositionality
Mittal, S., Bengio, Y., and Lajoie, G. Is modular architecture enough? Advances in Neural Information Processing Systems, 35:287777722277287777 2022.
Schug, S., Kobayashi, S., Akram, Y., Wolczyk, M., Proca, A. M., Oswald, V., Pascanu, R., Sacramento, J., and Steger, A. Discovering modular solutions that generalize compositionally. In The Twelfth International Conference on Learning Representations, 2024. URL https:
Montague, R. al. English a formal language. Ed. di Comunità, 1970.
/ //openreview net/ forummi
Pfeiffer, J., Ruder, S., Vulié, I., and Ponti, Modular deep learning. Transactions Machine Learning Research, 2023. ISSN 2835-8866. URthttps: open reperrevii ew. net/ t
Shannon, C. E. mathematical theory of communi- cation. ACM SIGMOBILE mobile computing and communications review, 5(1):3-55, 2001.
Survey Certification.
Sheth, A., Roy, K., and Gaur, M. Neurosymbolic artificial intelligence (why, what, and how). IEEE Intelligent Systems, 38(3):56666336 62, 2023.
Poole, D. L. and Mackworth, A. K. Artificial Intelligence: Soundations of compulational agents. Cambridge University Press, 2010.
Singh, G., Kim, Y., and Ahn, Neural systematic binder. In The Eleventh International Conference Learning Representations, 2023. URL https:
Quilty-Dunn, J., Porot, N., and Mandelbaum, E. The best game in town: The reemergence of the language- of-thought hypothesis across the cognitive sciences. Behavioral and Brain Sciences, 46:e261, 2023.
/ //operreiiee eww. net www.foiddddeeeeeee d-ii-H-2PH4H. fhtHeeffh190
Solomonoff. J. A formal theory of inductive inference, part Information and control, 7(1):1-22, 1964.
Rae, Compression for AGI Jack Rae Stanford MLSys #76. https://www yout ube.euttu...................ee.t www.o//wwttteo ch?v NO1fBUkeaaU&t-11225, 2023.
Sutskever, I. An observation on generalization. https: / //www. www..youtuue. youtube. www/wwtchtv=kkett.....o TVz3A, 2023.
Ram, P., Klinger, T., and Gray, A. G. What makes models compositional? a thcoretical view: With supplement. arXiv preprint arXiv:2405.023550 2024.
Swinney, D. A. and Cutler, A. The access and processing of idiomatic expressions. Journal of verbal learning and verbal behavior, 18(5):523-534, 1979.
Razavi, A., Van den Oord, A., and Vinyals, O. Generating images with vq-vae-2. Advances in neural information processing systems, 32, 2019.
diverse
Szabó, Z. G.
The case for compositionallity In The Oxford Handbook of Compositionaaliy: Oxford Uni- versity Press, 02 2012. ISBN 9780199541072. doi:
Reimers, N. and Gurevych, I. Making monolingual sentence embeddings multilingual using knowledge distillation. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 11 2020. URL ht Attpps:/l /tas:///rxxii wwt//bsg////eeeoooeooo//eee /ts//004/..0000 09813.
10. 00.099900rruuhhhh777701955000000
URL
/ttp:::://oii..o//10..1..... 10t.//0/////ooobbbb//// 7780199541072.013..o 0003.
Szahó, G. Compositionality. Zalta, N. and Nodelman, U. (eds.), The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, Fall 2022 edition, 2022.
Ren, Y. and Sutherland, J. Understanding simplicity bias towards compositional mappings via learning dynamics. arXiv preprint arXiv:2409.0900 09626, 2024.
Trager, M., Perera, P., Zancato, L., Achille, A., Bhatia, P., and Soatto, S. Linear spaces of meanings: compositional structures in vision-language models. In Proceedings of the IEEE/CVE International Conference on Computer Vision, pp. 15395-15404, 2023.
Ren, Y., Guo, S., Labeau, M., Cohen, S. B., and Kirby, S. Compositional languages emerge in neural iterated learning model. arXiv preprint arXiv:2002.01336 2020.
Ren, Y., Lavoie, S., Galkin, M., Sutherland, D. J., and Courville, A. Improving compositional generalization using iterated learning and simplicial embeddings. arXiv preprint arXiv:2310. 18777, 2023.
Vafidis, Bhargava, A., and Rangel, A. Disentangling representations through multi-task learning. arXiv preprint arXiv:2407.11244 2024a.
Vafidis, P., Bhargava, A., and Rangel, A. Multi-task learning yields disentangled world models: Impact and implications. In UniReps: 2nd Edition of the Workshop on Unifying Representations Neural Models, 2024b.
Sawada, Disentangling controllable and uncontrollable factors of variation by interacting with the world. arXiv preprint arXiv: arepiv:ttxxiv::: 100.:v:080000000 06955,, 2018.
13

---

Towards Formal Theory of Representational Compositionality
Van Den Oord, A., Vinyals, O., et al. Neural discrete
representation learning. Advances in neural information processing systems, 30, 2017.
van der Ouderaa, T. F. and van der Wilk, M. Learning invariant weights in neural networks. In Uncertainty in Artificial Intelligence, pp. 1992-2001, PMLR, 2022.
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E.,, Le, Q. V., Zhou, D., et Chain-of Shain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24487,, 2022.
Weinreich, U. Problems the analysis of idioms. Substance and structure of language, ((81):208-200) 1969.
Wiedemer, T., Mayilvabanan. P., Bethge, M., and Bren- del, W. Compositional generalization from first principles. Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https: //openreview net/
form fmrum? wiw.:uumii---ooooo Lolo---ooluuumms
Wiedemer, T., Brady, J., Panfilov, A., Juhos, A., Bethge, M., and Brendel, W. Provable compositional generalization for object-centric learning. In The Twelfth International Con- ference on Learning Representatiins, 2024. URL ttsp:: www.:eww.eeeeeeeeeeeeeee //openreviex.eo///////e/ea/ee/ee net wwt.//et/oouiiie forum? 1==
Wilk, M. v. d., Bauer, M., John, S., and Hensman, J. Learning invariances using the marginal likelihood. In Proceed- ings of the 32nd International Conference on Neural Information Processing Systems, pp. 1960-9970, 2018.
Witten, I. H., Neal, R. M., and Cleary, J. G. Arithmetic coding for data compression. Communications of the ACM, 520))500-0400, 1987.
Wu, Y.F,, Lee, M., and Ahn, S. Neural language of
thought models. The Twelfth International Conference on Learning Representations, 2024. URL. https:
www.:/iwww..eeeeee...eeeeeeeeee //ppe//eeii...ooeccee net. foremm/forummm -id--Yi---Hiiim mm.
Yasuda, Y., Wang, X., and Yamagishd, J. End-to-end text-to-speech using latent duration based on vq-vae. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5694-5698. IEEE, 2021.
Yun, Z., Chen, Y., Olshausen, B. A., and LeCun, Trans- former visualization via dictionary learning: contextual- ized embedding linear superposition of transformer factors. arXiv preprint arXiv:2103. 15949 2021.
Zhou, H., Vani, A., Larochelle, H., and Courville, A. Fortuitous forgetting in connectionist networks. In Inter- national Conference on Learning Representations, 2021.
14

---

Towards Formal Theory of Representational Compositionality
A. Background on Kolmogorov complexity
Kolmogorov complexity was independently developed in the 1960s by Kolmogorov (1965), Solomonoff (1964), and Chaitin (1966), and defines a notion of "information quantity".
Intuitively, the Kolmogorov complexity of an object is the length of the shortest program (in some programming language) that outputs that object. Specifically, given some finite string x, K( K(x) is the length ((r) (in bits) of the shortest binary program that prints x and halts. Let U be universal Turing machine that executes these programs. The Kolmogorov complexity of x is then:
K ((x) = (t)==mi(((()U(())=>>))) (0.1)))
(4)
where {0.1}* denotes the space of finite binary strings. A related notion is the conditional Kolmogorov complexity of a string given another string y, which is the length of the shortest program that takes y as input and outputs x::
((n)))=min((():((())>))
where r(y) denotes a program taking y as input. Finally, we can also define a "joint" Kolmogorov complexity K (x.,y) which denotes the length of the shortest program that jointly outputs both x and y. Surprisingly, joint Kolmogorov complexity is related to conditional Kolmogorov complexity (up to additive logarithmic term, which we will ignore) by the Symmetry of Information theorem (Li et al., 2008):
K
(6)
Kolmogorov complexity has many intuitive properties that make it attractive as a measure of information quantity, and although it is less common than notions from Shannon information theory (Shannon, 2001), is strictly more general (as we will show later below). The smaller and the more "structure" an object has-regularity, patterns, rules, etc.-the more it can be compressed using short program and the lower its Kolmogorov complexity. Kolmogorov complexity therefore is deeply rooted in the idea of compression. For instance, a sequence with repeating patterns or a dataset that spans a low- -iwdiieeniioall subspace can be significantly compressed relative to its original size, and this results in low Kolmogorov complexity. In contrast, a random string devoid of any structure cannot be compressed at all and must effect be "hard-coded", making its Kolmogorov complexity equal to its original size in bits.
While powerful, Kolmogorov complexity has certain limitations. First and foremost, Kolmogorov is intractable to compute exactly because it requires a brute force search over an exponentially large space of possible programs. It is therefore often using more efficient compression
of conceptual rather than practical value, although it can nevertheless be strategies. Second, Kolmogorov complexity depends on the programming language of choice. For instance, if a programming language has a built-in primitive for the object being encoded, Kolmogorov complexity trivially small. This concern, however, often overblown: given any two suring-complets programming languages, the difference in Kolmogorov complexity that they assign to an object is upper-bounded by constant that is independent of the object itself, because any Turing-complete programming language can simulate another (Grünwald & Vitányi, 2003; Fortnow, 2000). In practice, we can simply consider "reasonable" Turain complete programming languages that don't 't contain arbitrary object-specific primitives, in which case this simulation constant will be relatively small and the particular programming language of choice will have little effect. Finally, Kolmogorov complexity is only defined for discrete objects because no terminating program can output a continuous number with infinite precision. This concern is also less consequential in practice, because we can always represent continuous objects using finite (e.g., floating-pott point) precision.
Important properties for machine learning In ML, we are often concerned with datasets and probabilistic models. Kolmogorov complexity relates these two concepts in several interesting ways. First, we can ask about the Kolmogorov complexity of a finite dataset X = (#1, Z.) where each sample is drawn iid from distribution p(z). It turns out that if we have access to the true distribution p(z). optimal algorithms such as arithmetic coding (Witten et al., 1987) can encode each sample using only log,p(x;;) bits. Intuitively, this is because samples that occur more frequently can be encoded using shorter codes in order to achieve an overall better compression. We thus have that:
K(XIp)
(xx.)
(7)
15

---

Towards Formal Theory of Representational Compositionality
instead of access the true distribution p(æ) we only have probabilistic model of the data (o(),,, we have that:
((X)po) log2po (x:);
(8)
where we have equality when =p= This insight is significant. Notice that - -Ei= log2po(z;) is the negative log-likelihood of the data under the model, which is a common loss function used in ML. This tells us that models with lower error better compress their data, and directly relates Kolmogorov complexity to optimization in ML. However, what we do not have model? What is the Kolmogorov complexity of the data itself? Intuitively, if the dataset sufficiently large, the optimal method for encoding it should be first specify a model and then encode the data using that model as in Equation (8). Specifically, using identities in Fortnow (2000), we have:
x S
(9)
This encoding scheme on the RHS is referred to as a 2-part code (Grünwald, 2007). We have equality when the model's de- scription length and error are jointly minimized, which occurs when the model po (o(x) is equivalent to the true distribution p(r)):
K(X)= = argmink (X ppo) + K (po) = argmin
oggpo (x:)+ k(po)
(10)
Pe
Pe
n
= =K(XIp)+K00)
> loggp(x;)+
(11)
Again, we can draw important connections to ML. Equation (9) says that the Kolmogorov complexity of a dataset is upper-bounded by the model's 's error and complexity. In addition, Equations (10) and (11) tell us that the simplest model that explains the data is most likely to be the true one, which draws theoretical link between compression, maximum likelihood training. model complexity, and generalization (Goldblum et al., 2023).
Relation to Shannon information In Shannon information theory (Shannon, 2001), the notion of information quantity is entropy. Given a random variable X ~ p(z), entropy is defined as: (X) = Ez=p(=>) - -lgg, (p(z)). Notice that the -log, (p(x)) inside the expectation equal the quantity inside the sum of Equation (7), which specified the minimum number of bits needed to encode a sample from a dataset given the distribution that sample was drawn from. This is no accident: entropy can be seen the average number of bits needed to compress events from distribution using an optimal encoding scheme when the distribution p(z) is known. If we simply sum these bits for finite number of samples instead of taking an expectation, we get exactly K (XIp)) as defined in Equation (7).
As we have seen, though, the assumption about a known distribution p(x), need not be made in the Kolmogorov complexity framework. In this sense, Kolmogorov complexity is a strict generalization of Shannon information theory: K (X) as defined in Equation (11) equivalent to summed entropy plus the complexity of the distribution p(ar). which is unknown and needs to be encoded. In the Shannon framework, it difficult to derive a meaningful notion for the information quantity in the distribution p(x)) because it is an individual object function, in particular- and Shannon information is only defined for random variables (Grünwald & Vitányi, 2003). A second drawback of Shannon information is that entropy is measure of statistical deter- minability of states; information is fully determined by the probability distribution on states and unrelated to the representation, structure, or content of the individual states themselves (Grünwald & Vitányi, 2003). For this current work, we require a notion of complexity that can account for representations and functions, making Kolmogorov complexity better suited to the task.
B. Compressing a representation using discrete auto-encoders
To measure compositionality as defined in Definition 2, we must first compress K(Z) using the program form in Section 2. This involves finding Pu,, W, and f that jointly minimize:
K(Z)= = min K K(pw) ((p))+((W)) (WWWWWWWW++H K(W))) P.,
revisited)
N
min K(pw) Logp (w,) +K()) Σ (2ni(()))
W.W
16

---

Towards Formal Theory of Representational Compositionality
While this is intractable search problem, it can be turned into an easier optimization problem using modern deep learning minimize least some of the terms in Equation (1) by fitting discrete auto-encoder Z using
tools. In partieular, learned prior in the latent W W-space, as illustrated in Figure B. This auto-encoder consists of an encoder ={=) that maps the representation to a discrete latent space of sentences, a latent prior Pw (w), and a decoder N (z:f(w)) that outputs the sufficient statistics of a Gaussian distribution order to evaluate the likelihood of the original representation. In practice, the latent prior Pw (w) can parameterized using an auto-regressive model such as a causal Transformer, which tends to work well on language data. We can then train this discrete auto-encoder using the following loss function:
((Zze.pwr))
-logp (ogp SEZ
Σ
(12)
The first term in this loss ensures that W has high prior likelihood, and optimizes both the prior model Pw well as the encoder that produces the latent sentences. The second term in the loss ensures that Z has high likelihood given W, and optimizes the decoder f' as well as the encoder e so that they preserve information about Z. Recall from Equation (7) that the negative likelihood of an object under some probability distribution is equal to its conditional Kolmogorov complexity given that distribution. As result, minimizing the loss in Equation (12) is equivalent to finding a Pws W, and f that jointly minimize K
( (W [w + K (f.....
Auto-regressive prior
& Pw())
Z EERNX
e
W E 7.NxM
Z ZERNXD
Representation
Encoder
Sentences
Decoder
Representation
1. Fit discrete auto-encoder with learned prior
2. Measure complexity terms
L
log Pw. log p (Z (WW))
K(Z) ((ww) KWW (Pw) K()) K(Z
Figure B.I. Estimating the complexity of a representation K(Z) by fitting a discrete auto-encoder with learned latent prior, The encoder, prior, and decoder are jointly trained with a loss that maximizes the likelihood of 2 using sentences that have high prior likelihood (WW).. pw and are also regularized to be simple functions, fitting this discrete auto-encoder equivalent to finding Pu.. W, and f that jointly minimize (2)).
To measure K (Z), we also need to minimize K (ppw) and K(f). For this, two options present themselves:
1. Hope that the implicit simplicity bias of DNNs trained using SGD does a good enough job on its own of finding solutions with low complexity (Blier & Ollivier, 2018).
2. Use additional regularization techniques that implicitly minimize the complexities of the models, such simple architectures, L1 or L.2 weight penalties, modularity (Goyal & Bengio, 2022), dropout (Hinton et al., 2012), periodic resetting (Zhou et al., 2021), etc.
Regardless of which method is used, the complexities of the final trained models can be estimated using method called prequential coding (Blier& & Ollivier, 2018), which we describe in Appendix H. Thus, are able to estimate all of the constituent complexity terms of ((Z) in Equation (1). The main challenge in this overall approach then becomes how to successfully train a discrete auto-encoder with a prior in latent space, in a way that is both stable and scalable.
The most popular method for training discrete auto- encoders is the Vector- Quantized Variational into-Encoder VAE) (Van Den Oord et al., 2017). While the latent prior in a VQ- VAE is generally trained post-hoc, some work has managed to train the prior end-to-end along with the rest of the model (Jones & Moore, 2020; Yasuda et al., 2021; Cohen
VQ-VAE
17

---

Towards Formal Theory of Representational Compositionality
al., 2022). The main challenge with VQ-VAES is that they explicitly discretize in the latent space during training-which is an inherently non-differentiable operation and then attempt to approximate gradients using imperfect estimators (Bengio et al., 2013; Jang et al., 2016). As result, training is often unstable and fraught with degenerate solutions that collapse in the latent space (Larccuci et al., 2020).
Simplicial embeddings Another option, which avoids the difficulty of training with hard-discretization, is to use so-called simplicial embeddings in the latent space (Lavoie et al., 2023). Simplicial embeddings amount to soft attention: each vector "chunk" " representing a word in the latent space is projected onto [ word embeddings followed by a softmax, and the weighted word embeddings are then summed at each sentence position. The temperature of the softmax can then be gradually decreased over the course of training such that the operation approaches sard-diseretization in the limit. As the operation entirely continuous and deterministic, it is easier to train using end-to-end gradient descent methods (although it may become numerically unstable at low softmax temperatures). One challenge becomes how to define and train the prior Pio in this case, where W is in fact a sequence of continuous word embedding mixtures as opposed to a sequence of discrete tokens. One possibility is to perform a hard-discretization of the latent hefore is passed to the prior, along with relevant gradient estimators (e.g. Bengio et al., 2013; Jang et al., 2016). While this could make training more difficult, the encoder-decoder part of the model would at least remain entirely continuous and deterministic. Another option is to define Pw: in continuous space, where the input is a sequence of word embedding mixtures and the "next-token" targets are categorical distributions over words.
GelowNets If we still wish to perform hard-discretization, but do not want to resort to imperfect gradient estimators required for end-to-end training, Generative Flow Networks (GFlowNets) could be a promising alternative (Bengio et al., 2021; 2023). GFlowNets can learn to sample some compositional discrete object in proportion to a reward function. The reward function and GFlowNet can also be conditioned on some input, and the reward function can be learned in alternation with the GFlowNet using sepectation-maximizzae
(GFlowNet-EMI) (Hu et., 2023). In the case of discrete auto-encoder, the encoder would be GFlowNet, while the decoder and prior would be the reward function. While this approach has been used to train a discrete auto-encoder before (Hu et al., 2023), it comes with its own challenges. First, GFlowNet-EEN is not an end-to-end training procedure (no gradients flow from the decoder to the encoder), which makes it more difficult to train. Second, while GelowNets sample proportionally to their reward, our ultimate goal is to maximize the reward (i.e., find sentences W that maximize the prior and reconstruction). To do this, we will ultimately have to decay the temperature of the reward over the course of training order to settle a final solution that minimizes the loss in Equation (12). Training GFlowNets with a sparse reward, however, is more diffieult due to exploration challenges (Atanackovic & Bengio, 2024).
Computational complexity the discrete auto-encoder described in this section can be trained successfully, then estimating representational compositionality is tractable, despite being defined theoretically in terms of Kolmogorov complexities. Fitting the auto-encoder itself is tractable using modern machine learning hardware. Then, to estimate K (Pw) and K (f) we must use prequential coding (see Appendix H), which amounts to fitting neural network at varying dataset sizes. While fitting neural network N times (where N is the dataset size) is inefficient, it is nonetheless tractable, and can be approximated efficiently by chunking the data into coarser sizes as we did in our experiments. There are also methods for computing prequential coding online rather than retraining the model from scratch each iteration (Bornschein et al., 2022).
C. Assumptions in compressing a representation
In laying out our framework for measuring K K(Z) in Section 2, we made several key assumptions.
First, we assumed that the shortest program that outputs Z has particular form. If it does not, then the estimated K K(Z) can be far greater than the true one. However, we argue that the assumed program form is safe for the kinds of representations that we are interested in and the kinds of insights we wish to gain from estimating K K(Z). Namely, we are interested in seeing if given neural representations share similar properties to conscious human thought, which is believed to have a symbolic structure where each thought is composition of discrete concepts (Fodor, 1975). If a representation does not have this kind of structure, then our method would detect it in the form of high estimated K (()), even if this is overestimate of the true Kolmogorov complexity due to incorrectly assuming the program form in Section 2.
Second, actually estimating K( (Z) using Equation (1) requires minimization over Pw. W. and f. This optimization approach assumes that the P.. and f which minimize K (Z) are DNNs. While this can seem unintuitive at first given the significant number of parameters in DNNs, it has been found that they converge to solutions that are remarkably simple and compressible (Blier& & Ollivier, 2018; Goldblum al., 2023; Sutskever, 2023; Rae, 2023), which likely explains their strong generalization
18

---

Towards Formal Theory of Representational Compositionality
abilities. We therefore believe that for neural representations with sufficient complexity, the assumption that they can be best compressed using DNNs is justified.
D. Examples of compositional representations
To supplement and clarify the arguments in Section 3, it is easiest to gain further intuition for our definition of compositionality through concrete examples of different hypothetical representations. For each, we have strong intuitions about whether or not the representation is compositional, and we will see that our definition agrees with and indeed extends these intuitions. We illustrate these examples in Figure D.1.
Example 1, (()) f'is a lookup table from w to
Example 2, 1 C())
Example 3, J C())
Z is smooth and continuous
Z is simple
bab
388
aab
bba
bas
abb
aba
~ -(p. E)
bibb
o(K()) - M7
Error (Z [W, f ) large
Expressivity K (Z. ) low
Example 4, C(Z) f uses word embeddings
Example 5, t C(Z)
Example 6, (Z)
f is modular
f has equivariances
a8a
aab
baa
bab
!i
#1
bbb
6(K ())) |?|
6( i)
Σ (())
6 (f
Σ (8))
Figure D. Examples of different representations and their compositionalities according to C(Z). Example 1. A representation whose clusters lack any structure has semantics f that map w = arbitrarily using a lookup table, resulting in high K KJ) and low C(Z). Example A representation that is smooth and continuous cannot be compressed as a function of discrete parts without incurring significant prediction error, resulting in high K (Zl f) and low C(Z). Example 3. A representation that cannot express many different things (thoughts, visual scenes, ideas, etc.), such as one that is sampled from unimodal distribution, has low K ((2) and low C(Z). Example 4. A representation that can be described by assigning word embeddings which are then processed using a simple operation (c.g.. concatenation. as in disentanglement) has low K(J) and high CZ)). Example 5. A representation whose semantics can be compressed using a small number of simple and reusable modules has low K (f) and high CZZ). Example 6. A representation whose semantics have large number of symmetries, or equivariances, has low KJJ) and high C(Z).
Example 1, J C(Z): f is a lookup table from w to Consider a representation Z that is sampled from a mixture of Gaussians, where the centroids are far apart but their locations lack any kind of structure (i.e., they are randomly distributed). To simplify things, let us assume that there are as many unique centroids as there are possible sentences. In such a case, the semantics function ff would identify each centroid with a unique sentence and the resulting error K (Z W),, would be low. However, because these centroids lack any structure, f would have to define an arbitrary mapping from each sentence to its corresponding centroid. In other words, ff would function as a lookup table from w to that does not leverage the internal structure (i.e., words and their ordering) in the sentence to achieve a more compressed mapping. The resulting description length of f would be equal to the size of the lookup table, which would grow exponentially with the sentence size. f would be, in effect, a complex "hard-coded" mapping (in fact, the most complex possible) with O (f)](())())))))) where M is the sentence length and | is the vocabulary size. The resulting compositionality C(Z)) would be extremely low.
Example 2, I C(Z): Z is smooth and continuous discrete structure that could be accurately modeled by sentences, and the source of low compositionality came from a high
The above example considered a case where the representation had
19

---

Towards Formal Theory of Representational Compositionality
K()). However, the compositionality can also be low if Z is inherently continuous, in which case modeling it using discrete Wi is at best an approximation via quantization. In such a case, the error K (Z(W.f) would be high and the corresponding compositionality would be low. Note that it might be possible to compress Z using low-dimensional continuous code rather than discrete sentences, from which an equivalent (perhaps even identical) definition of continuous compositionality could be derived, but in this work we consider only compositions of discrete parts.
Example 3, J C(Z): Z is simple Most of the discussion thus far has focused on the denominator of ((Z) in Definition 2. However, a representation can also lack compositionality if the complexity of the numerator, K (Z), is low. If Z were very low-say it were a constant, for instance-then it could be modeled using a simple f that achieves low error KZZ)W,)) However, we would certainly not be tempted say that the representation compositional. In fact, it would be best compressed using a single word and an f that outputs a constant, rather than using complex sentences and simple compositional rules. Compositionality must therefore also increase with the expressivity of the representation, which is captured by the numerator (2) in our definition. In cognitive science, where the scientific notion of compositionality has its origins, expressivity is considered an essential component of compositionality; Chomsky (1956) famously argued that natural language as a compositional system derives its power because it gives us "infinite use of finite means", or in the language of our definition high expressivity as a simple function of parts.
Example 4, tC(Z): f assigns an embedding to each word followed by a simple operation We now turn to paradigmatic examples of high compositionality, beginning with the most intuitive. Consider once again a representation Z that is sampled from a mixture of Gaussians like Example 1, but this time imagine that the centroids are arranged in a structured way. In particular, imagine that they are structured such that each can be described as concatenation of subcomponents that are shared across all centroids. Now, the simplest f would be one that first assigns a vector embedding to each word such that it represents a possible subcomponent of the centroid, and then concatenates the embeddings for all words in the sentence. The complexity of f would then scale only linearly as a function of the number of words in the vocabulary (assuming they are all necessary), because concatenation is a simple operation that takes a constant number of lines of code. We would have (((())== [V]. which is independent of the sentence length, in contrast to the arbitrary mapping in Example I that scaled This is substantial reduction in complexity and increase in compositionality, and it comes from the fact that the words contribute independently to the representation. This a case of a perfectly disentangled representation, which in our theory is simply an extreme case of compositionality, but intermediate cases are possible as well. For instance, the representation could be determined by interactions between pairs of words in the sentence, or it might be the case that words largely contribute independently to the representation but that there is some small degree of context-sente sensttiitnstiiiity as in human language. Our theory unifies all of these cases under a single, succinet definition.
as (((())== =
Example 5, 1 C(ZZ) f is modular As already explained in Section 2, modular f is simpler to describe and thus implies higher compositionality. To see why modular functions are more compressible, consider a paradigmatic case: computer programs. When a computer program is written in such a way that it can be refactored into a small number of functions and classes that are reused several times, the total length of the program decreases substantially. Programs that are not written with modularity in mind tend to be much longer and complex. Modular functions therefore tend to have far lower complexity because the modules only need to be defined once, but can then be reused many times inside the function. In ML, modularity is leveraged in a similar fashion. For instance, Goyal et al. (2021) introduces architecture that consists of N DNNs as well as a learned attention based routing mechanism for how they communicate. Crucially, these modules are leveraged by the routing mechanism in a context-dependen way, and each module can be reused many times to process each individual input. This means that while the entire model is simple (small number of modules and simple routing mechanism), it is nevertheless highly expressive due to the combinatorial way in which modules can be composed. Our definition explains how this expressivity and compression endowed by modular functions formally relates compositionality (Lepori al., 2023; Goyal & Bengio, 2022).
Example 6, CC()): f has many equivariances The connection between equivariance and compositionality is perhaps less obvious (Gordon et al., 2020), but it a natural and intuitive consequence of our definition. Equivariances (and invariances) symmetries sources of structure that decreases the complexity of function (Immer et al., 2022; Wilk et al., 2018; van der Ouderaa & van der Wilk, 2022). For instance, convolutional layers have local connectivity and reuse weights across spatial loca- tions, which both reduces their description length and makes them equivariant to spatial translations. We can also consider linear equivariance as a special case that is easy to illustrate. If f is linearly equivariant to a particular operation g in sentence-s -spcce,,,e,,,,,.eeee it means that fg((w) =0 fww)((()))) +gg. where by is a constant vector that corresponds to the equivariant change in the representation output by f. The difference in the function's 's behaviour for two different inputs, w and g(w), can therefore be compactly de-
20

---

Towards Formal Theory of Representational Compositionality
scribed by single vector, whereas in the general non-equivariant case the change in the function's behaviour can be arbitrarily complex. In an extreme case, if f can be completely described by a set of linear equivariances, then each w corresponds to set of gi ss applied to a constant "default" sentence, and f merely needs to encode a single vector for each of these gi 's then sum those that apply to particular input. The resulting function is very similar to the one described in Example 4, where f applied a simple operation to a sequence of word embeddings in a sentence (in this case vector addition). The function also bears similar- ities to the one described in Example if we view the equivariances as modules. Similar arguments can be made for non- non-linear equivariance, where the complexity (J) would still be reduced, but to a lesser extent. In general, the more equivariances a function has and the simpler those equivariances are, the lower the complexity K ((f) and the higher the compositionality CZZ).
E. Synthetic representations: varying both sentence length and vocabulary size in lookup tables
In Section 4.1 when discussing our results on synthetic representations generated from lookup tables, we argued that sentence length and vocabulary size should have a joint impact on compositionality. Namely, if the vocabulary is too small relative to sentence length, then expressivity and compositionality are limited (e.g., with only one word in the vocabulary, nothing can be expressed). On the other hand, if the vocabulary too large relative to sentence length, then compositionality is low because expressivity doesn't come from combining constituent parts (e.g., with one-word sentences and large vocabulary, there is no notion of parts). A good quantitative definition of compositionality should capture this intuition. In Figure 1. we demonstrate that our definition of representational compositionality reproduces this result empirically: as sentence length grows, the vocabulary size that maximizes compositionality does as well.
Compasiionallly
10' Vocabulary size
10¹
Figure F. Compositionality C(Z) for seathettcallly-geerattee lookup table representations a function of both vocabulary size and sentence length. As in Section 4,1, lookup table representations are generated by uniformly sampling sentences of particular length and vocabulary size, and mapping individual words vectors in a lookup table, followed hy concatenation. As sentence length grows, the vocabulary size that maximizes compositionality does as well. Note that for clarity, vocabulary size is shown on a log scale. Vertical lines show peaks. Error bars show a over 10 seeds.
F. Relations between representational compositionality and other ML topics
Compositional generalization One of the benefits of compositional representations is that they enable better compositional generalization (Lake & Baroni, 2018). a model is compositional with respect to a set of features in its training data, need not observe all possible combinations of those features in order to generalize to novel ones (Schug et al., 2024; Wiedemer et al., 2024; 2023; Bahdanau et al., 2019; Mittal al., 2021; Hupkes et al., 2020; Jarvis et al., 2024; Lippl & Stachenfeld, 2024; Lachapelle et al., 2024). For instance, if an image classifier's representation is compositional with respect to foreground objects and background scenes, then it should be able to correctly classify an image of "a cow cow after having only observed cows and beaches separately at training time.
on a beach" at inference time
In certain cases, compositionality is defined in terms of a model's ability to compositionally generalize compositionally (e.g.. Jarvis et al., 2024; Wiedemer et al., 2024; 2023; Lippl & Stachenfeld, 2024). However, while such definitions of compositionality can often provide theoretical guarantees on generalization, they also place strong assumptions on either the representation, the downstream model, or both. For instance, Wiedemer et al. (2023) assumes that the representation is perfectly disentanglement with respect to some underlying task constituents. Similarly, Lachapelle et al. (2024) assumes disentanglement and that the downstream function using the representation is additive with respect to the the disentangled factors, and Lippl & Stachenfeld (2024) assumes disentanglement and "conjunction- wise additivity".. Wiedemer et al. (2024) takes from the object-centric learning literature and defines a compositional representation as one that is structured into distinct "slots" (Locatello et al., 2020), and then requires that the downstream model using these slots is additive.
In contrast, our definition of representational compositionality is far more general: it defines compositionality in terms
21

---

Towards Formal Theory of Representational Compositionality
of compression, which abstracts across the architecture producing and using the representation, learning details, data requirements, and particular representational format. For instance, disentangled and slot-wise representations are particular cases of representational compositionality in terms of their simple semantics K (f) (see Appendix D), but these are rigid assumptions to build into a model that might negatively impact performance. In contrast, representational compositionality has the potential to explain the success of more varied and flexible methods in terms of compositional generalization, such as loss regularizers or simply scaling dataset and model size.
As a consequence of its generality, it may be difficult formally characterize the relationship between representational compositionality and compositional generalization with theoretical guarantees, and we did not attempt to do so in this paper. Nevertheless we hypothesize that representations with high (() should enable better compositional generalization. This is because the representation of constituent parts is systematic: the semantics mapping constituent parts to the representation is a simple function that will generalize better to novel part combinations (i.e., it will assign them meaningful rather than arbitrary representation, which downstream functions should be able to leverage). One of our central goals for future work is to test this hypothesis empirically, where we measure the compositionalitie of many model representations using our definition and then correlate this score with the models' compositional generalization abilities.
Generative models in latent space In addition to compositional generalization, representational compositionality also relates to generative models that sample in latent space. In particular, once a compositional representation is learned, efficient and generalizable generative models can be constructed by sampling in the space of discrete sentences, rather than in the high- dimensional continuous latent space directly. This is because the semantics function / of a representation with high C(Z) is sim- ple, and can generalize to novel sentences that the generative model might produce. Empirically, modeling and sampling from discrete distributions is often easier and more effective, especially for complex multi-model distributions (Razavi et al., 2019).
To give a concrete example, imagine that a vision model has been pretrained on some task like object classification and produces latent representations with high (Z)). Using this representation, we can train a generative model of the form 2~~ pw (w) (z: (w)) described Section 2. and then generate novel samples for downstream visual reasoning tasks directly in the abstract latent space, rather than in the low-level image space. This is similar to thought and reasoning involved in human cognition, which generative processes believed to exhibit a discrete language-like structure (Fodor, 1975; Dehaene
et al., 2022; Lake et al., 2017; Bengio, 2017; Goyal & Bengio, 2022).
G. Inductive biases for representational compositionality
In virtue of being formally precise and quantitative, representational compositionality can inspire the design of novel inductive biases for compositional representations in MI. models. In this section, we outline two approaches that we believe have promise: one that directly optimizes for C(Z), and another that indirectly attempts increase it through task and data constraints. In addition, C(Z) can be used to validate existing inductive biases for compositionality (e.g., architectures for object-centric representations Locatello et al., 2020).
Regularizing W)) The most direct way to learn representations with high C(Z) is to regularize the denominator K(Z so that the representations become more verbalizable, as suggested in Bengio (2017) and Goyal & Bengio (2022). Definition 2 says that compositional representations are (a) expressive and (b) easily described using sequences of discrete symbols-in in other words, that they are verbalizable like human thoughts that can largely be conveyed in natural language. Expressivity can be obtained simply by training on a sufficiently complex task; for example, representations for image classification need to be expressive so that they can discriminate different objects. Task pressure alone, however, does not guarantee that the representation will be verbalizable. This second desiderata can be achieved, however, through prior that regularizes the model's loss function.
Say that some model ge produces representation Z xX) of inputs X. Verbalization corresponds to minimizing the denominator in Definition 2: K K(ZW)) = K(J)+ + K(),,,). Crucially, W and here are obtained from the shortest program that outputs Z as described in Section 2, which can be approximated by optimizing a discrete auto-encoder who's 's training scheme is sketched out in Appendix B. To make the dependence of W and f on Z more explicit here, we will use the superscripts 7 and f² If we wish to increase verbalizability (and therefore compositionality), we therefore need to perform some update update 0 - 8' such that:
22

---

Towards Formal Theory of Representational Compositionality
(13)
where Z' =0= (X). One option for accomplishing this is by backpropagating the reconstruction error of the discrete auto- encoder, K (Z]W2, f²). This approach assumes that the semanties before and after the update are unchanged (i.e., fz f2). so that the only thing that needs to be considered is the auto auto-encoding reconstruction error K KZZ - K(Z' )
While this assumption will be violated in practice, it may hold approximately such that regularizing reconstruction error alone is sufficient to increase compositionality.
In sum, the approach described here consists of training a DNN go (X) on some task as usual, but with an additional loss: a discrete auto-encoder is fit to a layer in the model which we want to be more compositional, and the 0 regularized to minimize the loss of this discrete auto-encoder. As result, in addition to subserving task demands, the representation is optimized to be more compressible as a function of constituent discrete parts (i.e., it is verbalizable).
Multi-task training A common observation in deep learning is that the model representations after training tend to be surpris- ingly simple despite the significant number of parameters in the network (Blier & Ollivier, 2018), as evidenced by their strong fid generalization abilities. However, absent additional constraints (e.g. Lachapelle et al., 2024), these same representations do dittrf--ditiibution generalization, suggesting that they lack sufficient compositional structure. One
not enable compositional hypothesis is that while the simplest representation used to solve a single task may not be compositional, the simplest representa- tion used to solve many related tasks might be. An analogy can be made to computer programs. When a program is written for a single narrow purpose, writing it in a compositional manner that reuses shared functions and classes might in fact result in bloat that increases the total program length. However, if these same functions and classes constitute useful library that can be lever- aged to write other programs well, significant compression might be possible because the library is shared across all programs.
In the terminology of C(Z), learning the simplest representation that subserves many different related tasks might result in low K(Z)W) and high compositionality because the semantics ff are shared across these tasks and therefore lead to high compression; only K (pw) grows to accommodate additional tasks, analogous to how a programming library would be used in novel ways write a new program. Since DNNs already tend learn simple representations (Blier & Ollivier, 2018), our definition suggests that ordinary training in certain multi-task settings (those that reuse certain task components) might be simple method for learning compositional representations. Indeed, this has long been hypothesized and observed empirically (Driscoll et al., 2024; Johnston & Fusi, 2023; I Lachapelle et al., 2023; Vafidis et al., 2024a; Maziarka et al., 2022; Vafidis et al., 2024b), especially in the case of disentangled representation learning, and could be verified more formally using our definition of representational compositionality.
H. Prequential coding
While the Kolmogorov complexity of model K (po) is difficult to measure directly, it turns out that we can can jointly estimate ((Dpps) + K (pa) in cases where the model was fit to the data using a learning algorithm, as is the case in ML. From Equation (6), we have that:
K(p))
(14)
Instead of trying to estimate the terms on the LHS directly, we can estimate the RHS by finding the shortest program that jointly compresses both the dataset and the model, which we turns out to be casier through a compression algorithm called prequential coding illustrated in Figure H.1 and described below.
Prequential coding first assumes that we have access to a learning algorithm T which was used to fit the model pe. For instance, Pe= TD)) might correspond to randomly initialized DNN architecture fit to D using SGD with some set of hyperparameters. Then, consider an ordering of iid datapoints D (D1,. [D.....Dx), }, and denote 1:: = DD...., D.). In prequential coding, the first datapoint D1 is hard hard-coded in an uncompressed form, which takes a large number of bits. The learning algorithm 7 is then used to train model pa, = ( on this single observation. Because the model is trained on only one datapoint, it will not be very accurate; however, it should be better than a random model that has seen no data at all. Because of the relationship between probabilistic generative models and compression described in Appendix A, we can use this model to specify the next datapoint D2 in a compressed form using only- - loggpe, (D2) bits. At this point, we have encoded 2 datapoints, on which we can train new model po, =D(2..)). Having seen more data, this model should assign a higher likelihood to a
23

---

Towards Formal Theory of Representational Compositionality
a. Proquential coding to compress D def construct_] D_ and TT]_
b.
N-1 Σ
1preg(D: (D:T) TT:
log2 (D((1)
== [I Starting off without any data
1=0
for rangolO. N):
8 Train model on all the data so far p T:D)
Generalization c Simplicity
-log, (+))
# Specify the (encoded) next datapoint
D next encoded = [..] 8 K -og((p(D__ext))
K (pp)
Extend the datuset after decoding with
K (D Ipg)
D + decode D_ coockedddddd.p) p)
2
3
5 6 Data index i
9
return T(D)
Figure H. Illustration of prequential coding, a method for estimating =(D,0)= [ +K a. Pseudocode of the prequential coding program that outputs both and ps. The program jointly compresses D and ps by incrementally training a model using' I on increasingly more data, each time efficiently encoding the next datapoint using the model obtained from all previous ones. The primary sources contributing to total program length come from specifying each next datapoint D:41 in compressed form using the current model po,, which takes - -loggPo, (D++1) bits. b. A visual illustration of the number of bits needed to specify each next datapoint given the model that was trained on all previous ones. As the learner T sees more data, outputs models that assign a higher likelihood to new observations, and can thus better compress them. The total prequential code length Lpreq ( (D;T") is given by the area under the curve. The area underneath the curve's last point is equal to the number of bits needed to encode the entire dataset given the final model. K (D) (p)). Since Lpreg (D:T)= K (Dlps) K (pe)). the area above the curve's last point is equal to K (ps). Prequential coding formalizes the intuition that simple models generalize better, thus quickly decreasing their prediction error for the next datapoint.
using pe 's learningalgorithhn T.
new datapoint D3, which we can specify in compressed form using -loggPo, (Da) bits. This process repeats until the entire dataset has been generated. At this point, the model pe can be obtained simply by applying the learning algorithm to the complete dataset pa = T(D,, since we assumed by construction that this was where the model came from.
The total number of bits that takes to jointly compress D and py using prequential coding is the sum of how many bits it takes specify each next datapoint using a model that was trained on all previous ones. Visually, it is the area under the prequential coding curve shown in Figure H.lb. We can call the total length of this compression program the prequential code length Leprag D)T) (Blier & Ollivier, 2018):
N-1
I.pray (DTT= = Σ
loggPo, (D (D++1)
(15)
Lyreg (D:T) > x( K(Dpp))+
(16)
Strictly speaking, Iepreg(1))) (D;T) is an upper-bound K K(D (DDpo)) the prequential coding algorithm is one way to jointly compress the data and model, but it is not necessarily the optimal way. The upper-bound is tight in practice, however, if (a) the final model K(D (D Po) < K (D)) and (b) passing data to the learner T through the prequen- tial coding algorithm is an effective strategy for compressing the model. Regarding this second point, consider how the model is obtained through prequential coding. Data is gradually transmitted to the learner T, with each additional datapoint requiring fewer bits to encode. If the speed of improvement in predicting the next datapoint is fast as a function of the amount of data ob- served, it means that the learner is effectively able to converge to the final model using only a small amount of data that takes few bits to encode, and thus that the model has low complexity. Concretely, when prequential coding a good algorithm for jointly compressing the data and model, then Lprey (D:T) (D:T) x= K (o) and the model complexity is given by (Blier & Ollivier, 2018):
Pa does good job of compressing the data (i.e., K
Lpreg K(po) ~ = -D,T)-K(Dlp))
(17)
Assuming that the model's error decreases monotonically with the size of the training dataset, K (Dlpp) is equal to the area under the lowest point of the prequential coding curve in Figure H. The area above this point is therefore the complexity of the model K (pe). This relates Kolmogorov complexity to intuitions about generalization in ML: the simpler a model is, the quicker it generalizes from limited amounts of training data.
24

---

Towards Formal Theory of Representational Compositionality
I. Synthetic representations- - experimnntal details
I.1. Lookup table representations
Generating the representations We generated our synthetic lookup table representations Z (and their ground-truth sentences W) according to the program summarized in Algorithm 1. short, the program does the following:
Generate a lookup table: We begin by constructing a lookup table from words (or n-grams) to their embeddings. This table has dimensions (K',, .xgg ). where K is the vocabulary size, g is our disentanglement factor (i.e., the size of the n-grams), and is the desired dimensionality of Z. We use the Skellam distribution to generate lookup table entries, which a discrete approximation of Gaussian distribution with precision λ. This discretization is necessary because continuous distribution would cause the correction term K (f. to be infinite.
D
Sample Wi We generate random integer sentences uniformly with shape (N,L), where N represents the number of samples and L denotes the number of words per sentence. Each integer in W corresponds to word from our vocabulary of size K.
Decode W to get Z: For each sentence w E W, we perform the following steps to obtain the corresponding represetttinnn sample E Z:
We divide the sentence into consecutive L/g subsequences, each representing an r-gram (or word y=
For each subsequence, we retrieve the corresponding embedding from the lookup table.
We concatenate these embeddings form the complete representation sample = for the sentence.
We then add Gaussian noise (discretely approximated by a Skellam distribution with mean 0 and standard deviation r for the same reason as above) to the representation. This introduces stochasticity to our representations that cannot easily be modeled with discrete parts. The final representation Z has shape (N,D).
Add noise:
Calculating the compositionality to calculate the following terms: K (pw), (W Ipw), K (f), and K KZ),,,f). We show how to do this below for a lookup table representation:
To compute representational compositionality C(Z) according to Definition 2, we need
K (pw): The language Pw in this case a uniform categorical distribution over integers in range (0,K 1) each sentence position I E (0-(M-1)), where K is the vocabulary size and M is the sentence length. To specify an integer u, need u bits, we have K (p..)) = log + Mogg.M. There is also complexity term associated with describing the function for the uniform distribution itself, but we ignore this because it is small constant.
(W'pww) As described in Section 2, K ((W(pw) Pw) is simply equal to - EN logz (w;). To derive (w:) for each sentence w; E W, we notice that each wy composed of L words, each sample from uni- form categorical distribution over (0, K 1). Thus Pw Pw (w;) R for each sentence w.- In total, then, K(W ( - - log2Pt. - Dy=,,oog k = MMog,, K bits.
1
K()): In this case, the function that maps sentences to their meanings is mainly composed of the lookup table, with some additional small constant complexity to describe how to use the lookup table. To describe each number a in the lookup table, we need - -log2P(a) (a) bits, where is the PMF of the distribution these numbers were sampled from. In our case, this distribution is the Skellam distribution with a mean of 0, a standard deviation of 1, and a precision of X. We therefore have K K(J)= = Eaglookkp ta (ag. Given that the size of the lookup table (K", >1/7g)) )), the complexity of the semantics K(f) grows linearly in D. polynomially in K, and exponentially in
K (Z(W,,) This term comes from imperfect reconstructions of Z. can be thought of as the number of bits needed to correct the errors in these imperfect reconstructions. In these lookup table representations, these imperfect reconstructions come from the noise added to Z when it is sampled, which cannot be recovered since the lookup table does not contain it. To describe the corrections, we therefore just need to describe this noise. Each noise sample can be described using -log24(c) (c) bits where is the PMF of the distribution the noise was sampled from. In our case this is a Skellam distribution with a mean of O, standard deviation of r, and precision of X. If we let E be the matrix of all noises added form Z, we have that K K(Z (Z..)) equal to _ogggog,9()))
25

---

Towards Formal Theory of Representational Compositionalit
Algorithm 1: Sampling Z using lookup table program
Input:
number of samples N
sentence length M vocabulary size K embedding dimension D disentanglement factor quantization precision noise ratio r
Generate lookup table:
lookup table e skellam sample(u=0,0== X,shape
D (79) :M7g
II Sample W: W + rerrradd_mnteeee Boaadoomittege((O.. 1.shape=
Decode W to get Z:
Z +-
for each in W do
2+
for position = 0 to (M/
entry + (w pposition x position x - 1])
end for
+ concatenate(2
Z. (apppdd(
end for
7 < stack ?)
11 Add noise:
if r 0 then
noise+ +- swellkk skellam_sampe((u=000 =r, s,sapp Z.shape)
Z noise
end if return Z
Combining these complexity terms together, the final expression for C(Z) following Definition 2 is:
C(Z) K(Z) K(pw. +K( KK)) K(ZW)
k(1)+K(2WW.))
logg K +logg M + N Mog, K -- Eoelookppaatee -
- Eaelookup table logzp(a) -Eccplogg(ee
Experiment parameters We used the following parameter values to generate representatiion (except when sweeping parameter while keeping the others constant): N 1000, M 16, 1= D D= 64, 1=,, 0= 0.01.. To sweep over sentence length, we varied M from (1,D), only keeping values where 1) was divisible by M. To sweep over vocabulary size, we varied from (2,100). To sweep over representation dimensionality, we varied from AM.2M,..,110.MM. To sweep over disentanglement, we varied q from (1,M), only keeping values where M was divisible by For each setting of experiment parameters, we generated representations across 10 different random seeds.
26

---

Towards Formal Theory of Representational Compositionalit
1.2. Context-free grammar representations
Generating the representations We generated our context-free grammar representations (and their ground-truth sentences W) according to the following procedure:
Generate a context-free grammar: Our context-free grammars consist of exclusively binary production rules that combine two child non-terminals into parent non-terminal. We define vocabulary of size K and evenly assign each word one of T possible base part of speech types that serve the first non-terminal symbols in the context- grammar. We call these T first non-terminals "terminal parts of speech". We algorithmically generate the grammar in a way that depends two parameters: the width and the depth. The depth refers to the number of levels in the parse tree (above the parts of speech) that have unique non tenmeralanll symbols which can only exist at that level. The width h refers to the number of unique non-terminal symbols defined at each level of depth. At any given level of depth, we generate a production rule for all possible combinations of non-terminal at that level, each of which produces one of the possible non-terminals at the next level (we evenly distribute outputs across these possible non-terminals the higher level). For arbitrarily long sentences still have valid parses despite the finite depth of our grammar, we define additional recursive production rules that take non-terminals the highest level of the grammar and produce of those same non-terminals. To provide additional clarity for how generated these grammars, give an example below for 7 = 5, wi hth 2, and depth = 5 (we exclude the vocabulary for brevity). In this grammar, the terminal parts of speech are denote by the prefix "T_" and other non-terminals are denoted by the prefix "r[depth level]_".
start: r2
r2 2
r0.1: T.1
T.2
T_2
T_3
T.3 " 4
T 4
T 5
T "
T.I
r0.2: T_1 " T_3
T_2 " T_4
T.3 " T.5
T_4 " T-1
T.5 " T.2
rl.1: r0_1 " r0.1
r0.2
r0_1
r1.2: r0_1 "" r0_2
10.2
r0_2 10.2
rl.1 12.1: rI_1 " rl.1
r1_2 rl.
rl_1
r2_ "" r2_1
r2_2 "" r2_1 121
r2 2: r1 " r1
r1 " r1
r2_1 12-2
r2.2
12_2
Sample W: We generate random integer sentences of length M based on a transmission sentence defined over terminal parts of speech. Denote a terminal part of speech by / 1..T. A sentence w always randomly starts from a word that has either t = or == 2 with equal probability. Permissible transitions to the next word's ''' terminal part of speech are 4+1 4 1 4.41 + +2, which we sample between with equal probability (we also wrap 44+1 so that remains in range 1..7'. Given a sampled terminal part of speech at location in w, we randomly sample word that has been assigned that terminal part of speech.
Semantics f: The representation is assigned a dimensionality D. Each word in the vocabulary is given a D-dimensional embedding by sampling from a Skellam distribution, which a discrete approximation
Gaussian distribution, using #= 0, a == 1, and quantization precision A. For each production rule in the grammar, we define a linear mapping A, E D with values sampled from a Skellam distribution using 0= a and quantization precision Given sentence w, the semantics function f is defined by the following steps:
Parse to using Earley parser (Earley, 1970) implemented with the Lark Python package.
Retrieve the embedding for each word in w.
Hierarchically apply the function [x1, A; at each node in the parse tree to obtain node embedding, where [x]] are the concatenated embeddings of the child nodes and A; is the linear transform of the production rule the node. The embedding of the root node is taken to be 2 for the sentence.
Add noise: We then add Gaussian noise (discretely approximated by a Skellam distribution with mean and standard deviation r) to the representation. This introduces stochasticity to our representations that cannot easily be modeled with discrete parts. The final representation Z has shape (N,D).
27

---

Towards Formal Theory of Representational Compositionality
Calculating the compositionality To compute representational compositionality C(Z) according Definition 2, we need to calculate the following terms: K(pw), (Wpp), K and f())W,)) We show how to do this below for a context-free grammar representation:
K (pw): The language Pw in this case is defined by a terminal part of speech for each vocabulary item and a binary matrix of permissible transitions between terminal parts of speech. Defining the terminal part of speech for each vocabulary item takes log,T bits, and we have K vocabulary items. The binary transition matrix is of shape (T 1) xT (where the + is for the grammar's start symbol), and so takes T(*+ 1) bits to define. The total Kolmogorov complexity of the language (ignoring code of constant complexity that doesn' 't scale with K or T) is therefore K (ppw)= 2
K (WWpp lpw): As described in Section 2, K (WW (pw) is simply equal to - - 1oggPP (w;). Since pw is defined by a transi- tion matrix over terminal parts of speech, and for each terminal part of speech each word having that terminal part of speech has equal probability, we have that piu (wx² = -I mi]] where (.)) is the set of all permissible next words m that the previous word wi,m-1 can lead to based on the transition matrix between terminal parts of speech, and w1,0 denotes the M
grammar's start symbol. We therefore have that K(W (WPp))= P-= 1og2P= = -E== m== log2 (i bits.
K(f): The semantics are defined by the parser, the production rule operations (linear maps), and the word embeddings. Both the parsing algorithm and the production rule operations scale in complexity a function of the number of production rules in the grammar, so we ignore the parsing algorithm's 's complexity and only consider the production rules and word em- beddings as the scaling behaviour is the same. To describe each number in the word embedding table a, we need -loggP(a) bits, where p is the PMF of the distribution these numbers were sampled from. In our case, this distribution is the Skellam distribution with a mean of 0, standard deviation of 1, and a precision of X. The complexity of the embedding table is therefore La emmbedding ubll log.p( a). Given that the size of the embedding table is (K x D)), the complexity of the embedding table grows linearly in both K and D. To describe each production rule i, we must describe a matrix of shape 2D x D. Each number in this matrix takes -log-p(v) (v) bits to encode, where p is the PMF of the distribution these numbers were sampled from. In our case, this distribution is the Skellam distribution with mean of O, standard deviation of 1, and a precision of X. The total complexity of all production rules is therefore - EEEum rules E ())))22x www.pploo.pp...oo (r..).))). -E
We therefore have that (ff)= -E aeembeddingg table toble logzp(a)
> Enum mless E (nejeeDD log,p (Ai.)(Ai.(rr))) bits.
K K(Z,W,) f): This term comes from imperfect reconstructions of Z. can be thought of as the number of bits needed to correct the errors in these imperfect reconstructions. In these lookup table representations, these imperfect reconstructions come from the noise added to Z when it is sampled, which cannot be recovered since the lookup table does not contain it. To describe the corrections, we therefore just need to describe this noise. Each noise sample can be described using (c) bits where is the PMF of the distribution the noise was sampled from. In our case this is a Skellam distribution with a mean of O, standard deviation of r, and precision of X. If we let E be the matrix of all noises added form Z, we have that K (2f) is equal to E.eglog,9(s
Combining these complexity terms together, the final expression for C(Z) following Definition 2 is:
C(Z) K(Z) ((w ) KKW (wWWle.)tH ((())
K(Z
K()+ K()+K(ZWW.1)
Klog, T T - M EM
loga [elwe 1)l
Σ
Lacembeclding table log2p(a) Σ
- tenumm rules E (irreeenDxDlogg/// -eeo (oep
ignum Lignmmules rules
Cagebeeddingg table log2p(a)
Experiment parameters We used the following parameter values to generate representations (except when sweeping one parameter while keeping the others constant): N = 1000, M = 16, K = 100, D= 10, T 5, width 3, depth= 2, 0=0001, r 0.01. To sweep over sentence length, we varied M from (1, only keeping values where D was divisible by M. To sweep over grammar width, we varied wi d from (1,4). To sweep over grammar depth, we varied depth from (1,4). For each setting of experiment parameters, parammeter,,,m,, we generated representations across 10 different random seeds.
28

---

Towards Formal Theory of Representational Compositionality
J. Emergent languages- - experimental details
Dataset construction To obtain emergent languages from multi-agent reinforcement learning in a simple object reference game, both with and without iterated learning, we used the code base from Ren et al. (2020), found at https: / //gitubb. com/ hta//Josuus seaa-Ree Ren/Neurze Iteraaa__reettee_e_e_e Learning. Objects consisted of 2 attributes with 8 possible discrete values each, for total of 8 -44 possible objects. Sentences similarly were of length 2 and had a vocabulary size of 8. We used the default values in Ren et al. (2020) for all model and training hyperparameters (refer to their associated code base for details). but reserved no held-out objects for separate validation. After training, we generated 50 sentences from the speaker agent for each unique object, giving us W and Z, respectively. The resulting size of these datasets were thus 50 x 8 = =3200.
Estimating compositionality Estimating the compositionalities of these different emergent language systems (z) requires estimates of the numerator (Z) and denominator ((Z W Both with and without iterated learning, Z consisted of the same enumeration over all possible discrete symbolic objects O. Each 2 Z can therefore be represented using a single integer indexing the object, where these integers range from {1..|0}} and therefore each require ((0) bits to encode.
Summing these bits over all objects gives a total of K (Z) = | [ (Ol).
We estimated K (Z) for each language using prequential coding (see Appendix H). The model architecture used for prequential coding was an MLP with with 2 hidden layers of size 256. Each word in WL embedded into a 64-ddimensional vector, and these concatenated embeddings were the input to the MLP. The MLP output logits over object values for each attribute. To estimate prequential code lengths more efficiently and avoid having to retrain the model N times (where N is the dataset size), we incremented the size of the dataset by chunks of size 50 at a time. We used the Adam optimizer with a learning rate of 1 x 10-3 -3 to train the model at each iteration of prequential coding. We reserved 400 datapoints for separate validation set that was used for early stopping at each iteration of prequential coding.
K. Natural languages - experimental details
Dataset construction We obtained English sentences from captions that were used to describe images in the Common Objects in Context (COCO) dataset (COCO, 2024), downloaded from Hugging Face. The reason for using a dataset of image captions was that we expected these captions to use common words and simple sentence structures, given their grounding in visual stimuli. For each image, the dataset contained two independent captions, and we kept only the first. This gave us total of 414,010 English sentences. We then translated each sentence to French, Spanish, German, and Japanese using a large open-source language model with 3.3 billion parameters (Costa-juse) et al., 2022). We visually inspected several of the French, German, and Japanese sentences (no authors spoke Spanish) to make sure the translations were reasonable, and we found them to be of high quality. These sentences constituted the W 's for our experiments. We obtained proxies for the "meanings" Z of these sentences by passing them through a large (278 million parameter), pretrained, multilingual sentence embedding model that output a fixed-size vector for each sentence (Reimers & Gurevych, 2020). Both the translation model and the sentence embedding model were obtained from Hugging Face.
Estimating compositionality Estimating the compositionalities of these different language systems (Z) requires estimates of the numerator (()) and denominator K (Z) While we did not estimate K (Z), we assumed that it was approximately equal among languages. This is common assumption in linguistics, where languages appear to be equivalent in their expressive power to express ideas, refer objects, etc. Fixing the numerator K (Z) to some (unknown) constant shared among languages allowed us to assess their relative compositionalities by estimating only the denominator K (Z))W>). We estimated K (Z) for each language using prequential coding (see Appendix H).
The model architecture used for prequential coding was the same as the one used to generate Z (Reimers & Gurevych, 2020). Learning a significant number of word embeddings from only xs 400,000 samples would have been difficult however. We therefore used the original model's pretrained word embeddings and only computed prequential code length by resets of the model's 's downstream weights, which encode the semantics of the grammar rather than the word meanings. Strictly speaking, then, we only estimated K ((Z)cnn embeddingg (W))). To estimate prequential code lengths more efficiently and avoid having to retrain the model R 4-4000000 times, we incremented the size of the dataset in chunks. Chunk boundaries were selected on a base-10 10 logarithmic scale from 1,000 to N datapoints (the full size of the dataset), with 15 interval boundaries. A logarithmic scale was used because we observed that next next-datapoint prediction error as a function of dataset size changed more quickly in low-data regimes and more slowly in high-data regimes. We could therefore more accurately estimate the true prequential coding curve using a logarithmic chunking scale that had higher resolution in low-data regimes. We used the Adam optimizer
29

---

Towards Formal Theory of Representational Compositionalit
with learning rate of x 10 to train the model at each iteration of prequential coding. We reserved 10,000 datapoints for separate validation set that was used for early stopping each iteration of prequential coding.
Limitations Our approach for measuring the compositionalities of real-world language systems has several limitations that should be taken into account when judging the results. First, the translation model that we used may not have been trained on equal amounts of text from the different languages we studied, which could have lead to lower quality translations for some languages compared to others. Similarly, the multilingual sentence embedding model that we used may have not been trained on equal amounts of data from the different languages, leading to lower quality embeddings for some languages compared others which could have impacted the quantity and accuracy of "true" sentence meaning captured in Z. Indeed, for these reasons we did not include the original English language sentences and embeddings in our experiments (we thought it very likely that the sentence embedding model had been trained on far more English text compared to other languages). Finally, the use of pretrained sentence embeddings as a proxy for sentence meaning Z is likely flawed. The sentence embedding model that we used is trained with invariance- basteddeeeeeeddddee self- self--upereised methods, and the resulting representations are unlikely to capture the full scope meaning that would be represented in human brains processing these sentences.
30


Reviews:
[{"review_id": "4gp0u51fen", "reviewer": "Reviewer_JsGE", "summary": "This submission frames compositionality as a quantitative measure of how compressible a representation is into a specific family of probabilistic models. This quantitative measure of compositionality is tested in three settings: One in which the generative model of the data is known and specific parameters can be controlled, and two in which it is not known.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the constructive review.\n\n**Tempering our claims**\n\nReviewer q4Av made a similar comment—in retrospect, we agree. While we believe that existing definitions of compositionality suffer from significant pitfalls which our definition addresses, it is unfair to claim that ours is the first to rigorously define compositionality and premature to claim that it is the “true” or most useful definition in all circumstances. It is also premature to claim that it has the potential to dramatically improve AI models, and such claims are best left for future work that actually attempts this. We plan to edit our paper accordingly in the following ways:\n\n1. Remove premature claims in the abstract and elsewhere that frame the definition as uniquely “correct”, being “the first formal definition”, or having the potential to dramatically improve AI.\n2. Add a new section “Comparisons to prior work” that systematically compares our work to other definitions of compositionality that have been proposed, pointing out both advantages (e.g., generality, no assumptions on the structure of $f$) and limitations (e.g., computability, sensitivity to modeling choices in practice). This should help provide a neutral framing of our specific contributions.\n3. Add a new section discussing additional “Limitations” of our definition.\n\n**Discussing additional references**\n\nThe Chater and Feldman references are only tangentially related, as we don’t define compositional representations as simple (only that they can be compressed as a simple function of parts)—i.e., $C(Z) \\neq K(Z)$. However, we will add these references when discussing compression more broadly (paragraph on “expressivity and compression”).\n\nThe Adriaans & Jacobs reference is highly relevant as it pertains to finding simple grammars that explain data—the function $f$ in our framework—which is required to compute $C(Z)$. Thank you! We will include this.\n\n**Advances upon Kirby et al.’s work on compositionality**\n\n1. Our definition provides a formal and quantitative framing of ideas in Kirby’s work, clearly defining what is meant by a language (symbols $W$, meanings $Z$, and their mapping $f$), effective communication (high $K(Z)$ that can represent many things, low information loss during communication $K(Z|W, f)$), and language simplicity (low $K(f)$). Lines 196-202 RHS made this contribution explicit, but we will make this more central throughout the paper (especially in the abstract, introduction, and discussion) so that readers understand how we are building on existing literature.\n2. Kirby’s work presents ideas around the compositionality of *language systems, or mappings from a given* $W \\rightarrow Z$, which pertains to our $C^L(Z)$ definition. In this sense, $C^L(Z)$ is a drop-in replacement for topological similarity*.* While this is relevant to natural language, it is not directly applicable to questions about the compositionality of *representations, where only* $Z$ *is given*, such as in testing the Language of Thought hypothesis. Our definition $C(Z)$ (but not Kirby’s theory or topological similarity) remains applicable in this case.\n\nIn our revisions, we will summarize these points.\n\n**Interpretation of natural language results**\n\nThe motivation for the natural language experiments is stated on lines 386-392 LHS: it is unknown whether different languages are equally compositional, partly because we lack principled definitions of compositionality. We therefore took this as an opportunity to apply to our definition to a real problem in linguistics. Our results in Fig. 4 suggest that these natural languages are roughly equally compositional. We will edit our paper to relate these results back to the original motivation for the experiment. We also wanted to show how another measure often used as a proxy for compositionality of language systems, topological similarity, gives different and counter-intuitive results.\n\n**Other comments**\n\n> I think you mean [a discrete approximation of the Normal distribution] \"can be used\" instead of \"must be used\"\n> \n\nYes, thank you; we will correct the text.\n\n> Did you collect the [English sentences] dataset? Or did you make use of it?\n> \n\nWe made use of the existing dataset; we will correct the text.\n\n> Isn't compositionality always about representations?\n> \n\nIt is discussed more broadly in the literature, or at least would require a much broader notion of “representation” than the one used in our paper. It is sometimes about data [e.g., 1], functions [e.g., 2],  or mappings from externally-defined latents to a representation as in $C^L(Z)$ [e.g., 3]. We can clarify this in the text to better situate our definition in the broader AI and cognitive science communities.\n\n[1] Aitchison 1982. The Statistical Analysis of Compositional Data\n\n[2] Lepori 2023. Break It Down: Evidence for Structural Compositionality in Neural Networks\n\n[3] Ren 2023. Improving Compositional Generalization Using Iterated Learning and Simplicial Embeddings", "claims_and_evidence": "The abstract boldly claims that: \"Our definition has the potential to inspire the design of novel, theoretically-driven models that better capture the mechanisms of compositional thought.\" This is quite a bold claim for a paper that has three small experiments, one on procedurally generated data. I believe a better description of this paper is: a model-based quantitative measure of compositionality.", "methods_and_evaluation_criteria": "adequate", "theoretical_claims": "n/a", "experimental_designs_or_analyses": "> Figure 4. Compositionality of natural language systems.\n\nThis is not natural language data but instead elicitations from an LLM. That should be made clear.", "relation_to_broader_scientific_literature": "Realizes compositionality as compression, following closest to the work of Kirby that shows that compositional language structures emerge via cultural transmission as a balance between expressive communication and efficient (compressed) encoding (Kirby, 2015; 2019).", "essential_references_not_discussed": "Several important works in cognitive science:\n\n1. Cognition as compression in a probabilistic framework, efficient coding:\n\n    Chater N, Vitányi P. Simplicity: a unifying principle in cognitive science? Trends Cogn Sci. 2003 Jan;7(1):19-22. doi: 10.1016/s1364-6613(02)00005-0. PMID: 12517354.\n\n    Feldman J. The simplicity principle in perception and cognition. Wiley Interdiscip Rev Cogn Sci. 2016 Sep;7(5):330-40. doi: 10.1002/wcs.1406. Epub 2016 Jul 29. PMID: 27470193; PMCID: PMC5125387.\n\nAnd a methodological connection in computer science:\n\n1. Connections between compression and induction of simple grammars:\n\n    Adriaans, P., Jacobs, C. (2006). Using MDL for Grammar Induction. In: Sakakibara, Y., Kobayashi, S., Sato, K., Nishino, T., Tomita, E. (eds) Grammatical Inference: Algorithms and Applications. ICGI 2006. Lecture Notes in Computer Science(), vol 4201. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11872436_24", "other_strengths_and_weaknesses": "#### Stengths\n\nVery clear.\n\n#### Weaknesses\n\nClaims are too advanced for what is shown relative to prior work.", "other_comments_or_suggestions": "> Thus, in practice, Z must be discretized to some finite precision and a discrete approximation of the Normal distribution must be used (e.g., the Skellam distribution).\n\nI think you mean \"can be used\" instead of \"must be used\". Specific approximations, including this one, are not justified a priori.\n\n> we first collected a dataset of English sentences describing natural images (COCO, 2024)\n\nDid you collect the dataset? Or did you make use of it?\n\n> We introduced a novel definition of compositionality, representational compositionality, that is grounded in algorithmic information theory. \n\nIsn't compositionality always about representations?", "questions_for_authors": "1. Given that connections between compression and compositionality have been made by Kirby, including in emergent communication, what is the advancement that your work brings? If it is a specific methodology for approximating compositionality, and/or a drop-in replacement for  topological similarity, then the paper should be reframed to make that claim central, rather than overclaiming about a new approach to explaining compositionality in language and thought.\n\n1. There is almost no interpretation of the \"natural\" language results in Figure 4 other than no significant differences per the measure of representational compositionality. What are we supposed to conclude from this experiment?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yq8Dn7PbGv", "reviewer": "Reviewer_AgWc", "summary": "This paper argues that a quantitative measure of compositionality, beyond the traditional colloquial definition, is needed for a more precise understanding of the concept. The authors propose a measure of representational compositionality based on optimal compression using Kolmogorov complexity. Specifically, the measure is defined as the ratio of the Kolmogorov complexity of the representation to the Kolmogorov complexity of a compositional function that maps the underlying structure and parts to the representation. The authors show how the intractability of Kolmogorov complexity may be approximation in practice and demonstrate through simulation studies that meaningful estimates of the proposed measure are possible. Their numerical experiments show that the measure aligns with intuitive expectations of compositionality, capturing dependencies on sentence length, vocabulary size, representational dimensionality, and disentanglement.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the constructive review.\n\n**Q1 / Should we aim to measure the compositionality of** $W$**,** $f$**, or** $Z$**?**\n\nIn our definition $C(Z)$, we are interested in the compositionality of representation $Z$ where no $W$ or $f$ are provided. We believe that our definition does in fact measure $Z$’s compositionality in terms of whether it can be expressed as a simple function of parts. We would reframe your statement as “our framework addresses the question of whether there exists an efficient code $W$ and simple model $f$ that can *generate* a given representation $Z$”, and we have argued in our paper that this is precisely how the compositionality of $Z$ should be defined.\n\n> It seems more natural to ask if a (or what) representation $W$ can be composed into an expressive $Z$ by $f$, rather than whether $Z$ can be generated by some compositional code\n> \n\nThis is an interesting and related question! Whether $Z$ can be compressed through $W$ and $f$ measures compositionality, but whether there exists *other* codes $W'$ that can be composed into an expressive $Z'$ by $f$ is related to “productivity” in cognitive science (the ability to generate novel and meaningful representations using the same semantics) and compositional generalization in AI. We discuss this in Appendix E.\n\n**Q5 / Claims about structure-preserving maps and modularity are not supported**\n\nWhile we were not explicit about this, both were tested experimentally in Section 4.1. We will clarify in revisions.\n\nLookup table semantics with disentanglement=1 are structure-preserving maps, and disentanglement>1 increasingly warps structure. This is why topological similarity, which only tests whether $f$ is a structure preserving map, agrees with our definition for the disentanglement results in Fig. 2b rightmost plot.\n\nThe context-free grammars construct representations with modular semantics because every production rule is a separate module and each $z$ is constructed through a composition of these modules (Fig. 2c). As expected, increasing the number of modules decreases compositionality as the semantics become too complex (Fig. 2d rightmost plot), unlike highly compositiona languages in which a small number of grammar rules provide immense expressivity.\n\n> none of the five claims are validated or examined through numerical experiments\n> \n\nThe other 3 claims are simply restatements of our definition:\n\n- Expressivity and compression: the numerator is expressivity, the denominator is compression with respect to parts\n- Constituent parts are intrinsic to $Z$: $W$ is defined through $Z$ in terms of optimal compression\n- Systematicity and generalization: functions with low complexity generalize better, and compositionality is maximized by low $K(f)$ in the denominator\n\n**Sensitivity to modeling choices**\n\nIn our definition $f$ and $W$ are intrinsic to $Z$, but in practice modeling choices must indeed be made for these components and the sensitivity of our measure should be tested. This is a valid criticism, and in our revised paper we will have a dedicated section acknowledging limitations to be addressed in future work (following your suggestion to include such a section).\n\nWe note, however, that the abstract definition can be useful in and of itself. Kolmogorov complexity for instance is uncomputable but still conceptually useful.\n\n**Q4 / German reaches a minimal compositionality score of ~1, which seems to invalidate claims about interpretable absolute values**\n\nThis is a lack of clarity on our part—German does not have a compositionality of 1. In Fig. 4, a.u. stands for arbitrary units. To compute $C^L(Z)$, we need to estimate $K(Z)$ in the numerator. For the emergent languages this is simple to do (lines 352-355 RHS), but for natural languages it is not. Instead, we make the commonly-held assumption that all languages are equally expressive, which translates to equal $K(Z)$ (lines 431-435 LHS). The units are therefore “arbitrary” because we use an arbitrary constant numerator in place of $K(Z)$ that is shared for all languages. We use the $K(Z|W,f)$ obtained from German as this constant, which also explains why German has a $C^L(Z) = 1$ in these arbitrary units. While assuming equal $K(Z)$ simplifies analysis, it is a limitation that only allows us to compare the *relative* $C^L(Z)$ for different languages without knowing their absolute values—we will clarify this in the text.\n\n**Q2**\n\nWe expect the definition to fail when implemented with improper modeling assumptions (e.g., wrong DNN architecture for $f$), poor training hyperparameters, or insufficient data for training DNNs. We will expand on this in a new Limitations section.\n\n**Q3**\n\nDisentanglement (defined in lines 248-258 RHS) refers to the size of the n-grams used to generate our synthetic lookup table representations. For instance, if disentanglement=2, the lookup table has an entry for all possible *pairs* of words and $z$ is generated by concatenating these pair embeddings.", "claims_and_evidence": "The authors propose a quantitative measure of representational compositionality as the ratio of the Kolmogorov complexity of a representation to the Kolmogorov complexity of the representation given a set of sentences.\n\nWhile the proposed framework is well-motivated and provides an interesting perspective on compositionality through the lens of optimal compression, there are some aspects that could benefit from further clarification and support.\n\nA key concern is that the framework seems to address the question of whether an efficient compositional code can *generate* a representation, rather than measuring *how compositional* a given representation is itself. This distinction suggests that the measure may reflect the potential for compositional generation rather than the intrinsic compositionality of a representation. To put it as a question: if we want to study compositionality, should we aim to measure the \"compositionality\" of $W$, $f$, or $Z$? It seems more natural to ask if a (or what) representation $W$ can be composed into an expressive $Z$ by $f$, rather than whether $Z$ can be generated by some compositional code.\n\nThe claims that the framework addresses issues with the colloquial definition of compositionality (such as expressivity, compression, and the intrinsic nature of constituent parts) are intuitive and reasonably supported by the definition. However, claims about structure-preserving maps and modularity are weakly supported and not directly justified by the definition. Crucially, none of the five claims are validated or examined through numerical experiments.\n\nThe authors state that $p_w$, $W$, and $f$ are \"not free parameters\" because they are intrinsic to the representation in that they best compress $Z$. However, in practice, the measure is highly sensitive and determined by the specific choice of $f$ and $W$ (even when they are the result of a training procedure). It is unclear how the measure would generalize beyond synthetic datasets with an underlying generative model — and even in those cases, it’s plausible that some choices of $f$ and $W$ could lead to better representational compositionality scores than the actual generative model itself. Or in other words, the Kolmogorov complexity remains untraceable, even when it is decomposed into data and a model.\n\nLastly, the claim that the absolute value of the measure is interpretable raises some questions. The authors state that the lowest possible compositional score is 1 in the emergent language experiment, representing an arbitrary mapping from sentences to representations. However, in the natural language study, German reaches a compositionality score of ~1 — which seems counterintuitive, as natural languages are typically considered compositional. This suggests that there is a strong dependency of the calculation of $K(f)$ and $K(Z∣W,f)$ and the interpretability of absolute values of C(Z).", "methods_and_evaluation_criteria": "The authors evaluate the proposed measure across four distinct tasks: a synthetic lookup table, a context-free grammar task, an emergent language task from multi-agent training, and a natural language task using a multilingual large language model (LLM). These evaluation criteria are reasonable for demonstrating the versatility of the proposed measure across different domains. The authors show that the measure aligns with intuitive expectations of compositionality, capturing relations between compositionality and factors such as sentence length, vocabulary size, representational dimensionality, and disentanglement. Comparing the measure to topological similarity also seems reasonable, as it provides a useful benchmark for assessing structural relationships between representations.\n\nNo simulations are provided to justify expressivity, compression, the intrinsic nature of constituent, the structure-preserving maps and modularity statments.\n\nNo simulations or benchmarks are provided to show the limitations of the measure, explitly providing insights when it fails, when it fails our intuitions and when the interpretability of absolute values fails (see above).", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "Compositionality, the idea that complex expressions derive meaning from their parts and structure, has it's roots in cognitive science and linguistics. Chomsky’s theories on language productivity (Chomsky, 1956) and Fodor’s Language of Thought hypothesis (Fodor, 1975) highlight the systematic nature of thought and language, however, without providing a definition of compositionality that goes beyond intuition (Szabo, 2022). A quantitive theory of compositionality that goes beyond symbolic algorithms and provides a quantitative measure is in particular important as artificial neural networks like LLMs and brains capture and process compositional structures through abstract, non-symbolic representations. The presented paper builds on these foundations by proposing a Kolmogorov complexity-based measure of representational compositionality, linking insights from cognitive science, AI, and neuroscience.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Overall, the paper makes a strong case for the potential of the proposed measure. However, it would greatly benefit from a dedicated Limitations section that clearly and explicitly outlines the limitations of the proposed measure and highlights potential pitfalls through additional simulation studies. This would provide a more balanced perspective and help clarify the conditions under which the measure is / is not reliable and interpretable.", "other_comments_or_suggestions": "The following sentence is difficult to follow and could benefit from a rewrite: \"But where do these expressions and their constituent parts come from when considering neural representations themselves such as in the Language of Thought hypothesis, where thoughts are encoded in distributed patterns of neural activity?\"\n\nThe idiom \"he kicked the bucket\" may be less familiar to some readers; consider using a more widely known example.\n\nThe sequence should consistently follow the same order, i.e., either K(p) + K(X|p) or K(X|p) + K(p)\n\nTypo in section 4: \"we will first illustrate [...] where where [...]\nGrammar: (e.g., that it is linear, a hierarchical, etc.)", "questions_for_authors": "1. In practice, do we want to measure the \"compositionality\" of $W$, $f$, or $Z$? It seems more natural to ask how a given representation $W$ can be composed into a meaningful $Z$ with $f$, rather than whether $Z$ can be generated by some optimal compositional code. It seems like there might be a distinction between measuring compositionality of the representation versus the process that generates it. Could you shed some light on this?\n2. How, why, and when do you expect the measure to fail or produce misleading results?\n3. In Section 4, what do you mean by \"disentanglement,\" and how is it measured?\n4. Could you clarify the interpretation of a compositionality score. When does it lead to an absolute value that can be interpreted and when not?\n5. The claims about structure-preserving maps and modularity are not directly justified by the definition nor evaluated numerically. Do you have plans to study these aspects more explicitly?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IBCV27ba4a", "reviewer": "Reviewer_q4Av", "summary": "The paper builds a more rigorous version of compositional generalization, compared to the ones proposed by linguists. It claims to be the first to do so, although this may be debatable. This seems to be the first serious attempt based on kolmogorov complexity and is more agnostic of the learning model achitecture than predecessors, at the cost of being hard to compute and often even to approximately bound. However the authors cover a few examples of toy model applications, and they delineate a plan for future research in order to further \"concretize\" this notion.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the constructive review.\n\n**Tempering claims on novelty and highlighting limitations**\n\nReviewer JsGE made a similar comment—in retrospect, we agree. While we believe that existing definitions of compositionality suffer from pitfalls that ours addresses, it is unfair to claim that ours is the first and premature to claim that it is the “true” or most useful one. We plan to edit our paper accordingly:\n\n1. Remove premature claims in the abstract and elsewhere that frame our definition as uniquely “correct” or “the first formal definition”.\n2. Add a new section “Comparisons to prior work” that systematically points out advantages (e.g., generality, no assumptions on the structure of $f$) and limitations. This should help provide a neutral framing of our specific contributions.\n3. Add a new section discussing “Limitations”, including challenges the reviewer has mentioned such as:\n    1. The difficulty of estimating KC.\n    2. The need for “strong assumptions” in practice to estimate $C(Z)$ as in Fig. B.1.\n\n**Fundamental tradeoff between (a) easily estimating complexity and (b) making strong structural assumptions?**\n\nThere is indeed a fundamental tradeoff. KC requires an uncomputable search over all programs, so compression schemes impose constraints on the search space: the more constraints, the smaller the search space. We will highlight this in the paper. However, we also emphasize that the advantage of an abstract definition like ours is precisely that it allows estimators to make different tradeoffs.\n\nTo some extent DNNs mitigate the tradeoff: they make few structural assumptions, but are easy to train and have inductive biases for simplicity resulting in excellent compression (Wilson 2025, Goldblum 2023). This is why we advocate for using DNNs in Appendix B.\n\n**Oversimplification of the “intuitive” definition?**\n\n> The paper states that \"structure\" is not defined in the usual definition, [but] structure is defined under assumptions on sentence parsing/type/semantics.\n> \n\nOur point is that the intuitive definition refers to the structure of a complex expression as if it were provided. Of course this definition is alluding to grammars, but it does not specify how such grammars are inferred for a given representation. Our definition addresses this because it precisely defines “structure” as an intrinsic property of the representation through the semantics $f$ that optimally compress it.\n\n> \"sentences are simply strings\" also is oversimplifying […] Better say \"we consider sentences as simply strings\"\n> \n\nAgreed—we will change to your wording.\n\n**Alternatives to Kolmogorov complexity**\n\nBetter notions of complexity might be developed, but for the moment KC is indeed “the canonical measure”. We will better justify it, especially for unfamiliar readers. We note the presence of additional introductory material for KC in the supplement.\n\n**Why use prequential coding to measure KC?**\n\nWe mention it “provides good estimates in practice”. Empirically, it provides tighter bounds on the KC of DNNs than other methods (Blier 2018), and we are using DNNs in our experiments to parameterize $f$. If other compression schemes with better bounds become available, they should be used instead. We will clarify this in the text.\n\n**Validating the natural language results?**\n\nThere is no consensus on which natural languages are more/less compositional, and it is in fact a longstanding debate in linguistics. The purpose of this experiment is not to validate our compositionality metric, but rather to demonstrate it as a tool to help resolve this debate. This is explained in lines 286-296 LHS. Our results suggest that these languages are roughly equally compositional (limitations in Appendix J).\n\n**Comparisons to TopSim**\n\nWe compare to TopSim because it is frequently used in the literature as a measure of compositionality (we cite several works). It is a valid competing metric because, like $C^L(Z)$, it depends on the pair $(W, Z)$. While we do not investigate “what TopSim did wrong” and why in-depth, we include it simply to show how it, as a competing metric, gives more counter-intuitive results. Whenever it deviates from the results of our definition, we flag this (e.g. that it gives nonsensical results for the natural language experiment, namely that Japanese is negatively compositional).\n\n**Other comments**\n\n> line 302-304 says there should be a comparison between sentence length and vocabulary size. It would be good to validate the sentence by some data\n> \n\nWe will add a new result showing these curves for different sentence lengths.\n\n> line 057: compressed \"more easily\" or just \"more\"?\n> \n\n“more”—we will change it.\n\n> line 162: the $\\mathcal{N}$ notation was not introduced […] say it's a gaussian density before\n> \n\nWe will do that.\n\n> line 345-348: the description of \"depth\" is too short\n> \n\nIt is better defined in Appendix H.2 with a concrete grammar as an example. We will define it more clearly in the main text.", "claims_and_evidence": "I think that the claims are mostly correct and well defended.\n\nI don't agree that this is exactly the first attempt at rigorously defining compositionality (this sounds as an unbearably bold statement), and the authors cite a few works that have already tried general enough (in my view) approaches. However I agree that the work is new and worth reading.\n\nAs a minor point, the authors don't discuss any alternatives to Kolmogorov Complexity as a basis for quantifying compositionality. This is a gap in the justifications which could make the notion questioned in the long term. However right now, most people agree that KC is \"the\" canonical measure.\n\nI feel that the representation of previous theory of compositionality is oversimplifying and therefore several statements are misrepresenting it. The paper states that \"structure\" is not defined in the usual definition, then goes on to immediately contradict that by hinting at the correct statement, that actually structure is defined under assumptions on sentence parsing/type/semantics.\n\nFurthermore, even if the abstract formulas do not have many assumptions, still e.g. the core setup summarized e.g. in Fig. B.1 involves several strong assumptions without which the actual value of C(Z) is not computable or realistic (as mentioned after Fig. B.1). But the paper's abstract claims that the new quantity is (a) quantitative and (b) conceptually simple (meaning it has no strong structural assumptions, which seems to be the main difference to previous works). \n\nIt seems that there is a strong trade-off between (a) and (b), as when we want (a) we have to give up (b) and impose structural assumptions, and when we want (b) we have to give up (a). This trade-off is fine for me, but should be highlighted for transparency. I would like to know the view of the authors on whether this trade-off is an inherent problem of KC-based metrics, or of the notion of compositionality itself: can we get rid of the trade-off?\n\nThe related claim that \"sentences are simply strings\" also is oversimplifying, which may lead to confusion between semiology and computer science approaches. Better say \"we consider sentences as simply strings\". This simplification (forgetting that sentences are uttered by intelligent agents in order to communicate) is related to the simplification that KC is considered as unquestioned as a measure of compositionality. Using KC is fine and valuable, but the fact that it is a modelling simplification should be at least hinted at, at least in the part in which the paper refers to model \"brains\" and human interactions at several places in the document.", "methods_and_evaluation_criteria": "The datasets used are a bit on the toy model side. \n\nIt would be useful to have a more thorough discussion of limitations due to the hardness of computing KC in practice. \n\nThe authors show some practical improvements like using prequential coding, VQ-VAE ideas, and others, but no experiment or comparison is present to show what can help and where. Why do you decide that \"prequential coding is the answer\"? I can't find where the use of this method is justified in the paper.\n\nI think that the discussion about heuristics behing the blue curves in figure 2 is the main validation of the metric, and the rest of the experiments are not very enlightening:\n\n- There is a graph about how compositional are different languages according to this metric. How do we know that this is realistic, is there no other benchmark or consensus about e.g. Japanese being slightly more compositional than the others? In other words I don't see how the experiment about actual languages is relevant to validating this particular metric.\n\n- It is not clear at all that TopSim is the correct counterpart of this particular complexity measure: why is that so?\nAlso, what does the comparison to TopSim say, in terms of evaluation? \nThis differential in behavior is not discussed, so it's not clear why there is a graph between metrics. \nThe authors limit themselves to a series of heuristic descriptions of their own metric, and no description of \"what TopSim did wrong\". This being the case, why did they put the graph of TopSim metric in the paper?", "theoretical_claims": "I don't think that there are theorems/proofs in the mathematical sense. \nI checked the calculations and they are OK.", "experimental_designs_or_analyses": "See \"methods and evaluation criteria\".\n\nAnother point is that in the paragraph on \"vocabulary size\" (line 302-304 more or less) the text says there should be a comparison between sentence length and vocabulary size. But no graph highlights that scaling/comparison. It would be good to validate the sentence by some data.", "relation_to_broader_scientific_literature": "I think that this paper will give a good starting benchmark for the line of future research hinted at by the authors. \nIn particular, it invites the community to improve upon the computability/approximability of abstract KC-based metrics.", "essential_references_not_discussed": "I didn't find something concrete to point out.", "other_strengths_and_weaknesses": "nothing comes to mind.", "other_comments_or_suggestions": "line 057: compressed \"more easily\" or just \"more\"?\n\nline 162: the \\mathcal N notation was not introduced, so one has to wonder for a bit and then notice that you talk about Gaussians around that point. Maybe say it's a gaussian density before using the symbol.\n\nline 345-348: the description of \"depth\" is too short, I couldn't understand it fully. maybe expand a bit", "questions_for_authors": "See the parts \"claims and evidence\" and \"methods and evaluation criteria\".", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yP4We6YEMc", "reviewer": "Reviewer_cjwu", "summary": "This paper introduces a notion of compositionality grounded in algorithmic complexity. The authors propose to treat compositionality employing Kolmogorov complexity related to representations and to a discrete language that is used to make the conversion. The contribution rests mainly in bridging how such a measure can capture compositionality, grounding many observations from intuitions in cognitive science and AI, and contrast it to topological similarity. The idea is very appealing and makes sense. The authors also present some empirical investigation of how this can be used to characterize compositionality in both synthetic and real-world representations.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the constructive review.\n\n**Limitation:** $Z$ **is continuous,** $W$ **is discrete**\n\nWhile continuous values are problematic for Kolmogorov complexity, this may not be a significant limiting factor in practice: for instance, tokenization methods for continuous data (e.g., VQ-VAE) often exhibit surprisingly low information loss. We take the point, however, that some representation attributes (e.g., “size”) might be inherently continuous and difficult compress using a discrete $W$. We leave open the possibility that our definition can be extended to drop the requirement of a discrete $W$.\n\n**Meaning associated to higher values of** $C$\n\nIt is easiest to get some intuition by fixing the denominator (which depends on $f$ and a reconstruction error) and to imagine how the numerator $K(Z)$ might be scaled. A concrete example comes from disentanglement: each word in the vocabulary has a vector embedding encoded in a lookup table of $f$, and $f$ simply concatenates or adds these vector embeddings. If we consider representations modeled by increasingly longer sentences, $f$ remains identical but $K(Z)$ keeps increasing due to increases in $-\\log_2 p_w(W)$ (longer sentences have higher entropy). This is precisely what is occurring in Fig. 2b leftmost plot. The meaning of a higher $C$ is therefore that expressivity (loosely, the number of different things that can be represented) increases, but the semantics $f$ of how things are represented through parts stays the same. In theory, $C$ could be unbounded, but this requires the length of sentences to approach $\\infty$, which is unlikely to be an optimal compression scheme for a representation.\n\n**Relationship to OoD compositional/combinatorial generalization?**\n\nWe believe there is a relationship—we discuss this in Appendix E. Testing the empirical relationship between the two is an interesting direction for future work. We also give some hypotheses about how to specify inductive biases for compositional representation (which could improve OoD compositional generalization) in Appendix F.\n\n**Algorithmic approaches for measuring** $C(Z)$ **are in Appendix B, but should be more central**\n\nGiven that we did not apply the methods in Appendix B (this is a direction left for future work, which we were transparent about in the Experiment and Conclusion sections), we thought it appropriate not to include it in the main text. The current paper focuses on validating $C(Z)$ in synthetic settings where the optimal compression of $Z$ is known from a ground-truth generative model (lines 238-246 RHS), and otherwise computes $C^L(Z)$ on real data (which is easier than $C(Z)$ because $W$ is given, lines 360-365 LHS). Our methods for estimating $C^L(Z)$ are discussed in the main text, Section 4.2.\n\n**Values for $C^L(Z)$ obtained on different natural languages**\n\n> What is a.u.?\n> \n\nApologies, this should be in the paper: a.u. stands for arbitrary units. To compute $C^L(Z)$, we need to estimate $K(Z)$ in the numerator. For the emergent languages experiment in Section 4.2 this was simple to do (lines 352-355 RHS), but for the natural languages it is difficult. Instead, we make the (commonly-held) assumption that all languages are equally expressive in their abilities to express ideas and identify referents, which translates to equal $K(Z)$ (lines 431-435 LHS). The units are therefore “arbitrary” in Fig. 4 because we use an arbitrary constant numerator in place of $K(Z)$ that is shared among the different languages. We used the $K(Z|W,f)$ obtained from German as this constant, which also explains why German has a $C^L(Z) = 1$ in these arbitrary units: it does not mean that German obtains the trivial lowest possible compositionality, because we don’t know the true $K(Z)$ for German or the other languages. While assuming that all languages have equal $K(Z)$ simplifies analysis, it is a limitation that only allows us to compare the *relative* $C^L(Z)$ for different languages without knowing their absolute values.\n\n**Suggestion: include some examples from the supplementary material in the main text to help grasp what C is measuring**\n\nThank you for the suggestion—we will do this.\n\n**Interpretability and linear representation hypothesis**\n\nThank you for the great question—we have indeed thought about this! Our hypothesis is that DNNs often linearly represent these concepts because this in fact *maximizes* compositionality according to our definition: $f$ is simple because it need only store and sum word embeddings. However, we might find that far more concepts are compositionally represented and interpretable if we relax the strong assumption of linearity and allow for semantics $f$ that are more flexible, yet still simple. Interesting future work inspired by our definition could for instance train a flexible DNN as $f$ to predict LLM activations from latent concepts, and then use the same methods we applied in Sections 4.2 & 4.3 to estimate $K(f)$ and compositionality.", "claims_and_evidence": "The main claim is the proposal of a theory of representation compositionality that can capture intuitions from several previous works. This rests in using Kolmogorov complexity and relating representations to a sort of composition of symbols from a language. The examples and the long discussion with related literature provide evidence that Kolmogorov complexity can be useful, and overall, the idea is simple enough to adapt to different research areas. Based on the discussion and on the results, it is a particular interesting proposal.", "methods_and_evaluation_criteria": "Experiments on natural language are limited to one model and one dataset.", "theoretical_claims": "I found the theory pretty clear and the authors did a good work to introduce it. Some limitations are discussed by the authors, concerning the representations Z and the language W.\n\n- **Z is continuous, W is discrete.** This is one limitation of the proposed approach. The theory of compositionality the authors propose is grounded on discrete symbols and cannot capture the complexity of real numbers. This is sensible, especially if representations capture factors of variations like the continuous values of the color of an object, its size, or whatever. It looks like this creates a complication to treat it in this framework that can only be addressed by leveraging quantization. Moreover, Kolmogorov's complexity does not easily adapt to continuous numbers. \n\n- **The measure of compositionality requires more intuition.** I found the examples clarifying but it is not clear how values of C can be interpreted. Specifically, while C=1 is the lowest possible value, that corresponds to trivial cases, what is the meaning associated to higher values of C and is there an upper limit for C? \n\n- **Usefulness to ood generalization and combinatorial generalization?** The idea of compositionality is especially intriguing when related to ood generalization. Is there a relation with representation compositionality? This aspect is only mentioned but it is worth expanding.", "experimental_designs_or_analyses": "The synthetic experiments are confirming the theory. Since data are generated according to the theory, I am not particularly surprised by the representation compositionality but it is interesting to see the topological counterpart not behaving as expected. As I am not an expert in this field, I wonder if other measures of compositionality can be used in those experiments.\n\nThe algorithmic side of the paper should be more central and is now hidden in the supplementary, but it would be beneficial to know how to measure C. This can be of help with new real world experiments. Can the authors comment on the values obtained on different languages? What is a.u.? As far as I understood, C=1 reveals low compositionality and all languages reveal pretty similar representation compositionality (around 1 and 1.25)? Does this mean that the model does not attain any compositionality?", "relation_to_broader_scientific_literature": "There is an interesting link to _combinatorial generalization_ [1]. In that problem, based on a limited set of observations, e.g., over variations of few object factors, the model is tested whether it generalizes to new unseen combinations of these factors. It would be interesting to see if there is a relation between this generalization and representation compositionality.\n\n[1] The role of Disentanglement in Generalisation, Montero et al., ICLR (2021)", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "I suggest the authors include some examples from the supplementary material in the main text, even in a shorter version. They are quite helpful in grasping what C is measuring.", "questions_for_authors": "- **I have asked some questions in the previous sections.**\n\n- **Relation to interpretability.** It would be interesting to connect this notion of compositionality and the use of language W to current focus in probing interpretability of neural/LLMs representations. Many works consider the so called \"Linear Representation Hypothesis\", whereby concepts (or symbols) are linearly encoded in model representations [2,3].  If these interpretable concepts are seen as elements of a language, is it possible to measure some form of representation compositionality based on that language? Do the authors have an intuition on this matter?\n \n[2] The Linear Representation Hypothesis and the Geometry of Large Language Models, Park et al., ICML (2024) \\\n[3] All or None: Identifiable Linear Properties of Next-token Predictors in Language Modeling, Marconato et al., AISTATS (2025)", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces a formal, quantitative definition of representational compositionality based on Kolmogorov complexity. The main contributions include 
- It reframes compositionality as the compressibility of representations into structured functions of their parts. This definition offers a compelling alternative to heuristic or symbolic notions and aligns with intuitive expectations across multiple domains. 
- The paper evaluates the proposed measure in synthetic setups, emergent language scenarios, and multilingual LLM embeddings, and contrasts it with topological similarity. 
- It serves as a bridge between cognitive and computational perspectives.

During the response period, the authors addressed concerns about overclaims, interpretability, and modeling sensitivity. They committed to tempering claims, adding a limitations section, clarifying assumptions about absolute vs. relative compositionality scores, and situating their work more precisely with respect to prior definitions (e.g., Kirby mentioned by Reviewer JsGE). While Reviewer JsGE maintained a weak reject, citing limited empirical depth, other reviewers increased their scores post-rebuttal. Given the paper’s conceptual clarity, rigor, and potential for impact, I recommend acceptance.

For the final version, the authors are suggested to (1) temper novelty claims, and (2) improve clarity on practical estimation of Kolmogorov complexity.
Decision: Accept (poster)