PaperlayerView exact revision on arXiv

Source-linked AI summary

The Lattice of Transition Laws

T. Y. Tsui, Jiatao Gu, Lingjie Liu

arXiv:2610.11216v1cs.LGcs.CL

TL;DR

The paper asks whether a model’s decoding schedules can be ranked before decoding, and describes diffusion, autoregression, and intermediate schedules as paths on a corruption lattice. It defines a dependence cost for those paths; for graph-Markov data, the minimum zero-cost decoding steps equal graph treedepth, while the conclusion notes limits from errors in trained conditionals and the pairwise bound.

  • Problem

    Existing hybrid models fix their decoding schedule, and schedule quality can vary substantially, leaving a need to choose schedules before decoding.

    Source: §1 · p. 1

  • Method

    The paper represents schedules as paths on a corruption lattice and measures their cost by the dependence discarded in parallel steps.

    Source: §1 · p. 2, §2.1 · p. 3

  • Results

    For graph-Markov data dependent along unresolved paths, the fewest zero-cost steps equal graph treedepth; on MAR, spread order lowers FID by more than 25% from the model’s random order at 8 steps.

    Source: §4 · p. 4, §6.2 · p. 7

  • Takeaways & Limitations

    The lattice and dependence cost provide a quantified design principle for choosing future diffusion, autoregressive, and intermediate decoders.

    Source: §1 · p. 2, §7 · p. 9

    Errors in trained conditionals lie outside the cost and can affect schedule rankings, while the pairwise bound is tight only on a first-order Markov reference.

    Source: §7 · p. 9

Abstract

from arXiv · show

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. Our code is available at https://github.com/TSUITUENYUE/The-Lattice-of-Transition-Laws.

1 INTRODUCTION

The paper asks whether a model’s decoding schedules can be ranked before decoding, then places diffusion, autoregression, and intermediate schedules on one corruption lattice. It defines a dependence cost and relates zero-cost decoding depth to data geometry.

1 INTRODUCTION

  • Existing hybrid models fix their schedule by design, leaving no principle for choosing a schedule before decoding.With the same weights and few-step budget, MAR image quality varies by an order of magnitude across reveal orders.Source: §1 · p. 1
  • Below treedepth, every schedule pays positive cost; a pretrained-weight kernel of pairwise dependence predicts how schedules rank before decoding.The prediction uses how dependence decreases with distance to compare schedules at a fixed step budget.Source: §1 · p. 2
  • The corruption lattice represents diffusion, autoregression, and intermediate schedules as paths through one family of transition laws.Each coordinate has its own corruption level, and a schedule chooses which coordinates to update and by how much at each step.Source: §1 · pp. 1–2
  • A schedule’s dependence cost is the dependence discarded by its parallel steps, and for graph-Markov data the fewest zero-cost steps equal the graph’s treedepth.The result applies to both discrete tokens and continuous values.Source: §1 · p. 2

2 DECODING SCHEDULES ON THE CORRUPTION LATTICE

The paper represents decoders as transition-law paths through a coordinatewise corruption lattice. It shows that one model trained across the lattice can decode both diffusion and autoregressive corners, as well as schedules between them.

2 DECODING SCHEDULES ON THE CORRUPTION LATTICE

  • A continuous diffusion transition uses a conditional mean and either fresh noise or carried-forward noise to move between adjacent noise levels.The transition levels have ratio r = a_{k+1}/a_k.Source: §2 · p. 2

2.1 ONE LEVEL PER COORDINATE

  • The corruption lattice assigns each coordinate a corruption level, and a schedule is a monotone path from fully corrupted to clean.A step advances a subset of coordinates; other coordinates retain their values.Source: §2.1 · p. 3
  • Every monotone path composes transition laws whose marginal on clean coordinates is the data distribution; paths differ in which transition laws they evaluate.Autoregression is the sequential corner and diffusion the synchronized corner.Source: §2.1 · p. 3

2.2 ONE MODEL FOR EVERY SCHEDULE

  • One model trained on a distribution over the lattice decodes both corners and intermediate schedules with the same weights.At the sequential token corner, its bpc is 0.06 below a dedicated masked model trained on random subsets; pixel schedules span an order of magnitude in step count.Source: §2.2 · p. 3, Figure 2 · p. 3
  • A model trained on one family of paths collapses when used to decode other families.Following a path requires both an architecture that expresses its conditionals and training that covers it.Source: §2.2 · p. 3

3 THE DEPENDENCE COST OF A SCHEDULE

The dependence cost measures what parallel steps discard when they replace a joint transition with independent coordinate draws. The paper relates this cost to path divergence and explains how step composition and coordinate choice affect it.

3 THE DEPENDENCE COST OF A SCHEDULE

  • The dependence discarded by parallel updates is the total correlation of the coordinates advanced together, accumulated across the schedule.The path’s exact joint transition is compared with the product of coordinate conditionals; the divergence between finished-sample laws is bounded by the same sum.Source: §3 · p. 4
  • At an interior level, the step cost is the total correlation of the values reached, and an intermediate advance can reduce cost by retaining information from other coordinates.Two advances per coordinate double the step width at a fixed step budget.Source: §3 · p. 4
  • Sequential decoding has zero dependence cost, and continuous synchronized decoding also approaches zero cost as level increments tend to zero.On the two-level token channel, a synchronized one-step reveal pays the full total correlation.Source: §3 · p. 4
  • When dependence decreases with distance, advancing adjacent coordinates incurs the largest cost at a given width.The contiguous rule selects adjacent coordinates at every step.Source: §3 · p. 4
  • A continuous decoder’s measured error includes dependence cost, errors in trained conditionals, and one-step error from the continuous channel.Each step applies the conditional mean through one of the specified transition equations.Source: §3 · p. 4

4 SCHEDULES WITH ZERO DEPENDENCE COST

For data that are Markov on a graph and dependent along unresolved paths, the fewest zero-cost steps equal the graph’s treedepth. The separator interpretation yields logarithmic depth for a chain and linear scaling with grid side length.

4 SCHEDULES WITH ZERO DEPENDENCE COST

  • Under the theorem’s graph-Markov and path-dependence conditions, the minimum number of zero-cost steps is the graph’s treedepth.The condition applies at the current and every later state to unresolved coordinates given revealed ones.Source: §4 · p. 4
  • A zero-cost schedule resolves at most one coordinate per connected component per step, tracing an elimination tree one depth at a time.Resolving a coordinate removes it from the graph and may split its component.Source: §4 · p. 5
  • On a chain of d coordinates, the midpoint rule finishes in ⌈log2(d + 1)⌉ steps; on an n × n grid, treedepth is between n + 1 and a constant multiple of n.The midpoint rule halves each masked run, while splitting a grid takes a whole row or column.Source: §4 · p. 5

5 RANKING SCHEDULES BELOW THE TREEDEPTH

Below the treedepth, every schedule has positive cost when coordinates are dependent along graph paths. A pairwise kernel lower bound estimates schedule cost before decoding and characterizes a first-order Markov reference case.

5 RANKING SCHEDULES BELOW THE TREEDEPTH

  • When coordinates are dependent along graph paths, every schedule using fewer steps than the treedepth pays positive cost.Source: §5 · p. 5
  • For an advanced coordinate set, the pairwise lower bound sums the kernel over consecutive selected coordinates.Source: §5 · p. 5
  • The schedule estimate sums the pairwise bound over steps and can be computed before decoding; midpoint updates on masked runs give a schedule whose first-step cost is the sum of consecutive-pair kernels.On the reference model, a step of k coordinates with gaps at least s costs at most (k −1) ε when κ ≤ ε at distances ≥s.Source: §5 · p. 5

6 EXPERIMENTS

Across text, image, and video experiments, measured schedule rankings mostly followed the pairwise-dependence estimates, with larger gains over released rules at smaller step budgets. The experiments also test how kernels, graph separation, and interior corruption levels relate to measured quality.

6 EXPERIMENTS

  • The study compares matched-step selection-rule rankings on text8, MAR-B, LLaDA-8B, and a pretrained Diffusion Forcing video model.For released models, the experiments change only the decoding schedule; the models’ outputs remain as released.Source: §6 · p. 5

6.1 THE KERNEL

  • The measured kernels decay with distance: text8 within-word dependence is 2–4 times across-boundary dependence through distance 4, while MAR prediction displacement falls below 5% by grid distance 8.MAR’s information kernel decays faster than its displacement kernel, but floors built from both kernels order the rules alike apart from nearly tied rules.Source: §6.1 · pp. 6–7, Figure 4 · p. 6

6.2 THE RANKING OF SCHEDULES

  • On MAR, FID followed predicted raster, random, midpoint, and spread ordering at 8 and 16 steps; spread lowered FID by more than 25% versus random at 8 steps.At 64 steps, all orders except raster were within 0.1 FID of one another.Source: §6.2 · p. 7, Figure 5 · p. 7, Table 3 · p. 7
  • Across text8, MAR, LLaDA, and video, schedule rankings mostly followed pairwise-cost predictions, and gains over released rules grew as step budgets decreased.Video subject consistency tracked the predicted cost of memory depth; on LLaDA, constrained confidence selection improved GSM8K accuracy from 8 to 32 steps.Source: §6.2 · pp. 7–8

6.3 THE MAGNITUDE OF THE COST

  • The pairwise estimate never exceeded text8 excess bpc, matched the rules’ ranking, and accounted for about 30%–50% of the excess at 2 steps.The absolute gap narrowed as the number of steps increased.Source: §6.3 · p. 8, Table 5 · p. 8

6.4 SEPARATION

  • On MAR, midpoint selection lowered FID versus random by about 20% at 8 steps and 10% at 16, while spread and low-discrepancy selection lowered it further.The nested rule followed grid separators and had lower 8-step floors than random, yet its measured FID was higher at both 8 and 16 steps.Source: §6.4 · p. 9

6.5 INTERIOR LEVELS

  • The absorbing model had lower bpc than the graded model at every budget; the graded model’s two-stage pairwise estimates were twice the absorbing estimate at 8 steps and nearly equal from 16.At 8 steps, wider steps outweighed the graded model’s lower dependence cost; from 16 steps, the models’ costs roughly cancelled, and the graded model’s sequential chain accounted for most of the bpc gap.Source: §6.5 · p. 9, Table 6 · p. 9

7 CONCLUSION

The paper frames diffusion, autoregression, and intermediate schedules as paths on a corruption lattice, then uses discarded dependence to rank schedules before decoding. For graph-Markov data, zero-cost step counts equal treedepth, and most measured rankings follow the predictions across modalities and benchmarks.

7 CONCLUSION

  • For data Markov on a graph and dependent along its paths, the fewest zero-cost steps equal graph treedepth: logarithmic in sequence length and linear in grid side length.This result applies to tokens and continuous values alike.Source: §7 · p. 9
  • Where schedules differ in dependence cost, most measured rankings follow the predictions across modalities and benchmarks.The framework can miss rankings when trained-conditional errors matter, especially when costs are close; the pairwise bound is tight only on a first-order Markov reference.Source: §7 · p. 9
  • With fewer steps than treedepth, a pretrained-weight pairwise-dependence kernel predicts schedule rankings before decoding.The paper presents the lattice and cost as a quantified design principle for future diffusion, autoregressive, and intermediate decoders.Source: §7 · p. 9

ETHICS STATEMENT

The study uses public datasets and released model weights, and trains additional models on text8, CIFAR-10, and ImageNet-256.

ETHICS STATEMENT

  • The study uses public datasets and released model weights, and trains its own models on text8, CIFAR-10, and ImageNet-256.For released models, only the decoding procedure changes; their generation capabilities remain as released.Source: ETHICS STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

The paper describes code and scripts for training, kernel estimation, and decoding, with a script for each measurement table or figure.

REPRODUCIBILITY STATEMENT

  • Supplementary code trains models, estimates kernels, and decodes under every schedule; a numbered script writes the data for each measurement table or figure.The paper also states that released-model evaluations use the released weights.Source: REPRODUCIBILITY STATEMENT · p. 10

AI USE STATEMENT

The section connects hybrid schedules and dependence-cost analyses to a shared lattice, then shows that one model can traverse its paths. It illustrates how schedules differ in intermediate states and reports corner-quality gaps across text and image models.

A.1 HYBRIDS OF AUTOREGRESSION AND DIFFUSION

  • The section places token hyperschedules and video corruption patterns on lattice paths, where dependence cost enables schedule comparison before decoding.The video examples include independent corruption levels and rolling, diagonal, and streaming schedules.Source: §A.1 · p. 12

A.2 THE DEPENDENCE COST OF A DECODING STEP

  • Prior analyses average over random positions or use other selection mechanisms; the lattice analysis retains positions and levels, with graph separation defining zero-cost update sets.For graph-Markov data, the fewest such steps are treedepth; the section also contrasts these sets with two-colour parallel Gibbs updates.Source: §A.2 · pp. 12–13

B THE LATTICE AND ITS CORNERS

  • Every monotone lattice path composes transition laws from one family into a law whose clean-coordinate marginal is the data distribution.A model that realizes the family realizes every path; observed corner gaps instead reflect capacity or optimization, training allocation, or architectural supervision limits.Source: B THE LATTICE AND ITS CORNERS · pp. 13–14

B.1 THE INTERIOR STATES

  • The five CIFAR-10 schedules produce visibly different intermediate states: synchronised denoising keeps one level, while sloped and sequential paths create spatially uneven progress.Spread order denoises separated patches first, leaving noisy regions between them.Source: §B.1 · p. 14

B.2 THE CORNER QUALITY GAPS

  • At the synchronised CIFAR-10 corner, the dedicated model’s FID is about 2 points lower, while the lattice model assigns that corner 25% of its training distribution.Table 7 reports CIFAR-10 FID over 50K samples and includes the two lattice training distributions and single-schedule controls.Source: §B.2 · p. 15, Table 7 · p. 15
  • On text8, the two-stream model’s sequential-corner bpc is 0.03 bits above the dedicated causal model’s, and the lattice model’s masked-bound gap is 0.13 bits.These gaps depend on which conditionals a backbone supervises in one forward pass.Source: §B.2 · p. 15
  • At CIFAR-10 slope 16, spread order beats raster order in FID after the model continues to 120K steps on fresh data, despite the cost favouring spread at both tested slopes.At slope 4, replacing raster with spread lowers FID; at slope 16 it raises FID before the doubled training budget.Source: §B.2 · p. 15, Table 7 · p. 15
  • On ImageNet-256, the lattice model’s synchronised-corner FID is within 4 of the dedicated model’s, but its sequential-corner FID is more than twice its synchronised value.The sequential-only and synchronised-only schedules differ in training distribution; Table 8 reports FID-50K against the ADM reference.Source: §B.2 · p. 15, Table 8 · p. 15

B.3 LATTICE POINTS AN ARCHITECTURE CAN SUPERVISE

The section compares how architectures supervise lattice transitions and develops a dependence cost for parallel schedules. It relates zero-cost decoding depth to graph treedepth and tests whether pairwise kernels can predict schedule rankings before decoding.

B.3 LATTICE POINTS AN ARCHITECTURE CAN SUPERVISE

  • Two-stream attention supervises every conditional along a sampled path in one pass, while identity order recovers autoregression exactly.The comparison evaluates width-1 advances, where the architectures’ expressed laws coincide.Source: §B.3 · p. 16, Table 9 · p. 16
  • 0.06 bits lower bpc at the sequential corner is achieved by the lattice model than by dedicated masked models; causal and two-stream backbones lower bpc by about 0.1 bits more.The two-stream masked ELBO is 0.2 bits above the lattice model’s; dense supervision improves the sequential corner but not the masked-diffusion bound.Source: §B.3 · p. 16

C THE SCHEDULE ON THE LATTICE

  • A schedule’s path cost equals the divergence between exact joint-step sampling and sampling from the same coordinate conditionals independently, and bounds the divergence of finished samples.The identity applies to both channels and all advanced-coordinate levels.Source: C THE SCHEDULE ON THE LATTICE · pp. 16–17
  • The pairwise kernel lower-bounds a step’s total correlation, with equality when selected coordinates satisfy the stated first-order Markov condition.The lower bound sums conditional mutual information over consecutive selected coordinates.Source: C THE SCHEDULE ON THE LATTICE · p. 17
  • With graph-Markov unresolved coordinates that remain dependent along unresolved paths, the fewest zero-cost steps equal the graph’s treedepth.On a path of d coordinates, midpoint resolution takes ⌈log2(d + 1)⌉ steps; for an n × n grid, the described schedule uses 46 steps at n = 16 and about 3n generally.Source: C THE SCHEDULE ON THE LATTICE · p. 17

C.1 THE TEXT8 KERNEL AND THE PAIRWISE ESTIMATES

  • A 26M text8 model’s kernel predicts the 85M model’s schedule ranking at every budget, while spread has lower total correlation than random at every width.The spread-rule difference is an order of magnitude at width 8 and a factor of 3 to 5 at width 32.Source: §C.1 · p. 18, Table 11 · p. 18, Table 13 · p. 19

C.2 SEPARATION ON TEXT

The experiments test whether dependence estimates distinguish schedules across text, image, and token-generation settings. Separation, width, and confidence constraints produce different measured outcomes, with rankings generally—but not uniformly—matching kernel predictions.

C.2 SEPARATION ON TEXT

  • 4× or more: from 8 steps onward, midpoint’s measured excess bpc is at least four times separator’s, while one revealed character leaves over 50% of within-word dependence.The state-aware kernel estimate captures most of midpoint’s excess and stays within 0.01 bits of separator’s measured excess.Source: §C.2 · p. 20, Table 17 · p. 20

C.3 TEXT8 DECODING FROM 2 TO 64 STEPS

  • From 16 steps onward, spread and dilated orders diverge in bpc: dilated stays within 0.01 bits of its 64-step chain, while spread has lower bpc.On MAR-B, kernel floors mostly order schedules alike, but both misrank nested versus random and low-discrepancy; minimum-distance confidence also has spread-like estimates but random-like bpc.Source: §C.3 · p. 21, §C.4 · p. 21, §C.5 · p. 21

C.6 WIDTH PROFILES

  • Geometric width profiles reach bpc up to 0.2 bits higher at 16 steps, while the uniform profile has the lowest bpc under spread.The widest geometric step advances 33% of the sequence and includes dependence beyond pairs.Source: §C.6 · pp. 21–22, Table 20 · p. 22

C.7 THE GRADED CHANNEL

  • From 32 steps, absorbing and graded models’ excess bpc values are within 0.01 bits, and the graded model’s higher bpc comes from its sequential chain.For both models, excess bpc exceeds the corresponding pairwise estimate at every budget.Source: §C.7 · p. 22, Table 21 · p. 23

C.8 FREE GENERATION ON TEXT8

  • In free text generation, clustered-coordinate rules have the largest unigram divergence, while word-aware spread scores above spread at every budget.At the sequential limit, contiguous order gives the lowest scorer loss.Source: §C.8 · p. 23, Table 23 · p. 23

C.9 GENERATIVE PERPLEXITY ON THE RELEASED LANGUAGE MODEL

  • At 8 and 16 steps, confidence has higher generative perplexity than random, and minimum-distance confidence lowers perplexity versus plain confidence with intervals excluding zero.The minimum-distance reduction persists after controlling for unigram entropy and repeated 4-token sequences, and among less repetitive samples.Source: §C.9 · pp. 23–24, Table 25 · p. 24, Table 24 · p. 24

C.10 THE COST OF SELECTING

  • Less than 1%: every selection rule’s measured time is below 1% of a forward pass; minimum-distance selection is below 0.75% on the released model and 0.5% on text8.On HumanEval, both constrained rules outperform plain confidence significantly from 8 to 64 steps, but all three tie at 128 steps.Source: §C.10 · p. 24, §C.11 · pp. 24–25, Table 26 · p. 25

D THE FRAME AXIS ON RELEASED VIDEO WEIGHTS

The video experiments use frame-level dependence estimates to compare memory-depth schedules on released weights. Greater memory depth is predicted to require more steps without improving quality, and most tested settings score near the shipped setting across the reported VBench dimensions.

D THE FRAME AXIS ON RELEASED VIDEO WEIGHTS

Loading 2610.11216v1…