MCTS & rStar
蒙特卡洛树搜索（MCTS）
蒙特卡洛树搜索（MCTS）是一种用于解决复杂决策问题的算法，常用于游戏等领域。它的基本思想是通过构建一棵搜索树并模拟各种可能的行动来估计每个行动的价值。MCTS的过程可以分为四个主要步骤：
- 选择（Selection）：
从根节点开始，根据某种策略（如UCT）遍历子节点，直到找到一个叶节点。
UCT（Upper Confidence Bound applied on Trees）是一种平衡探索和利用的策略。
- 扩展（Expansion）：在叶节点，如果它不是终止状态，则添加一个或多个子节点，表示未来可能的行动。
- 模拟（Evaluation）：从新添加的节点中随机选择一个，进行随机模拟，直到达到终止状态，以此估计该节点的潜在价值。
- 反向传播（Backpropagation）：将模拟结果（赢、输或平局）反向传播到遍历过的节点，更新统计数据（如奖励或访问次数），以指导未来的决策。
通过这些步骤，MCTS逐步构建决策树，帮助在状态空间巨大时找到最优策略。
rStar框架
rStar框架是基于MCTS的扩展，通过多种推理动作来增强小型语言模型的解决问题的能力。rStar的包含多种推理动作：
- A1：提出一步思考：基于之前的步骤生成下一步推理。
- A2：提出剩余思考步骤：一次性生成所有剩余的推理步骤。
- A3：生成下一个子问题和答案：将主问题分解为一系列子问题，逐一解决。
- A4：重新回答子问题：重新回答之前生成的子问题，提高准确性。
- A5：重述问题/子问题：重述问题以澄清条件，减少误解。
这些动作使rStar能够动态选择推理路径，增强MCTS的探索能力。
RARE方法
图片
推理过程：该过程结合了生成和事实性评分。(1)检索增强生成器使用蒙特卡洛树搜索(MCTS)产生多个候选推理轨迹；(2)检索增强事实性评分器评估每个推理轨迹的事实准确性；(3)选择事实性得分最高的轨迹作为最终答案。
通过检索增强生成器和RAFS两个阶段，RARE系统地将基于检索的证据整合到推理过程中，优化了推理的连贯性和事实准确性。这种方法使RARE非常适合于常识和推理等知识密集型任务。
1.检索增强生成器
这一阶段基于MCTS（蒙特卡洛树搜索）的自生成器，引入了两个新的检索增强动作，动态获取相关外部信息。这些动作通过将上下文化知识整合到中间推理步骤中，提高了候选推理轨迹的相关性和准确性，特别是对于复杂问题。
为了通过外部知识增强推理过程，引入了两个新动作到检索增强生成器中：
- A6：搜索查询生成与信息检索
图片
该动作提示LLM根据初始问题构建搜索查询并执行信息检索。检索到的文档提供了额外的上下文，丰富了推理轨迹，支持生成器形成更全面、更具上下文相关性的最终答案。
- A7：子问题检索与重答
图片
该动作通过动作A3生成的子问题进行细化。对于每个子问题，生成器检索特定的相关信息并使用它来重新回答子问题。这种方法提高了中间推理步骤的准确性，从而增强了整个推理轨迹的连贯性和事实可靠性。
通过这些检索增强动作，生成器可以探索更广泛的解决方案空间，导致逻辑连贯且富含外部信息的推理路径。
2. 检索增强事实性评分器（RAFS）
这一阶段用检索增强事实性评分器替换了rStar中的鉴别器，评估每个候选轨迹的事实可靠性。评分器验证中间推理步骤与检索证据的一致性，分配一个反映轨迹与外部知识一致程度的事实性评分。选择事实性评分最高的轨迹作为最终答案，优先考虑最具事实支持的推理路径。这种选择确保了推理的连贯性和事实对齐，增强了响应的可信度。
RARE引入了检索增强事实性评分器（RAFS）。RAFS通过用LLaMA 3.1替换GPT-3.5-turbo，并用包含一般领域知识（Wikipedia）和医学领域资源（PubMed、StatPearls和医学教科书）的语料库索引检索系统替换Google Search，从而适应特定领域的需求。为了评估生成推理路径的事实准确性，RAFS在四个系统性步骤中评估每个候选轨迹，如下图。
图片
- 分割成语句每个推理轨迹被分割成单独的语句。这种分段使得RAFS能够独立验证离散推理步骤的事实准确性，增强了整体评估的可靠性。
- 生成检索查询对于每个语句，RAFS使用LLM生成多个检索查询，旨在检索与上下文相关的证据。这些查询针对可以支持或反驳每个语句内容的信息，确保全面的事实验证。
- 检索信息检索系统收集与每个生成的查询相对应的文档或信息。这些证据为评估每个推理步骤与外部来源的一致性提供了事实基础。
- 使用检索信息进行评分每个语句与检索到的证据进行比较，并标记为“支持”或“不支持”（如上图所示，RAFS为每个语句输出一个事实性得分以及“支持”或“不支持”的标签。），基于与信息的对齐情况。推理路径的整体事实性得分计算为支持语句的比例，指示轨迹的事实可靠性。这种评分有助于从多个候选者中选择最可靠的推理路径，使RARE能够优先考虑与经过验证的外部知识紧密对齐的响应。
参考文献
RARE: Retrieval-Augmented Reasoning Enhancement for Large Language Models，https://arxiv.org/pdf/2412.02830v3