Reproduce “Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Yuxi Liu
This paper establishes a theoretical dichotomy for diffusion models, demonstrating that 'perfect' diffusion, characterized by an exact score function, is computationally limited to the `TC_0` complexity class. Conversely, 'bad' diffusion, where the score network can be arbitrarily designed, is proven to be Turing-complete, providing a theoretical framework for observed performance characteristics.
Key insights
- The inherent computational power of diffusion models is directly tied to the fidelity and constraints placed on their score-matching networks.
- Rapid convergence, often a benefit for speed, imposes a fundamental `TC_0` limitation on 'perfect' diffusion due to its constant-depth computational nature.
- Diffusion-like processes are not inherently limited; if the score function is not constrained by a true data distribution, they possess universal computational capabilities.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.