# Tree of Thoughts: Deliberate Problem Solving with Large Language Models 論文導讀

#### 背景知識請看 [Chain-of-Thought Prompting / Self-consistency in LLMs 論文導讀](https://hackmd.io/@chrizeroxtwo/SkaL8PUE3)
前文我們知道 Chain of Thought Prompting 可以針對不同涉及常識、算數、符號等推理讓LLM的Output更加理想，而Self Consistency利用Sampling不同的Reasoning path後選取最高頻率的output增加了精准度，但Tree of Thought(ToT)的作者認為單純Sample Language Sequence的解題方式並無法使LLM完全複製人類的解題方式成為General Problem Solver。

作者先回顧Kahneman的[《快思慢想》](https://www.youtube.com/watch?v=cJn2Bihh-_E)和之前的dual thinking心理學研究顯示的人類做思考的兩種模式，快速、自動、無意識的「系統一」和緩慢、深思熟慮、需集中精神的「系統二」，兩者在之前的ML的運用。LM的每個token生成與選擇就像是「系統一」，「系統二」則需要不停考慮不同於現在的Choice和評斷現在的思考狀態而選擇往下進行還是回到上一步(backtrack)而能做出更好的全域(Global)判斷，因此可以使LLM「系統一」的Output更完善。

**作者比較不同Prompting Method**

作者比較了之前的幾種在LLM reasoning表現不俗的Prompting Method，包含直接給few shot examplars的Input-Output Prompting、前面提過的Chain-of-thought和Self-Consistency with CoT，其中只有Self Consistency有些許涉及「系統二」的判斷，但僅止於Global Scale的reasoning path sampling，local的intermediate step並沒有涉及「系統二」的思考和選擇，因此並無法使整個LLM完全模仿人類的dual thinking，且其sampling output的方式只限於有限的output space(如multi-choice QA)。

### Tree of Thought(ToT)
作者因此提出了Tree of Thought(ToT,樹型思考)，將問題prompt給LLM後，請其在每一個中間step給出好幾個candidate thoughts，對每一個thought評分後，再請LLM根據最高評分的thought給出下一層的(下一個step的)candidate thoughts，若遇到判斷不可能reach到理想output的thought時，又無其他sibling thoughts時就backtrack(DFS only)到上一個母thought的其他siblings，同時pruning(剪枝)，原理同資料結構的tree，可以在Local的每一個Thought進行「系統二」的思考，最終導向單一最好的Output。
實作方面，作者融合了資料結構中Tree Searching的Algorithm，BFS(Breadth-first search)和DFS(Depth-first search)。
#### ToT-BFS 作者使用於需要的Steps數較低的Game of 24和Creative Writing
ToT-BFS沒有Backtrack，是一層層遍歷(traverse)每一個thought。
1. $x$ 是initial input
2. $G(p_{θ},s,k)$ 是透過LM產生的所有子代node(thought)，較長的子代thought可以用sample的(一次給出一個thought)，因為每次得到一樣答案的機率較低(e.g. creative writing)，較短的thought則用propose的，亦即一次條列式output每一個子代thought以避免重複(e.g.Game of 24)
3. $k$ 是每一個node最大的degree，亦即最多可以有幾個子thought
4. $V(p_{θ},S_{t}')$ 是請LM透過value或vote來判斷子代thought集合中元素的評分
5. $T$ 則是最多允許 $T$ 個thought searching steps
6. $b$ 是 $V(p_{θ},S_{t}')$ 判斷最好的前一層的前 $b$ 個thought集合

ToT-BFS會參照前一層做出的前 $b$ 個最高value的node(thought)生成下一層每個thought 各k個children thought，再利用 $V(p_{θ},S_{t}')$ 將children thought 的 value assign 給 $V_{t}$ 的array，再取 $V_{t}$ 的前 $b$ 大的value 的 $arg max$ 作為生成下一層children thought的參照，直到 $t=T$ ，最後一次traverse後，return最後5個candidates中，有$V_{T}$ 最大值的thought的output。

#### ToT-DFS 作者在較困難的Mini Crosswords資料集實驗中使用的DFS(Algorithm 2)
1. $s$ 是現在的node(thought)
2. $t$ 是現在是第幾個step，亦即樹的第幾層(level)
3. $G(p_{θ},s,k)$ , $k$ 和 $T$ 同BFS
4. $V(p_{θ},\{s'\})(s)$ 是請LM透過value或vote來判斷子代thought的評分
5. $v_{thres}$ 是設定一個子代的value/vote threshold，即當 $V(p_{θ},\{s'\})(s) > v_{thres}$ 時判斷這個子代thought不可能到達理想的output，可以查看下一個子代thought或backtrack，同時pruning(剪枝掉這個子代node)

透過遞迴DFS直到$t>T$，取最深的node作為最佳的Output(有超過一個的話取第一個到達的)，順帶一提，作者的pesudo code似乎漏掉了backtrack的過程，不過實作是在Mini crosswords有使用的。

### 實驗資料與結果
使用的資料集有三種，**Game of 24、Creative Writing和Mini Crosswords**
**Game of 24** 是給定一些數字，目標是使用基本的四則運算將其湊成24，同時請LM evaluate自己的thought有沒有可能湊到24，按照可能性給impossible/maybe/sure的評分。
**Creative Writing** 是使用給定的幾個句子寫一篇短文，並將給定的句子作為各段的結尾，短文必須前後連貫，並讓LM針對自己要寫的短文的每個步驟進行vote(review全部的thought好幾次)來決定這個thought/plan合不合理。
**Mini Crosswords** 是類似數獨的概念，讓 $5\times5$ 的matrix在每一行跟每一列都是有意義的Words，因為需要考慮global範圍的matrix恰當性，所以使用可以backtrack的DFS，每一次access都會再讓LM評估它影響的global範圍其他字的可能性(一樣是impossible/maybe/sure)來決定要繼續往下還是prune然後拜訪其它sibling node或backtrack到 parent node。


可以看出ToT對Game of 24相比於過去的CoT等方法有超過8倍的進步，非常的驚人，同時在需要多層次思考的Mini crosswords也有非常強大的表現，對Creative Writing的進步是有，但就不是那麼顯著，不過可以看出Tree of Thought的確是Prompting Engineering的一個突破點，我認為某種程度上就是iterative reasoning，可以就不同的演算法來輔助LLM的思考過程。

Reference: [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://arxiv.org/pdf/2305.10601.pdf), [princeton-nlp/tree-of-thought-llm (Github)](https://github.com/princeton-nlp/tree-of-thought-llm)