mlsanityData to 14 Oct 2026

Adaptive Uncertainty-Aware Tree Search for Robust Reasoning

arXiv 2602.06493 ↗First posted 6 Feb 2026cs.LGcited by 0

On the map: LLM reasoning → Test-time compute and efficient thinking

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 15 of its 32 references that are in the map. First posted on arXiv 6 Feb 2026.

Builds on

15 of 32 references.

Closest ancestors · 4

Same direction, newest first

  1. 2025Every Rollout Counts: Optimal Resource Allocation for Efficient Test-Time Scaling30 May
  2. 2025Can 1B LLM Surpass 405B LLM? Rethinking Compute-Optimal Test-Time Scaling10 Feb
  3. 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters6 Aug
  4. 2023Self-Evaluation Guided Beam Search for Reasoning1 May

Other references · 11

  1. 2024The Llama 3 Herd of Modelscited by 14,715
  2. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,330
  3. 2024Qwen2.5 Technical Reportcited by 4,942
  4. 2023Let's Verify Step by Stepcited by 3,789
  5. 2025Kimi k1.5: Scaling Reinforcement Learning with LLMscited by 1,210
  6. 2024Qwen2.5-Math Technical Report: Toward Mathematical Expert Model via Self-Improvementcited by 1,090
  7. 2024Large Language Monkeys: Scaling Inference Compute with Repeated Samplingcited by 991
  8. 2023Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotationscited by 928
  9. 2022Solving math word problems with process- and outcome-based feedbackcited by 901
  10. 2022Automatic Chain of Thought Prompting in Large Language Modelscited by 688
  11. 2025The Lessons of Developing Process Reward Models in Mathematical Reasoningcited by 415

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Uncertainty-Guided Likelihood Tree Search
  2. 2026Amortized Reasoning Tree Search: Decoupling Proposal and Decision in Large Language Models
  3. 2025Unlocking Exploration in RLVR: Uncertainty-aware Advantage Shaping for Deeper Reasoning
  4. 2025Beyond Correctness: Confidence-Aware Reward Modeling for Enhancing Large Language Model Reasoning
  5. 2025Unifying Tree Search Algorithm and Reward Design for LLM Reasoning: A Survey
  6. 2025Sycophancy Mitigation Through Reinforcement Learning with Uncertainty-Aware Adaptive Reasoning Trajectories
  7. 2023Tree of Uncertain Thoughts Reasoning for Large Language Models
  8. 2026UCPO: Uncertainty-Aware Policy Optimization