PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zixiang Xu, Yanbo Wang, Chenxi Wang, Lang Gao, Zirui Song, Yue Huang, Zhaorun Chen, Xiangliang Zhang, Xiuying Chen

arXiv:2609.12265v1cs.AI

TL;DR

Reliable language-based graph reasoning remains unclear, and existing evaluations often use simple tasks, code generation, or a single input format. This paper introduces GT Bench and GTA; its evaluation finds representation-dependent accuracy, and GTA yields gains over prompting and agent baselines while transferring to other benchmarks.

  • Problem

    Existing evaluations often use simple graph tasks, score code generation rather than reasoning over the graph, or fix a single input format.

    Source: §1 · p. 2

  • Method

    The paper evaluates graph reasoning with GT Bench and pairs a preference-trained representation selector and plan-and-decompose scaffolding with a frozen executor.

    Source: §1 · p. 2, §7 · p. 20

  • Results

    Accuracy depends on representation, task, graph structure, and model, with sensitivity persisting in the strongest reasoning models; GTA yields consistent gains over prompting and agent baselines and transfers to unseen benchmarks.

    Source: §1 · p. 2, §7 · p. 20

  • Takeaways & Limitations

    The best representation varies with graph structure and model, supporting adaptive selection rather than reliance on one fixed format.

    Source: §1 · p. 2

    The static heuristic selector is an economical fallback that would need re-derivation outside its GT Bench coverage.

    Source: §5.1 · p. 13

Abstract

from arXiv · show

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

1 Introduction

The paper introduces GT Bench to evaluate multi-step algorithmic reasoning over graphs in language, then uses it to study representation sensitivity and motivate an adaptive agent. Its experiments find that performance depends on input format and graph structure, motivating representation selection and decomposition around a frozen executor.

1 Introduction

  • GT Bench covers 24 classical graph problems in 44 task–structure settings, with more than 100,000 examples across four representations.Its easy and hard subsets range from basic connectivity checks to minimum-cost maximum-flow.Source: §1 · p. 2
  • Connectivity accuracy on sparse graphs ranges from 60.5% to 89.1% across four formats, and the winning format varies with graph structure.The proposed Graph Theory Agent (GTA) responds with adaptive representation selection and solution decomposition around a frozen executor.Source: §1 · p. 2
  • Language-only evaluation tests whether a model can interpret a graph, maintain intermediate algorithmic state, and carry out dependent operations.Code-augmented evaluation additionally measures translating a problem into an executable algorithm and using its output.Source: §1 · p. 2
  • The paper’s contributions include characterizing representation sensitivity across tasks, graph structures, and models, and introducing GTA to select formats and decompose solutions.The executor remains frozen while lightweight auxiliary components handle representation selection and algorithmic decomposition.Source: §1 · p. 2

2 Related Work

Related work spans graph benchmarks, graph-oriented systems, and agent frameworks, but uses different tasks, representations, and execution protocols. GT Bench compares standard encodings for language-based algorithmic reasoning, while GTA combines adaptive representation selection and decomposition around a frozen executor.

2.1 LLMs and Graph Reasoning Benchmarks

  • Prior graph benchmarks and representation studies use varied tasks and protocols; GT Bench provides a controlled comparison of four encodings across 44 task–structure settings and eight models.GTA couples per-instance representation selection with plan–decompose–execute scaffolding.Source: §2.1 · pp. 3–4

2.2 Attempts to Solve Graph-Theoretic Problems with LLMs

  • Related graph systems address prediction, graph representation learning, or code execution, whereas GT Bench starts from an explicit graph and evaluates requested computations across equivalent encodings.GTA keeps a frozen executor and supplies algorithmic decomposition rather than relying on code execution.Source: §2.2 · pp. 4–5

2.3 LLM-Based Agent Frameworks

  • Agent frameworks vary in planning, workflow adaptation, and execution structure; GTA fixes its high-level workflow and learns representation choice and decomposition for graph tasks.Its specified workflow permits component ablations and transfer evaluation on benchmarks with different task distributions.Source: §2.3 · pp. 6–7

3 GT Bench: Graph Theory Benchmark

GT Bench is designed to evaluate multi-step inference across graph structures and classical graph-theoretic problems. It varies graph characteristics and presents each instance in four input modalities, with task coverage and graph sizes calibrated for reasoning within contemporary LLM context windows.

3.1 Graph Characteristics

  • Graphs are categorized as sparse, dense, or trees, with task-dependent choices such as weighted or unweighted edges and connected or disconnected graphs.Trees are connected graphs with E = V −1; star graphs also arise among the generated structures.Source: §3.1 · p. 7

3.2 Input Representations

  • Every problem instance is provided in natural language, structured language, adjacency matrix, and adjacency list formats.These encodings describe vertices, edges, and applicable weights in prose, templates, matrix entries, or neighbor lists.Source: §3.2 · p. 7

3.3 Task Coverage and Dataset Composition

  • GT Bench covers 24 classical graph problems in 44 task–structure settings, with node ranges calibrated so instances fit contemporary LLM context windows.Twenty problem types use sparse and dense graphs, while four are tree-specific; dense families have tighter size ranges because edge counts grow quadratically.Source: §3.3 · p. 7
  • The dataset comprises 105,600 examples across four representations, stratified into easy and hard subsets.Table 2 details node counts and instance numbers by problem type.Source: Figure 1 · p. 8
  • Dataset generation and verification are automated, with ground truths derived using canonical algorithms specific to each task.The generation process can adjust graph scales to create new instances.Source: §3.3 · p. 8

4 Benchmarking LLMs on GT Bench

Across eight evaluated LLMs, graph-reasoning accuracy depends on representation, task, graph structure, and model, and performance drops on harder instances. The section also finds that concatenating every representation degrades accuracy and that graph reasoning does not simply track general language capabilities.

4 Benchmarking LLMs on GT Bench

  • The evaluation covers eight LLMs, with each tested on 10,000 instances across four representations in one inference run per configuration at temperature 0.01.The models include three proprietary and five open-source systems.Source: §4 · p. 8

4.1 Representation Sensitivity

  • 89.9% NL leads sparse Bipartite Check, 38.6% AM dense Maximum Clique, 60.8% SL Tree Centroid, and 88.3% AL dense Hamiltonian Circuit.These selected task results illustrate that the best representation varies with task and graph structure.Source: §4.1 · p. 10, Table 3 · p. 10
  • NL suits sparse graphs, SL trees, AM dense graphs, and AL pathfinding or neighbor-iteration tasks at any density.The paper links these patterns to each encoding’s presentation of graph structure for the relevant task.Source: §4.1 · p. 10
  • The best-to-worst format gap is 2.0 points for Llama-3.1-8B, 6.1 for Phi-4, 7.3 for GPT-4o-mini, 9.2 for QwQ-32B, 2.8 for o3-mini, and 1.9 for DeepSeek-R1.Sensitivity shrinks but remains present in the strongest reasoning models.Source: §4.1 · p. 10, Table 4 · p. 10

4.2 Performance across Difficulty Levels

  • All eight models drop sharply on Hard; GPT-4o leads Llama-3.3-70B on Easy (60.54% versus 58.19%) but trails on Hard (28.94% versus 30.40%).Even the strongest reasoning models remain well below ceiling on the Hard split.Source: §4.2 · pp. 10–11, Table 5 · p. 11

4.3 Does Providing Every Representation Help?

  • GPT-4o accuracy falls from 47.6% with its best single representation to 40.3% when all four are concatenated.The authors attribute the degradation to longer prompts and structural diversity that the model must reconcile.Source: §4.3 · p. 11, Table 6 · p. 11

4.4 Relationship to General Capabilities

  • GT-H performance diverges from general language ratings: top GT-H models also lead Coding and MATH, while smaller reasoning-optimized models outperform larger generalists.The authors conclude GT Bench probes a capability axis not captured by general leaderboards.Source: §4.4 · p. 11, Table 7 · p. 12

5 Graph Theory Agent Framework

GTA addresses representation sensitivity and multi-step failures by selecting an input format and decomposing a planned solution while keeping the executor frozen. Its pipeline moves from representation choice through planning and substeps to executor output.

5 Graph Theory Agent Framework

  • GTA combines per-instance representation selection and solution decomposition around a frozen executor, optimizing only lightweight Selector and Decomposer modules.The base LLM is not trained or fine-tuned on GT Bench data.Source: §5 · p. 12

5.1 Input Representation Selector

  • The Selector chooses among NL, SL, AM, and AL for each graph-task instance; its learned form is fine-tuned for a target executor using historical outcomes.It is most advantageous when executor preferences depart from general trends or graph structure is ambiguous.Source: §5.1 · pp. 12–13
  • The heuristic selector maps graph and task characteristics to formats with the strongest average performance, but needs re-derivation outside GT Bench coverage.Its primary advantage is computational efficiency.Source: §5.1 · pp. 12–13

5.2 Algorithm Generator

  • An off-the-shelf LLM generates a high-level strategic plan from the task and selected graph representation, without producing detailed instructions or executable code.This abstract plan-generation stage is not task-specifically fine-tuned.Source: §5.2 · p. 13

5.3 Algorithm Decomposer

  • The Decomposer turns the abstract strategy into concise, manageable natural-language substeps for sequential processing by the Executor.It is implemented as a dedicated LLM.Source: §5.3 · p. 13

5.4 Training and Execution Workflow

  • The Decomposer is first fine-tuned on expert-like decompositions distilled from a stronger model, then preference-optimized using decompositions whose execution succeeds or fails.The preference pairs are labeled by whether the Executor reaches a correct solution.Source: §5.4 · pp. 13–14
  • The Learned Selector is trained with preference pairs from running the full pipeline on all four representations, then chooses an input format at inference.The pairs distinguish representations leading to correct solutions from those leading to incorrect ones.Source: §5.4 · p. 14

6 Evaluating GTA

The evaluation compares GTA and baselines using Phi-4 as a frozen executor, then examines component contributions, transfer, scalability, cost, and failure modes. GTA leads the benchmark comparison, while ablations and deployment analyses characterize its gains and boundaries.

6.2 Comparative Performance of GTA

  • Trained solely on GT Bench, GTA reaches 80.5% accuracy on GraCoRe and 89.4% on NLGraph, benchmarks whose task distributions are not subsets of GT Bench, indicating transfer rather than overfitting.Source: §6.2 · p. 15

6.3 Ablation Study of GTA Components

  • Removing the selector lowers GT-E accuracy from 69.1% to 58.2%, while replacing it with the heuristic costs 4.6 points and removing planning and decomposition costs 7.0 points.The same configuration ordering holds on GT-H, GraCoRe, and NLGraph.Source: §6.3 · p. 15, Table 9 · p. 15
  • Removing the Decomposer costs 4.8 GT-E points versus 2.3 for removing the Generator, while removing both costs 7.0 points, close to the sum of individual drops.The Decomposer supplies actionable step-level signal; the Generator contributes a complementary high-level algorithmic frame.Source: §6.3 · p. 16, Table 10 · p. 16

6.4 SFT–DPO Training Dynamics of the Learned Components

  • SFT establishes a cross-task, cross-modality foundation and DPO optimizes task success; SFT+DPO outperforms SFT-only, and the learned selector outperforms the heuristic variant.DPO-trained Decomposers also improve over Vanilla under both training-time selector policies.Source: §6.4 · pp. 16–17

6.5 Scalability Analysis with Increasing Graph Size

  • On GT-E, GTA stays comparatively flat as graphs grow while Phi-4 and GPT-4o-mini decline; on GT-H, GTA also declines, but less steeply than its base model.GTA remains ahead of Phi-4 at every tested hard-graph size, but QwQ-32B degrades more gently than GTA on GT-H.Source: §6.5 · p. 17, Figure 2 · p. 18

6.6 Generality across Executor Models

  • With Phi-4-trained components, GTA improves GPT-4o from 60.5% to 68.8% on GT-E and from 28.9% to 36.9% on GT-H; DeepSeek-R1 gains 8.1 points on GT-H.DeepSeek-R1’s changes range from −0.2 to +0.1 points on GT-E, GraCoRe, and NLGraph, where it is near ceiling.Source: Table 14 · p. 18, §6.6 · p. 18

6.7 Inference Cost Analysis

  • GTA uses roughly 5–6× vanilla-prompting tokens and costs $1.11 per 600 instances, less than every evaluated method except MaAS and Vanilla prompting.Its one-time training and data-generation cost is roughly $92, which amortizes with inference volume.Source: Table 15 · p. 19, §6.7 · p. 19, Table 16 · p. 19

6.8 Failure-Mode and Truncation Analysis

  • Input overflow is 0.0% by design, output truncation is 1.2% overall and 2.1% on Hard, and answer-extraction failures are 0.8% overall.The reported accuracy differences are larger than truncation rates, including the 7.0-point GT-E gap between GTA-NoDec and full GTA.Source: Table 17 · p. 19, §6.8 · pp. 19–20

7 Conclusion

The paper introduces GT Bench to characterize language-based algorithmic graph reasoning and proposes GTA to improve it. GT Bench reveals representation sensitivity, while GTA combines adaptive representation selection with plan-and-decompose scaffolding around a frozen executor.

7 Conclusion

  • GT Bench covers 24 graph problems in 44 task–structure settings, with over 100,000 examples across four input representations.It is used to characterize how LLMs reason over graphs in language.Source: §7 · p. 20
  • Accuracy depends on input representation, task, graph structure, and model; this sensitivity persists, though attenuated, in the strongest reasoning models.Hard multi-step tasks remain far from solved by scale alone.Source: §7 · p. 20
  • GTA pairs a preference-trained Selector with a Generator–Decomposer that structures steps for a frozen executor, yielding gains over prompting and agent baselines at bounded cost.The conclusion also reports transfer to benchmarks and executors unseen in training and gentler accuracy degradation as graphs grow.Source: §7 · p. 20

A Task Definitions and Solution Algorithms in GT Bench

This section defines the graph-theoretic tasks in GT Bench and specifies canonical algorithms used to generate ground-truth solutions. The tasks span traversal, optimization, tree, and flow problems, with algorithms ranging from BFS and DFS to dynamic programming and brute-force search.

A Task Definitions and Solution Algorithms in GT Bench

  • Connectivity, bipartiteness, Eulerian path and circuit, and shortest-path tasks use BFS-based checks or traversals, with Dijkstra’s algorithm used for weighted non-negative shortest paths.Eulerian existence checks also use connectivity and vertex-degree conditions.Source: A Task Definitions and Solution… · pp. 33–34
  • Hamiltonian path and circuit, cycle counting, maximum clique, and maximum independent set use backtracking or enumeration; the latter two are NP-hard optimization problems.Cycle counting uses DFS-based backtracking on the small graphs specified for that task.Source: A Task Definitions and Solution… · pp. 33–34
  • Bridge and biconnected-component counts use DFS, while triangle counting checks vertex triples and spanning-tree counting uses Kirchhoff’s Matrix Tree Theorem.The bridge test compares low-link values with DFS discovery times.Source: A Task Definitions and Solution… · p. 34
  • Weighted spanning-tree tasks use Kruskal’s algorithm for MST weight and replace a suitable cycle edge to find the strictly heavier second-minimum spanning tree.Flow tasks use Edmonds–Karp for maximum flow and minimum cut, and successive shortest augmenting paths for minimum-cost maximum flow.Source: A Task Definitions and Solution… · pp. 34–35
  • Tree tasks use two BFS traversals for diameter, subtree sizes for centroid, parent pointers for LCA, and dynamic programming for maximum independent set.The tree maximum independent set answer is the larger root score for including or excluding the root.Source: A Task Definitions and Solution… · pp. 34–35

B Experimental Details

Appendix B describes the models, baseline configurations, and experimental setup. Baseline executors were standardized where stated to compare reasoning strategies rather than underlying model capabilities.

B.1 Models

  • Table 18 catalogs model versions, organizations, licenses, and study roles; direct model evaluations used zero-shot Vanilla prompting.The roles distinguish evaluation models from fine-tuning models.Source: §B.1 · p. 35, Table 18 · p. 36

B.2 Baselines

  • Baseline methods used Phi-4 as executor to isolate reasoning strategies from underlying model capabilities, while automated planners followed their original specifications.The standardized methods included Vanilla, CoT, LLM-Debate, Self-Refine, ADAS, AFlow, and MaAS.Source: §B.2 · p. 36
  • GraphTeam was evaluated without search, coding, tools, or external execution, so its gains reflect coordination or reasoning rather than tool use.GraphWiz-DPO was tested in its prescribed instruction format alongside Vanilla and GTA.Source: §B.2 · p. 36
  • Other graph systems use distinct task or execution interfaces, so the comparisons do not establish a general system ranking.The authors characterize GTA as improving through adaptive representation selection and plan–decompose–execute reasoning without modifying the executor or using code execution.Source: §B.2 · p. 36

B.3 Training and Evaluation Parameters

The appendix reports component-training data and settings, along with inference temperatures and evaluation sample sizes.

B.3 Training and Evaluation Parameters

  • The Algorithm Decomposer used 1,000 GPT-4o-distilled SFT instances and 2,000 preference pairs, with its decomposed subtask count capped at k=3.The authors observed higher overhead and lower overall GTA accuracy when k exceeded 3.Source: §B.3 · pp. 36–37
  • The Learned Selector received 1,000 SFT instances, followed by DPO pairs based on end-to-end GTA success across input representations..Source: §B.3 · p. 37
  • Fine-tuning used 2 epochs, a 5.0e-6 learning rate, cosine scheduling with 0.1 warmup, batch size 1, and accumulation over 8 steps.Training used bf16 precision on 2 NVIDIA A6000 GPUs for 40 hours; SFT data generation and DPO candidate sampling used temperature 1.0.Source: §B.3 · p. 37
  • Evaluation used temperature 0.01; direct GT Bench model assessments covered 10,000 instances per model, while each method was tested on 1,000 instances per dataset.The latter evaluations covered GT Bench, GraCoRe, and NLGraph.Source: §B.3 · p. 37

B.4 Evaluation Scope and Statistical Protocol

The evaluation scope is synthetic, domain-independent graph tasks, with controlled graph-size ranges and a statistical protocol that differs between broad sweeps and targeted analyses.

B.4 Evaluation Scope and Statistical Protocol

  • GT Bench uses synthetic, domain-independent instances that isolate structural reasoning, so its evaluation does not establish performance on domain-attributed graphs or application-specific knowledge.Transfer gains on GraCoRe and NLGraph are reported, but do not establish performance on social, molecular, or other application-specific knowledge.Source: §B.4 · p. 37
  • GT Bench instances range from 6 to 60 nodes, with ranges calibrated to prompt fit and algorithmic complexity; the best model reaches 75.1% on GT-H.Model-averaged accuracy remains below 1% under each representation on dense Min-Cost Max-Flow, and reported accuracy remains specific to evaluated size ranges.Source: §B.4 · p. 37
  • Representation-sweep scores come from one inference run per configuration, whereas targeted analyses are averaged over three runs with reported standard deviations.The single-run sweeps do not quantify run-to-run uncertainty for individual cells.Source: §B.4 · p. 37

C.1 Best-Performing Representation Per Task

Table 19 reports the best-performing input representation for each task–graph-type combination, based on average accuracy across evaluated models; these results informed GTA’s heuristic selector.

C.1 Best-Performing Representation Per Task

  • Dense graph cases often favor adjacency matrices, including Connectivity, Bipartite, and Maximum Flow, while some dense tasks favor adjacency lists.Dense Bridge Count, Hamiltonian Circuit, and Shortest Path are listed with adjacency lists rather than matrices.Source: §C.1 · p. 38, Table 19
  • Sparse graph cases show task-dependent winners: adjacency lists lead for Connectivity and Maximum Flow, while natural language leads for Maximum Clique and Minimum Cycle.Other sparse-task entries select structured language or adjacency matrices.Source: §C.1 · p. 38, Table 19
  • All listed tree tasks—Tree Centroid, Tree Diameter, Tree LCA, and Tree Max Independent Set—select structured language.Source: §C.1 · p. 38, Table 19

C.2 Task-Specific Performance Across Input Representations

Average accuracy across GT Bench’s task–structure settings shows that no input representation is universally optimal. The leading modality varies by task and graph type, with representation gaps often exceeding ten points.

C.2 Task-Specific Performance Across Input Representations

  • Natural Language leads on sparse Bipartite Check, Bridge Count, Minimum Cycle, Maximum Clique, and Triangle Count.Source: §C.2 · p. 38
  • Structured Language leads on the three tree tasks, sparse Minimum Spanning Tree, and Second MST at both densities.Source: §C.2 · p. 38
  • Adjacency Matrix leads on sparse Cycle Count, Eulerian Path at both densities, dense Maximum Clique, and Maximum Independent Set at both densities.Source: §C.2 · p. 38
  • Adjacency List leads on sparse Connectivity, Hamiltonian Path and Circuit at both densities, Shortest Path at both densities, and several sparse flow and cut tasks.Those sparse tasks are Maximum Flow, Min Cost Max Flow, and Minimum Cut.Source: §C.2 · p. 40
  • Within a single task–structure row, the best and worst representations often differ by more than ten points, and the winner changes across rows.Table 20 reports model-averaged accuracy for 43 settings; bold values identify each row’s best representation.Source: §C.2 · pp. 38, 40, Table 20 · p. 39

D Case Studies

Case studies show that the same model can succeed or fail on the same graph problem depending on its input representation. The appendix also describes prompt templates for GTA’s Selector, Algorithm Generator, and Algorithm Decomposer.

D Case Studies

  • GPT-4o-mini fails a sparse connectivity problem with Natural Language input but solves the same instance with Adjacency List input.The neighbor listing is described as facilitating path-finding compared with the more verbose Natural Language description.Source: D Case Studies · p. 40, Figure 3 · p. 41, Figure 4 · p. 42
  • Llama-3.3-70B fails to identify a tree centroid with Adjacency List input but computes it correctly with Structured Language input.The paper suggests the templated, potentially hierarchical format better supports reasoning about subtree sizes and properties.Source: D Case Studies · p. 40, Figure 5 · p. 43, Figure 6 · p. 44
  • o3-mini miscounts cycles in a dense graph from Natural Language input but counts them correctly from an Adjacency Matrix.The paper suggests that explicitly representing connections and non-connections helps combinatorial bookkeeping.Source: D Case Studies · p. 40, Figure 7 · p. 45, Figure 8 · p. 46
  • The same model solves the same instance once its graph structure arrives in a form matched to the task, illustrating the instance-level counterpart of aggregate representation sensitivity.GTA’s Selector is trained to exploit this behavior.Source: D Case Studies · p. 40

E Prompt Templates

Loading 2609.12265v1…