Jiaxi Li Yucheng Shi Jin Lu Ninghao Liu

摘要

树搜索（Tree search）已成为大语言模型（LLMs）在测试阶段进行推理的代表性框架，典型方法包括思维树（Tree-of-Thought）和蒙特卡洛树搜索（Monte Carlo Tree Search），这些方法通过探索多条推理路径来提升推理能力。然而，当前仍难以对中间推理步骤的质量进行即时且可靠的定量评估，而广泛路径探索又带来高昂的计算成本。为解决这一问题，我们提出了一种新颖的框架——互信息树搜索（Mutual Information Tree Search, MITS），该框架基于信息论原则指导推理过程。MITS引入了一种基于点互信息（Pointwise Mutual Information, PMI）的有效评分函数，能够在无需昂贵的前瞻模拟（look-ahead simulations）的前提下，实现对推理路径的逐步评估以及通过束搜索（beam search）进行搜索树扩展，从而在保持计算高效性的同时显著提升推理性能。此外，该框架还配备了一种基于熵的动态采样策略，可自适应地将计算资源分配给不确定性较高的推理步骤，以最大化探索收益。在最终预测阶段，MITS采用加权投票机制，融合PMI得分与预测一致性（prediction consensus）。在多种推理基准上的大量实验表明，MITS consistently 超越基线方法，构建了一个兼具理论严谨性与计算高效性的大语言模型推理新范式。