Markdown Is a Wish, Lean Is a Contract

Every week someone shows me a new spec-driven workflow for coding agents, and every week it is a folder of markdown. A spec.md, a plan.md, a tasks.md, an AGENTS.md or CLAUDE.md with a “constitution.” The agent reads them, nods politely, and does roughly what it wanted to do anyway.

I don’t think this is a tooling problem that the next release will fix. It is a category error. A markdown spec is a prompt dressed up as a contract. Nothing can fail against it. It enters the agent as context, competes with everything else in the window, and drifts the moment code starts changing. When it is violated, nobody is notified, because there is nobody to notify. There is no referee.

My claim in this essay is deliberately provocative: the future of agentic coding and executable specifications is in verifiable Lean 4, not in markdown. I also want to be fair about what that claim means. Markdown is not going away, and it shouldn’t. It is the right medium for intent. What it cannot be is the contract. The contract has to be something a machine can reject.

Wishes the agent is free to misread

The spec-driven development movement got the diagnosis right. Vibe coding loses intent, and agents need something more durable than a chat history. GitHub’s Spec Kit announcement in September 2025 put it beautifully: we are moving “from ‘code is the source of truth’ to ‘intent is the source of truth,’” because “AI makes specifications executable.”

But read the rest of that same post. GitHub asks for feedback because “Managing lots of Markdown files can get overwhelming,” and it tells the developer that “your role isn’t just to steer. It’s to verify.” That is an admission. The spec does not verify anything. You do.

Birgitta Böckeler’s careful review of Kiro, spec-kit and Tessl on martinfowler.com says the quiet part out loud. “Even with all of these files and templates and prompts and workflows and checklists, I frequently saw the agent ultimately not follow all the instructions.” In one run the agent was told certain classes already existed, “just took them as a new specification and generated them all over again.” Her verdict on review load: “I’d rather review code than all these markdown files.” She also noticed that the specs are written to launch a session, not to govern the codebase: spec-first, “not spec-anchored over time.”

None of this is a failure of diligence. It is what happens when the only enforcement mechanism is a model reading text. A larger context window does not turn a wish into an obligation. martinfowler

What “executable spec” should mean: a spec that can fail

Here is my working definition. A specification is executable when there exists a mechanical procedure that can reject an implementation for violating it. Running it is not enough. Generating code from it is not enough. It has to be able to say no.

Tests are the weak form of this. They can fail, which is why we love them, but they only sample. arxiv This year we got a sharp measurement of how much they miss. The SWE-Proof study, from UC Berkeley, Georgia Tech, UIUC and AWS AI Labs, attached formal specifications to all 500 tasks in SWE-bench Verified and evaluated Claude Opus 4.8. An adversarial audit overturned 26.8% of the patches that passed every hidden test. arxiv A quarter of “green” fixes were wrong on inputs nobody tested.

The part that should end the markdown debate is the control. The researchers also gave the agent a structured natural-language specification in EARS, the requirements notation Kiro uses. It did not close the gap: 17.8 points of the EARS pass rate came from patches that were still distinguishable from the correct fix. Handing the agent a correct formal specification raised resolution from 85.0% to about 95% across the three formal backends, 95.2% under pure Lean. The finding is blunt: a structured non-formal specification “confers none of the improvement that a formal one does.” arxiv

So the difference between markdown and a formal spec is not style. It is whether anything can fail.

Lean as the spec layer

Why Lean 4 specifically, and not just “formal methods”?

Lean is a real programming language and a proof assistant in one. github You can write a reference implementation, run it with #eval, compile it to native code, state theorems about it, and have a small kernel check those theorems. arxiv A specification in Lean is not a comment about the program. It is a type, and an implementation either inhabits it or doesn’t.

Here is a small example: a spec, a reference implementation, and the theorem an agent must prove.

lean

/-- The contract (human-owned): what it means to deduplicate a list. -/
abbrev DedupSpec (xs ys : List Nat) : Prop :=
  ys.Nodup ∧ (∀ x ∈ xs, x ∈ ys) ∧ (∀ y ∈ ys, y ∈ xs)

/-- A reference implementation (agent-owned; runnable). -/
def dedup : List Nat → List Nat
  | [] => []
  | x :: xs => if x ∈ dedup xs then dedup xs else x :: dedup xs

#eval dedup [3, 1, 3, 2, 1]            -- [3, 2, 1]

-- The spec is decidable on concrete inputs, so it doubles as a test oracle:
#eval decide (DedupSpec [3, 1, 3, 2, 1] (dedup [3, 1, 3, 2, 1]))   -- true

/-- The obligation (agent-owned; kernel-checked). -/
theorem dedup_correct (xs : List Nat) : DedupSpec xs (dedup xs) := by
  sorry  -- the agent's job: replace `sorry` with a proof the kernel accepts

Look at what the same artifact does. On a concrete input it executes: it is a test oracle, because the bounded quantifiers make the proposition decidable. Before anyone writes a proof, you can throw random inputs at it with Plausible, Lean’s property-based testing framework, and look for counterexamples. proofsandintuitions When the agent replaces sorry with a proof, the claim holds for every list. And if the agent cheats, the toolchain sees it. sorry and stray axioms show up in #print axioms, and Lean’s Comparator judge checks that a submission proves exactly the stated challenge using only allowed axioms. leangineergithub

Now notice the weak spot, because it is the honest center of this essay. If I had written the spec as just ys.Nodup, then fun _ => [] would satisfy it, and the kernel would happily certify a function that throws your data away. The kernel checks the proof. It does not check that the statement is what you meant. github Hold that thought.

Why now: agents got good at proving

Two years ago this argument would have been academic. In 2025, the Verina benchmark found that the best model produced correct proofs for 4.9% of tasks on the first try. mlanthology Proofs were the wall.

The wall has largely fallen for function-level programs:

  • Claude Code on CLEVER. In May 2026, “Agentic Proving for Program Verification” (Sosso, Arora, Spitters) ran Claude Code in a compiler-in-the-loop setup on CLEVER, a Lean 4 benchmark for verified code generation. It reached 98.1% end-to-end over well-formed entries and certified implementations against ground-truth specs for 87.5% of problems. Along the way it diagnosed “lingering bugs in the dataset.” arxiv

  • Goedel-Code-Prover-8B. This open 8B model reached 62.0% across 427 Lean verification tasks, against 18.5% for GPT-5.3-Codex. Its quickcheck step disproved 47 problems outright with concrete counterexamples. xgithub The prover found broken specs.

  • Leanstral. In March 2026 Mistral released Leanstral, an Apache-licensed Lean 4 agent with 6B active parameters, trained to work through lean-lsp-mcp. On real Fermat’s Last Theorem project PRs it scored 26.3 at pass@2 for $36 of compute, where Claude Opus 4.6 scored 39.6 for $1,650. mistral +3 Proof engineering is getting cheap.

  • Tooling. lean-lsp-mcp gives any MCP-capable agent the goal state, the diagnostics and theorem search. githubplugable The agent sees exactly what a human sees in the editor.

This is not only benchmarks. Microsoft’s SymCrypt team writes new cryptography in safe Rust, translates it to Lean with Aeneas, and proves it against formalized NIST standards. Their development is 237 KLOC of Lean establishing safety, panic-freedom and functional correctness of 16.7 KLOC of Rust, and ML-KEM and SHA-3 already ship in Windows Insider builds. Their engineer Son Ho put it in a sentence I keep quoting: “We are verifying code faster than we can write it.” microsoft +2

There is also a structural reason Lean suits adversarial AI. Reinforcement learning will find every shortcut, and a verifier you cannot cheat is AI-safety infrastructure. githubgithub Leo de Moura reports that Claude Opus 4.6, with expert help, found seven kernel bugs in Rocq. Against Lean it found two bugs in an independent kernel, Nanoda, but no proof of False in Lean’s official kernel. The design keeps the trusted piece tiny: Nanoda implements the full checking logic in under 5,000 lines of Rust. It also keeps that piece plural, with multiple independent kernels continuously tested in the open on the Lean Kernel Arena. github Dafny, F* and Verus, by contrast, sit on Z3’s much larger trusted base. github

The new division of labor

Put these together and a new arrangement of work falls out:

  • Humans own the statements. What must be true: invariants, pre- and postconditions, refinement relations, security properties.

  • Agents own the implementations and the proofs. As many attempts as it takes, in whatever style they like.

  • The kernel arbitrates. Deterministically, cheaply, and without getting tired on the 400th pull request.

This is not my speculation. It is how the people building Lean already work. De Moura’s FLoC 2026 keynote describes the Hex computational-algebra library this way: “Specifications written by hand. Implementations and proofs written by AI.” github He describes Radix, a verified embedded DSL with 52 theorems and about 7,400 lines, built by ten agents over a weekend: “I did not touch the code. Zero lines.” github Kim Morrison describes the payoff of a proved-correct Lean zlib: “This allows us to let AIs loose optimizing the code, requiring that they update the proof whenever the implementation materially changes.” githubgithub The kernel became the reviewer, and the reviewer never sleeps.

Martin Kleppmann predicted in December 2025 that AI would pull formal verification into the mainstream, for three reasons: “formal verification is about to become vastly cheaper; AI-generated code needs formal verification so that we can skip human review and still be sure that it works; the precision of formal verification counteracts the imprecise and probabilistic nature of LLMs.” The evidence from 2026 says he was right about the economics.

Objections, head-on

“A proof only shows the code matches the spec, not your intent.” Correct, and this is the most important objection. De Moura’s own slide says it plainly: “Lean cannot check whether AI autoformalized the statement correctly.” github SWE-Proof measured the problem. When the agent had to write its own spec, it gained nothing over the unaided baseline, and only about 56% of synthesized specs survived audit. The dominant failure was faithfulness: specs that were correct about what they covered but covered too little. arxiv

My answer is that this objection moves the human job; it does not refute the approach. With markdown, the intent gap is invisible and unbounded. With Lean, it is concentrated in a small, readable artifact that you can attack:

  • run it as a test oracle on known cases;

  • fuzz it with Plausible;

  • require that the known-buggy version fails to verify; arxiv

  • check that mutants are rejected; arxiv

  • ask an agent to prove the spec unsatisfiable or vacuous (Vero’s benchmark does exactly this, and it caught real curation errors). arxiv

Reviewing a 100-line statement is a different job from reviewing 10,000 lines of generated diff. That is where human attention should go.

“Specs are too expensive.” They were. A Lean spec module in SWE-Proof had a median of 107 lines and verified in about 10 seconds on average. arxiv The proofs, the historically expensive part, are increasingly the agent’s problem. Write full specs only where wrongness hurts: authorization, money, crypto, parsers, protocol state machines, data invariants. Everywhere else, partial specs (no panics, round-trips, monotonicity) are cheap and still catch real bugs. Be honest about the limits, too. Some changes, such as renames, signature shuffles and pure side effects, have no functional spec at all; SWE-Proof found 22 such tasks among the 266 in SWE-bench Pro. arxiv

“Our code is TypeScript, Python and Rust, not Lean.” This is the strongest practical objection, and AWS answered it years ago with Cedar:

  • Keep the Lean model as the contract, about 10× smaller than the Rust it governs. githubx

  • Prove properties about the model. arxiv

  • Run about 100 million differential random tests nightly against production Rust (per de Moura’s NFM 2026 slides).

  • Gate releases: “A new version of Cedar isn’t released unless its model, proofs, and differential tests are up to date.” amazon

For Rust, Aeneas and Hax translate code into Lean so the proof is about the real thing. runtimeverification +2 TypeScript and Python bridges (LemmaScript, PastaLean) exist but are early. arxiv And Lean is not slow: Morrison’s lean-zip beats Rust’s miniz_oxide on the Silesia corpus at the default level, though it uses more memory and hand-tuned C still wins. github

“Lean is hard and proofs break across versions.” Both true. Off-the-shelf LLMs still succeed more often in Dafny (82%) than in Lean (27%) on one 2025 vericoding benchmark. danielvaughanycombinator Lean releases do break proofs; Leanstral’s showcase case was diagnosing a 4.29 breakage. mistral +2 But maintenance is exactly the toil agents absorb best, and the payoff of Lean’s foundational design is that nothing beneath the kernel needs trusting. If your team needs push-button SMT automation on day one, Dafny or Verus are reasonable choices. If you want a spec layer that is a full programming language, has the deepest AI-prover ecosystem, and has a trusted base small enough to reimplement, Lean is the bet.

A practical adoption path: Lean as the contract layer

You do not need to rewrite anything in Lean to start. You need a contract layer beside the code you already have.

  1. 1.

    Keep markdown for intent. User stories, rationale, non-goals and design discussion belong in prose. Feed them to the agent. Just stop calling them the contract.

  2. 2.

    Pick one high-stakes kernel of logic. An authorization decision, a pricing rule, a state machine, a schema invariant, a parser.

  3. 3.

    Write the Lean spec and an executable reference model. Humans write and review the statement; the agent can draft it, but a human signs off. Validate it before you trust it: #eval on known cases, Plausible for counterexamples, a known-bad version that must fail.

  4. 4.

    Let agents implement and prove. Wire up lean-lsp-mcp in Claude Code, Codex or Mistral Vibe. Forbid sorry and custom axioms in CI, and check submissions with Comparator or #print axioms.

  5. 5.

    Connect the model to production. Use differential testing between the Lean model and your Rust, TypeScript or Python implementation, Cedar-style. Where the language allows it (safe Rust via Aeneas or Hax), prove against the translated code itself.

  6. 6.

    Make the kernel a merge gate. A change that breaks a theorem does not merge. That is the whole point.

This is also how I approach my own work on agent memory. In LeanRDF I treat RDF graphs as typed, verifiable structures in Lean 4. In lean-elpi I pair Lean with Elpi/λProlog as a reasoning layer. My book Bulletproof Knowledge argues that agents need proof-checked memory, not just retrieved memory. The pattern is the same at every layer: let the probabilistic system propose, and let a small deterministic checker dispose.

Closing: intent in prose, contracts in Lean

I titled this piece as if markdown loses. It doesn’t. Markdown is where intent lives, and intent is where humans add the most value. But intent is not a contract, and pretending otherwise is how we end up with agents that comply with the vibe of a document while violating its substance.

The agentic future I want is one where I write down what must be true in a language that can say no. Agents are free to be as creative, fast and numerous as they like in satisfying it, and a few thousand lines of kernel decide whether they did. Markdown carries intent. Lean carries the contract. The kernel is the reviewer.

Originally published on Sovereign Agentic AI on Substack.