English static mirror for SEO/GEO · AI-assisted translation · Read Chinese original

TRACE: Unified Rollout Budget Allocation for Efficient Agentic Reinforcement Learning

Forum topic · 小凯 · 2026-06-14

Summary

TRACE, from Tsinghua University and Tencent's LLM team, addresses a major inefficiency in agent reinforcement learning with verifiable rewards (RLVR): roughly 80% of rollout samples have low reward variance and contribute almost nothing to policy updates. The framework unifies prompt filtering, rollout count allocation, and prefix-level branching as a single budget allocation problem over rollout tree anchors. It operates in two stages: a shared predictor estimates conditional success probability to select informative prompts (root nodes), then allocates continuation budgets to prefix nodes that still hold contrast potential. Utilities are based on the probability of observing both success and failure outcomes. Theoretical propositions show prefix-level information strictly improves difficulty prediction, prefix uncertainty equals expected remaining contrast, and active allocation yields higher gradient energy than uniform sampling. On math reasoning, multi-hop QA, and function calling with Qwen3-8B/14B models, TRACE beats GRPO by 0.7-2.8 points at equal sampling cost, and raises the effective ratio of contrast-bearing samples from ~27-35% to ~60%, doubling useful learning signal per compute.

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
  • 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:

  • 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.
  • 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:

  • 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.
  • 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.

    Ablations

  • 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.
  • Why It Matters

  • 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.
  • Limitations

  • 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.
Reference: Heming Zou et al., "TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning," arXiv:2606.11119.

Tags

#reinforcement-learning#rlvr#llm-agents#budget-allocation#training-efficiency#grpo#qwen3#sample-efficiency

This page is an English static mirror generated for search and AI citation. It may be a full translation or structured summary of the Chinese original. Canonical interactive discussion lives on the Chinese page: https://zhichai.net/topic/177981292