Interpretable Contrastive Monte Carlo Tree Search Reasoning

• URL: http://arxiv.org/abs/2410.01707v3
• Date: Wed, 25 Dec 2024 13:32:54 GMT
• Title: Interpretable Contrastive Monte Carlo Tree Search Reasoning
• Authors: Zitian Gao, Boye Niu, Xuzheng He, Haotian Xu, Hongzhang Liu, Aiwei Liu, Xuming Hu, Lijie Wen,
• Abstract summary: We propose SC-MCTS: a novel Monte Carlo Tree Search (MCTS) reasoning algorithm for Large Language Models (LLMs)<n>We show that SC-MCTS significantly improves both reasoning accuracy and speed.<n>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*.
• Score: 25.11379135302235
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Scaling Up RL: Unlocking Diverse Reasoning in LLMs via Prolonged Training [121.5858973157225]
  We investigate the effects of prolonged reinforcement learning on a small language model across a diverse set of reasoning domains.<n>We introduce controlled KL regularization, clipping ratio, and periodic reference policy resets as critical components for unlocking long-term performance gains.<n>Our model achieves significant improvements over strong baselines, including +14.7% on math, +13.9% on coding, and +54.8% on logic puzzle tasks.
  arXiv  Detail & Related papers  (2025-07-16T17:59:24Z)
• Teaching LLM to Reason: Reinforcement Learning from Algorithmic Problems without Code [76.80306464249217]
  We propose TeaR, which aims at teaching LLMs to reason better.<n>TeaR leverages careful data curation and reinforcement learning to guide models in discovering optimal reasoning paths through code-related tasks.<n>We conduct extensive experiments using two base models and three long-CoT distillation models, with model sizes ranging from 1.5 billion to 32 billion parameters, and across 17 benchmarks spanning Math, Knowledge, Code, and Logical Reasoning.
  arXiv  Detail & Related papers  (2025-07-10T07:34:05Z)
• Mind the Gap: Bridging Thought Leap for Improved Chain-of-Thought Tuning [54.65050470296886]
  We propose the CoT Thought Leap Bridge Task, which aims to automatically detect leaps and generate missing intermediate reasoning steps.<n>We demonstrate that models fine-tuned on bridged datasets consistently outperform those trained on original datasets.<n>Our approach effectively enhances distilled data and provides better starting points for reinforcement learning.
  arXiv  Detail & Related papers  (2025-05-20T17:59:31Z)
• Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition [11.422434149376478]
  Large Language Models (LLMs) have been touted as AI models possessing advanced reasoning abilities. In theory, autoregressive LLMs with Chain-of-Thought (CoT) can perform more serial computations to solve complex reasoning tasks. Recent studies suggest that, despite this capacity, LLMs do not truly learn to reason but instead fit on statistical features.
  arXiv  Detail & Related papers  (2025-04-04T20:57:36Z)
• MCTS-RAG: Enhancing Retrieval-Augmented Generation with Monte Carlo Tree Search [27.378904180238557]
  We introduce MCTS-RAG, a novel approach that enhances the reasoning capabilities of small language models on knowledge-intensive tasks. Unlike standard RAG methods, which typically retrieve information independently from reasoning, MCTS-RAG combines structured reasoning with adaptive retrieval. This integrated approach enhances decision-making, reduces hallucinations, and ensures improved factual accuracy and response consistency.
  arXiv  Detail & Related papers  (2025-03-26T17:46:08Z)
• Innate Reasoning is Not Enough: In-Context Learning Enhances Reasoning Large Language Models with Less Overthinking [39.48406368755411]
  Large Language Models (LLMs) have introduced Reasoning Large Language Models (RLLMs) RLLMs exhibit innate Chain-of-Thought (CoT) reasoning capability obtained from training, leading to a natural question: "Is CoT prompting necessary to enhance the reasoning capability of RLLMs?" We present the first comprehensive analysis of the impacts of Zero-shot CoT and Few-shot CoT on RLLMs across mathematical reasoning tasks.
  arXiv  Detail & Related papers  (2025-03-25T12:37:22Z)
• Stop Overthinking: A Survey on Efficient Reasoning for Large Language Models [54.04678363287392]
  Large Language Models (LLMs) have demonstrated remarkable capabilities in complex tasks. Recent advancements in OpenAI o1 and DeepSeek-R1 have further improved performance in System-2 reasoning domains.
  arXiv  Detail & Related papers  (2025-03-20T17:59:38Z)
• Towards Thinking-Optimal Scaling of Test-Time Compute for LLM Reasoning [113.49074603075032]
  Recent studies have shown that making a model spend more time thinking through longer Chain of Thoughts (CoTs) enables it to gain significant improvements in complex reasoning tasks. We explore whether scaling with longer CoTs can indeed impair the reasoning performance of Large Language Models (LLMs) in certain domains.
  arXiv  Detail & Related papers  (2025-02-25T10:48:05Z)
• MCTS-Judge: Test-Time Scaling in LLM-as-a-Judge for Code Correctness Evaluation [17.432401371613903]
  We propose a resource-efficient, System-2 thinking framework for code correctness evaluation. MCTS-Judge uses Monte Carlo Tree Search to decompose problems into simpler, multi-perspective evaluations. High-precision, unit-test-level reward mechanism encourages the Large Language Model to perform line-by-line analysis.
  arXiv  Detail & Related papers  (2025-02-18T02:55:48Z)
• MME-CoT: Benchmarking Chain-of-Thought in Large Multimodal Models for Reasoning Quality, Robustness, and Efficiency [63.23935582919081]
  Chain-of-Thought (CoT) has significantly enhanced the reasoning capabilities of Large Language Models (LLMs) We introduce MME-CoT, a specialized benchmark evaluating the CoT reasoning performance of LMMs. We conduct an in-depth analysis of state-of-the-art LMMs, uncovering several key insights.
  arXiv  Detail & Related papers  (2025-02-13T18:59:46Z)
• LLMs Can Easily Learn to Reason from Demonstrations Structure, not content, is what matters! [53.84130385074551]
  Large reasoning models (LRMs) tackle complex reasoning problems by following long chain-of-thoughts (Long CoT) We find that a Large Language model (LLM) can effectively learn Long CoT reasoning through data-efficient supervised fine-tuning (SFT) and parameter-efficient low-rank adaptation (LoRA) With just 17k long CoT training samples, the Qwen2.5-32B-Instruct model achieves significant improvements on a wide range of math and coding benchmarks.
  arXiv  Detail & Related papers  (2025-02-11T08:48:48Z)
• When More is Less: Understanding Chain-of-Thought Length in LLMs [53.77747102201451]
  Chain-of-thought (CoT) reasoning enhances the multi-step reasoning capabilities of large language models (LLMs) However, for most models and tasks, does an increase in CoT length consistently lead to improved reasoning accuracy? In this paper, we observe a nuanced relationship: as the number of reasoning steps increases, performance initially improves but eventually decreases.
  arXiv  Detail & Related papers  (2025-02-11T05:28:59Z)
• MC-NEST: Enhancing Mathematical Reasoning in Large Language Models leveraging a Monte Carlo Self-Refine Tree [0.16385815610837165]
  We propose Monte Carlo Self-Refine Tree (MC-NEST) as an extension of Monte Carlo Tree Search.<n>MC-NEST integrates self-refinement and self-evaluation for improved decision-making in complex reasoning tasks.<n>It achieves state-of-the-art pass@1 scores on Olympiad-level benchmarks.
  arXiv  Detail & Related papers  (2024-11-23T20:31:58Z)
• Language Models are Hidden Reasoners: Unlocking Latent Reasoning Capabilities via Self-Rewarding [74.31981011985681]
  Large language models (LLMs) have shown impressive capabilities, but still struggle with complex reasoning tasks requiring multiple steps. We introduce LaTent Reasoning Optimization (LaTRO), a principled framework that formulates reasoning as sampling from a latent distribution. We validate LaTRO through experiments on GSM8K and ARC-Challenge datasets using multiple model architectures.
  arXiv  Detail & Related papers  (2024-11-06T22:02:30Z)
• Optimized Monte Carlo Tree Search for Enhanced Decision Making in the FrozenLake Environment [0.0]
  Monte Carlo Tree Search (MCTS) is a powerful algorithm for solving complex decision-making problems. This paper presents an optimized MCTS implementation applied to the FrozenLake environment, a classic reinforcement learning task.
  arXiv  Detail & Related papers  (2024-09-25T05:04:53Z)
• Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning [55.96599486604344]
  We introduce an approach aimed at enhancing the reasoning capabilities of Large Language Models (LLMs) through an iterative preference learning process. We use Monte Carlo Tree Search (MCTS) to iteratively collect preference data, utilizing its look-ahead ability to break down instance-level rewards into more granular step-level signals. The proposed algorithm employs Direct Preference Optimization (DPO) to update the LLM policy using this newly generated step-level preference data.
  arXiv  Detail & Related papers  (2024-05-01T11:10:24Z)
• THOUGHTSCULPT: Reasoning with Intermediate Revision and Search [45.55992387270442]
  We present THOUGHTSCULPT, a general reasoning and search method for tasks with outputs that can be decomposed into words. THOUGHTSCULPT explores a search tree of potential solutions using Monte Carlo Tree Search (MCTS), building solutions one action at a time and evaluating according to any domain-specific components. Empirically, THOUGHTSCULPT outperforms state-of-the-art reasoning methods across three challenging tasks.
  arXiv  Detail & Related papers  (2024-04-09T02:53:14Z)
• AQA-Bench: An Interactive Benchmark for Evaluating LLMs' Sequential Reasoning Ability [29.1826948551409]
  AQA-Bench is a novel benchmark to assess the sequential reasoning capabilities of large language models. We build AQA-Bench with three different algorithms, namely binary search, depth-first search, and breadth-first search. Our investigations reveal several interesting findings.
  arXiv  Detail & Related papers  (2024-02-14T18:59:33Z)
• Exploring Progress in Multivariate Time Series Forecasting: Comprehensive Benchmarking and Heterogeneity Analysis [70.78170766633039]
  We address the need for means of assessing MTS forecasting proposals reliably and fairly. BasicTS+ is a benchmark designed to enable fair, comprehensive, and reproducible comparison of MTS forecasting solutions. We apply BasicTS+ along with rich datasets to assess the capabilities of more than 45 MTS forecasting solutions.
  arXiv  Detail & Related papers  (2023-10-09T19:52:22Z)
• Beyond Task Performance: Evaluating and Reducing the Flaws of Large Multimodal Models with In-Context Learning [105.77733287326308]
  We evaluate 10 recent open-source LMMs from 3B up to 80B parameter scale, on 5 different axes; hallucinations, abstention, compositionality, explainability and instruction following. We explore the training-free in-context learning (ICL) as a solution, and study how it affects these limitations. Based on our ICL study, (3) we push ICL further and propose new multimodal ICL variants such as; Multitask-ICL, Chain-of-Hindsight-ICL, and Self-Correcting-ICL.
  arXiv  Detail & Related papers  (2023-10-01T12:02:59Z)
• Benchmarking Causal Study to Interpret Large Language Models for Source Code [6.301373791541809]
  This paper introduces a benchmarking strategy named Galeras comprised of curated testbeds for three SE tasks. We illustrate the insights of our benchmarking strategy by conducting a case study on the performance of ChatGPT under distinct prompt engineering methods.
  arXiv  Detail & Related papers  (2023-08-23T20:32:12Z)
• Exploring Self-supervised Logic-enhanced Training for Large Language Models [59.227222647741094]
  In this paper, we make the first attempt to investigate the feasibility of incorporating logical knowledge through self-supervised post-training. We devise an auto-regressive objective variant of MERIt and integrate it with two LLM series, i.e., FLAN-T5 and LLaMA, with parameter size ranging from 3 billion to 13 billion. The results on two challenging logical reasoning benchmarks demonstrate the effectiveness of LogicLLM.
  arXiv  Detail & Related papers  (2023-05-23T06:13:10Z)
• Scale-Adaptive Balancing of Exploration and Exploitation in Classical Planning [1.6574413179773757]
  We show that a more detailed theoretical understanding of MAB literature helps improve existing planning algorithms. We propose GreedyUCT-Normal, a MCTS/THTS algorithm with UCB1-Normal bandit for agile classical planning.
  arXiv  Detail & Related papers  (2023-05-16T22:46:37Z)
• TMR: Text-to-Motion Retrieval Using Contrastive 3D Human Motion Synthesis [59.465092047829835]
  We present TMR, a simple yet effective approach for text to 3D human motion retrieval. Our method extends the state-of-the-art text-to-motion synthesis model TEMOS. We show that maintaining the motion generation loss, along with the contrastive training, is crucial to obtain good performance.
  arXiv  Detail & Related papers  (2023-05-02T17:52:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.