MASTER : A Multi-Agent System with LLM Specialized MCTS (2025)

Abstract: Large Language Models (LLM) are increasingly being explored for problem-solving tasks. However, their strategic planning capability is often viewed with skepticism. Recent studies have incorporated the Monte Carlo Tree Search (MCTS) algorithm to augment the planning capacity of LLM. Despite its potential, MCTS relies on extensive sampling simulations to approximate the true reward distribution, which leads to two primary issues. Firstly, MCTS is effective for tasks like the Game of Go, where simulation results can yield objective rewards (e.g., 1 for a win and 0 for a loss). However, for tasks such as question answering, the result of a simulation is the answer to the question, which cannot yield an objective reward without the ground truth. Secondly, obtaining statistically significant reward estimations typically requires a sample size exceeding 30 simulations, resulting in excessive token usage and time consumption. To address these challenges, we present Multi-Agent System with Tactical Execution and Reasoning using LLM Specialized MCTS (MASTER), a novel framework that coordinates agent recruitment and communication through LLM specialized MCTS. This system autonomously adjusts the number of agents based on task complexity and ensures focused communication among them. Comprehensive experiments across various tasks demonstrate the effectiveness of our proposed framework. It achieves 76% accuracy on HotpotQA and 80% on WebShop, setting new state of-the-art performance on these datasets.

## introduction llm represent a significant milestone in artificial intelligence and are increasingly employed in problem-solving tasks @xcite . however, their application to complex problems is often limited due to concerns about their planning capabilities. llm generate text based on "next token probability" conditioned on the context @xcite , but effective reasoning requires rigorous deduction rooted in the first principles of logic, grounded in data and reality @xcite . to enhance the planning capabilities of llm, recent studies have incorporated the mcts algorithm @xcite @xcite . mcts uses simulations to evaluate the long-term consequences of actions, backpropagating aggregated rewards up the tree. this allows for backtracking to previous states based on estimated future potential, striking a balance between exploitation and exploration. however, the use of mcts in existing works presents two significant challenges: to tackle the first challenge, certain approach compares the outcomes of simulations with the ground truth to derive objective rewards @xcite which is flawed because revealing the ground truth during problem-solving is inappropriate. in addressing the second challenge, they limit the number of simulations @xcite or terminate the process once a correct answer is identified @xcite . yet, this early termination approach is not feasible if the ground truth remains undisclosed. these issues highlight a critical step of mcts: simulation. due to these limitations, mcts is constrained to a narrow scope of application and is not fully compatible with llm. consequently, we propose an adaptation of mcts tailored to llm scenarios. instead of performing limited simulations with uncertain rewards, we eliminate the simulation process, relying on the llm's self-evaluation capabilities to allocate rewards. additionally, we propose several methods to enhance the objectivity of rewards: 1). an additional step is introduced for the llm to provide more context before selfevaluation; 2). the llm's confidence is incorporated as a weight for the reward to regulate its influence; 3). the backpropagation mechanism is retained, allowing for rewards updates if initially misallocated. while traditional mcts focuses resources on simulations for an approximate reflection of reality, our approach distributes resources across multiple steps to jointly ensure the accuracy and objectivity of rewards. this is why we named our project master, as it replaces simulation, the core procedure of mcts, by mastering a series of refined designs. another contribution of this paper is the introduction of a novel multi-agent system. current multiagent systems feature two prominent frameworks: the first allows agents to be independently created and to share ideas freely. while versatile, this open communication can lead to off-topic discussions due to hallucinations @xcite @xcite , diverting focus from the main task and depleting the token window length for extended conversation history. the second approach involves human-created agents, where communication is predefined. although more controlled, this approach lacks code reusability @xcite . additionally, since the procedures are established, it cannot adapt to tasks of varying difficulty. it struggles with unanticipated complex tasks on the one hand and spends unnecessary resources on easy tasks on the other. our system, master, addresses these limitations by employing llm-specialized mcts to guide the creation and interaction of agents. in this system, child agents respond to and build upon the outputs of the parent agent, making recruitment and communication more manageable and efficient. the system dynamically scales the number of agents based on task complexity, ensuring flexibility. although the agents share similar profiles, they assume different roles by taking distinct actions. unlike the nodes in lats @xcite and rap @xcite , which represent states on a reasoning tree and are closely tied to specific tasks, our agents are task-agnostic and do not require reconfiguration when the task changes. in summary, our key contributions are: ## related work many studies have been done to enhance the planning capabilities of llm. among these efforts, two primary planning approaches have emerged for agents: single-path planning and tree-based planning. in the context of multi-agent systems, current frameworks predominantly employ either predefined frameworks or open frameworks depending on their agent communication patterns. we discuss some of the relevant works in this section. ## experiment setup to demonstrate the generalizability of our framework, we conduct experiments across a diverse set of tasks, including question answering (hotpotqa), decision making (webshop), and coding (mbpp). these datasets are widely recognized benchmarks in their respective domains. in addition to assessing effectiveness and efficiency, we also performed ablation and parameter studies to investigate the contributions of each mechanism in our framework and the impact of hyperparameters. ## conclusion this paper introduces master, a novel multiagent system framework that leverages a specialized mcts to enhance the planning capabilities of llm. our llm-optimized mcts broadens the applicability of mcts to a wider range of tasks with reduced costs. besides, we employ this algorithm to guide agent recruitment and communication protocols, thereby introducing an innovative form of multi-agent system. extensive experiments across various datasets demonstrate master's effectiveness and efficiency over existing frameworks.