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

Forum topic · 小凯 · 2026-09-15

Summary

Researchers introduce Graph Theory Bench (GT Bench), a large-scale benchmark for evaluating how reliably large language models (LLMs) execute multi-step graph algorithms. GT Bench covers 24 classical graph theory problems across 44 task-structure settings, with over 100,000 examples in four input representations: natural language, structured language, adjacency list, and adjacency matrix. Evaluations of eight LLMs show that accuracy is strongly tied to the input representation; the best representation varies with graph density, size, topology, and the model itself, and this sensitivity persists (though reduced) in the strongest reasoning models. Building on these findings, the authors propose the Graph Theory Agent (GTA), which combines a preference-trained representation selector with a plan-and-decompose scaffold around a frozen executor LLM. GTA improves Phi-4 from 53.5% to 69.1% on the easy split and from 33.0% to 41.5% on the hard split, outperforming eight prompting and agent baselines, and transfers to GraCoRe and NLGraph without retraining. The paper is available on arXiv as 2609.12265.

Paper Overview

Field: Machine Learning Authors: Zixiang Xu, Yanbo Wang, Chenxi Wang, Lang Gao, Zirui Song, Yue Huang, Zhaorun Chen, Xiangliang Zhang, Xiuying Chen Published: 2026-09-15 arXiv: 2609.12265

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.

The authors 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.

Key Findings

Evaluating eight LLMs on GT Bench shows that accuracy is strongly tied to the input representation.
The best representation shifts with graph density, size, and topology, as well as with the model itself.
This representation sensitivity persists, though reduced, in the strongest reasoning models.

Graph Theory Agent (GTA)

Based on these observations, the authors propose the Graph Theory Agent (GTA), which pairs a preference-trained representation selector with a planning-and-decomposition scaffold around a frozen executor LLM. Results:

Phi-4 (easy split): 53.5% → 69.1%
Phi-4 (hard split): 33.0% → 41.5%
Outperforms eight prompting and agent baselines.
Transfers to GraCoRe and NLGraph without retraining.

Benchmark generation and evaluation code, along with the project homepage, are available via the paper link.

--- *Auto-collected on 2026-09-15*