Schedule optimization for tau-leaping in masked discrete diffusion
Abstract
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 (εfact), 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 εfact for a fixed sampling budget. To do so, we establish an exact integral representation of εfact 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 εfact, while if ρ degenerates, schedule optimization can improve the asymptotic order. Examples based on stationary processes and exchangeable mixtures illustrate these regimes.
Related
- Minimax bounds for watermarked and masked recursive discrete distribution estimation
- Structured Masked Diffusion for Shared-Codebook Unsourced Random Access Decoding
- Representation-based Masked Diffusion Model
- Anytime Training with Schedule-Free Spectral Optimization
- Query-Efficient Rejection Sampling for Parallel Masked Diffusion
BibTeX
@misc{secchi2026schedule,
title = {{Schedule optimization for tau-leaping in masked discrete diffusion}},
author = {Cecilia Secchi and Giacomo Zanella},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.21960},
eprint = {2609.21960},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21960},
}
RIS
TY - UNPB
TI - Schedule optimization for tau-leaping in masked discrete diffusion
AU - Cecilia Secchi
AU - Giacomo Zanella
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2609.21960
UR - https://arxiv.org/abs/2609.21960
AB - 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 (ε_fact), 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 ε_fact for a fixed sampling budget. To do so, we establish an exact integral representation of ε_fact 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 ε_fact, while if ρ degenerates, schedule optimization can improve the asymptotic order. Examples based on stationary processes and exchangeable mixtures illustrate these regimes.
ER -