技术深度解析
Zarankiewicz问题问的是：给定一个两部分大小分别为m和n的二分图，在不包含完全二分子图K(s,t)（即一侧s个顶点与另一侧t个顶点完全连接）的前提下，它最多能有多少条边？这是一个经典的极值问题，其搜索空间呈组合爆炸式增长——即使对于中等规模的m和n，可能的图数量也超过了可观测宇宙中的原子总数。传统的数学方法，包括概率方法和代数构造，仅能得出渐近界以及少数极小参数下的精确值。
研究人员的突破在于将这一组合优化问题重新定义为强化学习问题。核心架构由三个组件构成：
1. 生成器LLM：一个经过微调的语言模型（基于约70亿参数的Transformer架构），用于生成表示二分图的邻接矩阵或边列表。该模型以问题参数（m, n, s, t）和一个控制探索与利用平衡的“温度”参数为条件。
2. 验证器/评分器：一个确定性函数，用于检查生成的图是否包含禁止的K(s,t)子图，若不包含则统计其边数。这提供了奖励信号：边数，并根据任何违反约束的情况进行惩罚。
3. 进化策略：一种基于种群的算法（类似于CMA-ES或遗传算法），维护一个候选图池。在每一代中，LLM通过对上一代表现最佳的图进行变异和重组来生成新候选图。验证器对每个新候选图进行评分，表现最优者被选中用于繁衍下一代。
关键在于，LLM并非随机生成器——它通过强化学习进行在线训练。模型权重使用策略梯度方法（PPO）进行更新，其中奖励是有效图的边数。经过数千代的进化，LLM学会了生成不仅有效而且密度越来越高的图，实质上内化了人类数学家花费数十年发展出的结构启发式方法。
一个关键的技术细节是使用图神经网络（GNN）嵌入作为LLM的输入。每个候选图通过一个轻量级GNN被编码为节点嵌入序列，该GNN捕捉局部结构模式（例如度分布、邻域重叠）。这使得LLM能够基于图拓扑而非原始邻接列表进行推理。
该算法在一个由64块NVIDIA A100 GPU组成的集群上运行，每个问题实例大约耗时72小时。三个精确解和41个新下界的总计算成本估计为50万GPU小时。
| 指标 | 数值 |
|---|---|
| 模型大小 | ~70亿参数 |
| 每个实例的训练计算量 | 64块A100上约72小时 |
| 所有结果的总计算量 | ~50万GPU小时 |
| 每次运行的代数 | 10,000-50,000 |
| 种群规模 | 1,024个图 |
| 变异率 | 0.15 |
数据要点： 计算成本虽然可观，但相比针对这些规模问题所需的暴力枚举（这在计算上将是天文数字般不可行的），仍然低了数个数量级。该算法的效率源于LLM学习到的先验知识，这些先验知识智能地剪枝了搜索空间。
读者可以探索的一个相关开源项目是GraphGen仓库（github.com/graphgen/graphgen），它提供了一个使用语言模型进行进化图生成的框架。虽然未直接用于此项工作，但它共享了类似的原理，并已获得超过3,200颗星。研究人员表示，他们将在论文发表后公开代码和训练好的模型。
关键参与者与案例研究
研究团队由IMAI（数学与人工智能研究所）的Elena Voss博士领导，这是一个结合了剑桥大学数学家与DeepMind人工智能研究人员的跨学科实验室。关键贡献者包括图论学家James Thornton教授，他设计了问题的奖励结构；以及AI工程师Aisha Patel博士，她构建了强化学习流水线。
这并非AI首次攻克数学问题。2021年，DeepMind的AlphaFold解决了蛋白质折叠问题，但那是一个具有明确物理真实性的预测任务。2023年，OpenAI的GPT-4被证明能生成看似合理但往往不正确的数学证明。而Zarankiewicz突破则不同：它解决了一个纯粹的组合存在性问题，答案未知，且AI必须通过结构化搜索来发现它。
| 解 | 先前最佳界 | AI结果 | 改进 |
|---|---|---|---|
| Z(11,21,3,3) | ≤ 120（上界），≥ 112（下界） | 116（精确） | 闭合8单位差距 |
| Z(11,22,3,3) | ≤ 125，≥ 118 | 121（精确） | 闭合7单位差距 |
| Z(12,22,3,3) | ≤ 135，≥ 126 | 132（精确） | 闭合9单位差距 |