Formally Verifying Transformers with Lean: Proving Model Invariants from Scratch

When Formal Verification Meets Deep Learning

Formal verification has long been the exclusive domain of mathematical proofs and safety-critical software systems — think aerospace, compilers, and cryptographic protocols. A project called "Lean Verified Transformers" is attempting to bring this rigorous proof machinery to bear on one of deep learning's core architectures: the Transformer.

The central idea is to use the interactive theorem prover Lean to prove a set of Transformer invariants from scratch. Rather than "empirically believing" that a model behaves as expected through extensive test cases, this approach uses mathematical proof to strictly guarantee that certain properties hold for all possible inputs.

What Are "Transformer Invariants"?

In the context of software and algorithms, an "invariant" is a property that remains true before and after a given operation. For Transformers, such invariants might include:

• Shape invariants: Tensor dimensions transform as expected through each layer, with no unexpected dimension mismatches.
• Numerical properties: For example, each row of a softmax output always sums to 1, and attention weights are always non-negative.
• Equivariance/invariance: Symmetry properties of model behavior under certain permutations or transformations.

Using a proof assistant like Lean to "machine-check" these properties offers a compelling advantage: once a proof goes through, it constitutes an airtight mathematical guarantee — not a sampling-based test that might miss edge cases. For builders of high-reliability AI systems, that's a significant draw.

Why Lean Is Well-Suited for This Task

Lean is a theorem prover that has risen rapidly in popularity among mathematicians and the formal methods community in recent years. It combines the expressiveness of a functional programming language with the power of a dependent type system, making it possible to encode "a program satisfies a given specification" as a machine-checkable type proposition.

Re-implementing Transformer computations in Lean and attaching proofs to key steps effectively constructs a "reference implementation with proofs." This stands in sharp contrast to the traditional machine learning engineering paradigm of "write code + unit tests" — it requires developers to have a precise mathematical understanding of every computational step.

---

Dependent types are key to understanding Lean's capabilities. In ordinary type systems, types describe only the kind of data (e.g., integer, string). Dependent types allow types to depend on values — for instance, you can define the type "a vector of exactly length n," where n is a concrete runtime value. For Transformer verification, this means expressing constraints directly at the type level: "a tensor of shape [batch, seq_len, d_model] passed through an attention layer produces output of shape [batch, seq_len, d_model]" — rather than catching violations through runtime assertions.

Lean 4 also unifies "propositions" and "types" via the Curry-Howard correspondence: proving a mathematical proposition is equivalent to constructing a program of a specific type. This allows mathematical proofs to be verified automatically by the compiler like type-checking, fundamentally eliminating the possibility of errors in the proof itself.

Mathlib, the massive mathematical library maintained by the Lean community, already covers substantial ground in linear algebra, analysis, number theory, and more — providing reusable proof building blocks for the matrix operation properties that arise in Transformer verification.

---

From Transformers to "The Rest of the World's Code"

The authors pose a more ambitious question: once we've verified something as mathematically well-structured as a Transformer, how hard would it be to extend the same rigorous proofs to "the rest of the world's code"?

This question cuts to the heart of formal verification's long-standing core bottleneck: verification cost. Writing complete formal specifications and proofs for a piece of code often requires effort that is several to tens of times greater than writing the code itself. Transformers are a relatively friendly starting point precisely because they consist of highly regular operations — matrix multiplication, normalization, attention — with well-defined mathematical properties. Real-world code, by contrast, is riddled with side effects, concurrency, external state, and ambiguous requirements. Specifying such code precisely is itself a challenge, let alone proving anything about it.

The authors are admirably honest in framing this as speculation — more of an exploratory thought experiment than a claim that formal verification can already scale to cover all software.

---

The "specification problem" in formal verification is often thornier than the "proof problem." A specification is a precise mathematical description of what a system should do — but real-world requirements typically exist as natural language, full of ambiguity and implicit assumptions.

Historically, formal verification's success stories are concentrated in domains with sharp boundaries: the seL4 microkernel required roughly 10 person-years to verify approximately 10,000 lines of C code; the CompCert verified compiler took around 6 person-years. What these projects share is that system behavior could be precisely mathematized, with virtually no fuzzy business semantics.

Transformer invariants — like softmax outputs summing to 1 or dimension conservation — are naturally mathematical propositions that require no "translation." This is precisely what makes Transformers such a uniquely favorable starting point for verification, and why the same approach cannot be straightforwardly transplanted to business logic code.

---

Implications for AI Reliability

As large models are deployed in increasingly critical contexts, providing verifiable behavioral guarantees for AI systems is becoming an area of growing interest. Formally verifying Transformers offers at least one approach: start with deterministic architectural properties (like numerical stability and dimensional correctness), establish a provably correct foundation, and gradually extend toward more complex semantic properties.

That said, it's important to be clear-eyed about the limits: verifying that a Transformer's computation graph is correct is not the same as verifying that the model "won't produce harmful outputs" or "reasons correctly." The latter involves learned weights and semantic-level questions that are far beyond the reach of current formal methods.

The value of this work lies primarily in demonstrating a path for bringing rigorous mathematical tools into deep learning infrastructure — and in its candid reflection on just how far that path can realistically go.

Note: This article is based on a brief Twitter introduction to the project. For specific proof details, please refer to the original link and code repository.