HyperPlan: Modeling High-Order Task Relations with Constraint Hypergraphs for LLM Planning

Large language models (LLMs) have demonstrated strong performance on various reasoning tasks but still struggle with complex planning problems, such as travel planning, which require long-horizon reasoning under multiple hard constraints. Existing planning methods primarily focus on effectively decomposing a complex planning objective into simpler subtasks and solving them step by step. However, they often overlook high-order relations induced by shared constraints across multiple subtasks, which constitute a fundamental challenge that distinguishes complex planning from traditional reasoning tasks. To bridge this gap, we propose HyperPlan, a novel LLM planning framework that explicitly models high-order relations among tasks using a constraint hypergraph. First, HyperPlan induces a query-specific constraint hypergraph from the parsed query semantics. Decision-oriented task nodes represent planning subtasks, while constraint hyperedges with normalized types capture complete constraint scopes through hierarchical scope binding. Second, HyperPlan serializes the hypergraph in a constraint-centric form and performs constraint-aligned task reasoning under intra-node and inter-node consistency guidance. The coordinated task solutions are then composed into the final plan. We further theoretically characterize when explicit constraint scopes reduce LLM planning uncertainty. Experiments demonstrate that HyperPlan achieves state-of-the-art performance among planning methods with LLMs as reasoners, improving success rates by up to 28.9% over strong planning baselines across diverse planning settings.