acceptodds
Under review as a conference paper at ICLR 2027

Generation Order and Parallel Decoding in Masked Diffusion Models: An Information-Theoretic Perspective

Abstract

Masked diffusion models (MDMs) can accelerate sequence generation by decoding multiple positions in parallel, but two distributional questions remain central: how generation order interacts with model error, and what sampling bias is introduced by parallel factorization. We develop an information-theoretic framework separating order sensitivity from parallelization bias. Our analysis yields three insights. First, local conditional errors are evaluated under model-induced rollouts, so early mistakes can alter the contexts of later predictions. Second, factorized parallel decoding can produce individually likely but jointly implausible samples even with exact marginal predictions; forward KL, reverse KL, and incoherence reveal different aspects of this error. Third, exact correction by fixed whole-block rejection has expected proposal cost at least exponential in conditional total correlation. We study Prefix-Consistent Parallel Decoding (PCPD) as a practical relaxation that checks local prefix consistency rather than exact joint sampling. A controlled Block-HMM isolates sampling error, LLaDA provides ordering and parallelization diagnostics, and batched WeDLM experiments examine the quality–latency trade-off of verification. Together, the results explain why improving marginal predictions and correcting the sampling procedure address distinct obstacles to reliable parallel generation.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Language models, Parallel decoding, Masked diffusion models, information theory

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_tWSoOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
3(+1)
Soundness
3(+1)
Read review
Paper summary

The paper analyzes the errors that arise when a masked diffusion model generates several tokens in parallel, using tools from information theory. The authors separate two sources of error. The first is order sensitivity. Because the model's predictions are imperfect, the order in which positions are filled can change the distribution of the generated output. The second is parallelization bias. When several positions are decided independently at the same time, the dependence between them is lost, so the output can be inconsistent as a whole even if each individual prediction is correct. For the second, the authors show that forward KL, reverse KL, and the probability of a failure event capture different aspects of the problem, and that correcting an independent proposal exactly by rejection becomes expensive. They then propose PCPD, a decoding method that drafts tokens, checks them in order with the same model, and corrects the first position where the check disagrees. It is evaluated on synthetic data, LLaDA, and WeDLM.

Critical strengths

The main message is easy to follow. Improving the per-position predictions and fixing the sampling procedure are different problems, and the paper makes this point well. The small examples showing how forward and reverse KL see different things are helpful. Using synthetic data with a known distribution to remove model error and look only at the error caused by sampling is a reasonable design. I also appreciate that the authors are open about the limits of PCPD, for example, that it does not recover the target distribution and can drop one mode entirely.

Critical weaknesses
  1. Both sources of error are already well known. The loss of dependence under independent parallel prediction is the multimodality problem from non-autoregressive machine translation (Gu et al., 2018), and in diffusion LMs, it has been studied by Discrete Copula Diffusion and EB-Sampler. Order sensitivity is closely related to the inconsistency of learned conditionals in masked language models and to exposure bias. It is not clear what the analysis here adds beyond this prior work.
  2. Most of the theory is a direct application of textbook tools, namely the KL chain rule, Pinsker's inequality, and the standard lower bound for rejection sampling. The authors also note in the appendix that EB-Sampler and ParallelBench already give decompositions close to the forward KL decomposition in Equation 10.
  3. The novelty and benefit of PCPD are not well supported. Drafting and verifying with the same model is very close to self-speculative decoding methods for diffusion models such as SSD, FreeDave, and Spiffy, but there is no experimental comparison with them. The speedup is shown only on WeDLM, which uses causal attention and makes prefix verification cheaper. On LLaDA, with standard bidirectional attention, the appendix reports that PCPD is slower than one-token decoding.
  4. The experiments do not really test the claims. The synthetic results mostly confirm what can be computed analytically, and the LLaDA result that committing more tokens per step hurts quality is already well known. There is no evidence that the strength of dependence explains failures on real tasks, and all experiments are single runs without confidence intervals.
Questions for authors
  1. Compared with prior work on the multimodality problem in non-autoregressive translation and on inconsistent conditionals in masked language models, what does this analysis show that was not known before?
  2. How does PCPD compare with SSD, FreeDave, or Spiffy in quality at a matched speed?
  3. Is there any setting in which PCPD is faster than one-token decoding on a masked diffusion model with standard bidirectional attention?
3 comments
AuthorsOpenReview ↗

Response to Reviewer tWSo (1/3)

Q1 and W1

Both sources of error are already well known.

We agree that the core problem is well known, and yet the solution is elusive - fixed order models still dominate. Therefore, we don't feel that nothing of value is left to be said. Indeed, a paper about arbitrary order decoding ("The flexibility trap") received an outstanding paper award in ICML 2026.

The loss of dependence under independent parallel prediction is the multimodality problem from non-autoregressive machine translation (Gu et al., 2018), and in diffusion LMs, it has been studied by Discrete Copula Diffusion and EB-Sampler.

Gu et al. (2018) identified the underlying multimodality problem in non-autoregressive translation. Discrete Copula Diffusion, EB-Sampler, and ParallelBench subsequently analyzed the dependence lost under factorized prediction using forward KL or total correlation. However, they didn't introduce reverse KL and incoherence as metrics to measure the parallelization error, and we point out that they are very important. We ask how much probability the decoder assigns to outputs that violate a constraint.

This question exposes a tension in structured generation. The flexibility to fill positions in different orders is attractive for tasks such as code infilling, where useful context can lie on either side of a missing span. Yet the same dependencies that make this context useful can make independent parallel decisions unreliable. A single mismatched delimiter, for example, can make an entire JSON object unparsable.

Our hard-parity example makes the distinction quantitative. Even with exact token marginals, the factorized decoder violates the constraint on half its samples. Its forward KL is one bit per block regardless of block length, so its forward KL per token approaches zero as the block grows, while the violation rate remains 50%. Reverse KL detects the support mismatch by becoming infinite. Incoherence measures how often it occurs. Thus, a forward-KL bound provides meaningful error control, but a positive tolerance still permits constraint violations.

This distinction also matters for scaling. Better marginal predictions can reduce model error, while the parity example shows that factorization error persists even at the limit of perfect marginals. EB-Sampler’s entropy budget and the factorized remasking updates we study can mitigate this risk, but neither criterion alone guarantees that every committed combination is valid. This motivates our study of verification. PCPD checks whether a proposed token remains the model’s greedy choice after earlier proposals are revealed and corrects the first disagreement. It provides a practical test of local consistency. Guaranteeing that every output satisfies a hard task constraint requires a decoding rule that enforces or verifies that constraint itself.

Order sensitivity is closely related to the inconsistency of learned conditionals in masked language models and to exposure bias. It is not clear what the analysis here adds beyond this prior work.

Prior work on inconsistent conditionals explains why different reveal orders can induce different joint distributions. Exposure bias explains why the contexts encountered during generation can differ from those observed in the data. Our contribution is to quantify how this shift in context frequencies affects the sequence-level error of each reveal order.

EB-Sampler’s forward-KL analysis averages conditional errors along target trajectories. Our reverse-KL analysis expresses each order’s sequence-level error as the sum of local errors along model-generated trajectories (Eq. 3). For a given order, we then evaluate the same local model-to-data KL errors under data prefixes. The difference isolates how much the accumulated error changes because the model visits some contexts more or less frequently than the data do (Appendix A). This explains how two orders with comparable accumulated error on data prefixes can differ in sampling fidelity. Early predictions under one order may lead the model more often into contexts where its subsequent predictions are inaccurate.

W2

 Most of the theory is a direct application of textbook tools

We appreciate this point - it took some effort to make the mathematical development as simple and straightforward as possible, and we feel this adds, rather than detracts, from the paper.

AuthorsOpenReview ↗

Response to Reviewer tWSo (2/3)

Q2 and W3: Comparison with self-speculative decoding

How does PCPD compare with SSD, FreeDave, or Spiffy in quality at a matched speed?

The novelty and benefit of PCPD are not well supported.

We agree that SSD's linear candidate chain is particularly close to PCPD. PCPD fixes a within-round order, accepts the token-agreeing prefix at those positions, corrects the first mismatch, and then recomputes the proposal and order. The SSD-style reference checks both the position newly selected under each revealed prefix and its token. PCPD's equivalence result concerns its specified serial prefix verifier under identical numerical evaluations and round boundaries.

We have added a controlled comparison in Section 5.3, Table 3. The SSD-style adaptation and a parent-reuse PCPD variant share the proposal machinery, batched root/prefix contexts, and packed-query optimization. Both use WeDLM-7B-Instruct, greedy decoding, window 16, entropy ordering, penalty .5, a 256-token limit, and KV blocks of 256 tokens.

The SSD-style adaptation reproduces the one-token output and complete position/token action sequence on all 164 HumanEval+ tasks at both k=4 and k=9. Here k is maximum commits per round. The k=9 comparison is:

MethodHumanEval+ pass@1 (164 tasks)Total seconds (32 tasks)
One-token reference70.12%86.41 ± .06
SSD-style70.12%48.31 ± .02
PCPD, shared variant71.34%39.81 ± .05

Times are mean ± sample SD over five repetitions on the same exclusive RTX 6000 Ada GPU, with trajectory warmup, interleaved method order, and CUDA synchronization. They include prefill and discarded speculative work. All 800 timed outputs match their corresponding full-quality outputs. PCPD takes 17.6% less time than SSD (1.21× speedup) and is 2.17× faster than one-token. The paired PCPD-minus-SSD quality difference is +1.22 percentage points, with 95% CI [−1.83, 4.27] from 20,000 task bootstrap resamples; this does not establish superior or equivalent quality. At k=4, both score 70.12%, with paired difference 0.00 points [−2.44, 2.44]. This is a WeDLM adaptation rather than an official SSD reproduction; we have not evaluated FreeDave or Spiffy.

Q3: Bidirectional attention

We have not demonstrated wall-clock acceleration on dense bidirectional LLaDA. LLaDA motivates verification; acceleration claims concern our WeDLM implementation with batching and prefix reuse.

AuthorsOpenReview ↗

Response to Reviewer tWSo (3/3)

W4: Mechanism and uncertainty

The synthetic results mostly confirm what can be computed analytically.

Structured outputs contain jointly constrained choices: a valid field value or code token in isolation need not remain valid with other choices. The Block-HMM gives a minimal, analytically accessible version of this issue. It serves as analytical role to help us understand the failure mode of the forward KL metric.

We chose the Block-HMM for its analytical tractability. In structured generation, a code token or field value can be plausible in isolation yet incompatible with another choice. When a learned decoder produces such an output, both inaccurate marginal predictions and independent sampling of dependent positions are possible explanations. The Block-HMM lets us isolate the latter. At each parity-noise level, we give the factorized decoder the exact conditional marginals and use sampling from the known joint block conditional as a reference.

Figure 4 shows why this control matters. As the parity constraint becomes stricter, the factorized decoder’s sequence-level forward KL changes relatively little, while its reverse KL rises sharply. At the lowest noise level, roughly half of the generated blocks fall below the specified target-probability threshold. Judging the decoder by the forward-KL curve alone would therefore obscure a substantial change in the risk of generating very unlikely blocks. The known target lets us attribute this divergence between diagnostics specifically to the sampling rule, even when every marginal prediction is correct.

The LLaDA result that committing more tokens per step hurts quality is already well known

We agree that the quality loss from committing more tokens per step is well known. On LLaDA, we use this observation as a baseline for testing a hypothesis motivated by our analysis. A token that appears reliable when several positions are masked may change once earlier draft tokens are revealed. Checking for these changes before committing the full draft could therefore recover some of the lost quality.

To test this hypothesis, we additionally compared LLaDA’s native parallel sampler with PCPD, which re-evaluates draft tokens in prefix order and corrects the first disagreement. The verified decoder achieved substantially higher task quality in the settings we evaluated. This result supports our hypothesis that revisiting parallel proposals can mitigate the quality loss from committing them together.

There is no evidence that the strength of dependence explains failures on real tasks

The Block-HMM provides direct evidence for the proposed mechanism, and the real-task experiments provide indirect evidence. We respectfully disagree with the characterization that there is “no evidence.”

All experiments are single runs without confidence intervals.

Thanks for pointing out this. We have now replicated all 20 plotted HMM settings with 300 independently generated length-64 sequences per KL direction and setting, saving all sequence log probabilities and block-level events. The new 95% intervals use 20,000 bootstrap resamples of complete sequences, preserving within-sequence block dependence. At parity noise 1e-8, the mean-field incoherence rate is 51.88% [49.92, 53.87]; after 16 remasking updates it remains 34.12% [32.25, 36.04]. The corresponding reverse KL decreases from 75.50 [72.63, 78.43] to 45.79 [43.11, 48.51] nats per sequence. The replication uses the same exact remasking kernel, validated against the original implementation; the intervals quantify Monte Carlo uncertainty, rather than uncertainty in the specified target distribution.

For greedy WeDLM evaluations, the 95% intervals below use 20,000 paired bootstrap resamples of benchmark examples. Separately, we repeated synchronized latency measurements five times on fixed 32-example subsets using exclusive GPUs and report mean ± SD, as in the comparison above.

With EB proposal policy, ordering, and penalty fixed (budget 5, penalty .05), verification off/on gives:

TaskOff → OnDifference, pp [95% CI]
GSM8K46.17 → 77.48%+31.31 [28.43,34.27]
HumanEval+10.37 → 67.07%+56.71 [49.38,64.02]
JSON10.09 → 85.58%+75.49 [73.38,77.54]

JSON denotes extracted-object schema validity. The quality intervals quantify uncertainty across examples; runtime variability is assessed by the separate timing repetitions.

Reviewer_eCQjOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies two sources of error in MDMs: order sensitivity (where early prediction errors accumulate as generation goes) and parallelization bias (where decoding multiple tokens independently ignores dependencies between them and potentially produces incoherent outputs). The authors formalize these effects, motivating Easy-First decoding and analyzing how parallelization error relates to dependencies between tokens. They also introduce Prefix-Consistent Parallel Decoding (PCPD), which drafts multiple tokens and verifies them against prefix-conditioned predictions. They perform experiments on a controlled Block-HMM setting and show that PCPD can achieve 2–3× speedups with respect to one-token decoding at similar quality.

Critical strengths
  • Interesting separation of the two failure modes: I find the separation between the two error modes (order sensitivity and parallelization bias) interesting. The theoretical results show that improving marginals reduces the model error but the conditional total correlation term remains, which is a useful insight.
  • Well-motivated study: the theory explains why early errors matter and motivates Easy-First decoding, while also acknowledging its limitations.
  • Informative analysis: the paper shows how different metrics (forward KL, reverse KL, and incoherence) can capture different failure modes. I also liked the use of counterexamples.
  • Controlled experiments: Block-HMM provides exact marginals and a known joint distribution, which allows the authors to separate sampler errors from model quality in their experiments.
  • Transparency and limitations: the paper is careful about the scope of the claims and openly discusses the limitations.
Critical weaknesses
  • Missing related work: the paper discusses related work, but leaves out two recent works: 1. on adaptive decoding orders and uncertainty measures (Kim et al., 2025) and 2. on the role of interactions between jointly predicted masked positions (He et al., 2026), which are relevant to the topics in this paper.

  • Unclear novelty and use of PCPD: although the paper distinguishes PCPD from reference-preserving speculative decoding, the relationship between PCPD and speculative or self-speculative decoding is not very clear and PCPD is not compared empirically against them.

  • Limited practical evidence: the speedups and quality gains of PCPD are inconsistent across settings. These gains appear to be confounded with ordering penalties, as the authors acknowledge, and there are no confidence intervals.

  • Theory–experiment connection: beyond the Block-HMM setting, the theoretical analysis is not directly connected to the experiments. Also, the theory does not directly cover PCPD, and real-model evaluations use greedy decoding and task accuracy rather than testing the distributional claims, diversity, or mode coverage.

  • Overall narrative: overall, while the paper is clear and easy to follow, the main message is a bit diluted, and sometimes it is difficult to connect the different sections of the paper (see previous point).

REFERENCES

(Kim et al., 2025) Jaeyeon Kim, Kulin Shah, Vasilis Kontonis, Sham Kakade, Sitan Chen. Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions. ICML 2025.

(He et al., 2026) Andre He, Sean Welleck, Daniel Fried. Reasoning with Latent Tokens in Diffusion Language Models. Preprint, 2026.

Questions for authors
  1. How does the rollout-amplification relate to the explanation in Kim et al. of order effects? Did the authors also consider comparing entropy with the top-probability margin (as proposed by Kim et al.) as the confidence proxy for Easy-First?

  2. Following the analysis in He et al., how much of PCPD’s prefix mismatch is a result of dependence between jointly predicted positions or just changes in the set of masked positions? It would be interesting to control for this by, for example, keeping a fixed number of masked positions.

  3. Is PCPD a contribution of this work? If not, could the authors better clarify this and add references? If so, what is the main difference between PCPD and blockwise parallel decoding or SSD and why are these not included as baselines?

  4. Beyond Block-HMM, how do the authors think the conclusions transfer to distributions with less structured dependencies such as natural text? The current limitations just mention it briefly, it would be interesting to extend the limitations and/or mention it as future work.

4 comments
AuthorsOpenReview ↗

Response to Reviewer eCQj (1/3)

Q1 and W1: Ordering and uncertainty measures

How does the rollout-amplification relate to the explanation in Kim et al. of order effects? Did the authors also consider comparing entropy with the top-probability margin (as proposed by Kim et al.) as the confidence proxy for Easy-First?

Kim et al. (2025) explain how adaptive ordering can defer difficult predictions until more context is available. Our analysis complements this by quantifying how early decisions affect later errors. Eq. (3) evaluates errors on the model’s own rollout, and the bound in Eq. (4) gives earlier discrepancies greater weight because they can affect more subsequent contexts.

We compared lowest-entropy ordering with largest top-two probability margin on all 164 HumanEval+ tasks using WeDLM-7B-Instruct. Both used greedy decoding and zero distance penalty to isolate the ordering rule.

Max commits per roundEntropy pass@1Margin pass@1Margin − entropy, pp [95% CI]
165.85%59.15%−6.71 [−13.41, 0.00]
965.24%46.95%−18.29 [−26.22, −10.37]

Entropy had higher observed pass@1 in both settings. Across 20,000 paired bootstrap resamples, the interval includes zero at one commitment per round and favors entropy at nine.

Q2 and W1: Dependence versus the masked-position set

Following the analysis in He et al., how much of PCPD's prefix mismatch is a result of dependence between jointly predicted positions or just changes in the set of masked positions?

He et al. (2026) show that still-masked positions can contribute to a target prediction through their hidden representations. This motivates the reviewer’s question. When PCPD reveals a draft token, both the visible content and the set of masked positions change.

We ran a paired diagnostic on WeDLM using 32 HumanEval and 32 JSON prompts. At preset stages of each PCPD trajectory, we queried the same still-masked target position twice. In both queries, we revealed the same draft position. One query used its greedy token and the other used the highest-scoring non-mask token other than the greedy choice. The two queries had identical masked positions, other visible tokens, position IDs, cached prefix, and query length.

TaskProbe statesTarget argmax differs between the two queries95% CI
HumanEval147134/147 (91.16%)85.71%–95.97%
JSON8672/86 (83.72%)76.60%–91.11%

The intervals resample prompts, keeping all probe states from each prompt together. Repeating the identical input reproduced the logits in all 233 checks, and the diagnostic queries left all 64 generated outputs unchanged.

These results show that changing the value of a single revealed token can change the verifier’s prediction even when the entire mask pattern is fixed. The percentages quantify sensitivity to this specific intervention. The alternative tokens had median proposal probabilities of 0.103% on HumanEval and 3.501% on JSON, so the intervention can probe values rarely encountered during ordinary decoding. The fraction of ordinary PCPD mismatches attributable to data dependence, learned-model error, or mask-pattern changes remains unresolved.

AuthorsOpenReview ↗

Response to Reviewer eCQj (2/3)

Q3 and W2: PCPD and self-speculative decoding

Is PCPD a contribution of this work? If not, could the authors better clarify this and add references? If so, what is the main difference between PCPD and blockwise parallel decoding or SSD and why are these not included as baselines?

Yes. We introduce PCPD as the specific relaxation of prefix verification studied in this work. The revised §4.3 credits the draft–verify–accept-prefix procedure to prior work. SSD already uses the same masked model to draft candidate tokens and verify their prefixes in a batch. We therefore use SSD as the closer empirical baseline.

PCPD and SSD differ in what the verifier must confirm before accepting a draft token. SSD checks whether the stepwise decoder would select both the proposed position and its proposed token next. PCPD fixes the position order at the start of each round and checks each token after revealing the preceding draft tokens. If another position now ranks first but the token at the proposed position still agrees, PCPD can continue along the draft. This relaxation can yield a longer accepted prefix and reduce decoding latency.

Each method corresponds to token-by-token greedy decoding under its own ordering rule. SSD targets a serial decoder that reranks positions after every commitment. PCPD follows the round’s fixed order, commits the agreeing prefix and the verifier’s correction at the first mismatch, and refreshes the proposal and order for the next round. Lemma 2 establishes that batched PCPD reproduces this serial verifier under identical numerical evaluations, tie-breaking, and round boundaries.

We added an SSD-style comparison to Section 5.3 (Table 3). To compare the two acceptance criteria, we evaluated both verifiers in a shared WeDLM-7B-Instruct engine with parent-prediction reuse and batched prefix checks. All methods, including the one-token reference, used the same numerical backend, greedy decoding, a window size of 16, a distance penalty of 0.5, and a 256-token generation limit. For both verifiers, k denotes the maximum number of tokens that can be committed per round.

For both verifiers, k is the maximum number of tokens that can be committed in one decoding round. At k = 9, the SSD-style WeDLM adaptation reproduced the one-token reference’s output and full sequence of position and token choices on all 164 HumanEval+ tasks (§5.3, Table 3).

MethodHumanEval+ pass@1 (164 tasks)Total time (32 tasks)
One-token reference70.12%86.41 ± 0.06 s
SSD-style adaptation (k = 9)70.12%48.31 ± 0.02 s
PCPD, shared variant (k = 9)71.34%39.81 ± 0.05 s

Times are mean ± sample SD over five repetitions on a fixed 32-task subset using a dedicated RTX 6000 Ada. PCPD reduced end-to-end latency by 17.6% relative to the SSD-style baseline (1.21× speedup). These times include the difference in output lengths, with 4,544 tokens generated by PCPD and 4,792 by SSD-style.

The paired pass@1 difference at k = 9 was +1.22 percentage points (95% CI [−1.83, 4.27], 20,000 task bootstrap resamples). At k = 4, both methods scored 70.12% (paired difference 0.00 points, 95% CI [−2.44, 2.44]). Appendix E reports the shared execution protocol and timing ablations.

AuthorsOpenReview ↗

Response to Reviewer eCQj (3/3)

W3: Ordering confounds and uncertainty

These gains appear to be confounded with ordering penalties, as the authors acknowledge, and there are no confidence intervals.

We agree that differences in ordering penalties complicate the attribution of quality gains to verification. We therefore report a controlled ablation in Appendix E (Table 5). Both conditions use the same EB proposal policy, entropy ordering, entropy budget of 5, distance penalty of 0.05, window size of 16, and maximum chunk size of 16. We vary only whether proposals are verified. A correction can change the context and hence the proposals made in subsequent rounds.

TaskVerification offVerification onPaired difference, pp [95% CI]
GSM8K accuracy46.17%77.48%+31.31 [28.43, 34.27]
HumanEval+ pass@110.37%67.07%+56.71 [49.38, 64.02]
JSON schema validity10.09%85.58%+75.49 [73.38, 77.54]

The intervals use 20,000 paired bootstrap resamples of examples within each benchmark. JSON validity is measured on extracted objects. With the ordering policy held fixed, verification substantially improved quality on all three tasks under this aggressive proposal setting, at the cost of additional computation and latency.

For the main comparison, PCPD and the one-token reference use the same ordering score and distance penalty of 0.5. Table 5 reports paired confidence intervals for their quality differences. All three intervals include zero, so the small observed differences leave the quality comparison inconclusive. To quantify runtime variability, we repeated timing five times on fixed 32-example subsets using a dedicated GPU. Relative to the one-token reference, PCPD achieved mean speedups of 3.094× on HumanEval+ (SD 0.047) and 2.446× on JSON (SD 0.045).

Q4, W4 and W5: Transfer beyond Block-HMM and the overall message

Beyond Block-HMM, how do the authors think the conclusions transfer to distributions with less structured dependencies such as natural text?

The KL identities apply to general sequence distributions. What the Block-HMM gives us is a known target distribution and a constraint whose strength we can vary. In natural text, the target joint distribution is unknown, and incoherence is harder to define. Subject–verb disagreement can often be checked directly, whereas a contradiction with an earlier statement may require judging the passage as a whole. Many low-probability continuations are also valid. If we can measure the inconsistency of generated text, we can then investigate to what extent the introduction of verification can improve this inconsistency metric.

The theory does not directly cover PCPD, and real-model evaluations use greedy decoding and task accuracy rather than testing the distributional claims, diversity, or mode coverage.

Our distributional analysis motivates checking a parallel proposal after revealing part of its context. For greedy PCPD, Lemma 2 gives a specific guarantee: batched verification reproduces the serial verifier with the same within-round order, round boundaries, numerical evaluations, and tie-breaking. Appendix C illustrates the limit of this guarantee. Even with exact marginals and two equally probable valid outputs, greedy PCPD can return the same output on every run and miss the other mode entirely.

We evaluate distributional distortion in the Block-HMM, where the target law is known. On real models, we test whether the conditional checks matter for decoding decisions and task performance. In the fixed-mask diagnostic, changing one revealed token could change the verifier’s prediction. In the fixed-policy HumanEval+ ablation, enabling verification increased the number of tasks passed from 17 to 110 out of 164. These results support the practical value of conditional checks in greedy decoding. Diversity and mode coverage under stochastic decoding remain open empirical questions.

The main message is a bit diluted, and sometimes it is difficult to connect the different sections of the paper.

Thank you for pointing this out. We agree that the connection between the order analysis and the verification experiments could be clearer. The common message is that reliable parallel generation requires attention to both prediction quality and the sampling procedure. The order analysis explains how model errors interact with generated contexts. The parallelization analysis shows what independent commitment can lose even with accurate marginals. Verification then tests whether proposals survive the context created by earlier decisions. Section 4.3 now follows this progression, explicitly acknowledges SSD, and introduces PCPD's relaxation; Section 5.3 includes the direct empirical comparison.

I thank the authors for the detailed response and additional experiments, which address several of my raised concerns. Some points remain open: mainly regarding the novelty of PCPD relative to SSD and the connection between the theory and the real-model experiments.

Overall, I remain mostly positive about the paper and keep my score recommending acceptance.

Reviewer_ckSMOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper aims to provide a formal treatment of errors in Masked Diffusion Models (MDMs). Its main contribution is formalizing the separation of errors into those due to order sensitivity and those due to predictions being made independently (in parallel). Given this

Lemma 1 formalizes the fact that early decisions for a given order of decoding affect later decisions over a general model. Based on this, it establishes how modeling errors with respect to the true data distribution compound, showing an at most quadratic upper bound for compounding of errors and how much missmatch weights.

Parallelization error uses an oracle decoder factorized over blocks of parallel predictions and considers forward and reverse KL divergences and an incoherence metric. For the forward KL it is shown that the error is sum of blockwise conditional total correlations. Prop. 1 shows that exactly correcting a fixed factorized proposal by whole-block rejection costs at least exp(total correlation) proposals per block.

Finally, the paper proposes Prefix-Consistent Parallel Decoding (PCPD). PCPD drafts a chunk greedily, verifies the drafted tokens in a batch against the same model conditioned on the earlier drafts, and accepts the agreeing prefix. Experiments include:

  • a Block-HMM with parity constraints, where exact KLs can be computed;
  • LLaDA at one vs two tokens per step on GSM8K, HumanEval+, and JSONSchemaBench;
  • WeDLM-7B latency/quality comparisons of PCPD against one-token decoding, native WeDLM, and the EB-Sampler rule.
Critical strengths
  • the separation of errors as being either form order sensitivity or parallelization makes a lot of intuitive sense, so it formalization is valuable for general research in masked diffusion models

  • the formal treatment seems correct and extensive with a number of interesting results. The paper brings in well-understood tools from information theory and imitation learning and applies them consistently to the MDM setting.

Critical weaknesses

The formalization does not bring strong conclusions for a real case scenario.

  • For the error bound after Lemma 1, It is required that the factor B to bound the local error for every model context, which is not a realistic assumption.

  • the clean separation holds only for the forward KL case. The abstract claims gnerally "a framework separating order sensitivity from parallelization bias". The paralelization formalization requires as well marginal oracles, so the metrics are not applicable to real cases.

Questions for authors

Clarify the bound after Lemma 1 having to do Theorem 2.1 in Section 2.1, "The supervised learning approach to imitation", of Ross & Bagnell, Efficient Reductions for Imitation Learning in AISTATS 2010

Also Kim et al. 2025, "Train for the Worst, Plan for the Best" in ICML 2025 seems related to the easy first question

2 comments
AuthorsOpenReview ↗

Response to Reviewer ckSM

Thank you for the careful reading and for recognizing the value of distinguishing model error from sampling error. We address the scope of the assumptions and the connections to prior work below.

W1: Bounded local error

For the error bound after Lemma 1, It is required that the factor B to bound the local error for every model context, which is not a realistic assumption.

We agree that a uniform bound on local conditional KL is a strong assumption. If the model assigns positive probability to a token excluded by the target conditional, the local reverse KL is infinite. Even with compatible support, very small target probabilities can make the bound too loose to be numerically useful.

We use this assumption to derive Eq. (4), which makes explicit how a discrepancy at an early step can affect the contexts of the remaining predictions. Its role is to explain this propagation under bounded local error. The rollout-weighted KL identity in Lemma 1, Eq. (3), holds without the boundedness assumption and allows an infinite value under support mismatch.

W2: Forward-KL separation and oracle marginals

The clean separation holds only for the forward KL case. The abstract claims generally "a framework separating order sensitivity from parallelization bias".

We agree that “separating” in the abstract suggests a broader decomposition than we establish. We will revise the abstract sentence to read: “We analyze how reveal order affects the accumulation of model error and how parallel factorization can distort the generated distribution even when token marginals are exact.”

The parallelization formalization requires as well marginal oracles, so the metrics are not applicable to real cases.

We agree that the true data conditionals are generally unavailable in language tasks, which limits direct evaluation of forward and reverse KL. We use oracle marginals in the Block-HMM to answer a controlled question: how much error can parallel commitment introduce even when every token marginal is correct? As the parity constraint tightens, forward KL changes relatively little, yet at the lowest noise level roughly half of the independently generated blocks fall in the specified low-probability region. Because the marginals are exact, we can attribute this failure to the sampling rule.

This analysis also informs evaluation on real tasks. When a failure event is externally checkable, its frequency can be estimated directly from generated samples. For example, a schema validator can measure how often a decoder produces an invalid object without access to oracle marginals. This gives us a practical way to assess the consequence of parallel commitment that matters for the task, while the controlled experiment explains how such failures can persist even with accurate marginal predictions.

Q1: Connection to Ross and Bagnell (2010)

Clarify the bound after Lemma 1 having to do Theorem 2.1 in Section 2.1, "The supervised learning approach to imitation", of Ross & Bagnell, Efficient Reductions for Imitation Learning in AISTATS 2010.

Equation (4) adapts the compounding-error argument in Ross and Bagnell’s Theorem 2.1 to masked decoding. Their theorem bounds the increase in cumulative task cost using the learner’s average action error on expert-visited states. Their proof already captures the temporal asymmetry that an early error can affect the states visited at every later step.

In our setting, the states are revealed prefixes, and the quantity bounded is the sequence-level reverse KL for a fixed reveal order. We account for each step’s local conditional KL under data prefixes, then bound the effect of evaluating that loss under model-generated prefixes. A conditional TV discrepancy at step s can shift the prefix distribution at each of the remaining T − s steps. The bound B on local KL converts each such shift into a bound on the change in expected loss, yielding the weight B(T − s) in Eq. (4). We have cited Theorem 2.1 directly alongside Eq. (4) and made this connection explicit in Section 3 and Appendix A.

Q2: Connection to Kim et al. (2025) and Easy-First

Also Kim et al. 2025, "Train for the Worst, Plan for the Best" in ICML 2025 seems related to the easy first question.

Thank you for pointing us to Kim et al. (2025). Their work is directly relevant to our discussion of Easy-First decoding. They show that masked prediction problems differ in difficulty and that adaptive ordering can help the model avoid difficult subproblems. Our analysis complements this perspective by examining how errors accumulate along the chosen order. An unreliable early prediction can change the contexts of several later predictions, which provides a further motivation for choosing reliable positions early. We have cited Kim et al. and clarify this connection in Section 3.

The authors have answered my questions satisfactorily.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.