Graph2Eval builds agent benchmarks straight out of a knowledge graph

The traditional ways of training AI agents have stopped working. It shows most clearly in agents that have to read documents, parse diagrams, click through sites and carry out multi-step scenarios. Hand annotation goes stale quickly and costs a lot. Generating tasks automatically with LLMs is already being tried, but it usually collapses into plain question-answer formats that teach nothing about real interactivity or tool use.

The Graph2Eval team proposed a clean way out: build the tasks directly from a knowledge graph assembled out of documents and web pages. The graph becomes not just a store of facts but a task space. Pieces of it can be turned automatically into checkable scenarios — both document comprehension and interaction with sites.

The idea: tasks out of a knowledge graph

The knowledge graph brings together:

• elements of documents and web pages (paragraphs, tables, headings, links, forms, buttons);
• the relations between them: structural, semantic and interactive.

Two kinds of tasks come out of it:

• document tasks — extracting facts, comparing them, following chains of links, working with tables and figures;
• web interactions — search, filtering, filling in forms, following results, handling modal windows.

Difficulty is controlled by the size and type of the subgraph: the more steps and relations, the richer the scenario. The web side uses meta-paths — interaction templates at the level of “search → filter → item card” that are matched automatically against a concrete DOM and unrolled into step-by-step agent actions (input, click, navigate).

How it works inside

• Parsing. Documents keep their structure and captions, web pages their DOM and screenshots. Source quality is filtered by rules and by an LLM.
• The graph. Nodes hold text and visual features; edges encode order, containment and links, and on the web, navigation and interactions.
• Subgraph sampling. Document tasks draw on meaningful fragments; web tasks on “seeds” (forms, buttons) and what surrounds them.
• Generation. Task templates are filled with variables from the subgraph and with metadata. Web cases are assembled out of meta-paths into executable chains.
• Selection. Multi-stage filtering accounts for reachability, novelty and coverage of different patterns. That holds the balance between quality and variety.

What it produced in practice

The authors assembled Graph2Eval-Bench: 1,319 tasks — 1,002 document tasks and 317 web interaction tasks. The sources include 16 documents and 8 sites, an average of 83.5 tasks per document and 48.4 per site. There are 12 task types for documents and 7 for the web. Average generation time is 34.87 s for documents and 95.51 s for the web, several times faster than building them by hand.

How the models and agents behaved

Document tasks

A single agent was compared against a multi-agent system with RAG. On F1 and ROUGE-L, GPT-4o came out ahead of everyone; by the LLM judge, DeepSeek-V3 led. One detail stands out: the multi-agent setup gave no consistent gain, and sometimes made quality slightly worse while spending more tokens. The differences between model sizes are sharp — the set really does discriminate.

Web interactions

Two agents were compared: SoM (visual marks) and Agent S 2.5 (reflection and memory). Agent S 2.5 is better almost everywhere. On gemini-2.5-flash, overall success: SoM — 14.51%, Agent S 2.5 — 69.20%. Qwen2.5-VL-72B took second place, and gpt-4o-mini was competitive on individual subtasks. Smaller models are noticeably weaker, which again shows the benchmark's power to discriminate. The conclusion suggests itself: reflection during execution and richer memory help agents get through multi-step web scenarios more reliably.

Why this matters

• The graph as a “task space” pulls documents and the web into a single logic and gives control over difficulty.
• Interactive web cases can now be generated automatically — a rare chance to test agents honestly.
• The pipeline scales and reproduces: the benchmark can be refreshed as the sources change, without rewriting everything by hand.
• Evaluation along several dimensions (single agent, multi-agent system, web agent) exposes the real gaps — in reasoning, in cooperation and in interaction.

Where this goes next

The authors plan to add formal safety policies and to build verifiable safe cases, and to use the structure of the graph for precise error detection. That would make it possible not just to measure an overall score but to explain where exactly an agent gets lost: in finding the right node, in chaining facts together, or in driving the interface.

💾 Code