# GPU Kernel Formal Verification

## Executive summary

This talk details the critical challenge of establishing trust in high-performance GPU kernels generated by AI. While AI tools like KForge can efficiently generate optimized kernels (e.g., replacing expensive divide operations with exponent/mantissa decomposition), the primary concern shifts from performance generation to correctness. The speaker introduces Tatwa, a tensor algebra equivalence checker, which uses formal verification (Z3 solvers) to reason about the semantic equivalence between a reference kernel (e.g., PyTorch model) and an AI-generated candidate kernel. The talk highlights that while testing is useful, only formal verification can detect subtle bugs, such as missing intermediate clamp operations or semantic discrepancies, by reasoning about the underlying mathematical primitives.

## Key takeaways

- Limitations of Testing vs. Verification: Testing is inherently sampling and can only prove the absence of bugs for tested inputs. Formal verification, however, reasons about the semantics and mathematical structure, allowing it to detect bugs (like missing clamps or incorrect scaling factors) that only manifest for specific, untested inputs.
- The Need for Semantic Equivalence Checking: The core problem is ensuring that the optimized AI-generated kernel maintains the exact mathematical semantics of the original reference kernel. Tatwa achieves this by decomposing high-level operations (like `clamp` or `softmax`) into basic mathematical primitives for the Z3 solver to reason over.
- Bounded Verification Approach: Due to computational complexity, the current approach uses bounded verification, limiting the summation or expansion of product terms (e.g., capping the reduction over k to a small value) to keep the problem solvable by solvers like Z3.

## Technical details

- Quantization and Kernel Optimization: The quantization process involves selecting a scale such that the maximum absolute value fits within the target format (e.g., FP8 max value of 448). Optimized kernels often replace expensive divide operations with decompositions involving exponents and mantissas for improved performance.
- Formal Verification Tool (Tatwa): Tatwa is a tensor algebra equivalence checker that takes a reference program (PyTorch model) and an optimized candidate (Triton kernel) and reasons about their semantic equivalence. It requires decomposing high-level operations into basic mathematical primitives for solvers like Z3.
- Verification Challenges and Scope: Current verification focuses on computation equivalence at the tensor level. Limitations include reasoning about different thread instances, synchronization, and race detection, which are planned for future development (e.g., reasoning down to PTX).

## Practical implications

- The integration of formal verification tools into the kernel generation pipeline is necessary to build trust in AI-generated code, moving beyond reliance solely on unit or fuzz testing.
- Developers must be aware that while AI accelerates kernel generation, the correctness guarantee requires specialized tools that reason about mathematical semantics, not just input/output pairs.
- The industry trend requires building better memory and synchronization models to enable formal verification at lower levels (e.g., PTX).

## Topics

GPU Computing, Formal Verification, AI/ML Kernels, Tensor Algebra, Compiler Optimization, Quantization, Gimlet Labs, Tatwa, Alive2

Source: https://www.youtube.com/watch?v=IxyeS8WvX-E