Adaptive Branching MCTS
Researchers from Sakana AI introduce Adaptive Branching Monte Carlo Tree Search (AB-MCTS), a new framework that dynamically decides whether to "go wider" (explore new solutions) or "go deeper" (refine existing ones) during inference. Key ideas:
Ask this paper
Beyond Fixed-Width Search – Traditional MCTS uses a fixed branching factor, which limits its ability to explore the vast output space of LLMs. AB-MCTS introduces unbounded branching, allowing it to harness the diversity of repeated sampling while also enabling multi-turn solution refinement.
Principled Exploration-Exploitation – The decision to go wider or deeper is not based on heuristics, but on a principled Bayesian approach. The framework uses Thompson sampling to balance exploration and exploitation, ensuring that the search is both efficient and effective.
Unifying Search Directions – AB-MCTS unifies the "go wide" (repeated sampling) and "go deep" (sequential refinement) strategies into a single, coherent framework. This allows the model to dynamically adapt its search strategy to the specific demands of the task at hand.
Superior Performance on Complex Tasks – On challenging coding and engineering benchmarks, AB-MCTS outperforms both repeated sampling and standard MCTS, demonstrating the power of combining the response diversity of LLMs with multi-turn solution refinement.