Skip to content

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

🕒 Published (v1): 2026-05-28 13:39 UTC · Source: Arxiv · Venue: EMNLP · link

Why this paper was selected

Empirical study of planning representation formats for LLM web agents

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

PLANA HEAD is a static planner-executor framework that empirically compares four natural-language plan representations—sequential subgoals, narrative, pseudocode, and checklist—for LLM-based web agents on WebArena's hardest tasks. The study shows that both the plan format and the choice of executor LLM significantly affect task success and robustness, with no single representation dominating across all model families. Mixed planner-executor pairings (e.g., GPT-4.1-mini planner + Gemini executor) outperform homogeneous setups.

Problem

Prior LLM web agent research overwhelmingly encodes plans as sequential subgoal lists, leaving unexplored whether alternative natural-language representations (narrative prose, pseudocode, checklists) yield better performance. Existing evaluation also relies on binary Success Rate (SR), which conflates stochastic per-run failures with genuinely unsolvable tasks and cannot measure robustness across runs.

Method

PLANA HEAD uses a static planner-executor separation: a planner LLM generates a one-shot plan from the task goal and an initial browser screenshot (temperature 0.6); an executor LLM consumes that plan plus the live browser state at each step to select low-level actions (temperature 0, max 30 steps). Four plan formats are tested: (S) sequential subgoals, (C) requirement checklist (unordered), (P) pseudocode with conditionals/loops, (N) narrative prose. Evaluation is conducted on 158 "Hard" WebArena tasks—tasks where five backbone models each fail across all five independent trials—identified via an automated difficulty-grading pipeline using BrowserGym's GenericAgent. Two new metrics are introduced: - Achievement Rate (AR): \(\mathrm{AR} = \frac{1}{T}\sum_{t=1}^{T}\bigvee_{i=1}^{N}\mathrm{Reward}(t,i) \times 100\) — task is "achieved" if it succeeds in at least one of \(N\) runs. - Solved-Task Consistency (STC): \(\mathrm{STC} = \frac{1}{|A| \cdot N}\sum_{t \in A}\sum_{i=1}^{N}\mathrm{Reward}(t,i) \times 100\) — among achieved tasks, the fraction of runs that succeed.

Backbone models: GPT-4.1-mini, Qwen-2.5-VL-72B, Gemini 2.5 Flash, evaluated in all nine planner-executor pairings (including same-model). A dynamic single-agent baseline (GenericAgent UsePlan, which re-plans at each step) is included for comparison.

Key Contributions

  • Automated task difficulty grading pipeline that partitions WebArena's 381 test tasks into Easy (14), Medium (209), and Hard (158) without human annotation.
  • Empirical evaluation of three novel NL plan representations (narrative, pseudocode, checklist) against the standard sequential subgoal baseline across nine planner-executor configurations.
  • Two new evaluation metrics—AR and STC—that disentangle achievability from per-run consistency in stochastic multi-run settings.
  • Finding that mixed planner-executor pairings consistently outperform homogeneous same-model setups.
  • Evidence that static planning can outperform dynamic per-step re-planning on hard tasks.

Results

  • Best overall AR: GPT-4.1-mini (planner) + Gemini 2.5 Flash (executor) with sequential subgoals, AR = 10.7%, STC = 47%.
  • GPT-4.1-mini as executor benefits most from narrative plans (AR 5.1%, STC 75 in homogeneous config); Qwen-2.5-VL-72B performs best with checklist (AR 7.5%, STC 30 in Qwen–Qwen); Gemini 2.5 Flash benefits from pseudocode (AR 8.2%, STC 43 in Gemini–Gemini), the highest AR in a homogeneous setup.
  • Dynamic planning baseline underperforms static planning in matching configurations (e.g., GPT-4.1-mini dynamic SR ≈ 2.0% vs. static sequential SR ≈ 2.6% for same executor; Gemini dynamic AR = 9.5% but only tested in sequential).
  • Bootstrap 95% CIs confirm AR improvements above zero for best strategies, ruling out stochastic noise.
  • Hard set sensitivity: 84% of Hard tasks remain Hard under \(N=1\) runs; overlap grows to 100% at \(N=5\).

Limitations

  • Only three LLM families evaluated (GPT-4.1-mini, Qwen-2.5-VL-72B, Gemini 2.5 Flash); conclusions may not generalize to other models.
  • Single benchmark (WebArena); no cross-benchmark validation.
  • Only \(N=5\) runs per task; larger trial counts would narrow confidence intervals.
  • Static plans are never updated during execution; the study does not explore hybrid reactive strategies.
  • Hard set restricted to tasks all five models fail in all five trials, which may be idiosyncratically difficult rather than representative of general hard web tasks.

Relevance to Agentic AI / LLM Agents

This work directly addresses the under-studied question of how plans should be communicated in planner-executor agent architectures—a design choice that practitioners typically fix by convention (sequential subgoals) without empirical justification. The finding that the optimal plan representation is model-family-dependent has immediate practical implications for multi-LLM agent pipelines, suggesting that representation should be treated as a hyperparameter matched to the executor's pretraining distribution. The new AR/STC metrics provide a more principled evaluation protocol for any stochastic agentic system, and the empirical result that static planning beats dynamic re-planning on hard tasks challenges the common assumption that more frequent replanning is always better.