The Lattice of Transition Laws

The Lattice of Transition Laws. By T. Y. Tsui and two others, from the University of Pennsylvania. Published on the eighth of October.

Diffusion and autoregression have long been treated as different kinds of generative model. Diffusion has specialised in continuous fields, and autoregression in discrete tokens. Recent work tries to combine the strengths of both, and each such hybrid fixes its decoding schedule by design. The question posed here is whether that choice can be informed in advance: whether the performance of a model's decoding schedules can be predicted before decoding, at a fixed number of steps.

To make the question precise, the paper places diffusion, autoregression and everything in between on a single object, a corruption lattice, where each model is a path. The cost of a schedule is then defined as the dependence that its parallel steps throw away. Decoding several things in one step means treating them as if they did not depend on each other, and whatever dependence actually existed between them is what the schedule pays.

The central result is that the fewest steps a zero-cost schedule can take are set by the geometry of the data, and in the same way for tokens as for continuous fields. For data that are Markov on a graph and dependent along its paths, that minimum equals the graph's treedepth. For a sequence, treedepth is logarithmic in the sequence's length. For a grid, it is linear in the grid's side length.

Below that threshold, with fewer steps than the treedepth, every schedule pays a positive cost. The paper predicts how those costs rank before any decoding happens, using a kernel of pairwise dependence estimated from pretrained weights.

The thread of the argument runs from one definition. Once cost is measured as discarded dependence, a schedule costs nothing only if no step ever decodes two dependent pieces together. How few steps that allows is a property of how the dependence is arranged, not of whether the data are words or pixels, which is why tokens and continuous fields fall under one account. When the dependence lives on a graph, the treedepth captures the minimum, and that is what separates a sequence, which needs only logarithmically many steps, from a grid, which needs linearly many in its side. Once a budget falls short of the treedepth, some dependence must be discarded, and the pairwise kernel is what estimates how much each schedule gives up, so the schedules can be ranked.

The treedepth result is stated for a particular class of data: Markov on a graph, and dependent along its paths. The ranking below the threshold rests on a kernel of pairwise dependence, estimated from pretrained weights rather than known exactly. Empirically, the predictions are checked across text, image and video generation, under different metrics and benchmarks, and most of them, not all, are verified.

The upshot is a design principle for decoding that does not care which family a model comes from. Autoregressive models, diffusion models and the hybrids between them become points on one lattice, and the number of steps a schedule needs is read off the structure of the data rather than fixed in advance by design.