# WebGraphEval: Multi-Turn Trajectory Evaluation for Web Agents using Graph Representation

arXiv: https://arxiv.org/abs/2510.19205 · HTML: https://mlsanity.com/paper/2510.19205/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in Web, search, and research agents, one of 16 directions in LLM agents and tool use.
- Builds on 19 of its 25 references that are in the map.
- First posted on arXiv 22 Oct 2025.

## Placed in

- LLM agents and tool use / [Web, search, and research agents](https://mlsanity.com/agents/web-search-and-research-agents/)

## Builds on (most cited first, 19 of 19)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](https://mlsanity.com/paper/2404.16130/) (2024)
- [A Survey on LLM-as-a-Judge](https://mlsanity.com/paper/2411.15594/) (2024)
- [AgentBench: Evaluating LLMs as Agents](https://mlsanity.com/paper/2308.03688/) (2023)
- [WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agents](https://mlsanity.com/paper/2207.01206/) (2022)
- [Mind2Web: Towards a Generalist Agent for the Web](https://mlsanity.com/paper/2306.06070/) (2023)
- [ALFWorld: Aligning Text and Embodied Environments for Interactive Learning](https://mlsanity.com/paper/2010.03768/) (2020)
- [UI-TARS: Pioneering Automated GUI Interaction with Native Agents](https://mlsanity.com/paper/2501.12326/) (2025)
- [WebVoyager: Building an End-to-End Web Agent with Large Multimodal Models](https://mlsanity.com/paper/2401.13919/) (2024)
- [LightRAG: Simple and Fast Retrieval-Augmented Generation](https://mlsanity.com/paper/2410.05779/) (2024)
- [FLASK: Fine-grained Language Model Evaluation based on Alignment Skill Sets](https://mlsanity.com/paper/2307.10928/) (2023)
- [ST-WebAgentBench: A Benchmark for Evaluating Safety and Trustworthiness in Web Agents](https://mlsanity.com/paper/2410.06703/) (2024)
- [Learn-by-interact: A Data-Centric Framework for Self-Adaptive Agents in Realistic Environments](https://mlsanity.com/paper/2501.10893/) (2025)
- [Mind2Web 2: Evaluating Agentic Search with Agent-as-a-Judge](https://mlsanity.com/paper/2506.21506/) (2025)
- [Graph-R1: Towards Agentic GraphRAG Framework via End-to-end Reinforcement Learning](https://mlsanity.com/paper/2507.21892/) (2025)
- [VideoWebArena: Evaluating Long Context Multimodal Agents with Video Understanding Web Tasks](https://mlsanity.com/paper/2410.19100/) (2024)
- [Towards Enterprise-Ready Computer Using Generalist Agent](https://mlsanity.com/paper/2503.01861/) (2025)
- [GraphRAG-Causal: A novel graph-augmented framework for causal reasoning and annotation in news](https://mlsanity.com/paper/2506.11600/) (2025)

## Built on by (most cited first, 7 of 7)

- [A Subgoal-driven Framework for Improving Long-Horizon LLM Agents](https://mlsanity.com/paper/2603.19685/) (2026)
- [GUIDE: Interpretable GUI Agent Evaluation via Hierarchical Diagnosis](https://mlsanity.com/paper/2604.04399/) (2026)
- [Tangent: An Empirical Study of Testing Practices for LLM-Based Agent Applications](https://mlsanity.com/paper/2608.08413/) (2026)
- [Do Web Agents Investigate Before They Decide?](https://mlsanity.com/paper/2602.05354/) (2026)
- [SearchAtlas: Analyzing Agentic Search Strategies via Evidential Query Graphs](https://mlsanity.com/paper/2609.10901/) (2026)
- [GUITAR: Structured Failure Diagnosis of GUI Agents via State Transitions](https://mlsanity.com/paper/2609.34113/) (2026)
- [Auditing Web Agent Evaluation on WebArena-Lite: Human Review of Outcomes and Trajectories](https://mlsanity.com/paper/2610.01491/) (2026)

## Abstract (arXiv)

Current evaluation of web agents largely reduces to binary success metrics or conformity to a single reference trajectory, ignoring the structural diversity present in benchmark datasets. We present WebGraphEval, a framework that abstracts trajectories from multiple agents into a unified, weighted action graph. This representation is directly compatible with benchmarks such as WebArena, leveraging leaderboard runs and newly collected trajectories without modifying environments. The framework canonically encodes actions, merges recurring behaviors, and applies structural analyses including reward propagation and success-weighted edge statistics. Evaluations across thousands of trajectories from six web agents show that the graph abstraction captures cross-model regularities, highlights redundancy and inefficiency, and identifies critical decision points overlooked by outcome-based metrics. By framing web interaction as graph-structured data, WebGraphEval establishes a general methodology for multi-path, cross-agent, and efficiency-aware evaluation of web agents.