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:
generalizeandId.of_wp_run_eqturn the claim about thedoblock into a form thatmvcgencan read.mvcgensplits the claim into one goal for each part of the loop.- The
case inv1line gives the loop invariant: the count is at most the number of entries that the loop read so far,cur.prefix. simp_allandomegaprove each goal.
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:
- Each index of a
raw::loadorraw::storemust be inside its tensor. The compiler proves this before it compiles the program (example). - For a function that returns a reference,
vxc --print-borrow-clausesprints the facts about borrows that the compiler can prove from the body. For thefindfunction of the contracts chapter, it printsfind: ensures !reaches(return, *key): the result does not point intokey. Copy the line into the signature, and it becomes part of the contract.
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
- Fewer kinds of facts. z3 reasons about whole numbers with
+,-,*and%, and about comparisons. Division and floats give it nothing. Lean can state any fact of mathematics. - z3 can fail to prove a true fact. We tried a loop that adds the numbers from 1 to n,
with the invariant
2 * total == i * (i + 1). z3 found neither a proof nor a counterexample. It may have reached its limit of a million steps. In Lean, you add proof steps until the proof passes. In Vx, you state a simpler fact, or check it at run time withassert. - Some loops are not proved yet. The Vx example above takes a tensor of 64
numbers. With a
Vec, the prover proves the same invariant, but notreturn <= v.len()after the loop.Vecsays that its length is never below zero, but the prover does not use the invariants of a struct yet (#2832). - More code to trust. Lean's small kernel checks each step of a proof. Vx trusts z3, and its own translation of the program into questions for z3. In five months, each bug that we found was on the side of Vx, not in z3 (the list).
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.