Graph-of-Thought: 思维图
Graph-of-Thought: 思维图
用图的推理能力来设计 prompt，思维图能助力 LLM 解决更复杂的任务。近日，一个研究团队提出了更进一步的想法：思维图（GoT）。让思维从链到树到图，为 LLM 构建推理过程的能力不断得到提升，研究者也通过实验证明了这一点。他们也发布了自己实现的 GoT 框架。
研究论文：https://arxiv.org/pdf/2308.09687v2.pdf
官方实现：https://github.com/spcl/graph-of-thoughts
1 相关工作
大型语言模型正在变成人工智能世界的主导技术。近些年高速发展的模型主要基于仅解码器 Transformer 的变体，比如 GPT、PaLM 或 LLaMA。而在解决不同的 LLM 任务时，prompt 工程设计是一种能高效利用资源的方法。简单来说，就是在发送给 LLM 的输入中包含对任务的描述。如果能以适当的形式描述该任务，那么 LLM 就能借助其用于生成文本的基于自回归 token 的机制来解决该任务。
思维链（CoT）便是一种用于设计 prompt 的方法，即 prompt 中除了有任务的输入和输出外，还包含推理的中间步骤（中间思维）。研究表明，CoT 能极大地提升 LLM 的能力，使之无需任何模型更新便能解决一些难题。具体参阅文章见Chain-of-Thought: 思维链。也有研究者改进了 CoT，提出了使用 CoT 实现自我一致的方法（CoT-SC）；这个方案是生成多个 CoT，再选出其中最佳的结果。最近还有研究者更进一步提出了思维树（ToT），其做法是通过树（tree）来建模 LLM 推理过程。这能让模型使用不同的思维路径，并能提供全新的功能，比如基于不好的结果反向回溯推理过程。更多详情请参阅文章Tree-of-Thought: 思维树。
2 论文概述
研究团队认为，如果能将 LLM 的思维构建成图结构，那么就能为 prompt 的能力带来重大提升。这一想法受到了多种现象的启发，比如人类的推理方式、大脑结构和算法的执行方式。
在进行思考时，人类不会像 CoT 那样仅遵循一条思维链，也不是像 ToT 那样尝试多种不同途径，而是会形成一个更加复杂的思维网。举个例子，一个人可能会先探索一条思维链，然后回溯再探索另一条，然后可能会意识到之前那条链的某个想法可以和当前链结合起来，取长补短，得到一个新的解决方案。
基于这一观察，研究团队提出了思维图（GoT，Graph of Thoughts），这种方法可以通过网络形式的推理来增强 LLM 的能力。在 GoT 中，一个 LLM 思维会被建模成一个顶点，顶点之间的依赖关系则建模为边。使用 GoT，通过构建有多于一条输入边的顶点，可以将任意思维聚合起来。整体而言，GoT 使用的图抽象方法可无缝地将 CoT 和 ToT 泛化到更复杂的思维模式，而且这个过程无需更新模型。
2.1 GoT模块化架构
GoT模块化架构有两大亮点。
一是可实现对各个思维的细粒度控制。这让用户可以完全控制与 LLM 进行的对话并使用先进的思维变换，比如将正在进行的推理中两个最有希望的思维组合起来得到一个新的。
二是这种架构设计考虑了可扩展性 —— 可无缝地扩展用于新的思维变换、推理模式（即思维图）和 LLM 模型。这让用户可使用 GoT 快速为 prompt 的新设计思路构建原型，同时实验 GPT-3.5、GPT-4 或 Llama-2 等不同模型。
2.2 思维容量
研究团队还有另一项贡献，即提出一种新的评估指标 —— 思维容量（the volume of a thought），可用于评估 prompt 设计策略。使用这一指标的目标是更好地理解 prompt 设计方案之间的差异。
对于一个给定的思维 v，v 的容量是指 LLM 思维的数量，用户可以基于此使用有向边得到 v。直观上说，这些就是有望对 v 做出贡献的所有 LLM 思维。
通过研究表明，通过整合聚合等思维变换技术，GoT 能让思维容量比其它方案显著更大。
3 GoT框架详细介绍
下面详细介绍一下 GoT 框架。其示意图见图3.1，图中还给出了其它 prompt 设计策略的示意图。
在数学形式上，GoT 可以建模为一个元组 (G, T, E, R)，其中 G 是 LLM 推理过程（即上下文中的所有 LLM 思维及其关系），T 是可能的思维变换，E 是用于获得思维分数的评估器函数，R 是用于选择最相关思维的排序函数。
3.1 推理过程
这里，推理过程被建模为一个有向图 G = (V, E)，其中 V 是一组顶点，E ⊆ V × V 是一组边。G 是有向的，因此边是有序顶点对 E ⊆ V × V 的子集。一个顶点包含对当前问题的一个解答，不管这个问题是最初的问题、还是中间问题或最后的问题。这种思维的具体形式取决于用例；其可能是一段文本（在写作任务中），也可能是一个数值序列（在排序任务中）。有向边 (t_1, t_2) 表示思维 t_2 的构建方式是将 t_1 用作「直接输入」，即通过明确指示 LLM 使用 t_1 来生成 t_2。
在某些用例中，图节点属于不同类别。举个例子，在写作任务中，某些顶点建模写出一段文本的计划，其它节点则建模实际的文本段。在这种情况下，GoT 采用异构图 G = (V, E, c) 来建模 LLM 推理，其中 c 将顶点 V 映射到各自的类 C（在上述案例中，C = {plan, par} ）。这样一来，任何顶点 v 都可以建模推理的不同方面。
于是 G 就与 LLM 推理过程关联了起来。为了推进这一过程，用户可对 G 使用思维变换。举个这种变换的例子：将目前为止分数最高的思维融合成一个新的。另一个例子是对一个思维进行循环，以对其增强。注意，这些变换严格扩展了 CoT、CoT-SC 或 ToT 中可用转换的集合。
3.2 思维变换
得益于将基于图的模型用于推理，GoT 能实现全新的思维变换。研究者称之为图使能的变换（graph-enabled transformation）。比如，在写作任务中可以将多篇输入文章组合成一篇连贯一致的摘要。在排序时，可将多个已排序的数值子数组合并为一个最终已排序数组。图 3.2给出了聚合和生成的示例。
3.3 对思维进行评分和排名
对思维评分的目的是为了理解当前的解答是否足够好。分数被建模为一个一般函数 E (v, G, p_θ)，其中 v 是所要评估的思维。为了尽可能让 E 更普适通用，E 中还使用了推理的整个过程 (G)，因为在某些评估场景中，分数可能与其它思维相关。
GoT 也能排名。研究者使用了函数 R (G, p_θ, h) 来建模，其中 h 指定了要被 R 返回的 G 中排名最高的思维的数量。虽然 R 的具体形式取决于用例，但最常使用一个简单而有效的方法是返回分数最高的 h 个思维，即 v_1, ..., v_h = R (G, p_θ, h)。
E 和 R 的具体形式取决于用例。
3.4 系统架构和扩展能力
GoT 由一组交互式模块构成。这些模块是 Prompter（准备用于 LLM 的消息）、Parser（解析器，提取 LLM 答复中的信息）、评分模块（验证 LLM 答复并评分）、Controller（控制器，协调整个推理过程，并决定如何推进推理）。Controller 中包含另外两个重要组件：操作图（GoO）和图推理状态（GRS）。GoO 是一个静态结构，其指定了对给定任务的图分解，即它规定了应用于 LLM 思维的变换及其顺序和依赖关系。GRS 是一个动态结构，其维持着正在进行的 LLM 推理过程的状态（其思维及其状态的历史）。
4 用例示例
研究者描述一些 GoT 的一些用例，包括排序、集合运算、关键词计数、文档合并；下图 4.1 便是 GoT 的排序用例中一个图分解示例。
5 思维容量
延迟（在思维图中抵达给定最终思维的跳数）和容量之间的权衡也非常重要，研究者表明：GoT 在这一权衡上也优于之前的 prompt 设计方案。这篇论文定义了一个新指标 —— 思维容量，即可以影响给定思维 t 的之前 LLM 思维的数量。从数学上看，思维 t 的容量就是在思维图中，与 t 之间存在路径的思维的数量。研究者假设输出单个思维的成本为 O (1)，并将每个提示方案的总成本固定为 Θ(n)。
各种方案的结构如下。CoT-SC 由源自单个起始思维的 k 条独立链构成。ToT 是一条完全 k 叉树。而在 GoT 中，会在其叶节点处加入一个完全 k 叉树，并带有一个「镜像」k 叉树 —— 其大小一样而边是反向的。
详细分析见表 5.1。CoT 的容量较大，最大可至 N，但也有 N 的高延迟成本。CoT-SC 将延迟降低了 k 倍（对应于其分支因子），但同时其容量也会减小 k 倍。ToT 的延迟为 log_k N，但容量也很低。GoT 是唯一能做到低延迟 log_k N 和高容量 N 的方案。GoT 之所以能做到这一点，是因为其利用了思维聚合，使其可从图分解中任何其它中间思维得到最终思维。
