acceptodds
Under review as a conference paper at ICLR 2027

Leveraging Interactions and Sequential Dependencies for Effective Credit Assignment in Search Agents

Abstract

Search agents answer questions by iteratively issuing queries, retrieving evidence, and reasoning over the results. A key research question is how to assign informative scores to intermediate search steps without relying on an additional critic model. Our case studies highlight two factors that such scores should capture: interaction effects, where multiple pieces of evidence jointly support an answer, and sequential dependencies, where earlier search results guide later queries. We propose Sequential Shapley, a fine-grained credit assignment method for multi-turn search agents that accounts for both effects. It evaluates each subset of search steps through a continuation-induced closure within the observed trajectory. The resulting coalition value models sequential dependencies through expected future contributions, while Shapley attribution captures evidence interactions by aggregating marginal contributions across coalitions. Our theoretical analysis relates Sequential Shapley to standard Shapley values and supports an approximate backward-redistribution interpretation. We integrate these step-level rewards with GRPO to obtain SPGRPO. On seven search-augmented QA benchmarks, SPGRPO improves average success rates over the strongest baseline by 2.8 and 1.4 percentage points for Qwen2.5-3B and 7B, respectively. Ablations further support the benefit of jointly modeling evidence interactions and search dependencies in this setting.

Primary area:
reinforcement learning
Keywords:
LLM Search Agents, Shapley Value, Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_Yw4pOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies step-level credit assignment for multi-step search agents. It proposes Sequential Shapley, which extends standard Shapley attribution by incorporating both interaction effects among search steps and sequential dependencies, so that early steps can receive credit for enabling useful later searches. The resulting step rewards are integrated with GRPO to form SPGRPO. Experiments on seven search-augmented QA benchmarks with Qwen2.5-3B/7B show consistent improvements over outcome-level RL and existing step-level methods。

Critical strengths

This paper proposes a reasonable design of sequential Shapley for effective credit assignment in search agent.

Theoretical analysis of sequential Shapley is provided.

Experiments are provided to justify the proposed method.

Critical weaknesses

This paper is a bit overclaim on the novelty of sequential shapley. The concept of sequential shapley was not introduced for the first time by this paper. Instead, SSVPO (Li et al., 2026) has already formulated sequential Shapley-based credit assignment for LLM reasoning. While this paper differs in how sequential structure is modeled, the introduction repeatedly describes sequential Shapley itself as a novel framework. Therefore, the prior work SSVPO should be discussed in the introduction instead of just cited in the experimental part as a compared method.

In Table 1, SSVPO should be included in comparison, especially comparisons on the 7B model.

The experimental comparisons are limitted only to Qwen2.5 models. Comparisons on newer Qwen models and other model families should be included.

Questions for authors

Could the authors empirically quantify M

max ⁡ S ∣ R ( S ) ∣ M=max S ​ ∣R(S)∣, on actual search trajectories? How does the value of M M compared to ϕ s e q ϕ seq ​ and ϕ s t a n d a r d ϕ standard ​ empirically?

How does the proposed method perform on newer Qwen models and other model families?

4 comments

Question 1. Could the authors empirically quantify M=max⁡S∣R(S)∣M=\max_S|R(S)| on actual search trajectories? How does MM compare with sequential and standard Shapley credits empirically?

Response. MM measures the largest absolute nonlinear coalition residual within a trajectory. Its mean is 0.0791, approximately half the mean absolute standard and sequential Shapley credits (0.167 and 0.158, respectively). We introduce MM as a tool for deriving a theoretical bound on Δ\Delta; the accuracy of the linear redistribution approximation is directly determined by Δ\Delta, rather than by the bound itself. The actual mean absolute per-step Δ\Delta is only 0.00560, roughly 1/30 of the mean absolute Shapley credits. These results support the linear redistribution interpretation of Theorem 2 as a close approximation on the evaluated trajectories.

We generated 600 search trajectories on the four multi-hop QA benchmarks. We study the 475 trajectories that executed at least two searches, since single-search trajectories have identically zero residual. For each trajectory, we computed both Shapley values, using p=0.2p=0.2 for Sequential Shapley.

For each trajectory, we compute the coalition residual and its maximum magnitude:

\qquad M=\max_{S\subseteq N}|R(S)|.$$ We also directly compute the remainder $\Delta$ in Theorem 2, whose bound is given in Corollary 1: $$\Delta=\phi_{\mathrm{seq}}-(I+B)\phi_{\mathrm{standard}}.$$ The table reports $\overline M$ and the mean absolute magnitudes of standard credits, sequential credits, and $\Delta$. For the per-step quantities, we average within each trajectory and then across trajectories. Numerical metrics are rounded to three significant figures. | Group | Trajectories | $\overline M$ | $\overline{\lvert\phi_{\mathrm{standard}}\rvert}$ | $\overline{\lvert\phi_{\mathrm{seq}}\rvert}$ | $\overline{\lvert\Delta\rvert}$ | | ----------------------- | -----------: | --------------: | --------------------------------------------------: | ---------------------------------------------: | --------------------------------: | | All trajectories | 475 | 0.0791 | 0.167 | 0.158 | 0.00560 | | Successful trajectories | 175 | 0.124 | 0.360 | 0.343 | 0.00973 | | Failed trajectories | 300 | 0.0531 | 0.0539 | 0.0495 | 0.00320 | | HotpotQA | 103 | 0.107 | 0.161 | 0.150 | 0.00761 | | 2WikiMultihopQA | 134 | 0.0885 | 0.150 | 0.141 | 0.00607 | | MuSiQue | 121 | 0.0242 | 0.139 | 0.136 | 0.00136 | | Bamboogle | 117 | 0.101 | 0.219 | 0.206 | 0.00769 |

Question 2. How does the proposed method perform on newer Qwen models and other model families?

Response. SPGRPO achieves the highest average performance among the compared methods on both Qwen3-4B (48.1) and Llama-3.2-3B (47.8). These scores improve over standard Shapley by 0.8 and 1.6 points, and over GRPO by 1.6 and 3.1 points, respectively. SPGRPO outperforms standard Shapley on six of the seven datasets for each model, supporting the effectiveness of sequential modeling on both a newer Qwen model and a different model family.

To assess generalization across models, we extended our ablation study to these two backbones, using standard Shapley as the direct ablation of sequential dependencies and GRPO and IGPO as additional outcome-level and step-level reward baselines, respectively. The detailed results are reported below.

Method (Qwen3-4B)NQTriviaQAPopQAHotpotQAWikiMuSiQueBamboogleAvg.
GRPO43.963.346.742.140.316.772.246.5
IGPO44.062.745.838.942.117.271.446.0
Standard Shapley45.663.847.642.843.015.972.647.3
SSVPO46.163.546.943.243.917.071.447.4
SPGRPO46.564.448.243.945.017.970.648.1
Method (Llama-3.2-3B)NQTriviaQAPopQAHotpotQAWikiMuSiQueBamboogleAvg.
GRPO46.862.447.638.436.013.568.544.7
IGPO46.063.145.841.240.315.867.345.6
Standard Shapley47.362.948.539.740.216.368.546.2
SSVPO47.262.547.341.238.716.669.046.1
SPGRPO48.163.448.343.342.617.671.447.8

Update: We have added SSVPO results on Qwen3-4B and Llama-3.2-3B to the tables above.

Weakness 1&2. The novelty of sequential Shapley is overclaimed. SSVPO (Li et al., 2026) already formulated sequential Shapley-based credit assignment for LLM reasoning, and it should be discussed in the introduction instead of only being cited as a compared method.

Response. We have expanded the Introduction to discuss SSVPO (Li et al., 2026). We would like to clarify that although both methods use Shapley-based credit assignment and share the name “Sequential Shapley,” they differ fundamentally in motivation and methodology, modeling different aspects of sequential reasoning.

SSVPO evaluates a step's contribution across reordered reasoning chains through an insertion MDP. Expressed as a permutation-averaged coalition value, this corresponds to

=\mathbb E_{\pi\sim\mathrm{Unif}(\Pi(S))}[V(\pi(S))],$$ where $\Pi(S)$ denotes the permutations of the steps in $S$. Our method instead constructs $$\widetilde V_{\mathrm{SPGRPO}}(S)=\sum_C P(C\mid S)V(S\cup C),$$ where $P(C\mid S)$ models how retaining preceding searches changes the likelihood of subsequent continuations. These constructions reflect different motivations. SSVPO addresses the dependence of a step's evaluated contribution on the ordering of the input chain and its insertion position, averaging over these alternatives to obtain fair credit beyond any single arrangement. Our motivation is to use sequential dependencies as a basis for credit redistribution: an earlier search should receive credit for increasing the likelihood of useful later evidence, even when its own evidence has little direct answer utility. Through $P(C\mid S)$, we explicitly model this enabling effect and redistribute credit to the preceding searches that facilitate it. Our contribution is this conditional-continuation formulation and its credit-redistribution interpretation.

Thank you for the detailed rebuttal and additional experiments. Most of my concerns are solved.

I keep my original rating of 3 and lean towards acceptance.

Reviewer_1mZMOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Sequential Shapley for fine-grained credit assignment in multi-turn search agents, accounting for evidence interactions and sequential dependencies. Integrated with GRPO, SPGRPO improves performance across seven QA benchmarks.

Critical strengths
  1. Sequential Shapley offers a meaningful formulation for jointly modeling evidence interactions and temporal dependencies in search-agent credit assignment.

  2. Experiments across seven QA benchmarks show consistent average gains, supported by ablations against standard Shapley and IGPO.

Critical weaknesses
  1. The continuation model relies on length-normalized action likelihoods rather than actual continuation probabilities. Table 5 reports substantial calibration errors, weakening the interpretation of sequential credit.

  2. The theoretical backward-redistribution interpretation relies on assumptions not empirically verified, while the incremental gains over standard Shapley remain relatively modest.

Questions for authors

(1) In Eq. (2) and Table 5, continuation probabilities are approximated using token likelihoods, yet calibration errors remain substantial (MAE up to 0.185). How sensitive are the learned credits and final performance to these estimation errors?

(2) In Sec. 3.3, coalition evaluation preserves selected retrieved evidence from the original trajectory. Such evidence may not be obtainable without preceding searches. How does the method handle these potentially infeasible counterfactual contexts?

(3) The backward-redistribution interpretation in Theorem 2 and Appendix E.5 relies on a monotonicity assumption. Is this assumption satisfied by actual search trajectories? Can the authors measure how frequently it is violated?

(4) Table 2 attributes a 1.2-point average gain over standard Shapley to sequential modeling. Is this improvement statistically significant across independent runs? Why is the corresponding ablation absent for the 7B model?

(5) Table 1 combines reproduced baseline results with numbers from previous studies. Were all methods evaluated using identical retrieval corpora, search budgets, and evaluation protocols? Could these differences affect the reported ranking?

(6) Appendix C assigns the final answer a residual reward and normalizes search and answer advantages separately. How much of the improvement comes from this reward design rather than Sequential Shapley itself? Can a controlled ablation isolate these effects?

6 comments

Question 1. In Eq. (2) and Table 5, continuation probabilities are approximated using token likelihoods, yet calibration errors remain substantial (MAE up to 0.185). How sensitive are the learned credits and final performance to these estimation errors?

Response. MAE depends on the scaling factor pp used in our method. The global MAE is 0.0750 at the training setting p=0.2p=0.2 and remains below 0.1 for p∈0.1,0.2,0.5p\in\\{0.1,0.2,0.5\\}. We further observe that the changes in MAE and RMSE correspond to the performance trend in Figure 3: as pp increases, the errors first decrease and then increase, with p=0.2p=0.2 achieving both the lowest MAE and RMSE and the highest average model performance. At p=0.5p=0.5, global MAE and model performance remain close to their respective values at the standard Shapley setting (p=0p=0). Increasing pp further to 0.80.8 substantially increases the estimation errors and is accompanied by a decline in model performance.

The initial calculation in Table 5 used geometrically averaged token likelihoods without the scaling factor pp. Taking the geometric mean increases the numerical values, which can lead to overestimation of continuation probabilities without the scaling factor. Since MAE and RMSE measure numerical differences rather than agreement in rankings, this scale mismatch contributes to the large reported errors. We therefore reevaluated calibration using recurrence frequencies estimated from 256 independent re-rollouts per context on the same 100 HotpotQA trajectories. For each evaluated context induced by SS, we performed 256 independent re-rollouts and recorded the recurrence frequency of each continuation. We then compared P(C∣S)P(C\mid S) against these empirical frequencies for p∈0.0,0.1,0.2,0.5,0.8,1.0p\in\\{0.0,0.1,0.2,0.5,0.8,1.0\\}, including p=1.0p=1.0 as the unscaled reference. The results are reported below.

ppGlobal MAEWithin-trajectory MAEGlobal RMSEWithin-trajectory RMSE
0.00.08700.1210.1510.159
0.10.07510.1030.1340.136
0.20.07500.09950.1260.129
0.50.09640.1190.1420.152
0.80.1370.1650.2020.213
1.00.1760.2190.2650.283

Values are rounded to three significant figures. The results at p=1.0p=1.0 differ from the corresponding functional-matching results in Table 5 because we increased the number of samples per context.

Comparing these results with Figure 3 in our paper reveals a consistent pattern: lower calibration errors generally correspond to better downstream performance. Although downstream performance is influenced by many factors, these findings suggest a link between the accuracy of sequential dependency modeling and downstream performance, providing an additional basis for selecting pp. We thank the reviewer for the valuable insight that led us to this finding.

Question 2. In Sec. 3.3, coalition evaluation preserves selected retrieved evidence from the original trajectory. Such evidence may not be obtainable without preceding searches. How does the method handle these potentially infeasible counterfactual contexts?

Response. We deliberately retain such coalitions and account for their obtainability through credit assignment rather than imposing feasibility constraints during coalition evaluation. Specifically, we use P(C∣S)P(C\mid S) to transform coalition values before computing Shapley credits. Here, SS denotes the retained subset of preceding searches and CC the specified coalition. When retaining a preceding search makes useful subsequent evidence more likely, the transformation allows that search to receive credit for enabling the later evidence.

For example, when asked where a film’s director was born, the agent first identifies the director in x1x_1 and then uses that name to search for the director’s birthplace in x2x_2. A high V({x2})V(\{x_2\}) reflects the direct usefulness of the birthplace evidence, and assigning greater credit to more informative steps is consistent with our objective. But credit assignment should also account for x1x_1’s role in enabling the query that retrieves this evidence. Proposition 1 in Appendix D.2 formalizes this enabling effect: in the two-step setting where only the second step contributes direct evidence value, namely V(T)=v0+d1x2∈TV(T)=v_0+d\mathbf{1}_{x_2\in T} with d>0d>0, standard Shapley assigns ϕ1std=0\phi^{\mathrm{std}}_1=0 and ϕ2std=d\phi^{\mathrm{std}}_2=d, whereas Sequential Shapley gives

\phi^{\mathrm{seq}}_1 = \frac d2(1-\alpha)(\gamma-\beta),\quad \phi^{\mathrm{seq}}_2 = \frac d2\left[2-(1+\alpha)\gamma-(1-\alpha)\beta\right]. \end{aligned}$$ where $\alpha=\rho_1(\varnothing)$, $\beta=\rho_2(\varnothing)$, and $\gamma=\rho_2(\{x_1\})$, with $\rho_k$ denoting the model's conditional generation probabilities of step $k$. When $\alpha<1$ and $\gamma>\beta$, Sequential Shapley redistributes credit of $\frac{d}{2}(1-\alpha)(\gamma-\beta)$ from $x_2$ back to $x_1$ since $x_1$ increases the probability of generating $x_2$ from $\beta$ to $\gamma$, even though $x_1$ provides no direct answer evidence. Therefore, we evaluate $V(\{x_2\})$ using the retained evidence, without imposing a hard obtainability constraint on the coalition. We then redistribute credit to reflect how preceding searches affect the obtainability of subsequent evidence.

Question 3. The backward-redistribution interpretation in Theorem 2 and Appendix E.5 relies on a monotonicity assumption. Is this assumption satisfied by actual search trajectories? Can the authors measure how frequently it is violated?

Response. We empirically evaluated this assumption: 86.7% of the tested comparisons satisfy monotonicity, and 95.8% of the backward-redistribution coefficients are positive. We analyzed the 100 original trajectories generated from the 100 questions used in our response to the first concern: 59 trajectories contain two search steps, 23 contain three, and 18 contain four, excluding the final answer step. We retained the same setting of p=0.2p=0.2.

For each earlier step i<ji<j and retained context T⊆1,…,j−1∖{i}T\subseteq\\{1,\ldots,j-1\\}\setminus\{i\}, we computed the modeled inclusion probability fj(T)=∑CP(C∣T)1j∈Cf_j(T)=\sum_C P(C\mid T)\mathbf{1}_{j\in C} and compared fj(T∪{i})f_j(T\cup\{i\}) with fj(T)f_j(T). A violation occurs when retaining search ii reduces the probability of including step jj, i.e., fj(T∪{i})<fj(T)f_j(T\cup\{i\})<f_j(T). This yielded 480 comparisons: 416 showed an increase, while 64 (13.3%) violated monotonicity.

We also directly computed the redistribution matrix I+BI+B in Theorem 2. Among its backward coefficients (i<ji<j), 226 of 236 were positive, and 10 (4.24%) were negative. At the trajectory level, 92/100 trajectories (92%) had non-negative entries throughout the upper triangle of I+BI+B. These results show that backward redistribution is the predominant pattern in the linear credit-redistribution component of Sequential Shapley.


Question 4. Table 2 attributes a 1.2-point average gain over standard Shapley to sequential modeling. Is this improvement statistically significant across independent runs? Why is the corresponding ablation absent for the 7B model?

Response. We have now extended the Shapley ablation to the 7B model, with the results shown below. SPGRPO achieves an average score of 48.6, improving over standard Shapley (47.6) and SSVPO (47.7) by 1.0 and 0.9 points, respectively. At the 3B scale, SPGRPO outperforms both Shapley-based baselines on all evaluated datasets. At the 7B scale, it also outperforms both baselines on six of the seven datasets, except for Wiki. These results provide consistent empirical support for the benefit of sequential modeling across both model scales.

Method (7B)NQTriviaQAPopQAHotpotQAWikiMuSiQueBamboogleAvg.
GRPO44.161.745.240.942.314.268.145.2
IGPO44.060.145.442.942.516.870.246.0
Standard Shapley46.264.145.044.043.718.971.447.6
SSVPO46.262.846.943.245.419.070.247.7
SPGRPO47.264.647.344.643.921.071.748.6

We further examined whether the improvement generalizes across model backbones. Beyond Qwen2.5-3B/7B, we repeated the ablation on Qwen3-4B and Llama-3.2-3B. Sequential Shapley improves average performance over standard Shapley by 0.8 and 1.6 points, respectively, with gains on six of the seven datasets for each model. These results provide additional evidence that the benefit of sequential modeling is consistent. If you are interested in these results, please refer to our response to Reviewer Yw4p for further details.

Reviewer_TvxeOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes a method for optimizing search agents using reinforcement learning based on the Shapely attribution-based method. Shapely assumes that the actions are unordered (i.e., a set), while search agents often take actions sequentially, so the authors expand Shapely and propose Sequential Shapely for optimizing search agents, such as Search-R1. The method is evaluated on seven QA benchmarks and performs well across two model sizes.

Critical strengths
  • The propose sequential shapely method is novel and interesting.
  • The obtained results are encouraging.
  • The method is sound with some theoretical justifications.
Critical weaknesses
  • The presentation can be improved. For example, from the introduction it is not clear what are the basic ideas behind sequential shapely. The figures (such as Fig 2) are overly crowded and unnecessarily confusing. The citation format is incorrect in many cases, for example, IGPO Wang et al. (2025) is wrong and should be changed to IGPO (Wang et al. 2025). Use \citep{}.

  • The model performance beyond GRPO (for example PPO) is unclear.

  • The model performance beyond Qwen models is unclear.

Questions for authors

None.

2 comments

Weakness 1. The presentation can be improved. For example, from the introduction it is not clear what are the basic ideas behind sequential shapely. The figures (such as Fig 2) are overly crowded and unnecessarily confusing. The citation format is incorrect in many cases, for example, IGPO Wang et al. (2025) is wrong and should be changed to IGPO (Wang et al. 2025). Use \citep{}.

Response. We have clarified the basic idea of Sequential Shapley in the Introduction and corrected the citation formatting. The revised explanation emphasizes that a search step contributes both through the evidence it retrieves and through its role in enabling useful subsequent searches. We model the latter through conditional continuation probabilities and use them to redistribute credit to preceding steps that facilitate later evidence. We have also corrected the parenthetical citations using \citep{}, including the citation accompanying IGPO. We have revised Figure 2 to make it simpler and clearer. Specifically, we simplified the illustration of Stage 1 and removed unnecessary formulas. We also improved the layout and alignment of the framework diagram to make it more organized and easier to follow.


Weakness 2. The model performance beyond GRPO (for example PPO) is unclear.

Response. SPGRPO achieves the highest average score (44.9) in our expanded comparison on Qwen2.5-3B-Instruct, outperforming PPO (41.8) and GSPO (41.8) by 3.1 points, RLOO (40.9) by 4.0 points, and GRPO (40.6) by 4.3 points. These results extend the comparison beyond GRPO and demonstrate consistent improvements over PPO, RLOO, and GSPO, as detailed below.

Method (Qwen2.5-3B-Instruct)NQTriviaQAPopQAHotpotQAWikiMuSiQueBamboogleAvg.
GRPO39.257.842.434.434.510.765.340.6
GSPO41.658.943.536.337.111.464.141.8
PPO41.859.944.136.636.012.561.741.8
RLOO38.458.543.235.335.812.462.940.9
SPGRPO (ours)44.661.446.639.140.214.568.044.9

Weakness 3. The model performance beyond Qwen models is unclear.

Response. SPGRPO achieves the highest average score among the compared methods on Llama-3.2-3B (47.8), improving over standard Shapley by 1.6 points and GRPO by 3.1 points. We also evaluated Qwen3-4B, where SPGRPO achieves an average score of 48.1, improving over standard Shapley by 0.8 points and GRPO by 1.6 points. Together, these results show consistent average improvements on both a different model family and a newer Qwen model.

We extended our ablation study to both models, using standard Shapley as the direct ablation of sequential dependencies and GRPO and IGPO as additional outcome-level and step-level reward baselines, respectively.

Method (Llama-3.2-3B)NQTriviaQAPopQAHotpotQAWikiMuSiQueBamboogleAvg.
GRPO46.862.447.638.436.013.568.544.7
IGPO46.063.145.841.240.315.867.345.6
Standard Shapley47.362.948.539.740.216.368.546.2
SSVPO47.262.547.341.238.716.669.046.1
SPGRPO48.163.448.343.342.617.671.447.8

The corresponding results on Qwen3-4B are shown below.

Method (Qwen3-4B)NQTriviaQAPopQAHotpotQAWikiMuSiQueBamboogleAvg.
GRPO43.963.346.742.140.316.772.246.5
IGPO44.062.745.838.942.117.271.446.0
Standard Shapley45.663.847.642.843.015.972.647.3
SSVPO46.163.546.943.243.917.071.447.4
SPGRPO46.564.448.243.945.017.970.648.1

Update: We have added SSVPO results on Qwen3-4B and Llama-3.2-3B to the tables above.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.