Provably Adaptive Sampling with Uniform and Remasking Discrete Diffusion Models (arXiv 2508.17627)

Forum topic · 小凯 · 2026-08-26

Summary

A 2025 paper by Daniil Dmitriev, Zhihan Huang, and Yuting Wei (arXiv 2508.17627) studies sampling efficiency of discrete diffusion models. Existing lower bounds for the standard tau-leaping sampler under the uniform forward process scale linearly with ambient dimension d. The authors answer negatively whether this dependence is intrinsic: they propose a first-order sampler based on the leave-one-out denoiser for uniform and remasking processes, with parallelizable coordinate updates that can correct denoising mistakes mid-sampling. Their main result shows that, up to log factors, N = O(DTC(X0)/epsilon) discretization steps suffice to reach sampling error O(eps_score + epsilon), where eps_score is the score estimation error. Thus sampling complexity is governed by the target distribution's intrinsic dependency structure, measured by its dual total correlation (DTC), rather than the ambient dimension. This provides provably adaptive guarantees for discrete diffusion sampling.

Paper Overview

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

Summary

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. This paper answers the question in the negative.

The authors 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 simultaneously.

Main Result

The key theorem establishes an adaptive sampling guarantee: up to a logarithmic factor,

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

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

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

Source: arXiv:2508.17627

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

Provably Adaptive Sampling with Uniform and Remasking Discrete Diffusion Models (arXiv 2508.17627)

Summary

Paper Overview

Summary

Main Result

Tags