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

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

## Key facts

- Cited by 8 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 18 of its 53 references that are in the map.
- First posted on arXiv 4 Oct 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

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

- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Phi-3 Technical Report: A Highly Capable Language Model Locally on Your Phone](https://mlsanity.com/paper/2404.14219/) (2024)
- [A Survey on LLM-as-a-Judge](https://mlsanity.com/paper/2411.15594/) (2024)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [The Entropy Mechanism of Reinforcement Learning for Reasoning Language Models](https://mlsanity.com/paper/2505.22617/) (2025)
- [Step-DPO: Step-wise Preference Optimization for Long-chain Reasoning of LLMs](https://mlsanity.com/paper/2406.18629/) (2024)
- [SWE-RL: Advancing LLM Reasoning via Reinforcement Learning on Open Software Evolution](https://mlsanity.com/paper/2502.18449/) (2025)
- [Spurious Rewards: Rethinking Training Signals in RLVR](https://mlsanity.com/paper/2506.10947/) (2025)
- [A Survey on Recent Advances in LLM-Based Multi-turn Dialogue Systems](https://mlsanity.com/paper/2402.18013/) (2024)
- [The Unreasonable Effectiveness of Entropy Minimization in LLM Reasoning](https://mlsanity.com/paper/2505.15134/) (2025)
- [When To Solve, When To Verify: Compute-Optimal Problem Solving and Generative Verification for LLM Reasoning](https://mlsanity.com/paper/2504.01005/) (2025)
- [Automating Expert-Level Medical Reasoning Evaluation of Large Language Models](https://mlsanity.com/paper/2507.07988/) (2025)
- [Mitigating Hallucination Through Theory-Consistent Symmetric Multimodal Preference Optimization](https://mlsanity.com/paper/2506.11712/) (2025)
- [Mitigating Spurious Correlations Between Question and Answer via Chain-of-Thought Correctness Perception Distillation](https://mlsanity.com/paper/2509.05602/) (2025)
- [Self-Regularization with Sparse Autoencoders for Controllable LLM-based Classification](https://mlsanity.com/paper/2502.14133/) (2025)
- [Fact or Guesswork? Evaluating Large Language Models' Medical Knowledge with Structured One-Hop Judgments](https://mlsanity.com/paper/2502.14275/) (2025)

## Built on by (most cited first, 8 of 8)

- [Online Skill Learning for Web Agents via State-Grounded Dynamic Retrieval](https://mlsanity.com/paper/2606.04391/) (2026)
- [GraphVerse: A Comprehensive Visual Graph Reasoning Benchmark for Multimodal Large Language Models](https://mlsanity.com/paper/2608.06769/) (2026)
- [RSTR: Reducing SpatioTemporal Redundancy in Diffusion Transformers](https://mlsanity.com/paper/2512.14096/) (2025)
- [Palette: A Modular, Controllable, and Efficient Framework for On-demand Authorized Safety Alignment Relaxation in LLMs](https://mlsanity.com/paper/2605.24154/) (2026)
- [Self-Improving Small Object Grounding in LVLMs](https://mlsanity.com/paper/2606.01612/) (2026)
- [Beyond Fixed Budgets: Characterizing the Inelasticity and Limitations of Tree-of-Thought Reasoning Strategies](https://mlsanity.com/paper/2606.20599/) (2026)
- [DeepLook: Deeper Thinking with Lookahead](https://mlsanity.com/paper/2607.22602/) (2026)
- [SemOPT: Fixing Semantic Errors in LLM-based Optimization Modeling via Reward-Guided Search](https://mlsanity.com/paper/2609.37361/) (2026)

## Abstract (arXiv)

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. 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. The code is available at https://github.com/plusnli/MITS.