How Compositional Generalization and Creativity Improve as Diffusion Models are Trained

Alessandro Favero, Antonio Sclocchi, Francesco Cagnetta, Pascal Frossard, Matthieu Wyart · 2025

Read How Compositional Generalization and Creativity Improve as Diffusion Models are Trained by Alessandro Favero, Antonio Sclocchi, Francesco Cagnetta, Pascal Frossard, Matthieu Wyart (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-12089.txt.

Introduction

Alessandro Favero and co-authors wrote this machine learning paper, published in two thousand twenty-five, on how diffusion models learn to create new combinations. Real data is built in layers: parts make features, features make wholes, and a good generator must learn the recipe, not just the samples.

The team models the data with a tree-like grammar and proves a tidy result. A diffusion model learns the grammar's rules once it has seen enough data to cluster features that share a context, much like the old word2vec trick. Big structures need more data than small ones, so learning climbs the tree level by level. A half-trained model thus makes outputs that hang together locally but fall apart globally. Tests on text and images match the theory well. The authors link the climb to the renormalization idea from physics.

Catalog record

CREATORAlessandro Favero, Antonio Sclocchi, Francesco Cagnetta, Pascal Frossard, Matthieu Wyart
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-12089

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

How Compositional Generalization and Creativity Improve as Diffusion Models are Trained Alessandro Favero, Antonio Sclocchi, Francesco Cagnetta, Pascal Frossard, Matthieu Wyart Abstract Natural data is often organized as a hierarchical composition of features. How many samples do generative models need in order to learn the composition rules, so as to produce a combinatorially large number of novel data? What signal in the data is exploited to learn those rules? We investigate these questions in the context of diffusion models both theoretically and empirically. Theoretically, we consider a simple probabilistic context-free grammar—a tree-like graphical model used to represent the hierarchical and compositional structure of data such as language and images. We demonstrate that diffusion models learn the grammar’s composition rules with the sample complexity required for clustering features with statistically similar context, a process similar to the word2vec algorithm. However, this clustering emerges hierarchically: higher-level features associated with longer contexts require more data to be identified. This mechanism leads to a sample complexity that scales polynomially with the said context size. As a result, diffusion models trained on an intermediate dataset size generate data coherent up to a certain scale, but lacking global coherence. We test these predictions across different domains and find remarkable agreement: both generated texts and images achieve progressively larger coherence lengths as the training time or dataset size grows. We discuss connections between the hierarchical clustering mechanism we introduce here and the renormalization group in physics. † † affiliationnotice: Equal contribution 1 Introduction Compositional generalization , the ability to understand and generate novel combinations of known components, is a fundamental characteristic of human intelligence. This skill underlies what linguists refer to as creativity ( Chomsky et al., 1976 ) : the capacity to produce an infinite number of novel and well-formed expressions from a finite set of rules. Under which conditions can machines learn such a skill? The success of diffusion models in producing realistic data across various domains ( Sohl-Dickstein et al., 2015 ; Ho et al., 2020 ; Song & Ermon, 2019 ; Betker et al., 2023 ; Rombach et al., 2022 ) provides a unique opportunity to study how this ability emerges. Fundamental questions include: What signals in the data are exploited by neural networks to learn the compositional rules ? How many training examples are needed to learn such rules, and in what order are they learned? How does the finiteness of the training set affect the structure of generated data? To address these questions theoretically, we bridge two viewpoints developed in the context of natural language processing. On the one hand, symbolic approaches aim to describe the structure of data via a list of rules that generate them. For example, probabilistic context-free grammars (PCFG) ( Chomsky, 2014 ) describe sentences with trees, whose nodes are hidden variables that can generate other nodes or leaves according to probabilistic production rules. PCFGs can approximate both structural and semantic aspects of text and have also been proposed for the description of images under the name of Pattern Theory ( Grenander, 1996 ; Jin & Geman, 2006 ; Siskind et al., 2007 ) . On the other hand, statistical approaches use data-driven analyses agnostic to expert knowledge of grammatical structure. A notable example is word2vec ( Mikolov et al., 2013 ) , where a shallow neural network learns meaningful representations of words by merely predicting their neighborhood. Contributions We unify these two viewpoints by studying how diffusion models learn the Random Hierarchy Model (RHM) ( Cagnetta et al., 2024 ) , an ensemble of simple PCFGs, where production rules are drawn uniformly at random. In particular, • We show empirically that the learning process of diffusion models trained on the RHM is hierarchical, progressively capturing compositional rules at deeper levels of the PCFG’s hierarchy. • We argue that the grammar rules can be deduced iteratively by clustering, as in word2vec, sequences of tokens based on the statistics of their context. For each level, we analytically derive the corresponding sample complexity. • We show that these sample complexities match the number of data required by the diffusion model to generate data that follow the grammar rules up to the corresponding level. Since this hierarchical clustering procedure requires a number of samples that is polynomial in the size of the token sequence, this mechanism allows the model to learn a high-dimensional distribution while avoiding the curse of dimensionality . • Beyond simple PCFGs, we predict that diffusion models trained on limited samples generate data that is locally coherent (i.e., satisfying local compositional rules), but not globally, with a coherence length growing with the training time/number of samples. We confirm this prediction in diffusion models trained on OpenWebText and ImageNet. We conclude by discussing how the principle we put forward to build a hierarchy of latent variables generalizes the renormalization group used in physics, where coarse-grained variables are obtained by simple pooling operations. 1.1 Related work Sample complexity in diffusion models Under mild assumptions on the data distribution, diffusion models exhibit a sample complexity that scales exponentially with the data dimension ( Block et al., 2020 ; Oko et al., 2023 ) . It is not the case if data lie on a low-dimensional latent subspace ( De Bortoli, 2022 ; Chen et al., 2023 ; Yuan et al., 2023 ) , correspond to Gaussian mixture models ( Biroli & Mézard, 2023 ; Shah et al., 2023 ; Cui et al., 2023 ) , Ising models ( Mei & Wu, 2023 ) , or distributions that can be factorized across spatial scales ( Kadkhodaie et al., 2023a ) . Kadkhodaie et al. (2023b) framed sample efficiency in terms of the geometric inductive bias of neural network denoisers. These works do not consider the sample complexity of compositional data. Compositional generalization of diffusion models Okawa et al. (2024) ; Park et al. (2024) considered synthetic compositional data to empirically show how diffusion models learn to generalize by composing different concepts, in the absence of a compositional hierarchy. Li & Chen (2024) studied Gaussian mixtures with hierarchical clustering structure and derived the time at which different features emerge in the diffusion process. Kamb & Ganguli (2024) studied how equivariant diffusion models can compose images by combining local patches seen in the dataset. Sclocchi et al. (2025b) ; Sclocchi et al. (2025a) showed that diffusion on hierarchically compositional data can be solved using Belief Propagation. Mei (2024) showed that U-Nets can efficiently approximate the Belief Propagation algorithm on hierarchical data. Yet, efficient representability does not guarantee learnability by gradient descent for hierarchical data ( Cagnetta et al., 2024 ) . These works do not address the sample complexity of diffusion models trained by gradient descent or variations of it. Learning hierarchical representation via next-token prediction It has been observed that transformers trained on next-token prediction on PCFGs learn a hierarchical representation of the data that reflects the structure of the latent variables ( Cagnetta & Wyart, 2024 ; Allen-Zhu & Li, 2023 ; Garnier-Brun et al., 2024 ) . Closest to our work, Cagnetta & Wyart (2024) showed that for the prediction of the last token in a sequence of fixed length, the latent structure is learned hierarchically, with a sample complexity

Read the complete text