Tree of Thoughts: Deliberate Problem Solving with Large Language Models
https://github.com/princeton-nlp/tree-of-thought-llm

標題翻譯：思維樹：利用大型語言模型問題求解

1. 內容介紹

1.1. 背景

決策過程有兩種模式：

1. 快速、自動、無意識的模式（System 1）-- 語言模型基于語言的token聯想生成
2. 緩慢、謹慎、有意識的模式(System 2) – 多樣化選擇和規劃的過程

現有的LLM方法在復雜問題中面臨兩大局限：

• 局部探索不足：在生成過程中不能同時探索多種可能的推理路徑
• 缺乏全局規劃：沒有能力回溯或前瞻，導致路徑選擇可能陷入局部最優解

論文提出了思維樹的框架，可以與搜索算法相結合，例如廣度優先搜索（BFS）或深度優先搜索（DFS）來進行前瞻、回溯和狀態評估。

---

1.2. 對比圖：

• IO：傳統的從輸入直接生成輸出，屬于單步決策，無探索過程
• CoT：通過生成一系列中間步驟（思維鏈）來推導最終結果，但每次僅沿單一路徑生成，缺乏分支探索能力
• SC-CoT：通過采樣多條獨立的思維鏈，利用多數投票機制實現自一致性
• ToT：允許在每個思維步驟生成多種可能的中間狀態，并選擇最有希望的分支，每個分支的狀態可以通過啟發式評估（如評分或投票）確定是否繼續擴展

---

1.3. 什么是思維？

根據不同的問題，一個思維可能是：

• 填字游戲：幾個單詞
• 24點：一行算式
• 創意寫作：一段文字

---

2. 研究方法

2.1. 框架設計：ToT框架圍繞以下四個核心問題展開

• 如何分解問題？-- 思維分解：將復雜問題分解為多個中間步驟，每個步驟稱為一個思維，思維需要足夠小以保證模型能生成多樣化候選解，又要足夠大以便評估

• 如何生成候選解？ – 思維生成器G(p,s,k)={z1,z2…zk}：輸入當前的狀態s=[x,z1,z2…zi]（x表示問題，z是中間的思維），利用語言模型p生成k個候選思維z
  有兩種生成策略：

  1. 隨機生成：用COT獨立隨機生成k個候選解，多樣性更好，適合開放性任務（如寫作）；
  2. 順序生成：在同一上下文中逐步生成k個候選解，適合約束較強的任務（如數學問題）

• 如何評估候選狀態？ – 狀態評估器V(p,S)(s)=score：給定多個候選狀態的集合S，通過啟發式方法評估
  有兩種評估策略：

  1. 獨立價值評估：為每個狀態s生成一個分數（如 1-10）或分類標簽（如 “sure” / “maybe” / “impossible”）；
  2. 投票評估：跨狀態比較，通過對比多個狀態，選擇最有潛力的一個（類似于SC）。對于這兩種策略，都可以多次提示LM來整合價值或投票結果

• 如何搜索最優路徑？-- 選擇什么搜索算法：
  

  1. BFS: 每層保留b個最優狀態，逐層展開,適合24點這種層少的
  2. DFS:首先探索最有希望的狀態，直到達到最深；或者狀態評估器認為從當前狀態s解決問題是不可能的（價值V < v_th（臨界值）），就修剪停止擴展并回溯到s的父狀態

2.2. 優點：

• 模塊化與靈活性：可以分別調整上面四個模塊，選擇不同LM,思維生成策略，狀態評估策略，搜索算法

• 高適應性：針對不同任務可以有不同的策略

• 無需額外訓練

3. 實驗

3.1. 24點任務：100個實例

3.1.1. 步驟

將問題分解為3步，每步生成一個中間算式，然后使用BFS（b=5）確保所有可能的算式都被探索，且通過啟發式評估篩選出最有潛力的路徑（順序生成，獨立評估，BFS）

• 步驟1：從四個數字中選取兩個進行運算，生成一個新的狀態（例如4+9=13或者10-4=6）

• 步驟2：使用剩余的數字進行下一步操作，生成新的候選狀態

• 步驟3：根據啟發式評估（分類標簽），判斷當前狀態是否有可能最終達成目標24

3.1.2. 結果：

對于每種方法，選擇100次嘗試中的最好結果，作為理論上的最佳表現

• 表2：

  • IO prompt：傳統的輸入輸出方法，直接從輸入（數字）到輸出（算式）進行推理，但沒有中間推理過程

  • CoT prompt：生成一系列中間步驟，逐步推導結果

  • CoT-SC：使用k個CoT的樣本，通過投票選擇最常見的答案，以增強推理的多樣性

  • IO + Refine：對IO方法進行迭代優化，在每次生成后進行反思和修正

• 圖3a：訪問節點越多，成功率越高，ToT能夠探索更多的路徑，從而大大提高成功率

• 圖3b：CoT方法容易在推理的初期階段就走錯路徑，但TOT因為有評估并能夠進行回溯修正所以能夠保持更高的成功率

3.2. 創意寫作任務：

根據四個隨機的句子生成一篇連貫的文章，每段結尾包含一個輸入句子（隨機生成，投票評估，BFS）

3.2.1. 步驟

• 生成計劃：根據輸入生成多個寫作計劃
• 評估計劃：對計劃投票
• 生成完整段落：根據最好的計劃生成多個完整段落
• 評估段落：再對完整的段落再進行投票，選擇最連貫的段落生成方案

3.2.2. 結果：用GPT-4（1-10分）和人類來評估每個生成的段落的質量

都是ToT方式得分最好

---

3.3. **5×5Mini填詞任務：

20個實例，評估，正確字母的比例（每個游戲25個）、單詞數（每個游戲10個）和完成游戲數 （順序生成，獨立評估，DFS）

3.3.1. 步驟

• 候選生成：根據字謎提示生成多個候選單詞
• 啟發式評估：每個候選單詞會通過啟發式評估器進行評分，判斷其與其他已填單詞的交叉匹配程度，根據得分選擇得分最高的單詞填入網格，并繼續處理其他空格，如果某個單詞導致沖突（如垂直或水平單詞不匹配），就修剪掉并回溯到上一步的，選擇其他候選單詞

3.3.2. 結果：

通過假設理想化的評估機制（Oracle），來模擬最優路徑選擇，模擬ToT上限，能達到35%的游戲完成率，可能是因為5×5填字游戲設計中有一些GPT-4無法識別的罕見或過時單詞

去掉剪枝或者去掉回溯后效果表現均不佳

---

3.4. 消融實驗

換了點更艱難的任務，然后換了LM版本比較

---

3.5. 計算成本

計算成本相對來說很大

---

4. 總結：

ToT通過探索不同路徑、評估中間狀態并進行全局優化，提高模型在復雜任務中的問題解決能力
未來的方向還是LLM的微調和更高效的搜索算法（如A*）