betaFeedback

WorksComputer Science

MCTS Is Counting the Wrong Thing: Learning Exploration Counts for LLM Reasoning

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.

Introduction

Monte Carlo tree search (MCTS) is a powerful approach to sequential decision making ([21, 4]). By combining search with learned policies and value estimates, it helped enable landmark reinforcement learning systems such as AlphaGo ([36]). Its appeal extends naturally to large language models (LLMs): reasoning requires choosing among alternative plans, intermediate hypotheses, and tool calls, and search offers a way to revisit these choices before committing to an answer. A growing body of work has applied MCTS to LLM reasoning at inference time and during training ([15, 32, 41, 40] (Zhou et al. 2023; Zhang et al. 2026)). Meanwhile, methods such as Group Relative Policy Optimization (GRPO) obtain strong reasoning policies from groups of sampled responses without explicitly constructing search trees ([35]). For MCTS to offer a compelling alternative, its additional computation must translate into sufficiently better reasoning.

However, tree-search-based training can still yield only modest performance gains over GRPO-style methods ([40]). Zhao et al. (2026) report that tree-based approaches such as TreePO ([26]) perform comparably to GRPO and its variants. The DeepSeek-R1 report also highlights the difficulty of iteratively improving model performance through MCTS-based self-search ([14]). Together, these findings indicate that using a tree structure alone does not guarantee substantial gains in LLM reasoning. The effectiveness of exploration within the tree therefore remains an important question. With this in mind, our starting point is a component that is usually treated as routine bookkeeping: the visit count. We identify a mismatch between what MCTS counts and what language reasoning needs to explore. Our central finding is strikingly simple: changing only the exploration count is enough to produce substantial gains.

The issue arises from the meaning of a visit in a language search tree. UCT allocates exploration according to branch values and visit counts, giving larger exploration bonuses to less-visited branches [21]. When branches are identified by token sequences, however, different formulations of the same strategy receive independent counters. Repeatedly exploring one formulation does not increase the count of another. The counts therefore record textual branch visits accurately while failing to reflect how extensively a reasoning strategy has already been explored. We refer to this mismatch as count fragmentation. It allows familiar strategies to repeatedly appear novel and compete for exploration budget through different textual realizations.

Figure 1 illustrates this issue with an actual rollout-tree example. Branches AA and BB follow the same substitution-based derivation and reach the same quadratic, despite their different textual forms, whereas branch CC instead uses a product identity and symmetric sums. In standard UCT, although AA has already been explored 8 times, standard UCT treats the new branches BB and CC as equally unexplored because both have one exact visit. LPC-MCTS instead assigns similar pseudo-counts to AA and BB while separating CC, allowing the search to share evidence across the two related branches and prioritize the distinct reasoning pattern.

Figure 1. Motivation for LPC-MCTS. The parent and branches AA-CC are taken from an actual model rollout tree, and the displayed CϕC_{\phi} values are their learned pseudo-counts. Although branches AA and BB differ textually, they follow the same reasoning pattern and receive similar pseudo-counts, whereas CC follows a distinct pattern. Standard UCT instead treats BB and CC as equally unexplored because both have one exact visit. Additional rollout-tree examples are provided in Appendix § 13.1.2.

We address this problem with Learned Pseudo-Count MCTS (LPC-MCTS), which retains the UCT selection structure and replaces independent branch-local visit counts with learned pseudo-counts. These counts estimate representation coverage, allowing exploration evidence to be shared across related branches. We obtain them using a Coin-Flipping Network (CFN) [27], implemented as a lightweight auxiliary head on top of the policy’s existing hidden representations. The CFN head adds almost no computational overhead to standard MCTS. Evidence collected from one branch can thereby increase the estimated familiarity of related branches, reducing repeated exploration of already-covered reasoning patterns and directing search toward less-explored alternatives.

We evaluate LPC-MCTS on two agentic settings: tool-integrated mathematical reasoning and search. The results show that it improves task performance over the strong MCTS baseline, indicating that representation-level coverage provides a more informative basis for allocating search than independent counts over textual branches. Our contributions are as follows:

  • We introduce LPC-MCTS, a novel tree-search method that replaces independent branch counts with learned decision-level pseudo-counts, enabling search evidence to generalize across related LLM reasoning patterns, thereby reducing redundant exploration.

  • We theoretically characterize the exploration cost of count fragmentation through cumulative regret.

  • Our experiments on tool-integrated mathematical reasoning and search tasks demonstrate that LPC-MCTS improves task performance over strong MCTS baselines.

Preliminaries

MCTS and the role of counts

MCTS repeatedly allocates computation through four stages (Browne et al., [4]): (1) selection follows promising edges from the root; (2) expansion adds an unexplored child; (3) simulation estimates its outcome; and (4) backpropagation updates statistics along the selected path. Repeating these stages concentrates simulations on strong branches while reserving some budget for alternatives whose value remains uncertain.

Let node vv represent state svs_v, and let edge (v,a,va)(v, a, v_a) represent taking action aa and reaching child vav_a. In tool-augmented LLM reasoning, the state is the interaction history; an action may be a reasoning segment, a tool call, or a final answer, and a tool may append an external observation. Let Q(v,a)Q(v, a) be the backed-up value of action aa, N(v)N(v) the number of simulations through vv, and N(va)N(v_a) the number allocated to its child branch. The UCT algorithm (Kocsis & Szepesvári, [21]) selects

a∗=arg⁡max⁡a∈A(v)[Q(v,a)+clog⁡(N(v)+1)N(va)+ϵ](1)a^* = \underset{a \in A(v)}{\arg\max}\left[Q(v,a) + c\sqrt{\frac{\log(N(v)+1)}{N(v_a)+\epsilon}}\right] \tag*{(1)}

where c>0c > 0 controls exploration and ϵ>0\epsilon> 0 ensures numerical stability. The first term favors high estimated value; the second is an optimistic bonus that is larger for less-visited children.

Coin-Flipping Network

Exact visitation counts become uninformative in high-dimensional continuous spaces because nearly every state representation may be unique. Classical pseudo-count methods address this problem with learned density models (Bellemare et al., [3]; Ostrovski et al., [30]), but training and continually updating these models can be costly. A Coin-Flipping Network (CFN) provides a lighter alternative by reducing count estimation to random-label regression (Lobel et al., [27]). Whenever a representation hi∈RHh_i \in\mathbb{R}^{H} is observed, the CFN pairs it with a randomly sampled Rademacher vector zi∈{−1,+1}dz_i \in\{-1,+1\}^{d}, whose coordinates independently take either value with probability 1/21/2. Importantly, repeated occurrences receive different random targets. A predictor fϕ:RH→Rdf_{\phi}:\mathbb{R}^{H}\to\mathbb{R}^{d} is trained by minimizing the following objective:

LCFN(ϕ)=E(hi,zi)∼DCFN[∥fϕ(hi)−zi∥22](2)\mathcal{L}_{\mathrm{CFN}}(\phi)=\mathbb{E}_{(h_i,z_i)\sim\mathcal{D}_{\mathrm{CFN}}}\left[\left\|f_{\phi}(h_i)-z_i\right\|_2^2\right] \tag*{(2)}

where DCFN\mathcal{D}_{\mathrm{CFN}} contains the observed representation-target pairs. If the representation hh occurs nn times, mean-squared loss minimization predicts the mean of its targets, f∗(h)=1n∑i=1nzif^*(h)=\frac{1}{n}\sum_{i=1}^{n}z_i. Since each target coordinate is independent, zero-mean, and unit-variance,

E[1d∥f∗(h)∥22]=1n.(3)\mathbb{E}\left[\frac{1}{d}\left\|f^*(h)\right\|_2^2\right]=\frac{1}{n}. \tag*{(3)}

Thus, 1d∥fϕ(h)∥22\frac{1}{d}\left\|f_{\phi}(h)\right\|_2^2 estimates an inverse count: it shrinks as evidence accumulates. The dd coordinates estimate the same inverse count independently in this idealized solution, so averaging them reduces estimator variance. Taking its square root gives the CFN count-based bonus bϕ(h)=1d∥fϕ(h)∥22b_{\phi}(h)=\sqrt{\frac{1}{d}\left\|f_{\phi}(h)\right\|_2^2}, which scales as 1n\frac{1}{\sqrt{n}} under repeated observations.

Methodology

LPC-MCTS replaces the visit count with a learned pseudo-count that measures familiarity across model decisions. As shown in Figure 2, a CFN estimator computes this count from hidden representations, and the count directly determines the exploration bonus used for MCTS selection.

Overview of LPC-MCTS

Figure 2. Overview of LPC-MCTS, including CFN-based pseudo-count estimation, estimator training, tree selection, and pseudo-count-guided trajectory selection.

Learned decision-level pseudo-counts

CFN estimation and training. We attach a lightweight linear CFN head to the policy’s hidden representations. For h∈RHh \in\mathbb{R}^{H}, we compute

fϕ(h)=Wϕ⊤sg⁡(h),uϕ(h)=1d∥fϕ(h)∥22,(4)f_{\phi}(h) = W_{\phi}^{\top}\operatorname{sg}(h), \qquad u_{\phi}(h) = \frac{1}{d}\lVert f_{\phi}(h)\rVert_{2}^{2}, \tag*{(4)}

where Wϕ∈RH×dW_{\phi} \in\mathbb{R}^{H \times d} is trainable and sg⁡(⋅)\operatorname{sg}(\cdot) prevents the CFN loss from updating the policy backbone. Following Lobel et al. [27], we use uϕ(h)u_{\phi}(h) as a token-level inverse-count signal. During search, we collect representations at model-generated reasoning and tool-call positions, excluding prompt and tool-response tokens. Each observed occurrence hih_i is paired with a fresh, independently sampled Rademacher target zi∈{−1,+1}dz_i \in\{-1,+1\}^{d}. We train the head on minibatches BCFN\mathcal{B}_{\mathrm{CFN}} of the accumulated pairs using

LCFN(ϕ)=1∣BCFN∣∑(hi,zi)∈BCFN∥fϕ(hi)−zi∥22.(5)\mathcal{L}_{\mathrm{CFN}}(\phi) = \frac{1}{\lvert\mathcal{B}_{\mathrm{CFN}}\rvert}\sum_{(h_i,z_i)\in\mathcal{B}_{\mathrm{CFN}}}\lVert f_{\phi}(h_i)-z_i\rVert_{2}^{2}. \tag*{(5)}

From token scores to a node count. For a search node vv, let xv=(xv,1,…,xv,Lv)x_v=(x_{v,1},\ldots,x_{v,L_v}) denote its token sequence. We encode this sequence independently with the policy backbone gg and score each position with the trained CFN head fϕf_{\phi}:

hv,t=g(xv,≤t),uv,t=1d∥fϕ(hv,t)∥22.(6)h_{v,t}=g(x_{v,\leq t}), \qquad u_{v,t}=\frac{1}{d}\lVert f_{\phi}(h_{v,t})\rVert_{2}^{2}. \tag*{(6)}

By the definition above, uv,tu_{v,t} is the representation-level uncertainty at position tt. A larger score means that the CFN has accumulated less evidence for the represented state, making that position more important for exploration. Among the model-generated tokens in node vv, we retain the top-p%p\% with the largest uv,tu_{v,t}, so that the node statistic emphasizes the exploration signal from positions with relatively higher uncertainty. Since isolated high scores may be noisy, we partition the retained positions into contiguous runs and discard short runs that do not form coherent local segments. Let IvI_v be the union of the remaining runs. We then define

Uϕ(v)=1∣Iv∣∑t∈Ivuv,t,Cϕ(v)=1Uϕ(v)+ϵ.(7)U_{\phi}(v)=\frac{1}{\lvert I_v\rvert}\sum_{t\in I_v}u_{v,t}, \qquad C_{\phi}(v)=\frac{1}{U_{\phi}(v)+\epsilon}. \tag*{(7)}

Uϕ(v)U_{\phi}(v) summarizes uncertainty over coherent high-score regions. Cϕ(v)C_{\phi}(v) is the reciprocal of Uϕ(v)+ϵU_{\phi}(v)+\epsilon. We use it as a learned pseudo-count: a larger uncertainty score produces a smaller Cϕ(v)C_{\phi}(v) and thus, all else being equal, a larger exploration bonus in Eq. (8).

Pseudo-count-guided tree search

Constructing tree nodes. During expansion, we grow the search tree together with the generated trajectory and use token entropy as the signal for creating new nodes. After each tool response, the policy generates a probe window of ww tokens. Let H‾win\overline{H}_{\mathrm{win}} and H‾ctx\overline{H}_{\mathrm{ctx}} denote the mean token entropy over the probe window and the preceding context, respectively. We create a new node when H‾win>αH‾ctx\overline{H}_{\mathrm{win}} > \alpha\overline{H}_{\mathrm{ctx}}; otherwise, generation continues within the current node. Here, α>1\alpha> 1 controls the frequency of node branching, with a larger α\alpha leading to less frequent branching.

Shared rollout and tree values. During expansion, the behavior policy πθold\pi_{\theta_{\mathrm{old}}} generates candidate action segments. Repeated selection and expansion yield terminal trajectories. A verifier or reward model assigns each completed trajectory τ\tau an outcome reward R(τ)R(\tau), and these outcomes are used to maintain an action value Q(v,a)Q(v,a) for each expanded edge (v,a)(v,a).

UCT-style acquisition rule. At a node vv with expanded children, let Aactive(v)\mathcal{A}_{\mathrm{active}}(v) denote their actions and let vav_a be the child reached by action aa. We place the parent normalizer on the same learned scale as the child pseudo-counts by setting Mϕ(v)=∑a∈Aactive(v)Cϕ(va)M_{\phi}(v) = \sum_{a \in\mathcal{A}_{\mathrm{active}}(v)} C_{\phi}(v_a). LPC-MCTS selects

a∗=arg⁡max⁡a∈Aactive(v)[Q(v,a)+ccountlog⁡(Mϕ(v)+1)Cϕ(va)].(8)a^{*} = \underset{a \in\mathcal{A}_{\mathrm{active}}(v)}{\arg\max} \left[ Q(v,a) + c_{\mathrm{count}} \sqrt{\frac{\log(M_{\phi}(v)+1)}{C_{\phi}(v_a)}} \right]. \tag*{(8)}

By construction, at a fixed selection step, a larger node score Uϕ(va)U_{\phi}(v_a) gives a smaller Cϕ(va)C_{\phi}(v_a) and hence a larger exploration bonus.

Policy optimization from searched trajectories. Following the node-value formulation of DeepSearch (Wu et al., [40]) and group-relative reward normalization (Shao et al., [35]; Chu et al., [6]), we compute an action-level advantage from the corresponding tree value. Let Lx\mathcal{L}_x denote the terminal trajectories for prompt xx:

bx=1∣Lx∣∑τ∈LxR(τ),A(v,a)=Q(v,a)−bx.(9)b_x = \frac{1}{|\mathcal{L}_x|} \sum_{\tau\in\mathcal{L}_x} R(\tau), \qquad A(v,a) = Q(v,a) - b_x. \tag*{(9)}

Here Q(v,a)Q(v,a) denotes the tree value associated with edge (v,a)(v,a), and bxb_x is the prompt-level mean terminal outcome used as the baseline. All generated tokens in an action segment a=(y1,…,yLa)a = (y_1, \ldots, y_{L_a}) share this action-level advantage.

We optimize these action segments using the clipped surrogate objective of PPO (Schulman et al., [34]). For token tt, the importance ratio is rθ,t(v,a)=πθ(yt∣pv,y<t)πθold(yt∣pv,y<t)r_{\theta,t}(v,a) = \frac{\pi_{\theta}(y_t|p_v,y_{<t})}{\pi_{\theta_{\mathrm{old}}}(y_t|p_v,y_{<t})}, where pvp_v is the complete prefix at node vv. Following DAPO (Yu et al., 2025), we use separate lower and upper clipping ranges and average the surrogate over all trainable tokens:

Jpolicy(θ)=1∑(v,a)∈DtreeLa∑(v,a)∈Dtree∑t=1Lamin⁡(rθ,t(v,a)A(v,a),clip⁡(rθ,t(v,a),1−ϵlow,1+ϵhigh)A(v,a)).(10)\begin{aligned} \mathcal{J}_{\mathrm{policy}}(\theta) ={}& \frac{1}{\sum_{(v,a)\in\mathcal{D}_{\mathrm{tree}}} L_a} \sum_{(v,a)\in\mathcal{D}_{\mathrm{tree}}} \sum_{t=1}^{L_a} \min\bigl(r_{\theta,t}(v,a) A(v,a),\\ &\operatorname{clip}(r_{\theta,t}(v,a),1-\epsilon_{\mathrm{low}},1+\epsilon_{\mathrm{high}}) A(v,a)\bigr). \tag*{(10)} \end{aligned}

We additionally use dual clipping for negative advantages to limit extreme updates from large importance ratios, as detailed in Appendix § 8.§ 2. LPC-MCTS influences policy learning through exploration: the pseudo-count changes which branches are searched and hence which action segments enter Dtree\mathcal{D}_{\mathrm{tree}}, while empirical visits remain in use for value averaging.

Pseudo-count-guided trajectory selection

Let Cx={τ1,…,τK}\mathcal{C}_x = \{\tau_1,\ldots,\tau_K\} be the candidate pool of completed trajectories for prompt xx, and let V(τ)\mathcal{V}(\tau) denote the set of nodes on trajectory τ\tau. For trajectory comparison, node scores within a candidate pool are evaluated against a shared reference state of fϕf_{\phi}. We define the pseudo-count of a trajectory as the mean of its node-level pseudo-counts:

C‾ϕ(τ)=1∣V(τ)∣∑v∈V(τ)Cϕ(v),Bx=arg⁡min⁡B⊆Cx∣B∣=B∑τ∈BC‾ϕ(τ).(11)\overline{C}_{\phi}(\tau) = \frac{1}{|\mathcal{V}(\tau)|} \sum_{v \in\mathcal{V}(\tau)} C_{\phi}(v), \qquad\mathcal{B}_x = \underset{\substack{\mathcal{B} \subseteq\mathcal{C}_x \\ |\mathcal{B}|=B}}{\arg\min} \sum_{\tau\in\mathcal{B}} \overline{C}_{\phi}(\tau). \tag*{(11)}

We sort CxC_x by C‾ϕ(τ)\overline{C}_{\phi}(\tau) in ascending order and pass the first BB trajectories, denoted by Bx\mathcal{B}_x, to policy optimization. This rule prioritizes trajectories that pass through underexplored decisions. It thereby extends pseudo-count-guided exploration from tree expansion to training-batch construction.

How Count Fragmentation Impairs Exploration

We next analyze how count fragmentation affects exploration efficiency. We quantify this effect through cumulative regret, a standard criterion in online learning that measures the reward lost relative to always selecting an optimal action [1, 23]. We begin with the simplest setting, a one-step decision problem modeled as a stochastic bandit, and show that count fragmentation already incurs an additional exploration cost.

Consider a fixed finite bandit with K≥2K \ge2 groups of actions. Within each group, actions are distinct choices but yield rewards from the same distribution. Let CcC_c denote group cc, containing mc=∣Cc∣m_c = |C_c| actions. Rewards lie in [0,1][0,1], are independent across pulls, and have mean μc\mu_c for every action in group cc. Assume group 1 contains the unique optimal action, so m1=1m_1 = 1 and μ1>μc\mu_1 > \mu_c for all c≥2c \ge2. Let Δc=μ1−μc\Delta_c = \mu_1 - \mu_c denote the reward gap of a suboptimal group. For actions A1,…,ATA_1, \ldots, A_T selected over TT rounds, the expected cumulative regret is R(T)=E[∑t=1T(μ1−μc(At))]=∑c=2KΔcE[Nc(T)]R(T) = \mathbb{E}\left[\sum_{t=1}^{T}(\mu_1 - \mu_{c(A_t)})\right] = \sum_{c=2}^{K}\Delta_c \mathbb{E}[N_c(T)], where c(a)c(a) identifies the group containing action aa, and Nc(T)N_c(T) counts all selections of actions in group cc. Regret therefore measures the sampling budget spent on suboptimal actions, weighted by their reward gaps.

Independent versus shared counts. Let Na(t)N_a(t) and μ^a(t)\hat{\mu}_a(t) denote the visit count and empirical mean of action aa after tt rounds, and define the class count as Nc(t)=∑a∈CcNa(t)N_c(t) = \sum_{a \in C_c} N_a(t). We compare two UCB rules that differ only in their exploration counts. Standard UCB1 uses Iind(a,t)=μ^a(t−1)+2log⁡t/Na(t−1)I_{\mathrm{ind}}(a,t) = \hat{\mu}_a(t-1) + \sqrt{2\log t/N_a(t-1)}, whereas the shared-count variant uses Ishare(a,t)=μ^a(t−1)+2log⁡t/Nc(a)(t−1)I_{\mathrm{share}}(a,t) = \hat{\mu}_a(t-1) + \sqrt{2\log t/N_{c(a)}(t-1)}. Both sample every action once before selecting actions with the largest index. Each action retains its own empirical mean, computed only from its observed rewards; only the exploration counts are shared.

Theorem 1 (Regret penalty of count fragmentation). For the bandit and selection rules defined above, as T→∞T \to\infty,

Rind(T)=2log⁡T∑c=2KmcΔc+o(log⁡T),Rshare(T)=2log⁡T∑c=2K1Δc+o(log⁡T).(12)R_{\mathrm{ind}}(T) = 2\log T \sum_{c=2}^{K}\frac{m_c}{\Delta_c} + o(\log T), \qquad R_{\mathrm{share}}(T) = 2\log T \sum_{c=2}^{K}\frac{1}{\Delta_c} + o(\log T). \tag*{(12)}

In particular, if every suboptimal class contains mm equivalent actions, then Rind(T)/Rshare(T)→mR_{\mathrm{ind}}(T)/R_{\mathrm{share}}(T) \to m.

Independent counts therefore repeat the same logarithmic exploration cost across equivalent actions, increasing regret even when rewards are deterministic. The proof and a finite-time bound are provided in Appendix § 9.

Extension to tree search. We extend our analysis to recursive UCT with terminal-reward backup and obtain a similar regret separation. In the tree setting, the leading exploration costs accumulate along the optimal path, with independent counts paying separately for each equivalent action. When every suboptimal class on this path contains mm equivalent actions, independent-count UCT incurs mm times the leading cumulative regret of shared-count UCT, while both retain separate action-value estimates. The formal statement (Theorem 2), assumptions, and proof are provided in Appendix § 10.

Related Work

Tree-structured search for LLM agents. Tree of Thoughts and RAP formulate language reasoning as explicit search over intermediate states [15] (Yao et al. 2023a), while ReAct and LATS extend this view to agents that interleave reasoning, actions, and environmental observations (Yao et al., 2023b; Zhou et al., 2023). Subsequent work augments tree search with tool-aware feedback, reflective simulation, safe pruning, adaptive lookahead, and multi-agent reasoning [33, 25] (Yang et al. 2026; Zhang et al. 2026c; Zhang et al. 2026a). Recent training-time methods use the tree structure to obtain backed-up node values or fine-grained relative advantages, improving rollout efficiency and credit assignment [40, 17, 26]. LPC-MCTS addresses a complementary question: how exploration evidence should be represented during tree selection. Some methods reduce redundant exploration through embedding-based clustering and merging of semantically similar search states. For instance, FETCH uses a separate embedding model to form these clusters [38]. Compared with this class of explicit clustering methods, LPC-MCTS requires neither an additional embedding model nor online clustering. Its lightweight CFN head operates on the policy’s existing hidden representations and is updated with states collected during rollouts. The pseudo-count therefore reflects how familiar a state is under the current policy after accumulated rollout visitation and enters tree selection directly.

Count-based exploration beyond tabular spaces. UCT treats the visit count as the evidence supporting a branch [21]. Exact counts are effective when search repeatedly reaches the same discrete states, but language trees contain many low-visit nodes whose textual forms differ even when their reasoning content is similar. Generalized pseudo-counts address this problem in large observation spaces by replacing exact identity with learned density or representation-level recurrence [3, 30]. Coin-Flipping Networks (CFNs) estimate such recurrence through random-label regression, avoiding an explicit normalized density model [27]. Recent work has brought these exploration signals to LLM training. COPO uses a CFN pseudo-count over prompt–response pairs for optimistic preference alignment [2], while MERCI applies token-level CFN scores as intrinsic rewards for diverse reasoning trajectories (Zhang et al., 2026b). CDE instead combines actor surprise with critic disagreement [8]. These methods shape policy learning after responses are sampled, whereas LPC-MCTS uses the learned pseudo-counts directly during tree selection.

Experiments

To evaluate whether learned pseudo-counts improve exploration and final task performance, we study LPC-MCTS in two agentic settings: tool-integrated mathematical reasoning and search.

Experimental Setup

Tool-integrated mathematical reasoning. We use Qwen2.5-7B [42] and Qwen3-4B [42] as policy backbones. Both models are initialized with the same ReTool SFT dataset [11]. For RL training, we use DAPO-Math-17K (Yu et al., 2025). We evaluate on AIME 2024/2025/2026 [28], as well as HMMT February 2025 and BRUMO 2025 from MathArena [9]. For each problem, we sample 16 responses with temperature T=0.6T = 0.6 and top-p=0.95p = 0.95, and report their mean accuracy (mean@16).

Search. We use Qwen2.5-7B-Instruct and Llama-3.2-3B-Instruct [13] as policy backbones. Both models are initialized by SFT on the same 2,000 examples sampled from the dataset constructed by [24]. Following [18], our RL training set consists of the training splits of NQ [22] and HotpotQA (Yang et al., 2018). We evaluate our training paradigm on 7 search-augmented QA tasks, including single-hop QA datasets (NQ, TriviaQA [19], and PopQA [29]) and multi-hop QA datasets (HotpotQA, 2Wiki (Ho et al., 2020), MuSiQue [37], and Bamboogle [31]). We use offline retrieval over the 2018 Wikipedia corpus [20] using E5-base-v2 embeddings [39], and return the top-3 documents for each query. We evaluate each question with greedy sampling and MCTS. For MCTS, we set the temperature T=0.6T = 0.6 and top-p=0.95p = 0.95, and report the mean accuracy over 5 responses per question (mean@5).

Baselines and configurations. We use DAPO as our policy-optimization baseline and additionally include three exploration-oriented methods. Cheng et al. [5] encourage exploration through entropy-based advantage shaping; this baseline is denoted as DAPO + Entropy. Gao et al. [12] use random network distillation (RND)-based intrinsic rewards for exploration; this baseline is denoted as DAPO + IMAGINE. Zhang et al. (2026b) uses CFN-based intrinsic rewards to encourage exploration of unfamiliar reasoning trajectories; this baseline is denoted as DAPO + MERCI. We compare these baselines with standard visit-count MCTS and LPC-MCTS, which jointly trains the policy and CFN head. During tree search, standard MCTS uses discrete visit counts, whereas LPC-MCTS replaces them with CFN-estimated pseudo-counts. At inference time, the CFN head is frozen, so its pseudo-counts reflect coverage learned during training and do not update with test-time visits. For MCTS-based inference, motivated by the use of self-consistency-derived terminal rewards for MCTS backup in RStar [32], we assign terminal rewards through answer consistency without using reference answers. After adding each terminal node, we group all terminal nodes by their final answers, assign +1+1 to nodes in the current majority group and −1-1 to the others, and recompute the backed-up QQ-values throughout the tree. Details are provided in Appendix § 12.

Analysis of the Learned CFN Head

Token-level uncertainty visualization. Within each selected response, we visualize how the CFN score uv,tu_{v,t} of every eligible generated token changes across the sequence. The visualizations and corresponding analysis are provided in Appendix § 13.1.1. Across these examples, high scores cluster on novel reasoning patterns, such as introducing a new solution strategy, applying a theorem, correcting an earlier step, reformulating a query, or integrating evidence into an answer. In contrast, common connecting text and simple calculations or routine queries receive lower scores. The high values also extend across groups of nearby tokens rather than appearing as isolated spikes. Together, these observations suggest that the learned CFN head assigns higher uncertainty to novel high-level reasoning patterns in both mathematical reasoning and search, rather than isolated token differences. This behavior directly supports our learned pseudo-count: Eq. (7) maps less-familiar reasoning spans with larger Uϕ(v)U_{\phi}(v) to a smaller Cϕ(v)C_{\phi}(v) and thus a larger exploration bonus in Eq. (8), while familiar patterns receive larger learned counts and less exploration.

Reasoning-pattern sensitivity. To test whether the learned pseudo-count captures reasoning-pattern similarity during search, we sample some sibling groups from actual model rollout trees. In each group, two textually different children follow the same or a closely related reasoning pattern, while a third child takes a distinct approach. The two pattern-aligned children receive closely matched pseudo-counts, whereas the distinct child is separated from both by a markedly larger gap. This separation indicates that the estimator responds to changes in reasoning pattern rather than surface-level wording alone. In these cases, the distinct child also receives a lower pseudo-count and therefore a larger exploration bonus in Eq. (8). The complete cases are analyzed in Appendix § 13.1.2. These results qualitatively support the motivation in Figure 1: discouraging redundant expansion of familiar patterns while preserving exploration for distinct strategies.

Quantitative analysis of evidence sharing. We quantify semantic alignment and count transfer in mathematical reasoning using Qwen3-4B and Qwen2.5-7B in Appendix § 13.1.3. Pseudo-count closeness correlates positively with embedding similarity (ρ=0.248\rho= 0.248–0.3580.358), and nearest-neighbor agreement reaches 24.1–29.2%, above the 14.3% uniform-random baseline. These correlations suggest that learned pseudo-counts provide an exploration signal that is related to semantic similarity but does not fully match it. In the transfer evaluation, 16 CFN updates on one branch increase the pseudo-counts of held-out same-pattern siblings by 5.5%, while those of distinct-pattern siblings decrease by 3.2%. Together, these results support the use of learned pseudo-counts to share exploration evidence across related reasoning branches.

Main Results

Mathematical reasoning. Table 1 shows that LPC-MCTS achieves the highest average performance on both backbones when used during both training and inference, improving over standard MCTS by 4.96 points on Qwen2.5-7B and 4.37 points on Qwen3-4B. Holding each LPC-MCTS-trained policy fixed, replacing discrete visit counts with learned pseudo-counts at inference yields further gains of 3.79 and 2.71 points, isolating the benefit of LPC-MCTS during test-time search. Under standard MCTS evaluation, LPC-MCTS-trained policies also outperform the strongest alternative training method by 0.87 and 1.66 points. The consistent improvements across both backbones and both stages provide strong empirical support that mitigating count fragmentation benefits test-time exploration and the collection of trajectories for policy optimization.

Table | Training | Inference | AIME 24 | AIME 25 | AIME 26 | HMMT25 | BRUMO25 | Avg.

Qwen2.5-7B
SFTDirect sampling9.588.548.134.1719.5810.00
SFTMCTS10.4212.088.5410.0021.0412.42
DAPODirect sampling24.5823.3320.219.3830.6321.63
DAPOMCTS29.7927.7123.3316.2540.6327.54
DAPO + EntropyDirect sampling27.0822.9223.9612.2933.3323.92
DAPO + EntropyMCTS30.4227.50<u>26.25</u>14.1742.0828.08
DAPO + IMAGINEDirect sampling24.3821.4620.2110.8332.0821.79
DAPO + IMAGINEMCTS28.3326.4623.9616.0441.8827.33
DAPO + MERCIDirect sampling25.4223.5422.2912.9233.3323.50
DAPO + MERCIMCTS<u>32.29</u>28.7525.2114.3840.0028.13
MCTSDirect sampling25.2123.7521.0411.2530.4222.33
MCTSMCTS28.3327.5026.0415.2142.0827.83
LPC-MCTSDirect sampling26.6724.3822.0813.3334.7924.25
LPC-MCTSMCTS30.83<u>29.17</u>25.42<u>17.08</u><u>42.50</u><u>29.00</u>
LPC-MCTSLPC-MCTS37.0830.6327.9223.3345.0032.79
Qwen3-4B
SFTDirect sampling40.4228.3325.4220.6337.5030.46
SFTMCTS36.4625.0018.9616.8839.5827.38
DAPODirect sampling59.5851.4654.1736.2558.3351.96
DAPOMCTS71.8857.5059.3847.9261.6759.67
DAPO + EntropyDirect sampling60.6353.3355.8335.6361.4653.38
DAPO + EntropyMCTS69.1756.0464.1743.9668.3360.33
DAPO + IMAGINEDirect sampling62.9249.3857.2937.0858.7553.08
DAPO + IMAGINEMCTS69.5855.4261.4649.3865.4260.25
DAPO + MERCIDirect sampling63.1352.2958.3335.6359.7953.83
DAPO + MERCIMCTS70.8357.9260.8349.1761.4660.04
MCTSDirect sampling60.8352.2957.5035.8360.0053.29
MCTSMCTS<u>73.75</u>56.4665.0050.2165.2162.13
LPC-MCTSDirect sampling62.7153.1358.1336.6759.3854.00
LPC-MCTSMCTS71.25<u>59.17</u><u>74.38</u><u>50.63</u>63.54<u>63.79</u>
LPC-MCTSLPC-MCTS78.1363.54<u>72.92</u>51.88<u>66.04</u>66.50

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 <u>underlined</u> represents the second best.

Search. Table 2 shows improvements on search. Using LPC-MCTS at both stages improves over standard MCTS by 2.26 points on Qwen2.5-7B-Instruct and 1.71 points on Llama-3.2-3B-Instruct. Holding the policy fixed, LPC-MCTS improves test-time MCTS by 0.58 and 0.45 points, while LPC-MCTS training improves MCTS evaluation by 1.52 and 1.02 points over the strongest alternatives. Compared with mathematical reasoning, however, these gains are more modest. The logged trees provide one explanation: among 256 sampled trees per task, search covers 1.82 effective first-level branches on average, compared with 4.05 for mathematical reasoning. This narrower structure suggests that search is simpler in our setting and tends to follow more standardized solution strategies, leaving fewer competing branches across which pseudo-counts can share exploration evidence.

TrainingInferenceNQTriviaQAPopQAHotpotQA2WikiMuSiQueBamboogleAvg.
Qwen2.5-7B-Instruct
SFTGreedy sampling36.8054.4025.8043.2038.6029.2046.4039.20
SFTMCTS36.9653.8425.2442.8042.9229.7247.5239.86
DAPOGreedy sampling43.4055.6039.6046.0043.6031.2046.4043.69
DAPOMCTS45.4856.6442.4845.9640.0431.4448.0044.29
DAPO + EntropyGreedy sampling44.6057.6041.0044.6044.6031.4048.0044.54
DAPO + EntropyMCTS46.0856.5640.6846.0840.0832.0048.9644.35
DAPO + IMAGINEGreedy sampling44.4056.6040.6044.2042.4032.2050.4044.40
DAPO + IMAGINEMCTS46.8056.5240.1246.0439.5632.4447.5244.14
DAPO + MERCIGreedy sampling43.8057.0041.6045.6043.0031.4048.0044.34
DAPO + MERCIMCTS45.2857.2441.4046.0842.2832.5248.3244.73
MCTSGreedy sampling42.4058.0041.6046.2043.0031.6046.4044.17
MCTSMCTS45.4458.2440.8046.2842.8831.1647.2044.57
LPC-MCTSGreedy sampling44.4057.0042.0048.0043.2033.4048.8045.26
LPC-MCTSMCTS45.3258.5642.3248.2046.0833.1650.0846.25
LPC-MCTSLPC-MCTS46.9258.4842.1247.9646.8834.2451.2046.83
Llama-3.2-3B-Instruct
SFTGreedy sampling39.4051.6026.2039.4035.2027.6047.2038.09
SFTMCTS38.1252.4026.8840.1635.6825.7645.9237.85
DAPOGreedy sampling44.4055.0036.6044.6036.8030.8047.2042.20
DAPOMCTS44.5255.9237.9245.0839.0430.3246.2442.72
DAPO + EntropyGreedy sampling45.6055.0040.0045.0038.4031.4046.4043.11
DAPO + EntropyMCTS46.5255.8040.8045.6837.6832.0045.9243.49
DAPO + IMAGINEGreedy sampling44.0055.2040.8044.8040.0030.4047.2043.20
DAPO + IMAGINEMCTS46.3255.7640.7244.5639.2831.4047.5243.65
DAPO + MERCIGreedy sampling45.2056.0040.8044.6038.2030.8046.4043.14
DAPO + MERCIMCTS45.2456.2041.4844.6840.9230.7646.7243.71
MCTSGreedy sampling45.2055.4038.8044.0043.2028.6048.0043.31
MCTSMCTS45.2856.0439.8044.5640.2830.0448.3243.47
LPC-MCTSGreedy sampling45.0056.8043.0046.0040.4030.4048.8044.34
LPC-MCTSMCTS47.1656.0041.8847.1241.6830.9248.3244.73
LPC-MCTSLPC-MCTS46.8056.1641.8447.4042.2831.7250.0845.18

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=0T = 0 and MCTS with temperature T=0.6T = 0.6.

The ablations in Appendix § 13.§ 2.2 show that pseudo-count-guided trajectory selection and token-to-node aggregation both improve performance, while the sensitivity results in Appendix § 13.2.3 favor p=30p = 30 on both backbones. Overall, LPC-MCTS improves performance in both domains. The larger gains in mathematical reasoning are consistent with richer branching, where learned pseudo-counts can better distinguish novel paths and share exploration evidence across related branches. An inference-time cost analysis is provided in Appendix § 13.§ 3.

Conclusion

We identify count fragmentation as a key limitation of MCTS for LLM reasoning: textually different branches can follow the same reasoning pattern while retaining independent visit counts. We introduce LPC-MCTS, which replaces exact UCT visits with pseudo-counts from a lightweight CFN head and prioritizes less-covered trajectories for policy optimization. Our theory quantifies the additional exploration cost caused by fragmented counts. Across mathematical reasoning and search tasks, LPC-MCTS consistently improves over standard MCTS, while its learned counts align across related patterns and distinguish novel ones, showing that representation-level familiarity provides a more effective basis for exploration than textual branch identity.

Algorithm 1 LPC-MCTS training with learned pseudo-counts

Input: Policy πθ\pi_\theta, prompt dataset D\mathcal{D}, verifier RR, training iterations NN, candidate limit Kmax⁡≥BK_{\max} \ge B, selected batch size BB.

  1. Initialize CFN head fϕf_\phi randomly.

  2. for i=1i = 1 to NN do

  3. Sample a prompt batch Di\mathcal{D}_i from D\mathcal{D}.

  4. Initialize the policy-training set Dtree←∅\mathcal{D}_{\mathrm{tree}} \leftarrow\varnothing.

  5. for each prompt x∈Dix \in\mathcal{D}_i do

  6. Initialize search-tree root v0v_0 and terminal pool Cx←∅C_x \leftarrow\varnothing.

  7. while ∣Cx∣<Kmax⁡|C_x| < K_{\max} do

  8. Select a path from v0v_0 using Eq. (8), and expand its frontier node with πθold\pi_{\theta_{\mathrm{old}}}.

  9. Continue tree expansion until obtaining a terminal trajectory τ\tau.

  10. During the rollout, construct decision nodes with the entropy rule and compute their pseudo-counts using Eq. (7).

  11. Evaluate R(τ)R(\tau), update the tree statistics, and add τ\tau to CxC_x.

  12. Store the collected representations and newly sampled Rademacher targets, and periodically update fϕf_\phi using the newly collected samples.

  13. end while

  14. Select the BB least-covered trajectories from CxC_x using Eq. (11).

  15. Compute bxb_x and A(v,a)A(v,a) using Eq. (9), and add the selected action segments to Dtree\mathcal{D}_{\mathrm{tree}}.

  16. end for

  17. Update πθ\pi_\theta with the clipped objective in Eq. (10).

  18. end for

Output: Optimized policy πθ\pi_\theta and online CFN head fϕf_\phi.

Addition descriptions for our method

Algorithmic Description of our method

The complete LPC-MCTS procedure is summarized in Algorithm 1. The learned count enters the search policy, while terminal outcomes provide the learning signal for policy optimization. The CFN head is trained online and retained throughout policy training, sharing the evidence accumulated across prompts.

Policy Optimization Details

Unless stated otherwise, the following choices are shared by all compared search variants.

Bounded MCTS iterations. Rollout lengths and tool-interaction costs can vary substantially across prompts, so unconstrained tree search may lead to excessively long rollouts and unpredictable training time. To keep the computational cost bounded, we set a maximum number of MCTS iterations, denoted by TT, for each prompt. Once this limit is reached, we stop expanding the search tree and proceed to policy optimization using the trajectories collected so far. We set this practical runtime budget to T=24T = 24 during training and T=128T = 128 during evaluation.

Task- and model-specific advantage adaptation. For some model–task combinations, including Qwen2.5-7B on tool-integrated mathematical reasoning, we observe that RL can weaken tool-use behavior acquired during SFT. We therefore apply a small, bounded format-aware adjustment to the policy advantage to encourage valid tool use, with scale δ=0.1\delta= 0.1. This training adaptation is separate from the LPC-MCTS exploration rule.

Clipping and loss aggregation. Search trajectories are generated by πθold\pi_{\theta_{\mathrm{old}}} and then reused to update πθ\pi_\theta. As the two policies diverge, large importance ratios can produce unstable gradients, especially for actions with negative advantages. We control these updates with the asymmetric clipping ranges ϵlow=0.2\epsilon_{\mathrm{low}} = 0.2 and ϵhigh=0.28\epsilon_{\mathrm{high}} = 0.28 in Eq. (10), together with a dual-clipping floor cdual=10c_{\mathrm{dual}} = 10 for negative advantages (Ye et al., 2020). Because trajectories have different lengths, we average the surrogate terms over all trainable model-generated tokens in the batch so that longer trajectories do not receive disproportionate weight. Tool-response tokens are environment outputs rather than policy actions and are therefore excluded from optimization. We use neither a KL penalty nor an entropy bonus.

Trajectory candidate selection. LPC-MCTS assigns every completed trajectory in Cx\mathcal{C}_x the mean node pseudo-count in Eq. (11) and ranks the full candidate pool in ascending order. All node scores used by this ranking are recorded under the candidate pool’s shared reference state. The first BB trajectories form Bx\mathcal{B}_x and provide the trainable samples for policy optimization. For tool-integrated mathematical reasoning, we set Kmax⁡=12K_{\max}=12 and B=8B=8; for search task, we set Kmax⁡=8K_{\max}=8 and B=5B=5.

Node Construction and Token Aggregation

As introduced in § 3.2, ww denotes the number of newly generated probe tokens used to decide whether to create a node after a tool response. The coefficient α>1\alpha>1 is the multiplicative threshold that compares the probe window’s mean token entropy with that of the preceding context: a new node is created when the former exceeds α\alpha times the latter. We use w=16w=16 and α=2.0\alpha=2.0.

Token filtering and aggregation. The CFN encoder receives only the current node segment. Its score mask excludes prompt, padding, and tool-response positions. Among eligible positions within each node, we set p=30p=30 and retain the top p%p\% by uv,tu_{v,t}, then partition their indices into maximal contiguous runs. Every run of at least two tokens is kept, and IvI_v is the union of the tokens in all such runs. If no run reaches the minimum length, the highest-scoring eligible token is used as a singleton fallback. We average the inverse-count scores of all tokens in IvI_v to obtain Uϕ(v)U_\phi(v), then apply Eq. (7).

CFN Training and Shared-Backbone Execution

Representations collected by the search worker are paired with Rademacher targets and processed in vectorized minibatches. Eligibility masks are applied before pairs enter the training set, so environment outputs are not encoded as random-label training examples. The lightweight linear head is optimized with the CFN regression objective and evaluated over token-level representations collected within nodes in vectorized batches.

Each completed simulation contributes the eligible representations along its selected path, paired with independently sampled Rademacher targets. New samples are accumulated between updates and used to update the CFN head every 4 MCTS iterations. The head is initialized once at the beginning of policy training; its parameters persist across prompts and policy-training steps. Its pseudo-counts therefore reflect the policy model’s accumulated evidence over the entire training process.

Shared-backbone execution. The CFN and policy share the same LLM backbone and SGLang engine, which avoids loading and storing a separate backbone for CFN, and removes the need to swap between separate policy and CFN backbone instances. During tree search, policy rollouts benefit from prefix KV-cache reuse. CFN feature extraction performs a prefill over the node-local segment to obtain the token-level hidden states required for scoring. Its additional cost merely consists of this feature extraction and lightweight head evaluation.

Proof of the regret cost of fragmented counts

We prove Theorem 1 in this section. Our finite-time bound adapts the classical UCB analysis (Auer et al., [1]), while our asymptotic argument follows the proof strategy of Fan & Glynn [10]. We extend these arguments to shared exploration counts while retaining separate action-level empirical means. This requires controlling estimation errors using each action’s own samples and establishing consistency of the maximum empirical mean within each counting unit.

Setup and a common form of the two algorithms

We use the action groups defined in § 4: each group Cc\mathcal{C}_c contains mcm_c distinct actions with the same reward distribution. Let M=∑c=1KmcM=\sum_{c=1}^{K}m_c be the total number of actions. For each a∈Cca\in\mathcal{C}_c, let (Xa,n)n≥1(X_{a,n})_{n\geq1} be its potential reward sequence, with Xa,n∼PcX_{a,n}\sim P_c, PcP_c supported on [0,1][0,1], and mean μc\mu_c. All these reward variables are mutually independent. The nn-th selection of aa reveals Xa,nX_{a,n}. Write

X‾a,n=1n∑i=1nXa,i,μ^a(t)=X‾a,Na(t).\overline{X}_{a,n}=\frac{1}{n}\sum_{i=1}^{n}X_{a,i},\qquad\widehat{\mu}_a(t)=\overline{X}_{a,N_a(t)}.

Both algorithms select every action once during the first MM rounds and then follow the UCB rules in § 4. All counts and empirical means refer to the respective algorithm’s own history. The shared-count rule is given the action grouping, but neither rule is given the reward means or the identity of the optimal action. Each action’s empirical mean uses only its own observed rewards.

To analyze both rules together, call a set of actions that share one exploration counter a counting unit. Under independent-count UCB, each action forms its own unit; under shared-count UCB, all actions in Cc\mathcal{C}_c form one unit. Thus, an action group contains mcm_c counting units under the first rule and one under the second. For a counting unit g⊆Ccg \subseteq\mathcal{C}_c, define

Sg(t)=∑a∈gNa(t),Gg(t)=max⁡a∈gμ^a(t).(13)S_g(t) = \sum_{a \in g} N_a(t), \qquad G_g(t) = \max_{a \in g} \widehat{\mu}_a(t). \tag*{(13)}

The largest index in gg is

Jg(t)=Gg(t−1)+2log⁡tSg(t−1).(14)J_g(t) = G_g(t-1) + \sqrt{\frac{2 \log t}{S_g(t-1)}}. \tag*{(14)}

Thus, each algorithm selects a unit maximizing Jg(t)J_g(t) and then an action attaining Gg(t−1)G_g(t-1). This is an exact rewriting of the action-level rule, not a replacement of local values by a pooled estimate. Let

ρcind=mc,ρcshare=1\rho_c^{\mathrm{ind}} = m_c, \qquad\rho_c^{\mathrm{share}} = 1

denote the number of counting units in action group cc. The unique optimal action, denoted ⋆\star, forms a unit by itself under both rules.

A finite-time bound

For B∈{ind,share}B \in\{\mathrm{ind}, \mathrm{share}\}, every T≥MT \ge M, every suboptimal action group cc, and every ε∈(0,Δc)\varepsilon\in(0, \Delta_c), we first show that

EB[Nc(T)]≤mc+ρcB⌈2log⁡T(Δc−ε)2⌉+mce2ε2−1+2.(15)\mathbb{E}_B[N_c(T)] \le m_c + \rho_c^B \left\lceil\frac{2 \log T}{(\Delta_c-\varepsilon)^2} \right\rceil+ \frac{m_c}{e^{2\varepsilon^2}-1} + 2. \tag*{(15)}

At round t>Mt > M, let

Et={μ^⋆(t−1)+2log⁡tN⋆(t−1)<μ1}E_t = \left\{ \widehat{\mu}_{\star}(t-1) + \sqrt{\frac{2 \log t}{N_{\star}(t-1)}} < \mu_1 \right\}

be the event that the optimal index underestimates its mean. By Hoeffding’s inequality ([16]) and a union bound over the possible sample counts,

Pr⁡(Et)≤∑n=1t−1Pr⁡(X‾⋆,n<μ1−2log⁡tn)≤(t−1)t−4≤t−3.(16)\begin{aligned} \Pr(E_t) \le\sum_{n=1}^{t-1} \Pr\left(\overline{X}_{\star,n} < \mu_1 - \sqrt{\frac{2 \log t}{n}}\right) \\ &\le(t-1)t^{-4} \le t^{-3}. \tag*{(16)} \end{aligned}

In particular, ∑t=M+1∞Pr⁡(Et)<2\sum_{t=M+1}^{\infty} \Pr(E_t) < 2. The union bound handles adaptive sampling without assuming that an empirical mean is independent of its random sample count.

Fix cc, TT, and ε\varepsilon, and set

Lc=⌈2log⁡T(Δc−ε)2⌉.L_c = \left\lceil\frac{2 \log T}{(\Delta_c-\varepsilon)^2} \right\rceil.

Suppose action a∈g⊆Cca \in g \subseteq\mathcal{C}_c is selected at t≤Tt \le T with Sg(t−1)≥LcS_g(t-1) \ge L_c. Its exploration bonus is at most Δc−ε\Delta_c-\varepsilon. Outside EtE_t, its index must be at least μ1\mu_1, so

μ^a(t−1)≥μc+ε.(17)\widehat{\mu}_a(t-1) \ge\mu_c+\varepsilon. \tag*{(17)}

Every such selection increases the selected action’s own count. Therefore, each pair (a,n)(a,n), where n=Na(t−1)n=N_a(t-1), can account for at most one selection. The expected number of selections satisfying Eq. equation 17 is consequently bounded by

∑a∈Cc∑n=1T−1Pr⁡(X‾a,n≥μc+ε)≤mc∑n=1∞e−2nε2=mce2ε2−1.(18)\begin{aligned} \sum_{a \in\mathcal{C}_c} \sum_{n=1}^{T-1} \Pr(\overline{X}_{a,n} \ge\mu_c+\varepsilon) \le m_c \sum_{n=1}^{\infty} e^{-2n\varepsilon^2} \\ &= \frac{m_c}{e^{2\varepsilon^2}-1}. \tag*{(18)} \end{aligned}

There are mcm_c initialization selections and at most ρcBLc\rho_c^B L_c subsequent selections with the counting unit’s count below LcL_c. Adding these terms and the expected number of EtE_t events proves Eq. equation 15. Crucially, every concentration bound uses the selected action’s actual local sample size; the shared count is never treated as the sample size of a local empirical mean.

Taking ε=Δc/2\varepsilon= \Delta_c/2, using ex−1≥xe^x - 1 \ge x and ⌈x⌉≤x+1\lceil x\rceil\le x + 1, and applying the regret decomposition in § 4 gives

RB(T)≤∑c=2K[8ρcBlog⁡TΔc+2mcΔc+(mc+ρcB+2)Δc].(19)R_B(T) \le\sum_{c=2}^{K} \left[\frac{8\rho_c^B \log T}{\Delta_c} + \frac{2m_c}{\Delta_c} + (m_c+\rho_c^B+2)\Delta_c\right]. \tag*{(19)}

Hence, for each action group, the dependence improves from mclog⁡Tm_c \log T to log⁡T+mc\log T + m_c, up to gap-dependent factors. The additive dependence on mcm_c accounts for initialization and errors in the separate empirical values. Comparing these upper bounds alone would not establish an actual regret separation; we prove the matching asymptotic statements next.

Exact asymptotics

Proof of Theorem 1. Every counting unit is selected infinitely often. Suppose some unit has a finite limiting count. Since its count is integer-valued and nondecreasing, it eventually stops being selected. For every unit, Gg(t)∈[0,1]G_g(t) \in[0,1], and

Jg(t)2log⁡t=Gg(t−1)2log⁡t+1Sg(t−1).\frac{J_g(t)}{\sqrt{2\log t}} = \frac{G_g(t-1)}{\sqrt{2\log t}} + \frac{1}{\sqrt{S_g(t-1)}}.

This expression has a positive limit for any unit with finite limiting count, and tends to zero for a unit whose count diverges. There are finitely many units, so all sufficiently late maximizing indices would belong to units that have supposedly stopped being selected, a contradiction. Thus Sg(t)→∞S_g(t) \to\infty for every unit.

The maximum local mean in each counting unit is consistent. Work on the probability-one event on which the strong law holds for every action’s potential reward sequence. In a unit g⊆Ccg \subseteq C_c, at least one action is selected infinitely often, and the empirical mean of every such action converges to μc\mu_c. Actions selected finitely often eventually have frozen empirical means. No frozen mean can exceed μc\mu_c: otherwise, after all finitely selected actions have received their last samples and all infinitely selected actions have means below the largest frozen mean, the next selection of gg would have to select a supposedly frozen action. This contradicts the definition of those actions. Therefore,

Gg(t)⟶μcalmost surely.(20)G_g(t) \longrightarrow\mu_c \qquad\text{almost surely}. \tag*{(20)}

This argument permits some actions to receive only finitely many samples; it relies on selecting a maximum-mean action whenever its unit is chosen.

Each suboptimal counting unit incurs one logarithmic sampling cost. Fix a unit g⊆Ccg \subseteq C_c, c≥2c \ge2, and η∈(0,Δc/2)\eta\in(0,\Delta_c/2). By Eq. equation 20, for all sufficiently large tt, Gg(t−1)≤μc+ηG_g(t-1) \le\mu_c+\eta and G⋆(t−1)≥μ1−ηG_\star(t-1) \ge\mu_1-\eta. If gg is selected at such a round, comparison with the optimal index gives

μc+η+2log⁡tSg(t−1)≥μ1−η,Sg(t−1)≤2log⁡t(Δc−2η)2.\mu_c+\eta+\sqrt{\frac{2\log t}{S_g(t-1)}} \ge\mu_1-\eta,\qquad S_g(t-1)\le\frac{2\log t}{(\Delta_c-2\eta)^2}.

Applying this inequality at the last selection of gg up to TT yields

lim sup⁡T→∞Sg(T)log⁡T≤2(Δc−2η)2almost surely.(21)\limsup_{T\to\infty}\frac{S_g(T)}{\log T}\le\frac{2}{(\Delta_c-2\eta)^2}\qquad\text{almost surely}. \tag*{(21)}

Since the number of suboptimal counting units is finite, N⋆(T)=T−O(log⁡T)N_\star(T)=T-O(\log T) almost surely. Let τ(T)\tau(T) be the last round up to TT at which the optimal action is selected. Every subsequent round is suboptimal, so τ(T)=T−O(log⁡T)\tau(T)=T-O(\log T) and log⁡τ(T)/log⁡T→1\log\tau(T)/\log T\to1. At round τ=τ(T)\tau=\tau(T), the optimal index dominates Jg(τ)J_g(\tau), and hence

2log⁡τSg(τ−1)≤G⋆(τ−1)−Gg(τ−1)+2log⁡τN⋆(τ−1)=Δc+o(1).(22)\sqrt{\frac{2\log\tau}{S_g(\tau-1)}}\le G_\star(\tau-1)-G_g(\tau-1)+\sqrt{\frac{2\log\tau}{N_\star(\tau-1)}}=\Delta_c+o(1). \tag*{(22)}

The final bonus tends to zero because the optimal action receives τ−O(log⁡τ)\tau-O(\log\tau) samples. Using Sg(T)≥Sg(τ−1)S_g(T)\ge S_g(\tau-1) therefore gives

lim inf⁡T→∞Sg(T)log⁡T≥2Δc2.\liminf_{T\to\infty}\frac{S_g(T)}{\log T}\ge\frac{2}{\Delta_c^2}.

Letting η↓0\eta\downarrow0 through a countable sequence in Eq. equation 21 proves

Sg(T)log⁡T⟶2Δc2,NcB(T)log⁡T⟶2ρcBΔc2(23)\frac{S_g(T)}{\log T} \longrightarrow\frac{2}{\Delta_c^2}, \qquad\frac{N_c^B(T)}{\log T} \longrightarrow\frac{2\rho_c^B}{\Delta_c^2} \tag*{(23)}

almost surely.

Passing to expected regret. For each fixed ε∈(0,Δc)\varepsilon\in(0,\Delta_c), Eq. equation 15 implies

lim sup⁡T→∞EB[Nc(T)]log⁡T≤2ρcB(Δc−ε)2.\limsup_{T\to\infty}\frac{\mathbb{E}_B[N_c(T)]}{\log T}\leq\frac{2\rho_c^B}{(\Delta_c-\varepsilon)^2}.

Letting ε↓0\varepsilon\downarrow0 bounds this limsup by 2ρcB/Δc22\rho_c^B/\Delta_c^2. Conversely, Fatou’s lemma and Eq. equation 23 yield

lim inf⁡T→∞EB[Nc(T)]log⁡T≥EB[lim inf⁡T→∞Nc(T)log⁡T]=2ρcBΔc2.\liminf_{T\to\infty}\frac{\mathbb{E}_B[N_c(T)]}{\log T}\geq\mathbb{E}_B\left[\liminf_{T\to\infty}\frac{N_c(T)}{\log T}\right]=\frac{2\rho_c^B}{\Delta_c^2}.

Thus the expected counts have the same limiting coefficients. Substitution into the regret decomposition in § 4, with ρcind=mc\rho_c^{\mathrm{ind}}=m_c and ρcshare=1\rho_c^{\mathrm{share}}=1, proves the theorem. □

The resulting separation. The theorem compares actual expected regrets, giving

Rind(T)−Rshare(T)=2log⁡T∑c=2Kmc−1Δc+o(log⁡T),(24)R_{\mathrm{ind}}(T)-R_{\mathrm{share}}(T)=2\log T\sum_{c=2}^{K}\frac{m_c-1}{\Delta_c}+o(\log T), \tag*{(24)}

and

lim⁡T→∞Rind(T)Rshare(T)=∑c=2Kmc/Δc∑c=2K1/Δc.(25)\lim_{T\to\infty}\frac{R_{\mathrm{ind}}(T)}{R_{\mathrm{share}}(T)} =\frac{\sum_{c=2}^{K}m_c/\Delta_c}{\sum_{c=2}^{K}1/\Delta_c}. \tag*{(25)}

If every suboptimal action group contains mm actions, this ratio is mm. Deterministic reward distributions satisfy the assumptions, so the separation can occur even when all local empirical values are exact after initialization.

Count Fragmentation in Recursive Tree Search

We extend the bandit analysis to recursive UCT with terminal-reward backup. Our proof follows the recursive strategy used in UCT analysis (Kocsis & Szepesvári, [21]) and the subtree-regret decomposition of Coquelin & Munos [7]: we control the error in parent-edge value estimates through the regret accumulated in child subtrees. We adapt this strategy to shared exploration counts while retaining separate empirical action values. In the fixed deterministic tree considered here, this yields matching regret asymptotics that quantify the cost of count fragmentation along the optimal path.

Tree setting. Consider a fixed finite rooted tree T\mathcal{T} with root v0v_0. Each leaf ℓ\ell has a deterministic reward rℓ∈[0,1]r_\ell\in[0,1], and V∗(v)V^*(v) denotes the largest leaf reward reachable from node vv. At each internal node vv, divide the actions into groups Cv,c\mathcal{C}_{v,c}, with mv,c=∣Cv,c∣m_{v,c}=|\mathcal{C}_{v,c}| actions in each group. Actions in the same group lead to separate subtrees with identical structure and matching leaf rewards. Writing vav_a for the child reached by action aa, their common optimal continuation value is μv,c=V∗(va)\mu_{v,c}=V^*(v_a) for a∈Cv,ca\in\mathcal{C}_{v,c}.

Assume every internal node has a unique optimal action a∗(v)a^*(v), whose group, indexed by c∗(v)c^*(v), contains only that action. For each suboptimal action group, define Δv,c=V∗(v)−μv,c>0\Delta_{v,c}=V^*(v)-\mu_{v,c}>0. Let P∗\mathcal{P}^* denote the internal nodes on the unique optimal root-to-leaf path.

Selection and backup. Each simulation recursively selects a root-to-leaf path and backs up the terminal reward along that path. Let N(v)N(v) and N(v,a)N(v,a) be the numbers of completed simulations through node vv and edge (v,a)(v,a), respectively, and define N(v,c)=∑a∈Cv,cN(v,a)N(v,c)=\sum_{a\in\mathcal{C}_{v,c}}N(v,a). The empirical value Q^(v,a)\widehat{Q}(v,a) averages only the terminal rewards observed through edge (v,a)(v,a).

At each node, both algorithms first try every action once and then select an action maximizing the corresponding index:

Iind(v,a)=Q^(v,a)+2log⁡N(v)N(v,a),I_{\mathrm{ind}}(v,a)=\widehat{Q}(v,a)+\sqrt{\frac{2\log N(v)}{N(v,a)}},
Ishare(v,a)=Q^(v,a)+2log⁡N(v)N(v,c(a)).(26)I_{\mathrm{share}}(v,a)=\widehat{Q}(v,a)+\sqrt{\frac{2\log N(v)}{N(v,c(a))}}. \tag*{(26)}

Thus, both algorithms retain separate empirical action values and use the same terminal-reward backup procedure; only their exploration counts differ.

Following the cumulative-regret formulation for tree search [7], define

R(T)=∑t=1T(V∗(v0)−rℓt),(27)\mathcal{R}(T) = \sum_{t=1}^{T} \left(V^*(v_0) - r_{\ell_t}\right), \tag*{(27)}

where ℓt\ell_t is the leaf reached by simulation tt.

Theorem 2 (Regret penalty of count fragmentation in trees). Under the setting above, for the fixed tree as T→∞T \to\infty,

Rind(T)=2log⁡T∑v∈P∗∑c≠c∗(v)mv,cΔv,c+OT(log⁡log⁡T),\mathcal{R}_{\mathrm{ind}}(T) = 2 \log T \sum_{v \in P^*} \sum_{c \ne c^*(v)} \frac{m_{v,c}}{\Delta_{v,c}} + O_T(\log\log T),
Rshare(T)=2log⁡T∑v∈P∗∑c≠c∗(v)1Δv,c+OT(log⁡log⁡T).(28)\mathcal{R}_{\mathrm{share}}(T) = 2 \log T \sum_{v \in P^*} \sum_{c \ne c^*(v)} \frac{1}{\Delta_{v,c}} + O_T(\log\log T). \tag*{(28)}

If there is at least one suboptimal action group on P∗P^* and every such group contains mm actions, then Rind(T)/Rshare(T)→m\mathcal{R}_{\mathrm{ind}}(T)/\mathcal{R}_{\mathrm{share}}(T) \to m. The constants in the remainder may depend on the fixed tree.

Proof. We use local visit counts and proceed by induction on subtree height. Each subtree is analyzed in its own local visit time. Its search process can be continued beyond the visits made by the parent, so the bounds also apply to any finite observed prefix.

Recursive identities. For a node vv, let nn denote its number of visits and let Nv,a(n)N_{v,a}(n) count selections of action aa during those visits. Define the local subtree regret as

Rv(n)=nV∗(v)−∑i=1nrℓi(v),Rv(0)=0,(29)\mathcal{R}_v(n) = nV^*(v) - \sum_{i=1}^{n} r_{\ell_i^{(v)}}, \qquad\mathcal{R}_v(0) = 0, \tag*{(29)}

where ℓi(v)\ell_i^{(v)} is the leaf reached on the iith visit to vv. For a leaf, Rv(n)=0\mathcal{R}_v(n) = 0.

Since every visit to child vav_a passes through edge (v,a)(v,a), the empirical edge value satisfies, for k=Nv,a(n)>0k = N_{v,a}(n) > 0,

Q^v(a;n)=V∗(va)−Rva(k)k.(30)\widehat{Q}_v(a;n) = V^*(v_a) - \frac{\mathcal{R}_{v_a}(k)}{k}. \tag*{(30)}

Thus, the error in the parent edge value is exactly the average regret accumulated within the child subtree.

Writing Δ(v,a)=V∗(v)−V∗(va)\Delta(v,a) = V^*(v) - V^*(v_a), we also have

Rv(n)=∑a∈A(v)Δ(v,a)Nv,a(n)+∑a∈A(v)Rva(Nv,a(n)).(31)\mathcal{R}_v(n) = \sum_{a \in A(v)} \Delta(v,a)N_{v,a}(n) + \sum_{a \in A(v)} \mathcal{R}_{v_a}(N_{v,a}(n)). \tag*{(31)}

This follows by decomposing each simulation’s regret as V∗(v)−rℓ=[V∗(v)−V∗(va)]+[V∗(va)−rℓ]V^*(v) - r_{\ell} = [V^*(v) - V^*(v_a)] + [V^*(v_a) - r_{\ell}].

Induction hypothesis and counting units. Suppose every child subtree uu satisfies

Ru(k)=Aulog⁡k+OT(log⁡log⁡k)as k→∞.(32)\mathcal{R}_u(k) = A_u \log k + O_T(\log\log k) \qquad\text{as } k \to\infty. \tag*{(32)}

In particular, for a suitable finite constant CuC_u,

0≤Ru(k)≤Culog⁡(k+e)for all k≥0.(33)0 \le\mathcal{R}_u(k) \le C_u \log(k + e) \qquad\text{for all } k \ge0. \tag*{(33)}

These statements hold at leaves with $A_u = C_u = 0.

At the parent node vv, a counting unit is a set of actions sharing one exploration counter. Under independent-count UCT, each action forms its own unit; under shared-count UCT, all actions in Cv,cC_{v,c} form one unit. For a counting unit gg, suppressing vv in the notation, define

Sg(n)=∑a∈gNv,a(n),S_g(n) = \sum_{a \in g} N_{v,a}(n),
Gg(n)=max⁡a∈gQ^v(a;n),G_g(n) = \max_{a \in g} \widehat{Q}_v(a;n),
Jg(n)=Gg(n)+2log⁡nSg(n).(34)J_g(n) = G_g(n) + \sqrt{\frac{2 \log n}{S_g(n)}}. \tag*{(34)}

Maximizing the action indices is equivalent to choosing a unit maximizing Jg(n)J_g(n) and then an action attaining Gg(n)G_g(n). This is only a rewriting of the selection rule: empirical values remain separate.

Let μg\mu_g be the common optimal child value within unit gg, and let Δg=V∗(v)−μg\Delta_g = V^*(v) - \mu_g. The optimal counting unit, denoted by g∗g_*, contains only the optimal action.

Consistency and a coarse count bound. Every counting unit is visited infinitely often. Otherwise, some units would have eventually constant positive counts sgs_g. For such units, Jg(n)/2log⁡n→1/sg>0J_g(n)/\sqrt{2\log n} \to1/\sqrt{s_g} > 0, whereas this normalized index tends to zero for units whose counts diverge. Since there are finitely many units, a maximizing unit would eventually have to belong to the set whose counts supposedly stopped increasing, a contradiction.

We next control the value estimate within each counting unit. By Eq. equation 30, Q^v(a;n)≤μg\widehat{Q}_v(a;n) \leq\mu_g for every a∈ga \in g. At least one action in gg has count k≥Sg(n)/∣g∣k \geq S_g(n)/|g|. Applying Eq. equation 33 to that action gives

0≤bg(n):=μg−Gg(n)≤Dglog⁡(Sg(n)+e)Sg(n)(35)0 \leq b_g(n) := \mu_g - G_g(n) \leq D_g \frac{\log(S_g(n)+e)}{S_g(n)} \tag*{(35)}

where Dg=∣g∣max⁡a∈gCvaD_g = |g| \max_{a\in g} C_{v_a}. Hence Gg(n)→μgG_g(n) \to\mu_g. This argument does not require every action within a shared counting unit to be visited infinitely often.

If a suboptimal unit gg is selected after nn completed visits, then

μg+2log⁡nSg(n)≥Jg(n)≥J∗(n)≥G∗(n).\mu_g + \sqrt{\frac{2\log n}{S_g(n)}} \geq J_g(n) \geq J_*(n) \geq G_*(n).

For sufficiently large nn, consistency gives G∗(n)≥V∗(v)−Δg/2G_*(n) \geq V^*(v) - \Delta_g/2, and therefore Sg(n)≤8log⁡n/Δg2S_g(n) \leq8\log n/\Delta_g^2 at such selection times. Applying this bound at the last selection of gg and allowing for its unit increment yields Sg(n)=OT(log⁡n)S_g(n) = O_{\mathcal{T}}(\log n) at every sufficiently large time. Consequently,

S∗(n)=n−OT(log⁡n),b∗(n)=OT(log⁡nn).(36)S_*(n) = n - O_{\mathcal{T}}(\log n), \qquad b_*(n) = O_{\mathcal{T}}\left(\frac{\log n}{n}\right). \tag*{(36)}

Matching upper and lower count bounds. We first sharpen the upper bound. Whenever a suboptimal unit gg is selected, comparison with the optimal unit gives

2log⁡nSg(n)≥Δg−b∗(n).\sqrt{\frac{2\log n}{S_g(n)}} \geq\Delta_g - b_*(n).

Using Eq. equation 36 and the fixed positive gap Δg\Delta_g,

Sg(n)≤2log⁡n(Δg−b∗(n))2=2log⁡nΔg2+OT((log⁡n)2n).S_g(n) \leq\frac{2\log n}{(\Delta_g-b_*(n))^2} = \frac{2\log n}{\Delta_g^2} + O_{\mathcal{T}}\left(\frac{(\log n)^2}{n}\right).

Applying this inequality at the last selection of gg, including its unit increment, proves

Sg(n)≤2log⁡nΔg2+OT(1).(37)S_g(n) \leq\frac{2\log n}{\Delta_g^2} + O_{\mathcal{T}}(1). \tag*{(37)}

For the lower bound, let τ≤n\tau\leq n be the last visit on which the optimal action was selected, and put s=τ−1s = \tau- 1. All visits after τ\tau are suboptimal, so the coarse count bound implies s=n−OT(log⁡n)s = n - O_{\mathcal{T}}(\log n) and log⁡s=log⁡n+o(1)\log s = \log n + o(1). At the decision after ss completed visits, J∗(s)≥Jg(s)J_*(s) \geq J_g(s). Since G∗(s)≤V∗(v)G_*(s) \leq V^*(v),

2log⁡sSg(s)≤Δg+bg(s)+2log⁡sS∗(s).(38)\sqrt{\frac{2\log s}{S_g(s)}} \leq\Delta_g + b_g(s) + \sqrt{\frac{2\log s}{S_*(s)}}. \tag*{(38)}

The last two terms tend to zero, so Sg(s)≥cglog⁡sS_g(s) \geq c_g\log s for some constant cg>0c_g > 0. Together with Eq. equation 37, this gives Sg(s)=ΘT(log⁡s)S_g(s) = \Theta_{\mathcal{T}}(\log s) at these comparison times. Equation equation 35 then yields

bg(s)=OT(log⁡log⁡slog⁡s),2log⁡sS∗(s)=OT(log⁡ss).b_g(s) = O_{\mathcal{T}}\left(\frac{\log\log s}{\log s}\right), \qquad \sqrt{\frac{2\log s}{S_*(s)}} = O_{\mathcal{T}}\left(\sqrt{\frac{\log s}{s}}\right).

Substituting these estimates into Eq. equation 38 and expanding the reciprocal square around the fixed gap Δg\Delta_g gives

Sg(s)≥2log⁡sΔg2−OT(log⁡log⁡s).S_g(s) \ge\frac{2\log s}{\Delta_g^2} - O_{\mathsf{T}}(\log\log s).

Indeed, the first error contributes O(log⁡log⁡s)O(\log\log s) after multiplication by log⁡s\log s, while the second contributes O((log⁡s)3/2/s)=o(1)O((\log s)^{3/2}/\sqrt{s})=o(1). Using Sg(n)≥Sg(s)S_g(n) \ge S_g(s) and log⁡s=log⁡n+o(1)\log s = \log n + o(1) proves

Sg(n)≥2log⁡nΔg2−OT(log⁡log⁡n).(39)S_g(n) \ge\frac{2\log n}{\Delta_g^2} - O_{\mathsf{T}}(\log\log n). \tag*{(39)}

Combining the two bounds,

Sg(n)=2log⁡nΔg2+OT(log⁡log⁡n).(40)S_g(n) = \frac{2\log n}{\Delta_g^2} + O_{\mathsf{T}}(\log\log n). \tag*{(40)}

From local counts to tree regret. For algorithm B∈{ind,share}B \in\{\mathrm{ind},\mathrm{share}\}, define ρv,cind=mv,c\rho^{\mathrm{ind}}_{v,c}=m_{v,c} and ρv,cshare=1\rho^{\mathrm{share}}_{v,c}=1. Independent counting has one counting unit per action, whereas shared counting has one per action group. Summing Eq. equation 40 within each suboptimal action group gives

Nv,cB(n)=2ρv,cBlog⁡nΔv,c2+OT(log⁡log⁡n).(41)N^B_{v,c}(n)=\frac{2\rho^B_{v,c}\log n}{\Delta_{v,c}^2}+O_{\mathsf{T}}(\log\log n). \tag*{(41)}

The local action-gap contribution in Eq. equation 31 is therefore

2log⁡n∑c≠c∗(v)ρv,cBΔv,c+OT(log⁡log⁡n).2\log n\sum_{c\ne c^*(v)}\frac{\rho^B_{v,c}}{\Delta_{v,c}}+O_{\mathsf{T}}(\log\log n).

Let u∗=va∗(v)u_* = v_{a^*(v)} be the optimal child. It receives n∗=n−OT(log⁡n)n_* = n-O_{\mathsf{T}}(\log n) visits, so the induction hypothesis gives

Ru∗B(n∗)=Au∗Blog⁡n+OT(log⁡log⁡n).\mathcal{R}^B_{u_*}(n_*)=A^B_{u_*}\log n+O_{\mathsf{T}}(\log\log n).

Every suboptimal child receives at most OT(log⁡n)O_{\mathsf{T}}(\log n) visits. Its additional subtree regret is bounded by

RvaB(Nv,aB(n))≤Cvalog⁡(Nv,aB(n)+e)=OT(log⁡log⁡n).\mathcal{R}^B_{v_a}\left(N^B_{v,a}(n)\right)\le C_{v_a}\log\left(N^B_{v,a}(n)+e\right)=O_{\mathsf{T}}(\log\log n).

This bound also covers actions that receive only finitely many visits.

Substitution into Eq. equation 31 proves

RvB(n)=AvBlog⁡n+OT(log⁡log⁡n),\mathcal{R}^B_v(n)=A^B_v\log n+O_{\mathsf{T}}(\log\log n),

where

AvB=Au∗B+2∑c≠c∗(v)ρv,cBΔv,c.(42)A^B_v=A^B_{u_*}+2\sum_{c\ne c^*(v)}\frac{\rho^B_{v,c}}{\Delta_{v,c}}. \tag*{(42)}

This completes the induction.

Finally, unrolling Eq. equation 42 along the unique optimal path yields

Av0B=2∑v∈P∗∑c≠c∗(v)ρv,cBΔv,c.A^B_{v_0}=2\sum_{v\in P^*}\sum_{c\ne c^*(v)}\frac{\rho^B_{v,c}}{\Delta_{v,c}}.

Taking ρv,cind=mv,c\rho^{\mathrm{ind}}_{v,c}=m_{v,c} and ρv,cshare=1\rho^{\mathrm{share}}_{v,c}=1 proves Eq. equation 28. When every suboptimal action group on P∗P^* contains mm actions, the independent-count coefficient is mm times the shared-count coefficient, giving the stated regret ratio.

Prompt Template and Reward Construction

For both settings, the task instance is placed in the user message, while the prompt specifies the available tool and required function-call format. For each backbone, the corresponding prompt is identical for DAPO, standard MCTS, and LPC-MCTS.

Tool-integrated mathematical reasoning. We use the following system prompt with the code_interpreter tool: Mathematical-reasoning system prompt

You are Qwen, created by Alibaba Cloud. You are a helpful assistant.

# Tools

You may call one or more functions to assist with the user query.

You are provided with function signatures within <tools></tools> XML tags:
<tools>
{"type": "function",
 "function": {
  "name": "code_interpreter",
  "description": "A tool for executing code.",
  "parameters": {
   "type": "object",
   "properties": {
    "code": {"type": "string", "description": "The code to execute."}
   },
   "required": ["code"]
  }
 }
}
</tools>

For each function call, return a JSON object with function name and arguments within <tool_call></tool_call> XML tags
:
<tool_call>
{"name": <function-name>, "arguments": <args-json-object>}
</tool_call>

Search. For Qwen2.5-7B-Instruct, we use the following system prompt with the search tool:

Qwen search system prompt

You are Qwen, created by Alibaba Cloud. You are a helpful assistant.

# Tools

You may call one or more functions to assist with the user query.

You are provided with function signatures within <tools></tools> XML tags:
<tools>
{"type": "function",
 "function": {
  "name": "search",
  "description": "Searches the web for relevant information based on the given query.",
  "parameters": {
   "type": "object",
   "properties": {
    "query_list": {
     "type": "array",
     "items": {"type": "string"},
     "description": "A list of fully-formed semantic queries. The tool will return search results for each query."
    }
   },
   "required": ["query_list"]
  }
 }
}
</tools>

For each function call, return a JSON object with function name and arguments within <tool_call></tool_call> XML tags

<tool_call>
{"name": <function-name>, "arguments": <args-json-object>}
</tool_call>

For Llama-3.2-3B-Instruct, the serving framework automatically adds the system metadata at runtime. We therefore show only the user-message template below:

Llama search user prompt

Given the following functions, please respond with a JSON for a function call with its proper arguments that best answers the given prompt.

Respond in the format {"name": function name, "parameters": dictionary of argument name and its value}. Do not use variables.

{
    "type": "function",
    "function": {
        "name": "search",
        "description": "Searches the web for relevant information based on the given query.",
        "parameters": {
            "type": "object",
            "properties": {
                "query_list": {
                    "type": "array",
                    "description": "A list of fully-formed semantic queries. The tool will return search results for each query.",
                    "enum": null
                }
            },
            "required": [
                "query_list"
            ]
        },
        "strict": false
    }
}

The model can alternate between reasoning and tool calls, using each tool output to continue its response. Because tool outputs are generated by the environment rather than the policy, their tokens are excluded from both the policy and CFN losses.

During training, we extract the final answer from \boxed{} for both tasks. For mathematical reasoning, we normalize the extracted expression before comparing it with the reference answer; for search, we use exact match against the reference answer. We define the base task score as

Sbase={+1,if the final answer is correct,−1,otherwise.(43)S_{\mathrm{base}} = \begin{cases} +1, & \text{if the final answer is correct},\\ -1, & \text{otherwise}. \end{cases} \tag*{(43)}

To address potential tool-call collapse in some RL settings, we add an auxiliary tool-call reward to DAPO training. For incorrect trajectories, the bonus increases by 0.05 for each interaction turn beyond the first two and is capped at 0.4. Correct trajectories receive a unit bonus when they contain more than two turns.

Training and Inference Configurations

Training Configurations

All experiments were conducted on 8 GPUs. Tool-integrated mathematical reasoning uses Qwen2.5-7B and Qwen3-4B, while search uses Qwen2.5-7B-Instruct and Llama-3.2-3B-Instruct.

Supervised Fine-Tuning. Before RL training, we perform SFT on each policy backbone. For tool-integrated mathematical reasoning, Qwen2.5-7B and Qwen3-4B are trained on the ReTool SFT corpus (Feng et al., [11]). For search, Qwen2.5-7B-Instruct and Llama-3.2-3B-Instruct are trained on the same 2,000 examples sampled from the Chain-of-Agents SFT corpus (Li et al., [24]). The SFT configurations are summarized in Table 3.

HyperparameterValue
OptimizerAdamW
Learning rate1×10−51 \times10^{-5}
Weight decay0.01
Learning-rate scheduleCosine
Warmup ratio0.1
Global batch size16
Maximum sequence length16,384 (math) / 8,192 (search)
Training epochs2

Table 3. Supervised fine-tuning configurations.

Policy training. Table 4 and Table 5 summarize the policy training settings for the two tasks. We train each experiment for 100 steps.

HyperparameterValue
General training hyperparameters
BackbonesQwen2.5-7B / Qwen3-4B
OptimizerAdamW
Policy learning rate1×10−61 \times10^{-6}
Prompts per training batch128
Samples per prompt8
Mini-batch size128
Max prompt length1,024
Max response length18,000
Rollout temperature1.0
MCTS hyperparameters
Maximum tree depth6
Maximum tool-interaction turns per node3
UCT coefficient ccountc_{\mathrm{count}}2.0
Maximum response length per node3,072

Table 4. Policy training configuration for tool-integrated mathematical reasoning.

HyperparameterValue
General training hyperparameters
BackbonesQwen2.5-7B-Instruct / Llama-3.2-3B-Instruct
OptimizerAdamW
Policy learning rate1×10−61 \times10^{-6}
Prompts per training batch512
Samples per prompt5
Mini-batch size256
Max prompt length512
Max response length8,192
Rollout temperature1.0
MCTS hyperparameters
Maximum tree depth4
Maximum tool-interaction turns per node2
UCT coefficient ccountc_{\mathrm{count}}2.0
Maximum response length per node2048

Table 5. Policy training configuration for search.

CFN configuration. Table 6 summarizes the parameters specific to the CFN estimator. The CFN head is randomly initialized and trained online. During search, newly collected samples are accumulated, and the head is updated after every four MCTS iterations. Backbone representations are treated as fixed inputs to the CFN loss, so these updates do not propagate gradients into the policy backbone.

HyperparameterValue
CFN output dimension dd20
OptimizerAdamW
Online learning rate1×10−41 \times10^{-4}
CFN-head update frequencyEvery 4 MCTS iterations
Token filteringTop 30%

Table 6. CFN estimator and online-training configurations.

Training cost. On 8 GPUs, a full training run takes approximately 100 hours for tool-integrated mathematical reasoning and 50 hours for search. Across all evaluated tasks and backbones, LPC-MCTS increases training time by no more than 20% relative to standard MCTS, making it a lightweight addition for exploration through learning the pseudo-count.

Inference Configurations

For sampling-based evaluation of mathematical reasoning, we use a temperature of 0.6 and top-pp sampling with p=0.95p = 0.95. For search, we evaluate greedy decoding and tree-based inference with standard MCTS or LPC-MCTS with a temperature of 0.6 and top-pp sampling with p=0.95p = 0.95. For MCTS-based evaluation, we run a search tree for each problem and collect 16 terminal trajectories for mathematical reasoning or 5 for search. Tree search stops once the required number of trajectories is collected or the maximum of 128 MCTS iterations is reached. If the limit is reached before collecting enough trajectories, each missing candidate is counted as incorrect. We report mean@16 (mathematical reasoning) or mean@5 (search) as the fraction of these trajectories whose final answers are correct, using the same protocol and search budget for standard MCTS and LPC-MCTS.

Search Retrieval Configuration

All search experiments use the same offline retrieval service. We use PeterJinGo/wiki-18-corpus, a 2018 Wikipedia corpus containing 21,015,324 documents. Queries are encoded on CPU with intfloat/e5-base-v2 into 768-dimensional embeddings.

Retrieval uses the precomputed PeterJinGo/wiki-18-e5-index-HNSW64 FAISS HNSW64 index, which contains 21,015,324 vectors and uses inner-product similarity. We set efSearch to 128 and return the top three documents for each query.

Additional Experimental Results

Coin Flipping Network

Token-level Uncertainty Visualization

For each selected response, we align the raw scalar score uv,tu_{v,t} with every eligible token position and preserve the original generation order. Prompt, padding, and tool-response positions are excluded using the same mask as in the node-level estimator. A larger uv,tu_{v,t} indicates higher CFN uncertainty due to less accumulated representation evidence.

Token-level CFN value heatmap

CFN value

0.00730.0073 0.05080.0508 0.09420.0942

So e=116e=116. Then check if e−(190)/2=116−95=21e-(190)/2=116-95=21. Yes! 2121. That works.

Now check p=211p=211. Then p−1=210p-1=210.

Compute e=2016 mod 210e=2016\bmod210.

{"name": "code_interpreter", "arguments": {"code": "print(2016 % 210)"}}

TOOL RESPONSE

Output:

126

Then e−210/2=126−105=21e-210/2=126-105=21. Oh! That also works.

So both p=191p=191 and p=211p=211 satisfy the equation e−(p−1)/2=21e-(p-1)/2=21.

So we need more information to distinguish between these two.

But Evan says that he tried taking 2016 mod (p−1)2016\bmod(p-1) and got ee larger than 100100. Let's check for both p=191p=191 and p=211p=211.

For p=191p=191, e=116e=116, which is greater than 100100.

For p=211p=211, e=126e=126, also greater than 100100. So both satisfy that.

Hmm. So need another condition.

Then Evan realized the answer was −221 mod p-2^{21}\bmod p. So let's compute 22016 mod p2^{2016}\bmod p, which should be equivalent to −221 mod p-2^{21}\bmod p.

So let's check for both p=191p=191 and p=211p=211.

First p=191p=191:

Compute 22016 mod 1912^{2016}\bmod191.

Since by Fermat's little theorem, 2190≡1 mod 1912^{190}\equiv1\bmod191, since p−1=190p-1=190. Wait, p=191p=191, so p−1=190p-1=190. So 2190≡1 mod 1912^{190}\equiv1\bmod191.

Therefore, 22016=2(190∗10+16)=(2190)10∗216≡110∗216≡216 mod 1912^{2016}=2^{(190*10+16)}=(2^{190})^{10}*2^{16}\equiv1^{10}*2^{16}\equiv2^{16}\bmod191.

Compute 2162^{16}:

{"name": "code_interpreter", "arguments": {"code": "print(2 ** 16 % 191)"}}

TOOL RESPONSE

Output:

23

Therefore, 22016 mod 191=232^{2016}\bmod191=23.

But Evan thought it was −221 mod 191-2^{21}\bmod191.

{"name": "code_interpreter", "arguments": {"code": "neg_2_21 = (-pow(2, 21, 191)) % 191\nprint(neg_2_21)"}}

TOOL RESPONSE

Output:

28

tool response (excluded from CFN scoring)

Across the examples, uncertainty changes within each response. In Figure 3, high scores appear when the model changes its plan from direct modulo calculations to a different exponentiation method, and when it builds a new tool call. In Figure 4, high scores appear when the model compares two possible values of pp, applies Fermat’s little theorem, and later fixes its calculation. In Figure 5, high scores appear when the model works through a sampling process that combines discrete and continuous choices and turns it into simulation code. Figure 6 shows another geometry example: high scores appear when the model notices that its first radius calculation cannot be right, rethinks the geometry, and writes the correct equation using the Pythagorean theorem. In Figure 7, high scores concentrate on named entities and relation-bearing terms as the model reformulates its query after the initial search results do not resolve the target relation. In Figure 8, high scores appear when the model combines retrieved archaeological evidence, reasons over its temporal context, and commits to the final answer despite the absence of a direct match. By contrast, common connecting words, routine calculations, and repeated search scaffolding generally receive lower scores. The high scores usually cover several neighboring tokens rather than isolated tokens. Across both task types, these high-score spans correspond to changes in reasoning strategy, tool-query formulation, evidence synthesis, code, or specialized mathematical steps. This suggests that the learned CFN head captures high-level reasoning patterns in both internal reasoning and tool-augmented information seeking, rather than only token-level differences. Each heatmap has its own score range, so its colors should be read within that example rather than compared directly with the other figures.

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,tu_{v,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.

Token-level CFN value heatmap showing a Qwen3-4B modular-arithmetic response with token-level uncertainty highlighting

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.

Token-level CFN value heatmap for a Qwen2.5-7B-Instruct search response

Figure 7. An example of token-level uncertainty estimated by CFN within a Qwen2.5-7B-Instruct search response.

Token-level CFN value heatmap for a Llama-3.2-3B-Instruct search response

Figure 8. An example of token-level uncertainty estimated by CFN within a Llama-3.2-3B-Instruct search response.

Reasoning-Pattern Sensitivity in Rollout Trees

During model rollouts, we record each expanded parent node together with its children and their learned pseudo-counts. We sample some instances from these rollout records for qualitative visualization. Each instance contains two textually different children that follow the same or a closely related reasoning pattern, together with a third child that takes a more distinct approach.

A combinatorial-reasoning case from an actual Qwen3-4B rollout tree

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.

A symbolic-computation case from an actual Qwen2.5-7B rollout tree

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.

A query-planning case from an actual Qwen2.5-7B-Instruct search rollout tree

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.

Together, Figure 1 and Figure 9–Figure 15 show this behavior across eight sampled rollout-tree examples. The six mathematical-reasoning cases cover changes in theorem, representation, and computational strategy, while the two search cases cover query planning and evidence use. Across both tasks and model families, textually different children following the same high-level pattern receive close pseudo-counts, whereas a child that changes the reasoning pattern shows a substantially larger pseudo-count gap from the aligned pair. The final search case further shows that this distinction can persist even when all children produce the same answer, indicating that the estimator responds to the reasoning path rather than outcome identity alone.

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 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.

This behavior addresses a limitation of standard MCTS counts. Standard MCTS maintains an independent tabular count for each child, so sampling child A does not increase the count of a semantically related child B. Consequently, B can still appear unexplored even when its reasoning pattern has already been covered through A. LPC-MCTS instead assigns pseudo-counts from learned hidden representations, allowing such branches to share familiarity. Holding the other UCT terms fixed, the larger counts of A and B reduce redundant exploration of the repeated pattern, while the lower count of C gives the distinct strategy a larger exploration bonus.

Quantitative Mechanism Validation

Both experiments use frozen Qwen3-4B and Qwen2.5-7B backbones on mathematical reasoning tasks.

Semantic alignment. For each backbone, we sample 8 distinct non-root MCTS nodes from each of 128 questions, independently of pseudo-counts or embedding similarities. For node pairs within each question, we compare count closeness, ∣−log⁡Cϕ(vi)−log⁡Cϕ(vj)∣\lvert-\log C_{\phi}(v_i)-\log C_{\phi}(v_j)\rvert, with cosine similarity between embeddings of the generated text. Using Qwen3-Embedding-4B and QZhou-Embedding, we report Spearman correlation and nearest-neighbor agreement.

Table 7 shows positive correlations (ρ=0.248\rho= 0.248–0.3580.358; all 95% CIs exclude zero) and 24.1–29.2% nearest-neighbor agreement, above the 14.3% uniform-random baseline. These results support the semantic relevance of learned pseudo-counts.

CFN backboneEmbedding modelSpearman ρ\rho [95% CI]Nearest-neighbor agreement
Qwen3-4BQwen3-Embedding-4B0.255 [0.197, 0.315]24.1%
Qwen3-4BQZhou-Embedding0.248 [0.197, 0.299]24.8%
Qwen2.5-7BQwen3-Embedding-4B0.335 [0.279, 0.391]29.2%
Qwen2.5-7BQZhou-Embedding0.358 [0.303, 0.413]26.9%

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.

Count transfer across branches. For sibling responses AA and BB, we use GPT-6 to label reasoning-pattern similarity separately from content equivalence. We measure the change in the pseudo-count of held-out sibling BB after 16 coin-flip updates to the CFN head on AA. Each trial starts from the original head and a fresh optimizer. Log-count changes are averaged within questions and reported as geometric mean percentage changes with question-level bootstrap 95% CIs.

Table 8 shows a 5.5% increase for same-pattern siblings and a 3.2% decrease for distinct-pattern siblings, with both 95% CIs excluding zero. This supports selective evidence sharing across related reasoning branches.

Probe nodesQuestionsPseudo-count change (geometric mean; 95% CI)
Same-pattern siblings400+5.5% [+3.5%, +7.4%]
Distinct-pattern siblings126−3.2% [−5.0%, −1.3%]

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.

MCTS Training

Training Dynamics

Figure 16 compares the answer scores of standard MCTS and LPC-MCTS across four task–model settings at training time. The curves are smoothed using a 3-step running average.

Training reward dynamics of standard MCTS and LPC-MCTS

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.

Ablation Studies

To separate the effects of the training and inference configurations, Table 9 specifies the method used at each stage. Pseudo-count-guided trajectory selection is used only to construct the policy-training batch, so we ablate it only during training by removing the ranking and selection rule in Eq. (11). Token-to-node aggregation is used to compute node pseudo-counts in both stages and is therefore ablated separately during training and inference. When aggregation is removed at a given stage, let tlastt_{\mathrm{last}} be the last eligible model-generated token in node vv. We directly use its CFN score to compute the node-level pseudo-count:

TrainingInferenceAIME 24AIME 25AIME 26HMMT25BRUMO25Avg.
Qwen2.5-7B
LPC-MCTS (w/o pseudo-count)MCTS39.1725.6324.7918.9644.5830.63
LPC-MCTS (w/o trajectory selection)LPC-MCTS34.7929.5827.7115.8342.5030.08
LPC-MCTS (w/o node aggregation)LPC-MCTS37.7128.7525.6319.1748.5431.96
LPC-MCTS (w/o both)LPC-MCTS37.5026.0428.9618.5445.4231.29
LPC-MCTSLPC-MCTS (w/o node aggregation)35.8328.3327.0819.1746.6731.42
LPC-MCTS (w/o node aggregation)LPC-MCTS (w/o node aggregation)38.1327.0827.0818.1341.8830.46
LPC-MCTSLPC-MCTS37.0830.6327.9223.3345.0032.79
Qwen3-4B
LPC-MCTS (w/o pseudo-count)MCTS76.2557.7164.3847.2965.2162.17
LPC-MCTS (w/o trajectory selection)LPC-MCTS74.3863.1372.0850.2165.6365.09
LPC-MCTS (w/o node aggregation)LPC-MCTS75.2162.7170.8348.3362.0863.83
LPC-MCTS (w/o both)LPC-MCTS70.6358.1366.0447.2964.7961.38
LPC-MCTSLPC-MCTS (w/o node aggregation)74.7962.5070.4248.9665.8364.50
LPC-MCTS (w/o node aggregation)LPC-MCTS (w/o node aggregation)73.1358.7567.2949.3862.5062.21
LPC-MCTSLPC-MCTS78.1363.5472.9251.8866.0466.50

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).

Uϕ(v)=uv,tlast,Cϕ(v)=1Uϕ(v)+ϵ.(44)U_{\phi}(v) = u_{v,t_{\mathrm{last}}}, \qquad C_{\phi}(v) = \frac{1}{U_{\phi}(v) + \epsilon}. \tag*{(44)}

The combined training variant removes both trajectory selection and node aggregation. We also remove node aggregation at both stages to assess its end-to-end effect. The w/o pseudo-count variant uses standard visit counts for tree search during training and inference, while retaining pseudo-count-guided trajectory selection for policy training. All other settings are kept identical to full LPC-MCTS.

Table 9 shows that the ablated components contribute across backbones. Removing pseudo-counts from tree search while retaining trajectory selection lowers the average by 2.16 points on Qwen2.5-7B and 4.33 points on Qwen3-4B. Removing pseudo-count-guided trajectory selection lowers the average by 2.71 points on Qwen2.5-7B and 1.41 points on Qwen3-4B. Removing token-to-node aggregation during training lowers the average by 0.83 and 2.67 points, while removing it only at inference lowers it by 1.37 and 2.00 points. Removing aggregation at both stages produces larger drops of 2.33 and 4.29 points, respectively. Removing both training components also reduces the average by 1.50 and 5.12 points. These consistent average degradations support the roles of trajectory selection in policy training and node aggregation in both training and inference.

Hyperparameters

The default token-filtering ratio in LPC-MCTS is p=30p = 30, as described in Appendix § 8.§ 3. To examine sensitivity to this choice, we additionally evaluate p=50p = 50, p=70p = 70, and p=100p = 100. A larger pp retains a broader set of token-level CFN scores, while p=100p = 100 retains all eligible tokens before contiguous-run filtering. The same value of pp is used during training and inference, with all other configurations fixed.

Table 10 shows that the default p=30p = 30 achieves the highest average performance on both backbones. Qwen3-4B drops by 1.96–2.25 points with larger filtering ratios, whereas Qwen2.5-7B varies by less than one point across all settings. These results support p=30p = 30 as a strong default while indicating that LPC-MCTS is not highly sensitive to this choice, especially on Qwen2.5-7B. Moreover, retaining all eligible tokens (p=100p = 100) does not improve the average, suggesting that filtering helps exclude less informative token-level estimates from node aggregation.

Top p%p\%AIME 24AIME 25AIME 26HMMT25BRUMO25Avg.
Qwen2.5-7B
30%37.0830.6327.9223.3345.0032.79
50%36.2526.6728.7522.7145.0031.88
70%34.3831.6727.0824.7942.7132.13
100%38.9629.1729.7922.0843.3332.67
Qwen3-4B
30%78.1363.5472.9251.8866.0466.50
50%74.1761.4669.5854.3863.1364.54
70%76.8859.5870.0048.9666.2564.33
100%78.9660.2171.2548.5462.2964.25

Table 10. Sensitivity to the top-p%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).

Inference-Time Cost Analysis

We compare MCTS and LPC-MCTS on the 60 problems from AIME 2024 and AIME 2025 using 2 GPUs and 16 candidate slots per problem. For each backbone, both methods use the same policy checkpoint, decoding parameters, and maximum search-iteration budget; the CFN head is frozen during inference.

Table 11 reports the overall inference costs. Policy-generated token counts cover the entire search, including branches not selected for the final output. The amortized time per candidate includes all search and CFN computation, but excludes model initialization and post-processing.

ModelGenerated tokens (M)Time (s/candidate)
MCTSLPC-MCTSReductionMCTSLPC-MCTS
Qwen3-4B80.95863.10622.05%16.7215.98
Qwen2.5-7B44.00725.52542.00%12.0512.83

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.

LPC-MCTS generates 22.05% fewer tokens on Qwen3-4B and 42.00% fewer on Qwen2.5-7B under the same search budget, showing the higher token efficiency. The amortized time per candidate falls from 16.72 to 15.98 seconds on Qwen3-4B, and rises from 12.05 to 12.83 seconds on Qwen2.5-7B. Thus, the measured wall-clock cost remains similar in these runs, despite introducing a CFN head.

Table 12 shows where the CFN spends time. For each component, we sum its elapsed time across workers and divide by the total search time across those workers. Feature extraction includes requesting hidden states from the backbone, waiting for the request, and processing the returned states; scoring/control includes evaluating the CFN head.

MeasurementQwen3-4BQwen2.5-7B
Mean CFN input length (tokens/sequence)2,905.481,442.85
CFN input sequences processed20,96816,512
CFN feature-extraction time share6.50%5.31%
CFN scoring/control time share0.23%0.18%
Combined CFN time share6.73%5.49%

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.

CFN-related work accounts for 6.73% of total worker search time on Qwen3-4B and 5.49% on Qwen2.5-7B. Most of this time is spent obtaining hidden states from the backbone, compared with just 0.23% and 0.18% for CFN scoring/control.

References

  1. [1]Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235–256, 2002.DOI
  2. [2]Chenjia Bai, Yang Zhang, Shuang Qiu, Qiaosheng Zhang, Kang Xu, and Xuelong Li. Online preference alignment for language models via count-based exploration. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=cFKZ5VrhXt.arxiv.org/abs/2501.12735
  3. [3]Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. Advances in neural information processing systems, 29, 2016.
  4. [4]Cameron B. Browne, Edward Powley, Daniel Whitehouse, Simon M. Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1):1–43, 2012. doi:10.1109/TCIAIG.2012.2186810.DOI
  5. [5]Daixuan Cheng, Shaohan Huang, Xuekai Zhu, Bo Dai, Wayne Xin Zhao, Zhenliang Zhang, and Furu Wei. Reasoning with exploration: An entropy perspective, 2025. URL https://arxiv.org/abs/2506.14758.
  6. [6]Xiangxiang Chu, Hailang Huang, Xiao Zhang, Fei Wei, and Yong Wang. GPA: A simple and strong reinforcement learning baseline for model reasoning. In The Fourteenth International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=inccdtfx8x.arxiv.org/abs/2504.02546
  7. [7]Pierre-Arnaud Coquelin and Rémi Munos. Bandit algorithms for tree search. arXiv preprint cs/0703062, 2007.
  8. [8]Runpeng Dai, Linfeng Song, Haolin Liu, Zhenwen Liang, Dian Yu, Haitao Mi, Zhaopeng Tu, Rui Liu, Tong Zheng, Hongtu Zhu, and Dong Yu. CDE: Curiosity-driven exploration for efficient reinforcement learning in large language models. In The Fourteenth International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=5rXN5knHKW.arxiv.org/abs/2509.09675
  9. [9]Jasper Dekoninck, Nikola Jovanović, Tim Gehrunger, Kári Rögnvaldsson, Ivo Petrov, Chenhao Sun, and Martin Vechev. Beyond benchmarks: Matharena as an evaluation platform for mathematics with llms. 2026. URL https://arxiv.org/abs/2605.00674.
  10. [10]Lin Fan and Peter W Glynn. The typical behavior of bandit algorithms. arXiv preprint arXiv:2210.05660, 2022.arxiv.org/abs/2210.05660
  11. [11]Jiazhan Feng, Shijie Huang, Xingwei Qu, Ge Zhang, Yujia Qin, Baoquan Zhong, Chengquan Jiang, Jinxin Chi, and Wanjun Zhong. Retool: Reinforcement learning for strategic tool use in LLMs. In The Fourteenth International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=tRk1no fSmz.arxiv.org/abs/2504.11536
  12. [12]Jingtong Gao, Ling Pan, Yejing Wang, Rui Zhong, Chi Lu, Maolin Wang, Qingpeng Cai, Peng Jiang, and Xiangyu Zhao. Navigate the unknown: Enhancing llm reasoning with intrinsic motivation guided exploration, 2026. URL https://arxiv.org/abs/2505.17621.
  13. [13]Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhari, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The llama 3 herd of models, 2024. URL https://arxiv.org/abs/2407.21783.
  14. [14]Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Peiyi Wang, Qihao Zhu, Runxin Xu, Rouyu Zhang, Shirong Ma, Xiao Bi, et al. Deepseek-r1 incentivizes reasoning in llms through reinforcement learning. Nature, 645(8081):633–638, 2025.DOI
  15. [15]Shibo Hao, Yi Gu, Haodi Ma, Joshua Hong, Zhen Wang, Daisy Wang, and Zhiting Hu. Reasoning with language model is planning with world model. In Proceedings of the 2023 conference on empirical methods in natural language processing, pp. 8154–8173, 2023.arxiv.org/abs/2305.14992
  16. [16]Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301):13–30, 1963.
  17. [17]Yuxiang Ji, Ziyu Ma, Yong Wang, Guanhua Chen, Xiangxiang Chu, and Liaoni Wu. Tree search for LLM agent reinforcement learning. In The Fourteenth International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=ZpQwAFhU13.arxiv.org/abs/2509.21240
  18. [18]Bowen Jin, Hansi Zeng, Zhenrui Yue, Jinsung Yoon, Sercan O Arik, Dong Wang, Hamed Zamani, and Jiawei Han. Search-r1: Training LLMs to reason and leverage search engines with reinforcement learning. In Second Conference on Language Modeling, 2025. URL https://openreview.net/forum?id=Rwhi91idedu.arxiv.org/abs/2503.09516
  19. [19]Mandar Joshi, Eunsol Choi, Daniel S. Weld, and Luke Zettlemoyer. Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension, 2017. URL https://arxiv.org/abs/1705.03551.
  20. [20]Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 6769–6781, Online, November 2020. Association for Computational Linguistics. doi:10.18653/v1/2020.emnlp-main.550. URL https://aclanthology.org/2020.emnlp-main.550/.DOI
  21. [21]Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning, pp. 282–293. Springer, 2006.
  22. [22]Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming-Wei Chang, Andrew M. Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov. Natural questions: A benchmark for question answering research. Transactions of the Association for Computational Linguistics, 7:452–466, 2019. doi:10.1162/tacl_a_00276. URL https://aclanthology.org/Q19-1026/.DOI
  23. [23]Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
  24. [24]Weizhen Li, Jianbo Lin, Zhuosong Jiang, Jingyi Cao, Xinpeng Liu, Jiayu Zhang, Zhengjiang Huang, Qianben Chen, Weichen Sun, Qiexiang Wang, Hongxuan Lu, Tianrui Qin, Chenghao Zhu, Yi Yao, Shuying Fan, Xiaowan Li, Tiannan Wang, Pai Liu, King Zhu, He Zhu, Dingfeng Shi, Piaohong Wang, Yeyi Guan, Xiangru Tang, Minghao Liu, Yuchen Eleanor Jiang, Jian Yang, Jiaheng Liu, Ge Zhang, and Wangchunshu Zhou. Chain-of-agents: End-to-end agent foundation models via multi-agent distillation and agentic rl, 2025a. URL https://arxiv.org/abs/2508.13167.
  25. [25]Xiang Li, Yucheng Zhou, Xiangzhi Wei, Zesheng Shi, Haiyuan Wan, Gong Yifan, Fangming Liu, and Jing Li. Llm inductive reasoning through multi-agent enhanced monte carlo tree search. In Findings of the Association for Computational Linguistics: ACL 2026, pp. 23548–23562, 2026.DOI
  26. [26]Yizhi Li, Qingshui Gu, Zhoufutu Wen, Ziniu Li, Tianshun Xing, Shuyue Guo, Tianyu Zheng, Xin Zhou, Xingwei Qu, Wangchunshu Zhou, Zheng Zhang, Wei Shen, Qian Liu, Chenghua Lin, Jian Yang, Ge Zhang, and Wenhao Huang. Treepro: Bridging the gap of policy optimization and efficacy and inference efficiency with heuristic tree-based modeling, 2025b. URL https://arxiv.org/abs/2508.17445.
  27. [27]Sam Lobel, Akhil Bagaria, and George Konidaris. Flipping coins to estimate pseudocounts for exploration in reinforcement learning. In International Conference on Machine Learning, pp. 22594–22613. PMLR, 2023.
  28. [28]MAA. American invitational mathematics examination (aime), 2025. https://maa.org/.
  29. [29]Alex Mallen, Akari Asai, Victor Zhong, Rajarshi Das, Daniel Khashabi, and Hannaneh Hajishirzi. When not to trust language models: Investigating effectiveness of parametric and non-parametric memories, 2023. URL https://arxiv.org/abs/2212.10511.
  30. [30]Georg Ostrovski, Marc G Bellemare, Aäron Oord, and Rémi Munos. Count-based exploration with neural density models. In International conference on machine learning, pp. 2721–2730. PMLR, 2017.
  31. [31]Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A. Smith, and Mike Lewis. Measuring and narrowing the compositionality gap in language models, 2023. URL https://arxiv.org/abs/2210.03350.
  32. [32]Zhenting Qi, Mingyuan Ma, Jiah​​ang Xu, Li Lyna Zhang, Fan Yang, and Mao Yang. Mutual reasoning makes smaller LLMs stronger problem-solvers. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=6aHUmotXaw.
  33. [33]Tianhao Qian, Jiayu Chen, and Lix​​i Wang. Pac-cf: Calibrating irreversible frontier pruning in llm-guided search, 2026. URL https://arxiv.org/abs/2604.14345.
  34. [34]John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.arxiv.org/abs/1707.06347
  35. [35]Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Yang Wu, et al. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300, 2024.
  36. [36]David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484–489, 2016.
  37. [37]Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. MuSiQue: Multihop questions via single-hop question composition. Transactions of the Association for Computational Linguistics, 2022.
  38. [38]Ante Wang, Linfeng Song, Ye Tian, Dian Yu, Haitao Mi, Xiangyu Duan, Zhaopeng Tu, Jinsong Su, and Dong Yu. Don’t get lost in the trees: Streamlining llm reasoning by overcoming tree search exploration pitfalls. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 23946–23959, 2025.
  39. [39]Liang Wang, Nan Yang, Xiaolong Huang, Binxing Jiao, Linjun Yang, Daxin Jiang, Rangan Majumder, and Furu Wei. Text embeddings by weakly-supervised contrastive pre-training, 2024. URL https://arxiv.org/abs/2212.03533.
  40. [40]Fang Wu, Weihao Xuan, Heli Qi, Aaron Tu, Ximing Lu, Li Erran Li, and Yejin Choi. Deepsearch: Overcome the bottleneck of reinforcement learning with verifiable rewards via tree-based search. In The Fourteenth International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=KxOG6v2c2S.
  41. [41]Yuxi Xie, Anirudh Goyal, Wenyuе Zheng, Min-Yen Kan, Timothy P Lillicrap, Kenji Kawaguchi, and Michael Shieh. Monte carlo tree search boosts reasoning via iterative preference learning. arXiv preprint arXiv:2405.00451, 2024.
  42. [42]An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengен Huang, Chenxu Lv, et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388, 2025a.arxiv.org/abs/2505.09388

Paper details

vlnc:W_p5gjhzde
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents