cs.LGSep 30, 2025

Free Draft-and-Verification: Toward Lossless Parallel Decoding for Diffusion Large Language Models

Authors: Shutong Wu, Jiawei Zhang

Organizations: Department of Computer Sciences, University of Wisconsin–Madison, Madison, WI.

Abstract

Diffusion Large Language Models (dLLMs) have emerged as a compelling paradigm for language modeling, offering the unique potential for highly efficient inference via multi-token parallel decoding. However, unlocking this potential remains challenging. High-quality generation typically defaults to one-token-per-step static decoding, while existing parallel algorithms rely on heuristic confidence thresholds, introducing a fragile trade-off between decoding efficiency and generation quality. To overcome this, we introduce Free Draft-and-Verification (FreeDave), a novel training-free and model-free fast decoding algorithm. FreeDave capitalizes on the inherent properties of dLLMs by treating future token predictions as ``free drafts'' and rigorously self-verifying them in subsequent forward passes. Theoretically, FreeDave searches for a shorter decoding path that is guaranteed to reproduce the exact sequence generated by static decoding, achieving algorithmically lossless acceleration. With a sufficiently large draft budget and a verification frontier that does not retreat, it can use the fewest possible model forward passes among feasible paths. Extensive evaluations on math reasoning and code generation benchmarks demonstrate that FreeDave can boost the number of generated tokens per model forward (TPF) by up to 5.48×\times and tokens per second (TPS) by up to 3.94×\times, while robustly maintaining generation quality and avoiding the task-specific performance degradation faced by heuristic methods. Code is available at https://github.com/cychomatica/FreeDave.

Figures & tables

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. PSD: Pushing the Pareto Frontier of Diffusion LLMs via Parallel Speculative Decoding

    May 15, 2026Shengyin Sun, Yiming Li, Renxi Liu +7Parallel Speculative DecodingMasked Diffusion Models

  2. Streaming-dLLM: Accelerating Diffusion LLMs via Suffix Pruning and Dynamic Decoding

    Jan 25, 2026Zhongyu Xiao, Zhiwei Hao, Jianyuan Guo +4Adaptive InferenceBlockwise Diffusion Language Models