Skip to main content
Back

Tree-GRPO Cuts AI Agent Training Costs by 75% Without Losing Performance

A new tree-search variant of GRPO gives multi-turn LLM agents step-level credit from outcome rewards alone, and matches chain-based RL on a quarter of the rollout budget.

Pro

  • Tree-GRPO restructures agent rollouts as trees of ReAct steps, sharing prefixes to save tokens and tool calls.
  • Sibling branches under shared prefixes produce step-level preference signals from outcome rewards alone.
  • Intra-tree GRPO is shown to have the same gradient structure as step-level DPO, but online.
  • On Qwen2.5-3B, matches chain-based GRPO with a quarter of the rollout budget across multi-hop QA.
  • Up to 69% relative improvement on small models; encourages longer tool-use interactions (2.4 to 3.0 calls).
  • Code available at github.com/AMAP-ML/Tree-GRPO; evaluated on 11 QA benchmarks.

Training LLM agents with reinforcement learning has a nasty scaling problem. Every rollout can burn thousands of tokens and multiple paid tool calls, and at the end of that whole trajectory the model gets a single scalar reward telling it whether the final answer was right. Somewhere across those five or ten tool calls, the model made good and bad decisions, but the training signal has no idea which is which. Researchers from Xiamen University, Alibaba's AMAP group, and SUSTech have proposed Tree-GRPO, a modification to Group Relative Policy Optimization that turns those flat trajectory rewards into step-level supervision by restructuring the rollout itself as a tree.

The code is on GitHub, and the headline result is striking: on Qwen2.5-3B, the tree version beats chain-based GRPO on multi-hop question answering while using only a quarter of the token and tool-call budget.

Comparison of chain-based versus tree-based agent RL showing rollout budget and performance advantages

The sparse reward tax on agents

RL-tuned LLMs trained only with outcome rewards have shown strong gains in single-turn tasks like math and code, but agent settings work differently. Agents interact with the environment over multiple turns and complete tasks through sequential decision-making, producing trajectories with thousands of tokens and many tool calls. Two things go wrong under standard GRPO:

  • Rollout costs dominate training. Existing group-based methods sample multiple independent trajectories per task in a chain-based scheme with substantial redundancy, and the sampling phase dominates overall training time while tool calls incur real API costs.
  • The reward is too coarse to learn from. Trajectory-level sparse signals make it hard to identify which specific steps contributed to success or failure, so even with a larger rollout budget the model gets the same limited feedback, leading to imbalanced learning and sometimes training collapse.

The usual escape hatch is a Process Reward Model that scores intermediate steps, but step-level human annotations are expensive and PRMs themselves are hard to train, so those approaches have not scaled to general scenarios. Tree-GRPO tries to get step-level signal for free.

Rollouts as trees, nodes as ReAct steps