Transformer 中隐式演绎推理的扩展性研究

深度足够时，Transformer 隐式推理可逼近 CoT 显式推理

前置知识

Horn 子句

Horn 子句是至多含一个正文字的析取式，形如 $A_1 \land A_2 \land \dots \land A_n \rightarrow B$。Horn 子句的逻辑蕴含判定是 P-complete 的，意味着可在多项式时间内求解，但很难高效并行化。

本文所有理论分析和实验都建立在 Horn 子句的演绎推理上，读者需要先理解为何 forward-chaining 是顺序的，而 rule synthesis 可借助 pointer-jumping 并行化。

Forward-chaining 深度 $\delta$

把事实沿规则逐层前向推导直到得到查询，每经过一层 BFS 深度加一。证明深度 $\delta$ 是查询在 BFS 哪一层首次被推导出来，可作为推理难度的统一度量。

作者将 $\delta$ 设为关键变量，证明在深度受限 Transformer 中存在 $\lambda(\delta) = \Omega(\delta)$ 的层数下界，是全文实验设计与曲线读图的基础。

Chain-of-Thought（CoT）

CoT 让模型在给出最终答案前先生成中间推理步骤，相当于把一个复杂推理拆为多步串行计算。理论上 CoT 可扩大 Transformer 表达能力，但依赖自回归因果掩码，无法反向修订前期 token。

全文以 CoT 作为隐式推理的性能上界，并试图用 corrective objective 拉近直接预测与 CoT 的差距。

Shortcut Learning

模型利用训练数据中与标签虚假相关的浅层特征（如 token 数量、查询出现次数）绕过真正推理任务的现象。在逻辑推理中表现为用图深度代替可达性判断，导致 OOD 失效。

本文三大干预（r2、bidirectional mask、corrective objective）都是为了抑制 shortcut learning，这是理解方法动机的关键。

Procrustes 对齐

寻找两个表示集之间的正交变换 $R$ 使 $\min_R \|XR - Y\|_F$ 最小，可恢复经过旋转但保持几何结构的潜空间信息。

作者用 Procrustes 对齐把不同层隐藏状态映射到同一坐标系，从而用线性探针追踪 provability 信息如何随深度累积，是 Figure 7 的技术基础。

研究动机

尽管早期研究[4,5,6]表明 Transformer 可充当软定理证明器，并在训练未见深度上展现泛化能力，但后续工作[7]证明这些模型严重依赖训练分布中的虚假特征（如 query 出现次数、规则数量），无法真正 OOD 泛化。神经网络的低复杂度偏置[9,10]使其倾向走 shortcut[11,12,13,14]，而非按因果结构执行顺序算法[8]。在标准复杂度假设[16]下，深度受限模型不可能完美解决 Horn 可满足性或 AI 规划问题[17]，但具体的限制因素仍不清楚。此外，作者在 Appendix C 观察到即使是 RL 增强的开源大模型[28,29]，在符号推理的直接预测上仍明显落后于 CoT，而 RL 主要保留而非扩展基础模型的覆盖度[31]。

本文的目标是本文聚焦于在 Horn 子句演绎推理设定下，识别出基于复杂度和信息论的可忠实近似的扩展性规律，并把扩展性表述为注意力层数 $L$ 与头维度 $d_{head}$ 的函数。具体目标包括：建立 rule synthesis 的 $\lambda(\delta) = \Omega(\log \delta)$ 下界与 forward-chaining 的 $\lambda(\delta) = \Omega(\delta)$ 下界；用稀疏恢复框架 $m = \Omega(s \log(n/s))$[61,63,64] 分析注意力头维度的信息瓶颈；通过系统性消融判断能否在训练 horizon 内闭合隐式与显式推理的差距。

与已有工作不同的是，与依赖外部定理证明器[26,27]或简单扩大模型规模的工作不同，本文同时从理论、架构对齐和训练目标三个层面切入：提出 r2 对抗启发式来解耦虚假特征，引入双向前缀掩码消除顺序偏置，并设计 corrective objective 把 CoT 推理基元与直接预测对齐到一个序列中。关键切入角度是用算法对齐而非简单堆参数来突破 shortcut——这与[34,35,36,37,38]中关于因果/非因果解码器的讨论形成对比，论文发现自回归目标已足够让非因果解码器胜出。同时，文章用 Procrustes 对齐的线性探针[45,46]解决了跨层表示连续变换导致标准探针失效[44]的问题。

核心方法

方法整体思路是把演绎推理当作算法对齐问题：Transformer 之所以在 Horn 子句上失败，是因为模型架构、训练目标和数据分布都未与 forward-chaining 算法匹配。作者据此设计一个诊断-干预-验证的闭环——先用两类合成数据集（RP、LP）作为可控实验台[7]，在 Llama 3 架构上系统地引入三项干预（r2、bidirectional、corrective），最后用 Procrustes 探针验证学到的算法痕迹。直觉上：r2 抑制了用图深度预测 provability 的统计捷径；双向掩码让所有 token 互相可见从而消除顺序偏置；corrective objective 把 CoT 答案作为监督信号，让直接预测头共享 CoT 的推理基元。

与已有方法（多任务混合课程、外部 CoT 提示、强化学习）的本质区别是单序列对齐：传统多任务训练 $D_{mixed} = \{(x, \tau_{direct}, y_{direct})\} \cup \{(x, \tau_{cot}, y_{cot})\}$[39,40] 会因梯度冲突[69]导致任务 token 嵌入坍缩。本文提出 $(x, \tau_{direct}, y_{direct}, \tau_{cot}, y_{cot})$ 单一序列格式，用隔离式注意力掩码[41]让两分支只能看问题陈述而互不交叉，从结构上避免信息泄漏与嵌入坍缩。这与[40,68]中观察到的混合课程退化形成对比，论文证明通过几何隔离可以让两种推理模式共享同一组推理基元。

方法步骤详情

第一步数据集：RP 采样事实/规则/查询并用 forward-chaining 计算 $\delta$；LP 在有序层分配谓词真值后注入干扰，LP* 增加循环。训练 $N_{pred} \leq 30, \delta \leq 6$，平衡 50k/桶。第二步 r2 启发式：LP 用 prune-and-add 删关键规则+加传递性干扰；RP 用贪心迭代修改最大化剩余图深度，目标 $\phi(C_1) \approx \phi(C_2)$ 标签相反。第三步架构：Llama 3 解码器 $L=8, d_{model}=256$，类型嵌入解耦逻辑角色与 token 身份，归一化加权重衰减。第四步 corrective 单序列：$(x, \tau_{direct}, y_{direct}, \tau_{cot}, y_{cot})$ 串成一条，cross-entropy 监督两分支，问题陈述对两分支可见但分支互不可见。第五步评估：$N_{pred} \leq 60, \delta \leq 12$ OOD 上 $2^4$ 消融，Procrustes 探针追踪 provability。

技术新颖性

技术新颖性体现在三处：第一，把演绎推理的理论下界（$\Omega(\log\delta)$ 与 $\Omega(\delta)$）和信息瓶颈（$m = \Omega(s\log(n/s))$）首次联合用于分析 Transformer 的可学习性，并对应到具体的层数 $L$ 和头维度 $d_{head}$ 维度，这是此前[50,51,24,54]等理论工作未明确建立的。第二，r2 启发式不同于[32,33]的反事实增强——后者用信息瓶颈视角，本文则把对抗平衡解释为与标准正则化竞争的张量范数约束，即线性分离近冲突对需要大 $\|w\|$ 从而与权重衰减冲突。第三，Procrustes 探针结合[44]的发现：在非因果解码器中线性可分信息跨层保持拓扑一致，可作为新工具追踪内部算法演化，这扩展了[42,43]的探针方法论。

**Figure 1**: Proof depth δ on RP and LP problems

**Figure 3**: Rule synthesis on the LP backbone

实验结果

核心发现在 Table 2（LP 上 $2^4=16$ 配置均值）：直接预测中 corrective 最有效，$N_{pred}\leq 30, \delta\leq 6$ 提升 $18.9 \pm 8.4$ pp，$6<\delta\leq 12$ 仍贡献 $5.3 \pm 4.6$；bidirectional mask 贡献 $8.4 \pm 7.1$；r2 配 corrective 贡献 $7.1 \pm 3.0$，无 corrective 时伤害直接预测（$-0.6 \pm 7.8$）；FFN 贡献 $-2.4 \pm 5.7$。CoT 模式下组件边际显著缩小（corrective $-0.8 \pm 6.3$），CoT 已绕过大部分 shortcut。Table 3 显示 Universal Transformer（权重共享 × 8 迭代）配 FFN 在 LP 上比 baseline 高 $6.8 \pm 3.5$。Fig.6 显示 $L$ 从 8 扩到 128 在 $\delta\leq 6$ 内闭合隐式-显式差距$p<0.05$，$\delta>6$ 仍需 CoT。

**Table 1**: Pearson correlation between features and the ground-truth label on RP dataset

**Table 2**: Marginal contribution of components on LP

**Table 3**: Universal and baseline direct performance on δ≤6 problems

**Figure 5**: Evaluation across topologies on logical depth δ=5

**Figure 6**: Increasing model depth closes the implicit-explicit gap within the training horizon on LP

**Figure 7**: Probing provability on LP reveals traces of forward-chaining

查看结构化数据

任务	指标	本文	基线	提升
LP δ≤6 直接预测 marginal gain (corrective)	百分点（%）	18.9 ± 8.4	无 corrective baseline	+18.9 pp
LP δ≤6 直接预测 marginal gain (bidirectional)	百分点（%）	8.4 ± 7.1	无 bidirectional baseline	+8.4 pp
LP δ≤6 直接预测 marginal gain (r2 + corrective)	百分点（%）	7.1 ± 3.0	无 r2 但有 corrective	+7.1 pp
LP N_pred≤30 Universal Transformer vs baseline (with ffn)	百分点（%）	+6.8 ± 3.5	standard Transformer (8 layers) with ffn	+6.8 pp
depth scaling on LP N_pred≤30 for closing implicit-explicit gap	accuracy gap (pp) at δ≤6	0 (L=128)	gap at L=8	gap closed within training horizon (p<0.05 sustained non-inferiority)

局限与改进

作者承认的局限：(1) 完整 corrective 收益要求 $L \geq \delta$，浅模型上边际贡献不显著；(2) r2 启发式实施困难，仅能削弱一阶相关性，高阶结构特征仍可能被利用且使收敛更难；(3) 双向掩码难推广到多轮对话；(4) 即便堆深度闭合训练 horizon 内差距，CoT 在 $\delta>6$ 深度外推上仍不可替代；(5) 仅在玩具规模合成 Horn 子句任务验证（$N_{pred}\leq 60$），向自然语言外推需谨慎。我额外观察到：Table 2 CoT 模式标准差大于均值（cot w. ffn $0.7 \pm 3.9$），结果对超参敏感，论文未充分分析稳定性；Table 1 r2-augmented 数据的 num_rules 相关系数从 $0.277$ 翻转到 $-0.247$，可能引入新偏置。

独立分析的弱点

独立分析的弱点有四：第一，r2 设计脆弱——依赖对单一规则的剪枝/添加构造近冲突对，但 RP 高冗余图单规则删除常无法打破证明，需要迭代修改又会破坏 $\phi(C_1) \approx \phi(C_2)$ 的统计保证；改进方向是用 GNN 评估图编辑距离升级 r2。第二，corrective 依赖训练 horizon——$L \geq \delta$ 是必要条件但未给出自适应方案；改进方向是引入早退机制或深度预测 token。第三，评估范围过窄——仅在 RP/LP 评测，应扩展到 CLUTRR、RuleTaker、ProofWriter 等自然语言演绎基准。第四，理论下界与实证解耦——$m = \Omega(s\log(n/s))$ 是信息论下界，论文未证明实际学习算法是否达到；应做 probing 实验测量有效 active feature 数 $s$ 并对比下界。

未来方向

作者明确指出的方向有四：(1) 把当前理论框架扩展到 CoT 提示词长度的形式化极限；(2) 寻找能更好促进逐步推理学习的优化偏置（如 RL 中的过程奖励）；(3) 细粒度刻画构成推理步骤的原语（rule synthesis、fact retrieval、derivation 等的更小单元）；(4) 推广到一阶逻辑、自动定理证明或自然语言推理，以及具有无界状态或循环的架构（如状态空间模型 Mamba、循环 Transformer）。基于结果可延伸的方向还包括：把 r2 启发式与对抗训练/RLHF 结合形成在线虚假特征检测；用 Procrustes 探针作为模型选型工具挑选哪些层最适合知识编辑；把 corrective objective 与多任务指令调优结合，让单一模型同时具备隐式快路径和显式慢路径两种推理模式。

复现评估

复现评估：作者明确给出了完整超参数（Llama 3 base, $L=8, d_{model}=256$）、数据集规模（50k/桶训练、500/桶评估、$N_{pred}\leq 30$ 训练/$N_{pred}\leq 60$ 评估、$\delta\leq 6$ 训练/$\delta\leq 12$ 评估）、注意力头数 $H=4$、Universal Transformer 迭代 $K=8$。数据集生成器直接沿用[7]的 RP/LP/LP*，规则前提数 1–3，可对照复现。但完整实验需要：数百次 $2^4$ 因素消融跑 16 个配置 + 多层深度扫描（L=8,16,32,64,128）+ Universal Transformer 对比 + Procrustes 探针的数百个 checkpoint 评估。算力门槛对单卡研究者偏高（即便 $d_{model}=256$，8 层模型仍可单卡训练，但 L=128 实验需要数十张 GPU/TPU 小时）。开源情况：论文未明确给出代码仓库 URL，仅在附录列出超参——是中等偏低的复现难度，建议先复现 L=8 的 $2^4$ 消融再扩展深度。

Transformer 中隐式演绎推理的扩展性研究 The Scaling Properties of Implicit Deductive Reasoning in Transformers