# Schedule optimization for tau-leaping in masked discrete diffusion

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 22 of its 29 references that are in the map.
- First posted on arXiv 18 Sep 2026.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

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

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [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)
- [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)
- [Your Absorbing Discrete Diffusion Secretly Models the Conditional Distributions of Clean Data](https://mlsanity.com/paper/2406.03736/) (2024)
- [Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions](https://mlsanity.com/paper/2502.06768/) (2025)
- [Masked Diffusion Models are Secretly Time-Agnostic Masked Models and Exploit Inaccurate Categorical Sampling](https://mlsanity.com/paper/2409.02908/) (2024)
- [Accelerated Sampling from Masked Diffusion Models via Entropy Bounded Unmasking](https://mlsanity.com/paper/2505.24857/) (2025)
- [Plan for Speed: Dilated Scheduling for Masked Diffusion Language Models](https://mlsanity.com/paper/2506.19037/) (2025)
- [Optimal Inference Schedules for Masked Diffusion Models](https://mlsanity.com/paper/2511.04647/) (2025)
- [Breaking AR's Sampling Bottleneck: Provable Acceleration via Diffusion Language Models](https://mlsanity.com/paper/2505.21400/) (2025)
- [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)
- [Error Bounds and Optimal Schedules for Masked Diffusions with Factorized Approximations](https://mlsanity.com/paper/2510.25544/) (2025)
- [Adaptation to Intrinsic Dependence in Diffusion Language Models](https://mlsanity.com/paper/2602.20126/) (2026)
- [The Cosine Schedule is Fisher-Rao-Optimal for Masked Discrete Diffusion Models](https://mlsanity.com/paper/2508.04884/) (2025)
- [Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamics](https://mlsanity.com/paper/2512.00580/) (2025)
- [The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity](https://mlsanity.com/paper/2608.13520/) (2026)
- [Improved Sampling Schedules for Discrete Diffusion Models](https://mlsanity.com/paper/2602.06849/) (2026)

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

- [Transformer-Based Masked Diffusion Models Provably Learn Distributions with Latent Structure](https://mlsanity.com/paper/2610.12544/) (2026)
- [KL Before and After Mixing: A Round-Complexity Separation in Parallel Sampling](https://mlsanity.com/paper/2610.13924/) (2026)

## Abstract (arXiv)

Masked diffusions are popular generative models for discrete distributions. Unlike standard autoregressive sampling, they reveal several coordinates in parallel, approximating each block's joint conditional law by a product of one-coordinate conditionals. The resulting procedure, usually called tau-leaping, reduces computational cost but introduces a factorization error (varepsilonfact), even with perfectly learned predictors. We study the resulting tradeoff between generative accuracy and computational cost, focusing on how to choose a denoising schedule to minimize varepsilonfact for a fixed sampling budget. To do so, we establish an exact integral representation of varepsilonfact separating the schedule from the target's dependence structure, summarized by a dependence density ρ. This representation yields recursive stationarity equations for optimal schedules and allows us to quantify how estimation errors in ρ affect schedule selection. As the dimension N and sampling budget grow, we characterize the optimal schedule and quantify the cost of random block sizes relative to a deterministic planner. We highlight a fundamental dichotomy: if ρ converges uniformly to a strictly positive continuous profile as N→∞, schedule optimization can only improve the leading constant of varepsilonfact, while if ρ degenerates, schedule optimization can improve the asymptotic order. Examples based on stationary processes and exchangeable mixtures illustrate these regimes.