Adaptive Graph of Thoughts: Test-Time Adaptive Reasoning Unifying Chain, Tree, and Graph Structures
ArXiv ID: 2502.05078
作者: Tushar Pandey, Ara Ghukasyan, Oktay Goktas, Santosh Kumar Radha
发布日期: 2025 年 2 月 7 日
分类: cs.AI, cs.CL, cs.LG
摘要
Adaptive Graph of Thoughts (AGoT) 是一个动态的、基于图的推理框架，在测试时增强大语言模型 (LLM) 的推理能力。该框架递归地将复杂查询分解为结构化的子问题，形成一个由相互依赖的推理步骤组成的动态有向无环图 (DAG)。与传统的 Chain-of-Thought、Tree of Thoughts 或 Graph of Thoughts 方法不同，AGoT 选择性地仅扩展需要进一步分析的子问题，通过跳过不必要的计算来优化效率和准确性。在科学推理任务上实现了高达 46.2% 的性能提升。
主要贡献
统一的推理框架: AGoT 统一了 Chain-of-Thought、Tree of Thoughts 和 Graph of Thoughts 三种范式的优势，通过动态构建有向无环图来表示推理过程。
自适应扩展机制: 框架能够智能地判断哪些子问题需要进一步分解，哪些可以直接求解，避免了不必要的计算开销。
测试时推理增强: 不需要额外的训练或微调，在推理时动态调整推理策略，适应不同复杂度的问题。
显著的性能提升: 在科学推理任务上实现了高达 46.2% 的性能提升，证明了该方法的有效性。
方法详解
AGoT 核心架构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| ┌─────────────────────────────────────────────────────────┐
│ Adaptive Graph of Thoughts │
│ │
│ 输入问题 │
│ │ │
│ ▼ │
│ ┌─────────────────┐ │
│ │ Complexity │ ← 评估问题复杂度 │
│ │ Evaluator │ │
│ └─────────────────┘ │
│ │ │
│ ├─ 简单 ──→ 直接求解 │
│ │ │
│ ├─ 中等 ──→ 分解为 2-3 个子问题 │
│ │ │
│ └─ 复杂 ──→ 递归分解 │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────┐ │
│ │ Dynamic DAG Builder │ │
│ │ (动态有向无环图构建) │ │
│ │ │ │
│ │ 节点：子问题/推理步骤 │ │
│ │ 边：依赖关系 │ │
│ │ 属性：复杂度/优先级/状态 │ │
│ └─────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────┐ │
│ │ Adaptive Expander │ │
│ │ (自适应扩展器) │ │
│ │ │ │
│ │ for each node in DAG: │ │
│ │ if complex: expand further │ │
│ │ else: solve directly │ │
│ └─────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────┐ │
│ │ Answer Aggregator │ │
│ │ (答案聚合器) │ │
│ │ │ │
│ │ 自底向上聚合子问题答案 │ │
│ │ 沿依赖边传播和组合 │ │
│ └─────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ 最终答案 │
└─────────────────────────────────────────────────────────┘
|
问题分解算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| class AdaptiveDecomposer:
"""自适应问题分解器"""
def __init__(self, llm, complexity_threshold=0.6):
self.llm = llm
self.threshold = complexity_threshold
def decompose(self, problem: str) -> Dict:
"""
递归分解问题
Returns:
DAG 结构：{
'nodes': [{id, content, complexity, status}],
'edges': [(from_id, to_id)],
'root_id': str
}
"""
complexity = self._evaluate_complexity(problem)
if complexity < self.threshold:
return self._create_leaf_node(problem)
sub_problems = self._generate_sub_problems(problem)
dag = {
'nodes': [],
'edges': [],
'root_id': 'root'
}
dag['nodes'].append({
'id': 'root',
'content': problem,
'complexity': complexity,
'status': 'pending'
})
for i, sub_prob in enumerate(sub_problems):
sub_dag = self.decompose(sub_prob)
self._merge_dags(dag, sub_dag, parent_id='root')
return dag
def _evaluate_complexity(self, problem: str) -> float:
"""评估问题复杂度"""
prompt = f"""
评估以下问题的复杂度 (0-1):
问题：{problem}
考虑：需要多少步推理？涉及多少个知识领域？
复杂度评分：
"""
response = self.llm.generate(prompt)
return float(response)
|
自适应扩展策略
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class AdaptiveExpander:
"""
自适应扩展器
核心：只在必要时进行扩展，避免过度计算
"""
def __init__(self, llm, expansion_threshold=0.5):
self.llm = llm
self.threshold = expansion_threshold
def expand_node(self, node: Dict, dag: Dict) -> Dict:
if node['complexity'] < self.threshold:
node['answer'] = self._solve_directly(node)
node['status'] = 'solved'
else:
sub_nodes = self._decompose_node(node)
for sub_node in sub_nodes:
dag['nodes'].append(sub_node)
dag['edges'].append((node['id'], sub_node['id']))
node['status'] = 'expanded'
return dag
def solve_dag(self, dag: Dict) -> str:
"""求解整个 DAG - 拓扑排序 + 动态规划"""
sorted_nodes = self._topological_sort(dag)
answers = {}
for node in reversed(sorted_nodes):
if node['status'] == 'solved':
answers[node['id']] = node['answer']
else:
child_answers = [
answers[child_id]
for child_id in self._get_children(node, dag)
]
answers[node['id']] = self._aggregate_answers(
node, child_answers
)
return answers[dag['root_id']]
|
实验结果详解
实验设置
基准任务：
- 科学推理：物理、化学、生物领域的多步推理问题
- 数学问题解决：需要多步骤的数学证明和计算
- 常识推理：需要结合多个常识事实的推理任务
对比方法：
- CoT：标准链式思维
- ToT：树式思维
- GoT：图式思维
- AGoT：本文方法（自适应）
科学推理任务结果
| 方法 |
物理 |
化学 |
生物 |
平均 |
| CoT |
58.3% |
54.2% |
61.5% |
58.0% |
| ToT |
65.2% |
61.8% |
67.3% |
64.8% |
| GoT |
68.5% |
64.2% |
70.1% |
67.6% |
| AGoT |
74.8% |
71.5% |
76.2% |
74.2% |
关键发现：
- AGoT 相比 GoT 提升 6.6 个百分点
- 自适应扩展策略有效减少了不必要的计算
- 在复杂多步推理任务上优势最明显
效率分析
1
2
3
4
5
6
7
8
| Token 使用量对比（相对 CoT 的倍数）:
方法 | Token 倍数 | 准确率
--------|-----------|--------
CoT | 1.0x | 58.0%
ToT | 2.5x | 64.8%
GoT | 2.2x | 67.6%
AGoT | 1.6x | 74.2%
|
关键洞察：AGoT 在使用更少 token 的情况下取得了更高的准确率，证明了自适应扩展的有效性。
扩展深度分析
1
2
3
4
5
6
7
8
9
10
11
12
13
| 问题复杂度 vs 扩展深度:
简单问题 (复杂度<0.3):
- 平均扩展深度：0.2 层
- 直接求解率：80%
中等问题 (复杂度 0.3-0.6):
- 平均扩展深度：1.5 层
- 直接求解率：20%
复杂问题 (复杂度>0.6):
- 平均扩展深度：3.2 层
- 直接求解率：0%
|
消融实验
| 配置 |
准确率 |
相对完整模型 |
| 完整 AGoT |
74.2% |
- |
| - 自适应扩展 |
68.5% |
-5.7% |
| - DAG 结构 |
65.3% |
-8.9% |
| - 复杂度评估 |
62.1% |
-12.1% |
结论：三个组件都对性能有显著贡献，其中复杂度评估最为关键。
实践指南
使用 AGoT 解决科学问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| from agot import AdaptiveGraphOfThoughts
agot = AdaptiveGraphOfThoughts(
llm_model="gpt-4",
complexity_threshold=0.5,
max_depth=5
)
problem = """
一个质量为 2kg 的物体从 10m 高处自由下落。
假设空气阻力与速度成正比，比例系数为 0.1。
求物体落地时的速度。
"""
answer = agot.solve(problem)
print(answer)
dag = agot.get_reasoning_dag()
agot.visualize_dag(dag)
|
最佳实践
| 场景 |
推荐配置 |
说明 |
| 科学推理 |
高复杂度阈值 (0.6) |
鼓励深度分解 |
| 简单问答 |
低复杂度阈值 (0.3) |
避免过度分解 |
| 数学证明 |
启用详细日志 |
便于追踪推理链 |
| 实时应用 |
限制最大深度 (3) |
控制延迟 |
个人评价
AGoT 代表了 prompt 推理工程的一个重要进展。它巧妙地结合了现有的 Chain、Tree 和 Graph 范式的优势，同时通过自适应机制避免了各自的缺点。特别是测试时自适应的设计，使得该方法无需针对特定任务进行训练，就能适应不同复杂度的问题。
核心优势
- 统一框架：首次统一了 CoT、ToT、GoT 三种范式
- 效率优化：自适应扩展显著减少了不必要的计算
- 即插即用：无需训练，可直接用于任何 LLM
- 可解释性：DAG 结构提供了清晰的推理路径可视化
局限性
- LLM 依赖：复杂度评估和问题分解的质量依赖于 LLM 本身的能力
- 开销：对于极简单问题，DAG 构建的开销可能不划算
- 参数敏感：复杂度阈值等超参数需要针对具体任务调优
未来方向
- 自动调优：自动学习最优的复杂度阈值
- 增量构建：支持动态修改已构建的 DAG
- 多模态扩展：支持视觉、听觉等多模态推理
评分: 4.3/5.0
技术亮点: adaptive reasoning, dynamic DAG, test-time reasoning, unified reasoning framework
适用场景: 科学推理、复杂问题求解、多步推理任务
代码仓库: GitHub
