Source-linked AI summary
Empirical-MCTS: Continuous Agent Evolution via Dual-Experience Monte Carlo Tree Search
Hao Lu, Haoyuan Huang, Yulin Zhou, Chen Li, Ningxin Zhu
TL;DR
Inference-time search methods can improve reasoning, but often discard useful patterns between problems. Empirical-MCTS couples local prompt evolution with global memory optimization, and reports stronger results across difficult reasoning benchmarks, including against larger stateless baselines.
Problem
Inference-time search methods often treat each problem independently and discard successful reasoning patterns, leaving persistent experience insufficiently integrated with structured search.
Source: §1 · p. 1Method
Empirical-MCTS combines pairwise-feedback-driven prompt evolution during local search with a global memory optimizer that accumulates experience across problems without weight updates.
Source: §1 · p. 2, §3.1 · p. 3Results
Takeaways & Limitations
Across the evaluated benchmarks, the authors conclude that converting search history into actionable policy priors supports reasoning efficiency and performance against stateless baselines.
Source: §5 · p. 8The framework relies on the base model to verify reasoning; beyond that verification boundary, low-quality or hallucinated insights may enter memory and drive prompt evolution on false premises.
Source: §5 · p. 8
Abstract
from arXiv · showhide
Inference-time scaling strategies, particularly Monte Carlo Tree Search (MCTS), have significantly enhanced the reasoning capabilities of Large Language Models (LLMs). However, current approaches remain predominantly stateless, discarding successful reasoning patterns after each problem instance and failing to mimic the empirical accumulation of wisdom characteristic of human problem-solving. To bridge this gap, we introduce Empirical-MCTS, a dual-loop framework that transforms stateless search into a continuous, non-parametric learning process. The framework unifies local exploration with global memory optimization through two novel mechanisms: Pairwise-Experience-Evolutionary Meta-Prompting (PE-EMP) and a Memory Optimization Agent. PE-EMP functions as a reflexive optimizer within the local search, utilizing pairwise feedback to dynamically synthesize adaptive criteria and evolve meta-prompts (system prompts) in real-time. Simultaneously, the Memory Optimization Agent manages a global repository as a dynamic policy prior, employing atomic operations to distill high-quality insights across problems. Extensive evaluations on complex reasoning benchmarks, including AIME25, ARC-AGI-2, and MathArena Apex, demonstrate that Empirical-MCTS significantly outperforms both stateless MCTS strategies and standalone experience-driven agents. These results underscore the critical necessity of coupling structured search with empirical accumulation for mastering complex, open-ended reasoning tasks.
1. Introduction
Empirical-MCTS addresses the statelessness of inference-time search by combining local reasoning updates with persistent experience across problems. Its evaluations report stronger performance than prior search and experience-based approaches on difficult reasoning benchmarks.
1. Introduction
- PE-EMP uses pairwise response feedback to synthesize adaptive criteria and evolve the system prompt during local search.The evolving prompt refines the generation policy, rather than using feedback only to select among responses.Source: §1 · pp. 1–2
- A Memory Optimization Agent treats the global repository as a dynamic policy prior and distills insights across problems through add, modify, and merge operations.The repository is updated with high-quality insights from the search process.Source: §1 · p. 2
- A hybrid preference model maps PE-EMP’s self-principled scores into a globally consistent ranking with Enhanced Borda Count.This is intended to address non-transitivity in LLM preferences and guide the prioritization of search trajectories.Source: §1 · p. 2
- The framework couples structured tree search with continuous experience accumulation, turning MCTS into a non-parametric online learning agent without weight updates.It combines local exploration with global memory optimization.Source: §1 · pp. 1–2
- Empirical-MCTS outperforms standard MCTS and previous experience-based models, achieving state-of-the-art results on high-difficulty benchmarks including AIME25, ARC-AGI-2, and MathArena Apex, while solving complex multi-step logic problems more efficiently than traditional search methods.Source: §1 · p. 2
2. Related Work
Prior work improves inference-time search structure and develops ways for agents to use experience, but these approaches leave experience and structured search only partially integrated. Meta-reasoning work informs Empirical-MCTS’s use of prompts to guide later reasoning steps.
2.1. Inference-Time Scaling and Tree Search
- Tree-search methods structure reasoning into steps, but remain stateless across problems and do not retain successful patterns discovered during search.Empirical-MCTS builds on LLaMA-Berry’s search backbone while persisting experience to evolve policy across problems.Source: §2.1 · p. 2
2.2. Experience-Driven Agents
- FLEX stores successful trajectories for retrieval, whereas Training-Free GRPO adjusts policy using group results; neither is itself a reasoning search engine integrated with a search tree.Empirical-MCTS combines MCTS-generated reasoning data with a global repository that stores and refines it.Source: §2.2 · p. 2
2.3. Meta-Reasoning and Refinement
- Self-Refine and Reflexion critique outputs, while MCTSR-Zero uses meta-prompts; Empirical-MCTS formalizes meta-prompts as short-term experience guiding child-node generation.The prompts include critiques and suggestions intended to keep reasoning focused and build on prior steps.Source: §2.3 · p. 3
3. Methodology: The Empirical-MCTS Framework
Empirical-MCTS combines pairwise-driven prompt evolution, persistent memory updates, preference-based value estimation, and tree search. These components use immediate feedback and accumulated experience to guide prompt generation, repository updates, and search valuation.
3.1. Pairwise-Experience-Evolutionary Meta-Prompting (PE-EMP)
- PE-EMP compares candidate and baseline states, generates context-specific evaluation criteria, critiques and scores responses, and evolves the prompt using lessons from the pair.The process also synthesizes new insights using retrieved experience; the evolved prompt encodes success factors and failure lessons.Source: §3.1 · pp. 3–4
3.2. Experience Memory Optimization
- A Memory Optimization Agent treats new insights as updates to a global knowledge state, using add, modify, merge, and delete operations on the experience library.The described operations expand the library, refine or combine entries, and prune obsolete or low-quality experiences.Source: §3.2 · pp. 4–5
3.3. Value Estimation via Hybrid Preference Integration
- The hybrid reward combines a Bradley-Terry local transition probability with an Enhanced Borda Count global ranking derived from pairwise comparisons.PE-EMP’s explicit self-principled scores provide the input for this preference integration.Source: §3.3 · p. 5
3.4. Search Strategy
- Search selects nodes with UCB and backpropagates values using a decay-based update that lets high-reward insights propagate through the tree.The update rule is adopted from Self-Refine MCTS.Source: §3.4 · p. 5
4. Experiments
Experiments compare Empirical-MCTS with inference-time baselines on AIME25, MathArena Apex, and ARC-AGI-2, using multiple frontier models. Results cover mathematical reasoning, cost-performance, ablations, memory growth, and policy evolution.
4.1. Experimental Setup
- Evaluation covers AIME25, MathArena Apex, and ARC-AGI-2 with DeepSeek-V3.1-Terminus, gpt-oss-120b, and Gemini 3 Flash against ICL, ReAct, repeated sampling, FLEX, LLaMA-Berry, and Training-Free GRPO.MathArena Apex uses recent competition problems to mitigate contamination and evaluates proof-writing; ARC-AGI-2 tests fluid intelligence through transformation programs inferred from minimal examples.Source: §4.1 · p. 5
4.2. Results on Mathematical Reasoning
- 73.3% on AIME25 exceeds LLaMA-Berry (63.3%) and FLEX (66.6%), while Empirical-MCTS reaches 4.17% on MathArena Apex versus 0.00% for the base model.On MathArena Apex, repeated sampling also scores 0.00%, while LLaMA-Berry reaches 2.08%.Source: §4.2 · pp. 5–6, Table 1 · p. 6
4.4. Ablation Studies and Scalability Analysis
- 76.7% at 8 rollouts for the full framework contrasts with 56.7% for standard MCTS without PE-EMP and memory.Without meta-prompting, performance is 66.7% at rollout 8; without memory and meta-prompting, it peaks at 66.7% at rollout 3 before falling to 63.3% at rollout 8, while repeated sampling plateaus at 56.7% after 2 rollouts.Source: §4.4 · pp. 6–7
4.3. Efficiency and Cost Analysis
- 35.42% accuracy at $5.24 on MathArena Apex outperforms Gemini 3 Pro (23.44%, $3.40) and GPT-5.2 (High) (13.54%, $12.00).On ARC-AGI-2, Empirical-MCTS reaches 38.33%, exceeding Gemini 3 Pro (31.1%) and Grok 4 (16.0%); it lies at the frontier’s knee despite GPT-5.2’s marginal accuracy lead.Source: §4.3 · p. 6, Figure 2 · p. 6, Table 2 · p. 7
4.4. Ablation Studies and Scalability Analysis
- The empirical memory repository grows monotonically from zero to 311 experiences over 8 rollouts, including 110 experiences during its growth trajectory.The repository accumulates distilled experiences without parameter updates.Source: §4.4 · p. 7, Figure 4 · p. 8
4.5. Qualitative Analysis of Policy Evolution
- By rollout 4, the meta-prompt shifts from generic calculation checks to geometry-specific guidance distilled from invalid proofs.For cyclic-quadrilateral proofs, the prompt instructs the model to verify Ptolemy’s inequality before assuming existence.Source: §4.5 · pp. 7–8
5. Conclusion
Empirical-MCTS couples structured search with non-parametric online learning, and evaluations across three benchmarks report a new Pareto frontier for reasoning efficiency. The framework depends on reliable verification: tasks beyond the base model’s verification boundary risk introducing low-quality insights.
5. Conclusion
- Empirical-MCTS couples PE-EMP with a dynamic global memory optimizer to refine reasoning policies in real time without gradient updates.The framework unifies structured search with non-parametric online learning.Source: §5 · p. 8
- Evaluations across AIME25, MathArena Apex, and ARC-AGI-2 report a new Pareto frontier for reasoning efficiency.The reported results also show significantly smaller models outperforming larger stateless baselines.Source: §5 · p. 8
- When tasks exceed the base model’s verification boundary, low-quality or hallucinated insights can steer meta-prompt evolution toward suboptimal regions.The authors identify this as a primary limitation of the framework.Source: §5 · p. 8
- Future work will add consistency checks and uncertainty quantification, and extend the framework to multi-turn interactions and longer-horizon planning.Source: §5 · p. 8