- 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
- 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.
- 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.
- 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.
- 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
- 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?
- How does PCPD compare with SSD, FreeDave, or Spiffy in quality at a matched speed?
- Is there any setting in which PCPD is faster than one-token decoding on a masked diffusion model with standard bidirectional attention?
3 comments
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:
| Method | HumanEval+ pass@1 (164 tasks) | Total seconds (32 tasks) |
|---|---|---|
| One-token reference | 70.12% | 86.41 ± .06 |
| SSD-style | 70.12% | 48.31 ± .02 |
| PCPD, shared variant | 71.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.
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:
| Task | Off → On | Difference, pp [95% CI] |
|---|---|---|
| GSM8K | 46.17 → 77.48% | +31.31 [28.43,34.27] |
| HumanEval+ | 10.37 → 67.07% | +56.71 [49.38,64.02] |
| JSON | 10.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.
Response to Reviewer tWSo (1/3)
Q1 and W1
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.
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.
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
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.