GPT 和 PaLM 等大型語言模型在處理數(shù)學(xué)、符號、常識和知識推理等任務(wù)時正變得越來越熟練。也許令人驚訝的是，所有這些進展的基礎(chǔ)仍然是生成文本的原始自回歸機制。它逐個 token 地進行決策，并按從左到右的方式生成文本。這樣簡單的機制是否足以構(gòu)建一個通用問題求解器的語言模型呢？如果不行，哪些問題將挑戰(zhàn)當(dāng)前的范式，應(yīng)該采用什么樣的替代機制呢？

有關(guān)人類認知的文獻提供了一些線索來回答這些問題。關(guān)于「雙過程（dual process）」模型的研究表明，人們在進行決策時有兩種模式：一種是快速、自動、無意識的模式（System 1），另一種是緩慢、深思熟慮、有意識的模式（System 2）。這兩種模式以前與機器學(xué)習(xí)中使用的各種數(shù)學(xué)模型聯(lián)系在一起。例如，對人類和其他動物的強化學(xué)習(xí)的研究探討了他們進行聯(lián)想式的「無模型」學(xué)習(xí)或更加深思熟慮的「基于模型」的規(guī)劃的情況。語言模型的簡單聯(lián)想式 token 級選擇也類似于「System 1」，因此可能受益于更深思熟慮的「System 2」規(guī)劃過程的增強，該過程保持并探索當(dāng)前選擇的多種替代方案，而不僅僅是選擇一個。此外，它會評估其當(dāng)前狀態(tài)，并積極地展望或回溯以進行更全局的決策。

為了設(shè)計這樣一個規(guī)劃過程，來自普林斯頓大學(xué)、 Google DeepMind 的研究者選擇先回顧一下人工智能（和認知科學(xué)）的起源，汲取 Newell、Shaw 和 Simon 在上世紀 50 年代探索的規(guī)劃過程的靈感。Newell 和他的同事將問題解決描述為對組合式問題空間的搜索，這個空間被表示為一棵樹。因此，他們提出了適用于語言模型的思維樹（ToT）框架，用于通用問題求解。

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

項目地址：https://github.com/ysymyth/tree-of-thought-llm

正如圖 1 所示，現(xiàn)有的方法通過對連續(xù)語言序列進行采樣來解決問題，而 ToT 則積極地維護一棵思維樹，其中每個思維都是一個連貫的語言序列，作為解決問題的中間步驟（表 1）。

這樣一個高級語義單元使 LM 能夠通過深思熟慮的推理過程來自我評估不同中間思維對解決問題的進展貢獻情況（圖 2、4、6）。通過 LM 的自我評估和深思熟慮來實現(xiàn)搜索啟發(fā)式是一種新穎的方法，因為以前的搜索啟發(fā)式要么是編程的，要么是學(xué)習(xí)得來的。

最后，研究者將這種基于語言的生成和評估多樣思維的能力與搜索算法相結(jié)合，例如廣度優(yōu)先搜索（BFS）或深度優(yōu)先搜索（DFS），這些算法允許對思維樹進行系統(tǒng)性的探索，并具備展望和回溯功能。

在實驗階段，研究者設(shè)置了三項任務(wù)，即 24 點游戲、創(chuàng)意寫作和填字游戲（表 1），這些問題對現(xiàn)有的 LM 推理方法來說頗具挑戰(zhàn)性，即使對于 GPT-4 來說也不例外。這些任務(wù)要求具備演繹、數(shù)學(xué)、常識、詞匯推理能力，以及一種融入系統(tǒng)性規(guī)劃或搜索的方式。實驗結(jié)果表明，ToT 在這三個任務(wù)上取得了優(yōu)越的成績，因為它具備足夠的通用性和靈活性，可以支持不同層次的思維、不同生成和評估思維的方式，以及適應(yīng)不同問題性質(zhì)的不同搜索算法。通過系統(tǒng)的實驗消融分析，作者還探討了這些選擇如何影響模型性能，并討論了未來訓(xùn)練和使用 LM 的方向。

思維樹：利用語言模型進行深思熟慮的問題求解

一個真正的問題求解過程涉及反復(fù)使用可用信息來啟動探索，進而揭示更多信息，直到最終發(fā)現(xiàn)實現(xiàn)解決方案的方法。—— Newell 等

對人類問題求解的研究表明，人類通過搜索一個組合式問題空間來解決問題。這可以看作一棵樹，其中節(jié)點表示部分解，分支對應(yīng)修改它們的運算符。選擇哪個分支是由啟發(fā)式?jīng)Q定的，這些啟發(fā)式幫助導(dǎo)航問題空間并引導(dǎo)問題解決者朝著解決方案的方向前進。這個觀點突出了使用語言模型來解決通用問題的現(xiàn)有方法的兩個關(guān)鍵缺點：1）局部上，它們不探索思維過程中的不同延續(xù) —— 樹的分支。2）全局上，它們不包括任何類型的規(guī)劃、展望或回溯來幫助評估這些不同的選擇 —— 這種啟發(fā)式引導(dǎo)的搜索似乎是人類問題求解的特征。

為了解決這些問題，作者引入了思維樹（ToT），這是一種讓語言模型能夠在思維路徑上探索多種推理方式的范式（圖 1 (c)）。ToT 將任何問題框架化為對樹的搜索，其中每個節(jié)點是一個狀態(tài) s = [x, z_1???i ]，表示帶有輸入和迄今為止的思維序列的部分解。ToT 的具體實例包括回答以下四個問題：

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

1. 思維分解。雖然 CoT 在沒有明確分解的情況下對思維進行連貫的采樣，但 ToT 利用問題屬性來設(shè)計和分解中間思維步驟。如表 1 所示，根據(jù)不同的問題，思維可以是幾個單詞（填字游戲），一個等式（24 點游戲），或者是一段寫作計劃（創(chuàng)意寫作）。一般來說，思維應(yīng)該足夠「?。╯mall）」，以便 LM 能生成預(yù)期多樣化的樣本（如生成太「大（big）」而不連貫一本書），但思維又應(yīng)該足夠「大」，以便 LM 可以評估其解決問題的前景（例如，生成一個 token 通常太小而無法評估）。

2. 思維生成器 G (p_θ， s, k)。給定樹狀態(tài) s = [x, z_1???i]，該研究利用兩種策略來為下一步思維 step 生成 k 個候選對象。

3. 狀態(tài)評估器 V (p_θ， S)。給定不同狀態(tài)的邊界，狀態(tài)評估器評估它們在解決問題方面的進展，以確定哪些狀態(tài)應(yīng)該繼續(xù)探索，以及以何種順序進行探索。雖然啟發(fā)式是解決搜索問題的標準方法，但它們通常要么是編程式的（例如 DeepBlue），要么是需要經(jīng)過學(xué)習(xí)的（例如 AlphaGo）。本文提出第三種替代方法，通過使用語言來有意地推理狀態(tài)。在適用的情況下，這種深思熟慮的啟發(fā)式方法可能比編程規(guī)則更靈活，比學(xué)習(xí)模型更有效。

與思維生成器類似，考慮兩種策略來單獨或一起評估狀態(tài)：

• （1）獨立評估每個狀態(tài)
• （2）跨狀態(tài)投票

這兩種策略，可以多次提示 LM 來整合價值或投票結(jié)果，用時間、資源、成本換得更加可靠、魯棒的啟發(fā)式。

4. 搜索算法。最后，在 ToT 框架內(nèi)，可以根據(jù)樹結(jié)構(gòu)即插即用不同的搜索算法。本文探索了兩個相對簡單的搜索算法，并將更高級的算法留作以后進行研究：

• （1）廣度優(yōu)先搜索（BFS）(算法 1)
• （2）深度優(yōu)先搜索（DFS）(算法 2)

從概念上講，ToT 作為語言模型解決一般問題的方法有幾個好處：

• （1）通用性。IO、CoT、CoT- sc 和自我細化可以看作 ToT 的特殊情況（即深度和廣度有限的樹；圖 1）；
• （2）模塊化。基本的 LM 以及思維分解、生成、評估和搜索過程都可以獨立變化；
• （3）適應(yīng)性?？梢赃m應(yīng)不同的問題屬性、LM 能力和資源約束；
• （4）便捷性。無需額外的訓(xùn)練，只需要一個預(yù)訓(xùn)練的 LM 就足夠了。

實驗結(jié)果

該研究提出了三個任務(wù)，即便使用最先進的語言模型 GPT-4，通過標準的 IO prompting 或思維鏈（CoT）prompting 進行采樣，這些任務(wù)仍然具有挑戰(zhàn)性。

24 點數(shù)學(xué)游戲 

給定四個數(shù)字，玩家需要在限定的時間內(nèi)使用這四個數(shù)字和基本數(shù)學(xué)運算符號（加號、減號、乘號、除號）來創(chuàng)建一個表達式，使其結(jié)果為 24。比如，給定數(shù)字：4、6、8、2，一個可能的解法是：(8 ÷ (4 - 2)) × 6 = 24。

如表 2 所示，使用 IO、CoT 和 CoT-SC prompting 方法在任務(wù)上表現(xiàn)不佳，僅實現(xiàn)了 7.3%、4.0% 和 9.0% 的成功率。相比之下，b（breadth） = 1 的 ToT 已經(jīng)實現(xiàn)了 45% 的成功率，而 b = 5 時則達到了 74%。他們還考慮了 IO/CoT 的 oracle 設(shè)置，通過使用 k 個樣本中的最佳值來計算成功率 (1 ≤ k ≤ 100)。

為了將 IO/CoT（k 個最佳結(jié)果）與 ToT 進行比較，研究者考慮在 ToT 中計算每個任務(wù)中訪問的樹節(jié)點數(shù)量，其中 b = 1???5，并將 5 個成功率映射在圖 3 (a) 中，將 IO/CoT（k 個最佳結(jié)果）視為在賭博機中訪問 k 個節(jié)點。毫不奇怪，CoT 比 IO 更具擴展性，而最好的 100 個 CoT 樣本實現(xiàn)了 49% 的成功率，但仍遠遠不及在 ToT 中探索更多節(jié)點（b > 1）。

下圖 3 (b) 分解了 CoT 和 ToT 樣本在任務(wù)失敗時的情況。值得注意的是，大約 60% 的 CoT 樣本在生成第一步，相當(dāng)于生成前三個單詞 (例如 “4 + 9”) 后就已經(jīng)失敗了。這讓直接從左到右解碼的問題更加凸顯了。

創(chuàng)意寫作

研究者還發(fā)明了一個創(chuàng)意寫作任務(wù)，輸入 4 個隨機句子，輸出一篇包含四段的連貫文章，每段分別以 4 個輸入句子結(jié)尾。這樣的任務(wù)是開放式和探索性的，挑戰(zhàn)了創(chuàng)造性思維和高級規(guī)劃。

下圖 5 (a) 顯示了 GPT-4 在 100 個任務(wù)中的平均分數(shù)，其中 ToT (7.56) 比 IO (6.19) 和 CoT (6.93) 生成了更連貫的段落。雖然這樣的自動度量可能會有噪聲，但圖 5 (b) 證實，人類在 100 passage 對中有 41 對更喜歡 ToT 而不是 CoT，而只有 21 對更喜歡 CoT 而不是 ToT (其他 38 對被發(fā)現(xiàn) “相似連貫”)。

最后，迭代優(yōu)化算法在該自然語言任務(wù)上取得了更好效果，IO 一致性得分從 6.19 提高到 7.67，ToT 一致性得分從 7.56 提高到了 7.91。研究者認為，這可以看作是 ToT 框架中思維生成的第三種方法，新思維可以從細化舊思維中產(chǎn)生，而不是順序生成。

迷你填字游戲

在《24 點數(shù)學(xué)游戲》和創(chuàng)意寫作中，ToT 是比較淺顯的 —— 最多需要 3 個思考步驟就能達到最終的輸出。研究者將探索 5×5 迷你填字游戲作為有關(guān)自然語言的更難一層的搜索問題。同樣，這次的目標不僅僅是解決任務(wù)，因為一般填字游戲可以通過專門的 NLP pipeline 輕松解決，該 pipeline 利用大規(guī)模檢索而不是 LM。相反，研究者的目標是探索語言模型作為一個通用問題求解器的極限，探索它自身的思維，并以嚴謹?shù)耐评碜鳛閱l(fā)式來指導(dǎo)自己的探索。

如下表 3 所示，IO 和 CoT 提示方法表現(xiàn)不佳，單詞級別的成功率低于 16%，而 ToT 顯著提高了所有指標，實現(xiàn)了 60% 的單詞級別成功率，在 20 個游戲中解決了 4 個?？紤]到 IO 和 CoT 缺乏嘗試不同線索、更改決策或回溯的機制，這樣的提升并不令人驚訝。