- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3(+1)
Read review
Paper summary
This paper studies optimal classical planning with LLM-generated heuristics. Traditional optimal planners return optimal plans, but their domain-independent heuristics do not exploit domain structure and scale poorly. Existing LLM methods generate heuristics for satisficing planning, so their plans may not be optimal. LeanPlan uses an agentic loop in which an LLM writes a strong domain-specific heuristic and proves its admissibility in Lean, so that A* finds optimal plans at low cost. The loop runs once per domain on training tasks. LeanPlan is evaluated on test tasks from ten IPC 2023 domains and three new domains, where it solves 281 and 67 tasks, against 221 and 51 for Scorpion. VAL accepts every returned plan, and all planners find plans of the same cost on a task.
Critical strengths
- The problem, the method and the results are clearly presented, and the purpose of the method and its correctness are easy to follow. Proving admissibility in Lean is a useful complement that removes the main reason not to trust LLM-written heuristics in optimal planning. Admissibility reduces to goal awareness and consistency on reachable states.
- The experiments support the correctness claim. VAL accepts every returned plan, and all planners find plans of the same cost on a task.
Critical weaknesses
- One run per domain shows that the loop can succeed, but not how reliably.
- The loop was run once per domain, with one model and one coding agent (L311-312, L480-481).
- The three new domains are the only ones the model cannot have seen, yet the appendix does not describe their heuristics or certificates. L252-253 says App. C covers the remaining heuristics, so these should be added.
- Their test tasks are at most about twice the training size (L90-92), and even so the Cisterns certificate refused three test tasks, the only refusals among 1,170 (L418-419).
- The method is the loop, not the 13 heuristics, so how reliably the loop runs decides how far the results generalize. Question 3 asks for a rerun.
- Two steps may fall outside the machine-checked guarantee.
- The abstract says grounding is machine-checked (L018-020), and grounding prunes actions with mutexes (L236-237). App. A lists proofs for atom numbering, static preconditions and relevance pruning, but not for pruning (L787-788), and Sec. 7 does not list it as unchecked (L483-485). Since the search guarantees concern the executable ground task (L792), optimality for the original PDDL task may rest on unverified code. Please check the paper's wording against the system you built (Question 2).
- App. B tells the agent that "A theorem that is true but says less fails" (L930-932). Sec. 3 does not say how the controller detects a weakened statement, and the axiom audit alone would not (L208-209). The source scan covers only sorry, admit, native_decide and new axioms (L205-207, L927-929), so an attribute such as implemented_by would pass both checks while letting the compiled heuristic differ from the proved definition. Could you assess whether the loop can exploit this (Question 2)?
Questions for authors
- [Clarification] Did the worked examples in the prompt (App. B) include a heuristic or proof for any evaluated domain?
- [Clarification] Is pruning proved, or treated as a trusted component? Does the controller compare theorem statements with fixed references and reject attributes such as implemented_by? If both are handled, I would support acceptance more firmly.
- [Requested analysis] Could you rerun the loop on each new domain and report how often it succeeds and the coverage of the heuristics it produces?
- [Clarification] Could you describe the heuristics and certificates for the three new domains in an appendix, and say what the tasks refused by the Cisterns certificate have in common?
5 comments
Dear Reviewer WZR3,
We thank you again for your constructive review and positive assessment of the method. Our rebuttal provides the requested repeated synthesis results for all three new domains and discusses the proof guarantees, controller checks, prompt examples, and certificate refusals. As the discussion period approaches its conclusion, we would appreciate knowing whether these answers addressed the concerns you identified as important for firmer support. We would be glad to provide further clarification. If your concerns have been resolved, we kindly ask you to consider updating your score to reflect the additional evidence.
Thank you for the response and the repeated synthesis runs. Your explanations on pruning, the controller checks, the prompt examples, and the Cisterns refusals address my soundness questions well, so I am raising Soundness from 2 to 3. That said, the repeated runs switched to a stronger model rather than testing variance on the paper's original setup, per-domain variance and synthesis cost are still missing, and no revised PDF has been uploaded yet. I will therefore keep my overall rating at 3, and I continue to support acceptance.
Thank you for the positive assessment of the method and its correctness. We first present the additional experiments, which also inform our answers below.
W1 and Q3: Repeated Synthesis on the New Domains
We extended the experiments to LeanPlan with GPT-6.1 Sol and repeated synthesis three times across all ten IPC and three new domains. Every repetition produced a verified heuristic in every domain. The table reports mean coverage (90 tasks per domain), with mean ± sample standard deviation in total rows for LeanPlan with GPT-6.1 Sol. Search totals cover the same 248 tasks solved by all configurations, using per-task medians over three evaluations for the new heuristics. Scorpion SCP and GPT-5.6 Sol results are paper references. The full domain table appears in our response to Reviewer JCJG.
All three synthesis repetitions produced a verified heuristic in every domain. Compared with Scorpion SCP, mean new-domain coverage increases from 51 to 154 tasks. On the 248 jointly solved tasks, LeanPlan with GPT-6.1 Sol is about 17 times faster, and requires 95 times fewer expansions than Scorpion SCP. These experiments extend the evidence from one successful synthesis per domain to repeated synthesis using a new model across the full benchmark suite. We will include these results in the paper.
W2 and Q2: Pruning and Enforcement of the Proof Contract
h2 pruning is proved in Lean. The shared proofs establish that pruning preserves the optimal plan cost and that plans found after pruning correspond to plans of the original ground task with the same cost. They also connect the heuristic guarantees to the compiled search after pruning. We will make this proof coverage explicit in Appendix A and clarify its place in the formalized planning pipeline.
The controller checks the required theorem against a fixed statement about the actual heuristic and certificate used by the planner. A weaker theorem cannot satisfy that statement. The controller also rejects implementation overrides such as
implemented_byandextern. Together with the axiom audit, these checks connect the proved claim to the executable heuristic. We will describe these checks explicitly in the paper.Q1: Worked Examples in the Prompt
No, the prompt only uses heuristic and proof examples from Gripper and Logistics, neither of which is included in our evaluation. These illustrate the expected implementation and proof structure. We will clarify this in Appendix B.
W1 and Q4: New-Domain Heuristics and Certificate Refusals
We will include descriptions of all three heuristics and their certificates in the appendix:
The paper's three Cisterns refusals share the same preprocessing interaction: relevance pruning removes a new-level add effect while retaining the old-level deletion. This preserves planning behavior but violates the complete level-update structure required by the certificate. The certificate correctly excludes these three tasks, which are counted as unsolved. Across the paper's test suite, the certificates accept 1,167 of 1,170 tasks. This allows the heuristics to exploit natural domain structure and apply to virtually the entire test suite with machine-checked admissibility guarantees.