# Path Planning for Masked Diffusion Model Sampling

arXiv: https://arxiv.org/abs/2502.03540 · HTML: https://mlsanity.com/paper/2502.03540/

## Key facts

- Cited by 80 papers in the map (data through 14 Oct 2026).
- Placed in Discrete and text diffusion, one of 14 directions in Diffusion models.
- Builds on 42 of its 64 references that are in the map.
- First posted on arXiv 5 Feb 2025.

## Placed in

- Diffusion models / [Discrete and text diffusion](https://mlsanity.com/diffusion/discrete-and-text-diffusion/)

## Builds on (most cited first, 30 of 42)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [ALBERT: A Lite BERT for Self-supervised Learning of Language Representations](https://mlsanity.com/paper/1909.11942/) (2019)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [MaskGIT: Masked Generative Image Transformer](https://mlsanity.com/paper/2202.04200/) (2022)
- [The LAMBADA dataset: Word prediction requiring a broad discourse context](https://mlsanity.com/paper/1606.06031/) (2016)
- [Simple and Effective Masked Diffusion Language Models](https://mlsanity.com/paper/2406.07524/) (2024)
- [Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution](https://mlsanity.com/paper/2310.16834/) (2023)
- [Simplified and Generalized Masked Diffusion for Discrete Data](https://mlsanity.com/paper/2406.04329/) (2024)
- [A Continuous Time Framework for Discrete Denoising Models](https://mlsanity.com/paper/2205.14987/) (2022)
- [A Corpus and Evaluation Framework for Deeper Understanding of Commonsense Stories](https://mlsanity.com/paper/1604.01696/) (2016)
- [The Reversal Curse: LLMs trained on "A is B" fail to learn "B is A"](https://mlsanity.com/paper/2309.12288/) (2023)
- [Your Absorbing Discrete Diffusion Secretly Models the Conditional Distributions of Clean Data](https://mlsanity.com/paper/2406.03736/) (2024)
- [Discrete Flow Matching](https://mlsanity.com/paper/2407.15595/) (2024)
- [Generative Flows on Discrete State-Spaces: Enabling Multimodal Flows with Applications to Protein Co-Design](https://mlsanity.com/paper/2402.04997/) (2024)
- [Scaling Diffusion Language Models via Adaptation from Autoregressive Models](https://mlsanity.com/paper/2410.17891/) (2024)
- [Efficient Training of Language Models to Fill in the Middle](https://mlsanity.com/paper/2207.14255/) (2022)
- [Masked Diffusion Models are Secretly Time-Agnostic Masked Models and Exploit Inaccurate Categorical Sampling](https://mlsanity.com/paper/2409.02908/) (2024)
- [Scaling up Masked Diffusion Models on Text](https://mlsanity.com/paper/2410.18514/) (2024)
- [Lessons from the Trenches on Reproducible Evaluation of Language Models](https://mlsanity.com/paper/2405.14782/) (2024)
- [Score-based Continuous-time Discrete Diffusion Models](https://mlsanity.com/paper/2211.16750/) (2022)
- [ProGen2: Exploring the Boundaries of Protein Language Models](https://mlsanity.com/paper/2206.13517/) (2022)
- [Simple Guidance Mechanisms for Discrete Diffusion Models](https://mlsanity.com/paper/2412.10193/) (2024)
- [A Reparameterized Discrete Diffusion Model for Text Generation](https://mlsanity.com/paper/2302.05737/) (2023)
- [Likelihood-Based Diffusion Language Models](https://mlsanity.com/paper/2305.18619/) (2023)
- [Diffusion Language Models Are Versatile Protein Learners](https://mlsanity.com/paper/2402.18567/) (2024)

## Built on by (most cited first, 30 of 80)

- [Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions](https://mlsanity.com/paper/2502.06768/) (2025)
- [Accelerated Sampling from Masked Diffusion Models via Entropy Bounded Unmasking](https://mlsanity.com/paper/2505.24857/) (2025)
- [Any-Order Flexible Length Masked Diffusion](https://mlsanity.com/paper/2509.01025/) (2025)
- [KLASS: KL-Guided Fast Inference in Masked Diffusion Models](https://mlsanity.com/paper/2511.05664/) (2025)
- [Fine-Tuning Masked Diffusion for Provable Self-Correction](https://mlsanity.com/paper/2510.01384/) (2025)
- [Plan for Speed: Dilated Scheduling for Masked Diffusion Language Models](https://mlsanity.com/paper/2506.19037/) (2025)
- [A Survey on Parallel Text Generation: From Parallel Decoding to Diffusion Language Models](https://mlsanity.com/paper/2508.08712/) (2025)
- [From Bits to Rounds: Parallel Decoding with Exploration for Diffusion Language Models](https://mlsanity.com/paper/2511.21103/) (2025)
- [DiFFPO: Training Diffusion LLMs to Reason Fast and Furious via Reinforcement Learning](https://mlsanity.com/paper/2510.02212/) (2025)
- [The Flexibility Trap: Rethinking the Value of Arbitrary Order in Diffusion Language Models](https://mlsanity.com/paper/2601.15165/) (2026)
- [Confidence-Based Decoding is Provably Efficient for Diffusion Language Models](https://mlsanity.com/paper/2603.22248/) (2026)
- [Unifying Autoregressive and Diffusion-Based Sequence Generation](https://mlsanity.com/paper/2504.06416/) (2025)
- [Why Masking Diffusion Works: Condition on the Jump Schedule for Improved Discrete Diffusion](https://mlsanity.com/paper/2506.08316/) (2025)
- [Planner Aware Path Learning in Diffusion Language Models Training](https://mlsanity.com/paper/2509.23405/) (2025)
- [Error Bounds and Optimal Schedules for Masked Diffusions with Factorized Approximations](https://mlsanity.com/paper/2510.25544/) (2025)
- [CreditDecoding: Accelerating Parallel Decoding in Diffusion Large Language Models with Trace Credit](https://mlsanity.com/paper/2510.06133/) (2025)
- [Parallel Sampling from Masked Diffusion Models via Conditional Independence Testing](https://mlsanity.com/paper/2510.21961/) (2025)
- [Learn from Your Mistakes: Self-Correcting Masked Diffusion Models](https://mlsanity.com/paper/2602.11590/) (2026)
- [Self-Speculative Masked Diffusions](https://mlsanity.com/paper/2510.03929/) (2025)
- [Why Diffusion Language Models Struggle with Truly Parallel (Non-Autoregressive) Decoding?](https://mlsanity.com/paper/2602.23225/) (2026)
- [Simple and Critical Iterative Denoising: A Recasting of Discrete Diffusion in Graph Generation](https://mlsanity.com/paper/2503.21592/) (2025)
- [Enabling Approximate Joint Sampling in Diffusion LMs](https://mlsanity.com/paper/2509.22738/) (2025)
- [Demystifying MaskGIT Sampler and Beyond: Adaptive Order Selection in Masked Diffusion](https://mlsanity.com/paper/2510.04525/) (2025)
- [dUltra: Ultra-Fast Diffusion Language Models via Reinforcement Learning](https://mlsanity.com/paper/2512.21446/) (2025)
- [Generation Order and Parallel Decoding in Masked Diffusion Models: An Information-Theoretic Perspective](https://mlsanity.com/paper/2602.00286/) (2026)
- [CORE: Context-Robust Remasking for Diffusion Language Models](https://mlsanity.com/paper/2602.04096/) (2026)
- [Stop Training for the Worst: Progressive Unmasking Accelerates Masked Diffusion Training](https://mlsanity.com/paper/2602.10314/) (2026)
- [Where-to-Unmask: Ground-Truth-Guided Unmasking Order Learning for Masked Diffusion Language Models](https://mlsanity.com/paper/2602.09501/) (2026)
- [DUEL: Exact Likelihood for Masked Diffusion via Deterministic Unmasking](https://mlsanity.com/paper/2603.01367/) (2026)
- [All-atom inverse protein folding through discrete flow matching](https://mlsanity.com/paper/2507.14156/) (2025)

## Abstract (arXiv)

Any order generation of discrete data using masked diffusion models (MDMs) offers a compelling alternative to traditional autoregressive models, especially in domains that lack a natural causal ordering of data. However, current popular MDMs depart from their successful continuous diffusion model counterparts with simplified masked inference wherein unmasked tokens cannot be iteratively refined -- even if there is a mistake. In this paper, we extract the full power of MDMs by introducing a novel inference sampling strategy termed Path Planning (P2) that decomposes each generation step into two sub-stages: planning and denoising. Under P2, the planner at every step selects appropriate tokens that are marked to be updated, which can then be sampled using the denoiser. We demonstrate that P2 generalizes all existing sampling strategies for MDMs and critically enhances generative quality through the new capability of refining and updating existing unmasked tokens. We theoretically prove that P2 establishes a (new) expanded evidence lower bound (ELBO) on the log marginal likelihood of data. We instantiate P2 with a family of planners including: 1.) Self-Planning, 2.) BERT-Planning, and 3.) Trained-Planning with a learned planner leading to SOTA generative performance for MDMs on a suite of domains. Specifically, solely using P2 inference, we observe relative improvements of 22% in protein sequence foldability, 8% in RNA sequence pLDDT, 4% in math reasoning, 68% in story generation (ROUGE score), and 33% in code generation for the challenging pass@1 metric.