思維樹：大模型的復(fù)雜推理技術(shù)

論文標(biāo)題：Tree of Thoughts: Deliberate Problem Solving with Large Language Models
論文鏈接：https://arxiv.org/abs/2305.10601
論文來源：arXiv

一勒叠、概述

語言模型(LM)比如GPT镀裤、PaLM等，雖然最初是為生成文本而設(shè)計缴饭，但它們的大規(guī)模版本已經(jīng)顯示出了越來越強(qiáng)的多任務(wù)推理能力，可以進(jìn)行數(shù)學(xué)骆莹、符號颗搂、常識和知識推理∧豢眩或許令人驚訝的是丢氢，所有這些進(jìn)步的底層仍然是最初的在文本生成中的自回歸機(jī)制傅联，它逐個詞地、從左到右地做出決策疚察。這樣一個簡單的機(jī)制是否足以構(gòu)建一個通用問題求解器蒸走？如果不夠，會有哪些問題挑戰(zhàn)現(xiàn)有范式貌嫡？又需要什么替代機(jī)制比驻？

關(guān)于人類認(rèn)知的研究提供了一些線索來回答這些問題〉撼“雙進(jìn)程(dual process)”模型的研究表明别惦，人們在做決策時有兩種模式 —— 一種是快速、自動夫椭、無意識的(fast, automatic, unconscious)模式(“系統(tǒng)1”)掸掸，一種是慢速、經(jīng)過深思熟慮蹭秋、有意識的(slow, deliberate, conscious)模式(“系統(tǒng)2”)扰付。這兩種模式之前就與機(jī)器學(xué)習(xí)中使用的各種數(shù)學(xué)模型相關(guān)聯(lián)過。例如仁讨，關(guān)于人類和其他動物的強(qiáng)化學(xué)習(xí)研究已經(jīng)探討了它們什么時候進(jìn)行聯(lián)想的“模型無關(guān)”學(xué)習(xí)羽莺，什么時候進(jìn)行更深思熟慮的“模型相關(guān)”規(guī)劃。語言模型簡單的聯(lián)想式逐詞選擇也與“系統(tǒng)1”相似陪竿，因此可能會從一種更深思熟慮的“系統(tǒng)2”規(guī)劃過程中獲益禽翼，這種過程(1)維護(hù)和探索當(dāng)前選擇的各種可能性，而不僅僅選擇一個族跛，(2)評估其當(dāng)前狀態(tài)闰挡，并主動前瞻或回溯(lookahead or backtracking)以做出更全局的決策。

為了設(shè)計這樣的規(guī)劃流程礁哄，我們回歸人工智能(和認(rèn)知科學(xué))的起源长酗，從Newell, Shaw和Simon在20世紀(jì)50年代探索的規(guī)劃流程中獲得啟發(fā)。Newell等人將問題求解表征為在組合問題空間(combinatorial problem space)中進(jìn)行搜索桐绒，用樹來表示夺脾。因此我們?yōu)檎Z言模型的通用問題求解提出了“思維樹”(Tree of Thoughts， ToT)框架茉继。如下圖所示咧叭，現(xiàn)有的方法對問題求解采樣連續(xù)的語言序列，而ToT主動維護(hù)一個思維樹烁竭，其中每個thought都是連貫的(coherent)語言序列菲茬，作為問題求解的中間步驟。這樣一個高層語義單元使得語言模型能夠通過精心的推理過程來自我評估(self-evaluate)不同的中間thought對于解決問題的進(jìn)展。本文通過語言模型的自我評估和推理來實現(xiàn)搜索啟發(fā)式方法是新穎的婉弹，因為以前的搜索啟發(fā)式方法要么是編程實現(xiàn)的睬魂，要么是學(xué)習(xí)得到的。最后镀赌，我們將這種生成和評估多樣thought的基于語言的能力與搜索算法(如廣度優(yōu)先搜索BFS或深度優(yōu)先搜索DFS)相結(jié)合氯哮，這使得我們可以系統(tǒng)地探索思維樹以進(jìn)行前瞻和回溯。

推理方法

本文的實驗提出了三個新的問題商佛，它們即使對最先進(jìn)的語言模型GPT-4也具有挑戰(zhàn)性:24點游戲喉钢、創(chuàng)意寫作和填字游戲(Game of 24, Creative Writing, and Crosswords)。這些任務(wù)需要演繹推理威彰、數(shù)學(xué)出牧、常識和詞匯推理的能力，以及一種將系統(tǒng)的規(guī)劃或搜索融入的方式歇盼。我們表明舔痕，通過支持不同層次的thought、生成和評估thought的不同方式豹缀、根據(jù)不同問題性質(zhì)采用不同的搜索算法伯复，ToT框架對所有三個任務(wù)都取得了優(yōu)越的結(jié)果。我們還通過系統(tǒng)的消融實驗分析了這些選擇如何影響模型表現(xiàn)邢笙，并討論了進(jìn)一步訓(xùn)練和使用語言模型的未來方向啸如。

二、背景

我們首先形式化一些使用大型語言模型進(jìn)行問題求解的現(xiàn)有方法氮惯，我們的方法受到這些方法的啟發(fā)并與之進(jìn)行了比較叮雳。我們使用 $p_{\theta }$ 表示一個預(yù)訓(xùn)練語言模型及其參數(shù) $\theta$ ，使用小寫字母 $x,y,z,s,\cdots$ 表示一個語言序列妇汗，即 $x=(x[1],\cdots ,x[n])$ 帘不，其中每個 $x[1]$ 是一個token，因此 $p_{\theta }(x)=\prod_{i=1}^{n}p_{\theta }(x[i]|x[1\cdots i-1])$ 杨箭。我們使用大寫字母 $S寞焙，\cdots$ 表示一組語言序列。

Input-output (IO) prompting

Input-output (IO) prompting是最常見的將問題輸入 $x$ 轉(zhuǎn)化為語言模型輸出 $y$ 的方式: $y\sim p_{\theta }(y|\mathrm{prompt}_{IO}(x))$ 互婿，其中 $\mathrm{prompt}_{IO}(x)$ 在輸入 $x$ 周圍包裹任務(wù)說明和/或小樣本輸入輸出示例捣郊。為簡單起見，我們記 $p_{\theta }^{\mathrm{prompt}}(\mathrm{output}|\mathrm{input})=p_{\theta }(\mathrm{output}|\mathrm{prompt}(\mathrm{input}))$ 慈参，所以IO提示可以表示為 $y\sim p_{\theta }^{IO}(y|x)$ 呛牲。

Chain-of-thought (CoT) prompting

Chain-of-thought (CoT) prompting是為了解決輸入 $x$ 到輸出 $y$ 之間的映射更困難的情況而提出的(例如當(dāng) $x$ 是一個數(shù)學(xué)問題而 $y$ 是最終的數(shù)值答案)。其關(guān)鍵思想是引入一條思維鏈 $z_{1},\cdots ,z_{n}$ 來橋接 $x$ 和 $y$ 驮配，其中每個 $z_{i}$ 是一個連貫的語言序列侈净，作為有意義的中間步驟來解決問題(例如尊勿， $z_{i}$ 可以是數(shù)學(xué)問答的中間方程)。為了用CoT求解問題畜侦，每個thought $z_{i}\sim p_{\theta }^{CoT}(z_{i}|x,z_{1\cdots i-1})$ 都是順序生成的，然后輸出 $y\sim p_{\theta }^{CoT}(y|x,z_{1\cdots n})$ 躯保。實踐中旋膳， $[z_{1\cdots n},y]\sim p_{\theta }^{CoT}(z_{1\cdots n},y|x)$ 作為一個連續(xù)的語言序列進(jìn)行采樣，thought的分解(decomposition)是模糊的（也就是關(guān)于每個 $z_{i}$ 是一個短語途事、一個句子還是段落）验懊，也就是說thought之間沒有明確的邊界。

Self-consistency with CoT (CoT-SC)

Self-consistency with CoT (CoT-SC)是一種集成方法尸变，它采樣 $k$ 條獨立同分布的思維鏈: $[z_{1\cdots n}^{(i)},y^{(i)}]\sim p_{\theta }^{CoT}(z_{1\cdots n},y|x)(i=1\cdots k)$ 义图，然后返回最頻繁的輸出: $argmax_{y}\#\left \{i|y^{(i)}=y\right \}$ 。CoT-SC改進(jìn)了CoT召烂，因為對于同一個問題通常有不同的思考過程(例如證明同一定理的不同方法)碱工，通過探索更豐富的thought集合，輸出決策可以更可靠奏夫。但是怕篷，在每條鏈內(nèi)部都沒有對不同thought步驟的局部探索，而且“最頻繁”這種啟發(fā)式方法只適用于輸出空間有限的情況(例如多項選擇問答)酗昼。

三廊谓、方法

A genuine problem-solving process involves the repeated use of available information to initiate exploration, which discloses, in turn, more information until a way to attain the solution is finally discovered. —— Newell et al.

關(guān)于人類求解問題的研究表明，人們在組合問題空間(也就是一個樹結(jié)構(gòu))中進(jìn)行搜索麻削，其中節(jié)點表示部分解決方案蒸痹，分支對應(yīng)修改它們的操作符。選擇哪條分支由啟發(fā)式方法決定呛哟，這有助于在問題空間中導(dǎo)航叠荠，引導(dǎo)問題求解者朝著解決方案的方向前進(jìn)。這一視角突出了現(xiàn)有使用語言模型求解一般問題方法的兩個關(guān)鍵缺陷:(1) 在局部上竖共，它們不搜索思維過程中的不同延續(xù) - 樹的分支蝙叛；(2) 在全局上，它們沒有融入任何類型的規(guī)劃公给、前瞻或回溯以幫助評估這些不同選項 —— 這種啟發(fā)式引導(dǎo)搜索似乎是人類求解問題方式的特征借帘。

為了解決這些缺陷，我們提出了“思維樹”(Tree of Thoughts淌铐， ToT)范式肺然，它允許語言模型在thought上搜索多種推理路徑。ToT將任何問題框定為在一棵樹上搜索腿准，其中每個節(jié)點是一個狀態(tài) $s=[x,z_{1\cdots i}]$ 际起，表示到目前為止的帶有輸入和thought序列的部分解決方案拾碌。ToT的一個具體實例需要回答四個問題:
①如何將中間過程分解(decompose)為thought步驟；
②如何從每個狀態(tài)生成(generate)潛在的思維街望；
③如何啟發(fā)式地評估(evaluate)狀態(tài)校翔；
④使用什么搜索(search)算法。

Thought decomposition

CoT在沒有顯式分解的情況下連貫地對thought進(jìn)行采樣灾前，而ToT利用問題的屬性來設(shè)計和分解中間thought步驟防症。如下表所示，根據(jù)不同的問題哎甲，一個thought可以是幾個詞(填字游戲)蔫敲，一個方程(24點游戲)，或是一個完整的寫作計劃段落(創(chuàng)意寫作)炭玫。通常來說奈嘿，一個思維應(yīng)該足夠“小”，以便語言模型可以生成有前景且多樣化的樣本(例如生成一整本書通常太“大”而無法連貫)吞加，但也應(yīng)該足夠“大”裙犹，以便語言模型可以評估它對解決問題的前景(例如生成一個token通常太“小”而無法進(jìn)行評估)。

任務(wù)

Thought generator $G(p_{\theta },s,k)$

給定一個樹狀態(tài) $s=[x,z_{1\cdots i}]$ 榴鼎，我們考慮兩種生成下一個thought步驟的 $k$ 個候選的策略:
①從CoT提示中采樣(Sample)獨立同分布的多個thought(比如創(chuàng)意寫作任務(wù)伯诬，見下圖4): $z^{(j)}\sim p_{\theta }^{CoT}(z_{i+1}|s)=p_{\theta }^{CoT}(z_{i+1}|x,z_{1\cdots i})(j=1\cdots k)$ 。當(dāng)思維空間足夠豐富時(例如每個思維是一個段落)巫财，獨立同分布的采樣可以帶來多樣性盗似，這種方法效果更好。
②使用“propose prompt”來對可能的thought提出建議(Propose)(比如24點游戲平项，見下圖2赫舒；填字游戲，見下圖6): $[z^{(1)},\cdots ,z^{(k)}]\sim p_{\theta }^{propose}(z_{i+1}^{(1\cdots k)}|s)$ 闽瓢。當(dāng)思維空間更受約束時(例如每個思維只是一個詞或一行)接癌，在同一上下文提出不同的thought可以避免重復(fù)。

State evaluator $V(p_{\theta },S)$

給定最新狀態(tài)的集合扣讼，state evaluator評估它們對于解決當(dāng)前問題的價值缺猛，也就是作為搜索算法的啟發(fā)式標(biāo)準(zhǔn)來確定對哪些狀態(tài)保持搜索以及搜索順序。雖然啟發(fā)式方法是解決搜索問題的標(biāo)準(zhǔn)方法椭符，但它們通常要么是編程實現(xiàn)的(例如DeepBlue)荔燎，要么是學(xué)習(xí)得到的(例如AlphaGo)。我們提出了第三種選擇销钝，即使用語言模型來深思熟慮地推理狀態(tài)有咨。在適用的情況下，這樣的深思熟慮型啟發(fā)式方法可以比編程規(guī)則更靈活蒸健，也比學(xué)習(xí)得到的模型采樣更高效座享。類似于thought generator 婉商，我們考慮獨立或一起評估狀態(tài)的兩種策略:
①獨立評分(Value)每個狀態(tài): $V(p_{\theta },S)(s)\sim p_{\theta }^{value}(v|s)\; \forall s\in S$ ，這里使用一個 value prompt通過對狀態(tài) $s$ 進(jìn)行推理來生成一個標(biāo)量值 $v$ (例如1-10)或一個分類結(jié)果(例如sure/likely/impossible)渣叛，這些可以啟發(fā)式地轉(zhuǎn)化為一個值丈秩。這種評估推理的基礎(chǔ)在不同問題和thought步驟中有所不同。在本文實驗中淳衙，我們通過幾步前瞻模擬(例如快速確認(rèn)5癣籽，5，14可以通過5 + 5 + 14達(dá)到24滤祖，或“hot_l”可以通過在“_”中填入“e”得到“inn”)以及常識(例如1 2 3太小而無法達(dá)到24，或沒有詞可以以“tzxc”開頭)來評估當(dāng)前狀態(tài)瓶籽。前者可能推進(jìn)“好”狀態(tài)匠童，而后者可以幫助消除“壞”狀態(tài)。這樣的評估不需要完美塑顺，只需要近似即可汤求。
②跨狀態(tài)投票(Vote): $V(p_{\theta },S)(s)=\mathbb{1}[s=s^{*}]$ ，其中一個“好”狀態(tài) $s^{*}\sim p_{\theta }^{vote}(s^{*}|S)$ 是通過在vote prompt中比較 $S$ 中的不同狀態(tài)進(jìn)行投票產(chǎn)生的严拒。當(dāng)問題的成敗很難直接評估時(例如段落的連貫性)扬绪，比較不同的部分解并投票給最有前景的一個是很自然的做法。這在思想上與““step-wise”自洽策略類似裤唠，即將“搜索哪個狀態(tài)”轉(zhuǎn)換為多項選擇QA挤牛，并使用語言模型樣本對其進(jìn)行投票。
對于兩種策略种蘸，我們可以多次提示語言模型來聚合價值或投票結(jié)果墓赴，以時間/資源/成本換取更可信/健壯的啟發(fā)式結(jié)果。

Search algorithm

最后航瞭，在ToT框架內(nèi)诫硕，可以根據(jù)樹的結(jié)構(gòu)結(jié)合不同的搜索算法。我們探索了兩個相對簡單的搜索算法:
①廣度優(yōu)先搜索(BFS):在每一步維護(hù) $b$ 個最有前景的狀態(tài)集合刊侯。這用于游戲24點和創(chuàng)意寫作章办，這些任務(wù)中樹的深度是有限的( $T\leq 3$ )，且初始thought步驟可以評估和修剪為一個小集合( $b\leq 5$ )滨彻。
②深度優(yōu)先搜索(DFS):先搜索最有前景的狀態(tài)藕届，直到達(dá)到最終輸出( $t> T$ )，或state evaluator認(rèn)為從當(dāng)前 $s$ 不可能解決問題( $V(p_{\theta },\left \{s\right \})(s)\leq v_{th}$ 疮绷，其中 $v_{th}$ 是一個閾值)翰舌。在后一種情況下，剪枝 $s$ 的子樹以換取利用率冬骚。在以上兩種情況下椅贱，DFS回溯到 $s$ 的父狀態(tài)以繼續(xù)搜索懂算。

搜索算法

概念上，作為利用語言模型進(jìn)行通用問題求解的方法庇麦，ToT具有幾個優(yōu)勢:
①通用性计技。IO、CoT山橄、CoT-SC和self-refinement都可以看作是ToT的特例(即有限深度和寬度的樹垮媒，如前圖1所示)。
②模塊化航棱∷停基礎(chǔ)語言模型以及thought分解、生成饮醇、評估和搜索過程都可以獨立變化它抱。
③適應(yīng)性∑蛹瑁可以適應(yīng)不同的問題特性观蓄、語言模型能力和資源約束。
④方便性祠墅。不需要額外訓(xùn)練侮穿，僅需要一個預(yù)訓(xùn)練語言模型即可。

四毁嗦、實驗

24點游戲

實驗

創(chuàng)意寫作

實驗

填字游戲

實驗

最后編輯于：2023.07.22 18:41:06

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末亲茅，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子金矛，更是在濱河造成了極大的恐慌芯急，老刑警劉巖，帶你破解...
沈念sama閱讀 218,682評論 6贊 507
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件驶俊，死亡現(xiàn)場離奇詭異娶耍，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)饼酿，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,277評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門榕酒，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人故俐，你說我怎么就攤上這事想鹰。” “怎么了药版？”我有些...
開封第一講書人閱讀 165,083評論 0贊 355
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵辑舷，是天一觀的道長。經(jīng)常有香客問我槽片，道長何缓，這世上最難降的妖魔是什么肢础？我笑而不...
開封第一講書人閱讀 58,763評論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮碌廓，結(jié)果婚禮上传轰，老公的妹妹穿的比我還像新娘。我一直安慰自己谷婆，他們只是感情好慨蛙，可當(dāng)我...
茶點故事閱讀 67,785評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著纪挎，像睡著了一般期贫。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上异袄，一...
開封第一講書人閱讀 51,624評論 1贊 305
城市分裂傳說
那天撮竿，我揣著相機(jī)與錄音摊求，去河邊找鬼唾那。笑死瞳购，一個胖子當(dāng)著我的面吹牛垢揩，可吹牛的內(nèi)容都是我干的玖绿。我是一名探鬼主播，決...
沈念sama閱讀 40,358評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼叁巨，長吁一口氣：“原來是場噩夢啊……” “哼斑匪！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起锋勺，我...
開封第一講書人閱讀 39,261評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤蚀瘸，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后庶橱，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體贮勃，經(jīng)...
沈念sama閱讀 45,722評論 1贊 315
?護(hù)林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,900評論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年苏章，在試婚紗的時候發(fā)現(xiàn)自己被綠了寂嘉。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 40,030評論 1贊 350
活死人
序言：一個原本活蹦亂跳的男人離奇死亡枫绅，死狀恐怖泉孩，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情并淋，我是刑警寧澤寓搬，帶...
沈念sama閱讀 35,737評論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站县耽，受9級特大地震影響句喷，放射性物質(zhì)發(fā)生泄漏镣典。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 41,360評論 3贊 330
男人毒藥：我在死后第九天來索命
文/蒙蒙一脏嚷、第九天我趴在偏房一處隱蔽的房頂上張望骆撇。院中可真熱鬧，春花似錦父叙、人聲如沸神郊。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,941評論 0贊 22
一樁弒父案趾唱，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽涌乳。三九已至，卻和暖如春甜癞，著一層夾襖步出監(jiān)牢的瞬間夕晓，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 33,057評論 1贊 270
情欲美人皮
我被黑心中介騙來泰國打工悠咱，沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留蒸辆，地道東北人。一個月前我還...
沈念sama閱讀 48,237評論 3贊 371
代替公主和親
正文我出身青樓析既，卻偏偏與公主長得像躬贡，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子眼坏，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 44,976評論 2贊 355

思維樹：大模型的復(fù)雜推理技術(shù)

一勒叠、概述

二、背景

三廊谓、方法

四毁嗦、實驗

推薦閱讀更多精彩內(nèi)容