今天分享一篇普林斯頓大學的一篇文章，Tree of Thoughts: Deliberate Problem Solving with Large Language Models[1]：思維之樹:用大型語言模型解決復雜問題。

這篇工作還是非常有借鑒意義的，OpenAI的Andrej Karpathy（前Tesla AI高級總監、自動駕駛Autopilot負責人）在state of gpt[2]中也分享了這篇文章，其可以通過搜索多條解決路徑，利用dfs以及bfs等算法，像人類一樣利用回溯、剪枝等策略來思考和解決問題，可以讓GPT-4解決一些更復雜的推理問題。

一、概述

Title：Tree of Thoughts: Deliberate Problem Solving with Large Language Models

論文地址：https://arxiv.org/abs/2305.10601

論文代碼：https://github.com/princeton-nlp/tree-of-thought-llm

非官方代碼：https://github.com/kyegomez/tree-of-thoughts

1 Motivation

1. 大模型的推理過程是一個token級別的，從左到右的一個決策過程，對比人類的思考方式來說，有著非常大的局限（例如人類寫文章，寫著寫著發現寫錯了，我們可以回過頭來，重新修改前面的內容，然后再繼續往后寫，而大模型LM不能這樣），這使得大模型在需要探索，全局分析（前瞻探索或者回溯），初步決策發揮關鍵作用的任務中效果不太好。

2. 現有大模型的缺點：1）局部性：現有LM模型不會在思維過程中探索不同的延續，即不會去探索當前節點的其他分支解決方案。2）缺乏全局性：大模型LM沒有納入任何類型的規劃、展望或回溯來幫助評估不同的選項。
3. 人類推理特點：可以重復使用可用的信息來進行啟發式的探索，促使挖掘出更多真正有用的信息，找到最終的解決方案。

2 Methods

• 提出了Tree of Thoughts（ToT）方法：其允許LM通過考慮多種不同的推理路徑并且能進行自我評估選擇來決定下一步行動，并在必要時looking ahead或回溯以做出全局選擇（可以用dfs或者bfs等方法做全局探索），從而進行深思熟慮的決策。
• 主要通過Thought decomposition【thought分解】，Thought generator【thought生成】，State evaluator【狀態評估】，Search algorithm【搜索算法】四個步驟完成，詳情如下。

2.1 Thought decomposition【thought分解】

目的：如何將中間過程分解成一個思維步驟【不同任務的thought steps怎么設計比較好】

方法：不同的任務，中間的思考過程thought可能不同，例如可能是幾個words（Crosswords填字謎游戲），可能是一個equation（24點游戲），也可能是一個paragraph（創意文本生成），設計thoughts可以有幾個原則：

• 不能太大：這樣LM可以生成有前景的、多樣性的候選樣本（例如一整本書就太大了）
• 不能太小：太小了LM不好評估其對最終解決問題是否有幫助（例如只生成一個token，LM無法評估其是否有用）

2.2 Thought generator【thought生成】

背景：不同的任務Thought生成的原則也不太一樣，可以根據任務的特點制定thought生成的原則。

• 原則一：當thought空間比較大【例如創意寫作，thought位一個段落】 => 可以用CoT prompt的方法來生成

• 例子一：【創意文本生成】thought生成方法：直接用COT方法提出多個Plans

• 原則二：當thought空間比較小【例如只有幾個字（字謎游戲），或者只有一行（24點游戲）】 => 使用“propose prompt”依次提出想法，例如下面兩個例子：

• 【24點游戲】是什么？："Game of 24"是一種數學益智游戲，旨在通過組合和計算四個給定的數字（通常是1到9之間的整數）來得到結果為24的表達式。
• 【24點游戲】thought生成方法：根據上一個節點的left（例如：4 9 10 13），把它當作限制，生成模塊依次提出多種可能的想法

【Mini Crosswords 填字游戲】是什么？：Mini Crosswords是一種簡化版的填字游戲，適合在有限的空間和時間內進行。與傳統的填字游戲不同，Mini Crosswords使用較小的網格，通常為5x5或6x6，且只包含較少的單詞。每個單詞都有一個提示，玩家需要根據提示填寫正確的單詞。

【Mini Crosswords 填字游戲】thought生成方法：直接根據當前節點已經填好的單詞（限制條件），利用prompt方法生成5次，產生下一個詞可能的5種填寫方法。

2.3 State evaluator【狀態評估】

定義：給定不同的當前state狀態，state evalutor用于評估那個方法最有接近解決當前問題。通常是利用heuristis方法來解決，像deepBlue是用編程的方法來解決，AlphaGo是用學習的方法來解決，本文直接是用LM去評估和思考當前state解決問題的前景。同樣的，針對不同的任務也有不同的評估方法。這里主要提出兩種策略：

• 原則一：【獨立評估】，當每個state獨立時并且好用數值型的方式來評估時，直接利用prompt生成數值型或者類別性的評估結果，這里可以利用一些前瞻性的模擬（例如：5+5+14可以湊成24點） + 常識commonsense（例如：1,2,3太小了，夠不到24點）來直接給出 good 或者 bad的評價，并且不要求特別準確。

【24點游戲】評估方法：直接利用prompt LM去評估每個thoughts為sure、maybe、impossible幾個選項

【Mini Crosswords 填字游戲】評估方法：直接利用prompt評估每個candidates的confidence（sure、impossible、maybe）

• 原則二：【對所有state投票】：當評估passage coherency（段落連貫性），不是特別好用數值型的方法來評估時，通過vote prompt來詳細比較不同的state，選出一個最優前景的方案，例如可以將多個state拼接成一個多選題，然后利用LM來對其進行投票。

【創意文本生成】評估方法：直接利用LM投票從多個state中選擇最好的一個，例如使用以下prompt：“analyze choices below，then conclude which is most promising for the instruction”

其他：對于每一種策略，都可以利用LM prompt多次集成多次的value分數或者vote投票提升其魯棒性。

2.4 Search algorithm【搜索算法】

說明：對于樹的結構，有很多中搜索算法，本文探索了兩種簡單的搜索算法BFS和DFS。

• BFS（寬度優先算法）：每一個步驟保留b個最有前景的方案，本文提到的Game of 24以及Creative Writing就是用的這個算法，其中tree depth限制為（T小于等于3），thoughts step可以先打分（evaluated）然后剪枝到一個小的集合b小于等于5。
• DFS（深度優先算法）：先探索最有前景的解決方案，直到超過樹的最大深度T（t>T）,或者當前state已經不可能解決問題了，此時可以直接剪枝，然后回到父節點，繼續進行探索。

3 Conclusion

• 在需要non-trivial planing（非平凡的規劃）或者search（搜索）的任務中，取得了非常好的表現，例如24點游戲（Game of 24，4個數湊成24）中，GPT-4+COT只有4%的解決率，本文TOT方法解決率可以達到74%。
• TOT再利用LM解決通用問題時有幾大優點：（1）通用性：IO，COT，COT-SC，self-refinement都可以看作TOT的一種特例。（2）模塊化：基礎LM，thought分解，thought生成、評估、搜索都可以獨立的當做一個模塊來實現。（3）適應能力強：不同的問題，LM，資源限制都能使用。（4）方便：不需要額外的訓練，直接用預訓練的LM就足夠了。

4 Limitation

1. 必要性：有些場景GPT4已經解決的比較好了，可能用不上。
2. 需要更多資源：多次調用GPT-4 API等等帶來的cost。
3. 只是離線使用，沒有利用TOT-stype的思想去對LM做fine-tuning，該方法可能更能增強LM解決問題地能力。

二、詳細內容

1 三個實驗的定義

• 【24點游戲】是什么？："Game of 24"是一種數學益智游戲，旨在通過組合和計算四個給定的數字（通常是1到9之間的整數）來得到結果為24的表達式。
• 【Mini Crosswords 填字游戲】是什么？：Mini Crosswords是一種簡化版的填字游戲，適合在有限的空間和時間內進行。與傳統的填字游戲不同，Mini Crosswords使用較小的網格，通常為5x5或6x6，且只包含較少的單詞。每個單詞都有一個提示，玩家需要根據提示填寫正確的單詞。
• 【創意文本生成】是什么：這個比較好理解，就是生成創意文本。
• 其他：紅色圈出來的部分為定義的Thoughts中間結果。

2 搜索算法策略

特點：利用BFS，可以像人類一樣，一直探索比較好的b個（寬度）實現方法。利用DFS方法，可以方便的進行剪枝，回溯，像人一樣，當前路走不通，我退回上一個不走重新選擇。相對于之前的COT等從左到右的思想策略，理論上感覺確實會有著比較大的提升空間。

3 Game of 24實驗結果分析

• Table2：IO、CoT和CoT-SC提示方法在任務上表現較差，僅達到7.3%、4.0%和9.0%的成功率。相比之下，具有b = 1寬度的ToT的成功率為45%，而b = 5的成功率為74%。
• Figure3（a）：比較訪問k個樣本（感覺是生成k次結果）的情況下，IO，COT，TOT方法的成功率，COT（100）才49%，TOT在30左右就超過60了，在60左右應該就有74%的成功率。
• Figure3（b）：直接利用COT，有60%左右在第一部就失敗了，這突出了直接從左到右解碼的問題。

4 Creative Writing results和Mini Crosswords results結果分析

• Creative Writing results結果

自動評估（連貫性）：ToT (7.56) > CoT (6.93) > IO (6.19)

人工評估（GSB）：ToT vs COT G：S：B = (41：38 ：21)

iterative-refine（舊的thought -> refine -> 新的thought）：迭代優化還能繼續提升，ToT (7.56 -> 7.91) ，IO (6.19 -> 7.17) ，這個提升也挺大的，可以作為一個新的方法

• Mini Crosswords results結果

Letter（字母級別準確率）：ToT (78) > CoT (40.6) > IO (38.8)

Word（字級別準確率）：ToT (60） > CoT (15.6) > IO (14)

Game（游戲級別解決率）：ToT (20) > CoT (1) > IO (0)

消融實驗：（1）+best state：利用更好的state評估器，可能得到更大的提升，Game級別解決率從20%->35%，說明本文提到的簡單的啟發式的評估算法還有比較大的空間。（2）剪枝：去掉剪枝，只能解決1個問題，另外3個都是通過啟發式的剪枝找到的，說明這種方法對于解決問題是至關重要的。（3）回溯：去掉回溯算法后，效果表現比較差，說明有延續性的這種尋找答案的方法也是非常重要的。

• 缺點：感覺用的測試數據不算太多？只用了20個游戲來做測試？

5 Related Work

三、總結

本文轉載自NLP PaperWeekly，作者： HxShine ????