Discrete diffusion models are widely used for learning and generating discrete distributions. However, the generation process is inherently sequential, making sampling acceleration crucial. In this work, we parallelize the mainstream $\tau$-leaping algorithm for absorbing discrete diffusion in a Continuous-Time Markov Chain (CTMC) framework. By leveraging the continuous-time stochastic integral form of the $\tau$-leaping algorithm and the Picard iteration method, we achieve parallel-in-time sampling acceleration and provide a proof of exponential-order convergence for our algorithm.
We improve the overall time complexity of the $\tau$-leaping under absorbing settings from ${\mathrm{O}}(d \log S)$ to ${\mathrm{O}}(\log (d\log S)\times \log d)$ with respect to NFE (Number of Function Evaluations). Empirically, our method shows consistent acceleration across synthetic and real-data settings. The new sampler achieves at most $7$ to $9$ times runtime speedup for synthetic distributions, while maintaining the same quality with $50\%$ fewer NFE and $1.45$ to $1.86$ times runtime speedup in image/text tasks on a single GPU.
Our research expands the potential of discrete diffusion models for efficient parallel inference, with broader implications for applications such as molecular structure and language generation.
Blogger's Review: This paper opens a new path for sampling acceleration in discrete diffusion models by parallelizing the $\tau$-leaping algorithm. The significant improvements in time complexity and impressive performance in practical applications suggest a promising future in the field of efficient inference.