The Lattice of Transition Laws

arXiv · T. Y. Tsui, Jiatao Gu, Lingjie Liu · 2026-10-11

This item is no longer on the current shelf. Its page remains available, and editorial corrections may be made. See what is featured now.

A lattice-based theory lets you predict the optimal decoding schedule for diffusion, autoregressive, and hybrid generators before you run a single step.

What it does

The paper formalizes diffusion, AR, and intermediate models as paths on a single corruption lattice and defines a schedule-cost that measures how much parallelism discards. It shows that the minimal-cost (zero-cost) schedule length is dictated by the data’s graph treedepth—logarithmic in sequence length and linear in grid side length. Using a kernel of pairwise dependence estimated from pretrained weights, the authors predict the relative cost of any schedule before decoding. Empirical tests on text, image, and video generation confirm the predicted rankings across several metrics.

Why it matters

Decoding speed is a bottleneck for production LLM and multimodal services. Knowing the theoretical lower bound on steps and being able to rank schedules ahead of time lets engineers allocate compute more efficiently without trial-and-error. The work also unifies diffusion and AR under a common framework, opening doors to hybrid designs that inherit the best of both worlds.

How it applies

When building an LLM or diffusion-based image generator, you can compute the treedepth of your token or pixel graph to set a realistic step budget. The kernel-based cost predictor can be plugged into existing pipelines to auto-select a schedule that balances quality and latency. This reduces the need for extensive hyper-parameter sweeps on decoding strategies.

The short version

What if you could read the optimal number of generation steps off a graph before you even start decoding?

My take

I see this as a practical cheat-sheet for anyone wrestling with the trade-off between speed and fidelity. If you can estimate treedepth from your token graph, you instantly know the best-case step count. The kernel predictor is lightweight enough to run as a pre-flight check, saving days of trial-and-error. It won’t replace fine-tuning, but it will make your decoding decisions data-driven from day one.

How it connects

• Aligns with the industry push toward "fast inference" for LLMs (e.g., speculative decoding, chunked diffusion).
• Provides a theoretical backbone for hybrid diffusion-AR models that are starting to appear in commercial products.
• Encourages a shift from heuristic schedule design to principled, graph-based budgeting.

Bottom line

Compute the treedepth of your data graph and let the lattice-cost predictor pick your decoding schedule—speed up inference without sacrificing quality.

Takeaways

• Zero-cost schedules are bounded by the data’s treedepth, not by model architecture.
• Treedepth grows logarithmically with sequence length, so long texts can still be generated in few parallel steps.
• A simple kernel estimated from pretrained weights can rank arbitrary schedules before any decoding occurs.
• Empirical validation spans three modalities (text, image, video), suggesting broad applicability.
• The lattice view provides a unified design principle for future hybrid generative models.

Topics: generative-models, diffusion, autoregressive, decoding-schedules, theory