arXiv Computation and Language

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."

arXiv Machine Learning
Jun 24

ParallelBench: Understanding the Trade-offs of Parallel Decoding in Diffusion LLMs

arXiv:2510. 04767v2 Announce Type: replace Abstract: While most autoregressive LLMs are constrained to one-by-one decoding, diffusion LLMs (dLLMs) have attracted growing interest for their potential to dramatically accelerate inference through parallel decoding.

By Wonjun Kang, Kevin Galim, Seunghyuk Oh, Minjae Lee, Yuchen Zeng, Shuibai Zhang, Coleman Hooper, Yuezhou Hu, Hyung Il Koo, Nam Ik Cho, Kangwook Lee
arXiv Machine Learning
Oct 16

Query-Efficient Rejection Sampling for Parallel Masked Diffusion

The paper introduces the Single-Increment Rejection Sampler (SIRS) to improve query efficiency in parallel masked diffusion models (MDMs). SIRS estimates the log acceptance probability using only one randomly sampled increment, then applies a Bernoulli factory to decide accept/reject outcomes. By Rao‑Blackwellizing each increment and bounding the KL‑divergence, SIRS reduces bias while maintaining parallel decoding performance.

By Shiyuan Zhang, Xuheng Li, Qiwei Di, Quanquan Gu
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
arXiv Machine Learning
Oct 8

Walk fast but be careful: Understanding Parallel Sampling in Masked Diffusion

The paper introduces random walks on graphs as a controllable sandbox for studying parallel sampling strategies in masked diffusion models (MDMs). It shows that common parallel unmasking methods, such as lowest‑entropy scoring, are not universally superior to random sampling and that performance depends on the graph’s conditional dependence structure. The authors also propose training‑free bisection samplers that are provably exact for random walks and demonstrate their effectiveness on both graph‑walk tasks and pretrained MDMs for language generation and reasoning benchmarks.

By Vansh Bansal, Cholyeon Cho, Syamantak Kumar, Sujay Sanghavi, Purnamrita Sarkar
arXiv AI
Nov 6

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

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.

By Adrian Baule