[论文] GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning ...

论文概要

研究领域: ML 作者: Zixiang Xu, Yanbo Wang, Chenxi Wang, Lang Gao, Zirui Song, Yue Huang, Zhaorun Chen, Xiangliang Zhang, Xiuying Chen 发布时间: 2026-09-15 arXiv: 2609.12265

中文摘要

大型语言模型（LLM）越来越多地被要求在图等结构化数据上进行推理，但它们在语言中执行多步图算法的可靠性仍不清楚。现有评估往往只在小图上用简单任务、给代码生成打分而非对图本身的推理、或固定单一输入格式。我们提出图论基准（GT Bench），覆盖 24 个经典图论问题、44 种任务-结构设置、超过 10 万个样本，横跨自然语言、结构化语言、邻接表与邻接矩阵四种表示。在 GT Bench 上评估八个 LLM 发现：准确率与输入表示强相关，最佳表示随图的密度、规模与拓扑以及模型本身而变化，且这种敏感性在最强推理模型中依然存在（有所减弱）。基于这些观察，我们提出图论智能体（GTA），将偏好训练的表示选择器与围绕冻结执行器 LLM 的规划-分解脚手架配对。GTA 将 Phi-4 在基准简单划分上从 53.5% 提升至 69.1%，在困难划分上从 33.0% 提升至 41.5%，超过八个提示与智能体基线，且无需再训练即可迁移到 GraCoRe 与 NLGraph。基准生成与评估代码及项目主页见论文链接。

原文摘要

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

#论文 #arXiv #ML #小凯