Research map / Image generation / Fast diffusion sampling
Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planning
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.
Proposes MGDM, a discrete diffusion LM with token-level adaptive reweighting, showing it beats autoregressive and prior diffusion models on Countdown, Sudoku, and SAT without search.
Problem
Autoregressive language models struggle with complex reasoning and long-horizon planning because some subgoals (subgoal imbalance) are hard to learn left-to-right.
Approach
Discrete absorbing-state diffusion trained with a multi-granularity loss: sequence-level timestep reweighting plus a token-level adaptive weight that emphasizes hard tokens, with easy-first TopK decoding at inference.
Key results
- MGDM (85M) reaches 91.5% on Countdown 4 vs 45.8% for 85M GPT-2 autoregressive trained from scratch.
- MGDM solves 100% of Sudoku test problems with a 6M model, while LLaMA-13B reaches 32.9%.
- On Game of 24, MGDM achieves 76.0% accuracy vs 74.0% for GPT-4 ToT, using about 186x fewer tokens.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MGDM instead of the strongest reported autoregressive model | Countdown CD 4 · Countdown CD 4 | accuracy: 51.1 -> 91.5 | Helped |
| Use MGDM instead of the strongest prior diffusion baseline | Countdown CD 4 · Countdown CD 4 | accuracy: 87.0 -> 91.5 | Helped |
| Use MGDM instead of AR | Game of 24 · Game of 24 | accuracy: 18.8 -> 76.0 | Helped |
| Use MGDM instead of GPT-4 ToT | Game of 24 · Game of 24 | token cost: x186 -> x1 | Helped |
| Use MGDM instead of LLaMA 13B | Sudoku · Sudoku | accuracy: 32.9 -> 100% | Helped |
| Add token reweighting to AR (ablation) | AR on minimal planning · Minimal planning, PD 2 | accuracy: 51.1 -> 52.1 | Helped |
| Add token reweighting to AR (ablation) | AR on minimal planning · Minimal planning, PD 3 | accuracy: 46.9 -> 51.5 | Helped |
| Add token reweighting to AR (ablation) | AR on minimal planning · Minimal planning, PD 4 | accuracy: 52.0 -> 50.3 | Hurt |
| Add token reweighting to AR (ablation) | AR on minimal planning · Minimal planning, PD 5 | accuracy: 49.9 -> 51.9 | Helped |
| Increase MGDM model size from 85M to 303M with 500k training data (ablation) | MGDM on Countdown CD 4 · Countdown CD 4 | accuracy: 91.5 -> 88.3 | Hurt |
| Increase training data from 500k to 1M for the 303M AR model (ablation) | AR on Countdown CD 4 · Countdown CD 4 | accuracy: 41.3 -> 53.3 | Helped |
| Increase training data from 500k to 1M for the 303M MGDM model (ablation) | MGDM on Countdown CD 4 · Countdown CD 4 | accuracy: 88.3 -> 95.6 | Helped |
Surprising findings
- A 6M-parameter diffusion model outperforms a 303M GPT-2 and a 13B pretrained LLaMA on Countdown.
- Applying the same token reweighting to autoregressive models does not fix hard subgoals (PD>1 stays near 50%).
Limitations
- Experiments use small GPT-2-style models trained from scratch on synthetic or narrow tasks.
- Diffusion accuracy degrades with more timesteps trade-off; speed-accuracy trade-off requires tuning.
- Comparison with GPT-4 borrows numbers from prior work, not re-run under identical settings.
Experimental setup
Datasets: Countdown (500k generated problems) Sudoku (1M solved games, first 100k used) random 3-SAT (generated) Game of 24 test set synthetic minimal planning task
Benchmarks: Countdown 3/4/5 Sudoku 3-SAT 5/7/9 variables Game of 24 minimal planning task
Metrics: accuracy tokens consumed samples per second
Baselines: GPT-2 Scratch LLaMA Stream-of-Search VDM D3PM RDM GPT-4 IO GPT-4 CoT GPT-4 CoT-SC GPT-4 ToT
Builds on: D3PM RDM GPT-2 Stream-of-Search
Closest papers by meaning
- Discrete Diffusion Models Exploit Asymmetry to Solve Lookahead Planning Tasks (NeurIPS 2026 · similarity 0.90)
- Beyond Autoregression: Fast LLMs via Self-Distillation Through Time (ICLR 2025 · similarity 0.89)
- Diffusion Beats Autoregressive in Data-Constrained Settings (NeurIPS 2025 · similarity 0.88)
- d1: Scaling Reasoning in Diffusion Large Language Models via Reinforcement Learning (NeurIPS 2025 · similarity 0.87)
- Diffusion of Thought: Chain-of-Thought Reasoning in Diffusion Language Models (NeurIPS 2024 · similarity 0.87)
- Scaling Diffusion Language Models via Adaptation from Autoregressive Models (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.