Why Diffusion Language Models Struggle with Truly Parallel (Non-Autoregressive) Decoding?

Paper: 2602.23225 Authors: Pengxiang Li, Dilxat Muhtar, Lu Yin, Tianlong Chen, Shiwei Liu Categories: cs.CL, cs.AI

Abstract

Diffusion Language Models (DLMs) promise parallel token generation, yet in practice they often converge to autoregressive (AR)-like left-to-right decoding patterns. This paper diagnoses the root cause: a fundamental mismatch between DLM training objectives and the sequential structure of standard training data, including pretraining corpora and chain-of-thought (CoT) supervision. The authors propose NAP (Non-Autoregressive Parallel DLMs), a data-centric solution that curates training examples as multiple independent reasoning trajectories and employs parallel-forced decoding to encourage multi-token parallel updates. Experiments on math reasoning benchmarks demonstrate that NAP achieves superior performance under parallel decoding compared to DLMs trained on standard sequential CoT data, with performance gains increasing as parallelism scales.

Key Contributions

• Identifies the data-objective mismatch as the primary driver of AR-like behavior in DLMs, where sequential training data conflicts with parallel generation objectives
• Proposes NAP, a data-centric approach that restructures supervision into multiple independent reasoning trajectories rather than single sequential chains
• Introduces parallel-forced decoding strategy that actively encourages simultaneous multi-token updates during training
• Demonstrates empirically that NAP outperforms standard DLM training on math reasoning tasks, with gains scaling positively with increased parallelism
• Provides open-source implementation to facilitate further research in non-autoregressive generation

The Core Problem: Data-Objective Mismatch

The paper reveals a critical insight: while DLMs are theoretically capable of parallel generation, their training on inherently sequential data creates a fundamental tension. Standard pretraining corpora and long CoT supervision exhibit strong left-to-right dependencies, where each token heavily depends on preceding context. When DLMs are trained on such data, they learn these sequential patterns and naturally gravitate toward AR-like decoding dynamics during inference, even though the diffusion framework permits parallel updates.

This mismatch manifests in practical fast DLMs that, despite their architectural capacity for parallelism, decode tokens in a predominantly sequential manner. The sequential bottleneck negates the primary advantage of non-AR models: exploiting parallel hardware to reduce latency and improve scaling with output length. The authors argue that addressing this requires rethinking not just model architecture or training objectives, but fundamentally how supervision data is structured.

NAP Methodology: Restructuring Supervision

NAP tackles the data-objective mismatch through two complementary strategies:

Independent Reasoning Trajectories: Instead of providing single long CoT sequences, NAP curates training examples as multiple independent reasoning paths. Each trajectory can be processed in parallel without strong sequential dependencies. For math reasoning tasks, this means decomposing problems into sub-problems that can be solved simultaneously rather than in strict order.

Parallel-Forced Decoding: During training, NAP employs a decoding strategy that actively encourages the model to update multiple tokens simultaneously. This contrasts with standard DLM training where the model may learn to update tokens sequentially even when parallel updates are possible. The parallel-forcing mechanism creates training dynamics that better align with the desired inference behavior.

The combination creates a virtuous cycle: data structure permits parallelism, and training strategy reinforces parallel generation patterns. This alignment between supervision structure and generation objective is the key innovation distinguishing NAP from prior DLM approaches.

Experimental Results and Analysis

NAP was evaluated on math reasoning benchmarks, comparing against DLMs trained on standard long CoT data. The results reveal several important patterns:

Scaling with Parallelism: NAP consistently outperforms baseline DLMs under parallel decoding conditions, with the performance gap widening as the degree of parallelism increases. This validates the core hypothesis that data-centric restructuring enables better exploitation of parallel generation capacity.

Genuine Non-AR Behavior: Analysis of decoding dynamics shows that NAP models exhibit more genuinely parallel token updates compared to baselines, which tend toward sequential left-to-right patterns. This behavioral difference directly translates to the performance improvements observed.

Task Performance: Beyond decoding dynamics, NAP achieves stronger task-level performance on math reasoning benchmarks. This demonstrates that parallel generation is not merely a computational efficiency gain but can also improve solution quality when properly implemented.

The results suggest that the data-centric approach is not just theoretically motivated but practically effective, offering a principled path toward realizing the full potential of non-AR generation in DLMs.

Takeaways

1. The primary obstacle to parallel generation in DLMs is not architectural but data-related: sequential training data conflicts with parallel generation objectives
2. NAP demonstrates that restructuring supervision as independent reasoning trajectories enables genuinely non-AR parallel decoding
3. Parallel-forced decoding during training is crucial for encouraging models to learn parallel update patterns rather than defaulting to sequential behavior
4. Performance gains from NAP scale positively with increased parallelism, validating the approach’s effectiveness at exploiting parallel hardware
5. Data-centric solutions offer a principled and practical direction for advancing non-autoregressive generation in language models