Probing the Latent Hierarchical Structure of Data via Diffusion Models
Authors: Antonio Sclocchi
Alessandro Favero
Noam Itzhak Levi
Matthieu Wyart
Venue: ICLR 2025 Poster (2025)
Keywords: data structure
hierarchical compositionality
diffusion models
statistical physics
phase transition
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: A hierarchical structure in the data induces a diverging correlation length at a phase transition in diffusion models, which is observed also in text and images.

Abstract: High-dimensional data must be highly structured to be learnable. Although the compositional and hierarchical nature of data is often put forward to explain learnability, quantitative measurements establishing these properties are scarce. Likewise, accessing the latent variables underlying such a data structure remains a challenge. In this work, we show that forward-backward experiments in diffusion-based models, where data is noised and then denoised to generate new samples, are a promising tool to probe the latent structure of data. We predict in simple hierarchical models that, in this process, changes in data occur by correlated chunks, with a length scale that diverges at a noise level where a phase transition is known to take place. Remarkably, we confirm this prediction in both text and image datasets using state-of-the-art diffusion models. Our results show how latent variable changes manifest in the data and establish how to measure these effects in real data using diffusion models.

Published as a conference paper at ICLR 2025
PROBING THE LATENT HIERARCHICAL STRUCTURE OF DATA VIA DIFFUSION MODELS
Antonio Sclocchi"
Alessandro Favero" Institute of Physics, EPFL
Noam Itzhak Levi' Institute of Physics, EPFL.
Institute of Physics, EPFL
Matthicu Wyart
Department of Physics and Astronomy, Johns Hopkins
ABSTRACT
High-dimensional data must be highly structured to be learnable. Although the compositional and hierarchical nature of data is often put forward to explain learnability, quantitative measurements establishing these properties are scarce. Likewise, accessing the latent variables underlying such data structure remains a challenge. In this work, we show that barward-bacwwand experiments in diffusion-based models, where data is noised and then denoised generate new samples, are a promising tool to probe the latent structure of data. We predict in simple hicrarchical models that, in this process, changes data occur by correlated chunks, with length scale that diverges at noise level where a phase transition is known to take place. Remarkably, we confirm this prediction in both text and image datasets using state-of-the thettheart art diffusion models. Our results show how latent variable changes manifest the data and establish how to measure these effects in real data using diffusion models.
INTRODUCTION
Generative artificial intelligence (AI) systems have demonstrated remarkable capabilities in synthe- sizing data across various modalities, including images (Betker et al.) 2023 Rombach et al.) 2022) and text (Brown| 2020 Ouyang et al. 2022) Touvron et al.) 2023). The underlying reasons behind these achievements remain poorly understood. Indeed, natural data are often high-dimensional and thus generically intractable due the curse of dimensionality (Luxburg Bousquet] (0004) Bach
2017]. Hence, to be learnable, the distribution of the data must be highly structured. Characterizing this structure is a fundamental challenge central to any theory of learning.
Hierarchical compositionality (Patel et al. 2015 Mossel 2016 Poggio et al. 2017 Malach & Shalev-Shwartz/ 2018, Schmidt-Hiebert 2020 Cagnetta et al.) (0224) is a candidate property put for- ward to rationalize the success of deep architectures. In this view, data be decomposed into features organized hicrarchically. It is well-established that the grammatical structure of most lan- guages is approximately context-free and hierarchical (Chomsky, 2014 Jäger & Rogers 2012). al- though it is unclear how well this structure can capture language semantics (Goldbergg) 1995] 2015).
Likewise, pattern theory (Grenander 1996) posits that images have hierarchical structure. both cases, obtaining quantitative evidence characterizing this hierarchy and building tools to determine the associated latent variables remain a challenge.
Generative denoising diffusion probabilistic models (DDPMs) offer new handle to tackle this challenge, particularly through forward-backward experiments, where controlled level of noise is added to a starting image and then removed to generate a new one (Ho et al. 2020 Sclocchi al. 2023 Behjoo & Chertkov (003). For small amounts of noise, low-level features of the image change (Ho et 20200 Sclocchi et al. (025). Passed transition point, the class is likely
to change (Ambrogioni 2023; Sclocchi et al. 2025 Biroli et al. 2024 Li & Chen, 2024). but
remarkably some of the low-level features of the original image are still retained, predicted in
"Co-first authors. Contact: first name. last namefepfi.ch.
1 On leave from EPFI.

---

Published as a conference paper at ICLR 2025
simple hierarchical models of data structure (Sclocchi et al. 2025). However, the empirical tests in these works were limited to images and did not explore other data modalities. Moreover, the geometrical structure of the changes occurring in such a process is not known.
In this work, we derive the length scale associated with changes occurring in the brrwadd protocol in synthetic generative model of hierarchical data, and we show experimentally that our predictions hold in both language and image datasets. The synthetic model we consider belongs to the class of probabilistic context-free grammars (Rozenberg & Salomaa [997); it is thus defined on a tree graph, and its forward-backwa ward diffusion experiments can be done exactly with a message- passing algorithm. Specifically, our contributions are as follows:
In the generative model of hierarchically structured data, using mean-field description of diffusion process, we show theoretically that changes in the tokens are correlated over length scale that diverges at the class transition. This phenomenology is signature of the hierarchy in the data structure, indicating changes in deep latent variables.
the
We validate our theoretical predictions performing numerical experiments on our synthetic data with diffusion process used in practice for discrete data, showing the same phe- nomenology predicted by our theory. To do so, we measure the dynamical susceptibility, observable used to study the dynamics in physical systems.
We perform forward-backward experiments with state-of-the-art masked diffusion lan- guage models (MDLM) (Sahoo et al.) (024) WikiText. We show the presence of peaking correlation length in the token changes at finite inversion time, consistently with our theoretical model.
We perform the same experiments with vision Denoising Diffusion Probabilistic Models (DDPM) (Nichol & Dhariwal, 202T) on ImageNet. We tokenize the resulting images using the patch embeddings of a contrastively pre-trained vision encoder (Radford et al. 202T) and show that the correlations of token changes display a qualitative agreement with our analysis.
Overall, our results show how changes in latent variables affect visible data, and directly support the idea that a hierarchical latent structure is central to both language and vision modalities. Moreover, our work puts forward the forward-backwer protocol as a tool to probe the latent hierarchical structure of real data.
Organization of the manuscript In Section 2 we provide background on continuous and dis- crete diffusion models. We then define the theoretical model of hierarchical data we consider and its Bayes- Bayes-optimal denoising. In Section 3 we define the correlations between changes and asso- ciated susceptibility and then present our theoretical result on the hierarchical data model and its experimental validation. In Section 4 we report the experimental measures for the same quantities in language and image diffusion models.
BACKGROUND
2.1 DIFFUSION MODELS
Denoising diffusion models are generative models designed to sample from a distribution by reversing a step-by-step noise addition process (Sohl-Dickstein et al. 2015: Ho al., 2020 Song & Ermon| 2019 Song et al. (020)). Let indicate the time step in a sequence [O..... TT. q()) the data distribution we wish sample from, and Fy ~ ((xa) sample drawn from this distribution. Diffusion models consist of: forward process generating a sequence of increasingly noised data
I 4( ((0z)ae x.-1). where at the final time T. ær corresponds to pure noise; a backward process, which reverts the forward one by gradually removing noise. This process is typically obtained by learning the backward transition kernels p(x;,11 l2x)) using neural network. This corresponds to learning the score function, which is proportional to the conditional expectation Ey(mo| [zo]]. Sampling from q(-) is achieved by sampling noise ØT ((*T) and then applying the learned backward process to obtain new sample 2g ~ q(xa). Different diffusion models correspond to different choices of the forward process, depending on the data space under consideration (see) Yang et al. (2023) for review).
{æ, kassT q(x1...., F (2)
2

---

Published as a conference paper at ICLR 2025
Discrete data For discrete data, like text, zo consists of sequence of tokens Tu,s, i E [d]. each corresponding to a symbol belonging to a vocabulary V. In this case, we consider masked diffusion with absorbing state by introducing additional [MASK] symbol (Austin et al. 2021]. At time step 1, each non-masked token either stays unchanged or transitions to [MASK] with some probability 32. Using one-hot-encoding representation of these |V] + states, the forward transition matrix reads q(Zr,, ( = (1- 3,)1+ 3,1e where ll is the identity matrix, a column vector of all ones and еи the one-hot-encoding of the [MASK] symbol. At the final time T. ZT, [MASK] for every E [d]. In the following, we consider the noise schedule 3 = 1 -1+11-++ such that q = [MASK] at)) = I/T (Austin et al. 2021).
Continuous data For continuous data, like images, corresponding to zu E R we consider the diecriisret Gaussian diffusion introduced (Ho et al. 2020). The forward transition matrix reads (( ( (axx; vI -, Byll), where N represents the Gaussian probability dis- tribution and the sequence {BehiseTT is the variance schedule. At the final time T, 2T ~ NN0, T)-
borward-backward experiments involve inverting the diffusion process at intermediate time t = T. Starting from Te. the forward process up to time produces a noisy sample a, ~ q( [z)) The backward process, obtained from a diffusion model, produces a new sample (1) p( a..). We refer l as the inversion time of the forward-backwartt process.
Forward-backward bbackward experiments
2.2 THE RANDOM HIERARCHY MODEL (RHM)
The RHM is generative model of hierarchically structured data introduced by (Cagnetta et al., 2024). It belongs to the class context-fire grammars in the field of language theory (Rozenberg & Salomaa 1997), and assumes that production rules random. In its simplest version, consists of:
A regular tree graph of depth L and branching factor s. Each node of the tree corresponds
discrete random variable.
. L the tree. We call A discrete vocabulary v(() of size v for each level & = 0, 1,......
{ the level of the leaves and e L the root level.
A set of production rules defining how each symbol belonging to Q(O can be represented at the lower level with the symbols of (v((-1))88, For each element of V(O, there are m equivalent lower-level representations, which are all distinct and chosen randomly.
We use the notation (())) to indicate the variable at level and position [s4-9]. The leaf nodes h (0) ...... h..., correspond to the visible tokens, while the upper-level nodes represent latent variables. See App. A for an example. We define the tree distance between two visible tokens as the number of edges between them and their lowest common ancestor. Their corresponding real space distance r is r s Because the hierarchical structure generating the data, the visible tokens have non-trivial spatial correlations, which depend on their tree distance (Cagnetta & Wyart 2(25
2.2.1 BAYES-OPTIMAL DENOISING OF THE RHM USING BELIEF PROPAGATION
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., 2025) using the Belief Propagation (BP) algorithm (Mezard & Montanari, 2009). Specifically, if an RHM datum 2n is corrupted by some noise, c.g., via masking a fraction tokens, resulting in a noisy observation x2, then BP can be used to:
compute the marginal probabílities of any latent or visible variable, conditioned on the noisy observation æ;: p(h lac.):
sample directly from the posterior p(
If the noisy observation is produced by forward diffusion process, then sampling from p( (r)) equivalent to integrating exactly (i.e., for an infinite number of time steps) the backward diffusion process starting from æ, and using the exact score function. In fact, BP can also be used to compute [zo]. corresponding to having access to a neural network achieving perfect generalization (see App. A.1.3 for a comparison between BP sampling and backward diffusion with the score function). This is a different situation with respect to real data, like images and text, where the score is estimated by training neural network.
the score function, which is proportional to Eptig (m,)
3

---

Published as a conference paper at ICLR 2025
2.2.2 DIFFUSION PROCESSES IN THE RHM
For the RHM data, we consider two different processes.
e-rrocess This is a simplified process where one considers any datum Po that can be generated by the RHM, and assumes that there is some level of uncertainty on each visible token (see App. A.1.2 for details). One then uses BP to compute the probability that the initial datum was &g. The noising process is controlled by a noise-to-signal ratio é E [0, 11, which plays the role of time in the standard diffusion processes, such that e 0 at f 0 and
T. Starting from an RHM datum Zg. we indicate with æ, the noisy observation at the leaf priors. Therefore, BP computes the marginals p(h (xx) and samples from o(#b)(2e) We study theoretically this process in section 33. through mean-field approximation, neglecting some fluctuations of the marginal probabilities and averaging over the disorder of the RHM.
Masking diffusion with an absorbing state This is the diffusion process described in section 2.1 for discrete data, which is commonly used practice. We study it numerically with BP in section 3.2
Phase transition in the class reconstruction of the RHM Sclocchi et al. (0255) ) showed that there exists regime of the RHM parameters where the probability of reconstructing the class in the e diffusion process, that is p(h) æz), undergoes sharp phase transition at a critical noise level e* in the limit of large L. Therefore, sampling @o(c) ~ p(.)) ) for < 6", (c((c) and zo share the same latent h(()) (i.e. they belong to the same class), while, for e > c", the probability that (c(c) and zo share the same class corresponds to the random chance 1/ I/v.
In Fig. 10, we show numerically that also in masking diffusion the probability of reconstructing the class p(h (x)) undergoes a phase transition at specific inversion time t².
3. HIERARCHICAL STRUCTURES INDUCE CORRELATED BLOCKS OF TOKEN CHANGES
In this section, we characterize the statistics of how the input tokens change in the forward- backward experiments. Let Zg,; denote the i-th input token, i E [d]. and (t, the same token after undergoing a forward- backward experiment with inversion time t. We seek to compute the correlations between changes in the tokens as a function of the inversion time L. For each token position we introduce variable (I) characterizing the dynamics.
Definition (Token change), If the tokens To, and (t) take values in a discrete vocabulary, then (t(() is spin variable defined as
+1,
xo * ft,
01(() 1-1
if êt,
Definition 2 (Dynamical correlation function), Given the o,(t) defined above, the dynamical corre- lation function between the changes of tokens at positions and j. relative to the initial point Da, is defined as
Czo.s ás (t) (av(t)a,(t)) - (a, (a))((()))))
(2)
where (.) denotes averaging over different stochastic trajectories. The average dynamical corre- lation function is defined (t) (t), where the overline indicates averaging over the initial point Vo.
Given the correlations, we compute the dynamical susceptibility x(t), a quantity used to study the dynamics in physical systems (Donati et al., 2002 Toninelli al. (2005).
Definition 3 (Dynamical susceptibility). Given the average correlation function Cty(t) of Defini- tion 2 the dynamical susceptibility is defined as
Ed EI Co(() x(t)
(3)
EL, CR()) where we normalized by the sum of auto-correelaiion.
4

---

Published as a conference paper at ICLR 2025
Intuitively, the susceptibility measures the volume of the blocks of tokens that change together.
In the case of the e-process for the RHM, where (e is sampled from p( the same defini- tions hold for the quantities (e) and x(e). In the case of continuous embeddings, where the tokens 4 for image diffusion), the same definitions for
Zo,i and (t) are continuous vectors (see Section
Ciy(t (t) and (t) hold by redefining oz (t) as (t) Do (t)x(t)l
3.1
MEAN-FIELD THEORY OF THE E-PROCESS OF THE RHM
The average correlation function (c) can he computed for the 6-process of the RHM through mean-field approximation. This mean-field approach consists of computing the average BP messages at each layer É, where the average is performed over the possible realizations of the RHM
rules. Let's consider two leaf nodes h,0)) and h connected to the common ancestor h( layer & through the nodes hn(-1) and (((-1) (see Fig. 1 for an illustration). Their associated spin variables (0)
are therefore o jj Ok of (8-1) and dm where we omit the dependence to lighten the notation. Given the tree structure, the joint probability distribution P(o! ( can be written
P(o: (0) 10))
Σ
P(o: (0)
(1-1)) P(o)) (0) 10 (ll-1))) P(o (6-1) .om (l-
(4)
of (1-1) (E-1)
m0
Each element in the sum of Eq. can be written in terms of BP messages, and its average value can be com- puted by averaging over the realizations of RHM rules. (0) The average of P(o oo (((-1) and P(a, 10 ( can be written as 2 x 2 matrix (((-1) only depending on the layer & 1. Similarly, also the average of the joint probability P(a)
bi
(t-1) ((a((-1) om 1)) can be represented as a 2 x 2 matrix C(I-1), In the mean-field approximation, we neglect the fluctuations of these quantities around their means. Therefore, we compute the average joint proba- bility ((o (1)) by substituting the elements the product of Eq. 4 with their means. For spin variables and tree distance we have
Figure 1: Example of leaf nodes h,!
connected the common ancestor
P(o!") (0) (00) ()- (tt-1) T((-1)
(5)
h through h ((-1) and ((f-1).
All the expressions for the above quantities are reported in App. A.2 With a similar procedure, we can compute the average marginal probability p(o(")). From these quantities, we obtain the average correlation function Cıy(e) each noise level e.
3.1.1 DYNAMICAL CORRELATION LENGTH
In what follows, present main result predicting a power law divergence of the dynamical cor- relation length at the phase transition. Technical details the derivation are reported in App. A.2.I
Main result (Divergence of the correlation length). Consider the RHM in the limit L - oc, with parameters v, m. 8 such that the probability of reconstructing the class in the e-process undergoes phase transition noise level e* (condition 28 in App. A.2 Then, the correlation length E(e) associated to the dynamical correlation function (e) diverges at the class phase transition e* as
E~ |c 1-----1" c'I"",
where v is a function of v, m, 8 reported in Eq. (54) of App. A.2.1
This divergence of the correlation length at the class transition indicates that large blocks of tokens change in concert. fact, these large correlated changes are caused by the modifications of deeper and deeper latent variables near the transition (see Fig. 3 for illustration). At both smaller and larger noise levels, the correlation length decays. This behavior of the dynamical correlation func- tions implies that the dynamical susceptibility also peaks the transition, hallmark of criticality.
5

---

Published as a conference paper at ICLR 2025
(a-l)
e-process: spatial correlations
(a-11)
e-process: susceptibility
10
experiments
2-0,0
000.0
theory
C(r.)) Cin.
0-0.74
10-1
10-*
10
10
10'
10
0.2
0.4
0.5
0.8
1.0
1
(b-1)
Masking diffusion: spatial correlations
(b-1l)
Masking diffusion: susceptibility
10
0-0.00
1-0.00 T
3.0
C(r,t) / ((0, ()
T-0.30
1-0.80 T
T.0.34
1:0.00
10
T-0,00T
10
1.5
10
10
0.8
++r
t
Figure 2: Correlation measures on diffusion samples of the Random Hierarchy Model (RHM). (a-I) In the e-process, the average correlation function shows correlation length that is maximal for 0.74, corresponding to the class phase transition, with a system-spanning power-law be- havior. The full lines experiments
with Belief Propagation, while the dashed lines the corresponding mean- field theory description (Section B.T). showing excellent agreement. (a-lI) Cor- respondingly, also the average susceptibility shows a peak at the transition e" (b) The same behavior is observed for the correlation function (b-l) and the susceptibility (b-Il) for masking diffusion. In this case, the phase transition is observed for inversion time length and the susceptibility peak. Data for RHM parameters v = 32, m = 8, = 2, L 9, averaged over 256 starting data and 256 diffusion trajectories per starting datum.
0.3 T. where both the correlation
3.2 NUMERICAL EXPERIMENTS
To test our theoretical predictions for the e-process, in Fig. 2 (a-I), we present the average correlation functions ((r,e), corresponding Cty(t) averaged all pairs ij such that their real space distance r, and normalized by the auto-correlation C(O, c). We observe that the correlation function 0.74, while it decays faster with distance when * e". This observation implies correlation length that peaks at the critical value e*. Consistently, also the susceptibility X(e) in Fig. 2 (a-II) peaks at this critical value. We compare both the correlation functions and the susceptibility measures with the theoretical predictions obtained by the mean-field theory of the e-process (dashed lines in Fig. P (a-I) and (a-Il)), showing excellent agreement. Moreover, in 9 App. A we test the prediction for the critical exponent of the correlation length of Eq. (6) also showing very good agreement.
displays system-spanning power-law behavior a critical value
In the panels (b-I) and (b-II) of Fig. 2 we report the average correlation functions C(r, t) and sus- ceptibility (t) for masking diffusion at different inversion times t. Also in this case, the correlation length and the susceptibility are maximal at specific critical time t* s 0.3 T. From Fig. 10 observe that this critical time t" corresponds to the phase transition the class reconstruction prob- ability. Although there is not simple mapping between the masking probability t/T and the noise level in the simplified e-process, the qualitative behaviors in the two settings show a remarkable agreement, validating the relevance of our theoretical predictions for both kinds of diffusion process.

---

Published as a conference paper at ICLR 2025
(t)
20
8006
(a) 10 0.3
Figure 3: Masking diffuusion in the RHM for masking fraction (a) t/T 0.3 and (b) t/T 0.5. The bottom sequence represents the starting datum To. The blue (green) symbols are the masked ones in 2, that (do not) change feature in @t). The leaves of the tree represent the sampled sequence (t) ~ (x:) In the corresponding tree, the red nodes are those that changed features with respect the generating tree of zo- We observe that larger blocks of changed tokens reflect changes in deeper latent variables.
3.3 SPATIAL CORRELATIONS IN DATA ARE NOT SUFFICIENT TO GET A SUSCEPTIBILITY PEAK
In the RHM, the latent hierarchical structure induces spatial correlations both between the input tokens and in their changes in the whether any model of data displaying spatial correlations, even without a latent hierarchical structure, exhibits the same phenomenology of the RHM in the forward-backwant diffusion.
diffusion. Therefore, it is natural to ask
In App. B we show that this is not the case. In particular, we consider a Gaussian random field model with covariance having power-law decaying spectrum. This induces spatial correlations in the field that decay algebraically with the distance. We show that performing herward-hackwandd diffusion at different inversion times results variation field having a correlation length that creases monotonically with f and is maximal at the final time = T. This behavior contrasts sharply with the hierarchical data studied here, where the growing length scale occurs in correspondence with phase transition at a finite inversion time t".
In fact, the mechanisms behind the dynamical correlations are different. For Gaussian random fields, the noise of the diffusion acts as a low-pass filter, which defines characteristic scale below which mode reconstructed in the backward process. For hierarchically structured data, instead, the spatial correlations in the changes are associated with the changes of latent variables at different levels of the hierarchy. Therefore, a diverging correlation length is present only when the reconstruction probability of the root node (i.e., the class) undergoes phase transition.
4 EXPERIMENTS ON NATURAL LANGUAGE AND IMAGE DATA
This section extends our analysis real-world scenarios, demonstrating that language and vision diffusion models exhibit the same phenomenology as observed in the RHM.
Language diffusion models We consider Masked Diffusion Language Models (MDLM) (Sahoo et al. 2024) utilizing the GPT2 tokenizer. We perform samples from the WikiText2 dataset. In Fig. (a), illustrate how an initial paragraph changes with different inversion times f. At small f, only few isolated words are modified. At intermediate I, we clearly observe clusters of words changing in a correlated manner. At large f, only small fraction of the initial sentence remains unchanged (see App. A presentation of the same data in their larger context). In Fig. 4 (b-c), we quantify these observations by measuring the average correlation functions and susceptibility Strikingly, in line with the phenomenology obtained for the RHM, we find a growing correlation length as t increases, reaching a maximum 7 +
experiments starting from
'To avoid finite size effects due imposing fixed masking fraction, integrate the average correlation function up the maximal correlation length O(10).
7

---

Published as a conference paper at ICLR 2025
(a)
Masking fraction t/T 0.1
Masking fraction t/T - 0.5
The third day, September the situation worsened. The weather was hot and ammunition, food and supplies were nearly completely exhousted
The third day, September the situation worsened. The weather hot and ommunition, food and
Original
supplies were nearly completely exhousted
Forward-
The third day, September 3, the situation worsened. The weather was hot and ammunition, tanks and supplies were nearly completely exhausted
the same day, September 29, the situation worsened. The weather was hot and ammunition, food and materials were almost completely exhausted
Backward
Masking fraction t/T 0.7
Masking fraction t/T = 0.9
warsened. The weather was emmunition, food and supplies were nearly completely exhausted
The third day, September
The third day, September 3, the situation worsened. The weather was hot ammunition, food and supplies were nearly completely exhausted
Original
Forward-
Next day, September the situation worsened. The weather hot and humid, and the prisoners were, almost completely exhausted
information maps the actual burial
Backward
population size, The number probably around 30,000, glmost completely encroached
10"
1.5
(b)
t=
(c)
T-2
1.4
103T
/ /C10
10-1
1-04
1.3-
TOST
T6T
$12 1.2
Cir,t)
(r.t)/
-88
1.1
10-2
09
0.9
10-3
10a
10a
0.0
0.2
0.4
0.6
0.8
1.0
14r
t/T
Figure 4: Forward-backwand experiments with language diffusion models. (a) Forward- backward examples for different masking fractions. The words in blue (green) are those that were masked and changed (did not change), while the words in red changed following the backward pro- cess. (b) Normalized correlations as function of index distance = l jl for different fractions of masked tokens. (c) Susceptibility xt) as a function of masking fraction. The results are averaged over Ns 300 samples, each consisting of Nr 128 tokens, with NR 50 noise realizations for each masking fraction. The susceptibility is given by integrating over the domain r E [0, 10).
tokens at critical inversion time 1* 0.6 followed by subsequent decline. Additionally, the susceptibility peaks at 1", establishing the existence of a phase transition for the language modality.
Vision diffusion models We extend our analysis to computer vision by considering Improved De- noising Diffusion Probabilistic Models (Nichol & Dhariwal (221). trained on the ImageNet dataset. To compute the correlation between changes in the image tokens, we follow recent trends in multi- modal L.MSs (Liu et 2024 Dai et al. 2003). Specifically, we divide each image into 7 patches and use the last-layer embeddings for each patch from CLIP ViT-B32 (Radford al. 2021 to to- kenize the image. Let æo,; denote the embedding of the i-th patch, where (k. () with 6,7 E [7]. After the backwad process, the variation of each patch embedding is given by (t; Z0,i (t). We then compute the average correlations between the norms these variations:
(t) = Aa; (1) Ae, Ae, (01)) - (I) [| (O1I)
The susceptibility is subsequently obtained as x(t = E., Cy(t)/ Ct))). In Fig. we present some examples of starting images and generated ones at different inversion times t, Together with the grid representing their tokenization. We observe that, for increasing i, new semantic elements appear in the generated images, corresponding to blocks tokens changing in concert. Fig. 6 present the average correlation functions and the susceptibility for vision DDPMs, starting from samples of the ImageNet validation set (Deng et al.) 2009). At a critical inversion time 1x 0.6 + 0.. T, observe peak in susceptibility, signaling the class phase transition in these
8

---

Published as a conference paper at ICLR 2025
=
0.7.T
110
Figure 5: Examples of images generated at different inversion times with forward-backward diffusion. The first column represents the starting images do. while the other columns represent the generated ones (t). The grid indicates the tokens represented inside the CLIP vision encoder. For inversion time t >> O, the red patches indicate the token embeddings that have variation magnitude larger than a fixed threshold. These patches of variation appear domains of growing size around the class transition, observed for t 0.6 + 0.77 (Fig. 6
(a) 1
L-0.1
1-00
(b)
5.0
1-03
1-08
C(r,t) C10,
1-037
4.0-
x(t)
3.5
10
3.0
2.5
2.0
0.2
0.1
0.6
1+r
1/T
Figure 6: Correlation measures on the variation of CLIP embeddings of images generated with forward-backward diffusion. (a) The average correlation function displays system spanning power-law behavior for 0.6 0.7 T, corresponding the class phase transition (ef. Fig. (3). (b) In correspondence with the phase transition, the average susceptibility displays peak. Data obtained with 344 starting images and 128 diffusion trajectories per starting image. The shaded areas correspond to the standard deviations the starting images.
models. This finding highlights the compositional semantic structure of image data, similar to the phase transitions observed language diffusion models and the RHM.
RELATED WORK
Phase transitions in diffusion models Several works have studied phenomena related to phase transitions diffusion models. Biroli et al. (2024); Ambrogioni (2023) show the presence of different dynamical regimes in the diffusion process separated by 'speciation' cross-over where bimodal distribution merges into a mono-modal one. Li & Chen (2024) provide bounds for critical time windows appearing in the diffusion of mixtures of strongly log-concave densities. These works do not consider hierarchical data, and thus do not present growing dynamical susceptibility or length scale at the transition.

---

Published as a conference paper at ICLR 2025
Hierarchical models of images and text Generative models have been used to describe the struc- ture of data in several contexts, including in linguistics and signal processing. For languages, hicrarchically-sttutuurrddd formal grammars
often used model of their syntactic structure (Rozenberg & Salomaa 1997). Likewise, pattern theory formalizes the semantic decomposition of visual scenes through hierarchy of features (Stoyan 1997: Jin & Geman [2066] (iskind et al. 2007]
Li et al.) 2009). More recently, images have been described through hierarchical decomposition
multi-scale wavelet coefficients (Marchand al. 2022 Kadkhodaie al. 2023 although the
underlying structure, in this case, is not tree-like.
Semantic vs geometrical description of images Several studies [Rissanen et al. 2022 Wang & Vastola 2023) pointed out that the backward diffusion process of images acts on coarse-to- to-fine scales. Since the Fourier spectra of images decay power laws, higher frequencies are affected at short diffusion times, while low-frequency modes persist for longer. This precisely the pattern we describe in the Gaussian random field model in Section 3.3 and App. B While this viewpoint is an appropriate starting point to describe the geometrical structure at the pixel level, our hierarchi- cal model seeks to capture a high-level, semantic description of images that we test using CLIP encoder. This means that high/low-level features can correspond to parts of objects - such as the eyes, mouth, and nose of face rather than simple geometric or frequency components. The two descriptions are, therefore, complementary.
Hierarchical models in machine learning theory Several studies (Mossel 2016 Shalev-Shwartz
al.) 22177; Malach & Shalev-Shward 2018 2020) have shown that the correlations between in- put and task are crucial for determining learnability in hierarchical data. Furthermore, the internal representations of trained deep networks reflect the data's latent structure (Cagnetta et al., [024] Allen-Zhu & Li 2023). Sclocchi et al. 2025) showed that diffusion on hierarchical data can be solved using Belief Propagation. Mei (2024) showed that U-Nets can efficiently approximate the Belief Propagation algorithm on hierarchical data, while Garnier-Brun et al. (0224) provided evi-
dence that transformers can implement the same algorithm.
DISCUSSION AND CONCLUSION
In this work, we showed that when data exhibit hierarchical structure, the changes induced by forward-backward experiments in diffusion models reveal growing correlation length and susceptibility near a phase transition. At this critical point, changes the data become highly correlated, reflecting changes in deep latent variables. In particular, we focused understanding how modifications in the latent variables manifest in the data, in contrast with common approaches which attempt to reconstruct the latent representations from visible data.
Our predictions for a hierarchical model were confirmed through experiments across different natural data modalities, showing a remarkable level of universality. This supports the hypothesis that hierarchical and compositional structures are fundamental, universal properties underlying natural data as diverse as images and text.
Such fundamental analyses have the potential to impact practical applications. For example, they can enhance the interpretability of deep networks, whose representations are believed to reflect the hierarchical structure of data. Moreover, the diffusion dynamics of high and low-level features can suggest improved training strategies, for instance, to avoid mode collapse when fine-tuning diffusion models (Barceló et 2024).
Future work may include interpreting the large, correlated changes in text in terms of grammatical structure and context variables, possibly sharpening these concepts through the data-driven method introduced in this study. Moreover, better capturing the grammatical structure of real languages may require considering more general latent models involving context dependencies. A challenge for future work is extending our theoretical analysis to such cases.
ACKNOWLEDGMENTS
We thank Umberto Maria Tomasini for discussions at the early stages of this project. We thank Francesco Cagnetta, Daniel Korchinski, and Jack Parley for providing feedback on the manuscript. NL is supported by the EPFL A14science program. This work was supported by a grant from the Simons Foundation (#454953 Matthieu Wyart).
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Zeyuan Allen- -hlnn-Zhu and Yuanzhi Li. Physics of language models: Part 1, context-free grammar. arXiv preprint arXiv:2305. 13673, 2023.
Luca Ambrogioni. The statistical thermodynamics of generative diffusion models. arXiv preprint vrXiv:2310.17466) 2023.
Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 14:11981117993 2021.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-68) 2017.
Roberto Barceló, Cristóbal Alcázar, and Felipe Tobar. Avoiding mode collapse diffusion models fine-tuned with reinforcement learning. arXiv preprint arXfv:2410.08315, 2024.
Hamidreza Behjoo and Michael Chertkov. U-turn diffusion. arXiv preprint arXiv:2308.07421,
James Betker, Gabriel Goh, Li Jing, Tim Brooks, Jianfeng Wang, Linjie Li, Long Ouyang, Juntang Zhuang. Joyce Lee, Yufei Guo, al. Improving image generation with better captions. Computer Science. https://cdn. openai. com/papers/dall-e3. pdf. 2(3), 2023.
Giulio Biroli, Tony Bonnaire, Valentin De Bortoli, and Mare Mézard. Dynamical regimes of diffu- sion models. Nature Communicationns 15(1):9957, 2024.
Tom B Brown. Language models are few-shot learners. arXiv preprint arXiv:2005. 2020.
Francesco Cagnetta and Matthieu Wyart. Towards a theory of how the structure of language is acquired by deep neural networks. Advances in Neural Information Processing Systems, 37: 13119-83163, 2025.
Francesco Cagnetta, Leonardo Petrini, Umberto M Tomasini, Alessandro Favero, and Matthieu Wyart. How deep neural networks learn compositional data: The random hierarchy model. Phys- ical Review X, 14(3):031011, 2024.
Noam Chomsky, Aspects of the Theory of Syntax. Number 11. MIT press, 2014.
Wenliang Dai, Junnan Li, Dongxu Li, Anthony Meng Huat Tiong, Junqi Zhao, Weisheng Wang, Boyang Li, Pascale Fung, and Steven Hoi. Instructblip: Towards general-purpon vision-language models with instruction tuning. arXiv preprint arXiv:2305. 06500, 2023.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. Ieee, 2009.
Claudio Donati, Silvio Franz, Sharon Glotzer, and Giorgio Parisi. Theory of non-linear sus- ceptibility and correlation length in glasses and liquids. Journal of non-crystalline solids, 307: 215-224, 2002.
Jérôme Garnier-Brun, Marc Mézard, Emanuele Moscato, and Luca Saglietti. How transformers learn structured data: insights from hierarchical filtering. arXiv preprint arXiv:2408. 15138, 2024.
Adele E Goldberg. Constructions: A construction grammar approach to argument structure. Chicago
UP. 1995.
Adele Goldberg. Compositionality. In The Routledge handbook of semantics, pp. 419-433. Routledge, 2015.
Ulf Grenander. Elements of pattern theory. JHU Press, 1996.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-6851, 2020.

---

Published as a conference paper at ICLR 2025
Gerhard Jäger and James Rogers. Formal language theory: refining the chomsky hierarchy. Philo- sophical Transactions of the Royal Society B: Biological Sciences, 367(1598):1956-19777 2012.
Ya Jin and Stuart Geman. Context and hierarchy in a probabilistic image model. In 2006 IEEE computer society conference on computer vision and pattern recognition (CVPR'OC (06), volume 2, pp. 2145-2152. IEEE, 2006.
Zahra Kadkhodaie, Florentin Guth, Stéphane Mallat, and Eero P Simoncelli. Learning multi-scale local conditional probability models images. arXiv preprint urXiv:2303.02966 2023.
Li-Jia Li, Richard Socher, and Li Fei-Fei. Towards total scene understanding: Classification, an- notation and segmentation in automatic framework. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 2036-2043, IEEE, 2009.
Marvin Li and Sitan Chen. Critical windows: non-asymptotic theory for feature emergence in diffusion models. arXiv preprint wwxxv:244330063333 2024.
Haotian Liu, Chunyuan Li, Qingyang Wu, and Yong Jae Lee. Visual instruction tuning. Advances in neural information processing systems, 36, 2024.
Zhuang Liu, Hanzi Mao, Chao- Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. A convnet for the 2020s. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. pp. 1997-11986, 2022.
Ulrike von Luxburg and Olivier Bousquet.
Distance-based classification with lipschitz functions. The Journal of Machine Learning Research, 5(Jun):669695, 2004.
Eran Malach and Shai Shalev-Shwartz. A provably correct algorithm for deep learning that actually works. arXiv preprint arXiv: 1803,0920, 2018.
Eran Malach and Shai Shalev-Shwartz. The implications of local correlation on learning some deep functions. Advances in Neural Information Processing Systems, 33:1322-13322 2020.
Tanguy Marchand, Misaki Ozawa, Giulio Biroli, and Stéphane Mallat. Wavelet conditional renor- malization group. arXiv preprint (2XXiv2207..04411, 2022.
Song Mei. U-nets belief propagation: Efficient classification, denoising, and diffusion in genera- tive hierarchical models. arXiv preprint arXiv:2404. 18444, 2024.
Mare Mezard and Andrea Montanari. Information, physics, and computation. Oxford University Press, 2009.
Elchanan Mossel. Deep learning and hierarchal generative models. arXiv:1612.09057, 2016.
arXiv preprint
Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. In International Conference on Machine Learning, pp. 8162-8171. PMLR, 2021.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to fol- low instructions with human feedback. Advances in neural information processing systems, 35: 27730-27744, 2022.
Ankit B Patel, Tan Nguyen, and Richard G Baraniuk. A probabilistic theory of deep learning. arXiv preprint arXiv: 304.00641, 2015.
Tomaso Poggio. Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda. and Qianli Liao. Why and when can deep-but but not shallow-networks avoid the curse of dimensionality: a review. Inter- national Journal of Automation and Computing, 14(5):503-519 2017.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pp- PMLR, 2021.
12

---

Published as a conference paper at ICLR 2025
Severi Rissanen, Markus Heinonen, and Amn Solin. Generative modelling with inverse heat dissi- pation. arXiv preprint arXiv:2206.13397, 2022.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Bjöm Ommer. High- resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF confer- ence on computer vision and pattern recognition, pp. 10684-10695, 2022.
Grzegorz Rozenberg and Arto Salomaa. Handbook of Formal Languages. Springer, January 1997. doi: (1077998-3-642-599
Subham Sekhar Sahoo, Marianne Arriola, Yair Schiff, Aaron Gokaslan, Edgar Marroquin, Justin Chiu, Alexander Rush, and Volodymyr Kuleshov. Simple and effective masked diffusion language models. arXiv preprint arXiv:2406.07524, 2024.
Johannes Schmidt- Nonparametric regression using deep neural networks with relu activation function. The Annals of Statistics,
2020.
Antonio Sclocchi, Alessandro Favero, and Matthieu Wyart. A phase transition diffusion models reveals the hierarchical nature of data. Proceedings of the National Academy of Sciences, 122(1): e2408799121 22,, 2025.
Shai Shwarz, Ohad Shamir, and Shaked Shammah. Failures of gradient-basee deep learning. In International Conference on Machine Learning, pp. 3067-3075, PMLR, 2017.
Jeffrey Mark Siskind, J Sherman, Ilya Pollak, Mary P Harper, and Charles A Bouman. Spatial random tree grammars for modeling hierarchal structure in images with regions of arbitrary shape. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(9):1504-1511 2007.
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International conference machine learn- ing, pp. 2256-2265. PMLR, 2015.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Yang Song, Jascha Sohl--Dcckttei, Diederik Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint 1rX1v:2011.134566, 2020.
Stoyan. Grenander, ulf: Elements of pattern theory. johns hopkins university press, baltimore and london, 1996, xiii+ 222 pp., hardcover,f 54.00, isbn 0-8018-51877-8 1997.
Cristina Toninelli, Matthieu Wyart, Ludovie Berthier, Giulio Biroli, and Jean-Philippe Bouchaud. Dynamical susceptibility of glass formers: Contrasting the predictions of theoretical scenarios. Physical Review E- Statisisti,,ll, Nonlinear, and Soft Malter Physics, 71(4):041505 2005.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint urXiv:2302. 13971, 2023.
Binxu Wang and John J Vastola. Diffusion models generate images like painters: an analytical theory of outline first, details later. arXiv preprint arXiv:2303.02490. 2023.
Ling Yang, Zhilong Zhang, Yang Song, Shenda Hong, Runsheng Xu, Yue Zhao, Wentao Zhang, Bin Cui, and Ming-Hsuan Yang. Diffusion models: A comprehensive survey of methods and applications. ACM Computing Surveys, 56(4):1-39, 2023.
13

---

Published as a conference paper at ICLR 2025
A
THE RANDOM HIERARCHY MODEL
Data generation in the RHM A datum of the RHM is generated with the following procedure:
symbol at the root h(4) is chosen uniformly random from B(L);
one of the m production rules associated with the symbol sampled at the root is chosen uniformly at random. This choice defines the values, belonging to 7(4-1), of the children
nodes h/ 1 ................................ h(4-1);
the procedure is iterated sampling the symbols at layer & according to the symbols at layer & and their respective production rules;
result, string of sf symbols belonging to V(o) is generated at the leaf nodes. This string the generated datum æ.
Levels
Production Rules
ef df dd
fe
fd
(=2+1=1
ed
hi
85
ii
hh
f=1=1=0
gi
hg
gh
1=
Left: example of production rules with vocabularies y(22 {a, b, c). y()) {dd, e, f). 4(()) = {g. i). Right: one possible datum generated by the production rules, with the hierarchical levels indicated on the right.
Figure 7: Example of RHM with == 2, 2
A.1 DENOISING THE RHM WITH BELIEF PROPAGATION
In the RHM, knowing the production rules of its tree structure, the Bayes-optimal denoising of its data can be done exactly using the Belief Propagation (BP) algorithm (Sclocchi et al. 2025).
In the factor graph of the RHM tree, all latent and visible variables b(9 represent variable nodes, while the RHM rules connecting them are factor nodes. Each variable node associated to two BP messages, one coming from below, by (b(()), ), and one coming from above, 11 (h(")). The starting point of the BP algorithm is the definition of the messages at the boundaries of the tree, which are
the upward messages the leaves in (b! and the downward message at the root node "n (h) Since we consider glass-unconditional diffusion processes, we consider the latter as being uniform over the values of (4)), The initialization the leaves, instead, corresponds to the prior belief on the values of the single visible tokens, which is given by the noisy observation. In the case of diffusion processes, the noisy observation æ, gives prior beliefs v4 (h p( (s),,)), which can be computed for the single token by Bayes' rule and depends on the specific diffusion process under consideration.
A.1.1 BP ITERATION
The initialization of BP is given by the leaf messages V, (h."), E [. For each s- s-patch at level e, (E+1) the upward message in
e.g., (h("))==,... > having a common parent node layer l e.g. h the upper level is computed as:
B/ (bf (e+1) = -y)
Σ
2h(l-1) (y. a1 II ve (n = a.).
(8)
EV0))
24 (++1)
14(h
(E+1) (E+1) = y) Everrenn (b) (6+1) =
14

---

Published as a conference paper at ICLR 2025
where the factor (b++1) (y, a1......,.. (Q.....,a))) reads
V ay.a1,... as)
{
1,
if y - (a1...,,s) as) is rule at layer (e + 1) -
(10)
otherwise.
This upward process is iterated from the leaf nodes é = 0 until the root node at T.. Afterward, BP computes the downward messages. The initialization at the root node is given by a uniform prior over the symbols of y/4,, i.e.
1i (1) [110=10 = -a===)=- = Va w(L)
(11)
For the same s-patch at layer and parent node layer + as before, the downward message for h is given by
(1(h1 = a1) =
Σ
gilett) al as) (1( = y) II 14 (b =a:), (12)
"2 Ey100, Ey(0000-)) DEV((+1)
Dy (h (h(()) =0) Ev'ence (1)
(b = a)
(13)
(2) a')
with the same factor node of Eq. 10
At the end of the upward-downwed messages for each symbol of the vocabulary y(0; (b((") and my (h) Their product gives the marginal probability of the value of the node:
iteration, each variable node h, is associated with two BP
p(h a) x (h a) 11 (h a), a V
(14)
These marginal probabilities are conditioned on the BP messages at the leaf nodes, which can come from noisy observation of an RHM datum, as is the case for denoising diffusion.
Similarly, sampling from the posterior probabilities given by BP is done by starting sampling from the marginal probability at the root and then iteratively updating the marginal probabilities every time a new node sampled (Mezard & Montanari 2009).
A.1.2 PRIORS THE LEAVES
Masking diffusion Let's consider a datum Dy of the RHM undergoing masking diffusion. At any time t, the tokens of æ, can have value
Ft, To, Ft [MASK],
if token i has not yet been masked;
(15)
if token i has already been masked.
Therefore, given the noisy observation æs, the prior belief Dy (h!)) = a.) on the value of the token i being equal is given by p( (,), that is:
14 h = = Sa,as
if If = - B
(16)
u (n(0) = = 1/v, Va E v(0) if अτ.; [MASK].
e-process In this process, instead of rumning a forward diffusion process, we act directly on the leaf priors. We introduce noise-to-signal ratio E [0, 1]. which controls the noise level instead of the diffusion time Starting from datum 2p. whose i-th token has value E v(0), the prior beliefs the leaf node taking values in ((0) are defined as
15

---

Published as a conference paper at ICLR 2025
14 Vt
h = (0) = a
= =1-
for Tú,; = a: Va E V(0) \
(17)
= =c/U,
The role e decreasing the prior belief on starting value token. This process can be inter- preted as averaged forward diffusion process, where the average is made over different forward trajectories. In the example masking diffusion (Eq. (16)), calling 1 aa the probability of a token being masked at time the average prior beliefs the leaves read
{ ut (n a) (4 = a)
Ott + L-0e
where T0,i a;
(18)
1-as
Va E 7(0)) \0,
which have the same functional form Eq. (17 by identifying = or- Both and 1 Og vary between 0 and and play the role of noise-to-signe ratio in their respective processes. However, the fluctuations of the upward belief's around their mean in the masking diffuusion change the statisties of the BP messages propagating upwards and make the mapping
Oe inaccurate. For example, in the experimental data of Fig. [ the phase transition in the e-process is located at c* 0.74, while
it is found at 1 or- l' /T ~ 0.3 for masking diffusion.
A.1.3 BP SAMPLING VS BACKWARD DIFFUSION
BP sampling As discussed at the end of section A.I.I BP allows for sampling directly from the posterior probability p (()o) Given a noisy observation 2t and the corresponding marginal probabilities p(h! (E) xz)). the sampling procedes as follows:
root symbol b1th) ÿ. E v(L), is sampled according to the probability p(h (x)); (2)
the corresponding downward message is updated as v4 h = y) 5y.0i
the probabilities of the production rules - (a1, a.) form layer L to layer L are computed as
p (y + 01 .., a b( -)) x us (n(²) = in (n(t-1) a1) ... (n((-1)) ag
(19)
Notice that the upward messages up (n((-2) = a. carry the information on the observa-
tion æ;;
a production rule > (a1, az) is sampled according to the probabilities of Eq.
This gives the values å; (L--1) of the latent nodes h (I-11) The corresponding downward
messages are updated as 1/1 [n.- (n(--11 a òa.ā. the prohabilities of the production rules from layer L - 1 to L - are computed as in Eq. (19)
the sampling procedure continuous up to the visible layer h. giving a leaf configuration En-
The obtained sequence to is a configuration of the RHM sampled from the posterior p(0o (x:)
Backward diffusion with BP The BP sampling above equivalent to running the backward dy- namics with the true score function of the RHM. In fact, given noisy observation æ, time t, marginal probabilities p(h!")=a (xx) at the visible nodes can used to compute the expectation values E(h, (f) (zz), which corresponds to B(bglar,) This expectation gives the score function at æ; at time f, which can be used the backward dynamics to sample I;-1 at time 1, and so on.
Fig. 8 compares BP sampling and the backward diffusion with the exact of masking diffusion. Both the average correlation functions and the dynamical susceptibility at different masking fractions i/T show the same behavior, independently of the sampling procedure.
function in the case
16

---

Published as a conference paper at ICLR 2025
(a)
(b)
109
LANT
1
L-0.00
3.0-
BP samplnng
Baclwarr ditfusion
C(r,t) / C((,,)
2.5
10-1
1.5
10-2
10 1.0- 0.2
10
0.4
0.6
0.8
1.0
++
t/
Figure 8: Comparison between BP sampling and backward diffusion for masking in the Ran- dom Hierarchy Model (RHM), Forward-backw experiments with masking diffusion, where the sampling from the posterior p(,g/ is done with BP sampling (continuous lines) or by running the backward diffusion dynamics (dotted-dashe) lines), using the score function given by BP. Both the average correlation functions of changes (panel (a)) and the dynamical susceptibility (panel (b)) for different masking fractions t/T do not depend on the sampling process. Data for RHM parameters L 8, averaged over 32 starting data and 256 diffusion trajectories per
32, m starting datum.
A.2 MEAN-FIELD THEORY OF THE e-PROCESS
Computation of the marginal probabilities Starting from Eq. (17 and the BP iterative Eqs. (8)
(9) 112 and 13 Sclocchi et al. (2025) computed the average BP messages at each layer L, where the average is performed over the possible choices of the RHM rules. The result consists in the
average messages associated with reconstructing the starting value 7(() of a latent node h,00)
(6) =a)) = Pe- (rr [b. = a qc. Pt h
(20)
where the average (...)o y is performed over the factor nodes & representing the randomly chosen rules of the RHM. The values of pt and gr can be computed layer-by-layer through the following iterative maps:
P++1 = F(p;), 9--1 = G(qe.Pe-1).
(21)
where
pd + f m- (1 - p²)
F(p)
(22)
p¹ + f(1 p²))
-p"
- -p"-1)
G(g,P) q qp"-1 f -ー p
(23)
(v 1)f m-g
and ʃ ma. The initial conditions are given by
Po = 1 1-
(24)
4r = 1/v.
(25)
Notice that the expectation values Pe and qe only depend the layer é and not the specific position of the node inside the layer. Once pe and qe have been computed for every layer & = 0,..., I., the average marginal probability of reconstructing the original value à E v(t) of the variable (0) is given by
P(h ( =ā)
Pede
(26)
(1- (1
Pege
リ-1
17

---

Published as a conference paper at ICLR 2025
This marginal probability is conditioned the initialization of the leaf nodes (Eq. 117 and only depends on the layer L, not on the position of the node inside the layer. Given the initialization of qu. the probability of reconstructing the root node P(h = ~) that is the class of the datum, is given by
P(h = a)= PL.
(27)
Therefore, in the limit of large depth L + oC, the value of pr, is given by one of the fixed of the iterative map F()). When (1) > 1, F(p) has two fixed points: p 1, which is repulsive, and
p 1/e, which is attractive. This implies that, in this regime, for any noise level 0 the leaf nodes, it is impossible to reconstruct the value of the class better than random chance. Instead, when (1( < that is
m U
1,
(28)
F())) appears, which repulsive, while both p and P 1/v are now attractive. This implies the presence of phase transition at specific noise level 1-p_. For < E", the class reconstructed, for e" it is not.
a third non-trivial fixed point p' =
1-1/0"
Computation of the correlation functions Similar to the marginal probabilities, the average cor- relation function can also be computed through an annealed average over the RHM rules. Let's consider two leaf nodes h!") and h2) connected the common ancestor h(d) at layer i through the nodes b (f-1) !) and h2 1)- Given the tree structure, their joint probability distribution can be written as
P(h. (0) .n)
Σ
P (
1b
11
P
h
Σ P
h (1-1)
A P
(29)
In the mean-field approach, the average joint probability only depends on the rree-distance é between i and j and not their precise location. Moreover, we are only interested in the probability that both the starting values of h, h reconstructed, and the probability of only of the two is reconstructed. In the following. we use an overline ... to indicate the starting value of a variable to be reconstructed. We need compute
((h) (0) = ā. h, 10:=0p =d=)=,))))))))))) ),)))n²
(30)
(((h/") az, 11))) az)) a3)) = ,,))),=((p (P((b) # ai h/ -a;))
(31)
where the average (...)o> is done over the possible choices of RHM rules. Using the same strategy
for the computation of the marginal probabilities, we compute the average of each term in Eq. (29 by substituting the BP messages with their averages. For this purpose, we first define the average marginal conditioned on the downward messages at layer É, P(h ā و²|9;
c). with L l.
This is computed with Eq. 26) by iterating the equations 21 between layers 0 and é and using the initial conditions of Eq. 24 and qi c. Therefore, the marginals of Eq. (26) correspond to
((h = allqı- = 1/v). For the marginals in Eq. (2)) we have:
(P h
(0) )r P(h d 1/v),
(32)
that is the average marginal computed in Eqq. (26);
P h a.|h) 0
( ((-1)
(2 1))) (0) - 1),
(33)
P (b(0)
(0) a.ln!
(1-1) + aj
(1
1))
((h a 0).
(34)
18

---

Published as a conference paper at ICLR 2025
The probability terms of the type P(h(0) # .!... are given by 1 - P(h # a ... ). Since these
averages only depend on the layer level é, they are the same for P
hy 1b (8-1) 1)
(0)
The last term
to compute is the joint P [ng (1, bobr-1) (2)
|n
which can be expressed in terms of BP messages:
p P(1f oq, 11- am 1b( (2) = w) x
Σ
6000 az amn.... .,s) (b) = ai) 1 (b// am) II
( = dz). " (h.)
(35)
Computing the averages over the rules, we have:
P (11 18-1) ãi pm (1-1) = T.m 10g = 0)) v
(8)
= př- / Z
2((-1)
(36)
P 11, (8-1) σi, ((-11) & a. 1b/ (8) 81 v
ff P -PE-1) m - 1
THU 1 / L
11
(37)
P (1/
(8-1)
# ãτ, T.i ((-1) + Tm 1b/ (8) -r
3) ) f (1- 12- m-1 1 m- - 1 (1 - -p²-1)
mv-1 /
26-1)
(38)
2(6-1) = 1p-11 +
(39)
1100 - 1
P (n/ 1) ãi, hm
(1-1) a. 1b/ + 1 ) 0,
(40)
P [1g (8-1) = ai, h b 11-1)
+ am 1b
(2) +イ) 1 +
= f p1-1(1 - Pt--1) mi 1 / 7((6-1)
m
(41)
P (n. (1-1) * Tz. b 11 # am 10 + 8) ) =f (1 - 1P-
(0)
m
/ 2 (1
mu- - 1 2
(42)
z z(6-1) =f mv- (1 - 1)
f
(43)
We can combine these terms with the marginals Eq. (32 to obtain P (n((-11),, (((-))),((-1)))
We can
write this probabilities in a 2 x 2 matrix (1Ê-1) such that:
((--)) 1) = (p (1) (6-1) = =a,, (E-11) = T. )mm))
(44)
11
c(f-1) = ch(l-13 = (pl [n/ (1( a. bif 1) # am)) )m))
(45)
cll-1) 1) = -(p (nf(-1)) + Jr, 1(6 # Tm
(46)
Similarly, also the conditional marginals of Eqs. T((-1);
33 and 34
can be written as a 2 x 2 matrix
I (6-1) 1) ( P (n." l/4 (-1) a (111
(47)
((-1) P (1 क. |ng (1-1 1) # मी (11-11
(48)
(i-1) P (0) # a. |bg (-1) a (
22
(49)
T2
(f-1) 1) P (n,0
(0) # a. 1
(1-1) 1) 4 a
(2-1)
(50)
19

---

Published as a conference paper at ICLR 2025
(0) ,b3) finally obtain (0) .h 1) into a x 2 matrix P(h Collecting the values of (P(h)
P(h (0) ( = ( c(t-1) T(E-1)"
(51)
In the language of the spin variables introduced in Section the probability of reconstructing
variable h,!) n is the probability that of +1, while h (0) # T corresponds of =1
A.2.1 DYNAMICAL CORRELATION LENGTII
In the mean-field approach, the average upward belief Pe in the original value of latent variable at layer can be computed through the iterative map
Pr F(pe-1). 1),
(52)
where the functional form of F(p) is reported in Eq. (22) and the initial condition Po depends on + e/v. In the limit large depth L + oo, probability pr. of reconstructing the class is given by the fixed points of F(p). For RHM parameters such that Eq. (8 is satisfied, pL undergoes a phase transition and F(p) has three fixed points: two attractive ones, corresponding to p I/' and p solution of p* F(p") with pa E ( 1). p" corresponds to a critical noise level 1-1/--
noise level as po =
and a repulsive one, corresponding to the non-trivial
In the vicinity of Ex and the limit L + oc, we can estimate the typical distance over which token changes are correlated by computing the number of layers i after which the upward probability of reconstructing the latent variables pj approaches one of the two trivial fixed points p 1 and p = 1/v. This corresponds to the number of layers required to escape the repulsive fixed point p".
Given the iterative map of Eq. 52 layers,
can linearize it around the fixed point p" and iterate for &
dF(p) dp
Ap: =
Apo.
(53)
where Ap; = Pe- Pe-p". We have that dFip)
> 1 and we use the shorthand notation F
d.F(p)
dp
p'
dp
We want to compute the depth i at which E Apol = O terms of the corruption noise e, we have F | (1), where A = 6 6* Hence, ? ~ log le c/ log FV. From the depth ? we can compute the correlation length in input space
with log
{ - 6--1-1-
(54)
log F!
that diverges at the critical point: lime E 400.
B GAUSSIAN RANDOM FIELD MODEL
Consider E [-1,1] Let (rw) denote centered Gaussian random field defined over this domain with translational -ntilatiiiinn-iiiiaaattt isotropic covariance function K (u, w'). Specifically, the field satisfies [[x(u)] and [[x(u)<< (u=)) K(u, u') = c(Ilu u'l)), where is a function depending only on the Fuclidean distance 1|u u' |||
Assume that the Fourier coefficients C(k) of c(Ilu u' w'll) satisfy, for large ||]]]. C(k) ~| ([[{&][-9) || | + co, with 0<a<<d. This implies that the Fourier coefficients X(k) are independent Gaussian random variables, X ~ *N(00 with of x ||
B.1 BRRWARD-BACKWANK EXPERIMENTS IN FOURIER SPACE
Given the independence of the Fourier coefficients X(k), we apply the diffusion dynamics to each Fourier coefficient independently. The noising process given by:
X(k); /1 (,) v BBn 1 7~ N0.00 1),
(55)
20

---

Published as a conference paper at ICLR 2025
10
10f
10a
107
C(r,
10-
10a
10-1
3 C(r, c)
10
10
102
10'
c-0.60
c-0.74
c-0.64
c-0.75
10
=00.6
e00.76
=00.8
c=..78
10-1
=00.0
c=0.80
c00.2
c0090
c=0.73
10-2
10
10
10
10
10
10
r /
Figure 9: e-process in the RHM (v = 32, m = 8, = 2, L 9): correlation function with respect the token distance r, for noise levels close the transition e* 0.74. (Inset) The correlation function displays system-spanning power-law decay at the transition e* = 0.74, while it decays faster for noise values e * E". The length scale which departs from the critical behaviour defines the correlation length & (Main) Rescaling the distance with & given by Eq. (54) and C'r,, e) with 5", a = the different correlation functions collapse on a single curve. This implies that the power-law scaling { -dc- of Eq. (54) describes well the peaking of the correlation length around the class transition. For this choice of RHM parameters, V 1.78. The exponent a is obtained by fitting the critical decay C(r, e*) r from the data.
(probability of reconstructing a node)
1.0
layer
layer
layer
layer
layer 8
layer 2
0.8
layer
layer
layer 6
layer
layer
0.6
0.4
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
masking fraction t t/T
Figure 10: Masking diffusion in the RHM: probability of reconstructing (latent) node as function of the inversion time This is proportional to the masking fraction t/T. The probability is averaged over the nodes at given layer. The probability of reconstructing leaf node (layer 0) decreases smoothly with the inversion time, while the probability of reconstructing the root node (layer 10), that is the datum class, undergoes sharper decay from 1 to 1/v at critical time t 0.2 = 0.3 T. This sharp decay is expected to become a step-like transition in the limit of infinite depth L, co. Data for RHM parameters diffusion trajectories per 10 starting data Zg.
32, m 8, 2, I 10, averaged 10
21

---

Published as a conference paper at ICLR 2025
fort 1.2...., where 3g (0, are the diffusion coefficients and 77 are independent standard
Gaussian variables.
By unrolling the recursion, the forward dynamics can be expressed
{(k); - Va,X(()) + v1 - -p 1 ~ ~((,1)
(56)
where IT= (1 Br).
We then reverse the process at time i, following the backward dynamies:
X(K))-1= = (x()), + Be Vx() log (X))))) + V =~ ~~ 1),
(57)
where (K):)) marginal probability density
X(k)) in the forward process and
Vx(1) log (K)))) is the corresponding score function.
Given the forward process, q( (X(())) is Gaussian and the score function can be computed explicitly:
X(k),
V (x) log (((()))) = 0.00 +
(58)
B.2 MODE RETRIEVAL
Our goal is to determine which Fourier coefficients are retrieved after the reverse process. Specif- ically, we want to compute the modes & for which the distance between the coefficient obtained at the end of the backward process ((k, t)o pk-[)(())) with the starting coefficient X X(k)o small:
[kk, t)o - X(k)ol <
(59)
Thus, consider the signal-to-noise ratio (SNR) for each mode
SNR(K,
K
(60)
a2
where x = |
Define the critical wavevector magnitude x* where SNR(k*, ()
1) 11/0
(61)
Modes with x < R² (low-frequency modes) have SNR > and can be retrieved, while modes with s² (high-frequency modes) have SNR are dominated by the noise in the forward dynamics and cannot be reconstructed.
B.3 CORRELATION ANALYSIS
We seek to compute the correlation of the changes after reverting the process at time t. Let au, t) denote the field obtained after reverting the diffusion process at time I, position u. In particular, ar.00) 0) denotes the starting random field. Define the difference field 2(u, 1) æ(u, L) - æ(u, 0).
Since the two fields Gaussian, also 2 t) is Gaussian.
We are interested in the following spatial correlation function:
C(r, t) E[z(u, xx (0,,
(62))
where r = ||u]]. Using Wick's theorem, we have
C(r, t) = E[z(u, (v, 1)) (0, ()= () + 2E[z(,, ()=(0, z)]²
(63)
The first term constant independent of r, while the second term captures the spatial dependence. To compute [[ (0,
t)]. we express =u, t) in terms of its Fourier coefficients Z(k, t). For modes with k k (t), can assume Z(k: t) ss O. For modes with k K (t), İ(k, t)o is approximately independent of X(k)o- Thus, Z(k, t) for k > x² (t) is a Gaussian random variable with zero mean and variance 20?
22

---

Published as a conference paper at ICLR 2025
(a)
(b)
10a
10
1-03 1
11820 Xibhll
1-0.1 T
1-0.2
C(r)/C(0)
10
1-04
(3
1-
0
1-0.5
10
10-1
1-066
1-107 T
1071
1014
10
1-08
1-09
10-3
10-3
10-1
10
10a
10a
10P
10
102
1//10
(c)
1.0
0.4
0.2
0.0
0.2
0.1
0.6
0.8 10
t/T
Figure 11: Gaussian random field model. (a) Relative modal errors as function wave-vector magnitude kk). For kk| > π², errors remain large, indicating unsuccessful retrieval of the Fourier coefficients, while kk| < k", the emrors decrease, signifying successful recovery. (b) Spatial correlation function C(r, I). showing power law decay at short distances and cutoff at long dis- tances. The correlation length increases with inversion time (c) The susceptibility x(t) increases monotonically and reaches its maximum at the inversion time t T.
Thus, the covariance of is
B[z(u, ()(0,,)
/
T " 22fod
(64)
Substituting of ||||| have:
B(z(0,()2(0,1)
(AADSw ek "2[=211 -dtk.
(65)
To evaluate the integral, we consider the asymptotic behavior for different regimes of r. At short distances r & 1/x*, the integral over is dominated by large and behaves E[z(u, f)2 t)] x ra-d where C₁ a constant. At long distances r > 1/k= (t), the lower limit x* (t) introduces an effective cutoff and the covariance decays faster than any power law.
Therefore, the correlation function C(r, t) exhibits algebraic decay with exponent 2(a d) for r << 1/x* and faster than any power law for 1/k".
B.4 DISCUSSION
For the Gaussian random field model, the correlation length & 1/x²(() is monotonically increas- ing function of the inversion time t, or noise-to-signal ratio (NSR). As result, the susceptibility x(t) calculated by integrating the correlation function space also increases monotonically and
23

---

Published as a conference paper at ICLR 2025
reaches its maximum the inversion time T, where the NSR This behavior contrasts sharply with the hierarchical data studied here, where a phase transition occurs at finite time/NSR. As discussed in the main text, this divergence arises due to the geometry of correlations induced by the hierarchical tree structure, which absent the Gaussian random field model.
B.5 NUMERICAL EXPERIMENTS
In Figure 11 (a), we plot the relative modal errors & o ( - ( For |||]| > k², the emrors remain (1), indicating that the coefficients are not retrieved, predicted by our analysis. Conversely, for | > K", the errors decay, indicating successful recovery of the coefficients. In panel (b). present the correlations C(r, t), which exhibit power law decay followed by cutoff. Notably, the correlation length increases monotonically with the inversion time t. Finally, in panel (c), plot the susceptibility (t), which reaches its maximum at T.
C LANGUAGE DIFFUSION
C.I SETUP
Here, we briefly describe the particular realization of discrete diffusion used in the MDLM setting, which is detailed in (Sahoo et al., 2024).
MDLMs are form of discrete diffusion model tailored for language generation. Unlike autore- gressive (AR) models, MDLMs generate text by gradually unmasking tokens, allowing for non- sequential generation. This process governed by a forward masking and reverse unmasking pro- cess, parameterized using a Rao-Blackwellitn objective to improve performance.
Forward Process:
The forward process is defined by progressively noising clean input sequence using categorical distribution:
(=+/a>) = Cat(2e;004 + (1 )m)),)
(66)
where is the latent variable at time f. representing the noisy version of the input sequence, z is the original, clean sequence of tokens, Cat(:;)) :) is categorical distribution over the possible states, Ot is the noise schedule function, strictly decreasing from 1 to 0 as / increases, and m is a one-hot vector representing the special masked token. At each time step, a fraction of the data transitions into the masked state.
Reverse Process and Rao- Pro-Blackwellizattinn nal data from noisy observations. It is parameterized using a neural network approximation aa t), which predicts clean tokens from noisy inputs:
The reverse diffusion process reconstructs the origi-
Cat(2aj Zt),
if 2t + m,
po (0(22)2 24)
(1-a, (1 (a..a))
(67)
Cat Exi
if 2t = m.
1-0:
where 2, is the latent variable at a prior time step (with s t), xo( t) is neural network approximation of x given the noisy observation at time t, and po(-l-) is the model distribution approximating the true reverse process.
The training objective is negative evidence lower bound (NELBO), expressed as:
T
Laiftusion Σ Eg 1 (((())
(u(is) ax(1))
log (2(()) z²)
(68)
where T' is the number of diffusion steps, a(e))) ax(s) is the noise schedules evaluated at time steps t(i and s(i), respectively, Eg is the expectation over the forward process defined by g, and (ro((e(6)) x)) the dot product between the neural network output zo(2((e) and the original input
24

---

Published as a conference paper at ICLR 2025
Continuous-Time Time Likelihood Bounds: To achieve tighter approximation to the ELBO, the dis- crete objective is extended to continuous time as:
/ at (0) dt. NELLBO E.g Jo at
(69)
where of is the time derivative of the noise schedule 0Ą- The integral evaluates the objective over continuous time, providing tighter bound the likelihood. This formulation is invariant to the specific functional form of the noise schedule az, highlighting the robustness of the MDLM ap- proach.
Connection to Masked Language Models: MDLMs leverage a masked diffusion approach where the training objective weighted average of classical masked language modeling (MLM) losses:
LONNLBB Egg ['
a/
Σ log(<<((e)) dt,
(70)
1 04
where xf: The ě-th token in the original sequence, (z)): The neural network's prediction for the ê-th token given the noisy sequence 2,- The summation runs over all tokens in the sequence, effectively establishing connection between MDLMs and BERT-style encoders while equipping them with generative capabilities.
We employ the MDLM proposed in (Sahoo et al. 2024) to conduct the forward-backward ex- periments described in Section 4 by first drawing random texts of fixed token length from the WikiText2 database, masking fixed fraction of the tokens t, and then performing the backward diffusion process by using the masked sequence as the initial point for the MDLM model.
C.2 EXAMPLES TEXT SAMPLES FOR THE FORWARD- FORWARD-BACKWARR EXPERIMENTS
Below, we provide examples of texts generated by the forward-backward process using MDLM seeded from WikiText2 examples for different masking fractions. Selected samples were shown in the main text in Fig. (a). We dub the text results after the forward-back samples. As can be seen by the color coding, correlated blocks of words change together along the denoising process, as described in Section 3] and the semantic meaning of the paragraphs themselves change along the phase transition. In blue we denote masked tokens that have changed their value after the backward process, while in green masked tokens that have returned to their initial value. Red indicates the changes in the final texts. It can be seen that for small masking fractions such as t/T 0.1, most of the tokens do not change after masking, while the amount of changed tokens far exceeds the unchanged ones near the phase transition at t/T = 0.5, hinting at the long-range range correlations emerging.
process as U-turn
25

---

Published as a conference paper at ICLR 2025
Masking fraction
Highlighted Original Text:
The third day, September 3, the situation worsered. The weather hot and ammunition, food and supplies were nearly completely exhausted Since the previous afterroon, North Korean mortar barrages had alternated with infantry assaults against the perimeter. Survivors later estimated there were about twenty separate infantry attacks repulsed. Two North Korean
machine guns still swept the perimeter whenever anyone showed himself
Dead and dying us troopa were almost every fox hole, Mortar fragments destroyed the radio and this ended all communication with other US units. Artillery fire and air strikes requested by Schmitt never came. North Koreans worked their way close to the perimeter and threx grenades
Highlighted U-Tur Text:
information maps of the actual burial population size. number probably around 30, 000, population there the walls, it is estimated there were at around 30, 000 and ancther holding room for perhaps 10,000 It also seems highly unlikely, as with Dead Drop s tes generally, that the only eviderce for the storage of the firearm from the drop was more wood pieces. The other medieval site which requized constant fire and perhaps continual storage is the firearm, one of which we were aware of having been stored during the same time period
almost completely encroached into the to 100 barr is excavated the site against
Masking fraction 0.7
Highlighted Original Text:
The third day, September the situation worseced. The weather hot and ammunition, Food and suppl ies were nearly completely exhausted Since the previous afternoon, North Korean mortar barrages had alternated with infantry assaults against the perimeter. Survivors later estimated there were about twenty separate infantry attacks repulsed. Two North Korean machine guns atill swept the perimeter whenever anyone showed himself.
Dead and dying US troops were in almost every fox hole, Mortar fragments destroyed the radio and this ended all communication with other US units. Artillery fire and air strikes requested by Schmitt never came. Some North Koreans worked their way close to the perimeter and threw grenades
Highlighted U-Tum Text:
increased. On September 3, the situation was under control, Despite tons of ammunition air train orders were almost completely violated. On the previcus day, North Americans, farm crews and miners were heard rebelling against the perimeter. Survivors were estimated to be about twenty dead from attacks convulsing and starvation, as machine guns still awept the perimeter whenever ever they could. Dead end troops were almost all general effects, crying out for particular strikes
every fox hole for about twenty minutes; the radio and newapapera frequently with or the loading of vehicles. Some North Americans reported bl blocking way to fill the perineter, and others
26

---

Published as a conference paper at ICLR 2025
Masking fraction
Highlighted Original Text:
The third day, September 3, the situation worsered. The weather was hot and ammunition, food and supplies ies were nearly completely exhausted, Since the previous afternoon, North Korean mortar barrages had alternated with infantry assaults against the perimeter. Survivors later estimated there were about twenty separate infantry attacks zepulsed. Two North Korean machine guns still swept the perimeter whenever anyone showed himself.
dying US troops were almost every fox hole. Mortar fragments deatrayed the zadio and this ended all communication with other uS units. Artillery fire and air strikes requested by Schmitt never
Some North Koreans worked their way close to the perimeter and threx grenades
Highlighted U-Turn Text:
The next morning, March 3, the situation changed. The border was secure, ammunition, food and everybody were nearly completely met. On the previous afternoon, North Korean artillery barrister repulseated within the perimeter. Survivors later said there were about twenty separate infantry attacks repulseated. Two North Korean nachine gans shells had the ground where anyone showed himself. Dead and wounded US troops were in wounded positions. eliminated any communication of communication with other US troops.
infantry attack
the time, fragments of mortar shells
Exceptional fire and submunitions by Schmitt never came. The North Koreans worked their way up to the ground and threw bottles
27

---

Published as a conference paper at ICLR 2025
Masking fraction 0.3
Highlighted Original Text:
The thi rd day, September 3, the si situation worsered. The weather was hot and ammunition, food and supplies were nearly completely exhausted. since the previous afternoon, North Korean mortar barrages had alternated with infantry assaults against the perimeter. Survi vors later estimated there about twenty separate infantry attacks zepulsed. machine guns still swept the perimeter whenever anyone showed himself.
North Korean
Dead and dying US troops were in almost every fox hole. Mortar fragments destroyed the radio and this ended all communication with other uS units. Artillery fire and air strike kes requested by Schmitt never came. Some North Koreans worked their way close to the perimeter and threw grenades
Highlighted U-Tum Text:
third! the 3rd the situation worsened. The perimeter was thick and nearly completely exhausted. By the late
ammunition, food and fuel afternoon, North Korean mortar barrages still cooperated with infantry assaulta against the perimeter for, later hours there were about 10 separate infantry attacks repulsed. Two North Korean machine guns still swept the perimeter without anyone but himself. Dead and dying uS troops were in practically every man hole. Mortar fragments destroyed all radio and this ended al1 comrunication with other us units. Artillery fire or air support requested by Schmitt still came, Some North Koreans worked to bring them to the perimeter. The whites
Masking fraction 0.1
Highlighted Original Text:
The third day, September 3, the si situation worsered. The weather was hot and ammunition, food and supplies were nearly completely exhausted. Since the previous afterroon, North Korean morcar barrages had alternated with infantry assaults against the perimete:: Survivors later estirated there were about twenty separate infantry attacks zepulsed. Two North Korean machine guns atill swept the perimeter whenever anyone showed himself.
Dead and dying US troops were in almost every fox hole, Mortar fragments destroyed the radio and this ended all communication with other US units. Artillery fire and air strikes requested by Schmitt never came. Some North Koreans worked their way close to the perimeter and threw grenades
Highlighted U-Tum Text:
The third day, September 3, the situation worsened. The weather was hot and ammunition, tanks and supplies were nearly completely exhausted. Since the early afternoon, North Korean artillery barrages had alternated with infantry assaults against the perimeter. Survivors later estinated there were about twenty separate infantry attacks zepulsed. Two North Korean machine guns still swept the perimeter whenever anyone showed himself,
dying US troops were almost every fox hole. Mortar fragments
destroyed the radio and this ended all communication with other us units. Artillery fire and air strikes requested by Schmitt never stopped. Some North Koreans worked their way clese to the perimeter and threw grenades
D IMAGE DIFFUSION
For image diffusion, we use the publicly available models from Improved Denoising Diffusion Probabilistic Models (Nichol & Dhariwal 2021). trained on the ImageNet dataset at resolution 256 256. We use the class-unconditional model to ensure class phase transition at an inter- mediate diffusion time. To tokenize the images in a semantically meaningful manner, we use the last-layer embeddings from a CLIP ViT-B32 (Radford et al.) (02T) encoder. This procedure crops the images to the size 224 224, which get tokenized in 7 x patches, each of dimension 32 32. The embeddings at the last layer of the CLIP encoder have dimension 768.
In Fig. 12]
we provide some examples of images generated with the red, we highlight the patches whose CLIP embeddings show a statistically significant change with respect to the starting image (f = 0), In Fig. 13 we evaluate convolutional classifier on the gener- ated images and the starting ones to detect the inversion time corresponding to the class transition.
protocol. In
28

---

Published as a conference paper at ICLR 2025
-
t= 0.6.77 T
t 0.7
10
Figure 12: Examples of images generated different inversion times The grid indicates the tokens represented inside the CLIP vision encoder. For inversion time t > 0, the red patches indicate the token embeddings that have a variation magnitude larger than fixed threshold. These patches of variation appear in domains of growing size.
29

---

Published as a conference paper at ICLR 2025
Similarity of the logits of xo and those of (t)
1.00
cosine similarity
0.75
0.50
0.25
0.00
0.00
0.25
0.50 t/T
0.75
1.00
Figure 13: Class transition in the borward-backward diffusion for ImageNet images. Cosine similarity between the logits of convolutional classifier computed the starting images and on the generated images (c) at different inversion times The logits are standardized on the statistics of the ImageNet validation set and the cosine similarities are averaged over 10k starting images. The convolutional classifier is ConvNeXt Base architecture (Liu et al. 2022) pre-trained on ImageNet- Ik and achieving 96.9% top-5 generalization accuracy. At short inversion times, the similarity is close to one, implying that Xy and (t(t) are images of the same class. At inversion time around t 0.6T, the similarity has sharp drop, corresponding to the class transition. Correspondingly, the susceptibility measure in Fig. (b)bb has a peak.
30


Reviews:
[{"review_id": "tcYvMFpF6C", "reviewer": "Reviewer_7ZQW", "summary": "The paper examines the hierarchical correlation structures among input tokens using a dynamic correlation function and dynamical susceptibility within a forward-backward experimental framework. These variables reveal how two input tokens respond to perturbations when attempting to recover data from noisy inputs. Analyzing diffusion and language models, the study demonstrates an anticipated correlation aligned with spatial structures.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "(1) The paper introduces novel approaches for analyzing the structure of inputs using pretrained diffusion and language models.\n\n(2) The authors offer a thorough analysis and derivation, with experimental results closely aligning with theoretical expectations.\n\n(3) Multiple schematic diagrams and data visualizations are included, providing valuable insights into the methods.", "weaknesses": "(1) The paper’s presentation could be improved. While there are numerous figures to aid understanding, the main text is somewhat challenging to follow.\n\n(2) Why is the σ in Equation 3 binary? Wouldn’t a continuous measurement be more appropriate? For instance, a small difference in pixel values might not alter the semantic structure of the images, but it would be captured by binary measurement.\n\n(3) Shouldn’t the spatial correlation structures be content-dependent? For example, if the bird and the laptop in Figure 5 were moved slightly farther from the camera, would this change affect the result shown in Figure 2?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DqKq4YiiuS", "reviewer": "Reviewer_ohKX", "summary": "This paper aims to understand diffusion models through a hierarchical latent variable model. Through this framework, this paper demonstrates the connection between the noise level and the hierarchical levels, as evidenced by a transition phrase. This paper builds on the tools from physics and illustrate their theoretical model with empirical results on practical models.", "questions": "Please refer to the weaknesses section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The hierarchical perspective provides novel insights into the diffusion model's mechanism and the application of physics is also refreshing. I feel that the community can benefit from these insights, which may give rise to empirical advancements.\n2. The paper is well written and clearly communicates the main ideas.\n3. The experiments on natural data (image/text) support the theoretical claims.", "weaknesses": "1. It'd be great to see attempts at utilizing the theoretical/empirical observations to advance practical model design. Some discussions along this direction would also be appreciated.\n2. The tree model seems overly simplified for real-world data like images and languages. For example, one would imagine two high-level variables could become co-parents for some low-level variables, thus breaking the tree structure. I would appreciate a discussion on this limitation and the applicability of the theoretical framework to more general latent models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mYg8W8aEzk", "reviewer": "Reviewer_s11H", "summary": "In this paper, the authors examine the hierarchical structure in high-dimensional data by conducting forward-backward experiments within diffusion-based models. They employ a Random Hierarchy Model (RHM) for the data where the tokens of data are generated from a tree structure of latent, they also use Belief Propagation (BP) as the score function to denoise samples.\n\nThe authors focus on the phase transition of the average belief $p_L$ of the RHM's root node by analyzing an iterative mapping (Equation 7) and identifying a critical noise level $\\epsilon^*$ at which the transition occurs. Based on that, they also compute the minimum layers $\\tilde {l}$ needed for the transition, beyond which $p_l$ would collapse to trivial fixed points $\\{1/v,1\\}$, indicating either a complete reconstruction or randomization of upper latent variables. At this specific noise level, BP can modify the deepest latent layer $\\tilde {l}$, yielding the maximum correlation length (i.e. big \"chunks\" of data token), which is the distance over which token changes remain correlated.\n\nTo characterize this effect, the authors introduce **dynamical susceptibility** which exhibits a first increase then decrease curve as expected. They further demonstrate that the dynamical susceptibility curve has the same trend for forward-backward experiments with diffusion models and synthetic RHM experiments.", "questions": "1. From the analysis, BP denoising appears to be a one-step method that directly samples $\\hat{x_0}$ from the noisy observation $x_t$, differing from typical diffusion denoising that iteratively samples $x_{t-1}$ from $x_t$ throughout the process. Does this discrepancy exist, or are the authors also using a denoising schedule similar to real diffusion models?\n\n2. Can we interpret the maximal correlated length achieved at an intermediate noise level (time step) as the model generating class information or lower-level features? If so, this would contrast with existing observations that diffusion processes follow a coarse-to-fine generation pattern (e.g., https://arxiv.org/abs/2303.02490), where lower-level features are generated at the beginning, not in the middle.\n\n3. Figure 4(a) is somewhat unclear. Combined with (c), it seems the authors are suggesting that the largest correlated changing chunk appears at a masking fraction $t/T \\in [0.5, 0.7]$. However, this is not immediately evident from (a) alone.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The authors aim to capture hidden hierarchical structures within discrete data using the RHM model, with their RHM+BP framework supporting both discrete and continuous diffusion processes.\n\n2. By applying BP for denoising, the authors rigorously analyze phase transitions in the denoising results and identify the critical noise level needed to induce a change in the data class (or low-level feature).", "weaknesses": "1. The paper is somewhat disorganized and hard to follow, as definitions, derivations, and experimental results are heavily interwoven. To improve clarity, consider using theorems or structured definitions to better organize the content (e.g. by moving some derivations, such as Equations 8 and 9 to appendix and summarizing them as a main theorem).\n\n2. In practice, people use real data + score-based denoising; however, the authors use RHM data + BP denoising instead. This discrepancy is insufficiently justified, making the claim that real-world data shares the same hierarchy as RHM unconvincing. While the authors show a similar phase transition phenomenon between the RHM case and real-world diffusion case, they do not rigorously establish a connection between them. Verification by testing real-world diffusion on RHM data may strengthen this claim.\n\n3. The results are somewhat vague and lack practical insights, as it appears that neither the RHM setup nor the forward-backward experiment has direct practical applications. Although the authors mention interpreting the \"chunks\" that emerge during the forward-backward experiments, they do not provide further discussion or related work on that.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gz7qAbqjWW", "reviewer": "Reviewer_WL6E", "summary": "This paper suggests that forward-backward diffusion experiments can be helpful in uncovering hierachical structure in data. They first study a synthetic Random Hierarchical Model and show that a peak of the dynamical susceptibility (related to correlations between blocks of tokens) occurs at a noise level where a phase transition is known to occur in the RHM (i.e. the latent class at the root changes). They then show peaks in the susceptibility in text and image experiments.", "questions": "L57: Does such a divergence definitely indicate a hierarchical structure or are there other ways/reasons divergence could occur? i.e. is this divergence a “proof” of (or very strong evidence for) hierarchy?\n\nL210: Clarification: so, the epsilon-process is itself a mean-field approximation of the discrete diffusion process, but then you use another mean-field on top of that to compute the correlation?\n\nL356: Can you elaborate on why a susceptibility peak is a ‘smoking gun’ for hierarchy? Just because one nonhierarchical example doesn’t have a susceptibility peak doesn’t mean there might not be others that do?\n\nL511: How (or does) this relate to the diffusion-as-spectral-autoregression point of view? Also there is a typo, 'trough'.\n\nGeneral: \n\nDoes the susceptibility divergence tell us anything about how many levels of hierarchy are likely present? Or just that there is at least one level?\n\nThe RHM is discrete, and discrete vs continuous diffusion are rather different; can you justify why RHM should be a good model for continuous data/diffusion as well?\n\nDo the MDLM and ImageNet expts actually confirm that a phase transition occurs? Or do we just observe the susceptibility peak and infer a phase transition by analogy to RHM? In particular, it seems that for ImageNet it might actually be possible to run a classifier to determine whether the class changed.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is clearly written and the RHM model is nicely studied. The text and image experiments are well-designed (although I still have some questions, below, about how well the conclusions from RHM transfer to real data). I appreciate the application of ideas from Physics to ML problems.", "weaknesses": "Please see Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)