Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval

Forum topic · 小凯 · 2026-05-08

Summary

This arXiv paper (2605.05189) by Nicholas Barnfield, Juno Kim, Eshaan Nichani, Jason D. Lee, and Yue M. Lu studies how many key-value associations a d x d linear memory matrix can store, showing the answer depends on the retrieval criterion. Under top-1 retrieval, where each signal must beat its largest distractor, capacity requires the logarithmic scaling d^2 ~ n log n. The authors prove that the correlation matrix memory construction achieves this scale via a sharp phase transition, and that this scaling is necessary for any linear memory, making the logarithm the intrinsic extreme-value cost of winner-take-all decoding. They then propose the Tail-Average Margin (TAM), a convex upper-tail criterion for listwise retrieval, under which capacity follows the quadratic scale d^2 ~ n. Using a two-parameter scalar variational principle, they derive an exact asymptotic theory for the TAM empirical-risk minimizer, yielding a closed-form critical load separating satisfiable and unsatisfiable phases in the ridgeless limit, plus limiting laws for true scores, competitor scores, margins, and percentile profiles. A small-tail extrapolation leads to a conjectural sharp top-1 threshold of d^2 ~ 2n log n.

*Translated and adapted from a Chinese forum post on zhichai.net. Paper: arXiv:2605.05189*

Overview

Field: Machine Learning
Authors: Nicholas Barnfield, Juno Kim, Eshaan Nichani, Jason D. Lee, Yue M. Lu
Published: 2026-05-06
arXiv: 2605.05189

Key Points

The paper asks: how many key-value associations can a d x d linear memory matrix store? The answer depends not only on the d^2 degrees of freedom of the memory matrix, but also on the retrieval criterion.
In an isotropic Gaussian model for stored pairs, top-1 retrieval — where every signal must beat its largest distractor — requires the logarithmic model-size scale d^2 ~ n log n.
The correlation matrix memory construction (storing associations by superposing key-target outer products) provably achieves this scale through a sharp phase transition, and the same scaling is necessary for any linear memory. The logarithm is thus the intrinsic extreme-value price of winner-take-all decoding.
The paper then studies listwise retrieval, where the correct target need not be the unique top-scoring item but should remain among the strongest candidates.
To formalize this regime, the authors introduce the Tail-Average Margin (TAM), a convex upper-tail criterion that certifies inclusion of the correct target in a controlled candidate list. Under this criterion, capacity follows the quadratic scale d^2 ~ n.

Asymptotic Theory

At load n/d^2 -> alpha, an exact asymptotic theory for the TAM empirical-risk minimizer is developed via a two-parameter scalar variational principle.
The theory exhibits rich phenomenology:
In the ridgeless limit, it yields a closed-form critical load separating satisfiable and unsatisfiable phases.
It predicts the limiting laws of true scores, competitor scores, margins, and percentile profiles.
A small-tail extrapolation further leads to the conjectural sharp top-1 threshold d^2 ~ 2n log n.

Abstract (Original)

How many key-value associations can a d x d linear memory store? We show that the answer depends not only on the d^2 degrees of freedom in the memory matrix, but also on the retrieval criterion. In an isotropic Gaussian model for the stored pairs, we show that top-1 retrieval, where every signal must beat its largest distractor, requires the logarithmic model-size scale d^2 ~ n log n. We prove that the correlation matrix memory construction, which stores associations by superposing key-target outer products, achieves this scale through a sharp phase transition, and that the same scaling is necessary for any linear memory. Thus the logarithm is the intrinsic extreme-value price of winner-take-all decoding. We next consider listwise retrieval, where the correct target need not be the unique top-scoring item but should remain among the strongest candidates. To formalize this regime, we propose the Tail-Average Margin (TAM), a convex upper-tail criterion that certifies inclusion of the correct target in a controlled candidate list. Under this listwise retrieval criterion, the capacity follows the quadratic scale d^2 ~ n. At load n/d^2 -> alpha, we develop an exact asymptotic theory for the TAM empirical-risk minimizer through a two-parameter scalar variational principle. The theory has a rich phenomenology: in the ridgeless limit it yields a closed-form critical load separating satisfiable and unsatisfiable phases, and it predicts the limiting laws of true scores, competitor scores, margins, and percentile profiles. Finally, a small-tail extrapolation further leads to the conjectural sharp top-1 threshold d^2 ~ 2n log n.

---

*Auto-collected on 2026-05-08.*