GABench: A Comprehensive Benchmark for Evaluating LLM Agents on Graph Analysis Tasks

arXiv:2608.01684 · cs.AI · Submitted 2026-08-03 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: We're looking at the paper: "GABench: A Comprehensive Benchmark for Evaluating LLM Agents on Graph Analysis Tasks".

Jane: Here's the gist of the paper. Large language model (LLM) agents are increasingly capable of planning, using tools, and interacting with external environments They are typically supported by harnesses, which manage state and coordinate multi-step execution Graph analysis provides a promising setting for evaluating their agentic capabilities, because it requires agents to access data and execute operations in a graph environment However, existing graph benchmarks for LLMs provide limited coverage of graph tasks and graph types, making it difficult to comprehensively evaluate LLM agents Moreover, they typically formulate graph analysis as text-based question answering, where graph information is directly provided in the prompt, limiting the evaluation of end-to-end agentic capabilities.

Tom: To address these limitations, we introduce GABench, a comprehensive benchmark for agentic graph analysis.

Jane: Benchmark Scope and Coverage GABench spans three graph types and covers four graph analysis task categories: graph retrieval, graph theory, graph machine learning, and graph open-ended question answering.

Tom: GABench also provides 84 executable tools for accessing graph data and performing diverse graph operations.

Paper summary: Tom: So we're diving into GABench today, which is this new comprehensive benchmark for evaluating how well large language model agents can handle graph analysis tasks. Jane, can you give us the quick rundown on what this paper is all about?

Jane: Absolutely. Essentially, LLMs are becoming agents that can plan and use tools to interact with external environments, right? And graphs are a really promising area to test that because analyzing them requires agents to actually access data and perform operations in a graph structure. But the problem is, existing benchmarks for LLMs on graphs don't cover enough different tasks or graph types.

Tom: Right, so they mostly focus on things like simple retrieval or basic graph theory, and they usually just give the LLM text about the graph to answer a question directly. That limits how much we really learn about what an agent can *do* end-to-end.

Lu: Exactly. The authors point out that existing benchmarks are limited in their coverage of both the types of graphs and the tasks, which makes it hard to fully evaluate agent capabilities. They also note that they don't test agents interacting with executable graph tools, which is a big part of being an agent right now.

Meng: From a production standpoint, if we're building these systems, we need to know if the model can actually chain together those tool calls correctly to solve a multi-step problem instead of just hallucinating an answer from the prompt.

Lalam: I see what they are trying to do here. GABench aims to address that gap by providing a much broader testbed for agentic graph analysis. It covers four main task categories: graph retrieval, graph theory, graph machine learning, and open-ended question answering.

Tom: And what's the scale of this effort? How big is this benchmark compared to what we have now?

Jane: The paper says they built GABench on thirteen real-world datasets spanning six different domains and three distinct graph types: NAGs, TAGs, and TPGs. These datasets range from twenty-six to more than three point seven million nodes and contain up to one hundred twenty-three point six million edges.

Lu: That's a massive amount of data variety they are working with. They categorize the datasets based on the attributes they have, like having numerical attributes or textual attributes, which is important for testing how robust the agent is across different data structures.

Meng: And to make this work for agents, they included eighty-four executable tools. That's a lot of tool complexity we're talking about here—ten tools for retrieval, fifty-four for theory alone. How do you think that affects the cost or complexity of training an agent?

Tom: Well, the authors found that success in graph analysis actually depends more on how good those individual tool calls are than just how many tools the agent tries to use. It’s about quality over sheer quantity of calls.

Paper summary: Jane: That makes sense. So, even if an agent has access to a hundred tools, if it keeps calling the wrong one or making bad queries, it won't solve the problem correctly.

Lu: The paper also found that agents still struggle with certain complex tasks, specifically graph machine learning and open-ended question answering, with success rates often below forty percent in most cases. That tells us where the current agentic capabilities are hitting a wall.

Meng: And token efficiency? I'm always worried about context management and running costs. The paper noted that token consumption varies a lot across different models when using the same harness, and different harnesses introduce significant overhead in managing context.

Lalam: They specifically pointed out that graph machine learning and open-ended question answering tasks tend to have higher token costs compared to graph retrieval or graph theory tasks. This means we need to be mindful of which agentic workflows we're designing for deployment.

Tom: The harness choice also matters a lot here. Claude Code, for instance, was found to consume the fewest input tokens on both the machine learning and open-ended question answering tasks compared to other setups mentioned in the paper.

Jane: That’s a very concrete finding. It suggests that designing these agent harnesses needs to be really focused on efficiency, especially when dealing with those more complex analysis tasks where we see lower success rates.

Lu: So, what does this mean for the future of building better graph analysis agents? The paper is pushing toward a unified testbed and practical guidance for both LLMs and the specific agent harnesses needed for graphs.

Meng: It sounds like they are providing a unified way to compare performance across different graph types and task categories using these verifiable ground truths they generated. That should help us move past just testing models on text prompts.

Lalam: GABench is positioned as that testbed, covering everything from node classification in machine learning to scenario-based questions in open-ended analysis, giving us a clearer picture of agentic capabilities on graphs.

Tom: Overall, it seems the main message is that while agents are getting better at planning and tool use, they still need more rigorous testing against complex graph tasks that require deep interaction with executable environments.

Jane: And the authors are providing a practical way to measure this by creating ten thousand four hundred tasks with verifiable ground truth, which should give developers much more concrete feedback than just seeing a high score on a text question <ref:2608.01684#pg2>.

Lu: I think the implication is that we need to focus our research not just on making the underlying LLMs smarter, but also on designing better agent harnesses and task generation pipelines tailored for graph environments.

Meng: If we're deploying these agents, understanding those token costs and harness efficiencies mentioned in GABench is critical for managing operational expenses at scale.

Lalam: So to sum up, GABench gives us a unified testbed that shows where agents still struggle, highlights the impact of tool quality versus quantity, and points toward more efficient agent designs for graph work.

Conclusion: Tom: So we're wrapping up our look at GABench, which is this new benchmark for testing how well large language model agents handle graph analysis tasks.

Jane: Right, it’s a comprehensive testbed that puts LLM agents through four major categories of graph work.

Lu: It covers everything from finding specific data in a graph to predicting things about the whole structure or answering open-ended questions about it.

Meng: The authors built this on thirteen real-world datasets across six domains and three different types of graphs, covering nodes, edges, and graphs with different kinds of attributes.

Lalam: The main point is that we have to move beyond just text questions and see if the agent can actually plan a multi-step process using executable tools in a graph environment.

Tom: They found that existing agents still struggle with the harder tasks like machine learning and those open-ended questions, often only succeeding in under forty percent of cases.

Jane: And they also highlighted that tool quality matters way more than just the sheer quantity of tools an agent tries to use for success.

Lu: Plus, there's a big discussion around how different agent harnesses affect the token usage and context management when dealing with these graph tasks.

Meng: Claude Code was actually found to be quite efficient in terms of input tokens on those complex tasks compared to other setups they tested.

Lalam: So essentially, GABench gives us a unified way to test agents against real-world graph data and shows us exactly where the current agentic capabilities are falling short.

Tom: It’s a lot of practical guidance for anyone trying to build these things right now, whether you're training a model or designing an agent harness.

Jane: It really changes how we think about testing agents on complex data structures like graphs in a way that’s much more concrete than just looking at simple text answers.

Beijing University of Posts and Telecommunications · The Chinese University of Hong Kong · Peking University

cs.AI

Submitted: 2026-08-03

Updated: 2026-11-06

Code: https://github.com/anthropics/claudecode

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 91/100

The gist: Large language model (LLM) agents are increasingly capable of planning, using tools, and interacting with external environments They are typically supported by harnesses…

Key concepts

LLM Agents
These are AI models enhanced to plan actions, use external tools, and interact with environments. They move beyond simple answers by translating a request into a sequence of steps: selecting tools, processing results, and making decisions. They require 'harnesses' to manage their state during this multi-step execution.
Graph Analysis
This involves using graphs—structures representing relationships between entities like social networks or citation maps—to extract insights. Tasks range from finding specific data (retrieval) and calculating structural properties (theory) to predicting new connections (machine learning). It tests an agent's ability to navigate and manipulate this structured data.
GABench
This is the proposed comprehensive benchmark for testing LLM agents on graph analysis. It unifies evaluation by spanning three graph types, four analysis categories, and 84 executable tools. This allows researchers to test end-to-end agentic capabilities rather than just text-based question answering.
Tool Trajectory
This is the sequence of specific tool calls an agent makes during a task execution. For GABench, this trajectory is constructed based on the required input-output dependencies for a given graph analysis problem. Evaluating this trajectory helps assess how effectively an agent plans and uses its tools to solve the problem autonomously.

Terminology

Summary

Large language model (LLM) agents are increasingly capable of planning, using tools, and interacting with external environments They are typically supported by harnesses, which manage state and coordinate multi-step execution Graph analysis provides a promising setting for evaluating their agentic capabilities, because it requires agents to access data and execute operations in a graph environment However, existing graph benchmarks for LLMs provide limited coverage of graph tasks and graph types, making it difficult to comprehensively evaluate LLM agents Moreover, they typically formulate graph analysis as text-based question answering, where graph information is directly provided in the prompt, limiting the evaluation of end-to-end agentic capabilities. p. 0 p. 0 To address these limitations, we introduce GABench, a comprehensive benchmark for agentic graph analysis. p. 0 p. 0

Benchmark Scope and Coverage

GABench spans three graph types and covers four graph analysis task categories: graph retrieval, graph theory, graph machine learning, and graph open-ended question answering. GABench also provides 84 executable tools for accessing graph data and performing diverse graph operations. p. 0 Building on these tools, we develop an agentic graph analysis task generation pipeline and construct 10,400 tasks with verifiable ground truth. p. 0

Key Findings from Evaluation

Our experiments reveal three key findings: (1) Existing LLM agents still struggle with complex graph analysis tasks (2) Harness choice significantly affects performance, yet existing harnesses remain limited on complex graph tasks (3) Graph analysis depends more on tool-call quality than quantity.

Methodology and Pipeline

We propose a graph analysis question generation pipeline that combines template-based and LLM-based generation methods, producing 10,400 agentic questions grounded in real-world graph data. To construct a ground-truth tool trajectory, we select the required tools and assign them to stages based on their input–output dependencies. p. 4 For graph open-ended questions, we use an LLM-based process that combines realistic scenarios and tool descriptions to generate them. p. 4

Performance Insights

We observe that agents still struggle with complex graph analysis tasks, particularly graph machine learning and graph open-ended question answering, with success rates below 40% in most cases. Furthermore, tool-call quality is more important than tool-call quantity for successful graph analysis. p. 1

Token Efficiency Analysis

Token consumption varies substantially across models under the same agent harness, and different harnesses introduce substantially different context-management overhead. Graph machine learning and open-ended question answering incur higher token costs than graph retrieval and graph theory. p. 0

Harness Impact

Agent harnesses differ substantially in input-token efficiency, with Claude Code consuming the fewest input tokens on both graph machine learning and graph open-ended question answering. Future work should therefore investigate more token-efficient agent designs, including compact intermediate-state representations, selective retention of tool observations, adaptive context pruning, and early termination of redundant tool calls. p. 7

Conclusion

Overall, GABench provides a unified testbed and practical guidance for developing more capable LLM agents and graph-specific agent harnesses.

--- Page 1 ---

GABench: A Comprehensive Benchmark for Evaluating LLM Agents on Graph Analysis Tasks

Jiarui Tan, Zhongjian Zhang, YaBo Guo et al.

Abstract

Large language model (LLM) agents are increasingly capable of planning, using tools, and interacting with external environments They are typically supported by harnesses, which manage state and coordinate multi-step execution. Graph analysis provides a promising setting for evaluating their agentic capabilities, because it requires agents to access data and execute operations in a graph environment However, existing graph benchmarks for LLMs provide limited coverage of graph tasks and graph types, making it difficult to comprehensively evaluate LLM agents. p. 0 Moreover, they typically formulate graph analysis as text-based question answering, where graph information is directly provided in the prompt, limiting the evaluation of end-to-end agentic capabilities. To address these limitations, we introduce GABench, a comprehensive benchmark for agentic graph analysis.

--- Page 2 ---

Jiarui Tan, Zhongjian Zhang, and YaBo Guo et al.

1 Introduction

Large language models (LLMs) have evolved from simple text generators into agents capable of reasoning, planning, using tools, and interacting with external environments [1, 8, 36, 53] These capabilities are typically supported by agent harnesses, which provide interfaces for tool invocation, state and memory management Unlike standard question answering, where a model generates an answer directly from a given context, an agentic task requires an LLM to translate a user request into an action sequence, select appropriate tools, process intermediate observations, and adjust subsequent decisions [12, 14, 47, 56]. As a representative agentic setting, data analysis tasks often require an LLM to access and preprocess raw data Accordingly, recent studies have developed data analysis benchmarks for evaluating LLM agents, attracting considerable attention and making this a timely research focus. p. 0

Problem Formulation

Graphs are widely used to model complex relationships among entities in real-world systems, such as social networks, e-commerce networks, and citation networks [5, 13, 51] Analyzing these graphs is essential for understanding complex systems, uncovering latent patterns, and supporting prediction and decision-making [2, 17, 39, 41, 48]. To further investigate the potential of LLMs for graph analysis, recent studies have developed a series of benchmarks that evaluate their capabilities across different graph tasks and graph types. p. 0

Existing Benchmark Limitations

As summarized in Table 1, most existing benchmarks focus on graph retrieval and graph theory [3, 31, 59, 61], while only a few cover graph machine learning [19, 57, 61]. Meanwhile, they primarily consider numerical-attribute and text-attributed graphs [19, 57, 59], with text-paired graphs receiving limited attention [45]. p. 0 In a nutshell, existing benchmarks remain limited in their coverage of both graph tasks and graph types, making it difficult to comprehensively evaluate the graph analysis capabilities of LLM agents. p. 0 More importantly, existing benchmarks are not designed to evaluate agents’ capabilities in graph analysis. p. 0 They typically formulate graph analysis as text-based question answering, where graph information is provided in the prompt and LLMs directly produce a final answer without interacting with graph tools. p. 0

Research Question

The above limitations raise a fundamental question: Can LLM agents autonomously solve diverse graph analysis tasks through planning, tool composition, and interaction with executable graph environments? Answering this question not only helps reveal the agentic capabilities of LLMs in graph environments, but also provides a new perspective on complex graph analysis tasks. p. 0

Proposed Solution

To this end, we propose GABench, a comprehensive benchmark for evaluating LLM agents on graph analysis tasks. GABench is built on 13 real-world graph datasets spanning 6 domains and 3 graph types, and covers 4 major task categories: graph retrieval, graph theory, graph machine learning, and graph open-ended question answering. p. 0 To support the construction of agentic graph analysis tasks at scale, GABench provides 84 executable tools for accessing graph data and performing diverse graph operations. p. 0

--- Page 3 ---

Jiarui Tan, Zhongjian Zhang, and YaBo Guo et al.

Table 1: Comparison of GABench with representative graph-oriented benchmarks in task coverage, supported graph types, agentic interaction, and reported graph-size range. p. 1

Benchmark Coverage Summary

GABench integrates multiple graph types, graph analysis tasks, executable tools, and agent–tool interactions within a unified evaluation framework. Specifically, GABench collects 13 real-world datasets from 6 domains and covers 3 different graph types: NAGs, TAGs, and TPGs. p. 2 p. 2 These datasets range from 26 to more than 3. p. 2 p. 27 million nodes and contain up to 123. p. 2 p. 26 million edges. p. 2 p. 2 GABench further covers 4 common graph analysis categories: graph retrieval, graph theory, graph machine learning, and graph open-ended question answering. p. 2 p. 2

Task Selection Details

Graph retrieval tasks aim to access explicit information stored in a graph, such as node attributes, local neighborhoods, and graph statistics. Graph theory tasks aim to compute structural properties using deterministic graph algorithms. p. 3 Graph machine learning tasks aim to predict unknown labels, links, or graph properties using graph topology, attributes, and available supervision. p. 3 Graph open-ended question answering tasks aim to answer scenario-based questions with free-form responses. p. 3

Tool Set Details

GABench provides a unified toolset of 84 tools, including 10 for graph retrieval, 54 for graph theory, 10 for graph machine learning, and 10 for open-ended graph question answering. The task-specific toolset contains 84 tools. p. 3

Task Categories Breakdown

Graph retrieval tasks include node-, edge-, and graph-level retrieval tasks. Graph theory tasks include node-, edge-, and graph-level graph theory tasks. p. 3 Graph machine learning tasks include three common prediction tasks: node classification, link prediction, and graph classification. p. 2 Graph open-ended question answering tasks include graph insight and graph prediction tasks. p. 2

--- Page 4 ---

Jiarui Tan, Zhongjian Zhang, and YaBo Guo et al.

3 Benchmark

3.1 Overview and Statistics

To comprehensively evaluate the planning, tool-use, and end-to-end problem-solving capabilities of LLM agents on realistic graph analysis tasks, we propose GABench. As illustrated in Figure 1, GABench integrates multiple graph types, graph analysis tasks, executable tools, and agent–tool interactions within a unified evaluation framework. p. 2 Specifically, GABench collects 13 real-world datasets from 6 domains and covers 3 different graph types: NAGs, TAGs, and TPGs. These datasets range from 26 to more than 3.7 million nodes and contain up to 123.6 million edges. GABench further covers 4 common graph analysis categories: graph retrieval, graph theory, graph machine learning, and graph open-ended question answering. Based on these datasets and tasks, GABench provides a unified toolset of 84 tools. p. 2

Raw Data Collection Criteria

To ensure a comprehensive evaluation across diverse real-world applications, we consider four key criteria when selecting datasets for GABench: (1) Various graph types, (2) Various domains, (3) Diverse scales and densities, and (4) Tool compatibility and task coverage.

Dataset Categorization

Based on these criteria, GABench collects 13 datasets from 6 domains, as summarized in Table 9 and Table 1. These datasets are categorized into 3 graph types: (1) For NAGs with node-level numerical attributes, we choose Pokec and NBA from the social domain, DGraph-Fin and Credit from the finance domain, and Bail from the justice domain. p. 2 (2) For TAGs with node-level textual attributes, we choose Arxiv and Cora from the academic citation domain, Reddit and Instagram from the social domain, History and Product from the e-commerce domain. p. 2 (3) For TPGs with graph-level textual information, we choose HIV and PCBA from the molecular domain. p. 2

GABench provides a unified toolset of 84 tools, including 10 for graph retrieval, 54 for graph theory, 10 for graph machine learning, and 10 for open-ended graph question answering.

Graph Analysis Tool Set Details

Here, GABench provides a unified toolset that covers graph data access and four categories of graph tasks. Specifically, the graph retrieval tools allow agents to query node attributes, check edge existence, extract subgraphs, and count nodes or edges. p. 3 The graph theory tools cover both local and global structural analysis, including centrality and clustering coefficients. p. 3 The graph machine learning tools support node classification and link prediction on NAGs and TAGs, as well as graph classification on TPGs. p. 3

Agentic Task Generation Pipeline

In this subsection, we present the overall design of our agentic graph task generation pipeline, including the construction of executable tool trajectories, verifiable answers, and corresponding user questions. For each target task, the pipeline first selects and executes the required tools to construct a ground-truth tool trajectory and answer. p. 3

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improve agent planning by developing a graph analysis question generation pipeline that combines template-based and LLM-based generation methods, which grounds user requests in real-world graph data to create 10,400 agentic questions with verifiable ground truth. This allows agents to solve complex tasks through a cascading storytelling narrative where each step naturally sets up the next.

  2. Enhance tool selection accuracy by implementing rule-based question generation for graph retrieval and theory, while using an LLM-based process for open-ended questions that combines realistic scenarios and tool descriptions. This ensures the agent selects tools correctly based on the required analysis steps to construct a groundtruth tool trajectory.

  3. Improve performance on complex tasks like graph machine learning and open-ended question answering by developing graph specific agent harnesses, as existing general harnesses are insufficient for these challenges. This will allow agents to better handle the multi-step nature of these tasks through specialized tool invocation and state management.

  4. Optimize tool use efficiency by prioritizing tool-call quality over quantity in the agent's decision-making process rather than simply expanding the toolset or increasing the call budget. This directs agents to focus on graph-tool routing, parameter validation, and trajectory-level execution strategies.

  5. Increase context management efficiency by developing more token efficient agent designs, including compact intermediate-state representations and adaptive context pruning. This reduces the high input token consumption observed in many models when performing graph analysis.

Sources

Related papers