摘要：語言模型正越來越多地用于廣泛任務(wù)中的一般問題解決，但在推理過程中，它們?nèi)匀痪窒抻谥鹱旨墑e、從左到右的決策過程。這意味著它們在需要探索、戰(zhàn)略性前瞻，或初始決策起關(guān)鍵作用的任務(wù)中可能表現(xiàn)不佳。為了解決這些挑戰(zhàn)，我們引入了一種新的語言模型推理框架——“思維樹”（Tree of Thoughts，ToT），它推廣了流行的“鏈?zhǔn)剿季S”方法，通過提示語言模型并使其能夠探索作為解決問題中間步驟的連貫文本單元（“思想”）。ToT 允許語言模型通過考慮多種不同的推理路徑并自我評估選擇來進(jìn)行深思熟慮的決策，決定下一步行動(dòng)，同時(shí)在必要時(shí)前瞻或回溯以做出全局性選擇。我們的實(shí)驗(yàn)表明，ToT 顯著增強(qiáng)了語言模型在需要非平凡規(guī)劃或搜索的三項(xiàng)新任務(wù)中的問題解決能力：24點(diǎn)游戲、創(chuàng)意寫作和迷你填字游戲。例如，在24點(diǎn)游戲中，使用鏈?zhǔn)剿季S提示的GPT-4僅解決了4%的任務(wù)，而我們的方法達(dá)到了74%的成功率。所有提示的代碼倉庫： [https://github.com/princeton-nlp/tree-of-thought-llm](https://github.com/princeton-nlp/tree-of-thought-llm)。

1.引言

最初設(shè)計(jì)用于生成文本的大規(guī)模語言模型（LMs），如GPT和PaLM，已經(jīng)被證明能夠執(zhí)行越來越多需要數(shù)學(xué)、符號(hào)、常識(shí)和知識(shí)推理的任務(wù)?；蛟S令人驚訝的是，這些進(jìn)步的基礎(chǔ)仍然是原始的自回歸機(jī)制，用于生成文本，即逐個(gè)令牌地從左到右做出決策。這樣的簡單機(jī)制是否足以構(gòu)建一個(gè)通用問題解決器？如果不是，哪些問題會(huì)挑戰(zhàn)當(dāng)前的范式，應(yīng)該采用哪些替代機(jī)制？

關(guān)于人類認(rèn)知的文獻(xiàn)提供了一些回答這些問題的線索。關(guān)于“二元過程”模型的研究表明，人們在做決定時(shí)有兩種模式——一種是快速、自動(dòng)、無意識(shí)的模式（“系統(tǒng)1”），另一種是慢速、深思熟慮、有意識(shí)的模式（“系統(tǒng)2”）。這些模式以前與機(jī)器學(xué)習(xí)中使用的各種數(shù)學(xué)模型相關(guān)聯(lián)。例如，人類和其他動(dòng)物的強(qiáng)化學(xué)習(xí)研究探討了在什么情況下他們會(huì)進(jìn)行聯(lián)想的“無模型”學(xué)習(xí)或更深思熟慮的“基于模型”的規(guī)劃。LMs的簡單聯(lián)想令牌級別選擇也讓人聯(lián)想到“系統(tǒng)1”，因此可能受益于一個(gè)更深思熟慮的“系統(tǒng)2”規(guī)劃過程的增強(qiáng)，該過程（1）保持并探索當(dāng)前選擇的多種替代方案，而不僅僅是選擇一個(gè)，并且（2）評估其當(dāng)前狀態(tài)并積極前瞻或回溯以做出更全局的決策。

為了設(shè)計(jì)這樣的規(guī)劃過程，我們回到人工智能（和認(rèn)知科學(xué)）的起源，從Newell、Shaw和Simon在20世紀(jì)50年代開始探索的規(guī)劃過程中汲取靈感。Newell和同事將問題解決描述為在組合問題空間中的搜索，表示為樹狀結(jié)構(gòu)。因此，我們提出了“思維樹”（Tree of Thoughts，ToT）框架，以通過語言模型進(jìn)行通用問題解決。如圖1所示，現(xiàn)有方法（詳見下文）采樣用于問題解決的連續(xù)語言序列，而ToT則主動(dòng)維護(hù)一個(gè)思想樹，每個(gè)思想都是一個(gè)連貫的語言序列，作為問題解決的中間步驟。這樣的高級語義單元允許LM通過一種深思熟慮的推理過程自我評估不同中間思想在解決問題方面的進(jìn)展，這個(gè)過程也在語言中體現(xiàn)出來。通過LM自我評估和深思熟慮來實(shí)現(xiàn)搜索啟發(fā)式是新穎的，因?yàn)橐郧暗乃阉鲉l(fā)式要么是編程的，要么是學(xué)習(xí)的。最后，我們將這種基于語言的生成和評估多樣思想的能力與搜索算法（如廣度優(yōu)先搜索（BFS）或深度優(yōu)先搜索（DFS））結(jié)合起來，允許系統(tǒng)地探索思想樹，進(jìn)行前瞻和回溯。

圖1：示意圖展示了使用大型語言模型進(jìn)行問題解決的各種方法。每個(gè)矩形框代表一個(gè)思想，它是一個(gè)連貫的語言序列，作為問題解決的中間步驟。有關(guān)思想如何生成、評估和搜索的具體示例，請參見圖2、圖4和圖6。

在實(shí)證上，我們提出了三種新問題，這些問題即使使用最先進(jìn)的語言模型GPT-4也會(huì)挑戰(zhàn)現(xiàn)有的LM推理方法：24點(diǎn)游戲、創(chuàng)意寫作和填字游戲。這些任務(wù)需要演繹、數(shù)學(xué)、常識(shí)、詞匯推理能力，以及一種系統(tǒng)規(guī)劃或搜索的方法。我們證明了ToT在所有三項(xiàng)任務(wù)上都取得了優(yōu)異的結(jié)果，因?yàn)樗銐蛲ㄓ煤挽`活，能夠支持不同層次的思想，不同的生成和評估思想的方式，以及適應(yīng)不同問題性質(zhì)的不同搜索算法。我們還通過系統(tǒng)性消融分析了這些選擇如何影響模型性能，并討論了更好地訓(xùn)練和使用LMs的未來方向。

2.背景

我們首先形式化一些使用大型語言模型進(jìn)行問題解決的現(xiàn)有方法，這些方法啟發(fā)了我們的方法，并將在后文進(jìn)行比較。我們用 p_θ 表示一個(gè)帶有參數(shù) θ 的預(yù)訓(xùn)練語言模型，用小寫字母 x, y, z, s, ... 表示一個(gè)語言序列，即 x = (x[1], ..., x[n])，其中每個(gè) x[i] 是一個(gè)令牌，因此 p_θ(x) = ∏_i=1ⁿ p_θ(x[i]|x[1...i])。我們用大寫字母 S, ...表示一個(gè)語言序列的集合。

輸入-輸出（IO）提示是將問題輸入 x 轉(zhuǎn)換為輸出 y 的最常見方法： y~p_θ(y|prompt_IO(x))，其中 prompt_IO(x) 將輸入 x 包裝成任務(wù)指令和/或少量的輸入-輸出示例。為了簡單起見，我們將 p_θ^prompt(output | input) = p_θ(output | prompt(input))，這樣IO提示可以形式化為 y~ p_θ^IO(y|x)。

鏈?zhǔn)剿季S（CoT）提示被提出用于解決輸入 x 到輸出 y 的映射非平凡的情況（例如，當(dāng) x 是一個(gè)數(shù)學(xué)問題而 y 是最終的數(shù)值答案時(shí)）。關(guān)鍵思想是引入一系列思想 z₁, ..., z_n 來連接 x 和 y，其中每個(gè) z_i 是一個(gè)連貫的語言序列，作為問題解決的有意義的中間步驟（例如，z_i 可能是數(shù)學(xué)問答中的中間方程）。為了使用CoT解決問題，每個(gè)思想 z_i ~ p^CoT_θ(z_i| x, z_{1 ... i-}1) 依次被采樣，然后輸出 y ~p^CoT_θ(y|x, z_{1 ... n})。在實(shí)際中，[z_{1 ... n}, y] ~ p^CoT_θ(z_{1 ... n}, y|x) 被作為一個(gè)連續(xù)的語言序列采樣，思想的分解（例如每個(gè) z_i 是一個(gè)短語、一句話還是一段話）是模糊的。

自一致鏈?zhǔn)剿季S（CoT-SC）是一種集成方法，它采樣 k 個(gè)獨(dú)立同分布的思想鏈：[z⁽ⁱ⁾_{1 ... n}, y⁽ⁱ⁾] ~ p^CoT_θ(z_{1 ... n}, y|x) (i = 1 ... k)，然后返回最頻繁的輸出：arg max_y {i | y⁽ⁱ⁾ = y}。CoT-SC改進(jìn)了CoT，因?yàn)橥粏栴}通常有不同的思維過程（例如證明同一理論的不同方法），通過探索更豐富的思想集可以使輸出決策更為準(zhǔn)確。然而，在每個(gè)鏈中沒有對不同思想步驟的局部探索，并且“最頻繁”啟發(fā)法僅在輸出空間有限（例如多選問答）時(shí)適用。

3. 思維樹：利用LM進(jìn)行深思熟慮的解決問題

一個(gè)真正的問題解決過程涉及重復(fù)使用現(xiàn)有信息進(jìn)行探索，從而揭示更多信息，直到最終發(fā)現(xiàn)解決方案?！?Newell等人

關(guān)于人類問題解決的研究表明，人們在組合問題空間中進(jìn)行搜索——一個(gè)樹狀結(jié)構(gòu)，其中節(jié)點(diǎn)代表部分解決方案，分支對應(yīng)修改它們的操作。選擇哪個(gè)分支由啟發(fā)式方法決定，這些方法有助于導(dǎo)航問題空間并指導(dǎo)問題解決者走向解決方案。這種觀點(diǎn)突顯了現(xiàn)有使用LMs解決一般問題的方法的兩個(gè)主要缺點(diǎn)：1）在局部，他們沒有在思想過程的不同延續(xù)中進(jìn)行探索——樹的分支。2）在全局，他們沒有結(jié)合任何類型的規(guī)劃、前瞻或回溯來幫助評估這些不同的選項(xiàng)——這種啟發(fā)式指導(dǎo)的搜索似乎是人類問題解決的特征。

為了解決這些缺點(diǎn)，我們引入了思維樹（Tree of Thoughts，ToT），一種允許LMs在思想路徑上進(jìn)行多路徑探索的范式。ToT將任何問題框架化為樹上的搜索，其中每個(gè)節(jié)點(diǎn)是一個(gè)狀態(tài) s = [x, z_1···i]，表示帶有輸入和迄今為止的思想序列的部分解決方案。ToT的具體實(shí)現(xiàn)涉及回答四個(gè)問題：

1. 如何將中間過程分解為思想步驟；2. 如何從每個(gè)狀態(tài)生成潛在思想；3. 如何啟發(fā)式地評估狀態(tài)；4. 使用哪種搜索算法。

1. 思維分解。雖然CoT在沒有明確分解的情況下連貫地采樣思維，ToT利用問題屬性設(shè)計(jì)并分解中間思維步驟。如表1所示，根據(jù)不同問題，思維可以是幾個(gè)單詞（填字游戲），一個(gè)方程式（24點(diǎn)游戲），或整段寫作計(jì)劃（創(chuàng)意寫作）。一般而言，思維應(yīng)該足夠“小”，以便LMs能夠生成有前途且多樣的樣本（例如，生成整本書通常太“大”而不連貫），但也要足夠“大”，以便LMs能夠評估其解決問題的前景（例如，生成一個(gè)令牌通常太“小”而無法評估）。

2. 思維生成器 G(p_θ, s, k)。給定樹狀態(tài) s = [x, z_1···i]，我們考慮兩種策略來生成下一個(gè)思維步驟的 k 個(gè)候選項(xiàng)：

3. 狀態(tài)評估器 V (p_θ, S)。給定不同狀態(tài)的前沿，狀態(tài)評估器評估它們在解決問題方面的進(jìn)展，作為搜索算法確定哪些狀態(tài)繼續(xù)探索以及順序的啟發(fā)式方法。雖然啟發(fā)式方法是解決搜索問題的標(biāo)準(zhǔn)方法，但它們通常是編程的（例如DeepBlue）或?qū)W習(xí)的（例如AlphaGo）。我們提出了第三種替代方案，通過使用LM對狀態(tài)進(jìn)行深思熟慮的推理。當(dāng)適用時(shí)，這種深思熟慮的啟發(fā)式方法比編程規(guī)則更靈活，比學(xué)習(xí)模型更高效。類似于思想生成器，我們考慮兩種策略來獨(dú)立或共同評估狀態(tài)：

對于這兩種策略，我們可以多次提示LM以匯總值或投票結(jié)果，以時(shí)間/資源/成本換取更真實(shí)/穩(wěn)健的啟發(fā)式。

4. 搜索算法。最后，在ToT框架內(nèi)，可以根據(jù)樹結(jié)構(gòu)使用不同的搜索算法。我們探索了兩種相對簡單的搜索算法，并將更高級的算法（例如A，MCTS）留待未來工作：

從概念上講，ToT作為使用LMs進(jìn)行一般問題解決的方法有幾個(gè)好處：（1）通用性。IO，CoT，CoT-SC和自我改進(jìn)可以看作ToT的特例（即有限深度和廣度的樹；圖1）。（2）模塊化?；A(chǔ)LM以及思想的分解、生成、評估和搜索過程都可以獨(dú)立變化。（3）適應(yīng)性?？梢赃m應(yīng)不同的問題屬性、LM能力和資源限制。（4）便利性。不需要額外的訓(xùn)練，只需一個(gè)預(yù)訓(xùn)練的LM即可。下一節(jié)將展示這些概念上的好處如何轉(zhuǎn)化為在不同問題上強(qiáng)大的實(shí)證性能。

4.實(shí)驗(yàn)

我們提出了三個(gè)任務(wù)，即使使用最新的語言模型GPT-4 [23]，采用標(biāo)準(zhǔn)的輸入輸出提示或思維鏈（CoT）提示也很難完成。我們展示了在思維樹（ToT）中進(jìn)行有目的的搜索如何產(chǎn)生更好的結(jié)果，更重要的是，展示了使用語言模型解決需要搜索或規(guī)劃的問題的新穎而有前途的方法。除非另有說明，我們使用具有0.7采樣溫度的GPT-4的Chat Completion模式進(jìn)行實(shí)驗(yàn)。

4.1 24點(diǎn)游戲

24點(diǎn)游戲是一個(gè)數(shù)學(xué)推理挑戰(zhàn)，目標(biāo)是使用4個(gè)數(shù)字和基本的算術(shù)運(yùn)算（加減乘除）得到24。例如，給定輸入“4 9 10 13”，一個(gè)解決方案輸出可以是“(10 - 4) (13 - 9) = 24”。

任務(wù)設(shè)置：我們從4nums.com獲取數(shù)據(jù)，該網(wǎng)站有1362個(gè)按人類解決時(shí)間從易到難排序的游戲，并使用索引為901-1000的相對較難的游戲子集進(jìn)行測試。對于每個(gè)任務(wù)，如果輸出是一個(gè)等于24的有效方程，并且使用輸入數(shù)字各一次，我們就認(rèn)為任務(wù)成功。我們報(bào)告100個(gè)游戲的成功率作為指標(biāo)。

圖2：在24點(diǎn)游戲中的思維樹（ToT）。語言模型用于(a)思維生成和(b)評估。

（注釋：在24點(diǎn)游戲中應(yīng)用思維樹（ToT）方法來生成和評估語言模型（LM）的思維。這種方法分為兩個(gè)主要步驟：（a）思維生成和（b）思維評估。以下是詳細(xì)的工作原理講解：

1. 輸入和初始狀態(tài)

- 輸入是一組數(shù)字，例如“4 9 10 13”。

- 目標(biāo)是通過基本的算術(shù)運(yùn)算（加、減、乘、除）將這些數(shù)字組合成24。

2. 思維生成（Propose Prompt）

- 步驟 (a): 生成下一步的可能操作。

- 語言模型（LM）根據(jù)輸入提示生成可能的下一步操作。輸入提示（Propose Prompt）包含一個(gè)示例輸入“4 9 10 13”，并要求模型生成可能的下一步操作。

- 模型可能生成的操作包括例如“4 + 9 = 13（剩下：10 13 13）”和“10 - 4 = 6（剩下：6 9 13）”。

3. 思維評估（Value Prompt）

- 步驟 (b): 評估生成的操作的有效性。

- 語言模型（LM）根據(jù)評估提示（Value Prompt）對生成的操作進(jìn)行評估。評估提示要求模型判斷給定的數(shù)字是否能達(dá)到24，結(jié)果分為“確定（sure）”、“可能（likely）”或“不可能（impossible）”。

- 例如，模型可能評估“10 14：10 + 14 = 24”為“確定（sure）”，并給出進(jìn)一步的操作建議。

4. 思維樹的構(gòu)建

- 圖的左側(cè)展示了一個(gè)思維樹的分支結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)表示一個(gè)操作及其剩余數(shù)字。

- 例如，起始節(jié)點(diǎn)是“4 9 10 13”，通過“10 - 4 = 6（剩下：6 9 13）”和“4 + 9 = 13（剩下：10 13 13）”生成了兩個(gè)子節(jié)點(diǎn)。

- 每個(gè)子節(jié)點(diǎn)繼續(xù)生成進(jìn)一步的操作，形成分支，例如“13 - 6 = 7（剩下：7 9）”和“13 - 9 = 4（剩下：4 6）”。

5. 操作的具體評估

- 圖的右側(cè)展示了模型在生成和評估思維過程中的具體操作。

- 思維生成：模型生成具體操作如“4 + 9 = 13（剩下：10 13 13）”和“10 - 4 = 6（剩下：6 9 13）”。

- 思維評估：模型評估每個(gè)生成操作的有效性。例如，模型可能會(huì)評估“(13 - 10) * 13 = 39”和“10 + 13 + 13 = 36”為不可能達(dá)到24，標(biāo)記為“不可能（impossible）”。

6. 結(jié)果和決策

- 基于模型的生成和評估，最終選擇最有可能達(dá)到24的操作路徑。

- 例如，經(jīng)過幾輪操作和評估后，模型可能選擇一條路徑如“4 * 6 = 24（剩下：24）”，并確認(rèn)這是一個(gè)成功的操作。

結(jié)論

通過這種有目的的搜索和評估，思維樹（ToT）方法能夠更有效地解決24點(diǎn)游戲等需要多步驟規(guī)劃和決策的問題。每一步生成和評估的結(jié)合，使得模型能夠排除不可能的路徑，集中資源在最有前途的操作上，提高了問題解決的效率和成功率。）

基線：我們使用具有5個(gè)上下文示例的標(biāo)準(zhǔn)輸入輸出（IO）提示。對于思維鏈（CoT）提示，我們?yōu)槊總€(gè)輸入輸出對增加了3個(gè)中間方程，每個(gè)方程操作兩個(gè)剩余數(shù)字。例如，給定輸入“4 9 10 13”，思維可能是“13 - 9 = 4（剩下：4 4 10）；10 - 4 = 6（剩下：4 6）；4  6 = 24（剩下：24）”。對于每個(gè)游戲，我們抽樣100次IO和CoT提示以獲得平均性能。我們還考慮了一個(gè)CoT自洽基線，它從100個(gè)CoT樣本中選出多數(shù)輸出，并在IO樣本基礎(chǔ)上進(jìn)行最多10次迭代的迭代精煉方法。在每次迭代中，如果輸出不正確，語言模型將根據(jù)所有先前的歷史生成“反思你的錯(cuò)誤并生成改進(jìn)的答案”。注意，它使用關(guān)于方程正確性的真實(shí)反饋信號(hào)。

ToT設(shè)置：為了將24點(diǎn)游戲框架化為ToT，自然地將思維分解為3步，每步一個(gè)中間方程。如圖2(a)所示，在每個(gè)樹節(jié)點(diǎn)，我們提取剩余數(shù)字并提示語言模型提出一些可能的下一步。同樣的“建議提示”用于所有3個(gè)思維步驟，盡管它只有一個(gè)帶有4個(gè)輸入數(shù)字的示例。我們在ToT中執(zhí)行寬度優(yōu)先搜索（BFS），在每一步我們保留最好的5個(gè)候選者。為了在ToT中進(jìn)行有目的的BFS，如圖2(b)所示，我們提示語言模型評估每個(gè)思維候選者關(guān)于到達(dá)24的“確定/可能/不可能”。目的是在少量前瞻試驗(yàn)內(nèi)促進(jìn)正確的部分解決方案，并基于“太大/太小”的常識(shí)消除不可能的部分解決方案，并保留其余的“可能”。我們?yōu)槊總€(gè)思維抽樣3次。

結(jié)果：如表2所示，IO、CoT和CoT-SC提示方法在該任務(wù)上的表現(xiàn)很差，成功率僅為7.3%、4.0%和9.0%。相比之下，寬度為1的ToT成功率已達(dá)到45%，而寬度為5時(shí)成功率達(dá)到74%。我們還考慮了IO/CoT的Oracle設(shè)置，通過使用最好的k個(gè)樣本（1 ≤ k ≤ 100）計(jì)算成功率。為了比較IO/CoT（最佳k樣本）與ToT，我們考慮計(jì)算在ToT中每個(gè)任務(wù)訪問的樹節(jié)點(diǎn)數(shù)在b = 1 ··· 5范圍內(nèi)，并在圖3(a)中繪制5個(gè)成功率，將IO/CoT（最佳k樣本）視為在bandit中訪問k個(gè)節(jié)點(diǎn)。不出所料，CoT比IO擴(kuò)展得更好，100個(gè)CoT樣本中的最佳樣本成功率達(dá)到49%，但仍遠(yuǎn)不及在ToT中探索更多節(jié)點(diǎn)（b > 1）。

錯(cuò)誤分析：圖3(b)分解了CoT和ToT樣本在任務(wù)中的失敗步驟，即思維鏈中的思維（在CoT中）或所有b個(gè)思維（在ToT中）無效或不可能達(dá)到24。值得注意的是，大約60%的CoT樣本在生成第一步或等效的前三個(gè)單詞（例如“4 + 9”）后已經(jīng)失敗。這凸顯了直接從左到右解碼的問題。

4.2 創(chuàng)意寫作

接下來，我們設(shè)計(jì)了一個(gè)創(chuàng)意寫作任務(wù)，輸入為4個(gè)隨機(jī)句子，輸出應(yīng)為一個(gè)連貫的段落，其中4個(gè)段落分別以4個(gè)輸入句子結(jié)尾。這樣的任務(wù)是開放性和探索性的，挑戰(zhàn)了創(chuàng)意思維和高層次的規(guī)劃能力。

任務(wù)設(shè)置：我們從randomwordgenerator.com上隨機(jī)抽取句子形成100個(gè)輸入，每個(gè)輸入約束沒有標(biāo)準(zhǔn)答案。由于我們發(fā)現(xiàn)GPT-4大多數(shù)情況下能遵循輸入約束，我們重點(diǎn)評估段落連貫性，采用兩種方式：使用GPT-4零樣本提示提供1-10的標(biāo)量評分，或使用人工判斷比較不同方法的輸出對。對于前者，我們對每個(gè)任務(wù)輸出抽取5個(gè)評分并取平均值，這5個(gè)評分通常一致，輸出的標(biāo)準(zhǔn)差平均約為0.56。對于后者，我們在盲測中讓部分作者比較CoT和ToT生成的段落對的連貫性，段落順序在100個(gè)輸入中隨機(jī)翻轉(zhuǎn)。

基線：考慮到任務(wù)的創(chuàng)意性質(zhì)，IO和CoT提示都是零樣本。前者提示語言模型在給定輸入約束的情況下直接生成連貫的段落，后者提示語言模型先做一個(gè)簡短的計(jì)劃再寫段落，即計(jì)劃作為中間思維步驟。我們?yōu)槊總€(gè)任務(wù)生成10個(gè)IO和CoT樣本。我們還考慮了一種迭代精煉方法（ k \leq 5 ），在每個(gè)任務(wù)的隨機(jī)IO樣本基礎(chǔ)上進(jìn)行迭代，語言模型根據(jù)輸入約束和最后生成的段落判斷段落是否“完美連貫”，如果不是，則生成改進(jìn)的段落。

ToT設(shè)置：我們構(gòu)建了一個(gè)深度為2的ToT（只有1個(gè)中間思維步驟）——語言模型首先生成5個(gè)計(jì)劃并投票選出最佳計(jì)劃（圖4），然后基于最佳計(jì)劃生成5個(gè)段落并投票選出最佳段落。這里寬度限制  b = 1 ，每步只保留一個(gè)選擇。我們在兩個(gè)步驟都使用一個(gè)簡單的零樣本投票提示（“分析下面的選擇，然后總結(jié)哪個(gè)最有希望完成指令”）抽取5票。

圖4：在一個(gè)隨機(jī)選取的創(chuàng)意寫作任務(wù)中進(jìn)行有目的搜索的一個(gè)步驟。給定輸入后，語言模型生成5個(gè)不同的計(jì)劃，然后投票5次決定哪個(gè)計(jì)劃最佳。多數(shù)票選出的計(jì)劃將用于按照相同的生成-投票程序撰寫輸出段落。

（注釋:在一個(gè)隨機(jī)選取的創(chuàng)意寫作任務(wù)中進(jìn)行有目的搜索的一個(gè)步驟。

(a) 輸入 (Input)

- 任務(wù)說明：任務(wù)是寫一個(gè)包含4個(gè)短段落的連貫段落，每個(gè)段落的結(jié)尾句子必須是指定的4個(gè)句子。

- 這些結(jié)尾句子分別是：

1. It isn't difficult to do a handstand if you just stand on your hands.

2. It caught him off guard that space smelled of seared steak.

3. When she didn’t like a guy who was trying to pick her up, she started using sign language.

4. Each person who knows you has a different perception of who you are.

(b) 計(jì)劃生成 (Plans)

- 步驟 (b)：語言模型根據(jù)輸入生成多個(gè)不同的計(jì)劃。

- 計(jì)劃1：

1. 介紹和解釋做倒立的技巧

2. 轉(zhuǎn)換到一個(gè)關(guān)于宇航員第一次進(jìn)入太空的故事

3. 描述一個(gè)女人使用手語避免不必要注意的情況

4. 最后一個(gè)段落解釋每個(gè)人對他人的不同看法

- 得票：0/5票

- 計(jì)劃2：

1. 介紹一本不尋常的自助書，提到做倒立作為迎接挑戰(zhàn)的隱喻

2. 討論從宇航員身上學(xué)到的意外事情，包括太空的氣味

3. 描述一個(gè)女人在酒吧避免不必要注意的巧妙策略

4. 思考對自己的不同看法如何塑造個(gè)人身份

- 得票：3/5票（最終選中）

- 計(jì)劃3-5：類似于計(jì)劃1和計(jì)劃2，但未顯示具體內(nèi)容。

(c) 投票 (Votes)

- 步驟 (c)：評估和投票。

- 分析和評價(jià)每個(gè)選擇：

- 選擇1：盡管包含所需的結(jié)尾句子，但段落之間缺乏明確的連接。

- 選擇2：提供了一個(gè)有趣的視角，通過使用所需的結(jié)尾句子展示了自助書的內(nèi)容。它將段落與自我提升和迎接挑戰(zhàn)的主題連接起來，形成連貫的段落。

- 最終選擇：最佳選擇是計(jì)劃2。

工作原理總結(jié)

1. 輸入階段：明確任務(wù)要求，即需要生成包含指定結(jié)尾句子的連貫段落。

2. 計(jì)劃生成階段：語言模型生成多個(gè)計(jì)劃，每個(gè)計(jì)劃都嘗試符合輸入要求并形成一個(gè)完整的故事。

3. 投票和評估階段：對生成的計(jì)劃進(jìn)行評估，通過投票選擇最符合任務(wù)要求的計(jì)劃。

4. 最終輸出：選中的計(jì)劃用于撰寫最終的輸出段落。

這種有目的的搜索方法通過生成多個(gè)候選計(jì)劃并進(jìn)行評估和投票，有效提高了輸出內(nèi)容的連貫性和質(zhì)量。）

結(jié)果：圖5(a)顯示了100個(gè)任務(wù)的平均GPT-4評分，其中ToT（7.56）被認(rèn)為生成的段落比IO（6.19）和CoT（6.93）更連貫。盡管這種自動(dòng)評分可能有噪音，圖5(b)通過展示人工偏好ToT而非CoT的41對段落（在100對中），而僅偏好CoT的21對（另有38對被認(rèn)為“同樣連貫”），確認(rèn)了這一發(fā)現(xiàn)。最后，迭代精煉在這個(gè)自然語言任務(wù)中更有效，IO連貫性評分從6.19提高到7.67，ToT連貫性評分從7.56提高到7.91。我們認(rèn)為這可以被視為ToT框架中思維生成的第三種方法，其中新思維可以通過精煉舊思維而不是獨(dú)立同分布或順序生成。

4.3 迷你填字游戲

在24點(diǎn)游戲和創(chuàng)意寫作中，ToT相對較淺——最多需要3個(gè)思維步驟才能達(dá)到最終輸出。在這里，我們探索5×5迷你填字游戲作為一個(gè)涉及自然語言的更難的搜索問題。目標(biāo)不僅僅是解決任務(wù)，因?yàn)楦话愕奶钭钟螒蚩梢酝ㄟ^利用大規(guī)模檢索而不是語言模型的專業(yè)NLP管道輕松解決[34]。相反，我們旨在探索語言模型作為一個(gè)通用問題解決者的極限，它探索自己的思維并用有目的的推理作為啟發(fā)式引導(dǎo)自己的探索。

任務(wù)設(shè)置：我們從GooBix抓取數(shù)據(jù)，其中包含156個(gè)5×5迷你填字游戲。由于我們觀察到相鄰的游戲包含類似的線索，我們使用索引為1、6、···、91、96的20個(gè)游戲進(jìn)行測試，索引為136、141、146、151、156的游戲進(jìn)行提示。對于每個(gè)任務(wù)，輸入描述了5個(gè)水平線索和5個(gè)垂直線索，輸出應(yīng)為一個(gè)5×5 = 25個(gè)字母的棋盤以解決填字游戲。對于評估，我們考慮三個(gè)層次的成功：正確字母的部分（每局25個(gè)字母）、單詞（每局10個(gè)單詞）和游戲。

基線：我們在IO提示中提供5個(gè)輸入輸出對的示例，在CoT提示中還包括按順序的中間單詞  h1..5  和  v1..5 。我們?yōu)槊總€(gè)提示運(yùn)行10個(gè)樣本并平均結(jié)果。

ToT設(shè)置：我們利用深度優(yōu)先搜索（算法2），不斷探索最有前途的后續(xù)單詞線索，直到狀態(tài)不再有前途，然后回溯到父狀態(tài)以探索其他思維。為了使搜索變得可行，后續(xù)思維被限制為不改變?nèi)魏我烟畛涞膯卧~或字母，以便ToT最多有10個(gè)中間步驟。對于思維生成，在每個(gè)狀態(tài)下我們將所有現(xiàn)有的思維（例如“h2.motor；h1.tasks”對于圖6(a)中的狀態(tài)）翻譯成剩余線索的字母約束（例如“v1.To heap: tm;...”），并提示5次建議提示以提出下一個(gè)單詞的填充位置和內(nèi)容。重要的是，我們還提示語言模型對不同的思維給出置信度，并在提案中聚合這些置信度以獲得下一步探索的排序思維列表（圖6(a)）。對于狀態(tài)評估，我們類似地將每個(gè)狀態(tài)翻譯成剩余線索的字母約束，然后評估每個(gè)線索在給定約束下是否可填充。如果任何剩余線索被認(rèn)為“不可填”（例如“v1.To heap: tm s”），則該狀態(tài)的子樹探索被修剪，DFS回溯到其父狀態(tài)以探索下一個(gè)有前途的思維。我們將DFS搜索步驟限制為100步，并簡單地將最深探索的狀態(tài)（如果有多個(gè)則為第一個(gè)）渲染為最終輸出。

圖6：在迷你填字游戲中，(a) 思維如何在深度優(yōu)先搜索（DFS）中提出并在優(yōu)先隊(duì)列中聚合，(b) 如何基于填入每個(gè)剩余單詞線索的可能性評估狀態(tài)，如果任何剩余線索被語言模型認(rèn)為不可填，則進(jìn)行修剪。然后DFS回溯到父狀態(tài)，并探索下一個(gè)有前途的線索思維。

（注釋：在迷你填字游戲中應(yīng)用深度優(yōu)先搜索（DFS）時(shí)思維的提出和評估過程。

(a) 思維提出 (Thought Proposals)

- 輸入線索 (Input Clues)：如圖左上角所示，輸入線索包括一組需要填字的單詞提示。已填字母如“tasks”、“motor”和“salon”。

- 思維提出：

- 語言模型根據(jù)現(xiàn)有的輸入線索提出多個(gè)可能的填字方案。例如，“h4.salon（確定）”、“v5.srdry（低）”和“v3.string（高）”。

- 這些思維被放入一個(gè)優(yōu)先隊(duì)列中進(jìn)行聚合，根據(jù)其可能性和優(yōu)先級排序。

(b) 狀態(tài)評估 (State Evaluation)

- DFS 順序 (DFS Order)：圖右上角展示了根據(jù)優(yōu)先級排序后的DFS順序，例如“h4.salon”、“h3.grand”和“v3.string”。

- 狀態(tài)評估：

- 每個(gè)狀態(tài)的評估基于填入每個(gè)剩余單詞線索的可能性進(jìn)行。

- 狀態(tài)評估器 (State Evaluator) 會(huì)對每個(gè)線索進(jìn)行評估。例如：

- v3. Pretentious; flowery: _____（確定）

- v1. To heap: tm_s_（不可能）

- v5. Desiccator; more dry: sr_n_（可能）

深度優(yōu)先搜索 (DFS) 和修剪 (Pruning)

- DFS 執(zhí)行過程：

- DFS首先探索優(yōu)先隊(duì)列中的最高優(yōu)先級思維，例如“h4.salon”。

- 如果某個(gè)狀態(tài)的任何剩余線索被評估為“不可能”，則該狀態(tài)的子樹會(huì)被修剪（subtree pruned），如圖中紅色標(biāo)注的“h4.salon”。

- 修剪后，DFS會(huì)回溯到父狀態(tài)，繼續(xù)探索下一個(gè)有前途的思維，例如從“h4.salon”回溯到“h1.tasks”，再探索“h3.grand”。

總結(jié)

在迷你填字游戲中如何通過深度優(yōu)先搜索（DFS）進(jìn)行思維提出和狀態(tài)評估：

1. 思維提出：基于輸入線索，語言模型生成多個(gè)可能的填字方案，并將其按優(yōu)先級排序。

2. 狀態(tài)評估：每個(gè)狀態(tài)根據(jù)填入每個(gè)剩余單詞線索的可能性進(jìn)行評估。如果評估結(jié)果為“不可能”，則該狀態(tài)會(huì)被修剪。

3. 深度優(yōu)先搜索：通過DFS探索最有前途的思維，遇到不可能的狀態(tài)時(shí)回溯并繼續(xù)探索其他可能的思維。

這種方法能夠有效地利用語言模型的能力，在復(fù)雜的填字游戲中進(jìn)行有目的的搜索和評估，提高問題解決的效率和成功率。）

結(jié)果：如表3所示，IO和CoT提示方法在單詞級成功率不到16%的情況下表現(xiàn)不佳，而ToT顯著改善了所有指標(biāo)，單詞級成功率達(dá)到60%，解決了20個(gè)游戲中的4個(gè)。這樣的改進(jìn)并不令人意外，因?yàn)镮O和CoT缺乏嘗試不同線索、修改決策或回溯的機(jī)制。

Oracle和消融研究：在每個(gè)任務(wù)中輸出Oracle最佳DFS狀態(tài)（而不是啟發(fā)式確定的最佳狀態(tài)）時(shí)，ToT的性能甚至更高，實(shí)際上解決了7/20個(gè)游戲（表3，“+最佳狀態(tài)”），這表明我們的簡單輸出啟發(fā)式可以得到改進(jìn)。有趣的是，有時(shí)當(dāng)填字游戲?qū)嶋H上解決了，狀態(tài)評估器仍可能認(rèn)為某些單詞“不可填”并修剪——可能是因?yàn)?×5填字游戲設(shè)計(jì)上有一些稀有或過時(shí)的詞匯，GPT-4無法識(shí)別。由于狀態(tài)評估作為修剪啟發(fā)式是不完美的，我們還探索了消融修剪，發(fā)現(xiàn)性能總體較差（表3，“-修剪”）。然而，它實(shí)際上可以找到4/20個(gè)游戲的正確解決方案（盡管僅輸出1個(gè)通過啟發(fā)式），其中3個(gè)是ToT+修剪在100步內(nèi)無法解決的游戲。因此，改進(jìn)DFS修剪的啟發(fā)式對于解決此類問題至關(guān)重要。最后，我們通過運(yùn)行一個(gè)消融實(shí)驗(yàn)確認(rèn)了回溯的重要性，在該實(shí)驗(yàn)中最多允許填充20步的最有前途線索，允許覆蓋。這類似于寬度限制為  b = 1  的“貪心”BFS搜索，單詞級成功率僅為20%（表3，“-回溯”）。

5. 相關(guān)工作

規(guī)劃和決策：智能規(guī)劃和決策對實(shí)現(xiàn)預(yù)定目標(biāo)至關(guān)重要。由于語言模型（LMs）在大量世界知識(shí)和人類示例上訓(xùn)練，已知它們已經(jīng)吸收了豐富的常識(shí)，使得根據(jù)問題設(shè)置和環(huán)境狀態(tài)提出合理計(jì)劃成為可能[12, 42, 37, 13, 35, 41, 40]。我們提出的思維樹（ToT）方法通過在每一步問題解決過程中同時(shí)考慮多個(gè)潛在可行的計(jì)劃，并繼續(xù)最有前途的計(jì)劃，擴(kuò)展了現(xiàn)有的規(guī)劃形式。思維采樣與價(jià)值反饋的結(jié)合有機(jī)地整合了規(guī)劃和決策機(jī)制，能夠在解決方案樹中進(jìn)行有效搜索。另一方面，傳統(tǒng)的決策過程通常需要訓(xùn)練專門的獎(jiǎng)勵(lì)和策略模型，如強(qiáng)化學(xué)習(xí)中的CHAI[33]，而我們使用語言模型本身提供決策所需的價(jià)值評估。RAP[9]是一個(gè)將語言模型推理視為其內(nèi)部世界模型規(guī)劃的并發(fā)工作，并提出了一種類似ToT的MCTS方法。然而，其任務(wù)比我們的簡單，并且其框架缺乏整合不同樹搜索算法的模塊化。

自我反思：使用大型語言模型（LLMs）評估其自身預(yù)測的可行性在問題解決中變得越來越重要。[28, 20, 24]引入了“自我反思”機(jī)制，在此機(jī)制中，語言模型為其生成的候選項(xiàng)提供反饋。[4]通過注入語言模型基于其代碼執(zhí)行結(jié)果生成的反饋消息，提高了語言模型代碼生成的準(zhǔn)確性。同樣地，[17]也在計(jì)算機(jī)操作任務(wù)中引入了對操作和狀態(tài)的“批評”或?qū)彶椴襟E，決定下一步采取的行動(dòng)。另一項(xiàng)與我們工作非常相關(guān)的近期研究是“自我評估引導(dǎo)解碼”[39]。與我們的方法類似，自我評估解碼也遵循樹搜索過程，葉節(jié)點(diǎn)從隨機(jī)束搜索解碼中抽樣，然后由語言模型本身使用精心準(zhǔn)備的自我評估提示進(jìn)行評估。然而，他們的方法使用PAL形式[8]，將思維表示為代碼，這使得處理如本論文中考慮的創(chuàng)意寫作等具有挑戰(zhàn)性的任務(wù)變得困難。因此，我們的思維樹方法更加通用，能夠處理GPT-4在標(biāo)準(zhǔn)提示下僅能達(dá)到非常低準(zhǔn)確率的挑戰(zhàn)性任務(wù)。

程序引導(dǎo)的語言模型生成：我們的提議也與最近的進(jìn)展有關(guān)，這些進(jìn)展通過系統(tǒng)程序[14, 44, 6, 43]或符號(hào)程序引導(dǎo)來組織語言模型的行為。例如，Schlag等人[27]將語言模型嵌入到算法搜索過程中，幫助逐步解決問題，如回答問題，其中搜索樹由可能提供答案的相關(guān)段落擴(kuò)展。然而，該方法與我們的方法不同，因?yàn)闃渫ㄟ^抽樣外部段落而非語言模型自身的思維進(jìn)行擴(kuò)展，并且沒有反思或投票步驟。另一種方法，LLM+P[18]，更進(jìn)一步，將實(shí)際的規(guī)劃過程委托給傳統(tǒng)的規(guī)劃者。

經(jīng)典搜索方法：最后但同樣重要的是，我們的方法可以被視為經(jīng)典搜索方法在問題解決中的現(xiàn)代演繹。例如，它可以被視為一種啟發(fā)式搜索算法，如A[10]，在每個(gè)搜索節(jié)點(diǎn)的啟發(fā)式由語言模型的自我評估提供。從這個(gè)角度來看，我們的方法也與NeuroLogic Aesque解碼[19]相關(guān)，后者受A搜索啟發(fā)，引入了前瞻啟發(fā)式，對于提高束搜索或top-k抽樣解碼的語言模型來說是高效的。然而，該方法限制于句子生成任務(wù)，而我們的框架設(shè)計(jì)用于復(fù)雜的、多步驟的問題解決，由價(jià)值反饋進(jìn)行保護(hù)。

6.討論

限制和未來方向：像ToT這樣的有目的搜索可能對于GPT-4已經(jīng)擅長的許多現(xiàn)有任務(wù)（見附錄B.1）并不必要，作為初步工作，本研究僅探索了三個(gè)相對簡單的挑戰(zhàn)GPT-4的任務(wù)（見附錄B.2中的一些GPT-3.5實(shí)驗(yàn)結(jié)果），并呼吁將更好的搜索和規(guī)劃能力整合到語言模型中。然而，當(dāng)我們開始將語言模型部署到更多現(xiàn)實(shí)世界的決策應(yīng)用中（如編碼、數(shù)據(jù)分析、機(jī)器人技術(shù)等），更復(fù)雜的任務(wù)可能會(huì)出現(xiàn)，并為研究這些問題提供新機(jī)會(huì)。此外，為了提高任務(wù)性能，像ToT這樣的搜索方法需要比采樣方法更多的資源（如GPT-4 API費(fèi)用），但ToT的模塊化靈活性允許用戶定制這種性能-成本權(quán)衡，并且正在進(jìn)行的開源努力[32]應(yīng)該會(huì)在不久的將來減少這些成本。更多關(guān)于成本和效率的詳細(xì)信息見附錄B.3。最后，這項(xiàng)工作側(cè)重于使用現(xiàn)成的語言模型，并且使用ToT風(fēng)格的高層反事實(shí)決策進(jìn)行語言模型微調(diào)（如權(quán)衡下一段的潛在選擇，而不是預(yù)測下一個(gè)標(biāo)記）可能會(huì)增強(qiáng)語言模型的問題解決能力。

結(jié)論：語言模型的聯(lián)想“系統(tǒng)1”可以通過基于搜索問題解決路徑樹的“系統(tǒng)2”得到有益的增強(qiáng)。思維樹框架提供了一種將關(guān)于問題解決的經(jīng)典見解轉(zhuǎn)化為現(xiàn)代語言模型可操作方法的途徑。同時(shí)，語言模型解決了這些經(jīng)典方法的弱點(diǎn)，提供了一種解決難以形式化的復(fù)雜問題（如創(chuàng)意寫作）的途徑。我們認(rèn)為，語言模型與經(jīng)典AI方法的交叉是一個(gè)令人興奮的方向。

更廣泛的影響：ToT是一個(gè)使語言模型能夠更自主和智能地做出決策和解決問題的框架。雖然當(dāng)前任務(wù)僅限于推理和搜索問題，未來涉及與外部環(huán)境或人類互動(dòng)的應(yīng)用可能會(huì)帶來潛在危險(xiǎn)，如促進(jìn)語言模型的有害使用。另一方面，ToT也提高了模型決策的可解釋性和人類對齊的機(jī)會(huì)，因?yàn)榻Y(jié)果表示是可讀的高層語言推理，而不是隱含的低層標(biāo)記值。

Yao S, Yu D, Zhao J, et al. Tree of thoughts: Deliberate problem solving with large language models[J]. Advances in Neural Information Processing Systems, 2024, 36.

1 Princeton University

2 Google DeepMind

本文轉(zhuǎn)載自公眾號(hào)AIRoobt ，作者：AIRoobt

原文鏈接：????https://mp.weixin.qq.com/s/DgtXskiQmrdmkYAg5oNXbQ???