Accelerating Discrete Diffusion Models with Parallel-In-Time Sampling

arXiv:2607.00773v1 Announce Type: new Abstract: Discrete diffusion models are widely used for learning and generating discrete distributions. As the generation process is inherently sequential, the acceleration of sampling is of significant importance. In this work, we parallelize the mainstream au-leaping algorithm for absorbing discrete diffusion in a Continuous-Time Markov Chain (CTMC) framework. By leveraging the continuous-time stochastic integral form of the au-leaping algorithm and the Picard iteration method, we achieve parallel-in-time sampling acceleration and provide a proof of exponential-factorial convergence for our algorithm. We improve the overall time complexity of au-leaping under absorbing settings from {O}(d log S) to {O}(log (dlog S)dot log d) with respect to NFE. Empirically, our method shows consistent acceleration across synthetic and real-data settings. The new sampler achieves at most 7--9imes runtime speedup for synthetic distribution, and maintains the same quality with 50% fewer NFE and 1.45--1.86imes runtime speedups 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.

Source: arXiv cs.LG | 2026-07-02