The Price of Not Planning: Parallel Sampling Depth Peaks at the Reconstruction Threshold
Organizations: Shenzhen Key Laboratory of Advanced Machine Learning and Applications, School of Mathematical Sciences, Shenzhen University, Shenzhen 518060, China · National Center for Applied Mathematics Shenzhen (NCAMS), Shenzhen 518055, China
Abstract
Masked diffusion models sample the tokens of one round independently. Planned decoders first generate a coarse plan, then fill in the tokens in parallel. We ask when a plan saves rounds, how many it saves, and how fine it must be. We study this on broadcast trees: the leaves are the tokens, the internal nodes are the plan, and the edge correlation sets how strongly tokens depend on the plan. Errors are measured by the forward Kullback-Leibler divergence , and the lower bounds hold for every deterministic value-adaptive rule, also with learned conditionals. We show that a decoder without the plan needs of order rounds below the reconstruction threshold, where rises to at the threshold, and that the exponent stays below above it (binary channel: ). With the plan, rounds suffice. In the binary model below the threshold, a plan with units of tokens needs of order rounds, so it gives logarithmic depth exactly when is logarithmic. A plan therefore helps most near the threshold, and only if its units are small. Exact divergence computations in the Gaussian model with up to leaves confirm these exponents below the threshold.
Figures & tables
| Broadcast model | Plan-then-fill decoding |
|---|---|
| leaves | output tokens |
| internal nodes | plan: outline, latent code or coarse scales |
| leaves below a finest plan node, | size of a plan unit |
| edge correlation or | how strongly the tokens depend on the plan |
| rule on the leaves | masked diffusion sampler without a plan |
| rule on all nodes | decoder that generates the plan first |
| regime | proved depth bounds | schedule attaining the upper bound | source |
|---|---|---|---|
| leaves only, (both models) | one leaf of every subtree of height per round, rounds | Theorems 6 , 7 | |
| leaves only, Gaussian, | as above | Theorem 7 | |
| leaves only, Gaussian, | , both exponents , equal when | sparse leaves first, then denser ones, in stages | Theorem 7 |
| leaves only, binary, , | for every , | as above | Theorem 8 |
| all nodes (plan generated) | ; (binary) | one level of the tree per round | Theorem 10 |
| plan down to subtrees of leaves, binary, | plan level by level, then the first schedule inside each subtree | Theorem 11 |
| measured exponent | at | ||||
|---|---|---|---|---|---|
| 0.40 | 0.189 | 0.180 | 2.8 | 1.25 | 1.26 |
| 0.50 | 0.250 | 0.245 | 4.5 | 1.38 | 1.35 |
| 0.60 | 0.339 | 0.327 | 9.0 | 1.43 | 1.50 |
| 0.65 | 0.402 | 0.336 | 14.5 | 1.67 | 1.62 |
| 0.70 | 0.486 | 0.385 | 25.6 | 1.64 | 1.80 |
| measured exponent | at | ||||
|---|---|---|---|---|---|
| stride | multistage | stride | multistage | ||
| 0.72 | 0.499 | 0.45 (0.03) | 0.44 (0.05) | 39.6 | 28.9 |
| 0.75 | 0.489 | 0.52 (0.02) | 0.39 (0.02) | 70.7 | 34.9 |
| 0.80 | 0.447 | 0.62 (0.03) | 0.48 (0.03) | 184 | 60.6 |
| 0.85 | 0.379 | 0.70 (0.01) | 0.48 (0.04) | 393 | 81.4 |
| 0.90 | 0.307 | 0.80 (0.05) | 0.45 (0.05) | 1180 | 65.1 |
| stride | multistage | random batches | confidence | |
|---|---|---|---|---|
| 0.40 | 2.8 | 3.2 | 286 | |
| 0.60 | 9.0 | 8.8 | 1124 | |
| 0.7071 | 28.6 | 23.8 | 1540 | |
| 0.80 | 99.5 | 39.9 | ||
| 0.90 | 731 | 55.7 |
| no plan | plan with units of leaves | ||||||
| 0.60 | 8.8 | 11.7 | 13.7 | 14.6 | 13.3 | 12.2 | 13.0 |
| 0.7071 | 23.8 | 29.9 | 27.5 | 20.7 | 13.5 | 12.3 | 13.0 |
| 0.80 | 39.9 | 72.4 | 44.7 | 23.9 | 13.7 | 12.3 | 13.0 |
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
| part | range of | intervals | boxes | result |
|---|---|---|---|---|
| 76 | all verified; smallest lower bound | |||
| (V0) and linear bounds | 43 | all verified; smallest (V0) margin | ||
| (V1), recomputed | 43 | – | is ( ), ( ), ( ), ( ) |