Research map / Large language models / Reasoning and chain of thought
Language Models can Self-Improve at State-Value Estimation for Better Search
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 Self-Taught Lookahead (STL), a reward-free self-improvement method that fine-tunes an LLM value model to simulate one step of lookahead in natural language, improving search on WebShop, HotpotQA and Game-of-24.
Problem
Search with LLM value functions needs accurate state-value estimates, but ground-truth rewards or human demonstrations for multi-step interactive tasks such as web navigation are expensive to collect.
Approach
Train a value LLM on its own tree-search lookahead: for each visited state, record the best next action, the resulting successor state, its value rationale, and the lookahead value (a Bellman-style target), then fine-tune to generate these before the value. At inference the model simulates a lookahead step itself, letting small open models guide search with fewer expansions.
Key results
- On WebShop with a gpt-3.5-turbo policy, greedy search with an STL-tuned llama-3.1-8b value model reaches 36.6% SR vs 26.4% for the base llama value model on the full test set (about 39% relative improvement on the mini set, 26.0 to 40.0 with gpt-4o policy).
- STL with gpt-4o policy and STL llama value achieves 74.2 score and 40.6% SR on full WebShop, matching the gpt-4o value model (40.8% SR).
- On HotpotQA full test set (500), STL reaches 61.8% match rate vs 56.4% for the base llama value model and 57.6% for gpt-4o value.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Fine-tune the value model with STL | Greedy search with llama-3.1-8b-instruct value model · WebShop full test set (500) | Success rate: 26.4 -> 36.6 | Helped |
| Fine-tune the value model with STL | Greedy search with llama-3.1-8b-instruct value model · WebShop full test set (500) | Score: 67.7 -> 72.8 | Helped |
| Fine-tune the value model with STL | Greedy search with llama-3.1-8b-instruct value model · HotpotQA test set (500) | Match rate: 56.4 -> 61.8 | Helped |
| Use lookahead values only (ablation) | STL value model · WebShop mini test set (50) | Score: 70.0 -> 76.0 | Helped |
| Add next-best action and successor state to lookahead values (ablation) | STL value model · WebShop mini test set (50) | Score: 76.0 -> 74.4 | Hurt |
| Add successor-state value rationale to lookahead values and transitions (ablation) | STL value model · WebShop mini test set (50) | Score: 74.4 -> 78.3 | Helped |
| Train with loss on output tokens only instead of input and output tokens (ablation) | Lookahead-value-only baseline · WebShop | Score: 70.9 -> 76.0 | Helped |
| Run a second STL iteration (ablation) | STL value model · WebShop | Average reward: 68.6 | Hurt |
| Run a second STL iteration (ablation) | STL value model · WebShop | Success rate: 26.0 | Hurt |
| Increase to 50 tasks per iteration (ablation) | STL value model · Game-of-24, unseen tasks | Accuracy: 30.0 -> 48.0 | Helped |
| Use 25 tasks per iteration (ablation) | STL value model · Game-of-24, unseen tasks | Accuracy: 38.0 -> 34.0 | Hurt |
Surprising findings
- A second iteration of STL decreased WebShop performance (score 68.6, SR 26.0) because the simulated second-step lookahead often did not match the true environment.
- Loss over input and output tokens harmed the lookahead-value-only baseline, while output-only loss was needed for it to perform well.
Limitations
- Gains are limited to tasks with high action diversity and consistent state transitions; HotpotQA shows smaller gains and needs 500 rollout tasks.
- Multiple STL iterations hurt on WebShop because the value model cannot reliably simulate more than one step ahead.
- Experiments are limited to models up to 8B parameters due to compute constraints.
Experimental setup
Datasets: WebShop HotpotQA Game-of-24
Benchmarks: WebShop HotpotQA Game-of-24
Metrics: score success rate match rate accuracy states expanded tokens cost
Baselines: IL IL+RL AgentQ Reflexion LATS R1-Searcher ReAct Greedy search with gpt-4o value
Builds on: Tree-of-Thoughts LATS fitted value iteration ReAct Self-Taught Reasoner
Closest papers by meaning
- Iterative Self-Incentivization Empowers Large Language Models as Agentic Searchers (NeurIPS 2025 · similarity 0.88)
- Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models (ICML 2024 · similarity 0.88)
- ReSeek: A Self-Correcting Framework for Search Agents with Instructive Rewards (ICML 2026 · similarity 0.88)
- Enhancing Decision-Making for LLM Agents via Step-Level Q-Value Models (AAAI 2025 · similarity 0.88)
- Search-R2: Enhancing Search-Integrated Reasoning via Actor-Refiner Collaboration (ICML 2026 · similarity 0.87)
- Learning to Better Search with Language Models via Guided Reinforced Self-Training (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.