可验证的搜索并非一种可学习的思维过程
A Verifiable Search Is Not a Learnable Chain-of-Thought
摘要
人们很容易认为，那些可以通过简短程序解决的任务，都可以被转化为“思维过程”来训练模型——即把操作步骤写下来，然后对模型进行微调，模型就能按照这些步骤进行推理。不过本文表明，对于某些可识别的算法来说，这种假设并不成立。测试样本包括九种推理任务，每个任务都来自一个确定性生成器；公开和隐藏的版本共享同一个生成器，因此使用保留的数据来评估模型的准确性。我们将这些生成器转换为Python求解器，将其转化为“思维过程”形式，然后将其整合到30亿参数（其中3.5亿为活性参数）的Nemotron模型中，形成rank≤32的LoRA层。那些可以正向计算的任务则很容易实现：查找/算术运算以及8位布尔任务的成功率分别达到≥0.99和0.68。但密码计算则不然：在11种不同的“思维过程”设计、基于可验证奖励的强化学习以及自训练方式下，其回溯搜索的准确率仅为0.01-0.07；尽管有71%的实例可以被求解器解决，但模型仍然无法将搜索过程 weiter推进下去。这并非能力上的差距。该模型在97-100%的实例中能够完成算术运算，并且在71%的情况下能正确识别出正确的密码；但它无法以从左到右的方式继续搜索过程。微调过程则有助于学习出有效的消除步骤，而模型的判断结果则成为无条件的模板，只有16-57%的时间才是正确的（“判断作为令牌”）。无论是在3亿还是671亿参数的模型上，无论是通过微调还是提示式输入，这一准确率都保持不变；通过控制性的干预可以找出原因：揭示密码密钥后，就可以让模型以正向方式继续搜索，此时相同实例的准确率可从0.03提升到0.57。当某个算法的唯一解决方案就是对无信息结构进行搜索时，就不存在可以模仿的忠实于实际思维的“思维过程”。这样的任务只能通过去除搜索过程、将组合核心预先计算到数据库中，再减少不必要的步骤来实现学习；通过这种方式，第一名的解决方案的私有LB值可以达到0.92。所进行的处理主要是记忆和验证，而非搜索。
English Abstract
It is tempting to assume any task solvable by a short program can be taught to a model as its chain-of-thought: write the steps out, fine-tune, and the model follows. This paper shows the assumption fails for an identifiable class of procedures. The testbed is nine reasoning tasks, each from a deterministic generator; public and hidden splits share generators, so held-out data proxies test accuracy. I reverse-engineer the generators into Python solvers, render them as chain-of-thought, and distill into a rank-<= 32 LoRA over a 30B (3.5B-active) Nemotron model. Forward-computable tasks install readily: lookup/arithmetic and an 8-bit boolean task transfer (>= 0.99 and 0.68). Cryptarithm does not: distilling its backtracking search holds at 0.01-0.07 across eleven chain-of-thought designs, RL from verifiable rewards, and self-training, even though a search solver answers 71% of instances. This is not a capability gap. The model does the arithmetic on 97-100% of lines and ranks the correct cipher in its top eight on 71%; it cannot carry the search forward as a left-to-right derivation. Fine-tuning learns the shape of a verifiable elimination step while its verdicts become unconditional templates, correct only 16-57% of the time ("verdict-as-token"). The ceiling holds across backbones from 3B to 671B and across fine-tuning and prompting; a controlled intervention isolates the cause: revealing the cipher key, which turns the derivation forward, lifts the same instances from 0.03 to 0.57. When a procedure's only solution is search over information-free structure, no faithful forward chain-of-thought exists to imitate. The task becomes learnable only by removing the search, precomputing its combinatorial core into a catalog and reducing the trace to recall plus verification; the 1st-place solution reaches Private LB 0.92 this way. What distills is memorization and verification, not search.