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

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.