Testing the Planning Claims of LLM-Based Agents against Formal Semantics

Oriol Miro-Lopez-Feliu; Oscar Miró López-Feliu; Victor Gimenez-Abalos; Javier Vazquez-Salceda; Victor Carballo Araruna; Sergio Alvarez-Napagao

cs.AIOct 15, 2026

Testing the Planning Claims of LLM-Based Agents against Formal Semantics

Authors: Oriol Miro-Lopez-Feliu, Oscar Miró López-Feliu, Victor Gimenez-Abalos, Javier Vazquez-Salceda, Victor Carballo Araruna, Sergio Alvarez-Napagao

Organizations: Barcelona Supercomputing Center, Barcelona, Spain · University of Amsterdam, Amsterdam, The Netherlands · Safe AI Netherlands, The Netherlands · Universitat Politècnica de Catalunya, Barcelona, Spain

Abstract

LLM-based agents are increasingly credited with the competences of practical reasoning: planning, monitoring, and correcting their own actions. Their success is attributed to the prompting strategies and agent architectures built around the model, such as chain-of-thought, search-based prompting, self-refinement, reflection, critics and tool-using loops. Yet these claims are usually supported by end-to-end success rates, which show only whether a task was completed, or by LLM judges, which are not verifiers. We test LLM planning against formal semantics. Tasks are posed in natural language, but each is grounded in a hidden PDDL model that decides whether every action is applicable, whether the goal is reached, and whether a plan exists at all. Across five domains (two of them new, all released with the paper), four models, six prompting strategies and three agent architectures, the best configuration solves 78% of the solvable tasks offline but only 40% online, where agents mostly act without inspecting the state. Unsolvable tasks are recognised in under 10% of episodes, and heavier prompting strategies use 5 to 22 times as many tokens as direct prompting with no clear gain. In our experiments, planning performance varied more across models than across prompting strategies or agent architectures. Claims that agents can plan require evidence from validated action traces.

Figures & tables

Panel of Figure 1 — Figure 1. Evaluation protocols. (a) Offline, the planner maps the natural-language task to a complete plan or UNSOLVABLE , which is validated once. (b) Online, the agent interacts through tools: epistemic calls return observations without changing the state, ontic calls are validated before the state changes, and an inapplicable action ends the episode. Two diagrams side by side. The first shows a pipeline from the natural-language briefs to an LLM-based system, which outputs a full plan or UNSOLVABLE; an evaluator then marks it as success or failure. The second shows an LLM-based agent issuing calls to an environment. Epistemic actions go directly to the state and return observations. Ontic actions go through a validator: valid ones update the state, invalid ones cause a precondition violation. A submit action triggers the goal check.

Attributed competence	Checked property	Measure
Means–ends reasoning (CoT, Plan-and-Solve, ReAct)	The plan reaches the goal	Success (solvable)
Tracking state and constraints (Step-Back, ReAct)	Every committed action is applicable	Executability
Search and lookahead (Tree of Thoughts)	Higher success, no wasted actions	Success; score $L^{\star}/\|\pi\|$
Self-monitoring and repair (Self-Refine, Reflexion, Critic)	Fewer failures than the within-model baseline	Paired $\Delta$ vs. baseline
Sensing before acting (ReAct, Critic)	The state is queried before each commitment	Inspection rate; failure mode
Recognising infeasibility (all)	$\bot$ if and only if no plan exists	Detection; false abstention

Table 1. Competences attributed to prompting strategies and agent architectures (with the methods credited with them), the property that operationalises each, and its measure.

Domain	1	2	3	4	5	6	7	8	9	10
Blocksworld	4	6	6	10	–	8	–	10	10	14
Gripper	–	5	9	11	15	17	21	23	–	29
Logistics	9	15	21	–	–	39	45	51	57	63
LoadBalancing	4	3	–	7	4	5	3	–	8	5
Hospital	2	2	–	6	11	–	9	8	5	10

Table 2. Optimal plan length

L^{\star}

per task; a dash marks an unsolvable task.

Model	API identifier	Input	Output
GPT-4o-mini	gpt-4o-mini-2024-07-18	0.15	0.60
GPT-4o	gpt-4o-2024-08-06	2.50	10.00
Gemini 2.0 Flash-Lite	gemini-2.0-flash-lite	0.075	0.30
Gemini 2.0 Flash	gemini-2.0-flash	0.10	0.40

Table 3. Evaluated models and list prices (USD per million tokens, as of January 2026) used for cost estimates.

		GPT-4o-mini			GPT-4o			Gemini 2.0 Flash-Lite			Gemini 2.0 Flash
Method	Tok.	Succ.	Exec.	Det.	Succ.	Exec.	Det.	Succ.	Exec.	Det.	Succ.	Exec.	Det.
Offline (prompting strategies)
Direct	1.5	12.5	12.5	1	57.5	62.5	1	25.0	45.0	0	45.0	47.5	0
Zero-shot CoT	4.3	27.5 ∗	32.5	1	77.5 ∗	80.0	3	22.5	27.5	0	62.5	65.0	2
Plan-and-Solve	2.9	17.5	22.5	0	75.0	77.5	1	22.5	25.0	0	65.0 ∗	65.0	0
Step-Back	3.0	20.0	25.0	1	57.5	57.5	1	20.0	30.0	0	57.5	60.0	3

Table 4. Results per model and method. Succ. : success on the 40 solvable tasks (%). Exec. : share of those episodes that are executable (well formed, with every action applicable), whether or not they reach the goal (Definition 3.4 ; %). Det. : unsolvable tasks recognised (out of 10). Tok. : mean tokens per episode in thousands, averaged over the four models (per-model values are in the supplementary material). Bold marks the best success per model in each regime. No difference from the within-model baseline (Direct offline, ReAct online) survives the Holm correction; ∗ marks

p<0.05

before correction (exact McNemar test).

Panel of Figure 2 — Figure 2. Outcomes and cost. (a) Episodes on solvable tasks, pooled over the four models (160 per method); labels give the percentage of successes and of precondition violations, and Other covers malformed outputs and false abstentions. (b) Score against mean cost per episode for the 36 configurations; colour marks the regime, marker shape the model, and the line the Pareto front. PS: Plan-and-Solve; SB: Step-Back; CoT: chain-of-thought; ToT: Tree of Thoughts. Two panels. Left: horizontal stacked bars, one per method. Offline, Direct, zero-shot CoT, Plan-and-Solve, Step-Back, Self-Refine and Tree of Thoughts succeed in 35, 48, 45, 39, 34 and 28 percent of episodes, and precondition violations end 58, 46, 53, 56, 56 and 64 percent. Online, ReAct, Reflexion and Critic succeed in 23, 21 and 19 percent, and precondition violations end 67, 68 and 66 percent; Critic also has a 15 percent share of timeouts. Right: scatter plot of score against cost on a logarithmic axis. Offline configurations, shown in blue, form the upper-left boundary; online configurations, shown in red, all lie below it. GPT-4o with chain-of-thought has the highest score, 0.67, at about 0.017 dollars per episode. GPT-4o with Tree of Thoughts and GPT-4o with ReAct cost about 0.1 dollars per episode and score 0.34 and 0.39.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Figure F.1. Success on each solvable task: the share of the 24 offline configurations (four models and six strategies) and of the 12 online configurations (four models and three architectures) that solve it. The second row of labels gives the optimal plan length

L^{\star}

; unsolvable tasks are omitted.

LLM Planning

Large language model planning studies how models decompose goals, choose actions, and revise plans under constraints.

See all 142 papers

How Far Are LLMs from Symbolic Planners? An NLP-Based Perspective
Aug 2, 2025Ma'ayan Armony, Albert Meroño-Peñuela, Gerard CanalLLM Planning LLM Evaluation
Department of Informatics, King’s College London
Agent Planning Benchmark: A Diagnostic Framework for Planning Capabilities in LLM Agents
Jun 3, 2026Haoyu Sun, Wenxuan Wang, Mingyang Song +5Tool-Augmented Language Model Agents LLM Agent Evaluation
Tongji University · Shanghai AI Laboratory · Harbin Institute of Technology +5
Agentic LLM Planning via Step-Wise PDDL Simulation: An Empirical Characterisation
Mar 6, 2026Kai Göbel, Pierrick Lorang, Patrik Zips +1LLM Planning LLM Agent Planning
AIT Austrian Institute of Technology GmbH, Vienna, Austria

Aug 2, 2025J/K move · Enter open · S save

How Far Are LLMs from Symbolic Planners? An NLP-Based Perspective

Ma'ayan Armony, Albert Meroño-Peñuela, Gerard Canal

Department of Informatics, King’s College London

LLM Planning LLM Evaluation Long-Horizon LLM Reasoning Language Model Reasoning Evaluation Symbolic Planning

Open paper AskPDF arXiv

AI planning provides agents the ability to act autonomously towards achieving a goal in a given environment. Recent advances in Large Language Models (LLMs) have introduced the prospect of using unstructured input for planning, making LLMs in planning an active area of research, especially for supporting autonomous agents. However, LLMs remain unreliable as long-horizon planners, since some of the plans they produce contain mistaken or hallucinated actions; executing such plans could lead to unexpected and harmful outcomes. Existing benchmarks for LLMs in planning primarily rely on binary evaluation metrics, providing limited insight into the quality of plans that do not achieve the goal, and how far those are from becoming valid. In this paper, we frame the evaluation of LLMs in planning as a natural language processing (NLP) task, as LLMs are themselves NLP models. We propose a pipeline comprising three NLP-based steps that assess plan quality from complementary perspectives, followed by a symbolic planning step to achieve a valid plan, to provide a finer-grained understanding of the quality of invalid plans. In our experiments, we find no clear evidence of logical derivation or state-tracking during LLM plan generation -- on average, for all non-empty plans, only 3.55 actions per plan are executable, despite symbolically-generated optimal plans having an average length of 9.47 actions, which suggests that LLMs are still far from the reliability of symbolic planners. Our suite of metrics is further used to investigate patterns in LLM plan generation over time, and can provide a useful metric for assessing the quality of individual invalid plans.

Abstract

LLM Planning

Explore similar work

How Far Are LLMs from Symbolic Planners? An NLP-Based Perspective

Agent Planning Benchmark: A Diagnostic Framework for Planning Capabilities in LLM Agents

Agentic LLM Planning via Step-Wise PDDL Simulation: An Empirical Characterisation