TL;DR
Researchers from SF Tensor have mathematically formalized NVIDIA’s PTX (Parallel Thread Execution) instruction set within the Lean 4 theorem prover. This framework allows developers to rigorously prove the functional correctness of high-performance GPU kernels—including complex modern features like Tensor Cores, asynchronous copies, and multi-kernel pipelines—ensuring that AI infrastructure behaves exactly as specified.
What Problem Does This Paper Address?
As GPU kernels become the backbone of modern AI, their correctness is paramount. However, writing these kernels is notoriously difficult due to massive parallelism and "weak" memory models where operations can appear out of order. Traditional testing often misses subtle race conditions, and existing formal verification tools are frequently limited to simple, synchronous code.
Furthermore, as we move toward a world where LLMs generate specialized GPU code, we need a way to trust those outputs without exhaustive manual review. The authors address this by providing a foundational mathematical model for PTX that can handle the "messy" realities of modern hardware, such as data-dependent control flow and complex synchronization primitives.
Methods
The authors implemented their model in Lean 4, a functional programming language and theorem prover. Their approach centers on several key technical pillars:
- Axiomatic Memory Model: They built upon existing formalizations of the PTX memory model, which defines how threads interact through memory using relations like "program order" and "synchronizes-with."
- The Oracle Model: To handle the non-determinism of parallel execution, they give each thread an "oracle" that provides values for external events (like memory loads). This allows them to define a deterministic "small-step" semantics for individual threads while checking for global consistency after the fact.
- Observer Reads: To define what a kernel actually "computed," they introduced logical "observer read events" that occur after the kernel finishes. This allows them to prove that the final state of memory matches a mathematical specification.
- Modern Feature Support: Unlike previous work, this model explicitly formalizes "proxies" (different ways of accessing memory), asynchronous bulk copies (TMA), and Warp-Group Matrix Multiply-Accumulate (WGMMA) operations used in NVIDIA's Hopper architecture.
Verified Applications
Rather than using standard ML datasets, the authors evaluated their framework by verifying a suite of hand-written PTX kernels of increasing complexity:
- Elementwise operations: Simple affine maps ($y = \alpha x + \beta$).
- Matrix Multiplication (GEMM): Ranging from basic scalar versions to high-performance Ampere-tiled and Hopper-specific (WGMMA) implementations.
- FlashAttention: A critical algorithm for modern Transformers, verified using exact real arithmetic.
- Mixture of Experts (MoE): A 3-kernel pipeline involving routing and expert computation.
- Megakernels: Kernels that use atomic counters for dynamic work distribution.
Key Insights and Ideas
- Formalizing PTX vs. CUDA: The authors chose to model PTX because it is the common "bottleneck" language that most high-level DSLs (like Triton or Mojo) compile into. Verifying at this level captures the behavior of the code that actually runs on the hardware.
- Soundness Over Completeness: The model is designed to be conservative. If the NVIDIA documentation is ambiguous, the model allows more possible outcomes. This means they might fail to prove a correct kernel is correct, but they are much less likely to accidentally "prove" an incorrect kernel is correct.
- Compositionality: By modeling the boundary between kernels, they can prove the correctness of an entire multi-step pipeline (like an MoE layer) by treating the output of one kernel as the input to the next.
- Real Number Abstraction: They model floating-point operations as exact real numbers. While this ignores quantization errors, it allows them to prove "functional correctness"—the logic of the algorithm—as a necessary precursor to numerical stability analysis.
Key Results
The project successfully verified 9 PTX entry points totaling 454 instructions. This required a massive effort of 34,034 lines of Lean proof code.
The complexity of the proofs scales significantly with the hardware features used:
- A simple Elementwise kernel (18 instructions) took ~1,000 lines of proof.
- The Hopper GEMM kernel (98 instructions), which utilizes complex asynchronous pipelines and mbarriers, required nearly 17,000 lines of proof.
All proofs were checked by the Lean 4 kernel, ensuring they rely only on a small set of standard mathematical axioms.
Limitations and Future Work
- Partial Correctness: The model proves that if a kernel terminates, the answer is correct. It does not currently prove that kernels will always terminate (e.g., it doesn't rule out infinite loops in custom synchronization).
- Undefined Behavior (UB): The proofs assume the kernel is free of ISA-level undefined behavior (like misaligned memory access). Proving "UB-freedom" is noted as a difficult but important future direction.
- Proof Automation: The current proof-to-instruction ratio is high (~75:1). The authors suggest that future work will need more automation and reusable libraries to verify larger, production-scale kernels.
- Hardware Scope: The model does not yet cover multi-node communication (NCCL) or concurrent modification of memory by the CPU host while the GPU is running.
Summary updated