AI Papers Reader

Personalized digests of latest AI research

View on GitHub

LE-MCTS: A Novel Framework for Ensembling Large Language Models to Tackle Complex Reasoning

Large language models (LLMs) have shown impressive capabilities across various tasks, but open-source models often struggle with complex reasoning problems. Existing ensemble methods, which combine multiple LLMs at the token or output level, have failed to adequately address this challenge. A new research paper introduces Language model Ensemble with Monte Carlo Tree Search (LE-MCTS), a process-level ensembling framework that significantly improves performance on complex reasoning tasks.

The core innovation of LE-MCTS lies in its process-level approach. Unlike existing methods that combine models at the token or final output stage, LE-MCTS models the step-by-step reasoning process as a Markov Decision Process (MDP). Each state in the MDP represents an intermediate reasoning path, while actions consist of generating the next reasoning step using one of several LLMs from a pre-defined pool. This allows for the correction of errors early in the reasoning chain, guiding the model toward more accurate solutions.

The selection of the best reasoning chain is guided by a process-based reward model (PRM), which assigns a scalar value to the correctness of each intermediate reasoning step. LE-MCTS utilizes Monte Carlo Tree Search (MCTS) to efficiently explore the space of possible reasoning chains, maximizing the overall reward. An example of LE-MCTS’s output is shown in Figure 1 of the paper. The figure demonstrates how different LLMs contribute to different steps in solving a complex word problem, with each step’s LLM highlighted in a corresponding color.

The effectiveness of LE-MCTS is demonstrated through experiments on five mathematical reasoning benchmarks: GSM8K, MATH, SVAMP, ASDiv, and MQA. These benchmarks represent a range of difficulty, from simple arithmetic problems (GSM8K) to complex competition-level math problems (MATH) and GRE/GMAT-level questions (MQA). The results show that LE-MCTS consistently outperforms existing single LLM decoding algorithms and other LLM ensemble methods across all five benchmarks. Notably, LE-MCTS achieves a 3.6% improvement on the MATH dataset and a 4.3% improvement on MQA compared to the next-best performing methods.

A key aspect of LE-MCTS’s success is its optimistic backpropagation strategy. Unlike standard MCTS backpropagation, which updates the value of a node based on the average reward of its children, LE-MCTS uses the maximum reward. This encourages exploration of paths with high potential, even if some intermediate steps are less than optimal. This technique, combined with a carefully tuned UCT (Upper Confidence Bound 1 applied to Trees) constant for controlling exploration versus exploitation, allows LE-MCTS to effectively navigate the complex search space.

The paper also investigates the impact of the number of MCTS iterations and the choice of UCT constant on the performance of LE-MCTS. These experiments demonstrate that increasing the number of iterations generally improves accuracy, but at a computational cost. Similarly, the optimal choice of the UCT constant depends on the complexity of the problems, with lower values promoting deeper searches for more challenging tasks. Finally, the researchers analyze the efficiency of LE-MCTS against other ensemble methods, showing that while LE-MCTS has higher computational requirements, its superior performance on complex reasoning justifies the increased cost.

In summary, the paper presents a significant advancement in LLM ensembling. LE-MCTS offers a novel process-level approach that overcomes the limitations of existing token- and output-level methods, demonstrating substantial improvements in tackling complex reasoning problems. The framework’s ability to adapt to varying problem complexities and its use of an optimistic backpropagation strategy contribute significantly to its effectiveness. This work represents a valuable step towards developing more robust and powerful LLMs capable of solving challenging real-world problems.