Provably adaptive sampling with uniform and remasking discrete diffusion models
The paper argues that sampling cost can track a distribution’s dependence structure, not its raw dimension.
Dmitriev, Huang, and Wei study first-order samplers for uniform and remasking discrete diffusion models, using leave-one-out denoisers with parallel coordinate updates. Their guarantee says roughly `O(DTC(X0) / ε)` discretization steps are enough, up to logs, with final error tied to score-estimation error plus `ε`. The analysis separates discretization and score errors through a Bayes-optimal auxiliary sampler, then represents discretization error via mutual information across coordinates and times. Synthetic experiments are reported as matching the predicted dimension-adaptive behavior. ArXiv · AI/CL/LG's note
Dmitriev, Huang, and Wei study first-order samplers for uniform and remasking discrete diffusion models, using leave-one-out denoisers with parallel coordinate updates. Their guarantee says roughly `O(DTC(X0) / ε)` discretization steps are enough, up to logs, with final error tied to score-estimation error plus `ε`. The analysis separates discretization and score errors through a Bayes-optimal auxiliary sampler, then represents discretization error via mutual information across coordinates and times. Synthetic experiments are reported as matching the predicted dimension-adaptive behavior. ArXiv · AI/CL/LG's note
score 5