acceptodds
Under review as a conference paper at ICLR 2027

When Does Branching Pay? An Exact Variance Analysis of Tree-Structured Policy Gradients

Abstract

Group-relative policy gradient methods sample a fixed number of independent completions per prompt, so the rollouts share nothing but the prompt. A growing literature makes use of tree-structured policy gradient estimators instead, branching at chosen points guided by heuristics. We formalize such designs as a pair : a kernel that decides where and how much to branch, and an anchor map that decides which ancestor supplies each edge's baseline group. For any such pair, we give an exactly unbiased on-policy gradient estimator and, to our knowledge, the first exact variance decomposition for tree policy gradients with adaptive branching and group baselines. From it, we derive design principles for where to branch and how to form baseline groups, and identify regimes in which branching does not help. We test these predictions on reasoning and multi-turn agentic tool-use tasks with verifiable rewards.

Primary area:
reinforcement learning
Keywords:
Tree-Structured Policy Gradients, Group-relative Policy Optimization, Reinforcement Learning with Verifiable Rewards, Multi-turn Agents

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_iq1vOpenReview ↗
Rating
2
Confidence
4
Informativeness
3
Presentation
3
Soundness
1
Read review
Paper summary

The paper studies when tree-structured sampling reduces policy-gradient estimator variance at matched sampling cost. It defines a weighted estimator with path-predictable branching and ancestor-based leave-branch-out baselines, derives an exact variance decomposition through cut refinement that captures prefix scores, baseline-anchor offsets, and sibling noise, and provides conditional branching/re-anchoring comparisons and a late-branching lower bound. Experiments on MATH and HotpotQA examine noise location and random, entropy-based, and oracle placement; separate HotpotQA training experiments compare existing tree samplers and baseline estimators. The oracle is effective in fixed-model variance diagnostics, but this placement rule is not used in the training experiments.

Critical strengths
  1. The full increment analysis for dependent trees has substantive content. Equations (40) and (54) track how revealing a subtree changes earlier prefix-gradient contributions and affects other branches through an ancestor baseline, while handling unequal branch masses and path-predictable branching. Joint moments of random continuation scores and rewards, multilevel dependence, and cross-branch baselines do not follow automatically from multiplication by a fixed score matrix. This is a technical extension beyond shared-context advantage analysis that deserves credit.

  2. The baseline tradeoff and restricted lower bound provide useful insight. The decomposition makes explicit that a local baseline can reduce the anchor offset while increasing estimation noise from a finite number of siblings. Under a front-loaded noise profile and its stated sampling conditions, Proposition I.1 gives a global lower bound showing that sufficiently late branching cannot outperform independent sampling at the same cost. Table 1 also shows that placement information can materially change fixed-model variance. These results support the paper's value as a diagnostic framework for tree estimators.

Critical weaknesses

The experiments do not connect the oracle variance advantage to achievable placement benefits or training gains. Appendix J.2 uses additional sibling continuations 2–3 to estimate candidate-specific V,G,C,BV,G,C,B, selects a location using Eq. (55), and evaluates it with the original suffix and sibling 1. Separating the continuations used for selection and evaluation is a useful control, but the probing continuations are excluded from cost. Thus the relative variances of 0.86 on MATH and 0.63 on HotpotQA in Table 1 demonstrate placement potential with additional information. They do not establish an efficiency advantage including information-acquisition cost, or show how these quantities can be obtained cheaply at sampling time. The authors explicitly disclose the oracle setup; the issue is the contribution that this experiment can substantiate.

The training comparisons in Section 5.3/Table 2 include existing random and entropy-based sampling rules and estimator variants such as the shipped and root/local-anchor estimators, but do not train with the theory-guided placement rule above. They therefore do not test the chain from theoretically identified lower-variance locations to better learning curves or final performance. The existing root/local comparisons deserve credit, but they change baseline selection and cannot substitute for a placement-rule comparison; the differing training configurations also do not clearly isolate the effects of the new dependence terms.

More fundamentally, reducing the trace of the raw gradient covariance does not guarantee better optimizer updates or final task performance: covariance directions, objective curvature, optimizer transformations, and policy changes during training all affect this relationship. The paper analyzes estimator variance at a fixed policy, without a conditional result or controlled experiment sufficient to connect it to training gains. The training results mainly show that the tested random/entropy rules do not consistently help; they do not validate a training benefit from the oracle's lower variance. The theoretical contribution should be assessed through the estimator insights actually established, without additionally crediting an unshown training benefit.

Questions for authors

see weakness

2 comments

Thank you for your careful review and detailed comments. We address the weaknesses pointed out below

W1: sufficiency of placement potential as a contribution

Paragraph 1: “relative variances … in Table 1 demonstrate placement potential without additional information”, “authors explicitly disclose the oracle setup; the issue is the contribution that this experiment can substantiate.”

You are completely right in that the experiments in section 5.2 are meant to demonstrate placement potential only. However, we would argue that measuring placement potential is in fact a valuable contribution in itself, because it shows that existing heuristic-guided branching methods do not reach that potential. Furthermore, this constitutes a diagnostic framework that can show exactly for what type of tasks there is no benefit to branching.

See also point 1 of our general response.

W2: connection between reduced variance and training benefits

Paragraphs 2 and 3: “comparisons in Section 5.3 … do not train with the theory-guided placement rule”, “reducing the trace of the raw gradient covariance does not guarantee better optimizer updates or final task performance”

This is a fair point, and while we mainly wanted to show that in the absence of variance reduction, there is no training benefit, we agree that our case would be stronger if we can also show that where there is variance reduction, there is training benefit. We have taken your suggestion to train with the theory-guided placement rule, and aim to have the results ready by the camera ready version.

See also point 2 of our general response.

Thank you for the clarification. I appreciate the variance analysis and the diagnostic insights it provides. My main concern is whether the framework can use preliminary diagnostics to assess, before training, whether a given heuristic branching strategy is worth adopting. Such guidance would help practitioners make informed sampling decisions before committing to a full training run, making the framework’s practical value clearer. The current submission and rebuttal have not yet demonstrated this capability, and it also remains unclear how the framework could identify suitable branching points in practice. These questions leave my main concern unresolved, so I will maintain my original rating.

Reviewer_2dsTOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies when tree-structured rollouts, which branch partway through generation instead of sampling independent completions, reduce the variance of the policy gradient at the same sampling cost in RL post-training of LLMs with verifiable rewards. The paper formalizes tree-structured methods as a pair of a branching kernel β, which decides where and how much to branch, and an anchor map α, which decides which ancestor fork supplies each edge's baseline group. If the branching decisions depend only on what has been generated so far (previsibility), the estimator is unbiased (Theorem 3.2), and its variance decomposes exactly into a sum of per-fork contributions (Theorem 3.5). From this, the paper derives principles for where to branch and how to form baseline groups, and a condition under which a tree that waits to branch cannot beat independent completions when the gradient noise is front-loaded (Proposition 4.5).

The experiments use Qwen2.5-3B on MATH and on HotpotQA with a retrieval tool. From the measured gradient-noise profiles, the paper argues that trees are better suited to multi-turn tasks. When the variance of single-fork trees is measured directly, forks placed at a random vertex or at an entropy rise (ARPO's trigger) stay close to independent completions at matched cost, whereas the oracle based on the variance formula reduces the variance (0.86 on MATH, 0.63 on HotpotQA). In training on HotpotQA, the paper reports that neither Tree-GRPO's nor ARPO's branching consistently improves accuracy.

Critical strengths
  • The paper gives an exact variance decomposition of tree-structured policy gradients without approximation, and shows that branching location strongly affects the variance. Equation 11 separates which terms of the variance are affected by the number of children, the choice of anchors, and the branching location. This makes the trade-off explicit between averaging out noise with more children and the cost of baselining against siblings from the same fork. For independent completions, it reduces to the variance of RLOO. In Table 1, forks placed at locations chosen by this formula substantially reduce the variance at matched cost, whereas random and entropy placements barely reduce it, and entropy is not detectably better than random. This provides a valuable common ground for discussing the design of tree-structured rollouts.
Critical weaknesses
  • The design principles are not validated as a usable branching method. The central claim of the paper is that the variance decomposition yields principles for where to branch and how to form baseline groups. However, a placement that substantially reduces the variance is shown only for the oracle. This oracle estimates the quantities in Equation 11 by generating two additional rollouts at each candidate vertex, and this probe cost is excluded from the comparison (Appendix J.2). No estimation procedure usable at sampling time is proposed. The Anchor Selection Principle (Proposition 4.4) is not validated, since Table 1 uses only the root-anchored estimator. The statement in §5.2 that the predicted variance change matches the realised one is also not an independent validation, because prediction and measurement reuse the same continuations (Appendix J.2). The experiments therefore support only that good branching locations exist, not that the variance decomposition yields practical design principles.

  • The conclusions about where trees apply and about the training results are not supported by the evidence. §5.1 concludes from Proposition 4.5 that trees are better suited to multi-turn tasks. However, Proposition 4.5 assumes, among other things, a non-increasing gradient-noise profile (q1≥⋯≥qLq_1 \ge \dots \ge q_L), and it is not shown that the MATH measurements satisfy this assumption. Moreover, the trees in Table 1 (four chains from the prompt, only one of which forks into cc children at depth dd) cost 4L+(c−1)(L−d)4L+(c-1)(L-d), so the condition d≥nL/md \ge nL/m of Proposition 4.5 is not satisfied at any branching location for c=2,3,4c = 2, 3, 4. As for the training experiments, the introduction attributes the lack of accuracy improvement to variance, but the variance of the Tree-GRPO and ARPO kernels used in training is not measured. Furthermore, warm-up, prompt counts, and advantage scales differ across methods, and 10 of the 24 runs failed to train or hit a gradient freeze. The evidence is therefore insufficient to attribute the lack of accuracy differences to variance.

Questions for authors
  • On branching location and anchor selection Does the theory rule still reduce the variance below that of independent completions at matched cost when the cost of the oracle's additional rollouts is included? Can you also report results with every fork as an anchor (g^β,Vf\hat{g}_{\beta,\mathcal{V}^f}) in the same setting as Table 1?

  • On the training experiments Can you measure the variance at matched cost of the Tree-GRPO and ARPO kernels used in training, using the same procedure as Table 1? If this is difficult, please tone down the statement in the introduction that attributes the lack of accuracy improvement to variance.

2 comments

Thank you for your careful review and detailed comments. We address the weaknesses pointed out below

W1 / Q1: lack of usable branching estimator

We agree that our design principles do not constitute a usable branching estimator, which we state explicitly throughout the paper. And so the answer to the first part of Q1 would be no, the theory rule would not reduce variance at matched cost if the cost of the oracle inputs is included (hence why it is the oracle).

The concern about the anchor selection principle is a fair criticism, and we will extend our experiments to report results with every fork as an anchor in the same settings as Table 1, as per your suggestion.

However, we would like to argue that our experiments are valuable as contributions, because they not only support that “good branching locations exist”, but also that “good branching locations are easier to come by in some tasks than others”, and that “existing methods fail to find good branching locations”.

See also point 1 of our general response.

W2 / Q2: clarification on Prop 4.5 + connection between reduced variance and training benefits

a) “Section 5.1 concludes from Proposition 4.5 that trees are better suited to multi-turn tasks. However, Proposition 4.5 assumes, among other things, a non-increasing gradient-noise profile (q₁ ≥ ⋯ ≥ q_L), and it is not shown that the MATH measurements satisfy this assumption”

We would like to clarify that section 5.1 predicts that trees are better suited to multi-turn tasks than single-turn tasks such as MATH, based on their gradient noise profiles and Prop 4.5. However, it does not conclude that branching has no benefit at all on MATH compared to independent completions at matched cost, because we observed that it does not have a non-increasing gradient noise profile, as the reviewer stated. This prediction is further validated in section 5.2, where we show that there is potential benefit to branching in MATH with an oracle placement rule.

b) “the trees in Table 1 … cost 4L + (c − 1)(L − d), so the condition d ≥ nL/m of Proposition 4.5 is not satisfied at any branching location for c = 2, 3, 4”

Again, we would like to clarify that Prop 4.5 gives sufficient conditions under which branching has no benefit. To say that the trees in Table 1 do not satisfy these conditions, then, is to say that branching may have some benefits in these settings. And indeed Table 1 does show that branching at the optimal points reduces variance at matched cost.

c) “introduction attributes the lack of accuracy improvement to variance, but the variance of the Tree-GRPO and ARPO kernels used in training is not measured, … The evidence is therefore insufficient to attribute the lack of accuracy differences to variance.”

This is a fair point. While we do measure the variance of branching estimators with a single fork relative to independent completions, we do not directly measure the variance of the Tree-GRPO and ARPO estimators used in training. We will extend our experiments to include this, as per your suggestion.

See also point 2 of our general response.

Thank you for the response and the clarifications. I agree that the variance decomposition and the finding that existing heuristics do not reduce variance at matched cost are useful. However, the response adds no new evidence: the anchor-selection results and the variance of the kernels used in training are deferred, and the attribution of the training results to variance remains untested. I therefore maintain my rating.

Reviewer_ZAx5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper analyzes how branching locations and baseline groups affect policy gradient variance and when tree-structured sampling is beneficial.

Critical strengths

The paper provides a systematic explanation of how branching locations and baseline groups affect policy gradient variance.

Critical weaknesses
  1. The paper does not address how to find good branching points in practice.

  2. The experimental setup needs improvement. For mathematical reasoning, branching points are set at fixed token positions rather than reasoning-step boundaries or specific token patterns.

  3. The model choice is not convincing, especially for agent tasks, as it does not include a stronger model with substantial agent training.

  4. The paper is poorly written and difficult to follow.

Questions for authors

See weaknesses.

1 comment

Thank you for your time and your feedback. We address the weaknesses pointed out below

  1. See point 1 of our general response

  2. This is a fair criticism. In trying to compare different placement rules in section 5.2, we did not take into account that results would likely vary across different candidate sets of branching points as well (i.e. token position vs reasoning step boundaries). We will repeat our experiments with mathematical reasoning with reasoning step boundaries as candidate branching points.

  3. This is another fair criticism, and we are in the process of repeating all our experiments with Qwen2.5-7B. However, we would like to note that Qwen2.5-3B base is used by both Tree-GRPO and Search-R1, so our training comparison reproduces, at least in part, the setting those methods were published in.

  4. Thank you for taking time to read the paper. We would appreciate it if you could point out any sections that were particularly difficult to follow, so we can prioritize their presentation in the revision.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank the reviewers for their comments and suggestions, especially in recognizing the strength of our theoretical contribution, and the insights it provides. Below, we address overlapping points which appeared in multiple reviews.

1. No usable branching estimator

Our experiments primarily intend to measure the ceiling of potential gains in policy gradient variance reduction from branching, across task types (i.e. single-turn vs multi-turn) and existing methods (i.e. random vs entropy-triggered) and our findings reveal

  • Branching is better suited for multi-turn tasks (section 5.1)
  • Neither random nor entropy-triggered branching significantly reduces the policy gradient variance at matched cost, compared to independent completions. (section 5.2)

We agree that the design implications we derive in section 4 do not yield a usable method on their own (as we have explicitly stated throughout the paper), but argue that they are a valuable starting point for further research, so that future estimators can at least be pointed in the right direction instead of continuing to rely on heuristics.

2. Policy gradient variance reduction does not imply training gains

Our training experiments in section 5.3 were a follow-up to the experiments in section 5.2, where we established that neither random nor entropy-triggered branching significantly reduces the policy gradient variance at matched cost in the settings in which we tested them. This follow-up was again intended to measure the ceiling of potential gains in training accuracy from branching, and found that in the absence of variance reduction, there is no training benefit.

We agree with reviewers iq1v and 2dsT, who helpfully pointed out that the converse claim (i.e. “in the presence of variance reduction, there is a training benefit”) remains empirically untested in our paper. To remedy this, we are currently running experiments which extend section 5.3 experiments by training with the theory-guided placement rule, to test whether it can produce a training benefit, as suggested by reviewer iq1v. We aim to have the results for the camera ready version.

We would also like to highlight that existing work has identified policy gradient variance as a common failure mode in long horizon reasoning tasks. In particular, Li et al have observed spikes in variance right before training collapse, while estimators with lower variance result in stable training, in their paper The Optimal Token Baseline: Variance Reduction for Long-Horizon LLM-RL (ICML 2026).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.