betaFeedback

WorksComputer Science

LARK: Lean-Assisted Reasoning for LLM-Generated GPU Kernels

Abstract

Efficient GPU kernels are typically low-level and hardware-specific, and LLM agents can now generate them faster than experts can verify. Existing approaches rely on testing, which provides evidence but not a guarantee of correctness. We introduce LARK, an agentic framework that automatically and formally verifies GPU kernels against their PyTorch reference implementations. LARK proves equivalence in functional and memory behavior under exact arithmetic and establishes a new trust boundary: human effort is only needed to verify operator-level Lean semantics ahead of kernel generation time, instead of checking every single line of generated code. LARK formalizes the GPU machine model and the semantics of each operation in Lean 4 once per target language, and the Lean 4 semantics of any incoming kernel is derived from these pre-built definitions. LLM agents then automate the proof in two steps. First, an agent decomposes the whole kernel semantics into smaller segments and Lean 4 verifies this segmentation, which addresses the intractability of proving equivalence for large kernels directly. Second, agents write Lean proofs that each kernel segment matches its high-level PyTorch counterpart. Together, the two steps give whole-program equivalence. We demonstrate that LARK can be used 1) to ensure correctness in existing code-generation agents and 2) to automatically verify human-written kernel libraries. On the KernelCraft GPU tasks, combined with a simple ReAct agent, LARK enables GLM 5.3 to fully verify 10 of 12 Level-1 kernels and Opus 5.5 all 5 Level-2 kernels. Moreover, over 10 production kernels randomly sampled from popular open-source LLM serving frameworks, LARK verifies 9 and identifies a new data race bug in the tenth. We believe LARK represents a significant step toward verifiable code generation in the agentic era.

Introduction

GPU kernels are where the cost of training and serving deep learning models is paid, and the fastest are hand-scheduled CUDA, PTX, or HIP written close to the metal ([11, 33] (Wu et al. 2026)). Such code is increasingly written by LLM agents ([27, 28, 7, 6]), and a plausible kernel is not a correct one: the same models that write fluent code write fluent bugs ([20, 9]). Every regenerated kernel needs its own correctness check, at the pace of generation. Existing checks fall short on one count or the other (Figure 1, top). Tests on sampled inputs keep pace but give evidence, never a guarantee; human review reasons about all inputs but cannot keep pace; an LLM judge removes the human but not the problem. What a generated kernel needs is a proof of a precise equivalence statement, checked by a proof assistant such as Lean 4 ([25]), and formal tools do not provide one either: GPUVerify ([8]) proves race and divergence freedom, not the specification; a verified compiler ([21]) certifies its own translation, not a generated kernel; a hand-written model ([4]) or proof ([18]) puts a human back where we want automation.

Figure 1. Where trust sits in LLM kernel generation. Top: existing pipelines check a generated kernel by sampled tests or review, so the whole kernel is taken on faith. Bottom: LARK fixes what is assumed (dashed) before the kernel is seen, the machine model and operation semantics formalized once per language and the task’s interface; every property of the kernel is proved in Lean or the kernel is rejected, and the assumptions are reported with every result.

We present LARK (Lean-Assisted Reasoning for Kernels), an agentic framework in which LLM agents write both the model of the kernel and the proof, and Lean checks both. Once per target language, LARK formalizes in Lean a machine model of the GPU and the semantics of each operation and measures them against the hardware; the machine model is shared across languages, so a new target supplies only its operations and their semantics, and we instantiate LARK for PTX, CUDA, and AMD HIP. Given a PyTorch specification and a kernel from any generator, the kernel’s semantics is derived from these pinned parts, agents write the proofs, and Lean checks every step, so a wrong agent output is a failed proof, never a wrong theorem. This division of labor raises three challenges:

  1. Semantic gap. The kernel’s Lean semantics is spelled out operation by operation over the machine model, while the PyTorch reference has a tensor-level semantics in Lean. LARK bridges the two by deriving a flat model of the kernel and having an LLM agent segment it, verifiably, into a segment-level model that a proof can induct on (§ 5).

  1. Fidelity versus tractability. The machine model must be sound for the hardware yet abstract enough to prove against. LARK’s model computes over exact numbers, runs a phase’s threads in sequence, and treats undefined behavior as a fault; what makes this sound, race freedom above all, is proved in Lean per kernel as obligations, and a kernel that can fault or race has no theorem (§ 4.1 and § 5).

  1. Trust boundaries. Any assumption the theorem depends on but Lean does not verify must be trusted by humans; we call this set the trust boundary. LARK keeps it small and fixed by the task, the hardware machine model, the fixed mapping from operation semantics to kernel semantics, and the formalized task specification, so it can be reviewed once in advance; every run produces a Lean certificate that any Lean project re-checks without repeating the LARK procedure (§ 5.1).

LARK tackles these three challenges, and we make the following contributions:

  • We present LARK, an agentic formal-verification workflow for GPU kernels in low-level, close-to-metal languages. To our knowledge, LARK is the first attempt at using agents to produce formally verified low-level GPU code for equivalence check.

  • We show how to formalize low-level GPU semantics in Lean 4 and prove functional equivalence between a GPU kernel and a PyTorch reference. LARK combines verified program segmentation with iterative agentic proof construction, and humans review the task’s trust boundary only once, ahead of time in dependent of kernel inputs; every kernel generated afterwards is certified relative to those trusted assumptions.

  • We demonstrate that LARK can be integrated with agentic code-generation harnesses to certify their kernels and serves as an automated verifier for human-written kernels. On KernelCraft, GLM 5.3 certifies 10 of the 12 Level-1 kernels and Opus 5.5 all five fused Level-2 kernels, every semantics-breaking mutant is rejected, and nine of ten production kernels verify while the tenth is rejected for a real data race (§ 6).

Motivating Example

Figure 2 makes the three challenges of § 1 concrete. The specification (Figure 2a) multiplies two FP16 matrices. The kernel (Figure 2c) is LLM-written PTX, the virtual instruction set CUDA compiles to, in the shape of fast kernels: each one-warp block computes one output tile (line 3), staging slabs of AA and BB into shared memory (lines 5–7) and multiplying them on the tensor cores (lines 8–11) before storing the tile (lines 16–17). The theorem (Figure 2b) relates the two through the state of a machine that runs the kernel, under a premise of the task, not of the kernel; a test samples it, a proof establishes it for every input (§ 3).

Running example: general matrix multiplication

Figure 2. Running example: general matrix multiplication (GEMM). (a) The PyTorch reference. (b) The equivalence theorem: the task’s fixed premise (StdPre: inputs placed, buffers apart, bases aligned, launch geometry) implies fault-free completion (some s′s') and ABAB in the region of CC, over the reals. (c) The PTX kernel implementing (a); its per-lane addressing, shared-memory staging, barrier, and warp-collective ldmatrix/mma (lines 4–11) each need formal meaning before (b) can be stated. Line 13 (red), in place of line 15 (green), omits the barrier before the next slab is staged. Testing can only sample (b) and accepts the bug; LARK proves (b) with line 15 and locates the race with line 13.

What a guarantee catches. Line 13 of Figure 2c is a one-line bug a generator could write: without the barrier, a lane may overwrite a staged slab another lane is still reading. Nothing marks the omission among 300 lines that look alike, and the kernel can pass every test, since on a given GPU the warp may finish ldmatrix before any lane stores, while PTX promises no such order. LARK catches it in Lean: the race-freedom obligation it proves before any value (§ 5) fails for line 13 with a counterexample, two lanes meeting at one shared cell, that points to where the barrier belongs; with line 15 the kernel gets the theorem in Figure 2b.

Where the challenges show. Semantic gap: the conclusion speaks of the matrix ABAB, while the kernel updates four registers per lane per mma (line 10) and loops by a branch to a label (line 15), naming no tile, iteration, or sum to induct on. Fidelity versus tractability: a model faithful to every interleaving of 32 lanes and 32 blocks admits no tractable proof, and each abstraction that helps has a condition, such as sequential threads needing lines 6 and 8 never to race, that must be proved rather than assumed for the theorem to be worth anything. Trust: that the Lean mma is what the tensor core computes, that bar.sync is a barrier, and that the Lean specification and interface are those of the task can only be believed, so this trust boundary (§ 1) must exclude whatever an agent writes and stay a short, fixed list; § 4 shows how LARK meets each challenge.

Problem Definition

§ 2 showed the theorem informally; we now state, for a fixed target language, what is proved, what is assumed, and what a verifier must deliver.

Specification. A specification SS is a Torch module, denoting a total function ⟦S⟧:D→T\llbracket S \rrbracket: D \to T from the inputs DD with the declared shapes, types, and constraints to the output tensors TT. SS is the ground truth.

Kernel and machine model. A kernel KK is a program in the target language with a launch geometry. Its meaning is fixed only relative to a machine model MM: the states ΣM\Sigma_M, a partial semantics for each operation, a scheduling rule, and a representation of values (ours is in § 4.1). These define the partial whole-launch semantics ⟦K⟧M:ΣM⇀ΣM\llbracket K \rrbracket_M : \Sigma_M \rightharpoonup\Sigma_M, defined at σ\sigma when every maximal execution from σ\sigma is finite, fault-free, and ends in the same state.

Interface. Tensors enter and leave the machine through memory under the task’s interface II: the region and layout of each tensor, the launch geometry, and the disjointness of the regions. II belongs to the task, not to KK, and yields a precondition In⁡I(σ,x)\operatorname{In}_I(\sigma,x), true when σ\sigma has the declared geometry and holds x∈Dx \in D in the declared regions, and an output extractor Out⁡I:ΣM→T\operatorname{Out}_I : \Sigma_M \to T. In Figure 2b, StdPre is InI_I, stdExtract is OutI_I, and runLaunch is ⟦K⟧M\llbracket K \rrbracket_M.

Equivalence. Both sides are compared as real-valued tensors, the kernel’s operations read over exact reals (§ 4.1 and § 5.1). KK is equivalent to SS under MM and II, written K≡M,ISK \equiv_{M,I} S, if

∀x∈D. ∀σ∈ΣM. In⁡I(σ,x)⟹⟦K⟧M(σ)↓∧Out⁡I(⟦K⟧M(σ))=⟦S⟧(x).(1)\begin{aligned} &\forall x \in D.\ \forall\sigma\in\Sigma_M.\ \operatorname{In}_I(\sigma,x)\\ &\qquad\Longrightarrow\llbracket K \rrbracket_M(\sigma)\downarrow\land\operatorname{Out}_I(\llbracket K \rrbracket_M(\sigma)) = \llbracket S \rrbracket(x). \tag*{(1)} \end{aligned}

Quantifying over every initial state that holds the input forbids KK from depending on memory outside the interface, and reading the output from the declared region fixes where the result lands. This is all that equivalence in memory behavior means: the memories of MM are unbounded (Section 4.1), so a write outside the interface is invisible to the statement, and out-of-bounds safety on the host’s allocations is not guaranteed.

Trust boundary. A proof of (1) is a proof about MM; to carry over to the real hardware and host H\mathcal{H}, it needs facts no proof inside MM can establish: that MM is faithful to the hardware up to its idealizations, that the formalization of SS denotes ⟦S⟧\llbracket S \rrbracket, and that the host honors II. This trust boundary must be fixed by the task, not by the kernel: MM and II are unavoidably premises, nothing else may be, and properties of KK such as race freedom or termination are obligations, proved per kernel (Sections 4.1 and 4.2).

Problem definition. Fix a target language with machine model MM. Given a specification SS, an interface II, and a kernel KK, produce either a certificate (Π,π)(\Pi,\pi) or a rejection, which makes no claim about KK. The premises Π=ΠM∪ΠK\Pi= \Pi_M \cup\Pi_K are ΠM\Pi_M, the faithfulness of MM to H\mathcal{H}, and ΠK\Pi_K, the task’s signature and launch, from which In⁡I\operatorname{In}_I and Out⁡I\operatorname{Out}_I are computed by fixed definitions; both are reported with the result (Section 4.3). The machine-checked proof π\pi establishes

ΠK⊢K≡M,IS\Pi_K \vdash K \equiv_{M,I} S

with In⁡I\operatorname{In}_I satisfiable for every input in DD, and hence ΠM⊨K≡H,IS\Pi_M \models K \equiv_{\mathcal{H},I} S: π\pi supplies the equivalence in MM, ΠM\Pi_M the passage from MM to H\mathcal{H}.

Requirements. A solution must be sound: a certificate is issued only if K≡M,ISK \equiv_{M,I} S holds, and π\pi is checked by a checker that does not trust its producer. Soundness makes both conjuncts of (1) obligations, proved rather than assumed. Among sound solutions we prefer the more complete, certifying more of the kernels that are equivalent, and the more trustworthy, certifying with a smaller ΠM\Pi_M. The second objective separates this problem from classical equivalence checking: race freedom and the other regularities that make GPU kernels tractable are properties of KK, proved per kernel, so that ΠM\Pi_M keeps only what no per-kernel proof can discharge.

Method

Section 3 asks for a certificate whose premises say nothing about the kernel: everything inside the trust boundary must be fixed before the kernel arrives, and everything about the kernel must be proved. This section follows that split (Figure 3): a Lean model of the kernel we can trust, fixed once per target language (Section 4.1); the way from the model to a proof, written by agents and checked by Lean (Section 4.2); and the short, fixed list of what is left to trust (Section 4.3).

A Model We Can Trust

In this section, we describe how, ahead of time, a Lean semantic model can be generated for each operation in a target language such as PTX or HIP. This process involves three key components: 1) Machine model: Defining a machine model encompassing memory, register abstraction, fault handling, and concurrency, 2) Per-op semantic contextualization: Specifying per-operation semantics that contextualize the machine model for the chosen target language; and 3) Translator: Developing translators to automate kernel semantic composition and support extension to new target languages.

In this setup, the Lean model of a kernel can be trusted because everything it is built from, a machine model, the semantics of each operation, and a translator, is fixed and checked by human experts before the kernel arrives, and none of it is generated by agents.

Machine model. The machine model of Section 3 is a quadruple M=(Σ,T,sem⁡,cut⁡)M = (\Sigma, \mathcal{T}, \operatorname{sem}, \operatorname{cut}): the states, the operations of the target language, their semantics, and their classification by the synchronization they perform. Each part trades fidelity for tractability, once, for every kernel.

Memory. A state holds the whole launch:

Σ=pc×reg×memG×memS×mem1×geom,\Sigma= pc \times reg \times mem_G \times mem_S \times mem_1 \times geom,

with pcpc the program counters, regreg the registers, keyed by thread and name, memGmem_G the global memory, memSmem_S one shared memory per block, mem1mem_1 one local memory per thread, and geomgeom the read-only launch geometry and coordinates. Keeping every thread’s registers in one state makes it immediate that an operation of one thread touches no register of another. Memories are unbounded, so the model cannot detect an access outside the host’s allocations, which is outside the guarantee (Section 3).

Values. Every register and memory cell holds a typed value or is undefined:

Val={⊥}∪{(τ,x):τ∈Ty, x∈Payload(τ)},Val = \{\bot\} \cup\{(\tau,x) : \tau\in Ty,\ x \in Payload(\tau)\},

a type tag τ∈Ty\tau\in Ty (the set is listed in Appendix A.7) and a payload xx: an exact real, extended with −∞-\infty for running maxima, and a float, an integer under an integer tag, a bit under a predicate. Exact arithmetic is a deliberate idealization, stated once as the scope of the guarantee rather than as an assumption about any kernel: LARK does not track numerical error, (1) is equivalence under exact arithmetic, and floating-point behavior is left to testing checks (§ 5.1).

Faults. sem⁡t(i):Σ⇀Σ\operatorname{sem}_{t}(i) : \Sigma\rightharpoonup\Sigma is the semantics of operation ii executed by thread tt, which selects the register row and the coordinates. Its undefined cases are the faults: an IEEE result outside R∪{−∞}\mathbb{R} \cup\{-\infty\}, a read of the wrong tag or of ⊥\bot, a misaligned vector access, a negative address, an exhausted fuel (defined below), a non-converged cut. A kernel that can fault has no theorem.

Concurrency. Reasoning about every interleaving of thousands of threads is not practical, and machine-learning kernels do not need it: they work in phases separated by barriers, within which no two threads touch the same data. The model makes phases explicit through cut⁡:I→{⊥,coll⁡,warp⁡,block⁡,grid⁡,halt⁡}\operatorname{cut} : \mathcal{I} \to\{\bot,\operatorname{coll},\operatorname{warp},\operatorname{block},\operatorname{grid},\operatorname{halt}\} (Table 1): a barrier is a cut at its level, a return the halt, and a warp-collective operation such as mma⁡\operatorname{mma} a cut of kind coll, where the lanes of the warp meet and the operation executes once over all their registers. A kernel is a sequence K∈I∗K \in\mathcal{I}^{*} with K[p]K[p] the operation at program counter pp; a thread iterates sem⁡\operatorname{sem} and parks at a cut:

Kind (examples)GuardUpdatecut
Scalar (add, mul)tags, x⃗∈dom⁡op⁡^\vec{x} \in\operatorname{dom}\widehat{\operatorname{op}}reg⁡(t,d)↦(τ,op⁡^(x⃗))\operatorname{reg}(t,d) \mapsto(\tau,\widehat{\operatorname{op}}(\vec{x}))⊥\bot
Memory (ld, st)tag, aligned, α≥0\alpha\ge0reg⁡(t,d)↔mem⁡(α)\operatorname{reg}(t,d) \leftrightarrow\operatorname{mem}(\alpha)⊥\bot
Control (bra, ret)reg⁡(t,p)=(pred⁡,b)\operatorname{reg}(t,p) = (\operatorname{pred},b)pc⁡t↦q\operatorname{pc}_{t} \mapsto q if bb⊥\bot, halt
Barrier (bar.sync)—parkswarp, block, grid
Collective (mma)tags on all lanesall lanes’ reg⁡(t′,d)\operatorname{reg}(t',d)coll

Table 1. Operation schemas by kind: guard (failed means a fault), update, and cut; all but Control also advance pc⁡t\operatorname{pc}_{t}. op⁡^\widehat{\operatorname{op}} is the operation’s own function (+, an address α\alpha, a branch target qq, a tile product); sem is defined per operation, the kinds only group them.

step⁡K,t(σ)={sem⁡t(K[p])(σ)if cut⁡[K[p]]=⊥,σotherwise (parked),\operatorname{step}_{K,t}(\sigma) = \begin{cases} \operatorname{sem}_{t}(K[p])(\sigma) & \text{if } \operatorname{cut}[K[p]] = \bot,\\ \sigma& \text{otherwise (parked),} \end{cases}

where p=pct(σ)p = p_{c_t}(\sigma). A launch is a fold over the hierarchy of units, in time and then in parallelism:

run⁡ℓ(σ)=conv⁡ℓ(run⁡ℓ−1(um)∘⋯∘run⁡ℓ−1(u1)(σ)).(2)\operatorname{run}_{\ell}(\sigma) = \operatorname{conv}_{\ell}\left(\operatorname{run}_{\ell-1}(u_m) \circ\cdots\circ\operatorname{run}_{\ell-1}(u_1)(\sigma)\right). \tag*{(2)}

Here u1,…,umu_1,\ldots,u_m are the units one level down (the lanes of a warp, the warps of a block, the blocks of the grid) making up the unit at level ℓ∈{warp⁡,block⁡,grid⁡}\ell\in\{\operatorname{warp},\operatorname{block},\operatorname{grid}\}, each run to the next cut of level ℓ\ell; conv⁡ℓ(f)(σ)=f(σ)\operatorname{conv}_{\ell}(f)(\sigma) = f(\sigma) if every thread of the unit parks at one program counter in f(σ)f(\sigma), undefined otherwise; and run⁡0\operatorname{run}_0 iterates step to the lane’s next cut. Each level has a fuel κℓ∈N\kappa_{\ell} \in\mathbb{N}, the steps or sub-runs allowed before its next cut; run⁡ℓ0\operatorname{run}_{\ell}^{0} is undefined, so running out of fuel is a fault, and κˉ\bar{\kappa} is data the run supplies. The theorem requires σ∈dom⁡(run⁡grid⁡κˉ)\sigma\in\operatorname{dom}(\operatorname{run}_{\operatorname{grid}}^{\bar{\kappa}}).

Per-operation semantics. Each operation op has a lower-layer function op⁡^\widehat{\operatorname{op}}, plain mathematics independent of the machine (add⁡^=+\widehat{\operatorname{add}} = +, max⁡^=max⁡\widehat{\operatorname{max}} = \operatorname{max} on R∪{−∞}\mathbb{R} \cup\{-\infty\}, mma⁡^\widehat{\operatorname{mma}} a tile multiply-accumulate), and an upper layer that binds it to the state. Writing an operation as in the kernel, op d,a1,…,akd,a_1,\ldots,a_k, with register names dd and aja_j and τ\tau and τj\tau_j for the tags the operation names for operand jj and the result, a scalar operation executed by thread tt is

sem⁡t(op⁡ d,a1,…,ak)(σ)=σ[reg⁡(t,d)↦(τ,op⁡^(x1,…,xk)), pct↦pct+1]\operatorname{sem}_{t}(\operatorname{op}\ d,a_1,\ldots,a_k)(\sigma) = \sigma\left[\operatorname{reg}(t,d) \mapsto(\tau,\widehat{\operatorname{op}}(x_1,\ldots,x_k)),\ p_{c_t} \mapsto p_{c_t}+1\right]

if reg⁡(t,aj)=(τj,xj)\operatorname{reg}(t,a_j) = (\tau_j,x_j) for every jj and (x1,…,xk)∈dom⁡(op⁡^)(x_1,\ldots,x_k) \in\operatorname{dom}(\widehat{\operatorname{op}}), and undefined otherwise. Table 1 gives the schema of each kind of operation: the guard that bounds the domain, the update, and the cut. The operations of each language and their lower-layer definitions are generated from one pinned table per language (Figure 3, per-op semantic formalization), and every definition is measured against a real GPU on random operands before use (Appendix § 9.§ 6).

Figure 3. The LARK pipeline. Offline, the machine model and per-operation semantics are formalized once per target language and measured against the hardware, and the Torch module once per module. Per kernel, the translator composes the flat whole-kernel semantics in Lean, then three Lean-checked stages follow: (1) the race-freedom check; (2) an agent segments the flat model and proves the segment-level model equivalent to it; (3) agents prove the segment-level model equivalent to the Torch semantics. Lean’s error reports drive the agent loops. Green: Lean-checked. Yellow: trusted, listed in the report (§ 5.1). Red: agent-generated, trusted for nothing.

Translator. The translator is fixed code, not an agent, and it never guesses. It reads the kernel text bb as data, parse⁡L:Bytes⇀I∗\operatorname{parse}_{L} : \mathit{Bytes} \rightharpoonup I^{*} (CUDA and HIP through a structured tree whose lowering lower⁡L:Tree→I∗\operatorname{lower}_{L} : \mathit{Tree} \to I^{*} is a definition in MM), so the kernel’s fold is run⁡gridκ⃗\operatorname{run}_{\mathrm{grid}}^{\vec{\kappa}} on K=parse⁡L(b)K = \operatorname{parse}_{L}(b) and nothing of the semantics is generated per kernel. Every reading is checked by a read-back: a formatter fmt⁡L:I∗→Bytes\operatorname{fmt}_{L} : I^{*} \to\mathit{Bytes} writes the data back and fmt⁡L(parse⁡L(b))=b\operatorname{fmt}_{L}(\operatorname{parse}_{L}(b)) = b must hold byte for byte, so what is trusted is the formatter, a quarter the size of the reader (Appendix § 9.§ 8). An operation or pattern outside II or the concurrency model (asynchronous operations, atomics, a NaN literal) is refused by name before any proof is attempted, since we would rather refuse a correct kernel than prove a wrong theorem (Appendix § 9.9).

Finally, the translator prepares the proof with proved lemmas, generated with their proofs and checked by Lean (the race-freedom lemmas of § 5, the lane bridges and program-counter rungs of Equation (2)), and scaffolding lemmas, whose statements it generates and whose proofs an agent writes, so they can be false and then simply fail. Two generator hints, the exact constant behind a rounded literal and the expected launch, guide this generation but decide nothing; Lean can check neither, so both are reported as trusted (§ 5.1).

Retargeting. MM splits as Mlaunch∪LM_{\mathrm{launch}} \cup L: a launch part shared by every language and a per-language part LL, which includes its operations with their semantics and cuts, warp width, reader and read-back formatter, collective lane layouts, and lowering (Appendix § 9.§ 7). We instantiate LARK for PTX, CUDA, and HIP.

From Model to Proof

The automated Lean proof flow relies on two key checks: ensuring data race freedom and verifying functional equivalence. Data race freedom can be directly verified within Lean (Figure 3 Stage 1); on the other hand, verifying full functional equivalence may pose computational challenges. To address this, we propose a segment-level approach: first, perform a formally verified flat-model segmentation (Figure 3 Stage 2); then, check functional equivalence at the segment level (Figure 3 Stage 3).

Stage 1: Data-race-freedom check. The fold of (2) runs the units of a phase one after another, while the hardware runs them at once. The two agree only for race-free kernels, so race freedom is the first thing LARK proves about a kernel, before any equivalence is attempted. The vocabulary is the fold’s: a phase ϕ\phi at a level is the run between two consecutive cuts of that level, its units uu are the lanes, warps, or blocks that the level folds, and the footprints Wϕ(u),Rϕ(u)⊆Loc⁡W_{\phi}(u), R_{\phi}(u) \subseteq\operatorname{Loc} are the locations unit uu writes and reads during ϕ\phi, with Loc⁡\operatorname{Loc} the global, shared, and local addresses and the register names of Σ\Sigma.

Obligation 1 (Race freedom). RF⁡(K)\operatorname{RF}(K): for every phase ϕ\phi and every two distinct units uj,uku_j,u_k of it, Wϕ(uj)∩Wϕ(uk)=∅W_{\phi}(u_j) \cap W_{\phi}(u_k) = \varnothing and Wϕ(uj)∩Rϕ(uk)=∅W_{\phi}(u_j) \cap R_{\phi}(u_k) = \varnothing.

A warp-collective step counts as one more unit: it executes once per warp, with a footprint over the registers of every lane and the memory it reads, and it must meet no lane’s footprint within the warp-level phase around its coll cut, since that cut orders execution, not memory. Race freedom is what the fold needs: the actions of race-free units commute and the barrier that ends a phase orders the phases, so every execution from σ\sigma is finite and ends in the fold’s result, ⟦K⟧M(σ)=run⁡gridκ⃗(σ)\llbracket K \rrbracket_{M}(\sigma) = \operatorname{run}_{\mathrm{grid}}^{\vec{\kappa}}(\sigma). This is Lipton’s reduction ([22]) as it applies to data-race-free GPU kernels ([1, 10, 8, 24]); we rely on it at every level as metatheory, not as a Lean proof (§ 5.1). To discharge the obligation, the translator derives each footprint from the kernel’s addresses and generates the two lemmas of Obligation 1, with proofs, for every phase and pair of units (Appendix § 9.10); Lean checks them, an agent attempts any lemma whose proof fails, and a kernel with an unproved lemma is rejected. The condition is sufficient, not necessary: a benign race is rejected as readily as a harmful one (§ 6 reports one found in a production kernel), the price of never accepting a racy kernel.

Stage 2: Verified flat-model segmentation. The kernel’s flat model FK=run⁡gridκ⃗F_{K} = \operatorname{run}_{\mathrm{grid}}^{\vec{\kappa}} on KK follows the kernel line by line with a program counter. Built only from the pre-checked parts of § 4.1 and the kernel’s text, it is trustworthy, and it is one semantics for every language, so CUDA and HIP are lowered to it at no cost in trust. It is not the proof’s view: it talks about single operations and registers where the Torch module talks about tensors, and a direct proof would unfold it operation by operation with no index to induct on. An agent therefore segments the flat model into a segment-level model GKG_K, a term of the grammar

G::=sem⁡t(i)∣G;G∣for j<n do G(j)∣if p then G else G,G ::= \operatorname{sem}_{t}(i) \mid G;G \mid\text{for } j<n\text{ do }G(j) \mid\text{if }p\text{ then }G\text{ else }G,

read as a partial function on states like FKF_K: runs of operations become a sequence, repeated runs one body G(j)G(j) under an index, and a loop a for over its body. For the GEMM of Figure 2, the inner loop’s twelve program-counter cases of ldmatrix and mma become one body run four times, and the KK-loop sixteen trips over it. GKG_K calls the same sem⁡t\operatorname{sem}_{t} as the flat model; only indexing and sequencing change, and a for can be treated by induction, one iteration at a time.

Verifying the segmentation. The segmentation was written by an agent, so by our own rule it is not trusted; the stage ends with a Lean-checked obligation.

OBLIGATION 2 (SEGMENTATION). SEG⁡(K)\operatorname{SEG}(K): for every σ\sigma with In⁡I(σ,x)\operatorname{In}_{I}(\sigma,x), FK(σ)=GK(σ)F_K(\sigma)=G_K(\sigma).

This is an equality of partial functions, both faulting or both reaching the same state, proved phase by phase by induction on the folded indices from the lemmas the translator prepared (§ 4.1). If the segmentation is wrong, SEG⁡(K)\operatorname{SEG}(K) fails, at no cost in trust.

Proof loop. An agent writes a proof, Lean checks it, and the errors go back to the agent; a proof passes only if it compiles without sorry and #print axioms shows only Lean’s standard axioms. When the attempts run out, a separate agent names the cause, a hard proof, a stuck agent, poorly chosen segments, or a wrong kernel, and the loop continues, restarts, redoes the segmentation, or returns the diagnosis to the kernel generator. This analysis only decides what to try next; whether a kernel is accepted, only Lean decides.

Stage 3: Segment-wise verification loop. The same loop now proves the segment-level model against the Torch semantics, the one place where the formalized module enters.

OBLIGATION 3 (SEGMENT-WISE EQUIVALENCE). EQ⁡(K,S)\operatorname{EQ}(K,S): for every xx and σ\sigma with In⁡I(σ,x)\operatorname{In}_{I}(\sigma,x), there is a σ′\sigma' with GK(σ)=σ′G_K(\sigma)=\sigma' and Out⁡I(σ′)=⟦S⟧(x)\operatorname{Out}_{I}(\sigma')=\llbracket S\rrbracket(x).

Segment by segment, the agent shows what each phase and each for body leaves in the state, and induction carries it across the iterations. Together the obligations give Equation (1), the theorem of Figure 2b: EQ⁡(K,S)\operatorname{EQ}(K,S) supplies σ′\sigma' with GK(σ)=σ′G_K(\sigma)=\sigma' and Out⁡I(σ′)=⟦S⟧(x)\operatorname{Out}_{I}(\sigma')=\llbracket S\rrbracket(x), SEG⁡(K)\operatorname{SEG}(K) makes it FK(σ)=σ′F_K(\sigma)=\sigma', and Stage 1 makes that ⟦K⟧M(σ)=σ′\llbracket K\rrbracket_M(\sigma)=\sigma'.

Statements. The three stages prove a statement that no agent wrote, which is what the soundness claim rests on: a proof of the wrong statement proves nothing. Its premise and extractor are two definitions fixed once in MM, applied to the task’s signature and launch:

In⁡I:=Pre⁡M(sig⁡,launch⁡),Out⁡I:=Ext⁡M(sig⁡).\operatorname{In}_{I}:=\operatorname{Pre}_{M}(\operatorname{sig},\operatorname{launch}), \qquad\operatorname{Out}_{I}:=\operatorname{Ext}_{M}(\operatorname{sig}).

Pre⁡M\operatorname{Pre}_{M} places every input buffer under its layout, keeps buffers apart and aligned, binds every scalar and dimension, and fixes the launch geometry; Ext⁡M\operatorname{Ext}_{M} reads every output buffer under its layout. The signature has one entry per kernel argument, a buffer with its row, element type, shape, and strided layout, or a scalar or dimension bound to the specification or pinned; it is the list the task’s tests launch with, checked against the kernel’s entry point (Appendix § 9.8). The theorem quantifies over the kernel’s parameters (base addresses, strides, scalars), every state satisfying the premise, and every input, and the premise is proved satisfiable once for every signature, so no statement holds vacuously.

What We Still Trust

Trust cannot be removed completely. What LARK does is narrow it, from the whole kernel to a short, fixed list, and report the list with every result. A certificate is

C=(ΠM,ΠK,κ⃗,π),ΠK=(sig⁡,launch⁡),C=(\Pi_M,\Pi_K,\vec{\kappa},\pi), \qquad\Pi_K=(\operatorname{sig},\operatorname{launch}),

with the premises Π=ΠM∪ΠK\Pi=\Pi_M\cup\Pi_K of § 3, the fuels κ⃗\vec{\kappa} the fold runs under (data, not premises: exhausting one is a fault the proof rules out), and a Lean-checked proof

π⊢∀p⃗ σ x. Pre⁡M(sig⁡,launch⁡)(p⃗,σ,x)⇒RF⁡(K)∧∃σ′. (run⁡Kκ⃗(σ)=σ′∧Ext⁡M(sig⁡)(p⃗,σ′)=⟦S⟧(x)),\pi\vdash\forall\vec{p}\,\sigma\,x.\ \operatorname{Pre}_{M}(\operatorname{sig},\operatorname{launch})(\vec{p},\sigma,x)\Rightarrow\operatorname{RF}(K)\wedge\exists\sigma'.\ (\operatorname{run}^{\vec{\kappa}}_{K}(\sigma)=\sigma'\wedge\operatorname{Ext}_{M}(\operatorname{sig})(\vec{p},\sigma')=\llbracket S\rrbracket(x)),

which with the reduction result of § 5 is K≡M,ISK\equiv_{M,I}S. The two parts of Π\Pi differ in what they are and how they are trusted.

ΠM\Pi_M is kernel-independent, the statement that MM is faithful to the hardware H\mathcal{H} of § 3: the idealizations of MM (exact arithmetic as scope, the fold of Equation (2) with the reduction result of § 5, sem⁡\operatorname{sem} as measured against the hardware, the Lean formalization of the Torch module, and Lean itself (full list in Appendix § 9.13). The Torch formalization is the one agent-written artifact no proof covers: it is written independently of kernels, auditable on its own, and tested ahead of time against the module.

ΠK\Pi_K is kernel-specific and small: the signature and the launch, which come from the task, not from the kernel or an agent (§ 5). What remains to believe is that they describe the task, which the report states by quoting them.

Target Lang.MetricGLM 5.3GLM 5.3 FlashDeepSeek V4.1 FlashGPT-6 Luna
PTXpass rate83%58%25%25%
PTXinput tokens (M)314.53714.60148.47445.93
PTXoutput tokens (M)8.0510.541.933.26
CUDApass rate75%50%25%25%
CUDAinput tokens (M)280.49626.5380.45476.20
CUDAoutput tokens (M)6.189.091.123.42
HIPpass rate83%50%25%25%
HIPinput tokens (M)312.21773.96156.15289.17
HIPoutput tokens (M)7.1510.591.861.89

Table 2. KernelCraft Level 1 results per target language and model: pass rate over the twelve tasks, and mean input and output tokens (millions) over the proven tasks, since a failed run spends to its budget. Per-task results in Appendix § 9.§ 4.1.

Floating-point behavior lies outside Π\Pi: no bound ∣Kfp(x)−⟦S⟧(x)∣≤ε|K_{\mathrm{fp}}(x)-\llbracket S\rrbracket(x)| \le\varepsilon is proved for the kernel KfpK_{\mathrm{fp}} as the hardware rounds it, and LARK claims nothing about rounding, overflow, or quantization; a GPU test against the Torch module answers that question, at a tolerance the report states beside the theorem.

Everything else is proved for the kernel at hand or guarded by refusal: RF(K)\mathrm{RF}(K); the absence of faults, convergence, and termination within the fuel, which together are [K]M(σ)↓[K]_{M}(\sigma)\downarrow; and SEG(K)\mathrm{SEG}(K) and EQ(K,S)\mathrm{EQ}(K,S). A theorem proved once in MM assembles these into π\pi. Each run exports the certificate as a standalone Lean project that re-checks without LARK (Appendix § 9.12), with a trusted-assumption report: ΠM\Pi_M as a fixed list of statements, ΠK\Pi_K quoted, the refusals that applied, and the sites where a named constant was read as exact. Trust is placed only where the report says it is.

Experiments

We show that LARK verifies most of the kernels a generation harness writes, each model stopping at a fixed rung of proof difficulty (§ 6.1); that a certificate is robust, rejecting single-site mutants (§ 6.2); and that the method holds on production kernels, where it finds a real race (§ 6.3). Ablations of the failure analysis and the segmentation (§ 6.4) and the takeaways (§ 6.5) close the section.

Setup. We evaluate LARK on KernelCraft (Nie et al. [27]), a recent benchmark of GPU kernel-generation tasks, each with a Torch reference module and tests, which gives LARK its specifications and the tests their baseline: the twelve Level 1 tasks, single operators, on PTX, CUDA, and HIP; and five Level 2 tasks, fused operators (FFN, SwiGLU, RoPE, FlashAttention, GQA), on PTX (Table 6). To measure verification alone, one kernel is generated once and pinned for every task and language, and every model verifies the same kernel. The verification agents are four small models on Level 1 (GLM 5.3, GLM 5.3 Flash, DeepSeek V4.1 Flash, GPT-6 Luna) and Opus 5.5 on Level 2, with GLM 5.3, the strongest of the four, as the comparison. Each verification runs under a cap on dialogue rounds per proof step and a spending ceiling, both read off preliminary runs (Appendix § 9.§ 2). Metrics. A verification passes when it ends in a certificate that Lean accepts with its standard axioms only, and the pass rate is the share of tasks that pass; cost is the input and output tokens of the verification. The numeric screen and the latency measurements use an H100 80GB for PTX and CUDA and an MI300X for HIP.

KernelCraft LevelTasks
Level 1: Primitive Operationssilu, relu, gelu, softmax, layernorm, rmsnorm, gemv, gemm, batchmatmul, linear, conv2d, depthwise_conv
Level 2: Composite Operationsrope, ffn, swiglu, flash_attn, gqa

Table 6. The evaluated KernelCraft tasks by level.

Verifying Generated Kernels: Difficulty Set by Proof Shape, Not Language

The tasks form a ladder of proof difficulty, and each model climbs to a fixed height. Table 2 gives the pass rates and token costs on Level 1 and Table 3 the results on Level 2 (per-task outcome details in Appendix § 9.§ 4.1). On all three languages every model proves the elementwise kernels; the two GLM models also prove the row-wise normalizations (GLM 5.3 stops at its spending ceiling on LayerNorm on HIP); only GLM 5.3 proves the tensor-core and convolution kernels; no model proves DepthwiseConv, and Batch-Matmul is proved only on HIP, where the pinned kernel runs one 64-lane wavefront per block instead of four warps; and only Opus 5.5 proves the fused Level 2 kernels (pass rate and cost against model size in Appendix § 9.4.6). Each step up adds a kind of obligation, an induction over a loop, a convergence fact at a cut, a fragment-layout lemma, and a model that cannot close one kind fails every kernel that needs it. The two kernels that stop every model on PTX and CUDA stop them on difficulty alone: no statement is false, no verdict blames the kernel, no construct is refused, and every model stops on the same proof, one warp’s tensor-core loop of 16 or 26 collective steps carried through the lane, warp, and block folds (Appendix § 9.§ 6). Proof cost follows the same shape: over the 116 PTX and CUDA runs it correlates with the length of the compiled program (Spearman 0.61), while the length barely predicts the number of agent turns (0.17), a turn being one proof attempt and its Lean check, so a long kernel costs more per turn, not more attempts (Appendix § 9.4.4). Every failure is a proof that ran out of rounds or budget, and on PTX and CUDA the two equivalence proofs take over 90% of a run’s tokens (Appendix § 9.§ 5.1).

ModelMetricFFNSwiGLURoPEFlashAttnGQATotal
Opus 5.5pass✓✓✓✓✓100%
Opus 5.5input token (M)78.2066.6015.50172.50203.90107.34
Opus 5.5output token (M)1.431.010.372.773.091.73
GLM 5.3pass✗✗✓✗✗20%
GLM 5.3input token (M)(459.60)(512.30)71.90(214.10)(611.60)373.90
GLM 5.3output token (M)(9.13)(15.96)2.70(4.49)(14.16)9.29

Table 3. KernelCraft Level 2 results on PTX: a check mark is a certificate; tokens are input and output tokens (millions), in parentheses for runs that failed or stopped at their budget and left out of the Total average.

The target language matters less than the kernel, and the lower level is not the harder one. Every model proves nearly the same set of kernels on PTX, CUDA, and HIP: the pass rates of a model differ by at most one task across the three languages, and the rung at which it stops is the same on each. The few cells that differ turn on the shape of the proof, not on the language. GEMV is the clearest case: the two GLM models prove it on PTX but not on CUDA, where the theorem is identical and every failure-analysis verdict was “theorem true, proof hard”, but the kernel compiles to ten segments with two block barriers inside the KK-loop against one segment with one barrier on PTX, so the PTX proof is shorter (29 agent turns against 48 for GLM 5.3). The shorter proof does not come from a weaker kernel: the verified PTX kernels are faster than the CUDA ones on half of the Level 1 kernels and within 5% of them on the rest, and 1.8 times faster on GEMV (Appendix § 9.4.10).

Robustness: Rejecting Semantics-Breaking Mutants

To test that a certificate is robust, we mutate verified kernels and ask whether LARK can correctly reject them. Table 4 lists the five mutation rules and the results; each mutant is a verified kernel with one change, on ReLU, Softmax, and GEMM in CUDA, PTX, and HIP. We test one semantics-breaking mutant per applicable rule and kernel; ReLU has no barrier, so R3 applies only to Softmax and GEMM. All runs use GLM 5.3 with the numeric screen disabled.

IDRuleChangeCUDAPTXHIP
R1ArithmeticOne operator or immediate (+ for −, a constant)3/33/33/3
R2Load/storeOne address, buffer, or stored value3/33/33/3
R3BarrierOne barrier removed or moved one statement2/22/22/2
R4RegisterOne variable or source register replaced at a use3/33/33/3
R5Loop rangeOne loop bound, increment, or stride3/33/33/3
Total14/1414/1414/14

Table 4. Mutation testing: per rule and target language, the mutants LARK rejects out of those tested. Every mutant is rejected; R3 has two mutants per language because ReLU has no barrier.

LARK rejects all 42 mutants: 11 at the translator’s static checks, 10 by a refuted race-freedom obligation, 18 by the failure analysis showing that the kernel computes a different function from the specification, and 3 by a statement Lean refuses because the mutant needs a premise the task’s signature does not give (Appendix § 9.4.11).

Verifying Production Kernels

We further evaluate LARK on ten production kernels adapted from vLLM (Kwon et al., [19]), SGLang (Zheng et al., 2024), FlashInfer (Ye et al., 2025), llm.c (Karpathy, [16]), and flash-attention-minimal (Kim, [17]): nine verify, and the tenth is rejected for a data race (Table 5). Each kernel enters the pipeline through small recorded rewrites, most of which reshape the code without changing what it computes; nine of the ten also carry a semantic departure, such as a 64-bit index read as 32 bits, and each theorem is about the kernel with its departures, all listed in Appendix § 9.14. The five with the simplest shapes, the rejected one among them, ran with GLM 5.3, the five that fuse stages or run several phases with Opus 5.5.

Metricvllm-silu-and-mulvllm-rms-normsglang-rmsnormvllm-rotary-embeddingllmc-softmax-forward
model usedGLM 5.3GLM 5.3GLM 5.3GLM 5.3GLM 5.3
verified✓✓✓✓✗
input tokens (M)192.90294.00529.00152.80(0)
output tokens (M)4.568.1212.234.44(0)
Metricsglang-fused-add-rmsnormflashinfer-rmsnormvllm-fused-qknorm-5flash-attnvllm-awq-gemm
model usedOpus 5.5Opus 5.5Opus 5.5Opus 5.5Opus 5.5
verified✓✓✓✓✓
input tokens (M)70.4062.50146.20117.20223.20
output tokens (M)0.991.191.872.002.86

Table 5. Verification of the ten production kernels (adapted as Appendix A.14 records), each in its library’s language (CUDA, except vllm-awq-gemm on PTX) by the model in its column. A check mark is a certificate; tokens are input and output tokens, in millions.

The rejected kernel shows what a certificate catches that random-input tests do not. llmc_softmax_forward reads, in its last pass, a neighbouring output cell that another thread of the same block writes in the same pass, with no barrier between. The value read is discarded, so the race is benign and no test sees it. The translator cannot derive the footprint of the store, so the obligation falls to the agent, which finds a counterexample instead, two threads of one block storing and loading the same cell of out in the same phase, confirmed by the independent second opinion. The kernel is rejected, since the obligation is over footprints, not over whether a value read is used (Appendix § 9.14).

Ablations: Failure Analysis and Segmentation

Two parts of LARK are heuristics outside the trust boundary, and the runs show that both earn their place. The failure analysis, an analyst that names a cause after a failed round, a falsity probe, and an independent second analyst, only chooses what the loop tries next. It is cheap, and it never cut off a proof that was going to succeed. Over the Level 1 runs on PTX and CUDA, the Level 2 runs, and the production kernels (Appendix § 9.4.9), the analysis costs 0.7% to 4.7% of a model’s input tokens and ended ten dialogues before their ceiling, and in the preliminary runs, where it ran without acting, no proof closed after the point where it would have stopped. It is fallible: it called a correct kernel buggy three times, each refuted by the second analyst; in all, the second analyst disputed eleven of the twenty stopping verdicts it reviewed. None of this touches soundness, since a wrong verdict can only end a run early.

On a complicated kernel the segmentation saves more than its own equivalence proof costs. We conducted an ablation that proves the specification directly against the flat model, with no segmentation and no first equivalence, on FlashAttention on PTX with Opus 5.5. The direct proof closed at 220M input tokens over 20 turns, against 120M over 11 for the second equivalence with the segmentation; with the 49M tokens of the segmentation and its equivalence counted, the direct run still used 29% more and crossed a ceiling the default run finished under, because without segments the agent re-proves the same loop body at every program counter (Appendix § 9.4.8).

Discussion

The experiments point to three properties of the framework.

1) Automated formal verification keeps pace with generation. GLM 5.3 certifies 10 of the 12 Level-1 kernels on PTX and on HIP (9 on CUDA) and Opus 5.5 every Level-2 kernel with no human in the loop, which shows that agentic formal verification of GPU kernels is feasible, and the cost per proof falls as the models improve.

2) A robust pipeline with soundness guaranteed. Lean supplies the soundness: a certificate exists only when every obligation is proved, so no agent can talk its way to one. LARK is also robust in practice: wrong segmentations and wrong analyst verdicts ended as failed proofs, semantics-breaking mutants are rejected (§ 6.2), and the one production kernel with a race was rejected while the nine correct ones were certified (§ 6.3).

3) A narrowed trust boundary. What a certificate rests on is independent of the kernel: the machine model, the operation semantics measured against the hardware, and the premise and extractor definitions are fixed and checked offline, before any kernel is seen, the specification is formalized once per task and tested, and everything about the kernel itself is proved. LARK is thus a step toward verifiable code generation in the agentic era: the generator stays untrusted, agents write the proofs, and the certificates are sound.

Related Work

Kernel generators and benchmarks [28, 6, 27] (Ye et al. 2026) judge a kernel correct when its outputs match a reference on test inputs, a check that generated kernels have been shown

to exploit [20] (Woo et al. 2025). Stricter tests [31, 32] catch more errors, but on every untested input the kernel’s correctness is still assumed. Earlier formal tools either prove only race freedom [8] or rely on human proofs for each program [14, 15].

Two recent verifiers have been applied to LLM-generated kernels. Volta [12] decides equivalence between a PTX kernel and a reference PTX kernel over the reals. Its specification is thus itself a low-level kernel that must be correct, its decision procedure is not mechanically verified, and its evaluation checks only the first pair of thread blocks, which covers the full grid only if every block behaves alike. ProofWright [9] has LLM agents annotate CUDA kernels for the VerCors verifier [3], which proves memory and thread safety, but proves equivalence only for element-wise kernels with one output per thread, relying on manual preprocessing of kernels and hand-checked LLM annotations.

In both systems, what must be trusted includes assumptions about, or manual work on, the kernel itself. LARK’s trust boundary is instead fixed before any kernel is seen: for each kernel, it proves in Lean equivalence to the task’s Torch module under exact arithmetic together with race freedom, absence of faults, and termination, or rejects the kernel. Appendix § 9.§ 1 discusses further related work.

Conclusion

We propose LARK, a framework that verifies LLM-generated GPU kernels against their Torch specifications in Lean, with the trust boundary moved off the kernel. It gives generated code the check it lacked: one that keeps pace with generation and means something when it passes. The machine model and the operation semantics are fixed and checked once per target language; everything about the kernel, race freedom above all, is proved per kernel or the kernel is rejected; and agents may write the segmentations and the proofs because Lean checks every line, so a wrong agent output is a failed proof, never a wrong theorem. GLM 5.3 certifies 10 of the 12 Level-1 kernels and Opus 5.5 all five fused Level-2 kernels, and nine of ten adapted production kernels verify. Then, tenth, a softmax kernel from llm.c, is rejected for a real data race present in the shipped code, a bug invisible to input–output testing because the racing value is discarded, which LARK located from the code alone.

Limitations

LARK’s guarantee is bounded in three ways. Arithmetic is idealized: floats and integers are exact, +∞+\infty and NaN are faults, and the theorem says nothing about rounding, overflow, accumulation order, or the precision of approximate instructions; floating-point behavior is tested, not proved (§ 5.1). Concurrency is phase-structured: blocks that communicate within a phase, benign races, and warps that halt early are rejected. The operation set is the pinned tables: asynchronous operations (TMA, wgmma, mbarrier), atomics, partial masks, bf16, 8-bit types, non-polynomial addresses, and multi-dimensional blocks are refused (Appendix § 9.9). None of these changes the method; each costs a pinned definition or a lemma emitter, and retargeting to a new language is manual (Appendix § 9.§ 7).

Appendix

Related Works

Kernel generation and test-based checking. Existing LLM kernel generation across target languages, from CUDA to close-to-metal assembly ([28, 6, 27] (Ye et al. 2026)), checks correctness by comparing a kernel’s outputs with a reference implementation on sampled inputs. Such testing has proved unreliable: kernels that pass KernelBench’s checks have achieved fake speedups of 50–120× by exploiting the evaluation harness, and excluding the affected tasks reduces the reported aggregate speedup from 3.13× to 1.49× [20]. Reward hacking is likewise a central obstacle for generators trained with reinforcement learning (Woo et al., 2025). Stricter test suites, contract-based checks, and metamorphic testing [31, 32] (Xiao et al. 2022) catch more errors, but their results remain empirical: a kernel that passes them has been checked only on the inputs that were tried, and its correctness on every other input is assumed. The kernel therefore remains inside the trust boundary.

Formal verification and equivalence checking. Translation validation [29, 26, 23], equivalence checking of program transformations [30], and verified compilers [21] relate a program to the source from which it was derived. These techniques do not apply directly to LLM-generated kernels, which have no such source and are specified only by a high-level module in a different language. Interactive proofs against a formal ISA semantics [14, 15] exclude the kernel from the trust boundary, but require substantial manual effort for each program. Conversely, GPUVerify [8] is fully automatic but establishes only the absence of data races and barrier divergence; since it does not relate a kernel to its specification, the kernel’s functional behavior remains within the trust boundary. LARK combines both properties: it is automatic, treats race freedom as one proof obligation among several, and additionally proves that the kernel is equivalent to its specification.

LLM-driven proving and its failure modes. LLM agents can now write machine-checked proofs [13]. A checked proof, however, is only as trustworthy as the statement it proves, and statements are where errors concentrate: audits of Lean benchmarks find missing hypotheses, simplified problems, and vacuous theorems [2], and models asked to annotate a program for verification have been observed to modify the program instead [5]. When the agent that writes the proof also writes the statement, the statement lies inside the trust boundary, and so does the agent. LARK keeps agents out of the per-kernel trust boundary: the theorem is fixed by the task before the kernel is seen, and Lean checks every proof an agent writes, so an agent’s error about the kernel can only cause a proof to fail, never a certificate for the wrong theorem. The one agent-written artifact that remains trusted, the specification formalization, is per task, tested, and reported as such (§ 5.1).

Formal verification of LLM-generated GPU kernels. Two recent verifiers have been applied to LLM-generated kernels. Volta [12], a general equivalence checker, uses symbolic execution to decide equivalence beնդ unerquicklich tween a PTX kernel and a reference PTX kernel over the reals. Its specification is thus itself a low-level kernel that must be correct, its decision procedure is not mechanically verified, and its evaluation checks only the first pair of thread blocks, which covers the full grid only if every block behaves alike. ProofWright [9] has LLM agents annotate CUDA kernels for the deductive verifier VerCors [3], which proves memory and thread safety, but proves equivalence only for elementwise kernels with one output per thread, relying on manual preprocessing of each kernel and hand-checked LLM annotations. LARK instead checks the kernel against the task’s Torch module, fixes its trust boundary before any kernel is seen, and proves in Lean equivalence under exact arithmetic, together with race freedom, absence of faults, and termination, or rejects the kernel.

Experiment Setup Details

Table 6 lists the evaluated tasks by KernelCraft level, Table 7 the round caps and spending ceilings per model, and Table 8 the kernels by the highest cut level of their phase structure.

Highest cutCore setLibrary kernels
Nonerelu, silu, gelu, conv2d, ropevllm_silu_and_mul, vllm_rotary_embedding
Warp—vllm_fused_qknorm_rope
Blocksoftmax, layernorm, rmsnorm, gemv, gemm, linear, batchmatmul, depthwise_conv, flash_attn, gqasglang_rmsnorm, vllm_rms_norm, flashinfer_rmsnorm, sglang_fused_add_rmsnorm, llmc_softmax_forward, fam_flash_attn, vllm_awq_gemm
Gridffn, swiglu—

Table 8. The evaluation kernels by the highest cut level of their phase structure (§ 4.1): the 17 kernels of the core set (KernelCraft Levels 1 and 2) and the 10 production kernels. A kernel with no cut runs as one phase; a warp-collective operation alone does not add a level.

Preliminary runs. The round caps of Table 7 were read off preliminary verify-only runs in which every failed round continued the same dialogue, under a cap of 15 rounds, while the failure analyst still ran and recorded what the normal gate would have done. A round closes an obligation when the agent’s proof of that round discharges one of the open lemmas or goals of the equivalence, and the rule is a high percentile of the last closing round, plus one round of margin. DeepSeek V4.1 Flash ran GEMM on PTX eight times, none proving the first equivalence, with last closing rounds at 1, 5, 8, 10, 11, 12, 23, and 23; the 75th percentile gives a cap of 16, which GPT-6 Luna and GLM 5.3 Flash, without preliminary runs of their own, take by decision. GLM 5.3 ran GEMM on PTX three times and proved both equivalences each time, with last closing rounds 1, 1, and 3 for the first and 5, 7, and 6 for the second, a cap of 8. Opus 5.5 ran GQA on PTX once and closed the second equivalence in round 9, a cap of 10. The spending ceilings are the amounts at which these runs were stopped. None of these runs is an evaluation cell.

Table 9 gives the configuration of each evaluated task in the notation of KernelCraft; every task runs at the largest of the benchmark’s five configurations.

Task (parameters)Configuration
Level 1
SiLU, ReLU, GELU (nn)(16384)
Softmax, LayerNorm, RMSNorm (nn)(16384)
GEMV (MM, NN)(512, 1024)
GEMM (MM, KK, NN)(64, 256, 512)
BatchMatmul (bb, MM, KK, NN)(32, 64, 256, 512)
Linear (nn, hinh_{\mathrm{in}}, houth_{\mathrm{out}})(64, 256, 512)
Conv2D (HH, cinc_{\mathrm{in}}, coutc_{\mathrm{out}}, kk)(8, 32, 8, 3)
DepthwiseConv (HH, cc, kk)(16, 32, 5)
Level 2
FFN, SwiGLU (nn, hh, hih_i)(64, 256, 1024)
RoPE (ss, dheadd_{\mathrm{head}})(256, 128)
FlashAttention (ss, hh)(128, 256)
GQA (ss, hh, nhn_h, nkvn_{kv})(128, 512, 8, 2)

Table 9. Configuration of each evaluated task, in the notation of KernelCraft ([27]): every task runs at the largest of the benchmark’s five configurations, and all tensors are FP16. nn = number of elements (input tokens), MM, KK, NN = matrix dimensions, bb = batch size, hinh_{\mathrm{in}}, houth_{\mathrm{out}} = input and output features, hh = hidden size, hih_i = intermediate size, ss = sequence length, nhn_h = attention heads, nkvn_{kv} = key-value heads, dheadd_{\mathrm{head}} = head dimension, HH = spatial size (height = width), cinc_{\mathrm{in}}, coutc_{\mathrm{out}} = input and output channels, cc = channels, kk = kernel size.

Experiment Configuration

Experiment configurations are detailed in Table 10.

FlagDeepSeek V4.1 FlashGPT-6 LunaGLM 5.3 FlashGLM 5.3Opus 5.5What it controls
--modeldeepseek-v4.1-flash-1017gpt-6-lunaglm-5.3-flashglm-5.3opus-5.5Model of the verification agents
--isaPTX, CUDA, HIPPTX, CUDA, HIPPTX, CUDA, HIPL1: all three; L2: PTX; library: CUDAL2: PTX; library: CUDA, PTXTarget language of the run
--kernelL1L1L1L1, L2, production librariesL2, production librariesTask verified (Table 6)
--backward-effortxhighxhighdefaultdefaultxhighReasoning effort of every verification agent
--proof-effortxhighxhighdefault (max)default (max)xhighEffort of the two proof agents
--other-effortdefault (xhigh)default (xhigh)default (high)default (high)default (xhigh)Effort of the statement, review, and diagnosis agents
--max-auto-tries1616168 (L1, library); 16 (L2)10Round cap per proof
--max-usd505075100100 or 200 by taskSpending ceiling per verification

Table 10. Table 10. Configuration of the verification runs, per model. Every run passes --verify-only, so the kernel is the registry’s pinned program for its task and language and the generation flags are unused. “default” means the flag is not passed. Round caps and spending ceilings are per verification of one kernel; the ceilings are in dollars because they are what the runs were stopped at, and their derivation from the preliminary runs is in Table 7. The last column says what each flag controls; the settings shared by every run are listed below the per-model rows.

Shared by every run. --ask-on-max-usd on (stop at the ceiling rather than continue); --repeats 2 (pipeline restarts allowed); --translation-attempts 10 (attempts per segmentation or statement step); --proof-attempts 10 (attempts per proof step); --check-attempts 3 (attempts per review); --diagnosis-attempts 3 (attempts per failure analysis); --lean-timeout 150 s (time limit per Lean check); --max-lean-tool-calls 40 (Lean checks per agent turn); --numeric-trials 6 and --numeric-probes 4 (random inputs of the numeric screen); all static translator checks on; --racefree-fallback on (the agent proves race freedom where no lemma is generated); --flat-model off (direct proof without segmentation, ablation only).

Additional Results

Unless a subsection says otherwise, the analyses below are over the PTX and CUDA runs; the HIP runs enter only the per-task table and the latency measurements.

Per-Task Results on Level 1

Table 11 gives, for every model, language, and task, the outcome and the input and output tokens of the verification. A run ends “pass” with a certificate, “budget” at its spending ceiling, and “fail” when the agent gave up or the round cap was hit.

ModelTarget Lang.MetricReLUSiLUGELUSoftmaxLayerNormRMSNormGEMVGEMMLinearBatchMatmulConv2DDepthwiseConvTotal
GLM 5.3CUDApass/fail/budgetpasspasspasspasspasspassbudgetpasspassbudgetpassbudget75%
input tokens (M)44.6761.6187.60332.71291.45481.23(700.51)389.51430.82(549.06)404.79(562.16)280.49
output tokens (M)1.781.782.387.976.325.93(15.60)8.9511.25(13.53)9.23(13.47)6.18
PTXpass/fail/budgetpasspasspasspasspasspasspasspasspassbudgetpassbudget83%
input tokens (M)119.2077.3056.50391.20483.20288.60481.00277.70508.70(752.70)461.90(616.80)314.53
output tokens (M)2.662.771.9110.6311.506.6813.798.0910.54(15.33)11.94(15.93)8.05
HIPpass/fail/budgetpasspasspasspassbudgetpasspasspasspasspasspassbudget83%
input tokens (M)158.8483.7999.16229.01(692.63)231.08576.31422.98414.93455.50450.52(581.50)312.21
output tokens (M)4.332.534.626.45(17.44)7.9312.3111.229.549.932.66(15.53)7.15
GLM 5.3 FlashCUDApass/fail/budgetpasspasspasspasspasspassbudgetbudgetbudgetbudgetbudgetfail50%
input tokens (M)221.00281.60248.70669.40457.401881.10(1981.50)(2052.50)(1901.70)(2036.30)(1811.90)(1366.40)626.53
output tokens (M)3.135.104.7410.096.9924.48(24.19)(25.26)(23.66)(27.72)(23.01)(20.11)9.09
PTXpass/fail/budgetpasspasspasspasspasspasspassfailfailbudgetfailbudget58%
input tokens (M)184.70260.80231.10792.901455.901219.50857.30(1408.60)(1486.40)(1974.40)(1531.10)(1891.60)714.60
output tokens (M)3.144.053.5111.9120.9416.3813.85(15.64)(21.43)(30.21)(25.58)(24.16)10.54
HIPpass/fail/budgetpasspasspasspasspasspassbudgetbudgetbudgetbudgetbudgetbudget50%
input tokens (M)240.88271.10292.31841.58990.152007.71(1019.44)(1638.08)(1880.69)(1783.35)(1477.32)(1871.22)773.96
output tokens (M)3.414.554.0812.0414.3125.13(15.53)(15.42)(20.43)(29.31)(23.78)(19.54)10.59
DeepSeek V4.1 FlashCUDApass/fail/budgetpasspasspasspassfailfailfailfailfailfailfailfail25%
input tokens (M)95.3966.8479.12(458.90)(780.60)(711.59)(528.54)(706.41)(744.72)(550.34)(403.48)(574.90)80.45
output tokens (M)1.190.961.20(7.63)(10.80)(9.62)(6.92)(10.27)(11.85)(8.65)(6.11)(8.16)1.12
PTXpass/fail/budgetpasspasspassfailfailfailfailfailfailfailfailfail25%
input tokens (M)224.58101.24119.58(368.11)(197.33)(383.49)(367.04)(653.25)(458.75)(215.81)(456.24)(430.42)148.47
output tokens (M)2.601.541.64(4.46)(3.50)(5.06)(5.46)(9.09)(7.30)(3.05)(6.85)(6.21)1.93
HIPpass/fail/budgetpasspasspassfailfailfailfailfailfailfailfailfail25%
input tokens (M)241.67133.7193.07(471.13)(831.19)(741.90)(462.83)(688.31)(691.33)(390.18)(501.33)(812.59)156.15
output tokens (M)1.982.011.59(6.32)(10.91)(8.91)(5.53)(10.10)(8.82)(2.98)(7.03)(9.03)1.86
GPT-6 LunaCUDApass/fail/budgetpasspasspassfailfailfailfailfailfailfailfailfail25%
input tokens (M)690.80316.40421.40(638.30)(707.80)(1243.20)(511.80)(1171.60)(596.90)(660.10)(689.10)(1152.50)476.20
output tokens (M)4.912.402.95(4.38)(5.30)(8.50)(4.27)(9.01)(4.17)(4.90)(5.12)(7.89)3.42
PTXpass/fail/budgetpasspasspassfailfailfailfailfailfailfailfailfail25%
input tokens (M)366.30401.70569.80(1144.90)(1281.40)(1494.60)(547.50)(1259.00)(1146.20)(1052.00)(932.00)(880.90)445.93
output tokens (M)2.303.164.31(7.77)(8.54)(9.66)(4.08)(8.60)(7.94)(7.48)(7.30)(5.78)3.26
HIPpass/fail/budgetpasspasspassfailfailfailfailfailfailfailfailfail25%
input tokens (M)345.00286.00236.50(780.39)(798.14)(1339.64)(580.62)(1150.13)(513.32)(710.28)(842.19)(1451.10)289.17
output tokens (M)2.132.061.48(4.71)(7.71)(9.05)(4.31)(8.33)(6.95)(6.93)(6.20)(8.68)1.89

Table 11. Verification of the twelve KernelCraft GPU Level 1 tasks, per model and target language. A run ends “pass” with a certificate, “budget” at its spending ceiling, or “fail” at its round cap or by an agent failure. Tokens are input and output tokens of the verification, in millions; the “Total” column gives the pass rate and the average tokens over the proven kernels. A count in parentheses belongs to a run that did not prove its kernel, reflects the budget it was given rather than the cost of a proof, and is left out of the average.

Refusal Census

Over the 116 PTX and CUDA verifications of the three subsets, no correct kernel was refused by scope: every kernel that passed the numeric screen compiled into the model and reached the proof loop. Outcomes on Level 1, per model (proved / budget stop / agent failure out of 24): GLM 5.3 19 / 5 / 0; GLM 5.3 Flash 13 / 7 / 4; GPT-6 Luna 6 / 0 / 18; DeepSeek V4.1 Flash 6 / 0 / 18. On Level 2 (PTX): Opus 5.5 5 / 0 / 0; GLM 5.3 1 / 3 / 1. Library: 10 / 0 / 0.

Cost per Stage

Each verification splits into a static part (the translator’s compile and its Lean modules, the certificate), the agent steps (segmentation, statements, the two proofs, reviews, and the diagnosis), and Lean checks inside the proof loop. Table 12 gives the tokens per stage. On Level 1 the two equivalence proofs take 95 to 99% of a run’s tokens (median per model), the diagnosis 0.7 to 4.4%, and the segmentation, statement, and review steps at most 0.3% each; the segmentation proof dominates for the three weaker models, which rarely reach the equivalence proof, and the equivalence proof dominates for GLM 5.3 and on Level 2. The static part takes 36 to 157 seconds per run (maximum 352); Lean inside the loop 18 to 60 minutes per run for the small models and 6 to 8 for Opus 5.5.

SetModelSegmentation proof SEG(KK)Equivalence proof EQ(K,SK,S)DiagnosisRace-freedom fallbackOther steps
Level 1 (PTX, CUDA)DeepSeek V4.1 Flash271.21 (68.7%)164.53 (36.2%; 15 of 24)14.85 (3.6%)—≤ 0.2%
GPT-6 Luna646.92 (93.6%)267.78 (38.5%; 9 of 24)35.95 (4.4%)—≤ 0.2%
GLM 5.3 Flash719.16 (55.1%)454.39 (48.3%; 21 of 24)10.34 (0.7%)—≤ 0.1%
GLM 5.3116.39 (42.8%)186.60 (54.8%)4.12 (1.3%)—≤ 0.3%
Level 2 (PTX)GLM 5.3103.96 (29.6%)388.21 (72.5%; 4 of 5)3.29 (1.0%)—≤ 0.2%
Opus 5.516.26 (27.2%)60.76 (69.4%)2.71 (1.4%; 2 of 5)—≤ 1.0%
ProductionGLM 5.3106.04 (47.7%; 4 of 5)137.63 (49.8%; 4 of 5)3.48 (1.3%; 4 of 5)10.30 (100%; 1 of 5)≤ 0.8%
Opus 5.521.27 (25.6%)56.03 (53.5%; 3 of 5)0.76 (0.7%; 4 of 5)48.81 (23.2%; 3 of 5)≤ 1.2%

Table 12. Tokens per stage of a verification (millions), per model and evaluation set: the median over the runs that reached the stage and, in parentheses, the median share of the run’s tokens; “kk of NN” where not every run reached the stage. “Other steps” is the largest median share among segmentation, statement, and review steps. The static compile and the Lean checks inside the proof loop spend time, not tokens (text). Rows cover the same runs as Table 13; the rejected llm.c run (GLM 5.3) stopped in the race-freedom fallback, so it reached no proof stage.

Table 7. Per-verification budgets by model and task group: the cap on dialogue rounds per proof step (--max-auto-tries) and the spending ceiling (--max-usd). The round caps were read off preliminary runs in which the failure analyst always answered CONTINUE (GEMM on PTX with DeepSeek V4.1 Flash and GLM 5.3, GQA on PTX with Opus 5.5): the cap is the round of the last proof closure at the 75th to 90th percentile, plus one. The ceiling is the dollar amount at which a run was stopped; it is given for reference only.

GroupWorkloadsDeepSeek V4.1 FlashGPT-6 LunaGLM 5.3 FlashGLM 5.3Opus 5.5
L1relu, silu, gelu, softmax, layernorm, rmsnorm, gemv, gemm, linear, batchmatmul, conv2d, depthwise_conv16 / 5016 / 5016 / 758 / 100—
L2rope———16 / 10010 / 100
L2ffn, swiglu, flash_attn, gqa———16 / 10010 / 200
Libraryvllm_silu_and_mul, sglang_rmsnorm, vllm_rms_norm, vllm_rotary_embedding———8 / 100—
Libraryllmc_softmax_forward, sglang_fused_add_rmsnorm, flashinfer_rmsnorm, vllm_fused_qknorm_rope————10 / 100
Libraryfam_flash_attn, vllm_awq_gemm————10 / 200

Table 7 (PDF p. 15).

Scaling with Kernel Size

Over the 116 PTX and CUDA verifications, the Spearman rank correlation between the compiled program’s length in program counters and the run’s cost in dollars is 0.61; within a model, between length and tokens, it is 0.43 for DeepSeek V4.1 Flash, 0.55 for GPT-6 Luna, 0.64 for GLM 5.3 Flash and Opus 5.5, and 0.70 for GLM 5.3. Figure 4 plots the proven runs; for the three models with at least ten of them, a least-squares fit in log coordinates has slope 1.03 (GLM 5.3), 0.90 (GLM 5.3 Flash), and 0.99 (Opus 5.5), so within a model the tokens grow about linearly with the program’s length, and the lines differ by the model’s token appetite, not by the kernel. Between length and proof turns it is 0.17, rounds 0.20, and between the number of segments and cost 0.17. Proof cost grows with per-block depth, not with the grid.

Figure 4. Tokens of each proven verification against the compiled program’s length, over the PTX and CUDA runs, one colour per model (the number of runs in parentheses). The dashed lines are least-squares fits in log coordinates for the models with at least ten proven runs, a guide to the eye, not a fitted law; DeepSeek V4.1 Flash and GPT-6 Luna prove only the elementwise kernels and get none.

Why Every Model Fails on BatchMatmul and DepthwiseConv

Read from the 16 failing Level 1 runs on PTX and CUDA (four models, two kernels): no statement is false and no verdict blames the kernel; every analyst verdict but two is “theorem true, proof hard” or “proof loop stuck”. Every model stops on the same proof. Both kernels pin a 128-thread block whose warps run long chains of tensor-core operations, each once per warp: BatchMatmul’s 16-trip KK-loop of ldmatrix and mma makes one warp’s run of a block phase up to 97 sub-phases, and DepthwiseConv runs 26 collective operations back to back. The generated

scaffolding stops at the lane: the per-lane bridges and the trip lemmas are given, but composing them into the warp-level fold across the loop and the collective steps is left to the agent, and that is where every stall is. The two weaker models never close the first equivalence; the two GLM models close it and run out of budget on the second, whose proof must carry the whole dataflow through the staged shared buffers and the fragment-layout arithmetic. Two runs ended on a genuine bug in GPT-6 Luna’s own segmentation, caught by the first equivalence as designed. What would move these kernels is a generated warp-level bridge per block phase, so that the part every model fails on becomes generated, checked text. On HIP the pinned BatchMatmul kernel runs one 64-lane wavefront per block, so the warp-level composition that stops every model here is absent, and GLM 5.3 proves it; DepthwiseConv fails on HIP as on the other two languages.

Model Size and Tokens

Taking the active parameter count as a proxy for capability, Figure 5 plots, for the three small models with published sizes, the Level 1 pass rate, the input tokens per proved kernel, and the input tokens per kernel against active parameters, over PTX and CUDA. The pass rate rises with model size, and the larger model is also the cheaper one per proof: the pass rate goes from 25% to 54% to 79%, and a model that can close a proof needs fewer turns to do it, while a model that cannot spends its rounds and stops. Input tokens per proved kernel: GLM 5.3 (40B active) 466M, DeepSeek V4.1 Flash (16B) 1,617M, GLM 5.3 Flash (18B) 2,170M, and GPT-6 Luna 3,313M; mean input tokens per kernel, proved or not: 369M, 1,175M, and 828M. The largest model is the most efficient per proof, by 3.5 and 4.7 times; DeepSeek and GLM 5.3 spend about the same per kernel, but GLM 5.3 turns it into 19 certificates against 6, while GLM 5.3 Flash fails expensively, running 7 of its 11 failures to the ceiling. Output tokens are 0.7 to 2.4% of input for every model, so the input count carries the comparison; the dialogue re-sent each turn, mostly as cache reads, is the cost, not what the model writes. In dollars the order of DeepSeek and GLM 5.3 per proof is reversed (39against39 against73), only because DeepSeek’s tokens are priced lowest. On Level 2 the gap is wider: Opus 5.5 proves every kernel at 107M input tokens per kernel, a quarter of the 374M GLM 5.3 spends per kernel (Table 3).

Figure 5. Level 1 pass rate and tokens against the number of active parameters of the three small models with published sizes, over PTX and CUDA.

The Race-Freedom Fallback

The translator’s generated race-freedom lemmas proved on all 40 Level 1 and Level 2 verifications on PTX and CUDA; the agent fallback of § 5 never ran there. On the production kernels it ran on five of ten, where the translator could not name a footprint: vllm_silu_and_mul (8 turns), llmc_softmax_forward (10 turns), fam_flash_attn (2), vllm_fused_qknorm_rope (7, an output address that divides by the block size), and vllm_awq_gemm (6); four were proved, and on llmc_softmax_forward the fallback returned a located race instead of a proof (Appendix § 9.14). A later run of the same kernel text reuses the stored proof at no cost.

The Flat-Model Ablation

Three kernels were proved directly against the flat model (no segmentation, no segmentation proof) and compared with their default runs; tokens are input / output in millions. FlashAttention, Opus 5.5, PTX: flat 222.5 / 3.06, of which the direct proof 219.6 / 2.99 in three rounds of 20 turns, against 172.5 / 2.77 for the default run, of which the equivalence proof 119.6 / 2.05 in two rounds of 11 turns and the segmentation with its proof 49.1 / 0.64. The direct proof used 84% more input tokens than the equivalence proof and the whole run 29% more than the default run; it also crossed the $140 ceiling the run started with and finished only after it was raised to the Level 2 ceiling of $200, under which the default run had finished. On the two short kernels, ReLU and GEMM with GLM 5.3 on PTX, the direct proof was cheaper than the default run. Caveats: one hard kernel; the model differs between GEMM and FlashAttention; the default runs ran on an earlier code version than the flat runs.

The Failure Analysis

Table 13 gives the cost and the verdict statistics of the analysis per model; Figure 6 the distribution of verdicts by language, model, level, and library.

ModelCalls analyst / probe / 2nd op.Share of cell input aggregate / medianVerdict stopsFalse positives refuted / issued2nd op. refuted
DeepSeek V4.1 Flash610 / 755 / 33.7% / 3.5%11 / 13 / 3
GPT-6 Luna599 / 815 / 54.7% / 4.3%61 / 12 / 5
GLM 5.3 Flash336 / 303 / 80.7% / 0.6%11 / 16 / 8
GLM 5.3154 / 176 / 41.1% / 1.1%20 / 00 / 4
Opus 5.53 / 10 / 00.8% / 0.5%00 / 00 / 0

Table 13. The failure analysis inside the verification runs, per model: the Level 1 runs on PTX and CUDA, the Level 2 runs, and the production kernels. “Analysis” is every analyst, falsity-probe, and second-opinion call. Share: the analysis’s input tokens over the run’s, summed over a model’s runs and as the per-run median. Verdict stops: runs an analyst verdict ended before their spending ceiling. False positives: kernel-bug or race verdicts on a correct kernel, those refuted by the second analyst over those issued; every one was refuted, so none was acted on (two were issued before the second analyst existed and are counted as reviewed and refuted). Refuted: reviews in which the second analyst disputed the verdict, out of those it gave; a disputed verdict is not acted on.

Stacked bar charts showing verdicts of the failure analysis by target language, model, and production kernels

Figure 6. Verdicts of the failure analysis, as shares of the verdicts given.

Latency

Table 14 and Figure 7 give the latency of the verified evaluation kernels against torch eager, torch.compile, and the fastest vendor library, on an H100 for PTX and CUDA and on an MI300X for HIP; every ratio is against baselines measured on the same device, so the targets are not compared with each other. The Level 2 kernels were verified on PTX only, so PTX covers 17 kernels and CUDA and HIP the twelve Level 1 kernels. The verified kernels beat torch eager on every kernel (geometric mean 5.5×5.5\times on PTX, 4.2×4.2\times on CUDA, 4.1×4.1\times on HIP); torch.compile with max-autotune on 14 of 17 on PTX (2.6×2.6\times), 9 of 12 on CUDA (1.9×1.9\times), and 10 of 12 on HIP (2.1×2.1\times); and the fastest vendor library on 11 of the 14 PTX kernels that have one (1.46×1.46\times), 6 of 9 on CUDA (1.37×1.37\times), and 7 of 10 on HIP (1.22×1.22\times). The PTX kernels are faster than the CUDA ones on 6 of the 12 Level 1 kernels, by the most on GEMV (1.8×1.8\times), BatchMatmul (1.8×1.8\times), and DepthwiseConv (1.4×1.4\times); the other six are within 5%. The losses are the launch-bound elementwise kernels (2 to 5% behind torch.compile on the H100); rmsnorm against FlashInfer (1.3×1.3\times) and, on HIP, against torch.compile (1.8×1.8\times) and AITER (1.5×1.5\times); batchmatmul against the vendor batched GEMM (cuBLAS, built on wgmma and TMA, which are outside LARK’s scope, 1.3×1.3\times on PTX and 2.3×2.3\times on CUDA; hipBLASLt 2.0×2.0\times); SwiGLU on PTX against vLLM’s fused MLP (1.05×1.05\times); GEMV on CUDA and HIP against torch.compile (1.9×1.9\times, 2.0×2.0\times), where the PTX version wins; and LayerNorm on HIP against AITER (1.2×1.2\times).

KernelPTX (H100) Ours (μ\mus)vs eagervs compilevs vendorCUDA (H100) Ours (μ\mus)vs eagervs compilevs vendorHIP (MI300X) Ours (μ\mus)vs eagervs compilevs vendor
relu2.053.530.96—2.013.600.98—1.734.351.07—
silu2.083.550.97—2.063.580.98—1.753.811.10—
gelu1.993.521.022.381.983.541.032.391.774.173.021.72
softmax4.122.933.063.004.372.762.882.835.252.232.191.32
layernorm5.036.631.78—4.786.981.87—5.053.791.690.85
rmsnorm4.386.121.730.754.296.261.770.774.025.610.540.67
gemv3.054.230.951.535.542.330.530.843.833.090.491.31
gemm2.905.792.031.183.394.951.741.012.145.056.181.27
linear2.887.405.931.263.625.884.711.003.363.744.341.02
batchmatmul7.245.663.960.7712.863.192.230.4311.132.904.080.51
conv2d3.288.415.964.953.238.566.075.042.659.554.543.16
depthwise_conv3.364.066.122.384.652.944.431.724.133.835.292.00
rope2.2420.121.101.16————————
ffn9.754.964.531.09————————
swiglu11.034.996.110.95————————
flash_attn6.015.134.771.25————————
gqa4.328.105.571.22————————
Geometric mean5.502.611.464.201.911.374.062.141.22

Table 14. Table 14. Latency of the verified evaluation kernels at their pinned problem sizes (median of 7 rounds): PTX and CUDA on an H100 80GB SXM, HIP on an MI300X. The Level 2 kernels were verified on PTX only. “Ours” is the kernel’s time in microseconds; a ratio is the baseline’s time over ours on the same device, so a value above 1 means the verified kernel is faster, and the targets are not compared with each other. Baselines: torch eager (the task’s Torch module), torch.compile with max-autotune, and the fastest vendor library that offers the operation (cuBLAS, cuDNN, vLLM, FlashInfer, and the torch attention backends on the H100; hipBLASLt, rocBLAS, MIOpen, and AITER on the MI300X; a dash where none does).

Figure 7. Latency of the verified evaluation kernels relative to the baselines, from the same measurement as Table 14: PTX and CUDA on the H100, HIP on the MI300X. The vendor libraries are cuBLAS and cuBLASLt (GEMM, GEMV, batched GEMM, linear), cuDNN (convolution), FlashInfer (RMSNorm, softmax, RoPE, prefill attention), vLLM (SiLU-and-mul, GELU, FlashAttention-2), and the torch attention backends on the H100, and hipBLASLt, rocBLAS, MIOpen, and AITER on the MI300X; “fastest” is the best of these per kernel. A dagger marks a kernel whose time is within the launch overhead.

Mutation Results Analysis

Table 15 reports final-run outcomes after corrections to specification premises and output extraction: 11 static rejections, 10 race-freedom failures, 18 kernel-bug diagnoses, and 3 premise rejections; no mutant escapes. Static and race-freedom checks account for 12 of 15 GEMM rejections, while equivalence failure analysis accounts for most ReLU and Softmax rejections.

KernelLang.MutantsaStaticbRace-freecKernel bugdPremiseeEscapedf
ReLUCUDA410210
ReLUPTX401210
ReLUHIP401300
SoftmaxCUDA510400
SoftmaxPTX510400
SoftmaxHIP522010
GEMMCUDA541000
GEMMPTX512200
GEMMHIP513100

Table 15. Table 15. Mutation study: how each non-equivalent mutant was rejected. One mutant per rule, each counted once by its final run; ReLU has no barrier, so R3 does not apply to it.

Measuring the Per-Operation Semantics against the Hardware

Every lower-layer definition of § 4.1 is checked against the GPU before it is pinned. For each operation in a language’s table, a harness draws random operands from declared strata (finite values of each width, −∞-\infty where the operation admits it, boundary cases such as zero and powers of two), runs the operation on the GPU in its own operand form, and compares the result with the Lean definition evaluated on the same operands; a disagreement outside the declared idealizations fails the sweep. The sweep makes no LLM calls and is re-run whenever a table

changes; its record is pinned with the table, and a run reads the record its table was pinned on, never the newest. The sweep is what turned one wrong definition into a right one: the approximate base-two exponential had been formalized as exe^x and is 2x2^x. Shuffles and vector accesses are measured per lane and per alignment in the same way, and the lane layouts of the warp-collective operations are recorded from the hardware before they are pinned.

Retargeting LARK to a New Target Language

Effort. CUDA support on top of PTX took at most 39 person-days; its written lines (code, tests, and documentation, generated tables apart) are 68,741, of which 35,314 are code. HIP, ported from CUDA, took 21,495 written lines, of which 15,333 are code, about a third of CUDA’s lines and under half of its code. The shared machine model changed by 885 lines added and 655 removed, including one generalization: the warp width became a parameter, 32 for PTX and CUDA and 64 for HIP, whose wavefront has 64 lanes. HIP’s own translator code is largely a copy of CUDA’s, with 91% of its lines identical. CUDA’s own code is 37 files and 14,062 Python lines and HIP’s 30 files and 7,535 lines, against 221 files and 127,988 lines shared across languages; of the machine model’s Lean text, 96% is shared for HIP, 94% for CUDA, and 86% for PTX.

The split in symbols. What is fixed once splits as M=Mlaunch∪LM = M_{\mathrm{launch}} \cup L. The shared part

Mlaunch=(Σ,run,conv,RF,PreM,ExtM,C)M_{\mathrm{launch}} = (\Sigma,\mathrm{run},\mathrm{conv},\mathrm{RF},\mathrm{PreM},\mathrm{ExtM},C)

describes a launch for every language: the state, the folds of Equation (2), race freedom RF and its library (§ 5), the premise and extractor definitions PreM\mathrm{PreM} and ExtM\mathrm{ExtM} (§ 5), and the certificate CC (§ 5.1). The per-language part

L=(I,sem,cut,wL,parseL,fmtL,layoutL,lowerL)L = (\mathcal{I},\mathrm{sem},\mathrm{cut},w_L,\mathrm{parse}_L,\mathrm{fmt}_L,\mathrm{layout}_L,\mathrm{lower}_L)

is the operation table with its lower-layer definitions, the warp width wLw_L (32 for PTX and CUDA, 64 for HIP), the reader and the read-back formatter, the lane layouts of the warp-collective operations, and, for a structured language, the lowering.

Table 16 lists the components of LARK by whether they are shared across target languages or written per language. The split follows one rule: what describes a parallel launch is written once, what describes a language’s operations is written per language. The machine model MM abstracts GPU execution in general, so its state, value representation, cut hierarchy, folds, and convergence rule, the definition of race freedom with the library that discharges it, the premise schemas, the certificate structure with its end-to-end theorem, the premise and extractor definitions over a signature, the agent loop, and the report are one Lean text and one harness shared by every language. A language supplies its operation set I\mathcal{I}, generated from a pinned table whose lower-layer definitions are measured against the hardware (Appendix § 9.§ 6); its semantics sem\mathrm{sem} and cut classification cut\mathrm{cut}; a parser and printer, so that the byte round trip of § 4.1 can check every reading; the lane layouts of its warp-collective operations, recorded from the hardware; and, for a structured language, the lowering of source to the operation sequence, which is itself a pinned Lean definition. The translator’s race-freedom layer is one algorithm with a per-language front end that says what an operation’s operands and memory window are. PTX, being unstructured by design, needs no lowering; CUDA and HIP share the structured-tree lowering and differ in their operation tables and collective layouts.

Harness Details

Grid barrier. Block-level barriers are single operations with hardware-defined semantics and a cut of their own. A grid-wide barrier is not: in PTX, grid.sync() lowers to atomic counters and spin loops. LARK pins one template of that lowering, which a PTX kernel copies verbatim with its own registers and labels; the translator reads the copy as one grid-barrier pseudo-operation whose body is the identity and whose cut is grid-level, and the printer re-emits the template from the names it read, so the recognition is covered by the byte round trip. What remains trusted is that the template is a barrier under a cooperative launch. In CUDA and HIP the barrier is the one-line this_grid().sync(). Any other spelling is refused.

Value types. The type tags of § 4.1 are Ty={f16,f32,f16x2,intw,pred}T_y = \{\mathrm{f16},\mathrm{f32},\mathrm{f16x2},\mathrm{int}_w,\mathrm{pred}\}: a 16- or 32-bit float with payload in R∪{−∞}\mathbb{R} \cup\{-\infty\}, two packed 16-bit floats held as one value, an integer of width ww with payload in Z\mathbb{Z}, and a predicate. Other formats (bf16, 64-bit floats, packed 8-bit types) are outside the set and refused by name (Appendix § 9.9). The payload of a float tag is an element of R∪{−∞}\mathbb{R} \cup\{-\infty\}, with −∞-\infty admitted because kernels use it as the initial value of a running maximum; of a packed tag a tuple of them; of an integer tag an element of Z\mathbb{Z}, the width being part of the tag; of a predicate an element of {0,1}\{0,1\}. Rounding is hard to reason about, which is why arithmetic is exact in MM and floating-point behavior is left to testing (§ 5.1).

Read-back check. The translator’s reading of a kernel is not verified; each of its outputs is checked instead, in the manner of translation validation (Pnuելի et al., (1998); Necula [26]): the parsed data is formatted back to text and compared byte for byte with the source, so a wrong reading passes only if the formatter has a compensating defect. The trust therefore moves from the reader to the read-back formatter, which is the smaller and simpler component: for PTX the reader is 1,405 lines against 320 for the format-

.

ComponentWhat it containsStatusPer-language part
Machine model MM
State and memory hierarchyOne state for the launch: registers keyed by thread and name, global, shared, and local memory with type tags, coordinates and geometrySharedCoordinate reads and address spellings
Value representationTyped values: exact reals with −∞-\infty, exact integers with a width tag, predicates, packed halves; partial operations (faults)Shared
Cut hierarchy and foldscut kinds, the folds of Equation (2), convergence, fuelsSharedWhich operations define which cut; the warp width (32 or 64)
Race freedomDefinition over footprints, span lemmas, pair-lemma library, the reduction metatheory relied onShared
Premise schemasPlacement, separation, parameters, alignment, geometry, fuel, entry (Appendix § 9.8)Shared
CertificateThe certificate structure, non-vacuity, the end-to-end theorem proved onceShared
Operation set I\mathcal{I} and semOperation type generated from a pinned table; lower-layer definitions; contextual semanticsPer languageMeasured against the hardware (Appendix § 9.§ 6)
Collective layoutsLane and fragment layouts of ldmatrix, mma, wmma, shufflesPer languageRecorded from the hardware
Source loweringStructured source tree to operation sequence, as a pinned Lean definitionPer languagePTX: none; CUDA and HIP: shared tree lowering
Torch module formalizationLean definition of the module, tested against the modulePer moduleShared by every language
Translator
Parser and printerSource to data and back; byte round tripPer language
RefusalsClosed list of named refusals (Appendix § 9.9)Shared mechanismPer-language spellings
Grid-barrier recognitionPinned template (PTX) or the one-line call (CUDA, HIP)Per language
Race-freedom layerFootprint regions, pair lemmas and their proofs, agent fallbackShared coreOperand and memory-window reader
ScaffoldingPhase structure, counted loops and bridges, fuelsShared coreLoop and branch spellings
Proof generation and reporting
Statement generationThe fixed premise and extractor over a signature; non-vacuity proved onceShared
Agent loop and failure analysisSegmentation, proofs, diagnosisShared
Report and exportTrusted-assumption report, standalone Lean projectShared

Table 16. Components of LARK by whether they are shared across target languages or written per language, as instantiated for PTX, CUDA, and HIP. Shared components are one artifact used verbatim by every language; shared core components have one algorithm and one emitted Lean text with a thin per-language front end; per language components are written for each target and, where marked, measured against its hardware.

Stage / artifactProduced byBasis for acceptanceStatusIf it fails
Offline, once per target language or per module
Machine model MMHumans, agentsReview; pinned by hash; its idealizations declared as scopeTrusted(pre-checked)
Per-operation semanticsGenerated from pinned tablesMeasured against the hardware; pinned by hashTrustedOperation not in table: refuse
Torch module formalizationAgents, humansTested against the Torch module on random inputsTrusted (tested)Mismatch: fix before any run
Premise and extractor definitionsPinned in MMOne definition each over a signature; pre-checkedTrusted(pre-checked)
Reduction metatheoryLiteratureRace-free phases ⇒\Rightarrow one final state for every interleavingTrustedReported
Per kernel
Kernel as dataTranslatorRead-back check: the data formatted back to text equals the source byte for byteVerified (read-back)Refuse
Flat modelDerived in MMBuilt from the data by the pinned definitionVerified (by construction)
Race-freedom obligation RF⁡(K)\operatorname{RF}(K)Translator; agent fallbackLean proof per phase and pair of unitsVerifiedReject
Segment-level modelAgentNone; covered by SEG⁡(K)\operatorname{SEG}(K)UntrustedSee SEG⁡(K)\operatorname{SEG}(K)
Theorem statementGenerated from the signatureThe fixed premise and extractor over the task’s signature, which the task’s tests launch withTrusted (signature)Entry point mismatch: refuse
Non-vacuityProved once in MMThe fixed premise satisfiable for every signature and inputVerified
Segmentation obligation SEG⁡(K)\operatorname{SEG}(K): flat = segment-levelAgentLean proof; no sorry; standard axiomsVerifiedRetry; then no certificate
Equivalence obligation EQ⁡(K,S)\operatorname{EQ}(K,S): segment-level = specificationAgentLean proof; no sorry; standard axiomsVerifiedRetry; then no certificate
End-to-end theoremProved once in MMAssembles the rows above into Equation (1); #print axiomsVerified
Generator hintsKernel generatorRegions: checked by the lemmas; constant marks and launch: reportedUntrusted / JudgedFailed proof / reported
Standing
Named constants and approximate instructionsTableRead as exact valuesTrustedReported
Grid-barrier templatePinnedA barrier under a cooperative launchTrustedOther spelling: refuse
Read-back formatterFixed per languageFormats the kernel data back to text; about a quarter the size of the readerTrustedReported
Floating-point behaviorNumeric testOutside the theorem; tested at a toleranceScopeReported
Lean, Mathlib, axiomsExternal#print axioms per theoremTrustedReported

Table 17. Basis for acceptance at each stage of LARK. Verified: a Lean proof for the kernel at hand. Trusted: pre-checked or declared, kernel-independent, listed in the trusted-assumption report (§ 5.1). Judged: data a run supplies, quoted in the report. Untrusted: agent-generated, covered by a later Verified row. Figure 1 uses the same statuses.

ter, for CUDA 2,313 against 570, with a 217-line helper shared by both. The formatter walks the emitted data, not the reader’s in-memory objects, so what is printed is the data the theorem is about. The formatter is a trusted item and is listed in the report.

Fuel. Each level of the fold of Equation (2) runs under a fuel: lane steps per sub-phase, sub-phases per block-level phase, block-level phases per grid-level phase, and grid-level phases per launch. The fuels are data a run supplies, and exhausting any of them is a fault, so a fuel too small for the kernel fails the proof rather than weakening the theorem; nothing about loop bounds is trusted or analysed by a trusted component. The translator proposes generous fuels from the source, and the proof carries termination.

Folds and the proof-friendly restatement. The folds of Equation (2) are pinned once in MM. The agent’s segment-level model restates the kernel’s run in a sequential shape that a proof can induct on; the first equivalence of § 5 proves that this restatement equals the fold, using the verified race freedom of the kernel, and the second relates the restatement to the specification.

Efficiency mechanisms. Several mechanisms keep the agent–checker loop efficient: the agent can test lemmas in scratch Lean scripts before committing to them; a timed-out check returns the slowest declarations, the lemmas that passed, and any errors raised, so a failure still yields information; PROGRESS and DELTA submissions let the agent resume from a partial proof or patch part of a program instead of re-emitting it; and context compaction drops the oldest dispensable turns and repeated listings while keeping the system prompt, the first turn, and the most recent messages.

Failure analysis. When a loop exhausts its attempts, an agentic failure analysis diagnoses the cause (a hard proof, an inefficient proving approach or formalization, or a faulty kernel) and acts accordingly: continue the loop, restart it with a fresh dialogue, redo the formalization, or return the diagnosis to the generation side as feedback for a new kernel. The last path closes the generate-and-verify cycle: a kernel that cannot be proved equivalent because it is wrong is sent back with an explanation of why. The pipeline aborts only when the number of analyses or the overall budget reaches its ceiling.

Premise Schemas

Every theorem statement is computed from the task’s signature: a list with one entry per kernel argument, in entry order. A buffer entry carries its role (input, output, in-place, or scratch), its element type, its shape, and its layout, a strided tensor in PyTorch’s sense, with each stride a literal or a named integer parameter; a scalar entry carries its domain (any real, or positive) or its pinned value; an integer dimension carries its value. The launch is recorded with it: the block pinned or capped at the declared bound, and the grid pinned, capped and one-dimensional, or merely nonempty, the form chosen by data. The signature is generated from the task’s registry, the same list the task’s tests launch the kernel with, and is checked against the kernel’s entry point by position and kind. The fixed premise over a signature states: every input and in-place buffer placed at its base under its layout, with the memory’s type tags set; every pair of distinct buffers byte-separated; every base aligned to its element size and vector width; every scalar bound to the specification’s input, or pinned; every dimension pinned; every runtime stride at least its row length; and the launch geometry. A scratch buffer is separated and aligned, never placed or extracted; an in-place buffer is placed as an input and read as an output. The fixed extractor reads every output and in-place buffer under its layout. Both are defined once in MM; the facts a proof needs (a placement, a separation, a binding) are projection lemmas of the model, instantiated by name for the run. Satisfiability of the premise is one theorem of MM over every signature whose byte spans fit. Layouts out of scope, refused by name: sub-byte and bit-packed elements, indirection through index buffers, and swizzled or blocked global layouts; shared-memory layouts are internal to the kernel and never part of the premise.

Formally, the signature is a list sig∈List(Arg)sig \in List(Arg) with one entry per kernel argument,

Arg::=buf(ρ,τ,shape,layout)∣scalar(dom)∣scalar(v)∣dim(n)Arg ::= buf(\rho, \tau, shape, layout) \mid scalar(dom) \mid scalar(v) \mid dim(n)

a buffer with role ρ∈{in,out,inout,scratch}\rho\in\{in, out, inout, scratch\}, element type τ\tau, shape, and strided layout (element i⃗\vec{i} at base+∣τ∣∑kikskbase + |\tau|\sum_k i_k s_k); a float scalar bound to a specification input of domain domdom or pinned to vv; an integer dimension pinned to nn. The theorem of § 5 quantifies over the kernel’s parameters p⃗\vec{p} (base addresses, strides, scalars; Equation (1) folds them into σ\sigma), every state satisfying the premise, and every input, and the satisfiability theorem above reads

∀sig. ∀x∈D. ∃p⃗ σ. Pre⁡M(sig,launch)(p⃗,σ,x),\forall sig.\ \forall x \in D.\ \exists\vec{p}\ \sigma.\ \operatorname{Pre}_{M}(sig, launch)(\vec{p}, \sigma, x),

proved once for every signature, so no statement holds vacuously.

Unsupported Constructs

The translator refuses, by name and before any proof is attempted: +∞+\infty as a value and NaN in any form (the creation of either is a fault); integer wraparound and integer division or remainder by zero; bit operations other than a literal mask, a literal shift, and the full warp mask; float-to-integer conversions out of range; the .sat, .ftz, and bf16 forms, FP64, and 8-bit types; asynchronous operations (cp.async, mbarrier, TMA, wgmma, tcgen05, cluster barriers); atomics and fences used for communication; partially masked barriers, shuffles, and collectives; a grid barrier spelled other than the pinned template; addresses that are not polynomial in the thread coordinates, loop counters, and parameters; blocks with more than one dimension and grids with more than two; and any operation absent from the pinned table. Approximate instructions (ex2.approx, lg2.approx, rcp.approx, rsqrt.approx) are accepted and read as the exact function, and the tf32 form of mma is accepted as an FP32 carrier; both are declared idealizations listed in the report. The complete list, with the name of each refusal, ships with the code.

Race-Freedom Lemmas

Race freedom is what the fold of Equation (2) needs because

RF⁡(K)∧run⁡r⃗grid(σ)=σ′⇒[ ⁣[K] ⁣]M(σ)∧[ ⁣[K] ⁣]M(σ)=σ′,\operatorname{RF}(K) \land\operatorname{run}_{\vec{r}_{\mathrm{grid}}}(\sigma)=\sigma' \Rightarrow[\![K]\!]_{M}(\sigma) \land[\![K]\!]_{M}(\sigma)=\sigma',

that is, every execution of KK from σ\sigma, under any scheduling, is finite and ends in σ′\sigma': the actions of race-free units commute, and the barrier that ends a phase orders the phases (Lipton’s reduction, § 5). The translator derives each footprint Wϕ(u)W_{\phi}(u), Rϕ(u)R_{\phi}(u) of § 5 as a region polynomial in the thread coordinates, loop counters, and kernel parameters, and generates the two disjointness lemmas of the race-freedom obligation for every phase and pair of units, with proofs over the theorem’s premises, which Lean checks. Where an address is not polynomial in these variables (a clamped index, for instance), the translator cannot name the region: it emits the lemma’s statement without a proof and an agent attempts it, with an independent second opinion on a verdict that the statement is false. A kernel with an unproved lemma is rejected, whether from a real race or a region the translator could not name, and a located race is returned as a counterexample naming the two threads and the cell (§ 6). The condition is sufficient, not necessary: it also rejects units that communicate within a phase, such as producer–consumer blocks.

Generator Hints

A kernel generator may annotate its kernel with three kinds of hint: the regions each thread writes in a phase, which guide the translator’s choice of footprints when it generates the race-freedom lemmas; a mark naming the exact constant behind a rounded literal, which the translator cross-checks against the literal’s bits and which the pinned decoder then reads as the exact value; and the launch it expects, which selects the launch form of the fixed premise and which the numeric test launches with. The first kind decides nothing, since every lemma built from it is checked by Lean and a wrong region fails a proof. The second and third are the two hints Lean cannot check; both appear in the report.

Certificate Export

Every run exports its certificate as a standalone Lean project: the pinned model text, the kernel as data with its parse, the signature, the fuels, the race-freedom lemmas, the two equivalence proofs, and the end-to-end theorem, together with the output of #print axioms on that theorem. The project builds with the public Lean toolchain and Mathlib and re-checks without any part of LARK, so a certificate can be audited by a checker that shares no code with the one that produced it. The supplementary material contains the project of the GQA kernel.

The Kernel-Independent Premises

The kernel-independent premises ΠM\Pi_M of § 5.1 are: (i) the idealizations of MM, exact arithmetic as scope and the fold of Equation (2) with the reduction result of § 5; (ii) the per-operation semantics sem, generated from the pinned tables and measured against the hardware (Appendix § 9.§ 6); (iii) the pinned grid-barrier template; (iv) a table of four named constants, under which a rounded literal a kernel writes for log⁡2e\log_2 e is read as the exact value, and the approximate instructions read as exact; (v) the Lean formalization of the Torch module; (vi) the premise and extractor definitions PreM and ExtM; (vii) the read-back formatter (Appendix § 9.§ 8); (viii) Lean, its three standard axioms, and its toolchain. Item (v) is tested: a Lean metaprogram evaluates the elaborated specification in 64-bit floating point on random inputs against the Torch module, refusing by name any construct it does not recognize, and the result is reported as evidence, not proof.

Production Kernels

What “adapted” means. No production kernel is verified byte for byte as upstream ships it. Each adapted kernel is the smallest mechanical rewrite of the upstream kernel into the pipeline’s input form, and every step is recorded as a change with its reason. The rewrites common to most kernels change the form of the code and not what it computes: one non-template extern "C" kernel per file, with the template instantiated as the library launches it and helpers such as warp reductions inlined; one operation per line, for written as while, no ternary; warp reductions written as full-mask shuffle steps; a lane-0 guard on the per-warp shared store that every lane makes with the same value; a declared block size where upstream declares none, since the theorem pins the block; dynamic shared buffers as static arrays of a covering size; cache hints and programmatic-dependent-launch calls dropped; a 2-D block flattened; vector accesses kept where the race-freedom lemmas cover them and otherwise written as loops of scalar accesses.

Departures. A step that changes upstream’s semantics is marked as a departure, and the theorem is about the kernel with the departure. They are: 64-bit token and stride indices read as 32-bit (exact at the tested shapes; vllm_silu_and_mul, sglang_rmsnorm, vllm_rms_norm); a runtime alignment test dropped, keeping its aligned path (vllm_rms_norm); the positions gather dropped, so the input is the already gathered rows of the cosine and sine cache, and sizes and flags written as literals (vllm_rotary_embedding, vllm_fused_qknorm_rope); vllm_fused_qknorm_rope made out of place, writing Q and K to a new buffer; the number of threads written as the host’s literal and rsqrt.approx replaced by rsqrtf (flashinfer_rmsnorm); FP32 input and output made FP16 storage (llmc_softmax_forward, fam_flash_attn); the running max and sum made per-thread arrays and the output zeroed by the kernel rather than the host, and __expf replaced by expf (fam_flash_attn); the int4 dequantization removed, so the weights are FP16, a single split-KK iteration, and the block decode’s sizes written as literals (vllm_awq_gemm, transcribed into PTX from upstream’s inline assembly). sglang_fused_add_rmsnorm has no departure and is verified in place, with input and residual as in-out buffers. Per kernel, the rewrite steps and, of them, the departures are: vllm_silu_and_mul 6 and 1, sglang_rmsnorm 10 and 1, sglang_fused_add_rmsnorm 9 and 0, vllm_fused_qknorm_rope 11 and 3, vllm_rotary_embedding 6 and 3, vllm_rms_norm 8 and 2, flashinfer_rmsnorm 12 and 2, llmc_softmax_forward 11 and 2, fam_flash_attn 9 and 4, vllm_awq_gemm 10 and 3.

The llm.c race. softmax_forward_kernel7 computes the softmax of each row in three passes: a maximum, a sum of exponentials, and a normalization that writes the row of out. In the third pass a thread’s unguarded clamped load __half yh = out[a] with a=min⁡(C−1,k)a = \min(C-1,k) reads a cell of out that another thread of the same block stores at out[a] = qh in the same pass, with no barrier between; the loaded value is used only where k<Ck < C, where the clamped address is the thread’s own cell, so on the tested shapes nothing observable depends on the race. What happened in LARK: the translator’s race-freedom layer builds its footprints from accesses whose addresses are polynomials in the thread and loop indices, and the clamped address is not one, so it refuses to emit its lemma raceFree_1 for the output store, without locating the by Lean and a wrong region fails a proof. The second and third are the two hints Lean cannot check; both appear in the report. race, and the obligation goes to the agent fallback of § 5, where the race-freedom statement is false. The fallback’s loop with GLM 5.3 ended after 10 turns and 9.8M input tokens with a counterexample rather than a proof: thread 0 of block 0 at the load with k≥C−1k \ge C - 1 reads out[50256], and thread 80 of the same block, the unique writer of that cell, stores it at the third pass’s store; the independent second opinion confirmed the race. A second run with a neutral kernel header found a different witness of the same race (a one-block, 32-thread launch the theorem admits) in 7 turns, so the race is found from the code alone, at about a tenth of what a proof of this kernel costs. The kernel of Table 5 is this original text, and its row records the rejection. A one-line rewrite removes the race: upstream reads out[row + min(C-1, k)] unconditionally, and the rewrite reads out[row + k] under the store’s bounds guard if (k < C), so each thread reads only the cell it then writes, with every other line unchanged and the same values on every input; it verified with Opus 5.5 in a separate run.

References

  1. [1]Adve, S. V. and Hill, M. D. Weak ordering a new definition. In Proceedings of the 17th Annual International Symposium on Computer Architecture, ISCA ’90, pp. 214, New York, NY, USA, 1990. Association for Computing Machinery. ISBN 0897913663. doi: 10.1145/325164.325100. URL https://doi.org/10.1145/325164.325100.
  2. [2]Ammanamanchi, P. S., Bhat, S., and Biderman, S. Faults in our formal benchmarking: Dataset defects and evaluation failures in Lean theorem proving. In Proceedings of the 43rd International Conference on Machine Learning, volume 306 of PMLR, pp. 2431–2462, 2026.arxiv.org/abs/2606.29493
  3. [3]Armborst, L., Bos, P., van den Haak, L. B., Huisman, M., Rubbens, R., Şakar, Ö., and Tasche, P. The vercors verifier: a progress report. In International Conference on Computer Aided Verification, pp. 3–18. Springer, 2024.DOI
  4. [4]Armstrong, A., Bauereiss, T., Campbell, B., Reid, A., Gray, K. E., Norton, R. M., Mundkur, P., Wassell, M., French, J., Pulte, C., Flur, S., Stark, I., Krishnaswami, N., and Sewell, P. Isa semantics for armv8-a, risc-v, and cherimips. Proc. ACM Program. Lang., 3(POPL), January 2019. doi: 10.1145/3290384. URL https://doi.org/10.1145/3290384.
  5. [5]Banerjee, D., Bouissou, O., and Zetzsche, S. Dafnypro: Llm-assisted automated verification for dafny programs. arXiv preprint arXiv:2601.05385, 2026.arxiv.org/abs/2601.05385
  6. [6]Baronio, C., Marsella, P., Pan, B., Guo, S., and Alberti, S. Kevin: Multi-turn rl for generating cuda kernels. In International Conference on Learning Representations, volume 2026, pp. 83418–83452, 2026.arxiv.org/abs/2507.11948
  7. [7]Beel, J., Kan, M.-Y., and Baumgart, M. Evaluating sakana’s ai scientist: Bold claims, mixed results, and a promising future? SIGIR Forum, 59(1):120, October 2025. ISSN 0163-5840. doi: 10.1145/3769733.3769747. URL https://doi.org/10.1145/3769733.3769747.
  8. [8]Betts, A., Chong, N., Donaldson, A., Qadeer, S., and Thomson, P. Gpuverify: a verifier for gpu kernels. In Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA ’12, pp. 113–132, New York, NY, USA, 2012. Association for Computing Machinery. ISBN 9781450315616. doi: 10.1145/2384616.2384625. URL https://doi.org/10.1145/2384616.2384625.
  9. [9]Chatterjee, B., Zagieboylo, D., Damani, S., Hari, S., and Kozyrakis, C. Proofwright: Towards agentic formal verification of cuda, 2026. URL https://arxiv.org/abs/2511.12294.
  10. [10]Collingbourne, P., Donaldson, A. F., Ketema, J., and Qadeer, S. Interleaving and lock-step semantics for analysis and verification of gpu kernels. In European Symposium on Programming, 2013. URL https://api.semanticscholar.org/CorpusID:17382289.DOI
  11. [11]Dao, T., Fu, D., Ermon, S., Rudra, A., and Ré, C. Flashattention: Fast and memory-efficient exact attention with io-awareness. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 16344–16359. Curran Associates, Inc., 2022. doi: 10.52202/068431-1189. URL https://proceedings.neurips.cc/paper_files/paper/2022/file/67d57c32e20fda7a302cb81d36e40d5-Paper-Conference.pdf.DOI
  12. [12]Driscoll, B., Dubey, K., Wei, A., Kayal, N., Sharma, R., and Aiken, A. Equivalence checking of ML GPU kernels. Proc. ACM Program. Lang., 10(OOPSLA2), 2026.arxiv.org/abs/2511.12638
  13. [13]Feng, Y., Kafle, D., Gladshtein, V., Kurin, V., Pîrlea, G., Zhao, Q., Müller, P., and Sergey, I. Certified program synthesis with a multi-modal verifier, 2026. URL https://arxiv.org/abs/2604.16584.
  14. [14]Ferrell, B., Duan, J., and Hamlen, K. W. Cuda au coq: A framework for machine-validating gpu assembly programs. In 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE), pp. 474–479, 2019. doi: 10.23919/DATE.2019.8715160.DOI
  15. [15]Goel, S., Keizer, A., Siddharth, Peng, Y., Morrison, K., Wetzler, N., de Moura, L., Ebeid, N., Lee, J., Letson, A., Cicolini, L., Kong, S., and dependabot[bot]. lean-prover/LNSym. https://github.com/leanprover/LNSym, jul 8 2026. URL https://github.com/leanprover/LNSym.
  16. [16]Karpathy, A. llm.c: LLM training in simple, raw C/CUDA. https://github.com/karpathy/llm.c, 2024. GitHub repository.
  17. [17]Kim, P. flash-attention-minimal: Flash attention in ~100 lines of CUDA. https://github.com/tspeaterkim/flash-attention-minimal, 2024. GitHub repository.
  18. [18]Klein, G., Andronick, J., Elphinstone, K., Heiser, G., Cock, D., Derrin, P., Elkaduwe, D., Engelhardt, K., Kolanski, R., Norrish, M., Sewell, T., Tuch, H., and Winwood, S. sel4: formal verification of an operating-system kernel. Commun. ACM, 53(6):107115, June 2010. ISSN 0001-0782. doi: 10.1145/1743546.1743574. URL https://doi.org/10.1145/1743546.1743574.
  19. [19]Kwon, W., Li, Z., Zhuang, S., Sheng, Y., Zheng, Y., Yu, C. H., Gonzalez, J. E., Zhang, H., and Stoica, I. Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, 2023.arxiv.org/abs/2309.06180
  20. [20]Lange, R. T., Sun, Q., Prasad, A., Faldor, M., Tang, Y., and Ha, D. Towards robust agentic cuda kernel benchmarking, verification, and optimization, 2025. URL https://arxiv.org/abs/2509.14279.
  21. [21]Leroy, X. Formal verification of a realistic compiler. Commun. ACM, 52(7):107115, July 2009. ISSN 0001-0782. doi: 10.1145/1538788.1538814. URL https://doi.org/10.1145/1538788.1538814.
  22. [22]Lipton, R. J. Reduction: a method of proving properties of parallel programs. Commun. ACM, 18(12):717721, December 1975. ISSN 0001-0782. doi: 10.1145/361227.361234. URL https://doi.org/10.1145/361227.361234.
  23. [23]Lopes, N. P., Lee, J., Hur, C.-K., Liu, Z., and Regehr, J. Alive2: bounded translation validation for llvm. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2021, pp. 6579, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383912. doi: 10.1145/3453483.3454030. URL https://doi.org/10.1145/3453483.3454030.
  24. [24]Lustig, D., Sahasrabuddhe, S., and Giroux, O. A formal analysis of the nvidia ptx memory consistency model. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’19, pp. 257270, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450362405. doi: 10.1145/3297858.3304043. URL https://doi.org/10.1145/3297858.3304043.
  25. [25]Moura, L. d. and Ullrich, S. The lean 4 theorem prover and programming language. In Automated Deduction CADE 28: 28th International Conference on Automated Deduction, Virtual Event, July 1215, 2021, Proceedings, pp. 625635, Berlin, Heidelberg, 2021. Springer-Verlag. ISBN 978-3-030-79875-8. doi: 10.1007/978-3-030-79876-5_37. URL https://doi.org/10.1007/978-3-030-79876-5_37.
  26. [26]Necula, G. C. Translation validation for an optimizing compiler. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, PLDI ’00, pp. 8394, New York, NY, USA, 2000. Association for Computing Machinery. ISBN 1581131992. doi: 10.1145/349299.349314. URL https://doi.org/10.1145/349299.349314.
  27. [27]Nie, J., Wu, H., Lai, Y., Cao, Z., Zhang, C., Lou, B., Wang, E., Cheng, J., Jones, T. M., Mullins, R., Antonova, R., and Zhao, Y. Kernelcraft: Benchmarking for agentic close-to-metal kernel generation on emerging hardware, 2026. URL https://arxiv.org/abs/2603.08721.
  28. [28]Ouyang, A., Guo, S., Arora, S., Zhang, A. L., Hu, W., Ré, C., and Mirhoseini, A. Kernelbench: can llms write efficient gpu kernels? In Proceedings of the 42nd International Conference on Machine Learning, ICML’25. JMLR.org, 2025.arxiv.org/abs/2502.10517
  29. [29]Pnueli, A., Siegel, M., and Singerman, E. Translation validation. In Proceedings of the 4th International Conference on Tools and Algorithms for Construction and Analysis of Systems, TACAS ’98, pp. 151166, Berlin, Heidelberg, 1998. Springer-Verlag. ISBN 3540643567.DOI
  30. [30]Pouchet, L.-N., Tucker, E., Zhang, N., Chen, H., Pal, D., Rodríguez, G., and Zhang, Z. Formal verification of source-to-source transformations for hls. In Proceedings of the 2024 ACM/SIGDA International Symposium on Field Programmable Gate Arrays, pp. 97–107, 2024.DOI
  31. [31]Sarkar, D. The correctness illusion in llm-generated gpu kernels, 2026. URL https://arxiv.org/abs/2606.20128.
  32. [32]Shah, R. and Shrestha, R. A contract-grade verifier for llm-generated gpu kernels, and a native blackwell backward for the gated-linear-recurrence family, 2026. URL https://arxiv.org/abs/2608.12700.
  33. [33]Tillet, P., Kung, H. T., and Cox, D. Triton: an intermediate language and compiler for tiled neural network computations. In Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, MAPL 2019, pp. 1019, New York, NY, USA, 2019. Association for Computing Machinery.DOI

Paper details

vlnc:W_9hrqusze
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents