Adaptive Uncertainty-Aware Tree Search for Robust Reasoning

• URL: http://arxiv.org/abs/2602.06493v1
• Date: Fri, 06 Feb 2026 08:40:05 GMT
• Title: Adaptive Uncertainty-Aware Tree Search for Robust Reasoning
• Authors: Zeen Song, Zihao Ma, Wenwen Qiang, Changwen Zheng, Gang Hua,
• Abstract summary: Inference-time reasoning has advanced the capabilities of Large Language Models (LLMs) in complex problem-solving.<n>A prevalent approach involves external search guided by Process Reward Models (PRMs)<n>We provide empirical evidence that PRMs exhibit high uncertainty and unreliable scoring on out-of-distribution (OOD) samples.<n>We then establish a theoretical framework proving that while standard search incurs linear regret accumulation, an uncertainty-aware strategy can achieve sublinear regret.
• Score: 30.006968507593452
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Know What You Know: Metacognitive Entropy Calibration for Verifiable RL Reasoning [31.629261193485053]
  Large reasoning models (LRMs) have emerged as a powerful paradigm for solving complex real-world tasks.<n>Most existing outcome-only RLVR pipelines rely almost exclusively on a binary correctness signal and largely ignore the model's intrinsic uncertainty.<n>We propose EGPO, a metacognitive entropy calibration framework that explicitly integrates intrinsic uncertainty into RLVR for enhancing LRMs.
  arXiv  Detail & Related papers  (2026-02-26T08:40:06Z)
• Native Reasoning Models: Training Language Models to Reason on Unverifiable Data [16.065264121785294]
  We introduce NRT (Native Reasoning Training), a novel framework that cultivates complex reasoning.<n>NRT reframes the training problem by treating the reasoning process as a latent variable.<n>NRT achieves state-of-the-art performance among verifier-free methods.
  arXiv  Detail & Related papers  (2026-02-12T04:15:46Z)
• BAPO: Boundary-Aware Policy Optimization for Reliable Agentic Search [72.87861928940929]
  Boundary-Aware Policy Optimization (BAPO) is a novel RL framework designed to cultivate reliable boundary awareness without compromising accuracy.<n>BAPO introduces two key components: (i) a group-based boundary-aware reward that encourages an IDK response only when the reasoning reaches its limit, and (ii) an adaptive reward modulator that strategically suspends this reward during early exploration, preventing the model from exploiting IDK as a shortcut.
  arXiv  Detail & Related papers  (2026-01-16T07:06:58Z)
• Towards Reliable LLM-based Robot Planning via Combined Uncertainty Estimation [68.106428321492]
  Large language models (LLMs) demonstrate advanced reasoning abilities, enabling robots to understand natural language instructions and generate high-level plans with appropriate grounding.<n>LLMs hallucinations present a significant challenge, often leading to overconfident yet potentially misaligned or unsafe plans.<n>We present Combined Uncertainty estimation for Reliable Embodied planning (CURE), which decomposes the uncertainty into epistemic and intrinsic uncertainty, each estimated separately.
  arXiv  Detail & Related papers  (2025-10-09T10:26:58Z)
• Lost at the Beginning of Reasoning [85.17612793300238]
  We show that the first reasoning step exerts a disproportionately large influence on the final prediction.<n>We propose an efficient sampling strategy that leverages a reward model to identify and retain high-quality first reasoning steps.
  arXiv  Detail & Related papers  (2025-06-27T09:53:57Z)
• TULiP: Test-time Uncertainty Estimation via Linearization and Weight Perturbation [11.334867025651233]
  We propose TULiP, a theoretically-driven uncertainty estimator for OOD detection.<n>Our approach considers a hypothetical perturbation applied to the network before convergence.<n>Our method exhibits state-of-the-art performance, particularly for near-distribution samples.
  arXiv  Detail & Related papers  (2025-05-22T17:16:41Z)
• Causality can systematically address the monsters under the bench(marks) [64.36592889550431]
  Benchmarks are plagued by various biases, artifacts, or leakage.<n>Models may behave unreliably due to poorly explored failure modes.<n> causality offers an ideal framework to systematically address these challenges.
  arXiv  Detail & Related papers  (2025-02-07T17:01:37Z)
• Bridging Internal Probability and Self-Consistency for Effective and Efficient LLM Reasoning [53.25336975467293]
  We present the first theoretical error decomposition analysis of methods such as perplexity and self-consistency.<n>Our analysis reveals a fundamental trade-off: perplexity methods suffer from substantial model error due to the absence of a proper consistency function.<n>We propose Reasoning-Pruning Perplexity Consistency (RPC), which integrates perplexity with self-consistency, and Reasoning Pruning, which eliminates low-probability reasoning paths.
  arXiv  Detail & Related papers  (2025-02-01T18:09:49Z)
• MR-Ben: A Meta-Reasoning Benchmark for Evaluating System-2 Thinking in LLMs [55.20845457594977]
  Large language models (LLMs) have shown increasing capability in problem-solving and decision-making.<n>We present a process-based benchmark MR-Ben that demands a meta-reasoning skill.<n>Our meta-reasoning paradigm is especially suited for system-2 slow thinking.
  arXiv  Detail & Related papers  (2024-06-20T03:50:23Z)
• Deterministic Uncertainty Propagation for Improved Model-Based Offline Reinforcement Learning [12.490614705930676]
  We present a theoretical result demonstrating the strong dependency of suboptimality on the number of Monte Carlo samples taken per Bellman target calculation.<n>Our main contribution is a deterministic approximation to the Bellman target that uses progressive moment matching.<n>We show that it is possible to provide tighter guarantees for the suboptimality of MOMBO than the existing Monte Carlo sampling approaches.
  arXiv  Detail & Related papers  (2024-06-06T13:58:41Z)
• Understanding, Predicting and Better Resolving Q-Value Divergence in Offline-RL [86.0987896274354]
  We first identify a fundamental pattern, self-excitation, as the primary cause of Q-value estimation divergence in offline RL. We then propose a novel Self-Excite Eigenvalue Measure (SEEM) metric to measure the evolving property of Q-network at training. For the first time, our theory can reliably decide whether the training will diverge at an early stage.
  arXiv  Detail & Related papers  (2023-10-06T17:57:44Z)
• Improving Out-of-Distribution Detection via Epistemic Uncertainty Adversarial Training [29.4569172720654]
  We develop a simple adversarial training scheme that incorporates an attack of the uncertainty predicted by the dropout ensemble. We demonstrate this method improves OOD detection performance on standard data (i.e., not adversarially crafted), and improves the standardized partial AUC from near-random guessing performance to $geq 0.75$.
  arXiv  Detail & Related papers  (2022-09-05T14:32:19Z)
• Uncertainty-Based Out-of-Distribution Classification in Deep Reinforcement Learning [17.10036674236381]
  Wrong predictions for out-of-distribution data can cause safety critical situations in machine learning systems. We propose a framework for uncertainty-based OOD classification: UBOOD. We show that UBOOD produces reliable classification results when combined with ensemble-based estimators.
  arXiv  Detail & Related papers  (2019-12-31T09:52:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.