Skip to content

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

🕒 Published (v1): 2026-07-15 16:16 UTC · Source: Arxiv · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

TRACE addresses the credit assignment problem in long-horizon LLM agents by using a frozen reference model to score per-turn progress toward the gold answer via log-ratio state values and temporal-difference updates. It requires no critic, process labels, or strong judge model. On BrowseComp-Plus, TRACE raises Qwen3-4B from 7.2→35.6 and Qwen3-30B-A3B from 8.4→42.6 using pure RL.

Problem

Outcome-only RL (GRPO, RLVR) assigns a single terminal reward to trajectories spanning tens or hundreds of tool calls. This creates sparse, high-variance gradients that (1) under-credit productive early tool calls in failed rollouts, (2) over-credit redundant actions in successful ones, and (3) slow convergence as horizon grows. Prior dense-reward solutions require step-level human labels, a trained process reward model, or a strong LLM judge—all expensive and potentially misaligned with final-answer correctness.

Method

TRACE assigns per-turn rewards using a critic-free, TD-based credit signal anchored to a frozen reference model \(\pi_\text{ref}\):

  1. Tool-boundary states: A rollout \(\tau = (x, a_1, o_1, \ldots, a_T, o_T, \hat{y})\) is segmented into prefix states \(S_0, \ldots, S_T\) at each tool-call boundary.

  2. Log-probability prefix score: For each prefix \(S_k\), the frozen reference model scores the gold answer \(y^\star\): $\(\bar{\ell}_k = \frac{1}{|y^\star|} \sum_{t=1}^{|y^\star|} \log \pi_\text{ref}(y_t^\star \mid S_k, y_{<t}^\star)\)$

  3. Log-ratio state value: Raw log-prob differences are normalized by the initial gap to measure relative closure: $\(V(S_k) = \log \frac{-\bar{\ell}_0 + \epsilon}{-\bar{\ell}_k + \epsilon}\)$ so \(V(S_0)=0\) and larger values indicate more evidence gathered. The one-step TD credit is \(\delta_k = V(S_{k+1}) - V(S_k) = \log(d_k / d_{k+1})\), which telescopes so redundant turns cannot inflate total credit.

  4. K-step TD backup: A truncated K-step backup with discount \(\gamma_\text{td}\) propagates delayed tool effects (e.g., a browser.search whose payoff materializes after a subsequent browser.open). Terminal turns are also anchored to the GRPO outcome advantage \(A^\text{out}_g\) via a scale \(\lambda_\text{term}\).

  5. Joint optimization: Per-token advantage is \(\hat{A}_{g,t} = \alpha_\text{out} A^\text{out}_g + \alpha_\text{turn} r^\text{turn}_{g,k}\), optimized with a clipped GRPO objective. No cold-start SFT, agentic mid-training, or live-web data are used.

Key Contributions

  • A critic-free, label-free dense reward method for long-horizon agentic RL derived from frozen reference model answer log-probabilities
  • Log-ratio state value formulation that normalizes credit by the initial answer-likelihood gap, making the TD signal scale-invariant
  • Telescoping property guaranteeing redundant intermediate tool calls cannot inflate total cumulative credit
  • K-step TD backup with terminal outcome anchoring to handle delayed evidence effects
  • Empirical demonstration that pure RL (no SFT cold start) can teach base models complex multi-hop search behavior with TRACE

Results

  • BrowseComp-Plus (closed-web): Qwen3-4B: 7.2→35.6 (+28.4); Qwen3-30B-A3B: 8.4→42.6 (+34.2)
  • BrowseComp (open-web): 30B-A3B reaches 12.9 vs. GRPO baseline 10.8
  • GAIA: 30B-A3B reaches 52.0 vs. GRPO 45.6
  • xbench-DeepSearch: 30B-A3B reaches 45.0 vs. GRPO 37.0; transfers to Chinese QA without language-specific training
  • Controlled baselines (same backbone, data, reward): TRACE outperforms GRPO, GSPO, and GiGRPO on all four benchmarks for both model sizes
  • External references (non-controlled): 30B-A3B TRACE (avg 38.1) surpasses ASearcher-QwQ-32B (32.2), WebDancer-32B (31.7), CutBill-30B-A3B (34.5); trails TongyiDS-30B-A3B (58.4)
  • Training curves show earlier improvement and faster convergence vs. outcome-only baselines

Limitations

  • Controlled ablations are single training runs; small differences between methods should be treated as directional, not variance-adjusted
  • External baseline comparisons are non-controlled (different data, harnesses, model backbones), limiting direct conclusions
  • The telescoping property holds exactly for the one-step TD component; K-step backup and terminal fill intentionally break exact endpoint-only form, introducing approximation
  • Evaluation restricted to complex search tasks; generalization of TRACE to other agentic domains (code execution, computer use) is not demonstrated
  • The reference model must hold the full gold answer in context for every prefix in every rollout, which increases forward-pass cost proportionally to trajectory length and group size

Relevance to Agentic AI / LLM Agents

TRACE directly attacks the sparse-reward bottleneck that limits applying RLVR—highly effective for single-turn reasoning—to multi-turn tool-using agents. By deriving dense per-turn credit from a frozen reference model rather than learned critics or human labels, it offers a practically deployable dense-reward signal that scales with trajectory length without additional annotation cost. The result that pure RL from a base model reaches competitive deep-research performance without SFT cold-start is significant: it suggests the agentic behavior itself (query decomposition, iterative evidence gathering, source triangulation) can emerge from verifier-anchored RL alone. The telescoping credit property and log-ratio value formulation are broadly applicable design principles for any agent trained with outcome rewards over long tool-call horizons.