Towards Multi-language Program Verification for AI

Raúl Raja Raúl Raja CTO at Predictable Machines

David Mazarro David Mazarro Founding Engineer at Predictable Machines

2026

AI enables faster development, but less reliable outputs

time code written checked AI assistants written checked the gap

Harder to review and keep up with code being written at a much faster pace

=

More pressing need to provide software verification solutions

The story of this talk

Functional programming AI Formal verification Dependent types

Testing is effective to show the presence of bugs, but not their absence

Headline!!

Edsger W. Dijkstra

How many test cases would it take?

Sometimes, testing could rule out bugs if you test all possible inputs, but:

Function

Possible inputs

Test all inputs?

and(Bool, Bool): Bool

2×2=42 \times 2 = 4

yes

multiply(Int32, Int32): Int32

232×232≈1.8×10192^{32} \times 2^{32} \approx 1.8 \times 10^{19}

impractical

toUpper(String): String

∞\infty

impossible

... so yeah, not really

A sea of inputs

unit tests check individual inputs some buggy input PBT and fuzzing can explore further 🔥 🔥but some bugs can still go unnoticed formal verification checks every input

For any given program, you have a sea of possible inputs and expected behaviors

Testing doesn't cover all behavior

unit tests check individual inputs some buggy input PBT and fuzzing can explore further 🔥 🔥but some bugs can still go unnoticed formal verification checks every input

Formal verification

Formal verification

What is formal verification?

“Formal verification is a set of techniques used to prove the correctness of a program against a given formal specification”

Correctness: a program is correct if it behaves as specified

Prove: use mathematical techniquesthese are the famous formal methods! to guarantee this correctness

…

so what about formal specification?

What is a specification?

A specification is a description of a program's behavior

function withdraw(acc: Account, amount: number): Account {
  acc.balance -= amount;
  acc.history.push({
    withdrawn: amount,
    balanceAfter: acc.balance,
  });
  if (amount >= 1000) {
    acc.flaggedForReview = true;
    sendEmail(acc.owner, "Large withdrawal");
  }
  db.accounts.save(acc);
  return acc;
}

“If amount is positive and does not exceed the account's balance, withdraw subtracts amount from the balance and records the withdrawal in some history. If amount is 1000 or more, the account is flagged for review and the account holder is emailed. It then saves the account and returns it. The balance never goes negative.”

Formal specifications through Hoare logic

Hoare logic (C. A. R. Hoare, 1969) is a logical framework useful for describing what a program does from what must hold before and after it runs

{ P }\{\,P\,\}precondition CCprogram { Q }\{\,Q\,\}postcondition

Hoare triple

If the precondition PP holds before running the program CC, the postcondition QQ holds after

Function contracts

Hoare logic allows us to precisely state contracts for our programs

function withdraw(acc: Account, amount: number): Account {
  acc.balance -= amount;
  acc.history.push({
    withdrawn: amount,
    balanceAfter: acc.balance,
  });
  if (amount >= 1000) {
    acc.flaggedForReview = true;
    sendEmail(acc.owner, "Large withdrawal");
  }
  db.accounts.save(acc);
  return acc;
}

Partial withdraw contract

“If amount is positive and does not exceed the account's balance [...] the balance never goes negative.”

{ 0<amount≤acc.balance }withdraw(acc, amount){ acc.balance≥0 }\begin{gathered} \{\,0 < \texttt{amount} ≤ \texttt{acc.balance}\,\} \\ \texttt{withdraw(acc, amount)} \\ \{\,\texttt{acc.balance} ≥ 0\,\} \end{gathered}

Example: safely getting an array element

For an array a where a.get(i) throws an exception out of bounds

a0 a1 a2 a3 a a.get(2) a2 a0 a1 a2 a3 a a.get(4) 💥 exception

Example

{ 0≤i<a.size() }\{\,0 \le \texttt{i} < \texttt{a.size()}\,\}the index must be in bounds r = a.get(i)\texttt{r = a.get(i)}⟹ { r=ai }\{\,\texttt{r} = a_{\texttt{i}}\,\}the returned element is the one found at position i

a0,a1,…a_0, a_1, \ldots are the elements of a, in order

Verification tools

A programming language defines a program and a specification language defines a specification; a verification tool checks whether the program matches the specification. If not, the program needs to be fixed; if so, it is correct, assuming the specification accurately reflects your expectations.

Formal verification covers all behavior

unit tests check individual inputs some buggy input PBT and fuzzing can explore further 🔥 🔥but some bugs can still go unnoticed formal verification checks every input

Static types

// Calculate the area of a rectangle
function findArea(x: number, y: number): number {
  return x * y;
}

Formal specification: the function findArea takes two numbers as arguments and returns a number

So the type system of your statically typed language is indeed a formal verification tool!

How this translates to functional programming

Functional programming

Functional programming and logic

Functions with types

Logical propositions

function checkIn(t: Ticket, id: Passport | IdCard):
    BoardingPass | Overbooked

Ticket && (Passport || IdCard)
→ BoardingPass || Overbooked

function refund(o: Overbooked): Refund

Overbooked → Refund

function board(b: BoardingPass): OnBoard

BoardingPass → OnBoard


function travel(t: Ticket, id: Passport | IdCard):
    OnBoard | Refund {
  // ?
}
function travel(t: Ticket, id: Passport | IdCard):
    OnBoard | Refund {
  return board(checkIn(t, id));
}  the Overbooked case is not handled
function travel(t: Ticket, id: Passport | IdCard):
    OnBoard | Refund {
  const result = checkIn(t, id);
  switch (result.kind) {
    case "boardingPass": return board(result);
    case "overbooked":   return refund(result);
  }
}

Ticket && (Passport || IdCard)
→ OnBoard || Refund ?✗ could not prove✓ proved
board needs a BoardingPasscheckIn gives a BoardingPass | Overbookedwe are not handling the Overbooked case, so the type checker gives an errorevery case is handled, so the type checker accepts it: it checked that our proof is sound

“Can we implement this?” = “Can we prove this?”

“We have an implementation” = “We have a proof”

Logic as types: the Curry-Howard correspondence

The class asks Bart to say the line, and Bart says: this is called the Curry-Howard correspondence.

Check out this talk: “Propositions as Types”, Philip Wadler, Strange Loop 2015

Going back to our withdraw example

function withdraw(acc: Account, amount: number): Account {
  // ...
}

Formal specification: the function withdraw takes an account and a number as arguments and returns an account

But it is missing something…

const acc = new Account(100);

withdraw(acc, 30);   // balance: 70
withdraw(acc, 60);   // balance: 10
withdraw(acc, 50);   // balance: -40

Partial withdraw contract

{ 0<amount≤acc.balance }withdraw(acc, amount){ acc.balance≥0 }\begin{gathered} \{\,0 < \texttt{amount} ≤ \texttt{acc.balance}\,\} \\ \texttt{withdraw(acc, amount)} \\ \{\,\texttt{acc.balance} ≥ 0\,\} \end{gathered}

Call

Type checker

Precondition

Postcondition

withdraw(acc, 30)

well-typed ✓

0<30≤1000 < 30 ≤ 100 ✓

70≥070 ≥ 0 ✓

withdraw(acc, 60)

well-typed ✓

0<60≤700 < 60 ≤ 70 ✓

10≥010 ≥ 0 ✓

withdraw(acc, 50)

well-typed ✓

0<50≤100 < 50 ≤ 10 ✗

−40≥0-40 ≥ 0 ✗

The type checker is still missing something to verify that the function is always called safely…

Introduction to dependent types

Dependent types

Types that depend on the arguments

Dependent types allow us to encode function contracts by allowing us to refer to arguments in the type itself

def get : (a : List α) → (i : Nat) → (h : i < a.length) → { r : α // r = a[i] } | x :: _, 0, _ => ⟨x, rfl⟩ | _ :: xs, i + 1, h => ⟨get xs i (by grind), by grind [get]⟩

Contract for get

{ 0≤i<a.size() }r = a.get(i){ r=ai }\begin{gathered} \colorbox{#EDDAC5}{$\{\,0 \le \texttt{i} < \texttt{a.size()}\,\}$} \\ \texttt{r = a.get(i)} \\ \colorbox{#BED7E4}{$\{\,\texttt{r} = a_{\texttt{i}}\,\}$} \end{gathered}

The type checker as the verification tool

A dependently typed programming language holds both the specification, the type of get, which only accepts an index i smaller than the length of the list a and returns the element at that index, and the program, its body; the type checker checks whether the program type checks. If not, the program needs to be fixed; if so, it is correct, assuming the specification accurately reflects your expectations.

def get : (a : List α) → (i : Nat) → (h : i < a.length) → { r : α // r = a[i] } | x :: _, 0, _ => ⟨x, rfl⟩ | _ :: xs, i + 1, h => ⟨get xs i (by grind), by grind [get]⟩

Contract for get

{ 0≤i<a.size() }\{\,0 \le \texttt{i} < \texttt{a.size()}\,\} r = a.get(i)\texttt{r = a.get(i)} { r=ai }\{\,\texttt{r} = a_{\texttt{i}}\,\}

Contracts as theorems

def withdraw (acc : Account) (amount : Nat) : Account := -- ... theorem withdraw_nonneg (acc : Account) (amount : Nat) -- precondition (h : 0 < amount ∧ amount ≤ acc.balance) : -- postcondition (withdraw acc amount).balance ≥ 0 := by grind [withdraw]

Hoare triple

{ 0<amount≤acc.balance }withdraw(acc, amount){ acc.balance≥0 }\begin{gathered} \colorbox{#EDDAC5}{$\{\,0 < \texttt{amount} ≤ \texttt{acc.balance}\,\}$} \\ \texttt{withdraw(acc, amount)} \\ \colorbox{#BED7E4}{$\{\,\texttt{acc.balance} ≥ 0\,\}$} \end{gathered}

You can define a function with “regular” types and keep the contract as a separate theorem

Hoare triples in Lean

In Lean, there is even a dedicated syntax for Hoare triples for stateful code verification

def withdraw (amount : Nat) : StateM Account Unit := do -- ... theorem withdraw_spec (amount : Nat) : ⦃ fun (acc : Account) => 0 < amount ∧ amount ≤ acc.balance ⦄ withdraw amount ⦃ fun _ acc => acc.balance ≥ 0 ⦄ := by vcgen [withdraw] grind

Hoare triple

{ 0<amount≤acc.balance }withdraw(acc, amount){ acc.balance≥0 }\begin{gathered} \colorbox{#EDDAC5}{$\{\,0 < \texttt{amount} ≤ \texttt{acc.balance}\,\}$} \\ \texttt{withdraw(acc, amount)} \\ \colorbox{#BED7E4}{$\{\,\texttt{acc.balance} ≥ 0\,\}$} \end{gathered}

A language with a dependent type system gives us a super powerful formal verification tool “for free”

“Solving” formal verification for different programming languages

A miner turns back just before a wall of diamonds labelled Java, Kotlin, TypeScript, C/C++, JavaScript and Python.

Predictable Code: our code verification platform

We are working on Predictable Code, a platform that uses formal verification techniques to reveal hidden bugs and check that code does what its requirements say, in the languages teams already use

Requirements

what the code should do,

defined as specifications

Code

aimed at languages like

Java, TypeScript or Python

Engine

being implemented in Lean

(for the most part)

One verification tool per check?

Approach #1: implement a verification tool per check

but each tool has to implement support for each programming language

JavaKotlinTypeScriptC#JavaScript…Verification toolNull safetyVerification toolBounds & overflowVerification toolContracts…

One verification tool per language?

Approach #2: implement a verification tool per programming language

but each tool has to implement all the checks for each programming language

Verification toolNull safetyBounds & overflowContracts…JavaVerification toolNull safetyBounds & overflowContracts…KotlinVerification toolNull safetyBounds & overflowContracts…TypeScriptVerification toolNull safetyBounds & overflowContracts…C#Verification toolNull safetyBounds & overflowContracts…JavaScript…

One verification tool for a common language

Approach #3 (our choice): translate programs to a common intermediate representation (IR) and implement a single verification tool for that

Verification tool IR Intermediate representationfunctions, branches, calls, effects, types...High-level languagesmany constructs, many semanticsLower levela common semantic groundA single verification frameworkfor the intermediate representation JavaKotlinTypeScriptC#JavaScript… Null safetyBounds & overflowContracts…

Our current approach for Predictable Code

Source Compiler front end Common IR Engines Verdicts Java Kotlin TypeScript C# Spoon on Eclipse JDT K2 compiler plugin tsc Roslyn Predictable IL on the IL, nothing runs running the source code IL deciders structural defects and bug patterns IL verifier requirements and unsafe operations Witness generates tests that reproduce bugs defect verified violated undecided reproduced bug

We are still figuring out what works best for us and our partners

IL deciders look for structural bugs

JavaCompletableFuture<Void> mail.sendAsync(acc.owner(), msg); KotlinDeferred<Unit> scope.async { sendEmail(owner, msg) } TypeScriptPromise<void> sendEmail(acc.owner, msg); C#Task SendEmailAsync(acc.Owner, msg); Predictable IL call sendEmail type async result unused IL decider asyncResultDropped reports async calls with an unused result defect: sendEmail is not awaited

A single IL decider detects this bug in all four languages

A dropped async call in Predictable Code

The Predictable Code defects view on the talk's withdraw function: the work sendEmail starts is dropped, with the explanation, a counterexample, the violated requirement and the code, line 30 of account.ts highlighted.

Line 30 sends the email without awaiting it

IL verifier checks requirements

function withdraw(acc: Account, amount: number): Account {
  acc.balance -= amount;
  // history, email, save
  return acc;
}

Partial withdraw contract

{ 0<amount≤acc.balance }withdraw(acc, amount){ acc.balance≥0 }\begin{gathered} \{\,0 < \texttt{amount} ≤ \texttt{acc.balance}\,\} \\ \texttt{withdraw(acc, amount)} \\ \{\,\texttt{acc.balance} ≥ 0\,\} \end{gathered}

The returned balance acc.balance - amount may be below 0

Every caller must satisfy the precondition

Call

Precondition

IL verifier

withdraw(acc, 30)

0<30≤1000 < 30 ≤ 100 ✓

verified ✓

withdraw(acc, 60)

0<60≤700 < 60 ≤ 70 ✓

verified ✓

withdraw(acc, 50)

0<50≤100 < 50 ≤ 10 ✗

violated ✗

The specification of withdraw in Predictable Code

The Predictable Code specifications view on withdraw: the English specification from the talk and its one requirement, that the balance of the result is at least 0, violated; below it, the line of withdraw that subtracts with no check.

Line 23 violates the requirement that the balance never goes negative

Witness tests to reproduce bugs

The witness reproduces a violation with a test in the project's language

From the verifier violated withdraw can leave the balance below 0 Java/Kotlin/C#/TS driver writes a test in Java/Kotlin/C#/TS with no dependencies The project's own runner runs it on a copy of the code the working tree stays unchanged
// generated: no dependencies
const acc = openAccount("ada", 10);
assert(withdraw(acc, 50).balance >= 0);
  • violated ✗: the test reproduces the bug, with a balance of -40

  • held ✓: the test passes

  • unexercised: the test cannot reach the call

Towards formal semantics

Formal semantics at the different layers of the pipeline would allow for provably correct translations between software representations

Source program Ttranslate IR semantics semantics ⟦ P ⟧src ⟦ T(P) ⟧IR ≈ proved “equivalent”

Sadly, almost no mainstream programming language provides official or complete formal semantics

Our choice to build this verification platform:

A programming language with a dependent type system + interactive theorem proving capabilities

An expressive programming language and type system in the same package: huge flexibility to try different approaches to these problems

Out-of-the-box building blocks for software verification, such as vcgen

Extensibility: teams can mold and shape its capabilities to their needs

But there are others too

Lean is the trendy thing in this field as of 2026, but there are other dependently typed programming languages / theorem provers:

Agda logo

Agda

Idris logo

Idris

Rocq logo

Rocq

Isabelle logo

Isabelle/HOL

Typical challenges, and where AI changes the picture

AI

Where it gets better: maintenance

Software development is way faster in general, and maintenance of projects is easier now

PROOFS The code changes A proof breaks AI proposes a fixed proof The kernel re-checks it a wrong proof does not type check, so AI tries again LANGUAGE INTEGRATIONS A language changes Its integration breaks AI updates it The tests re-check it a wrong update fails the tests, so AI tries again

An agent fixes withdraw, and the analysis decides when it is done

A Predictable Code agent run implementing the withdraw specification: it succeeded; the agent notes that withdraw(acc, 50) on a balance of 10 now throws instead of leaving the balance at -40; the run is implemented, every requirement verified by the analysis; and the notification says Withdraw is implemented and verified, with no new defect.

withdraw(acc, 50) on a balance of 10 now throws an error

AI challenges: autoformalization

Requirement “Withdrawals over 1000€ are flagged for review.” LLM autoformalization Formal specification ∀ acc n, n > 1000 → (withdraw acc n).isFlagged Lean ✅ checked by the kernel nothing checks that the specification says what we meant

Is > right? If “over 1000€” was meant to include 1000€, maybe it should be ≥ (and if so we are verifying the wrong requirement)

Open question: how do we check that a specification says what we meant?

AI challenges: from intent to requirements

Prompt “@claude implement a feature for booking seats, make no mistakes” Requirements the LLM wrote the seat exists mark the seat as taken send a confirmation Ana books 12A Ben books 12A Seat 12A 2 bookings ↑ at the same moment Missed requirement A given seat cannot be booked by more than one person

(this is not just hard for AI, writing complete specifications is hard for humans too!)

Granularity of specifications vs. verifiability

generality verifiability index in bounds no null dereference balance ≥ 0 withdrawals are recorded in order large withdrawals are flagged “the bank is fair”

There is no general, hands-⁠off approach to turn natural language requirements into formally verifiable requirements

Automation Verifiability fully hands-off not possible

At Predictable Machines, we are navigating this spectrum to find practical verification solutions for our partners

Automation Verifiability fully hands-off not possible

Our takeaways

AI calls for verification solutions

Recent AI-based software development lifecycles have spurred the need for better verification solutions beyond testing and code reviews, and formal verification is one of the most promising fields for this

AI makes formal verification easier

At the same time, AI pairs exceptionally well with theorem provers, making writing complex proofs take a fraction of the time and effort (although at the expense of understanding and readability)

Formal verification is not a silver bullet

“All our endpoints must have a P99 under 500 ms”

is a valid + unambiguous + verifiable requirement, but cannot be formally verified (without making many assumptions)

Closing the gap

time code AI assistants written the gap checked checked

Questions?

Thank you!