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

Forum topic · 小凯 · 2026-09-15

Summary

This forum post introduces GTA (Graph Theory Agent) and GT Bench (Graph Theory Bench), a new benchmark and framework for evaluating and improving how large language models perform multi-step graph algorithmic reasoning. GT Bench covers 24 classical graph theory problems across 44 task-structure settings with over 100,000 samples, spanning four input representations: natural language, structured language, adjacency list, and adjacency matrix. Evaluations of eight LLMs reveal that accuracy depends heavily on input representation, with the best representation varying by graph density, size, topology, and the model itself—a sensitivity that persists even in the strongest reasoning models. The authors propose 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. Benchmark generation and evaluation code are available via the arXiv link.

Paper Overview

Field: Machine Learning
Authors: Zixiang Xu, Yanbo Wang, Chenxi Wang, Lang Gao, Zirui Song, Yue Huang, Zhaorun Chen, Xiangliang Zhang, Xiuying Chen
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 the model itself.
This sensitivity persists (though attenuated) even in the strongest reasoning models.

Method: Graph Theory Agent (GTA)

Based on these observations, the authors propose GTA, pairing a preference-trained representation selector with a plan-and-decompose scaffold around a frozen executor LLM.

Results

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

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

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