大数跨境

姚期智杨植麟首次联手给 AI 出的博士级题目,Kimi 多画出了「关键一条边」

姚期智杨植麟首次联手给 AI 出的博士级题目,Kimi 多画出了「关键一条边」 AI科技评论
2026-11-10
11
导读:Kimi 刷新 629 条边图论参考纪录,只多加了1条边,为什么数学界等了这么多年?
Kimi刷新图论参考纪录:多1条边背后的AI科研突破

    作者丨郑佳美

    编辑丨岑   峰

                                                                                                       

在124个点的图中,要求既无三角形也无四边形,此前数学界公认的参考记录为629条边。Kimi K3成功构造出含630条边的图并通过程序验证。这看似微小的“1条边”增量,实则是AI首次在“极值构造”这类研究级任务上推动人类参考纪录前行,标志着AI从解题向科研迈进的重要一步。

该成果由图灵奖得主、中科院院士姚期智与月之暗面创始人杨植麟联合研究发表。团队核心旨在回答:AI是否具备真正的数学研究能力,而非仅停留在解题层面?

“多1条边”背后的科研范式变革

姚期智代表理论计算机科学的深厚底蕴,杨植麟代表大模型前沿实践,两者的联合署名象征着AI科研已从实验室猜想走向实质性的共同定义阶段。针对“AI是否仅靠暴力搜索蒙对”的争议,团队开发了全新评测系统——TCSExam。

TCSExam包含100项理论计算机科学科研任务,涵盖定理证明、Solver开发、数学对象构造及开放猜想挑战,旨在通过独立验证机制区分“运气”与“逻辑证明”。

论文地址:https://arxiv.org/pdf/2611.07962v1

实验显示,GPT-6 Astra完成了20项研究级定理中的14项,并将有限域矩阵猜想的已知证明范围从8维推进至9维。TCSExam通过Lean 4、程序检查器和Checkpoint机制,分别验证数学证明、算法表现及中间推导,确保成果的可独立验证性。

TCSExam评测框架的核心创新

TCSExam将“AI做科研”拆解为四条可验证轨道,并建立三层机制防止局部进展被误判为完整成果:

  • 定理证明(20项):覆盖13个理论计算机科学领域,要求提交Lean 4形式化证明。

  • Solver工程(30项):开发可重复运行的算法程序,在统一资源限制下评测;

  • 数学构造(20项):生成符合严格约束的图或纠错码等对象;

  • 开放猜想(30项):允许从证明成立或寻找反例两个方向展开研究。

为解决自然语言到机器验证语言的转换偏差,TCSExam建立了任务编写与独立审核机制。编写Agent构建形式化命题,审查Agent核对定义与参数,领域专家审定研究意义。此外,Solver轨道通过实例变换减少答案复用,数学构造轨道固定合法性条件以确保可比性。

针对证明任务,系统设置Bare(仅定理)、Ladder(增加引理)、Guided(提供思路)三种指导模式,以分析模型在关键引理发现与整体推导组织上的能力缺口。

区分局部推理与完整证明的机制

基于理论计算机科学中“找解难,验解易”的特点,TCSExam要求Agent提交可验证的研究证书。

对于定理证明,证书即为Lean代码。系统不仅检查内核逻辑,还审计证明依赖,排除未完成的占位符和非法公理。引入Checkpoint机制,将复杂证明拆解为多个中间目标。验证时,系统暂时假设其他Checkpoint成立,检查当前推导能力,但主定理最终必须在移除未经证明的中间假设后独立通过检查,以避免循环依赖。

案例显示,Kimi K3曾完成87.5%的中间Checkpoint,但因未能完成最终推导,系统拒绝将其认定为完整证明。数据显示,提供中间引理与思路后,模型完成数量显著增加,表明难点主要集中在关键步骤的发现与整合。

在Solver和数学构造轨道,系统通过标准化评分衡量有效性与优化质量。例如在IWLS 2023逻辑综合任务中,GPT-6 Astra生成的电路在部分实例上优于公开参考电路。

从8维到9维:AI证明能力的实证

GPT-6 Astra在Alon–Jaeger–Tarsi猜想研究中,将五元有限域上的可逆矩阵证明范围从8维推进至9维。面对维度增加带来的组合爆炸,Astra采用了结构分析与计算结合的新路线。

证明过程假设存在9维反例,通过低维结论限制其条件,转而研究向量变换前后的非零坐标数量。通过构造两组10×10非负整数数组,利用有限傅里叶恒等式建立联系,并结合反例结构性质推导计数约束。

Astra进一步将列向量按零元素分布及消去比例划分为7类,将可能的类别计数组合压缩至5005种。随后,系统构建包含204个非负变量的整数线性系统,通过选取143条方程组合,得出系数非负但等式右侧为负的矛盾关系,从而证明9维反例不存在。

该证明被整理为71个Lean模块,通过独立编译与公理检查。尽管完整的Alon–Jaeger–Tarsi猜想仍未解决,且其他开放猜想大多未取得完整方案,但这一成果展示了AI将数学结构分析与计算工具结合的能力。

迈向长期自主科研的未来

TCS实验表明,AI已在部分研究级任务中产出机器可核验的新结果,但在独立寻找关键引理、规划长程证明及推广一般性结论方面仍有差距。

研究证书机制为未来科研Agent提供了可迭代的基础:模型可利用Solver搜索候选结构,经形式化工具检查后,根据反馈修改策略。这一进展信号明确:AI科研正从辅助查文献、写代码,向辅助证定理、找反例的深度参与阶段演进。

//

推荐阅读

91% ≈ 0%?谷歌最新研究,戳破工程 Agent 的高正确率泡沫


0.016% 的 Astra 微创手术,治好了 Qwen 的 3 万 Token 死循环

未经「AI科技评论」授权,严禁以任何方式在网页、论坛、社区进行转载!

公众号转载请先在「AI科技评论」后台留言取得授权,转载时需标注来源并插入本公众号名片。

【声明】内容源于网络
0
0
AI科技评论
聚焦AI前沿研究,关注AI工程落地。
内容 9046
粉丝 0
AI科技评论 聚焦AI前沿研究,关注AI工程落地。
总阅读317.9k
粉丝0
内容9.0k