PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Leitian Tao, Baolin Peng, Wenlin Yao, Tao Ge, Hao Cheng, Mike Hang Wang, Jianfeng Gao, Sharon Li

arXiv:2607.13988v1cs.LG

TL;DR

Long-horizon agents can make many tool calls, but outcome rewards do not identify which turns advance the answer. TRACE estimates progress from frozen-reference gold-answer predictability at tool-call boundaries and assigns turn-level TD rewards. It outperforms outcome-only GRPO on all four benchmarks at both model scales, raising Qwen3-4B’s four-benchmark average from 29.5 to 34.0.

  • Problem

    A central question in long-horizon agentic RL is how to identify which tool calls move an agent toward the answer and turn that signal into dense rewards without step labels, a strong judge, or a trained process reward model.

    Source: §1 · p. 2, §2.1 · p. 3

  • Method

    TRACE uses a frozen reference model's gold-answer predictability at tool-call boundaries to form log-ratio state values and assign turn rewards from adjacent-value TD changes.

    Source: §1 · p. 2, §3.2 · p. 4

  • Results

    TRACE outperforms outcome-only GRPO on all four benchmarks at both model scales, raising Qwen3-4B’s four-benchmark average from 29.5 to 34.0, with gains transferring to open-web evaluation.

    Source: §7 · p. 13

  • Takeaways & Limitations

    Frozen-reference turn credit is an effective signal for long-horizon search with compact, verifiable answers.

    Source: §7 · p. 13

    TRACE's value-estimation strategy may be less direct for agentic tasks with long, structured, or open-ended outputs than for tasks with compact answers and known ground truth.

    Source: §6 · p. 12

Abstract

from arXiv · show

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 propose TRACE (Turn-level Reward Assignment via Credit Estimation), a dense credit-assignment method for agentic reinforcement learning. TRACE represents 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, TRACE substantially 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 from $7.2$ to $35.6$ and Qwen3-30B-A3B from $8.4$ to $42.6$. The learned search behavior also transfers to open-web benchmarks, and the learning curves show earlier improvement and faster convergence during RL training.

1 INTRODUCTION

TRACE addresses sparse credit assignment in long-horizon tool use by deriving turn rewards from changes in gold-answer predictability under a frozen reference model. It combines turn-level rewards with outcome-level rewards and reports gains on closed- and open-web search benchmarks using pure RL.

1 INTRODUCTION

  • Outcome-only training gives every turn in a rollout the same advantage, under-crediting useful actions, over-crediting irrelevant ones, and increasing gradient variance as horizons grow.Long-horizon rollouts may include many tool decisions before the final answer is verified.Source: §1 · p. 1
  • TRACE scores trajectory prefixes with a frozen reference model’s gold-answer log-probability, converts scores to log-ratio values, and assigns turn rewards from adjacent value changes.The one-step TD credits telescope, and TRACE combines them with the standard outcome-level advantage so final verifier success remains the training target.Source: §1 · p. 2
  • BrowseComp-Plus scores rise from 7.2 to 35.6 for Qwen3-4B and from 8.4 to 42.6 for Qwen3-30B-A3B with TRACE.On open-web benchmarks, the 30B-A3B agent reaches 12.9 on BrowseComp, 52.0 on GAIA, and 45.0 on xbench-DeepSearch.Source: §1 · p. 2
  • TRACE trains on deeper synthetic search questions with pure RL, without cold-start supervised fine-tuning, agentic mid-training, live-web data, a strong judge, or a trained process reward model.Its learning curves show earlier improvement and faster convergence.Source: §1 · p. 2

2 PRELIMINARIES

Agentic reinforcement learning assigns outcome feedback to complete tool-use rollouts, leaving the contribution of individual turns unresolved. Temporal-difference credit instead measures progress through changes in adjacent-state values, but requires a reliable dense value signal.

2.1 AGENTIC REINFORCEMENT LEARNING

  • Terminal rewards supervise assistant actions across long tool-use trajectories but do not identify which turns helped or hurt the final answer.Tool observations are environment outputs rather than policy-generated tokens, while gradients apply to assistant actions and answer tokens.Source: §2.1 · p. 3
  • GRPO compares rollouts for a prompt but assigns advantage to whole trajectories, motivating credit at tool-call prefix transitions.Adjacent prefixes isolate how each tool interaction changes the information available to the agent.Source: §2.1 · p. 3

2.2 TEMPORAL-DIFFERENCE CREDIT ASSIGNMENT

  • With zero intermediate rewards and γ = 1, one-step TD credit reduces to the adjacent-state value difference V(s_{t+1}) − V(s_t).This difference measures incremental progress, but long-horizon agent tasks lack a reliable dense value function over partial tool trajectories.Source: §2.2 · p. 3

3 TURN-LEVEL REWARD ASSIGNMENT VIA CREDIT ESTIMATION

TRACE assigns dense turn-level credit by measuring changes in gold-answer predictability under a frozen reference model, while retaining the outcome reward as the final measure of task success. It combines log-ratio state values with temporal-difference credit at tool-call boundaries, without learning a critic.

3.1 TOOL-BOUNDARY STATES

  • TRACE splits trajectories at tool-call boundaries and assigns credit to action–observation transitions, while applying policy-gradient loss only to assistant actions and answer tokens.The terminal verifier scores the final answer, and tool observations remain environment outputs masked from the loss.Source: §3.1 · p. 4

3.2 STATE VALUE VIA LOG-RATIO ANSWER PROBABILITY

  • A frozen copy of the policy initialization estimates gold-answer log-probability for each prefix, providing a stable progress probe without training a critic or reward model.The answer scores are computed in one batched forward pass and are never optimized; the outcome verifier still determines final-answer correctness.Source: §3.2 · pp. 4–5
  • TRACE converts prefix answer log-probability into a log-ratio state value measuring the fraction of the initial answer-likelihood gap that has closed.This relative-gap measure distinguishes changes that remove substantial uncertainty near the answer from equal-sized changes when the trajectory remains far away; the TD difference between consecutive values measures transition value added.Source: §3.2 · p. 5

3.3 TURN-LEVEL REWARD VIA TEMPORAL-DIFFERENCE CREDIT

  • One-step log-ratio TD credit rewards transitions that improve gold-answer readiness and telescopes across turns, so redundant intermediate actions cannot inflate total credit.TRACE also uses a truncated K-step backup to propagate delayed evidence and anchors turns whose look-ahead window reaches the outcome; this trades exact endpoint-only credit for delayed propagation and outcome anchoring.Source: §3.3 · p. 6
  • TRACE jointly optimizes unnormalized trajectory-local turn credit with group-relative GRPO outcome advantage, applying the mixed signal to tool-interaction tokens.Final-answer tokens use the outcome component with answer-tail weighting; tool observations are environment outputs and are masked from the policy-gradient loss.Source: §3.1 · p. 4, §3.3 · pp. 6–7

4 EXPERIMENTS

TRACE improves long-horizon search performance across closed-web and open-web benchmarks, with learning curves showing earlier improvement and ablations identifying effective turn-level credit settings.

4.1 EXPERIMENTAL SETUP

  • Experiments train Qwen3-4B and Qwen3-30B-A3B on synthetic multi-document search, then evaluate closed-web BrowseComp-Plus and three open-web benchmarks.The tasks require chained retrieval over multiple irreplaceable evidence documents; controlled runs share the browser interface, rollout protocol, training data, terminal reward, and evaluation interface.Source: §4.1 · pp. 7–8

4.2 MAIN RESULTS

  • 7.2 to 35.6 for Qwen3-4B and 8.4 to 42.6 for Qwen3-30B-A3B on closed-web BrowseComp-Plus with TRACE using outcome- and turn-level RL.Both models start from base search policies without cold-start SFT, agentic mid-training, or live-web training.Source: Table 1 · p. 8, §4.2 · p. 8
  • 34.0 vs. GRPO’s 29.5 for Qwen3-4B and 38.1 vs. 32.5 for Qwen3-30B-A3B on four-benchmark averages; Qwen3-30B-A3B scores 12.9 on BrowseComp, 52.0 on GAIA, and 45.0 on xbench-DeepSearch.The open-web results test transfer from closed synthetic search training to external retrieval and a Chinese QA benchmark.Source: Table 1 · p. 8, §4.2 · p. 9

4.3 LEARNING DYNAMICS OF TRACE

  • TRACE reward curves rise earlier, climb more steeply, and plateau higher; on Qwen3-30B-A3B, the 160-step TRACE checkpoint exceeds the 200-step outcome-reward baseline.The same earlier-and-faster trajectory-scale increase is shown for Qwen3-4B relative to GRPO.Source: Figure 3 · p. 9, §4.3 · p. 9, Figure 4 · p. 10

4.4 ABLATION STUDY

  • 33.6 at turn-level coefficient 1 rises to 35.6 at 3, then falls to 34.5 and 31.1 at larger coefficients.The results support using turn-level reward as an auxiliary signal rather than replacing outcome reward.Source: Figure 5 · p. 10, §4.4 · pp. 10–11
  • 30.0 with TD look-ahead disabled rises to 34.7 and 35.6 with moderate propagation, while the largest setting drops to 28.9.Moderate propagation credits earlier retrieval decisions for later evidence, whereas the largest setting can introduce noise from loosely related turns.Source: Figure 5 · p. 10, §4.4 · p. 11
  • 30.0 without reference-model progress scoring rises to 35.6 with the step-0 checkpoint and 36.1 with the step-200 checkpoint.The similar checkpoint results indicate that the base checkpoint is sufficient as a stable answer-readiness scoring anchor.Source: Figure 5 · p. 10, §4.4 · p. 11
  • 35.5 with log-ratio TD credit exceeds 34.6 with remaining-gap normalization, 32.4 with raw log-probability deltas, and 30.0 for outcome-only GRPO.The ablation suggests relative gap closure normalizes credit across confidence levels and discourages redundant trajectory extension.Source: Table 2 · p. 10, §4.4 · p. 10

5 RELATED WORK

The related work places TRACE within the expansion of LLM post-training from short-horizon reasoning to multi-turn tool use, and within efforts to assign credit more finely than trajectory-level rewards. TRACE’s distinction is turn-level feedback for intermediate progress without an additional critic or progress estimator.

Post-training of LLMs for reasoning and agentic tasks

Credit assignment for long-horizon language agents

  • TD learning, potential-based shaping, reward redistribution (Arjona-Medina et al., 2019), and process supervision (Uesato et al., 2022; Lightman et al., 2023; Li and Li, 2025) motivate denser credit but can require added supervision or estimators.The passage notes requirements can include a learned critic, step labels, process-reward annotation, Monte Carlo continuations, or task-specific reward features.Source: §5 · p. 12
  • Single-response credit methods use answer-probability changes, rollout-estimated values, or policy/reference log-likelihood ratios (Setlur et al., 2024; Wang et al., 2024a; Yuan et al., 2024).Related multi-turn work studies stepwise rewards, hindsight and memory-aware credit, search-agent RL, and long-horizon tool-use training.Source: §5 · p. 12
  • Rather than introduce a new agent interface or stronger teacher, TRACE assigns turn-level credit to intermediate progress without an extra critic or progress estimator, Monte Carlo continuations, or repeated states.It complements outcome-based post-training so agents can learn from useful intermediate progress as well as final success or failure.Source: §5 · p. 12

6 LIMITATIONS

TRACE is validated on long-horizon search with short, ground-truth answers, where gold-answer predictability provides a proxy for progress. Its reliability for long, structured, or open-ended outputs remains unclear, bounding the method’s current scope.

6 LIMITATIONS

  • TRACE’s gold-output log-probability value proxy may be less reliable for tasks with long, structured, or open-ended outputs than for compact-answer search.The paper gives multi-file code patches and preference-dependent open-ended assistance as examples where matching one gold response may not directly measure progress.Source: §6 · p. 12
  • This limitation bounds TRACE’s scope but does not undermine its claim that turn-level credit reduces outcome-only RL sparsity; richer tasks may need alternative progress targets.Proposed directions include execution-based coding signals, structured task specifications, and decomposed verifiable subgoals; reliable estimators for long-output and open-ended agents remain future work.Source: §6 · p. 12

7 CONCLUSION

TRACE assigns turn-level rewards from frozen-reference gold-answer log-ratio value changes at tool-call boundaries, combined with GRPO outcome advantage. It outperforms outcome-only GRPO across four benchmarks at both model scales and improves BrowseComp-Plus, with gains transferring to open-web evaluation.

7 CONCLUSION

  • TRACE derives local rewards from temporal-difference changes in frozen-reference log-ratio state values at tool-call boundaries, combining them with GRPO outcome advantage.The method needs no step labels, strong LLM judge, trained critic, or process reward model.Source: §7 · pp. 12–13
  • Four-benchmark averages rose from 29.5 to 34.0 for Qwen3-4B and from 32.5 to 38.1 for Qwen3-30B-A3B; BrowseComp-Plus rose from 7.2 to 35.6 and from 8.4 to 42.6, respectively.TRACE outperforms outcome-only GRPO on all four benchmarks at both scales, with gains transferring to open-web evaluation.Source: §7 · p. 13
  • Frozen-reference turn credit is effective for long-horizon search with compact, verifiable answers, while long, structured, or open-ended outputs require alternative state-value estimators.Source: §7 · p. 13

A APPENDIX · A.1 TRAINING HYPERPARAMETERS

The appendix documents the Search-R1 training configuration and explains how TRACE runs enable turn-level scoring. It distinguishes the TRACE training-gap offset from a separate legacy stabilizer.

A.1 TRAINING HYPERPARAMETERS

  • TRACE runs enable turn-level scoring, which the shared launch script otherwise disables for a single-node colocated layout unless a remote reference-model scoring endpoint is provided.TRACE uses the settings listed in Table 4.Source: §A.1 · p. 19
  • Table 3 summarizes core training, rollout, and optimization hyperparameters for the Qwen3-30B-A3B-Thinking-2507 Search-R1 training run.Source: Table 3 · p. 19
  • Table 4 lists TRACE-specific reward and turn-credit hyperparameters, distinguishing the training-gap offset ϵ from the separate legacy transform stabilizer.The legacy stabilizer is not used as the log-ratio gap offset in the reported TRACE runs.Source: Table 4 · p. 20

A.2 COMPARISON WITH RAW LOG-PROBABILITY DIFFERENCES

TRACE’s log-ratio TD reward credits relative reductions in the remaining answer-likelihood gap, while retaining an endpoint-only cumulative form. An offline diagnostic favors this score over raw log-probability differences and linear gap normalization.

A.2 COMPARISON WITH RAW LOG-PROBABILITY DIFFERENCES

  • Raw log-probability differences telescope to the endpoint change and preserve same-prompt rollout ordering, but measure absolute gains rather than the fraction of the remaining gap closed.Both linear remaining-gap normalization and log-ratio TD reward measure relative gap reduction; only the log-ratio reward has an endpoint-only cumulative form.Source: §A.2 · p. 20, Table 5 · p. 20
  • Log-ratio credits show the strongest correlation with endpoint quality and correctness, and the best pairwise ranking among rollouts with similar initial raw log-probabilities.The offline diagnostic used 830 held-out BrowseComp-Plus rollouts containing 3,742 tool turns.Source: §A.2 · pp. 20–21, Table 6 · p. 21
  • For nearly equal raw gains of 3.5475 and 3.5509, log-ratio TD rewards are 1.1806 and 0.4052, crediting the transition that closes more of the remaining gap.The passage motivates this distinction for long-horizon search: decisive evidence localization near the answer should receive more credit than an equal absolute gain that leaves the rollout far from predicting the gold answer.Source: §A.2 · p. 21

A.3 SEARCH-AGENT TASK AND INTERFACE

TRACE is evaluated in a deliberately simple closed-corpus search environment where the agent alternates reasoning with browser calls or a final answer. Training uses assistant-generated tokens, masks tool observations, and rewards exact normalized-answer matches with a small formatting component.

A.3 SEARCH-AGENT TASK AND INTERFACE

  • The closed-corpus agent alternates private reasoning with one browser call or a final answer per turn, isolating the training signal from planner or tool-stack improvements.The environment executes valid calls against the retrieval corpus and appends observations before the next turn.Source: §A.3 · p. 21
  • Rollouts end at a final <answer>, the tool-turn limit, or context or generation limits; reward checks exact normalized-answer matches plus a small format component.Diagnostics track tool-call counts, repeated queries, reopened documents, repeated in-document searches, navigation errors, and answer-format validity.Source: §A.3 · p. 21
  • Search retrieves document titles, URLs, and summaries; open displays corpus content, and find returns matching line numbers in the open document.These are the three browsing tools exposed to the agent in all experiments.Source: Table 7 · p. 21
  • Policy-gradient loss applies to assistant-generated reasoning, tool-call, and final-answer tokens, while environment-provided tool observations are masked.This token-level training treatment applies across assistant turns.Source: §A.3 · p. 21

A.4 SYNTHETIC TRAINING DATA … A.5.2 NEGATIVE TRAJECTORIES: LOCALIZING THE TOOL CALL THAT LOSES

The appendix describes how TRACE training questions are synthesized to demand multi-document search, then uses turn-credit examples to show how credit localizes decisive progress and harmful calls. The examples expose within-trajectory distinctions that outcome-only GRPO misses.

A.4 SYNTHETIC TRAINING DATA

  • Synthetic training questions require chained search, synthesis across at least two irreplaceable documents, and resistance to direct answer lookup.The motivation is to avoid saturation from direct-lookup questions that offer little pressure to learn deeper information gathering.Source: §A.4 · p. 22

A.4.1 GENERATION PIPELINE

  • For each anchor document, the pipeline selects related sources, generates candidates with rejection and regeneration, then independently verifies answers before retaining the highest-scoring example.The independent verifier sees the question and sources but not the proposed answer; examples are discarded unless its answer matches under fuzzy matching.Source: §A.4.1 · p. 22

A.4.2 QUESTION TEMPLATES

  • Questions use templates for cross-document reasoning and obfuscate entities, time expressions, names, or quantitative constraints to prevent direct keyword lookup.These transformations make the agent resolve what to search for before retrieving answer evidence.Source: §A.4.2 · p. 22

A.4.3 VERIFICATION AND SELECTION

  • Quality control checks for at least two source URLs and rejects questions that are easy, single-source answerable, unsupported, redundant, or lacking genuine synthesis.Selection favors verified examples with fewer regeneration attempts, longer reasoning chains, more distinct documents, and primary roles for cited sources, while penalizing answer leakage and overly long answers.Source: §A.4.3 · pp. 22–23

A.5 QUALITATIVE ANALYSIS OF THE TURN CREDIT

  • Turn credit is computed from frozen-reference values before tool use, after each observation, and after answer generation, with V ≥−0.3 diagnosing an answer-secured prefix.Each tool turn receives the one-step value difference, and the final difference is assigned to answer generation.Source: §A.5 · p. 23

A.5.1 SUCCESSFUL TRAJECTORIES: LOCALIZING THE TURN THAT WINS

  • Successful trajectories place nearly all credit on the search or open that first supplies the missing discriminative fact, while redundant confirmation receives near-zero credit.Examples include a decisive search-result snippet and a reformulated rescue query after stalled probes.Source: §A.5.1 · pp. 23–24

A.5.2 NEGATIVE TRAJECTORIES: LOCALIZING THE TOOL CALL THAT LOSES

  • Across five failures, trajectories first secure an answer and then receive dominant penalties for misleading find calls, while outcome-only GRPO gives every turn the same advantage.The misleading calls include over-interpreted empty matches and successful matches in the wrong context, showing that tool completion alone does not imply progress.Source: §A.5.2 · p. 26
Loading 2607.13988v1…