GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs

• URL: http://arxiv.org/abs/2609.12265v1
• Date: Thu, 10 Sep 2026 22:50:10 GMT
• Title: GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs
• Abstract summary: Graph Theory Bench (GT Bench) is a benchmark covering 24 classical graph problems in 44 task-structure settings.<n>GT Bench shows that accuracy is strongly tied to the input representation.<n>We propose the Graph Theory Agent (GTA), which pairs a preference-trained representation selector with plan-and-decompose scaffolding.
• Score: 50.68372832207766
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large Language Models (LLMs) are increasingly asked to reason over structured data such as graphs, yet how reliably they can carry out multi-step graph algorithms in language remains unclear. Existing evaluations tend to use simple tasks on small graphs, to score code generation rather than reasoning over the graph itself, or to fix a single input format. We introduce Graph Theory Bench (GT Bench), a benchmark covering 24 classical graph problems in 44 task-structure settings, with over 100,000 examples across four representations: natural language, structured language, adjacency list, and adjacency matrix. Evaluating eight LLMs on GT Bench shows that accuracy is strongly tied to the input representation, that the best representation shifts with graph density, size, and topology as well as with the model, and that this sensitivity persists, attenuated, in the strongest reasoning models. Building on these observations, we propose the Graph Theory Agent (GTA), which pairs a preference-trained representation selector with plan-and-decompose scaffolding around a frozen executor LLM. GTA lifts Phi-4 from 53.5% to 69.1% on the benchmark's easy split and from 33.0% to 41.5% on its hard split, outperforming eight prompting and agent baselines, and transfers without retraining to GraCoRe and NLGraph. Code for benchmark generation and evaluation: https://github.com/xzx34/GTA. The project homepage is available at https://xzx34.github.io/gta/.

Related papers

• ClosureBench: A Constructive Benchmark for Compositional Graph Reasoning [1.827510863075184]
  ClosureBench is a constructive benchmark for graph-relational reasoning with.<n> verified ground truth.<n>We evaluate models from 1.5B open weights to frontier systems.
  arXiv  Detail & Related papers  (2026-08-18T18:36:21Z)
• GraphCogent: Mitigating LLMs' Working Memory Constraints via Multi-Agent Collaboration in Complex Graph Understanding [13.356521655409422]
  Large language models (LLMs) show promising performance on small-scale graph reasoning tasks but fail when handling real-world graphs with complex queries.<n>We propose GraphCogent, a collaborative agent framework that decomposes graph reasoning into specialized cognitive processes: sense, buffer, and execute.
  arXiv  Detail & Related papers  (2025-08-17T14:28:38Z)
• An Automatic Graph Construction Framework based on Large Language Models for Recommendation [49.51799417575638]
  We introduce AutoGraph, an automatic graph construction framework based on large language models for recommendation.<n>LLMs infer the user preference and item knowledge, which is encoded as semantic vectors.<n>Latent factors are incorporated as extra nodes to link the user/item nodes, resulting in a graph with in-depth global-view semantics.
  arXiv  Detail & Related papers  (2024-12-24T07:51:29Z)
• What Do LLMs Need to Understand Graphs: A Survey of Parametric Representation of Graphs [69.48708136448694]
  Large language models (LLMs) are reorganizing in the AI community for their expected reasoning and inference abilities.<n>We believe this kind of parametric representation of graphs, graph laws, can be a solution for making LLMs understand graph data as the input.
  arXiv  Detail & Related papers  (2024-10-16T00:01:31Z)
• Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models [70.03602551880526]
  We introduce ProGraph, a benchmark for large language models (LLMs) to process graphs.<n>Our findings reveal that the performance of current LLMs is unsatisfactory, with the best model achieving only 36% accuracy.<n>We propose LLM4Graph datasets, which include crawled documents and auto-generated codes based on 6 widely used graph libraries.
  arXiv  Detail & Related papers  (2024-09-29T11:38:45Z)
• GraphArena: Evaluating and Exploring Large Language Models on Graph Computation [38.65000765032749]
  GraphArena is a tool designed to evaluate Large Language Models (LLMs) on real-world graph problems.<n> Evaluation of over 10 LLMs reveals that even top-performing LLMs struggle with larger, more complex graph problems.<n>We explore four potential solutions to address this issue, including chain-of-thought prompting, instruction tuning, code writing, and scaling test-time compute.
  arXiv  Detail & Related papers  (2024-06-29T09:19:23Z)
• GraphEval36K: Benchmarking Coding and Reasoning Capabilities of Large Language Models on Graph Datasets [19.329274124787858]
  GraphEval36K is the first comprehensive graph dataset, comprising 40 graph coding problems and 36,900 test cases.<n>Our dataset is categorized into eight primary and four sub-categories to ensure a thorough evaluation across different types of graphs.<n>To improve the usability of our evaluation framework, we propose Structured Symbolic Decomposition (SSD)<n>SSD improves the average passing rate of GPT-4, GPT-4o, Gemini-Pro and Claude-3-Sonnet by 8.38%, 6.78%, 29.28% and 25.28%, respectively.
  arXiv  Detail & Related papers  (2024-06-23T18:01:56Z)
• Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs [60.71360240206726]
  Large language models (LLMs) suffer from hallucinations, especially on knowledge-intensive tasks. Existing works propose to augment LLMs with individual text units retrieved from external knowledge corpora. We propose a framework called Graph Chain-of-thought (Graph-CoT) to augment LLMs with graphs by encouraging LLMs to reason on the graph iteratively.
  arXiv  Detail & Related papers  (2024-04-10T15:41:53Z)
• Can Language Models Solve Graph Problems in Natural Language? [51.28850846990929]
  Large language models (LLMs) are increasingly adopted for a variety of tasks with implicit graphical structures. We propose NLGraph, a benchmark of graph-based problem solving simulating in natural language.
  arXiv  Detail & Related papers  (2023-05-17T08:29:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.