The authors present an automated method that uses LLMs to produce generalized plans in the Lean theorem prover, along with formal proofs that those plans are complete for a given planning domain. The approach converts PDDL domain descriptions into Lean, then prompts an LLM to generate a generalized plan and a proof of its completeness. The proof is verified by Lean's kernel, eliminating the need for manual evaluation. Tested on 13 benchmark domains, the method succeeded in producing valid completeness proofs for 12 of them, a significant advance over prior work which could only handle simpler domains.
LLMs generate generalized plans with machine-checked completeness proofs
The system produced Lean-verified plans for 12 of 13 benchmark domains, proving they solve every instance covered by the supplied domain constraints.
Research Lab
Katharina Stein · Chaahat Jain · Jörg Hoffmann · Alexander Koller
Saarland University · German Research Center for Artificial Intelligence (DFKI)
Research Digest··2 min read
In one line
LLMs can generate generalized plans and formal proofs that the plans solve all domain instances.
Before you read this
Three ideas this paper builds onverificationChecking outputs for correctness before accepting them, often to catch errors or reward hacking.341 papers →code as actionA paradigm where actions are expressed as executable code, such as method calls or program synthesis, rather than direct manipulation.30 papers →large language modelA neural network trained on massive text corpora to generate coherent text and perform diverse language tasks.329 papers →
Read it as
Stein et al. convert planning domains from PDDL into Lean, then use GPT-5.6-Sol to generate both a generalized plan and a formal proof of its completeness.
The authors developed a semantics-preserving conversion from PDDL, a standard planning-domain language, into Lean.
How it works
stage by stageThe Daily Edition
The front page in your inbox each weekday morning: the lead, the picks, and why each one earned its place.