How Compositional Generalization and Creativity Improve as Diffusion Models are Trained
Authors: Alessandro Favero
Antonio Sclocchi
Francesco Cagnetta
Pascal Frossard
Matthieu Wyart
Venue: ICML 2025 poster (2025)
Keywords: Science of deep learning
compositionality
diffusion models
probabilistic graphical models
sample complexity
generalization
Primary area: deep_learning

Abstract: Natural data is often organized as a hierarchical composition of features. How many samples do generative models need in order to learn the composition rules, so as to produce a combinatorially large number of novel data? What signal in the data is exploited to learn those rules? We investigate these questions in the context of diffusion models both theoretically and empirically. Theoretically, we consider a simple probabilistic context-free grammar - a tree-like graphical model used to represent the hierarchical and compositional structure of data such as language and images. We demonstrate that diffusion models learn the grammar's composition rules with the sample complexity required for clustering features with statistically similar context, a process similar to the word2vec algorithm. However, this clustering emerges hierarchically: higher-level features associated with longer contexts require more data to be identified. This mechanism leads to a sample complexity that scales polynomially with the said context size. As a result, diffusion models trained on an intermediate dataset size generate data coherent up to a certain scale, but lacking global coherence. We test these predictions across different domains and find remarkable agreement:  both generated texts and images achieve progressively larger coherence lengths as the training time or dataset size grows. We discuss connections between the hierarchical clustering mechanism we introduce here and the renormalization group in physics.

How Compositional Generalization and Creativity Improve as Diffusion Models are Trained
Alessandro Favero 12
Antonio Sclocchi 1 Francesco Cagnetta
Pascal Frossard? Matthieu Wyart*
Abstract
1. Introduction
Compositional generalization, the ability to understand and generate novel combinations of known components, is fundamental characteristic of human intelligence. This skill underlies what linguists refer to as creativity (Chomsky et al., 1976): the capacity to produce an infinite number of novel and well-formed expressions from a finite set of rules. Under which conditions can machines learn such a skill? The success diffusion models in producing realistic data across various domains (Sohl-Dickstee et al., 2020; Song & Ermon, 2019; Betker al., 2023; Rom- bach et al., 2022) provides a unique opportunity to study how this ability emerges. Fundamental questions include: What signals in the data are exploited by neural networks to learn the compositional rules? How many training examples are needed to learn such rules, and in what order are they learned? How does the finiteness of the training affect the structure of generated data?
Natural data is often organized hierarchical composition of features. How many samples do generative models need in order to learn the composition rules, so as to produce a combinatorially large number of novel data? What signal in the data is exploited to learn those rules? We investigate these questions in the context of diffusion models both theoretically and empirically. Theoretically, simple probabilistic context-free grammar tree-like graphical model used to represent the hierarchical and compositional structure of data such as language and images. We demonstrate that diffusion models learn the grammar's composition rules with the sample complexity required for clustering features with statistically similar context, a process similar to the word2vec algorithm. However, this clustering emerges hi- erarchically: higher-level features associated with longer contexts require more data to be identified. This mechanism leads to a sample complexity that scales polynomially with the said context size. As a result, diffusion models trained on an intermediate dataset size generate data coherent up to certain scale, but lacking global coherence. We test these predictions across different domains and find remarkable agreement: both generated texts and images achieve progressively larger coherence lengths as the training time or dataset size grows. We discuss connections between the hierarchical clustering mechanism introduce here and the renormalization group in physics.
al., 2015; Ho
consider a
To address these questions theoretically, we bridge two viewpoints developed in the context of natural language processing, On the one hand, symbolic approaches aim to describe the structure of data via a list of rules that generate them. For example, prohabilistic context-free grammars (PCFG) (Chomsky, 2014) describe sentences with trees, whose nodes are hidden variables that can generate other nodes leaves according to probabilistic production rules. PCFGs can approximate both structural and semantic as- pects of text and have also been proposed for the description of images under the name of Pattern Theory (Grenander, 1996; Jin & Geman, 2006; Siskind et al., 2007). On the other hand, statistical approaches use data-driven analyses agnostic to expert knowledge of grammatical structure. A notable example is word2vec (Mikolov et al., 2013), where shallow neural network learns meaningful representations of words by merely predicting their neighborhood.
'Equal contribution 'Institute of Physics, EPFL 'Institute of Electrical and Micro Engineering, EPFL 'Theoretical and Scien- tific Data Science, SISSA 'Department of Physics and Astronomy, Johns Hopkins University. On leave from EPFL. Correspondence to: <alessandro. favero Sawesanndoo.avrr@eeeee @eter <mwyartl @ jh.edu..
Contributions We unify these two viewpoints by study- ing how diffusion models learn the Random Hierarchy Model (RHM) (Cagnetta et al.. 2024), an ensemble of sim- ple PCFGs, where production rules are drawn uniformly random. In particular,
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
We show empirically that the learning process of diffu-

---

Compositional Generalization and Creativity in Diffusion Models
sion models trained on the RHM is hierarchical, progres- sively capturing compositional rules at deeper levels of the PCFG's hierarchy.
(2025b;a) showed that diffusion on hierarchically compo- sitional data can be solved using Belief Propagation. Mei (2024) showed that U-Nets can efficiently approximate the Belief Propagation algorithm on hierarchical data. Yet, ef- ficient representability does not guarantee learnability by gradient descent for hierarchical data (Cagnetta et al., 2024). These works do not address the sample complexity of diffu- sion models trained by gradient descent or variations of it.
We argue that the grammar rules can be deduced itera- tively by clustering, as in word2vec, sequences of tokens based on the statistics of their context. For each level, we analytically derive the corresponding sample complexity.
We show that these sample complexities match the number of data required by the diffusion model to generate data that follow the grammar rules up to the corresponding level. Since this hierarchical clustering procedure requires number of samples that is polyno- mial in the size of the token sequence, this mechanism allows the model to learn a high-dimensional distribution while avoiding the curse of dimensionalityy.
Learning hierarchical representation via next-token pre- diction It has been observed that transformers trained on
next-token prediction on PCFGs learn hierarchical repre- sentation of the data that reflects the structure of the latent variables (Cagnetta & Wyart, 2024; Allen-Zhu & Li, 2023; Garnier-Brut et al., 2024). Closest to our work, Cagnetta & Wyart (2024) showed that for the prediction of the last token in a sequence of fixed length, the latent structure is learned hierarchically, with sample complexity polynomial in the context length. Our work extends this finding to diffusion models, in a setup where complete sequences can be gener- ated. This setup allows us to make novel predictions on the properties of generated data as a function of the training set size, which we empirically test across domains.
Beyond simple PCFGs, we predict that diffusion models trained on limited samples generate data that is locally co- herent (i.e., satisfying local compositional rules), but not globally, with coherence length growing with the train- ing time/number of samples. We confirm this prediction in diffusion models trained on Open WebText and ImageNet.
We conclude by discussing how the principle we put forward to build hierarchy of latent variables generalizes the renor- malization group used in physics, where coarse-grained variables are obtained by simple pooling operations.
2. Background and setup
2.1. Diffusion models
Denoising diffusion models are family of generative mod- els built to draw samples from a target distribution by in- verting a procedure in which noise is gradually introduced Gooh--Dickstein et al., 2015; Ho et al., 2020; Song & Ermon, 2019; Song et al., 2020). Let denote the time index run- ning in [0, ..... 77. and let q() be the distribution we aim to sample from, with =0)) from this distribution. A diffusion model is composed of two main parts:
1.1. Related work
Sample complexity in diffusion models Under mild as- sumptions on the data distribution, diffusion models exhibit a sample complexity that scales exponentially with the data dimension (Block et al., 2020; Oko et al., 2023). It is not the case if data lie on a cow-dimesiional latent subspace (De Bortoli, 2022; Chen al., 2023; Yuan al., 2023), correspond to Gaussian mixture models (Biroli & Mézard, 2023; Shah et al., 2023; Cui et al., 2023), Ising models (Mei & Wu, 2023), or distributions that can be factorized across spatial scales (Kadkhodaie et al., 2023a). Kadkhodaie et al. (2023b) framed sample efficiency in terms of the geometric inductive bias of neural network denoisers. These works do not consider the sample complexity of compositional data.
(2)) denoting sample
A forward process that sequentially adds noise to the data to produce the sequence (#(t))ısigr.
T
q(=(1),..... (T)) x()) = II g(((t) (x(-=())) 1)),
culminating in a purely noisy sample (TT).
Compositional generalization of diffusion models Okawa et al. (2024); Park et al. (2024) considered synthetic compositional data to empirically show how diffusion mod- els learn to generalize by composing different concepts, in the absence of a compositional hierarchy. Li & Chen (2024) studied Gaussian mixtures with hierarchical clustering struc- ture and derived the time at which different features emerge in the diffusion process. Kamb & Ganguli (2024) studied how equivariant diffusion models can compose images by combining local patches seen in the dataset. Sclocchi et al.
A backward process that reverses the noise addition step by step and is typically Iearned by training a neural network to approximate the backward transi- tion kernels p(z(t - 1)]=(t)). This corresponds to learning the score function, defined as V, logogg(a() ((=(()). Depending on the parameterization, the model may instead learn to predict the conditional expectation ()(= = ([ [[)(())=)() or alternative quanti- ties from which the score can be derived.
2

---

Compositional Generalization and Creativity in Diffusion Models
To draw a new sample from q()). one starts with noise sam- ple xTT) ~ ((x(T)) and then applies the learned backward process to obtain clean sample ==0)- ~ g(z(O)). Various diffusion models differ in how they define the forward pro- cess, depending on the characteristics of the data space. For an overview, see Yang et al. (2023).
ii) All the production rules transform one level- + 1) sym- bol into string of s level-f symbols,
1 (++1) - p1 (6)
(I)
ii) There are m unambiguous production rules per nontermi- nal symbol, ie., two distinct nonterminals cannot gener- the same s-tuple. The rules are randomly chosen and frozen for given instance of the RHM. We call the m strings produced by any given symbol synonyms;
Continuous data For continuous data, such as real-valued signals or images modeled a continuous space, Gaussian diffusion (Ho al., 2020) uses the forward transition kernel
iv) All the available production rules are equally likely.
(<((t) xxt - 1)) = (x((t)); /1 - 3, xtt 1), Br I),
Due assumptions i) and ii), the data-generatin process can be represented as regular tree graph with depth L and branching ratio 8. The leaf nodes (level e = 0) correspond to the tokens of the visible data, which form strings of size d = _ use the notation h/? to indicate the variable at level & and position i (s We define the tree distance i between visible token and (latent) tuple as the number of edges between their lowest common ancestor and the visible token. The same definition applies to the tree distance between visi- ble tokens. We define the distance between visible tokens as s where is their tree distance. Because of the hierarchi- cal structure generating the data, the visible tokens exhibit power-law spatial correlations (Cagnetta & Wyart, 2024).
where N indicates the Gaussian distribution and the se- quence (8t) is a noise schedule. At the final time T, x(T) (00.
The upper-level nodes are latent variables. We
Discrete data For discrete data, such as text, s0) consists of a sequence tokens z, 2,()), i [d]. each corresponding to symbol belonging to vocabulary V. Considering uniform diffussio process (Hoogeboom et al., 2021; Austin et al., 2021). at each time step t, tokens either stay un- changed or transition to any other symbol with some proba- bility Be. Using a one-hot-eneee monhooo-nn representation of these |V] states, the forward transition matrix reads
3 V
=
11
Bayes-optimal denoising of the RHM Knowing the production rules and the tree structure of the RHM. the probabilities of the latent variables, conditioned on some observation, can be reconstructed exactly (Sclocchi et al., 2025b) using the Belief Propagation (BP) algorithm (Mezard & Montanari, 2009). Specifically, if an RHM datum æn corrupted by some noise, e.g., via masking a fraction of tokens, resulting in a noisy observation æ,, then BP can be used to compute the marginal probabilities of any latent or visible variable, conditioned on the noisy obser- vation. Thus, using BP, the exact score function is known in these models. Here, we study instead how many samples are necessary to learn the distribution and the score from data.
where is the identity and 1 vector of all ones. The element [Q:]az indicates the probability of x; transitioning from state k to state I, i.c., [Qu]az = (xx (t)=())=((zz)
1)=k). The sta- tionary distribution achieved at the final time T' is uniform.
2.2. Probabilistic graphical models
Probabilistic context-free grammars (PCFG) To sys-
tematically investigate how diffusion models learn composi- tional structures, we consider synthetic datasets generated via a probabilistic context-free grammar (PCFG) (Rozen- berg & Salomaa, 1997): a collection of symbols and rules that prescribe how generate sequence data starting from single feature. Generic PCFGs consist of a vocabulary of hidden (nonterminal) symbols, vocabulary of visible (terminal) symbols and production rules that quantify the probability that one hidden symbol generates tuples of either hidden or visible symbols.
3. How diffusion models learn a grammar
In this section, we investigate how diffusion models learn to generate data from the RHM, and measure the sample complexity required to capture the underlying rules.
Random Hierarchy Model (RHM) The RHM (Cagnetta et al., 2024) is a particular PCFG, including the following additional assumptions to make it analytically tractable.
3.1. Experimental setting
To begin, we generate an instance of the RHM with parame- ters L (depth), (branching factor), v (vocabulary size), and m (number of synonyms). Next, we uniformly sample dis- tinct training points, i.c., sentences from the grammar. Each input symbol is encoded as a one-hot vector, x E (0, 1]
i) The nonterminal symbols are split into L finite vocabular- ies (Ve)<=1.....L of finite size u and V = Vo denotes the vocabulary of terminal symbols.
3

---

Compositional Generalization and Creativity in Diffusion Models
(1=5, 2=2 m=3)
RHM y=16 m=3)
RHM (1=55 x=2. 1= m=:
10"
109.
Crammiiaation aesurecy Ar
11
10P
10"
10-1
10-1
Cxdl N= 10
20-1-
10--
10p
M/n
20
P/
Leved C=2
10:
Lead (x2
Looed E-8
Load
10-14
Lead
Lovel m-
Lend (-5
102
10P
1(A
Number training points
Numbeer tratningg points
Teken disisnce
(a) Standard training.
(b) Online training.
(c) Token-token correlations.
Figure/ 1. Learning different levels of the grammar. (a) Accuracy various levels as function of training dataset size P. Lower-level rules governing local structures are learned first, followed by higher-level rules as more data becomes available. (Inset) The accuracy scaling matches our theoretical predictions of m ++1 samples for satisfying rules at level &. (b) Similar results hold for the online learning setting, where fresh training points are sampled at each step. (c) Token-token correlation magnitude measured for N = 10 samples generated by the diffusion model trained with P training points. As the model learns higher-level rules for increasing P. the generated samples display longer- range correlations until approaching the theoretical power-law decay with distance (red dashed line).
With this dataset, we train a Discrete Denoising Diffusion Probabilistic Model (D3PM) (Austin et al., 2021) with uniform transition probabilities (Hoogeboom et al., 2021).
choice of hyperparameters is detailed in Appendix C.
3.2. Learning the compositional rules
The diffusion model architecture is a convolutional U-Net (Ronneberger et al., 2015) with L. resolution blocks in both the encoder and decoder. Each block consists of single convolutional layer with filter size and stride followed by GeLU activation function. Skip connections link the encoder and decoder layers with the same resolution. The model also includes two embedding and unembedding layers, implemented as convolutions with filter size For all experiments, we use overparameterized networks with 8192 channels per layer.
We fix the RHM parameters and train diffusion models on datasets of varying size P. After training, we generate 1024 samples and evaluate whether the generated data satisfies the compositional rules of the RHM at different hierarchical levels. Specifically, we define the accuracy Ae at level as the fraction of generated samples that satisfy level-& rules.
Figure I(a) shows the accuracy at different levels as function of P. The results reveal staged learning process: the low-level rules, governing local structures, are learned first, followed by progressively higher-level rules that enforce global coherence. Thus, models trained on intermediate P values generate data that are locally consistent but lack global coherence.
To enable feature learning in the overparameterrzzed regime, we initialize the parameters using the maximal-update (μP) parameterization (Yang& & Hu, 2020). Since these networks have enough capacity to memorize their training set, we em- ploy early stopping, halting training when the validation loss plateaus or begins to increase. Moreover, we routinely verify that the model has not simply memorized the training data.
The inset of Figure I(a) compares favorably the scaling of accuracy with our theoretical prediction, which we will derive in the next section. This prediction indicates that learning to satisfy rules at level E requires a number of samples that scales as m Importantly, this scaling is polynomial, not exponential, in the data dimension d = s² as L increases. Specifically, the sample complexity to learn all rules is m +++1 mad m/ logs, Figure 1(b) demonstrates that the same staged learning process applies in the online learning setting, where fresh training samples are drawn at each training step.
We train the model with Stochastic Gradient Descent (SGD) with momentum, optimizing the diffusion model loss de- rived from a variational bound on the negative log-likelihood -Sohl-Dickstein et al., 2015). Following Austin et al. (2021), we use the neural network to predict the conditional expec- tation E[ (0) [z)],, which parameterizes the reverse diffu- sion process. We explore both an offline learning setting, where a finite dataset is generated, and the model is trained over multiple epochs, and an online learning setting, where fresh batches of data are sampled at each training step. The
This progressive acquisition of compositional rules also ap- pears in the internal correlations of the generated sequences, defined as the Frobenius norm of the covariance matrix between two visible tokens at distance t. As shown in Fig- ure 1(c), at small training set sizes or training times, only nearby tokens exhibit significant correlations, while long-
Following Cagnetta et al. (2024), we expect our results to remain valid for sufficiently expressive architectures, in particular, if the network depth least 2
4

---

Compositional Generalization and Creativity in Diffusson Models
RIM 21-2 s-3, 2-2
at each level of the hierarchy. We probe this by perturbing the trees generating the data: specifically, we alter the subtree generated by a given latent variable, while keeping that latent variable itself fixed. In Appendix D, we show that as the training set size increases, the hidden representations of the U-Net become increasingly invariant to such perturbations-indicaat progressively higher levels of synonyms and the emergence of more abstract representations.
1/2
Pr oc m
Arg. pisci clustering
10P
Aeg, romtest chustoring
Sumppe complesity 1 st.
Dillision model
10
reduced sensitivity to
6x 100"
10
171 10
100
4. Theoretical analysis
Figure 2. Sample complexity P for 2 in diffusion models and clustering algorithms based on correlations. Blue points show the empirical values P for trained diffusion models, while black and red points represent clustering methods based the correlations of latent tuples with the first token and the first visible tuple, respectively. The scaling 1 ~ m m=+11 aligns with theoretical predictions. Notably, the simple complexity of the diffusion model closely matches that of the correlation algorithm, suggesting that diffusion models learn hierarchical structures by leveraging statistical dependencies between synonyms.
To derive the sample complexity of the U-Net, we build upon prior work that explains how deep networks efficiently learn hierarchical tasks. This result is achieved by building lower-dimensional representation that iteratively clusters synonyms (Malach & Shalev-Shwarzz, 2018), allowing the network to recover the latent hierarchical structure of the data. This clustering mechanism is based on statistical correlations between s-tuples of tokens and the given task supe-supe or self=supervised -hiih are identical for synonyms. Notably, the sample complexity of deep networks trained with gradient descent aligns with the training set size required detect these correlations (Cagnetta et al., 2024; Cagnetta & Wyart, 2024), For supervised learning, this connection can be justified in a one-step gradient descent (GD) setting.
range correlations approach sampling noise (black dashed line, given by 1/ 1/(wN1/2), where N is the number of se- quences used to measure correlations). As training pro- gresses, long-range correlations emerge. When P 105, the correlation structure of the generated data aligns with the theoretical power-law scaling predicted in Cagnetta & Wyart (2024) (red dashed line).
Here, we extend these results to diffusion models, First, we demonstrate that learning the score function in the low- noise limit corresponds to task invariant to exchanging synonyms, and could thus be simplified by reconstructing the latent variables. Then, we compute the sample complexi- ties required to reconstruct latent variables of different levels using correlations. We conclude by showing that a cluster- ing algorithm based on correlations does indeed recover the latent variables with the predicted sample complexities, and the sample complexity required to reconstruct first-level latent variables can be recovered in one-step-Gr setting.
In Section 5, we show that this phenomenology extends be- yond our synthetic setting, consistently manifesting across various architectures and modalities. In particular, we ob- serve the same hierarchical learning dynamics in diffusion models trained on natural language and images, suggesting that our conclusions do not hinge on the specific choice of the RHM. Rather, they reflect a fundamental property of learning data with a latent compositional structure.
3.3. Dependence of sample complexity with m
To investigate the dependence of the accuracy on the number of synonyms m, we define the sample complexity p* as the training set size at which the accuracy of the last level Ag surpasses a threshold value AA". In our experiments, we set A' == 1/2 Figure shows the scaling behavior of p* with m at fixed depth L = 2 (blue points). Empirically, we find good agreement with m (dashed line in the figure).
4.1. Learning the score in the low-noise limit
Input-output correlations in diffusion models The loss function of diffusion models is minimized when the model prediction converges to the conditional expectation E| (0) (0){=)))) which is sampled in the limit of infinite dif- fusion trajectories and is proportional to the score function (Sohl-Dickstein et al., 2015; Song & Ermon, 2019; Austin et al., 2021). Since the expectation operates independently for each v-dimensional one-hot-encoded token x (0),
3.4. Emergence of hierarchical representations
To generate sequences that satisfy the compositional rules of the RHM, the diffusion model presumably needs to construct internal representations of the latent variables
[d], we have that (0)x(()))(()) is directly proportional to the correlation between token zy (0) and the input a(t).
2 Notice that the observed scaling of sample complexity remains robust to the specific choice of threshold value.
Score function at low noise We now consider a small- noise regime t- 0 where only the first token has been
5

---

Compositional Generalization and Creativity in Diffusion Models
label: ([z(())
Hence, in what follows, compute the number of samples required to detect these correlations.
Local constraints The first step in the learning process to recognize the valid s-tuples generated by the RHM at the visible level. Since these tuples lack internal structure, they can only be memorized. Each tuple can take om possible configurations corresponding to symbols for the first-level latents and m representations (synonyms) for each of them. Thus, the sample complexity required learn the local constraints scales as P1 um.
imput: axt) (a) U-Net scheme.
Once the local constraints are learned, the network can refine its estimate of x by utilizing correla- tions with the neighboring tuples 2=+1:281 - 1)ss" The sample complexity required detect the correlations between z and #:+1:2s was computed in Cagnetta & Wyart (2024) and correponds to P2 = (1 m//=-1)= um3 For > P2. after learning the first-level rules, the network can collapse the (s² s)-dimensional sequence of neighboring tuples into the corresponding first-level latents h
First-level latents
(b) RHM structure.
Figure 3. U-Net scheme and RHM structure. (a) To denoise the RHM data, the U-Net has to predict the conditional expectation [[==(0)=zz()) for a given noisy input (t). which is proportional to the correlations of the single tokens z0) with ætt). This can be done efficiently by learning the latent hierarchical structure of the data. (b) The correlations of the RHM data reflect the tree structure of the model (black squares represent the rules at different levels). For the token 21, using the correlations with tuples at different levels (highlighted red), conditional expectation E|z1 [22:s] can represented as E[zr (a2, h 122 J.
Second-level latents Having built the first-level latent representation, the model can leverage correlations between s-tuples of first-level latents h, and the first token to learn the rules at the second level, further improving the denoising task. These correlations can be computed by studying the statistics of the token-latent tuple correlations,
changed by noise, to some value 21 (t) uncorrelated with 21 (0). In this case, the function that the network has to learn is B[z, (0) (0)),, proportional to the correla- tions of the first token with the remaining sequence of length d. Since these correlations are invariant un- der exchanges of synonyms (Cagnetta al., 2024), they correspond to the correlations of the æ1 token with the la- tents at all levels generating the rest of the sequence, i.e., E[x, (222, hg. he...... h (1-11) (Figure 3(b).. This func- tion depends on sequence length (s (s-1)7 L),, much smaller than the data dimension d sh. In other words, knowing the latent variables allows for significant reduction of the problem dimensionality.
c = [1 = 14, h = vl
(1)
[1 = /4] IP h h+1:24 v).
(2)
over RHM realizations. Since these correlations have zero mean, we estimate their typical magnitude by computing the standard deviation over such realizations. As shown in Ap- pendix A, and denoting the average over RHM realizations by (>), the correlation magnitude is given by
(33 = =V((C(()))))
m/ve-1 u
(3)
4.2. Sample complexities
where the rightmost expression becomes exact asymptoti- cally in v and m. Since a finite training set of size P only allows measuring the empirical correlation function, we compare the magnitude of correlations with the sampling noise, which has magnitude (u²mP) 11/2, -1/2, Thus, the num- ber of samples required to detect correlations between tuples of first-level latents and visible tokens is
In this section, we determine the sample complexities quired to reconstruct the tuple of latent variables of different levels (1))) appearing the low-noise score function. As shown in Cagnetta & Wyart (2024), latents can be recon- structed via their correlations with the noised token 11. We thus work under the following assumption.
P3 (1 1mm vm
(4)
Assumption 4.1. The U-Net learns to generate data that is consistent with the rules at level when the correlations between a visible token and a tuple of latents at level & - 2 become detectable from the training data.
Extension to general depth & The same procedure gen- eralizes to any depth f. The correlations between tuples
6

---

Compositional Generalization and Creativity in Diffusion Models
of latents at level L - 2 and visible tokens, having lowest common ancestor at level l, have magnitude
ing the tuple (#1,-.. .ig with a synonym. As proved in Ap- pendix B, one step of gradient descent aligns the learned weights with the empirical token-tuple correlations. Conse- quently, if the size of the training set is large enough for the accurate measure of correlations, then the network can build a representation of the tuple (dI....4,), which is invariant to exchanging synonyms. This invariance is empirically observed for the U-Net in Figure 6 of Appendix D.
m/v-11 m
c
(5)
Meanwhile, the sampling noise remains of order (c"mP))-1/2 Equating these terms gives the sample com- plexity required to reconstruct level-(e-1) latents,
5. Natural data
Pt = (1 m///-=/)
umn um 1+1
(6)
In this section, we investigate whether the hierarchical learn- ing dynamics observed in the RHM also emerge in diffusion models trained on natural data, such as language and images. Since both modalities have an inherent compositional structure-where words form sentences and object parts form images- we expect their learning process progress hierarchically as training time or dataset size increases.
This result indicates that learning rules leveraging corre- lations at depth I. requires number of samples scaling as mL = mddlo m/ log x, which is polynomial (and not expo- nential) in the dimension. Knowing the rules, the network can reduce the dimensionality of the score by conditioning the expectation of the value of token on the latent variables instead of the full input sequence. Remarkably, Eq. (6) displays the same scaling observed in our experiments with the U-Net in Section 3, confirming Assumption 4.1.
5.1. Language diffusion models
We consider MD4 (Shi et al., 2024), state-of-thh-an masked diffusion model with absorbing state for discrete data such as language, as described in Appendix C. We train MD4 from scratch using a standard GPT-like transformer architecture with 12 layers (= 165M parameters) on the Open WebText corpus (Gokaslan & Cohen, 2019). The model is trained for a full epoch on the training split ( 10 tokens) using the same hyperparameters as Shi et al. (2024). We save checkpoints at different training stages and generate approximately 10 tokens per model. Figure 4(a) presents text samples generated at various training times. Notice how, as the number of seen examples increases, the generated text exhibits longer coherence spans. In particular, the intermediate checkpoint (= 10 tokens) correctly assem- bles words locally but fails to generate coherent sentences, similar to what observed in our synthetic experiments in Section 3. At qualitative level, this mechanism resembles how children acquire language: first recognizing and grouping sounds into syllables, then forming words, which are gradually combined into meaningful phrases.
4.3. Clustering and one-step GD
Clustering To validate the hypothesis that synonyms can be grouped based on correlations, we consider simple clustering algorithm based on the empirical correlations between (latent) tuples and a visible token. In particular, for a given (visible or latent) patch h, we fix it to one of its possible values v and compute its mean context vector by averaging the one-hot-encoded nearest tokens x. Otherly said, we estimate the empirical conditional expectation v. T.=EBa E[z h = y/ for each value v. These context vectors are proportional to the empirical token-patce correlations discussed in Section 4. We then perform k-means clustering on these vectors. When the dataset is sufficiently large, syn- onymous patches v will produce similar mean contexts and are consequently grouped together. As shown in Figure 2, the sample complexity for such an algorithm (black points) closely follows the theoretical prediction Pt ~ m We also test a modified algorithm that uses all the tokens in the first visible tuple instead of just the first (red points in Figure 2). Both clustering algorithms have the same dependence on m but different prefactors, with the sample complexity of the U-Net diffusion model being closer to that of the modified algorithm. This suggests that the diffusion model effectively leams hierarchical representations by leveraging correlations across broader contexts.
We confirm this result quantitatively by measuring the token-token correlation function of the generated text (Fig- ure 4(b)), as done for the RHM in Figure (cc). Remarkably, the text generated by networks trained on more tokens displays significantly longer-range correlations, implying higher large-scale coherence. In Appendix D, we provide an alternative measure based on measuring perplexity con- ditioned contexts of varying length to confirm this result.
One-step gradient descent Finally, to support the connec- tion with standard training techniques, we consider simpli- fied setting where a linear architecture is trained via gradient descent to predict the token Fs+1 given an adjacent tuple (æ1,... ..)). This task corresponds to learning the score function (())+1(0))m1 11: (0)) which is invariant to exchang-
5.2. Vision diffusion models
For image data, we consider Improved Denoising Diffusiio Probabilistic Models (DDPMs) (Nichol & Dhariwal, 2021).
7

---

Compositional Generalization and Creativity in Diffusion Models
10 training tokens
MD4 Open WebTewt
In popular spokesman typeted in diversity adventure allow price Zha Tampa usually Pages superstays's s under leveldowns swim a cycle who retains highly weapons batch floor despite
Cxfe) N 200
10 training tokens
Just like you growing fast and growing strong. But this way you became organic, changed someone else 2019s. But even then you made them off. sort came to smile around, because was in China okay.
104h training tokens
10'
Token distanec
At the beginning of winter when walked around; even he would be talking to me, on the highest field and back in the second round in my team I would take him over in his cell because it was my game against Juventus.
6. 3-4+-08 toloms
2.1e=00 toloms
7.6++888 tokons
1.3e=09
1.le (29 tokoms
8.60- (00 tolens
1. 1.3++00 tolome
camplingg noise
1.e+00 tobons
(a) Text generated at different training stages.
(b) Correlations in the generated text.
Figure 4. Stage-wise learning of masked language diffusion model on OpenWeTText. (a) Examples of text generated by MD4 at different training stages. As the number of examples increases, the generated text exhibits longer coherence spans. (b) Correlations between tokens at a distance in the generated text. Correlations are measured over N = =210 pairs of tokens, thus are lower bounded by the sampling noise N//2) (black dashed line), with = 50257 the vocabulary size of the tokenizer. Up = 7 x 10" training tokens, the correlations of generated sentences match the sampling noise, implying that MD4 generates sequences of uncorrelated tokens. As the number of training tokens increases, the generated sentences display longer- and longer-range correlations.
Specifically, we train a U-Net model architecture (Ron- neherger et al., 2015; Salimans et al., 2017) with multi-head attention layers (Vaswani et al., 2017) (+S 120M param- eters). The model is trained for 10 epochs 64 x 64 using the same hyperparameters as Nichol & Dhari- wal (2021). We save model checkpoints at different training steps and use them to generate 10d images per model.
(MMD) (Gretton et al., 2006) between ResNet embeddings of the generated images and those from the ImageNet validation set. MMD-based evaluations with deep network embeddings have recently been proposed as robust metric for assessing image quality in diffusion models (Jayasumana et al., 2024).
ImageNet
Figure 5(b) presents the MMD measured at different depths of the ResNet model as a function of the number of seen examples. Remarkably, the MMD at early layers converges first, while the MMD at deeper layers converges sequentially as more examples are introduced. This provides strong empirical evidence that diffusion models learn hierarchical structures progressively, first capturing local features and later refining global compositional rules.
Figure 5(a) illustrates images generated at different training stages. Initially, the outputs exhibit patterns of textures. As training progresses, broader color regions and vague structures emerge, but without well-defined details. By 10 steps, the model starts assembling coherent local features, such as object-like shapes or parts, though global consistency is still lacking.² Finally, images from the last checkpoint exhibit highly structured and realistic compositions, indicating that the model successfully learns to generate coherent scenes with well-defined objects.
6. Conclusions
We have provided a theory explaining how diffusion models can learn hierarchically compositional data using a number of samples that scales polynomially with the data dimension, thus beating the curse of dimensionality. In particular, we showed that when learning from data generated by simple context-free grammar, U-Nets reduce the dimensionality by assigning identical representations to groups of features that share similar contexts. This process unfolds hierarchically across levels of abstraction As a result, the framework predicts that increasing training time or dataset size leads to generated data that is coherent over progressively larger scales. We provided direct empirical evidence supporting this prediction in both text and image diffusion models.
To quantify these observations, we analyze the hierarchical and compositional structure of generated images using deep latent representations from a pre-trained ResNet- 18 (He et al., 2016). Early layers encode low-level localized features, while deep layers represent more abstract and global factors (Olah et al., 2017: LeCun et al., 2015), as also observed for CNNs trained the RHM (Cagnetta al., 2024). We compute the Maximum Mean Discrepancy
NNtice that at 10 steps with batch size 128 the model has seen 10t examples and is still in the online regime, as each image has been presented only once.
8

---

Compositional Generalization and Creativity in Diffusion Models
Improved DDPM on ImageNe164
10 steps
10a
ResNet- MMD
10a
10 steps
101
100
10 steps
102
102
104
10
109
10'
Number of examples
steps batch size
Layer
Layer
Layer
Layer
Layer
Layer
10 steps
Layer
Layer
(b) Maximum mean discrepancy at different CNN depths.
(a) Images generated different training stages,
Figure 5. Stage-wise learning of vision diffusion model on ImageNet64. (a) Examples of images generated by the diffusion model at different training steps. (b) MMD between generated and real images measured at different depths of ResNet18 model as function of the number of training steps. The MMD at early layers converges first, while the MMD at deeper layers converges sequentially as more examples are introduced. The grey dashed line indicates the end of the first epoch.
Importantly, the fact that the hierarchical dynamies predicted by our theory also emerges in natural language- despite its richer and more irregular syntactic structure compared to the RHM-offer strong empirical support for the modeling assumptions underlying our framework. Furthermore, recent studies on hallucinations in diffusion models (Iu et al., 2025; Han et al., 2025) report a strong local inductive bias and that inter-feature rules associated with higher-level consistency are harder to learn, which aligns with our theoretical predictions. Our model thus provides principled and quantitative lens through which these observations can be understood.
the coarse-grained variables is fixed: it simply corresponds to the average of field on larger and larger spatial scales. It is known that generative models trained certain physical systems
reproduce this pooling operation (Mehta & Schwab, 2014; Marchand et al., 2022). The principle we put forward here, whereby latent variables are built hierarchically by considering how they predict their neighborhood, is a generalization of the remormalization group. allows one construct coarse- coarse-grained variables that are complex functions of the input and can change in nature at different scales. An intriguing possibility is to revisit problems where the renormalization group led to insightful but limited headway, such as in turbulence (Yakhot & Orszag, 1986), with this novel viewpoint.
Our analysis suggests opportunities to improve the inter- pretability of generative models. Performing explicitly a 'word2vec' procedure hierarchically by identifying not only synonymic words with similar context, but also synonymic groups of words and so on, would mimic central aspect of diffusion models, according to our results. While such an approach will produce representation of text most likely inferior to that of diffusion models, it would be better controlled and easier to interpret.
Impact statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Finally, the coarsening mechanism we describe, where information low-level details of the data is lost con- struct latent variables, is reminiscent of the renormalization group used in physics to study phase transitions (Wilson, 1983). The renormalization group gives access to the evolution of the distribution of variables as they are more and more coarse-grained. Yet, in that case, the nature of
References
AllenZZhu, Z. and Li, Y. Physics of language models: Part 1, context-free grammar, arXiv preprint arXiv:2305.13661 13673, 2023.
D., Ho, J., Tarlow, D., and Van Austin, J., Johnson, D. D.,
Den Berg, R. Structured denoising diffusion models in

---

Compositional Generalization and Creativity in Diffusion Models
discrete spate-Spaces. Advances in Neural Information Processing Systems, 34:17981-17993 2021.
Grenander, U. Elements of pattern theory. JHU Press, 1996.
Gretton, A., Borgwardt, K., Rasch, M., Schölkopf, B., and Smola, A. A kernel method for the two-sample-probeem. Advances in neural information processing systems, 19, 2006.
Betker, J., Goh, G., Jing, I.., Brooks, T., Wang, J., Li, I.., Ouyang, L., Zhuang, J., Lee, J., Guo, Y., al. Improving image generation with better captions. Computer Science. https:///ddn. openat. comppapers/dall-e-3. pdf. 2(3), 2023.
Han, Y., Han, A., Huang, W., Lu, C., and Zou, D. Can diffusion models learn hidden inter-feature rules behind images? arXiv preprint arXiv:2502.00 04725, 2025.
Biroli, G. and Mézard, M. Generative diffusion in very large dimensions. Journal of Statistical Mechanics: Theory and Experiment, 2023()):093022, 2023.
He, K., Zhang, X., Ren, S., and Sun, J. Deep Residual Learning for Image Recognition. IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pp. 770-778, June 2016. doi: 10. 10.1109/CVRR.2016..999
Block, A., Mroueh, Y., and Rakhlin, A. Generative modeling with denoising auto-encoders and langevin sampling. arXiv preprint urXiv:2002.00100 2020.
Ho, J., Jain, A., and Abbeel, P. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-683 2020.
Cagnetta, and Wyart, M. Towards theory of how the structure of language acquired by deep neural networks. In The Tiihty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Hoogehoom, E., Nielsen, D., Jaini, P., Forré, P., and Welling, M. Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in Neural Information Processing Systems, 34:12454-1246, 2021.
Cagnetta, F., Petrini, L., Tomasini, U. M., Favero, A., and Wyart, M. How deep neural networks learn compositional data: The random hierarchy model. Physical Review X, 14(3):03100L, 2024.
Jayasumana, S., Ramalingam, S., Veit, A., Glasner, D., Chakrabarti, A., and Kumar, S. Rethinking fid: Towards a better evaluation metric for image generation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9307-9315, 2024.
Chen, M., Huang, K., Zhao, T., and Wang, M. Score approximation, estimation and distribution recovery of diffusion models owwdiimensional data. arXiv preprint ar arXiv:2302.07199, 2023.
Jin, Y. and Geman, S. Context and hierarchy in proba- bilistic image model. In 2006 IEEE computer society conference computer vision and pattern recognition (CVPR'06), volume 2, pp. 2145 2152. IEEE, 2006.
Chomsky, N. Aspects of the Theory of Syntax. Number 11. MIT press, 2014.
Chomsky, N. et al. Reflections on language. Temple Smith London, 1976.
Kadkhodaie, 7.,, Guth, F,, Mallat, S., and Simoncelli, F. P. Learning multi-scale local conditional probability models images. arXiv preprint arXiv:2303.0298/ 2023a.
Cui, H., Krzakala, F., Ganden-Eijndens E., and Zdeborová, L. Analysis learning flow-based generative model from limited sample complexity. arXiv preprint arXiv:2310.0357.. 2023.
Kadkhodaie, 7., Guth, F,, Simoncelli, E. P., and Mallat, Generalization in diffusion models arises from geometry-adaptin harmonic representations. arXiv preprint arXiv:2310.02557, 2023b.
Damian, A.,
Lee, J., and Soltanolkotabi, M. Neural networks can learn representations with gradient descent. Proceedings of Thirty-Fifth Conference on Learning Theory, 178:5413-5457 2022.
Kamb, M. and Ganguli, An analytic theory of creativity in convolutional diffusion models. arXiv preprint arXiv:2412.20299, 2024.
De Bortoli, V. Convergence of denoising diffusion models under the manifold hypothesis. arXiv preprint arXiv:2208. 05314 14, 2022.
LeCun, Y., Bengio, Y., and Hinton, G. Deep learning. Nature, 521((553):436, 2015.
Garnier-Brun, J., Mézard, M., Moscato, E., and Saglietti, L. How transformers learn structured data: insights from hierarchical filtering. arXiv preprint arXiv:2408. 15138, 2024.
Li, M. and Chen, S. Critical windows: non-asymptotic theory for feature emergence in diffusion models. arXiv preprint vrXiv:2403.0663. 2024.
Lu, R., Wang, R., Lyu, K., Jiang, X., Huang, G., and Wang, M. Towards understanding text hallucination of diffusion models via local generation bias. arXiv preprint arXiv:2503.03555, 2025.
Gokaslan, A. and Cohen, V. Openwebtext cor- pus.
http: http://Skylln 1ioooo0000 github. io/ OpenWeebeextCorpus. 2019.
10

---

Compositional Generalization and Creativity in Diffusion Models
Malach, E. and Shalev-Shwartz, S. A provably correct algorithm for deep learning that actually works. arXiv preprint 1XX.v:1883.095550 2018.
Ronneberger, O., Fischer, P., and Brox, T. U-net: Convo- lutional networks for biomedical image segmentation. In Medical image computing and computer-assisted intervention 2015: 18th international confer- ence, Munich, Germany, October 5-9, 2015, proceedings, part III 18, pp. 234-241. Springer, 2015.
Marchand, T., Ozawa, M., Biroli, G., and Mallar, S. Wavelet conditional renormalization group. arXiv preprint arXiv:2207.04944 2022.
Rozenberg, G. and Salomaa, A. Handbook of For- mal Languages. Springer, January 1997. doi:
Mehta, P. and Schwab, J. An exact mapping between the variational renormalization group and deep learning. arXiv preprint arXiv:/410.388) 2014.
10.
Salimans, T., Karpathy, A., Chen, X., and Kingma, D. P. Pixelenn++: Improving the pixelenn with discretized logistic mixture likelihood and other modifications.
Mei, S. U-nets as belief propagation: Efficient classifica- tion, denoising, and diffusion in generative hierarchical models. arXiv preprint arXiv:2404.1844/ 2024.
arXiv preprint (00i:::7001.555111 2017.
Sclocchi, A..
Favero, A., Levi, N. I., and Wyart, M. Probing the latent hierarchical structure of data via diffusion models. International Conference on Learning Representations (ICLR), 2025a.
Mei, S. and Wu, Y. Deep networks as denoising algo- rithms: Sample-efficient learning of diffusion models in high-dimensional graphical models. arXiv preprint arXiv:2309. 11420, 2023.
Sclocchi, A., Favero, A., and Wyart, M. A phase transition in diffusion models reveals the hierarchical nature of data. Proceedings of the National Academy of Sciences, (22(1):2248779112, 2025b.
Mezard, M. and Montanari, A. Information, physics, and computation. Oxford University Press, 2009.
Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., and Dean, J. Distributed representations of words and phrases and their compositionality. Advances in neural information processing systems, 26, 2013.
Shah, K., Chen, S., and Klivans, A. Learning mixtures of gaussians using the ddpm objective. arXiv preprint arXiv:2307.00 17888, 2023.
Nichol, A. Q. and Dhariwal, P. Improved denoising diffu- sion probabilistic models. International Conference on Machine Learning, pp. 8162-8171. PMLR, 2021.
Shi, J., Han, K., Wang, Z., Doucet, A., and Titsias, M. Simplified and generalized masked diffusion for discrete data. arXiv preprint arXiv:2406. 2406.0329, 2024.
Okawa, M., Lubana, E. S., Dick, R., and Tanaka, H. Com- positional abilities emerge multiplicatively: Exploring diffusion models on synthetic task. Advances in Neural Information Processing Systems, 36, 2024.
Siskind, J. M., Sherman, J., Pollak, I., Harper, M. P., and Bouman, C. A. Spatial random tree grammars for modeling hierarchal structure images with regions of arbitrary shape. IEEE Transactions Pattern Analysis and Machine Intelligence, 29(9):1504-155 2007.
Oko, K., Akiyama, S., and Suzuki. T. Diffusion models are minimax optimal distribution estimators. arXiv preprint arXiv:2303.01866 2023.
Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, Deep unsupervised learning using nonequi- librium thermodynamics. In International conference machine learning, pp. 2256-2265. PMLR, 2015.
Olah, C., Mordvintsev, A., and Schubert, L. Feature visualization. Distill, 2017. doi: (0.23915/distill ///istilll.0000 http://ffiiilllpp222077//tttretr
Song, Y. and Ermon, S. Generative modeling by estimating gradients of the data distribution. Advances neural information processing systems, 32, 2019.
Park, C. F., Okawa, M., Lee, A., Lubana, E. S., and Tanaka, H. Emergence of hidden capabilities: Exploring learning dynamics in concept space. Advances in Neural Information Processing Systems, 37:84698-84729, 2024.
Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:201 2020.
Rombach, R., Blattmann, A., Lorenz, D., Esser, P., and Ommer. B. High-resolution image synthesis with latent diffusion models. In Proceedings of the JEEE/CVF conference on computer vision and pattern recognition, pp. 10684-10695, 2022.
Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al. Llama: Open and efficient foundation lan- guage models. arXiv preprint arXiv:2302 /3971, 2023.

---

Compositional Generalization and Creativity in Diffusion Models
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J. Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is All you Need. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Wilson, K. G. The renormalization group and critical phenomena. Rev. Mod. Phys., 55:583-600, Jul 1983.
Yakhot, and Orszag, S. A. Renormalization group analysis of turbulence. basic theory. Journal of scientific computing, 1(1):3-51, 1986.
Yang, G. and Hu, E. Feature learning in infinite-width neural networks. arXiv preprint arXiv:201 14522, 2020.
Yang. L., Zhang, Z., Song, Y., Hong, S., Xu, R., Zhao, Y., Zhang, W., Cui, B., and Yang, M.-H. Diffusion models: A comprehensive survey of methods and applications. ACM Computing Surveys, 56(4):1-39, 2023.
Yuan, H., Huang, K., Ni, C., Chen, M., and Wang, M. Reward-directed conditional diffusion: Provable distribution estimation and reward improvement. arXiv preprint arXiv:2307.07055, 2023.
12

---

Compositional Generalization and Creativity in Diffusion Models
Supplementary Material
A. Token-latent tuple correlations
In this section, we derive our estimate for the magnitude of the correlations between #1 and tuples of latent, level-(e 1) features (6-1) ((=-1)x++:ixx=* with == 2....., and & = 1, ..... L-1 (level-0 latents ((0) correspond visible tokens). These correlations are identical for all the tuples of latents corresponding to the same higher-level feature h; thus can be used to reconstruct level-f latents. For instance, with 8 2, so that i == (see Figure 3), the correlations of æ1 with (rg, 244) determine the value of 1/5", while those with (hg _1 determine h2z) To simplify the notation, we will stick to the case i= 2 for the remainder of the section. Then, the goal is to compute the statistics of
(1,) = X1 14, h (--1)
8+1:28 = v) P = 1/
h (L-1) s+1:2s =
=
over realizations of the RHM.
For each visible token i == I,...,d, single-token probabilities can be written as products of probabilities over the single production rules,
P P|X
E
Pi (ulp)) ... .P.. (Pt-il (lr.)p (pr.).
(8)
where
i) the indices i fr. are such that i..... equals the s-ary representation of i, with ig 1,..,..,, 8, and I's added ensure that the representation always consists of indices. In other words, the multi-index ....., ig uniquely identifies the path linking the root of the tree the i-th leaf.
ti) Pit (He-)l denotes the probability of choosing, among the available production rules starting from μig one that has the symbol 1 on the ig-th position of the right-hand size.
(F)
ii ((L) denotes the probability of selecting the symbol μz the root (1/v for our model).
These decompositions arise naturally due to the connection between probabilistic context-free grammars and Markov processes. Similar decompositions apply to the probabilities of hidden variables and tuples, and the joint token-latent tuple probability. For the latter, in particular, starting from the level-(f 1) hidden symbol n (e+1), lowest common ancestor (LCA) of X, and the tuple h $ we have
PP p n. h 1:12 =v] = Σ
Pi 1 (plpp)) (0) (HE-Ilme) x
Σ
(1tt) (6+2)
(1e+1).
Me 188e
For é 1, the probability above coincides with the joint probability of the visible token X and the tuple of visible tokens
X X.+1...., X2.. The correlations,
c (m, v)
= X1 n1 X 1:24 = -P P XX.112 = =v]
(10)
have been analyzed in Cagnetta Wyart (2024): the mean vanishes, while the variance, in the limit of m, + +oo with m//=-1 finite, follows
(C0))))2)))
1-
(1))
13

---

Compositional Generalization and Creativity in Diffusion Models
For 8= 2, after applying Equation (9), get
(H, = Σ
Pi 1 (plma) (P (T|N Mr, h:41:24 2/ -P
P[1 ln IP h =w)
#1=1
= Σ Pi
a (ele))
(12)
#==1
where the last equality follows from noticing that the probability of level-& hidden variables coincides with the probability of the leaves of with - levels. In general,
(p,1) = E
(13)
m=
thus
( (1)))))))1)))) Σ
Th (ulun)) (el (C0
(pl (ulmi))
M1
(ill)) (ulei) (ot0 (1))
(14)
Knowing that the production rules of an RHM realization are chosen uniformly at random compatibly with the unambiguity constraint (Cagnetta & Wyart, 2024),
(pD va-1(0 1) + m(v--1-1 1) mo(u- - 1)
(15)
and, for 11 + p1.
20-1
(16)
2(20 - 1)
In addition, since E, ((0(H,))) then
Σ ((1 ((C
(17)
U1 11
Hence,
(1(t))))))))))
-0
- -
((o0))))))))))
131 1
(1))))))))))
(18)
m(v- -1)
Starting with (2) from Equation (11), we get
c ((CU(())))))
1 1-f 222
2
(19)
where the rightmost equality is exact in the limit u, u.m- >> +00.
B. One-step gradient descent
We consider simplified one-step gradient descent setting (Damian et al., 2022), where a simple machine-learning model trained to approximate the conditional probability one input token X following an s-tuple of tokens X (X1,..., X²). The training set Xp consists of pairs (æ, v), with denoting the feature in the token X We assume that
14

---

Compositional Generalization and Creativity in Diffusion Models
i) the input tuple X is given the one-hot encoding of the tuple index. Each of the me possible combinations of features is assigned index f== 1u-1.... me and is the mu-dimensional sequence Tiye p())())>
ii) the machine-leamingg model initialized on the empirical marginal probability of the token X over the training set, P ++1 =v) = (i S2,2. This assumption is equivalent a preprocessing step on the labels (Damian et al., 2022) that removes the class imbalance of the training set.
Due to assumption i), the task can be solved with a perceptron model followed by a softmax nonlinearity,
fel;;) = E Wu Po( W) = (o(o:W Σ (oolews)) -1 Ja
(20)
where W E (e)((m) is the weight matrix. In this setup, Assumption ii) is realized by initializing the weights as W = log IP [x++1 = v independently of μ.
The model fo of Equation (20) trained via Gradient Descent on the empirical cross-entropy loss computed over a training set Xpp consisting of P pairs (xz v), with v denoting the feature in the token Xa+1.
[-
edi(m:W)
)
= (a
-log
log
E. efo(m:W)
(21)
where () denotes the empirical average over the training set. Denoting the learning rate with y, the update of the weights reads
OL O5, (o..Ee 5x E Eo=ieto cta ZT
e/
AW., -1 0f. OWa,
=nB(a,))EX' ())0)))(())))))))))))))) - P [x+11 =v/ 6pp
=n (f = =; (X1,.... X,) (11 (f1....., [a)] - DX X.)) (M1, ... n.)l), (22)
where, in the second line, we used assumption i) replace Ty with (m.(())) and assumption to replace elv / /Eoz elo) with IP [X++1= =). The right-hand side of the last line equals the empirical token-uple correlation Cr(u, pJ). Therefore, after one gradient step, the weights are given by
vj.
We, log [X++1= =] + nCC(P.
(23)
The first term is independent of the input μ., whereas the second can be thought of noisy measurement of the true token-tuple correlation C'v,. μa). The true correlation is equal for all μtss generated by the same higher-level hidden symbol (p)) and its size can be estimated as the standard deviation over realizations of the RHM (Equation (11)),
(2
(24)
m
The empirical measurement Öp includes a sampling noise contribution, having size (v²mP)-1/2 P3 then the Čp in the right-hand side of Equation (23) is approximately equal to the true token-tuple correlation, thus the weights can be used to build a representation of the hidden variables of the generative model.
C. Experimental details
Random Hierarchy Model We train the U-Net-based Discrete Denoising Diffusion Probabilistic Model (D3PM), optimizing the diffusion loss derived from variational bound on the negative log-likelihood (Sohl-Dickstein et al., 2015). Following Austin et al. (2021), we use the neural network to predict the conditional expectation (())()))((t), which parameterizes the reverse diffusion process.
The convolutional U-Net consists of resolution blocks both the encoder and decoder, with a filter size of s, stride of s, and 8192 channels, Each block uses GeLU activation functions, and skip connections link encoder and decoder layers
15

---

Compositional Generalization and Creativity in Diffusion Models
Encoder loger
Breoder
layer
130
0.4
0.2
4.0
lowe
Dwender over 2
lager 3 (6
Brader 26 M.
Decoder loper
1.0
0.8
0.9
0.0
12" Number
10
10
Df if
10 10f Nomber taiming
Number P
Number of training
Number tealning
Ar
Figure Relative sensitivity of the hidden representations of the U-Net, defined in Equation (26), with respect to the number of training points/ P. Different colors correspond different levels of synonymic exchange, while different panels correspond to the ire-activations of different U-Net blocks. Encoder layer 1 the closest to the input, while decoder layer is the closest to the output. As the number of training points increases, deeper layers of the encoder become less sensitive deeper synonymic transformations. This implies that deeper encoder layers learn to represent deeper latent variables of the RHM. The decoder layers, instead, progressively regain the sensitivity the synonyms layer-by-layer they expand latent variables into their lower-level representations. For each level e, the dashed line represents the fraction of generated samples that do not satisfy the rules at that level, i.c., 1 - Ar. The U-Net learns to satisfy rules at level when becomes insensitive the synonyms of the variables level 1
with the same resolution. The model also includes two embedding and unembedding layers, implemented as convolutions with filter size 1.
We initialize the network using the maximal-update (μP) parameterization (Yang & Hu, 2020). This allows stable feature learning dynamics even in large models. The model is trained with SGD with learning rate of 1, using a batch size of 32, and momentum parameter of 0.9. The diffusson process follows a linear schedule with 1,000 noise levels. To prevent overfitting, we apply early stopping based on the validation loss, halting training when plateaus or begins increase.
Language diffuusin model Our experiments are based on the codebase of MD4 (Shi et al., 2024): MD4 is masked diffusion model. At each time step i, non-masked tokens either remain unchanged or transition to [MAS]] with probability Be. Using one-hot-encoding representation of the [V] + 1 states, the forward transition matrix is given by:
Q. = (1- 8,1
(25)
with I the identity matrix, 1 vector of ones and eи the one-hot-encoding vector corresponding to the [MASK] symbol. At the final time T, all tokens are masked, i.e., (T) [MASK] for every i E [dim(=)]. We train MD4 with batch size 64 and context size 1024 on 4 H100s for a single epoch. All other hyperparameters are kept unchanged.
Vision diffusion model Our experiments are based on the codebase of Improved DDPMs (Nichol & Dhariwal, 2021): wowm/ppeniimmprooedddffeooo
http:///hhhu.ccomppeaa//mm
particular, we train a DDPM with 128 channels, 3 resolution blocks, 4000 diffusion steps, cosine noise schedule, learning rate 10 and batch size 128 for 10 epochs using a hybrid objective (Nichol Dhariwal, 2021).
16

---

Compositional Generalization and Creativity in Diffusion Models
RHM (1=3, v=
Sample complexity p s.t. A = 1/2
m4+1
109
Avg. pixel clustering
Avg. context chustering
100
10a
109
10a
10a
m
Figure 7. Sample complexity of clustering with L Empirical values of P for clustering methods based the correlations of latent tuples with the first token (black) and the first visible tuple (red), respectively. The scaling 1 ~ m 4+1 aligns with theoretical predictions.
D. Additional results
D.I. Emergence of hierarchical representations in the U-Net
In Figure 6, we test the hypothesis that the U-Net learns to represent together inputs that differ by low-level synonyms, i.e. the choice of low-level production rules. To do so, we introduce transformation operator R2 which modifies given data sample æ by resetting all choices of the production rules emanating from level f. This operation is equivalent to substituting all tuples at depth with a synonym. We then define the relative sensitivity Sk,e of the pre-activations as at layer & to the transformation Re:
Ex (lll(xxxx)) 0A (R, 1
Sk. E., (x))))( a [1)
(26)
Here, the numerator measures how much the activations change when synonym substitutions applied depth E, while the denominator normalizes by the overall variability of activations across different data points. A low value of Sk, indicates that the network is invariant to synonym substitutions at depth L, implying that it has learned the corresponding compositional rule.
Figure 6 shows the relative sensitivity of each layer as a function of the number training points P. As P increases, the sensitivities Sz,e decrease sequentially across levels, following the same staged learning process observed in Figure 1. Deep encoder layers become invariant to synonym substitutions lower levels, confirming that the network is learning encode the hierarchical structure of the grammar. In contrast, decoder layers gradually regain sensitivity to specific low-level symbols as the output is approached. This behavior aligns with their role in reconstructing low-level details from high-level representations. Crucially, the network begins to satisfy rules at level & precisely when it becomes insensitive to synonymic variations at level f f-1 1. This suggests that the U-Net learns to collapse lower-level synonyms into shared latent representations and to compose these latents according to the production rules at level f.
D.2. Sample complexity of deep clustering algorithm
In Figure 7, we test our theoretical prediction for the hierarchical clustering algorithm with L = 3. Specifically, we examine how tuples of latent variables at depth = 2 are clustered based on their correlations with either a single visible token (black points) or an entire visible s-tuple (red points) in the context. As predicted in Section 4, the sample complexity of both clustering approaches scales as m confirming our theoretical result.
17

---

Compositional Generalization and Creativity in Diffusion Models
MD4 on OpenWebTexx
10a
5.4e+08 tokens
expl E [loopp(zy 20:3 ()
7.6e+08 tokens
104
1. 1.1e+09 tokens
2.1e+09 tokens
4.3e+09 tokens
10a
8.6e+09 tokens
1.7e+ 10 tokens
OWT
10a
10"
10a
Context length T
Figure Perplexity of the generated text as a function done over 1024 samples. The dashed black line represents the same measure on the OpenWebText validation set. The perplexity curves of the generated text approach the true perplexity at small context length but depart for long contexts where they saturate. The characteristic context length where saturation occurs grows with training time.
conditioning context length computed with LLaMA-2-7B, Averages
D.3. Perplexity of the generated text
Figure presents an alternative measure to correlations in the generated text for quantifying the longer and longer coherence as training progresses. Specifically, we extract sentences from the generated datasets and estimate token-level average log- ligllikelshoods using L-aMA-2-7B (Touvron et al., 2023), i.e., we compute
Exger [log (LTM(=T
(27)
for token 2y function of its context length T. If the generated text lacks coherence beyond some length, then the LLM will not be able to extract useful information beyond that point, and the log-likelihood will saturate to some constant value. Figure 8 reports the corresponding perplexity. defined the exponential of the negative log-likelihood (27), where the average is done over 1024 samples. The dashed black line represents the same measure on the Open Web validation set, whose slow decrease with context length indicates the presence of long-range correlations text. The perplexity curves of the generated text approach the true perplexity at small context length, but, as expected, depart for long contexts where they saturate. Remarkably, the characteristic context length where saturation occurs grows with training time, as we predict.
E. Examples of generated data
E.1. Text
10 TOKENS
Austin is heck because posting nicely 2010 claims requiring I. For best stands granted, so before other more child. After research spoof - :D until inevitable there in to citing comment, and Itemreciation may have composed of 25 questions guarding on habit of point register and it owned say owners and votes to indicate those wouldn' 't legateates to non rem on what the phones award my extra,job jobs are intentionally insensitive estimating ('Tasciated apply Inc exceptional - andd how I added quickly after this salary). Several customers. Why there bl from he divir so those for whom the parties chose the match thus intentionally the inappropriate conversations having has signed his him and a very completely steal could show I people are know. He tapped for careless sharing system of 'ties short Fallen generally deplor Has over mad Gamma himself as in 2012 fashion', pBuul none-uristic Howard yesterday is therefore played reserved Chief Zoe firm, whose practice such over God We believes yes NSW anyone today did the existing finished crutry. spent the found three years with party music? Plug WashingtonJ nighters then minor six up.. for his lead their 40, 10,000 persulations no start fixing time again will no scandaled thinks his follow he explodes. so a reduced street procedure problem whose edits introduced him his judged headline downtime though hardly exposed of coverage.Afer skipping a record detailing only the his times in production
18

---

Compositional Generalization and Creativity in Diffusion Models
10 TOKENS
the world, but right now you can create a set of ideas about what has been going on. An We think it's easy to walk in long world and dig in and share details where you are, but you don't 't have make a journey. "What?" JGame Johnson, up to that, answered several questions. \n" WWll it's i's got be Doctor Who."",, Abbsouuttyy yes, I'd love Doctors for Construction. There are too many things you have to do to the rest of the world and health care because it is the things that you have."",n replied: "The thing that has happened to a few physicians people you prefer is the kind of established above, things like numbers, life days, period and places, much more (no matter how much less thinking than things you have been thinking). \n Aik, I know I was the way of times knew what the patient had to say. At a time one doctor said that I wouldn't go to go health care time because there were possible things. \nn was just sit down and had never my conscience knew more less else it could be seen too, but it was helpful me. An" At one time there was one where it was actually my own problem of living who had been disabled. I lost it and called. An"
10 TOKENS
are analyzed by a series of algorithms. ArThat work pattern, too, is particularly absent for traditional platforms like Google and Facebook. Rather, the algorithm is carried through with the system and the attacker is able to match the IT systems that competing with the cnternet-connecie state-of-the-en approach behind marketing. nTTh new engineering means that the hardware is acquired from a third-party provider, and businesses will in lurn bear to undergo constant monitoring of the how their decryption algorithms will perform from the internet. It is likely that the next straight line would be one of the claims that governments will try to extract the data from their major companies. niThis might surprise some Monkey's 's announcement is because the industry is taking the culting corners. nnne of Washington's 's biggest informatioo-technolloy businesses forecasted that 30,00 30,000 inverts sent to people will use bitcoin as a third third-party party service on their PCs and it would take for more than a time for an exchange of "walls" to ensure that they have or are owned globally. The downside, course, is the risk represents in an increased attempt to favor less than one of the world's largest encryption agencies. \ (HHundreds of US products are expected to come out this year, which include Facebook and Google weed out the earliest on their users, and end on November 5th giving up roughly 300 individuals.
world'), nMonkey takes the new data-technology model and a less aggressive
E.2. Images
In Figures 9 to 12, we present images sampled from the vision DDPM trained on ImageNet after 100, 1,000, 10,000, and 100,000 training steps, respectively.
19

---

Compositional Generalization and Creativity in Diffusion Models
100 training steps
Figure 9, Images sampled from the vision DDPM trained on ImageNet after 100 training steps.
1 1000 training steps
Figure 10. Images sampled from the vision DDPM trained on ImageNet after 1,000 training steps.
20

---

Compositional Generalization and Creativity in Diffusion Models
10000 training steps
Figure 11. Images sampled from the vision DDPM trained on ImageNet after 10,000 training steps.
100000 training steps
Figure 12. Images sampled from the vision DDPM trained on ImageNet after 100,000 training steps.
21


Reviews:
[{"review_id": "g0giLgvSlt", "reviewer": "Reviewer_iFHU", "summary": "The paper proposes a model for understanding the evolution of learning feature dependencies when training diffusion models, specifically in terms of modeling the sample complexity required to learn certain structures. To do this, they adopt the adopt the perspective that data is generated by some ground truth probabilistic context-free grammar, and in particular, a specific class of PCFGs termed the Random Hierarchy Model. The authors construct a synthetic dataset consisting of discrete (one-hot) encoded vectors and train overparametrized discrete diffusion models (parametrized with a unet architecture) on varying number amounts of data samples. The success of the trained models is evaluated in terms of the fraction of generated samples which satisfy higher rules at various levels of the generative hierarchy. Under this synthetic data setting, clear trends emerge regarding how long it takes to learn different levels of the hierarchy, with higher levels (more complex/global features) taking longer to learn. However, a key trend that is noted is that the number of samples/time required grows polynomially with respect to the data dimension, rather than exponentially, matching the predictions made by the theoretical model proposed. The theoretical model employed primarily relies on prior work for determining sample complexity, and establishes the polynomial sample complexity needed due to the models ability to cluster synonyms to learn more complex dependencies. Examples of local to global structure learning in the context of language diffusion and image diffusion are presented as well, demonstrating the longer range correlations in text and MMD behavior at different CNN depths evolving with sample count.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and address their specific concerns below.\n\n**Models of images.** We agree that the relation between pixel and latent space in images is subtle. While images are continuous, they admit high-level abstract representations that can be described with discrete hierarchies. This idea was formalized in *pattern theory*, where scenes are parsed into objects and parts. The RHM describes these semantic aspects of images, in contrast to approaches emphasizing more geometric aspects. We also agree that the hierarchical level of a latent does not map perfectly to spatial locality, as in the RHM, e.g., low-level visual features - like a large patch of uniform color - can exhibit long-range spatial dependencies. This motivates our use of CNN representations, encoding image semantics, rather than raw pixels in Sec. 5.2.\n\n**Shuffled RHM.** With a CNN U-Net using non-overlapping filters, shuffling the RHM input is expected to significantly increase sample complexity because the model relies on spatial locality to infer the latent structure, and a shuffled input disrupts this property. In contrast, a fully connected network, invariant to input permutations, can overcome this issue. In that case, we expect a slight drop in performance compared to our results but still a polynomial scaling in the dimension, as observed in Cagnetta et al. (2024) for classification.\n\n**Clustering.** We will add clustering details to the paper. Briefly, for a given (visible or latent) patch $h$, we fix it to one of its possible values $\\nu$ and compute its mean context vector by averaging the one-hot-encoded tokens observed in the nearest neighboring visible patch $x$. In other words, we compute the empirical conditional expectations $v_{\\nu}=E[x|h=\\nu]$ for each of the possible values $\\nu$, which are proportional to the correlations discussed in Sec. 4. We apply k-means clustering to these vectors. When the training set size is sufficiently large, synonymous patches $\\nu$ will produce similar mean contexts and be clustered together.\n\n**Previous work.** While Kadkhodaie et al. focus on geometric inductive biases, we focus on the compositional and hierarchical structure of data. Our framework is complementary: instead of framing sample efficiency in terms of how networks capture geometric structure, our results show that compositional generalization can be achieved with a limited amount of data. We will incorporate this reference and clarify our scope. Similarly, the work of Kamb & Ganguli, contemporaneous and already discussed, studies locality and translational equivariance in trained models, but not sample complexity and finite-size effects, which are central to our work.\n\n**Hallucinations.** We thank the reviewer for pointing out these works. The findings that diffusion models have a local inductive bias and fine-grained rules have weaker signals in the loss are aligned with ours. We will cite these works as practical examples that can be quantitatively studied within our model.\n\n**Practical takeways.** Fundamental research has intrinsic value: a deeper understanding of how diffusion generalizes is important for building a foundation that could lead to long-term practical progress. Moreover, our findings already suggest practical paths. Our results show that overparameterized models - having the capacity to fully memorize their data, resulting in issues such as copyright infringement - have an inductive bias for reaching generalizing solutions before memorization. Trying the early stopping used in our synthetic experiments in real settings is thus an interesting future direction. Moreover, we propose new tools, e.g., MMD across depths or correlation analysis, that could serve as metrics for evaluating model quality beyond standard ones. We will clarify the broader significance of the paper.\n\n**Unambiguity.** While natural grammars have some ambiguity, we assume unambiguous rules to simplify the analysis. Yet, our theory indicates that limited ambiguity should not significantly affect results, as long as correlations among features exist. Extending the RHM to ambiguous rules and computing how correlations are affected is an interesting future direction. Note this assumption is not related to compositional generalization. In the example of objects with varying features, they can be thought of as different classes of the RHM data, i.e., different high-level concepts that can be composed with common low-level features. The example of generating two objects could be modeled by adding a production rule at the top, deciding which objects will appear on the left and right.\n\n**Synonymic invariance.** Collapsing distinctions between synonyms is key to lower dimensionality and denoise high-level latents. In the U-net, it is achieved in the internal layers. Yet, residual connections preserve low-level information to ultimately denoise the data at the finest level.", "claims_and_evidence": "I found the evidence supporting the claims very clear and pretty convincing. However, I'm not sure if it paints a sufficiently accurate picture for understanding sample complexity and learnability in the context of continuous diffusion for vision (synthetic dataset focused on discrete data). From my understanding, the local vs global relationships are not necessarily spatial relationship but rather relationships within the hierarchy; if so, it is not clear why training a diffusion model on a dataset of images of faces vs the same dataset with a fixed pixel permutation would have different sample complexities (as noted in appendix C.3 in https://arxiv.org/pdf/2310.02557). How can one interpret the influence of inductive biases in the context of the RHM and what levels of the hierarchy do they affect?", "methods_and_evaluation_criteria": "I appreciate the usage of the synthetic setting (although the discrete nature may less clearly capture behaviors in continuous diffusion) to demonstrate learnability, and the qualitative and quantitative evaluation methods for applied models. I believe these are appropriate in evaluating the problem studied in the paper.", "theoretical_claims": "I did not carefully check theory presented in section 4.2 or Appendix B regarding the one-step gradient descent", "experimental_designs_or_analyses": "The experimental designs appear sound and valid to me from the amount of information provided. Certain results, such as those shown in figure 2, are sorely lacking in information (the description of the context clustering, or modified clustering, is unfinished and not clear). A bit more information is provided in appendix D, but it's very brief and walking through an example of how clustering is done would be helpful", "relation_to_broader_scientific_literature": "I think connections of the key contributions to other diffusion literature are lacking. For example, https://arxiv.org/abs/2310.02557 also presented a perspective on the efficiency, feasibility, and generalizability of training which is provided through inductive biases of the networks being trained. However, it is not clear how to interpret such a result with respect to the perspective provided by the work nor how one would interpret inductive bias within the RHM framework (which also appears closely related to capabilities of generating novel data https://arxiv.org/abs/2412.20292). \n\nThis work also appears to be related to perspectives on hallucination in diffusion models. For example https://openreview.net/forum?id=SKW10XJlAI (and very recently https://arxiv.org/abs/2502.04725) have highlighted challenges in Diffusion models learning either global dependencies and rules, or very \"fine grained\" interdependencies in data, attributing hallucination to such failures. I believe connection and discussion of the RHM framework and the results of this work in relation to such perspectives on hallucinations would strengthen the work.", "essential_references_not_discussed": "All of the work required for understanding the contributions is cited.", "other_strengths_and_weaknesses": "While the primary contribution of the work is in demonstrating sample complexity and the stages of learning for diffusion models, discussion of practical takeaways of the work appears limited.", "other_comments_or_suggestions": "Nothing of note", "questions_for_authors": "Is the unambiguity assumption made reasonable? How does it relate to compositional generalization? In particular, if training is performed on images of single objects of different shapes, sizes, and colors, but the model is able to generate an image with two objects, how would this be interpreted under the RHM framework? Alternatively, could it be that being invariant to synonyms would correspond to harming compositional generalization?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qwRr3QsUkW", "reviewer": "Reviewer_b6pe", "summary": "In the paper, the authors use probabilistic context-free grammars and random hierarchy models in order to analyze compositional generalization in diffusion models. The papers begin by training a D3PM, analyzing how the model learns the rules of RHM at different hierarchical levels. They empirically observe a learned stage process, showing that the network first learns highest levels, and only after the generalization accuracy is high enough for lower levels, the accuracy starts to increase for higher levels. The authors proceed to investigate the sample complexity, which is defined as the number of samples required for the accuracy at a certain level to exceed that of chance. The authors establish theoretical results for this and show that simulated experiments behave according to theory. After establishing theoretical results, the authors show that for a hierarchical-structured data, deep networks such as UNets can exploit this structure resulting in enhanced. Finally, authors perform experiments for both diffusion on text and images, showcasing that diffusion models learn hierarchical structures in a progressive manner.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and address their specific concerns below.\n\n**Paper claims**\n\n1. **Creativity.**  By *creativity*, we refer to the well-established phenomenon in linguistics (e.g., Chomsky 1976) in which a finite set of rules can be learned by an infant so as to generate an infinite number of novel and well-formed sentences. This technical notion of creativity aligns with the behavior we observe in our models: the U-Net demonstrates compositional generalization on the RHM by generating novel, structurally valid samples that were not seen during training. We will revise the manuscript by recalling this definition.\n\n2. **Hierarchical learning.** We respectfully disagree with the reviewer's assessment of the novelty of our first contribution. \nThe works by Sclocchi et al. and Li et al. (which we will cite) involve no training and focus exclusively on the sampling behavior of diffusion models that have already been pre-trained up to their best performance.\nIn contrast, our work is the first to theoretically describe the hierarchical learning process of diffusion models: how they learn to compose low-level elements together, with how many data, and how generated data depend on training set size. These aspects are *entirely novel* with respect to the cited works and constitute the key contributions of our paper, as we will emphasize further.\n\n3. **Compositional generalization in real data.** In our view, the compositional abilities of diffusion models have already been established in various domains. Language diffusion models, for instance, are able to create new sentences using previously seen words. Regarding images, for example, the work of Sclocchi et al. (2025) demonstrates compositional abilities using forward-backward experiments: by adding a small amount of noise and then denoising an image, some of the low-level features are combined in a different way (e.g., a dog might open its mouth and bend its ears). Once again, our goal is not to prove that diffusion models compose but instead to study how this skill is gradually learned as models are trained on more and more data.\n\nGiven these points, we kindly invite the reviewer to reconsider their score.\n\n**Figure 1.** We believe there may be a misunderstanding: our theory does indeed predict the cascaded learning behavior across hierarchical levels. Specifically, it shows that rules at level $\\ell$ require a number of samples scaling as $m^{\\ell+1}$ to be learned. This prediction is precisely what we observe in Figure 1. In the inset of the figure, we explicitly rescale the horizontal axis by the theoretical prediction for each level, resulting in a collapse of the curves across layers and highlighting an excellent agreement between theory and experiments.\n\n**Other comments**\n\n1. We thank the reviewer for pointing out the typo.\n\n2. **Discrete diffusion.** We have added references to Hoogeboom et al. (2021) and Austin et al. (2021) for Equation 2. As suggested, we will also update the notation to follow Austin et al., using $Q$ for the forward transition matrix in the discrete setting.\n\nHoogeboom et al., 2021. Argmax flows and multinomial diffusion: Learning categorical distributions. NeurIPS 34.\n\nAustin et al., 2021. Structured denoising diffusion models in discrete state-spaces. NeurIPS 34.\n\n3. **Synonyms.** We thank the reviewer for the question. We have added to point *iii)* (L148) the following sentence: \"We call the $m$ strings produced by any given symbol *synonyms*\". The value of $m$ controls how many valid strings can be generated by the model. Since the number of produced strings is $v m$ ($m$ for each of the $v$ values of the parent node) and the maximum number of distinguishable strings is $v^s$, when $m=v^{s-1}$ all strings of size $s$ can be produced at any level, implying that all possible $v^d$ input strings are generated, and the data distribution has little structure. Instead, when $m<v^{s-1}$, only a small fraction of all possible strings is generated by the production rules, and spatial correlations - enabling self-supervised learning - appear.\n\n4. **Low-noise limit of the score.** This argument is presented in Section 4.1, in the paragraph \"score function at low noise\". There, we show that in the low-noise regime, the score function reduces to the conditional expectation of a token given the rest of the sequence, which is proportional to its correlations with the remaining input. As discussed, these correlations are invariant under the exchange of synonyms.", "claims_and_evidence": "I find there to be several claims in the paper which remain unsupported. For example, the title mentions \"creativity,\" a term that is not defined or discussed throughout the paper. I suggest reconsidering the title to better reflect the content.\n\nRegarding the first contribution, the authors claim to empirically demonstrate the hierarchical learning process of diffusion models. However, this concept has already been explored in previous studies, such as Sclocchi et al.'s \"A Phase Transition in Diffusion Models Reveals the Hierarchical Nature of Data\" and Li et al.'s \"Critical windows: non-asymptotic theory for feature emergence in diffusion models.\" These works provide similar insights, rendering the authors' claim less novel. Therefore, the significance of the first contribution lacks solid grounding.\n\nSecondly, regarding compositional generalization, which might be more obvious and valid for the case of context-free grammar (with which I am not extremely familiar), the contribution from a theoretical point of view stands. However, I am not convinced whether the numerical experiments really explain whether or why compositional generalization occurs in these models. The results, particularly on images, seem to show that early layers do indeed encode low-level localized features, while deeper layers represent more abstract and global factors, as the authors point out in Section 5. and provide sufficient number of references. However, I do not see, for example, why does the MMD result in Figure 5b) nor the images in Figure 5a) imply much on compositional generalization ability of diffusion models. An experiment that would be very useful to show is for example whether the model is capable indeed of generating combinations of features that have not previously been seen. To strengthen their claim, the authors could conduct additional experiments, such as testing the model's ability to generate combinations of features not seen during training. For instance, using text-to-image models, they could verify whether the model can produce feature combinations absent from the training set. Although this might be a costly and time-consuming experiment, I do believe that strong claims regarding compositional generalization of diffusion models require more extensive experimentation and convincing experimentation.\n\nIn conclusion, the paper starts off strong and develops good theory for RHM but after reading it, several claims are left unsupported.", "methods_and_evaluation_criteria": "The methods and evaluation criteria make sense for the problem at hand. I am unsure regarding Figure 1; Why does the evaluated empirical curve differ from the one suggested by theory? To be specific, could the authors comment on why does the theory not predict the cascaded learning across levels, as observed in practice (level k+1 starts to have better accuracy only after level k has a sufficiently high generalization accuracy). I think it would be very beneficial to the paper if the authors could provide explanation of this.", "theoretical_claims": "I did not check the correctness of the proofs.", "experimental_designs_or_analyses": "The experimental analyses seem to be sound.", "relation_to_broader_scientific_literature": "The problem of compositional generalization in diffusion is very timely and of great interest to the literature. Any progress towards understanding it, either from theoretical or empirical perspective is of great contribution to the community.", "essential_references_not_discussed": "There is one reference which the authors should add, mentioned above: Li et al.'s \"Critical windows: non-asymptotic theory for feature emergence in diffusion models.\".", "other_strengths_and_weaknesses": "Please see above.", "other_comments_or_suggestions": "1. Line 89 typo: Kamb & Ganguli studies -> study\n2. Please provide a reference for equation (2) for the discrete data case. Furthermore, it would be better if the authors could use different notation for the forward transition matrix q, as the same notation is used for the continuous data case, where the forward transition matrix is in fact a probability distribution.\n3. It would be beneficial if the authors could clarify or comment on what do they mean by \"synonyms\" at the beginning of Section 3.1, and how they relate to the m production rules that mentioned in the iii) part of Random Hierarchy Models introduction. It is not very clear what the authors mean by synonyms and what having a larger/smaller value of $m$ means in practice.\n4. Line 257 and 258: the authors mention that \"they demonstrate that the learning the score function in the low-noise limit corresponds to a task invariant to exchanging synonyms\" but do not reference where this is performed. Could the authors please provide a section or figure reference?", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Nc6yrEWHho", "reviewer": "Reviewer_SjY7", "summary": "This paper studies the sample complexity of learning hierarchical structures, mainly through theoretical analysis of RHMs accompanied by some experiments on synthetic RHMs as well as simple text and and image experiments. For the RHM, their theoretical analysis predicts that the production rules at a given level $\\ell$ of the tree can be learned with sample complexity proportional to $vm^{\\ell + 1}$ where $m$ is the number of production rules -- which in particular is better than exponential, and implies that the levels of the tree of learned sequentially from lowest to highest (i.e. higher-order/global structure is learned later later).\n\n**Update after rebuttal**\nThank you for the detailed responses to my questions and comments. I remain supportive of acceptance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and address their specific concerns below.\n\n**Role of branching factor $s$.**  The number of samples required to learn the full hierarchy in the absence of weight sharing is $m^{L+1}$, which is independent of $s$. In the presence of weight sharing, we expect an additional prefactor $1/d=s^{-L}$. Expressing the sample complexity as a polynomial of the dimension, one gets respectively in the two cases $md^{\\alpha}$ and $md^{\\alpha-1}$ with $\\alpha = \\log m / \\log s$. When $\\alpha$ is large, both sample complexities are dominated by the same effect.\nWe will clarify this point in the manuscript.\n\n**Network's capacity.** The generalization ability of the architecture is not due to a lack of capacity: the experiments are always run in the heavily overparametrized regime, and the networks eventually memorize their training data at the end of training. For this reason, we perform early stopping and avoid overfitting. We believe that not matching the network to the RHM structure does not change the dominant factor in the sample complexity as long as the architecture is deep enough. This is the case for both classification and last-token prediction with the RHM  (Cagnetta et al., 2024; Cagnetta & Wyart, 2024), where fully connected networks and transformers (agnostic to the RHM structure) show the same dominant factor (i.e., polynomial in the dimension) in the sample complexity as CNNs architectures matched to the data structure. We will clarify this point in the paper.\n\n**How realistic is the RHM?** We think of the RHM as the simplest yet tractable model that captures *hierarchical compositionality*, which is a property shared by many real-world data modalities. Making the model more realistic for specific datasets would involve introducing variable tree topologies, more complex non-random production rules, and possibly some context dependence - but all this would come at the cost of theoretical tractability. Despite its abstract form, the RHM captures key behaviors observed in real data, such as the staged learning and increasing-range correlations. These results cannot be obtained using simpler models (e.g., Gaussian random fields with long-range spatial correlations). This alignment between theory and empirics underscores the value of the RHM to study images and text.\n\n**Synonyms.** We thank the reviewer for pointing this out. We have added to point *iii)* (L148) the following sentence: \"We call the $m$ strings produced by any given symbol *synonyms*\".\n\n**Compositionality.** In our work, we adopt the formal notion of *compositionality* from theoretical linguistics (e.g., Montague, 1970; Partee, 2008), where it refers to the principle that the meaning of a complex sentence is determined by the meanings of its parts and the rules used to combine them. This principle underlies the ability to understand and generate an unbounded number of novel sentences by knowing the meanings of words and the grammar rules that govern their composition (Chomsky, 1957). In our setting, we interpret compositionality as the ability of diffusion models to represent and learn such structured, rule-based combinations of components. The RHM provides an idealized but expressive formalism for studying this phenomenon: it defines hierarchical, symbolic structures whose generative rules allow for compositional generalization.\nRegarding hierarchical structure specifically, it mirrors the hierarchical organization of syntax in language and the layered processing observed in biological vision systems. We will clarify our usage of the term \"compositional\".\n\nMontague, R., 1970. Universal grammar.\n\nPartee, B.H., 2008. Compositionality in formal semantics: Selected papers. John Wiley & Sons.\n\nChomsky, N., 1957. Syntactic Structures. De Gruyter Mouton.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I read the theory in section 4 and don't have any major objections. I didn't follow up on the results quoted from prior work e.g. L270.\n\nCould the authors comment on the justification for the assumption that $m \\gg s$ (L263)? Actually I don't see how $s$ enters the bounds at -- was it dropped or absorbed into a constant, or does it not appear?", "experimental_designs_or_analyses": "This paper makes reasonable choices of D3PM and standard learning settings for the RHM experiment. I think the text and ImageNet experiments also made sense, particularly the approach measuring hierarchical structure in images using different depths of ResNet embeddings.\n\nA question: In section 3.1 you describe a model architecture that seems to closely depend on the known parameters of the RHM (L, s, etc). How important is this choice? I understand needing sufficiently capacity to represent the RHM but is something special happening by not providing excess capacity? (i.e. could it be forcing the model to learn the correct RHM because it doesn't have sufficient capacity to overfit or learn an alternative incorrect model?) Would appreciate clarification.", "relation_to_broader_scientific_literature": "RHMs have been used as a theoretical tool in many prior works. As the paper states on L55 it extends the findings (Cagnetta&Wyart, 2024) of polynomial sample complexity for learning RHM models via next token prediction to diffusion. Although the theoretical gap may not be huge, I feel that the analysis of diffusions models to complement the prior analysis of autoregressive models is still worthwhile.", "essential_references_not_discussed": "No concerns", "other_strengths_and_weaknesses": "Overall I found this paper interesting. The main weakness I see is the question of whether the RHM is a realistic model for real-world data. I would appreciate further discussion from the authors on how well the RHM really represents the compositional structure of data like text, image, video, etc.", "other_comments_or_suggestions": "Would be helpful to explicitly define the term \"synonym\" before you start using it. Reader has to figure out the meaning from \"m\".\n\nI also found the use of the very-overloaded term \"compositional\" be somewhat vague and would appreciate a more concrete clarification of what is meant by it in this case, particularly with regard to hierarchical structure.", "questions_for_authors": "Please see other sections.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "00sb7Votzr", "reviewer": "Reviewer_9Hxr", "summary": "This paper shows empirically that diffusion models learn compositional rules in increasing depth. They then provide an analytic computation of the sample complexities of learning different levels of rules and show that the empirical sample complexities align with these predictions. Finally they define local and global coherence connected to these notions of compositionality and show that models learner deeper compositional rules with more training and data.\n\n## update after rebuttal\nAfter the rebuttal, in which I mainly asked the authors to clarify the limitations in the results, I increase my score to a weak accept.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and address their specific concerns below.\n\n**Scope of the analysis.** Our theoretical results are limited to the RHM, which is a form of PCFG. As suggested, we will modify the writing to stress this point in the abstract, introduction, and conclusion.\n\n**Modeling choices and random production rules.** We agree that a more detailed discussion of the RHM's applicability will improve the paper. The RHM is designed as a minimal yet analytically tractable framework that captures some phenomenology of real data as highlighted in previous work. Its simplifying assumptions - such as fixed tree topology and random production rules - allow us to compute all relevant correlations and derive theoretical predictions, which can then be empirically tested. In a more realistic setting with non-random rules, these correlations would be different, but our conclusions, formulated in terms of such correlations, would hold. Importantly, our experiments on OpenWebText, which contains richer syntactic structure, suggest that insights from the RHM, such as the fact that generated sentences achieve progressively larger coherence lengths as learning proceeds, extend to more realistic domains. We will revise the manuscript to articulate better both the strengths and limitations of the RHM, and to outline promising directions for future work, including more expressive models with context dependences or varying topology.\n\n**Relation to previous work.** We have added a discussion of these papers to the related work section. Park et al. (2024) study compositional generalization in concept space for vision diffusion models on a toy dataset, where data are shallow compositions of several features (shape, size, color, etc.). Li et al. (2024) consider hierarchical Gaussian mixtures and study when diffusion sampling localizes on a sub-mixture. Neither of these two works study sample complexity. Allen-Zhu and Li (2020) show that deep networks trained with a variant of SGD can learn a class of multivariate polynomials with a time/sample complexity polynomial in the dimension. None of these papers considered synthetic data models based on trees. \n\n**Limits of validity of the theory.** Thanks for the feedback. We will emphasize the set of assumptions made in Section 4.\n\n**Answers to questions:**\n\n1. **How realistic is the RHM?** Please see the paragraph above on modeling choices and the answer to *Reviewer SjY7*.\n\n2. **Alternative models.** We believe the local-then-global coherence predicted by our theory is not specific to the RHM, but rather reflects a broader phenomenon that would persist for more general context-free grammars. We expect our results to hold if some limited amount of context-dependence is present (corresponding to a graphical model that is not perfectly tree-like). While a complete characterization of which classes of graphical models exhibit this behavior is beyond the scope of the present work, we see this as an important direction for future research. Importantly, our findings stand in contrast to those predicted by simpler models that rely only on second-order statistics - such as Gaussian models, which dominate much of the theoretical literature in machine learning. In those settings, spectral bias theory predicts that modes are learned in order of decreasing variance, meaning that low-frequency (global) components are acquired first (e.g., Wang, 2025). This would lead to an **opposite** phenomenology, where global structure appears early in training, and local detail is learned later. The fact that the pattern predicted by our theory is also observed in real data (e.g., in Fig. 4-5) adds empirical support to the modeling assumptions behind the RHM and the broader relevance of our theoretical framework. We will clarify this distinction and its significance in the revised manuscript.\n\nWang, B., 2025. An Analytical Theory of Power Law Spectral Bias in the Learning Dynamics of Diffusion Models. arXiv preprint.\n\n3. **Autoregressive models.** Studying the sample complexity required by autoregressive models to learn data generated by a hierarchical grammar such as the RHM is a compelling direction. We view this as an important next step in understanding generative language models and plan to explore it in future work.", "claims_and_evidence": "I believe that the claims are solid and true for the particular kind of model of data (RHM) that this paper considers. I also think the experiments demonstrating local then global coherence are great and clearly support the main points. However, I have some concerns about the writing and framing; the paper sometimes unjustifiably extends these claims to much more general models of data.\n\nIn the contributions, they state \"that the learning process of diffusion models is hierarchical, progressively capturing compositional rules of increasing depth.\" This follows a discussion on the viewpoint of data as PCFG grammars, but they only exhibit this result for RHM, a form of PCFG. This distinction is extremely important and should be mentioned in the abstract and introduction. \n\nAnother example, in the conclusion, they state that \"if data consists of hierarchical combinations of features, U-Nets can lower the data dimension by giving identical representations to groups of features that have similar contexts.\" The previous sentence acknowledges that this is for a certain distribution, but this sentence is somewhat misleading because it seems to imply that you proved the statement for **all** data distributions that consist of hierarchical combinations of features. The writing should be modified to highlight the extent of the results.\n\nI think the paper would also benefit from a longer discussion on the applicability of the RHM. The authors should explain their choice of this model. In particular, I would appreciate exposition of the assumption of random production rules, which on face value seems pretty unrealistic.", "methods_and_evaluation_criteria": "Yes, the methods and evaluation criteria seem to confirm their theoretical predictions.", "theoretical_claims": "I checked the computations in Section 4, but I may have overlooked some small details.", "experimental_designs_or_analyses": "I checked the experimental design for the different experiments on text and vision diffusion models, and they seem reasonable.", "relation_to_broader_scientific_literature": "The key contribution of this paper is that they were able to show the diffusion models learns compositional rules in increasing depth under the RHM, building on the work of hierarchies and phase transitions from papers (Sclocchi et al. 2024 2023). They provide estimates of sample complexities for learning different levels of rules on RHM and verify these predictions empirically on both synthetic settings and real-world diffusion models. To the best of my knowledge, previous papers did not explore the local then global coherence for diffusion models.", "essential_references_not_discussed": "There are a few citations that are missing that are necessary to understand the contributions of the paper. For example, Park et al. 2024 (https://arxiv.org/abs/2406.19370) also explored compositional generalization over training for diffusion models, Li et al. 2024 (https://arxiv.org/abs/2403.01633) also discussed the notion of a phase transition if data are hierarchical, and Allen-Zhu and Li 2020 (https://arxiv.org/abs/2001.04413) theoretically studied how deep learning performed hierarchical learning. I think it is necessary to explain the contributions to the study of hierarchies in this paper in relation to the extensive literature on hierarchies.", "other_strengths_and_weaknesses": "Overall, I would rate the paper to be decently original and significant. Its contribution to diffusion models \ngenerating hierarchical data is clear and adds to the existing literature on phase transitions in diffusion models.\n \nHowever, I think in several places the clarity and writing of the manuscript could be improved. As I mentioned before, the authors need to clarify the extend of the contributions and limitations with respect to the choice of the model of data throughout the manuscript.", "other_comments_or_suggestions": "I thought that the presentation in Section 3.3 on sample complexities could be made clearer. This might not be necessary, but I would appreciate that the authors revise the claims in that section in terms of Theorems/Lemmas and formally state the sample complexities there. This would help clarify some of the assumptions that these arguments use, i.e. the central limit argument means that it is true in the the limit, and it would be nice to explicitly see what is going to infinity. Alternatively, the paper could carefully distinguish between what is a heuristic argument, what is a rigorous result, and what is an empirical fact before introducing a given result.", "questions_for_authors": "1. How realistic is the RHM? Why is it a reasonable model of data? \n\n2. How sensitive is your theory about local then global coherence to changes in the underlying model of data? Could alternative models of data explain that empirical behavior?\n\n3. How does your theory extend to the learning of hierarchical structures for other models beyond diffusion? It seems like autoregressive models also learn CFG languages (Allen-Zhu and Li) but it seems the RHM which does not describe data generation in an autoregressive way explain this learning?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work studies the evolution of sample complexity of diffusion models as they are trained. They show that diffusion models learn hierarchically increasing complex structures, and predict such complexity. They evaluate empirically on diffusion models trained on a synthetic dataset, by measuring the number of generated samples at different compositional complexity. 


The authors have performed a strong rebuttal, leading 2 reviewers to an increase in score. Overall, the reviewers have found (summarizing):
*  _"claims very clear and pretty convincing"_
* _"experiments also made sense, particularly the approach measuring hierarchical structure in images using different depths of ResNet embeddings"_
* _"claims are solid and true for the particular kind of model of data (RHM) that this paper considers"_


Reviewers also share dubts about the general applicability of the method beyond synthetic data and RHM. The author response to reviewers SjY7 and 9Hxr was satisfactory for both reviewers. 


Other concerns have been addressed thoroughly during the rebuttal phase, leading to an increase in score by reviewers b6pe and 9Hxr.


I believe this work has solid theoretical grounds and an interesting approach by analyzing the evolution of sample complexity through RHM. I think this work could inspire further work, or new training techniques for diffusion models. In general, I believe ICML could benefit from hosting this work. Therefore, I recommend this work for as **accept**.
Decision: Accept (poster)