Accelerating Discrete Diffusion Models with Parallel-In-Time Sampling

• URL: http://arxiv.org/abs/2607.00773v1
• Date: Wed, 01 Jul 2026 10:59:33 GMT
• Title: Accelerating Discrete Diffusion Models with Parallel-In-Time Sampling
• Abstract summary: We parallelize the mainstream $$-leaping algorithm for absorbing discrete diffusion in a Continuous-Time Markov Chain (CTMC) framework.<n>By leveraging the continuous-time integral form of the $$-leaping algorithm and the Picard method, we achieve parallel-in-time sampling acceleration.<n>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.
• Score: 55.388363730120325
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $τ$-leaping algorithm for absorbing discrete diffusion in a Continuous-Time Markov Chain (CTMC) framework. By leveraging the continuous-time stochastic integral form of the $τ$-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 $τ$-leaping under absorbing settings from ${\mathcal{O}}(d \log S)$ to ${\mathcal{O}}(\log (d\log S)\cdot \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$--$9\times$ runtime speedup for synthetic distribution, and maintains the same quality with $50\%$ fewer NFE and $1.45$--$1.86\times$ 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.

Related papers

• Demystifying Pipeline Parallelism: First Theory for PipeDream [53.657104889705856]
  In this paper we introduce Randomized PipeDream (PD) as a stale block-SGD abstraction that yields clean non convergence for a PD-style method.<n>We prove that the delay induced by steady-state PD grows as $S2 - S/2 + O(1)$ for $S$ stages, so the stale-read contribution scales as $(2 S4)$, equivalently $(S4/K)$ in the tuned-rate form.
  arXiv  Detail & Related papers  (2026-06-02T11:14:57Z)
• Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees [9.180350432640912]
  We study the sampling efficiency of score-based discrete diffusion models under a continuous-time Markov chain (CTMC) formulation.<n>For uniform discrete diffusion, we show that the $$-leaping algorithm achieves an complexity of order $tilde O(d/varepsilon)$.<n>For masking discrete diffusion, we introduce a modified $$-leaping sampler whose convergence rate is governed by an intrinsic information-theoretic quantity.
  arXiv  Detail & Related papers  (2026-02-16T18:48:17Z)
• Self-Refining Diffusion Samplers: Enabling Parallelization via Parareal Iterations [53.180374639531145]
  Self-Refining Diffusion Samplers (SRDS) retain sample quality and can improve latency at the cost of additional parallel compute.<n>We take inspiration from the Parareal algorithm, a popular numerical method for parallel-in-time integration of differential equations.
  arXiv  Detail & Related papers  (2024-12-11T11:08:09Z)
• Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models [55.07411490538404]
  We propose a novel parallel sampling method that improves adaptive complexity dependence on dimension $d$.<n>Our approach builds on parallel simulation techniques from scientific computing.
  arXiv  Detail & Related papers  (2024-12-10T11:50:46Z)
• Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel [10.840582511203024]
  We show that our algorithm can be parallelized to run in only $widetilde O(log2 d)$ parallel rounds. We also show that our algorithm can be parallelized to run in only $widetilde O(log2 d)$ parallel rounds.
  arXiv  Detail & Related papers  (2024-06-03T01:34:34Z)
• Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity [11.71206628091551]
  Diffusion models are costly to train and evaluate, reducing the inference cost for diffusion models remains a major goal. Inspired by the recent empirical success in accelerating diffusion models via the parallel sampling techniqueciteshih2024parallel, we propose to divide the sampling process into $mathcalO(1)$ blocks with parallelizable Picard iterations within each block. Our results shed light on the potential of fast and efficient sampling of high-dimensional data on fast-evolving modern large-memory GPU clusters.
  arXiv  Detail & Related papers  (2024-05-24T23:59:41Z)
• Fast Sampling via Discrete Non-Markov Diffusion Models with Predetermined Transition Time [49.598085130313514]
  We propose discrete non-Markov diffusion models (DNDM), which naturally induce the predetermined transition time set.<n>This enables a training-free sampling algorithm that significantly reduces the number of function evaluations.<n>We study the transition from finite to infinite step sampling, offering new insights into bridging the gap between discrete and continuous-time processes.
  arXiv  Detail & Related papers  (2023-12-14T18:14:11Z)
• DiffuSeq-v2: Bridging Discrete and Continuous Text Spaces for Accelerated Seq2Seq Diffusion Models [58.450152413700586]
  We introduce a soft absorbing state that facilitates the diffusion model in learning to reconstruct discrete mutations based on the underlying Gaussian space. We employ state-of-the-art ODE solvers within the continuous space to expedite the sampling process. Our proposed method effectively accelerates the training convergence by 4x and generates samples of similar quality 800x faster.
  arXiv  Detail & Related papers  (2023-10-09T15:29:10Z)
• SYNTHESIS: A Semi-Asynchronous Path-Integrated Stochastic Gradient Method for Distributed Learning in Computing Clusters [7.968142741470549]
  ulstochastic gradulient ulsearch is developed to overcome the limitations of both synchronous and asynchronous distributed learning algorithms. algname algorithms have (O(sqrtNepsilon-2(Delta+1) d+N)) and (O(sqrtNepsilon-2(+1) d+N)) (epsilon)-stationary point in non-Delta learning under distributed and shared memory architectures
  arXiv  Detail & Related papers  (2022-08-17T17:42:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.