TY - GEN
T1 - MITS
T2 - 30th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2026
AU - Li, Jiaxi
AU - Shi, Yucheng
AU - Huang, Xiao
AU - Lu, Jin
AU - Liu, Ninghao
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.
PY - 2026/6
Y1 - 2026/6
N2 - 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. The code is available at https://github.com/plusnli/MITS.
AB - 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. The code is available at https://github.com/plusnli/MITS.
KW - Large Language Models
KW - Reasoning
UR - https://www.scopus.com/pages/publications/105041822265
U2 - 10.1007/978-981-92-1462-4_23
DO - 10.1007/978-981-92-1462-4_23
M3 - Conference article published in proceeding or book
AN - SCOPUS:105041822265
SN - 9789819214617
T3 - Lecture Notes in Computer Science
SP - 288
EP - 300
BT - Advances in Knowledge Discovery and Data Mining - 30th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2026, Proceedings
A2 - Wong, Raymond Chi-Wing
A2 - Tong, Hanghang
A2 - Lu, Hua
A2 - Kwok, James
A2 - Salim, Flora
A2 - Song, Yuanfeng
A2 - Yiu, Man Lung
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 9 June 2026 through 12 June 2026
ER -