HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking

2025/05/05 by Runquan Gui, Zhihai Wang, Gui, Runquan +17 · 1 voice · 7 citations
Computer Science · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Multimodal Machine Learning Applications #Topic Modeling #cs.AI

paper · pdf · doi:10.48550/arxiv.2505.02322

openalex publication_date 2025/05/05 · arxiv published 2025/05/05 · arxiv updated 2025/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Recent advancements have significantly enhanced the performance of large language models (LLMs) in tackling complex reasoning tasks, achieving notable success in domains like mathematical and logical reasoning. However, these methods encounter challenges with complex planning tasks, primarily due to extended reasoning steps, diverse constraints, and the challenge of handling multiple distinct sub-tasks. To address these challenges, we propose HyperTree Planning (HTP), a novel reasoning paradigm that constructs hypertree-structured planning outlines for effective planning. The hypertree structure enables LLMs to engage in hierarchical thinking by flexibly employing the divide-and-conquer strategy, effectively breaking down intricate reasoning steps, accommodating diverse constraints, and managing multiple distinct sub-tasks in a well-organized manner. We further introduce an autonomous planning framework that completes the planning process by iteratively refining and expanding the hypertree-structured planning outlines. Experiments demonstrate the effectiveness of HTP, achieving state-of-the-art accuracy on the TravelPlanner benchmark with Gemini-1.5-Pro, resulting in a 3.6 times performance improvement over o1-preview.

Citations

• Evolving Deeper LLM Thinking
• Toward Adaptive Reasoning in Large Language Models with Thought Rollback
• Forest-of-Thought: Scaling Test-Time Compute for Enhancing LLM Reasoning
• Beyond Examples: High-level Automated Reasoning Paradigm in In-Context Learning via MCTS
• Transforming the Hybrid Cloud for Emerging AI Workloads
• Planning in Strawberry Fields: Evaluating and Improving the Planning and Scheduling Capabilities of LRM o1
• To CoT or not to CoT? Chain-of-thought helps mainly on math and symbolic reasoning
• Agent Q: Advanced Reasoning and Learning for Autonomous AI Agents
• Mutual Reasoning Makes Smaller LLMs Stronger Problem-Solvers
• The Llama 3 Herd of Models
• Chain of Preference Optimization: Improving Chain-of-Thought Reasoning in LLMs
• NATURAL PLAN: Benchmarking LLMs on Natural Language Planning
• ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search
• Dual Operating Modes of In-Context Learning
• The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains
• TravelPlanner: A Benchmark for Real-World Planning with Language Agents
• An Information-Theoretic Analysis of In-Context Learning
• Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations
• The Mystery of In-Context Learning: A Comprehensive Survey on Interpretation and Analysis
• In-Context Learning with Iterative Demonstration Selection
• Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models
• Large Language Models Cannot Self-Correct Reasoning Yet
• Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training
• AutoAgents: A Framework for Automatic Agent Generation
• A Circuit Domain Generalization Framework for Efficient Logic Synthesis in Chip Design
• AgentVerse: Facilitating Multi-Agent Collaboration and Exploring Emergent Behaviors
• Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models
• Graph of Thoughts: Solving Elaborate Problems with Large Language Models
• Dynamic Planning with a LLM
• MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework
• Skeleton-of-Thought: Prompting LLMs for Efficient Parallel Generation
• Coupling Large Language Models with Logic Programming for Robust and General Reasoning from Text
• Encouraging Divergent Thinking in Large Language Models through Multi-Agent Debate
• Reasoning with Language Model is Planning with World Model
• Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planning
• Tree of Thoughts: Deliberate Problem Solving with Large Language Models
• Multilingual LLMs are Better Cross-lingual In-context Learners with Alignment
• Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models
• GPT-4 Technical Report
• Automatic Prompt Augmentation and Selection with Chain-of-Thought from Labeled Data
• Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model
• Efficient Exploration in Resource-Restricted Reinforcement Learning
• Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks
• Distributing Accountability, Not Capability: Phase Separation and the LLM Workflow Quadrant in Autonomous AI Agent Architectures
• PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change
• Large Language Models are Zero-Shot Reasoners
• HyperTree Proof Search for Neural Theorem Proving
• BNAI, NO-TOKEN, and MIND-UNITY: Pillars of a Systemic Revolution in Artificial Intelligence
• Sample-Efficient Reinforcement Learning via Conservative Model-Based Actor-Critic
• Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivity
• Calibrate Before Use: Improving Few-Shot Performance of Language Models
• What Makes Good In-Context Examples for GPT-3?
• Monte-Carlo Tree Search as Regularized Policy Optimization
• Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
• OpenAI o1 System Card

Cited by

• MorphoBench: A Benchmark with Difficulty Adaptive to Model Reasoning
• TripScore: Benchmarking and rewarding real-world travel planning with fine-grained evaluation
• MITS: Enhanced Tree Search Reasoning for LLMs via Pointwise Mutual Information
• VIR-Bench: Evaluating Geospatial and Temporal Understanding of MLLMs via Travel Video Itinerary Reconstruction
• AgentCoMa: A Compositional Benchmark Mixing Commonsense and Mathematical Reasoning in Real-World Scenarios
• Entropy-Constrained Strategy Optimization in Urban Floods: A Multi-Agent Framework with LLM and Knowledge Graph Integration
• ReflecSched: Solving Dynamic Flexible Job-Shop Scheduling via LLM-Powered Hierarchical Reflection

Discussions

• arxiv.org/abs/2505.023... [bsky, 0 points, 0 comments]

Related

• A Roadmap to Guide the Integration of LLMs in Hierarchical Planning
• A Human-Like Reasoning Framework for Multi-Phases Planning Task with Large Language Models
• LLMs Can Plan Only If We Tell Them
• Systematic Analysis of LLM Contributions to Planning: Solver, Verifier,\n Heuristic
• Bridging the Reasoning Gap: Small LLMs Can Plan with Generalised Strategies