Research map / Large language models / Agents, code and math
HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes HyperTree Planning (HTP), which builds hypertree-structured planning outlines via top-down LLM-guided construction and then self-guided planning, evaluated on TravelPlanner, PlanBench Blocksworld, and Natural Plan trip planning.
Problem
LLM reasoning paradigms (CoT, ToT, in-context learning) struggle with complex planning tasks that involve long reasoning chains, diverse constraints, and multiple distinct subtasks.
Approach
Extends tree-of-thought to hypertrees where each edge connects a parent to a set of child nodes, enabling multi-level divide-and-conquer ("hierarchical thinking"); an LLM constructs a top-down hypertree planning outline from rules, selects the best hyperchain as the outline, and then fills it in via self-guided planning without manual examples.
Key results
- With Gemini-1.5-Pro, HTP reaches 36.1% success rate on TravelPlanner validation, versus 10.0% for o1-preview and 8.9% for the best agent baseline (EvoAgent).
- GPT-4o+HTP reaches 54.7% on Blocksworld and 36.9% on Trip Planning, versus 35.5% and 15.6% for the GPT-4o CoT baseline.
- Gemini-1.5-Pro+HTP reaches 42.8% on Trip Planning at about 13% of o1-preview's cost.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use HTP instead of o1-preview | Gemini-1.5-Pro on TravelPlanner · TravelPlanner | success rate: 10.0 -> 36.1 | Helped |
| Use HTP instead of o1-preview | Gemini-1.5-Pro on Blocksworld · Blocksworld | success rate: 97.8 -> 67.2 | Hurt |
| Use HTP instead of o1-preview | Gemini-1.5-Pro on Trip Planning · Trip Planning | success rate: 36.2 -> 42.8 | Helped |
| Add selection module rather than always choosing the leftmost leaf (ablation) | HTP with GPT-4o · TravelPlanner | success rate: 18.9 -> 20.0 | Helped |
| Add selection module rather than always choosing the leftmost leaf (ablation) | HTP with GPT-4o · Blocksworld | success rate: 42.0 -> 54.7 | Helped |
| Add selection module rather than always choosing the leftmost leaf (ablation) | HTP with Gemini-1.5-Pro · Trip Planning | success rate: 36.6 -> 42.8 | Helped |
| Add hierarchical division (ablation) | HTP with GPT-4o · TravelPlanner | success rate: 6.1 -> 20.0 | Helped |
| Add hierarchical division (ablation) | HTP with Gemini-1.5-Pro · Blocksworld | success rate: 27.8 -> 67.2 | Helped |
| Add hierarchical division (ablation) | HTP with Gemini-1.5-Pro · Trip Planning | success rate: 38.4 -> 42.8 | Hurt |
| Add decision module (ablation) | HTP with GPT-4o · Trip Planning | success rate: 15.3 -> 36.9 | Helped |
| Add query-specific planning outline rather than a fixed example (ablation) | HTP with GPT-4o · Blocksworld | success rate: 43.3 -> 54.7 | Helped |
| Add self-guided planning (ablation) | HTP with GPT-4o · TravelPlanner | success rate: 8.3 -> 20.0 | Helped |
Surprising findings
- Removing the division (hierarchical) module drops Gemini-1.5-Pro TravelPlanner success from 36.1% to 7.2%, the largest ablation drop.
- Probability-based pruning performance declines as branch width increases, attributed to inaccurate confidence scores accumulating at deeper levels.
Limitations
- LLMs struggle with complex single-step reasoning and lack human prior knowledge such as budgeting strategies.
- Vulnerable to long-horizon errors and lacks self-reflection and backtracking mechanisms.
- Inference cost can exceed single-path baselines due to multi-path expansion and hierarchical decomposition.
Experimental setup
Datasets: TravelPlanner validation set PlanBench Blocksworld PlanBench Mystery Blocksworld Natural Plan trip planning
Benchmarks: TravelPlanner Blocksworld Mystery Blocksworld Trip Planning (Natural Plan)
Metrics: delivery rate commonsense pass rate hard constraint pass rate success rate
Baselines: CoT ToT LATS One-shot HiAR-ICL RAP EvoAgent MTP o1-preview o1-mini GPT-4 GPT-4o
Builds on: Tree-of-Thought Chain-of-Thought RAP hypertree proof search
Closest papers by meaning
- Policy Guided Tree Search for Enhanced LLM Reasoning (ICML 2025 · similarity 0.89)
- Hierarchical Planning for Complex Tasks with Knowledge Graph-RAG and Symbolic Verification (ICML 2025 · similarity 0.88)
- Tree-Planner: Efficient Close-loop Task Planning with Large Language Models (ICLR 2024 · similarity 0.88)
- SPIRAL: Symbolic LLM Planning via Grounded and Reflective Search (AAAI 2026 · similarity 0.88)
- ReCAP: Recursive Context-Aware Reasoning and Planning for Large Language Model Agents (NeurIPS 2025 · similarity 0.87)
- ACPBench: Reasoning About Action, Change, and Planning (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.