When does compositional structure yield compositional generalization? A kernel theory.

## Abstract

Abstract Compositional generalization (the ability to respond correctly to novel combinations of familiar components) is thought to be a cornerstone of intelligent behavior. Compositionally structured (e.g. disentangled) representations are essential for this; however, the conditions under which they yield compositional generalization remain unclear. To address this gap, we present a general theory of compositional generalization in kernel models with fixed representations, a tractable framework for characterizing the impact of dataset statistics on generalization. We find that kernel models are constrained to adding up values assigned to each combination of components seen during training (“conjunction-wise additivity”). This imposes fundamental restrictions on the set of tasks these models can learn, in particular preventing them from transitively generalizing equivalence relations. Even for compositional tasks that kernel models can in principle learn, we identify novel failure modes in compositional generalization that arise from biases in the training data and affect important compositional building blocks such as symbolic addition and context dependence (memorization leak and shortcut bias). Finally, we empirically validate our theory, showing that it captures the behavior of deep neural networks (convolutional networks, residual networks, and Vision Transformers) trained on a set of compositional tasks with similarly structured data. Ultimately, this work provides a theoretical perspective on how statistical structure in the training data can affect compositional generalization, with implications for how to identify and remedy failure modes in deep learning models.

## 1 Introduction

Humans’ understanding of the world is inherently compositional: once familiar with the concepts “pink” and “elephant,” we can immediately imagine a pink elephant. Stitching together concepts in this way lets humans generalize far beyond our prior experience, allowing us to cope with unfamiliar situations and imagine things that do not yet exist (Lake et al., ; Frankland & Greene, ).
Understanding the basis of compositional generalization in humans and animals, and building it into machine learning models, is a long-standing and historically vexing problem (Fodor & Pylyshyn, ; Battaglia et al., ; Lake & Baroni, ).
While a wide range of studies have investigated the conditions under which compositionally structured (i.e. “disentangled”) representations can be learned (Hinton et al., ; Higgins et al., ; Träuble et al., ; Whittington et al., ; Ren et al., ), it remains unclear when learning these representations is actually useful to a downstream neural network. Some work suggests that disentangled representations improve compositional generalization (Esmaeili et al., ; van Steenkiste et al., ). However, others challenge this view (Locatello et al., ; Schott et al., ). In general, it remains unclear why insights from some compositional tasks fail to generalize to others, and a systematic understanding of the relationships among compositional tasks remains elusive (Hupkes et al., ).

To make progress on this question, we focus on standard statistical learning, a fundamental basis for compositional generalization that affects almost any machine learning model. Generalization in statistical learning depends on the similarities between different inputs. Notably, in compositionally structured representations, inputs that have components in common (say, a red circle and a blue circle) are more similar to each other than inputs that do not (say, a red circle and a blue square). As a result, the compositional structure of a task is reflected in its dataset statistics, influencing the generalization behavior of the model.

To understand when and how statistical learning leads to successful compositional behavior, we developed a theory for the behavior of kernel models on compositional tasks. Kernel models are an important class of statistical models that are able to provide a simplified approximation to neural networks while maintaining analytical tractability (Jäkel et al., , ). For example, kernel models accurately describe the behavior of learning and fine-tuning in neural networks under certain conditions (Jacot et al., ; Malladi et al., ). More broadly, they provide a tractable framework for characterizing the impact of dataset statistics on generalization (Canatar et al., , ).

Despite their broad relevance and relative simplicity, it has remained unclear how even kernel models generalize on compositional tasks (though see Abbe et al., ; Lippl et al., , see Section 2). To address this gap, we present a theory of compositional generalization in kernel models. We define a general family of compositional tasks with no constraints on the input-output mapping (ensuring broad applicability of our theory), theoretically characterize the compositional behavior of kernel models trained on such tasks, and go beyond kernel models to empirically validate our theory in several relevant deep neural network architectures. Our specific contributions are as follows:

- •
In Section 4, we show that kernel models with disentangled inputs are constrained to summing up values implicitly assigned to each component or combination of components seen during training. We call such computations “conjunction-wise additive.”
- •
In Section 5, we then characterize how representational geometry determines whether kernel models will generalize successfully on conjunction-wise additive compositional tasks, highlighting two important failure modes (memorization leak and shortcut bias). This highlights that disentangled representations are not sufficient for downstream compositional generalization (even on conjunction-wise additive tasks) and explains why.
- •
Finally, in Section 6, we validate our theory in several deep neural network architectures, showing that it captures their behavior on conjunction-wise additive tasks.

Overall, we take a step towards a general theory of compositional generalization by characterizing the impact of dataset statistics on compositional generalization for a broad range of tasks. Our theory systematically clarifies the compositional generalization behavior of deep neural networks and lays a foundation for the design of new learning mechanisms that overcome their limitations.

## 2 Related work

Compositional generalization.
Compositionality is an important theme in both human and machine reasoning problems, including visual reasoning (Lake et al., ; Johnson et al., ; Schwartenbeck et al., ), language production (Hupkes et al., ), and rule learning (Ito et al., ; Abdool et al., ).
Recent breakthroughs have led to massive improvements in models’ compositional capacities, but in some cases, these models still fail spectacularly (Srivastava et al., ; Lewis et al., ; West, ).
Attempts to improve compositional generalization often leverage meta-learning (Mitchell et al., ; Wu et al., ; Lake & Baroni, ) or modular architectures (Andreas et al., ), in the hopes that different modules will specialize for different components (Schug et al., ). Constraining a network to be linear (or additive) can guarantee modular specialization and compositional generalization (Lachapelle et al., ; Wiedemer et al., , ). However, these networks are extremely limited in the tasks they can learn (as we will show below) and end-to-end training of modular architectures without such constraints often does not result in the desired specialization (Bahdanau et al., ; Mittal et al., ; Jarvis et al., ).

Conjunctions. Henceforth, we will call a combination of components a conjunction. Conjunctive codes have a long history in neuroscience (Alvarado & Rudy, ; Baker et al., ), and are theoretically linked to the formation of highly specific episodic memories.

Kernel regime.
When using gradient descent, ridge regression, or similar learning algorithms to train the readout weights of a model $f_{w}(z)=w^{T}\phi(z)$, it can be shown that the resulting behavior of that model can be described in terms of the kernel $K(z,z^{\prime})=\phi(z)^{T}\phi(z^{\prime})$ induced by the representation $\phi(z)$ (Schölkopf, ). We will refer to such models as kernel models. Notably, when trained on a dataset $\{(x_{i},y_{i})\}_{i=1}^{n}$, a kernel model can be written in its “dual form” as

$$ $\textstyle f_{a}(z)=\sum_{i=1}^{n}a_{i}K(z,z_{i}),\mbox{ for dual coefficients }a\in\mathbb{R}^{n}.$ (1) $$

Prior work has shown that neural networks with large initial weights or wide architectures are well approximated by gradient descent on a model with a fixed representation (a kernel model) (Jacot et al., ). This is called the “kernel regime,” in contrast to the feature-learning regime, which is brought forth, for example, by small initial weights or small width (Chizat et al., ).

Norm minimization.
Gradient descent, ridge regression, and neural networks in the kernel regime learn the readout weights that describe the training data with minimal $\ell_{2}$-norm (Soudry et al., ; Gunasekar et al., ; Ji et al., ).
Norm minimization is a standard theoretical framework for analyzing how representational geometry and dataset statistics influence generalization (Canatar et al., , ) and we here apply it to the compositional task setting. This is similar to Lippl et al. () who characterize model behavior on a specific compositional task (transitive ordering) and Abbe et al. () who characterize the inductive bias of norm minimization for inputs with binary components in the limit of infinite components. Compared to these prior works, we analyze a broader range of compositional tasks and derive exact constraints for finite numbers of components.

Memorization leak.
Machine learning models sometimes memorize (parts of) their training data instead of learning a generalizable rule (Zhang et al., ; Dasgupta et al., ). This may improve generalization on long-tailed data (Feldman, ), but often impairs out-of-distribution performance (Elangovan et al., ). We find that models partially memorize their training data even when they extract the correct rule. Jarvis et al. () analyze a related phenomenon in deep linear networks.

Shortcut learning.
Shortcut learning refers to models exploiting spurious correlations between certain features of the input data and the target (Shah et al., ; Nagarajan et al., ). This substantially impacts their performance out of distribution (where those correlations may not hold) (Geirhos et al., ).
We theoretically analyze how shortcut biases impact compositional generalization.

## 3 Model and task setup

### 3.1 Task space

We assume that our model extracts from its input a set of disentangled components $(z_{c})_{c=1}^{C}$, e.g. color, shape, and background (Fig. 1a). For instance, the model could have been pre-trained to extract these components from an image or an input sentence. Each component $z_{c}\in Z_{c}\subset\mathbb{R}^{d}$ is drawn from a discrete set of possible components represented by $d$-dimensional real vectors and because we consider categorical components, we assume that all components have unit magnitude and are orthogonal to each other (these assumptions can be relaxed, Section A.1). We then assume that the model represents these components by adding them together: $z:=\sum_{c=1}^{C}z_{c}$. A simple example of this is given by a concatenation of one-hot representations of all components (Fig. 1a).
The target, $y\in\mathbb{R}$, is given by an arbitrary function of $z$, ensuring that our framework is agnostic to the underlying compositional structure. After training models on certain combinations of components $Z^{\text{train}}\subset Z=\prod_{c=1}^{C}Z_{c}$, we assess generalization on all other combinations $Z^{\text{test}}:=Z\setminus Z^{\text{train}}$.

Our theory applies to any task in this family; that is, any task with a fixed number of categorical input components and a scalar output, regardless of the input-output mapping. Below we describe three example tasks within this general framework that represent important building blocks for compositional reasoning in machine learning and cognitive science. We will focus on these tasks in the main text, to illustrate our general theory and analyze its consequences in more detail. In Appendix D, we describe additional tasks captured by our theory.

Symbolic addition. Many tasks involve inferring a magnitude associated with different underlying components (e.g. adding handwritten digits) (Lorenzi et al., ; Sheahan et al., ). We consider two components $(z_{1},z_{2})$ with unobserved assigned values $v_{1}(z_{1})$ and $v_{2}(z_{2})$. The target is the sum of those values: $y=v_{1}(z_{1})+v_{2}(z_{2})$. After sufficient exposition to individual items, a model with an additive structure can generalize to novel combinations of items. In particular, we consider nine input elements $[-4],[-3],\dotsc,[4]$ with associated values $-4,-3,\dotsc,4$ and training sets containing all pairs where at least one component is equal to a certain subset of values (given by the rows and columns in the training set in Fig. 1b). We vary the size of this subset (i.e. the number of rows/columns) as well as whether the task requires only interpolation or also extrapolation.

Context dependence. The relevance of different stimuli often depends on our current context. Taking this into account is a crucial aspect of cognition in humans and animals (Bouton et al., ; Taylor & Ivry, ; Parker & Hollister, ; Ito et al., ). We therefore consider a task with three input components $(z_{\text{co}},z_{f1},z_{f2})$. The context ($z_{\text{co}}$) has two possible values specifying whether $z_{f1}$ or $z_{f2}$ determine the response. Both features have six possible values which are split up in two categories. If the model has learned this context dependence, it should be able to generalize to novel feature combinations. We evaluate on the subset of data for which $z_{f1}$ indicates Cat. 2 and $z_{f2}$ indicates Cat. 1. In the most extreme generalization test (CD-3), we leave out the entire subset; in easier versions, we leave out combinations of two or one of those features (CD-2 and CD-1) (Fig. 1c).

Transitive equivalence.
Relational reasoning is an important example of compositional generalization and often involves extending learned relations to new item combinations (Halford et al., ; Battaglia et al., ). Given an unobserved (and arbitrary) equivalence relation, the task is to determine whether two presented items $(z_{1},z_{2})$ are equivalent. The model should generalize to novel item pairs using transitivity ($A=B$ and $B=C$ imply $A=C$) (Fig. 1d). This is an important instance of relational cognition (often studied as “associative inference” in cognitive science (Schlichting & Preston, ; Spalding et al., )). Although prior work has found that kernel models often successfully generalize on a transitive *ordered* relation ($A>B$ and $B>C$ imply $A>C$, Lippl et al., ), the behavior of kernel models on equivalence relations has remained unclear.

### 3.2 Models

Kernel models.
Our theory characterizes kernel models with a disentangled input $z\in\mathbb{R}^{d}$ that apply a transform $\phi(z)\in\mathbb{R}^{h}$ and learn a linear readout, $f_{w}(x):=w^{T}\phi(z)$, using gradient descent or ridge regression (Fig. 1a). For $\phi$, we consider a neural network with random weights (in the infinite-width limit; see Section A.3). Our model setup includes as a special case the random feature model studied by Abbe et al. () and further captures training via backpropagation in the kernel regime.

Deep neural networks. Additionally, we consider a broad range of deep neural network architectures: convolutional networks, residual networks (He et al., ), Vision Transformers (ViTs; Dosovitskiy et al., )), and ReLU networks; all trained through backpropagation. The code required to reproduce all experiments can be found at [https://github.com/sflippl/compositional-generalization](https://github.com/sflippl/compositional-generalization).

Figure: Figure 1: a, Theoretical setup: a disentangled representation of the input, followed by a nonlinear transform $\phi$ and a learned linear readout $w$. b, Example training sets for symbolic addition. The grid represents nine components with associated values $-4,-3,\dotsc,4$. The training set consists of certain rows and columns of this grid. c, Context dependence. In context 1, feat. 1 determines the category; in context 2, feat. 2 determines the category. The training sets leave out different subsets of the lower right orthant. d, Transitive equivalence: six items are split up into two arbitrary equivalence classes (e.g. A,B,C and D,E,F) and generalization requires transitive inference over equivalence classes.
Refer to caption: x3.png

## 4 Kernel models are conjunction-wise additive

Our primary theoretical contribution in this work is to characterize the full range of compositional computations that can be implemented by kernel models with disentangled inputs. We find that even though these models can learn arbitrary training sets, their test set behavior is restricted to adding up values assigned to each conjunction (combination of components) seen during training. We call this motif “conjunction-wise additivity.” Below, we formally state our finding and explain its implications.

### 4.1 Random networks yield compositionally structured representations

We first note that a linear readout of the disentangled input representation effectively constrains the model to adding up a value for each component (“component-wise additivity”):

$$ $\textstyle f(z)=w^{T}z=w^{T}\sum_{c=1}^{C}z_{c}=\sum_{c=1}^{C}f_{c}(z_{c}), \quad f_{c}(z_{c}):=w^{T}z_{c}.$ (2) $$

Although models of this class perfectly generalize on component-wise additive tasks, such as symbolic addition, they are incapable of even learning the *training data* (much less generalizing) on tasks that are not component-wise additive. In particular, these models cannot learn context-dependent computations or equivalence relations — both fundamental instances of compositional reasoning.

The nonlinear transform $\phi(z)$ can overcome this constraint; in particular, multi-layer nonlinear neural networks can learn arbitrary training data (in the infinite-width limit) (Hornik et al., ; Cybenko, ; Rigotti et al., ). In general, the wide range of possible neural network architectures and their nonlinearities makes it difficult to derive general statements about their representations, but in this case we can take advantage of a particularly useful property of disentangled categorical inputs. That is, its induced kernel, $K(z,z^{\prime})=z^{T}z^{\prime}$, depends only on the number of components that are identical between both inputs (specifically, $K(z,z^{\prime})=c$ if $c$ components are identical). We call any representation that satisfies this criterion “compositionally structured” (see Section A.2 for further motivation). Notably, in the infinite-width limit, the kernel of random weight neural networks, $K_{\phi}(z,z^{\prime})=\phi(z)^{T}\phi(z^{\prime})$, depends only on the input kernel $K(z,z^{\prime})$, making $K_{\phi}(z,z^{\prime})$ also compositionally structured (Cho & Saul, , see Section A.3).
This representational constraint allows us to derive strong constraints on the models’ generalization behavior.

### 4.2 Compositionally structured kernel models are conjunction-wise additive

We find that any kernel model with a compositionally structured representation is constrained to be conjunction-wise additive. To formally state this finding, we define, for each $z\in Z$, the set of conjunctions for which $z$ overlaps with some element in the training set $z^{\text{tr}}\in Z^{\text{train}}$,

$$ $\text{Conj}(z|Z^{\text{train}}):=\left\{J\subseteq\{1,\dotsc,C\}|\exists z^{ \text{tr}}\in Z^{\text{train}}:\forall c\in J:z_{c}=z^{\text{tr}}_{c}\right\}.$ (3) $$

We then prove:

###### Theorem 4.1 .

Consider a kernel model $f$ with a compositionally structured representation and training data $Z^{\text{train}}$. For any such model, we can find conjunction-wise functions $f_{J}:\prod_{c\in J}Z_{c}\to\mathbb{R}$, where $J\subseteq\{1,\dotsc,C\}$, such that for any input $z\in Z$, the model response is given by

$$ $\textstyle f(z)=\sum_{J\in\text{Conj}(z|Z^{\text{train}})}f_{J}(z_{J}),\quad z _{J}:=(z_{c})_{c\in J}.$ (4) $$

We prove Theorem 4.1 in Section A.4, but to develop an intuition for why this theorem holds, we consider an example representation concatenating one-hot vectors representing each component and conjunction of components. For example, if $C=2$, this representation will concatenate one-hot representations of each component with a one-hot representation of the conjunction of both components.
The readout weight for a conjunction $z_{J}$ seen during training will change (in Eq. 4, this weight is given by $f_{J}(z_{J})$). In contrast, the weights associated with conjunctions not seen during training remain at their initial value of zero (which is why we only sum over $J\in\text{Conj}(z|Z^{\text{train}})$).

###### Theorem 4.1 .

### 4.3 Conjunction-wise additivity constrains the tasks kernel models can solve

Theorem 4.1 immediately implies that compositionally structured kernel models cannot solve any task that cannot be expressed in conjunction-wise additive terms. This highlights fundamental computational restrictions on a broad range of models — including pre-trained models with disentangled representations that are finetuned in the kernel regime and infinite-width neural networks. Intriguingly, these restrictions are not caused by an architectural constraint, as the model can learn arbitrary training data. Rather, we highlight restrictions on how models – without any architectural constraints – can *generalize* (Zhang et al., ). Below we spell out the consequences of these restrictions.

First, for inputs with two components, the model’s behavior on the training set can be expressed as $f(z)=f_{1}(z_{1})+f_{2}(z_{2})+f_{12}(z)$. However, on the testing set, $f_{12}(z)$ falls away and the model is constrained to be component-wise additive: $f(z)=f_{1}(z_{1})+f_{2}(z_{2})$.
A striking consequence of this is that compositionally structured models – including infinite-width neural networks and regardless of implementational details – can only generalize on component-wise additive tasks. In particular, this implies that these models cannot generalize on transitive equivalence — a fundamental instance of relational reasoning. Intriguingly, transitive ordering – a superficially similar task – can be solved by a kernel model. This highlights the importance of a formal perspective on compositional tasks.

For inputs with more than two components, a conjunction-wise additive computation additionally encodes partial conjunctions between components (e.g. 12, 13, and 23 for three components). For test inputs, the model cannot rely on the unseen full conjunction 123, but it can rely on any partial conjunction it has seen before.
To see whether a kernel model can, in principle, generalize on such a task, we must 1) identify the conjunctions seen during training, $\text{Conj}(z|Z^{\text{train}})$, for each $z\in Z^{\text{test}}$, and 2) determine whether the target can be written as a conjunction-wise sum. For example, for context dependence, for all new test inputs, we have seen the context-feature conjunctions 12 and 13, but not the feature-feature conjunction 23. As a result, model behavior on the test set can be written as

$$ $f(z)=f_{1}(z_{\text{co}})+f_{2}(z_{f1})+f_{3}(z_{f2})+f_{12}(z_{\text{co}},z_{ f1})+f_{13}(z_{\text{co}},z_{f2}).$ $$

While context dependence is not component-wise additive, it is conjunction-wise additive. This is because we can encode it using $f_{12}$ and $f_{13}$: $f_{12}(z_{\text{co}},z_{f1})$ encodes the target when the context $z_{\text{co}}$ indicates the $z_{f1}$ as relevant and is zero otherwise; $f_{13}(z_{\text{co}},z_{f2})$ works in the opposite way. Thus, the model can, in principle, identify a set of weights that would allow it to generalize correctly.

This example illustrates that conjunction-wise additivity tells us both *whether* kernel models with compositionally structured representations can solve a certain task, and also *how* they solve it. As we noted, these insights immediately transfer to any model with compositionally structured representations that is trained or fine-tuned in the kernel regime. Because our theory determines the compositional computations emerging from dataset statistics, it is also likely to shed light on other learning models, including feature-learning deep neural networks (see Section 6).

Lastly, our theory tells us how to make a task non-additive: in Section D.2.3, we describe such a modification to context dependence that tests generalization to novel context-feature conjunctions. By helping us design hard benchmark tasks that are not solvable by kernel models, our framework grounds research into learning mechanisms that can implement other compositional computations.

## 5 Representational geometry still impacts generalization on conjunction-wise additive tasks in kernel models

Conjunction-wise additivity only determines whether kernel models can, in principle, solve a certain task. However, model generalization also depends on whether the model identifies the correct conjunction-wise function. This depends on the model’s representational geometry and the dataset statistics.
As noted in Section 2, the behavior of kernel models depends on their representation $\phi(z)$ only through the induced kernel $K_{\phi}(z,z^{\prime})$. In this section, we employ the modular approach suggested by this insight: We first investigate how different choices in network architecture influence its induced kernel (Section 5.1). Then, we characterize task performance on symbolic addition and context dependence across the full range of compositionally structured representations (Section 5.2).

### 5.1 Overlap salience characterizes compositional representational geometry

Figure: Figure 2: Representational salience (for three input components) in a random weight neural network with variable numbers of layers and nonlinearities.
Refer to caption: x4.png

In Section 4, we found that a broad range of transformations yield compositionally structured representations, i.e. representations that have the same similarity $K(z,z^{\prime})$ for all inputs $z,z^{\prime}$ overlapping in the same number of components. To characterize representations in this space, we introduce a new metric: representational salience. We formally define this metric in Section B.1. Intuitively, for $c=1,\dotsc,C$, the salience $S(c;C)$ measures the unique contribution of the subpopulation representing a conjunction of $c$ components. Further, $S(c;C)$ is normalized so that the salience of all components and conjunctions of components sums up to one. For example, the input representation only encodes single components and therefore $S(1;C)=1/C$ and, for all $c>1$, $S(c;C)=0$.

$S(c;C)$ is computed from the representational similarities $K(z,z^{\prime})$. It is useful because unlike those similarities, it makes immediately apparent how strongly different conjunctions are encoded (Section B.2). Further, it reduces the set of $C+1$ similarities characterizing the space of compositionally structured representations to $C-1$ free parameters: It removes the overall magnitude of the representation (by normalizing) and the baseline activity (by excluding the similarity between inputs with no overlap). This choice reflects the fact that both of these parameters often have negligible impact on model behavior (Section B.3).

We now analyze how $S(c;C)$ evolves over different layers of a random network, using an input with three components as an example (Fig. 2; see Section B.4 for other values of $C$). At the input stage, only individual components are represented and so $S(2;3)$ and $S(3;3)$ are zero. As the network gets deeper, these saliences increase, whereas $S(1;3)$ decreases. Eventually, the salience of the intermediate conjunction $S(2;3)$ decreases again, whereas $S(3;3)$ continues to increase. Indeed, for ReLU networks, we prove the following statement:

###### Proposition 5.1 .

For a random neural network with a (leaky) ReLU nonlinearity, as $L\to\infty$, $S(k;C)\to 0$ for $k<C$ and $S(C;C)\to 1$.

We prove the proposition in Section B.5. It implies that in very deep networks, the full conjunction dominates the representation, making compositional generalization to overlapping inputs harder.

###### Proposition 5.1 .

### 5.2 Kernel models suffer from memorization leak and shortcut bias

While there are many readout weights that can lead to minimal error, kernel models trained with gradient descent or ridge regression learn the weights with minimal $\ell_{2}$-norm (see Section 2). We now characterize how this inductive bias influences compositional generalization across different representational geometries. To characterize the full range of compositionally structured representations, we compute the behavior of the model directly using the kernel (see Appendix C). Importantly, as implied by our modular approach, our analysis clarifies the behavior of all random weight neural networks, including those covered in the previous section.

Symbolic addition suffers from a memorization leak.
We first consider an example case ($S(1;2)=0.4,\mathcal{W}=\{0\}$). We find that though the model perfectly learns the training cases, it underestimates the test cases by a proportional factor (Fig. 3a). To understand why, we consider the model’s functional form on the training cases: $f(z)=f_{1}(z_{1})+f_{2}(z_{2})+f_{12}(z)$ (see Section 4). Intuitively, $\ell_{2}$-norm minimization tends to yield distributed weights. As a result, unless the salience of the conjunction $S(2;2)$ is zero, the kernel model will associate some non-zero weight with it (i.e. $f_{12}(z)\neq 0$). This, in turn, necessarily distorts the generalization on the test set, $f(z)=f_{1}(z_{1})+f_{2}(z_{2})$.

We call this tendency to use the full conjunction (and its effect on generalization) “memorization leak.” To characterize it more systematically (and add mathematical rigor to the intuition above), we analytically characterize model behavior on a general family of symbolic addition tasks:

###### Proposition 5.2 .

Consider inputs $z_{1},z_{2}\in\{[v]\}_{v\in\mathcal{V}},\mathcal{V}\subset\mathbb{R}$, with associated values $v$. We assume that the training set contains all pairs such that at least one component is $z_{c}\in\{[w]\}_{w\in\mathcal{W}},\mathcal{W}\subset\mathcal{V}$ and that the average value in both $\mathcal{V}$ and $\mathcal{W}$ is zero. Then, model behavior on the test set is given by

$$ $f([v_{1}],[v_{2}])=m(v_{1}+v_{2}),\quad m:=\tfrac{p\cdot S(1;2)}{1+(p-2)S(1;2) },\quad p:=|\mathcal{W}|$ (5) $$

We prove the proposition in Section D.1. It implies that for this entire task family, model generalization is distorted by a proportional factor $m$ (see Fig. 3b). The formula implies that $m<1$ as long as $S(1;2)<\tfrac{1}{2}$ (i.e. as long as $S(2;2)>0$). Further, $m$ is smaller for lower $S(1;2)$ and smaller training set size $p$. (Note that $\mathcal{W}$ corresponds to the rows/columns making up the example training sets in Fig. 1b.) Interestingly, these are the only two factors that influence $m$. In particular, while interpolation is often seen as easier than extrapolation, this does not impact model behavior here.

More broadly, the memorization leak is a ubiquitous issue for statistical learning models trained on compositional tasks: $\ell_{2}$-norm minimization tends to yield distributed weights and so if the conjunctive population is represented, the model will generally end up partially relying on this conjunction. As shown above, this necessarily distorts generalization (see also Section D.3 for a minimal example).

Figure: Figure 3: Kernel models’ behavior on (a,b) symbolic addition and (c,d) context dependence. a, Model predictions on training and test set plotted against ground truth for an example case ($S(1;2)=0.4$, $\mathcal{W}=\{0\}$). b, The slope of the test set as a function of $S(1;2)$ and the training set size $p=|\mathcal{W}|$. c, Generalization on context dependence as a function of representational salience. Trajectories of networks with different nonlinearities are highlighted (color scale see Fig. 2). d, Coefficients of the different conjunction types for two example networks with three layers and different nonlinearities.
Refer to caption: x5.png

Context dependence suffers from a shortcut bias.
Next, we empirically analyzed model generalization on context dependence across different representational geometries and training sets. We found that on a given task, each model either generalizes with 100% or 0% accuracy. For CD-3 (the task version leaving out the largest subset of feature combinations), the model only generalizes when $S(2;3)$ is high relative to $S(1;3)$ (Fig. 3c, dark green area). As a result, whether the network generalizes is highly sensitive to the nonlinearity and depth of the network. In contrast, for CD-2 and CD-1, a much wider range of representational geometries generalizes successfully.

To understand this phenomenon, we determined the total magnitude of model weights associated with the different conjunctions (Fig. 3d). We found that unsuccessful models (e.g. blue color in Fig. 3d) had much larger magnitudes associated with the context component and the full conjunction. Notably, on CD-3, context is highly correlated with the target and can predict 2/3 of the training data. Models with high $S(1;3)$ (context) and $S(3;3)$ (full conjunction) exploit the context shortcut and use the full conjunction to learn the remaining training data. This strategy explains why these models fail to generalize to the test set. For CD-2, context is much less predictive on the training data (accuracy of $\tfrac{9}{16}$). This explains why only very low $S(2;3)$ yields failure to generalize on CD-2 or CD-1.

Our analysis shows how model and task structure interact to either give rise to a generalizable rule or a statistical shortcut (see Section D.3 for a minimal example). This highlights that for compositional tasks with strong spurious correlations, model behavior will be highly sensitive to architectural details affecting the representational geometry such as depth and nonlinearity.

###### Proposition 5.2 .

## 6 Our theory describes the behavior of deep networks on conjunction-wise additive tasks

Figure: Figure 4: Testing our theory in deep networks trained on MNIST and CIFAR versions of compositional tasks. Ranges indicate mean $\pm$ one std. error (often too small to be visible). a, $S(1;2)$ in an intermediate ConvNet layer for different distances between digits. Lower distance yields a more conjunctive representation. b, Average model prediction for each combination of components plotted against the ground truth (MNIST, distance of zero, $\mathcal{W}=\{0\}$). Generalization on the compositional split is distorted by a proportional factor. c, d, Slope of this linear relationship across all datasets as a function of c, distance (each line corresponding to a particular $\mathcal{W}$) and d, training set (for a distance of zero). For MSE instead of slope, see Fig. 9. e, Accuracy on all variants of context dependence.
Refer to caption: x6.png

So far, our analyses have been limited to simple kernel models, for their analytical tractability. We next test whether the insights developed from these simple models extend to a broader class of models: large-scale neural networks. We considered symbolic addition and context dependence on inputs created by concatenations of images from MNIST (Lecun et al., ) or CIFAR-10 (Krizhevsky et al., ). Each component corresponds to random samples from a particular category rather than the one-hot input considered so far and we study both in-distribution and compositional generalization.
Notably, different image categories are not necessarily equally correlated with each other. To control for this, we randomly permuted the assignment of categories to components for each ($n=10$) experiment.
We considered several relevant vision architectures: convolutional networks (ConvNets, LeCun et al., ) (trained on MNIST) and residual networks (ResNets, He et al., ) and Vision Transformers (ViTs, Dosovitskiy et al., ) (trained on CIFAR-10).

Spatial distance of components impact salience in internal representations.
First, we examined how changes in the input structure impact the networks’ representational geometry. We hypothesized that the ConvNets’ local weight structure should produce a more conjunctive representation for digits that are closer together. To test this, we determined $S(1;2)$ in an intermediate layer of the network, averaging over different instances of all digits. We found that $S(1;2)$ was indeed smaller for lower distances (Fig. 4a), indicating a more conjunctive population. This suggests that varying the distance between two digits provides a practical way of manipulating $S(1;2)$; below we use this insight to test predictions about how conjunctivity influences generalization behavior.

Deep networks implement a conjunction-wise additive computation.
Conjunction-wise additivity imposes a substantial computational restriction: on test set inputs, models can only add up values assigned to each conjunction of components seen during training. We therefore investigated whether the deep networks’ computations could be captured in these terms. Remarkably, we found that such a model was highly predictive of the model responses (see Section C.2). This indicates that large-scale neural networks tend to implement conjunction-wise additive computations — at least when trained on conjunction-wise additive tasks. Our theory suggests that they do so because the statistical structure of the dataset makes such a computation natural.

Deep networks are impacted by a memorization leak on symbolic addition.
Having found that our theory captures the networks’ general computational structure, we investigated whether it was also able to explain their specific performance. We first considered symbolic addition, training the ConvNets on seven different training sets with 20,000 samples and the ResNets and ViTs on three training sets with 40,000 samples. We varied both the size of $\mathcal{W}$ and whether generalization required interpolation or also extrapolation (Section D.1.3).

We tested three theoretical predictions made by Proposition 5.2. First, our theory predicts that the model’s test set response should be distorted by a proportional factor. To test this, we plotted the average model prediction for each combination of categories against the ground truth. We found that model predictions were indeed compressed relative to the ground truth, but still exhibited a strong linear relationship (Fig. 4b). This was also the case for ResNets and ViTs, which exhibited a slightly noisier linear relationship (Fig. 8). The memorization leak therefore affects generalization in large-scale networks as well. This is especially significant as our theoretical argument suggests that memorization leaks likely arise for a broad range of compositional tasks.

We then estimated the slope of this linear dependency for each dataset. Our theory predicts that the compositional generalization slope should increase with increasing $S(1;2)$ (i.e. increasing distance between components, Fig. 4a). On ConvNets, we found that higher distance indeed increases the slope (Fig. 4c). This was not due to an increase in task difficulty, as in-distribution generalization is not systematically affected by distance. On ResNets and ViTs, higher distance also yielded a higher slope on the compositional generalization set (though the effect was much subtler for ViTs). (Notably, these networks did not perfectly predict the training split, which may affect the results.)

Finally, our theory predicts that larger $\mathcal{W}$ should increase the compositional generalization slope. Our experiments confirmed this prediction (Fig. 4d). Further, whether the training set required interpolation or also extrapolation did not systematically affect the resulting slope, as predicted by our theory (though interestingly, it did affect in-distribution generalization). However, there was one exception to this: for $p=4$, the extrapolation dataset had a smaller slope than the interpolation data set. Our theory can therefore explain much but not all of the deep network behavior.

Deep networks are impacted by a shortcut bias on context dependence.
Lastly, we trained the ConvNets on an MNIST version of context dependence using 30,000 training samples and the ResNets and ViTs on a CIFAR-10 version of the task using 40,000 training samples. Again, their behavior was aligned with the kernel theory’s predictions, having better-than-chance accuracy on CD-1 and CD-2, but having worse-than-chance accuracy on CD-3 (Fig. 4e). This confirms that the deep networks also suffered from a context-driven shortcut on CD-3.

## 7 Outlook: feature learning enables non-additive compositional generalization

In the previous section, we found that neural networks trained on symbolic addition or context dependence implement a conjunction-wise additive computation. However, conjunction-wise additivity is not the only mechanism by which deep neural networks generalize compositionally. To demonstrate this, we show in Appendix E that feature-learning networks can generalize on transitive equivalence (a non-additive task) due to their tendency to learn low-dimensional internal representations. This highlights that neural networks can implement non-additive compositional computations. Future work should explore more systematically how feature learning impacts compositional generalization.

## 8 Discussion

Humans often generalize to new situations by stitching together concepts and knowledge from prior experience in new ways. Despite the broad importance of this ability (both for cognitive science and machine learning), a general theory of when and how neural networks accomplish compositional generalization has remained elusive. Here we have taken a step towards formalizing this relationship by characterizing kernel models with compositionally structured representations, a framework that captures neural network training in the kernel regime and more broadly lets us understand the impact of dataset statistics on generalization. We found that they implement a specific compositional computation (“conjunction-wise additivity”). We then investigated how dataset statistics and representational geometry impact successful generalization, highlighting two failure modes arising from the inductive bias of gradient descent (memorization leak and shortcut bias). Finally, we validated our theory in deep neural networks trained on natural image data.

Our results show how simple statistical models can implement (or at least approximate) abstract rules like context dependence. However, they also highlight that building in compositional structure by itself is often insufficient for compositional generalization. Indeed, contextual generalization is highly sensitive to the specific representational geometry and training data. This may explain why investigations into compositional generalization and the benefits of disentangled representation have yielded such inconsistent results. Overall, our insights highlight the utility of kernel models in systematically investigating model generalization (or at least generating an initial hypothesis as to the important factors). We here used these models to characterize deep neural networks, but they could be equally useful for better understanding human compositional generalization.

While our work covers a broad range of different tasks, a number of limitations remain. Though out of scope here, it would be interesting to test this theory in extremely large-scale models, e.g. large language models. Future work should also consider inputs and outputs with broader ranges of formats (e.g. sequences with variable length) as well as representations that are not compositionally structured. Most importantly, our theory is limited to a particular learning mechanism (fixed features with linear readout); other learning mechanisms could either implement a conjunction-wise additive model that overcomes the failure modes highlighted here or implement novel compositional computations beyond conjunction-wise additivity (we gave an initial example of this in Section 7). By clarifying the general relationship between dataset statistics and compositional generalization, our theory provides an important foundation for such advances.

## Acknowledgements

We are grateful to the members of the Center for Theoretical Neuroscience for helpful comments and discussions. We thank Elom Amematsro, Ching Fang, and Matteo Alleman for detailed feedback. The work was supported by NSF 1707398 (Neuronex), Gatsby Charitable Foundation GAT3708, and the NSF AI Institute for Artificial
and Natural Intelligence (ARNI).

## Appendix A Mathematical analysis

### A.1 Generalized compositionally structured representations

In the main text, we considered “compositionally structured” representations. This is the class of representations $\phi(z)$ whose kernel $K_{\phi}(z,z^{\prime})=\phi(z)^{T}\phi(z^{\prime})$ only depends on the number of components $z$ and $z^{\prime}$ have in common. Here we define a slightly more general class of representations whose kernel depends on the *identity* of the components they have in common, i.e.

$$ $O(z,z^{\prime}):=\{c=1,\dotsc,C|z_{c}=z_{c}^{\prime}\}.$ (6) $$

Thus, pairs of representations overlapping in the first component may have a different similarity than pairs of representations overlapping in the second component, but any pair of representations overlapping in the first component still need to have the same similarity. This case captures, for example, cases where one feature is more salient than another and therefore influences the representational similarity more strongly, or where conjunctions between certain components are more saliently represented than conjunctions between other components. For example, perhaps our input consists of two objects with different shapes and colors. In that case, we may wish to represent the conjunction between shape and color of the first object more strongly than the conjunction between the shape of the first object and the color of the second.

Note that we consider the constrained definition of compositionally structured representations in the main text purely for didactical purposes. In particular, our observations in Sections A.3 and A.4 extend to all generalized compositionally structured representations.

### A.2 Why are we considering compositionally structured representations?

So far, we have motivated the concept of compositionally structured representations in terms of the fact that disentangled representations as well as many nonlinear transforms of disentangled representations are compositionally structured. Here we discuss a more conceptual motivation for them: compositionally structured representations guarantee that the only basis for generalization is the compositional nature of the data. This is because we ensure that the model has no knowledge about certain components that may be more similar to each other. Otherwise, the component-wise similarity could serve as a basis for generalization. For example, in transitive equivalence (Fig. 1d), if items that are in the same equivalence class are represented as more similar to each other, that would serve as a basis for generalization on the task that is not compositional in nature. For this reason, we are particularly interested in compositionally structured representations, as they ensure that kernel models are only able to generalize compositionally.

Characterizing compositional generalization in non-compositionally structured representations requires us to meaningfully distinguish between compositional and non-compositional aspects of their generalization. We consider this question out of scope for this manuscript, but believe it would be interesting future work.

### A.3 Nonlinear transformations and compositional structure

A broad range of transforms $\phi$ induces a kernel $K_{\phi}(z,z^{\prime})=\phi(z)^{T}\phi(z^{\prime})$ that only depends on the input similarity $K(z,z^{\prime})=z^{T}z^{\prime}$. In particular (as noted in the main text), this condition is satisfied by the hidden layers and neural tangent kernel of randomly initialized neural networks (in the infinite-width limit) (Han et al., ):

###### Definition A.1 .

Given an input $z\in\mathbb{R}^{d}$, a network depth $L\geq 2$, and a set of widths $H_{1},\dotsc,H_{L}\in\mathbb{N}$, we define a neural network by recursively defining the operation $\phi^{(l)}$ of the $l^{\text{th}}$ layer as

$$ $a^{(0)}:=z,\quad a^{(l)}:=\phi^{(l)}(a^{(l-1)}):=\sigma\left(\tfrac{1}{\sqrt{H _{l}}}\left(W^{(l)}a^{(l-1)}+b^{(l)}\right)\right),\quad W^{(l)}\in\mathbb{R}^ {H_{l}\times H_{l-1}}$ (7) $$

where $W^{(l)}$ and $b^{(l)}$ are i.i.d. sampled from a random distribution and $\sigma:\mathbb{R}\to\mathbb{R}$ is a nonlinearity. The complete transform is then given by $\phi:=\phi^{(L)}\circ\dotsb\circ\phi^{(1)}$.

The infinite-width limit is characterized by $H_{1},\dotsc,H_{L-1}\to\infty$ (the order of these limits does not matter). This setup includes, in particular, the random feature model investigated by Abbe et al. ().

Further, the condition is met by most commonly used kernel functions including any radial basis function that depends on the Euclidean $\ell_{2}$-norm (e.g. the Gaussian kernel). Any nonlinear transform that meets this condition also conserves compositional structure, i.e. if $z$ is compositionally structured then so is $\phi(z)$. This allows us to derive computational restrictions on this broad range of models.

###### Definition A.1 .

### A.4 Proof of Theorem 4.1

See 4.1

###### Proof.

Because the kernel $K$ is compositionally structured, its similarity $K(z,z^{\prime})$ only depends on the overlap $O(z,z^{\prime})\subseteq\{1,\dotsc,C\}$ (see definition in Eq. 6). We denote the similarity for inputs overlapping in $S\subseteq\{1,\dotsc,C\}$ by $\kappa_{S}$ and define set of training items overlapping with $z\in Z^{\text{test}}$ in $S$ as

$$ $Z^{\text{train}}(z,J):=\left\{z^{\text{tr}}\in Z^{\text{train}}|\forall_{c\in J }z_{c}=z^{\text{tr}}_{c}\right\}.$ (8) $$

The key idea is to decompose $Z^{\text{train}}$ into these different overlaps in order to separate the sum into its components. However, by our definition, the datasets $Z^{\text{train}}(z,J)$ are not disjoint. Indeed, $S\subseteq S^{\prime}$ implies $Z^{\text{train}}(z,J)\subseteq Z^{\text{train}}(z,J^{\prime})$ and in particular $Z^{\text{train}}(z,\emptyset)=Z^{\text{train}}$. To adjust for this, we define $\delta_{J}$ as the similarity added by $\kappa_{S}$ to the similarity between conjunctions with one component fewer, recursively defining

$$ $\delta_{\emptyset}=\kappa_{\emptyset},\quad\delta_{J}=\kappa_{J}-\sum_{J^{ \prime}\subsetneq J}\delta_{J^{\prime}}.$ (9) $$

We then decompose

$$ $f(z)=\sum_{z^{\text{tr}}\in Z^{\text{train}}}a_{z^{\text{tr}}}K(z,z^{\text{tr} })=\sum_{J\subseteq\{1,\dotsc,C\}}\delta_{S}\sum_{z^{\text{tr}}\in Z^{\text{ train}}(z,J)}a_{z^{\text{tr}}}.$ (10) $$

This equality obtains because for each $z\in Z,z^{\text{tr}}\in Z^{\text{train}}$,

$$ $\sum_{J:z^{\text{tr}}\in Z^{\text{train}}(z,J)}\delta_{J}=\delta_{O(z,z^{\text {tr}})}+\sum_{J^{\prime}\subsetneq O(z,z^{\text{tr}})}\delta_{J^{\prime}}= \kappa_{O(z,z^{\text{tr}})}=K(z,z^{\text{tr}}),$ (11) $$

which is true by definition.
We note that for $J\notin\text{Conj}(z|Z^{\text{train}})$, $Z^{\text{train}}(z,J)=\emptyset$. Defining

$$ $f_{J}(z):=\delta_{J}\sum_{z^{\text{tr}}\in Z^{\text{train}}(z,J)}a_{z^{\text{ tr}}},$ (12) $$

proves the proposition.
∎

###### Proof.

## Appendix B Representation salience: a metric for compositionally structured representations

### B.1 Definition

Below we formally define representational salience. To do so, we denote the similarity between two trials $z,z^{\prime}$ by $\text{Sim}(O(z,z^{\prime})):=K(z,z^{\prime})$. Note that this is well-defined for compositionally structured representations, as $K(z,z^{\prime})$ is identical for all pairs of trials with the same $O(z,z^{\prime})$. We then define:

###### Definition B.1 .

For a generalized compositionally structured representation with kernel $K$ and a conjunction $J\subseteq\{1,\dotsc,C\}$, we recursively define

$$ $\textstyle\overline{S}(\emptyset):=K(\emptyset),\quad\overline{S}(J):=\text{ Sim}(J)-\sum_{J^{\prime}\subsetneq J}\overline{S}(J^{\prime}),\quad S(J)= \tfrac{\overline{S}(J)}{\sum_{\emptyset\neq J\subseteq\{1,\dotsc,C\}}\overline {S}(J)}.$ (13) $$

When emphasizing the total number of components, we denote $S(J;C)=S(J)$. Further, for compositionally structured representation, the similarity only depends on the total number of overlaps $|J|$. We therefore write $S(c;C)=S(J)$, where $c:=|J|$.

###### Definition B.1 .

### B.2 Why is representational salience a useful metric?

Intuitively, the representational salience captures the unique contribution of a population representing a particular conjunction $J$ (as in our informal definition in the main text). As we noted in the main text, distinguishing these unique contributions from the similarities directly would be more difficult. For example, changes in the similarity between inputs having two components in common could arise from changes in how saliently single components or conjunctions of two components are represented. To distinguish between these cases, we’d have to additionally look at the similarity between inputs having a single component in common. Our definition of representational salience avoids this issue; we therefore believe that this perspective could more broadly be useful for analyzing representations of compositional data.

### B.3 Why does representational salience leave out magnitude and baseline activity?

Notably, many learning models are largely invariant to a constant rescaling of their representation. For limit behavior (e.g. in the limit of infinite training in gradient descent), this scale has no impact. We see this, for instance, in Proposition 5.2, where the scaling turns out to be entirely irrelevant. For regularized models, on the other hand, the scale of the representation is confounded with the strength of the regularization and so we suggest that it is again best seen as separate from the representational geometry.

The baseline activity, on the other hand, may determine how easily an intercept is learned. However, many linear readout models (e.g. support vector machines) do not regularize their intercept, again rendering this parameter entirely irrelevant. Notably, in the case of gradient descent, the magnitude of the baseline activity does influence how easily an intercept is learned. However, the impact of this is often negligible; for example, in Proposition 5.2, we again find that the baseline activity is entirely irrelevant.

### B.4 Extended representational analysis

Figure: Figure 5: Extended analysis of overlap salience in random neural networks. a, Salience of the first component (1), the second component (2), and their conjunction (12), where we vary the two components’ saliences in the input. b, Salience for inputs with four components.
Refer to caption: x7.png

We computed the saliences by iteratively computing the representational similarities using the kernels derived in prior work (Cho & Saul, ; Tsuchida et al., , ; Han et al., ). In Fig. 5b, we plot the different saliences for an input with four components. Now the salience of overlap 2 and 3 both first increase and then decrease and, just like for inputs with three components (Fig. 2), a Gaussian and rectified quadratic nonlinearity yields a particularly high salience for these intermediate conjunctions. Notably, they appear to be trading off the salience of these conjunctions differently: the rectified quadratic nonlinearity more strongly emphasizes overlaps of three whereas the Gaussian nonlinearity more strongly emphasizes overlaps of two. This highlights that for larger numbers of components, the dependence of generalization behavior on specific architectural choices will likely be even stronger.

Finally, we consider an example of a generalized compositionally structured representation. Here we assume that the different input components have different magnitudes. In particular, we consider a disentangled representation whose first component has a salience between $s\in[0.1,0.5]$ and whose second component accordingly has a salience $1-s$ (Fig. 5a). As the random weight neural network becomes deeper, the more salient component (in this case component 2) increasingly dominates the representation. While the salience of the full conjunction still eventually converges to one for most nonlinearities, it takes longer to do so for a less balanced input representation. Further, for a Gaussian nonlinearity, an imbalanced representation actually decreases the limit salience the representation appears to be converging to for the full conjunction. This highlights that for disentangled representations that do not represent all components with equal magnitude, compositional generalization behavior may vary strongly with different neural network architectures.

### B.5 Proof of Proposition 5.1

See 5.1

###### Proof.

Note that the proof is a minor extension of Lemma S1.3 in Lippl et al. (). We present it here in a self-contained manner. We consider a nonlinearity

$$ $\sigma(u):=A\min(u,0)+\max(u,0),\quad A\in[0,1).$ (14) $$

By prior work (Cho & Saul, ; Tsuchida et al., , ; Han et al., ),

$$ $\mathbb{E}_{w}\left[\phi({w}^{T}{h}^{(l)}(z))\phi({w}^{T}{h}^{(l)}(z^{\prime}) )\right]=\sigma^{2}\|h^{(l)}(z)\|_{2}\|h^{(l)}(z^{\prime})\|_{2}k\left(\hat{h} ^{(l)}(z)^{T}\hat{h}^{(l)}(z^{\prime})\right),$ (15) $$

where

$$ $k(u)=\frac{(1-A)^{2}}{2\pi}\left(\sqrt{1-u^{2}}+(\pi-\cos^{-1}(u))u\right)+Au,$ (16) $$

$\sigma^{2}$ is the variance of the sampled weights, and $\hat{h}=h/\|\hat{h}\|_{2}$.

This means that for any two inputs that have a certain similarity $u$, their similarity in the $L$-th layer is given by $k^{(L)}(u)$, where $k^{(L)}$ denotes the $L$-times application of $k$.
Let distinct trials in the input have a similarity of $\kappa_{d}$ and let identical trials have a similarity of $\kappa_{i}$. Any set of trials with overlapping components will have a similarity $\kappa$, $\kappa_{d}<\kappa<\kappa_{i}$. We denote their corresponding similarity in the $L$-th layer by $\kappa_{i}^{(L)},\kappa_{d}^{(L)},\kappa^{(L)}$. Our goal is now to show that

$$ $\lim_{L\to\infty}s^{(L)}=0,\quad s^{(L)}:=\frac{\kappa^{(L)}-\kappa^{(L)}_{d}} {\kappa^{(L)}_{i}-\kappa^{(L)}_{d}}=0.$ (17) $$

This implies directly that the salience of all partial conjunctions converges to zero, which in turn implies that the salience of the full conjunction converges to one.

(15) implies that $\kappa_{i}^{(L+1)}=\sigma^{2}\kappa_{i}^{(L)}k(1)=\sigma^{2}\kappa_{i}^{(L)}
\tfrac{1+A^{2}}{2}$. Notably, all inputs have the same magnitude and therefore have the same magnitude through all layers; this is given by $\sqrt{\kappa_{i}^{(L)}}$. We can therefore denote

$$ $\kappa^{(L+1)}=\sigma^{2}\kappa_{i}^{(L)}k\left(\kappa^{(L)}/\kappa_{i}^{(L)} \right).$ (18) $$

Thus,

$$ $s^{(L+1)}=\frac{k(\kappa^{(L)}/\kappa_{i}^{(L)})-k(\kappa_{d}^{(L)}/\kappa_{i} ^{(L)})}{k(1)-k(\kappa_{d}^{(L)}/\kappa_{i}^{(L)})}$ (19) $$

We thus define new normalized variables $\hat{\kappa}^{(L)}:=\kappa^{(L)}/\kappa_{i}^{(L)},\hat{\kappa}_{d}^{(L)}:=
\kappa_{d}^{(L)}/\kappa_{i}^{(L)}$, i.e.

$$ $s^{(L)}=\frac{\hat{\kappa}^{(L)}-\hat{\kappa}^{(L)}_{d}}{1-\hat{\kappa}_{d}^{( L)}},$ (20) $$

and therefore

$$ $\hat{\kappa}^{(L)}=(1-\hat{\kappa}_{d}^{(L)})s^{(L)}+\hat{\kappa}_{d}^{(L)}.$ (21) $$

Note that $\hat{\kappa}^{(L+1)}=k(\hat{\kappa}^{(L)})/k(1)$ and $\hat{\kappa}_{d}^{(L+1)}=k^{(}\hat{\kappa}^{(L)}_{d})/k(1)$. We thus define

$$ $\tilde{k}(u):=\frac{k(u)}{k(1)}=u+\frac{\rho}{\pi}(\sqrt{1-u^{2}}-\cos^{-1}(u) u),\quad\rho:=\frac{(1-A)^{2}}{(1+A)^{2}}.$ (22) $$

Note that

$$ $\tilde{k}^{\prime}(u)=1+\frac{\rho}{\pi}\left(-\frac{u}{\sqrt{1-u^{2}}}-\cos^{ -1}(u)+\frac{u}{\sqrt{1-u^{2}}}\right)=1-\frac{\rho}{\pi}\cos^{-1}(u).$ (23) $$

Note that $k(1)=1$ and as for all $0\leq u<1$, $\tilde{k}^{\prime}(u)<1$, this is the only fixed point and $\hat{\kappa}^{(L)},\hat{\kappa}_{d}^{(L)}\to\infty$.
We can therefore define

$$ $s^{(L+1)}=\frac{\tilde{k}\left((1-\hat{\kappa}_{d}^{(L)})s^{(L)}+\hat{\kappa}_ {d}^{(L)}\right)-\hat{\kappa}_{d}^{(L)}}{1-\kappa_{d}^{(L)}}.$ (24) $$

We now determine the fixed mapping to this mapping assuming that $\hat{\kappa}_{d}^{(L)}$ is fixed at some value $d$, i.e.:

$$ $\displaystyle\begin{split}f(s,d)&=\frac{\tilde{k}((1-d)s+d)-\tilde{k}(d)}{1- \tilde{k}(d)}.\end{split}$ (25) $$

$s=0$ is a fixed point. Further,

$$ $\frac{\partial f(s,d)}{\partial s}=\frac{(1-d)\tilde{k}^{\prime}((1-d)s+d)}{1- \tilde{k}(d)}=\frac{(1-d)(1-\tfrac{\rho}{\pi}\cos^{-1}((1-d)s+d)}{1-d-\tfrac{ \rho}{\pi}(\sqrt{1-d^{2}}-\cos^{-1}(d)d)}.$ (26) $$

We now prove that this for $0<s\leq\tfrac{1}{2}$, this derivative is smaller than 1. Specifically,

$$ $\displaystyle\begin{split}&(1-d)(1-\tfrac{\rho}{\pi}\cos^{-1}((1-d)s+d)=\\ &1-d-\tfrac{\rho}{\pi}(\sqrt{1-d^{2}}-\cos^{-1}(d)d)+\tfrac{\rho}{\pi}r(s,d), \end{split}$ (27) $$

where the residual is given by

$$ $\displaystyle\begin{split}r(s,d):=(d-1)\cos^{-1}((1-d)s+d)+\sqrt{1-d^{2}}-d \cos^{-1}d.\end{split}$ (28) $$

We now need to prove that $r(s,d)<0$. Note that $r(s,d)$ is monotonically increasing in $s$ and therefore

$$ $\displaystyle\begin{split}r(s,d)\leq r(\tfrac{1}{2},d)&=(d-1)\cos^{-1}(\tfrac{ 1}{2}+\tfrac{1}{2}d)+\sqrt{1-d^{2}}-d\cos^{-1}d<0,\end{split}$ (29) $$

where we infer the latter inequality by visual inspection of the plot of this function.
∎

###### Proof.

## Appendix C Detailed methods

The code required to reproduce all experiments can be found under [https://github.com/sflippl/compositional-generalization](https://github.com/sflippl/compositional-generalization).

### C.1 Models

##### Kernel model.

We fit the kernel models by hand-specifying the kernel and fitting either a support vector regression or classification using scikit-learn Pedregosa et al. (). Note that this is equivalent to using a feature basis with the same resulting similarities. However, hand-specifying these similarities enabled us to easily explore the full range of possible representations.

##### Rich and lazy ReLU networks.

All networks were trained with Pytorch and Pytorch Lightning Paszke et al. ().
We consider ReLU networks with one hidden layer and $H=1000$ units. We initialize by $\sigma\sqrt{2/H}$, considering $\sigma\in[10^{-6},1]$. In particular, when reporting results on rich networks (without further specification), we assume $\sigma=10^{-6}$. When reporting results on lazy network, we assume $\sigma=1$.

##### Convolutional neural networks.

We considered networks with four convolutional layers (kernel size is five, two layers have 32 filters, two have 64 filters) and two densely connected layers (with 512 and 1024 units). Each layer is followed by a ReLU nonlinearity, and the convolutional stage is followed by a max pooling operation. All weights are initialized with He initialization (He et al., ).

##### Residual neural networks.

We trained a residual neural network with eight blocks in total, two with 16, 32, 64, and 128 channels, respectively, using the Adam optimizer with a learning rate of $10^{-3}$ for 100 epochs.

##### Vision Transformers.

Finally, we trained a Vision Transformer (ViT) with six attention heads, 256 dimensions for both the attention layer and the MLP, and a depth of four, using Adam with a learning rate of $10^{-4}$ for 200 epochs.

##### Data augmentation.

We did not use data augmentation for MNIST. For CIFAR-10, we used a random flip and a random crop.

### C.2 Additivity analysis

To analyze how well a conjunction-wise additive computation can describe network behavior, we considered as the set of possible features a concatenation of one-hot vectors coding for each possible conjunction. We then removed all features that are constant at zero on the training dataset and used linear regression to try and predict network behavior on both training and test set for all remaining features. The resulting $R^{2}$ defines the “additivity” of the network behavior (i.e. $R^{2}=1$ indicates full conjunction-wise additivity). Furthermore, we can use the inferred values assigned to these different conjunctions to compare kernel models, feature-learning networks, and vision networks. Note that for the vision networks, we first average the model predictions across all different images instantiating a given compositional input.

Notably, our theory predicts that the constrained conjunction-wise additive function can predict behavior on the test set, but not necessarily on the training set. To test this prediction in vision network, we compared the additivity of the test set alone to the additivity of the entire dataset (Fig. 6). First, we found that the predictivity on the test set was indeed generally very high. Second, we found that it was substantially higher than on the training and test set taken together.

Figure: Figure 6: $R^{2}$ of the conjunction-wise additive predictor on the test set as well as on both the training and test set.
Refer to caption: x8.png

## Appendix D Compositional task space

### D.1 Symbolic addition

#### D.1.1 Proof of Proposition 5.2

See 5.2

###### Proof.

We split up the training data into

$$ $\mathcal{I}^{(1)}:=\{[w]|w\in\mathcal{W}\}^{2},$ (30) $$

and

$$ $\displaystyle\mathcal{I}^{(2)}$ $\displaystyle:=\bigcup_{w\in\mathcal{W}}\mathcal{I}^{(1,w)}\cup\mathcal{I}^{(2 ,w)},$ (31) $\displaystyle\mathcal{I}^{(1,w)}$ $\displaystyle:=\left\{([w],[v])|v\in\mathcal{V}\setminus\mathcal{W}\right\}, \quad\mathcal{I}^{(2,w)}:=\left\{([v],[w])|v\in\mathcal{V}\setminus\mathcal{W} \right\}.$ (32) $$

We denote the dual coefficient associated with each training point $([i],[j])$ by $a_{ij}\in\mathbb{R}$. Note that the problem is symmetric and therefore we know that $a_{ij}=a_{ji}$. We define a few summed coefficients:

$$ $\displaystyle b_{v}:=\sum_{w\in\mathcal{W}}a_{vw},\quad\overline{b}_{w}:=\sum_ {v\in\mathcal{V}\setminus\mathcal{W}}a_{vw},\quad c_{w}:=\sum_{w^{\prime}\in \mathcal{W}}a_{ww^{\prime}},$ (33) $\displaystyle b:=\sum_{v\in\mathcal{V}\setminus\mathcal{W}}b_{v}=\sum_{w\in \mathcal{W}}b_{w},\quad c:=\sum_{w\in\mathcal{W}}c_{w}.$ (34) $$

Note that the sum over all dual coefficients is given by $2b+c$. Let $p:=|\mathcal{W}|$ and $q:=|\mathcal{V}|-|\mathcal{W}|$. We denote by $\kappa_{c}$ the similarity between inputs overlapping in $c$ components. Then, setting $\delta_{2}:=\kappa_{2}-\kappa_{0}$ and $\delta_{1}:=\kappa_{1}-\kappa_{0}$, the set of dual equations is given by

$$ $\displaystyle([w],[w^{\prime}])\in\mathcal{I}^{(1)}:\kappa_{0}(2b+c)+\delta_{1 }(\overline{b}_{w}+\overline{b}_{w^{\prime}}+c_{w}+c_{w^{\prime}})+(\delta_{2} -2\delta_{1})a_{ww^{\prime}}$ $\displaystyle=w+w^{\prime},$ (35) $\displaystyle([w],[v])\in\mathcal{I}^{(1,w)}:\kappa_{0}(2b+c)+\delta_{1}(b_{v} +\overline{b}_{w}+c_{w})+(\delta_{2}-2\delta_{1})a_{wv}$ $\displaystyle=w+v.$ (36) $$

(Note that the equation corresponding to $([v],[w])$ is equivalent due to the problem’s symmetry.)

The prediction is given by

$$ $f([v_{1}],[v_{2}])=\kappa_{0}(2b+c)+\delta_{1}(b_{v_{1}}+b_{v_{2}}).$ (37) $$

We now sum (36) over $w$ (setting $\overline{w}:=\sum_{w\in\mathcal{W}}w$):

$$ $\displaystyle\begin{split}\overline{w}+pv&=p\kappa_{0}(2b+c)+p\delta_{1}b_{v}+ \delta_{1}(b+c)+(\delta_{2}-2\delta_{1})b_{v}\\ &=((p-2)\delta_{1}+\delta_{2})b_{v}+(2p\kappa_{0}+\delta_{1})b+(p\kappa_{0}+ \delta_{1})c\end{split}$ (38) $$

Thus,

$$ $\delta_{1}b_{v}=\frac{\delta_{1}p}{(p-2)\delta_{1}+\delta_{2}}v+\delta_{1}( \overline{w}-(2p\kappa_{0}+\delta_{1})b-(p\kappa_{0}+\delta_{1})c).$ (39) $$

Thus, setting

$$ $m:=\frac{\delta_{1}p}{(p-2)\delta_{1}+\delta_{2}},\quad d:=2\delta_{1}( \overline{w}-(2p\kappa_{0}+\delta_{1})b-(p\kappa_{0}+\delta_{1})c)+\kappa_{0}( 2b+c),$ (40) $$

we can write

$$ $f([v_{1}],[v_{2}])=m(v_{1}+v_{2})+d.$ (41) $$

To simplify $d$, we sum (35) over all $w,w^{\prime}$:

$$ $\displaystyle\begin{split}2p\overline{w}&=p^{2}\kappa_{0}(2b+c)+2p\delta_{1}(b +c)+(\delta_{2}-2\delta_{1})c\\ &=2p(p\kappa_{0}+\delta_{1})b+(p^{2}\kappa_{0}+2(p-1)\delta_{1}+\delta_{2})c. \end{split}$ (42) $$

We further sum (38) over all $v$, setting $\overline{v}:=\sum_{v\in\mathcal{V}\setminus\mathcal{W}}v$:

$$ $((p+q-2)\delta_{1}+\delta_{2}+2pq\kappa_{0})b+q(p\kappa_{0}+\delta_{1})c=q \overline{w}+p\overline{v}.$ (43) $$

We can now compute $b$ and $c$ from this system of equations and plug it into $d$.

Finally, $\overline{w}=\overline{v}=0$ immediately implies that $b=c=0$ and therefore $d=0$.
∎

###### Proof.

#### D.1.2 Behavior of deep ReLU networks

Next, we examined the behavior of deep ReLU networks with varying depth (Fig. 7). On the extrapolation task ($\mathcal{W}=\{0\}$), these networks also had compressed model predictions on the compositional split that were approximately linearly distorted (though for deeper networks, this relationship seemed to have a slight S-shape). Intriguingly, these networks perfectly generalized on the interpolation task ($\mathcal{W}=\{-4,4\}$). For $\mathcal{W}=\{-2,2\}$, they perfectly generalized on the interpolation portion, but not the extrapolation portion.

Figure: Figure 7: Model prediction plotted against ground truth for different training sets and depths.
Refer to caption: x9.png

#### D.1.3 Behavior of vision models

We trained the Convnets on MNIST using seven different training sets $\mathcal{W}$: $\{[0]\}$, $\{[-4],[4]\}$, $\{[-2],[2]\}$, $\{[-4],[0],[4]\}$, $\{[-1],[0],[1]\}$, $\{[-4],[-3],[3],[4]\}$, $\{[-2],[-1],[1],[2]\}$. This allowed us to vary both the size of the training set and whether it involved only interpolation or also extrapolation. We trained these networks for 100 epochs on 20,000 samples. We trained the ResNets and ViTs on CIFAR-10 using the first three training sets listed above. We trained the ResNets for 100 epochs and the ViTs for 200 epochs, training all networks on 40,000 samples. Our findings on these experiments are summarized in Section 6. Further, Fig. 8 depicts, for each training set, the average prediction for each combination of components. We can see that the ConvNet predictions are highly linearly correlated with the ground truth. The ResNet and ViT predictions are also linearly correlated, but exhibit a slightly noisier relationship.

Figure: Figure 8: Average prediction for each combination of components plotted against the ground truth for a, ConvNets trained on MNIST, b, ResNets trained on CIFAR-10, and c, ViTs trained on CIFAR-10.
Refer to caption: x10.png

Additionally, we also plot the mean squared error of the networks on the different training sets (Fig. 9). This provides a more conventional (but harder to interpret) measure of performance compared to the slope depicted in Fig. 4. We again see that the mean squared error on the compositional generalization set is decreasing with increasing distance (Fig. 9a). Further, it is decreasing with increasing training set size (Fig. 9), though we note that the differences in the scales of the generalization set for different sets $\mathcal{W}$ renders it harder to directly to compare these values. In contrast, the slopes described in the main text are more easily comparable.

Figure: Figure 9: a, Mean squared error as a function of distance. b, Mean squared error as a function of training set size $p$ (different dots corresponding to interpolation versus extrapolation.
Refer to caption: x11.png

### D.2 Context dependence

#### D.2.1 General task definition

We consider inputs with three components, $(z_{\text{co}},z_{f1},z_{f2})$. We assume that $z_{\text{co}}\in C_{1}\cup C_{2}$, where $C_{1}$ is the set of possible contexts under which $z_{f1}$ is relevant and $C_{2}$ is the set of possible contexts under which $z_{f2}$ is relevant. We further assume that there are decision functions $d_{1}(z_{f1}),d_{2}(z_{f2})\in\mathbb{R}$. (For example, in the example in the main text, these function map three features to the first category (i.e. $y=-1$) and three features to the second category (i.e. $y=1$).) The target is then given by

$$ $y(z_{\text{co}},z_{f1},z_{f2})=\begin{cases}d_{1}(z_{f1})&\text{ if }z_{\text{ co}}\in C_{1},\\ d_{2}(z_{f2})&\text{ if }z_{\text{co}}\in C_{2}.\end{cases}$ (44) $$

Note that in the main text, we consider $C_{1}=\{1\}$, $C_{2}=\{2\}$, and six possible values for $z_{f1},z_{f2}$, where the decision function maps three onto $1$ and three onto $-1$.

#### D.2.2 Novel stimulus compositions are conjunction-wise additive

If the test set consists in novel combinations of stimuli, this is a conjunction-wise additive computation.
Namely, suppose that for all test inputs $(z_{\text{co}},z_{f1},z_{f2})$, the two features have never been observed in conjunction, but both $(z_{\text{co}},z_{f1})$ and $(z_{\text{co}},z_{f2})$ have been. (This includes the case considered in the main text.) In this case, we can define functions $f_{12}$ and $f_{13}$ to implement the appropriate mapping:

$$ $\displaystyle f_{12}(z_{\text{co}},z_{f1})$ $\displaystyle:=\begin{cases}d_{1}(z_{f1})&\text{ if }z_{\text{co}}\in C_{1},\\ 0&\text{ if }z_{\text{co}}\in C_{2},\end{cases}\quad f_{13}(z_{\text{co}},z_{f 2}):=\begin{cases}0&\text{ if }z_{\text{co}}\in C_{1},\\ d_{2}(z_{f2})&\text{ if }z_{\text{co}}\in C_{2},\end{cases}$ (45) $\displaystyle f(z_{\text{co}},z_{f1},z_{f2})$ $\displaystyle=f_{12}(z_{\text{co}},z_{f1})+f_{13}(z_{\text{co}},z_{f2}).$ (46) $$

#### D.2.3 Novel rule compositions are not conjunction-wise additive

We could also imagine an alternative generalization rule in a task where there are multiple components indicating the same context: $C_{1}=\{\text{co}_{1},\text{co}_{2}\}$ and $C_{2}=\{\text{co}_{3},\text{co}_{4}\}$. We then leave out certain features with certain contexts. For example, suppose we had never seen two values for $z_{f1}$ and $z_{f2}$ in conjunction with $z_{\text{co}}\in\{\text{co}_{2},\text{co}_{4}\}$. In principle, if the model understood that $z_{\text{co}}=\text{co}_{1},\text{co}_{2}$ (and $z_{\text{co}}=\text{co}_{3},\text{co}4$ resp.) signify the same context (i.e. learned to abstract the context from the context cue), it could generalize successfully as it had observed these features in conjunction with $z_{\text{co}}=\text{co}_{1},\text{co}_{3}$. However, the conjunction-wise additive mapping depends on having observed each context in conjunction with each feature and this task is therefore non-additive.

#### D.2.4 Coefficient groups

In Fig. 3d, we grouped the inferred coefficients into categories. We here explain these categories:

- •
Right conj.: This is the correct conjunction the model should use to solve the task, i.e. between $z_{\text{co}}=\text{co}_{1}$ and $z_{f1}$ and between $z_{\text{co}}=\text{co}_{2}$ and $z_{f2}$.
- •
Wrong conj.: This is the incorrect conjunction between context and feature, i.e. between $z_{\text{co}}=\text{co}_{1}$ and $z_{f2}$ and between $z_{\text{co}}=\text{co}_{2}$ and $z_{f1}$.
- •
Sensory feat.: This is any conjunction involving sensory features, i.e. $z_{f1},z_{f2},(z_{f1},z_{f2})$.
- •
Context only: This is the component $z_{\text{co}}$ by itself.
- •
Memorization: This is the full conjunction of all three components $(z_{\text{co}},z_{f1},z_{f2})$.

We then compute the average absolute magnitude within each of these groups in order to determine their overall relevance to model behavior.

#### D.2.5 Feature-learning ReLU networks

We find that feature-learning ReLU networks generalize consistently on CD-1 anREGULARIZATIONd CD-2 but not CD-3. They are also perfectly conjunction-wise additive and fail due to a context shortcut (Fig. 10).

Figure: Figure 10: Inferred values for different conjunctive groups on context dependence.
Refer to caption: x12.png

#### D.2.6 Vision networks

We additionally analyzed ConvNets for different distances between the digits. We found that convolutional neural networks trained on MNIST successfully generalized on CD-1 and CD-2, but not CD-3 (Fig. 11). For smaller distances between digits, the models tended to generalize worse on CD-1 and CD-2 and gradually reverted to chance accuracy (i.e. 0.5) for CD-3. Further, the networks were generally highly additive ($R^{2}>0.95$), but became worse for lower distance (Fig. 11b). Finally, across all distances, they had a high magnitude associated with the context cue, though this magnitude decreased for small distances — consistent with the accuracy of the network increasing from below chance to chance level (Fig. 11c).

Figure: Figure 11: Performance of convolutional neural networks trained on an MNIST version of context dependence. For different distances and training sets, we plot a, the accuracy on different splits, b, the additivity of the networks, and c, the magnitude of the different inferred coefficients.
Refer to caption: x13.png

### D.3 Invariance and partial exposure

We consider invariance and partial exposure as simple case studies for the memorization leak and shortcut bias. In both cases, the input consists of two components and the mapping only depends on the first (Fig. 12a). In the invariance case, we don’t see the second component vary at all, in the partial exposure case, we see one instance of the second component. Note that the partial exposure task has previously been studied in the context of network generalization (Dasgupta et al., ; Chan et al., ).

To understand the impact of different representational saliences, we consider the generalization margin $m:=y\hat{y}$ on the test set, where $y$ is the ground-truth label and $\hat{y}$ is the model’s estimate. Because we consider support vector machines, the margin on the training set is one; a smaller margin on the test set indicates worse performance. We determined a mathematical formula for the margins as a function of $S(1;2)$. Below we first describe its implications and then how we derived this.

##### Invariance suffers from a memorization leak.

On invariance, we find that the model’s test margin is expressed as
$m=\tfrac{S(1;2)}{1-S(1;2)}$.
This means that for a fully compositional representation ($S(1;2)=0.5$), its training and test margins are both one. However, as $S(1;2)$ decreases, the model increasingly memorizes the training set, resulting in a decreased margin (Fig. 12b).

##### Shortcut distortion.

On the partial exposure task, if the model used item 1 to solve the task, it would get two out of three training examples correct and could memorize the last data point. This is a statistical shortcut and we find that norm minimization (just as for context dependence) ends up partially relying on this strategy as this decreases the $\ell_{2}$-norm of the readout weights. As a result, the test margin for the partial exposure task decreases even more strongly as a function of $S(1;2)$: $m=\tfrac{2S(1;2)^{2}}{1-2S(1;2)^{2}}$ (where we assume that the similarity between identical trials is one and the similarity between distinct trials is zero) (Fig. 12b).

Figure: Figure 12: a, Schema for invariance and partial exposure. b, Generalization margin for the two tasks.
Refer to caption: x14.png

##### Derivations.

We analytically compute the kernel models’ test set prediction on the invariance task. The training set is given by $\{(-1,-1),(-1,1)\}$ and its kernel is therefore

$$ $K=\begin{pmatrix}\kappa_{2}&\kappa_{1}\\ \kappa_{1}&\kappa_{2}\end{pmatrix},$ (47) $$

where $\kappa_{2}$ is the similarity between identical trials and $\kappa_{1}$ is the similarity between overlapping trials.
Hence, the dual coefficients are given by

$$ $a=K^{-1}\begin{pmatrix}1\\ -1\end{pmatrix}=\frac{1}{\kappa_{2}^{2}-\kappa_{1}^{2}}\begin{pmatrix}\kappa_{ 2}&-\kappa_{1}\\ -\kappa_{1}&\kappa_{2}\end{pmatrix}\begin{pmatrix}1\\ -1\end{pmatrix}=\frac{1}{\kappa_{2}^{2}-\kappa_{1}^{2}}\begin{pmatrix}\kappa_{ 2}+\kappa_{1}\\ -(\kappa_{2}+\kappa_{1})\end{pmatrix}.$ (48) $$

The test set is given by $\{(1,-1),(1,1)\}$ and its kernel with respect to the training set is therefore

$$ $\tilde{K}=\begin{pmatrix}\kappa_{1}&\kappa_{0}\\ \kappa_{0}&\kappa_{1}\end{pmatrix},$ (49) $$

where $\kappa_{0}$ is the similarity between distinct trials. Hence the test set predictions are given by

$$ $\hat{y}=\tilde{K}a=\frac{1}{\kappa_{2}^{2}-\kappa_{1}^{2}}\begin{pmatrix}( \kappa_{2}+\kappa_{1})(\kappa_{1}-\kappa_{0})\\ -(\kappa_{2}+\kappa_{1})(\kappa_{1}-\kappa_{0}).\end{pmatrix}$ (50) $$

As the ground truth labels are $y=\{1,-1\}$, the margin $m=y\hat{y}$ is identical for both test set points:

$$ $m=\frac{(\kappa_{2}+\kappa_{1})(\kappa_{1}-\kappa_{0})}{\kappa_{2}^{2}-\kappa_ {1}^{2}}=\frac{\kappa_{1}-\kappa_{0}}{\kappa_{2}-\kappa_{1}}=\frac{(\kappa_{2} -\kappa_{0})S(1;2)}{(\kappa_{2}-\kappa_{0})-(\kappa_{1}-\kappa_{0})}=\frac{S(1 ;2)}{1-S(1;2)}.$ (51) $$

For partial exposure, the training set is given by $\{(-1,-1),(-1,1),(1,-1)\}$ and its kernel is therefore

$$ $K=\begin{pmatrix}\kappa_{2}&\kappa_{1}&\kappa_{1}\\ \kappa_{1}&\kappa_{2}&\kappa_{0}\\ \kappa_{1}&\kappa_{0}&\kappa_{2}\end{pmatrix}.$ (52) $$

The test set is given by $\{(1,1)\}$ and the test set kernel is therefore

$$ $\tilde{K}=\begin{pmatrix}\kappa_{0}&\kappa_{1}&\kappa_{1}\end{pmatrix}$ (53) $$

The margin is therefore given by

$$ $m=y\hat{y}=-\hat{y}=-\tilde{K}K^{-1}\begin{pmatrix}1\\ -1\\ 1\end{pmatrix}.$ (54) $$

We solve this equation for the special case where $\kappa_{0}=0$ and $\kappa_{1}=1$ using Mathematica and find that

$$ $m=\frac{2S(1;2)^{2}}{1-2S(1;2)^{2}}.$ (55) $$

### D.4 Other mathematical operations

We could consider mathematical operations other than addition as well, considering unobserved assigned values $v_{1}(z_{1})$ and $v_{2}(z_{2})$ together with some composition function $C(v_{1}(z_{1}),v_{2}(z_{2}))$. This task will only be additive if the composition function is additive (e.g. if it is subtraction). If it is, e.g. multiplication, division, or exponentiation, the task will be non-additive.

### D.5 Logical operations

In this task, inputs with two components are presented. Each component $z_{c}$ has an unobserved truth value $T(z_{c})$ associated with it and the target is some logical operation over these two truth values, for example AND: $T(z_{1})\wedge T(z_{2})$. After inferring the truth value of each component, the model could generalize towards novel item combinations. As long as the logical operation is additive (e.g. AND, OR, NEITHER, $\dotsc$), this is an additive task. If the logical operation is non-additive (e.g. XOR), this would be a non-additive task. Indeed, the XOR case is structurally equivalent to the transitive equivalence task.

### D.6 Transitive ordering

Transitive ordering is a popular task in cognitive science (often called transitive inference, (McGonigle & Chalmers, )). Here the subject is presented with two items $z_{1}$, $z_{2}$ drawn from an unobserved hierarchy $>$. It should then categorize whether $z_{1}>z_{2}$ or $z_{2}>z_{1}$. Crucially, this task can be solved by assigning a rank $r(z_{c})$ to each item and computing the response as $f(z)=r(z_{1})-r(z_{2})$ (Lippl et al., ). It is therefore additive, in contrast to transitive equivalence. This is also the case if we assume that there are multiple such hierarchies (e.g. $a_{1}>\dotsc,a_{5}$ and $b_{1}>\dotsc,b_{5}$). In this case, the model would generalize to comparisons between these different hierarchies as well.

## Appendix E A feature-learning mechanism for non-additive compositional generalization

Figure: Figure 13: Feature learning enables generalization on transitive equivalence. a, Learning curves in the lazy and rich regime. b, The weights of the network in the subspace corresponding to one underlying XOR-task. c, Weights for the same unit are plotted against each other and colored by whether they correspond to equivalent items (purple) or non-equivalent items (green). d, Accuracy of a ConvNet trained on an MNIST version of transitive equivalence.
Refer to caption: x15.png

We proved above that compositionally structured kernel models do not generalize on non-additive tasks, including transitive equivalence. To see if feature learning can overcome this limitation, we trained ReLU networks through backpropagation on transitive equivalence, using a disentangled and uncorrelated input. By varying the initial weight magnitude, we either trained these networks in the kernel/lazy regime or the feature-learning/rich regime. Notably, when trained on symbolic addition and context dependence, the rich networks were well-described by a conjunction-wise additive model (Figs. 7 and 10). On transitive equivalence, however, while the kernel-regime models failed to generalize (as predicted by our theory), the rich networks generalized correctly (Fig. 13a).

To explain why this is the case, we leveraged the insight that rich neural networks are biased to learning weights with a low overall $\ell_{2}$-norm (Lyu & Li (); Chizat & Bach (); cf. Vardi & Shamir ()). In particular, a one-hidden-layer ReLU network tends to learn a sparse set of features Savarese et al. (); Chizat & Bach ().
Transitive equivalence consists of multiple overlapping equality relations (e.g. $A=B\neq D=E$). Notably, ReLU networks such an XOR-type problem by specializing one unit to each conjunction (Brutzkus & Globerson (); Saxe et al. (); Xu et al. (); Fig. 13b).
Further, their sparse inductive bias incentivizes ReLU networks to use identical units for overlapping conjunctions (e.g. $(A,B),(A,C)$, and $(B,C)$). This causes the unit to generalize to unseen item combinations (e.g. $(A,C)$), enabling the network to generalize. Importantly, our theoretical argument is corroborated by empirical simulations: each network unit has identical weights for equivalent items (Fig. 13c).

Thus, rich networks’ capacity for abstraction gives rise to an additional compositional motif, allowing them to generalize on transitive equivalence. In particular, our findings highlight that transitive equivalence and transitive ordering are solved by fundamentally different network motifs.

To see whether large-scale neural networks can also benefit from this feature-learning mechanism, we trained ConvNets on an MNIST version of transitive equivalence. The networks were trained for 150 epochs on 20,000 samples. We found that if the digits were presented with a distance of zero, the network did not generalize compositionally at all. However, with increasing distance, the network started to improve its compositional generalization (Fig. 13d), demonstrating that a convolutional network can benefit from this rich compositional motif.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: - Line 262 states that "kernel models cannot solve any task that cannot be expressed in a conjunction-wise additive terms" - can you explain which tasks cannot be phrased in this way? In the worst case, the full conjunction can express any non-linear relationship, no?

- Line 269: why would the term f_{12}(z) fall away on the test set? I don't see how this should happen.

- How can a compositionally structured kernel model learn arbitrary training data, as is implied by section 4.3?

- Please add all the details on your empirical evaluation.

- In the related work, you state that Wiedemer et al. and Lachapelle et al. is restricted to linear networks, but you probably mean linear interactions between the components.

- Regarding the conjunction-wise additive computation: Why is the result surprising? In line 464 it states that "neural networks tend to implement conjunction-wise additive computations - at least when trained on conjunction-wise additive tasks". It would be quite surprising if it wouldn't implement that, no?

My scores currently reflect that the contributions of the paper are very difficult to assess and that the claims are way too broad (at least that's my current understanding). I can see interesting aspects and would like to encourage the authors to outline and state their contributions very clearly and without overclaiming. Understanding generalisation in machine learning is hard, so even some understanding on random-weights models is definitely interesting.
soundness: 2
strengths: The work tries to establish a stronger theory of compositional generalization in kernel and neural network models, addressing a crucial white spot in our understanding of statistical machine learning models. It also takes on an original angle to the problem by studying compositionality in the kernel limit, and I appreciate the empirical evaluation and comparison w.r.t. to deep neural networks.
summary: This paper studies compositional generalization from the perspective of kernel theory, showing that they are constrained to adding up values assigned to each combination seen during training. This result demonstrates a fundamental restriction in the generalisation capabilities of kernel models. The theory is validated empirically and shows, that the theory also captures certain behaviors of deep neural networks trained on compositional tasks.
weaknesses: - There is a wide gap between the claims of the paper and what is actually shown and proved. In particular, the theory only considers kernel models with random weights networks as feature extractors. In this limit the intermediate representation is compositionally structured (assuming the input is as well). But that doesn't necessarily extend to other kernels as implied by the abstract, which doesn't mention this limitation once.

- Also, while the work tries hard to make a connection to disentangled networks and thus establish an empirical relevance (which I generally welcome), the paper very carefully states that "This highlights fundamental computational restrictions on [...] pretrained models with disentangled representations that are fine-tuned in the kernel regime and infinite-width neural networks". For one, that's overly broad because even if a DNN is trained on disentangling the representation, there is no guarantee it is disentangled outside of the training data (in contrast to what is considered in the theoretical results). Second, this only applies if also the input is already compositional, rendering the statement mostly irrelevant for any practical application (e.g., in vision or language you don't have a compositional input to start with).

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

- There are pretty much no details on the empirical experiments with deep neural networks (both in the main text and the appendix). That part is thus almost impossible to evaluate. However, if my assumptions are correct, then the DNNs are trained in extremely simplistic settings that resemble nothing even close to what the networks are actually used for in practice (despite the use of MNIST or CIFAR images). Hence, claiming that the theory can explain the empirical behavior of DNNs is misleading.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: # Questions
- I'm not sure Wiedemer et al. (2023b) is characterized correctly as requiring a network that is constrained to be linear/additive. If I recall correctly, this paper allowed for arbitrary combinations of components. If so, a more detailed comparison of the assumptions in that work would be helpful to assess the new insights from this work.
- 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?
- §5.1 / §B: Even after reading these sections, it is unclear to me how the representational salience is computed in practice. Could you walk me through an example with a batch of training points?
- §5.1 / Fig. 2: Do you have any intuition where the difference between nonlinearities is coming from?
- §6: Am I correct in assuming all models are randomly initialized and not trained? This is not entirely clear from the text. Also, what specific model architectures were used, and how are they initialized? What are the training settings for the linear readout? 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.

# Minor suggestions
- LL99: Why call a combination of components a "conjunction", and not the more obvious "composition"?
- Fig. 1c: It was not immediately clear which side of the training set line is the training/test set
- LL256: "The readout weight ..." is unclear, is there a word missing? When will it change?
- L269: should be "test set"
- LL317: reusing $c$ here as a number of components is slightly confusing when $c$ was used above as a component index. I recommend using $k$ or $n$ instead
- LL354: What is $\mathcal W$ here? It has not been introduced before
soundness: 4
strengths: This paper presents a comprehensive study of compositional generalization. While the setting is restricted to fixed, disentangled representations (which, in practice, are not guaranteed to be recovered by the model), it succeeds in abstracting compositional generalization to encompass many specific problem formulations. The focus on kernel methods allows the authors to draw insightful conclusions about the limits of compositional generalization in terms of the operations that can be learned, which are entirely novel to the best of my knowledge. It is nice to see that the biases predicted by the theory can be demonstrated on real (if toyish) datasets.
summary: This paper considers the question, "Given a compositional (i.e., disentangled) representation, under what circumstances can kernel models (e.g., a linear readout trained with SGD) generalize compositionally?" The usefulness of disentangled representation for compositional generalization has been debated in the literature, but generally from an empirical angle or specific settings (e.g., object-centric learning). The authors opt to study the problem theoretically from the perspective of kernel models. This approach leads to a reasonably general framework that highlights important limitations: The type of computation that can be generalized is restricted to simple additive combinations of components, what the authors call "conjunction-wise additive". Even within this class of tasks, the authors go on to show that a kernel model will often not generalize perfectly, as it is biased to consider (spurious) interactions between all components or fall for spurious shortcuts.
weaknesses: 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).

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?

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: - In Figure-1b, why [-2]+[1]=1?
- The paper is a bit abstract for me to understand in depth. Especially, I cannot link the provided theory to practical applications, although section 6 indeed provides some results about deep neural networks and common datasets. I think the presentation of the paper is generally good: in the first several sections, we learn how the compositional generalization task and the kernel model studied in this paper are defined. We also learned the salience score is the main metric for tracking different types of features (e.g., how many ground truth features that this learned feature depends on). With this measurement, we know from proposition 5.1 that the later part of the network prefers using those higher-order features, which match our intuitions well. Then, we learn that memorization leak, which could be captured by those higher-order features, hinders the model’s generalization. After that, I began to feel confused: how could we link the results in Figure 4 to the theory provided in the previous part? I think a more detailed analysis of how results in section 6 are correlated to different parts of the theory (e.g., which proposition, which claim, etc.) would make the paper clearer.
soundness: 3
strengths: The paper studies an important question that might be overlooked by many related works in compositional generalization, i.e., when perfect disentangled representations are given, what types of downstream tasks are solvable (or non-solvable) in kernel methods? The paper theoretically analyzes this problem and verifies its theory using different experiments.
summary: The paper theoretically analyzes how the model can generalize downstream tasks when the ground-truth disentangled representations are achievable. The authors prove that different models can generalize well on component-wise additivity tasks. Meanwhile, the models are limited in learning tasks involving conjunction-wise additivity, which makes them hard to generalize. Based on the analysis, the authors figured out two important failure modes, i.e., memorization leakage and shortcut bias. The former is because the model learns too many non-atom features from the training set while the latter is caused by the hidden spurious correlation in the training data. Finally, the authors empirically verify their theory using the behavior of some deep neural network structures. Although the paper studies a very important and novel problem about compositional generalization ability, I find it is a struggle for me to understand the paper in depth. However, I do believe the assumption that perfect disentangled representations are achievable harms the applicability of the paper’s results. So I tend to give a negative evaluation.
weaknesses: ### Weakness:

My main concern in this part is about the gap between theory (with many assumptions) and practical systems. Although the paper proposes several experimental results to support the theory, the following concerns forbid me from giving a positive evaluation of this paper:

- The gap between kernel method assumption and deep neural networks. Analyzing the model’s behavior using a simplified model is acceptable, but I expect more results to show that the gap between theory and practical models is negligible. For example, will the deep network on real image input also have a salience score similar to Figure 2? Can we design an ablation study that directly manipulates the weights of overlapping features, e.g. $f_{12}$, and see its influence on the generalization ability? Although the answer might or might not support the claims, knowing the limits of the proposed theory is beneficial.
- 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.
- In section 6, the authors replace the one-hot input with real images, which is good. However, the task is still not so practical. Considering the experiments on more common compositional generalization problems, e.g., the dsprite dataset in [1],  can make the claim stronger.
- The paper has potential and the author did a good job of formalizing an important problem. However, the connection between the experimental part and the theory is still not quite clear. I think adding a high-level summary or conceptual diagram that ties together the main theoretical and empirical contributions of the paper would make it easier to understand the whole story of the paper.

[1] Xu, Zhenlin, Marc Niethammer, and Colin A. Raffel. "Compositional generalization in unsupervised compositional representation learning: A study on disentanglement and emergent language." Advances in Neural Information Processing Systems 35 (2022): 25074-25087.

---

confidence: 4
contribution: 3
initial_rating: 10
presentation: 3
questions: 1. In Section 3.1 first paragraph, the definition of the disentangled representation is a bit unclear.
    1. Does each component have a finite set of possible values it can take on (e.g., multiple values for the “color” component)?
    2. Are the different possible values within a component orthogonal (e.g., vectors for different colours), or are only the vectors across components orthogonal (e.g., colour and shape representations existing in different subspaces)?
    3. Is $C$ constant across samples? In other words, do the individual components (like color and shape) always apply to each possible input?
2. In Section 5 and subsections within, why is the approach of looking at the kernel and representational salience referred to as “modular”?
3. Section 5.2 refers to a set $\mathcal{W}$, but I can’t seem to find where the meaning of this variable was defined earlier on in the paper. Apologies if I’ve missed it, but what is $\mathcal{W}$?
4. See above weaknesses for other questions.
soundness: 4
strengths: 1. The reason for looking at kernel models is very clearly articulated and motivated.
2. The theory is supplemented with good empirical experiments that show it applies in deep neural networks, even though it was developed with kernel models (with a nice method for deep learn-afying the main tasks used in the kernel models sections).
3. Contributions and advantages over prior work are very clear (e.g., no assumptions about modularity or linear/additive combinations in the downstream model).
4. The practical consequences of the main finding, laid out in Section 4.3, are clearly articulated with several simple examples.
5. The work helps guide the design of more difficult compositional generalization benchmarks that cannot be solved by kernel models (or neural networks trained in the kernel regime).
6. Figures are clear and aesthetic, both when illustrating the framework/tasks and when presenting results.
    1. One exception I recommend fixing is Figure 3d, where the borders of the bar are too thick and obscure the colors of the bars.
summary: This paper considers under what circumstances a kernel model learning on top of a disentangled representation can generalize compositionally. The main finding is that these models can generalize compositionally if the task is what the authors call conjunction-wise additive with respect to the disentangled features. Although the theory is developed using kernel models, most of the results generalize more or less to deep neural networks, which in some training regimes are related to kernel models. Overall I really liked this paper. The results are interesting and novel, the paper is for the most part clear and well-written, and the results help push the field forward in terms of designing models which are more likely to generalize compositionally.
weaknesses: 1. 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 (e.g., Tensor product representations, block-wise disentanglement, etc.), and disentanglement is likely just one particular special case of compositional representations. Ideally I would want to see the whole paper rewritten in terms of disentanglement instead of compositionality (disentangled representations, generalization from disentangled representations). I understand that the authors might not want to go this far, so in this case 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.
2. 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 $z$ 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”).
3. 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. Below are some other stray comments about confusions during the introduction of kernel models in your setup.
    1. At times $x$ is used and at other times $z$ is used. Are these the same? Is it a typo in Section 3.2 for instance where you write $f_w(x)$ as opposed to $f_w(z)$?
    2. In equation (1), where do the dual coefficients come from? Are they determined from $w$ and $\phi$ in some way?
    3. Are you making a distinction between “input” and “representation”? Which of these is disentangled in your theory, $z$ or $\phi(z)$? At times, especially earlier on in the paper like in Section 2, it is not obvious.
4. Section 3.1 says that the target $y$ is given by an arbitrary function of $z$ and that your framework is agnostic to this function. This is a bit misleading, as the core contribution of the work is to formalize what downstream functions kernel models can compositionally generalize to w.r.t. some observed disentangled features.
5. Section 4.2 defines conjuction-wise additive functions, but it is quite difficult to quickly parse the math and get intuition for it. Intuition for the proof is given, but not intuition for what a conjunction-wise additive function is. This is a shame because after spending enough time to digest the definition, it is intuitively quite simple. Please try and provide more helpful intuition, as well as an example of a conjunction-wise additive function and how it differs from an additive function.
6. The theoretical and empirical results in Section 5.1 seem to be of significant consequence. Specifically, Proposition 5.1 seems to suggest that very deep neural networks in the kernel regime are unlikely to generalize compositionally as they only represent the full conjunction of disentangled features (if I understand correctly, another way of stating this is that they memorize the training data). While this is explored further in the subsequent subsections, the immediate consequences of Proposition 5.1 are only unpacked in a single sentence following the proposition. I think this result should be emphasized more, and Section 5.1 should do a better job of foreshadowing/leading the results in subsequence subsections.
    1. Additionally, I don’t think it will be completely obvious to everyone why assigning weight to the full conjunction function amounts to memorization. Maybe it can be more clearly articulated (e.g., the full conjunction is a function of combinations of features that can amount to something like a lookup table, without any ability to generalize).
7. Small point: I recommend citing Schug 2024 http://arxiv.org/abs/2312.15001 at the same place as where you cite Wiedemer 2023.

Meta-review: (a) Summary

This paper investigates compositional generalization(CG) in kernel models and deep neural networks with disentangled input. Theoretically, it presents the constraints for kernel models to solve a range of compositional tasks (conjunction-wise additive tasks). Empirically, it demonstrates that the theory captures the CG behavior of DNN models on the proposed compositional tasks.


(b) Strengths
+ This paper studies CG from theoretical and kernel angle. It succeeds in abstracting compositional generalization to encompass many specific problem formulations.
+ It conducts empirical evaluation and comparison of DNNs to support the theoretical claims.
+ It draws insightful conclusions about the limits of compositional generalization in terms of the operations that can be learned.
+ The biases predicted by the theory can be demonstrated on real  datasets.

(c) Weaknesses
- The assumption that perfect disentangled representations are achievable harms the applicability of the paper’s results.
- There is a gap between the simple models the theory describes and actual DNNs.
- The paper is too dense to read and the presentation could be improved.
are missing.

(d) decision

The paper presents theoretically-sound contributions to the field of compositional representations and generalization. While there is a gap between the simple models the theory describes and actual DNNs, this is to be expected given the complexity of real DNNs. Considering it's worth to share the theory paper in the community to inspire discussion, I recommend accept.

Decision: Accept (Poster)