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.

Lay Summary:

Many real-world tasks—such as planning a multi-day trip, organizing a complex schedule, or making long-term decisions—require advanced reasoning and step-by-step planning. Current large language models (LLMs) often struggle with these complex tasks due to their lack of explicit structure and long-term coherence.We present HyperTree Planning (HTP), a new method that enables LLMs to solve complex tasks by automatically decomposing them into subgoals using a tree-structured framework. This tree structure allows the model to plan and execute sub-tasks recursively, while a self-reflection mechanism guides the model to revise and improve its reasoning throughout the process. The entire pipeline is fully automated, without any human intervention.HTP significantly improves LLMs' ability to complete complex tasks accurately and efficiently. It outperforms strong baselines in travel planning, instructional generation, and embodied AI tasks. Our method demonstrates that LLM agents can autonomously perform multi-step reasoning and handle diverse real-world needs with high reliability and precision.