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

• URL: http://arxiv.org/abs/2605.05189v1
• Date: Wed, 06 May 2026 17:53:20 GMT
• Title: Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval
• Abstract summary: How many key-value associations can a $dtimes d$ linear memory store?<n>We show that the answer depends not only on the $d2$ degrees of freedom in the memory matrix, but also on the retrieval criterion.
• Score: 59.859592671274704
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: How many key-value associations can a $d\times 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\asymp 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\asymp n$. At load $n/d^2\toα$, 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\sim 2n\log n$.

Related papers

• Batch Size or Negatives? A Selection Rule for Memory-Constrained Recommender Training [0.8782033967242784]
  Large-scale neural recommender systems are typically trained with a softmax cross-entropy objective over the full item vocabulary.<n>For a fixed budget $B = n k$, it remains unclear whether one should prioritize larger batches or the inclusion of more negative items.<n>We propose a theoretical and empirical foundation for configuring memory during the training of recommender systems.
  arXiv  Detail & Related papers  (2026-08-11T15:29:01Z)
• Wavelet Variance Equipartition as a Threshold for World-Model Quality and Quantum Kernel TN-Simulability [0.0]
  We identify the wavelet scaling exponent $$ as a critical diagnostic.<n>We establish $= 1/2$ as a sharp transition boundary for the classical simulability of amplitude-encoded quantum kernels.<n>We prove this variance scales strictly as $Var[X] = (d-2)$.
  arXiv  Detail & Related papers  (2026-05-12T05:41:12Z)
• Factual recall in linear associative memories: sharp asymptotics and mechanistic insights [11.11958822145404]
  We study the limits of storing and retrieving input--output associations with neural networks.<n>A linear associative memory maps $p$ input embeddings in $mathbbRd$ to their corresponding$d$-dimensional targets.<n>We show that a decoupled model can store up to $p_c log p_c / d2 = 1 / 2$ associations.
  arXiv  Detail & Related papers  (2026-05-11T16:24:02Z)
• Linear-Readout Floors and Threshold Recovery in Computation in Superposition [0.0]
  Two recent approaches to computation in superposition reach different capacity regimes.<n>We argue these results are not contradictory because they maintain different interface invariants.<n> Robust nonlinear reset beyond the Hnni template is left open.
  arXiv  Detail & Related papers  (2026-05-02T02:11:31Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• How Many Features Can a Language Model Store Under the Linear Representation Hypothesis? [8.283029791278187]
  We introduce a mathematical framework for the linear representation hypothesis (LRH)<n>LRH asserts that intermediate layers of language models store features linearly.<n>We prove that $d = O_(frack2log klog (m/k))$ is required while $d = O_(k2log m)$ suffices.
  arXiv  Detail & Related papers  (2026-02-11T17:49:32Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)
• Deletion and Insertion Tests in Regression Models [1.2891210250935148]
  A basic task in explainable AI (XAI) is to identify the most important features behind a prediction made by a black box function $f$. The insertion and deletion tests of Petsiuk et al. Kernel can be used to judge the quality of algorithms that rank pixels from most to at least important for a classification.
  arXiv  Detail & Related papers  (2022-05-25T00:55:47Z)
• Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits [88.6139446295537]
  We study the problem of online generalized linear regression in the setting of a generalized linear model with possibly unbounded additive noise. We provide a sharp analysis of the classical follow-the-regularized-leader (FTRL) algorithm to cope with the label noise. We propose an algorithm based on FTRL to achieve the first variance-aware regret bound.
  arXiv  Detail & Related papers  (2022-02-28T08:25:26Z)
• Policy Optimization Using Semiparametric Models for Dynamic Pricing [1.3428344011390776]
  We study the contextual dynamic pricing problem where the market value of a product is linear in its observed features plus some market noise. We propose a dynamic statistical learning and decision-making policy that combines semiparametric estimation from a generalized linear model with an unknown link and online decision-making.
  arXiv  Detail & Related papers  (2021-09-13T23:50:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.