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

Source: arXiv - 2602.23225v1

Overview

Diffusion Language Models (DLMs) have been touted as a way to generate text in parallel, sidestepping the slow left‑to‑right (autoregressive) bottleneck that dominates most modern generators. In practice, however, many fast DLMs still end up behaving like autoregressive models, especially when trained on the usual pre‑training corpora and chain‑of‑thought (CoT) data. This paper pinpoints why that happens and proposes a data‑centric fix—NAP (Non‑Autoregressive Parallel DLMs)—that reshapes the training data to better match truly parallel decoding.

Key Contributions

• Diagnosis of AR‑like drift: Shows that the mismatch between diffusion objectives and the highly sequential structure of standard language data (including long CoT examples) pushes DLMs toward left‑to‑right decoding.
• NAP framework: Introduces a simple yet effective data‑curation pipeline that creates independent reasoning trajectories and pairs them with a parallel‑forced decoding schedule, encouraging multi‑token updates at each diffusion step.
• Empirical validation on math reasoning: Demonstrates that NAP‑trained DLMs outperform baseline diffusion models on several math‑reasoning benchmarks when decoded in parallel, with larger gains as the degree of parallelism increases.
• Open‑source release: Provides code and curated datasets (https://github.com/pixeli99/NAP) to enable reproducibility and further research.

Methodology

1. Problem formulation: Diffusion models generate a sequence by iteratively denoising a latent representation. The authors observe that, during training, the loss is dominated by predicting the next token in a chain, which implicitly encourages left‑to‑right updates.
2. Data‑centric redesign (NAP):
   • Trajectory extraction: From existing CoT examples, they split a long reasoning chain into several short, self‑contained sub‑chains that can be solved independently.
   • Parallel‑forced supervision: During training, the model is asked to predict all tokens of a sub‑chain simultaneously rather than one at a time, and the diffusion schedule is tweaked to apply larger denoising steps that update multiple positions in parallel.
3. Training pipeline: The same diffusion architecture as prior DLMs is used; only the supervision signal changes. No architectural modifications or extra parameters are introduced.
4. Evaluation: They compare standard diffusion models (trained on raw CoT data) with NAP‑trained models across three math reasoning datasets (e.g., GSM‑8K, MathQA). Decoding is performed with varying degrees of parallelism (2‑way, 4‑way, 8‑way).

Results & Findings

• Performance gap widens with more parallelism: As the number of tokens updated per diffusion step grows, NAP retains or improves accuracy, while the baseline degrades sharply.
• Latency reduction: On a single V100 GPU, 8‑way parallel decoding cuts end‑to‑end latency by ~60 % compared with left‑to‑right decoding of the same model size.
• Qualitative analysis: Sample generations show that NAP’s parallel trajectories produce coherent multi‑step reasoning without the “staircase” effect typical of AR‑like diffusion outputs.

Practical Implications

• Faster inference for latency‑sensitive apps: Chatbots, code assistants, or on‑device language tools can benefit from the reduced synchronization overhead, especially when running on GPUs or specialized accelerators that excel at batch operations.
• Better hardware utilization: Parallel decoding aligns with the SIMD/SME execution model of modern AI chips, allowing higher throughput without scaling the model size.
• Data‑centric engineering: The work suggests that, before redesigning model architectures, practitioners should audit their training data for sequential bias. Curating or augmenting datasets to contain more independent sub‑tasks can unlock parallelism in existing diffusion pipelines.
• Simplified deployment: Since NAP does not require new layers or inference tricks, existing diffusion‑based generation services can adopt the approach by swapping in the curated dataset and adjusting the training schedule.

Limitations & Future Work

• Scope limited to math reasoning: The experiments focus on structured problem‑solving tasks; it remains unclear how NAP performs on open‑ended generation (e.g., storytelling, dialogue).
• Data preparation overhead: Curating independent reasoning trajectories can be labor‑intensive for domains lacking naturally modular examples. Automated trajectory extraction is an open challenge.
• Scaling to larger models: The study uses medium‑sized diffusion models; whether the same gains hold for billion‑parameter DLMs is yet to be tested.
• Future directions: The authors propose exploring curriculum learning that gradually increases parallelism, integrating NAP with multimodal diffusion models, and developing self‑supervised methods to discover parallelizable sub‑structures in raw text.

Authors

• Pengxiang Li
• Dilxat Muhtar
• Lu Yin
• Tianlong Chen
• Shiwei Liu

Paper Information

• arXiv ID: 2602.23225v1
• Categories: cs.CL, cs.AI
• Published: February 26, 2026
• PDF: Download PDF