### Prompting Engineering
用以控制LLM Output的工程，使用不同的prompt來達到目的。
## Chain of Thought
#### by Google Research, Brain Team

### Chain-of-Thought Prompting 思考鏈提示法
一般大型語言模型在處理的問題涉及圖像、算數時，與其直接輸入問題，將問題轉換成Chain-of-Thought(CoT)的形式後Prompt給模型會顯著地提高正確度，而CoT Prompting著重於給予模型範例時，將==思考的邏輯與推理過程==秀給模型看，如下圖：


以<input, CoT, output>的形式作為few-shot 的 examplar。

### Chain-of-Thought Prompting 好處
1. 可以使模型將multi-step的問題切分成中間的步驟，需要越多解題步驟的問題能被分配到更多的運算資源。
2. Chain-of-Thought可以圖像化模型的解題思路，讓debug時有更有機會找出問題所在 (**注意:使模型完整歸納其運算過程的方法還待研究**)
3. Chain-of-Thought reasoning 可以處理幾乎所有人類能透過語言解決的問題 ex: 數字、常識、符號推理等等
4. 可以透過few shot的Chain-of-Thought prompting使現成的大型語言模型產生有Chain-of-Thought reasoning的output。

### 論文實驗
作者探討使用Chain-of-Thought prompting在Large Language Models中處理算術推理(Arithmetic reasoning)、常識推理與符號推理(Symbolic reasoning)對比標準prompting的差別。

#### 算術推理 Arithmetic reasoning

作者花了大片篇幅在論證CoT的算術推理，因為在確認了CoT可以顯著地improve solve rate(下圖左)之後，作者進行了各種的ablation study，如：
- 要求模型**在CoT中只能output equation而沒有自然語言推論的步驟**
- 要求模型的**CoT只output跟解題中equation推論中使用的總字元數量相同的dot**以測試用自然語言來進行推理的重要性
- **把CoT移到answer之後**以測試在答案前就給CoT是否有activate knowledge的作用

使用的
從下圖中可以知道，CoT能顯著提升solve rate並不是單獨建基於幾個variant，而是整個CoT。

之前的文獻有提及，更改examplars的排列可以使GPT-3的accuracy ranging from 54.3%到93.4%，因此作者想針對CoT的註解style的影響做分析。
結果發現不同的CoT style，儘管彼此之間的solve rate稍有差異，但只要使用了CoT，就能使Model表現出遠超baseline的solve rate!(如上圖右)

#### 常識推理(Commonsense Reasoning)
常識推理是透過廣泛的背景知識來對涉及物理上及人類的互動進行假設推理。
只要擁有足夠參數量的Model，使用CoT prompting來進行常識推理一樣是參數量越多，improvement越顯著，如下圖，針對不同的常識推理dataset和不同參數量的Model，CoT prompting與標準prompting的表現比較。


#### 符號推理(Symbolic reasoning)

人類進行抽象思考時通常會涉及內心的圖像，這種思考模式對人類可能很簡單，但對language model就不容易了。CoT prompting不只可以使LLM進行涉及複雜語境的符號推理，也可以使Model能處理比examplars更長的input，作者也設計了兩種實驗來測試CoT prompting使LLM進行符號推理的能力。

- 請Model將input的姓名中每個字的字尾串在一起，如 $Amy \space Brown \rightarrow yn$
- 在一些人有翻一些人沒翻硬幣之後判斷硬幣的正反

而所有test set的字數(name)/steps(coin)跟training examplars一樣時稱為in domain，其他則是OOD(out-of-domain)。從實驗結果(下圖)可以知道使用CoT prompting的Model在符號推理上不管是OOD、in domain都能有顯著的進步。


### 討論與重點整理
- **Chain of Thought Prompting**確實可以使足夠參數的大型語言模型針對不同類型的問題更好地output出正確的結果。
- **Chain of Thought是模仿人類推理模式，但這樣的prompting有沒有使得Model真的在進行「推理」還有待研究。**
- 推理的路徑並不一定是正確的，可能推理正確但結果錯誤，vice versa。
- 可以參照作者在Appendix附上的方法手工compose數字題的Chain of Thought Prompting嘗試引出Model的reasoning過程。

#### 作者針對數字題目的prompting方法


Reference: [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://arxiv.org/pdf/2201.11903.pdf),
[Self-consistency improves chain of thought reasoning in Language Models](https://arxiv.org/pdf/2203.11171.pdf)

## Tree of Thought
前文我們知道 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)

## Implementation
### API
### Price
#### GPT-4
#### GPT-3.5
### Token 計算
### 用 python 使用API


[Token計算](https://platform.openai.com/tokenizer)