使用MCTS顯著提升LLM在復(fù)雜任務(wù)的推理能力 精華
一、概述
?Title:Reasoning with Language Model is Planning with World Model
?URL:?? https://arxiv.org/abs/2305.14992??
?Code：?? https://github.com/maitrix-org/llm-reasoners??
?Demo:?? https://github.com/maitrix-org/llm-reasoners/blob/main/demo.ipynb??
1 Motivation
? 盡管COT表現(xiàn)不錯，但是當前LLM在生成plan、復(fù)雜數(shù)學(xué)推理、邏輯推理時仍然表現(xiàn)不夠好。
?LLMs缺乏內(nèi)部“世界模型”來預(yù)測世界狀態(tài)（例如環(huán)境狀態(tài)、中間變量值）并模擬行動的長期結(jié)果。
? LLM缺乏類似于人腦的深思熟慮的規(guī)劃能力。具體來說，LLMs 缺乏以下能力：
探索更多推理路徑：人類在解決問題時，會考慮多種可能的方案，并評估每種方案的優(yōu)缺點。而 LLMs 通常只會按照一種固定的推理路徑進行，缺乏靈活性和多樣性。
預(yù)測未來狀態(tài)和獎勵：人類在規(guī)劃時，會預(yù)測每個行動可能導(dǎo)致的結(jié)果，并根據(jù)結(jié)果調(diào)整自己的計劃。而 LLMs 無法預(yù)測未來狀態(tài)，因此無法進行有效的規(guī)劃。
迭代改進現(xiàn)有推理步驟：人類在規(guī)劃過程中，會根據(jù)反饋不斷調(diào)整自己的計劃，使其更加完善。而 LLMs 通常只會按照既定的計劃進行，缺乏自我反思和改進的能力。
2 Methods
RAP框架通過以下幾個關(guān)鍵步驟來克服這些限制：
- 將LLM用作世界模型：提供未來state預(yù)測息，幫助后面做action的決策。
- 采用基于蒙特卡洛樹搜索（Monte Carlo Tree Search, MCTS）規(guī)劃算法進行探索，高效找出reward最高的路徑。
- 在推理過程中，action執(zhí)行agent在世界模型agent的指導(dǎo)和reward獎勵下逐步構(gòu)建推理樹，并有效地找到高回報的推理路徑，同時在探索與利用之間保持適當?shù)钠胶?/strong>。
1）關(guān)鍵組成
本文文通過提出一個新的框架Reasoning via Planning (RAP)來解決大型語言模型（LLMs）在復(fù)雜推理任務(wù)中遇到的挑戰(zhàn), 關(guān)鍵組成部分解釋如下：
- 基于LLM構(gòu)建世界模型：通過適當?shù)膒rompt，基于LLM構(gòu)建世界模型，預(yù)測在給定當前狀態(tài)的情況下，應(yīng)用某個動作后下一個狀態(tài)的可能性。
- 根據(jù)不同的任務(wù)設(shè)置不同的reward：定義一個獎勵函數(shù)來評估每個推理步驟的可行性和可取性。獎勵函數(shù)可以根據(jù)不同任務(wù)的需求進行定制，包括動作的似然性、狀態(tài)的置信度、自我評估以及特定任務(wù)的啟發(fā)式方法。
- 引入Plan算法進行推理：MCTS通過迭代地構(gòu)建推理樹，有效地在探索（未訪問的推理路徑）和利用（已識別的最佳推理步驟）之間保持平衡。
- 構(gòu)建推理路徑的空間：在推理過程中，LLM（作為agent）根據(jù)世界模型的預(yù)測和reward模型的獎勵函數(shù)的指導(dǎo)，通過selection，expand，simulation，back-propagation逐步構(gòu)建一個推理樹。
- 結(jié)果聚合（RAP-Aggregation）：對于只需要最終答案的問題，RAP可以產(chǎn)生多個推理路徑和答案，這些結(jié)果可以通過聚合方法結(jié)合起來，以進一步提高推理性能。
2）基于世界模型預(yù)測未來狀態(tài)，提升LLM的planning能力能力
Language Model as World Model：RAP 框架將 LLM 重新利用為世界模型，使其能夠模擬未來狀態(tài)并指導(dǎo)規(guī)劃算法，從而實現(xiàn)更類似于人類深思熟慮的推理。即f(current state + action) -> next state of the reasoning。
2.1 如何將 LLM 作為世界模型：
- 定義狀態(tài)和動作：根據(jù)不同的推理任務(wù)，定義狀態(tài)和動作的具體含義。例如，在積木世界中，狀態(tài)是積木的配置，動作是移動積木；在數(shù)學(xué)問題中，狀態(tài)是變量的值，動作是提出子問題。
- 構(gòu)建馬爾可夫決策過程 (MDP)：將推理過程視為一個 MDP，其中 LLM 作為智能體，根據(jù)當前狀態(tài)生成動作空間，并使用 LLM 作為世界模型預(yù)測執(zhí)行動作后的下一個狀態(tài)。
- 模擬未來狀態(tài)：通過 LLM 作為世界模型預(yù)測未來狀態(tài)，LLM 作為智能體可以在腦海中模擬執(zhí)行不同動作后的結(jié)果，類似于人類的規(guī)劃過程。
2.2 使用世界模型的優(yōu)勢：
? LLM 能夠更好地理解推理過程中的狀態(tài)變化，從而進行更準確、更連貫的推理。
? 有了世界模型，LLM 就可以使用各種規(guī)劃算法來探索推理空間，例如蒙特卡洛樹搜索 (MCTS)，從而找到更優(yōu)的推理路徑。
2.3 CoT 和 RAP 的主要區(qū)別：
?狀態(tài)建模：CoT 中只有動作序列，沒有對世界狀態(tài)的建模。而 RAP 引入了世界模型，能夠預(yù)測未來狀態(tài)，使推理過程更加全面和可靠。
?規(guī)劃能力：CoT 缺乏規(guī)劃能力，只能按照固定的推理路徑進行。而 RAP 引入了規(guī)劃算法 (如 MCTS)，能夠探索多種可能的推理路徑，并選擇最優(yōu)的路徑。
?推理過程：CoT 的推理過程是自回歸的，每一步推理都依賴于前一步的輸出。而RAP 的推理過程是迭代的，LLM 可以根據(jù)反饋不斷調(diào)整推理步驟。
3 如何設(shè)計Reward Model？
3.1 獎勵函數(shù)的核心目標：
?評估每個推理步驟的可行性和可取性：判斷每個步驟是否符合規(guī)則，以及是否有助于達到最終目標。
?引導(dǎo) LLM 沿著最優(yōu)路徑進行推理：通過獎勵機制，鼓勵 LLM 選擇更有利于達成目標的推理步驟。
3.2 有哪些常見的reward獎勵函數(shù)方法：
類別 | 描述 | 原理 | 作用 | 應(yīng)用場景 |
動作概率 (Action Likelihood) | 采用當前action的概率作為reward，即采用log probability of the action作為reward。 | 評估 LLM 在當前狀態(tài)下生成特定動作的概率。 | 反映 LLM 對特定動作的偏好和置信度。 | 適用于需要判斷動作合理性的任務(wù)，例如積木世界中的移動積木。 |
狀態(tài)置信度 (State Confidence) | 狀態(tài)置信度通過采樣 LLM 的預(yù)測結(jié)果并計算最常見結(jié)果的比例來評估 LLM 對預(yù)測狀態(tài)的可靠性。 | 評估 LLM 對預(yù)測狀態(tài) (例如答案) 的置信度。 | 反映 LLM 對預(yù)測結(jié)果的可靠性程度。 | 適用于需要評估預(yù)測結(jié)果質(zhì)量的任務(wù)，例如數(shù)學(xué)問題中的答案。 |
自我評估 (Self-evaluation) | criticize itself，例如question“Is this reasoning step correct ?” 或者，利用next-word yes的概率作為reward。 | 讓 LLM 對自身推理步驟的正確性進行評估。 | 反映 LLM 對自身推理能力的自我認知。 | 適用于 LLM 可以判斷推理步驟正確性的任務(wù)，例如數(shù)學(xué)問題中判斷計算或邏輯錯誤。 |
特定任務(wù)啟發(fā)式 (Task-specific Heuristics) | 方便引入其他插件，來啟發(fā)式引導(dǎo)。 | 根據(jù)特定任務(wù)的特性設(shè)計啟發(fā)式函數(shù)，評估推理步驟的質(zhì)量。 | 利用領(lǐng)域知識，指導(dǎo) LLM 進行更有效的推理。 | 適用于需要利用領(lǐng)域知識的任務(wù)，例如積木世界中計算預(yù)測狀態(tài)與目標狀態(tài)之間的距離。 |
4 如何利用MCTS進行迭代
4.1 MCTS 的四個階段：
階段 | 描述 |
選擇（Selection） | 從根節(jié)點開始，遞歸選擇最優(yōu)的子節(jié)點，直到達到一個葉子結(jié)點。此過程基于一定的選擇策略，例如UCB (Upper Confidence Bound)。 |
擴展（Expansion） | 當達到葉節(jié)點時，根據(jù)問題的定義，擴展樹以添加一個或多個子節(jié)點。這模擬了在現(xiàn)實中采取一個動作并觀察新狀態(tài)的過程。 |
模擬（Simulation） | 從擴展的節(jié)點開始，執(zhí)行模擬來估計這個節(jié)點的價值。模擬是通過一種模型或隨機方法生成的，模擬直到達到某個終止條件。 |
回溯（Backpropagation） | 根據(jù)模擬的結(jié)果，將回報值（reward）傳播回來更新經(jīng)過的所有節(jié)點的統(tǒng)計信息，如訪問次數(shù)和累計獎勵。 |
4.2 如何選擇最終推理路徑？
算法終止后，需要從構(gòu)建的搜索樹中選擇一條推理軌跡進行評估。這里有幾種不同的選擇策略：
- 基于 Q 值的選擇：從根節(jié)點開始，迭代地選擇具有最高Q 值（即狀態(tài)-動作對的預(yù)期回報）的動作，直到達到一個終端節(jié)點（葉子節(jié)點）。這種方法依賴于算法在迭代過程中積累的值。
- 基于獎勵的選擇：直接選擇在迭代過程中產(chǎn)生最高總獎勵的路徑。這種方法考慮了整個路徑的累積獎勵，而不是單個步驟的 Q 值。
- 最頻繁訪問的葉子節(jié)點：選擇訪問次數(shù)最多的葉子節(jié)點，以及從根節(jié)點到該葉子節(jié)點的路徑。這種方法假設(shè)最頻繁訪問的路徑可能是最優(yōu)的。
實際觀察：在實際應(yīng)用中，作者觀察到第二種策略（基于獎勵的選擇）通常會產(chǎn)生最好的結(jié)果。這可能是因為它考慮了整個路徑的累積獎勵，而不是僅僅依賴于單個步驟的 Q 值，從而能夠更好地捕捉到長遠的推理效果。
5 Conclusion
? RAP在生成計劃、數(shù)學(xué)推理和邏輯推理任務(wù)上表現(xiàn)出色，超越了包括CoT和least-to-most prompting在內(nèi)的多種強基線。
? RAP在使用LLaMA-33B模型時超過了使用GPT-4的CoT方法，在plan生成中提升了33%。
二、詳細內(nèi)容
1 實驗設(shè)計
Benchmark： 采用了4個不同的任務(wù)來證明本方法的有效性：
- Plan生成（Plan Generation）：使用Blocksworld基準測試，要求智能體將塊按特定順序堆疊。定義狀態(tài)為塊的當前方向，動作為移動塊的指令。使用兩種獎勵：動作的似然性和特定任務(wù)啟發(fā)式獎勵。與Chain-of-Thought (CoT)和其他基線方法進行比較。
- 數(shù)學(xué)推理（Math Reasoning）：在GSM8K數(shù)據(jù)集上進行測試，該數(shù)據(jù)集包含小學(xué)數(shù)學(xué)文字問題。將問題分解為一系列較小的子問題。**定義狀態(tài)為中間變量的值，動作為提出關(guān)于未知中間變量的增量子問題。**結(jié)合自我評估獎勵和狀態(tài)置信度獎勵。與CoT、Least-to-Most prompting等變體進行比較。
- 邏輯推理（Logical Reasoning）：在PrOntoQA數(shù)據(jù)集上進行測試，該數(shù)據(jù)集包含一組事實和邏輯規(guī)則，要求模型驗證假設(shè)事實的真假。定義狀態(tài)為當前關(guān)注的fact，動作為從fact集中選擇規(guī)則。使用自我評估獎勵，并基于未來步驟的平均獎勵更新Q函數(shù)。與CoT基線方法進行比較，評估最終答案的預(yù)測準確性和完整證明的準確性。
額外實驗：
?復(fù)雜問題的分析：在完整的Blocksworld數(shù)據(jù)集上使用更強大的LLM（Llama-2 70B）進行實驗，以進一步研究RAP是否能幫助更強的LLM解決更復(fù)雜的問題。
?獎勵選擇的分析：對不同獎勵選擇對LLM推理性能的影響進行了綜合實驗，包括計劃生成和數(shù)學(xué)推理任務(wù)。
?適應(yīng)性提示（Adaptive Prompting）：為了解決演示案例和測試案例之間難度分布差異的問題，提出了一種適應(yīng)性提示技術(shù)，通過預(yù)計算演示案例的中間狀態(tài)并截斷搜索樹中的路徑來提高性能。
2 Blocksword場景超過GPT4+COT的效果
說明：
?任務(wù)：通過一系列的操作，將積木塊從一種特定的初始配置移動到另一種目標配置。
?RAP(10) 和 RAP(20)：這指的是使用 RAP 方法時，迭代次數(shù)分別設(shè)置為 10 和 20 的實驗設(shè)置。
?“pass@10”：表示對于每個測試案例，算法采樣了 10 個計劃。如果一個測試案例中至少有一個計劃是正確的，那么這個測試案例就被認為是解決了的。這種方法可以評估算法在多次嘗試中找到至少一個有效解決方案的能力。
結(jié)論1： 使用 LLaMA-33B（一個大型語言模型）的 CoT 方法只能為少數(shù)幾個兩步的問題生成成功的計劃，而在更難的問題上完全失敗。這表明 CoT 方法在處理簡單問題時表現(xiàn)尚可，但在問題復(fù)雜度增加時，其性能顯著下降。
結(jié)論2: RAP 方法在性能上顯著優(yōu)于 CoT，幾乎解決了所有四步以內(nèi)的難題，并且解決了一部分六步問題，平均成功率達到 64%。這說明 RAP 方法在處理更復(fù)雜問題時的有效性。
結(jié)論3: 六步問題的搜索空間可以達到 ，而RAP算法在 20 次迭代內(nèi)能夠以 42% 的概率找到成功的計劃。這強調(diào)了 RAP 方法在處理具有大規(guī)模搜索空間問題時的效率。
結(jié)論4: RAP框架使得 LLaMA-33B 在性能上超過了 GPT-4，提升了33%，表明 RAP 方法能夠顯著提升語言模型在復(fù)雜推理任務(wù)上的性能。
3 數(shù)學(xué)推理任務(wù)上表現(xiàn)也非常好
說明：
?任務(wù)：例如GSM8k的數(shù)學(xué)任務(wù)，包括一個描述和一個final question，需要進行multi-step數(shù)學(xué)計算，需要將final question拆解成一系列小的字問題來解決。
?狀態(tài)定義：在這個框架中，"狀態(tài)state"被定義為中間變量的值。中間變量是在解決問題過程中產(chǎn)生的，它們幫助模型理解問題的當前狀態(tài)。
?動作定義："動作action"是指提出一個關(guān)于未知中間變量的增量子問題。這個動作是為了獲取關(guān)于問題更多的信息。
?世界模型響應(yīng)：世界模型（可以理解為問題的背景知識庫）會根據(jù)當前的中間變量值和問題描述來回答提出的子問題?；卮鸬慕Y(jié)果是將新的中間變量值加入到下一個狀態(tài)中，從而更新模型對問題的理解。
?獎勵函數(shù)：獎勵函數(shù)是由兩個部分組合而成的：LLM對自己提出子問題有用性的自我評估（rt,1）和模型對當前狀態(tài)置信度（rt,2）的加權(quán)幾何平均。這個加權(quán)幾何平均表示為 rt = rα ? r1?α，其中 α 是權(quán)重系數(shù)。
?獎勵的目的：這個獎勵函數(shù)的設(shè)計目的是鼓勵模型提出更加相關(guān)和有用的子問題。通過這種方式，模型可以更有效地解決問題，因為它會被引導(dǎo)去關(guān)注那些能夠顯著推進問題解決進程的信息。
? 其他：RAP（aggr）取多條采樣路徑的結(jié)果。
4 邏輯推理任務(wù)上表現(xiàn)也比較好
image-20241104234512575
說明：
- ?任務(wù)設(shè)置：邏輯推理任務(wù)（例如 PrOn-toQA）通常提供一組事實和邏輯規(guī)則。模型的任務(wù)是使用這些邏輯規(guī)則來驗證給定的假設(shè)事實是否為真或假。這些任務(wù)不僅要求模型提供正確的最終答案（真或假），還要求模型提供一個詳細的證明來展示結(jié)果。
- ?狀態(tài)定義：在這個框架中，"狀態(tài)"被定義為模型當前關(guān)注的事實，這類似于人類在推理時的工作記憶（Baddeley, 1992）。工作記憶是指在進行復(fù)雜認知任務(wù)時，暫時存儲和操作信息的心理能力。
- ?動作定義："動作"被定義為從事實集中選擇一個規(guī)則。這個動作是為了應(yīng)用邏輯規(guī)則來進行推理。
- ?世界模型：世界模型執(zhí)行一個單跳推理步驟，使用選定的規(guī)則和當前的事實來生成一個新的事實，這個新事實成為下一個狀態(tài)。
- ?獎勵計算：獎勵是通過自我評估來計算的（參見 Section 3.2）。具體來說，通過向 LLM 提供一些帶有標簽的示例，幫助它更好地理解推理步驟的質(zhì)量。自我評估可以是模型對推理步驟有用性的評價。
- ?Q 函數(shù)更新：使用未來步驟的平均獎勵來更新 Q 函數(shù)，這與 GSM8k 中的方程（2）相同。Q 函數(shù)是強化學(xué)習(xí)中的一個概念，用于評估在特定狀態(tài)下采取特定動作的預(yù)期回報。
三、總結(jié)
?結(jié)論1:利用LLM作為世界模型和推理agent，可以顯著提升其推理和規(guī)劃能力，使其在多個推理任務(wù)上的表現(xiàn)優(yōu)于現(xiàn)有強基線。
?結(jié)論2:引入基于蒙特卡洛樹搜索（MCTS）的規(guī)劃算法，有效平衡了推理過程中的探索和利用，使得LLM在解決復(fù)雜推理問題時能夠高效獲取高獎勵的推理路徑。
本文轉(zhuǎn)載自 ??NLP PaperWeekly??，作者： NLP PaperWeekly
