大型語(yǔ)言模型在推理上仍然是弱勢(shì)項(xiàng)目，需要依賴各種思維工具輔助完善推理過(guò)程。

最近，蘇黎世聯(lián)邦理工大學(xué)、華沙理工大學(xué)的研究人員共同提出了一個(gè)全新的LLM思維框架GoT（Graph of Thoughts，GoT），在推理質(zhì)量和推理速度上都要超越現(xiàn)有的思維鏈（CoT）和思維樹（ToT）等方法。

論文鏈接：https://arxiv.org/pdf/2308.09687.pdf

GoT的關(guān)鍵思想和主要優(yōu)勢(shì)在于將LLM生成的信息建模為圖（arbitary graph），其中信息單元（思維，LLM thoughts）作為圖的頂點(diǎn)，頂點(diǎn)之間的依賴關(guān)系作為圖的邊。

GoT方法可以將任意的LLM思維組合成協(xié)同結(jié)果，提取出整個(gè)思維網(wǎng)絡(luò)的本質(zhì)，或者使用反饋回路來(lái)增強(qiáng)思維。

通過(guò)實(shí)驗(yàn)可以證明GoT在不同任務(wù)上提供了優(yōu)于現(xiàn)有技術(shù)的優(yōu)勢(shì)，例如，與ToT相比，排序任務(wù)的質(zhì)量提高了62%，同時(shí)成本降低了31%

研究人員認(rèn)為，GoT方法可以讓LLM推理更接近人類的思維和大腦推理機(jī)制，比如二者都在內(nèi)部形成了復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)。

LLM思維（thought）的進(jìn)化之路

用戶與LLM對(duì)話的過(guò)程主要包括用戶消息（提示，prompts）和模型回復(fù)（思維、想法，thoughts），其中回復(fù)可以是一段文本（摘要任務(wù)）、一個(gè)文檔（生成任務(wù)）或是一個(gè)代碼塊等。

為了充分激活語(yǔ)言模型的能力，通常會(huì)采用各種提示方法：

1. Input-Output (IO) 提示

輸入序列后，直接用語(yǔ)言模型獲取輸出，不添加任何中間思考過(guò)程。

2. 思維鏈（Chain-of-Thought, CoT）

在輸入和輸出之間引入多個(gè)中間思維狀態(tài)，相比IO方法，可以顯著提升語(yǔ)言模型在數(shù)學(xué)難題和通用推理任務(wù)上的性能。

3. 多思維鏈

獨(dú)立生成多條思維鏈，然后根據(jù)預(yù)先指定的評(píng)分指標(biāo)返回最佳輸出結(jié)果的思維鏈。

自一致思維鏈（CoT-SC）方法可以將CoT擴(kuò)展到多條推理路徑，不過(guò)沒(méi)有進(jìn)行單路徑內(nèi)的「局部探索」，例如回溯（backtracking）。

4. 思維樹（Tree of Thoughts, ToT）

ToT將過(guò)程或推理建模為一棵思維樹來(lái)增強(qiáng)CoT-SC方法，單個(gè)樹節(jié)點(diǎn)代表部分解決方案；基于給定的節(jié)點(diǎn)，思維生成器（thought generator）可以構(gòu)造出一定數(shù)量的新節(jié)點(diǎn)，然后用狀態(tài)評(píng)估器（state evaluator）為每個(gè)新節(jié)點(diǎn)生成相應(yīng)評(píng)分。

根據(jù)用例的不同，可以使用LLM自身對(duì)輸出結(jié)果進(jìn)行評(píng)估，也可以利用人工評(píng)分等。

擴(kuò)展樹的過(guò)程中，節(jié)點(diǎn)的調(diào)度取決于使用的搜索算法，如深度優(yōu)先、廣度優(yōu)先。

其他方法如思維分解（thought decomposition）等或多或少都隱含使用了樹的思路。

思維圖（Graph of Thought, GoT）框架

總體來(lái)說(shuō)，GoT包含四部分：

1. 語(yǔ)言模型推理過(guò)程，即在特定上下文中，所有語(yǔ)言模型的思維，以及思維之間的關(guān)系

2. 潛在的思維轉(zhuǎn)換

3. 用于獲取思維評(píng)分的評(píng)估函數(shù)

4. 用于選擇最相關(guān)思維的排序函數(shù)

推理過(guò)程

研究人員將推理過(guò)程建模為一個(gè)有向圖，頂點(diǎn)代表某個(gè)問(wèn)題（初始問(wèn)題、中間問(wèn)題、最終問(wèn)題）的一個(gè)解決方案，有向邊代表使用「出節(jié)點(diǎn)」作為直接輸入構(gòu)造出的思維（入節(jié)點(diǎn)），具體思維的形式取決于用例。

圖節(jié)點(diǎn)的類別也不一定相同，例如在生成任務(wù)中，某些節(jié)點(diǎn)代表「寫一段文字的規(guī)劃」，另一些節(jié)點(diǎn)用來(lái)對(duì)「實(shí)際文本段」進(jìn)行建模，推理過(guò)程是一個(gè)異構(gòu)圖（heterogeneous graph）。

思維轉(zhuǎn)換

基于圖結(jié)構(gòu)，GoT可以在推理中實(shí)現(xiàn)不同的思維轉(zhuǎn)換，也可以叫做graph-enabled transformations.

比如說(shuō)，在寫作任務(wù)中，可以將幾篇輸入文章合并成一個(gè)連貫的摘要；在排序任務(wù)中，可以將幾個(gè)排序后的數(shù)字子數(shù)組（sub-array）合并成一個(gè)最終的排序數(shù)組。

每次變換操作都包含兩部分：1）反映當(dāng)前推理狀態(tài)的圖，以及2）一個(gè)用到的語(yǔ)言模型。

變換操作會(huì)修改當(dāng)前的圖，添加新的節(jié)點(diǎn)和輸入邊。

為了最大化GoT的表現(xiàn)力，用戶可以指定要?jiǎng)h除的相應(yīng)頂點(diǎn)和邊來(lái)顯式刪除思維；為了節(jié)省上下文空間，用戶可以刪除推理中未來(lái)不改進(jìn)的部分。

1）聚合轉(zhuǎn)換（Aggregation Transformations）

GoT可以將任意多個(gè)思維聚合成一個(gè)新的思維，并將不同思維的優(yōu)勢(shì)結(jié)合起來(lái)。

在最基礎(chǔ)的形式中，只創(chuàng)建一個(gè)新的節(jié)點(diǎn)，其余思維鏈中的節(jié)點(diǎn)作為出節(jié)點(diǎn)連接到新節(jié)點(diǎn)中。

更一般地，該操作還可以聚合推理路徑，也就是組成更長(zhǎng)的推理路徑

2）優(yōu)化轉(zhuǎn)換（Refining Transformations）

可以修改當(dāng)前思維節(jié)點(diǎn)v為一條循環(huán)邊（v, v），代表與原始思維相同迭代思維。

3）生成轉(zhuǎn)換（Generation Transformations）

可以基于已有的單思維節(jié)點(diǎn)生成一個(gè)或多個(gè)新的思維，和之前的推理模式，如ToT或CoT-SC類似。

對(duì)思維進(jìn)行評(píng)分和排序

評(píng)估函數(shù)所需要的數(shù)據(jù)包括受評(píng)估的思維、整個(gè)推理過(guò)程的狀態(tài)以及語(yǔ)言模型，要求全推理過(guò)程可以最大化函數(shù)的通用性。

在對(duì)思維的排序時(shí)，其輸入包括推理過(guò)程、語(yǔ)言模型以及指定返回k個(gè)評(píng)分最高的思維。

系統(tǒng)架構(gòu)&可擴(kuò)展性

GoT架構(gòu)由一組交互模塊組成：

1. 提示器（Prompter）：為L(zhǎng)LM準(zhǔn)備信息

主要負(fù)責(zé)把圖結(jié)構(gòu)編碼進(jìn)提示詞中，GoT架構(gòu)允許用戶根據(jù)不同用例實(shí)現(xiàn)不同的圖編碼，提供全部圖結(jié)構(gòu)訪問(wèn)權(quán)限。

2. 解析器（Parser）：從LLM的回復(fù)中抽取信息

解析器為每個(gè)思維構(gòu)造出一個(gè)思維狀態(tài)（thought state），包含了抽取出的信息，并用于后續(xù)狀態(tài)更新。

3. 評(píng)分模塊（Scoring）：對(duì)LLM回復(fù)進(jìn)行驗(yàn)證和評(píng)分

驗(yàn)證一個(gè)給定的LLM思維是否能夠滿足潛在的正確性條件，然后對(duì)思維進(jìn)行打分。

具體分?jǐn)?shù)可能需要構(gòu)造提示，讓語(yǔ)言模型給出評(píng)價(jià)；對(duì)某些用例來(lái)說(shuō)，人類反饋評(píng)分也可以；如果是排序之類的用例，可能還需要引入局部評(píng)分函數(shù)。

4. 控制器（Controller）：協(xié)調(diào)整個(gè)推理過(guò)程，并決定如何繼續(xù)推理

控制器中包含兩個(gè)重要組件：圖操作（the Graph of Operations, GoO）和圖推理狀態(tài)（GRS）。

其中GoO是一個(gè)靜態(tài)結(jié)構(gòu)，指定了給定任務(wù)上的圖分解過(guò)程，即規(guī)定了可用于LLM思維轉(zhuǎn)換的操作，以及思維之間的順序和依賴關(guān)系；每個(gè)操作對(duì)象都知道自己的前置操作和后繼操作。

GRS是一個(gè)動(dòng)態(tài)結(jié)構(gòu)，用來(lái)維護(hù)LLM推理過(guò)程進(jìn)行中的狀態(tài)，包括所有思維的歷史及狀態(tài)。

示例用例

1. 排序

比如任務(wù)是對(duì)有重復(fù)的0-9數(shù)字序列進(jìn)行排序，直接輸入的話，語(yǔ)言模型無(wú)法對(duì)超過(guò)一定長(zhǎng)度的序列正確排序。

在GoT框架中，研究人員采用基于合并的排序方法：

首先將輸入的數(shù)字序列分解為多個(gè)子矩陣；然后對(duì)子矩陣分別進(jìn)行排序；再將子矩陣進(jìn)行排序；最后將所有子矩陣合并，得到最終結(jié)果。

在這個(gè)用例中，LLM思維就是一串有序的數(shù)字序列。

為了對(duì)LLM的輸出進(jìn)行評(píng)分，假定輸入序列a的長(zhǎng)度為n，輸出序列b的長(zhǎng)度為m，可以將誤差范圍定義為：

X表示錯(cuò)誤排序的連續(xù)數(shù)字對(duì)的數(shù)量，如果相鄰兩個(gè)數(shù)字排序錯(cuò)誤，即左邊的數(shù)字大于右邊，則X加一。

Y表示，輸出序列中的數(shù)字頻率，與輸入序列頻率的吻合程度。

2. 關(guān)鍵詞計(jì)數(shù)任務(wù)

GoT框架將輸入文本分割成多個(gè)段落，計(jì)數(shù)每個(gè)段落中的關(guān)鍵字，并聚合子結(jié)果。

段落的數(shù)量可以預(yù)先定義，也可以留給LLM分割，或者將每個(gè)句子視為一個(gè)單獨(dú)的段落。

為了獲得對(duì)思維的評(píng)分，首先需要對(duì)每個(gè)關(guān)鍵字推導(dǎo)出計(jì)數(shù)和正確計(jì)數(shù)之間的絕對(duì)差值，然后將所有差值相加，并得到最終分?jǐn)?shù)。

3. 文檔合并

該任務(wù)的目標(biāo)是基于幾個(gè)內(nèi)容部分重疊的輸入文檔生成一個(gè)新的保密協(xié)議（NDA）文檔，盡量減少重復(fù)，同時(shí)最大限度地保留信息，可以廣泛應(yīng)用于法律程序等領(lǐng)域。

為了給解決方案打分，研究人員要求語(yǔ)言模型查詢兩個(gè)值（每個(gè)值三次，取平均值），第一個(gè)值對(duì)應(yīng)于解決方案冗余（10表示沒(méi)有冗余，0表示至少一半的信息是冗余的），第二個(gè)值代表信息保留（10表示保留了所有信息，0表示沒(méi)有保留），然后計(jì)算調(diào)和平均值。

延遲與思維量的權(quán)衡

GoT在延遲（思維圖中達(dá)到給定最終思維的跳數(shù)）和思維量（volume，思維圖中存在通往某個(gè)思維的路徑數(shù)量）之間的權(quán)衡，也比之前的提示方案要好。

假設(shè)輸出一個(gè)思維的時(shí)間成本為O(1)，每個(gè)提示方案的總成本固定為Θ（n）：

1. CoT-SC由源自單個(gè)起始思維的k個(gè)獨(dú)立鏈組成；

2. ToT是一個(gè)完整的k-ary樹；

3. 在GoT中，在完整k-ary樹的葉子處與一個(gè)大小相同但邊反向的鏡像k-ary樹連接起來(lái)；

可以看到，雖然CoT-SC提供的思維量為N，但代價(jià)是高延遲（N）；CoT-SC將延遲降低了k倍（對(duì)應(yīng)于分支因子），但同時(shí)也將容量降低了k倍。

ToT提供logk N的延遲，但容量也下降了；

GoT是唯一一個(gè)同時(shí)具有l(wèi)ogk N的低延遲和高容量N的方案，可能是由于GoT利用聚合思想，可以從分解圖中的其他中間思維獲取到最終思維。

實(shí)驗(yàn)結(jié)果

總的來(lái)說(shuō)，GoT在排序、找集合交集、關(guān)鍵詞計(jì)數(shù)和文檔合并任務(wù)上，其結(jié)果質(zhì)量要比基線模型更好，并且推理成本也更低。

GoT vs. ToT

在所有任務(wù)中，GoT都比ToT（樹的分支更多、深度較淺）和ToT2（樹的分支少、深度更深）的性能更好。ToT通常比ToT2的質(zhì)量更高，但消耗也更大。

相比ToT，GoT方法將中值誤差降低了約62%，從而實(shí)現(xiàn)了更高的排序質(zhì)量，并且運(yùn)行成本降低了31%以上；優(yōu)勢(shì)主要是因?yàn)镚oT能夠?qū)?fù)雜的任務(wù)分解成更簡(jiǎn)單的子任務(wù)，獨(dú)立解決這些子任務(wù)，然后逐步將這些結(jié)果合并成最終結(jié)果。

GoT vs. IO / CoT

GoT的質(zhì)量更高，對(duì)于排序（P=64）任務(wù)，GoT的中值誤差分別比CoT和IO低約65%和約83%，不過(guò)GoT和ToT的運(yùn)行成本遠(yuǎn)高于IO和CoT

隨著問(wèn)題規(guī)模P的增加，GoT相比其他基線來(lái)說(shuō)質(zhì)量提升更大。

總的來(lái)說(shuō)，這個(gè)分析說(shuō)明了GoT確實(shí)非常適合復(fù)雜的問(wèn)題案例，因?yàn)橥评碚{(diào)度通常會(huì)隨著問(wèn)題規(guī)模的增長(zhǎng)而變得更加復(fù)雜。