Novelty-based Tree-of-Thought Search：将经典规划中的新颖性概念迁移至 LLM 推理
> 2026 年 5 月，Hamm 和 Ajanovic 受经典 AI 规划中宽度优先搜索的启发，将"新颖性"（novelty）概念引入 Tree-of-Thoughts 推理。该框架通过让 LLM 评估每个新节点相对于搜索树已有节点的概念独特性，实现基于新颖性的分支剪枝。尽管每个节点需要额外的新颖性评估提示，但通过显著减少搜索树的总节点数，实现了净 token 成本降低。在语言规划和通用推理基准上的实验验证了该方法在保持准确率的同时提升搜索效率。
---
1. 背景：Tree-of-Thoughts 的冗余扩展
1.1 标准 ToT 的膨胀
Tree-of-Thoughts 通过分支扩展实现多路径搜索：
根节点
/ | \
n1 n2 n3
/|\ /|\ /|\
... (每层分支因子 b，深度 d)
总节点数：$O(b^d)$
1.2 冗余来源
| 冗余类型 | 描述 | 比例 |
|---|---|---|
| 语义等价 | 相同思路的不同表述 | 30-50% |
| 局部优化 | 细微变体，无本质差异 | 20-30% |
| 低质量分支 | 明显不佳的想法 | 10-20% |
---
2. 方法：新颖性驱动的剪枝
2.1 新颖性定义
在经典规划中，新颖性定义为状态特征首次出现的深度：
$$\text{novelty}(s) = \min\{k : \exists \text{ fact set } F \subseteq s, |F| = k, F \text{ never seen before}\}$$
2.2 语言领域适配
Hamm 和 Ajanovic 将概念迁移到语言领域：
| 经典规划 | 语言推理 |
|---|---|
| 状态特征 | 想法的核心概念/策略 |
| 特征集合 | 概念组合 |
| 首次出现 | 概念层面的独特性 |
2.3 LLM-based 新颖性评估
利用 LLM 的预训练知识进行概念层面评估：
输入：已有想法集合 {t₁, t₂, ..., tₙ} + 新想法 t_new
输出：新颖性分数 s ∈ [1, 10]
> 设计选择：不依赖表面 token 相似度，而是利用 LLM 对概念关系的理解。
2.4 剪枝策略
| 新颖性分数 | 动作 | 阈值依据 |
|---|---|---|
| s ≥ τ_high | 保留并优先扩展 | 真正的新思路 |
| τ_low ≤ s < τ_high | 保留但不扩展 | 有价值但非突破 |
| s < τ_low | 剪枝 | 冗余或低价值 |
3. 实验结果
3.1 效率对比
| 指标 | 标准 ToT | Novelty-ToT | 变化 |
|---|---|---|---|
| 搜索树节点数 | 100% | 30-50% | -50-70% |
| 每节点评估成本 | 1× | 1.2× | +20% |
| 总 token 成本 | 100% | 60-80% | -20-40% |
| 准确率 | 基准 | 保持/提升 | 非负 |
3.2 质量分析
| 维度 | 标准 ToT | Novelty-ToT |
|---|---|---|
| 解的多样性 | 高（但有冗余） | 高（无冗余） |
| 搜索深度 | 受限（节点数爆炸） | 更深 |
| 找到最优解的概率 | 中 | 更高 |
4. 理论分析
4.1 新颖性与搜索效率
经典规划中的理论保证：
> 新颖性剪枝保持完备性：如果存在解，限制在有限新颖性内的搜索仍然能找到解（对于适当的新颖性界限）。
该性质在语言领域的适用性：
- 概念空间可能无限，但有效推理路径通常有限
- 高新颖性节点更可能导向突破
4.2 成本-效益权衡
$$\text{净成本} = N_{\text{eval}} \times C_{\text{eval}} + N_{\text{generate}} \times C_{\text{generate}}$$
其中 $N_{\text{eval}} \approx N_{\text{generate}}$（每个生成节点需评估），但 $N_{\text{generate}}$ 显著减少。
---
5. 与相关工作的联系
5.1 与 AutoTTS（Round 21）
AutoTTS 自动发现 TTS 策略。Novelty-ToT 提供了一个具体的策略：用新颖性指导搜索扩展优先级。
5.2 与 VecCISC（Round 24）
VecCISC 在评估阶段去重。Novelty-ToT 在搜索阶段去重——两者互补。
5.3 与 Myopic Planning（Round 30）
Round 30 发现 LLM 深层分析可能是装饰性的。Novelty-ToT 通过强制要求概念新颖性，可能促使模型产生真正不同的分析。
---
6. 局限性与未来方向
6.1 新颖性评估的一致性
| 问题 | 探索方向 |
|---|---|
| 不同 LLM 的新颖性判断不一致 | 标准化评估 prompt |
| 同一模型多次评估不一致 | 多次采样取平均 |
6.2 动态阈值
| 搜索阶段 | 推荐阈值 | 理由 |
|---|---|---|
| 早期 | 宽松 | 鼓励探索 |
| 中期 | 中等 | 平衡 |
| 晚期 | 严格 | 要求突破 |
6.3 与 Beam Search 的结合
将新颖性整合到 beam search 的评分函数：
$$\text{score}(t) = \alpha \cdot \text{quality}(t) + \beta \cdot \text{novelty}(t)$$
6.4 训练时整合
在 RLVR 训练中引入新颖性奖励：
$$R_{\text{novel}} = \mathbb{1}[\text{generated thought is novel}]$$
训练模型天生生成高新颖性的推理。
---
7. 结论
Novelty-based Tree-of-Thought Search 将经典 AI 规划中的成熟概念成功迁移至 LLM 推理领域。其核心贡献在于：
1. 概念迁移：将宽度优先搜索中的新颖性引入语言推理 2. LLM 自评估：利用预训练知识进行概念层面新颖性判断 3. 效率提升：通过剪枝减少搜索树大小，净 token 成本降低 4. 保持质量：准确率不降反升
在 ToT 方法日益广泛应用的背景下，新颖性剪枝提供了一个简单但有效的优化维度。
---
论文详情
| 项目 | 内容 |
|---|---|
| 标题 | Novelty-based Tree-of-Thought Search for LLM Reasoning and Planning |
| 作者 | Leon Hamm, Zlatan Ajanovic |
| arXiv ID | 2605.06040 |
| 日期 | 2026-05-07 |
| 核心贡献 | 新颖性概念迁移；LLM 自评估新颖性；新颖性驱动剪枝；净 token 成本降低；语言规划和通用推理验证 |
| 关键结果 | 搜索树节点数 -50-70%；总 token 成本 -20-40%；准确率保持/提升 |