[Paper] 即使有 AI，双射发现仍然困难：OpenEvolve 在新颖双射构建中的机遇与挑战

Source: arXiv - 2511.20987v1

概览

本文研究了 OpenEvolve——一种协调多个大型语言模型（LLM）的进化程序合成系统——在经典组合挑战上的表现：构造显式双射。通过解决三个关于 Dyck 路径的双射问题（其中两个已有文献解答，另一个仍未解决），作者评估了 AI 是否能够自主发现新颖、达到研究水平的组合构造。

主要贡献

• 首次系统性研究 LLM 驱动的进化用于双射发现，将 AI 辅助数学的范围扩展到不等式之外的构造性结果。
• 实现 OpenEvolve 流水线，将 LLM 生成的 Python/Mathematica 代码转化为可执行候选，并通过变异、交叉和适应度评估迭代改进。
• 在三个 Dyck 路径双射任务上的实证评估，表明系统能够复现已知双射，但在发明新双射方面仍有困难。
• 为希望将进化合成应用于其他构造性数学问题的研究者提供实用指南和“经验教训”。
• 开源制品（提示模板、适应度函数和基准脚本）已发布，以便复现。

方法论

1. 问题形式化 – 将每个双射任务表达为 构造函数：给定一个组合对象（例如 Dyck 路径），输出另一个等势对象（例如不同的格子路径）。
2. LLM 生成 – 一组 LLM（GPT‑4、Claude、Llama‑2）被提示用高级语言（Python，使用 networkx/itertools）编写候选构造代码。
3. 进化循环
   • 适应度：若候选在大小为 N 的抽样测试集上是 双射（单射 + 满射），则通过（例如 N = 10 000）。
   • 选择：保留前 k 名候选。
   • 变异：对存活的代码进行变异（如重命名变量、微调循环）或与另一存活代码交叉产生后代。
4. 验证 – 每代结束后，在更大的验证集上运行存活程序，以防止对训练样本的过拟合。
5. 人工参与 – 研究者检查表现优异的脚本，剔除无意义的变异，并偶尔注入领域特定提示（例如“保持峰的数量”）。

该流水线故意保持轻量，以便开发者可以接入任意 LLM API 和任何具有明确定义双射谓词的组合领域。

结果与发现

解释

• 当底层组合直觉相对直接时，进化框架能够可靠地重新发现已有双射。
• 对于真正的开放问题，系统在局部最优但不完整的构造上停滞，表明当前 LLM 推理和变异算子缺乏实现新证明所需的更深结构直觉。
• 人工检查仍然必不可少，以过滤出语法正确但数学上毫无意义的代码（例如始终返回常量对象的函数）。

实际意义

• 快速原型化组合工具 – 开发者可使用 OpenEvolve 风格的流水线自动生成处理 Catalan 对象的双射样板代码，节省数周手工编码时间。
• 教育助理 – AI 导师可以展示给定组合等价的多种有效构造，帮助学生探索不同的证明思路。
• 领域特定合成 – 同样的进化‑LLM 循环可用于生成解析器、数据结构转换或编译器优化等场景，其中需要在输入输出表示之间建立双射。
• 研究辅助 – 虽然系统不会取代数学家，但它可以充当“搜索引擎”，为人类专家提供有前景的候选构造，以加速枚举组合、密码学（群之间的双射）和编码理论等领域的发现。

局限性与未来工作

• 适应度近似 – 依赖抽样测试集可能遗漏细微的双射性违例；对大规模组合族进行穷尽验证不可行。
• LLM 知识缺口 – 现有模型缺乏对不变量的深层形式推理，导致在开放问题上陷入死胡同。
• 变异设计 – 简单的语法变异常产生无意义代码；更丰富、保持语义的算子（如“交换递归调用”）可能提升搜索效率。
• 可扩展性 – 随着搜索空间扩大，进化循环成本升高；引入基于强化学习的策略更新可能减少所需代数。

未来研究方向包括与定理证明器更紧密的集成，实现即时正确性检查；探索多目标适应度（如简洁性 vs. 正确性）；以及将框架扩展到图同构或代数结构嵌入等其他构造性领域。

作者

• Davis Brown
• Jesse He
• Helen Jenne
• Henry Kvinge
• Max Vargas

论文信息

• arXiv ID: 2511.20987v1