标题： 完美扩散是$\mathsf{TC}^0$ -- 无效扩散是图灵完备 显示英文标题

标题： Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete

摘要： 本文探讨了基于扩散的语言建模的计算复杂性。 我们证明了在扩散模型中，基于得分匹配网络的质量存在一种二分法。 一方面，一个能够精确计算某种初始分布得分函数的网络只能在$\mathsf{TC}^0$复杂度类内进行语言建模，这反映了快速收敛相关的限制。 另一方面，我们证明了如果不要求网络匹配任何得分函数，则扩散建模可以在某种意义上模拟任何图灵机。 这种二分法为扩散模型的能力和限制提供了一个理论视角，特别是针对需要序列计算的任务。 我们推测了我们理论结果的扩展，包括当扩散模型并不完美但只是良好时的情况。 我们还讨论了更广泛的背景和实际意义，并假设一种能够在序列和并行操作模式之间进行插值的机器学习架构将优于Transformer和扩散模型。 显示英文摘要

摘要： 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.