Slower Generalization, Faster Memorization: A Sweet Spot in Algorithmic Learning¶

会议: NeurIPS 2026
arXiv: 2605.14659
OpenReview: https://openreview.net/forum?id=FDIVnGvUBM
领域: 优化/理论
关键词: 算法学习, 泛化时序, Grokking, 结构化输出, 记忆与规则学习

一句话总结¶

揭示在结构化输出的算法学习任务中，验证集精确匹配泛化在适中的数据集规模下收敛最快（存在数据集规模“甜点”），推翻了数据越多必然加速验证收敛的直觉，并阐明部分规则学习可反向加速训练拟合。

研究背景与动机¶

大模型经验缩放定律与算法任务中的延迟泛化（Grokking）研究普遍建立在一种直觉之上：随着训练集规模跨越揭示底层算法规则的“临界数据量”（Critical Data Size）阈值后，提供更多的数据理应单调加速模型在验证集上的收敛速度。在诸如模算术或标量乘除等传统算法任务中，数据量的增长不仅能促使泛化电路迅速击败记忆电路，而且更充沛的数据覆盖往往使得验证精度以更少的优化更新步数达到完美状态。

然而，这一标准直觉主要源于输出结构极度紧凑（如标量或短字符串）的经典基准。在需要多步递推并产生复杂依赖网的结构化输出任务中，情况发生了根本性变化。对于序列比对中的 Needleman–Wunsch（NW）动态规划得分矩阵生成等任务，较短的输入序列会诱导出一个维度显著扩大且单元格之间存在严格递归依赖的输出表格。模型要想实现严格的“精确匹配”（Exact-Match），不仅要掌握通用的递推规则，还必须对全表中每一个单元格的计算细节做到零差错。

这种高输出复杂度的任务在优化动力学上暴露出一对此前被忽视的核心矛盾：增加数据规模一方面能够提供更密集的结构覆盖以促进算法规则发现，另一方面却会在规则发现效益边际递减后，急剧堆叠全矩阵残差细节的精确拟合（或样本级记忆）负担。本文的核心 idea 是：在具有强递归依赖的结构化输出算法任务中，解耦“泛化可行性起始点”与“基于优化更新步的收敛最优极值点”，揭示验证集精确匹配存在一个中间数据集规模“甜点”（Sweet Spot），在此平衡点之外增加数据反而导致泛化变慢，而规则的涌现反能加速训练拟合。

方法详解¶

整体框架¶

本文构建了一个高度受控的算法学习基准与探测流水线，旨在严格度量固定优化协议下，训练集规模 \(N\) 如何重塑模型达到高训练精度与高验证泛化精度的时序动态。系统输入为两段离散符号序列，自回归 Transformer 模型需生成完整的序列比对动态规划得分矩阵，并与纯标量/短输出任务（三位数乘法、十位数加法）进行跨任务对比；随后引入解耦探针，严格追踪规则学习与残差拟合对优化步数的竞争效应。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入序列对 (x, y)"] --> B["Needleman–Wunsch 结构化动态规划矩阵生成<br/>自回归解码输出递归得分矩阵"]
    B --> C["多阈值精确匹配跨越时间分析<br/>追踪训练 IT(τ, N) 与验证 IV(τ, N) 步数"]
    C --> D["随机后缀探测与训练-随机增益诊断<br/>引入无规则独立后缀 G(t) = AT(t) - AR(t)"]
    D --> E["双重压力机制判别<br/>平衡规则覆盖收益与残差精确拟合开销"]

关键设计¶

1. Needleman–Wunsch 结构化动态规划矩阵生成任务构建：解耦规则学习与残差精确拟合

为制造结构紧凑规则与高维度相互依赖输出的张力，本文采用生物信息学经典的 Needleman–Wunsch 全局序列比对算法生成全得分矩阵 \(M \in \mathbb{Z}^{(L+1) \times (L+1)}\) 作为预测目标。给定有限字母表 \(\Sigma = \{A, C, G, T\}\) 及长度为 \(L\) 的两序列 \(x, y \in \Sigma^L\)，目标矩阵边界按固定空位惩罚初始化（\(M_{0,0}=0, M_{i,0}=i \cdot g, M_{0,j}=j \cdot g\)），内部单元格遵循严格的局部极值递归方程：

\[M_{i,j} = \max\{M_{i-1,j-1} + s(x_i, y_j),\; M_{i-1,j} + g,\; M_{i,j-1} + g\}\]

其中匹配得分 \(s=5\)，不匹配罚分 \(-4\)，空位罚分 \(g=-5\)。该设计精妙之处在于：输入仅为 \(2L\) 个字符（\(L=5\) 时共 10 个 token），而目标矩阵展平后包含 36 个整数单元格。行优先的自回归生成顺序恰好使递归所需的先验依赖项（左、上、左上）始终在序列前面输出。评估指标采用最为严苛的全矩阵“精确匹配”——全表只要有一个单元格数值错误，该样本即判定为失败。相比于输出长度仅为 6 位的乘法基准，NW 任务迫使网络在有限参数下承载大量相互制约的递推计算，将算法规则与局部残差细节明确分离。

2. 多阈值精确匹配跨越时间分析与数据集最优甜点（Sweet Spot）：分离泛化起始点与梯度步收敛极值

为在时序尺度上刻画泛化与记忆过程，本文定义了精确匹配阈值 \(\tau \in (0, 1)\) 下的训练跨越时间 \(I_T(\tau; N)\) 与验证跨越时间 \(I_V(\tau; N)\)，分别表示训练精度与验证精度首次达到 \(\tau\) 所需的最少优化器更新步数。若在最大预算（50,000 步）内未达到则标记为截断（censored）。由此导出两个关键特征量：临界数据规模 \(N_c(\tau) = \min\{N: I_V(\tau; N) \text{ 未被截断}\}\)，以及最优数据集甜点规模 \(N^\star(\tau) = \arg\min_N I_V(\tau; N)\)。

实验揭示出颠覆直觉的两个时序规律：其一，对于严苛验证阈值（\(\tau=0.98\)），验证收敛时间呈显著的非单调 U 型曲线，满足 \(N_c(\tau) < N^\star(\tau) < N_{\max}\)。当 \(N < N^\star\) 时，数据过少导致结构覆盖不足，模型极难发现算法规则或泛化极度延迟；而在跨越最优规模 \(N^\star\) 后，验证集跨越所需更新步数反而单调激增，出现“泛化变慢（Slower Generalization）”。其二，在弱验证能力（如 \(\tau \in [0.1, 0.5]\)）初次显现的临界区间，增大数据量 \(N\) 反而使训练集达到严格高精度的更新步数 \(I_T(0.98; N)\) 显著减少，呈现“记忆加速（Faster Memorization）”。这直接推翻了“拟合训练集纯粹是逐样本查表式记忆”的经典假说，证明部分规则学习能为训练集拟合提供可复用的归纳偏置。

3. 随机后缀探测（Random-Suffix Probe）与训练-随机增益诊断：量化样本特异性记忆与可迁移规则的动态演化

为实证验证上述“双重优化压力”假说，本文设计了一种精巧的合成诊断探针：在每个 NW 矩阵目标的末尾追加一个 4-bit 独立均匀采样的随机二进制后缀。矩阵部分由全局确定性规则产生，而后缀在各样本间独立、无法由输入推导。在纯输出长度或逐样本拟合假说下，仅 4 位的短后缀应远比 36 维递推矩阵更容易被拟合。

实验通过同时跟踪矩阵训练精度 \(A_T(t)\)、矩阵验证精度 \(A_V(t)\) 以及随机后缀训练精度 \(A_R(t)\)，构建训练-随机增益诊断量 \(G(t) = A_T(t) - A_R(t)\)。结果表明：在早期阶段，只有当增益 \(G(t) > 0\) 时验证精度 \(A_V(t)\) 才开始起步，且二者高度重合，呈现近乎完美的线性分解 \(A_T(t) \approx A_R(t) + A_V(t)\)。这从实验上无可辩驳地证实：网络对结构化矩阵的拟合率先借力于可迁移的通用规则，而非样本查表；而在规则收益饱和后，面对庞大数据集，全矩阵各个单元格的严格精确匹配残差必须依赖类似无规则后缀的艰难优化过程，从而在更新步数维度上构成了决定性的收敛拖累。

损失函数 / 训练策略¶

模型采用基于自回归交叉熵损失的标准优化方案。网络架构为纯解码器 Transformer（Decoder-only），深度 \(D \in \{3, 4, 5, 6\}\)，每层注意力头数为 \(D\)，嵌入维度 \(d_{\text{emb}} = 64D\)，前馈全连接隐层维度 \(d_{\text{ff}} = 256D\)。优化器选用 AdamW，权重衰减系数设为 \(0.1\)，动量参数 \(\beta_1 = 0.9, \beta_2 = 0.99\)。学习率采用余弦退火调度，初始值为 \(10^{-3}\)，最终平滑衰减至 \(10^{-4}\)。单步微批次大小为 8，通过 20 步梯度累积实现等效全局批次大小 160。训练总预算上限为 50,000 个优化器更新步，每隔 100 步在固定验证集上全面评估精确匹配准确率。

实验关键数据¶

主实验¶

主实验在统一优化配置下对比了 Needleman–Wunsch 矩阵生成任务（序列长度 \(L=5\)，模型深度 \(D=6\)）与标量算术基准（3 位数乘法、10 位数加法）在不同训练样本规模 \(N\) 下达到严格精确匹配阈值 \(\tau=0.98\) 所需的优化器更新步数。

任务	样本规模 \(N\)	验证收敛步数 \(I_V(0.98)\)	训练收敛步数 \(I_T(0.98)\)	现象判定
3 位数乘法	\(1\text{k}\)	截断（未达标）	4,200	欠泛化 / 临界以下
3 位数乘法	\(10\text{k}\)	18,500	14,100	跨越临界泛化
3 位数乘法	\(100\text{k}\)	11,200	9,800	规模单调加速泛化
3 位数乘法	\(500\text{k}\)	9,400	8,900	维持最快收敛
NW 矩阵生成 (\(L=5\))	500	截断（未达标）	截断（未达标）	容量与数据双重匮乏
NW 矩阵生成 (\(L=5\))	\(2\text{k}\)	36,800	28,400	泛化起始点 \(N_c(0.98)\)
NW 矩阵生成 (\(L=5\))	\(5\text{k}\)	16,200	12,800	最优数据集甜点 \(N^\star\)
NW 矩阵生成 (\(L=5\))	\(10\text{k}\)	21,500	17,600	泛化减速（残差拟合拖累）
NW 矩阵生成 (\(L=5\))	\(50\text{k}\)	34,000	31,200	显著减速
NW 矩阵生成 (\(L=5\))	\(100\text{k}\)	45,600	43,800	极端拟合负担，收敛最慢

消融实验¶

消融实验考察模型深度 \(D \in \{3, 4, 5, 6\}\) 及序列长度 \(L \in \{4, 5\}\) 对临界规模 \(N_c(0.98)\)、最优甜点 \(N^\star(0.98)\) 以及随机后缀探针在不同数据规模下的拟合优先级表现。

配置维度	变量取值	临界规模 \(N_c\)	最优甜点 \(N^\star\)	最佳验证步数	随机后缀拟合关系（较大 \(N\)）
模型深度 (\(L=5\))	\(D=3\)	\(3\text{k}\)	\(5\text{k}\)	24,100	矩阵拟合显著领先后缀
模型深度 (\(L=5\))	\(D=4\)	\(2\text{k}\)	\(5\text{k}\)	19,800	矩阵拟合显著领先后缀
模型深度 (\(L=5\))	\(D=5\)	\(2\text{k}\)	\(5\text{k}\)	17,400	矩阵拟合显著领先后缀
模型深度 (\(L=5\))	\(D=6\)	\(2\text{k}\)	\(5\text{k}\)	16,200	矩阵拟合显著领先后缀
序列长度 (\(D=6\))	\(L=4\)	800	\(2\text{k}\)	9,100	矩阵拟合领先后缀
序列长度 (\(D=6\))	\(L=5\)	\(2\text{k}\)	\(5\text{k}\)	16,200	矩阵拟合领先后缀
探针消融 (\(D=6\))	\(N=1\text{k}\) (小数据)	-	-	-	\(A_T\) 与 \(A_R\) 同步缓慢提升
探针消融 (\(D=6\))	\(N=10\text{k}\) (大数据)	-	-	-	\(A_T\) 先行饱和， \(A_R\) 严重滞后

关键发现¶

最优甜点对深度具有强鲁棒性：在 \(D \in \{3, 4, 5, 6\}\) 各深度配置下，验证集跨越时间对数据集规模均呈现严格的非单调 U 型响应。随着模型深度增加，参数表征能力增强使得临界数据门槛 \(N_c\) 略微降低，最优收敛步数从 24,100 步压缩至 16,200 步，但极值点均稳定落在 \(N=5\text{k}\) 附近。
epoch 归一化与 update 视角的本质差异：若将横坐标换算为通过完整数据集的数据轮数（Epochs），大模型数据依然符合传统直觉（\(N\) 越大所需 Epoch 越少）。这证明“泛化变慢”是纯粹建立在参数优化更新步（Optimizer Updates）与实际计算吞吐维度上的客观约束，揭示了样本复用与计算效率的权衡。
记忆与泛化的非纯序贯性：经典 Grokking 理论通常认为网络先在训练集上完成过度拟合与记忆，随后在平坦极小值处经历表征相变以产生泛化。本文的多阈值分析清晰地证明：在弱验证精度区间，部分泛化规则早于严格训练拟合完成前便已建立，并直接反哺于加速训练集的整体拟合。

亮点与洞察¶

颠覆“更多数据必能加速泛化”的机械教条：敏锐地指出数据集扩增不仅带来规则覆盖收益，同时也会带来样本特异性精确拟合的负向计算负担，首次在结构化输出任务中精确标定了非单调的数据集最优甜点。
随机后缀探测法（Random-Suffix Probe）的设计极具说服力：将具备严格物理规则的矩阵与毫无规律的 4 位后缀串联在一个 target 中，用同一网络在同一优化轨迹下清晰观测到“规则驱动拟合优先于无序记忆”，形成了极佳的因果证据链。
对算法任务与大模型推理训练的启发：在长链推理（CoT）或结构化代码/表格生成中，过分盲目堆叠海量无差异的长序列合成监督数据，可能会因尾部残差项的微小扰动而陷入更新效率泥潭，适度精选覆盖核心逻辑递推的小规模数据集反而能以最少计算量达成最优泛化。

局限与展望¶

受控合成环境的外推边界：本文实验集中于有限状态转移与确定性递归关系的 Needleman–Wunsch 矩阵及算术运算，输入输出字母表有限且序列长度较短（\(L \le 5\)），与开放域自然语言大模型的泛化动力学存在复杂度代差。
行优先序列化偏置的影响：输出矩阵采用行优先展开，与 NW 算法的动态规划依赖顺序（左/上向右下传播）高度吻合。若采用对角线展开、列优先或并行无序输出头，优化景观与收敛甜点的位置可能发生未知漂移。
未深入解析底层神经回路机制：随机后缀探针虽从宏观精度分离了规则与记忆，但未对注意力头进行回路修剪（Circuit Pruning）或权重范数机制分析，尚不能具象化描绘模型在何时何地完成由归纳回路替代记忆回路的微观跃迁。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次在结构化输出算法任务中发现并系统证明了数据集规模验证收敛“甜点”，并揭示了部分规则学习反向加速记忆拟合的动力学。
实验充分度: ⭐⭐⭐⭐☆ 实验设计高度严谨，多深度、多长度、多任务对照完备，随机后缀探针逻辑闭环，唯合成任务场景略显单一。
写作质量: ⭐⭐⭐⭐⭐ 论证环环相扣，概念定义精炼明晰，对实验现象的归因克制且富有理论洞见。
价值: ⭐⭐⭐⭐☆ 对深入理解神经网络内部规则学习与记忆表征竞争机制、以及长输出结构化微调数据配比具有重要指导价值。