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

• URL: http://arxiv.org/abs/2606.21884v1
• Date: Sat, 20 Jun 2026 04:52:14 GMT
• Title: A Verifiable Search Is Not a Learnable Chain-of-Thought
• Abstract summary: It is tempting to assume any task solvable by a short program can be taught to a model as its chain-of-thought.<n>This paper shows the assumption fails for an identifiable class of procedures.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Cybersecurity Detection Classification with Reasoning-enabled Language Models [50.72675435043546]
  A major issue in Security Operations Centers (SOCs) is alert fatigue.<n>Prior work prompts or fine-tunes large language models (LLMs) to emit a triage label directly, but does not train them to reason about whether a detection is a genuine threat.<n>We train a chain-of-thought (CoT) reasoning-enabled triage classifier on real, human-labeled Windows endpoint detections.
  arXiv  Detail & Related papers  (2026-07-30T16:22:13Z)
• Anatomy of a Sound Neural Reasoner: One-Shot Amortization, First-Pass Poisoning, and Search Inertness in Clue-Rich Completion [0.0]
  In clue-rich Sudoku, one forward pass commits essentially the entire grid.<n>All hard-slice failures are decided before search begins, when the first pass confidently deletes a value required by the true solution.<n>In clue-rich completion, LDT-like systems are one-shot amortized predictors rather than learned search procedures.
  arXiv  Detail & Related papers  (2026-07-22T00:05:34Z)
• Where Does Agent Reliability Come From? A Cross-Benchmark Decomposition of Verification Loops, Specialist Models, and Scaffolding in a Production Enterprise Agent [0.0]
  We study one production system whose architecture installs verification loops.<n>We instrument the loop end-to-end, yielding an empirical verifier confusion matrix.
  arXiv  Detail & Related papers  (2026-07-19T03:20:33Z)
• When Agents Commit Too Soon: Diagnosing Premature Commitment in LLM Agents [0.0]
  Long-answer LLM agents can fail quietly: they settle on one reading of the evidence early, then spend the rest of the run defending it.<n>We define representational commitment as cross-run hidden-state convergence at a fixed reasoning step.<n>A runtime monitor detects inconsistent trajectories from hidden states at AUROC up to 0.97 (0.85--0.88 under a stricter split)
  arXiv  Detail & Related papers  (2026-06-22T07:13:13Z)
• Automated Proving of Shannon-Type Entropy Inequalities via Fine-Tuned Language Models and Guided Tree Search [50.16356451328644]
  Proving Shannon-type entropy inequalities is a fundamental task in information theory.<n>We investigate whether small-scale large language models, fine-tuned on atomic proof steps, can automate this process.<n>We show that GPT-5.5 solves 1.7% samples under zero-shot prompting while Psitip solves 33.3% samples.
  arXiv  Detail & Related papers  (2026-06-04T05:43:12Z)
• Right Makes Might: Aligning Verified Hidden States Empowers RL Reasoning [55.264863369127774]
  Current methods reduce each correct rollout to a single reward bit, ignoring the geometric structure shared among their hidden states.<n>We propose Hidden-Align, an auxiliary loss function that aligns the last-layer hidden states of correct rollouts at the anchor token during RL training, with zero overhead in both training and inference.<n>On eight mathematical reasoning benchmarks, Hidden-Align improves average pass@1 over the DAPO baseline by 3.8, 6.2, and 5.4 percentage points on Qwen3-1.7B, 4B, and 14B respectively, with consistent pass@k gains across all three scales.
  arXiv  Detail & Related papers  (2026-06-02T06:51:15Z)
• Self-Verified Distillation: Your Language Model Is Secretly Its Own Synthetic Data Pipeline [56.53954182896384]
  We propose Self-Verified Distillation, a simple post-training refinement algorithm for large language models.<n>Self-Verified Distillation generates candidate solutions to unlabeled seed questions.<n>It filters them using prompt-based self-verification, and trains on the resulting self-curated dataset.<n>We find that sampling more candidate generations and using a larger verification budget during training data construction produces higher-quality self-curated data.
  arXiv  Detail & Related papers  (2026-05-20T17:26:10Z)
• Distributional Energy-Based Models for Uncertainty-Aware Structured LLM Reasoning [40.342912574072024]
  Large Language Models produce structured outputs such as travel plans or code solutions.<n>Individual reasoning steps may appear correct while the output as a whole violates budgets, fails test cases, or contradicts earlier deductions.<n>We propose a learned quality scorer with deterministic analytical constraint penalties for verifying structured LLM outputs.
  arXiv  Detail & Related papers  (2026-05-15T17:08:27Z)
• LaTER: Efficient Test-Time Reasoning via Latent Exploration and Explicit Verification [35.08680804423239]
  Chain-of-thought (CoT) reasoning improves large language models (LLMs) on difficult tasks, but it also makes inference expensive.<n>We propose Latent-Then-Explicit Reasoning (LaTER), a two-stage paradigm that first performs bounded exploration in a continuous latent space.<n>LaTER projects final-layer hidden states back to the input embedding space, preserves the latent KV cache, and uses entropy and model-native stop-token probes to decide when to switch.
  arXiv  Detail & Related papers  (2026-05-08T06:23:58Z)
• Rethinking Dense Sequential Chains: Reasoning Language Models Can Extract Answers from Sparse, Order-Shuffling Chain-of-Thoughts [51.84894623128418]
  Modern reasoning language models generate dense, sequential chain-of-thought traces implicitly assuming that every token contributes and that steps must be consumed in order.<n>We challenge both assumptions through a systematic intervention pipeline--removal, masking, shuffling, and noise injection--applied to model-generated reasoning chains.<n>We find that answer extraction operates on a sparse, order-insensitive, and structurally robust informational substrate.
  arXiv  Detail & Related papers  (2026-05-08T06:15:50Z)
• Epistemic Observability in Language Models [0.0]
  We find that models report highest confidence precisely when they are fabricating.<n>We prove, under formal assumptions, that this is not a capability gap but an observational one.<n>We construct a tensor interface that escapes the impossibility by exporting computational byproducts.
  arXiv  Detail & Related papers  (2026-03-20T21:59:34Z)
• LaSeR: Reinforcement Learning with Last-Token Self-Rewarding [54.72617309922891]
  Reinforcement Learning with Verifiable Rewards (RLVR) has emerged as a core paradigm for enhancing the reasoning capabilities of Large Language Models (LLMs)<n>Previous practice requires the LLM to sequentially generate solutions and self-verifications using two separate prompt templates, which significantly reduces efficiency.<n>We propose LaSeR (Reinforcement Learning with Last-Token Self-Rewarding), an algorithm that simply augments the original RLVR loss with a MSE loss.
  arXiv  Detail & Related papers  (2025-10-16T17:55:11Z)
• Valid Stopping for LLM Generation via Empirical Dynamic Formal Lift [6.908972852063454]
  Sequential-EDFL reduces generation by 22-28% vs. sequential baselines.<n>EDFL serves as a first-stage filter reducing verification burden by 83%.
  arXiv  Detail & Related papers  (2025-10-07T21:28:53Z)
• Probing for Arithmetic Errors in Language Models [86.8227317662622]
  Internal activations in language models can be used to detect arithmetic errors.<n>We show that simple probes can accurately decode both the model's predicted output and the correct answer from hidden states.<n>We train lightweight error detectors that predict model correctness with over 90% accuracy.
  arXiv  Detail & Related papers  (2025-07-16T16:27:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.