Natural data are often organized as a hierarchical composition of features. How many samples do generative models need to learn composition rules to produce a combinatorially large number of novel data? What signal in the data is exploited to learn those rules? We investigate these questions theoretically and empirically in the context of diffusion models. Theoretically, we consider a simple probabilistic context-free grammar—a treelike 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 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 tested these predictions across different domains and found remarkable agreement: both generated texts and images achieved progressively larger coherence lengths as training time or dataset size increased. Finally, we discuss connections between the hierarchical clustering mechanism introduced here and the renormalization group in physics.