Large language models (LLMs) facilitate the development of autonomous agents. As a core component of such agents, task planning aims to decompose complex natural language requests into concrete, solvable sub-tasks. Since LLM-generated plans are frequently prone to hallucinations and sensitive to long-context prom-pts, recent research has introduced plan verifiers to identify and correct potential flaws. However, most existing approaches still rely on an LLM as the verifier via additional prompting for plan review or self-reflection. LLM-based verifiers can be misled by plausible narration and struggle to detect failures caused by structural relations across steps, such as type mismatches, missing intermediates, or broken dependencies. To address these limitations, we propose a graph-based verifier for LLM task planning. Specifically, the proposed method has four major components: Firstly, we represent a plan as a directed graph with enriched attributes, where nodes denote sub-tasks and edges encode execution order and dependency constraints. Secondly, a graph neural network (GNN) then performs structural evaluation and diagnosis, producing a graph-level plausibility score for plan acceptance as well as node/edge-level risk scores to localize erroneous regions. Thirdly, we construct controllable perturbations from ground truth plan graphs, and automatically generate training data with fine-grained annotations. Finally, guided by the feedback from our GNN verifier, we enable an LLM to conduct local edits (e.g., tool replacement or insertion) to correct the plan when the graph-level score is insufficient. Extensive experiments across diverse datasets, backbone LLMs, and planners demonstrate that our GNNVerifier achieves significant gains in improving plan quality. Our data and code is available at https://github.com/BUPT-GAMMA/GNNVerifier.
Figures & tables
Figure 1. An illustrative example of structural inconsistencies in LLM-generated plans. Although all steps are fluent and seemingly plausible, two image artifacts (poster.png and chart.png) are mistakenly input into the opposite downstream tools from their originally intended ones, which is difficult to detect by reading steps in isolation.
Figure 2. The overall framework of our proposed GNNVerifier with four main components.
Method
HuggingFace
Multimedia
DailyLife
UltraTool
n-F1 ↑
l-F1 ↑
Acc ↑
n-F1 ↑
l-F1 ↑
Acc ↑
n-F1 ↑
l-F1 ↑
Acc ↑
n-F1 ↑
l-F1 ↑
Acc ↑
Direct
Raw
79.60
55.27
34.20
85.94
64.36
49.60
97.12
84.21
72.80
73.07
46.36
36.80
+Refine
78.39
52.86
31.20
87.02
65.98
48.40
96.93
60.12
48.20
73.30
38.92
30.80
+VeriCoder
79.78
55.45
34.00
86.69
66.17
50.70
97.44
56.81
46.80
73.86
34.11
26.45
+VeriPlan
79.64
55.95
34.80
86.67
66.14
51.60
97.12
84.22
72.80
78.26
53.89
42.40
+GNNVerifier
82.82
60.71
43.80
88.09
70.74
58.60
97.51
87.45
78.76
76.89
52.82
42.80
Table 1. Performance comparison across four datasets on GPT-4o: Node-F1, Link-F1, and Accuracy are reported in %. The best results are highlighted in boldface, and the second-best results are underlined.
Variant
HuggingFace
Multimedia
n-F1 ↑
l-F1 ↑
Acc ↑
n-F1 ↑
l-F1 ↑
Acc ↑
Direct
Raw
79.60
55.27
34.20
85.94
64.36
49.60
w/o GNN
75.78
51.77
33.00
84.40
66.35
50.20
w/o Stage-II
79.92
55.51
35.40
86.03
66.05
50.40
w/o Stage-I
79.60
57.86
39.80
85.94
68.97
56.40
w/o Node Feat.
80.36
57.94
35.60
86.01
64.53
50.00
Table 2. Ablation studies on HuggingFace and Multimedia: Node-F1, Link-F1, and Accuracy are reported in %.
(a) HuggingFace
(b) Multimedia
(c) DailyLife
(d) UltraTool
Figure 3. Analysis of planning error types before and after correction across four datasets.
Figure 4. The t-SNE visualization of graph-, node-, and edge-level embeddings on UltraTool.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Variant
DailyLife
UltraTool
n-F1 ↑
l-F1 ↑
Acc ↑
n-F1 ↑
l-F1 ↑
Acc ↑
Direct
Raw
97.12
84.21
72.80
73.07
46.36
36.80
w/o GNN
95.47
84.64
74.00
72.62
45.71
34.00
w/o Stage-II
97.12
87.28
78.60
71.33
47.40
35.60
w/o Stage-I
97.12
87.28
78.60
73.33
47.56
37.60
w/o Node Feat.
97.12
87.28
78.60
75.15
50.49
41.00
Appendix
Table 4. Ablation studies on Dailylife and Ultratool: Node-F1, Link-F1, and Accuracy are reported in %. The best results are highlighted in boldface, and the second-best results are underlined.
(a) HuggingFace
(b) Multimedia
(c) DailyLife
(d) UltraTool
Appendix
Figure 7. Analysis of planning error types before and after correction under ReAct cross datasets with GPT-4o.
(a) HuggingFace
(b) Multimedia
(c) DailyLife
(d) UltraTool
Appendix
Figure 8. Analysis of planning error types before and after correction under GNN4Plan cross datasets with GPT-4o.
Figure 9. t-SNE visualization of graph-, node-, and edge-level embeddings on UltraTool under ReAct with GPT-4o.
Figure 10. t-SNE visualization of graph-, node-, and edge-level embeddings on UltraTool under GNN4Plan with GPT-4o.
Figure 11. Hyperparameter sensitivity on validation AUC cross datasets with GPT-4o. Three hyperparameter sensitivity plots showing the effect of tau, lambda graph, and lambda edge on validation AUC across all datasets.
Large language models (LLMs) provide a flexible interface for long-horizon robot planning, but generated plans often fail to respect embodiment constraints, recover from planning errors, or reason effectively under partial observability. We present GAVEL, a framework for verifying and repairing long-horizon LLM planning built around an explicit graph world model. The graph represents relevant object-relations, action pre-conditions and effects, and probabilistic beliefs over unobserved object locations. This model can predict the consequences of LLM-generated actions before execution, detect violations, and repair those whose corrections follow directly from the world model. This method also reserves LLM replanning solely for errors requiring semantic reasoning. For multi-task instructions, GAVEL reasons over distributions of possible object locations to reorder remaining subtasks and minimize expected search cost. We evaluate GAVEL on BEHAVIOR-1K across 100 single long-horizon tasks and 500 multi-task instructions. With Qwen3-8B, GAVEL improves single-task success from 41.2% to 91.8% and multi-task success from 19.9% to 92.6%. Distributional belief reasoning also reduces travel distance by approximately 5.4% compared with a static variant. These improvements show that an explicit graph world model harness can substantially improve the reliability and efficiency of long-horizon embodied planning across compact and frontier hosted LLM capabilities.
Large Language Models (LLMs) typically exhibit a performance profile where reliability degrades as task complexity increases. We address the challenge of generating high-quality natural language executable plans for complex tasks by introducing GRASP, a strategy-aware, multi-stage planning framework. GRASP decouples the planning pipeline across specialized, context-isolated modules: it pre-compiles global macro-guidelines (GenPlan), explores alternative localized strategies within isolated context windows (RevPlan), and independently evaluates trajectories using a multi-criteria discriminator (VerPlan). Empirical evaluations show that GRASP consistently establishes a new state-of-the-art frontier across diverse datasets, yielding substantial accuracy gains over direct LLM planners on Natural Plan Calendar Scheduling (∼12.4\%$$\uparrow), ZebraLogic (∼30.8\%$$\uparrow), and SciBench Math. Crucially, under multi-task scaling-where standard planners suffer immediate performance collapse-GRASP completely flattens the multi-task degradation penalty. In interleaved dual-task environments, GRASP achieves an absolute accuracy gain of up to 16.7% over direct LLM planners. Furthermore, by isolating context and enforcing strict macro-regularization, GRASP outperforms frontier reasoning models (such as GPT-5-mini) by a margin of 14.5%.
Arunabh Srivastava, Mohammad A., Khojastepour +2
Amir · NEC Laboratories America, Inc. · University of Maryland, College Park, MD
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.
Ma'ayan Armony, Albert Meroño-Peñuela, Gerard Canal