Let Vx handle Lean proofs for you

TL;DR — A Lean proof has two parts. The theorem says what you want to be true. The proof steps tell Lean why it is true. A programmer cares about the theorem. In Vx you write only that part, as a contract on the function that you compile, and the compiler asks the z3 solver for the proof on every build. Vx does not write Lean. For the facts that C, C++ and Rust programmers need most, you do not need Lean: offsets that stay inside a buffer, numbers that do not overflow, and what a loop keeps true.

Lean is a language for proofs. It checks each step of a proof, so a proof that Lean accepts is correct. Few programmers who write C, C++ or Rust write Lean proofs. In the Vx repository, each of the 51 commits that added our 18,446 lines of Lean names an AI agent as a co-author. When a machine writes the proof steps, a person reads the theorem. The theorem is the part that says what the program must do. This post shows two facts, first in Lean and then in Vx.

A loop in Lean

Here is a function that counts the entries of an array that are above zero, and a proof that the count is at most the size of the array:

import Std.Tactic.Do
open Std.Do

-- How many entries of `xs` are above zero.
def countPositive (xs : Array Int) : Nat := Id.run do
  let mut count := 0
  for x in xs do
    if x > 0 then
      count := count + 1
  return count

theorem countPositive_le (xs : Array Int) : countPositive xs ≤ xs.size := by
  generalize h : countPositive xs = r
  apply Id.of_wp_run_eq h
  mvcgen
  case inv1 => exact ⇓⟨cur, count⟩ => ⌜count ≤ cur.prefix.length⌝
  all_goals simp_all <;> omega

The theorem is one line: countPositive xs ≤ xs.size. The five lines after by tell Lean how to prove it:

Only the invariant says something about the program. The other lines are instructions for Lean. Change count + 1 to count + 2, and Lean answers:

CountPositive.lean:17:25: error: omega could not prove the goal:
a possible counterexample may satisfy the constraints
  c ≥ 0
  b ≥ 1
  a ≥ 0
where
 a := ↑r
 b := cur✝
 c := ↑b✝

The names ↑r, cur✝ and ↑b✝ come from inside the proof. None of them is in the program.

The same loop in Vx

// How many of the 64 scores are above zero.
fn count_positive(x : &Tensor<i64, [64]>) -> i32
    ensures 0 <= return && return <= 64
{
    let mut count : i32 = 0;
    for i in 0..64 invariant 0 <= count && count <= i {
        if x[i] > 0 {
            count = count + 1;
        }
    }
    return count;
}

fn main() -> i32 {
    let mut x = Tensor<i64, [64]>::fill(-1);
    x[3] = 7;
    x[40] = 2;
    println!("{}", count_positive(&x));
    return 0;
}

The program prints 2. The contract has two lines. ensures says what the function promises. invariant says what is true at the start of each pass of the loop. Both lines are about the program, and there are no proof steps. The compiler turns the function into facts and asks z3 whether some input breaks the promise. An earlier post shows the questions that it sends. Change count + 1 to count + 2, and the build stops:

Error[E8009] at count_positive.vx:6:41: this loop invariant `(0 <= count) && (count <= i)` may not hold for the next `i` after a pass through the loop body: the compiler cannot prove it from what it knows at the end of the body

You still write the invariant. It is part of what you mean: each pass adds at most one to the count. The error names the line, the invariant and the place where it can fail.

The proof is about the program you run

A Lean proof is about a Lean function. If your program is in C++ or Rust, the Lean function is a second copy of it, and the copy can differ from the program in ways that the proof does not see.

Here is the offset of one number in the KV cache of Llama 3.1 70B, with 80 layers, a context of 32,768 tokens, and 8 heads of 128 numbers. The layout is the one in Proving tensor indices at compile time:

-- Llama 3.1 70B KV cache, laid out as [layer][position][head][dim].
def kvOffset (layer pos head d : Nat) : Nat :=
  ((layer * 32768 + pos) * 8 + head) * 128 + d

theorem kvOffset_lt (layer pos head d : Nat)
    (h₁ : layer < 80) (h₂ : pos < 32768) (h₃ : head < 8) (h₄ : d < 128) :
    kvOffset layer pos head d < 2684354560 := by
  unfold kvOffset
  omega

#eval kvOffset 79 32767 7 127

omega proves it, and #eval prints 2684354559, the last offset. The theorem is true. But it is about Nat, numbers with no largest value. If the program computes this offset in 32-bit integers, the last multiplication overflows: 2,684,354,559 is larger than the largest 32-bit signed integer, 2,147,483,647.

To prove a fact about the 32-bit program, you write another copy in BitVec 32, Lean's 32-bit numbers, and another proof:

import Std.Tactic.BVDecide

-- The same offset, in the 32-bit integers that the program uses.
def kvOffset32 (layer pos head d : BitVec 32) : BitVec 32 :=
  ((layer * 32768 + pos) * 8 + head) * 128 + d

theorem kvOffset32_nonneg (layer pos head d : BitVec 32)
    (h₁ : (0#32).sle layer ∧ layer.slt 80#32) (h₂ : (0#32).sle pos ∧ pos.slt 32768#32)
    (h₃ : (0#32).sle head ∧ head.slt 8#32) (h₄ : (0#32).sle d ∧ d.slt 128#32) :
    (0#32).sle (kvOffset32 layer pos head d) := by
  unfold kvOffset32
  bv_decide
KvOffset32.lean:12:2: error: The prover found a counterexample, consider the following assignment:
layer = 64#32
pos = 0#32
head = 0#32
d = 0#32

With layer = 64, the offset is 231, one more than the largest 32-bit signed integer. With BitVec 64, the same proof passes. Lean found the overflow, but only in the copy that used the program's numbers.

In Vx there is one copy. The contract is on the function that the compiler compiles, in the numbers that the function uses:

// Llama 3.1 70B KV cache, laid out as [layer][position][head][dim].
fn kv_offset(layer : i32, pos : i32, head : i32, d : i32) -> i32
    requires 0 <= layer && layer < 80 && 0 <= pos && pos < 32768
    requires 0 <= head && head < 8 && 0 <= d && d < 128
    ensures 0 <= return && return < 2684354560
{
    let row = (layer * 32768 + pos) * 8 + head;
    return row * 128 + d;
}

fn main() -> i32 {
    print(kv_offset(79, 32767, 7, 127));
    return 0;
}
Error[E8001] at kv_offset.vx:8:5: Function 'kv_offset' cannot prove postcondition (ensures) at compile time

Change each i32 in kv_offset to i64, and the program compiles and prints 2684354559.

In October, Vx had the same gap as the Nat copy. z3 got integers with no largest value, so this contract passed, and the program printed -1610612737. Since 1 November, the compiler gives z3 each +, - and * with the wraparound of its type. We fixed it once, in the compiler, for every program.

Facts with no contract

Some facts need no contract at all:

Where we use Lean

Lean is the right tool for some facts. Vx promises that a program has no data race outside unsafe code, and that the runtime reports each deadlock and nothing else (What Vx guarantees about concurrency). These are facts about every Vx program, not about one function, and z3 cannot state them. So they are Lean proofs, in formal/memory_model/lean: 60 files and 18,446 lines.

Those proofs have the gap of the Nat copy. They are about a model of the checker in vxc, not about vxc itself, and the book says so. But one model covers every program. You would need a new copy for each program that you want to prove. We write Lean for the language, so that you do not need to write it for your program.

What you give up

Write what you mean

A contract in Vx is a theorem without proof steps. You write what a function needs and what it promises, next to its code. The compiler checks it on every build, in the numbers that the program uses. The contracts chapter shows what the prover knows, and how to give it a fact that it is missing.

We compiled the Vx programs with vxc from main at commit 9f847dd64 and z3 4.13.3 on Ubuntu, and checked the Lean files with Lean 4.35.0. Lean 4.35 warns that mvcgen is deprecated. Tell us about a fact that you want Vx to prove, on r/vxlang.