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, et al.
cs.AI
Quick verdict
Benchmark+agent paper: LLM graph accuracy hinges on input format; GTA lifts Phi-4 to 69.1%/41.5%; convincing, though graphs are small, synthetic, stats thin.
Summary
The paper introduces Graph Theory Bench (GT Bench), a benchmark of 24 classical graph-theoretic problems across 44 task-structure settings and over 100,000 examples, each instance rendered in four equivalent representations (natural language, structured language, adjacency list, adjacency matrix). Evaluations of eight LLMs show accuracy swings strongly with representation — Connectivity on sparse graphs spans 60.5%-89.1% across formats — and the winning format depends jointly on task, graph density/size/topology, and model; sensitivity narrows but persists in the strongest reasoning models (1.9-point spread for DeepSeek-R1 vs 9.2 for QwQ-32B). Concatenating all four formats hurts (GPT-4o falls 47.6% to 40.3%). Building on these findings, the Graph Theory Agent (GTA) couples a preference-trained representation Selector with plan-decompose-execute scaffolding around a frozen executor, lifting Phi-4 from 53.5% to 69.1% on the easy split and 33.0% to 41.5% on the hard split, outperforming eight prompting and agent baselines at roughly 5-6x vanilla token cost, and transferring without retraining to GraCoRe, NLGraph, and other executors. Limitations: graphs are small (6-60 nodes) and synthetic; headline representation sweeps use a single inference run without confidence intervals; gains shrink to near zero for near-ceiling executors.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 3
● low 1
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- LLM accuracy on algorithmic graph reasoning depends strongly and systematically on input representation, with the best format varying jointly by task, graph structure, and model (e.g., Connectivity on sparse graphs spans 60.5%-89.1%).
- Supplying all four representations simultaneously degrades accuracy relative to the best single format (GPT-4o: 47.6% to 40.3%, Table 6).
- GTA — a preference-trained representation Selector plus plan-decompose-execute scaffolding around a frozen executor — lifts Phi-4 from 53.5% to 69.1% on GT-E and 33.0% to 41.5% on GT-H, outperforming eight prompting and agent baselines.
- GTA transfers without retraining to GraCoRe, NLGraph, and other executor models, with residual gains concentrated where headroom remains (DeepSeek-R1 GT-H +8.1 points).
- Hard multi-step graph tasks remain far from saturated even for the strongest reasoning models (o3-mini 75.1% on GT-H; below 1% model-average on dense Min-Cost Max-Flow).
Strengths
Controlled representation study at scale
44 task-structure settings x 4 encodings x 8 models; the text quantifies swings (Connectivity sparse 60.5%-89.1%; per-model best-worst gaps in Table 4 from 1.9 points for DeepSeek-R1 to 9.2 for QwQ-32B), and Table 19 tabulates the best format for every task-structure pair.
Diagnostics beyond headline accuracy
All-formats concatenation ablation (Table 6: GPT-4o 47.6% to 40.3%), Easy/Hard stratification with ranking reversals (Table 5: GPT-4o beats Llama-3.3-70B on Easy, trails on Hard), divergence from Text Arena Elo (Table 7), and a truncation/extraction audit (Table 17: 0.0% input overflow, 1.2% truncation) ruling out mechanical artifacts.
Frozen-executor design isolates framework effect
Unusual cost and protocol transparency
Transfer evidence
Weaknesses
Small, synthetic graphs only
No uncertainty on headline sensitivity claims
Development-on-test exposure for the Selector
Internal bookkeeping inconsistencies
Easy split near saturation for strong models
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
GT Bench spans 24 classical graph problems (Table 2: Connectivity through Min-Cost Max-Flow), organized into 44 task-structure settings (sparse/dense variants; four single-structure tree tasks) totaling 105,600 encoded examples, each instance rendered in four equivalent representations (NL, SL, AM, AL). The paper claims three contributions: the benchmark; a systematic characterization of representation sensitivity across eight LLMs; and GTA, an agent that adaptively selects representation and decomposes the solution around a frozen executor. The visible tables support the headline claims: representation choice moves Connectivity on sparse graphs from 60.5% to 89.1% (Sec. 1); Phi-4+GTA reaches 69.1%/41.5% on GT-E/GT-H versus 53.5%/33.0% vanilla (abstract, Table 14); transfer to GraCoRe (66.8% to 80.5%) and NLGraph (80.2% to 89.4%) without retraining (Table 14). The language-only scope is stated consistently, with code-execution protocols (GraphAlgorithm, GraphTeam's coding pipeline) positioned as a different capability.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is the Graph Theory Agent (GTA)?
GTA is an agent framework for graph problems: a preference-trained selector first picks the best input format (natural language, structured language, adjacency list, or adjacency matrix), a decomposer splits the task into at most three sub-steps, and a frozen LLM executor solves them. On GT Bench it raised Phi-4 from 53.5% to 69.1% (easy split) and from 33.0% to 41.5% (hard split) without fine-tuning the executor.
What is GT Bench?
Graph Theory Bench is a benchmark of 24 classical graph problems (from connectivity checks to min-cost max-flow and NP-hard problems like Maximum Clique) organized into 44 task-structure settings with over 100,000 examples. Every instance appears in four equivalent encodings — natural language, structured language, adjacency list, adjacency matrix — with easy/hard splits and algorithmically computed ground-truth answers.
Why does input representation matter for LLM graph tasks?
Because the same graph encoded differently changes accuracy dramatically: on one task (Connectivity on sparse graphs) accuracy ranged from 60.5% to 89.1% across the four formats, and the best format varies with the task, graph density, size, topology, and the specific model. Giving all four formats at once actually hurts performance.
Is code or data available for this paper?
Yes. The paper points to github.com/xzx34/GTA for the benchmark generation and evaluation code, and a project homepage at xzx34.github.io/gta/.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The provided text is a sampled excerpt with three marked '[...sampling gap...]' regions; sections 3 (benchmark construction details), parts of Sec. 5-6 (including the main GTA-vs-baselines Table 8 and ablation Table 9 contents), part of the references, and Appendix C.2 Table 20 were skipped and not consulted; judgments rely only on text outside the gaps.
- Figures appear only as captions and response fragments in the extraction; figure-internal content was not verifiable.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.