Evidence-Based Credit Assignment for Search-Augmented Language Models
Authors: Wen Wang, Jindong Wang, Jiahua Bao, Tu Yongsiqi, Yihao Liu, Junwei He, Wenkui Fan
Organizations: University of the Chinese Academy of Sciences · Tencent · Harbin Institute of Technology · Renmin University of China · Peking University · Beijing Institute of Technology
Reinforcement learning from terminal answer rewards enables search-augmented language models to interleave reasoning and retrieval without step-level annotations, yet outcome supervision assigns identical credit to every search in a trajectory regardless of whether it retrieved useful information. This limitation is especially severe when all sampled rollouts for a question fail, collapsing group-centered outcome advantages to zero even when trajectories gather markedly different evidence. We present Evidence-based Credit Assignment (ECA), which augments terminal outcome rewards with a training-only auxiliary signal measuring how retrieved documents improve the likelihood of a reference answer. Rather than scoring the full dialogue prefix, ECA queries a frozen snapshot of the current policy under an evidence-only prompt containing solely the question and the deduplicated documents observed so far, isolating the utility of retrieved passages from surface variations in generated thoughts or search queries. Within this framework, we compare two return formulations, ECA-Step (which accumulates step-clipped potential increments) and ECA-Horizon (which preserves the telescoping horizon gain in potential), paired with cross-fold group normalization, novelty gating, and search-local token assignment. Across seven Search QA benchmarks, ECA-Horizon improves strict macro exact match over an outcome-only GRPO baseline by 1.03 and 4.80 percentage points on Qwen2.5-3B- and 7B-Instruct, respectively, outperforming both RLOO and GiGPO. Zero-shot evaluation on MultiHop-RAG further demonstrates strong transfer to multi-hop inference queries.
Figures & tables
Figure 1: ECA can credit useful searches in all-failure groups while gating repeated evidence (illustrative example).
Figure 2: Overview of Evidence-based Credit Assignment (ECA). (a) During rollout, the policy interleaves reasoning and search queries to accumulate documents, while terminal outcome credit Aout applies uniformly to all generated tokens. (b) During training, a frozen snapshot of the current policy scores the canonical reference answer y∗ given only the question x and deduplicated documents D , excluding generated thoughts and queries. (c) Step-wise potentials are aggregated via ECA-Step or ECA-Horizon, standardized via cross-fold normalization, clipped, and passed through a novelty gate before being added to search-action tokens.
Figure 3: Comparison of ECA-Step and ECA-Horizon return constructions on an illustrative trajectory with potentials (−8,−4,−7,−7) and step-wise increments (+4,−3,0) ( c=2,H=3 ). (a) The first search raises the potential from −8 to −4 , followed by a noisy second search ( −3 ) and a redundant third search ( 0 ). (b) Clipping each step to [−2,2] under ECA-Step saturates the +4 gain and −3 drop to +2 and −2 , yielding zero return at search 1 ( Ui,1S=0 ). ECA-Horizon preserves the horizon gain from D0 to D3 , yielding Ui,1H=(−7−(−8))/6=1/6 before the shared normalization and gating stages.
Method
NQ
TriviaQA
PopQA
Hotpot
2Wiki
MuSiQue
Bamboogle
Avg.
Qwen2.5-3B-Instruct
R1-Instruct †
27.0
53.7
19.9
23.7
29.2
7.2
29.3
27.1
Search-R1 †
34.1
54.5
37.8
32.4
31.9
10.3
26.4
32.5
ZeroSearch †
41.4
57.4
44.8
27.4
30.0
9.8
11.1
31.7
StepSearch †
–
–
–
34.5
32.0
17.4
34.4
–
TIPS †
43.46
58.80
42.76
31.40
29.25
8.73
20.80
33.60
Table 1: Question-level exact match (EM, %) across the seven-dataset Search QA benchmark, with macro average (Avg., Eq. 10 ). † denotes published reference results from Feng et al. [4] (Table 2) and Xie et al. [28] (Table 1). Best and second-best scores per column within each model scale are shown in bold and underlined .
3B variant
EM
F1
GRPO
37.19
45.87
ECA-Step
38.05
46.76
ECA-Horizon
38.22
45.80
ECA-Step (query only)
35.27
43.56
ECA-Step (broadcast)
36.42
44.96
Table 2: Credit-assignment ablations on Qwen2.5-3B-Instruct ( λ=0.1 ). EM and token F1 are macro averages (%) across the seven Search QA datasets. Best and second-best scores in each column are shown in bold and underlined .
Figure 4: Episode-level duplicate search query rate (%) on Qwen2.5-3B-Instruct across (a) the seven-dataset macro average and (b) individual multi-hop QA benchmarks. All RL-trained policies execute the full budget of 3.00 searches per episode (vs. 2.28 for the Base agent); pairing search-local evidence credit with novelty gating suppresses the redundant repeat queries induced by outcome-only RL.
Method
3B
7B
Base
59.93
76.84
GRPO
80.02
82.84
RLOO
83.46
88.11
GiGPO (w/std)
65.93
87.25
ECA-Step
84.68
88.85
ECA-Horizon
82.48
89.22
Table 3: Zero-shot transfer on MultiHop-RAG Inference-816 (EM, %), evaluated under the shared search agent and TreeHop scoring protocol. Best and second-best scores in each column are shown in bold and underlined .
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Method
EM (%)
Δ EM (pp)
Actions
Searches
Dup. Query (%)
Tokens
Invalid (%)
Qwen2.5-3B-Instruct
Base agent
21.75
+0.00
3.36
2.28
23.86
104.2
10.62
GRPO
37.19
+15.44
4.00
3.00
42.40
178.9
0.00
RLOO
35.43
+13.68
4.00
3.00
54.07
120.8
0.02
ECA-Step
38.05
+16.29
4.00
3.00
30.26
257.1
0.07
ECA-Horizon
38.22
+16.46
4.00
3.00
24.84
200.9
0.14
Appendix
Table S1 : Agent interaction statistics before and after RL across the seven Search QA benchmarks (unweighted macro averages over 51,713 questions). Δ EM is measured relative to the same-size Base agent. Actions count all model turns (including invalid actions and the final answer); Searches count executed retrieval calls; Dup. Query is the percentage of episodes containing at least one repeated search query; Tokens count generated policy tokens (excluding prompts and retrieved text); and Invalid is the percentage of episodes with at least one malformed action.
Model
Variant
Wrong → correct
Correct → wrong
Both correct
Both wrong
Δ acc. (pp)
3B
ECA-Step
12,115 (23.43)
2,081 (4.02)
10,186 (19.70)
27,331 (52.85)
+19.40
3B
ECA-Horizon
12,340 (23.86)
2,166 (4.19)
10,101 (19.53)
27,106 (52.42)
+19.67
7B
ECA-Step
8,473 (16.38)
2,320 (4.49)
15,275 (29.54)
25,645 (49.59)
+11.90
7B
ECA-Horizon
8,861 (17.13)
2,158 (4.17)
15,437 (29.85)
25,257 (48.84)
+12.96
Appendix
Table S2 : Paired question-level correctness transitions from the untrained Base agent to ECA across all 51,713 pooled test questions (count and percentage of total questions). Δ acc. denotes the net change in pooled accuracy, which weights all questions equally rather than weighting the seven datasets equally.
Hyperparameter
Value
Training pool / development set
8,192 / 1,024
Questions per update / rollout group G
32 / 8
Total optimizer updates
256
Optimizer / learning rate
AdamW / 10−6
Max actions / search budget H
4 / 3
Max generated tokens per action
512
Appendix
Table S3 : Shared training and evaluation configuration for ECA. Zero-shot transfer on MultiHop-RAG uses a 16,384-token policy context.
Method
Intermediate signal
Additional source or computation
Distinction from ECA
GiGPO [ 4 ]
Relative returns at repeated/similar states
State grouping across sampled trajectories
Groups outcomes, rather than scoring answer likelihood from document sets.
IGPO [ 23 ]
Mean answer log-likelihood change on rollout prefixes
Current-policy teacher forcing; separate process/outcome normalization
Normalizes immediate rewards before discounted accumulation; ECA constructs returns before cross-fold normalization.
TIPS [ 28 ]
Answer-likelihood potential differences
Frozen/refreshed teacher on dialogue context
Uses dialogue-context potentials; ECA restricts its readout to questions and documents and applies a search-local mask.
StepSearch [ 32 ]
Gold-document coverage and repetition penalties
Sub-question/search supervision and evidence references
ECA uses answer labels without gold supporting-passage annotations.
PiCA [ 15 ]
History-dependent success-potential progress
Pivot-annotated trajectories; trained reward model
ECA reuses the current actor for a document-only readout.
KnowGPO [ 3 ]
Gains in satisfied atomic knowledge conditions
Constructed conditions and LLM verification
ECA requires no external LLM verifier or constructed atomic conditions, relying only on document-ID deduplication and current-policy answer scoring.
Appendix
Table S4 : Mechanism-level comparison of intermediate credit assignment and group optimization methods for search agents.
Question: Where is the country with ISO code ISO 3166-2:CV located? Gold: central Atlantic Ocean. ID: dev_88 .
GRPO
ECA-Horizon
1. Where is the country with ISO code ISO 3166-2:CV located 2. Where is the country with ISO code ISO 3166-2:CV located 3. Where is the country with ISO code ISO 3166-2:CV located
1. Where is the country with ISO code ISO 3166-2 CV located 2. Cabo Verde location 3. Cabo Verde location map
Search 1: ISO 3166-2:CV (passage 18933183). “ISO 3166-2:CV is the entry for Cabo Verde in ISO 3166-2”
Search 1: ISO 3166-2:CV (passage 18933183). “ISO 3166-2:CV is the entry for Cabo Verde in ISO 3166-2” Search 2: Cape Verde (passage 5648183). “an island country spanning an archipelago of 10 volcanic islands in the central Atlantic Ocean.”
New passage IDs per search: 3 / 0 / 0
New passage IDs per search: 3 / 3 / 1
Final answer: Cabo Verde ( EM=0 )
Final answer: central Atlantic Ocean ( EM=1 )
Appendix
Table S5 : Following a bridge entity (3B, MuSiQue). Both models retrieve the country name. GRPO repeats the initial query and returns this intermediate entity; ECA-Horizon follows it to a passage stating the country’s location.
Question: For which club did the winner of the 2007 Ballon d’Or play for in 2012? Gold: Real Madrid. ID: test_104 .
GRPO
ECA-Horizon
1. 2007 Ballon d’Or winner club 2012 2. Lionel Messi club 2012 3. Lionel Messi club 2012
1. For which club did the winner of the 2007 Ballon d’Or play for in 2012 2. 2007 Ballon d’Or Kaká club 2012 3. Kaká 2012 club
Search 1: 2012 FIFA Ballon d’Or (passage 17186262). “The odds-on favourite Lionel Messi won the award.”
Search 1: 2007 Ballon d’Or (passage 20994564). “was awarded to Kaká.” Search 3: Kaká (passage 13277486). “In 2011–12, Real Madrid won La Liga with a record 100 points that year, with Kaká providing nine assists”
New passage IDs per search: 3 / 3 / 0
New passage IDs per search: 3 / 3 / 2
Final answer: Barcelona ( EM=0 )
Final answer: Real Madrid ( EM=1 )
Appendix
Table S6 : Resolving the award year before the club year (3B, Bamboogle). GRPO follows a retrieved passage about the 2012 award to Messi. ECA-Horizon retrieves the 2007 winner, Kaká, and a passage linking him to Real Madrid in 2011–12.
Question: Who lived longer, Horace Lawson Hunley or Ernst Ziehm? Gold: Ernst Ziehm. ID: dev_12551 .
GRPO
ECA-Horizon
1. Horace Lawson Hunley lifespan Ernst Ziehm lifespan 2. Horace Lawson Hunley lifespan Ernst Ziehm lifespan 3. Horace Lawson Hunley death Ernst Ziehm death
1. Horace Lawson Hunley 2. Ernst Ziehm 3. Horace Lawson Hunley died
Search 1: Horace Lawson Hunley (passage 14541340). “June 20, 1823 in Sumner County, Tennessee – October 15, 1863 off Charleston, South Carolina” Search 2: Ernst Ziehm (passage 7050528). “1 May 1867 – 7 July 1962”
New passage IDs per search: 3 / 0 / 3
New passage IDs per search: 3 / 3 / 1
Final answer: Horace Lawson Hunley ( EM=0 )
Final answer: Ernst Ziehm ( EM=1 )
Appendix
Table S7 : Separating two entity searches (7B, 2WikiMultiHopQA). GRPO’s repeated joint query retrieves an unrelated longevity record. ECA-Horizon retrieves both biographies; their returned dates support the correct lifespan comparison.