acceptodds
Under review as a conference paper at ICLR 2027

Beyond the Marginals: Dependence and Parallel Decoding in Masked Diffusion Language Models

Abstract

Parallel decoding in masked diffusion language models commits multiple tokens simultaneously from a product of marginals, introducing an error governed by the unobserved conditional total correlation of the revealed set. We establish the fundamental limits of parallel decoding by characterizing the tightest dependence certificates across a hierarchy of available information, defined as the supremum of total correlation over all consistent joint laws. From marginal entropies alone, the excess-bit criterion is tightest whenever the vocabulary is large relative to the entropies; with full marginal vectors, the tightest certificate is attained by a minimum-entropy coupling and can improve upon the excess bits by an amount on the order of bits. Our main theoretical result characterizes the tightest certificate under truncated conditional queries: a residual coupling constrained by the marginals attains this certificate, and computable brackets decouple approximation slack from missing-information slack. On sources with known joint distributions, this formulation doubles the fraction of certified sets compared to discarding unqueried values, while for larger vocabularies missing query information accounts for most residual slack. Crucially, such query-based certificates presuppose that the denoiser outputs are conditionals of a single coherent joint law; truncation-aware tests on saved LLaDA-8B states reveal that real model outputs violate this precondition. Finally, we characterize the position left unconstrained by the excess-bit criterion, proving that anchoring it to the most uncertain position adds no parallelism and can paradoxically increase dependence.

Primary area:
generative models
Keywords:
Diffusion Language Model, marginals, residual, draft, correlation, denoiser

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_nLvnOpenReview ↗
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

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:

  1. How do additional information and residual constraints change what can be certified? With marginal entropies alone, the excess bits e(S)=∑i∈Sh^i−max⁡i∈Sh^ie(S)=\sum_{i\in S}\hat h_i-\max_{i\in S}\hat h_i, which the entropy-bounded sampler of Ben-Hamu et al. (2025) keeps below a threshold, are already the best valid bound whenever the largest entropy is at most log⁡2∣V∣−∣S∣\log_2|\mathcal V|-|S| bits, about 16.9−∣S∣16.9-|S| on LLaDA (Proposition 5). Full marginal vectors tighten this without an extra forward pass but stay several times above the actual dependence (Table 5, formerly Table 4). Queried conditionals help most when the unqueried values are also accounted for, and missing information dominates the gap they leave (Table 2; Table 11, formerly Table 10).
  2. How does residual correction change learned-decoder selections, quality, and cost? It changes some selections, but on LLaDA neither quality nor latency improves reliably (Table 3): each queried value costs a forward pass, and the scores carry no guarantee (item 3).
  3. Do the learned outputs satisfy the necessary compatibility conditions? No. Both entropy-level and probability-level tests certify that the conditionals queried in the two directions cannot all come from one joint law, and the probability-level statistic is essentially unchanged in fp32 (Section 6.3). Certificates computed from these outputs are therefore diagnostics, not guarantees.
  4. What changes when the free position is selected differently under the same excess-bit budget? Moving it to the most uncertain token adds no per-step parallelism (Proposition 16). With exact marginals it is guaranteed to commit more information when the entropy gap exceeds the budget (Corollary 17), but otherwise it can commit less information with more dependence (Remark 25). With a learned model it places the model error where the model is least certain. The entropy-ordered prefix appears to be a reasonable default in the settings studied here (Section 6.4).

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.

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 kk queried values, each direction locates its complete score only within an interval of width (1−wk)log⁡2∣V∣(1-w_k)\log_2|\mathcal V|, where 1−wk1-w_k is the unqueried mass, and IncLB\mathrm{IncLB} 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 TT, query count kk and the scores d1,d2,kd_1,d_{2,k} 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 e(S)e(S) 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 max⁡vP^i(v)\max_v\hat P_i(v) and removes the competing e^i\hat e_i notation.
  • The role of κ\kappa. Table 1 is now an information-level roadmap without κ\kappa. Proposition 6 explains that κ\kappa 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 QQ, decoding one token per step with categorical commits samples exactly from QQ under every reveal order (Proposition 18). QQ 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, KL(QS∥⨂i∈SP^i)=TC(QS)\mathrm{KL}(Q_S\Vert\bigotimes_{i\in S}\hat P_i)=\mathrm{TC}(Q_S) for the committed set SS (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:

  1. With marginal entropies, the excess bits are already optimal (Proposition 5), so no entropy-based rule can safely commit more.
  2. Full marginal vectors are a free refinement, but substantially more safe parallelism requires conditional queries, best used through the residual coupling (Proposition 10).
  3. 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 KL(Pi∥P^i)>0\mathrm{KL}(P_i\Vert\hat P_i)>0, with PiP_i 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 zz and at each clamped state z[a←v]z[a\leftarrow v] 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).

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

Parallel decoding in masked diffusion language models commits a set of positions from a product of marginals, with an error governed by the conditional total correlation (TC) of the set, which the sampler cannot observe. The paper asks how much of this dependence can be certified from the information available to the sampler, defining the tightest certificate as the supremum of TC over all joint laws consistent with the observations. It shows that (i) from marginal entropies alone the excess-bit criterion of Ben-Hamu et al. is tightest when the vocabulary is large relative to the entropies; (ii) from full marginal vectors the tightest certificate is given by a minimum-entropy coupling and can be smaller than the excess bits by an amount of order log|V|; (iii) from truncated conditional queries a residual coupling gives the tightest certificate, with computable brackets. These guarantees require the queried distributions to be exact conditionals of the target; the paper gives necessary-condition tests for coherence and reports violations on some saved LLaDA-8B states. Finally it studies the one position left unconstrained by the excess-bit criterion and shows that anchoring it at the most uncertain position adds no parallelism and can increase dependence. Experiments use sources with known joint laws, saved LLaDA states, and GSM8K and MBPP generations.

Critical strengths
  1. A principled characterization of what each level of information can certify. Defining the tightest certificate as a supremum over all consistent joint laws gives a clean way to compare entropies, marginal vectors and conditional queries, and the paper gives matching results at each level: the excess bits are optimal for entropy-only information under a simple condition on the vocabulary, minimum-entropy couplings characterize the marginal-only limit with computable brackets, and a residual coupling characterizes the truncated-query case. This turns a heuristic criterion used in practice into a statement about what can and cannot be guaranteed.

  2. Honest treatment of the limits, including a testable necessary condition. The paper states that the certificates hold only for exact outputs, provides necessary-condition tests for coherence, and reports on LLaDA that the condition fails on some states, while being explicit that this is an existence result and does not separate model incoherence from reduced precision. The mixed decoding results are reported rather than hidden.

Critical weaknesses
  1. The "fundamental limits" are worst-case and their practical relevance is weak. The tightest certificate is a supremum over all joint laws compatible with the observations, and the paper does not measure how far it is from the actual dependence on natural text. Its own tractable-source experiments suggest the gap matters: with truncated queries, a large fraction of sets that meet the budget provably cannot be certified, and this fraction becomes small only when most of the anchor's mass is queried, at a considerably higher query cost. Moreover, the certificates are guarantees only for exact outputs, and the paper's own tests show that some LLaDA outputs are not even mutually coherent, so on the models of interest they cannot be read as guarantees. The paper therefore characterizes what is impossible under worst-case assumptions without showing that this limit matters for the dependence that real samplers face.

  2. No improvement for real decoding is obtained. The analysis does not lead to a better sampler or criterion. The richer certificates need additional forward passes per step, which cancel the gain in parallelism. The only constructive element, the anchored variant of the excess-bit sampler, adds no parallelism by the paper's own result, and its effect is not consistent: it helps on some tractable sources and in some small-budget MBPP settings, but is worse on GSM8K and at larger MBPP budgets, so the ordering depends on the task, the budget and the commit law. The paper itself notes that these measurements do not disentangle dependence, model error, incoherence and changes in visited states. A reader thus learns what can be certified at each information level, but not what should be done differently when decoding, and the state-level evidence on real models is limited to one model and a small set of development prompts.

Questions for authors
  1. Could the authors explain how closely they expect the worst-case certificates to reflect the dependence encountered in realistic text generation?
  2. When should a practitioner expect richer conditional information or anchoring to improve parallel decoding over the simpler excess-bit or prefix rules?
4 comments

Thank you for the precise summary and for recognizing both the characterization of what each information level can certify and the explicit treatment of its limitations. We address your two questions below. The revised Section 6 separates certification on known sources, residual-score decoding, compatibility diagnostics, and free-position selection, and we have added decoding and matched-precision evaluations. Purple text marks relocated existing material and orange text marks new or revised material; references use the revised numbering, with earlier table numbers given as "formerly".

Q1 / W1: How closely do worst-case certificates reflect realistic dependence?

In short. On sources with known joint laws, certificates from marginal information alone are about five to nine times the actual total correlation, while certificates from queried conditionals approach it as the queries cover more of the anchor's mass. The gap to natural-text target TC remains unmeasured; the LLaDA replay panel instead tests compatibility of the model outputs.

Why the worst case. A certificate must hold for every joint law compatible with the observed information, so the supremum in Definition 4 is the smallest bound that is valid from that information, not an extra assumption. Under the sufficient condition of Proposition 5, no guarantee computed from marginal entropies alone can be smaller than the excess bits, the quantity that the entropy-bounded sampler of Ben-Hamu et al. (2025) keeps below a threshold. As you note, this turns a criterion used in practice into a statement about what it guarantees; it does not imply that a particular target law attains the bound.

Where the target is known. On the mixture and Markov sources, the mean excess-bit bound is about nine times the mean TC and the mean major-profile bound about eight times (Table 5, formerly Table 4). Even the average lower bound on the optimal marginal-only certificate is 4.8 to 5.4 times the mean TC (Appendix F.1.1), so a substantial gap persists even with optimal use of the marginal information. For two positions with exact outputs, the optimal residual certificate satisfies

0≤βR⋆(S)−TC(P)≤rlog⁡2∣V∣,0\le\beta_R^\star(S)-\mathrm{TC}(P)\le r\log_2|\mathcal V|,

where rr is the unqueried anchor mass (Appendix B.4), so the information gap closes as the queries cover more of the anchor's mass. On the larger-vocabulary mixtures, the computable bracket is at most 0.032 bits wide on average (Table 11, formerly Table 10), while the information gap can remain large: for ∣V∣≥16|\mathcal V|\ge 16, queries targeting 80% of the anchor's mass leave 44.6% to 67.8% of all pairs within the true TC budget of 0.25 bits yet provably uncertifiable; at a 95% target this falls to 3.6% to 4.2%, but requires 9.6 to 46.0 queried values on average, each costing a forward pass.

What carries over to LLaDA. LLaDA's conditionals are peaked: on the development prompts, eight queried values already cover 95.1% to 99.8% of the mass on average across the two highest-entropy anchors in each set (Table 15 in Appendix F.2, formerly Table 13). This retained mass alone does not determine the gap to natural-text target TC. You noted that the submission did not separate incompatibility from reduced precision. We now recompute 140 saved states from 35 GSM8K evaluation items, a panel separate from the development prompts, in bf16 and fp32 with identical inputs and queried tokens (Section 6.3; Appendices E.7 and F.6). The probability-level statistic D8D_8 (Proposition 15) averages 0.121 in bf16 and 0.120 in fp32 (Table 18). Both runs load the same bf16-stored checkpoint, so the incompatibility is not an artifact of inference precision. We therefore treat learned-model scores as diagnostics, separate from target-error guarantees, which require exact outputs or the error budgets of Appendix B.6.

Q2 / W2: When should richer information or anchoring help a practitioner?

In short. The excess-bit criterion with the entropy-ordered prefix remains a reasonable default. Full marginal vectors tighten the certificate at no extra forward pass. Conditional queries yield guarantees only if the queried outputs are compatible, and speed only if the extra passes cost less than the decoding steps they save. Anchoring's only guarantee, more committed information, requires exact marginals and an entropy gap above the budget (Corollary 17), so it should be adopted only after a task-specific comparison of quality and cost. The three decisions in more detail:

  1. Without extra denoiser passes. When Proposition 5 applies, a tighter guarantee requires more than marginal entropies. The major-profile bound uses the already available marginal vectors and satisfies eMP(S)≤e(S)e_{\mathrm{MP}}(S)\le e(S), with O~(∣S∣2∣V∣)\widetilde O(|S|^2|\mathcal V|) arithmetic (Proposition 6). This can improve certification without extra model passes, although it does not remove the gap to actual TC. The major-profile result is supported by the known-source evaluations; the LLaDA experiment uses marginal-meet scores as a no-query baseline.

  2. With conditional queries. At a fixed query budget and under exact outputs, using residual constraints can certify sets that discarding the unqueried contribution cannot. In the four-symbol pair experiment with two queried values, certification rises from 24.8% to 48.5% with the computable residual bound, or 50.0% with the exact optimum (Table 2). This gain uses the same queried information. Obtaining that information has a separate cost: a single-anchor step costs 1+k1+k forward evaluations, and in the earlier tractable-source comparison the increased parallelism did not offset that cost (Table 6, formerly Table 5).

    We now evaluate the decoding effect directly on 200 items each from GSM8K, MBPP, IFEval and CNN/DailyMail, with argmax and categorical commits (Section 6.2, Table 3; Appendices E.6 and F.5). The residual-meet rule D scores candidate sets with the computable residual certificate of Proposition 10(ii), and the discarding-meet rule C with the certificate that discards unqueried values; their strict variants share candidate generation and one queried value per step and reject candidates with invalid residual laws. All 32 adjusted quality-difference intervals across both budgets and strict and proxy variants include zero, establishing neither improvement nor equivalence. Cost effects vary: for CNN/DailyMail with categorical commits at the strict four-bit budget, D uses 2.8% fewer forward evaluations, but preserved quality with lower latency is not established. We do not obtain a consistently better decoder.

    The offline query-budget analysis tests whether more queried values remain usable under the strict residual checks, with MASK excluded from the scoring support. On the fixed 140-state panel, at the minimum-entropy anchor and a four-bit score budget, no conditional candidate passes at k=4k=4 or k=8k=8 in either precision, so C and D select singletons (Table 4). A negative residual entry certifies that the queried outputs are not conditionals of one joint law (Proposition 13(ii)), and adding queried values can only lower these entries; with the single queried value used in decoding, fewer terms are subtracted and some multi-token candidates pass, which is why C and D can differ in Table 3. This identifies a compatibility obstacle for those model-score selections; it does not measure natural-text target TC or explain the quality differences between trajectories. In practice, the strict residual check requires no additional model queries for our strict C/D rules.

  1. Anchoring versus the prefix. Anchoring adds no per-step parallelism at a fixed state and excess-bit budget (Proposition 16). Under exact marginals, it commits strictly more information when h^(m)−h^(J(e)+1)>e\hat h_{(m)}-\hat h_{(J(e)+1)}>e (Corollary 17); this is a sufficient condition for an information gain, not a guarantee of better generation. On the controlled exact source, anchoring achieves realized TV 0.0408 versus 0.0568 for the prefix at six expected forward evaluations (Table 13, formerly Table 12). Anchoring can increase dependence even with exact marginals (Remark 25), and Theorem 3(v) makes explicit the contribution of prediction error at the chosen anchor: in the controlled corruption experiment, the fraction of states where anchoring has lower TV than the prefix falls from 98.3% to 68.6% as corruption concentrates at uncertain positions (Appendix E.1).

    The complete-generation evaluation covers all 1,319 GSM8K and 500 MBPP test problems (Section 6.4; Table 17, formerly Table 15). As you noted, anchoring helps at small MBPP budgets, and it uses fewer forward evaluations at the same budget in 9 of the 10 configurations. Across the MBPP entropy-rule configurations, however, the highest observed accuracy is 17.80% for the prefix at 17.90 NFE, versus 16.40% for anchoring at 31.25 NFE; both remain below the 64-step schedule's 20.00%. On GSM8K the prefix is more accurate at e=1e=1 under both commit laws, while at comparable NFE the argmax comparison establishes neither superiority nor equivalence. We therefore recommend the prefix as the default unless a task-specific comparison of quality and cost supports anchoring; high marginal entropy alone is not a reason to switch.

The revision makes these consequences explicit: richer information can improve a guarantee, query cost and compatibility determine whether it is usable, and the remaining token-selection freedom needs its own quality and cost evaluation. The new panel and decoding runs extend the evidence on real models beyond the development prompts, though still for a single model. We thank the reviewer for the questions that helped us connect the information limits to these decoding decisions, and we would be grateful if you would reconsider your assessment in light of them.

Thank you for the detailed response and additional experiments. They address some of my concerns and clarify the scope of the results. However, my main concern remains: the paper is still primarily an analysis of certificates and their limitations, without demonstrating an effective practical solution or consistent decoding improvement. I therefore maintain my original score.

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

This paper studies how much token dependence can be reliably bounded when masked diffusion models generate multiple tokens in parallel. It characterizes the tightest bounds obtainable from marginal predictions and limited conditional queries, including a way to account for unquerid values. The authors also examine token selection under a fixed entropy budget. Experiments highlight both the benefits of tighter bounds and the difficulties of applying these guarantees to practical decoding.

Critical strengths

S1. Sharp characterization of dependence bounds

This paper establishes when the excess-bit bound is optimal given only marginal entropies and characterizes the tightest marginal bound through coupling. The accompanying computable bounds also quantify how closely this optimum can be reached.

S2. Effective use of truncated conditional queries

The residual coupling formulation uses marginal constraints to account for unquereid token values rather than discarding. It yields the tightest certificate for the queries, with computable bounds, which separate approx. error from missing information. Controlled experiments show gainsat the same query budget.

Critical weaknesses

W1. Applicability and practical value of the theoretical guarantees

The bounds derived from conditional queries assume that the denoiser provides exact marginals and conditionals of the target joint distribution. However, the LLaDA experiments reveal violations of coherence among the conditional distributions, without distinguishing model inconsistency from numerical precision effects. Moreover, the paper does not evaluate a decoder that incorporates its main proposal, residual coupling, while experiments with a separate depth method show that the cost of additional forward passes outweighs the reduction in decoding steps. To establish the practical relevance of these theoretical results, the authors should examine how model prediction errors and numerical precision affect the guarantees, and evaluate decoding based on the certificates against existing approaches at comparable compute, considering both generation quality and efficiency.

W2. Gap between optimal bounds and actual dependence

While their analysis characterizes the tightest TC bounds given the available information, these bounds can remain far above the actual dependence. The synthetic experiments suggest that missing conditional information, rather than approximation error, is the main limitation for larger vocabularies. On this point it would be needed, for example, to assess how much parallel decoding these bounds can certify under realistic query budgets.

Questions for authors

How tight are the cumulative error bounds derived from per-step TC certificates compared with the actual final-output error?

(primary concerns are described in the Critical Weaknesses section above)

4 comments

Thank you for the detailed review and for recognizing the sharp characterization of the bounds and the residual coupling's use of marginal constraints (S1, S2). We agree that the guarantees for conditional queries presuppose exact outputs, and the revision adds the evaluations you requested; we address them in turn. On presentation, Section 6 now separates certification on known sources from model-score behavior on LLaDA and introduces each question and its setup before the results; we also define certificate and excess bits at first use and clarify the captions and notation. The general response lists all changes.

W1: prediction errors and the guarantees

For a product commit Q=⨂i∈SP^iQ=\bigotimes_{i\in S}\hat P_i, Theorem 3(i) gives

KL(P∥Q)=TC(P)+∑i∈SKL(Pi∥P^i),\mathrm{KL}(P\Vert Q)=\mathrm{TC}(P)+\sum_{i\in S}\mathrm{KL}(P_i\Vert\hat P_i),

so a valid TC certificate bounds the commit error only together with the marginal errors. At the entropy level, a calibration budget ∑i∈S∣H(Pi)−H(P^i)∣≤δ\sum_{i\in S}|H(P_i)-H(\hat P_i)|\le\delta gives TC(P)≤e⋆(S)≤e(S)+2δ\mathrm{TC}(P)\le e^\star(S)\le e(S)+2\delta (Appendix B.6), so the excess-bit certificate degrades additively. For depth-2 queries, Proposition 24 gives, for any denoiser,

KL(P∥Q)≤∑i∈S∖{a}CE(Pi,P^i)+KL(Pa∥P^a)−max⁡{0,H^θ(Xb∣Xa)−Δˉ},\mathrm{KL}(P\Vert Q)\le\sum_{i\in S\setminus\lbrace a\rbrace}\mathrm{CE}(P_i,\hat P_i)+\mathrm{KL}(P_a\Vert\hat P_a)-\max\lbrace 0,\hat H_\theta(X_b\mid X_a)-\bar\Delta\rbrace,

where the first two terms form Theorem 3(v), H^θ(Xb∣Xa)\hat H_\theta(X_b\mid X_a) is read from the queried outputs, possibly truncated to the kk queried values, and Δˉ\bar\Delta converts total-variation budgets on the anchor marginal and the order-induced pair law into an entropy correction.

With a known target, ignoring prediction error breaks validity and these corrections restore it. Under a noisy-logit denoiser, the uncorrected depth-2 expression falls below the true divergence in 48.2% of 4,000 state–set pairs, and neither calibration-aware form ever does (Table 7, formerly Table 6); for three EM-fitted denoisers with model errors of 0.007 to 0.34 in total variation, the exact-marginal bound fails at every singleton reveal set, whereas Theorem 3(v) never fails (Appendix F.1.3). These quantities involve the target law and serve offline validation; we have not estimated them for LLaDA and make no target-error claim there.

W1: numerical precision

We recomputed 140 saved states from 35 GSM8K evaluation items, a panel separate from the submission's 35 development prompts, in bf16 and fp32 with identical inputs, queried token IDs and candidate sets (Appendices E.7 and F.6, Table 18). Both runs load the released checkpoint, whose weights are stored in bf16, so the comparison isolates inference arithmetic. With eight queried values per direction, the probability-level statistic D8D_8 of Proposition 15, which lower-bounds the total variation between the two order-induced pair laws and is zero for coherent outputs, averages 0.121 in bf16 and 0.120 in fp32. The paired difference is 0.0014 (descriptive 95% interval clustered by item, [−0.0010, 0.0039]), so fp32 changes the statistic by about 1%, at most about 3% within the interval. The incompatibility is therefore a property of the released model, not of bf16 arithmetic.

W1: decoding with the residual correction

We added this evaluation on LLaDA-8B-Instruct (Section 6.2, Table 3; Appendices E.6 and F.5): 200 items each from GSM8K, MBPP, IFEval and CNN/DailyMail, with argmax and categorical commits. The residual-meet rule D scores candidate sets with the computable residual certificate of Proposition 10(ii), and the discarding-meet rule C with the certificate that discards unqueried values; their strict variants share candidate generation and one queried value per step and reject candidates with invalid residual laws, so C and D differ only in the residual correction. Total forward evaluations (NFE) and request time are measured as outcomes alongside quality, with no-query baselines: fixed confidence schedules, the entropy-bounded prefix and marginal-meet decoding.

All 32 adjusted intervals for the quality difference between D and C (four tasks, two commit modes, two budgets, strict and proxy variants) include zero, so we claim neither an improvement nor equivalence. Cost effects vary across settings; where the cost differs clearly, as for CNN/DailyMail with categorical commits at the strict four-bit budget, D uses 2.8% fewer forward evaluations (ratio 0.9722, Bonferroni-adjusted interval [0.9498, 0.9935]), but the D − C interval for ROUGE-Lsum F1, [−0.0050, 0.0092], and the request-time ratio interval, [0.9601, 1.0028], do not establish preserved quality at lower latency. Table 3 reports the strict four-bit C/D comparison; supplementary Table S28 reports quality, NFE and request time at all operating points, including fixed confidence schedules, the entropy-bounded prefix and marginal-meet decoding. A step with one queried value nominally costs two forward passes; the reported NFE accounts for eligible clamped-output reuse. We claim no advantage over the no-query baselines, consistent with the query-cost trade-off in the earlier depth-2 study (Table 6, formerly Table 5). On LLaDA the scores also carry no guarantee, so we present residual-score decoding as a controlled test of the certificates, not as a faster sampler.

W2: the gap to actual dependence under realistic query budgets

We agree that information-optimal certificates can remain far above TC; the paper measures how much of this gap is missing information. On the larger-vocabulary mixtures with ∣V∣≥16|\mathcal V|\ge 16 (Table 11, formerly Table 10), the computable bracket is at most 0.032 bits wide on average, so missing information dominates the remaining gap. When queries target 80% of the anchor's mass, 44.6% to 67.8% of all pairs meet the budget τ=0.25\tau=0.25 bits yet provably cannot be certified. At a 95% target, the computable residual bound certifies 62% to 72% of all pairs, about 94% of those that meet the budget, but this takes 1.7 to 2.9 times as many queries as at the 80% target, 9.6 to 46.0 values on average, and each queried value costs a forward pass.

On the LLaDA development prompts, eight queried values cover 95.1% to 99.8% of the mass on average across the two highest-entropy anchors in each set (Table 15 in Appendix F.2, formerly Table 13). The gap to natural-text target TC remains unmeasured. Separately, we added an offline analysis of the 140 matched states (Section 6.3, Table 4). At the minimum-entropy anchor and a four-bit score budget, no conditional candidate passes the strict residual checks at k=4k=4 or k=8k=8, in bf16 or fp32, so C and D select only singletons. A negative residual entry certifies that the queried outputs are not conditionals of one joint law (Proposition 13(ii)), and adding queried values can only lower these entries, so larger budgets expose more of this incompatibility. Conversely, with the single queried value used in decoding, fewer terms are subtracted and some multi-token candidates pass, which is why C and D can differ in Table 3. On this panel at k≥4k\ge 4, the strict rules therefore commit one token per step, showing a compatibility obstacle for these model-score selections. Target-certified parallelism on natural text would further require the calibration budgets discussed in Appendix B.6, which we do not claim.

Question: cumulative bounds versus final-output error

Under exact outputs, Theorem 27 gives the following identity, where Pk,SkP_{k,S_k} is the target joint law of the selected coordinates at the realized state ZkZ_k:

KL(ν∥μ)=∑k≥0EZk∼ν[TC(Pk,Sk)],\mathrm{KL}(\nu\Vert\mu)=\sum_{k\ge 0}\mathbb E_{Z_k\sim\nu}\big[\mathrm{TC}(P_{k,S_k})\big],

so accumulation itself adds no slack. Replacing each TC by a per-step certificate βk\beta_k gives B=∑k≥0EZk∼ν[βk]≥KL(ν∥μ)B=\sum_{k\ge 0}\mathbb E_{Z_k\sim\nu}[\beta_k]\ge\mathrm{KL}(\nu\Vert\mu), and Remark 28 converts it by TV(μ,ν)≤min⁡{((ln⁡2/2)B)1/2,(1−2−B)1/2}\mathrm{TV}(\mu,\nu)\le\min\lbrace((\ln 2/2)B)^{1/2},(1-2^{-B})^{1/2}\rbrace. The slack therefore has two separable sources: the certificate and the conversion. Appendix F.7 (Table 19, Figures 1–2) measures both on 80 synthetic cases (source, seed and reveal policy) and ten singleton controls, with exactly enumerated final distributions and the policy and output law held fixed; the original trajectory table, now Table S26, checks the identity itself.

Table 19 summarizes the 80 cases as medians and ranges over five seeds; supplementary Tables S40–S42 report the individual cases. We illustrate with one pairwise case. On the mixture source with seed 0 and commits of size two, the exact final KL is 0.205 bits and the exact TV is 0.207. The accumulated excess bits give 4.62 bits, 22.6 times the exact KL, and the residual certificate gives 2.12 and 0.724 bits with one and two queried values, 10.3 and 3.5 times. With three or four of the four values queried, it equals the exact KL: for commits of size two, querying all but one value always makes each per-step certificate exact, because the marginal constraint determines the remaining conditional. Larger commit sets can retain slack even with complete queries. Even with the exact KL, the converted TV bound is 0.266 against the exact 0.207, so closing the certificate gap leaves the conversion gap. These quantities are computable only on known sources; this is not an operational guarantee for LLaDA.

We hope these results address W1 and W2. The certificates are tight for the information they use, prediction error enters through explicit budgets, numerical precision does not explain the incompatibility on LLaDA, and the replay panel exposes a compatibility obstacle for strict model-score selection. We would be grateful if you would reconsider your assessment in light of these results.

Reviewer_pxFUOpenReview ↗

Assessment after rebuttal

Thank you for the response and the additional experiments. However, my main concerns about practical applicability remain. Theoretical guarantees have not been established for LLaDA, and the new decoding results do not show a clear quality–compute advantage over the no-query baselines. The strict rules also select only singletons at k = 4,8 in the replay. The synthetic experiments help clarify the bounds,yet their tightness on natural text remains unknown.

I therefore maintain my original rating.

Comments on the paper

2 comments

General Response (2): Learned outputs, and the completed evaluations

Learned outputs

Theorem 3(v) bounds the commit error of any denoiser: for every a∈Sa\in S,

KL(P∥Q)≤∑i∈S∖{a}CE(Pi,P^i)+KL(Pa∥P^a),\mathrm{KL}(P\Vert Q)\le\sum_{i\in S\setminus\lbrace a\rbrace}\mathrm{CE}(P_i,\hat P_i)+\mathrm{KL}(P_a\Vert\hat P_a),

and Appendix B.6 gives inference-time certificates under explicit error budgets. Coherence is a necessary condition for the exact-output interpretation, but does not establish agreement with the target distribution. On LLaDA we therefore report model-score decoding, which evaluates the same formulas on the model's outputs without a guarantee, and compatibility diagnostics, not certification.

Free position

At a fixed excess-bit budget, anchoring the free position at the most uncertain token adds no per-step parallelism (Proposition 16). With exact marginals it commits more information when the entropy gap exceeds the budget (Corollary 17), but taking aa as that position in the bound above shows that its commit error carries the model error KL(Pa∥P^a)\mathrm{KL}(P_a\Vert\hat P_a) where the model is most uncertain. The entropy-ordered prefix appears to be a reasonable default in the settings studied here (Section 6.4).

Completed evaluations

  • Residual-score decoding (Section 6.2, Table 3). On 200 items each from GSM8K, MBPP, IFEval and CNN/DailyMail, we compare the residual-meet rule, which scores candidate sets with the computable residual certificate of Proposition 10(ii), with the discarding-meet rule; both use the same candidate-generation and per-step query policies, with one queried value per step, so they differ only in the residual correction. Quality, total forward evaluations, and request time are reported against no-query baselines: fixed confidence schedules, the entropy-bounded prefix, and marginal-meet decoding. All 32 adjusted quality-difference intervals between the two rules include zero, and cost effects vary across settings; for CNN/DailyMail with categorical commits at the strict four-bit budget, the residual correction uses 2.8% fewer forward evaluations without an established latency gain. These evaluations do not establish a consistently better decoder or a quality-preserving latency improvement, consistent with the analysis: queries cost forward passes, and on LLaDA the scores carry no guarantee.
  • Precision and query budgets (Section 6.3; Tables 4 and 18). We recompute 140 saved states from 35 GSM8K evaluation items, a panel separate from the submission's development prompts, in bf16 and fp32 with the same inputs and queried tokens. The probability-level incompatibility statistic D8D_8 averages 0.121 in bf16 and 0.120 in fp32, a paired difference of about 1%. Both runs load the released checkpoint, whose weights are stored in bf16, so fp32 removes arithmetic rounding; incompatibility that persists in fp32 is a property of the released model. At the minimum-entropy anchor and a four-bit score budget, with four or eight queried values, no conditional candidate passes the strict residual checks, so the query-based rules commit one token per step. The analysis covers this fixed panel of states.
  • Cumulative bounds (Appendix F.7). On 80 synthetic cases (combinations of source, seed, and reveal policy) and ten singleton controls, we compare accumulated computable certificates with the exactly enumerated final KL and TV, holding the policy and output law fixed. This separates certificate conservatism from KL-to-TV conversion. In a pairwise example, the accumulated excess bits exceed the exact KL by a factor of 22.6, the residual certificate becomes exact once all but one value is queried, and the conversion still gives a TV bound of 0.266 against an exact 0.207.

General Response (1): Presentation, and what the certificates imply

We thank the reviewers for their careful reading and for recognizing the systematic characterization of the tightest dependence certificates at each level of information. Two concerns were shared: the presentation, especially Section 6, and the practical value of certificates defined by a worst case. We have revised the presentation and completed additional evaluations of decoding, numerical precision, and cumulative error bounds. 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.

To help locate the changes relative to the submitted PDFs, the revised paper and supplementary material mark relocated existing content in purple and new or revised content in orange. Colors within plots retain their analytical meaning. Section and table numbers refer to the revised PDF; where a table number changed, the submission's number follows as "formerly".

Presentation changes

Section 6 now separates information and certification (6.1), residual-score decoding (6.2), output compatibility (6.3), and free-position selection (6.4). Each subsection introduces its question and setup before interpreting the results. We define certificate and excess bits at first use, introduce depth and query count before the experiments, and clarify the table captions and notation. Detailed numerical results remain in the appendices and supplementary material.

What the tightest certificate means

For categorical product commits with exact marginals, the one-step forward KL error equals total correlation: KL(P∥Q)=TC(P)\mathrm{KL}(P\Vert Q)=\mathrm{TC}(P) (Theorem 3(i)). A certificate upper-bounds TC for every joint law compatible with the observed information. Its tightest value is the supremum over those laws (Definition 4). This identifies the smallest universally valid bound obtainable from that information; it can still exceed the dependence of the particular target law. Our results distinguish that information gap from computational approximation.

Implications for decoder design

Under the exact-output premise:

  1. Marginal entropies. The excess bits e(S)=∑i∈Sh^i−max⁡i∈Sh^ie(S)=\sum_{i\in S}\hat h_i-\max_{i\in S}\hat h_i are the quantity controlled by the entropy-bounded sampler of Ben-Hamu et al. (2025). Proposition 5 gives a simple sufficient condition, max⁡ih^i+∣S∣≤log⁡2∣V∣\max_i\hat h_i+|S|\le\log_2|\mathcal V| (for LLaDA, max⁡ih^i≤16.9−∣S∣\max_i\hat h_i\le 16.9-|S| bits), under which no smaller universally valid TC bound follows from those entropies alone. A rule that certifies more must use more than entropies.
  2. Full marginal vectors. The major-profile bound satisfies eMP(S)≤e(S)e_{\mathrm{MP}}(S)\le e(S) and requires no additional denoiser pass, with O~(∣S∣2∣V∣)\widetilde O(|S|^2|\mathcal V|) arithmetic (Proposition 6). Its bracket measures the distance to the best marginal-only certificate, not to the actual TC, and the latter gap can remain large: on our tractable sources, eMPe_{\mathrm{MP}} averages about eight times the actual TC (Table 5, formerly Table 4), and even a lower bound on every marginal-only certificate averages 4.8 to 5.4 times it (Appendix F.1.1). Marginal shape is a free refinement, not a remedy.
  3. Truncated conditional queries. Proposition 10(ii) characterizes the optimal use of the retained conditionals together with the residual marginal constraints. With two queried values in the four-symbol pair experiment, the certified fraction rises from 24.8% for discarding to 48.5% for the computable residual bound, or 50.0% for the exact optimum (Table 2). In the larger-vocabulary study, the computable bound exceeds the exact optimum by at most 0.032 bits on average (Table 11, formerly Table 10), so missing conditional information dominates the remaining gap to TC. For two positions this gap is controlled by the unqueried anchor mass rr: βR⋆−TC≤rlog⁡2∣V∣\beta_R^\star-\mathrm{TC}\le r\log_2|\mathcal V| (Appendix B.4).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.