PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Harsh Patel

arXiv:2606.21884v1cs.LGcs.AIcs.CL

TL;DR

The paper asks whether short, verifiable programs can be taught as faithful chain-of-thought. It reverse-engineers deterministic task generators and distills their solvers, finding that forward computation transfers while cryptarithm search does not.

  • Problem

    Whether a short program that solves every instance can be learned as chain-of-thought remains insufficiently established despite motivating reasoning distillation.

  • Method

    The paper reverse-engineers deterministic generators into symbolic solvers, renders their procedures as chain-of-thought, and distills them across nine reasoning tasks.

  • Results

    Cryptarithm’s solvability–learnability gap exceeds 0.65, with distilled chain-of-thought accuracy never exceeding 0.07 despite near-zero gaps on four tasks.

  • Takeaways & Limitations

    A verifiable search is not a learnable chain-of-thought: autoregressive models imitate forward computation, but search requiring carried state misfires during inference.

  • Takeaways & Limitations

    The deterministic-generator benchmark is a controlled proxy for procedural reasoning, so these findings should not be interpreted as claims about general model capability.

Abstract

from arXiv · show

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.

1 Introduction

The paper shows that a verifiable solver does not necessarily distill into a faithful chain-of-thought: forward-computable procedures transfer, but search over information-free structure does not. Cryptarithm exposes this gap across training methods and architectures, while revealing the hidden key or memorizing finite search structure restores performance.

  • Core finding: A solver’s coverage does not predict chain-of-thought learnability: the accuracy gap is near-zero for four tasks but exceeds 0.65 for cryptarithm.The benchmark contains nine deterministic-generator reasoning tasks, with hidden test data serving as a proxy for held-out accuracy.
  • Core finding: Cryptarithm-deduce never exceeds 0.07 across eleven chain-of-thought designs and three reinforcement-learning or self-training escalations.A backtracking solver answers approximately 71% of instances, showing that the failure is not simply task solvability.
  • Mechanism: Arithmetic is correct on 97–100% of lines, but elimination verdicts become unconditional templates with only 16–57% fidelity.This verdict-as-token pattern means fine-tuning reproduces the shape of search without carrying its instance-specific logic forward.
  • Mechanism: Ranking is not the bottleneck: the correct cipher appears in the top eight 71% of the time, whereas full forward derivation succeeds only 1/659 times.The evidence identifies forward-derivability, rather than ranking, as the binding constraint for faithful chain-of-thought.
  • Causal test: Revealing the cipher key lifts the same instances from 0.03 to 0.571, confirming that making the derivation forward is the causal intervention.Revealing only half the key barely helps, so a faithful trace must cover the whole derivation.
  • Practical escape: The competition’s first-place solution reaches Private LB 0.92 by memorizing finite candidate and rule-sequence catalogs, then verifying candidates in-trace.This reformulation removes the need to distill the combinatorial search itself.

2 Background and Related Work · 3 The Testbed: a Deterministic-Generator Benchmark

The paper tests whether perfect symbolic procedures can be distilled into faithful model chain-of-thought, using a deterministic-generator benchmark whose hidden test shares the training distribution. It situates the study among work on reasoning distillation, verifiability, chain-of-thought faithfulness, and transformer limits, while detailing a cryptarithm task requiring hidden-state search.

  • 2 Background and Related Work: The study asks whether a perfect symbolic solver’s procedure survives transfer into a smaller model’s chain-of-thought under a rank-≤32 adapter budget.This extends prior work on eliciting and distilling step-by-step reasoning by using a symbolic solver as the teacher.
  • 2 Background and Related Work: Self-training, RL from verifiable rewards, group-relative policy optimization, and process verification provide escalating methods for improving answers or intermediate reasoning.The paper reports that RLVR can improve easy curricula without moving held-out accuracy when positive rollouts on real instances are too rare.
  • 2 Background and Related Work: The paper frames its verdict-as-token result as a mechanistic example of unfaithful reasoning, alongside evidence that stated rationales can diverge from the computation producing answers.This connects the study to interventions that insert mistakes, truncate, or paraphrase traces without changing the answer.
  • 2 Background and Related Work: The negative result sharpens known limits involving compositional depth, algorithm-length generalization, memory constraints, and delayed emergence of algorithmic competence.The paper argues that state-space layers may interact poorly with explicit unbounded search-state, but treats this as at most a contributing factor rather than the cause of the search ceiling.
  • 3 The Testbed: a Deterministic-Generator Benchmark: 9,500 labeled training problems and ≈500 hidden-test problems are evaluated with a frozen base model plus a rank-at-most-32 LoRA adapter in deterministic greedy mode.The grader extracts the last boxed answer and applies task-specific exact matching or relative tolerance 10^-2 for floats.
  • 3 The Testbed: a Deterministic-Generator Benchmark: Because every category uses the same deterministic generator for training and hidden test, a stratified held-out slice of 100 rows per category serves as a faithful leaderboard oracle.The paper trains on synthetic chain-of-thought with different values to avoid leakage, then treats held-out training accuracy as test accuracy.
  • 3 The Testbed: a Deterministic-Generator Benchmark: The nine-generator benchmark spans straightforward numeral, unit-conversion, gravity, and cipher tasks, alongside bit manipulation, equation induction, and cryptarithm.Cryptarithm is designated the hard case, while cipher is among the “easy four”; the generators define the task distribution and test weights.
  • 3 The Testbed: a Deterministic-Generator Benchmark: Cryptarithm hides a per-row digit-to-symbol cipher, a wide-vocabulary operation, and endianness, requiring inference over multiple latent structural choices.Each instance has a five-character left-hand side and a per-row injective cipher drawn from 10 glyphs in a 23-symbol pool.

4 Method: Solver-Grounded Synthetic CoT and the Experiment Ladder

The study reverse-engineers each deterministic generator into a validated solver, renders leakage-free synthetic chain-of-thought, and evaluates LoRA adapters on held-out real-training rows. Its experiment ladder tests whether models reproduce forward derivations, revealing a sharp gap between search-solver accuracy and what left-to-right CoT can faithfully imitate.

  • Pipeline: Each category uses a validated solver, fresh generated instances, native-style synthetic CoT, LoRA SFT, and held-out real-training evaluation without leakage.Different values are used for synthetic traces and evaluation rows; train≡test makes the held-out evaluation the leaderboard.
  • Learnability frontier: 0.71 solver accuracy on cryptarithm contrasts with a ≈0.10 forward-derivable ceiling and 0.05 model accuracy, showing the model tracks imitability rather than search.For lookup/fit tasks, solver, forward-derivable ceiling, and model coincide; bit_manipulation is an exception with high forward derivation but a residual gap.
  • Rendering: Every verdict must restate the evidence forcing it; otherwise a fixed conclusion becomes a teleport that appears to reason but carries no transferable work.The enforced trace discipline is try → reject → match, rather than stating an underived answer.
  • Experiment ladder: When SFT plateaus, the ladder escalates to RLVR/GRPO and verifier-filtered STaR, promoting rounds only after a cheap held-out probe clears a preregistered threshold.Both escalation paths use the binary verify() reward or correct model rollouts folded back into SFT data.
  • Statistical reporting: Accuracies are reported as Wilson 95% confidence intervals with evaluation size n, using category-specific held-out slices and flagging when small samples make differences nonsignificant.The headline solver–model gaps are reported as significant despite the pass@k comparisons being affected by small n.

5 Results

Results show that forward-computable procedures transfer reliably, while search-based procedures do not: lookup tasks reach ≥0.99, bit manipulation reaches 0.678, and cryptarithm remains near 0.05 despite a ≈71% search-solver ceiling. The limiting failure is forward derivation, not arithmetic or hypothesis ranking, and the leaderboard solution instead removes search through catalog recall and verification.

  • Lookup/fit: ≥0.99 accuracy: the four lookup/fit tasks reproduce the solver once their chain-of-thought is correct and ASCII-clean.These results indicate that the pipeline, training budget, and grader are not the bottleneck.
  • Bit manipulation: 0.678 model accuracy: bit manipulation transfers partially, with misses concentrated in three-tap rules at 0.50 accuracy.The generator’s bounded search enumerates function bases and tap assignments, verifies all examples, and applies the resulting rule.
  • Bit manipulation: 0.526→0.656→0.678 accuracy: STaR improves bit-manipulation transfer while budget truncation falls from 18.6% to 0.2%.It trains on the model’s own verifier-passed rollouts, whose successful searches are executable rather than hand-written traces that conceal rule search.
  • Cryptarithm: ≈71% solver coverage versus ≈0.05 model accuracy: eleven cryptarithm chain-of-thought designs fail to teach faithful forward search.The fraction imitable by a faithful forward chain-of-thought is ≲10%, while the non-forward search solver could in principle reach ≈0.69.
  • Cryptarithm: 0.71 hit@8 versus 1/659 forward-closure coverage: the model can rank the correct cryptarithm map but cannot construct it left-to-right.A line-level audit finds arithmetic essentially perfect, while the dominant elimination line’s verdict is correct only 34.9% of the time.

6 Anatomy of the Failures

The failures are primarily decision and search-state failures rather than arithmetic or length failures. Bit-manipulation errors arise from hard rule selection, while cryptarithm traces decouple verdicts from evidence or lack carried search state; non-native trace openings can also make learned procedures unreachable.

  • Root causes: ≈96% of cryptarithm-deduce instances are wrong despite finishing within budget, while bit-manipulation truncates on 0% and is finished-but-wrong on 17%.The rendered cryptarithm search traces are a diagnostic exception, looping and truncating on 64–72% because the model does not maintain a tried-set.
  • Root causes: Zero transcription or arithmetic errors appeared in audits of 28 output bits and 7,566 cryptarithm lines; the failures were decisions about which rule or verdict.This identifies correctness, rather than length, as the relevant failure lever.
  • Bit-manipulation: 0.50 chance-corrected accuracy on three-tap bit-manipulation rules reflects hard rule selection, while one- and two-tap rules are largely solved.Observed mistakes included dropped shift anchors, unsupported run accept/reject decisions, and tie-breaking slips.
  • Cryptarithm: 69% of explicit cryptarithm search attempts re-enter an identical attempt, while forced termination teleports to a guess in 31% of cases, correct 1/31.Both behaviors reflect the absence of carried search state.
  • Native-voice attractor: 0% of greedy decodings entered non-native grammars despite 0.92–0.95 teacher-forced fidelity, creating fully learned but unreachable procedures.The model emits its native opener at the first token, with a 15–16 nat divergence; cryptarithm shares the native opener but drifts mid-trace.

7 Analysis: Why Some Procedures Resist Distillation

Cryptarithm search resists distillation because no faithful forward chain-of-thought exists for its information-free hidden structure. Across architectures and training regimes, models learn the surface form of verifiable steps and verdicts rather than carrying search state, while revealing the key makes the same task substantially learnable.

  • Task bottleneck: 97–100% arithmetic and 71% correct-map recognition show the model has cryptarithm’s primitives but cannot maintain assignments, propagate constraints, or prune dead branches.The bottleneck is task-intrinsic search execution, not missing arithmetic or mapping capabilities.
  • Architecture-general failure: 0.05 for DeepSeek-V3.1 and 0.00 for Nemotron-Super-120B extend the failure from 3B to 671B and from fine-tuning to in-context prompting.DeepSeek finishes incorrectly, whereas Nemotron truncates on 100% of sampled instances.
  • Verdict-as-token: Under teacher forcing, SFT learns verdict phrases such as “this candidate is impossible” as unconditional templates rather than functions of locally written evidence.The defect is hidden during training because each fixed phrase appears in a correct context.
  • Root cause: The hidden map is information-free, so backtracking is the only honest route; forward closure covers just 1/659 of instances, leaving no faithful forward trace to imitate.This creates the chain from absent forward reasoning to surface-form copying, verdict-as-token behavior, and free-running collapse.
  • Forward-derivability intervention: 0.03 without a key, 0.048 with half the key, and 0.571 with the full key show that making the derivation forward causes a ∼15× lift.The intervention used the same cryptarithm instances and fine-tuned Nemotron on n=42 examples.

8 Competition Dynamics and External Corroboration · 9 Memorization, not search

Competition results independently reproduce the paper’s ceiling: most teams plateaued near 0.85, while only one reached 0.92, consistent with cryptarithm search remaining largely unsolved. The winning approach instead succeeds by precomputing combinatorial structure into catalogs that the model memorizes and verifies.

  • 8.1 Leaderboard structure and external corroboration: 2,236 teams reached ≥0.85, but only 66 cleared 0.87, 7 cleared 0.88, and 2 reached ≥0.90; the single leader scored 0.92.A score of 0.85 was the median, matching the predicted frontier before cryptarithm is cracked.
  • 8.1 Leaderboard structure and external corroboration: 0.85 was also achieved independently by an open-source solution using reverse-engineered generators, solver-grounded synthetic chain-of-thought, and a rank-32 LoRA.Its recipe used one epoch, 8192-token context, and category-stratified batching.
  • 8.1 Leaderboard structure and external corroboration: 0.05 and 0.00 were the cryptarithm scores of prompted DeepSeek-V3.1 (671B) and Nemotron-Super-120B, respectively.Third-party reports also left several hundred of the hardest puzzles unsolved by frontier teacher models given the recovered rule.
  • 8.2 Threats to validity: Exact-width binary-string scoring and public/private overfitting made leaderboard selection hazardous, with operation choices able to raise public scores while lowering private scores.The public split’s few-hundred-row size made it a lossy selector of genuinely stronger models.
  • 8.2 Threats to validity: 0.860 was my best private score, while the same submission scored 0.844 public and public-best submissions reached 0.852–0.856.The ordering inverted: selecting on public performance could leave a medal-class private result unselected.
  • 9 Memorization, not search: Private LB 0.920 was achieved by the first-place solution by deciding what to memorize and what to compute, rather than teaching the model to search.This demonstrates that the ceiling applies to search distillation, not to the underlying task.
  • 9 Memorization, not search: ≈5 × 10^10 cryptarithm candidates cannot fit within 7680 tokens, so the winning method removes search from the trace through precomputed signatures and catalogs.It normalizes repeated-symbol patterns and catalogs valid operand configurations for verification.
  • 9 Memorization, not search: 5,238 valid 8-rule sequences were precomputed and memorized for bit manipulation, with nearest-catalog projection and example verification; held-out validation reached 91.57%.The method is learnable when candidate structure compresses into a small catalog and the residual verification is cheap enough to fit in budget.

10 Limitations … A Solver Pseudocode

The paper concludes that verifiable search does not become a learnable left-to-right chain-of-thought: most forward tasks transfer, but cryptarithm remains near 0.05 despite extensive training approaches. It frames the benchmark as a controlled proxy, documents architecture and scale limits, and releases solvers, evaluation data, and fidelity audits for reproducibility.

  • 10 Limitations: ≤0.04 was the cryptarithm floor across dense and MoE architectures, while frontier in-context models up to 671B capped at 0.05 / 0.00.The study reports single training seeds per cell and could not run frontier fine-tuning at length or the exact 30B/A3B Transformer match.
  • 11 Conclusion: ≈0.05 was cryptarithm performance after eleven chain-of-thought designs, RLVR, and STaR, supporting the conclusion that verifiable search is not a learnable chain-of-thought.The paper states that five independent measurements agreed on this explanation and that most other tasks transferred.
  • Ethics and Broader Impact: The benchmark raises competition-integrity concerns because public/private splits make public scores lossy selectors and adapter-noise laundering can create ostensibly independent submissions.The authors present these concerns to inform benchmark and competition design, not to enable gaming, and state they did not submit the noised adapter as their own work.
  • Reproducibility and Artifacts: 7,566 per-line fidelity-audit records accompany released solvers, synthetic-CoT renderers, held-out evaluation harnesses, and per-row evaluation CSVs.The code and paper source are released through the cited project repository and interactive walkthrough.
  • A Solver Pseudocode: 100% coverage is reported for numeral and unit_conversion among the forward solvers, while cipher is the only category requiring search over a closed vocabulary.Numeral uses a fixed greedy subtractive encoder, and unit_conversion fits y = ax + b from two separated example points.
  • A Solver Pseudocode: 67.7% deduce and 70.9% posterior vote are reported for cryptarithm, whose information-free digit-to-symbol cipher requires backtracking over assignments satisfying all example equations.The solver uses congruence and operand-forcing prunes, constrained variable ordering, up to 3000 assignments, and a two-regime mixture prior.
  • A Solver Pseudocode: ≈1/659 of instances are covered by the forward-only cryptarithm variant without backtracking, explaining why left-to-right chain-of-thought cannot faithfully reproduce the full search.The full solver instead enumerates consistent assignments and returns the answer with maximum posterior mass.

B Bit-Manipulation Solver, Basis, and Renderer

The bit-manipulation solver searches a composed boolean-expression grammar over transformed 8-bit input taps, reaching 98.88% query accuracy while exposing genuine over-fitting. Its verifiable rule inventory and per-bit stride renderer provide complementary machine-checkable and narratable representations, but the renderer is used only to author chain-of-thought.

  • Global single-rule search: 98.88% (1584/1602) of recovered rules generalize to the query, while 18 rules fit all examples but predict the wrong query output.The solver searches a composed expression grammar over up to three transformed taps; example fit and held-out query correctness are distinct measurements.
  • Global single-rule search: 56% of recovered rules use two taps and 34% use three taps, with the three-tap stratum forming the largest hard slice and residual ceiling.The cache contains 5 zero-tap, 149 one-tap, 899 two-tap, and 549 three-tap rules; the 18 over-fit failures split across one-, two-, and three-tap rows.
  • Verifiable rule inventory: The verifiable rule inventory covers all 1602 recovered rules and agrees with the human-named basis, including xor-dominant, xnor, identity/copy, and AND/OR composition families.Table 9 is computed directly from the solve cache, while the named basis is the interpretable view of the same rule structure.
  • Per-bit stride renderer: 84.6% is the per-bit stride renderer’s coverage when expressing each output bit as a constant, copy, or two-input gate with fixed-stride input positions.The renderer greedily set-covers the eight output bits using maximal cyclic runs, preferring longer runs and simpler descriptors, and is used only to author chain-of-thought.

C Training Configuration and Submission History

The paper used lean projection-only and merge training stacks, organized through a cheapest-first experiment ladder. Despite rapid loss convergence, held-out cryptarithm accuracy remained low, while bit accuracy improved only with STaR.

  • Training stacks: The lean stack adapted projection modules, while the merge stack also adapted attention projections and the unembedding, producing the banked 0.85 adapter.Projection-only training used ≈880M trainable parameters, or 2.71%; the merge set was larger.
  • Experiment ladder: The experiment ladder progressed from free base-model API probes to capped Tinker LoRA rounds and a Kaggle from-base final.Tinker used rank 32 and learning rate 2 × 10−4 fresh / 5 × 10−6 resume; its SVD conversion cost ≈0.025 LB on calibration.
  • Loss convergence vs. learning: [0.01, 0.07] held-out cryptarithm accuracy persisted across all fourteen rounds despite training loss reaching its floor rapidly.Kaggle merge runs reached final loss ≈0.003, Tinker warm-start reached NLL ≈0.001, and cryptarithm rounds reached NLL 0.146 by step 35 before the second-epoch floor.
  • Submission history: Cryptarithm rounds consumed compute without improving, whereas bit accuracy climbed only under STaR.The submission history identifies v17 as the banked result, v18 as adding bit STaR within noise, and v19 as parked.

D Tokenizer Analysis

The tokenizer’s byte-level BPE avoids practical unknown tokens but makes ASCII formatting important because Unicode operators fragment into rare pieces. Token audits show lookup/fit traces are easier for the base than cryptarithm and cipher traces, while inference generation often exceeds authored CoT brevity.

  • Tokenizer design: 131,072 vocabulary entries, 269,443 merges, no practical <unk> emissions, and 1,000 added tokens define the byte-level BPE tokenizer.Coverage comes through the byte alphabet; added tokens include <think>/</think> and 982 reserved <SPECIAL_n> slots.
  • ASCII constraint: 8-bit strings tokenize into exactly 8 tokens, while ASCII operator spellings avoid the rare multi-byte fragments produced by Unicode glyphs.The CoT therefore uses XOR/OR/AND/NOT, ->, !=, and ok/no instead of Unicode symbols.
  • Length and budget: ≤274-token synthetic CoT expands to ≈1k–3.8k generated tokens, although the 7680-token budget binds only on rendered cryptarithm searches.Free-run medians range from ≈1k for numeral to ≈3.8k for bit, while authored brevity does not survive inference.
  • Per-token difficulty: 2.1–3.2 mean token cross-entropy for lookup/fit traces contrasts with 5.9–6.3 for cryptarithm and cipher traces.The harder categories use tokens the base finds more surprising, including rare cipher words, cryptarithm glyphs, and enumeration.

E Per-Sub-Category Results and Failure Statistics

This section reports per-sub-category accuracy for the base model, reference adapter, and banked adapter on a held-out unseen split. It also breaks down failures, showing wrong answers dominate except in cryptarithm search renders, where truncation also occurs.

  • Failure statistics: Failures are wrong-answer rather than truncation in every category except the cryptarithm search renders.The failure-type breakdown grounds the section’s analysis of shipped-adapter behavior.
  • Per-sub-category accuracy: 0.86-class reference adapter accuracy is measured by re-running it over all 9,500 training rows, while the banked adapter uses a held-out unseen split.The unseen split is identified as the trustworthy generalization number.
  • Per-sub-category accuracy: 0.678 on a 500-row set replaces the small-n unseen bit result, while eq-deduce generalization is approximately 0.85.These disjoint evaluations supersede the small-n unseen cells for those sub-categories.

F Leaderboard Trajectory

The leaderboard gains came from making more categories learnable rather than polishing a single model. The submission history documents this trajectory.

  • F Leaderboard Trajectory: Leaderboard gains came from making more categories learnable, not from polishing a single model.The submission history is presented in Figure 6.
  • F Leaderboard Trajectory: Figure 6 tracks the submission history behind the leaderboard trajectory.
  • F Leaderboard Trajectory: The trajectory reflects expanding learnability across categories rather than incremental refinement of one model.
Loading 2606.21884v1…