Dense Associative Memory and the Sharpness of Separation

The classical Hopfield capacity of \(0.138N\) is not a property of associative memory. It is a property of one specific energy function, the quadratic one, and changing that function changes the capacity by orders of magnitude without touching the stored patterns, the retrieval rule's structure, or the size of the network. Replacing \(x^2\) with \(x^n\) takes capacity from linear in \(N\) to \(N^{n-1}\); replacing it with \(e^x\) takes it to exponential in \(N\). This is the single largest free lunch in the associative-memory literature, and understanding why it works tells you what attention is doing.

Write the energy over patterns, not over weights

Classical Hopfield energy is a quadratic form in the state, with patterns hidden inside the weight matrix. Krotov and Hopfield rewrote it as an explicit sum over stored patterns with a general interaction function \(F\):

With \(F(x) = x^2\) this recovers the classical model exactly (up to the diagonal term). With \(F(x) = x^n\) for \(n > 2\) it is a different machine: a network of \(N\) units can store and retrieve "many more patterns than the number of neurons" (Krotov and Hopfield, 2016, Dense Associative Memory for Pattern Recognition, NeurIPS, arXiv:1606.01164). The precise statement, as later restated and extended, is that \(M = \alpha_n N^{n-1}\) patterns can be stored if small retrieval errors are tolerated, and \(M = N^{n-1}/(c_n \log N)\) if every pattern must be an exact fixed point with probability approaching one, with \(c_n > 2(2n-3)!!\) (Demircigil, Heusel, Löwe, Upgang and Vermet, 2017, On a model of associative memory with huge storage capacity, arXiv:1702.01929).

Taking \(n \to \infty\) gives \(F(x) = e^x\), and that model's storage capacity is exponential in the number of neurons while its basins of attraction stay almost as large as the classical model's. Both results come from the same paper, and the second is the one modern work builds on.

The mechanism is separation, not storage

Why does the shape of \(F\) matter at all? Write any single-shot associative memory as three stages: compute a similarity between the query and every stored pattern, apply a separation function that amplifies the largest similarities relative to the rest, then project the resulting weights back onto the patterns. This decomposition covers classical Hopfield networks, Kanerva's sparse distributed memory and modern continuous Hopfield networks as instances that differ only in their similarity and separation functions (Millidge, Salvatori, Song, Lukasiewicz and Bogacz, 2022, Universal Hopfield Networks, ICML, arXiv:2202.04557).

Seen that way, capacity is a question about separation. The crosstalk that limits the classical model is the sum of contributions from patterns the query does not match. A quadratic \(F\) barely distinguishes a match from a near-match, so the \(M-1\) wrong patterns each contribute meaningfully and their noise grows until it drowns the signal. A degree-\(n\) polynomial raises the gap between the best match and the rest to the \(n\)th power; the exponential raises it further still. The wrong patterns are still there; they have simply been suppressed below the point where they matter. Millidge et al. also report that similarity functions other than the dot product, such as Euclidean or Manhattan distance, do substantially better on many tasks, which is the other half of the same knob.

The duality with a feedforward layer

Krotov and Hopfield's second observation is that a dense associative memory with a rectified-polynomial \(F\) corresponds to a feedforward network with one hidden layer, where the stored patterns are the rows of the first weight matrix and \(F\) is the hidden activation. The family of interaction functions includes logistic functions, rectified linear units, and rectified polynomials of higher degree, and the last group had not been used in deep learning at the time.

This is the bridge that makes the energy view relevant to transformers. If a one-hidden-layer network is a memory whose keys are rows of \(W_1\), then the feed-forward block of a transformer is one too, which is close to what was found empirically: feed-forward layers in transformer language models behave like key-value memories, with keys matching textual patterns in the training data and values inducing distributions over the output vocabulary, shallow patterns in lower layers and semantic ones in upper layers (Geva, Schuster, Berant and Levy, 2021, Transformer Feed-Forward Layers Are Key-Value Memories, EMNLP, arXiv:2012.14913).

When it breaks

Exponential capacity is addressability, not compression. The patterns are still stored explicitly: the model holds \(M\) vectors of \(N\) numbers whatever \(F\) is. What grows exponentially is the number of patterns that remain individually retrievable, which is a statement about interference, not about storage cost. A claim of exponential capacity with no mention of the memory footprint is being quoted out of context.

The capacity theorems are about random patterns. Both the polynomial and the exponential results assume patterns drawn at random, so they measure interference between unrelated items. Correlated patterns interfere far more, and no amount of sharpening fixes two memories that genuinely point in nearly the same direction.

Sharper separation means smaller basins. The two results above are not a strict improvement: the exponential model's basins are almost as large as the classical model's, not larger. Pushing \(n\) up buys capacity by making retrieval more selective, which is the same thing as being less tolerant of a corrupted query. Capacity and noise tolerance trade against each other, and the exponent is the dial.

The exponential form needs numerical care. \(e^{\xi \cdot s}\) overflows for any realistic dimension, so implementations work with log-sum-exp rather than the raw energy. This is not a detail: the log-sum-exp form is what makes the next model in this line, the modern Hopfield network, both stable and recognisable as softmax attention.

Tolerated errors versus exact fixed points. The two theorems quoted above differ by a \(\log N\) factor and by what they promise. Benchmarks quoting the generous figure while testing exact recall are comparing different quantities.