Towards a Formal Theory of Representational Compositionality

Thank you for the constructive review.

Limitation: $Z$ is continuous, $W$ is discrete

While 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$.

Meaning associated to higher values of $C$

It 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.

Relationship to OoD compositional/combinatorial generalization?

We 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.

Algorithmic approaches for measuring $C(Z)$ are in Appendix B, but should be more central

Given 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.

Values for $C^L(Z)$ obtained on different natural languages

What is a.u.?

Apologies, 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.

Suggestion: include some examples from the supplementary material in the main text to help grasp what C is measuring

Thank you for the suggestion—we will do this.

Interpretability and linear representation hypothesis

Thank 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.

Thank you for the constructive review.

Tempering claims on novelty and highlighting limitations

Reviewer 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:

1. Remove premature claims in the abstract and elsewhere that frame our definition as uniquely “correct” or “the first formal definition”.
2. 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.
3. Add a new section discussing “Limitations”, including challenges the reviewer has mentioned such as:
   1. The difficulty of estimating KC.
   2. The need for “strong assumptions” in practice to estimate $C(Z)$ as in Fig. B.1.

Fundamental tradeoff between (a) easily estimating complexity and (b) making strong structural assumptions?

There 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.

To 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.

Oversimplification of the “intuitive” definition?

The paper states that "structure" is not defined in the usual definition, [but] structure is defined under assumptions on sentence parsing/type/semantics.

Our 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.

"sentences are simply strings" also is oversimplifying […] Better say "we consider sentences as simply strings"

Agreed—we will change to your wording.

Alternatives to Kolmogorov complexity

Better 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.

Why use prequential coding to measure KC?

We 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.

Validating the natural language results?

There 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).

Comparisons to TopSim

We 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).

Other comments

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

We will add a new result showing these curves for different sentence lengths.

line 057: compressed "more easily" or just "more"?

“more”—we will change it.

line 162: the $\mathcal{N}$ notation was not introduced […] say it's a gaussian density before

We will do that.

line 345-348: the description of "depth" is too short

It is better defined in Appendix H.2 with a concrete grammar as an example. We will define it more clearly in the main text.

Thank you for the constructive review.

Q1 / Should we aim to measure the compositionality of $W$, $f$, or $Z$?

In 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.

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

This 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.

Q5 / Claims about structure-preserving maps and modularity are not supported

While we were not explicit about this, both were tested experimentally in Section 4.1. We will clarify in revisions.

Lookup 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.

The 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.

none of the five claims are validated or examined through numerical experiments

The other 3 claims are simply restatements of our definition:

• Expressivity and compression: the numerator is expressivity, the denominator is compression with respect to parts
• Constituent parts are intrinsic to $Z$: $W$ is defined through $Z$ in terms of optimal compression
• Systematicity and generalization: functions with low complexity generalize better, and compositionality is maximized by low $K(f)$ in the denominator

Sensitivity to modeling choices

In 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).

We note, however, that the abstract definition can be useful in and of itself. Kolmogorov complexity for instance is uncomputable but still conceptually useful.

Q4 / German reaches a minimal compositionality score of ~1, which seems to invalidate claims about interpretable absolute values

This 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.

Q2

We 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.

Q3

Disentanglement (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.

Thank you for the constructive review.

Tempering our claims

Reviewer 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:

1. 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.
2. 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.
3. Add a new section discussing additional “Limitations” of our definition.

Discussing additional references

The 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”).

The 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.

Advances upon Kirby et al.’s work on compositionality

1. 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.
2. 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.

In our revisions, we will summarize these points.

Interpretation of natural language results

The 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.

Other comments

I think you mean [a discrete approximation of the Normal distribution] "can be used" instead of "must be used"

Yes, thank you; we will correct the text.

Did you collect the [English sentences] dataset? Or did you make use of it?

We made use of the existing dataset; we will correct the text.

Isn't compositionality always about representations?

It 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.

[1] Aitchison 1982. The Statistical Analysis of Compositional Data

[2] Lepori 2023. Break It Down: Evidence for Structural Compositionality in Neural Networks

[3] Ren 2023. Improving Compositional Generalization Using Iterated Learning and Simplicial Embeddings