TRACE: Credit Estimation for Turn-Level Reward Assignment in Long-Horizon Agents

Background and Context

The domain of multi-agent systems and complex task resolution has long grappled with the fundamental challenge of credit assignment in long-sequence interactions. In the post-training phase of reinforcement learning, accurately evaluating the contribution of each step within a lengthy interaction trajectory is critical for model optimization. Traditional reinforcement learning paradigms predominantly rely on outcome-based rewards, where agents receive feedback solely upon the completion of a task. While this approach demonstrates efficacy in short-horizon reasoning tasks, it encounters severe limitations when applied to scenarios involving dozens or even hundreds of tool calls. In such long-horizon trajectories, the reward signal becomes extremely sparse, exhibiting high variance that complicates the learning process.

A more profound issue with outcome-only rewards is their potential for misleading credit assignment. In complex multi-turn agent tasks, a final attempt may fail despite containing numerous effective actions that significantly advanced the task toward its goal. If the model evaluates success or failure exclusively based on the final outcome, these valuable intermediate steps are incorrectly assigned negative advantages. Consequently, the model fails to learn from these productive interactions, leading to inefficient exploration and suboptimal decision-making in complex environments. This disconnect between intermediate progress and final reward creates a significant barrier to scaling reinforcement learning for sophisticated agent coordination.

To address these systemic inefficiencies, researchers have introduced TRACE (Turn-level Reward Assignment via Credit Estimation), a dense credit assignment mechanism specifically designed for agent reinforcement learning. TRACE fundamentally breaks the dependency on single outcome-based rewards by implementing a fine-grained, turn-level reward allocation strategy. This approach enables agents to precisely identify and reinforce intermediate behaviors that genuinely contribute to goal achievement. By providing dense feedback signals at each interaction step, TRACE significantly enhances decision quality and exploration efficiency in long-horizon tasks without requiring additional supervisory signals, thereby offering a robust solution to the credit assignment problem.

Deep Analysis

The technical implementation of TRACE elegantly integrates state-space modeling with temporal-difference learning theory to resolve the credit assignment dilemma. The method reformulates the agent's complete interaction trajectory into a sequence of state transitions bounded by tool-calling events. This structural redefinition allows for a granular analysis of agent behavior at the turn level rather than the episode level. To quantify the value of each state, TRACE leverages a frozen reference model to obtain the conditional log-probability of the golden answer. These probabilities are then transformed into log-odds ratio state values, providing a robust metric for evaluating the agent's progress toward the solution.

A key innovation of TRACE is its ability to derive action-level rewards from temporal-difference updates without training any additional value networks or Critic models. By calculating the change in log-odds ratios between adjacent states, the algorithm computes the first-order temporal-difference error to determine the immediate reward for each specific action. This design possesses unique mathematical properties: when an agent engages in redundant tool calls or loops, the state value changes tend to stabilize. The temporal-difference error automatically collapses in these scenarios, preventing the amplification of reward signals or the accumulation of noise. This mechanism ensures that the agent is not penalized or rewarded excessively for unproductive behavior, maintaining a stable learning signal.

Furthermore, TRACE operates entirely on offline data, eliminating the need for process-level annotations or complex cold-start supervised fine-tuning stages. The method can automatically collapse redundant tool calls, streamlining the trajectory and focusing learning on high-value actions. This independence from online data training or manual labeling makes TRACE particularly suitable for resource-constrained environments or scenarios where data acquisition is difficult. The absence of a separate Critic model significantly reduces computational overhead and implementation complexity, allowing for more efficient training pipelines that can be deployed with minimal infrastructure requirements.

Industry Impact

Experimental validation of TRACE was conducted across multiple high-difficulty search benchmarks, with a specific focus on its performance in long-horizon complex search tasks. The results demonstrated breakthrough progress in the offline BrowseComp-Plus benchmark. Specifically, the Qwen3-4B model, after applying TRACE, saw its performance metric surge from 7.2 to 35.6. Similarly, the larger Qwen3-30B-A3B model improved from 8.4 to 42.6. These substantial gains were achieved under strict conditions: the training process excluded cold-start supervised fine-tuning, mid-training agent phases, and online webpage data training. This outcome proves the feasibility of a pure reinforcement learning path for enhancing agent capabilities without relying on expensive data annotation or extensive pre-training adjustments.

Ablation studies further revealed that the search behaviors learned by TRACE exhibit strong generalization capabilities. The models were able to successfully transfer their improved search strategies to open-network benchmark tests, indicating that the learned policies are robust and not merely overfitting to specific benchmark constraints. The training curves showed that with the introduction of TRACE, models exhibited faster convergence speeds and more significant improvement trends during the early stages of reinforcement learning. This suggests that the dense turn-level reward signals effectively guided the exploration direction, mitigating the common issue of blind early exploration often seen in traditional sparse reward settings.

From an industry perspective, TRACE offers the open-source community and industrial practitioners a low-cost, high-efficiency agent training paradigm. It demonstrates that the potential of base models can be fully unlocked simply by improving the reward allocation mechanism, without the need for costly online data labeling or complex cold-start phases. This has significant implications for lowering the barrier to entry for large model agentization and accelerating the deployment of vertical domain agents. By removing the dependency on extensive human-in-the-loop annotation, TRACE enables faster iteration cycles and more scalable development processes for enterprise-grade AI agents.

Outlook

The TRACE framework presents a versatile methodology with broad applicability beyond search tasks. The proposed credit estimation framework based on log-odds ratio state values can be extended to other long-horizon decision-making tasks, such as code generation and automated workflow orchestration. As agent systems are deployed in increasingly complex environments, the ability to precisely evaluate the contribution of each step in a long sequence will become a critical differentiator for system performance. TRACE provides a solid theoretical foundation and methodological reference for future research in this area.

Looking forward, the work of TRACE is expected to drive the development of reinforcement learning in long-horizon agents toward denser and more granular reward structures. By proving that effective learning can occur without additional Critic models or process-level annotations, TRACE opens new avenues for research into lightweight, efficient training algorithms. Future iterations may explore integrating TRACE with other advanced planning techniques or multi-agent coordination strategies to further enhance performance in highly dynamic environments.

Ultimately, TRACE represents a significant step forward in making reinforcement learning more accessible and effective for complex agent tasks. Its ability to improve search performance dramatically without cold-start fine-tuning or online data training sets a new standard for efficiency in the field. As the industry continues to push the boundaries of what AI agents can achieve, methods like TRACE will play a crucial role in enabling more reliable, efficient, and scalable autonomous systems. The emphasis on dense, turn-level feedback ensures that agents can learn from their interactions more effectively, leading to more robust and capable AI systems in the long run.