cs.LGNov 16, 2026

The Price of Not Planning: Parallel Sampling Depth Peaks at the Reconstruction Threshold

Authors: Chuling Wen, Weijie Liang, Jian Lu

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 ε\varepsilon, 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 min⁡{n,(n/ε)α}\min\{n,(n/\varepsilon)^α\} rounds below the reconstruction threshold, where α=log⁡b/(4log⁡(1/θ))α=\log b/(4\log(1/θ)) rises to 1/21/2 at the threshold, and that the exponent stays below 1/21/2 above it (binary channel: 0.02≤θ≤0.980.02\leθ\le0.98). With the plan, log⁡bn+1\log_b n+1 rounds suffice. In the binary model below the threshold, a plan with units of mm tokens needs of order log⁡b(n/m)+min⁡{m,(n/ε)α}\log_b(n/m)+\min\{m,(n/\varepsilon)^α\} rounds, so it gives logarithmic depth exactly when mm 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 2202^{20} leaves confirm these exponents below the threshold.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Serial Depth of Adaptive Parallel Sampling: Lower Bounds and Schedules for Masked Diffusion Models

    Aug 26, 2026Chuling Wen, Weijie Liang, Jian Lu +1Adaptive SamplingParallel Decoding

  2. When Should Diffusion Language Models Reconsider Their Commitments?

    Nov 8, 2026Haoyang Zheng, Yidong Ouyang, Blake Jianhang Chen +5Diffusion Language Model DecodingParallel Decoding for Diffusion Language Models

  3. Query-Efficient Rejection Sampling for Parallel Masked Diffusion

    Oct 15, 2026Shiyuan Zhang, Xuheng Li, Qiwei Di +1Parallel Decoding for Diffusion Language ModelsDiffusion Sampling