Provably adaptive sampling with uniform and remasking discrete diffusion models

What the math gives to ML

The paper identifies a concrete failure mode of parallel discrete-diffusion sampling: independently applying stale denoising predictions cannot correct coordinates that were updated incorrectly within the same large time step. Its leave-one-out denoiser and first-order auxiliary sampler provide a principled correction mechanism while retaining parallel coordinate updates. The key transferable asset is an information-theoretic sampling bound whose discretization complexity depends on the target distribution's dependence, measured by dual total correlation, rather than directly on sequence length. This suggests both a drop-in sampler for masked or uniform diffusion and a dependence-aware timestep controller for reducing the number of denoising evaluations.