acceptodds
Withdrawn from ICLR 2027

Adaptive Uncertainty-Aware Tree Search for Robust Reasoning

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Inference-time reasoning scaling has significantly advanced the capabilities of Large Language Models (LLMs) in complex problem-solving. A prevalent approach involves external search guided by Process Reward Models (PRMs). However, a fundamental limitation of this framework is the epistemic uncertainty of PRMs when evaluating reasoning paths that deviate from their training distribution. In this work, we conduct a systematic analysis of this challenge. We first provide empirical evidence that PRMs exhibit high uncertainty and unreliable scoring on out-of-distribution (OOD) samples. We then establish a theoretical framework proving that while standard search incurs linear regret accumulation, an uncertainty-aware strategy can achieve sublinear regret. Motivated by these findings, we propose Uncertainty-Aware Tree Search (UATS), a unified method that estimates uncertainty via Monte Carlo Dropout and dynamically allocates compute budget using a reinforcement learning-based controller. Extensive experiments demonstrate that our approach effectively mitigates the impact of OOD errors.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
large language model

Reviews

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

This paper studies epistemic uncertainty in PRM-guided test-time search, arguing that PRMs score reasoning traces outside their training distribution unreliably. The authors present empirical evidence that MC Dropout score variance correlates with PRM miscalibration, and give a stylized analysis contrasting linear degradation under uncertainty-agnostic selection with sublinear degradation under UCB-style selection. Building on this, they propose UATS, which estimates PRM uncertainty via MC Dropout. A heuristic variant (H-UATS) uses a variance threshold and an optimism margin to selectively re-evaluate uncertain candidates before score-proportional expansion. An adaptive variant (A-UATS) replaces the fixed hyperparameters with an MLP controller trained via behavior cloning and REINFORCE. Experiments on MATH-500 and AIME24 across 15 policy–PRM pairs, plus a HumanEval extension, show consistent improvements over Best-of-N, Beam Search, DVTS, REBASE, and DoRA.

Critical strengths
  • The evaluation covers 15 policy–PRM pairs, seven candidate budgets, and two math benchmarks, with five runs each, plus a code-generation extension. The improvements over the baselines are consistent in direction across all reported pairs, and the per-pair results are fully reported in the appendix.

  • H-UATS is training-free, requires no change to the PRM, and can be added to existing score-proportional search procedures. The appendix includes sensitivity analyses for the main hyperparameters (τ\tau, δ\delta, dropout rate, K0K_0, controller size).

Critical weaknesses
  • Proposition 4.1 follows almost directly from its assumptions. Given (ii) a loss of at least Δ\Delta per selection error, and (iii) an error probability of at least ρ\rho under OOD and zero otherwise, the linear bound is obtained by summing ερΔ\varepsilon\rho\Delta over TT steps.

  • In Proposition 4.2, the confidence term Ut=2ln⁡t/KtU_t=\sqrt{2\ln t/K_t} depends only on tt and KtK_t, so it is identical for all candidates in Ht\mathcal{H}_t. Adding it therefore does not change the ranking, and the selection rule is equivalent to taking the argmax of the posterior mean. The sublinear bound thus reflects concentration from averaging Kt=Ω(t)K_t=\Omega(t) unbiased samples, not the use of uncertainty in decision making.

  • The analysis does not cover the variance threshold τ\tau, selective re-evaluation, the optimism margin δ\delta, or the RL controller. App. D.5 acknowledges this for the controller, and App. D.7 notes that systematic PRM bias is likewise outside its scope. In addition, the link between method and analysis (Sec. 3.3, Prop. 4.2) relies on treating MC Dropout passes as samples from p(ϕ∣DPRM)p(\phi\mid\mathcal{D}_{\text{PRM}}). Here dropout is enabled at inference and its rate is tuned per verifier (0.07 vs. 0.10, App. G.6). Under these conditions, this interpretation needs stronger justification. For instance: were these PRMs trained with dropout, and does the dropout mean remain a faithful estimate of the original PRM score?

  • Figure 1 and App. H (case 2) describe UATS as down-weighting high-score, high-uncertainty steps and favoring reliable low-variance nodes. Sec. 5.2, however, contains no explicit uncertainty penalty. Uncertain candidates are retained via an optimistic score, given additional evaluations, and then expanded according to their mean score. A high-score, high-uncertainty step is therefore corrected only if additional sampling lowers its mean, which is not guaranteed.

Questions for authors

1. Compute accounting.

Sec. 6.1 states that methods are compared under the same candidate budget NN. App. E.1 instead converts generation into PRM passes using a fixed ratio (571/32 ≈ 17.8) and states that baselines spend the saved budget on additional candidates. App. F.3, in turn, describes FLOPs-based matching.

  • Which accounting underlies Tables 1, 4 and 5?
  • Is the 17.8 ratio applied uniformly across policies (0.5B–8B) and PRMs (1.5B–7B)? Was PRM latency measured with batched or sequential passes?
  • In the "w/o Uncert." ablation, how is the budget freed by removing MC Dropout reallocated?

2. Hyperparameter selection protocol.

App. E.1 states that MATH-500 is used only for evaluation. Yet App. G sweeps τ\tau, δ\delta, the dropout rate and K0K_0 on MATH, and Table 6 selects the controller architecture on MATH-500. The best entry in Table 6 (86.54) coincides with the corresponding entry in Table 4.

  • Was a held-out split used for these choices, and how were the baselines' hyperparameters chosen?
  • Eq. 7 defines σR2\sigma_R^2, but Eq. 8 compares σR\sigma_R with τ\tau, whereas the values in Fig. 1 and App. G.2–G.3 are on the variance scale. Does τ=0.003\tau = 0.003 threshold the standard deviation or the variance?

3. Controller details.

  • Is a single controller, trained on four policy–PRM pairs from the MATH training split, used for all 15 pairs, for AIME24, and for HumanEval?
  • Are the state features normalized across PRMs with different score and variance scales?
  • How are the action ranges constrained? In particular, can βt\beta_t and γt\gamma_t lead to spending beyond the matched budget?
  • Please specify the action distribution, the REINFORCE baseline/advantage, and the BC objective.
  • The cost term changes the reward by at most λ=0.05\lambda = 0.05. Is there evidence, e.g., from existing training logs, that it measurably affects the learned policy?
Reviewer_ekGMOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes a search method that uses repeated PRM evaluations to decide which reasoning candidates need further checking and how to allocate computation between checking and expansion. The experiments report improvements across multiple model combinations. The main theoretical claim is that accounting for uncertainty changes linear accuracy degradation into sublinear degradation.

Critical strengths
  1. The paper studies a useful practical question: when is it better to check an existing candidate than to generate another one?
  2. The evaluation covers multiple policy–PRM combinations and includes FLOPs comparisons, variability across runs, and sensitivity analyses.
Critical weaknesses

1. The final-accuracy bounds are not established by the current proofs. There are two distinct issues. In Proposition 4.1, the proof assumes that correct selections cannot improve success probability, but this assumption is missing from the statement. In Proposition 4.2, Appendix B equates cumulative local regret with the loss in final accuracy. This equality generally does not hold: selecting the best available candidate and preserving the parent’s value are different properties. The authors should specify the value model and assumptions needed for these steps, or restrict the results to cumulative local regret. Since accuracy is bounded, the claimed degradation rates also need a clearly stated range of applicability.

2. The UCB term does not affect selection in Proposition 4.2. All candidates at a given step receive the same confidence bonus. Adding or removing this bonus therefore leaves the selected candidate unchanged. The concentration argument also works for ordinary selection by average score. The explanation following the proposition attributes the improvement to the UCB term, but the analysis only supports the benefit of increasing the number of independent, unbiased evaluations. It does not establish an additional benefit from uncertainty-dependent selection.

3. The theoretical comparison uses different scoring budgets. Single scoring requires MTMT PRM evaluations, while Kt=Θ(t)K_t=\Theta(t) requires Θ(MT2)\Theta(MT^2). The improved bound therefore comes with more computation. At the same horizon and total scoring budget, uniform repeated scoring already achieves the same order of bound.

4. Source of uncertainty The connection between dropout variability and the stated Bayesian posterior needs further explanation. The implementation also uses data-dependent evaluation counts and softmax branch allocation, whereas the theorem analyzes a simpler selection rule. These are gaps in justification and coverage; they do not by themselves show that the empirical method is ineffective.

Questions for authors

Posterior uncertainty depends on the prior and likelihood, not only on the training data. For example, a point-mass prior yields zero posterior parameter variance whenever the observed data have positive likelihood. The paper does not sufficiently specify which posterior its frozen PRMs represent or explain why dropout samples approximate that posterior. Repeated dropout evaluations estimate variance under the dropout distribution, but the connection to the stated Bayesian uncertainty remains unclear. Could the authors justify the connection between dropout sampling and the stated posterior? Alternatively, could they clarify the empirical evidence supporting dropout variance as a proxy for PRM prediction errors, particularly under distribution shift?

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

The paper studies whether process reward models (PRMs) can reliably guide external reasoning search when policy-generated trajectories are out of distribution relative to PRM training data. It proposes UATS, which uses Monte Carlo Dropout score means and variances to allocate additional verifier evaluations and candidate expansion; H-UATS uses an uncertainty threshold, while A-UATS learns budget allocation with a controller initialized by behavioral cloning and optimized with REINFORCE. The paper evaluates the methods on MATH-500 and AIME24 against several search baselines, reports FLOPs-matched comparisons and ablations, examines uncertainty calibration, and presents a simplified theoretical analysis of point-estimate versus uncertainty-aware selection.

Critical strengths

S1: The paper turns verifier uncertainty into a concrete budget-allocation mechanism: uncertain but competitive candidates can receive additional PRM evaluation, and A-UATS learns how to allocate evaluation and expansion resources. The reported evaluation spans multiple frozen policy–PRM combinations, making the approach more informative than a single-configuration demonstration.

S2: Reported results on MATH-500 and AIME24, together with ablations in which removing uncertainty handling reduces accuracy in the listed configurations, provide empirical support for the proposed mechanism. These results are encouraging, although their evidential strength depends on the cost accounting and uncertainty analysis being sufficiently documented.

Critical weaknesses

W1: The theoretical guarantees rely on assumptions including unbiased PRM estimators and distributional conditions that the paper itself characterizes as simplifying; the analysis does not establish comparable guarantees under systematic verifier bias or dynamic distribution shift. The claimed linear-to-sublinear degradation should therefore be interpreted within the simplified model, rather than as a general guarantee for realistic search.

W2: The uncertainty mechanism treats MC Dropout variance as a proxy for verifier-side epistemic uncertainty. The reported association with calibration metrics does not by itself establish reliable OOD discrimination or transfer of thresholds across PRMs, policies, and tasks; the paper also notes that the suitable dropout rate depends on the verifier.

Questions for authors
  1. For Proposition 4.2 (PDF p. 6) and its proof (Appendix B, PDF p. 14), what boundedness, independence, or other concentration conditions are required for the Hoeffding bound, beyond unbiasedness? How does the candidate-count factor in the union bound behave when candidates are generated online, and which parts of these conditions are intended to hold for practical PRMs?
  2. The paper reports FLOPs-matched benefits, while Appendix E.1 (PDF p. 17) converts one generation step to approximately 18 stochastic PRM passes using measured latency. Could the authors provide the per-model cost accounting and clarify whether it includes MC Dropout, controller training and inference, and differences in hardware utilization?
  3. Appendix E.1 (PDF p. 17) says MATH-500 and AIME24 are evaluation-only while the controller is trained on MATH. Were controller training, hyperparameter selection, and threshold tuning strictly separated from the evaluation data, and were training/evaluation problem overlaps checked?
  4. The paper's calibration analysis and verifier-specific dropout sensitivity leave uncertainty about transfer. What evidence supports using variance to identify OOD candidates across different PRMs, policies, or tasks, rather than only as a configuration-specific signal?

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

Related papers

Discussion (0)

Sign in to comment.