MITS: Enhanced Tree Search Reasoning for LLMs via Pointwise Mutual Information

• URL: http://arxiv.org/abs/2510.03632v1
• Date: Sat, 04 Oct 2025 02:30:40 GMT
• Title: MITS: Enhanced Tree Search Reasoning for LLMs via Pointwise Mutual Information
• Authors: Jiaxi Li, Yucheng Shi, Jin Lu, Ninghao Liu,
• Abstract summary: We propose Mutual Information Tree Search (MITS), a novel framework that guides reasoning with information-theoretic principles.<n>MITS introduces an effective scoring function based on pointwise mutual information (PMI), which enables step-wise evaluation of reasoning paths and search tree expansion.<n>For final prediction, MITS employs a weighted voting scheme that combines PMI scores with prediction consensus.
• Score: 32.43291637979958
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tree search has become as a representative framework for test-time reasoning with large language models (LLMs), exemplified by methods such as Tree-of-Thought and Monte Carlo Tree Search that explore multiple reasoning paths. However, it remains difficult to provide instant and reliable quantitative assessments of intermediate reasoning step quality, and extensive path exploration is computationally costly. To address this, we propose Mutual Information Tree Search (MITS), a novel framework that guides reasoning with information-theoretic principles. MITS introduces an effective scoring function based on pointwise mutual information (PMI), which enables step-wise evaluation of reasoning paths and search tree expansion via beam search without expensive look-ahead simulations, achieving superior reasoning performances while maintaining computational efficiency. The framework is complemented by an entropy-based dynamic sampling strategy that adaptively allocates computational resources to uncertain reasoning steps where exploration is most beneficial. For final prediction, MITS employs a weighted voting scheme that combines PMI scores with prediction consensus. Through comprehensive experiments on diverse reasoning benchmarks, MITS consistently surpasses baseline methods, establishing a principled and efficient framework for LLM reasoning.

Related papers

• Contrastive Concept-Tree Search for LLM-Assisted Algorithm Discovery [10.823958143531685]
  Large language Model (LLM)-assisted algorithm discovery is an iterative, black-box optimization process over programs.<n>Here, we introduce Contrastive Concept-Tree Search (CCTS), which extracts a hierarchical concept representation from the generated programs.<n>We show that CCTS improves search efficiency over fitness-based baselines and produces interpretable, task-specific concept trees.
  arXiv  Detail & Related papers  (2026-02-03T05:41:35Z)
• TreePS-RAG: Tree-based Process Supervision for Reinforcement Learning in Agentic RAG [71.06073770344732]
  Agentic retrieval-augmented generation (RAG) formulates question answering as a multi-step interaction between reasoning and information retrieval.<n>We present TreePS-RAG, an online, tree-based RL framework for agentic RAG that enables step-wise credit assignment while retaining outcome-only rewards.
  arXiv  Detail & Related papers  (2026-01-11T14:07:30Z)
• Reinforced Efficient Reasoning via Semantically Diverse Exploration [73.41112984160992]
  Reinforcement learning with verifiable rewards (RLVR) has proven effective in enhancing the reasoning of large language models (LLMs)<n>We propose reinforced efficient reasoning via semantically diverse explorations, i.e., ROSE, for LLMs.<n>Our method incorporates a semantic-entropy-based branching strategy and an $varepsilon$-exploration mechanism.
  arXiv  Detail & Related papers  (2026-01-08T15:56:44Z)
• Combining LLMs with Logic-Based Framework to Explain MCTS [13.276888833862447]
  We design a Computational Tree-guided large language model (LLM)-based natural language explanation framework for the Monte Carlo Tree Search (MCTS) algorithm.<n>By transforming user queries into logic and variable statements, our framework ensures that the evidence obtained from the search tree remains factually consistent.<n>We evaluate the framework rigorously through quantitative assessments, where it demonstrates strong performance in terms of accuracy and factual consistency.
  arXiv  Detail & Related papers  (2025-05-01T15:40:58Z)
• MCTS-RAG: Enhancing Retrieval-Augmented Generation with Monte Carlo Tree Search [61.11836311160951]
  We introduce MCTS-RAG, a novel approach that enhances the reasoning capabilities of small language models on knowledge-intensive tasks.<n>Unlike standard RAG methods, which typically retrieve information independently from reasoning, MCTS-RAG combines structured reasoning with adaptive retrieval.<n>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)
• MCTS-KBQA: Monte Carlo Tree Search for Knowledge Base Question Answering [5.926690985669765]
  This study explores how to enhance the reasoning capabilities of large language models (LLMs) in knowledge base question answering (KBQA) by leveraging Monte Carlo Tree Search (MCTS)<n>We design a carefully designed step-wise reward mechanism that requires only direct prompting of open-source instruction LLMs.<n>We contribute new data resources to the KBQA community by annotating intermediate reasoning processes for existing question-SPARQL datasets using distant supervision.
  arXiv  Detail & Related papers  (2025-02-19T04:58:39Z)
• Policy Guided Tree Search for Enhanced LLM Reasoning [3.090041654375235]
  Policy-Guided Tree Search (PGTS) is a framework that combines reinforcement learning with structured tree exploration to efficiently navigate reasoning paths.<n>Our key innovation is a learned policy that dynamically decides between expanding, branching, backtracking, or terminating exploration, eliminating the need for manuals or exhaustive search.
  arXiv  Detail & Related papers  (2025-02-04T22:08:20Z)
• RAG-Star: Enhancing Deliberative Reasoning with Retrieval Augmented Verification and Refinement [85.08223786819532]
  Existing large language models (LLMs) show exceptional problem-solving capabilities but might struggle with complex reasoning tasks.<n>We propose textbfRAG-Star, a novel RAG approach that integrates retrieved information to guide the tree-based deliberative reasoning process.<n>Our experiments involving Llama-3.1-8B-Instruct and GPT-4o demonstrate that RAG-Star significantly outperforms previous RAG and reasoning methods.
  arXiv  Detail & Related papers  (2024-12-17T13:05:36Z)
• Enhancing LLM Reasoning with Reward-guided Tree Search [95.06503095273395]
  o1-like reasoning approach is challenging, and researchers have been making various attempts to advance this open area of research.<n>We present a preliminary exploration into enhancing the reasoning abilities of LLMs through reward-guided tree search algorithms.
  arXiv  Detail & Related papers  (2024-11-18T16:15:17Z)
• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  The framework combines Monte Carlo Tree Search (MCTS) with iterative Self-Refine to optimize the reasoning path. The framework has been tested on general and advanced benchmarks, showing superior performance in terms of search efficiency and problem-solving capability.
  arXiv  Detail & Related papers  (2024-10-03T18:12:29Z)

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.