TLDR: Tree-GRPO is a novel reinforcement learning method for LLM agents that utilizes a tree-search approach, where each node represents a complete agent interaction step. This design allows for more efficient sampling, generating more rollouts within a fixed budget, and constructs finer-grained supervision signals from outcome rewards. Experimental results across 11 datasets demonstrate that Tree-GRPO consistently outperforms traditional chain-based RL methods, particularly for smaller models, leading to higher performance, more stable training, and reduced computational costs.
Large Language Models (LLMs) are becoming increasingly capable, especially when used as “agents” that can interact with environments over multiple steps, like using tools or searching the web. However, training these LLM agents with traditional reinforcement learning (RL) methods faces two big hurdles: they require a lot of computational resources (known as “rollout budget”) and struggle with “sparse supervision,” meaning it’s hard to tell which specific action in a long sequence led to a good or bad outcome.
A new research paper introduces an innovative solution called Tree-based Group Relative Policy Optimization (Tree-GRPO). This method significantly enhances how LLM agents learn by adopting a tree-search approach instead of the common chain-based methods. The core idea is to make each “node” in the search tree represent a complete agent interaction step, which includes a thought, an action (like using a tool), and an observation from the environment.
One of the primary advantages of Tree-GRPO is its efficiency. By sharing common prefixes in the tree structure, the method can generate many more “rollouts” (simulated interactions) within the same budget of tokens or tool calls. This is crucial because LLM interactions can be very expensive. The paper states that this tree-search sampling can yield approximately 1.5 times more samples compared to traditional chain-based methods, which is a substantial gain for multi-turn agent training.
Beyond efficiency, Tree-GRPO also tackles the sparse supervision problem. The tree structure naturally allows for the creation of more detailed, step-by-step supervision signals, even when only a final outcome reward is provided. This is achieved by estimating “grouped relative advantages” at two levels: within each tree (intra-tree) and across all trees (inter-tree). The theoretical analysis shows that the intra-tree group relative policy optimization is similar to direct preference learning at the step level, providing a finer-grained learning signal.
The researchers put Tree-GRPO to the test across 11 different datasets, covering three types of question-answering tasks: multi-hop, single-hop, and web-agent tasks. The results were compelling. Tree-GRPO consistently outperformed chain-based RL methods, especially for smaller models (those with fewer than 7 billion parameters). For instance, on multi-hop QA tasks, models under 3 billion parameters showed relative improvements ranging from 16% to a remarkable 69%.
Notably, Tree-GRPO demonstrated its ability to enable a base model to learn complex multi-turn agent interactions without needing extensive supervised fine-tuning (SFT), even with a very limited rollout budget. One impressive finding was that a Qwen2.5-3b model trained with Tree-GRPO achieved superior performance while using only a quarter of the rollout budget compared to chain-based methods.
Furthermore, the study found that Tree-GRPO not only improved performance but also encouraged LLM agents to engage in longer, more exploratory interactions, making more tool calls on average to solve complex multi-hop QA tasks. This is a significant step towards building agents capable of tackling more challenging, long-horizon problems. The method also proved more stable across various training configurations, including different learning rate warmup ratios.
Also Read:
- ToMPO: Boosting LLM Strategic Decisions in Complex Social Games
- Improving LLM Performance and Clarity with Probability Smoothing Policy Optimisation
In conclusion, Tree-GRPO offers a robust and efficient approach to training LLM agents. By intelligently structuring the rollout process with agent step-level tree search and deriving fine-grained process supervision, it addresses key limitations of current reinforcement learning methods for LLMs, paving the way for more capable and cost-effective AI agents. You can read the full paper here.
