Source-linked AI summary
Why Diffusion Language Models Struggle with Truly Parallel (Non-Autoregressive) Decoding?
Pengxiang Li, Dilxat Muhtar, Tianlong Chen, Lu Yin, Shiwei Liu
TL;DR
Practical fast DLMs often exhibit AR-like, left-to-right decoding despite architectures that permit parallel refinement, and standard sequential training data may contribute to this behavior. NAP aligns supervision and decoding with parallel reasoning, achieving higher accuracy across benchmarks and step budgets, with larger gains under more aggressive parallelism.
Problem
Practical fast DLMs frequently converge toward AR-like left-to-right decoding, limiting the realization of genuinely parallel generation.
Method
NAP aligns supervision with parallel decoding by training on parallel reasoning trajectories and enforcing multi-stream updates through parallel-forced decoding.
Results
Across all benchmarks and step budgets, NAP achieves higher accuracy than Base and Long-CoT baselines; on GSM8K with Dream-7B at 256 steps, it reaches 60.9% versus 46.5% for Long-CoT.
Takeaways & Limitations
Aligning supervision with parallel decoding can mitigate AR-like collapse and improve performance in high-parallelism regimes.
Takeaways & Limitations
NAP is a proof-of-concept evaluated post-training at relatively small scale, and broader pretraining with inherently parallel data may be needed to completely eliminate the AR bottleneck.
Abstract
from arXiv · showhide
Diffusion Language Models (DLMs) are often advertised as enabling parallel token generation, yet practical fast DLMs frequently converge to left-to-right, autoregressive (AR)-like decoding dynamics. In contrast, genuinely non-AR generation is promising because it removes AR's sequential bottleneck, better exploiting parallel hardware to reduce synchronization/communication overhead and improve latency scaling with output length. We argue that a primary driver of AR-like decoding is a mismatch between DLM objectives and the highly sequential structure of widely used training data, including standard pretraining corpora and long chain-of-thought (CoT) supervision. Motivated by this diagnosis, we propose NAP (Non-Autoregressive Parallel DLMs), a proof-of-concept, data-centric approach that better aligns supervision with non-AR parallel decoding. NAP curates examples as multiple independent reasoning trajectories and couples them with a parallel-forced decoding strategy that encourages multi-token parallel updates. Across math reasoning benchmarks, NAP yields stronger performance under parallel decoding than DLMs trained on standard long CoT data, with gains growing as parallelism increases. Our results suggest that revisiting data and supervision is a principled direction for mitigating AR-like behavior and moving toward genuinely non-autoregressive parallel generation in DLMs. Our code is available at https://github.com/pixeli99/NAP.
1. Introduction
DLMs can in principle generate tokens in parallel, but practical systems often collapse into left-to-right decoding. The paper attributes this AR-like behavior partly to sequential training data and proposes analyzing and redesigning supervision.
- DLMs offer iterative denoising that can enable parallel token generation and potentially reduce generation latency and cost.
- Practical fast DLMs often exhibit AR-like, left-to-right decoding despite architectures that permit bidirectional context and parallel refinement.This creates quality–speed trade-offs and leaves the conditions for meaningful departures from AR behavior unclear.
- Genuinely non-AR decoding can reduce sequential critical paths and communication overhead when dependencies across spans are weak.Such decoding can distribute work across devices with only occasional synchronization.
- Standard DLM pipelines reuse AR-oriented data, including next-token-style orderings and sequential CoT rationales, encouraging AR-shaped denoising strategies.This mismatch can limit genuine parallelism and make evaluation conflate apparent speedups with reproduced AR dynamics.
- The paper studies decoding behavior in commonly used DLMs to test whether training-data sequentiality explains their AR bias.
I. Widely used training corpora are strongly sequen-
The paper finds strong sequentiality in common training corpora and persistent AR-like decoding in DLMs, while NAP aligns supervision and decoding with parallel generation. Its gains increase as parallelism becomes more aggressive, although the method remains a proof of concept.
- I. Widely used training corpora are strongly sequential: FineWeb and OpenR1-Math show strong sequence dependence, with OpenR1-Math becoming more dependent on preceding reasoning steps as chains progress.This suggests standard data teaches reasoning as an ordered chain, mismatching position-agnostic diffusion objectives.
- I. Widely used training corpora are strongly sequential: LLaDA and Dream retain high ARness under nominally arbitrary decoding, while aggressive randomization lowers ARness but typically collapses reasoning performance.Standard setups therefore face a tradeoff between preserving reasoning capacity and reducing sequential behavior.
- I. Widely used training corpora are strongly sequential: Long-CoT post-training progressively increases ARness by rewarding earlier-token stabilization before later tokens.
- I. Widely used training corpora are strongly sequential: Recent fast-DLM methods often gain speed by gating parallelism through confident prefixes or staged block-wise updates, reinforcing rather than removing AR-like order.
- I. Widely used training corpora are strongly sequential: NAP combines multiple independent reasoning trajectories with parallel-forced decoding to encourage multi-token updates across traces.
- I. Widely used training corpora are strongly sequential: NAP consistently outperforms standard long-CoT baselines under parallel decoding, with improvements becoming more pronounced as parallelism increases.The reported results use 103K fine-tuning samples and indicate alignment with non-AR dynamics rather than an implicit sequential critical path.
- I. Widely used training corpora are strongly sequential: NAP is presented as a proof of concept for mitigating AR-like behavior through data and supervision design, not as a complete solution.
2. Related Work
Related work develops diffusion language models, studies masked-token generation, and treats decoding order as a controllable quality–efficiency trade-off. These directions motivate examining sampling paths as part of DLM behavior.
- Diffusion language models extend diffusion-based generation to discrete token sequences and are studied as non-autoregressive alternatives for text generation.
- Masked diffusion operates directly in token space through random masking and has been applied from smaller models to large text and multimodal systems.
- The sampling path determines which token positions are updated or committed at each refinement step and in what order.Recent methods use planning, confidence-based early commitment, or training-time order awareness to control this path.
- Arbitrary-order flexibility can be double-edged because models may resolve low-uncertainty tokens while bypassing high-uncertainty branching points.This motivates constraining or regularizing generation order when it improves reasoning.
3. Preliminaries
This section defines masked diffusion language models and introduces metrics for quantifying autoregressive decoding bias and sequential dependence in datasets.
- 3.1. Diffusion Language Models: Masked diffusion language models generate discrete token sequences by iteratively denoising partially masked states.The forward process independently masks each token with probability t; t=1 fully masks the sequence, while t=0 leaves it unchanged.
- 3.2. Measuring Autoregressive Bias: Global ARness measures whether decoding prioritizes the leftmost remaining tokens, capturing a front-to-back filling strategy.Global-ARness@1 is used as the primary measure because it directly quantifies adherence to a causal generation order.
- 3.2. Measuring Autoregressive Bias: A Global ARness score of 1.0 at k=1 indicates strict autoregressive, left-to-right generation.The indicator is averaged over the decoding sequence to produce the Global ARness score.
- 3.3. Measuring Sequential Dependence (SeqDep): Sequential Dependence measures how much predicting a text segment improves when preceding generation history is supplied beyond the initial prompt.It uses an external autoregressive scorer and averages the prefix-context log-probability gain across output segments.
- 3.3. Measuring Sequential Dependence (SeqDep): SeqDep near 0 indicates conditional independence from previous segments, whereas high positive SeqDep indicates a chain-like left-to-right reasoning structure.The metric therefore distinguishes sequences that could theoretically be generated in parallel from those heavily dictated by preceding context.
4. Decoding Behaviors of DLMs
DLMs retain strong autoregressive decoding tendencies despite nominally flexible update orders. Sequential training data and long-CoT supervision are associated with this behavior, while forcing lower ARness can severely harm reasoning accuracy.
- 4.1. Strong Sequential Dependence in Training Corpora: FineWeb and OpenR1-Math both exhibit strong sequence dependence, with OpenR1-Math dependence increasing across reasoning steps.This suggests standard data teaches reasoning as an ordered chain, mismatching position-agnostic diffusion objectives.
- 4.2. DLMs’ Decoding Remains Largely Autoregressive: AO decoding produces high ARness, indicating that confident tokens are usually the next tokens in sequence.The reported Dream-7B AO ARness is approximately 0.92, despite AO allowing arbitrary token positions.
- 4.2. DLMs’ Decoding Remains Largely Autoregressive: Random decoding achieves near-zero ARness but causes reasoning accuracy on GSM8K and MATH 500 to collapse.The result exposes a tradeoff between genuine parallelism and reasoning performance under standard setups.
- 4.3. Long-CoT Supervision Escalates AR-ness: LLaDA’s AO ARness rises from 0.73 to 0.81 after long-CoT tuning, showing that sequential supervision further increases autoregressive behavior.Long-CoT targets privilege earlier-token stabilization before later tokens.
- 4.4. Current Fast DLMs Reinforce Sequentiality: Fast-dLLM increases ARness from 0.73 to 0.87 for LLaDA and to 0.94 for Dream-7B, accelerating an underlying sequential path rather than removing it.Its parallelism remains gated by prefix convergence and staged updates.
5. NAP: Non-Autoregressive Parallel DLMs
NAP co-designs supervision and decoding to reduce the privileged order encoded by standard chain-of-thought data. It trains on grouped independent reasoning paths and forces updates across multiple reasoning streams before summarizing them.
- 5.1. Overview: NAP restructures supervision and inference jointly to counter the autoregressive lock-in caused by sequential reasoning data.The framework replaces a single linear chain with parallel trajectories and adds parallel-forced decoding.
- 5.2. Data Curation: Training examples group P independently sampled reasoning traces into one instance, preserving diverse approaches or logical orderings as parallel paths.The traces are generated with sampling temperature τ = 1.0 and are not treated as separate samples.
- 5.2. Data Curation: NAP conditions a final summary block on diverse, potentially noisy paths so the model learns to identify valid reasoning streams and filter errors.The summary is tied to the ground-truth answer and follows the grouped paths.
- 5.3. Parallel-Forced Decoding: The decoding canvas separates m reasoning blocks from a summary block, with fixed headers and masked reasoning slots that remove causal ordering between paths.Bidirectional attention makes the reasoning streams conditionally independent given the prompt.
- 5.3. Parallel-Forced Decoding: NAP-D distributes the unmasking budget across all reasoning blocks at every step, preventing upstream paths from stabilizing before downstream paths begin.This macro-parallel schedule is paired with confidence-based updates within streams.
6. Experiments
Experiments show that NAP combines parallel-aligned supervision with parallel-forced decoding to improve reasoning accuracy and reduce reliance on sequential generation. Its benefits increase under more aggressive parallelism, while curated data exhibits stable sequential dependence across length.
- Main Results: NAP-Dream-7B reaches 83.6% on GSM8K at 1024 steps, exceeding Long-CoT's 78.0% with the same compute and training data.Across three benchmarks and step budgets, NAP outperforms both the Base model and Long-CoT baseline.
- Main Results: At 256 steps, NAP-Dream-7B scores 60.9% versus 46.5% for Long-CoT, widening the gap from +5.6% at 1024 steps to +14.4%.This 256-step setting corresponds to 4x parallel decoding.
- Main Results: NAP produces parallel bands in ARness visualizations, unlike standard models whose Arbitrary Order decoding collapses into a left-to-right diagonal pattern.The visualization links NAP's decoding behavior to multiple parallel reasoning trajectories.
- Ablation Studies: Parallel-forced decoding underperforms Arbitrary Order on an unaligned Dream-7B base model, but reaches 60.9% versus 57.4% at the aggressive 256-step budget with aligned training.The ablation indicates that supervision and decoding strategy must be co-designed for robust simultaneous generation.
- Ablation Studies: Increasing parallel reasoning paths from m = 1 to m = 3 improves NAP-Dream from 75.4% to 83.6% and NAP-LLaDA from 79.4% to 84.1%.The total token budget remains fixed, consistent with an internal ensemble effect from multiple trajectories.
- Data Analysis: Dparallel's SeqDep remains approximately 12 as sequence length grows from 500 to over 1000 tokens.The stable profile contrasts with long-chain reasoning, where dependence escalates with depth, and supports parallel updates.
7. Conclusion
The paper attributes DLMs' AR-like decoding largely to sequential training data and proposes NAP to align supervision with parallel decoding. NAP is a proof of concept, and broader pretraining with non-sequential data may be needed to fully remove the autoregressive bottleneck.
- Conclusion: NAP trains on parallel reasoning trajectories and enforces multi-stream updates to mitigate autoregressive collapse in DLMs.The conclusion frames supervision structure as central to achieving genuine parallel decoding.
- Limitations: The current implementation is a proof of concept evaluated in post-training on approximately 100K samples.This limits the demonstrated scale of the approach.
- Limitations: Broader pretraining with inherently non-sequential, parallel-structured data may be required to completely eliminate the autoregressive bottleneck.The limitation follows from the role of scaling laws in DLM behavior.