Research map / Learning theory and algorithms / Sample complexity
On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysis
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Uses fine-grained complexity under SETH to show modern Hopfield retrieval admits sub-quadratic variants only when pattern norms are below a sqrt(log tau) threshold, and builds a low-rank almost-linear-time Hopfield model with retrieval error and exponential capacity bounds.
Problem
Computational limits of modern Hopfield memory retrieval: the dense retrieval costs O(dML) time, and it is unclear when faster (sub-quadratic or almost linear) approximate retrieval is possible.
Approach
Reduce approximate nearest neighbor search (ANNS) to the approximate modern Hopfield retrieval problem (AHop) to get a SETH-based lower bound, which yields a norm phase transition at B = Theta(sqrt(log tau)); below it, a low-rank polynomial approximation of exp gives almost linear time retrieval with bounded error.
Key results
- Under SETH, AHop cannot be solved in truly sub-quadratic time when the pattern norm bound B exceeds Theta(sqrt(log tau)), giving a phase-transition criterion.
- The low-rank modern Hopfield model runs in O(tau r (g+d)) time, which is tau^(1+o(1)) when d=O(log tau), beta=Theta(1/d), and B=o(sqrt(log tau)).
- Approximation error of the efficient retrieval is bounded by 2MB*delta_A, and the model retains exponential-in-d memory capacity, though slightly smaller than the dense model.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reduce the maximum entry norm B below Θ(√log τ) | AHop · AHop, under SETH and realistic settings | running time: τ^{2-Ω(1)} | Helped |
| Use low-rank polynomial approximation for retrieval | Modern Hopfield retrieval · AHop, where B = o(√log τ) | running time: τ^{1+o(1)} | Helped |
| Use low-rank approximation with precision δ_A | Modern Hopfield retrieval · AHop | approximation error: 2MBδ_A | Helped |
| Use efficient low-rank approximate retrieval | Modern Hopfield retrieval · Memory storage and retrieval | memory capacity: exponential-in-d | Mixed |
Limitations
- Purely formal work; the authors state the results do not lead to practical implementations.
- No empirical experiments validating the approximation or runtime.
- Efficient model's memory capacity is marginally smaller than the standard dense model.
Experimental setup
Metrics: time complexity max-norm approximation error memory capacity
Baselines: dense modern Hopfield retrieval (softmax attention)
Builds on: Modern Hopfield Networks Hopfield Networks is All You Need Strong Exponential Time Hypothesis polynomial method for attention approximation
Closest papers by meaning
- Nonparametric Modern Hopfield Models (ICML 2025 · similarity 0.91)
- Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Models (ICML 2024 · similarity 0.90)
- Provably Optimal Memory Capacity for Modern Hopfield Models: Transformer-Compatible Dense Associative Memories as Spherical Codes (NeurIPS 2024 · similarity 0.89)
- Sparse and Structured Hopfield Networks (ICML 2024 · similarity 0.87)
- Outlier-Efficient Hopfield Layers for Large Transformer-Based Models (ICML 2024 · similarity 0.85)
- Continual Learning in Modern Hopfield Networks with an Application to Diffusion Models (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.