Research map / Image generation / Fast diffusion sampling

Discrete Diffusion Models Exploit Asymmetry to Solve Lookahead Planning Tasks

NeurIPS 2026 · Image generation › Fast diffusion sampling · approach: Masked diffusion language model decoding · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that both autoregressive transformers and discrete diffusion LMs can solve the Star-Path lookahead task with perfect accuracy, and that diffusion models sidestep high-order lookahead by decoding the path backwards from the leaf, needing far fewer training examples and shallower models.

Problem

Prior work reported that autoregressive LMs fail at multi-step lookahead planning on the Star-Path graph task, while discrete diffusion LMs are claimed to plan better; the mechanisms behind this gap are not understood.

Approach

Identifies a forward/reverse asymmetry in Star-Path: forward generation needs high-order lookahead at junctions while reverse generation is deterministic. Non-autoregressive diffusion models can exploit this by unmasking target-end tokens first and decoding backwards with first-order transitions, whereas AR models must learn the high-order mechanism. Also shows that training with gradients on the

Key results

• Both AR and NAR models reach perfect (>0.95) exact-match accuracy on Star-Path when gradients flow through the graph prefix and training uses up to 50M examples.
• NAR (diffusion) models converge with substantially fewer training examples than AR models, with the gap widening as associative connections grow.
• When the forward-only lookahead is removed (the 1st-order reverse task), AR and NAR converge at similar rates, and when only the junction choice is required the NAR advantage disappears.

Surprising findings

• AR transformers can learn Star-Path to perfect accuracy, contrary to prior reports that they fundamentally fail, when prefix tokens are included in the loss.
• Diffusion models decode the path backwards from the target leaf, an anti-causal order impossible for standard AR models.

Limitations

• Evaluated only on a synthetic minimal graph task with a small GPT-2-sized model (d_model=384, 12 layers).
• Unclear whether NAR models have inherently greater planning capacity or only exploit an easier computational path.
• Some graph configurations did not converge even at 50M examples for AR models.

Experimental setup

Datasets: synthetic Star-Path graphs G(d,l)

Benchmarks: Star-Path held-out test sets G(d,l)

Metrics: exact match accuracy training examples to convergence

Baselines: conditional-training AR model (prefix masked) AR model trained on original Star-Path

Builds on: Star-Path task DDiT GPT-2 flow matching

Closest papers by meaning

• ALPINE: Unveiling The Planning Capability of Autoregressive Learning in Language Models (NeurIPS 2024 · similarity 0.90)
• Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planning (ICLR 2025 · similarity 0.90)
• Diffusion Beats Autoregressive in Data-Constrained Settings (NeurIPS 2025 · similarity 0.87)
• Towards an Understanding of Stepwise Inference in Transformers: A Synthetic Graph Navigation Model (ICML 2024 · similarity 0.87)
• From Next-Token to Next-Block: A Principled Adaptation Path for Diffusion LLMs (NeurIPS 2026 · similarity 0.87)
• Breaking AR’s Sampling Bottleneck: Provable Acceleration via Diffusion Language Models (NeurIPS 2025 · similarity 0.87)