Compositional Generalization from First Principles
Authors: Thaddäus Wiedemer
Prasanna Mayilvahanan
Matthias Bethge
Wieland Brendel
Venue: NeurIPS 2023 poster (2023)
Keywords: compositional generalization
compositionality
generalization
combinatorial generalization
out-of-distribution
out-of-domain
identifiability
disentanglement
object-centric learning
DSprites
TL;DR: We derive sufficient conditions on the data generating process and model architecture under which compositional generalization provably occurs.

Abstract: Leveraging the compositional nature of our world to expedite learning and facilitate generalization is a hallmark of human perception. In machine learning, on the other hand, achieving compositional generalization has proven to be an elusive goal, even for models with explicit compositional priors. To get a better handle on compositional generalization, we here approach it from the bottom up: Inspired by identifiable representation learning, we investigate compositionality as a property of the data-generating process rather than the data itself. This reformulation enables us to derive mild conditions on only the support of the training distribution and the model architecture, which are sufficient for compositional generalization. We further demonstrate how our theoretical framework applies to real-world scenarios and validate our findings empirically. Our results set the stage for a principled theoretical study of compositional generalization.

Compositional Generalization from First Principles
Thaddäus Wiedemer 1,2 1,2,3
Prasanna Mayilvahanan 1,2,3
Matthias Bethge
Wieland Brende12.31
University of Tübingen Tübingen Al Center
MMax-Planck-Instiinn for Intelligent Systems, Tübingen
{thaddaeus wiedemer, prasanna prasama..aaylLvvhannaaa.n -
Abstract
Leveraging the compositional nature of our world expedite learning and facilitate generalization is hallmark of human perception. In machine learning, on the other hand, achieving compositional generalization has proven be an elusive goal, even for models with explicit compositional priors. To get a better handle on compositional generalization, we here approach from the bottom up: Inspired by identifiable representation learning, we investigate compositionality of the data-generating process rather than the data itself. This reformulation enables us to derive mild conditions on only the support of the training distribution and the model architecture, which are sufficient compositional generalization. We further demonstrate how our theoretical framework applies to real-world scenarios and validate our findings empirically. Our results set the stage for principled theoretical study of compositional generalization.
property
1 Introduction
Systematic compositionality [1] is the remarkable ability to utilize finite set of known components to understand and generate vast array of novel combinations. This ability, referred to by Chomsky [2] as the "infinite use of finite means". is distinguishing feature of human cognition, enabling us to adapt diverse situations and learn from varied experiences.
It's been long-standing idea to leverage the compositional nature of the world for learning. In object-centric learning, models learn to isolate representations of individual objects as building blocks for complex scenes. disentanglement, models aim to infer factors of variation that capture compositional and interpretable aspects of their inputs, for example hair color, skin color, and gender for facial data. So far, however, there is little evidence that these methods deliver substantially increased learning efficacy or generalization capabilities (Schott et al. [3], Montero al. [4]). Across domains and modalities, machine learning models still largely fail to capture and utilize the compositional nature of the training data (Lake and Baroni [5], Loula et al. [6], Keysers et al. [7]).
To exemplify this failure, consider model trained on data set with images of two sprites with varying position, size, shape, and color overlaid on black canvas. Given the latent factors, simple multi-layer neural network can easily learn reconstruct images containing compositions of these sprites that were covered by the training set. However, reconstruction fails for novel compositions even if the individual components have been observed before (see Figure 1). Failure to generalize to
'Equal contribution
'Equal supervision
Code available
37th Conference on Neural Information Processing Systems (NcurIPS 2023), New Orleans.

---

target
reconstruction
shape,
shape,
train
test
train
test
Figure 1: Compositional generalization fails even in regression settings. Left: We train model to reconstruct images containing two sprites given their latent representation (x, y, shape, size, color). Center: In the training (top row and left column), one sprite fixed in its base configuration (orange triangle or red circle), while the other is varied randomly (in this example, sprite varies in position, sprite 2 shape and color). As result, each sample in the test (lower right block) can be expressed as novel composition of known components. Right: While the model able to fit the training data, fails to generalize compositionally the test data.
unseen data in even this simplistic regression setting demonstrates that compositional generalization does not automatically emerge simply because the data is of compositional nature.
We therefore take a step back to formally study compositionality and understand what conditions need be fulfilled for compositional generalization occur. To this end, take inspiration from identifiable representation learning and define a broad class of data generating processes that are compositional and for which we can prove that inference models can generalize to novel compositions that have not been part of the training set. More precisely, our contributions are as follows:
We specify compositional data-generating processes both in terms of their function class and latent distributions (Sections 3.1 and 3.2) such that they cover wide range of assumptions made by existing compositional methods.
We prove set of sufficient conditions under which models trained on the data are able to generalize compositionally (Section 3.3).
We validate our theory in range of synthetic experiments and perform several ablation studies that relate our findings to empirical methods (Section 4).
2
Related Work
Representation learning Disentanglement and identifiable representation learning aim to learn succinet representations that both factorize the data space efficiently and are robust towards distri- butional changes [8-10]. However, the expectation that more compositional representations lead to better out-of-distribution (OOD) generalization has not been met, as demonstrated by Schott al. [3] and Montero et al. [1]]. Although our work does not directly address generalization issues in identi- fiable representation learning, setup is directly inspired by it, and examine data-generating processes similar to [12-14].
Empirical Approaches Many empirical methods use compositional priors and claim improved compositional generalization. The problem has been studied especially closely in language [15- 17], but it remains far from being solved [5-7]. Object-centric learning is another domain in which compositionality plays major role, and many approaches explicitly model the composition of scenes from object-"slots" [18-22]. The slot approach also common vector-symbolic architectures like [23] and [24]. For most of these works, however, compositional generalization

---

is not a focal point, and their actual generalization capability remains to be studied. There are also some architectures like transformers [25], graph neural networks [26], bilinear models [27], or complex-valued autoencoders [28] that have been claimed to exhibit some degree of compositional generalization, but again, principled analysis of their generalization ability is lacking. Our framework can guide the systematic evaluation of these methods. While we use the visual domain as an example
throughout this work, our contributions are not tied to any specific data domain or modality.
Theoretical approaches to OOD generalization The OOD generalization problem for non-linear models where train and test distributions differ in their densities, but not their supports, has been studied extensively, most prominently by Ben-David and Urner [29] and Sugiyama et al. [30]. We refer the reader to Shen et al. [31] for comprchensive overview. In contrast, compositional generalization requires generalizing to distribution with different, possibly non-overlapping support. This problem is more challenging and remains unsolved. Ben-David al. [32] were able show that models can generalize between distributions with a very specific relation, but unclear what realistic distributions fit their constraints. Netanyahu al. [33] also study out-of-support problems theoretically but touch on compositional generalization only as a workaround for general extrapolation. Recently, Dong and Ma [34] took first step towards
applicable theory of compositional generalization to unseen domains, but their results still rely on specific distributions, and they do consider functions with arbitrary (nonlinear) compositions or multi-variate outputs. In contrast, our framework is independent of the exact distributions used for training and testing, and our assumptions on the compositional nature of the data allow us prove generalization in much broader setting.
3 A framework for compositional generalization
Notation [N] denotes the of natural numbers {1, (1,2.-.. ..., N). Vector-valued variables (e-g., a)) and functions (e.g.. f) are written in bold. Id denotes the (vector-valued) identity function. We write the support of a distribution /' supp P. To express that two functions f.g are equal for all points in the support of distribution P, i.e., f(x) g(x) Væ supp P, we write f=p g. Finally, of är denotes the total derivative of a vector-vats veluur- function f by all its inputs x, corresponding to the Jacobian matrix with entries 0f. Bx,"
3.1 Compositionality
Colloquially, the term "compositional data" implies that the data can be broken down into discrete, identifiable components that collectively form the whole. For instance, in natural images, these components might be objects, while in music, they might be individual instruments. As running illustrative example,
will refer simple dataset similar multi-dSprites [21], as shown in Figure 1. Each sample in this dataset is a composition of two basic sprites, each with random position, shape, size, and color, size.
Drawing inspiration from identifiable representation learning, we define compositionality mathemati- cally as a property of the data-genedt generatnnn process. In example, the samples generated by simple rendering engine that initially renders each sprite individually on separate canvases. These canvases then overlaid to produce single image featuring two sprites. More specifically, the rendering engine uses the (latent) properties of sprite one, z = (z1,x, produce image 3 of the first sprite. The same process is repeated with the properties of sprite two,
shape siss z1,ool) to
Z2 = x22.x; 22,y, 22, shupee size 22, ), to create an image 2e of the second sprite. Lastly, the engine combines 31 and 22 create the final overlaid rendering æ of both sprites. Figure demonstrates this process.
In this scenario, the individual sprite renderers carry out the bulk of the work. In contrast, the composition of the two intermediate sprite images Z1, 32 can be formulated as a simple pixel- wise operation (see Appendix B.1 1 for more details). The rendering processes for each sprite independent: adjusting the properties of one sprite will not influence the intermediate image of the other, and vice versa.
We posit that this two-step generative procedure- the (intricate) generation of individual components and their (simple) composition into a single output-iis key characteristic of broad class of
3

---

A
B
C
comporent
component
21 1
component
component
component
22
D
E
F
PK ØK
component
component
component
Figure 2: Compositional representation of function (Definition 1). The compo- nent functions 9px map each component la- tent z to intermediate component rep- resentation Øg- The composition function C' composes all component representations into a final data point æ.
Figure 3: Compositional support (Definition 2). A- D: Distribution P (blue) has compositional support w.r.t. to the entire latent space if has full support over the marginals. E: Gaps in the support require the model to interpolate/extrapoliee eralize compositionally. F: The support of the joint needs to be an open set.
rather than gen-
compositional problems. If we know the composition function, then understanding the basic elements (for example, the individual sprites) enough to grasp all possible combinations of sprites in the dataset. We can thus represent any latent variable model f Z - X, which maps latent vector to a sample æ in the observation space X, two-step generative process.
Definition (Compositional representation). {C,41,.... 1c..,.,..,,44 ,K. 2 2k, _....,, Lx} a com-
positional representation of function
Yz E z f(z) ((). px(2k) and 2 = 2 x ... x Zk,
where z; denotes the canonical projection of onto Z, We refer 9q 2x X'ss as the component functions, to .,...., XK as the (hidden) component spaces, and C: X1 x RK + X the composition function. functioon
Note that its most general form, we do not require the component functions be identical to map to the same component space. The compositional representation of a function f is also not unique. For instance, any f possesses trivial compositional representation given by {ff [d Id..... Id) (for the sake of clarity, we will omit the explicit mention of the latent factorization and component spaces henceforth). We will later establish conditions that must be met by least one compositional representation of f.
Our definition of compositionality naturally aligns with various methods in the fields of identifiability, disentanglement, object centric learning. In the decoder of SlotAttention [18], for example, each component function is spatial broadcast decoder followed by CNN, and the composition function is implemented as alpha compositing. Frady et al. [24] model the component functions element-wise multiplication nigh-dimensional latent codes, which are then composed through straightforward sum. A similar approach is chosen by Vankov and Bowers [23], except that interactions between components are modeled using matrix multiplication.
3.2 Compositional Generalization
The model in Figure was trained supervisedly, i.e., it was trained to reconstruct samples æ given the ground-truth latent factors (21, #2) for each sprite (see Section 4 for more details). We denote this model as f. indicating that meant to replicate the ground-trut truth generating process f of the data. The model f indeed learned to ff almost perfectly on the training distribution P, but failed to do the test distribution Q

---

This failure is surprising because the test samples only contain sprites already encountered during training. The novelty lies solely in the combination these sprites. We would expect any model that comprehends the compositional nature of the dataset to readily generalize to these test samples.
This compositional aspect of the generalization problem manifests itself in the structure of the training and test distribution. In our running example, the model was trained on samples from a distribution P that contained all possible sprites in each slot but only in combination with one base sprite in the other slot (illustrated in Figure 3A). More formally, the support of P can be written as
supp P {(21 E 2 22 22) 2 V =2)
(2)
where #1 denotes the base configuration of sprite (e.g.. the orange triangle and red square in the samples shown in Figure 1).
The test distribution Q a uniform distribution over the full product space 21 22, i.e., contains all possible sprite combinations. More generally. say that generalization problem is compositional the test distribution contains only components that have been present in the training distribution, see Figure 3. This notion can be formalized as follows based on the support of the marginal distributions: Definition (Compositional support), Given two arbitrary distribution P. Q over latents z = (z1, ..... Σk) E Z = Z1 .... x 2k. P has compositional support w.r.t. Q if the support over all marginals Pau, Qz is the same:
supp Pa. = supp Qz. S 2 E [K].
Clearly, compositional generalization requires compositional support. If regions of the test latent space exist for which component is observed, in Figure 3E, we can examine model's generalization capability, but the problem is not compositional. Depending on whether the gap in the support is in the middle of latent's domain towards either end, the generalization problem becomes an interpolation or extrapolation problem instead, which are not the focus of this work.
3.3 Sufficient conditions for compositional generalization
With the above setup, we can now begin examine under what conditions compositional generaliza- tion can be guaranteed to occur.
To make this question precise, let us assume for the moment that sprites don't occlude each other but that they are just summed up in pixel space. Then the compositional representation the generative process is simply (-()) (1: (2), i.e.
f(z) (=(=)) + (2(2)))
The question becomes: Given training samples (z. x)) from P, can we train a model ff that fitting this generative process on P also guarantees fitting it on Q? That is, are looking for conditions such that the model generalizes from to Q:
f f=
f f=
(5)
We assume that C' is known, in order to generalize, we must be able reconstruct the individual component functions yp,, For the simple case from equation 4, we can fully reconstruct the component functions as follows. First, we note that if supp P is in open set, we can locally reconstruct the hidden Jacobian of y from the observable Jacobian of f as
0f
04:
dz (z)
(zx).
(6)
Ozk
Since the training distribution contains all possible component configurations zk. we can reconstruct the Jacobian of 4 in every point 25. Then we know everything about 4 up to global offiset (which can be removed there exists a known initial point for integration).
Our goal is to extend this approach to maximally large set of composition functions C. Our reasoning is straightforward if C the identity, but what if we have occlusions or other nonlinear interactions between slots? What are general conditions on C' and the support of the training distri- bution P such that we can still reconstruct the individual component functions and thus generalize compositionally?
5

---

foreground sprite
foreground sprite
P
P
P
background sprite
background sprite
Figure 4: Sufficient support condition (Definition 3). For (compositional) diagonal support, all samples will contain sprites with similar positions, leading to heavy occlusions and making reconstruction of the background sprite impossible (left). Reconstruction of the background sprite only possible if the support is chosen broad enough, such that the subset of points sharing the same background sprite p' contains samples with sufficient variance in the foreground sample. Specifically, each pixel of the background sprite must be observable at least once (right).
Let us now consider the sprites example with occlusions, where (o renders the background sprite that is occasionally occluded by the foreground sprite rendered by 92-- Let us also assume that the support of P is basically a thin region around the diagonal; see Figure 4 (left). In this case, the two sprites are always relatively similar, leading large overlaps for practically all samples of the training set. It is impossible to reconstruct the full Jacobian of the occluded sprite from a single sample. Instead, we need of samples for which the background sprite is the
while the foreground sprite is in different positions; see Figure (right). With sufficient samples this kind, we can observe all pixels of the background sprite at least once. Then reconstruction of the Jacobian of 1 possible again.
This line of thought brings us to a more general condition on the gentaaggnn process: The composition function C' and the support of the training set must be chosen such that the full Jacobian can reconstructed for each component function and for all component latents. In other words, for each configuration of given component, P must be sufficiently large that it is possible to track how each dimension of the output depends on each dimension the component representation. We formally define the concept of sufficient support below. Note that whether the support of P is sufficient or not depends on the choice of composition function C; see Appendix for examples.
(æ1, ..... ²K) 2, has sufficient support w.rt. a compositional representation of function f. if supp in an open set and for any latent value 2 there exists finite set of points P'(z, k)) C {p supp P P 2x. for which the sum of total derivatives of C' has full rank. That is,
Definition (Sufficient support). distribution P over latents
àc
rank Σ
(+(p) M, Oep.
pEP
where M is the dimension of the component space X C R.M.
are now ready to state our main theorem, namely that if f. share same composition function and if P has compositional and sufficient support, then the model f generalizes to Q if it matches the ground-truth data- settraggneratnng process f P.
Let P, Q be arbitrary distributions over latents =21,..., z②) ) Z. Let f, be functions with compositional representations in the sense of definition that share 2,, 2x) }. but use arbitrary {4P1..., .... 'K XX, XI..., Xx ( Pr. RK}.
Theorem 1.
Assume the following assumptions hold:
(A1) C. 4kx Px are differentiable, C' is Lipschitz yp, and tp continuous z.
(A2) P has compositional support w.r.. Q in the sense of definition 2.
(A3) P has sufficient support w.r.t. f in the sense of definition 3.
(A4) There exists an initial point pd supp P such that (p(p)) = (p(2))
Then f generalizes to Q, i.e. f == f = f f

---

The proof follows roughly the intuition we developed above in that we show that the Jacobians of the component functions can be reconstructed everywhere. Bear in mind that this simply construction for the proof: The theorem holds whenever fits the output of f on the training distribution P. which we can achieve with standard supervised training and without access to the ground-truth Jacobians. It should also be emphasized that since the compositional representation is not unique, the theorem holds if there exists at least one for which the assumptions are fulfilled. Note also that the initial point condition (A4) is needed in the proof, but in all practical experiments (see below). we can generalize compositionally without explicit knowledge of that point. We relegate further details to Appendix A.
4
Experiments
We validate our theoretical framework on the multi-sprite data. All models were trained for 2000 epochs on training sets of 100k samples using an NVIDIA RTX 2080 Ti; all test sets contain 10k samples. Table summarizes the reconstruction quality achieved on the in-domain (ID) test set (P)
and the entire latent space (Q) for all experiments.
Motivating experiment We implement the setup from Figure 1 to demonstrate that compositional model does indeed generalize if the conditions from Theorem are met. We model the component functions four fully-conme connected layers followed by four upsampling-convoluttee the 5d component latent to 64 x 64 RGB images. For training stability, the composition function is implemented soft pixel-wise addition using the sigmoid function (-)
stages, mapping
= (m²) क1 + ( ..2,
(8)
which allows component 1 to occlude component 2. We contrast this to a non-compositional monolithic model, which has the same architecture as single component function (with adjusted layer sizes to match the overall parameter count of the compositional model). Both models are trained on samples (z, from the training set using an MSE reconstruction loss. We show that both models have the capacity to fit the data by training on random samples covering the entire latent space (Table 1, #1,2). We then train on a distribution with orthogonal support as in equation 2, albeit with two planes for the foreground component satisfy the sufficient support condition (Definition 3) as explained in Figure 4. Both models can reconstruct ID samples, but only the compositional model generalizes to the entire latent space (Table 1, #3,4).
Flexible compositional support Next, we demonstrate the variety of settings that fulfill the compositional support assumption illustrated in Figure 3B and C. To this end, repeat the experiment on training sets P sampled from (i) a normal distribution with orthogonal support (Table #5) and (ii) uniform distribution over diagonal support chosen broad enough to satisfy the sufficient support condition (Table 1, #6; see also Appendix C for details on how the support was chosen). The model generalizes to the entire latent space both settings. Since the generalization performance is already close to the performance ceiling, broadening the support of both distributions (Table #7,8) does not further increase performance.
Violating Conditions
Finally, we look at the effect of violating some conditions.
Gaps in support (Table 1, #9) Gaps in the support of the training set such that some compo- nent configurations are never observed (Figure 3E) violate the compositional support condition (Definition 2). While the overall reconstruction performance only drops slightly. visualizing the reconstruction error over a 2d-slice of the latent space in Figure illustrates clearly that generalization fails exactly where the condition is violated.
Insufficient training variability (Table 1, #10) Reducing the width of the diagonal support violates the sufficient support condition (Definition 3) as soon as some parts of the background component are always occluded and can not be observed in the output anymore (Compare Appendix C for details). We can clearly see that reconstruction performance on the entire latent space drops significantly result.
Collapsed Composition Function (Table 1, #11) Changing the output of each component function from RGB to RGBa and implementing the composition as alpha compositing yields model that is still compositional, but for which no support can satisfy the sufficient support condition since
7

---

# Train Set
Model
R ID
R2 all
AR&
1
Random
Monolithic
0.931
25.8e-4
0.931 25.8e-4
0.000
28.2e-4
2
Random
Compositional
0.957
=1 +1.0e-3
0.957 =1.0c-3
0.000
#1.4-33
3
Orthogonal
Monolithic
0,948
#1.7e-3
-0,500
=6.7e-2
1.448
46.76-2
4
Orthogonal
Compositional
0.957
#6.40-4
0.951 #1.4
0.006
+1.5e33
5 Ortho. ~ N
Compositional
0.957
45..5e-4
0,951 #1.0e=3
0.006
6
Diagonal
Compositional
0.954
+5.4e-3
0.945 =1.6e-2
0.009
7 Ortho. (broad)
Compositional
0.959
+9.70-4
0,954
21.303
21.603
8
Diag, (broad)
Compositional
0.957
=1.20-3
0.955 -1.20-3
0.002
9
Ortho. (gap)
Compositional
0.954
=1.70-3
0.895 =7.4o-3
0.059 40.69-7
10 Diag, (narrow)
Compositional
0.867 =7.5e-2
0,589
0,278 #2.96-1
11 Orthogonal
Comp. (RGBa)
=.984=1.86-44
0.979 =1 40.4
0,005 #2.36-4
Table 1: We report the reconstruction quality measured as variance-weighted R² score (closer to 1 is better) on the in-domain (ID) test set and the entire latent space. As the IID region occupies tiny fraction of the entire latent space, the difference in performance (AR2) indicates how well model generalizes OOD. All results are averaged over 5 random seeds.#1-4 The results demonstrate that a monolithic model fails to generalize the setup from Figure 1, but a compositional model performs well on the entire latent space. #5-8 Generalization can occur in a variety of settings that fulfill the sufficient conditions from Theorem #9,10 Violating the compositional and sufficient support condition prohibits generalization while choosing more complex function class still works (#11). Table in the appendix additionally reports the MSE for all experiments.
0.9
0.8
0.010
coord sprite
0.7
0.6
0.008
0.5
0.4
0.006
0.3
0.2
0.004
0.1
0.2
0.3
04
0.5
0.6
0.7
0.88
0.9
0.1
0.2
0.6
0.8
0.9
MSE
x-coord. sprite
x-coord. sprite
Figure 5: Heatmap of the reconstruction error over 21,==2xx-rojection of the latent space with overlaid training support (red). Generalization can occur when support compositional (left) fails exactly where the support is incomplete at 21,x E [0.14, 0.46] (right).
the derivative of transparent pixels will always be zero and the Jacobian matrix can therefore never have full rank (see Appendix B. for more details). However, observe that the model still generalizes to the entire latent space and achieves even lower reconstruction error than the original model. This emphasizes that what we present are merely sufficient conditions. We include this experiment to motivate future work to find weaker conditions.
5 Discussion
We presented a first step and a framework to study compositional generalization in a more principled way. Clearly, there remain many open questions and limitations that leave for future work.
Supervised setting We only studied supervised regression setting in which the model has access the ground-truth latents of each training sample. Or own findings underlined the results previous works, e.g., Schott et al. [3] that compositional generalization is not trivial even in this setting. Ultimately, we are of course interested in the unsupervised setting akin to what is typically studied in identifiable representation learning. The unsupervised setting comes with inherent ambiguitics the

---

relationship between ground-truti latent space and inferred representations is unknown. No prior works exist that address this identifiability problem when training on a subset of the latent space, which makes generalizations guarantees as presented in this work harder to derive. Still, the results in this paper build an important foundation for future studies as sufficient conditions in the supervised setting can be considered necessary conditions in the unsupervised setting.
Jacobian and initial point The proof of Theorem utilizes the Jacobian of the ground-truth model. We emphasize again that this construction is necessary only for the proof and does not mean that we require access to the data-generating processes' full Jacobian for training. Similarly, the existence of an initial point pd is technicality of the proof that is not reflected in the experiments. While it is not yet clear whether is possible to complete the proof without the initial point condition, we believe there is self-consistency condition that might alleviate the need for this condition. The experiments thus hint at the existence of alternative proof strategies with relaxed assumptions.
Known composition function We also assume the composition function to be known which is approximately true in many interesting scenarios, such as object composition in scenes or the composition of instruments in music. In fact, many structured representation learning approaches like e.g. SlotAttention [18] incorporate structural components that are meant to mimic the compositional nature of the ground-rutth-generaing process. In other interesting cases like language, however, the composition function is unknown a priori and needs to be learned. This might be possible by observing how the gradients of C' change with respect fixed slot, at least if certain regularity conditions are fulfilled.
Inductive biases Some of the conditions derived be relaxed in the presence of certain inductive biases. For example, models with an inductive bias towards shift invariance might be able to cope with certain gaps in the training support (e.g.. if sprites are not visible in every position). Similarly, assuming all component functions &p to be identical would substantially simplify the problem and allow for much smaller sufficient supports P. The conditions we derived do not assume any inductive bias but are meant to formally guarantee compositional generalization. We expect that our conditions generalize to more realistic conditions as long as the core aspects are fulfilled.
Error bounds Our generalization results hold only if the learned model perfectly matches the ground-truth model on the training distribution. This is similar to identifiable representation learning. where model must find the global minimum of certain loss or reconstruction error for the theory to hold. Nonetheless, extending our results towards generalization errors that are bounded by the error on the training distribution is an important avenue for future work.
Broader impact Compositional generalization, once achieved, has the potential to be benefit many downstream applications. By increasing sample and training efficiency. it could help to democratize the development and research of large-scale models. Better generalization capabilities could also increase the reliability and robustness of models but may amplify existing biases and inequalities in the data by generalizing them and hinder our ability to interpret and certify a model's decisions.
Conclusion
Machine learning, despite all recent breakthroughs, still struggles with generalization. Taking advantage of the basic building blocks that compose our visual world and our languages remains unique to human cognition. We believe that progress towards more generalizable machine learning is hampered by a lack of a formal understanding of how generalization can occur. This paper focuses on compositional generalization and provides precise mathematical framework study it. We derive a set of sufficient conditions under which compositional generalization can occur and which cover a wide range of existing approaches. We see this work stepping stone towards identifiable representation learning techniques that can provably infer and leverage the compositional structure of the data. is certainly still long road toward scalable empirical learning techniques that can fully leverage the compositional nature of our world. However, once achieved, there is an opportunity for drastically more cample-efficien robust, and human- aligneed machine learning models.

---

Acknowledgments
We would like to thank (in alphabetical order):
Jack Brady, Simon Buchholz, Attila Juhos, and Roland Zimmermann for helpful discussions and feedback.
This work was supported by the German Federal Ministry of Education and Research (BMBF): Tübingen AI Center, FKZ: 0111 8039A. WB acknowledges financial support via an Emmy Noether Grant funded by the German Research Foundation (DFG) under grant no. BR 6382/1-1 11 and via the Open Philantropy Foundation funded by the Good Ventures Foundation. WB a member of the Machine Learning Cluster of Excellence, EXC number 2064/1 Project number 390727645. This research utilized compute resources at the Tübingen Machine Learning Cloud, DFG FKZ INST 37/1057-1 FUGG. We thank the International Max Planck Research School for Intelligent Systems (IMPRS-IS) for supporting TW and PM.
Author contributions
The project was led and coordinated by TW. TW and PM jointly developed the theory with insights from WB. TW implemented and conducted the experiments with input from PM and WB. TW led the writing of the manuscript with help from WB, PM, and MB. TW created all figures with comments from PM and WB.
References
[1] Jerry A. Fodor and Zenon W. Pylyshyn. Connectionism and cognitive architecture: critical analysis. Cognition, 28(1):3-71, March 1988. ISSN 0010-0277. doi: 10.1016/0010-00777688 90031-5.
[2] Noam Chomsky, Aspects of the Theory of Syntax, volume 11. MIT press, 2014.
[3] Lukas Schott, Julius von Kügelgen, Frederik Träuble, Peter Gehler, Chris Russell, Matthias Bethge, Bernhard Schölkopf, Francesco Locatello, and Wieland Brendel. Visual Representation Learning Does Not Generalize Strongly Within the Same Domain. arXiv:2107.08221 [cs]. February 2022.
[4] Milton Llera Montero, Casimir JH Ludwig, Rui Ponte Costa, Gaurav Malhotra, and Jeffrey Bowers. The role of Disentanglement in Generalisation. In International Conference on Learning Representations, February 2022.
[5] Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of requence-to-sequeee recurrent networks. In International Conference Machine Learning, pages 2873-2882. PMLR, 2018.
[6] Joao Loula, Marco Baroni, and Brenden M Lake. Rearranging the familiar: Testing composi- 2018.
tional generalization in recurrent networks. arXiv preprint
[7] Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashu- bin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, et al. Measuring compositional generalization: A comprehensive method realistic data. arXiv preprint arXiv:1912.09711, 2019.
[8] Francesco Locatello, Gabriele Abbati, Thomas Rainforth, Stefan Bauer, Bernhard Schölkopf, and Olivier Bachem. On the fairness of disentangled representations. Advances in neural information processing systems, 32, 2019.
[9] Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE Transactions on Pattern Analysis and Machine Intelligence. 35(8): 1798-1828, 2013. doi: 10.11099/PAM...013..500
[10] Sjoerd van Steenkiste, Francesco Locatello, Jürgen Schmidhuber, and Olivier Bachem. Are disentangled representations helpful for abstract visual reasoning? In H. Wallach, H. Larochelle, A. Beygelzimer, dAlché-Bue, Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
10

---

[11] Milton L. Montero, Jeffrey Bowers, Rui Ponte Costa, Casimir JH Ludwig, and Gaurav Malhotra. Lost in Latent Space: Examining failures of disentangled models combinatorial generalisation. In Advances in Neural Information Processing Systems, October 2022.
[12] Patrik Reizinger, Luigi Gresele, Jack Brady, Julius Von Kügelgen, Dominik Zietlow, Bernhard Schölkopf, Georg Martius, Wieland Brendel, and Michel Besserve. Embrace the gap: VAFs perform independent mechanism analysis. arXiv preprint arXiv:2206.024 02441, 2022.
[13] Roland S Zimmermann, Yash Sharma, Steffen Schneider, Matthias Bethge, and Wieland Brendel. Contrastive learning inverts the data generating process. In International Conference on Machine Learning, pages 12979-12990. PMLR, 2021.
[14] Julius Von Kügelgen, Yash Sharma, Luigi Gresele, Wieland Brendel, Bernhard Schölkopf, Michel Besserve, and Francesco Locatello. Self-supervised learning with data augmentations provably isolates content from style. Advances neural information processing systems, 34: 16451-16467, 2021.
[15] Jake Russin, Jason Jo, Randall C C'RReilly and Yoshua Bengio. Compositional generalization in deep seq2seq model by separating syntax and semantics. arXiv preprint arXiv: 190400999 2019.
[16] Ekin Akyürek, Afra Feyza Akyürek, and Jacob Andreas. Learning to recombine and resample data for compositional generalization. arXiv preprint arXiv:2010.03706, 2020.
[17] Diego Marcheggiani, Jasmijn Bastings, and Ivan Titov. Exploiting semantics in neural machine translation with graph convolutional networks. arXiv preprint arXiv: 0831,, 2018.
[18] Francesco Locatello, Dirk Weissenborn, Thomas Unterthiner, Aravindh Mahendran, Georg Heigold, Jakob Uszkoreit, Alexey Dosovitskiy, and Thomas Kipf. Object-Centric Learning with Slot Attention. In Advances in Neural Information Processing Systems, volume 33, pages 11525-11538
Curran Associates, Inc., 2020.
[19] Geoffrey E Hinton, Sara Sabour, and Nicholas Frosst. Matrix capsules with EM routing. In International Conference on Learning Representations, 2018.
[20] Klaus Greff, Raphaël Lopez Kaufman, Rishabh Kabra, Nick Watters, Christopher Burgess, Daniel Zoran, Loic Matthey, Matthew Botvinick, and Alexander Lerchner. Multi-object repre- sentation learning with iterative variational inference. In International Conference on Machine Learning, pages 2424-2433. PMLR, 2019.
[21] Christopher P. Burgess, Loic Matthey, Nicholas Watters, Rishabh Kabra, Irina Higgins, Matt Botvinick, and Alexander Lerchner. MONet: Unsupervised Scene Decomposition and Repre- sentation, January 2019.
[22] Thomas Kipf, Gamaleldin Elsayed, Aravindh Mahendran, Austin Stone, Sara Sabour, Georg Heigold, Rico Jonschkowski, Alexey Dosovitskiy, and Klaus Greff. Conditional object-centric learning from video. arXiv preprint arXiv:2 2021.
[23] Ivan I. Vankov and Jeffrey S. Bowers. Training neural networks to encode symbols enables combinatorial generalization. Philosophical Transactions of the Royal Society B: Biological Sciences, 375(1791): 20019990,,, February 2020. doi: (099//ssb.2019.0330
[24] E. Paxon Frady, Spencer Kent, Quinn Tran, Pentti Kanerva, Bruno A. Olshausen, and Friedrich Sommer. Learning and generalization of compositional representations of visual scenes, March 2023.
[25] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz. Kaiser, and Illia Polosukhin. Attention is All you Need. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
(26) Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Velickovie. Combinatorial optimization and reasoning with graph neural networks.
11

---

[27] Zhang-Wa Wei Hong, Ge Yang, and Pulkit Agrawal. Bi-linear value networks for multi-goal reinforcement learning. In International Conference on Learning Representations, 2021.
[28] Sindy Löwe, Phillip Lippe, Maja Rudolph, and Max Welling. Complex-Valbee Autoencoders for Object Discovery, November 2022.
[29] Shai Ben-David and Ruth Urner. Domain adaptation quantity compensate for quality? Annals of Mathematics and Artificial Intelligence, 70:185-200 2014.
[30] Masashi Sugiyama, Matthias Krauledat, and Klaus- Robert Müller. Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research, 8(5), 2007.
[31] Zheyan Shen, Jiashuo Liu, Yue He, Xingxuan Zhang, Renzhe Xu, Han Yu, and Peng Cui. Towards Out-Of-Distribution Generalization: A Survey. arXiv:2108, 13624 [cs]. August 2021.
doi: 10.4 13624.
[32] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79: 151-175, 2010.
[33] Aviv Netanyahu, Abhishek Gupta, Max Simchowitz, Kaiqing Zhang, and Pulkit Agrawal. Learning to Extrapolate: A Transductive Approach. In The Eleventh International Conference on Learning Representations, February 2023.
[34] Kefan Dong and Tengyu Ma. First Steps Toward Understanding the Extrapolation of Nonlinear Models Unseen Domains. In NeurlPS 2022 Workshop on Distribution Shifts: Connecting Methods and Applications, October 2022.
[35] 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, 161i 066990 [cs], December 2016.
12

---

A Proof of Theorem
We reiterate the setup and notation introduced in the paper here for ease of reference.
Notation [N]] denotes the set of natural numbers {1. 2, ... Vector-valued variables (e.g., x) and functions (e.g.. f) written in bold. Id denotes the (vector-valued) identity function. We write the support of a distribution P as supp P. To express that two functions f are equal for all points in the support of distribution P. i.c., f(x) = g(x) Væ E supp P. we write f= Finally, zu denotes the total derivative of a vector-valued function f by all its inputs æ, corresponding the Jacobian matrix with entries af Dx."
Øf
Setup We are given two arbitrary distributions P. Q over latents z = [i.,..., xk) E Z. Each latent 2 describes one of the K components of the final data point produced by the ground-truth data-generating process f. A model f is trained to fit the data-generating process on samples of P; the aim is to derive conditions P and f that sufficient for f to then also fit on Q.
We assume that f. f are chosen such that we can find at least compositional representation (Definition 1) for either function that shares a common functiooo C and factorization of the latent space 2 X
x... Zx= Z.
Proof of Theorem I. For f to generalize Q, need show fitting on P implies also fitting it on Q, in other words
f
(9)
Step 1. Since C is known and fixed, we immediately get
$ p
-
(10)
i.e, it suffices to show that the component functions generalize. Note, however, that since C' is not generally assumed to be invertible, we do not directly get that agreement of f, f on P also implies agreement of their component functions sp & on
Step 2. We require P to have compositional support w.r.t. Q (Definition 2 and Assumption (A2)). The consequence of this assumption is that any point q (q1..... 9x) ) Q can be constructed from components of the K support points p* (pi..., Px P subject to p Qu as
q= (pl,.... p
(11)
trivial consequence, then, is that points & E E in component space corresponding to points Q in latent space always be mapped back to latents in P
(g))) =
= (4) (pf*) ,...KK PK (PK
(12)
because each component function 4Px only depends the latents zµ of single component. This is also the case for the component functions ep of so that we get
Φ.
(13)
Step 3. We now only need to show that & = & follows from f = f. As noted above, this is p not guaranteed to be the case, as C not generally invertible (e.g., in the presence of occlusions). We, therefore, need to consider when unique reconstruction of the component functions (and correspondingly ()) possible, based on only the observations æ = f(z) on Q.
As explained in the main paper, we can reason about how change in the latents 2μ of some slot affects the final output, which we can express through the chain rule as
0f (2) = 0ek
aC
04k (zk)
(v(())
Vk E [K].
(14)
Ozk
NxD
NxM
MxD
13

---

Here, N' is the dimension of the final output (e.g.. 64 x 64 x 3 for RGB images), M is the dimension of component's 's representation Tg (e.g., also 64 x 64 3 for RGB images composition happens (e.g., 5: x-position,
in image space), and D is the dimension of component's latent description y-position, shape, size, hue for sprites). Note that we can look at the derivative component-wiss because each component function (Pk only depends on the latents 2g of its component. However, the combination function still depends on the (hidden) representation of all components, and therefore aC is function of the entire yp and z. dp,
In Equation 14, the left-hand side (LHS) 8f can be computed from the training, long supp P 2zs is an open set. On the right-hand side (RHS), the functional form of BC is known since C' is de,
given, but since (p(=) is still unknown, the exact entries of this Jacobian matrix are unknown. As such, Equation 14 defines a system of partial differential equations (PDEs) for the set of component functions & with independent variables z.
Before we can attempt to solve this system of PDEs, we simplify it by isolating 0es Since all terms ãzt are matrices, this is equivalent to solving a system of linear equations. For N = M, ac, is square, and we can solve by taking its inverse as long as the determinant is not zero. In the general case of N 2 M, however, we have to resort to the pseudoinverse to write
dep 8z
( |Cc T aC
-1
ac T of Oep
Ak [K].
(15)
0up
04p/
azk
which gives all solutions aep if any exist. This system is overdetermined, and (unique) solution dzn exists if ac has full (column) rank. In other words, to execute this simplification step on P, we 0e, require that for all P the M column vectors of the form
( ( (+((2), .. 0pkm (p(=))) Vm E [M]
OCN
(16)
Tupkin
are linearly independent. Each entry of a column vector describes how all entries Cn of the final output (c.g., the pixels of the output image) change with a single entry Pkm of the intermediate representation of component A (e.g.. single pixel of the component-wise image). It is easy to see that if even a part of the intermediate representation is not reflected in the final output (e.g., in the presence of occlusions, when single pixel of one component is occluded), the entire corresponding column is zero, and the matrix does not have full rank.
To circumvent this issue, we realize that the LHS of Equation 15 only depends on the latents 2y of single component. Hence, for given latent z and a slot index k, the correct component function will have the same solution for all points in any (finite) set
(17) We can interpret these points as the intersection of P with a plane in latent space at z (e.g.. all latent combinations the training set which one component fixed then define a modified composition function Ö that takes z and a slot index & as input and produces "superposition" of images corresponding to the latents in the subset as
P'(z, k) C (p E supp Plp; = =x)
specific configuration). We can
Ö (4p, z,k)=
Σ C(p(p)).
(18)
(x,
Essentially, we are condensing the information from multiple points in the latent space into a single function. This enables to write modified version of Equation 14
of (p)
ac
0sh (zL) = Ozk
ac
0ep (zk)
Σ
(<(())
(4p, z. k)
Vk E [K] (19)
Ozk
dep
dip:
Ozk
kx.k)
PE (*.,)
Now we can solve for rank for unique solution to exist, i.e.,
042 dzz as in Equation 15, but this time require only that ac dip
has full (column)
ac (4, 2,k
ac (4(p) = M V Vk E [K].
rank Oep
Σ
dep 0
(20)
(x,
14

---

In general, this condition is easier to fulfill since full rank is not required in any one point but over set of points. For occlusions, for example, any pixel of slot can be occluded in some points p p' as long as it is not occluded in all of them. We can interpret this procedure as "collecting sufficient information" such that an inversion of the generally non-invertible C' becomes feasible locally.
The requirement that supp 1' has to be an open set, together with the full rank condition on the Jacobian of the composition function condensed over multiple points, C, is termed sufficient support in the main paper (Definition and Assumption (A3)). As explained here, this means that the training distribution P. the composition function C, and derivatives of the function f on the training set specify a unique relationship between the component function Pk: and its derivatives:
0ek
(4, k) (00'
OC 04p.
OC T
of Ozk
Σ pE."(z.k)
(p)
Vk E [K].
(21)
0zk
dep:
As explained above, this solution to the linear system of equations constitutes a system of partial differential equations (PDEs) in the set of component functions &p with independent variables z. We can see that this system has the form
0,4(2)) = a; sp(2),
(22)
where i E [L] with L == KD is an index over the flattened dimensions K and D such that the system of PDEs contains the functional relation between and its derivative from Equation 21 for all values of k. a; the combination of corresponding terms from the RHS of Equation 21. If this system of PDEs allows for more than one solution, Equation 21 does not uniquely determine the component functions.
However, we have access to some initial point for which we know 4p(0) = sp", we can write
cp(21,... 2L) - -00 = (pp(21, zL) - (0, 22, .... (.)))
+ (v(0,, ...,, 21.) (00 0, 23, .... zr.))
(23)
+...
+ (v.0....,
.... 0, =1.) (0,....
In each line of this equation, only a single 2; =: t is changing; all other 21, 2 are fixed. Any solution of Equation 23, therefore, also has to solve the L ordinary differential equations (ODEs) of the form
O,4(2 1 f, 2..1,...,, =1) = (2121..... 2; 1, 2,11, 2L, (21,, 21-1, 1, 2i+1, 21)
(24)
which have a unique solution if a; is Lipschitz in & and continuous in 2;, as guaranteed by (A1). Therefore, 23 has most one solution. This reference point does not have to be in = O, simple coordinate transform will yield the same result for any point in P. It is therefore sufficient that there exists some point pd P for which sp(x") = ppp") obtain the same unique solution for yo and s
which is exactly what (A4) states. Overall, this means that Equation 21 does indeed specify unique component functions k
To recap, we have shown that the training distribution P. the composition function C, and knowledge of f(z) for supp specifies unique relationship between the component functions s and their derivative (Equation 21). With additional knowledge one initial point, this constrains the problem enough get unique solution for the component functions y Since P and C are fixed, this means that if the functions and f agree on P. they specify the same component functions. i...
(25)
Step 4. Finally, we can conclude the model f fitting the ground-trute generating process f on the training distribution P. through Equations 25, 13, and 10, implies that the model generalizes Q. In other words, Equation holds.
15

---

21
bacche5
22
batche5
21.32
batchx10
Linwar 258)
(dnwardd_iiideeeeeee Elu()
Linear (20 Elu(?
Libear (1_ (d_216dea-266)) Elu()
Linoar (d (dddiddaa=29) EluO)
Linear (d_01 Elu()
Lizear (d_biddem=266) Rlu
Linear (a 256) Elu
Lineax (3 dduhiddes-520) Flu
Lizear (d_ 266) Elu()
Linear (d0aa-290) Elu
Lisear(d (1 32d Elu(
ba
batcba3rwtrd
batcbrarddr
epeasple(tatorr Conred Elu()
Upeanple (factor-2)
Upeanple (tactorr-))) (sernel-2, channel-64) Elu()
(sermel-2, chamel-332) Elu()
Opunspla
Upaanple (factor-2) Cour2d(terzze-22 chaznel-322
Conv2dCkerual-22 channel-32) Elu()
Conv2d (karme 1-2, chammel-64) Elu()
Elu()
(pesmpletaactor-2 Cherna 1-2, channe -32)
Upeanple (factor-2) (kermele)) (bame1-322
Upeample(tacter-2 (xermele)) chammel-64) Elu(}
Elu()
Elu()
Dpuanpla Couv2d (kermelker channel-82) Elu()
Upaanple (Factor-2)) Conv2d (kersel-2, chazmel-32)
Uga [paasple(aactor-2 2lov2((eeree122 chameel660 Elu()
Elu()
@1
batchh3++6464
batche33e64664
batcch3--64664
aoft__edd
batchb-+669464
Figure 6: Schematic of the employed models. The monolithic model (right) uses the same architecture each component model of the compositional model (left), except with higher number of hidden units and channels to match the number of parameters.
B Experimental Details
Figure shows a schematic of the employed compositional and monolithic model from Section 4.
Table 2 additionally reports the reconstruction quality measures as the mean squared error (MSE) for the experiments from Section
B.1 Details about the compositional functions
As explained in Equation 8 in section 4, the composition function is implemented as a soft pixel-wise addition in most experiments. The use of the sigmoid function o(-) in the composition
x = .. + o-()))) -
(26)
was necessary for training stability. With this formulation, sprites can also overlap somewhat transparently, which not desired and leads to small reconstruction artifacts for some specific samples. Implementing the composition with step function
step(ā1) Hi + step(-āt 22
(27)
instead would be more faithful to the ground-tros data- eetta-geneaaing process, but is hard to train with gradient descent.
Note that both formulations could easily be extended to more than one sprite by simply repeating the composition operation with any additional sprite.
16

---

Train Set
Model
MSE ID
MSE all
Random
Monolithic
1.730-3=1.5-55
2 Random
Compositional
1.07c-3
=2.60-5
1.07c-3
=2.60-5
Orthogonal
Monolithic
8.49c-4
2229e-5
4.06c-2 23.96-3
4 Orthogonal
Compositional
6.94e
e1lees
1.24e-3 24.1e-5
Ortho W
Compositional
7.01e-4
28.7e-6
1.24c-3 22.60-5
6 Diagonal
Compositional
8.87e-4
110004
1.39e-3 24.00-4
Ortho. (broad)
Compositional
6.50e-4.
=1.5e5
1.16e-3 23.30-5
8
Diag. (broad)
Compositional
9.51c
-2.8e-5
1.13e-3 #3.1e-5
9 Ortho. (gap)
Compositional
7.36c 22,70-5
2.64c-3 =1.80-4
10 Diag. (narrow)
Compositional
2.22c-
21.26-3
1.04c-2 =7.1e-3
11 Orthogonal
Comp. (RGBa)
2.67e 22-666
5.24e-4 23.7e-6
Table 2: We report the reconstruction quality measured as mean squared error (MSE, lower is better) for both the in-domain (ID) test set and the entire latent space, averaged over 5 random seeds.
In section 4, we also looked at model that implements the composition through alpha compositing instead (see also Table 1, #11). Here, each component's intermediate representation is an RGBa image. The components then overlaid on an opaque black background using the composition function
Za = T1,a + (1 -1- x1.a) 22,a
(28)
F2.a Ta
JRGB = 11,a 31 LI + (1 -1,.))
22BBGBB
(29)
While this yields compositional function, the sufficient support condition (Definition 3) is generally not fulfilled on the sprites data. The reason is that in fully transparent pixels (a = 0), changing the RGB value is not reflected in the output. Conversely, if pixel is black, changing its alpha value will not affect how it is blended over a black background. As a result, most columns in the Jacobian àc 0p; (see also Equation 16) will be zero. Since the intermediate representations of each sprite will contain a lot of black or transparent pixels (the entire background), the rank of the Jacobian here will be low. In this case, the workaround from Equation 18 does not help since the low rank is not result of another component in the foreground but of the specific parameterization of each component itself.
As stated in the main paper, the fact that this parameterization still produces good results and generalizes well is an indicator that there might another proof strategy or workaround that avoids this specific issue.
C Details on the sufficient support assumption
The sufficient support assumption stated in Definition 3 amounts to rank condition on the Jacobian of the final output by the intermediate component representation æ: For each configuration of a given component, P must be sufficiently large so that tracking the dependence of each output dimension on each dimension of the component representation is possible. Step 3 of the proof of Theorem outlines how this condition arises in general: For some interactions between components, is possible that the final output æ becomes invariant to changes in the representation ãe. of component k. We can assume that the output not generally invariant to component (since the component could then just be dropped from the data-genett data-generating process) and instead only arises for certain configurations of components. We provide additional examples here that illustrate how such an invariance can arise for different choices of C' and detail how a sufficient support can be chosen in these cases. Note that while it possible to calculate the sufficient support condition directly, this is costly do dataset scale since it involves calculating large Jacobians for many different data points. Instead, it is helpful to analyze which specific component configurations would violate the condition and choose the training set accordingly.
2d sprites with occlusion (orthogonal sampling) As explained the main text and illustrated in Figure 4, occlusions make the output image invariant to changes of the background sprite in the
17

---

samples
background sprite
samples same background sprite but dffereent foreground sprito
Figure 7: For each configuration of the background sprite, the training distribution must contain at least two samples in which the foreground sprites not overlap the same pixels.
occluded pixels. The model does not receive a training signal for these pixels, and reconstruction becomes impossible. In the case of orthogonal sampling, the foreground sprite is fixed in its base configuration (orange triangle in the bottom left corner) whenever the background sprite is sampled randomly; the first of Figure 7. The foreground sprite, therefore, always occludes the same background pixels, for which the Jacobian ac is zero. Therefore, for each configuration of the background sprite, second data point is required which the foreground sprite occludes a different and distinct set of pixels (cyan square in the second row of Figure 7). We can clearly observe that this is the case here; therefore, the Jacobians ac from both samples have zero entries at different kipkmm
Tep...
indices yn and their sum has full rank. The resulting sufficient support has the shape illustrated on the left of Figure 5.
2d sprites with occlusion (diagonal sampling) As explained above, sufficient support for occluding sprites is guaranteed if the dataset contains at least two samples with the same background sprite and different foreground sprites that overlap distinct pixels (as also illustrated in Figure 4). In the diagonal sampling case, we, therefore, need choose the width of the diagonal broad enough to guarantee that it contains such foreground sprites. The smallest possible width of the diagonal can be determined by finding the smallest possible x-offset (or y-offset) for which pair of sprites of the smallest scale does not overlap. This is the case for a width of 0.2, which was used for the diagonal sampling case in Table I, #6. The broad diagonal sampling case Table 1, #8 used a width of 0.4 (double the minimal width), while the narrow diagonal sampling case in Table 1, #10 used width of 0.1 (half the minimal width).
Attributes and transformations of an object The sufficient support assumption is also necessary If the composition function C is chosen to model the interaction of multiple attributes or transformations on single object. For example, if one component models the rotation of an object and another models its shape, and the composition happens pixel space, then circular shape will be invariant to rotations. The Jacobian of the output by the rotation component will not have full rank whenever the shape component circular. sufficient support must contain at least one non-circular sample for each rotation angle in the training set. See Appendix D for empirical observation of this phenomenon.
Overlaying audio signals Sufficient support has to be guaranteed whenever the composition function contains max(.) or min(-) operations or similar operations with zero gradients. For example, if two or more audio signals are picked up by microphone modeled with finite gain, a signal above certain amplitude will saturate the microphone. The sufficient support assumption guarantees that for the configuration of one audio signal, there exists at least one sample in the dataset in which the other signals are below that threshold, such that changes the signal are registered by the microphone.
Vector matrix products If the intermediate component representations ã are vectors matrices and the composition function is their (outer) product, changes in the first vector (matrix) of the product do not change the output if the second vector (matrix) multiplies with a zero-clement (or
18

---

Composition of object attributes. Each of three figures shows traversal of one component: rotation, color, and blur. The intermediate oulput of the first component function 4 an image of a white square specific angle; the intermediate output of the other two component functions are convolution filters. Note that for strong Gaussian blurs, the shape becomes circular, making the output invariant to rotations.
Figure 8:
Target
Reconnttuuttoon
logonnll tolliing spoit
MSE 10000002..00 Se-4
orthogo tall buiniig support sufident suppont not fulliled
Figure 9: Generalizing to novel compositions of object attributes. For the data-generating process illustrated in Figure 8, a compositional model can learn to generalize to unseen compositions of rotation, color, and blur when all conditions are fulfilled (middle row). If sufficient support is violated, in this case due to the rotation invariance introduced by the Gaussian blur, the model unable to learn the rotation transformation. he reported OOD MSE is calculated for samples with blur=0.
zero-row/column), The sufficient support assumption guarantees that the training contains some configuration of the second vector (matrix) with zero elements at different locations.
D
Additional experiments
D.1
Composition of Object Attributes
To demonstrate that the considered function class does not only apply to the composition of objects can also model the composition of object altributes, consider modification of our sprite setting, which each image contains a single sprite with configured by the three attributes rotation, color, and blur. Figure 8 illustrates the resulting data. We chose these attributes because, outlined in the previous section, they illustrate the connection between the sufficient support assumption and transformation invariances. Additionally, these attributes can be implemented with simple composition operation: convolution. The resulting generating process can, thus, formulated as
f(z) = C({(2)) = (z1) (22) * (2((2))
(30)
where ii renders the sprite with a specific rotation, S22 generates a convolution filter that changes color, and (P3 generates Gaussian blur filter.
As shown in Figure 8, the sprite's appearance is invariant rotations whenever strong Gaussian blur is applied. Consequently, to fulfill the sufficient support condition, the support of the training distribution needs be chosen such that rotations are observed on configurations for which the blur is not too strong. To demonstrate this, we train a compositional model on two different training distributions: The first one has a diagonal support as Experiment 1 #6, which fulfills the sufficient support assumption. The second one has orthogonal support as in Experiment 1 #3,4 chosen such that different rotations are only observed with a strong Gaussian blur. Figure shows reconstructions of random OOD samples for both models. While the model learns to reconstruct the color correctly on both training sets, the rotation can only be learned in the first case when sufficient support fulfilled.
19

---

Train Set
R ID
R OOD 1
AR
Orthogonal 0.676 24.8e-3
0.632 #2.9-33
0.04425.6e-3
Orthogonal with gap
0.560 =1 -1500-2
0.345 #1.30-2
0.215 #2.00-2
Table 3: Experiment results on CLEVR [35]. On an orthogonal training set (Equation 31) that fulfiils the assumptions from Theorem 1, compositional model is able to generalize compositionally. as indicated by the minuscule difference in performance on ID and OOD points. When the composi- tional support assumption is violated by introducing a gap in the support one latent, generalization fails, and the difference between ID and OOD performance increases significantly. The overall lower ID performance on the training set with a gap (and the corresponding proportionally lower OOD performance) are due to the smaller number of samples in this training set, explained below. Results are averaged over three seeds.
D.2 Compositional generalization on CLEVR
We additionally conduct experiments on the CLEVR dataset [35], a popular benchmark for compo- sitional generalization and object-centric learning. The original CLEVR dataset consists of simple 3d scenes containing a varying number of objects configured by their x-position, y-position, shape, color, size, and orientation. While CLEVR comes with the code generate cannot be controlled precisely: Objects are always positioned randomly, no specific combinations of object attributes other than the relation between shape and color can be controlled, and collisions always avoided. As a result, we cannot easily generate large, controlled training sets with precisely defined supports and distributions as in Section 4 and instead opt to filter the existing dataset.
samples, generation
Specifically, we select all 13145 images containing exactly three objects (since Theorem implicitly assumes that the number of slots is known). We filter orthogonal training set similar to the one described in Equation 2, except that we have three slots and replace equality to the base configurations with distance measure d, i.e.,
supp P = {z) E 21, E 22, E Zz)(d(z1. x)) < d(zz, 29) < < d(zz. 29) < 8)
(31)
This modification is necessary since barely any two samples use the exact same configurations of an object. For our experiments, we use 0.495 and set aside 10 % of the samples for evaluation. We end up with 4523 ID training samples, 502 ID test samples, and 8 120 OOD test samples.
We train a compositional model as outlined in Section 4 and shown in Figure 6, except that we add an additional upsampling and convolution layer to get to final output size of 128 128 x 3.
The results summarized in Table 3: On the orthogonal training that satisfies the assumptions from Theorem 1, ID and OOD performance are nearly identical, indicating that the model is able to generalize OOD. However, if we introduce gap in the support of 1 in Experiment #9 in Section we see that the gap between ID and OOD performance increases significantly, showing that violating the compositional support condition prohibits generalization. Note that since the IDD and OOD sets are filtered from a fixed pool of samples, introducing this gap in the ID set effectively reduces the size of the ID training and sets 3254 and 361, respectively. The drop in ID performance and proportional decrease in OOD performance can be attributed to the reduced size of the training set.
20


Reviews:
[{"review_id": "fYedXNRr0i", "reviewer": "Reviewer_yWdt", "summary": "This work combines the compositional generalization problem with the data generation process and mathematically defines and formalizes the relevant framework. In this process, two main conditions are proposed: the first is the condition for a given problem to be considered a compositional generalization problem (compositional support), and the second is the condition that ensures the compositional generalization problem can be compositionally generalized (sufficient support). In the proposed theorem, the authors proved that the approximated composition function generalizes to unseen data if two main support conditions are met. In the experiments, the proposed theories are validated by training models under various train set distributions and evaluating their performance on out-of-distribution test sets that include novel compositions.", "questions": "1. Are there any other examples that explain the relationship between composition function and sufficient support such as occlusion?", "limitations": "Authors mentioned limitations in the paper, while more empirical experiments for validating the theorem seem necessary.\n\n[1] Neural Systematic Binder (ICLR 23)", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The concepts that have been implicitly used in the field of Compositional Generalization are mathematically defined and formalized, which can be valuable for future work related to compositional generalization.\n2. The theorem related to sufficient support is quite interesting.", "weaknesses": "1. The attempt to support and validate the previously stated theories through experiments is commendable, but the connection seems somewhat weak. For example, while Theorem 1 describes the sufficient condition in a concrete manner using mathematical tools, the concepts of broad support and narrow support used in the experiments appear to be somewhat qualitative. It would be interesting to know if there were specific mathematical criteria or other considerations involved in determining the broadness of the support.\n2. It would be beneficial to have more explanation about the Collapsed Composition Function in the Violation Condition section. The provided explanation alone does not entirely justify why RGBa performs better. Specifically, in the case of RGBa, the performance seems not only to be comparable to other cases that satisfy different sufficient conditions but also noticeably better. If it can still be understood that RGBa achieves compositional generalization even with similar performance, it becomes acceptable for the performance to be somewhat lower. However, the part where performance is significantly better remains questionable, and it would be interesting to know if there are additional hypotheses to explain this phenomenon.\n3. More experiments are required for empirical validation of the theorem. There are some datasets that consists of diverse factors for compositional generation (e.g., MPI3D, Shapes3D). It would be nice to see the results on those more complex and diverse-factored scenes. Also, there can be various types of composition functions that include factors (e.g., noise, illumination) in real nature. The experimental results on how the sufficient support can be satisfied on different composition functions can be done. \n4. The theorem assumes the ground truth latent and the known composition function. While the support condition in unsupervised setting is harder to derive, empirical experiments can be done using scene factorization methods ([1]) and various composition functions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer yWdt for reviewing our paper and providing helpful suggestions. While we hope to have already captured most of your concerns in our global reply above, we would like to also address your individual concerns here.\n\n1. (Weakness 1.) We agree that the explanation of *broad* and *narrow* supports in the experiment was purely qualitative and should have been more detailed and rigorous. **We now include the specific mathematical criteria and considerations involved in determining the broadness of the support** in a **newly added Appendix C “Details on sufficient support assumption”**. The corresponding sections now read:\n    \n    **Orthogonal sampling** As explained in the main text and illustrated in Figure 4, occlusions make the output image invariant to changes of the background sprite in the occluded pixels. The model does not receive a training signal for these pixels and reconstruction becomes impossible. In the case of orthogonal sampling, the foreground sprite is fixed in its base configuration (orange triangle in the bottom left corner) whenever the background sprite is sampled randomly, see first row of the **newly added Figure 6**. The foreground sprite therefore always occludes the same background pixels, for which the Jacobian $\\frac{\\partial\\boldsymbol C}{\\partial\\boldsymbol \\varphi_{km}}$ is zero. Therefore, for each configuration of the background sprite a second data point is required in which the foreground sprite occludes a different and distinct set of pixels (cyan square in the second row of Figure 6). We can clearly observe that this is the case here; therefore, the Jacobians $\\frac{\\partial\\boldsymbol C}{\\partial\\boldsymbol \\varphi_{km}}$ from both samples have zero entries at different indices $m$ and their sum has full rank. The resulting sufficient support has the shape illustrated on the left of Figure 5.\n    \n    **Diagonal sampling** As explained above, sufficient support for occluding sprites is guaranteed if the dataset contains at least two samples with the same background sprite and different foreground sprites that overlap distinct pixels (as also illustrated in Figure 6). In the diagonal sampling case we therefore need to choose the width of the diagonal broad enough to guarantee that it contains such foreground sprites. The smallest possible width of the diagonal can be determined by finding the smallest possible x-offset (or y-offset) for which a pair of sprites of the smallest scale does not overlap. This is the case for a width of 0.2, which was used for the *diagonal* sampling case in Table 1 #6. The *broad diagonal* sampling case Table 1 #8 used a width of 0.4 (double the minimal width), while the *narrow diagonal* sampling case in Table 1#10 used a width of 0.1 (half the minimal width).\n    \n\nIn the same appendix, **we now elucidate the relationship between composition function and sufficient support** (Question 1) for other examples and data modalities, as also briefly outlined in the global response.\n\n2. (Weakness 2.) We agree with the reviewer that “RGBa [performs] noticeably better”, even OOD. The example was included to illustrate that there exist models which do not satisfy all the conditions of our theorem while still generalizing decently. This is not surprising, as our theorem merely states *sufficient conditions* which enable generalization, not *necessary conditions* that prohibit generalization if violated. We believe that the existence of such an example does not diminish the usefulness of having conditions that guarantee generalization. We included this example in the hope that future work can build on our results derive weaker sufficient conditions. **We acknowledge that this part was confusingly worded in the paper and adjusted the section accordingly**. As to why RGBa performs slightly better: We believe that the parameterization of the problem as alpha compositing (as detailed in Equation 26 in Appendix B) is slightly more amenable to training with SGD since no approximation of step functions (see Equations 25 and 26 in Appendix B) is necessary. In the finite-sample-finite-width training setting, RGBa is then able to fit the data slightly better. However, **the gap in performance is practically identical to the RGB case (0.005 vs. 0.006)**, indicating that the model does not “generalize better”.\n3. (Weakness 3 and 4) **We have conducted an additional experiment** with different component and composition functions to further demonstrate the generality of our theorem. For more details we kindly direct the reviewer's attention to points 8 and 9 in the global response and the accompanying rebuttal document. As highlighted in the concluding section of our global response, we kindly ask to judge the value of our contribution based on the theoretical results which make up the bulk of our work and greatly improve upon prior works. The application of our results to more complicated real-world datasets which are substantially harder to analyze is a direction we intend to explore in subsequent works.\n4. (Weakness 4.) As explained in point 6 of our global response extension to an unsupervised setting is far from trivial."}, {"review_id": "nt2O7lp0Ki", "reviewer": "Reviewer_zapL", "summary": "In this work, compositionality is examined as a fundamental attribute of the data-generating process, rather than being solely associated with the data. By establishing a precise mathematical framework, it aims to comprehensively analyze and understand compositional generalization. Notably, the work identifies a series of sufficient conditions that enable compositional generalization, highlighting the presence of these conditions in various existing approaches. It validates these observations on a synthetic task on images containing sprites with variable appearance.", "questions": "- Can this approach provide any insights into compositional generalization in scenarios where the ground-truth data generating process $\\mathbf{f}$ operates on latent factors $\\mathcal{Z}$ that are either unknown or only partially known (e.g. only the number of factors is known)? Providing more insight and possible future directions in lines 259-264 would be appreaciated.\n\n- Is it possible that there exists a threshold in model complexity or train dataset size beyond which compositional generalization naturally emerges?\n\n- In line 161, what is the meaning of the composition function $\\mathbf{Id}$? Is is assumed to be the sum?", "limitations": "The limitations are adequately discussed in Section 5 and 6.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- This work delves into the exploration of compositionality as a characteristic inherent to the data generating process, drawing inspiration from the literature on identifiable representation learning. To the best of the reviewer's knowledge, this is the first work that approaches compositionality from this particular perspective.\n\n- The synthetic experimental setup, despite its limited scope, is solid; and the results are convincing with reported mean and standard deviation over multiple seeds.\n\n- The ablation study conducted in lines 238-247 provides compelling evidence that violating specific conditions leads to a noticeable decline in compositional generalization. This observation is further supported by Figure 5, which clearly depicts instances of generalization failure precisely where the conditions are violated. These combined findings reinforce the validity of the conclusions.\n  \n- Further details are provided in the supplementary material, and anonymized code facilitates the reproducibility of the experiments.", "weaknesses": "\n- One weakness of this work is that all the conducted experiments focus on a single task. While the findings are valuable and provide insights, it would be beneficial to validate them on a  wider range of tasks. By demonstrating the generalizability of the observations across multiple tasks, and potentially across domains beyond images, the overall strength and impact would be significantly enhanced.\n\n- Table 1 presents the performance metrics of both the in-domain (ID) test set and the complete test set (all), which comprises both the ID and the out-domain (OD) test set. To enhance readability and hihglight the individual contributions of ID and OD to the overall performance, it would be beneficial to include separate columns specifically dedicated to the OD performance.\n\nMinor:\n- Broken reference at line 23\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to reviewer zapL for their thorough review of our paper, for highlighting the paper’s strengths, and for providing valuable suggestions. While we have already tackled a number of concerns outlined in our global response and will proceed to address specific questions below.\n\n1. (Weakness 1) **We have conducted an additional experiment** with different component and composition functions to further demonstrate the generality of our theorem. For more details we kindly direct the reviewer's attention to points 8 and 9 in the global response and the accompanying rebuttal document. We acknowledge that our new experiment remains within the image domain but maintain the conviction that our claims hold true across various domains. We kindly refer the reviewer to points 1-4 in the global response, where we **illustrate how our theory can be applied across multiple tasks and domains**.\n\n2. (Weakness 2): We understand that it is desirable to see the “pure” OOD performance in addition to the performance on the entire test set. However, as the training sets in most cases are planes through a high-dimensional latent space, the **ID samples in the entire test set generally make up less than 0.1% of samples**, so that the “pure OOD” performance would does not differ significantly from the “all” performance. The suggestion to make the table more readable was valuable however, and **we now report the ID and all performance, as well as the gap between them. We’ve also reformatted the standard deviations to be less obtrusive and relegated the MSE to a second table in the appendix**. We’re happy to include the reformatted table in the camera ready version, but couldn’t fit it in the rebuttal pdf due to space constraints.\n\n3. (Minor Weakness) **We fixed the reference in line 23**.\n\n4. (Question 1) As explained in point 7 of our global response extension to an unsupervised setting is far from trivial.\n\n5. (Question 2) This is an interesting question. The theoretical setting doesn’t make assumptions on the sample density in the training distribution, in principle allowing for infinite samples. Even then, we only provide *sufficient* conditions, which means we cannot rule out out the possibility that compositional generalization might always emerge for large, complex models or for models with certain architectures. Outside of the infinite-sample setting, we cannot make any claims about the relationship between training set size and generalization capability. This relationship would most likely depend on the specific densities of the training distribution, on which we deliberately don’t pose any assumptions. We hope to extend our work to such settings in the future.\n\n6. (Question 3) **Fixed line 161**, $Id$ should be $\\sum$; thanks for catching that!"}, {"review_id": "5F4E6qCzlc", "reviewer": "Reviewer_SW1j", "summary": "This paper proposes formal conditions on a data generating procedure such that \"compositional generalization\", i.e. generalization to unseen combinations of elements observed during training, can be shown to be possible. The authors construct a toy task and show empirically that when the proposed conditions are met, models can generalize in the predicted way.", "questions": "See weaknesses above.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* The term \"compositional generalization\" is often only intuitively defined in prior work. A better theoretical understanding of the constraints between training and test distributions would be helpful. This paper proposes a theoretical framework regarding what conditions must be met regarding the training and test distributions for compositional generalization to be possible, albeit for a relatively limited case and for an implicitly considered class of models.", "weaknesses": "* The case considered is a very limited form of compositional generalization, motivated by decomposing images into multiple objects. This is fine, but I think the limited scope of the paper and theory should be clearer, unlike in the current paper, which includes claims such as \"conditions... which are sufficient for compositional generalization\". It does not seem like the proposed model would be a good fit for the data generating procedure of more commonly studied cases of compositional generalization, such as those arising in mapping natural language to its semantics (e.g. https://arxiv.org/abs/1711.00350). In these case, the data generating procedure has a more hierarchical, potentially recursive, compositional structure.\n* The empirical experiments are limited to a toy dataset constructed by the authors. It would be more compelling if the authors could show how the proposed conditions apply to existing datasets that have been proposed (and accepted by the community) as evaluating \"compositional generalization\". \n* The proposed conditions seem rather strong. The limitations section mentions that models with various inductive biases could allow relaxation of some of the proposed conditions. At the same time, the authors implicitly assume some strong conditions on the model, e.g. that it factors similarly to the proposed model for the data generating procedure. A more satisfying theoretical framework might more explicitly consider what inductive biases are necessary for the model to be sufficiently specified by the training data such that it generalizes to the test distribution.\n\nNits:\n\n* Line 23 - missing reference\n* The notation used in equation 2 was not clear to me. What is $z_k^0$? I didn't see where the superscript notation $^0$ for the latents was defined.\n* The notation used in equation 3 was not clear to me. The `supp` operator defined in equation 2 does not have a subscript, but equation 3 introduces a subscripted latent.\n* Line 149 - distribution -> distributions", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer SW1j for reviewing our paper and for lauding our effort to formalize notions of compositional generalization. While we hope to have already captured most of your concerns in our general reply above, we would like to also address your individual concerns here.\n\n1. (Weakness 1): Our work primarily addresses compositional generalization on the continuous supervised regression setting. We concur with the reviewer's perspective that there's room for improving the emphasis on this aspect, and **have adapted the introduction and method sections as well as the discussion to more clearly explain the limitations of our work**. We have included these limitations in the global reply points 5-7. As explained there, our framework does not readily extend to NLP data generating processes like the one in [1]. We maintain, however, that our theory is applicable to a wide range of compositions in various data domains and tasks, as outlined in the global reply in points 1-4.\n2. **We have conducted an additional experiment** with different component and composition functions to further demonstrate the generality of our theorem. For more details we kindly direct the reviewer's attention to points 8 and 9 in the global response and the accompanying rebuttal document. We acknowledge that our new experiment remains within the image domain but maintain the conviction that our claims hold true across various domains. As highlighted in the concluding section of our global response, we kindly ask to judge the value of our contribution based on the theoretical results which make up the bulk of our work and greatly improve upon prior works. The application of our results to more complicated real-world datasets which are substantially harder to analyze is a direction we intend to explore in subsequent works.\n3. We thank the reviewer for pointing out the interesting work [2]. We acknowledge that we are not the first to give a formal definition for compositional generalization. However, as also pointed out by the reviewer, such a formalization requires tractable assumption to derive any theoretical guarantees, which the formulation in [2] is lacking. It's crucial to emphasize that our study's objective is to establish a formal framework for addressing compositional generalization within the context of regression to continuous data domains. **We kindly request the reviewer to elaborate how a formalization as in [2] could facilitate this**. We rather see our work as a continuation of [3, 4], which we cite in our introduction and related works section. Compared to these earlier works, our method allows for much more a more versatile function class with minimal assumptions on the training distribution. \n4. As addressed in our reply to point 3. and outlined in points 1-4. and the final paragraph of our global response, we maintain that our proposed conditions are much weaker than those of previous works [3, 4]. We acknowledge that we trade-off some assumptions on the data distribution for slightly stronger conditions on the data-generating process, but we do not agree with the reviewer that one kind of assumption is “more theoretically satisfying”. In practice, conditions on the model are much easier to enforce and are often key in identifiability settings which our work aims to lay the foundation for. **We kindly request the reviewer to elaborate why conditions on the data distribution should be preferrable to conditions on the function class.**\n\n[1] https://arxiv.org/abs/1711.00350\n\n[2] https://arxiv.org/abs/2112.07610\n\n[3] https://arxiv.org/abs/2211.11719\n\n[4] https://arxiv.org/abs/2304.14329"}, {"review_id": "qSeS1qOZuX", "reviewer": "Reviewer_5Ysh", "summary": "Compositional generalization, which is easy for humans but hard for deep neural networks, gradually attracts more attention. Different from most existing works focusing on how to train a more to compositionally generalize well, this paper aims at the characteristics of the datasets. It tries to find sufficient conditions for the dataset to make compositional generalization possible. Specifically, the paper claims that the compositional data-generating process is the key to compositional generalization. It also proves a set of sufficient conditions under which models trained on the data are able to generalize compositionally. The proposed theory is verified by a manually designed vision dataset. \n\nThe paper studies a very important problem from a unique perspective, which is novel to me. The theoretical analysis also has the potential to be extended to more general scenarios. However, I do have some concerns and confusion about the current version. I wish the authors could clarify some of them during the rebuttal phase. So I would give the current version a borderline accept, and I would be happy to increase my score if my following concerns are resolved.", "questions": "1. There is one citation missing (i.e., the ? mark) in the introduction part.\n\n2. It is easy to misunderstand Figure 1. It would be better to align the left and right panels and directly put the subtitle of different rows on the figure, e.g., row 3 contains images generated by the model, and row 4 contains the targets.\n3. In the second paragraph of section 3.1, the subscript should be $z_{2,x}$\n4. What are $z_2^0$ and $z_1^0$ in equation 2?\n5. Figures 3 and 4 use similar styles, but I guess they are discussing different things. In Figure 3, the x and y axis can be any attributes, e.g., position, color, etc., but those in Figure 4 seems only to refer to x and y positions.", "limitations": "1. For the experimental part, it would be helpful to demonstrate what the monolithic and compositional models look like (maybe in the appendix): it would be hard to imagine the difference between them without the diagrams.\n2. IIUC, the models used in the experimental parts are vanilla deep neural networks. Showing results on some models (and algorithms) designed for disentanglement or compositional learning might strengthen the paper a lot. The emergent-communication-based methods [1,2] or VAE-based methods [3] are both good options.\n3. The problem studied in [3] might be highly correlated with this 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.\" *NeurIPS 2022*\n\n[2] Ren, Yi, et al. \"Compositional languages emerge in a neural iterated learning model.\" ICLR 2020\n\n[3] Schott, Lukas, et al. \"Visual representation learning does not generalize strongly within the same domain.\" ICLR 2022", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "See the summary part.", "weaknesses": "Based on the definition in section 3.1 and the illustrative example in Figure 2, it seems that the compositional data generation needs multiple objects. For example, in equation 1, each $\\phi_i(z)$ determines one object and function $C$ is used to combine them into a single input signal (like putting different objects on the same image). However, different $\\phi_i(z)$ can also be different parts or different characteristics of ONE object. For example, we can use $\\phi_1(z)$ and $\\phi_2(z)$ to represent the silhouette and fillings of the same object (then $z$ should be some low-level semantic concepts, like different edges for silhouette and texture + color for the fillings). My main concern here is that in practice, the form of compositionality could be various, not only for different objects (parts) on the same input signal. The theoretical framework proposed in this paper also has the potential to cover those more general compositional relationships. The example proposed in the paper narrows down the scope of the theory. I think it would be very helpful to broaden the scope by providing extra examples that are quite different from the sprites one (e.g., an NLP example) but can still be explained by the theorem. This will strengthen the paper a lot.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer 5Ysh for reading our paper, for commending the novelty and relevance of our approach, and for asking intriguing questions. We have clarified some concerns in the global response to all reviewers. Nonetheless, we would like to address some specific points below:\n\n1. We concur with reviewer 5Ysh that “attribute compositions” are a very interesting and relevant setting. We hope to have illustrated in the **additional examples for possible composition functions in points 1-4 of the global response** and with our **added experiment** that **this is indeed captured by our setting** and that **the compositional data generation does not require multiple objects**. We selected the multi-object (multi-sprite) setting due to its growing significance in ML research and its suitability for visualizing the various conditions to the reader. That said, we emphasize again that we assume a *continuous* data domain with differentiable mappings, which is not applicable to most NLP tasks.\n2. (Question 1) **Fixed citation in line 23**.\n3. (Question 2) We **revised Figure 1** and included it in the pdf of the global rebuttal; we hope it is much clearer now.\n4. (Question 3) **Fixed typo in line 100**.\n5. (Question 4) In our multi-sprite running example, $z_1^0$ and $z_2^0$ referred to the base configuration of the components in the orthogonal sampling scheme. We indeed failed to introduce this notation properly and **have since clarified this in the text**, thanks for catching it!\n6. (Question 5) We agree that the relationship between the figures is slightly confusing. Figure 3 illustrates the concept of *compositional support* for 2 components with 1-dimensional marginals (e.g. 2 components with a single attribute). The same concept applies to the 2 components with 5-dimensional marginals (5 attributes shape, color, x, y, …) although this is of course not easily visualized. Figure 4 instead visualizes a 2d projection of the 10-dimensional latent space in order to pinpoint the example images. In the projection, the color, shape, x-position and scale dimensions are not shown explicitly and the axes correspond to the sprites’ y-position. **We have updated the figure captions to clarify the difference.**\n7. (Limitation 1) **We have added a schematic diagram for the monolithic and compositional models in the appendix** which we omit from the pdf response due to space constraints. As outlined in the experiments section, the compositional model uses the same architecture for each $\\varphi_k$: 4 fully-connected layers with 256 hidden units map the latent to a 32×4×4 feature map which is followed by 4 Upsample+Convolution layers with 32 channels mapping to a 3×64×64 slot outputs. The slot outputs are combined using the composition $C$. The monolithic model uses the same number of layers but with 320 hidden units and 64 channels to match the number of parameters in the compositional model.\n8. (Limitation 2) We thank the reviewer for pointing out interesting work on compositional learning. The architectures presented in [1, 2] are LSTM based and are used for autoregressive, discrete sequence-to-sequence modelling. On the other hand, VAE-based architectures in [1, 3] focus on unsupervised representation learning. Our work instead focuses on the supervised regression setting in a continuous data domain. As outlined in the global response in point 5, a translation to (discrete) NLP tasks or unsupervised settings is not straight forward. However, **it is worth noting that the models employed in our experiments incorporate convolutional and fully-connected layers, mirroring the architecture of VAE decoders as used in [1, 3] and analogous to the regression models tested in [3]**.\n9. (Limitation 2) The reviewer is correct that [3] is highly correlated with our setting. In fact, **[3] was a direct inspiration for this work as stated in the introduction and the first part of the related work**. The failure (and difficulty) of compositional generalization (even in regression settings) that our work is addressing was first demonstrated in [3]. However, [3] did not provide a thorough analysis of why generalization fails or provided conditions under which it is possible. We believe our work to be the first to address this in a comprehensive manner.\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.\" *NeurIPS 2022*\n\n[2] Ren, Yi, et al. \"Compositional languages emerge in a neural iterated learning model.\" ICLR 2020\n\n[3] Schott, Lukas, et al. \"Visual representation learning does not generalize strongly within the same domain.\" ICLR 2022"}, {"review_id": "WaTVXVJBP6", "reviewer": "Reviewer_1tYF", "summary": "This paper theoretically investigates mathematical conditions for compositional generalization.\nIt defines compositional representation and compositional support, then derives a set of sufficient conditions on training distribution support and model architecture.\nIt also conducts empirical validation and ablation and demonstrates the application of the theory in real-world scenarios.", "questions": "Please respond to the weakness section.\n\n(4) It might need a check for line 68: ``The OOD generalization ... where train and test distributions differ in their densities, but not their supports ...``.\nIf OOD means \"Out-of-distribution,\" it seems to treat disjoint supports.", "limitations": "The limitations are mentioned mainly in the discussion section.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The lack of compositional generalization ability has been a longstanding problem, and it is good to have a theory for it.\n\n- The definitions and the theorem are clearly stated.\n\n- The theorem has a general form, indicating potential wide application.\n\n- The theorem is derived strictly.\n\n- The theorem covers a wide range of existing approaches.\n\n- The running example helps to explain the concepts and ideas.\n\n- The experiments validate the theoretical results.", "weaknesses": "The setting is strong so the theorem is weak and only covers limited cases.\nAlthough this is an early work, it is still good to have wide coverage.\n\n(1) The input is disentangled factors, but many problems have entangled inputs.\n\n(2) It is not discussed whether the theorem applies to parametric composition function C.\nThough the generative processes are known in many interesting scenarios (line 272), we may not know the exact parametric values in the process, e.g., generating a human face from face parts.\nIn such a case, we may treat the composition process as a parametrized model, and the parameters are learned during training.\nHowever, the parameters may fit the training data and not generalize to test data.\nIt means equation (9) in the proof does not naturally hold.\n\n(3) It would be helpful to have an experiment on a complicated problem that fits the settings and satisfies the conditions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for reading our work and for commending the clarity of work. We encourage the reviewer to check our global response where we have addressed some of their concerns, nonetheless we address some specific points here:\n\n1. (Weakness 0: “The theorem is weak and only covers limited cases”) We agree that the theorem does not encompass all possible formulations of compositional generalization. However, **we hope to have clarified in points 1-4 of the global response that our theory still covers many different settings in various domains**. As also outlined there in the final paragraph of the global response, compared to earlier works on the same problem (chiefly [1, 2]) our assumptions on the composition function are much weaker and cover many more interesting cases. Diverging from these mentioned approaches, our work distinguishes itself by providing sufficient conditions that enable compositional generalization of a broader function class, while making minimal assumptions on the train and test support.\n2. (Weakness 1) To enhance clarity for our readers, we employ the multi-sprite setting featuring 'disentangled' factors as a means to elucidate our methodology. A our theory makes no assumptions on the relationship of latent factors across or within each slot, our theorem is valid for inputs that contain ‘entangled’ factors. What’s more, **the diagonal sampling case in our experiments demonstrates that our theorem holds for highly correlated inputs**.\n3. (Weakness 2) **Our theorem does apply to differentiable parametric functions C that remain fixed across the entire domain**. In practice, as the reviewer correctly notices, training a parametric composition function on only a subset of the entire domain will make it difficult to guarantee its behavior outside the training set. Even so, for specific parameterizations of C this might be possible; we are in fact exploring this direction in a follow up to this work. Besides that we want to stress again that prior work [1] also assumes knowledge of $C$ and additionally only allows $C$ to be from a very limited function class. **Our work therefore constitutes a considerable step forward from this methods.**\n4. (Weakness 3): **We have conducted an additional experiment** with different component and composition functions to further demonstrate the generality of our theorem. For more details we kindly direct the reviewer's attention to points 8 and 9 in the global response and the accompanying rebuttal document. As highlighted in the concluding section of our global response, we kindly ask to judge the value of our contribution based on the theoretical results which make up the bulk of our work and greatly improve upon prior works. The application of our results to more complicated real-world datasets which are substantially harder to analyze is a direction we intend to explore in subsequent works.\n5. (Question 1): The reviewer is correct that a better distinction between out-of-distribution (OOD) and out-of-support settings (OOS) is needed. In our work, we use the term OOD to encompass both OOS settings and settings where the densities differ, but not the support (for lack of a better term, we call this out-of-density here). In L68, we meant to say many prior works study out-of-density settings but not out-of-support settings. Our setting encompasses both, but compositional generalization clearly becomes trivial in out-of-density settings. **We have rephrased the section to better explain this distinction.**\n\n[1] https://arxiv.org/abs/2211.11719"}]

Author rebuttal:
We would like to thank all 5 reviewers for their time and valuable feedback!

We appreciate their assessment of our work as **“valuable for future work related to compositional generalization”** (yWdt). The reviewers concur that **“the lack of compositional generalization ability has been a longstanding problem, and it is good to have a theory for it”** (1tYF) and find that **“the paper studies a very important problem from a unique perspective”** (5Ysh) by addressing a setting which **“is often only intuitively defined in prior work [and for which] a better theoretical understanding […] would be helpful”** (SW1j). The reviewers commend the paper as the **“first work that approaches compositionality from this perspective”** (zapL) which **“has the potential to be extended to more general scenarios”** (5Ysh).

While the some reviewers praised the theorem’s **“general form, indicating potential wide application”** (1tYF) and its ability to **“cover a wide range of existing approaches”** (1tYF), some questions about the applicability of our results to other settings remain. We realize this should have been clearer in the paper and provide a short list of examples here that we **have included in a new section.**

The theorem **can cover**, e.g.:

1. **Additive compositions with occlusion** as shown in the paper. This composition function can model many object-centric datasets [2]. Even this simple composition function was outside the scope of prior work [3, 4]. We chose it as running example in the paper for ease of visualization.
2. **Attributes/transformations of an object**, e.g. with components shape, translation, color of a sprite composed in pixel space by a convolution or matrix multiplication. Or the components could be scale, shear, rotation, translation, projection in 3d applied to an object’s mesh by matrix multiplications. *Sufficient support* is violated whenever the parameterized transformations produce invariances, e.g. when a circular object should be rotated and the gradient of the rotation component cannot be reconstructed from the output.
3. The components could be **audio signals** that are overlayed with a $\max$ operation to model finite microphone gain. *Sufficient support* is violated if one signal saturates the microphone and drowns out the other.
4. **Vector or matrix products** The components are arbitrary vectors or matrices and the composition function is their (outer) product. *Sufficient support* is violated if an element (row/column) in the second vector (matrix) is zero. In that case the multiplied element (column/row) in the first vector (matrix) cannot be reconstructed.

The theorem **cannot cover:**

5. **Discrete data domains** such as NLP tasks or symbolic reasoning, as we assume continuous, differential mappings between the component latents and composition.
6. **Unsupervised Settings**. If data-generating process or latent factors are (partially) unknown, the model’s inferred representation can have an arbitrary relationship to the ground-truth latent space. Before generalization can be addressed, this problem of *identifiability* needs to be solved. There exists no prior work addressing identifiability on restricted training sets $P$. An extension of our results to unsupervised settings is, therefore, far from trivial. As prior work [1] suggested, generalization is already an interesting and challenging problem in the regression setting we examine. We are confident that our results constitute a **step towards a comprehensive theory of *generalizable identifiability* that encompasses the unsupervised case** and are motivated to address this problem in future work. **We realize that the discussion section was insufficient in explaining this issue and have updated it.**
7. **Hierarchical compositions**, as we consider only a single composition function.

While the reviewers commended our existing **“solid experimental setup”** (zapL), and mentioned that the **“experiments validate the theoretical results”** (1tYF), there were some calls for additional empirical validation. We thank the reviewers for suggesting a setting where each component models a “different characteristic of ONE object” (5Ysh) which **we now implemented and added to the paper (Experiment 2)**:

8. The data consists of square shapes with random rotation, color, and Gaussian blur, each modelled by one component and combined using a convolution operation as the composition function (see Fig. 7). The setting further highlights the generality of our theoretical setting.
9. Since the reviewers asked for “experimental results on how the sufficient support can be satisfied on different composition functions” (yWdt), we assess performance on two sampling schemes: a diagonal one which satisfies *sufficient support* and an orthogonal one which violates it. As explained in points 2. above and illustrated in Fig. 8, violating *sufficient support* leads to invariances in the training data that the model cannot resolve.

Finally, we wish to position our work thoughtfully within the broader literature landscape. **Our main contribution is a theoretical analysis of compositional OOD generalization and we hope the work can be evaluated as such**. There exist only a couple of studies [3, 4] that directly confront this issue, both of which approach it from a different direction (assuming specific distributions) and impose much stronger limitations on the composition function. **We kindly request the reviewers to assess our work within this context.**

[1] [arxiv.org/abs/2107.08221](http://arxiv.org/abs/2107.08221)

[2] [github.com/deepmind/multi_object_datasets#multi-dsprites](http://github.com/deepmind/multi_object_datasets#multi-dsprites)

[3] [arxiv.org/abs/2211.11719](http://arxiv.org/abs/2211.11719)

[4] [arxiv.org/abs/2304.14329](http://arxiv.org/abs/2304.14329)

Meta-review: The paper provides a theory of compositional generalization by taking a bottom-up approach by focusing on the data-generating process rather than the data itself. Through this lens, it offers mild conditions on the training distribution and model architecture that are necessary for achieving compositional generalization and validates these conditions both theoretically and empirically.

Overall, the reviewers acknowledge the paper's strength in presenting a mathematically rigorous and novel perspective on compositional generalization. The theoretical framework and theorems offered are seen as significant contributions that can potentially have a broad impact on future research. However, reviewers have pointed out certain weaknesses, such as the limited scope of empirical experiments and the focus on a single task, which could be improved to strengthen the paper's arguments. Some of these concerns were not fully addressed in the rebuttal. Nevertheless, the paper’s core contributions are solid and provide a novel way to understand an important problem in machine learning. Therefore, the paper is recommended for acceptance.
Decision: Accept (poster)