先给结论
这篇论文做了一件填补空白的事:把 LLM 辅助算法搜索 (LAS) 当作一个优化问题,用图论方法可视化并分析了它的适应度景观 (fitness landscape)。核心发现可以概括为三点:
1. 景观是多峰且崎岖的——搜索空间充满局部最优,没有经典的漏斗结构 (funnel structure),图连接稀疏(低连通性),意味着 LLM 生成算法的过程本质上是一个碎片化的探索。
2. 景观结构高度依赖任务和 LLM——组合优化任务中约 80% 的算法集中在最低 20% 适应度区域;而符号回归任务中 98% 的算法远离最优。不同 LLM 产生的景观密度和聚类系数差异巨大:GLM-3-Turbo 密度最高 (0.00223),DeepSeek-Chat 最稀疏 (0.00069)。
3. 现有代码相似度度量不够用——BLEU、Weighted BLEU、AST Match、Data-flow Match 四种度量与性能变化 (performance delta) 的相关性较弱,揭示了一个关键研究空白:需要为 LAS 开发专门的算法相似度度量。
研究动机
LLM 辅助的进化/迭代搜索在自动算法设计领域取得了显著进展 (EoH, ReEvo, LLaMEA 等),但一个基本问题悬而未决:为什么这些方法有效?什么时候会失效?
核心矛盾
传统数学分析难以研究这些方法,因为算法空间过于复杂且 LLM 是黑盒。适应度景观分析是进化计算领域理解搜索行为的经典工具,但在 LLM 辅助搜索场景下几乎空白。
前人工作的不足
van 2025 的 CEG (Code Evolution Graphs) 是第一个尝试,用 AST 分析候选算法的结构属性,但它聚焦代码结构,没有真正讨论适应度景观。本文正是要补上这一块。
数学表示及建模
LAS 的形式化
给定算法设计任务 $T$(如为 TSP 设计启发式算法)和实例集 $I$,目标是算法空间 $A^S$ 中找到使性能指标 $F(a, I)$ 最小的算法 $a^*$:
这里 $f(a, i)$ 是算法 $a$ 在实例 $i$ 上的性能得分,$F(a, I)$ 是所有实例上的平均性能。
进化搜索流程
LAS 通过进化搜索在算法空间中求解。每个算法表示为代码和/或文本描述,经历三个步骤:
适应度景观的形式化定义
沿用 Stadler 2002 的经典定义,适应度景观是一个三元组 $(S, NS, f)$:
- $S$:候选解的集合(这里是 LLM 生成的候选算法集合)
- $NS$:邻域结构——$a_i \in NS(a_j)$ 当且仅当 $a_i$ 由 $a_j$ 生成,即 $a_i = \text{LLM}(\text{Prompt}(a_j))$
- $f: S \to \mathbb{R}$:目标函数(适应度函数)
关键设计决策:由于算法空间没有定义良好的距离度量或邻域结构,论文借鉴 Search Trajectory Networks (STNs) 和 Attractor Networks 的思路,通过父子生成关系来定义邻域——这是一种适应 LLM 黑盒特性的务实选择。
图的定义
- 节点:每个节点是一个算法 $a_i$,节点大小反映该算法在搜索中被生成的次数
- 边:无向边,表示父子算法之间的遗传关系;边权重 = 该转换发生的频率
- 图:$G = (N, E)$,无向图
算法流程 / 方法
实验使用 EoH (Evolution of Heuristics) 框架——一个标准的 LLM 辅助进化搜索框架,其简单的进化结构便于分析适应度景观。
EoH 的四个进化算子
E1 (探索)
大差异交叉算子,产生最宽的性能方差和最低的 Dataflow Match 分数——激进的探索行为。
explorationE2 (探索)
另一种探索型算子,影响力度介于 E1 和变异算子之间。
explorationM1 (开发)
小变异算子,保持较高的 Dataflow Match 分数和较紧的性能分布——语义保持性更强。
exploitationM2 (开发)
另一种开发型变异算子,同样倾向于在父代算法附近做精细搜索。
exploitation种群大小
默认 20,实验中还测试了 2, 5, 10, 50
最大评估次数
2,000 次候选算法评估(LES 的典型设置)
数据采集流程
- 在 LLM4AD 平台上运行 EoH,记录所有生成的算法及其父子关系
- 每次运行构建一个适应度景观图
- 对图进行 2D 和 3D 可视化(节点布局 + 适应度映射)
- 计算图论指标:密度 (Density)、平均度 (Average Degree)、聚类系数 (Clustering Coefficient)
四种代码相似度度量
BLEU
N-gram 匹配,评估词法相似度。最初用于自然语言翻译评估,对编程语言关键字和普通 token 一视同仁,无法捕捉结构或语义等价性。
Weighted BLEU
对编程关键字(如 int, return,
for)赋予更高权重,更好地捕捉关键语法元素的变化,但仍是表层相似度。
AST Match
比较抽象语法树 (AST) 的子树匹配,忽略叶节点(如变量名),关注结构正确性。比 n-gram 方法更能抵抗表面代码变化。
Data-flow Match
分析数据流图中的变量依赖关系,检测值传播的不匹配(如错误的返回变量),捕捉语义层面的差异。计算复杂度最高。
实验设计
六个算法设计任务
| 类别 | 任务 | 缩写 | 目标 |
|---|---|---|---|
| 组合优化 | Online Bin Packing | OBP | 实时分配物品到箱子,最小化箱子数量 |
| Traveling Salesman Problem | TSP | 构造性启发式:选择下一节点,最小化总路径长度 | |
| Capacitated Vehicle Routing Problem | CVRP | 满足容量约束的构造性启发式 | |
| VRP with Time Windows | VRPTW | 同时满足容量和时间窗约束 | |
| Agent 设计 | Mountain Car | Car | 优化 RL agent 动作,最少迭代到达目标 |
| 符号回归 | Bacterial Growth Curve | Bact | 建模细菌生长曲线,最小化 MSE |
六个 LLM
OpenAI
GPT-3.5-Turbo
GPT-4o-Mini
DeepSeek
DeepSeek-V3
DeepSeek-Chat
其他开源
Qwen2-Turbo
GLM-3-Turbo
实验平台:所有实验在开源 LLM4AD Platform 上执行。每次运行记录所有生成的算法及其父子关系,构建适应度景观图。
实验结果
1. 不同任务的适应度景观
观察 1——三大景观特征:
- 多峰 (Multi-modal):多个近似局部最优,搜索需穿越众多潜在解而非收敛到单一全局最优
- 无漏斗结构 (Absence of Funnel):归因于 LLM 生成的固有随机性和缺乏明确指导原则
- 低连通性 (Low Connectivity):图的平均度低、连接稀疏,信息交换效率受限
观察 2——任务间差异显著:启发式设计任务中约 80% 算法落在最低 20% 适应度区域。VRPTW 因时间窗约束的额外复杂性分布略有不同。Car 任务呈双峰分布,中间地带空白。符号回归任务中 98% 算法远离最优——函数或参数的微小变异往往导致性能剧变。
2. 不同 LLM 的景观对比 (TSP 任务)
| LLM | Density | Avg Degree | Clustering Coef. | 搜索策略特征 |
|---|---|---|---|---|
| GLM-3-Turbo | 0.00223 (最高) | 4.04754 | 0.02282 (最高) | 密集连接,局部聚焦 |
| Qwen-Turbo | 0.00213 | 4.76190 (最高) | 0.00769 | 广泛探索邻居解 |
| GPT-4o-Mini | 0.00135 | 3.63397 | 0.00626 | 中等密度,平衡型 |
| DeepSeek-V3 | 0.00114 | 2.91158 | 0.00533 | 稀疏拉长,偏全局 |
| GPT-3.5-Turbo | 0.00110 | 2.79492 | 0.00409 | 中等密度,平衡型 |
| DeepSeek-Chat | 0.00069 (最低) | 2.15053 (最低) | 0.00180 (最低) | 最稀疏,精准全局搜索 |
核心洞察——探索-开发权衡:GLM-3-Turbo 和 Qwen-Turbo 擅长局部精细优化但有陷入局部最优的风险;DeepSeek-Chat 的稀疏连接有利于全局探索但牺牲了局部细化能力;GPT-3.5-Turbo 和 GPT-4o-Mini 走平衡路线。论文指出,组合不同 LLM 的行为可能增强搜索过程——这与 AlphaEvolve 等近期工作使用多 LLM 集成的发现一致。
3. 不同种群大小的景观 (DeepSeek-V3, TSP)
4. 进化轨迹
轨迹可视化揭示了三个关键方面:(1) 分支探索模式——LES 同时探索多个有前景的方向;(2) 向更有效算法的收敛趋势;(3) 看似次优的中间算法可能是通往优秀算法的关键跳板。
5. 算法相似度分析
指标间相关性
BLEU、Weighted BLEU、AST Match、Dataflow Match 之间强正相关。Dataflow Match 和 AST Match 与 TSP 性能变化相关性最高,表明它们与功能正确性更对齐。
分布差异
TSP 的 AST 和 Dataflow Match 得分偏向高值,意味着有效解倾向于保留结构和语义特征。OBP 分散度更大,反映实现多样性更高。
性能可预测性
TSP 上所有相似度度量呈反趋势——高相似度对应低性能变化。OBP 趋势更弱或不一致,尤其 BLEU 和 AST Match,说明相似度度量在某些领域不足以预测性能。
6. 算子级别的分析
算子行为验证:E1 产生最宽方差和最高中位性能变化(最激进),对应最低的 Dataflow Match 分数。M1 和 M2 保持较高的 Dataflow Match 分数和更紧的性能分布(语义保持性更强)。这验证了使用不同算子平衡探索和开发的必要性。
局限性承认:尽管观察到相关性,所有度量的相关系数普遍较小,跨度量和任务变异性显著。同一算法可以有多种代码实现(多对一关系),当前代码相似度度量无法充分捕捉算法等价性。这揭示了一个关键研究空白:需要为 LAS 开发专门的相似度度量。
探索-开发视角的深层解读
论文将 EoH 的四个算子标记为探索型(E1、E2)和开发型(M1、M2),并通过性能方差与 Dataflow Match 分布验证了这一标记。但"探索"与"开发"在 LAS 场景下的含义远比算子标签 复杂。以下从六个维度厘清论文实际报告了什么、哪些是描述性观察、哪些是尚未验证的推断。
1. 观察到的父子图 vs 验证过的语义邻域
- 定义不依赖生成过程的算法距离度量(如执行轨迹相似度、输入-输出行为等价性)
- 对比父子图中的边端点 vs 语义邻域中的邻居——如果重合率高,则父子图是语义邻域的合理近似
- 消融实验:用随机连接替代父子连接,观察景观指标和搜索性能是否显著变化
2. 代码/AST/文本相似度 vs 算法行为相似度
论文评估了四种代码层面的相似度度量,它们捕捉的层次各不相同:
| 度量 | 捕捉的层次 | 论文报告的相关性 |
|---|---|---|
| BLEU | 词法(n-gram 匹配) | 与 Performance Delta 弱相关,OBP 上趋势不一致 |
| Weighted BLEU | 词法 + 关键字权重 | 与 BLEU 强正相关;对性能的预测力同样有限 |
| AST Match | 语法结构(子树匹配,忽略叶节点) | TSP 上与 Performance Delta 相关性最高之一 |
| Data-flow Match | 数据流语义(变量依赖图) | TSP 上与 Performance Delta 相关性最高之一;OBP 上较弱 |
3. 描述性崎岖度/多峰性 vs 因果相切换策略
论文通过 2D/3D 可视化和三个图论指标(密度、平均度、聚类系数)描述了景观的特征:
- 多峰(Multi-modal):多个近似局部最优
- 无漏斗结构(Absence of Funnel):归因于 LLM 生成的随机性和缺乏指导原则
- 低连通性(Low Connectivity):稀疏连接,信息交换效率受限
4. 论文实际报告的 E1/E2 vs M1/M2、LLM 差异、种群大小与新颖性
4.1 算子层面(E1/E2 vs M1/M2)
论文在 arXiv:2504.19636v3 中明确表述:
- E1 和 E2 "focus on exploring new algorithms"——设计意图为探索
- M1 和 M2 "refine existing parent algorithms through exploitation"——设计意图为开发
验证证据来自两张图:
- Performance Delta 分布(Fig 10):E1 方差最大、中位数最高 → 最激进的行为变化
- Dataflow Match 分布(Fig 11):E1 的 Dataflow Match 最低 → 语义保持性最差;M1/M2 较高 → 更保守
4.2 LLM 层面
在 TSP 任务上,六个 LLM 产生了结构显著不同的景观(见 Table 1):
- 密集型(GLM-3-Turbo, Qwen-Turbo):高密度/高聚类系数 → 局部精细优化,可能陷入局部最优
- 稀疏型(DeepSeek-Chat):最低密度/最低度/最低聚类 → 全局探索,牺牲局部细化
- 平衡型(GPT-3.5-Turbo, GPT-4o-Mini):中间指标 → 混合策略
4.3 种群大小
仅报告了 DeepSeek-V3 在 TSP 上的结果(Fig 6):
- 小种群(2, 5)→ 局部开发
- 大种群(10, 50)→ 更广泛探索,揭示景观固有的多峰复杂性
4.4 新颖性(Novelty)
5. 重复运行/随机性证据缺口
论文没有报告独立重复次数、随机种子、运行间方差或置信区间。 因此,仅凭论文文本无法确定每个任务 × LLM × 配置是否做了多次独立运行,也无法判断展示的景观 在 LLM 随机性下是否稳定。这里应当表述为重复运行证据未披露,而不能反向断言所有配置都只运行一次。
这使下列结论缺少跨运行不确定性信息:
- "约 80% 的算法落在最低 20% 适应度区域"——尚无跨运行区间
- "GLM-3-Turbo 密度最高 (0.00223)"——尚不知道不同 seed 下排序是否稳定
- "小种群偏向局部开发"——只展示了 DeepSeek-V3/TSP 这一设置,且未报告重复运行统计
- 进化轨迹中的"关键跳板"——尚未证明能在独立运行中复现
6. 在声称"探索或开发何时有效"之前需要测量的具体指标
论文提供了景观的描述性刻画,但要回答"什么时候应该探索、什么时候应该开发" 这一策略性问题,需要以下论文中尚不存在的测量:
搜索空间覆盖度
独立算法数量 / 总生成数量的比率随时间的变化;探索阶段应呈现高覆盖率, 开发阶段应趋于收敛。论文没有报告这一指标。
解质量与景观指标的关联
图密度/聚类系数与最终解的适应度之间的定量关系。 论文报告了不同 LLM 的不同图指标,但没有将图指标与搜索性能关联。
算子-景观交互效应
在不同景观状态下(早期/中期/后期),E1/E2/M1/M2 各自产生的 性能提升分布。论文只在整体上比较算子,没有按搜索阶段分层分析。
多运行统计显著性
每个配置至少 5–10 次独立运行,报告图指标的均值±标准差, 以及跨运行景观结构的变异系数。当前论文没有报告这些重复运行统计。
新颖性 vs 质量权衡曲线
绘制 Pareto 前沿:算法新颖性(用代码或行为相似度定义)与 性能的关系。论文的相似度分析仅用相关系数,没有构建这一权衡曲线。
因果消融实验
移除某些算子(如只用 E1/E2 或只用 M1/M2)后观察搜索性能变化; 或在不同 LLM 组合下测试集成效果。论文建议多 LLM 集成但未实验验证。
我的评论
优点
- 填补空白:首次系统性地将适应度景观分析引入 LLM 辅助算法搜索领域,研究问题 (Q1-Q3) 的提出清晰且有价值
- 实验覆盖全面:6 任务 × 6 LLM 的交叉评估提供了丰富的实证数据,图论指标的选择合理(密度、度、聚类系数)
- 诚实面对局限:论文坦承四种代码相似度度量的不足,没有过度声称有效,这种科学态度值得肯定
- 可视化做得好:2D/3D 景观图、进化轨迹图、分布图直观且有信息量
不足与值得追问的点
- 图构建的任意性:用父子关系定义邻域是务实但粗糙的选择——同一父代的不同后代之间是否真的是"邻居"?LLM 的随机性可能使两次生成同一父代的后代差异极大,这种"邻域"的定义是否比随机连接更有意义?论文没有对此做对照实验
- 缺乏定量景观指标:论文主要用可视化+三个图论指标,但进化计算领域的景观分析有更丰富的工具(autocorrelation、fitness distance correlation、epistasis measures 等),论文几乎没有使用这些经典定量指标
- 因果方向不清:观察到"不同 LLM 产生不同景观"是描述性的,但没有回答是 LLM 的什么特性(参数规模?训练数据?对齐方式?)导致了密集 vs 稀疏的景观
- 单次运行:每个配置似乎只运行了一次,没有讨论运行间的方差。对于 LLM 这种高随机性的系统,单次运行的景观是否具有代表性?
- 相似度度量的评估不够深:仅用 correlation coefficient 评估,没有做预测实验(如用相似度预测后代是否优于父代的二分类),说服力有限
启发
对 LAS 系统设计的直接启发:
- 选择 LLM 时应考虑任务特性:需要精细搜索的任务用密集型 LLM (如 GLM-3-Turbo),需要广泛探索的任务用稀疏型 (如 DeepSeek-Chat)
- 多 LLM 集成是值得探索的方向——不同 LLM 的互补探索/开发行为天然适合集成
- 种群大小是一个关键超参数:小种群偏向局部开发,大种群实现更广探索
One More Thing
论文在 Limitations 中提到"同一个算法可以有多种代码实现"——这其实指向了一个更深层的问题:算法空间本身是什么? 当前 LAS 把算法等同于代码文本,但代码空间和算法功能空间之间存在巨大的多对一映射。如果我们能在功能空间而非代码空间中定义景观和邻域,搜索效率可能大幅提升。这需要一种"算法语义嵌入"——也许可以用执行轨迹、算法复杂度特征、甚至学习到的表示来构建。这个方向可能是 LAS 景观分析的下一个突破口。
Reference / Evidence
- arXiv: 2504.19636 — Fitness Landscape of Large Language Model-Assisted Automated Algorithm Search
- arXiv PDF: pdf/2504.19636
- arXiv HTML: html/2504.19636v3
- EoH (Evolution of Heuristics): arXiv:2404.17820 — Liu et al., 2024
- LLM4AD Platform: github.com/Optima-CityU-L4AD/L4AD
- CEGs (前人工作): van 2025 — Code Evolution Graphs, AST-based landscape analysis