Reproduce “Modern Hopfield Networks Require Chain-of-Thought to Solve $\mathsf{NC}^1$-Hard Problems” 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
Yang Cao, Xiaoyu Li, Yuanpeng Li, Yingyu Liang, Zhenmei Shi, Zhao Song
Researchers formally characterize the expressive power of Modern Hopfield Networks (MHNs) and Kernelized Hopfield Networks (KHNs), showing they belong to the TC₀ complexity class. This work demonstrates that while standard MHNs cannot solve NC₁-hard problems, integrating a Chain-of-Thought mechanism allows them to overcome this limitation.
Key insights
- Standard Modern Hopfield Networks and Kernelized Hopfield Networks (with constant layers and polynomial precision) are inherently limited to the TC₀ complexity class, implying restrictions for tasks requiring deeper sequential reasoning.
- MHNs and KHNs are theoretically incapable of solving NC₁-hard problems, such as Undirected Graph Connectivity and Tree Isomorphism, which delineates a fundamental ceiling for their computational expressiveness without additional mechanisms.
- Integrating a Chain-of-Thought mechanism allows MHNs to transcend their constant-depth TC₀ limitations, enabling them to solve NC₁-complete problems by leveraging iterative, sequential reasoning steps.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.