- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper studies parallel decoding in Masked Diffusion Language Models (MDLM), whose error stems from the fact that multiple tokens are chosen conditionally independently per step. The size of this error is characterized by a KL or total correlation, but this is difficult to estimate in general as it requires the true joint distribution. The paper considers bounds, or certificates on the total correlation using quantities that are efficient to compute during inference (marginal entropies, marginal distributions, anchor interventions). A thorough analysis of these bounds also takes into account the fact that the marginals from different decoding orders may not be consistent with a single joint distribution. The paper studies the tightness of different types of bounds.
Critical strengths
The paper is systematic in studying the tightness of bounds that arise from considering different computable quantities.
The paper notices that marginals from different decoding orders are not necessarily consistent with a single joint distribution, and takes this into account in developing some bounds. While decoding error and incompatibility of different decoding orders had both been studied separately, I had not seen the two issues combined until this ICLR.
I appreciated the inclusion of synthetic experiments to verify the qualitative behavior of the bounds with a known ground truth.
Critical weaknesses
Experiments are illegible
It was impossible (for me at least) to parse what the experiments were trying to say. Consider the block of text from 389-409. To me, it looks like the numbers from the tables have just been translated into impenetrable prose. This is not the how discussion of the results should look. What we really need is more like this:
- A description of what question you want to answer
- A readable description of the experiment, and why/how it will answer the question
- Point to the table for the raw numeric results, but give a high level discussion of what qualitative effect was observed (this number went up or down, or this method was better than the other)
Looking at table 2, ideally I should be able to get the gist of the experiment from the figure and caption. I don't believe any non-author could understand this caption. I think this is the synthetic experiment with small vocabulary and ground truth, trying to evaluate how different numbers of probes (k?) lead to tighter bounds on TC (?) If I'm in the ballpark, consider whether some friendly description like this could be included.
Table 3. "Depth-2 scores", searching the main text, I don't see a definition of depth-2 scores. I think it is in the appendix. "depth" isn't even mentioned until page 8, the experiments. "A positive IncLB certifies incoherence", this isn't too surprising, lots of papers have found that these marginals are incoherent. Was there something different expected for your result? I believe the sub-columns are meant to reflect the methods in table 1 (?) but the labeling is not consistent. Are we supposed to see a ranking of tightness here? Maybe the distances, d, in both direction also reflect incoherence?
Tables 1 and 2 are the only results in the main text, and I learned nothing from them. Random numbers from tables at least up to 15 are given in the text. It would be Ok to say something like "We wanted to test whether the qualitative result XXX holds under a different sampling strategy using argmax commits. Table 15 in the appendix confirms this". I don't think I'm being unreasonable in saying that the following text is not human-readable.
With argmax commits on GSM8K, the prefix at e = 1 matches the 256-step schedule (79.00%) at 73.78 mean NFE. At a comparable mean NFE, anchoring at e = 1 (74.75%, 63.75 NFE) and the prefix at e = 2 (74.53%, 65.32 NFE) differ by 0.23 percentage points in accuracy (anchored minus prefix, 95% interval [−2.20, 2.65]) and by −1.57 in NFE ([−2.10, −1.05]), which does not establish equivalence; both exceed the 64-step schedule (63.91%).
Also, is it not reasonable to have some sort of experiment that shows that tighter bounds can somehow be leveraged to improve sampling? If such a result was suggested I was not able to fish it out.
Other readability issues
Although experiments were most difficult to read, the paper was frustrating throughout, lots of internal jargon is used that are not defined or not defined until late in the paper. Even a high level definition could have helped to at least parse the claims in the intro. Let me just give a few examples.
"excess bits" is used many, many times in the intro. It's not defined until a technical definition on page 3, and I didn't see a high level definition. It was mentioned in the context of the Ben-Hamu paper, so I checked if maybe it's a well known term from that paper. They do not use the word "excess" anywhere in that paper. Table 1 could have helped - I can understand what the quantity in the first row is, but it's not referred to as excess entropy there, nor is Ben Hamu mentioned there, so I couldn't tell at that point if it's the same thing.
Minor comments
- In the abstract, I felt a little more context about what the "certificate" means was needed before making complex claims about it.
- Line 114 introduces e hat as the "error". I would have called this confidence. Also, this e kind of conflicts with using "e" as excess bits.
- Why is kappa in Table 1? Table 1 was almost a nice resource to give the main skeleton of the types of bounds considered and their relations. kappa is some detail that I didn't see until somewhere in the appendix, and I still don't understand it's role.
- "e is tightest if a <= b". I think I get the idea behind these types of statements, but I think there should be a better way to word it.
Questions for authors
I liked the mathematical development of the bounds. If the authors can give some intuitive accounting of what the results are trying to show and why this is useful, and would consider revising the results accordingly, I would be open to changing my score.
4 comments
The former Table 3 (now Table 14, Appendix F.2)
This table is a compatibility diagnostic, not a ranking of certificates. Its sub-columns are reveal-set rules (the entropy-ordered prefix, the anchored set, and the uniform average over feasible sets at a common budget), not the bounds of Table 1. Your reading of the two directions is right: if both query directions came from one joint law, their complete depth-2 scores would coincide. With queried values, each direction locates its complete score only within an interval of width , where is the unqueried mass, and is the gap between the two intervals (Proposition 14). A positive gap therefore certifies incompatibility. In the aggregated table it shows that at least one state–pair of positive weight is incompatible; it does not estimate how common incompatibility is.
We agree that incompatibility itself is known from prior work. What is new is detecting it from a few conditional queries and entropy summaries, identifying incompatibilities that entropy-based tests cannot see, and giving a probability-level test that does (Propositions 13–15). As you note, the paper combines this with decoding error: compatibility decides whether a certificate computed from model outputs can be interpreted at all. Section 6.3 now states this purpose, and depth , query count and the scores are introduced in Section 4, before the experiments.
Definitions and minor comments
- Certificate and excess bits. The abstract and introduction now define both at first use. A certificate is an upper bound on the dependence among the tokens committed in one step that holds for every joint law consistent with what the decoder observes. Excess bits is our name for the quantity defined in our earlier response; Ben-Hamu et al. (2025) bound the same quantity without naming it, and Table 1 now cites them.
- Token confidence. Section 2 defines confidence as and removes the competing notation.
- The role of . Table 1 is now an information-level roadmap without . Proposition 6 explains that bounds the computational gap to the optimal certificate, not the distance to the actual TC.
- Optimality statements. The introduction now states entropy-only optimality as the impossibility of a smaller universally valid upper bound. Proposition 5 is titled "A sufficient condition for optimality of the excess-bit bound", with its conditions and conclusions in separate sentences.
Do tighter scores improve sampling?
Not yet, and the paper now explains why. Section 6.2 evaluates residual-score decoding on LLaDA with generation quality, actual NFE and request time (Table 3): the residual correction changes some selections, but the comparisons establish neither a consistently better decoder nor preserved quality at lower latency. Supplementary Table S28 also includes marginal-meet decoding, which tightens the entropy-only score with full marginal vectors at no extra forward pass, so the effect of a tighter score can be read there without the cost of queries. Section 6.4 keeps the original prefix and anchored experiments. Improved certification and improved generation therefore have to be evaluated separately; Our earlier response summarizes when tighter scores could pay off.
We thank the reviewer again for the detailed feedback. We hope the revised Section 6 and the experimental overview in our earlier response give the intuitive account you asked for, and we would be grateful if you would reconsider your score in light of them.
Thank you, the readability of the paper is definitely improving, but I believe that organizing contributions around a tighter framing of the motivation would still help more. In the rebuttal you say:
The paper's central question is what dependence can be certified from the information available to a parallel decoder, and what additional information or assumptions are needed; it does not propose a faster sampler.
The issue is that for readers like myself, it's hard to imagine why we want to certify this dependence, if not to improve the sampler.
There are hints for why this could be useful in the contributions and appendix:
Saved-state tests and matched bf16/fp32 replay queries detect incompatible LLaDA-8B outputs (Section 6.3); these diagnose the evaluated outputs rather than establish target exactness.
analyses of one LLaDA8B checkpoint detect incompatible outputs, and residual-score decoding changes selections without establishing consistent quality or speed gains.
I find these statements still quite confusing. It seems like there's an interesting angle here - but 6.3 makes clear that this incompatibility or coherence does not imply exact sampling or better quality outputs either, so what then is it telling us? I mean, mathematically, I get the idea that the marginals are consistent with a joint law. Incompatibility then is a sign of some model deficiency? Then can/should the deficiency be remedied somehow?
I appreciate the effort in the rebuttal and re-writing, and the improvements to the paper, but maintain my score of 2.
Thank you for the follow-up. You are right that the contributions should be organized around the motivation, and our disclaimer "it does not propose a faster sampler" obscured it.
Why certify dependence
A parallel sampler commits several tokens per step to save forward passes. When the model's outputs are compatible, that is, conditionals of one joint law , decoding one token per step with categorical commits samples exactly from under every reveal order (Proposition 18). is then the model's own output law, and committing several tokens together departs from it only because they are drawn independently: each step costs exactly their dependence, for the committed set (Theorem 3(i)), and these costs add up over a generation (Theorem 27). Every adaptive sampler therefore decides how much dependence it can afford per step; the entropy-bounded sampler does this with the excess bits. A certificate turns that decision into a guarantee, and the tightest certificate determines how much parallelism a given kind of output can safely support. Our results are thus limits for sampler design rather than a new sampler:
- With marginal entropies, the excess bits are already optimal (Proposition 5), so no entropy-based rule can safely commit more.
- Full marginal vectors are a free refinement, but substantially more safe parallelism requires conditional queries, best used through the residual coupling (Proposition 10).
- All of this presupposes compatible outputs, which is where LLaDA falls short.
We will reorganize the introduction and the contribution list around this framing.
What incompatibility tells us
Compatibility does not imply that the model matches the data: a compatible model can still be miscalibrated. It decides whether parallel decoding has a well-defined one-at-a-time baseline, and whether certificates computed from the outputs bound the departure from it. On LLaDA, both fail (Section 6.3):
- Order dependence. Decoding the same two tokens one at a time in the two orders gives pair distributions that differ by at least 0.12 in total variation on average over the 140 replayed states. This certifies without ground truth that the outputs are not conditionals of any joint law (Proposition 15); by Proposition 18, calibration error alone cannot explain it.
- Broken Bayes consistency. At the minimum-entropy anchor with four or eight queried values, every multi-token candidate has a negative residual entry (Proposition 13(ii)): at some position, the model's marginal puts less mass on a value than its clamped conditionals imply. Even for a fixed order, the parallel step then carries a marginal-mismatch term , with the one-at-a-time marginal (Theorem 3(i)), which the excess-bit dependence bound does not account for.
This is the angle you point to: on LLaDA, the obstacle to certified acceleration is the model's outputs, not missing information.
Is it a deficiency, and can it be remedied?
Yes. The data's conditionals are compatible and minimize the masked cross-entropy loss, but the loss scores the predictions at a masked state and at each clamped state separately and never asks them to agree; incompatibility is the approximation error this leaves unconstrained. It can be addressed at three points:
- At inference, as a guard. A sampler can detect it from the queries it already makes and refuse multi-token commits where it is certified, as our strict residual rules do (Section 6.2).
- At inference, as a repair. For pairs of tokens, Torroba Hennigen & Kim (2023) derive the joint whose conditionals are closest to incompatible masked-LM conditionals, and find that its conditionals occasionally outperform the original ones; decoding from such a joint would restore a well-defined baseline.
- At training. A lower bound on the total variation distance between the two order-induced pair laws is computable from model outputs without labels, at 16 extra forward passes per state with eight queried values per direction (mean retained mass of 98.8% at the minimum-entropy anchor and 82.1% at the maximum-entropy anchor on the replay panel). It could serve as a consistency regularizer or validation metric. We have not tested this.
Whether it should be remedied depends on the goal: it is necessary for certified acceleration, while its effect on output quality remains open.
We will also rewrite the two sentences you quote to state these consequences: that at many tested states LLaDA-8B's one-at-a-time output depends on the decoding order, so the error of its parallel decoding cannot be certified from its outputs (Section 6.3), and that with such outputs and the cost of queries, tighter scores change selections without consistent quality or speed gains (Section 6.2).
Thank you for the specific guidance on presentation, and for recognizing the systematic study of the bounds, the combination of decoding error with incompatibility, and the synthetic experiments with known ground truth. We agree that the original experimental section obscured its questions and implications. We rewrote it and now define the terminology at first use; the revised PDFs mark relocated content in purple and new or revised content in orange.
What the results show, and why this is useful
Section 6 now has four subsections. Each states its question, describes the experiment and why it answers the question, then gives the qualitative result and points to the tables for the numbers. In short:
Why this is useful: the results tell a decoder designer which information is worth paying for. Entropy-based rules are already optimal for what they use, and full marginal vectors are a free refinement rather than a remedy, so certifying substantially more requires conditional queries. Queries pay off only if the outputs are compatible and the extra forward passes cost less than the steps they save. Current LLaDA outputs fail the first condition, and in our depth-2 cost study the extra passes outweigh the steps they save (Table 6, formerly Table 5); this is why tighter scores have not yet improved sampling.
Table 2
Your reading of Table 2 is correct: it uses a known four-symbol joint distribution and asks how much retained conditional queries tighten the certificate. The caption now states the 2,000 pairs, query count, retained mass, score budget and denominators. With two queried values, the certified fraction rises from 24.8% when the unqueried values are discarded to 50.0% with the exact residual coupling, or 48.5% with its computable bound, while 93.2% of pairs actually meet the budget. With three of the four values queried, every pair that meets the budget is certified. Using the residual constraints thus doubles what two queries certify, and the remaining gap is missing information.