一種完全由LLM + 啟發(fā)式搜索算法結(jié)合的TOT算法

2.2 Thought generator【thought生成】

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

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

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

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

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

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

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

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

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

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

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

【24點(diǎn)游戲】評(píng)估方法：直接利用prompt LM去評(píng)估每個(gè)thoughts為sure、maybe、impossible幾個(gè)選項(xiàng)

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

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

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

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

2.4 Search algorithm【搜索算法】

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

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

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

3 Conclusion

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

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

4 Limitation

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

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

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

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

1三個(gè)實(shí)驗(yàn)的定義

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

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

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

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

2 搜索算法策略

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

3 Game of 24實(shí)驗(yàn)結(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）：比較訪問(wèn)k個(gè)樣本（感覺是生成k次結(jié)果）的情況下，IO，COT，TOT方法的成功率，COT（100）才49%，TOT在30左右就超過(guò)60了，在60左右應(yīng)該就有74%的成功率。

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

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

Creative Writing results結(jié)果

自動(dòng)評(píng)估（連貫性）：ToT (7.56) > CoT (6.93) > IO (6.19)

人工評(píng)估（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) ，這個(gè)提升也挺大的，可以作為一個(gè)新的方法

Mini Crosswords results結(jié)果

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

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

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

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

缺點(diǎn)：感覺用的測(cè)試數(shù)據(jù)不算太多？只用了20個(gè)游戲來(lái)做測(cè)試？

5Related Work

三、總結(jié)

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

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

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

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