🤖 machine learning

Efficient Test-Time Inference via Deterministic Exploration of Truncated Decoding Trees

该论文提出了一种名为“不同叶子枚举”（DLE）的确定性解码方法，通过系统性地枚举截断解码树中的不同叶子节点而非随机重采样，有效避免了重复生成，从而在数学、编程及通用推理任务中显著提升了推理效率与性能。

原作者： Xueyan Li, Johannes Zenn, Ekaterina Fadeeva, Guinan Su, Mrinmaya Sachan, Jonas Geiping

发布于 2026-04-23

📖 1 分钟阅读☕ 轻松阅读

原作者： Xueyan Li, Johannes Zenn, Ekaterina Fadeeva, Guinan Su, Mrinmaya Sachan, Jonas Geiping

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

这篇论文介绍了一种让大型人工智能（LLM）在回答问题时更聪明、更省钱、更快速的新方法，叫做**“Distinct Leaf Enumeration”（简称 DLE，独特叶子枚举法）**。

为了让你轻松理解，我们可以把 AI 思考问题的过程想象成**“在迷宫里找出口”或者“在树上摘果子”**。

1. 现在的 AI 是怎么思考的？（笨办法：随机采样）

想象你让 AI 做一道数学题或写一段代码。现在的流行做法叫**“自一致性”（Self-Consistency）**。

做法：AI 会像是一个**“有点迷糊的探险家”**。它会拿着地图（题目），随机地往不同的方向走，走 5 次、10 次甚至更多次，试图找到正确的路。最后，它把这 10 次走出来的结果放在一起，看哪个答案出现得最多，就选哪个。
问题：
- 重复劳动：因为它是“随机”走的，它经常会在迷宫的前半段（比如刚出门的前几步）反复走同一条路。就像你让 5 个人去同一个地方，结果前 3 个人都走了完全一样的路，直到最后才分叉。
- 浪费资源：AI 每走一步都要消耗算力和时间。如果它反复走同一条路，就是在浪费钱和时间。
- 漏掉好路：因为它太依赖“随机运气”，可能有些好走的捷径（高概率的正确路径）它一次都没走到，反而走了很多死胡同。

论文里的图 1 就像这样：AI 生成了 5 条路线，结果前 3 条几乎一模一样，只有最后一点点不同。这就像你让 5 个厨师做菜，前 3 个厨师切菜、炒菜的前半段动作完全一样，最后才决定放盐还是放糖。这太浪费人力了！

2. DLE 是怎么做的？（聪明办法：系统性地摘果子）

DLE 提出了一种**“确定性探索”的方法。它不再让 AI 像无头苍蝇一样乱撞，而是把它变成一个“有条理的园丁”**。

把思考过程看作一棵树：
- 树干是问题的开头。
- 树枝是 AI 可能选择的下一个词（比如“是”、“否”、“加”、“减”）。
- 树叶是最终的答案。
DLE 的策略：
1. 修剪树枝：AI 不会去管那些概率极低的“杂草”（比如乱码或完全不通顺的词），只保留那些看起来靠谱的树枝（这叫“截断采样”）。
2. 不重复摘果子：DLE 会系统地检查这棵树。它先走一条最像对的树枝，一直走到头（摘一个果子）。然后，它不会重新从树根开始走，而是回到刚才分叉的地方，换另一条没走过的树枝继续走。
3. 共享前缀：这是最厉害的地方！因为所有路线的前半段（树干）都是一样的，AI 只需要计算一次树干，然后分别计算不同的树枝。就像你让 5 个人去不同的房间，他们只需要一起走到走廊（共享前缀），然后各自推开不同的门，而不是每个人都要重新从大门口走一遍。

3. 这个新方法好在哪里？（三大优势）

🚀 优势一：不撞墙，不重复（算法层面）

比喻：以前的方法是让 5 个人在迷宫里随机跑，结果 3 个人撞到了同一堵墙。DLE 的方法是给这 5 个人分配不同的任务：第一个人走左边，第二个人走右边，第三个人走中间……保证每个人都在探索新的区域。
结果：在同样的计算量下，DLE 能覆盖更多可能的正确答案，而不是浪费时间在重复的错误上。

💰 优势二：省时间、省算力（系统层面）

比喻：以前的方法是 5 个人各自从大门口重新走一遍。DLE 的方法是大家一起走到分叉口，然后分头行动。
结果：因为重复走了很多路，AI 需要生成的“新词”大大减少。论文数据显示，DLE 可以用更少的词（更少的计算步骤）达到和以前一样甚至更好的准确率。这就好比用更少的油跑完了同样的路程。

🎯 优势三：答案更准（效果层面）

比喻：因为 DLE 系统地探索了所有“靠谱”的树枝，它更有可能找到那个藏在深处的、正确的“金苹果”。
结果：在数学题（GSM8K）、写代码（HumanEval）和逻辑推理（MMLU-Pro）的测试中，DLE 的表现都比传统的随机方法要好。

4. 总结：这就像什么？

如果把 AI 解题比作**“在图书馆找一本书”**：

旧方法（随机采样）：派 10 个图书管理员进去，每个人闭着眼睛随机抽书。结果可能 5 个人都抽到了同一本《哈利波特》，而真正要找的《量子力学》没人抽到。而且大家每次都要重新从书架顶端开始找。
DLE 方法（独特叶子枚举）：派 1 个图书管理员，他手里有一张**“最可能藏书的地图”。他先找最像的那本书，如果不对，他不会**重新从书架顶端开始，而是直接走到刚才分叉的书架层，换一本没看过的书继续找。而且，他找书时，大家共用同一个梯子（共享前缀），不用每个人搬梯子。

一句话总结

DLE 让 AI 从“盲目乱撞的随机者”变成了“精打细算的探险家”，在同样的预算下，它能探索更多正确的路径，同时少做无用功，让 AI 变得更聪明、更快、更省钱。

1. 研究背景与问题 (Problem)

核心痛点：
在大语言模型（LLM）的推理阶段，自一致性（Self-Consistency） 是一种通过并行采样多条推理路径并投票来提升性能的有效策略。然而，在数学、代码等约束性领域（Constrained Domains）中，这种基于“有放回采样”（Sampling with Replacement）的方法存在严重的计算低效问题：

重复生成（Redundancy）： 模型倾向于反复生成相同的高概率前缀（Prefixes）和完整的推理路径。实验显示，在代码生成任务中，约 20% 的前缀 Token 在不同生成的轨迹中是重复的。
资源浪费： 由于重复生成，大量的计算资源（Token 生成和 KV Cache 计算）被浪费在已经探索过的相同路径上，导致在相同的计算预算下，实际探索的解空间覆盖率（Coverage）不足。
现有方法的局限：
- 束搜索（Beam Search）： 虽然显式地管理树结构，但容易导致退化的重复（Degenerate Repetitions）且多样性不足。
- 树思维（Tree-of-Thought）： 需要额外的模型提示和评估调用，计算成本过高。
- 无放回采样（Sampling without Replacement）： 现有方法通常旨在保持特定的采样分布，而非最大化搜索空间的覆盖率。

2. 方法论：Distinct Leaf Enumeration (DLE)

为了解决上述问题，作者提出了 Distinct Leaf Enumeration (DLE，不同叶子枚举) 算法。这是一种确定性的解码方法，旨在通过遍历截断的解码树来枚举不同的叶子节点，而非随机采样。

核心机制：

截断采样树（Truncated Sampling Tree）：
- 利用截断采样分布（如 Top-k, Top-p, Min-p, $\epsilon$ -sampling）定义一个“剪枝树”。
- 树的节点代表前缀，边代表满足截断条件的下一个 Token。
- 由于现代 LLM 输出分布尖锐，每个步骤的有效 Token 集（Active Set）通常很小，使得树的大小可控。
确定性扩展策略 (Deterministic Expansion)：
- 贪婪生成与分支： DLE 首先生成一条贪婪路径直到结束。然后，它回溯到具有多个有效子节点的节点（分支点），选择未被探索过的分支进行扩展。
- 优先级选择 (PROBFIRST)： 算法优先扩展当前路径概率（Path Probability）最高的分支。这确保了在有限的计算预算下，优先探索高概率区域，从而最大化搜索空间的覆盖率（Coverage）。
- 无重复叶子： 通过确定性遍历，DLE 保证生成的 $k$ 条推理轨迹是互不相同的叶子节点，彻底消除了重复采样。
早期停止机制 (Early Stopping)：
- 即使分支点不同，不同的分支在后续贪婪解码中可能会收敛到相同的后缀（即语义相似但表面形式不同的 Token 导致相同结果）。
- DLE 检测分支后的 $n$ 个连续 Token。如果新分支的后缀与已生成的兄弟分支的后缀匹配，则提前终止该分支的生成，将预算重新分配给其他未探索的分支。
- 实验表明，超过 85% 被剪枝的分支最终会产生相同的答案，因此该机制能显著减少无效计算。
系统级优化 (Prefix Reuse)：
- 由于 DLE 是树状遍历，共享的前缀（Prefix）只需计算一次。
- 结合支持前缀缓存（Prefix Caching）的推理引擎（如 SGLang 的 RadixAttention 或 vLLM），DLE 可以极大地复用 KV Cache，显著降低推理延迟和显存占用。

3. 主要贡献 (Key Contributions)

提出 DLE 算法： 一种无重复的确定性解码方法，可作为随机采样的直接替代品。它适用于多种截断采样器（Top-p, Min-p, $\epsilon$ -sampling）。
算法优势（覆盖率提升）： 在固定的 Token 预算下，DLE 比自一致性覆盖了更大的截断搜索空间概率质量（Probability Mass）。实验证明，更高的覆盖率与更好的下游任务性能（如数学推理、代码生成）呈正相关。
系统优势（效率提升）： 通过避免冗余生成和重用前缀，DLE 在相同的 Token 预算下能生成更多完整的序列。在内存受限或批处理较小的场景下，推理延迟显著降低。
广泛的实证验证： 在 GSM8K（数学）、HumanEval（代码）和 MMLU-Pro（通用推理）等多个基准测试中，DLE 均优于传统的自一致性、束搜索及其他高级推理策略。

4. 实验结果 (Results)

实验使用了 Qwen2.5 和 Llama3.2 系列模型，主要发现如下：

性能提升：
- 在 GSM8K 上，DLE 相比自一致性（Self-Consistency）提升了约 3-9% 的准确率（maj@k）。
- 在 HumanEval 上，提升了约 4-7% 的通过率（pass@k）。
- 在 MMLU-Pro 上也取得了稳定提升。
- 相比之下，传统的束搜索（Beam Search）和多样性束搜索并未带来一致的性能提升，甚至随束宽增加而性能下降。
效率与覆盖率：
- 覆盖率 - 准确率曲线： DLE 在相同的序列数量（ $k$ ）下，覆盖了更高的概率质量，因此达到了更高的准确率。
- Token 效率： 达到相同的准确率（例如 34%）， $\epsilon$ -采样的自一致性需要生成 >150 个新 Token，而 DLE 平均每个问题仅需 <20 个新 Token。
- 缓存命中率： 在 SGLang 引擎上，DLE 的实际缓存命中率（Cache Hit Rate）非常接近理论最大值，远高于基线方法。
推理速度：
- 在 SGLang 和 vLLM 上，DLE 显著降低了推理运行时间，特别是在小批量（Batch Size 1-2）和高 $\epsilon$ 值（导致更多前缀复用）的情况下，速度提升最为明显。

5. 意义与结论 (Significance & Conclusion)

重新定义测试时扩展（Test-Time Scaling）： 论文指出，有效的测试时扩展不仅仅依赖于生成更多的样本，更在于如何高效地分配计算资源。DLE 证明了通过确定性探索来消除冗余，比盲目增加采样数量更有效。
算法与系统的协同： DLE 展示了算法设计（树状遍历、去重）与系统优化（KV Cache 重用、前缀缓存）结合的巨大潜力。
适用性： 该方法特别适用于约束性推理任务（如数学、代码），在这些任务中，高概率路径往往对应正确答案，且重复采样极其浪费。
未来方向： 论文建议未来可以结合任务特定的质量信号来优化分支策略，或探索确定性探索与随机采样的混合模式，以平衡高概率区域探索与长尾分布的覆盖。

总结： DLE 通过将被动的随机采样转变为主动的、确定性的树遍历，解决了自一致性在约束域中的计算冗余问题，实现了**“更少 Token，更多覆盖，更高准确率”**的推理效率突破。