MITS: Enhanced Tree Search Reasoning for LLMs via Pointwise Mutual Information
Jiaxi Li, Yucheng Shi, Jin Lu, Ninghao Liu
2025-10-07
Summary
This paper introduces a new method called Mutual Information Tree Search, or MITS, to help large language models (LLMs) think through problems more effectively during use, not just during training.
What's the problem?
When LLMs are used to solve complex problems, they often explore many different possible solutions, like branching out in a tree. It's hard to tell which of these partial solutions are actually good while the model is still working, and checking every possibility takes a lot of computing power. Existing methods struggle to quickly and reliably judge the quality of each step in the reasoning process.
What's the solution?
MITS uses a concept from information theory called 'mutual information' to score how useful each step in the reasoning process is. It figures out how much information each step adds to the overall solution. This allows the model to focus on the most promising paths without needing to simulate everything all the way to the end. It also cleverly decides where to spend more computing power – on the parts of the problem where the model is most uncertain. Finally, it combines the scores of different reasoning paths to make a final prediction.
Why it matters?
This research is important because it provides a more efficient and reliable way for LLMs to reason. By quickly identifying good reasoning steps and focusing computational resources effectively, MITS allows LLMs to solve complex problems better and faster, making them more practical for real-world applications.
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.