PaperlayerView exact revision on arXiv

Source-linked AI summary

ParallelBench: Understanding the Trade-offs of Parallel Decoding in Diffusion LLMs

Wonjun Kang, Kevin Galim, Seunghyuk Oh, Minjae Lee, Yuchen Zeng, Shuibai Zhang, Coleman Hooper, Yuezhou Hu, Hyung Il Koo, Nam Ik Cho, Kangwook Lee

arXiv:2510.04767v2cs.LG

TL;DR

Parallel decoding in diffusion LLMs can ignore token dependencies, creating a gap in how its quality degradation is evaluated. The paper combines information-theoretic analysis, synthetic list operations, and ParallelBench, finding severe real-world degradation and poor adaptation of parallelism to task difficulty.

  • Problem

    Existing evaluations and analyses do not adequately capture the quality degradation caused by parallel decoding when token dependencies are strong.

  • Method

    The paper analyzes parallel decoding theoretically and on synthetic list operations, then introduces ParallelBench for realistic dependency-sensitive tasks.

  • Results

    dLLMs using parallel decoding suffer severe quality degradation on seemingly simple real-world tasks, while current strategies struggle to balance speed and quality across task difficulty.

  • Takeaways & Limitations

    ParallelBench exposes limitations of current parallel decoding and supports developing methods that better manage the speed-quality trade-off.

  • Takeaways & Limitations

    The benchmark covers 3 realistic categories and 17 tasks, primarily analyzes short output sequences, and needs broader and longer-sequence evaluation.

Abstract

from arXiv · show

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.

1 INTRODUCTION

Diffusion LLMs promise faster inference through parallel decoding, but conditional independence can overlook token dependencies and degrade quality. The paper analyzes this limitation and introduces ParallelBench to evaluate it on realistic tasks and speed-quality trade-offs.

  • 1 INTRODUCTION: Parallel decoding can generate invalid token combinations because dLLMs independently unmask tokens without modeling their mutual constraints.The paper illustrates this with “New City” replacing contextually valid alternatives such as “New York” or “Mexico City.”
  • 1 INTRODUCTION: The paper uses information-theoretic analysis and synthetic list operations to quantify how data dependencies and unmasking order limit parallel-decoding accuracy.The analysis covers both conditional total correlation in the data distribution and the accuracy of different unmasking strategies.
  • 1 INTRODUCTION: ParallelBench is a realistic benchmark spanning difficulty levels, including tasks that are easy for humans and autoregressive LLMs but difficult for dLLMs using parallel decoding.It is designed to evaluate the speed-quality trade-off and adaptive parallelism.
  • 1 INTRODUCTION: Experiments show severe quality degradation for current dLLMs on seemingly simple real-world tasks under parallel decoding.The benchmark is intended to expose failures that standard math and coding evaluations may not adequately capture.
  • 1 INTRODUCTION: Existing parallel decoding strategies struggle to adjust parallelism to task difficulty, producing suboptimal speed-quality trade-offs.The paper identifies adaptive control of parallelism as a central unresolved challenge.

2 RELATED WORKS

Prior work developed diffusion language models and methods for mitigating parallel-decoding errors, but evaluations largely used standard benchmarks rather than settings designed to expose parallel-decoding vulnerabilities.

  • 2 RELATED WORKS: Diffusion language modeling progressed from discrete diffusion processes to continuous diffusion and score-based approaches for language generation.The cited work includes D3PM, Diffusion-LM, and SEDD.
  • 2 RELATED WORKS: Previous decoding analyses attributed quality degradation to conditional independence and proposed threshold-based or factor-based unmasking methods.These methods target errors arising during parallel decoding.
  • 2 RELATED WORKS: Earlier evaluations focused mainly on GSM8K and HumanEval, leaving settings where parallel decoding is especially vulnerable less explored.ParallelBench addresses this evaluation gap with tasks designed around dependency-sensitive behavior.

3 PRELIMINARIES: DIFFUSION LLM DECODING

The paper defines parallel decoding as staged generation of token sets under conditional independence, while any-order decoding uses unmasking strategies to choose which tokens become final at each step.

  • 3 PRELIMINARIES: DIFFUSION LLM DECODING: The paper assumes masked diffusion because it is used by most cited dLLMs in scope.This assumption defines the decoding setting analyzed throughout the paper.
  • 3 PRELIMINARIES: DIFFUSION LLM DECODING: Parallel decoding generates token sets across timesteps, conditioning each set on the input and previously generated tokens.Within a timestep, the model factorizes the generation probability across tokens in the set.
  • 3 PRELIMINARIES: DIFFUSION LLM DECODING: The conditional-independence factorization enables within-step parallelism but introduces errors when tokens have strong semantic or syntactic dependencies.Such errors can produce invalid combinations because factorized marginals differ from the true joint distribution.
  • 3 PRELIMINARIES: DIFFUSION LLM DECODING: Conditional total correlation measures the difficulty of parallel generation by quantifying token dependencies and sets a limit that even optimal models cannot overcome.The quantity is defined relative to the data distribution conditioned on the input.
  • 3 PRELIMINARIES: DIFFUSION LLM DECODING: Any-order decoding predicts all masked positions but finalizes only selected subsets, with the unmasking strategy determining the partition of the output sequence.The paper distinguishes static Top-k selection from other strategy families introduced in the preliminaries.

4 THEORETICAL ANALYSIS OF PARALLEL DECODING

The analysis formalizes parallel decoding error through conditional total correlation and shows that increasing parallelism can make token dependencies harder to capture. Synthetic list operations and experiments then demonstrate that decoding quality depends sharply on both task structure and unmasking strategy.

  • 4.1 A CASE STUDY ON LIST OPERATIONS: A DATA DISTRIBUTION PERSPECTIVE: Parallel decoding has an irreducible error lower bound given by the conditional total correlation of tokens decoded together.The bound is achieved by ideal factorized models whose token marginals match the data distribution.
  • 4.1 A CASE STUDY ON LIST OPERATIONS: A DATA DISTRIBUTION PERSPECTIVE: The optimal error bound decreases monotonically from C(Y |X) with one-step decoding to zero with one-by-one decoding.These are the two endpoints of the decoding spectrum.
  • 4.1 A CASE STUDY ON LIST OPERATIONS: A DATA DISTRIBUTION PERSPECTIVE: Copy and Replace Index have C(Y |X) = 0, whereas Replace Random has bounded dependence approaching log2(e) ≈1.44.Replace Random remains difficult in a limited way because exactly one item must be replaced while all others remain unchanged.
  • 4.1 A CASE STUDY ON LIST OPERATIONS: A DATA DISTRIBUTION PERSPECTIVE: Shuffle’s parallel-decoding difficulty grows without bound with sequence length, even when decoding only 2 tokens per step.For T = n/2, the error bound diverges as n increases.
  • 4.2 DECODING STRATEGY PERSPECTIVE: Random Top-k decoding fails on Shuffle as sequence length grows: accuracy converges to 0 for both k = n and k = 2.The empirical validation confirms the predicted degradation, with one-step generation converging faster than two-token decoding.
  • 4.2 DECODING STRATEGY PERSPECTIVE: Confidence-threshold decoding can guarantee success on Shuffle by reducing to one-token-at-a-time decoding when γ > 0.5.For Replace Random, threshold choices likewise determine whether decoding proceeds in parallel or sequentially, producing opposite accuracy behaviors.

5 REALISTIC BENCHMARK: PARALLELBENCH

ParallelBench is a realistic benchmark designed to expose quality degradation from parallel decoding across tasks with different token-dependency structures. It includes 17 tasks spanning queues, text writing, and puzzles, with difficulty controlled through task design and input structure.

  • 5.1 BENCHMARK OVERVIEW: ParallelBench contains 17 tasks across three categories: Waiting Line, Text Writing, and Puzzles.The categories include 10 Waiting Line tasks, 5 Text Writing tasks, and 2 Puzzle tasks.
  • 5.2 WAITING LINE: Waiting Line extends synthetic list operations to customer-service queue management, with the number of customers n controlling difficulty.The tasks apply queue operations to ordered customer lists.
  • 5.3 TEXT WRITING: Text Writing uses grammar scores and task-specific metrics to capture token-level dependencies that ROUGE alone cannot measure.Its tasks include summarization, paraphrasing, and word-to-sentence construction.
  • 5.3 TEXT WRITING: Word-to-sentence tasks vary from easy to hard by changing word relatedness, with harder inputs requiring more creative construction and larger C(Y |X).The output is freely generated from a small set of input words, increasing token dependencies.
  • 5.4 PUZZLES: Sudoku and Latin Square isolate the effect of C(Y |X) because Sudoku has unique solutions while Latin Square permits multiple valid solutions.The structurally similar tasks therefore differ in the conditional uncertainty of their outputs.

6 BENCHMARK RESULTS AND ANALYSIS ON PARALLELBENCH

PARALLELBENCH shows that parallel decoding quality depends strongly on task dependencies and decoding strategy, while current methods struggle to balance speed and quality across tasks.

  • Waiting Line: Shuffle degrades from near-perfect to zero faster than other Waiting Line operations as parallelism increases, unlike dependency-free Replace Index.Replace Random also degrades rapidly, whereas Replace Index remains stable because C(Y |X) = 0.
  • Text Writing: Text-writing degradation steepens from Paraphrasing to W2S (easy) to W2S (hard) as conditional dependencies and candidate spaces increase.All three tasks achieve near-perfect grammar scores with one-by-one decoding before degrading under parallelization.
  • Unmasking Methods: No unmasking method is universally superior: Confidence Top-k helps when C(Y |X) = 0, whereas Random Top-k performs better for dependency-heavy tasks.Confidence Threshold outperforms Top-k conservatively but can degrade rapidly at aggressive thresholds, making tuning important.
  • Speed-Quality Trade-off: The oracle achieves higher accuracy and significant speedup than threshold methods, indicating substantial room for per-sample threshold adaptation.Figure 7 compares speed-quality curves across unmasking methods using tokens decoded per step.
  • Static parallel decoding suffers severe quality degradation, while adaptive strategies still have significant room to improve the speed-quality trade-off.The benchmark evaluates diverse tasks and decoding methods, including top-k, threshold, semi-AR, and oracle comparisons.

7 EXPLORING ADDITIONAL TECHNIQUES

Additional experiments test advanced unmasking, fine-tuning, chain-of-thought prompting, remasking, and alternative diffusion transitions to improve parallel decoding.

  • The study evaluates additional unmasking strategies and discrete diffusion with uniform transition matrices for their speed-quality trade-offs on PARALLELBENCH.
  • Fine-tuning makes Replace Index nearly 100% accurate under one-by-one decoding and preserves high parallel-decoding accuracy when C(Y |X) = 0.
  • Chain-of-thought prompting mitigates quality degradation under parallelism but uses 8× more output tokens, limiting its speed-accuracy benefit.
  • Remasking samplers such as ReMDM and RCR produce no improvements on Waiting Line, exposing limitations of these training-free approaches.

8 CONCLUSION

The paper analyzes parallel-decoding trade-offs theoretically and empirically, concluding that dLLMs can lose substantial quality in realistic tasks while current strategies do not adapt parallelism effectively to task difficulty.

  • Parallel decoding in dLLMs can suffer severe quality degradation in real-world scenarios, while existing strategies fail to adapt parallelism to task difficulty for an optimal speed-quality trade-off.
  • The paper formalizes degradation from token dependencies through information-theoretic analysis and tractable synthetic list operations.
  • PARALLELBENCH is introduced as a realistic benchmark for evaluating parallel-decoding trade-offs across tasks with different difficulty levels.
  • The theoretical proof develops bounds by decomposing target tokens into timestep-specific subsets and applying conditional independence within each parallelized subset.

A.3 EXTENDED VERSION OF THEOREM 2

The extended theorem analysis establishes that optimal parallel-decoding error bounds decrease as the number of generation steps increases, including when partitions depend on the input.

  • Theorem 3 states that the optimal error bound is monotonically decreasing as the number of generation steps increases.
  • The optimal T-step error bound is defined as the expected minimum error over all possible partitions for each input.
  • The proof derives the input-dependent result by first establishing a pointwise inequality for an arbitrary input and then taking its expectation over the data distribution.

C BENCHMARK DATASET SPECIFICATIONS AND EVALUATION DETAILS

PARALLELBENCH combines diverse benchmark tasks, standardized prompting and generation settings, task-specific metrics, and adaptive unmasking comparisons to evaluate parallel-decoding behavior.

  • PARALLELBENCH includes benchmark prompts and examples spanning waiting-line operations, text writing, and other task formats.
  • Waiting Line and Puzzle tasks use one-shot prompting, whereas Text Writing tasks use zero-shot prompting.
  • All models use greedy decoding except infilling tasks, which use temperature sampling at 1.0; generation limits are 32 tokens for Waiting Line and 64 for Puzzle and Text Writing.
  • Waiting Line and Puzzle outputs are scored by exact-match accuracy, while Text Writing uses grammar and task-specific metrics including ROUGE-L, BERTScore, and inclusion accuracy.
  • Margin Top-k and Entropy Top-k perform similarly to Confidence Top-k in the reported comparisons.
  • Factor-based unmasking follows a similar trend to Threshold-based unmasking but generally uses a narrower range of tokens per step.
  • KV caching decreased accuracy in the PARALLELBENCH evaluation under parallel decoding.
  • Text Writing benefits from larger blocks, whereas Waiting Line benefits from left-to-right decoding with block length 2 because their dependency structures differ.

D.5 BENCHMARK RESULTS ON LONGER OUTPUTS

Longer-output experiments show that model capacity compounds parallel-decoding degradation: most tasks collapse toward near-zero accuracy as parallelism increases, including Text Writing tasks under multiple metrics.

  • The study focuses on short outputs to isolate parallel-decoding effects because longer outputs introduce model-capacity bottlenecks that confound analysis.
  • The extended evaluation increases Waiting Line sizes from 3–6 to 21–24 and raises generation limits to 128 tokens, while other tasks receive analogous length expansions.
  • As parallelism increases, longer-output tasks rapidly collapse toward near-zero accuracy, while even Copy sharply degrades despite being the simplest task.
  • BERTScore and ROUGE-L show mild degradation with increasing parallelism, whereas inclusion accuracy declines clearly as required content is omitted.

E.1 BENCHMARK RESULTS ON ADDITIONAL PARALLEL DECODING METHODS

Additional parallel decoding methods show mixed progress on the speed-quality trade-off, but none reaches the oracle. Confidence-based decoding remains a strong reference, while revision strategies provide little improvement.

  • Evaluation setup: The benchmark evaluates additional methods on LLaDA 1.5 and Dream 7B, with APD restricted to Dream 7B because it currently supports only that model.SlowFast Sampling, DUS, and WINO are evaluated on LLaDA 1.5.
  • Additional parallel decoding methods: WINO achieves a better trade-off curve than the confidence-threshold method, while SlowFast Sampling and DUS perform worse; all remain below the oracle.APD surpasses confidence-threshold decoding at high parallelism but falls short at low parallelism.
  • Chain-of-Thought prompting: Chain-of-Thought prompting improves LLaDA 1.5 performance, especially under parallel decoding, but increases the token count.The evaluation uses one-shot examples generated by GPT-4.1 Mini and expands the output limit for verbose reasoning.
  • Token revision strategies: RCR and ReMDM produce no significant improvements on the evaluated tasks, despite supporting token revision during decoding.For ReMDM, one revision step is optimal, with no further gains from additional steps.

F.1 CHARACTERIZING TASKS BY PARALLELIZABILITY AND DECODING ORDER

The analysis characterizes benchmark tasks by how much parallel decoding and decoding order affect performance. Results show that task parallelizability varies substantially, while standard benchmarks and realistic examples also expose sharp quality losses as parallelism increases.

  • Parallelizability: Shuffle is the hardest task to parallelize, while Words-to-Sentence, Latin Square, and Sudoku also show substantial dependency-related difficulty.Latin Square may be harder than Sudoku because multiple valid solutions require the model to commit to one.
  • Speed-quality trade-offs: Accuracy degrades rapidly for Top-k methods as tokens per step increase, while Confidence Threshold delays the drop-off but remains below the oracle.The oracle is an empirical upper bound based on per-sample thresholds that achieve the best possible accuracy.
  • Existing benchmarks: Existing benchmarks such as GSM8K, IFEval, and MATH also show decreasing accuracy as the number of tokens decoded per step increases.These benchmarks were not specifically designed to evaluate parallel decoding performance.
  • Latency analysis: Wall-clock time-quality curves mirror token-per-step speed-quality curves, supporting tokens per step as a reliable hardware-independent trade-off measure.Latency measurements were collected on a single A100 80GB GPU with batch size 1.
  • Failure cases: Parallel decoding can corrupt names, repeat adjacent tokens, violate local syntax, and disrupt long-range grammatical structure.Examples include swapped first and last names, duplicated words or articles, incorrect articles, and incoherent verb sequences.
  • Autoregressive and commercial models: Mercury solves Reverse with 100% accuracy but fails to achieve a perfect Shuffle score, while Latin Square remains challenging despite strong performance on most tasks.Mercury nevertheless exceeds or matches open-source models on most benchmark tasks.
  • Cross-model benchmark behavior: Increasing parallel tokens from 1 to 2 causes a significant quality drop even on simple Copy, while Puzzles generally receive very low scores.The benchmark therefore exposes parallelization challenges across evaluated architectures.
Loading 2510.04767v2…