acceptodds
Under review as a conference paper at ICLR 2027

The Lattice of Transition Laws

Abstract

Diffusion and autoregression (AR) have long been seen as different categories of generative models, with diffusion specialising in continuous fields and AR specialising in discrete tokens. Recent work seeks to combine the advantages of the two models, and each hybrid fixes its decoding schedule by design. In this paper, we ask whether the performance of decoding schedules of one model can be predicted before decoding at a fixed number of steps. We describe diffusion, AR, and models in between as paths on one corruption lattice, and define the cost of a schedule as the dependence its parallel steps discard. The cost shows that the fewest steps of a zero-cost schedule are set by the geometry of the data, in the same way for tokens and for continuous fields. In particular, for data that are Markov on a graph and dependent along its paths, the fewest steps equal the graph's treedepth, which is logarithmic in the length of a sequence and linear in the side length of a grid. With fewer steps than the treedepth, every schedule pays a positive cost, whose ranking we predict before decoding with a kernel of pairwise dependence estimated from pretrained weights. Across text generation, image generation, and video generation, we verify most of the predictions about the rankings of different schedules under different metrics and benchmarks. This work therefore provides a design principle for decoding for future AR models, diffusion models, and anything in between.

Primary area:
generative models
Keywords:
Diffusion, AR, Generative AI

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_T6G7OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper puts autoregressive, diffusion, and intermediate decoding schedules into a common framework: a schedule is a monotone path on a lattice of coordinate-wise corruption levels. A parallel transition is assigned a dependence cost given by the conditional total correlation lost when the exact joint transition is replaced by a product of coordinate conditionals. Under exact transitions, the sum of these costs is exactly the path-space KL divergence between joint and factorized sampling. For graph-Markov data, the paper further relates the minimum number of zero-cost steps to graph treedepth.

Since the exact cost is generally unavailable, the practical method estimates a pairwise dependence kernel from pretrained model weights and uses it to compare or construct schedules. The empirical section covers text8, MAR-B on ImageNet-256, LLaDA-8B, and Diffusion Forcing for video. Across these settings, spatially or sequentially separated updates are usually better than clustered updates at small step budgets, although the estimated cost does not always predict the ordering among the stronger schedules.

Critical strengths
  1. The main theoretical picture is clean and useful. In particular, the KL/total-correlation identity makes precise what is lost by parallelizing a transition, and the treedepth result gives a nontrivial structural answer to when zero-cost parallel schedules exist. I found this connection more illuminating than treating each decoding family separately.

  2. Several experiments are unusually well controlled for a scheduling paper. For example, the MAR-B weights and step budget are fixed while only the reveal order changes; at eight steps, the spread schedule improves FID from 13.02 to 9.44 relative to the model's random order. The LLaDA experiments show similarly large gains from simple separation constraints. The appendix is also candid about cases where the proxy does not predict the final ordering.

Critical weaknesses
  1. The practical pairwise score is a lower bound on total correlation, not a generally order-preserving estimator of it. Exactness is obtained for a first-order Markov reference, while the evaluated models can contain substantial higher-order dependence. This matters in the reported results: nested is predicted below random for MAR but has worse FID, and low-discrepancy sampling beats spread despite the predicted order. I therefore view the pairwise construction as a useful heuristic, but the current text sometimes gives it a stronger predictive interpretation than the evidence supports.

  2. I am less convinced by the transfer of the exact-transition theory to the finite-step continuous implementations. Proposition 1 concerns exact joint reverse kernels and their exact coordinate marginals, whereas the image and video experiments use conditional-mean or deterministic updates with model and discretization error. Those errors can themselves depend on the schedule. The paper discusses this qualitatively but does not show when the dependence-cost ordering should survive.

Questions for authors
  1. Can the authors give an error decomposition for the finite-step continuous updates relative to the exact-transition path in Proposition 1? In particular, under what conditions would model and discretization errors preserve the schedule ordering?

  2. Is there a checkable diagnostic for when the pairwise approximation is unreliable, or a practical higher-order correction? It would be helpful to use the MAR reversals as concrete test cases.

  3. Which schedule rankings were specified before decoding results were observed? A single table of predicted versus observed rankings, with rank correlation across all schedule-budget pairs, would make the empirical claim much easier to assess.

3 comments

Thank you for the careful reading and for your positive assessment. In the following, the numbers refer to the revised version.

W1: The pairwise estimate is a lower bound on the total correlation, and it equals the total correlation only when the selected tokens have first-order Markov dependence. With higher-order dependence it does not have to preserve the order, so we use it as a heuristic to rank schedules. We now state this in Section 5, where the estimate is introduced. How well it ranks is an empirical question, which we answer in Q3 below.

W2 and Q1: Yes, there is an exact decomposition. A step that samples each coordinate from its own model conditional q_i is a product law, and for any product law KL(p ‖ ∏ q_i) = TC(p) + Σ_i KL(p_i ‖ q_i), where p_i is the exact coordinate conditional. This is the decomposition of Ben-Hamu et al. (2025, eq. 7) for masked models, and it holds on every path and channel. Summed along the path, a decode departs from the exact path by the dependence cost of Proposition 1 plus the error of the model's coordinate conditionals. For a Gaussian update, the second term includes the discretisation error. The ordering by dependence cost is preserved when the second term varies less across schedules than the first. On the absorbing lattice every schedule commits each coordinate once, and MAR's diffusion head samples with the same settings under every order, so the second term differs between schedules only through the states at which coordinates are committed. We measure both terms on text8 in Section 6.3: the dependence term is several times larger when steps are wide, and the conditional term determines the ranking when they are narrow. We now state this decomposition in Section 3.

Q2: Yes, we give a diagnostic in Table 15, where we add the triplet term of Lemma 2's proof to the pairwise estimate. Where the triplet term is large relative to the pairwise one, as for contiguous selection (0.62 to 0.90 bits at 8 steps), the pairwise ranking is least reliable. For spread and the separator rule it changes the estimate by at most 0.01 at 8 and 32 steps. We also give a second correction for the rules that rely on separation: with the kernel measured after a reveal between the pair, the estimate accounts for most of the midpoint rule's excess on text8 (Table 17). We give both on text8. On MAR the head gives a law only through samples, so a triplet term built from its proxy kernels would not separate a higher-order effect from the error of the proxy.

Q3: We compute every ranking in the paper from the kernel and the schedule alone, with no decoded sample, except the two that we mark in the captions: spread-then-raster's floor (Table 2) and the confidence rule's estimate (Table 15). The new Table 29 (Appendix C.12) lists predicted against measured rankings for every schedule and budget, with rank correlations: Spearman 0.98 pooled on text8, and 0.71 from 8 to 32 steps on MAR-B.

If these address your concerns, we would be grateful if you could raise your score.

I thank the authors for their detailed response, which addresses some of my concerns. However, the ranking reversals observed on MAR and the reversal on LLaDA at 64 steps leave me only partially convinced that the method remains reliable when compared against stronger schedules. I will therefore maintain my current score.

Thank you for the follow up. It is true that our estimate cannot always rank the strongest schedules correctly, but these reversals only cause a small loss. On MAR-B, the rule that we predict as the best is within 0.15 FID of the measured best one from 16 steps. On LLaDA at 64 steps, the estimates of the rules only differ by 0.02 bits, so they are too close to rank. Thus, we can see that the estimate is reliable when the schedules clearly differ in their cost, and this is also where the choice of schedule matters most.

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

This paper studies whether decoding schedules can be compared before running generation. It represents autoregressive, diffusion, and intermediate schedules as monotone paths on a coordinatewise corruption lattice. For exact transition conditionals, it expresses the path KL divergence introduced by independent parallel updates as accumulated conditional total correlation. Under graph-Markov and persistent-dependence assumptions, it identifies graph treedepth as the minimum number of zero-cost decoding steps. It then proposes pairwise dependence kernels estimated from pretrained models as practical schedule-ranking proxies. Experiments on text8, MAR, LLaDA, and a video model examine these predictions and demonstrate benefits from spatially dispersed or distance-constrained updates.

Critical strengths
  1. A coherent structural account of parallel decoding. The combination of a corruption-lattice representation, an exact dependence-cost decomposition, and the treedepth characterization gives a useful account of when parallel updates can preserve the target distribution. The paper appropriately relates the absorbing-token identity to prior work and extends the discussion to intermediate levels and continuous channels. The most consequential contribution is the connection between schedule geometry and the dependence discarded by parallel sampling.
  2. Practical improvements with fixed pretrained weights. The experiments isolate schedule changes on released models. On MAR-B, spread selection improves 8-step FID from 13.02 to 9.44, while low-discrepancy selection reaches 8.32. On LLaDA, minimum-distance confidence selection improves GSM8K accuracy by 9.7 and 7.6 percentage points at 8 and 16 steps, respectively. The HumanEval results and reported low selection overhead further support the practical value of avoiding strongly dependent simultaneous updates.
Critical weaknesses
  1. The breadth of validation exceeds its strongest evidence. The text8 analysis is detailed, but its main cost measurements use teacher forcing, which avoids the state-distribution shifts encountered during generation. The free-generation and LLaDA experiments help, yet do not fully establish how reliably the estimated cost predicts downstream quality across settings. The video evidence is particularly limited: it uses only three prompts, varies the step budget with memory depth, and mostly finds differences that are not statistically distinguishable. This is insufficient to establish quality equivalence or strong predictive validity for video decoding.

  2. The practical estimator has weaker guarantees than the exact cost. Lemma 2 bounds total correlation using consecutive pairwise terms, but ranking these bounds need not rank the underlying costs. In addition, MAR uses prediction displacement and changes in head distributions as proxies for conditional mutual information. The observed failures are consequential: nested selection receives a lower estimated cost than random but has worse FID, while low-discrepancy outperforms spread despite the opposite predicted ordering.

Questions for authors
  1. How reliably does the pairwise estimator select the best, or a near-best, schedule across all tested rules and budgets? Please report rank correlation or selection regret, including the nested and low-discrepancy exceptions. This would clarify whether the method provides actionable schedule selection beyond identifying poor choices such as raster order.
  2. Please clarify the probability distribution used to average entropy reductions and head-law KL values when estimating the kernels. Under what consistency and averaging conditions do these estimates equal conditional mutual information, and when should they be interpreted solely as empirical proxies?
2 comments

Thank you for the careful summary and for your positive assessment. In the following, the numbers refer to the revised version.

W1: We also test free generation, where sampled tokens feed the later steps, and it ranks the rules in the same order at every parallel budget we test (8, 16 and 64 steps, Table 23). On the video test, we do not claim quality equivalence. The kernel between frames predicts no change with memory depth, and we report the video test as a test of this prediction. Our claims about the ranking rest on text8, MAR and LLaDA, which we quantify in Q1 below.

W2: On text8, where we can measure the cost, the estimate ranks the rules as the measured excess does at every budget (Table 5). We now state in Section 5 that the estimate is a lower bound on the cost, exact on a first-order Markov reference and a ranking heuristic beyond it. On MAR the displacement and the head KL are proxies, and the floors built from the two rank the rules alike, except two rules whose displacement floors are within 3% of each other (Appendix C.4).

Q1: We add rank correlations and the regret of the predicted best rule for every rule and budget (Appendix C.12, Table 29):

  • text8 (the 4 rules of Table 5, 2 to 32 steps): the Spearman correlation is 1.00 at every budget except 0.95 at 2 steps, and 0.98 pooled. The predicted best rule is the measured best at every budget.
  • MAR-B (7 orders against FID): 0.71 at 8, 16 and 32 steps and 0.50 at 64 with the displacement floor, and 0.86 at 8 steps with the information floor. The predicted best rule trails the measured best by 1.11 FID at 8 steps and by 0.15 or less from 16.
  • LLaDA (the position-only rules of Table 25 against perplexity): 1.00 at 8 and 16 steps, 0.50 at 32 and -0.50 at 64. The predicted best rule is the measured best up to 32 steps.

The selection is useful beyond ruling out raster order. Without raster, the information floor still ranks the other 6 MAR orders with Spearman 0.77 at 8 steps. The predicted best rule lowers FID from the model's own random order by 3.58 at 8 steps (13.02 to 9.44), against a regret of 1.11. The exceptions are nested and low-discrepancy on MAR, and LLaDA at 64 steps, where the estimates differ by only 0.02 bits. We list them next to the correlations in Table 29.

Q2: On text8, we mask held-out windows at rate 0.3, 0.5 or 0.7 and draw pairs at a controlled distance, within a word or across a word boundary. On LLaDA, we mask a held-out sequence at a rate, reveal one masked position to its true token, and read the entropy drop at every other masked position, binned by distance. On MAR, we perturb 64 ImageNet training images 8 times each at revealed fractions 0.25, 0.5 and 0.75, and read the relative displacement of the head's statistic and the KL of its law under a Gaussian fit. The text8 and LLaDA estimates equal the model's conditional mutual information when its conditionals come from one joint law, and the data's when the model matches the data. On MAR, the displacement and the head KL are empirical proxies.

We also note the ethics flag. The paper uses only public datasets and released weights and only changes how the models decode (Ethics Statement). We are glad to address any specific concern.

Thank you again for the constructive review.

Thank you for your responses and I think it resolves my concerns.

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

The paper places autoregressive, diffusion and hybrid decoding schedules on one "corruption lattice" and defines the dependence cost of a schedule as the total correlation discarded when coordinates updated in parallel are sampled from their own conditionals. For data Markov on a graph and dependent along its paths, the fewest zero-cost steps equal the graph's treedepth. Below that budget, schedules are ranked before decoding by a pairwise lower bound on the cost, computed from a dependence-versus-distance kernel estimated from a pretrained model. Predictions are tested on text8, MAR-B, LLaDA-8B and SkyReels-V2.

Critical strengths

The text8 part is a clean, falsifiable programme. The kernel is measured from the model, the pairwise estimate is computed before decoding and compared with the measured excess bpc over each schedule's own exact chain (Tables 5, 13, 17), and a kernel from a 26M model predicts the ranking for an 85M model. This is the one place where the paper goes beyond ordering heuristics, and the paper also reports its failed predictions.

Critical weaknesses

My main concern is that the two central theoretical objects are known. Proposition 1 is credited to Chen et al. (2026) and Cai & Li (2026), but the same quantity appears earlier in [1] (Prop. 1), [2] (eq. 7) and as the "entropy gap" of DUS [3] (Cor. 3.4), none of which is connected to it; the extension to interior levels and continuous channels is immediate. Theorem 1 is a direct translation of treedepth as minimum elimination-tree height, which the paper cites, and the operative rule, spacing parallel positions because dependence decays with distance, is already the rationale of the Halton scheduler and of DUS. The assumption carrying Theorem 1 also fails in the tested domains: Appendix C.2 concedes that on text a revealed character "does not separate its neighbours in the sense of Theorem 1", on MAR the separator-based nested rule reads above random (13.73 vs 13.02 FID at 8 steps, Table 3), and §6.4 falls back to "distance sets the ranking". I believe the real contribution is the kernel-based ranking estimate validated on text8, and the paper should be framed around it.

Second, the released-model experiments do not isolate the contribution, and the regime where the cost discriminates is not the deployed one. Table 4 reports only changes in GSM8K accuracy against plain confidence at 8–32 steps, and the adaptive parallel samplers that encode the same idea on LLaDA (Fast-dLLM, EB-sampler [2], DUS, which Table 1 marks as tested only on text8) are absent. By the paper's own §6.3, at 16–32 steps the ranking is set by conditional error, which lies outside the cost. The cost therefore separates schedules only where quality is far from deployed (text8 bpc 1.6–3 vs 1.32; MAR FID 8–14 vs 2.3). The claim that the cost works "in the same way for tokens and continuous fields" is never tested as a cost prediction: Table 7 gives single-run differences of about 1 FID, and the video test is a no-change prediction on three prompts.

[1] Liu et al. Discrete Copula Diffusion. ICLR 2025. [2] Ben-Hamu et al. Accelerated Sampling from Masked Diffusion Models via Entropy Bounded Unmasking. NeurIPS 2025. [3] Luxembourg et al. Plan for Speed: Dilated Scheduling for Masked Diffusion Language Models. ICML 2026 (arXiv 2506.19037v5).

Questions for authors
  1. How does Proposition 1 differ from Prop. 1 of [1], eq. 7 of [2] and Cor. 3.4 of [3]? If only by interior levels and continuous channels, please state the contribution as that.
  2. Is there any tested setting in which separation, rather than distance, predicts a measured ranking? If not, what role does Theorem 1 play in the experiments?
  3. Please report absolute GSM8K accuracies at 8–32 steps for Table 4, and compare the constrained rules with Fast-dLLM, EB-sampler and DUS on LLaDA at matched forward passes.
  4. Please show the LLaDA kernel and the pairwise estimates behind Table 25, so the 64-step reversal can be checked.
  5. Can the cost be estimated and compared with a measured quantity on a continuous channel, as Table 5 does for tokens? A DDPM step (eq. 1) does not sample the product of conditionals in Proposition 1.
4 comments

Thank you for finding our text8 experiments clean and falsifiable. In the following, the numbers refer to the revised version.

Q1 and W1: We agree that the core contribution of this paper is that the ranking of schedules can be predicted before decoding from a kernel measured on the model. However, without these theoretical objects, the kernel would be a heuristic score that could only be checked by correlation. Proposition 1 and Lemma 2 define the estimate as a lower bound on the divergence of the path, so it can be compared with the measured excess in the same units and must stay below it (Table 5). The properties that the reviewer appreciates in the text8 programme, that it is clean and falsifiable, come from this. On the novelty of the theory itself, first, our statements are not the same as those in the literature. [1], [2] and [3] state the quantity on particular paths, but our Proposition 1 states it on every monotone path (we now cite all three in Section 3). The extension has a short proof, but it is what allows the same estimate to be used on MAR's continuous tokens and at interior levels. Second, we think the novelty should be judged on how we use the quantity, since stating the quantity, or using it for another purpose, is different from having a framework that uses it to rank schedules. [1] uses the quantity to motivate a copula model; [2] bounds it by marginal entropies to choose the width of a step; and [3] bounds it by spacing under a fast-mixing assumption, while we estimate it from a kernel and predict the ranking with it.

Theorem 1 has a different role. It uses treedepth as a tool, but its statement concerns decoding: the cost cannot be zero in fewer steps than the treedepth. It defines a boundary: below it every schedule pays and a ranking is needed. On an n×n grid the treedepth is at least n+1, so no schedule of logarithmic length has zero cost on images, which neither Halton nor DUS states. It also leads to the design of the separator rule, the best rule on text8 from 8 to 32 steps (Table 3). The cases that the reviewer lists (Appendix C.2, the nested rule and Section 6.4) are all cases where the cost is positive. There, Theorem 1 makes no claim about the ranking, and the kernel ranks the schedules (Section 5).

Q2: Yes, on text8. The separator rule keeps spread's spacing and takes at most one token per masked run. We compare them in Table 5. At 8 steps the estimate ranks it below spread (0.01 against 0.06 bits), and the measured excess agrees (0.06 against 0.09). We also test this in Table 17: with the kernel measured after a reveal, we predicted before decoding that a third rule (midpoint, ties spread) would have a lower excess than midpoint, and it does.

For the rest of the reply please see the other comment.

W2: In Section 6.3 we state that conditional errors determine the ranking from 32 to 64 steps. At 16 and 32 steps the total bpc (Table 3) still ranks the rules of Table 5 as the estimate predicts; Table 29 lists the rank correlations on text8, MAR-B and LLaDA. The predicted best rule is also close to the reference quality:

predicted bestrandomreference
text8, 32 steps (bpc)1.381.621.32 (exact chain)
MAR-B, 16 steps (FID)3.274.102.33 (256 steps)

Q3: We now print absolute strict accuracies in Table 4 (in blue), and Table 30 adds DUS and EB-sampler under the same protocol.

GSM8K accuracy (%)8 steps16 steps32 steps
confidence0.002.1221.08
min-distance9.709.7026.38
DUS's order, uniform widths4.097.7311.07

With DUS's own blocks, widths and passes and only the positions changed, min-distance obtains 23.88 to 51.02 against 12.28 to 45.26 for DUS, and is above the numbers that DUS v5 reports:

B = 64B = 32
min-distance37.3851.02
DUS v5 (reported)35.1849.36

EB-sampler and min-distance make different choices: EB-sampler sets how many tokens a step commits, and min-distance which ones. Comparing min-distance at fixed widths with EB-sampler at its adaptive widths changes both at once (26.38 against 40.56 near 32 passes), so we keep EB-sampler's widths and change only the positions:

24 passesnear 32 passes
EB-sampler27.7240.56
EB-sampler + min-distance30.4440.35

DUS (Section 4.4) adds a distance filter to EB-sampler and sweeps its gap over 4, 8 and 16; we set ours at 6 from the kernel before any decode. Fast-dLLM's confidence threshold also sets the width of a step, so we use EB-sampler to represent this class.

Q4: We now give the kernel at three mask rates and the estimates behind Table 25 in Table 26. At rate 0.5 the kernel falls below a tenth of its first value at distance 6, which is why we use min-distance 6. At 64 steps the estimates of random and spread differ by 0.02 bits.

Q5: We make this test as a ranking in Table 2: the floors of 7 orders against their FID (Spearman 0.86 for the information floor). A DDPM step samples a product of Gaussians. For any product law, KL(p ‖ ∏ q_i) = TC(p) + Σ_i KL(p_i ‖ q_i). This is the decomposition of [2] (eq. 7) for masked models; we now state it in Section 3 for every path and channel, so a factorised decode departs from the exact path by the cost of Proposition 1 plus each coordinate's model error.

If these address your concerns, we would be grateful if you could raise your score.

Thanks for the detailed response and the new experiments. They mostly confirm what I wrote, the gains appear only far from usable accuracy, so I keep my score.

Thank you for the reply. Our earlier experiments used few-step budgets because this is where the cost predicts the largest differences between rules. To test your point, we ran the comparison at DUS's two smaller blocks, where the accuracy is higher. The blocks, widths and passes are the same as in DUS, and we only change the positions:

passesconfidenceDUSmin-distanceseparator
40 (B = 32)25.9345.2651.0251.33
64 (B = 16)44.8156.7959.2958.38
96 (B = 8)58.9161.9462.0262.85

The reference with 256 passes obtains 71.42.

At 64 passes, we can see that min-distance gains 14.48 points over confidence (exact McNemar p = 3e-20), at an accuracy that is 83% of the reference with a quarter of its passes. So the gains do not appear only far from usable accuracy. The gain over confidence then becomes smaller as the passes increase, which is the trend that our cost predicts: the fewer the steps, the larger the gain (Section 6.2). At the two smaller blocks, the three rules that keep their tokens apart obtain similar accuracy.

We hope this addresses your remaining concern.

Comments on the paper

1 comment

We thank all reviewers for their careful reading. We have uploaded a revised version, with changes marked in blue. The main changes are:

  • Section 3: we cite Liu et al. (2025), Ben-Hamu et al. (2025) and Luxembourg et al. (2026) where Proposition 1 is stated, and add the decomposition of a factorised decode into the dependence cost and the model's conditional error (dMBi, T6G7).
  • Section 5: we state that the pairwise estimate is a lower bound on the cost and a heuristic for ranking beyond a first-order Markov reference (YguA, T6G7).
  • Table 4: absolute GSM8K accuracies (dMBi).
  • Table 26: the LLaDA kernel and the pairwise estimates behind Table 25 (dMBi).
  • Table 29 (Appendix C.12): predicted against measured rankings for every rule and budget, with rank correlations and the regret of the predicted best rule (YguA, T6G7).
  • Table 30: comparison with DUS and EB-sampler on LLaDA under the same protocol (dMBi).

We reply to each reviewer below.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.