Research map / Large language models / Reasoning and chain of thought
Learning to Better Search with Language Models via Guided Reinforced Self-Training
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 Guided-ReST, a self-training method that injects optimal solution subgoals into self-generated search traces (subgoal augmentation) and fine-tunes on them, followed by operation-level PPO, improving search efficiency on Countdown and code self-repair.
Problem
Language models trained on noisy search traces (stream of search) use test-time compute inefficiently, repeatedly exploring irrelevant paths; need self-generated search traces that are both high-likelihood and high-quality for effective search.
Approach
Use optimal solution subgoals as landmarks: when a search attempt fails at a subgoal, replace an unsuccessful child with the correct subgoal, truncate, and let the model continue, producing high-likelihood successful traces for SFT; then apply PPO reformulated at the operation level.
Key results
- On Countdown at maximum token budget, Guided-ReST+PPO reaches 87% accuracy on both seen and unseen targets, outperforming the second-best PPO by more than 10%.
- Guided-ReST reaches comparable accuracy to PPO while using about 50% of its tokens on Countdown.
- On CodeContests pass@32, Guided-ReST reaches 33.9% vs 30.4% for ReST and 25.8% for base; on CodeForces 37.6% vs 35.9%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use optimal-solution guidance to generate search traces instead of standard ReST data generation | Countdown · seen target, pass@32 | pass@32 accuracy: 76.6 -> 96.8 | Helped |
| Use optimal-solution guidance to generate search traces instead of standard ReST data generation | Countdown · unseen target, pass@32 | pass@32 accuracy: 77.0 -> 96.8 | Helped |
| Use optimal-solution guidance to generate search traces instead of standard ReST data generation | CodeContests · pass@32 | pass@32 accuracy: 30.4 -> 33.9 | Helped |
| Use optimal-solution guidance to generate search traces instead of standard ReST data generation | CodeForces · pass@32 | pass@32 accuracy: 35.9 -> 37.6 | Helped |
| Increase partial-solution guidance length from 0 to 3 (ablation) | Countdown search traces · 10K training examples | accuracy: 55.96 -> 100.00 | Helped |
| Increase partial-solution guidance length from 0 to 3 (ablation) | Countdown search traces · 10K training examples | cross-entropy loss: 0.0481 -> 0.2539 | Hurt |
| Add optimal-solution guidance during data generation before PPO fine-tuning (ablation) | Countdown PPO · Countdown | accuracy | Helped |
| Use operation-level rather than token-level MDP for PPO (ablation) | Guided-ReST + PPO · Countdown, maximum token budget | accuracy: 83% -> 87% | Helped |
| Use operation-level rather than token-level MDP for PPO (ablation) | Guided-ReST + PPO · Countdown, low-budget regime | token efficiency: approximately 2× | Helped |
| Use operation-level rather than token-level MDP for PPO (ablation) | Guided-ReST + PPO · Countdown, high-budget regime | token efficiency: about 1.5× | Helped |
| Add subgoal-based dense rewards to PPO fine-tuning (ablation) | SoS model on Countdown · Countdown, high-budget regime | accuracy | Hurt |
| Increase the number of samples from pass@1 to pass@32 | Guided-ReST versus ReST · Countdown, seen and unseen targets | pass@k accuracy: 62.7 -> 96.8; 61.0 -> 96.8 | Helped |
Surprising findings
- PPO initialized with standard ReST does not benefit, while PPO initialized with Guided-ReST yields significant gains.
- A dense subgoal reward added to PPO has little effect and slightly degrades high-budget performance.
Limitations
- Assumes access to optimal solutions and an oracle that identifies the first incorrect step for backtracking on Countdown.
- Code self-repair gains are moderate compared to Countdown, attributed to fewer training examples and incomplete subgoal augmentation.
- RL fine-tuning was not performed for code self-repair due to limited compute.
Experimental setup
Datasets: Countdown (generated arithmetic problems) SYNTHETIC-1 APPS CodeContests TACO
Benchmarks: Countdown CodeContests CodeForces
Metrics: accuracy pass@k token efficiency
Baselines: behavior cloning stream of search ReST PPO base model
Builds on: stream of search reinforced self-training (ReST) jump-start reinforcement learning PPO GRPO
Closest papers by meaning
- MARGE: Improving Math Reasoning with Guided Exploration (ICML 2025 · similarity 0.88)
- T1: Advancing Language Model Reasoning through Reinforcement Learning and Inference Scaling (ICML 2025 · similarity 0.88)
- Planning in Natural Language Improves LLM Search for Code Generation (ICLR 2025 · similarity 0.88)
- Token-Supervised Value Models for Enhancing Mathematical Problem-Solving Capabilities of Large Language Models (ICLR 2025 · similarity 0.88)
- Soft Reasoning: Navigating Solution Spaces in Large Language Models through Controlled Embedding Exploration (ICML 2025 · similarity 0.88)
- Language Models can Self-Improve at State-Value Estimation for Better Search (NeurIPS 2025 · similarity 0.87)
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.