🤖 machine learning

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

TRACE introduces a dense, critic-free credit assignment method for long-horizon agents that derives per-turn rewards from temporal-difference changes in log-ratio state values, enabling pure reinforcement learning to significantly improve tool-use performance on complex search benchmarks without requiring supervised fine-tuning or live-web data.

Original authors: Leitian Tao, Baolin Peng, Wenlin Yao, Tao Ge, Hao Cheng, Mike Hang Wang, Jianfeng Gao, Sharon Li

Published 2026-07-16

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Leitian Tao, Baolin Peng, Wenlin Yao, Tao Ge, Hao Cheng, Mike Hang Wang, Jianfeng Gao, Sharon Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to solve a giant, multi-step mystery. In the world of artificial intelligence, this is called "agentic reinforcement learning." Think of the robot as a detective who doesn't just guess the answer once, but spends hours searching libraries, opening files, asking questions, and gathering clues before finally shouting, "I found the culprit!" The tricky part is figuring out how to teach the detective. If the detective gets the answer wrong at the very end, a simple teacher might just say, "Bad job," and give a zero. But that's unfair! Maybe the detective spent the first hour finding the right clues, only to trip over a loose floorboard in the final minute. If you punish the whole hour of hard work just because of the last mistake, the detective gets confused and stops trying to gather clues. This is the problem of "credit assignment": how do you give credit for the good steps and blame for the bad ones when the reward only comes at the very end?

This paper, titled TRACE, tackles this exact headache for AI agents that have to take many turns to solve a problem. The researchers propose a clever way to give the detective a "thumbs up" or "thumbs down" after every single step (like every search or file opening), rather than waiting until the end. They do this without needing a human to grade every step or a super-smart judge to watch the whole movie. Instead, they use a "frozen reference model"—think of it as a calm, unchanging librarian who knows the answer key. After every move the detective makes, the librarian checks: "Does this new clue make the final answer easier to guess?" If yes, the detective gets a small reward. If no, they get a tiny penalty. This method, called TRACE, helps the AI learn much faster and better than just waiting for the final grade.

The Detective's Dilemma

Imagine you are training a robot to find the birthplace of a fictional author named "Elena Cruz." The robot has to use a browser to search, open pages, and read text. It might take 20 clicks to get there. In the old way of training these robots (called "outcome-only" training), the robot would go through all 20 clicks, maybe get the answer wrong, and then the computer would say, "Fail." The robot would then try again, but it wouldn't know which of those 20 clicks were helpful. Maybe the first 15 clicks found the right book, but the 16th click opened a page about a different Elena, leading to the wrong answer. The old method treats the helpful first 15 clicks the same as the useless 16th click: both get punished. It's like getting a bad grade on a math test because you made a tiny arithmetic error at the end, even though you solved the hard algebra correctly.

The researchers found that this "all-or-nothing" approach makes it very hard for robots to learn complex, long tasks. The robot gets confused, the training takes forever, and it often gives up on exploring new ideas because it's afraid of making a mistake at the very end.

The TRACE Solution: A Scorecard for Every Step

The authors of this paper came up with TRACE (Turn-level Reward Assignment via Credit Estimation). Instead of waiting for the final answer to grade the robot, TRACE gives the robot a score after every single tool call (every search, every open, every click).

Here is how it works, using our detective analogy:

The Frozen Librarian: The system uses a "frozen reference model." Imagine a librarian who has already read the answer key and will never change their mind. This librarian is "frozen," meaning they don't learn or get confused; they just act as a steady measuring stick.
The Progress Check: After the robot makes a move (like searching for "Elena Cruz"), the librarian checks the robot's current notes. The librarian asks, "Based on what the robot has found so far, how easy is it to guess the correct answer?"
The Score Change: If the robot's new search makes the answer easier to guess, the robot gets a positive score. If the search leads to a dead end or a confusing page, the score goes down.
The Magic of "Telescoping": The paper uses a math trick called "Temporal-Difference" (TD). Think of it like a ladder. If you climb one rung up, you get credit for that rung. If you climb up and then accidentally slide back down, you lose credit for the slide. The system adds up these tiny changes. If the robot spends 10 turns gathering good clues and then makes one bad move, the system sees the 10 good steps as positive and the one bad step as negative. It doesn't punish the 10 good steps just because the final answer was wrong.

This method is special because it doesn't need a human to write down "Good job" after every step, nor does it need a second, super-smart AI to watch the robot and grade it. It just uses the "frozen librarian" to see if the robot is getting closer to the truth.

What They Found

The researchers tested TRACE on a very difficult task: finding specific facts hidden deep inside a massive collection of documents (a "closed-web" search). They used two different sizes of AI models: a smaller one (Qwen3-4B) and a larger one (Qwen3-30B-A3B).

The results were impressive. Before using TRACE, the smaller model could only solve about 7.2% of the hard search questions. After training with TRACE, it jumped to 35.6%. The larger model went from 8.4% to 42.6%. These are huge improvements, especially considering they didn't use any "cold-start" training (where you teach the robot with perfect examples first) or live internet data. They just used the TRACE method on the raw model.

The paper also showed that TRACE works even when the robot is tested on the open internet, not just the practice library they trained on. The robot learned a general skill for searching and reading that transferred to new places. For example, the larger model scored 12.9 on a benchmark called BrowseComp, 52.0 on GAIA, and 45.0 on a Chinese deep-search test.

Why It Matters and What It Doesn't Do

The paper suggests that this method makes learning much faster. In their experiments, the robots trained with TRACE started getting better much earlier and reached their peak performance faster than robots trained with the old "wait until the end" method. The learning curves showed that the robots were learning to explore and gather evidence more effectively.

However, the authors are careful to point out the limits of their work. This method works best when the final answer is short and clear, like a name, a date, or a number. If the robot's job is to write a long, complex story or fix a broken computer program where the "right" answer is open-ended and hard to define, this method might not work as well. The "frozen librarian" needs a clear answer key to check against. If the answer is vague, the librarian can't tell if the robot is getting closer.

In short, TRACE is a new way to teach AI agents how to be good detectives. Instead of waiting until the end of the case to say "Good job" or "Bad job," it gives a scorecard after every clue found. This helps the AI understand that gathering evidence is valuable, even if the final guess isn't perfect, leading to smarter, faster, and more reliable search agents.

Technical Summary: TRACE (Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents)

1. Problem Statement

Large Language Model (LLM) agents solve complex tasks through extended sequences of tool interactions (e.g., web search, code execution) before producing a final answer. While Reinforcement Learning with Verifiable Rewards (RLVR) has been successful for single-turn reasoning tasks (like math or coding) using deterministic outcome rewards, applying this to long-horizon agents presents a fundamental credit assignment challenge.

In multi-turn agent rollouts, a single terminal reward (success/failure) is sparse and high-variance. It fails to distinguish between:

Useful actions: Early tool calls that gather necessary evidence but are part of a trajectory that eventually fails.
Redundant or harmful actions: Intermediate steps that do not contribute to the goal or derail the agent.

Outcome-only training assigns the same advantage to all turns in a trajectory, leading to under-crediting productive exploration, over-crediting irrelevant actions, and increased gradient variance as trajectory horizons grow. Existing process supervision methods often require step-level labels, strong LLM judges, or trained process reward models, which introduce complexity, drift, or dependency on expensive supervision.

2. Methodology: TRACE

The authors propose TRACE (Turn-level Reward Assignment via Credit Estimation), a critic-free framework that generates dense, turn-level rewards without additional process-label training or a learned critic.

Core Mechanism

TRACE treats the agent's rollout as a sequence of state transitions occurring at tool-call boundaries. Instead of learning a value function, it utilizes a frozen reference model ( $\pi_{ref}$ ) as a stable probe to estimate the "readiness" of the current trajectory prefix to produce the gold answer.

State Representation: A rollout is segmented into prefixes $S_k$ at each tool-call boundary.
State Value Estimation:
- The frozen reference model computes the log-probability of the gold answer $y^*$ given the prefix $S_k$ : $\bar{\ell}_k = \frac{1}{|y^*|} \sum \log \pi_{ref}(y^*_t | S_k, y^*_{<t})$ .
- To handle scale issues where raw log-probability changes are misleading (e.g., a small gain is significant when far from the answer but negligible when close), TRACE transforms this into a log-ratio state value:
  $V(S_k) = \log \frac{-\bar{\ell}_0 + \epsilon}{-\bar{\ell}_k + \epsilon}$
  where $\epsilon$ is an offset. This value measures the relative closure of the initial answer-likelihood gap.
Turn-Level Reward via Temporal Difference (TD):
- The reward for a transition $S_k \to S_{k+1}$ is derived from the TD error (value difference):
  $\delta_k = V(S_{k+1}) - V(S_k) = \log \frac{d_k}{d_{k+1}}$
- Interpretation: A positive reward is assigned if the tool call and its observation make the gold answer more predictable (increasing the state value). A negative reward is assigned if the trajectory moves away from the answer.
- Telescoping Property: The sum of one-step TD credits telescopes to the total value change between the start and end of the trajectory. This ensures that redundant intermediate turns cannot artificially inflate the total credit.
Look-Ahead and Anchoring:
- To account for delayed effects (e.g., a search query that only pays off after a document is opened), TRACE uses a truncated K-step TD backup with a discount factor $\gamma_{td}$ .
- The final turn-level reward combines the TD progress signal with the standard outcome-level advantage ( $A^{out}$ ) from Group Relative Policy Optimization (GRPO), ensuring the final correctness remains the ultimate training target.
Optimization: The policy is updated using a clipped objective that mixes the outcome advantage and the turn-level TD credit, without normalizing turn values across the prompt group.

3. Key Contributions

Critic-Free Dense Credit: TRACE provides dense, turn-level rewards for long-horizon agents without training a separate critic, process reward model, or relying on step-level human/synthetic labels.
Frozen Reference as a Probe: It repurposes a frozen reference model (typically used for KL regularization) as a stable value estimator, measuring how much each tool interaction increases the predictability of the gold answer.
Log-Ratio TD Formulation: The method introduces a log-ratio transformation of answer probabilities to create a robust state value that normalizes credit across different confidence levels and prevents reward inflation from redundant steps.
Pure RL Training: The approach enables effective training of base models using pure RL (outcome + turn-level rewards) without a cold-start supervised fine-tuning (SFT) stage, agentic mid-training, or live-web data.

4. Experimental Results

The authors evaluated TRACE on long-horizon complex search tasks using Qwen3-4B and Qwen3-30B-A3B backbones.

Closed-Web Benchmark (BrowseComp-Plus):
- Qwen3-4B: Improved from a base score of 7.2 to 35.6.
- Qwen3-30B-A3B: Improved from a base score of 8.4 to 42.6.
- TRACE significantly outperformed outcome-only baselines (GRPO, GSPO, GiGRPO) and approached or surpassed larger external deep-research agents (e.g., TongyiDS-30B-A3B) despite using a smaller backbone and minimal supervision.
Open-Web Transfer:
- The learned search behavior transferred to open-web benchmarks (BrowseComp, GAIA, xbench-DeepSearch).
- The 30B-A3B agent achieved 12.9 on BrowseComp, 52.0 on GAIA, and 45.0 on xbench-DeepSearch, demonstrating generalization beyond the closed training corpus.
Learning Dynamics:
- TRACE showed earlier improvement and faster convergence compared to outcome-only baselines.
- It facilitated a faster expansion of interaction length (trajectory scale) in early training stages, as the turn-level signal rewarded intermediate progress even before the final answer was correct.

5. Significance and Claims

The paper claims that verifier-anchored turn-level credit is a critical missing component for training long-horizon agents via pure RL.

Efficiency: TRACE demonstrates that base models possess latent reasoning and tool-use primitives that can be unlocked with denser credit signals, eliminating the need for expensive SFT or complex process supervision pipelines.
Generalization: The method teaches a general interaction strategy (searching, reading, refining) that transfers across different retrieval environments and languages, not just overfitting to the training corpus.
Limitations: The authors modestly note that the current method relies on compact, verifiable answers (short strings). For tasks with long, structured, or open-ended outputs (e.g., multi-file code patches), the log-probability proxy may be less reliable, suggesting a need for alternative state-value estimators in future work.

In summary, TRACE establishes that assigning credit at tool-call boundaries via a frozen reference model is an effective, scalable, and data-efficient strategy for enhancing long-horizon agent performance.