Source-linked AI summary
StepSearch: Igniting LLMs Search Ability via Step-Wise Proximal Policy Optimization
Ziliang Wang, Xuhui Zheng, Kang An, Cijun Ouyang, Jialu Cai, Yuhang Wang, Yichao Wu
TL;DR
Complex multi-hop QA requires iterative acquisition of external knowledge, but existing approaches leave search trajectories under-supervised and search-RL methods often rely on sparse global rewards. StepSearch combines sub-question-level search trajectories with PPO augmented by token-level information-gain rewards and redundancy penalties. It consistently outperforms strong Search-RL baselines across in-domain and out-of-domain benchmarks, with reported absolute gains of 5.7%, 9.1%, 10.0%, and 15.2%.
Problem
Complex multi-hop QA faces intrinsic knowledge gaps, while existing search-RL methods provide limited explicit guidance for intermediate search trajectories.
Method
StepSearch combines sub-question-aligned search trajectories with PPO augmented by token-level information-gain rewards and redundancy penalties.
Results
5.7%, 9.1%, 10.0%, and 15.2% absolute gains are reported over standard reinforcement-learning baselines across diverse multi-hop QA benchmarks.
Takeaways & Limitations
StepSearch consistently outperforms strong Search-RL methods on both in-domain MuSiQue and out-of-domain multi-hop QA datasets.
Takeaways & Limitations
Evaluation is limited to text-only QA, modest parameter scales, and 19k MuSiQue training examples.
Abstract
from arXiv · showhide
Efficient multi-hop reasoning requires Large Language Models (LLMs) based agents to acquire high-value external knowledge iteratively. Previous work has explored reinforcement learning (RL) to train LLMs to perform search-based document retrieval, achieving notable improvements in QA performance, but underperform on complex, multi-hop QA resulting from the sparse rewards from global signal only. To address this gap in existing research, we introduce StepSearch, a framework for search LLMs that trained with step-wise proximal policy optimization method. It consists of richer and more detailed intermediate search rewards and token-level process supervision based on information gain and redundancy penalties to better guide each search step. We constructed a fine-grained question-answering dataset containing sub-question-level search trajectories based on open source datasets through a set of data pipeline method. On standard multi-hop QA benchmarks, it significantly outperforms global-reward baselines, achieving 11.2% and 4.2% absolute improvements for 3B and 7B models over various search with RL baselines using only 19k training data, demonstrating the effectiveness of fine-grained, stepwise supervision in optimizing deep search LLMs. Our code will be released on https://github.com/Zillwang/StepSearch.
1 Introduction
Multi-hop QA remains difficult because models face intrinsic knowledge gaps and inefficient knowledge assimilation, while existing search-RL methods often lack explicit guidance for intermediate search trajectories. StepSearch addresses this with sub-question-aligned search data and token-level, step-wise rewards for information gain and redundancy.
- Complex multi-hop QA still faces intrinsic knowledge gaps and static, inefficient knowledge-assimilation mechanisms.
- Existing search-RL methods mainly use answer- and format-level rewards, leaving intermediate search keywords and document use under-specified.
- StepSearch builds sub-question-aligned search-keyword trajectories and a regenerated multi-hop dataset for sequential retrieval benchmarking.
- StepSearch augments PPO with token-level information-gain rewards and redundancy penalties for query formulation and document retrieval.
- StepSearch outperforms standard reinforcement-learning baselines by 5.7%, 9.1%, 10.0%, and 15.2% absolutely across diverse multi-hop QA benchmarks.
2 Methodology
StepSearch constructs subquestion-level search trajectories and trains search-capable LLMs with step-wise PPO, combining global answer rewards with token-level signals for query quality, information gain, and redundancy. Its pipeline iteratively generates and filters queries, while training masks retrieved content to focus updates on the model’s reasoning and search policy.
- Data Pipeline: The MuSiQue-based pipeline enriches decomposed questions with subquestion–answer pairs, generates multiple queries per step, and retains results validated across at least half of the sources.The pipeline uses GPT-4o enrichment, reformulation into N queries, retrieval from M sources, and a ⌈M/2⌉ validity threshold.
- Search Actions: Training iterates through think, search, and information phases until an answer is produced or the action budget is reached, while masking information segments from gradient computation.Masking retrieved documents decouples parameter updates from retrieval artifacts and concentrates optimization on internal reasoning and search-policy parameters.
- Step-wise PPO: StepSearch augments PPO with token-level information-gain and redundancy-penalty rewards for query formulation and document retrieval.The method is described as step-wise reinforcement learning with dual rewards and process-aware supervision.
- Step-wise PPO: The advantage combines global and step-wise search-round rewards, placing the global reward at the output’s last position and the step-wise reward at each search round’s final token.PPO clipping stabilizes training, and the advantage is estimated with GAE from future rewards and a learned value function.
- Global and Query Rewards: Global answer reward uses word-level F1 with a format check, while search-key reward measures word-level F1 alignment between emitted queries and reference keywords when the required format is satisfied.Strict format validation requires properly paired search tags, at least one think/search round, and one final answer tag.
- Search-Step Reward: Information gain tracks marginal similarity improvements to ground-truth documents, whereas redundancy penalties apply when retrieved results overlap with prior retrieval history.The information-gain calculation maintains maximum matching records across rounds; redundancy is based on repeated documents and updates cumulative history for later rounds.
3 Experiment
StepSearch is evaluated against prompting, supervised fine-tuning, reasoning-model, and search-RL baselines across four multi-hop QA datasets. The experiments use Qwen models, synthesized MuSiQue supervision data, E5 retrieval during training, and Wikipedia-based evaluation retrieval.
- Datasets and Metrics: Evaluation covers HotpotQA, MuSiQue, 2WikiMultiHopQA, and Bamboogle using canonical word-level F1 and Exact Match.The study avoids third-party LLM judges because of reproducibility and stability limitations.
- Baselines: StepSearch is compared with naive generation, CoT, RAG, SFT, large reasoning models, and existing search-RL methods.The baseline set spans prompting and reinforcement-learning paradigms as well as static and dynamic retrieval strategies.
- Models and Setup: Experiments use Qwen-2.5-7B and Qwen-2.5-3B Base and Instruct models, testing both model size and instruction status.RL methods are evaluated on Base and Instruct variants to gauge cross-model robustness.
- Main Results: StepSearch consistently outperforms strong Search-RL baselines across in-domain MuSiQue and out-of-domain HotpotQA, 2WikiMultiHopQA, and Bamboogle.The reported advantage holds across models of different sizes and types.
4 Further Analysis
Further analyses compare StePPO with PPO and GRPO and ablate its search-process rewards. They indicate benefits from stepwise supervision, information gain, and redundancy control, while keyword rewards alone can destabilize training.
- Different RL Comparison: StePPO achieves higher accuracy in fewer training rounds with shorter outputs than PPO and GRPO.The analysis attributes this result to enriched search supervision.
- Different RL Comparison: StePPO reaches the highest convergence speed and peak effectiveness, outperforming PPO and GRPO in final F1.PPO provides the most stable training, whereas GRPO is prone to reward collapse at higher learning rates.
- Ablation Study: Redundancy penalty alone does not optimize search ability, but combined information gain supports high-quality, low-repetition search and a higher capacity ceiling.The comparison refers to the ow-rp and ow-ss ablations.
- Ablation Study: Search-key rewards can significantly accelerate convergence, but without process supervision they may produce hallucination, reward collapse, incoherent responses, and failed convergence.This behavior appears in the ow-skr ablations.
- Ablation Study: Supervising intermediate sub-task answers produces search keywords similar to sub-question answers and improves results across various datasets.These experiments further support the effectiveness of process supervision.
5 Limitations
The study is limited to text-only QA, modest parameter scales, and 19k MuSiQue training examples, leaving multimodal generalization and larger-scale behavior unresolved.
- Scope: Evaluation is restricted to text-only question answering, so generalization to multimodal inputs and cross-paradigm tasks remains untested.The authors specifically identify images and audio as open cases.
- Scale: Experiments use relatively modest parameter scales, and larger models may intensify reward collapse and unstable training dynamics.The authors point to 14B and 32B models as untested regimes requiring stabilization and regularization strategies.
- Training Data: StepSearch currently uses only 19k MuSiQue training examples, and its performance at Search-R1’s training-data scale is unknown.This leaves the effect of substantially increasing training data unresolved.
6 Future Work
Future work targets richer post-retrieval comprehension, more diverse search behavior, multimodal and cross-paradigm tasks, and stable scaling to larger models.
- Planned Extensions: The authors plan to improve post-retrieval comprehension and metacognitive reflection for more nuanced integration of external evidence.They also plan to diversify and increase the complexity of search behaviors.
- Planned Extensions: The framework is planned for extension beyond text-only QA to multimodal, cross-paradigm settings.This directly addresses the current evaluation boundary.
- Scaling: Future work will explore scaling StePPO to 14B and 32B parameter regimes and developing countermeasures against reward collapse.The stated goal is stable, efficient training at scale.
A Prompt for Research Plan on Question Answering
The prompt template structures tool-augmented reasoning with demonstrations and a dedicated retrieved-results label. Intermediate sub-answer feedback is associated with improved supervised search behavior and results across datasets.
- Prompt design: The prompt uses three chain-of-thought demonstrations and a dedicated label for retrieved results.This structure enforces consistent reasoning and retrieval behavior through zero-shot guidance.
- Prompt design: Table 4 describes an LLM interacting with external search engines and answering prompts instantiated with the actual question.
- Process feedback: Intermediate sub-task answers provide feedback through the global reward during the search process.
- Process feedback: Keywords in supervised search behavior resemble sub-question answers and improve results across various datasets.
B Experiment Setups
Experiments train Qwen-2.5 models on processed MuSiQue data and evaluate them across four multi-hop QA benchmarks. EM and F1 are used as the evaluation metrics, with implementation and optimization details specified for reproducibility.
- Datasets and models: Experiments use Qwen-2.5-3B and Qwen-2.5-7B models, training on processed MuSiQue data and evaluating four multi-hop QA datasets.Evaluation uses 2WikiMultiHopQA, Bamboogle, HotpotQA, and MuSiQue test or validation sets.
- Evaluation: EM and F1 score are used as evaluation metrics.
- Optimization: Training runs for 500 steps across two nodes with 16 H800 GPUs and uses policy and value-model learning rates of 7e −7 and 7e −6.
- Optimization: Rollout sampling uses temperature 1.0, top_p 1.0, KL coefficient β 1e −3, and clipping ratio 0.2.
C Case Study
Training cases show that redundancy penalties and information-gain guidance address repetitive or unreliable retrieval behavior. Using only a global search-key reward instead causes formatting exploitation, anomalous interactions, fabricated answers, and training failure.
- Early training: Early training repeatedly issues similar search keywords, wasting computation and increasing failure risk before the search limit.Low-quality queries may miss required documents, while distrust of correct documents prompts reconfirmation.
- Global-reward failure: Using only GLOBAL search-key scores encourages format-reward exploitation, producing anomalous interactions and ultimately causing a training crash.Observed failures include incorrect search formatting and fabricated phantom answers.
- Reward behavior: Table 6 labels golden, question-independent, and redundant documents to illustrate redundancy-penalty and information-gain effects during early training.
- Reward behavior: Table 7 uses the same document categories to show the roles of redundancy penalties and effective information gain in late training.
- Global-reward failure: Table 8 reports that search-key-only rewards produce incorrect search interactions and fabricated data through formatting-reward exploitation.