Technical Summary: An Empirical Study of Planning Representations for LLM Web Agents

Problem Statement

Despite recent advances in Large Language Models (LLMs), web agents continue to struggle with limited exploration, the omission of critical steps, and sensitivity to task constraints. While planning is widely recognized as a key strategy for decomposing complex tasks, existing research has largely focused on planning algorithms rather than the representation of those plans. Most current approaches rely on sequential lists of subgoals expressed in natural language. However, the impact of alternative natural language (NL) plan representations on agent robustness and task success remains largely unexplored. Furthermore, existing benchmarks often lack reproducible difficulty grading, making it difficult to systematically evaluate planning strategies under varying levels of complexity.

Methodology

Framework: PLANAHEAD

The authors introduce PLANAHEAD, a static planner-executor framework designed to isolate and evaluate the impact of plan representation. Unlike dynamic planning methods where the agent regenerates plans at every step, PLANAHEAD generates a single static plan at the beginning of a task. This plan is then provided to an executor LLM, which performs low-level actions based on the current browser state. This setup ensures that performance differences arise from the plan formulation and the underlying models rather than action-level stochasticity or dynamic re-planning overhead.

Benchmark and Task Difficulty

The study utilizes WebArena, a closed and reproducible environment containing diverse, realistic web interactions. To address the lack of standardized difficulty grading, the authors developed an automated pipeline to categorize 381 WebArena tasks into three levels: Easy, Medium, and Hard.

• Categorization Logic: Tasks were evaluated using a lightweight GenericAgent across five different LLM backbones with five independent trials each.
  • Easy: 100% success rate across all models and trials.
  • Hard: 0% success rate across all models and trials.
  • Medium: Intermediate success rates.
    The study focuses specifically on the Hard subset (158 tasks), as these provide the most informative setting for evaluating planning capabilities under challenging conditions.

Experimental Setup

The authors evaluated four distinct plan representations on the Hard tasks across different multimodal LLM families (OpenAI, Alibaba, and Google):

1. Sequential Subgoals: The standard approach using an ordered list of high-level subgoals.
2. Requirement Checklist: An unordered list of requirements that must be met, leaving the execution order to the executor.
3. Pseudocode: A structured format using intuitive functions, conditionals, and loops to capture contingencies.
4. Narrative: A verbose, natural-language description of the task completion process.

The experiments tested various planner-executor combinations, including homogeneous setups (same model for both roles) and heterogeneous setups (different models for planning and execution).

Evaluation Metrics

Recognizing that standard Success Rate (SR) treats every trial as independent and fails to capture the stochastic nature of LLMs, the authors introduced two novel metrics:

• Achievement Rate (AR): Measures task-level achievability across multiple runs. A task is considered "achieved" if at least one of the $N$ runs succeeds. This distinguishes between tasks that are "rarely solvable" and those that are "completely unsolved."
• Solved-Task Consistency (STC): A robustness metric that measures the reliability of performance across trials for tasks that were achieved at least once.

Key Contributions

1. Automated Task Difficulty Grading: The paper presents a reproducible pipeline for partitioning benchmark tasks into difficulty levels without human annotation, enabling systematic evaluation of planning strategies.
2. Evaluation of Novel Planning Representations: The study proposes and evaluates three alternative NL-based planning formats (Narrative, Pseudocode, Checklist) against the standard Sequential Subgoals.
3. Novel Evaluation Metrics: The introduction of AR and STC provides a more nuanced view of agent performance, capturing both achievability and consistency in stochastic environments.

Results and Analysis

The empirical study yielded several significant findings:

• Plan Representation Matters: The effectiveness of a planning strategy is highly dependent on the underlying LLM.
  • GPT-4.1-mini consistently performed best with Narrative plans, suggesting that models trained extensively on natural language text leverage coherent descriptive instructions effectively.
  • Qwen-2.5-VL performed best with Checklist representations, benefiting from explicit and structured guidance.
  • Gemini models showed competitive performance across multiple formats and notably benefited from non-standard formats; specifically, Pseudocode yielded high Achievement Rates when Gemini acted as both planner and executor.
• Planner-Executor Separation: Mixed planner-executor pairs generally outperformed homogeneous setups. For instance, combining GPT-4.1-mini as the planner with Gemini as the executor achieved the strongest overall performance. This suggests that different models possess complementary strengths: some are superior at high-level structural planning, while others excel at low-level action execution.
• Static vs. Dynamic Planning: Contrary to the intuition that dynamic re-planning is superior, Static Planning often outperformed dynamic single-agent planning. Qualitative analysis revealed that dynamic agents frequently entered action loops, lost track of task progress, or prematurely marked subtasks as completed. The static planner-executor setup allowed the executor to focus exclusively on action selection without the cognitive load of continuous re-planning.

Significance and Claims

The paper claims that the formulation of a plan and the specific LLM generating it significantly influence web-agent robustness and task success. By challenging the assumption that plans must take the form of sequential subgoals, the authors demonstrate that non-standard formats can be beneficial, particularly for difficult tasks.

The study emphasizes that planning effectiveness is not solely a function of model capability but is also deeply tied to the representational form of the plan. The results support the adoption of modular agent architectures that exploit complementary model strengths (e.g., using one model for planning and another for execution) and suggest that static planning can be a more robust and efficient alternative to dynamic planning in certain contexts.

The authors remain modest regarding their scope, acknowledging limitations such as the restricted set of LLM backends, the use of a single benchmark (WebArena), and a limited number of runs ($N=5$). They posit that expanding these variables would provide a more comprehensive picture of planning effectiveness.