Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training

By Xidong Feng, Ziyu Wan, Muning Wen, Ying Wen, Weinan Zhang, Jun Wang. International Conference on Machine Learning, 2023

351 citations recorded by the source corpus.

Recent works like Tree-of-Thought (ToT) and Reasoning via Planning (RAP) aim to augment the reasoning capabilities of LLMs by using tree-search algorithms to guide multi-step reasoning. These methods rely on prompting a pre-trained model to serve as a value function and focus on problems with low search depth. As a result, these methods will not work in domains where the pre-trained LLM does not have enough knowledge to serve as an effective value function or in domains that require long-horizon planning. To address these limitations, we present an AlphaZero-like tree-search learning framework for LLMs (termed TS-LLM), systematically illustrating how tree-search with a learned value function can guide LLM decoding. TS-LLM distinguishes itself in two key ways. (1) Leveraging a learned value function and AlphaZero-like algorithms, our approach can be generally adaptable to a wide range of tasks, language models of any size, and tasks of varying search depths. (2) Our approach can guide LLMs during both inference and training, iteratively improving the LLM. Empirical results across reasoning, planning, alignment, and decision-making tasks show that TS-LLM outperforms existing approaches and can handle trees with a depth of 64.

Subfields: Artificial Intelligence, Information Systems

View Paper: https://www.semanticscholar.org/paper/e8df1cf6742b50a15500b8dd3dde3942e9c91418

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

Citations in the corpus

SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-training (2025, positive): “Subsequent work (Zelikman et al., 2022; Feng et al., 2023; Tian et al., 2024; Chen et al., 2024a; Snell et al., 2024) has demonstrated that fine-tuning verifiers during inference improves model accuracy, effectively utilizing test-time computation.”
Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs (2024, neutral): “…(Lightman et al., 2024; Li et al., 2023; Khanov et al., 2024; Heineman et al., 2024; Wu et al., 2024), and structured search methods such as Tree-of-Thought, Graph-of-Thought, and Monte Carlo Tree Search (Yao et al., 2024; Besta et al., 2024; Luo et al., 2024; Tian et al., 2024; Wan et al., 2024).”
Vision-R1: Incentivizing Reasoning Capability in Multimodal Large Language Models (2025, neutral): “…such as Chain-of-Thought (CoT) prompting methods [3], plan-based methods like Tree-of-Thought and Graph-of-Thought [4, 5], process-based reward models [6– 9], Monte Carlo Tree Search (MCTS) and Beam Search [10– 12], as well as constructing complex Supervised Fine-Tuning (SFT) datasets [13, 14].”
DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning (2025, neutral): “Several prior works have explored various approaches, including process-based reward models (Lightman et al., 2023; Uesato et al., 2022; Wang et al., 2023), reinforcement learning (Kumar et al., 2024), and search algorithms such as Monte Carlo Tree Search and Beam Search (Feng et al., 2024; Trinh et”
Improve Mathematical Reasoning in Language Models by Automated Process Supervision (2024, neutral): “Recently, utilizing tree-like decoding to find the best output during the inference-time has become a hot topic to explore as well, multiple works (Feng et al., 2023, 2024; Kang et al., 2024; Ma et al., 2023; Tian et al., 2024; Zhang et al., 2024) have observed improvements in reasoning tasks.”
Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters (2024, methodology): “…targeted optimization on specific reasoning tasks by finetuning with RL [32, 35, 49, 50] enabling models to critique and revise their answers iteratively [4, 8, 23, 30]; 3) enabling LLMs to benefit from additional test-time computation by finetuning verifiers [6, 7, 10, 22, 40, 42, 45, 48].”