Why It Matters
This paper is the hard boundary around agent planning hype. It gives agent builders a concrete architecture lesson: keep domain models, validators, and planners in the loop, and never treat an LLM's natural-language plan as proof of executability.
Problem
- Many agent demos evaluated plans by plausibility or human inspection rather than executability against a domain model.
- LLMs often produce natural-language plans that look reasonable but violate action preconditions or fail to reach goals.
- Human-in-the-loop iterative correction can hide who is doing the planning, creating a Clever Hans problem.
- Classical planners can validate and repair plans, but LLM agent literature often underuses them.
Key gap: The paper asks whether LLMs can autonomously generate executable plans in classical planning tasks, and whether their failed plans can still help sound planners or verifiers.
Method
Generate planning prompts from PDDL domains, test LLM plans autonomously with a validator, then separately test whether LLM candidate plans help external planners or verifier-backed repair.
- Generate planning instances from PDDL domains and translate them into natural-language and PDDL prompt variants.
- Evaluate GPT-family models, BLOOM, and a fine-tuned GPT-3 variant in autonomous mode by validating generated plans.
- Stress-test GPT-4 with Mystery Blocksworld name obfuscations.
- Evaluate forgiving plan-validation relaxations to see whether failed plans are close to correct.
- Seed LPG with LLM-generated plans and compare search steps against empty and random seed plans.
- Use VAL to give mechanical feedback to GPT-4 for up to 15 backprompting rounds.
- Run a human user study with and without GPT-4 suggestions and measure accuracy, time, and cognitive load.
Claims
C1 · paper-supported
The paper separates LLM planning evaluation into autonomous mode and heuristic mode, using automated planning tools to avoid plausibility-only assessment.
Scope: Abstract, Introduction, Figure 1, and Sections 3-5.
- E-eval-design: The paper evaluates LLMs in autonomous mode, where generated plans are validated by VAL, and heuristic mode, where generated plans are used by external planners or verifiers.
C2 · paper-supported
In autonomous mode, the best model, GPT-4, averages only about 12% executable-plan success across domains.
Scope: Abstract and Section 4.
- E-headline: The abstract states that the best model, GPT-4, has an average autonomous executable-plan success rate of about 12% across domains.
C3 · paper-supported
Even in Blocksworld, GPT-4 reaches only around one-third success, and chain-of-thought or PDDL-formatted prompts do not fix the failure.
Scope: Tables 1 and 2, Section 4.
- E-blocksworld: GPT-4 solves 210/600 (34.6%) zero-shot natural-language Blocksworld instances, 214/600 (35.6%) with chain-of-thought, 106/600 (17.6%) zero-shot PDDL instances, and 75/600 (12.5%) one-shot PDDL instances. The paper says overall Blocksworld performance is still around 34%.
C4 · paper-supported
Obfuscating action and predicate names causes a catastrophic drop, showing that GPT-4's apparent planning depends strongly on familiar semantics.
Scope: Section 4 obfuscation experiments.
- E-obfuscation: With zero-shot natural-language prompts, GPT-4 solves 210/600 ordinary Blocksworld instances, but only 1/600 deceptive Mystery Blocksworld instances and 0/600 randomized Mystery Blocksworld instances. With PDDL prompts, GPT-4 solves 106/600 ordinary instances but only 3/600 deceptive instances.
C5 · paper-supported
Humans substantially outperform LLMs on the simple Blocksworld setting: 78% of participants produced valid plans, and 89.7% of valid human plans were optimal.
Scope: Section 4 human baseline.
- E-human-baseline: In an IRB-approved Blocksworld study, 39 of 50 participants produced valid plans (78%), and 35 of those 39 valid plans were optimal (89.7%).
C6 · paper-supported
LLM-generated plans can still be useful as seed plans for LPG local-search repair, reducing search steps in familiar domains.
Scope: Section 5.1, Table 3.
- E-lpg: LPG with a GPT-4 Blocksworld seed plan takes 8.9 average search steps versus 15.8 empty-seed and 20.07 random-seed baselines; Logistics takes 51.3 versus 77.5 and 144.39. Mystery Blocksworld shows weaker help: 16.09 versus 15.8 empty and 20.45 random.
C7 · paper-supported
External verifier feedback from VAL improves GPT-4 plan generation in common-sense domains but not much in obfuscated domains.
Scope: Section 5.2, Table 4.
- E-val: With VAL backprompting over 50 failed instances and at most 15 feedback rounds, GPT-4 reaches 41/50 correct on Blocksworld with 3.68 average feedback rounds, 35/50 on Logistics with 3.31 rounds, and 5/50 on deceptive Mystery Blocksworld with 7.0 rounds.
C8 · paper-supported
LLM suggestions did not significantly improve human planning accuracy, time, or cognitive load, and some users accepted incorrect suggestions.
Scope: Section 5.3.
- E-human-assist: The LLM-assisted human study had 49 unassisted and 48 assisted participants and found no statistically significant differences in accuracy, time, or cognitive load. Three assisted participants accepted incorrect LLM suggestions, and two submitted those suggestions as their plans.
Agent Infrastructure Takeaways
- Do not let plan-shaped text bypass an executable validator. Planning outputs need machine-checkable preconditions, effects, and goals.
- LLMs can be good proposal generators while still being bad autonomous planners. Architect the loop so a sound planner or verifier owns correctness.
- Name obfuscation is a useful stress test: if a model collapses when labels lose semantics, it is pattern matching more than planning.
- Verifier feedback beats self-critique because it comes from the domain model, not the same model that made the error.
- Human review is not a free safety layer; LLM suggestions can create automation bias without improving planning performance.
- Agent planning benchmarks should report executable success, not plausibility, and should separate extraction failures, invalid actions, unmet goals, and repairable sketches.
Caveats
- The results focus on classical deterministic planning domains.
- The paper evaluates GPT-family models available at the time plus BLOOM; later reasoning models may change absolute numbers but not the architecture lesson without fresh proof.
- Autonomous-mode prompts include domain descriptions, so this is not a test of discovering actions from raw environment interaction.
- Heuristic mode relies on external planners and verifiers with correct domain models.
- Verifier backprompting can require multiple rounds and still fails badly in obfuscated settings.
- The human-assistance study is limited, but it is enough to flag automation-bias risk.