GABench: A Comprehensive Benchmark for Evaluating LLM Agents on Graph Analysis Tasks
2026-08-03 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors created GABench, a new and detailed test to see how well large language models (LLMs) can work with graphs, which are networks of connected points. Unlike older tests, GABench uses real graph data and tools, making the tasks more realistic and varied. They tested several top LLMs and found that these models still have trouble with hard graph problems, that the software organizing the models' work (harnesses) matters a lot, and that doing tool actions well is more important than having many tools. Their work helps understand how to better build and test LLMs for working with graphs.
Large Language ModelsGraph AnalysisAgent HarnessGraph BenchmarkGraph RetrievalGraph TheoryGraph Machine LearningTool-Call QualityMulti-step ExecutionAgentic Capabilities
Authors
Jiarui Tan, Zhongjian Zhang, YaBo Guo, Jiawei Liu, Yujie Xing, Muhan Zhang, Cheng Yang, Chuan Shi
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. 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. 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. Building on these tools, we develop an agentic graph analysis task generation pipeline and construct 10,400 tasks with verifiable ground truth.Using GABench, we evaluate a range of frontier LLMs and agent harnesses. 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. Our findings provide practical insights into the development and evaluation of LLM agents for graph analysis.