Reproduce “On Powerful Ways to Generate: Autoregression, Diffusion, and Beyond” 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
Chenxiao Yang, Cai Zhou, David Wipf, Zhiyuan Li
Researchers from Toyota Technological Institute at Chicago (TTIC) and MIT introduce Any-Process Masked Diffusion Models (AP-MDM), an extension of standard diffusion models with learnable `remask`, `insert`, and `delete` operations. This new paradigm provides provable computational advantages over autoregressive and vanilla diffusion models, offering exponential speedups and improved scalability for complex reasoning tasks, while demonstrating superior sample efficiency and generalization on problems like Sudoku and parity checking.
Key insights
- Standard Masked Diffusion Models (MDMs) can simulate any Parallel Random Access Machine (PRAM) algorithm with optimal parallel time complexity, offering exponential speedups for parallelizable problems compared to ARMs.
- Both ARMs and vanilla MDMs are inherently limited for problems beyond complexity class P (e.g., NP-hard problems) when context length is polynomially bounded, due to their irreversible token generation.
- Any-Process MDM (AP-MDM) achieves universally efficient computation, capable of solving problems in PSPACE with polynomial space and optimal parallel time, a significant theoretical improvement over existing generative paradigms.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.