Graph2Eval: Automatic Multimodal Task Generation for Agents via Knowledge Graphs

1. Introduction

• Static datasets cannot distinguish genuine generalization from retrieval of memorized knowledge, so success on them does not establish real-world reliability.The authors also identify limited task diversity, labor-intensive dataset expansion, weak entity-relation modeling, and poor adaptation to dynamic websites as gaps in existing methods.Source: §1 · pp. 1–2
• Graph2Eval treats a knowledge graph as a task space and uses task templates, meta-paths, and sampled subgraphs to generate document-understanding and web-interaction tasks.LLMs combine sampled graph structures with contextual information to produce task instances.Source: §1 · p. 2
• 20% higher semantic consistency and 17% higher solvability on average than a KG-free baseline are reported for tasks generated by Graph2Eval.Graph2Eval-Bench contains 1,319 tasks for evaluating RAG Agents and Web Agents, and distinguishes performance across foundation models.Source: §1 · p. 2
• Graph2Eval-Bench contains 1,319 diverse tasks designed to evaluate both Retrieval-Augmented Generation Agents and Web Agents.The dataset includes 1,002 document-understanding tasks and 317 web-interaction tasks.Source: §1 · p. 2

2. Background

• Most existing agent-oriented benchmarks are manually constructed, and their human-defined task specifications limit scalability.The cited examples include GAIA, MiniWob, MiniWoB++ [18], and Mind2Web.Source: §2 · p. 2
• TaskCraft lacks explicit entity relationships, while Su et al. rely on static documents for web tasks and cannot reliably assess executability in dynamic scenarios.The described quality checks for Su et al. are deduplication and LLM-based alignment and evaluation.Source: §2 · p. 3

3. GRAPH2EVAL

• Graph2Eval's five-stage pipeline ingests data, constructs a knowledge graph, samples subgraphs, generates tasks, and optimizes coverage.The graph is presented as a structured task space for document-understanding tasks for RAG Agents and web-interaction tasks for Web Agents.Source: §3 · p. 3, Figure 2 · p. 4

3.1. Data Ingestion

• Document ingestion preserves layout and hierarchy as semantic graph nodes, while web ingestion crawls pages, extracts DOM structures and screenshots, and uses simulated interactions.Document processing also computes embeddings and adds source and positional metadata; web collection filters links and applies safety constraints.Source: §3.1 · p. 3

3.2. KG Construction

• The graph represents document and web content as nodes with preserved structural paths, textualized visual content, and edges for semantic, structural, reference, and interaction relations.Combined node text is embedded and stored for semantic search and similarity matching.Source: §3.2 · pp. 3–4

3.3. Subgraph Sampling

• Document sampling selects relevant, structurally aligned nodes, while web sampling starts from task-specific operational seeds and collects their local interaction context.The sampling workflow extracts a task-specific subgraph and its interconnections from the knowledge graph.Source: §3.3 · p. 4

3.4. Task Generation

• Document tasks use templates and sampled-subgraph variables, whereas web tasks match seed-driven subgraphs to meta-path task chains before LLM generation.Different strategies reflect the execution modes: document tasks use a few API calls, while web tasks require sequential interaction in dynamic environments.Source: §3.4 · p. 5

3.5. Coverage Optimization

• Coverage optimization filters web-task quality, measures coverage and multi-level novelty, and uses MMR selection; document tasks use semantic diversity, LLM-based similarity, and MMR.Web coverage spans node and edge types, patterns, pages, website types, and difficulty; document coverage spans task type, difficulty, template, variable, and content length.Source: §3.5 · pp. 5–6

4.1. Implementation Details

• RAG document agents are tested in single- and multi-agent settings alongside web agents; metrics include F1, ROUGE-L, LLM Judge, web SR, consistency, and solvability.The multi-agent document setup comprises a planner, retriever, reasoner, verifier, and summarizer; web evaluation includes SoM Agent and Agent S 2.5.Source: §4.1 · p. 6

4.2. Main Results

• Document tasks use high-quality papers and web tasks use screenshots plus DOM; 100 sampled node pairs were manually verified, and Figure 3 reports lower generation time than manual construction.Table 1 presents benchmark statistics.Source: §4.2 · p. 6, Figure 3 · p. 6, Table 1 · p. 6
• GPT-4o leads F1 and ROUGE-L, while Deepseek-V3 leads LLM-as-a-Judge in document understanding.GPT-4o ranks second on LLM-as-a-Judge.Source: §4.2 · pp. 6–7, Table 2 · p. 7
• In GRAPH2EVAL-BENCH web interaction tasks, Agent S 2.5 consistently outperformed SoM Agent across nearly all task types; on Gemini 2.5 Flash, they achieved 69.20% and 14.51% SR, respectively.Source: §4.2 · p. 7, Table 3 · p. 7

4.3. Ablation Studies

• Against KG-free generation, GRAPH2EVAL tasks reveal clearer size-related performance gaps; KG-free web tasks are often single-page, with multi-page workflows unsolvable from missing inter-page relations.Tasks generated without a KG also require LLM or manual review to resolve ambiguities.Source: §4.3 · p. 8, Table 4 · p. 8

4.4. Comparison with Existing Methods

• Compared with human-annotated benchmarks, GRAPH2EVAL enables low-time-cost automated construction with strong consistency and solvability across more task types; unlike TaskCraft, it samples subgraphs from a complete graph.TaskCraft first generates atomic tasks and combines them into complex ones, while GRAPH2EVAL uses a top-down paradigm.Source: §4.4 · p. 8, Table 5 · p. 8, Table 6 · p. 8

5. Conclusion and Future Work

• Graph2Eval models entities and relationships in documents and web data as a unified task space for scalable, semantically consistent, and solvable task creation.The framework is used to construct Graph2Eval-Bench and assess document-understanding and web-interaction capabilities across settings.Source: §5 · p. 8
• Experiments report improved semantic consistency and solvability, broad scenario coverage, and reliable assessment of document understanding and web interaction.Source: §5 · p. 8
• Future work will explore formal safety policies for adversarial and malicious scenarios and use knowledge-graph structure to localize errors at nodes and edges.Source: §5 · p. 8

A. Task Content Constraints

• Web-task safety combines page screening for privacy, copyright, harmful content, and robots compliance with bans on payment or privacy-data operations and business-data placeholders.Source: A. Task Content Constraints · p. 11

B. Task Templates

• Templates specify graph-structure requirements and difficulty-tagged task types, then select graph-compatible prompts and reference answers with evaluation criteria and citation requirements.The supported tasks range from extraction and summarization to multi-hop reasoning, image interpretation, and cross-referencing.Source: B. Task Templates · p. 11

C. Meta-Path

• Meta-path patterns match web subgraphs, bind variables to graph nodes, and generate executable task steps, prioritizing business-data patterns before general and basic interaction fallbacks.A graph-regex engine supports node and edge matching, quantifiers, and alternatives.Source: C. Meta-Path · pp. 11–12

D. Limitations and Discussion

• Incomplete or erroneous knowledge graphs may adversely affect the quality of generated tasks.Source: D. Limitations and Discussion · p. 12
• The focus on structured knowledge and predefined relationships may limit tasks involving unstructured or novel information outside the graph.Source: D. Limitations and Discussion · p. 12
• The authors propose more robust graph construction and methods that use unstructured data to improve task quality, diversity, and coverage.Source: D. Limitations and Discussion · p. 12

E. Agent Architecture

• The Single-Agent follows a retrieve-execute-evaluate-respond workflow and returns references, reasoning paths, and confidence scores while retaining task history.Source: E. Agent Architecture · p. 12
• The Multi-Agent assigns planning, retrieval, reasoning, verification, and summarization roles, with coordinated messaging for task allocation and load balancing.The passage reports collaborative reasoning performance superior to single-agent setups for complex multi-hop tasks.Source: E. Agent Architecture · p. 12
• The SoM Agent maps textual descriptions to web-element coordinates by having an LLM identify marked elements in a screenshot.Source: E. Agent Architecture · p. 12
• Agent S 2.5 combines screenshot-and-text processing with a reflection module that analyzes execution trajectories and suggests improvements.Source: E. Agent Architecture · p. 12

F.1. Document Understanding Task Metrics

• F1 is the harmonic mean of precision and recall for predicted and ground-truth answer spans.Source: §F.1 · p. 12
• ROUGE-L measures the longest common subsequence between the predicted answer span P and ground-truth span G.Source: §F.1 · p. 12
• The LLM-as-a-Judge scores document answers on quality, relevance, and completeness, normalizing scores to [0, 1] for an overall semantic-alignment judgment.Source: §F.1 · p. 13
• The document-answer evaluation prompt asks for 0.0–1.0 ratings of answer quality and accuracy, relevance to the task, and completeness.Source: §F.1 · p. 13
• The document-evaluation rubric prioritizes answer quality and records answer_quality, relevance, and completeness scores.Source: §F.1 · p. 13

F.2. Web Task Metrics

• Success Rate is the fraction of web tasks judged successful by an LLM evaluator.Source: §F.2 · p. 13
• For web-task evaluation, the LLM assesses action sequences, final page state, and error messages because dynamic pages make rule-based checks unreliable.Source: §F.2 · p. 13

F.3. LLM Evaluator Reliability

• 88% of judgments matched GPT-4o on 50 Agent S 2.5 web-task trajectories independently judged by two human annotators.The annotators labeled each trajectory successful or unsuccessful.Source: §F.3 · p. 14

• 1,319 tasks comprise document-understanding and web-interaction datasets, with document tasks covering reasoning, analysis, and aggregation.Source: G. GRAPH2EVAL-BENCH Overview · p. 14
• Web tasks focus on navigation and interaction across domains including digital libraries, weather services, and news portals to mitigate risks to live websites.Source: G. GRAPH2EVAL-BENCH Overview · p. 14

• Agent S 2.5 uses screenshots and DOM representations with memory and reflection to select and execute actions, then another LLM validates the outcome.Source: H. Case Study · p. 14
• Graph2Eval records execution time and token consumption during the web-task trajectory as efficiency and cost indicators.Source: H. Case Study · p. 14

• For document understanding, safety instances are derived from existing tasks with minimal input perturbation to preserve naturalness and detect latent model risks.Source: §I · p. 14
• Document safety generation parses policy or security documents for candidate threats, explores four embedding strategies, then creates and quality-checks instances against preset thresholds.The strategies are content injection, prompt manipulation, context switching, and indirect reference; checks cover clarity, relevance, difficulty, and completeness.Source: §I · p. 14
• Web safety tasks use isolated Docker environments or controlled browser sessions to simulate threats, and augment existing tasks with safety nudges.Injected artifacts can include forged phishing elements, malicious forms, or suspicious redirects.Source: §I · p. 14