💬 NLP

Entropy-Tree: Tree-Based Decoding with Entropy-Guided Exploration

该论文提出了 Entropy-Tree，一种新颖的基于树结构的解码方法，它利用熵仅在模型存在真实不确定性的点上引导分支决策，从而在推理任务中相比于随机采样和独立多重采样等现有策略，实现了更优越的准确性和校准度。

原作者： Longxuan Wei, Yubo Zhang, Zijiao Zhang, Zhihu Wang, Shiwan Zhao, Tianyu Huang, Huiting Zhao, Chenfei Liu, Shenao Zhang, Junchi Yan

发布于 2026-01-23

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Longxuan Wei, Yubo Zhang, Zijiao Zhang, Zhihu Wang, Shiwan Zhao, Tianyu Huang, Huiting Zhao, Chenfei Liu, Shenao Zhang, Junchi Yan

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在要求一个非常聪明但有时过于自大的机器人去解决一个困难的数学问题或写一个复杂的故事。这个机器人并不只是进行单一的线性思考；它拥有一个巨大的、由可能出现的词汇组成的地图。

问题：机器人的两个坏习惯
目前，当机器人（大语言模型）尝试解决难题时，它们通常会采取两种方式，而这两种方式都有缺陷：

“保守型”机器人（贪婪搜索/束搜索）： 这个机器人总是选择最显而易见、最稳妥的下一个词。这就像一个游客，只走在拥挤的主干道上，因为觉得安全。他们很少迷路，但也永远无法发现那些隐藏的、惊人的捷径或独特的解决方案。他们会陷入枯燥、重复的回答循环中。
“随机型”机器人（随机采样）： 这个机器人通过完全随机地挑选词汇来尝试变得有创意。这就像一个游客，闭着眼睛原地旋转，然后朝着落下的方向走。有时他们能发现宝藏，但大多数时候，他们会在死胡同里徘徊，或者重复同样的错误。他们浪费了大量精力去探索那些无关紧要的地方。

解决方案：熵树 (Entropy-Tree)
这篇论文的作者提出了一个更聪明的引导方式。他们意识到，机器人对于它所说的每一个词，其不确定程度是不一样的。

“置信度计”（熵）： 想象一下，机器人对它考虑的每一个词都有一个置信度计。
- 低熵（高置信度）： 机器人百分之百确定。它知道下一个词应该是“the”或“and”。这只是在填充语法。
- 高熵（低置信度）： 机器人正在犹豫。它在两个截然不同的想法之间徘徊，比如“因此 (therefore)”还是“然而 (however)”，或者是两种不同的数学方程解法。这是一个分叉路口。

熵树是如何工作的：“决策分叉”策略
熵树不像是在随机到处游荡，它更像是一个聪明的向导，观察着机器人的置信度计。

确定时直行： 当机器人很有信心（低熵）时，向导就让它直接走下去。没必要浪费时间去探索。
犹豫时停下并分支： 一旦机器人遇到“分叉路口”（高熵），向导就会停下机器人。向导说：“好吧，你现在不确定。让我们同时尝试这两条路径。”
构建一棵树： 机器人现在会分裂成多个版本，从那个特定的决策点开始，每个版本尝试不同的路径。它们在到达该点之前共享相同的历史记录（节省能量），然后开始探索不同的可能性。
挑选赢家： 在结束时，向导查看所有机器人所走的路径，并选出那条通往正确答案的路径。

为什么这更好
论文声称，这种方法就像拥有一支探险队，他们只有在真正到达混乱的十字路口时才会分头行动，而不是在森林中间随机地分散开来。

更高的准确性： 因为机器人将精力集中在问题的难点上（决策分叉处），它比“随机型”机器人能更频繁地找到正确答案。
更好的自我意识： 论文还发现，这种方法有助于机器人知道自己何时错了。如果机器人分裂成许多不同的路径，且这些路径都导致了不同、冲突的答案，系统就会知道：“嘿，我们在这里真的很困惑。”这使得机器人的“不确定性评分”更加可靠。

简而言之
熵树是一种告诉 AI 的策略：“当你确定时，不要浪费时间猜测。但当你真正感到困惑和犹豫时，停下来，分裂你的注意力，并从那个特定的时刻尝试每一个可能的方向。”这带来了更聪明、更准确且更可靠的答案。

技术摘要：Entropy-Tree（熵树）

问题陈述

大语言模型（LLMs）在复杂推理任务中展现了显著的能力，然而其性能受到现有解码策略的严重制约。作者识别出当前方法存在的两个主要局限性：

盲目探索（Blind Exploration）： 诸如 top-k 和 top-p 采样等随机方法在所有 token 位置上均匀地引入随机性，而忽略了模型实际的不确定性。这导致了低效的探索，即计算资源被浪费在低不确定性的句法延续上，而非关键的决策点上。
多重采样中的冗余（Redundancy in Multi-Sampling）： 诸如自一致性（Self-Consistency）等通过生成多个独立样本以通过多数投票提高准确性的策略，存在计算冗余。这些独立路径并不共享前缀计算，且探索过程缺乏引导，可能在重复语义冗余路径的同时，错失了关键的决策分叉点。

此外，传统的确定性量化方法依赖于多次随机采样，由于采样过程本身具有随机性，这限制了不确定性评估的可靠性。

方法论：Entropy-Tree

本文提出了 Entropy-Tree，一种利用 token 熵作为分支决策信号的基于树结构的解码框架。其核心假设（得到 Wang 等人 [9] 最新发现的支持）是：token 熵分布具有高度非均匀性——大约 80% 的 token 是低熵的（高置信度、句法性的），而剩余 20% 是高熵的“决策分叉”（decision forks），它们引导着推理轨迹。

Entropy-Tree 的过程包含三个主要阶段：

1. 分支点过滤（Branch Point Filtering）

模型并非在每一步都进行分支，而是通过动态监测 token 熵（ $H_t$ ）和语义重要性来识别候选分支点：

熵阈值化（Entropy Thresholding）： 如果 token 的熵 $H_t$ 低于阈值 $\tau$ ，则使用标准的随机采样（top-k/top-p）。如果 $H_t \geq \tau$ ，则该 token 被标记为候选。
语义重要性过滤（Semantic Importance Filtering）： 为了避免在缺乏语义意义的高熵 token（例如句法填充词）上进行分支，该方法采用了自注意力分数。通过使用来自先前 token 的最大注意力值（作为重要性的代理，类似于 DRAGIN [11]），计算重要性得分 $I_t$ 。只有当 $I_t \geq \delta$ 时，才会进行分支。

2. 树扩展与规模控制（Tree Expansion and Size Control）

一旦识别出分支点：

扩展（Expansion）： 模型不再仅选择单个 token，而是选择前 $b$ 个概率最高的 token 来形成新的分支。
搜索策略（Search Strategy）： 使用广度优先搜索（BFS）算法扩展树，优先处理深度较低的节点，以确保在设定的分支步数后完成所有叶子节点的生成。
终止（Termination）： 为了防止指数级的规模爆炸，总叶子节点数被限制在 $N_{tree}$ 以内。一旦达到此限制，分支停止，剩余路径回归为标准采样，直到遇到序列结束（EOS）标记。

3. 不确定性量化（Uncertainty Quantification）

该框架同时也作为一种不确定性估计机制。预测熵是基于 Entropy-Tree 叶子节点导出的答案分布进行计算的，而非来自独立的随机采样。

核心贡献

本文概述了三项主要贡献：

新型解码框架： Entropy-Tree 通过在具有高熵、高重要性的位置进行带有前缀共享的分支，构建了树状输出。这实现了对模型决策空间的结构化探索，与随机采样的盲目探索形成对比。
提升推理准确性： 该方法在多种模型和数据集上展现出优于多链（Multi-chain，即随机独立采样）的 pass@k 性能。通过将资源集中在“决策分叉”上，模型能以更少的样本实现更高的准确率。
树衍生的不确定性量化： 基于 Entropy-Tree 叶子节点计算的预测熵具有更好的校准性。具体而言，与标准预测熵、语义熵（Semantic Entropy）及其他基准相比，它在 AUROC（受试者工作特征曲线下面积）方面表现出显著提升。

实验结果

作者使用 Qwen2.5 模型（7B, 14B, 32B）在多样化的推理数据集（SVAMP, MATH-500, SciBench, GPQA-main/diamond, 以及 AIME24/25）上对 Entropy-Tree 进行了评估。

准确率 (Pass@k)： Entropy-Tree 一致优于 Multi-chain。例如，在 MATH-500 数据集上使用 Qwen2.5-7B 时，Entropy-Tree 仅用约 2/3 的样本量（k=13 对比 k=20）就达到了与 Multi-chain 相当的 pass@k 性能。在 pass@20 的比较中，Entropy-Tree 在所有数据集上均显示出提升，尤其在 GPQA-diamond 和 AIME25 上增益显著。
校准度 (AUROC)： 由 Entropy-Tree 衍生的预测熵（ET-PE）在大多数模型和数据集上均获得了最高的 AUROC 分数，表明该方法提供了更可靠的模型不确定性度量。它显著优于在长推理文本中表现挣扎的语义熵（SE）。
消融研究：
- 分支位置： 将熵阈值从第 80 百分位数移动到第 90 百分位数（延迟分支）会导致性能下降，这表明在高熵点进行早期分支更为有效。
- 引导作用： 没有熵引导的随机分支性能明显较差，证实了高熵位置确实充当了关键的“决策分叉”。

意义与主张

本文声称 Entropy-Tree 在单一解码过程中统一了高效的结构化探索和可靠的不确定性估计。通过从盲目的均匀探索转向熵引导的探索，该方法允许 LLM 精确地在模型表现出真实不确定性的地方主动探索不同的推理路径。

作者将其定位为一种原则性的解码方法，超越了确定性（贪婪搜索）和随机性（随机采样）方法的局限。他们断言，该方法既提高了推理任务的准确性，也提高了不确定性指标的校准度，为生成大量独立样本提供了一种更具资源效率的选择。

局限性

论文承认 Entropy-Tree 需要访问 token logits 和自注意力分数，这可能会引入额外的延迟。此外，这种对模型内部状态的依赖限制了其在黑盒场景下的适用性，因为 API 无法提供这些指标。未来的工作旨在将该方法集成到现有的 LLM 推理引擎（如 vLLM）中，并探索其对强化学习采样效率的影响。