acceptodds
Under review as a conference paper at ICLR 2027

TreeRPO: Tree Relative Policy Optimization

Abstract

Large Language Models (LLMs) have shown remarkable reasoning capabilities through Reinforcement Learning with Verifiable Rewards (RLVR) methods. However, a key limitation of existing approaches is that rewards defined at the full trajectory level provide insufficient guidance for optimizing the intermediate steps of a reasoning process. To address this, we introduce \name, a novel method that estimates the mathematical expectations of rewards at various reasoning steps using tree sampling. Unlike prior methods that rely on a separate step reward model, \name directly estimates these rewards through this sampling process. Building on the group-relative reward training mechanism of GRPO, \name innovatively computes rewards based on step-level groups generated during tree sampling. This advancement allows \name to produce fine-grained and dense reward signals, significantly enhancing the learning process and overall performance of LLMs. Experimental results demonstrate that our \name algorithm substantially improves the average Pass@1 accuracy of Qwen-2.5-Math on test benchmarks, increasing it from 19.0% to 35.5%. Furthermore, \name significantly outperforms GRPO by 2.9% in performance while simultaneously reducing the average response length by 18.1%, showcasing its effectiveness and efficiency.

Primary area:
reinforcement learning
Keywords:
RL, LLM, Reasoning

Reviews

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

The paper proposes TreeRPO, a GRPO variant that replaces flat trajectory sampling with tree-structured sampling for RLVR on mathematical reasoning. Continuations are sampled in fixed-length segments to a bounded depth, terminal paths are scored by a binary verifier, and rewards are propagated upward by averaging over children, giving fractional estimates of downstream success without a learned process reward model. Siblings under the same prefix form comparison groups; near-uniform groups are filtered out, and advantages are scaled by the group's Bernoulli variance µ(1−µ)µ(1−µ) instead of the empirical standard deviation.

The stated contributions are:

  • outcome-derived intermediate supervision via sibling groups at shared prefixes
  • range-based group filtering combined with a mean-dependent advantage scale
  • an empirical comparison against GRPO at two model sizes.

Validation uses Qwen2.5-Math-1.5B and 7B trained on the MATH training split and evaluated on AIME24, MATH-500, OlympiadBench, and Minerva Math. Reported macro accuracy improves for both models and all benchmarks, comparing to naive GRPO.

Critical strengths

None

Critical weaknesses

1. No compute-matched comparison. A depth-3, 8-way tree generates up to 584 segments and 512 verifier calls per question versus 8 and 8 for GRPO, and the two methods differ in gradient updates per step (16 vs 2 under the stated minibatch rule). All curves nevertheless use training steps as the x-axis, and no GRPO baseline with a larger rollout budget is reported. The paper acknowledges this in Sections 4.3, 4.5 and argues from the curves anyway. The central claim of a "practical alternative" is therefore unsupported.

2. Gains are indistinguishable from noise or model-specific artifacts. Single run per setting, no variance. The 7B macro gain is 0.7 points; the 1.5B AIME24 gain is about one problem out of 30. All experiments use Qwen2.5-Math, where spurious rewards have been shown to produce comparable MATH-500 gains(findings in https://arxiv.org/pdf/2506.10947), so the improvement cannot be credited to the method. The evaluation protocol is itself inconsistent (8 samples in text, Avg@16 in the table caption) and marked as "requires confirmation", which is very suspicious to be the LLM-generated text.

3. No component is isolated. Tree sampling, group filtering, and the advantage scale are never ablated. None of the three stated contributions is individually supported.

4. The length reduction has an unexamined structural cause. Early-terminating children receive rewards in {0, 1} while continuing children receive fractional means, so terminating segments occupy the extremes of every group's advantage distribution. On MATH training data, correct terminations dominate, pushing toward shorter outputs; the 1/∣zi∣1/|z_i| normalization adds the known per-token length bias. The paper offers speculation and no test, so the length result cannot be read as a benefit.

5. The µ(1−µ) advantage scale is unmotivated. Preserving reward-gap magnitude only requires not normalizing (A = R − µ). Dividing by µ(1−µ) instead amplifies groups with extreme µ: the paper's example sits at µ = 0.5, where amplification is minimal, while a valid group such as (0, 0, 0, 0, 0, 0, 0, 0.125) yields a top advantage near 7 against 0.9 under standard normalization. The authors note the endpoint issue and provide no measurement.

6. Positioning does not match implementation, and the closest prior work is missing. "Step-level" means fixed 384-token blocks with two branch points per path, unrelated to reasoning steps. Methods that estimate intermediate advantages from rollouts at prefixes are neither cited nor compared: VinePPO (https://arxiv.org/abs/2410.01679), SPO, whose SPO-tree variant uses tree-based segment advantage estimation (https://arxiv.org/abs/2505.23564), TreeRL (https://arxiv.org/abs/2506.11902), and rStar-Math (https://arxiv.org/abs/2501.04519). With GRPO as the only baseline, the paper does not establish what tree-relative grouping adds.

Questions for authors
  1. Please report the measured per-question generation cost of TreeRPO relative to GRPO (generated tokens, verifier calls, and wall-clock time), accounting for early termination, together with the number of gradient updates per training step under each method's minibatch configuration.
  2. Please confirm whether the results in Table 1 are from a single training seed, and whether evaluation uses eight or sixteen samples per question.
  3. Among retained groups, how frequently do early-terminating children (whose rewards lie in {0, 1}) receive the largest-magnitude advantages, and what is the empirical distribution of µ(1−µ)µ(1−µ)? These statistics determine whether the observed length reduction and the proposed advantage scale reflect intended behavior or estimator artifacts.
  4. A GRPO baseline whose rollout budget matches the realized generation cost of TreeRPO.
  5. Ablations isolating tree sampling, group filtering, and the µ(1−µ)µ(1−µ) scale, including the unnormalized alternative A = R − µ.
  6. Results on a model family other than Qwen2.5-Math (like more recent Qwen series) with multiple seeds, and a matched-compute comparison against other baselines, e.g. VinePPO or SPO-tree.
Reviewer_U4QNOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes TreeRPO, a tree-based policy optimization method that constructs process training signals from verified terminal rewards. It recursively estimates continuation values from sampled subtrees and performs GRPO-style updates using sibling-relative advantages, combined with reward-range filtering and a mean-dependent normalization scheme. Experiments on Qwen2.5-Math models show improvements across mathematical reasoning benchmarks.

Critical strengths
  1. The method uses verifiable terminal rewards to construct process signals, avoiding the need for a separately trained process reward model or critic.
  2. The proposed TreeRPO shows improvement on Qwen2.5-Math models across mathematical benchmarks.
Critical weaknesses
  1. SPO-tree already employs fixed-length segments, recursive averaging of terminal rewards, sibling-relative advantage estimation, and clipped policy optimization. These mechanisms closely match the central formulation in Sections 3.1–3.5. However, SPO-tree is neither discussed nor directly compared, making the methodological novelty unclear.
  2. TreeRPO generates a substantially larger tree than the eight independent trajectories used by GRPO. Appendix A.2 reports theoretical generation bounds of 224,256 versus 9,216 tokens per question. It is difficult to determine whether the reported accuracy improvements arise from the proposed optimization mechanism or additional sampling and optimization resources. And the actual generation costs and wall-clock training times are not provided.
  3. The proposed method jointly introduces tree-based credit assignment, reward-range filtering, and mean-dependent advantage scaling. The ablations of key design choices are lacked.
  4. The macro accuracy improvement decreases to 0.7 percentage points for the 7B model, raising the concerns of the effectiveness of the method for larger models, and all experiments are conducted on Qwen2.5-Math-1.5B/7B, a relatively old model family, with comparisons limited to vanilla GRPO, it remains unclear whether the proposed method provides meaningful improvements over stronger recent baselines or applied to more capable backbones.
Questions for authors
  1. How sensitive is TreeRPO to the branching factor, maximum depth, and segment length? Does deeper branching consistently improve performance, or could a shallower tree achieve comparable results with lower sampling costs?
  2. Eq. (4) divides centered rewards by (\mu(1-\mu)), which can amplify advantages when the group mean approaches 0 or 1. How frequently do such extreme group means occur during training, and what prevents excessively large advantages from destabilizing optimization?
  3. TreeRPO divides reasoning trajectories into fixed 384-token segments rather than semantic reasoning steps. How sensitive is the effectiveness of local credit assignment to this segmentation choice? Could arbitrary boundaries weaken the correspondence between estimated continuation values and meaningful reasoning decisions?
Reviewer_qeaUOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper targets credit assignment in RLVR, where the verifier only scores the final answer. TreeRPO replaces flat rollouts with a sampled tree: the question is the root, edges are token blocks, and branches grow until a stop token or a depth limit. Leaf rewards are averaged bottom-up, so each internal node gets a fractional reward, roughly how often its continuations end up correct. Siblings share a prefix and form a comparison group for a GRPO-style clipped update, with range filtering and a variance rescaling on top. Against GRPO on Qwen2.5-Math-1.5B and 7B (trained on MATH, four benchmarks), the paper reports a macro gain at 1.5B, a smaller one at 7B, and shorter 1.5B responses. The authors themselves say that branching, filtering and scaling are not separated, and that the token saving is at evaluation time, not in training cost.

Critical strengths
  1. The idea is a sensible and cheap answer to a real problem. Trajectory-level normalization treats two solutions as wholes even when they share a good prefix and only diverge late, and PRMs fix this at the cost of an extra model and process labels. Reusing the terminal verifications at several depths, and only comparing siblings so the context is held fixed, gets local signal out of the verifier you already have. Prefix sharing keeps the token cost well below a naive path count. This is the part worth building on, and it is why I am not at a clear reject.

  2. The paper is careful about what its quantities mean. Section 3.2 says a node reward of 0.75 means the descendants did well on average, not that the step is 75% correct, and it separates recursive averaging from a plain leaf average when branches stop at different depths. Section 4.3 says the token saving is at evaluation, not training, and Appendix A.2 says matching path length does not match sampling budget. I appreciate this, even though several of the limits it names are exactly what weakens its claims.

Critical weaknesses
  1. The comparison cannot isolate tree-relative supervision, and the paper gives no measurement that would. Three things change at once and none is ablated, which the authors acknowledge in Section 4.5.
  • Budget. Appendix A.2 gives a full-expansion ceiling of 584 edges and 224,256 generated tokens per question, against 9,216 for eight GRPO rollouts. The realized number is never reported, and the ceiling is only a bound. Even a few-fold difference would be large next to a 2.9-point gap.
  • Update weighting. Eq. (7) averages equally over retained groups, so each depth counts by how many groups it has; a full tree gives 1, 8 and 64 groups at depths 0-2 (my own count, not stated in the paper). That weighting is another difference between the arms. The minibatch is also defined differently: 64 for GRPO, "half of constructed training-data size" for TreeRPO (Section 4.1).
  • Attribution. With branching, tau-filtering and the Eq. (4) rescaling changed together, and curves that are "not independent replications" (Section 4.2, l.322-323), the 1.5B gain can't be credited to the mechanism the paper argues for. At 7B the ordering in Figure 3 is fairly consistent on several benchmarks, but the gains are 0.0-1.2 points, with the same budget difference and no seed replication.
  1. The length result may come from the objective itself, and the headline AIME24 number does not match either stated protocol.
  • Length. Section 4.6 says the objective "does not directly reward a shorter evaluation response" and reads the 18.1% reduction as learned economy. But Eq. (2) treats stopping and continuing siblings differently: a child that stops is scored 0 or 1, while a continuing sibling gets the mean over its continuations. That need not favor stopping in expectation, but it gives stopping decisions more extreme advantages in both directions. The paper also never says how a branch that hits depth D without a stop token is scored (Section 3.1); if it gets 0, continuing is penalized directly. Since brevity is one of the two empirical claims, this needs to be ruled out.
  • AIME24. Table 1 reports 16.8% for TreeRPO-1.5B. With 30 problems this cannot come out of either protocol: over 240 samples the nearest values are 16.667% and 17.083%, and over 480 they are 16.667% and 16.875%. The other two AIME24 entries are attainable, so the problem is specific to one of the largest per-benchmark gains. Together with the Avg@8/Avg@16 ambiguity that Appendix A.1 says "cannot be resolved from the manuscript archive alone," I cannot match this number to any stated procedure.
Questions for authors
  1. What is the measured generation cost per question for both arms (generated tokens, tree occupancy, retained groups, wall-clock or GPU-hours)? A GRPO baseline at matched generated tokens would settle the budget question.

  2. How is AIME24 = 16.8% obtained? It is not a mean of 8 or 16 binary samples over 30 problems. Is it 30 problems, 8 or 16 samples, or some other aggregation?

  3. How is a branch truncated at depth D verified, and is it scored 0? If so, how much of the 18.1% length reduction survives without truncated-but-correct prefixes, and does the unaveraged stopping reward change how often the policy stops early?

  4. Do you have runs with tree sampling plus standard GRPO normalization, or without range filtering? What share of the gradient comes from each depth?

  5. Are the Table 1 numbers from single runs, and is the checkpoint the last one or a selected one? A second seed or a paired interval for the 1.5B gain would help. Which optimizer, clipping epsilon and inner epochs were used, and what is the "constructed training-data size" behind TreeRPO's minibatch?

Not part of my assessment: semantic instead of fixed-token segmentation, and spending branching budget on uncertain prefixes (as Appendix A.4 notes), seem like natural next steps.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.