Chopping Trees: Semantic Similarity Based Dynamic Pruning for Tree-of-Thought Reasoning

📄 arXiv: 2511.08595v2 📥 PDF

作者: Joongho Kim, Xirui Huang, Zarreen Reza, Gabriel Grand

分类: cs.CL, cs.AI

发布日期: 2025-10-30 (更新: 2025-12-07)

备注: 39th Conference on Neural Information Processing Systems (NeurIPS 2025) Workshop on Efficient Reasoning

🔗 代码/项目: GITHUB

💡 一句话要点

提出基于语义相似性的动态剪枝方法，加速思维树推理。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 思维树推理 大型语言模型 语义相似性 动态剪枝 并行树搜索

📋 核心要点

  1. 思维树推理计算成本高，原因是不同分支可能探索语义上等价的推理路径，存在冗余。
  2. 提出基于语义相似性的动态剪枝（SSDP）方法，在并行树搜索中实时合并语义相似的分支并进行剪枝。
  3. 实验表明，SSDP在保持竞争力的准确率下，实现了高达2.3倍的加速，并显著减少了探索的节点数量。

📝 摘要（中文）

思维树（ToT）推理提升了大型语言模型（LLM）解决问题的能力，但由于语义冗余而导致计算成本高昂，不同的分支探索等效的推理路径。我们引入了基于语义相似性的动态剪枝（SSDP），据我们所知，这是第一个将在线语义合并集成到并行树搜索中的框架，能够实时聚类和剪枝冗余步骤。在包括GSM8K和MATH500在内的推理基准测试中，SSDP实现了高达2.3倍的加速，同时保持了具有竞争力的准确性（通常在最强基线的5%以内），并将探索的节点数量减少了85-90%，展示了一种高效、可扩展的LLM推理的实用方法。SSDP的实现可在https://github.com/kimjoonghokim/SSDP公开获取。

🔬 方法详解

问题定义：论文旨在解决思维树（Tree-of-Thought, ToT）推理中由于语义冗余导致的计算效率低下的问题。现有的ToT方法在探索多个推理分支时，经常会遇到语义相似甚至等价的推理路径，导致大量的重复计算，浪费计算资源。

核心思路：论文的核心思路是利用语义相似性来动态地识别和剪枝冗余的推理分支。通过在线地计算不同分支之间的语义相似度，将语义相似的分支合并或剪枝，从而减少需要探索的节点数量，提高推理效率。这种方法避免了对所有分支进行完全探索，从而节省了计算资源。

技术框架：SSDP框架主要包含以下几个阶段：1) 思想生成：LLM生成多个可能的推理步骤（思想）。2) 语义相似度计算：计算新生成的思想与已探索思想之间的语义相似度。3) 动态剪枝：根据语义相似度，决定是否合并或剪枝新生成的思想。如果相似度高于阈值，则合并或剪枝该分支；否则，继续探索该分支。4) 状态评估：评估每个分支的当前状态，并选择最有希望的分支继续探索。

关键创新：SSDP的关键创新在于将在线语义合并集成到并行树搜索中，实现了实时地聚类和剪枝冗余步骤。与传统的静态剪枝方法不同，SSDP能够根据当前已探索的推理路径动态地调整剪枝策略，从而更有效地减少冗余计算。此外，SSDP是一种轻量级方法，易于集成到现有的ToT框架中。

关键设计：语义相似度的计算是SSDP的关键。论文可能采用了诸如余弦相似度、BERT embeddings等方法来计算思想之间的语义相似度。动态剪枝的阈值是一个重要的参数，需要根据具体的任务进行调整。阈值过高可能导致过度剪枝，影响准确率；阈值过低则可能无法有效地减少冗余计算。此外，状态评估函数的设计也会影响最终的推理效果。

🖼️ 关键图片

fig_0

📊 实验亮点

实验结果表明，SSDP在GSM8K和MATH500等基准测试中，相对于最先进的ToT基线方法，实现了高达2.3倍的加速，同时保持了具有竞争力的准确率（通常在最强基线的5%以内）。更重要的是，SSDP能够将探索的节点数量减少85-90%，这表明SSDP能够有效地减少冗余计算，提高推理效率。

🎯 应用场景

SSDP具有广泛的应用前景，可以应用于各种需要复杂推理的任务中，例如数学问题求解、代码生成、自然语言理解等。通过提高LLM推理的效率和可扩展性，SSDP可以帮助LLM更好地解决实际问题，并降低使用LLM的成本。未来，SSDP可以进一步扩展到其他类型的推理框架中，并与其他优化技术相结合，以实现更高的推理效率。

📄 摘要（原文）

Tree-of-Thought (ToT) reasoning boosts the problem-solving abilities of Large Language Models (LLMs) but is computationally expensive due to semantic redundancy, where distinct branches explore equivalent reasoning paths. We introduce Semantic Similarity-Based Dynamic Pruning (SSDP), a lightweight method that, to the best of our knowledge, is the first framework to integrate online semantic merging into parallelized tree search, enabling the clustering and pruning of redundant steps in real time. Across reasoning benchmarks, including GSM8K and MATH500, SSDP achieves up to a 2.3x speedup over state-of-the-art tree-search baselines while maintaining competitive accuracy (typically within 5% of the strongest baseline) and reducing the number of explored nodes by 85-90%, demonstrating a practical approach to efficient, scalable LLM reasoning. The implementation of SSDP is publicly available at https://github.com/kimjoonghokim/SSDP.