Research map / Large language models / Reasoning and chain of thought
On the Bias of Next-Token Predictors Toward Systematically Inefficient Reasoning: A Shortest-Path Case Study
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Trains small GPT-style (Phi3-architecture) transformers from scratch on layered-graph shortest-path question-trace-answer data and finds that inefficient DFS-like traces generalize better than DP traces at equal token budget, with next-token confidence as the explanatory signal.
Problem
Whether optimal, globally efficient chain-of-thought traces are the best training signal for next-token predictors learning multi-step reasoning, versus longer but structured inefficient traces.
Approach
Controls trace efficiency via an exploration-order temperature eta in a synthetic layered-DAG shortest-path task, showing that backtracking DFS-like traces beat bottom-up DP traces under equal token budgets, and that generalization tracks average next-token confidence rather than length alone.
Key results
- With a 128M-token budget, the inefficient DFS-like (eta=-5) traces, roughly 75% longer than DP traces, yield better generalization accuracy than DP (eta=+5) traces, and the paper reports the DFS model sees about 1/3 fewer graph examples.
- Average exploration-order surprisal is 1.3262 for DP, 0.4821 for DFS, and 1.905 for random eta=0, with eta=0 the least predictable and worst-performing.
- Injecting deterministic redundancy (DR) slightly degrades performance versus DP at a 128M budget, indicating length alone does not help.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add an intermediate reasoning trace instead of training question-to-answer only (ablation) | 3-layer Phi3-small · Shortest path on unseen larger in-distribution graphs | answer accuracy | Helped |
| Train with systematic depth-first traces (η=-5) instead of DP traces (η=+5) (ablation) | 3-layer Phi3-small · Shortest path on unseen graphs | answer accuracy | Helped |
| Train with DP traces (η=+5) instead of randomly ordered traces (η=0) (ablation) | 3-layer Phi3-small · Shortest path on unseen graphs | answer accuracy | Helped |
| Replace DP traces with longer, systematic DFS traces (ablation) | 3-layer Phi3-small · Shortest path; fixed training-token budget | answer accuracy: roughly 75% longer | Helped |
| Add deterministic repetition of each DP reasoning step (ablation) | 3-layer Phi3-small · Shortest path; 128M-token budget | answer accuracy | Hurt |
| Add randomized repetition of completed DP reasoning steps (ablation) | 3-layer Phi3-small · Shortest path | answer accuracy | Hurt |
| Use positive sampling temperature rather than zero temperature (ablation) | η=0 model · Shortest path | answer accuracy | Helped |
| Use positive sampling temperature rather than zero temperature (ablation) | η=+5 randomized-repetition (RR) model · Shortest path | answer accuracy | Helped |
| Increase the model depth from 3 layers to 6 layers (ablation) | DP-trained Phi3-small · Shortest path generalization; 32M tokens | answer accuracy | Helped |
| Reduce the training budget from 32M to 16M tokens (ablation) | 3-layer DP-trained Phi3-small · Shortest path generalization | answer accuracy: 10% | Hurt |
Surprising findings
- Inefficient backtracking DFS-style traces generalize better than globally optimal DP traces under the same token budget.
- Adding arbitrary redundant repetitions of reasoning steps fails to help and can slightly hurt performance.
Limitations
- Synthetic, minimalist algorithmic task with a custom token language; transfer to natural language is untested.
- Only a small 3-layer transformer (28.5M params) studied in main experiments; other architectures may behave differently.
- Confidence is correlational evidence for the explanation rather than a causal mechanism.
Experimental setup
Datasets: procedurally generated layered-DAG shortest-path instances with DP and parametric alternative traces
Benchmarks: held-out layered-graph shortest-path test set (3, 5, 7 layers)
Metrics: answer accuracy number of reasoning steps next-token confidence surprisal of exploration order training loss
Baselines: eta=+5 (DP) trace training eta=0 random exploration traces eta=+5 (DR) deterministic redundancy eta=+5 (RR) randomized redundancy no-CoT question-answer training
Builds on: Phi-3 chain-of-thought prompting A* search dynamics transformer work min-margin confidence metrics
Closest papers by meaning
- Token Assorted: Mixing Latent and Text Tokens for Improved Language Model Reasoning (ICML 2025 · similarity 0.90)
- Beyond Semantics: The Unreasonable Effectiveness of Reasonless Intermediate Tokens (NeurIPS 2026 · similarity 0.90)
- Tracing the Traces: Latent Temporal Signals for Efficient and Accurate Reasoning (ICLR 2026 · similarity 0.90)
- Probing the Trajectories of Reasoning Traces in Large Language Models (NeurIPS 2026 · similarity 0.90)
- On the Token Value Inequality in Efficient Reasoning (NeurIPS 2026 · similarity 0.90)
- Boule or Baguette? A Study on Task Topology, Length Generalization, and the Benefit of Reasoning Trace (NeurIPS 2026 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.