TreeRL: LLM Reinforcement Learning with On-Policy Tree Search

• URL: http://arxiv.org/abs/2506.11902v1
• Date: Fri, 13 Jun 2025 15:52:37 GMT
• Title: TreeRL: LLM Reinforcement Learning with On-Policy Tree Search
• Abstract summary: Reinforcement learning (RL) with tree search has demonstrated superior performance in traditional reasoning tasks.<n>We propose TreeRL, a reinforcement learning framework that directly incorporates on-policy tree search for RL training.
• Score: 36.08914596340525
• License: http://creativecommons.org/licenses/by/4.0/
• 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 a 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.

Related papers

• Process Reward Informed Tree Rollout for Effective Multi-Turn RL [58.392997761968566]
  In long-horizon agentic tasks, a uniform rollout strategy can waste budget on uninformative dead-end attempts.<n>We propose Process-Scorer Guided Adaptive Tree Rollout (PATR), a quality-aware rollout framework for multi-turn agent RL.<n>PATR uses task-appropriate process feedback to score partial trajectories, selectively branches from promising states, reuses shared prefixes, and conservatively stops paths to reduce wasted sampling.
  arXiv  Detail & Related papers  (2026-07-17T04:16:58Z)
• MARS$^2$: Scaling Multi-Agent Tree Search via Reinforcement Learning for Code Generation [29.92851142870157]
  Reinforcement learning (RL) paradigms have demonstrated strong performance on reasoning-intensive tasks such as code generation.<n>We propose textbfMARS$2$ (Multi-Agent Reinforced Tree-Search Scaling), a unified RL framework in which multiple independently-optimized agents collaborate.
  arXiv  Detail & Related papers  (2026-04-16T02:52:24Z)
• TreePS-RAG: Tree-based Process Supervision for Reinforcement Learning in Agentic RAG [71.06073770344732]
  Agentic retrieval-augmented generation (RAG) formulates question answering as a multi-step interaction between reasoning and information retrieval.<n>We present TreePS-RAG, an online, tree-based RL framework for agentic RAG that enables step-wise credit assignment while retaining outcome-only rewards.
  arXiv  Detail & Related papers  (2026-01-11T14:07:30Z)
• TreeGRPO: Tree-Advantage GRPO for Online RL Post-Training of Diffusion Models [14.130608036489336]
  Reinforcement learning (RL) post-training is crucial for aligning generative models with human preferences, but its prohibitive computational cost remains a major barrier to widespread adoption.<n>We introduce textbfTreeGRPO, a novel RL framework that dramatically improves training efficiency by recasting the denoising process as a search tree.
  arXiv  Detail & Related papers  (2025-12-09T01:17:34Z)
• Tree Search for LLM Agent Reinforcement Learning [23.7084695563981]
  Tree-based Group Relative Policy Optimization (Tree-GRPO) is a grouped agent RL method based on tree search.<n>By sharing common prefixes, the tree search sampling increases the number of rollouts achievable.<n>We demonstrate that the objective of intra-tree level group relative policy optimization is equivalent to that of step-level direct preference learning.
  arXiv  Detail & Related papers  (2025-09-25T14:37:09Z)
• Policy Guided Tree Search for Enhanced LLM Reasoning [3.090041654375235]
  Policy-Guided Tree Search (PGTS) is a framework that combines reinforcement learning with structured tree exploration to efficiently navigate reasoning paths.<n>Our key innovation is a learned policy that dynamically decides between expanding, branching, backtracking, or terminating exploration, eliminating the need for manuals or exhaustive search.
  arXiv  Detail & Related papers  (2025-02-04T22:08:20Z)
• RL-LLM-DT: An Automatic Decision Tree Generation Method Based on RL Evaluation and LLM Enhancement [82.02155942106877]
  We propose RL-LLM-DT, an automatic decision tree generation method based on RL Evaluation and LLM Enhancement.<n>To evaluate the effectiveness of this integrated approach, we conducted experiments in a curling game.
  arXiv  Detail & Related papers  (2024-12-16T03:33:49Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search [50.45155830888697]
  We develop a reinforced self-training approach, called ReST-MCTS*, based on integrating process reward guidance with tree search MCTS* for collecting higher-quality reasoning traces as well as per-step value to train policy and reward models. We first show that the tree-search policy in ReST-MCTS* achieves higher accuracy compared with prior LLM reasoning baselines such as Best-of-N and Tree-of-Thought, within the same search budget.
  arXiv  Detail & Related papers  (2024-06-06T07:40:00Z)
• RLET: A Reinforcement Learning Based Approach for Explainable QA with Entailment Trees [47.745218107037786]
  We propose RLET, a Reinforcement Learning based Entailment Tree generation framework. RLET iteratively performs single step reasoning with sentence selection and deduction generation modules. Experiments on three settings of the EntailmentBank dataset demonstrate the strength of using RL framework.
  arXiv  Detail & Related papers  (2022-10-31T06:45:05Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  Machine learning has emerged as a promising paradigm for branching. We propose retro branching; a simple yet effective approach to RL for branching. We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
  arXiv  Detail & Related papers  (2022-05-28T06:08:07Z)
• Decoupling Exploration and Exploitation in Reinforcement Learning [8.946655323517092]
  We propose Decoupled RL (DeRL) which trains separate policies for exploration and exploitation. We evaluate DeRL algorithms in two sparse-reward environments with multiple types of intrinsic rewards.
  arXiv  Detail & Related papers  (2021-07-19T15:31:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.