可验证搜索不是可学习的思维链

证明搜索过程无法通过监督学习蒸馏为思维链，根本原因是缺乏可靠的向前推导路径。

前置知识

思维链（Chain-of-Thought）

一种让大语言模型逐步推理的方法，要求模型显式输出中间推理步骤，而不仅仅是最终答案。核心思想是通过分步骤的显式推理来提高多步骤任务的准确性，每个推理步骤都应该是可验证的逻辑推演。在蒸馏场景中，老师模型通常是符号求解器生成正确的推理步骤，学生模型通过监督学习模仿这些步骤。

本文核心研究对象是能否将程序化推理过程蒸馏为模型的思维链，理解思维链的可学习性边界对于构建可靠的AI推理系统至关重要。

监督微调（Supervised Fine-Tuning, SFT）

一种模型训练范式，使用标注数据集通过最大化似然估计来调整模型参数。给定输入序列x和目标输出序列y，通过最小化交叉熵损失来学习条件分布。在teacher forcing模式下，每个时间步的真实标签作为下一时刻的输入，这与自由生成时的分布可能不同，导致exposure bias问题。

本文所有实验都基于SFT，论文的核心发现'Verdict-as-Token'机制正是SFT在teacher forcing下的产物，理解这一机制对于解读负结果至关重要。

回溯搜索（Backtracking Search）

一种系统化的搜索算法，通过递归地尝试候选解决方案并在检测到冲突时回退到上一个决策点来寻找解。典型框架包括：选择未赋值变量、尝试候选值、检查约束满足、如果冲突则回退。时间复杂度在最坏情况下是指数级的O(b^d)，其中b是分支因子，d是搜索深度。空间复杂度为O(d)用于存储递归调用栈。

Cryptarithm任务只能通过回溯搜索解决，而论文证明了这种搜索过程无法蒸馏为向前思维的CoT，这是全文负结果的根源。

LoRA适配器（Low-Rank Adaptation）

一种高效的参数微调方法，通过在预训练模型的权重矩阵上添加低秩分解矩阵来实现适配。给定原始权重矩阵，LoRA添加增量，其中B和A是低秩矩阵且秩r远小于原始维度。训练时冻结原始权重，只更新A和B，参数量大幅减少。本文使用rank≤32的LoRA，在30B模型上只有约880M可训练参数（2.71%）。

本文所有微调实验都使用LoRA，理解其约束（低秩更新、有限的训练参数）有助于评估实验结果的可信度和普适性。

研究动机

当前AI研究存在一个广泛但未经验证的假设：如果一个任务可以用短程序解决，那么就可以将该程序作为思维链教给模型。这个假设支撑了大量关于推理蒸馏的工作，从rationale distillation到bootstrapped self-training和从可验证奖励的强化学习。然而，本文发现这个假设对一类可识别的过程失效。在一个包含9个推理任务的基准测试中，作者将确定性生成器逆向工程为Python求解器，其中5个任务达到98%以上准确率，但对于Cryptarithm任务，即使存在达到71%准确率的回溯搜索求解器，经过11轮不同CoT设计、RL从可验证奖励和self-training后，模型准确率仍停留在1-7%。

本文的目标是本文的核心目标是系统性地回答三个研究问题：第一，可验证求解器的覆盖率是否预测其过程是否可作为小模型思维链学习？第二，当过程对每一种尝试的训练方法都产生抵抗时，约束瓶颈是什么？第三，是否存在训练前的廉价测试可以预测这种抵抗？作者希望通过受控实验来建立求解器可解性与模型可学习性之间的定量关系，并识别出搜索过程无法蒸馏为向前思维链的根本原因。

与已有工作不同的是，本文的独特切入点在于：不同于以往工作关注算法长度泛化或组合性的一般限制，本文聚焦于搜索蒸馏这一特定场景下的失败机制。通过设计一个训练集等同于测试集的确定性生成器基准（训练和测试数据来自同一分布），作者可以精确测量过程是否转移，而无需访问测试标签。这种设计使得能够将求解器准确率与模型实际在CoT中重现的准确率进行精确对比，从而量化了可解性-可学习性差距。

核心方法

本文采用逆向工程到合成CoT生成到监督微调到受控评估的实验流程。对于9个任务类别，作者首先将确定性生成器逆向工程为Python求解器并在9500个训练行上验证；然后用求解器对新生成的随机实例生成合成CoT，通过工具化求解器以基础模型的原生ASCII风格叙述每一步，最后以boxed字段结束；接着在Nemotron-3-Nano-30B-A3B混合Mamba-2和Mixture-of-Experts模型上训练rank不超过32的LoRA适配器；最后在真实训练行的保留切片上评估适配器。整个实验流程强调一个CoT纪律：trace必须展示搜索（尝试、拒绝、匹配）且绝不能跳跃到未在页面上推导的答案。

核心创新点是建立了向前可推导性作为搜索可学习性的因果杠杆。当任务可以通过向前推导（从左到右的计算）解决时，SFT可以成功蒸馏；但当任务的唯一诚实解决方案是回溯搜索时，不存在可靠的向前CoT可供模仿，SFT只能学习其表面形式即Verdict-as-Token，导致推理时崩溃。论文通过因果干预实验（revealing cipher key将准确率从0.03提升到0.571）证实了向前可推导性的因果作用，排除了架构限制、预算限制、数据噪声等替代解释。

方法步骤详情

实验步骤包括：第一，逆向工程生成器为求解器并验证覆盖率；第二，用求解器对新鲜随机实例生成合成CoT，确保零泄漏；第三，设计CoT渲染器，强制每个判决必须在同一行重述迫使其成立的证据；第四，在rank不超过32 LoRA上进行SFT训练，使用2e-4学习率；第五，当SFT平台化时，升级到RLVR或GRPO和STaR；第六，在真实训练行保留集上评估，由于train等同于test性质，这直接预测测试准确率；第七，对于失败任务，进行五个独立测量（求解器上限、信息下限、基础行为、向前推导覆盖率、逐行保真度）来约束可实现准确率；第八，通过架构控制实验验证结论的泛化性；第九，通过因果干预实验验证向前可推导性的因果作用。

技术新颖性

技术新颖性体现在三个方面：第一，建立了定量化的可解性-可学习性差距测量框架，精确量化了求解器准确率与模型实际重现准确率之间的差距（对于cryptarithm超过0.65）；第二，识别并命名了Verdict-as-Token机制作为搜索蒸馏失败的标志，即在teacher forcing下模型学会了判决步骤的表面形式但与证据解耦，导致推理时无条件发射；第三，通过五个独立测量（求解器覆盖率、信息下限、基础行为、向前推导覆盖率、判决保真度）实现了对搜索可学习性的收敛约束，所有测量指向同一结论。

**Figure 3**: Bit-manipulation: only the model's own search transfers

实验结果

核心发现分为正反两面。正向发现：对于四个查找或拟合任务（numeral、unit_conversion、gravity、cipher），一旦CoT正确且ASCII-clean，模型可重现求解器到99%以上准确率；对于bit_manipulation任务，使用STaR在模型自身成功的搜索上训练，准确率从0.526提升到0.678，预算截断从18.6%降至0.2%。负向发现：对于cryptarithm-deduce任务，即使存在71%准确率的回溯搜索求解器，经过11轮连续CoT设计（从解码优先验证到显式终止追踪）、RLVR或GRPO和STaR，模型准确率始终停留在0.01到0.07区间。五个独立测量高度一致：求解器上限457除以659等于0.693；信息下限互信息为0.021 nats约等于shuffle；基础行为0除以50正确；向前推导覆盖率1除以659；判决保真度16到57%。架构控制实验显示，相同的cryptarithm语料库在四种不同架构上训练都达到相同的0.04以下下限，跨越3B到671B参数规模和SFT到in-context设置。

**Table 1**: The benchmark, and the central gap

**Table 3**: Five independent bounds on cryptarithm-deduce

**Table 7**: Forward-derivability is causal

**Table 6**: The search does not distill, on any backbone

查看结构化数据

任务	指标	本文	基线	提升
Cryptarithm-deduce cryptarithm任务操作符在示例中见过	准确率	0.01-0.07 11轮CoT设计	回溯搜索求解器 0.71	负结果无法提升
Bit-manipulation 位操作任务	准确率	0.678 STaR后	单规则搜索求解器 0.989	相比基线降低31%但相比手动CoT的0.053大幅提升
Cipher 替换密码任务	准确率	约0.99	求解器 1.00	几乎完美转移
Cryptarithm revealing full cipher key	准确率	0.571 Nemotron n等于42	原任务 0.03	约15倍提升验证向前可推导性的因果作用

局限与改进

作者承认的局限性包括：研究深度聚焦于一个基准而非广度；每个训练单元格只使用单个随机种子（虽然二项CI约束采样噪声但不约束种子方差）；在贪婪解码下评估（虽然评分器要求这样做，但基于采样的测试时搜索会改变可达数字）；没有赢得竞赛（最佳公共0.852、私有0.860 vs 第一名0.92）；未运行前沿模型长时间微调。我观察到的局限性包括：实验只考虑了rank不超过32的LoRA，更大rank或全参数微调是否能突破上限未探索；STaR在bit_manipulation上有效但在cryptarithm上失败，两者的本质区别需要更深入分析；论文提出的向前可推导性预测试只在这一基准上后验验证，前瞻性验证仍在进行中；对于更复杂的搜索任务如AlphaGo式的蒙特卡洛树搜索，结论是否成立有待验证。

独立分析的弱点

论文的几个关键弱点为未来研究指明方向。第一，实验设置中LoRA rank不超过32可能过于保守，更大rank或全参数微调是否能安装更深的搜索记忆需要验证。第二，STaR在bit_manipulation上有效但在cryptarithm上失败，两者的本质区别在于bit_manipulation的搜索空间是有界的（1577除以1602训练行可由六函数基础解释），而cryptarithm的搜索空间无界，未来工作应该探索如何将有界搜索与无界搜索的可学习性边界形式化。第三，论文提出的向前可推导性预测试需要更广泛的前瞻性验证，特别是对于不同类型的搜索任务（如规划、推理图构建）。第四，实验只考虑了向前推导，没有探索其他CoT编码方式（如从后向前、双向、分层）是否可能编码搜索过程。

未来方向

作者提出的未来方向包括：向前可推导性的前瞻性测试；更广泛的基准验证；探索更大rank或全参数微调的影响；研究不同CoT编码方式对搜索可学习性的影响；探索更复杂的搜索任务（如蒙特卡洛树搜索）的可学习性边界。基于论文成果，可延伸的方向包括：形式化向前可推导性边界条件的理论框架；开发自动检测向前可推导性的工具；探索向前可推导性与任务结构（如约束类型、搜索空间形状）的关系；研究是否可以通过架构创新（如显式搜索状态记忆模块）来突破向前可推导性限制；探索搜索蒸馏与记忆化之间的最优权衡（第一名解决方案的0.92证明了记忆化-计算分离的有效性）。

复现评估

论文的复现性评估：代码、论文源码、架构控制脚本和每行评估数据已开源在github.com/harshpatel1692/search-not-learnable；交互式演示在nemotron.harshpatel.live；发布内容包括：每个类别的逆向工程求解器和合成CoT渲染器；保留评估框架；支撑图表的每行评估CSV；逐行保真度审计7566条记录。基准数据本身属于竞赛，可从Kaggle获取而不在此重新分发。最终适配器在单个RTX PRO 6000 Blackwell 96GB上训练；迭代使用托管LoRA服务，约3.5美元每轮；训练配置详细记录（LoRA rank 32除以32除以0.0，学习率2e-4，有效批大小32，2个epoch，8192序列长度，bf16精度）。论文中所有数字都来自有日期的实验日志；只引用有报告支持的数字；对于只在运行日志中存在但不可重新运行的数字，作者明确标记。复现难度：中等，主要挑战在于算力需求（96GB GPU）和训练稳定性（需要配置PTXAS shim和离线Mamba和causal-conv1d内核）。

可验证搜索不是可学习的思维链 A Verifiable Search Is Not a Learnable Chain-of-Thought