MITS: Enhanced Tree Search Reasoning for LLMs via Pointwise Mutual
  Information
Authors: name: Jiaxi Li, name: Yucheng Shi, name: Jin Lu, name: Ninghao Liu
Organization: University of Georgia

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.