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

AI summary

Overview

Research area: LLM reasoning over structured data (graph theory and combinatorial algorithms), benchmark design, and agent frameworks for multi-step reasoning.

Technical level: Intermediate. Readers should be comfortable with basic graph theory (vertices, edges, connectivity, spanning trees, max flow) and with standard LLM concepts like prompting, chain-of-thought, and fine-tuning. The paper is self-contained enough for newcomers who know what an adjacency matrix is.

Scope: This paper introduces a large, controlled benchmark for language-only graph algorithm reasoning and an agent that adaptively picks the graph's textual encoding before decomposing the problem into sub-steps.

What This Paper Is About

Large Language Models are increasingly deployed on graph-structured data, yet existing benchmarks mostly test simple tasks on tiny graphs, score generated code rather than the model's own reasoning, or lock in a single input format. This paper asks two questions: how reliably can LLMs carry out multi-step graph algorithms purely in language, and can that reliability be improved without changing the model weights? To answer them, the authors build GT Bench (a benchmark spanning 24 classical graph problems in four equivalent encodings) and GTA (an agent that selects the best encoding per instance and decomposes the problem into a plan).

Key Contributions

1. GT Bench, a benchmark of 24 classical graph problems across 44 task–structure settings and 105,600 encoded examples, each instance rendered in four equivalent representations: natural language (NL), structured language (SL), adjacency list (AL), and adjacency matrix (AM). Problems span connectivity checks up to min-cost max-flow, and include NP-hard and NP-complete tasks. Data is generated automatically with algorithmically computed ground truth, stratified into easy (GT-E) and hard (GT-H) splits.

2. An empirical characterization of representation sensitivity, showing that accuracy swings by up to roughly 30 points on a single task depending on format, that the winning format depends jointly on task, graph density, size, and topology, and that the effect is largest in capable-but-unsaturated models and shrinks but does not disappear in the strongest reasoners.

3. The Graph Theory Agent (GTA), a framework that pairs a preference-trained representation selector with plan-and-decompose scaffolding around a frozen executor LLM, improving accuracy on GT Bench and transferring without retraining to GraCoRe and NLGraph.

4. Evidence that graph algorithm reasoning is a distinct capability axis, diverging from general language leaderboard performance and aligning instead with coding and math ability.

Main Findings

• No single representation wins across models. Llama-3.1-8B prefers adjacency matrices (29.4%), Phi-4 prefers structured language (44.9%), GPT-4o peaks with adjacency lists (47.6%), and DeepSeek-R1 prefers adjacency matrices (82.5%). Fixing one format for all models flatters some and shortchanges others.

• Format choice tracks graph structure. Natural language suits sparse graphs, where little structural parsing is needed; structured language dominates on trees because its templated indentation mirrors hierarchy; adjacency matrices win on dense graphs because all pairwise connections are visible at once; adjacency lists are strongest for pathfinding and neighbor-iteration tasks at any density.

• The effect is large on individual tasks. Connectivity on sparse graphs ranges from 60.5% to 89.1% across the four formats. Averaged across models, Bipartite Check spans 14.0 points and Tree Centroid 18.3 points.

• Sensitivity peaks in mid-capability models. The best-minus-worst format gap is 2.0 points for Llama-3.1-8B (near floor everywhere), widens to 9.2 points for QwQ-32B, then narrows to 2.8 for o3-mini and 1.9 for DeepSeek-R1. It attenuates but does not vanish at the frontier.

• Supplying all four representations at once backfires. Concatenating formats drops GPT-4o from 47.6% to 40.3%, inflating the prompt three to four times and introducing conflicting structural cues the model must reconcile.

• Difficulty sharply separates models, and it reorders them. Every model drops steeply from GT-E to GT-H: QwQ-32B falls 47 points (85.62% to 38.46%). GPT-4o beats Llama-3.3-70B on easy instances (60.54% vs 58.19%) but trails on hard ones (28.94% vs 30.40%), so rankings from easy tasks alone can mislead.

• Graph reasoning is not general language ability. QwQ-32B has the lowest Instruction Following (1149) and Longer Query (1176) Elo scores of the set, below the 8B Llama model, yet ranks third on GT-H. The GT-H leaders (o3-mini, DeepSeek-R1, QwQ-32B) consistently lead in Coding and MATH, suggesting graph reasoning shares machinery with formal multi-step execution rather than with natural language understanding.

• GTA improves a frozen executor. Phi-4 rises from 53.5% to 69.1% on GT-E and from 33.0% to 41.5% on GT-H, beating eight prompting and agent baselines and transferring to GraCoRe and NLGraph without retraining. Decomposition alone adds 7.0 points on GT-E over a selector-only configuration.

Methodology in Plain English

The authors separated measurement from intervention.

Measurement. They built a parameterized generator that produces graphs of controlled density (sparse, dense, tree), size, and weighting, sized so every instance fits inside a modern context window while still requiring real multi-step reasoning rather than lookup. For each of 24 problems, canonical algorithms compute the ground truth, so no human labeling is needed. Every instance is serialized four ways, and the same graph and question is posed in each. Eight LLMs are then evaluated under all four encodings at temperature 0.01 to isolate the effect of format from the effect of the task itself.

Intervention. GTA keeps the executor LLM frozen and adds two lightweight components around it: a selector trained with preference-style supervision to choose the encoding best matched to the current instance, and a plan–decompose–execute scaffold that breaks the algorithm into dependent sub-steps. Because only the auxiliary components are trained, any gain reflects better representation and decomposition choices rather than extra model capacity. Component ablations isolate how much each part contributes, and evaluation on GraCoRe and NLGraph tests whether the learned components transfer across task distributions.

Why This Matters

Impact on research. The paper reframes graph representation as a first-class variable rather than a fixed preprocessing detail. It gives benchmark designers a controlled testbed where the graph stays identical and only the encoding changes, and it establishes that graph algorithm reasoning is an axis of capability that general leaderboards do not measure. The frozen-executor framing also isolates reasoning improvements from capacity improvements, which is methodologically useful for the broader agent literature.

Real-world applications:

• Network and infrastructure analysis. Operational questions about server topology, citation networks, or social graphs are naturally phrased in language, and the right encoding varies with whether the graph is sparse, dense, or tree-shaped.
• Molecular and biological discovery. Molecules are graphs; the findings on density-dependent format choice inform how cheminformatics pipelines should prompt models.
• Logistics and route planning. Shortest path, spanning tree, and flow problems map directly onto delivery routing, capacity planning, and supply chain optimization.
• Knowledge graph question answering. Systems that traverse entity-relation structures can adopt adaptive encoding selection instead of committing to one serialization scheme.

Industry relevance. Companies deploying LLMs over structured data can gain measurable accuracy without retraining or swapping models, which matters when the executor is a costly proprietary API or a fixed on-premise deployment. The finding that concatenating all formats hurts is an immediate, actionable prompt-engineering lesson.

Future Directions

• Scale limits. Current graphs are deliberately prompt-sized. How these findings hold for graphs well beyond context windows, or for hybrid setups that combine textual encoding with tool calls, remains open.
• Learned decomposition. GTA's scaffolding is relatively fixed. Whether the plan-and-decompose structure itself can be learned or searched per task, as some recent workflow-optimization work attempts, is a natural extension.
• Beyond four encodings. The paper covers the four standard textual representations. Node relabeling, edge reordering, color-based encodings, and visual or multimodal graph renderings are not tested and may shift the sensitivity picture.
• Why sensitivity persists. The paper documents that strong reasoning models remain format-sensitive but does not explain the mechanism. Understanding whether this stems from tokenization, positional effects, or attention over serialized structure would inform both architecture and prompting design.

Target Audience

Researchers and practitioners working on LLM reasoning over structured data, benchmark construction, and agent design will get the most from this paper. It is also directly useful to applied engineers who prompt LLMs with graph or network data and want evidence-based guidance on format selection, and to graph-learning researchers interested in how language models handle combinatorial problems that graph neural networks traditionally address.

Authors’ 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/.