top of page
HyperTree Planning: Hierarchical LLM Planning for Complex Tasks
- Methodology: HTP introduces a novel hypertree structure for LLM planning, decomposing queries into hierarchical subtasks, enabling a divide-and-conquer approach. This contrasts with linear (Chain-of-Thought) or simple tree-based (Tree-of-Thought) methods.
- Algorithm: HTP employs a top-down algorithm involving selection, expansion, construction, and decision stages. The LLM autonomously selects nodes to split, expands branches using rule libraries, and prunes hyperchains based on self-evaluation, eliminating the need for hand-crafted examples.
- Performance: HTP achieves state-of-the-art accuracy on the TravelPlanner benchmark using Gemini-1.5-Pro, demonstrating a 3.6x performance improvement over o1-preview. It also outperforms Chain-of-Thought, Tree-of-Thought, and agent-based methods by up to 4x on complex, long-horizon tasks like Blocksworld and Trip Planning.
- Hierarchical Thinking: The hypertree structure facilitates "hierarchical thinking," a multi-level divide-and-conquer approach, enabling deeper and more organized reasoning compared to traditional tree structures.
- Ablation Studies: Removing any module of HTP consistently leads to a notable decline in performance, highlighting the importance of hierarchical thinking, planning outlines, and the self-guided planning process.
- Limitations: LLMs still struggle with complex single-step reasoning, lack human prior knowledge, are vulnerable to long-horizon errors, and lack mechanisms for self-reflection and backtracking. Future work will focus on integrating HTP with self-reflection and backtracking mechanisms.
Source:
bottom of page