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

Computer Science > Machine Learning arXiv:2509.21835 (cs) [Submitted on 26 Sep 2025 (v1), last revised 1 Mar 2026 (this version, v2)] Title:On the $ε$-Free Inference Complexity of Absorbing Discrete Diffusion Authors:Xunpeng Huang, Yingyu Lin, Nishant Jain, Kaibo Wang, Difan Zou, Yian Ma, Tong Zhang View a PDF of the paper titled On the $\epsilon$-Free Inference Complexity of Absorbing Discrete Diffusion, by Xunpeng Huang and 6 other authors View PDF HTML (experimental) Abstract: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/\epsilon))$ 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 $\epsilon$-TV convergence with $\mathcal{O}(d \ln d)$ complexity-\emph{independent} of the error tolerance $\epsilon$-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-ba...