Sharp Capacity Thresholds in Linear Associative Memory: From Top-1 Retrieval to Tail-Average Learning
Nicholas Barnfield, Juno Kim, Eshaan Nichani, Jason D. Lee, Yue M. Lu
stat.ML, cs.IT, cs.LG
2026-05-07
高斯嵌入下,线性记忆一次取对的临界是 d²=2n log n:之上可构造,之下任何数据依赖线性记忆都失败。log n 是赢者通吃必须付的极值税。
联想记忆问的是一件很具体的事:存下 n 对键值,拿出键,能不能把对应的值捞回来。Transformer 的 FFN 和 attention 都被观测到在做类似的键值查找,事实回忆、知识编辑的理论分析也经常落到这个模型上。最瘦的版本是线性的:记忆就是一张 d×d 矩阵 W,键 vi 对候选目标 uj 的分数是 uj^T W vi。
容量不能只数 W 有 d² 个自由度,还要看「取回成功」怎么定义。最严的标准是 top-1:每个键的匹配目标必须压过其余全部 n-1 个干扰。Nichani 等人 2024 年证明,经典相关矩阵记忆(CMM,把外积直接叠加)在 d² ≥ C n (log n)^4 时能一次取对。对数幂次和前置常数都还松着。这篇要把整类数据依赖线性记忆的临界钉到一个数。
键和目标全部独立,服从各向同性高斯 N(0, Id/d)。这个设定把高维干扰单独拎出来,不额外假设语义簇。
top-1 分两边做。可行性用「CMM + 稀疏修补」。坐标切成一大一小两块:大块做缩放后的 CMM,边际不够 γ 的查询记进缺陷集;小块宽度约 d/(log n)^{1/8},只用缺陷查询的加权外积做一次修补。CMM 单独要 d²/(n log n)>8 才稳,补完之后常数降到 2。不可能性走对偶证书:每个比较对应矩阵 Aij=(ui-uj)vi^T。如果存在不全为零的非负系数让这些矩阵线性相关,任何 W 都不可能让所有内积同时为正。阈值 2 恰好让这种证书以高概率存在。
log n 的来源是极值。匹配分数量级是 1,单个干扰标准差大约 √n/d,n-1 个近高斯里最大的还要再乘 √(2 log n)。两者打平,得到 d² ≈ 2 n log n。赢者通吃付的是最强干扰的税,不是平均干扰的税。
去掉这个对数,进入 n/d²→α 的二次负载区,一次取对已经不可能。他们改问匹配目标能不能稳定待在前 r 比例的候选里。直接卡 rank≤k 是非凸的,于是改用尾部平均边际(TAM):匹配分数必须超过最强 k 个干扰的平均值。平均值是第 k 名的凸上界,TAM 为正就保证目标进了 top-k 名单。k/n→r∈(0,1) 固定时,这是百分位保证,名单长度仍是 Θ(n),不是短名单。学习用 logistic 损失加岭回归,TAM 做指数平滑,整段凸。分析上他们写了一套耦合留一法:删掉一对样本,既改它自己的信号,也改它作为别人干扰的那一列,一共扰动 O(n) 个损失项。展开之后,优化器的主扰动仍是留一 Hessian 的逆作用在单个 rank-1 特征 uh vh^T 上。高维极限塌成两个标量参数的变分问题。
Theorem 1 给出尖锐相变。任意 n,d→∞:若 liminf d²/(n log n)>2,存在线性记忆以高概率一次取对全部 n 条;若 limsup<2,任何数据依赖线性记忆都以高概率失败。并发工作 Giorlandino 等人 2026 在解耦模型上用统计物理猜到同一个常数,这篇把它在原始依赖结构里证完。
| 方案 | 临界 | 口径 |
| Nichani 等 2024 的 CMM | d² ≥ C n (log n)^4 | 充分条件,对数幂次松 |
| 单独 CMM | d²/(n log n)>8 | 充分,且对 CMM 不可再压 |
| 任意线性记忆,top-1 | d²/(n log n)=2 | 之上可构造,之下全失败 |
| TAM, ridgeless | α=n/d² < αc(r) | 百分位取回,平均损失趋于 0 |
αc(r) 有闭式:αc(r)=1/[(1+κr²)Φ(κr)+κr φ(κr)],其中 κr=φ(Φ^{-1}(1-r))/r,φ、Φ 是标准正态密度和分布函数。r=0.15 时 αc≈0.294。α 小于它,平均 TAM 损失趋于 0,几乎所有键满足 TAM 取回;大于它,损失停在正值。这个阈值与平滑参数 β 无关。d=400、岭系数 1e-6 的二维扫描,以及 d=600、r=0.15、β=30 的一维切片,经验相变都贴着这条曲线。SAT 相里,匹配目标的百分位有硬下沿 pα=Φ(ρα),不会掉到这个百分位以下;同一设置下未优化的 CMM 百分位明显更靠后。
有限尺寸下他们用弱岭 softmax 交叉熵当代理,扫 c=n log n/d²,有效岭系数 λn/d²=10^{-8}。经验范数峰始终高于临界 1/2(对应 Theorem 1 的 2),向 1/2 漂得很慢。猜想二阶修正是 dc²(n)=n(2 log n - 3 log log n + o(log log n));d 从 300 扫到 1200 的七个峰,拟合斜率 -2.97,对着预测的 -3。
一层线性记忆能装多少「一次必须取对」的事实,现在有一个精确到常数的答案。如果把 FFN 或 attention 当成键值表,一次取对的标尺是 d²≍2n log n,不是 d²≍n。中间计算如果只需要正确答案留在固定比例的候选集里,就可以回到二次负载,并且这份保证能用凸优化学出来。
这是渐进理论,不是新架构。可行性构造是存在性的稀疏修补,实验里用的交叉熵和 TAM-ERM 并没有被证明顶到同一个常数 2。TAM 的名单长度是词表的固定比例,当不了检索短名单。
全部定理绑在独立各向同性高斯嵌入上。真实词向量有簇、有相关,干扰不再是近独立高斯,极值税可能更重也可能更轻,论文没有给出。r→0 怎样接到 top-1 的 log n,是他们自己标出的开放问题。二阶修正仍是猜想,只在解耦高斯方向模型和中等 d 的仿真上对得上。
top-1 的可行性证明是一块修补构造,不是交叉熵最小化。中等维度上有限尺寸漂移很大,经验临界明显偏保守。TAM 保证百分位,不保证短名单,k=Θ(n) 对实际解码帮助有限。没有真实语言模型实验。