Parallel-in-time sampling accelerates discrete diffusion models 9x
New algorithm cuts NFE by 50% while maintaining output quality.
Discrete diffusion models power applications from molecular generation to language modeling, but their sequential sampling process creates a bottleneck. In a new paper, Yu Yao, Huanjian Zhou, Andi Han, Wei Huang, and Masashi Sugiyama from the University of Tokyo and RIKEN introduce a parallel-in-time sampling method that breaks this sequential dependency. Their approach rethinks the τ-leaping algorithm for absorbing discrete diffusion within a Continuous-Time Markov Chain (CTMC) framework.
By leveraging the continuous-time stochastic integral representation of the τ-leaping steps and applying Picard iteration, the team achieves provable exponential-factorial convergence. The key theoretical result: time complexity drops from O(d log S) to O(log(d log S) · log d) with respect to number of function evaluations (NFE). Practically, this translates to up to 7–9× runtime speedup on synthetic distributions, and 1.45–1.86× speedup on real image and text tasks using a single GPU — all while matching or exceeding quality with 50% fewer NFE.
The work opens the door to efficient parallel inference for discrete diffusion models, with direct implications for large-scale molecular structure generation and autoregressive language modeling. The code and paper are available on arXiv (2607.00773).
- Parallelizes the τ-leaping algorithm for absorbing discrete diffusion using Picard iteration, reducing complexity from O(d log S) to O(log(d log S) · log d) per NFE.
- Achieves 7–9× runtime speedup on synthetic data and 1.45–1.86× on image/text tasks (single GPU) while cutting NFE by 50%.
- Provides theoretical proof of exponential-factorial convergence for the proposed parallel-in-time sampler.
Why It Matters
Faster discrete diffusion sampling enables real-time generation for molecular design, language models, and other discrete data applications.