Research map / Image generation / Fast diffusion sampling
How Compositional Generalization and Creativity Improve as Diffusion Models are Trained
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows theoretically and empirically that diffusion models learn the Random Hierarchy Model (a PCFG) hierarchically via word2vec-like clustering, with polynomial sample complexity m^(L+1), yielding generated data coherent only up to a length that grows with training set size or time.
Problem
How many training samples diffusion models need to learn the composition rules of hierarchically compositional data, which signal they exploit, and how the finiteness of the training set shapes the coherence of generated samples.
Approach
Diffusion models learn the low-noise score of a PCFG by reconstructing latent variables hierarchically from token-context correlations (word2vec-like clustering), giving a sample complexity polynomial in context size, m^(L+1); the coherence length of generated data grows with training set size and training time.
Key results
- Sample complexity to satisfy level-l rules scales as m^(l+1), matching the theoretical prediction for the U-Net on RHM (L=2 experiments).
- For MD4 on OpenWebText, generated text shows coherence spans that grow with training tokens; at ~10^9 tokens sentences are locally correct but not globally coherent.
- On ImageNet64, MMD at early ResNet-18 layers converges first, with deeper layers converging sequentially as training proceeds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase training dataset size | D3PM U-Net on the Random Hierarchy Model · Random Hierarchy Model | compositional-rule accuracy | Helped |
| increase training dataset size | D3PM U-Net on the Random Hierarchy Model · Random Hierarchy Model | long-range token-token correlations | Helped |
| increase training time and number of training tokens | MD4 · OpenWebText | coherence length | Helped |
| increase training time and number of training tokens | MD4 · OpenWebText | token-token correlation range | Helped |
| increase training examples | Improved DDPM U-Net · ImageNet 64×64 | MMD in ResNet embeddings | Helped |
| use correlations across an entire visible tuple instead of a single visible token | Correlation-based clustering algorithm · Random Hierarchy Model, L=3 | sample complexity | Helped |
Surprising findings
- Up to about 7x10^7 training tokens, MD4 generated text shows correlations at the level of sampling noise, i.e., essentially uncorrelated tokens.
Limitations
- Theory is derived for the RHM with asymptotic limits in v and m; the natural-data results are qualitative rather than tied to the theory.
- Image experiments use a single ImageNet64 DDPM and MMD on ResNet-18 features rather than a direct coherence measure.
Experimental setup
Datasets: Random Hierarchy Model synthetic data OpenWebText ImageNet 64x64
Benchmarks: ImageNet 64x64 validation set (MMD on ResNet-18 features) OpenWebText validation set (perplexity and token correlations)
Metrics: accuracy at level l sample complexity P* token-token correlation MMD perplexity
Baselines: correlation-based clustering algorithm
Builds on: Random Hierarchy Model D3PM MD4 Improved DDPM maximal-update parameterization
Closest papers by meaning
- How Diffusion Models Learn to Factorize and Compose (NeurIPS 2024 · similarity 0.91)
- Swing-by Dynamics in Concept Learning and Compositional Generalization (ICLR 2025 · similarity 0.90)
- Generalization Dynamics of Linear Diffusion Models (NeurIPS 2026 · similarity 0.89)
- Probing the Latent Hierarchical Structure of Data via Diffusion Models (ICLR 2025 · similarity 0.89)
- Why Diffusion Models Don’t Memorize: The Role of Implicit Dynamical Regularization in Training (NeurIPS 2025 · similarity 0.88)
- Learning curves theory for hierarchically compositional data with power-law distributed features (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.