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
Figure 1: Motivation for LPC-MCTS. The parent and branches A - C are taken from an actual model rollout tree, and the displayed Cϕ values are their learned pseudo-counts. Although branches A and B differ textually, they follow the same reasoning pattern and receive similar pseudo-counts, whereas C follows a distinct pattern. Standard UCT instead treats B and C as equally unexplored because both have one exact visit. Additional rollout-tree examples are provided in Appendix F.1.2 .
Figure 2: Overview of LPC-MCTS, including CFN-based pseudo-count estimation, estimator training, tree selection, and pseudo-count-guided trajectory selection.
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
Table 1: Mathematical reasoning results under different training and test-time inference settings. SFT denotes the model before RL training. The bold text represents the best, while underlined represents the second best.
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
Table 2: Search results under different training and test-time inference strategies. SFT denotes the model before RL training. We evaluate greedy sampling with temperature T=0 and MCTS with temperature T=0.6 .
Appendix figures & tables24 assets
Supplementary material from the paper’s appendix.
Appendix
Hyperparameter
Value
Optimizer
AdamW
Learning rate
1×10−5
Weight decay
0.01
Learning-rate schedule
Cosine
Warmup ratio
0.1
Global batch size
16
Appendix
Table 3: Supervised fine-tuning configurations.
Hyperparameter
Value
General training hyperparameters
Backbones
Qwen2.5-7B / Qwen3-4B
Optimizer
AdamW
Policy learning rate
1×10−6
Prompts per training batch
128
Samples per prompt
8
Appendix
Table 4: Policy training configuration for tool-integrated mathematical reasoning.
Hyperparameter
Value
General training hyperparameters
Backbones
Qwen2.5-7B-Instruct / Llama-3.2-3B-Instruct
Optimizer
AdamW
Policy learning rate
1×10−6
Prompts per training batch
512
Samples per prompt
5
Appendix
Table 5: Policy training configuration for search.
Hyperparameter
Value
CFN output dimension d
20
Optimizer
AdamW
Online learning rate
1×10−4
CFN-head update frequency
Every 4 MCTS iterations
Token filtering
Top 30%
Appendix
Table 6: CFN estimator and online-training configurations.
Figure 3: An example of token-level uncertainty estimated by CFN within a Qwen3-4B modular-arithmetic response. Each eligible generated token is colored by its raw CFN score uv,t . Darker colors indicate higher uncertainty estimate, while lighter colors indicate relatively lower estimates. Tool responses are shown in gray and excluded from CFN scoring. The same applies hereafter.
Figure 4: An example of token-level uncertainty estimated by CFN within a Qwen3-4B modular-arithmetic response.
Figure 5: An example of token-level uncertainty estimated by CFN within a Qwen2.5-7B modular-arithmetic response.
Figure 6: An example of token-level uncertainty estimated by CFN within a Qwen2.5-7B geometric-reasoning response.
Figure 7: An example of token-level uncertainty estimated by CFN within a Qwen2.5-7B-Instruct search response.
Figure 8: An example of token-level uncertainty estimated by CFN within a Llama-3.2-3B-Instruct search response.
Figure 9: A geometry case from an actual Qwen3-4B rollout tree. Children A and B continue the same algebraic expansion and receive close pseudo-counts of 11.77 and 12.45. Child C instead combines Stewart’s theorem with an area argument and receives a lower pseudo-count of 8.46.
Figure 10: A combinatorial-reasoning case from an actual Qwen3-4B rollout tree. Children A and B repeat closely related manual constructions and receive pseudo-counts of 10.58 and 10.89. Child C reformulates the task as a maximum-independent-set problem and receives a lower count of 5.44.
Figure 11: A geometry case from an actual Qwen2.5-7B rollout tree. Children A and B retry closely related coordinate-based calculations and receive pseudo-counts of 6.43 and 6.35. Child C replaces this route with an area-ratio argument and receives a lower count of 3.41.
Figure 12: A symbolic-computation case from an actual Qwen2.5-7B rollout tree. Children A and B repeat the same symbolic-solving attempt and receive nearly identical pseudo-counts of 7.41 and 7.45. Child C switches to numerical fitting and receives a lower count of 4.98.
Figure 13: A solid-geometry case from an actual Qwen2.5-7B rollout tree. Children A and B retry the same coordinate-system equations and receive pseudo-counts of 6.26 and 6.48. Child C computes the dihedral angle with a vector normal and receives a lower count of 2.95.
Figure 14: A query-planning case from an actual Qwen2.5-7B-Instruct search rollout tree. Children A and B repeatedly search for the program’s directors and receive close pseudo-counts of 22.96 and 20.86. Child C instead follows the presenter relation first and receives a lower count of 14.05.
Figure 15: An evidence-use case from an actual Llama-3.2-3B-Instruct search rollout tree. Children A and B organize the same final answer around retrieved relationship evidence and receive pseudo-counts of 9.01 and 9.54. Child C relies on prior knowledge after noting an evidence gap and receives a lower count of 7.20.
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%
Appendix
Table 7: Semantic alignment of learned pseudo-counts. Spearman correlations are reported with 95% confidence intervals (CIs). Nearest-neighbor agreement compares count closeness with embedding cosine similarity.
Probe nodes
Questions
Pseudo-count change (geometric mean; 95% CI)
Same-pattern siblings
400
+5.5%[+3.5%,+7.4%]
Distinct-pattern siblings
126
−3.2%[−5.0%,−1.3%]
Appendix
Table 8: Count transfer to held-out sibling responses. Results across Qwen3-4B and Qwen2.5-7B measure the change in a probe’s pseudo-count after CFN updates on its sibling.
Figure 16: Training reward dynamics of standard MCTS and LPC-MCTS over 100 policy-training steps across two mathematical-reasoning and two search model settings.
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
Appendix
Table 9: Ablation results under separate training and inference settings on tool-integrated mathematical reasoning with Qwen2.5-7B and Qwen3-4B. Each value is the mean accuracy over 16 responses per problem (mean@16).
Top p%
AIME 24
AIME 25
AIME 26
HMMT25
BRUMO25
Avg.
Qwen2.5-7B
30%
37.08
30.63
27.92
23.33
45.00
32.79
50%
36.25
26.67
28.75
22.71
45.00
31.88
70%
34.38
31.67
27.08
24.79
42.71
32.13
100%
38.96
29.17
29.79
22.08
43.33
32.67
Qwen3-4B
Appendix
Table 10: Sensitivity to the top- p% token-filtering ratio on tool-integrated mathematical reasoning with Qwen2.5-7B and Qwen3-4B. Each value is the mean accuracy over 16 responses per problem (mean@16).
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
Appendix
Table 11: Inference-time costs on AIME 2024/2025. Generated tokens are summed over the entire search; time is the amortized wall-clock cost per candidate slot.
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%
Appendix
Table 12: CFN workload and runtime breakdown. Time shares use summed worker search time as the denominator for LPC-MCTS under the same evaluation setting as Table 11 .