mlsanityData to 7 Oct 2026

On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysis

arXiv 2402.04520 ↗First posted 7 Feb 2024cs.LG cs.AI stat.MLcited by 41

Not on the map. Why?

Abstract (arXiv)

We investigate the computational limits of the memory retrieval dynamics of modern Hopfield models from the fine-grained complexity analysis. Our key contribution is the characterization of a phase transition behavior in the efficiency of all possible modern Hopfield models based on the norm of patterns. Specifically, we establish an upper bound criterion for the norm of input query patterns and memory patterns. Only below this criterion, sub-quadratic (efficient) variants of the modern Hopfield model exist, assuming the Strong Exponential Time Hypothesis (SETH). To showcase our theory, we provide a formal example of efficient constructions of modern Hopfield models using low-rank approximation when the efficient criterion holds. This includes a derivation of a lower bound on the computational time, scaling linearly with max# of stored memory patterns, length of input query sequence. In addition, we prove its memory retrieval error bound and exponential memory capacity.

Key facts. Cited by 41 papers in the map (data through 7 Oct 2026). First posted on arXiv 7 Feb 2024.

Builds on

0 of 0 references.

No references here yet.

Built on by

Cited by year

Citing papers per year: 2024: 25; 2025: 16.

41 papers.

Sort:

By area:

  1. 2024Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Modelscited by 38
  2. 2024Outlier-Efficient Hopfield Layers for Large Transformer-Based Modelscited by 38
  3. 2024Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Modelscited by 31
  4. 2024Circuit Complexity Bounds for RoPE-based Transformer Architecturecited by 26
  5. 2024Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Timecited by 22
  6. 2024BiSHop: Bi-Directional Cellular Learning for Tabular Data with Generalized Sparse Modern Hopfield Modelcited by 21
  7. 2024Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descentcited by 21
  8. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  9. 2024Conv-CoA: Improving Open-domain Question Answering in Large Language Models via Conversational Chain-of-Actioncited by 19
  10. 2024A Tighter Complexity Analysis of SparseGPTcited by 19
  11. 2024Looped ReLU MLPs May Be All You Need as Practical Programmable Computerscited by 19
  12. 2024HSR-Enhanced Sparse Attention Accelerationcited by 19
29 more
  1. 2024Provably Optimal Memory Capacity for Modern Hopfield Models: Transformer-Compatible Dense Associative Memories as Spherical Codescited by 19
  2. 2025T2VWorldBench: A Benchmark for Evaluating World Knowledge in Text-to-Video Generationcited by 18
  3. 2025Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Countingcited by 17
  4. 2024Nonparametric Modern Hopfield Modelscited by 16
  5. 2024Do LLMs dream of elephants (when told not to)? Latent concept association and associative memory in transformerscited by 14
  6. 2024Provable Differentially Private Computation of the Cross-Attention Mechanismcited by 14
  7. 2024Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformerscited by 12
  8. 2025Video Latent Flow Matching: Optimal Polynomial Projections for Video Interpolation and Extrapolationcited by 11
  9. 2025Circuit Complexity Bounds for Visual Autoregressive Modelcited by 10
  10. 2024Decoupled Alignment for Robust Plug-and-Play Adaptationcited by 9
  11. 2024Fundamental Limitations on Subquadratic Alternatives to Transformerscited by 9
  12. 2024Modern Hopfield Networks Require Chain-of-Thought to Solve mathsfNC1-Hard Problemscited by 9
  13. 2025Theoretical Guarantees for High Order Trajectory Refinement in Generative Flowscited by 9
  14. 2025T2VTextBench: A Human Evaluation Benchmark for Textual Control in Video Generation Modelscited by 9
  15. 2025Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transformcited by 9
  16. 2024Dense Associative Memory Through the Lens of Random Featurescited by 8
  17. 2025Fast and Low-Cost Genomic Foundation Models via Outlier Removalcited by 8
  18. 2025Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapsecited by 7
  19. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  20. 2024CoRMF: Criticality-Ordered Recurrent Mean Field Ising Solvercited by 3
  21. 2024Unlocking the Theory Behind Scaling 1-Bit Neural Networkscited by 3
  22. 2025Neural Algorithmic Reasoning for Hypergraphs with Looped Transformerscited by 3
  23. 2024Differentially Private Kernel Density Estimationcited by 2
  24. 2025Hyper-SET: Designing Transformers via Hyperspherical Energy Minimizationcited by 2
  25. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  26. 2025Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiencycited by 2
  27. 2024Binary Hypothesis Testing for Softmax Models and Leverage Score Modelscited by 1
  28. 2025On the Role of Hidden States of Modern Hopfield Network in Transformercited by 1
  29. 2025Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspectivecited by 0