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

1.引言

最初設計用于生成文本的大規模語言模型（LMs），如GPT和PaLM，已經被證明能夠執行越來越多需要數學、符號、常識和知識推理的任務。或許令人驚訝的是，這些進步的基礎仍然是原始的自回歸機制，用于生成文本，即逐個令牌地從左到右做出決策。這樣的簡單機制是否足以構建一個通用問題解決器？如果不是，哪些問題會挑戰當前的范式，應該采用哪些替代機制？

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

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

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

在實證上，我們提出了三種新問題，這些問題即使使用最先進的語言模型GPT-4也會挑戰現有的LM推理方法：24點游戲、創意寫作和填字游戲。這些任務需要演繹、數學、常識、詞匯推理能力，以及一種系統規劃或搜索的方法。我們證明了ToT在所有三項任務上都取得了優異的結果，因為它足夠通用和靈活，能夠支持不同層次的思想，不同的生成和評估思想的方式，以及適應不同問題性質的不同搜索算法。我們還通過系統性消融分析了這些選擇如何影響模型性能，并討論了更好地訓練和使用LMs的未來方向。

2.背景

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

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

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

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

3. 思維樹：利用LM進行深思熟慮的解決問題

一個真正的問題解決過程涉及重復使用現有信息進行探索，從而揭示更多信息，直到最終發現解決方案。—— Newell等人

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

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

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

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

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

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

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

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

從概念上講，ToT作為使用LMs進行一般問題解決的方法有幾個好處：（1）通用性。IO，CoT，CoT-SC和自我改進可以看作ToT的特例（即有限深度和廣度的樹；圖1）。（2）模塊化。基礎LM以及思想的分解、生成、評估和搜索過程都可以獨立變化。（3）適應性。可以適應不同的問題屬性、LM能力和資源限制。（4）便利性。不需要額外的訓練，只需一個預訓練的LM即可。下一節將展示這些概念上的好處如何轉化為在不同問題上強大的實證性能。

4.實驗

我們提出了三個任務，即使使用最新的語言模型GPT-4 [23]，采用標準的輸入輸出提示或思維鏈（CoT）提示也很難完成。我們展示了在思維樹（ToT）中進行有目的的搜索如何產生更好的結果，更重要的是，展示了使用語言模型解決需要搜索或規劃的問題的新穎而有前途的方法。除非另有說明，我們使用具有0.7采樣溫度的GPT-4的Chat Completion模式進行實驗。

4.1 24點游戲

24點游戲是一個數學推理挑戰，目標是使用4個數字和基本的算術運算（加減乘除）得到24。例如，給定輸入“4 9 10 13”，一個解決方案輸出可以是“(10 - 4) (13 - 9) = 24”。

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

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

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

1. 輸入和初始狀態

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

- 目標是通過基本的算術運算（加、減、乘、除）將這些數字組合成24。

2. 思維生成（Propose Prompt）

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

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

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

3. 思維評估（Value Prompt）

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

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

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

4. 思維樹的構建

- 圖的左側展示了一個思維樹的分支結構，每個節點表示一個操作及其剩余數字。

- 例如，起始節點是“4 9 10 13”，通過“10 - 4 = 6（剩下：6 9 13）”和“4 + 9 = 13（剩下：10 13 13）”生成了兩個子節點。

- 每個子節點繼續生成進一步的操作，形成分支，例如“13 - 6 = 7（剩下：7 9）”和“13 - 9 = 4（剩下：4 6）”。

5. 操作的具體評估

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

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

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

6. 結果和決策

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

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

結論

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

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

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

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

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

4.2 創意寫作

接下來，我們設計了一個創意寫作任務，輸入為4個隨機句子，輸出應為一個連貫的段落，其中4個段落分別以4個輸入句子結尾。這樣的任務是開放性和探索性的，挑戰了創意思維和高層次的規劃能力。

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

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

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

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

（注釋:在一個隨機選取的創意寫作任務中進行有目的搜索的一個步驟。

(a) 輸入 (Input)

- 任務說明：任務是寫一個包含4個短段落的連貫段落，每個段落的結尾句子必須是指定的4個句子。

- 這些結尾句子分別是：

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) 計劃生成 (Plans)

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

- 計劃1：

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

2. 轉換到一個關于宇航員第一次進入太空的故事

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

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

- 得票：0/5票

- 計劃2：

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

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

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

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

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

- 計劃3-5：類似于計劃1和計劃2，但未顯示具體內容。

(c) 投票 (Votes)

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

- 分析和評價每個選擇：

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

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

- 最終選擇：最佳選擇是計劃2。

工作原理總結

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

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

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

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

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

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

4.3 迷你填字游戲

在24點游戲和創意寫作中，ToT相對較淺——最多需要3個思維步驟才能達到最終輸出。在這里，我們探索5×5迷你填字游戲作為一個涉及自然語言的更難的搜索問題。目標不僅僅是解決任務，因為更一般的填字游戲可以通過利用大規模檢索而不是語言模型的專業NLP管道輕松解決[34]。相反，我們旨在探索語言模型作為一個通用問題解決者的極限，它探索自己的思維并用有目的的推理作為啟發式引導自己的探索。

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

基線：我們在IO提示中提供5個輸入輸出對的示例，在CoT提示中還包括按順序的中間單詞  h1..5  和  v1..5 。我們為每個提示運行10個樣本并平均結果。

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

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

（注釋：在迷你填字游戲中應用深度優先搜索（DFS）時思維的提出和評估過程。

(a) 思維提出 (Thought Proposals)

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

- 思維提出：

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

- 這些思維被放入一個優先隊列中進行聚合，根據其可能性和優先級排序。

(b) 狀態評估 (State Evaluation)

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

- 狀態評估：

- 每個狀態的評估基于填入每個剩余單詞線索的可能性進行。

- 狀態評估器 (State Evaluator) 會對每個線索進行評估。例如：

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

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

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

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

- DFS 執行過程：

- DFS首先探索優先隊列中的最高優先級思維，例如“h4.salon”。

- 如果某個狀態的任何剩余線索被評估為“不可能”，則該狀態的子樹會被修剪（subtree pruned），如圖中紅色標注的“h4.salon”。

- 修剪后，DFS會回溯到父狀態，繼續探索下一個有前途的思維，例如從“h4.salon”回溯到“h1.tasks”，再探索“h3.grand”。

總結

在迷你填字游戲中如何通過深度優先搜索（DFS）進行思維提出和狀態評估：

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

2. 狀態評估：每個狀態根據填入每個剩余單詞線索的可能性進行評估。如果評估結果為“不可能”，則該狀態會被修剪。

3. 深度優先搜索：通過DFS探索最有前途的思維，遇到不可能的狀態時回溯并繼續探索其他可能的思維。

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

結果：如表3所示，IO和CoT提示方法在單詞級成功率不到16%的情況下表現不佳，而ToT顯著改善了所有指標，單詞級成功率達到60%，解決了20個游戲中的4個。這樣的改進并不令人意外，因為IO和CoT缺乏嘗試不同線索、修改決策或回溯的機制。

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

5. 相關工作

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

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

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

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

6.討論

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

結論：語言模型的聯想“系統1”可以通過基于搜索問題解決路徑樹的“系統2”得到有益的增強。思維樹框架提供了一種將關于問題解決的經典見解轉化為現代語言模型可操作方法的途徑。同時，語言模型解決了這些經典方法的弱點，提供了一種解決難以形式化的復雜問題（如創意寫作）的途徑。我們認為，語言模型與經典AI方法的交叉是一個令人興奮的方向。

更廣泛的影響：ToT是一個使語言模型能夠更自主和智能地做出決策和解決問題的框架。雖然當前任務僅限于推理和搜索問題，未來涉及與外部環境或人類互動的應用可能會帶來潛在危險，如促進語言模型的有害使用。另一方面，ToT也提高了模型決策的可解釋性和人類對齊的機會，因為結果表示是可讀的高層語言推理，而不是隱含的低層標記值。

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

本文轉載自公眾號AIRoobt ，作者：AIRoobt

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