https://arxiv.org/pdf/2607.13988 Good RL work from Microsoft research that manages to improve the Qwen3 small MoE better than other approaches, focusing here on crafting turn-level signals for long horizon trajectories

The main idea comes from TD-Learning, but they do so without using a trained value model.

Their approach, instead, uses at state S_k the probability for the gold answer to be output to compute an estimate of the value function. This allows them to have a value drift positive if the new observation is more likely to converge to the objective, and negative otherwise.

To stabilize for delayed tool effect (like if you search and click for something, the search should get quite the credit for it) the authors make use of a truncated K-step TD backup instead, aggregating with a discount hyperparameter.

If the K-step reaches the end of the trajectory, the credit also takes into it the verifiable reward signal, ie the GRPO advantage multiplied by a power of the discount and another hyperparameter to control its impact.

Main GRPO advantage remains computed, but now is taken into account with the per step credit computation, each multiplied by a parameter that assigns their strength in the sum. This gives a mixed per-step advantage, changed to a mixed per-token advantage by making it so that the credit of the token is the credit of the step it belongs to.

Once this is all done, the clipped GRPO objective is optimized with this modified advantage.

And to great result it is! Beats basically every RL method on the evaluated agentic benchmarks. All hyperparameters are within the work itself.

Learning dynamics are pretty solid, and ablations do validate their choices. Nice work, hope it holds up for more general agentic!

TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents

Source: https://arxiv.org/html/2607.13988 Leitian Tao1,2Baolin Peng2Wenlin Yao2Tao Ge2Hao Cheng2Mike Hang Wang2 Jianfeng Gao2Sharon Li1 1University of Wisconsin–Madison2Microsoft Research

Abstract

Multi-turn agents solve complex tasks through extended sequences of tool interactions before producing a final answer, making credit assignment a fundamental challenge during post-training. Outcome rewards provide reliable supervision for short-horizon reasoning, but become sparse and high-variance as trajectories grow to tens or hundreds of tool calls. They can also be misleading: a failed rollout may contain many useful actions that move the agent closer to the goal, yet outcome-only training assigns them the same negative advantage as the eventual mistake. We proposeTRACE(Turn-level Reward Assignment via Credit Estimation), a dense credit-assignment method for agentic reinforcement learning.TRACErepresents rollouts as state transitions at tool-call boundaries, obtains gold-answer log-probabilities from a frozen reference model, transforms them into log-ratio state values, and derives per-action rewards as Temporal-Difference changes in those values. This requires no additional critic or process-label training, and its one-step log-ratio TD component telescopes across redundant tool calls. On long-horizon complex search,TRACEsubstantially improves base-model tool-use ability using pure RL, without a cold-start supervised fine-tuning stage, an agentic mid-training stage, or training on live-web data. On the closed-web BrowseComp-Plus benchmark, it raises Qwen3-4B from7.27.2to35.635.6and Qwen3-30B-A3B from8.48.4to42.642.6. The learned search behavior also transfers to open-web benchmarks, and the learning curves show earlier improvement and faster convergence during RL training.

1Introduction

Large language model (LLM) agents increasingly solve complex tasks by reasoning and acting through many interactions with external environments, including web navigation, software engineering, and general computer use[Yaoet al.,2023, Schicket al.,2023, Nakanoet al.,2021, Yaoet al.,2022, Denget al.,2023, Zhouet al.,2024, Jimenezet al.,2024, Xieet al.,2024]. Reinforcement learning with verifiable rewards (RLVR) has been effective for single-turn reasoning tasks such as mathematics and coding, where a deterministic checker can evaluate the final answer and provide a clean outcome reward[Shaoet al.,2024, Guoet al.,2025]. Applying the same idea to agents is appealing but insufficient: an agentic rollout may contain dozens of search, open, find, code, or other tool-use decisions before the final answer is verified. A single terminal reward says whether the trajectory succeeded, but it does not reveal which intermediate actions gathered necessary evidence, which were redundant, or which derailed the agent.

Dense turn-level rewards are therefore desirable, but obtaining them is challenging because partial progress in agent trajectories is not directly observed. As illustrated in Figure1, a failed rollout can begin with useful search and open actions that make the answer easier to infer, while a successful rollout can contain redundant searches or accidental openings that do not contribute to the final answer. Outcome-only training assigns the same trajectory-level advantage to all of these turns, under-crediting productive exploration, over-crediting irrelevant actions, and increasing gradient variance as horizons grow[Sutton and Barto,2018, Arjona-Medinaet al.,2019, Yeet al.,2025]. Prior work on process supervision offers finer feedback, but typically requires step-level labels, a strong LLM judge to score intermediate behavior[Zhenget al.,2023], or a trained process reward model whose scores may drift away from final-answer correctness[Uesatoet al.,2022, Lightmanet al.,2023, Wanget al.,2024a, Setluret al.,2024, Yuanet al.,2024]. This raises the central question of this work:how can we identify the tool calls that actually move a long-horizon agent toward the answer, and turn that signal into dense rewards without relying on step labels, a strong judge, or a trained process reward model?

We proposeTRACE(Turn-levelRewardAssignment viaCreditEstimation), a critic-free credit-assignment framework that keeps the final verifier as the anchor while adding dense credit at tool-call boundaries. The key idea is to use a frozen reference model not as a judge, but as a stable probe of whether each trajectory prefix makes the gold answer more predictable.TRACErepresents a rollout as state transitions at tool-call boundaries, scores each prefix by the reference model’s gold-answer log-probability, and converts the score into a log-ratio state value measuring progress toward the answer. It then assigns turn rewards using temporal-difference (TD) changes between adjacent values: a tool call receives positive credit when its returned observation increases answer predictability, near-zero credit when it adds no useful evidence, and negative credit when it moves the trajectory away from the answer. Because the one-step TD credits telescope, redundant intermediate turns cannot inflate this component, while the cumulative credit remains aligned with the final reference-model state. The resulting rewards combine this dense TD signal with the standard outcome-level advantage[Sutton,1988], preserving verifiable success as the final training target while distinguishing which turns deserve credit.

Figure 1:Credit assignment at tool-call boundaries in a search trajectory.The figure illustrates a long-horizon search rollout decomposed into tool-call turns. Early search and open actions can add task-relevant evidence to the transcript even when a later branch leads to an incorrect final answer. Outcome-reward training attaches one trajectory-level advantage to all actions in the rollout, whereasTRACEcomputes prefix values at tool boundaries and assigns turn credit from adjacent value changes.We evaluateTRACEon long-horizon complex search, a setting where agents must learn to interact with an environment, explore through multiple tool calls, and refine later actions from earlier observations. Because common multi-hop benchmarks can be solved by strong agents in only a few turns[Yanget al.,2018], we train on deeper synthetic search questions and evaluate on both closed-web and open-web deep-research benchmarks. Our recipe is pure RL: it uses outcome-level and turn-level rewards directly, without a cold-start supervised fine-tuning stage, an agentic mid-training stage, live-web training data, a strong judging model, or a trained process reward model. Despite this minimal supervision,TRACEsubstantially improves base-model tool use in both closed-web and open-web settings. On closed-web BrowseComp-Plus[Chenet al.,2025c], it raises Qwen3-4B from7.27.2to35.635.6and Qwen3-30B-A3B from8.48.4to42.642.6. The learned behavior also transfers to open-web retrieval, with the 30B-A3B agent reaching12.912.9on BrowseComp,52.052.0on GAIA, and45.045.0on xbench-DeepSearch. In addition to final performance, the training curves show thatTRACEstarts improving earlier and converges faster, indicating that turn-level credit makes long-horizon tool use easier to learn from pure RL. These results show that verifier-anchored turn-level credit can teach base models to explore, interact with the environment, and refine tool use for complex long-horizon tasks, while remaining independent of expensive process supervision or strong judge-based feedback.

2Preliminaries

2.1Agentic Reinforcement Learning

In agentic reinforcement learning, a policy LLMπθ\pi_{\theta}solves a promptx∼𝒟x\sim\mathcal{D}by interleaving assistant tokens, tool calls from an available tool set𝒯\mathcal{T}, and tool observations before producing a final answer. A common KL-regularized training objective is

maxπθ𝔼x∼𝒟,τ∼πθ(⋅∣x;𝒯)[rϕ(x,τ)]−βKL𝔻KL[πθ(τ∣x;𝒯)∥πref(τ∣x;𝒯)],\max_{\pi_{\theta}}\mathbb{E}_{x\sim\mathcal{D},\,\tau\sim\pi_{\theta}(\cdot\mid x;\mathcal{T})}\left[r_{\phi}(x,\tau)\right]-\beta_{\mathrm{KL}}\,\mathbb{D}_{\mathrm{KL}}\!\left[\pi_{\theta}(\tau\mid x;\mathcal{T})\,\|\,\pi_{\mathrm{ref}}(\tau\mid x;\mathcal{T})\right],(1)whereτ\taudenotes the complete rollout,rϕr_{\phi}is the reward function,πref\pi_{\mathrm{ref}}is a reference policy, andβKL\beta_{\mathrm{KL}}controls the strength of the KL penalty. In reinforcement learning with verifiable rewards,rϕr_{\phi}is usually an outcome reward that is observed only after the rollout is complete, for example by checking whether the final answer satisfies an automatically verifiable criterion[Sutton and Barto,2018, Shaoet al.,2024]. Unlike single-turn reasoning, agentic rollouts induce a distribution over both the intermediate interaction trajectory and the final answer[Yaoet al.,2023, Schicket al.,2023, Nakanoet al.,2021, Yaoet al.,2022]. We write the interaction part as alternating policy actions and environment observations. Letℛ=((a1,o1),…,(aTℛ,oTℛ))\mathcal{R}=((a_{1},o_{1}),\ldots,(a_{T_{\mathcal{R}}},o_{T_{\mathcal{R}}}))andHk=(x,a1,o1,…,ak−1,ok−1)H_{k}=(x,a_{1},o_{1},\ldots,a_{k-1},o_{k-1}). Then

Pθ​(ℛ,y∣x;𝒯)=∏k=1Tℛπθ​(ak∣Hk;𝒯)​Penv​(ok∣Hk,ak;𝒯)⏟Tool​interaction⋅∏t=1Tyπθ​(yt∣y<t,HTℛ+1;𝒯)⏟Answer​generation,P_{\theta}(\mathcal{R},y\mid x;\mathcal{T})=\underbrace{\prod_{k=1}^{T_{\mathcal{R}}}\pi_{\theta}(a_{k}\mid H_{k};\mathcal{T})\,P_{\mathrm{env}}(o_{k}\mid H_{k},a_{k};\mathcal{T})}_{\mathrm{Tool\ interaction}}\cdot\underbrace{\prod_{t=1}^{T_{y}}\pi_{\theta}(y_{t}\mid y_{<t},H_{T_{\mathcal{R}}+1};\mathcal{T})}_{\mathrm{Answer\ generation}},(2)whereℛ\mathcal{R}is the multi-turn trajectory, including tool-call feedback, andyyis the final answer. Gradients are taken through assistant actions and answer tokens, while tool observations are environment outputs rather than policy-generated tokens. This decomposition highlights the source of the credit-assignment problem: the terminal reward supervises a long sequence of heterogeneous policy decisions, but does not identify which turns made the answer more or less likely.

For credit assignment, it is useful to view the interaction trajectory at tool-call boundaries. Given a rollout withTℛT_{\mathcal{R}}tool interactions, letSkS_{k}denote the prefix containing the prompt and the firstkkaction–observation pairs, optionally followed by the final-answer opener used to score answer tokens. The transition fromSkS_{k}toSk+1S_{k+1}is induced by the next policy action and environment observation(ak+1,ok+1)(a_{k+1},o_{k+1}). These prefix transitions are the natural units for assigning credit to tool use, because they isolate how each interaction changes the information available to the agent.

Typical RL training builds on outcome-based agentic RL algorithms such as Group Relative Policy Optimization (GRPO)[Guoet al.,2025], which compare multiple rollouts from the same prompt and avoid a learned critic for the outcome-reward stage[Shaoet al.,2024]. However, the resulting group-relative advantage is still attached to the entire rollout. It can rank a successful trajectory above failed alternatives, but it cannot distinguish useful tool calls from redundant or harmful ones within the same trajectory. This limitation motivates a reward construction that preserves the reliability of outcome verification while exposing denser signal at the prefix-transition level.

2.2Temporal-Difference Credit Assignment

Temporal-difference (TD) learning estimates progress by comparing the value of two adjacent states[Sutton,1988]. Given a value functionV​(s)V(s), an immediate rewardrtr_{t}, and a discountγ\gamma, the one-step TD error is

δt=rt+γ​V​(st+1)−V​(st).\delta_{t}\;=\;r_{t}+\gamma V(s_{t+1})-V(s_{t}).(3)The TD error is positive when the transition leads to a state whose realized or estimated future return is higher than expected, and negative when it leads to a worse state. In sparse-reward agentic tasks, intermediate environment rewards are usually unavailable. If we setrt=0r_{t}=0before termination and useγ=1\gamma=1, the TD form reduces to the value differenceV​(st+1)−V​(st)V(s_{t+1})-V(s_{t}), which naturally measures the incremental progress made by one transition. The difficulty is that long-horizon agent tasks usually lack a reliable dense value function over partially completed tool trajectories. The next section addresses this missing ingredient: how to obtain a stable prefix-level progress signal without training a critic or collecting step-level process labels.

3Turn-Level Reward Assignment via Credit Estimation

Figure 2:TRACEreward construction at tool-call boundaries.The figure shows a long-horizon rollout segmented by tool calls and observations. Each prefix state is scored by a frozen reference model, transformed into a log-ratio value, and compared with adjacent prefix values to obtain turn-level TD credit. The turn-level advantage is then combined with the trajectory-level outcome advantage for policy optimization.We introduceTRACE, a critic-free credit-assignment method for long-horizon agent post-training. Instead of learning a critic over sparse terminal rewards,TRACEmeasures whether each tool interaction makes the gold answer more predictable under a frozen reference model. It splits rollouts at tool-call boundaries, maps prefix answer log-probabilities to log-ratio state values, uses TD changes in those values as turn-level rewards, and mixes the resulting turn-level advantage with the standard GRPO outcome advantage. The outcome reward remains the final arbiter of task success. Figure2illustrates the framework, and Algorithm1summarizes the procedure.

3.1Tool-Boundary States

Following the prefix-transition view in Section2.1, we instantiate the notation used byTRACE. For a sampled trajectory on questionxxwith gold answery⋆y^{\star}, write

τ=(x,a1,o1,a2,o2,…,aT,oT,y^),\tau=\bigl(x,\;a_{1},\;o_{1},\;a_{2},\;o_{2},\;\ldots,\;a_{T},\;o_{T},\;\hat{y}\bigr),(4)whereaka_{k}is thekk-th assistant action,oko_{k}is the corresponding tool observation,y^\hat{y}is the final answer span, andTTis the number of tool interactions. The terminal verifier returnsR=R​(y^,y⋆)R=R(\hat{y},y^{\star}).TRACEconstructs one credit target for each transitionSk→Sk+1S_{k}\to S_{k+1}induced by(ak+1,ok+1)(a_{k+1},o_{k+1}), while the policy-gradient loss is applied only to policy-generated assistant actions and answer tokens; tool observations remain environment outputs and are masked from the loss. The remaining question is how to score whether a prefix transition improves the trajectory’s ability to reach the gold answer.

3.2State Value via Log-Ratio Answer Probability

Reference answer score.

Long-horizon agentic RL makes critic learning brittle: the trajectory reward is sparse, observations shift the state after each tool action, and failed trajectories can still contain useful action–observation transitions.TRACEtherefore replaces a learned critic with afrozenreference modelπref\pi_{\mathrm{ref}}(a copy of the policy initialization), used only to estimate how ready the single-trajectory prefix is to produce the gold answer. This is a natural proxy for progress in RLVR settings: the gold answer is available during training, and a transcript that has collected relevant evidence should make that answer easier for a fixed language model to conditionally predict. Freezing the model keeps this probe stable across policy updates and prevents it from becoming another learned reward model. For stateSkS_{k}, the average gold-answer log-probability is

ℓ¯k=1|y⋆|​∑t=1|y⋆|log⁡πref​(yt⋆∣Sk,y<t⋆)≤0.\bar{\ell}_{k}=\frac{1}{|y^{\star}|}\sum_{t=1}^{|y^{\star}|}\log\pi_{\mathrm{ref}}\!\left(y^{\star}_{t}\mid S_{k},\,y^{\star}_{<t}\right)\;\leq\;0.(5)Larger (less negative)ℓ¯k\bar{\ell}_{k}means that the current transcript already contains more evidence for generatingy⋆y^{\star}. Allℓ¯k\bar{\ell}_{k}are obtained in a single batched forward pass and are never optimized; final-answer correctness is still determined by the outcome verifier.

Log-ratio state value.

The scoreℓ¯k\bar{\ell}_{k}is a prefix-readiness measure, but its raw scale is not directly suitable for credit assignment. Raw changes inℓ¯k\bar{\ell}_{k}can be misleading: the same absolute gain is minor when the trajectory is far from the answer but important when it nearly resolves the answer. For instance, shrinking the remaining gap from0.20.2to0.10.1removes half the uncertainty, whereas5.1→5.05.1\!\to\!5.0barely changes it despite an identical raw gain. We therefore model the state value as relative closure of the initial answer-likelihood gap. Definedk=−ℓ¯k+ϵd_{k}=-\bar{\ell}_{k}+\epsilonwith offsetϵ>0\epsilon>0, and set

V​(Sk)=log⁡d0dk=log⁡−ℓ¯0+ϵ−ℓ¯k+ϵ.V(S_{k})\;=\;\log\frac{d_{0}}{d_{k}}\;=\;\log\frac{-\bar{\ell}_{0}+\epsilon}{-\bar{\ell}_{k}+\epsilon}.(6)ThusV​(S0)=0V(S_{0})=0, and a largerV​(Sk)V(S_{k})means that the action–observation history has closed a largerfractionof the initial gap. The later TD differenceV​(Sk+1)−V​(Sk)V(S_{k+1})-V(S_{k})therefore measures the value added by the transition induced by actionak+1a_{k+1}and observationok+1o_{k+1}.

Algorithm 1TRACEreward construction and policy update for one prompt group.1:prompt

xx, gold answer

y⋆y^{\star}, current policy

πθ\pi_{\theta}, behavior snapshot

πold\pi_{\mathrm{old}}, frozen reference

πref\pi_{\mathrm{ref}}, group size

GG, horizon

KK, discount

γtd\gamma_{\mathrm{td}}, offset

ϵ\epsilon, terminal scale

λterm\lambda_{\mathrm{term}}, weights

αout,αturn\alpha_{\mathrm{out}},\alpha_{\mathrm{turn}}, clip bounds

c−,c+c_{-},c_{+} 2:Sample

GGtrajectories

{τg}g=1G∼πold(⋅∣x)\{\tau_{g}\}_{g=1}^{G}\sim\pi_{\mathrm{old}}(\cdot\mid x), where

τg=(x,ag,1,og,1,…,ag,Tg,og,Tg,y^g)\tau_{g}=(x,a_{g,1},o_{g,1},\ldots,a_{g,T_{g}},o_{g,T_{g}},\hat{y}_{g}).

3:Compute terminal rewards

Rg=R​(y^g,y⋆)R_{g}=R(\hat{y}_{g},y^{\star})and outcome advantages

Agout=GroupNorm⁡(Rg;{Rh}h=1G)A^{\mathrm{out}}_{g}=\operatorname{GroupNorm}(R_{g};\{R_{h}\}_{h=1}^{G}), returning

0for all

ggif the group standard deviation is

0.

4:for

g=1,…,Gg=1,\ldots,Gdo

5:Form answer-ready prefixes

Sg,0,…,Sg,TgS_{g,0},\dots,S_{g,T_{g}}from

τg\tau_{g}.

6:for

k=0,…,Tgk=0,\ldots,T_{g}do

7:

ℓ¯g,k=1|y⋆|​∑t=1|y⋆|log⁡πref​(yt⋆∣Sg,k,y<t⋆)\displaystyle\bar{\ell}_{g,k}=\frac{1}{|y^{\star}|}\sum_{t=1}^{|y^{\star}|}\log\pi_{\mathrm{ref}}(y^{\star}_{t}\mid S_{g,k},y^{\star}_{<t}).

8:

dg,k=−ℓ¯g,k+ϵ,Vg,k=V​(Sg,k)=log⁡dg,0dg,k\displaystyle d_{g,k}=-\bar{\ell}_{g,k}+\epsilon,\qquad V_{g,k}=V(S_{g,k})=\log\frac{d_{g,0}}{d_{g,k}}.

9:endfor

10:for

k=0,…,Tg−1k=0,\ldots,T_{g}-1do

11:

δg,k=Vg,k+1−Vg,k=log⁡dg,kdg,k+1\displaystyle\delta_{g,k}=V_{g,k+1}-V_{g,k}=\log\frac{d_{g,k}}{d_{g,k+1}}.

12:if

K=0K=0then

13:

cg,k(K)=0c^{(K)}_{g,k}=0and

hg,k=kh_{g,k}=k.

14:else

15:

hg,k=min⁡(k+K−1,Tg−1)\displaystyle h_{g,k}=\min(k+K-1,T_{g}-1).

16:

Zg,k=∑u=khg,kγtdu−k,cg,k(K)=Zg,k−1​∑u=khg,kγtdu−k​δg,u\displaystyle Z_{g,k}=\sum_{u=k}^{h_{g,k}}\gamma_{\mathrm{td}}^{u-k},\qquad c^{(K)}_{g,k}=Z_{g,k}^{-1}\sum_{u=k}^{h_{g,k}}\gamma_{\mathrm{td}}^{u-k}\delta_{g,u}.

17:endif

18:

rg,kturn=cg,k(K)+𝟏​[hg,k=Tg−1]​λterm​γtdTg−k​Agout.\displaystyle\begin{aligned} r^{\mathrm{turn}}_{g,k}={}&c^{(K)}_{g,k}+\mathbf{1}[h_{g,k}=T_{g}-1]\lambda_{\mathrm{term}}\gamma_{\mathrm{td}}^{T_{g}-k}A^{\mathrm{out}}_{g}.\end{aligned} 19:endfor

20:endfor

21:Let

ℐg\mathcal{I}_{g}be the assistant-token indices of trajectory

gg.

22:For each

ggand

t∈ℐgt\in\mathcal{I}_{g}, set

A^g,t=αout​Agout+αturn​rg,turn​(t)turn\displaystyle\hat{A}_{g,t}=\alpha_{\mathrm{out}}A^{\mathrm{out}}_{g}+\alpha_{\mathrm{turn}}r^{\mathrm{turn}}_{g,\mathrm{turn}(t)}.

23:

ρg,t​(θ)=πθ​(ag,t∣sg,t)πold​(ag,t∣sg,t)\displaystyle\rho_{g,t}(\theta)=\frac{\pi_{\theta}(a_{g,t}\mid s_{g,t})}{\pi_{\mathrm{old}}(a_{g,t}\mid s_{g,t})}.

24:Update

πθ\pi_{\theta}by maximizing

𝒥TRACE​(θ)\mathcal{J}_{\mathrm{TRACE}}(\theta):

25:

1G​∑g=1G1|ℐg|​∑t∈ℐgmin⁡(ρg,t​(θ)​A^g,t,clip⁡(ρg,t​(θ),1−c−,1+c+)​A^g,t)\displaystyle\frac{1}{G}\sum_{g=1}^{G}\frac{1}{|\mathcal{I}_{g}|}\sum_{t\in\mathcal{I}_{g}}\min\!\left(\rho_{g,t}(\theta)\hat{A}_{g,t},\operatorname{clip}(\rho_{g,t}(\theta),1-c_{-},1+c_{+})\hat{A}_{g,t}\right).

3.3Turn-Level Reward via Temporal-Difference Credit

One-step TD action credit.

With no intermediate environment reward and discount11, the credit assigned to the transitionSk→ak+1,ok+1Sk+1S_{k}\xrightarrow{a_{k+1},\,o_{k+1}}S_{k+1}is the one-step TD change in value,

δk=V​(Sk+1)−V​(Sk)=log⁡dkdk+1,k=0,…,T−1.\delta_{k}\;=\;V(S_{k+1})-V(S_{k})\;=\;\log\frac{d_{k}}{d_{k+1}},\qquad k=0,\dots,T-1.(7)This is positive when the action and returned observation make the gold answer more likely, equalslog⁡2\log 2when the transition halves the remaining gap, is0when the gap is unchanged, and is negative when the transition moves away from the answer. Because the credits telescope,

∑k=0T−1δk=V​(ST)−V​(S0)=log⁡−ℓ¯0+ϵ−ℓ¯T+ϵ,\sum_{k=0}^{T-1}\delta_{k}\;=\;V(S_{T})-V(S_{0})\;=\;\log\frac{-\bar{\ell}_{0}+\epsilon}{-\bar{\ell}_{T}+\epsilon},so total credit depends only on the endpoints: redundant intermediate transitions cannot inflate it, and the agent is not rewarded for padding a trajectory. AppendixA.2compares this log-ratio credit with raw and linearized alternatives.

KK-step turn credit.

The one-step TD credit above can miss delayed tool effects: for example, abrowser.searchmay only surface candidate links, while the answer likelihood jumps after a laterbrowser.openexposes decisive evidence. We therefore use a truncatedKK-step TD backup withK≥1K\geq 1: each turn receives discounted future TD progress from the current transition and the next few transitions in the same trajectory. For rolloutggand turnkk, let

hg,k=min⁡(k+K−1,Tg−1)h_{g,k}=\min(k+K-1,\,T_{g}-1)(8)be the last transition included in the backup window. The local progress credit assigned to the current turn is

cg,k(K)=1Zg,k​∑u=khg,kγtdu−k​δg,u,Zg,k=∑u=khg,kγtdu−k,c^{(K)}_{g,k}=\frac{1}{Z_{g,k}}\sum_{u=k}^{h_{g,k}}\gamma_{\mathrm{td}}^{\,u-k}\delta_{g,u},\qquad Z_{g,k}=\sum_{u=k}^{h_{g,k}}\gamma_{\mathrm{td}}^{\,u-k},(9)whereγtd\gamma_{\mathrm{td}}discounts delayed evidence andZg,kZ_{g,k}is theKK-step normalization factor used in our reported runs. In ablations, we useK=0K=0only as a shorthand for disabling the dense TD backup entirely, not as an input to Eq.9. When the backup window reaches the end of the trajectory, we additionally anchor the last turns to the verifiable outcome signal:

rg,kturn=cg,k(K)+𝟏​[hg,k=Tg−1]​λterm​γtdTg−k​Agout.r^{\mathrm{turn}}_{g,k}=c^{(K)}_{g,k}+\mathbf{1}\!\left[h_{g,k}=T_{g}-1\right]\lambda_{\mathrm{term}}\,\gamma_{\mathrm{td}}^{\,T_{g}-k}\,A^{\mathrm{out}}_{g}.(10)HereAgoutA^{\mathrm{out}}_{g}is the standard GRPO group-relative advantage computed from the terminal reward, andλterm\lambda_{\mathrm{term}}controls the strength of the terminal anchor. The exponentTg−kT_{g}-ktreats final-answer generation as one additional transition after the last tool observation, so the last tool turn is discounted by one step before receiving terminal-outcome fill. This form makes the two sources of credit explicit:cg,k(K)c^{(K)}_{g,k}captures local answer-likelihood progress, while the terminal fill only affects turns whose look-ahead window reaches the final outcome. The endpoint telescoping property above applies exactly to the one-step componentδk\delta_{k}; theKK-step backup and terminal fill intentionally trade this exact endpoint-only form for delayed credit propagation and outcome anchoring.

Joint optimization with outcome reward.

We do not group-normalize the turn values. Instead, the TD-derived turn credit is used directly as a trajectory-local auxiliary signal and is jointly optimized with the GRPO outcome reward. For the outcome component, we use the standard group-relative normalization

Agout={(Rg−R¯)/σR,σR>0,0,σR=0,R¯=G−1​∑h=1GRh,σR=G−1​∑h=1G(Rh−R¯)2.A^{\mathrm{out}}_{g}=\begin{cases}(R_{g}-\bar{R})/\sigma_{R},&\sigma_{R}>0,\\ 0,&\sigma_{R}=0,\end{cases}\quad\bar{R}=G^{-1}\sum_{h=1}^{G}R_{h},\quad\sigma_{R}=\sqrt{G^{-1}\sum_{h=1}^{G}(R_{h}-\bar{R})^{2}}.For each token generated as part of tool-interaction actionag,k+1a_{g,k+1}, we setturn​(t)=k\mathrm{turn}(t)=k; final-answer tokens use the outcome component with the answer-tail weighting described in AppendixA.1. The mixed per-token advantage for tool-interaction tokens is

A^g,t=αout​Agout+αturn​rg,turn​(t)turn,\hat{A}_{g,t}=\alpha_{\mathrm{out}}\,A^{\mathrm{out}}_{g}+\alpha_{\mathrm{turn}}\,r^{\mathrm{turn}}_{g,\,\mathrm{turn}(t)},(11)whereαout,αturn≥0\alpha_{\mathrm{out}},\alpha_{\mathrm{turn}}\geq 0control the relative strength of terminal correctness and turn-level credit. Letℐg\mathcal{I}_{g}be the assistant-token indices used in the policy-gradient loss for rolloutgg, and letρg,t​(θ)=πθ​(ag,t∣sg,t)/πold​(ag,t∣sg,t)\rho_{g,t}(\theta)=\pi_{\theta}(a_{g,t}\mid s_{g,t})/\pi_{\mathrm{old}}(a_{g,t}\mid s_{g,t}), whereπold\pi_{\mathrm{old}}is the frozen behavior-policy snapshot that generated the current rollout batch. We optimize the clipped GRPO objective

𝒥TRACE​(θ)=1G​∑g=1G1|ℐg|​∑t∈ℐgmin⁡(ρg,t​(θ)​A^g,t,clip⁡(ρg,t​(θ),1−c−,1+c+)​A^g,t),\mathcal{J}_{\mathrm{TRACE}}(\theta)=\frac{1}{G}\sum_{g=1}^{G}\frac{1}{|\mathcal{I}_{g}|}\sum_{t\in\mathcal{I}_{g}}\min\!\left(\rho_{g,t}(\theta)\hat{A}_{g,t},\operatorname{clip}\!\left(\rho_{g,t}(\theta),1-c_{-},1+c_{+}\right)\hat{A}_{g,t}\right),(12)which keeps the standard GRPO group-relative outcome signal while adding dense turn-level credit without normalizing the turn values across the prompt group.

4Experiments

4.1Experimental Setup

Training datasets.

A central question in this work is whether dense turn-level credit can improve long-horizon tool use when the only verifiable supervision is final-answer correctness. To examine this question in a controlled setting, we train agents on synthetic multi-document search tasks built over the offline corpus released by OpenResearcher[Liet al.,2026]. Standard multi-hop QA benchmarks are often too short for this purpose: many examples can be solved with one search and one document open, leaving little room to study delayed credit from later evidence gathering. Our training data instead requires chained retrieval over multiple irreplaceable evidence documents, so early queries, document-selection decisions, and in-document localization steps can all affect the final answer. AppendixA.4describes the data generation, filtering, and verification pipeline.

Agentic harness.

The policy is trained in a ReAct-style reasoning-and-acting harness[Yaoet al.,2023], where each assistant turn contains private reasoning and either one browser action or a final answer. The closed-corpus harness serves documents from the OpenResearcher offline corpus through a FAISS retrieval index built with Qwen3-Embedding-8B[Zhanget al.,2025c]. The browser interface exposes three actions,browser.search,browser.open, andbrowser.find; the final response must be emitted inside<answer>tags. The outcome reward checks normalized exact-match answer correctness, with a small format component for well-formed answer blocks. AppendixA.3gives the full tool schema, rollout stopping rules, masking convention, and prompt template.

Models.

To evaluate whether the same credit-assignment signal works across model scale, we instantiate the search policy with two Qwen3 thinking backbones: Qwen3-4B-Thinking-2507 and Qwen3-30B-A3B-Thinking-2507[Yanget al.,2025a]. The 4B model is our primary controlled setting for comparing optimization objectives and ablations, while the 30B-A3B model tests whetherTRACEtransfers to a larger agentic backbone. Unless otherwise stated, both models use the same browser action space, rollout protocol, terminal reward, training data, and evaluation interface. Importantly, all controlled RL runs start directly from the base search policy without a cold-start supervised fine-tuning stage, a mid-training stage, or training on live-web data.

Training protocol.

We optimize each student with Adam at a constant learning rate of10−610^{-6}, using a global batch size of128128and88rollouts per prompt, with up to6060tool turns per trajectory.TRACEcomputes turn credit with the log-ratio formulation in Eq.7, using training gap offsetϵtrain=10−1\epsilon_{\mathrm{train}}=10^{-1}. The look-ahead advantage in Eq.10uses horizonK=3K=3and discountγtd=0.8\gamma_{\mathrm{td}}=0.8, with terminal-outcome fill enabled at scale2.02.0. The final per-token advantage in Eq.11mixes outcome and turn signals withαout=1.0\alpha_{\mathrm{out}}=1.0andαturn=0.2\alpha_{\mathrm{turn}}=0.2; the token-level distillation term is disabled in this work. Tokens in the final answer span are weighted by the group-mean rule at scale0.050.05. AppendixA.1lists the full script-level training, rollout, and turn-credit hyperparameters.

Baselines.

We compareTRACEwith both external deep-research agents and controlled RL baselines. The external agents include ASearcher-QwQ-32B[Gaoet al.,2025], WebDancer-32B[Wuet al.,2025b], CutBill-30B-A3B[Wuet al.,2025a], and TongyiDS-30B-A3B[Tongyi DeepResearch Teamet al.,2025]; these systems provide strong reference points for long-horizon search, although they may use different data, model backbones, training pipelines, and benchmark harnesses, so we treat their reported numbers as non-controlled reference points. The controlled baselines are initialized from the same Qwen3 backbones asTRACE. Base denotes the untrained search policy. GRPO[Guoet al.,2025]uses only the terminal outcome reward, GSPO[Zhenget al.,2025a]replaces token-level importance ratios with sequence-level ratios, and GiGRPO[Fenget al.,2025]applies group-in-group policy optimization for agent training. For all controlled baselines, we keep the browser action space, rollout protocol, training data, terminal reward, and evaluation interface fixed, so performance differences primarily reflect the optimization objective and credit-assignment signal.

Evaluation.

We evaluate deep-research ability in both closed-web and open-web settings. The closed-web benchmark is BrowseComp-Plus[Chenet al.,2025c], for which we build an offline search engine from the officially released corpus using a Qwen3-Embedding-8B[Zhanget al.,2025c]FAISS index. This setting measures long-horizon reasoning under a reproducible retrieval environment that matches the training interface. To test transfer beyond the closed training corpus, we also evaluate on three open-web benchmarks: BrowseComp[Weiet al.,2025a], GAIA[Mialonet al.,2024], and xbench-DeepSearch[Chenet al.,2025a], where retrieval is served by the Serper API[Serper.dev,2026]. Among them, xbench-DeepSearch is a Chinese QA benchmark, allowing us to test whether a training recipe learned in the closed search setting transfers across languages as well as across retrieval environments. Across all evaluations, rollouts stop when the model emits a final<answer>span, reaches the tool-turn limit, or hits a context or generation limit. Unless otherwise stated, controlled ablations are single training runs, so small differences should be read as directional rather than as variance-adjusted conclusions.

4.2Main Results

ModelBrowseComp-PlusBrowseCompGAIAxbench-DeepSearchAvgDeep-research agentsASearcher-QwQ-32B28.95.252.842.032.2WebDancer-32B32.43.851.539.031.7CutBill-30B-A3B35.113.446.643.034.5TongyiDS-30B-A3B44.443.470.975.058.4Qwen3-4B-Thinking-2507Base7.23.324.219.013.4GRPO30.05.138.844.029.5GSPO29.75.436.741.028.2GiGRPO27.74.437.936.026.5\rowcolorgray!15TRACE35.66.744.649.034.0Qwen3-30B-A3B-Thinking-2507Base8.44.434.120.016.7GRPO36.410.845.637.032.5GSPO39.711.846.635.033.3GiGRPO33.010.144.731.029.7\rowcolorgray!15TRACE42.612.952.045.038.1Table 1:Performance comparison on long-horizon deep-research benchmarks.BrowseComp-Plus is evaluated in the closed-web setting, while BrowseComp, GAIA, and xbench-DeepSearch are evaluated with open-web retrieval. Avg reports the unweighted average over all four benchmarks. The top block lists external deep-research agents for reference, while the Qwen3 blocks compare controlled RL variants initialized from the same backbone and trained with the same browser interface, data, terminal reward, and evaluation protocol. Highlighted rows denoteTRACE.##### TRACEremarkably improves base-model tool use and transfers beyond the training corpus.

Table1shows thatTRACEsubstantially improves base-model tool use while retaining generalization beyond the training environment. The most direct evidence comes from the closed-web BrowseComp-Plus setting, whereTRACEraises Qwen3-4B from7.27.2to35.635.6and Qwen3-30B-A3B from8.48.4to42.642.6using only RL with outcome-level and turn-level rewards. This is a strong gain for a minimal recipe: the models are not first adapted with cold-start SFT, agentic mid-training, or live-web data, so the improvement suggests that the base backbones already contain useful reasoning and tool-use primitives, but need a denser credit signal to organize them into effective long-horizon behavior. The external-agent comparisons give the result additional context. Although those systems may use different data and training pipelines, the 4BTRACEagent already surpasses several larger deep-research agents on BrowseComp-Plus, while the 30B-A3B agent approaches the strong TongyiDS-30B-A3B result. The more important controlled test is whether this behavior transfers beyond the closed training corpus: despite being trained in a closed synthetic search environment,TRACEimproves both backbones on open-web benchmarks served by an external search API; with Qwen3-30B-A3B, it reaches12.912.9on BrowseComp,52.052.0on GAIA, and45.045.0on the Chinese QA benchmark xbench-DeepSearch. This pattern suggests thatTRACEis not merely fitting the closed retrieval corpus within our controlled setup; it teaches a more general interaction strategy for searching, reading observations, and refining later actions across different corpora and languages, though it does not close the gap to the strongest external deep-research system in Table1.

TRACEoutperforms other RL methods across model scales.

The controlled RL comparison clarifies why the gains come from credit assignment rather than from a change in model, data, or environment. All RL variants use the same backbone, browser interface, training data, terminal reward, and evaluation protocol; what differs is how the policy-gradient signal is constructed. Against outcome-only GRPO,TRACEasks the cleanest question: if the final correctness reward is unchanged, does adding turn-level TD credit help? The answer is yes on both scales, with the 4B four-benchmark average rising to34.034.0from GRPO’s29.529.5and the 30B-A3B average rising to38.138.1from32.532.5. This indicates that terminal rewards alone do not expose enough information about which parts of a long trajectory should be reinforced. GSPO and GiGRPO address a different aspect of RL optimization by changing sequence- or group-level estimation, but they still operate primarily at the trajectory level: they can compare rollouts, yet they do not assign credit to the intermediate interaction that made later success more likely. This distinction explains whyTRACEis especially beneficial on BrowseComp-Plus and xbench-DeepSearch, where success depends on a chain of dependent environment interactions rather than a single decisive final answer. By keeping outcome correctness as the global anchor and adding temporally aligned progress credit within the trajectory,TRACEsupplies the kind of supervision that long-horizon agent training is missing.

4.3Learning Dynamics ofTRACE

Figure 3:Learning dynamics on BrowseComp-Plus.(a) Training reward on Qwen3-4B. (b) Evaluation accuracy on Qwen3-4B. (c) Training reward on Qwen3-30B-A3B. (d) Evaluation accuracy on Qwen3-30B-A3B.##### TRACEmakes the model converge faster and to a better policy.

Figure3compares the learning dynamics ofTRACEand outcome-reward baselines across four panels. The first visible trend is that all methods improve as training proceeds, but theTRACEcurves start rising earlier. The second trend is that the slope ofTRACEis steeper in the early stage, indicating faster reward acquisition rather than only a late-stage separation. The third trend is that the gap does not disappear after the initial rise:TRACEstabilizes at a higher plateau, suggesting that the faster optimization also leads to a better learned policy. Finally, the same ordering appears in held-out accuracy on BrowseComp-Plus with Qwen3-30B-A3B, where the160160-stepTRACEcheckpoint already exceeds the200200-step outcome-reward baseline. These observations suggest that the reward-curve improvement reflects earlier acquisition of transferable long-horizon search behavior. A likely reason is that outcome-only training assigns one terminal signal to the whole trajectory, so early failed rollouts can update useful intermediate progress together with the final mistake.TRACEreduces this temporal mismatch by assigning turn-level TD credit when an interaction makes the gold answer more predictable under the reference model, while still keeping the outcome reward in the objective to enforce final correctness.

TRACEscales up interaction length faster in the beginning stage.

Figure 4:Trajectory-scale dynamics on BrowseComp-Plus with Qwen3-4B. TheTRACEcurve increases earlier and faster than GRPO, indicating that the two training objectives expand interaction length at different rates during the early training stage.Figure4shows a clear difference in trajectory scale betweenTRACEand GRPO on the Qwen3-4B backbone: theTRACEcurve starts to rise earlier and grows faster, while the GRPO curve increases more slowly. This suggests that the objectives differ in how they encourage longer environment interaction during early training. With outcome-only GRPO, longer early trajectories often still fail at the final answer, so the whole rollout receives low or negative relative advantage and the objective cannot separate unhelpful extra interaction from intermediate progress.TRACEprovides a more local signal: when an interaction and its observation increase answer readiness, the turn-level TD credit can reward that progress before the final answer is correct. This gives a smoother incentive for scaling interaction length, while the outcome reward keeps optimization tied to final correctness.

4.4Ablation Study

Figure 5:Ablations on BrowseComp-Plus with Qwen3-4B.(a) Turn-level reward coefficient. (b) TD look-ahead horizonKK. (c) Reference checkpoint for answer-readiness scoring.##### Log-ratio credit assignment is more effective in this run.

MethodBC-PlusGRPO30.0+ raw delta32.4+ remaining gap34.6\rowcolorgray!15 + log-ratio35.5Table 2:Credit-assignment ablation on Qwen3-4B.We ablate the turn-level credit format on BrowseComp-Plus while keeping the same Qwen3-4B training setup. Starting from outcome-only GRPO (30.030.0), adding dense transition rewards based on the raw log-probability delta improves the score to32.432.4, and normalizing by the remaining answer-likelihood gap further improves it to34.634.6. The proposed log-ratio TD credit achieves the best score in this run (35.535.5), suggesting that relative gap closure provides a more effective credit signal than absolute likelihood changes. This supports the design in Eq.7: the log-ratio form better normalizes credit across states with different confidence levels and preserves a telescoping structure that discourages redundant trajectory extension.

Ablation on turn-level reward coefficient.

Figure5(a) shows that the weight assigned to the dense turn-level signal must be chosen moderately. A small coefficient underuses the extra supervision from prefix-level progress, while an overly large coefficient can make local reference-model readiness dominate the final correctness signal. In the coefficient sweep, performance rises from33.633.6to35.635.6as the coefficient increases from11to33, but then drops to34.534.5and31.131.1at larger values. This pattern supports the use of turn-level reward as an auxiliary credit signal rather than a replacement for the outcome reward.

Ablation on TD look-ahead horizonKK.

Figure5(b) varies the TD look-ahead horizonKK, which controls the strength of the propagated transition-level signal. TheK=0K=0ablation denotes disabling the dense TD backup entirely rather than passingK=0K=0into Eq.9; it obtains only30.030.0accuracy, close to outcome-only GRPO, because early search and document-selection actions receive little useful credit. Moderate propagation substantially improves performance, reaching34.734.7and35.635.6, which indicates that delayed evidence from lateropenandfindoperations should be assigned back to the preceding retrieval decisions. However, the largest setting reduces accuracy to28.928.9, suggesting that overemphasizing the propagated signal introduces noise from loosely related later turns and weakens the temporal locality of the reward.

Ablation on reference model for probability estimation.

Finally, Figure5(c) studies which reference checkpoint should be used to compute the gold-answer prefix probabilities. The baseline without reference-model progress scoring reaches30.030.0, while using the initialization checkpoint at step0raises accuracy to35.635.6. Replacing it with a slightly updated checkpoint at step200200obtains a similar score of36.136.1in this run. The small gap between the two reference checkpoints suggests thatTRACEdoes not rely on a specially strong or heavily tuned reference model. Instead, the reference model mainly serves as a stable value-estimation anchor: it provides prefix-level answer-readiness scores from which relative TD progress can be computed. In practice, the base checkpoint is already sufficient for this role, which makes the method easier to apply and reduces dependence on selecting an advanced teacher or a carefully adapted scoring model.

5Related Work

Post-training of LLMs for reasoning and agentic tasks.

Post-training has become a central recipe for turning pretrained language models into capable problem solvers. For reasoning tasks, reinforcement learning with verifiable rewards has shown that outcome supervision can substantially improve mathematical and symbolic problem solving when correctness can be checked automatically[Shaoet al.,2024, Guoet al.,2025]. These methods typically optimize a trajectory-level signal with clipped policy-gradient updates[Schulmanet al.,2017]: a complete solution receives positive or negative feedback according to whether the final answer is correct. This simple regime is effective for short-horizon reasoning, but becomes less informative as decisions grow into multi-hop or browsing trajectories[Yanget al.,2018, Weiet al.,2025a, Chenet al.,2025c]. LLM post-training has also been extended from single-response reasoning to agentic settings in which models interact with tools, environments, users, or external feedback over multiple turns. Early systems such as WebGPT and ReAct introduced the interleaving of language-model reasoning, actions, and observations[Nakanoet al.,2021, Yaoet al.,2023]. Subsequent work improves tool use through self-supervised tool-call prediction, instruction tuning on tool-use traces, and agent-specific tuning corpora[Schicket al.,2023, Qinet al.,2023, Zenget al.,2023], while related approaches use feedback across trials to revise plans, memory, or behavior[Shinnet al.,2023]. This agentic post-training landscape now covers a wide range of tasks beyond search. Representative settings include shopping and web navigation[Yaoet al.,2022, Denget al.,2023, Zhouet al.,2024, Kohet al.,2024, Drouinet al.,2024, Panet al.,2024], API and tool use[Schicket al.,2023, Qinet al.,2023, Liet al.,2023], software engineering agents and related coding systems, real-computer and mobile-device control[Xieet al.,2024, Rawleset al.,2025, Zhanget al.,2023], and multi-turn user-interactive tool use[Zhaoet al.,2025b, Chaiet al.,2025, Xiet al.,2025b, Zhanget al.,2025a]. Within software engineering, representative work spans role-based multi-agent development and interactive code execution[Honget al.,2024, Qianet al.,2024, Yanget al.,2023, Wanget al.,2024b]; repository-level evaluation, planning, and repair[Jimenezet al.,2024, Yanget al.,2024, Zhanget al.,2024a, Bairiet al.,2024, Zhanget al.,2024b, Bouzeniaet al.,2025, Wanget al.,2025c, Xiaet al.,2024]; and executable training environments, scalable task generation, and RL or inference-scaling recipes[Panet al.,2025, Yanget al.,2025b, Weiet al.,2025b, Jainet al.,2025, Wanget al.,2025b, Muet al.,2023]. Search and deep-research agents form one important branch of this broader agentic post-training trend, with recent work applying outcome-based RL, synthetic trajectory construction, and tool-use training to search-augmented reasoning and deep browsing[Liet al.,2025b, Chenet al.,2025b, Jinet al.,2025b, Songet al.,2025, Sunet al.,2025, Muet al.,2025, Liet al.,2025c, Wuet al.,2025b, Liet al.,2025a, Zhenget al.,2025b, Liet al.,2026, Wanget al.,2026b, Gaoet al.,2025]. Recent surveys and position papers summarize these developments under deep search, tool-use agents, and agentic deep research[Xiet al.,2025a, Zhanget al.,2025b]. Our work is in this general post-training regime: rather than designing a new agent interface or adding a stronger teacher, we study how to make the training signal more informative inside a multi-turn trajectory.

Credit assignment for long-horizon language agents.

Credit assignment is a long-standing challenge in reinforcement learning when the reward is delayed until the end of an extended trajectory[Sutton and Barto,2018]. Temporal-difference learning addresses this problem by estimating how each transition changes the value of the current state[Sutton,1988]. Potential-based reward shaping similarly uses differences in a state potential to provide denser feedback while preserving the underlying task objective under standard assumptions[Nget al.,1999], and return-decomposition methods such as RUDDER redistribute delayed rewards to the decisions that make the final outcome predictable[Arjona-Medinaet al.,2019]. In language-model reasoning, process supervision and process reward models provide fine-grained feedback by labeling or modeling intermediate reasoning steps[Uesatoet al.,2022, Lightmanet al.,2023, Li and Li,2025]. These approaches motivate dense supervision, but they often require a learned critic, human or synthetic step labels, process-reward annotation, Monte Carlo continuations, or task-specific reward features. Recent work has begun to adapt fine-grained credit assignment to language-model policies. For single-response reasoning,Setluret al.[2024]formalize a process reward as the change in the probability of eventually reaching a correct answer,Wanget al.[2024a]estimate per-step values from Monte Carlo rollouts, andYuanet al.[2024]derive an implicit process reward from the log-likelihood ratio between a policy and a fixed reference model. For multi-turn agents, recent work studies stepwise rewards, hindsight credit, memory-aware credit assignment, search-agent RL, and training infrastructure for long-horizon tool use[Fenget al.,2025, Wanget al.,2025a, Donget al.,2025b, Wanget al.,2025d, Zhaoet al.,2025a, Wanget al.,2026a, Tanet al.,2026, Yanet al.,2026, Quet al.,2025, Donget al.,2025a, Jinet al.,2025a, Xiet al.,2025b, Chaiet al.,2025, Zhaoet al.,2025b, Zhanget al.,2025a].TRACEshares the goal of assigning credit below the trajectory level, but avoids training an additional critic or progress estimator, does not require Monte Carlo continuations, and does not depend on revisiting identical states. At a high level,TRACEcomplements outcome-based post-training with turn-level feedback, allowing long-horizon agents to learn from useful intermediate progress rather than only from final success or failure.

6Limitations

Our empirical validation focuses on long-horizon search agents whose final answers are short and can be compared against a known ground truth. This setting matches the core design ofTRACE: the frozen reference model estimates the value of a trajectory prefix by measuring how much more predictable the gold answer becomes after each tool interaction. For tasks with compact answers, this provides a simple and stable proxy for progress. However, the same value estimation strategy may be less direct for agentic tasks whose correct outputs are long, structured, or open-ended. For example, a code agent may need to produce a multi-file patch rather than a short answer string, and an open-ended assistant may need to satisfy underspecified user preferences rather than match a single gold response. In such settings, it is unclear whether gold-output log-probability under a frozen reference model is still a reliable state-value proxy.

This limitation does not affect the main claim that turn-level credit can reduce the sparsity of outcome-only agentic RL, but it does bound the current scope of the method. ExtendingTRACEto richer agent tasks may require alternative state-value targets, such as execution-based progress signals for coding, structured task specifications, or decomposed verifiable subgoals. We leave the design of reliable credit estimators for long-output and open-ended agents to future work.

7Conclusion

We presentedTRACE, a critic-free method for assigning turn-level credit in long-horizon agentic RL. At tool-call boundaries, a frozen reference model maps gold-answer log-probabilities to log-ratio state values, whose TD changes provide local rewards. Combining this signal with the GRPO outcome advantage preserves final-answer correctness as the training anchor without step labels, a strong LLM judge, or a trained critic or process reward model.TRACEoutperforms outcome-only GRPO on all four benchmarks at both model scales, raising the four-benchmark average from29.529.5to34.034.0for Qwen3-4B and from32.532.5to38.138.1for Qwen3-30B-A3B. On BrowseComp-Plus, it improves the base policies from7.27.2to35.635.6and from8.48.4to42.642.6, with gains transferring to open-web evaluation. These results establish frozen-reference turn credit as an effective signal for long-horizon search with compact, verifiable answers; long, structured, or open-ended outputs will require alternative state-value estimators.

Acknowledgment

We gratefully acknowledge Xuhui Huang for his valuable feedback. The work is supported in part by the Research Forward Fund from the University of Wisconsin-Madison Office of the Vice Chancellor for Research, AFOSR Young Investigator Program under award number FA9550-23-1-0184, National Science Foundation under awards IIS-2237037 and IIS-2331669, Office of Naval Research, Schmidt Sciences Foundation, Open Philanthropy (now Coefficient Giving), and Alfred P. Sloan Fellowship.

References

• J. A. Arjona-Medina, M. Gillhofer, M. Widrich, T. Unterthiner, J. Brandstetter, and S. Hochreiter (2019)RUDDER: return decomposition for delayed rewards.InAdvances in Neural Information Processing Systems,Cited by:§1,§5.
• R. Bairi, A. Sonwane, A. Kanade, D. C. Vageesh, A. Iyer, S. Parthasarathy, S. Rajamani, B. Ashok, and S. Shet (2024)CodePlan: repository-level coding using LLMs and planning.Proceedings of the ACM on Software Engineering1(FSE),pp. 675–698.External Links:DocumentCited by:§5.
• RepairAgent: an autonomous, LLM-based agent for program repair.InProceedings of the 47th IEEE/ACM International Conference on Software Engineering,pp. 2188–2200.External Links:DocumentCited by:§5.
• J. Chai, G. Yin, Z. Xu, C. Yue, Y. Jia, S. Xia, X. Wang, J. Jiang, X. Li, C. Dong, H. He, and W. Lin (2025)RLFactory: a plug-and-play reinforcement learning post-training framework for LLM multi-turn tool-use.arXiv preprint arXiv:2509.06980.Cited by:§5,§5.
• K. Chen, Y. Ren, Y. Liu, X. Hu, H. Tian, T. Xie, F. Liu, H. Zhang, H. Liu, Y. Gong,et al.(2025a)xbench: tracking agents productivity scaling with profession-aligned real-world evaluations.arXiv preprint arXiv:2506.13651.Cited by:§4.1.
• M. Chen, T. Li, H. Sun, Y. Zhou, C. Zhu, F. Yang, Z. Zhou, W. Chen, H. Wang, J. Z. Pan, W. Zhang, and H. Chen (2025b)ReSearch: learning to reason with search for LLMs via reinforcement learning.arXiv preprint arXiv:2503.19470.Cited by:§5.
• Z. Chen, X. Ma, S. Zhuang, P. Nie, K. Zou,et al.(2025c)BrowseComp-Plus: a more fair and transparent evaluation benchmark of deep-research agent.arXiv preprint arXiv:2508.06600.Cited by:§1,§4.1,§5.
• X. Deng, Y. Gu, B. Zheng, S. Chen, S. Stevens, B. Wang, H. Sun, and Y. Su (2023)Mind2Web: towards a generalist agent for the web.InAdvances in Neural Information Processing Systems,Cited by:§1,§5.
• G. Dong, Y. Chen, X. Li, J. Jin, H. Qian, Y. Zhu, H. Mao, G. Zhou, Z. Dou, and J. Wen (2025a)Tool-Star: empowering LLM-brained multi-tool reasoner via reinforcement learning.arXiv preprint arXiv:2505.16410.Cited by:§5.
• G. Dong, H. Mao, K. Ma, L. Bao, Y. Chen,et al.(2025b)Agentic reinforced policy optimization.arXiv preprint arXiv:2507.19849.Cited by:§5.
• A. Drouin, M. Gasse, M. Caccia, I. H. Laradji, M. Del Verme, T. Marty, L. Boisvert, M. Thakkar, Q. Cappart, D. Vazquez, N. Chapados, and A. Lacoste (2024)WorkArena: how capable are web agents at solving common knowledge work tasks?.arXiv preprint arXiv:2403.07718.Cited by:§5.
• L. Feng, Z. Xue, T. Liu, and B. An (2025)Group-in-group policy optimization for LLM agent training.arXiv preprint arXiv:2505.10978.Cited by:§4.1,§5.
• J. Gao, W. Fu, M. Xie, S. Xu, C. He, Z. Mei, B. Zhu, and Y. Wu (2025)Beyond ten turns: unlocking long-horizon agentic search with large-scale asynchronous RL.arXiv preprint arXiv:2508.07976.Cited by:§4.1,§5.
• D. Guo, D. Yang, H. Zhang, J. Song, R. Zhang, R. Xu, Q. Zhu, S. Ma, P. Wang, X. Bi,et al.(2025)DeepSeek-R1: incentivizing reasoning capability in LLMs via reinforcement learning.Nature645,pp. 633–638.External Links:DocumentCited by:§1,§2.1,§4.1,§5.
• S. Hong, M. Zhuge, J. Chen, X. Zheng, Y. Cheng, C. Zhang, J. Wang, Z. Wang, S. K. S. Yau, Z. Lin, L. Zhou, C. Ran, L. Xiao, C. Wu, and J. Schmidhuber (2024)MetaGPT: meta programming for a multi-agent collaborative framework.InInternational Conference on Learning Representations,Cited by:§5.
• N. Jain, J. Singh, M. Shetty, L. Zheng, K. Sen, and I. Stoica (2025)R2E-Gym: procedural environments and hybrid verifiers for scaling open-weights SWE agents.arXiv preprint arXiv:2504.07164.Cited by:§5.
• C. E. Jimenez, J. Yang, A. Wettig, S. Yao, K. Pei, O. Press, and K. Narasimhan (2024)SWE-bench: can language models resolve real-world GitHub issues?.InInternational Conference on Learning Representations,Cited by:§1,§5.
• B. Jin, J. Yoon, P. Kargupta, S. O. Arik, and J. Han (2025a)An empirical study on reinforcement learning for reasoning-search interleaved LLM agents.arXiv preprint arXiv:2505.15117.Cited by:§5.
• B. Jin, H. Zeng, Z. Yue, J. Yoon, S. Arik, D. Wang, H. Zamani, and J. Han (2025b)Search-R1: training LLMs to reason and leverage search engines with reinforcement learning.arXiv preprint arXiv:2503.09516.Cited by:§5.
• J. Y. Koh, R. Lo, L. Jang, V. Duvvur, M. C. Lim, P. Huang, G. Neubig, S. Zhou, R. Salakhutdinov, and D. Fried (2024)VisualWebArena: evaluating multimodal agents on realistic visual web tasks.arXiv preprint arXiv:2401.13649.Cited by:§5.
• K. Li, Z. Zhang, H. Yin, L. Zhang, L. Ou, J. Wu, W. Yin, B. Li, Z. Tao, X. Wang,et al.(2025a)WebSailor: navigating super-human reasoning for web agent.arXiv preprint arXiv:2507.02592.Cited by:§5.
• M. Li, Y. Zhao, B. Yu, F. Song, H. Li, H. Yu, Z. Li, F. Huang, and Y. Li (2023)API-Bank: a comprehensive benchmark for tool-augmented LLMs.arXiv preprint arXiv:2304.08244.Cited by:§5.
• W. Li and Y. Li (2025)Process reward model with q-value rankings.InProceedings of the International Conference on Learning Representations,Cited by:§5.
• X. Li, G. Dong, J. Jin, Y. Zhang, Y. Zhou, Y. Zhu, P. Zhang, and Z. Dou (2025b)Search-o1: agentic search-enhanced large reasoning models.arXiv preprint arXiv:2501.05366.Cited by:§5.
• X. Li, J. Jin, G. Dong, H. Qian, Y. Wu, J. Wen, Y. Zhu, and Z. Dou (2025c)WebThinker: empowering large reasoning models with deep research capability.arXiv preprint arXiv:2504.21776.Cited by:§5.
• Z. Li, D. Jiang, X. Ma, H. Zhang, P. Nie, Y. Zhang, K. Zou, J. Xie, Y. Zhang, and W. Chen (2026)OpenResearcher: a fully open pipeline for long-horizon deep research trajectory synthesis.arXiv preprint arXiv:2603.20278.Cited by:§4.1,§5.
• H. Lightman, V. Kosaraju, Y. Burda, H. Edwards, B. Baker, T. Lee, J. Leike, J. Schulman, I. Sutskever, and K. Cobbe (2023)Let’s verify step by step.arXiv preprint arXiv:2305.20050.Cited by:§1,§5.
• G. Mialon, C. Fourrier, C. Swift, T. Wolf, Y. LeCun, and T. Scialom (2024)GAIA: a benchmark for general AI assistants.InInternational Conference on Learning Representations,Cited by:§4.1.
• J. Mu, Y. Lu, and M. Smith (2023)LLM-assisted incrementality (uplift) modeling for email advertising: from feature interactions to interpretable audience–creative–channel policies.Journal of Advanced Computing Systems3(1),pp. 31–48.Cited by:§5.
• J. Mu, T. Ye, and P. Patel (2025)Offline counterfactual evaluation for advertising and recommendation slot policies: a reproducible study on the open bandit dataset (small).Journal of Technology Informatics and Engineering4(3),pp. 521–543.Cited by:§5.
• R. Nakano, J. Hilton, S. Balaji, J. Wu, L. Ouyang, C. Kim, C. Hesse, S. Jain, V. Kosaraju, W. Saunders,et al.(2021)WebGPT: browser-assisted question-answering with human feedback.arXiv preprint arXiv:2112.09332.Cited by:§1,§2.1,§5.
• A. Y. Ng, D. Harada, and S. Russell (1999)Policy invariance under reward transformations: theory and application to reward shaping.InProceedings of the Sixteenth International Conference on Machine Learning,pp. 278–287.Cited by:§5.
• J. Pan, X. Wang, G. Neubig, N. Jaitly, H. Ji, A. Suhr, and Y. Zhang (2025)Training software engineering agents and verifiers with SWE-Gym.InInternational Conference on Machine Learning,Cited by:§5.
• Y. Pan, D. Kong, S. Zhou, C. Cui, Y. Leng, B. Jiang, H. Liu, Y. Shang, S. Zhou, T. Wu, and Z. Wu (2024)WebCanvas: benchmarking web agents in online environments.arXiv preprint arXiv:2406.12373.Cited by:§5.
• C. Qian, W. Liu, H. Liu, N. Chen, Y. Dang, J. Li, C. Yang, W. Chen, Y. Su, X. Cong, J. Xu, D. Li, Z. Liu, and M. Sun (2024)ChatDev: communicative agents for software development.InProceedings of the 62nd Annual Meeting of the Association for Computational Linguistics,pp. 15174–15186.External Links:DocumentCited by:§5.
• Y. Qin, S. Liang, Y. Ye, K. Zhu, L. Yan, Y. Lu, Y. Lin, X. Cong, X. Tang,et al.(2023)ToolLLM: facilitating large language models to master 16000+ real-world apis.arXiv preprint arXiv:2307.16789.Cited by:§5.
• Y. Qu, Y. Jiang, B. Wang, Y. Mao, C. Wang, C. Liu, and X. Ji (2025)Latent reward: LLM-empowered credit assignment in episodic reinforcement learning.arXiv preprint arXiv:2412.11120.Cited by:§5.
• C. Rawles, S. Clinckemaillie, Y. Chang, J. Waltz, G. Lau, M. Fair, A. Li, W. Bishop, W. Li, F. Campbell-Ajala, D. Toyama, R. Berry, D. Tyamagundlu, T. Lillicrap, and O. Riva (2025)AndroidWorld: a dynamic benchmarking environment for autonomous agents.arXiv preprint arXiv:2405.14573.Cited by:§5.
• T. Schick, J. Dwivedi-Yu, R. Dessì, R. Raileanu, M. Lomeli, L. Zettlemoyer, N. Cancedda, and T. Scialom (2023)Toolformer: language models can teach themselves to use tools.InAdvances in Neural Information Processing Systems,Cited by:§1,§2.1,§5.
• J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov (2017)Proximal policy optimization algorithms.arXiv preprint arXiv:1707.06347.Cited by:§5.
• Serper.dev (2026)Serper: google search API.Note:https://serper.devCited by:§4.1.
• A. Setlur, C. Nagpal, A. Fisch, X. Geng, J. Eisenstein, R. Agarwal, A. Agarwal, J. Berant, and A. Kumar (2024)Rewarding progress: scaling automated process verifiers for LLM reasoning.arXiv preprint arXiv:2410.08146.Cited by:§1,§5.
• Z. Shao, P. Wang, Q. Zhu, R. Xu, J. Song, X. Bi, H. Zhang, M. Zhang, Y. K. Li, Y. Wu, and D. Guo (2024)DeepSeekMath: pushing the limits of mathematical reasoning in open language models.arXiv preprint arXiv:2402.03300.Cited by:§1,§2.1,§2.1,§5.
• N. Shinn, F. Cassano, E. Berman, A. Gopinath, K. Narasimhan, and S. Yao (2023)Reflexion: language agents with verbal reinforcement learning.arXiv preprint arXiv:2303.11366.Cited by:§5.
• H. Song, J. Jiang, Y. Min, J. Chen, Z. Chen, W. X. Zhao, L. Fang, and J. Wen (2025)R1-Searcher: incentivizing the search capability in LLMs via reinforcement learning.arXiv preprint arXiv:2503.05592.Cited by:§5.
• H. Sun, Z. Qiao, J. Guo, X. Fan, Y. Hou, Y. Jiang, P. Xie, F. Huang, and Y. Zhang (2025)ZeroSearch: incentivize the search capability of LLMs without searching.arXiv preprint arXiv:2505.04588.Cited by:§5.
• R. S. Sutton and A. G. Barto (2018)Reinforcement learning: an introduction.2 edition,MIT Press.Cited by:§1,§2.1,§5.
• R. S. Sutton (1988)Learning to predict by the methods of temporal differences.Machine Learning3,pp. 9–44.Cited by:§1,§2.2,§5.
• H. Tan, X. Yang, H. Chen, J. Shao, Y. Wen, Y. Shen, W. Luo, X. Du, L. Guo, and Y. Li (2026)Hindsight credit assignment for long-horizon LLM agents.arXiv preprint arXiv:2603.08754.Cited by:§5.
• Tongyi DeepResearch Team, B. Li, B. Zhang, D. Zhang, F. Huang, G. Li, G. Chen, H. Yin, J. Wu, J. Zhou,et al.(2025)Tongyi DeepResearch technical report.arXiv preprint arXiv:2510.24701.Cited by:§4.1.
• J. Uesato, N. Kushman, R. Kumar, F. Song, N. Siegel, L. Wang, A. Creswell, G. Irving, and I. Higgins (2022)Solving math word problems with process- and outcome-based feedback.arXiv preprint arXiv:2211.14275.Cited by:§1,§5.
• G. Wang, S. Dai, G. Ye, Z. Gan, W. Yao, Y. Deng, X. Wu, and Z. Ying (2026a)Information gain-based policy optimization: a simple and effective approach for multi-turn search agents.InInternational Conference on Learning Representations,Cited by:§5.
• H. Wang, C. T. Leong, J. Wang, J. Wang, and W. Li (2025a)SPA-RL: reinforcing LLM agents via stepwise progress attribution.arXiv preprint arXiv:2505.20732.Cited by:§5.
• H. Wang, Z. Hou, Y. Wei, J. Tang, and Y. Dong (2025b)SWE-Dev: building software engineering agents with training and inference scaling.InFindings of the Association for Computational Linguistics: ACL 2025,Cited by:§5.
• P. Wang, L. Li, Z. Shao, R. X. Xu, D. Dai, Y. Li, D. Chen, Y. Wu, and Z. Sui (2024a)Math-Shepherd: verify and reinforce LLMs step-by-step without human annotations.arXiv preprint arXiv:2312.08935.Cited by:§1,§5.
• X. Wang, Y. Chen, L. Yuan, Y. Zhang, Y. Li, H. Peng, and H. Ji (2024b)Executable code actions elicit better LLM agents.InInternational Conference on Machine Learning,Cited by:§5.
• X. Wang, B. Li, Y. Song, F. F. Xu, X. Tang, M. Zhuge, J. Pan, Y. Song, B. Li, J. Singh,et al.(2025c)OpenHands: an open platform for AI software developers as generalist agents.InInternational Conference on Learning Representations,Cited by:§5.
• Y. Wang, J. Mu, M. Jobanputra, Y. Wang, J. Lee, S. Oh, I. Valera, and V. Demberg (2026b)Sparse mixture-of-experts reward models learn interpretable and specialized experts for personalized preference modeling.arXiv preprint arXiv:2606.04284.Cited by:§5.
• Z. Wang, X. Zheng, K. An, C. Ouyang, J. Cai, Y. Wang, and Y. Wu (2025d)StepSearch: igniting LLMs search ability via step-wise proximal policy optimization.arXiv preprint arXiv:2505.15107.Cited by:§5.
• J. Wei, Z. Sun, S. Papay, S. McKinney, J. Han, I. Fulford, H. W. Chung, A. T. Passos, W. Fedus, and M. Glaese (2025a)BrowseComp: a simple yet challenging benchmark for browsing agents.arXiv preprint arXiv:2504.12516.Cited by:§4.1,§5.
• Y. Wei, O. Duchenne, J. Copet, Q. Carbonneaux, L. Zhang, D. Fried, G. Synnaeve, R. Singh, and S. I. Wang (2025b)SWE-RL: advancing LLM reasoning via reinforcement learning on open software evolution.InAdvances in Neural Information Processing Systems,Cited by:§5.
• J. Wu, Z. Xu, Q. Fu, and W. Yang (2025a)Cut the bill, keep the turns: affordable multi-turn search RL.Note:project pageCited by:§4.1.
• J. Wu, B. Li, R. Fang, W. Yin, L. Zhang, Z. Tao, D. Zhang, Z. Xi, G. Fu, Y. Jiang, P. Xie, F. Huang, and J. Zhou (2025b)WebDancer: towards autonomous information seeking agency.arXiv preprint arXiv:2505.22648.Cited by:§4.1,§5.
• Y. Xi, J. Lin, Y. Xiao, Z. Zhou, R. Shan, T. Gao, J. Zhu, W. Liu, Y. Yu, and W. Zhang (2025a)A survey of LLM-based deep search agents: paradigm, optimization, evaluation, and challenges.arXiv preprint arXiv:2508.05668.Cited by:§5.
• Z. Xi, J. Huang, C. Liao, B. Huang, H. Guo, J. Liu, R. Zheng, J. Ye, J. Zhang, W. Chen,et al.(2025b)AgentGym-RL: training LLM agents for long-horizon decision making through multi-turn reinforcement learning.arXiv preprint arXiv:2509.08755.Cited by:§5,§5.
• C. S. Xia, Y. Deng, S. Dunn, and L. Zhang (2024)Agentless: demystifying LLM-based software engineering agents.arXiv preprint arXiv:2407.01489.Cited by:§5.
• T. Xie, D. Zhang, J. Chen, X. Li, S. Zhao, R. Cao, T. J. Hua, Z. Cheng,et al.(2024)OSWorld: benchmarking multimodal agents for open-ended tasks in real computer environments.arXiv preprint arXiv:2404.07972.Cited by:§1,§5.
• S. Yan, A. Bahloul, E. Nie, S. Schwarzmann, R. Trivisonno, V. Tresp, and Y. Ma (2026)Memory-R2: fair credit assignment for long-horizon memory-augmented LLM agents.arXiv preprint arXiv:2605.21768.Cited by:§5.
• A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, C. Zheng, D. Liu, F. Zhou, F. Huang, F. Hu, H. Ge, H. Wei, H. Lin, J. Tang, J. Yang, J. Tu, J. Zhang, J. Yang, J. Yang, J. Zhou, J. Zhou, J. Lin, K. Dang, K. Bao, K. Yang, L. Yu, L. Deng, M. Li, M. Xue, M. Li, P. Zhang, P. Wang, Q. Zhu, R. Men, R. Gao, S. Liu, S. Luo, T. Li, T. Tang, W. Yin, X. Ren, X. Wang, X. Zhang, X. Ren, Y. Fan, Y. Su, Y. Zhang, Y. Zhang, Y. Wan, Y. Liu, Z. Wang, Z. Cui, Z. Zhang, Z. Zhou, and Z. Qiu (2025a)Qwen3 technical report.arXiv preprint arXiv:2505.09388.Cited by:§4.1.
• J. Yang, C. E. Jimenez, A. Wettig, K. Lieret, S. Yao, K. Narasimhan, and O. Press (2024)SWE-agent: agent-computer interfaces enable automated software engineering.arXiv preprint arXiv:2405.15793.Cited by:§5.
• J. Yang, K. Lieret, C. E. Jimenez, A. Wettig, K. Khandpur, Y. Zhang, B. Hui, O. Press, L. Schmidt, and D. Yang (2025b)SWE-smith: scaling data for software engineering agents.InAdvances in Neural Information Processing Systems,Cited by:§5.
• J. Yang, A. Prabhakar, K. Narasimhan, and S. Yao (2023)InterCode: standardizing and benchmarking interactive coding with execution feedback.InAdvances in Neural Information Processing Systems,Vol.36,pp. 23826–23854.Cited by:§5.
• Z. Yang, P. Qi, S. Zhang, Y. Bengio, W. W. Cohen, R. Salakhutdinov, and C. D. Manning (2018)HotpotQA: a dataset for diverse, explainable multi-hop question answering.InProceedings of the 2018 Conference on Empirical Methods in Natural Language Processing,pp. 2369–2380.Cited by:§1,§5.
• S. Yao, H. Chen, J. Yang, and K. Narasimhan (2022)WebShop: towards scalable real-world web interaction with grounded language agents.InAdvances in Neural Information Processing Systems,Cited by:§1,§2.1,§5.
• S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao (2023)ReAct: synergizing reasoning and acting in language models.InInternational Conference on Learning Representations,Cited by:§A.3,§1,§2.1,§4.1,§5.
• C. Ye, Z. Yu, Z. Zhang, H. Chen, N. Sadagopan, J. Huang, T. Zhang, and A. Beniwal (2025)Beyond correctness: harmonizing process and outcome rewards through RL training.arXiv preprint arXiv:2509.03403.Cited by:§1.
• L. Yuan, W. Li, H. Chen, G. Cui, N. Ding, K. Zhang, B. Zhou, Z. Liu, and H. Peng (2024)Free process rewards without process labels.arXiv preprint arXiv:2412.01981.Cited by:§1,§5.
• A. Zeng, M. Liu, R. Lu, B. Wang, X. Liu, Y. Dong, and J. Tang (2023)AgentTuning: enabling generalized agent abilities for LLMs.arXiv preprint arXiv:2310.12823.Cited by:§5.
• C. Zhang, Z. Yang, J. Liu, Y. Han, X. Chen, Z. Huang, B. Fu, and G. Yu (2023)AppAgent: multimodal agents as smartphone users.arXiv preprint arXiv:2312.13771.Cited by:§5.
• H. Zhang, X. Liu, B. Lv, X. Sun, B. Jing, I. L. Iong, Z. Hou, Z. Qi, H. Lai, Y. Xu,et al.(2025a)AgentRL: scaling agentic reinforcement learning with a multi-turn, multi-task framework.arXiv preprint arXiv:2510.04206.Cited by:§5,§5.
• K. Zhang, J. Li, G. Li, X. Shi, and Z. Jin (2024a)CodeAgent: enhancing code generation with tool-integrated agent systems for real-world repo-level coding challenges.InProceedings of the 62nd Annual Meeting of the Association for Computational Linguistics,pp. 13643–13658.External Links:DocumentCited by:§5.
• W. Zhang, Y. Li, Y. Bei, J. Luo, G. Wan, L. Yang, C. Xie, Y. Yang, W. Huang, C. Miao,et al.(2025b)From web search towards agentic deep research: incentivizing search with reasoning agents.arXiv preprint arXiv:2506.18959.Cited by:§5.
• Y. Zhang, M. Li, D. Long, X. Zhang, H. Lin, B. Yang, P. Xie, A. Yang, D. Liu, J. Lin, F. Huang, and J. Zhou (2025c)Qwen3 embedding: advancing text embedding and reranking through foundation models.arXiv preprint arXiv:2506.05176.Cited by:§4.1,§4.1.
• Y. Zhang, H. Ruan, Z. Fan, and A. Roychoudhury (2024b)AutoCodeRover: autonomous program improvement.InProceedings of the ACM International Symposium on Software Testing and Analysis,pp. 1592–1604.External Links:DocumentCited by:§5.
• Q. Zhao, R. Wang, D. Xu, D. Zha, and L. Liu (2025a)R-Search: empowering LLM reasoning with search via multi-reward reinforcement learning.arXiv preprint arXiv:2506.04185.Cited by:§5.
• W. Zhao, X. Wang, C. Ma, L. Kong, Z. Yang, M. Tuo, X. Shi, Y. Zhai, and X. Cai (2025b)MUA-RL: multi-turn user-interacting agent reinforcement learning for agentic tool use.arXiv preprint arXiv:2508.18669.Cited by:§5,§5.
• C. Zheng, S. Liu, M. Li, X. Chen, B. Yu, C. Gao, K. Dang, Y. Liu, R. Men, A. Yang, J. Zhou, and J. Lin (2025a)Group sequence policy optimization.arXiv preprint arXiv:2507.18071.Cited by:§4.1.
• L. Zheng, W. Chiang, Y. Sheng, S. Zhuang, Z. Wu, Y. Zhuang, Z. Lin, Z. Li, D. Li, E. P. Xing, H. Zhang, J. E. Gonzalez, and I. Stoica (2023)Judging LLM-as-a-judge with MT-Bench and chatbot arena.InAdvances in Neural Information Processing Systems,Cited by:§1.
• Y. Zheng, D. Fu, X. Hu, X. Cai, L. Ye, P. Lu, P. Liu,et al.(2025b)DeepResearcher: scaling deep research via reinforcement learning in real-world environments.arXiv preprint arXiv:2504.03160.Cited by:§5.
• S. Zhou, F. F. Xu, H. Zhu, X. Zhou, R. Lo, A. Sridhar, X. Cheng, T. Ou, Y. Bisk, D. Fried, U. Alon, and G. Neubig (2024)WebArena: a realistic web environment for building autonomous agents.InInternational Conference on Learning Representations,Cited by:§1,§5.

Appendix AAppendix

A.1Training Hyperparameters

TablesA.1andA.1summarize the script-level hyperparameters used for the Qwen3-30B-A3B-Thinking-2507 Search-R1 training run. The shared launch script keeps turn-level scoring disabled by default for a single-node colocated layout unless a remote reference-model scoring endpoint is provided;TRACEruns enable this path and use the settings in TableA.1.

CategoryHyperparameterValueRolloutRollout engineSGLangGPUs per rollout engine11Running requests6464Rollout batch size6464Samples per prompt88Sampling temperature1.01.0Sampling top-pp1.01.0Max trajectory length48,00048{,}000tokensMax response tokens40964096tokensMax tool turns6060Max observation tokens20482048tokensRollout timeout240240sEvaluationEval samples per prompt11Eval max response length81928192tokensEval max context length72,00072{,}000tokensEval max tool turns8080tool turnsOptimizationGlobal batch size128128OptimizerAdamLearning rate scheduleConstantLearning rate1×10−61\times 10^{-6}Weight decay0.010.01Adamβ1\beta_{1}0.90.9Adamβ2\beta_{2}0.980.98Optimizer offloadCPU offload with overlapped D2H/H2D transferKL loss0Entropy coefficient0.000.00Clip ratio lower bound0.200.20Clip ratio upper bound0.280.28Loss accountingPer-token lossTISEnabledTable 3: Core training, rollout, and optimization hyperparameters for the Qwen3-30B-A3B-Thinking-2507 Search-R1 training run.

CategoryHyperparameterValueOutcome rewardOutcome reward coefficient1.01.0Format score0.10.1Zero-advantage handlingReturn zero when the group advantage is zeroTurn creditTurn-reward scoringEnabled forTRACEruns with a remote reference-model scoring endpointTurn-reward weight0.20.2Training gap offsetϵtrain\epsilon_{\mathrm{train}}0.10.1Ground-truth fieldground_truthAdvantage modeturn_advantagesRemaining-space transformEnabledTransform modelog_ratioLegacy transform stabilizer0.0010.001TD look-ahead horizonK=3K=3TD discountγtd=0.8\gamma_{\mathrm{td}}=0.8KK-step normalizationEnabledTerminal-outcome fillEnabledTerminal-outcome scale2.02.0Advantage normalizationnonePost-group normalizationFalseAdvantage clipping0.00.0Table 4:TRACE-specific reward and turn-credit hyperparameters from the Search-R1 launch script. The training gap offset is theϵ\epsilonused indk=−ℓ¯k+ϵd_{k}=-\bar{\ell}_{k}+\epsilon; the legacy transform stabilizer is a separate script parameter and is not used as the log-ratio gap offset in the reportedTRACEruns.

A.2Comparison with Raw Log-Probability Differences

This section expands on the choice of the log-ratio state value in Eq.6and the resulting TD action reward in Eq.7. For a fixed rollout, writeℓ¯k\bar{\ell}_{k}for the raw average gold-answer log-probability anddk=−ℓ¯k+ϵd_{k}=-\bar{\ell}_{k}+\epsilonfor the remaining answer-likelihood gap. The raw log-probability differenceΔkℓ=ℓ¯k+1−ℓ¯k\Delta^{\ell}_{k}=\bar{\ell}_{k+1}-\bar{\ell}_{k}telescopes toℓ¯T−ℓ¯0\bar{\ell}_{T}-\bar{\ell}_{0}and therefore preserves the ordering of two rollouts from the same prompt when they share the same initial state. However, raw differences measure absolute improvement in log-probability, not the fraction of the remaining gap that a turn closes. The linear remaining-gap scoreΔ~klin=(ℓ¯k+1−ℓ¯k)/dk\widetilde{\Delta}^{\mathrm{lin}}_{k}=(\bar{\ell}_{k+1}-\bar{\ell}_{k})/d_{k}and the TD reward from the log-ratio value,Ck=Vk+1−Vk=log⁡(dk/dk+1)C_{k}=V_{k+1}-V_{k}=\log(d_{k}/d_{k+1}), both correct this scale issue by rewarding relative gap reduction, but only the log-ratio value also retains an endpoint-only telescoping form.

PropertyRaw deltaΔkℓ\Delta^{\ell}_{k}Linear remaining gapΔ~klin\widetilde{\Delta}^{\mathrm{lin}}_{k}Log-ratio TD rewardCkC_{k}Definitionℓ¯k+1−ℓ¯k\bar{\ell}_{k+1}-\bar{\ell}_{k}(ℓ¯k+1−ℓ¯k)/dk(\bar{\ell}_{k+1}-\bar{\ell}_{k})/d_{k}Vk+1−Vk=log⁡(dk/dk+1)V_{k+1}-V_{k}=\log(d_{k}/d_{k+1})Telescopingℓ¯T−ℓ¯0\bar{\ell}_{T}-\bar{\ell}_{0}No endpoint-only formVT−V0=log⁡(d0/dT)V_{T}-V_{0}=\log(d_{0}/d_{T})Order preservationYes, for sharedℓ¯0\bar{\ell}_{0}Not guaranteedYes, for sharedℓ¯0\bar{\ell}_{0}Per-step unitAbsolute improvementRelative gap reductionRelative gap reductionLarge remaining gapUniform scalingDownweights early large-gap stepsDownweights early large-gap stepsSmall remaining gapUniform scalingStrongly amplifies near-terminal stepsModerately amplifies near-terminal stepsNumerical behaviorStableCan spike whendkd_{k}is smallFinite with offset and logarithmic growthTable 5: Comparison of raw log-probability differences, a linear remaining-gap normalization, and the TD reward from the log-ratio value used byTRACE. The log-ratio value is the only relative-gap formulation whose cumulative action reward depends only on the initial and final states.

An offline diagnostic on a held-out BrowseComp-Plus evaluation trace further supports this choice. We compared the cumulative score from each formulation against the final reference-model log-probability and the binary outcome reward over830830rollouts containing37423742tool turns, using a separate diagnostic offsetϵdiag=10−3\epsilon_{\mathrm{diag}}=10^{-3}for the two remaining-gap normalizations. The log-ratio score has the strongest correlation with both endpoint quality and final correctness, while also giving the best pairwise ranking accuracy among rollouts with similar initial raw log-probabilities.

MetricRawLinearLog-ratioCorrelation with finalℓ¯T\bar{\ell}_{T}0.4250.4250.7210.7210.751\mathbf{0.751}Correlation with positive outcome reward0.6030.6030.6800.6800.713\mathbf{0.713}Pairwise ranking accuracy,|Δ​ℓ¯0|≤0.2|\Delta\bar{\ell}_{0}|\leq 0.297.34%97.34\%93.13%93.13\%98.24%\mathbf{98.24\%}Table 6: Offline comparison of transition-credit formulations on a held-out evaluation trace. Scores are computed by summing turn-level credits within each rollout before comparing to the final reference-model score or outcome reward.

The difference is visible at the turn level. Consider two transitions with nearly identical raw gains: one moves fromℓ¯=−5.1187\bar{\ell}=-5.1187toℓ¯=−1.5712\bar{\ell}=-1.5712(Δℓ=3.5475\Delta^{\ell}=3.5475), while another moves fromℓ¯=−10.6570\bar{\ell}=-10.6570toℓ¯=−7.1061\bar{\ell}=-7.1061(Δℓ=3.5509\Delta^{\ell}=3.5509). Raw delta treats them as essentially equal. In contrast, the corresponding log-ratio TD rewards are1.18061.1806and0.40520.4052, respectively, because the first transition closes a much larger fraction of its remaining gap. This behavior is desirable for long-horizon search: decisive evidence localization near the answer should receive more credit than an equally sized absolute improvement that still leaves the rollout far from predicting the gold answer.

A.3Search-Agent Task and Interface

We instantiateTRACEon a deliberately simple closed-corpus search task. Given a questionxx, the agent follows an interleaved reasoning-and-acting pattern[Yaoet al.,2023]: each assistant turn contains private reasoning and either one browser tool call or a final answer. If the turn contains a valid tool call, the environment executes it against the retrieval corpus and appends the resulting observation before the next assistant turn. Keeping this interface small helps isolate the effect of the training signal from improvements due to a more specialized planner or tool stack.

Rollouts stop when the model emits a final<answer>span, reaches the tool-turn limit, or hits a context or generation limit. Training loss is applied only to assistant-generated tokens, while tool observations are masked. The outcome reward checks whether the normalized final answer exactly matches the gold answer, with a small format component for well-formed answers. We also record lightweight trajectory diagnostics, including tool-call counts, repeated queries, reopened documents, repeated in-document searches, navigation errors, and answer-format validity.

The environment exposes three browsing tools over the retrieval corpus. TableA.3summarizes the tool schema used in all experiments.

ToolArgumentType/defaultDescriptionbrowser.searchquerystring, requiredSearch query string.topninteger, default1010Number of top results to return.browser.openidinteger, default−1-1Result index from the most recent search, using zero-based indexing;−1-1rereads the current page.locinteger, default−1-1Starting line number;−1-1uses the beginning of the page or a relevant passage.num_linesinteger, default−1-1Number of lines to display;−1-1uses the environment default.browser.findpatternstring, requiredExact text pattern to search for in the currently open document.cursorinteger, default−1-1Page cursor to search in;−1-1searches the current page.Table 7: Browser tool schema exposed to the search agent. Search returns titles, URLs, and summaries for the top retrieved documents; open displays document content from the closed corpus; find returns matching line numbers in the currently open document.

The assistant’s reasoning, tool call, and final-answer formatting tokens are part of the assistant turn for training purposes, while tool observations are environment outputs and remain masked from the policy-gradient loss.

A.4Synthetic Training Data

Training a search agent with verifiable reinforcement learning requires questions whose rewards remain informative beyond the single-hop retrieval regime. If the training distribution is dominated by direct lookup questions, the agent quickly saturates: once it can issue one or two effective searches, additional training provides little pressure to learn deeper information gathering or cross-document synthesis. We therefore construct a synthetic training set of hard multi-document identification questions designed to require chained search, reasoning over at least two irreplaceable source documents, and resistance to trivial answer lookup.

A.4.1Generation Pipeline

The pipeline starts from a document corpus, stored as parquet files or a Hugging Face dataset, together with a related-document index in JSONL format. For each anchor document, we retrieve the top-KrelK_{\mathrm{rel}}related documents whose similarity score exceeds a minimum threshold and use this set as the source context for question generation. This related-document context increases the probability that a valid question can connect facts across documents while still requiring the model to identify which documents are necessary.

For every anchor document, we run a best-of-BBgeneration procedure with rejection sampling. Each independent candidate is generated by an LLM prompted to produce a hard question, its answer, and an explicit reasoning chain over the provided sources. If a candidate fails verification, the rejection reason is fed back to the generator for up to a fixed number of regeneration attempts. Candidates that pass the initial checks are then sent to an independent answer verification stage: a separate LLM call receives only the question and source documents, not the proposed answer, and must derive the answer from scratch. We discard the example unless the independently derived answer matches the proposed answer under fuzzy matching. Among the remaining candidates, we keep the highest-scoring example and write it to the training JSONL.

A.4.2Question Templates

The generator is constrained to produce questions from a small set of templates that naturally require cross-document reasoning. TableA.4.2summarizes the templates used in our data synthesis pipeline.

TypeDescriptionBRIDGE_ENTITYIdentify a masked entity, then retrieve one of its attributes from another document.INTERSECTIONFind the unique entity satisfying independent conditions from different documents.COUNTING_FILTEREDCount members of a set defined by cross-document criteria.COMPARATIVECompare obfuscated entities using facts distributed across documents.REVERSE_LOOKUPGiven an obfuscated output, identify its creator or source through another document.Table 8: Question templates used to synthesize hard multi-document QA examples.

To prevent direct keyword lookup, each question applies at least one obfuscation operation. Time expressions may be blurred into relative or approximate descriptions; entity names may be masked; names may be replaced by role descriptions; and quantitative constraints may be converted into qualitative ones. These transformations force the agent to first resolve what should be searched for and only then retrieve the evidence needed to answer.

A.4.3Verification and Selection

Quality control combines programmatic checks with LLM-based verification. The programmatic check requires the reasoning chain to cite at least two distinct source URLs. The LLM verifier then evaluates whether the question is actually hard, grounded, and multi-document. It rejects candidates whose answer appears directly in the question, whose constraints can be satisfied from a single source, whose answer is retrievable with a trivial query, or whose reasoning chain lacks a genuine synthesis step. It also filters unsupported or hallucinated answers and examples in which one of the cited documents is redundant.

The final selection score favors candidates that pass both quality and answer verification, succeed in fewer regeneration attempts, use longer reasoning chains, cite more distinct documents, and assign primary roles to all cited documents. It penalizes questions that leak the answer or produce overly long answers. This scoring rule selects examples that are not merely answerable, but useful for training long-horizon search behavior: the agent must issue multiple queries, maintain intermediate entities, and combine evidence from multiple documents before producing the final answer.

A.5Qualitative Analysis of the Turn Credit

Outcome-only GRPO assigns one trajectory-level advantage to every action in a rollout, obscuring whether an individual turn retrieves decisive evidence, adds redundant context, or discards an answer already supported by the transcript. We examine five successful and five failed trajectories from rollout batches 0140–0149. In each successful case, we highlight the tool call that closes most of the answer-likelihood gap; in each failed case, the trajectory first reaches an answer-secured prefix and then loses it after one diagnostic tool call. Each example reports the complete question and answer, the one-step credit sequence, and the most diagnostic tool call together with its credit.

For a trajectory withTTtool calls,search_r1_turn_valuescontainsT+2T+2frozen-reference values: one before tool use, one after each tool observation, and one after answer generation. LargerVVindicates greater closure of the gold-answer likelihood gap; we useV≥−0.3V\geq-0.3as a diagnostic definition of ananswer-securedprefix. Following Eq.7,δk=V​(Sk+1)−V​(Sk)\delta_{k}=V(S_{k+1})-V(S_{k})is assigned to zero-based tool turnkk, with the final difference assigned to answer generation. We mark positive progress ingreen, harmful transitions inred, and near-zero or mixed credit ingray. Tool calls use the notationbrowser.tool(argument=value); search-relativeopenIDs are accompanied by the returned page name.

A.5.1Successful Trajectories: Localizing the Turn That Wins

Positive turn example P1: A decisive search resolves the distractorQuestion.Starting from the job ad for a major Canadian flag carrier where line-maintenance applicants are asked to speak English plus German, trace to that carrier’s separate maintenance leadership posting that gives an edge to bilingual candidates, then compare this carrier against its express-partner company that says it was recognized as a top small/medium employer around the mid-2010s. Which company is associated with the mid-2010s employer recognition (rather than the bilingual-preference maintenance posting)?Answer:Air Georgian.Final answer:✓\checkmarkCorrectTurn-credit distribution.δ=[+6.39,+0.59,+0.10,+0.05].\delta=[+6.39,+0.59,+0.10,+0.05].Critical turn.Turn 0.browser.search(query=question) Turn credit:δ0=+6.39\delta_{0}=+6.39. The salient entity in the question is Air Canada, but the result set surfaces the Air Georgian careers page and thereby introduces the non-obvious express-partner answer. The subsequent page open secures the answer, while the literalfind(pattern=“2015”)adds only+0.10+0.10after it is already secured.

Positive turn example P2: Only the answer-bearing document earns creditQuestion.In the rail-safety material from around the early 2010s, a conference is said to be opened by a senior infrastructure executive (not named here). Follow that trail to the police-led plan later described as helping prevent rail suicides, then move to a later partnership update and identify the person quoted as managing the suicide-prevention programme for the rail industry. Who is that person?Answer:Ian Stevens.Final answer:✓\checkmarkCorrectTurn-credit distribution.δ=[+1.63,−1.03,−1.04,+6.05,+0.03].\delta=[+1.63,-1.03,-1.04,+6.05,+0.03].Critical turn.Turn 3.browser.open(id=2)(Samaritans–Network Rail partnership update) Turn credit:δ3=+6.05\delta_{3}=+6.05. After two plausible but non-answer-bearing opens, this page names Ian Stevens and supplies the missing discriminative fact.

Positive turn example P3: A decisive open makes confirmation redundantQuestion.Identify the venue where the Nepali boxer was defeated by the Filipino Olympian in a unanimous decision, if that Filipino was the same athlete once knocked out in a world-title rematch by the Thai ex-IBF flyweight champion who made an impressive Rio start around the mid-2010s.Answer:Jakarta Expo Boxing Hall.Final answer:✓\checkmarkCorrectTurn-credit distribution.δ=[+0.88,+5.86,+0.00,−0.00].\delta=[+0.88,+5.86,+0.00,-0.00].Critical turn.Turn 1.browser.open(id=1)(Rappler match report) Turn credit:δ1=+5.86\delta_{1}=+5.86. The report supplies “at the Jakarta Expo Boxing Hall” and immediately secures the venue. The subsequent literalfindreceives+0.00+0.00, illustrating that repeated confirmation cannot inflate the telescoping signal.

Positive turn example P4: The search-result snippet secures the answerQuestion.Starting from the maker described as doing Friday evening Arizona “drops” and claiming a no-open-edge signature stitch, follow that trail to the similarly sized product from the black-label line for everyday-carry users, then compare those with the summer-themed, hand-dyed Atlanta shop item that comes with a holographic extra. Which brand is the one that explicitly says no other maker uses its edge/lanyard construction method?Answer:Godspeed Tactical.Final answer:✓\checkmarkCorrectTurn-credit distribution.δ=[+5.48,+0.06,+0.00].\delta=[+5.48,+0.06,+0.00].Critical turn.Turn 0.browser.search(query=question) Turn credit:δ0=+5.48\delta_{0}=+5.48. The result snippet exposes the Godspeed Tactical identity and exclusivity claim before any page is opened. The decisive credit therefore belongs to the search-result observation rather than the subsequent page read.

Positive turn example P5: A reformulated search rescues a stalled rolloutQuestion.In a software podcast episode from around the early 2020s featuring two engineering guests, an ad segment promotes an open-source time-series database and references that brand’s event series. For the London edition that was moved online during the pandemic period, what was the earlier company name (from around the early 2010s) that immediately preceded the host company’s later name change associated with that database?Answer:Errplane.Final answer:✓\checkmarkCorrectTurn-credit distribution.δ=\displaystyle\delta={}[+1.18,−0.12,−0.19,−0.14,\displaystyle[+18,-12,-19,-14,+0.43,+5.44,+0.02,+0.00].\displaystyle\phantom{[}+43,+44,+02,+00].Critical turn.Turn 5.browser.search(query=“influxdata company name change from early 2010s to later name”) Turn credit:δ5=+5.44\delta_{5}=+5.44. After four stalled probes, this reformulated query returns “Errplane became InfluxData in 2015,” localizing nearly all progress in the eight-turn trajectory to this rescue query.

A.5.2Negative Trajectories: Localizing the Tool Call That Loses

Every failure below reaches an answer-secured prefix and then undergoes a single large negative transition. The examples differ in what triggers the collapse: a query-echo self-match, an over-interpreted no-match, a match in the wrong context, an over-literal type comparison, or a phrase copied from the question rather than read from the page.

Negative turn example N1: A query-echo self-match discards a secured answerQuestion.In a post from around the mid-2010s by a youth organizer planning an end-of-season teen church overnight, the writer jokes about a very high-voltage fence and doubts a loft drop trust exercise. Use that to find another reflection from roughly the same era where students mention trusting the rope-holder during a heights course, then compare the fear-focused activity named there with the similarly fear-themed activity listed in a different school day-log that also mentions climbing, archery, a blindfold obstacle course, and a ladder challenge. Which fear-themed activity title comes later in alphabetical order?Gold answer:Leap of Faith.Model answer:loft drop trust exercise.Final answer:×\boldsymbol{\times}IncorrectTurn-credit distribution.δ=[+1.47,+0.13,+1.49,−0.00,−4.83,−0.78].\delta=[+1.47,+0.13,+1.49,-0.00,-4.83,-0.78].Critical turn.Turn 4.browser.find(pattern=“loft drop trust exercise”, cursor=0) Turn credit:δ4=−4.83\delta_{4}=-4.83. After the gold answer is secured, this call matches the model’s earlier query echo rather than a page-supported title. Accepting its own paraphrase as a second candidate discards the answer and produces the sharp negative credit.

Negative turn example N2: A no-match becomes a false factual negativeQuestion.Starting from the article about a TV doctor’s health-content partnership launched on a global blood-disorder awareness observance in the late 2010s, use that observance date to find another program episode from around the mid-2010s featuring three women in the same disease space. Then use the early-2010s Pittsburgh interview with the longtime local nonprofit executive (described by role, not name) to filter that trio by shared family name. How many women in the trio match that surname?Gold answer:22.Model answer:0.Final answer:×\boldsymbol{\times}IncorrectTurn-credit distribution.δ=\displaystyle\delta={}[+2.31,+0.10,−1.32,+0.09,\displaystyle[+31,+10,-32,+09,+0.35,+0.98,−4.05,−1.09].\displaystyle\phantom{[}+35,+98,-05,-09].Critical turn.Turn 6.browser.find(pattern=“Bush”)(returns “No matches”) Turn credit:δ6=−4.05\delta_{6}=-4.05. Although the preceding prefix is answer-secured, the model interprets absence from an incomplete episode page as evidence that none of the women is a Bush. The negative credit localizes this invalid factual-negative inference.

Negative turn example N3: A successful find locks onto distractor contextQuestion.Starting from a celebrity-photo page from around the mid-2010s that praises two aristocratic sisters for attending separate events in England, follow to the article comparing the elder future queen consort’s conservative red charity gown with her younger sibling’s more revealing red look earlier that month. Using those two sisters as the candidate set, then check a later royal-fashion tag page from the early 2020s and count how many of those candidates are explicitly mentioned in the sentence about children serving as page attendants and bridesmaid at the younger sister’s wedding.Gold answer:22.Model answer:11.Final answer:×\boldsymbol{\times}IncorrectTurn-credit distribution.δ=\displaystyle\delta={}[+2.19,−0.35,+0.10,−1.03,+0.96,\displaystyle[+19,-35,+10,-03,+96,+0.50,−3.63,+0.19,−1.22].\displaystyle\phantom{[}+50,-63,+19,-22].Critical turn.Turn 6.browser.find(pattern=“Pippa Middleton”) Turn credit:δ6=−3.63\delta_{6}=-3.63. The call succeeds, but matches “as she did for her aunt Pippa Middleton last year,” a sentence about the wrong wedding. From a just-secured prefix, the model anchors on this superficially relevant single-name match and later answers11. Tool success is therefore not equivalent to information progress.

Negative turn example N4: Exact-string matching replaces a type comparisonQuestion.Using a post from around the early 2010s by the person who says he ordered interchangeable raw-brass ring parts as your starting clue, go to a different instrument-forum thread that references a repair specialist by first name and mentions that writer considering an instrument with many strings. From that thread, take the distinct instrument types named there as the candidate set. Then check a separate dealer page listing “other instrument offerings” from the mid-2000s era and count how many of those candidate types are present there.Gold answer:11.Model answer:0.Final answer:×\boldsymbol{\times}IncorrectTurn-credit distribution.δ=[+1.42,−0.10,+0.82,+0.08,−3.41,−0.97].\delta=[+1.42,-0.10,+0.82,+0.08,-3.41,-0.97].Critical turn.Turn 4.browser.find(pattern=“autoharp”)(returns “No matches”) Turn credit:δ4=−3.41\delta_{4}=-3.41. The dealer page has already secured the answer, but the task requires comparing the candidates by instrument type. The model instead probes one literal string and treats its absence as proof that the intersection is empty, discarding the page-level evidence.

Negative turn example N5: A prompt phrase is mistaken for page textQuestion.Using the workshop notice from around the early 2010s that mentions a big northern English city and a hotel-branded venue, trace forward to a later full-day procurement training page to recover a per-attendee cost, then apply that amount as a strict threshold to the industry-only Canadian pricing workshops held a few years afterward. How many city sessions in that Canadian notice have fees greater than that threshold?Gold answer:22.Model answer:0.Final answer:×\boldsymbol{\times}IncorrectTurn-credit distribution.δ=\displaystyle\delta={}[+2.00,+0.43,+0.06,−2.46,\displaystyle[+00,+43,+06,-46,+0.40,+1.98,−3.48,−1.03].\displaystyle\phantom{[}+40,+98,-48,-03].Critical turn.Turn 6.browser.find(pattern=“fees greater than”)(returns “No matches”) Turn credit:δ6=−3.48\delta_{6}=-3.48. The Canadian workshop page has already supplied the city-level fees. The model nevertheless searches for a comparison phrase copied from the question rather than comparing the listed numbers, then over-interprets the no-match and answers0.

Across the positive cases, nearly all credit lands on thesearchoropenthat first supplies the missing discriminative fact; redundant probes and post-hocfindcalls remain near zero. Across the negative cases, all five trajectories first reach the answer-secured region, after which one misleadingfindreceives the dominant penalty. The calls cover both empty matches that are over-interpreted and successful matches in the wrong context, showing that tool completion alone does not imply progress. Outcome-only GRPO cannot express any of these within-trajectory distinctions because it assigns every turn the same trajectory-level advantage.