# Sharp Capacity Thresholds in Linear Associative Memory: From Top-1 Retrieval to Tail-Average Learning

arXiv: https://arxiv.org/abs/2605.05189 · HTML: https://mlsanity.com/paper/2605.05189/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 60 references that are in the map.
- First posted on arXiv 6 May 2026.

## Builds on (most cited first, 17 of 17)

- [Transformer Feed-Forward Layers Are Key-Value Memories](https://mlsanity.com/paper/2012.14913/) (2020)
- [Toy Models of Superposition](https://mlsanity.com/paper/2209.10652/) (2022)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Hopfield Networks is All You Need](https://mlsanity.com/paper/2008.02217/) (2020)
- [Memory Networks](https://mlsanity.com/paper/1410.3916/) (2014)
- [Dense Associative Memory for Pattern Recognition](https://mlsanity.com/paper/1606.01164/) (2016)
- [Birth of a Transformer: A Memory Viewpoint](https://mlsanity.com/paper/2306.00802/) (2023)
- [Physics of Language Models: Part 3.3, Knowledge Capacity Scaling Laws](https://mlsanity.com/paper/2404.05405/) (2024)
- [Universal Hopfield Networks: A General Framework for Single-Shot Associative Memory Models](https://mlsanity.com/paper/2202.04557/) (2022)
- [Understanding Factual Recall in Transformers via Associative Memories](https://mlsanity.com/paper/2412.06538/) (2024)
- [Scaling Laws for Associative Memories](https://mlsanity.com/paper/2310.02984/) (2023)
- [Key-value memory in the brain](https://mlsanity.com/paper/2501.02950/) (2025)
- [Learning Associative Memories with Gradient Descent](https://mlsanity.com/paper/2402.18724/) (2024)
- [Do LLMs dream of elephants (when told not to)? Latent concept association and associative memory in transformers](https://mlsanity.com/paper/2406.18400/) (2024)
- [Sharp Capacity Scaling of Spectral Optimizers in Learning Associative Memory](https://mlsanity.com/paper/2603.26554/) (2026)
- [Transformers as Measure-Theoretic Associative Memory: A Statistical Perspective and Minimax Optimality](https://mlsanity.com/paper/2602.01863/) (2026)
- [Learning to Recall with Transformers Beyond Orthogonal Embeddings](https://mlsanity.com/paper/2603.15923/) (2026)

## Built on by (most cited first, 3 of 3)

- [Factual recall in linear associative memories: sharp asymptotics and mechanistic insights](https://mlsanity.com/paper/2605.10795/) (2026)
- [The Rank the Task Demands: A Causal Rank Law for Matrix Memories Trained on Group Composition](https://mlsanity.com/paper/2609.12259/) (2026)
- [A Geometry-Based Capacity Theory for Finite-Feature Associative Memory](https://mlsanity.com/paper/2610.09056/) (2026)

## Abstract (arXiv)

How many key-value associations can a d× d linear memory store? The answer depends not only on the d2 degrees of freedom in the memory matrix, but also on the retrieval criterion. Under isotropic Gaussian embeddings, we prove a sharp threshold for top-1 retrieval, where every signal must beat its largest distractor: the critical value of d2/(nlog n) is 2. Above the threshold, we explicitly construct a linear memory that retrieves all n associations with high probability; below it, no data-dependent linear memory can do so. The log n factor is therefore the unavoidable extreme-value cost of winner-take-all decoding. Without the logarithmic factor---that is, when n/d2→α∈(0,∞)---simultaneous top-1 retrieval is impossible. The matched target can nevertheless remain near the top of the ranking. We capture this weaker retrieval goal with the Tail-Average Margin (TAM), which, for list size k, compares each signal with the average of its k strongest competitors; a positive TAM margin certifies that the target belongs to the top-k candidate list. When k/n→ r∈(0,1), we learn the memory by empirical risk minimization with a smoothed TAM objective and derive an exact high-dimensional characterization through a two-parameter scalar variational problem. The result gives limiting laws for signal and competitor scores, margins, and percentile ranks. Sending the ridge parameter to zero after the high-dimensional limit yields a closed-form critical load αc(r) separating vanishing from positive average loss. The analysis in this work also develops a coupled leave-one-out method for matrix-valued empirical risk problems in which each sample enters many dependent comparisons, a tool that may be useful beyond associative memory.