GTBench：一个基于课程体系的图论数学研究助手大语言模型评估基准

# GTBench：一个基于课程进度的基准，用于评估大语言模型作为图论数学研究助手的能力
来源：https://arxiv.org/html/2606.03144
Noujoud Nader, Ibrahem Aljabea, Patrick Diehl
洛斯阿拉莫斯国家实验室
新墨西哥州，美国
[email protected] (https://arxiv.org/html/2606.03144v1/mailto:[email protected])
1234-5678-9012 (https://orcid.org/1234-5678-9012)
以及
Deepti Gupta
德克萨斯农工大学中德克萨斯分校
德克萨斯州学院站，美国

(2018)

###### 摘要。

大语言模型（LLMs）越来越多地被用作技术学科的自学助手，然而它们作为数学推理助手的可靠性仍知之甚少。我们提出了GTBench，一个基于课程进度的基准，用于评估大语言模型作为图论数学研究助手的能力。该基准包含63个问题，组织成三个难度递增的组别：本科定义与基本性质（第1组）、算法追踪与结构推理（第2组），以及研究生级别的证明构建（第3组）。问题来源于经过验证的学术材料，包括Diestel的《图论》。我们评估了五个前沿模型——GPT-5、Claude Sonnet 4.6、Gemini 2.5 Flash-Lite、Llama 3.3 70B和Mistral Large 3——在零样本提示和思维链提示下的表现，对第1组和第2组使用精确匹配和LLM作为评判员的评估，对第3组使用混合人类专家和LLM作为评判员的协议。我们的结果揭示了一个明显的性能层级：GPT-5在第1组中接近天花板（零样本准确率95.8%），并在研究生证明上保持了有意义的准确率（82%），而所有其他模型随着难度的增加性能大幅下降，其中Llama在第3组零样本下的人类评估中达到0%。故障模式分析表明，第1组和第2组中“算法正确，执行错误”占主导地位，而第3组则额外出现了“推理不完整”的失败，并揭示了人类评估员与自动评判员之间的系统性分歧，尤其是在冗长或近乎完整的证明上（不同人类组合的κ=0.48–0.83）。GTBench提供了第一个用于LLM图论推理的基于课程进度的评估框架，对数学教育和科学研究中AI工具的治理具有直接意义。

大语言模型（LLMs），数学推理，图论，基准测试，零样本提示，思维链提示，故障分析

††版权：acm许可
††期刊年份：2018
††DOI：XXXXXXX.XXXXXXX
††会议：请从您的权利确认邮件中输入正确的会议标题；2018年6月03–05日；纽约州伍德斯托克
††ISBN：978-1-4503-XXXX-X/2018/06
††CCS：计算方法 人工智能
††CCS：数学计算 离散数学
††CCS：人工智能 知识表示与推理

## 1. 引言

大语言模型（LLMs）在广泛的推理任务中展现出卓越的性能，从常识问答到数学问题解决和代码生成（cobbe2021gsm8k, (https://arxiv.org/html/2606.03144#bib.bib8); hendrycks2021math, (https://arxiv.org/html/2606.03144#bib.bib18); diehl2024evaluating, (https://arxiv.org/html/2606.03144#bib.bib11); nader2025llm, (https://arxiv.org/html/2606.03144#bib.bib26); diehl2025llm, (https://arxiv.org/html/2606.03144#bib.bib13); mhatre2026can, (https://arxiv.org/html/2606.03144#bib.bib25)）。这些进展推动了人们对于理解 LLM 推理能力和局限性的兴趣，尤其是在需要结构化、多步骤思考的领域。其中，数学已成为一个核心试验场，因为它提供了具有明确定义答案和清晰难度梯度的数学问题。然而，数学推理文献主要集中于数值、代数和形式证明设置。图论推理在这一领域中占据着独特的位置——它既在定义上基础，又在证明上极具挑战性，需要那种只有通过持续练习才能发展的结构直觉。正是因为这种丰富性，它成为了LLMs的理想压力测试：这些模型能否超越模式匹配的答案，真正推理关系结构、组合性质和形式证明构建？这个问题不仅仅是理论上的。研究人员和学生越来越多地依赖LLMs作为日常工作中的推理助手（nader2025llm, (https://arxiv.org/html/2606.03144#bib.bib26); diehl2025llmhpc, (https://arxiv.org/html/2606.03144#bib.bib12)），而在像图论这样基础性的领域中，假设能力与实际能力之间的差距，对这些工具如何被信任和采用具有实际影响。

图论是离散数学和理论计算机科学的核心分支，对算法设计、网络分析、组合优化、复杂性理论和数据结构做出了重要贡献（nader2015classification, (https://arxiv.org/html/2606.03144#bib.bib27); nader2015pregnancy, (https://arxiv.org/html/2606.03144#bib.bib28)）。图论问题需要一种独特的推理形式：它同时是视觉性和抽象性的，需要操作关系结构、应用算法程序以及证明结构属性。与算术或代数推理不同，图论问题解决通常要求模型在多个推理步骤中跟踪组合对象的状态，识别结构模式，并应用需要仔细验证条件的定理。这些特性使得图论成为探测LLM推理能力的一个特别丰富且具有挑战性的领域。

图论推理在LLM基准测试文献中尚未被系统评估。现有的基准要么专注于数值和代数推理，如MATH (hendrycks2021math, (https://arxiv.org/html/2606.03144#bib.bib18))、GSM8K (cobbe2021gsm8k, (https://arxiv.org/html/2606.03144#bib.bib8))和GHOSTS (frieder2023ghosts, (https://arxiv.org/html/2606.03144#bib.bib15))，要么专注于形式化、机器可验证的证明生成，如LeanDojo (yang2023leandojo, (https://arxiv.org/html/2606.03144#bib.bib33))和MiniF2F (zheng2021minif2f, (https://arxiv.org/html/2606.03144#bib.bib34))。研究级别的基准测试如FrontierMath (glazer2024frontiermath, (https://arxiv.org/html/2606.03144#bib.bib16))、HLE (anonymous2024hle, (https://arxiv.org/html/2606.03144#bib.bib4))、LemmaBench (anonymous2024lemmabench, (https://arxiv.org/html/2606.03144#bib.bib5))和RealMath (anonymous2024realmath, (https://arxiv.org/html/2606.03144#bib.bib6)) 针对专家级别的数学难度，但并未特别将图论推理作为评估领域加以分离。虽然最近的工作开始探究LLMs是否能解决用自然语言表达的图问题 (fatemi2023graphnl, (https://arxiv.org/html/2606.03144#bib.bib14))，但一个系统的、基于课程进度的、涵盖图论教学全范围的基准在文献中仍然缺失。至关重要的是，这些基准均未解决具体的治理问题：LLMs是否足够值得信赖，能够充当数学研究助手——即科学家或学生可能依赖的理解、验证或扩展技术领域知识的工具。

为了解决这一局限性，我们引入了GTBench，一个专门设计用于评估大语言模型图论推理能力的基于课程进度的基准。GTBench根据图论教学在本科和研究生项目中的标准进展组织问题，问题来源于经过验证的学术资料，包括大学环境中使用的教科书、课程材料和习题集。该基准被结构化为三个难度递增的组别，每个组别对应于图论教育的一个可识别阶段。当前研究侧重于第1组（本科初级）和第2组（本科中级），第3组涵盖研究生级别内容。

第1组问题评估基础知识：熟悉标准图族，例如完全图 \(K_n\)、圈 \(C_n\)、路径 \(P_n\)、轮图 \(W_n\)、超立方体 \(Q_d\) 和完全二部图 \(K_{r,s}\)，以及度序列、子图操作、补图、同构和基本计数论证。这些问题主要是定义性和组合性的，其答案足够简洁，可以通过精确匹配来评估。

第2组问题复杂度增加，要求应用图算法以及对连通性和遍历所产生的性质进行结构推理。主题包括广度优先搜索（BFS）和深度优先搜索（DFS）、割点和桥、欧拉图和哈密顿图条件、树的刻画以及最小生成树算法（如 Kruskal 和 Prim 算法）。这些问题对应于标准本科离散数学或图论课程的算法核心，要求模型执行多步骤过程，跟踪中间状态，并在每一步产生可验证的推理。

第3组问题超越了标准的算法推理，需要更深入的数学论证、证明构建以及对多种解决策略的比较评估。这些问题通常涉及高级图论概念，如图着色、平面性、匹配、网络流、谱性质、NP完全图问题和基于复杂性的推理。与第1组和第2组相比，第3组强调开放式的推理，可能存在多种有效方法，必须仔细评估部分正确性。由于这种复杂性，第3组的评估结合了人类专家评审和LLM作为评判员的评估，以确保可靠的评分和一致性。

我们的主要贡献如下：

- • 我们引入了GTBench，这是第一个基于课程进度的基准，用于评估LLM的图论推理能力，明确将其构建为对LLM作为数学研究助手的评估，并根据图论教学的标准进展组织为三个组别。
- • 我们进行了系统的实证评估，测试领先的LLM在第1组和第2组上的表现，提供了关于模型优势和跨一系列图论问题类型的失败模式的详细分析。
- • 我们设计并验证了一种混合评估方法，结合了LLM作为评判员的评分和人类专家评估。
- • 我们公开发布GTBench，以支持可重复的研究，并为未来评估LLM在离散数学和理论计算机科学中的推理能力奠定基础。

##### 论文结构

本文的其余部分组织如下。第2节 (https://arxiv.org/html/2606.03144#S2) 回顾了相关工作。基准设计在第3节 (https://arxiv.org/html/2606.03144#S3) 中介绍。过滤过程在第4节 (https://arxiv.org/html/2606.03144#S4) 中描述。实验方法在第5节 (https://arxiv.org/html/2606.03144#S5) 中概述，接着是第6节 (https://arxiv.org/html/2606.03144#S6) 中的故障模式分类。结果在第7节 (https://arxiv.org/html/2606.03144#S7) 中讨论。第8节 (https://arxiv.org/html/2606.03144#S8) 总结全文，并确定未来工作的方向。

## 2. 相关工作

对LLM数学推理进行基准测试的努力涵盖了广泛的难度谱。在学校和竞赛级别，GSM8K (cobbe2021gsm8k, (https://arxiv.org/html/2606.03144#bib.bib8)) 涵盖了小学算术，MATH (hendrycks2021math, (https://arxiv.org/html/2606.03144#bib.bib18)) 针对竞赛级别的代数和几何，而GHOSTS (frieder2023ghosts, (https://arxiv.org/html/2606.03144#bib.bib15)) 则探测本科问题解决能力。在研究前沿：(i) LemmaBench (anonymous2024lemmabench, (https://arxiv.org/html/2606.03144#bib.bib5)) 使用了 Gemini 2.5 Pro 和 ChatGPT 4/5，结果由LLMs和人类共同评判；(ii) RealMath (anonymous2024realmath, (https://arxiv.org/html/2606.03144#bib.bib6)) 从 arXiv 预印本和数学论坛中提取问题，使用了 ChatGPT o3/o4、Gemini 2.5 Pro、Claude 3.7、Grok-3 和 DeepSeek R1，结果由LLMs评判；(iii) FrontierMath (glazer2024frontiermath, (https://arxiv.org/html/2606.03144#bib.bib16)) 使用了 GPT-4、Claude 3.7 和 Gemini 1.5 Pro，结果通过自动验证进行核实；(iv) HLE (anonymous2024hle, (https://arxiv.org/html/2606.03144#bib.bib4)) 使用专家筛选的问题将模型推向极限，其初始出版物评估了 GPT-4o/o1 和 Claude 3.5。他们的排行榜还报告了 GPT o3-mini/o3/o5、Sonnet 3.7/4/4.5、Gemini 2.5 Pro/3.x、Grok 4、DeepSeek R1 和 Kimi K2 的结果。表1 (https://arxiv.org/html/2606.03144#S2.T1) 总结了这些工作。另一条独立的研究路线，以 LeanDojo (yang2023leandojo, (https://arxiv.org/html/2606.03144#bib.bib33)) 和 MiniF2F (zheng2021minif2f, (https://arxiv.org/html/2606.03144#bib.bib34)) 为代表，专注于在交互式定理证明器中进行机器可验证的证明生成。在所有上述努力中，问题主要来自数值、代数和分析领域，离散数学和图论基本未被覆盖。在本工作中，作者 (xie2026core, (https://arxiv.org/html/2606.03144#bib.bib32)) 引入了 CORE，一个由人类验证的基准，用于评估LLMs在基本静态代码分析任务上的语义推理能力。作者 (kulkarni2026evaluating, (https://arxiv.org/html/2606.03144#bib.bib20)) 通过使用结构化数学评估过程测试LLM在一个已解决问题和一个开放研究问题上的表现，评估了LLM支持图论推理的有效性。Wang 等人 (wang2025exploring, (https://arxiv.org/html/2606.03144#bib.bib30)) 对LLMs在图学习任务上的表现进行了全面研究，比较了它们在不同评估设置下的推理能力、鲁棒性和迁移性能与传统图学习模型。本工作中，作者 (liu2025combibench, (https://arxiv.org/html/2606.03144#bib.bib22)) 引入了 CombiBench，一个使用基于 Lean 4 的数学问题来测试LLMs组合推理能力的正式基准和评估框架。

与我们工作最相关的是，文献 (fatemi2023graphnl, (https://arxiv.org/html/2606.03144#bib.bib14)) 研究了LLMs能否解决用自然语言表达的图问题，揭示了结构推理方面的重要局限性。然而，该工作缺乏基于课程进度的结构，也没有解决多步骤程序性问题带来的评估挑战。GTBench 填补了这一空白，提供了第一个系统的、多层次的基准，与标准的本科图论课程保持一致，并采用了适用于各类问题类型的混合精确匹配和LLM作为评判员的评估方法。

表 1. 相关基准与 GTBench（本文）在难度级别、评估模型、数据来源和评估方法上的比较。自动 = 自动验证；LLM = LLM作为评判员；人类 = 人类专家评估。
## 3. 基准设计

在本研究中，我们引入了GTBench，一个基于课程进度的基准，用于评估大语言模型（LLMs）的图论推理能力。本节描述了GTBench的设计原则、问题来源以及三个组别。