Research map / Image generation / Fast diffusion sampling
Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms
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.
Proposes the first high-order numerical inference solvers (θ-RK-2 and θ-Trapezoidal) for discrete diffusion models, proving second-order KL convergence and showing gains over τ-leaping on toy, text, image, and LLaDA math tasks.
Problem
Inference of discrete diffusion models is slow: exact simulation has unpredictable time and redundant evaluations, while first-order tau-leaping needs small steps for accuracy.
Approach
Adapts second-order Runge-Kutta-style schemes (θ-RK-2 and a θ-Trapezoidal extrapolation scheme with coefficients α1, α2) to discrete diffusion via Poisson random measures with evolving intensities, giving second-order KL error for θ-Trapezoidal.
Key results
- On a 15-state toy model, the θ-Trapezoidal method converges approximately quadratically in step count, outperforming θ-RK-2 at θ=1/2.
- θ-Trapezoidal consistently beats Euler and Tweedie τ-leaping on RADD text generation at fixed NFE, and beats FHS at NFE 1024 per the paper's claim.
- On ImageNet with MaskGIT, θ-Trapezoidal achieves lower FID than Euler and τ-leaping across NFE 4 to 64.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use θ-Trapezoidal instead of θ-RK-2 | 15-state toy model · 15-state toy model | KL divergence | Helped |
| Use θ-Trapezoidal instead of Euler or τ-leaping | RADD · OpenWebText text generation | generative perplexity | Helped |
| Use θ-Trapezoidal instead of FHS | RADD · OpenWebText text generation, NFE 1024 | generative perplexity | Helped |
| Use θ-Trapezoidal instead of Euler or τ-leaping | MaskGIT · ImageNet validation split | FID | Helped |
| Use θ-Trapezoidal instead of Semi-AR | LLaDA-Instruct · GSM8K, low NFE | accuracy | Helped |
| Increase NFE for FHS or parallel decoding | MaskGIT · ImageNet validation split | FID | Hurt |
| Vary θ near its optimal choice (ablation) | θ-Trapezoidal · Text and image generation | sample quality | No clear effect |
| Use θ values in [0.3, 0.5] (ablation) | θ-Trapezoidal · Text and image generation | sample quality | Helped |
| Choose θ in (0, 1/2] rather than outside that range (ablation) | θ-RK-2 · Discrete diffusion inference | sample quality | Helped |
| Use θ-Trapezoidal rather than θ-RK-2 | Discrete diffusion inference · Theoretical convergence | discretization error | Helped |
Surprising findings
- Exact simulation (FHS) at high NFE is outperformed by the approximate θ-Trapezoidal solver in sample quality, suggesting discretization-free sampling does not imply better quality.
Limitations
- Theoretical guarantees require an assumption that the extrapolated intensity is nonnegative; empirically it holds with over 95% probability.
- θ-RK-2 convergence proven only for θ in (0, 1/2].
- Covariance-error convergence in discrete diffusion is left to future work.
Experimental setup
Datasets: OpenWebText ImageNet GSM8K
Benchmarks: GSM8K OpenWebText generative perplexity ImageNet FID
Metrics: KL divergence generative perplexity unigram entropy FID accuracy
Baselines: Euler method tau-leaping Tweedie tau-leaping First-Hitting Sampler Parallel Decoding Semi-AR sampler theta-RK-2
Builds on: tau-leaping Runge-Kutta methods RADD uniformization Tweedie tau-leaping
Closest papers by meaning
- Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics (ICLR 2025 · similarity 0.90)
- Scaling Inference Time Compute for Diffusion Models (CVPR 2025 · similarity 0.89)
- Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity (NeurIPS 2024 · similarity 0.89)
- PFDiff: Training-Free Acceleration of Diffusion Models Combining Past and Future Scores (ICLR 2025 · similarity 0.89)
- Towards Non-Asymptotic Convergence for Diffusion-Based Generative Models (ICLR 2024 · similarity 0.89)
- Distilling ODE Solvers of Diffusion Models into Smaller Steps (CVPR 2024 · similarity 0.89)
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.