Serial Depth of Adaptive Parallel Sampling: Lower Bounds and Schedules for Masked Diffusion Models
Abstract
Masked diffusion models generate sequences in rounds, predicting several masked positions at once. Fewer rounds can accelerate decoding, but sampling positions independently can lose their dependence and bias the output. How few rounds suffice for a prescribed error budget? Beyond error bounds for individual decoding rules, we study sharp lower bounds on the number of rounds required for a given target distribution. We introduce serial depth: the minimum number of rounds, averaged over target sequences, needed to meet a forward Kullback-Leibler error budget. With exact conditional probabilities, we prove these bounds for all deterministic rules that may adapt to generated values and construct matching schedules for several distribution families, with depths ranging from loglog n to linear in sequence length n. To narrow the gap to trained models, we show that these lower bounds remain valid for learned predictors and give sufficient accuracy conditions on visited contexts for schedules to retain their error guarantees. On two pretrained models across five text domains, a schedule suggested by the theory achieves higher average log-likelihood on held-out text in five rounds than random selection in eight. A preregistered confirmation study certifies a relative improvement on independent dialogue data.
Related
- Query-Efficient Rejection Sampling for Parallel Masked Diffusion
- Lower Bounds for Parallel Diffusion Sampling
- Adaptive Reparametrized Time for Score-Based Diffusion Sampling
- The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity
- Randomization Beyond Deterministic Adaptivity in Parallel Sampling
BibTeX
@misc{wen2026serial,
title = {{Serial Depth of Adaptive Parallel Sampling: Lower Bounds and Schedules for Masked Diffusion Models}},
author = {Chuling Wen and Weijie Liang and Jian Lu and Zhouchen Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.25505},
eprint = {2608.25505},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.25505},
}
RIS
TY - UNPB
TI - Serial Depth of Adaptive Parallel Sampling: Lower Bounds and Schedules for Masked Diffusion Models
AU - Chuling Wen
AU - Weijie Liang
AU - Jian Lu
AU - Zhouchen Lin
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2608.25505
UR - https://arxiv.org/abs/2608.25505
AB - Masked diffusion models generate sequences in rounds, predicting several masked positions at once. Fewer rounds can accelerate decoding, but sampling positions independently can lose their dependence and bias the output. How few rounds suffice for a prescribed error budget? Beyond error bounds for individual decoding rules, we study sharp lower bounds on the number of rounds required for a given target distribution. We introduce serial depth: the minimum number of rounds, averaged over target sequences, needed to meet a forward Kullback-Leibler error budget. With exact conditional probabilities, we prove these bounds for all deterministic rules that may adapt to generated values and construct matching schedules for several distribution families, with depths ranging from loglog n to linear in sequence length n. To narrow the gap to trained models, we show that these lower bounds remain valid for learned predictors and give sufficient accuracy conditions on visited contexts for schedules to retain their error guarantees. On two pretrained models across five text domains, a schedule suggested by the theory achieves higher average log-likelihood on held-out text in five rounds than random selection in eight. A preregistered confirmation study certifies a relative improvement on independent dialogue data.
ER -