Wider or Deeper?  Scaling LLM Inference-Time Compute with Adaptive Branching Tree Search
Authors: Yuichi Inoue
Kou Misaki
Yuki Imajuku
So Kuroki
Taishi Nakamura
Takuya Akiba
Venue: NeurIPS 2025 spotlight ()
Keywords: inference-time compute
tree search
LLMs
programming
reasoning
Primary area: deep_learning
TL;DR: Adaptive Branching MCTS, a novel inference-time framework for LLMs, generalizes repeated sampling with multi-turn exploration and exploitation.

Abstract: Recent advances demonstrate that increasing inference-time computation can significantly boost the reasoning capabilities of large language models (LLMs). Although repeated sampling (i.e., generating multiple candidate outputs) is a highly effective strategy, it does not leverage external feedback signals for refinement, which are often available in tasks like coding. In this work, we propose Adaptive Branching Monte Carlo Tree Search (AB-MCTS), a novel inference-time framework that generalizes repeated sampling with principled multi-turn exploration and exploitation. At each node in the search tree, AB-MCTS dynamically decides whether to ''go wider'' by expanding new candidate responses or ''go deeper'' by revisiting existing ones based on external feedback signals. We evaluate our method on complex coding and engineering tasks using frontier models. Empirical results show that AB-MCTS outperforms both repeated sampling and standard MCTS, underscoring the importance of combining the response diversity of LLMs with multi-turn solution refinement for effective inference-time scaling.

Wider or Deeper? Scaling LLM Inference-Time Compute with Adaptive Branching Tree Search
Yuichi Inoue", Kou Misaki", Yuki Imajuku, So Kuroki, Taishi Nakamura, Takuya Akiba
Sakana AI, Japan
fy. inoue, takiia/asaaaaaaaaaaa.mm
Abstract
Recent advances demonstrate that increasing inference-time computation can signif- icantly boost the reasoning capabilities of large language models (LLMs). Although repeated sampling (i.e., generating multiple candidate outputs) is a highly effec- tive strategy, it does not leverage external feedback signals for refinement, which are often available real tasks like coding. this work, we propose Adaptive Branching Monte Carlo Tree Search (AB-MCTS), novel inference-time frame- work that generalizes repeated sampling with principled multi-tuna exploration and exploitation. At each node in the search tree, AB-MCTS dynamically de- cides whether to "go wider" by expanding new candidate responses or "go deeper" by revisiting existing ones based external feedback signals. We evaluate method on complex coding and engineering tasks using frontier models. Empirical results show that AB-MCTS outperforms both repeated sampling and standard MCTS, underscoring the importance of combining the response diversity of LLMs with multi-turn solution refinement for effective inference-time scaling. Code is available at: https:/ /ttp:///gtthb... com/ Sa SaaaaaaaT/teeeeeeeesss
Introduction
Recent work has shown that inference-time scaling, namely allocating more computation at inference time, can markedly boost the performance of large language models (LLMs) on complex tasks. As outlined in Section existing approaches inference-time scaling fall into three broad categories: (/) post-training fine-tuning, (2) reward-guided chain-of-thought (CoT) generation, and (3) multiple answer generation. In this paper, we focus on the third category. The multiple answer generation approach repeatedly queries an LLM at non-zero temperature to produce a set of candidate outputs and then selects the most promising one. This approach enhances the LLM's problem-solvine abilities on-the-fly fly. without further training [I] Because it is orthogonal to the other two families, it can be seamlessly combined with them.
The most widely successful approach in this category is repeated sampling. which includes techniques such best-of-n sampling, majority voting, and self-consistency [2 [2 In repeated sampling, an LLM at non-zero temperature generates multiple candidate outputs independently from the same initial prompt, and final solution is selected, typically by simple heuristic. This paradigm has proved effective on challenging benchmarks, including coding competitions [3] and ARC-AGI (13). The strategy leverages the diverse and vast output space exposed by LLM generation, and sampling more responses increases the odds that one of them is high-quality. The empirical success of repeated sampling underscores that harnessing this diversity is central effective inference sitreneee-imeeeeee scaling.
However, repeated sampling focuses exclusively on exploration and lacks an explicit mechanism for exploitation. In certain real-world scenarios,
obtain external feedback on candidate
"qqual contribution. See author contributions for details.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Baseline Repeated Sampling
Baseline 2: Sequential Refinement
Task Prompt
Tark Promot
Refine u-1 times
Inital Answer
Ansovers
Refined Answer
Sample a answers
Repeated sampling goes pure exploration)
Sequential refinement only goes deep the. pure exploitation)
Baseline 3: Standard MCTS
Ours: Adaptive Branching MCTS
Fixed branching factor example)
Branch adaptively appropriste
MCTS expands a node at most once with a fixed width
AB-MCTS systematically decides whether go vider or deeper
Figure 1: Visual comparison of AB-MCTS vs. baselines. Unlike baselines that are purely wide (repeated sampling), purely deep (sequential refinement), axxddwidthh (standard MCTS), AB- MCTS dynamically decides whether branch outward or drill down, unifying both search directions.
tests to evaluate the correctness of generated programs and gather feedback on how to improve them 14). In such settings, it is natural to select promising solutions and refine them based on available feedback, which repeated sampling alone cannot accomplish effectively.
solution. For instance. in coding tasks,
Several approaches 6 multi-turn settings, but the majority were designed before the power inference-time scaling was fully recognized. Consequently, these methods use fixed "width", i.e., they treat the number of answers generated from a single prompt as a fixed hyperparameter. For example, methods based standard Monte Carlo Tree Search (MCTS) use fixed branching factor (i.e., the number of child nodes per state) as a hyperparameter I [5]. As demonstrated by the success of repeated sampling, effective inference-tie time scaling requires leveraging diverse and vast output space, thus, providing substantial evidence that a fixed width hinders scaling.
15 have been proposed for exploration and exploitation in such
In this work, we propose Adaptive Branching Monte Carlo Tree Search (AB-MCTS), novel inference- time framework that generalizes repeated sampling with multi-turn exploration and exploitation (Figure DT. The main technical challenge is to introduce unbounded branching into MCTS. Unlike traditional MCTS, AB-MCTS does not fix the width as static hyperparameter. Instead, at each node of the search tree, AB- ABMCTT adaptively decides whether to explore ("go wider") by generating new candidate responses or exploit ("go deeper") by refining existing ones, leveraging external feedback signals. Under the hood, formalize our decision process via Bayesian posterior updates, ensuring each expansion balances exploration and exploitation a principled manner. This design naturally extends repeated sampling, allowing to harness the diverse and vast output space of LLMs when necessary. Consequently, our framework provides a powerful mechanism for balancing exploration and exploitation in the context of LLM inference-tima scaling.
evaluated AB-MCTS on complex coding and machine learning engineering benchmarks [ as well as ARC-AGI 17. using frontier models such as GPT-4o [18] and DeepSeek-V3 V3 [19]. in scenario that scales up inference-time compute by allowing multiple generation calls for each task instance. Under the same computational budget, AB-MCTS achieved better results than previous approaches, such as repeated sampling and standard MCTS.
Contributions. ! We highlight the challenge of effectively incorporating unbounded branching into tree search. This pivotal for combining the power of the diverse and vast output space of LLMs, cornerstone of inference-time scaling, with solution refinement. introduce AB-MCTS. which systematically decides whether to "go wider" or "go deeper." We present two variants, AB-MCTS-M and AB-MCTS-A, based on different principles, each offering distinct trade-offs. 3 In a practical setting using frontier models and real-world complex tasks, we show that AB-MCTS outperforms existing methods.
② To address this challenge, we

---

2 Related Work
Inference-Time Scaling by Post-Training Fine- Sine-Tuning. Recent post-training work, exemplified by OpenAl o1/o3 [20 2T, uses reinforcement learning or supervised CoT fine-tuning to deepen LLM reasoning and boost single-answer quality |0|255 Our approach instead generates many candidates and refines them with external feedback. pursuing a complementary objective.
Inference- TimeeneceeTieeee&& Scaling via Reward-Guided CO'.. Reward-guided CoT scales inference by search- ing one step (typically sentence) at a time 226 34 Primarily for math tasks, aims to improve single-anse answer quality, making it orthogonal to our multiple-answer generation approach.
Inferenee-Time Scaling by Multiple Answer Generation. Since the community has come to appreciate the power of inference-time scaling, the strategy that has been studied widely is repeated sampling, in which the model generates many candidate answers and selects the best one [333 35.. Although empirically strong and widely used, repeated sampling leaves obvious room for improvement because does not refine its candidates using external feedback 5]. Before the era of large-scale inference-ting compute, a variety of task-specific strategies were proposed for relatively small scales; examples include tree expansions directed by LLMs 6 and Bayesian methods [7]. LATS 19]. RAP [15., SWE-Search [10]. and Repo
[1 combine LLMs with MCTS, primarily targeting sequential decision making. In this context, nodes represent states and edges represent actions, which may involve interaction with an environment. LATS utilizes API calls and code execution as actions to solve tasks. RAP addresses the process of solving block-moving puzzles and mathematical word problems step-by-step SWE-Search explores sequences of actions such as searching. editing, and running tests to resolve issues within software repository. RepoUnderstander employs MCTS for exploration on a repository knowledge graph. 'The application of LATS to coding tasks O Section 5.2] aligns with the context of multiple-answer generation in this paper and corresponds to what we refer to "standard MCTS" in our experiments.
is a classic technique that gradually increases actions considered per node. It was designed for games with unique actions and no side information for untried moves, relying on visit-count heuristics. Complementary to PW, Sokota et al. (38] propose "abstraction refining", which groups similar successors using decreasing similarity threshold and shows advantages over PW under equal simulation budgets in stochastic domains. Our approach differs as new branches are sampled from the same LLM. This homogeneity in generation allows a principled statistical rule for choosing between widening and deepening.
Progressive Widening in MCTS. Progressive widening (PW)
36 37
3 Method
3.1 Preliminaries
First, we introduce the setup and notation. with detailed claboration provided in Appendix A.I We consider setting where an LLM, represented by a function fLLM, receives a textual prompt fin containing (1) task instructions with optional few-shot examples, and/or (2) previously generated outputs along with external feedback, and generates an answer fout fLLM (f.)) A scoring function R then evaluates an answer fout to produce score r = R(fout), where higher scores indicate better performance. We typically assume that the score is normalized to the range [0, 1), but our framework allows for arbitrary ranges as well. Our goal is to find an output four. that attains high score under limited calls to the LLM at inference time. Such tasks arise, for example, code generation, where the correctness or quality of the output can be quantified; for instance, R may execute the generated code and return the fraction of test cases passed. In some cases, the true score evaluator may be inaccessible (c.g., hidden test cases), so assume we have access to some surrogate partial evaluator R, such as a public test evaluator, during the search. We aim to leverage this evaluator to guide an efficient search for better solutions.
3.2 Adaptive Branching MCTS
MCTS for LLM-bbssed Answer Generation. We perform the answer search by constructing search tree T, in which each non-root node N is associated with an L.M--genertee answer to a given task. Our goal is to construct I' so that it contains answers with scores as high as possible.
3

---

AB-MCTS-M Example Tree
Posterior Predictive Distribution
N
2
a,
3
3
N,
N
N
GEN
110
GEN
GEN
0.0
0.5
1.0
T [
T (
Figure 2: Example tree structure and score posterior predictive distributions for AB-MCTS with mixed models (AB-MCTS-M), Here, aj leads to a set child nodes with higher scores, causing a peak larger As more child samples collected, the variance of the distribution decreases.
Algorithm 1 Adaptive Branching MCTS
1: function (F
2: T + INITIALIZETREE(
3: for nl = 1, RRodess do
4- SELECCEXPANSONTAGGETC Nnww +- EXPAND(V, T)
Step 1. Select an expansion target b. Step Expand the selected node to generate a child
6: SCOREBACKUP(MM, 7)
b Step 3. Backup the score from the generated node
7:
return SELECTBEST(T)
8: function SELECTEXPANSIONTARGEENN
9: N + GETROOT(T)
10:
while not IsLEAF(N) do
Nuea SELECTCHILDDN,, T)
Detailed Sections
12:
ISGENNODE Nuea) then break
If GEN node is selected, branch off from the node
13:
14:
N < Nu
15:
return N
For this purpose, we employ MCTS, formulated iteratively as follows. Starting from a single root node, we perform moddes iterations, each adding one new node, resulting in a total of 1 Tmnoes nodes. Each iteration has three steps: (1) Selection, where we select node N for expansion; (2) Expansion, where we expand N by generating new answer from node N, creating a new child node Neew and appending it to N. Specifically, if N is the root, the new answer is directly generated from the task prompt; N is non-root, the new answer refines the answer associated with N, using external feedback; and (3) Score backup, where propagate the score of Nuew up toward the root of the tree T' We adopt different backup rules in our proposed methods (see Section 3.3 and 3.4 In our setting, separate rollout is needed, since each node's 's score r can be evaluated directly once output generated. After Rruudes iterations, we select the best node based on chosen criterion.
In standard MCTS, only leaf nodes are selected and expanded, (i.e., each node is expanded at most once), and the expansion adds fixed number of child nodes. However, since each query to an LLM at non-zero temperature can yield different outputs from the same prompt, the branching factor is theoretically infinite. To accommodate such unbounded branching. we relax the standard MCTS constraints and allow selection and expansion of non-leaf nodes. Moreover, recent studies 3 suggest that drawing many outputs from the same prompt at non-zero temperature can improve performance. Allowing unbounded branching enables to fully exploit these varied samples, whereas restricting the branching factor could miss correct answer generations and undermine overall performance.
A daptive Branching via the GEN Node. To fully leverage the potential performance improvement from unbounded branching, we allow nodes that have already been expanded once to be expanded again and further branched, unlike in standard MCTS. To explicitly represent the action of generating new child nodes, we introduce GEN node. Every node N (including newly expanded ones during iterations) has GEN node as child. When the GEN node with parent node N is selected during the selection step, we expand N by adding a new child node. Algorithm outlines this approach, called Adaptive Branching Monte Carlo Tree Search (AB-MCTS).

---

The only remaining component we need is selection policy, including when to select a GEN node. We propose two algorithms with different selection policies: AB-MCTS-N M (Mixed model) and AB-MC7S-A (node Aggregation). Both follow the overall procedure in Algorithm [ and use Thompson sampling to balance exploration and exploitation.
The UCT score is inapplicable to our AB-MCTS because GEN nodes make the problem fundamentally different from standard multi-armed bandit problem, for which UCT was designed. In standard MCTS, the arms (branches) are static. In contrast, the GEN node in AB-MCTS dynamically generates new arms, This special problem setting, where arms are generated on the fly, prevents the direct application of UCT. We, therefore, adopt Bayesian probabilistic model. This enables Thompson sampling based on the posterior distribution and obviates the need for complex UCB-style confidence bound analysis.
Thompson Sampling for Node Selection. In our proposed methods, we employ Bayesian approach with Thompson sampling for node selection. Here, we employ Thompson sampling because GEN nodes do not have child nodes, making it impossible compute their UCT scores. In addition, Thompson sampling has the advantage of allowing node expansion in parallel. This is particularly beneficial when evaluating node scores time-consuming, in the case of MLE-Bench (See Appendix
B.I for MLE-Bench details).
Concretely, during Select Chile ld step line of of Algorithm [ we employ Thompson sampling to decide between expanding a GEN node or selecting from existing child nodes at node N. Let N be node with potential actions
AN = {ao, a1.... Omamna J:
where the action dg corresponds to choosing the GEN node, and ai..... anaga correspond to choosing the already-existing child nodes. Suppose Px(r as)) is the posterior predictive distribution of the score r for eventually expanded new node (Nnew at line 5) Algorithm 1 if we choose the action ag at node N. Then Thompson sampling proceeds by,
1. Calculate (v(r az) for each action aj at node N.
2. Draw scores aN from (x az) for each action aj-
3. Select arg ma ay
This three-step process corresponds to single call to SelectChild.
A key question is how to perform step i.e., how to model and calculate Pv (r a.) for all aj. in particular for j = 0 (i.e., GEN node). We address this with two strategies: a mixed Bayesian model (AB-MC7S-M) and node aggregation method (AB-MCTS-A). In both cases, we model the score probability distributions by Bayesian posterior predictives, but with different statistical models.
3.3 AB-MCTS-M: Adaptive Branching MCTS with Mixed Model
To model (r (r az), we employ node-specific mixed model fitted individually at each node N. That is, we fit a separate model for each N every time SelectChi 1d in Algorithm Iis invoked. Denoting aa
Px (r a,) as a score of an eventually expanded node New if we choose an action aj at N, our mixed model given as:
TN = Otj + TyENNar 0gj No Jatjo
CN ~ N0,,1), ey ~0,N(0,1))
Here, ay is a "group-level" intercept capturing the quality of the base solution at Nj, while E represents per-instance noise. To fit this model, place priors the hyperparameters (Ma. Jas a.)) and employ Markov Chain Monte Carlo (MCMC) to sample from their posterior distribution. The GEN node (action an) is treated as newly introduced group without its direct observations. However, its group-level intercept Orp is inferred not from the prior alone but rather from the posterior distribution Ha and da, which is informed by the other observed data. We assume that even after multiple refinement stages, the quality associated with the answer at node N, continues to be captured by this shared parameter (see Appendix A.3.2 for further details).
Algorithm Outline. To model (r (a;), AB-MCTS-M assigns each subtree under Ny. denoted as Tab (Ny), as distinct group j (see Figure 2 for example subtree). The mixed model leverages
5

---

observed scores from these groups to compute the posterior predictive distributions of expected scores for new nodes generated from each group (See Figure 2 for a schematic illustration). We sample the scores from all the groups (the GEN node and sith (2))) using calculated posterior predictives. If the GEN node's sampled score is highest, we call fLLM to generate a new child node. Otherwise, we choose the child node N₂ with the highest score and continue the sampling step.
Score Backup Mechanism. When new node N is created, its observed score is added to the histories of N and its ancestors. This cumulative record is used to update the posterior distributions in the mixed model. The observed score not backed up GEN node, but it indirectly influences the GEN node's 's score probability distribution through the shared parameters in the mixed model (see Appendix (A.5diiXAA3]eeee for a detailed walkthrough).
3.4 AB-MCTS-A: Adaptive Branching MCTS with Node Aggregation
In AB-MCTS-M -M, during the selection step at N, we use a mixed model that shares statistical strength across groups through the shared model parameters. In contrast, AB- AB-MCTS-A is designed in the same spirit as the standard UCT-based MCTS, and there are no shared model parameters among the different actions. This design simplifies the statistical modeling and makes the computation more lightweight compared to AB-MCTS-M.
The major problem is how to back up scores to GEN nodes. Since the generated node is not attached as a child to a GEN node, it makes the backup of scores difficult to define. Here, we introduce CONT node at the same tree level all the GEN nodes (see Figure B Intuitively, the CONT node represents the action of continuing refinement from the current answer at node N, rather than generating new node. By explicitly separating these two actions genneraing new answers (GEN) and refining existing answers (CONT)-we create a clear path for score propagation. Specifically, the score of the expanded node is first backed up to the GEN node, and since all ancestors of the GEN node are either nodes with LLM answers or CONT nodes, the score subsequently does not propagate through other GEN nodes (see Figure 3 for an example tree).
Algorithm Outline. AB-MCTS-A aggregates all child nodes under single CONT node, which represents refinements from existing child nodes (see Figure 3). We model each node's score probability in a Bayesian framework and posterior pre- dictives to decide between generating a new child (GEN) or refining an existing one (CONT). In contrast to AB-MCTS-M, we do not use shared parameters among different node proba- bility distributions.
AB-MCTS-A Example Tree
N
perform Thompson sampling
GEN
CONT
B
r-
r
GEN
CONT
GEN
GEN
CONT
0-0.8
1-0
00
To model (N(r a,). we utilize exponential family distributions with conjugate priors, en- abling analytical and efficient posterior updates. We employ two variants:
Figure 3: Example tree structure for AB-MCTS- A. All child nodes are aggregated under a CONT node, and GEN node doesn't 't have child nodes.
1. AB-MCTS-A (Gaussian), using normal-inverse-y 2 prior for unbounded scores: (N a²) = =p(r| {rx)<=)) = [N(rr m, ) x=)x2(()) 2002 Dù f²), and
2. AB-MCTS-A (Beta), using a Beta prior for scores in [o, 1]: Px(r (a,) p(r (ra)ken) (rr à,
where Th represents the scores backed up to the node N₂ (GEN node, CONT node or LLM-generated child nodes; see Figure 3 for example tree), where m. R, 8, f, a, 9 are determined from observed scores F%k and updated as these scores are backed up. The detailed parameter update rules are given in Appendix A.4
Score Backup Mechanism. During score-backup operations, the expanded node score is backed up to the GEN node which led to the expansion of that node and the GEN node's ancestors (see Appendix A.3 for a detailed walkthrough). As we can see from Figure 3 a GEN node's ancestors include only generated nodes and CONT nodes, so the score is backed up to GEN node only from

---

Table Performance of AB-MCTS against baselines across benchmarks and models. This table compares AB-MCTS with the baseline methods. Evaluations were performed on LiveCodeBench. CodeContest, and ARC-AGI using GPT-4o and DeepSeek-Ve V3 with maximum generation budget (2"). Each entry provides performance score (higher values are better) and its corresponding rank (in parentheses, 1st is best). The "Avg. Rank" column shows the average rank across all settings.
LiveCodeBench
CodeContest
ARC-AGI
Avg. Rank
Method
GPT-4o DeepSeek-V3
GPT-4o
DeepSeek-V3
GPT-4o
DeepSeek-
Repeated Sampling
37.8 0.5 (4) 40.7 : (6) 37.9 03
43.2 0.9 (S) 15.0 :: 1.0 (1) 18,6 (1)
3.5
Sequential Refinement
37.8 + 24 (4) 41.6 (5) 30.1 +03
49 (6) 0.7 (6) 10.0 +0 (6)
5.5
Standard MCTS
36.7 + 1.0 (6) 43.2 37.
43. +09
150=15
15
4.2
AB-MCTS-M
38.9 19 (2) 43.0
1 (0) 44.6
(2.3
11.0
2.3
AB-MCTS-A (Gaussiin)
39.1 +: 1.9 (1) 45 40.2 H (7) (49 13.0
18.3
1 (2)
2.7
AB-MCTS-A (Beta)
38.7 (3) 42.3 +08 40.4 03 (2) 44.8 0.6 (I) 14.0
16.6 0. (4)
2.7
the node that is created by choosing that GEN node. The backed-up score is used to update prior probability distribution parameters.
4 Experiments
4.1 Experimental Setup
Benchmarks. We evaluated AB-MCTS on four diverse benchmarks that require complex problem- solving: LiveCodeBench 14] CodeContest (1, ARC-AGI (17), and MLE-Bench [16]. Live- CodeBench and CodeContest consist of competitive programming problems that demand mathe- matical and algorithmic reasoning. ARC-AGI involves abstracting a common transformation rule from visual patterns and implementing it as code. MLE-Bench, derived from Kaggle competitions, involves constructing and optimizing machine learning models to achieve high scores based on the evaluation metrics of each competition. For all these benchmarks, LLMs generate Python code to solve each task, and external feedback (e.g., test case results, validation scores) is available to guide the search. More details on the benchmarks can be found in Appendix B.1
Models. We perform our experiments using GPT-4o 4011----------222-0------ 06) 18 and DeepSeek- V3 (deepseek-che) t.) 19. Each LLM generates a complete solution in single API call. We define the generation budget the maximum number of API calls and set it 2 128. The temperature was set to 0.6 for GPT-4o following ( and 1.0 for DeepSeck-V V3 following the official documentation.
Baselines. We benchmark AB-MCTS against three representative approaches. (1) Repeated Sam- pling (Best-of-n) B 39]
independently generates up candidate solutions from single LLM prompt, a simple yet competitive baseline for coding tasks. (2) Sequential Refinement [4] iteratively improves each solution by re- prompting the LLM with its own output and feedback. (3) Standard MCTS follows the configuration from LATS 9 Section 5.2) (See also Appendix [C.8). Each ex- pansion adds five child nodes, and the search proceeds until it reaches the 2 nodes, with the final expansion creating only three nodes to meet this limit precisely. Hyper-parameters for AB-MCTS are summarized in Appendix B.2
4.2 Results
As detailed in Tables T and 2 our comprehensive evaluations reveal AB- MCTS as a consistently superior ap- proach across diverse benchmarks and LLMs, achieving the top average rank and outperforning established base- lines. This consistent success stems from the distinctive ability of AB-
Table 2: Performance MLFE-Bench tasks. AB-MCTS-M demonstrates robust performance, achieving the best average rank across diverse ML tasks.
Method
Nomad2018
Spooky.
Pizza.
Avg.
Repeated Sampling Sequential Refinement
0.065 (3)
0.47 (4)
0.72 (2)
3.0
0.059 (1)
0.46 (3)
0.62 (3)
2.3
Standard MCTS
0.076 (4)
0.45 (2)
0.60 (4)
3.3
AB-MCTS M
0.060 (2)
0.38 (1)
0.72 (1)
1.3
7

---

LiveCodeBench (higher is better)
CodeContest (higher is better)
ARC-AGI (higher is better)
Success Rate (Pass
Success Rake (Pass(11)
Success Rate (Pacs(82)
9.12
Success Rate
Final Success Rate
9.00
Seceess
1.0
820
013
3.40
3.2
3335
0.00
3.50
2f
0.00
Generation Budget
Generation Budget
Generation Budget
Repeated Sampling
Sequential Refinement
MCTS
AB-MCTS-M
(GGusia))
AB-MCTS-A
Figure 4: Performance comparison on LiveCodeBench, CodeContest, and ARC-AGL. We compare the six methods using GPT-4o by plotting the success rate against the generation budget. The inset plots provide a detailed view of performance at a maximum generation budget (2"); the mean success rate, its 95% confidence interval, and the results from the individual runs shown. Variance at generation budget of arises from conducting each experiment independently with nonzero temperature. See Figure 6 for experiments ARC-AGI with larger budget.
LiveCodeBench (higher is better)
CodeContest (higher is better)
ARC-AGI (higher is better)
0.39
0.33
Success Rate (Pass@1)
Success Rate (Pass@11)
Success Rate (Pasv@2)
0.38
0.35
8.32
9.32
6.37
6.03
0.26
3.36
0.08
0.23
-2
0.20
2
0.03
Mean Depth Mean Width, (log2)
Mean Depth Mean Width, (log2)
Mean Depth / Mean Width, (log2)
Repeated Sampling
Sequential Refinement
Standard MCTS
AB-MO AB-MCTS-M
AB AB-MCTS-AR (Gaussian)
AB-MCTS-A (Beta)
Figure 5: Comparing algorithms by search tree shape and performance. Each point shows the performance against the average tree shape for a given algorithm at a specific generation budget. The x-axis represents the log-ratio of mean depth mean width. Mean width the average number of nodes per depth. Larger and smaller x-axis values indicate deeper and wider searches, respectively.
MCTS to dynamically adapt its search strategy by precisely balancing exploration and exploitation to the varying demands of each problem, adaptability largely absent in baseline methods. We next detail these results by benchmark, followed by an analysis of the search behavior of AB-MCTS.
LiveCodeBench and CodeContest. Figure 4 (left and center) reports the success rate (Pass @ 1) ver- sus the generation budget for GPT-4o on LiveCodeBench and CodeContest. As expected, all methods demonstrate improved performance with increasing computational budget. On both benchmarks, AB-MCTS algorithms generally outperform the bascline methods. Notably, on LiveCodeBench (Figure 4 left). AB-MCTS starts to pull ahead of the baselines even with small budget of 2 On CodeContest (FigureFcenta center). AB-MCTS demonstrates superior performance compared to baselines at larger budgets of 2n and beyond. Appendix Figure 8 shows that while standard MCTS performs relatively well with DeepSeek- V3 compared to GPT-4o, our proposed methods achieve a comparable success rate on LiveCodeBench and surpass standard MCTS on CodeContest.
(righe(((ight)) shows the performance on ARC-AGI, a particularly challenging bench- mark. Following ARC-AGI's official evaluation protocol, we report Pass@2 (Pass@1 is also reported Appendix (C6)). Consistent with previous work [33, repeated sampling proves to be strong baseline in our setup, indicating the importance of broad exploration for this task. While standard
ARC-AGI. Figure (right)

---

Random Acts of Pizza: AB-MCTS-M
0.78
0.76
4.72
0.70
Figure 7: Example search tree generated by AB-MCTS-M Random Acts of Pizza (MLE- Bench). The figure shows how AB-MCTS-M dynamically balances exploration and exploitation. Each node represents solution. Nodes are colored according to their evaluation score used as the search signal for AB-MCTS-M, The number inside each node indicates the order of generation. Grey nodes mark candidates whose code failed to execute and therefore received score.
MCTS yields only marginal improvements with larger budgets, our AB-MCTS framework achieves performance comparable to repeated sampling. This suggests AB-MCTS's capability to effectively explore potentially by dynamically widening its search when beneficial. Similar results were observed with DeepSeck- V3, as detailed in Appendix Figure
MLE-Bench. Table 2 and Appendix Figure 10 present the performance on three competitions from MLE-Bench using GPT-4o. Since MLE-Bench requires substantial GPU resources for training and evaluating machine learning models, we exclusively used GPT-4o and focused on the baseline methods and AB-MCTS-M (see also Appendix [B.I.. The best-performing baseline method varies across competitions. This again highlights that different tasks benefit from different exploration- exploitation trade-offs. In contrast, AB-MCTS-M consistently delivers strong performance these tasks. This consistent success across diverse competitions underscores AB-MCTS-M's inherent strength in effectively adapting search strategy to varying problem structures.
4.3 Analysis
Analysis of Search Behavior: Width vs.
ARC-AGI, Accuracy (higher is better)
Depth. To quantitatively analyze how AB-
MCTS balances exploration and exploitation, we examined the average depth and the average width each depth of the generated search trees. Figure shows that AB-MCTS methods tend to generate wider trees compared standard MCTS. This occurs because AB-MCTS can adaptively decide to explore wider (select the GEN node) from any existing node, unlike stan- dard MCTS. This mechanism allows for more flexible exploration across various tree depths (See also Appendix C.7). In addition to this flexibility in exploring wider, seen in Table 2 AB-MCTS also achieves strong performance on benchmarks where sequential refinement excels, suggesting that AB-MCTS effectively identifies and exploits promising branches by selecting existing child nodes for refinement. This adap- tive nature allows it to combine the strengths of exploration and exploitation, resulting in robust performance across diverse benchmarks.
Success Rate (Pass@2)
0:55
0.10
Repeated Sampling
Sequential Relinement
0.05
Standard MCTS
AB-MCTS-4 (Gaussian)
AB 10B-MCTS-A (Bess)
Generation Budget
Figure 6: Performance comparison ARC- AGI with increased budget. Scalability of AB- MCTS
assessed with generation budget ex- tended up to 512. Plotted points represent moving averages clarify performance trends.
Scaling with Increased Budget. Highly complex problems often require a substantial generation budget find correct solution. ARC-AGI prime example, where extensive exploration via repeated sampling is known to improve performance even at large budgets as reported in [3]. To investigate the scaling properties of our approach, we extended the experiments on ARC-AGI using DeepSeck-V. V3 with a larger generation budget up to 2 512. As shown in Figure the performance

---

of AB-MCTS continues to improve substantially as the budget increases from 200 to 500, while the improvement rate of repeated sampling begins to plateau. Standard MCTS also continues to improve with larger budget, yet shows a significantly lower success rate compared to the AB-MCTS methods. This performance gap highlights that AB-MCTS is more effective directing its search towards promising branches within the search tree at large computational scales.
Qualitative Analysis of the Search Trees. Figure 7 and Appendix Figure II present example search trees generated by AB-MCTS-M and standard MCTS. These visualizations illustrate more adaptive branching by AB-MCTS-M compared to standard MCTS. This adaptive nature reveals that AB- MCTS-M flexibly balances exploration and exploitation throughout the search process, dynamically allocating budget to explore diverse new candidates ("going wider") and refine promising ones ("going deeper"). Further discussion can be found in Appendix C333
Efficiency and Performance against Repeated Sampling. While repeated sampling benefits from potential efficiencies such as parallel sampling and no feedback computation costs, our results demonstrate the significant advantages of AB-MCTS. On ARC-AGI, where repeated sampling is notably strong, AB-MCTS not only continues to improve with increased budget but also ultimately achieves performance levels that repeated sampling cannot reach (Figure (b. Furthermore, on LiveCodeBench and CodeContest, AB-MCTS variants can reach the peak performance of repeated sampling substantially earlier in many cases (Figure 4 Appendix Figure 8). This indicates that even when accounting for the inherent advantages of repeated sampling, AB-M AB-MCTS emerges as promising approach to efficiently use the generation budget to achieve superior results in diverse scenarios.
5 Conclusions
This paper introduced Adaptive Branching Monte Carlo Tree Search (AB-MCTS), novel inference- time framework to enhance L.M performance on complex tasks by effectively integrating multi-turn exploration and exploitation. Unlike previous methods, AB-MCTS dynamically decides to "go wider" or "go deeper" based on external feedback, leveraging Bayesian decision-making Our experimental results show AB-MCTS outperforms repeated sampling and standard MCTS, demonstrating the value of adaptively handling the challenge of unbounded branching for effective inference-time scaling.
Limitations. Our approach assumes the existence of reliable score evaluator, but developing such an evaluator itself can be challenging depending on the task. Future work could also explore search strategies that incorporate more fine-graii -eeaginnedd real-world cost factors beyond API call counts, potentially enhancing the practical utility of AB-MCTS. We believe that addressing these challenges will further enhance the applicability of AB-MCTS across wider range of problems.
Author Contributions
Kou Misaki co-designed AB-MCTS and implemented its algorithm and core experimental code. Yuichi Inoue designed and led the experiments, proposed and conducted the experimental analysis, and co-led experimental code development. Yuki Imajuku conducted the CodeContest and Live- CodeBench experiments and co-led experimental code development. So Kuroki implemented and conducted the MeLE-Bench experiments. Taishi Nakamura conducted the ARC-AGI experiments. Takuya Akiba initiated the project, co-designed AB-MCTS, advised on experimental code design, and provided overall supervision. All authors contributed to experimental code development, results interpretation, and manuscript refinement.
Acknowledgements
The authors would like thank Edoardo Cetin, Luke Darlow, Taro Makino, Kosuke Nakago, Makoto Shing, and Yutaro Yamada for helpful feedback on an earlier version of the draft.
References
[1] Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. Competition-level code
10

---

generation with alphacode. Science, 37866624):1092-1007 2022.
[2] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consisteney improves chain of thought reasoning in language models. In International Conference on Learning Representations, 2023.
[3] Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoe V Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787, 2024.
[4] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, al. Self-refine: Iterative refinement with self-feedback. Advances in Neural Information Processing Systems, 36, 2024.
[5] Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 2024.
[6] Jierui Li, Hung Le, Yingbo Zhou, Caiming Xiong, Silvio Savarese, and Doyen Sahoo. CodeTree: Agent-guided tree search for code generation with large language models. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics:
Human Language Technologies (Volume 1: Long Papers), pages 3711 171167,6, 2025.
[7] Hao Tang, Keya Hu, Jin Peng Zhou, Si Cheng Zhong, Wei-Long Zheng, Xujie Si, and Kevin Ellis. Code repair with LLMs gives exploration-exploitation tradeoff. In Advances in Neural Information Processing Systems, 2024.
[8] Kuang- Huei Lee, Ian Fischer, Yueh-Hua Wu, Dave Marwood, Shumeet Baluja, Dale Schu- urmans, and Xinyun Chen. Evolving deeper Ilm thinking. arXiv preprint ttXiv:250100955 2025.
[9] Andy Zhou, Kai Yan, Michal Shlapentokh-Rothhnn Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning, acting, and planning in language models. In International Conference on Machine Learning, 2024.
[10] Antonis Antoniades, Albert Örwall, Kexun Zhang, Yuxi Xie, Anirudh Goyal, and William Yang Wang. SWE-search: Enhancing software agents with monte carlo tree search and iterative refinement. International Conference on Learning Representations, 2025.
[11] Yingwei Ma, Qingping Yang, Rongyu Cao, Binhua Li, Fei Huang, and Yongbin Li. How to understand whole software repository? arXiv preprint arXiv:2406.01422. 2024.
[12] Zhenwen Liang, Ye Liu, Tong Niu, Xiangliang Zhang, Yingbo Zhou, and Semih Yavuz. Im- proving IIm reasoning through scaling inference computation with collaborative verification. arXiv preprint arXiv:2410.05318, 2024.
[13] Ryan Greenblatt.
Getting 50%
(sota) on arc-agi with gpt-4o.
https: www.wwwwoo....ggg..oooooommm com wtw/post /twwwuwwiii 3wH.CeKb BocK7ffeK.
getting 50 sota on are agi with gpt 40) 2024.
Accessed: January 21,
2025.
[14] Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Ar- mando Solar-Lezama, Koushik Sen, and Ion Stoica. Livecodebench: Holistic and contamination free evaluation of large language models for code. In International Conference on Learning Representations, 2025.
[15] Shibo Hao, Yi Gu, Haodi Ma, Joshua Hong. Zhen Wang, Daisy Wang, and Zhiting Hu. Rea- soning with language model is planning with world model. In Empirical Methods in Natural Language Processing, pages 8154 8173, 2023.
[16] Jun Shern Chan, Neil Chowdhury, Oliver Jaffe, James Aung, Dane Sherburn, Evan Mays, Giulio Starace, Kevin Liu, Leon Maksin, Tejal Patwardhan, Aleksander Madry, and Lilian Weng. MLEh-bech: Evaluating machine learning agents on machine learning engineering. In International Conference Learning Representations, 2025.

---

[17] François Chollet. On the measure of intelligence. arXiv preprint arXiv: 111.v:191..01547,. 2019.
[18] OpenAl. Gpt-4o system card. arXiv preprint arXiv:2410.21276, 2024.
[19] DeepSeek-AI. Deepseek-v3 technical report. arXiv preprint 2rX1v:2412.19437,,
[20] OpenAl. Openai ol system card. arXiv preprint arXiv:2412.16720, 2024.
[21] OpenAL. Competitive programming with large reasoning models. arXiv preprint arXiv:2502.06807,, 2025.
[22] DeepSeek-Al. Deepseek-rl: Incentivizing reasoning capability Ilms via reinforcement learning. arXiv preprint arXiv:2501. 2025.
[23] Yixin Ye, Zhen Huang, Yang Xiao, Ethan Chern, Shijie Xia, and Pengfei Liu. Limo: Less is more for reasoning. arXiv preprint arXiv:2502.03387, 2025.
[24] Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannanch Hajishirzi, Luke Zettlemoyer, Percy Liang, Emmanuel Candès, and Tatsunori Hashimoto. sl: Simple test-time scaling. arXiv preprint arXiv:2501.1939) 2025.
[25] Kimi Team. Kimi k1.5: Scaling reinforcement learning with 1lms. arXiv preprint arXiv:2501.122 12599, 2025.
[26] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances in Neural Information Processing Systems, 2024.
[27] Charlie Victor Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling test-time compute optimally can be more effective than scaling LLM parameters. In International Conference on Learning Representations, 2025.
[28] Guoxin Chen, Minpeng Liao, Chengxi Li, and Kai Fan. Alphamath almost zero: Process supervision without process. In Advances in Neural Information Processing Systems, 2024.
[29] Bofei Gao, Feifan Song, Zhe Yang, Zefan Cai, Yibo Miao, Qingxiu Dong, Lei Li, Chenghao Ma, Liang Chen, Runxin Xu, et al. Omni-MATH: A universal olympiad level mathematic benchmark for large language models. In International Conference on Learning Representations, 2025.
[30] Yu Zhao, Huifeng Yin, Bo Zeng, Hao Wang. Tianqi Shi, Chenyang Lyu, Longyue Wang, Weihua Luo, and Kaifu Zhang. Marco-ol: Towards open reasoning models for open-ended solutions. arXiv preprint arXiv:2411 14405, 2024.
[31] Zhenting Qi, Mingyuan MA, Jiahang Xu, Li Lyna Zhang, Fan Yang, and Mao Yang. Mutual reasoning makes smaller LLMs stronger problem-solver. In International Conference on Learning Representations, 2025.
[32] Xinyu Guan, Li Lyna Zhang, Yifei Liu, Ning Shang, Youran Sun, Yi Zhu, Fan Yang, and Mao Yang. rstar-math: Small 1lms can master math reasoning with self-evolved deep thinking. arXiv preprint arXiv:2501 .0451,, 2025.
[33] Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. Inference scaling laws: An empirical analysis of compute-optimal inference for LLM problem-solving. In International Conference Learning Representations, 2025.
[34] Dan Zhang, Sining Zhoubian, Ziniu Hu, Yisong Yue, Yuxiao Dong, and Jie Tang. R LLM self-training via process reward guided tree search. In Advances in Neural Information Processing Systems, 2024.
[35] Rylan Schaeffer, Joshua Kazdan, John Hughes, Jordan Juravsky, Sara Price, Aengus Lynch, Erik Jones, Robert Kirk, Azalia Mirhoseini, and Sanmi Koyejo. How do large language monkeys get their power (laws)?, 2025.
[36] Rémi Coulom. Computing "elo ratings" of move patterns in the game of go. ICGA journal, 30(4):198-25) 2008 2007.
12

---

[37] Adrien Couêtoux, Jean Jean-Bapal Baptiste Hoock, Nataliya Sokolovska, Olivier Teytaud, and Nicolas Bonnard. Continuous upper confidence trees. In Learning and Intelligent Optimization: Sth International Conference, LION 5, Rome, Italy, January 17-21, 2011. Selected Papers 5, pages 433 445. Springer, 2011.
[38] Samuel Sokota, Caleb Y Ho, Zaheen Ahmad, and J. Zico Kolter. Monte carlo tree search with iteratively refining state abstractions. In Advances in Neural Information Processing Systems, volume 34, pages 18698-18709, 2021.
[39] Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. In International Conference on Learning Representations, 2024.
[40] An Yang, Beichen Zhang, Binyuan Hui, Bofei Gao, Bowen Yu, Chengpeng Li, Dayiheng Liu, Jianhong Tu, Jingren Zhou, Junyang Lin, al. Owen2.5-math technical report: Toward mathematical expert model via self- ceff-improvement. arXiv preprint arXiv:2409. 222i::2409.1222,, 2024.
[41] Oriol Abril-Pla, Virgile Andreani, Colin Carroll, Larry Dong, Christopher Fonnesbeck, Maxim Kochurov, Ravin Kumar, Junpeng Lao, Christian C Luhmann, Osvaldo A Martin, et al. PyMC: A modern, and comprehensive probabilistic programming framework in python. PeerJ Computer Science, 9,165 2023.
[42] Ruocheng Wang, Eric Zelikman, Gabriel Poesia, Yewen Pu, Nick Haber, and Noah Goodman. Hypothesis search: Inductive reasoning with language models. In International Conference Learning Representations, 2024.
[43] Jianhao Chen, Zishuo Xun, Bocheng Zhou, Han Qi, Hangfan Zhang, Qiaosheng Zhang, Yang Chen, Wei Hu, Yuzhong Qu, Wanli Ouyang, and Shuyue Hu. Do we truly need so many samples? multi-llm repeated sampling efficiently scales test-time compute. arXiv preprint arXiv:2501.12948, 2025.
[44] Francois Chollet, Mike Knoop, Gregory Kamradt, Bryan Landers, and Henry Pinkard. Arc- agi-2: A new challenge for frontier ai reasoning systems. arXiv preprint arXiv:2505.11831, 2025.
[45] Gemini Team. Gemini 2.5:
Pushing the frontier with advanced reasoning, multimodal- ity, long context, and next generation agentic capabilities. Technical report, Google Deep- Mind, jun 2025. URL https:://ttosaaaaeee goog www.golollpppeo. eapis iss.... com deepm ind-media a/ gemini gemi ini v2
pdf Technical report, accessed 26 Jun 2025.
[46] OpenAL. OpenAl o4-mini System Card. bttts::/oppense www.wiowennnnnno/te.ot....cc.eee
c3-04 104-minn mini system-card/ apr 2025. Accessed 26 Jun 2025.
13

---

A Method Details
A.1
Extended Preliminaries
A.1.1 Problem Setup
First, we define the problem setting and introduce the mathematical notation.
We consider problems where the input is natural language prompt lin (which may include few-shot
examples, task instructions, etc.). Given lins an LLM produces natural language output lout, which
is then scored by score evaluator yield a final score We assume 0 S r S 1, where higher values of correspond to better answers.
This two-stage pipeline can be expressed as:
R(fout) R(LLLM((I)))
(2)
where the function fLLM represents LLM that generates the answer, and R is the score evaluator. fLLM stochastic and may produce different outputs fout for the same input lin- Here we allow out to include information beyond the direct answer (e.g., the reasoning steps), and we assume that R properly performs the parsing of this answer to perform the score evaluation.
Our framework applies to any task whose final answer can be quantitatively scored, such as program- ming tasks [4], math problems (29), and machine learning competitions [[6]. We assume the score evaluator R is already defined in a task-specific manner, and our goal is to find oout that attains as high an r as possible during the inference-time answer search.
In some tasks that mimic real competitions, the ground-truth score evaluator Rgr (reflecting the correctness of the answer) not accessible during the answer search stage. For example, in MLE- Bench [16]. the test dataset used for final evaluation is withheld, and in coding competition tasks 114. participants can often only submit their code limited number of times obtain the score on hidden test cases. In such situations, to search for the best answer, one may resort to different score evaluator. For instance, in HLE-BBncch, this could be the performance on public dataset, while in coding competitions, it might be the fraction of solved public test cases. For mathematical tasks, separately trained reward model 40 may be used. Throughout this work, we assume there some accessible score evaluator at the answer search stage that can assess the quality of fout-
A.1.2 Existing Methods for Inference-Tine Answer Search
We now review two standard approaches that focus on exploration or exploitation alone.
Only Go Wide: Repeated Sampling. A straightforward approach to inference-time answer search is to repeatedly sample answer from the LLM with nonzero temperature. We refer to each sampling step as the direct answer generation process. By performing it n times,
4772
(tin( m E {1....,,n]. oout
we obtain multiple candidate answers. Then, one can select the best answer based on a predefined criterion, such the highest score (best-of-n), majority voting, self-consistency. Brown et al. 3 recently showed that as increases, the coverage of generated answers improves. A similar approach was employed by AlphaCode [ to achieve human-level performance on competitive programming tasks.
Only Go Deep: Sequential Refinement. Alternatively, can leverage the answer refinement process and apply it sequentially to perform the answer search. We consider the situation where we already let some answer generator solve the problem at hand l times, and collected the onput-output pairs in and 1 where (). for those answer generations.
We define the answer refinement process as a two-step procedure: (1) creation of a new refinement input from the existing input-output pairs, and (2) generation new answer t from t Symbolically,
k+ = (LLM(t FLLM (brefine ( (ttm Lout ben)....)))
(4)
where Prefine a refinement input generator that provides all the information necessary for refinement, such feedback on each answer (e.g., code execution results errors for coding tasks).
14

---

Applying this refinement step iteratively yields answers:
t tim:
(5)
( out fLLM (Ma)::
(6)
m Prefino (Imm lout je
(7)
out = fLLM(!()
(8)
for m E n2. Finally, one selects the best candidate among {fott Sooutaefian ae based on a chosen criterion, similar to the repeated sampling approach.
We can regard the two methods above (pure exploration and pure exploitation) as special cases of a tree search: the former expands only from the root node, while the latter continues from the most recently reached leaf node on a single linear path, exploring it in depth without branching outward. The standard MCTS naturally incorporates the two, while it uses fixed branching factor, thereby limiting the performance gain from the repeated sampling when using L.M. Our AB-MCTS employs more flexible branching algorithm and effectively leverages performance improvements obtained by repeated sampling.
A.2 Comparison of AB-MCTS and Standard MCTS with Progressive Widening
The progressive widening has parameters (k, o)) which bounds the number of branching factors by kn with node visit count n. With these parameters, the rule for whether to branch is pre-determined as function of the node's visit count. Crucially, this decision does not use important information gathered during the search, namely, the observed rewards of the expanded nodes. The UCT score only used to select which child to descend to after the decision has been made not to branch. Furthermore, defining the branching rule as function of visit count means that the scaling behavior of the tree's shape and node degrees is pre-determined by the choice of hyperparameters.
In contrast, our approach does not restrict the branching rule based solely on visit counts and hyperparameterss Instead, the branching factor adapts dynamically based on the observed rewards. This an important requirement for LLM test-time inference scaling, where a tree search that purely goes wide is known to be strong baseline. To demonstrate the robustness of AB-MCTS, we conducted an experiment to compare AB-MCTS and progressive widening in Appendix C.4
A.3
AB-MCTS-M Details
A.3.1
Background on Mixed Models
Mixed linear models are extensions of traditional linear models that explicitly model non- independence among observations by incorporating both fixed and random effects. Fixed effects capture consistent, predictable patterns across the entire population or dataset (c.g.. treatment effects common to all groups). contrast, the random effects model variability arises within or between specific nested or hierarchical groups (e.g., individual differences among participants, or variations between schools).
A.3.2 Detailed Mixed Model Formulation and Example Code
In AB-MCTS-M, we fit separate mixed model at each node N of the MCTS tree, that is, at each sub- step within the MCTS selection step. Specifically, let N, (j = 1....., rechia) denote the direct child nodes of N, and define sub as the subtree under Nj. including N, itself. For a newly generated node Ñ where (i) j 0 (i.e. for GEN node) and N is direct child of N, or (ii) 1,..., Rehild and Ñ is node expanded from some node in Tash Tast(N, (N₂) at that iteration step, we assume:
rg aj + N CN 1),,
ag Ma + Jatjs G ~,,,1,,
(10)
Here, aj is "group-level"" intercept capturing the quality of the base solution at Nj, while o represents per-instance noise. The GEN node (action ag) treated as a newly introduced group without its own direct observations. However, its group-level intercept on is inferred not from the prior alone but rather from the posterior distribution over (oa and aa, which is informed by the other observed data.
15

---

import рyme as
Child indices use 0-based indexing; note the difference from index j Equations (9-10)
child_indices = [0, 0, 0, 1, 2, 2] rewards [0.8, 0.8, 1.0, 0, 0.2, 0.31 coords ("child_idx"; [0, 1, 21}
with pm. ModeM (coords=coords) as model:
#* Priors
mu_alpha pm. mn.Normal1 (atmmaaammmmaa100" ("mu_alpha", mu=0.5, sigma=0.
sigma_alpha = pm. Halrfraall (" "sigmamappha sigma=0.22
sigma_y = pm. Hal.Halfooma sigmay"" sigma-0.3)
## Pricrs END
eps_j pm, Normal ("eps_i", mu=0, sigma=1, dims="child alpha = mu alpha + eps_] signa_aipha
pm. Normalrllll.m ("r", mu-alpha [chi insicess, si gi observed- rewards)
Listing I: AB-MCTS-M fitting model example code
eps_]_gee pm. Normal ("eps_i_gen", mu-0, sigma-1)
alpha_gen mu_alpha eps_i_gen sigma_alpha
r_gen pm.Normal ("r_gen", mu-aappa__enn, s sigma-sigma_
Listing 2: AB-MCTS-M GEN node reward modeling
We place priors on (Ma,To. σy) and estimate them via MCMC (Markov Chain Monte Carlo), then perform Thompson Sampling. Because the GEN group (j 0) has no direct observations, its posterior remains more uncertain and thus encourages exploration. To illustrate how to estimate posterior predictives, in Listing we provide PyMC [4] code corresponding to the example tree shown in Figure 2 Here, we adopted the same priors as in our experimental setting, as noted in Appendix B.2
Ha ~ ((0.5,0.))) aa ~ (0.2) oy ~ (0.3
(11)
In this implementation, the variable alpha specifie (indexed by child idx), yet shares parameters mu_alpha, representing the overall average answer quality determined by the inherent difficulty the task, and sigma_ai al phap, representing the variability in answer quality arising from the LLM's response diversity. Differences in answer quality among nodes are captured by the variable eps_j.
To compute the probability distribution for the GEN node, we introduce slightly modified predictive model by adding an additional variable representing the GEN node reward, as shown Listing
Since eps _ignnn has no associated observed data, r_gen typically exhibits higher variance com- pared Intuitively, r_gen incorporates both the variance arising from the refinement process and the inherent variability in answer generation at node N. This increased variance encourages greater exploration during Thompson Sampling.
After model fitting, the posterior predictive distributions of r (existing child nodes) and r_gen (GEN node) utilized for Thompson Sampling.
16

---

A.4 AB-MCTS-A Details: Parameter Update Rules
A.4.1 AB-MCTS-A (Gaussian) Parameter Update Rules
As for the parameter update rules, for the Gaussian case, we use pormallinverse-x" prior:
p(r fra (rm)n)) = [r m, o R )x 10,
(12)
f Km NT
(13)
R + N
(14)
D 8 + N,
(15)
N K N
D pg 872 + Σ
(r' - 7)2 +
(m 7)
(16)
1 N
Tm
(17)
where in is the observed score.
A.4.2 AB-MCTS-A (Beta) Parameter Update Rules
Altematively, if E [0, 1], we can use Beta distribution with the following parameter update rules after observing (Tm)==
p(r (nm B(r / B),
(18)
â á
Tn:
(19)
N 3= 3 +
(1 - ra),
(20)
n=1
where B(- a. 5) denotes the Beta distribution. We note that, usually this update rule is used in conjunction with the Bernoulli trial, but here we directly use Beta distribution to model the score distribution. In practice, this parameter update rule worked well according to our experimental results.
A.5 Walk- through Examples
We walk through an itcration of AB-MCTS-M and AB-MCTS-A on the example trees in Figures 2 and 3 The process is stochastic due to Thompson sampling; for clarity, assume specific sampled outcomes.
A.5.1 AB-MCTS-M
AB-MCTS-M incrementally builds the search tree by adding one node at a time. In this section, we detail a single iteration the AB-MCTS-M algorithm, clearly illustrating the sequence of selecting a node to expand, performing the expansion, and backing up the resulting score. For simplicity and concreteness, we assume the current search tree structure is depicted in Figure and we describe one complete iteration, including selection, expansion, and score backup.
1. (N Ni) At N, we compute posterior distributions for its four children, GEN, Ni, N2. and N3 under the mixed model, and draw one score from each. If GEN receives the highest sample it is expanded and its score is backed up (Algorithm [ lines 11-13). Here, assume that N1 attains the highest sampled score, reflecting the exploitation of a child whose posterior peak is comparatively large.
2. (N1 + N2) N₁ has two direct children, N (r 0.8) and N (r = 1.0). We compute posteriors for GEN, Nj, and N₁, then sample again. Although the subtree T(Ng) currently contains nodes with higher score as can see from Figure 2, the finite variance of its posterior ensures that N/ not always selected, and encourages more exploration for under-explored tree regions. Suppose N is chosen on this iteration.
17

---

3. (Expanding ND Because N2 is leaf, we expand it (Algorithm | line 10). Assume the newly generated node receives the score 0.5. Since all the leaf nodes have a GEN child, a GEN node is appended to this expanded node as well.
4. (Score backup) The score is propagated upwards from the expanded node toward the root, as standard MCTS. In the current example. the score is backed up through the node generated at step 3, then through nodes N1. NN. and N. Unlike standard MCTS, AB-MCTS-M M maintains individual scores rather than averages. Specifically, the backed-up scores for nodes N1, N2, Ng form distinct observation lists corresponding to each group in the mixed model. Although GEN nodes have no direct observations due this score backup rule, their posterior distributions share statistical strength with these groups, allowing indirect information sharing and improved estimation accuracy for a score obtained by node expansion. At the next SelectExpans: anTar call, the four posteriors at N have different shapes; specifically, the peak of N1 's posterior shifts left due to the lowered expected value. Other posterior distributions are affected as well, c.g., the right-hand tail of the GEN posterior contracts. Please note that, in AB-MCTS- M, the change of posterior distribution shape cannot be analytically written down, and is calculated by MCMC. Thus, unlike standard MCTS, the score backup step involves appending the new score to list of scores.
A.5.2 AB-MCTS-A
AB-MCTS-A works in a similar manner to AB-MCTS-M, except for the introduction of CONT node and how we perform score backup. To clearly illustrate the algorithm and highlight the difference from AB-MCTS-M, we describe complete iteration of selection, expansion, and score backup cycle for AB- AB-MCTS-A. Since the only difference between Beta and Gaussian variants is how the score update is reflected in the posterior distribution, here we focus on the qualitative aspect of posterior update and focus on the details for an example tree, Figure 3.
1. (V CONT) At the root, we sample from the posteriors of the GEN and CONT children. As detailed in Section 3.4 the GEN posterior is informed by the CONT children nodes N1 (0.8), N₂ (0.0), N₂ (0.2), whereas the CONT posterior uses the CONT node's 'ss descen- dant scores excluding N1, N₂ and Ng. i.e., 0.8, 1.0, 0.3. We assume CONT is selected here.
2. (CONT N1) Next we compute posteriors for CONT's children N1, N2, and Ng. Due to the score- backup rule, the posterior distributions are computed from previously expanded nodes; Concretely, the following scores are used for posterior distribution calculation: Ni: (0.8, 0.8, 1.0), N2: (0.0), and Ng: (0.2, 0.3). Here, we assume N₁ obtains the highest sample via Thompson sampling.
3. (Expanding N2) Again, we perform Thompson sampling between the GEN and CONT children of N1. The GEN posterior uses (0.8, 1.0); the CONT posterior falls back to the prior because no generated descendants exist. Here we assume GEN is selected, leading to the expansion of a new node under N₃ s CONT child. We assume the score = 0.5.
4. (Score backup) We backup the score r = 0.5 as prescribed in Section 3.4 First, the score is backed up to the GEN node which generates the node. Second, propagates to: GEN node's ancestor Nj. and (ii) the CONT node that is Ni's parent. Because 0.5 is lower than the existing scores 0.8, 1.0, the posterior peak of N1 shifts left, reducing the probability that N1 will be chosen again from CONT. Similarly, adding 0.5 to the existing scores (0.8, 1.0, 0.3) lowers the peak of the CONT posterior N, thus decreasing the probability that CONT will be selected at N in later iterations.
A.6 Hyperparameter Sensitivity of AB-MCTS
This section presents a sensitivity analysis of the hyperparameters used in AB-MCTS. As discussed in Appendix B.2, the prior parameters were designed to be non-informative to minimize bias. Since the posterior distributions become increasingly data-driven as the search progresses, we hypothesized that the influence of the initial priors would be limited. Here, we empirically verify this hypothesis through an extensive analysis. We evaluated the sensitivity of AB-MCTS variants to their prior hyperparameters LiveCodeBench, using GPT-4o with generation budget of 2
18

---

Table 3: Hyperparameter Sensitivity of AB-MCTS. Pass@ values are averaged over five runs.
results for each prior setting. All
AB-MCTS-M
m
0.0
0.4
0.5
0.6
1.0
Pass@
38.4 + 1.6
37.3 0.4
36.8 +
1.5
37.5 +
1,5
37.7 + 1.3
0.01
0.1
0.2
0.3
1.0
Pass@1
38.4 1.3
37.7 1 0.9
36.8 T 1.5
38.2 1. 2.3
38.6 1. 1.8
0.01
0.1
0.2
0.3
1.0
Pass@1
37.3 2.0
38.2 1.1 37.1 t 1.2 36.8 + 1.5
39.5 +: 1.3
AB-MCTS-A (Gaussian)
0.0
0.1
0.5
1.0
Pass
38.0 1.6
37.0 + 1.4
37.3 1.5
37.7 + 0.7
6
0.001
0.5
1.0
10.0
Pass
38.4 + 1.3
37.3 + 1.5
38.0 + 1.6
37.7 + 0.7
8
0.001
0.5
1.0
10.0
Pass
38.2 1.3
37.7 1.3
38.0 1.6
38.9 + 1.0
0,05
0.1
0.2
0.5
1.0
Pass
0.9
38.0 1.6 37.7 1.3.
37.9 0.8
37.7 + 0.7
AB-MCTS-A (Beta)
0.1
0.4
0.5
0.6
1.0
Pass@1
37.3 + 1.5
37.0 + 1.5
37.5 + 1.3
37.5 + 1.3
37.7 # 1.2
3
0.4
0.5
0.6
1.0
Pass@1
38.4 1 1.8 38.4 1 1.1 37.5 1
1.3 37.9 1 0.5 37.9 1 1.4
Each configuration was run five times (n = 5) to compute mean and standard deviation of Pass 1. Tables summarize the results for AB-MCTS-M, AB-MCTS-A (Gaussian), and AB-MCTS-A (Beta) under various prior settings, Across all tested ranges, the performance remains stable, indicating low sensitivity the initial hyperparameter values. This confirms that AB-MCTS is robust to the initialization of prior hyperparameters, and its performance is primarily governed by the data-driven posterior updates during search.
B
Additional Experimental Details
B.1 Tasks and Datasets
We evaluated our approach on four benchmarks: CodeContest (1. LiveCodeBench 11. the Abstrac- tion and Reasoning Corpus (ARC) [17]. and MLE-Bench [16]. All of these benchmarks feature tasks that are often solved via code generation. Each experiment was multiple times using non-zero temperature to account for stochasticity (n = for LiveCodeBench, n 3 for CodeContest and ARC-AGI). For MLE-Bench, experiments were with = 1 due to the significant computational cost.
CodeContest and LiveCodeBench are well-established competitive programming benchmarks, both providing public tests and hidden tests. We use the public tests to calculate each node's score and the hidden tests for final evaluation. A solution is counted as correct only if it passes all hidden test cases for given problem, and the success rate defined as the fraction of problems for which the chosen solution is fully correct. The prompt templates we used are based on those from previous work [14]
19

---

In LiveCodeBench, we only use problems released between August and November 2024, aligning with the previous work [19 to prevent data contamination.
ARC-AGI requires discovering a shared transformation rule from multiple input-output examples, then using it predict the output for a test input. Generating code from sample grids is frequently used approach for ARC 7 13 42]. We instruct the LLM to infer a transformation rule from the provided input/output examples and generate corresponding Python code. Each node's score is determined by the fraction of examples it correctly transforms. The node that achieves the highest score is then used to transform the test examples; if the output exactly matches the ground truth, that node's 's score is set to 1. We evaluate our method on the same set of 100 public evaluation problems and prompts used in prior work [13].
MLE.-Bench BencBench comprises practical machine learning tasks derived from Kaggle competitions. In order to enable fair comparisons [16), we adopt three low-complexity challenges (Nomad2018 Predicting Transparent Conductors, Spooky Author Identification, and Random Acts of Pizza). Each competition's training data is randomly split into 80% for training and 20% for validation. The validation set is used to obtain the scores for each node. We select a node with the highest validation score given inference budget and then evaluate it on the hidden test set to get the final result. Following previous research [16], we use the AIDE scaffold for our experiments. Evaluating the generated machine learning models within these competitions is notably resource-intensive requiring substantial GPU power even to process single solution candidate. In our experiments, each solution candidate was executed on a single H100 GPU with time limit of one hour. This computational demand is still considerably higher than for other benchmarks discussed in this work. Consequently, due to these significant costs, comprehensive experimentation across all methods and models on MLE-Bence was prohibitive. We therefore focused our evaluations using GPT-4o for these tasks specifically on AB-MCTS-M.
B.2 AB-MCTS Parameters
Due to its Bayesian nature, the hyperparameters of AB-MCTS consist only of prior parameters. We used the same prior parameters for all the tasks without task task-specific domain knowledge (except for the range of the score being approximately [0, 1)), thereby minimizing any potential bias. Consequently, our priors have the following shared properties:
The vast majority of the probability mass (or all of it, in the case AB-MCTS-A (Beta)) is within [0, I].
The average value of score is 0.5, reflecting a neutral initial assumption regarding answer quality (where O indicates the worst and 1 the best)
The probability mass does not concentrate excessively in any particular region, reflecting our unbiased prior.
We assign the following priors for AB-MCTS-M in Equations and 10
Ha ~ (V.0., 0.23), aa ~ (0.2))
0g ~ (0.3))
(21)
where Niair is the half-normal distribution (please refer to Section 3.3
and Appendix A.3) For
AB-MCTS-A (Gaussian), we set m = 0, A = 1, v = 1, and 72 = 0.1 in Equations 12 17 and for
AB-MCTS-A A (Beta), we set & = 0.5 and / 0.5 in Equations 18
20
As we noted earlier, we
chose these parameters in a way that imposes as few assumptions as possible to minimize bias.
We expect the dependency on specific initial prior parameter values to be minimal, largely due to the substantial computational budgets in our evaluations and because posterior distributions become increasingly data-dominated as the search tree expands with more score observations (up to 2 nodes in most of the experiments and 29 in the extended ARC-AGI experiments). Because our node selection methods (AB-MCTS M, with its mixed model, and AB-MCTS-A using conjugate priors) are fundamentally Bayesian, the priors primarily influence the early stages of the search. Moreover, the "borrowing strength" mechanism inherent in the mixed model stabilizes posterior estimates and facilitates convergence. As the search progresses and score observations accumulate, the initial prior influence naturally diminishes.
20

---

LiveCodeBench (higher is better)
CodeContest (higher is better)
ARC-AGI (higher is better)
0.30
Success Rate (Pass(11)
Success Rate (Pass@11)
Success Rate (Pass:821
9.40
9335
0.40
Fral Success Rate
0.0
Final Success Rate
Success
0.00
020
0.30
022
3.43
134
034
2f
0.00
Generation Budget
Generation Budget
Generation Budget
Repeated Sampling
Sequential Refinement
MCTS
AB-MCTS-M
AB-MCTS-A (Gauusssnn (Gaussian)
AB-MCTS-A
Figure 8: Performance comparison with DeepSeek- V3 on LiveCodeBench, CodeContest, and ARC-AGI. We compare AB-MCTS methods with the baselines by plotting the success rate against the generation budget.
LiveCodeBench
CodeContest (higher is better)
ARC-AGI (higher is better)
(higher is better)
0.18
Success (Pass@3))
Success Rate (Pass@@1))
Success Rate (Poss
3:40
0.15
0.41
0.35
6.12
8.40
0.08
3.30
0.00
Depth Mean Width, (log2)
Mean Depth Mean Width, (log2)
Mean Depth Mean Width, (log2)
Repeated Sampling AB-MCTS-M
Sequential Refinement AB-MCTS-A (Gaussian)
Standard MCTS
AB-MCTS-A (Beta)
Figure 9: Comparing algorithms by search tree shape and performance Each point shows the performance against the average tree shape for a given algorithm at a specific generation budget. The x-axis represents the log-ratio of mean tree depth to mean tree width. Mean width is calculated as the average number of nodes per depth. Larger x-axis values indicate deeper searches, while smaller values indicate wider searches.
No1ad2018 (lower is better)
Spooky Author Identification (lower is better)
Random Acts of Pizza (higher is better)
Repested Sampping
0.75
Sccuercaal
Standard
0.70
RMSLE
Loss
3.50
ROC AUC
0.65
0.065
2:45
0.60
Sampling
0.060
3.40
Generation Budget
Generation Budget
Generation Budget
Figure 10: Performance comparison three MLEE-ench tasks using GPT-4o. Each plot shows performance versus the total generation budget. For Nomad2018 Predicting Transparent Conductors and Spooky Author Identification, lower scores better (RMSLE and Log Loss, respectively): for Random Acts of Pizza, higher is better (ROC AUC). At each budget, we choose the single solution based validation-set performance and report its test-set score.
21

---

Nomad2018: AB-MCTS-M
CCC
0.037
CCCCO Ocoicco CC Ccoreco
CECOTCCOR 205 OIOCE
0.035
0.036
0.032
Nomad2018: Standard MCTS
0.089
0.038
4.005
4.002
Spooky Author Identification: AB-MCTS-M
0.65
0.60
4.55
4.50
CONOXCCO
4.45
0.40
Spooky Author Identification: Standard MCTS
CEECCO
Random Acts of Pizza: AB-MCTS-M
KOOOGCOCK COO
4.70
Random Acts Pizza: Standard MCTS
0.78
0.75
0.74
0.72
0.70
.0.8
Figure 11: Example search trees generated by AB-MCTS-M and standard MCTS on MLE- Bench. The example tree for Random Acts of Pizza generated by AB-MCTS-M is the same tree shown in Figure 7
22

---

C Additional Experiments and Analysis
C.1 Results with DeepSeek- V3 on Competitive Programming and ARC-AGI
This appendix provides supplementary results using the DeepSeek-V3 V3 model, focusing on both overall performance and search behavior characteristics.
Figure 8 shows the performance (Pass@) 1) with DeepSeek-Ve V3 on the Competitive Programming (LiveCodeBench, CodeContest) and ARC-AGI benchmarks. While the overall performance trends were similar to those with GPT-4o (Figure 4). the relative strengths of the baseline methods varied with DeepSeek- V3. For instance, standard MCTS achieved the highest success rate on LiveCodeBench. On CodeContest, the performance differences between AB-MCTS and the vop-performing baselines were less pronounced than with GPT-4o. Despite these variations, AB-MCTS variants consistently placed among the leading methods across all tasks. This indicates that A AB-MCTS reliably delivers strong performance even when changes in the underlying model alter the effectiveness of different baseline strategies.
The analysis of search tree shape versus performance with DeepSeek-V3 (Figure ( closely mirrors the findings from GPT-4o 3.. As expected. repeated sampling forms wide search trees, while sequential refinement develops deep trees. AB-MCTS methods consistently generated wider trees compared to standard MCTS. This tendency towards wider exploration is notable even on tasks like BiveCodeBench with DeepSeek- V3, where sequential refinement outperformed repeated sampling. The strong performance of AB-MCTS algorithms in such scenarios suggests their ability to not only explore broadly but also to effectively identify and deepen promising branches through their adaptive node selection. This highlights the robust nature of AB-MCTS in balancing these competing demands across different models.
C.2 Results with GPT-40 on three competitions from MLE-Bench
Figure 10 compares AB- MBMMSTS-M against the baseline methods on the three MLB-Bench petitions using GPT-4o, plotting performance scores against the generation budget. Notably, the most effective baseline varies across these competitions. For instance, Nomad2018, sequential refinement ultimately achieves the best score while repeated sampling shows no improvement. On Spooky Author Identification, standard MCTS exhibits continued improvement throughout the budget range. Conversely, on Random Acts of Pizza, repeated sampling significantly outperforms other baselines. Despite this variability in baseline effectiveness, AB-MCTS-M consistently delivers strong performance across all three competitions. This highlights the robustness and adaptability of AB-MCTS-M, suggesting its capability to effectively adjust its search approach to the differing characteristics of each task, especially when the optimal strategy is not apparent beforehand.
C.3 Example search trees generated by each methods on ML.E-Bench
Figure T presents example search trees generated by AB-MCTS-N - and standard MCTS for the three MLE-Bench competitions. Across all tasks, the trees generated by AB-MCTS-M M visually suggest more flexible approach compared to standard MCTS, effectively combining broader exploration with focused exploitation of promising nodes.
Table 4: Comparison between Progressive Widening and AB-MCTS on LeveCodeBench.
a)) 0.45) (&, (5, 0.5) (k) (10, 0.55) AB-MCTS-A (Gaussian) AB-MCTS-A (Beta) AB-MCTS-M
Pa
20.
50.7
51.8
C.4
Comparison Progressive Widening on LiveCodeBench
To compare the progressive widening with AB-MCTS, we conducted an experiment on Live- CodeBench for progressive widening with various parameters. We used deepseek v3-eee-v---00 0324 with generation budget 27 (n 5). The results are shown in Table 4 While an adequate progressive widening parameter leads to strong performance comparable to AB-MCTS, its effectiveness highly sensitive to hyperparameters. For example, it produces the worst result with (k, a) 01.4..).
23

---

Table 5: Comparison @ and Pass@2 on ARC-AGI with GPT-4o.
Method
Pass 1
Pass@2 2
Repeated Sampling
14.0 1.7
15.0 1.0
Sequential Refinement
7.7 = 0.6
8.7 + 0.9
Standard MCTS
8.0 1.0
9.0 1.5
AB-MCTS-M
11.0 1.0
12.3 + 1.2
AB-MCTS-A (Gaussian)
3.6
13.0
AB-MCTS-A (Beta)
12.7 4 0.6
14.0 + 2.1
Furthermore, the (k, a) (10, 0.55) setting shows search instability, leading to the highest variance. In contrast, AB-MCTS is robust without such tuning, demonstrating its practical advantage.
C.5 AB-MCTS-M vs. AB-MCTS-A: Analysis and Selection
This paper introduces two adaptive branching algorithms: AB-MCTS-M and AB-MCTS-A, This section offers considerations for selecting between them, drawing upon experimental findings and their distinct underlying mechanisms.
When outcome quality is the main priority, AB-MCTS-M is often the preferred choice because of its consistently strong performance T D}.
For node selection, this algorithm uses MCMC, an iterative procedure that improves effectiveness but incurs some computational cost per selection. For applications with strict time constraints, AB-MCTS-A offers lighter alternative, as its Gaussian and Beta variants employ analytically tractable posterior updates. However, when the LLM-inference time or the time required to evaluate the generated candidate solutions dominate, the extra time spent on MCMC has little impact on total runtime.
While both algorithms feature adaptive search, Figures and show that AB-MCTS-A tends to construct wider search trees. This tendency is attributed to its core design: at each depth, AB- MCTS-A chooses between selecting GEN node or a CONT node. Reaching depth requires d consecutive CONT choices, so deeper paths become geometrically less likely than wider expansions (see also Section A.4). Therefore, for tasks such as ARC-AGI where broader exploration is considered particularly beneficial, AB-MCTS-A can be preferable.
Ultimately, the choice depends on the application's 's primary goal: AB-MCTS-M often performs well when outcome quality is prioritized, whereas AB-MCTS-A offers advantages in computational efficiency and for tasks that benefit from broader exploration. However, both provide capable adaptive search strategies.
C.6 Pass vs. Pass@2 on ARC-AGI
In Table [ we reported Pass scores for ARC-AGI to follow the standard evaluation protocol defined by the benchmark [17]. For completeness and transparency, we also report the corresponding Pass@1 results in Table As shown in Table the results indicate consistent relative performance between Pass@1 and Pass particular, the ranking of methods remains unchanged, confirming that the conclusions presented in the main text are robust to the evaluation metric.
C.7 Analysis of Adaptive Search Behavior via Node Degree Distribution
To gain a granular view of the adaptive nature of our methods, we analyze the node degree distribution of the search trees generated on Binchh with DeepSeek- V3,, illustrated in Figure [2] The results show two distinct behaviors. AB-MCTS-M clearly favors depth-focused search, with around 90% of its non-leaf nodes having small degree (1-3). However, its long-tail distribution. with degrees up to 40, confirms that it adaptively broadens the search when required. In contrast, AB-MCTS-A performs much wider search. Low-degree nodes (1-3) account for only about 30% of its non-leaf nodes, and the distribution spreads broadly, with degrees exceeding 100. This adaptive shaping of the search tree, which differs starkly from the more rigid patterns of baselines, provides strong evidence for the flexibility of our framework.
24

---

Node Degree Distribution
10a
Repeated Sampling
Sequential Refinement:
Standard MCTS
AB MCTS-N M
10
AB-MCTS-A (Gaussian)
AB MCTS A (Beta)
Frequency (%)
10a
10
10-2
10-3
Node Degree
Figure 12: Node-degree distribution reveals the adaptive search nature of our methods. The plot displays the frequency of nodes (y-axis, log scale) for each degree (x-axis) under search budget of N 128.
Table 6: Performance of Standard MCTS with Different Fixed Branching Factors (w) LiveCodeBench. Pass@1 scores are reported. The best result is shown in bold.
Metric
3
5
w
10
Pass@1 0.429 + 0.018 0.432 + 0.021 0.402 + 0.015
C.8
Ablation on the Fixed Branching Factor in Standard MCTS
We tested standard MCTS with fixed branching factors (w) of 3, 5, and 10 on LiveCodeBench using DeepSeek-V3. The results are summarized in Table We find that w achieves the best performance among the tested values. Crucially, performance degrades with both smaller and larger widths, highlighting the sensitivity of the baseline to this hyperparameter. This finding underscores key advantage of our adaptive method, which dynamically adjusts the effective branching factor during the search.
C.9 Robustness of AB-MCTS Performance
In other baseline methods, the branching factor is either predetermined or determined by hyperpa- rameters. For example, we need to predefine the branching factor in standard MCTS. However, the efficiency of the width vs depth strongly depends the type of tasks and LLMs. This is reflected in Table [ and Table where AB-MCTS shows robust performance across various task types, while other methods excel for some tasks, but not for others. This is due to the adaptive branching nature of AB-MCTS, where the algorithm adapts to the wide or deep direction depending on the observed rewards. This is beneficial in the context of LLM inference-time scaling, since recently LLM has been used for solving various kinds of tasks, e.g., math tasks, coding tasks, etc., and a search algorithm that works for various task types out of the box is in high demand.
C.10 Towards Pushing the Pareto Frontier of LLM Inference-Time Scaling
In this section, we propose the following two potential directions for future work aimed at pushing the Pareto frontier of LLM inference-time scaling:
1. Enhanced Adaptivity via Difficulty Estimation: We propose to enhance our algorithm's existing width balancing by explicitly estimating problem difficulty from collected rewards. For difficult problems (identified by low rewards), the strategy would dynamically
25

---

switch, e.g., from deep search (AB-MCTS-M) to wide one (AB-MCTS-A) This is motivated by findings that optimal search strategies depend on difficulty (27]
2. Collaborative Search with Multiple LLMs: We also propose a method that leverages the diverse strengths of different LLMs within single search. This is implemented by extending AB-MCTS with multiple GEN nodes, one for each LLM.
We elaborate on the specific methodology and preliminary experimental results for the second direction (Collaborative Search) in Section
D Multi-LLM AB-MCTS
Depending on the task, using more than one LLM for answer search 43 can be advantageous. For example, LLM A can generate more diverse initial answers and LLM B excels refinement, building the answer tree with both models is expected to improve performance. This section demonstrates how AB-MCTS can be extended scenarios in which multiple LLMS are available for answer generation, and also reports the experimental results for ARC-AGI-2, demonstrating the effectiveness of the proposed method.
D.1 Method
D.1.1 Multiple LLMs as Answer Generators
Suppose L LLMs are available for answer generation. We denote by fLLM the answer generator implemented by the 1-th LLM, with = 1, ..... I., following the notation introduced in Equation 2 The overall procedure identical the single-LL.M AB-MCTS (Algorithm{) I with the addition of step to select one of the L. available generators for node expansion. This selection occurs at each expansion phase, utilizing the current state of the answer tree The chosen generator, fiLM is then used to expand the selected node. We introduce two distinct algorithms for this generator selection process.
D.1.2 Generator Selection Algorithm I: Single GEN Node
In this algorithm, node selection proceeds identically to AB-MCTS, followed by additional generator selection step. During this step, each node in the entire answer tree annotated with obtain the set of nodes Ag C T,
the index of the generator that produced it. For every generator, containing all nodes it has generated; Ni is empty if the generator has not been selected yet. The scores of the nodes in MG are used to calculate the posterior distribution of the expected score of a new node that will be generated by the generator After all L posteriors have been computed, Thompson sampling is applied: single sample is drawn from each distribution, and the generator with the highest sample is selected for the node expansion. These posteriors are modeled in the same way the distributions used for node expansion target selection, as detailed below.
Multi-LLM AB-MCTS-M with Generator Selection Algorithm this algorithm, Multi-LLM AB-MCTS-M treats the generators groups within the mixed-effects model defined as
TN ai + OBEN, as pa + toEl, ~ a~ 10,,
(22)
(23)
where the group index has been replaced by the generator index from Equations 9-10 As for the prior distributions, we can the ones in Equation| IT After calculating the score posterior distributions using Ni for all I, we perform Thompson sampling to select one generator.
Multi-LLM AB-MCTS-A with Generator Selection Algorithm I. In this algorithm, Multi-LLM AB-MCTS-A assigns each 1-th generator an independent prior-Gaussian (Equations 17) or Beta (Equations 18 20) depending on the score metric, and updates these priors to posteriors using the scores of the nodes in N₁. After calculating the posteriors for all we perform Thompson sampling to choose generator.
26

---

D.1.3 Generator Selection Algorithm II: Multiple GEN Nodes
An alternative approach attaches multiple GEN nodes children to every node in the tree-one for each of the L available generators. At each node N in the expansion target selection process, the following process occurs:
1. The AB-MCTS selection logic applied independently within the sub-trees associated with each generator. This means that for each generator I, we run a selection process considering associated GEN node and any child nodes previously generated by from node N.
2. Thompson sampling is used to identify the best node (either the GEN node or an existing child node) for each generator I.
3. Finally, the scores of the L best nodes selected in the previous step are compared, and the one with the highest overall score is selected.
This algorithm is designed to better capture the local context of the search tree, allowing for the adaptive selection of the most suitable generator each specific stage of the solution process.
D.2 Experiments
In this section, we evaluate the effectiivnesss of Multi-LLM AB-MCTS by reporting the results and analysis of ARC-AGI-2 [44]. ARC-AGI-2 is enhanced benchmark building upon the original ARC-AGI, specifically designed assess higher-level cognitive abilities of artificial intelligence systems rigorously. It maintains the same fundamental principles ARC-AGI, emphasizing tasks that require general fluid intelligence rather than extensive prior knowledge or memorization. this benchmark, which is hard to solve even for frontier LLMs (less than 5% success rate [44)), to assess whether we can combine multiple frontier reasoning LLMs to obtain better performance for challenging tasks.
selected
D.2.1 Experimental Setup
In this experiment, evaluated our approach the 120 problems comprising the public eval- uation set of ARC-AGI-2. For each problem, the generation budget was set to 250. The solu- tion generation and refinement procedures are the same those of ARC-AGI-1 experiment: The models were instructed to generate the transformation rule as Python code, and the search was guided by reward signal corresponding the number of demonstration cases correctly solved by the generated code. For solution generation, we used three frontier reasoning models: Gemini- 2.5 Pro (gemini nimminii---e. previiorpeiiwwweeeeeeeeerrre-eee and DeepSeck-RI R1-0528 (deepseek-r--00e models.
45
04-mini (o4 1:4-mini: inn 22025-0200000 04-16) 46
22
The temperature is set to be 0.6 for all the
To primarily evaluate the potential of Multi-LLM AB-MCTS, we used the Pass metric. This metric measures whether at least correct solution is found within k attempts. This differs from the official ARC-AGI-2 contest standard, which typically uses a Pass criterion (i.e., one two submitted final answers must be correct). Evaluating Pass@2 requires additional selection mechanism to identify promising candidates from the search history. Therefore, this experiment focuses on the search capability itself via @ass@k. Due the significant API costs of the used frontier reasoning models, we focused on the evaluation of Single-LLM AB-MCTS-A and Multi-LLM AB-MCTS-A (and repeated sampling for o4-mini), since it worked most efficiently in our experiment ARC- AGI-I. Also, we employed the generator selection algorithm II (see Section D.1.3 for details) for our experiments.
D.2.2 Results
The performance of our proposed methods was compared against repeated sampling, which was the most efficient method for the ARC-AGI-1 experiment, and the result is shown in Fig. [3] As shown, Repeated Sampling using the o4-mini model achieved a 23% Pass@k success rate on public evaluation set, and the single-model AB-MCTS using 04-mini improved the success rate to 27.5%. The performance advantage of AB-MCTS over Repeated Sampling becomes more evident as the generation budget increases, particularly after approximately 50 budget.
27

---

Multi-LLM AB-MCTS
Performance of AB-MCTS
04-mini Gemin1-2.5-Pro + R1-0528
0.30
o4-mini Gemini-2.5-Pro
Success Rate (Pass@k)
0.25
o4-mini
04-mini (Repeated Sampling)
0.20
0.15
Gemini-2.5-Pro
0.10
DeepSeek-R1-052
0.05
0.00
50
100
150
200
250
Number of LLM Calls (k)
Figure 13: Pass @k (coverage) of ARC-AGI-2 for each generation budget. The methods tested repeated sampling, AB-MCTS, and Multi-LLM AB-MCTS methods.
250
S0b0hibie & de Wild
22 &
Model Counts
200
150
100
10
70
100
110
120
Ranking of Reward Values (1st is the highest reward.)
o4-mini
Gamini25-Pro
R1-3528
Solved
Figure 14: Distribution of LLM usage in the 120 ARC-AGI-2 problems with Multi-LLM AB-MCTS- A. Trials are sorted by the maximum reward obtained from demonstration cases (higher reward the left). Starred trials indicate correct final solution was found.
By employing Multi-LLM AB-MCTS, which integrates Gemini-2.5 Pro-Pro and DeepSeek-R1 R1-0528, we further improved the performance, ultimately finding correct solutions for over 30% of the problems. Notably, although DeepSeek- R1 -0528 exhibited lower individual performance, its integration into Multi-LLM framework led to an increase in number of solved problems.
D.2.3 Analysis
The Multi-LLM AB-MCTS framework demonstrated an ability to effectively allocate different L.MMs to problems based on their characteristics. As illustrated in Figure [4] the distribution of LLM usage varied across problems. For trials that quickly achieved high reward from the demonstration cases (left side the figure), the more proficient model tended to assigned. Conversely, for trials where obtaining high reward was more challenging (right side), the models were utilized in more balanced manner.
Furthermore, we observed instances where problems unsolvable by any single LLM were solved through the collaboration of multiple models. This suggests synergistic interaction that transcends simply matching the best model to problem. Figure 15 and Figure 16 depict search process where an incorrect solution generated by o4-mini served as a useful hint for DeepSeek-RI R----- and Gemini-2.5-Pin which then collaboratively produced the correct solution. This result indicates
28

---

Example Search Tree by Mult-LLM MBMT-LLMAB-MMTT AB-MCTS
Figure 15: example search tree from successful trial on ARC-AGI-2 using Multi-LLM AB- MCTS-A. The number in each node indicates the generation step, and the color represents the selected LLM. The yellow node generated the code that correctly solved the test case. This problem was not solved by any single model in isolation.
Problem: 36808778
Training
Analysis of the grevious soldion by DaepSeak- 1-0528
Pe decrparcie telveen ropernant expacted
(Mts liseiiid main nose:
pep baloe with volue (rbkke the spriec othor colotng the curnnt call "Tas
Mosinn
Spread:
?
2. Global Visted Satk Causting Salpped Procsseing The lid ser wet stored sorvee dan pled nanural water flow
gar daring spreed bakewin Buring drsp 2. Rerwving the sor ont entray dinon roan cranges mnsun prose repar- Mamasnyy
doop friargids
Solution generated by o4-mini
New solution refined by DeepSeck-R1-085
Test sel
Test
|
Comeer
Wrong @
Correct
by analysed and sucoesstully corrected.
Mudh the code shard
Figure 16: An illustration of model collaboration. In this example, DeepSeek-R1 R1-0528 refines an incorrect intermediate solution generated by o4-mini (from the problem shown in Figure [5] to produce the final correct solution.
29

---

that Multi-LLM AB-MCTS can facilitate flexible and effective collaboration among heterogeneous frontier LLMs.
D.3 Challenges and Future Work
While our primary evaluation focused on search capability using the Pass@k k metric, we conducted preliminary evaluation based the Pass criterion for reference. Using simple rule-based method to select two final answers (prioritizing code with high reward generated later in the search), the Multi-LLM AB-MCTS achieved Pass@2 of 19.2%. Although this is promising result, significant gap of over 10 percentage points remains compared to the 30% Pass@250 rate. Future work should focus on closing this gap by developing more sophisticated final-answer selection algorithms. Potential directions include building more accurate reward models or integrating an -LMa-a-a-Judge for a more nuanced evaluation of candidate solutions.
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction accurately reflect the paper's contributions and its empirical validation, as detailed throughout the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Limitations the proposed method are discussed in Section S
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
31

---

Justification: We focus on an empirical investigation of novel framework rather than formal theoretical results or proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The paper provides a detailed description of the algorithm in Sections 3 and A The experimental setup, including benchmarks, models, and hyperparameters, is detailed in Section 4.1 and Appendix Section
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
32

---

reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provide the code in the supplementary material for reproduction.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
htwpiiicggides///ooeee oom.eeesuuuumissssoooooooooyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
httpssccccccccccccctccc.cccccc /u ides CCoe/ooduubnn ss i onPolicy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The details can be found in Section 4.1 and Appendix Section
B
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Figure Appendix Figure reeport mean success rates with 95% confidence intervals based on multiple runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
33

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We wrote the details in Section 4.1 and Appendix B.I
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We have reviewed the NeurIPS Code of Ethics and adhere to
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work aims to improve the reasoning and problem-solving capabilities of LLMs in code generation. This may potentially have both positive and negative societal impacts common to the advancements in LLM technology.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
34

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility MI).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
The original publications for all benchmarks and LLMs are cited Section 4. and Appendix B Our use of these resources follows standard academic practices and complies with each provider's terms.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
35

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, ppapersw haperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The paper introduces algorithm. The code for this algorithm will be released upon publication.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
36

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [Yes]
Justification: The core methodology leverages LLMs, and the proposed method is specifi- cally designed to enhance their inference-time performance.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy bttrp::/meerrpss.cc//ooeeee LLM) for what should or should not be described.
37


Reviews:
[{"review_id": "UzJD3YMpYd", "reviewer": "Reviewer_RYt1", "summary": "This paper extends MCTS-based LLM test-time computation to include progressive widening, while novelly leveraging statistical information stemming from all actions being drawn from the same LLM distribution, resulting in a potentially more efficient search. Consequently, two different approaches to utilizing this information are introduced: Adaptive-Branching MCTS Mixed-model and Adaptive-Branching MCTS Node-Aggregation. Experiments across LiveCodeBench, CodeContest, ARC-AGI, and MLE-Bench suggest that this approach is more robust in different settings at improving performance through test-time compute, compared to Best-of-N, Self-refine, and MCTS baselines.", "questions": "* The MCTS baselines with a branching factor of 5 end up generating 2^7-2 branches, or do you cut the last generation to 2 instead of 5? I would clarify this for completeness. \n* In 4.3, is the overall width of the tree really representative of your method? Perhaps you could explore plotting the distribution of node degrees, which I believe would better show the strength of your approach.  \n* What do you think are the following steps to explore to try to reach the Pareto frontier? I believe it would be helpful to include a more comprehensive discussion of different designs, such as including problem difficulty and other metrics used in other works that control the relative benefit of width vs depth.\n\n### Other suggestions\n\n* I agree with the distinction regarding Progressive Widening in the related work. Still, given its relevance as prior work, I would encourage you to make this point more precise, potentially in the appendix.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n* **Problem significance**. Test-time compute has shown great potential and is an area of great relevance and timeliness \\[1\\].  \n* **Originality/impact**. Adaptive branching could hypothetically reach the Pareto frontier for the different test-time compute methods, which seem to perform with different success for different prompts \\[1\\]. Consequently, the ideas proposed in this paper can be valuable to the community, and the different design choices can be progressively improved in future work to approach the Pareto frontier for varying test-time budgets.\n\n## Weaknesses\n\n* **Clarity.** The paper is overall well-written, but the method section lacks precision due to relying solely on text-based exposition instead of presenting the method mathematically. Since this is the core contribution of the paper, I believe a clear explanation of the method (e.g., incorporating elements from Section A.2.2, but ideally with greater clarity) would significantly enhance the paper’s quality.  \n  * A minor suggestion would also be to include in the appendix a walk-through example of each approach, clearly illustrating, for example, the effect of the shared parameters on the overall update for AB-MCTS-M.  \n* **Quality/Evaluation**. I have some doubts about the overall soundness of the empirical evidence provided by the authors.  \n  * **Baselines**. As far as I understand, the baselines used for MCTS (e.g., LATS \\[2\\] and RAP \\[3\\]) consider nodes as steps toward the final answer, rather than as full solutions, which differs from the formalism presented in this work. Therefore, although MCTS on solutions is a valid baseline for this paper, it misrepresents previous works. Vanilla progressive widening could also be included as a valuable ablation.  \n  * **Metrics**. LiveCodeBench and CodeContest are evaluated at Pass@1, while ARC-AGI is evaluated at Pass@2. I would encourage transparency and completeness to provide at least Pass@1 for ARC-AGI, too, and ideally also Pass@2 in the other tasks. Additionally, it is unclear what the metrics displayed in Tables 1 and 2 represent, especially given the inconsistency in Figures 4 and 5\\.  \n  * **Statistical significance**. Gains in Tables 1 and 2 appear modest, especially when compared to Repeated Sampling, and it is unclear whether they are statistically significant, as no error bars are provided. In fact, confidence intervals in Figure 4 and Figure 8 in the appendix seem to suggest that gains are non-statistically significant, and the results do not evidently extend qualitatively to other LLMs. \n\nRegarding my score, the main pain points are the “clarity” point mentioned above and the lack of transparency in the representation of other works from baselines, the metrics provided, and the statistical significance as outlined above. I am not looking for further experiments, and I don’t think modest and mixed performance improvements alone would be a reason to reject, especially given the potential long-term impact this paper could have with follow-up works that find better approaches to the Pareto frontier. Therefore, I invite the authors to address these comments and provide a clearer picture; in that case, I am willing to increase the score to ‘weak accept’. More conclusive results with more relevant improvements would be required for me to raise my score to a full ‘accept’.  \n—  \n\\[1\\] Snell, C., Lee, J., Xu, K., & Kumar, A. (2024). Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters. *ArXiv*. [https://arxiv.org/abs/2408.03314](https://arxiv.org/abs/2408.03314) \n\\[2\\] Zhou, A., Yan, K., Wang, H., & Wang, Y. (2023). Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models. ArXiv. https://arxiv.org/abs/2310.04406\n\\[3\\] Hao, S., Gu, Y., Ma, H., Hong, J. J., Wang, Z., Wang, D. Z., & Hu, Z. (2023). Reasoning with Language Model is Planning with World Model. ArXiv. https://arxiv.org/abs/2305.14992", "was_revised": true, "final_justification": "I have reviewed other reviews and rebuttals, and I consider all points adequately addressed during the rebuttal. \n\nRegarding 'Statistical Significance', I appreciate the statistical tests performed by the authors during the rebuttal, which demonstrate transparency that will be highly valuable to readers. Although the benefit of AB-MCTS is not game-changing, it indeed appears consistent. In any case, this paper provides a first and flexible step in this direction that easily admits refinements, which can be incorporated in the future to achieve stronger results in deployment settings.\n\nTherefore, I recommend acceptance.", "rebuttal": "We sincerely thank the reviewer for their detailed and constructive feedback. We were particularly encouraged by the reviewer's clear path to a higher score. The reviewer stated:\n\n> I invite the authors to address these comments and provide a clearer picture; in that case, I am willing to increase the score to ‘weak accept’. More conclusive results with more relevant improvements would be required for me to raise my score to a full ‘accept’.\n\nFollowing this valuable guidance, we have addressed every concern raised. While the rebuttal format prevents us from submitting a revised manuscript at this stage, we have already implemented all corresponding changes. We believe these revisions satisfy the conditions outlined for a 'weak accept'. Furthermore, by providing new comparative experiments and deeper analyses, we have endeavored to present the \"more conclusive results and relevant improvements\" that the reviewer suggested would merit a full 'accept'. We hope the reviewer will agree that our strengthened manuscript is worthy of this higher evaluation.\n\n---\n## [W1-1] Methodological Clarity and Formalism\nWe have revised Sections 3.2, 3.3, and 3.4 to include more mathematical details and to better clarify the correspondence between each step and Algorithm 1. The revised sections are provided in Appendix 1 at the end of this response.\n\n---\n## [W1-2] Walk-through Examples\nWe have revised our manuscript to include a detailed walk-through example section as recommended. The revised section is attached as Appendix 2 at the end of this response.\n\n---\n## [W2-1] Baselines\nWe appreciate the reviewer's proposal for avoiding misinterpretation of the existing literature. Accordingly, we have revised the \"Related Work\" and \"Experimental Setup\" sections.\n\nWe also thank them for the constructive suggestion to include the comparison with vanilla progressive widening. We added a new experiment in Appendix C.4, which evaluates the performance of progressive widening using the branching limit $kn^\\alpha$ for various parameters $k,\\alpha$, where $n$ is the node visit count.\n### Content of Appendix C.4\nTo compare the progressive widening with AB-MCTS, we conducted an experiment on LiveCodeBench for progressive widening with various parameters. We used `deepseek-v3-0324` (the only `deepseek-v3` version available via official API at the time) with a generation budget $2^7$.\n||$(k, \\alpha)=(1, 0.45)$|$(k, \\alpha)=(5, 0.5)$|$(k, \\alpha)=(10, 0.55)$|AB-MCTS-A(Gaussian)|AB-MCTS-A(Beta)|AB-MCTS-M|\n|-|-|-|-|-|-|-|\n|Pass@1|48.7±0.8|50.7±1.3|50.5±3.1|48.9±2.0|**51.8±1.4**|49.6±1.6|\n\nThe results are shown in Table 3. While an adequate progressive widening parameter leads to strong performance comparable to AB-MCTS, its effectiveness is highly sensitive to hyperparameters. For instance, it yields the worst result with $(k,\\alpha)=(1,0.45)$. Furthermore, $(k, \\alpha) = (10,0.55)$ setting shows search instability, leading to the highest variance. In contrast, AB-MCTS is robust without such tuning, demonstrating its practical advantage.\n\n---\n## [W2-2] Metrics\nOur initial reporting of Pass@2 for ARC-AGI was to adhere to the standard evaluation protocol for that specific benchmark [Francois et al. 2024]. However, we agree that providing Pass@1 results improves transparency. Below are the Pass@1 results on ARC-AGI for GPT-4o:\n||Pass@1|Pass@2|\n|-|-|-|\n|Repeated Sampling|14.0±1.7|15.0±1.0|\n|Sequential Refinement|7.7±0.6|8.7±0.95|\n|Standard MCTS|8.0±1.0|9.0±1.5|\n|AB-MCTS-M|11.0±1.0|12.3±1.2|\n|AB-MCTS-A(Gaussian)|13.0±3.6|13.0±3.6|\n|AB-MCTS-A(Beta)|12.7±0.6|14.0±2.1|\n\nThe table shows consistent trends between Pass@1 and Pass@2. We observed the same trend for DeepSeek-V3. We have added these results to Appendix C.5 and revised the captions for all tables to explicitly state the metric.\n\n---\n## [Q1] Clarification on MCTS Baseline\nWe employed the latter approach (cutting the last generation) in our experiment, and we revised our manuscript to include the clarification on this point at the end of section 4.2.\n\n---\n## [Q2] Further Analysis of Search Tree Topology\nWe agree that analyzing the node degree distribution offers a more granular view of our algorithm's behavior and strength. We have plotted the distribution (max budget=$2^7$), and the results clearly demonstrate our method's adaptive nature:\n- For AB-MCTS-M, the search is focused on depth: 90% of non-leaf nodes have a small degree (1-3). The remaining nodes show a long tail with degrees up to 40, which confirms that the search adaptively broadens when required.\n- AB-MCTS-A performs a much wider search. Low-degree nodes (1-3) account for 30%, and the distribution spreads broadly with degrees reaching over 100.\n\nWe have added these plots and a detailed discussion to Appendix C.6.\n\n---\n## [Q3] Towards the Pareto Frontier\nFollowing the advice, we have added a new discussion to the Appendix on future directions for pushing the Pareto frontier. This new section outlines two key strategies:\n1. **Enhanced Adaptivity via Difficulty Estimation**: We propose to enhance our algorithm's existing depth-width balancing by explicitly estimating problem difficulty from collected rewards. For difficult problems (identified by low rewards), the strategy would dynamically switch, e.g., from a deep search (AB-MCTS-M) to a wide one (AB-MCTS-A). This is motivated by findings that optimal search strategies depend on difficulty [Snell et al. 2024].\n2. **Collaborative Search with Multiple LLMs:** We also propose a method that leverages the diverse strengths of different LLMs within a single search. This is implemented by extending AB-MCTS with multiple GEN nodes, one for each LLM. Our preliminary experiment has already confirmed this to be a promising direction, showing its potential as a fruitful area for future work.\n\n---\n## Appendix 1: Method Revision\n### 3.2 Adaptive Branching MCTS\n…\n\n**Thompson Sampling for Node Selection.**\nIn our proposed methods, we employ a Bayesian approach with Thompson sampling for node selection. Here, we employ Thompson sampling because GEN nodes do not have child nodes, making it impossible to compute their UCT scores. In addition, Thompson sampling has the advantage of allowing node expansion in parallel. This is particularly beneficial when evaluating node scores is time-consuming, as in the case of MLE-Bench (See Appendix B.1 for MLE-Bench details).\n\nConcretely, during `SelectChild` step at line 11 of Algorithm 1, we employ Thompson sampling to decide between expanding a GEN node or selecting from existing child nodes at node $N$. Let $N$ be a node with potential actions $A_N = \\\\{a_0,a_1,\\dots,a_{n_{\\rm child}}\\\\}$, where the action $a_0$ corresponds to choosing the GEN node, and $a_1, \\dots, a_{n_{\\rm child}}$ correspond to choosing the already-existing child nodes. Suppose $P_{N}(r \\mid a_i)$ is the posterior predictive distribution of the score $r$ for an eventually expanded new node ($N_{\\text{new}}$ at line 5 of Algorithm 1) if we choose the action $a_i$ at node $N$. Then Thompson sampling proceeds by \n1. Calculate $P_{N}(r \\mid a_j)$ for each action $a_j$ at node $N$.\n1. Draw scores $r_{N_\\text{new},a_j}$ from $P_N(r \\mid a_j)$ for each action $a_j$.\n1. Select $\\hat{a} = \\arg\\max_{a_j \\in A_N} r_{N_\\text{new},a_j}$.\n\nThis three-step process corresponds to a single call to `SelectChild`.\n\nA key question is how to perform step 1, i.e., how to model and calculate $P_N(r \\mid a_j)$ for all $a_j$, in particular for $j=0$ (i.e., GEN node). …\n\n(3.3 and 3.4 revisions omitted due to length limit)\n\n---\n## Appendix 2: Walk‑through Examples\nWe walk through an iteration of AB-MCTS-M and AB-MCTS-A on the example trees in Figures 2 and 3. The process is stochastic due to Thompson sampling; for clarity, we assume specific sampled outcomes.\n\n### AB‑MCTS‑M\nAB-MCTS-M incrementally builds the search tree by adding one node at a time. This section details one complete iteration of the AB-MCTS-M algorithm, clearly illustrating the sequence of selecting a node to expand, performing the expansion, and backing up the score. For simplicity and concreteness, we use the tree structure depicted in Figure 2.\n\n1. **($N \\to N_1$)** At $N$, we compute posterior distributions for its four children, GEN, $N_1$, $N_2$, and $N_3$ under the mixed model, and draw one score from each. If GEN receives the highest sample, it is expanded and its score is backed up (Algorithm 1, lines 11–13). Here, we assume that $N_1$ attains the highest sampled score, reflecting exploitation of a child whose posterior peak is comparatively large.\n2. **($N_1 \\to N_1'$)** $N_1$ has two direct children, $N_1'\\;(r = 0.8)$ and $N_2'\\;(r = 1.0)$. We compute posteriors for GEN, $N_1'$, and $N_2'$, then sample again. Although the subtree $T(N_2')$ currently contains nodes with higher score, as we can see from Figure 2, the finite variance of its posterior ensures that $N_2'$ is not always selected, and encourages more exploration for under-explored tree regions. Suppose $N_1'$ is chosen on this iteration.\n3. **(Expanding $N_1'$)** Because $N_1'$ is a leaf, we expand it (Algorithm 1, line 10). Assume the newly generated node receives the score $r = 0.5$. Since all the leaf nodes have a GEN child, a GEN node is appended to this expanded node as well. \n4. **(Score backup)** The score is backed up to the ancestors, and the sampled score influences subsequent posterior updates. At the next `SelectExpansionTarget` call, the four posteriors at $N$ have different shapes; specifically, the peak of $N_1$’s posterior shifts left due to the lowered expected value. Other posterior distributions are affected as well, e.g., the right‑hand tail of the GEN posterior contracts. Please note that, in AB-MCTS-M, the change of posterior distribution shape cannot be analytically written down and is calculated by MCMC. Thus, unlike standard MCTS, the score backup step involves appending the new score to a list of scores.\n\n(AB-MCTS-A explanation omitted due to length limit)"}, {"review_id": "iaBUwhCkid", "reviewer": "Reviewer_Mkvu", "summary": "This paper presents an adaptive-branching version of MCTS-based LLM inference to find the highest performing sequence under a fixed budget of LLM calls, given an external verifier. The approach uses a Bayesian selection strategy to either generate a new child node or refine an existing child at a particular node in the search tree based on an estimated posterior predictive and Thompson sampling.", "questions": "1. How are the parameters decided for the priors used in the mixed and aggregate models? Do you have experiments evaluating how sensitive the performance is to this choice?\n2. Why is the width for standard MCTS fixed to 5, simply because previous works did that? For a fair comparison, it would be helpful to find the width (even a single setting across tasks) that performs the best and then show a comparison with the adaptive method.\n3. Why are the standard deviations not reported despite repeat runs being executed? It would be useful to conclude whether the reported performance differences are significant or not.\n4. While a reasonable choice, it is unclear to me how much the Bayesian selection mechanism adds value beyond a simpler UCT-style counting mechanism. Related, it remains unclear from the current description in the main text why progressive widening is not applicable in this setting. Could you provide an extended explanation?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:** I like the motivation of the paper and think the presented approach makes sense given that each problem instance may require very different search tree shapes to behave optimally. The paper is written clearly, and the experiments seem thorough.\n\n**Weaknesses:** It would've been useful to tune the standard MCTS baseline to provide a more robust comparison, which would have also strengthened the case for wanting a dynamic branching factor. Additionally, standard deviations for the experiment results would have been very useful since temperature-based LLM sampling can have high variance.", "was_revised": true, "final_justification": "The authors have provided additional experiments and analyses, which do indicate merit in the method. Additionally, the extended explanations vis-a-vis prior work is convincing to the extent of meriting this new method. My score would have been higher if the empirical results were stronger. Overall, I think this could be a good contribution.", "rebuttal": "We are grateful for the reviewer's valuable feedback on our manuscript. We have carefully addressed **all the weaknesses and questions** raised. Although we cannot submit a revised version at this stage due to the rebuttal format, we have already implemented all the necessary revisions based on the reviewer's suggestions. Below is a summary of our responses and new results:\n\n* **[W1/Q2] Tuning the MCTS Baseline:** Provided new experiments to vary the MCTS baseline's branching factor.\n* **[W2/Q3] Reporting on Result Variance:** Added standard deviations to result tables, confirming their statistical reliability.\n* **[Q1] Hyperparameter Sensitivity of AB-MCTS:** Conducted experiments to analyze hyperparameter sensitivity and confirmed the method's robustness.\n* **[Q4-1] Rationale for a Non-UCT Approach:** UCT score cannot be used because of unbounded branching, while the Bayesian method can incorporate it naturally.\n* **[Q4-2] Comparison with Progressive Widening:** Compared AB-MCTS with progressive widening in new experiments, showing our method is more robust and consistent.\n\nWe elaborate on each of these points below.\n\n\n---\n\n## [W1/Q2] Tuning the MCTS Baseline\n\n**TLDR:** Provided new experiments to vary the MCTS baseline's branching factor.\n\nFollowing the reviewer's valuable suggestion, we conducted experiments to vary the MCTS baseline's branching factor. Our initial choice of branching factor $w=5$ was based on its common use as a standard baseline setting in prior work. However, we agree that running this additional experiment provides a fairer comparison and highlights the benefits of our adaptive method.\n\nWe tested standard MCTS with fixed branching factors ($w$) of 3, 5, and 10 on LiveCodeBench using `deepseek-v3`. The results are as follows:\n||$w=3$|$w=5$|$w=10$|\n|-|-|-|-|\n|Pass@1|0.429±0.018|0.432±0.021|0.402±0.015|\n\nThe results confirm that $w=5$ (the setting from our original manuscript) is indeed the optimal fixed width among those tested. Crucially, performance degrades with other settings, highlighting the sensitivity of the baseline to this hyperparameter. This finding underscores a key advantage of our adaptive method.\n\nWe have revised our manuscript to add these experimental results to Appendix C. We are grateful for this suggestion, as it has significantly strengthened our experimental evaluation.\n\n---\n\n## [W2/Q3] Reporting on Result Variance\n\n**TLDR:** Added standard deviations to result tables, confirming their statistical reliability.\n\nWe agree with the reviewer that including standard deviations is crucial for providing a clearer and more reliable picture of our experimental outcomes.\nWe have updated our main results table (Table 1 in the paper) to include standard deviations, as shown below:\n|Method|LiveCodeBench (GPT-4o)|LiveCodeBench (DeepSeek-V3)|CodeContest (GPT-4o)|CodeContest (DeepSeek-V3)|ARC-AGI (GPT-4o)|ARC-AGI (DeepSeek-V3)|Avg. Rank|\n|-|-|-|-|-|-|-|-|\n|Repeated Sampling|37.8±0.5 (4)|40.7±1.9 (6)|37.9±0.3 (4)|43.2±0.9 (5)|15.0±1.0 (1)|18.6±1.0 (1)|3.5\n|Sequential Refinement|37.8±2.4 (4)|41.6±0.6 (5)|30.1±0.3 (6)|41.6±0.9 (6)|8.7±0.9 (6)|10.0±0.6 (6)|5.5\n|Standard MCTS|36.7±1.0 (6)|43.2±2.1 (1)|37.5±0.0 (5)|43.8±0.9 (3)|9.0±1.5 (5)|14.0±1.5 (5)|4.2\n|AB-MCTS-M|38.9±1.9 (2)|43.0±1.5 (2)|40.6±1.0 (1)|44.6±0.9 (2)|12.3±1.2 (4)|16.0±1.0 (3)|2.3\n|AB-MCTS-A(Gaussian)|39.1±1.9 (1)|42.5±1.5 (3)|40.2±1.7 (3)|43.4±0.9 (4)|13.0±3.6 (3)|18.3±0.6 (2)|2.7\n|AB-MCTS-A(Beta)|38.7±1.2 (3)|42.3±0.8 (4)|40.4±0.3 (2)|44.8±0.6 (1)|14.0±2.1 (2)|16.6±0.6 (4)|2.7\n\nThe updated table confirms that the strong performance of our AB-MCTS methods is consistent across multiple runs. This addition makes our experimental findings significantly more robust.\n\n---\n\n## [Q1] Hyperparameter Sensitivity of AB-MCTS\n\n**TLDR:** Conducted experiments to analyze hyperparameter sensitivity and confirmed the method's robustness.\n\nThe reviewer asks two important questions regarding our priors: (1) how these hyperparameters were chosen and (2) how sensitive performance is to this choice. We address both points below.\n\nAs we state in Appendix B.2, we chose the prior parameters to be as non-informative as possible to minimize bias. We hypothesized that the influence of these initial priors would be minimal, as the posterior distributions become increasingly dominated by observed data as the search progresses (see Appendix B.2). However, we agree with the reviewer on the importance of empirically verifying this.\n\nTo investigate this, we conducted a comprehensive sensitivity analysis. We ran new experiments on LiveCodeBench with a maximum generation budget of 16, using `gpt-4o` ($n=5$ runs), while varying the hyperparameters for each AB-MCTS variant.\n\nThe results are presented below:\n\n**Table 1. AB-MCTS-M, $\\breve{m}$**\n|$\\breve{m}$|0.0|0.4|0.5|0.6|1.0|\n|-|-|-|-|-|-|\n|Pass@1|38.4±1.6|37.3±0.4|36.8±1.5|37.5±1.5|37.7±1.3|\n\n\n**Table 2. AB-MCTS-M, $\\breve{\\alpha}$**\n|$\\breve{\\alpha}$|0.01|0.1|0.2|0.3|1.0|\n|-|-|-|-|-|-|\n|Pass@1|38.4±1.3|37.7±0.9|36.8±1.5|38.2±2.3|38.6±1.8|\n\n**Table 3. AB-MCTS-M, $\\breve{\\tau}$**\n|$\\breve{\\tau}$|0.01|0.1|0.2|0.3|1.0|\n|-|-|-|-|-|-|\n|Pass@1|37.3±2.0|38.2±1.1|37.1±1.2|36.8±1.5|39.5±1.3|\n\n**Table 4. AB-MCTS-A (Gaussian), $\\breve{m}$**\n|$\\breve{m}$|0.0|0.1|0.5|1.0|\n|-|-|-|-|-|\n|Pass@1|38.0±1.6|37.0±1.4|37.3±1.5|37.7±0.7|\n\n**Table 5. AB-MCTS-A (Gaussian), $\\breve{\\kappa}$**\n|$\\breve{\\kappa}$|0.001|0.5|1.0|10.0|\n|-|-|-|-|-|\n|Pass@1|38.4±1.3|37.3±1.5|38.0±1.6|37.7±0.7|\n\n**Table 6. AB-MCTS-A (Gaussian), $\\breve{\\nu}$**\n|$\\breve{\\nu}$|0.001|0.5|1.0|10.0|\n|-|-|-|-|-|\n|Pass@1|38.2±1.3|37.7±1.3|38.0±1.6|38.9±1.0|\n\n**Table 7. AB-MCTS-A (Gaussian), $\\breve{\\tau}^2$**\n|$\\breve{\\tau}^2$|0.05|0.1|0.2|0.5|1.0|\n|-|-|-|-|-|-|\n|Pass@1|37.5±0.9|38.0±1.6|37.7±1.3|37.9±0.8|37.7±0.7|\n\n\n**Table 8. AB-MCTS-A (Beta), $\\breve{\\alpha}$**\n|$\\breve{\\alpha}$|0.1|0.4|0.5|0.6|1.0|\n|-|-|-|-|-|-|\n|Pass@1|37.3±1.5|37.0±1.5|37.5±1.3|37.5±1.3|37.7±1.2|\n\n**Table 9. AB-MCTS-A (Beta), $\\breve{\\beta}$**\n|$\\breve{\\beta}$|0.1|0.4|0.5|0.6|1.0|\n|-|-|-|-|-|-|\n|Pass@1|38.4±1.8|38.4±1.1|37.5±1.3|37.9±0.5|37.9±1.4|\n\nAs shown in Tables 1-9 above, the performance is stable across a wide range of hyperparameter values, with most results falling within the standard deviation of each other. This confirms that our method is not sensitive to the initial choice of priors. We have revised the paper to include this full analysis in Appendix B.2 to more concretely demonstrate the robustness of our method.\n\n---\n\n## [Q4-1] Rationale for a Non-UCT Approach\n\n**TLDR:** UCT score cannot be used because of unbounded branching, while the Bayesian method can incorporate it naturally.\n\nThank you for pointing out the need to justify the additional complexity of our Bayesian mechanism. We added the following clarification after \"Adaptive Branching via the GEN Node\" paragraph in Section 3.2:\n\nThe UCT score is inapplicable to our AB-MCTS because GEN nodes make the problem fundamentally different from a standard multi-armed bandit problem, for which UCT was designed. In standard MCTS, the arms (branches) are static. In contrast, the GEN node in AB-MCTS dynamically generates new arms. This special problem setting, where arms are generated on the fly, prevents the direct application of UCT. We, therefore, adopt a Bayesian probabilistic model. This enables Thompson sampling based on the posterior distribution and obviates the need for complex UCB-style confidence bound analysis.\n\n---\n\n## [Q4-2] Comparison with Progressive Widening\n\n**TLDR:** Compared AB-MCTS with progressive widening in new experiments, showing our method is more robust and consistent.\n\nWe thank the reviewer for the opportunity to clarify the key differences between our approach and progressive widening. We clarified the key differences between our approach and progressive widening in Appendix A.2 and added a new comparative experiment in Appendix C.4.\n\n### Revision of Appendix A.2 \nThe progressive widening has parameters $k,\\alpha$ which bounds the number of branching factors by $kn^\\alpha$ with node visit count $n$. Therefore, the potential number of branches is determined a priori when we pick specific hyperparameters. \nIn contrast, our approach does not limit the branching factors with hyperparameters. Instead, the branching factor adapts dynamically by the observed rewards. This is an important requirement for LLM test-time inference scaling, where a tree search that purely goes wide is known to be a strong baseline. To demonstrate the robustness of AB-MCTS, we conducted an experiment to compare AB-MCTS and progressive widening in Appendix C.4.\n### Content of Appendix C.4\nTo compare the progressive widening with AB-MCTS, we conducted an experiment on LiveCodeBench for progressive widening with various parameters. We used `deepseek-v3-0324` (the only `deepseek-v3` version available via official API at the time) with a generation budget $2^7$.\n||$(k, \\alpha)=(1, 0.45)$|$(k, \\alpha)=(5, 0.5)$|$(k, \\alpha)=(10, 0.55)$|AB-MCTS-A(Gaussian)|AB-MCTS-A(Beta)|AB-MCTS-M|\n|-|-|-|-|-|-|-|\n|Pass@1|48.7±0.8|50.7±1.3|50.5±3.1|48.9±2.0|**51.8±1.4**|49.6±1.6|\n\nThe results are shown in Table 3. While an adequate progressive widening parameter leads to strong performance comparable to AB-MCTS, its effectiveness is highly sensitive to hyperparameters. For instance, it yields the worst result with $(k,\\alpha)=(1,0.45)$. Furthermore, $(k, \\alpha) = (10,0.55)$ setting shows search instability, leading to the highest variance. In contrast, AB-MCTS is robust without such tuning, demonstrating its practical advantage.\n\n---\n\nWe thank the reviewer again for their valuable feedback. We believe our responses and revisions fully address all concerns and have significantly strengthened the manuscript."}, {"review_id": "IF1XOAZ8aQ", "reviewer": "Reviewer_hmeP", "summary": "The paper proposes  modified forms of MCTS. In standard MCTS, only leaf nodes are expanded and a fixed set of child nodes are expanded. The modified versions of MCTS instead add a child node (to every node) called GEN, which when called, expands the parent node again. Two selection policies are introduced called AB-MCTS-M and AB-MCTS-A that use either a mixed model for scoring or aggregate node values and are estimated with Gaussian or Beta distributions. The different versions are evaluated on different tasks and perform better than different baselines.", "questions": "- What is the computation cost from adaptive MCTS? \n- Why are there two versions of adaptive MCTS? Is one better for some applications than others?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths: \n- The new MCTS variants introduced are novel and a creative solution to fixed-width MCTS. (Originality) \n- The paper identifies an important weakness of MCTS which is that it favors exploration over exploitation. (Significance)\n- The methods do well under smaller generation budget. (Quality) \n\nWeaknesses:\n- While the conceptual motivation is clear, the experimental results do not show large gains from the approach making it hard to justify the extra complexity. (Quality)\n- It is not clear what the computation cost is from the new methods compared to typical MCTS. (Clarity)", "was_revised": true, "final_justification": "My main concerns were the small increase in performance and the computational overhead. The authors addressed this with statistical significance tests in another rebutal response and provided computational costs for the different methods on a CPU. \n\nThe paper identifies and generates a unique solution to an existing problem that has not been addressed. Given the popularity of MCTS techniques, it is an important development and would be of great interest to the community.", "rebuttal": "We would like to thank the reviewer for the thoughtful feedback on our manuscript. We have carefully addressed **all the weaknesses and questions** raised. Although the rebuttal format precludes the submission of a revised manuscript at this stage, we have incorporated all the necessary changes into the manuscript based on the feedback. The key revisions we have made are summarized below:\n\n* **[W1] Performance Gains:** The manuscript has been revised to further emphasize that AB-MCTS exhibits superior robustness across a diverse range of tasks.\n* **[W2/Q1] Computational Overhead:** We measured the overhead and found that it is not the practical bottleneck.\n* **[Q2] Rationale for Two AB-MCTS Designs:** We have clarified the rationale for our two designs by elaborating on the different trade-offs for each method.\n\nWe elaborate on each of these points below.\n\n---\n\n## [W1] Performance Gains\n\n**TLDR:** AB-MCTS exhibits superior robustness across a diverse range of tasks.\n\n> While the conceptual motivation is clear, the experimental results do not show large gains from the approach making it hard to justify the extra complexity. (Quality)\n\nWe thank the reviewer for the opportunity to clarify the advantage of AB-MCTS. As shown in the `Avg. Rank` columns in Tables 1 and 2, the strength of our method lies in its robustness, delivering top-level performance across a variety of tasks. We revised our manuscript to further clarify this point in Appendix A.2 as follows:\n\nIn other baseline methods, the branching factor is either predetermined or determined by hyperparameters. For example, we need to predefine the branching factor in standard MCTS. However, the efficiency of the width vs depth strongly depends on the type of tasks and LLMs. This is reflected in Table 1 and Table 2, where AB-MCTS shows robust performance across various task types, while other methods excel for some tasks, but not for others. This is due to the adaptive branching nature of AB-MCTS, where the algorithm adapts to the wide or deep direction depending on the observed rewards. This is beneficial in the context of LLM test-time scaling, since recently LLM has been used for solving various kinds of tasks, e.g., math tasks, coding tasks, etc., and a search algorithm that works for various task types out of the box is in high demand.\n\n---\n\n## [W2/Q1] Computational Overhead\n\n**TLDR:** We measured the overhead and found that it is not the practical bottleneck.\n\n> It is not clear what the computation cost is from the new methods compared to typical MCTS. (Clarity)\n\n> What is the computation cost from adaptive MCTS?\n\nWe thank the reviewer for the insightful comment, which is crucial for clarifying the properties of AB-MCTS. To quantify the computational overhead, we measured the execution times of our proposed methods against Standard MCTS.\n\nWe used the same machine used in our experiments. Since all algorithms are CPU-intensive, we measured the wall-clock time. The experiments were conducted with a generation budget of 128, and for Standard MCTS, we used a branching factor of 5. Reward values are drawn from a uniform random distribution $U[0,1)$.\nThe results from 50 runs are presented below, showing the average execution time per one MCTS step. All units are in milliseconds (ms).\n\n|Algorithm|Mean|Stdev|Minimum|Maximum|\n|:-|-:|-:|-:|-:|\n|Standard MCTS|$1.28 \\times 10^{-2}$|$9.54 \\times 10^{-4}$|$1.21 \\times 10^{-2}$|$1.73 \\times 10^{-2}$|\n|AB-MCTS-M|$1.56 \\times 10^{4}$|$4.47 \\times 10^{2}$|$1.48 \\times 10^{4}$|$1.68 \\times 10^{4}$|\n|AB-MCTS-A (Gaussian)|$2.28 \\times 10^{0}$|$5.37 \\times 10^{-1}$|$1.14 \\times 10^{0}$|$3.3 \\times 10^{0}$|\n|AB-MCTS-A (Beta)|$1.91 \\times 10^{0}$|$3.27 \\times 10^{-1}$|$1.23 \\times 10^{0}$|$2.62 \\times 10^{0}$|\n\nThe execution time for AB-MCTS-A, regardless of the prior used, is approximately 2 ms, which is about x150 longer than Standard MCTS (0.013 ms). On the other hand, AB-MCTS-M shows a substantial increase compared to Standard MCTS and AB-MCTS-A, averaging 15600 ms.\nHowever, this overhead must be evaluated in the context of the entire system, particularly one that involves LLM calls. A single call to an LLM typically takes from tens of seconds to several minutes.\nAssuming a typical value of 1 minute per call, the overhead of AB-MCTS-A is negligible compared to the LLM call latency. Furthermore, even for the most computationally intensive method, AB-MCTS-M, its execution time (16 seconds) accounts for only about 26% of a LLM call time (60 seconds). Therefore, this suggests that the search process by AB-MCTS does not become the computational bottleneck of the overall process.\n\nWhile the execution time of AB-MCTS-M appears slow, this is primarily because its implementation was not actively optimized, as the practical bottleneck of the overall process lies in the time-consuming LLM calls and task evaluations. The bottleneck within AB-MCTS-M is its MCMC fitting process, which can be significantly accelerated, for example, through computation on a GPU.\n\n---\n\n## [Q2] Rationale for Two AB-MCTS Designs\n\n**TLDR:** We revised our paper to add elaboration on the different trade-offs for each method.\n\n> Why are there two versions of adaptive MCTS? Is one better for some applications than others?\n\nThank you for the important and pragmatic question. We revised our manuscript to include a clarification on this point as a new section in the Appendix. We summarize the revision below.\n\nWhen outcome quality is the main priority, AB-MCTS-M is often the preferred choice because of its consistently strong performance (Tables 1 and 2). For node selection, this algorithm uses MCMC, an iterative procedure that improves effectiveness but incurs some computational cost per selection. For applications with strict time constraints, AB-MCTS-A offers a lighter alternative, as its posterior updates are done analytically. However, as the LLM-inference time or the time required to evaluate the generated candidate solutions often dominate, the extra time spent on MCMC has little impact on total runtime.\n\nWhile both algorithms feature adaptive search, Figures 5 and 9 show that AB-MCTS-A tends to construct wider search trees due to its core design: Reaching depth $d$ requires $d$ consecutive CONT choices, so deeper paths become geometrically less likely than wider expansions. Therefore, for tasks such as ARC-AGI, where broader exploration is considered particularly beneficial, AB-MCTS-A can be preferable.\n\nUltimately, the choice depends on the application's primary goal: AB-MCTS-M often performs well when outcome quality is prioritized, whereas AB-MCTS-A offers advantages in computational efficiency and for tasks that benefit from broader exploration. However, both provide capable adaptive search strategies.\n\n---\n\nOnce again, we would like to thank the reviewer for the valuable feedback. We believe that our responses and the corresponding revisions have fully addressed all the concerns raised, and we hope the manuscript is now suitable for publication. Please do not hesitate to let us know if any further clarification is required."}]

Author rebuttal:

Meta-review: This paper extends MCTS-based test-time computation for LLMs by incorporating progressive widening, while leveraging the statistical property that all actions are drawn from the same LLM distribution. This enables a more efficient search process. Building on this idea, the authors propose two approaches: Adaptive-Branching MCTS Mixed-Model and Adaptive-Branching MCTS Node-Aggregation. Experiments on LiveCodeBench, CodeContest, ARC-AGI, and MLE-Bench demonstrate that the proposed methods are more robust across diverse settings, outperforming Best-of-N, Self-Refine, and standard MCTS baselines in improving performance through test-time computation.

The studied problem of this paper is very important, and the experiments are comprehensive. There are several minor weaknesses in the experiments as mentioned by the reviewers, and the authors have provided sufficient feedback.

In the rebuttal, the authors have addressed all the concerns proposed by the reviewers. The final scores from all the reviewers are positive. I recommend acceptance.
Decision: Accept (spotlight)