GPT-5.6-Sol writes Lean-checked complete generalized plans for 12 of 13 PDDL domains

Provably Complete Generalized Planning with LLMs

Katharina Stein, Chaahat Jain, Jörg Hoffmann, Alexander Koller

cs.AI

2026-09-23

Saarland compiles PDDL into Lean, then has GPT-5.6-Sol write a generalized plan and a completeness proof. 12 of 13 benchmark domains pass the Lean kernel; Transport does not.

What problem this solves

Generalized planning asks for a strategy program, with loops and branches, that solves every legal instance of a PDDL domain. Silver et al. (2024) and Stein et al. (2026) already had LLMs write those programs in Python. Stein et al. reached 100% coverage on the test splits of 14 domains. A test split is finite. Completeness, meaning the program works on every instance the domain admits, was still a manual proof.

Automatic completeness proofs existed in narrower settings. Hu and Levesque (2010) covered one-dimensional problems. Cui et al. (2023) can prove that a sound abstraction implies completeness, but the published successes stop at clearing a single Blocksworld block, IPC Gripper, and Logistics with one vehicle. This Saarland/DFKI paper wants the same guarantee on standard IPC-style domains, with Lean's kernel as the checker.

Method

The inputs are a PDDL domain plus user-written validity constraints and state invariants. The pipeline has three stages.

• A deterministic converter compiles PDDL into Lean. Objects become naturals, predicates become Boolean functions, actions become constructors of an inductive type. The state splits into a static part (predicates no action can change, such as location links) and a dynamic part. Goals use Option Bool, with none meaning unconstrained. actionPre and actionApply handle one step; ValidPlan and runPlan lift that to action sequences. The conversion preserves semantics: a Lean plan is correct for the compiled instance iff the matching PDDL plan is correct for the original.
• An LLM receives a (possibly revised) Stein 2026 pseudocode strategy and the full Lean encoding, and writes solve. Static check: Lean accepts the code. Dynamic check: run on six small instances, convert the returned plans back to PDDL, validate with VAL. At most four debug rounds.
• The same LLM then proves: for every instance that satisfies ValidInit and ValidGoal, solve returns a plan that is applicable step by step and meets the goal. On easier domains the model writes the whole proof and revises it as a unit. When it says the proof is too large to emit at once, the pipeline switches to a sketch of lemmas, then checks and repairs one declaration at a time. That iterative repair follows the same idea as Ospanov et al. (2025).

Four anti-cheating checks: reject notation or macros that change parsing; require the completeness theorem to appear verbatim; ban axioms beyond Lean's standard set; rebuild the file from scratch and recheck it with Lean's standalone checker. The REPL is only for faster incremental debugging.

Completeness is relative to the constraints the user wrote. If those constraints do not imply solvability, no proof exists. Invariants could in principle be derived from the init constraints and the action schemas; here they are written into ValidState so the model does not have to rediscover them. The converter also emits, per action schema, a lemma that valid states stay valid.

The converter covers only conjunctive conditions with negation and no action costs. Types compile down to unary predicates.

Results

The model is GPT-5.6-Sol, temperature 1, reasoning high. The 13 domains are a subset of the 17 from Stein et al. (2026). Gripper was dropped as too close to Grippers, Beluga because LLMs already fail to find a strategy there, Minigrid and Visitall because solvability is hard to specify. For every tested domain except Rovers, Stein et al. had already proved their Python generalized plans complete by hand.

All 13 domains got a Lean-accepted solve that passed VAL on all six debug instances. Ten succeeded on the first sample; the other three needed one debug round. Given a correct strategy up front, that is expected.

Proofs: generating the whole proof with at most six debug rounds succeeded on 7 of 13 domains. On the remaining six the model said on the first reply that a full proof was too complex. The iterative declaration-level loop then closed 5 more. Transport is the miss. The Transport plan still had perfect coverage on the easy and medium IPC Learning 2023 test splits. The gap is the proof, not the test-set behavior.

Proof Lean is much thicker than plan Lean. Rovers arrives with 293 declarations already in the prompt and the model writes 66 more; Heavy's proof side only needs 9 model-written declarations.

There is no head-to-head against Cui et al. (2023) on the same domains. The comparison the paper actually makes is scale: prior automatic proofs stopped around Gripper; this run reaches Rovers, Satellite, and Logistics.

Why it matters

For people who write planners, LLM-generated code, or formal proofs, the result is a working bridge between "100% on the test split" and "true for every admitted instance." The trust root is Lean's kernel, not the model's self-report.

The prerequisites are strict. Someone still has to write the constraints and invariants, the PDDL fragment has to be conjunctive-with-negation, and a strategy is assumed to exist. This is not a drop-in compiler from a domain file to a verified program. For a lab that already has a pseudocode strategy and wants to replace a hand completeness argument with a machine check, 12 of 13 is usable.

Limitations

The strategy is not searched for. It is Stein 2026 pseudocode rewritten in Lean. Completeness proving is automated; strategy discovery is not.

Constraints and invariants are human-written. Too loose, and the theorem may be false. Too tight, and the proof only covers the instance family you carved out, not every PDDL-syntactically legal problem. The paper does not report how the system fails when the constraints are wrong.

Only one model is tested. There is no error taxonomy for Transport. The anti-cheating rules are a checklist the authors wrote; they do not report how many opportunistic proofs those checks actually caught.

The PDDL fragment is narrow. Two of the four excluded domains were dropped because solvability constraints are hard to write. That leaves "is the constraint language expressive enough" outside the evaluation set.

Terms

• Generalized planning: find a strategy program for a whole domain, not an action sequence for one instance.
• PDDL: Planning Domain Definition Language; predicates and action schemas describe the state space.
• Complete generalized plan: for every legal instance under the constraints, the program returns a step-wise applicable plan that reaches the goal.
• Lean kernel: the small trusted type checker. A proposition is proved only if the proof term passes it.
• VAL: an external validator that checks PDDL plans for applicability and goal satisfaction.

Source

• arXiv 2609.27105v1
• PDF
• Hugging Face

What people are saying

• New paper: Provably Complete Generalized Planning with LLMs JFPuget

Related papers

• Five seller models inflate tool fields; Gemini 3.8 Flash cuts success from 89% to 30%
• 273 idea atoms distilled from LLM papers drive a sampler toward directions no community would propose
• Meta Experts Match Vanilla MoE Loss at 70-80% Expert Budget
• Throwing away synthesized agent rules beats stored abstractions, 59.9% vs 49.0%
• Jev 1.13 lifts terminal-agent cost 19% on Terminal-Bench; pass rate stays 73%
• Synthetic questions cut replies 20% and lift OPD signal 28% over DAPO-17k

All paper explainers