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

How many key-value associations can a d times d linear memory store? The answer depends not only on the d squared 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 d 2/(n 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 n factor is therefore the unavoidable extreme-value cost of winner-take-all decoding. Without the logarithmic factor---that is, when n/d 2 toα in(0, infinity) ---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 to r in(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.