MCTS Is Counting the Wrong Thing: Learning Exploration Counts for LLM Reasoning
Organizations: Fudan University · Shanghai Innovation Institute · Meituan · Shanghai Academy of Artificial Intelligence for Science
Abstract
Monte Carlo tree search (MCTS) has powered landmark successes in reinforcement learning, yet its gains in LLM reasoning can remain modest despite substantial search effort. We identify an overlooked bottleneck: what MCTS counts. Standard UCT assigns independent visit counts to textual branches, allowing different formulations of the same reasoning strategy to repeatedly receive exploration bonuses. Our theoretical analysis shows that this count fragmentation can impair exploration efficiency, as quantified by increased cumulative regret. To address this problem, we introduce Learned Pseudo-Count MCTS (LPC-MCTS), which changes only the exploration statistic in UCT. A lightweight Coin-Flipping Network head on the policy's hidden representations estimates representation coverage, enabling related branches to share exploration evidence. Across 5 mathematical-reasoning and 7 search benchmarks, LPC-MCTS consistently outperforms strong MCTS baselines. Holding each LPC-MCTS-trained policy fixed, replacing standard MCTS counts at inference improves average mean@16 accuracy across 5 mathematical benchmarks by 3.79 percentage points on Qwen2.5-7B and 2.71 points on Qwen3-4B. Applying LPC-MCTS during both training and inference yields gains of 4.96 and 4.37 points over standard MCTS, respectively. Together, our theory and experiments show that changing what MCTS counts can substantially improve its exploration efficiency and reasoning performance.
Figures & tables
| Training | Inference | AIME 24 | AIME 25 | AIME 26 | HMMT25 | BRUMO25 | Avg. |
| Qwen2.5-7B | |||||||
| SFT | Direct sampling | 9.58 | 8.54 | 8.13 | 4.17 | 19.58 | 10.00 |
| SFT | MCTS | 10.42 | 12.08 | 8.54 | 10.00 | 21.04 | 12.42 |
| DAPO | Direct sampling | 24.58 | 23.33 | 20.21 | 9.38 | 30.63 | 21.63 |
| DAPO | MCTS | 29.79 | 27.71 | 23.33 | 16.25 | 40.63 | 27.54 |
| DAPO + Entropy | Direct sampling | 27.08 | 22.92 | 23.96 | 12.29 | 33.33 | 23.92 |
| Training | Inference | NQ | TriviaQA | PopQA | HotpotQA | 2Wiki | MuSiQue | Bamboogle | Avg. |
| Qwen2.5-7B-Instruct | |||||||||
| SFT | Greedy sampling | 36.80 | 54.40 | 25.80 | 43.20 | 38.60 | 29.20 | 46.40 | 39.20 |
| SFT | MCTS | 36.96 | 53.84 | 25.24 | 42.80 | 42.92 | 29.72 | 47.52 | 39.86 |
| DAPO | Greedy sampling | 43.40 | 55.60 | 39.60 | 46.00 | 43.60 | 31.20 | 46.40 | 43.69 |
| DAPO | MCTS | 45.48 | 56.64 | 42.48 | 45.96 | 40.04 | 31.44 | 48.00 | 44.29 |
| DAPO + Entropy | Greedy sampling | 44.60 | 57.60 | 41.00 | 44.60 | 44.60 | 31.40 | 48.00 | 44.54 |
Appendix figures & tables24 assets
Supplementary material from the paper’s appendix.
Appendix
| Hyperparameter | Value |
| Optimizer | AdamW |
| Learning rate | |
| Weight decay | 0.01 |
| Learning-rate schedule | Cosine |
| Warmup ratio | 0.1 |
| Global batch size | 16 |
| Hyperparameter | Value |
| General training hyperparameters | |
| Backbones | Qwen2.5-7B / Qwen3-4B |
| Optimizer | AdamW |
| Policy learning rate | |
| Prompts per training batch | 128 |
| Samples per prompt | 8 |
| Hyperparameter | Value |
| General training hyperparameters | |
| Backbones | Qwen2.5-7B-Instruct / Llama-3.2-3B-Instruct |
| Optimizer | AdamW |
| Policy learning rate | |
| Prompts per training batch | 512 |
| Samples per prompt | 5 |
| Hyperparameter | Value |
| CFN output dimension | 20 |
| Optimizer | AdamW |
| Online learning rate | |
| CFN-head update frequency | Every 4 MCTS iterations |
| Token filtering | Top 30% |
| CFN backbone | Embedding model | Spearman [95% CI] | Nearest-neighbor agreement |
| Qwen3-4B | Qwen3-Embedding-4B | 0.255 [0.197, 0.315] | 24.1% |
| Qwen3-4B | QZhou-Embedding | 0.248 [0.197, 0.299] | 24.8% |
| Qwen2.5-7B | Qwen3-Embedding-4B | 0.335 [0.279, 0.391] | 29.2% |
| Qwen2.5-7B | QZhou-Embedding | 0.358 [0.303, 0.413] | 26.9% |
| Probe nodes | Questions | Pseudo-count change (geometric mean; 95% CI) |
| Same-pattern siblings | 400 | |
| Distinct-pattern siblings | 126 |
| Training | Inference | AIME 24 | AIME 25 | AIME 26 | HMMT25 | BRUMO25 | Avg. |
| Qwen2.5-7B | |||||||
| LPC-MCTS (w/o pseudo-count) | MCTS | 39.17 | 25.63 | 24.79 | 18.96 | 44.58 | 30.63 |
| LPC-MCTS (w/o trajectory selection) | LPC-MCTS | 34.79 | 29.58 | 27.71 | 15.83 | 42.50 | 30.08 |
| LPC-MCTS (w/o node aggregation) | LPC-MCTS | 37.71 | 28.75 | 25.63 | 19.17 | 48.54 | 31.96 |
| LPC-MCTS (w/o both) | LPC-MCTS | 37.50 | 26.04 | 28.96 | 18.54 | 45.42 | 31.29 |
| LPC-MCTS | LPC-MCTS (w/o node aggregation) | 35.83 | 28.33 | 27.08 | 19.17 | 46.67 | 31.42 |
| Top | AIME 24 | AIME 25 | AIME 26 | HMMT25 | BRUMO25 | Avg. |
| Qwen2.5-7B | ||||||
| 37.08 | 30.63 | 27.92 | 23.33 | 45.00 | 32.79 | |
| 36.25 | 26.67 | 28.75 | 22.71 | 45.00 | 31.88 | |
| 34.38 | 31.67 | 27.08 | 24.79 | 42.71 | 32.13 | |
| 38.96 | 29.17 | 29.79 | 22.08 | 43.33 | 32.67 | |
| Qwen3-4B | ||||||
| Generated tokens (M) | Time (s/candidate) | ||||
| Model | MCTS | LPC-MCTS | Reduction | MCTS | LPC-MCTS |
| Qwen3-4B | 80.958 | 63.106 | 22.05% | 16.72 | 15.98 |
| Qwen2.5-7B | 44.007 | 25.525 | 42.00% | 12.05 | 12.83 |
| Measurement | Qwen3-4B | Qwen2.5-7B |
| Mean CFN input length (tokens/sequence) | 2,905.48 | 1,442.85 |
| CFN input sequences processed | 20,968 | 16,512 |
| CFN feature-extraction time share | 6.50% | 5.31% |
| CFN scoring/control time share | 0.23% | 0.18% |
| Combined CFN time share | 6.73% | 5.49% |
Monte Carlo Tree Search
Monte Carlo Tree Search (MCTS) uses sampled lookahead through decision trees to choose actions in large, uncertain planning problems.
See all 97 papers