# ASTRO: Teaching Language Models to Reason by Reflecting and Backtracking In-Context

arXiv: https://arxiv.org/abs/2507.00417 · HTML: https://mlsanity.com/paper/2507.00417/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 22 of its 41 references that are in the map.
- First posted on arXiv 1 Jul 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 22 of 22)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Understanding R1-Zero-Like Training: A Critical Perspective](https://mlsanity.com/paper/2503.20783/) (2025)
- [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [Qwen2.5-Math Technical Report: Toward Mathematical Expert Model via Self-Improvement](https://mlsanity.com/paper/2409.12122/) (2024)
- [Tulu 3: Pushing Frontiers in Open Language Model Post-Training](https://mlsanity.com/paper/2411.15124/) (2024)
- [Open-Reasoner-Zero: An Open Source Approach to Scaling Up Reinforcement Learning on the Base Model](https://mlsanity.com/paper/2503.24290/) (2025)
- [Demystifying Long Chain-of-Thought Reasoning in LLMs](https://mlsanity.com/paper/2502.03373/) (2025)
- [Spurious Rewards: Rethinking Training Signals in RLVR](https://mlsanity.com/paper/2506.10947/) (2025)
- [In-context Reinforcement Learning with Algorithm Distillation](https://mlsanity.com/paper/2210.14215/) (2022)
- [Stream of Search (SoS): Learning to Search in Language](https://mlsanity.com/paper/2404.03683/) (2024)
- [LLMs Can Easily Learn to Reason from Demonstrations Structure, not content, is what matters!](https://mlsanity.com/paper/2502.07374/) (2025)
- [Towards System 2 Reasoning in LLMs: Learning How to Think With Meta Chain-of-Thought](https://mlsanity.com/paper/2501.04682/) (2025)
- [Beyond A*: Better Planning with Transformers via Search Dynamics Bootstrapping](https://mlsanity.com/paper/2402.14083/) (2024)
- [e3: Learning to Explore Enables Extrapolation of Test-Time Compute for LLMs](https://mlsanity.com/paper/2506.09026/) (2025)
- [Step-KTO: Optimizing Mathematical Reasoning through Stepwise Binary Feedback](https://mlsanity.com/paper/2501.10799/) (2025)
- [The Climb Carves Wisdom Deeper Than the Summit: On the Noisy Rewards in Learning to Reason](https://mlsanity.com/paper/2505.22653/) (2025)

## Built on by (most cited first, 13 of 13)

- [From Reasoning to Super-Intelligence: A Search-Theoretic Perspective](https://mlsanity.com/paper/2507.15865/) (2025)
- [Schoenfeld's Anatomy of Mathematical Reasoning by Language Models](https://mlsanity.com/paper/2512.19995/) (2025)
- [Tailored Primitive Initialization is the Secret Key to Reinforcement Learning](https://mlsanity.com/paper/2511.12429/) (2025)
- [Credit Assignment with Resets in Language Model Reasoning](https://mlsanity.com/paper/2605.25507/) (2026)
- [Asking the Right Questions: Improving Reasoning with Generated Stepping Stones](https://mlsanity.com/paper/2602.19069/) (2026)
- [Search, Fail, Recover: A Training Framework for Correction-Aware Reasoning](https://mlsanity.com/paper/2607.07492/) (2026)
- [Can Transformers Learn to Verify During Backtracking Search?](https://mlsanity.com/paper/2605.22221/) (2026)
- [When RL Suppresses Its Own Vocabulary: Recovering Reasoning Diversity in Puzzle-to-Math Transfer](https://mlsanity.com/paper/2605.29190/) (2026)
- [Offline-Online Curriculum RL for Multimodal Reasoning](https://mlsanity.com/paper/2607.23700/) (2026)
- [When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models](https://mlsanity.com/paper/2608.30395/) (2026)
- [Training Large Language Models for Small-Molecule Design with Synthetic Task Scaling](https://mlsanity.com/paper/2609.04735/) (2026)
- [Self-Play Search Distillation for Large Language Model Reasoning](https://mlsanity.com/paper/2609.30936/) (2026)
- [TreeFlex: Agents Navigating Their Own Search Trees](https://mlsanity.com/paper/2610.20334/) (2026)

## Abstract (arXiv)

We introduce ASTRO, the "Autoregressive Search-Taught Reasoner", a framework for training language models to reason like search algorithms, explicitly leveraging self-reflection, backtracking, and exploration in their outputs. Recently, training large language models (LLMs) via reinforcement learning (RL) has led to the advent of reasoning models with greatly enhanced reasoning capabilities. Open-source replications of reasoning models, while successful, build upon models that already exhibit strong reasoning capabilities along with search behavior observed even before RL. As a result, it is yet unclear how to boost the reasoning capabilities of other non-reasoner models including Llama 3. ASTRO teaches such models to internalize structured search behavior through a synthetic dataset derived from Monte Carlo Tree Search (MCTS) over mathematical problem-solving trajectories. By converting search traces into natural language chain-of-thoughts that capture both successes and recoveries from failure, ASTRO bootstraps models with a rich prior for exploration during RL. We finetune our models on these search-derived traces and further improve performance via RL with verifiable rewards. We apply ASTRO to the Llama 3 family of models and achieve absolute performance gains of 16.0% on MATH-500, 26.9% on AMC 2023, and 20.0% on AIME 2024, especially improving upon challenging problems that require iterative correction. Our results demonstrate that search-inspired training offers a principled way to instill robust reasoning capabilities into open LLMs.