Towards a formal theory of compositionality

We thank the reviewer for their excellent points, which we hope we have addressed. We apologize for the long response, as we wanted to respond to every point.

The experiments can be more practical. It might be helpful to consider LLMs and finetuning.

Our framework can indeed be used to study the compositionality in the representations of LLMs, but this is complicated by the variable representation dimensionality in these models that depends on the number of input tokens. For simplicity, we instead considered sentence-embedding models that encode any variable-length linguistic sequence to a fixed-size vector representation. Note that the sentence-embedding model we used was large (300 million parameters; the largest multilingual sentence embedding model on HuggingFace) [1] and widely used on HuggingFace (200 million downloads the past month) [2].

Regarding the evolution of compositionality in representations over the course of finetuning, we are curious as well! However, we believe that the question of compositionality across different natural languages that we investigated is also very interesting, current, and practical, especially for fields that have been studying compositionality for a long time (such as linguistics). We also studied compositionality in emergent language systems multi-agent systems, which is an important and current field of study in reinforcement learning. We therefore respectfully argue that our experiments do, in fact, consider practical or real-world use cases, although we agree that the core contribution of this work is conceptual and theoretical.

Discussions on how the proposed metric can inspire new algorithms would make the paper stronger

We have now added an additional section, Appendix F, that outlines two very different but equally promising approaches for learning compositional representations that are directly inspired by our definition. The first approach directly regularizes $K(Z|W)$ using the loss of a discrete auto-encoder, and the second approach relies on multi-task training. We believe that this suggestion has made our paper much stronger, especially for ML practitioners that wish to build on it.

Include a system diagram to clarify that $Z$ comes from some source like a pretrained model, and the role of $W$ is to compress it

We have edited Fig. 1b to show that $Z$ comes from some external source, and that the role of the components described in Section 2 is to compress this $Z$. We have also clarified the conceptual role played by different components of the compression program in the figure.

For the first line of equation (1), if $pw,W,f$ are all empty strings, then the right-hand side is still minimized. The equation is degenerated to be $K(Z)=K(Z)$. Is that the case?

Yes, but only because the shortest program for $K(Z| f=null, W=null)$ would itself decompose $Z$ according to the program form we have outlined, and would internally define $p_w, W, f$. In practice to estimate the minimization in Eq. 1, we must put constraints on the different models so that they learn to represent the correct corresponding program component (e.g., parameterise $p_w$ using an autoregressive sequence model, model $K(Z | W, f)$ as a Gaussian, etc.). We felt that including this discussion in the paper would add too much complexity, but it is an important caveat.

Is there any particular reason to define $C(Z)$ as the ratio of two $K$ terms? What about a difference?

We believe that a ratio is more intuitive: it asks how much more compressible the representation becomes when it is described as a function of parts (2x, 3x, etc.). A ratio is also unitless, which helps with interpretation across distinct model implementations. However, we are not strongly committed to this particular choice, and there could be reasons why a difference is more appropriate or intuitive in certain circumstances. What we believe is most important is the component $K$ terms emphasized in our definition. Importantly, when controlling for all representations of fixed complexity $K(Z)$, both alternatives agree about how to order the compositionalities of these representations. We would be keen in considering additional reasoning and recommendations from the reviewer on this front.

Include the formal definition of topological similarity in the main text

Thank you for the suggestion: we have added this at the start of Section 4.

Figure 3 caption: change “iterated learning is an inductive bias” to “iterated learning amplifies the inductive bias of model’s learning that more compositional mappings are learned faster”

This was in the main text (not Figure 3), but we have made the reviewer’s suggested change in Section 4.2 when introducing iterated learning. Thank you for the catch!

We thank the reviewer for their excellent points, which we hope we have addressed. We apologize for the long response, as we wanted to respond to every point.

The clarity of Section 2 can be improved with clearer definitions of the program components and concrete examples

Thank you for the suggestion. We have addressed this in 2 ways:

1. We have added a table in Section 2, where for each term we give: its notational symbol, its shape, and a concrete example. We believe this will serve as a useful point-of-reference for readers where all concepts are concretely summarized in one place.
2. We have edited Fig. 1b to show that $Z$ comes from some external source, and that the role of the components described in Section 2 is to compress this $Z$. We have also added additional descriptors in Fig. 1b to clarify the conceptual role played by components of the compression program.

Define systematicity

Systematicity is a term from cognitive science describing a property of compositional systems: that the meaning of a whole (e.g., a sentence) is derived from the meanings of the parts (e.g., the words) in a structured or non-arbitrary way. Idioms are a classic counter-example for systematicity [1]. We have added this definition in Section 3 when first introducing the term.

The examples of high/low $C(Z)$ in the Appendix are helpful for understanding the proposed definition. Can these be moved to the main text, and can they be made more concrete?

We agree that the examples are very helpful for gaining intuition. However, we believe that for most readers a large number of examples in the main text will prove distracting. We therefore summarized a small number of prototypical examples in the main text that were supported by our empirical experiments: (1) lookup-table representations and (2) modular grammar representations. Crucially, these are the most important examples to contextualize our definition in the prior literature on compositionality: as we cite early in the second paragraph of the introduction, ML often considers compositionality as synonymous with disentanglement or object-centric representations (lookup-table representations), and both ML and cognitive science think of compositionality in terms of languages, grammars, and modularity.

We agree that our examples in the Appendix could have been further fleshed out. We have now edited them to be more concrete, and in particular have followed the reviewer’s suggestion by adding a new Fig. D.1 to illustrate each example described in the Appendix.

What is the definition of “modularity” used in Section 3?

Modularity refers to a system which can be decomposed into interacting sub-parts that can be understood separately [2]. An example in ML is mixture-of-experts models. We have added the definition and example to Section 3.

How does modularity relate to compositionality?

Modularity relates to compositionality because if a function $f$ decomposes according to reusable modules, those modules only need to be defined once, making $f$ more compressible and $K(f)$ lower (which appears in the denominator of $C(Z)$). An example is that a modular program that defines reusable functions can be much shorter than one that does not. We have clarified this in the main text and in Appendix D.

The assumption that the representation $Z$ follows a normal distribution seems arbitrary.

We believe there was a misunderstanding here. Representations $Z$ come from some model (e.g., a latent layer in a pretrained image classifier) and are certainly unlikely to be normally-distributed, but we do not assume that they are. Perhaps the normal distribution referred to by the reviewer is $p(z | f(w))$: given $f(w)$, the representation is normally-distributed. This is a mixture-of-Gaussians distribution with as many possible mixture components as there are possible sentences (which is exponentially large), and mixtures of Gaussians can approximate any distribution arbitrarily well given enough mixture components [3].

In the experiment on lookup table representations, are the sentence length and vocabulary size correlated with each other?

No, sentence length and vocabulary size are uncorrelated. When varying one, we keep the other fixed. We wanted to see how each of these attributes independently affect $C(Z)$.

Is modularity a specific form of systematicity?

No: as specified above, modularity refers to a function with distinct components, whereas systematicity refers to a function that behaves in a predictable way for novel combinations of inputs. For instance, natural language is systematic in how it represents the meaning of a phrase like “he kicked the ball”, but not systematic (i.e., arbitrary) in how it represents the meaning of an idiom like “he kicked the bucket”. While modularity can in some circumstances help with systematicity, this is not always the case [4].

Hi authors! Thank you for the detailed response. Unfortunately, it doesn't address my main concerns---I still think the paper has fundamental technical issues and isn't ready to publish in its current form. Briefly:

The identifiability argument in the original review used discrete distributions to avoid all the complications that come up with entropies of continuous distributions. But if the Gaussian piece of this is important, let's just call $G$ the entropy / average number of bits needed to encode a sample from $\mathcal{N}(0, 1)$. Now suppose my data consists of $N$ i.i.d. draws from $\mathcal{N}(0, 1)$; the Kolmogorov complexity of this set is $NG$. Now as above we have two choices:

We can let $p = \mathcal{N}(0, 1)$ and $f(x) = (x, \epsilon)$

or we can let $p = \mathcal{N}(0, \epsilon)$ and $f(x) = (0, 1)$

In the former case compositionality scales with $NG$, and you pay $NG$ to represent the encodings $E$. In the latter case compositionality is constant, and you pay $NG$ to account for prediction noise. Both choices achieve the same value of the objective in Equation 1. As the author response notes, these two implementations are morally "the same". This is exactly the problem with the proposed definition---a useful definition of compositionality should be invariant to these implementation details. The constraints given in the first part of the author response don't actually help us break the tie here: we can implement both ps above as trivial transformers (constraint 1), the matrix of discrete representations $E$ contains either the binary encoding of all points or the trivial all-zeroes matrix in the two constructions above (constraint 2), $f$ outputs the parameters of a normal distribution in both constructions (constraint 3), and $p(z; f(w))$ is a Gaussian (constraint 4).

And despite the (helpful!) conceptual scaffolding in the author response, I'm genuinely unsure which of these two schemes the authors would consider to be the "right" one for encoding a bunch of unstructured noise. Is high-dimensional noise compositional or non-compositional? And given how much intuition / discretion seems required to compute $\mathcal{C}$, it seems a bit premature to refer to this as a "formal" definition. For something as fundamental as compositionality, it seems a little worrying for that definition to depend on things like transformers and even Gaussians rather than more basic computational primitives like Turing machines---in this sense, the version presented in the first paper draft seemed closer to the right answer than the revised one.

All that said, I have been convinced by the author response that it's worthwhile to quantify the structure in collections of representations, even independent of mappings (I might call the subject of the current paper something like "combinatoriality" to avoid confusion with all the existing definitions of "compositionality"). I think the definitional issues are likely fixable (even if I'm not sure which fix is compatible with the authors' intuition), I'm still excited about this line of work, I look forward to seeing a version of this paper at a future conference!

Realized I didn't respond to the point about predictability vs compositionality in sec 3.1. Suppose I have some highly compositional data with an extremely transparent encoding scheme, e.g. data are pairs of letters (e.g. $(a, b)$) and encodings $E$ are ASCII representations of these pairs (e.g. $[01100001, 01100010]$). Now suppose I take my letter pairs and pass them through a hash function, such that it's not possible to look at any individual part of the hashed data and say that it corresponds to the $a$ or the $b$. I would think of the hashed data as a canonical set of representations that is "predictable, but non-compositional" (and we can make $K(Z|W)$ really small / $\mathcal{C}^L(Z)$ really big). Is the intuition in the paper that this data is in fact compositional? If so, is there any difference between compositionality and predictability? If so, what do the separating cases look like?

We thank the reviewer for their excellent points, which we hope we have addressed. We apologize for the long response, as we wanted to respond to every point. As the reviewer points out, formally quantifying compositionality is an important topic for the community and a daunting task. We hope the reviewer sees this contribution as a step toward this goal that is worthy of publication so that future work can build on it.

There exists related definitions of compositionality in terms of representation reconstruction that, while different from the proposed method, should be discussed and cited

Thank you for pointing this out. We have edited our paper to acknowledge this line of work in Section 3 under the paragraph “Constituent ‘parts’ are intrinsic to $Z$”, as this feature of our definition is one of the core differences to others. We also note that our definition remains more agnostic to the structure of the mapping $f$ from $w$ to $z$ as it only considers the complexity of $f$, whereas other work puts more rigid constraints on the mapping (e.g., linear additive, hierarchical grammar, etc.).

Degrees of freedom in the definition

The reviewer raises an excellent point, and indeed simply reading Eq. 1 our definition appears to be ill-defined. Crucially, however, this is a problem about how to delineate, or “label”, different parts of the program that optimally compresses $Z$. For instance, in the reviewer’s example, both schemes actually implement the same program (a uniform distribution over strings of length $MN$), and we are only changing which parts of that program we label as $p_w$, $p(z ; f(w))$, and so on. Eq. 1 must therefore be read with the entirety of Section 2 in mind, which specifies how to label the different program components. With this in mind, $C(Z)$ is well-defined and can be estimated in practice by putting constraints on the different components of the generative model during training. We will explain this in the case of a continuous $Z$ where we have given more thought to these labelings and constraints, as opposed to the discrete case in the reviewer’s example. It might be helpful here to think of the generative model as a mixture of gaussians with modes indexed by $W$.

1. $p_w$ conceptually is the part of the program that defines the distribution over mode indices in $Z$. For compositional representations, these modes are structured, so the indices should be structured as well using symbolic sequences. Constraint: the function specifying $p_w$ should be a sequence model taking discrete inputs and outputting a scalar (e.g., an auto-regressive Transformer).
2. $W$ conceptually is the part of the program that specifies the structured mode indices for each row of the representation. Constraint: rows of $W$ should be discrete sequences.
3. $f$ conceptually is the part of the program that maps the structured mode indices to their vector embeddings representing the mode location and size. Constraint: $f$ should be a function that takes a discrete sequence as input and outputs two real-valued vectors (mode mean and standard deviation).
4. $p(z ; f(w))$ conceptually represents the prediction error, or how far each row in $z$ was to its predicted mode $f(w)$. Constraint: $p(z ; f(w))$ should be a Gaussian with mean and standard deviation given by $f(w)$. The decision to use a Gaussian is not arbitrary, but is in fact an important constraint, and we have edited Section 2 accordingly.

While technically very important, we felt that including these details in the paper would have added too much complexity. Please let us know if this has addressed your concern, and if so whether you would like it to be included in the paper.

Thank you for the quick replies! We'll respond to the predictability/compositionality question first, as it's quicker.

In your example each $w \in W$ is a pair of letters $(a,b)$ and $f(w) :=$

1. Define a lookup table with the ASCII characters for $a$ and $b$
2. Index the lookup table based on the words in $w$
3. Concatenate the embeddings

If we applied a hash function $h$ to each $w \in W$ (let's assume that it's invertible so that we maintain perfect predictability), then the semantics would need to change. We would now have $f'(w) :=$

0. Invert the hash to retrieve $w' = h^{-1}(w)$
1. Define a lookup table with the ASCII characters for $a$ and $b$
2. Index the lookup table based on the words in $w'$
3. Concatenate the embeddings

Notice that the extra step 0 can add complexity, which will depend on $K(h^{-1})$. If the hash function was benign (e.g., swap the two letters in $w$), then it actually doesn't matter (we can just define the lookup table in step 1 differently). But, if the hash function does what you say where "it's not possible to look at any individual part of the hashed data and say that it corresponds to the $a$ or the $b$", then step 0 is actually relevant and adds complexity.

So, in your example, our intuition is the same as yours and our $C^L(Z)$ agrees with it: the hash scenario is less compositional because $K(f') > K(f)$ (note that $K(Z|W) = K(f)$ or $K(f')$ in this case, due to perfect predictability).

Given the extensive exchange above, we would be curious to know whether our comments above have addressed your concerns about predictability vs. compositionality with regards to $C^L$ and, more generally, if there are any further points that would increase you support for our paper.

OK, but just to clarify---should I interpret this comment as adding additional stipulations to the definition that aren't present in the paper? Either:

• Models "aren't overfit". What makes scheme 1 overfit and scheme 2 not overfit? More generally, what does "overfitting" mean here, given that none of the definitions presently make any reference to generalization?

• The particular programming model with which respect to which we're measuring $K$ complexity happens to have a short program for Dirac deltas and a long program for Gaussians. Kolmogorov complexity is typically only defined up to a constant factor, so if these constant factors are really important for choosing solutions to Eq 1, we're not really talking about Kolmogorov complexity in a general sense---we're tied to some specific model of computation, but it's currently not clear what that is (or why it's better than any of the other models that algorithmic information theory generally treats as interchangeable).

Again, I don't think these issues are insurmountable! But they really need to be locked down if the goal is to enable apples-to-apples between different sets of representations. My concern is that, even if we can agree about how to break the tie for this specific hypothetical, I'd be worried that there are other distributions that still have identifiability problems, and we need yet a different set of extra rules to break the tie in the right way.

Now responding to your new identifiability argument. Please correct us if we've misunderstood your example, but we believe the two different schemes here have different total complexities, and so only one of them satisfies Eq. 1 (scheme 2 in this case)

For scheme 1

1. $p_w$ is (a discrete floating point approximation of) a Gaussian
2. $\mathbb{E}[K(w|p_w)]$ is the entropy of the Gaussian
3. $f$ is trivially simple as it just outputs its input, so $K(f) \approx 0$
4. $\mathbb{E}[K(z|w,f)] = 0$ because $w = z$

For scheme 2

1. $p_w$ puts all its mass on a single $w$ of constant symbols
2. $\mathbb{E}[K(w|p_w)] = 0$ as the trivial constant $w$ has probability of $1$
3. $f$ is trivially simple as it just outputs a constant $(0,1)$, so $K(f) \approx 0$
4. $\mathbb{E}[K(z|w,f)]$ is the entropy of a Gaussian (the same as 2. in scheme 1)

Comparison of the two schemes

In the end, scheme 1 step 2 cancels with scheme 2 step 4, and then in both schemes the remaining steps contribute zero complexity except for step 1. For scheme 1, $K(p_w) =$ the complexity of defining a Gaussian distribution. For scheme 2, $K(p_w) =$ the complexity of a point-mass distribution, which is simpler than a Gaussian. We therefore have that scheme 2 is the only valid decomposition according to Eq. 1 in our paper, and compositionality is therefore $C(Z) = K(Z|W,f) / K(Z|W,f) = 1$ (as we would intuitively expect, structureless noise is not compositional).

Again we can explain what's going on by thinking of a mixture of Gaussians, with modes indexed by $W$. If there are no such modes (as in structureless noise), then $p_w$ and $W$ will not pay the complexity cost of representing other bits in $Z$, since they can simply be captured by the error term.

Both are constant-sized programs, but if we're talking about the formal definition and whether it is identifiable in this thought experiment, the length of that constant-sized program needs to be taken into account.

For actual implementation with neural networks, there would be no issue for your example: neural networks for $p_w$ and $f$ (if not overfit) would just learn a point-mass distribution for $p_w$ and a constant output for $f$. This is because such a solution would give the lowest training error $K(Z|W,f)$ that can be achieved without overfitting to $Z$.

Hi---thanks for all the helpful responses! It seems like both of the issues I raised above really stem from the same source, which is a set of unstated assumptions about which functions are "simple" or "complex". These assumptions are in fact critical for determining which representation systems are compositional or non-compositional. In particular:

Compositionality vs predictability: Sorry if this wasn't clear; I was imagining applying the hash after performing the lookup (so calling $H$ rather than $H^{-1}$), but I think it also works the way you've described here. The only difference between the two schemes is a single invocation of the (inverse) hash function, which takes constant space to represent, so the difference between the two schemes will in general be negligible for large numbers of representations. (And who's to say we're not computing $K$ w/r/t some esoteric programming language where $H$ gets applied by default on top of every function call, so that scheme 1 actually has a longer program?)

Here I think it would be really helpful if you could give an example of two systems, both of which have the property that representations are predictable from encodings, but where the difference in compositionality between the two systems can be made arbitrarily large.

Identifiability: It seems like we're on the same page here, in the sense that we agree that Eq 1 has two minima, one saying random noise is highly compositional, and the other saying that random noise is highly non-compositional. The only way to break the tie is to stipulate that some kinds of distributions (arbitrarily) have longer descriptions than others.

One of the earlier comments refers to these points as "splitting hairs", which I really want to push back against. In a "formal definition of compositionality", the formalism needs to be fully spelled out. Right now, it takes several paragraphs of handwaving and special constant factors to correctly describe a set of i.i.d. samples from a Gaussian---and extremely simple and extremely fundamental object of study. Standard ways of measuring Kolmogorov complexity ignore these constant factors altogether, but here they are critically necessary. But right now there's nothing stated explicitly enough to argue about, and I don't know how I would generalize the stipulations given in the comments above to any other distribution.

The authors agreed in a previous comment that

Kolmogorov complexity is defined up to a constant factor

But they also agree that many crucial predictions from this approach depend on constant-factor differences in Kolmogorov complexity. So the approach is not well-defined.

This is a fundamental problem that must be fixed before we have the "formal theory of compositionality" promised by the title. All that said, I hope this discussion has been helpful! If the paper gets in this cycle, I hope the authors at least see fit to mention these issues in a footnote, and if not I look forward to seeing how they are resolved in a future version of the paper.

I really want to echo what the other reviewers have said about this being a clearly written and conceptually interesting piece of work. I would love to see it at a future ML conference, where I think it has the potential to be one of the better pieces of work. But I also feel very strongly that it should not be published in its current form.

Thank you for your continued interaction!

Overall, we believe that we’re on the same page with respect to tricky parts of the definition. The identifiability issues you have raised are important to resolve in a neater way that rests on simpler arguments than the ones provided in our responses (although we stand by those arguments). The limitations applying to Kolmogorov complexity in general that you’ve mentioned (e.g., only defined by to a constant, dependence on the programming language) also apply to our work, which makes significant use of Kolmogorov complexity.

Where we still disagree or course is whether or not the paper is ready for publication despite these limitations. We believe that it is.

1. The conceptual link between compositionality, compression, and meaning being a simple function of parts has been hinted at in some prior work, but we believe we are the first to dissect it in a systematic and direct way, with both theoretical machinery and concrete examples. As a whole, we believe that this perspective is both novel and useful to the field, with the potential to spawn follow-up works that build on our ideas.
2. Our definition of language system compositionality, which pertains to a W and Z that are both given (and is a setting that the reviewer believes important), does not have identifiability issues in the current version of our paper.
3. We believe that using deep learning machinery to estimate compositionality as it is conceptualized in our paper will not suffer from identifiability issues in practice, as specifying architectures for different components of the generative model imposes significant additional constraints. We also believe that it will give results consistent with intuition; the framework resembles reconstruction-based methods described by the reviewer which have already proven useful in estimating compositionality, but without making strong assumptions such as linear additivity of part embeddings that our definition suggests are unnecessary.

All this being said, we are very grateful to the reviewer for their excellent feedback and are actively working on addressing it. We perhaps should have put more emphasis on the “Towards…” part of our title (we will take the reviewer’s advice into account and do so in the next version we upload), and we hope that we can refine the compression-based perspective of representational compositionality through more productive conversations like these.

Note regarding a concrete example where two representations that are equally predictable from their parts can have arbitrarily high differences in compositionality

We believe that our paper already contains such examples using synthetically-generated representations. For instance, lookup table representations with increasingly high “disentanglement”, where the representation is a function of n-grams. If n is made larger, the lookup table defining $f$ becomes more complex (has more parameters needed to define it) and the representation is less compositional. We don’t have to think too hard about the Kolmogorov complexity in this case; if a lookup table grows substantially in size, a longer program will be needed to define it in any reasonable programming language (in short, a large lookup table is less compressible). While we can always consider an esoteric programming language in which the large lookup table is pre-defined, this sort of thing is a limitation with Kolmogorov complexity in general, not only our work, and it is more artificial than substantial (no such programming languages actually exist). If we consider increasingly long sentences $W$, we can make the complexity of $f$ arbitrarily high (and compositionality arbitrarily low) for large n (but not n=1), despite these cases all having equal predictability (they are all deterministic). Our synthetic grammar experiments admit similar examples (e.g., grammars with arbitrarily many production rules defining $f$).

We thank the reviewer for their excellent points, which we hope we adequately address.

What is the relationship between representational compositionality and compositional generalization, and does it provide any additional insight?

We hypothesize that representations which are compositional according to our definition 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 a 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 compositionalities of many model representations using our definition and then correlate this score with compositional generalization ability. We strongly believe that this work would be out of scope for our current paper, which already introduces many novel ideas.

Furthermore, we believe that representational compositionality relates to other important topics in machine learning outside of compositional generalization. For instance, representational compositionality has significant implications for generative models that reason in latent space (akin to thought in human cognition), since this generation can be done in the space of constituent parts in a way that generalizes through simple semantics.

We have now edited our paper to include these important discussions (as well as connections to papers cited by the reviewer) in a new Appendix section E, which describes hypotheses regarding compositional generalization, ideas for future work to test these hypotheses, and relations to other topics outside of compositional generalization.

Implementing the framework for estimating compositionality suggested in Appendix B and empirically evaluating the relationship between representational compositionality and compositional generalization would increase the impact of the paper.

We completely agree that both of these are very interesting research directions. We are actively working on implementing the method for estimating $C(Z)$ described in Appendix B as well as studying the empirical relationship between $C(Z)$ and compositional generalization (which we now discuss in a new Appendix E, as explained above). However, the core contribution of the current paper is theoretical in nature, with the goal of introducing and justifying our definitions. We wish to stress that these are novel ideas that require a standalone paper; measuring representational compositionality using new deep learning tools and evaluating its empirical relationship to compositional generalization would themselves be novel and substantive contributions.

Is topological similarity very sensitive to the dimensionality of the word embeddings, given that in high-dimensions vectors tend to be more orthogonal?

This is absolutely correct: for example, as the reviewer points out, in the sentence length experiments having shorter sentences with more high-dimensional word embeddings will lead to the resulting representations more often being orthogonal. In general, topological similarity is highly sensitive to dimensionality effects (like orthogonality in high dimensions) that greatly influence geometry and distance metrics. This is an important point of motivation to define a novel metric that does not suffer from this and other flaws.

Could you apply the prequential coding method to the synthetic examples in Section 4.1, to further validate it?

Thank you for the suggestion. We are actively running these experiments and will reply in this thread when we have edited the paper accordingly. In the past, we have looked at the effect of disentanglement on prequential code length and found that it strongly correlated with the true underlying complexity $K(Z|W)$, so we expect this to hold with our other results.

Could you specify the numerical values on the y axis in Fig. 2?

We did not include these mainly for aesthetic reasons, since it would have compressed the graph horizontally as we would have required different scales for each plot, and different scales for each metric (representational compositionality (ours) and topological similarity). We didn’t feel this was an issue, as the only thing we wanted to highlight in these experiments was the trends in compositionality scores rather than absolute values. As a compromise, though, we have now updated Fig. 2 to include numerical values showing the min/max of each metric for each plot, which preserves the horizontal space of the plots. Please let us know if this is sufficient, and if not we can attempt to do some more reorganization of the figure as a whole to make more space for numerical values along the entire axes.

Thank you for the comment and for your interest in our work! Compositionality of functions is indeed a very important topic in machine learning, and we agree that it can and has been nicely formalized using ideas from compositional generalization. However, what we attempt to define here is the compositionality of representations, rather than functions. For instance, a representation might be the latent activity in some intermediate layer of a neural network, or some brain region. There is no current definition for the compositionality of representation, although we have intuitions about them (for instance, "disentangled" representations are a paradigmatic examples). In this paper, we are attempting to formalize and generalize these intuitions.

Note that in our reply to other reviewers and in our updated paper, we plan to clarify the relationship between representational compositionality (as we define it) and compositional generalization, and indeed this will relate to the "function compositionality" of the function processing the representation. In particular, we hypothesize that increased representational compositionality puts fewer demands on the structure (or compositionality) of the downstream function required for compositional generalization. As we will explain in those other responses, however, representational compositionality also relates to other important topics apart from compositional generalization (e.g., generative models in latent space, multi-task adaptation, etc.). Crucially, we believe that both of these notions of compositionality (of representation and of function) are crucial to understand and formalize for machine learning and cognitive science.