Ensembling Large Language Models with Process Reward-Guided Tree Search for Better Complex Reasoning
LE-MCTS uses PRM-guided MCTS to ensemble reasoning steps, reaching 45.2% on MATH and 71.1% on MQA.
Key Findings
Methodology
LE-MCTS formulates stepwise reasoning as an MDP: states are partial reasoning trajectories, while actions select one model from LLaMA-3, Gemma-2, DeepSeek-Math, or Rho-Math to generate the next line. MCTS uses UCT selection, greedy newline-delimited expansion, Math Shepherd PRM evaluation, and optimistic backpropagation based on the maximum child value.
Key Results
- Across GSM8K, MATH500, SVAMP, ASDiv, and MQA, Top-3 LE-MCTS averages 73.8% accuracy, 3.9 points above Best-of-Ensemble (BoE) at 69.9%. It reaches 45.2% on MATH, a 3.6-point gain over the runner-up.
- On MQA, LE-MCTS achieves 71.1%, improving 4.3 points over the second-best method. It also obtains 84.1% on GSM8K, 84.0% on SVAMP, and 84.4% on ASDiv.
- Optimistic backpropagation improves all datasets by 0.1–1.6%. C=0.5 is best for MATH/MQA, whereas C=1.0 or 1.414 favors simpler tasks; increasing niter from 10 to 200 generally helps.
Significance
The work shifts ensembling from probability or answer aggregation to reasoning-process search. It addresses heterogeneous open-source model expertise, shared candidate failures, and vocabulary incompatibility. More broadly, it shows that model diversity becomes useful for difficult reasoning only when paired with intermediate-step evaluation and structured search.
Technical Contribution
The method constructs a unified natural-language reasoning tree across architecturally incompatible LMs. It uses UCT for exploration–exploitation, newline-level greedy expansion, and Math Shepherd PRM rewards without rollouts; the authors note ORM-based rollouts increase execution time roughly five- to tenfold. Optimistic backpropagation encodes the objective that one viable child can justify retaining a parent.
Novelty
LE-MCTS is presented as a pioneering process-level LM ensemble framework that combines multiple generators inside one MCTS tree. Unlike BoE and EBS, it does not merely select or beam-search complete candidates; unlike LLM-Blender, MoA, and EVA, it composes intermediate reasoning steps and avoids shared vocabulary or architecture requirements.
Limitations
- With niter=200, MATH inference averages 342.2 minutes per example, versus 47.2 for EBS, making the accuracy gain expensive. The method is therefore unsuitable for latency-sensitive deployment without optimization.
- Deep search provides limited benefit on easy problems: BoE and EBS are cheaper and competitive on ASDiv. Fixed search budgets can waste computation when short reasoning chains suffice.
- Performance depends on PRM calibration. If the reward model misjudges a locally plausible but globally invalid step, MCTS may systematically amplify that error.
Future Work
Promising directions include difficulty-adaptive niter and C, learned model routing by problem type, better PRM calibration and long-horizon credit assignment, parallel search and KV-cache sharing, and evaluation beyond mathematics on code, science, and planning tasks.
AI Executive Summary
Complex mathematical reasoning requires a model to remain correct across many intermediate steps, not merely produce a plausible final answer. The paper argues that token-level ensembling is constrained by vocabularies and architectures, while output-level systems such as LLM-Blender and MoA cannot recover when all complete candidates contain errors.
The proposed LE-MCTS, or Language model Ensemble with Monte Carlo Tree Search, treats each solution as a path through a reasoning tree. A node stores a partial derivation; an action selects one model from a pool and generates the next step. UCT balances exploration and exploitation, while the Math Shepherd process reward model scores each step. Optimistic backpropagation preserves a branch when at least one continuation is promising, allowing different models to contribute different parts of one solution.
On GSM8K, MATH500, SVAMP, ASDiv, and MQA, Top-3 LE-MCTS averages 73.8%, versus 69.9% for BoE. It reaches 45.2% on MATH and 71.1% on MQA, gains of 3.6 and 4.3 points over the respective runners-up. The trade-off is computation: 200 iterations require 342.2 minutes per MATH example. Thus LE-MCTS is most compelling for difficult, high-value reasoning, while simpler tasks may favor BoE or EBS.
Deep Analysis
Background
Open-source LMs such as LLaMA-3, Gemma-2, DeepSeek-Math, and Rho-Math exhibit complementary strengths. Prior work explored token/logit fusion, EVA’s vocabulary projection, and output fusion through LLM-Blender and MoA. Separately, Chain-of-Thought, MCTS, and process reward models improved reasoning search. The missing link was a principled way to combine heterogeneous generators during the reasoning process itself.
Core Problem
Given question q and models {π1,…,πL}, any model may generate step k. The candidate space grows as ∏k|Pk|, making exhaustive search infeasible. Ranking complete outputs cannot repair shared errors, while token fusion requires compatible vocabularies, dimensions, or architectures. The central challenge is therefore scalable step-level selection across models.
Innovation
- ��MDP formulation: a state is a partial trajectory and an action chooses a model plus its next step.
- ��Unified reasoning tree: natural-language steps from incompatible LMs can coexist without parameter fusion.
- ��PRM-guided search: Math Shepherd scores each intermediate step directly.
- ��Optimistic backpropagation: the maximum child value represents a parent, matching the objective that one successful continuation is sufficient.
Methodology
- ��Initialization: create a root node for q; each node stores trajectory, value vs, and visit count Ns.
- ��Selection: recursively choose the eligible child maximizing U(s)=vs+C√(ln Nparent/Ns).
- ��Expansion: randomly select πl and greedily decode pk until newline using pk,t=argmaxw πl(w|pk,<t;q,p1:k−1). Expansion is capped by nchild and an ε depth-prioritization rule.
- ��Evaluation: compute rk=ϕ(q,pk) with the pretrained Math Shepherd PRM; no rollout is performed. The paper reports ORM rollouts would raise runtime about 5–10×.
- ��Backpropagation: increment Ns and update ancestors using the maximum child value. After niter iterations, rank terminal trajectories by PRM and return the highest-scored solution.
Experiments
The evaluation uses GSM8K, MATH500, SVAMP, ASDiv, and MQA, with accuracy as the metric. Baselines include Greedy, Self-Consistency, Beam Search, Best-of-N, BoE, EBS, LLM-Blender, MoA, and EVA. The pool contains LLaMA-3 8B, Gemma-2 9B, DeepSeek-Math 7B, and Rho-Math 7B. Default niter is 200; ablations vary backpropagation, UCT C, and iteration count. Efficiency is measured on one NVIDIA H100 80GB.
Results
Top-3 LE-MCTS averages 73.8%, exceeding BoE’s 69.9%. Per-dataset scores are GSM8K 84.1%, MATH 45.2%, SVAMP 84.0%, ASDiv 84.4%, and MQA 71.1%. LLM-Blender collapses to 1.4% on MATH, illustrating the weakness of output fusion. Optimistic backpropagation adds 0.1–1.6%; performance generally rises from niter=10 to 200, but MATH throughput reaches 342.2 minutes/example.
Applications
The framework fits competition mathematics, GRE/GMAT solving, theorem derivation, code planning, and tool-using agents requiring multi-step verification. Deployment needs complementary models, a reasonably calibrated PRM, and GPU capacity. For easy or latency-sensitive tasks, BoE or EBS may deliver similar accuracy at much lower cost.
Limitations & Outlook
The approach assumes reasoning can be segmented by newline and that local PRM scores correlate with global correctness. Search can amplify reward-model errors, and 200 iterations are costly. The evidence is limited to mathematical benchmarks and mostly open-source models. Future work should introduce adaptive budgets, parallelization, caching, stronger long-horizon PRMs, and tests in code, science, and planning.
Plain Language Accessible to non-experts
Imagine a restaurant preparing an extremely difficult dish. The old methods either mix every chef’s tiny hand movements together, or ask each chef to finish an entire dish before choosing one. If everyone makes the same mistake, neither method can rescue the meal. LE-MCTS lets chefs take turns: after each step, another chef may propose what to do next, while an inspector checks whether that step makes sense. The system keeps several possible cooking plans, spends more effort on promising ones, and occasionally checks less-tried plans. A chef who is best at the opening can hand the dish to another who is better at the finale. This is why the approach can outperform any single chef. But repeated trial cooking is slow: on hard MATH problems, 200 search rounds average 342.2 minutes per example. For easy dishes, faster selection methods are more sensible.
ELI14 Explained like you're 14
Think of four classmates forming a math-game squad. One is great at word problems, another at tricky contest puzzles, and another at checking calculations. Everyone is smart, but everyone can make a mistake. The usual strategy is to let each person finish a whole solution and vote. But what if all four get stuck at the same step?
LE-MCTS works like a branching game map. At every checkpoint, a different classmate can write the next move. A checker gives that move a score, and the searcher spends more turns on routes that look promising while still exploring new routes. The final answer can be a relay: student A starts, student B fixes the middle, and student C finishes!
The clever part is the scoring rule. If one continuation from a checkpoint looks excellent, the checkpoint stays valuable even if its other branches are bad. That is like keeping a game level because one hidden path can still lead to victory.
The results are impressive: 45.2% on MATH and 71.1% on MQA, beating the next-best systems by 3.6 and 4.3 points. The catch? Searching 200 rounds on MATH takes about 342.2 minutes per question. So use it for boss-level problems, not every easy homework exercise!
Glossary
Monte Carlo Tree Search (MCTS)
A search method that repeatedly selects, expands, evaluates, and backs up nodes in a tree. It allocates limited computation toward promising decisions while retaining exploration.
LE-MCTS uses MCTS to search combinations of model-generated reasoning steps.
Process Reward Model (PRM)
A model that evaluates intermediate reasoning steps rather than only final answers. Technically, the paper computes rk=ϕ(q,pk) using Math Shepherd.
PRM supplies the reward guiding tree search and ranking terminal trajectories.
UCT
The Upper Confidence bound applied to Trees criterion combines node value with an exploration bonus. LE-MCTS uses U(s)=vs+C√(ln Nparent/Ns).
UCT chooses which eligible child to follow during selection.
Optimistic Backpropagation
A backup rule that propagates the maximum child value instead of averaging all child rewards. It assumes one strong continuation can make a partial path useful.
This is LE-MCTS’s principal modification to standard value backup.
Process-level ensembling
Combining models at intermediate reasoning steps rather than at token probabilities or complete outputs. It permits model handoffs within one solution.
LE-MCTS is designed as a process-level ensemble, unlike EVA, MoA, and LLM-Blender.
Open Questions Unanswered questions from this research
- 1 How reliably does a PRM score long, globally dependent reasoning? Current local rewards may miss errors that appear only several steps later, requiring better calibration, long-horizon labels, and outcome-aware evaluation.
- 2 Random model selection is simple but not necessarily optimal. It remains unclear how to learn routing policies from problem type, partial trajectory, model expertise, and uncertainty.
Applications
Immediate Applications
Competition-math assistance
An education platform can combine open-source math LMs and use Math Shepherd PRM to inspect each step before selecting a solution. This suits MATH, GRE, and GMAT-style problems, provided the platform can afford GPU search and independently verify answers.
Multi-model reasoning agents
Code or science agents can treat each plan step as a branching checkpoint. Specialist models propose alternatives, while a process evaluator filters them, reducing the risk of committing early to one flawed end-to-end plan.
Long-term Vision
General reliable reasoning
A cross-domain PRM and adaptive search controller could allocate deep search to high-risk mathematics, code, science, and planning tasks while using shallow decoding elsewhere. The main obstacles are reward quality, latency, and scalable parallel inference.
Abstract
Despite recent advances in large language models, open-source models often struggle to consistently perform well on complex reasoning tasks. Existing ensemble methods, whether applied at the token or output levels, fail to address these challenges. In response, we present Language model Ensemble with Monte Carlo Tree Search (LE-MCTS), a novel framework for process-level ensembling of language models. LE-MCTS formulates step-by-step reasoning with an ensemble of language models as a Markov decision process. In this framework, states represent intermediate reasoning paths, while actions consist of generating the next reasoning step using one of the language models selected from a predefined pool. Guided by a process-based reward model, LE-MCTS performs a tree search over the reasoning steps generated by different language models, identifying the most accurate reasoning chain. Experimental results on five mathematical reasoning benchmarks demonstrate that our approach outperforms both single language model decoding algorithms and language model ensemble methods. Notably, LE-MCTS improves performance by 3.6% and 4.3% on the MATH and MQA datasets, respectively, highlighting its effectiveness in solving complex reasoning problems.