Plan, Verify and Fill: A Structured Parallel Decoding Approach for Diffusion Language Models

Diffusion Language Models (DLMs) enable parallel text generation by denoising multiple masked positions in a single pass, but confidence-threshold decoding often commits only the safest predictions, leaving informative uncertainty underused. We propose Plan-Verify-Fill (PVF), a training-free draft-and-verification decoding strategy that preserves the high-confidence decoding backbone while selectively testing lower-confidence candidates with high expected verified utility. PVF uses a calibrated planning-token vocabulary to allocate its limited verification budget, accepts proposed drafts only when they remain consistent with the backbone trajectory, and otherwise defaults to conservative confidence-gated unmasking. Across benchmarks spanning mathematical reasoning, knowledge, and code generation, PVF preserves final accuracy while reducing decoding cost. Extensive empirical evaluations show that PVF achieves up to $2.3\times$ higher throughput than confidence-threshold decoding.