DAG-Math: Graph-of-Thought Guided Mathematical Reasoning in LLMs¶

会议: ICLR 2026
arXiv: 2510.19842
代码: https://github.com/YuanheZ/DAG-MATH
领域: LLM推理
关键词: mathematical reasoning, DAG, chain-of-thought, logical closeness, evaluation metric

一句话总结¶

将 LLM 的 CoT 推理形式化为 DAG 上的基于规则的随机过程，提出"逻辑闭合性"（logical closeness）度量来评估模型是否通过搜索还是严格逻辑推理得到答案，构建了 2894 个金标准 DAG-MATH benchmark，发现即使 PASS@k 相近的模型在推理忠实度上也存在显著差异。

研究背景与动机¶

领域现状：LLM 在数学推理上表现强劲（o1、R1、Gemini-2.5），核心策略是 CoT。但 CoT 的黑盒性质使得难以判断模型是通过逻辑推理还是通过搜索/启发式得到正确答案。
现有痛点：(1) PASS@k 只看最终答案，不评估推理过程的逻辑一致性——搜索式探索也能给出正确答案；(2) LEAN 形式化验证虽严格但需要大量专家工作来预先形式化问题；(3) 现有图模型（Dziri 2023）用确定性子图匹配，忽略了多样采样和长程依赖。
核心矛盾：PASS@k 可能高估推理能力——模型可能通过"探索性分支"偶然找到正确答案，而非严格逻辑推导。需要一个介于自由 CoT 和形式化证明之间的评估框架。
本文要解决什么？ 如何严格定义和评估 LLM 的数学推理能力——区分"搜索得到的正确答案"和"逻辑推理得到的正确答案"？
切入角度：将 CoT 建模为 DAG 上的随机过程——节点是推导步骤的结论，边是推理规则的应用。定义"逻辑闭合"要求每个中间节点都有后续节点使用它，没有无用的探索分支。
核心idea一句话：用 DAG 上的逻辑闭合性来度量 LLM 是否在做真正的逻辑推理，而非仅仅搜索。

方法详解¶

整体框架¶

两阶段框架：Phase 1 构建任务特定的 DAG（源节点=前提，汇节点=答案，中间节点=推导步骤）；Phase 2 LLM 在 DAG 上生成 CoT 轨迹（基于规则的随机过程，只能访问父节点已被生成的节点）。三类 CoT 输出：完美推理（仅包含正确答案的祖先）、不完美推理（包含无关节点但最终答案正确）、错误推理。

关键设计¶

逻辑闭合性（Logical Closeness）:
做什么：评估 CoT 轨迹中每个节点是否都被后续推理使用（出度≥1）
核心思路：如果轨迹中存在"死端"节点（生成了但未被后续步骤引用），说明模型在搜索/探索而非做严格推理。完美推理 = 逻辑闭合 + 最终答案正确
设计动机：PASS@k 只看答案，忽略了过程。Toy example 显示：在双链 DAG 中，PRR 随深度指数衰减 \((1/2)^{L-1}\)，即使最终准确率稳定在 50%
Perfect Reasoning Rate (PRR):
做什么：定义数学推理能力的形式化度量
核心思路：\(\text{PRR}(\mathbf{x}) = \mathbb{E}[\delta_{\text{close}} \times \delta_{\text{final}}]\)——既要逻辑闭合又要答案正确。AUC 变体通过放松闭合比例（0%到100%）提供连续评分
与 PASS@k 的区别：PASS@k 只需要 \(\delta_{\text{final}}=1\)，PRR 额外要求 \(\delta_{\text{close}}=1\)
DAG-MATH Benchmark 构建:
做什么：构建 2894 个金标准 DAG 格式 CoT
核心思路：三阶段 prompting——(1) 让 LLM 生成结构化 CoT（每步标注父节点依赖）；(2) GPT-4 级模型验证和修正 DAG 结构；(3) 人工审核
统计发现：更难的问题对应更大、更稀疏、分支更复杂的 DAG

损失函数 / 训练策略¶

N/A（评估框架 + benchmark，不训练模型）。使用 few-shot prompting 引导 LLM 生成 DAG-MATH 格式的 CoT。

实验关键数据¶

主实验（跨模型 PRR vs PASS@1 对比）¶

发现	说明
搜索膨胀 PASS@1	探索性分支可以通过偶然发现正确路径来提高 PASS@1，但 PRR 不变
PRR 跨模型可比	即使 PASS@k 差异大，各模型家族的完美推理能力其实很接近
完美推理对应简单问题	PRR 高的问题往往是难度低的——说明当前模型对难题的逻辑推理仍然薄弱
错误 CoT 来自超能力范围	困难来自分支（多路推导合并）而非线性链长度

图级统计分析¶

难度	平均节点数	平均边数	分支因子
简单	少	少	低
困难	多	多但稀疏	高

关键发现¶

在 MATH-500、GSM8K、AIME24/25 等上，Gemini、GPT、Qwen3 家族的 PASS@1 差异可达 10%+，但 PRR 差异小得多——说明高 PASS@1 主要来自搜索而非推理
DAG 结构分析揭示：LLM 对需要多步汇聚（多个中间结论合并为一个步骤）的问题最容易失败
PRR 与 PASS@1 的差值可以量化模型的"探索性开销"——差值越大说明模型越依赖搜索而非推理

亮点与洞察¶

首次给出 LLM 数学推理能力的形式化定义：将直觉上的"模型是否真正在推理"转化为可计算的度量（PRR），类比学习理论中记忆/泛化的形式化
"Goldilocks 原则"：框架介于自由 CoT（太松）和 LEAN 形式化证明（太严）之间，提供了实用的中间地带
DAG 复杂度分析的诊断价值：通过分析 DAG 的拓扑结构（深度 vs 分支），可以精确定位模型的弱点——是线性推理不足还是多路整合不足

局限性 / 可改进方向¶

DAG 的构建依赖 LLM + 人工，不完全自动化
节点/边的分解可能不唯一（语义变体），虽然论文讨论了但未完全解决
目前仅在数学推理上验证，推广到其他推理领域（如法律、科学）需要适配
PRR 对非确定性问题（如开放式推理）的适用性受限

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次形式化定义 LLM 推理能力，DAG+逻辑闭合性的框架非常原创
实验充分度: ⭐⭐⭐⭐ 多模型家族对比、图级统计分析、多 benchmark
写作质量: ⭐⭐⭐⭐⭐ 理论推导严谨，概念定义清晰，toy example 说明直观
价值: ⭐⭐⭐⭐⭐ 为推理评估开辟新方向，可能影响该领域的评估标准