🤖 machine learning

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

This paper demonstrates that while models can effectively learn to verify and memorize solutions for reasoning tasks, they fundamentally fail to learn verifiable search procedures as forward chain-of-thought derivations, regardless of model scale or training method, because such tasks lack a faithful, information-preserving step-by-step path to imitate.

Original authors: Harsh Patel

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Harsh Patel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a very smart but literal-minded apprentice how to solve a complex puzzle. You have a perfect master solver who can crack the puzzle every time. Your plan is simple: write down the master's step-by-step thinking process (the "Chain of Thought") in a notebook, show it to the apprentice, and expect them to learn the logic and solve it themselves.

This paper argues that this plan works for some puzzles, but fails spectacularly for others, and the reason isn't that the apprentice is "dumb." It's because of how the puzzle is solved.

Here is the breakdown of the paper's findings using simple analogies:

1. The Two Types of Puzzles

The researcher tested the apprentice on nine different types of logic puzzles. They fell into two distinct groups:

The "Straight-Line" Puzzles (The Easy Ones):
Think of these like following a recipe. "Mix flour, add eggs, bake for 20 minutes." The steps happen in a straight line from start to finish. If you write these steps down and teach them to the apprentice, they learn perfectly. The paper found that for tasks like Roman numerals or simple math conversions, the apprentice could copy the master's steps and get the answer right 99% of the time.
- The Lesson: If the solution is a direct path, you can teach it by showing the path.
The "Backtracking" Puzzles (The Hard Ones):
Think of these like navigating a massive, dark maze where you have to guess which door is the right one. If you hit a dead end, you have to go all the way back to the start and try a different door. The master solver does this by trying a door, realizing it's wrong, erasing that thought, and trying another.
- The Problem: You cannot write down a "straight-line" story of this process. A story that says "I tried Door A, it failed, I tried Door B, it failed..." is actually a lie if the apprentice doesn't actually have the ability to go back and erase their previous thoughts in real-time.

2. The "Verdict-as-Token" Trap

The paper discovered a specific failure mode with the "Backtracking" puzzles (specifically a type called Cryptarithm, where you have to figure out which letter stands for which number).

When the researcher taught the apprentice the master's "search" process, the apprentice didn't learn the logic of searching. Instead, it learned the shape of the answer.

The Analogy: Imagine the master says, "I checked the red door, it was wrong, so I eliminated it." The apprentice memorizes the phrase "Eliminate red door" but doesn't actually understand why it was wrong.
The Result: When the apprentice tries to solve a new puzzle on its own, it sees a red door and blindly says, "Eliminate red door," even if the red door was actually the correct one. It is reciting a script without understanding the story. The paper calls this "Verdict-as-Token": the model treats the conclusion as a fixed word to be spoken, rather than a decision based on evidence.

3. Why Bigger Brains Didn't Help

The researcher tried this on many different models, from small ones to massive, super-smart ones (up to 671 billion parameters).

The Finding: Even the giant models failed at the "Backtracking" puzzles when asked to show their work step-by-step. They all hit the same low ceiling (around 5% accuracy).
The Reason: The problem wasn't the size of the brain; it was the type of thinking required. You cannot force a model to "remember what it tried and go back" if its internal architecture isn't designed to hold that kind of "search state" while it writes a story.

4. The "Magic Key" Experiment

To prove that the problem was the search and not the math, the researcher did a clever trick. They gave the apprentice a "cheat sheet" (the cipher key) that turned the maze into a straight line.

The Result: As soon as the search was removed and the task became a straight-line calculation, the apprentice's accuracy jumped from 3% to 57%.
The Conclusion: The model could do the math and logic perfectly fine. It just couldn't perform the "search" part while writing the story.

5. The Real Solution: Memorization, Not Reasoning

So, how did the winner of the competition solve the hard puzzles? They didn't teach the model to search.

The Strategy: They realized the maze had a finite number of possible paths. Instead of teaching the model to walk the maze, they had the model memorize a map of every possible maze layout.
The Analogy: Instead of teaching the apprentice how to navigate a maze, you give them a book that says, "If the maze looks like this, the answer is that." The model memorized this book (a catalog of solutions) and then just had to do a quick check to make sure the answer fit.
The Takeaway: The paper concludes that for these hard search problems, memorization works, but distilling the search process does not.

Summary

The paper's main message is: You cannot teach a model to "search" by just showing it the search steps.

If the task is a straight line, showing the steps works.
If the task requires backtracking (trying, failing, and retrying), the model will just memorize the words of the failure, not the logic.
To solve these hard tasks, you must either teach the model to run the search itself (which is hard) or pre-compute the answers and teach the model to memorize the catalog of possibilities.

The paper is a warning to AI researchers: Just because a computer program can solve a problem doesn't mean a language model can learn to "think" its way to that solution just by reading the program's notes. Sometimes, the only way to learn is to memorize the map, not the journey.

Technical Summary: A Verifiable Search Is Not a Learnable Chain-of-Thought

Problem Statement

The paper investigates a central hypothesis in the distillation of reasoning: if a task can be solved by a short, deterministic program, can that program's logic be taught to a smaller language model as a verifiable Chain-of-Thought (CoT)? The intuition suggests that writing out a solver's steps in natural language and fine-tuning a model on them should enable the model to reproduce the reasoning.

The author challenges this intuition using a controlled benchmark of nine reasoning tasks. The benchmark possesses a unique property: the hidden test set is generated by the same deterministic generators as the public training set. This ensures that a held-out slice of the training data is a faithful proxy for test accuracy, allowing the author to measure the "learnability gap" between a perfect symbolic solver and a fine-tuned model without access to external test labels.

The core question is whether the coverage of a verifiable solver predicts the accuracy of a model attempting to learn the procedure via CoT. The study focuses specifically on tasks where the solution requires search (e.g., backtracking) versus tasks that are forward-computable (e.g., arithmetic, lookup).

Methodology

The research employs a rigorous, instrumented pipeline to isolate learnability from data noise or architectural limitations:

Benchmark Construction: Nine task categories were defined, including Roman numerals, unit conversion, free-fall physics, monoalphabetic substitution ciphers, 8-bit boolean rule induction, equation induction, and two families of cryptarithms (deduce and guess).
Solver Reverse-Engineering: The author reverse-engineered the deterministic generators into Python solvers. Five tasks yielded solvers with $\ge$ 98% accuracy. The cryptarithm task was solved via a backtracking search solver achieving ~71% accuracy (the remainder being information-theoretically ambiguous).
Synthetic CoT Generation: Solvers were instrumented to narrate their own steps in the base model's native ASCII style. A critical discipline was enforced: every "verdict" (e.g., "drop this candidate") had to be witnessed, meaning the evidence forcing the decision had to be explicitly restated on the same line.
Training Regime:
- Base Model: Nemotron-3-Nano-30B-A3B (a hybrid Mamba-2/Mixture-of-Experts model).
- Adapter: Rank- $\le$ 32 LoRA adapters trained via Supervised Fine-Tuning (SFT) on synthetic CoT.
- Escalations: When SFT plateaued, the author applied Reinforcement Learning from Verifiable Rewards (RLVR/GRPO) and Self-Taught Reasoner (STaR) training, harvesting the model's own successful rollouts.
Evaluation: Models were evaluated on held-out real training rows (acting as the test set) under greedy decoding. The study also included an architecture control (testing dense and MoE Transformers from 3B to 671B) and a causal intervention (revealing parts of the cipher key to test forward-derivability).

Key Contributions and Findings

1. The Solvability–Learnability Gap

The paper quantifies a stark divergence between solver accuracy and model accuracy.

Forward-Computable Tasks: For tasks like Roman numerals, unit conversion, and simple ciphers, the solver's coverage (near 100%) directly translates to model accuracy ( $\ge$ 0.99).
Search Tasks: For cryptarithm, the solver achieves ~71% accuracy, but the fine-tuned model caps at 0.01–0.07, regardless of training method (SFT, RLVR, STaR) or CoT design (11 different designs tested).
Bit Manipulation: This task sits in the middle. The solver reaches 98.9%, but the model reaches only 0.678. The gap is closed partially by STaR, which allows the model to imitate its own successful searches, suggesting the model can learn search if it can execute the search itself within the context window.

2. The Failure Mechanism: "Verdict-as-Token"

The paper identifies a specific failure mode in search tasks called "verdict-as-token."

Observation: In cryptarithm traces, the model performs arithmetic correctly on 97–100% of lines. However, the verdict (the conclusion that a candidate is invalid) is often decoupled from the evidence on that line.
Mechanism: Under teacher forcing, the model learns to emit a fixed phrase (e.g., "none matches $\to$ drop") because it always appears in a correct context during training. At inference (free-running), this phrase fires unconditionally, even when the arithmetic on the line contradicts it.
Evidence: A per-line fidelity audit showed that while arithmetic correctness was near-perfect, the logical fidelity of the verdict (does the conclusion follow from the numbers?) was only 16–57%.

3. Architecture Independence and Forward-Derivability

The failure is not specific to the hybrid Mamba-2/MoE architecture.

Architecture Control: Training the same cryptarithm corpus on dense Transformers (Llama-3.2-3B, Qwen3.5-4B) and MoE Transformers (gpt-oss-20b) resulted in the same $\le$ 0.04 accuracy floor.
Causal Intervention: Revealing the full cipher key (turning the task from search to forward lookup) lifted the model's accuracy from 0.03 to 0.571. Revealing only half the key barely helped.
Conclusion: The binding constraint is forward-derivability. A task whose only honest solution is backtracking search over information-free structure admits no faithful forward CoT. Without a forward trace to imitate, SFT learns only the surface shape of the search, not its logic.

4. The Escape: Memorization, Not Search

The paper demonstrates that the task is learnable, but not by distilling the search process.

The 1st-Place Solution: The competition winner (Private LB 0.92) did not teach the model to search. Instead, they precomputed the combinatorial core of the search (a catalog of 4,205 candidate signatures for cryptarithm) and memorized it. The model's CoT then reduced to recall (looking up the catalog) plus bounded verification.
Implication: What distills is memorization and verification, not the search itself. A verifiable search is learnable as a CoT only if its candidate structure can be compressed into a finite catalog small enough to memorize.

Significance and Claims

The paper's primary contribution is a negative result with convergent evidence: a verifiable search is not a learnable chain-of-thought.

Refutation of Intuition: The assumption that "any solvable task is learnable via CoT" fails for procedures requiring backtracking over information-free structures.
Mechanism Identification: The paper isolates "verdict-as-token" as the specific failure mode where SFT decouples the form of a reasoning step from its logical content, leading to unfaithful traces that collapse at inference.
Predictive Heuristic: The author proposes a pre-training test for learnability: Does a purely forward closure (no backtracking) cover a meaningful fraction of instances? If not, the task will likely resist CoT distillation.
Distinction: The paper distinguishes between solvability (an answer exists) and learnability (a model can reason its way to it). Solver coverage predicts model accuracy only when the solver is a forward map; for search procedures, it predicts almost nothing.

The author explicitly states that the contribution is not a new model capability or a competition ranking (their best score was 0.85, median of the field), but a "clean, instrumented account of where and why a verifiable search fails to become model reasoning." The findings suggest that for complex search tasks, the path to high performance lies in reformulating the task to separate memorization from computation, rather than attempting to distill the search process itself.