Certified Speedups for Diffusion Language Models

Diffusion language models write text differently from ordinary chatbots. An ordinary model produces one word-piece (token) at a time, left to right. A diffusion language model starts from a sequence of blanks and fills in many positions at once over a few dozen rounds. Almost all of their speed comes from one decision made at every round: how many blanks to fill and lock in right now. Current fast samplers make this decision with hand-set confidence thresholds. When the thresholds are right, the result is a large speedup at almost no cost. When they are wrong for a new model, task, or prompt mix, the sampler silently changes answers, and the user never finds out how often.

We propose to replace those hand-set thresholds with calibrated ones that carry a finite-sample guarantee. The guarantee reads: "on at most an $\alpha$ fraction of prompts does the fast sampler give a different final answer than the slow, careful sampler." The fast sampler then commits as many tokens per round as that guarantee allows. The guarantee is measured against the slow sampler's own output rather than against human labels, so calibration needs only unlabeled prompts. It can therefore be redone cheaply whenever the deployment distribution moves.

Core Claim

Parallel commitment is the right place to put statistical control in masked diffusion decoding. Remasking, the other popular lever, is the wrong place. The claim rests on three pieces of evidence from the literature.

The first is negative. Re-evaluating Confidence Remasking in Masked Diffusion Language Models studies remasking, meaning un-committing tokens so the model can reconsider them. It shows that training-free remasking gains only about 0.4–0.5% accuracy at block length 32. It also finds that in 75–95% of remasked cases the model regenerates the identical token. Read one way, this says the frozen model's committed tokens are usually already what it would choose again. Correcting commitments after the fact buys little, so the leverage lies in deciding correctly when to commit.

The second is positive. Accelerating Diffusion Large Language Models with SlowFast Sampling: The Three Golden Principles shows that committing high-confidence spans in parallel yields a 15.63x speedup on GPQA, and 34.22x with caching, with reported accuracy drops often under 1%. The authors concede that their certainty and convergence thresholds need manual retuning across model families.

The third concerns structure. Efficient Test-Time Scaling via Hierarchical Search and Self-Verification for Discrete Diffusion Language Models identifies an early "logic phase transition" window in the denoising trajectory. This suggests that the right amount of parallelism differs between early and late rounds. A single global threshold should therefore be looser than necessary in some phases and too tight in others.

The contribution has three parts. The first is a phase-wise vector of commitment thresholds. The second is a label-free, reference-relative risk. The third is a Learn-Then-Test calibration that selects the fastest threshold vector certified to keep risk below $\alpha$. As far as the research file shows, no existing work calibrates the internal iteration dynamics of a non-autoregressive decoder under a distribution-free guarantee.

How It Differs From Prior Work

The method comes from distribution-free risk control. In this family of procedures, a small held-out calibration set is used to pick a decision parameter so that expected loss on new data provably stays below a budget, assuming only that calibration and test prompts are exchangeable.

The closest methodological ancestor is Safe and Efficient In-Context Learning via Risk Control. It uses Learn-Then-Test to calibrate an early-exit threshold across transformer layers and saves 53% of layer passes without exceeding its tolerance. It also defines risk relative to a zero-shot reference rather than as absolute error. We reuse both ideas, calibrated compute reduction and reference-relative loss. We move them from the depth dimension of an autoregressive model to the refinement-round dimension of a bidirectional decoder. There, one decision changes many positions at once and alters every later round.

Conformal Language Modeling also calibrates a stopping rule with Learn-Then-Test. Its rule decides when to stop drawing independent samples from a black-box model. It does not touch how any single sample is decoded. Conformal Autoregressive Generation: Beam Search with Coverage Guarantees calibrates beam width token by token, which requires left-to-right conditioning that bidirectional decoders lack. It also reports beam widths spiking past 100 on hard tasks.

How to Trust Your Diffusion Model: A Convex Optimization Approach to Conformal Risk Control is the precedent for replacing one scalar calibration parameter with a vector. On AbdomenCT-1K at $\alpha=0.05$ it shrinks mean interval length from 0.1506 to 0.1369. Its setting is continuous pixel intervals after sampling, whereas ours is discrete commitment decisions during sampling.

On the diffusion side, CORE: Context-Robust Remasking for Diffusion Language Models reports sizable code gains from perturbation-based remasking, including +9.2% on MBPP with LLaDA-8B-Base. That result partially contradicts the remasking skepticism above. CORE spends extra forward passes to improve accuracy, whereas we remove forward passes while bounding degradation. The two are complementary, and CORE can serve as the slow reference decoder in one experimental arm.

Method

Let $x$ be a prompt. Let $R(x)$ be the final answer produced by a reference decoder, for example LLaDA's standard low-confidence schedule at full step count. Let $A_\lambda(x)$ be the answer produced by the accelerated decoder with threshold vector $\lambda=(\lambda_1,\dots,\lambda_P)$.

The accelerated decoder works as follows. In denoising phase $p$, where phases are defined by the fraction of positions still blank, it commits every blank position whose top-token probability is at least $\lambda_p$. It always commits at least one position per round, so decoding terminates.

The loss is $L(\lambda,x)=\mathbf{1}\{A_\lambda(x)\not\equiv R(x)\}$. Here $\equiv$ means answer equivalence: the same extracted numeric answer for math, and passing the same unit tests for code. This disagreement loss upper-bounds true degradation, the event that the fast answer is wrong while the reference answer is right. Calibration therefore needs no gold labels. As an alternative arm, we also calibrate the labeled degradation loss directly, which is less conservative.

We fix a finite grid $\Lambda$ of threshold vectors and $n$ exchangeable calibration prompts. For each candidate $\lambda$, we test the null hypothesis that its risk exceeds $\alpha$ using an exact binomial p-value on the $n$ observed losses. The candidates are tested in a fixed order, from conservative to aggressive, which controls family-wise error without a Bonferroni penalty. The order is chosen by average forward-pass count on a separate pilot split. Among the candidates that reject their null, we select the one with the lowest mean forward-pass count. Learn-Then-Test then gives

$$ \Pr\Big(\mathbb{E}_{x}\big[L(\hat\lambda,x)\big]\le\alpha\Big)\ge 1-\delta, $$

where $\hat\lambda$ is the selected vector, the expectation is over a fresh test prompt, and $\delta$ is the allowed probability that calibration itself fails.

Two technical points matter. First, the loss is not monotone in $\lambda$, because committing a token changes every later round. Learn-Then-Test does not require monotonicity, which is why we use it rather than plain conformal risk control. Second, with stochastic sampling, the loss includes sampling randomness and the guarantee holds marginally over it. In the main experiments we fix seeds so that the reference decoder is deterministic.

Research Program

We will implement the calibrated committer inside inclusionAI/dInfer, which exposes a separate diffusion-iteration manager and decoder. We will reuse LiangrunFlora/Slow-Fast-Sampling and maomaocun/dLLM-cache as the heuristic comparison and as optional caching. The models are LLaDA-8B-Instruct, introduced in Large Language Diffusion Models, and Dream-7B-Instruct.

We start with $P=3$ phases and roughly 60 grid vectors. Calibration uses $n$ between 250 and 2000 prompts per task. The central analyses have three parts. The first asks how much speedup the phase-wise vector buys over a scalar threshold at fixed $\alpha$. The second measures how conservative label-free disagreement risk is compared with labeled degradation risk. The third asks whether cheap recalibration on unlabeled prompts from a shifted task restores the guarantee after naive transfer breaks it.

Baselines

The naive reference point is the slow reference decoder itself: full-step LLaDA or Dream decoding, which has zero degradation by definition and the maximum number of forward passes. For orientation, Large Language Diffusion Models reports 70.3% zero-shot GSM8K for LLaDA 8B Base. Every accelerated method is reported as speedup over this decoder together with its realized disagreement and degradation.

The strongest existing method is SlowFast sampling (Accelerating Diffusion Large Language Models with SlowFast Sampling: The Three Golden Principles). It reports a 15.63x speedup on GPQA without caching, 34.22x with dLLM-Cache, and accuracy drops often below 1%. It is the strongest competitor because it already exploits the same certainty and convergence structure that we exploit. We run it with the authors' default thresholds on the same models, prompts, seeds, and hardware, with and without caching. We give our method caching only when SlowFast has it too.

We beat SlowFast only in one of two cases. In the first, at matched realized degradation, our certified operating point is faster. In the second, at a matched speedup, SlowFast's defaults exceed $\alpha$ on some task or model where our method does not. If SlowFast's defaults already sit below $\alpha$ at a higher speedup everywhere, we will report that our contribution reduces to certification alone.

A second baseline is fixed-step reduction: running the reference schedule with 1/2, 1/4, and 1/8 of the steps. This is the obvious knob that any practitioner would try first.

Three ablations isolate our ingredients. A scalar-threshold version tests the value of the phase-wise vector. A version calibrated on labeled degradation loss tests the price of being label-free. A plain validation-tuned version, which picks the fastest $\lambda$ whose empirical calibration risk is at most $\alpha$ with no statistical margin, tests the value of the guarantee itself. All variants share the same grid, calibration prompts, and forward-pass budget for calibration.

Why not just…?

Why not just tune the SlowFast thresholds on a validation set? This is the most serious alternative, because in expectation it will land close to our operating point. Its weakness is variance. With a few hundred calibration prompts and $\alpha$ around 2–5%, picking the empirically fastest safe point overfits the split, and realized test risk will exceed $\alpha$ on a sizable fraction of splits. The validation-tuned ablation measures this directly over 100 random calibration/test splits. If its violation rate is near $\delta$ at realistic $n$, the guarantee adds little, and we will say so. We could find no reported result on Lacuna for the risk-violation rate of heuristic dLLM sampling thresholds.

Why not just use speculative decoding with an autoregressive verifier? DiffuSpec: Unlocking Diffusion Language Models for Speculative Decoding reports a 3.08x speedup with exact preservation of the target model's outputs. It does this by pairing Dream-7B with a Qwen2.5-32B verifier. That requires hosting a second, much larger model. It also inherits left-to-right behavior, such as the reversal curse on which LLaDA outperforms GPT-4o (45.6% versus 34.3%). Our method keeps a single native diffusion model and aims for larger speedups at a bounded, stated risk. These are different deployment regimes, and we will not claim to dominate DiffuSpec on its own terms.

Why not just add post-hoc abstention on the finished answer? Selective generation, as in Selective Generation for Controllable Language Models, controls the error rate of answers that are emitted. It spends the full decoding cost before deciding and never reduces compute. It also answers a different question, namely whether an answer is correct, rather than whether acceleration changed it. The two compose naturally: our certified fast decoder can feed an abstention layer. We will report the compute saved at a fixed abstention guarantee as a secondary result.

Why not just remask more? The flip-flop evidence in Re-evaluating Confidence Remasking in Masked Diffusion Language Models indicates that training-free remasking mostly regenerates identical tokens and adds latency. CORE's contrary gains come at the cost of extra forward passes. For this reason we treat remasking as a possible reference decoder, not as an acceleration lever.

Proposed Experiments

The benchmarks are GSM8K, MATH-500, HumanEval, MBPP, and GPQA, with $\alpha\in\{0.02,0.05,0.10\}$ and $\delta=0.1$. For each setting we report mean forward passes, wall-clock tokens per second, realized disagreement, and labeled degradation. We also report the fraction of 100 random splits in which realized test risk exceeds $\alpha$.

Four checks decide the outcome. The first is validity: our violation rate must stay at or below about $\delta$ on every task and model. The second is the value of the vector: at equal $\alpha$, the phase-wise version must be meaningfully faster than the scalar version. If it is not, the vector design is dropped in favor of the simpler scalar. The third compares against SlowFast: at matched realized degradation, we record whether our method is faster, or whether SlowFast's defaults exceed $\alpha$ on at least one model or task pairing. The fourth tests shift. We calibrate on GSM8K and test on MATH-500, expecting violation. We then recalibrate using only 250 unlabeled MATH-500 prompts and check that validity is restored.

A clean result would be a certified operating point within a small factor of SlowFast's speed that never silently exceeds its stated risk. It would also show that the label-free loss costs only modest extra conservatism relative to the labeled one.