Sharp Capacity Thresholds in Linear Associative Memory: From Top-1 Retrieval to Tail-Average Learning
Nicholas Barnfield, Juno Kim, Eshaan Nichani, Jason D. Lee, Yue M. Lu
stat.ML, cs.IT, cs.LG
2026-05-07
A linear memory retrieves all n pairs top-1 iff d²/(n log n)>2. The log n is an extreme-value tax; without it only a percentile TAM guarantee survives at load n/d².
Associative memory asks a concrete question: store n key-value pairs, present a key, recover the matching value. Transformer FFNs and attention layers have been observed to behave like key-value tables, and theoretical work on factual recall and knowledge editing often reduces to this model. The thinnest version is linear: the memory is a d×d matrix W, and the score of candidate target uj on key vi is uj^T W vi.
Capacity is more than the d² degrees of freedom in W. It also depends on the retrieval criterion. The strictest one is top-1: every matched target must outrank all n-1 competitors. Nichani et al. (2024) showed that classical correlation matrix memory (CMM), the superposition of outer products, succeeds once d² ≥ C n (log n)^4. Both the log power and the leading constant were loose. This paper pins down the threshold for the entire class of data-dependent linear memories.
Keys and targets are i.i.d. isotropic Gaussians N(0, Id/d). The model isolates high-dimensional crosstalk and adds no semantic clustering.
Top-1 is handled from both sides. Achievability uses CMM plus a sparse repair. Coordinates split into a large block and a small one. The large block stores a rescaled CMM; queries whose margin falls below γ go into a deficient set. The small block has width about d/(log n)^{1/8} and applies a one-shot weighted outer-product correction only on those deficient queries. CMM alone is reliable once d²/(n log n)>8; after the repair the constant drops to 2. Impossibility uses a dual certificate. Each pairwise comparison corresponds to the matrix Aij=(ui-uj)vi^T. A nontrivial nonnegative linear dependence among these matrices makes it impossible for any W to make all inner products positive at once. The constant 2 is exactly where such a certificate exists with high probability.
The log n factor is an extreme-value cost. The matched score is order one. A single competitor has standard deviation about √n/d, and the largest of n-1 near-Gaussians multiplies that by √(2 log n). Equating the two scales yields d² ≈ 2 n log n. Winner-take-all pays for the strongest distractor, not the average one.
Drop the logarithm and enter the quadratic-load regime n/d²→α. Simultaneous top-1 is then impossible. The weaker question is whether the matched target can stay inside a fixed fraction of the ranking. Requiring rank≤k directly is nonconvex, so they use the Tail-Average Margin (TAM): the matched score must beat the average of the k strongest competitors. That average is a convex upper bound on the k-th order statistic, so a positive TAM margin certifies membership in the top-k list. With k/n→r∈(0,1) fixed, the guarantee is a percentile rank; the list is still Θ(n), not a shortlist. Learning uses logistic loss plus ridge, with an exponentially smoothed TAM, which keeps the program convex. The analysis develops a coupled leave-one-out argument: deleting one pair changes both its own signal and its role as a competitor for every other query, perturbing O(n) loss terms. After those induced changes, the leading shift of the optimizer is still the inverse leave-one-out Hessian applied to the single rank-one feature uh vh^T. The high-dimensional limit collapses to a two-parameter scalar variational problem.
Theorem 1 is a sharp threshold. Along any n,d→∞: if liminf d²/(n log n)>2, some linear memory retrieves all n associations with high probability; if limsup<2, no data-dependent linear memory can. Concurrent work by Giorlandino et al. (2026) conjectured the same constant on a decoupled model via a statistical-physics calculation. This paper proves it on the original dependent comparisons.
| Scheme | Threshold | Scope |
| Nichani et al. 2024, CMM | d² ≥ C n (log n)^4 | Sufficient, loose log power |
| CMM alone | d²/(n log n)>8 | Sufficient, and unimprovable for CMM |
| Any linear memory, top-1 | d²/(n log n)=2 | Constructible above, impossible below |
| TAM, ridgeless | α=n/d² < αc(r) | Percentile retrieval, average loss → 0 |
The ridgeless TAM threshold is closed-form: αc(r)=1/[(1+κr²)Φ(κr)+κr φ(κr)], with κr=φ(Φ^{-1}(1-r))/r. At r=0.15 this is αc≈0.294. Below it, average TAM loss vanishes and TAM retrieval holds for all but a vanishing fraction of keys; above it, the limiting loss stays positive. The threshold does not depend on the smoothing parameter β. A 2-D sweep at d=400 with ridge 1e-6, and a 1-D slice at d=600, r=0.15, β=30, both track the predicted curve. In the SAT phase the signal percentile has a hard lower edge pα=Φ(ρα); the unoptimized CMM percentile sits further back in the same plot.
For finite size they use weakly ridged softmax cross-entropy as a proxy, sweeping c=n log n/d² with effective ridge λn/d²=10^{-8}. The empirical norm peak sits above the critical value 1/2 (the reciprocal of 2) and drifts toward it only slowly. They conjecture the second-order correction dc²(n)=n(2 log n - 3 log log n + o(log log n)). Peak locations for d from 300 to 1200 fit a slope of -2.97 against the predicted -3.
How many must-be-exact facts a single linear memory can hold now has an answer with a sharp constant. If an FFN or attention weight is treated as a key-value table, the top-1 scale is d²≍2n log n, not d²≍n. Intermediate computation that only needs the answer to remain in a fixed-fraction candidate set can return to quadratic load, and that guarantee is learnable by convex optimization.
This is asymptotic theory, not a new architecture. The achievability construction is an existence argument via sparse repair; the cross-entropy and TAM-ERM used in the simulations are not proved to reach the same constant 2. TAM lists a fixed fraction of the vocabulary, so it is not a retrieval shortlist.
Every theorem is tied to independent isotropic Gaussian embeddings. Real token embeddings cluster and correlate, so distractors are not near-independent Gaussians; the extreme-value tax could be heavier or lighter, and the paper does not say which. How the r→0 limit reconnects to the log n of top-1 is left open. The second-order correction remains a conjecture, matching a decoupled Gaussian-direction model and moderate-d simulations.
Top-1 achievability is a repair construction, not cross-entropy minimization. Finite-size drift is large at moderate d, so the empirical critical load is noticeably conservative. TAM certifies percentile rank, not a shortlist; k=Θ(n) is of limited use for actual decoding. There are no experiments on real language models.