2.2 Thought generator【thought生成】

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

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

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

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

【24點游戲】是什么？："Game of 24"是一種數(shù)學(xué)益智游戲，旨在通過組合和計算四個給定的數(shù)字（通常是1到9之間的整數(shù)）來得到結(jié)果為24的表達(dá)式。

【24點游戲】thought生成方法：根據(jù)上一個節(jié)點的left（例如：4 9 10 13），把它當(dāng)作限制，生成模塊依次提出多種可能的想法

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

【Mini Crosswords 填字游戲】thought生成方法：直接根據(jù)當(dāng)前節(jié)點已經(jīng)填好的單詞（限制條件），利用prompt方法生成5次，產(chǎn)生下一個詞可能的5種填寫方法。

2.3 State evaluator【狀態(tài)評估】

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

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

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

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

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

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

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

2.4 Search algorithm【搜索算法】

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

BFS（寬度優(yōu)先算法）：每一個步驟保留b個最有前景的方案，本文提到的Game of 24以及Creative Writing就是用的這個算法，其中tree depth限制為（T小于等于3），thoughts step可以先打分（evaluated）然后剪枝到一個小的集合b小于等于5。

DFS（深度優(yōu)先算法）：先探索最有前景的解決方案，直到超過樹的最大深度T（t>T）,或者當(dāng)前state已經(jīng)不可能解決問題了，此時可以直接剪枝，然后回到父節(jié)點，繼續(xù)進(jìn)行探索。

3 Conclusion

在需要non-trivial planing（非平凡的規(guī)劃）或者search（搜索）的任務(wù)中，取得了非常好的表現(xiàn)，例如24點游戲（Game of 24，4個數(shù)湊成24）中，GPT-4+COT只有4%的解決率，本文TOT方法解決率可以達(dá)到74%。

TOT再利用LM解決通用問題時有幾大優(yōu)點：（1）通用性：IO，COT，COT-SC，self-refinement都可以看作TOT的一種特例。（2）模塊化：基礎(chǔ)LM，thought分解，thought生成、評估、搜索都可以獨立的當(dāng)做一個模塊來實現(xiàn)。（3）適應(yīng)能力強(qiáng)：不同的問題，LM，資源限制都能使用。（4）方便：不需要額外的訓(xùn)練，直接用預(yù)訓(xùn)練的LM就足夠了。

4 Limitation

必要性：有些場景GPT4已經(jīng)解決的比較好了，可能用不上。

需要更多資源：多次調(diào)用GPT-4 API等等帶來的cost。

只是離線使用，沒有利用TOT-stype的思想去對LM做fine-tuning，該方法可能更能增強(qiáng)LM解決問題地能力。

二、詳細(xì)內(nèi)容

1三個實驗的定義

【24點游戲】是什么？："Game of 24"是一種數(shù)學(xué)益智游戲，旨在通過組合和計算四個給定的數(shù)字（通常是1到9之間的整數(shù)）來得到結(jié)果為24的表達(dá)式。

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

【創(chuàng)意文本生成】是什么：這個比較好理解，就是生成創(chuàng)意文本。

其他：紅色圈出來的部分為定義的Thoughts中間結(jié)果。

2 搜索算法策略

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

3 Game of 24實驗結(jié)果分析

Table2：IO、CoT和CoT-SC提示方法在任務(wù)上表現(xiàn)較差，僅達(dá)到7.3%、4.0%和9.0%的成功率。相比之下，具有b = 1寬度的ToT的成功率為45%，而b = 5的成功率為74%。

Figure3（a）：比較訪問k個樣本（感覺是生成k次結(jié)果）的情況下，IO，COT，TOT方法的成功率，COT（100）才49%，TOT在30左右就超過60了，在60左右應(yīng)該就有74%的成功率。

Figure3（b）：直接利用COT，有60%左右在第一部就失敗了，這突出了直接從左到右解碼的問題。

4 Creative Writing results和Mini Crosswords results結(jié)果分析

Creative Writing results結(jié)果

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

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

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

Mini Crosswords results結(jié)果

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

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

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

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

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

5Related Work

三、總結(jié)

1. 提出了一種完全由LLM + 啟發(fā)式搜索算法結(jié)合的TOT算法，其可以從多條解決路徑，快速的找到最佳解決方法，可以解決的一些復(fù)雜的，GPT-4都表現(xiàn)差的一些任務(wù)。其主要由thought生成、thought評估、搜索算法組成，可以生成解決方案、對方案進(jìn)行自我評估、同時可以通過回溯算法來延續(xù)之前的解決思路，利用剪枝算法過濾不可靠解決方案，提升找到最優(yōu)解決路徑的速度。

2. TOT其各個部分都是高度模塊化的，例如可以用不同的LM，不同的搜索算法來實現(xiàn)，通用性比較強(qiáng)，同時其對于每個任務(wù)thought的定義都不太一致，如何針對不同的任務(wù)設(shè)置更好的thought也比較重要，他這里提出了“不能太小”、“不能太大”的指導(dǎo)原則可以參考。

3. TOT直接利用LM的評估器效果還有待提高，Mini Crosswords results任務(wù)利用更好的state評估器，可能得到更大的提升，Game級別解決率從20%->35%，說明利用更好的評估器也是非常重要的，可以取得更好的結(jié)果。

4. OpenAI的Andrej Karpathy在state of gpt中也提到了TOT算法，其也可能是比Auto-GPT更好的一種，讓llm進(jìn)行深思熟慮來解決復(fù)雜問題的一種實現(xiàn)思路。