Graph of Thoughts (GoT) 框架详解

摘要

Graph of Thoughts (GoT) 是一种创新的大语言模型（LLM）提示框架，通过将LLM推理过程建模为任意有向图结构，实现了对思维链（Chain-of-Thought）和思维树（Tree-of-Thought）等现有方案的全面扩展。GoT引入了思维聚合等新型变换操作，使LLM能够模拟人类非线性问题解决过程，在排序、集合运算、关键词统计和文档合并等任务中实现了显著性能提升，同时降低推理成本。

引言

大语言模型（LLM）在自然语言处理领域取得了突破性进展，但如何有效引导LLM进行复杂推理仍是一个挑战。现有提示方案如：

输入-输出（IO）：直接映射输入到输出
思维链（CoT）：引入中间推理步骤
多CoT（CoT-SC）：生成多条独立推理链
思维树（ToT）：树状结构探索推理路径

然而，这些方案存在局限性：CoT缺乏全局探索，CoT-SC无法实现局部回溯，ToT不支持思维聚合。GoT通过图结构建模推理过程，解决了这些限制，实现了更灵活、高效的LLM推理框架。

核心原理

GoT的核心思想是将LLM推理过程建模为有向图，其中：

顶点（V）：表示LLM思维（部分解或最终解）
边（E）：表示思维间的依赖关系

形式化定义：GoT = (G, T, E, R)，其中：

G = (V, E)：有向图表示推理过程
T：思维变换操作集合
E：评估函数，用于评分思维
R：排序函数，用于选择最优思维

GoT形式化定义（Python伪代码）

class GraphOfThoughts:
    def __init__(self):
        self.graph = Graph()  # 有向图 G=(V,E)
        self.transformations = []  # 思维变换操作 T
        self.evaluator = None  # 评估函数 E
        self.ranker = None  # 排序函数 R
    
    def apply_transformation(self, transformation, inputs):
        """应用思维变换操作"""
        new_vertices = transformation(inputs)
        self.graph.add_vertices(new_vertices)
        return new_vertices
    
    def evaluate(self, vertex):
        """评估思维质量"""
        return self.evaluator(vertex, self.graph)
    
    def rank(self, k):
        """选择前k个最优思维"""
        return self.ranker(self.graph, k)

思维变换操作

GoT支持三类核心思维变换操作：

聚合（Aggregation）：合并多个思维为新思维

聚合操作示例

def aggregate(thoughts):
    """合并多个排序子数组为完整排序数组"""
    prompt = f"合并以下已排序列表：{thoughts}"
    merged = llm.generate(prompt)
    return merged

精炼（Refining）：迭代改进现有思维

精炼操作示例

def refine(thought):
    """改进排序结果中的错误"""
    prompt = f"修正以下排序中的错误：{thought}"
    improved = llm.generate(prompt)
    return improved

生成（Generation）：基于单个思维生成多个新思维

生成操作示例

def generate(thought, k=3):
    """生成k个不同排序方案"""
    prompts = [f"对列表进行排序：{thought}"] * k
    return [llm.generate(p) for p in prompts]

系统架构

GoT采用模块化架构设计，包含以下核心组件：

GoT系统架构图（文字描述）

+----------------+      +----------------+      +----------------+
|   Prompter    |----->|     Parser     |----->| Scoring Module |
+----------------+      +----------------+      +----------------+
        ^                       |                       |
        |                       v                       v
+----------------+      +----------------+      +----------------+
|   Controller   |<-----| Graph Reasoning|<-----|    LLM/External |
|                |      |    State (GRS) |      |    Entities    |
+----------------+      +----------------+      +----------------+
        ^
        |
+----------------+
| Graph of Ops  |
|    (GoO)       |
+----------------+

核心组件详解

提示器（Prompter）：负责构建发送给LLM的提示，编码图结构信息
解析器（Parser）：从LLM响应中提取信息，更新图状态
评分模块（Scoring）：验证思维正确性并分配分数
控制器（Controller）：协调推理过程，决定下一步操作
操作图（GoO）：静态结构，指定任务分解和操作顺序
图推理状态（GRS）：动态结构，维护当前推理状态

工作流程

用户构建GoO实例，定义任务分解策略
控制器根据GoO初始化GRS
迭代执行以下步骤直到完成：
- 选择当前思维并应用变换操作
- 提示器构建提示发送给LLM
- 解析器处理LLM响应并更新GRS
- 评分模块评估新思维质量
- 控制器决定是否继续或终止
返回最优解作为最终结果

设计思想

1. 图结构建模推理过程

GoT的核心创新在于使用图结构建模LLM推理过程，相比线性链（CoT）或树结构（ToT），图结构能够：

表示任意复杂的依赖关系
支持思维间的多对多连接
实现非线性推理路径
支持思维聚合等高级操作

2. 模块化与可扩展性

GoT采用高度模块化设计，每个组件提供清晰API：

核心API示例

# 提示器API
Prompter.generate(thought, k)  # 生成k个新思维
Prompter.aggregate(thoughts)     # 聚合多个思维

# 控制器API
Controller.generate()           # 生成操作
Controller.aggregate()           # 聚合操作
Controller.keep_best(n)         # 保留前n个最优思维

3. 任务分解策略

GoT的核心设计原则是将复杂任务分解为LLM可可靠解决的子任务：

分解粒度：确保子任务在LLM能力范围内
渐进合并：通过聚合操作逐步构建最终解
错误纠正：通过精炼操作修正中间结果错误

4. 延迟-体积权衡优化

GoT通过图结构实现了延迟（推理步数）和体积（信息覆盖范围）的最优权衡：

方案	延迟	体积
CoT	N	N
CoT-SC	N/k	N/k
ToT	log_kN	O(log_kN)
GoT	log_kN	N

GoT在保持低延迟（log_kN）的同时，实现了最大信息覆盖（N），这是通过聚合操作实现的独特优势。

应用案例与评估

1. 排序任务

GoT采用归并排序策略分解任务：

将输入数组分解为子数组
独立排序子数组
聚合排序结果为最终解

排序任务GoO配置

1. Generate(k=1)  # 分割数组为子数组
2. foreach subarray:
3.   Generate(k=5)  # 排序子数组
4.   Score(k=1)     # 评分排序结果
5.   KeepBestN(1)   # 保留最佳排序
6. Aggregate(10)    # 聚合排序结果
7. Score(k=1)       # 评分聚合结果
8. KeepBestN(1)     # 保留最佳结果

2. 集合运算

对于集合交集运算，GoT采用分治策略：

将第二个集合分解为子集
计算子集与第一个集合的交集
聚合交集结果为最终解

3. 关键词统计

GoT将文本分解为段落，独立统计关键词后聚合结果：

关键词统计提示示例

prompt = """
统计以下段落中每个国家的出现次数：
{paragraph}
输出格式：
{{
  "country1": count1,
  "country2": count2,
  ...
}}
"""

4. 文档合并

GoT通过多轮聚合和精炼操作合并多个NDA文档：

生成多个合并候选
评分并选择最佳候选
聚合最佳候选
精炼最终结果

性能评估

在GPT-3.5上的实验结果表明：

排序任务：相比ToT，GoT将128元素排序的中位错误数降低62%，同时减少31%以上成本
集合运算：GoT在128元素集合上实现100%正确率，而ToT存在错误
关键词统计：GoT将错误数从25（ToT）降至7
文档合并：GoT的文档质量评分（7.78）显著高于ToT（6.87）

结论与展望

Graph of Thoughts (GoT) 框架通过将LLM推理过程建模为有向图结构，实现了对现有提示方案的全面扩展。其核心创新包括：

引入思维聚合等新型变换操作
实现非线性推理路径
优化延迟-体积权衡
提供模块化可扩展架构

实验证明，GoT在排序、集合运算、关键词统计和文档合并等任务中显著优于现有方案，同时降低推理成本。未来工作将探索：

自动化图分解策略
多模态任务支持
分布式推理优化
与外部工具的集成

GoT为复杂LLM推理任务提供了强大而灵活的框架，为提示工程领域开辟了新的研究方向。