PaperlayerView exact revision on arXiv

Source-linked AI summary

From Trajectories to Grounded Preferences: Process Preference Synthesis via Interaction Element Graphs for Web PRMs

Yangzhe Peng, Xiaoyang Wang, Yiyang Zhao, Lijun Wu, Kun He

arXiv:2609.32351v1cs.AI

TL;DR

Web PRM training data synthesized by multi-policy sampling contains few grounded, same-action-type contrasts between candidate actions. SURFPRM uses a persistent Interaction Element Graph to propose such negatives and constructs a curated preference dataset. The dataset improves Web PRM benchmark performance and reward-guided search results.

  • Problem

    Multi-policy-sampled Web PRM data has only 24.19% GMCPs, where competing candidates target genuine on-page elements with identical action types.

    Source: §1 · p. 2

  • Method

    SURFPRM aggregates demonstrations into a persistent Interaction Element Graph and proposes grounded negative actions across spatial, temporal, and spatiotemporal axes.

    Source: §1 · p. 2, §3.3 · p. 5

  • Results

    SURFPRM-DATA raises the GMCP proportion from 24.19% to 74.60%, and its PRMs outperform baseline-trained models on average on WEBPRMBENCH and improve WEBARENA-LITE search success by 14.21% for GPT-4o and 12.83% for GPT-4o-mini.

    Source: §1 · p. 2, §5.2 · p. 8, §6 · p. 10

  • Takeaways & Limitations

    Across six open-source backbones from 3B to 9B parameters, SURFPRM-trained PRMs provide step-level guidance that improves downstream reward-guided web-agent search.

    Source: §1 · p. 2, §6 · p. 10

Abstract

from arXiv · show

Comparative Process Reward Models (PRMs) provide critical step-level guidance for autonomous web agents by evaluating state-conditioned preferences between candidate actions. However, existing preference training data synthesized via multi-policy sampling suffers from a severe scarcity of Grounded Minimal Contrastive Pairs (GMCPs)-where competing candidates target genuine on-page elements with identical action types. In representative baselines preference data (namely, WebArbiter), GMCPs account for merely 24.19%, biasing PRMs during training to rely on shallow shortcuts (such as element hallucinations and action type mismatches) rather than acquiring genuine contextual decision semantics. To address these challenges, we propose SURFPRM, a graph-guided process preference synthesis framework for comparative Web PRMs. SURFPRM structures web demonstrations into a persistent Interaction Element Graph that acts as an environment-grounded negative action proposal mechanism, systematically synthesizing contrastive negative actions across spatial, temporal, and spatiotemporal confusion axes. This elevates the GMCP proportion from 24.19% to 74.60%, producing the curated SURFPRM-DATA dataset. Across six open-source backbones (3B to 9B parameters), PRMs trained on SURFPRM-DATA outperform baseline-trained models on average on WEBPRMBENCH and rival leading proprietary LLMs. In downstream reward-guided trajectory search on WEBARENA-LITE, SURFPRM provides step-level guidance for both GPT-4o (+14.21%) and GPT-4o-mini (+12.83%) policies, yielding substantial improvements in complex web task success rates.

1 INTRODUCTION

The paper identifies a scarcity of grounded, same-action-type contrasts in Web PRM training data and proposes SURFPRM, which uses an Interaction Element Graph to synthesize them. The resulting dataset raises the GMCP share and supports stronger benchmark and search performance.

1 INTRODUCTION

  • Comparative Web PRMs evaluate preferences between candidate actions in the same state, whereas outcome reward models provide only delayed trajectory-level rewards.The paper motivates step-level verification because unguided greedy decoding can lead web agents into irreversible dead ends.Source: §1 · pp. 1–2
  • Existing multi-policy-sampled Web PRM data contains only 24.19% GMCPs, where candidates target genuine on-page elements with identical action types.The remaining pairs are dominated by element hallucinations and action-type mismatches, which the paper says bias training toward superficial cues.Source: §1 · p. 2
  • 74.60% of SURFPRM-DATA pairs are GMCPs, compared with 24.19% in WebArbiter.The framework proposes negatives across spatial, temporal, and spatiotemporal axes using an Interaction Element Graph.Source: §1 · p. 2

2 RELATED WORK

Prior work develops web-agent benchmarks, synthetic environments, and step-level reward models, but policy-generated candidates do not ensure grounded, action-type-controlled comparisons. SURFPRM instead mines contrastive negatives from demonstration interaction graphs without requiring active environment rollouts or resets.

2 RELATED WORK

  • Web interfaces contain dense, overlapping interactable elements, and prior failure analyses identify low-level execution and grounding errors as a primary bottleneck.Positive-only imitation demonstrations provide no discriminative signal against plausible decoy elements in the same observation.Source: §2 · pp. 2–3
  • WebArbiter and WebShepherd use policy-generated candidates, which do not ensure grounded, action-type-controlled comparisons; WebArbiter data contains 24.19% GMCPs.SURFPRM proposes negatives from an Interaction Element Graph, followed by teacher filtering and synthesis of rationales and verdicts.Source: §2 · p. 3
  • Unlike online agentic RL methods focused on policy optimization, SURFPRM builds an evaluative verifier for downstream inference-time search without active rollouts or resets.It perturbs successful demonstration steps along spatial, temporal, and spatiotemporal axes using a persistent Interaction Element Graph.Source: §2 · p. 3

3 METHOD

SURFPRM represents website demonstrations as persistent interaction graphs and uses graph-based proposals to create grounded negative actions. Teacher verification filters candidate pairs and supplies rationales and preference labels for comparative Web PRM training.

3.1 PROBLEM FORMULATION AND COMPARATIVE PRM PIPELINE

  • A comparative Web PRM evaluates candidate actions in a state defined by the instruction, AXTree observation, action history, and current URL.The model outputs a judgment rationale and the preferred candidate index.Source: §3.1 · p. 4

3.2 WEBSITE INTERACTION ELEMENT GRAPH CONSTRUCTION

  • The Interaction Element Graph combines persistent element nodes, spatial containment edges, and temporal transitions observed across successful trajectories.Element identities use BID-invariant context; the graph records observed relationships rather than a complete world model.Source: §3.2 · p. 4

3.3 GRAPH-BASED GROUNDED MINIMAL NEGATIVE ACTION SYNTHESIS

  • SURFPRM proposes negatives from graph elements uniquely resolvable in the active AXTree, raising the GMCP proportion to 74.60%.Virtual nodes represent non-DOM positive steps but are not proposed as negatives.Source: §3.3 · pp. 4–5
  • Six graph-based rules target spatial distraction, temporal misordering, and divergence from the task’s global progression.Examples include selecting nearby or textually similar elements, repeating past actions, acting too early, moving away from the goal, and creating a cycle.Source: Figure 2 · p. 4, §3.3 · p. 5

3.4 TEACHER VERIFICATION AND GOLD SUPERVISION SYNTHESIS

  • The teacher filters candidate pairs only when all five independent trials contradict the trajectory label; 9,821 of 10,000 sampled pairs pass verification.For retained pairs, the consistent judgment rationale is used as gold supervision.Source: §3.4 · p. 5

4 DATA COLLECTION AND DATASET STATISTICS

SURFPRM-DATA is built from successful web demonstrations aggregated into site-level interaction graphs, then curated into grounded contrastive pairs and checked for execution compliance and false negatives.

4.1 SOURCE TRAJECTORIES AND GRAPH CONSTRUCTION

  • 854 successful trajectories and 9,497 page observations from 50 websites form 50 site-level subgraphs containing 116,182 element nodes and 8,271 deduplicated spatial and temporal edges.The source demonstrations match those used for WebArbiter.Source: §4.1 · p. 6

4.2 DATASET CURATION AND FINAL STATISTICS

  • Of 31,648 mined candidates, 31,400 uniquely resolved in active observations; 9,821 of 10,000 teacher-verified pairs passed the K = 5 consistency filter.The final dataset covers 1,084 normalized URL paths.Source: §4.2 · p. 6
  • Table 1 summarizes the distribution of proposal rules across the 10k-pair dataset.The dataset’s proposal rules are described as the basis for contrastive negatives.Source: Table 1 · p. 6, §4.2 · p. 6
  • SURFPRM-DATA raises the GMCP share from 24.19% in WebArbiter to 74.60% (7,326 of 9,821 pairs), with every negative grounded in an active page element.The remaining 25.40% are virtual-positive pairs or affordance-driven action-type divergences.Source: §4.2 · p. 6

4.3 QUALITY ASSURANCE AND ITERATIVE REFINEMENT

  • 30 of 100 WebArbiter negatives were false negatives, compared with 12 of 100 for SURFPRM-DATA, a reduction from 30% to 12%.Automated checks also found zero empty input values.Source: §4.3 · p. 6

5 EXPERIMENTS

The experiments evaluate comparative Web PRMs on held-out environments and downstream trajectory search, then examine GMCP ratios, graph structure, and confusion axes. SURFPRM-DATA-trained models outperform WebArbiter-trained models across six backbones, and SURFPRM improves guided task success for both tested policies.

5.1 EXPERIMENTAL SETUP

  • Evaluation measures Pairwise and BoN accuracy on three WEBPRMBENCH environments, excluding MIND2WEB because its demonstrations overlap with SFT training, and tests reward-guided search on WEBARENA-LITE.The six-backbone comparison uses aligned approximately 10k training budgets and identical protocols.Source: §5.1 · pp. 7–8

5.2 MAIN EXPERIMENTAL RESULTS

  • 46.11% macro-average success with GPT-4o guidance (+14.21% over unguided) and 36.31% with GPT-4o-mini (+12.83%) on WEBARENA-LITE.The table reports success rates across five environments; GitLab success declines under GPT-4o guidance.Source: Table 3 · p. 8, §5.2 · p. 8
  • Across all six 3B–9B backbones, SURFPRM-DATA models consistently outperform WebArbiter on WEBPRMBENCH macro-average Pairwise and BoN; Qwen2.5-3B gains +6.45% and +7.76%, respectively.Source: §5.2 · p. 8

5.3 IN-DEPTH ANALYSIS AND ABLATION STUDIES

  • 80.65% Pairwise and 51.29% BoN accuracy at 74.60% GMCP exceed 74.20% and 43.53% at 24.19% GMCP; full-GMCP BoN rises from 66.67% for WebArbiter to 71.50%.On the full non-GMCP subset, BoN accuracy saturates near 51% across variants.Source: §5.3 · p. 9
  • 80.65% Pairwise and 51.29% BoN for the graph model exceed No-Graph’s 75.50% and 42.01%, with matched GMCP ratios and aligned dataset scales.The compared settings share demonstration states, BID remapping, and teacher scoring.Source: §5.3 · p. 9
  • The full mixture reaches 80.65% Pairwise and 51.29% BoN, outperforming each single-axis variant and supporting the complementary role of spatial, temporal, and spatiotemporal proposals.The temporal-only training set contains 470 pairs, compared with more than 4,000 for each of the other axes; training updates were scaled to comparable orders of magnitude.Source: §5.3 · p. 9

6 CONCLUSION

SURFPRM uses an Interaction Element Graph to propose contrastive negatives across three confusion axes, raising GMCPs in SURFPRM-DATA and improving Web PRM and trajectory-search results. The paper also describes reproducibility resources and its use of generative AI.

6 CONCLUSION

  • SURFPRM raises the GMCP proportion from 24.19% to 74.60% and reports improved WEBPRMBENCH and WEBARENA-LITE results.Across six 3B–9B backbones, SURFPRM-DATA-trained PRMs outperform baselines on WEBPRMBENCH; reward-guided search gains are +14.21% for GPT-4o and +12.83% for GPT-4o-mini.Source: §6 · p. 10

REPRODUCIBILITY STATEMENT

  • The paper provides algorithmic, implementation, and experimental specifications, with datasets and trained checkpoints anonymously accessible.The statement locates graph formulation and proposal rules in Section 3.2 and Appendices A and B, and describes evaluation setups and extended ablations in Section 5.1 and Appendix E.Source: REPRODUCIBILITY STATEMENT · p. 10

AI USE STATEMENT

  • The authors report using generative AI for synthetic data, implementation, translation, dataset cleanup, analysis, code, and literature identification, with authors reviewing the work.They state that LLM-generated code was verified and tested for correctness.Source: AI USE STATEMENT · p. 10

A FORMAL DEFINITIONS OF GRAPH-BASED PROPOSAL RULES

The appendix formalizes six graph-based rules for proposing negative actions from demonstrated interactions. The rules select candidates by structural or textual proximity and by temporal or goal-related relations, subject to grounding and graph constraints.

A FORMAL DEFINITIONS OF GRAPH-BASED PROPOSAL RULES

  • Candidate negative actions use a grounded graph node and prefer that node’s most frequently demonstrated complete action, with executable-label fallbacks when history is absent.The six rules include structurally near, textually near but graph-distant, repeat-past, act-too-early, away-from-goal, and create-a-cycle proposals.Source: A FORMAL DEFINITIONS OF GRAPH-BASED… · p. 15
  • Textually similar candidates that lie within four combined-graph hops are excluded because they may form valid multi-step navigation paths.The combined graph uses spatial and temporal edges; spatial distance is measured along containment edges.Source: A FORMAL DEFINITIONS OF GRAPH-BASED… · p. 15
  • Repeat Past and Act Too Early select prior or upcoming successful targets on the same page URL, using demonstrated action identities and a lookback or lookahead horizon of five.The rule indexes prior or subsequent successful targeted interactions rather than raw environment steps.Source: A FORMAL DEFINITIONS OF GRAPH-BASED… · p. 15
  • Away from Goal and Create a Cycle use combined-graph reachability to propose distractors related to the task goal or recent interaction history.Away from Goal is skipped when the positive target has no path to the goal; cycle candidates need not themselves have been visited previously.Source: A FORMAL DEFINITIONS OF GRAPH-BASED… · pp. 15–16

B PERSISTENT NODE IDENTITY, ACTION MAPPING, AND VIRTUAL NODES

The appendix describes how the Interaction Element Graph maintains persistent identities for DOM elements and represents non-DOM actions. It also explains why some verified preference pairs are not GMCPs despite all negative targets resolving to active elements.

B PERSISTENT NODE IDENTITY, ACTION MAPPING, AND VIRTUAL NODES

  • Persistent element identities use site, URL, and BID-invariant structural context so elements can be aligned across trajectories despite changing runtime BIDs.The context includes accessible descriptors, ancestor chain, sibling position, and subtree signature; URL scoping keeps semantically distinct pages separate.Source: B PERSISTENT NODE IDENTITY, ACTION… · p. 16
  • Element-grounded actions map to persistent element nodes, while viewport, navigation, tab, and terminal-response actions map to typed virtual nodes.Virtual nodes preserve trajectory transitions as directed temporal edges, and are scoped to landing pages to retain local topological fidelity.Source: B PERSISTENT NODE IDENTITY, ACTION… · pp. 16–17
  • 74.60% of verified pairs are GMCPs; the remaining 25.40% arise from virtual positive steps or affordance-preserving action-type mismatches, not absent targets.The audit reports that 0% of non-GMCP pairs fail because negative targets are absent from the active AXTree; the two sources are reported as 16.6% and 9.1%.Source: B PERSISTENT NODE IDENTITY, ACTION… · pp. 17–18
  • The graph excludes 685 successful-action targets that cannot be resolved in the AXTree/SOM marker space rather than approximating them.One keyboard type action was discarded, while eight mouse-click targets were recovered through a manual BID audit table.Source: B PERSISTENT NODE IDENTITY, ACTION… · p. 17

C IMPLEMENTATION DETAILS

The implementation isolates candidate actions from their exploratory rationales during data construction and PRM training. The appendix also reports teacher-verification costs for the sampled candidate pairs.

C IMPLEMENTATION DETAILS

  • The Action-Only protocol strips candidate rationales so teachers and PRMs receive the state and raw candidate actions rather than generator-style cues.The state includes the instruction, AXTree observation, action history, and URL; actions are rendered with operation type, target BID, and arguments.Source: C IMPLEMENTATION DETAILS · p. 18
  • Teacher verification issued 11,210 calls for 10,000 sampled pairs and cost approximately $335 in total.The reported average was $0.0334 per pair; Table 4 covers teacher verification and gold-supervision synthesis cost.Source: C IMPLEMENTATION DETAILS · p. 18, Table 4 · p. 18

D PROMPT SPECIFICATIONS: ALIGNMENT FILTERING, GOLD SYNTHESIS, FILL VALUE COMPLETION, AND JEV EVALUATION

Appendix D specifies how candidate pairs are alignment-filtered, how verified judgments become SFT targets, how fill negatives receive values, and how two JEV decision modes evaluate candidates.

D.1 ALIGNMENT FILTERING PROMPT SPECIFICATION

  • The teacher compares randomized Response 1 and Response 2 using task intent, the accessibility tree, trajectory, and URLs, then returns a structured state, criteria, analysis, and verdict.The pair is discarded only if the verdict still disagrees with the ground-truth label after up to five sequential re-evaluation attempts.Source: §D.1 · pp. 18–19

D.2 GOLD JUDGMENT RATIONALE AND VERDICT SYNTHESIS

  • For aligned pairs, the first response whose verdict matches the ground truth is retained, with no further selection among aligned trials.Its reasoning prefix and verdict are inserted verbatim as the assistant message in the SFT triple.Source: §D.2 · p. 19

D.3 CONTEXTUAL FILL VALUE COMPLETION PROMPT SPECIFICATION

  • When an unobserved text-entry target lacks a concrete value, an LLM generates a concise, plausible input that differs from existing field content.The prompt fixes the target BID and action type and conditions value generation on the instruction, page state, target evidence, and known positive action.Source: §D.3 · p. 20
  • The fill-value completion model decodes at temperature 0.2.Source: §D.3 · p. 20

D.4 JEV EVALUATION PROMPT SPECIFICATIONS

  • JEV receives shared judging-guidance and web-context state blocks containing the task, page observation, trajectory, URLs, and candidate responses.The evaluation covers Choice and Noul modes.Source: §D.4 · pp. 20–21
  • Choice mode asks which response is the better next step, assessing correctness, grounding in the current page, and effectiveness for the intent.Source: §D.4 · p. 21
  • Noul mode keeps both state blocks unchanged and asks whether Response 1 is better, assigning false when Response 2 is better or the responses are indistinguishable.Source: §D.4 · p. 21

E EXTENDED EVALUATION AND REPEATED RUNS

The appendix details graph-axis and GMCP-ratio ablations, graph-necessity comparisons, and repeated-run stability; the reported repeated runs show consistent gains for SURFPRM-DATA over the WebArbiter 10k baseline.

Ablation on Graph Confusion Axes

  • The graph-confusion-axis ablation compares individual Spatial, Temporal, and Spatiotemporal training against the complete multi-axis mixture on WEBPRMBENCH.Because temporal mining yields 470 pairs versus more than 4,000 for the other axes, its fine-tuning epochs are increased to align compute and gradient-update steps in order of magnitude.Source: E EXTENDED EVALUATION AND REPEATED RUNS · p. 21, Table 5 · p. 22

Effect of the Grounded Minimal Contrastive Pair (GMCP) Ratio

Graph Necessity Ablation

Repeated Evaluation Runs and Statistical Stability

  • 86.22±0.20% Pairwise and 68.01±0.24% BoN were reached by SURFPRM-DATA, versus 84.16±0.51% and 64.09±1.01% for the WebArbiter 10k baseline, with low variance across three runs.The reported average standard deviations are ±0.20% for Pairwise and ±0.24% for BoN; gains are clear on WebArena and WorkArena while performance remains competitive on AssistantBench.Source: E EXTENDED EVALUATION AND REPEATED RUNS · pp. 22–23, Table 8 · p. 23

F DATA QUALITY ASSURANCE PIPELINE DETAILS

The data-quality appendix documents how fill negatives and custom dropdown controls are corrected to support executable actions.

Parameter Completion for Fill Actions

  • Of 262 mined fill negatives, 199 lacked input strings, so an LLM generated plausible but incorrect or distracting values; 11 non-editable targets were remapped to clicks, leaving 251 fill negatives.In the sampled 10,000 pairs, 73 fill negatives were present and 68 remained in the verified 9,821-pair set; audits found no empty values, repeated current values, or invalid formats.Source: F DATA QUALITY ASSURANCE PIPELINE… · p. 23

Combobox Control Correction

  • Custom dropdowns without editable inputs were remapped from fill to click, with selection handled through standard dropdown click-and-select semantics.This correction addressed runtime execution errors from attempting fill operations on those controls.Source: F DATA QUALITY ASSURANCE PIPELINE… · p. 23
Loading 2609.32351v1…