Large language model (LLM) web agents are increasingly used for web navigation but remain far from human reliability on realistic, long-horizon tasks. Existing evaluations focus primarily on end-to-end success, offering limited insight into where failures arise. We propose a hierarchical planning framework to analyze web agents across three layers (i.e., high-level planning, low-level execution, and replanning), enabling process-based evaluation of reasoning, grounding, and recovery. Our experiments show that structured Planning Domain Definition Language (PDDL) plans produce more concise and goal-directed strategies than natural language (NL) plans, but low-level execution remains the dominant bottleneck. These results indicate that improving perceptual grounding and adaptive control, not only high-level reasoning, is critical for achieving human-level reliability. This hierarchical perspective provides a principled foundation for diagnosing and advancing LLM web agents.
Figures & tables
Figure 1: Overview of the hierarchical planning evaluation framework we propose. The pipeline consists of 3 stages: 1) High-level Planning: The LLM proposes high-level subgoals, 2) Low-level Execution: each high-level subgoal is translated into a set of low-level actions, a postcondition checker verifies whether the low-level actions lead to successful completion of the subgoal. If the subgoal fails after multiple iterations, then 3) Replanning is triggered. In addition to natural language, we explore a structured representation ( PDDL ) for high-level planning.
Human Step
NL (LLM-generated) Step
PDDL (LLM-generated) Step
Set the search criteria to include Audi cars made between 1992 and 2015.
Apply a year filter to restrict results to model years before 2015 (i.e., 2014 and earlier).
(filter_by_year "before 2015")
Go to the E-Gift card purchase page.
Navigate to the e-gift card section.
(open_gift_card_section)
Add the highest rated activity to your wish list.
From the results, identify the card with the highest rating and open its details by clicking on that card. Add the identified experience to your wishlist by clicking the Save to Wishlist (or Add to Wishlist) control on the details page.
(select_top_result) ; (add_to_wishlist)
Unmatched LLM steps (reference human plan shown below):
1. Navigate to the ’The Legend of Zelda: Breath of the Wild’ game page.
If no suitable walkthrough is found, perform an alternate search for Breath of the Wild guides (in Nintendo or Games sections)
(verify_walkthrough_loaded)
2. Access the walkthrough section for ’The Legend of Zelda: Breath of the Wild’
Table 1: Examples of annotated NL and PDDL steps with reference to human steps. Blue = Decomposed alignment, Green = Perfect Match, Purple = Partial alignment, Gray = Unmatched or extra steps.
Before Replanning
After Replanning
NL
PDDL
NL
PDDL
Perfect Match
60.6
67.7
56.1
59.0
Partial
5.7
7.4
6.1
6.9
Missing
4.2
2.2
4.0
14.5
Decomposed
29.5
22.7
33.8
19.6
Unmatched
29.4
15.4
35.0
15.4
Table 2: Alignment (%) between human and LLM-generated high-level plans.
Human
NL
PDDL
# High-level subgoals
3.04
5.51
4.39
# Low-level actions
7.08
11.94
8.89
Table 3: Avg. length of high-level plans and low-level actions for each representation.
Metric
Action Object
Action ID
Expanded
Hallucination Rate
34.0
2.0
3.0
Table 4: Hallucination (invalid action) rates across different action representations (%).
Figure 2: Execution results of different representations
Failure Mode
Rate (%)
Base Category
Repetitions
10.4
of failures
Hallucinated links
32.0
of goto actions
Redundant actions
34.2
of all actions
Out-of-domain links
16.7
of all actions
Table 5: Failure modes across different categories. Each rate is computed relative to its own base set. Illustrated examples of these failures can be found in Appendix B.3 .
Figure 3: Performance with and without replanning
Appendix figures & tables16 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Examples of the high-level step annotation process We begin by prompting gpt-5-nano to produce a high-level step based on the evaluation key-node object and correct issues such overspecification and steps framed as evaluation functions manually.
Figure 5: Evaluation trees for high-level alignment.
Figure 6: Motivating example highlighting the importance of high-level representation.
Figure 7: Distribution of actions in the expanded action space across different LLMs.
Figure 8: Examples of some of the most common errors encountered by the model ( gpt-5-nano )
NL
PDDL
Perfect Match
54.9
66.7
Partial
6.8
4.8
Missing
7.5
7.3
Decomposed
30.8
21.2
Unmatched
17.4
10.1
Matched
83.6
89.9
Appendix
Table 6: Alignment (%) between human and LLM-generated high-level plans: claude-haiku-4.5 .
NL
PDDL
# High-level steps
4.89
3.70
# Low-level actions
11.0
10.6
Appendix
Table 7: Avg. Length of High-level and Low-level plans for each representation for claude-haiku-4.5
Figure 9: Execution Results using different high-level representations using claude-haiku-4.5
Failure Mode
Rate (%)
Base Category
Repetitions
16.7
of failures
Hallucinated links
25.3
of goto actions
Redundant
23.6
of all actions
Out-of-domain links
16.9
of all states
Appendix
Table 8: Failure modes across different categories. Each rate is computed relative to its own base set. claude-haiku-4.5
Figure 10: Replanning results claude-haiku-4.5
NL
PDDL
Perfect Match
61.4
64.3
Partial
8.5
7.2
Missing
11.6
12.4
Decomposed
18.5
16.1
Unmatched
21.6
18.3
Matched
78.4
81.7
Appendix
Table 9: Alignment (%) between human and LLM-generated high-level plans: gemini-flash-2.5 .
Figure 11: Execution Results using different high-level representations using gemini-flash-2.5
Failure Mode
Rate (%)
Base Category
Repetitions
6.70
of failures
Hallucinated links
31.2
of goto actions
Redundant
41.2
of all actions
Out-of-domain links
14.7
of all actions
Appendix
Table 10: Failure modes across different categories. Each rate is computed relative to its own base set. gemini-flash-2.5
NL
PDDL
# High-level steps
3.63
3.19
# Low-level actions
8.55
8.25
Appendix
Table 11: Avg. Length of High-level and Low-level plans for each representation for gemini-flash-2.5
Figure 12: Replanning results gemini-flash-2.5
Initial page shown to the agent (homepage of Six Flags).
Despite recent advances, LLM-based web agents still struggle with limited exploration, omission of critical steps, and sensitivity to task constraints. Prior work suggests that many of these failures stem from weaknesses in planning, yet the impact of alternative natural language plan representation remains unexplored. To address this, we introduce PlanAhead, a static planner-executor framework that evaluates the impact of plan representation in agent performance. We first automatically categorize WebArena tasks into 3 difficulty levels, enabling consistent difficulty grading without human annotation. Then we systematically evaluate 4 different plan representations on the tasks categorized as hard: sequential subgoals, narrative, pseudocode, and checklist; across different families of multimodal LLM powered agents (OpenAI, Alibaba, and Google). To account for stochastic variability, we introduce two novel evaluation metrics: Achievement Rate (AR) and Solved-Task Consistency (STC). Our results show that both, the plan formulation and the underlying LLM generating the plan, significantly influence web-agent robustness and task success.
Alejandra Zambrano, Sara Vera Marjanovic, Imene Kerboua +2
Concordia University · Mila - Quebec AI Institute · University of Copenhagen +2
Developing autonomous agents for web-based tasks is a core challenge in AI. While Large Language Model (LLM) agents can interpret complex user requests, they often operate as black boxes, making it difficult to diagnose why they fail or how they plan. This paper addresses this gap by formally treating web tasks as sequential decision-making processes. We introduce a taxonomy that maps modern agent architectures to traditional planning paradigms: Step-by-Step agents to Breadth-First Search (BFS), Tree Search agents to Best-First Tree Search, and Full-Plan-in-Advance agents to Depth-First Search (DFS). This framework allows for a principled diagnosis of system failures like context drift and incoherent task decomposition. To evaluate these behaviors, we propose five novel evaluation metrics that assess trajectory quality beyond simple success rates. We support this analysis with a new dataset of 794 human-labeled trajectories from the WebArena benchmark. Finally, we validate our evaluation framework by comparing a baseline Step-by-Step agent against a novel Full-Plan-in-Advance implementation. Our results reveal that while the Step-by-Step agent aligns more closely with human gold trajectories (38% overall success), the Full-Plan-in-Advance agent excels in technical measures such as element accuracy (89%), demonstrating the necessity of our proposed metrics for selecting appropriate agent architectures based on specific application constraints.
Orit Shahnovsky, Rotem Dror
Faculty of Computer and Information Science, University of Haifa, Haifa, Israel
Existing LLM-based web agents struggle on complex, long-horizon tasks due to limited in-context memory, weak planning abilities, and greedy behaviors that lead to premature termination. To address these challenges, we propose \SA{}, a hierarchical planning framework that interleaves planning and execution via dynamic \ANDOR trees. The framework separates structural planning from LLM-based reasoning, enabling principled error recovery through node repair, systematic exploration of alternatives via OR nodes, and modular plans that can facilitate human intervention. On WebArena (630 tasks), \SA{} achieves a ∼53% success rate vs.\ ∼46% for AgentOccam, and on complex multi-constraint Amazon shopping tasks, gains reach 10% over the strongest baseline.
ELita Lobo, Xu Chen, Jingjing Meng +5
University of Massachusetts Amherst · Amazon · Virginia Commonwealth University +1