核心问题:所有完成的执行都正确,再加上存在可完成的执行,为什么仍不等于 kernel 一定正确地结束?
论文卡片
- 原题: Formalizing PTX in Lean to Prove GPU Kernel Correctness
- 作者: Luk Koska、Tom Koska、Ben Koska;SF Tensor。
- 日期与版本: 2026-11-03,arXiv v1;cs.AI,形式化模型与案例研究预印本。
- 定位: 用 Lean 表达 PTX 执行与内存一致性,验证异步操作、数据相关控制流及顺序多 kernel 管线。
- 入口: arXiv · 一手全文(v1) · PDF · alphaXiv
简短导读:把“正确”拆成不同的命题
GPU 线程读到的值,既影响后续计算,也可能决定它走哪条分支、循环多少次。现有 PTX 内存一致性公理约束事件之间的关系,却不能单独解释这些事件如何由程序产生。作者因此把线程内的逐步执行与线程间的一致性约束接起来。
方法中的 oracle 不是另一个 AI 判断器,而是数学上的外部取值序列:先给每个线程提供可能读到的值,使它的执行路径确定下来,再用 reads-from、原子性、同步等规则筛选整组执行是否一致。异步拷贝和矩阵运算也进入同一事件模型;同步不足时,不能随意把结果当成已经可用。
核心保证针对满足启动前提的每次 launch 中,所有一致且已完成的执行。其中“已完成”要求所有启动线程退出。作者还分别构造一条一致的完成执行,并给出满足前提的具体 launch,防止证明对象根本不存在。
这一步很容易被误读。若模型约束互相冲突,根本没有完成执行,“所有完成执行的结果都正确”仍可在逻辑上成立。存在性证明排除了这种空洞性;但它没有排除其他执行永远等待。能够完成与必然完成,量词不同。 §5.2 正面承认,没有为轮询等循环证明终止性。
证据与限制
这是一篇形式化与案例研究,没有给出与其他验证器的同题成功率、耗时或性能排名。与 Volta 等工作的比较主要是表达范围及证明方式:作者希望覆盖更多异步和动态行为,代价是依赖人工、LLM 辅助的 Lean 证明,而非通用自动判定程序。
| 论文展示的证据 | 可以支持什么 | 不能据此推出什么 |
|---|---|---|
| 9 个 PTX 入口、454 条指令,对应 34,034 行证明 | 模型能承载所选案例的机器检查证明 | 已能低成本验证任意生产 kernel |
| 每个变体都有普遍正确性与构造性非空洞证明 | 完成执行满足规格,且模型允许完成执行 | 所有执行都终止、不会挂起 |
| H100 / B200 上与参考实现的正确性测试;WGMMA 案例仅测 H100 | 所选实现另有硬件测试证据 | 测试已经证明模型与硬件完全一致 |
案例包括矩阵乘、简化 FlashAttention、三次启动组成的双专家 MoE,以及依赖原子计数器分配任务的小型 megakernel。PTX 均为便于论证而手写的实现,不是真实编译器输出;覆盖的 81 种指令形式也采用固定限定符组合。证明行数不含约 5,600 行共享引理,Hopper 案例还复用了另一变体约 2,100 行引理,因此不能把表中的总量当成全部证明投入。
作者报告 Lean 4 检查通过,未使用 sorry 或自定义 axiom 声明,定理只依赖 Lean 的三个标准公理。不过,内存规则被写成模型的定义和谓词:没有新增逻辑公理,不意味着模型已经被证明忠实于 PTX。 作者、规格、解析器、模型和底层实现仍各有信任责任。
另外,浮点被解释为精确实数,不覆盖舍入误差、数值稳定性或浮点位级重解释;把模型结论用于真实 PTX,还假定没有 ISA 层未定义行为,并信任 ptxas 与硬件实现。论文没有证明这项无未定义行为假设。以上为原文报告,本导读未独立运行证明或硬件测试。
重点阅读章节
- §3.3: 顺着执行、一致性、完成性和存在性定义读,关注正确性定理究竟量化了哪些对象。
- §4.1–4.2: 先看证明检查和规模,再看原子计数器如何保证两个线程领取不同任务;不要把任务分配正确直接理解为一般进展保证。
- §5.2–5.4: 对照终止性、未定义行为与 no-thin-air 的边界,理解作者为什么宁可允许更多执行,也不轻易排除难处理的执行。
思想启发:证明的范围也需要被解释
以下是导读者的延伸理解。
存在性证明的价值,在于给一个普遍命题补上“确实有对象”的证据。它不是装饰性的附加结论,也不是终止性证明的简写。把三者分开,才能看清一份机器检查证明究竟消除了哪种疑问。
作者为了保守建模而省略 no-thin-air 等约束,意在扩大允许的执行集合:如果能在更大的集合上证明输出正确,结论仍有价值。但这种方向上的保守性,也使“存在一条模型执行”不能自动成为“真实机器可以实现这条执行”的保证。普遍性质与存在性性质面对过近似时,推理方向并不相同。
作者展望未来整个训练软件栈都能被形式化验证。这是研究愿景;当前案例更具体的启发,是让“已验证”从一个标签变成一组有前提、有量词、有适用边界的命题。
三个开放性思考问题
1. 如果 kernel 有一种能结束的执行,也有一直等待的执行,论文的两类定理会如何描述它?
参考思路
只要所有完成执行都满足规格,部分正确性就可以成立;只要至少一条一致的完成执行存在,非空洞性也可以成立。一直等待的执行不会被这两个结论排除。终止性还涉及调度、可见性与进展前提,不能从存在性直接补出。
2. 允许比真实机器更多的执行,为什么有利于保守地证明输出,却可能削弱完成执行的存在性证据?
参考思路
若真实执行集合包含于模型集合,对模型集合中的全部对象成立的性质,也对真实执行成立;但模型中的一个见证可能落在多出来的部分。非空洞性首先检查模型内部是否自洽,要推及真实可执行性,还需要额外的对应关系。
3. 没有自定义公理、证明也全部检查通过,为什么仍不能据此判断 PTX 模型是否正确?
参考思路
证明检查确认推导服从给定定义与逻辑,并不自行确认定义与外部规范对应。一个遗漏行为的模型仍可能拥有严密证明。另一方面,不能因为存在建模信任就否定证明价值:需要分别讨论推导有效性、语义忠实度和应用前提,而不是只用可信或不可信概括。