# Error Bounds and Optimal Schedules for Masked Diffusions with Factorized Approximations

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

## Key facts

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

## Placed in

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

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

- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Simple and Effective Masked Diffusion Language Models](https://mlsanity.com/paper/2406.07524/) (2024)
- [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)
- [Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions](https://mlsanity.com/paper/2502.06768/) (2025)
- [Remasking Discrete Diffusion Models with Inference-Time Scaling](https://mlsanity.com/paper/2503.00307/) (2025)
- [Accelerated Sampling from Masked Diffusion Models via Entropy Bounded Unmasking](https://mlsanity.com/paper/2505.24857/) (2025)
- [Path Planning for Masked Diffusion Model Sampling](https://mlsanity.com/paper/2502.03540/) (2025)
- [A Deep and Tractable Density Estimator](https://mlsanity.com/paper/1310.1757/) (2013)
- [Think While You Generate: Discrete Diffusion with Planned Denoising](https://mlsanity.com/paper/2410.06264/) (2024)
- [Informed Correctors for Discrete Diffusion Models](https://mlsanity.com/paper/2407.21243/) (2024)
- [textitJump Your Steps: Optimizing Sampling Schedule of Discrete Diffusion Models](https://mlsanity.com/paper/2410.07761/) (2024)
- [Plan for Speed: Dilated Scheduling for Masked Diffusion Language Models](https://mlsanity.com/paper/2506.19037/) (2025)
- [Breaking AR's Sampling Bottleneck: Provable Acceleration via Diffusion Language Models](https://mlsanity.com/paper/2505.21400/) (2025)
- [The Cosine Schedule is Fisher-Rao-Optimal for Masked Discrete Diffusion Models](https://mlsanity.com/paper/2508.04884/) (2025)

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

- [Optimal Inference Schedules for Masked Diffusion Models](https://mlsanity.com/paper/2511.04647/) (2025)
- [Confidence-Based Decoding is Provably Efficient for Diffusion Language Models](https://mlsanity.com/paper/2603.22248/) (2026)
- [Adaptation to Intrinsic Dependence in Diffusion Language Models](https://mlsanity.com/paper/2602.20126/) (2026)
- [Discrete-WAM: Unified Discrete Vision-Action Token Editing for World-Policy Learning](https://mlsanity.com/paper/2606.05645/) (2026)
- [ConvergeFlow: Language Flow with Provable Convergence to Token Embeddings](https://mlsanity.com/paper/2608.23551/) (2026)
- [A Mathematical Introduction to Diffusion Models](https://mlsanity.com/paper/2607.01693/) (2026)
- [Conditional Total Correlation and the Serial Depth of Adaptive Parallel Sampling](https://mlsanity.com/paper/2608.25505/) (2026)
- [Parallelism, critical windows, and separations among diffusion language models](https://mlsanity.com/paper/2609.20539/) (2026)
- [Factorization-Error-Free Discrete Diffusion Language Model via Speculative Decoding](https://mlsanity.com/paper/2605.14305/) (2026)
- [Unified Energy for Invariant and Independent Decoding in Diffusion Language Models](https://mlsanity.com/paper/2606.09159/) (2026)
- [When Can You Correct Distribution Drift in Temporal Graph Generation? A Sharpening--Drift Tension and an Impossibility for Observation-Based Correction](https://mlsanity.com/paper/2607.24662/) (2026)
- [Schedule optimization for tau-leaping in masked discrete diffusion](https://mlsanity.com/paper/2609.21960/) (2026)
- [Simple Diffusion Language Models Are More Effective Few-Step Generators Than Reported](https://mlsanity.com/paper/2609.33947/) (2026)
- [Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure](https://mlsanity.com/paper/2609.37841/) (2026)

## Abstract (arXiv)

Recently proposed generative models for discrete data, such as Masked Diffusion Models (MDMs), exploit conditional independence approximations to reduce the computational cost of popular Auto-Regressive Models (ARMs), at the price of some bias in the sampling distribution. We study the resulting computation-vs-accuracy trade-off, providing general error bounds (in relative entropy) that depend only on the average number of tokens generated per iteration and are independent of the data dimensionality (i.e. sequence length), thus supporting the empirical success of MDMs. We then investigate the gain obtained by using non-constant schedule sizes (i.e. varying the number of unmasked tokens during the generation process) and identify the optimal schedule as a function of a so-called information profile of the data distribution, thus allowing for a principled optimization of schedule sizes. We define methods directly as sampling algorithms and do not use classical derivations as time-reversed diffusion processes, leading us to simple and transparent proofs.