This is a fork. VeriTile was created by Zenan Li (Lizn-zn/VeriTile, MIT License; see
LICENSE). Everything below the next horizontal rule is the original project's README, and the docs site it links to describes the original project. All credit for VeriTile itself — the Lean 4 Triton DSL, its semantics and theorem surfaces, and the 173 ported TritonBench-G kernels with proofs — belongs to its author. This fork is not affiliated with or endorsed by the original author, and its additions have not been upstreamed.Fork point: upstream commit
95a01f59("Refactor audit source helpers and shared scatter-store proofs", 2026-09-24). To list what it adds and changes, rungit diff --stat 95a01f59. Modified upstream Lean files keep their original code verbatim; the fork's gate (scripts/launch_local_check.py) enforces that.
1. A verified host-launch layer for Triton kernels (VeriTile/Triton/Launch/, bench/tritonbench_g/add_example/)
- Launch proofs. Lean proofs that a 1-D blocked, masked launch covers its output exactly
(
Blocked1D,Serial,Line3,StridedUnary). There is also a flat-memory placement bridge, and a kernel-agnostic relational result for fused-versus-unfused launches (Relational.lean). - Whole-wrapper contracts. Contracts for
add_example,vector_addition_customand a strided ReLU consumer, connected to a checked Python invocation. - Gate (
scripts/launch_local_check.py):- freeze-from-
sorrystatement snapshots; - axiom audits;
- an upstream-pin check;
- per-evidence dependency hashes.
- freeze-from-
2. Optimization studies with proofs (bench/optimizations/)
cat_repack/: a standalone fast-division kernel for pytorch/pytorch#189940 (dynamic nestedcat), proved correct. It includesVeriTile/Triton/Launch/FastDiv.lean(magic-number division, 32-bit exact).inductor_divmod/: a guarded rewrite of Inductor's own generated kernel. It isolates two effects: narrowing its size arguments toint32helped, and computing fast division inside the kernel did not.inductor_narrow/: the main result.NarrowCat.leanproves that declaring the kernel's seven size argumentsint32instead ofint64preserves every observable of every lane. The proof is stated over the kernel's actual integer semantics, extracted from the emitted source, under facts Inductor already holds.RULE.mdstates the rule and all of its premises.CONFIRM.mdholds the pre-registered measurement on one L4: 26–30% less warm-sequence time than the emitted kernel, bitwise-identical output.upstream/holds a small opt-in PyTorch patch (config.triton.narrow_proven_size_args), validated at PyTorch6aa9e2fc.
Where to start
Scope and caveats
- Measurements. One NVIDIA L4 (Modal), warm cache.
- Evidence. All evidence JSON files are in
bench/tritonbench_g/add_example/launch_evidence/. - Floating point. No claim is made. Payloads are treated symbolically, or over exact reals.
- Trust assumptions. They are listed where they apply, for example in
RULE.md.
📖 Docs site: lizn-zn.github.io/VeriTile/ (bench cookbook, status, architecture). Run locally: ./site/scripts/dev.sh.
VeriTile embeds a typed Triton-style kernel DSL in Lean 4 and proves
correctness or refinement of those kernels against mathematical
specifications or against each other. The implementation embeds the kernel
language with triton { ... } syntax, defines an operational semantics over
typed Op : TileDType → TileShape → Type terms, and exposes
ComputeCorrect / ComputeRefine theorem surfaces for end users.
Algorithmic proofs run over the erased .real (mathematical) channel; the
optional GapPolicy records — but does not internally prove — the
compute-to-algorithm gap (IEEE-754 / PTX / TMA / concurrency), which stays
externally checked. See Triton subset and gaps.
- DSL: typed Triton subset with
triton { ... }macro, ND tile shapes, reductions, masks (mask=/other=), block-pointer ops, and bareif/forcontrol flow. - Theorem surfaces:
ComputeCorrect.Realizes_without_Roundingfor one kernel vs a math specification,ComputeRefine.Refinesfor one kernel refining another (writes-equality: the two final memories agree at every cell outside the declared scratch regions). Both project throughtoAlgorithm?and run onKernel.Correct_without_Rounding/Kernel.Refineunderneath. - Narrow-float / rounding-model layer (#1): an abstract
RoundingModel(round : FloatDType → ℝ → ℝ, fieldsround_real(real-channel identity) andround_idem(idempotence)) threads a black-box rounding function through the semantics (evalOpR/stepStmtR/execR). The unqualified surfaces are the rounding-parametric ones —ComputeRefine.Realizes(single kernel vs an R-annotated spec) andRefines/RefinesAt(two kernels) run under aRoundingModel R; the exact-ℝ idealization is the qualified*_without_Roundingname, which the bridgeRealizes.toRealizes_without_Roundingdegenerates out to (asComputeCorrect.Realizes_without_Rounding) at the trivial model. See the fused-vs-unfused SwiGLU showcasebench/examples/FusedSwigluEquiv.lean. - Examples: 173 ported TritonBench-G kernels with proofs (source of truth:
bench/tritonbench_g/completion_audit.md; see the per-theorem coverage table for configured models, slices, and remaining gaps) plus FlashAttention-1 forward, online softmax, Welford, LayerNorm, log-sum-exp. - CI gates:
.github/workflows/bench-audit.ymlrunsbench/audit_tritonbench_g.sh— per-port elaboration (bench/check_ports.sh), the Python↔Lean faithfulness scans, the proof-gap manifest, and both trust audits (#axiomsCleanover the library viaVeriTile.Meta.TrustReport, and over the standalone bench corpus viabench/audit_trust.sh)..github/workflows/artifact.ymlrunslake build+scripts/check-artifact.sh(nosorry, axiom whitelist, manifest schema, doc-drift checks)..github/workflows/site.ymlbuilds and deploys the docs site to GitHub Pages on every push touchingsite/.
Out of scope: IEEE-754 floating-point semantics, PTX-level codegen, detailed concurrency (atomics / async-copy serialization, beyond the projection boundary), Python wrapper execution.
Kernels are region-polymorphic: memory regions arrive as RegionName
parameters; tl.load / tl.store use first-class pointer expressions.
def addKernel (xReg yReg outReg : RegionName) (n : Nat) : ComputeKernel := triton {
pid = tl.program_id(0)
offsets = pid * $(n) + tl.arange(0, $(n))
x = tl.load($(xReg) + offsets)
y = tl.load($(yReg) + offsets)
tl.store($(outReg) + offsets, x + y)
}| Goal | Use |
|---|---|
| One kernel matches an output spec | ComputeCorrect.Realizes_without_Rounding |
| One kernel refines another (writes-equality) | ComputeRefine.Refines |
| Two kernels agree pointwise per address | ComputeRefine.RefinesAt |
| Single kernel / pairs under a rounding model (narrow-float) | ComputeRefine.Realizes / Refines / RefinesAt |
Value + index output (e.g. tl.max(..., return_indices=True)) |
ComputeCorrect.OutputPairWhere |
| Custom postcondition over the final state | ComputeCorrect.Post / ComputeRefine.Post |
| Relation over arbitrary initial states (rare) | ComputeCorrect.General / ComputeRefine.General |
Full surface guide: CorrectnessSurfaces.md.
theorem add_kernel_correct
(xReg yReg outReg : RegionName) (n : Nat) (hN : 0 < n)
(s : BlockState) (xs ys : Fin n → ℝ)
(h_x : TensorView.loadedArray s (programTileView s xReg n) xs)
(h_y : TensorView.loadedArray s (programTileView s yReg n) ys) :
ComputeCorrect.Realizes_without_Rounding
(kernel := addKernel xReg yReg outReg n)
(initialState := s)
(write := fun i : Fin n => some (outReg, s.pid * n + i.val))
(expected := fun i => xs i + ys i) := by
-- bridge to the projected algorithm kernel, then close on Real semantics
...The standard pattern: ComputeKernel.computeCorrect_of_toAlgKernel rfl
discharges the projection, then simp reduces exec to the body
recurrence; the algebraic content closes by simp on the spec or by
invoking a math identity from Mathlib. The LLM proof wrapper
scripts/prove.sh automates this loop and uses the official comparator to judge
the targets selected with --theorem against the original task.
See setup and usage.
The artifact and bench check scripts also require comparator proof replay;
see the shared verification gate.
Add a row to scripts/kernel-manifest.tsv
so scripts/check-artifact.sh recognizes the theorem in CI. Schema and
naming conventions: KernelManifest.md,
TheoremSurfaces.md.
Elementwise vector add against the addSpec xs ys i = xs i + ys i math
spec — see bench/examples/VectorAdd.lean.
Naive vs numerically-stable softmax (kernel pair refinement) — see
bench/examples/SoftmaxStableEquiv.lean.
Task-oriented:
| Question | Doc |
|---|---|
| Which Triton constructs are supported? | TritonSubset.md |
| What semantic caveats affect theorem interpretation? | SemanticCaveats.md |
| Where does my new lemma / definition belong? | CodeOrganization.md |
Tactic conventions (incl. erw carrier-bridge) |
ProofConventions.md |
| Which theorem surface should I use? | CorrectnessSurfaces.md |
| How does dtype erasure work? | EraseDType.md |
| How does memory safety / framing work? | MemorySafety.md |
| What's the GPU memory model? | GpuMemoryModel.md |
| How are atomics / async copies modeled? | ConcurrencySemantics.md |
| How does the kernel manifest work? | KernelManifest.md |
| Naming conventions for theorem surfaces | TheoremSurfaces.md |
| LLM proof wrapper | scripts/README.md |
VeriTile/
Triton.lean Umbrella prelude (`import VeriTile.Triton`)
Triton/
Core/ AST (Kernel/ComputeKernel type, ComputeOp bits)
Semantics/ Typed operational semantics (exec, execR)
Memory/ BlockState, tensor views, readback
DSL/ `triton { ... }` front-end
Math/ Pure `(Fin N → ℝ) → ...` operators (+ Math/Erf)
KernelLemmas/ Reusable bench-proof helpers (was Triton/Kernel/)
Correctness.lean Top-level correctness/refinement surfaces
(Kernel.Correct_without_Rounding, ComputeCorrect.*, ComputeRefine.*)
Float/ Floating-dtype machinery: dtype erasure +
the rounding model (RoundingModel, execR, Refine,
Pipeline)
Launch/ Grid-launch composition / write footprints
Concurrency/ Grid-wide atomic-add correctness (above Launch)
Examples/ Worked correctness/refinement proofs
bench/tritonbench_g/ TritonBench-G v1 ports (173 pairs; see completion_audit.md)
bench/examples/ Showcase proofs (SwiGLU rounding invariance, ...)
documents/ Design notes, subset spec, surface guide
scripts/ CI gate, kernel manifest, LLM proof wrapper
verso/ Slide deck / overview
lake build— build the defaultVeriTilelibrary target; standalone benchmarks/showcases and the GeLU/trust-report target are separatelake build VeriTile VeriTileFull— also build the full analysis and library trust reportlake env lean bench/examples/VectorAdd.lean— quick example smoke check after buildingscripts/check-artifact.sh—lake build∧no sorry∧ axiom whitelist ∧ kernel-manifest schema ∧ README/doc-term driftbench/check_ports.sh— per-port build of the TritonBench-G ports (also run insidebench/audit_tritonbench_g.sh, the bench-audit CI gate)bench/audit_tritonbench_g.sh— the full bench gate: the per-port build above ∧ faithfulness scans ∧ proof-gap manifest ∧ both trust auditsbench/audit_trust.sh— trust gates and comparator replay for every standalone bench file
- Lean 4 (
v4.29.0) + Mathlib - Claude Code CLI +
lean4-skills - For artifact/bench verification and proof automation: Python 3 and the official comparator, lean4export, and landrun on Linux with a systemd user service; see installation instructions.
Long-running project. Goal: bring real Triton kernels (forward, backward, concurrency, production layouts / autograd) into Lean's proof scope with minimal modification. Live roadmap: #1. Architecture and decision log: PLAN.md.
VeriTile is a collaboration between Zenan Li, Kaiyu Yang, Ziran Yang, Zhaoyu Li, Mike He, and Aarti Gupta.
MIT © 2026 Zenan Li.