When does compositional structure yield compositional generalization? A kernel theory.
Authors: Samuel Lippl
Kim Stachenfeld
Venue: ICLR 2025 Poster (2025)
Keywords: compositional generalization
rule learning
kernel regression
kernel models
relational reasoning
memorization
shortcuts
dataset statistics
norm minimization
implicit regularization
disentanglement
Primary area: learning theory
TL;DR: We present a theory of compositional generalization in kernel models with fixed representations and validate it in deep neural networks.

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 support this ability; however, the conditions under which they are sufficient for the emergence of compositional generalization remain unclear. To address this gap, we present a theory of compositional generalization in kernel models with fixed, compositionally structured representations. This provides a tractable framework for characterizing the impact of training data statistics on generalization. We find that these models are limited to functions that assign values to each combination of components seen during training, and then sum up these values ("conjunction-wise additivity"). This imposes fundamental restrictions on the set of tasks compositionally structured kernel models can learn, in particular preventing them from transitively generalizing equivalence relations. Even for compositional tasks that they can learn in principle, we identify novel failure modes in compositional generalization (memorization leak and shortcut bias) that arise from biases in the training data. 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 examines 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.

Published as a conference paper at ICLR 2025
WHEN DOES COMPOSITIONAL STRUCTURE YIELD COM- POSITIONAL GENERALIZATION? A KERNEL THEORY.
Samuel Lippl
Kimberly Stachenfeld
Center for Theoretical Neuroscience
Google DeepMindd and Center for Theoretical Neuroscience Columbia University
Columbia University
New York, NY, USA
samuel 14 1ippllll columbia. edu
New York, NY, USA
ABSTRACT
Compositional generalization (the ability to respond correctly to novel combina- tions of familiar components) is thought to be cornerstone of intelligent behavior. Compositionally structured (c.g. disentangled) representations support this abil- ity; however, the conditions under which they are sufficient for the emergence of compositional generalization remain unclear. To address this gap, we present a theory of compositional generalization in kernel models with fixed, compositionally structured representations. This provides a tractable framework for characterizing the impact of training data statistics on generalization. We find that these models are limited to functions that assign values to each combination of components additiv-
seen during training. and then sum up these values ("conjunction-wee ity"). This imposes fundamental restrictions on the set of tasks compositionally structured kernel models can learn, in particular preventing them from transitively generalizing equivalence relations. Even for compositional tasks that they can learn in principle, we identify novel failure modes in compositional generalization (memorization leak and shortcut bias) that arise from biases in the training data. Finally, we empirically validate our theory, showing that 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 examines 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.
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 to cope with unfamiliar situations and imagine things that do not yet exist (Fig. [T] (Lake et al. 2017] Franklladd & Greene (F17)laaankann
2020). Understanding the basis of compositional generalization humans and animals, and building into machine learning models, is a long-standing and historically vexing problem (Fodor & Pylyshyn 1988 Battaglia et al. 2018 Lake & Baroni 2018 Lepori al. 2023). While a wide range of
studies have investigated the conditions under which compositionally structured (i.e. "disentangled") representations can be learned (Hinton al.) 2011; Higgins al., 2017; Trääbble al., 202T
Whittington et al. 2023 Ren et 2023). it remains unclear when learning these representations is actually useful to a downstream neural network. Some work suggests that disentangled representations improve compositional generalization (Esmacili et al. 2019 van Steenkiste al. 2019). Other studies challenge this view (Locatello et al.) [019]] Schott et al. 2022). In general, a systematic understanding of the relationships among compositional tasks remains elusive (Hupkes et al. 2020).
To make progress on this question, we focus on standard statistical learning, a fundamental basis for generalization that affects almost any machine learning model. Generalization in statistical learning depends on the similarities between different inputs. In compositionally structured representations, inputs that have components in common (say, red circle and blue circle) similar each

---

Published as a conference paper at ICLR 2025
4, Compositional generalization
Compositionally structured
C, Example representations
Conjunction-WWse additivity
representations Detiniton 4.1
Propositoo 4.2
Theorem 4.3
Compertanay +
6-00 AUM
Mull-hht
Random
Test set
Familar conjunctions (ween during manng))
Shadiing
O
Liner nombinatin
Rep.
Banday zoglo
similiaity
111
see lap three
O
Shape
Color
Untamillar conjunctions seot durtng traniing) Not
O
Training
Test
structred
We consider inputs with several categorical components and study compositional generalization to novel combinations of components. b. We assume compositionally structured representations for which trials with the same number of overlaps have identical similarities. c, We find that a random weights neural network conserves compositional structure: if its input is compositionally structured then so is its output. d, We find that compositionally structured kernel models are constrained to adding up values for each conjunction seen during training ("conjunction- seiee additivity").
Figure 1: Overview of main theoretical findings (Section 4
other than inputs that do not (say, a red circle and blue square). As a result, the compositional structure of a task is reflected in its dataset statistics, influencing the model's generalization behavior.
To understand when and how statistical learning leads to successful compositional behavior, developed a theory for the behavior of kernel models on compositional tasks. Kernel models are an important class of statistical models that are able provide a simplified approximation to neural networks while maintaining analytical tractability Oakel et al., 2008 (009). For example, kernel models accurately describe the behavior of learning and fine-tuning in neural networks under certain conditions (Jacot et al. [018 Malladi et al. (2023). More broadly, they provide tractable framework for characterizing the impact of dataset statistics on generalization (Canatar al. 2021a b).
Despite their broad relevance and relative simplicity, it has remained unclear how even kernel models generalize on compositional tasks (though see /Abbe et al. [2033] Lippl et al.) 2024 see Section 2}. To address this gap, we present theory of compositional generalization in kernel models. We define a general class of "compositionally structured representations" (Fig. [T)) and a general family of compositional tasks with constraints the input-output mapping (ensuring broad applicability of our theory). We then theoretically characterize the compositional behavior of compositionally structured kernel models, and go beyond kernel models empirically validate our theory in several relevant deep neural network architectures. Our specific contributions are as follows:
In Section we show that compositionally structured kernel models are constrained to summing up values implicitly assigned to each component or combination of components seen during training (Fig. D. We call such computations "ccnjuunctin-- wise additive."
In Section 5 then characterize how representational geometry determines whether ker- nel models will generalize successfully on conjunction-wiss additive compositional tasks, highlighting important failure modes (memorization leak and shortcut bias). This demon- strates that disentangled representations are not sufficient for downstream compositional generalization (even conjunction-wer 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-wee wise additive tasks.
Overall, take step towards general theory of compositional generalization. Our theory systematically clarifies the compositional generalization behavior of deep networks and lays foundation for the design of new learning mechanisms that overcome their limitations.
RELATED WORK
Compositional generalization. Compositionality is an important theme in both human and machine
cognition, including visual reasoning (Lake et al. 2013 2015) Johnson et al. [0017] Schwartenbeec et al. 2023), language production (Hupkes al. 2020). and rule learning (Ito et al. 2022 Abdool et al.
2

---

Published as a conference paper at ICLR 2025
While recent breakthroughs have led to massive improvements in models' compositional capacities, these models can still fail spectacularly (Srivastava et al., 2023 Lewis et al. 2023: West
2023
2023). Attempts improve compositional generalization often leverage meta-learming (Mitchell
et al. 2021 Wu et al. 2023 Lake & Baroni 2023) or modular architectures (Andreas et al. (017)
Constraining network's is compositional function (e.g. to adding up value for each component)
can guarantee modular specialization and compositional generalization (Lachapelle et al. 2023
Wiedemer et al. 2023a by Schug et al., 2024). 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., 2019
Mittal et al. 2022 Jarvis et al. 2023
Kernel regime. When using gradient descent, ridge regression, or similar learning algorithms to train the readout weights of a model [L) w² Φ(r), the behavior of that model can be described terms of the kernel K x²) "(x)" o(a') induced by Φ(x) (Schölkopf) 2000). Notably, when trained on dataset {Zz; M4) 34) such "kernel models" can be written in dual form as fa( = Ei= a; (z, xy), for inferred dual coefficients a E IR". Prior work has shown that neural networks with large initial weights or wide architectures are well approximated by kernel model ( ("kernel regime") (Jacot et al.) (0188). In contrast, the "feature-learning regime" (which can be brought forth, for example, by small initial weights small width) yields more substantial changes in neural networks' internal representations (Chizat et al. 2019).
Norm minimization. Gradient descent, ridge regression, and neural networks in the kernel regime learn the readout weights that describe the training data with minimal 4n-norm (Soudry et al. 2018 Gunasekar et al. 2018 Ji al., 2020).. Norm minimization is a standard theoretical framework for analyzing how representational geometry and dataset statistics influence generalization (Canatar el al.. 2021a bj 2023) and we here apply the compositional task setting. This is similar to Lippl et al. (2024) who characterize model behavior on a specific compositional task (transitive ordering) and Abbe et al. (202) 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 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 generalizable rule (Zhang et al. 2020 Dasgupta et al. 2022). This may improve generalization long-taile taig-tailed data (Feldman 2020). but often impairs out of distribbuiiinionn performance (Elangovan et al., 2021). We find that models partially memorize their training data even when they extract the correct rule. Jarvis et al. (2023) analyze 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 al. 2020 Nagarajan et al., (021). This substantially impacts their performance out of distribution, where those correlations may not hold (Geirhos et al.) 2020). We theoretically analyze how shorteut biases impact compositional generalization.
3
MODEL AND TASK SETUP
3.1 TASK SPACE
(zc) where each component 2, E Z, is drawn from discrete, finite set of possible components. For example, could be a "multi-hor" concatenation of one-hot representations of all components [p). We make a specific assumption about how the trial-by-trial similarity of input representations x relates to the underlying components (Fig. [b):
We consider an input x representing a set of underlying components 2
Definition 3.1. A representation z is "compositionally structured" iff its kernel K(x, x'),,')=0)) = =Ta only depends on the number of components that are identical between z and 2', where 2 and 2' are the components represented by x and x' respectively.
In particular, the multi-hot representation described above is compositionally structured, but we will see below that this concept captures a richer set of representations as well. The target, y E TR, is given
by an arbitrary function of 2, ensuring that our framework is agnostic to the underlying compositional structure. After training models on certain combinations of components Zuaan Z II Ze, we assess generalization on all other combinations Zrest : Z Zuainn
3

---

Published as a conference paper at ICLR 2025
a, Symbolic addition
b, Context dependence
c, Transitive equivalence
d, Compositional
Extrapolation
task space
e.g. [2)]-
[4]
Target
Training sot
Split
Test
Train
[-4]
Cat. 1
CaL 2
CD-3
CD-1
CD-2
Target
Eq.
Split
Train
Test
Symbokic
Conjenctin-wise
addliive tasks
Transtive
dependence
Contest
Item 2
[4]
Interpelation
Both
Context
Context
operations
ANDNG
eroosure
Fartal
Feat
Ilem
Non-adoltive tasks
[-4)
Symbolic
Maxification
mudipiaation
context
[-4]
Item
[4][-4]
[4]
Irain
Feat. 1
ABCDEF Item
eouisalence
Trans
dependencs
Figure 2: The compositional task space. a, Example training sets for symbolic addition. The grid represents pairs of components with associated values -4,...,4 4. rows and columns of this grid. b, Context dependence. In context feat. determines the category; in context 2, feat. 2 determines the category. The training sets leave out subsets of the lower right orthant. c, Transitive equivalence:
The training set consists of certain
items are split up into two equivalence classes (e.g. A,B,C and D.E,F) and generalization requires transitive inference over equivalence classes (e.g. A = B and = C implies A = C). d, Our theory partitions the task space into conjunction-wise additive (which can be solved by kernel models) and non-additive tasks (which cannot).
Our theory characterizes constraints on model behavior for arbitrary tasks within this family, regard- less of the ground-truth input-output mapping. Below we describe three example tasks 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. Appendix D
we describe additional tasks captured by our theory (Fig. 2
Symbolic addition. Many tasks involve inferring a magnitude associated with different underlying components (e.g. adding handwritten digits) (Lorenzi et al. 2021 Sheahan er al. 202T). We consider two components (21, 22) with hidden values 21 (21) and 2t2 (22). The target the sum of those values: y = U1 (21) + (22). After sufficient exposure to individual items in different combinations, an additive model could in principle generalize to novel combinations. We consider training sets consisting of entire rows and columns of the compositional dataset (Fig. [b), varying the number of rows and columns as well as whether generalization involves interpolation or also extrapolation.
Context dependence. The relevance of different stimuli often depends crucially on our current context (Bouton al., 1999 Taylor & Ivry) 2013: Parker & Hollister 2014 Ito al. (0022). We
consider a task with three imput components (Zeo 2f1, 2f2). The context (Zeo) has two possible values specifying whether 2 or 22 determine the response. Features have six possible values which are divided into two classes. If the model has learned this context dependence, it should generalize to novel feature combinations. We evaluate on the subset of data for which 2f1 indicates Cat. 2 and 2/2 indicates Cat. 1. In the most extreme generalization test (CD-3), we leave out the entire subset; in easier versions, we leave out combinations one or two features (CD-1, CD-2) (Fig. (
Transitive equivalence. Relational reasoning involves extending learned relations to new item combinations (Halford et al., 2010: Battaglia et al., 2018). Given an unobserved (and arbitrary) equivalence relation, the task here is to determine whether two presented items (21,22) equivalent. The model should generalize to novel item pairs using transitivity (A = B and C imply A == == C) (Fig. D This is important instance of relational cognition (often studied as "associative inference" in cognitive science (Schlichting & Preston 2015 Spalding et al. 2018)). Although prior work has found that kernel models often successfully generalize transitive ordered relation (A > B and B > C imply A > C. Lippl et al. 2024), the behavior of kernel models on equivalence relations has remained unclear.
3.2 MODELS
Our theory characterizes kernel models with a compositionally structured input x E Id that apply a transform ((x) E Rh and learn a linear readout, f=) := w o(x), using gradient descent with initial weights Wo = O. For ó, we consider neural network with random weights (in the infinite- width limit; see Appendix (A.3). Our setup captures, for example, the random feature model studied by Abbe al. (2023) and training via backpropagation in the kernel regime.
4

---

Published as a conference paper at ICLR 2025
4 KERNEL MODELS ARE CONJUNCTION-WISE ADDITIVE
Our primary theoretical contribution is to characterize the full range of compositional computations that can be implemented by kernel models with compositionally structured inputs. We find that even though these models can learn arbitrary training sets, their test set behavior is restricted to adding up values for each conjunction (combination of components) seen during training. We call this motif "conjunction-we wise additivity." Below, we formally state our finding and explain its implications.
4.1 RANDOM NETWORKS YIELD COMPOSITIONALLI STRUCTURED REPRESENTATIONS
We first note that linear readout of the multi-hot input constrains the model to adding up a value for each component ("component- wise additivity"): f(x) EenJe(ze), fe(ze). Although models of this class perfectly generalize component-we wise additive tasks, such symbolic addition, they incapable of even learning the training data (much less generalizing) on tasks that are not component additive. In particular, these models cannot learn context-dependent computations or equivalence relations - both fundamental instances of compositional reasoning.
The nonlinear transform ((x) can overcome this constraint: in particular, mulli--aaer nonlinear neural networks can learn arbitrary training data (in the infinite-widhy limit) (Horiik et al. 1989]
Cybenko 1989; Rigotti al., 2013). Normally, the wide range of possible network architectures makes it difficult to derive general statements about their representations, but in this case we can take advantage of the fact that Φ(x) will also be compositionally structured (Fig. [b):
Proposition 4.1. For random weights neural network with compositionally structured input in the infinite-width limit, σ(x) is also compositionally structured.
Proposition 4.1 holds because in the infinite-width width limit, the kernel of random weight neural networks depends only the input kernel (Cho & Saul 2009, see Appendix A.3) We now consider the constraints that compositional structure imposes on the models' generalization behavior.
4.2 COMPOSITIONALIE STRUCTURED KERNEL MODELS ARE CONJUNCTION- WISE ADDITIVE
We find that any kernel model with a compositionally structured representation constrained to be conjunction-wir wise additive. To formally state this finding, we define, for each z E 2, the set of conjunctions for which z overlaps with some element in the training set z" Ztrain
(min) = {J S (1....,C)(therr 2" zrain such that 2, 2e for all aelllc (I)
Theorem 4.2. For any kernel model f with a compositionally structured representation, we can find conjunction-wise functioos fa II
J Ze > IR, where J C (I,...,C}, such that for any input x E IRd representing components z Z,, the model response is given by
f(z) Jecomj(s Zumn fz(zz), 2J (ze)EEJ.
We prove the theorem in Appendix A.4 It implies that for given test input, kernel models add up a value for each component and partial conjunction seen during training (Fig. Dt). We call this computation "conjunction-wii srsie additive." In particular, for inputs with components, the model's behavior on the training set can be expressed as f(z) = fi (z1) (2)22)+++2+)))))) fi2(21, 22). Thus, f12(21, 22) enables the model learn arbitrary training data. However, a represents E Ziest, the training set does not contain any input with the conjunction (#1, 22) and the model is component-wise additive: fx) = (21) + fz(22). For inputs with more than two components, conjunction wise additive computation additionally encodes partial conjunctions seen during training, e.g., if 2mmin
contains the conjunction (21, 22). f(x) = (i + f2((2) fz(23) + f12(21,22)
4.3 CONJUNCTION-WISS WISE ADDITIVITY CONSTRAINS THE TASKS KERNEL MODELS CAN SOLVE
Theorem 4.2
implies that compositionally structured kernel models can only solve tasks that can be expressed in conjunction-wee wise additive terms. This highlights a fundamental computational restriction, partitioning the compositional task space into tasks that can and cannot be solved by kernel models
5

---

Published as a conference paper at ICLR 2025
(Fig. 21). Intriguingly, these restrictions are not caused by an architectural constraint, the model can learn arbitrary training data (at least with a nonlinear transformation Φ, see Section[31I) Rather, highlight restrictions on how models without any architectural constraints generalize /Zhang et al. 202T). We now spell out the consequences of the highlighted restrictions.
First, for inputs with two components, noted above that the model's behavior on the test set is component-wise additive. A consequence of this is that compositionally structured models 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 superficially similar task- can be solved by kernel model. This highlights the importance of formal perspective on compositional tasks.
More generally, to see whether kernel model can, in principle, generalize on task with more than two input components, we must 1) identify, for each E Ziest the conjunctions seen during training, Conj(z| ( and 2) determine whether the target can be written as conjunction- wise sum (Eq. (2).
For context dependence for example, for all Z we have seen the context-feature conjunctions 12 and 13, but not the feature-feature conjunction 23. As a result, model behavior on test trial x representing the components Rco: æf1, 2 can be written as ((x) fi(=c) + f2(211) + Ja(zy2) f12(2c0. 2)1) + fia (Zeo: 252). Importantly, this conjunction wise additive function can encode context (Zco: dependence, specifically with the following schema: f12 (22 2)1) encodes the target when the context
Aco indicates: z as relevant and is zero otherwise; f13(2 222) works in the opposite way. Thus, the model can, in principle, identify 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 certain task, and also how they solve it. It even tells us how to make a task non-additive: in Appendix E.2.3 we describe such a modification to context dependence that tests generalization 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.
What do our findings imply about compositional generalization in more general representations? In this section, we analyzed compositionally structured inputs, as we consider them the best-case scenario for compositional generalization. Accordingly, we expect that the limitations revealed by our theory are also relevant for kernel models with con-colpositionally structured representations. We present two pieces of preliminary evidence for this conjecture in the appendix: First, we theoretically prove that randomly sampled representations (that are only compositionally structured in expectation) also conjunction wise additive in expectation (Appendix AA.5). Second, we empirically investigate compositional generalization in disentangled representation learning models trained on the DSprites dataset (Locatello et al. 2019), finding that, when averaged across randomly sampled task instances, these models are also limited to conjunction-wis wise additive computations (Appendix ( These findings suggest that the generalization class we have highlighted in this section captures fundamental limitations of kernel models beyond our theoretical setting.
(A.5)
5 REPRESENTAAIONALL GEOMETRY STILL IMPACTS GENERALIZATINN 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-wis function. This depends on the model's 's representational geometry and the training data statistics. As noted in Section [ the behavior of kernel models depends on their representation ((x) only through the induced kernel K5(2, x'). In this section, we first investigate how different choices in network architecture influence its induced kernel (Section (.TI. Then, we characterize how this kernel impacts task performance on symbolic addition and context dependence (Section 5.2).
5.1 OVERLAP SALIENCE CHARACTERIZES COMPOSITIONAL REPRESENTATIIOAAL GEOMETRY
To characterize compositionally structured representations, we introduce a new metric: representa- tional salience. We formally define this metric in Appendix B.] Intuitively, for k 1,.... C, the salience S(k; C') measures the unique contribution of the subpopulation representing a conjunction of e components. Further, S(k; C') is normalized that all saliences sum up to one. For example,

---

Published as a conference paper at ICLR 2025
the multi-hot input only encodes single components and therefore S(1; CJ = 1/C and, for all l 1, S(k; C) = O. Note that the model can only use conjunctions whose salience is nonzero. For example, the multi-hot input is constrained to component wise sum (as all other saliences are zero).
S(k; C)) is computed from the representational similarities K5(2, x²) = <(x)) This metric is useful because unlike Ka (zr, x²), it makes immediately apparent how strongly different conjunctions are encoded (A (Appendix [B.2). Furthermore, it reduces the C++1 similarities characterizing the space of compositionally structured representations to C free parameters, removing the overall magnitude of the representation (by normalizing) and the baseline activity (by not considering the similarity between inputs with no overlap). This is because these parameters often have negligible impact on model behavior (Appendix B.3).
We now analyze how S(k; C') evolves over dif- ferent layers of a random network, using three components as an example (Fig. see Ap- pendix [B44] for other values of C). The input only represents individual components and so 3); and 3); are zero. As the network gets deeper, these saliences increase and (1; decreases. In particular, because S(3 > for all networks with at least one layer, the re- learn arbitrary train-
5(1:3)
S(2:3)
S(3:3)
Nonlinearity
Salience
0.2
Step fun.
0.5
ReLU
Leaky ReLU
Rect quad.
0.0
0.0
0.0
Gaussian
0
10
20
0
10 20
0 10 20
# Layers
sulting representations ing data (using the full conjunction). As depth increases, S(2; 3) eventually decreases again, whereas (3; 3) continues to increase.
Figure 3: Representational salience (for three input components) in random weight neural network with variable numbers of layers and nonlinearities.
In fact, we prove that for ReLU networks the limit of infinite depth, S(C; C) + 1 (Proposition B.2). Put differently, very deep networks exclusively encode the full conjunction. As a result, these models effectively implement look-up table, memorizing the training data without generalizing to novel combinations of components. In the next section, we find that even moderately conjunctive representation presents significant challenges to compositional generalization.
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 learn the weights with minimal εz-norm (see Section 2). We now characterize how this inductive bias influences compositional generalization. To characterize the full range of compositionally structured representations, we compute the behavior of the model directly using the kernel (see Appendix DD. Importantly, our analysis clarifies the behavior of all random weight neural networks, including those covered in the previous section.
Symbolic addition suffers from memorization leak. We first consider an example task (21, 22 e {[-4)...... [4]]: the training set consists of all trials containing a [0]. Fig. 22) and an example representation (5; 0.4). We find that though the model perfectly learns the training cases, it underestimates the test cases by proportional factor (Fig. Fb). To understand why, we consider the model's functional form on the training cases: f(x) = (1 f2(2) + fi2(2) (see Section 4p. Intuitively, f--nomm 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. f12(21, 22) * 0). This distorts the test set generalization, f(x) f1 + f2(22).
We call the tendency to use the full conjunction (and its detrimental effect on generalization) "memo- rization 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.1. Consider inputs 21, 22 E [ul]vve, V C E. with associated values v. We assume that the training set contains all pairs such that at least one component is 2 E [[w]]wew> W C V and that the average value both V and W is zero. Then, model behavior on the test set is given by
f((e1, [02])= = m(v + 02).
m
(p- 215(1:)
p-1(12)
[
We prove the proposition in Appendix E.I It implics that for this entire task family, model general-
ization is distorted by a proportional factor m (Fig. 4b). The formula implies that < 1 as long as
7

---

Published as a conference paper at ICLR 2025
5(1:2) 0:4. (0)
Prediction
Slope (m)
4
1/3
Generali-
Conj. type
Right conj.
ReLU
CD-3
zation on...
Wrong conj.
-4-
train
lest
all
CD-1,2
Sensory feat.
Context only
Full conj.
Rect. quad.
CD-2
CD-1
CD-3
0
0.5
none
0.5
Ground truth
S(1; 2)
S(1;3) 3)
Value
Figure 4: 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, W {0]). b. The slope of the test set as a function of S(1; and the training set size [W]. c, Generalization on context dependence as function of representational salience. Trajectories of networks with different nonlinearities are highlighted (color scale see Fig. 3). d. Coefficients of the different conjunction types for two example networks with three layers and different nonlinearities.
((1 < (i.e. as long as S(2: > 0). Further, m is smaller for lower S1; and smaller training set size p. (Note that W corresponds to the rows/columns making up the example training sets in Fig. 2b) Interestingly, these are the only two factors that influence m. In particular, even though 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: f2 fy-norm minimization tends to yield distributed weights and if the conjunctive population is represented, the model will generally end up partially relying on this conjunction. As shown above, this necessarily distorts generalization. This issue also arises in tasks that involve directly decoding specific components, popular task for evaluating disentangled representations (Locatello al. 2019 Schott al. 2022
(see Appendix E.3 for minimal example).
Context dependence suffers from shorteut bias. Next, we empirically analyzed model gener- alization 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 ((2 3) is high relative to S(1;3) 3) (Fig. 4p. dark green area). As a result, compositional generalization highly sensitive to the nonlinearity and depth of the network. contrast, for CD-2 and CD-1, 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. 4t). We found that unsuccessful models (e.g. the blue color in Fig. 4i) 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 of the training data. Models with high 3)1 (context) and S(; 3) (full conjunction) exploit this 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 ) This explains why only very low 5(2; 3) yields failure 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 statistical shortcut. This highlights that for compositional tasks with strong spurious correlations, model behavior will be highly sensitive to architectural hyperparameters affecting the representational geometry such as depth and nonlinearity. Indeed, this sensitivity minor experimental choices could explain why the literature has been so divided on the usefulness of disentangled representations.
6 OUR THEORY CAN DESCRIBE THE BEHAVIOR OF DEEP NETWORKS ON CONJUNCTION- WISE ADDITIVE TASKS
So far, our analyses have been limited to simple kernel models, for their analytical tractability. We next tested 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 al.] 1998) or CIFAR- 10 (Krizhevsky et al., 2209) (see Appendix[p, D). Each component corresponds to random samples from a particular category rather than the one-hot input considered far and we study both in-distribution
8

---

Published as a conference paper at ICLR 2025
a
b
Convnet (MNIST)
ResNet (CIFAR)
VIT
(CIFAR)
Prediction
5
1.00
1.0
1.0
S(1;2)
Slope
0.8
0.75
0.6
0.6
0.33
-5
0.4
20
-5
10
20
20
0
Split
Dist.
Ground truth
Distance
Training
Convnet (MNIST)
ResNet (CIFAR)
ViT (CIFAR)
Convnet (MNIST)
ResNet (CIFAR)
VIT (CIFAR)
In-distribttion
Compositional
1.0
1.0
1.0
Accuracy
1.0
Interpolation Extrapolation
Slope
0.8
0.8
0.6
0.5
0.6
0.4
0.0
2
3
4
CD-3
CD-1
CD-3
CD-1
CD-3
CD-1
Training set size (p)
Task
Figure 5: Testing our theory in deep networks trained on MNIST and CIFAR versions of compositional tasks. Ranges indicate mean + one std. error (often too small to be visible). a. 51; in an intermediate ConvNet layer for different distances between digits. Lower distance yields a more conjunctive representation. b, Average model prediction for each combination components plotted against the ground truth (MNIST, distance of zero, 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 distance (each line corresponding of zero). For MSE instead of slope, see Fig. 12 e, Accuracy on all variants of context dependence.
particular W) and d, training set (for distance
and compositional generalization. Notably, different image categories correlated with each other. To control for this, we randomly permuted the assignment of categories 10) experiment. We considered several relevant vision architectures. which we all trained with backpropagation: convolutional networks (ConvNets, LeCun et al.) 1989) (trained on MNIST) and residual networks (ResNets, He et al. 2016) and Vision Transformers (ViTs, Dosovitskiy et al., 2020) (trained on CIFAR-10).
necessarily equally
to components for each
Spatial distance of components impacts 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, determined S(122) in intermediate layer of the network, averaging over different instances of all digits. We found that (1;2) was indced smaller for lower distances (Fig. (p), indicating more conjunctive population. This suggests that varying the distance between two digits provides a practical way of manipulating (1; below we use this insight to test predictions about how conjunctivity influences generalization behavior.
Deep networks tend to implement conjunction-wist additive computations. Conjunction additivity imposes substantial computational restriction: 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 a nontrivial prediction as these networks can in principle express arbitrary compositional computations. Remarkably, we found that a conjunction Appendix D.3). This indicates that large-scale neural networks tend to implement conjunction- wise additive computations, at least when trained on conjunction-wir additive tasks. Our theory suggests that they do so because the statistical structure of the dataset makes such computation natural.
additive model was highly predictive of the model responses (see
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, varying the size of the training set and whether generalization required interpolation also extrapolation. We trained the ConvNets on 20,000 samples and the ResNets and ViTs on 40,000 samples (Appendix EEI13)
We tested three theoretical predictions made by Proposition 5.1 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

---

Published as a conference paper at ICLR 2025
that model predictions were indeed compressed relative to the ground truth, but still exhibited strong linear relationship (Fig. 5p). This was also the case for ResNets and ViTs, which exhibited a slightly noisier linear relationship (Fig. T.]. 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 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 (1; (i.e. increasing distance between components, Fig. 5 l). On ConvNets, we found that higher distance indeed increases the slope (Fig. (p). This was not due to an increase in task difficulty, as m-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 training sets should increase the compositional generalization slope. Our experiments confirmed this prediction (Fig. 55)). 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). Notably, there was one exception to the latter finding: 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 MNIST version of context dependence using 30,000 training samples and the
the ConvNets ResNets and ViT's on a CIFAR-10 10 version of the task using 40,000 training samples. Again, their behavior was aligned with the kernel theory's predictions, having beiter-than-chance accuracy on CD-1 and CD-2, but having worse-than-chance accuracy on CD-3 (Fig. (p). This confirms that the deep networks also suffered from a context-driven shorteut on CD-3 (see also Fig. [6].
7 DISCUSSION
Humans often generalize to new situations by stitching together concepts and knowledge from prior experience. Despite the broad importance of this ability (both for cognitive science and machine learn- ing), 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, framework that captures neural network training or finetuning the kernel regime and more broadly lets us understand the impact of representational geometry on generalization. We found that they implement specific compositional computation ("conjunction-wis additivity"). We then investigated how dataset statistics and repre- sentational geometry impact successful generalization, highlighting two failure modes arising from the inductive bias of gradient descent (memorization leak and shorteut bias). Finally, we validated our theory in deep neural networks trained 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 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 representations have yielded such inconsistent results. Overall, our insights highlight the utility of kernel models in systematically investigating model generalization. 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. We demonstrate that our theory captures many qualitative phenomena in deep neural networks, but do not provide any quantitative bounds. Further, 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 other input/output formats (e.g. sequences with variable length) and non-compositionaaly structured representations. Most importantly, our theory is limited to a particular learning mechanism (kernel models). Other learning mechanisms could overcome the limitations highlighted in Sections 4 and 5 (we give an initial example in Appendix(F) By helping us design new benchmark tasks not solvable by kernel models, our theory provides important foundation for such advances.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
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, and Zeb Kurth-Nelson for comments the manuscript. The work was supported by NSF 1707398 (Neuronex), Gatsby Charitable Foundation GAT3708, and the NSF Al Institute for Artificial and Natural Intelligence (ARNI).
REFERENCES
Emmanuel Abbe, Samy Bengio, Aryo Lotfi, and Kevin Rizk. Generalization on the Unseen, Logic Reasoning and Degree Curriculum. June 2023. URL 1d 3dqwXbited]
Mustafa Abdool, Andrew J Nam, and James L McClelland. Continual learning and out of distribution generalization in a systematic reasoning task. In MATH-AI: The 3rd Workshop on Mathematical Reasoning and Al NeurlPS, volume 23, 2023.
Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural Module Networks, July 2017. wwLLattp://axxi.crrgp/p wttp/rrg/aabb.llae C2799 arXiv:1511 1X.009911.02799 .007999 [cs].
Dzmitry Bahdanau, Shikhar Murty, Michael Noukhovitch, Thien Huu Nguyen, Harm de Vries, and Aaron Courville. Systematic Generalization: What Required and Can It Be Learned?, April [es].
2019. URtp:/t///arxi wttp://.rgg/////aaaaoo//oo/aae/ abs/ 12889
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanzhez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash. Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks, October 2018. URL/sttp//arrxi..org//aass [cs, stat].
01261
Mark E. Bouton, James B. Nelson, and Juan M. Rosas. Stimulus generalization, context change, and forgetting. Psychological Bulletin, 125(2):171-186, 1999. ISSN 1939-1455. doi: 10.1037) 1883-2909.125.2.111 Place: US Publisher: American Psychological Association.
Alon Brutzkus and Amir Globerson. Why do Larger Models Generalize Better? A Theoretical Perspective via the XOR Problem. In Proceedings of the 36th International Conference on Machine Learning, pp. 822 830. PMLR. May 2019. URL https://proceednng .mrr ISSN: 2640-3498.
bress//97/brutzkkee 9b. html
Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Out-of-Distribution Generalization in Kernll Regression. In Advances in Neural Information Processing Systems, volume 34, pp. 12600-12612, Curran Associates, Inc., 2021a. URLnttpps://rroeeeiings http://rrooeeiinns..uu..p..p.ppp cc/
.tml
Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model align- ment explain generalization in kernel regression and infinitely wide neural networks. Nature Communications, 12(1):2914, May 2021b. ISSN 2041-1723, doi: 10. 10010003//414----22233313333
URL /tthhttps: //t::://wwwwwww www. nat patuure.e com/ htt.ee/ww....raoleeeee//6622222/ ture Publishing Group.
Publisher: Na-
Abdulkadir Canatar, Jenelle Feather, Albert Wakhloo, and Sue Chung. A Spectral Theory of Neural Prediction and Alignment. November 2023. URL httphtttss///oeeeev..ee.
forum?id=5B12222
Stephanie C. Y. Chan, Ishita Dasgupta, Junkyung Kim, Dharshan Kumaran, Andrew K. Lampinen, and Felix Hill. Transformers generalize differently from information stored in context vs in weights, October 2022. URL /tl.http..//xxww..oor//aaass/ 2210./06755 05675 1rX.v22210.05675 [es].

---

Published as a conference paper at ICLR 2025
Lénaïc Chizat and Francis Bach. Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss. In Proceedings of Thirty Third Conference on Learning Theory, pp. 1305-1338. PMLR. July 2020. URL attpss//pproceedings mlr press/
v1 v125/
html
ISSN: 2640-3498.
Lénaic Chizat, Edouard Oyallon, and Francis Bach. On Lazy Training in Differentiable Pro- gramming. In Advances in Newral Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019. URL https:: www.uinggn...u..p.eo.ee.. ae614c5578 111144c55743blaf330 3blaff2 0tt.oo332222222222225555333 Abst html
neurips pttp:/ppp....appee///0.......... hc/ppapeee//11///aelll
Youngmin Cho and Lawrence Saul. Kernel Methods for Deep Learning. In Ad- vances in Neural Information
Processing Systems, volume 22. Curran Asso-
ciates, 3fleccearfaabb55eeea000003330333
Inc., 2009. URL https:://ppers.nntt nipp htt.::siiss.ccpppp..e.eee wccppaper/200//aaeeee
html
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 344)333311, December 1989. ISSN 1435-568X. doi: 10.10077/F025551274 URL /ttt:::://oo..oo///1000....
Ishita Dasgupta, Erin Grant, and Tom Griffiths. Distinguishing rule and exemplar-based generalization in learning systems. In Proceedings of the 39th International Conference on Machine Learning. pp. 4816 4830. PMLR, June 2022. URL
mlr. www.ppesss/vvl22
dasqupta22b.htr html
ISSN: 2640-3498.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, and others. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprini
arXiv:2010.11929, 2020.
Aparna Elangovan, Jiayuan He, and Karin Verspoor. Memorization vs. Generalization: Quantifying Data Leakage in NLP Performance Evaluation, February 2021. URL
abs/2100 01818 arXiv:2102.01818 [es].
Babak Esmaeili, Hao Wu, Sarthak Jain, Alican Bozkurt, N. Siddharth, Brooks Paige, Dana H. Brooks, Jennifer Dy, and Jan- Willem Meent. Structured Disentangled Representations. In Proceedings of the Twenty-Second International Conference Artificial Intelligence and Statistics, pp. 2525-2534 PMLR, April 2019. URL https://proceedigg: ml press/v89/ esmae: 1111999 9a. html
ISSN: 2640-3498.
Vitaly Feldman. Does learning require memorization? a short tale about a long tail. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, STOC 2020, pp. 954 959, New York, NY. USA, June 2020. Association for Computing Machinery. ISBN 978- 978-144503-697944 doi: 10.1 N0.114//335773333342290
URL https::////tt. wtt.:ll.a..or.gg//// http:///wc....rr.../...11111111. 1ttp://..111111131333
3384290
Jerry A. Fodor and Zenon W. Pylyshyn. Connectionism and cognitive architecture: A
critical analysis. Cognition, 28(1):3-71, March 1988. ISSN 0010-0277.
doi: 10.
101670010-0277888900011- URL https:: www. wwwencediree......mcccoo..oo com/ science/
Steven M. Frankland and Joshua D. Greene. Concepts and Compositionality: In Search of the Brain's Language of Thought. Annual Review of Psychology. 71(1)2273-303 2020. doi: 10.1 10.1146/annurev-ppsyee 122216-011829, /tL.htttpp///01..o////000 annurev psareee-ppycc--2 12t.ppasch-12211111111 0118829 011829.
_eprint: http:://loooog////..//dmmeeeeeep
Robert Geirhos, Jöm--enrik Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A. Wichmann. Shortcut learning in deep neural networks. Nature Machine
Intelligence, 2(11))665- (66)6,,,,,6,660 November 2020. ISSN 2522-5839 doi: 10. 10.1038/s42256-000 0200442220620002577777
URL https: / //www natura
s2leee///2222652 020 020-07277-2
Number: 11
Publisher: Nature Publishing Group
12

---

Published as a conference paper at ICLR 2025
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pp. 1832-1841. PMLR. 2018.
Graeme Halford, William Wilson, and Steven Phillips. Relational knowledge: the foundation of higher cognition. Trends in Cognitive Sciences, 14(11):497-505, November 2010. ISSN 2010.08.00.0 1364-6613, doi: 10.1016/j.tics 000.://...cs.2200.8......0 005. URL https:/ http::/wwwww... /tt..//winweeieret..t...e.////ee com/
Insu Han, Amir Zandieh, Jaehoon Lee, Roman Novak, Lechao Xiao, and Amin Karbasi. Fast Neural Kernel Embeddings for General Activations, September 2022. URL http:/ttpp//ati// /ttppp//axxvvoorrrg
abs/2205 04121 arXiv:2209.0411 04121 [es, stat].
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving Deep into Recti-
fiers: Surpassing Human- Performance on ImageNet Classification. pp. 1034. 2015. URL http:pss////ppeaccccsseee thecvf......... cwm/cooccooo///oo httm//ontenttteee la____cccv_______ 22155/hmlm/// Delv
html
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image
Recognition. pp. 770-778, 2016. URL/attp:://peeaccees thecvf. wttpv//ccomooooooooo content. Deep Residual Reseeppeesiaaaaaaianniiee Lew.nnnennnnnnn___eeeaa
cvpr Srpr_2016/htm..
laloppppppe.__ paper.htm.
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta- VAE: Learning Basic Visual Concepts with a Constrained Variational Framework. In International Conference on Learning Representations, 2017. URL http::::: /ttpas::///peeeeeeeeeee net wwt.:neutt/dd-yyy///2/222m
Geoffrey E. Hinton, Alex Krizhevsky, and Sida D. Wang. Transforming Auto-Encoders, In Timo Honkela, Włodzislaw Duch, Mark Girolami, and Samuel Kaski (eds.), Artificial Neural Networks and Machine Learning ICANN 20/1, pp. 41,51, Berlin, Heidelberg, 2011. Springer. ISBN
978-3-642-21133--7 doi: 10. 10.10077997--3-64-221333
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks universal approximators. Neural Networks, 2(5):359 366, January 1989. ISSN 0893-6080. doi: 10100160093300000889990000000000 / wtw.://cceeeeeet...oooooc/eceeee com/ cww.sciecccc////cccccccccccccccc art.cle//11105533088000000
Dieuwke Hupkes, Verna Dankers, Mathijs
Mul, and Elia Bruni. Compositionalitt Decomposed: How do Neural Networks Generalise? Journal of Artificial Intelligence Research, 67:757-795, April 2020. ISSN 1076-9757, doi: 00.1613/jair..116677
JRLhttps: www. jair otg/index
aho/jaar/arriicle/viiee
Takuya Ito, Tim Klinger, Douglas H. Schultz, John D. Murray, Michael W. Cole, and Mattia Rigotti. Compositional generalization through abstract representations in human and artificial neural net- works. September 2022. URL [q-bio].
a/bs /ttp://///2222222/
arXiv:2209.0745 .07431
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and
generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Devon Jarvis, Richard Klein, Benjamin Rosman, and Andrew M. Saxe. On The Specialization of Neural Modules. In The Eleventh International Conference on Learning Representations, 2023. URL
Ziwei Ji, Miroslav Dudik, Robert E Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. In Conference on Learning Theory, pp. 2109-2136. PMLR, 2020.
Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Li Fei-Fei, C. Lawrence Zitnick, and Ross Girshick. CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoning. pp. 1901-29100 2017. URL htttps://ppeaccessss
thecvf. com/ content. cvpr www.:/tmmmmoooooooooooo CLEVR A_D.aagosttc_ccve
hatpra/so_ccccctA..aaaaaaaataitr 2017 2atp__22001___________22__
paperaper.... .tmml
13

---

Published as a conference paper at ICLR 2025
Frank Jäkel, Bernhard Schölkopf, and Felix A Wichmann. Generalization and similarity in exemplar models of categorization: Insights from machine learning. Psychonomic Bulletin Review, 15: 256-271 2008. Publisher: Springer.
Frank Jäkel, Bernhard Schölkopf, and Felix A. Wichmann. Does Cognitive Science Need Ker- nels? Trends Cogmitive Sciences, 13(9):381-338 September 2009. ISSN 1364-6613, 1879-307X. doi: 10. 1a.10166j.iiss.200000000 www.0000900000000 002. URL https: wwww. cell com/trends/ Publisher: Elsevier.
(09) 00143-0
Alex Krizhevsky, Geoffrey Hinton, and others. Learning multiple layers of features from tiny images.
2009. Publisher: Toronto, ON, Canada.
Sebastien Lachapelle, Divyat Mahajan, Ioannis Mitliagkas, and Simon Lacoste-Julien. Additive Decoders for Latent Variables Identification and Cartesian-Product Extrapolation. November 2023.
URL htRL:hhts:://// /ttp:::://ppeeeeieiee net /ane/ffornn forum? wet.rrummmmd-6eNNN- d= AUAR
Brenden Lake and Marco Baroni. Generalization without systematicity: 35th International Conference on Machine Learning, ICML 2018. 35th International Conference Machine Learming, ICML
2018, pp. 4487-4499, 2018. URL http::/wwww scopus com/ inward/ record. url?
Publisher: International Machine Learning
Society (IMLS).
Brenden M. Lake and Marco Baroni. Human- Hlue systematic generalization through meta- learning neural network. Nature, (2385)))) 115-121, November 2023. ISSN 1476- 4687. doi: 1011038/41188--02-0666----
URL http::ts:: www.we.tuur...m com/ cow/articles/////ccccccocmcooott Publisher: Nature Publishing Group.
1115866023-0555
Brenden M. Lake, Ruslan Salakhutdinov, and Joshua B. Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350(6266:1332--3333 1338. December 2015. doi: 10. http:///iienc..aa300555500 URL BRL.httss:// www. sc Lence...... www.oorgooo..oo.ooooooo.oo wwtg/////fll//////////oooogooeee 1126/science. aab3050
Publisher: American Association for the Advancement of Science.
Brenden M. Lake, Tomer D. Ullman, Joshua B. Tenenbaum, and Samuel J. Gershman. Building machines that learn and think like people. Behavioral and Brain Sciences, 40:e253, January 2017. ISSN 0140-525X, 1469-1825,
doi: 10.10177500440555XX600011333
URL https:
7/ camb
9955511744500777166333303
Publisher: Cambridge University Press.
Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L., D. Jackel. Backpropagation Applied Handwritten Zip Code Recognition. Neural Computation, 1(4): 541-551, 1989. doi: 10.1162/ncco. (tt6///cco..99........3 1..4.1.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 36(11):2278-23) 2324, 1998. doi: 10. 10.1109/5.72679.
Michael A. Lepori, Thomas Serre, and Ellie Pavlick. Break It Down: Evidence for Structural Compositionality in Neural Networks, November 2023. URL http::/arxiv.orrrg. abs/ 2301 10884
ftt::2301.10884 [cs].
Martha Lewis. Nihal V. Nayak, Peilin Yu, Qinan Yu, Jack Merullo, Stephen H. Bach, and Ellic Pavlick. Does CLIP Bind Concepts? Probing Compositionality in Large Image Models, March 2023. URL
/ttt:://aaatteeee wwwpsiiw.rrgaasa. www./ogg.s.....oooo /2112,22222.. 10537 1XXi:22212.10533 [cs].
Samuel Lippl, Kenneth Kay, Greg Jensen, Vincent Ferrera, and L. F. Abbott. mathematical theory of relational generalization in transitive inference. Proceedings of the National Academy of Sciences, 121 (23322)3331455111 July 2024. doi: 10. 10.1073/pna..231455
URL (https Publisher: Proceedings of
wwws.pna...o orgo /ttb////////// 1013.11773pppeee 2aniaas..335550 2314511122
the National Academy of Sciences.
Francesco Locatello, Stefan Bauer, Mario Lucic, Gunnar Raetsch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem. Challenging common assumptions in the unsupervised learning of disentan- gled representations. international conference on machine learning, pp. 4114-4122 PMLR, 2019.
14

---

Published as a conference paper at ICLR 2025
Elena Lorenzi, Matilde Perrino, and Giorgio Vallortigara. Numerosities and Other Magnitudes in the Brains: A Comparative View. Frontiers in Psychology. 12, April 2021. ISSN 1664-1078 doi: 10.3389ffssyg.22211644422 Seychology/artee
URL https://wwwt www.ttfroontttoneeoo org. jtw.o//sssooooooooo.......aa.. journals/ / www..pp..p....... 2021. .61.1..4111111
3389/
641 (41994/fu1]
Publisher: Frontiers.
Kaifeng Lyu and Jian Li. Gradient Descent Maximizes the Margin of Homogeneous Neural Networks.
Neuraal In International Conference on Learning Representations, 2020. URL /ttp:ttts///oeereeei.e
net/ forum SttemmmdddSJJeeeeeeeeeee
Sadhika Malladi, Alexander Wettig, Dingli Yu, Danqi Chen, and Sanjeev Arora. A Kernel-Based
View of Language Model Fine-Tuning. In Proceedings of the 40th International Conference on Machine Learming, pp. 23610-23641, PMLR. July 2023. URL /RLLttts///prrceediing
Dxess/v202/malladi:
html
ISSN: 2640-3498.
Brendan O. McGonigle and Margaret Chalmers. Are monkeys logical? Nature, 267:694-696, 1977.
ISSN 1476-4687. doi: 10.1038/267694a0.
Place: United Kingdom Publisher: Nature Publishing
Group.
Eric Mitchell, Chelsea Finn, and Chris Manning, Challenges of acquiring compositional inductive biases via meta-learning. In AAAI Workshop on Meta-Learning and MetaDL. Challenge, pp. 138-148. PMLR, 2021.
Sarthak Mittal, Yoshua Bengio, and Guillaume Lajoie.
a Modular Architecture
Enough? Advances in Neural Information Processing Systems, 35:28747-28760, Decem-
ber 2022. URL/httpss//prrcceddnng neuri http:////e.ppopooononnoonnnnnnaa httppppperr.fllsppppee/222222 hasa//baLL4111777666111113333333 htt.:///ee.aatt.ao....eaaaaaaaaa hoteeeatttttttttttooooott..ee.e.
Vaishnavh Nagarajan, Anders Andreassen, and Behnam Neyshabur. Understandingg the Failure Modes of Dut-of-Distributiin Generalization, April 2021. URL.
15775
arXiv:2010.15777 [cs, stat].
Jeanne E Parker and Debra L Hollister. The Cognitive Science Basis for Context. In Patrick Brézillon and Avelino J. Gonzalez (eds.), Context in Computing: A Cross-Disciplines Disccppiiaar Ap- proach for Modeling the Real World, pp. 205-219. Springer, New York, NY, 2014. ISBN doi:
978- 1981--4939-188744
11109997-1-4999-111
14. URL httpp:://di..rog///..o org//0
9007/978-1-4999-1885
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, and others. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research, 12:2825-288 2830. 2011.
Yi Ren, Samuel Lavoie, Michael Galkin, Danica J. Sutherland, and Aaron C Courville. Im- proving Compositional Generalization using Iterated Learning and Simplicial Embeddings. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Ad- vances in Neural Information Processing Systems, volume 36, pp. 60547-60572. Curran Asso- ciates, Inc., 2023. URL,
2023 1tt//ile/// be FTF.L///2.33222222aaee1111223332
Mattia Rigotti, Omri Barak, Melissa R Warden, Xiao-Jing Wang, Nathaniel D Daw, Earl K Miller, and Stefano Fusi. The importance of mixed selectivity in complex cognitive tasks. Nature, 497 (7451):585-509 590, 2013. Publisher: Nature Publishing Group UK London.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Alina Beygelzimer and Daniel Hsu (eds.), Proceedings of the Shirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp. v savaaaaaaaaaee rese1 9a. .hmm
pressersss PMLR, June 2019. URL https: http::///pp.ceediggs..m... mlr press/
15

---

Published as a conference paper at ICLR 2025
Andrew Saxe, Shagun Sodhani, and Sam Jay Lewallen. The Neural Race Reduction: Dynamics of Abstraction in Gated Networks. In Proceedings of the 39th International Conference on Machine Learning, pp. 19387-19309. PMLR, June 2022. URL https://proceedings
m1 a.lr. press/rs//vv 62 saxe22a............ html
ISSN: 2640-3498.
Margaret L Schlichting and Alison R Preston. Memory integration: neural mechanisms and implica- tions for behavior. Current opinion in behavioral sciences, 1:1-8. 2015. Publisher: Elsevier.
Lukas Schott, Julius Von Kügelgen, Frederik Träuble, Peter Vincent Gehler, Chris Russell, Matthias Bethge, Bernhard Schölkopf, Francesco Locatello, and Wieland Brendel. Visual Representation Learning Does Not Generalize Strongly Within the Same Domain. In International Confer- Learning Representations, 2022. URL https:: 9RUHP11adch
net wwweeeettorrrree Forumooiiii 7id=
Simon Schug, Seijin Kobayashi, Yassir Akram, Maciej Wotczyk, Alexandra Proca, Johannes von Oswald, Razvan Pascanu, João Sacramento, and Angelika Steger. Discovering modular solutions that generalize compositionally, March 2024. URLhttp:: httpc:/://arxiv.oorr/aa////11111 15001 arXiv:2312.15001 [cs].
Philipp Schwartenbeck, Alon Baram, Yunzhe Liu, Shirley Mark, Timothy Muller, Raymond Dolan, Matthew Botvinick, Zeb Kurth-Nelson, and Timothy Behrens. Generative replay underlies com- positional inference in the hippocampal--reffonnni
circuit. Cell, October 2023. ISSN 0092-8674. h 100 60666. ce 11 2023 09. 004
Place: United States.
Bernhard Schölkopf. The Kernel Trick for Distances. In Advances in Neural Information Processing http://pppprr..ippccccppaaaapaaa
Systems, volume 13. MIT Press, 2000. URL httpsssts///pppperr nips cwtppppppppppppcceepcccceee..eee _illss/
wttppppcccpppprre_eeee.... 7337 http:///............/////aaaaaa.
paper/2000
Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain, and Praneeth Netrapalli. The
Pitfalls of Simplicity Bias in Neural Networks, October 2020. URL http://arxiv.orgg
abs/2006. 07710 arXiv:2006.07710 [cs, stat].
Hannah Sheahan, Fabrice Luyckx, Stephanie Nelli, Clemens Teupe, and Christopher Summer- field. Neural state space alignment for magnitude generalization in humans and recurrent net- works. Neuron, (09())1214-1222:e) April 2021. ISSN 0896-6273, doi: 10.1016/j.neuron. 2021.02.004. URL https: www. www.sscieeneeiree..com www.://wwee..eeeeee.oeeeeeeeeeee http:///c/cccceeeeee/aatiiceeeea SDE966273210007811
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018. Publisher: JMLR. org.
Kelsey N Spalding, Margaret L Schlichting, Dagmar Zeithamova, Alison R Preston, Daniel Tranel, Melissa C Duff, and David Warren. Ventromedial prefrontal cortex necessary for normal associative inference and memory integration. Journal of N 38(15):3767-3775, 2018. Publisher: Soc Neuroscience.
Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R. Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, Agnieszka Kluska, Aitor Lewkowycz, Akshat Agarwal, Alethea Power, Alex Ray, Alex Warstadt, Alexander W. Kocurek, Ali Safaya, Ali Tazary, Alice Xiang, Alicia Parrish, Allen Nie, Aman Hussain, Amanda Askell, Amanda Dsouza, Ambrose Slone, Ameet Rahane, Anantharaman S. Iyer, Anders An- dreassen, Andrea Madotto, Andrea Santilli, Andreas Stuhlmüller, Andrew Dai. Andrew La. Andrew Lampinen, Andy Zou, Angela Jiang, Angelica Chen, Anh Vuong, Animesh Gupta, Anna Gottardi, Antonio Norelli, Anu Venkatesh, Arash Gholamidavoodi, Arfa Tabassum, Arul Menezes, Arun Kirubarajan, Asher Mullokandov, Ashish Sabharwal, Austin Herrick, Avia Efrat, Aykut Erdem, Ayla Karakaş, B. Ryan Roberts, Bao Sheng Loe, Barret Zoph, Bartiomiej Bojanowski, Batuhan Özyurt, Behnam Hedayatnia, Behnam Neyshabur, Benjamin Inden, Benno Stein, Berk Ekmekci, Bill Yuchen Lin, Blake Howald, Bryan Orinion, Cameron Diao, Cameron Dour, Cather- ine Stinson, Cedrick Argueta. César Ferri Ramírez, Chandan Singh, Charles Rathkopf, Chenlin Meng, Chitta Baral, Chiyu Wu, Chris Dallison-Burchh Chris Waites, Christian Voigt, Christo- pher D. Manning, Christopher Potts, Cindy Ramirez, Clara E. Rivera, Clemencia Siro, Colin Raffel,
16

---

Published as a conference paper at ICLR 2025
Courtney Asheraft, Cristina Garbacea, Damien Sileo, Dan Garrette, Dan Hendrycks, Dan Kilman, Dan Roth, Daniel Freeman, Daniel Khashabi, Daniel Levy, Daniel Moseguí González, Danielle Perszyk, Danny Hernandez, Danqi Chen, Daphne Ippolito, Dar Gilboa, David Dohan, David Drakard, David Jurgens, Dehajyoti Datta, Deep Ganguli, Denis Emelin, Denis Kleyko, Deniz Yuret, Derek Chen, Derek Tam, Dieuwke Hupkes, Diganta Misra, Dilyar Buzan, Dimitri Coelho Mollo, Diyi Yang. Dong-Ho Lee, Dylan Schrader, Ekaterina Shutova, Ekin Dogus Cubuk, Elad Segal, Eleanor Hagerman, Elizabeth Barnes, Elizabeth Donoway, Ellie Pavlick, Emanuele Rodola, Emma Lam, Eric Chu, Eric Tang, Erkut Erdem, Ernie Chang, Ethan A. Chi, Ethan Dyer, Ethan Jerzak, Ethan Kim, Eunice Engefu Manyasi, Evgenii Zheltonozhskii, Fanyue Xia, Fatemeh Siar, Fernando Martinez-Plumee, Francesca Happé, Francois Chollet, Frieda Rong. Gaurav Mishra, Genta Indra Winata, Gerard de Melo, Germán Kruszewski, Giambattista Parascandolo, Giorgio Mariani, Gloria Wang, Gonzalo haimovitch-L.óper Gregor Betz, Guy Gur-Ari, Hana Galijasevic, Hannah Kim, Hannah Rashkin, Hannanch Hajishirzi. Harsh Mchta, Hayden Bogar, Henry Shevlin, Hinrich Schütze. Hiromu Yakura, Hongming Zhang, Hugh Mee Wong, Ian Ng. Isaac Noble, Jaap Jumelet, Jack Geissinger, Jackson Kernion, Jacob Hilton, Jaehoon Lee, Jaime Fernández Fisac, James B. Simon, James Koppel, James Zheng, James Zou, Jan Kocoñ, Jana Thompson, Janelle Wingfield, Jared Kaplan, Jarema Radom, Jascha Sohl-Dickstein, Jason Phang, Jason Wei, Jason Yosinski, Jekaterina Novikova, Jelle Bosscher, Jennifer Marsh, Jeremy Kim, Jeroen Taal, Jesse Engel, Jesujoba Alabi, Jiacheng Xu, Jiaming Song, Jillian Tang. Joan Waweru, John Burden, John Miller, John U. Balis, Jonathan Batchelder, Jonathan Berant, Jörg Frohberg, Jos Rozen, Jose Hemandez--rain Orallo, Joseph Boudeman, Joseph Guerr, Joseph Jones, Joshua B. Tenenbaum, Joshua S. Rule, Joyce Chua, Kamil Kanclerz, Karen Liveseu, Karl Krauth, Karthik Gopalakr- ishnan, Katerina Ignatyeva, Katja Markert, Kaustubh D. Dhole, Kevin Gimpel, Kevin Omondi, Kory Mathewson, Kristen Chiafullo, Ksenia Shkaruta, Kumar Shridhar, Kyle McDonell, Kyle Richardson, Laria Reynolds, Leo Gao, Li Zhang, Liam Dugan, Lianhui Qin, Lidia Contreras- Ochando, Louis-Philippe Morency, Luca Moschella, Lucas Lam, Lucy Noble, Ludwig Schmidt, Luheng He, Luis Oliveros Colón, Luke Metz. Lütfi Kerem Şenel, Maarten Bosma, Maarten Sap. Maartje ter Hoeve. Maheen Farooqi. Manaal Faruqui, Mantas Mazeika, Marco Baturan, Marco Marelli, Marco Maru, Maria Jose Ramírez Quintana, Marie Tolkiehn, Mario Giulianelli, Martha Lewis, Martin Potthast, Matthew I.. Leavitt, Matthias Hagen, Mátýás Schubert, Medina Orduna Baitemirova, Melody Arnaud, Melvin McElrath, Michael A. Yee, Michael Cohen, Michael Gu, Michael Ivanitskiy, Michael Starritt, Michael Strube, Michal Swędrowski, Michele Bevilacqua, Michihiro Yasunaga, Mihir Kale, Mike Cain, Mimee Xu, Mirac Suzgun, Mitch Walker, Mo Tiwari, Mohit Bansal, Moin Aminnaseri, Mor Geva, Mozhdeh Gheini, Mukund Varma T, Nanyun Peng, Nathan A. Chi, Nayeon Lee, Neta Gur-Ari Krakover, Nicholas Cameron, Nicholas Roberts, Nick Doiron, Nicole Martinez, Nikita Nangia, Niklas Deckers, Niklas Muennighoff, Nitish Shirish Keskar, Niveditha S. Iyer, Noah Constant, Noah Fiedel, Nuan Wen, Oliver Zhang, Omar Agha, Omar Elbaghdadi, Omer Levy, Owain Evans, Pablo Antonio Moreno Casares, Parth Doshi, Pascale Fung, Paul Pu Liang. Paul Vicol, Pegah Alipoormolabashi, Peiyuan Liao, Percy Liang. Peter Chang, Peter Eckersley, Phu Mon Htut, Pinyu Hwang, Piotr Milkowski, Piyush Patil, Pouya Pezeshkpour, Priti Oli, Qiaozhu Mei, Qing Lyu, Qinlang Chen, Rabin Banjade, Rachel Etta Rudolph, Raefer Gabriel, Rahel Habacker, Ramon Risco, Raphaël Millière, Rhythm Garg, Richard Barnes, Rif A. Saurous, Riku Arakawa, Robbe Raymaekers, Robert Frank, Rohan Sikand, Roman Novak, Roman Sitelew, Ronan LeBras. Rosanne Liu, Rowan Jacobs, Rui Zhang, Ruslan Salakhutdinov, Ryan Chi, Ryan Lee, Ryan Stovall, Ryan Techan, Rylan Yang, Sahib Singh, Saif M. Mohammad, Sa- jant Anand, Sam Dillavou, Sam Shleifer, Sam Wiseman, Samuel Gruetter. Samuel R. Bowman, Samuel S. Schoenholz, Sanghyun Han, Sanjeev Kwatra, Sarah A. Rous, Sarik Ghazarian, Sayan Ghosh, Sean Casey, Sebastian Bischoff, Sebastian Gehrmann, Sebastian Schuster, Sepideh Sadeghi, Shadi Hamdan, Sharon Zhou, Shashank Srivastava, Sherry Shi. Shikhar Singh. Shima Asaadi, Shixiang Shane Gu, Shubh Pachchigar, Shubham Toshniwal, Shyam Upadhyay, Shyamolima, Debnath, Siamak Shakeri, Simon Thormeyer, Simone Melzi, Siva Reddy, Sneha Priscilla Makini, Soo-Hwan Lee, Spencer Torene, Sriharsha Hatwar, Stanislas Dehaene, Stefan Divic, Stefano Ermon, Stella Biderman, Stephanie Lin, Stephen Prasad, Steven T. Piantadosi, Stuart M. Shieber, Summer Misherghi, Svetlana Kiritchenko, Swaroop Mishra, Tal Linzen, Tal Schuster, Tao Li, Tao Yu, Tariq Ali, Tatsu Hashimoto, Te-Lin Wu, Théo Desbordes, Theodore Rothschild, Thomas Phan, Tianle Wang, Tiberius Nkinyili, Timo Schick, Timofei Kornev, Titus Tunduny, Tobias Ger- stenberg, Trenton Chang, Trishala Neeraj. Tushar Khot, Tyler Shultz, Uri Shaham, Vedant Misra, Vera Demberg, Victoria Nyamai, Vikas Raunak, Vinay Ramasesh, Vinay Uday Prabhu, Vishakh Padmakumar, Vivek Srikumar, William Fedus, William Saunders, William Zhang, Wout Vossen,
17

---

Published as a conference paper at ICLR 2025
Xiang Ren, Xiaoyu Tong, Xinran Zhao, Xinyi Wu, Xudong Shen, Yadollah Yaghoobzadeh, Yair Lakretz, Yangqiu Song. Yasaman Bahri, Yeji Choi, Yichi Yang. Yiding Hao, Yifu Chen, Yonatan Belinkov, Yu Hou, Yufang Hou, Yuntao Bai, Zachary Seid, Zhuoye Zhao, Zijian Wang, Zijie J. Wang, Zirui Wang, and Ziyi Wu. Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models, June 2023. URL http::://aa.....rr/aabaaaee/ arXiv:2206.0461 [cs, stat].
645
Jordan A. Taylor and Richard B. Ivry. Context-dependent generalization. Frontiers in Human Neuro- : www Publisher: Frontiers.
science, 7, May 2013. ISSN 1662-5161, doi: 10.3389/fnhum 2013.0017
Frontiersin.c wttp:siin.rggrrtiieesssee
/ Enhum. 2013. 00171
Frederik Träuble, Elliot Creager, Niki Kilbertus, Francesco Locatello, Andrea Dittadi, Anirudh Goyal, Bernhard Schölkopf, and Stefan Bauer. On Disentangled Representations Learned from Correlated Data. In Proceedings of the 38th International Conference Machine Learning, pp. 10400-104122 PMLR, July 2021. httpp:t//ppp:cceeeeeeeee Erauble2la. html
mlr. wwl...ress/vv3.
ISSN: 2640-3498.
Russell Tsuchida, Farbod Roosta-Khorasani, and Marcus Gallagher. Invariance of Weight Dis- tributions in Rectified MIPs,, May 2018. URL http:://arr.....r////////1111 09090 1rXiv:1711. 111::971 [cs, stat].
Russell Tsuchida. Fred Roosta, and Marcus Gallagher. Richer priors for infinitely wide multi-layer perceptrons, November 2019. URL arXiv:1911.1292) [es, stat].
12927
Sjoerd van Steenkiste, Francesco Locatello, Jürgen Schmidhuber, and Olivier Bachem. Are Disentangled Representations Helpful for Abstract Visual Reasoning? vances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.. 2019. URL haa.:/eccc51aa30000111a555aa-aa3
Ad-
Gal Vardi and Ohad Shamir. Implicit Regularization in ReLU Networks with the Square Loss. In Proceedings of Thirty Fourth Conference Learning Theory, pp. 4224-4258. PMLR, July 2021. ISSN: 2640-3498.
URL http:///pppoeednnnng...r..eeeeee
html
Colin G. West. Advances in apparent conceptual physics reasoning in GPT-4, March 2023. URL Publication Ti-
https://ui ads harvard. tle: arXiv e-prints ADS Bibcode: 2023urXiw2303170122.
James C. R. Whittington, Will Dorrell, Surya Ganguli, and Timothy Behrens. Disentanglement with Biological Constraints: Theory of Functional Cell Types. In The Eleventh International
//t/////////s////ee/eeeeee Conference Learning Representations, 2023. htRp:tt:::/ http:///pppeeeee..eee/e net. wtt.://wwwweettttntnte forum?
1d 12-92_.0 Gfh2nGH
Thaddäus Wiedemer, Jack Brady, Alexander Panfilov, Attila Juhos, Matthias Bethge, and Wieland Brendel. Provable Compositional Generalization for Object-Centric Learning. arXiv preprint
arXiv:2310.05327, 2023a.
Thaddäus Wiedemer, Prasanna Mayilvahanan, Matthias Bethge, and Wieland Bren- Compositional Generalization from First Principles.
del.
Advances in Neu- ral Information Processing Systems, 36:6941 69600, December 2023b. URL
https://proceeeing.eeeeet http::/aw.....aaaaaaaaaeaeeeeeea
15 LL5.000SSSseee11139993433--acooe
html
Bin Wu, Jinyuan Fang, Xiangxiang Zeng, Shangsong Liang, and Qiang Zhang. Adaptive compo- sitional continual meta-learning. In International Conference on Machine Learning, pp. 37358- 37378, PMLR, 2023.
Zhiwei Xu, Yutong Wang, Spencer Frei, Gal Vardi, and Wei Hu. Benign Overfitting and Grokking in ReLU Networks for XOR Cluster Data, October 2023. URL htttp://acxiv.org/////// wwwp:xiiiorr///aa.o 231 0. 02541 arXiv:23 100.02441 [cs, stat].
18

---

Published as a conference paper at ICLR 2025
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Michael C. Mozer, and Yoram Singer. Identity Crisis: Memorization and Generalization under Extreme Overparameterization January 2020. URL
httt://arxiv.org/ wrg.abs//////ooooooooo.....eso 1902. 04698 arXiv:1902.04698 [es, stat].
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021. Publisher: ACM New York, NY. USA.
19

---

Published as a conference paper at ICLR 2025
A MATHEMATICAL ANALYSIS
A.1 GENERALIZED COMPOSITIONALIY STRUCTURED REPRESENTATIONS
In the main text, we considered "compositionally structured" representations. This is the class of representations ((2) whose kernel (2 =') = ((z)" o(²') only depends on the number of components and 2' have in common. Here define slightly more general class of representations whose kernel depends on the identity of the components they have in common, i.e.
(²2,2') == {c 1, ....., Cl z
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 representa- tional 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 Appendices A.33 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 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 basis for generalization. For example, in transitive equivalence (Fig. 21), if items that are in the same equivalence class are represented as more similar to each other, that would serve basis for generalization are particularly interested in compositionally structured representations, as they ensure that kernel models only able generalize compositionally.
the task that is not compositional in nature. For this reason,
Characterizing compositional generalization in non-compositionally structured representations re- quires us to meaningfully distinguish between compositional and non-compositional aspects of their generalization. We present an example of such an analysis in Appendix AA.5] proving that if the non-compositional representational components are random, the models still generalize in conjunction-wise additive manner in expectation.
A.3 NONLINEAR TRANSFORMATIONS AND COMPOSITIONAL STRUCTURE
broad range of transforms & induces a kernel Kz(2, z') o(z)" ((2)) that only depends on the input similarity K(z, 2 z'''. 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 wndth limit) (Han et al.
2022):
Definition A.I. Given an input z E Rd a network depth 2 2, and a set of widths Hi,...,
(i....,H, Hr E N,
we define neural network by recursively defining the operation d!')) of the 1hh layer as
a = (a
(H.. (w + b()) w() E M
(5)
where (()) and (00) are i.i.d. sampled from random distribution and a R R is nonlinearity The complete transform is then given by Φ = x(L)
(1))).
The infinite-wide limit is characterized by Hi...., H (the order of these limits does not matter). This setup includes, in particular, the random feature model investigated by Abbe et al. (002)).
20

---

Published as a conference paper at ICLR 2025
Further, the condition is met by most commonly used kernel functions including any radial basis function that depends on the Euclidean l fy-norm (e.g. the Gaussian kemne), Any nonlinear transform that meets this condition also conserves compositional structure, i... if z: is compositionally structured then so is (()). This allows us to derive computational restrictions on this broad range of models.
A.4 PROOF OF THEOREM
Theorem 4.2. For any kernel model f with a compositionally structured representation, we can find conjunction-wise functions fa Ilee Ze - IR, where J S (1...., C), such that for any input Rd representing components Z, the model response is given by
f(x) = Σ J JcCoj]t=l fz(zs),
== (ze)eEJ.
(2)
Proof. Because the kernel K' is compositionally structured, its similarity K(z, z²) only depends on the overlap (zz, 2²) S {I...., C'} (see definition in Eq. (4)) We denote the similarity for inputs
overlapping in S S (1,...,C) C) by lis and define set of training items overlapping with E Zost in
S as
Zitain (z, J) = {2" E Zitain VVe.zo = 2.
(6)
The key idea is to decompose Zunin into these different overlaps in order to separate the sum into its components. However, by our definition, the datasets Zuain (z, J) are not disjoint. Indeed, S C S implies (z, JJ) C Zuan J') and in particular (z, 0) Zuain To adjust for this, we define ō as the similarity added by Ki to the similarity between conjunctions with one component fewer, recursively defining
8, = KJJ - Σ 60 kig
6y-
J'CJ
We then decompose
[())
Σ 0g (2, =
E
85
agt.
(8)
JE()....))
This equality obtains because for each & E Z, 2 E Zurain
ōo do(x,
Σ
8y RO(s,2") K x2,,²",,
(9)
J:2F EZ (z,J)
J'C0(2,2*)
which is true by definition. We note that for Conj(z [ (2/zznnnn) Zimin (2, 0. Defining
fz(2) = 5J
a+7
(10)
et ETEZ
proves the proposition.
A.5 NON-COMPOSITIONALYY STRUCTURED REPRESENTATIONS
So far, we have considered representations that are compositionally structured. In practice, however, representations will almost never be exactly compositionally structured. Even when there is no specific similarity structure within components, there will be random noise in the representations. Here we characterize one such scenario, demonstrating that in expectation, these representations still yield conjunction-we wise additive computations.
Proposition A.2. Consider an input with C components. We consider representation that represents each component and conjunction of components =1, J C (1....,C) by random vector [و(= E RRd, F, ~ (0, ( of O, where k []. The representation itself is given by the sum of EEc(t..... [)](=s) All ور(=ソ] are sampled independently from each other. This means that the similarity between different components well as the entanglement of different components varies randomly. As a result, the kernel regression estimator f(2) is not conjunction-wee additive. However, its expectation, E[]())], is conjunction additive, indicating that all deviations from conjunction additivity arise from random noise and cannot be used for systematic generalization.
all these vectors:
21

---

Published as a conference paper at ICLR 2025
Proof. We consider the training representation X (#(zo])=Er,mn, X E R Ni and the test representation X = (=]==])==e X R This gives rise to the training kernel K XXT and the train-test kernel, K X The dual coefficients are given by
K We now consider a test set input ã = ][ representing the underlying components ž. Denoting the similarity to the training set by k(,, X) X8 E R Nuin, the test set behavior is given by
f(0) = a a
Σ
a d'xxslzs++
E
at x= (1() f2(),
JEConj(E 2
J&Conj(E) 22min)
(11)
where we've simply split up the sum into the conjunction wise additive part and the remainder. Clearly, this remainder, (²) = Σ Jcconi(s) Quin) a Xx.]zz), will generally not be zero. However, will now prove that [2 proposition. To do so, we note that we can assume that we have first sampled all Gaussian vectors relevant for the training set (we will denote this set of random variables by A and subsequently sample the set of Gaussian vectors only relevant for the test trial, i.c. (ØJ) J3Conj(3] (unis) (we will denote this set of random variables by 2eest). Then,
O. As (z) is conjunction wise additive, this will prove the
[[]( = p
E (2(())AA)
Σ
Ex [a X
[x] [B]] [[]]]
(12)
JeConi( & Zuai)
This is zero, Exuu [x. [=]] Exp [x.] ( = 0, which follows from the fact that x. [zy]
for J E Conj(3) Zimin)) is sampled independently from train
To test our theory empirically, we sample range of Gaussian representations and train them on symbolic addition, transitive equivalence, and context dependence. For symbolic addition and transitive equivalence, we consider representations with expected S(1: e [0.1, 1] using ten equally spaced values (i.e.
For context dependence, we consider two types of representation: rep. 1, where 01 0, = 0.5, Ø3 0.1, (i.e. single components are most saliently represented), and rep. 2, where 01 = 0.5, 02 = 1, 0.1 (i.e. conjunctions of two components are most saliently represented). We consider representations with 100 and sample 100 instances of each representations. We then fit each representation to these three tasks.
We first estimate these models' additivity on symbolic addition and context dependence. We find that while many model instance are highly additive, some can be highly non-additive (Fig.60). However, when averaging across the model behavior 100 randomly sampled representations, this average behavior is perfectly described by a conjunction-wiss additive function. This empirically confirms our proposition.
Our proposition implies that these con-compositionally structured representations can still only systematically generalize on conjunction-wise additive tasks. To confirm this insight, we plotted the distribution of accuracies on the transitive equivalence problem across all random model instances. We found that while the models consistently learned the training set, they were indeed unable to generalize to the test set (Fig. (6)).
Finally, we investigated whether our analysis in Section predicted the behavior of randomly sampled representations. Importantly, we have no theoretical guarantees for this scenario. Interestingly, however, the model behaviors were still well predicted by our theory. Specifically, we estimated the slopes that best described the compositional generalization behavior on symbolic addition for different training sets (as in 55. We found that across different model instances, these slopes were highly varied (Fig. (G)). However, the average slope across all random samples was well predicted by our analytical theory.
Similarly, our theoretical insights on context dependence provided meaningful insight into the generalization behavior of these randomly sampled models. Specifically, on CD-3, the model more saliently representing the single components failed to generalize, whereas the model more saliently representing conjunctions of two components generalized above chance. In contrast, CD-2, both models generalized above chance. This indicates that our insights on how prevalent shortcut biases are for different training datasets extends to randomly sampled representations.
22

---

Published as a conference paper at ICLR 2025
average per sample
150
Count
Count
Train Test
100
Addition CD
50
0.5 Additivity
1.0
0.00
0.25
0.50
0.75 1.00
Accuracy
CD-3
CD-2
1.00
80
60
Slope
0.50
Size
Count
Rep. 1 Rep. 2
= 2
40
0.25
20
0.00
-0.25
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.5
1.0
0.0
0.5
1.0
((1:2)
Accuracy
Figure 6: Analysis of randomly sampled representations considered in Proposition A.2 In all cases we sample 100-dimensional representations. For addition, we consider representations with weights that explore S(1:2) E [0.1, 1] and for context dependence, we consider representations where (51, 02 03) {00.5, 1, 0.1),, (1, 0.5, 0.1)}, where indicates the standard deviation of the Gaussian vector representing conjunctions of components. a, We compare the additivity of individual models to the additivity of the model behavior averaged across 100 randomly sampled representations. While individual models may be severely non-additive, their average hehavior consistently highly additive, empirically confirming models are trained on transitive equivalence, they also systematically exhibit chance performance, they still, average, constrained to be conjunction additive. We then estimated the slope of the model trained on symbolic addition for each random instance of a representation against corresponding representation's 's S(1 2). The individual slope estimates are depicted by the small translucent dots, whereas the average across all random instances is depicted by the larger points. Finally, our theoretical predictions in the exactly compositionally structured case are depicted by the lines. The average model behaviors are well described by our theory. d. We plot the distribution of generalization accuracies on context dependence across different model seeds, the two considered representations, and for CD-3 and CD-2. On CD-3, the representation with a higher salience for individual components (rep. 1, (01, F2 03) (0.5, 1, 0.1) performs systematically below chance, whereas the representation with higher salience for conjunctions of two components (rep. 2, (a), 02, 03) = (1, 0.5, 0.1)) generalizes above chance. In contrast, on CD-2, both representation exhibit better-thann-chanc-eccurrg
proposition. b, As result, when these
23

---

Published as a conference paper at ICLR 2025
B REPRESENTAAIINALL SALIENCE: A METRIC FOR COMPOSITIONALLY STRUCTURED REPRESENTATIONS
B.I DEFINITION
Below we formally define representational salience. To do so, denote the similarity between two trials 2, z' by (im(O(z,=')) == =zz,='). Note that this is well-defined for compositionally structured representations, as K (2, 2²) is identical for all pairs of trials with the same O 2'). We then define:
Definition B.1. For generalized compositionally structured representation with kernel K and conjunction C [I,..., C}, we recursively define
(0) = K(),, ((J) := SJm(J) Err S(J) Eoas Ol...,y) S(J)
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 (k;; C) SJ). where k : |/]-
To illustrate how salience would be computed in practice, we consider an example representation X E IRxxd This representation gives rise to a kernel K XX" E R We can also understand the trial-by-trial similarity in terms of the components it is overlapping in - denoting the set of all subsets of (I..... C} by J, we denote this by O E Juxn In particular, O = {1..... CJ. For example, if data points and overlap in the third component, O12 = (3). Sim(J) then defined as the entries Kg where O₁ = J. Note that in a compositionally structured representation, whenever Og, = J, Kg takes on the same value, but more generally, we can define Sim(J) by taking the average similarity. We can then define the unnormalized salience 3 by recursively computing it from (J) using Eq. (13). We then normalize the salience get final estimate.
B.2 WHY IS REPRESENTATIONAL. SALIENCE A USEFUL METRIC?
Intuitively, the representational salience captures the unique contribution of a population representing a particular conjunction (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 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 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 S.I 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 is again best seen as separate from the representational geometry.
The baseline activity, on the other hand, may determine how easily an intercept 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. irrelevant.
we again find that the baseline activity is entirely
24

---

Published as a conference paper at ICLR 2025
a
Step function
ReLU
Leaky relu
Rect. quad.
Gaussian
Overlap
1.00
0.2
0.75
0.1
0.50
0.0
0.25
Overlap 2
0.00
1.00
Salience of first comp. 0.5
0.1
Nonlinearity
Salience
0.75
Sallence
0.0
Step fun.
0.50
Overlap 3
Leaky ReL
ReLU
0.25
0.3
Rect. quad.
0.2
0.2
Gaussian
0.00
0.1
0.1
1.00
0.0
0.75
Overtap
0.50
12
1.0
0.25
0.5
0.00
0.0
20
10
20
20 Layers
10
Layers
Figure 7: Extended analysis of overlap salience in random neural networks. a. Salience of first component (1), the second component (2), and their conjunction (12), where vary the two components' saliences the input. b, Salience for inputs with four components.
B.4 EXTENDED REPRESENTATIONAL ANALYSIS
We computed the saliences by iteratively computing the representational similarities using the kernels derived in prior work (Cho & Saul 2009 Tsuchida et al. 2018 2019 Han et al., 2022). In Fig. 7p.
we plot the different saliences for an input with four components. Now the salience of overlap and both first increase and then decrease and, just like for inputs with three components (Fig. Gaussian and rectified quadratic nonlinearity yields particularly high salience for these intermediate conjunctions. Notably, they appear 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 example of a generalized compositionally structured representation. Here we assume that the different input components have different magnitudes. In particular, we consider disentangled representation whose first component has salience between whose second component accordingly has a salience s (Fig. 7b). As the random weight neural network becomes deeper, the more salient component (in this dominates the representation. While the salience the full conjunction still eventually converges one for most nonlinearities. takes longer to do for less balanced input representation. Further, for a Gaussian nonlinearity, an imbalanced representation actually decreases the limit salience the representation appears to be converging 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.
[0.1, 0.5] and
component 2) increasingly
B.5 SALIENCE IN VERY DEEP RELU NETWORKS
Proposition B.2. For random neural network with a (leaky) ReLU nonlinearity, as - oc, S(k; C) 0.for k < C and S(C;C)
25

---

Published as a conference paper at ICLR 2025
Proof. Note that the proof is a minor extension of Lemma S1.3 in Lippl et al. (0024)
We present it
here in a self-contained manner. We consider a nonlinearity
(u) == A Amin u, 0) + max (u, 0), A E [0,
(14)
By prior work (Cho & Saul
2009
Tsuchida et al. 2018
2019
Han et al. 2022)
Ev ((w") 10 (z)) no (2))) = o²| "llll
(2)(()))
(15)
where
k(u) (1 (1=A) A)2 (V1- u2- (m cos cos-coos))))) (w)))) + Au,
(16)
2x
a² is the variance of the sampled weights, and = h
This means that for any two inputs that have a certain similarity u, their similarity in the L-th layer is given by k(")u) where k=(.) denotes the L-times application of kt Let distinct trials in the input have a similarity of Kig and let identical trials have a similarity of kg. Any set of trials with overlapping components will have similarity K. Ka <, Kiz- We denote their corresponding similarity in the
L-th layer by k2 (L) (E)
Rid (,) Our goal is now to show that
K(L)
(L)
lim g(4) = O, g(L)
0.
(17)
L))
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.
(L) 1+42 Notably, all inputs have the same magnitude implies that k3 [L+1] = x2 k(1) o² O²M;
15
and therefore have the same magnitude through all layers; this is given by V (L). We can therefore denote
(((+1) = 02k( (1k (m(())/((())
(18)
Thus,
(L+1)) k(((1)/n/) - k((r)) /n((1))
(19)
k(1) k(k() (1) (2)
We thus define new normalized variables R(L) = L1) //1 (1) (:(() = Rid
(1) (1) i.e.
s (L) (1)) - kd
(20)
1 1 -
and therefore
R(() = (1 - R/d (L)) )2()) + Rid
(21)
Note that R(L+1) k(R(())//k(() and Rd (L+1) k/ 1 (L) /k((1). We thus define
k(uu = k(u)
k(1) u + P ((V1 u² cos - (u)u), p:
(1 11-Ap A)2
(22)
(1 + A)2
Note that
(u(u) = 1+ P
3 cos (u)) + vI n
cos (w).
(23)
Note that k11) 1 and as for all S 1, 1u) < 1, this is the only fixed point and ((()), R.(()
co. We can therefore define
(1+1) k k(11- ((6)) ( + R
(L)
(24)
(I)
kdd
26

---

Published as a conference paper at ICLR 2025
We now determine the fixed mapping this mapping assuming that ( is fixed some value i.e:
[(8 k((1 - d)s + d) k(d)
(25)
1-((d)
is fixed point. Further,
0f(s. d)
(1 d) ((1 d)s + d)
(1- (1-d)(1 P cos 1(1 d)s + d)
x 1 d [(v1 d2 cos cos-
(26)
Ös
k(d)
We now prove that this for 0 < 8 S 1/2 this derivative is smaller than 1. Specifically,
(1 - d)( (1 - cos ((1
+ d)s+
(27)
d " <(v -coos
cos - (d)d) + fr(s,d).
x
where the residual is given by
r(s,d) == (d - 1) cos -lac-oo--s ( d)s dd / 1 d cos
(28)
We now need to prove that r(s, d) < 0. Note that r(s, d) monotonically increasing s and therefore
r(s,d) S d) = (d - 1) cos - + + (d) + v
dos -ocoos--0 < O,
(29)
where we infer the latter inequality by visual inspection of the plot of this function.
C DSPRITES REPRESENTATIONS
To investigate whether our theory can describe compositional generalization in practically used disentangled models, we considered six different model architectures considered in Locatello et al. (20T9) and trained the DSprites dataset, important benchmark for disentangles representation learning. This paper considers fifty random seeds for each model and further considers six different possible hyperparameters per architectures, resulting total of 1,800 models. In our analysis, we only analyze differences between architectures, pooling across all hyperparameter choices.
C.I
TASK SETUP
DSprites consists of small black-and-white shapes and has five different underlying components: shape (three categories: hearts, ovals, and squares), size, x-position, y-position, and rotation. We consistently consider the largest possible size and hold the rotation fixed at zero. While x- and y-position can each take 32 possible values, we only consider four different categories for each. Importantly, this still a highly non non-compositionally structured representation: not only do the disentangled representation learning methods often fail to discover the underlying factors of variation; the model also likely represents X- and y-positions that are closer to each other, as more similar, violating our compositionally structured assumption. These representations therefore present particularly challenging test of our framework.
For symbolic addition and transitive equivalence, we consider x- and y-position as the two components. For each task instance, we randomly determine which position takes on which component's 's role. In total, we consider 50 randomly sampled task instance for each of the 1,800 models. For context dependence, we subsample two shapes and assume that these shapes provide the context cue. We then consider x- and y-position feature 1 and feature 2. While the context dependence considered the main text had six possible feature values for each feature, we now only consider four. As a result, we only consider two different datasets: CD-2, which leaves out all trials where feature indicates category 2 and feature 2 indicates category 1; and CD-1 which only leaves out one conjunction of features. Put diffcrently, on given trial, the task could for example look as follows: if we see heart shape, the model should output whether this object in certain x-position; if we see square shape, the model should output whether this object is in a certain y y-position. While the model has seen all x- and y- y-positions individually, it has not seen each combination of and y-positions.
Finally, we consider either direct linear readout from the disentangled representation or an initial transformation by one-hidden-layer ReL.U neural network with random weights.
27

---

Published as a conference paper at ICLR 2025
arnosled voe
bota, Ir_ voc
bota uSc
Count
Addition
Addition (R (ReLU)
dip. v
dip vse
factor vse
CD (ReLU)
Additivity
1000
750
Varfance ratio
0.8
Count
Train
0.7
250
0.4
0.6
0.8
1.0
annealed,
beta, Ir, sae
bata. sae
anp vae.
dlp sae it
factor,
Accuracy
Model
CD-2
CD-1
Generalizationen entr
1000
Accuracy
0.50
100
identity
0.45
0.0
0.3
0.6
anneated vat
beta 200
betel Jeat
dip, vist
tactor vae dip vae.
arnealed, see.
betth betts voan
taclor. val dip, sae, ein. use
S(1:2)
Model
Figure 8: Conjunction-wis wise additivity in empirical disentangled models. Additivity across the different model architectures and four different task settings. All the model behaviors are gener- ally highly additive. b, Distribution of accuracies on transitive equivalence when averaged across different component roles. c, Variance ratio, capturing the ratio between the deviation between the representational similarity matrix and its compositionally structured approximation and the general variance of the representational similarity matrix. The numbers indicate that all disentangled models discover some compositional strueture in their representation, but still deviate substantially from a compositionally structured representation. d, Generalization error on symbolic addition plotted against the estimated S(1; 2). Average accuracy two versions of context dependence with total of four features: CD-2 which now leaves out an entire orthant, and CD-1, which only leaves out single data point. Again, models generally perform below chance on CD-2 but above chance on CD-1, though performance is generally really low.
28

---

Published as a conference paper at ICLR 2025
C.2 THE MODELS ARE WELL DESCRIBED BY CONJUNCTION- WISE ADDITIVE COMPUTATION
We first investigated whether the model predictions on the test set were well characterized by conjunction-wist wise additive computation (see Appendix D.3), averaging this model behavior across the fifty random task instances. We found that they were generally well captured, though they were certainly not perfectly conjunction-wis additive (Fig. [a). Further, none of these models were able to systematically generalize on transitive equivalence (Fig. Sp). This indicates that conjunction-win additivity may characterize the generalization class of these highly non-compositionally structured representations as well at least when averaged across task instances.
C.3 THE REPRESENTATIONS ARE PARTIALLY COMPOSITIONALIA STRUCTURED
We next investigated whether these representations exhibit compositional structure according to our definition. To determine this, we computed their representational similarity matrix and computed the average similarity for cach set of overlaps. This instantiates the compositionally structured representational similarity matrix that most closely described the empirical representational similarity. We then determined the average squared deviation from this matrix, o².. comparing it to the overall variance of this matrix, oaar. Overall, the variance ratio, o o paap characterizes the degree to which the given representation is compositionally structured. In a fully non-compositionally structured representation, the variance ratio will be roughly one, whereas in fully compositionally structured representation, it will be zero. For the disentangled representation learning models, we found that this variance ratio took on value between 0.5 and 0.9 (Fig. (B:). Thus, the models' representation partially captured compositional structure, but also contained a lot of non-compositionall structure.
C.4 THE NON-COMPOSITIONAL REPRESENTATIONAL STRUCTURE SUBSTANTIALLY IMPACTS MODEL BEHAVIOR
Finally, we tested whether our representational geometry analysis in Section[ to the DSprites representations. We first estimated their salience S(1; 2) by computing the average representational similarity for each overlap and then computing the salience using Eq. (3) Proposition [5.1 would predict that the generalization error should decrease with increasing 2) However, we do not observe such a trend (Fig. (d) This indicates that our representational geometry analysis does not apply to the DSprites representations, due to the way in which they violate the compositional structure assumption.
Finally, we determined generalization accuracy CD-2 and CD-1. We found that most models performed quite poorly, perhaps owing to the fact that shape is barely represented in these models. Nevertheless, we found that most models performed systematically below chance for CD-2 but systematically above chance for CD-1. Our analysis of context dependence in compositionally structured representations suggests that this may be because these models exploit a context-driven shortcut on CD-2 but not CD-1.
Overall, our analysis therefore paints nuanced picture of the applicability of our theory practical disentangled representations. Our findings suggest that these models may still be well approximated by conjunction-wisg additive computations and that this generalization class may therefore shed light on fundamental limits to the generalization of linear readout models. At the same time, to understand how these models generalize on conjunction-wise additive tasks, taking into account the specific ways in which they violate the compositional structure assumption is likely important.
D DETAILED METHODS
D.I MODELS
Kernel model. We fit the kernel models by hand-specifying the kernel and fitting either a support vector regression classification using scikit-learn (Pedregosa et al.) 2011). Note that this is equivalent to using a feature basis with the same resulting similarities. However, -peciffyn these similarities enabled us to easily explore the full range of possible representations.
29

---

Published as a conference paper at ICLR 2025
Rich and lazy ReLU networks. All networks were trained with Pytorch and Pytorch Lightning Paszke et al. (2019). We consider ReLU networks with one hidden layer and = 1000 units. We initialize by a 2/H,, considering a E [10-6, 1]. In particular, when reporting results on rich networks (without further specification), we assume o = 10-6. When reporting results on lazy network, assume 1.
Compositional MNIST/CIFAR-IU We create a compositional version of MNIST and CIFAR-IO 10 by concatenating multiple images along different channels. For example, the input to the MNIST version of the symbolic addition task had two channels, each containing one digit whereas the CIFAR- 10 version of the symbolic addition task had six channels, three for each digit. We further varied the distance between the concatenated images either presenting them all on top of each other or presenting them offset by certain number of pixels. Each image category corresponded to certain component, where its role as ranodmly sampled for each task instance. The output was still given by single scalar: the total magnitude for symbolic addition and the two categories for context dependence and transitive equivalence.
Convolutional neural networks. We considered networks with four convolutional layers (kernel size 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 al.) 2015).
We trained these networks with SGD using a learning rate of 10 and momentum of 0.9.
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 3 for 100 epochs.
Vision Transformers. Finally, we trained 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 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 random crop.
D.2
REPRODUCIBILITY
The code required to reproduce all experiments can be found under stfipppp/ccmmpaittooollgeeeeeele zatiini
com/
D.3 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² defines the "additivity" of the network behavior (i.e. R² indicates full conjunction-wise additivity). Furthermore, we can use the inferred values assigned to these different conjunctions to compare kernel models, leature-learnng networks, and vision networks. Note that for the vision networks, we first average the model predictions across all different images instantiating 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, ( First, we found that the predictivity on the test set was indeed generally very high. Second, we found that it was substantially higher than the training and test set taken together.
30

---

Published as a conference paper at ICLR 2025
Cantext Dependence
Addition
1.000
1.0
0.995
0.9
0.990
0.8
test
0.985
0.980
0.7
0.975
Convnet (MNIST) (CIFAR) (CIFAR)
ResNet
viT
Convnet (MNIST) (CIFAR) (CIFAR)
ResNet
viT
Figure 9: ni2 of the conjunction-wise additive predictor on the test set as well as on both the training and test set.
E COMPOSITIONAL TASK SPACE
E.1 SYMBOLIC ADDITION
E.1.1 PROOF OF PROPOSITION 5.1
Proposition 5.1. Consider inputs 21, E [eulbev V C R, with associated values v. We assume that the training set contains all pairs such that at least one component is ze E [e] W C v and that the average value in both V and W is zero. Then, model behavior on the test set is given by
f((r), [02]) m(vi + 02),
8022) 2)-22) p:= [W]
(3)
Proof. We split up the training data into
I(') = [[u] w W)?
(30)
and
7(2) = U I(l.w) U
(31)
WEW
(1,m) [[ww), [o]] e W\) I(2,)) ((v), [w]]lo V W}.
(32)
We denote the dual coefficient associated with each training point ([t), (i)) by a, E R. Note that the problem is symmetric and therefore we know that aij- aji. We define few summed coefficients:
b
Σ awwn
D =
Σ
awwn
Cw
Σ
Oww':
(33)
WEW
VEV(W
w'EW
Σ BEV(W
b
Σ WEW
bws
Σ
Cw
(34)
wEW
Note that the sum over all dual coefficients is given by 2b + Let petp:= = [W] and q == | W We denote by Ki the similarity between inputs overlapping in components. Then, setting 82 K2 Ko and 8n : 161 Kg. the set of dual equations given by
([w), [w]]) ()) No (26 + c) + 81 (b. + byr car + cw') (82 281)a = w', (35)
([w), [v]) E ((..)) (2b + c) + 51 + + + cw) + (6z - 25g (a))) = w + U.
(36)
(Note that the equation corresponding to ([v], [w]) is equivalent due to the problem's symmetry.) The prediction is given by
[(m1), = Ko (2b + c) + 8n (br, + brz))
(37)
We now sum 36 over (setting w = Σnew w):
W + p
p2u bb + c) + põ b, + 81 + + (6 266 281)bb ((p 2) b2 (2pro + 51)b (pro 8n )c
(38)
31

---

Published as a conference paper at ICLR 2025
4
-2,2 2
5
-5
Prodiction
5
2 Xxpda
plit
0-
Training Compositional
-5
5
E: CAndda
0-
-5
-5
0
-5
-5
Ground truth
Figure 10: Model prediction plotted against ground truth for different training sets and depths.
Thus,
5ip
b, (p-2)01 + 02
v + 8 (2pko + 8,)6 (pro + dc)...
(39)
Thus, setting
81p
m = (p 2) + 02¹
d: 26, (w (2pro + 6136 (pNo + 51)c) - <2 + cc,
(40)
we can write
f(vn), (v2)) = m(v1 + 02) + d.
(41)
To simplify d, we sum
35 over all w, w/:
2p
(2b c) + 2po (b + c) (62 281)c
(42)
2p(pro + +8)6 - (p²No + 2(p 1)61 + 82)c.
We further sum
38 over all v. setting = == Ever 2:
((p 1pp+g 9 2) + 52 + 2p + 4ppro + 8 c = qu + pc.
(43)
We compute and from this system of equations and plug into d.
Finally, w = immediately implies that = c 0 and therefore
E.1.2 BEHAVIOR DEEP RELU NETWORKS
Next, we examined behavior deep ReLU networks with varying depth (Fig. TOP. On the extrapolation task (W = {0)), these networks also had compressed model predictions 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 (W = { [-4,4]). For W (-2, 2}. they perfectly generalized on the interpolation portion, but not the extrapolation portion.
E. BEHAVIOR OF VISION MODELS
We trained the Convnets on MNIST using seven different training sets W: [0]]. [1-4], [4]].
[i-2], [2]]. [[-4], [4]]. [[-1], [[], (33, [3], [4]] [1-,), 2] This allowed us vary both the size of the training set and whether it involved only interpolation lation. We trained these networks for 100 epochs on 20,000 samples. We trained the ResNets and ViT's on CIFAR-10 10 using the first three training sets listed above. We trained the ResNets for 100
also extrapo-
32

---

Published as a conference paper at ICLR 2025
4,4
2,22
4,0,4
-1,,1
4,3,3,4
-,112
Model prediction
5
10
20
0 5
5
5
505
-5
5
-0
5
5
-5.0
Split
Ground truth
Training
c
In-distibution
222
Compositonal
Model prediction
Model prediction
5
9t
9t
22
ZE
-5
0
-5
0
-5
-5
-5
-5 0
Ground truth
Ground truth
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.
Figure 11:
Convnel MNIST!
ResNet (CIFAR)
VIT (CIFAR)
Convnel (MNIST]
ResNet (CIFAR)
VIT (CIFAR)
split
4000
5000
4000
2000
2000
Training
In-distiiutton Compositional
MSE
1000
2000
2500
MSE
1000
2000
2500
2-2222
0
Extrapolation Interpolation
10
20
20
1234
2
Distance
Figure 12: a, Mean squared enror as a function of distance. b, Mean squared error function of training set size p (different dots corresponding to interpolation versus extrapolation.
epochs and the ViTs for 200 epochs, training all networks on 40,000 samples. Our findings these experiments are summarized in Section 6 Further, Fig. 11 depicts, for each training set, the average prediction for each combination of components. We can see that the ConvNet predictions highly linearly correlated with the ground truth. The ResNet and VIT predictions are also linearly correlated, but exhibit slightly noisier relationship.
Additionally, we also plot the mean squared error of the networks on the different training sets (Fig. 12p. This provides more conventional (but harder to interpret) measure of performance com- pared to the slope depicted in Fig. 5 We again see that the mean squared enror on the compositional generalization set decreasing with increasing distance (Fig. 12a). Further, it decreasing with increasing training set size (Fig. [2] though note that the differences in the scales of the general- ization set for different sets W renders it harder to directly to compare these values. contrast, the slopes described in the main text more easily comparable.
33

---

Published as a conference paper at ICLR 2025
0.30
1.0
Slope
0.24
after training before training
0.5
0.18
0.0
10
20
0.00
0.25
0.50
Dist
S(1:2)
Figure 13: a, 21: in the convolutional neural network's neural tangent kernel, before and after being trained on symbolic addition with W = {0}. b, The estimated slope for each model instance plotted against 2); While increased 5(1;2) generally yields larger slope (as predicted by our theory), the relationship between 2): and the slope does not follow the exact quantitative relationship predicted by our theory.
Distance:
Distance:20
MSE
0
1
1
2
Depth
Mean squared error on the compositional generalization set for different depths of the fully connected network at the end of the convolutional neural network architecture.
Figure 14:
Overall, our analysis indicates that our theory provides several valuable qualitative insights into the behavior of deep neural network models. Importantly, however, we are not able to provide quantitative bounds at the moment. demonstrate this, we computed the salience S(1; of the neural tangent kernel of the convolutional neural networks before and after being trained on the MNIST version of symbolic addition with W = {0} (Fig. 13)). Importantly, S(1: 2) changed substantially during not trained in the kernel regime. As such, our theory does not apply exactly. To see whether it provided appropriate quantitative bounds, we then estimated the slope of each model instance on the compositional generalization dataset and plotted it against S(1;2) 2) of the neural tangent kernel at the beginning of training. We found that higher S1;;2) generally resulted larger slope, as predicted by our theory. However, the relationship between S(1; 2) and slope did not adhere exactly to the quantitative predictions made by our theory. This indicates that while our theory can shed light on certain qualitative behaviors, still leaves certain generalization behaviors in deep neural networks unclear.
training. indicating that these networks
Finally, our analysis in Section 5. suggests that deeper models should yield more conjunctive repre- sentations, and therefore exhibit worse generalization on symbolic addition. To test this prediction, we varied the number of fully connected layers in the convolutional neural network and trained these networks on the symbolic addition task with the training set W = {0]. We found that deeper networks indeed generalized worse (Fig. 14p
E.2 CONTEXT DEPENDENCE
E.2.1 GENERAL TASK DEFINITION
We consider inputs with three components, (Re. Z/2). We assume that 2e E C1 U where Ci is the set of possible contexts under which Zy1 is relevant and C2 is the set of possible contexts under which 2y2 is relevant. We further assume that there are decision functions d1 (2y1), (2(2)2) E 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
E 211, (d1(2)1 (d2(212)
if 2 C1, if Zco C2.
(44)
Note that in the main text, we consider C = (1). C2 = {2). and six possible values for 211, 2y2. where the decision function maps three onto 1 and three onto -1
34

---

Published as a conference paper at ICLR 2025
CD-3
CD-2
CD-1
conj.
Conj. type
Wrong conj.
Depth
Sensory feat
Context only
Memorization
Value
Figure 15: Inferred values for different conjunctive groups on context dependence.
E.2.2 NOVEL STIMULUS COMPOSITIONS ARE CONJUNCTION-WISS ADDITIVE
the test consists novel combinations of stimuli, this a conjunction-winn additive computation. Namely, suppose that for all test inputs (Zco, ff1; zf2), the two features have never been observed in conjunction, but both (Zen: 2f1) and (Zea: 2f2) have been. (This includes the case considered in the main text.) In this case, we can define functions f12 and f13 to implement the appropriate mapping:
(21(2)1 S12(F00;2 = {0
if 200 E C1,
Sia(zoon 212) fo
if 2co E C1,
(45)
if 2co C22,
d2(2222
if tco E C2
[(ea, 2f2) f12(200; 2f1) f13( 2f2).
(46)
E.2.3 NOVEL RULE COMPOSITIONS ARE NOT CONJUNCTION- WISE ADDITIVE
We could also imagine alternative generalization rule in task where there multiple components indicating the same context: C₁ = {co,, ] and C2 {cog, co We then leave out certain features with certain contexts. For example, suppose 2/2 in conjunction with Zço E (co2, co In principle, if the model understood that 2.o = cO1, CO2 (and Zeo CO3, c04 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 Zco co1, cog. However, the conjunction- wise additive mapping depends on having observed each context in conjunction with each feature and this task is therefore non-additive.
had never seen values for 2f1 and
E.2.4
COFFFICIENT GROUPS
In Fig.
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 2 CO1 and 2y1 and between A.. c02 and zz2-
Wrong conj.: This is the incorrect conjunction between context and feature, i.e. between Zea = co2 and z and between Zeo = co2 and zf1-
Sensory feat.: This is any conjunction involving sensory features, i.e. Zf2, (2)1;
Context only: This is the component Zeo by itself.
Memorization: This is the full conjunction of all three components (Zeor 2f1 2y2)-
We then compute the average absolute magnitude within each of these groups in order determine their overall relevance to model behavior.
E.2.5 FEATURE-LEARNING RELU NETWORKS
We find that Teature-learning ReLU networks generalize consistently on CD-I and CD-2 but not CD-3. They also perfectly conjunction-wise additive and fail due to context shorteut (Fig. 15
35

---

Published as a conference paper at ICLR 2025
b
CD-1
CD-2
CD-3
1.0
Generalization
G
Additivity
Task variant
ACC.
0.5
Training set
0.975
CD-3
In dn-distriutioon
CD -
om pal
CD-1 D
0.0
0.950
20 0
20
Dist.
Dist.
CD-3
CD-2
CD-1
conj.
Conj, type
Distance
W Wrong conj.
Sensory feat-
Context only
Memorization
Rel. magnitude
Figure 16: Performance of convolutional neural networks trained 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.
E.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-/ and CD-2, but not CD-3 (Fig. 16p. 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 (R22 > 0.95), but became worse for lower distance (Fig. 16p). 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. 162)
E.3 INVARIANCE AND PARTIAL EXPOSURE
We consider invariance and partial exposure as simple case studies for the memorization leak and shorteut bias. In both cases, the input consists of two components and the mapping only depends see
on the first (Fig. 17p). 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. 2022
Chan al. 2022).
To understand the impact of different representational saliences, we consider the generalization margin m := yú on the test set, where y is the ground-truth label and ý 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 mathematical formula for the margins as function of 2); Below we first describe its implications and then how we derived this.
Invariance suffers from memorization leak. On invariance, find that the model's test $(1:2)
margin is expressed as m I-1(1:3 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 decreased margin (Fig. 17p).
36

---

Published as a conference paper at ICLR 2025
b
Partial exposure
Invariance
Class Class
Item 2
Margin
Invariance Partial exposure
Train Test
0.0
0.5
Item
S(1:2)
Figure 17: a, Schema for invariance and partial exposure. b, Generalization margin for the two tasks.
Shortcut distortion. On the partial exposure task, if the model used item solve the task, 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 this decreases the f--norm of the readout weights. As result, the test margin for the partial exposure task decreases even more strongly as a function (11
25(1:2)2 2S(2)) (where assume that the similarity between identical trials one and the similarity between distinct trials zero) (Fig.
m
Derivations. We analytically compute the kernel models' test set prediction on the invariance task. The training set given by ((-1,-1), (-1, and its kernel therefore
K
R2
161
(47)
Ri
K2
where R2 is the similarity between identical trials and Kn is the similarity between overlapping trials. Hence, the dual coefficients are given by
a a= K (1)
K2 -K1
(+
+ (- kn))
(48)
R2 1²
K2
x²
The test set is given by ((1, (1), (1, 1)) and its kernel with respect to the training set is therefore
K
K1
(49)
No
161
where Ko is the similarity between distinct trials. Hence the test set predictions are given by
(k2 + Kn KI) ko)
ý Ka-
(50)
122 n2
( + k1) Ko).
As the ground truth labels are y = {1, 11.. the margin m yÿ is identical for both test set points:
(R2 N1 (k² -Ro) K1 Ki
(K2 ((;
S(1:2)
m
R2 x²
K2 Ki
(K2 no) - (x1 -o)) 1- (-5(1;2)
(51)
For partial exposure, the training set given by {(-1, 11, (-1, (1,- and its kernel is
therefore
R22
Ri
K1
K
Ri
R2
fig
(52)
R1
fig
f22
The test set is given by ((1,1) 1)) and the test set kernel is therefore
K
(Ro
R1
Ki)
(53)
The margin is therefore given by
(1]
m = yy = - KK-I
(54)
We solve this equation for the special case where Kig = 0 and 1 using Mathematica and find that
2);
m = 21:
(55)
37

---

Published as a conference paper at ICLR 2025
b Lazy
d
1.0
0.01
0.005
Item
1.0
Split
Acc.
Train
Sign
weights
Acc.
Training set mnddisrrbutton Compositional
0.5
Test
Pos.
Eq.
Rich
0.01
Neg.
-0.005
Not eq.
0.5
10
1000
Train
-0.01
0.01
-0.005
0.005
20
Epoch
Test
Dist.
Figure 18: Feature learning enables generalization 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 ConvNet trained on an MNIST version of transitive equivalence.
E.4 OTHER MATHEMATICAL OPERATIONS
We could consider mathematical operations other than addition as well, considering unobserved assigned values o1 (=,) and (22) together with some composition function C(ei (=)), (22))). This task will only be additive the composition function is additive (e.g. it is subtraction). If is, e.g. multiplication, division, exponentiation, the task will be non-additive.
E.5 LOGICAL OPERATIONS
In this task, inputs with two components are presented. Each component 2e has unobserved truth value T= associated with it and the target is some logical operation over these two truth values, for example AND: T(z1) A (22).. 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, ... this is 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.
E.6 TRANSITIVE ORDERING
Transitive ordering is popular task in cognitive science (often called transitive inference, McGonigle Chalmers (1977). ) Here the subject is presented with two items 21, 22 drawn from an unobserved hierarchy It should then categorize whether 21 22 22 > 21. Crucially, this task can be solved by assigning rank r(z.) to each item and computing the response as f(z) = r(21) r(22) Lippl al. (2024). It is therefore additive, in contrast transitive equivalence. This is also the case if we assume that there are multiple such hierarchies (e.g. a1 > >... as and b > ...,, bz). In this case, the model would generalize comparisons between these different hierarchies well.
F A FEATURE-LEARNING MECHANISM FOR NON-ADDITIVE COMPOSITIONAL GENERALIZATION
We proved above that compositionally structured kernel models do not generalize on non-additive tasks, including transitive equivalence. To if feature learning can overcome this limitation, trained ReLU networks through backpropagation uncorrelated input. By varying the initial weight magnitude, we either trained these networks in the kernel/lazy regime or the Saature-earming/ricll regime. Notably, when trained on symbolic addition and context dependence, the rich networks were well-described by a conjunction-we (Figs. 10 and 15). On transitive equivalence, however, while the kernel-regime models failed to generalize (as predicted by our theory), the rich networks generalized correctly (Fig (8h).
transitive equivalence, using disentangled and
additive model
To explain why this is the case, leveraged the insight that rich neural networks are biased to learning weights with a low overall fz-norm (Lyu & Li (2020); Chizat & Bach (2020); cf. Vardi & Shamir (2021)). I). In particular, one-hidden- maaeiidde-- ReLU network tends to learn sparse set of features (Savarese et al. (2019); Chizat & Bach 2020). Transitive equivalence consists of multiple
overlapping equality relations (e.g. A =
F.). Notably, ReL.U networks such XOR-type
38

---

Published as a conference paper at ICLR 2025
problem by specializing unit to each conjunction (Brutzkus & Globerson (2019); Saxe al. (2022); Xu et al. (2023); Fig. [8)). Further, their sparse inductive bias incentivizes ReLU networks to 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, theoretical argument is corroborated by empirical simulations: each network unit
has identical weights for equivalent items (Fig. (8p).
Thus, rich networks' capacity for abstraction gives rise am 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 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 distance of zero, the network did not generalize compositionally at all. However, with increasing distance, the network started to improve its compositional generalization (Fig. [8d), demonstrating that a convolutional network can benefit from this rich compositional motif.
39

---

Published as a conference paper at ICLR 2025
Behavior on symbolic addition Proposition 5.2
Prediction
oooe (m)
train
-4
test
-4 0
0.0
0.5
Ground truth
S(1; 2)
Compositional generalization is distorted by proportional factor
This factor increases
This factor
increases with larger training sets
for lower conjunctivity
Convnet (MNIST)
Convnet
(MNIST)
Split
Prediction
5
Slope
1.00
Slope
1.0
Training
0.75
in-distribution Compositional
0.6
Interpolation Extrapolation
5
Ground truth
Distance
Training size (p)
Influence of architecture Proposition 5.1
Behavior on context dependence
Overlap
Overlap
Overlap 3
Sallence
Generali- zation on all
0.5
CD-1,2
0.0
0.0
0.0
CD-1
10
20
10
20
0
10
1/3
none
Layers
S(1: 3)
Deeper networks generalize worse on symbolic addition
CD-3 is much more challenging than CD-2 or CD-1
Convnet (MNIST)
Distance:
Distance: 20
1.0
Split
MSF
6.0
Accuracy
5.5
Training
0.5
In distribution Compositional
2
Depth
CD-3
CD-1
Figure 19: This figure composes the relevant theoretical insights and empirical experiments to illustrate how they speak to each other.
40


Reviews:
[{"review_id": "B7fBvKbms7", "reviewer": "Reviewer_jpBR", "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.", "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?\n\n- Line 269: why would the term f_{12}(z) fall away on the test set? I don't see how this should happen.\n\n- How can a compositionally structured kernel model learn arbitrary training data, as is implied by section 4.3?\n\n- Please add all the details on your empirical evaluation.\n\n- 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.\n\n- 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?\n\nMy 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.", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 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.", "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.\n\n- 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).\n\n- 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.\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vza8q9kMt1", "reviewer": "Reviewer_Gayd", "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.", "questions": "# Questions\n- 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.\n- 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?\n- §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?\n- §5.1 / Fig. 2: Do you have any intuition where the difference between nonlinearities is coming from?\n- §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.\n\n# Minor suggestions\n- LL99: Why call a combination of components a \"conjunction\", and not the more obvious \"composition\"?\n- Fig. 1c: It was not immediately clear which side of the training set line is the training/test set\n- LL256: \"The readout weight ...\" is unclear, is there a word missing? When will it change?\n- L269: should be \"test set\"\n- 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\n- LL354: What is $\\mathcal W$ here? It has not been introduced before", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "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.", "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).\n\nGiven 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lht638U5wN", "reviewer": "Reviewer_kn7u", "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.", "questions": "- In Figure-1b, why [-2]+[1]=1?\n- 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.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 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.", "weaknesses": "### Weakness:\n\nMy 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:\n\n- 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.\n- 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.\n- 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.\n- 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.\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "s58F9a4FEF", "reviewer": "Reviewer_CS3X", "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.", "questions": "1. In Section 3.1 first paragraph, the definition of the disentangled representation is a bit unclear.\n    1. Does each component have a finite set of possible values it can take on (e.g., multiple values for the “color” component)?\n    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)?\n    3. Is $C$ constant across samples? In other words, do the individual components (like color and shape) always apply to each possible input?\n2. In Section 5 and subsections within, why is the approach of looking at the kernel and representational salience referred to as “modular”?\n3. 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}$?\n4. See above weaknesses for other questions.", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The reason for looking at kernel models is very clearly articulated and motivated.\n2. 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).\n3. Contributions and advantages over prior work are very clear (e.g., no assumptions about modularity or linear/additive combinations in the downstream model).\n4. The practical consequences of the main finding, laid out in Section 4.3, are clearly articulated with several simple examples.\n5. 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).\n6. Figures are clear and aesthetic, both when illustrating the framework/tasks and when presenting results.\n    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.", "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.\n2. 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”).\n3. 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.\n    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)$?\n    2. In equation (1), where do the dual coefficients come from? Are they determined from $w$ and $\\phi$ in some way?\n    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.\n4. 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.\n5. 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.\n6. 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.\n    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).\n7. Small point: I recommend citing Schug 2024 http://arxiv.org/abs/2312.15001 at the same place as where you cite Wiedemer 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)