Researchers demonstrate that language models cannot reliably learn certain types of algorithmic reasoning—specifically backtracking search procedures—through chain-of-thought fine-tuning, regardless of model size or training method. While models perform individual computational steps correctly, they fail to chain those steps into valid forward derivations when the task requires combinatorial search over unstructured information.
This research exposes a fundamental limitation in how large language models learn procedural reasoning. The experiment tests nine reasoning tasks across models ranging from 3B to 671B parameters, using cryptarithmetic (solving letter-substitution puzzles) as the primary failure case. Although a traditional solver achieves 71% accuracy and the model correctly executes individual arithmetic operations 97-100% of the time, distilled models plateau at 1-7% accuracy—revealing a capability that cannot be imitated through standard fine-tuning approaches.
The core finding distinguishes between verification and search. Models successfully memorize what correct elimination steps look like but generate "verdict-as-token" outputs—verdicts disconnected from actual derivations, correct only 16-57% of the time. When researchers intervene by revealing the solution cipher upfront, converting search into pure verification, accuracy jumps from 3% to 57% on identical instances. This demonstrates the problem is architectural rather than computational.
The implications span AI safety, interpretability, and practical model deployment. The research suggests models cannot faithfully learn procedures requiring exploration of combinatorial spaces without explicit structure. The winning competition solution bypassed search entirely by precomputing solutions into lookup tables—achieving 92% accuracy through pure recall and verification. For developers building reasoning systems, this indicates that some algorithmic tasks require fundamentally different approaches than chain-of-thought prompting. The findings also inform expectations around model scaling and reasoning capabilities, suggesting that increasing parameters alone won't overcome procedural bottlenecks inherent to unstructured search problems.
- →Language models fail to learn backtracking search procedures as chain-of-thought, even at 671B parameters, despite correctly performing individual computational steps.
- →Models memorize verification patterns while treating verdicts as unconditional tokens rather than deriving them logically from search steps.
- →Revealing solution structure converts unsolvable search tasks into solvable verification problems, jumping accuracy from 3% to 57% on identical instances.
- →Successful solutions precompute combinatorial search into catalogs, reducing the task to lookup and verification rather than true algorithmic learning.
- →This limitation likely applies broadly to any task whose only solution requires exploring information-free combinatorial structures without shortcuts.