Information Gain-based Rollout Policy Optimization: An Adaptive Tree-Structured Rollout Approach for Multi-Turn LLM Agents

# Information Gain-based Rollout Policy Optimization: An Adaptive Tree-Structured Rollout Approach for Multi-Turn LLM Agents
Source: [https://arxiv.org/html/2607.06223](https://arxiv.org/html/2607.06223)
Yijun Zhang∗Fan Xu∗Jiaxin Ding†Yule XieShiqing Gao Xin DingHaoxiang ZhangLuoyi FuXinbing Wang Shanghai Jiao Tong University ∗Equal contribution\.†Corresponding author\.

###### Abstract

Reinforcement learning has become a promising paradigm for improving large language model \(LLM\) agents on long\-horizon search tasks, where the agent must make a sequence of intermediate decisions before receiving a final outcome\. However, existing methods still face a key limitation: the rollout budget is often allocated without explicitly assessing the utility of intermediate states\. As a result, substantial computation may be spent on low\-value states, even though different branches can vary drastically in their informativeness\. In this paper, we propose Information Gain\-based Rollout Policy Optimization \(IGRPO\), a policy optimization framework that treats intermediate\-state informativeness as the organizing principle of rollout collection\. Specifically, IGRPO performs budget\-aware tree\-structured rollouts by allocating expansion budget according to node\-level informativeness, so that more informative branches are expanded more frequently while unpromising branches are progressively suppressed\. We further demonstrate that the information gain\-based rollout induces an explicit limiting teacher distribution over trajectories, which naturally yields a clear policy optimization target, thereby unifying adaptive tree\-structured exploration with principled policy learning under a single framework\. Experiments on seven challenging search\-augmented QA benchmarks demonstrate that IGRPO consistently outperforms strong baselines under the same rollout budget constraints, validating the effectiveness of leveraging the induced teacher distribution to guide policy optimization for long\-horizon search agents\.

## 1Introduction

Large language models\[[2](https://arxiv.org/html/2607.06223#bib.bib29),[3](https://arxiv.org/html/2607.06223#bib.bib30),[26](https://arxiv.org/html/2607.06223#bib.bib31)\]are increasingly trained to act as agents that solve tasks through multi\-turn interaction with external tools\[[34](https://arxiv.org/html/2607.06223#bib.bib32),[20](https://arxiv.org/html/2607.06223#bib.bib33),[36](https://arxiv.org/html/2607.06223#bib.bib35),[10](https://arxiv.org/html/2607.06223#bib.bib36)\]\. In search\-augmented question answering\[[30](https://arxiv.org/html/2607.06223#bib.bib38),[15](https://arxiv.org/html/2607.06223#bib.bib37),[12](https://arxiv.org/html/2607.06223#bib.bib3)\], an agent must decide what to reason about, when to issue a retrieval query, how to use the returned evidence, and finally when to answer\. A central difficulty in this setting is that the agent must allocate a limited interaction budget across many possible intermediate search states\. Effective training therefore requires not only assigning credit to completed trajectories, but also deciding where rollout computation should be spent\.

Reinforcement learning has been widely adopted to improve such agents by optimizing their interaction trajectories\[[19](https://arxiv.org/html/2607.06223#bib.bib34)\]\. Existing outcome\-based methods typically optimize complete trajectories using final correctness rewards\[[21](https://arxiv.org/html/2607.06223#bib.bib2),[17](https://arxiv.org/html/2607.06223#bib.bib22)\], while group\-based variants such as GRPO\[[22](https://arxiv.org/html/2607.06223#bib.bib1)\]further avoid a learned critic by comparing multiple rollouts for the same question\. Recent studies have sought to improve long\-horizon agent training from two complementary directions: finer\-grained credit assignment and broader exploration\. Chain\-based methods such as GiGPO\[[7](https://arxiv.org/html/2607.06223#bib.bib6)\]and IGPO\[[28](https://arxiv.org/html/2607.06223#bib.bib7)\]move beyond pure outcome\-level learning by introducing turn\-level learning signals for intermediate decisions\. Tree\-based methods such as Tree\-GRPO\[[11](https://arxiv.org/html/2607.06223#bib.bib10)\]and AEPO\[[4](https://arxiv.org/html/2607.06223#bib.bib28)\]extend rollout generation from a single chain to a branching search process, exploring alternative continuations through random branching or heuristic hard\-threshold expansion rules\. Together, these two lines of work demonstrate that intermediate states are crucial for training search agents\.

![Refer to caption](https://arxiv.org/html/2607.06223v1/figures/introduction.png)Figure 1:Illustration of different rollout patterns\. Red nodes represent unpromising or even misleading states, green nodes represent informative states, and gray nodes represent other intermediate states\.Left: both chain\-based and existing tree\-based methods may still allocate exploration budget to unpromising nodes\.Right: our method adopts information gain\-based rollout allocation, preferentially expanding informative nodes and reducing exploration over unpromising branches\.However, existing approaches still leave a basic computation\-allocation problem unresolved\. Intermediate states can differ substantially in their downstream utility, but rollout budget is often allocated without explicitly estimating this utility\. Chain\-based methods may spend full trajectories on prefixes that are already unpromising\. Tree\-based methods improve exploration through branching, but their heuristic or uncertainty\-driven expansion rules can still allocate branches to unpromising continuations\. Moreover, these methods typically treat intermediate nodes as expansion targets rather than explicitly assessing whether they provide useful evidence for the final answer\. As a result, training can waste computation on low\-value or even misleading prefixes while under\-exploring states that contain evidence useful for answering the question\. This limitation appears in both chain\-based and existing tree\-based rollouts, as illustrated in the left panel of Fig\.[1](https://arxiv.org/html/2607.06223#S1.F1)\.

To tackle this issue, we proposeInformationGain\-basedRolloutPolicyOptimization \(IGRPO\), a policy optimization framework that treats intermediate\-state informativeness as the core organizing principle for rollout collection\. We use “information gain” in the operational sense of*answer\-likelihood information gain*: the increase in a policy’s normalized likelihood of the ground\-truth answer after reaching an intermediate search state\. Instead of allocating search budget uniformly over active branches, IGRPO treats information gain\-derived informativeness as a soft expansion potential\. At each rollout stage, active prefixes with larger informativeness are selected for expansion with higher probability, while low\-informativeness prefixes are sampled less often and therefore consume less computation\. This induces a budget\-aware tree\-structured rollout process that is better aligned with the needs of long\-horizon search \(see Fig\.[1](https://arxiv.org/html/2607.06223#S1.F1), right\)\. Moreover, our theoretical analysis shows that this information gain\-based rollout induces a limiting teacher distribution that explicitly biases sampling toward more informative trajectories\. This in turn provides a clear policy optimization target, enabling the policy to be trained toward the induced distribution\. In this way, IGRPO unifies adaptive tree\-structured rollout collection and policy optimization within a single framework for search\-intensive LLM agents\.

Extensive experiments on seven challenging search\-augmented QA benchmarks show that IGRPO consistently outperforms strong baselines, achieving stronger performance under the same rollout budget constraints\. Our main contributions are summarized as follows:

- •We introduce an information gain\-based tree rollout strategy for search\-intensive LLM agents\. Our method adaptively allocates rollout budget toward more informative intermediate states, reducing unnecessary exploration over unpromising branches during rollout collection\.
- •We provide a theoretical characterization of the induced limiting distribution under information gain\-based rollout\. This characterization shows that the rollout process naturally defines a teacher distribution, which serves as a clear optimization target for policy learning\.
- •We demonstrate on multiple challenging search\-augmented QA benchmarks that IGRPO consistently surpasses strong baselines\. On average, IGRPO improves the strongest baseline by 3\.1% with the 3B backbone and by 0\.9% with the 7B backbone\.

## 2Related Work

#### Reinforcement learning for large language models\.

Reinforcement learning \(RL\) has recently become a central paradigm for enhancing the reasoning and decision\-making capabilities of large language models \(LLMs\)\[[8](https://arxiv.org/html/2607.06223#bib.bib21),[17](https://arxiv.org/html/2607.06223#bib.bib22)\]\. Early post\-training methods such as PPO\[[21](https://arxiv.org/html/2607.06223#bib.bib2)\]establish the standard policy optimization framework for aligning generation behavior, while more recent critic\-free methods, including GRPO\[[22](https://arxiv.org/html/2607.06223#bib.bib1)\], RLOO\[[1](https://arxiv.org/html/2607.06223#bib.bib23)\], DAPO\[[35](https://arxiv.org/html/2607.06223#bib.bib24)\], and GSPO\[[37](https://arxiv.org/html/2607.06223#bib.bib25)\], improve scalability by avoiding an explicit value function and estimating policy gradients with reward\-based baselines or group\-normalized advantages\. Beyond preference alignment, RL has also been widely used to elicit complex reasoning behaviors, where models must make a sequence of intermediate decisions before receiving final feedback\. This property naturally connects RL\-based LLM training with agentic tasks, in which models need to reason, act, and interact with external environments over multiple turns\. These advances have laid the foundation for applying RL to search\-intensive LLM agents\.

#### RL for search\-intensive LLM agents\.

Building on these advances, a growing line of work has applied RL to search\-based LLM agents\. Early frameworks such as Search\-R1\[[12](https://arxiv.org/html/2607.06223#bib.bib3)\]train the model to autonomously issue search queries during turn\-by\-turn reasoning and optimize the entire interaction with outcome\-based rewards\. ZeroSearch\[[25](https://arxiv.org/html/2607.06223#bib.bib4)\]further studies how to incentivize search behavior without directly relying on a real search engine during training\. R1\-Searcher\[[23](https://arxiv.org/html/2607.06223#bib.bib26)\]formulates search capability learning as a two\-stage outcome\-based RL problem, and Smart\-Searcher\[[24](https://arxiv.org/html/2607.06223#bib.bib27)\]further strengthens dynamic knowledge acquisition by jointly encouraging the agent to leverage both internal parametric knowledge and external retrieved evidence\.

To alleviate the sparsity of outcome\-only rewards in multi\-turn search, several works move toward finer\-grained supervision over intermediate decisions\. StepSearch\[[31](https://arxiv.org/html/2607.06223#bib.bib5)\]introduces turn\-wise PPO\[[21](https://arxiv.org/html/2607.06223#bib.bib2)\]with richer intermediate rewards for evidence utilization\. GiGPO\[[7](https://arxiv.org/html/2607.06223#bib.bib6)\]proposes a RL framework with anchor\-based grouping, enabling fine\-grained credit assignment while maintaining the stability of group\-based optimization\. IGPO\[[28](https://arxiv.org/html/2607.06223#bib.bib7)\]further introduces information gain as an intrinsic turn\-level reward, measuring the marginal improvement in answer confidence from each interaction turn\.

Another direction extends rollout generation from a single chain to a branching search process\. Tree\-GRPO\[[11](https://arxiv.org/html/2607.06223#bib.bib10)\]exploits tree\-structured rollouts and shared prefixes to improve exploration efficiency under a fixed interaction budget, while ARPO\[[5](https://arxiv.org/html/2607.06223#bib.bib9)\]and AEPO\[[4](https://arxiv.org/html/2607.06223#bib.bib28)\]introduce entropy\-guided rollout to selectively branch at uncertain tool\-use turns\. These methods highlight the importance of leveraging intermediate states during agent training\.

Despite these advances, existing methods do not explicitly account for the actual utility of intermediate states when allocating rollout computation, and may therefore waste substantial budget on unpromising trajectories\. Our IGRPO addresses this issue by introducing an information gain\-based, budget\-aware rollout framework that prioritizes more informative states during sampling, while providing a clear target for policy optimization\.

## 3Preliminaries

### 3\.1Problem Setup

Let𝒟=\{\(q,a\)\}\\mathcal\{D\}=\\\{\(q,a\)\\\}denote a dataset of question\-answer pairs, whereqqis a question andaais the ground\-truth answer\. We consider a search environment equipped with an external retrieval tool, denoted by𝒮\\mathcal\{S\}, which accepts a textual query and returns a set of retrieved results, such as snippets and documents\. The goal of the agent is to solve questionqqby interacting with𝒮\\mathcal\{S\}under a limited search budget and finally producing an answera^\\hat\{a\}\. For each questionqq, the agent generates a search rollouto=\(τ1,τ2,…,τT\)o=\(\\tau\_\{1\},\\tau\_\{2\},\\dots,\\tau\_\{T\}\), whereTTdenotes the total number of turns and eachτi\\tau\_\{i\}is a particular interaction turn\. The last turnτT\\tau\_\{T\}is the answer turn, which outputs the final predictiona^\\hat\{a\}in a\[ans\]\[\\textsc\{ans\}\]step, while each preceding turn corresponds to one search turn\. In particular, fort<Tt<T, each turnτt\\tau\_\{t\}is defined as a triple consisting of\[think\]\[\\textsc\{think\}\],\[search\]\[\\textsc\{search\}\], and\[result\]\[\\textsc\{result\}\]steps\. The\[think\]\[\\textsc\{think\}\]step represents the intermediate reasoning based on the current search historyht−1h\_\{t\-1\}, which consists of the previous search\-result pairs collected up to turnt−1t\-1\. The\[search\]\[\\textsc\{search\}\]step issues a textual retrieval query to the external search tool𝒮\\mathcal\{S\}\. The\[result\]\[\\textsc\{result\}\]step then returns the retrieved evidence from𝒮\\mathcal\{S\}\. We then define the reward of rolloutooasR​\(o\)=𝕀​\[a^=a\]R\(o\)=\\mathbb\{I\}\[\\hat\{a\}=a\], where𝕀​\[⋅\]\\mathbb\{I\}\[\\cdot\]is the indicator function\. The objective is to maximize the average reward of sampled search rollouts\.

### 3\.2Group\-based Reinforcement Learning Pipeline

A representative method for training search agents is Group Relative Policy Optimization \(GRPO\)\[[22](https://arxiv.org/html/2607.06223#bib.bib1)\], where multiple candidate rollouts are sampled for the same question and optimized according to their relative outcome quality\. To align the notation with our proposed tree\-structured IGRPO formulation, we describe GRPO from a tree perspective\. In fact, the rollout space induced by the agent naturally forms a search tree: each partial interaction history corresponds to a node, each interaction turn corresponds to an edge that expands the current node, and each leaf node corresponds to an answer node that outputs the final prediction\. Under this view, a complete rollout is simply a root\-to\-leaf path in the search tree\. Formally, given an actor modelπθ\\pi\_\{\\theta\}, for each question\-answer pair\(q,a\)∼𝒟\(q,a\)\\sim\\mathcal\{D\}, GRPO samples a group ofNNcomplete rollouts\{oi\}i=1N∼πθold\(⋅∣q\)\\\{o\_\{i\}\\\}\_\{i=1\}^\{N\}\\sim\\pi\_\{\\theta\_\{\\mathrm\{old\}\}\}\(\\cdot\\mid q\), where each rolloutoi=\(τi,1,τi,2,…,τi,Ti\)o\_\{i\}=\(\\tau\_\{i,1\},\\tau\_\{i,2\},\\dots,\\tau\_\{i,T\_\{i\}\}\)is a root\-to\-leaf path in the search tree induced by the old policyπθold\\pi\_\{\\theta\_\{\\mathrm\{old\}\}\}, and different rollouts correspond to different paths whose interaction turns, i\.e\., tree edges, are non\-overlapping\. Correspondingly, lethi,th\_\{i,t\}denote the history node reached after the firstttturns of rolloutoio\_\{i\}, withhi,0=h0h\_\{i,0\}=h\_\{0\}being the root node that contains only the input questionqq\. Thus, each edgeτi,t\\tau\_\{i,t\}connects nodehi,t−1h\_\{i,t\-1\}tohi,th\_\{i,t\}\. Then, the policy is optimized by reweighting the edge decisions along each path according to the group relative advantage:

𝒥GRPO​\(θ\)\\displaystyle\\mathcal\{J\}\_\{\\mathrm\{GRPO\}\}\(\\theta\)=𝔼\(q,a\)∼𝒟,\{oi\}∼πθold\(⋅∣q\)\[1N∑i=1N1\|oi\|∑t=1Ti∑k=1\|τi,t\|min\(ri,t,kA^i,\\displaystyle=\\mathbb\{E\}\_\{\(q,a\)\\sim\\mathcal\{D\},\\,\\\{o\_\{i\}\\\}\\sim\\pi\_\{\\theta\_\{\\mathrm\{old\}\}\}\(\\cdot\\mid q\)\}\\Bigg\[\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\frac\{1\}\{\|o\_\{i\}\|\}\\sum\_\{t=1\}^\{T\_\{i\}\}\\sum\_\{k=1\}^\{\|\\tau\_\{i,t\}\|\}\\min\\Bigg\(r\_\{i,t,k\}\\hat\{A\}\_\{i\},\\,\(1\)clip\(ri,t,k,1−ϵ,1\+ϵ\)A^i\)−α𝔻KL\(πθ∥πref\)\],\\displaystyle\\mathrm\{clip\}\\Big\(r\_\{i,t,k\},1\-\\epsilon,1\+\\epsilon\\Big\)\\hat\{A\}\_\{i\}\\Bigg\)\\,\-\\alpha\\,\\mathbb\{D\}\_\{\\mathrm\{KL\}\}\(\\pi\_\{\\theta\}\\\|\\pi\_\{\\mathrm\{ref\}\}\)\\Bigg\],whereri,t,k=πθ​\(τi,t,k∣hi,t−1,τi,t,<k\)πθold\(τi,t,k∣hi,t−1,τi,t,<k\)\)r\_\{i,t,k\}=\\frac\{\\pi\_\{\\theta\}\(\\tau\_\{i,t,k\}\\mid h\_\{i,t\-1\},\\tau\_\{i,t,<k\}\)\}\{\\pi\_\{\\theta\_\{\\mathrm\{old\}\}\}\(\\tau\_\{i,t,k\}\\mid h\_\{i,t\-1\},\\tau\_\{i,t,<k\}\)\)\}is the importance ratio, andA^i=R​\(oi\)−mean​\(R​\(o1\),…,R​\(oN\)\)std​\(R​\(o1\),…,R​\(oN\)\)\\hat\{A\}\_\{i\}=\\frac\{R\(o\_\{i\}\)\-\\mathrm\{mean\}\\left\(R\(o\_\{1\}\),\\dots,R\(o\_\{N\}\)\\right\)\}\{\\mathrm\{std\}\\left\(R\(o\_\{1\}\),\\dots,R\(o\_\{N\}\)\\right\)\}is the normalized group relative advantage of rolloutoio\_\{i\}\.ϵ\\epsilonis the PPO\-style\[[21](https://arxiv.org/html/2607.06223#bib.bib2)\]clipping parameter, andα\\alphacontrols the KL penalty with respect to the reference policyπref\\pi\_\{\\mathrm\{ref\}\}\. We optimize the policy only over decision tokens produced by the agent, e\.g\.,\[think\]\[\\textsc\{think\}\]steps,\[search\]\[\\textsc\{search\}\]steps, whereas environment returned tokens are masked out and do not contribute to the gradient\. By maximizing the surrogate objective \([1](https://arxiv.org/html/2607.06223#S3.E1)\), GRPO effectively performs policy optimization toward the following KL\-regularized expected\-reward objective:

maxπθ⁡𝔼\(q,a\)∼𝒟​\[𝔼o∼πθ\(⋅∣q\)​\[R​\(o\)\]\]−α​𝔻KL​\(πθ∥πref\)\.\\max\_\{\\pi\_\{\\theta\}\}\\;\\mathbb\{E\}\_\{\(q,a\)\\sim\\mathcal\{D\}\}\\left\[\\mathbb\{E\}\_\{o\\sim\\pi\_\{\\theta\}\(\\cdot\\mid q\)\}\[R\(o\)\]\\right\]\-\\alpha\\,\\mathbb\{D\}\_\{\\mathrm\{KL\}\}\(\\pi\_\{\\theta\}\\\|\\pi\_\{\\mathrm\{ref\}\}\)\.\(2\)

## 4Methodology

![Refer to caption](https://arxiv.org/html/2607.06223v1/figures/pipeline.png)Figure 2:Overview of IGRPO\.Left:During rollout, the expansion budget is adaptively allocated according to node\-level informativeness, so that more informative nodes are expanded with higher probability, thereby inducing a distributionμθ\\mu\_\{\\theta\}that biases sampling toward more promising trajectories\.Right:the expansion process between tree\-level 1 and tree\-level 2 is governed by an informativeness\-aware strategy, where each active node is selected for expansion with probabilityp​\(⋅\)∝exp⁡\(γ​val​\(⋅\)\)p\(\\cdot\)\\propto\\exp\(\\gamma\\,\\text\{val\}\(\\cdot\)\)\.In this section, we describe our methodology\. Section[4\.1](https://arxiv.org/html/2607.06223#S4.SS1)introduces the information gain\-based tree\-structured rollout framework\. Section[4\.2](https://arxiv.org/html/2607.06223#S4.SS2)then provides the theoretical analysis of the induced limiting distribution, and further derives the corresponding policy optimization objective\. An overview of the overall pipeline is illustrated in Fig\.[2](https://arxiv.org/html/2607.06223#S4.F2)\.

### 4\.1Information Gain\-based Tree\-Structured Rollout Framework

![Refer to caption](https://arxiv.org/html/2607.06223v1/figures/pre.png)Figure 3:Average cumulative information gain at different trajectory turns across IGPO training steps\. Blue and red denote successful and failed trajectory groups, respectively, and color intensity corresponds to the trajectory turn\.#### Node\-level Information Gain\.

To instantiate the idea of budget\-aware tree expansion, we first require a criterion for assessing how promising each intermediate node is\. We employ information gain \(IG\)\-derived value as a scoring signal for intermediate search nodes, a criterion further supported by a preliminary empirical observation\. Specifically, during IGPO\[[28](https://arxiv.org/html/2607.06223#bib.bib7)\]training, we compare the average cumulative information gain of sampled trajectories that eventually answer the question correctly with those that fail\. As shown in Fig\.[3](https://arxiv.org/html/2607.06223#S4.F3), the gap between the two groups is substantial: successful trajectories consistently exhibit much larger average information gain\. This suggests that informativeness can serve as an effective indicator of whether the current search node is promising, even before the final outcome is observed\.

We now define the information gain\. For an intermediate history nodehh, we first define its answer score under the current policyπθ\\pi\_\{\\theta\}as the likelihood of the ground\-truth answer conditioned onhh:

sθ​\(h;a\)=πθ​\(a∣h\)=exp⁡\(1L​∑j=1Llog⁡πθ​\(aj∣h,a<j\)\),s\_\{\\theta\}\(h;a\)=\\pi\_\{\\theta\}\(a\\mid h\)=\\exp\{\\big\(\\frac\{1\}\{L\}\\sum\_\{j=1\}^\{L\}\\log\\pi\_\{\\theta\}\(a\_\{j\}\\mid h,a\_\{<j\}\)\\big\)\},\(3\)wherea=\(a1,…,aL\)a=\(a\_\{1\},\\dots,a\_\{L\}\)denotes the ground\-truth answer tokens\. Letparent​\(h\)\\mathrm\{parent\}\(h\)denote the parent node ofhhin the search tree\. We then define the information gain of an intermediate nodehhas the marginal improvement in answer score induced by expanding from its parent to the current node:

IG​\(h\)=sθ​\(h;a\)−sθ​\(parent​\(h\);a\);\\mathrm\{IG\}\(h\)=s\_\{\\theta\}\(h;a\)\-s\_\{\\theta\}\(\\mathrm\{parent\}\(h\);a\);\(4\)while we directly setIG​\(h0\)=sθ​\(h0;a\)\\mathrm\{IG\}\(h\_\{0\}\)=s\_\{\\theta\}\(h\_\{0\};a\)for the root node\. In this sense, the answer score can be viewed as a cumulative information gain signal along the path from the root to the current node, and the difference between two nodes’ answer scores reflects the difference in cumulative information gain accumulated after they branch from their lowest common ancestor\. Following previous works\[[12](https://arxiv.org/html/2607.06223#bib.bib3),[28](https://arxiv.org/html/2607.06223#bib.bib7)\], the ground\-truth answeraais wrapped in the same schema as a predicted answer to ensure consistency with rollout formatting, e\.g\.,<think\>Now there’s enough information to answer\.</think\><answer\>Ground Truthaa</answer\>\. This allows the answer score to be computed efficiently, without any further sampling\.

#### Rollout Framework\.

We next utilize information gain to construct rollout trajectories under a fixed search budget\. For each questionqq, we initialize a search tree with a root history nodeh0h\_\{0\}, which contains only the questionqq, and define the initial active node set as𝒜0=\{h0\}\\mathcal\{A\}\_\{0\}=\\\{h\_\{0\}\\\}, where an active node refers to an intermediate node that remains eligible for further expansion\.

At theii\-th expansion stage, let𝒜i\\mathcal\{A\}\_\{i\}denote the current set of active nodes\. Instead of allocating rollout budget uniformly across all active nodes, we distribute it according to their relative informativeness\. Concretely, for each nodeh∈𝒜ih\\in\\mathcal\{A\}\_\{i\}, we assign an expansion probability

pi​\(h\)=exp⁡\(γ​val​\(h\)\)∑h′∈𝒜iexp⁡\(γ​val​\(h′\)\),p\_\{i\}\(h\)=\\frac\{\\exp\\\!\\big\(\\gamma\\,\\mathrm\{val\}\(h\)\\big\)\}\{\\sum\\limits\_\{h^\{\\prime\}\\in\\mathcal\{A\}\_\{i\}\}\\exp\\\!\\big\(\\gamma\\,\\mathrm\{val\}\(h^\{\\prime\}\)\\big\)\},\(5\)whereval​\(⋅\)\\mathrm\{val\(\\cdot\)\}can be any IG\-derived signal, andγ\\gammais a temperature parameter controlling how strongly the allocation favors nodes with larger values\. Given a stage budgetBiB\_\{i\}, we independently sampleBiB\_\{i\}active nodes from𝒜i\\mathcal\{A\}\_\{i\}according to the allocation probability in \([5](https://arxiv.org/html/2607.06223#S4.E5)\), and expand each selected node under the frozen rollout policy\. The resulting intermediate nodes form the next active set𝒜i\+1\\mathcal\{A\}\_\{i\+1\}, while terminal nodes receive rewards according to their final predicted answers and are then recorded as completed rollout endpoints\. This process is repeated until the active set becomes empty or the maximum interaction turn is reached\.

A key distinction of our rollout framework is that branching is not determined by hard thresholding\. Instead, expansion is governed by a probabilistic allocation, which softly biases computation toward nodes with higher informativeness\. As a result, trajectories containing more informative intermediate nodes are sampled with higher probability, thereby inducing a non\-uniform rollout distribution biased by informativeness\. We analyze the limiting distribution and its properties in the next subsection\.

### 4\.2Theoretical Analysis and Policy Objective

According to the rollout procedure described above, we first characterize the distribution of sampled trajectories induced by our information gain\-based expansion strategy\. Intuitively, since the expansion budget at each layer is allocated probabilistically according to node\-level informativeness, trajectories passing through more informative intermediate nodes are expanded more frequently and therefore appear with higher probability in the final sample set\. The following theorem formalizes the limiting trajectory distribution when the per\-layer budget is sufficiently large\. Without loss of generality, we continue rolling out even after an answer has been produced\. As a result, every trajectory is padded to the same maximum interaction lengthTT\. Then, the limiting rollout distribution can be viewed as an exponentially tilted version of the original policy\-induced trajectory distribution\. Detailed proofs are presented in Appendix[A\.1](https://arxiv.org/html/2607.06223#A1.SS1)\.

###### Theorem 1\(Limiting trajectory distribution induced by IG\-based rollout\)\.

Consider the following tree\-structured rollout process\. For each questionqq, the process starts from the root history nodeh0=qh\_\{0\}=qand initializes the active set as𝒜0=\{h0\}\\mathcal\{A\}\_\{0\}=\\\{h\_\{0\}\\\}\. At thett\-th expansion stage\(0≤t<T\)\(0\\leq t<T\), each nodeh∈𝒜th\\in\\mathcal\{A\}\_\{t\}is assigned the expansion probability

pt​\(h\)=exp⁡\(γ​val​\(h\)\)∑h′∈𝒜texp⁡\(γ​val​\(h′\)\),p\_\{t\}\(h\)=\\frac\{\\exp\\\!\\big\(\\gamma\\,\\mathrm\{val\}\(h\)\\big\)\}\{\\sum\_\{h^\{\\prime\}\\in\\mathcal\{A\}\_\{t\}\}\\exp\\\!\\big\(\\gamma\\,\\mathrm\{val\}\(h^\{\\prime\}\)\\big\)\},\(6\)whereval​\(⋅\)\\mathrm\{val\}\(\\cdot\)denotes the informativeness of a history node\. Given the stage budgetBtB\_\{t\}, the process independently samplesBtB\_\{t\}nodes from𝒜t\\mathcal\{A\}\_\{t\}according topt​\(⋅\)p\_\{t\}\(\\cdot\), expands each selected node under the policyπθ\\pi\_\{\\theta\}, and adds the resulting child nodes to𝒜t\+1\\mathcal\{A\}\_\{t\+1\}\. For convenience, define the cumulative value of a trajectoryo=\(h0→τ1h1→τ2⋯→τThT\)o=\(h\_\{0\}\\xrightarrow\{\\tau\_\{1\}\}h\_\{1\}\\xrightarrow\{\\tau\_\{2\}\}\\cdots\\xrightarrow\{\\tau\_\{T\}\}h\_\{T\}\)asV​\(o\):=∑t=1T−1val​\(ht\)V\(o\):=\\sum\_\{t=1\}^\{T\-1\}\\mathrm\{val\}\(h\_\{t\}\)\. Letπθ​\(o\)=∏t=1Tπθ​\(τt∣ht−1\)\\pi\_\{\\theta\}\(o\)=\\prod\_\{t=1\}^\{T\}\\pi\_\{\\theta\}\(\\tau\_\{t\}\\mid h\_\{t\-1\}\)denote the probability of trajectoryoounder the original policy\. IfBt→∞B\_\{t\}\\to\\inftyat every layer, then the empirical distribution of sampled complete trajectories converges to

μθ​\(o\)∝πθ​\(o\)​exp⁡\(γ​V​\(o\)\)\.\\mu\_\{\\theta\}\(o\)\\propto\\pi\_\{\\theta\}\(o\)\\exp\\bigl\(\\gamma V\(o\)\\bigr\)\.\(7\)

This result shows that our rollout mechanism does not sample trajectories directly from the original policy distributionπθ\\pi\_\{\\theta\}\. Instead, it induces a reweighted distribution that favors trajectories with larger informativeness values\. In other words, informativeness acts as an intrinsic bias on the rollout process, encouraging the policy to allocate more computation to trajectories that are expected to be more informative during search\. The following analysis further justifies such an intrinsic bias\. In particular, we show that the induced distributionμθ\\mu\_\{\\theta\}is in fact the optimizer of a variational problem\.

###### Theorem 2\(Variational characterization of the induced trajectory distribution\)\.

Letπθ\\pi\_\{\\theta\}denote the original policy\-induced trajectory distribution, and letV​\(o\)V\(o\)denote the cumulative information value of trajectoryoo\. Consider the following variational objective over trajectory distributionsμ\\mu:

maxμ⁡𝔼o∼μ​\[V​\(o\)\]−1γ​𝔻KL​\(μ∥πθ\)\.\\max\_\{\\mu\}\\;\\mathbb\{E\}\_\{o\\sim\\mu\}\\\!\\left\[V\(o\)\\right\]\-\\frac\{1\}\{\\gamma\}\\,\\mathbb\{D\}\_\{\\mathrm\{KL\}\}\\\!\\left\(\\mu\\,\\\|\\,\\pi\_\{\\theta\}\\right\)\.\(8\)Then the unique optimizer of \([8](https://arxiv.org/html/2607.06223#S4.E8)\) is the induced trajectoryμθ​\(o\)∝πθ​\(o\)​exp⁡\(γ​V​\(o\)\)\.\\mu\_\{\\theta\}\(o\)\\propto\\pi\_\{\\theta\}\(o\)\\exp\\bigl\(\\gamma\\,V\(o\)\\bigr\)\.

Theorem[2](https://arxiv.org/html/2607.06223#Thmtheorem2)\(see Appendix[A\.2](https://arxiv.org/html/2607.06223#A1.SS2)\) further provides a practical bridge to the GRPO objective in \([2](https://arxiv.org/html/2607.06223#S3.E2)\)\. According to our preliminary observation in Fig\.[3](https://arxiv.org/html/2607.06223#S4.F3), the trajectory rewardR​\(o\)R\(o\)is strongly positively correlated with the cumulative valueV​\(o\)V\(o\)\. Therefore, as long as policy optimization is performed in a regime where the updated policy remains at a comparable distance from the reference policyπref\\pi\_\{\\mathrm\{ref\}\}, the induced distributionμθ\\mu\_\{\\theta\}can be viewed as a reward\-aligned teacher that provides a useful policy improvement direction for the reward\-based objective\. Accordingly, we obtain a clear optimization target:the distributionμθ\\mu\_\{\\theta\}serves as a teacher distribution, specifying a policy improvement direction for the current policyπθ\\pi\_\{\\theta\}\. Based on this view, we use the induced distribution as an informative sampling distribution for policy optimization\. At each training iteration, we freeze the current policy asπθold\\pi\_\{\\theta\_\{\\mathrm\{old\}\}\}and construct the teacher sampler induced by the information gain\-based rollout process in Section[4\.1](https://arxiv.org/html/2607.06223#S4.SS1)\. This sampler approximately draws trajectories fromμθold\\mu\_\{\\theta\_\{\\mathrm\{old\}\}\}under finite rollout budgets, thereby biasing the collected training samples toward trajectories with more informative intermediate states\. Given the sampled trajectories for each question, we then apply a group\-based policy optimization objective to updateπθ\\pi\_\{\\theta\}, where relative advantages within the group provide the optimization signal and a KL penalty toπref\\pi\_\{\\mathrm\{ref\}\}is used for stable training\.

#### Surrogate Objective\.

We now turn to the optimization objective induced by our information gain\-based rollout\. For each questionqq, let\{oi\}i=1N\\\{o\_\{i\}\\\}\_\{i=1\}^\{N\}denote the set of all sampled root\-to\-leaf trajectories, whereNNis the number of leaf nodes and each pathoio\_\{i\}is associated with a rewardR​\(oi\)R\(o\_\{i\}\)\. We define the following IGRPO objective:

𝒥IGRPO​\(θ\)\\displaystyle\\mathcal\{J\}\_\{\\mathrm\{IGRPO\}\}\(\\theta\)=𝔼\(q,a\)∼𝒟,\{oi\}∼μθold\(⋅∣q\)\[1N∑i=1N1\|oi\|∑t=1Ti∑k=1\|τi,t\|min\(ri,t,kA^i,\\displaystyle=\\mathbb\{E\}\_\{\(q,a\)\\sim\\mathcal\{D\},\\,\\\{o\_\{i\}\\\}\\sim\\mu\_\{\\theta\_\{\\mathrm\{old\}\}\}\(\\cdot\\mid q\)\}\\Bigg\[\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\frac\{1\}\{\|o\_\{i\}\|\}\\sum\_\{t=1\}^\{T\_\{i\}\}\\sum\_\{k=1\}^\{\|\\tau\_\{i,t\}\|\}\\min\\Bigg\(r\_\{i,t,k\}\\hat\{A\}\_\{i\},\\,\(9\)clip\(ri,t,k,1−ϵ,1\+ϵ\)A^i\)−β𝔻KL\(πθ∥πref\)\],\\displaystyle\\mathrm\{clip\}\\Big\(r\_\{i,t,k\},1\-\\epsilon,1\+\\epsilon\\Big\)\\hat\{A\}\_\{i\}\\Bigg\)\\,\-\\beta\\,\\mathbb\{D\}\_\{\\mathrm\{KL\}\}\(\\pi\_\{\\theta\}\\\|\\pi\_\{\\mathrm\{ref\}\}\)\\Bigg\],whereri,t,k=πθ​\(τi,t,k∣hi,t−1,τi,t,<k\)πθold\(τi,t,k∣hi,t−1,τi,t,<k\)\)r\_\{i,t,k\}=\\frac\{\\pi\_\{\\theta\}\(\\tau\_\{i,t,k\}\\mid h\_\{i,t\-1\},\\tau\_\{i,t,<k\}\)\}\{\\pi\_\{\\theta\_\{\\mathrm\{old\}\}\}\(\\tau\_\{i,t,k\}\\mid h\_\{i,t\-1\},\\tau\_\{i,t,<k\}\)\)\}is the importance ratio, andA^i=R​\(oi\)−mean​\(R​\(o1\),…,R​\(oN\)\)std​\(R​\(o1\),…,R​\(oN\)\)\\hat\{A\}\_\{i\}=\\frac\{R\(o\_\{i\}\)\-\\mathrm\{mean\}\\left\(R\(o\_\{1\}\),\\dots,R\(o\_\{N\}\)\\right\)\}\{\\mathrm\{std\}\\left\(R\(o\_\{1\}\),\\dots,R\(o\_\{N\}\)\\right\)\}is the normalized group relative advantage of tree pathoio\_\{i\}\.μθold\\mu\_\{\\theta\_\{\\mathrm\{old\}\}\}represents the information gain\-based sampling process in Section[4\.1](https://arxiv.org/html/2607.06223#S4.SS1)\. For paths that terminate due to the absence of expandable nodes, we set their rewards according to the cumulative information gain along the path\. For the node\-level informativeness scoring function, we instantiateval​\(⋅\)\\mathrm\{val\}\(\\cdot\)as the average of the cumulative information gain and the instantaneous information gain:

val​\(h\)=sθ​\(h;a\)\+IG​\(h\)2\.\\mathrm\{val\}\(h\)=\\frac\{s\_\{\\theta\}\(h;a\)\+\\mathrm\{IG\}\(h\)\}\{2\}\.\(10\)This captures both the current promise of the node and the marginal progress made by the latest transition, encouraging the rollout selector to prioritize nodes that are both answerable and still improving\. The complete IGRPO workflow is in Appendix[B](https://arxiv.org/html/2607.06223#A2)\.

## 5Experiments

In this section, we present empirical evaluations of IGRPO on challenging search\-augmented QA tasks\. Specifically, we aim to demonstrate: \(1\) the strong ability of IGRPO in training long\-horizon search agents; \(2\) the importance of maintaining sufficient entropy during policy optimization; \(3\) the ablation study on the rollout allocation temperatureγ\\gamma\.

### 5\.1Experiment Setup

#### Benchmarks & Metrics\.

To evaluate the effectiveness of our proposed IGRPO, we conduct experiments on seven challenging search\-augmented QA benchmarks\. These benchmarks include both single\-hop and multi\-hop question answering tasks\. Specifically, the single\-hop setting includes NQ\[[14](https://arxiv.org/html/2607.06223#bib.bib11)\], TriviaQA\[[13](https://arxiv.org/html/2607.06223#bib.bib12)\], and PopQA\[[16](https://arxiv.org/html/2607.06223#bib.bib13)\], while the more challenging multi\-hop setting includes HotpotQA\[[33](https://arxiv.org/html/2607.06223#bib.bib14)\], 2Wiki\[[9](https://arxiv.org/html/2607.06223#bib.bib15)\], MusiQue\[[27](https://arxiv.org/html/2607.06223#bib.bib16)\], and Bamboogle\[[18](https://arxiv.org/html/2607.06223#bib.bib17)\], which require the model to perform multi\-step reasoning by integrating information across multiple pieces of evidence\. We use exact match \(EM\) as the evaluation metric, which measures whether the predicted answer exactly matches the reference answer after standard normalization\.

#### Baselines\.

We compare IGRPO against a diverse set of competitive baselines\. Our evaluation includes R1\-Instruct as the vanilla instruction\-tuned backbone, as well as Search\-R1\[[12](https://arxiv.org/html/2607.06223#bib.bib3)\]and ZeroSearch\[[25](https://arxiv.org/html/2607.06223#bib.bib4)\]as two chain\-based search RL methods with trajectory\-level optimization\. We further consider representative chain\-based methods with finer\-grained step\-level optimization, including StepSearch\[[31](https://arxiv.org/html/2607.06223#bib.bib5)\], GiGPO\[[7](https://arxiv.org/html/2607.06223#bib.bib6)\], and IGPO\[[28](https://arxiv.org/html/2607.06223#bib.bib7)\]\. In addition, we include the tree\-based baseline Tree\-GRPO\[[11](https://arxiv.org/html/2607.06223#bib.bib10)\], which extends group\-based policy optimization to tree\-structured rollouts\. Together, these baselines cover the main lines of recent progress in search\-augmented QA, ranging from search\-unaware instruction tuning to chain\-based and tree\-based policy optimization\.

#### Training details\.

All baselines are trained under the same experimental configuration\. We use Qwen2\.5\-3B/7B\-Instruct\[[32](https://arxiv.org/html/2607.06223#bib.bib18)\]as the base models\. The rollout group sizeNNfor all chain\-based baselines is set to 5\. For our tree\-based rollout, we set the per\-stage budgetBiB\_\{i\}to 5 for all stages to match the search budget of chain\-based methods\. Following Search\-R1, we use E5\[[29](https://arxiv.org/html/2607.06223#bib.bib19)\]as the retriever, and set the maximum number of interaction turns to 4\. All experiments are trained for 200 iterations\. More training details and hyperparameter configurations are provided in Appendix[C\.1](https://arxiv.org/html/2607.06223#A3.SS1)\.

### 5\.2Overall Performance

Table[1](https://arxiv.org/html/2607.06223#S5.T1)presents the main results on seven search\-augmented QA benchmarks\. Overall, IGRPO achieves superior average performance on both backbone scales, reaching 45\.4% on 3B and 48\.2% on 7B\. These results show that our information gain\-based rollout can consistently improve agent training across both single\-hop and multi\-hop tasks\. Compared with strong chain\-based methods, IGRPO provides additional gains by going beyond trajectory\-level or turn\-level credit assignment and explicitly reallocating rollout computation according to the informativeness of intermediate states\. Moreover, IGRPO also outperforms Tree\-GRPO, which exhibits unstable performance on multi\-hop datasets, indicating that simply introducing tree\-structured exploration is not sufficient\. The advantage of IGRPO comes from its clearer optimization target: the information gain\-based rollout induces a limiting teacher distribution, which guides the policy toward more informative search behaviors in a principled manner\. The improvement is especially pronounced on the 3B backbone, where IGRPO shows consistent advantages across most evaluation datasets and outperforms the strongest baseline by 3\.1% on average\. This suggests that smaller models benefit more from rollout guidance, since their initial search policies are less reliable and are more likely to spend computation on low\-value branches\. By evaluating intermediate nodes with informativeness, IGRPO helps the model focus on more promising search states, thereby providing stronger supervision during policy optimization\.

Table 1:Performance on seven search\-augmented QA tasks \(%\)\. The best results are highlighted inbold, and the runner\-up results areunderlined\.†\\daggerand⋆\\starindicate in\-domain and out\-of\-domain datasets, respectively\. Avg\. denotes the test\-size\-weighted average over the evaluation datasets\.TypeMethodSingle\-Hop QAMulti\-Hop QAAvg\.NQ†TriviaQA⋆PopQA⋆HotpotQA†2Wiki⋆MuSiQue⋆Bamboogle⋆Qwen2\.5\-3B\-InstructRL TrainingR1\-Instruct27\.053\.719\.923\.729\.27\.229\.329\.8Chain\-basedSearch\-R134\.154\.537\.832\.431\.910\.326\.437\.4Chain\-basedZeroSearch41\.457\.444\.827\.430\.09\.811\.139\.1Chain\-basedStepSearch–––34\.532\.017\.434\.4–Chain\-basedGiGPO42\.059\.542\.436\.937\.012\.664\.142\.3Chain\-basedIGPO40\.258\.143\.235\.734\.912\.364\.541\.4Tree\-basedTree\-GRPO44\.560\.443\.731\.131\.711\.928\.040\.8\\rowcolorgray\!15 Tree\-basedIGRPO45\.660\.947\.538\.940\.214\.165\.745\.4Qwen2\.5\-7B\-InstructRL TrainingR1\-Instruct21\.044\.917\.120\.827\.56\.019\.225\.8Chain\-basedSearch\-R139\.361\.039\.737\.040\.114\.636\.842\.5Chain\-basedZeroSearch43\.661\.851\.534\.635\.218\.427\.844\.8Chain\-basedStepSearch–––38\.636\.622\.640\.0–Chain\-basedGiGPO46\.464\.746\.141\.643\.618\.968\.947\.3Chain\-basedIGPO44\.060\.145\.442\.942\.516\.839\.945\.7Tree\-basedTree\-GRPO45\.662\.542\.839\.935\.617\.541\.643\.6\\rowcolorgray\!15 Tree\-basedIGRPO48\.064\.747\.044\.643\.820\.271\.848\.2

![Refer to caption](https://arxiv.org/html/2607.06223v1/figures/entropy_loss_comparison.png)Figure 4:Entropy loss during training on Qwen2\.5\-3B\-Instruct\.We further examine the training dynamics by comparing the entropy loss of different rollout strategies in Fig\.[4](https://arxiv.org/html/2607.06223#S5.F4)\. IGPO quickly drives the policy entropy to a very low level, suggesting that chain\-based optimization may prematurely concentrate on a narrow set of behaviors\. In contrast, Tree\-GRPO maintains high entropy throughout training, suggesting that random tree expansion increases exploration but also amplifies the model’s uncertainty, making it harder for the policy to converge toward stable search behaviors\. IGRPO exhibits a more balanced pattern: the entropy first decreases as the policy learns reliable search behaviors, and then marginally increases as information gain\-based expansion encourages broader exploration around promising intermediate states\. This trend supports our main intuition that IGRPO does not merely increase exploration, but reallocates exploration toward informative regions of the search space\.

### 5\.3Ablation Study

We examine the effect of the temperatureγ\\gammaused in the rollout allocation rule\. In IGRPO, the expansion probability of an active node is determined by its informativeness, soγ\\gammacontrols how strongly the rollout budget is biased toward more informative nodes\. A largerγ\\gammaplaces more probability mass on nodes with higher informativeness, thereby encouraging more aggressive exploitation of promising branches\. In contrast, a smallerγ\\gammayields a flatter allocation distribution and thus preserves broader exploration\. Therefore,γ\\gammadirectly governs the exploration–exploitation trade\-off in our budget\-aware tree rollout\.

![Refer to caption](https://arxiv.org/html/2607.06223v1/figures/ablation_radar.png)Figure 5:Ablation results\. The y\-axis shows success rate \(%\)\.Figure[5](https://arxiv.org/html/2607.06223#S5.F5)reports the results forγ∈\{0,1,5\}\\gamma\\in\\\{0,1,5\\\}\. Whenγ=0\\gamma=0, the information gain bias is removed and the expansion policy becomes agnostic to node quality, which weakens the benefits of adaptive budget allocation\. This variant obtains an overall score of 42\.2%, while increasing the temperature toγ=1\\gamma=1consistently improves performance and yields the best overall result of 45\.4%\. In particular,γ=1\\gamma=1achieves the strongest results on most datasets\. These gains indicate that moderately favoring more informative nodes helps the agent allocate rollout computation to more informative branches while still maintaining sufficient exploration\. When the temperature is further increased toγ=5\\gamma=5, the model still outperforms the unbiased variant on several datasets, but its overall score decreases to 44\.5%\. This suggests that overly concentrating the rollout budget on currently highly informative nodes can reduce exploration and make the search process less robust\. Nevertheless, stronger exploitation can still be beneficial in some cases\. Overall, these results show that information gain\-based allocation is crucial, while a moderate temperature value provides the best balance between prioritizing informative nodes and retaining sufficient exploration\. We provide additional results in Appendix[C\.2](https://arxiv.org/html/2607.06223#A3.SS2), together with case studies in Appendix[D](https://arxiv.org/html/2607.06223#A4)\.

## 6Conclusion and Limitations

In this work, we propose IGRPO, an information gain\-based budget\-aware tree rollout framework for search\-augmented policy optimization\. Our method addresses a key limitation of existing approaches, which often waste rollout budget on uninformative intermediate states due to the lack of principled utility\-aware exploration\. By introducing node\-level information value as the scoring signal, IGRPO adaptively allocates computation budget and prioritizes more informative nodes during expansion\. Consequently, the induced trajectory distribution becomes a reweighted version of the original policy distribution, favoring trajectories with larger cumulative information values\. We further provide a theoretical characterization of the limiting distribution, which yields a teacher optimization target\. Empirical results on seven search QA benchmarks demonstrate the effectiveness of our framework\.

A limitation of our method is that it relies on the information gain signal to assess intermediate nodes, which may restrict its direct applicability to tasks where such a signal is difficult to define\. Nevertheless, the framework itself is more general\. As long as an appropriate node\-level assessment criterion can be designed, the same budget\-aware tree rollout mechanism can be extended to other tasks\. Exploring alternative assessment signals remains an important direction for future work\.

## References

- \[1\]\(2024\)Back to basics: revisiting reinforce\-style optimization for learning from human feedback in llms\.InProceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 12248–12267\.Cited by:[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px1.p1.1)\.
- \[2\]T\. Brown, B\. Mann, N\. Ryder, M\. Subbiah, J\. D\. Kaplan, P\. Dhariwal, A\. Neelakantan, P\. Shyam, G\. Sastry, A\. Askell,et al\.\(2020\)Language models are few\-shot learners\.Advances in neural information processing systems33,pp\. 1877–1901\.Cited by:[§1](https://arxiv.org/html/2607.06223#S1.p1.1)\.
- \[3\]A\. Chowdhery, S\. Narang, J\. Devlin, M\. Bosma, G\. Mishra, A\. Roberts, P\. Barham, H\. W\. Chung, C\. Sutton, S\. Gehrmann,et al\.\(2023\)Palm: scaling language modeling with pathways\.Journal of machine learning research24\(240\),pp\. 1–113\.Cited by:[§1](https://arxiv.org/html/2607.06223#S1.p1.1)\.
- \[4\]G\. Dong, L\. Bao, Z\. Wang, K\. Zhao, X\. Li, J\. Jin, J\. Yang, H\. Mao, F\. Zhang, K\. Gai,et al\.\(2025\)Agentic entropy\-balanced policy optimization\.arXiv preprint arXiv:2510\.14545\.Cited by:[§1](https://arxiv.org/html/2607.06223#S1.p2.1),[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px2.p3.1)\.
- \[5\]G\. Dong, H\. Mao, K\. Ma, L\. Bao, Y\. Chen, Z\. Wang, Z\. Chen, J\. Du, H\. Wang, F\. Zhang,et al\.\(2025\)Agentic reinforced policy optimization\.arXiv preprint arXiv:2507\.19849\.Cited by:[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px2.p3.1)\.
- \[6\]M\. D\. Donsker and S\. S\. Varadhan\(1975\)Asymptotic evaluation of certain markov process expectations for large time, i\.Communications on pure and applied mathematics28\(1\),pp\. 1–47\.Cited by:[§A\.2](https://arxiv.org/html/2607.06223#A1.SS2.p1.2)\.
- \[7\]L\. Feng, Z\. Xue, T\. Liu, and B\. An\(2025\)Group\-in\-group policy optimization for llm agent training\.arXiv preprint arXiv:2505\.10978\.Cited by:[§C\.1](https://arxiv.org/html/2607.06223#A3.SS1.SSS0.Px1.p1.5),[§C\.1](https://arxiv.org/html/2607.06223#A3.SS1.SSS0.Px2.p1.4),[§1](https://arxiv.org/html/2607.06223#S1.p2.1),[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px2.p2.1),[§5\.1](https://arxiv.org/html/2607.06223#S5.SS1.SSS0.Px2.p1.1)\.
- \[8\]D\. Guo, D\. Yang, H\. Zhang, J\. Song, P\. Wang, Q\. Zhu, R\. Xu, R\. Zhang, S\. Ma, X\. Bi,et al\.\(2025\)Deepseek\-r1: incentivizing reasoning capability in llms via reinforcement learning\.arXiv preprint arXiv:2501\.12948\.Cited by:[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px1.p1.1)\.
- \[9\]X\. Ho, A\. D\. Nguyen, S\. Sugawara, and A\. Aizawa\(2020\)Constructing a multi\-hop qa dataset for comprehensive evaluation of reasoning steps\.InProceedings of the 28th International Conference on Computational Linguistics,pp\. 6609–6625\.Cited by:[§C\.1](https://arxiv.org/html/2607.06223#A3.SS1.SSS0.Px2.p1.4),[§5\.1](https://arxiv.org/html/2607.06223#S5.SS1.SSS0.Px1.p1.1)\.
- \[10\]Y\. Huang, Y\. Chen, H\. Zhang, K\. Li, H\. Zhou, M\. Fang, L\. Yang, X\. Li, L\. Shang, S\. Xu,et al\.\(2025\)Deep research agents: a systematic examination and roadmap\.arXiv preprint arXiv:2506\.18096\.Cited by:[§1](https://arxiv.org/html/2607.06223#S1.p1.1)\.
- \[11\]Y\. Ji, Z\. Ma, Y\. Wang, G\. Chen, X\. Chu, and L\. Wu\(2025\)Tree search for llm agent reinforcement learning\.arXiv preprint arXiv:2509\.21240\.Cited by:[§C\.1](https://arxiv.org/html/2607.06223#A3.SS1.SSS0.Px2.p1.4),[§1](https://arxiv.org/html/2607.06223#S1.p2.1),[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px2.p3.1),[§5\.1](https://arxiv.org/html/2607.06223#S5.SS1.SSS0.Px2.p1.1)\.
- \[12\]B\. Jin, H\. Zeng, Z\. Yue, J\. Yoon, S\. Arik, D\. Wang, H\. Zamani, and J\. Han\(2025\)Search\-r1: training llms to reason and leverage search engines with reinforcement learning\.arXiv preprint arXiv:2503\.09516\.Cited by:[§C\.1](https://arxiv.org/html/2607.06223#A3.SS1.SSS0.Px2.p1.4),[§1](https://arxiv.org/html/2607.06223#S1.p1.1),[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px2.p1.1),[§4\.1](https://arxiv.org/html/2607.06223#S4.SS1.SSS0.Px1.p2.10),[§5\.1](https://arxiv.org/html/2607.06223#S5.SS1.SSS0.Px2.p1.1)\.
- \[13\]M\. Joshi, E\. Choi, D\. S\. Weld, and L\. Zettlemoyer\(2017\)Triviaqa: a large scale distantly supervised challenge dataset for reading comprehension\.InProceedings of the 55th Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 1601–1611\.Cited by:[§5\.1](https://arxiv.org/html/2607.06223#S5.SS1.SSS0.Px1.p1.1)\.
- \[14\]T\. Kwiatkowski, J\. Palomaki, O\. Redfield, M\. Collins, A\. Parikh, C\. Alberti, D\. Epstein, I\. Polosukhin, J\. Devlin, K\. Lee,et al\.\(2019\)Natural questions: a benchmark for question answering research\.Transactions of the Association for Computational Linguistics7,pp\. 453–466\.Cited by:[§C\.1](https://arxiv.org/html/2607.06223#A3.SS1.SSS0.Px1.p1.5),[§5\.1](https://arxiv.org/html/2607.06223#S5.SS1.SSS0.Px1.p1.1)\.
- \[15\]X\. Li, G\. Dong, J\. Jin, Y\. Zhang, Y\. Zhou, Y\. Zhu, P\. Zhang, and Z\. Dou\(2025\)Search\-o1: agentic search\-enhanced large reasoning models\.InProceedings of the 2025 Conference on Empirical Methods in Natural Language Processing,pp\. 5420–5438\.Cited by:[§1](https://arxiv.org/html/2607.06223#S1.p1.1)\.
- \[16\]A\. Mallen, A\. Asai, V\. Zhong, R\. Das, D\. Khashabi, and H\. Hajishirzi\(2023\)When not to trust language models: investigating effectiveness of parametric and non\-parametric memories\.InProceedings of the 61st annual meeting of the association for computational linguistics \(volume 1: Long papers\),pp\. 9802–9822\.Cited by:[§C\.1](https://arxiv.org/html/2607.06223#A3.SS1.SSS0.Px2.p1.4),[§5\.1](https://arxiv.org/html/2607.06223#S5.SS1.SSS0.Px1.p1.1)\.
- \[17\]L\. Ouyang, J\. Wu, X\. Jiang, D\. Almeida, C\. Wainwright, P\. Mishkin, C\. Zhang, S\. Agarwal, K\. Slama, A\. Ray,et al\.\(2022\)Training language models to follow instructions with human feedback\.Advances in neural information processing systems35,pp\. 27730–27744\.Cited by:[§1](https://arxiv.org/html/2607.06223#S1.p2.1),[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px1.p1.1)\.
- \[18\]O\. Press, M\. Zhang, S\. Min, L\. Schmidt, N\. A\. Smith, and M\. Lewis\(2023\)Measuring and narrowing the compositionality gap in language models\.InFindings of the Association for Computational Linguistics: EMNLP 2023,pp\. 5687–5711\.Cited by:[§C\.1](https://arxiv.org/html/2607.06223#A3.SS1.SSS0.Px2.p1.4),[§5\.1](https://arxiv.org/html/2607.06223#S5.SS1.SSS0.Px1.p1.1)\.
- \[19\]C\. Qian, E\. C\. Acikgoz, Q\. He, H\. Wang, X\. Chen, D\. Hakkani\-Tür, G\. Tur, and H\. Ji\(2025\)Toolrl: reward is all tool learning needs\.arXiv preprint arXiv:2504\.13958\.Cited by:[§1](https://arxiv.org/html/2607.06223#S1.p2.1)\.
- \[20\]T\. Schick, J\. Dwivedi\-Yu, R\. Dessì, R\. Raileanu, M\. Lomeli, E\. Hambro, L\. Zettlemoyer, N\. Cancedda, and T\. Scialom\(2023\)Toolformer: language models can teach themselves to use tools\.Advances in neural information processing systems36,pp\. 68539–68551\.Cited by:[§1](https://arxiv.org/html/2607.06223#S1.p1.1)\.
- \[21\]J\. Schulman, F\. Wolski, P\. Dhariwal, A\. Radford, and O\. Klimov\(2017\)Proximal policy optimization algorithms\.arXiv preprint arXiv:1707\.06347\.Cited by:[§1](https://arxiv.org/html/2607.06223#S1.p2.1),[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px2.p2.1),[§3\.2](https://arxiv.org/html/2607.06223#S3.SS2.p1.22)\.
- \[22\]Z\. Shao, P\. Wang, Q\. Zhu, R\. Xu, J\. Song, X\. Bi, H\. Zhang, M\. Zhang, Y\. Li,et al\.\(2024\)Deepseekmath: pushing the limits of mathematical reasoning in open language models\.arXiv preprint arXiv:2402\.03300\.Cited by:[§1](https://arxiv.org/html/2607.06223#S1.p2.1),[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px1.p1.1),[§3\.2](https://arxiv.org/html/2607.06223#S3.SS2.p1.14)\.
- \[23\]H\. Song, J\. Jiang, Y\. Min, J\. Chen, Z\. Chen, W\. X\. Zhao, L\. Fang, and J\. Wen\(2025\)R1\-searcher: incentivizing the search capability in llms via reinforcement learning\.arXiv preprint arXiv:2503\.05592\.Cited by:[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px2.p1.1)\.
- \[24\]H\. Song, J\. Jiang, W\. Tian, Z\. Chen, Y\. Wu, J\. Zhao, Y\. Min, W\. X\. Zhao, L\. Fang, and J\. Wen\(2025\)Smart\-searcher: incentivizing the dynamic knowledge acquisition of llms via reinforcement learning\.InFindings of the Association for Computational Linguistics: EMNLP 2025,pp\. 13572–13586\.Cited by:[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px2.p1.1)\.
- \[25\]H\. Sun, Z\. Qiao, J\. Guo, X\. Fan, Y\. Hou, Y\. Jiang, P\. Xie, Y\. Zhang, F\. Huang, and J\. Zhou\(2025\)Zerosearch: incentivize the search capability of llms without searching\.arXiv preprint arXiv:2505\.04588\.Cited by:[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px2.p1.1),[§5\.1](https://arxiv.org/html/2607.06223#S5.SS1.SSS0.Px2.p1.1)\.
- \[26\]H\. Touvron, T\. Lavril, G\. Izacard, X\. Martinet, M\. Lachaux, T\. Lacroix, B\. Rozière, N\. Goyal, E\. Hambro, F\. Azhar,et al\.\(2023\)Llama: open and efficient foundation language models\. arxiv 2023\.arXiv preprint arXiv:2302\.1397110\.Cited by:[§1](https://arxiv.org/html/2607.06223#S1.p1.1)\.
- \[27\]H\. Trivedi, N\. Balasubramanian, T\. Khot, and A\. Sabharwal\(2022\)MuSiQue: multihop questions via single\-hop question composition\.Transactions of the Association for Computational Linguistics10,pp\. 539–554\.Cited by:[§C\.2](https://arxiv.org/html/2607.06223#A3.SS2.SSS0.Px3.p1.1),[§5\.1](https://arxiv.org/html/2607.06223#S5.SS1.SSS0.Px1.p1.1)\.
- \[28\]G\. Wang, S\. Dai, G\. Ye, Z\. Gan, W\. Yao, Y\. Deng, X\. Wu, and Z\. Ying\(2025\)Information gain\-based policy optimization: a simple and effective approach for multi\-turn llm agents\.arXiv preprint arXiv:2510\.14967\.Cited by:[§C\.1](https://arxiv.org/html/2607.06223#A3.SS1.SSS0.Px2.p1.4),[§1](https://arxiv.org/html/2607.06223#S1.p2.1),[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px2.p2.1),[§4\.1](https://arxiv.org/html/2607.06223#S4.SS1.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2607.06223#S4.SS1.SSS0.Px1.p2.10),[§5\.1](https://arxiv.org/html/2607.06223#S5.SS1.SSS0.Px2.p1.1)\.
- \[29\]L\. Wang, N\. Yang, X\. Huang, B\. Jiao, L\. Yang, D\. Jiang, R\. Majumder, and F\. Wei\(2022\)Text embeddings by weakly\-supervised contrastive pre\-training\.arXiv preprint arXiv:2212\.03533\.Cited by:[§C\.1](https://arxiv.org/html/2607.06223#A3.SS1.SSS0.Px1.p1.5),[§5\.1](https://arxiv.org/html/2607.06223#S5.SS1.SSS0.Px3.p1.2)\.
- \[30\]X\. Wang, Z\. Wang, X\. Gao, F\. Zhang, Y\. Wu, Z\. Xu, T\. Shi, Z\. Wang, S\. Li, Q\. Qian,et al\.\(2024\)Searching for best practices in retrieval\-augmented generation\.InProceedings of the 2024 Conference on Empirical Methods in Natural Language Processing,pp\. 17716–17736\.Cited by:[§1](https://arxiv.org/html/2607.06223#S1.p1.1)\.
- \[31\]Z\. Wang, X\. Zheng, K\. An, C\. Ouyang, J\. Cai, Y\. Wang, and Y\. Wu\(2025\)Stepsearch: igniting llms search ability via step\-wise proximal policy optimization\.arXiv preprint arXiv:2505\.15107\.Cited by:[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px2.p2.1),[§5\.1](https://arxiv.org/html/2607.06223#S5.SS1.SSS0.Px2.p1.1)\.
- \[32\]A\. Yang, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu, C\. Li, D\. Liu, F\. Huang, H\. Wei,et al\.\(2024\)Qwen2\. 5 technical report\.arXiv e\-prints,pp\. arXiv–2412\.Cited by:[§C\.1](https://arxiv.org/html/2607.06223#A3.SS1.SSS0.Px1.p1.5),[§5\.1](https://arxiv.org/html/2607.06223#S5.SS1.SSS0.Px3.p1.2)\.
- \[33\]Z\. Yang, P\. Qi, S\. Zhang, Y\. Bengio, W\. Cohen, R\. Salakhutdinov, and C\. D\. Manning\(2018\)HotpotQA: a dataset for diverse, explainable multi\-hop question answering\.InProceedings of the 2018 conference on empirical methods in natural language processing,pp\. 2369–2380\.Cited by:[§C\.1](https://arxiv.org/html/2607.06223#A3.SS1.SSS0.Px1.p1.5),[Appendix D](https://arxiv.org/html/2607.06223#A4.p1.2),[§5\.1](https://arxiv.org/html/2607.06223#S5.SS1.SSS0.Px1.p1.1)\.
- \[34\]S\. Yao, J\. Zhao, D\. Yu, N\. Du, I\. Shafran, K\. Narasimhan, and Y\. Cao\(2022\)React: synergizing reasoning and acting in language models\.arXiv preprint arXiv:2210\.03629\.Cited by:[§1](https://arxiv.org/html/2607.06223#S1.p1.1)\.
- \[35\]Q\. Yu, Z\. Zhang, R\. Zhu, Y\. Yuan, X\. Zuo, Y\. Yue, W\. Dai, T\. Fan, G\. Liu, L\. Liu,et al\.\(2025\)Dapo: an open\-source llm reinforcement learning system at scale\.arXiv preprint arXiv:2503\.14476\.Cited by:[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px1.p1.1)\.
- \[36\]G\. Zhang, H\. Geng, X\. Yu, Z\. Yin, Z\. Zhang, Z\. Tan, H\. Zhou, Z\. Li, X\. Xue, Y\. Li,et al\.\(2025\)The landscape of agentic reinforcement learning for llms: a survey\.arXiv preprint arXiv:2509\.02547\.Cited by:[§1](https://arxiv.org/html/2607.06223#S1.p1.1)\.
- \[37\]C\. Zheng, S\. Liu, M\. Li, X\. Chen, B\. Yu, C\. Gao, K\. Dang, Y\. Liu, R\. Men, A\. Yang,et al\.\(2025\)Group sequence policy optimization\.arXiv preprint arXiv:2507\.18071\.Cited by:[§2](https://arxiv.org/html/2607.06223#S2.SS0.SSS0.Px1.p1.1)\.

## Appendix ADerivations and Proofs

### A\.1Proof of Theorem[1](https://arxiv.org/html/2607.06223#Thmtheorem1)

#### Setup\.

Recall that a complete trajectory is denoted by

o=\(h0→τ1h1→τ2⋯→τThT\),o=\(h\_\{0\}\\xrightarrow\{\\tau\_\{1\}\}h\_\{1\}\\xrightarrow\{\\tau\_\{2\}\}\\cdots\\xrightarrow\{\\tau\_\{T\}\}h\_\{T\}\),\(11\)where all trajectories share a common root nodeh0=qh\_\{0\}=q\. Its probability under the original policy is

πθ​\(o\)=∏t=1Tπθ​\(τt∣ht−1\)\.\\pi\_\{\\theta\}\(o\)=\\prod\_\{t=1\}^\{T\}\\pi\_\{\\theta\}\(\\tau\_\{t\}\\mid h\_\{t\-1\}\)\.\(12\)
At each expansion stage, among all currently active nodes, nodehhis selected with probability proportional toexp⁡\(γ​val​\(h\)\)\\exp\(\\gamma\\mathrm\{val\}\(h\)\), as specified in \([6](https://arxiv.org/html/2607.06223#S4.E6)\), and then expanded according toπθ\(⋅∣h\)\\pi\_\{\\theta\}\(\\cdot\\mid h\)\. We further define the partial cumulative value as

V​\(ot\):=∑k=1t−1val​\(hk\),V\(o\_\{t\}\):=\\sum\_\{k=1\}^\{t\-1\}\\mathrm\{val\}\(h\_\{k\}\),\(13\)whereoto\_\{t\}denotes the partial trajectory ofooup to depthtt\.

#### Proof strategy\.

We first derive the induced distribution over partial trajectories at each depth\. We then show by induction that the depth\-ttdistribution is proportional to the original policy probability multiplied by the exponential information\-gain weight\. Finally, specializing to terminal prefixes yields the desired complete\-trajectory distribution\.

#### Step 1: One\-step expansion from the root\.

At depth0, the root is deterministic:

ℙ​\(h0=q\)=1\.\\mathbb\{P\}\(h\_\{0\}=q\)=1\.\(14\)Since the root is always expanded, the probability of generating a depth\-11nodeh1=\(τ1\)h\_\{1\}=\(\\tau\_\{1\}\)is

μθ\(1\)​\(h1\)=πθ​\(τ1∣h0\)\.\\mu\_\{\\theta\}^\{\(1\)\}\(h\_\{1\}\)=\\pi\_\{\\theta\}\(\\tau\_\{1\}\\mid h\_\{0\}\)\.\(15\)We have

μθ\(1\)​\(o1\)=μθ\(1\)​\(h1\)∝πθ​\(τ1∣h0\)​exp⁡\(γ×0\)=πθ​\(τ1∣h0\)​exp⁡\(γ​V​\(o1\)\)\.\\mu\_\{\\theta\}^\{\(1\)\}\(o\_\{1\}\)=\\mu\_\{\\theta\}^\{\(1\)\}\(h\_\{1\}\)\\propto\\pi\_\{\\theta\}\(\\tau\_\{1\}\\mid h\_\{0\}\)\\exp\\bigl\(\\gamma\\times 0\\bigr\)=\\pi\_\{\\theta\}\(\\tau\_\{1\}\\mid h\_\{0\}\)\\exp\\bigl\(\\gamma V\(o\_\{1\}\)\\bigr\)\.\(16\)

#### Step 2: Induced distribution at an arbitrary layer\.

Let𝒜t\\mathcal\{A\}\_\{t\}denote the set of depth\-ttpartial trajectories\. We now characterize the induced distribution over𝒜t\\mathcal\{A\}\_\{t\}\.

Suppose that at deptht−1t\-1, the empirical distribution over𝒜t−1\\mathcal\{A\}\_\{t\-1\}converges to some limitμθ\(t−1\)\\mu\_\{\\theta\}^\{\(t\-1\)\}\. Fix the stage budget at deptht−1t\-1to beBt−1B\_\{t\-1\}\. For any prefixot−1o\_\{t\-1\}, letN​\(ot−1\)N\(o\_\{t\-1\}\)denote the number of times thatot−1o\_\{t\-1\}appears inAt−1A\_\{t\-1\}\. By construction,

∑ot−1N​\(ot−1\)=Bt−1\.\\sum\_\{o\_\{t\-1\}\}N\(o\_\{t\-1\}\)=B\_\{t\-1\}\.\(17\)According to the expansion rule in \([6](https://arxiv.org/html/2607.06223#S4.E6)\), for each independent sampling trial at deptht−1t\-1, the probability that prefixot−1o\_\{t\-1\}is selected for expansion is

ℙ​\(select​ot−1\)=N​\(ot−1\)​exp⁡\(γ​val​\(ht−1\)\)∑o~t−1N​\(o~t−1\)​exp⁡\(γ​val​\(h~\)\)\.\\mathbb\{P\}\\bigl\(\\text\{select \}o\_\{t\-1\}\\bigr\)=\\frac\{N\(o\_\{t\-1\}\)\\exp\\bigl\(\\gamma\\,\\mathrm\{val\}\(h\_\{t\-1\}\)\\bigr\)\}\{\\sum\_\{\\tilde\{o\}\_\{t\-1\}\}N\(\\tilde\{o\}\_\{t\-1\}\)\\exp\\bigl\(\\gamma\\,\\mathrm\{val\}\(\\tilde\{h\}\)\\bigr\)\}\.\(18\)
Conditioned on selectingot−1o\_\{t\-1\}, the next actionτt\\tau\_\{t\}is sampled according toπθ​\(τt∣ht−1\)\\pi\_\{\\theta\}\(\\tau\_\{t\}\\mid h\_\{t\-1\}\)\. Therefore, for the depth\-ttprefixot=\(ot−1→τtht\)o\_\{t\}=\(o\_\{t\-1\}\\xrightarrow\{\\tau\_\{t\}\}h\_\{t\}\), its generation probability satisfies

ℙ​\(generate​ot\)=ℙ​\(select​ot−1\)​πθ​\(τt∣ht−1\)\.\\mathbb\{P\}\(\\mathrm\{generate\}\\ o\_\{t\}\)=\\mathbb\{P\}\(\\mathrm\{select\}\\ o\_\{t\-1\}\)\\,\\pi\_\{\\theta\}\(\\tau\_\{t\}\\mid h\_\{t\-1\}\)\.\(19\)Substituting \([18](https://arxiv.org/html/2607.06223#A1.E18)\) into \([19](https://arxiv.org/html/2607.06223#A1.E19)\), we obtain

ℙ​\(generate​ot\)=N​\(ot−1\)​exp⁡\(γ​val​\(ht−1\)\)∑o~t−1N​\(o~t−1\)​exp⁡\(γ​val​\(h~t−1\)\)​πθ​\(τt∣ht−1\)\.\\mathbb\{P\}\(\\mathrm\{generate\}\\ o\_\{t\}\)=\\frac\{N\(o\_\{t\-1\}\)\\exp\\bigl\(\\gamma\\mathrm\{val\}\(h\_\{t\-1\}\)\\bigr\)\}\{\\sum\_\{\\tilde\{o\}\_\{t\-1\}\}N\(\\tilde\{o\}\_\{t\-1\}\)\\exp\\bigl\(\\gamma\\mathrm\{val\}\(\\tilde\{h\}\_\{t\-1\}\)\\bigr\)\}\\pi\_\{\\theta\}\(\\tau\_\{t\}\\mid h\_\{t\-1\}\)\.\(20\)
WhenBt−1→∞B\_\{t\-1\}\\to\\infty, by the law of large numbers, for every prefixot−1o\_\{t\-1\},

N​\(ot−1\)Bt−1​⟶a\.s\.​μθ\(t−1\)​\(ot−1\)\.\\frac\{N\(o\_\{t\-1\}\)\}\{B\_\{t\-1\}\}\\overset\{a\.s\.\}\{\\longrightarrow\}\\mu\_\{\\theta\}^\{\(t\-1\)\}\(o\_\{t\-1\}\)\.\(21\)
Therefore, dividing both the numerator and denominator of \([20](https://arxiv.org/html/2607.06223#A1.E20)\) byBt−1B\_\{t\-1\}yields

ℙ​\(generate​ot\)​⟶a\.s\.​μθ\(t−1\)​\(ot−1\)​exp⁡\(γ​val​\(ht−1\)\)∑o~t−1μθ\(t−1\)​\(o~t−1\)​exp⁡\(γ​val​\(h~t−1\)\)​πθ​\(τt∣ht−1\)\.\\mathbb\{P\}\(\\mathrm\{generate\}\\ o\_\{t\}\)\\overset\{a\.s\.\}\{\\longrightarrow\}\\frac\{\\mu\_\{\\theta\}^\{\(t\-1\)\}\(o\_\{t\-1\}\)\\exp\\bigl\(\\gamma\\mathrm\{val\}\(h\_\{t\-1\}\)\\bigr\)\}\{\\sum\_\{\\tilde\{o\}\_\{t\-1\}\}\\mu\_\{\\theta\}^\{\(t\-1\)\}\(\\tilde\{o\}\_\{t\-1\}\)\\exp\\bigl\(\\gamma\\mathrm\{val\}\(\\tilde\{h\}\_\{t\-1\}\)\\bigr\)\}\\pi\_\{\\theta\}\(\\tau\_\{t\}\\mid h\_\{t\-1\}\)\.\(22\)
Hence, noting that the denominator in \([22](https://arxiv.org/html/2607.06223#A1.E22)\) is a finite normalizing constant independent ofoto\_\{t\}, the limiting depth\-ttdistribution satisfies

μθ\(t\)​\(ot\)∝μθ\(t−1\)​\(ot−1\)​exp⁡\(γ​val​\(ht−1\)\)​πθ​\(τt∣ht−1\)\.\\mu\_\{\\theta\}^\{\(t\)\}\(o\_\{t\}\)\\propto\\mu\_\{\\theta\}^\{\(t\-1\)\}\(o\_\{t\-1\}\)\\exp\\bigl\(\\gamma\\mathrm\{val\}\(h\_\{t\-1\}\)\\bigr\)\\pi\_\{\\theta\}\(\\tau\_\{t\}\\mid h\_\{t\-1\}\)\.\(23\)

#### Step 3: Induction formula for prefix distributions\.

We now prove by induction that, for every deptht≥1t\\geq 1,

μθ\(t\)​\(ot\)∝πθ​\(ot\)​exp⁡\(γ​V​\(ot\)\),\\mu\_\{\\theta\}^\{\(t\)\}\(o\_\{t\}\)\\propto\\pi\_\{\\theta\}\(o\_\{t\}\)\\exp\\bigl\(\\gamma V\(o\_\{t\}\)\\bigr\),\(24\)whereπθ​\(ot\):=∏k=1tπθ​\(τk∣hk−1\)\\pi\_\{\\theta\}\(o\_\{t\}\):=\\prod\_\{k=1\}^\{t\}\\pi\_\{\\theta\}\(\\tau\_\{k\}\\mid h\_\{k\-1\}\)is the original policy probability of the prefixoto\_\{t\}\.

*Base case\.*The claim has already been shown fort=1t=1\.

*Inductive step\.*Assume that \([24](https://arxiv.org/html/2607.06223#A1.E24)\) holds for deptht−1t\-1\. Then, by substituting the inductive hypothesis into \([23](https://arxiv.org/html/2607.06223#A1.E23)\) and using the transitivity of proportionality, we obtain

μθ\(t\)​\(ot\)∝πθ​\(ot−1\)​exp⁡\(γ​V​\(ot−1\)\)​exp⁡\(γ​val​\(ht−1\)\)​πθ​\(τt∣ht−1\)\.\\mu\_\{\\theta\}^\{\(t\)\}\(o\_\{t\}\)\\propto\\pi\_\{\\theta\}\(o\_\{t\-1\}\)\\exp\\bigl\(\\gamma V\(o\_\{t\-1\}\)\\bigr\)\\exp\\bigl\(\\gamma\\mathrm\{val\}\(h\_\{t\-1\}\)\\bigr\)\\pi\_\{\\theta\}\(\\tau\_\{t\}\\mid h\_\{t\-1\}\)\.\(25\)Usingπθ​\(ot\)=πθ​\(ot−1\)​πθ​\(τt∣ht−1\)\\pi\_\{\\theta\}\(o\_\{t\}\)=\\pi\_\{\\theta\}\(o\_\{t\-1\}\)\\pi\_\{\\theta\}\(\\tau\_\{t\}\\mid h\_\{t\-1\}\)andV​\(ot\)=V​\(ot−1\)\+val​\(ht−1\)V\(o\_\{t\}\)=V\(o\_\{t\-1\}\)\+\\mathrm\{val\}\(h\_\{t\-1\}\), we obtain

μθ\(t\)​\(ot\)∝πθ​\(ot\)​exp⁡\(γ​V​\(ot\)\),\\mu\_\{\\theta\}^\{\(t\)\}\(o\_\{t\}\)\\propto\\pi\_\{\\theta\}\(o\_\{t\}\)\\exp\\bigl\(\\gamma V\(o\_\{t\}\)\\bigr\),\(26\)which proves the inductive step\.

Therefore, \([24](https://arxiv.org/html/2607.06223#A1.E24)\) holds for allt=1,…,Tt=1,\\dots,T\. ∎

### A\.2Proof of Theorem[2](https://arxiv.org/html/2607.06223#Thmtheorem2)

Following the Donsker\-Varadhan variational formula\[[6](https://arxiv.org/html/2607.06223#bib.bib20)\], we show that the optimizer of \([8](https://arxiv.org/html/2607.06223#S4.E8)\) is the induced trajectory distributionμθ​\(o\)∝πθ​\(o\)​exp⁡\(γ​V​\(o\)\)\\mu\_\{\\theta\}\(o\)\\propto\\pi\_\{\\theta\}\(o\)\\exp\\bigl\(\\gamma V\(o\)\\bigr\)\. We optimize over all trajectory distributionsμ\\mu\. Let

J​\(μ\):=𝔼o∼μ​\[V​\(o\)\]−1γ​𝔻KL​\(μ∥πθ\)\.J\(\\mu\):=\\mathbb\{E\}\_\{o\\sim\\mu\}\[V\(o\)\]\-\\frac\{1\}\{\\gamma\}\\mathbb\{D\}\_\{\\mathrm\{KL\}\}\(\\mu\\\|\\pi\_\{\\theta\}\)\.\(27\)
Using the definition of KL divergence, we have

𝔻KL​\(μ∥πθ\)=𝔼o∼μ​\[log⁡μ​\(o\)πθ​\(o\)\]\.\\mathbb\{D\}\_\{\\mathrm\{KL\}\}\(\\mu\\\|\\pi\_\{\\theta\}\)=\\mathbb\{E\}\_\{o\\sim\\mu\}\\left\[\\log\\frac\{\\mu\(o\)\}\{\\pi\_\{\\theta\}\(o\)\}\\right\]\.\(28\)Hence,

J​\(μ\)=∑oμ​\(o\)​V​\(o\)−1γ​∑oμ​\(o\)​log⁡μ​\(o\)πθ​\(o\)\.J\(\\mu\)=\\sum\_\{o\}\\mu\(o\)V\(o\)\-\\frac\{1\}\{\\gamma\}\\sum\_\{o\}\\mu\(o\)\\log\\frac\{\\mu\(o\)\}\{\\pi\_\{\\theta\}\(o\)\}\.\(29\)Rearranging terms gives

J​\(μ\)=1γ​∑oμ​\(o\)​log⁡exp⁡\(γ​V​\(o\)\)​πθ​\(o\)μ​\(o\)\.J\(\\mu\)=\\frac\{1\}\{\\gamma\}\\sum\_\{o\}\\mu\(o\)\\log\\frac\{\\exp\(\\gamma V\(o\)\)\\pi\_\{\\theta\}\(o\)\}\{\\mu\(o\)\}\.\(30\)
Now we define the normalized distribution

μ⋆​\(o\):=πθ​\(o\)​exp⁡\(γ​V​\(o\)\)∑o~πθ​\(o~\)​exp⁡\(γ​V​\(o~\)\)\.\\mu^\{\\star\}\(o\):=\\frac\{\\pi\_\{\\theta\}\(o\)\\exp\(\\gamma V\(o\)\)\}\{\\sum\_\{\\tilde\{o\}\}\\pi\_\{\\theta\}\(\\tilde\{o\}\)\\exp\(\\gamma V\(\\tilde\{o\}\)\)\}\.\(31\)Let

Z:=∑o~πθ​\(o~\)​exp⁡\(γ​V​\(o~\)\)Z:=\\sum\_\{\\tilde\{o\}\}\\pi\_\{\\theta\}\(\\tilde\{o\}\)\\exp\(\\gamma V\(\\tilde\{o\}\)\)\(32\)be the normalization constant\. Then

πθ​\(o\)​exp⁡\(γ​V​\(o\)\)=Z​μ⋆​\(o\)\.\\pi\_\{\\theta\}\(o\)\\exp\(\\gamma V\(o\)\)=Z\\,\\mu^\{\\star\}\(o\)\.\(33\)Substituting \([33](https://arxiv.org/html/2607.06223#A1.E33)\) into \([30](https://arxiv.org/html/2607.06223#A1.E30)\), we obtain

J​\(μ\)=1γ​∑oμ​\(o\)​log⁡Z​μ⋆​\(o\)μ​\(o\)=1γ​log⁡Z−1γ​∑oμ​\(o\)​log⁡μ​\(o\)μ⋆​\(o\)\.J\(\\mu\)=\\frac\{1\}\{\\gamma\}\\sum\_\{o\}\\mu\(o\)\\log\\frac\{Z\\,\\mu^\{\\star\}\(o\)\}\{\\mu\(o\)\}=\\frac\{1\}\{\\gamma\}\\log Z\-\\frac\{1\}\{\\gamma\}\\sum\_\{o\}\\mu\(o\)\\log\\frac\{\\mu\(o\)\}\{\\mu^\{\\star\}\(o\)\}\.\(34\)Therefore,

J​\(μ\)=1γ​log⁡Z−1γ​𝔻KL​\(μ∥μ⋆\)\.J\(\\mu\)=\\frac\{1\}\{\\gamma\}\\log Z\-\\frac\{1\}\{\\gamma\}\\mathbb\{D\}\_\{\\mathrm\{KL\}\}\(\\mu\\\|\\mu^\{\\star\}\)\.\(35\)Since KL divergence is always nonnegative, with equality if and only ifμ=μ⋆\\mu=\\mu^\{\\star\}, it follows that

J​\(μ\)≤1γ​log⁡Z,J\(\\mu\)\\leq\\frac\{1\}\{\\gamma\}\\log Z,\(36\)and the equality holds if and only ifμ=μ⋆\\mu=\\mu^\{\\star\}\. ∎

## Appendix BWorkflow

Algorithm 1IGRPO1:Require:Initial policy

πθold\\pi\_\{\\theta\_\{\\mathrm\{old\}\}\}, reference policy

πref\\pi\_\{\\mathrm\{ref\}\}, dataset

𝒟\\mathcal\{D\}, temperature

γ\\gamma, KL coefficient

β\\beta, clipping parameter

ϵ\\epsilon, stage budgets

\{Bi\}i=0T−1\\\{B\_\{i\}\\\}\_\{i=0\}^\{T\-1\}, maximum interaction turn

TT
2:foreach training iterationdo

3:Update the old policy snapshot:

θold←θ\\theta\_\{\\mathrm\{old\}\}\\leftarrow\\theta
4:Sample question\-answer pairs

\(q,a\)∼𝒟\(q,a\)\\sim\\mathcal\{D\}
5:Initialize the search tree root

h0h\_\{0\}with each question

qq
6:Initialize the active node set

𝒜0←\{h0\}\\mathcal\{A\}\_\{0\}\\leftarrow\\\{h\_\{0\}\\\}and completed trajectory set

𝒪←∅\\mathcal\{O\}\\leftarrow\\emptyset⊳\\trianglerightInformation gain\-based rollout phase

7:for

i=0i=0to

T−1T\-1do

8:if

𝒜i=∅\\mathcal\{A\}\_\{i\}=\\emptysetthen

9:break

10:endif

11:foreach active node

h∈𝒜ih\\in\\mathcal\{A\}\_\{i\}do

12:Compute the answer score

sθ​\(h;a\)s\_\{\\theta\}\(h;a\)according to \([3](https://arxiv.org/html/2607.06223#S4.E3)\)

13:Compute the information gain

IG​\(h\)\\mathrm\{IG\}\(h\)according to \([4](https://arxiv.org/html/2607.06223#S4.E4)\)

14:Compute the informativeness

val​\(h\)\\mathrm\{val\}\(h\)according to \([10](https://arxiv.org/html/2607.06223#S4.E10)\)

15:endfor

16:Compute the node allocation probabilities

pi​\(h\)p\_\{i\}\(h\)within each group according to \([5](https://arxiv.org/html/2607.06223#S4.E5)\)

17:Initialize the next active set

𝒜i\+1←∅\\mathcal\{A\}\_\{i\+1\}\\leftarrow\\emptyset
18:for

b=1b=1to

BiB\_\{i\}do

19:Sample an active node

h∼pi​\(⋅\)h\\sim p\_\{i\}\(\\cdot\)for each group

20:Expand

hhby sampling one next turn

τ∼πθold\(⋅∣h\)\\tau\\sim\\pi\_\{\\theta\_\{\\mathrm\{old\}\}\}\(\\cdot\\mid h\)
21:Execute the environment transition and obtain the child node

h′h^\{\\prime\}
22:if

h′h^\{\\prime\}is terminalthen

23:Construct the completed trajectory

o′o^\{\\prime\}ending at

h′h^\{\\prime\}
24:Add

o′o^\{\\prime\}to

𝒪\\mathcal\{O\}
25:else

26:Add

h′h^\{\\prime\}to

𝒜i\+1\\mathcal\{A\}\_\{i\+1\}
27:endif

28:endfor

29:foreach unexpanded node

h∈𝒜ih\\in\\mathcal\{A\}\_\{i\}do

30:Construct the trajectory

ooending at

hhand use

sθ​\(h;a\)s\_\{\\theta\}\(h;a\)as its reward according to \([3](https://arxiv.org/html/2607.06223#S4.E3)\)

31:Add

ooto

𝒪\\mathcal\{O\}
32:endfor

33:endfor

34:foreach node

h∈𝒜Th\\in\\mathcal\{A\}\_\{T\}do

35:Construct the completed trajectory

ooending at

hh
36:Add

ooto

𝒪\\mathcal\{O\}
37:endfor⊳\\trianglerightPolicy optimization phase

38:Collect sampled trajectories

\{oi\}i=1N\\\{o\_\{i\}\\\}\_\{i=1\}^\{N\}from the completed set

𝒪\\mathcal\{O\}
39:Update policy

θ\\thetaby maximizing the IGRPO objective

𝒥IGRPO​\(θ\)\\mathcal\{J\}\_\{\\mathrm\{IGRPO\}\}\(\\theta\)according to \([9](https://arxiv.org/html/2607.06223#S4.E9)\)

40:endfor

Algorithm[1](https://arxiv.org/html/2607.06223#alg1)shows the overall workflow of IGRPO\. Instead of directly sampling complete trajectories from the policy, IGRPO constructs paths through a tree\-structured rollout process, where active nodes are expanded layer by layer under information gain\-based allocation\. This procedure approximates the teacher distributionμθold\\mu\_\{\\theta\_\{\\mathrm\{old\}\}\}over trajectories, based on which policy optimization is performed\.

## Appendix CExperiment Details

### C\.1Training Details

#### Hyperparameters for Search\-Augmented QA\.

Our hyperparameter configuration directly follows GiGPO\[[7](https://arxiv.org/html/2607.06223#bib.bib6)\]\. We set the maximum prompt length to 4096 tokens and the maximum response length to 512 tokens\. The actor learning rate is set to1×10−61\\times 10^\{\-6\}\. We use a rule\-based reward function, assigning a reward of 1 to successful trajectories and 0 otherwise, while imposing a penalty of−0\.01\-0\.01for invalid actions\. The training batch size is 256, with training data constructed by mixing NQ\[[14](https://arxiv.org/html/2607.06223#bib.bib11)\]and HotpotQA\[[33](https://arxiv.org/html/2607.06223#bib.bib14)\]datasets\. We use E5\[[29](https://arxiv.org/html/2607.06223#bib.bib19)\]as the retriever, returning the top\-3 most relevant results for each query, and expose the full retrieval history to the agent\. The rollout temperature and validation temperature are set to 1\.0 and 0\.0, respectively\. The KL regularization coefficient is set to 0\.001\. Our IGRPO expanding temperatureγ\\gammais set to 1\.0 without further tuning\. Qwen2\.5\-3B\-Instruct\[[32](https://arxiv.org/html/2607.06223#bib.bib18)\]is trained on 4×\\timesH20 GPUs, while Qwen2\.5\-7B\-Instruct is trained on 8×\\timesH20 GPUs\.

#### Implementation Details\.

We build our codebase on top of theverl\-agentframework\[[7](https://arxiv.org/html/2607.06223#bib.bib6)\]\. In particular, on top of this framework, we reproduce IGPO\[[28](https://arxiv.org/html/2607.06223#bib.bib7)\]and adapt it to use the E5 retriever in our search\-augmented QA setting\. Our preliminary experiments as well as the proposed IGRPO are then both developed based on this reproduced IGPO implementation\. For IGRPO, due to a limited rollout budget, we adopt a practical strategy: each node is expanded at most twice at each stage, which encourages exploration\. We emphasize that the information gain signal is only used during training for rollout allocation; at inference time, the agent follows the learned policy without access to the ground\-truth answer\. For Tree\-GRPO\[[11](https://arxiv.org/html/2607.06223#bib.bib10)\], we implement it based on its official codebase, withm=2m=2,n=3n=3,k=4k=4, andl=1l=1\. The remaining baseline results reported in Table[1](https://arxiv.org/html/2607.06223#S5.T1)are taken from GiGPO\. We directly use the Search\-R1 datasets\[[12](https://arxiv.org/html/2607.06223#bib.bib3)\], whose data sources have different test\-set sizes\. Accordingly, the average score in Table[1](https://arxiv.org/html/2607.06223#S5.T1)is computed as a dataset\-size\-weighted average, where Bamboogle\[[18](https://arxiv.org/html/2607.06223#bib.bib17)\]has only 125 examples while PopQA\[[16](https://arxiv.org/html/2607.06223#bib.bib13)\]and 2WikiMultiHopQA\[[9](https://arxiv.org/html/2607.06223#bib.bib15)\]contain over 10K examples\.

#### Search Prompt\.

The prompt template for the search agent is shown in Figure[6](https://arxiv.org/html/2607.06223#A3.F6)\. We construct this template using Python\-style string formatting, where placeholders enclosed in curly braces, including\{task\_description\},\{step\_count\}, and\{memory\_context\}, are dynamically populated at runtime\. The interaction history is explicitly incorporated into the prompt, where prior search queries are marked by<search\></search\>and retrieved evidence is marked by<information\></information\>\.

The agent is first required to perform explicit reasoning within<think\></think\>tags\. It must then take exactly one action: either calling the search engine using<search\></search\>when additional knowledge is required, or producing the final answer using<answer\></answer\>when it is confident enough to respond\. Such a formulation makes retrieval\-augmented generation more interpretable and easier to standardize across search trajectories\.

![Refer to caption](https://arxiv.org/html/2607.06223v1/figures/prompt.png)Figure 6:Prompt template for the search agent\.

### C\.2Additional Results\.

Table 2:Average number of tool calls during inference at step 200\. Lower values indicate more efficient tool usage\. Experiments are conducted with Qwen2\.5\-3B\-Instruct\.†\\daggerand⋆\\starindicate in\-domain and out\-of\-domain datasets, respectively\.MethodSingle\-Hop QAMulti\-Hop QANQ†TriviaQA⋆PopQA⋆HotpotQA†2Wiki⋆MuSiQue⋆Bamboogle⋆IGPO1\.371\.361\.471\.681\.932\.391\.84\\rowcolorgray\!15IGRPO1\.111\.151\.221\.501\.861\.941\.44

#### Tool\-call Efficiency\.

We further compare the tool\-call frequency of IGPO and IGRPO during inference\. As shown in Table[2](https://arxiv.org/html/2607.06223#A3.T2), IGRPO consistently uses fewer tool calls than IGPO across the evaluated datasets, indicating that the proposed information gain\-based rollout encourages the model to search more selectively rather than issuing unnecessary queries\. This suggests that IGRPO learns to avoid low\-value search actions and can reach final answers with fewer external interactions, leading to more efficient inference\. Meanwhile, the number of tool calls on multi\-hop datasets remains higher than that on single\-hop datasets, which is consistent with the fact that multi\-hop questions usually require collecting and integrating evidence from multiple sources\. Therefore, the reduction in tool usage does not imply that the model simply suppresses searching; instead, it learns a more adaptive search pattern, using more tool calls when the task requires additional evidence while reducing redundant calls on simpler questions\.

#### Per\-node Budget Reduction\.

As shown in Figure[7](https://arxiv.org/html/2607.06223#A3.F7), we analyze the training dynamics in terms of entropy loss\. The experiment investigates how the per\-node maximum expansion budget affects the entropy dynamics\. Reducing this maximum budget at either step 100 or step 150 consistently leads to a faster decay of entropy loss, suggesting that limiting node expansion makes the induced rollout distribution more concentrated\. Nevertheless, the final overall success rate drops by approximately 1% after per\-node budget reduction\. This indicates that the higher entropy maintained by tree\-structured rollout is not merely a by\-product of increased branching, but plays a useful role in sustaining exploration, which is consistent with our main experimental observation that sufficient entropy benefits final task performance\.

![Refer to caption](https://arxiv.org/html/2607.06223v1/figures/entropy_loss_branch.png)Figure 7:Training dynamics of IGRPO\-3B and IGPO\-3B\. Dashed vertical lines indicate the steps where the per\-node expansion budget is reduced, where yellow denotes reducing the budget at step 100 and red denotes reducing the budget at step 150\. The figure shows the entropy loss during training\.
#### Per\-stage Budget Reduction\.

We further study the robustness of IGRPO under a reduced per\-stage rollout budget\. Specifically, IGRPO\-low reduces the per\-stage expansion budget to the size of the current active set𝒜i\\mathcal\{A\}\_\{i\}, so that each stage allocates substantially fewer expansions while preserving the information gain\-based node selection mechanism\. As shown in Table[3](https://arxiv.org/html/2607.06223#A3.T3), IGRPO\-low achieves an average score of 44\.5%, which is only 0\.9% lower than the full IGRPO variant\. Moreover, IGRPO\-low also outperforms IGRPO on HotpotQA and MuSiQue\[[27](https://arxiv.org/html/2607.06223#bib.bib16)\], suggesting that reducing the per\-stage budget does not uniformly hurt performance and can sometimes improve generalization by limiting redundant expansions\. Notably, despite using a smaller expansion budget, IGRPO\-low still outperforms all baselines reported in Table[1](https://arxiv.org/html/2607.06223#S5.T1), demonstrating the robustness and effectiveness of information gain\-based rollout allocation\.

Table 3:Performance on QA tasks \(%\)\. IGRPO\-low denotes the variant with a reduced per\-stage expansion budget\. Experiments are conducted with Qwen2\.5\-3B\-Instruct\.†\\daggerand⋆\\starindicate in\-domain and out\-of\-domain datasets, respectively\. Avg\. denotes the test\-size\-weighted average\.MethodSingle\-Hop QAMulti\-Hop QAAvg\.NQ†TriviaQA⋆PopQA⋆HotpotQA†2Wiki⋆MuSiQue⋆Bamboogle⋆IGRPO\-low44\.759\.846\.439\.438\.714\.465\.344\.5\\rowcolorgray\!15IGRPO45\.660\.947\.538\.940\.214\.165\.745\.4

#### Reward Design\.

Our main focus is adaptive branching rather than reward design: the former determines the induced trajectory distribution, while the latter affects how effectively the policy approaches the corresponding teacher distribution during optimization\. In practice, we find that different reward designs can lead to different training behaviors\. For paths that terminate due to the absence of expandable nodes, we set their rewards according to the cumulative information gain along the path\. Formally, letG​\(o\)G\(o\)denote the cumulative information gain of a pathoo\. Since there are many possible ways to convertG​\(o\)G\(o\)into a reward signal, we conduct an ablation study over four representative designs\. The first design uses the full cumulative information gain throughout all 200 training steps, i\.e\.,R​\(o\)=G​\(o\)R\(o\)=G\(o\)\. The second and third designs use a conservative reward scale in the first 150 steps, i\.e\.,R​\(o\)=0\.5​G​\(o\)R\(o\)=0\.5\\,G\(o\), which prevents partially informative but incomplete paths from receiving overly large rewards while still preserving their relative informativeness\. For the last 50 steps, the second design keeps the same conservative scale, whereas the third design switches to the full cumulative information gain to provide a stronger and more stable dense signal in the later stage\. The fourth design also uses0\.5​G​\(o\)0\.5\\,G\(o\)in the first 150 steps, but applies a hard threshold in the last 50 steps, assigning reward1\.01\.0whenG​\(o\)\>0\.5G\(o\)\>0\.5and0\.00\.0otherwise\.

Among the four variants, we obtain the best overall performance with the third reward design, where the reward is set to0\.5​G​\(o\)0\.5\\,G\(o\)in the first 150 training steps and switched toG​\(o\)G\(o\)in the last 50 steps\. The other reward designs lead to an accuracy drop of about0\.5%0\.5\\%–2%2\\%, suggesting that the reward scale for such terminated paths has a non\-negligible effect on optimization stability\. Intuitively, the coefficient0\.50\.5can be interpreted as a penalty for paths that terminate due to the absence of expandable nodes, preventing these incomplete or insufficiently explored paths from receiving overly large rewards\. In the later training stage, once the model has learned a reasonable search pattern, using the full cumulative information gain provides a stronger and more stable dense signal\. This is especially beneficial for single\-hop QA, where one effective search step can already produce highly informative evidence; assigning the full information\-gain reward in this stage therefore better captures the utility of such trajectories\.

## Appendix DCase Study

Figure[8](https://arxiv.org/html/2607.06223#A4.F8)presents the overall tree structure of a representative example from the multi\-hop QA benchmark HotpotQA\[[33](https://arxiv.org/html/2607.06223#bib.bib14)\]\. The rollout tree shows that IGRPO induces a clear bias toward branches with larger informativeness value, so that the final sampled trajectories are concentrated on more informative search paths\. At the same time, the allocation remains probabilistic rather than deterministic: nodes with lower informativeness value can still be expanded at each stage, which preserves exploration and avoids overly greedy rollout behavior\. Moreover, the transition from𝒜2\\mathcal\{A\}\_\{2\}to𝒜3\\mathcal\{A\}\_\{3\}clearly illustrates how low informative nodes are gradually filtered out during rollout\. These nodes continue to receive less expansion budget over time and ultimately fail to produce correct answers, whereas more informative branches are retained and expanded into successful trajectories\.

![Refer to caption](https://arxiv.org/html/2607.06223v1/figures/case_study_overall.png)Figure 8:Case study of the overall tree\-structured rollout behaviors of IGRPO\. The number on each edge indicates the information gain obtained by the corresponding search step\. The three numbered nodes are further analyzed in detail\.![Refer to caption](https://arxiv.org/html/2607.06223v1/figures/case_study_detail.png)Figure 9:Detailed analysis of the three highlighted nodes in the case study\. Node 1 issues an ambiguous query and fails to target the key entity\. Node 2 uses the correct subject and retrieves useful evidence, while its child, Node 3, further verifies the answer and confirms the Conn Smythe Trophy\.As shown in Figure[9](https://arxiv.org/html/2607.06223#A4.F9), we further detail the three highlighted nodes in Figure[8](https://arxiv.org/html/2607.06223#A4.F8)\. Node 1 issues an ambiguous query and obtains misleading search evidence, causing its subsequent continuations to fail to reach the correct answer\. In contrast, Node 2 and its child Node 3 progressively move toward the correct prediction\. Notably, the search results of Node 2 already contain the correct answer, while Node 3 further verifies it before producing the final decision\. Such verification behavior frequently emerges during training across different models, further highlighting the importance of allocating rollout budget to informative nodes\.