NOTE-685: A Phase Transition in Diffusion Models

Contribution

A reason, in a solvable model, why noising a datum and denoising it back changes its class abruptly at some noise level while keeping many of its low-level parts. For hierarchical data generated by a random grammar, the optimal denoiser is belief propagation on the generating tree, and the paper shows (by an annealed mean-field calculation, confirmed numerically) that the reconstruction of the root has a phase transition in the noise in the large-depth limit when the grammar is sparse, whereas the reconstruction of leaves is smooth. It then quantifies the corresponding effect for a real diffusion model on ImageNet through the hidden layers of pretrained classifiers, and contrasts it with a two-mode Gaussian mixture, which has a class transition but no hierarchy.

Key insight

In a sparse grammar most strings are not grammatical, so an error at a low level is detectable and correctable from its neighbours: whether the evidence about the class grows or shrinks on the way up the tree is decided by one number, s f (branching times the fraction of tuples in use). Below a critical noise the evidence is amplified at each level and the class survives; above it the evidence decays at each level, and over many levels it reaches chance. The leaves need no such amplification, so they degrade gradually. Class and parts therefore come apart in noise: the whole is lost all at once, the parts one by one.

Assumptions

• Data. The RHM of LIT-877, with v classes, every level’s vocabulary of size v, branching s, depth L, d = s^L leaves, and m rules per symbol drawn uniformly without replacement from the v^s tuples, no tuple shared between parents. Main text: f = m/v^(s−1); SI uses f = (mv − 1)/(v^s − 1), the same to leading order.
• Known rules, uniform prior. The denoiser knows the grammar and has a uniform prior over classes (unconditional diffusion). It is the Bayes posterior, i.e. a diffusion model with perfect generalisation, which the authors call “a strong assumption”.
• Noise. Either Gaussian diffusion of each one-hot leaf in ℝ^v, whose posterior per leaf is a softmax of x(t)·√α_t/(1 − α_t) (Eq. 4, SI 1), or the simplified ε-process: belief 1 − ε on the true symbol, ε uniform (Eq. 6). The two are connected empirically through an effective ε(t) (SI 3, Fig. S7).
• Annealed mean field. Messages are replaced by their average over realisations of the rules; correlations between messages and the fluctuations of the random rules are neglected, and the downward pass substitutes average upward messages (Eq. 54).
• Large depth. The transition is a statement about L → ∞; at finite L it is a crossover that sharpens with L (Fig. 5, S4).

Key results

• Eq. 4 / SI Eq. 12. p(x_i(0) = e_γ | x_i(t)) = exp(x_{i,γ}(t)/Δ_t)/Z, Δ_t = (1 − α_t)/√α_t: leaf initialisation for BP.
• Eqs. 5, 13–16. BP upward and downward updates over factor nodes ψ(y, x_1, …, x_s) = 1 iff y → (x_1, …, x_s) is a rule.
• Fig. 5. Exact BP, v = 32, m = 8, s = 2, L = 10, versus diffusion time: the class’s probability of being unchanged drops sharply at a characteristic t; lower levels decline smoothly.
• Eq. 8 / SI Eqs. 35–38. Annealed upward map F(p) = (p^s + f (m−1)/(mv−1)(1 − p^s)) / (p^s + f(1 − p^s)), with p = 1 − ε + ε/v. Fixed points p = 1 and p = 1/v.
• SI Eqs. 39–42. F′(1) = f s m(v−1)/(mv−1), so p = 1 is attractive iff s f < 1 + (1 − 1/m)/(v − 1), i.e. s f < 1 + O(1/v). Then a repulsive fixed point p* in (1/v, 1) appears and the class is recoverable iff ε < ε*(s f); for s f > 1 only p = 1/v attracts and the class is never recoverable at depth. Holds in: annealed approximation, L → ∞.
• Fig. 6 / S2. Phase diagram in (s f, ε) from upward BP on one realisation (v = 32, s = 2, L = 10) agrees with ε* from the map. “Inference” there means the class’s probability exceeds the leaves’ initial belief.
• Eqs. 54–59, Fig. 7a, S4–S6. Combining upward and downward maps gives per-level marginals p^(ℓ); they match exact BP for leaves and class, and the curves for top and bottom levels cross at the transition. Downward messages fluctuate strongly at small ε (synonyms leave a child underdetermined by its parent).
• Fig. 2, S8. Unconditional ImageNet DDPM (Dhariwal and Nichol, T = 1000): cosine similarity of standardised ConvNeXt-Base activations, original versus forward–backward sample, drops sharply for the logits near t ≈ T/2 while early layers decline smoothly, and the layer curves invert around the drop; ResNet-50, Wide ResNet-50 and ResNet-152 agree.
• Fig. 7b. A 7-layer CNN trained to 99.2% on an RHM (L = 7, s = 2, v = 16, m = 4; s f = 0.5) with BP-sampled reconstructions shows the same inversion versus ε.
• SI 5, Fig. S9. A two-mode Gaussian mixture in d = 1024 with exact score: the classifier’s logits drop at t ≈ 0.6 T, but hidden layers move with the logits; no inversion.

Claims

id	claim	strength	support
C1	Bayes-optimal denoising of RHM data with known rules is exact BP on the tree	strong	construction (tree factor graph)
C2	In the annealed approximation, class reconstruction has a sharp transition at ε*(s f) as L → ∞ when s f < 1 (+O(1/v)), and fails at any noise when s f > 1	strong for the map, moderate for the RHM	SI Eqs. 38–42 (exact for the map); the map’s fidelity to quenched BP is numerical
C3	Low-level features are reconstructed smoothly in ε, so they persist past the class transition and the level curves cross	moderate	Figs. 5, 7a, S6; one parameter set
C4	The ε-process approximates Gaussian diffusion of the leaves	weak–moderate	Fig. S7, qualitative agreement through an effective ε(t)
C5	Forward–backward diffusion on ImageNet changes class abruptly near t ≈ T/2 while preserving low-level features	moderate	Figs. 2, S8; one DDPM, classifier activations as proxy
C6	The layer-curve inversion is specific to hierarchical, compositional data and absent for a bimodal Gaussian mixture	weak	one mixture (SI 5) against one RHM and ImageNet
C7	What a trained diffusion model does on images is what BP does on the RHM	not supported here	analogy of curve shapes; U-Net as BP is left to future work and to Mei (2024)

Method

Exact belief propagation on the RHM’s factor tree, run numerically on single draws of the rules from leaf beliefs set either by Gaussian diffusion or by the ε-process; then an annealed average of one BP step over rule draws (multivariate hypergeometric counts of tuples at each Hamming distance from the true one), iterated level by level as a scalar map whose fixed points give the phase diagram. Empirically, the forward–backward protocol of Ho et al. on ImageNet, measured through the standardised activations of pretrained classifiers at every depth.

Concepts

• forward–backward experiment — noise a datum to time t by the forward process, then sample the reverse process from there; compare the result with the original.
• f — the fraction of the v^s possible s-tuples a level’s rules use; f = 1 makes every string grammatical.
• ε-process — leaf beliefs 1 − ε on the true symbol and ε uniform over the alphabet; a stand-in for Gaussian noise.
• phase transition — here, the change at ε* in the L → ∞ fixed point of the annealed map, between a phase where the class is recoverable and one where it is at chance.
• inversion — the crossing, at the transition, of the “unchanged” curves of top and bottom levels (or of logits and early layers).

Connections

It applies LIT-877’s grammar to generative modelling. Ho et al. introduced the forward–backward protocol and the remark this paper half-contradicts. Biroli and Mézard’s and Raya and Ambrogioni’s speciation or symmetry-breaking times for mixtures are the nearest theory; SI 5 is the paper’s case that they miss the hierarchy. The phase transition is a tree reconstruction problem in the sense of Mossel (cited for BP), with an annealed criterion: stability of the perfectly informed fixed point, which is my reading of Eq. 40, not a bound the paper proves. Mei’s “U-Nets as belief propagation” (arXiv:2404.18444) is cited as the follow-up showing U-Nets can approximate the BP denoiser. Kadkhodaie et al.’s multiscale wavelet models are the other hierarchical account of images it cites, and it notes that their graph of latents is not tree-like.

Bearing on the record

• THEORY-195. Complementary, not overlapping: same grammar, different quantity. THEORY-195 counts the examples needed to learn the grammar; this paper assumes the grammar known and asks how much of a noised datum an ideal denoiser can restore. One difference worth recording: the phase transition needs a sparse grammar (s f < 1), while LIT-877’s experiments range up to the maximal case (m = v^(s−1), f = 1, which it uses to argue that the data lie on no low-dimensional manifold), where every string is grammatical and this paper predicts the class is lost at any noise for deep trees. The two papers use the model in different regimes, and results from one should not be carried to the other without checking f.
• THEORY-186. Both show hierarchy as levels that behave differently, but THEORY-186’s stages are in training time and coarse to fine; here the levels separate in noise, and the coarsest (the class) is the one with the sharp change. No conflict.
• QUESTION-025. No bearing: constituency hierarchy, no co-occurrence matrix, embedding directions or concept lattice.
• New account. THEORY-199, Proposed: the class-reconstruction threshold and its sparsity condition, stated for the model only.
• Practice. The paper gives no instruction; its subject is diffusion models and the structure of image data, which the anthology’s generative-modeling and signal-structure topics hold, hence the flag on the LIT.

Limitations

• The transition is not proved. It is the fixed-point structure of an annealed scalar map; agreement with quenched BP is shown numerically for one or two parameter sets (v = 32, s = 2, L = 10; m = 8 for the marginals). The downward map is a further approximation and fluctuates at small ε.
• Ideal, not trained, denoiser. The theory assumes the rules are known. Nothing shows that the ImageNet DDPM, or any trained network, computes BP; the link is the shape of the curves.
• Proxies. Latent features of images are not observed; classifier activations at each depth stand in for them, with the classifier’s own hierarchy taken on trust.
• Small inconsistencies. The related-work section says results are averaged over 10^5 ImageNet samples, the Fig. 2 caption over 10,000 images; the caption’s statistic, “the maximum of their empirical distribution”, is not defined further. Main text and SI define f slightly differently.
• Uniform grammar, s = 2. All numerics use s = 2 and equiprobable rules.
• The contrast case is one mixture. That only hierarchical data invert is supported by one Gaussian mixture against one RHM.

Open questions

• A rigorous threshold for class reconstruction on the RHM with quenched random rules, and its relation to known tree-reconstruction thresholds (Kesten–Stigum and beyond).
• What a trained diffusion model on RHM data does with finite training sets, and whether its threshold moves with the number of examples (the regime of THEORY-195).
• Whether hierarchical segmentations of real images, as the authors propose, show their latent variables changing at the predicted times.