Wider or Deeper? Scaling LLM Inference-Time Compute with Adaptive Branching Tree Search

📄 arXiv: 2503.04412v5 📥 PDF

作者: Yuichi Inoue, Kou Misaki, Yuki Imajuku, So Kuroki, Taishi Nakamura, Takuya Akiba

分类: cs.AI

发布日期: 2025-03-06 (更新: 2025-11-07)

备注: Accepted as a spotlight at NeurIPS 2025

🔗 代码/项目: GITHUB

💡 一句话要点

提出自适应分支蒙特卡洛树搜索(AB-MCTS)，提升LLM推理时计算效率与复杂任务性能。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大型语言模型 推理时计算 蒙特卡洛树搜索 自适应分支 代码生成

📋 核心要点

  1. 现有方法如重复抽样虽然能提升LLM推理能力，但缺乏利用外部反馈信号进行优化的机制。
  2. AB-MCTS通过在搜索树的每个节点动态决定“扩展宽度”或“加深深度”，实现多轮探索和利用。
  3. 实验表明，AB-MCTS在编码和工程任务上优于重复抽样和标准MCTS，验证了其有效性。

📝 摘要（中文）

本文提出了一种新颖的推理时框架——自适应分支蒙特卡洛树搜索(AB-MCTS)，旨在通过有原则的多轮探索和利用来推广重复抽样，从而提升大型语言模型(LLM)的推理能力。与重复抽样不同，AB-MCTS能够利用外部反馈信号进行优化。在搜索树的每个节点，AB-MCTS动态决定是“扩展宽度”以生成新的候选响应，还是“加深深度”以基于外部反馈信号重新访问现有响应。我们在复杂的编码和工程任务上，使用前沿模型评估了该方法。实验结果表明，AB-MCTS始终优于重复抽样和标准MCTS，强调了结合LLM的响应多样性和多轮解决方案优化对于有效推理时扩展的重要性。代码已在https://github.com/SakanaAI/treequest 公开。

🔬 方法详解

问题定义：论文旨在解决如何更有效地利用推理时计算资源，提升大型语言模型在复杂任务（如编码和工程问题）中的性能。现有方法，如重复抽样，虽然增加了计算量，但缺乏利用外部反馈信号进行迭代优化的机制，导致效率不高。标准蒙特卡洛树搜索(MCTS)虽然能进行探索和利用，但可能无法充分利用LLM生成多样化响应的能力。

核心思路：论文的核心思路是结合LLM生成多样化响应的能力和多轮迭代优化的思想，提出自适应分支策略。AB-MCTS在搜索树的每个节点，根据外部反馈信号动态决定是生成新的候选响应（“扩展宽度”）还是基于现有响应进行优化（“加深深度”）。这种自适应策略能够更有效地利用计算资源，提升解决方案的质量。

技术框架：AB-MCTS的整体框架是一个蒙特卡洛树搜索过程。主要包含以下几个阶段： 1. 选择(Selection)：从根节点开始，根据一定的策略（如UCT）选择一个子节点。 2. 扩展(Expansion)：如果选择的节点未被完全扩展，则根据LLM生成新的候选响应，并添加到搜索树中。 3. 模拟(Simulation)：对新生成的候选响应或已有的响应进行评估，获取外部反馈信号。 4. 反向传播(Backpropagation)：将评估结果反向传播回搜索树，更新节点的值。

关键创新：AB-MCTS的关键创新在于其自适应分支策略。传统MCTS通常采用固定的分支策略，而AB-MCTS能够根据外部反馈信号动态调整分支策略，从而更有效地利用计算资源。具体来说，AB-MCTS会根据当前节点的状态和外部反馈信号，决定是“扩展宽度”以生成新的候选响应，还是“加深深度”以基于现有响应进行优化。这种自适应性使得AB-MCTS能够更好地适应不同的任务和场景。

关键设计：AB-MCTS的关键设计包括： 1. 分支策略：AB-MCTS使用一个策略来决定是扩展宽度还是加深深度。这个策略可以基于多种因素，如当前节点的值、访问次数、以及外部反馈信号。 2. 外部反馈信号：AB-MCTS依赖于外部反馈信号来评估候选响应的质量。这些反馈信号可以是任务特定的，例如，在编码任务中，可以使用单元测试的结果作为反馈信号。 3. 探索-利用平衡：AB-MCTS需要平衡探索（生成新的候选响应）和利用（优化现有响应）之间的关系。这可以通过调整分支策略中的参数来实现。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，AB-MCTS在复杂的编码和工程任务上，显著优于重复抽样和标准MCTS。具体来说，AB-MCTS在HumanEval编码任务和工程设计任务上均取得了明显的性能提升，验证了其有效性。例如，在某些任务上，AB-MCTS的性能提升超过了10%。

🎯 应用场景

AB-MCTS具有广泛的应用前景，可应用于代码生成、机器人控制、游戏AI、药物发现等需要复杂推理和决策的任务。通过结合LLM的生成能力和外部反馈信号的优化，AB-MCTS能够提升这些任务的性能和效率，加速相关领域的发展。

📄 摘要（原文）

Recent advances demonstrate that increasing inference-time computation can significantly boost the reasoning capabilities of large language models (LLMs). Although repeated sampling (i.e., generating multiple candidate outputs) is a highly effective strategy, it does not leverage external feedback signals for refinement, which are often available in tasks like coding. In this work, we propose Adaptive Branching Monte Carlo Tree Search (AB-MCTS), a novel inference-time framework that generalizes repeated sampling with principled multi-turn exploration and exploitation. At each node in the search tree, AB-MCTS dynamically decides whether to "go wider" by expanding new candidate responses or "go deeper" by revisiting existing ones based on external feedback signals. We evaluate our method on complex coding and engineering tasks using frontier models. Empirical results show that AB-MCTS consistently outperforms both repeated sampling and standard MCTS, underscoring the importance of combining the response diversity of LLMs with multi-turn solution refinement for effective inference-time scaling. Code is available at https://github.com/SakanaAI/treequest .