Hypergraph-Grounded Rollout Search for Multi-Constraint LLM Planning

While large language models (LLMs) have made significant strides in handling complex reasoning tasks, existing planning methods still face substantial challenges with multiple fine-grained constraints. Fundamentally, relying on unstructured textual context to track dynamic resources and global constraints makes resource selection difficult to audit and failures hard to localize. We propose HyperPlan, which introduces an instance-level directed heterogeneous hypergraph as a formal, structured planning representation. Through explicit operator families, the hypergraph integrates constraints, actual candidate resources, temporal states, and partial plans, capturing high-order dependencies and multi-step state transitions. Rather than generating the final plan, the LLM serves as a semantic interface, parsing open-ended requests into formal entities and n -ary relations. These elements enable hypergraph-based Monte Carlo rollouts and lexicographic feasibility assessment. Failed simulations are attributed to specific hypergraph elements; bounded failure memory guides later search without overriding hard constraints. On the TravelPlanner test set, HyperPlan achieves 100.00% delivery and 82.40% final pass rate with GPT-4-Turbo. With the same backend on NATURAL PLAN, it achieves 75.00% exact match on Trip Planning, 100.00% accuracy on Meeting Planning, and 62.00% solve rate on Calendar Scheduling. The system boundary is clear: the LLM handles language parsing, while explicit hypergraph search makes verifiable decisions.