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

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

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

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

項(xiàng)目地址：https://github.com/ysymyth/tree-of-thought-llm

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

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

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

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

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

一個(gè)真正的問題求解過程涉及反復(fù)使用可用信息來啟動(dòng)探索，進(jìn)而揭示更多信息，直到最終發(fā)現(xiàn)實(shí)現(xiàn)解決方案的方法?！?Newell 等

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

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

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

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

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

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

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

• （1）獨(dú)立評(píng)估每個(gè)狀態(tài)
• （2）跨狀態(tài)投票

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

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

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

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

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

實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

創(chuàng)意寫作

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

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

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

迷你填字游戲

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

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