摘要

語言模型正日益被部署于廣泛任務中的通用問題求解，但在推理階段仍受限于 token 級、從左到右的決策過程。這意味著在需要探索、戰略前瞻，或初始決策起關鍵作用的任務中，語言模型可能表現不佳。為克服這些挑戰，我們提出了一種新的語言模型推理框架——“思維樹（Tree of Thoughts, ToT）”，它是對當前廣泛使用的“思維鏈（Chain of Thought）”提示方法的推廣，能夠在連貫的文本單元（即“思維”）之間進行探索，這些單元作為問題求解的中間步驟。ToT 允許語言模型進行深思熟慮的決策：在多種不同的推理路徑之間進行考慮、自我評估選擇以決定下一步行動，并在必要時進行前瞻或回溯，以做出更具全局性的決策。我們的實驗表明，在三個需要非平凡規劃或搜索的新任務上，ToT 顯著增強了語言模型的問題求解能力，這三項任務分別是：24 點游戲、創意寫作和迷你縱橫字謎。例如，在 24 點游戲中，使用思維鏈提示的 GPT-4 僅解決了 4% 的任務，而我們的方法成功率達到了 74%。完整提示與代碼倉庫：https://github.com/princeton-nlp/tree-of-thought-llm

1 引言

語言模型（LMs）最初被設計用于文本生成，但隨著規模的擴大，如 GPT [25, 26, 1, 23] 和 PaLM [5]，它們已經被證明能夠處理越來越廣泛的任務，這些任務需要數學、符號、常識和知識推理能力。令人驚訝的是，支撐這一切進展的，依然是最初的自回歸文本生成機制——以從左到右、逐 token 做出決策的方式生成文本。這樣一個簡單的機制是否足以構建一個通用問題求解器？如果不足，哪些問題會挑戰這一現有范式？又有哪些替代機制值得探索？

人類認知的相關文獻為回答這些問題提供了一些線索。“雙系統”模型的研究表明，人類在做決策時存在兩種模式——快速、自動、無意識的模式（“系統1”），以及緩慢、深思熟慮、有意識的模式（“系統2”）[30, 31, 16, 15]。這兩種模式也曾被關聯到機器學習中各種數學模型上。例如，人類及其他動物在強化學習中的研究探索了他們在何種情境下會采取聯想式的“無模型”學習，或更具深思熟慮的“有模型”規劃[7]。語言模型那種簡單的、聯想式的 token 級選擇也類似于“系統1”，因此或許可以通過一種更具深思熟慮的“系統2”規劃過程加以增強，該過程 (1) 維護并探索當前選擇的多種可能性，而非僅做出單一選擇，(2) 對當前狀態進行評估，并主動進行前瞻或回溯，以做出更具全局性的決策。

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

在實證方面，我們提出了三項新任務，用以挑戰現有語言模型推理方法，即便是最先進的模型 GPT-4 [23]：24 點游戲、創意寫作和縱橫字謎（見表1）。這些任務需要演繹推理、數學推理、常識推理、詞匯推理能力，并要求引入系統性的規劃或搜索機制。我們展示了 ToT 在這三項任務上均取得了優越的結果，這得益于其足夠通用與靈活，能夠支持不同層級的思維單元、不同的思維生成與評估方式，以及適應不同問題特性的多種搜索算法。我們還通過系統性的消融實驗分析了這些設計選擇如何影響模型性能，并討論了未來如何更有效地訓練和使用語言模型的研究方向。

2 背景

我們首先形式化一些現有使用大型語言模型進行問題求解的方法，這些方法為我們的工作提供了靈感，并將在后文與我們的框架進行比較。我們使用 $p_{\theta }$ 表示一個具有參數 $\theta$ 的預訓練語言模型（LM），使用小寫字母 $x,y,z,s,?$ 表示一個語言序列，即 $x=(x[1],?,x[n])$，其中每個 $x[i]$ 是一個 token，從而有：$\begin{array}{r}{p}_{\theta }(x)={\prod }_{i=1}^n{p}_{\theta }(x[i]|x[\mathrm{1...}i]).\end{array}$ 我們使用大寫字母 $S,?$ 表示一組語言序列。

輸入-輸出（IO）提示是使用語言模型將問題輸入 $x$ 轉化為輸出 $y$ 的最常見方式：$y～p_{\theta }(y\mid {\text{prompt}}_{IO}(x))$，其中 ${\text{prompt}}_{IO}(x)$ 是將輸入 $x$ 包裝為包含任務指令和/或少量示例的提示模板。為簡潔起見，我們將$p_{\theta }^{\text{prompt}}(\text{output}\mid \text{input})=p_{\theta }(\text{output}\mid \text{prompt}(\text{input}))$ ，因此，IO 提示可以形式化為：$y～p_{\theta }^{IO}(y\mid x)$。

Chain-of-thought（CoT）提示 [38] 被提出用以解決輸入 $x$ 到輸出 $y$ 的映射非平凡的情況（例如，當 $x$ 是一道數學題而 $y$ 是最終的數值答案時）。其核心思想是在 $x$ 和 $y$ 之間引入一系列思路鏈 $z_1,?,z_n$，其中每個 $z_i$ 是一個連貫的語言序列，作為通向問題解決的有意義的中間步驟（例如，對于數學問答任務，$z_i$ 可以是一個中間公式）。在使用 CoT 解決問題時，每個思路 $z_i～p_{\theta }^{\text{CoT}}(z_i\mid x,z_1?z_{i?1})$ 被順序采樣，然后最終輸出 $y～p_{\theta }^{\text{CoT}}(y\mid x,z_1?z_n)$。在實踐中，整體序列 $[z_{\mathrm{1...}n},y]～p_{\theta }^{CoT}(z_{\mathrm{1...}n},y|x)$ 被作為一個連續的語言序列進行采樣，而對于思路的劃分方式（例如每個 $z_i$ 是短語、句子還是段落）則是模糊的。

Self-consistency with CoT（CoT-SC）[36] 是一種集成方法，它采樣 $k$ 條相互獨立的思路鏈：$[z_{1?n}^{(i)},y^{(i)}]～p_{\theta }^{CoT}(z_{1?n},y|x)(i=1?k)$，然后返回出現頻率最高的輸出： a r g m a x y # { i ∣ y ( i ) = y } \mathrm { a r g \, m a x } _ { y } \, \# \{ i \ | \ y ^ { ( i ) } \, = \, y \} argmaxy?#{i?∣?y(i)=y}

，CoT-SC 相較于 CoT 有所提升，因為對于同一個問題通常存在多種思考過程（例如，證明同一個定理的不同方式），通過探索更豐富的思路集合可以使最終決策更具忠實性。然而，在每條鏈內部并未對不同思路步驟進行局部探索，而且“最頻繁”這一啟發式方法僅適用于輸出空間有限的情形（例如多項選擇問答）。

3 Tree of Thoughts: 使用語言模型進行深思熟慮的問題求解

一個真正的問題解決過程涉及反復使用已有信息以啟動探索，進而揭示更多信息，直到最終發現達成解答的方法為止。—— Newell 等人 [21]

關于人類問題解決的研究表明，人們會在一個組合型問題空間中進行搜索——這個空間可被視為一棵樹，其節點表示部分解，分支對應于對這些部分解進行修改的操作符 [21, 22]。采取哪條分支由啟發式方法決定，這些啟發式方法幫助在問題空間中導航，并引導問題解決者走向答案。這一視角揭示了當前使用語言模型解決一般問題的方法的兩個主要缺陷：

1）在局部層面，它們并未探索思路過程中的不同延續——即樹的各個分支；
2）在全局層面，它們未采用任何形式的規劃、前瞻或回溯來幫助評估這些不同的選項——也就是類似人類問題解決所特有的啟發式搜索方式。

為了解決上述問題，我們提出了 Tree of Thoughts（ToT）這一范式，它允許語言模型在多個思維路徑上進行探索（見圖1?）。ToT 將任何問題建模為對一棵樹的搜索過程，其中每個節點是一個狀態 $s=[x,z_{1?i}]$，表示一個由輸入和迄今為止的思路序列構成的部分解。ToT 的一個具體實例需回答以下四個問題：

1. 如何將中間過程分解為思維步驟；
2. 如何從每個狀態生成可能的思路；
3. 如何基于啟發式方法評估這些狀態；
4. 應該使用哪種搜索算法。

1. 思路分解（Thought decomposition）

雖然 CoT 會以連貫方式采樣思路但不進行顯式分解，ToT 則利用問題的性質來設計并分解中間思路步驟。如表1所示，具體問題不同，思路的粒度也不同：在填字游戲中，一個思路可能是幾個詞；在24點游戲中，可能是一行算式；在創意寫作中，可能是一個寫作計劃的整段文字。一般而言，思路應足夠“小”，以便語言模型可以生成有希望且多樣的樣本（例如，生成整本書通常太“大”而難以保持連貫性）；但也應足夠“大”，以便語言模型能夠評估其在解決問題方面的前景（例如，僅生成一個 token 通常太“小”，不足以做出判斷）。

2. 思路生成器 $G(p_{\theta },s,k)$

給定一個樹狀態 $s=[x,z_{1?i}]$，我們考慮兩種策略來為下一個思路步驟生成 $k$ 個候選：

(a) 從 CoT 提示中獨立同分布地采樣思路（用于創意寫作，見圖4）：
$z^{(j)}～p_{\theta }^{CoT}(z_{i+1}|s)=p_{\theta }^{CoT}(z_{i+1}|x,z_{1?i})(j=1??k)$。
當思路空間較為豐富（例如每個思路是一個段落）時，這種方法效果更好，i.i.d. 采樣能帶來更大的多樣性；

(b) 使用“建議式提示”順序提出思路（用于24點游戲，見圖2；填字游戲，見圖6）：
$[z^{(1)},?,z^{(k)}]～p_{\theta }^{\text{propose}}(z_{i+1}^{(1?k)}\mid s)$ 。當思路空間較受限（例如每個思路只是一個詞或一行）時，這種方法效果更佳，因為在相同上下文中提出多個不同思路可以避免重復。

一個真正的問題解決過程，是反復利用已有信息發起探索，而探索過程又反過來揭示更多信息，直到最終找到達成解決方案的路徑為止。—— Newell 等人 [21]

關于人類問題解決的研究表明，人類是在一個組合型的問題空間中進行搜索的——這個問題空間可以看作一棵樹，其中的節點表示部分解，分支則對應于對這些部分解進行修改的操作符 [21, 22]。選擇哪一個分支，取決于一些啟發式方法，這些方法幫助導航問題空間，引導問題解決者走向解決方案。這樣的視角揭示了現有語言模型在通用問題求解中存在的兩個關鍵缺陷：1）在局部層面，它們不會探索思維過程中的不同延續——即樹的不同分支；2）在全局層面，它們缺乏任何形式的計劃、前瞻性或回溯機制，無法評估這些不同的選項——而這些正是人類問題解決過程中的典型啟發式搜索方式。

為了解決上述缺陷，我們提出了 Tree of Thoughts（ToT）這一范式，它允許語言模型在“思維”層面探索多條推理路徑（見圖1?）。ToT 將任何問題建模為對一棵樹的搜索，其中每個節點表示一個狀態 $s=[x,z_{1???i}]$，即包含輸入 $x$ 和到目前為止生成的思維序列 $z_1???i$ 的一個部分解。一個具體的 ToT 實例包含對以下四個問題的回答：

1. 如何將中間推理過程分解為思維步驟；
2. 如何從每個狀態生成潛在的思維；
3. 如何對狀態進行啟發式評估；
4. 使用什么樣的搜索算法。

1. 思維分解（Thought decomposition）

雖然 Chain-of-Thought（CoT）可以在沒有顯式分解的情況下連貫地生成思維，ToT 則利用問題本身的特性對中間推理步驟進行設計和分解。如表1所示，依據問題的不同，一個“思維”可能是幾個詞（如填字游戲），一行公式（如24點游戲），或一整段寫作計劃（如創意寫作）。一般而言，一個“思維”應當足夠“小”，以便語言模型能夠生成有前景且多樣的樣本（例如生成整本書通常太“大”，不夠連貫）；同時也要足夠“大”，以便語言模型可以對其在問題求解中的前景做出評估（例如生成一個 token 通常太“小”，無法評估）。

2. 思維生成器 $G(p_{\theta },s,k)$

給定樹狀態 $s=[x,z_1???i]$，我們考慮以下兩種策略來生成 $k$ 個下一步思維候選：

（a）從 CoT 提示中獨立同分布地采樣思維（創意寫作，圖4）：

$$z^{(j)}～p_{\theta }^{\text{CoT}}(z_{i+1}\mid s)=p_{\theta }^{\text{CoT}}(z_{i+1}\mid x,z_1???i),j=1???k$$

這種方法在思維空間較為豐富（例如每個思維是一段文字）時表現更好，獨立樣本有利于提高多樣性；

（b）使用“提議提示”順序提出思維（24點游戲，圖2；填字游戲，圖6）：

$$[z^{(1)},???,z^{(k)}]～p_{\theta }^{\text{propose}}(z_{i+1}^{(1???k)}\mid s)$$

這種方法在思維空間較為受限（如每個思維僅為一個詞或一行）時表現更好，在同一上下文中提出不同思維可以避免重復。

溫馨提示：
閱讀全文請訪問"AI深語解構" ：ToT：思維樹：借助大語言模型進行審慎的問題求解