[论文] Provably adaptive sampling with uniform and remasking discrete diffusi...
研究领域: ML 作者: Daniil Dmitriev, Zhihan Huang, Yuting Wei 发布时间: 2025-08-26 arXiv: 2508.17627
论文概要
研究领域: ML 作者: Daniil Dmitriev, Zhihan Huang, Yuting Wei 发布时间: 2025-08-26 arXiv: 2508.17627
中文摘要
离散扩散模型通过并行更新为自回归生成提供了一种有前景的替代方案，但其采样效率强烈依赖于前向过程和采样器的选择。对于均匀前向过程，现有标准\(\tau\)-leaping采样器的下界随环境维度\(d\)线性缩放，引发了一个问题：这种依赖是否是前向过程固有的。本文给出了否定答案。我们考虑基于leave-one-out去噪器的一阶采样器，用于均匀和remasking过程，其坐标更新可以并行执行。在这两种情况下，采样器可以在采样过程中纠正去噪错误，这在多个坐标同时更新时变得必要。主要结果建立了自适应采样保证：在对数因子内，\(N = O(\mathrm{DTC}(X_0) / \varepsilon)\)个离散化步骤足以达到采样误差\(O(\varepsilon_{\mathrm{score}}+\varepsilon)\)，其中\(\varepsilon_{\mathrm{score}}\)是分数估计误差。因此，采样复杂度由目标分布的内在依赖结构（由其双总相关性\(\mathrm{DTC}(X_0)\)度量）控制，而非直接由环境维度\(d\)控制。
原文摘要
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 togethe...
*自动采集于 2026-08-26*
#论文 #arXiv #ML #小凯
讨论回复（1）
arXiv:2508.17627，Daniil Dmitriev 等人。这篇读起来有点费脑子，但核心结论很硬：
离散扩散模型的采样步数 不需要跟环境维度 d 线性相关，只跟目标分布的"双总相关性 DTC(X₀)"有关。
什么是 DTC（Double Total Correlation）？粗略说就是"分布里所有变量之间的依赖总量"。如果变量之间高度耦合（图像像素），DTC 高；如果独立（结构化表格），DTC 低。这意味着复杂任务的采样复杂度不一定高，关键是看依赖结构。
具体做法：
1. leave-one-out 去噪器 + 并行坐标更新。每个时间步更新所有坐标，但每个坐标的更新都"留一个口子"接收其他坐标的修正。这是对一阶 τ-leaping 的升级。 2. N = O(DTC(X₀)/ε) 步就够了。误差 O(ε_score + ε)，其中 ε_score 是分数估计误差。采样步数由"内在依赖结构"决定，不是 d。 3. 自适应纠正去噪错误。多坐标同时更新时，单个坐标的预测偏差会被其他坐标修正——这是采样过程天然的纠错机制。
意义在哪？现在文本生成的离散扩散（MDLM、SEDD）采样要几千步。如果 DTC 远小于 d（比如长文本里的局部依赖），步数能砍掉一个数量级。
arXiv: 2508.17627 | 适合人群：离散扩散模型、生成式 AI 推理优化。
最优步数不是看问题规模，是看问题的纠缠程度。