TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents
TRACE assigns turn-level rewards via credit estimation using frozen reference models and TD changes, boosting long-horizon agent performance without extra critic training.
Key Findings
Methodology
TRACE employs a frozen reference model to evaluate each prefix of a long trajectory at tool-call boundaries, converting log-answer probabilities into state values. It then calculates temporal-difference (TD) differences between consecutive prefix values to assign dense, turn-level rewards. This approach avoids training critics or process labels, relying solely on the model's probability ratios. The core components include: • computing prefix answer log-probabilities, • transforming into log-ratio state values, • applying one-step TD differences for reward signals. Experiments on complex search tasks show significant improvements: Qwen3-4B scores increased from 7.2 to 35.6, and Qwen3-30B-A3B from 8.4 to 42.6, demonstrating the method's effectiveness.
Key Results
- In long-horizon search benchmarks, TRACE dramatically enhances tool use, with Qwen3-4B's score jumping from 7.2 to 35.6 and Qwen3-30B-A3B from 8.4 to 42.6, outperforming baselines. The training is purely RL, without supervised fine-tuning, leading to earlier improvements and faster convergence. The learned behaviors transfer well to open-web benchmarks, indicating strong generalization.
Significance
This work addresses the core challenge of reward sparsity in multi-turn, long-horizon tasks. By providing dense, reliable rewards aligned with final success, TRACE facilitates more efficient exploration and learning in complex environments. Its critic-free design simplifies implementation and reduces training costs, making it highly applicable to real-world scenarios like web navigation, automated reasoning, and coding assistants. The approach paves the way for more autonomous, capable agents that learn from sparse signals without heavy supervision.
Technical Contribution
The paper introduces a novel reward estimation framework that leverages frozen models to evaluate prefix answer likelihoods, transforming these into state values. The use of one-step TD differences ensures rewards are telescoping, preventing reward inflation from redundant actions. This method combines outcome verification with dense, step-wise credit assignment, enabling stable, critic-free RL training. It also generalizes across model scales and tasks, offering a new paradigm for reward design in long-horizon RL settings.
Novelty
This is the first work to utilize frozen language models' log-probability ratios as a stable, critic-free proxy for state values in long-horizon RL. Unlike prior methods relying on trained critics or process labels, TRACE's approach is simple, effective, and theoretically grounded, with the endpoint telescoping property ensuring reward accuracy. It innovatively bridges the gap between sparse outcome rewards and dense behavioral feedback, enabling more efficient learning.
Limitations
- The method depends on the stability and accuracy of the frozen reference model; biases or inaccuracies in the model can distort reward signals.
- In highly complex or out-of-distribution tasks, the probability estimates may be unreliable, limiting effectiveness.
- Computational overhead increases with model size and sequence length due to repeated forward passes, impacting training efficiency.
Future Work
Future research could explore adaptive reference models that evolve during training, multi-modal reward signals incorporating visual or other data, and hybrid approaches combining supervised signals with dense rewards. Additionally, optimizing computational efficiency and extending to real-world applications like autonomous agents in dynamic environments are promising directions.
AI Executive Summary
The development of autonomous agents capable of long-horizon reasoning remains a central challenge in artificial intelligence. Traditional reinforcement learning approaches rely heavily on sparse, outcome-based rewards, which are often insufficient for guiding complex multi-step behaviors. This limitation hampers the ability of models to learn effective tool use and exploration strategies in tasks such as web navigation, coding, or multi-document reasoning. To address this, the paper introduces TRACE, a novel reward assignment framework that leverages frozen reference models to estimate the incremental contribution of each tool call or action within a long sequence.
TRACE operates by segmenting the agent’s trajectory at tool-call boundaries, evaluating each prefix’s answer likelihood using a frozen model, and transforming this into a log-ratio state value. The core innovation lies in applying temporal-difference (TD) differences between consecutive prefix values to generate dense, turn-level rewards. This approach effectively captures the incremental progress toward the final answer, even in the presence of redundant or misleading intermediate steps. Importantly, it does not require training additional critics or process labels, simplifying the reinforcement learning pipeline.
Experimental results demonstrate that TRACE significantly boosts performance on complex search benchmarks. For instance, in the BrowseComp-Plus dataset, the Qwen3-4B model’s score increased from 7.2 to 35.6, and Qwen3-30B-A3B from 8.4 to 42.6, surpassing existing baselines. The training curves show earlier improvements and faster convergence, indicating that dense, turn-level rewards facilitate more efficient exploration. Moreover, the learned search behaviors transfer effectively to open-web benchmarks, highlighting the method’s robustness and generalization.
This work offers a practical and theoretically grounded solution to the reward sparsity problem in long-horizon RL, with broad implications for building more autonomous, capable agents. Future directions include integrating adaptive reference models, multi-modal signals, and real-world deployment scenarios, promising to advance the frontier of AI reasoning and interaction capabilities.
Deep Dive
Plain Language Accessible to non-experts
想象你在厨房里做一道复杂的菜，你需要不断试验不同的调料和步骤。有时候你会觉得某个动作特别重要，比如多放点盐，菜就会变得更好吃。TRACE就像是一个聪明的助手，它会在你每次调料后偷偷告诉你，这一步是不是让菜变得更美味。它不用你告诉它“你做得好”或“做错了”，而是通过观察每次操作后菜的味道变化，自己判断哪一步帮了大忙，哪一步没用。这样，你就能更快学会哪些步骤最重要，做出更好吃的菜。这种方法让你在做菜时，能更聪明、更快地掌握诀窍。
ELI14 Explained like you're 14
想象你在玩一个超级复杂的游戏，你要不停做出各种动作，比如跳跃、躲避、攻击。每次你做完动作后，游戏会告诉你得分，但这个得分只在最后告诉你你赢了还是输了。可是，你其实想知道每个动作是不是帮你赢得了比赛。TRACE就像是一个聪明的教练，它会在你每次动作后，偷偷告诉你这个动作是不是让你离胜利更近了。它不用看整个比赛的最终结果，也不用你告诉它哪个动作好，只靠观察每次动作后得分的变化，就能知道哪些动作最有效。这样，你就能更快学会怎么打这个游戏，变得更厉害。
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 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.