Fugu-MT 論文翻訳(概要): On the Complexity Theory of Masked Discrete Diffusion: From $\mathrm{poly}(1/ε)$ to Nearly $ε$-Free

論文の概要: On the Complexity Theory of Masked Discrete Diffusion: From $\mathrm{poly}(1/ε)$ to Nearly $ε$-Free

arxiv url: http://arxiv.org/abs/2509.21835v1
Date: Fri, 26 Sep 2025 03:50:17 GMT
ステータス: 翻訳完了
システム内更新日: 2025-09-29 20:57:54.162823
Title: On the Complexity Theory of Masked Discrete Diffusion: From $\mathrm{poly}(1/ε)$ to Nearly $ε$-Free
Title（参考訳）: Masked Discrete Diffusionの複素性理論について:$\mathrm{poly}(1/ε)$からほぼ$ε$-freeへ
Authors: Xunpeng Huang, Yingyu Lin, Nishant Jain, Kaibo Wang, Difan Zou, Yian Ma, Tong Zhang,
Abstract要約: マスク付き離散拡散(マスク付き離散拡散)は、トークンが識別される前に特別なマスクシンボルによって劣化するテキスト生成のフレキシブルパラダイムである。その結果,Eulerサンプルは,$tildeO(d2epsilon-3/2)$離散スコア評価で,総変量(TV)の$epsilon$-精度を達成できることが判明した。そこで我々は,有界スコアの仮定を取り除き,偏りのない離散スコア近似を保ったMask-Aware Truncated Uniformization (MATU) アプローチを提案する。
参考スコア（独自算出の注目度）: 49.34727933066799
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study masked discrete diffusion -- a flexible paradigm for text generation in which tokens are progressively corrupted by special mask symbols before being denoised. Although this approach has demonstrated strong empirical performance, its theoretical complexity in high-dimensional settings remains insufficiently understood. Existing analyses largely focus on uniform discrete diffusion, and more recent attempts addressing masked diffusion either (1) overlook widely used Euler samplers, (2) impose restrictive bounded-score assumptions, or (3) fail to showcase the advantages of masked discrete diffusion over its uniform counterpart. To address this gap, we show that Euler samplers can achieve $\epsilon$-accuracy in total variation (TV) with $\tilde{O}(d^{2}\epsilon^{-3/2})$ discrete score evaluations, thereby providing the first rigorous analysis of typical Euler sampler in masked discrete diffusion. We then propose a Mask-Aware Truncated Uniformization (MATU) approach that both removes bounded-score assumptions and preserves unbiased discrete score approximation. By exploiting the property that each token can be unmasked at most once, MATU attains a nearly $\epsilon$-free complexity of $O(d\,\ln d\cdot (1-\epsilon^2))$. This result surpasses existing uniformization methods under uniform discrete diffusion, eliminating the $\ln(1/\epsilon)$ factor and substantially speeding up convergence. Our findings not only provide a rigorous theoretical foundation for masked discrete diffusion, showcasing its practical advantages over uniform diffusion for text generation, but also pave the way for future efforts to analyze diffusion-based language models developed under masking paradigm.
Abstract（参考訳）: マスク付き離散拡散(マスク付き離散拡散)は、トークンが特殊マスクのシンボルによって徐々に劣化するテキスト生成のフレキシブルパラダイムである。このアプローチは強い経験的性能を示しているが、高次元設定における理論上の複雑さは未だ十分に理解されていない。既存の分析は、主に均一な離散拡散に焦点をあてており、より最近の試みでは、(1)広く使われているオイラーサンプリング、(2)限定的な有界スコア仮定を課すか、(3)マスク付き離散拡散の利点を均一に示さないかのいずれかに対処している。このギャップに対処するため、Euler sampler が$\epsilon$-accuracy in total variation (TV) with $\tilde{O}(d^{2}\epsilon^{-3/2})$ Discte score Evaluations を達成できることを示し、マスク付き離散拡散における典型的なEuler sampler の厳密な分析を提供する。そこで我々は,有界スコアの仮定を取り除き,偏りのない離散スコア近似を保ったMask-Aware Truncated Uniformization (MATU) アプローチを提案する。 MATUは、各トークンを最大1回アンマスクできるという特性を利用することで、$O(d\,\ln d\cdot (1-\epsilon^2))$のほぼ$\epsilon$-freeの複雑さを達成できる。この結果は、一様離散拡散の下での既存の均一化法を超越し、$\ln(1/\epsilon)$因子を排除し、収束を大幅に高速化する。本研究は,テキスト生成における一様拡散に対する実用的優位性を示すとともに,マスキングパラダイムの下で開発された拡散に基づく言語モデル解析への今後の取り組みの道を開くものである。

論文の概要: On the Complexity Theory of Masked Discrete Diffusion: From $\mathrm{poly}(1/ε)$ to Nearly $ε$-Free

関連論文リスト