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