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

Aug 26, 2026

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

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\log\log n to linear in sequence length nn. 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.
Nov 8, 2026

When Should Diffusion Language Models Reconsider Their Commitments?

Masked Diffusion Models (MDMs) are well known for fast text generation via parallel decoding. However, independent parallel sampling can commit to inconsistent predictions, and less is known about how to selectively revise these early token commitments. In this work, we introduce P‾\underline{\mathrm{P}}lanned U‾\underline{\mathrm{U}}nmasking-and-R‾\underline{\mathrm{R}}evision Joint L‾\underline{\mathrm{L}}earning (PURL) for MDMs, a training-based framework that seamlessly unifies parallel generation with selective token revision. We derive a normalized joint transition whose likelihood factorizes into edit selection, unmask selection, and token prediction. These components are trained jointly on partially masked sequences constructed according to the model's own unmasking policy. During inference, all three decisions are supported by a single shared forward pass, enabling the model to decode masked tokens and revise noisy tokens. Across logic puzzles, mathematical reasoning, and code generation, PURL improves accuracy at matched unmask budgets, with relative gains up to 47.4% accuracy improvement and up to an 8×8\times reduction in scheduled decoding rounds. Beyond these gains, our analysis further reveals general principles of revisable decoding: token edits become more effective as context accumulates; early edits can steer unfinished trajectories, whereas later edits tend to remain localized; and effective edits therefore depend on both calibrating when to intervene and learning where and how to revise. Together, these suggest that effective parallel generation depends not on revising more tokens, but on making the right commitments revisable at the right time.
Oct 15, 2026

Query-Efficient Rejection Sampling for Parallel Masked Diffusion

Masked diffusion models (MDMs) accelerate generation by unmasking multiple tokens in parallel, but sampling these tokens independently ignores their correlations and biases the output. Anari et al. (2026) corrected this bias with rejection sampling, decomposing the log acceptance probability into a sum of token-level terms, but the evaluation requires one score query per unmasked token. We propose the Single-Increment Rejection Sampler (SIRS), which provides an estimate of the log acceptance probability from a single randomly sampled increment at the cost of one query. SIRS then converts a Poisson number of clipped estimates into accept/reject decisions through a Bernoulli factory adapted from Chen et al. (2026). Since each query returns the conditionals of all remaining tokens in the block, we further Rao-Blackwellize each increment by averaging over these tokens at no extra cost, thereby reducing clipping. We show that the KL-divergence between the data distribution and the SIRS output is bounded by a clipping term plus the model's training error. With exact scores, parallel decoding pays the full within-block dependence, whereas SIRS pays only the part beyond the clipping range.