Back to AI News
MarkTechPost

Columbia and CertiK Introduce TensorLean for Formal Verification of GPU Kernels

Researchers from Columbia University and CertiK introduced TensorLean, a Lean-based framework for formally verifying GPU kernels at the PTX level against tensor-level math specifications. The system checks properties including data-race freedom, termination, correct output within tolerance, and no stray memory writes. In its evaluation, 83 of 149 kernel instances were proved correct and 38 correctness bugs were found across projects including FlashAttention-2/3/4 and DeepGEMM, including a FlashAttention-4 data race that never appeared in 17,760 test runs. The paper and code are announced as coming soon, and the authors note limitations such as unsupported random sampling and acquire/release synchronization patterns.

AI Brief

It presents a concrete formal-verification advance for GPU kernels and documents real bugs found in widely used attention and GEMM implementations.

Researchers from Columbia University and CertiK have introduced TensorLean, a framework for formal verification of GPU kernels at the PTX level. TensorLean is a Lean-based verifier that proves compiled kernels match a tensor-level math spec. The research team checked 149 kernel instances, including every kernel of FlashAttention-2, -3 and -4 plus DeepGEMM. It proved 83 correct. The remaining 66 led to 38 correctness bugs.

TL;DR

  • Size: 1.8K-line PTX parser. Specs total 10,278 lines against 151,285 lines of kernel source, a ratio near 15:1.
  • Runs on: A 16-core workstation. It checks PTX compiled for A100, H100 and B200 kernels.
  • Performance: 83 of 149 kernel instances proved correct, 38 bugs found across 6 projects.
  • Best: Caught a FlashAttention-4 data race that never appeared in 17,760 test runs.

What is TensorLean?

TensorLean is a formal verification framework for GPU kernels at the PTX level.

It starts from unmodified source code. A developer writes a tensor-level spec in Lean. TensorLean then proves 4 properties: no data races, termination, correct output within tolerance, and untouched memory elsewhere.

How does TensorLean verify a GPU kernel?

Specs build on Lean’s Mathlib. Tensor operators follow PyTorch names, so @ means torch.matmul. Each spec has 5 parts: spec_math, spec_mut, spec_layout, spec_tol and requires. The math stays separate from the memory layout.

The pipeline runs in 7 steps:

  1. Start from unmodified source.
  2. Write the tensor-level spec.
  3. Compile to PTX and load a PTX semantics.
  4. Build a happens-before graph to check races and termination.
  5. Symbolically execute to get final memory, identical across schedules.
  6. Lower the spec to PTX-memory level.
  7. Discharge proofs with Lean’s kernel, Z3 and cvc5.

Which techniques make it scale?

  • Concurrency to sequential: Race-freedom proofs on the happens-before graph cover all CTAs, threads and loop iterations symbolically.
  • Loop invariants over semirings: Closed forms for tiled, accumulating loops, such as online softmax, need 1 SMT query per loop.
  • Tolerance proofs: Algebraic error is proved zero. Round-off error is bounded separately, then combined.
  • Assertions as hints: Developers add tensorlean_assert in source. Each is proved once, then reused.

What bugs did TensorLean find?

The GitHub README lists 38 bugs, all reported upstream. FlashAttention accounts for 23. Liger Kernel has 7, TileOPs 3, TileLang 2, DeepGEMM 2 and Triton 1.

By category, the site reports 19 memory access errors and 13 numerical bugs. It also counts 7 data races, 5 uninitialized memory reads and 5 undefined behaviors. There are 3 algorithm errors, 2 miscompilations and 1 deadlock. One bug can sit in several categories.

Of 102 FlashAttention instances, 56 passed all 4 properties. The other 46 each failed a proof goal on a source bug.

Columbia University + CertiK

TensorLean: proving GPU kernels correct at the PTX level

Lean specs, symbolic execution and SMT solvers applied to FlashAttention-2, -3, -4, DeepGEMM and more.

0
kernel instances checked
102 from FlashAttention, the rest from DeepGEMM, Liger Kernel and more.
0
proved correct
Race-free, terminating, correct within tolerance, no stray writes.
0
correctness bugs
All reported upstream. 23 are in FlashAttention-2 to -4.
0
test runs that missed 1 FA-4 race
A FlashAttention-4 data race never showed up in its own tests.
83 proved
66 with bugs

Click a tile for detail. Verification: ~10 min median per instance on a 16-core workstation; FA-3 forward on Hopper takes 50 min (31,402 proof goals).

1

SourceLean specPTXHB graphSymbolic execLowered specLean + Z3 + cvc5
Hover or tap a bar. One bug can fall into several categories, so category counts sum to more than 38.

Source lines per spec line. Overall: 151,285 source lines vs 10,278 spec lines, nearly 15:1.

Not released yetPaper and code are announced as coming soon. No license listed.
No random samplingDropout and top-p sampling cannot be expressed in specs.
No acquire/release yetKernels synced through atomic flags, such as NCCL and DeepEP, are out of scope.
Sound, not completeMay fail on correct kernels: missing input constraints, loose round-off bounds or solver timeouts.
Trusted basePTX ISA and ptxas, TensorLean's PTX semantics, its tensor-core rounding model, each spec, the 1.8K-line parser, Lean, Z3, cvc5.
Spec still neededDevelopers write a Lean spec with 5 parts: spec_math, spec_mut, spec_layout, spec_tol, requires.
Source: tensorlean.ai, GitHub (self-reported, Nov 20, 2026)© Marktechpost

How does it compare with other GPU kernel verifiers?

FeatureTensorLeanVoltaProofWrightPTX in Lean (Koska et al.)
BuildersColumbia, CertiKMSR India, StanfordNot disclosedSF Tensor
Code levelPTXPTXCUDAPTX
Checks againstLean tensor specReference kernelSafety + equivalenceLean proofs
Kernels verified149 instances, FA-2/3/4, DeepGEMM, LigerTutorial reductions, SGEMM, FA-style, TileLangKernelBench L1, safety for 74%3 simple kernels
Async ops (wgmma, TMA)Yes, FA-3 and FA-4Out of scopeNot disclosedYes
New bugs reported38Races, OOB readsNot disclosedNot disclosed
Check time~10 min median, 50 min max0.007 s to ~570 s~3 min per kernelNot disclosed

The key gap versus Volta is configuration coverage. TensorLean says equivalence checkers unroll loops for one concrete setup at a time. It uses symbolic parameters instead.

Key Takeaways

  • TensorLean proves GPU kernels correct at the PTX level using Lean, Z3 and cvc5.
  • 83 of 149 kernel instances proved correct; 38 bugs found.
  • 23 bugs sit in FlashAttention-2, -3 and -4.
  • Specs run about 15x smaller than the kernel source.


Check out the project page, GitHub repo and announcement on X. You can check the deployment options and specs here through our GPULeaderboard.com chrome extension.

Also, feel free to follow us on Twitter and don’t forget to join our 150k+ML SubReddit and Subscribe to our Newsletter. Wait! are you on telegram? now you can join us on telegram as well.

Need to partner with us for promoting your GitHub Repo OR Hugging Face Page OR Product Release OR Webinar etc.? Connect with us

The post A Team of Researchers from Columbia and CertiK Introduce TensorLean for Formal Verification of GPU Kernels appeared first on MarkTechPost.

Be the first to rate this article.

Comments & Questions (0)

Captcha
Please be respectful — let's keep the conversation friendly.

No comments yet

Be the first to comment!