Tree Search for LLM Agent Reinforcement Learning
Authors: Yuxiang Ji
Ziyu Ma
Yong Wang
Guanhua Chen
Xiangxiang Chu
Liaoni Wu
Venue: ICLR 2026 Poster (2026)
Keywords: Tree Search
LLM
Agent
Reinforcement Learning
Primary area: foundation or frontier models, including LLMs

Abstract: Recent advances in reinforcement learning (RL) have significantly enhanced the agentic capabilities of large language models (LLMs).
In long-term and multi-turn agent tasks, existing approaches driven solely by outcome rewards often suffer from the problem of sparse supervision.
To address the challenge, we propose Tree-based Group Relative Policy Optimization (Tree-GRPO), a grouped agent RL method based on tree search, where each tree node represents the complete agent interaction step.
By sharing common prefixes, the tree search sampling increases the number of rollouts achievable within a fixed budget of tokens or tool calls.
Moreover, we find that the tree-structured trajectory naturally allows the construction of step-wise process supervised signals even using only the outcome reward.
Based on this, Tree-GRPO estimates the grouped relative advantages both on intra-tree and inter-tree levels.
Through theoretical analysis, we demonstrate that the objective of intra-tree level group relative policy optimization is equivalent to that of step-level direct preference learning.
Experiments across 11 datasets and 3 types of QA tasks demonstrate the superiority of the proposed tree-based RL over the chain-based RL method.

Published as a conference paper at ICLR 2026
TREE SEARCH FOR LLM AGENT REINFORCEMENT LEARNING
Yuxiang J Ziyu Ma², Yong Wang Guanhua Chen?, Xiangxian Chu², Liaoni Wu" I Xiamen University AAMAP, Alibaba Group "Southern University of Science and Technology
O GitHub: btttps://gite http://www..caaaaaaaa//tttee--e
ABSTRACT
Recent advances in reinforcement learning (RL) have significantly enhanced the agentic capabilities of large language models (LLMss). In long-term and multi-turn agent tasks, existing approaches driven solely by outcome rewards often suffer from the problem of sparse supervision. To address the challenge, we propose Tree-based Group Relative Policy Optimization (Tree-GRPO), grouped agent RL method based on tree search, where each tree node represents the complete agent interaction step. By sharing common prefixes, the tree search sampling increases the number of rollouts achievable within a fixed budget of tokens or tool calls. Moreover, we find that the tree-structured trajectory naturally allows the construction of step-wise process supervised signals even using only the outcome reward. Based on this, Tree-GRPO estimates the grouped relative advantages both intra-tree and inter-tree levels. Through theoretical analysis, we demonstrate that the objective of intra-tree level group relative policy optimization is equivalent to that of step-level direct preference learning. Experiments across 11 datasets and 3 types of QA tasks demonstrate the superiority of the proposed tree-based RL over the chain-based RL method.
Rellout Budget
Ag
Chats hand
Tree bared (teal Callo
Proces Signal
Preferenes
Trajectory Signal
At 42
Chal--aandd True faced
Prefference
Signal
Sodwats
fotoor Dedget
Chais-based Agent R1. v.s. Trae-based Agent R1.
Figure I: Comparison of chain-based and tree-based sampling strategies in LLM multi-turn agent RL. The tree structure brings two major advantages: (i) less rollout budget (both tokens and tool- calls); (ii) higher performance.
INTRODUCTION
Reinforcement Learning (RL) has emerged as a pivotal post-training paradigm for Large Language Models (LLMs), catalyzing the development of several frontier models (DeepSeek-AI Team, 2025; Yang et al., 2025a; OpenAl, 2024). RL-tuned LLMs trained only with outcome rewards acquire complex reasoning abilities and achieve remarkable gains in single-turn tasks, such as mathematical proof and code generation (Team et al., 2025b; Yu et al., 2025; Chu et al., 2025a; Shao et al., 2024; Xin al., 2024; Dai et al., 2026). This suggests that LLMs can learn not only through static imitation, but also by actively interacting with dynamic environments. Guided by this prospect, recent works have extended this RL paradigm to more complex agent settings involving dynamic,
"Wor done during internship AMAP, Alibaba Group
I Project lead.
I "ooresppnniig author.

---

Published as a conference paper at ICLR 2026
bp Takess
T
Camplete Agret Step
idd ipdddy iddd "
Thought
1o0d:
1ood) (bod food
1000 1
Action
ropd ipb9 ( :poá
1000
Olscrvation
SelennSemtence
Agent sup-lese Tree Snarch (Owrs)
Figure 2: Comparison between chain-based and tree-based rollout at different levels. Left: Chain- based rollout. Mid: Tree search with nodes corresponding to tokens/sentence. Right (Ours): Tree search with nodes corresponding to complete agent step.
multi-turn interactions (Feng et al., 2025b; Singh al., 2025; Ji et al., 2026; Qian al., 2025; Feng et al., 2025a). It is believed that such agentic intelligence through long- long-horizon interaction in open-ended environments is essential for next-generation foundation models (Team et al., 2025a).
The agentic RL manifests in two key challenges: i) Heavy budget taken in LLM rollouts. Agent settings require LLMs to interact with the environment over multi-turns and complete tasks through sequential decision-making, which consequently leads to agent trajectories with thousands or more tokens alongside multiple tool-calls (Dong et al., 2025b; Feng et al., 2025b). Existing group-based RL methods sample multiple independent trajectories for each task in a chain based rollout scheme, with considerable redundancy in the sampling process. This reflected in practical agentic RI by the fact that the rollout phase dominates overall training time and tool-calls can incur substantial costs (e.g., high-priced search APIs). äi Sparse supervision in long-horizon, multi-turn trajectories. Although agent trajectories grow with the number of turns, current agent RL approaches are still primarily driven by outcome rewards. Such trajectory-Iever sparse signals make it difficult to iden- tify which specific steps actions in multi-turn, interdependent sequence contributed success or failure. This means that even with a substantial increase in rollout budget, the sampled agent trajectories are still supervised by the same limited amount of training signal, resulting in highly imbalanced learning process and even the training collapse (Wang et al., 2025c;b; Jin et al., 2025b). These two challenges raise a question: Can we construct more fine-grained supervision signals for agent RL under a limited rollout budget while still solely based on outcome rewards?
In this paper, we propose Tree-based Group Relative Policy Optimization (Tree-GRPO) with an online rollout strategy based on tree search. Unlike current RL approaches that independently sam- ple complete trajectory rollouts (Figure 2 left), we replace the chain-based sampling logic with a tree-search process, which yields interleaved trajectories with shared prefix segments. Existing tree- based RL methods (Hou et al., 2025; Li al., 2025f; Wan et al., 2024; Guo et al., 2025; Kazemnejad et al., 2024) often use token/sentence--evee units as tree nodes (Figure 2 mid). For the agent tasks that have a clear step structure, it is natural to treat a complete Thought- as the tree node unit (Figure 2 right). This design with clear contextual segmentation proves more suitable for agent RL (Appendix B.3) and explicitly constrains the rollout budget in both tokens and tool-calls. Under the same budget, our tree-search method obtain around 1.5x samples (de- pending on the tree structure) compared to the chain-based method, which is highly significant for multi-turn agentic RL training where rollout costs substantial.
step
Furthermore, to address the challenge of sparse supervision, we construct more fine-grained process supervision signals by estimating relative advantages based on the tree structure. Specifically, at every branching point of the tree, we back-propagate outcome rewards from the respective subtree leaves. The differences across sibling branches serve as a preference-learning objective, providing process-level supervision signals between subtrees, where the subtree depth determines the granu- larity of the process signal. Since our tree search strategy uses a random expansion, inherently yields process signals of varying granularity, enabling the model to learn intermediate decision mak- ing. This meticulous design leverages the tree structure to transform trajectory-level signals into process-level supervision. Its reliance solely on outcome rewards without additional supervision highlights its scalability and plug-and-plas nature.
In our experiments, we evaluate Tree-GRPO on 11 datasets across single-hop and multi-hop knowledge-intent intensive tasks, along with hard web-agent tasks. Compared to chain-based methods, proposed tree-based method demonstrates consistent improvements across models of varying series and scales. It is noteworthy that Tree-GRPO can successfully enable a base model to adopt a pre-defined multi-turn agent interaction paradigm without any supervised fine-tuning (SFT), despite
2

---

Published as a conference paper at ICLR 2026
operating under extremely limited rollout budget (tokens/tool calls). Based on Qwen2.5-3b. Tree-GRPO achieves superior performance over the chain-based method while using only a quarter of the rollout budget. Our contributions are summarized follows:
We introduce a tree-based rollout strategy with nodes anchored at the agent step level in place of independent chain- based approaches for multi-tum agentic RL.
We propose group-relative advantage estimation in both intra-tree and inter-tree level, incorporat- ing an implicit step-level preference learning objective with relatively stable baseline estimate.
We provide theoretical and empirical evidence that Tree-GRPO outperforms chain-based methods in agentic RL, attaining higher performance under less rollout budgets.
PRELIMINARY
2.1 MULTI-TURN AGENT FRAMEWORK
We adopt the widely used ReAct (Yao et al., 2022) as the agent framework. Unlike static single-tum interaction, the agent engages in multi-turn NonughtAAttonn-Ohservaiiio cycles with the environ- ment to solve given task. Specifically, at each step = 0, 1, ..., 7 1, the LLM generates thought and parsable textual action a based on the existing context st. The action typically corresponds to tool use, through which the agent dynamically interacts with the environment to ob- tain new observations og. A complete T Tsstep agent episode consists of three interleaved trajectories:
H {(TO: 00, on), (TI, (11 (1), 1,,
(1)
Such trajectories grow linearly with the number of steps, and for complex tasks requiring multiple interactions, the full trajectory can reach tens of thousands of tokens.
Following analysis in related work (Wang et al., 2025b), such dynamic process can be described as Markov Decision Process M = (S, A, P), where represents states (the complete interaction context up to given time step ).). A denotes the compound action space (each action comprising a thought-action pair (Te, at)). and P denotes the transition dynamics (includes both the external environment P'nv and the concatenation of the full context over time steps). The complete process can be formulated based on LLM policy model my as:
T-1
Po (SO:T,, To:T, 0O:T, 00:r) = p(so) II
To To(T)ss) Pmm (0+11ar))
(2)
2.2 AGENTIC REINFORCEMENT LEARNING
After formalizing the ReAct-based process as a Markov Decision Process, RL can be directly ap- plied to optimize over the policy space by maximizing the expected return of the full state-action trajectory (Wang et al., 2025b; Dong et al., 2025b; Zhang et al., 2025b):
J(0) = Ex [R (7())-
In practice, optimization is performed with a variance-reduced advantage estimator Á(H), which stabilizes gradient updates (Schulman et al., 2015; DeepSeek-A1 Team, 2025; Zhang et al., 2025a). Most existing agentic RL systems adopt an outcome- based reward, where single scalar reward R(-) determined by predefined rules or model-based scoring functions is delivered to the entire trajectory.
Our method is built upon the group-based RL algorithm (DeepSeck-Al Team, 2025). Unlike esti- mating advantages based on extra value functions like PPO (Schulman et al., 2015), the group-based RL methods estimate advantages Á by sampling group of N candidate rollouts to estimate in- group baseline to guide the optimization direction.
3 TREE-BASED GROUP RELATIVE POLICY OPTIMIZATION (TREE-GRPO)
To achieve a more effective allocation of the rollout budget and address the sparse supervision chal- lenges in multi-turn agentic RI., propose employing tree-search-based sampling. By sharing
3

---

Published as a conference paper at ICLR 2026
Enit
2. Samppp
Quariie: Ane Neadi15 2005, ICLR 2004, CVPLt 3025 alochhhddd be hadd in dhe NA!
Relieal Budact
Finer Sigial
Thought Leeed vorr De lesterrn...
3. Pepand
Action "Saadd Nealls 2023 iccabos...
Node
Ols. SeailPS 2015 will lako phac
Leve- Tree Seurch
Treo M
Polley Model
Tree
Search
Reference Modet
Intral Trow Group
Inter Group
Tosl Envirinment
Apos
Mudel
Face
Figure 3: The overview of the manner, where each node corresponds to complete goough--ction-obeevvee relative advantages are estimated at both intra-tree and inter-tree levels. Tree-GRPO constructs step- level process supervision signals through a tree structure with a less rollout budget.
training pipeline. The rollout is conducted in a tree-search step. The group
partial prefixes between rollouts, tree search method could obtain more rollouts under the same token/tool-call budget. Based on the tree structure, we can further derive step-level process signals purely from outcome rewards, introducing an implicit step-level preference learning target into on- line RI.. Figure presents overview of proposed Tree-GRPP. In the following section, will detail the implementation of agent tree search ($ 3.1), ), the construction of tree-structured group relative advantages ($ 3.2), and the analysis of step-level process signals 3.3).
3.1 TREE SEARCH FOR AGENT ROLLOUT
Tree-search methods such as Monte Carlo Tree Search (MCTS) have proven effective for construct- ing offline DPO datasets (Xie et al., 2024; Lai al., 2024) and for test-time scaling (Yao al., 2023; Xin et al., 2025a), yet they are seldom used in online RL. training. The main obstacle is its reliance on multi-turn sequential rollouts, which are poorly suited for parallelized LLM inference engines. This mismatch bottlenecks rollout throughput and severely limits online RL efficiency.
To address this, we adopt an initialize-then-eee -ee-e- approach, in which multiple chains are first initialized in parallel and nodes are then iteratively sampled for expansion. Furthermore, the clear structured agent step-level process allows us to replace the token-level nodes with agent step-level nodes, meaning that each node in the tree represents corresponding (T, tuple. More formally, the overall tree-search sampling process is as follows:
1. Initialization. For each prompt x;, we first generate M independent chain-based trajectories Y = {HL ~ Te {-Ic:)) by policy model Ta as the initialization for M trees T.
2. Sampling. Then we randomly sample N nodes P; {pi. Ti except the leaf node (agent answer) from each tree T, for expansion.
3. Expansion. For each selected node Pt,j. we take the entire context from the root to that node
H's, = (pigi ..... falher } and the original prompt F, as the input, continue generating the remaining part of the response by Ynew = (H's ~ Te(-12, HV then insert it into the source tree as new branch by T, < T, U Vnew.
By iteratively repeating steps 2 and 3 L times, this tree search process results in a total of M X (Lx N + 1) rollouts as final group size for a single prompt. These rollouts are evenly distributed across the M trees. Let the expectation rollout budget (both in tokens and tool-calls) of a single agent trajectory be B. For each single random tree expansion, the expected depth of the selected node is half of the maximum depth, and the corresponding expected cost is B 7. This means we can obtain a larger number of agent rollouts for training using tree search under the same token/tool-call budget. Specifically, the total expected budget for tree-search sampling is determined by:
(4) Under a fixed sampling budget, decreasing tree number M while increasing expansion number N, L can raise the number of rollouts, but it also narrows the exploration scope, as more trajectories share the same prefix. In experiments, different tree configurations exhibit varying effects.
E Bueell = M B L N B/2.
4

---

Published as a conference paper at ICLR 2026
3.2 TREE-BAN BASED GROUP RELATIVE ADVANTAGES
Beyond enabling more rollouts under the fixed budget, more significant potential advantage of tree search lies in the process supervision signals naturally embedded within the tree structure.
Given a group of complete trajectory rollouts {?() based on each prompt, a naive way to apply group-based policy optimization for agent RL is to organize the rollouts into trajectory-level groups. For each rollout, the reward R(-)) is only computed at the outcome, and thus the advantage estimation also the trajectory level. This means that the entire multi-turn agent trajectory including multi- steps is assigned an identical credit as:
(HH) A([(To, 0o, 9o): (Tr, or, (r))) A((70- oo: on}) =.. A((TT, or, oT))- (5)
Due to the coarse credit assignment, such sparse rewards severely affect the stability of RL training for Long-horizon multi-turn agents.
Tree-based credit. Unlike independent chain-based rollouts, tree-structured rollouts with shared prefixes naturally embed process credit signals. As shown in Figure 4, every branching point of the tree, the difference between the back-propagated outcome rewards from respective leaves naturally constitutes a preference-learning objective for the different sub- trees. Such a form of preference learning results in process signals of varying granularity modulated by subtree depth. To achieve this form of tree-based credit assignment, perform grouped advantage estimation within each tree Gintra-tree(11 (T:), serving as:
Al +.
Stgnal
Trajectary Sigual
At
Proces Signal
Preforence
44
AL
Chais-haed
Tree-bused
Figure 4:
Comparison between chain-
based and tree- based rollouts.
Amtra/Inter-rrre (H(' [R()') mean (R(H))) Chmnotancm s/td(( ( Cuerstrocmeee (T)))
(6)
Although the intra-tree group relative advantage incorporates explicit preference objectives, the lim- ited number of rollouts within each tree may lead to unreliable baseline estimation. To better stabi- lize the RL training, also group rollouts across inter-trees (rollouts from all trees) and combine the intra-tree and inter-tree group relative advantages to obtain the final advantage estimate as:
Ane') Atatm-ree (H') + Ammer.tree (H').
The final tree-based group relative policy optimization object is:
G min (mce
JTee-GRPOO (0)
anD 74 gunc
(8)
(ip(r,.(0),11e,))) Auee 3DKL (Te(Hl(2)) ) Tie (H(z))
where Wef and Vold represent the reference LLM and previous LLM, and Dxr. denotes the KL di- vergence. The importance sampling ratio ro.(() is defined the token level t. The complete Tree-GRPO workflow is Algorithm 1.
3.3 IMPLICIT STEP-LEVEL PREFERENCE LEARNING
Leaving aside cost and scalability, a potential way to address the granularity of sparse supervision is to explicitly construct step-level DPO data with positive and negative pairs, thereby enabling preference optimization at each step. In this section, to better understand Tree-GRPO agentic RL, establish that intra-tree GRPO admits the same gradient structure step-level DPO, with the only difference at the weight term.
Assumption 3.1 (Binary Preference Setting) For each intermediate tree node (x, He)), the sub- sequent trajectory in terms of reward falls into two categories, denoted as Hisn and Hloes with associated rewards [1,0). The trajectory probabilities defined as
Po (Holl)) = 1 -po(7doos =
II
na (H (r, Her))
5

---

Published as a conference paper at ICLR 2026
Under this assumption, the step-level DPO objective be expressed as optimizing the Bradley- Terry likelihood between the winning and losing outcomes by:
V stostcp-DPO(O) (e Hog
(3 (3 log pe (H2 :log pe (H
(10)
Voglogpo (H Ve log pe (M
Correspondingly, the gradient of intra-tree GRPO can be derived into combined form consisting of Hain and H. losss as:
V JiJint tree (0) Po (H2))) pa (H Vo log (H2)) V log Po (H2
(11)
Proposition 3.1 (Structural Equivalence of Step-level DPO and Intra-tree GRPO) Under As-
sumption C.I, both step-level DPO and intra-tree GRPO admit gradient estimators of the form
V Junifien(() (0)
Vologge po (H2)) Vologro po (HL
(12)
Preference Advantage Gradient where the only difference lies in the choice of the weight term w.
Weight
Proposition C.1 indicates that intra-tree GRPO can be interpreted as implicitly performing step-level preference optimization, thereby inheriting the key property of step-level DPO while operating in an online rollout setting. Detailed derivations are put in Appendix C.
4 EXPERIMENT
4.1 EXPERIMENTAL SETUP
Datasets. To evaluate the effectiveness of our proposed Tree-GRPO in LLM agentic RL, we con- duct experiments on 11 benchmarks across three categories: (i) Multi-Hop QA including: Hot-
potQA (Yang et al., 2018), 2WikiMultiHopQA (Ho et al., 2020), Musique (Trivedi et al., 2022), and Bamboogle (Press et al., 2023); (ii) Single-Hop QA including: NQ (Kwiatkowski et al., 2019), TriviaQA (Joshi et al., 2017), and PopQA (Mallen et al., 2023); (iii) Web-Agent QA including: Sim- pleQA (Press et al., 2023), GAIA (Mialon et al., 2023), WebWalkerQA (Wu et al., 2025b), and BrowseComp (Wei et al., 2025).
Baselines. We compare the proposed Tree-GRPO against the following baseline: (i) Direct Prompt- ing Methods including direct inference, ReAct agent framework (Yao et al., 2022); (ii) Advanced RAG Method Search-ol (Li et al., 2025c); (iii) RL-based Methods including GRPO (DeepSeek-Al Team, 2025) and GSPO (Zheng et al., 2025). Our implementation is built upon the Search-R1 (Jin al., 2025b) repository, including prompt template and agent-environment interaction.
Experimental Setups. For all settings, we exclusively use search engines as the designated tool. For Multi-Hop QA and Single-Hop QA settings, et al., 2022) built on a Wikipedia dump (Karpukhin et al., 2020), while the Web-Agent QA setting employs a real web search API for retrieval.
E5-based local retrieval server (Wang
Metrics. Exact Match (EM) is used for both the training and test score in Single-Hop QA and Multi Multi-Hop QA. For Web-Agent QA, we utilize Fl scores for both training and test.
We conduct experiments using two series of models Qwen- 2.5 (Base/Instruct) (Qwen et al., 2024) and 3.a (Base/Instruct) (Grattafiori et al., 2024) across differrnt parameter scales including 1.5b, 3b, 7b, and 14b. If not specified, the default rollout budget is 4 for each prompt during training. More implementation and experiment details are in Appendix A and B.
4.2 MAIN RESULTS
Multi-Hop QA. As shown in Table 1, in multi-hop QA setting that requires multi-tum interactions, although models within the ReAct framework can acquire information via tool calls, small models (<7b parameters) exhibit little improvement direct inference. This indicates that prompting

---

Published as a conference paper at ICLR 2026
Table Overall performance on single-hop QA and multi-hop QA, with EM scores for each dataset. The best results are indicated in bold.
Single-Hop QA
Multi-Hop QA
Method
NQ
Trivia
PopQA
Avg./A
Hotpot
2wiki
Musiq
Bamb
Avg./a
Direct Inference
7.1
22.4
9.9
13.1
5.9
4.3
2.6
8.0
5.2
Qwen2.5511.5
Scarch-ol
10.2
30.9
15.0
15.4
11.6
12.2
3.1
13.0
10.0
ReAct
9.5
22.1
13.8
15.1
7.3
8.0
1.9
11.2
7.1
GRPO
39.4
51.0
39.7
43.4 Aare
14.6
24.4
2.2
4.0
11.3 Anees
GSPO
36.8
48.9
37.3
41.0-5.8m
15.8
23.7
2.5
4.8
11.7
Tree-Gree GReo-GRO
43.6
57.3
41.6
47.5
29.5
26.8
13.6
19.1-60%
Direct Inference
10.6
28.8
10.8
16.7
14.9
24.4
2.0
2.4
10.9
Qwen2.5-31
Search-o1
15.1
44.3
13.1
24.2
18.7
17.6
5.8
29.6
17.9
ReAct
21.1
43.5
28.3
31.0
19.2
19.1
4.8
20.0
15.8
GRPO
44.4
58.0
42.0
48.1 Aeuse
39.0
36.3
15.2
36.8
31.8 Aouse
GSPO
43.0
58.8
42.5
48.1 4..0%
40.2
17.0
36.8
3 66.2%
FRee-GRPO
46.8
59.7
43.6
50.0 44.0%
42.4
43.7
17.8
43.2
36.8 100
Direct Inference
16.2
29.6
7.4
17.7
12.6
9.2
2.0
8.0
8.0
Llama3.2-33
Search-ol
24.2
48.4
8.8
27.1
19.4
17.4
32.0
14.1
ReAct
23.9
21.7
29.3
16.2
10.4
23.2
GRPO
45.5
58.2
42.4
48.7 Abssc
36.0
26.9
11.8
32.0
26.7 Abrec
GSPO
41.2
57.8
40.8
46.6-4.5%
28.1
24.5
8.6
32.0
23.3 23.3-13%
Tree-GRPO
47.7
59.9
42.3
50.0
2.7%
44.6
38.4
17.6
46.4
36.8 3816
Direct Inference
13.4
40.8
14.0
22.7
18.3
25.0
3.1
12.0
14.6
Qwen2.5-7b
Search-ol
23.8
47.2
26.2
32.4
22.1
21.8
5.4
32.0
20.3
ReAct
30.6
56.3
34.6
40.5
27.9
25.3
11.3
28.8
23.3
GRPO
45.8
61.5
44.3
50.5 Ansic
42.5
40.7
19.1
43.2
36.4
Abrec
GSPO
47.0
64.5
46.1
52.5 4.0%
40.0
38.2
19.2
44.0
35.4
Tree-GRPO
48.1
63.3
45.2
52.2+3.4%
44.6
42.3
20.2
44.0
37.8+3.0%%
Qwen2.5-144 14b
Direct Inference
19.8
53.1
18.4
30.4
21.7
25.3
4.5
16.0
16.9
Search-ol
34.7
63.5
24.1
40.8
26.8
16.1
9.9
41.6
23.6
ReAct
36.1
64.2
39.3
46.5
39.1
33.8
15.0
43.2
32.8
GRPO
51.3
67.2
46.7
55.1 Aeee
47.7
42.6
23.2
53.6
41.8 Anss
GSPO
50.7
47.1
55.1 4.0.0%
50.1
52.8
44.245.7%
Tree- GRPO
51.7
68.1
47.3
55.7
11.1%
50.2
50.5
25.9
54.4
45.3 (8.47%
alone is insufficient for models to complete long-horizon agent tasks. Among RI. approaches, our Tree-GRPO method achieves a substantial margin over chain-based GRPO baseline on models be- low 3b, yielding relative improvements ranging from 16% to 69% across both the Llama and Qwen series models. Remarkably, Tree-GRPO remains effective on Qwen2.5-1.55 whereas chain-based methods struggle to stimulate multi multi-turn tool-use behavior. Although RL offers limited benefits Qwen2.5-14b, our tree-based method still achieves an average relative improvement of 8.4%. These results demonstrate the superiority of the process signal provided by the tree-based method.
Single-Hop QA. In the single-hop QA setting which requires fewer interaction turns, the 14b model already exhibits agentic capabilities complete tasks under the ReAct framework Table 1. Com- pared to chain-based RL methods, Tree-GRPO still shows stable improvements, especially for small models like Qwen2.5-1.5b and Qwen2.5-3b. However, for most single-hop questions, the agent does not require multi-turn ReAct-style interactions and can usually solve the problem with just one round of retrieval followed by one round of answering. Due the tree depth in this setting being limited (typically 2), the gains from process-level signals over trajectory- are also limited.
Web-Agent QA. Existing open- open-source web-agent QA benchmarks are predominantly test sets, with notable lack of training sets. Moreover, most of these test benchmarks are highly challenging, with some tasks requiring dozens web interactions. The limited training data we were able to collect fails to match this level of difficulty and quality. Consequently, the performance improvement from RL relatively limited, as shown in Table 2. In this case, Tree-GRPO consistently outperforms the chain-based GRPO across four test datasets, most notably GALA with 28% average improve- ment. However, on more challenging benchmarks such as BrowseComp, RL yields only marginal gains, which is primarily constrained by the training data.

---

Published as a conference paper at ICLR 2026
Table 2: Overall performance on web-agent QA, with Fl scores for each dataset. The best results are indicated in bold.
SimpleQA
General AI Assistant
WebWalkerQA
BrowseComp
Method
Avg.
Lv.1
Lv.2
Lv.3
Avg.
Easy
Med.
Hard
Avg.
Avg.
Direet
Qwen2.55 5-h Instruct
7.7
8.8
7.7
3.0
7.6
6.2
9.4
5.8
7.4
2.2
DeepSeck-R RI---stiDDis I-Distill-32b
12.6
19.2
7.8
4.1
11.7
13.3
9.4
11.0
2.4
Qwen22 Quen2.
ReAct
25.1
6.2
3.5
1.1
4.2
9.2
5.6
7.6
1.3
GRPO
61.5
17.7
14.9
4.5
14.7
11.4
11.6
10.9
2.3
Tree- GRPO
62.4
19.3
17.5
5.7
16.8
9.3
11.8
11.9
11.2
2.7
ReAct
43.3
11.4
7.1
0.9
8.0
9.5
11.3
7.4
9.5
1.2
+ GRPO
65.4
21.6
15.0
5.5
16.4
11.4
10.3
12,4
2.4
Tree-GiRP)
67.8
20.8
24.3
7.3
21.0
11.1
15.5
10.8
12.8
2.6
Table 3: Performance with different training budget (defined as the cost of several complete agent trajectories per prompt). The base model is Qwen2.5-3b. The best results are indicated in bold.
Single-Hop QA
Multi-Hop QA
Method
NQ
Trivia
PopQA
Avg
Hotpot
2wiki
Musiq
Bamb
Avg.l
Rollout Token/Tool Budget = 2/per prompt
Chain-based
42.0
56.7
40.8
46.5 Aawe
17.9
25.6
3.3
12.8
14.9 Aner
Tree-based (M 1, = 2,
46.1
59.4
43.6
46.7.6.%
39.5
40.2
13.7
32.8
31.6-1199
Rollout Token/Tool Budget = 4/per prompt
Chain-based
44.4
58.0
42.0
48.1 Arse
39.0
36.3
15.2
36.8
31.8 Abee
Tree-based (M N, = 2,
46.8
59.7
43.6
400k
42.4
43.7
17.8
43.2
36.8-169
Rollout Token/Tool Budget ts 8/per prompt
Chuin-based
46.5
59.2
44.3
50.0
Arse
39.4
36.4
16.1
33.6
31.4 Anse
Tree-based (M N 2-2
47.6
60.8
50.8
1.0%
42.0
42,9
19.5
36,0
35.1
Tree-based (M N,N =
46.9
59.7
44.5
50.4
42.2
42.6
18.3
42.4
36.4-199
Rollout Token/Tool Budget 16/per prompt
Chain-based
$1.2 Dane
40.1
38.8
17.5
39.2
33.9 Ane
Tree-based (M 8,N 2, L-
48.6
61.7
44.9
51.7
44.6
43.2
18.2
38.4
3
Tree-based (M N = =3,4 13,4=
48.5
61.6
45.0
51.7.L.0
45.3
44.1
18.8
37.6
36.5
Trec-based (M = N,N = 5,
48.4
61.3
43.8
51.2-0.0%
45.0
43.9
18.5
41.6
37%
4.3 QUANTITATIVE ANALYSIS
In this section, we extend our study to more training configurations and analyze what the tree-based method affords beyond performance.
Different Training Budget. LLM agent RL training, the token/tool-call costs introduced by multi-turn interactions an important concern. Here we assess our method under different cost constraints. As shown in Table 3. the tree-based method consistently demonstrates improvements under different budget settings. Especially under highly constrained rollout budgets (e.g., when only two complete rollouts budget per prompt), chain-based RL. struggles to learn multi-turn interactions, whereas the tree-based method achieves substantially better results (112% relative improvement). As the rollout budget increases, the superiority of the tree-based method having more training tra- jectories gradually diminishes in the single-hop setting, whereas the benefit of finer process super- vision signals remains in the multi-hop setting. Remarkably, our Tree-GRPO achieves superior performance over the chain-based method while using only quarter of the rollout budget. In ad- dition, when the rollout budget is larger, tree-based sampling offers more flexibility in parameter choices. More analysis is in Appendix B.4.
Chain-based vs. Tree-based Beyond Performance. Due to the sparse nature of outcome rewards in multi-turn agentic RL, the model often struggles to learn more complex processes, tending in- stead to favor shorter interaction paths rather than extended exploration, and in some cases even learning toward unreasonable shortcuts. While such behavior is generally acceptable, it becomes a limitation for agent tasks that inherently require longer multi-turn interactions. In experiments on the multi-hop QA setting in Figure 5, we find that beyond performance improvements in training reward, the tree-based method also encourages the L.M agent to engage in longer interactions (i.e.,
8

---

Published as a conference paper at ICLR 2026
Owen22 2-30 Trweband
Owest 2:36 Chamsteee Rt.
lareh.b-b-i beard
Llasal 2o0--t Charsteard SL.
0.90
0.50
0.04
50100
0.30
0.10
230
376
150
120
Comparison Qwen2.5-3b
(b) Comparison Llama3 2-ama..2-3b-i
Figure 5: Comparison between tree-based and chain- based RL on reward and action number.
Owee22 2iw Tree bused RL
Owee2 3.23.-bbee Now Chan
Elamad bob-a Treebssedd Ri
BS Uo Daite-oane RC.
38.0
37.5
37.5
35.0
35.0
35.0
Teak Scases
30.0
12.
122
23.0
34.0
12.00
22.5
27.5
03.0
22.5
22.5
Wamnuu Ratia
21.0
Careiicina
21.0
0.5
0.5
10
20.0
5.00
5,5
(a) Ablation on Qwen2.5-3b
(b) Ablation on Llama3.2-3b-it
Figure 6: Ablation study on learning rate warmup ratio and KL term coefficient.
making more tool calls) from 2.4 to 3.0 average to solve each multi-hop QA. This is particularly meaningful for training agents capable of solving more complex long-horizon tasks. Moreover, we observe that the learning rate (LR) warmup is particularly sensitive hyperparameter when training small models below 3b. The results in Figure show that our tree-based method outperforms the conduct ablation study
chain-based method under all LR warmup ratio settings. In addition, on the coefficient of the KL. term, which is often crucial in LLM RL. The results also highlight that the tree-based method maintains stability across different settings, and that an appropriately weighted KL term can help the model learn better within a constrained exploration space.
Tree-based Advantage. In Table methods. When the rollout budget is relatively limited (e.g.. M = 2, N = 2. L = 1), the number of branches within a single tree small. This scarcity of intra-tree grouped responses results in high-variance Amtr-tre and unstable baseline estimation, making RL training highly prone to col- lapse. This issue is absent when the intra-tree branch count is sufficient (e.g.. N 6). Leveraging the symmetric step-level preference learning property of A the Ammestree act fallback baseline estimator when intra-tree branching is insufficient. In our experiments, combining Amara-tre and Amser tree yields more stable and improved training performance across various NML settings. We argue that this approach enables agent RL to incorporate the step-level preference learning prop- erty while preserving greater stability. It is worth noting that due to the more efficient sampling of tree search under the same budget, when using vanilla global group relative ad estimation (e.g., Am the tree- besd results are still better than the chain- based GRPO.
compare the performance of different advantage estimation
5 RELATED WORK
Reinforcement Learning for Sparse Rewards. Existing sparse-reward RL methods can gener- ally be divided into three categories. (i) Exploration-oriented methods mitigate sparse rewards by encouraging the model to visit potentially rewarding states via curiosity (Pathak et al., 2017), goal- conditioned replay (Andrychowicz al., 2017), etc. Due to the strong prior knowledge from base LLM models and the highly structured agent action space, exploration is not primary bottleneck in current LLM agent RL. (ii) Reward-shaping methods (Ng et al., 1999; Arjona-Media 2019) provide additional intermediate supervision signals by decomposing or predicting process feedback. Recent studies in LLM RL primarily utilize Process Reward Models (PRMs) to generate step- loken-level feedback. However, due to the high cost of step-level human annotations and the challenges in training PRMs, such approaches have yet to scale to general scenarios. (iii) Credit assignment methods (Hung al., 2019) redistribute outcome rewards to earlier steps through heuris-
et al.,

---

Published as a conference paper at ICLR 2026
Table 4: Ablation study on tree-based advantages.
Advantage
Hotpot
2Wiki
Musiq
Bamb
Avg.
%
Rollout Token/Tool Budget x 4lper prompt
Chain-based
39.0
36.3
15.2
36.8
31.8
Atuse
Amtrssrre (MV = 2, 2, 1) Aunesteee (M- N. 2, 1) Amurauee Amaesuce (M = 2, = 1)
collapse
collapse
collapse
collapse
collapse 33.8
40.6
41.3
16.5
+6.3%
42.4
43.7
17.8
43.2
36.8
+16%
Rollout Token/ Token/Tool Budget x Siper prompt
Chain-based
39.4
36.4
16.1
33.6
31.4
Atuse
Amuaace (M = N. =) Amersues (M = N 1)
40.9
39.7
17.8
40.0
34.6
+10%
41.1
40.3
17.9
34.4
33.4
+6,4%
Amnrsere Ammrnee (M- 2,N 22N=660 1)
42.2
42.6
18.3
42.4
36.4
+16%
tie mechanisms. representative line of work focuses on improving credit assignment by utilizing heuristic structures (Wang et al., 2024) or sampling-base (Kazemnejad et al., 2024) techniques.
Reinforcement Learning for LLM and Agent. Recent advances in RL (Kaufmann et al., 2023; Lambert et al., 2024) have demonstrated the effectiveness in LLM alignment and reasoning. Al- though process reward models have been shown to provide more gains on complex reasoning tasks (Lightman al., 2023; Shao et al., 2024; Zhang et al., 2025e; Wang et al., 2025c; Liu et al., 2025; Cui et al., 2025; Choudhury, 2025; Setlur et al., 2024; Li et al., 2025b), most existing works still rely solely on outcome rewards for training due to the additional costs and limited scalability of PRMs. Techniques ranging from PPO (Schulman et al., 2015), GRPO (DeepSeek-Al Team, 2025), GSPO (Zheng al., 2025), along with more policy variants such as DAPO (Yu et al., 2025) and GPG (Chu et al., 2025b) are employed for LLM RL training. Recent works (Wang et al., 2025b; Feng et al., 2025b; Dong et al., 2025b; Xue al., 2025; Wang et al., 2025c; Zhou al., 2025; Wang et al.. 2025a; Li et al., 2025e: Sun et al., 2025; Dong et al.. 2025a; Li et al., 2025d) apply this paradigm to end-to-end agent training. In addition these online RL approaches, another line of work (Wang et al., 2025c; Xie et al., 2024; Xiong et al., 2025; Lai et al., 2024) directly con- structs step-level DPO training data an offline manner to achieve more fine-grained optimization objectives, while increasing the complexity of the training pipeline.
Tree Search for LLM Reasoning. One line of LLM tree-search research focuses on test-time scaling. Yao et al. (2023); Long (2023); Snell et al. (2024); Koh et al. (2024); Zhou et al. (2024) propose tree-of-thought to allow LLMs to consider multiple reasoning paths during solving complex tasks. Xin et al. (2024; 2025a;b) employs the Monte-Carie Carlo tree search strategy to generate diverse proof paths for theorem proving problems. Another line of research (He et al., 2024; Wan et al., 2024; Wu et al., 2024; Xie al., 2024; Zhang al., 2025c; Lai et al., 2024; He et al., 2024; Li et al., 2025a) is to utilize tree-search structures for constructing step-level preference learning data, which are then used in DPO or SFT. There are also some works (Hou et al., 2025; Zhang et al., 2024; Yang et al., 2025b) similar to ours that employ tree search for sampling in LLM online RL. In particular, VinePPO (Kazemnejad et al., 2024) uses Monte Carlo estimation instead of the critic model in PPO to obtain accurate value estimates. SPO (Guo et al., 2025) partitions the trajectory into segments and performs advantage estimation through tree-based segments, thereby enabling finer segment-level credit assignment. However, since these tree-related methods are still conducted at the token/sentence level and cannot be directly employed on agent tasks.
CONCLUSION
In this work, we propose Tree-based Group Relative Policy Optimization (Tree-GRie GRPO), adopting a tree-search rollout strategy in place of independent chain-based rollouts for LLM agent RL. Based on agent step-level nodes, Tree-GRPO carries out rollout sampling over a semantically well-defined search tree. By sharing common prefixes, the tree search sampling significantly reduces the roll- out budget in terms of both tokens and tool calls during training. Tree-GRe GRPO leverages the tree structure to conduct tree-base grouping for advantage estimation, introducing an implicit step-level pifeerence-learming objective. Empirical evaluations on datasets demonstrate the superiority of tree-based approach for agentic RI.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abheel, and Wojeiech Zaremba. Hindsight experience play. Advances in neural information processing systems, 30, 2017.
Jose A
Michael Gillhofer, Michael Widrich, Thomas Unterthiner, Johannes Brand- stetter, and Sepp Hochreiter. Rudder: Return decomposition for delayed rewards. Advances in Neural Information Processing Systems, 32, 2019.
Sanjiban Choudhury. Process reward models for Ilm agents: Practical framework and directions. arXiv preprint arXiv:2502.10325, 2025.
Tianzhe Chu, Yuexiang Zhai, Jihan Yang, Shengbang Tong, Saining Xie, Dale Schuurmans, Quoc V Le, Sergey Levine, and Yi Ma. Sft memorizes, r1 generalizes: A comparative study of foundation model post-training. arXiv preprint wwxXv:2501.171000 2025a.
Xiangxiang Chu, Hailang Huang, Xiao Zhang, Fei Wei, and Yong Wang. Gpg: A simple and strong reinforcement learning baseline for model reasoning. arXiv preprint arXiv:2504.02546. 2025b.
Ganqu Cui, Lifan Yuan, Zefan Wang, Hanbin Wang, Yuchen Zhang, Jiacheng Chen, Wendi Li, Bingxiang He, Yuchen Fan, Tianyu Yu, et al. Process reinforcement through implicit rewards. arXiv preprint arXiv:2502.01456, 2025.
Yanqi Dai, Yuxiang Ji, Xiao Zhang, Yong Wang, Xiangxiang Chu, and Zhiwu Lu. Harder is better: Boosting mathematical reasoning via difficulty-aware grpo and multi-aspect question reformula- tion. arXiv preprint 4rXiv:2601.20614, 2026.
DeepSeek-AI Team. Deepseek-rl: Incentivizing reasoning capability in Ilms via reinforcement learning. arXiv preprint arXiv:2501. /2948, 2025.
Guanting Dong, Licheng Bao, Zhongyuan Wang. Kangzhi Zhao, Xiaoxi Li. Jiajie Jin, Jinghan Yang, Hangyu Mao, Fuzheng Zhang, Kun Gai, et al. Agentic entropy-balann balanced policy optimization. arXiv preprint arXiv:25 10. 14545, 2025a.
Guanting Dong, Hangyu Mao, Kai Ma, Licheng Bao, Yifei Chen, Zhongyuan Wang, Zhongxia Chen, Jiazhen Du, Huiyang Wang. Fuzheng Zhang, al. Agentic reinforced policy optimization. arXiv preprint arXiv:2507.1995 2025b.
Jiazhan Feng, Shijue Huang, Xingwei Qu, Ge Zhang, Yujia Qin, Baoquan Zhong, Chengquan Jiang, Jinxin Chi, and Wanjun Zhong. Retool: Reinforcement learning for strategic tool use in llms. arXiv preprint arXiv:2504.1 1536, 2025a.
Lang Feng, Zhenghai Xue, Tingcong Liu, and Bo An. Group-in-gren group policy optimization for Ilm agent training. arXiv preprint arXiv:2505. 10978, 2025b.
Jiaxuan Gao, Wei Fu, Minyang Xie, Shusheng Xu, Chuyi He, Zhiyu Mei, Banghua Zhu, and Yi Wu. Beyond ten turns: Unlocking long-horizon agentic search with large-scale asynchronous rl. arXiv preprint Stt.:::50000977777 2025.
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The Ilama 3 herd of models. arXiv preprint arXiv:2407.2178. 2024.
Yiran Guo, Lijie Xu, Jie Liu, Dan Ye, and Shuang Qiu. Segment policy optimization: Ef- fective segment-level credit assignment in for large language models. arXiv preprint arXiv:2505.23564 2025.
Mingqian He, Yongliang Shen, Wenqi Zhang, Zeqi Tan, and Weiming Lu. Advancing process verification for large language models via tree-based preference learning. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp. (099, 2024.
Xanh Ho, Anh-Khoa Duong Nguyen, Saku Sugawara, and Akiko Aizawa. Constructing multi-hop qa dataset for comprehensive evaluation of reasoning steps. In Proceedings of the 28th Interna- fional Conference on Computational Linguistics, pp. 6609-6625, 2020.

---

Published as a conference paper at ICLR 2026
Zhenyu Hou, Ziniu Hu, Yujiang Li, Rui Lu, Jie Tang, and Yuxiao Dong. Treerl: Lim reinforcement learning with on-policy tree search. arXiv preprint arXiv:2506. 11002, 2025.
Chia-Chun Hung, Timothy Lillicrap, Josh Abramson, Yan Wu, Mehdi Mirza, Federico Carnevale, Arun Ahuja, and Greg Wayne. Optimizing agent behavior over long time scales by transporting value. Nature communications, 10(1):5223, 2019.
Yuxiang Ji, Yong Wang, Ziyu Ma, Yiming Hu, Hailang Huang, Xuecai Hu, Guanhua Chen, Liaoni Wu, and Xiangxiang Chu. Thinking with map: Reinforced parallel map-augmented agent for geolocalization. arXiv preprint 2xXi:2600.004322. 2026.
Bowen Jin, Jinsung Yoon, Priyanka Kargupta, Sercan O Arik, and Jiawei Han. An empirical study on reinforcement learning for sessoning-search interleaved Ilm agents. arXiv preprint arXiv:2505.15117, 2025a.
Bowen Jin, Hansi Zeng. Zhenrui Yue, Jinsung Yoon, Sercan Arik, Dong Wang, Hamed Zamani, and Jiawei Han. Search-rl: Training Ilms to reason and leverage search engines with reinforcement learning. arXiv preprint arXiv:2503.05116 2025b.
Mandar Joshi, Eunsol Choi, Daniel S Weld, and Luke Zettlemoyer. Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension. In Proceedings the 55th Annual Meet- ing of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1601-1611, 2017.
Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 6769-6781, 2020.
Timo Kaufmann, Paul Weng, Viktor Bengs, and Eyke Hüllermeier. A survey of reinforcement learning from human feedback. arXiv preprint arXiv:2312.14925 2023.
Amirhossein Kazemnejad, Milad Aghajohari, Eva Portelance, Alessandro Sordoni, Siva Reddy, Aaron Courville, and Nicolas Le Roux. Vineppo: Refining credit assignment in rl training of Ilms. arXiv preprint drXiv:2410.01679, 2024.
Jing Yu Koh, Stephen McAleer, Daniel Fried, and Ruslan Salakhutdinov. Tree search for language model agents, arXiv preprint arXiv:2407.01476, 2024.
Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, et al. Natural questions: A benchmark for question answering research. Transactions of the Association for Computational Lingnistics, 7:452-466, 2019.
Xin Lai, Zhuotao Tian, Yukang Chen, Senqiao Yang, Xiangru Peng. and Jiaya Jia. Step-dpo: Step- wise preference optimization for long-chain reasoning of 1lm.. arxiv preprint Xix::4446111629 2024.
Nathan Lambert, Jacob Morrison, Valentina Pyatkin, Shengyi Huang, Hamish Ivison, Faeze Brah- man, Lester James V Miranda, Alisa Liu, Nouha Dziri, Shane Lyu, et al. Tulu 3: Pushing frontiers in open language model post-training arXiv preprint arXiv:241 1...2241..1124... 2024.
Pengxiang Li, Zhi Gao, Bofei Zhang, Yapeng Mi, Xiaojian Ma, Chenrui Shi, Tao Yuan, Yuwei Wu, Yunde Jia, Song-Chun Zhu, et al. Iterative tool usage exploration for multimodal agents via step-wise preference tuning. arXiv preprint arXiv:2504.215611 2025a.
Renda Li, Hailang Huang, Fei Wei, Feng Xiong, Yong Wang, and Xiangxiang Chu. Adacurl: Adap- tive curriculum reinforcement learning with invalid sample mitigation and historical revisiting. arXiv preprint arXiv: 194478, 2025b.
Xiaoxi Li, Guanting Dong, Jiajie Jin, Yuyao Zhang, Yujia Zhou, Yutao Zhu, Peitian Zhang, and Zhicheng Dou. Search-ol: Agentic search-enhanced large reasoning models. arXiv preprint 2:Xi::5511.05366, 2025c.
12

---

Published as a conference paper at ICLR 2026
Xiaoxi Li, Jiajie Jin, Guanting Dong, Hongjin Qian, Yutao Zhu, Yongkang Wu, Ji-Rong Wen, and Zhicheng Dou. WebThinker: Empowering Large Reasoning Models with Deep Research Ca- pability, April 2025d. URL httt:::/aaxivv.rg//aaa/ 21777 arXiv:2504.21776 [es].
Xuefeng Li, Haoyang Zou, and Pengfei Liu. arXiv:2503.23383, 2025e.
Torl: Scaling tool-integrated rl. arXiv preprint
Yizhi Li, Qingshui Gu, Zhoufutu Wen, Ziniu Li, Tianshun Xing, Shuyue Guo, Tianyu Zheng, Xin Zhou, Xingwei Qu, Wangchunshu Zhou, et al. Treepo: Bridging the gap of policy optimiza- tion and efficacy and inference efficiency with heuristic tree-based modeling. arXiv preprint arXiv:2508. 17445, 2025f.
Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. arXiv preprint 0rXiv:2305.20055 2023.
Xiaoqian Liu, Ke Wang, Yuchuan Wu, Fei Huang, Yongbin Li, Junge Zhang, and Jianbin Jiao. On- line process reward leanring for agentic reinforcement learning. arXiv preprint arXiv:2509 19199, 2025.
Jieyi Long. Large language model guided tree-of-thought. arXiv preprint arXiv:2305.0820) 2023.
Alex Mallen, Akari Asai, Victor Zhong, Rajarshi Das, Daniel Khashabi, and Hannanch Hajishirzi. When not trust language models: Investigating effectiveness of parametric and non-parametric memories. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 9802-9822, 2023.
Grégoire Mialon, Clémentine Fourrier, Craig Swift, Thomas Wolf, Yann LeCun, and Thomas Scialom. Gaia: a benchmark for general ai assistants. arXiv preprint arXiv:2311.12983, 2023.
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In International conference on machine learning, volume 99, pp. 278 287. Citeseer, 1999.
OpenAl. Openai ol system card. arXiv preprint arXiv:2412.16722 2024.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International conference on machine learning, pp. 2778-2787. PMLR, 2017.
Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A Smith, and Mike Lewis. Mcasuring and narrowing the compositionality gap in language models. In Findings of the Association for Computational Linguisties: EMNLP 2023, pp. 5687-5711, 2023.
Cheng Qian, Emre Can Acikgoz, Qi He, Hongru Wang, Xiusi Chen, Dilek Hakkani-Tin Gokhan Tur, and Heng Ji. Toolrl: Reward all tool learning needs. arXiv preprint arXiv:2504.13955 2025.
Qwen, An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jingren Zhou, Junyang Lin, Kai Dang, Keming Lu, Keqin Bao, Kexin Yang, Le Yu, Mei Li, Mingfeng Xue, Pei Zhang, Qin Zhu, Rui Men, Runji Lin, Tianhao Li, Tianyi Tang, Tingyu Xia, Xingzhang Ren, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yu Wan, Yuqiong Liu, Zeyu Cui, Zhenru Zhang, and Zihan Qiu. Qwen2.5 technical report. arxiv preprint 212 2024.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint 2015.
Amrith Setlur. Chirag Nagpal, Adam Fisch, Xinyang Geng, Jacob Eisenstein, Rishabh Agarwal, Alekh Agarwal, Jonathan Berant, and Aviral Kumar. Rewarding progress: Scaling automated process verifiers for Ilm reasoning. arXiv preprint arXiv:2410.081446 2024.
13

---

Published as a conference paper at ICLR 2026
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song. Xiao Bi. Haowei Zhang, Mingchuan Zhang, YK Li, Yang Wu, et al. Deepseekmath: Pushing the limits of mathemati- cal reasoning in open language models. arXiv preprint aTXIv:2402.03300, 2024.
Joykirat Singh, Raghav Magazine, Yash Pandya, and Akshay Nambi. Agentic reasoning and tool integration for Ilms via reinforcement learning. arXiv preprint arXi::2005004441, 2025.
Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.033144 2024.
Hao Sun, Zile Qiao, Jiayan Guo, Xuanbo Fan, Yingyan Hou, Yong Jiang, Pengjun Xie, Yan Zhang, Fei Huang, and Jingren Zhou. Zerosearch: Incentivize the search capability of Ilms without searching. arXiv preprint arXiv:2505. 2025.
Kimi Team, Yifan Bai, Yiping Bao, Guanduo Chen, Jiahao Chen, Ningxin Chen, Ruijue Chen, Yanru Chen, Yuankun Chen, Yutian Chen, et al. Kimi k2: Open agentic intelligence. arXiv preprint ar arXiv:2507.20 205544, 2025a.
Kimi Team, Angang Du, Bofei Gao, Bowei Xing, Changjiu Jiang, Cheng Chen, Cheng Li, Chenjun Xiao, Chenzhuang Du, Chonghua Liao, et al. Kimi k1. 5: Scaling reinforcement learning with Ilms. arXiv preprint arXiv:2501. 2025b.
Harsh Trivedi, Niranjan Balasubramanian. Tushar Khot, and Ashish Sabharwal. Musique: Multihop questions via single-hop question composition. Transactions of the Association for Computational Linguistics, 10:539-555 554, 2022.
Ziyu Wan, Xidong Feng. Muning Wen, Stephen Marcus Mcaleer, Ying Wen, Weinan Zhang, and Jun Wang. Alphazero-like tree-search can guide large language model decoding and training. In International Conference Machine Learning, pp. 49890-49920, PMLR, 2024.
Liang Wang. Nan Yang, Xiaolong Huang, Binxing Jiao. Linjun Yang, Daxin Jiang, Rangan Ma- jumder, and Furu Wei. Text embeddings by weakly-supervised contrastive pre-training. arXiv preprint ar arXiv:22/2.088: 03533, 2022.
Peiyi Wang, Lei Li, Zhihong Shao, Runxin Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhifang Sui. Math-shepherd: Verify and reinforce Ilms step-by-step without human annotations. In Pro- ceedings of the 62nd Annual Meeting of the Association for Computational Linguisties (Volume 1: Long Papers), pp. 9426-9439, 2024.
Qiuchen Wang, Ruixue Ding, Yu Zeng, Zehui Chen, Lin Chen, Shihang Wang, Pengjun Xie, Fei Huang, and Feng Zhao. Vrag-rl: Empower rusion-perception-baeee based rag for visually rich in- formation understanding via iterative reasoning with reinforcement learning. arXiv preprint arXiv:2505.22019 2025a.
Zihan Wang, Kangrui Wang, Qineng Wang. Pingyue Zhang, Linjie Li, Zhengyuan Yang, Xing Jin, Kefan Yu, Minh Nhat Nguyen, Licheng Liu, et al. Ragen: Understanding self-evolution in I1m agents via multi-turn reinforcement learning. arXiv preprint arXiv:2504.20011 2025b.
Ziliang Wang. Xuhui Zheng. Kang An, Cijun Ouyang, Jialu Cai, Yuhang Wang, and Yichao Wu. Stepsearch: Igniting Ilms search ability via wise proximal policy optimization. arXiv preprint urXiv:2505.15107 2025c.
Jason Wei, Zhiqing Sun. Spencer Papay, Scott McKinney, Jeffrey Han, Isa Fulford, Hyung Won Chung. Alex Tachard Passos, William Fedus, and Amelia Glaese. Browsecomp: A simple yet challenging benchmark for browsing agents. arXiv preprint arXiv:2504. /2516, 2025.
Jialong Wu, Baixuan Li, Runnan Fang, Wenbiao Yin, Liwen Zhang, Zhengwei Tao, Dingehu Zhang, Zekun Xi, Gang Fu, Yong Jiang, et al. Webdancer: Towards autonomous information seeking agency. arXiv preprint arXiv:2505.22644 2025a.
Jialong WU, Wenbiao Yin, Yong Jiang, Zhenglin Wang, Zekun Xi, Runnan Fang. Linhai Zhang, Yulan He, Deyu Zhou, Pengjun Xie, et al. Webwalker: Benchmarking 1lms in web traversal. arXiv preprint 2501:2501007577 2025b.
14

---

Published as a conference paper at ICLR 2026
Zijian Wu, Suozhi Huang, Zhejian Zhou, Huaiyuan Ying, Jiayu Wang, Dahua Lin, and Kai Chen. Internhm2. 5-stepprover: Advancing automated theorem proving via expert iteration on large-seale lean problems. arXiv preprint arXiv:2410.15700, 2024.
Yuxi Xie, Anirudh Goyal, Wenyue Zheng, Min- Yen Kan, Timothy P Lillicrap, Kenji Kawaguchi, and Michael Shich. Monte carlo tree search boosts reasoning via iterative preference learning. arXiv preprint ar wxXiv2240500045 2024.
Huajian Xin, ZZ Ren, Junxiao Song. Zhihong Shao, Wanjia Zhao, Haocheng Wang, Bo Liu, Liyue Zhang, Xuan Lu, Qiushi Du, et al. Deepseck-prover-vl. 5: Harnessing proof assistant feedback for reinforcement learning and monte-carlo tree search. arXiv preprint arXiv:2408.08/35 2024.
Ran Xin, Chenguang Xi. Jie Yang. Feng Chen, Hang Wu, Xia Xiao, Yifan Sun, Shen Zheng, and Kai Shen. Bfs- Bis-prover: Scalable best-first tree search for Ilm-based automatic theorem proving. arXiv preprint arXiv:2502.033338 2025a.
Ran Xin, Zeyu Zheng, Yanchen Nie. Kun Yuan, and Xia Xiao. Scaling up multi-turn off- off-policy rl and multi-agent tree search for Ilm step-provers. arXiv preprint arXiv:2509. 06499,, 2025b.
Wei Xiong, Chengshuai Shi, Jiaming Shen, Aviv Rosenberg, Zhen Qin, Daniele Calandriello, Misha Khalman, Rishabh Joshi, Bilal Piot, Mohammad Salch, et al. Building math agents with multi- turn iterative preference learning. In ICLR, 2025.
Zhenghai Xue, Longtao Zheng, Qian Liu, Yingru Li, Xiaosen Zheng, Zejun Ma. and Bo An. Sim- pletir: End-to-end reinforcement learning for multi-turn tool-integrated reasoning. arXiv preprint arXiv:2509.02479, 2025.
An Yang, Anfeng Li, Baosong Yang. Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, et al. Qwen3 technical report. arXiv preprint arXiv:2505.00338, 2025a.
Zhicheng Yang, Zhijiang Guo, Yinya Huang, Xiaodan Liang, Yiwei Wang, and Jing Tang. Treerpo: Tree relative policy optimization. arXiv preprint 25X::2500.05/83, 2025b.
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D Manning. Hotpotqa: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 Conference on Empirical Methods Natural Language Processing, pp. 2369-2380, 2018.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629, 2022.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- 2023.
vances in neural information processing systems,
Qiying Yu, Zheng Zhang, Ruofei Zhu, Yufeng Yuan, Xiaochen Zuo, Yu Yue, Weinan Dai, Tiantian Fan, Gaohong Liu, Lingjun Liu, et al. Dapo: An open-source Ilm reinforcement learning system at scale. arXiv preprini arXiv:2503. 14476, 2025.
Chong Zhang, Yue Deng, Xiang Lin, Bin Wang, Dianwen Ng, Hai Ye, Xingxuan Li, Yao Xiao, Zhanfeng Mo, Qi Zhang, et al. 100 days after deepseek-rl: survey on replication studies and more directions for reasoning language models. arXiv preprint vrXiv:2505.005// 2025a.
Dan Zhang, Sining Zhoubian, Ziniu Hu, Yisong Yue, Yuxiao Dong, and Jie Tang. Rest-mets Llm self-training via process reward guided tree search. Advances in Neural Information Processing Systems, 37:64735-64777 2024.
Guibin Zhang, Hejia Geng, Xiaohang Yu, Zhenfei Yin, Zaibin Zhang, Zelin Tan, Heng Zhou, Zhongzhi Li, Xiangyuan Xue, Yijiang Li, et al. The landscape of agentic reinforcement learning for lms: A survey. arXiv preprint arXiv:2509.02547 2025b.
15

---

Published as a conference paper at ICLR 2026
Wenlin Zhang, Xiangyang Li, Kuicai Dong. Yichao Wang, Pengyue Jia, Xiaopeng Li, Yingyi Zhang, Derong Xu, Zhaocheng Du, Huifeng Guo, et al. Process vs. outcome reward: Which better for agentic rag reinforcement learning. arXiv preprint arXh::2505
2025c.
Chujie Zheng, Shixuan Liu, Mingze Li, Xiong- Hui Chen, Bowen Yu, Chang Gao, Kai Dang, Yuqiong Liu, Rui Men, An Yang, et al. Group sequence policy optimization. arXiv preprint arXiv:2507. 18071, 2025.
Andy Zhou, Kai Yan, Michal Balapentokh-Rothmaal Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning, acting, and planning in language models, In International Conference on Machine Learning. pp. 62138 62160. PMLR, 2024.
Yifei Zhou, Song Jiang, Yuandong Tian, Jason Weston, Sergey Levine, Sainbayar Sukhbaatar, and Xian Li. Sweet-rl: Training multi-turn Ilm agents on collaborative reasoning tasks. arXiv preprint arXiv:2503.15478, 2025.
APPENDIX
A DATASETS
Since the agent exhibits varying characteristics across different benchmark settings, we consider three experimental settings, where distinct training sets are employed.
A.1 SINGLE-HOP QUESTION ANSWERING
Single-hop QA is question answering solvable with a single supporting passage. For single-hop QA training, directly the training split from NQ (Kwiatkowski al., 2019). The whole training data includes 79,168 QA pairs.
For single-hop QA test, utilize the following datasets:
Natural Questions (NQ) (Kwiatkowski et al., 2019) test set includes 3,610 QA pairs.
TriviaQA (Joshi et al., 2017) test set includes 11,313 QA pairs.
PopQA (Mallen et al., 2023) test set includes 14,267 QA pairs.
A.2 MUL.TI-HOP QUESTION ANSWERING
Multi-hop QA is question answering that requires compositional reasoning and aggregation of evi- dence across multiple documents entities. For multi-hop QA training, directly use the training split from HotpotQA (Yang et al., 2018). The whole training data includes 90,447 multi-hop QA pairs.
For multi-hop QA test, we utilize the following datasets:
HotpotQA (Yang al., 2018) test set includes 7,405 QA pairs.
2WikiMultiHopQA (Ho et al., 2020) test set includes 12,576 QA pairs.
Musique (Trivedi et al., 2022) is a challenging multi-hop benchmark, which requires not only the model's lss information retrieval capabilities, but also deeper semantic understanding and logi- cal reasoning. The test set includes 2,417 QA pairs.
Bamboogle (Press et al., 2023) is a 2-hop hand maded dataset. The test set includes only 125 QA pairs.
A.3 WEB-AGENT QUESTION ANSWERING
Web-agent QA is question answering in interactive web environments where the agent must search, navigate, and perform single- or multi-turn exploration and information integration. The dataset for web-agent QA training consists of two parts. For the first part, sample 2k samples from ASearcher-323 (Gao et al., 2025), where each question and answer filtered and verified. The second part is from released samples from WebDancer (Wu al., 2025a), which includes 200 hard
16

---

Published as a conference paper at ICLR 2026
web QA pairs. Due to the high cost of real search APIs and the difficulty of obtaining high-quality training samples, the scale of our Web-Agent QA experimental setup is relatively small.
For web-agent QA test, utilize the following datasets:
SimpleQA (Press et al., 2023) includes 500 short, fact-seeking QA pairs, which is adversarially collected against GPT-4 responses.
GAIA (Mialon et al., 2023) is a hard general AI assistant benchmark consists of real-world questions. It requires the model to have the abilities such as reasoning, multi-modality handling, web browsing, and generally tool-use. We only use 103 text-only questions following previous works.
Web WalkereAA (Wu al., 2025b) contains 680 web traversal QA tasks, which is splited into three levels: easy, medium and hard.
BrowseComp (Wei et al., 2025) is a challenging benchmark for measuring the abilityf ro agents to browse the web. comprises 1,266 extremely complex, hard-to sold-to-fidd information questions.
B EXPERIMENT DETAILS
B.1 IMPLEMENTATION DETAILS
Our implementation is built upon Search-RI (Jin et al., 2025b) based on VeRL. As Table 5, for all experimental settings, we use the learning rate le-6, and K3 KL in loss with 0.001 coefficient. If not specified, we use group size 4 for all chain-based RI, and (M = 2, N = 2, T= 1) for Tree-GRPP In particular, we follow Jin et (2025a) to add format score X to the training reward r(y) as:
r(y) = (ccore(y) - Xy if frommat (y) = False
(13)
(cooeey))
else
where X is set to 0.2 in all experiments. The following are the different setups for different experi- mental settings:
For Single-Hop QA and Multi-Hop QA settings, our standard setup includes a total training step of 180, training batch size 512, PPO mini batch size 64. The max response length set to 4096 tokens, and the top 3 passages from local retrieval server will be passed to the agent.
the total training setp 34 (which corresponds to 2 epoch), training batch size 128, PPO mini batch size 64. The max response length is set to 8000 tokens, and the top 10 passages from web serp API will be passed agent.
For Web-Agent QA setting,
Table 5: Hyperparameters for Tree-GRPO and baseline methods for all experiments.
Config
Single-Hop QA
Multi-Hop QA
Web-Agent QA
optimizer
AdamW
Adam W
AdamW
learning rate
le-6
le-6
le-6
learning rate warmup ratio
0.285/0.5
0.285/0.5
0
KL type
K3
K3
K3
KL coefficient
0.001
0.001
0.001
training data
79,168
90,447
2,200
total training steps
180
180
34
training batch size
512
512
128
PPO mini batch size max response length
64
64
64
4096
4096
8000
max observation length
500
500
1000
max tool-calls
3
3
5
reward metrics
EM
EM
Fl score
format scores
0.2
0.2
0.2
retriever
local wiki 3
local wiki
Bing API
top-K retrieval passages
10
17

---

Published as a conference paper at ICLR 2026
Following Jin et al. (2025b), content enclosed within <search> </search> tags is parsed the search query, which corresponds to the Action a. The returned search results are then wrapped in <informa- tion> </information> tags to form the Observation o, thereby completing the ReAct tuple (T, at o). The prompt template for each question as:
Prompt Template
Answer the given question. You must conduct reasoning inside <think> and </think> first every time you get new information. After reasoning, if you find you lack some knowledge, you can call a search engine by <search> query </search> and it will return the top searched results between <information> and </information>, You can search as many times as your want. If you find no further external knowledge needed, you can directly provide the answer inside <answer> and </answer>, without detailed illustrations. For example, <answer> Beijing </answer>. Question:
B.2 BASELINES
Direct Inference. For direct inference, we directly employ instruct model answer the question. The prompt template no longer includes any tool-use instructions, and keeps only the directive "Answer the given question. You must put the answer inside <answer> and </answer>".
Scarch-ol (Li et al., 2025c) is the search-enhanced reasoning framework, which integrates the agen- tic RAG mechanism and crason-in-documee module.
ReAct (Yao et al., 2022) interleaves reasoning traces "Thought" with "Actions" (tool calls) to enable deliberate, step-by-step problem solving. The model decides when to think and when to act, using observations to refine subsequent reasoning. We use the instruct model based on ReAct as the baseline. All the RL-based methods are also based on ReAct.
GRPO (DeepSeek-AI Team, 2025) is a group-relativ policy optimization method that updates the policy using relative advantages computed across multiple trajectories for the same prompt. Com- pared to PPO, it discards the value/critic model and associated losses, yielding policy-only objec- tive that simplifies the training pipeline with fewer components and hyperparameters. Our approach built on GRPO, and we adopt GRPO as the primary baseline for chain-based RL.
GSPO (Zheng et al., 2025) is a variant of GRPO that replaces token-level importance ratio calcu- lation with trajectory-level reweighting. By unifying importance ratio computation and advantage estimation at the trajectory level, GSPO improves the stability of LLM RL training.
B.3 TREE SEARCH AT DIFFERENT LEVELS
To verify the effectiveness of tree search at different levels, we also conduct tree search at the to- ken/sentence level. Since existing tree-based RL methods (Hou et al., 2025; Yang et al., 2025b; Li et al., 2025f; Guo et al., 2025; Kazemnejad et al., 2024) are not designed for agent tasks and cannot be directly applied, here we separately implement token/sentence level tree search for agent RL.. Specifically, we build the tree where each node corresponds to a token, and modify step 2 of Tree- GRPO randomly sample tokens. During sampling, we mask out tokens from the observation that are not generated by the LLM for each trajectory H' in order to prevent information confusion as:
[1.
H E fT,a}
[MASK]
(14)
10
P. = Sample (fps, E T [MASK] = =))-
(15)
The other settings remain consistent with Tree-GRPO.
Table 6 and Figure 7 show that tree search at the token/sentence level performs worse than the agent-step level in both single-hop QA and multi-hop QA, and even falls below the performance of chain-based GRPO. We attribute this effect to two factors. On the one hand, exploring branches in the middle of an agent step lacks a clear purpose and may lead to rollout budget waste. On the other hand, the credit derived from token/sentence-leell tree structure undermines the integrity of
18

---

Published as a conference paper at ICLR 2026
Table 6: Test score comparison between search token/sentencc-llvel and agent step-level. The base model is Qwen2.5-3b. The rollout budget is 4/per prompt. Tree search parameters are
M N 2
Single-Hop QA
Multi-Hop QA
Method
NQ
Trivia
PopQA
Avg.
Hotpot
2wiki
Musiq
Bamb
Avg.
GRPO
44.4
58.0
42.0
48.1
39.0
36.3
15.2
36.8
31.8
Token/sentence level
42.1
56.0
40.6
46.2
32.0
30.8
8.4
17.6
22.2
Agent step level
46.8
59.7
43.6
50.0
42.4
43.7
17.8
43.2
36.8
0.65
0.60
Reward
0.55
0.50
0.45
True Apunt Step
beaed
0.35
40
60
80
100
120
140
160
180
Step
Figure 7: Training reward comparison on multi-hop QA between tree search at token/sentence-level and agent step-level.
the agent step, and the resulting process signal instead hinders the learning performance. Therefore, we argue that tree search conducted at the token or sentence level not suitable for agent RL tasks.
B.4 PERFORMANCE WITH DIFFERENT TREE STRUCTURES
We try different tree-search structures in Table 7. When (N 0, 0), the Tree-GRPO degener- ates into vamilla GRPO. The results show that the impact of and N is not much different. However, since the expansion iterations T. directly affect the rollout efficiency (as the iterations executed serially), we consider using larger and set I. = in most of the experiments. In addition, while reducing the number of trees M saves rollout budget, the more constrained exploration in tree search adversely impacts the performance of RL.
Based on the results from Table and Table 7, we attribute that M governs the diversity of sampling (as exploration), whereas N and L govern the granularity of the process signal (as exploitation). The gramularity process signals required for RL training is strongly correlated with the interaction length of the task, since the tree depth is directly dictated by the number of agent steps (e.g.. 3-4 steps for Multi-hop QA). this case, when N is the same order magnitude as or slightly larger than the tree depth, it is theoretically sufficient to construct the necessary granularity of the process signals. Given certain rollout budget, larger values N, L (much larger than tree depth) yield diminishing marginal benefits, while relatively smaller M limits sampling diversity and results in performance degradation. Balancing M and N can achieve trade-off between exploration and exploitation in tree search, leading to better performance.
C THEORETICAL ANALYSIS
Assumption C.1 (Binary Preference Setting) For each intermediate tree node (I, H.r)), the sub- sequent trajectory in terms of reward falls into two categories, denoted as Huin and Hoos with associated rewards (1,0). The trajectory probabilities are defined as
Do (Holl)) = 1 pa (P =
I T=
na (7 ( Her))
(16)
19

---

Published as a conference paper at ICLR 2026
Table Performance on multi-hop QA with different structures. The base model Qwen2.5- 3b. The best results are indicated in bold.
M, N, L
Hotpot
2wiki
Musiq
Bamb
Avg.
Rollout Token/Tool Budget = 2/per prompt
(M N 0, L = 0)
39.0
36.3
15.2
36.8
31.8
(M = 2, = 2, =1
42.4
43.7
17.8
43.2
36.8
(M N,N = -1,-=2
42.3
43.2
17.6
41.9
36.3
(M = 1,N = -5,L=1)
41.5
39.3
15.8
37.6
33.6
Rollout Token/Tool Budget = 16/per prompt
(M = 16, N = 0, 0)
40.1
38.8
17.5
39.2
33.9
(M = 8, N = =2,L=1)
44.6
43.2
18.2
38.4
36.1
[M 6, N =3,L=1
45.3
44.1
18.8
37.6
36.5
.M = 5, =V21=
44.6
43.8
17.9
36.8
35.8
(M 4,N = =5,-=1]
45.0
43.9
18.5
41.6
37.3
(M = 2. N = =11,==1
43.0
42.2
16.1
40.0
35,3
(M N,N 6, 22
43.2
43.1
17.0
40.0
35.8
[M = 2,N 4, L = 3)
43.6
43.1
16.8
40.8
36.1
By the assumption, the probability of H could be normalized within the binary set C = {Wain Hlmr)) as:
Po (H
po
II mo (7 zr, Her)
(H C, Hct)
(17)
log pu Po
log po (2, + (H
= =log (H Hee) - log po (7 l. Het)),
and the loss probability is:
Po Po loss = (1) win = a (log po (Hl loss (x, Hers) - log Pogpo(H10) xr, Het)).
(18)
For step-level DPO, the objective is to optimize Bradley-Terry preference likelihood by:
(D) Ex Hice, Hei, Aggg) [log (3Ae (zx Hee, H Hooss ))]
(19)
where preference defined by:
Az Her, Hwin Hluss) = log (H Cog Hee) - log Po (Hte0s Jr, Her).
(20)
Let
3.30 (ar, Hest Hwin Heloss)
(21)
where / is a temperature parameter, and we assume 3 1 for simplicity. Since DPO usually treats the expectation the empirical average of the sampled pairs (HWin Hloes). ), the gradient of Eq. 19
20

---

Published as a conference paper at ICLR 2026
(0) can be directly put inside
VoJDro(()
V log (Ao (z, Hese H2n H )]
= V log (2))
log (2) Ve2
d=
= o(-2) V/2
o--)) VaLo(æ, Her H2n Holo))
(-=)) V logpo (H [x, Het)) Vo log (H pi, Hct)]
o (1) Hot Hwin Hoge)
(22)
(log po Ho I. Het)) log po (H2 (r, Hct))
Vo log pa (H x Hee)) Vo log (H2 zz Hetr)
log po
log pol Hec)
Vo logoo (7 2., Hee) Vo log po (M 2 Hete)
pe x. Hee))
V log pe (H x Hoc))
V log pe (H x. Het)l
2(H)
Ve log po (H 2 V log (905)
Weight
Preference Advantage Gradient
For our intra-tree group policy optimization, the objective can be expressed as the combination of two categories Hwin and Hlosss
Give
Intrratreee (0) = (a
Awin + Arees)
(23)
Guee
where Guee is the number of leaves within the tree. Then the gradient of Eq. Jusua-uee (0) is:
J tree (0) 2 E [Aiin Vo log po (74 lc. Heee) + Auss Vo log pa (He or, Her))
Pa win [x. Hoce) Awin V log pa (H x Herr)
(24)
+ pe (Hl2s Jx, Hoz)) Ajoss V log (H Ix, Hel)
The baseline Rruse could estimated by probability as
R po (7 win - (oo
(25)
Here simply use the difference between Rwin/lass and Phuseline to express the advantage estimate as:
Awin Poin Pouse Po (H( (HH2108)), Anas Pives Phuse -po(?t win)
(26)
21

---

Published as a conference paper at ICLR 2026
Combining Eq. 17, Eq. 18, Eq. 24, and Eq. 26, the gradient of intra-tree group policy optimization can be reformulated as Ig pe
(H x. Her) Awin V log pe (H x, H.rt)
po 1 z: Ho()) Asss Vo log (H 2 x2 Het)
oo (o x. Het) po (H Ho0s x. Hct)
Ve log Po (H 22, Hct)
(27)
Poo(H 1 z. Heee)
po (H win x. He.1)
Vo Po Hell)
po (H pp
V log pe H 2
Ve Po
Weight
Preference Advaniage Gradient
From Eq. 22 and Eq. 27, we can have the following Proposition C.I.
Proposition C.I (Structural Equivalence of Step-level DPO and Intra-tree GRPO) Under As-
sumption C. 1, both step-level DPO and intra-tree GRPO admit gradient estimators of the form
V Juniffedd()
W.
(VelogPo pa (H V logog pe loss))
(28)
Weigha
Preference Advantage Gradient
where the only difference lies in the choice of the weight term w.
D ALGORITHM WORKFLOW OF TREE-GRPO
The complete Tree-GRPO procedure is detailed in Algorithm
E CASE STUDY
In this section, we provide some cases of the model trained by Tree-GRPO. As illustrated by suc- cessful Case 8 and Case the model can execute multi-turn agent tasks through iterative tool calls and autonomous information aggregation. For failed cases 10 and 11, the model selected a single candidate solution path at the beginning from among several that only partially met the requirements and did not pursue further exploration. In subsequent reasoning. it neither reconsidered nor verified its choice in light of newly acquired information, resulting in incorrect final answer. These find- ings motivate future work to integrate reflective reasoning and richer exploration into the training loop for complex, open-domain agents.
THE USE OF LARGE LANGUAGE MODELS (LLMs)
In this paper, LLMs are used to polish the content, adjust the format, write tables, and provide writing suggestions in some chapters.
22

---

Published as a conference paper at ICLR 2026
Algorithm 1: Tree-hased Group Relative Policy Optimization
Input: Policy model ne, search environment e, dataset D, hyperparameters M, N, L, maximum action budget B
Procedure GenerateRo lout (Hprefi))
// This procedure completes trajectory from prefix
H +- Hprefix:
6 budget of existing prefix
while < do
Generate H4 TO(- (z, Het));
H + + H4:
if yt </search> then
Parse last action <- Parse(y):
Observation + e(g):
H + H + -intormtioonociioomatto
else if H. E {</answer>, <eos>> then
break;
return 74;
Main algorithm logic starts here for step to Smatt do Reference model The +- mp: Training data H + Depp // Step 1: Generate independent chains for initial M trees for i
to M do
Hinitial < GenerateRRllout(")
Add Hamital to Tr
for Expansion iter = 1 to I. do
// Step 2: Sample nodes from each tree T for expansion
Randomly sample M x N expansion node from existing trees
P Prample PP..PP.....PMMNN... // Step 3: Do expansion
foreach E Paample do
Hexpansion <- GenerateRollutt/ee
Update M trees T with Hexpansion'
for Updating iter= = 1, do
Calculate intra-trec group relative advantage A by Eq. 6;
Calculate inter-tree group relative advantage Amerrstre by Eq. 6;
Update the policy model To by maximizing the Tree-GRPe objective (Eq. 8);
23

---

Published as a conference paper at ICLR 2026
Table 8: Tree-GRPO case study 1 (successful).
Example from Multi-Hop QA Dataset Musique
Question: Who is the owner of the record label of the performer of Groovy Little Summer Song?
Ground Truth: Warner Music Group, Warner Music
Model Output by Tree-GRPO (14B)
<think> To answer this question, I need to identify the performer of the song "Groovy Little Summer Song" and then find out who owns the record label that this performer is associated with. </think>
<search> Performer of the song "Groovy Little Summer Song" </search>
<information> Doc 1(Title: "Groovy Little Summer Song") Groovy Little Summer Song ''Groovy Little Summer Song"" "" is a song co-written recorded by American country music artist James Otto. It was released in March 2010 as the first single from his album ""Shake What God Gave Ya"". The song was written by Otto Doc 2(Title: "Emm Gryner") is written about her. Gryner was married to visual artist Sean Odell from 2004-2016. They have two children together. Emm Gryner Emm Gryner (born 8 June 1975 in Sarnia, Ontario) is Canadian singer-songwrite best known for her 1998 indie hit ""Summerlongg". Gryner's childhood ... Doc 3(Title: "Emm Gryner") Emm Gryner Emm Gryner (born 8 June 1975 in Sarnia, Ontario) is a Canadian singer- songwriter best known for her 1998 indie hit ""Summmerlong". Gryner's s childhood was spent in Forest, Lambton County, Ontario. Her father was of half Irish heritage and her mother was Filipina. Gryner ... </information>
<think> From the search results, it seems that the performer of the song "Groovy Little Summer Song" is James Otto. Now, need to find out who owns the record label that James Otto is associated with. </think> <search> Record label of the performer James Otto </search>
<information> Doc I(Title: "James Otto") In June 2015, Otto signed with Blaster Records, and ""Somewhere Tomight"" "" was released to country radio on July 13, 2015 as his first single with the record label. James Otto James Allen Otto (born July 29, 1973) is an American country music artist who is Doc 2(Title: "James Otto") James Otto James Allen Otto (born July 29, 1973) is an American country music artist who is member of the Muzik a group of country musicians known for their "" country music without prejudice"". Otto began his career on Mercury Nashville Records in 2002... Doc 3(Title: "James Otto") signed as an opening act for Shania Twain on her Up! Tour. His fourth single for Mercury, ""Sunday Morning and Saturday Night"", peaked at No. 58. After the song fell from the charts, Otto exited Mercury's 's roster. From there, he began working with the MuzikMafia ... </information>
<think> From the search results, it seems that James Otto is associated with record labels such as Mereury Nashville Records and Warner Bros. Records. Now, need to find out who owns these record labels. </think>
<search> Who owns Mercury Nashville Records and Warner Bros. Records </search>
<information> Doc 1TTtle: "Warner Bros. Records") Records from EMI as part of its sale to Universal Music Group. Most Parlophone artists (excluding Coldplay and Tinie Tempah, who were placed under Atlantic) were placed under Warner Bros Doc 2(Title: "Warner Bros. Records") Warner Bros. Records Warner Bros. Records Inc. is an American major record label owned by Warner Music Group and headquartered in Burbank, California. It was founded in 1958 as the Doe 3(Titl:: "Mereury Records") Mereury Records Mercury Records is an American record label owned by Universal Music Group. In the United States, it operates through Island Records; in the UK, it is distributed by Virgin EMI Records </information>
<think> From the search results, it seems that Mercury Nashville Records is owned by Sony Music Entertainment and Warner Bros. Records is owned by Warner Music Group. </think> <answer> Warnrr Music Group </answer>
24

---

Published as a conference paper at ICLR 2026
Table 9: Tree-GRPO case study 2 (successful).
Example from Web-Agent QA Dataset GATA
What is the absolute difference tens of thousands between the population of chin- strap penguins on the Wikipedia page for penguin species populations as of the end of 2018 and the population recorded in the Nature.com "global population assessment of the Chinstrap penguin" article from 2020, assuming two penguins per breeding pair?
Question:
Ground Truth: 116
Model Output by Tree-GRPO (14B)
<think> The user wants to know the absolute difference tens of thousands between the popula-
tion of chinstrap penguins mentioned on the Wikipedia page for penguin species populations as of the end of 2018 and the population recorded in the Nature Nature.com com article from 2020, considering two penguins per breeding pair. To find the answer, we need to search for the specifie population figures for chinstrap penguins in both sources and then calculate the difference. </think> <search> chinstrap penguin population in 2018 Wikipedia </search>
<information> Page I: The population of chinstrap penguins was estimated by IUCN in August 2018 and it is reported that there is a total of 8 million individual chinstrap penguins are living in the world. Page 2: According to the IUCN Red List, the total population size of the Chinstrap penguin 8 million individuals or 4 million breeding pairs. Currently, this species is classified as Least Concern Page 3: Jun 13, 2018 Most of the data analyses suggests a single large pop- ulation of chinstrap penguins throughout the Southern Ocean, with minimal population structure in the WAP region, and Page 4: This is a list of Sphenisciformes species by global popu- lation. While numbers are estimates, they have been made by the experts in their fields. Page 5: How many chinstrap penguins are there today? In 2018, the IUCN estimated about 8 million mature chinstrap penguins worldwide, though the population is decreasing. Page 6: Most of the data analyses suggests single large popula-tion of chinstrap penguins throughout the South- ern Ocean, with minimal population structure in the WAP re-gion, and absence of ... Page 7: BirdLife International has assessed 18 species. 16 (89% of total species) have had their popula- tion estimated: those missing are the king and little penguins, both of which have been assessed as being of least concern. [1][2] Page 8: Jun 13, 2018 High genetic diversity, evidence of female bias-dispersal and a sign of population expansion after the last glacial maximum around 10,000 mya were detected. Page 9: Nov 10, 2020 Twenty-thre previously known Chinstrap penguin colonies are found to be absent or extirpated </information>
<think> From the Wikipedia page, the population of chinstrap penguins 2018 was estimated to be 8 million. </think>
<search> chinstrap penguin population 2020 Nature.com </search>
<information> Page 1: Nov 10, 2020 Using satellite imagery, drone imagery, and ground counts, we have assembled the first comprehensive global population assessment of Chinstrap penguins (Pygoscelis... ... Page 2: We estimate the global population of Chinstrap penguins at 3.42 (95th- percentile CI: [2.98, 4.00)) million breed- ing pairs (Table 1) in 375 extant breeding sites, not including recent... Page 3: Population Convey et al. (1999) estimate a world population of million breeding pairs. Page 4: Using satellite imagery, drone imagery, and ground counts, we have assembled the first comprehensive global population Page 5: The Antarctic Penguin Bio- geography Project is an effort to collate all known information Page 6: Nov 10, 2020 Using satellite imagery, drone imagery. and ground counts, we have assembled the first comprehensive global population assessment of Chinstrap penguins (Pygoscelis antarctica) at 3.42... Page 7: Using satellite imagery, drone imagery, and ground counts, we have assembled the first com- prehensive global population assessment of Chinstrap penguins (Pygoscelis antarctica) at 3.42... Page 8: Feb 11, 2020 Scientists discovered that colonies of chinstrap penguins also known as ringed or bearded penguins- have dropped dramatically since they were last surveyed almost 50 years </information>
<think> The Nature com article estimates the global population of chinstrap penguins in 2020 to be 3.42 million breeding pairs. Since the user mentioned "two penguins per breeding pair", the population would be approximately 3.42 million * #2 = 6.84 million chinstrap penguins. Now, we need to find the absolute difference between the 2018 population (8 million) and the 2020 popu- lation (6.84 million) in tens of thousands. The difference 8,000,000 6,840.000 = 1,160.000. In tens of thousands, this is 116. </think> <answer> 116 </answer>
25

---

Published as a conference paper at ICLR 2026
Table 10: Tree-GRPO case study 3 (failed).
Example from Mop QA Dataset Musique
Question: Who is a cast member of the show that contains the character Michael Knight?
Ground Truth: Deanna Russo, Bruce Davison
Model Output by Tree-GRPO (14B)
<think> To answer this question, I need to identify the show in which the character Michael Knight appears and then find out who is cast member of that show. </think>
<search> Character Michael Knight in TV show </search>
<information> Doc 1(Title: "Michael Knight (Knight Rider)")) Michael Knight (Knight Rider) Michael Knight is a fictional character and the protagonist of the 1980s television series ""Knight Rider" played by David Hasselhoff. The character first appeared in the opening scenes as Michael Long, played by Larry Anderson in the beginning of the pilot. Born Michael Arthur Long on January 9, 1949 outside of Los Angeles, California, raised by a blue-collar working family. In the late 1960s, while in his 20s, Long joined the Army, was part of the Green Berets, and spent three years in counter-intellienne work in Vietnam. He got captured at one point while on a Doe 2(Title: "Knight Rider (1982 TV series)") Knight Rider (1982 TV series) Knight Rider is an American television series created and produced by Glen A. Larson. The series was originally broadcast on NBC from 1982 to 1986. The show stars David Hasselhoff as Michael Knight, a high-tech modern crime fighter assisted by KITT, an advanced artificially intelligent, self-aware and nearly indestructible car. This was the last series Larson devised at Universal Television before he moved to 20th Century Fox. Self-made billionaire Wilton Knight rescues police Detective Licutenant Michael Arthur Long after a near fatal shot to the face, giving him a new identity (by plastic surgery) and Doc (TTtle:: "Michael Knight (Knight Rider)") Industries, an organization founded by Wilton Knight, a billionaire philanthropist. Michael was not Wilton Knight's first choice for the pilot program, but Wilton changed his mind and reopened the foun- dation due to Michael's arrival. In the context of the pilot, Wilton Knight (Richard Basehart) is dying of an undisclosed illness. Wilton picked up Michael passed out in front of his car, on a desert highway. Michael barely survived, thanks to the metal plate. Given a new face via facial reconstructive surgery, Long is resurrected as Michael Knight (now played by David Hasselhoff). Together with a high-tech automobile called the Knight </information>
<think> From the search results, is clear that Michael Knight a character in the show "Knight Rider". Now, I need to find out who is a cast member of this show. </think> <search> Cast members of Knight Rider </search>
<information> Doc 1(Title: "Knight Rider") Orci. On February 13, 2014, Schmoes Know reports that actors Chris Pratt and Danny McBride are in talks for roles and may use a sort of action- comedy hybrid in the same vein ""21 Jump Street"". In December 2015, media report indicated that a new movie named ""Knight Rider Heroes"" "" is in the works and will include David Hasselhoff. Knight Rider Knight Rider is an American entertainment franchise created by Glen A. Larson. The core of "nightt Rider"" "" is its three television series: ""Knight Rider"" (1982-1986), ""Team Knight Rider"" (1997-1998), and ""Knight Rider"" (2008-2009). The franchise also includes three Doc 2(Title: "Knight Rider") to write the first script draft, with the series' lead actor David Hasselhoff attached as an advisor and also have an onscreen role. In April 2003, Revolution Studios hired screenwriters David Elliott and Paul Lovett to pen the film 's script. In April 2004, the premise of the film was described as having Hasselhoff reprise his role as Michael Knight, now the mentor to the protagonist as Devon Miles mentored Knight in the television series. The protagonist would be Knight's son, inheriting his father's role and driving the vehicle KITT. The producers' choice for the role "Knight Rider (2008 TV series)") Knight Rider (2008 TV series) Knight Rider is a 2008 series that follows the 1982 television series of the same title created by Glen A. Larson and the 2008 television movie. The series stars Justin Bruening as Mike Traceur, the estranged son of Michael Knight. The series also stars Deanna Russo as Sarah Graiman, Traceur's former girlfriend and love interest. Sarah is the daughter of Charles Graiman. Graiman, played by Bruce Davison, is the creator of a new generation of KITT (Knight Industries Three Thousand), which is voiced by Val Kilmer. The series was in production for just one season. </information>
actor Ben Affleck. In Doc 3(Tile::
<think> From the search results, it clear that David Hasselhoff is a cast member of the show "Knight Rider". </think> <answer> David Hasselhoff </answer>
26

---

Published as a conference paper at ICLR 2026
Table 11: Tree-GRPO case study (failed).
Example from Web-Agent QA Dataset WebWalkerQA
Question:
As of December 2023, this individual was announced as the football team's 's coach as per an article published between 2019 and 2021 inclusive. The football team initially started as a social football club in 1995 before changing its name in 2011 as per an article published that began as a social club per an article published between 2019 and 2021 inclusive. The football club won a title in its home country league for the fourth successive time in a row as reported in an article published between 2020 and 2023 inclusive. This league win was this individual's 's third with the football club and the fourth overall as reported in an article published between 2020 and 2023 inclusive. The individual underwent surgery for back injury as per an article published in 2018. Tell me the full name of this individual.
Ground Truth: Norman Takanyariwa Mapeza
Model Output by Tree-GRPO (14B)
<think> To find the full name of the individual, I need identify the football team and its league
in their home country. Then, I will look for articles about this team between 2020 and 2023 that mention a coach who won a title for the fourth consecutive time and is the third time for this coach. Additionally, I should look for an article about the coach's 's surgery in 2018. The coach's 's name will likely be mentioned in these articles. </think>
<search> football team social club 1995 </search>
<information> Page I: 1995 Stadium Club Football checklist, gallery, release date, inserts, paral- lels, forum, and collection tracking Page 2: 1995 Stadium Club card list & price guide. Ungraded & graded values for all 1995-96 Topps Stadium Club Football Cards Page 3: Get the best deals on 1995 Topps Stadium Club Football Trading Cards when you shop the largest online selection at eBay.com.. Page 4: A wide selection of single cards from the 1995 Stadium Club football card set. Page 5: Shop COMC's extensive selection of 1995 topps stadium club members only football cards Page 6: Get the latest and most accurate trading card values and sets info for 1995 Stadium Club Football sports cards ... Page 7: 1995 Stadium Club Teams Arizona Cardinals Atlanta Falcons Buffalo Bills Carolina Panthers Chicago Bears </information> <think> The search results do not provide enough information to identify the football team or the individual. I need to narrow down my search query </think>
<search> football team started as social club 1995, changed name 2011, coach won league title four consecutive times between 2020 and 2023 </search>
<information> Page I: The Crossword Solver found 30 answers to "football club changed name 2011 league title... ... Page 2: May 27, 2016 Leicester became the sixth club to win the Premier League, completing
Page 3: 18 hours ago Live updating Football Club Started As Social Club 1995 Renamed 2011 ... Page 4: List of football league clubs in the top four tiers of English football (i.e. the Page 5: May 22, 2024 Manchester City saw off West Ham United on the
final 2023/24... ... Page 6: Aug 29, 2023 Manchester City wrapped up the 2022/23 season with an incredible </information>
<think From the search results, I learned that Manchester City won four consecutive domestic league titles between 2020 and 2023. need to find articles between 2020 and 2023 that mention the name of the coach of Manchester City who won the league titles. Additionally, I should look for an article about the coach's 's surgery in 2018. </think>
<search> manchester city coach won league title four consecutive times between 2020 and 2023, coach surgery 2018 </search>
<information> Page 1: May 19, 2024 Manchester City won an unprecedented fourth consecutive Premier League title on Sunday as Phil Page 2: May 19, 2024 Pep Guardiola and Manchester City made history on Sunday, when a 3-1 win over West Ham- Page 3: May 20, 2024 But Guardiola now stands alone as the only boss to manage quality quartet of title.. ... Page 4: May 21, 2024 Pep Guardiola was announced as the winner of the Premier League Manager of the Season ... Page 5: May 19, 2024 Manchester City have
their fourth consecutive Premier League title, sealing yet Page 6: May 19, 2024 Some wondered whether Manchester City would retain their hunger after winning the ... Page 7: May 19, 2024 Taking in spells Barcelona and Bayern Munich, Guardiola has now won the league ... </information> <think> Based on the search results, the full name of the individual who was announced as the football team's 's coach is Pep Guardiola. </think <answer> Pep Guardiola </answer>
27


Reviews:
[{"review_id": "7eeJWct4k3", "reviewer": "Reviewer_PcpF", "summary": "The paper \"Tree Search for LLM Agent Reinforcement Learning\" introduces Tree-based Group Relative Policy Optimization (Tree-GRPO), a novel method to address the high costs and sparse supervision challenges in training LLM agents for multi-turn tasks . Instead of inefficient \"chain-based\" rollouts, Tree-GRPO employs a tree-search sampling strategy where each node represents a complete agent step (Thought, Action, Observation). This structure significantly improves budget efficiency by sharing common prefixes and, crucially, allows the model to derive fine-grained, step-level process supervision signals directly from sparse outcome rewards by comparing the performance of different branches. The paper's key contributions include this highly efficient agent-step-level tree-search method, an implicit preference learning objective that is theoretically shown to be structurally equivalent to step-level DPO , and strong empirical results demonstrating superior performance over baselines while using as little as one-quarter of the rollout budget.", "questions": "- In Table 4, it seems that intra-tree advantage will lead to collapse and the main performance gain is from the inter-tree. So the mainly the advantage estimated by different initialization contribute most to the performance. So, it seems that large $M$ is more important than large $N$ and large $L$. Is that understanding correct? \n- How do you choose M,N,L in prior? In practice, it seems that $L=1$ is the best choice. But how to balance $M$ and $N$ given the same computational budget? For example, to choose larger M or larger N given the same budget?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper re-frames the inefficient \"chain-based\" sampling process  as a problem that can be optimized with a \"tree-based\" shared-prefix structure.\n- The authors don't just propose a method; they provide a theoretical justification (Proposition 3.1) that connects their intra-tree advantage estimation to the well-established DPO framework , lending it significant credibility.\n- The quality is further reinforced by a series of insightful ablation studies. These include testing performance under different rollout budgets, analyzing the contribution of the $\\hat{A}_{intra-tree}$ and $\\hat{A}_{inter-tree}$ advantage components, and comparing against the intuitive token-level tree search.", "weaknesses": "- While Tree-GRPO showed consistent improvements, the authors note that for highly challenging web-agent benchmarks like BrowseComp, the gains from RL (both chain-based and tree-based) were marginal. They attribute this primarily to the limited quality and difficulty of the available training data rather than a failure of the method itself .\n- The method introduces new hyperparameters that govern the tree structure, specifically the number of initial trees ($M$), the number of nodes to expand ($N$), and the number of expansion iterations ($L$). This will introduce additional hyperparameter choice under different situations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Au2lWED56Q", "reviewer": "Reviewer_TDPe", "summary": "The paper presents a new efficient tree-search rollout approach for training an RL-based LLM agent in which each node of the rollout tree represents a complete thought-action-observation step of the LLM agent. This tree-search based method is shown to obtain more samples than existing chain-based method. The paper then introduces a group-relative advantage estimation at both intra and inter-tree levels, incorporating preference objectives while leveraging rollouts from all trees, allowing for a more stable training. Experiments across different settings including multi-hop QA, single-hop QA, and web-agent QA are conducted, showing improved performance of the proposed method compared to baselines.", "questions": "1. Could you please justify why uniform distribution of credits across different steps is reasonable in this learning setting?\n2. Can you provide some thoughts on applying existing sparse-reward RL methods for LLM agents?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is clearly written. Explanations on how rollout search trees are built and how group relative advantages are computed are easy to follow.\n2. The idea of rollout search trees based on a complete thought-action-observation step is promising as it is shown to be cost-effective in collecting samples. \n3. Experiments are extensive. Results on various QA settings show that the proposed method outperforms other SOTA baselines in most of the evaluated settings.", "weaknesses": "1. In sparse-reward RL, there is a long line of research on credit assignments or reward redistributions. There lacks discussions on why these existing sparse-reward RL algorithms were not applied in this RL-based LLM agent. \n2. In the proposed tree-based credit assignment method, it appears that stepwise advantages are identical across all time steps within each trajectory. This uniform credit distribution is quite simplistic and may fail to capture the varied contributions of different steps to overall performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "85eZxLJqdW", "reviewer": "Reviewer_uD4w", "summary": "This paper introduces Tree-GRPO, a novel method designed to enhance LLM agents in long-term, multi-turn RL tasks. The authors address two critical challenges in current agentic RL: the heavy computational budget associated with LLM rollouts, and the sparse supervision problem arising from outcome-only rewards.\n\n1. Tree-GRPO proposes a tree-search based online rollout strategy where each tree node represents a complete agent interaction step (Thought-Action-Observation). By sharing common prefixes within the tree structure, the method significantly increases the number of effective rollouts under a fixed token/tool-call budget.\n2. This method leverages the tree structure to naturally derive fine-grained, step-wise process supervision signals purely from outcome rewards by estimating grouped relative advantages at both intra-tree and inter-tree levels.\n3. The paper theoretically demonstrates that intra-tree level group relative policy optimization is equivalent to step-level direct preference learning.\n4. Empirical evaluations across 11 datasets spanning Single-Hop, Multi-Hop, and hard Web-Agent QA tasks, using various LLM models, demonstrate Tree-GRPO's superiority over chain-based RL methods. Notably, it achieves higher performance with a significantly reduced rollout budget, particularly for smaller models and in complex multi-hop interactions.\n5. The paper also provides ablation studies on tree node granularity and tree structure parameters, as well as analyses on budget efficiency and the method's ability to encourage longer, more complex interactions.", "questions": "1. In Figure 1, the paper claims \"less rollout budget (both on tokens and tool-calls)\", and mentions achieving 1.5x samples under the same budget later. Does there exist a more detailed breakdown of how these savings in tokens and tool-calls are realized in practice?\n2. What is the actual wall-clock time comparison between chain-based and tree-based training? Considering the complexity of tree management, does this offset the token savings?\n3. How does your implicit process supervision compare to explicit process reward models when both are available?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper presents a relatively original approach by integrating tree-search sampling with GRPO for online LLM agent RL. The key innovation is the agent step-level node definition within the tree, which is a clever adaptation for efficient and meaningful process supervision in multi-turn agent tasks.\n2. The overall quality of the paper is exceptional. The method is clearly described, and the theoretical analysis provides valuable insights into why the method works. The experimental evaluation is thorough, covering different model families (Qwen, Llama), multiple sizes (1.5B-14B), and diverse task types (Single-Hop QA, Multi-Hop QA and Web-Agent QA). The detailed ablation studies, especially on the granularity of tree nodes (token/sentence vs. agent step) and tree structure parameters (M, N, L), examine important design choices.\n3. The paper is written with outstanding clarity. The explanations are precise, the technical details are well-articulated, and the figures effectively convey complex ideas.\n4. The work offers substantial significance to the field. It provides a highly effective and efficient method for training LLM agents, addressing the critical issues of sparse supervision and high computational costs. By showing how to derive fine-grained process signals from outcome rewards in an online setting, it opens new avenues for scalable and robust agent learning. The ability to encourage longer, more complex interactions is particularly important for the development of next-generation foundation models.", "weaknesses": "1. Detailed Breakdown of Rollout Budget Savings: Although the paper emphasizes \"less rollout budget\" and shows its effectiveness, a direct quantitative comparison of the actual training time and memory consumption (e.g., GPU hours, peak memory usage) between Tree-GRPO and chain-based GRPO would provide a more complete picture of its efficiency. While \"less rollout budget\" implies efficiency, explicit benchmarks on wall-clock time for training on large models would solidify this claim, especially since tree search itself can introduce overheads. This would complement the token/tool-call budget analysis.\n2. Restrictive Theoretical Assumptions: Assumption 3.1 (binary preference setting) is quite strong and unlikely to hold with continuous outcome rewards. The theoretical analysis would be more convincing with relaxed assumptions or empirical validation that the approximation holds reasonably well.\n3. Inconsistent Improvements: Performance gains vary considerably across settings. On single-hop QA with larger models (14B), improvements are marginal (~1%). On web-agent tasks, gains are limited by training data quality. This suggests the method's benefits are context-dependent.\n4. Experimental Limitations: There lackscomparison with explicit process reward models, which would be a natural baseline. There is also missing analysis of computational overhead for tree construction/management during training.\n5. Sensitivity Analysis for Key Hyperparameters Beyond Tree Structure: The paper conducts an excellent ablation on tree structure parameters (M, N, L) and shows LR warmup sensitivity. However, a more comprehensive sensitivity analysis for other critical hyperparameters, such as the KL coefficient or max response length across different tasks, could provide further guidance for practitioners on how to tune Tree-GRPO effectively. For example, how robust is the method to changes in the KL regularization term, which is often crucial in RL?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)