💬 NLP

Empirical-MCTS: Continuous Agent Evolution via Dual-Experience Monte Carlo Tree Search

Empirical-MCTS introduces a dual-loop framework that enhances Large Language Model reasoning by integrating local search with a global memory system, utilizing Pairwise-Experience-Evolutionary Meta-Prompting and a Memory Optimization Agent to continuously evolve adaptive meta-prompts and distill insights across problems, thereby significantly outperforming stateless MCTS strategies on complex reasoning benchmarks.

Original authors: Hao Lu, Haoyuan Huang, Yulin Zhou, Chen Li, Ningxin Zhu

Published 2026-02-05

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Hao Lu, Haoyuan Huang, Yulin Zhou, Chen Li, Ningxin Zhu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a very difficult puzzle, like a complex math problem or a logic riddle.

The Old Way: The "Amnesiac" Genius
Currently, most advanced AI models act like a brilliant genius who suffers from total amnesia after every single puzzle. They might try 100 different ways to solve a problem, find the one that works, and celebrate. But the moment they move to the next puzzle, they forget everything they just learned. They start from scratch, treating the new problem as if they've never seen a puzzle before. They don't "remember" that a specific trick worked last time, so they waste time rediscovering it.

The New Way: Empirical-MCTS (The "Wisdom-Collecting" Detective)
The paper introduces a new system called Empirical-MCTS. Think of this AI not as an amnesiac, but as a detective who keeps a growing, organized case file. Every time they solve a clue or make a mistake, they don't just throw the paper away. They analyze it, write down what worked, and add it to their permanent "Wisdom Library."

This system works using two main "loops" or habits:

1. The Local Loop: The "Debate Club" (PE-EMP)

Inside the AI's mind, while it is trying to solve a specific problem, it doesn't just guess. It acts like a Debate Club.

It generates two different possible answers (let's call them Candidate A and Candidate B).
It puts them in a "debate" where it acts as the judge.
Instead of just picking a winner, the judge asks: "Why did A win? What specific rule did it follow that B missed?"
Based on this debate, the AI rewrites its own instruction manual (called a "meta-prompt") in real-time. It's like a student realizing, "Oh, I need to check my math before I write the final answer," and immediately updating their study guide for the next step.

2. The Global Loop: The "Librarian" (Memory Optimization)

While the "Debate Club" is working on the current problem, a separate "Librarian" agent is watching.

If the Debate Club discovers a brilliant new trick or a common mistake to avoid, the Librarian doesn't just save the raw text.
The Librarian acts like a smart editor. It might add a new rule to the library, merge two similar rules into one to save space, modify an old rule that was slightly wrong, or delete a rule that is no longer useful.
This creates a "living" library of wisdom that gets smarter and more precise with every single problem the AI solves.

The Result: Getting Smarter Without "Studying"

Usually, to make an AI smarter, you have to "train" it, which is like forcing a human to go back to school for months to relearn everything. That is expensive and slow.

Empirical-MCTS is different. It doesn't change the AI's brain (its weights). Instead, it changes the AI's context.

It takes a standard AI model (like a smart but inexperienced student).
It gives that student a constantly updating "cheat sheet" of their own past successes and failures.
Because the student has this cheat sheet, they can solve incredibly hard problems (like advanced math competitions or abstract logic puzzles) much better than before, even though the student's underlying brain hasn't changed.

What the Paper Found

The authors tested this on some of the hardest logic and math tests available (like the AIME math competition and abstract reasoning tasks).

The Amnesiac AI (standard methods) often got stuck or gave up on the hardest problems.
The Wisdom-Collecting AI (Empirical-MCTS) solved significantly more problems.
Cost Efficiency: They found that using this method with a smaller, cheaper AI model actually beat much larger, more expensive models. It's like a small team with a perfect, shared playbook beating a giant team that has no memory of past games.

In short: This paper shows that if you teach an AI to "remember" its own reasoning patterns and update its own instructions as it goes, it becomes a master problem-solver without needing to be retrained from scratch. It turns a "stateless" search into a continuous journey of learning.

Technical Summary: Empirical-MCTS

1. Problem Statement

Current inference-time scaling strategies, particularly Monte Carlo Tree Search (MCTS) and "Best-of-N" sampling, have significantly improved the reasoning capabilities of Large Language Models (LLMs). However, a critical limitation persists: these approaches are stateless. Once a search process concludes for a specific problem, successful reasoning patterns and valid strategies are discarded. This contrasts sharply with human problem-solving, which is empirical, relying on the accumulation of both long-term domain knowledge and short-term immediate feedback. Existing attempts to integrate memory, such as FLEX (which separates retrieval from reasoning) or Training-Free GRPO (which lacks structured tree search), fail to unify continuous experience accumulation with structured exploration. Consequently, agents cannot evolve their search strategies dynamically across problem instances without expensive parameter updates.

2. Methodology: The Empirical-MCTS Framework

The authors propose Empirical-MCTS, a dual-loop framework designed to transform stateless search into a continuous, non-parametric learning process. The system unifies local exploration with global memory optimization through two core mechanisms:

A. Pairwise-Experience-Evolutionary Meta-Prompting (PE-EMP)

PE-EMP acts as a reflexive optimizer within the local search loop. Instead of using static system prompts for node expansion, PE-EMP dynamically evolves the meta-prompt in real-time based on pairwise feedback.

Mechanism: When expanding a node, the system compares a candidate state ( $S_c$ ) against a baseline state ( $S_p$ ). A Judge model processes the query, prior experiences, and the two states to generate a triadic output: a raw score vector, new empirical insights, and an evolved meta-prompt ( $P_{evolved}$ ).
Seven-Stage Cognitive Process: The PE-EMP module executes a strict sequence:
1. Adaptive Criteria Generation: The model generates specific evaluation dimensions tailored to the query (inspired by Self-Principled Critique Tuning).
2. Comparative Chain-of-Thought: A step-by-step critique contrasts the candidate and baseline against these criteria.
3. Dynamic Weight Allocation: Weights are assigned to criteria based on context relevance.
4. Weighted Scoring: Quantitative scores are calculated.
5. Raw Score Generation: A precise scalar value (0–10) is derived.
6. Context-Aware Insight Synthesis: Immediate feedback is synthesized with retrieved historical wisdom to distill high-order empirical insights ( $E_{new}$ ).
7. Strategic Prompt Evolution: The model analyzes execution differences to synthesize a more advanced meta-prompt, encoding critical success factors and failure lessons.
Retrieval: To prevent semantic drift, the system retrieves experiences ( $E_{prior}$ ) from a global library only if they share the same task taxonomy (e.g., geometry-proof) as the current query.

B. Memory Optimization Agent

This component manages a global experience repository as a dynamic policy prior, functioning as an optimizer in the context space rather than a static database.

Atomic Operations: Upon receiving new insights ( $E_{new}$ $E_{n e w}$ ) from PE-EMP, the agent executes four atomic operations to update the library ( $D_t$ $D_{t}$ ):
- Add: Appends distinct, high-quality experiences.
- Modify: Refines existing experiences based on new semantic advantages.
- Merge: Synthesizes fragmented experiences into cohesive principles to reduce redundancy.
- Delete: Prunes obsolete or low-quality experiences (a "forgetting" mechanism).
Non-Parametric Update: This process shifts the output distribution $\pi(y|q, D)$ toward higher rewards over time without gradient-based training.

C. Value Estimation and Search Strategy

Hybrid Preference Integration: To convert discrete insights into continuous rewards, the framework uses a Hybrid-Reward signal. It maps raw pairwise scores to local transition probabilities via the Bradley-Terry model and employs an Enhanced Borda Count (EBC) to construct a global ranking, addressing the non-transitivity inherent in LLM preferences.
Search: The framework uses Upper Confidence Bound (UCB) for node selection and a decay-based backpropagation rule to ensure high-reward insights propagate efficiently up the tree.

3. Key Contributions

Empirical-MCTS Paradigm: A novel framework bridging structured search and continuous learning, transforming MCTS from a stateless inference technique into a non-parametric online learning agent capable of accumulating "wisdom" across disparate problems without weight updates.
PE-EMP Mechanism: A reflexive optimizer that synthesizes "self-principles" from pairwise feedback to dynamically evolve meta-prompts, allowing agents to refine reasoning policies in real-time.
Empirical Validation: Demonstration that Empirical-MCTS outperforms standard MCTS and previous experience-based models on high-difficulty benchmarks, proving that "remembering" reasoning patterns is critical for solving complex, multi-step logic problems.

4. Experimental Results

The framework was evaluated on AIME25, MathArena Apex, and ARC-AGI-2 using models including DeepSeek-V3.1-Terminus, gpt-oss-120b, and Gemini 3 Flash.

Mathematical Reasoning (AIME25): Empirical-MCTS achieved 73.3% accuracy, outperforming the stateless LLaMA-Berry (63.3%) and the memory-augmented FLEX agent (66.6%).
Extreme Difficulty (MathArena Apex): The base model scored 0.00%. While LLaMA-Berry reached 2.08%, Empirical-MCTS achieved 4.17%, demonstrating the ability to synthesize new solution paths through empirical accumulation where standard methods failed.
Cost-Efficiency (ARC-AGI-2 & MathArena): Using the cost-efficient Gemini 3 Flash, Empirical-MCTS achieved 38.33% on ARC-AGI-2 and 35.42% on MathArena Apex. This performance surpassed much more expensive models (e.g., GPT-5.2 at $12.00 cost vs. Ours at $5.24 cost), establishing a new Pareto frontier for reasoning efficiency.
Ablation Studies: Removing PE-EMP reduced performance to 56.7% (matching naive repeated sampling), confirming that the evolution of prompts driven by pairwise signals is the core engine of improvement. Removing meta-prompting while retaining memory dropped performance to 66.7%, highlighting the necessity of dynamic instruction.

5. Significance and Claims

The paper claims that Empirical-MCTS establishes a new paradigm where structured search is coupled with empirical accumulation. The authors argue that the critical necessity for mastering complex, open-ended reasoning tasks lies not just in the search capability itself, but in the ability to "remember" and refine past reasoning patterns.

By converting search history into actionable policy priors, the framework enables significantly smaller models to outperform larger, stateless baselines. The results underscore that continuous, non-parametric learning via memory optimization and meta-prompt evolution is a viable and effective alternative to traditional gradient-based training for enhancing LLM reasoning.

Limitations Acknowledged: The authors note that the framework assumes the base model can accurately verify reasoning steps. For tasks exceeding the model's verification boundary, there is a risk of integrating "hallucinated wisdom," potentially leading to degenerative evolution. Future work aims to introduce robust consistency checks and uncertainty quantification to mitigate this.