Organizations: Renmin University of China, Beijing 100872, China · Key Laboratory of Data Engineering and Knowledge Engineering, MOE, China · Ant Group, Beijing, China · Beijing Key Laboratory of Intelligent Database Systems and Applications, China · Engineering Research Center of Database and Business Intelligence, MOE, China
LLM-based search agents demonstrate strong capabilities in long-horizon information seeking and reasoning, typically trained via reinforcement learning. However, existing approaches predominantly rely on trajectory-level outcome rewards, providing limited supervision for complex search and reasoning processes. Although step-level credit assignment offers a promising solution, obtaining reliable and task-grounded supervision for open-ended search remains challenging. In this paper, we propose Evidence-Guided Group Relative Policy Optimization (EG-GRPO), a framework that derives step-level supervision from the evidence annotations available in synthetic deep search data. EG-GRPO identifies the first supporting citation for each required evidence claim and uses the newly acquired evidence to construct step-level process rewards. By representing the accumulated evidence as an evolving knowledge state, EG-GRPO further performs state-conditioned relative advantage estimation and combines the resulting step-level signal with the standard trajectory-level outcome advantage. Experiments on five challenging deep search benchmarks show that EG-GRPO generally outperforms standard GRPO and existing reward-enhanced and step-level RL baselines across different model scales. These results demonstrate that task-grounded evidence annotations can provide effective process supervision for credit assignment in deep search RL.
Figures & tables
Figure 1: Left: Distribution of overall evidence coverage across correct and incorrect trajectories, showing that task success strongly correlates with higher coverage. Right: Trajectory-wise cumulative evidence coverage over normalized search progress, demonstrating that correct trajectories consistently accumulate evidence faster from the early search stages.
Figure 2: Overview of EG-GRPO. Step-level advantages ( AS ) are computed through fine-grained knowledge-state grouping. Intermediate steps across different trajectories are aligned according to their cumulative knowledge states. A three-level fallback mechanism progressively relaxes the grouping criterion when exact states are sparse, enabling robust step-level advantage estimation.
Level
Grouping key
Trigger condition
1 (exact state)
(q,Si,t)
≥M1 samples
2 (state size)
(q,∣Si,t∣)
≥M1 samples
3 (query global)
q
≥2 samples
Table 1: Three-level fallback grouping for step-level advantage estimation.
Model
Browse Comp
Browse Comp-ZH
GAIA
xBench- DS-2505
xBench- DS-2510
Advanced Agents with Proprietary Data
GLM-4.7
67.5
66.6
61.9
72.0
52.3
Kimi-K2.5
74.9
62.3
–
–
46.0
DeepSeek-V3.2
67.6
65.0
75.1
78.0
55.7
Gemini 3.1 Pro
53.6
75.9
–
86.0
–
Tongyi-DeepResearch
43.4
46.7
70.9
75.0
–
Table 2: Overall performance of different agents on five challenging deep search benchmarks.
Figure 3: Training dynamics of GRPO and EG-GRPO on 4B models, including the changes of outcome rewards, average tool call steps and evidence coverage.
Model
BC
BC-ZH
GAIA
xBenchDS-2505
xBenchDS-2510
Qwen3-4B-SFT
5.7
13.7
32.7
49.0
14.0
+ EG-GRPO(w=0)
6.7
16.7
34.7
62.7
15.7
+ EG-GRPO(w=0.25)
7.3
23.2
42.4
65.0
15.7
+ EG-GRPO(w=0.5)
8.0
23.5
45.9
65.0
19.0
+ EG-GRPO(w=0.75)
7.3
21.1
41.0
64.7
18.3
+ EG-GRPO(w=1.0)
7.0
23.2
37.2
64.2
17.0
Table 3: Performance of EG-GRPO with different w .
Model
BC
BC-ZH
GAIA
xBenchDS-2505
xBenchDS-2510
EG-GRPO (full)
8.0
23.5
45.9
65.0
19.0
EG-GRPO (level 3 only)
7.9
20.1
47.1
64.0
19.0
EG-GRPO (level 1 only)
7.9
22.8
39.4
62.0
18.3
Table 4: Performance comparison of EG-GRPO under different fallback grouping strategies.
Deep search agents operate over trajectories spanning dozens of steps, yet standard reinforcement learning provides only a single outcome reward per trajectory, which is far too sparse for effective credit assignment. On-policy self-distillation (OPSD) addresses this by using the model's own logits as dense token-level teachers, but extending it to search agents introduces a fundamental tension: the teacher, having access to privileged information such as the correct answer, produces a distribution that differs systematically from the student's exploration-based reasoning, and naive distillation causes the student to inherit this information asymmetry rather than learn better search strategies. We resolve this tension through two contributions. First, we construct Evidence Anchors, which are concise, step-level evidence snippets extracted from the web, as privileged information that captures key reasoning steps without revealing the entire answer path. Second, we propose Step-Level Self-Distilled Policy Optimization (SSPO), which converts teacher-student disagreement into step-level advantage weights within GRPO, applied exclusively to incorrect trajectories. This design decouples what to update from how much to update: the outcome reward determines the direction of policy change, while the teacher modulates its magnitude at each step. Correct trajectories are left untouched, preserving their diversity. On Qwen3-8B, SSPO consistently outperforms GRPO across BrowseComp, GAIA, and FRAMES, surpassing or matching GRPO trained with twice as many gradient steps while adding only about 5 percent overhead per step from a single additional forward pass.
Haoze Wu, Chuqiao Kuang, Tianyi Zhuang +1
The Hong Kong University of Science and Technology · Huawei Technologies Ltd.
Long-horizon search agents must make multiple sequential actions (steps) to search, retrieve, verify, and integrate evidence to reach a final answer. However, existing methods for training these agents typically treat all steps within a trajectory uniformly during both supervised fine-tuning (SFT) and reinforcement learning (RL), failing to distinguish useful actions from erroneous or redundant ones. In this paper, we propose Answer-Backtracked Credit Assignment (ABC), a fine-grained credit assignment framework for training long-horizon search agents by converting sparse trajectory-level outcomes into dense step-level supervision that rewards useful actions (even in failed trajectories) while suppressing erroneous or redundant actions. Specifically, given a potentially obscure query and its corresponding ground-truth answer, ABC first performs Answer-Backtracked Clue Recovery, which traces back from the answer to recover intermediate clues required to solve the question. It then applies Clue-Anchored Step Scoring to evaluate each search step against these clues, converting sparse binary outcome supervision into dense step-level rewards. Based on these rewards, we develop ABC-SFT, which reweights the loss of each turn, and ABC-GRPO, which uses the step-level scores as rewards in GRPO. Building on this framework, we train ABSeeker based on Qwen3.5-4B with only 8.5k examples. ABSeeker achieves 37.3% on BrowseComp and 39.1% on BrowseComp-ZH. With context management, the scores further improve to 55.3% and 52.9%, respectively, significantly outperforming same-scale (4B) agents and even matching the performance of larger ones (approximately 30B). These results demonstrate the effectiveness of answer-backtracked step-level credit assignment for training long-horizon search agents.
Reinforcement learning for deep-search agents has largely focused on trajectory-level scoring -- outcome correctness, citation-aware rewards, and evidence coverage. Yet the actions that expose supporting documents receive no targeted credit, a gap we call the reward-credit mismatch. We propose STAMP, in which a reference-based verifier judges whether each cited document supports an entity or relation in a training-time evidence graph, and first-exposure attribution traces each supported citation back to the action that first surfaced it. This step credit is injected through sign-preserving advantage modulation, which redistributes advantage across steps without changing the trajectory-level reward or the relative ranking of trajectories within each group. On BrowseComp, BrowseComp-ZH, and xbench-DS, STAMP improves the GRPO baseline by +2.0/+5.5/+3.0 points under matched SFT initialization, training data, and search tools, and composes with both outcome-only and citation-rubric base rewards. Component ablations confirm that the provenance-based credit signal and the sign-preserving advantage modulation each contribute to the gains.