Thank you very much for your helpful review. We are glad that you liked our paper. Below we respond to your questions and criticisms. We hope that our answers address your concerns.

Clarity of our setup

We appreciate your comments on the clarity of our setup and we agree that our presentation of this was needlessly confusing. We have attempted to clean up this presentation. In particular, we now clarify early on that we generally consider models with compositionally structured inputs and immediately introduce our definition for this class of representations (Definition 3.1). While disentangled models are an example of how such a representation could arise, they are no longer a part of our general setup (and we have removed this part from Fig. 1 as well). This is more consistent with the setup as presented e.g. in Jarvis et al. (2023) and Abbe et al. (2023). We also note that we have introduced a small notational change and now refer to the input as $x$ and the underlying components represented by that input as $z=(z_c)_c$. The input $x$ and the underlying components $z$ are connected by the definition of compositionally structured representations.

Overall, we hope that our revised Section 3.1 clarifies the specific theoretical setup we consider. We are thankful to the reviewer for their very helpful comments on this topic and would appreciate hearing whether you think the new presentation is better.

Below we respond to your specific comments on this topic.

The paper discusses compositional generalization with respect to compositional representations, but equates compositional representations with disentangled representations. I think it’s fair to say that other compositional structures are possible in additional to disentanglement (...). I would make it very clear in the introduction that you are only considering disentangled representations, and that these are a subset of what might be considered compositional representations more generally.

Thank you for highlighting this. We want to emphasize that our theory captures not just disentangled representations but the broader class of compositionally structured representations -- a point that our previous presentation left unclear. By providing the definition of compositional structure early on, we hope to clarify this. We also agree that this does not capture all kinds of compositional representations and now clarify in the introduction that we define a specific class of compositionally structured representations.

At times it is unclear whether this work is about compositional tasks (tasks where the optimal solution would necessitate some compositional representation/function), compositional inputs/datasets, or compositional representations of inputs. All three are used at various times, which leads to confusion about the scope of what is being studied, especially in earlier parts of the paper before section 3.1 where it becomes clear that is the disentangled representation which would have been extracted in some earlier part of a model, like an intermediate layer in a neural network. Even after 3.1, though, at times “input” and “representation” are used interchangeably, which causes confusion. This extends even into the discussion section (”dataset statistics and compositional generalization” as opposed to “representation statistics and compositional generalization”).

Thank you for this comment. We have gone through the manuscript to try and standardize our terminology. In general, we now refer to the input $x$ as an input and only as a representation insofar as $x$ represents the underlying components. Further, we always refer to $\phi(x)$ as a representation.

The sections introducing kernel regime and kernel model, in particular in Sections 2 and 3.2, can be cleaned up. Overall, I suggest a restructuring of the content regarding kernel models and your setup. After the introduction, I would suggest immediately introducing your setup and defining variables, as is done currently in Section 3.1, and then describing kernel models within that framework. While doing this, keep a concrete running example that makes it clear what $x$, $z$, $\phi$, and $K$ would refer to on some task that readers would be familiar with. The related work can come after this setup, so that we can make a connection between the related work and your particular setting.

Thank you for this suggestion. We are a bit hesitant to implement it because we're concerned that the related work section will break the flow between model setup and theory. However, we also see that it would make the discussion of kernel models in the related work more immediately relevant. We're hoping that our current changes have already addressed some of your concerns; in particular, we're now introducing the multi-hot input example immediately at the beginning of Section 3 as a guiding example. But we're also open to making further changes to our presentation of the model setup.

Thank you very much for your helpful review. Below we respond to your questions and criticisms. We hope that our answers address your concerns.

Practical relevance of compositionally structured representations

An important concern of the reviewer was the extent to which compositionally structured representations are practically relevant:

However, I do believe the assumption that perfect disentangled representations are achievable harms the applicability of the paper’s results.

The paper assumes that perfect disentangled representations are accessible, which could be easily violated in practical scenarios. Then, how will the results change when the representations are partially disentangled? If the theoretical analysis under this more practical condition is hard, some experimental results under a non-perfect case would be helpful.

We agree that this is an important concern --- indeed, in practice, representations are likely not exactly compositionally structured. In our theory, we wanted to investigate the limitations that arise even in the best-case scenario of a perfectly compositionally structured representation. Indeed, we'd like to emphasize that despite the relative simplicity of this case, its generalization behavior has so far been poorly understood.

The non-perfect case may introduce new issues, but we expect that the limitations highlighted in the compositionally structured case will still affect generalization behavior. In particular, our theorem implies that kernel models with compositionally structured representations implement conjunction-wise additive functions. This means that they are unable to perform tasks that cannot be expressed in these terms, such as transitive equivalence. We expect that the constraint to conjunction-wise additive generalization behavior (and the resulting inability to generalize on transitive equivalence) extends to other representations as well. In the revised manuscript, we have added two new analyses that provide evidence for this claim: a novel theoretical result on randomly sampled, Gaussian representations and an empirical analysis of disentangled DSprites representations, analyzing the 1,800 models studied in Locatello et al. (2019). We give an overview of our insights in the general response. In the revised manuscript, we discuss these analyses in detail in Appendices A.5 and C. Additionally, we now discuss the relationship between our theoretical setup and practically relevant representations at the end of Section 4 (l. 286-298). We thank the reviewer for the suggestion to consider this non-perfect case, and in particular for suggesting the DSprites dataset.

Briefly, we find that in both cases, conjunction-wise additivity provides a good description of average-case behavior. As a result, we find that these models are also incapable of systematic generalization on transitive equivalence. Further, whereas our analysis of the influence of representational geometry provides a good characterization of Gaussian representations, these insights break down much more strongly in the case of the DSprites representations.

We hope that our new presentation explains how our theory relates to practically relevant scenarios and would appreciate your feedback.

Thank you very much for your helpful review. Below we respond to your questions and criticisms. We hope that our answers address your concerns.

§6: Am I correct in assuming all models are randomly initialized and not trained? (...) As the code will not be published, these details are essential to ensure reproducibility. I recommend adding a corresponding section detailing initialization, architecture, and other specifications to the main text or appendix.

Importantly, these models are trained with backpropagation and all weights in those models are trained, in the case of the ConvNet and the ResNet using SGD and in the case of the ViT using Adam. They are all initialized using He initialization. We provide further details on their architecture in Appendix C.1 and have made this description more extensive in the revised manuscript. Additionally, we will also upload our codebase to ensure reproducibility. Thank you for pointing this out and we apologize for the confusion.

The paper is quite dense and not easily accessible to readers. I can see that the authors attempted to illustrate their theoretical findings on a few example tasks to convey some intuition, but the explanation of the example tasks is still frequently very technical and hard to parse. For example, it is still somewhat unclear to me why transitive equivalence is ruled out by Thrm. 4.1 (see also minor suggestions below).

LL269: Why does $f_{12}(z)$ "fall away"? I assume because $f_J(z_{12})=0$, but why? Could you elucidate this on a brief example?

Thank you for pointing this out that this could be presented in more intuitive terms. To make the connection to the theorem explicit, this is because for test set items, the conjunction has never been seen during training and so is not a part of the sum in Eq. 4. As a result the model cannot use the conjunctive term $f_{12}(z)$. More intuitively, the unseen conjunctive terms correspond to a direction in representational space that was not seen during training (as this specific combination of components was never seen) and, as a result, the model did not change its weights in this direction and they remained at their initial value of zero. We now provide a novel diagram in the appendix (Fig. 5) that aims to convey the central insights of Section 4. We have also added a paragraph directly after the theorem explaining its central insights (l. 244-252).

Given Thrm. 4.1, I would have appreciated a short discussion on existing compositional generalization tasks from the literature, e.g., from Schott et al., or Locatello et al., or Hupkes et al. Which of these tasks would be solvable by a kernel model? Could the insights from this paper aid in understanding why the existing literature on the usefulness of disentangled representations is so divided?

We agree that it would be useful to further link Theorem 4.1 to the literature. Both Locatello et al. and Schott et al. consider as their downstream task direct decoding of the underlying components. This is a conjunction-wise additive (and indeed component-wise additive) computation. However, linear readout models may still fail to generalize on these tasks due to a memorization leak and a shortcut bias. Indeed, we analyze two simple instances of this problem in Appendix D.3 (invariance and partial exposure) and find that they are affected by these failure modes. Intriguingly, Schott et al. also report a regression to the mean (Section 5.3 in their paper) which is consistent with memorization leaks and shortcut biases. Our paper theoretically explains why this regression to the mean may arise in the linear readout setting. We have added a sentence explaining this connection (l. 396-399).

Our work is related to existing literature on disentangled representations in that we find that subtle differences in representational geometry and training data (in particular on the context dependence task) can yield substantially different generalization behavior: for example, the darkgreen region in representational geometry space in Fig. 3c robustly generalizes on CD-3, whereas the lightgreen region consistently does not generalize. Depending on the exact nonlinearity and depth chosen, neural network representations may either be in one of these regions or the other. This emphasizes how subtle changes in experimental settings can substantially change conclusions --- as disentangled representations are often evaluated in terms of a linear readout, this may explain why empirical evaluations of these representations have often been inconsistent between different experimental setups. We briefly mention this in l. 414-419 and have added a sentence making this connection explicit. Thank you for pointing out these connections. We are quite excited about the ways in which our theory may speak to these existing lines of research and appreciate the opportunity to clarify these connections.

Thank you very much for your helpful review. We are glad that you agree that understanding compositional generalization is an important problem and appreciate your constructive feedback. We hope that the response below addresses your questions and your criticisms. We'd love to continue discussing these points; in particular, we'd appreciate your thoughts on our clarified theoretical contributions (directly below).

Clarifying our contributions

The overall presentation is quite confusing and hard to follow and I am having a hard time even understanding what the precise contribution of the paper is, what assumptions are being made and what conclusions can be drawn from it. In particular, what is drawn from the results is mixed up with the precise theoretical results. It would be great to have one section that is really precise and doesn't immediately tries to generalise to pre-trained models, before outlining precisely how and in what way the results might generalise to empirical models and tasks.

Thank you for this comment. In light of it, we wanted to briefly state our main theoretical contribution here as clearly as possible, and also make explicit our assumptions and their limitations. We have also modified the text and introduced a schematic figure (Fig. 5) to the manuscript in order to make presentation more clear.

• We introduce compositionally structured representations, which are defined as representations whose trial-by-trial similarity only depends on the number of overlapping components between the two trials (now defined in Definition 3.1).
• We then analyze the compositional generalization of kernel models instantiated by first transforming these representations by deep neural networks, then learning the weights on a linear readout of this representation. This allows us to capture the representational changes that happen as a compositional representation is modified by a neural network, what kind of compositional generalization is possible following learning on the resulting representation.
• We find that the representations remain compositionally structured after having been processed by the deep neural network (in the infinite-width limit) (now stated in Proposition 4.1).
• We find that kernel models with compositionally structured representations are limited to a conjunction-wise additive computation on the test set (Theorem 4.2). This refers to any compositional computation that can be performed by summing compositional features and combinations of features seen during training, and can capture a suprisingly large number of compositional behaviors. This allows us to identify which tasks are fundamentally unsolvable by these models and thus require different learning mechanisms. We spell out these consequences in Section 4.3.
• In Section 5, we then analyze in more detail how the training data and the deep neural network influence the generalization behavior of these models on conjunction-wise additive tasks. Although these tasks can be performed by a conjunction-wise additive computation, we identify two failure modes that can still disrupt generalization by preventing kernel models from discovering the right computation: memorization leak and shortcut bias.
• These failure modes result from imbalances in the training data, and we note that deep neural networks show the same qualitative sensitivity to training data imbalances as well.

We appreciate your suggestions on how to make our contributions in Section 4 clearer and have modified our manuscript accordingly. In particular, we now introduce compositionally structured representations when first introducing the task setup (i.e. in Section 3.1) and further present all of our theoretical contributions in theorem environments (whereas Definition 3.1 and Proposition 4.1 were previously just stated in paragraphs). We have also removed discussion of potential applications of our theory from this section in order to focus on explaining our concrete results. Instead, we have now added a final paragraph to the section where we discuss the relationship between our theory and practically relevant scenarios, and in particular clarify when our theory cannot directly speak to these scenarios. Thank you for this suggestion.

Improving presentation of the theoretical setup

The reviewers pointed out several aspects of the presentation they thought could be improved. We respond to their suggestions in detail in the individual responses and give an overview here. The biggest change we've made to our presentation is in Section 3.1. Specifically, we now immediately define our class of compositionally structured representations (Definition 3.1; previously defined in Section 4), rather than discussing only disentangled input representations. This enables us to clarify the scope of our theory from the beginning. As part of these changes, we now also explicitly separate the components underlying the input (which we continue to denote by $z=(z_c)_c$) and the input itself (which we now denote by $x\in\mathbb{R}^d$). To further clarify our theoretical insights in Section 4, we have also added a new schematic figure illustrating these insights (Fig. 5). Finally, we now also provide a more concrete intuition about what a conjunction-wise additive computation is (l. 244-252). We note that to accommodate for these changes, we moved section 7 (the brief outlook on the role of feature learning) fully into the appendix (Appendix F).

Overall, we really appreciate everyone's detailed comments on which aspects they found clearly explained and which aspects they'd like to see improved. We hope that our revised manuscript addresses the reviewers' concerns and would appreciate their further feedback.