PaperlayerView exact revision on arXiv

Source-linked AI summary

Web-Shepherd: Advancing PRMs for Reinforcing Web Agents

Hyungjoo Chae, Sunghwan Kim, Junhee Cho, Seungone Kim, Seungjun Moon, Gyeom Hwangbo, Dongha Lim, Minjin Kim, Yeonjun Hwang, Minju Gwak, Dongwook Choi, Minseok Kang, Gwanhoon Im, ByeongUng Cho, Hyojun Kim, Jun Hee Han, Taeyoon Kwon, Minju Kim, Beong-woo Kwak, Dongjin Kang, Jinyoung Yeo

arXiv:2505.15277v2cs.CL

TL;DR

Long-horizon web navigation is challenging, and specialized reward models for the domain have been absent despite speed and cost constraints on MLLM evaluators. The paper introduces WEB-SHEPHERD, a checklist-guided process reward model, alongside a dataset and benchmark. It reports stronger benchmark accuracy than prompted GPT-4o-mini and improved, more cost-effective WebArena-lite tree-search performance than GPT-4o-mini evaluation.

  • Problem

    Long-horizon web navigation challenges MLLM agents, while specialized reward models for training and test-time use have been absent and prompted MLLM evaluation raises speed and cost constraints.

    Source: §1 · p. 2

  • Method

    The paper introduces WEB-SHEPHERD, a checklist-guided process reward model, and releases WEBPRM COLLECTION for training and WEBREWARDBENCH for PRM evaluation.

    Source: §1 · p. 2

  • Results

    85.0% on WebRewardBench (WebArena set) versus GPT-4o-mini prompting at 5.0%; with a GPT-4o-mini policy, tree search reaches 34.55% WebArena-lite success, 10.9 points better and 10× more cost-effective than GPT-4o-mini evaluation.

    Source: §1 · p. 2

  • Takeaways & Limitations

    WEBREWARDBENCH allows PRMs to be tested without resource-intensive web agents, and WEB-SHEPHERD provides step-level reward guidance for inference-time tree search.

    Source: §1 · p. 2

Abstract

from arXiv · show

Web navigation is a unique domain that can automate many repetitive real-life tasks and is challenging as it requires long-horizon sequential decision making beyond typical multimodal large language model (MLLM) tasks. Yet, specialized reward models for web navigation that can be utilized during both training and test-time have been absent until now. Despite the importance of speed and cost-effectiveness, prior works have utilized MLLMs as reward models, which poses significant constraints for real-world deployment. To address this, in this work, we propose the first process reward model (PRM) called Web-Shepherd which could assess web navigation trajectories in a step-level. To achieve this, we first construct the WebPRM Collection, a large-scale dataset with 40K step-level preference pairs and annotated checklists spanning diverse domains and difficulty levels. Next, we also introduce the WebRewardBench, the first meta-evaluation benchmark for evaluating PRMs. In our experiments, we observe that our Web-Shepherd achieves about 30 points better accuracy compared to using GPT-4o on WebRewardBench. Furthermore, when testing on WebArena-lite by using GPT-4o-mini as the policy and Web-Shepherd as the verifier, we achieve 10.9 points better performance, in 10 less cost compared to using GPT-4o-mini as the verifier. Our model, dataset, and code are publicly available at LINK.

1 Introduction

Web navigation agents struggle with long-horizon tasks, while prompted MLLM evaluators impose speed and cost constraints. The paper introduces a checklist-guided process reward model and resources for training and evaluating web-navigation PRMs.

1 Introduction

  • Long-horizon web navigation remains unreliable, while prompted MLLM evaluators constrain deployment through speed and cost.The paper cites an example of GPT-4o tree search on 812 WebArena queries costing approximately $14,000 and taking 40 hours on one A100.Source: §1 · p. 2
  • WEB-SHEPHERD is a process reward model that uses checklists of interpretable subgoals to assess step-level progress through agent trajectories.The paper motivates process-level decisions because web actions can have irreversible consequences, unlike selecting among alternative generated solutions.Source: §1 · p. 2
  • 85.0% on WebRewardBench (WebArena set) versus GPT-4o-mini prompting at 5.0%; tree search with GPT-4o-mini policy reaches 34.55% WebArena-lite success, 10.9 points better and 10× more cost-effective.The cost comparison is against GPT-4o-mini as the evaluator.Source: §1 · p. 2
  • WEBPRM COLLECTION supplies 40K step-level action annotations and checklists, while WEBREWARDBENCH enables PRM evaluation without resource-intensive web agents.The collection covers diverse tasks and difficulty levels.Source: §1 · p. 2

2 Related Work

Prior web-agent research explores MLLM agents, inference-time scaling, and reward models, but the reliability and efficiency of process-level MLLM rewards remain underexplored.

MLLM-based web agents

  • Prior MLLM web agents use tools [15] or workflows [4], or imitate expert trajectories [17] [18], but often generalize poorly to unseen environments.Recent work also explores inference-time scaling [7] [19] and reinforcement learning [20] to improve decision-making through reward feedback.Source: §2 · pp. 2–3

Inference-time scaling for web agents

  • Web-agent inference-time scaling includes tree search [23] [19], long chain-of-thought [24] [25], and prompted verifiers; Pan et al. use feedback-driven Reflexion retries.Source: §2 · p. 3

Rewards for web navigation

  • Web-navigation rewards range from binary rules and prompted LLMs [7] to ORMs [20]; PRMs offer step-level credit assignment, but MLLM reliability and efficiency remain underexplored.Source: §2 · p. 3

3 Preliminaries

The paper models web navigation as a partially observable Markov decision process, with agents acting on browser-rendered observations to maximize trajectory reward.

3 Preliminaries

  • Web navigation is formulated as a POMDP with environment states, agent actions, observations, transition function, and reward function.Source: §3 · p. 3
  • At each step, browser observations only partially reflect the underlying state and include an accessibility tree and a rendered screenshot.Source: §3 · p. 3
  • Agents choose discrete browser actions such as click, scroll, and type to maximize expected reward over a trajectory.Source: §3 · p. 3

4 WEBPRM COLLECTION

WEBPRM COLLECTION pairs instructions and observations with expert actions, rejected alternatives, and checklists. Its construction combines expert annotation, checklist abstraction, and difficulty-level statistics.

4 WEBPRM COLLECTION

  • The dataset pairs user instructions and observations with expert chosen actions, rejected actions, and a checklist.The expert actions form a trajectory; the collection is intended to provide training data for web-navigation PRMs.Source: §4 · p. 3

4.1 Collecting User Instruction and Expert Trajectory

  • Human experts supplied instructions and chosen trajectories on Mind2Web sites accessible through Playwright; annotators received three hours of training and 10 evaluators reviewed submissions.Review filtered invalid, unreproducible trajectories and vague instructions; instructions spanned easy, medium, and hard levels.Source: §4.1 · pp. 3–4

4.2 Annotating Checklist and Rejected Action

  • Checklists abstract equivalent actions into higher-level subgoals using GPT-4o; five policy-generated alternatives are filtered to retain up to five rejected actions per expert action.The abstraction is intended to reduce website bias and sensitivity to action ordering.Source: §4.2 · p. 4

4.3 Dataset Statistics

  • Trajectory medians rise from approximately 5 easy steps to 9 medium and 20 hard steps, with some hard tasks exceeding 40; checklist counts rise from 3–4 to 4–5.The trajectory lengths and checklist subgoals are compared across task difficulty levels.Source: Figure 4 · p. 4, §4.3 · pp. 4–5

5 WEB-SHEPHERD

WEB-SHEPHERD generates task-specific checklists of intermediate subgoals, then uses checklist completion to produce process rewards. Its reward model learns to generate feedback and judgments and converts checklist-item judgments into continuous scores.

5.1 Step 1: Checklist Generation

  • WEB-SHEPHERD first generates a natural-language checklist of intermediate milestones from the user instruction, which then guides reward prediction.The checklist comprises a sequence of subgoals used to track progress toward the goal.Source: §5.1 · p. 5, §5 · p. 5

5.2 Step 2: Reward Modeling with Checklist

  • The reward model is trained with a language-modeling loss to generate feedback and judgment tokens autoregressively from the checklist, observation, and answer.The targets concatenate feedback F and judgment J into one sequence.Source: §5.2 · p. 5
  • At inference, a verbalizer estimates soft probabilities over checklist labels; per-item reward weights “Yes” and “In Progress” at 0.5, then averages item scores.Sampling multiple output sequences is also described as an alternative scoring strategy.Source: §5.2 · pp. 5–6

6 Experiments

WEB-SHEPHERD outperforms prompted MLLM baselines on WEBREWARDBENCH, and reward-guided search improves policy performance on WebArena-lite and WorkArena. Checklist use improves reward assignment, while multimodal input does not consistently help.

6.1.1 Setup

  • Benchmark setup draws 707 Mind2Web demonstrations and 69 manually annotated WebArena instances, evaluates preferred-action ranking, and compares prompted MLLMs with LoRA-trained Qwen models.Reported metrics include MRR, step accuracy, and trajectory accuracy.Source: §6.1.1 · p. 6

6.1.2 Results

  • WEB-SHEPHERD significantly outperforms all baselines across WEBREWARDBENCH settings, where MLLMs often fail to assign rewards consistently across trajectory steps.The evaluation varies observation type and checklist use.Source: §6.1.2 · pp. 6–7, Table 1 · p. 7
  • Checklists improve trajectory reward accuracy across baselines, while ablations show substantial drops when checklists or feedback are removed.The findings support the importance of both checklist guidance and feedback for reliable reward assignment.Source: §6.1.2 · p. 7, Figure 6 · p. 7
  • Multimodal input does not consistently improve performance and can degrade it; GPT-4o shows a trajectory-accuracy gain only on Mind2Web cross-website tasks.The authors note that multiple modalities can introduce ambiguity and noise.Source: §6.1.2 · p. 7

6.2 Reward-Guided Trajectory Search

  • WebArena-lite and WorkArena tests use GPT-4o-mini as policy and execute the highest-reward action among five sampled candidates; WorkArena tests out-of-domain robustness.Success rate measures the share of tasks whose final state satisfies the task condition.Source: §6.2 · pp. 7–8
  • 23.64 to 34.55: WEB-SHEPHERD raises GPT-4o-mini policy browsing success on WebArena-lite, outperforming GPT-4o without trajectory search by about three points.It also improves both GPT-4o-mini and GPT-4o policies across nearly all domains.Source: Table 2 · p. 8, §6.2 · p. 8
  • 9.39 to 12.42: on out-of-domain WorkArena, WEB-SHEPHERD-guided search raises the Total score; it beats GPT-4o-mini across domains except Menu.The authors attribute Menu's lower performance to complex dropdowns and embedded search boxes that make policy action candidates unreliable.Source: Table 3 · p. 8, §6.2 · p. 8
  • Step-wise refinement using WEB-SHEPHERD feedback improves performance, unlike prior findings that such feedback may be unhelpful or detrimental.The authors suggest the model identifies patterns of suboptimal behavior as well as action impacts.Source: §6.2 · p. 8

7 Discussion

The discussion evaluates checklist quality, reward-model objectives, cost, and dataset scaling, and examines reward-score trends and common errors. Its analyses highlight the value of high-quality checklists and the importance of retaining data for out-of-domain generalization.

7 Discussion

  • Table 4 reports results for refinement with WEB-SHEPHERD feedback, using GPT-4o-mini as the policy on WebArena-lite.The supplied caption identifies the evaluation setting but does not provide result values.Source: Table 4 · p. 8

7.1 The Impact of Checklist Quality in Reward Prediction

  • High-quality checklists lead to more reliable reward assignments, though the model's capability imposes a ceiling regardless of checklist quality.WEB-SHEPHERD, trained solely for checklist generation, achieves the highest checklist-quality score; Figure 7 compares checklist quality and reward accuracy.Source: §7.1 · p. 9, Figure 7 · p. 9

7.2 Training Objective: Bradley-Terry Modeling vs. Generative Reward Modeling

  • The Bradley-Terry-trained WEB-SHEPHERD (3B) underperforms the paper's model, particularly on the out-of-distribution WebArena subset.The authors attribute this to BT loss's weaker use of checklists for reward assignment and reduced sensitivity to task progress.Source: §7.2 · p. 9, Figure 8 · p. 9

7.3 Cost Efficiency of WEB-SHEPHERD

  • WEB-SHEPHERD delivers the best performance at the lowest cost per 1,000 instances, roughly 10× cheaper than GPT-4o-mini and 100× cheaper than GPT-4o.Costs use an A100 80GB GPU instance rate and measured throughput for WEB-SHEPHERD, and publicly available API prices for the other models.Source: §7.3 · p. 9

7.4 Data Scaling Law for PRM Training

  • Reducing instructions or rejected actions to about half the original dataset sharply lowers ACC (traj), including WebArena drops from 60.0 to 15.0 and 60.0 to 20.0, respectively.The WebArena results indicate that reducing either data component significantly impairs generalization to an out-of-domain setting.Source: Table 5 · p. 9, §7.4 · p. 10

7.5 Case Study

  • Successful cases show steadily rising reward scores, while failure cases are relatively flat; frequent errors include misjudging action effects, misreading state, and hallucinating checklist features.The case study samples 30 successful and 30 failed cases and plots reward against normalized trajectory step index.Source: §7.5 · p. 10, Figure 9 · p. 10

8 Conclusion

The paper introduces WEB-SHEPHERD, a process reward model for evaluating web-agent trajectories, alongside a dataset and benchmark for PRM development. On WebArena-lite, process-level rewards improve inference-time search over baselines.

8 Conclusion

  • The paper introduces WEB-SHEPHERD, the first PRM designed specifically to evaluate web-agent trajectories.The conclusion frames the work as process reward modeling for web navigation.Source: §8 · p. 10
  • The paper releases WEBPRM COLLECTION, with human-annotated instructions and expert trajectories, and WEBREWARDBENCH, a benchmark for evaluating PRMs.Source: §8 · p. 10
  • 34.55% success rate on WebArena-lite is reported for process-level rewards, compared with 23.64% for baselines.The conclusion also presents checklist-based rewards as a framework that could extend to other sequential decision-making domains with sparse rewards and partial observability.Source: §8 · p. 10

A.1 Limitations

The appendices describe scope boundaries and future directions, societal risks and potential benefits, and human data collection and verification procedures. The annotation process uses a toolkit, trained annotators, expert trajectories, judge codes, and verification safeguards.

A.1 Limitations

  • Coordinate-based action support has a collected dataset, but its exploration remains outside this work's primary scope.Source: §A.1 · p. 15
  • Applying WEB-SHEPHERD as an RL reward signal is left to future work because that setting requires significant computational resources.The authors plan to investigate effects on learning efficiency and final benchmark performance.Source: §A.1 · p. 15
  • The current implementation uses 3B–8B base models; scaling to 32B–72B models, which may improve performance in complex environments, remains future work.Source: §A.1 · p. 15
  • Most existing web-agent benchmark instructions are text-only; extending WEB-SHEPHERD to multimodal instructions is future work.Some tasks, including VisualWebArena tasks, incorporate both text and image modalities.Source: §A.1 · p. 15

A.2 Societal Impacts

  • The authors suggest WEB-SHEPHERD could help web agents tackle complex, goal-oriented tasks, potentially supporting accessibility, professional workflows, and scalable digital assistance.Source: §A.2 · p. 15
  • Without safeguards, autonomous web agents could submit unauthorized forms, modify user data, or access sensitive information; the authors call for constraints, permissions, oversight, and auditing.They also warn that misaligned or insufficiently robust reward models may be exploited through shortcuts that do not accomplish the intended task.Source: §A.2 · p. 15

B.1 Data Annotation Toolkit

  • The annotation toolkit streamlines browser interaction with predefined action types and snapshots of prior actions, which annotators can review or undo.Selecting action types by button clicks rather than typing full action sequences is described as reducing errors.Source: §B.1 · pp. 15–16, Figure 10 · p. 16

B.2 Details of Human Annotation

  • Annotators selected accessible sites, received three hours of training, created tasks across three difficulty levels, recorded expert trajectories, and wrote judge codes.Verification automatically checked judge-code success against trajectories, while managers manually reviewed annotations and discarded 15% of the data.Source: §B.2 · pp. 16–17

B.3 Annotating Dataset with MLLMs

The collection process adds generated rationales and checklists to human trajectory data and gathers rejected actions from multiple policies. The appendix reports human-data composition, action patterns, and the volume and distribution of rejected actions.

B.3 Annotating Dataset with MLLMs

  • Qwen-2.5-VL-72B generates rationales from the current observation, selected action, and post-action screenshot to supplement human trajectories that lack reasoning traces.Source: §B.3 · p. 17
  • GPT-4o generates checklists from instructions and human trajectories that include intermediate thoughts; the authors report that this reasoning-based approach improves checklist quality.Source: §B.3 · p. 17
  • Checklist data grows from 851 human-trajectory instances to 3.6K through GPT-4o-generated checklists for Mind2Web instructions and newly generated instructions.Source: §B.3 · p. 17
  • Rejected actions are sampled from multiple policies, with up to five candidates per chosen action; rule-based filtering retains actions judged clearly invalid but cannot guarantee correctness in every case.Source: §B.3 · pp. 17–18

B.4 Statistics of WEBPRM COLLECTION

  • The human-annotated collection contains 851 tasks: 244 easy, 426 medium, and 181 hard, with 15% discarded during manual verification.Source: §B.4 · p. 18
  • Instructions commonly describe intents such as visiting webpages or finding restaurants, while click, scroll, and fill are the most frequent annotated action types.Source: §B.4 · p. 18
  • The collection contains 30,960 rejected actions from 9,473 chosen actions, and rejected-action distributions differ slightly from chosen-action distributions.Click actions are proportionally more common and scroll actions less common among rejected actions.Source: §B.4 · p. 18

C.1 Training

The appendix specifies Web-Shepherd’s training and inference setup, then describes how chosen and rejected actions are assembled for data construction.

C.1 Training

  • Training uses 3 epochs, a 1e-4 learning rate, rank-16 LoRA, and about 16 GPU-hours on eight RTX A6000 GPUs.The setup uses DeepSpeed ZeRO Stage 2 and LLaMA-Factory with Liger kernel optimization.Source: §C.1 · p. 18

C.2 Inference

  • Inference uses vLLM with temperature 1.0 and nucleus sampling to generate five responses, then sums token-variant logits for each label.The labels are Yes, No, and In Progress, each mapped to listed token variants.Source: §C.2 · pp. 18, 20

D.1 Data Construction

  • WebArena chosen actions are manually annotated expert trajectories; Mind2Web uses supplied actions converted from HTML observations to bid-based observations, with CoT rationales added post hoc by LLMs.Source: §D.1 · p. 20
  • For each chosen action, three MLLM policies generate four rejected actions each, which undergo rule-based and human filtering to form 3,880 test instances.The instances derive from 776 step-level examples across 220 tasks.Source: §D.1 · p. 20

D.2 Analysis of WEBREWARDBENCH

The analyses characterize WebRewardBench’s action and task distributions, test MLLM reward-prediction formats, and compare scoring strategies. They report patterns in action failures, checklist use, and reward estimation.

D.2 Analysis of WEBREWARDBENCH

  • Rejected actions most often involve clicks across source models, while chosen actions are also dominated by clicks and fills, yielding varied failure examples.The authors interpret the similar rejection distributions as evidence that MLLM failure modes concentrate on similar action types.Source: §D.2 · p. 20, Figure 13 · p. 22
  • Most trajectories span 2–8 steps and checklists 2–5 items; longer trajectories generally accompany more checklist items, but short runs can still have several.The authors note this variability supports evaluating steps as well as whole trajectories.Source: §D.2 · p. 20, Figure 13 · p. 22

E.1 Evaluating MLLMs as Process Reward Models for Web Navigation

  • A 1–5 Likert rating consistently outperforms three-class helpful, neutral, or not-helpful classification for MLLM preference reward prediction.Each instance is sampled five times and scores are averaged.Source: §E.1 · p. 20, Table 8 · p. 21
  • Checklist-based reward prediction is more reliable with an In Progress label alongside Yes and No, so the authors use it in benchmark evaluation and training.Source: Table 7 · p. 21, §E.1 · p. 22

E.2 Detailed Results of Refinement

  • The paper provides detailed results for refinement using Web-Shepherd feedback in Table 9, but this passage does not state the outcome.Source: §E.2 · p. 22, Table 9 · p. 22

E.3 Scoring Strategy: Probability vs. Token

  • Sampling five responses improves reward estimation overall; with one response, probability-based scoring performs better than raw output, especially for trajectory accuracy.Source: §E.3 · p. 23, Table 10 · p. 23

E.4 Relationship between Reward and Task Success

This section examines how Web-Shepherd’s final-step rewards track task success, alongside training-data ratios, inference cost, and checklist quality. It also records ethics and release checklist responses, with justifications referring to appendices on societal impacts, dataset verification, asset documentation, and annotation details.

E.4 Relationship between Reward and Task Success

  • Higher normalized final-step rewards for WEB-SHEPHERD are associated with higher success rates, while GPT-4o-mini shows no clear correlation.Rewards are normalized by subtracting the average preceding-step reward within each trajectory; the authors interpret this as better alignment with task success and lower susceptibility to reward over-optimization than GPT-4o-mini.Source: §E.4 · p. 23, Figure 14 · p. 24

E.5 The Impact of the Ratio between Chosen and Rejected Actions in Training Dataset

  • The 1:4 positive-to-negative training ratio provides more effective inference-time guidance than the 1:1 ratio.The comparison uses GPT-4o-mini as policy in WebArena-Lite trajectory search; the authors suggest learning rewards across diverse rejected actions helps even with highly imbalanced examples.Source: §E.5 · pp. 23–24

E.6 Cost Efficiency

  • WEB-SHEPHERD’s per-1,000-instance cost is estimated from evaluation-set token use, single-A100 throughput, and hardware cost.The hardware is priced at $1.19/hour; API-model costs use pricing from OpenRouter, OpenAI, Anthropic, and Google.Source: §E.6 · p. 24

E.7 Evaluating the Quality of the Generated Checklist

  • Checklist quality is comparable across most models, with the initial checklist-only model and WEB-SHEPHERD (3B) as exceptions.The authors release a checklist-only model to support broader use cases and state that task-specific supervision is beneficial.Source: §E.7 · p. 24, Table 13 · p. 25

2. Limitations

  • The authors report discussing positive and negative societal impacts in Appendix A.2.They also answer yes to describing safeguards for responsible release, citing the dataset verification process in Appendix B.Source: §2 · pp. 41–42
  • The paper says it credits the models, benchmarks, and code it uses, and provides explanations for them.It also reports documenting the WebPRM Collection and Web-Shepherd in Appendices B and C.2, respectively.Source: §2 · pp. 42–43
  • The paper says its human annotation process is detailed in Appendix B.2 and that all annotation was performed by the authors.It marks IRB approval as not applicable.Source: §2 · p. 43

Related papers

Loading 2505.15277v2…