掩码扩散模型的自适应并行采样串行深度：下界与调度策略

View PDF HTML (experimental)

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 $\log\log 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.

Comments:	45 pages. Revised version with a new title
Subjects:	Information Theory (cs.IT); Computation and Language (cs.CL)
Cite as:	arXiv:2608.25505 [cs.IT]
	(or arXiv:2608.25505v2 [cs.IT] for this version)
	https://doi.org/10.48550/arXiv.2608.25505 arXiv-issued DOI via DataCite

Submission history

From: Jian Lu [view email]
[v1] Wed, 26 Aug 2026 08:16:24 UTC (78 KB)
[v2] Tue, 20 Oct 2026 13:49:11 UTC (75 KB)