TRACE assigns turn-level credit to long-horizon tool-using agents

Introduction

Long-horizon agents rarely solve difficult search or browsing tasks in a single step. They may issue dozens or even hundreds of tool calls before producing a final answer. In that setting, a reward that only says whether the final answer is correct becomes a blunt training signal: a failed trajectory may still contain useful intermediate actions, while a successful one may include redundant or accidental steps.

The arXiv paper “TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents” addresses this bottleneck. TRACE is designed to provide denser turn-level rewards for agentic reinforcement learning without training an additional critic and without collecting process-level labels.

Key ideas

• Sparse outcome rewards are not enough. Final-answer rewards can work well for short reasoning tasks, but they become high-variance in long tool-use trajectories. They also risk assigning the same negative signal to every action in a failed rollout, including actions that actually moved the agent closer to the solution.
• Rollouts are viewed as state transitions. TRACE represents an agent trajectory at tool-call boundaries. Each tool interaction changes the context available to the model, creating a sequence of states that can be compared.
• A frozen reference model estimates value. Instead of learning a separate value model, TRACE queries a frozen reference model for the log probability of the gold answer under each state. These probabilities are transformed into log-ratio state values.
• Temporal-difference changes become rewards. The reward for an action is derived from the change in value between adjacent states. If a tool call makes the gold answer more likely, it receives positive credit; if it moves the agent away, the signal becomes weaker or negative.
• No process labels or critic training are required. This makes the method appealing for settings where step-by-step supervision is expensive and where training an additional critic may add complexity or instability.

Reported results

The authors test TRACE on long-horizon complex search. According to the abstract, the method improves base-model tool-use ability using pure RL, without a cold-start supervised fine-tuning stage, without an agentic mid-training stage, and without training on live-web data.

On the closed-web BrowseComp-Plus benchmark, the paper reports that Qwen3-4B improves from 7.2 to 35.6, while Qwen3-30B-A3B improves from 8.4 to 42.6. The learned search behavior is also said to transfer to open-web benchmarks, with learning curves showing earlier improvement and faster convergence during RL training.

Why it matters

TRACE matters because it tackles one of the central difficulties in training tool-using agents: knowing which intermediate actions deserve credit. As agents grow more capable and interact with longer tool chains, final outcomes alone become too coarse to guide learning efficiently.

If the reported gains hold across broader tasks and models, TRACE points to a practical direction for agent post-training: use an existing reference model to extract denser supervision from the same final-answer data. Rather than relying solely on more rollouts, more data, or human process annotations, the method tries to make each step of a trajectory more informative for reinforcement learning.

Source: arXiv