STRUCTUREDAGENT: Planning with AND/OR Trees for Long-Horizon Web Tasks

ELita Lobo; Xu Chen; Jingjing Meng; Nan Xi; Yang Jiao; Chirag Agarwal; Yair Zick; Yan Gao

cs.AIMar 5, 2026

STRUCTUREDAGENT: Planning with AND/OR Trees for Long-Horizon Web Tasks

Authors: ELita Lobo, Xu Chen, Jingjing Meng, Nan Xi, Yang Jiao, Chirag Agarwal, Yair Zick, Yan Gao

Organizations: University of Massachusetts Amherst · Amazon · Virginia Commonwealth University · University of Virginia

Abstract

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 $\sim$ 53% success rate vs.\ $\sim$ 46% for AgentOccam, and on complex multi-constraint Amazon shopping tasks, gains reach 10% over the strongest baseline.

Figures & tables

Figure 1: Illustration of StructuredAgent solving a web task via greedy DFS of a dynamically constructed And/Or tree. The root node represents the task objective and is expanded into sub-tasks that are progressively refined and executed. Node types are color-coded to distinguish OR ( $\vee$ ), AND ( $\wedge$ ), and ACTION nodes. The top half tracks the corresponding DFS stack states, where each node enters the stack in one of three states: ENTERING (ENT), EXITING (EXT), or FAILED (FAIL). Node repair and pruning are supported but not triggered in this example, and human intervention is optional.

Figure 2: Illustration of the StructuredAgent Framework.

Figure 3: Overview of the primary operations used to construct and maintain the And/Or tree structure.

Method	Map $\uparrow$	Shopping $\uparrow$	Reddit $\uparrow$	GitLab $\uparrow$	Overall $\uparrow$
	(n=128)	(n=192)	(n=114)	(n=196)	(n=630)
StructuredAgent †	0.45 [0.37, 0.53]	0.53 [0.46, 0.60]	0.73 [0.64, 0.80]	0.46 [0.39, 0.53]	0.53 [0.49, 0.56]
AgentOccam (Claude)	0.46 [0.38, 0.55]	0.38 [0.31, 0.45]	0.60 [0.51, 0.69]	0.47 [0.40, 0.54]	0.46 [0.43, 0.50]
AgentOccam (GPT-4o)	0.45 [0.36, 0.53]	0.35 [0.29, 0.42]	0.62 [0.54, 0.71]	0.33 [0.26, 0.40]	0.41 [0.38, 0.45]
SteP (GPT-4o)	0.33 [0.26, 0.41]	0.27 [0.21, 0.33]	0.56 [0.47, 0.65]	0.22 [0.17, 0.28]	0.32 [0.29, 0.36]
BasicClaudeAction	0.37 [0.29, 0.45]	0.30 [0.24, 0.36]	0.30 [0.22, 0.39]	0.28 [0.22, 0.34]	0.31 [0.28, 0.34]

Table 1: Success rates on WebArena across four task categories, as mean [95% bootstrap CI]. Bold is best per column. †

p<0.05

vs. all methods (one-sided permutation test).

Table 5

Figure 4: Ablation analysis on Amazon tasks. Top: tree structure metrics (depth, nodes, pruning). Bottom: success, repair trigger, recovery rate, and revisions. The full agent (Repair+OR) builds deeper trees and achieves non-zero recovery on hard tasks.

Panel of Figure 5 — Figure 5: Trajectory length distributions on Amazon tasks. On hard tasks, StructuredAgent explores more strategies before terminating, leading to higher success rate, while baselines terminate prematurely with shorter but less successful trajectories.

Dimension	Gemini 2.5 Flash	Opus 4.8
Precision	86.8 (203/31/3)	94.7 (160/9/70)
Self sufficiency	64.3 (9/5/223)	72.4 (155/59/25)
Clarity	63.2 (91/53/93)	76.9 (183/55/1)
Actionability	78.3 (162/45/30)	67.6 (148/71/20)
Overall preference	81.7 (192/43/2)	75.2 (170/56/13)

Table 4: StructuredAgent vs. AgentOccam diagnosis quality on the 15 shared failures; cells give % favoring StructuredAgent (raw SA/AO/Tie). Details in Table 9 .

Appendix figures & tables38 assets

Supplementary material from the paper’s appendix.

Appendix

Backend	Temp.	top- $p$	Seed
Claude (Bedrock invoke_model )	0.0	NA	NA
Bedrock Converse (Kimi/Qwen/Nova/…)	0.0	NA	NA
OpenAI GPT	0.0	0.01	0
Kimi (Novita)	0.1	0.95	NA
Gemini	0.0	NA	NA

Appendix

Table 5: Decoding configuration by model backend. The Anthropic (Bedrock), Novita, and Gemini APIs do not accept a request seed, so determinism on those paths follows from greedy decoding. A request seed (fixed to

0

) is honored only on the OpenAI path.

Panel of Figure 6 — Figure 6: Distribution of average HTML observation lengths (in tokens) per timestep across agent trajectories on WebVoyager and the WebArena Shopping category. Token counts reflect only raw web page content, excluding any additional context provided to the agent.

Method	Map	Shop.	Reddit	GitLab	Overall
	(81)	(126)	(11)	(63)	(281)
StructuredAgent	0.348	0.432	0.545	0.383	0.401
AgentOccam	0.410	0.370	0.591	0.410	0.399

Appendix

Table 6: Success rates on WebArena using Kimi-K2 as the backbone model, evaluated on the subset of tasks with URL and string evaluators.

Panel of Figure 7 — Figure 7: Completion time distributions (in minutes) for StructuredAgent and AgentOccam across four WebArena task categories, with the mean marked per violin. StructuredAgent exhibits longer completion times and heavier right tails, reflecting greater variance in task duration due to its deliberate planning and dynamic replanning upon encountering failures.

Panel of Figure 8 — Figure 8: Average action counts per task for each agent on Amazon and WebVoyager Other tasks, broken down by action type (click, type, note, go_back). StructuredAgent and StructuredAgentMem issue more type and note actions on harder tasks because they gather and record more information about candidate items.

Panel of Figure 9 — Figure 9: StructuredAgent ’s longer trajectories on harder tasks (Map, GitLab) reflect systematic exploration of alternative strategies, which translates to higher overall success rates ( Table 1 ). On Shopping and Reddit, where StructuredAgent achieves the largest gains, trajectory lengths remain comparable to AgentOccam.

Panel of Figure 10 — Figure 10: Average action counts per task for each agent across three WebArena task categories (GitLab, Map, Reddit), broken down by action type (click, type, note, go_back, go_home). StructuredAgent issues more note actions because it records structured task information. Its click and type counts are similar to the baselines.

	Full	OR only	Repair only	Neither
Task Performance
Success Rate (Gemini)	68.3	65.0	75.0	60.0
Success Rate (Opus)	67.5	50.0	57.5	50.0
Constraint Satisfaction	89.3	83.5	87.7	77.2
Tree Structure
Browser Steps	19	8	22	8

Appendix

Table 7: And/Or tree analysis on the Amazon-easy split with a Haiku 4.5 backbone. Full uses both Node Repair and Or alternatives, OR only disables repair, Repair only disables Or nodes, and Neither disables both. All rates are percentages and count-valued metrics report means. Repair Trigger Rate counts node failures that would invoke repair, whether or not repair is enabled. The no-repair conditions make no repair attempts, so their Recovery Rate is reported as 0 by convention.

	Full	OR only	Repair only	Neither
Task Performance
Success Rate (Gemini)	38.3	13.3	35.0	16.7
Success Rate (Opus)	14.5	8.5	20.0	6.8
Constraint Satisfaction	82.8	59.8	77.8	57.3
Tree Structure
Browser Steps	43	11	46	12

Appendix

Table 8: And/Or tree analysis on the Amazon-hard split with a Haiku 4.5 backbone. Conditions and conventions are as in Table 7 . All rates are percentages and count-valued metrics report means.

Dimension	Gemini 2.5 Flash	Opus 4.8	Pooled
Precision	86.8 (203/31/3) ∗∗∗	94.7 (160/9/70) ∗∗∗	90.1 (363/40/73) ∗∗∗
Self sufficiency	64.3 (9/5/223)	72.4 (155/59/25) ∗∗∗	71.9 (164/64/248) ∗∗∗
Clarity	63.2 (91/53/93) ∗∗∗	76.9 (183/55/1) ∗∗∗	71.7 (274/108/94) ∗∗∗
Actionability	78.3 (162/45/30) ∗∗∗	67.6 (148/71/20) ∗∗∗	72.8 (310/116/50) ∗∗∗
Four dimension pooled	77.6 (465/134/349) ∗∗∗	76.9 (646/194/116) ∗∗∗	77.2 (1111/328/465) ∗∗∗
Overall preference	81.7 (192/43/2) ∗∗∗	75.2 (170/56/13) ∗∗∗	78.5 (362/99/15) ∗∗∗

Appendix

Table 9: Blinded comparison of StructuredAgent and AgentOccam diagnoses across 15 tasks that both agents failed, 4 diagnosis paraphrases, and 4 comparison paraphrases. Each cell reports the percentage of decided verdicts that favor StructuredAgent , followed by the raw counts SA/AO/Tie. The diagnosis model, Claude Opus 4.6, differs from both judges. We randomize the presentation order for each task under a fixed seed. We test significance with a one sided binomial test that compares StructuredAgent against AgentOccam and excludes ties. The markers ∗ , ∗∗ , and ∗∗∗ denote

p<0.05

p<0.01

, and

p<0.001

You are an expert evaluator analyzing web browsing agent trajectories to diagnose why a task failed. You will be given: the task objective, which constraints were NOT satisfied, and the agent’s step-by-step trajectory. Your job is to perform a precise root-cause analysis of why the agent failed. You MUST respond in this exact JSON format: {"root_cause": "<one sentence: the primary reason the task failed>", "critical_steps": [ {"step_number": <int>, "what_happened": "<what the agent did>", "what_went_wrong": "<why this was the critical error>"} ], "what_should_have_been_done": "<specific alternative action(s)>", "failure_category": "<one of: wrong_search_strategy | missed_information | navigation_error | premature_stop | constraint_violation | verification_failure | other>", "confidence": <1-5 integer> } EXAMPLE of a valid response (structure only – your content will differ): {"root_cause": "The agent searched with the wrong keyword and never applied the price filter.", "critical_steps": [ {"step_number": 2, "what_happened": "Typed ’cheap laptop’ into search", "what_went_wrong": "Ignored the required ’under

500’ constraint, returning irrelevant results"}, {"step_number": 5, "what_happened": "Clicked the first result and stopped", "what_went_wrong": "Never verified the price met the constraint"} ], "what_should_have_been_done": "Search ’laptop’, then apply the <

500 price filter and sort by rating before selecting.", "failure_category": "wrong_search_strategy", "confidence": 4 } Output ONLY the JSON object – no prose before or after, no markdown code fences. Use exactly these keys, once each. GROUNDING (mandatory): Every claim in your diagnosis MUST be grounded in or directly implied by the observations, actions, and notes in the trajectory. Do NOT assume, infer, or invent any fact that is not present in the trajectory. If the trajectory does not make the root cause clear, say so explicitly in "root_cause" and set a LOW "confidence" (1-2) rather than guessing. Do not use hedging like "likely" or "probably" to smuggle in unsupported claims. Guidelines: - Be SPECIFIC. Name the wrong search term, the missed filter, the unexplored page. - Point to exact step numbers where the critical error occurred. - The fix should be concrete and actionable. - Confidence 5 = root cause obvious; 1 = unclear.

Appendix

Table 10: Diagnosis prompt (detailed variant) that we use in the error localization experiment. We append the agent trajectory below this system prompt. AgentOccam receives its flat step sequence with the notes it records at each step. StructuredAgent receives its AND/OR tree with per-node status followed by its step sequence with the notes it records at each step.

Method	Human
StructuredAgent	56.7
AgentOccam	55.0
BasicClaudeAction	40.0

Appendix

Table 11: Human evaluation task-success rate (%) on the 60 Amazon-hard tasks. A single independent annotator (non-author) judged whether each method fully completed each task from its full trajectory. Table 13 shows an example where the annotator overlooked unmet constraints and marked a partially correct answer as complete.

Judge	Agent	Agr. (%)	$\kappa$	Sat. (%)
GPT-4.1-mini	StructuredAgent	81.7	0.64	87.2
	AgentOccam	75.0	0.50	90.8
	BasicClaudeAction	86.4	0.71	82.7
Gemini-2.5-Flash	StructuredAgent	71.7	0.45	82.1
	AgentOccam	68.3	0.38	84.8
	BasicClaudeAction	86.7	0.71	78.9

Appendix

Table 12: Evaluator reliability on the 60 Amazon-hard tasks, per judge and agent. Agr. and Cohen’s

\kappa

measure how well each judge’s per-task success labels match the human annotator’s. Sat. is the judge’s mean constraint-satisfaction rate, the mean of

(\text{satisfied}+1)/(\text{total}+1)

across tasks.

Agent	Recommended printer (price)	Wireless, $<$ $150	AirPrint	Borderless 4 $\times$ 6
AgentOccam	Canon TS5320 ($85.99)	✓	✓	✓
	Epson XP-5200 ($79.99)	✓	✗ (not observed)	✓
	Canon TS702a ($109.00)	✓	✓	✗ (not observed)
StructuredAgent	Canon PIXMA TS6420a ($44.99–109.95)	✓	✓	✗ (not observed)
	Canon PIXMA TR4720 ($64.00)	✓	✗ (not observed)	✓
	HP DeskJet 2827 ( $\cdots$ )	✓	✗	✗

Appendix

Table 13: Case study of task Amazon–DeepMulti-603. The task asks the agent to recommend three wireless printers under

150 that support both AirPrint and borderless 4

\times$ 6 photo printing, to list brand, print support, and price, and not to add to cart. The printer rows reproduce each agent’s returned answer. ✓ and ✗ mark whether each requested spec is grounded in the page observations rather than only asserted by the agent. AgentOccam asserts that all three of its printers meet the specs, but the observations confirm this for only the TS5320. StructuredAgent states in its answer that none of its printers fully meet all requirements. The human annotator nevertheless marks AgentOccam as a success, while the LLM judge, which requires every spec to be grounded in the observations, marks both agents as failures.

You are a web-browsing assistant designed to extract structured constraint data from user queries. Given a natural language query, your task is to identify and return: 1. A list of distinct items the user wants to retrieve (if any). 2. For each item, a list of item-level constraints that are explicitly mentioned in the query. 3. A separate list of task-level constraints that apply to the overall task. Definitions: - Item: A specific product, object, or entity that the user wants to find or retrieve information about. - Item-level constraint: Any attribute or specification that is directly tied to an individual item. This may include (but is not limited to): brand, model, price, rating, features, color, size, dimensions, delivery time, material, and any other explicitly stated property of the item. - Task-level constraint: A condition that affects the overall search or task execution rather than a specific item. Instructions: - You must extract only those task-level and item-level constraints that are explicitly stated in the query. - You must not assume, infer, or interpret any implicit constraints, even if they seem logically implied or contextually likely. - Do not include any reasoning, commentary, or explanation in your output. - Each item type must appear only once in the ‘ITEM_CONSTRAINTS‘ list. - If the query contains no valid constraints or items, return empty lists using the required format. Output Format: The result must be returned strictly in the following JSON format: {"TASK_CONSTRAINTS": ["explicit_task_constraint1", "explicit_task_constraint2", "…"], "ITEM_CONSTRAINTS": [ { "item_type": ["explicit_item_constraint1", "explicit_item_constraint2", "…"] }, … ] } EXAMPLE: QUERY: Find a black laptop bag under

40andawirelessmouseunder

25. Both should be delivered within 2 days. URL: www.amazon.com OUTPUT: {T̈ASK_CONSTRAINTS:̈ [ ], ÏTEM_CONSTRAINTS:̈ [ { "laptop bag": [ "Color: black", "Price: under

40", "Delivery time: within 2 days" ] }, { "wireless mouse": [ "Price: under

25", "Type: wireless", "Delivery time: within 2 days" ] } ] } QUERY: {task_objective}

Appendix

Table 14: Prompt for extracting task constraints for task completion evaluation.

You are an evaluator assessing the performance of a web-browsing agent on a specific task. You will be provided with the following components: - Task Description A natural-language instruction outlining the goal the agent is expected to accomplish. This may involve retrieving, summarizing, comparing, or verifying information from the web. - Constraints A list of specific item-level and task-level requirements that must be satisfied for the task to be considered successful. - Trajectory Summary A step-by-step log of the agent’s interaction with the environment. Each time step includes: - Observation: Summary of the web-page the agent perceives at that moment. - Action: The behavior or command the agent executes (e.g., clicking, searching). - Interaction History Summary: Summary of the agent’s progress (if available) - The agent’s final response to the task - Evidence extracted from raw observations A digest of what was actually observed across the agent’s full trajectory. Evaluation Guidelines - Evaluate each item-level constraint once per item type. Do not repeat the constraint evaluation for each instance of the same item type. Instead, assess whether the constraint is satisfied across all relevant items of that type, and justify the evaluation with evidence from the observations, notes, or interaction history. For example: If the task requires finding 3 laptops under

1000,andtheagentrecommends3laptops,evaluatetheconstraint"Price\mathrel{\mathop{\mathchar 58\relax}}under

1000" only once. Mark it as satisfied only if all 3 laptops meet the price constraint. - Only use information that is explicitly visible in the agent’s observations, actions, notes, and final response. Do not rely on external knowledge, domain expertise, or assumptions made by the agent. - Do not assume that a constraint is satisfied based on the agent’s search terms, reasoning, or keyword usage (e.g., searching for "size 6"). A search query does not guarantee that the results meet the constraint. A constraint is only considered satisfied if the specific value (e.g., "Size: 6") is explicitly shown in the observations, actions or agent’s notes. - If the task requires finding the cheapest, most rated, or most reviewed item, only verify that appropriate filters or sorting options were applied - but only if those options are actually available on the website. - Evaluate only based on the final response of the agent. Intermediate steps or partially explored options should not be considered unless they directly contribute to the final result. - Do not award partial credit for incomplete constraints. A constraint is either fully satisfied or not satisfied. All requested attribute values (e.g., price, brand, size) are treated as separate constraints. - Do not evaluate the agent based on constraints that are not explicitly stated in the task description. For example, if the task does not mention "size," "material," or "capacity," do not treat them as constraints — even if the agent includes or discusses them during the task. - If there is no final response or the task is incomplete, assign a score of 0. - You do not need to consider constraints that require the agent to find items with a given delivery period as the agent does not have access to the current date and time. Scoring Instructions - Assign 1 point for each item-level or task-level constraint that is fully and explicitly grounded in the observations, notes and actions. Confirm that the agent is not hallucinating. Note: If the recommended item costs less than the specified price, it still satisfies the price constraint. Evidence for constraints satisfied must be grounded only in observations, notes and actions. Do not ground evidence in the final response of the agent. - Assign 0 points for constraints that are: - Not satisfied or Partially Satisfied - Assumed or inferred without explicit evidence in observations, notes, or final response - Assign 1 point if the task was completed successfully and the final response is likely not hallucinated. A task is considered completed successfully if the agent provides a clear and specific final response that directly fulfills the task objective, and is explicitly supported by observed content or notes. - Normalize the score: Score = (Number of Satisfied Constraints + 1 point if task completed) / (Total Number of Constraints + 1) This yields a final score between 0.0 and 1.0. Final Verdict - SUCCESS – Only if all explicitly stated item and task-level constraints are fully satisfied (score = 1.0) - FAILURE – If any constraint is not satisfied, or if the task is incomplete (score < 1.0) Your response must strictly follow this format: 1. Task Overview - Task Description: (Copy the task as provided.) - Constraints: (List the item-level and task-level constraints exactly as stated in the task description. Do not infer or add any additional constraints.) 2. Evaluation of Each Constraint Evaluate each constraint using one of the following labels: - Satisfied - Partially Satisfied - Not Satisfied Constraint 1: Evidence: Evaluation: Reason: Constraint 2: Evidence: Evaluation: Reason: (Continue for all constraints.) Note: Evidence must be grounded in observations, notes and actions only. Evidence cannot be grounded in the final response of the agent. 3. Agent Behavior Assessment - Action Effectiveness: Was the agent’s sequence of actions appropriate and goal-directed? - Interpretation Accuracy: Did the agent correctly interpret the content it observed? - Handling of Multi-step Tasks (if applicable): Did the agent address all required components of the task? 4. Final Scoring - Total Satisfied Constraints: X - Total Constraints: Y - Score (X / Y): Z - Final Verdict: SUCCESS / FAILURE 5. Summary Comments (Optional) (Provide any additional insights or suggestions about the agent’s behavior or reasoning.) OBJECTIVE: {objective} CONSTRAINTS: {constraints} FINAL RESPONSE: {notes} TRAJECTORY {trajectory}

Appendix

Table 15: Prompt for evaluating completion of task based on observation summaries, actions, notes and final response of the agent.

You are a meticulous evidence-EXTRACTION assistant. You are NOT the judge. You are shown the raw text of ONE web page OBSERVATION (an accessibility tree / page dump) captured during a browsing session, plus the OBJECTIVE and CONSTRAINTS. Your only job is to COPY OUT, verbatim, every snippet in THIS observation that bears on any constraint or on overall task completion, and return it as JSON. VERBATIM RULE (most important): every "quote" you emit MUST be an EXACT, character-for-character substring of THIS observation’s raw text – copy-pasted. Do NOT reword, summarize, normalize, round, translate, or reformat. If a price appears as "-31 109.98 List:159.99", copy exactly that; never rewrite it as "$109.98". If a title spans a long string, copy the whole literal string. A reader must be able to Ctrl-F your quote and find it unchanged in this observation. BANNED – never report content in your own words ("the page shows", "it lists", "priced at", etc.). Every "quote" is a raw verbatim substring; nothing else. OUTPUT FORMAT – return ONLY a JSON object, no prose, no markdown fences: {"items": [{"constraint": "<the constraint label from CONSTRAINTS this snippet bears on, verbatim>", "quote": "<exact verbatim substring copied from THIS observation>", "step_id": <the integer step id given below>}]} - One entry per distinct relevant snippet. If several constraints share one snippet, emit one entry per constraint. - If NOTHING in this observation bears on the task, return exactly: {"items": []} Rules: - Copy real text from THIS observation only. Never invent. Never infer. Never reference other steps. - Do NOT read or rely on any agent’s summary or answer – extract only from the raw observation text. - Do NOT judge. No verdict/status/agreement words. Only the JSON object. EXAMPLE (illustrative only – a made-up museum page, unrelated to your actual task): CONSTRAINTS: ["Ticket price: under 20 EUR", "Open on Mondays"] THIS OBSERVATION (step_id=2): "link ’Rijks Gallery’ StaticText ’Adult admission EUR 18,50’ StaticText ’Closed on Mondays’ button ’Buy’" Correct output: {"items": [{"constraint": "Ticket price: under 20 EUR", "quote": "Adult admission EUR 18,50", "step_id": 2}, {"constraint": "Open on Mondays", "quote": "Closed on Mondays", "step_id": 2}]} Note the quotes are copied character-for-character (e.g. "EUR 18,50", not "18.50 euros").

Appendix

Table 16: Prompt for extracting grounded, verbatim evidence from each raw observation. The per-observation snippets are consolidated into the evidence digest supplied to the evaluator.

You are an efficient And/Or Tree Constructing Agent specialized in web-browsing tasks. You solve complex problems using And/Or planning trees. You dynamically construct And/Or planning trees from observations of the webpage’s HTML DOM structure for efficient and robust task execution. You are provided: - root-level task description - task constraints at item level - HTML DOM structure as the observation - node_id and desription of the node to analyze - summary of current task progress - summary of notes taken so far - Information about node’s siblings node’s parent’s siblings. Node definitions: Node Types <AND/ OR / Atomic> - node: Represents an ordered list of logical sub-goals required to achieve the node’s objective. - Or node: Represents alternative sub-strategies (which can be other And/Or nodes) - Atomic Action: Single executable action strictly matching navigation_specifications described below. Node status indicators: - Unvisited nodes marked UNVISITED - Pruned nodes marked PRUNED - Completed nodes marked SUCCESS - Temporarily failed nodes marked FAIL NAVIGATION_SPECIFICATIONS: <LIST OF BROWSER ACTIONS> Your Task For the given node: 1. First, briefly analyze the node type: Based on the available information and the node description, determine whether the node is an node, an Or node, or an Atomic node. Justify your reasoning before taking any action. 2. Then, choose ONE of the following options for the node: A. MARK node as Atomic if: - the goal can be achieved using a single atomic action that strictly matches the NAVIGATION_SPECIFICATION. OR - the goal does not require any browser navigation actions like ‘type‘, ‘click‘, and ‘go_back‘ and is information retrieved from thr webpage that can be noted down using the ‘note‘ action. B. EXPAND the node if: - the goal is not atomic and requires executing a sequence of atomic actions from NAVIGATION_SPECIFICATIONS. Clearly state the node type (AND/OR): - Do not consider sub-goals and sub-strategies that cannot be executed on the webpage using one action or a sequence of actions from NAVIGATION_SPECIFICATIONS. - For nodes, provide ordered list of logical sub-goals that are necessary for satisfying the node’s objective. - For Or nodes, provide observable list of alternative sub-strategies only. - For Or nodes, order alternatives by likelihood of success, assigning scores within the range (0,1). - Do not add speculative or redundant sub-goals. VERY IMPORTANT RULES: - Focus on expanding nodes in a way that will result in completing the task faster with high probability (Don’t take very risky actions). - Make sure that the temporal order of the children of an node is correct, detailed, and efficient. - Make sure to not split notes into multiple atomic actions. - Strictly do not use ‘note‘ for noting future actions or sub-goals. For example, this is not a note -> ‘[Need to examine each search result for: 1. Publication date 2024 2. Review count 20+ 3. Confirm it’s a Japan travel guide book]‘ - Use ‘go_back‘ action to return to previous page especially when you have consecutive atomic actions like ‘click‘, ‘type‘, ‘goto‘. - Atomic actions like ‘type‘, ‘click‘ must be accompanied with valid IDs from the HTML DOM observation. - Use atomic action ‘note‘ strictly to note information that is necessary for completing the task or for actions that cannot be executed on the webpage. - Expand only non-atomic steps. Do not decompose goal when it is directly achievable using an action from NAVIGATION_SPECIFICATIONS. - Create Or nodes to consider different alternative strategies in cases where failure is probable. - Structure plans as a knowledgeable efficient human would. Output Format: Begin by briefly describing the key elements from the input (overall task description, task progress, task feedback, task notes, node description, observation). Then analyze the node within the given context and clearly identifying its type. Do not change the node’s intended objective or assume a different node objective. Your highest priority is satisfying the node’s objective. You can borrow notes from the notes summary if it helps in achieving the node’s objective. Use the local tree information to ensure that you are not repeating any sub-goals that have already been considered. If the node is an Atomic Action, determine and briefly analyze the 3 best possible actions it could represent. For each, explain why it fits the context. Then, select the single best action among them that is not very risky and will contribute to faster completion of the task and justify your choice. Conclude your response using ONE of the following formats: FORMAT 1 (Enclose all values in <<>> on a single line): Node ID: <<node_id>> Node Description: <<Describe what does the atomic action do>> Node Type: <<Atomic>> Expansion: <<Exact Atomic action from NAVIGATION_SPECIFICATIONS>> Reasoning: <<Brief justification explaining why the node is classified as Atomic>> OR FORMAT 2 (Enclose all values in <<>> on a single line, colon (;) separated): Node ID: <<node_id>> Node Description: <<node_description>> Node Type: <<AND / OR>> Expansion: <<1. First sub-goal; 2. Second sub-goal; 3. Additional sub-goals>> OR <<1. Alternative strategy; 2. Alternative strategy; Additional alternatives as necessary;…>> Reasoning: <<Brief justification explaining why the node is classified as AND, OR, or Atomic, based on current observations.>> Example 1: Node ID: <<2.1>> Node Description: <<Find recipe with visible ratings and review counts>> Node Type: <<Atomic>> Expansion: <<click [123]>> Example 2: Node ID: <<2>> Node Description: <<Filter results by rating and number of reviews>> Node Type: <<AND>> Expansion: <<1. click [Recipe with 69 ratings to check star rating]; 2. go_back; 3. click [Check page 2 if first recipe doesn’t meet criteria]; 4. go_back; 5. click [Check page 3 if needed]>> Example 3: Node ID: <<0.5.1>> Node Description: <<Filter recipes by rating and review count>> Node Type: <<OR>> Expansion: <<1. Manually scan recipe listings for review counts and ratings (score: 0.9), 2. Click through to individual recipes to check ratings and reviews (score: 0.8)>> Do not output anything outside of the specified format. Atomic actions must strictly match format specified in NAVIGATION_SPECICATIONS. NOTE: Atomic actions ‘click‘ and ‘type‘ must be accompanied with valid IDs from the HTML DOM observation. ROOT-LEVEL TASK DESCRIPTION: {task_description} ITEM LEVEL CONSTRAINTS: {item_constraints} {additional_context} OBSERVATION: {observation} NODE_ID : Description: node_id : {node_description} LOCAL TREE INFORMATION: {local_tree_info}

Appendix

Table 17: Prompt for node expansion.

You are an And/Or Tree Completeness Evaluator Agent specialized in web-browsing tasks. Your role is to assess whether a given node’s objective has been successfully executed by the child nodes. Node definitions: Node Types <AND/ OR / Atomic> - node: Represents an ordered list of logical sub-goals required to achieve the node’s objective. - Or node: Represents alternative sub-strategies (which can be other And/Or nodes) - Atomic Action: Single executable action strictly matching navigation_specifications described below. Node status indicators: - Unvisited nodes marked UNVISITED - Pruned nodes marked PRUNED - Completed nodes marked SUCCESS - Temporarily failed nodes marked FAIL NAVIGATION_SPECIFICATIONS: <LIST OF BROWSER ACTIONS> You are provided: - The root-level task description - Item level constraints if any - node_id and description of the node to analyze - Task progress summary - Notes summary: notes taken by the agent so far - A list of its children: each with an ID, description, and status (SUCCESS, VISITED, UNVISITED, or PRUNED) - Task feedback Your task is to determine whether a given node is complete. Follow the steps below to make this determination: 1. Examine the current children of the node and their statuses. - Identify each child sub-goal or atomic action. - Check whether each is marked as SUCCESS, FAILURE, or INCOMPLETE. 2. Review the task progress, task feedback, and notes summary. - Look for any additional information that confirms or contradicts the completion of the node’s objective. 3. Determine whether all required sub-goals or actions are present. - Ensure no required sub-goals are missing. - Confirm that the sub-goals appear in the correct order, as expected based on the task tree and the overall task objective. 4. Verify that each required sub-goal or atomic action is marked as SUCCESS. - Do not assume completion unless it is explicitly indicated. - Partial or INCOMPLETE statuses are not sufficient. 5. Conclude that the node is COMPLETE only if: - All required sub-goals or atomic actions are present, in the correct order, and marked SUCCESS; OR - The successful child nodes, task progress summary, and task feedback clearly indicate that the node’s objective has been fully achieved. - You are only required to satisfy explicitly stated constraints. Do not assume or enforce any implicit constraints. 6. Mark the node as INCOMPLETE if: - The node’s objective is not fully achieved, or - Any required sub-goal, step, or relevant information is missing or not marked SUCCESS. Special Case - Root Node Evaluation: If the node being evaluated is the root node, you must additionally verify whether the overall task objective is fully satisfied. - If the task requires recommending or evaluating items, then: - You must iterate over each item that is being considered or presented as a recommendation. - For each item, check whether it satisfies all task constraints explicitly provided in the task description or item-level constraints. - Note that constraints that are not explicitly mentioned in the task need not be satisfied. - The node is incomplete if any recommended item fails to meet required constraints or if evaluation is missing or partial. - The node is incomplete if the task is incomplete and some information explicitly required by the task is missing. - Do not assume any additional implicit constraints than the ones explicitly specified. Begin by analyzing all the information provided (task progress summary, notes summary, node description, children description). Provide a brief explanation for your decision, citing any missing, out-of-order, or incomplete sub-goals if relevant. End your response in strictly one of the following formats, using a single line (reasoning node id must be enclosed in <<>>): If node’s objective is achieved: COMPLETE <<node_id>> Reasoning: <<Reason why node’s objective is achieved by the agent. Cite references from task progress summary, notes summary and successful children’s description>> OR If node’s objective is not achieved: INCOMPLETE <<node_id>> Reasoning: <<Reason why node’s objective is not achieved by the agent, Cite references from task progress summary, notes summary and successful children’s description>> Example 1: COMPLETE <<0.1>> Reasoning: <<All required sub-goals for finding a compact digital camera with specified requirements are present, in logical order, and marked as SUCCESS.>> Example 2: INCOMPLETE <<0.2>> Reasoning: <<The sub-goal to compare prices is marked as PRUNED, and the sub-goal to check reviews is missing. The node’s objective is not fully achieved.>> You must strictly follow the above format. {additional_context} NODE ID : DESCRIPTION node_id : {node_description} CHILDREN {children}

Appendix

Table 18: Prompt for evaluating if an node’s objective has been achieved.

You are a Global And/Or Tree Update Agent revising an existing planning tree for a web-browsing task based on current available information so that the task is executed more efficiently. Do not change the ordering of the sub-plans. Node definitions: Node Types <AND/ OR / Atomic> - node: Represents an ordered list of logical sub-goals required to achieve the node’s objective. - Or node: Represents alternative sub-strategies (which can be other And/Or nodes) - Atomic Action: Single executable action strictly matching navigation_specifications described below. Node status indicators: - Unvisited nodes marked UNVISITED - Pruned nodes marked PRUNED - Completed nodes marked SUCCESS - Temporarily failed nodes marked FAIL NAVIGATION_SPECIFICATIONS: <LIST OF BROWSER ACTIONS> You are provided: -The root-level task description -Current And/Or tree description -HTML DOM structure as the observation - Task progress summary - Notes summary: Summary of notes taken by the agent during the task Your task is to carefully analyze all the information provided and determine which nodes to prune and which nodes to update. Apply changes in this strict order: 1. PRUNE nodes that are no longer relevant or are duplicates. 2. UPDATE node descriptions if intent is unchanged but content needs minor revision. VERY IMPORTANT RULES: - You are only allowed to PRUNE or UPDATE nodes that have not been deleted, pruned, or marked successful. - Do not add status of the node while updating the description. - Only use existing node IDs from the current tree; do not create new node IDs or subtrees. - Do not PRUNE important observations relevant to the task made in Atomic nodes with action ‘note‘. - Do NOT PRUNE children that are necessary for satisfying the parent node’s objective. - Do not change node types. - Do not change the ordering of the sub-plans. First reason about the update to the tree based on the information given (task description, item constraints, task progress summary, notes summary, current And/Or tree description, observation) to you and then given your answer in the following format. Use the And/Or tree description to ensure that you are not repeating any sub-goals that have already been considered. Format each instruction on a new single line in the format given below (All children and description must be enclosed in <<>>. Children should be colon (;) separated): PRUNE [node_id] UPDATE [node_id] <<Describe the node’s new objective (sub-goal/strategy/description of action)>> Example: PRUNE [1.2] PRUNE [1.3] UPDATE [0.1.2] <<type eggless cake in search bar>> UPDATE [0.2] <<Find an eggless cake recipe with over 60 votes and at least 4.5 star rating by examining search results>> Do not split the list across multiple lines. ROOT-LEVEL TASK DESCRIPTION: {task_description} {additional_context} AND/OR TREE DESCRIPTION: {and_or_tree_description} OBSERVATION: {observation}

Appendix

Table 19: Prompt for global tree update.

You are a Web-browsing Agent specialized in web-browsing tasks. You have taken notes while completing a given task and now you need to generate an output for the task based on the notes you have collected. You are provided: - Task description - Sequence of notes taken during the execution of task - Planning tree representation of the task Node definitions: Node Types <AND/ OR / Atomic> - node: Represents an ordered list of logical sub-goals required to achieve the node’s objective. - Or node: Represents alternative sub-strategies (which can be other And/Or nodes) - Atomic Action: Single executable action strictly matching navigation_specifications described below. Node status indicators: - Unvisited nodes marked UNVISITED - Pruned nodes marked PRUNED - Completed nodes marked SUCCESS - Temporarily failed nodes marked FAIL Your Task is to: Give a detailed response that directly addresses the task description, using only the information from the notes and the planning tree presentation. Do not add any additional information or context that is not present in the notes. Even if the selected notes indicate that the task was not complete or certain information is missing or constraints are not met, provide the best possible response based on the available information. Do not make assumptions or inferences beyond what is explicitly stated in the notes. VERY IMPORTANT RULES: - Do not assume any details or context that is not explicitly mentioned in the notes. Output Format: Begin by analyzing the notes, then give your detailed final response in the following format.: Task Response: <<Your detailed response to the task based on the notes. If the task was not completed, this may include incomplete information or recommendations that do not meet the constraints or requirements, if applicable. If the task was completed successfully, ensure all required details are specified. Do not skip any information that is required by the task.>> Example: Task Response: <<I successfully found a recipe for an eggless chocolate cake with over 60 votes and a rating of 4.5 stars. The recipe includes ingredients such as flour, sugar, cocoa powder, and baking soda. I also noted that the recipe requires 30 minutes of preparation time….>> TASK DESCRIPTION: {task_description} NOTES TAKEN DURING TASK EXECUTION: {notes} {additional_context}

Appendix

Table 20: Prompt for generating final task response from notes taken during execution.

You are a Context Summarization and Critiquing Agent for web-browsing tasks. Your job is to maintain an accurate, up-to-date understanding of task progress by analyzing: - Task description - Item-level constraints (if any) - Task progress summary (if provided) - Observation history (if provided) - Action history (if provided) - Notes summary: summary of notes taken by the agent so far (if provided) - Current observation (HTML DOM) INSTRUCTIONS: 0. Do not infer any details or make assumptions. 1. Analyze all available inputs, especially the current HTML DOM. 2. Ensure all summaries remain aligned with the main task objective. 3. Do not omit any information that may influence decisions or navigation. 4. Make summaries detailed, well-structured, and actionable. 5. Use the format below exactly. 6. Enclose the response to each section in double angle brackets: ‘<< >>‘. Begin by analyzing the given context in detail. Then given your response stricly in the following format. Your output must ensure continuity, preserve all essential details, and contribute to successful task completion. RESPONSE FORMAT: OBSERVATION SUMMARY <<Describe the information from the CURRENT OBSERVATION. Emphasize elements and features that are relevant or potentially useful for fulfilling the task objective. Include all important detail.>> OBSERVATION HIGHLIGHTS <<Single list of integer element IDs (i.e., [123, 8765, 345]) from the current DOM that are relevant for interaction or for revisiting this step later. Only include elements from the current page. Sort by relevance, with the most important listed first.>> TASK PROGRESS <<Analyze the task progress using the task description, item-level constraints, past progress summaries, observation history, action history, and notes. First, summarize the key high-level steps the agent has actually taken toward completing the goal, focusing only on actions that were executed. Next, evaluate whether each explicitly stated task requirement or constraint has been satisfied—if the task involves item selection or recommendation, assess each item individually for compliance. Do not assume or infer unstated constraints. Finally, diagnose why the task has not yet been completed: identify any unsatisfied constraints, incorrect actions, or gaps in execution. Conclude with key takeaways or insights from the agent’s exploration that are relevant to achieving successful task completion.>> TASK FEEDBACK <<Based on the task progress summary, provide an outline of what the agent should focus on next to successfully complete the task. (2 sentences)>> Example: OBSERVATION SUMMARY <<The page shows search results for "iPhone 12 Pro Blue 128GB" on Amazon. The first relevant listing is an Apple iPhone 12 Pro, 128GB in Pacific Blue (Renewed) for

314.39. Multiple other iPhone models are also shown including iPhone 12, 13, and 14 in various colors and storage configurations….>> OBSERVATION HIGHLIGHTS <<[6028, 6033, 6042, 7204, 9277, 9280, 7242]>> NEW NOTES <<Refer to the task description and constraints, and identify all new information that can be used to completing the task. This should support future reference and continuity. Do not assume any information or make up new details. All details must be grounded in observation and actions. >> TASK PROGRESS <<The agent has successfully navigated to an Amazon search results page and identified a relevant product listing matching the task requirements. Specifically, the agent located an Apple iPhone 12 Pro with 128GB of storage in Pacific Blue, listed for

314.39 in renewed condition and fully unlocked. This matches the explicitly stated constraints for model, color, and storage capacity. The observation and notes confirm that the identified product has a strong customer rating (4.1 out of 5 from over 12,000 ratings), further supporting its relevance. All explicitly defined task constraints appear to be satisfied: model (iPhone 12 Pro), storage (128GB), color (Pacific Blue), fully unlocked, and condition (renewed). However, the task has not yet been completed. The agent has not taken action to click on the product listing, verify the full product details on the product page, or add the item to the cart. These remaining steps are essential for completing the task, as product details may vary across pages. The main takeaway is that the search and identification phase has been completed successfully, and the agent should now focus on verifying the product and adding it to the cart to fulfill the task requirements.>> TASK FEEDBACK <<The next step should be to click on the product listing to verify all details on the product page and then add it to the cart. The agent should ensure the exact model and specifications are confirmed before proceeding with the purchase. Focus on completing the final step of adding the item to cart.>> Do not output anything outside of the specified format. TASK DESCRIPTION: {task_description} {additional_context} CURRENT OBSERVATION: {observation}

Appendix

Table 21: Prompt for generating observation summary and context summary.

You are an advanced web-browsing agent that solves web-browsing related tasks. Your job is to generate notes base on current observation as well as formulate a response to the task query based on the notes and available information. You are given: - Task description - Item-level constraints (if any) - Task progress summary (if provided) - Action history (if provided) - Notes: Notes taken so far (if provided) - Current observation (HTML DOM) INSTRUCTIONS: 0. Do not infer any details or make assumptions. 1. Analyze all available inputs, especially the current HTML DOM. 3. Do not omit any information that may influence decisions or navigation. 5. Use the format below exactly. 6. Enclose the response to each section in double angle brackets: ‘<< >>‘. Begin by analyzing the context in detail. Given your final answer strictly in the following format. RESPONSE FORMAT: NEW NOTES <<Refer to the task description and constraints, and identify all new information that can be used to completing the task. This should support future reference and continuity. Do not assume any information or make up new details. All details must be grounded in observation. Do not skip any important notes relevant to the task. >> TASK RESPONSE <<Give a detailed response (you may repeat information from the above notes) that directly addresses the task description and constraints (if any), using only the information from the previous notes,new notes, and the action history. Do not add any additional information or context that is not present in the available information. Even if the selected notes indicate that the task was not complete or certain information is missing or constraints are not met, provide the best possible response based on the available information. Do not make assumptions or inferences beyond what is explicitly stated in the notes.>> Example: NEW NOTES <<Found relevant iPhone 12 Pro listing matching requirements: - Model: iPhone 12 Pro - Storage: 128GB - Color: Pacific Blue - Price:

314.39 - Condition: Renewed - Fully Unlocked - Rating: 4.1/5 stars from 12,669 ratings>> TASK RESPONSE <<Based on the task requirements, I have found an Apple iPhone 12 Pro with 128GB of storage in Pacific Blue, fully unlocked, in renewed condition, and priced at

314.39. The listing has a solid customer rating of 4.1 out of 5 from 12,669 reviews.>> Do not output anything outside of the specified format. TASK DESCRIPTION: {task_description} {additional_context} PREVIOUS NOTES: {notes} CURRENT OBSERVATION: {observation}

Appendix

Table 22: Prompt for generating notes summary.

You are an advanced web-browsing agent. Your task is to maintain a table of candidate items by parsing the current webpage’s HTML DOM and applying ’ADD’, ’UPDATE’, or ’DELETE’ actions. Your goal is to keep the table accurate, up to date, and free of duplicates, based only on information explicitly visible in the DOM. You are given: -HTML DOM of the current webpage - task description - item-level constraints VERY IMPORTANT - Record all important details that are relevant to the task and can be used for completing the task. Include any additional relevant details. - Only include keys whose values are clearly visible in the HTML DOM. Record the exact value corresponding to each key. - Keys must match attributes listed under ITEMS AND CONSTRAINTS. IMPORTANT RULES Use this table to keep track of potential candidate solutions that can be used in the future for task completion or if search fails. 1. Matching and Deduplication - Before using ‘ADD‘, check whether the item already exists in the candidate table. - An item is considered a duplicate if all its visible fields match an existing entry (even if the ID differs). - If a match is found: - Use ‘UPDATE‘ with the existing ID. - Only include fields that are newly visible or changed. - Do not use ‘ADD‘ for duplicates. 2. Field Visibility - Only include fields with values explicitly visible in the HTML DOM. - Do not guess or infer missing values. - Add exact values instead of simply checking if constraints is satisfied. - Do not include ‘"unknown"‘ or empty-string values for missing fields. - Omit any field that is not explicitly visible. 3. Constraint Checking 3.1 Basic Constraint Handling - For each item, evaluate which required constraints are satisfied. - If any are violated or missing: - Add ‘constraints_not_met‘ listing the missing/invalid fields (e.g., ‘lift range, tray type‘) - Set ‘status: uncertain‘ - Add a brief ‘comment‘ (e.g., "missing lift range") 3.2 Add Only When Most Constraints Are Met - Only use ‘ADD‘ if the item satisfies most required constraints (at least 60%). - If fewer than half are satisfied: - Do not add the item. - If it already exists, consider using ‘UPDATE‘ or ‘DELETE‘. 4. When to Use ‘UPDATE‘ Only use ‘UPDATE‘ when at least one of the following is true: - A previously missing field has now been found (and was not already present) - The item now meets all required constraints and can be marked ‘status: complete‘ Do not update items: - If nothing has changed - If the values are already present and correct - If the item is already marked ‘deleted‘ 5. Deletion - Use ‘DELETE‘ only if the item is clearly invalid — for example: - It is irrelevant - It is severely incomplete (missing most required fields) - It does not satisfy constraints and is not fixable - Never issue ‘UPDATE‘ for an item that has already been deleted. 6. ID Assignment - When using ‘ADD‘, assign a unique ID not already present in the table (e.g., ‘S102‘, ‘CH014‘). 7. Item Validity - The ‘item‘ name must match a known type defined under ITEMS AND CONSTRAINTS. - Skip any item with an invalid or unrecognized type. RESPONSE FORMAT - Return only valid ‘ADD‘, ‘UPDATE‘, or ‘DELETE‘ actions — one per line. - Do not return the HTML DOM or candidate table. - Do not include explanation or commentary. - If no action is needed, return an empty string. Your response must strictly follow the following format. Use one or more of the following actions, one per line: ADD item:ID:UniqueID; key1:value1; key2:value2; … UPDATE item:ExistingID key1:value1; key2:value2; … DELETE item [ExistingID] Note: item must match exactly to the items in item-level constraints. While adding new items, always include the name or the title of the item. EXAMPLES ADD standing desk:ID:S102; Title:ErgoRise Desk; Price:$299.99; surface finish:Matte; status:uncertain; comment:"missing tray type and lift range" UPDATE standing desk:S101 lift range:"24-̈48"̈; status:complete; comment:"lift range confirmed" DELETE standing desk [S099] TASK DESCRIPTION {task_description} ITEMS AND CONSTRAINTS {items_and_constraints} CURRENT CANDIDATE TABLES {current_table} WEB PAGE CONTENT {current_observation}

Appendix

Table 23: Prompt for extracting candidate items to add to structured memory

You are a web-browsing assistant. Given a user query, extract a list of items to retrieve and, for each item, list all relevant item-specific constraints such as brand, price, rating, features, delivery time, etc. Include any other item attributes explicitly or implicitly mentioned in the query that affect the desirability, quality, or functionality of the item (e.g., surface finish, memory presets, power type, compatibility). Treat these as additional constraints. Include all intrinsic item-specific constraints, even if mentioned implicitly or as part of comparison criteria (e.g., “differ in brand or surface finish” implies that brand and surface finish are relevant constraints). Treat such attributes as constraints to be listed. Ignore any source-specific constraints (e.g., “from [a specific website]”) and general task-level instructions (e.g., “compare prices”, “top three results”). Only include intrinsic item-specific constraints. Only include items to retrieve—ignore any actions to perform. Ensure each item listed is unique. If there are no items to retrieve, return an empty list. Output your response strictly in the following JSON format: "ITEMS": [ "item": "<description of item>", "constraints": ["<constraint1>", "<constraint2>", "…"] , … ] Do not include any additional explanation. Always follow this format exactly. TASK DESCRIPTION {task_description} ITEMS AND CONSTRAINTS {items_and_constraints} CURRENT CANDIDATE TABLES {current_table} WEB PAGE CONTENT {current_observation}

Appendix

Table 24: Prompt for extracting item-level constraints and attributes from task description.

You are a validation assistant for a candidate item table. Your task is to verify whether each item satisfies the required constraints for its item type. If any constraint is violated or missing, issue an ‘UPDATE‘ or ‘DELETE‘ command to adjust the table accordingly. INSTRUCTIONS 1. For each item: - Issue an ‘UPDATE‘ only if all of the following are true: - The item is not marked as deleted - One or more constraints are violated or missing - The current values of ‘constraints_not_met‘, ‘status‘, or ‘comment‘ are incorrect, incomplete, or missing - Use the following format: “‘ UPDATE item:ID constraints_not_met: <key1> <key2> …, status: uncertain or complete; comment: "brief explanation" “‘ - You are only allowed to update the following fields: - ‘constraints_not_met‘ - ‘status‘ - ‘comment‘ - Do not issue duplicate updates. Skip updates if no changes are needed. - Issue a ‘DELETE‘ only if: - The item is marked as complete but fails to meet any constraint - Or the item is mostly complete but violates most required constraints - Use this format: “‘ DELETE item [ID] “‘ - Do not delete items that are mostly incomplete or missing most of the required fields. These should be updated instead. 2. Item Validity - The ‘item‘ in every ‘UPDATE‘ or ‘DELETE‘ command must exactly match a valid item type defined under ‘ITEMS AND CONSTRAINTS‘. - Skip any action for items with invalid or unrecognized types. 3. If the item satisfies all constraints and is already marked ‘status: complete‘, or if the item is incomplete but does not require any changes, return nothing. RESPONSE FORMAT - Return only ‘UPDATE‘ and ‘DELETE‘ commands, one per line. - Do not return the full item rows or any explanation. - If no action is needed, return an empty string. - Use one or more of the following actions, one per line. - Note: item must match exactly to the items in item-level constraints. Your response must strictly follow the following format. Use one or more of the following actions, one per line: UPDATE item:ExistingID key1:value1; key2:value2; … DELETE item [ExistingID] EXAMPLES UPDATE standing desk:SD002 constraints_not_met: <lift range> <tray type>; status: uncertain; comment: "Missing lift range and tray type" DELETE standing desk [SD010] TASK DESCRIPTION {task_description} ITEMS AND CONSTRAINTS {items_and_constraints} CANDIDATE TABLE: {current_table}

Appendix

Table 25: Prompt for updating structured memory

You are an And/Or Tree Repairer Agent specialized in web-browsing tasks. Your job is to repair a node in an And/Or planning tree derived from HTML DOM structure observations. Node definitions: Node Types <AND/ OR / Atomic> - node: Represents an ordered list of logical sub-goals required to achieve the node’s objective. - Or node: Represents alternative sub-strategies (which can be other And/Or nodes) - Atomic Action: Single executable action strictly matching navigation_specifications described below. Node status indicators: - Unvisited nodes marked UNVISITED - Pruned nodes marked PRUNED - Completed nodes marked SUCCESS - Temporarily failed nodes marked FAIL NAVIGATION_SPECIFICATIONS: <LIST OF BROWSER ACTIONS> You are provided: - root-level task description - task constraints at item level - HTML DOM structure as the observation - node_id and desription of the node to analyze - A list of its children: each with an ID, description, and status (SUCCESS, VISITED, UNVISITED, or PRUNED) - A success Or node with id and description, if present - Task progress summary of the task - Notes summary of the task : Notes taken by the agent so far Your task: Your task is to review all the information provided including reasoning for repair (if available) and use it to repair the node. Make sure you prune infeasible sub-goals (which have not been marked successful or pruned) and add sub-goals that are necessary for completing the node’s objective: Repair the node by pruning or adding children to the node: Remove old infeasible children and add new children that were not previously used. VERY IMPORTANT: -Assess node repairability using node type, child status, and remaining unmet goals. -Add only new, untried children , not already present or marked SUCCESS or PRUNED. These children will be appended to existing children. -Each child must be minimal, concrete, and justified by the current DOM. -For Or nodes: Suggest only new, obvious alternatives from the DOM. -For nodes: Suggest only missing or incomplete sub-goals in correct order. -Do NOT PRUNE children that are necessary for satisfying the parent node’s objective. First reason about the repair and then give the final answer in the following format (Enclose all values in <<>> on a single line, colon (;) separated. Ordering: Prune first, then add children): PRUNE [node_id of child] ADD [repair_node_id] repair_node_type : <<1. First added sub-goal; 2. Second added sub-goal; 3. Additional added sub-goals as necessary>> OR ADD [node_id] node_type : <<1. Added alternative strategy 1 (score: 0.x); 2. Added alternative strategy 2 (score: 0.y); Added additional alternatives as necessary>> Reasoning <<Reason for the nodes pruned and added.>> Example 1: PRUNE [1246] PRUNE [1245] ADD [1244] AND : <<1. Go north for 5 meters; 2. Turn left at the intersection; 3. Walk for 10 minutes>>> OR ADD [1244] OR : <<1. Open the door (score: 0.9); 2. Pick up the key (score: 0.8)>> Do not re-add processed or pruned children. Note that you can only prune children of the node to repair and add children to the node to repair. Added children will be appended to existing successful children. Respond using only the above. No extra text. Valid node_types are AND/OR/Atomic . ROOT-LEVEL TASK DESCRIPTION: {task_description} {additional_context} OBSERVATION: {observation} NODE ID : Description {node_id} {node_type} : {node_description} NODE_CHILDREN_REPRESENTATION: children REASON FOR REPAIR reason_for_repair LOCAL TREE INFORMATION: {local_tree_info}

Appendix

Table 26: Prompt for node repair

Figure 11: Illustration of node state transitions during iterative modified greedy depth-first search on AND-OR tree. Unlike traditional depth-first search, nodes may be revisited and repeatedly transition through Entering , Exiting , and Failed states.

Figure 12: Example of Structured Memory used to track candidate solutions during information-seeking tasks.

Representation	Description
Interaction History	Logs all observation summaries and actions up to the current time step
Task Progress Summary	Tracks progress toward the main objective
Notes Summary	Aggregates information from all past observations that are relevant to the task
Task Constraints	Encodes global and item-level requirements from the task description
Observation Summary	Distills salient information from the current web page at each step
Action History	Lists all executed browser actions

Appendix

Table 27: Internal Representations Maintained by StructuredAgent

Figure 13: Human Decomposition Intervention in AND/OR Tree Planning to Correct Bad Subtask Decomposition. The diagram illustrates how a human decomposition intervention can redirect an AI agent that has produced an incorrect sub-goal breakdown for a multi-step task. The task requires finding the driving route between the home cities of the 1980 and 1991 Super Bowl champions. Without intervention (bottom), the agent incorrectly assumes destinations a priori, defaulting to Pittsburgh, PA and Washington, DC, without first verifying which teams won in those respective years, resulting in a hallucinated but confidently stated incorrect answer. With intervention (top), a human intercepts the agent’s flawed decomposition and injects three corrective sub-goals into the AND/OR tree: (1) identify the 1980 Super Bowl champions and their home city, (2) identify the 1991 Super Bowl champions and their home city, and (3) return to the mapping tool with the verified locations. This human-guided correction grounds the plan in factual information before execution continues, yielding the correct route from Pittsburgh, PA (Pittsburgh Steelers) to East Rutherford, NJ (New York Giants) at 599 km and approximately 7 hours 23 minutes. For simplicity, we illustrate the human intervention at the first level of the AND/OR planning tree; however, such human decomposition interventions can be applied at any level of the tree, allowing a human operator to catch and correct errors in sub-goal formulation at whatever level of abstraction they arise.

Status	Description
UNVISITED	Initial state of all nodes before processing begins.
VISITED	Node has been processed but final outcome is not yet determined.
SUCCESS	Node’s objective is achieved. For nodes, all children succeed and collectively satisfy the objective; for Or nodes, any single child’s success suffices; for Action nodes, the corresponding browser operation succeeds.
FAIL	Node’s objective cannot be achieved. For nodes, occurs if any child fails or is pruned; for Or nodes, if the selected child fails; for Action nodes, if the operation is invalid or unsuccessful.
PRUNED	Node becomes irrelevant or irresolvable due to new information discovered during execution.
DELETED	Node is marked as inapplicable due to failure or pruning of a predecessor sibling in an node with ordering constraints.

Appendix

Table 28: Node Status Definitions in StructuredAgent Framework

Function Name	Description
PERFORM_ROLLBACK(node)	Performs context rollback to restore the browser state to the URL of the given node. Returns success status. Used when processing OR node children to ensure clean state.
POPULATE_NODE_TYPE(node)	Expands an UNKNOWN node by determining its type (ACTION, AND, OR) and populating relevant fields like children or action details. Returns updated node, status, and action.
BACKTRACK_FAILURE(node)	Handles backtracking when a node fails. For ordered AND nodes, deletes remaining siblings and their descendants. Propagates failure up the tree.
PERFORM_ACTION(node)	Executes the action specified in the node (e.g., click, type, navigate). Interacts with the environment to perform the web automation task. Returns action and execution status.
UPDATE_NOTES(action)	Extracts and updates notes from the action if any are present. Notes are used to record information during execution.
IS_NOTE_ACTION(action)	Checks if an action is a "note" action. Note actions don’t change observations, so they don’t require a full tree update.

Appendix

Table 29: Internal Functions Reference

Collection	Description
CLOSED_STATUSES	Node statuses that indicate the node is no longer active or executable: [SUCCESS, PRUNED, DELETED]
FAILED_STATUSES	Node statuses that imply failure or deleted: [PRUNED, DELETED]
FAILED_OR_PRUNED	Node statuses that indicate failure or pruned: [FAIL, PRUNED]
VISITED_TYPES	Node statuses that indicate a node has been visited or processed in some way: [FAIL, VISITED, PRUNED, SUCCESS]
VALID_NODE_TYPES	All valid/expected node types (excluding UNKNOWN): [AND, OR, ACTION]
NON_LEAF_NODES	Node types that represent composite (non-leaf) logic structures: [AND, OR]

Appendix

Table 30: Node Status and Type Collections

Attribute	Type	Description
type	NodeType	The type of the node (e.g., AND, OR, ACTION)
description	str	A human-readable description of the node
id	str	A unique identifier for the node
steps	int	Number of steps or operations this node represents (default: 0)
children	List[Node]	A list of child nodes (default: empty list)
parent	Optional[Node]	A reference to the parent node, if any

Appendix

Table 31: And/Or Tree Node Attributes

Figure 14: AgentOccam vs StructuredAgent on a Pinterest task: AgentOccam terminates its search prematurely when it fails to explore the third trend. On the other hand, StructuredAgent is able to successfully retrieve items for all three trending women’s ethnic wear styles.

- [0] (AND) Research Pinterest to identify the top 3 women’s ethnic wear trends for Diwali. For each trend: 1) Specify the signature color currently trending. 2) Find one matching footwear style and one purse, both in the same color (same color as the trend) from the Pinterest Shop. 3) Provide the name of a potential brand or seller for each footwear and purse, and include a direct source or pin link if possible. Focus on vibrant, festive, and popular looks. Do not end your search early. Limit your review to only the first 2 scrolls of results. Do not click on external links. [success] - [0.1] (Atomic) Search for Diwali ethnic wear trends on Pinterest (type [401] [Diwali ethnic wear trends 2024] [1]) [success] - [0.2] (Atomic) Document 3 trending ethnic wear styles with their signature elements (note [Trending Diwali Ethnic Wear 2024: 1. Pink - Anupa Sari with embellished blouse from INDIASPOPUP.COM 2. Pista Green - Crush fabric sari with sequins embroidery border and yellow jacquard blouse from Etsy 3. Powder Peach - Stripe sari set with thread, pearl and sequin embroidery, featuring plunging neckline blouse from KYNAH]) [success] - [0.3] (AND) Navigate to Pinterest Shop and search for footwear in Pink, Pista Green, and Powder Peach shades from verified sellers specifically for Diwali looks [success] - [0.3.1] (Atomic) Navigate to Pinterest Shop section (click [208]) [success] - [0.3.2] (Atomic) type [401] [Pink ethnic juttis Diwali footwear] [1] (type [401] [Pink ethnic juttis Diwali footwear] [1]) [success] - [0.3.3] (Atomic) Return to previous page after completing pink footwear search (go_back) [success] - [0.3.4] (Atomic) type [401] [Pista Green ethnic juttis Diwali] [1] (type [401] [Pista Green ethnic juttis Diwali] [1]) [success] - [0.3.5] (Atomic) Return to previous page to continue accessory search (go_back) [success] - [0.3.6] (Atomic) type [401] [Powder Peach ethnic juttis Diwali] [1] (type [401] [Powder Peach ethnic juttis Diwali] [1]) [success] - [0.4] (OR) Search Pinterest Shop for matching ethnic clutches/purses in three colors by trying alternative search terms: 1) Search "Pink potli Diwali bag" or "Pink ethnic clutch" from verified sellers, 2) Search "Pista Green potli Diwali bag" or "Mint ethnic clutch" from verified sellers, 3) Search "Peach potli Diwali bag" or "Blush ethnic clutch" from verified sellers. Limit to first 2 scrolls of results. [success] - [0.4.1] (AND) Search for powder peach ethnic clutches in Shop section [success] - [0.4.1.1] (Atomic) Search for powder peach ethnic clutches in Shop section (type [401] [powder peach ethnic clutch Diwali] [1]) [success] - [0.4.1.2] (Atomic) Execute search query for powder peach ethnic clutches (type [401] [powder peach ethnic potli clutch bag Diwali] [1]) [success] - [0.4.1.4] (Atomic) note [Found matching powder peach potli bags from verified sellers: 1. 5 Elements Peach Brocade Pattern Potli Bag at Pernia’s Pop Up Shop 2. AMYRA Peach Poly Silk Pearl Embroidered Potli Bag 3. SWABHIMANN ACCESSORIES Peach Pure Silk Potli Bag] (note [Found matching powder peach potli bags from verified sellers: 1. 5 Elements Peach Brocade Pattern Potli Bag at Pernia’s Pop Up Shop 2. AMYRA Peach Poly Silk Pearl Embroidered Potli Bag 3. SWABHIMANN ACCESSORIES Peach Pure Silk Potli Bag]) [success] - [0.4.1.5] (Atomic) Modify search query to find matching powder peach potli bags (type [401] [powder peach potli bag Diwali] [1]) [success] - [0.4.1.6] (Atomic) click [208] to ensure Shop filter is active before searching for powder peach accessories (click [208] to ensure Shop filter is active before searching for powder peach accessories) [success] - [0.4.1.8] (Atomic) Modify search to find powder peach potli bags for Diwali (type [401] [powder peach potli bag Diwali] [1]) [success] - [0.5] (Atomic) Document powder peach accessory pairs with seller details (note [Powder Peach - Footwear: Coral Haze Juttis, Jutti Express formal wear, 5 Elements ethnic shoes; Purse: 5 Elements Brocade Potli with tassels, AMYRA Poly silk Pearl Embroidered Potli, Ri Ritu Kumar Net and Silk Zari Potli]) [success] - [0.6] (AND) Document pink and pista green accessory pairs with seller details and pin links, ensuring color coordination and authenticity of sellers [success] - [0.6.1] (AND) Search and document pink ethnic footwear with seller details [success] - [0.6.1.1] (Atomic) Search for pink ethnic footwear for Diwali (type [401] [pink ethnic juttis Diwali] [1]) [success] - [0.6.1.2] (Atomic) note [Found matching pink footwear options: 1. B Anu Designs - Baby Pink Punjabi Jutti with Mirror and Bead handwork 2. Miar Designs - Pink Leather Embroidered Juttis at Pernia’s Pop Up Shop 3. YASSIO - Pink Silk Floral Embroidered Juttis] (note [Found matching pink footwear options: 1. B Anu Designs - Baby Pink Punjabi Jutti with Mirror and Bead handwork 2. Miar Designs - Pink Leather Embroidered Juttis at Pernia’s Pop Up Shop 3. YASSIO - Pink Silk Floral Embroidered Juttis]) [success] - [0.6.1.3] (Atomic) Return to previous page to continue accessory search (go_back) [success] - [0.6.2] (Atomic) Document matching pink potli/clutch from search results (note [Found matching pink brocade potli bag from 5 Elements with tassels and beads embellishments, suitable for festive wear]) [success] - [0.6.3] (Atomic) Return to previous page after powder peach potli search (go_back) [success] - [0.6.4] (Atomic) Search for pista green ethnic footwear using specific search terms (type [401] [Pista green embroidered juttis Diwali] [1]) [success] - [0.6.5] (Atomic) Search for matching pista green clutch/potli (type [401] [Pista green brocade potli Diwali] [1]) [success] - [0.6.6] (Atomic) Document complete accessory details with seller information for pista green trend accessories: Footwear - House of Vian’s Crepe Embroidered Juttis and 5 Elements’ Leatherette Embellished Juttis; Purse - 5 Elements Green Brocade Embroidered Potli with tassels and dupion lining, and Tarini Nirula Green Brocade Stone Embellished Potli with antique gold frame (Document complete accessory details with seller information for pista green trend accessories: Footwear - House of Vian’s Crepe Embroidered Juttis and 5 Elements’ Leatherette Embellished Juttis; Purse - 5 Elements Green Brocade Embroidered Potli with tassels and dupion lining, and Tarini Nirula Green Brocade Stone Embellished Potli with antique gold frame) [success] - [0.6.7] (Atomic) Search for powder peach ethnic footwear (type [401] [powder peach ethnic juttis Diwali] [1]) [success] - [0.6.10] (AND) Search for pink ethnic footwear pins from verified sellers and save direct links [success] - [0.6.10.1] (Atomic) View details of pink leather embroidered juttis for Pink category (click [17999]) [success] - [0.6.10.2] (Atomic) note [Pink leather juttis by Miar Designs - Features: Leather base with coin, thread, pearl, sequins and beads embroidery, Available at Pernia’s Pop Up Shop, Price: 40,00, Formal occasion wear] (note [Pink leather juttis by Miar Designs - Features: Leather base with coin, thread, pearl, sequins and beads embroidery, Available at Pernia’s Pop Up Shop, Price: 40,00, Formal occasion wear]) [success] - [0.6.10.3] (Atomic) Return to previous page to continue purse search (go_back) [success] - [0.6.11] (Atomic) Search for matching pink potli/clutch pins (type [401] [pink ethnic potli clutch Diwali] [1]) [success] - [0.6.14] (Atomic) Verify and document color coordination between footwear-purse pairs (note [Color coordination verified: Pink category - Pink Beaded Mirror Work Potli and Pink Brocade Potli perfectly match the pink leather juttis from Miar Designs in shade and festive style]) [success] - [0.7] (Atomic) Document direct pin links for pink accessories from verified sellers (note [Found verified seller pin links: 1. Pink Brocade Tassels Embellished Potli by 5 Elements - Direct Pin ID 20730 2. Pink Brocade Ghungroo Embroidered Potli by 5 Elements - Direct Pin ID 20752 3. Pink Beaded Mirror Work Potli by Etsy verified seller - Direct Pin ID 21242]) [success] - [0.8] (AND) Review and document direct pin links for all three color categories ensuring each has verified footwear and purse pairs with seller details [success] - [0.8.1] (Atomic) Document completed findings for Pink category (note [Pink Category Complete - Footwear: Miar Designs, Purses: Pink Beaded Mirror Work Potli (Etsy), Pink Brocade Potli (5 Elements)]) [success] - [0.8.2] (Atomic) Navigate to Pinterest Shop section for ethnic potli clutches (click [20411]) [success] - [0.8.7] (Atomic) Search for powder peach potli options (type [401] [powder peach ethnic potli clutch Diwali] [1]) [success] - [0.8.8] (Atomic) Search for matching Pista Green potli options with verified sellers and clear product details (type [401] [pista green ethnic potli clutch Diwali] [1]) (Search for matching Pista Green potli options with verified sellers and clear product details (type [401] [pista green ethnic potli clutch Diwali] [1])) [success] - [0.8.9] (Atomic) Document verified seller information for Pista Green potlis (note [Verified Pista Green Potlis: 1. PLODE - Green Velvet Swarovski Triangle Potli with crystal embellishments and rhinestone strap 2. Velleso - Green Mirror Work Potli with crystal drops and silver threadwork (24x23cm) 3. The Pink Potli - Green Raw Silk Potli with bead work and tassel embellishments]) [success] - [0.8.10] (Atomic) Search for matching Powder Peach ethnic footwear options (type [401] [powder peach ethnic footwear Diwali] [1]) [success] - [0.8.11] (Atomic) Search for matching Pista Green ethnic footwear options with verified sellers and clear product details (type [401] [pista green ethnic footwear Diwali] [1]) [success] - [0.8.12] (Atomic) Document pin links and details for Pista Green category footwear and purse pairs (note [Found direct pin links for Pista Green category: 1) House of Vian Green Crepe Embroidered Juttis with crystals and gota patti from Pernia’s Pop Up Shop 2025, 2) 5 Elements Green Leatherette Embellished Juttis with beadwork from Pernia’s Pop Up Shop 2025]) [success]

Appendix

Table 32: Planning tree for the task “Research Pinterest to identify the top 3 women’s ethnic wear trends for Diwali. For each trend: 1) Specify the signature color currently trending. 2) Find one matching footwear style and one purse, both in the same color (same color as the trend) from the Pinterest Shop. 3) Provide the name of a potential brand or seller for each footwear and purse, and include a direct source or pin link if possible. Focus on vibrant, festive, and popular looks. Do not end your search early. Limit your review to only the first 2 scrolls of results. Do not click on external links.”

Step	StructuredAgent	AgentOccam
1	search “Diwali ethnic wear trends 2024”	search “Diwali ethnic wear trends 2024”
2	click search bar	click first result
3	search “light pink ethnic purse palazzo style”	click search bar
4	click product result	[note] Top 3 trends: (1) Palazzo suits – Light Pink, (2) Stripe sari sets – Powder Peach, (3) Dhoti-style with peplum tops
5	go_back	search “light pink purse ethnic”
6	search “light pink traditional juttis wedding”	click product result

Appendix

Table 33: Trajectory and final response comparison on task Diwali-05 : “Research Pinterest to identify the top 3 women’s ethnic wear trends for Diwali. For each trend: 1) Specify the signature color currently trending. 2) Find one matching footwear style and one purse, both in the same color (same color as the trend) from the Pinterest Shop. 3) Provide the name of a potential brand or seller for each footwear and purse, and include a direct source or pin link if possible. Focus on vibrant, festive, and popular looks. Do not end your search early. Limit your review to only the first 2 scrolls of results. Do not click on external links.” Both agents use claude-3-5-sonnet-20241022 .

LLM Agent Planning

Large language model (LLM) agent planning studies how agents decompose goals, choose actions and tools, and adapt plans from feedback.

See all 216 papers

May 28, 2026

Does The Way You Plan Matter? An Empirical Study of Planning Representations for LLM Web Agents

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

LLM Agent Evaluation LLM Agent Planning Web Agents

Ask PDF

Mar 15, 2026

Why Do LLM-based Web Agents Fail? A Hierarchical Planning Perspective

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

Web Agents LLM Agent Reliability Long-Horizon LLM Agents LLM Agent Planning LLM Agent Evaluation

Ask PDF

Mar 13, 2026

AI Planning Framework for LLM-Based Web Agents

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

LLM Agent Planning Web Agents LLM Agent Evaluation Web Agent Benchmarks

Ask PDF

Abstract

LLM Agent Planning

Explore similar work

Does The Way You Plan Matter? An Empirical Study of Planning Representations for LLM Web Agents

Why Do LLM-based Web Agents Fail? A Hierarchical Planning Perspective

AI Planning Framework for LLM-Based Web Agents