Study Reveals Sharp Capacity Thresholds for Linear Associative Memory
jasondeanlee · x · 2026-08-24
This research by Nicholas Barnfield, Juno Kim, and collaborators investigates the storage capacity limits of a $d \times d$ Linear Associative Memory (LAM). The paper establishes a sharp threshold for perfect Top-1 retrieval under isotropic Gaussian embeddings, governed by the formula $d^2 = 2n \log n$.
- Capacity Threshold: When $d^2/(n \log n) > 2$, a linear memory can be constructed to retrieve all $n$ associations with high probability; below this threshold, no data-dependent linear memory can achieve this.
- Logarithmic Cost: The $\log n$ factor represents the unavoidable extreme-value cost of winner-take-all decoding.
- Weaker Retrieval: Without the logarithmic factor, simultaneous Top-1 retrieval is impossible. The study introduces the Tail-Average Margin (TAM) to capture this weaker goal. When $k/n \to r$, the memory is learned via empirical risk minimization with a smoothed TAM objective.
More from Research
- Solving RL latency: Hillclimb cleaner proxy tasks — JoshPurtell · 2026-08-24
- Qwen-Video-Edit enables instruction-based video editing by repurposing an image model — AgeNo5351 · 2026-08-24
- Paper: Pretraining Recurrent Networks without Recurrence via Transformer Teacher — chrmanning · 2026-08-24
- Mathematician shares latest thoughts on the relationship between math and AI — littmath · 2026-08-24
- NeurIPS 2026 Workshop AIDaR focuses on data readiness for scientific AI — arjunrajlab · 2026-08-24
- Why AI chips move trillions of bits for cheap arithmetic — prateekj · 2026-08-24