Provably Adaptive Sampling with Uniform and Remasking Discrete Diffusion Models

Forum topic · 小凯 · 2026-08-26

Summary

This arXiv paper (2508.17627) by Daniil Dmitriev, Zhihan Huang, and Yuting Wei studies the sampling efficiency of discrete diffusion models, which enable parallel updates as an alternative to autoregressive generation. Existing lower bounds for the standard tau-leaping sampler under a uniform forward process scale linearly with the ambient dimension d. The authors show this dependence is not intrinsic: they propose a first-order sampler based on a leave-one-out denoiser for both uniform and remasking forward processes, with parallelizable coordinate updates. The sampler can correct denoising mistakes during sampling, which becomes necessary when many coordinates are updated simultaneously. Their main result establishes adaptive sampling guarantees: up to a logarithmic factor, N = O(DTC(X0) / epsilon) discretization steps suffice to achieve sampling error O(eps_score + epsilon), where eps_score is the score estimation error. Thus sampling complexity is governed by the intrinsic dependence structure of the target distribution, measured by its dual total correlation (DTC), rather than directly by the ambient dimension.

Paper Overview

Field: Machine Learning Authors: Daniil Dmitriev, Zhihan Huang, Yuting Wei Published: 2025-08-26 arXiv: 2508.17627

Abstract (Original)

Discrete diffusion models offer a promising alternative to autoregressive generation by enabling parallel updates, but their sampling efficiency can depend strongly on the choice of the forward process and the sampler. For the uniform forward process, existing lower bounds for the standard $\tau$ -leaping sampler scale linearly with the ambient dimension $$d$$ , raising the question of whether this dependence is intrinsic to the forward process. We answer this question in the negative. We consider a first-order sampler based on the leave-one-out denoiser for uniform and remasking processes whose coordinate updates can be performed in parallel. In both cases, the sampler can correct denoising mistakes during the sampling process, which becomes necessary when many coordinates are updated together.

Summary

Discrete diffusion models enable parallel updates, offering an alternative to autoregressive generation. However, sampling efficiency depends heavily on the forward process and sampler choice. For the uniform forward process, known lower bounds for the standard $\tau$ -leaping sampler scale linearly with ambient dimension $$d$$ , prompting the question of whether this dependence is intrinsic.

Key contributions

The paper shows this linear dependence on $$d$$ is not intrinsic to the uniform forward process.
It analyzes a first-order sampler based on the leave-one-out denoiser, applicable to both uniform and remasking processes, with coordinate updates that can be performed in parallel.
The sampler can correct denoising mistakes during sampling — a capability that becomes necessary when many coordinates are updated simultaneously.

Main result

An adaptive sampling guarantee: up to logarithmic factors,

N = O(\mathrm{DTC}(X_0) / \varepsilon)

discretization steps suffice to reach sampling error $O(\varepsilon_{\mathrm{score}} + \varepsilon)$ , where $\varepsilon_{\mathrm{score}}$ is the score estimation error.

Consequently, sampling complexity is governed by the target distribution's intrinsic dependence structure — measured by its dual total correlation $\mathrm{DTC}(X_0)$ — rather than directly by the ambient dimension $$d$$ .

--- *Auto-collected on 2026-08-26*

Provably Adaptive Sampling with Uniform and Remasking Discrete Diffusion Models

Summary

Paper Overview

Abstract (Original)

Summary

Key contributions

Main result

Tags