arXiv AI By Adrian Baule

Masked diffusion as random sequential adsorption: an exactly solvable model for parallel decoding

Read the original on arXiv AI →

Masked diffusion models generate text by reversing a stochastic masking process, allowing many tokens to be revealed in parallel at the cost of errors due to independent token draws. The paper maps this trade‑off onto driven many‑particle systems, showing that for Markov data the process is a solvable random sequential adsorption model and that the error equals entropy production relative to the reversed masking. For many steps, the error corresponds to dissipation in a slowly driven system, with optimal schedules being geodesics of a thermodynamic metric derived from token mutual information, revealing how text correlations influence error concentration and output quality.

Machine-generated by The Flow from the publisher's headline and feed description — not written or checked by a human. The full article lives at arXiv AI.

arXiv Machine Learning
Oct 9

The Lattice of Transition Laws

The paper introduces a framework that unifies diffusion and autoregressive (AR) generative models as paths on a corruption lattice, defining a cost for decoding schedules based on discarded parallel steps. It shows that the minimal number of steps for a zero‑cost schedule is determined by the data’s geometry—specifically, the graph’s treedepth for Markov data—providing a theoretical limit for both token and continuous field models. By estimating pairwise dependencies from pretrained weights, the authors predict the ranking of decoding schedules before execution, and validate these predictions across text, image, and video generation tasks.

By T. Y. Tsui, Jiatao Gu, Lingjie Liu
arXiv Machine Learning
Sep 18

Parallelism, critical windows, and separations among diffusion language models

The paper compares the parallelism capabilities of three diffusion large language model paradigms—masked, uniform, and Gaussian diffusion. It proves that uniform and Gaussian diffusion can sample with a number of forward passes scaling with the dual total correlation of the distribution, potentially much less than the context length, whereas masked diffusion may require more passes. The study establishes a provable separation in parallelism, showing that masked diffusion’s critical windows are asymptotically narrower than those of the other two approaches.

By Sitan Chen, Liye Wang
Hugging Face Trending Papers
Oct 8

The Lattice of Transition Laws

The paper investigates how to predict the performance of decoding schedules for generative models that blend diffusion and autoregressive (AR) approaches. By modeling diffusion, AR, and hybrid models as paths on a corruption lattice, the authors define a schedule cost based on discarded parallel steps and show that the minimal zero‑cost schedule is determined by the data’s geometry, such as the treedepth of a Markov graph. They further demonstrate that schedules with fewer steps than the treedepth incur a positive cost, which can be ranked in advance using a kernel derived from pretrained weights, and validate these predictions across text, image, and video generation tasks.

arXiv Computation and Language
Aug 27

Conditional Total Correlation and the Serial Depth of Adaptive Parallel Sampling

The paper introduces a new framework for adaptive parallel sampling of discrete vectors, where a deterministic policy reveals coordinates round‑by‑round based on previously observed values and samples the remaining coordinates from their exact conditional marginals. The authors prove an exact identity linking the forward Kullback‑Leibler divergence of any policy to the expected conditional total correlation accumulated during the sampling process, establishing conditional total correlation as the precise information cost of within‑round parallelism. Using this identity, they derive zero‑error schedules for finite‑order Markov chains, characterize the serial depth of Bernoulli walks, and demonstrate separations between different reveal orders, permutation strategies, and string structures, thereby revealing how conditional dependence governs parallelizability. whyItMatters":"The results provide a principled, information‑theoretic measure of parallel sampling efficiency that can guide the design of decoding rules for masked diffusion models and other generative systems."

By Chuling Wen, Weijie Liang, Jian Lu