Graph of Thoughts： Solving Elaborate Problems with Large Language Models

（AAAI 2024）

方法

GoT 框架的核心在于将 LLM 的推理过程建模为一个有向图 $G = (V, E)$ 。

• 顶点集 $V$：图中的节点 $v \in V$ 代表一个独立的“LLM 想法（thought）”，即问题求解过程中的初始状态、中间状态或最终解决方案 。
• 边集 $E$：图中的有向边 $E \subseteq V \times V$ 映射了想法之间的依赖关联 。存在有向边 $(t_1, t_2)$ 意味着想法 $t_1$ 作为显式输入参与了想法 $t_2$ 的生成过程 。
• 异构图扩展：在包含不同类型推理模块（如规划节点与内容生成节点）的复杂任务中，系统引入类别映射函数 $c$，将 $G$ 扩展为异构图 $G = (V, E, c)$，以区分不同顶点的推理属性。

节点是 Operation 类的实例，每个操作定义了对思维的一种处理方式，如生成、评分、聚合等。 operations.py:38-65

节点的通用属性

所有 Operation 对象都包含以下核心属性：

属性	类型	说明
id	int 整数	节点的唯一标识符
operation_type	OperationType 操作类型	操作类型枚举（如 generate, score, aggregate）
predecessors	List[Operation] 列表[操作]	前驱节点列表（依赖的操作）
successors	List[Operation] 列表[操作]	后继节点列表（依赖此操作的操作）
executed	bool 布尔值	标记操作是否已执行
thoughts	List[Thought] 列表[想法]	该操作生成的思维列表（在子类中实现）

不同操作类型的特定属性

不同的操作子类有各自的特定参数：

操作类型	特定属性
Score	num_samples, combined_scoring, scoring_function operations.py:161-186
Generate	num_branches_prompt, num_branches_response operations.py:398-412
ValidateAndImprove	num_samples, improve, num_tries, validate_function
KeepBestN	n, higher_is_better
Aggregate	num_responses
Selector	selector
GroundTruth	ground_truth_evaluator

推理图 $G$ 的演进通过一系列思维转换操作 $\mathcal{T}$ 实现。给定当前推理状态图 $G$ 与模型参数 $p_\theta$，转换操作可定义为 $\mathcal{T}(G, p_\theta)$，其输出为更新后的图状态 $G’$ 。

拓扑结构的更新规则形式化为：

$$V’ = (V \cup V^+) \setminus V^-$$

$$E’ = (E \cup E^+) \setminus E^-$$

在此定义下，$V^+$ 与 $E^+$ 代表注入网络的新想法及依赖关系，而 $V^-$ 与 $E^-$ 则允许框架显式剪枝无前景的推理分支以优化上下文视窗 。

基于此，框架定义了三种核心拓扑变换：

• 聚合 (Aggregation)：通过多入度拓扑结构合并不同推理路径的信息 。针对 $k$ 个源节点 $v_1, \dots, v_k$，操作定义为插入新节点 $v^+$ 及有向边集合 $E^+ = {(v_1, v^+), \dots, (v_k, v^+)}$ 。
• 生成 (Generation)：基于单一源节点 $v$ 派生多个假设空间分支 。操作定义为插入 $k$ 个新节点 ${v_1^+, \dots, v_k^+}$ 及对应的单源辐射状有向边集合 $E^+ = {(v, v_1^+), \dots, (v, v_k^+)}$ 。
• 优化 (Refining)：在图拓扑中通过自环（self-loop）机制实现状态的迭代修正 。操作形式化为空顶点增量 $V^+ = \emptyset$ 及边增量 $E^+ = {(v, v)}$ 。

评估与排序机制 (Scoring & Ranking)

在非线性状态空间的搜索过程中，GoT 引入了评分与评估算子以指导图的展开方向。

• 评分函数 (Scoring)：定义为 $\mathcal{E}(v, G, p_\theta)$，用于计算特定顶点 $v$ 的启发式分数 。该函数将图的全局状态 $G$ 作为输入自变量之一，从而支持基于网络上下文的相对评估机制 。
• 排序函数 (Ranking)：定义为 $\mathcal{R}(G, p_\theta, h)$，作为选择算子，从图空间中提取当前目标函数值最高的 $h$ 个候选节点 。

系统架构实现

在工程实现层面，GoT 框架被解耦为四个协同运作的子模块 。

• 控制器 (Controller)：负责系统层面的调度，它利用两个核心数据结构维护执行逻辑 。其一为静态的操作图 (Graph of Operations, GoO)，预先定义了任务的图解构与拓扑转换范式 。其二为动态的图推理状态 (Graph Reasoning State, GRS)，实时记录模型对话历史及各节点的度量参数 。
• 提示器 (Prompter)：承接控制器的拓扑指令，将底层的图结构与图操作协议编码为模型可解析的上下文提示词输入 。
• 解析器 (Parser)：作为反向解码器，对 LLM 输出的非结构化文本进行信息抽提，重构出标准化的思维状态数据以更新 GRS 。
• 评分与验证模块 (Scoring & Validation)：执行由 $\mathcal{E}$ 定义的打分逻辑，视任务属性可调用 LLM 自评分系统、启发式规则或人类反馈接口 。

性能评估与成本优势

论文在排序、集合操作、关键字计数和文档合并等任务上对 GoT 进行了评估 。

• 在排序任务中，GoT 相比于 ToT 提升了约 62% 的质量，同时降低了超过 31% 的成本 。
• GoT 能够将复杂的任务分解为更小的子任务，独立解决后再逐步合并为最终结果，这是其取得优势的重要原因 。
• 论文提出了一种名为“想法体积”（volume of a thought）的新评估指标，用于衡量有多少先前的 LLM 想法可能对当前想法产生了影响 。
• GoT 是唯一能够同时实现 logkN 的低延迟和 N 的高体积的提示方案 。

提示方案	延迟 (Latency)	体积 (Volume)
思维链 (CoT)	N PDF	N PDF
思维树 (ToT)	O(logkN) PDF	O(logkN) PDF
思维图 (GoT)	logkN PDF	N PDF