arXiv:2509.21835cs.LG2025-09

提出新方法实现无误差依赖的高效离散扩散采样,突破理论瓶颈。

On the $ε$-Free Inference Complexity of Absorbing Discrete Diffusion

  • 利用吸收态仅重置一次的结构优势,设计新采样算法
  • 收敛复杂度仅需O(d ln d),与误差ε无关,优于传统方法
  • 适用于高精度生成,尤其适合语言模型的掩码建模场景

吸收式离散扩散已成为离散数据生成的主流框架。然而,其经验成功与理论理解之间仍存在显著差距:现有分析未能证明其在复杂度上优于针对均匀扩散建立的 𝒪(d ln(d/ε)) 基线。本文通过揭示关键结构优势——均匀扩散会重复去噪有效元素,而吸收方案仅对每个吸收态去噪一次——提出了吸收感知截断均匀化(AATU)。证明AATU可在 ε-电视距离(TV)收敛下实现 𝒪(d ln d) 复杂度,且不依赖误差容限 ε,严格优于现有均匀基线。此外,该分析消除了以往研究中常见的有界得分假设。进一步将AATU扩展至时间不变参数化,自然导出一种均匀随机去噪顺序的插补型推理。结合懒更新策略,电视收敛仅需 𝒪(d) 次离散得分评估。这些结果不仅为吸收式离散扩散建立了严谨基础,确认其在高精度生成中的效率,也为基于掩码范式的扩散语言模型分析开辟新路径。

原文摘要 · Abstract (English)

Absorbing discrete diffusion has emerged as a dominant framework for discrete data generation. However, a significant disparity remains between its empirical success and theoretical understanding: existing analyses fail to demonstrate a complexity advantage over the $\mathcal{O}(d \ln(d/ε))$ baseline established for \emph{uniform} discrete diffusion. We bridge this gap by identifying a critical structural advantage: whereas uniform diffusion redundantly re-denoises valid elements, the absorbing scheme denoises each absorbing state exactly once. Leveraging this insight, we introduce \emph{Absorbing-Aware Truncated Uniformization} (AATU). We prove that AATU achieves $ε$-TV convergence with $\mathcal{O}(d \ln d)$ complexity-\emph{independent} of the error tolerance $ε$-thereby strictly outperforming existing uniform baselines. Beyond improving convergence rates, our analysis eliminates the restrictive bounded-score assumption commonly required in prior studies of uniformization-based inference. Furthermore, we extend AATU to time-invariant parameterizations, showing that it naturally adopts an imputation-type inference with a uniformly randomized denoising order. When combined with a lazy update strategy, TV convergence requires only $\mathcal{O}(d)$ discrete score evaluations. These results not only establish a rigorous foundation for absorbing discrete diffusion -- confirming its efficiency in high-accuracy generation -- but also open new avenues for analyzing diffusion-based language models under the masking paradigm.

扩散模型离散生成理论分析语言建模

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。