One-sentence Summary

Researchers from the University of Wisconsin–Madison and Microsoft Research propose TRACE (Turn-level Reward Assignment via Credit Estimation), a dense credit-assignment method for long-horizon agentic reinforcement learning that computes per-action rewards as Temporal-Difference changes in log-ratio state values from a frozen reference model, thereby eliminating the need for a critic or process labels, and raises Qwen3-4B from 7.2 to 35.6 on the BrowseComp-Plus benchmark while enabling faster convergence.

Key Contributions

• TRACE is a critic-free credit-assignment method that converts gold-answer log-probabilities from a frozen reference model into log-ratio state values and computes per-action rewards as temporal-difference changes at tool-call boundaries, avoiding any critic, process labels, or Monte Carlo continuations.
• Applied with pure RL and no cold-start SFT, TRACE improves long-horizon search agents: on BrowseComp-Plus, Qwen3-4B rises from 7.2 to 35.6 and Qwen3-30B-A3B from 8.4 to 42.6, with learning curves showing earlier improvement and faster convergence than outcome-only GRPO.
• The learned search behavior transfers to open-web benchmarks, and the turn-level credit complements outcome-based training to reduce reward sparsity on compact-answer tasks without step-label annotation or a trained critic.

Introduction

Large language model agents now tackle complex, multi-step tasks like web navigation and code generation by interleaving reasoning with tool calls. Reinforcement learning with verifiable rewards has proven effective for short-horizon reasoning, but in agentic trajectories a single terminal outcome signal cannot distinguish which intermediate actions were useful, redundant, or harmful. Prior work on process supervision can provide denser feedback but typically relies on step-level labels, a strong LLM judge, or a trained process reward model whose scores may drift from final-answer correctness. The authors introduce TRACE, a critic-free credit assignment framework that uses a frozen reference model to measure how much each tool interaction makes the gold answer more predictable, then assigns turn-level rewards via temporal-difference changes while preserving the outcome-based verifiable reward as the final training anchor.

Method

In agentic reinforcement learning, a policy LLM solves prompts by interleaving assistant tokens, tool calls, and tool observations. A major challenge in this setting is credit assignment, as the terminal reward supervises a long sequence of heterogeneous policy decisions without identifying which specific turns contributed to the final answer. To address this, the authors introduce TRACE, a critic-free credit-assignment method for long-horizon agent post-training. Instead of learning a critic over sparse terminal rewards, TRACE measures whether each tool interaction makes the gold answer more predictable under a frozen reference model.

Refer to the framework diagram below:

TRACE splits rollouts at tool-call boundaries to construct credit targets for each transition. For a sampled trajectory with a gold answer, the method evaluates the prefix state $S_k$Sk​ using a frozen reference model $\pi_{\mathrm{ref}}$πref​. The average gold-answer log-probability for state $S_k$Sk​ is computed as: $\bar{\ell}_k = \frac{1}{|y^\star|} \sum_{t=1}^{|y^\star|} \log \pi_{\mathrm{ref}}(y_t^\star \mid S_k, y_{<t}^\star) \leq 0.$ℓˉk​=∣y⋆∣1​∑t=1∣y⋆∣​logπref​(yt⋆​∣Sk​,y<t⋆​)≤0. A larger (less negative) $\bar{\ell}_k$ℓˉk​ indicates that the current transcript contains more evidence for generating the gold answer. To make this score suitable for credit assignment, the authors model the state value as the relative closure of the initial answer-likelihood gap. Defining $d_k = -\bar{\ell}_k + \epsilon$dk​=−ℓˉk​+ϵ with an offset $\epsilon > 0$ϵ>0, the state value is set to: $V(S_k) = \log \frac{d_0}{d_k} = \log \frac{-\bar{\ell}_0 + \epsilon}{-\bar{\ell}_k + \epsilon}.$V(Sk​)=logdk​d0​​=log−ℓˉk​+ϵ−ℓˉ0​+ϵ​. This ensures $V(S_0) = 0$V(S0​)=0, and a larger $V(S_k)$V(Sk​) means the action-observation history has closed a larger fraction of the initial gap.

With no intermediate environment reward and a discount of 1, the credit assigned to a transition is the one-step temporal-difference change in value: $\delta_k = V(S_{k+1}) - V(S_k) = \log \frac{d_k}{d_{k+1}}.$δk​=V(Sk+1​)−V(Sk​)=logdk+1​dk​​. This credit is positive when the action and observation make the gold answer more likely, and negative when the transition moves away from the answer. To capture delayed tool effects, the authors use a truncated K-step TD backup. The local progress credit assigned to the current turn is: $c_{g,k}^{(K)} = \frac{1}{Z_{g,k}} \sum_{u=k}^{h_{g,k}} \gamma_{\mathrm{td}}^{u-k} \delta_{g,u},$cg,k(K)​=Zg,k​1​∑u=khg,k​​γtdu−k​δg,u​, where $\gamma_{\mathrm{td}}$γtd​ discounts delayed evidence. When the backup window reaches the end of the trajectory, the last turns are anchored to the verifiable outcome signal: $r_{g,k}^{\mathrm{turn}} = c_{g,k}^{(K)} + \mathbf{1}[h_{g,k} = T_g - 1] \lambda_{\mathrm{term}} \gamma_{\mathrm{td}}^{T_g - k} A_g^{\mathrm{out}}.$rg,kturn​=cg,k(K)​+1[hg,k​=Tg​−1]λterm​γtdTg​−k​Agout​. Here, $A_g^{\mathrm{out}}$Agout​ is the standard Group Relative Policy Optimization group-relative advantage.

Finally, the TD-derived turn credit is jointly optimized with the GRPO outcome reward. The mixed per-token advantage for tool-interaction tokens is: $\hat{A}_{g,t} = \alpha_{\mathrm{out}} A_g^{\mathrm{out}} + \alpha_{\mathrm{turn}} r_{g,\mathrm{turn}(t)}^{\mathrm{turn}},$A^g,t​=αout​Agout​+αturn​rg,turn(t)turn​, where $\alpha_{\mathrm{out}}$αout​ and $\alpha_{\mathrm{turn}}$αturn​ control the relative strength of terminal correctness and turn-level credit. The authors optimize a clipped GRPO objective that incorporates this mixed advantage, keeping the standard group-relative outcome signal while adding dense turn-level credit without normalizing the turn values across the prompt group.

Experiment

These experiments evaluate TRACE, a dense turn-level credit assignment method, on synthetic multi-document search tasks using Qwen3-based agents. Main results show that TRACE substantially improves long-horizon tool use over outcome-only RL baselines, both on the closed training corpus and on open-web benchmarks, indicating transferable search strategies. Learning dynamics reveal that TRACE converges faster and yields better policies, while ablations confirm that the log-ratio credit formulation and moderate tuning of the turn-level reward and look-ahead horizon are critical for its effectiveness.

TRACE greatly improves base-model tool use on long-horizon deep-research benchmarks, without any cold-start SFT, agentic mid-training, or live-web data. Adding turn-level temporal-difference credit to an outcome reward raises the closed-web BrowseComp-Plus score from 7.2 to 35.6 for Qwen3-4B and from 8.4 to 42.6 for Qwen3-30B-A3B, and lifts the four-benchmark average from 29.5 to 34.0 (4B) and from 32.5 to 38.1 (30B-A3B) compared to outcome-only GRPO. The gains stem from better credit assignment rather than changes in model, data, or environment, and the method works with the base checkpoint as a stable reference model. TRACE boosts the closed-web deep-research accuracy of Qwen3-4B from 7.2 to 35.6 and Qwen3-30B-A3B from 8.4 to 42.6 using only outcome and turn-level rewards, with no SFT or live-web data. Against GRPO's outcome-only baseline, TRACE increases the four-benchmark average from 29.5 to 34.0 for the 4B model and from 32.5 to 38.1 for the 30B-A3B model, showing that denser turn-level credit is critical for long-horizon tasks. A log-ratio temporal-difference credit outperforms absolute likelihood-based dense rewards, and the approach does not require a specially tuned reference model; the base checkpoint is sufficient.

In this credit-assignment ablation, outcome-only GRPO scores 30.0, and adding dense transition rewards based on the raw log-probability delta raises the score to 32.4. Normalizing by the remaining answer-likelihood gap further improves the score to 34.6, while the proposed log-ratio TD credit achieves the best result of 35.5, indicating that relative gap closure provides a more effective credit signal than absolute likelihood changes. Raw delta rewards improve over outcome-only GRPO, but normalizing by the remaining gap yields a larger gain, and the log-ratio method reaches the highest accuracy. The log-ratio form better normalizes credit across states with different confidence levels and preserves a telescoping structure that discourages redundant trajectory extension.

TRACE is evaluated on long-horizon deep-research and tool-use benchmarks, including BrowseComp-Plus and a four-benchmark average, using base Qwen3 models. Adding turn-level temporal-difference credit to an outcome reward significantly raises closed-web accuracy over outcome-only GRPO, with the log-ratio TD credit form outperforming alternative dense rewards. The method requires no cold-start SFT, agentic mid-training, or live-web data, and the base checkpoint serves as a stable reference model, demonstrating that better credit assignment alone drives large gains in complex multi-step tasks.