🤖 AI

Contrastive Concept-Tree Search for LLM-Assisted Algorithm Discovery

本文介绍了对比概念树搜索（Contrastive Concept-Tree Search, CCTS），这是一种通过学习层次化概念模型来通过对比重加权引导父节点选择，从而通过识别并避免无效的概念组合来提高搜索效率和可解释性，进而增强大语言模型辅助算法发现的方法。

原作者： Timothee Leleu, Sudeera Gunathilaka, Federico Ghimenti, Surya Ganguli

发布于 2026-02-04

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Timothee Leleu, Sudeera Gunathilaka, Federico Ghimenti, Surya Ganguli

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

想象一下，你正在试图教一位非常有天赋但略显困惑的学徒去解决一个复杂的谜题，比如将圆圈放入正方形中，或者排列点以避免产生微小的三角形。你拥有一个强大的工具：一个大型语言模型（LLM），它就像一个超级聪明、博学多才的机器人，能够编写计算机代码。

然而，这里有一个问题：当你要求这个机器人尝试一种新的解决方案时，它往往只是在随机猜测，或者只是对之前的尝试进行微调，而并不真正理解为什么一个方案比另一个更好。这就像是在询问某人如何改进食谱，却是在不知道哪些香料能让菜肴更好吃的情况下，随机更换食材。

这篇论文介绍了一种名为**对比概念树搜索（Contrastive Concept-Tree Search, CCTS）**的新方法来解决这个问题。以下是它的工作原理，通过简单的想法进行拆解：

1. 问题所在：在黑暗中搜索

目前的系统大多运作起来像是一场“适者生存的竞赛”：它们生成一堆代码，看哪一个得分最高，然后要求机器人让那个特定的获胜者变得更好。

缺陷： 这就像是通过只观察你当前所在的顶峰来攀登一座山。你可能会被困在一个小山丘上，误以为那是顶峰；或者因为过于关注你站立的地方而错过了更好的路径。机器人并不理解代码背后的“概念”；它只看到了最终的分数。

2. 解决方案：“概念树”

作者意识到，我们不应该只看最终分数，而应该观察代码中的“成分”（概念）。

隐喻： 想象代码不仅仅是一块文本，而是一个思想的家族树。
- 在顶端，你有宽泛的概念，如“优化”。
- 向下分支，你会得到具体的主意，如“梯度下降”。
- 再往下，则是微小的细节，如“自适应学习率”。
CCTS 方法强制要求机器人为它写的每一段代码都贴上这些“概念标签”。

3. 魔法技巧：“好”与“坏”的列表

这是新方法的核心。系统并没有仅仅挑选出那段最好的代码，而是将所有的尝试分成了两堆：

“好”的一堆： 得分高的尝试。
“坏”的一堆： 得分低的尝试。

然后，它玩起了一个**“找不同”**的游戏。

它会问：“哪些概念频繁出现在‘好’的一堆中，但在‘坏’的一堆中却缺失了？”（这些是有用的概念）。
它还会问：“哪些概念频繁出现在‘坏’的一堆中，但在‘好’的一堆中却缺失了？”（这些是陷阱概念）。

4. 结果：学会避坑

研究发现了一些令人惊讶的事实：系统性能的最大提升不仅来自于学习该“做什么”，还来自于学习什么不该做。

类比： 想象你正在尝试烘焙一个完美的蛋糕。旧的方法是不断烘焙那些味道“还可以”的蛋糕，并寄希望于它们能变得更好。而新的方法（CCTS）则像是一位厨师，他意识到：“每次我放太多盐时，蛋糕就会失败。每次我忘了放泡打粉时，蛋糕也会失败。”
通过主动避开“陷阱概念”（比如盐），搜索变得更加高效。它不再把时间浪费在死胡同里。

5. 他们是如何测试的

研究人员在几个困难的数学谜题上测试了该方法（例如“圆圈填充”问题，即尝试在盒子里放入尽可能多的圆圈）。

他们将这种新方法与旧的“仅基于适应度”的方法进行了对比。
结果： 新方法能更快地找到更好的解决方案。
“合成”测试： 为了证明这不仅仅是由于他们使用的特定机器人的特性，他们构建了一个虚构的、简化的版本问题（一个“玩具世界”），在这个世界里他们知道完美答案。即使在这个虚构的世界里，新方法也运行得非常完美，这证明了即便没有复杂的机器人，其逻辑依然成立。

总结

简而言之，这篇论文教会了 AI 如何停止盲目猜测，开始学习游戏的规则。通过将思想组织成一棵树，并对比什么是有效的以及什么是失效的，系统学会了避开坏主意并结合好主意。它将盲目的搜索变成了一场有引导的巡游，使新算法的发现变得更快、更聪明。

核心要点： 最大的收获来自于系统学会了规避错误的逻辑，而不只是寻找正确的逻辑。

技术摘要：用于 LLM 辅助算法发现的对比概念树搜索 (CCTS)

问题陈述

大语言模型（LLM）辅助的算法发现是一个迭代的、黑盒优化的过程，其中 LLM 提出候选程序，外部评估器提供任务反馈。虽然近期的范式（如 FunSearch、AlphaEvolve）已成功重新发现或改进了组合问题（如 Erdős 型问题）的解，但它们在很大程度上依赖于由适应度驱动的进化更新。在这些现有系统中，父代选择是由程序的原始性能（适应度）决定的，且搜索过程是沿着按性能排序的程序谱系进行的步进。

这种方法的一个关键局限在于程序空间仍然缺乏结构化。即使受到 LLM 的约束，生成的算法通常也缺乏清晰的概念局部性、平滑变化或可被搜索算法利用的组合结构。因此，引导主要源于原始的适应度信号和 LLM 的隐式先验，而非对哪些算法语义组件真正有用的显式学习理解。本文旨在解决一个开放性问题：如何最大限度地利用 LLM 对程序空间的内部表示来提高搜索效率和可解释性。

方法论：对比概念树搜索 (CCTS)

作者引入了对比概念树搜索 (CCTS) 框架，该框架将搜索引导从原始适应度转向学习到的、层次化的语义概念空间。其核心假设是：算法可以用一个组织为层次结构的底层语义概念空间来描述，其中节点代表概念，边编码了细化或特化关系。

1. 概念表示与树构建

特征提取： 每个候选程序 $x$ 被映射到一个语义特征表示 $b = \Phi(x)$ ，该表示通过提示 LLM 生成相关的概念列表来提取。
层次结构： 这些概念被组织成一个根概念树。概念向量 $b$ 是一个指示向量，其激活状态满足祖先封闭性（激活子概念意味着激活其所有祖先）。该树是动态的，随着搜索过程中新概念的发现而增长。

2. 概念效用的对比学习

CCTS 不仅仅根据适应度分数选择父代，而是通过对比方法学习哪些概念在经验上与高性能相关：

划分： 程序存档根据性能阈值被划分为“好” ( $y_i \ge \tau_t$ ) 和“坏” ( $y_i < \tau_t$ ) 子集。
模型拟合： 分别对“好”子集和“坏”子集的特征分布进行拟合，得到 $\hat{p}_{\eta^+}(b)$ 和 $\hat{p}_{\eta^-}(b)$ 。作者采用了类似于树结构帕森估计器 (TPE) 的方法，使用因子化的层次伯努利模型。该模型假设给定其父节点时特征是条件独立的。
似然比评分： 为每个程序计算一个似然比得分（对数概念效用）：
$\log w(b) = \log \hat{p}_{\eta^+}(b) - \log \hat{p}_{\eta^-}(b)$
该得分量化了特定概念集在区分高绩效解与低绩效解方面的强度。

3. 父代选择与搜索动力学

偏置采样： 从存档中选择父代时，其概率与似然比得分成正比。这使得搜索向包含经验上与改进相关的概念组合的程序倾斜。
探索机制： 为了防止过早收敛并鼓励发现新概念，CCTS 结合了一个轻量级的探索机制。这包括：
- Beta 先验： 通过平滑计数确保新发现的概念永远不会出现零概率。
- 新颖性偏差： 降低被频繁尝试的概念的权重，从而倾向于探索未被充分探索的区域。
- 混合策略： 利用基于学习到的对比模型（利用）和基于新颖性（探索）的混合策略，来指导注入到 LLM 提示词中以生成子代的概念。

核心贡献

显式语义结构： 本文提出通过学习层次化概念树来使算法空间的潜在结构显式化，超越了标准进化算法中使用的无结构程序空间。
对比引导： 引入了一个对比统计框架，该框架旨在识别哪些概念需要优先考虑，以及更关键的是，识别哪些概念应该避免，而不仅仅是追踪哪些程序表现最好。
可解释性： 该方法产生了具有任务特定性的可解释概念树，揭示了搜索过程中探索的语义结构，为所发现的算法策略提供了见解。
合成验证： 作者构建了一个带有“教师”概念树和地面真值效用的受控合成环境。这使得他们能够验证 CCTS 是否能恢复底层的语义结构，并确认观察到的搜索动力学是由概念效用的学习驱动，而非特定的 LLM 人造物驱动。

实验结果

作者在包括圆堆积 (circle packing)、算术 Kakeya 猜想 (Arithmetic Kakeya conjecture)、Heilbronn 三角形问题 (Heilbronn's triangle problem) 和正方形入正方形问题 (squares-in-square problem) 在内的 Erdős 型组合问题基准测试上评估了 CCTS。

性能提升： 在多个任务中，CCTS 相比于基准策略（均匀采样、贪婪选择和 $k$ -精英选择）始终实现了更高的得分和更快的改进速度。
改进机制： 分析表明，性能增益很大程度上是由学习哪些概念应当避免驱动的。成功的运行识别出了与不成功的运行相似的高效用概念集，但展现出了显著更好的抑制低效用（有害）概念的能力。这表明 CCTS 通过减少由 LLM 初始先验中的误导性相关性引起的无效探索，从而稳定了搜索。
合成验证： 在合成环境中，学习到的概念效用与地面真值教师效用显示出强相关性 ( $r=0.94$ )，证实了该方法能有效恢复有意义的语义表示。
结构依赖性： 研究发现，探索与利用之间的最佳平衡取决于底层概念树的结构（例如分支比），这表明搜索策略应适应特定问题的拓扑结构。

意义与主张

本文声称 CCTS 解决了当前 LLM 辅助算法发现中的一个根本性失配：高分算法并不一定会产生强大的后代，因为在弱结构空间中，适应度是衡量可进化性的糟糕代理指标。通过将选择从原始适应度转向关于改进的语义证据，CCTS 使搜索能够在距离、重组和搜索方向都有意义的概念空间中运行。

作者将这项工作定位为迈向更可靠、更具扩展性的算法发现的方法论进步。他们强调，虽然目前的结果展示了在特定基准测试上相对于基准方法的相对改进，但其主要贡献在于证明了显式的、人类兼容的语义概念结构可以使自动化发现变得更加透明、可控且高效。这项工作表明，未来的系统应侧于学习并利用这些潜在的语义层次结构，而非仅仅依赖于黑盒适应度信号。