The research presented a new benchmark, Graph Theory Bench (GT Bench), designed to assess Large Language Models’ ability to perform multi-step graph algorithms. GT Bench comprises 24 classical graph problems across 44 task-structure settings, utilizing four representations: natural language, structured language, adjacency list, and adjacency matrix. The benchmark contains over 100,000 examples. Evaluations of eight LLMs on GT Bench revealed a strong correlation between accuracy and the input representation. The optimal representation varied based on graph density, size, and topology, and also differed across models.
Building on these observations, the research proposed the Graph Theory Agent (GTA). GTA integrates a preference-trained representation selector with a plan-and-decompose scaffolding system around a frozen executor LLM. The system utilizes Phi-4. GTA achieved a 69.1% accuracy on the benchmark’s easy split and a 41.5% accuracy on its hard split, outperforming eight prompting and agent baselines. The system transfers effectively to GraCoRe and NLGraph without retraining.
The GTA system's performance highlights the sensitivity of LLMs to input representation when reasoning about graphs. The benchmark and agent system provide a tool for evaluating and comparing LLMs on complex graph reasoning tasks. The project includes code for benchmark generation and evaluation, accessible at a specified URL.
Source: https://arxiv.org/abs/2609.12265
