Plan of Thoughts: Heuristic-Guided Problem Solving with Large Language Models
On the map: LLM reasoning → Test-time compute and efficient thinking
Abstract (arXiv)
While language models (LMs) offer significant capability in zero-shot reasoning tasks across a wide range of domains, they do not perform satisfactorily in problems which requires multi-step reasoning. Previous approaches to mitigate this involves breaking a larger, multi-step task into sub-tasks and asking the language model to generate proposals ("thoughts") for each sub-task and using exhaustive planning approaches such as DFS to compose a solution. In this work, we leverage this idea to introduce two new contributions: first, we formalize a planning-based approach to perform multi-step problem solving with LMs via Partially Observable Markov Decision Processes (POMDPs), with the LM's own reflections about the value of a state used as a search heuristic; second, leveraging the online POMDP solver POMCP, we demonstrate a superior success rate of 89.4% on the Game of 24 task as compared to existing approaches while also offering better anytime performance characteristics than fixed tree-search which is used previously. Taken together, these contributions allow modern LMs to decompose and solve larger-scale reasoning tasks more effectively.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 10 of its 14 references that are in the map. First posted on arXiv 29 Apr 2024.
Builds on
10 of 14 references.
Closest ancestors · 2
Same direction, newest first
- 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Models17 May
- 2023REFINER: Reasoning Feedback on Intermediate Representations4 Apr
Other references · 8
- 2023GPT-4 Technical Reportcited by 18,132
- 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
- 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,355
- 2019The Curious Case of Neural Text Degenerationcited by 2,881
- 2021A Token-level Reference-free Hallucination Detection Benchmark for Free-form Text Generationcited by 137
- 2023Prompting is not a substitute for probability measurements in large language modelscited by 43
- 2022CHAI: A CHatbot AI for Task-Oriented Dialogue with Offline Reinforcement Learningcited by 33
- 2023Closing the Curious Case of Neural Text Degenerationcited by 30
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2025PLAN-TUNING: Post-Training Language Models to Learn Step-by-Step Planning for Complex Problem Solving
- 2023Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models
- 2026Policy-Guided Search on Tree-of-Thoughts for Efficient Problem Solving with Bounded Language Model Queries
- 2026Heuristic Classification of Thoughts Prompting (HCoT): Integrating Expert System Heuristics for Structured Reasoning into Large Language Models
- 2024First Heuristic Then Rational: Dynamic Use of Heuristics in Language Model Reasoning
- 2024Multi-Step Reasoning with Large Language Models, a Survey
- 2026SokoBench: Evaluating Long-Horizon Planning and Reasoning in Large Language Models
- 2025Computational Thinking Reasoning in Large Language Models