Long-horizon LLM agents make many tool calls before a final answer, and a single outcome reward at the end gives no credit to individual actions. TRACE fixes this by decomposing each rollout at tool-call boundaries, scoring every prefix by how predictable the gold answer becomes, and converting adjacent score differences into dense turn-level rewards. No critic network or process labels are needed.
TRACE uses a frozen reference model to estimate gold-answer log-probabilities for each prefix, turns them into log-ratio state values, and derives per-action rewards from temporal-difference changes between adjacent values. This dense signal is combined with the standard outcome advantage so final correctness remains the training anchor. Because redundant turns cannot inflate the one-step TD sum, the stays aligned with real progress.
On the closed-web BrowseComp-Plus benchmark, TRACE raises Qwen3-4B from 7.2 to 35.6 and Qwen3-30B-A3B from 8.4 to 42.6, using pure RL and no cold-start SFT, agentic mid-training, or live-web data. The learned search behavior also transfers to open-web benchmarks, and training curves show earlier and faster convergence.