ParallelBench: Understanding the Trade-offs of Parallel Decoding in
  Diffusion LLMs
Authors: name: Wonjun Kang, name: Kevin Galim, name: Seunghyuk Oh, name: Minjae Lee, name: Yuchen Zeng, name: Shuibai Zhang, name: Coleman Hooper, name: Yuezhou Hu, name: Hyung Il Koo, name: Nam Ik Cho, name: Kangwook Lee
Organization: FuriosaAI

While most autoregressive LLMs are constrained to one-by-one decoding,
diffusion LLMs (dLLMs) have attracted growing interest for their potential to
dramatically accelerate inference through parallel decoding. Despite this
promise, the conditional independence assumption in dLLMs causes parallel
decoding to ignore token dependencies, inevitably degrading generation quality
when these dependencies are strong. However, existing works largely overlook
these inherent challenges, and evaluations on standard benchmarks (e.g., math
and coding) are not sufficient to capture the quality degradation caused by
parallel decoding. To address this gap, we first provide an
information-theoretic analysis of parallel decoding. We then conduct case
studies on analytically tractable synthetic list operations from both data
distribution and decoding strategy perspectives, offering quantitative insights
that highlight the fundamental limitations of parallel decoding. Building on
these insights, we propose ParallelBench, the first benchmark specifically
designed for dLLMs, featuring realistic tasks that are trivial for humans and
autoregressive LLMs yet exceptionally challenging for dLLMs under parallel
decoding. Using ParallelBench, we systematically analyze both dLLMs and
autoregressive LLMs, revealing that: (i) dLLMs under parallel decoding can
suffer dramatic quality degradation in real-world scenarios, and (ii) current
parallel decoding strategies struggle to adapt their degree of parallelism
based on task difficulty, thus failing to achieve meaningful speedup without
compromising quality. Our findings underscore the pressing need for innovative
decoding methods that can overcome the current speed-quality trade-off. We
release our benchmark to help accelerate the development of truly efficient
dLLMs.