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.
Figures & tables
Human Trajectory
Agent Planned Trajectory
Agent Actual Trajectory
Step No.
Action
Step No.
Action
Step No.
Action
H1
Click Products link
AP1
Click About Us link
AA1
Click About Us link
H2
Click Electronics category
AP2
Click Products link
AA2
Click Products link
H3
Click Smartphones filter
AP3
Click Electronics category
AA3
Click Electronics category
AP4
Scroll down page
AA4
Scroll down page
AP5
Click Smartphones filter
AA5
Click Smartphones filter
Table 1. Human and agent trajectories for the task: Show me all smartphones.
Prompt Component
Content and Purpose
Task Definition
You will be provided with two actions: 1. Human Recorded Action: [The human’s action description] 2. Agent-Recorded Action: [The agent’s action description, which may include metadata like IDs]. Your task is to determine whether the Human-Recorded Action and the Agent-Recorded Action are semantically equivalent.
Evaluation Criteria
Semantic Equivalence means both actions express the same intent. Your output must be a single numerical value: 1 if both actions are semantically identical, 0 if they are not. Note: 1. Minor textual variations such as differences in casing (‘Design’ vs ‘design’), extra/missing spaces, or punctuation should be ignored as long as the core identity and meaning are preserved. 2. Any substantive mismatch in meaning or details (e.g., different dates) must result in a 0
Chain-of-Thought (CoT)
Evaluation Steps: 1. Read the Human-Recorded Action and the Agent-Recorded Action carefully. 2. Rate the output as 1 (same) or 0 (different) according to the criteria above. Example: Human-Recorded Action: search for flights. Agent-Recorded Action: find flights. Output: 1
Table 2. Example prompt structure for semantic equivalence.
Figure 1. An example step from task 40 illustrating the agent’s decision-making process. The pink section, labeled A represents the previous action , the top gray section, labeled B details the agent’s reasoning process , the bottom gray section, labeled C , contains meta data , which we did not include in our analysis, and the yellow section, labeled D indicates the next action to be performed.
Website
Webarena Agent
Full-Plan-in-Advance Agent
delta
CMS
7.69%
3.85%
-3.84%
Gitlab
12.33%
10.96%
-1.37%
Map
10.39%
12.99%
-2.60%
Reddit
4.00%
8.00%
+4.00%
e-commerce
5.00%
2.51%
+4.00%
All
38.41%
36.29%
-2.12%
Table 3. Success rates and relative change of the Full-Plan-in-Advance and Webarena agents per domain.
Figure 2. Success rates of Step-by-Step agent and Full-Plan-in-Advance agent on the WebArena benchmark divided to success on each domain.
Figure 3. Results of the proposed evaluation metrics of Step-by-Step agent and Full-Plan-in-Advance agent on the WebArena benchmark averaged over all domains.
Evaluatin Metric
Webarena Agent
Full-Plan-in-Advance Agent
Step Success Rate
0.82±0.14
0.58±0.29
Step Success Rate (within successful tasks)
0.89±0.06
0.63±0.10
Element Accuracy
0.82±0.12
0.89±0.03
Repetitiveness Rate
0.79±0.14
0.81±.13
Recovery Rate
0.36±0.19
0.31±0.12
Partial Success Rate
0.22±0.39
0.12±0.27
Table 4. Average score for all metrics.
Task 82: What is the duration required to first walk from Massachusetts Institute of Technology to
Harvard University, and then drive to Boston Logan International Airport?
#
Human Trajectory
General Plan by Full-Plan-in-Advance agent
1
Click on the ’Find directions between two points’
Click on the link ’Find directions between two points’
2
Type ’Massachusetts Institute of Technology’ into the ’From’ textbox
Type "Massachusetts Institute of Technology" in the "From" textbox
3
Type ’Harvard University’ into the ’To’ textbox
Type "Harvard University" in the "To" textbox
4
Select the ’Foot (OSRM)’ option
Table 5. Human trajectory for Task 82 alongside the general plan produced by the Full-Plan-in-Advance agent. Differences between the two appear in bold text.
Agent
Number of Steps
Human
7.92±5.18
WebArena Agent
15.02±8.93
Full-Plan-in-Advance Agent
20.21±10.16
Table 6. Average number of steps (mean ± SD) observed across human golden trajectories, WebArena agent, and Full-Plan-in-Advance agent trajectories.
Figure 4. A step performed by the Full-Plan-in-Advance agent for task number 727, where the reasoning phase suggests scrolling in the correct format of the instruction, but the actual action taken in ‘None’. Task 727 : DisLike all submissions created by PatientBuilder499 in subreddit videos.
Figure 5. A step performed by the Full-Plan-in-Advance agent for task 392, where the reasoning phase suggests scrolling but does not follow the required action format, causing the actual executed action to be ‘None’. Task 392 : Post “Good idea” for the merge request related to color ulitity in a11yproject.com project.
Answer Category
WebArena Agent
Full-Plan-in-Advance Agent
N/A
17
20
Produced Answer
55
48
Percentage of Legitimate Answers
75.00%
70.83%
Early Stop
24
28
Sum
96
96
Table 7. Distribution of final-answer types for tasks requiring multiple correct elements, comparing how often each agent produced no answer (N/A), stopped early, or generated a final answer.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Original WebArena Prompt
Modified Prompt (Our Work)
…To be successful, it is very important to follow the following rules:… 4. Generate the action in the correct format. Start with a “In summary, the next action I will perform is” phrase, followed by action inside ````` . For example, “In summary, the next action I will perform is ``` click [1234] ''' ”…
… To be successful, it is very important to follow the following rules:… 4. Generate the action in the correct format. Start with a “In summary, the next action I will perform is” phrase, followed by action inside . For example, “In summary, the next action I will perform is click [1234] ''' ”….
Appendix
Table 8. Comparison of the original and modified prompts. We unify the action delimiter by replacing the inconsistent five-backtick instruction with the three-backtick format used in the example.
Original WebArena Prompt
Modified Prompt (Our Work)
OBSERVATION: [1744] link ‘HP CB782A#ABA 640 Inkjet Fax Machine (Renewed)’ [1749] StaticText ‘$279.49’ [1757] button ‘Add to Cart’ [1760] button ‘Add to Wish List’ [1761] button ‘Add to Compare’ URL: http://onestopmarket.com/office-products/office-electronics.html OBJECTIVE: What is the price of HP Inkjet Fax Machine PREVIOUS ACTION: None
OBJECTIVE: What is the price of HP Inkjet Fax Machine OBSERVATION: [1744] link ‘HP CB782A#ABA 640 Inkjet Fax Machine (Renewed)’ [1749] StaticText ‘$279.49’ [1757] button ‘Add to Cart’ [1760] button ‘Add to Wish List’ [1761] button ‘Add to Compare’ URL: http://onestopmarket.com/office-products/office-electronics.html PREVIOUS ACTION: None
Appendix
Table 9. Prompt format used in our work, showing the revised ordering of components.
Original WebArena Prompt
Modified Prompt (Our Work)
OBSERVATION: [164] textbox ‘Search’ focused: True required: False [171] button ‘Go’ [174] link ‘Find directions between two points’ [212] heading ‘Search Results’ [216] button ‘Close’ URL: http://openstreetmap.org OBJECTIVE: Show me the restaurants near CMU PREVIOUS ACTION: None, Let’s think step-by-step. This page has a search box whose ID is [164]. According to the nominatim rule of openstreetmap, I can search for the restaurants near a location by “restaurants near”. I can submit my typing by pressing the Enter afterwards. In summary, the next action I will perform is ``` Type [164] [restaurants near CMU] [1] '''
OBJECTIVE: Check if CMU can be reached in one hour by car from Hobart Street in Pittsburgh OBSERVATION: [656] textbox ‘From’ required: False [649] textbox ‘To’ required: False [609] combobox “ hasPopup: menu expanded: False [607] button ‘Go’ [629] button ‘Reverse Directions’ URL: http://openstreetmap.org PREVIOUS ACTION: click [174] where [174] is link ‘Find directions between two points’ Let’s think step-by-step. There are two textboxes available: one for the starting point and one for the destination. The one labeled ‘From’ , which is where I will type the starting location. I will search for ‘Hobart Street, Pittsburgh’ in the ‘From’ textbox that has an id of [656]. After typing, I will not submit my input by pressing Enter, because I need to complete the destinetion first. ACTION: In summary, the next action I will perform is ``` Type [656] [Hobart Street, Pittsburgh] [0] '''
Appendix
Table 10. Side-by-side comparison of the original WebArena prompt and our modified version. The modified prompt adds previous action information and incorporates structured hints to improve multi step reasoning.
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.
Mohamed Aghzal, Gregory J. Stein, Ziyu Yao
Department of Computer Science, George Mason University
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
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