# Tree of Uncertain Thoughts Reasoning for Large Language Models

arXiv: https://arxiv.org/abs/2309.07694 · HTML: https://mlsanity.com/paper/2309.07694/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 13 of its 16 references that are in the map.
- First posted on arXiv 14 Sep 2023.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 13 of 13)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation](https://mlsanity.com/paper/2302.09664/) (2023)
- [Teaching Models to Express Their Uncertainty in Words](https://mlsanity.com/paper/2205.14334/) (2022)
- [Generating with Confidence: Uncertainty Quantification for Black-box Large Language Models](https://mlsanity.com/paper/2305.19187/) (2023)
- [Prompting GPT-3 To Be Reliable](https://mlsanity.com/paper/2210.09150/) (2022)
- [Uncertainty Quantification with Pre-trained Language Models: A Large-Scale Empirical Analysis](https://mlsanity.com/paper/2210.04714/) (2022)

## Built on by (most cited first, 19 of 19)

- [Demystifying Chains, Trees, and Graphs of Thoughts](https://mlsanity.com/paper/2401.14295/) (2024)
- [Entropy-based Exploration Conduction for Multi-step Reasoning](https://mlsanity.com/paper/2503.15848/) (2025)
- [Mathematical Language Models: A Survey](https://mlsanity.com/paper/2312.07622/) (2023)
- [Search, Verify and Feedback: Towards Next Generation Post-training Paradigm of Foundation Models via Verifier Engineering](https://mlsanity.com/paper/2411.11504/) (2024)
- [A Survey of Scaling in Large Language Model Reasoning](https://mlsanity.com/paper/2504.02181/) (2025)
- [Reward Generalization in RLHF: A Topological Perspective](https://mlsanity.com/paper/2402.10184/) (2024)
- [ReasonBENCH: Benchmarking the (In)Stability of LLM Reasoning](https://mlsanity.com/paper/2512.07795/) (2025)
- [Latent Chain-of-Thought as Planning: Decoupling Reasoning from Verbalization](https://mlsanity.com/paper/2601.21358/) (2026)
- [Fleet of Agents: Coordinated Problem Solving with Large Language Models](https://mlsanity.com/paper/2405.06691/) (2024)
- [The Tyranny of Possibilities in the Design of Task-Oriented LLM Systems: A Scoping Survey](https://mlsanity.com/paper/2312.17601/) (2023)
- [MasonTigers at SemEval-2024 Task 9: Solving Puzzles with an Ensemble of Chain-of-Thoughts](https://mlsanity.com/paper/2403.14982/) (2024)
- [Bonsai: Interpretable Tree-Adaptive Grounded Reasoning](https://mlsanity.com/paper/2504.03640/) (2025)
- [Deep Hidden Cognition Facilitates Reliable Chain-of-Thought Reasoning](https://mlsanity.com/paper/2507.10007/) (2025)
- [We Choose to Go to Space: Agent-driven Human and Multi-Robot Collaboration in Microgravity](https://mlsanity.com/paper/2402.14299/) (2024)
- [Random Forest-of-Thoughts: Uncertainty-aware Reasoning for Computational Social Science](https://mlsanity.com/paper/2502.18729/) (2025)
- [Listening Alone, Understanding Together: Collaborative Context Recovery for Privacy-Aware AI](https://mlsanity.com/paper/2604.13348/) (2026)
- [Chain of Uncertain Rewards with Large Language Models for Reinforcement Learning](https://mlsanity.com/paper/2604.13504/) (2026)
- [A Proactive Multi-Agent Dialogue Framework for Assessing Social Language Disorder Traits in Autism](https://mlsanity.com/paper/2605.22993/) (2026)
- [GUT: Quantifying and Optimizing the Reasoning Uncertainty of LLMs via Graph Complexity](https://mlsanity.com/paper/2609.05284/) (2026)

## Abstract (arXiv)

While the recently introduced Tree of Thoughts (ToT) has heralded advancements in allowing Large Language Models (LLMs) to reason through foresight and backtracking for global decision-making, it has overlooked the inherent local uncertainties in intermediate decision points or "thoughts". These local uncertainties, intrinsic to LLMs given their potential for diverse responses, remain a significant concern in the reasoning process. Addressing this pivotal gap, we introduce the Tree of Uncertain Thoughts (TouT) - a reasoning framework tailored for LLMs. Our TouT effectively leverages Monte Carlo Dropout to quantify uncertainty scores associated with LLMs' diverse local responses at these intermediate steps. By marrying this local uncertainty quantification with global search algorithms, TouT enhances the model's precision in response generation. We substantiate our approach with rigorous experiments on two demanding planning tasks: Game of 24 and Mini Crosswords. The empirical evidence underscores TouT's superiority over both ToT and chain-of-thought prompting methods.