TLAPS-Bench: Formally Proving Correctness Of Real-World System Specifications With TLA+ Proof System
TLA+ specification language has long been associated exclusively with TLC model checker in most people's minds. Model checking with TLC finds bugs fast, but it only covers the configuration you give it, and is cheap only for small configurations (3 nodes, value ranges "1..4", etc.). There is also the TLA+ Proof System, TLAPS, which checks a deductive proof, instead of enumerating states like model checking. After you write the proof in TLA+ as a hierarchy of numbered steps, TLAPS turns each step into proof obligations and hands them to backend provers. Being a prover, TLAPS can cover all configurations at once, but it requires a lot of expertise and effort. I had always stayed away from TLAPS, because I hadn't felt I am up to the challenge. You have to figure out the inductive invariant (see below), show every action preserves it, and divide the argument into obligations small enough for Z3, Isabelle, or LS4 to check. So in practice what ends up happening is that almost everyone model checks and almost nobody proves.
Well, like with most things in our industry, this changed drastically in the last year. Earlier this summer, my mind was blown when I saw Claude doing TLAPS proofs! Holy molly, I didn't have this on my bingo card for this year! I knew it would be smart to invest more on this, and it turns out Tianyin Xu, Qian Cheng, and Markus Kuppe were already working on it, and they had a paper in the works. I joined the team late, and I am not sure if I was able to contribute significantly. It was great to collaborate and associate with such a qualified team nevertheless.
The paper is now on arXiv, and the code is on GitHub. The paper asks how much of the proof burden the agents can carry today, and introduces a benchmark and a harness to investigate this. TLAPS-Bench is a benchmark of 265 proof targets from 95 TLA+ specs of real systems and protocols. Tilapia is the harness that runs agents on those targets, and it provides the proof checker, the model checkers, the proof libraries, and the guards that keep agents from cheating. We evaluated on the 70 hardest targets, and the best model proved 44.3% of them. I hope the labs use TLAPS-Bench to train agents to get a lot better at proofs, and at autoformalization in general, over the next few model releases.
What's new here?
Most verification benchmarks are limited proof-completion tasks. They hand the model a scaffold. Selene and FVELer pull lemmas out of seL4's Isabelle proof. CoqStoq and VeriSoftBench pull theorems out of finished Rocq and Lean projects. NTP4VC supplies the verification conditions. VeruSAGE-Bench and Laurel extract functions from systems that were already verified. The model gets the helper lemmas, the intermediate invariants, or the theorem dependency structure, and fills in the gaps. TLAPS-Bench gives it none of that.
The second difference is scope. Dafny, Verus, and Lean benchmarks target the functional correctness of a single function, API, or module. Even the ones that ask the model for an invariant (DafnyBench and VerusBench), want a loop invariant inside one function. None of these asks for the inductive invariant of a distributed protocol. In contrast, TLAPS-Bench attacks this head on. The properties in TLAPS-Bench are about the whole system over time: no two leaders in a term, committed entries survive crashes, transactions serialize, cache lines stay coherent.
A recent paper, TLA-Verus, advocates translating TLA+ specs into Verus and proves them there, stating incorrectly that TLAPS cannot prove arbitrary temporal properties. (Writing `BY PTL` on a proof step tells TLAPS to treat that step as propositional temporal logic and send it to LS4, an LTL decision procedure.) On the contrary, translating out of TLA+ also means leaving the temporal logic behind. Verus verifies Rust, and it knows nothing about [] and <>, so you get temporal logic only as a library via Anvil. Anvil built always, eventually, leads_to, and WF1 on top of Verus. Lean, which has been getting a lot of deserved coverage lately, is in the same position. Lean is a general purpose proof assistant, so to reason about a protocol you write your own state machine and your own temporal operators, or borrow from another framework, like Veil. In TLA+ the state machine comes included with the language. You write variables, an initial predicate, and actions as before/after relations, and "always", "eventually", "leads_to" come with the logic. A behavior is an infinite sequence of states, and the spec and the property you want of it are both formulas over those behaviors. Verus and Lean are built for different jobs, and they are good at them. But TLA+ is where the state machine and the temporal logic come built in.
Refinement is the other thing you get for free in TLA+. To show that an implementation satisfies its abstract spec, you just write an implication between two temporal formulas. For each variable in the abstract spec, you supply a "refinement mapping" that computes it from the implementation's variables. Then you prove Concrete => Abstract, with the same prover you use for everything else. In other systems, refinement is machinery you have to build (via establishing/proving a simulation relation between the two state machines). Since TLA+ hands refinement to you as implication, TLAPS-Bench can carry refinement targets next to the safety and liveness ones, like Wildfire's cache coherence protocol refining the Alpha memory model. Nice!
So TLA+ lets you state the global system properties you actually care about, and TLAPS proves it for every configuration rather than the few small ones TLC can enumerate. This combination is what our benchmark builds on. TLAPS-Bench gives the agent a spec and a target theorem such as Spec => []LeaderUniqueness. These targets come from real system specs (etcd Raft, HashiCorp Raft, ZooKeeper, CCF, MongoDB distributed transactions), and include liveness and refinement, not just safety. The full collection has 95 specs and 265 targets, but the easy ones have been taken out. Classics like Paxos, Bakery, and Byzantine Paxos are things current agents already prove, so they sit in the appendix. (I can't believe I typed that. We are talking about the agents proving Byzantine Paxos out of the box!) What remains is an active set of 70 hard targets across 12 specs. The results in our paper cover only this active set, and the best model proved 31 of the 70 targets. This leaves plenty of room in our benchmark for the AI labs to tackle.
Falsify before you prove
This is the idea I like best in the paper. It shows how versatile the TLA+ ecosystem is. TLC and Apalache read the same TLA+ module TLAPS is working on, and they shoot down a bad candidate invariant in seconds, before the prover spends anything on it. Let me explain.
Let's start with what an inductive invariant is, since the rest of the section depends on it. You have a safety property Inv, and you want it to hold in every reachable state. A model checker gets there by enumerating the reachable states. A proof cannot enumerate, so it uses induction, and for that you need an IndInv with three properties: Init => IndInv, IndInv /\ Next => IndInv', and IndInv => Inv. The first two say the states satisfying IndInv include all initial states and are closed under the transition relation, so they include every reachable state. The third says IndInv still fits inside the property you wanted. So IndInv is squeezed from both sides. It has to be loose enough to be closed under Next, and tight enough to stay inside Inv.
Finding an inductive invariant is a guess-and-check loop. You guess a candidate, try to prove it, fail, stare at the failed obligation, and guess again. On TLAPS alone, each turn of that loop is slow and expensive. A failed SMT obligation says "unknown", and you are left to work out whether the candidate is false, too weak, or just needs a better decomposition.
So the idea is to put a model checker in the loop. TLC answers "is this candidate even true?" in seconds, and when the answer is no, it hands back a counterexample. That is much richer feedback than "unknown", because it shows exactly which state breaks which conjunct.
Figure 3 shows this loop. Let's say the agent wants to prove mutual exclusion via a token. It proposes as inductive invariant that "exactly one node holds the token". TLC returns a violation trace where node A sends the token and, while the message is in transit, no node holds it. So the agent refines to "exactly one node or in-transit message holds the token." TLC finds no violation, and this tells the agent that the candidate is worth proving for any number of nodes.
Apalache, being symbolic, brings a real advantage to the table. Instead of listing states one at a time, Apalache compiles the spec and a bounded number of steps into SMT constraints and asks Z3 whether a violation exists anywhere in that bound. That is what we want here, because it can start from every state satisfying a predicate, not just the states you can afford to list.
Our recipe is three checks. Write the candidate as IndInv == TypeOK /\ H, where TypeOK pins the domain of every variable and H carries the content. First, start from the real initial states and check the candidate holds there in zero steps: that is Init => IndInv. Second, start from /any/ state satisfying the candidate, take one step, and check the candidate still holds: that is IndInv /\ Next => IndInv'. Third, start from any state satisfying the candidate and check the target property holds in zero steps: that is IndInv => Inv. The second check is the interesting one. Starting from all candidate states rather than only the reachable ones makes this a true test of inductiveness. These three TLAPS obligations are falsified cheaply before we pay to prove them.
Apalache's symbolic encoding comes with the constrain that it has to type the spec. TLA+ is untyped set theory: a variable can hold a number in one state and a set of records in the next, and nothing in the language complains. But SMT has to know, so Apalache asks you to annotate every constant and variable with a type and infers the rest. When Apalache can't type the spec, we fall back to TLC with a trick from Lamport: make the candidate its own initial predicate (INIT IndInv, INVARIANT IndInv). This is the same inductiveness test as Apalache's second check, but this time performed by brute force instead of symbolically. TLC has to list every state satisfying the candidate before taking a step, and that list explodes quickly. To keep this tractable, we put each conjunct right after the TypeOK clauses that bind its variables so TLC prunes early, and sample large domains with RandomSubset. (I guess this might sound like gooble-de-gook to you, but you would have appreciated this if you had worked hands-on with TLC.)
Again, all of this is for identifying the inductive invariant. TLAPS gives definitive irrefutable proof after we identify an inductive invariant.
You Can't Cheat the Tilapia
We named our agentic framework Tilapia (TLA+ Proof Infrastructure for Agents). Beside the phonetic fit, we also went for a subliminal message here. Tilapia is about the toughest fish out there. It tolerates low oxygen, murky water, wide temperature swings, and brackish water, and it eats nearly anything. It is the cockroach of the pond.
Tilapia gives each run its own Docker container with pinned versions of the four TLA+ tools: SANY for parsing, TLAPS for proofs, TLC and Apalache for model checking. The container also holds the TLAPS library and CommunityModules for set and sequence theorems, two skills that teach the agent the model checking recipes from the previous section, and a check_proof_bin command that gives the same verdict the final grading gives. A task is three modules: the model, the target properties, and a third one where the agent writes helper definitions, lemmas, and one proof per target.
The harness needed to be tough, because the agents tried to cheat. We saw three kinds in early runs, before the current checks were in place. An agent added ASSUME Useful == FALSE to the module and derived ZooKeeper's agreement theorem from it. An agent cited a helper lemma whose proof was PROOF OMITTED. An agent replaced /opt/tlapm/bin/tlapm with a shell script that printed "All 214 obligations proved" and exited 0.
Tilapia has three fences, one for each of those. The first is context integrity. The model and the target theorems sit in read-only modules, and SANY rejects any new ASSUME, AXIOM, CONSTANT, or VARIABLE in the agent's region. The agent can add definitions and lemmas, but it cannot change the context the target is proved in. The second is dependency tracking. SANY collects the lemma citations into a dependency graph, and a target counts only if its own proof checks and every lemma it cites, transitively, is proved too. The third is clean-room grading. The verdict comes from a fresh container with the original task files and unmodified tools, carrying over only the submitted module, so a patched tlapm or a helpful scratch wrapper never reaches the grader.
Proofmaxxing
So what happened when we ran this? We put four GPT models through Codex at max, high, and low reasoning effort, twelve configurations over the 70 targets. Every number is pass@3. Each target gets three independent runs, and it counts if any one of them proves it. Each run gets its own container, with an hour of TLAPS time per proof and a budget of two million output tokens per spec.
Max effort is where every model does its best. GPT-6.1 Sol proved 31 (44.3%). GPT-6 Astra proved 30 (42.9%), using about half Sol's tokens at three times the price. GPT-5.6 Terra proved 15 (21.4%) for and over 36 days of cumulative agent time. GPT-6 Luna proved 7 (10%). Sol and Astra both proved all 15 FLASH targets, eight of them liveness.
If you turn the effort down, things degrade quickly. Sol and Astra drop to 24 or 25 targets. Terra and Luna prove nothing at high or low effort. Below some reasoning threshold, you get no proof. Nobody proved the Wildfire refinement at any effort.
Lessons learned
Table 5 sorts every attempt that did not end in an accepted proof over all models, effort levels, and runs. The two big buckets are where the difficulty is: 1,455 incomplete proofs and 537 undecomposed proof attempts.
Incomplete proofs mean the invariant was never found. This is the biggest bucket. Either the agent could not find an inductive invariant strong enough for the target, or it proved a stack of helper lemmas and never connected them to the target. Here are two examples. On OpenAddressing's Consistent, Astra split the proof in two. The case with no hash collisions it proved with a dedicated invariant. The case with collisions and evictions it handed to a single SMT call citing three invariants it already had. Its own comment in the proof says that case needs a stronger invariant. So the accepted part of the proof only covers configurations where no collision ever happens. On Ivy TLB's NonStarvation, the agent proved the safety target with a 29-lemma inductive invariant, then tried to get liveness from that invariant plus the fairness assumptions. It skipped the progress lemmas that say the locks are eventually released and the loops terminate, and left a comment listing those missing steps. In both cases the agent knew what was missing, but could not produce it.
Undecomposed attempts mean the solver chokes. On Cahill SSI, Astra had a sound strategy, a ranking function, and it proved the supporting lemmas. Then it sent the entire inductive step to Z3 as a single obligation. Z3 said unknown, and the agent sent the same obligation again. Committing a transaction in that protocol can force other transactions to abort, while updating history, locks, and conflict flags. Each of those updates has to be shown to preserve the ranking argument. That is several pages of reasoning in one SMT query. The strategy was right, but it was not cut into pieces the solver could handle.
Abstraction wins. Cutting the obligation into pieces (decomposition) is not the only way to get the proof pass through the solver. Abstraction, in the modeling sense, asks what the property actually depends on and throws away everything orthogonal to it. Then the cases you would have argued one by one collapse into a single argument. Look at the two attempts at the ZooKeeper implementation. Terra reasoned directly over the implementation state, transaction origins and queued messages and synchronization state. It generated about 13,000 lines of intermediate proof, ran out of token budget, and proved neither leadership property. Astra first asked what leadership actually depends on, and found that a recorded vote and an eligible acknowledgment still in flight are the same thing: a claim of support for a leader. Once both are represented the same way, the synchronization and broadcast actions preserve the invariant for one common reason instead of a dozen separate ones, and both leadership properties follow. The level Astra chose to work at made the whole difference.
Bugs found
The specs in the benchmark are not guaranteed to be correct. They come from real systems, a few of them generated from source code, and most had been model checked a lot but never proved. Trying to prove them turned up 46 issues, 35 of which are now fixed. They came in three kinds.
The theorem was wrong. etcd Raft's LeaderCompletenessInv compared a leader's term against the term that created an entry, rather than the term that committed it. Raft allows an entry to be committed late, so the property as stated is false. The agent produced a 47-transition counterexample. A task can end this way, with a counterexample instead of a proof, as long as TLC or Apalache confirms the trace.
The model was wrong. SlateDB's WAL had a 58-step trace where garbage collection deletes a data entry, a delayed writer writes its fence into the vacated slot, and a writer replaying the log skips that fence and reaches READY without the deleted data. We reproduced the trace and reported it upstream. The fix validates the writer's epoch after replay, and on the revised model all four targets go through.
The configuration was hiding the problem. MongoDB's distributed transactions spec, one I wrote with Will Schultz, did not explicitly rule out a transaction starting at two routers with different read timestamps. The implementation rules this out, because a transaction stays pinned to the router that started it, and the spec took that as given instead of stating it. The model checking config used a single router, which supplied this assumption for free, so TLC was never in a position to notice, but the proof attempt called this assumption out explicitly.
Bounded model checking with a narrow config missed these. The proof attempt forced the question "why is this true in general?", and model checking with the right configuration produced the counterexample. Neither tool alone got there.
Proving gives you insight. A model checker can tell you when something breaks and hands you a trace. But a proof tells you why, and when the proof fails, it fails at a specific obligation, on a specific action, against a specific conjunct of the invariant. That points at the design assumption that is wrong, not just the symptom. Proofs are also incremental. TLAPS fingerprints the obligations it has already discharged, so after an edit only the affected steps need re-proving, and the ones that fail show which part of the argument the change broke. In contrast, a model checker reruns from scratch and hands you another trace.
Proofs people can follow
Another advantage of proof over model checking is that it leaves you with an inductive invariant, as a short statement of why the system works, and the lemmas get reused across targets and across revisions of the spec. This is awesome, but how readable are these? Sol's accepted max-effort proofs total over 15K lines. If agents produce proofs faster than engineers can follow them, the team incurs cognitive debt. You get a green checkmark backed by an argument nobody on the team can explain. So there is clear future work here: we need a user-friendly way to convey what a proof says. Surface the key invariants in plain language, tie each lemma to the design decision it relies on, and show which parts of the argument each action touches.






Comments