TreeRL: LLM Reinforcement Learning with On-Policy Tree Search
Zhenyu Hou, Ziniu Hu, Yujiang Li, Jie Tang, Yuxiao Dong · 2025
Read TreeRL: LLM Reinforcement Learning with On-Policy Tree Search by Zhenyu Hou, Ziniu Hu, Yujiang Li, Jie Tang, Yuxiao Dong (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-11902.txt.
Introduction
Hou and co-authors present a 2025 paper on training language models with tree search inside reinforcement learning. Instead of sampling whole answer chains one by one, a tree search branches at unsure steps and scores paths as they grow. That gives denser feedback during training. Older work often trained a separate reward model, which can drift from the policy and invite gaming.
Their framework, TreeRL, folds on-policy tree search straight into training and needs no separate reward model. Branching from high-uncertainty steps raises search yield for the same token budget. Tests on hard math and code tasks beat chain-based training, the authors report. They released the code in public for other teams.
Catalog record
| CREATOR | Zhenyu Hou, Ziniu Hu, Yujiang Li, Jie Tang, Yuxiao Dong |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-11902
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
TreeRL: LLM Reinforcement Learning with On-Policy Tree Search Zhenyu Hou, Ziniu Hu, Yujiang Li, Jie Tang, Yuxiao Dong Abstract Reinforcement learning (RL) with tree search has demonstrated superior performance in traditional reasoning tasks. Compared to conventional independent chain sampling strategies with outcome supervision, tree search enables better exploration of the reasoning space and provides dense, on-policy process rewards during RL training but remains under-explored in On-Policy LLM RL. We propose TreeRL, a reinforcement learning framework that directly incorporates on-policy tree search for RL training. Our approach includes intermediate supervision and eliminates the need for separate reward model training. Existing approaches typically train a separate process reward model, which can suffer from distribution mismatch and reward hacking. We also introduce a cost-effective tree search approach that achieves higher search efficiency under the same generation token budget by strategically branching from high-uncertainty intermediate steps rather than using random branching. Experiments on challenging math and code reasoning benchmarks demonstrate that TreeRL achieves superior performance compared to traditional ChainRL, highlighting the potential of tree search for LLM. TreeRL is open-sourced at https://github.com/THUDM/TreeRL . 1 1 footnotetext: Equal contribution; order is alphabetical. 1 Introduction Large language models (LLMs) have demonstrated remarkable capabilities across diverse complex reasoning tasks ( Achiam et al. 2023 ; Team et al. 2023 ; Dubey et al. 2024 ) , including mathematics Shao et al. 2024b , programming ( Lozhkov et al. 2024 ; Zhu et al. 2024 ) , and autonomous agents ( Zhou et al. 2024 ) . Reinforcement learning (RL) has emerged as a powerful approach to significantly improve the reasoning abilities of LLMs by optimizing the policy through reward feedback ( OpenAI 2024 ; Guo et al. 2025 ; Hou et al. 2025 ; Shao et al. 2024b ) . Figure 1: Left : Performance comparison of sampling strategies. EPTree consistently outperforms i.i.d multi-chain sampling and MCTS under different inference budgets. Right : TreeRL powered with EPTree demonstrates better performance than ChainRL with i.i.d multi-chain sampling. Figure 2: Illustration of offline training with tree search (Left), traditional ChainRL with online i.i.d multi-response sampling (Middle), and TreeRL with tree search (Right). Current RL methods for LLM training generally independently sample multiple trajectories Shao et al. 2024b ; Wang et al. 2024b ; Touvron et al. 2023 and obtain reward signals based on the final answers. However, tree search, which has demonstrated significant success in other domains like AlphaZero Silver et al. 2017 , remains under-developed in reinforcement learning for LLM reasoning. Existing efforts have mainly focused on using tree search to enhance inference-time performance alongside an external reward Zhang et al. 2024a ; Chen et al. 2024a , or to produce data for offline training Chen et al. 2024a ; Xie et al. 2024 ; Zhang et al. 2024a (e.g., finetuning or DPO Rafailov et al. 2023 ), as illustrated in Figure 2 . But Guo et al. 2025 also demonstrates the limitation of distribution shift and reward hacking in offline tree search compared to online RL training. Up to now, the potential of on-policy RL training incorporating tree search to improve LLM reasoning remains largely unexplored. The challenges are two-fold. First, classical Monte Carlo Tree Search (MCTS) ( Browne et al. 2012 ) can be less effective nd efficient than independently sampling multiple responses. MCTS achieves a lower PassRate performance under the same inference cost, as shown in Figure 1 . The step-by-step generation requires numerous iterations and is not friendly to modern LLM inference engines. Second, though tree search could provide fine-grained process supervision, the derived offline process reward model almost contributes to no performance improvement in RL training Guo et al. 2025 . To address this gap, we propose TreeRL, a reinforcement learning (RL) approach for LLMs employed with tree search. Under the same inference cost as independent multiple sampling, our method generates more diverse and effective responses and also provides on-policy process supervision signals to further boost RL performance. First, we introduce an efficient and effective tree search strategy EPTree. Unlike MCTS which breaks answers into smaller parts to allow the model to explore step-by-step, we obtain a new response by forking branches from the most uncertain intermediate tokens in the existing tree based on entropy and continuing the generation until the final answer. Thus EPTree requires fewer tokens but encourages effective exploration for the diverse answers. And it typically requires only around two iterations to form the generation trees. One step further, we leverage the tree search for reinforcement learning with process supervision. Each step in the trees is assigned a credit based on advantage, i.e., how much that step improves the likelihood of reaching a correct solution compared to other steps. The process signal for a given reasoning step is calculated as a weighted sum of two components: 1) global advantage, which reflects the step’s potential over the overall correctness rate for the question, and 2) local advantage, which quantifies the improvement the step provides compared to its parent step in the tree. Since these advantage signals are derived directly from the on-policy generated trees, they are inherently resistant to reward hacking ( Skalse et al. 2022 ) and do not rely on any additional reward models. We evaluate TreeRL on challenging college-level and competition-level math and code reasoning benchmarks based on Qwen ( Qwen 2024 ) and GLM ( GLM et al. 2024 ) . Experiments show that TreeRL achieves superior performance and demonstrates advantages over traditional independent multi-chain sampling. The gain benefits from both EPTree with promising PassRate performance and process supervision. These results highlight the potential of RL with tree search to advance complex reasoning capabilities for LLM. The implementation of TreeRL is available at https://github.com/THUDM/TreeRL . Figure 3: Illustration of TreeRL. In each iteration, TreeRL first performs a tree search using EPTree, progressively expanding branches from the top- N most uncertain tokens. The resulting tree, along with the process supervision signals derived from each step, is then fed into reinforcement learning to update the policy model. 2 Preliminary To align the fine-tuned model \pi_{\theta} with feedback signals, Ouyang et al. 2022 proposes to apply reinforcement learning (RL) to enable LLM to learn from self-exploration. Reinforcement learning maximizes a reward signal, e.g., human preference or final answer correctness. The typical RL for the LLM process works as follows: for a given prompt {\bm{x}} , the policy model \pi_{\theta} generates K possible responses, denoted as ({\bm{y}}_{1},\dots,{\bm{y}}_{K}) . The reward function r({\bm{x}},{\bm{y}}_{i}) then assigns a scalar reward to each pair ({\bm{x}},{\bm{y}}_{i}) . Afterward, the policy model \pi_{\theta} is updated using reinforcement learning to optimize the following objective: \underset{{\bm{x}}\sim p_{\text{data}},{\bm{y}}\sim\pi_{\theta}}{\mathbb{E}}\frac{1}{K}\sum_{i}^{K}A({\bm{x}},{\bm{y}}_{i})\log\pi_{\theta}({\bm{y}}_{i}|{\bm{x}}) (1) where A(\cdot) is the advantage function and usually defined as A({\bm{x}},{\bm{y}}_{i})=\beta(r({\bm{x}},{\bm{y}}_{i})-b) , where b is the baseline Mei et al. 2022 ; Chung et al. 2021 and varies in different methods. For example, A({\bm{y}}_{i})=\frac{r({\bm{y}}_{i})-\text{mean}\{r({\bm{y}}_{i})\}}{\text{std}\{r({\bm{y}}_{i})\}} in GRPO Shao et al. 2024b and A({\bm{y}}_{i})=r({\bm{y}}_{i})-\frac{1}{K-1}\sum_{j\neq i}^{K}r({\bm{y}}_{i}) in RLOO Ahmadian et al. 2024 . 3 TreeRL: Reinforcement Learning with Tree Search In this section, we present TreeRL to improve LLM reasoning with tree search. Figure 3 shows the overview of TreeRL. We first present an efficient and effective tree search algorithm EPTree, which guides tree search by token-level uncertainty instead of traditional Monte Carlo Tree