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

This paper presents a critical analysis of the limitations of teaching models to perform reasoning tasks through chain-of-thought methods, demonstrating that certain tasks, particularly those requiring backtracking search, cannot be effectively learned this way. The authors utilize a 30B parameter Nemotron model and show that while forward-computable tasks can be successfully distilled into a fine-tuned model, tasks like cryptarithms fail to achieve similar performance due to their inherent reliance on search processes. This work highlights the necessity of rethinking how certain complex reasoning tasks are approached in AI, suggesting that effective solutions may require precomputing combinatorial structures rather than relying solely on chain-of-thought learning.