归纳推理的极限：整数序列基准测试中的描述长度难度与记忆差距

# 整数序列基准测试中的描述长度难度与记忆差距  
来源：https://arxiv.org/html/2608.29411

## 归纳的尽头：整数序列基准测试中的描述长度难度与记忆差距  
###### 摘要  
来自《整数数列线上大全》（OEIS）的整数序列越来越多地被用于基准测试语言模型的数学推理能力。我们利用一个可精确计算的参考学习器——基于 P-递归（全纯）递推类的两部分最小描述长度（MDL），在序列的每个前缀上逐项评估——来探究此类基准测试实际衡量的内容。由此得出三项发现：  
第一，MDL 难度是一种*参数计数*。发现点 \(n_d\)，即符号假设首次优于逐字存储的前缀长度，几乎完全由所选算子的阶数与次数的组合可识别性边界所预测。它不随项的量级变化：将斐波那契数列缩放十二个数量级后 \(n_d\) 保持不变，因为假设必须编码其自身的初始条件，而量级会相互抵消。  
第二，在大规模数据下，学习器呈现出我们手工构建语料库无法产生一次的规律：在 20,000 个 OEIS 序列中，89.98% 的序列在某个前缀上符合某种递推关系，但在完整长度上*不符合任何*递推关系。我们将此称为*荒野*——归纳获得理论，失去理论，且永不复得。  
第三，在按 MDL 规律分层的序列上评估三个语言模型，*驳斥*了我们的预注册假设：模型不会在 MDL 报告无理论时捏造答案，而是适当采取谨慎态度。确信的错误*反转*集中于*简单*分层，其中表面能力实际上是对序列的识别而非对其规则的归纳。因此，OEIS 衍生的基准测试在很大程度上衡量的是记忆能力，而 MDL 提供了一种廉价、无污染的难度信号，这是它们目前所缺乏的。  
代码、数据及所有模型响应已发布于 https://github.com/sabilashang/where-induction-runs-out。

## 1 引言  
整数序列是检验数学推理能力的理想测试：输入简短，答案可验证，且 OEIS 提供了数十万免费序列。它们已成为语言模型的标准基准测试。基准测试的价值取决于其难度度量，然而何种因素使一个序列比另一个更难——是增长速度、数学深度，还是锁定规则所需的项数——并不明显。  
本文通过一个可精确计算的参考学习器回答了这个问题，并用该答案来审计基准测试实际测量的内容。该学习器采用两部分 MDL，基于全纯递推类，在序列各项逐个到达时应用于每个前缀。我们选择此类是因为其 MDL 假设可通过 \(\mathbb{Q}\) 上的线性代数精确计算（无搜索启发式干扰测量），并且它是整数序列的自然符号类。  
此类学习器的自然动态图景如下：给定 1, 2, 4, 16，它尝试 \(a_n = n\)，被反驳，转而尝试 \(a_n = 2n\)，再次被反驳，再尝试 \(a_n = 2^n\)，最终可能将分段分支拼接到不再整体拟合的公式上。这种将归纳视为连续修正的图景，构成了形式学习理论中“思维改变”概念的基础，也是 Schmidhuber 将趣味性描述为可压缩性导数的依据。然而现代文献仅报告*终点*：最终表达式是否正确，或最终程序有多短。我们测量了轨迹，定义了*修正谱* \(R(n) = L(n+1) - L(n)\) 以及两个精确地标——发现点和稳定点。  

我们的发现依次如下：  
1. **修正在经典序列中罕见，在大规模中常见（§4）**。仅 2/61 个经典序列曾发生修正，因为 MDL 具有自正则性：过拟合递推所需比特数超过其解释的数据，因此不会被选中。在 OEIS 规模下，比例上升至 315/2,780（11.3%），且与长度相关。  
2. **难度即参数计数（§5）**。发现点由可识别性边界 \(n_{\text{id}} = (r+1)(d+1) + s + r\) 预测，这仅是所选算子的阶与次数的组合函数——在 89% 的已标记经典语料库中精确预测，在 100% 中误差在 ±1 以内，而基于压缩的预测器平均绝对误差（MAE）为 3.20。  
3. **增长无关紧要（§6）**。一项跨越十二个数量级的控制缩放实验显示 \(n_d\) 保持不变，因为量级同时以相同速率放大假设和逐字编码，从而抵消。  
4. **荒野（§8）**。89.98% 的序列在某前缀上符合某种递推，但在全长上不符合任何递推——这是我们的经典语料库一次也无法产生的领域。结构修正一旦发生，几乎总是单次事件而非级联。  
5. **基准测试衡量记忆（§9）**。在按 MDL 分层的序列上评估三个语言模型，驳斥了我们的预注册假设并提出更强假设：确信的错误集中于*简单*分层，其中表面能力实则是 OEIS 识别而非归纳。  
我们将最后一点视为实际贡献。MDL 随度计算廉价、独立于项的量级，且（不同于公开数据集上的准确率）无法通过记忆膨胀。

## 2 相关工作  
#### 线性复杂度轮廓  
修正谱最接近的定量亲属来自密码学而非机器学习。二进制序列的线性复杂度轮廓（LCP）\(L(s, N)\) 是生成其前 \(N\) 项的最短 LFSR 长度，通过 Berlekamp–Massey 算法计算；随着 \(N\) 增加，其*跳跃*已被深入研究。这恰是线性递推在有限域上的特例的修正谱。我们有三点重要区别：首先，我们的假设类是全纯的而非 \(\mathbb{F}_q\)-线性的，允许多项式系数，从而涵盖阶乘、二项式和卡特兰型序列。其次，我们的度量是基于两部分 MDL 目标的比特码长，而非寄存器长度，因此不同形状的假设可直接比较。第三，领域与目标颠倒：密码学文献研究伪随机密钥流，希望轮廓不规则，而我们研究结构化数学序列，探究其规律性意味着什么。我们在附录 B 中报告 LCP 作为基线；它区分全纯与非全纯序列，但无法区分其中的类别。  

#### 思维改变复杂度  
形式学习理论量化学习者在极限收敛前改变猜想的频率。思维改变复杂度是针对整个目标类的最坏情况边界（整数或构造序数），计数改变次数。相比之下，修正是经验性、逐序列的轨迹，单位为比特。两者在量化方式、单位和对象上正交；§4 的结果可解读为观察到 MDL 归纳在经典序列上的经验思维改变次数几乎总是一。  

#### MDL 稳定化  
Poland 和 Hutter 证明了在线预测中两部分 MDL 在可数模型类上的收敛与损失界限，并给出了 MDL 估计器*稳定化*的充分条件。该工作是 §4 的理论背景；它确立稳定化最终会发生，而我们在具体序列上测量它立即发生，并精确刻画其何时不发生。  

#### 符号回归与序列归纳  
d'Ascoli 等训练 Transformer 推断整数与浮点序列的递推，在 OEIS 子集上评估；Gauthier 等搜索生成 OEIS 序列的短程序；经典符号回归与归纳程序合成在其他领域追求相同目标。它们均报告最终表达式或最终程序大小。从有限项猜测全纯递推是计算机代数的标准做法；我们将其用作精确预言机而非最终目标。基于压缩的趣味性与智能解释启发了对轨迹的研究，但未计算轨迹。

## 3 设置  
表 1 列出了下文使用的符号。  

**表 1：全文使用的符号**  

### 3.1 编码  
所有描述长度均基于前缀无关编码（单位为比特），因此两部分求和是真正的码长且满足 Kraft 不等式。对于自然数 \(k \geq 0\)，我们使用 Elias γ 编码，\(\ell(k) = 2 \lfloor \log_2(k+1) \rfloor + 1\)；带符号整数需额外一位符号位。前缀 \(s_{1:n}\) 的*逐字*模型成本为  
\[ L_{\text{lit}}(s_{1:n}) = \ell(n) + \sum_{i=1}^n \ell_\pm(s_i) \quad (1) \]  
此模型始终适用，这使得每个序列（包括无递推的序列）的 MDL 码长有限。

### 3.2 假设类  
我们的类 \(\mathcal{H}\) 由全纯算子组成  
\[ \sum_{i=0}^r p_i(n) s_{n+i} = 0, \qquad p_i(n) = \sum_{j=0}^d c_{ij} n^j, \quad (2) \]  
其中系数 \(c_{ij}\) 为整数，加上运行递推所需的 \(r\) 个初始项。令 \(d=0\) 即得 C-有限（常系数）情况。假设 \(H \in \mathcal{H}\) 的成本为  
\[ L(H) = \ell(r) + \ell(d) + \sum_{i,j} \ell_\pm(c_{ij}) + \sum_{k=1}^r \ell_\pm(s_k). \quad (3) \]  
对于斐波那契数列，\(r=2, d=0\)，系数为 \((1,1,-1)\)（编码 \(s_n + s_{n+1} - s_{n+2} = 0\)），初始项为 \((0,1)\)。则 \(\ell(r)=3, \ell(d)=1\)，三个系数各 4 比特，两个初始项分别 2 和 4 比特，故 \(L(H)=22\)。我们仅接受 \(H\) 确实整除所有可用项，且其首项多项式 \(p_r\) 在所用范围内非零，从而 \(H\) 真正确定序列，成为其合法编码。由于 \(H\) 精确重现数据，\(L(D|H)=0\)，两部分目标简化为 (3)。前缀的 MDL 码长为  
\[ L(n) = \min\Big\{\, \min_{H \in \mathcal{H},\, H \models s_{1:n}} L(H), \;\; L_{\text{lit}}(s_{1:n}) \,\Big\}. \quad (4) \]  
寻找内部最小值是精确的：对于每个 \((r,d)\)，(2) 是关于 \((r+1)(d+1)\) 个未知数 \(c_{ij}\) 的齐次线性系统，因此我们通过大素数模检测秩亏，然后在 \(\mathbb{Q}\) 上精确计算零空间，取每个基向量的本原整数向量。我们按参数计数递增枚举 \((r,d)\)，使用分支定界剪枝，并要求系统超定度松弛为 \(s=2\) 个方程——计算机代数猜测中的标准保护。§4 表明此保护近乎冗余。

### 3.3 修正谱  
修正谱逐项记录下一个整数是被预测、仅被存储，还是迫使学习器改变其假设。

###### 定义 1（修正谱）  
对于有 \(N\) 项的序列 \(s\)，\(n\) 处的*原始修正*为 \(R(n) = L(n+1) - L(n)\)，*归一化修正*为  
\[ \rho(n) = \frac{R(n)}{L_{\text{lit}}(s_{1:n+1}) - L_{\text{lit}}(s_{1:n})} = \frac{L(n+1) - L(n)}{\ell_\pm(s_{n+1})}. \quad (5) \]  
*修正谱*即轨迹 \(\{\rho(n)\}_n\)。归一化基于新到达项的逐字成本，使 \(\rho\) 无标度并具有直接解释：\(\rho=1\) 表示该项以完整逐字成本吸收（无新学习），\(\rho=0\) 表示该项免费（现有假设已蕴含），\(\rho<0\) 表示该项触发简化，\(\rho \gg 1\) 表示其迫使代价高昂的重构。

###### 观察 1（精确性）  
\(L(H)\) 不依赖于 \(n\)。因此，当所选假设不变且为结构性时，\(R(n)=0\) *精确成立*，每个非零 \(R(n)\) 要么是真正的修正，要么是逐字段吸收。这就是我们使用原始增量而非压缩比的原因：比率仅因分母增长而漂移，产生虚假“事件”。

###### 定义 2（地标）  
*发现点* \(n_d\) 是使 \(L(n) = L(H^*)\) 成立的最小 \(n\)，其中 \(H^*\) 是使 \(L(H^*) < L_{\text{lit}}(s_{1:n})\) 成立的最简假设。*稳定点* \(n_s\) 是使 \(\rho(m)=0\) 对所有 \(m \geq n\) 成立的最小 \(n\)。  
设 \(n_{\text{id}}\) 是*可识别性边界*，即 \(n\) 的最小值使得 (2) 在 \(s_{1:n}\) 上存在非平凡解（秩不足）；设 \(n_{\times}\) 是*盈利点*，即 \(n\) 的最小值使得 \(L_{\text{lit}}(s_{1:n}) > L(H^*)\)（盈利：最少项数使假设划算），给出预测  
\[ n_d = \max(n_{\text{id}}, n_{\times}). \]  
序列在 \(n_{\text{id}} \geq n_{\times}\) 时为*识别受限型*，否则为*压缩受限型*。表 2 显示了 46 个可拟合序列的结果。

**表 2：发现点 \(n_d\) 的预测**  
单独的可识别性边界