MCTS & rStar

蒙特卡洛樹搜索（MCTS）

蒙特卡洛樹搜索（MCTS）是一種用于解決復(fù)雜決策問題的算法，常用于游戲等領(lǐng)域。它的基本思想是通過構(gòu)建一棵搜索樹并模擬各種可能的行動來估計每個行動的價值。MCTS的過程可以分為四個主要步驟：

• 選擇（Selection）：

從根節(jié)點開始，根據(jù)某種策略（如UCT）遍歷子節(jié)點，直到找到一個葉節(jié)點。

UCT（Upper Confidence Bound applied on Trees）是一種平衡探索和利用的策略。

• 擴展（Expansion）：在葉節(jié)點，如果它不是終止?fàn)顟B(tài)，則添加一個或多個子節(jié)點，表示未來可能的行動。
• 模擬（Evaluation）：從新添加的節(jié)點中隨機選擇一個，進行隨機模擬，直到達到終止?fàn)顟B(tài)，以此估計該節(jié)點的潛在價值。
• 反向傳播（Backpropagation）：將模擬結(jié)果（贏、輸或平局）反向傳播到遍歷過的節(jié)點，更新統(tǒng)計數(shù)據(jù)（如獎勵或訪問次數(shù)），以指導(dǎo)未來的決策。

通過這些步驟，MCTS逐步構(gòu)建決策樹，幫助在狀態(tài)空間巨大時找到最優(yōu)策略。

rStar框架

rStar框架是基于MCTS的擴展，通過多種推理動作來增強小型語言模型的解決問題的能力。rStar的包含多種推理動作：

• A1：提出一步思考：基于之前的步驟生成下一步推理。
• A2：提出剩余思考步驟：一次性生成所有剩余的推理步驟。
• A3：生成下一個子問題和答案：將主問題分解為一系列子問題，逐一解決。
• A4：重新回答子問題：重新回答之前生成的子問題，提高準(zhǔn)確性。
• A5：重述問題/子問題：重述問題以澄清條件，減少誤解。

這些動作使rStar能夠動態(tài)選擇推理路徑，增強MCTS的探索能力。

RARE方法

圖片

推理過程：該過程結(jié)合了生成和事實性評分。(1)檢索增強生成器使用蒙特卡洛樹搜索(MCTS)產(chǎn)生多個候選推理軌跡；(2)檢索增強事實性評分器評估每個推理軌跡的事實準(zhǔn)確性；(3)選擇事實性得分最高的軌跡作為最終答案。

通過檢索增強生成器和RAFS兩個階段，RARE系統(tǒng)地將基于檢索的證據(jù)整合到推理過程中，優(yōu)化了推理的連貫性和事實準(zhǔn)確性。這種方法使RARE非常適合于常識和推理等知識密集型任務(wù)。

1.檢索增強生成器

這一階段基于MCTS（蒙特卡洛樹搜索）的自生成器，引入了兩個新的檢索增強動作，動態(tài)獲取相關(guān)外部信息。這些動作通過將上下文化知識整合到中間推理步驟中，提高了候選推理軌跡的相關(guān)性和準(zhǔn)確性，特別是對于復(fù)雜問題。

為了通過外部知識增強推理過程，引入了兩個新動作到檢索增強生成器中：

• A6：搜索查詢生成與信息檢索

圖片

該動作提示LLM根據(jù)初始問題構(gòu)建搜索查詢并執(zhí)行信息檢索。檢索到的文檔提供了額外的上下文，豐富了推理軌跡，支持生成器形成更全面、更具上下文相關(guān)性的最終答案。

• A7：子問題檢索與重答

圖片

該動作通過動作A3生成的子問題進行細(xì)化。對于每個子問題，生成器檢索特定的相關(guān)信息并使用它來重新回答子問題。這種方法提高了中間推理步驟的準(zhǔn)確性，從而增強了整個推理軌跡的連貫性和事實可靠性。

通過這些檢索增強動作，生成器可以探索更廣泛的解決方案空間，導(dǎo)致邏輯連貫且富含外部信息的推理路徑。

2. 檢索增強事實性評分器（RAFS）

這一階段用檢索增強事實性評分器替換了rStar中的鑒別器，評估每個候選軌跡的事實可靠性。評分器驗證中間推理步驟與檢索證據(jù)的一致性，分配一個反映軌跡與外部知識一致程度的事實性評分。選擇事實性評分最高的軌跡作為最終答案，優(yōu)先考慮最具事實支持的推理路徑。這種選擇確保了推理的連貫性和事實對齊，增強了響應(yīng)的可信度。

RARE引入了檢索增強事實性評分器（RAFS）。RAFS通過用LLaMA 3.1替換GPT-3.5-turbo，并用包含一般領(lǐng)域知識（Wikipedia）和醫(yī)學(xué)領(lǐng)域資源（PubMed、StatPearls和醫(yī)學(xué)教科書）的語料庫索引檢索系統(tǒng)替換Google Search，從而適應(yīng)特定領(lǐng)域的需求。為了評估生成推理路徑的事實準(zhǔn)確性，RAFS在四個系統(tǒng)性步驟中評估每個候選軌跡，如下圖。

圖片

• 分割成語句
  每個推理軌跡被分割成單獨的語句。這種分段使得RAFS能夠獨立驗證離散推理步驟的事實準(zhǔn)確性，增強了整體評估的可靠性。
• 生成檢索查詢
  對于每個語句，RAFS使用LLM生成多個檢索查詢，旨在檢索與上下文相關(guān)的證據(jù)。這些查詢針對可以支持或反駁每個語句內(nèi)容的信息，確保全面的事實驗證。
• 檢索信息
  檢索系統(tǒng)收集與每個生成的查詢相對應(yīng)的文檔或信息。這些證據(jù)為評估每個推理步驟與外部來源的一致性提供了事實基礎(chǔ)。
• 使用檢索信息進行評分
  每個語句與檢索到的證據(jù)進行比較，并標(biāo)記為“支持”或“不支持”（如上圖所示，RAFS為每個語句輸出一個事實性得分以及“支持”或“不支持”的標(biāo)簽。），基于與信息的對齊情況。推理路徑的整體事實性得分計算為支持語句的比例，指示軌跡的事實可靠性。這種評分有助于從多個候選者中選擇最可靠的推理路徑，使RARE能夠優(yōu)先考慮與經(jīng)過驗證的外部知識緊密對齊的響應(yīng)。

參考文獻

RARE: Retrieval-Augmented Reasoning Enhancement for Large Language Models，https://arxiv.org/pdf/2412.02830v3