On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysis
This work addresses computational efficiency challenges for researchers in machine learning and theoretical computer science, offering a fine-grained analysis that is incremental in refining existing models.
The paper investigates the computational limits of modern Hopfield models, establishing a phase transition in efficiency based on pattern norms, with sub-quadratic variants existing only below a specific criterion under SETH, and provides an example achieving linear scaling in computational time with proven error bounds and exponential memory capacity.
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.