Masked Diffusion Parallel Decoding Mapped to Random Sequential Adsorption
Masked diffusion as random sequential adsorption: an exactly solvable model for parallel decoding
The physics framing turns schedule design for masked diffusion decoding into a geometry problem, giving practitioners a principled way to choose unmasking steps instead of heuristics. Builders working on parallel decoding, such as teams tuning LLaDA- or Mercury-style diffusion LMs, can use the closed-form metric to cut error at a fixed step budget. The finding that errors concentrate early for long-correlation text directly informs how to allocate compute across generation steps.
An arXiv paper (2611.07845v1) maps the error trade-off in masked diffusion text generation onto the statistical physics of driven many-particle systems. The authors show parallel-generation error equals the entropy production of the generation process relative to the reversed masking process. For Markov data, they reduce generation to a random sequential adsorption process with labelled gaps and solve it exactly for any number of steps. The unmasking schedule acts as a driving protocol, with the error given by a thermodynamic metric derived in closed form from token mutual information, and optimal schedules are geodesics of this metric. The solution shows small initial steps yield lower path error and perplexity with fewer steps needed to reach asymptotic behaviour.
Masked diffusion as random sequential adsorption: an exactly solvable model for parallel decoding
Masked diffusion models generate text by reversing a stochastic masking process. Unlike autoregressive LLMs, which generate text one token at a time, they can reveal many tokens in parallel, at the price of an error, since tokens revealed together are drawn independently. We show that this trade-off maps onto the statistical physics of driven many-particle systems. (i) For any data, the error of parallel generation is the entropy production of the generation process relative to the reversed masking process. (ii) For Markov data, generation is a random sequential adsorption process with labelled gaps, which we solve exactly for any number of steps. (iii) For many steps, the error becomes the dissipation of a slowly driven system: the unmasking schedule plays the role of the driving protocol, the number of steps that of its duration, and the error is set by a thermodynamic metric that we obtain in closed form from the mutual information between tokens. Optimal schedules are geodesics of this metric. The exact solution shows how correlations in the text shape both the error and the quality of the output. The longer the correlations, the more the error concentrates at the start of generation. Schedules that start with small steps then gain more, both in path error and in perplexity, and need fewer steps to reach their asymptotic behaviour.