A Verifiable Search Is Not a Learnable Chain-of-Thought

摘要

It is tempting to assume that any task one can solve with a short program can be taught to a model as its chain-of-thought: write the program’s steps out in words, fine-tune on them, and the model should follow. This paper shows the assumption fails for an identifiable class of procedures, and that the reflexive remedies do not rescue it. The testbed is nine reasoning tasks, each emitted by a deterministic generator, with one convenient property: the public and hidden splits are drawn from the same generators, so a held-out slice of training data is a faithful proxy for test accuracy. I reverse-engineer the generators into Python solvers (five reach $\geq\!98\%$ ), render their procedures as chain-of-thought, and distill them into a rank- $\leq\!32$ LoRA over a 30B (3.5B-active) Nemotron model. Forward-computable tasks install readily: four lookup/arithmetic tasks and an 8-bit boolean-rule task transfer ( $\geq\!0.99$ and $0.68$ ). Cryptarithm does not, when one tries to distill its backtracking search: it 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 its instances. The failure is not a capability gap. The model does the arithmetic correctly on $97$ – $100\%$ of lines and ranks the correct cipher into its top eight on $71\%$ of instances. What it cannot do is carry the search forward as a left-to-right derivation. Supervised fine-tuning therefore learns the shape of a verifiable elimination step while its verdicts become unconditional templates, correct only $16$ – $57\%$ of the time (“verdict-as-token”). This search-distillation ceiling holds across four backbones from 3B to 671B and across both fine-tuning and in-context prompting, and 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$ . The constraint binds the search, not the task: when a procedure’s only solution is search over information-free structure, no faithful forward chain-of-thought exists to imitate. The task nonetheless becomes learnable by removing the search from the trace, precomputing its combinatorial core into a finite catalog the model memorizes and reducing the chain-of-thought to recall plus bounded verification; the competition’s 1st-place solution is the existence proof, reaching Private LB $0.92$ by memorizing a per-signature candidate catalog rather than teaching the model to search [8]. What distills is memorization and verification, not search. I release the benchmark decomposition, the solvers, the per-line fidelity audits, and the control experiments.