基于序列模型的符号谜题递归推理

# 递归逻辑谜题的序列模型推理

来源：https://arxiv.org/html/2606.15686

Gowrav Mannem¹, Chowdhury Marzia Mahjabin¹, Jason Chen¹,², Shivank Garg¹, Kevin Zhu¹

¹Algoverse AI Research  
²Cornell University  
shivank@algoverseairesearch\.org

###### 摘要

大型语言模型在符号和算法任务上通常表现强劲，但这种表面能力可能掩盖其在问题变长、变难或轻微超出分布时的脆弱行为。当前推理基准的一个主要局限是，许多基准主要测试模型是否能产生有效答案，而较少关注解是否最小、鲁棒且在可控难度缩放下稳定。我们引入了 RecurrReason，这是一个难度可控的基准，包含四个递归逻辑谜题（汉诺塔、过河问题、积木世界和跳棋跳跃），配有 BFS 最优轨迹和一个单一可解释的难度参数 \(N \in \{1,\dots,10\}\)，共计 10,817 个独特谜题和 285,933 步操作。我们在一致的数据划分和评估标准下，对两个 Transformer 系列（T5 式编码器-解码器模型和 GPT-2 式仅解码器模型）进行了基准测试，在 \(N=1\) 到 \(7\) 上训练，并在 \(N=8\) 到 \(10\) 上评估了保留的分布内实例和更难的分布外实例。微调后的预训练 T5 在积木世界上达到了 97.27% 的验证准确率和 81.00% 的分布外准确率；所有模型在过河问题上的所有条件下都得到了 0.00% 的准确率。失败模式分析表明，架构是比规模更重要的成功决定因素。预训练仅对具有局部结构转移函数的谜题产生迁移。我们的代码和数据集将在接收后开源。

## 1 引言

神经语言模型的最新进展使得多步推理看起来越来越易于实现。模型能生成连贯的中间步骤，模仿类似求解器的行为，并通常在精心策划的推理任务上得出正确的最终答案。然而，对于算法问题，正确性并不仅仅在于产生一个合理的终点。模型必须反复选择有效的中间动作，避免非法转移，在长跨度上保持一致性，并且理想情况下以最短长度的解达到目标。随着问题规模的增长，这些要求变得更加严苛，使得算法推理成为区分真正鲁棒性与浅层模式匹配的有用场景。最近的工作（Shojaee 等人，2025 (https://arxiv.org/html/2606.15686#bib.bib1)）认为，模型可能看起来有能力，但依赖于脆弱的启发式方法，这些方法在难度稍有变化时就会崩溃。我们在每一步都可以机械验证的环境中研究这一问题。递归逻辑谜题非常适合这一点：它们完全基于状态，具有明确的转移规则，使我们能够分别评估动作的有效性、目标达成和近乎最优的效率。相关工作讨论见附录 A (https://arxiv.org/html/2606.15686#A1)。

我们的贡献包括：

-   我们引入了一个统一的基准（RecurrReason），包含四个递归逻辑谜题，配有 BFS 最优解、可扩展的难度和逐步骤监督（10,817 个谜题，285,933 步操作）。
-   我们在一致的预处理和划分下，提供了两个 Transformer 系列（T5 式编码器-解码器和 GPT-2 式仅解码器）的受控比较。
-   我们设计了一个评估协议，专注于完整轨迹展开和推理特定指标（语法有效性、动作有效性、终止准确率和最优性差距）。
-   我们表明，谜题结构（特别是转移局部性、动作空间大小和解长度增长）是学习能力的主要决定因素。

## 2 RecurrReason 基准

一个递归推理游戏由以下要素定义：(1) 有限状态集 \(S\)，(2) 带有约束遵守转移的动作 \(A\)，(3) 目标集 \(G \subseteq S\)，(4) 递归多步结构，以及 (5) 需要系统搜索的约束满足。我们从 Shojaee 等人（2025 (https://arxiv.org/html/2606.15686#bib.bib1)）扩展了四个谜题，加入了排列增强、BFS 最优轨迹和自回归格式，得到了 10,817 个谜题和 285,933 步操作（附录 J (https://arxiv.org/html/2606.15686#A10)）。

表 1：RecurrReason 基准统计摘要。完整表格见附录 J (https://arxiv.org/html/2606.15686#A10)。

## 3 任务形式化、训练与评估

每个谜题被构建为预测下一步的任务。状态被序列化为字符串（例如，汉诺塔的盘到柱列表，积木世界的堆栈内容）。从每个 BFS 最优轨迹 \((s_0,\dots,s_T)\) 中，我们创建步骤对 \((s_t \to s_{t+1})\)。在评估时，模型自回归展开：\(\hat{s}_{t+1} = f_\theta(\hat{s}_t, g)\)，\(\hat{s}_0 = s_0\)，不提供真实状态。

#### 模型。

两种架构都学习 \(f_\theta: (s_t, g) \mapsto \hat{s}_{t+1}\)。T5-small（60M）（Raffel 等人，2020 (https://arxiv.org/html/2606.15686#bib.bib6)）：编码器对 \([s_t; s_g]\) 计算双向注意力，因此 \(s_t\) 中的每个标记在解码开始前都关注 \(s_g\) 中的每个标记；解码器通过交叉注意力生成 \(\hat{s}_{t+1}\)，使其充分利用目标作为每一步的首要条件信号。GPT-2（124M）（Radford 等人，2019 (https://arxiv.org/html/2606.15686#bib.bib7)）：因果掩码阻止 \(s_t\) 标记关注 \(s_g\)（因为 \(s_g\) 出现在拼接序列 \([s_t; s_g; \hat{s}_{t+1}]\) 的后面），为目标导向规划创造了结构瓶颈。完整的架构方程见附录 B (https://arxiv.org/html/2606.15686#A2)。符号定义见附录 I (https://arxiv.org/html/2606.15686#A9)。

#### 训练条件。

我们对每种架构评估三种实验条件：(1) 仅使用谜题数据从头训练，(2) 预训练零样本 (ZS)，即评估基础预训练检查点而不进行任何谜题特定训练，以及 (3) 预训练微调 (FT)，即从预训练检查点初始化并在谜题数据上微调。

#### 数据与划分。

我们枚举每个 \(N\) 的实例，计算 BFS 最优轨迹，应用谜题特定的增强，并序列化为模型就绪的输入（附录 E）。我们将 \(N=1\) 到 7 的实例分割为训练集和验证集（每个 \(N\) 内 80/20 随机分割）；\(N=8\) 到 10 用作分布外 (OOD) 评估。结果中“Val (%)”指来自 \(N=1-7\) 的保留验证实例；“OOD (%)”指来自 \(N=8-10\) 的所有实例。

#### 训练。

所有模型最小化预测下一状态的标记级交叉熵，掩码位置。两者都使用 AdamW（Loshchilov 和 Hutter，2019 (https://arxiv.org/html/2606.15686#bib.bib8)）（\(LR=10^{-4}\)，批次 16）并采用早停法。完整训练超参数见附录 M (https://arxiv.org/html/2606.15686#A13)。

#### 评估与指标。

展开在达到目标、输出无法解析、非法转移或超过水平 \(T_{\max}\) 时终止。主要指标是轨迹成功率、动作合法率和最优性差距 = \((|\hat{\tau}| - |\tau^\star|) / |\tau^\star|\)（仅对正确解决的谜题计算），该指标衡量相对于 BFS 最优解长度的多余步数百分比。

## 4 结果

一个谜题只有在展开通过有效状态在 \(T_{\max} = 2|\tau^\star|\) 步内到达 \(s_g\) 时才被认为解决（符号见附录 I (https://arxiv.org/html/2606.15686#A9)）。每个失败的展开被分类为四种模式之一：invalid_move（约束违反）、invalid_output（无法解析）、loop（循环）或 premature_stop（在目标前停止）。

### 4.1 跨谜题总结

表 2 (https://arxiv.org/html/2606.15686#S4.T2) 总结了每个谜题的最佳结果。积木世界是唯一表现出显著学习的谜题；其他三个谜题最多达到 1.11% 的验证准确率和 0.10% 的 OOD 准确率，这确立了谜题结构比架构或预训练更能决定可学习性。跳棋跳跃在 T5 和 GPT-2 上表现相同，因为两个模型只解决了起始状态等于目标状态的平凡实例，在所有需要实际移动的实例上都失败了。

表 2：跨谜题总结：每个谜题的最佳模型结果。完整的逐谜题结果表见附录 K (https://arxiv.org/html/2606.15686#A11)。

积木世界成功的三个叠加原因如下。首先，其转移函数是*局部*的：一个积木能否移动只需检查其源堆栈的顶部（\(O(1)\) 个标记），因此模型无需对整个棋盘进行推理即可产生有效移动。其次，其解长度线性增长（\(L(N) = O(N)\)），因此复合展开误差积累缓慢。第三，训练信号密集且一致：549 个训练谜题共享相同的移动语法，为模型提供了许多机会来泛化同一规则。其他三个谜题至少违反这些条件之一：汉诺塔有指数级的解长度（\(2^N - 1\)），过河问题需要每一步进行全局约束验证（\(O(N)\) 个标记），而跳棋跳跃结合了二次解长度和仅在极少数有效配置中出现的受限跳跃语法。

#### 零结果谜题。

汉诺塔：只有 1/9 的验证谜题被解决（\(N=1\)，一步移动）；所有 \(N \geq 2\) 的实例都失败，因为 \(L(N) = 2^N - 1\) 需要递归分解，而平面映射无法表示。跳棋跳跃：1.11% 的验证准确率完全对应起始等于目标的平凡实例。过河问题：尽管训练损失低，但处处为 0.00%；全局安全约束和组合动作空间（在 \(N=5\) 时多达 175 个候选）击败了所有模型。完整表格：附录 K (https://arxiv.org/html/2606.15686#A11)。

T5 预训练微调在 \(N=1\) 到 2 上达到 100%，在 \(N=7\) 之前保持在 93% 以上，并逐渐下降到 \(N=10\) 时的 75%（图 1 (https://arxiv.org/html/2606.15686#A3.F1)，附录 C (https://arxiv.org/html/2606.15686#A3)），这与规则泛化而不是记忆一致。逐渐的 OOD 退化（\(N=8\) 时 84%，\(N=9\) 时 84%，\(N=10\) 时 75%）与 GPT-2 的急剧崩溃形成对比，GPT-2 在所有条件下达到 21% 到 25% 的验证准确率，但 OOD 准确率下降到 0%。GPT-2 的失败模式系统性变化：在验证集上，循环占失败原因的 80% 到 92%，而在 OOD 上，invalid_move 占主导地位（>91%）。这种转变表明 GPT-2 学会了训练分布内哪些移动是*合法*的，但无法根据目标接近度进行选择，这是第 3 节 (https://arxiv.org/html/2606.15686#S3) 描述的因果注意力瓶颈的直接后果。失败模式分解在图 2 (https://arxiv.org/html/2606.15686#A4.F2)（附录 D (https://arxiv.org/html/2606.15686#A4)）中可视化，并在附录 L (https://arxiv.org/html/2606.15686#A12) 中表格化。

## 5 讨论

#### 架构比规模更重要。

T5（60M）在每一个谜题上都优于 GPT-2（124M），尽管参数只有后者的一半，因为其编码器提供了对 \([s_t; s_g]\) 的完全双向注意力，使目标成为解码器每一步的首要条件信号。GPT-2 的因果掩码阻止 \(s_t\) 关注 \(s_g\)，为目标导向规划创造了结构瓶颈。Ding 等人（2024 (https://arxiv.org/html/2606.15686#bib.bib25)）理论上证明了因果语言模型会收敛到比前缀（双向）模型更次优的解，形式化了为什么我们的目标标记在因果掩码下无法被最优利用。经验上，Wang 等人（2022 (https://arxiv.org/html/2606.15686#bib.bib26)）表明，具有非因果注意力的编码器-解码器模型在多任务微调后优于同等规模的仅解码器模型，而 Zhang 等人（2022 (https://arxiv.org/html/2606.15686#bib.bib29)）发现架构差异在较小规模时影响最大，这正是我们实验的范围。Csórdás 等人（2021 (https://arxiv.org/html/2606.15686#bib.bib28)）和 Tay 等人（2023 (https://arxiv.org/html/2606.15686#bib.bib27)）进一步证明，有针对性的架构修改可以改善系统性泛化，并能超越缩放定律，这与我们的发现一致：一个匹配良好的 60M 参数架构可以超越一个不匹配的 124M 参数架构。

#### 预训练的好处因谜题而异。

所有模型在零样本下得分均为 0.00%。微调后，预训练仅在转移函数为局部时才有帮助：T5 在积木世界（\(O(1)\) 验证）上提升 +97.27 个百分点，但在过河问题（\(O(N)\) 全局约束）上提升 +0.00 个百分点。GPT-2 预训练在 BW 上仅增加了 2.73 个百分点，证实了架构瓶颈限制了预训练所能贡献的范围。Talmore 等人（2020 (https://arxiv.org/html/2606.15686#bib.bib33)）经验表明，预训练在其一半的符号推理任务上失败，收益仅出现在任务结构与自然语言分布模式重叠的地方。Mueller 等人（2022 (https://arxiv.org/html/2606.15686#bib.bib34)）解释了其机制：预训练赋予一种层次性归纳偏差，仅对具有局部可分解结构的任务有帮助。Papadimitriou 和 Jurafsky（2020 (https://arxiv.org/html/2606.15686#bib.bib30)）证明，迁移取决于预训练域和目标域之间的共享结构属性，甚至跨模态也是如此。Furrer 等人（2020 (https://arxiv.org/html/2606.15686#bib.bib35)）在组合泛化基准上证实了这一点，发现预训练有助于局部可分解的划分，但在全局组合的划分上失败，这与我们的积木世界与过河问题结果精确平行。

#### 失败模式。

Invalid_move 反映了约束非泛化（McCoy 等人，2019 (https://arxiv.org/html/2606.15686#bib.bib3)）。BW 上的循环表明部分规则学习（合法移动但没有目标方向）。GPT-2 在 ToH 上的过早停止是由于低多样性训练数据中 \(\langle\texttt{STOP}\rangle\) 的统计过表征。完整分解：附录 L (https://arxiv.org/html/2606.15686#A12)。

#### 可学习性由谜题结构决定。

三个属性设定了上限：(1) *转移局部性*（BW 为 \(O(1)\)，RC 为 \(O(N)\)），(2) *动作空间大小*（BW 为 \(O(K^2)\)，RC 为组合级），以及 (3) *解长度增长*。假设每步独立错误率 \(\varepsilon\)（小），成功概率在解轨迹上复合：\(P(\text{success}) = (1 - \varepsilon)^{L(N)} \approx e^{-\varepsilon L(N)}\)。(1) BW 有 \(L(N) = O(N)\)；CJ 有 \((N+1)^2 - 1\)；ToH 有 \(2^N - 1\)。这种复合效应是模仿学习下自回归展开的直接后果（Ross 等人，2011 (https://arxiv.org/html/2606.15686#bib.bib36)）。这解释了为什么即使 T5 在 \(N=1\) 的 ToH 成功也不能扩展到 \(N \geq 2\)。这些发现与 Valmeekam 等人（2022 (https://arxiv.org/html/2606.15686#bib.bib4)）和 Kambhampati（2024 (https://arxiv.org/html/2606.15686#bib.bib5)）一致：可靠的规划需要...