2022年，前谷歌大腦華人科學(xué)家Jason Wei在一篇思維鏈的開山之作中首次提出，CoT可以增強(qiáng)LLM的推理能力。

但即便有了思維鏈，LLM有時(shí)也會(huì)在非常簡單的問題上犯錯(cuò)。

最近，來自普林斯頓大學(xué)和Google DeepMind研究人員提出了一種全新的語言模型推理框架——「思維樹」（ToT）。

【資料圖】

ToT將當(dāng)前流行的「思維鏈」方法泛化到引導(dǎo)語言模型，并通過探索文本（思維）的連貫單元來解決問題的中間步驟。

論文地址:https://arxiv.org/abs/2305.10601

項(xiàng)目地址:https://github.comandroid/kyegomez/tree-of-thoughts

簡單來說，「思維樹」可以讓LLM:

自己給出多條不同的推理路徑

分別進(jìn)行評估后，決定下一步的行動(dòng)方案

在必要時(shí)向前或向后追溯，以便實(shí)現(xiàn)進(jìn)行全局的決策

論文實(shí)驗(yàn)結(jié)果顯示，ToT顯著提高了LLM在三個(gè)新任務(wù)（24點(diǎn)游戲，創(chuàng)意寫作，迷你填字游戲）中的問題解決能力。

比如，在24點(diǎn)游戲中，GPT-4只解決了4%的任務(wù)，但ToT方法的成功率達(dá)到了74%。

讓LLM「反復(fù)思考」

用于生成文本的大語言模型GPT、PaLM，現(xiàn)已經(jīng)證明能夠執(zhí)行各種廣泛的任務(wù)。

所有這些模型取得進(jìn)步的基礎(chǔ)仍是最初用于生成文本的「自回歸機(jī)制」，以從左到右的方式一個(gè)接一個(gè)地進(jìn)行token級的決策。

那么，這樣一個(gè)簡單的機(jī)制能否足以建立一個(gè)通向「解決通用問題的語言模型」?如果不是，哪些問題會(huì)挑戰(zhàn)當(dāng)前的范式，真正的替代機(jī)制應(yīng)該是什么?

恰恰關(guān)于「人類認(rèn)知」的文獻(xiàn)為這個(gè)問題提供了一些線索。

「雙重過程」模型的研究表明，人類有兩種決策模式:快速、自動(dòng)、無意識(shí)模式——「系統(tǒng)1」和緩慢、深思熟慮、有意識(shí)模式——「系統(tǒng)2」。

語言模型簡單關(guān)聯(lián)token級選擇可以讓人聯(lián)想到「系統(tǒng)1」，因此這種能力可能會(huì)從「系統(tǒng)2」規(guī)劃過程中增強(qiáng)。

「系統(tǒng)1」可以讓LLM保持和探索當(dāng)前選擇的多種替代方案，而不僅僅是選擇一個(gè)，而「系統(tǒng)2js」評估其當(dāng)前狀態(tài)，并積極地預(yù)見、回溯以做出更全局的決策。

為了設(shè)計(jì)這樣一個(gè)規(guī)劃過程，研究者便追溯到人工智能和認(rèn)知科學(xué)的起源，從科學(xué)家Newell、Shaw和Simon在20世紀(jì)50年代開始探索的規(guī)劃過程中汲取靈感。

Newell及其同事將問題解決描述為「通過組合問題空間進(jìn)行搜索」，表示為一棵樹。

這個(gè)觀點(diǎn)突出了現(xiàn)有使用LLM解決通用問題方法的2個(gè)主要缺點(diǎn):

1. 局部來看，LLM沒有探索思維過程中的不同延續(xù)——樹的分支。

2. 總的來看，LLM不包含任何類型的計(jì)劃、前瞻或回溯，來幫助評估這些不同的選擇。

為了解決這些問題，研究者提出了用語言模型解決通用問題的思維樹框架（ToT），讓LLM可以探索多種思維推理路徑。

ToT四步法

當(dāng)前，現(xiàn)有的方法，如IO、CoT、CoT-SC，通過采樣連續(xù)的語言序列進(jìn)行問題解決。

而ToT主動(dòng)維護(hù)了一個(gè)「思維樹」。每個(gè)矩形框代表一個(gè)思維，并且每個(gè)思維都是一個(gè)連貫的語言序列，作為解決問題的中間步驟。

ToT將任何問題定義為在樹上進(jìn)行搜索，其中每個(gè)節(jié)點(diǎn)都是一個(gè)狀態(tài)

，表示到目前為止輸入和思維序列的部分解。

ToT執(zhí)行一個(gè)具體任務(wù)時(shí)需要回答4個(gè)問題:

如何將中間過程分解為思維步驟;如何從每個(gè)狀態(tài)生成潛在的想法;如何啟發(fā)性地評估狀態(tài);使用什么搜索算法。

1. 思維分解

CoT在沒有明確分解的情況下連貫抽樣思維，而ToT利用問題的屬性來設(shè)計(jì)和分解中間的思維步驟。

根據(jù)不同的問題，一個(gè)想法可以是幾個(gè)單詞（填字游戲） ，一條方程式(24點(diǎn)) ，或者一整段寫作計(jì)劃(創(chuàng)意寫作)。

一般來說，一個(gè)想法應(yīng)該足夠「小」，以便LLM能夠產(chǎn)生有意義、多樣化的樣本。比如，生成一本完整的書通常太「大」而無法連貫 。

但一個(gè)想法也應(yīng)該「大」，足以讓LLM能夠評估其解決問題的前景。例如，生成一個(gè)token通常太「小」而無法評估。

2.思維生成器

給定樹狀態(tài)

，通過2種策略來為下一個(gè)思維步驟生成k個(gè)候選者。

（a）從一個(gè)CoT提示采樣

思維:

在思維空間豐富（比如每個(gè)想法都是一個(gè)段落），并且

導(dǎo)致多樣性時(shí)，效果更好。

（b）使用「proposal prompt」按順序提出想法:

。這在思維空間受限制（比如每個(gè)思維只是一個(gè)詞或一行）時(shí)效果更好，因此在同一上下文中提出不同的想法可以避免重復(fù)。

3.狀態(tài)求值器

給定不同狀態(tài)的前沿，狀態(tài)評估器評估它們解決問題的進(jìn)展，作為搜索算法的啟發(fā)式算法，以確定哪些狀態(tài)需要繼續(xù)探索，以及以何種順序探索。

雖然啟發(fā)式算法是解決搜索問題的標(biāo)準(zhǔn)方法，但它們通常是編程的（DeepBlue）或?qū)W習(xí)的(AlphaGo)。這里，研究者提出了第三種選擇，通過LLM有意識(shí)地推理狀態(tài)。

在適用的情況下，這種深思熟慮的啟發(fā)式方法可以比程序規(guī)則更靈活，比學(xué)習(xí)模型更有效率。與思維生成器，研究人員也考慮2種策略來獨(dú)立或一起評估狀態(tài):對每個(gè)狀態(tài)獨(dú)立賦值;跨狀態(tài)投票。

4.搜索算法

最后，在ToT框架中，人們可以根據(jù)樹的結(jié)構(gòu)，即插即用不同的搜索算法。

研究人員在此探索了2個(gè)相對簡單的搜索算法:

算法1——廣度優(yōu)先搜索（BFS），每一步維護(hù)一組b最有希望的狀態(tài)。

算法2——深度優(yōu)先搜索（DFS），首先探索最有希望的狀態(tài)，直到達(dá)到最終的輸出

，或者狀態(tài)評估器認(rèn)為不可能從當(dāng)前的

為閾值

解決問題。在這兩種情況下，DFS都會(huì)回溯到s的父狀態(tài)以繼續(xù)探索。

由上，LLM通過自我評估和有意識(shí)的決策，來實(shí)現(xiàn)啟發(fā)式搜索的方法是新穎的。

實(shí)驗(yàn)

為此，團(tuán)隊(duì)提出了三個(gè)任務(wù)用于測試——即使是最先進(jìn)的語言模型GPT-4，在標(biāo)準(zhǔn)的IO提示或思維鏈（CoT）提示下，都是非常富有挑戰(zhàn)的。

24點(diǎn)（Game of24）

24點(diǎn)是一個(gè)數(shù)學(xué)推理游戲，目標(biāo)是使用4個(gè)數(shù)字和基本算術(shù)運(yùn)算（+-*/）來得到24。

例如，給定輸入「491013」，答案的輸出可能是「（10-4）*(13-9)=24」。

ToT設(shè)置

團(tuán)隊(duì)將模型的思維過程分解為3個(gè)步驟，每個(gè)步驟都是一個(gè)中間方程。

如圖2（a）所示，在每個(gè)節(jié)點(diǎn)上，提取「左邊」的數(shù)字并提示LLM生成可能的下一步。(每一步給出的「提議提示」都相同)

其中，團(tuán)隊(duì)在ToT中進(jìn)行寬度優(yōu)先搜索（BFS），并在每一步都保留最好的b=5個(gè)候選項(xiàng)。

如圖2（b）所示，提示LLM評估每個(gè)思維候選項(xiàng)是「肯定/可能/不可能」達(dá)到24?；凇高^大/過小」的常識(shí)消除不可能的部分解決方案，保留剩下的「可能」項(xiàng)。

結(jié)果

如表2所示，IO，CoT和CoT-SC提示方法在任務(wù)上的表現(xiàn)不佳，成功率僅為7.3%，4.0%和9.0%。相比之下，ToT在廣度為b=1時(shí)已經(jīng)達(dá)到了45%的成功率，而在b=5時(shí)達(dá)到了74%。

團(tuán)隊(duì)還考慮了IO/CoT的預(yù)測設(shè)置，通過使用最佳的k個(gè)樣本（1≤k≤100）來計(jì)算成功率，并在圖3(a)中繪出5個(gè)成功率。

不出所料，CoT比IO擴(kuò)展得更好，最佳的100個(gè)CoT樣本達(dá)到了49%的成功率，但仍然比在ToT中探索更多節(jié)點(diǎn)（b>1）要差。

錯(cuò)誤分析

圖3（b）分析了CoT和ToT樣本在哪一步失敗了任務(wù)，即思維(在CoT中)或所有b個(gè)思維(在ToT中)都是無效的或無法達(dá)到24。

值得注意的是，大約60%的CoT樣本在第一步就已經(jīng)失敗了，或者說，是前三個(gè)詞（例如「4+9」）。

創(chuàng)意寫作

接下來，團(tuán)隊(duì)設(shè)計(jì)了一個(gè)創(chuàng)意寫作任務(wù)。

其中，輸入是四個(gè)隨機(jī)句子，輸出應(yīng)該是一個(gè)連貫的段落，每段都以四個(gè)輸入句子分別結(jié)束。這樣的任務(wù)開放且富有探索性，挑戰(zhàn)創(chuàng)造性思維以及高級規(guī)劃。

值得注意的是，團(tuán)隊(duì)還在每個(gè)任務(wù)的隨機(jī)IO樣本上使用迭代-優(yōu)化（k≤js5）方法，其中LLM基于輸入限制和最后生成的段落來判斷段落是否已經(jīng)「完全連貫」，如果不是，就生成一個(gè)優(yōu)化后的。

ToT設(shè)置

團(tuán)隊(duì)構(gòu)建了一個(gè)深度為2（只有1個(gè)中間思維步驟）的ToT。

LLM首先生成k=5的計(jì)劃并投票選擇最佳的一個(gè)（圖4），然后根據(jù)最佳計(jì)劃生成k=5的段落，然后投票選擇最佳的一個(gè)。

一個(gè)簡單的zero-shot投票提示（「分析以下選擇，然后得出哪個(gè)最有可能實(shí)現(xiàn)指令」）被用來在兩個(gè)步驟中抽取5票。

結(jié)果

圖5（a）顯示了100個(gè)任務(wù)中的GPT-4平均分?jǐn)?shù)，其中ToT(7.56)被認(rèn)為比IO(6.19)和CoT(6.93)平均生成更連貫的段落。

雖然這樣的自動(dòng)評測可能會(huì)有噪音，但圖5（b）通過顯示人類在100個(gè)段落對中有41個(gè)更喜歡ToT而只有21個(gè)更喜歡CoT(其他38對被認(rèn)為「同樣連貫」)來確認(rèn)這一發(fā)現(xiàn)。

最后，迭代優(yōu)化在這個(gè)自然語言任務(wù)上更有效——將IO連貫性分?jǐn)?shù)從6.19提高到7.67，將ToT連貫性分?jǐn)?shù)從7.56提高到7.91。

團(tuán)隊(duì)認(rèn)為它可以被看作是在ToT框架下生成思維的第三種方法，新的思維可以通過優(yōu)化舊的思維而產(chǎn)生，而不是i.i.d.或順序生成。

迷你填字游戲

在24點(diǎn)游戲和創(chuàng)意寫作中，ToT相對較淺——最多需要3個(gè)思維步驟就能完成輸出。

最后，團(tuán)隊(duì)決定通過55的迷你填字游戲，來設(shè)置一個(gè)更難的問題。

同樣，目標(biāo)不僅僅是解決任務(wù)，而是研究LLM作為一個(gè)通用問題解決者的極限。通過窺視自己的思維，以有目的性的推理作為啟發(fā)，來指導(dǎo)自己的探索。

ToT設(shè)置

團(tuán)隊(duì)利用深度優(yōu)先搜索保持探索最有可能成功的后續(xù)單詞線索，直到狀態(tài)不再有希望，然后回溯到父狀態(tài)以探索替代的思維。

為了使搜索可行，后續(xù)的思維被限制不改變?nèi)魏我烟顚懙膯卧~或字母，這樣ToT最多有10個(gè)中間步驟。

對于思維生成，團(tuán)隊(duì)在每個(gè)狀態(tài)下將所有現(xiàn)有的思維（例如，「h2.motor; h1.tasks」對于圖6(a）中的狀態(tài))轉(zhuǎn)換為剩余線索的字母限制(例如，「v1.To heap: tm___;...」)，從而得到下一個(gè)單詞填寫位置和內(nèi)容的候選。

重要的是，團(tuán)隊(duì)也提示LLM給出不同思維的置信度，并在提案中匯總這些以獲得下一個(gè)要探索的思維的排序列表（圖6(a）)。

對于狀態(tài)評估，團(tuán)隊(duì)類似地將每個(gè)狀態(tài)轉(zhuǎn)換為剩余線索的字母限制，然后評估每個(gè)線索是否可能在給定限制下填寫。

如果任何剩余的線索被認(rèn)為是「不可能」的（例如，「v1. To heap: tm_s_」），那么該狀態(tài)的子樹的探索就被剪枝，并且DFS回溯到其父節(jié)點(diǎn)來探索下一個(gè)可能的候選。

結(jié)果

如表3所示，IO和CoT的提示方法在單詞級成功率上表現(xiàn)不佳，低于16%，而ToT顯著改善了所有指標(biāo)，實(shí)現(xiàn)了60%的單詞級成功率，并解決了20個(gè)游戲中的4個(gè)。

鑒于IO和CoT缺乏嘗試不同線索、改變決策或回溯的機(jī)制，這種改善并不令人驚訝。

局限性與結(jié)論

ToT是一個(gè)讓LLM可以更自主、更智能地做決策和解決問題的框架。

它提高了模型決策的可解釋性以及與人類對齊的機(jī)會(huì)，因?yàn)門oT所生成的表征表形式是可讀的、高級的語言推理，而不是隱式的、低級的token值。

對于那些GPT-4已經(jīng)十分擅長的任務(wù)來說，ToT可能并是不必要的。

此外，像ToT這樣的搜索方法需要更多的資源（如GPT-4API成本）來提高任務(wù)性能，但ToT的模塊化靈活性讓用戶可以自定義這種性能-成本平衡。

不過，隨著LLM被用于更多真實(shí)世界的決策應(yīng)用（如編程、數(shù)據(jù)分析、機(jī)器人技術(shù)等），ToT可以為研究那些即將出現(xiàn)的更為復(fù)雜的任務(wù)，提供新的機(jī)會(huì)。

作者介紹

Shunyu Yao（姚順雨）

論文一作Shunyu Yao是普林斯頓大學(xué)的四年級博士生，此前畢業(yè)于清華大學(xué)的姚班。

他的研究方向是在語言智能體與世界之間建立互動(dòng)，例如玩文字游戲（CALM），網(wǎng)上購物(WebShop)，瀏覽維基百科進(jìn)行推理(ReAct)，或者，基于同樣的想法，用任何工具來完成任何任務(wù)。

在生活中，他喜歡閱讀、籃球、臺(tái)球、旅行和說唱。

Dian Yu

Dian Yu是Google DeepMind的一名研究科學(xué)家。此前，他在加州大學(xué)戴維斯分校獲得了博士學(xué)位，并在紐約大學(xué)獲得了學(xué)士學(xué)位，雙主修計(jì)算機(jī)科學(xué)和金融（還有一點(diǎn)表演）。

他的研究興趣是語言的屬性表征，以及多語言和多模態(tài)的理解，主要專注于對話研究（包括開放領(lǐng)域和任務(wù)導(dǎo)向）。

Yuan Cao

Yuan Cao也是Google DeepMind的一名研究科學(xué)家。此前，他在上海交通大學(xué)獲得了學(xué)士和碩士學(xué)位，并在約翰斯霍普金斯大學(xué)獲得了博士學(xué)位。還曾擔(dān)任過百度的首席架構(gòu)師。

Jeffrey Zhao

Jeffrey Zhao是Google DeepMind的軟件工程師。此前，他在卡內(nèi)基梅隆大學(xué)獲得了學(xué)士和碩士學(xué)位javascript。

參考資料:

https://arxiv.org/abs/2305.10601

關(guān)鍵詞：