Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval
Nicholas Barnfield, Juno Kim, Eshaan Nichani, [0.25em] Jason D. Lee, Yue M. Lu, [0.5em] Harvard University University of California, Berkeley Princeton University · 2026
Read Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval by Nicholas Barnfield, Juno Kim, Eshaan Nichani, [0.25em] Jason D. Lee, Yue M. Lu, [0.5em] Harvard University University of California, Berkeley Princeton University (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-05189.txt.
Introduction
Nicholas Barnfield and four co-authors find sharp capacity limits for linear associative memories, asking how many key-value pairs a square matrix memory can store and retrieve. The answer depends on the retrieval rule, not just the number of free entries. Under Gaussian embeddings, they prove a sharp threshold for the strictest rule, where every target must beat its strongest competitor.
Above the threshold they construct a memory that retrieves everything, and below it they prove no data-dependent linear memory can. The logarithmic cost in the threshold is the unavoidable price of winner-take-all decoding. For weaker top-list retrieval they introduce a tail-average margin measure and characterise the high-dimensional behaviour of learning with it exactly.
Catalog record
| CREATOR | Nicholas Barnfield, Juno Kim, Eshaan Nichani, [0.25em] Jason D. Lee, Yue M. Lu, [0.5em] Harvard University University of California, Berkeley Princeton University |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 225 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.05189