- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes HyperPlan, a planning framework that separates language understanding from decision-making. Given a natural-language request, an LLM extracts entities and relations and represents them using an directed heterogeneous hypergraph. The system then performs hypergraph-based Monte Carlo rollouts to construct candidate plans, applies feasibility-first evaluation to enforce hard constraints, and maintains bounded failure memory to guide subsequent search. The framework is evaluated on TravelPlanner and NATURAL PLAN. The reported results demonstrate a 100% delivery rate on TravelPlanner and competitive performance across several planning tasks. However, the test results reveal a substantial gap between plan delivery and final constraint satisfaction.
Critical strengths
- The method is reasonable and complete. It uses the LLM to understand the request and graphs to guide decision-making, leveraging the strengths of LLMs in semantic understanding and graphs in relational modeling.
- Experiments on TravelPlanner and NATURAL PLAN provide an assessment of the proposed architecture's transferability across different planning domains.
Critical weaknesses
1.The framework appears to be a combination of established techniques, including LLM-based semantic parsing, typed graph representations, and Monte Carlo search. The paper does not sufficiently demonstrate its contributions in method.
2.The paper lacks theoretical guarantees establishing that the search procedure can reliably identify feasible plans within a finite rollout budget.
3.The paper does not fully describe hyper-edge construction, rollout selection, termination conditions, or the implementation of global constraint checking.
4.The paper presents bounded failure memory as an important component, but does not include an ablation study. All of the experiments do not report variance across multiple random seeds.
5.Figures 1 and 2 are not presented clearly, making it difficult to understand the framework and the main workflow.
Questions for authors
1.What is the essential novelty of the proposed method? The framework appears to the combination of established techniques.
2.How robust are the results across repeated runs? Can the authors report standard deviations over multiple random seeds?
3.Could the authors provide theoretical analysis on whether the search procedure can identify feasible plans within a finite rollout budget?
Response to Reviewer 3: Novelty, Robustness, and Search Guarantees
Thank you. We clarify the contribution, reproducibility details and feasibility limits below.
Our new controls use the same 180 recovered-input TravelPlanner validation cases, resources, checks, seed 13 and 128 rollouts, without LLM hints. Hypergraph, ordinary incidence graph (relation nodes plus binary arcs), and flat-pool representations yield identical plans and 94.44% final pass. Disabling joint stay-block hotel selection gives 76.67%. The 17.78-point drop supports joint composition, not graph expressivity or superiority over independent CSP/SMT planners.
Memory reduces the mean by 1.67 percentage points. We withdraw claims of a search benefit and keep it off in the primary setting. These runs measure search randomness on 180 validation cases, not repeated LLM extraction, full-test variance or NATURAL PLAN variance; we will not generalize the SDs to those settings.
P(no feasible plan generated in N rollouts) <= (1-p)^N.
This follows by multiplying conditional failure probabilities; independence is not required. For 0<p<1 and 0<delta<1, N >= ceil(log(delta)/log(1-p)) suffices for success probability at least 1-delta. This bounds generation, not acceptance or retention by an imperfect checker.
Crucially, we have not established a positive uniform p for our implementation. Top-k truncation, resource filtering and fixed operators can exclude every feasible plan, giving p=0. Thus we claim neither guaranteed finite-budget success nor probabilistic completeness over the original problem space. Failure within M rollouts does not certify unsatisfiability. Empirically, budgets 1/16/32/64/128/256 achieve 77.78/86.67/91.11/92.78/94.44/94.44% on the same validation protocol (seed 13); this is evidence of budget sensitivity, not a theorem.
Each rollout selects a route, stay lengths, transport policy, block hotels and daily resources, then scores the complete plan. The first is greedy; later ranked choices sample up to 16 candidates with weights proportional to 1/(rank+1). Cities use resource-count weights; attractions sample uniformly from up to 32 unused name-sorted candidates. Missing resources incur losses; least-violating hotel choices may remain infeasible. There is no complete backtracking.
Candidates minimize (delivery, hard, soft, normalized cost) lexicographically. Checks aggregate missing fields/transfers, route count, hotel capacity/rules/minimum stays, transport restrictions, cuisine coverage and total budget across the plan. Default M=128 exhausts the budget and returns the best candidate, possibly infeasible; optional early stopping requires zero internal delivery/hard loss. Memory is an instance-local FIFO that penalizes attributed resource IDs, chiefly reranking hotels; it provides no certified pruning. We will include pseudocode and exact settings. Delivery of a plan, internal acceptance and official final pass are distinct: 100% delivery is not 100% constraint satisfaction.