[Paper] 对比概念树搜索用于 LLM 辅助的算法发现

Source: arXiv - 2602.03132v1

Overview

本文介绍了 Contrastive Concept‑Tree Search (CCTS)，这是一种在使用大型语言模型（LLMs）发现算法时进行引导的新方法。通过从 LLM 生成的程序中提取“概念”层次结构，并学习哪些概念倾向于产生高性能的解决方案，CCTS 在显著加快有效算法搜索的同时，保持了过程的可解释性。

关键贡献

• Concept‑tree extraction: 将生成的代码解析为可重用算法概念的层次树（例如 “graph traversal”、 “union‑find”、 “binary search”）。
• Contrastive learning of concept utility: 一个轻量模型通过比较概念在高性能与低性能程序中的出现频率来为概念打分，生成似然比的 “contrastive score”。
• Guided parent selection: 在迭代的 generate‑evaluate 循环中，CCTS 根据 contrastive scores 对候选父程序重新加权，使 LLM 偏向有前景的概念组合。
• Empirical gains on combinatorial benchmarks: 在一套 Erdős‑type 问题（图着色、Ramsey‑type 构造等）中，CCTS 将达到目标性能所需的 LLM 查询次数比仅使用适应度的基线降低 30‑50 % 。
• Interpretability: 学到的概念树展示了每个任务中哪些算法构件是有用的或有害的，提供可读的人类洞察。
• Synthetic validation: 在已知概念空间的受控环境中复现相同的搜索动态，证实观察到的改进来源于学习避免 “bad” 概念，而非 LLM 的奇特行为。

方法论

1. 生成候选程序 – 一个大型语言模型（例如 GPT‑4）提出旨在解决组合任务的代码片段。

2. 解析为概念 – 静态分析过程提取高级算法模式（循环、数据结构、递归模式），并将它们组织成一棵树，每个节点是一个概念，边表示组合关系。

3. 对比评分 – 系统维护两个概念频率分布：一个来自表现前 k 的程序，另一个来自表现后 k 的程序。概念 (c) 的对比得分为

   [ s(c)=\log\frac{P_{\text{high}}(c)}{P_{\text{low}}(c)}. ]

   正得分表示“好”概念；负得分标记“坏”概念。

4. 父代重新加权 – 当 LLM 请求一个父程序进行变异时，CCTS 将每个父程序的原生概率乘以

   [ \exp!\left(\sum_{c\in\text{parent}} s(c)\right). ]

   这会将搜索倾向于包含高得分概念的父代。

5. 迭代 – LLM 对选中的父程序进行变异，评估器对新程序打分，概念模型随之更新。循环持续进行，直至达到性能阈值或查询预算耗尽。

结果与发现

• 概念规避驱动提升: 仅提升高得分概念（不惩罚低得分概念）的消融实验仅带来适度加速；最大收益来自对“坏”概念的降权。
• 可解释性: 最终的概念树显示，例如“贪婪边选择”对 Ramsey 问题有害，而“带路径压缩的并查集”在图任务中始终有益。
• 合成测试: 在一个已知真实概念效用的玩具领域，CCTS 在几次迭代内恢复了正确的分数，呈现出与真实 LLM 行为相似的表现。

实际意义

• 更快的原型生成: 使用 LLM 自动生成算法代码的团队（例如用于竞赛编程助手、自动定理证明器或领域特定优化器）可以将昂贵的 LLM 调用次数削减近一半。
• 降低计算成本: 由于每次 LLM 查询在云 API 中可能花费数美元，CCTS 直接转化为嵌入代码生成循环的 SaaS 产品的运营开支降低。
• 人机交互调试: 概念树提供了模型尝试过程的简洁“调试视图”，让工程师可以手动修剪或注入概念（例如，强制使用平衡二叉搜索树）。
• 可迁移到其他领域: 对比概念模型对底层 LLM 并不依赖；它可以用于符号回归、电路合成，甚至用于层次概念存在的非代码任务的提示工程。

限制与未来工作

• 概念提取依赖于静态分析： 复杂的 Python 惯用法或高度混淆的代码可能被错误解析，限制概念树的忠实度。
• 基准测试聚焦于组合数学： 真实的软件工程问题（例如 API 集成、UI 生成）可能涉及更丰富、结构更松散的概念，需要更复杂的提取流水线。
• 对比得分的可扩展性： 随着概念词汇量的增长，估计可靠的低表现频率可能变得嘈杂；可能需要平滑或贝叶斯先验。
• 未来方向： 将 CCTS 扩展到多目标设置（例如平衡运行时和内存），整合强化学习式的策略更新，并探索从开源仓库自动扩展概念库。

作者

• Timothee Leleu
• Sudeera Gunathilaka
• Federico Ghimenti
• Surya Ganguli

论文信息

• arXiv ID: 2602.03132v1
• 分类: cs.LG, cs.AI, cs.NE
• 发表时间: 2026年2月3日
• PDF: 下载 PDF