TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning
- Paper: TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning (arXiv:2606.11119)
- Authors: Heming Zou, Qi Wang, Yun Qu, Yuhang Jiang, Lizhou Cai, Yixiu Mao, Ru Peng, Xin Xu, Weijie Liu, Kai Yang, Saiyong Yang, Xiangyang Ji
- Institutions: Tsinghua University, Tencent LLM group
- GRPO: uniform prompt sampling and uniform rollout counts.
- PCL: predicts prompt difficulty, but only at the root; ignores per-turn information differences.
- TreePO: builds tree rollouts, but branches randomly without information guidance.
- Root utility:
V_root(x_i, m) = 1 - v_i^m - (1-v_i)^m— the probability of at least one success and one failure among m rollouts. - Prefix utility:
V_pref(i,j,t,k) = 1 - [r·Ṽ_ψ + (1-r)(1-Ṽ_ψ)]^k— the probability of at least one observed reward flip among k continuations. - Both stages add up: on Qwen3-8B HotpotQA, uniform/uniform gives 49.5 accuracy / 42.8 effective ratio; active root + active prefix gives 50.6 / 52.3.
- Budget shape > budget size: with the same total budget (2048), wider root coverage (1024 roots × 2 expansions) beats deeper prefix sampling (512 × 6, TreePO-style): 50.6 vs 49.4 accuracy. The bottleneck is whether budget reaches contrast-capable states.
- Training efficiency: TRACE doesn't make the model smarter — it makes training smarter with the same compute.
- Effective ratio as a diagnostic: below 50% means your sampling strategy is wasting most compute.
- Prefix-level information is an agent-specific goldmine: each thought-action-observation turn is a semantically complete node with much larger contrast differences than text generation, explaining TRACE's strong agent-task gains.
- Primarily targets outcome-reward RLVR; tasks without terminal verification need rethinking.
- Depends on a (currently basic) predictor; better prediction → better budget placement.
- Validated mainly on math reasoning, multi-hop QA, function calling, at 8B-14B scale; larger models and more complex scenarios remain open.
- Predictor training and DP solving add overhead, negligible relative to rollout generation.
TL;DR
TRACE finds that about 80% of rollout samples in agentic RL training have low reward variance and contribute almost nothing to policy updates. It proposes tree-based budget allocation: first filter for high-information tasks at prompt root nodes, then allocate continuation budgets at prefix nodes, so the model learns from branches with contrast. Across math reasoning, multi-hop QA, and function calling, it improves accuracy by 0.7-2.8 points at equal sampling cost and raises the effective ratio (samples producing contrast signals) by 25-34%.
The Problem
RLVR (Reinforcement Learning with Verifiable Rewards) is the standard method for improving LLM reasoning and agent capabilities, but rollout-heavy training wastes compute: samples with low reward contrast (all-correct or all-wrong) contribute little to the policy gradient. Existing methods share a blind spot:
All ignore prefix-level information differences — the uncertainty of step 1 vs step 5 of the same rollout differs greatly, yet budget is spread uniformly.
Method: Budget Allocation as an Investment Decision
TRACE unifies three operations into one framework: prompt filtering (root budget = 0 or ≥ 2), rollout count allocation, and prefix branching decisions — all are budget placement at rollout tree anchors to maximize reward contrast.
Two-stage pipeline:
1. Global root allocation: a shared predictor estimates each prompt's conditional success probability; an optimization yields root counts {m_i}, funding only prompts with contrast potential. 2. Local prefix expansion: for activated prompts, generate m_i rollouts, score each prefix node, and allocate continuation counts {K_{i,j,t}} only where contrast potential remains.
Key utilities:
Insight: sample where information is, not where tasks are hard.
Theoretical Results
1. Prefix information improves group difficulty prediction: prefix-level prediction is at least as informative as prompt-level, and strictly better. 2. Prefix uncertainty = remaining contrast potential: the expected cumulative variation of conditional success probability below a prefix equals V(1−V). 3. Active allocation > uniform allocation: under a standardized conditional gradient energy assumption, TRACE's allocation yields strictly higher expected gradient energy.
Experimental Results
Math reasoning (in-distribution / out-of-distribution):
| Model | GRPO | TRACE | |---|---|---| | Qwen3-8B | 70.0 / 74.6 | 71.1 / 75.3 | | Qwen3-14B | 73.5 / 77.1 | 74.9 / 77.8 |
Multi-hop QA & function calling: Qwen3-14B improves multi-hop QA from 51.2 to 54.0 (+2.8) and function calling from 46.1 to 48.0 (+1.9) over GRPO.
Effective ratio (samples with both success and failure rollouts):
| Setting | GRPO | TRACE | |---|---|---| | Math 8B | 26.8% | 60.6% | | Math 14B | 34.7% | 59.7% |
GRPO only produces useful learning signal in ~27-35% of samples; TRACE roughly doubles it at the same compute.