Interpretable Contrastive Monte Carlo Tree Search Reasoning

## Abstract

Abstract We propose (S) peculative (C) ontrastive MCTS ∗ : a novel Monte Carlo Tree Search (MCTS) reasoning algorithm for Large Language Models (LLMs), significantly improves both reasoning accuracy and speed. Our motivation comes from: 1. Previous MCTS LLM reasoning works often overlooked its biggest drawback—slower speed compared to CoT; 2. Previous research mainly used MCTS as a tool for LLM reasoning on various tasks with limited quantitative analysis or ablation studies of its components from reasoning interpretability perspective. 3. The reward model is the most crucial component in MCTS, however previous work has rarely conducted in-depth study or improvement of MCTS’s reward models. Thus, we conducted extensive ablation studies and quantitative analysis on components of MCTS, revealing the impact of each component on the MCTS reasoning performance of LLMs. Building on this, (i) we designed a highly interpretable reward model based on the principle of contrastive decoding and (ii) achieved an average speed improvement of 51.9% per node using speculative decoding. Additionally, (iii) we improved UCT node selection strategy and backpropagation used in previous works, resulting in significant performance improvement. We outperformed o1-mini by an average of 17.4% on the Blocksworld multi-step reasoning dataset using Llama-3.1-70B with SC-MCTS ∗ . Our code is available at https://github.com/zitian-gao/SC-MCTS .

## 1 Introduction

With the remarkable development of Large Language Models (LLMs), models such as o1 (OpenAI, ) have now gained strong ability to multi-step reasoning across complex tasks and solve problems that are more difficult than previous scientific, code, and mathematical problems. The reasoning task has long been considered challenging for LLMs. These tasks require converting a problem into a series of reasoning steps and then executing those steps to arrive at the correct answer. Recently, LLMs have shown great potential in addressing such problems. A key approach is using Chain of Thought (CoT) (Wei et al., ), where LLMs break down the solution into a series of reasoning steps before arriving at the final answer. Despite the impressive capabilities of CoT-based LLMs, they still face challenges when solving problems with an increasing number of reasoning steps due to the curse of autoregressive decoding (Sprague et al., ). Previous work has explored reasoning through the use of heuristic reasoning algorithms. For example, Yao et al. () applied heuristic-based search, such as Depth-First Search (DFS) to derive better reasoning paths. Similarly, Hao et al. () employed MCTS to iteratively enhance reasoning step by step toward the goal.

The tremendous success of AlphaGo (Silver et al., ) has demonstrated the effectiveness of the heuristic MCTS algorithm, showcasing its exceptional performance across various domains (Jumper et al., ; Silver et al., ). Building on this, MCTS has also made notable progress in the field of LLMs through multi-step heuristic reasoning. Previous work has highlighted the potential of heuristic MCTS to significantly enhance LLM reasoning capabilities. Despite these advancements, substantial challenges remain in fully realizing the benefits of heuristic MCTS in LLM reasoning.

Figure: Figure 1: An overview of SC-MCTS^∗. We employ a novel reward model based on the principle of contrastive decoding to guide MCTS Reasoning on Blocksworld multi-step reasoning dataset.
Refer to caption: extracted/5920265/fig/Fig1.png

The first key challenge is that MCTS’s general reasoning ability is almost entirely dependent on the reward model’s performance (as demonstrated by our ablation experiments in Section 5.5), making it highly challenging to design dense, general yet efficient rewards to guide MCTS reasoning. Previous works either require two or more LLMs (Tian et al., ) or training epochs (Zhang et al., ), escalating the VRAM and computational demand, or they rely on domain-specific tools (Xin et al., ; ) or datasets (Qi et al., ), making it difficult to generalize to other tasks or datasets.

The second key challenge is that MCTS is significantly slower than Chain of Thoughts (CoT). CoT only requires designing a prompt of multi-turn chats (Wei et al., ). In contrast, MCTS builds a reasoning tree with 2–10 layers depending on the difficulty of the task, where each node in the tree represents a chat round with LLM which may need to be visited one or multiple times. Moreover, to obtain better performance, we typically perform 2–10 MCTS iterations, which greatly increases the number of nodes, leading to much higher computational costs and slower reasoning speed.

To address the these challenges, we first went beyond previous LLM reasoning works who primarily treated MCTS as an tool rather than analyzing and improving its components, to study each component of MCTS related to the reward model. We redesigned the reward model for MCTS reasoning based on the principle of contrastive decoding: specifically, we first combined multiple highly interpretable reward functions in contrast with a small model, then identified their modes by clustering the prior distributions, and normalized the rewards separately for each mode. We found the Upper Confidence Bound applied on Trees (UCT) strategy that is often set *a priori* in most previous works failed to function in our experiments, and the performance is sensitive to choices of the exploration constant. We also refined the backpropagation of MCTS to prefer more steadily improving paths. These changes boost the performance of our MCTS system. Finally, we incorporated speculative decoding into MCTS to address the speed challenge.

The contributions of our new method, SC-MCTS^∗, are summarized as follows:

- 1.
We went beyond previous works who primarily treated MCTS as an tool rather than analyzing and improving its components. Specifically, we found the UCT strategy in most previous works may failed to function from our experiment. We also refined the backpropagation of MCTS to prefer more steadily improving paths, boosting performance.
- 2.
To fully study the interpretability of MCTS multi-step reasoning, we conducted extensive quantitative analysis and ablation studies on every component. We carried out numerous experiments from both the numerical and distributional perspectives of the reward models, as well as its own interpretability, providing better interpretability for MCTS multi-step reasoning.
- 3.
We designed a novel, general action-level reward model for MCTS multi-step reasoning based on the principle of contrastive decoding, which requires no external tools, training, or datasets. Additionally, we found that previous works often failed to effectively harness multiple reward models, thus we proposed a statistical linear combination method. At the same time, we introduced token-level speculative decoding which incurs no additional cost and speeds up MCTS reasoning by an average of 52%, as contrastive decoding also requires a smaller language model.

We demonstrated the effectiveness of our approach by outperforming OpenAI’s flagship o1-mini model by an average of 17.4% using Llama-3.1-70B on the Blocksworld multi-step reasoning dataset.

## 2 Related Work

#### Large Language Models Multi-Step Reasoning

One of the key focus areas for LLMs is understanding and enhancing their reasoning capabilities. Recent advancements in this area focused on developing methods that improve LLMs’ ability to handle complex tasks in domains like code generation and mathematical problem-solving. Chain-of-Thought (CoT) (Wei et al., ) reasoning has been instrumental in helping LLMs break down intricate problems into a sequence of manageable steps, making them more adept at handling tasks that require logical reasoning. Building upon this, Tree-of-Thought (ToT) (Yao et al., ) reasoning extends CoT by allowing models to explore multiple reasoning paths concurrently, thereby enhancing their ability to evaluate different solutions simultaneously. Complementing these approaches, Monte Carlo Tree Search (MCTS) has emerged as a powerful reasoning method for decision-making in LLMs. Originally successful in AlphaGo’s victory (Silver et al., ), MCTS has been adapted to guide model-based planning by balancing exploration and exploitation through tree-based search and random sampling, and later to large language model reasoning (Hao et al., ), showing great results. This adaptation has proven particularly effective in areas requiring strategic planning. Notable implementations like ReST-MCTS^∗ (Zhang et al., ), rStar (Qi et al., ), MCTSr (Zhang et al., ) and Xie et al. () have shown that integrating MCTS with reinforced self-training, self-play mutual reasoning or Direct Preference Optimization (Rafailov et al., ) can significantly improve reasoning capabilities in LLMs. Furthermore, recent advancements such as Deepseek Prover (Xin et al., ; ) demonstrates the potential of these models to understand complex instructions such as formal mathematical proof.

#### Decoding Strategies

Contrastive decoding and speculative decoding both require Smaller Language Models (SLMs), yet few have realized that these two clever decoding methods can be seamlessly combined without any additional cost. The only work that noticed this was Yuan et al. (), but their proposed speculative contrastive decoding focused on token-level decoding. In contrast, we designed a new action-level contrastive decoding to guide MCTS reasoning, the distinction will be discussed further in Section 4.1. For more detailed related work please refer to Appendix B.

## 3 Preliminaries

### 3.1 Multi-Step Reasoning

A multi-step reasoning problem can be modeled as a Markov Decision Process (Bellman, ) $\mathcal{M}=(S,A,P,r,\gamma)$. $S$ is the state space containing all possible states, $A$ the action space, $P(s^{\prime}|s,a)$ the state transition function, $r(s,a)$ the reward function, and $\gamma$ the discount factor. The goal is to learn *and* to use a policy $\pi$ to maximize the discounted cumulative reward $\mathbb{E}_{\tau\sim\pi}\left[\sum_{t=0}^{T}\gamma^{t}r_{t}\right]$. For reasoning with LLMs, we are more focused on using an existing LLM to achieve the best reasoning.

### 3.2 Monte Carlo Tree Search

Monte Carlo Tree Search (MCTS) is a decision-making algorithm involving a search tree to simulate and evaluate actions. The algorithm operates in the following four phases:

Node Selection: The selection process begins at the root, selecting nodes hierarchically using strategies like UCT as the criterion to favor a child node based on its quality and novelty.

Expansion: New child nodes are added to the selected leaf node by sampling $d$ possible actions, predicting the next state. If the leaf node is fully explored or terminal, expansion is skipped.

Simulation: During simulation or “rollout”, the algorithm plays out the “game” randomly from that node to a terminal state using a default policy.

Backpropagation: Once a terminal state is reached, the reward is propagated up the tree, and each node visited during the selection phase updates its value based on the simulation result.

Through iterative application of its four phases, MCTS efficiently improves reasoning through trials and heuristics, converging on the optimal solution.

### 3.3 Contrastive Decoding

We discuss vanilla Contrastive Decoding (CD) from Li et al. (), which improves text generation in LLMs by reducing errors like repetition and self-contradiction. CD uses the differences between an expert model and an amateur model, enhancing the expert’s strengths and suppressing the amateur’s weaknesses. The CD objective is defined as:

$$ ${\mathcal{L}}_{\text{CD}}(x_{\text{cont}},x_{\text{pre}})=\log p_{\text{EXP}}( x_{\text{cont}}|x_{\text{pre}})-\log p_{\text{AMA}}(x_{\text{cont}}|x_{\text{ pre}})$ $$

where $p_{\text{EXP}}$ and $p_{\text{AMA}}$ are the expert and amateur probability distributions.

To avoid penalizing correct behavior of the amateur or promoting implausible tokens, CD applies an adaptive plausibility constraint using an $\alpha$-mask, which filters tokens by their logits against a threshold:

$$ $V_{\text{valid}}=\{i\mid s^{(i)}_{\text{EXP}}\geq\log\alpha+\max_{k}s^{(k)}_{ \text{EXP}}\}$ $$

Final logits are adjusted with a coefficient $(1+\beta)$, modifying the contrastive effect on output scores (Liu et al., ):

$$ $s^{(i)}_{\text{CD}}=(1+\beta)s^{(i)}_{\text{EXP}}-s^{(i)}_{\text{AMA}}$ $$

However, our proposed CD is at action level, averaging over the whole action, instead of token level in vanilla CD. Our novel action-level CD reward more robustly captures the differences in confidence between the expert and amateur models in the generated answers compared to vanilla CD. The distinction will be illustrated in Section 4.1 and explained further in Appendix A.

### 3.4 Speculative Decoding

Based on vanilla Speculative Decoding (Leviathan et al., ), the process can be summarized as follows: Let $M_{p}$ be the target model we aim to accelerate, with $p(x_{t}|x_{<t})$ representing its distribution for a given prefix $x_{<t}$. Let $M_{q}$ be a smaller, more efficient approximation model, with $q(x_{t}|x_{<t})$ representing its distribution. The key idea is to generate $\gamma$ new tokens using $M_{q}$ and evaluate them against $M_{p}$, accepting those that align with $M_{p}$’s distribution.
Each evaluation of $M_{p}$ on the new tokens which is parallel can produce at least one new token according to $p(x)$ in the end, with potentially many more tokens if they get accepted.

Specifically, speculative decoding first samples $x\sim q(x)$ autoregressively $\gamma$ times and keep them as long as $q(x)\leq p(x)$. If $q(x)>p(x)$ at some point, that sample is rejected with probability $1-\frac{p(x)}{q(x)}$, and a new sample is drawn from an adjusted distribution:

$$ $p^{\prime}(x)=\text{norm}(\max(0,p(x)-q(x)))$ $$

This ensures that the final sample distribution always follows $p(x)$. Since contrastive decoding and speculative decoding both require smaller language model, after employing our proposed action level contrastive decoding, we can achieve the acceleration effect of speculative decoding without additional cost (Yuan et al., ).

## 4 Method

The SC-MCTS^∗ reasoning methodology is outlined as follows: In Section 4.1 details the multi-reward design; Section 4.2 discusses the UCT strategy for node selection; and Section 4.3 proposes the refinement of backpropagation.

### 4.1 Multi-Reward Design

SC-MCTS^∗ is guided by three highly interpretable reward models: contrastive JS divergence, loglikelihood and self evaluation.
Previous work such as (Hao et al., ) often directly adds reward functions with mismatched numerical magnitudes without any prior statistical analysis or linear combination. As a result, their combined reward models may fail to demonstrate full performance. Moreover, combining multiple rewards online presents numerous challenges such as distributional shifts in the values. Thus, we propose a statistically-informed reward combination method: Multi-RM method. Each reward model is normalized contextually by the fine-grained prior statistics of its empirical distribution. The pseudocode for reward model construction is shown in Algorithm 1. Please refer to Appendix D for a complete version of SC-MCTS^∗ that includes other improvements such as dealing with distribution shift when combining reward functions online.

Figure: Algorithm 1 SC-MCTS^∗, reward model construction

#### Jensen-Shannon Divergence

Inspired by contrastive decoding, we propose a novel reward model: average Jensen-Shannon divergence between the expert model’s logits and the amateur model’s logits.
Unlike vanilla contrastive decoding (Li et al., ), which operates at the token level, our novel reward is computed at the action level, treating a sequence of action tokens as a whole:

$$ $R_{\text{JSD}}=\frac{1}{n}\sum_{i=T_{\text{prefix}}+1}^{n}\left[\mathrm{JSD}(p _{\text{e}}(x_{i}|x_{<i})\,\|\,p_{\text{a}}(x_{i}|x_{<i})\right]$ $$

where $p_{\text{e}}$ and $p_{\text{a}}$ represent the softmax probabilities of the expert model and the amateur model, respectively.
This approach ensures that the reward captures model behavior at the action level, as the entire sequence of tokens is taken into account at once. This contrasts with token-level methods like vanilla contrastive decoding, where each token is treated serially.

#### Loglikelihood

Inspired by Hao et al. (), we use a loglikelihood reward model to evaluate the quality of generated answers based on a given question prefix. The model computes logits for the full sequence (prefix + answer) and accumulates the log-probabilities over the answer part tokens.

Let the full sequence $x=(x_{1},x_{2},\dots,x_{T_{\text{total}}})$ consist of a prefix and a generated answer. The loglikelihood reward $R_{\text{LL}}$ is calculated over the answer portion:

$$ $R_{\text{LL}}=\sum_{i=T_{\text{prefix}}+1}^{T_{\text{total}}}\log\left(\frac{ \exp(z_{\theta}(x_{i}))}{\sum_{x^{\prime}\in V}\exp(z_{\theta}(x^{\prime}))}\right)$ $$

where $z_{\theta}(x_{i})$ represents the unnormalized logit for token $x_{i}$. After calculating logits for the entire sequence, we discard the prefix and focus on the answer tokens to form the loglikelihood reward.

#### Self Evaluation

Large language models’ token-level self evaluation can effectively quantify the model’s uncertainty, thereby improving the quality of selective generation (Ren et al., ). We instruct the LLM to perform self evaluation on its answers, using a action level evaluation method, including a self evaluation prompt to explicitly indicate the model’s uncertainty.

After generating the answer, we prompt the model to evaluate the quality of its response by asking "Is this answer correct/good?" This serves to capture the model’s confidence in its own output, leading to more informed decision-making. The self evaluation prompt’s logits are then used to calculate a reward function. Similar to the loglikelihood reward model, we calculate the self evaluation reward $R_{\text{SE}}$ by summing the log-probabilities over the self-evaluation tokens or obtaining the log-probability of a single ’good’ token in between.

#### Harnessing Multiple Reward Models and Modes

We collected prior distributions for the reward factors and found some of them span multiple regions. Therefore, we compute the fine-grained prior statistics as mean and standard deviation of modes of the prior distribution ${\mathcal{R}}\in\{{\mathcal{R}}_{\text{JSD}},{\mathcal{R}}_{\text{LL}},{
\mathcal{R}}_{\text{SE}}\}$:

$$ $\mu^{(k)}=\frac{1}{c_{k}}\sum_{R_{i}\in\rinterval{b_{k}}{b_{k+1}}}R_{i}\quad \text{and}\quad\sigma^{(k)}=\sqrt{\frac{1}{c_{k}}\sum_{R_{i}\in\rinterval{b_{k }}{b_{k+1}}}(R_{i}-\mu^{(k)})^{2}}$ (1) $$

where $b_{1}<b_{2}<\dots<b_{K+1}$ are the region boundaries in ${\mathcal{R}}$, $R_{i}\in{\mathcal{R}}$, and $c_{k}$ is the number of $R_{i}$s in $\rinterval{b_{k}}{b_{k+1}}$. Instead of using formal clustering algorithms like k-means, we manually define the regions based on the clear boundaries in the reward’s empirical distribution.

After we computed the fine-grained prior statistics, the reward factors are normalized separately for each region (which degenerates to standard normalization if only a single region is found):

$$ $R_{\text{norm}}(x)=(R(x)-\mu^{(k^{*})})/\sigma^{(k^{*})},~{}\text{where}~{}k^{ *}=\operatorname*{arg\,max}\{k:b_{k}\leq R(x)\}$ (2) $$

This reward design, which we call Multi-RM method, has some caveats: first, to prevent distribution shift during reasoning, we update the mean and standard deviation of the reward functions online for each mode (see Appendix D for pseudocode); second, we focus only on cases with clearly distinct reward modes, leaving general cases for future work. For the correlation heatmap, see Appendix E.

### 4.2 Node Selection Strategy

Upper Confidence Bound applied on Trees Algorithm (UCT) (Coquelin & Munos, ) is crucial for the selection phase, balancing exploration and exploitation by choosing actions that maximize:

$$ $UCT_{j}=\bar{X}_{j}+C\sqrt{\frac{\ln N}{N_{j}}}$ $$

where $\bar{X}_{j}$ is the average reward of taking action $j$, $N$ is the number of times the parent has been visited, and $N_{j}$ is the number of times node $j$ has been visited for simulation, $C$ is a constant to balance exploitation and exploration.

However, $C$ is a crucial part of UCT. Previous work (Hao et al., ; Zhang et al., ) had limited thoroughly investigating its components, leading to potential failures of the UCT strategy. This is because they often used the default value of 1 from the original proposed UCT (Coquelin & Munos, ) without conducting sufficient quantitative experiments to find the optimal $C$. This will be discussed in detail in Section 5.4.

### 4.3 Backpropagation

After each MCTS iteration, multiple paths from the root to terminal nodes are generated. By backpropagating along these paths, we update the value of each state-action pair. Previous MCTS approaches often use simple averaging during backpropagation, but this can overlook paths where the goal achieved metric $G(p)$ progresses smoothly (e.g., $G(p_{1})=0\rightarrow 0.25\rightarrow 0.5\rightarrow 0.75$). These paths just few step away from the final goal $G(p)=1$, are often more valuable than less stable ones.

To improve value propagation, we propose an algorithm that better captures value progression along a path. Given a path $\mathbf{P}=\{p_{1},p_{2},\dots,p_{n}\}$ with $n$ nodes, where each $p_{i}$ represents the value at node $i$, the total value is calculated by summing the increments between consecutive nodes with a length penalty. The increment between nodes $p_{i}$ and $p_{i-1}$ is $\Delta_{i}=p_{i}-p_{i-1}$. Negative increments are clipped at $-0.1$ and downweighted by 0.5. The final path value $V_{\text{final}}$ is:

$$ $V_{\text{final}}=\sum_{i=2}^{n}\left\{\begin{array}[]{ll}\Delta_{i},&\text{if }\Delta_{i}\geq 0\\ 0.5\times\max(\Delta_{i},-0.1),&\text{if }\Delta_{i}<0\end{array}\right\}- \lambda\times n$ (3) $$

where $n$ is the number of nodes in the path and $\lambda=0.1$ is the penalty factor to discourage long paths.

## 5 Experiments

### 5.1 Dataset

Blocksworld (Valmeekam et al., ; ) is a classic domain in AI research for reasoning and planning, where the goal is to rearrange blocks into a specified configuration using actions like ’pick-up,’ ’put-down,’ ’stack,’ and ’unstack. Blocks can be moved only if no block on top, and only one block at a time. The reasoning process in Blocksworld is a MDP. At time step $t$, the LLM agent selects an action $a_{t}\sim p(a\mid s_{t},c)$, where $s_{t}$ is the current block configuration, $c$ is the prompt template. The state transition $s_{t+1}=P(s_{t},a_{t})$ is deterministic and is computed by rules. This forms a trajectory of interleaved states and actions $(s_{0},a_{0},s_{1},a_{1},\dots,s_{T})$ towards the goal state.

One key feature of Blocksworld is its built-in verifier, which tracks progress toward the goal at each step. This makes Blocksworld ideal for studying heuristic LLM multi-step reasoning. However, we deliberately avoid using the verifier as part of the reward model as it is task-specific. More details of Blocksworld can be found in Appendix F.

### 5.2 Main Results

To evaluate the SC-MCTS^∗ algorithm in LLM multi-step reasoning, we implemented CoT, RAP-MCTS, and SC-MCTS^∗ using Llama-3-70B and Llama-3.1-70B. For comparison, we used Llama-3.1-405B and GPT-4o for CoT, and applied 0 and 4 shot single turn for o1-mini, as OpenAI () suggests avoiding CoT prompting. The experiment was conducted on Blocksworld dataset across all steps and difficulties. For LLM settings, GPU and OpenAI API usage data, see Appendix C and G.

**Table 1: Accuracy of various reasoning methods and models across steps and difficulty modes on the Blocksworld multi-step reasoning dataset.**
| Mode | Models | Method | Steps |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Step 2 | Step 4 | Step 6 | Step 8 | Step 10 | Step 12 | Avg. |  |  |  |
| Easy | Llama-3-70B<br>~Llama-3.2-1B | 4-shot CoT | 0.2973 | 0.4405 | 0.3882 | 0.2517 | 0.1696 | 0.1087 | 0.2929 |
| RAP-MCTS | 0.9459 | 0.9474 | 0.8138 | 0.4196 | 0.2136 | 0.1389 | 0.5778 |  |  |
| SC-MCTS* (Ours) | 0.9730 | 0.9737 | 0.8224 | 0.4336 | 0.2136 | 0.2222 | 0.5949 |  |  |
| Llama-3.1-70B<br>~Llama-3.2-1B | 4-shot CoT | 0.5405 | 0.4868 | 0.4069 | 0.2238 | 0.2913 | 0.2174 | 0.3441 |  |
| RAP-MCTS | 1.0000 | 0.9605 | 0.8000 | 0.4336 | 0.2039 | 0.1111 | 0.5796 |  |  |
| SC-MCTS* (Ours) | 1.0000 | 0.9737 | 0.7724 | 0.4503 | 0.3010 | 0.1944 | 0.6026 |  |  |
| Llama-3.1-405B | 0-shot CoT | 0.8108 | 0.6579 | 0.5931 | 0.5105 | 0.4272 | 0.3611 | 0.5482 |  |
| 4-shot CoT | 0.7838 | 0.8553 | 0.6483 | 0.4266 | 0.5049 | 0.4167 | 0.5852 |  |  |
| o1-mini | 0-shot | 0.9730 | 0.7368 | 0.5103 | 0.3846 | 0.3883 | 0.1944 | 0.4463 |  |
| 4-shot | 0.9459 | 0.8026 | 0.6276 | 0.3497 | 0.3301 | 0.2222 | 0.5167 |  |  |
| GPT-4o | 0-shot CoT | 0.5405 | 0.4868 | 0.3241 | 0.1818 | 0.1165 | 0.0556 | 0.2666 |  |
| 4-shot CoT | 0.5135 | 0.6579 | 0.6000 | 0.2797 | 0.3010 | 0.3611 | 0.4444 |  |  |
| Hard | Llama-3-70B<br>~Llama-3.2-1B | 4-shot CoT | 0.5556 | 0.4405 | 0.3882 | 0.2517 | 0.1696 | 0.1087 | 0.3102 |
| RAP-MCTS | 1.0000 | 0.8929 | 0.7368 | 0.4503 | 0.1696 | 0.1087 | 0.5491 |  |  |
| SC-MCTS* (Ours) | 0.9778 | 0.8929 | 0.7566 | 0.5298 | 0.2232 | 0.1304 | 0.5848 |  |  |
| Llama-3.1-70B<br>~Llama-3.2-1B | 4-shot CoT | 0.6222 | 0.2857 | 0.3421 | 0.1722 | 0.1875 | 0.2174 | 0.2729 |  |
| RAP-MCTS | 0.9778 | 0.9048 | 0.7829 | 0.4702 | 0.1875 | 0.1087 | 0.5695 |  |  |
| SC-MCTS* (Ours) | 0.9778 | 0.9405 | 0.8092 | 0.4702 | 0.1696 | 0.2174 | 0.5864 |  |  |
| Llama-3.1-405B | 0-shot CoT | 0.7838 | 0.6667 | 0.6053 | 0.3684 | 0.2679 | 0.2609 | 0.4761 |  |
| 4-shot CoT | 0.8889 | 0.6667 | 0.6579 | 0.4238 | 0.5804 | 0.5217 | 0.5915 |  |  |
| o1-mini | 0-shot | 0.6889 | 0.4286 | 0.1776 | 0.0993 | 0.0982 | 0.0000 | 0.2034 |  |
| 4-shot | 0.9556 | 0.8452 | 0.5263 | 0.3907 | 0.2857 | 0.1739 | 0.4966 |  |  |
| GPT-4o | 0-shot CoT | 0.6222 | 0.3929 | 0.3026 | 0.1523 | 0.0714 | 0.0000 | 0.2339 |  |
| 4-shot CoT | 0.6222 | 0.4167 | 0.5197 | 0.3642 | 0.3304 | 0.1739 | 0.4102 |  |  |

From Table 1, it can be observed that SC-MCTS^∗ significantly outperforms RAP-MCTS and 4-shot CoT across both easy and hard modes, and in easy mode, Llama-3.1-70B model using SC-MCTS^∗ outperforms the 4-shot CoT Llama-3.1-405B model.

Figure: Figure 2: Accuracy comparison of various models and reasoning methods on the Blocksworld multi-step reasoning dataset across increasing reasoning steps.
Refer to caption: extracted/5920265/fig/acc.png

From Figure 2, we observe that as the reasoning path lengthens, the performance advantage of two MCTS reasoning algorithms over themselves, GPT-4o, and Llama-3.1-405B’s CoT explicit multi-turn chats and o1-mini implicit multi-turn chats (OpenAI, ) in terms of accuracy diminishes, becoming particularly evident after Step 6. The accuracy decline for CoT is more gradual as the reasoning path extends, whereas models employing MCTS reasoning exhibits a steeper decline. This trend could be due to the fixed iteration limit of 10 across different reasoning path lengths, which might be unfair to longer paths. Future work could explore dynamically adjusting the iteration limit based on reasoning path length. It may also be attributed to our use of a custom EOS token to ensure output format stability in the MCTS reasoning process, which operates in completion mode. As the number of steps and prompt prefix lengths increases, the limitations of completion mode may become more pronounced compared to the chat mode used in multi-turn chats. Additionally, we observe that Llama-3.1-405B benefits significantly from its huge parameter size, although underperforming at fewer steps, experiences the slowest accuracy decline as the reasoning path grows longer.

### 5.3 Reasoning Speed

Figure: Figure 3: Speedup comparison of different model combinations. For speculative decoding, we use Llama-3.2-1B and Llama-3.1.8B as amateur models with Llama-3.1-70B and Llama-3.1-405B as expert models, based on average node-level reasoning speed in MCTS for Blocksworld multi-step reasoning dataset.
Refer to caption: extracted/5920265/fig/speed.png

As shown in Figure 3, we can observe that the combination of Llama-3.1-405B with Llama-3.1-8B achieves the highest speedup, improving inference speed by approximately 100% compared to vanilla decoding. Similarly, pairing Llama-3.1-70B with Llama-3.2-1B results in a 51.9% increase in reasoning speed. These two combinations provide the most significant gains, demonstrating that speculative decoding with SLMs can substantially enhance node level reasoning speed. However, we can also observe from the combination of Llama-3.1-405B with Llama-3.2-1B that the parameters of SLMs in speculative decoding should not be too small, since the threshold for accepting draft tokens during the decoding process remains fixed
to prevent speculative decoding from affecting performance (Leviathan et al., ), as overly small parameters may have a negative impact on decoding speed, which is consistent with the findings in Zhao et al. (); Chen et al. ().

### 5.4 Parameters

Figure: Figure 4: Accuracy comparison of different constant $C$ of UCT on Blocksworld multi-step reasoning dataset.
Refer to caption: extracted/5920265/fig/uct.png

As discussed in Section 4.2, the constant $C$ is a crucial part of UCT strategy, which completely determines whether the exploration term takes effect. Therefore, we conducted quantitative experiments on the constant $C$, to eliminate interference from other factors, we only use MCTS base with the common reward model $R_{\text{LL}}$ for both RAP-MCTS and SC-MCTS^∗. From Figure 5 we can observe that the constant $C$ of RAP-MCTS is too small to function effectively, while the constant $C$ of SC-MCTS^∗ is the value most suited to the values of reward model derived from extensive experimental data.

From Figure 5, it can be observed that the accuracy of SC-MCTS^∗ on multi-step reasoning increases steadily with the number of iterations. During the first 1-7 iterations, the accuracy rises consistently. After the 7th iteration, the improvement in accuracy becomes relatively smaller, indicating that under the experimental setting with depth limitations, the exponentially growing exploration nodes in later iterations bring diminishing returns in accuracy.

### 5.5 Ablation Study

**Table 2: Ablation Study on the Blocksworld dataset at Step 6 under difficult mode. For a more thorough ablation study, the reward model for the MCTS base was set to pseudo-random numbers.**
| Parts of SC-MCTS^∗ | Accuracy (%) | Improvement (%) |
| --- | --- | --- |
| MCTS base | 55.92 | — |
| + $R_{\text{JSD}}$ | 62.50 | +6.58 |
| + $R_{\text{LL}}$ | 67.76 | +5.26 |
| + $R_{\text{SE}}$ | 70.39 | +2.63 |
| + Multi-RM Method | 73.68 | +3.29 |
| + Improved $C$ of UCT | 78.95 | +5.27 |
| + BP Refinement | 80.92 | +1.97 |
| SC-MCTS^∗ | 80.92 | Overall +25.00 |

As shown in Table 2, the results of the ablation study demonstrate that each component of SC-MCTS^∗ contributes significantly to performance improvements. Starting from a base MCTS accuracy of 55.92%, adding $R_{\text{JSD}}$, $R_{\text{LL}}$, and $R_{\text{SE}}$ yields a combined improvement of 14.47%. Multi-RM method further boosts performance by 3.29%, while optimizing the $C$ parameter in UCT adds 5.27%, and the backpropagation refinement increases accuracy by 1.97%. Overall, SC-MCTS^∗ achieves an accuracy of 80.92%, a 25% improvement over the base, demonstrating the effectiveness of these enhancements for complex reasoning tasks.

### 5.6 Interpretability Study

Figure: Figure 6: Distribution of reward functions of SC-MCTS^∗ on the Blocksworld multi-step reasoning dataset using Llama-3.1-70B as expert model and Llama-3.2-1B as amateur model.
Refer to caption: extracted/5920265/fig/dist.png

We observe two distinct types of reward value distributions: normal distribution and half-normal distribution (truncated normal distribution).

Normal distribution is represented by $R_{\text{LL}}$ which is computed by accumulating the log probabilities over the token indices of the answer portion from the logits. This accumulation captures the probability trends of the entire answer generation, with a symmetric and concentrated distribution, resulting in a normal distribution. This distribution reflects the balance in the reasoning process and provides a stable and interpretable guide to MCTS multi-step reasoning.

Half-normal distribution includes $R_{\text{JSD}}$ and $R_{\text{SE}}$. $R_{\text{JSD}}$ quantifies the difference in confidence between the expert model and the amateur model over the logits of the answer part. The motivation for designing this reward function stems from the principle of contrastive decoding where constraining the expert model with the amateur model significantly reduces the low-quality outputs of the expert (Li et al., ). $R_{\text{JSD}}$ introduces symmetry by averaging distributions defined as $M=\frac{1}{2}(\text{Logits}_{\text{Expert}}+\text{Logits}_{\text{Amateur}})$, which differs from KL divergence. This symmetry combined with the non-negative nature of JS divergence also leads to a half-normal distribution. $R_{\text{JSD}}$ guide MCTS reasoning by measuring the discrepancy between the models’ logits. Our ablation experiments in Section 5.5 demonstrate that $R_{\text{JSD}}$ is highly effective as a reward function, significantly improving the performance of multi-step reasoning.

The self-evaluation reward function computes the log probability of a single self evaluation token such as "good" to measure the model’s confidence in generated answer (Ren et al., ). Since it only focuses on the log probability of single specific token and relies on the model’s confidence in particular outputs, its distribution also takes the form of a half-normal distribution. This distribution reflects the uncertainty in the reasoning process especially at decision points with lower confidence.

By combining the observations from ablation experiments in Table 2 and Figure 6, we also find that reward functions whose distributions more closely resemble a normal or half-normal distribution tend to perform better. For example, $R_{\text{JSD}}$, whose shape is more aligned with a half-normal distribution compared to $R_{\text{SE}}$, also demonstrates better performance than $R_{\text{SE}}$.

From the ablation study results in Table 5.5, it can be seen that the reward model is the most critical factor for MCTS reasoning performance. Having well-interpretable reward models implies better interpretability of MCTS reasoning. By studying these highly interpretable rewards, we can gain a clearer and more explainable understanding of MCTS reasoning.

## 6 Conclusion

In this paper, we present SC-MCTS^∗, a novel and effective algorithm to enhancing the reasoning capabilities of LLMs. With extensive improvements in reward modeling, node selection strategy and backpropagation, SC-MCTS^∗ boosts both accuracy and speed, outperforming OpenAI’s o1-mini model by 17.4% on average using Llama-3.1-70B on the Blocksworld dataset. Experiments demonstrate its strong performance, making it a promising approach for multi-step reasoning tasks. For future work please refer to Appendix I. The synthesis of interpretability, efficiency and generalizability positions SC-MCTS^∗ as a valuable contribution to advancing LLMs multi-step reasoning.

## Appendix A Action-Level Contrastive Reward

We made the distinction between action-level variables and token-level variables: action-level (or step-level) variables are those that aggregate over all tokens in a reasoning step, and is typically utilized by the reasoning algorithm directly; token-level variables, by contrast, operates in a more microscopic and low-level environment, such as speculative decoding.

We found that the traditional contrastive decoding using the difference in logits, when aggregated over the sequence gives a unstable reward signal compared to JS divergence. We suspected this is due to the unbounded nature of logit difference, and the potential failure modes associated with it that needs extra care and more hyperparameter tuning.

## Appendix B More Related Work

#### Large Language Models Multi-Step Reasoning

Deepseek Prover (Xin et al., ; ) relied on Lean4 as an external verification tool to provide dense reward signals in the RL stage. ReST-MCTS^∗ (Zhang et al., ) employed self-training to collect high-quality reasoning trajectories for iteratively improving the value model. AlphaLLM (Tian et al., ) used critic models initialized from the policy model as the MCTS reward model. rStar (Qi et al., ) utilized mutual consistency of SLMs and an additional math-specific action space. Xu () proposed reconstructing fine-tuned LLMs into residual-based energy models to guide MCTS.

#### Speculative Decoding

Speculative decoding was first introduced in Leviathan et al. (), as a method to accelerate sampling from large autoregressive models by computing multiple tokens in parallel without retraining or changing the model structure. It enhances computational efficiency, especially in large-scale generation tasks, by recognizing that hard language-modeling tasks often include easier subtasks that can be approximated well by more efficient models. Similarly, DeepMind introduced speculative sampling (Chen et al., ), which expands on this idea by generating a short draft sequence using a faster draft model and then scoring this draft with a larger target model.

#### Contrastive Decoding

Contrastive decoding, as proposed by Li et al. (), is a simple, computationally light, and training-free method for text generation that can enhancethe quality and quantity by identifying strings that highlight potential differences between strong models and weak models. In this context, the weak models typically employ conventional greedy decoding techniques such as basic sampling methods, while the strong models are often well-trained large language models. This approach has demonstrated notable performance improvements in various inference tasks, including arithmetic reasoning and multiple-choice ranking tasks, thereby increasing the accuracy of language models. According to experiments conducted by O’Brien & Lewis (), applying contrastive decoding across various tasks has proven effective in enhancing the reasoning capabilities of LLMs.

## Appendix C Experimental Settings

For reproducibility, you can download the checkpoints from the Huggingface repository below and use the hyperparameters below. We utilized 4-bit quantized checkpoints in all experiments, as they only result in around 2% performance loss while providing several-fold reductions in memory usage and significantly improving inference speed (Frantar et al., ). For better output formatting to capture a single step and convert it into an MCTS node, we used the LLM’s completion mode so we set LLM to greedy sampling, and we don’t have to set an additional system prompt, simply apply prompts in Appendix F. Our experiments were all conducted on exllamav2 inference framework.

### C.1 Checkpoints

**Table 3: Checkpoints used in experiments and their links.**
| Usage | Models | Links |
| --- | --- | --- |
| Expert | Llama-3.1-405B | [https://huggingface.co/hugging-quants/Meta-Llama-3.1-405B-Instruct-GPTQ-INT4](https://huggingface.co/hugging-quants/Meta-Llama-3.1-405B-Instruct-GPTQ-INT4) |
| Llama-3.1-70B | [https://huggingface.co/hugging-quants/Meta-Llama-3.1-70B-Instruct-GPTQ-INT4](https://huggingface.co/hugging-quants/Meta-Llama-3.1-70B-Instruct-GPTQ-INT4) |  |
| Llama-3-70B | [https://huggingface.co/TechxGenus/Meta-Llama-3-70B-Instruct-GPTQ](https://huggingface.co/TechxGenus/Meta-Llama-3-70B-Instruct-GPTQ) |  |
| Amateur | Llama-3.1-8B | [https://huggingface.co/hugging-quants/Meta-Llama-3.1-8B-Instruct-GPTQ-INT4](https://huggingface.co/hugging-quants/Meta-Llama-3.1-8B-Instruct-GPTQ-INT4) |
| Llama-3-8B | [https://huggingface.co/astronomer/Llama-3-8B-Instruct-GPTQ-4-Bit](https://huggingface.co/astronomer/Llama-3-8B-Instruct-GPTQ-4-Bit) |  |
| Llama-3.2-1B | [https://huggingface.co/meta-llama/Llama-3.2-1B](https://huggingface.co/meta-llama/Llama-3.2-1B) |  |
| OpenAI | GPT-4o | [https://platform.openai.com/docs/models/gpt-4o](https://platform.openai.com/docs/models/gpt-4o) |
| o1-mini | [https://platform.openai.com/docs/models/o1](https://platform.openai.com/docs/models/o1) |  |

### C.2 Hyperparameters

**Table 4: LLM Hyperparameters and EOS tokens used in experiments.**
| Hyperparameter | Value |
| --- | --- |
| temperature | 1.0 |
| top-k | 1.0 |
| top-p | 1.0 |
| repetition_penalty | 1.0 |
| max_new_tokens | 200 |
| max_seq_len | 32768 |
| MCTS EOS: Llama-3 family | "\\n[" |
| CoT EOS: Llama-3 family | "\\n", "
" |

## Appendix D Algorithm Details of SC-MCTS ∗

The pseudocode inside MCTS reasoning of SC-MCTS^∗ is shown in Algorithm 2, based on Zhang et al. (). The complete version of SC-MCTS^∗ is: first sample a subset of problems to obtain the prior data for reward values (Algorithm 1), then use it and two SLMs, one for providing contrastive reward signals, another for speculative decoding speedup, to perform MCTS reasoning. The changes of SC-MCTS^∗ compared to previous works are highlighted in teal.

Figure: Algorithm 2 SC-MCTS^∗, reasoning

Although we sampled a small portion of the dataset as prior data for reward values, distribution shift may still occur when normalizing reward values during reasoning. Therefore, we use the following algorithm to incrementally update the mean and standard deviation of the online reward distribution:

Figure: Algorithm 3 Online incremental update of reward factor statistics

## Appendix E Reward Functions Correlation

Figure: Figure 7: Reward Functions Correlation Heatmap.
Refer to caption: extracted/5920265/fig/heatmap.png

It can be seen from Figure 7 that the correlations between the three reward functions are relatively low, absolute values all below 0.15. These low correlations of reward functions make them ideal for Multi-RM method.

## Appendix F Blocksworld Dataset

The Blocksworld dataset comprises 600 instances with varying block numbers and plan lengths. Simpler instances have 3-5 blocks, while more complex cases involve up to 25 blocks, introducing additional goals and obstacles. This setup covers a range of problem difficulties for evaluating planning algorithms.

### F.1 Difficulty Settings

According to settings of LLM Reasoners (Hao et al., ), we divide the original 600 instances of Blocksworld (Valmeekam et al., ) into two parts, Easy and Hard settings.

In the Easy Blocksworld setting, we use more friendly demonstration cases. If a problem requires a specific minimum number of steps to solve, we select other problems that require the same number of steps as demonstration cases in the context. For example, if a problem requires at least 4 steps to solve, we use other 4-step problems as demonstration examples. For each group of problems, we randomly select 10 cases to create a pool of demonstration cases, while the remaining cases form the test set (a total of 540 cases). During inference, we randomly sample 4-shot demonstration cases from this pool to construct the prompts.

In the Hard Blocksworld setting, we randomly select 10 cases from the entire dataset to create the demonstration pool. These selected cases are then excluded from the test set, leaving a total of 590 cases for testing. During inference, we randomly sample 4-shot demonstration cases from this global pool, without considering the minimum number of actions required for the test case. For example, if a problem requires at least 4 steps to solve, we may still use demonstration cases that require a different number of steps, such as 2 or 12, as there is no restriction based on the number of actions.

**Table 5: Normal Blocksworld Task Setting**
| domain_intro: |
| --- |
| I am playing with a set of objects. Here are the actions I can do: |
| pick up a block |
| unstack a block from on top of another block |
| put down a block |
| stack a block on top of another block |
| I have the following restrictions on my actions:<br>To perform the Pick Up action, the block must be clear, on the table, and my hand must be empty. Once the Pick Up action is performed, I am holding the block, and my hand is no longer empty. |
| To perform the Unstack action, the block must be clear, on top of another block, and my hand must be empty. Once the Unstack action is performed, I am holding the block, and my hand is no longer empty. |
| To perform the Put Down action, I must be holding a block. Once the Put Down action is performed, the block is on the table, my hand is empty, and the block becomes clear. |
| To perform the Stack action, I must be holding a block, and the block I want to stack it on must be clear. Once the Stack action is performed, the block is on top of another block, my hand is empty, and the block on top is no longer clear. |

### F.2 Prompts Settings of Easy Blocksworld

**Table 6: The Prompt Settings for Easy Blocksworld**
| Input Instructions: |
| --- |
| I am playing with a set of blocks where I need to arrange the blocks into stacks. Here are the actions I can do:<br>1.<br>Pick up a block<br>2.<br>Unstack a block from on top of another block<br>3.<br>Put down a block<br>4.<br>Stack a block on top of another block<br>I have the following restrictions on my actions:<br>1.<br>I can only pick up or unstack one block at a time.<br>2.<br>I can only pick up or unstack a block if my hand is empty.<br>3.<br>I can only pick up a block if the block is on the table and the block is clear. A block is clear if the block has no other blocks on top of it and if the block is not picked up.<br>4.<br>I can only unstack a block from on top of another block if the block I am unstacking was really on top of the other block.<br>5.<br>I can only unstack a block from on top of another block if the block I am unstacking is clear.<br>Once I pick up or unstack a block, I am holding the block.<br>1.<br>I can only put down a block that I am holding.<br>2.<br>I can only stack a block on top of another block if I am holding the block being stacked.<br>3.<br>I can only stack a block on top of another block if the block onto which I am stacking the block is clear.<br>Once I put down or stack a block, my hand becomes empty. |
| [STATEMENT] |
| As initial conditions I have that, the red block is clear, the hand is empty, the blue block is on top of the orange block, the red block is on the table, the orange block is on the table and the yellow block is on the table. |
| My goal is to have that the orange block is on top of the blue block.<br>My plan is as follows: |
| [End Of STATEMENT] |
| [PLAN] |
| unstack the blue block from on top of the orange block |
| put down the blue block |
| pick up the orange block |
| stack the orange block on top of the blue block |
| [PLAN END] |
| [STATEMENT] |
| As initial conditions I have that, the red block is clear, the yellow block is clear, the hand is empty, the red block is on top of the blue block, the yellow block is on top of the orange block, the blue block is on the table and the orange block is on the table. |
| My goal is to have that the orange block is on top of the red block.<br>My plan is as follows: |
| [End Of STATEMENT] |
| Output format: |
| [PLAN] |
| [LLM Completion] |
| [PLAN_END] |

### F.3 Prompts Settings of Hard Blocksworld

**Table 7: The Prompt Settings for Hard Blocksworld**
| Input Instructions: |
| --- |
| I am playing with a set of blocks where I need to arrange the blocks into stacks. Here are the actions I can do:<br>1.<br>Pick up a block<br>2.<br>Unstack a block from on top of another block<br>3.<br>Put down a block<br>4.<br>Stack a block on top of another block<br>I have the following restrictions on my actions:<br>1.<br>I can only pick up or unstack one block at a time.<br>2.<br>I can only pick up or unstack a block if my hand is empty.<br>3.<br>I can only pick up a block if the block is on the table and the block is clear. A block is clear if the block has no other blocks on top of it and if the block is not picked up.<br>4.<br>I can only unstack a block from on top of another block if the block I am unstacking was really on top of the other block.<br>5.<br>I can only unstack a block from on top of another block if the block I am unstacking is clear.<br>Once I pick up or unstack a block, I am holding the block.<br>1.<br>I can only put down a block that I am holding.<br>2.<br>I can only stack a block on top of another block if I am holding the block being stacked.<br>3.<br>I can only stack a block on top of another block if the block onto which I am stacking the block is clear.<br>Once I put down or stack a block, my hand becomes empty. |
| [STATEMENT] |
| As initial conditions I have that, the blue block is clear, the hand is empty, the blue block is on top of the red block, the red block is on the table, the orange block is on the table and the yellow block is on the table. |
| My goal is to have that the blue block is on top of the orange block.<br>My plan is as follows: |
| [End Of STATEMENT] |
| [PLAN] |
| unstack the blue block from on top of the red block |
| stack the blue block on top of the orange block |
| [PLAN END] |
| [STATEMENT] |
| As initial conditions I have that, the red block is clear, the yellow block is clear, the hand is empty, the red block is on top of the blue block, the yellow block is on top of the orange block, the blue block is on the table and the orange block is on the table. |
| My goal is to have that the orange block is on top of the red block.<br>My plan is as follows: |
| [End Of STATEMENT] |
| Output format: |
| [PLAN] |
| [LLM Completion] |
| [PLAN_END] |

## Appendix G OpenAI API Data

**Table 8: OpenAI API cost of experiments on the Blocksworld dataset.**
| Difficulty | Model | USD per instance | Total Experiment Cost (USD) |
| --- | --- | --- | --- |
| Easy (0-shot) | GPT-4o | $0.0032 | $1.73 |
| o1-mini | $0.0136 | $7.34 |  |
| Easy (4-shot) | GPT-4o | $0.0062 | $3.35 |
| o1-mini | $0.0171 | $9.23 |  |
| Hard (0-shot) | GPT-4o | $0.0032 | $1.89 |
| o1-mini | $0.0177 | $10.44 |  |
| Hard (4-shot) | GPT-4o | $0.0063 | $3.70 |
| o1-mini | $0.0172 | $10.15 |  |

Figure: Figure 8: o1-mini Step Length vs Reasoning Tokens for Zero Shot in Easy Blocksworld
Refer to caption: extracted/5920265/fig/o1_1.png

Figure: Figure 9: o1-mini Step Length vs Reasoning Tokens for Four Shot in Easy Blocksworld
Refer to caption: extracted/5920265/fig/o1_2.png

Figure: Figure 10: o1-mini Step Length vs Reasoning Tokens for Zero Shot in Hard Blocksworld
Refer to caption: extracted/5920265/fig/o1_3.png

Figure: Figure 11: o1-mini Step Length vs Reasoning Tokens for Four Shot in Hard Blocksworld
Refer to caption: extracted/5920265/fig/o1_4.png

## Appendix H GPU Usage

In the main experiments, the total GPU usage (measured in GPU hours) for different models on NVIDIA H800 SXM5 80GB GPUs shows a clear progression with model size. For RAP-MCTS, Llama-3 70B requires approximately 420 GPU hours across all steps and difficulty modes, Llama-3.1 70B model requires approximately 450 GPU hours. For SC-MCTS^∗, Llama-3 70B requires approximately 280 GPU hours across all steps and difficulty modes and difficulty modes, Llama-3.1 70B model requires approximately 300 GPU hours. For CoT, Llama-3-70B and Llama-3.1-70B both takes approximately 7 GPU hours across all steps and difficulty modes, while Llama-3.1 405B model exhibits significantly higher GPU usage, amounting to approximately 75 GPU hours. In the parameter research and algorithm development phase before main experiments, we consumed a total of around 800 GPU hours on NVIDIA A100 SXM4 80GB GPUs.

## Appendix I Future Work

In future work, we can explore utilizing more metrics-based reward models (such as the three reward models discussed in this paper) with LM-based reward models (such as Critic LLM (McAleese et al., ) and Eurus (Yuan et al., )). Additionally, there is potential to design more general methods for splitting steps in other tasks and datasets. Since step-splitting is the most challenging part of MCTS multi-step reasoning generalization, although we conducted extensive experiments on the Blocksworld multi-step reasoning dataset, which is the most suitable dataset for studying MCTS multi-step reasoning as far as we know. Some previous works have attempted to use datasets like GSM8K and MATH through extensive adaptation efforts on the datasets themselves, however, we aim to design a more general method from the perspective of step-splitting. We hope that MCTS multi-step reasoning will achieve the same level of generalization as CoT, which remains a fundamental area for future research. Future work can also attempt to combine this approach with the fine-grained compositional reasoning framework (Chen et al., ) to further explore the boundaries of MCTS multi-step reasoning capabilities.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 3
presentation: 1
questions: - Around line 241, what is n? and can you also write out JSD formula. Since the paper focus on action-level contrastive decoding and not the token-level decoding, I would expect to theoretically relate L_{CD} and Rewards (JSD, LL, SE) for these two (token level, action level) contrastive decoding. For e.g., with eqn in line 241 you can decompose p(x_i|x_{<i}) = \prod_{j=1}^{i} p(x_{j}|x_{<j}) into token level.  

- line 97, perhaps rephrase with more details. "failed to function from our experiment" does not provide much details/intution

- line 84-90, perhaps rephrase it too. not clear "modes by clustering the prior distribution"
soundness: 1
strengths: - I like the overall methodology of reconsidering different components of MCTS and improving them. 
- Achieved empirical performance is impressive, especially compared to o1.
summary: The paper proposes speculative contrastive MCTS algorithm. They redefined reward model (using an expert model) in the MCTS based on contrastive decoding. The paper also focus on improving different components of MCTS (e.g., node selection and back propagation) and achieves significant gain.
weaknesses: - The setup and requirements are not explained well. The introduction focuses on MCTS and its drawbacks but does not clearly explain the authors' goal, objective, and setup. Only in line 148 do they mention that the focus is on using existing LLMs to achieve better reasoning, but this is also not clearly presented. I would appreciate if the goal were explained in the introduction (along with a high-level setup and an example of a known expert). Additionally, in section 3.1, the authors could explain their assumption of access to an expert model.

- In Section 3.3, symbols are not explained. I had to go back and forth multiple times to speculate on the meanings of x_{count, pre}, s^{i}, V, {i}, etc.

- Throughout the paper, the authors kept mentioning a novel reward model, but it only becomes clear on page 5 that the objective is similar to distillation, which aims to mimic the expert. I would have considered adding a few papers focusing on distillation in the related works section. And explaining the setup before hand

- Since the LLM's are stochastic, can you also add uncetainity values across multiple runs in the experiments? That would be helpful.

---

confidence: 2
contribution: 3
initial_rating: 5
presentation: 2
questions: In the reward model section, it is stated: “Instead of using formal clustering algorithms like k-means, we manually define the regions based on the clear boundaries in the reward’s empirical distribution.” Can you provide more details on how these boundaries were found? 

In section 5.4, how was the constant C found? Would this parameter need to be tuned for new reasoning tasks?

What makes the reward model more interpretable than previous methods? I see how the reward distribution can help evaluate the quality of the reward function, but I am not sure I understand how it can help interpret a particular set of reward values. 

 It is worth noting that the paper has grammatical errors in the first sentences of the abstract and introduction, which should be fixed. 
“We propose (S)peculative (C)ontrastive MCTS∗: a novel Monte Carlo Tree Search (MCTS) reasoning algorithm for Large Language Models (LLMs) [which] significantly improves both reasoning accuracy and speed”
“With the remarkable development of Large Language Models (LLMs), models such as o1 (OpenAI, 2024a) have now gained [a] strong ability [for] multi-step reasoning across complex tasks and [can] solve problems that are more difficult than previous scientific, code, and mathematical problems.”
soundness: 2
strengths: The authors introduce several improvements to previous MCTS methods, and verify these improvements via an ablation study. In particular, their method of combining three reward signals and adaptively weighting them is interesting and (to my knowledge) novel. They demonstrate a clear improvement on the Blocksworld dataset against RAP-MCTS as well as CoT.
summary: This paper focuses on improving MCTS as a tool for reasoning in LLMs. The authors introduce a new method, which they call Speculative Contrastive MCTS, that refines previous methods. They create a composite reward model, introducing a method to properly normalize and combine three disparate reward signals. Further, they improve on previous work by modifying the exploration constant in UCT and better tuning the backpropogation method. Finally, they evaluate their model against Chain of Thought and RAP-MCTS (Hao et al 2023) on Blocksworld with various versions of Llama and GPT as the base model.
weaknesses: **Methodology**
The authors only evaluate their method on the Blocksworld dataset. Showing results on other reasoning datasets such as GSM-8k, even if the experiment is limited in scope, would help show that the method generalizes to different types of tasks. 

The authors could provide more detail as to how they chose hyperparameters, picked the reward clusters, etc. 

In my opinion, the claim that the model is interpretable is not sufficiently motivated. In particular, I do not see how their observations on the distributions of the reward components make the reward more interpretable. 

**Clarity**
There are significant grammatical errors which affect the clarity of the paper, and at some points the meaning of authors’ claims is ambiguous. Of course this is a minor issue as it can be easily fixed.

In the explanation of contrastive decoding, terms x_cont/x_pre and s_EXP/s_AMA are not defined.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: 1. Could you clarify how planning and reasoning are defined in your framework? What specific characteristics differentiate them?
2. How does separating planning and reasoning lead to improved outcomes in your experiments?
3. The performance of MCTS appears to be influenced by how intermediate nodes are evaluated. Could you provide insights or analysis on this aspect within your methodology?
4. Are there specific scenarios or use cases where your proposed separation provides a distinct advantage over existing integrated approaches?
soundness: 2
strengths: The introduction of a reward model based on contrastive decoding, which emphasizes action-level evaluation, enhances interpretability and robustness.
summary: This  paper introduces Speculative Contrastive Monte Carlo Tree Search (SC-MCTS*), a novel reasoning algorithm designed to enhance the performance of Large Language Models (LLMs) in multi-step reasoning tasks. The authors aim to address the limitations of previous Monte Carlo Tree Search (MCTS) implementations, such as slower reasoning speed and insufficient analysis of core components, particularly the reward model. SC-MCTS* incorporates a new reward model grounded in contrastive decoding principles, speculative decoding for speed optimization, and refined node selection and back-propagation strategies.
weaknesses: * The impact of the evaluation of intermediate nodes on MCTS performance is significant but not discussed in depth. This oversight may lead to an incomplete understanding of the method's effectiveness.
* The novelty of applying MCTS to planning is somewhat diminished by the fact that this approach is already well-established in the literature. The paper would benefit from a more thorough comparison with existing methodologies to highlight its contributions.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: - Could you further describe the MCTS process, especially how it integrates with speculative decoding?
- Compared to different search algorithms, particularly heuristic algorithms based on A*, what are the advantages of MCTS?
- The authors need to compare the efficiency and effectiveness (also known as test time scaling law) of different inference time methods to demonstrate how SC-MCTS* better balances the trade-off
- Why does using two models (Expert and Amateur) yield better results in the search context? Perhaps need to further explain where the improvements lie when combining Contrastive Decoding with MCTS compared to using only Expert model for MCTS
soundness: 2
strengths: - Shows significant improvement compared to the baseline
- Accelerates the search process by using speculative decoding
summary: This paper introduces SC-MCTS* (Speculative Contrastive MCTS), a novel Monte Carlo Tree Search algorithm for LLMs that addresses previous speed and reasoning accuracy limitations. The authors enhance MCTS through three key innovations: a contrastive decoding-based reward model, speculative decoding for 51.9% faster node processing, and improved UCT node selection and backpropagation strategies. Using Llama-3.1-70B, their method achieved a 17.4% performance improvement over o1-mini on the Blocksworld multi-step reasoning dataset.
weaknesses: - The article is unclear, especially in section 4 where the authors fail to describe how CONTRASTIVE DECODING and SPECULATIVE DECODING are applied in MCTS.
- Using MCTS in LLM reasoning is not a novel approach, as numerous papers have already discussed its application to LLMs. This paper doesn't present any innovative ideas to enhance reasoning capabilities. Although the authors claim speculative decoding as one of their contributions, this inference acceleration paradigm was already mentioned in [1].
- The experimental evaluation is limited to only Blocksworld tasks, without exploring more complex reasoning problems such as MATH and HumanEval (code generation).
- The comparison with baselines is limited, lacking comparisons with other search-based methods like TOT, beam search[2], and Q*[3].

[1]:AlphaZero-Like Tree-Search can Guide Large Language Model Decoding and Training

[2]:Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters

[3]:Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 3
questions: This paper presents a comprehensive Monte Carlo Tree Search (MCTS) method, SC-MCTS∗, which not only enhances the reasoning accuracy of Large Language Models (LLMs) but also reduces the time required for reasoning. It offers a novel and effective algorithm that significantly boosts both the accuracy and speed of reasoning, as demonstrated through extensive experiments and quantitative analysis. The authors have designed their experiments to include various models and reasoning methods, providing a robust comparison and validation of their proposed SC-MCTS∗ method.

However, a minor shortcoming of the experiments is the absence of performance evaluation on common mathematical test sets, such as GSM8k and MATH. Incorporating these benchmarks would have provided a more comprehensive assessment of the algorithm's generalization capabilities and its effectiveness across different types of reasoning tasks.
soundness: 3
strengths: see question
summary: The paper introduces SC-MCTS∗, a novel enhancement to the Monte Carlo Tree Search algorithm, designed to improve the reasoning capabilities of Large Language Models (LLMs). It combines Contrastive Decoding and Speculative Decoding to not only increase reasoning accuracy but also to significantly reduce the time consumption.
weaknesses: see question