Wider or Deeper? Scaling LLM Inference-Time Compute with Adaptive Branching Tree Search

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:

• [W1] Performance Gains: The manuscript has been revised to further emphasize that AB-MCTS exhibits superior robustness across a diverse range of tasks.
• [W2/Q1] Computational Overhead: We measured the overhead and found that it is not the practical bottleneck.
• [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.

We elaborate on each of these points below.

---

[W1] Performance Gains

TLDR: AB-MCTS exhibits superior robustness across a diverse range of tasks.

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)

We 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:

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

---

[W2/Q1] Computational Overhead

TLDR: We measured the overhead and found that it is not the practical bottleneck.

It is not clear what the computation cost is from the new methods compared to typical MCTS. (Clarity)

What is the computation cost from adaptive MCTS?

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

We 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)$. The results from 50 runs are presented below, showing the average execution time per one MCTS step. All units are in milliseconds (ms).

The 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. However, 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. Assuming 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.

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

---

[Q2] Rationale for Two AB-MCTS Designs

TLDR: We revised our paper to add elaboration on the different trade-offs for each method.

Why are there two versions of adaptive MCTS? Is one better for some applications than others?

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

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

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

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

---

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

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:

• [W1/Q2] Tuning the MCTS Baseline: Provided new experiments to vary the MCTS baseline's branching factor.
• [W2/Q3] Reporting on Result Variance: Added standard deviations to result tables, confirming their statistical reliability.
• [Q1] Hyperparameter Sensitivity of AB-MCTS: Conducted experiments to analyze hyperparameter sensitivity and confirmed the method's robustness.
• [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.
• [Q4-2] Comparison with Progressive Widening: Compared AB-MCTS with progressive widening in new experiments, showing our method is more robust and consistent.

We elaborate on each of these points below.

---

[W1/Q2] Tuning the MCTS Baseline

TLDR: Provided new experiments to vary the MCTS baseline's branching factor.

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

We tested standard MCTS with fixed branching factors ($w$) of 3, 5, and 10 on LiveCodeBench using deepseek-v3. The results are as follows:

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

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

---

[W2/Q3] Reporting on Result Variance

TLDR: Added standard deviations to result tables, confirming their statistical reliability.

We agree with the reviewer that including standard deviations is crucial for providing a clearer and more reliable picture of our experimental outcomes. We have updated our main results table (Table 1 in the paper) to include standard deviations, as shown below:

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

---

[Q1] Hyperparameter Sensitivity of AB-MCTS

TLDR: Conducted experiments to analyze hyperparameter sensitivity and confirmed the method's robustness.

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

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

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

The results are presented below:

Table 1. AB-MCTS-M, $\breve{m}$

Table 2. AB-MCTS-M, $\breve{\alpha}$

Table 3. AB-MCTS-M, $\breve{\tau}$

Table 4. AB-MCTS-A (Gaussian), $\breve{m}$

Table 5. AB-MCTS-A (Gaussian), $\breve{\kappa}$

Table 6. AB-MCTS-A (Gaussian), $\breve{\nu}$

Table 7. AB-MCTS-A (Gaussian), $\breve{\tau}^2$

Table 8. AB-MCTS-A (Beta), $\breve{\alpha}$

Table 9. AB-MCTS-A (Beta), $\breve{\beta}$

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

---

[Q4-1] Rationale for a Non-UCT Approach

TLDR: UCT score cannot be used because of unbounded branching, while the Bayesian method can incorporate it naturally.

Thank 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:

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

---

[Q4-2] Comparison with Progressive Widening

TLDR: Compared AB-MCTS with progressive widening in new experiments, showing our method is more robust and consistent.

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

Revision of Appendix A.2

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

Content of Appendix C.4

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

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

---

We thank the reviewer again for their valuable feedback. We believe our responses and revisions fully address all concerns and have significantly strengthened the manuscript.

Thank you for your detailed responses! I consider W1/Q2, W2/Q3, and Q1 well addressed. I appreciate your work on getting the additional numbers.

Regarding Q4-1 (UCT) and Q4-2 (progressive widening), I find the explanation still unsatisfactory. In particular, the reasoning provided for the incompatibility of UCT is the presence of the GEN node and dynamic branching, and the reasoning provided for not choosing progressive widening (PW) is that it selects the number of branches a priori based on hyperparameters. However, the latter statement is not quite accurate --- the branching factor in PW should surely be considered dynamic because $n$ varies over the course of MCTS for different nodes. The hyperparameters $k$ and $\alpha$ serve to control the rate of widening. Given, therefore, that PW is a valid option, one must, therefore, ask whether the introduction of GEN nodes is, in fact, necessary. With no GEN nodes, one could also then use standard UCT, which would be easily compatible with dynamic branching.

My main criticism above stems from the narrative currently that adaptive branching is not possible in MCTS, whereas, as described above, one can feasibly achieve it with existing concepts.

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:

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

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

---

[W1-1] Methodological Clarity and Formalism

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

---

[W1-2] Walk-through Examples

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

---

[W2-1] Baselines

We appreciate the reviewer's proposal for avoiding misinterpretation of the existing literature. Accordingly, we have revised the "Related Work" and "Experimental Setup" sections.

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

Content of Appendix C.4

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

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

---

[W2-2] Metrics

Our 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:

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

---

[Q1] Clarification on MCTS Baseline

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

---

[Q2] Further Analysis of Search Tree Topology

We 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:

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

We have added these plots and a detailed discussion to Appendix C.6.

---

[Q3] Towards the Pareto Frontier

Following 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:

1. 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].
2. 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.

---

Appendix 1: Method Revision

3.2 Adaptive Branching MCTS

…

Thompson Sampling for Node Selection. In 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).

Concretely, 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

1. Calculate $P_{N}(r \mid a_j)$ for each action $a_j$ at node $N$.
2. Draw scores $r_{N_\text{new},a_j}$ from $P_N(r \mid a_j)$ for each action $a_j$.
3. Select $\hat{a} = \arg\max_{a_j \in A_N} r_{N_\text{new},a_j}$.

This three-step process corresponds to a single call to SelectChild.

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

(3.3 and 3.4 revisions omitted due to length limit)

---

Appendix 2: Walk‑through Examples

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

AB‑MCTS‑M

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

1. ($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.
2. ($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.
3. (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.
4. (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.

(AB-MCTS-A explanation omitted due to length limit)