- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper proposes a method to use MCTS for training LLMs while accounting for evaluation uncertainty.
Critical strengths
-
Much of the idea seems sound.
-
Results seem promising.
Critical weaknesses
Novelty:
-
Up until section 4.2, effectively nothing is novel - it's just a rehashing of the equations from Epistemic MCTS (EMCTS, [1]). While EMCTS is cited briefly in the related work, these sections (4, 4.1) are presented as novel, and they are almost entirely not.
-
In the related work, other MCTS-for-LLM work is presented with "A separate line of work applies tree search at inference time to improve a single response (citations). UMCTS-GRPO searches only during training and evaluates the policy without test-time search. " The AlphaZero [2] line of work has shown us that there is effectively no difference between searching for acting (producing an improved policy at the root and selecting an action from it) and searching for learning (producing an improved policy at the root and learning from it). So I don't think this line is sufficient to cover the parallels between this work and the prior work in this area, which renders me unable to establish the remaining novelty of this work.
Soundness and theoretical motivation:
There is effectively no theoretical motivation for the way uncertainty is used, except for a little in 4.1 (which is not novel). This is part of a larger problem: a better framing of the uncertainty is very necessary, in my opinion. MCTS already addresses uncertainty in the returns with the visitation counts. That's the purpose of the PUCT search term: to trade off uncertainty (opt. in the face of unc.) vs probability of promising-ness under the policy prior. The uncertainty that EMCTS motivates is epistemic, and is not addressed by this PUCT term, which necessitate the second term (Eq 3 in this work, which is Eqs 10 and 11 in EMCTS). This work does not make it clear why it is correct to quantify and use the type of uncertainty raised by this work in this way.
In addition, the "confidence weighted advantages" are not theoretically motivated, nor do I find the theoretical results of section 4.3 convincing. If my understanding is correct, Proposition 1 shows properties of . But it's not clear to me that is itself sound: the advantage is usually computed . A policy which selects advantage positive actions improves with respect to . However, is defined with respect to an uncertainty weighting, instead of policy probabilities. As a result, it's not clear to me that it is sound as a quantity for improvement to start with.
Statistical Significance:
Is missing from the majority of results. When it is not missing, an +- 1 STD is used, which is not the appropriate metric to evaluate the stat. signif. of the mean. Please include a principled confidence interval, such as a 95% Gaussian CI (approx. +- 2 Standard Error of the Mean (SEM)).
Presentation:
-
I would like to preface this point by saying that I strongly approve of the choice to try to adhere to standard RL notation (states, rewards, transitions). It's not always done in LLM papers, and I think it's the right choice here and I commend the authors on taking it. That being said, there are a large number of issues with the notation, examples below:
- R is called reward but defined, described and treated as a return. They are not the same thing. The reward is defined for a transition, and the return is defined for a trajectory. Respectively, the value is the expected return, eg the expectation over the sum of (often) discounted rewards.
- The paper uses both observations and states, implying a POMDP (never defining either an MDP or a POMDP). Observations are usualy reserved specificaly to denote the information that is available to the agent and is not the complete state, and introduce a lot more complexity to (the already complex enough) MDPs. This does not seem to me to be necessary here, in which case I strongly recommend trying to change the notation around classical MDP notation, and defining MDPs. Otherwise, I would suggest defining POMDPs properly in the preliminaries section.
- The term advantage is well defined in RL: . It sort of makes sense to me to call an advantage, except that it's not clear why it's normalized by the STD and why it's called as opposed to .
- Q is presented as a return-estimate, which it is not. It is an expected return (eg the value, and specifically the action-value) estimate. The paper will benefit from defining all of this in the preliminaries section, which will also allow for a more natural definition of the advantage.
- The prior P, transition model , policy (which is never defined I believe) are all confusing choices for notation. The transition probabilities can safely be P. The "prior" is usually the "prior policy", eg the LLM, eg . It's not clear to me what is, how it's different from , how its different from the prior P, is P not , and if there is a reason to use these confusing terms.
- G is defined as a "group" of trajectories. What is a group? A set?
-
Missing preliminaries:
- MCTS is not defined or presented, making it very hard to understand the terminology chosen by the authors. For example, what is a rollout? in MCTS, these are usually the rollouts from a leaf during expansion. But it can also be the trajectory from the root to a leaf during selection. As well as other things.
- MDPs, POMDPs and value functions are never defined, resulting in many of the notation problems mentioned above.
-
Proofs are not linked to from the body of the paper (unless ive missed that).
-
Evaluation metrics are cited but not explained.
-
Policy optimization is placed structurally as part of "UMCTS", but if I understand correctly its explicitly applied to extract policy target from the search, once it has concluded. If this is the case, please consider changing the structure of the contribution sections, seperating how MCTS is modified from how its being used.
-
"For each prompt we build M independent trees" sounds cool, not standard, and leaves me very unclear on how the algorithm actually works.
-
"Because the language action space cannot be enumerated": can it not? I thought LLMs had a finite output space of size num. possible tokens. I assume the authors are correct and the misunderstanding is mine, but it's not clear to me what this means exactly.
-
The results are presented in tables. Tables are the single least informative way to present results. If the most informative results to present are individual numerical scores (which seems unlikely to me for a learning algorithm), consider presenting them in bar charts instead.
-
I personally find the diagrams confusing rather than clear. For example, why do the search / expansion / backup trajectories and / or the trees seem to be inconsistent within the same figures?
[1] Oren et. al., Epistemic Monte Carlo Tree Search. ICLR 2025.
[2] Silver et. al., A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science 2018.
Questions for authors
Please see the weaknesses section.
4 comments
Author Response 2
(4) Soundness of .
We understand the concern to be that uses uncertainty weights where uses policy probabilities. App. C now explains the construction in three steps.
First, plays the role of the state value. It is an estimate of from the siblings sampled at , just as the group mean is in GRPO, and subtracting it centers the comparison and reduces the variance of the update.
Second, the weights. Sibling values are estimated with different precision, and inverse-uncertainty weighting is the standard way to average such estimates, since it gives the lowest-variance average. When all siblings are equally uncertain, reduces to the plain mean (Prop. 1iii).
Third, the gate. lies in , so it reduces the magnitude of an advantage and leaves its sign unchanged (Prop. 1i). Its role is similar to that of in GAE, where some magnitude is given up for less noise. For two siblings, the update always raises the better action relative to the worse one (Prop. 2).
As for the name, dividing by the sibling standard deviation is the per-group standardization of GRPO. We now call the quantity the standardized local advantage and relate it to in App. C.
(5) Statistical significance.
We give ±2 SEM intervals below. The tables keep mean ± std, because another reviewer asked for standard deviations, and App. D states the conversion (±2 SEM = 1.15 × std for three runs).
For QA, every setting in Table 1 now has three independent training runs. Training follows the Tree-GRPO configuration, including its source of randomness (unseeded data shuffling and tree expansion, as in their released code). With ±2 SEM over runs, Tree-GRPO lies below our interval in nine of ten settings, for example 49.1 ± 0.3 vs. 47.5 (1.5B single-hop) and 47.1 ± 0.3 vs. 45.3 (14B multi-hop). The exception is 7B multi-hop (38.0 ± 0.2 vs. 37.8), where the two methods are on par.
For ALFWorld at 7B (seeds 0, 1, 2), the intervals are UMCTS-GRPO 94.2 ± 2.2, GiGPO 90.8 ± 1.5, and Tree-GRPO 76.5 ± 2.9.
(6) Notation, preliminaries and structure.
We revised the following as you suggested:
| Topic | Change |
|---|---|
| Return vs. reward | §3 now calls the return and states that the reward is non-zero only at termination |
| Background | §3 now gives the MDP formulation and introduces MCTS. A new App. H defines , , |
| Described as an estimate of the action value | |
| "Rollout" | Defined in §3: a simulation is one select–expand–rollout–backup cycle, and a rollout is the continuation from a new node to the end |
| Advantage | is named the standardized local advantage; App. C relates it to and explains the division by the sibling std |
| Proofs and metrics | The main text now links Proposition 1 to its proof (App. C) and defines EM and success rate in §5 |
For the remaining points:
- States and observations. The setting is a fully observed MDP. The state is the whole interaction history, (§3.1). "Observation" is the ReAct term for the tool's output, which becomes part of that history; it is not a partial view of a hidden state. §3 now says this explicitly.
- Symbols. The notation table (App. A) lists every symbol: is the policy being trained; is what the text calls the behavior policy, a frozen copy of used to collect data; is the reference policy of the KL term; is the search prior; and is the transition model. §4.1 now says this where first appears, and App. H restates these roles in one place.
- Enumerating actions. An action is a complete agent step: a thought followed by a textual action (§3.1) of up to 500 tokens (App. D). A single token is only a fragment of it. The number of possible steps is about with , so the children of a node cannot be listed and have to be obtained by sampling.
- independent trees. This is the Tree-GRPO setup we build on (§3.2): each prompt gets separate trees. Outcome advantages compare the leaves of all trees, and local advantages are computed inside each tree. The full procedure is Algorithm 1 in App. B, referenced at the start of §4.
- "Group". follows GRPO's usage (§3.2): the set of trajectories sampled for one prompt.
- Structure. The search is §4.1. Policy optimization is the last paragraph of §4.2, with its own title, because it takes the advantages defined there as input.
On the tables, we keep Table 1 in the main text because prior work on these seven benchmarks is compared through per-dataset numbers.
If the revised §3–§4 and Appendices C and H address your concerns on soundness and presentation, we would be grateful if you would reconsider those scores.
I thank the authors for their rebuttal and the improvements to the paper.
My concerns remain, unfortunately, for the most part unaddressed.
Soundness and theoretical motivation:
MCTS is already designed to account for return variance (aleatoric uncertainty in return). It enters the theoretically motivated search policies (UCT, PUCT) in the count-based coefficient, under the assumption that leaves have the same variance.
The authors observe that in fact, the leaves do not have the same variance, and that EMCTS provides an alternative approach for propagating uncertainty.
However, EMCTS's (along with UBE's) uncertainty propagation mechanism is motivated specifically under the assumption that this uncertainty is not aleatoric, so this approach is not suited (or at least, not well motivated) for propagating this type of uncertainty.
Here is a paper that treats non-uniform leaf uncertainty, if memory serves:
[1] Tesauro, G., Rajan, V. T., & Segal, R. (2010). Bayesian Inference in Monte-Carlo Tree Search. UAI 2010.
I think it should be contrasted with, discussed, and perhaps even adopted into the authors method.
Statistical significance:
Every result presented in the paper needs to be paired with the appropriate metric for statistical significant. It is always unfortunate when reviewers appear to have conflicting requests. That being said, I cannot recommend the paper for acceptance until all quantities are paired with the appropriate metric of statistical significance, or it is explained connivingly why one need not, or cannot, be included. The appropriate metric for statistical significance depends on the purpose of the result presented, but when mean's presented, these are generally confidence intervals over the mean, such as 2*SEM based. STD is not a confidence interval.
Unless I misread (in which case, please correct me), the vast majority of the results presented in the paper are still not paired with a metric of statistical significance (Tables 1-5, Figure 4, for example).
Until both of these issues are fully addressed, I will not be able to raise my score. That being said, I think the underlying idea and method have promise, and even if the paper does not get accepted at this submission cycle, I would like to encourage the authors to keep following this direction.
Author Response
Thank you for the comments, the reference, and the encouragement. We address your two issues in order; the first has two parts.
1a. The EMCTS/UBE backup is motivated for epistemic uncertainty, while ours is variance in the return.
Propagating return variance does not need an epistemic assumption. The variance of the return has its own recursion, the law of total variance (Sobel, 1982). For a policy and deterministic transitions,
Our backup has the same two parts: Eq. 19 adds the disagreement between child values, and Eq. 4 carries the subtree statistic upward with . In QA the retriever is deterministic, so this variance comes entirely from the later choices of the policy. §4.1 states this motivation, App. G gives the recursion, and UBE is cited only for the recursive form.
1b. Tesauro et al. (2010) should be contrasted, discussed, and perhaps adopted.
We discuss Tesauro et al. (2010) in §2, contrast it with our method in App. G, and test its exploration rule below. They explore with a posterior standard deviation that shrinks with the visit count, which in our setting is the return dispersion scaled by the count, (Table 10):
| Bonus | Single-hop EM | Multi-hop EM |
|---|---|---|
| (count-scaled, one run) | 48.4 | 19.6 |
| (no count scaling, one run) | 48.5 | 19.5 |
| Our full statistic (three runs, ±2 SEM) | 49.1 ± 0.3 | 20.2 ± 0.5 |
Count scaling makes no measurable difference here: an edge holds at most three returns, so the scaling changes the bonus by a factor of at most . We therefore keep the unscaled form. We did not adopt the full Bayesian backup because it targets the value of best play, while an advantage needs the value under the current policy.
2. Every result should be paired with a measure of statistical significance.
Every main result and every ablation of UMCTS-GRPO reports a mean with a ±2 SEM interval over three independent runs, in the table itself:
| Result | What is reported |
|---|---|
| Table 1 | ±2 SEM on all ten UMCTS-GRPO category averages, three independent training runs each. Baseline rows are the numbers reported in the Tree-GRPO paper, which gives one value per setting. |
| Table 2 | ±2 SEM on the overall success rate of every RL method, three seeds each. |
| Table 4 | ±2 SEM on the full method and all four ablations, three runs each. |
| Table 3, Figures 4 and 5 | Single-run budget, training-dynamics, and sensitivity analyses, used for trends. A training run takes 8 to 48 hours on 4 GH200 gpus/8 H200 gpus, so the repeated runs went to the main results and the ablations. |
| Table 5 | Notation table. |
Per-run values for QA and the ablations are in App. I.
Under these intervals, Tree-GRPO lies below ours in nine of ten settings of Table 1, and the tenth (7B multi-hop, 38.0 ± 0.2 vs. 37.8) is on par. On ALFWorld at 7B, UMCTS-GRPO reaches 94.2 ± 2.2 against 76.5 ± 2.9 for Tree-GRPO.
We believe this addresses both issues and would be grateful if you would reconsider your rating.
Author Response 1
Thank you for the careful reading. Your comments on notation and structure were helpful, and we have uploaded a revised PDF with the changes in blue. We reply in two parts. This part covers novelty and the role of U; the next covers soundness, statistics and presentation.
(1) Relation to EMCTS.
You are right that §4.1 builds on EMCTS, and the text should have said so. Two elements come from prior work: the recursive uncertainty backup (Eq. 4), which follows the uncertainty Bellman equation, and the additive uncertainty bonus in the selection score (Eq. 3), which follows EMCTS. The submission cited EMCTS only in the related work. §4.1 now cites UBE and EMCTS at both places, and a new App. G compares the two methods.
That said, §4.1 differs from EMCTS in two respects. The first is where the uncertainty comes from. EMCTS propagates the uncertainty of learned value or dynamics models, and we have no learned model. Our U is computed from the returns the environment actually gave: how much they disagree, plus the surprisal of the action and the uncertainty of the subtree below (Eq. 5). No critic or uncertainty estimator is trained. The second is the action space. Tree search needs to know the children of a node. A board game has a fixed list of legal moves, but an agent step is free text and has no such list, so we build one by sampling several next steps at the same prefix, merging near-duplicates, and using the cluster frequency as the prior.
Our main contribution is in §4.2, where the same statistic is used a second time with the opposite effect. In search, a high U gives a branch more rollouts; in learning, a high U gives its comparison less weight. EMCTS uses uncertainty for selection only, and to our knowledge neither EMCTS nor AlphaZero uses it to weight credit. This second use matters empirically: removing it lowers multi-hop EM from 20.2 ± 0.4 to 18.9 ± 0.5 (three runs each, and every run of the full method is above every run without it).
(2) Relation to AlphaZero.
We agree that searching to act and searching to learn are closely related. The related-work sentence you quote was meant for methods such as ToT (Yao et al., 2023) and LATS (Zhou et al., 2023), which run the search every time the model is used. We added a sentence on AlphaZero there and a comparison in App. G.
What separates us from AlphaZero is what we take from the tree. AlphaZero trains the policy toward the root visit distribution and also trains a value network. We instead use the Monte Carlo returns at every branching node, at any depth, to form advantages, apply a clipped policy-gradient update, and train no value network.
(3) Why U in addition to visit counts.
Visit counts treat two branches with the same number of visits as equally well known, which is often not the case. Take two branches that have each been visited twice, one returning (1, 1) and the other (1, 0). With equal priors, PUCT gives both the same bonus, even though the second estimate is less certain. U captures this difference. Variance-aware bounds such as UCB-V (Audibert et al., 2009) rest on the same idea, namely that a confidence width depends on the count and on the observed spread. In our score, PUCT supplies the count part and U the spread part. §4.1 now states this.
On the kind of uncertainty: in EMCTS it is about a learned model. We have none, so what remains uncertain is whether the average of a few sampled returns (at most three in QA) is close to the true value, and the spread of those returns is what indicates this. We checked it with rollouts the tree never saw. Where U is high, the tree's value is 3.1× further from the value those rollouts give (488 branches, up to 8 rollouts each; 95% Confidence Interval [1.6, 6.4], permutation p<0.001).
We also tried the count-scaled form σ^/N. It lands within 0.7 points of the original (48.4 / 19.6 vs. 49.1 / 20.2 EM), which is what one would expect with so few visits per branch.