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

Source: arXiv:2607.13988 · Published 2026-07-15 · By Leitian Tao, Baolin Peng, Wenlin Yao, Tao Ge, Hao Cheng, Mike Hang Wang et al.

TL;DR

This paper addresses the core challenge of credit assignment in long-horizon agentic reinforcement learning, where an agent must perform many sequential tool interactions before producing a final answer. Existing approaches relying solely on outcome rewards suffer from sparse and high-variance signals that fail to distinguish which intermediate actions actually contribute toward success versus which are redundant or harmful. TRACE proposes a novel dense credit-assignment mechanism that leverages a frozen reference model to assign per-turn rewards by measuring increases in the gold-answer log-probability at each tool-call boundary. By converting these into temporal-difference style log-ratio state values, TRACE provides turn-level rewards that telescope across the trajectory, avoid inflating credit from redundant steps, and do not require additional learned critics or step-level labels. Empirically, TRACE improves long-horizon tool-use ability substantially on synthetic multi-document search tasks, raising performance from 7.2 to 35.6 on Qwen3-4B and from 8.4 to 42.6 on Qwen3-30B-A3B on the closed-web BrowseComp-Plus benchmark. The improvements transfer to multiple open-web benchmarks, demonstrating generalization beyond the training domain. Furthermore, TRACE enables faster convergence and earlier task mastery compared to outcome-only reinforcement learning methods.

Key findings

• TRACE improves Qwen3-4B agent BrowseComp-Plus accuracy from 7.2 to 35.6 and Qwen3-30B-A3B from 8.4 to 42.6 using pure RL without cold-start fine-tuning or live-web training data.
• On open-web benchmarks, the 30B-A3B TRACE agent achieves 12.9 on BrowseComp, 52.0 on GAIA, and 45.0 on xbench-DeepSearch, showing transfer beyond closed training corpus.
• TRACE yields faster learning curves, reaching higher reward and evaluation accuracy earlier and converging to better policies compared to outcome-only GRPO.
• Adding turn-level temporal-difference credit assignment (K=3, γtd=0.8) improves average accuracy over outcome-only RL by 4.5 points on Qwen3-4B and 5.6 points on Qwen3-30B-A3B across multiple benchmarks.
• TRACE leverages a frozen reference model’s gold-answer log-probabilities as stable prefix state values for per-turn reward computation, without training any critic or reward model.
• Redundant or irrelevant intermediate tool calls do not inflate credit due to the telescoping sum property of log-ratio TD rewards.
• TRACE combines dense turn-level credit with terminal outcome reward to maintain verifiable task success while improving intermediate credit signal.
• TRACE outperforms other RL baselines applying group-relative or importance-sampled policy optimization that only operate at final outcome trajectory level.

Threat model

The adversary is the environment that challenges the agent with long sequences of tool interactions, where the agent must identify which steps contribute to achieving the correct final answer. The approach assumes access to gold answers during training but cannot observe or supervise intermediate step correctness. It does not consider malicious actors actively trying to deceive the agent or corrupt observations.

Methodology — deep read

1. Threat Model & Assumptions: The adversary is implicitly the complex environment that an agent interacts with via multiple sequential tool calls to reach a final target answer. The method assumes access to gold answers during training and a frozen reference language model to estimate progress. It assumes no step-level supervision or trained reward model, only terminal outcome rewards.

2. Data: Training uses synthetic multi-document deep-research search tasks generated over an offline OpenResearcher corpus with multiple irreplaceable evidence documents requiring chained retrieval. This contrasts with short multi-hop QA sets that do not challenge credit assignment with long sequences. The evaluation includes closed-web BrowseComp-Plus and open-web BrowseComp, GAIA, and xbench-DeepSearch benchmarks. Training samples up to 60 tool turns per trajectory. Labels are gold final answers.

3. Architecture / Algorithm: The agent is a policy LLM (Qwen3-4B or Qwen3-30B-A3B) that reasons and acts via interleaved assistant tokens and tool calls (browser.search, browser.open, browser.find). TRACE decomposes trajectories at tool-call boundaries into prefix states S_k. Each prefix is scored by the frozen reference model’s gold-answer log-probability (¯ell_k). This raw log-prob is transformed into a log-ratio state value V(S_k) measuring relative closure of the initial answer likelihood gap. The per-turn reward credit is computed as the temporal difference (TD) of adjacent prefix values: δ_k = V(S_{k+1}) - V(S_k), capturing progress made by that tool call.

K-step truncated TD backup (K≥3) combines multiple future TD changes with discount γ_{td} to propagate delayed evidence. The final per-turn reward also anchors to the terminal outcome advantage scaled by λ_{term}. Turn-level advantage values are combined with group-normalized trajectory-level terminal outcome advantage A_{out} weighted by α_{turn} and α_{out} respectively for policy optimization.

No additional critic or process reward model is learned, avoiding brittleness from sparse rewards and shifting states. The frozen reference model remains fixed throughout training and acts as a stable probe for whether trajectory prefixes improve answer predictability.

4. Training Regime: Training uses Adam with learning rate 1e-6, batch size 128, 8 rollouts per prompt, up to 60 tool turns per trajectory. The training offset ε=0.1 stabilizes log-ratio computations. Policy updates optimize clipped Group Relative Policy Optimization (GRPO) objectives with combined outcome and turn advantages. K=3 step look-ahead for TD backup and γ_{td}=0.8. Turn reward coefficient α_{turn}=0.2 and outcome α_{out}=1.0. No cold-start supervised fine-tuning or mid-training with agentic data is performed.

5. Evaluation Protocol: Performance is measured as normalized exact-match answer correctness on multiple closed- and open-web benchmarks. Baselines include the base models, GRPO, GSPO, and GiGRPO optimizers without turn-level credit. External strong deep-research agents provide contextual references. Single runs are reported, so small gaps should be interpreted cautiously.

6. Reproducibility: The paper’s methodology depends on the proprietary Qwen3 backbones and OpenResearcher data. Code release status is not stated. Reference model weights are frozen copies of policy initializations. Complete hyperparameters and algorithm are specified in the appendix.

Example end-to-end: For a given prompt and gold answer, the agent performs T tool calls producing prefix states S_0 to S_T. At each S_k, the frozen model scores the average gold answer token log-prob ¯ell_k. TRACE computes V(S_k) as the log-ratio relative closure of initial gap. Then for each turn k, it calculates the turn reward δ_k = V(S_{k+1}) - V(S_k) and applies truncated K-step backup to incorporate future rewards, combined with terminal outcome reward at the last turn, yielding per-turn advantages for policy gradient updates. This dense signal guides the policy to reward intermediate progress toward the gold answer rather than only final correctness. Over training, this yields improved tool-use performance and more sample-efficient learning compared to outcome-only objectives.

Technical innovations

• Use of a frozen reference model’s gold-answer log-probabilities as stable prefix-level state values for credit estimation, avoiding learned critics or reward models.
• Formulation of turn-level rewards as temporal-difference log-ratio changes in prefix state values, which telescope to the global trajectory outcome.
• Truncated K-step TD backup with discounting to propagate delayed credit to earlier turns without inflating redundant intermediate steps.
• Joint optimization combining stable outcome-level trajectory rewards with dense turn-level TD credits to improve credit assignment in long horizons.

Datasets

• OpenResearcher synthetic multi-document search tasks — size unspecified — constructed from offline corpus released by OpenResearcher
• BrowseComp-Plus — closed-web deep-research benchmark — proprietary/released by Chen et al. (2025c)
• BrowseComp — open-web benchmark — uses Serper API for retrieval
• GAIA — open-web benchmark — from Mialon et al. (2024)
• xbench-DeepSearch — Chinese QA open-web benchmark — from Chen et al. (2025a)

Baselines vs proposed

• Qwen3-4B Base: BrowseComp-Plus accuracy = 7.2 vs TRACE = 35.6
• Qwen3-4B GRPO (outcome-only RL): BrowseComp-Plus accuracy = 30.0 vs TRACE = 35.6
• Qwen3-4B GSPO: BrowseComp-Plus accuracy = 29.7 vs TRACE = 35.6
• Qwen3-4B GiGRPO: BrowseComp-Plus accuracy = 27.7 vs TRACE = 35.6
• Qwen3-30B-A3B Base: BrowseComp-Plus accuracy = 8.4 vs TRACE = 42.6
• Qwen3-30B-A3B GRPO: BrowseComp-Plus accuracy = 36.4 vs TRACE = 42.6
• Qwen3-30B-A3B GSPO: BrowseComp-Plus accuracy = 39.7 vs TRACE = 42.6
• Qwen3-30B-A3B GiGRPO: BrowseComp-Plus accuracy = 33.0 vs TRACE = 42.6

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.13988.

Fig 1: Credit assignment at tool-call boundaries in a search trajectory. The figure illustrates

Limitations

• Results reported on single training runs without statistical significance tests, so small differences should be interpreted cautiously.
• TRACE relies on availability of gold answers during training, limiting applicability where such labels are unavailable.
• The frozen reference model may become less reliable if distribution shifts occur during long training or deployment.
• Evaluation does not include adversarial or robustness tests to malicious or off-distribution tool interactions.
• The method assumes the reference model’s answer log-probabilities accurately reflect prefix progress, which may not hold in all domains.
• Training and evaluation use curated synthetic and benchmark datasets, leaving open transfer to real-life noisy environments.

Open questions / follow-ons

• How does TRACE perform under distribution shifts where prefix log-probabilities from the frozen reference model degrade in quality?
• Can the approach be extended to settings without gold final answers, such as purely unsupervised or human-in-the-loop feedback?
• How robust is TRACE credit assignment to environment stochasticity or partial observability in tool responses?
• What are the effects of varying the lookahead horizon K and discount factor γ_{td} systematically across task types?

Why it matters for bot defense

Bot-defense and CAPTCHA practitioners often face the challenge of distinguishing genuine human or legitimate automated behaviors from malicious or low-quality interactions across multiple steps or stages. TRACE's approach to credit assignment—decomposing a long sequence of interactions into per-step contributions toward a final goal—offers a principled framework to attribute partial progress or trust scores at intermediate steps. This could inspire more nuanced behavioral analysis or reinforcement learning policies in multi-turn bot-defense systems, where sparse binary labels of legitimacy or failure are insufficient for learning fine-grained decision policies. Furthermore, the use of a frozen reference model as a stable probe to evaluate intermediate states without additional supervision can reduce the cost and complexity of building judge models or annotating step-level feedback in CAPTCHA-like domains. However, practitioners should consider limitations related to domain mismatch and the reliance on gold labels during training. Overall, TRACE demonstrates a scalable method to incorporate dense internal feedback derived from model-internal metrics, which could enhance detection and intervention strategies in complex multi-turn bot or automation detection pipelines.

Cite

@article{arxiv2607_13988,
  title={ TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents },
  author={ Leitian Tao and Baolin Peng and Wenlin Yao and Tao Ge and Hao Cheng and Mike Hang Wang and Jianfeng Gao and Sharon Li },
  journal={arXiv preprint arXiv:2607.13988},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.13988}
}

Read the full paper

• arXiv:2607.13988 (abstract)
• arXiv:2607.13988 (PDF)