The Monte Carlo Tree Search (MCTS) algorithm has been utilized to assist large language models (LLMs) in generating higher-quality content, particularly in the domain of code generation. However, MCTS requires enormous amounts of computation time to select the best option from the lists of outcomes. The main reason is that the vast number of potential token combinations produced by the LLMs makes the search space extremely large, thus leading to extremely low search efficiency. To address this mentioned challenge, in this paper, we propose Dynamic Adjusted Monte-Carlo Tree Search (DA-MCTS), a novel algorithm that dynamically decides the number of child nodes at each node based on the token probability and depth of the search tree. Specifically, unlike existing methods that generate a fixed number of nodes during the expansion phase of the MCTS algorithm, our DA-MCTS only expands nodes where the token probability exceeds a threshold. This threshold varies according to the content and length of the currently generated code. We empirically evaluate our method with several large language models as backbones on coding benchmarks, showing that it can potentially save up to 30.37% of computational time compared to the baseline.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Learning to Expand: Dynamic Adaptive Monte-Carlo Tree Search for Code Generation

  • Feng Ji

摘要

The Monte Carlo Tree Search (MCTS) algorithm has been utilized to assist large language models (LLMs) in generating higher-quality content, particularly in the domain of code generation. However, MCTS requires enormous amounts of computation time to select the best option from the lists of outcomes. The main reason is that the vast number of potential token combinations produced by the LLMs makes the search space extremely large, thus leading to extremely low search efficiency. To address this mentioned challenge, in this paper, we propose Dynamic Adjusted Monte-Carlo Tree Search (DA-MCTS), a novel algorithm that dynamically decides the number of child nodes at each node based on the token probability and depth of the search tree. Specifically, unlike existing methods that generate a fixed number of nodes during the expansion phase of the MCTS algorithm, our DA-MCTS only expands nodes where the token probability exceeds a threshold. This threshold varies according to the content and length of the currently generated code. We empirically evaluate our method with several large language models as backbones on coding benchmarks, showing that it can potentially save up to 30.37% of computational time compared to the baseline.