# Interpretable Contrastive Monte Carlo Tree Search Reasoning

arXiv: https://arxiv.org/abs/2410.01707 · HTML: https://mlsanity.com/paper/2410.01707/

## Key facts

- Cited by 64 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 25 of its 34 references that are in the map.
- First posted on arXiv 2 Oct 2024.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)
- LLM alignment / RLHF / preference optimisation / [Process reward models for reasoning](https://mlsanity.com/alignment/process-reward-models-for-reasoning/)

## Builds on (most cited first, 25 of 25)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers](https://mlsanity.com/paper/2210.17323/) (2022)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Contrastive Decoding: Open-ended Text Generation as Optimization](https://mlsanity.com/paper/2210.15097/) (2022)
- [DExperts: Decoding-Time Controlled Text Generation with Experts and Anti-Experts](https://mlsanity.com/paper/2105.03023/) (2021)
- [PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change](https://mlsanity.com/paper/2206.10498/) (2022)
- [ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search](https://mlsanity.com/paper/2406.03816/) (2024)
- [On the Planning Abilities of Large Language Models : A Critical Investigation](https://mlsanity.com/paper/2305.15771/) (2023)
- [To CoT or not to CoT? Chain-of-thought helps mainly on math and symbolic reasoning](https://mlsanity.com/paper/2409.12183/) (2024)
- [Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning](https://mlsanity.com/paper/2405.00451/) (2024)
- [DeepSeek-Prover: Advancing Theorem Proving in LLMs through Large-Scale Synthetic Data](https://mlsanity.com/paper/2405.14333/) (2024)
- [DeepSeek-Prover-V1.5: Harnessing Proof Assistant Feedback for Reinforcement Learning and Monte-Carlo Tree Search](https://mlsanity.com/paper/2408.08152/) (2024)
- [Accessing GPT-4 level Mathematical Olympiad Solutions via Monte Carlo Tree Self-refine with LLaMa-3 8B](https://mlsanity.com/paper/2406.07394/) (2024)
- [Toward Self-Improvement of LLMs via Imagination, Searching, and Criticizing](https://mlsanity.com/paper/2404.12253/) (2024)
- [Self-Evaluation Improves Selective Generation in Large Language Models](https://mlsanity.com/paper/2312.09300/) (2023)
- [Contrastive Decoding Improves Reasoning in Large Language Models](https://mlsanity.com/paper/2309.09117/) (2023)
- [LLM Reasoners: New Evaluation, Library, and Analysis of Step-by-Step Reasoning with Large Language Models](https://mlsanity.com/paper/2404.05221/) (2024)
- [Bandit Algorithms for Tree Search](https://mlsanity.com/paper/1408.2028/) (2014)
- [Ouroboros: Generating Longer Drafts Phrase by Phrase for Faster Speculative Decoding](https://mlsanity.com/paper/2402.13720/) (2024)
- [Speculative Contrastive Decoding](https://mlsanity.com/paper/2311.08981/) (2023)

## Built on by (most cited first, 30 of 64)

- [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025)
- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [A Survey on Test-Time Scaling in Large Language Models: What, How, Where, and How Well?](https://mlsanity.com/paper/2503.24235/) (2025)
- [SoTA with Less: MCTS-Guided Sample Selection for Data-Efficient Visual Reasoning Self-Improvement](https://mlsanity.com/paper/2504.07934/) (2025)
- [Perception-R1: Pioneering Perception Policy with Reinforcement Learning](https://mlsanity.com/paper/2504.07954/) (2025)
- [S*: Test Time Scaling for Code Generation](https://mlsanity.com/paper/2502.14382/) (2025)
- [Not All Rollouts are Useful: Down-Sampling Rollouts in LLM Reinforcement Learning](https://mlsanity.com/paper/2504.13818/) (2025)
- [A Survey on (M)LLM-Based GUI Agents](https://mlsanity.com/paper/2504.13865/) (2025)
- [Hume: Introducing System-2 Thinking in Visual-Language-Action Model](https://mlsanity.com/paper/2505.21432/) (2025)
- [Training a Scientific Reasoning Model for Chemistry](https://mlsanity.com/paper/2506.17238/) (2025)
- [Does Thinking More always Help? Mirage of Test-Time Scaling in Reasoning Models](https://mlsanity.com/paper/2506.04210/) (2025)
- [A Survey of Test-Time Compute: From Intuitive Inference to Deliberate Reasoning](https://mlsanity.com/paper/2501.02497/) (2025)
- [Search and Refine During Think: Facilitating Knowledge Refinement for Improved Retrieval-Augmented Reasoning](https://mlsanity.com/paper/2505.11277/) (2025)
- [LLaVA-Critic-R1: Your Critic Model is Secretly a Strong Policy Model](https://mlsanity.com/paper/2509.00676/) (2025)
- [One-shot Entropy Minimization](https://mlsanity.com/paper/2505.20282/) (2025)
- [Two Heads are Better Than One: Test-time Scaling of Multi-agent Collaborative Reasoning](https://mlsanity.com/paper/2504.09772/) (2025)
- [AlphaOne: Reasoning Models Thinking Slow and Fast at Test Time](https://mlsanity.com/paper/2505.24863/) (2025)
- [Thinking Machines: A Survey of LLM based Reasoning Strategies](https://mlsanity.com/paper/2503.10814/) (2025)
- [AtomThink: Multimodal Slow Thinking with Atomic Step Reasoning](https://mlsanity.com/paper/2411.11930/) (2024)
- [Accelerating Large Language Model Reasoning via Speculative Search](https://mlsanity.com/paper/2505.02865/) (2025)
- [Generative AI Act II: Test Time Scaling Drives Cognition Engineering](https://mlsanity.com/paper/2504.13828/) (2025)
- [Bottom-up Domain-specific Superintelligence: A Reliable Knowledge Graph is What We Need](https://mlsanity.com/paper/2507.13966/) (2025)
- [Sample Complexity and Representation Ability of Test-time Scaling Paradigms](https://mlsanity.com/paper/2506.05295/) (2025)
- [Zero-Shot Verification-guided Chain of Thoughts](https://mlsanity.com/paper/2501.13122/) (2025)
- [Can Atomic Step Decomposition Enhance the Self-structured Reasoning of Multimodal Large Models?](https://mlsanity.com/paper/2503.06252/) (2025)
- [Guided Search Strategies in Non-Serializable Environments with Applications to Software Engineering Agents](https://mlsanity.com/paper/2505.13652/) (2025)
- [Large Reasoning Models are not thinking straight: on the unreliability of thinking trajectories](https://mlsanity.com/paper/2507.00711/) (2025)
- [Step Guided Reasoning: Improving Mathematical Reasoning using Guidance Generation and Step Reasoning](https://mlsanity.com/paper/2410.19817/) (2024)
- [Policy Guided Tree Search for Enhanced LLM Reasoning](https://mlsanity.com/paper/2502.06813/) (2025)
- [Best-of-Majority: Minimax-Optimal Strategy for Pass@k Inference Scaling](https://mlsanity.com/paper/2510.03199/) (2025)

## Abstract (arXiv)

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