# Modern Hopfield Networks Require Chain-of-Thought to Solve mathsfNC1-Hard Problems

arXiv: https://arxiv.org/abs/2412.05562 · HTML: https://mlsanity.com/paper/2412.05562/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 45 references that are in the map.
- First posted on arXiv 7 Dec 2024.

## Builds on (most cited first, 30 of 31)

- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Hopfield Networks is All You Need](https://mlsanity.com/paper/2008.02217/) (2020)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [Dense Associative Memory for Pattern Recognition](https://mlsanity.com/paper/1606.01164/) (2016)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [Large Associative Memory Problem in Neurobiology and Machine Learning](https://mlsanity.com/paper/2008.06996/) (2020)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022)
- [Modern Hopfield Networks and Attention for Immune Repertoire Classification](https://mlsanity.com/paper/2007.13505/) (2020)
- [Dense Associative Memory is Robust to Adversarial Inputs](https://mlsanity.com/paper/1701.00939/) (2017)
- [How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation](https://mlsanity.com/paper/2310.04064/) (2023)
- [On Sparse Modern Hopfield Model](https://mlsanity.com/paper/2309.12673/) (2023)
- [On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysis](https://mlsanity.com/paper/2402.04520/) (2024)
- [Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Models](https://mlsanity.com/paper/2404.03827/) (2024)
- [Outlier-Efficient Hopfield Layers for Large Transformer-Based Models](https://mlsanity.com/paper/2404.03828/) (2024)
- [STanHop: Sparse Tandem Hopfield Model for Memory-Enhanced Time Series Prediction](https://mlsanity.com/paper/2312.17346/) (2023)
- [The Fine-Grained Complexity of Gradient Computation for Training Large Language Models](https://mlsanity.com/paper/2402.04497/) (2024)
- [Training Tensor Attention Efficiently: From Cubic to Almost Linear Time](https://mlsanity.com/paper/2405.16411/) (2024)
- [Circuit Complexity Bounds for RoPE-based Transformer Architecture](https://mlsanity.com/paper/2411.07602/) (2024)
- [Transformers in Uniform TC0](https://mlsanity.com/paper/2409.13629/) (2024)
- [Context-enriched molecule representations improve few-shot drug discovery](https://mlsanity.com/paper/2305.09481/) (2023)
- [Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time](https://mlsanity.com/paper/2408.13233/) (2024)
- [BiSHop: Bi-Directional Cellular Learning for Tabular Data with Generalized Sparse Modern Hopfield Model](https://mlsanity.com/paper/2404.03830/) (2024)
- [What is my math transformer doing? -- Three results on interpretability and generalization](https://mlsanity.com/paper/2211.00170/) (2022)
- [Provably Optimal Memory Capacity for Modern Hopfield Models: Transformer-Compatible Dense Associative Memories as Spherical Codes](https://mlsanity.com/paper/2410.23126/) (2024)
- [Nonparametric Modern Hopfield Models](https://mlsanity.com/paper/2404.03900/) (2024)

## Built on by (most cited first, 9 of 9)

- [ATLAS: Learning to Optimally Memorize the Context at Test Time](https://mlsanity.com/paper/2505.23735/) (2025)
- [It's All Connected: A Journey Through Test-Time Memorization, Attentional Bias, Retention, and Online Optimization](https://mlsanity.com/paper/2504.13173/) (2025)
- [The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity](https://mlsanity.com/paper/2412.06148/) (2024)
- [Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Counting](https://mlsanity.com/paper/2510.04401/) (2025)
- [Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformers](https://mlsanity.com/paper/2412.18040/) (2024)
- [Circuit Complexity Bounds for Visual Autoregressive Model](https://mlsanity.com/paper/2501.04299/) (2025)
- [T2VTextBench: A Human Evaluation Benchmark for Textual Control in Video Generation Models](https://mlsanity.com/paper/2505.04946/) (2025)
- [Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent](https://mlsanity.com/paper/2504.04702/) (2025)
- [Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective](https://mlsanity.com/paper/2510.05494/) (2025)

## Abstract (arXiv)

Modern Hopfield Networks (MHNs) have emerged as powerful components in deep learning, serving as effective replacements for pooling layers, LSTMs, and attention mechanisms. While recent advancements have significantly improved their storage capacity and retrieval efficiency, their fundamental theoretical boundaries remain underexplored. In this paper, we rigorously characterize the expressive power of MHNs through the lens of circuit complexity theory. We prove that poly(n)-precision MHNs with constant depth and linear hidden dimension fall within the mathsfDLOGTIME-uniform mathsfTC0 complexity class. Consequently, assuming mathsfTC0 neq mathsfNC1, we demonstrate that these architectures are incapable of solving mathsfNC1-hard problems, such as undirected graph connectivity and tree isomorphism. We further extend these impossibility results to Kernelized Hopfield Networks. However, we show that these limitations are not absolute: we prove that equipping MHNs with a Chain-of-Thought (CoT) mechanism enables them to transcend the mathsfTC0 barrier, allowing them to solve inherently serial problems like the word problem for the permutation group S5. Collectively, our results delineate a fine-grained boundary between the capabilities of standard MHNs and those augmented with reasoning steps.