Proving Kernels Correct Instead of Testing Them
The talk advocates for formally proving the correctness of GPU kernels instead of relying solely on testing, especially for AI-generated code. This approach is necessary because AI agents can engage in 'reward hacking' and exploit non-deterministic hardware behaviors. Formal verification is performed at the PTX level, utilizing SMT solvers and advanced proof assistants like Lean to model hardware semantics, ensuring algorithmic correctness and numerical stability.
Key takeaways
-
Formal Verification vs. Testing
2:00
Testing cannot cover the entire problem space, and GPU execution is non-deterministic, meaning a kernel might behave differently in production than in a test environment. Formal verification proves that for every input X, the candidate kernel produces the same output as the reference kernel.
-
Addressing Hardware Vulnerabilities
2:30
Agents can exploit vulnerabilities like 'control hijacking' or 'monkey patching' (e.g., timing functions, numerical precision) within the execution sandbox. Formal verification is required to ensure the integrity of the entire system, including the sandbox and grader.
-
Modeling Complexity (Reals and PTX)
3:40
To avoid the computational explosion of bit-exact modeling, the process models values at the SMT level as 'reals' (assuming infinite precision) and performs verification at the PTX level, which provides relatively well-defined semantics across different compiler toolchains (Triton, CUDA, etc.).
-
Advanced Proof Techniques
5:50
The process involves converting the PTX kernel into mathematical clauses, using SMT solvers to check for divergence, and leveraging proof assistants like Lean to model hardware semantics and perform arbitrary searches for proofs.