# Optimal Inference Schedules for Masked Diffusion Models

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Placed in Discrete and text diffusion, one of 14 directions in Diffusion models.
- Builds on 22 of its 38 references that are in the map.
- First posted on arXiv 6 Nov 2025.

## Placed in

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

## Builds on (most cited first, 22 of 22)

- [MaskGIT: Masked Generative Image Transformer](https://mlsanity.com/paper/2202.04200/) (2022)
- [Large Language Diffusion Models](https://mlsanity.com/paper/2502.09992/) (2025)
- [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)
- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization](https://mlsanity.com/paper/2308.03686/) (2023)
- [Mercury: Ultra-Fast Language Models Based on Diffusion](https://mlsanity.com/paper/2506.17298/) (2025)
- [Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions](https://mlsanity.com/paper/2211.01916/) (2022)
- [Convergence of score-based generative modeling for general data distributions](https://mlsanity.com/paper/2209.12381/) (2022)
- [A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Models](https://mlsanity.com/paper/2408.02320/) (2024)
- [KL Convergence Guarantees for Score diffusion models under minimal data assumptions](https://mlsanity.com/paper/2308.12240/) (2023)
- [Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms](https://mlsanity.com/paper/2502.00234/) (2025)
- [Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization](https://mlsanity.com/paper/2402.08095/) (2024)
- [ParallelBench: Understanding the Trade-offs of Parallel Decoding in Diffusion LLMs](https://mlsanity.com/paper/2510.04767/) (2025)
- [Breaking AR's Sampling Bottleneck: Provable Acceleration via Diffusion Language Models](https://mlsanity.com/paper/2505.21400/) (2025)
- [Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning](https://mlsanity.com/paper/1911.07357/) (2019)
- [Error Bounds and Optimal Schedules for Masked Diffusions with Factorized Approximations](https://mlsanity.com/paper/2510.25544/) (2025)
- [Parallel Sampling via Counting](https://mlsanity.com/paper/2408.09442/) (2024)
- [Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective](https://mlsanity.com/paper/1808.07226/) (2018)
- [Information-Theoretic Proofs for Diffusion Sampling](https://mlsanity.com/paper/2502.02305/) (2025)
- [Exponential random graphs behave like mixtures of stochastic block models](https://mlsanity.com/paper/1707.01227/) (2017)

## Built on by (most cited first, 25 of 25)

- [Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees](https://mlsanity.com/paper/2602.15008/) (2026)
- [Confidence-Based Decoding is Provably Efficient for Diffusion Language Models](https://mlsanity.com/paper/2603.22248/) (2026)
- [Corrective Diffusion Language Models](https://mlsanity.com/paper/2512.15596/) (2025)
- [Generation Order and Parallel Decoding in Masked Diffusion Models: An Information-Theoretic Perspective](https://mlsanity.com/paper/2602.00286/) (2026)
- [Adaptation to Intrinsic Dependence in Diffusion Language Models](https://mlsanity.com/paper/2602.20126/) (2026)
- [Sharp Convergence Rates for Masked Diffusion Models](https://mlsanity.com/paper/2602.22505/) (2026)
- [The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity](https://mlsanity.com/paper/2608.13520/) (2026)
- [Discrete-WAM: Unified Discrete Vision-Action Token Editing for World-Policy Learning](https://mlsanity.com/paper/2606.05645/) (2026)
- [Provably adaptive sampling with uniform and remasking discrete diffusion models](https://mlsanity.com/paper/2608.23554/) (2026)
- [Vocabulary-size-independent Convergence of Discrete Diffusion Models: adjoint equations induce the right space](https://mlsanity.com/paper/2605.17232/) (2026)
- [Diffusion Models Are Statistically Optimal for Learning Low-Dimensional Multi-Modal Distributions](https://mlsanity.com/paper/2605.30153/) (2026)
- [Discrete diffusion samplers and bridges: Off-policy algorithms and applications in latent spaces](https://mlsanity.com/paper/2602.05961/) (2026)
- [ConvergeFlow: Language Flow with Provable Convergence to Token Embeddings](https://mlsanity.com/paper/2608.23551/) (2026)
- [The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling](https://mlsanity.com/paper/2608.28949/) (2026)
- [Is Your Diffusion Sampler Actually Correct? A Sampler-Centric Evaluation of Discrete Diffusion Language Models](https://mlsanity.com/paper/2602.19619/) (2026)
- [Latent-DARM: Bridging Discrete Diffusion And Autoregressive Models For Reasoning](https://mlsanity.com/paper/2603.09184/) (2026)
- [Diffusion Models Adapt to Low-Dimensional Structure Under Flexible Coefficient Choices](https://mlsanity.com/paper/2606.23627/) (2026)
- [Conditional Total Correlation and the Serial Depth of Adaptive Parallel Sampling](https://mlsanity.com/paper/2608.25505/) (2026)
- [Unified Energy for Invariant and Independent Decoding in Diffusion Language Models](https://mlsanity.com/paper/2606.09159/) (2026)
- [One-step lowest-variance selection in a Gaussian random-field model motivated by masked diffusion: Total correlation and a square root collision threshold](https://mlsanity.com/paper/2607.17522/) (2026)
- [Schedule optimization for tau-leaping in masked discrete diffusion](https://mlsanity.com/paper/2609.21960/) (2026)
- [Unmask the State: When Does State Adaptation Matter for Masked Diffusion Language Models](https://mlsanity.com/paper/2609.33355/) (2026)
- [Simple Diffusion Language Models Are More Effective Few-Step Generators Than Reported](https://mlsanity.com/paper/2609.33947/) (2026)
- [Sample complexity bounds for categorical Markov random fields via Discrete Diffusions](https://mlsanity.com/paper/2610.02128/) (2026)
- [Training Parallel Speculative Draft Models by Directly Minimizing Expected Decoding Rounds](https://mlsanity.com/paper/2610.10411/) (2026)

## Abstract (arXiv)

A major bottleneck of standard auto-regressive large language models is that their inference process is inherently sequential, resulting in very long and costly inference times. To circumvent this, practitioners proposed a class of language models called diffusion language models, of which the masked diffusion model (MDM) is the most successful. The MDM is able to sample tokens out-of-order and, ostensibly, many tokens at once and in parallel. However, there is very limited rigorous understanding of how much parallel sampling these models can perform without noticeable degradation in their sampling performance. Prior work of Li and Cai obtained some preliminary bounds, but these are not tight for many natural classes of distributions. In this work, we give a new, exact characterization of the expected divergence between the true distribution and the sampled distribution, for any distribution and any unmasking schedule for the sampler, showing an elegant connection to the theory of univariate function approximation. By leveraging this connection, we then attain a number of novel lower and upper bounds for this problem. While the connection to function approximation in principle gives the optimal unmasking schedule for any distribution, we show that it is in general impossible to compete with it without strong a priori knowledge of the distribution, even in seemingly benign settings. However, we also demonstrate new upper bounds and new sampling schedules in terms of well-studied information-theoretic properties of the base distribution, namely, its total correlation and dual total correlation, which show that in some natural settings, one can sample in O(log n) steps without any visible loss in performance, where n is the total sequence length.