Chain-in-Tree: Back to Sequential Reasoning in LLM Tree Search

📄 arXiv: 2509.25835v3 📥 PDF

作者: Xinzhe Li

分类: cs.AI

发布日期: 2025-09-30 (更新: 2025-10-18)

备注: Under Review; Add codebase

🔗 代码/项目: GITHUB

💡 一句话要点

Chain-in-Tree：通过动态分支策略提升LLM树搜索效率

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

关键词: LLM树搜索 长程推理 分支必要性评估 动态分支策略 计算效率 Chain-in-Tree 自洽性 模型优化

📋 核心要点

  1. 现有LLM树搜索方法（LITS）虽然性能强大，但计算效率低下，推理速度远低于迭代方法。
  2. Chain-in-Tree (CiT) 框架通过引入分支必要性评估，动态决定何时进行分支，减少不必要的分支扩展。
  3. 实验表明，CiT显著降低了token生成、模型调用和运行时间，同时保持了甚至提升了在数学问题上的准确率。

📝 摘要（中文）

本文提出Chain-in-Tree (CiT)，一个即插即用的框架，用于在LLM树搜索中动态决定何时进行分支，而非每一步都扩展。CiT引入了轻量级的分支必要性(BN)评估方法：BN-DP (直接提示)，使用辅助LLM判断分支需求；BN-SC (自洽性)，通过聚类候选动作来评估一致性。集成到Tree of Thoughts、ReST-MCTS和RAP后，BN-DP在GSM8K和Math500上实现了75-85%的token生成、模型调用和运行时间减少，且通常精度损失可忽略不计或没有损失。BN-SC通常也能显著节省资源（高达80%），但在14个设置中的1-4个中表现出不稳定性，这是由一小部分产生极长推理步骤的示例引起的。理论证明BN-DP永远不会增加策略调用次数。论文发布了模块化的LITS实现和一个轻量级的CiT函数，适用于所有LITS变体。代码已开源。

🔬 方法详解

问题定义：现有基于LLM的树搜索方法，如Tree of Thoughts等，在每一步都进行分支扩展，导致计算量巨大，效率低下。尤其是在长程推理任务中，这种盲目扩展会浪费大量计算资源，成为实际应用的瓶颈。

核心思路：CiT的核心思想是并非每一步都需要进行分支，而是应该根据当前状态和潜在动作的价值，动态地决定是否需要进行分支。通过引入分支必要性评估，避免不必要的分支扩展，从而提高整体的推理效率。

技术框架：CiT是一个即插即用的框架，可以集成到现有的LITS方法中。其主要流程包括：1) 在每个推理步骤，首先进行分支必要性(BN)评估；2) 如果BN评估认为需要分支，则进行正常的树搜索扩展；3) 如果BN评估认为不需要分支，则继续沿着当前路径进行推理。CiT主要包含两个BN评估方法：BN-DP和BN-SC。

关键创新：CiT的关键创新在于引入了分支必要性评估的概念，并提出了两种具体的评估方法：BN-DP和BN-SC。与现有方法在每一步都进行分支扩展不同，CiT能够根据当前状态动态地决定是否需要分支，从而显著减少计算量。BN-DP利用辅助LLM直接判断分支的必要性，而BN-SC则通过评估候选动作的一致性来判断。

关键设计：BN-DP通过prompting辅助LLM来判断分支的必要性，prompt的设计至关重要，需要清晰地表达分支的含义和评估标准。BN-SC则通过聚类候选动作，并计算聚类结果的自洽性得分来判断分支的必要性。聚类算法的选择和自洽性得分的计算方法是关键的设计细节。论文中理论证明了BN-DP不会增加策略调用次数。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，CiT在GSM8K和Math500数据集上，能够显著降低token生成、模型调用和运行时间，降幅达到75-85%，同时通常不会降低准确率，甚至在某些情况下还能提升准确率。BN-SC虽然通常也能显著节省资源，但在少数情况下表现出不稳定性，需要进一步改进。

🎯 应用场景

CiT框架可以广泛应用于需要长程推理的LLM应用中，例如数学问题求解、代码生成、游戏策略规划等。通过提高推理效率，CiT能够降低LLM应用的部署成本，并使其能够处理更复杂的任务。该研究对于推动LLM在实际场景中的应用具有重要意义。

📄 摘要（原文）

Test-time scaling improves large language models (LLMs) on long-horizon reasoning tasks by allocating more compute at inference. LLM Inference via Tree Search (LITS) methods achieve strong performance but are highly inefficient, often running an order of magnitude slower than iterative approaches. We propose Chain-in-Tree (CiT), a plug-in framework that decides when to branch during search rather than expanding at every step. CiT introduces lightweight Branching Necessity (BN) evaluations: BN-DP (Direct Prompting), where an auxiliary LLM judges branching needs, and BN-SC (Self-Consistency), which clusters candidate actions to assess agreement. Integrated into Tree of Thoughts, ReST-MCTS, and RAP, BN-DP achieves 75-85% reductions in token generation, model calls, and runtime on GSM8K and Math500, with often negligible or no accuracy loss. BN-SC typically yields substantial savings (up to 80%) generally but shows instability in 1-4 out of 14 settings, caused by a small subset of examples that produce extremely long reasoning steps. We theoretically prove that BN-DP never increases policy invocations and release both modular LITS implementations and a lightweight CiT function applicable across all LITS variants. The full codebase is publicly available at https://github.com/xinzhel/chain_in_tree.