SpecCTMC: Exact Speculative Simulation of Diffusion Language Model Continuous-Time Markov Chains

Siva Rajesh Kasa, Yasong Dai, Sumit Negi, Hongdong LiarXiv 2026 · arXiv

TL;DR

SpecCTMC is a training-free speculative sampling algorithm that significantly accelerates Masked Diffusion Language Models (MDLMs) without sacrificing mathematical exactness. By exploiting the unique property that unmasking times in these models are independent of token identities, it reduces sequential model evaluations by up to 4.38× while perfectly preserving the original sampling distribution.

What Problem Does This Paper Address?

Masked Diffusion Language Models (MDLMs) like LLaDA and Dream offer a flexible alternative to standard autoregressive models, allowing for non-linear text generation. However, they face a major efficiency hurdle: to generate text that is "exact" (i.e., follows the model's intended probability distribution), they typically require one sequential model evaluation for every single token produced.

While researchers have tried to speed this up using parallel decoding (predicting multiple tokens at once), this often introduces "factorization errors" because tokens in a sequence are rarely independent. Alternatively, numerical solvers can speed up the process but introduce "discretization errors," blurring the model's precision. The challenge is to find a way to generate text faster without these approximations.

Methods

The authors introduce SpecCTMC, a speculative sampler designed for the continuous-time Markov chain (CTMC) framework underlying MDLMs.

Unlike traditional speculative decoding for autoregressive models, which requires a separate, smaller "draft" model, SpecCTMC is training-free. It uses the target model itself to generate "draft" tokens based on its current state.

The core innovation relies on a specific property of "absorbing-mask" diffusion: the random times at which tokens are unmasked depend only on the total number of masks remaining, not on the specific tokens themselves. This allows SpecCTMC to:

  1. Pre-sample the "clock": Determine all future unmasking times in advance.
  2. Draft and Batch: Propose a sequence of future token updates and evaluate their validity in parallel using a single batched model call.
  3. Verify and Correct: Use an exact acceptance-and-correction procedure (based on maximal coupling) to ensure that if a draft is rejected, the "corrected" token is sampled from the exact residual distribution.

This process, illustrated in Figure 1, ensures the final output is statistically identical to the slow, one-token-at-a-time method.

Comparison of sampling methods: Direct CTMC (slow/exact), Finite solvers (fast/approximate), and SpecCTMC (fast/exact).

Datasets

The researchers evaluated SpecCTMC across a diverse set of benchmarks to test reasoning, coding, and instruction-following:

  • GSM8K & MATH: Mathematical word problems.
  • MBPP & HumanEval: Python programming tasks.
  • IFEval: Instruction-following capabilities.
  • MathVerse & MathVista: Multimodal (image+text) mathematical reasoning.

They tested these using state-of-the-art MDLMs: LLaDA-8B-Instruct and Dream-v0-Instruct-7B.

Key Insights and Ideas

  • The "Aha" Moment on Timing: The realization that the "event clock" is independent of token values is crucial. It means you can fix the timeline of generation and only speculate on what happens at those times, rather than when they happen.
  • Exactness is Free (Sort of): Most speed-up methods trade off accuracy for speed. As shown in Figure 2, SpecCTMC maintains a 100% accuracy ratio relative to the exact reference, whereas approximate solvers like tau-leaping see accuracy plummet as they try to go faster.
  • Stochasticity for Success: The paper highlights that for complex reasoning (like GSM8K), deterministic "greedy" decoding often fails. By accelerating stochastic sampling, SpecCTMC makes it practical to run multiple attempts (Pass@K), which significantly improves the chances of finding a correct answer.
Figure 2. Exact law preserving of SpecCTMC on NFE accelera- tion. On GSM8K with LLaDA-8B-Instruct (256 generated tokens), SpecCTMC reduces target NFEs by 2.88× relative to DirectCTMC while preserving expected accuracy. Finite-step samplers trade accuracy for fewer evaluations.

Key Results

  • Evaluation Reduction: SpecCTMC achieved a 1.73× to 4.38× reduction in sequential model evaluations (NFEs) across various benchmarks.
  • Wall-Clock Speedups: On high-end hardware like the NVIDIA B200, this translated to real-world speedups of up to 2.88×.
  • Multimodal Gains: The benefits extended to image-conditioned models, with NFE reductions of over 6× on MathVerse and MathVista.
  • Solution Coverage: In stochastic settings, SpecCTMC reached the same solution coverage as the exact reference but with ~2.8× fewer evaluations.

Limitations and Future Work

  • Hardware Sensitivity: The actual wall-clock speedup depends heavily on the GPU's ability to handle batches efficiently. As sequence length grows, the "overhead" of processing multiple candidate states in parallel increases, which can eventually eat into the speed gains (see Figure 3).
  • Draft Quality: The efficiency of SpecCTMC is tied to how well the model can predict its own future states. If unmasking one token drastically changes the predicted distribution of others, the "acceptance rate" drops, and the sampler reverts to sequential steps.
  • Future Directions: The authors suggest that combining SpecCTMC with other optimizations, like advanced KV-caching or even better "self-drafting" strategies, could further push the boundaries of MDLM efficiency.
Figure 3. Batching cost and complete-generation speedup depend on the hardware. (a, b) Forward-only relative cost of one three- candidate target call against one single-candidate call, versus complete sequence length for LLaDA-8B-Instruct and Dream-7B-Instruct on a B200 and an L40S GPU. The dashed line marks the cost of three separate calls and the dotted line one single-candidate call. At short lengths on the B200, one three-state call costs less than three separate calls. As sequence length grows, the three-state call approaches the cost of three separate calls on both GPUs, with the L40S reaching that regime at shorter lengths. (c) Complete-generation speedup of SpecCTMC over DirectCTMC versus speculation depth for Dream-7B-Instruct on HumanEval and GSM8K with 256 generated tokens, on a B200 (solid) and an L40S (dashed); shaded bands are paired 95% intervals. The same depth, acceptance, and evaluation reduction give different wall-clock outcomes on the two devices, and depth 8 on GSM8K exceeds L40S memory.

Summary updated

Abstract

Masked diffusion language models offer parallel text generation, but independently sampling multiple tokens can disrupt their dependencies and change the output distribution. Exact continuous-time sampling avoids this approximation, yet typically requires one sequential model evaluation per token. We introduce SpecCTMC, a training-free speculative sampler that reduces this sequential bottleneck without a separate draft model. SpecCTMC proposes successive token updates using previously computed model predictions, evaluates their intermediate states in parallel, and applies an exact acceptance-and-correction procedure. We prove that SpecCTMC preserves the joint distribution of event times, generation order, and token values of the underlying continuous-time Markov chain. It therefore introduces neither time-discretization error nor additional factorization error from parallel decoding. Experiments on LLaDA-8B-Instruct and Dream-v0-Instruct-7B across five benchmarks demonstrate 1.73-4.38x fewer sequential model evaluations than direct continuous-time sampling, while preserving the reference sampling distribution. Our code is available at: https://github.com/kasakh/specctmc
BibTeX
@misc{kasa2026specctmc,
  author = {Siva Rajesh Kasa and Yasong Dai and Sumit Negi and Hongdong Li},
  title = {{SpecCTMC: Exact Speculative Simulation of Diffusion Language Model Continuous-Time Markov Chains}},
  year = {2026},
  eprint = {2611.08362},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.08362},
}
Figure