From 64 to over a million: memory capacity of linear layers, MLPs, self-attention derived

The post builds its argument step by step, starting with the simplest memory store: a linear layer that accumulates key-value pairs via outer products. This store's capacity is limited to about d_k memories because interference from other memories grows as more are added. The author then shows that an optimal linear store, which whitens the keys, doubles capacity to 2d_k.

Next, the post introduces nonlinearities: applying a ReLU or squared ReLU to the similarity scores suppresses low-similarity interference, boosting capacity to roughly d_k^p for a power p. For a squared ReLU, that's about 2,700 memories with 64-dimensional keys, far beyond the linear store's 64. This connects to MLPs in transformers, where feedforward layers act as key-value memories.

Finally, self-attention uses an exponential of the similarity, effectively summing over all powers, which leads to very good recall and a capacity that can exceed a million. The author notes that the original transformer paper briefly described the feedforward layer as a kind of attention, a passage removed from later versions.