[ICLR 2025] STRUCTUREDAGENT: Mastering Long-Horizon Web Tasks with AND/OR Tree Planning

TL;DR

STRUCTUREDAGENT introduces a hierarchical planning framework that replaces "greedy" LLM decision-making with a systematic AND/OR tree search. By decoupling high-level planning logic from local execution and adding a Structured Memory module, it achieves superior performance on complex, multi-constraint web tasks where traditional agents fail.

Background: The "Greedy" Agent Problem

Despite the power of models like Claude 3.5 and GPT-4o, current web agents often behave like short-sighted hikers: they take the most promising immediate step but get stuck when a path leads to a dead end. This is known as greedy behavior, often leading to premature termination of tasks.

The challenges are three-fold:

1. Context Fragmentation: Web pages are huge (>20k tokens), making it impossible to remember every alternative path in a flat history.
2. Weak Error Recovery: Simple backtracking is inefficient without a sense of "why" a path failed.
3. Compositional Complexity: Tasks like "Find a vegan recipe with 4+ stars and buy the ingredients" are naturally hierarchical, but agents treat them as linear sequences.

Methodology: The Power of AND/OR Trees

STRUCTUREDAGENT treats a web task as a search problem over a dynamically constructed AND/OR tree.

1. The Tree Structure

• AND Nodes (∧): Represent subgoals that must all succeed (e.g., "Find product" AND "Apply discount").
• OR Nodes (∨): Represent alternative strategies (e.g., "Search on Amazon" OR "Search on BestBuy").
• ACTION Nodes: Atomic browser operations (Click, Type, Scroll).

2. Modified Greedy DFS

The system uses a modified Depth-First Search that tracks three states: ENTERING, EXITING, and FAILED. This allows the agent to propagate failures upwards. If an action fails, the framework doesn't just "try again"; it triggers Node Repair or Pruning, forcing the LLM to find a different branch in the OR node.

Figure 1: The STRUCTUREDAGENT Framework overview, showing the interplay between the LLM controller and the Tree Planner.

3. Structured Memory

For "Information Seeking" tasks, the agent maintains a dynamic table of candidates. This prevents the agent from forgetting a valid product it saw 10 steps ago while it explores a different sub-segment of a website.

Experimental Performance

The authors tested the agent on WebArena, WebVoyager, and a new Amazon Hard benchmark.

Key Results:

• SOTA on WebArena: StructuredAgent achieved an overall success rate of 0.526, significantly higher than AgentOccam (0.464).
• Amazon Hard: On complex shopping tasks with multiple constraints, the agent showed a +14% improvement over competitive baselines.
• Efficiency vs. Success: Interestingly, STRUCTUREDAGENT often has longer trajectories (more steps). This isn't a sign of inefficiency, but rather a sign of robust exploration—the agent refuses to give up until it has exhausted all viable branches of its plan.

Table 1: Performance comparison across different LLM judges. STRUCTUREDAGENT (top row) consistently leads in the "Hard" categories.

Deep Insight: Why it Works

The "magic" isn't in making the LLM smarter, but in providing a structured scaffolding. By forcing the LLM to expand specific nodes ("Expand this AND node into subgoals"), the framework reduces the cognitive load on the model. It no longer has to track the global plan and the local action simultaneously—the tree handles the global, and the LLM handles the local.

Furthermore, the Human-in-the-Loop potential is huge. Because the tree is human-readable, a user can pause the agent, notice it has a bad "sub-goal" decomposition, and manually prune a branch before the agent wastes time (and tokens) executing it.

Conclusion & Future Work

STRUCTUREDAGENT proves that for long-horizon tasks, symbolic structure + LLM reasoning is superior to end-to-end LLM execution.

Limitations:

• The framework currently relies on a "greedy" selection of OR branches based on LLM scores, which could be improved with formal Admissible Heuristics.
• Token costs are higher due to the frequent tree updates and summarization calls.

Takeaway: As AI agents move toward handling hours-long workflows, explicit hierarchical management will likely become the standard architecture.