Research map / Large language models / Reasoning and chain of thought
LLMs Can Reason Faster Only If We Let Them
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.
Proposes AoT-O3, which applies SFT on AoT-style random-exploration planning traces followed by RLOO with a rule-based step-penalty reward to shorten solutions of Llama3-1B/3B and Gemma2-2B on Game of X, N-Puzzle, and Word Ladder.
Problem
Algorithm-of-Thoughts (AoT) planning gives good accuracy with a single query but produces much longer solutions than chain-of-thought, raising compute, latency and token costs.
Approach
Combine SFT on AoT-style state-transition traces (random valid exploration plus solution segments) with RL using an objective, non-learned reward that gives +1 for correct solutions minus a per-step penalty, so the model learns to find shorter valid plans.
Key results
- AoT-O3 on Llama3-1B Game of X: accuracy 55% to 72% while solution length drops from 31.9 to 9.7 steps.
- Across Game of X, N-Puzzle, and Word Ladder, AoT-O3 reduces solution length by up to about 80% relative to AoT-SFT per the abstract, with 27.8%-62.4% reductions reported in Section 5.3.
- AoT-O3 reaches 82% accuracy on Llama3-3B Game of X vs 66% for AoT-SFT.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Fine-tune AoT-SFT with RL to optimize for correctness and concise solutions | Llama3-1B · Game of X | accuracy: 55 -> 72 | Helped |
| Fine-tune AoT-SFT with RL to optimize for correctness and concise solutions | Llama3-1B · Game of X | solution length (steps): 31.9 -> 9.7 | Helped |
| Fine-tune AoT-SFT with RL to optimize for correctness and concise solutions | Llama3-1B · N-Puzzle | accuracy: 64 -> 68 | Helped |
| Fine-tune AoT-SFT with RL to optimize for correctness and concise solutions | Llama3-1B · N-Puzzle | solution length (steps): 26.0 -> 14.2 | Helped |
| Fine-tune AoT-SFT with RL to optimize for correctness and concise solutions | Llama3-1B · Word Ladder | accuracy: 47 -> 52 | Helped |
| Fine-tune AoT-SFT with RL to optimize for correctness and concise solutions | Llama3-1B · Word Ladder | solution length (steps): 26.1 -> 13.8 | Helped |
| Remove the κ incentive for transitions on the correct solution path (ablation) | AoT-O3 · Game of X | accuracy: 72 -> 71 | Hurt |
| Remove the κ incentive for transitions on the correct solution path (ablation) | AoT-O3 · Game of X | solution length (steps): 9.7 -> 11.6 | Hurt |
| Remove the κ incentive for transitions on the correct solution path (ablation) | AoT-O3 · N-Puzzle | accuracy: 68 -> 68 | No clear effect |
| Remove the κ incentive for transitions on the correct solution path (ablation) | AoT-O3 · N-Puzzle | solution length (steps): 14.2 -> 14.9 | Hurt |
| Remove the κ incentive for transitions on the correct solution path (ablation) | AoT-O3 · Word Ladder | accuracy: 52 -> 51 | Hurt |
| Remove the κ incentive for transitions on the correct solution path (ablation) | AoT-O3 · Word Ladder | solution length (steps): 13.8 -> 16.2 | Hurt |
Surprising findings
- Fine-tuning on random search trajectories drops Llama-3.3-70B Game of 24 accuracy to 3-5%, while prompting with random demonstrations keeps performance comparable to gold examples.
- In the authors' GPT-4 experiments, longer in-context demonstrations led to longer solutions with higher accuracy, contrary to the expectation that brevity helps.
Limitations
- Reward depends on hand-tuned step penalty alpha and cutoff beta tied to context window size.
- Evaluated only on small models (1B-3B) and three synthetic planning-style puzzles.
- Reported reductions and accuracy gains are inconsistent across domains (e.g., smaller gains on N-Puzzle).
Experimental setup
Datasets: Game of X (generated) N-Puzzle (generated) Word Ladder (NLTK words)
Benchmarks: Game of X N-Puzzle Word Ladder
Metrics: accuracy (%) average solution length (steps)
Baselines: CoT-SFT AoT-SFT AoT-O3 (kappa=0)
Builds on: Algorithm of Thoughts AoT+ RLOO Chain-of-Thought
Closest papers by meaning
- Rectifying LLM Thought from Lens of Optimization (ICLR 2026 · similarity 0.92)
- LLMs Can Plan Only If We Tell Them (ICLR 2025 · similarity 0.91)
- When More is Less: Understanding Chain-of-Thought Length in LLMs (ICLR 2026 · similarity 0.89)
- Chain of Thoughtlessness? An Analysis of CoT in Planning (NeurIPS 2024 · similarity 0.89)
- Satori: Reinforcement Learning with Chain-of-Action-Thought Enhances LLM Reasoning via Autoregressive Search (ICML 2025 · similarity 0.89)
- RL of Thoughts: Navigating LLM Reasoning with Inference-time Reinforcement Learning (ICLR 2026 · similarity 0.89)
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.