完美扩散模型只能做TC⁰级计算，差的反而能模拟图灵机。
Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete
- 用精确得分网络时，语言建模受限于TC⁰复杂度
- 无得分匹配要求时，可模拟任意图灵机
- 揭示扩散模型在序列计算上的理论极限
本文探讨基于扩散的语言建模的计算复杂性。我们证明了一个基于得分匹配网络质量的二分定理：若网络精确计算某初始分布的得分函数，则语言建模能力仅限于TC⁰复杂度类，反映快速收敛带来的限制；反之，若不限制网络必须匹配任何得分函数，则扩散建模可在某种意义上模拟任意图灵机。这一二分定理为扩散模型的能力与局限提供了理论视角，尤其关乎需要序列计算的任务。我们还提出猜想，认为当扩散模型不完美但足够好时，该理论结果可能仍成立。文章进一步讨论了更广泛背景与实际意义，并推测一种能在串行与并行模式间切换的架构，或优于当前的Transformer与扩散模型。
原文摘要 · Abstract (English)
This paper explores the computational complexity of diffusion-based language modeling. We prove a dichotomy based on the quality of the score-matching network in a diffusion model. In one direction, a network that exactly computes the score function of some initial distribution can only perform language modeling within the $\mathsf{TC}^0$ complexity class, reflecting limitations tied to rapid convergence. In the other direction, we show that if there is no requirement for the network to match any score function, then diffusion modeling can simulate any Turing machine in a certain sense. This dichotomy provides a theoretical lens on the capabilities and limitations of diffusion models, particularly concerning tasks requiring sequential computation. We conjecture extensions of our theoretical results, including for the case where the diffusion model is not perfect, but merely good. We also discuss the wider context and practical implications, and hypothesize that a machine learning architecture that can interpolate between sequential and parallel modes of operation would be superior to both Transformers and diffusion models.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。