betaFeedback

WorksComputer Science

TLAPS-Bench: Formally Proving Correctness of Real-World System Specifications with TLA+ Proof System

Abstract

TLAPS-Bench is a benchmark and execution harness for constructing machine-checked proofs for real-world system specifications in TLA+ with agentic AI. Proving correctness of complex system specifications requires discovering inductive invariants, reasoning about intricate state transitions, and decomposing proofs into tractable obligations. TLAPS-Bench provides a proof harness that supports iterative proof development atop the TLA+ Proof System (TLAPS), where agents are equipped with proof tools and libraries, with safeguards against reward hacking. Using the harness, we have employed AI agents to prove desired properties for important system specifications that were not proved before, spanning cache coherence, Byzantine consensus, and write-ahead logs. TLAPS-Bench contains 265 proof targets (each encodes a property to prove) from 95 TLA+ specifications of real-world systems. We evaluated frontier AI agents, represented by Codex with GPT models, on a subset of 70 proof targets across 12 specifications. The highest-scoring model, GPT-6.1 Sol (max), proved 31 (44.3%) proof targets. The results show challenges and opportunities in end-to-end proof development.

Introduction

Formal proofs establish correctness properties of concurrent and distributed systems, such as cache coherence, consensus agreement, and transaction isolation, across all possible executions. Unlike other formal methods like model checking Clarke et al. [11], machine-checked proofs establish these properties deductively, providing correctness guarantees beyond finite exploration Cousineau et al. [12].

Traditionally, constructing formal proofs requires substantial expertise and effort. Developers must discover suitable inductive invariants Ma et al. (2019); ); Yao et al. [49], prove that they are preserved by every system transition, and decompose the reasoning into proof obligations that automated tools can discharge. For example, proving election safety in a consensus protocol Ongaro & Ousterhout [31] may require strengthening the target property with auxiliary invariants about majority support and vote uniqueness.

Recent advances in agentic AI show promise for automating proof construction. Several recent studies demonstrate that agents can construct nontrivial machine-checked proofs through iterative interactions with proof checkers Lucas et al. (2026); Yang et al. (2025a;b); Ye et al. (2026); Agarwal et al. (2026). These advances offer a path toward automating proof development for real-world concurrent and distributed systems beyond prototypes and research artifacts.

However, existing benchmarks do not sufficiently address end-to-end proof construction for real-world system specifications. First, many benchmarks provide agents with helper lemmas and intermediate invariants Yang et al. [48]; ); Xin et al. [45], or with predefined proof decomposition that specifies individual theorems and their dependencies Zhang et al. [53]; ); Lin et al. [24]. Such proof-completion style benchmarks predefine much of the proof structure, missing key challenges of discovering auxiliary invariants/lemmas, decomposing the target property into tractable proof obligations, and organizing them into a complete proof.

Second, few existing benchmarks target real-world system specifications. Many instead evaluate research artifacts developed specifically with formal verification in mind. For example, both VerusAGE Yang et al. [48] and Vero Ye et al. (2026a) include IronKV Hawblitzel et al. [16], rather than than widely deployed systems such as etcd and MongoDB. It is unclear whether agents can construct proofs for substantially richer behaviors of real-world systems.

Lastly, correctness properties of concurrent and distributed systems (e.g., liveness) go beyond functional correctness addressed by existing benchmarks like Vero Ye et al. (2026a).

Concurrent and distributed systems require extensive reasoning about system-wide properties that emerge from interactions among components over time, such as agreement, consistency, isolation, etc. These properties pose distinct proof challenges, because their correctness depends on the composition and interleaving of many state transitions.

We present TLAPS-Bench, a benchmark and execution harness for constructing machine-checked proofs of system and protocol specifications in TLA+^{+} (the de facto formal language for specifying concurrent and distributed systems; see § 2). We set two goals for TLAPS-Bench:

  • building a proof service to verify important real-world systems and protocols that desire correctness guarantees;

  • understanding the capabilities of frontier AI in constructing formal proofs of real-world systems, end to end.

Each task in TLAPS-Bench is a proof target (a property to be proved) desired for a real-world system/protocol, as shown in Figure 1; so, results are of practical value.

Overview of TLAPS-Bench

Figure 1. Overview of TLAPS-Bench. TLAPS-Bench provides AI agents with a TLA+^{+} specification (including models and target properties). TILAPIA (our TLA+^{+} proof harness) runs the agents, checks generated proofs with TLAPS, and records results.

TLAPS-Bench includes a proof harness for autonomous proof development, named TILAPIA (TLA+^{+} Proof Infrastructure for Agents). TILAPIA is built atop the TLA+^{+} Proof System or TLAPS ([12]), the native proof system for TLA+^{+}. It provides agents with tools including a semantic analyzer, model checkers, and common proof libraries. Agents can use these tools during proof development to explore system behaviors, refine proofs, and validate proof obligations. For example, agents constantly use model checkers to test invariants and obtain counterexamples that guide proof development. TILAPIA also enforces safeguards against reward hacking, ensuring that accepted proofs establish target properties under the original specifications.

We have used TILAPIA to construct machine-checked proofs for important properties for real-world system and protocol specifications which were not proved before.

TLAPS-Bench maintains a collection of 95 TLA+^{+} specifications and 265 proof targets drawn from real-world systems and protocols, spanning cache coherence, Byzantine fault tolerance, and write-ahead logs. The proof targets cover safety, liveness, and refinement properties. We are continuously adding new proof tasks and retiring tasks that were proved and can no longer challenge AI frontier.

We evaluate frontier AI agents, represented by Codex with GPT models, on 70 proof targets across 12 real-world system specifications. The highest-scoring model, GPT-6.1 Sol at max effort, successfully proves 31 (44.3%) targets, demonstrating strong capability while leaving substantial room for improvement. Our analysis reveals that success depends not only on finding valid proof arguments. For example, case studies show that the choice and decomposition of invariants substantially affect proof obligations, whereas naïve calling of automated backends is ineffective.

In summary, we make the following main contributions:

  • TILAPIA, an effective TLA+^{+} proof harness for agentic TLA+^{+} proof development, which offers a TLA+^{+} proof service for real-world system specifications;

  • TLAPS-Bench, a rich benchmark suite for end-to-end proof development based on real-world system specifications, which poses significant challenges to frontier AI;

  • An analysis of frontier AI’s ability of developing formal proofs for real-world system/protocol specifications.

  • TLAPS-Bench and TILAPIA are publicly available at github.com/specula-org/TLAPS-Bench.

Background

TLAPS-Bench focuses on formally proving the correctness of TLA+^{+} specifications ([21]). TLA+^{+} is the de facto specification language for verifying concurrent and distributed systems. It is widely adopted across industry ([43]) to specify and verify cloud infrastructure ([30, 17]), replication protocols ([32]), databases like Azure Cosmos DB and MongoDB ([15, 36]), OS kernel code ([41]), and hardware cache coherence ([2]).

A TLA+^{+} specification comprises a system model and correctness properties. The model defines a state machine. through a set of state variables, an initial predicate that defines their initial values, and a next-state relation written as a collection of actions, each describing one atomic update to the variables. Correctness requirements are expressed as temporal properties, including safety (nothing bad ever happens) and liveness (something good eventually happens). TLA+^{+} is built upon the Temporal Logic of Actions (TLA) [20], which extends linear temporal logic [35] to express models and temporal properties in a single logic. A target theorem asserts that every behavior allowed by the model satisfies a given property.

TLA+^{+} specifications can be validated through explicit-state model checking with TLC (Yu et al., 1999) and symbolic model checking with Apalache [18], or verified via deductive verification with the TLA+^{+} Proof System (TLAPS) [12]. Model checking can expose counterexamples through finite-state or bounded exploration, but it guarantees are limited to the configured bounds. Deductive verification can establish a target theorem beyond those bounds by checking a proof.

In TLAPS-Bench, agents construct complete TLA+^{+} proofs of these theorems. TLAPS checks these proofs by generating proof obligations for their steps and dispatching them to specialized backends, including SMT solvers such as Z3 [13], Isabelle/TLA+^{+} [33], and LS4 [39]. Agents may use TLC and Apalache to test candidate invariants and obtain counterexamples that guide proof development, but a target is accepted only when TLAPS verifies the proof.

Figure Figure 2 illustrates the input and output of an etcd Raft task in TLAPS-Bench. The input on the left consists of a system model and a target property, while the output on the right is an accepted agent-generated TLAPS proof. Init defines the initial states, in which every server is a follower in term zero and has received no votes. Timeout initiates a new election by transitioning a server to the candidate state, advancing its term, and resetting its votes; BecomeLeader transitions a candidate with a quorum of votes to the leader state. Next combines these with the remaining actions, and Spec defines the allowed system behaviors. The target LeaderUniqueness states that two leaders in the same term must be the same server, and the theorem Spec => []LeaderUniqueness asserts that this property always holds (the temporal operator [] denotes “always”).

Figure 2. A simplified example of a proof task in TLAPS-Bench based on etcd Raft, with the TLA+^{+} model and the target property (LeaderUniqueness) as input (left) and an accepted agent-generated TLAPS proof (right).

The output on the right proves the target property through a stronger inductive invariant. This invariant, ARInv, captures voting facts needed by the proof but not stated in LeaderUniqueness: every leader has votes from a quorum, and each voter supports at most one candidate in a term. ARInitial and ARStep establish that ARInv holds initially and is preserved by every action. Using these lemmas, ARAlways proves Spec => []ARInv. To derive the target, ARUniqueLeader applies quorum intersection: two leaders in the same term must share a voter, whose vote uniqueness implies that they are the same server. Together, these results establish Spec => []LeaderUniqueness.

While TLA+\mathrm{TLA}^{+} and TLAPS are built natively around TLA, state-machine and temporal reasoning can also be realized in other proof systems. Lean (de Moura & Ullrich, [14]) targets general theorem proving and supports state-machine verification with Veil (Pırlea et al., [34]), while Verus (Lattuada et al., [23]) targets Rust verification and encodes temporal reasoning through libraries ([40, 5]). TLAPS-Bench focuses on TLA+\mathrm{TLA}^{+}, but the techniques can be extended to other proof systems.

TILAPIA: TLA+ Proof Harness

We develop TILAPIA: a TLA+\mathrm{TLA}^{+} proof harness, to support AI agents for autonomous development of TLA+\mathrm{TLA}^{+} proofs. TILAPIA provides agents with the flexibility to develop proof strategies, invoke verification tools, and build on partial progress, while preventing reward hacking and ensuring that accepted proofs establish the original targets.

Using TILAPIA, we have instructed AI agents to construct machine-checked proofs for TLA+\mathrm{TLA}^{+} specifications of important systems and protocols. Table 1 gives a few examples where we proved the target properties for the TLA+\mathrm{TLA}^{+} specifications, including both classic protocol and real-world system specifications (some of them had proofs in other forms). For example, Bosco (Song & Renesse, [37]), an asynchronous Byzantine consensus protocol, only has pen-and-paper proofs; we generated TLA+ proofs for its five properties. We also proved all the properties of several WAL (Write Ahead Log) protocols of databases; these protocols were specified in TLA+\mathrm{TLA}^{+} and heavily model checked, but were not formally proved to be correct.

SpecificationLOCTargetsPrior Proof
German protocol4027Isabelle
Bosco Byzantine consensus1405Pen-and-paper
Sailfish BFT consensus2003Rocq
OSWALD WAL2603None
SlateDB WAL5644None
Walgit WAL5587None
TLC DiskStateQueue1,5671None
Disruptor MPMC2152None
Disruptor SPMC1872None
BufferedRandomAccessFile33414None

Table 1. Examples of TLA+\mathrm{TLA}^{+} specifications we proved using TILAPIA. Some of them were proved in other forms.

TILAPIA organizes each proof target as a task and groups tasks of the same specification in one proof file, allowing their proofs to share auxiliary invariants and lemmas. For proof integrity (see § 3.2), the TLA+\mathrm{TLA}^{+} model and the target properties are placed in separate read-only files. Within the proof file, target theorem statements are fixed, while agents can define auxiliary invariants and lemmas in a shared editable region and construct a proof for each target. This layout preserves the original proof goals while allowing agents to flexibly choose their own proof strategies.

TILAPIA uses Docker containers to isolate workspaces of different agents. File-system isolation mounts the original task files read-only and each run starts a fresh agent session without conversations or memories from other runs; network isolation only allows connections to LLM API endpoints and agent built-in web search tools are disabled.

Tools for Agents

TILAPIA provides a local environment for agents to construct proofs of target properties in a TLA+\mathrm{TLA}^{+} specification. It supports coding agents such as Codex, Claude Code, Copilot, and Cursor, and integrates pinned versions of SANY for semantic analysis, TLAPS for proof checking, and TLC and Apalache for model checking. TILAPIA provides agents with the TLAPS library (Chaudhuri et al., [7]) and CommunityModules (Kuppe et al., [19]) which include theorems and proofs for commonly used TLA+\mathrm{TLA}^{+} operators, such as set and sequence operations.

Model checkers. TILAPIA provides model checkers, including TLC (Yu et al., 1999) and Apalache (Konnov et al., [18]), to help agents test conjectures during proof development. TLC explores reachable states of a finite model, while Apalache uses SMT solving for bounded exploration and inductiveness checking. Both can quickly falsify incorrect conjectures by producing counterexamples. An agent can use them to test whether a proposed invariant holds and use a counterexample to identify conditions needed to refine it, as illustrated in Figure 3. Model checking thus provides rapid feedback for proof development, while the final proof is established by TLAPS.

Figure 3. An example of an AI agent attempting to prove that no two nodes access a shared resource simultaneously, where access requires holding a token. The agent uses TLC counterexamples to refine an auxiliary invariant that supports the target proof.

Guidance. TILAPIA provides two agent skills to guide the use of proof libraries and model checkers. The first explains how to apply instantiated library theorems, e.g., by establishing the premises required to use them. The second explains how to configure invariant checks, e.g., by using the proposed invariant as the initial predicate when checking its preservation. Both address common usage errors that agents encounter without explicit guidance.

Proof checker. Agents can invoke the same TLAPS proof checker used for final evaluation, with identical acceptance criteria and per-verification time limits. The checker provides two modes: (1) a fast pass runs SANY for immediate syntax and semantic feedback, while (2) a full pass applies the proof-integrity checks of § 3.2 and then verifies each target together with its dependencies. For each target, the checker reports whether its proof succeeded, failed, or exceeded the time limit. This feedback helps agents identify unresolved proof obligations, repair failed proofs, and decide where to focus subsequent proof development.

Proof Integrity

TILAPIA accepts a proof for a target property if all three of the following conditions hold:

  • Context integrity. The proof must establish the target property under the original specification and assumptions. For example, in Figure 4(a), an agent adds ASSUME Useful == FALSE, making ZooKeeper’s agreement theorem trivially provable. TILAPIA therefore makes the specification and target theorems read-only and restricts edits to designated regions of the task file. Within these regions, SANY’s semantic analysis is used to permit only definitions, named lemmas, and imports from pinned proof libraries, while rejecting new assumptions, axioms, constants, and variables. In summary, agents can introduce auxiliary invariants and lemmas without changing the logical context in which the target must be proved.

  • Dependency tracking. Every lemma on which a target depends must itself be proved. Figure 4(b) shows a direct violation: the proof of ZooKeeper’s leadership property cites NextInv, but the proof of NextInv is omitted. More subtly, because targets are verified separately for evaluation (§ 5.1), a target may pass even when the proof of a helper lemma it cites fails. Without tracking such dependencies, an agent could therefore establish a target by relying on an unproved or unprovable lemma. TILAPIA uses SANY to extract lemma references and constructs a dependency graph over targets and helper lemmas. A target is accepted only if its own proof succeeds and every lemma on which it transitively depends is also proved.

  • Clean-room grading. The final result must be independent of any agent-modifiable tools or execution environment. In Figure 4(c), an agent replaces tlapm with

Three cheating attempts observed in real agent runs

Figure 4. Three cheating attempts observed in real agent runs that can appear successful without TILAPIA.

a script that simply reports success, causing the local checker to return PASS without verifying the proof. To prevent such manipulation, TILAPIA grades each submission in a fresh container with the original task files and unmodified verification tools, carrying over only the submitted task module. Agents may create wrapper modules, configuration files, and scripts during proof development, but these artifacts are excluded from the grading environment and therefore cannot affect the final result.

Execution Control

TILAPIA enforces fixed verification time limits and CPU quotas to ensure consistent execution conditions across runs. It tracks resource usage including execution time, token usage, model cost, and tool calls, enabling evaluation of both proof success and computational cost.

To support long-running experiments, TILAPIA can pause and resume agent runs interrupted by external failures, such as provider quota limits or API outages. Resumed runs retain completed verification results and caches, avoiding redundant computation while preserving the agent’s progress.

TLAPS-Bench

The proof tasks from TLAPS-Bench come from TLA+^{+} specifications of real-world systems and protocols. TLAPS-Bench currently includes 95 specifications with 265 proof targets, covering cache coherence, distributed consensus, atomic broadcast, transaction isolation, and concurrent data structures. In the spirit of measuring the frontier (and saving token cost), we maintain an active set of challenging proof tasks and retire tasks that are too easy for AI agents. Our current active set has 12 specifications with 70 targets and we will use this set in our evaluation. The information of the other tasks can be found in Appendix § 9.

Task Definition

In TLAPS-Bench, a task is to prove a target property of a given TLA+^{+} specification. Targets include safety, liveness, and refinement properties. A safety property rules out undesirable behaviors—any violation can be witnessed by a finite execution prefix, such as two processes simultaneously accessing a shared resource without protection. A liveness property requires progress over an execution, such as every pending request eventually completing; unlike safety, its violation cannot be established from any finite prefix because the required event may still occur later. A refinement property relates two specifications, requiring every behavior of a concrete model, under a refinement mapping, to satisfy an abstract specification. For example, Wildfire’s refinement target requires its request and response histories to satisfy the Alpha memory model ([22]).

A specification consists of a formal TLA+^{+} model, which defines state variables and actions, and the targets as TLA+^{+} theorems, stating what properties the model should satisfy. Figure 2 shows one task from etcd Raft: the formal model defines state variables and election actions, while the target LeaderUniqueness states that two leaders in the same term must be the same server.

Note that the TLA+^{+} specifications are not guaranteed to be correct. As they are collected from real-world systems/protocols (some were generated by tools ([9]) that infer TLA+^{+} specifications from source code), many of them were not formally proved though most of them have been heavily model checked. It is possible that specifications are incorrect—either the system designs are flawed or the specification was not written correctly. In either case, the results of TLAPS-Bench help improve real-world system specifications and/or their designs/implementations.

During task construction, we found 46 specification issues, of which 35 have been fixed. For example, an agent found a snapshot isolation violation in MongoDB’s TLA+^{+} specification which incorrectly allowed one transaction to use two routers with different read timestamps; the model checking uses a single-router configuration and thus misses it.

For the target property of a given task, the AI agent either proves it to be correct by providing a proof that can pass TLAPIA’s (§ 3) proof checks, or disproves it by providing a counterexample that shows an execution that violates the target property. The counterexample can be generated using model checkers like TLC or Apalache. TLAPS-Bench poses few restrictions on the proof strategies: agents can pick their own auxiliary invariants and use the tools, libraries, and guidance provided by TLAPIA.

Task Construction

Some specifications list explicit correctness properties. In this case, each property PP of a specification Spec\mathit{Spec} is formulated as a top-level theorem in the form of Spec⇒P\mathit{Spec} \Rightarrow P. For example, the German protocol’s theorem Spec⇒[]Coherence\mathit{Spec} \Rightarrow[]\text{Coherence} states that exclusive access to a cache line cannot coexist with access by another cache. AI agents are asked to prove the theorem end-to-end. If the specification contains proofs of the target theorem, we carefully remove all related auxiliary lemmas and proofs.

For specifications that do not have explicit properties, we identify target properties from different sources. If a model checking configuration lists a property as an invariant, such as OpenAddressing’s Sorted invariant described in its .cfg file, we formulate the target Spec => []Sorted. If correctness requirements are stated in other files, such as comments and documents, as in the Cahill SSI specification whose comments say that serializability must hold, we formulate targets from those requirements as Spec => []CahillSerializable(history).

Rewriting specifications. Certain revisions of the specification may be needed, including rewriting constructs for tool issues, and adding explicit assumptions specified in other sources. We also translate specifications written in other specification languages into TLA⁺.

Figure 5 shows three examples. 5(a) shows MongoDB’s snapshot isolation specification whose model-checking configuration encodes assumptions as constant assignments. We make these assumptions explicit in the proof task. 5(b) shows our translation of a TLB specification from Ivy to TLA⁺. We map Ivy state and transitions to TLA⁺ variables and actions, and use TLC to check the translated specification on a finite instance. 5(c) shows an incorrect TLAPS expansion of a nested LET inside a definition of a recursive function. We work around this issue by inlining the binding without changing the recursive function or its domain.

Figure 5. Three examples of rewriting specifications into TLAPS-Bench tasks.

Task organization. As a final step, we transform each specification into the task format expected by Tilapia (§ 3). We use SANY, the TLA⁺ syntactic analyzer, to resolve references and compute the transitive dependencies of each target theorem. Figure 6 illustrates this process for the Sorted theorem in OpenAddressing. The statement Spec => []Sorted depends on Spec, Sorted, and, transitively, isSorted; we retain the union of such dependencies across all selected targets. We remove definitions outside this dependency closure, together with existing proofs, auxiliary lemmas, unselected theorems, and comments.

Figure 6. An example of task organization of the OpenAddressing specification.

The retained content is then organized into three modules. OpenAddressingModel.tla contains the specification and assumptions, while OpenAddressingDefs.tla contains the target properties and their definitions, e.g., Sorted and isSorted; both modules are read-only. The editable task module, OpenAddressing.tla, contains the target theorem statements and regions for agents to introduce helper definitions, lemmas, and proofs. Targets from the same module share a task file and helper region, allowing agents to develop and reuse common lemmas.

Task Validation

Unlike agentic coding benchmarks that validate generated programs by running test cases, the validation of agent results in TLAPS-Bench is complete with no ambiguity. For each task, an agent succeeds by proving the target to be either correct (with a formal proof) or wrong (with a counterexample). An agent fails if it can neither prove the target nor provide a counterexample. The validation does not depend on test coverage, hidden test cases, or an approximate correctness oracle. As with other formal techniques, the guarantee is relative to the trusted computing base, including TLAPS and its backends (e.g., Z3, Isabelle, and LS4).

Developing and evaluating TLAPS-Bench has also led to improvements to TLAPS itself, including bug fixes and support for autonomous proof development. For example, we introduced a strict mode that treats missing or omitted proof steps as errors, allowing TILAPIA to ensure that submitted proofs are complete rather than relying on unproved steps.

Evaluation

Experimental Setup

We evaluate the latest available GPT models: GPT-6 Astra, GPT-6.1 Sol, GPT-6 Luna, and GPT-5.6 Terra. We use Codex across the models with max, high, and low reasoning effort (12 configurations in total).

The evaluation ran on an Ubuntu 24.04.3 virtual machine with 96 vCPUs, backed by an AMD EPYC 9V74 processor and 378 GiB of DRAM. Each run executed in a separate Docker container with 8 vCPUs. We set a time limit of 60 minutes for the TLAPS backend to process a proof, which is empirically sufficient for properly decomposed proofs to be verified. We also set a cumulative limit of two million output tokens (including reasoning tokens) for each specification. Only Terra and Luna at max effort reach this limit (they could not finish the proof but did not give up).

Metrics. We report pass@3, the fraction of tasks that pass in at least one of three independent runs, to accommodate nondeterminism. We report input/output token usage, model cost, and agent execution time (including model prompting and tool calling), summed across all tasks and all three runs.

Proof Capability

Table 3 shows significant differences in proof capability across evaluated models. GPT-6.1 Sol achieves the highest success rate at max effort, proving 31 of 70 targets (44.3%), followed closely by GPT-6 Astra with 42.9%. GPT-5.6 Terra and GPT-6 Luna prove far fewer targets at max effort and none at high or low effort.

Model (Agent)EffortSuccess Rate (pass@3)Correct Proof LOC TotalCorrect Proof LOC Per TargetTotal Tokens (M) InputTotal Tokens (M) OutputTotal Cost (USD)Total Agent Time (min)
GPT-6.1 Sol (Codex)max44.3%15,619503.81456.147.730$328.86 | 5917.4
GPT-6.1 Sol (Codex)high34.3%5,967248.6635.573.312$134.75 | 2725.0
GPT-6.1 Sol (Codex)low35.7%8,834353.4549.232.238$97.75 | 1795.6
GPT-6 Astra (Codex)max42.9%13,725457.5770.224.270$1086.44 | 3992.5
GPT-6 Astra (Codex)high34.3%5,503229.3353.111.663$486.57 | 1575.7
GPT-6 Astra (Codex)low34.3%7,175299.0272.831.162$373.41 | 1262.5
GPT-5.6 Terra (Codex)max21.4%15,4481,029.921475.8756.232$5602.15 | 52481
GPT-5.6 Terra (Codex)high0.0%--126.850.635$42.00 | 528.6
GPT-5.6 Terra (Codex)low0.0%--35.450.243$14.78 | 215.2
GPT-6 Luna (Codex)max10.0%11,4971,642.42338.159.586$31.11 | 5285.4
GPT-6 Luna (Codex)high0.0%--33.980.284$0.69 | 200.3
GPT-6 Luna (Codex)low0.0%--13.810.070$0.30 | 45.6

Table 3. Overall benchmark results on the problem set described in Table 2.

The successful proofs show that frontier AI agents can establish correctness properties of real-world specifications. Astra and Sol proved all 15 targets of the FLASH cache coherence protocol, spanning both safety and liveness properties. Sol proved all target properties of OpenAddressing.

On the other hand, complex tasks are still challenging for frontier AI agents to prove end to end. For example, Sol at max effort proved leader uniqueness and log matching for the etcd Raft system specification, but failed to prove consistency between committed logs and durability of committed entries. For both ZooKeeper protocol and system specifications, Sol proves none of the target properties.

System specifications introduce additional proof challenges by exposing implementation mechanisms and optimizations abstracted away by protocol specifications. For example, the ZooKeeper protocol specification synchronizes a replica by copying the leader’s entire log, whereas the system specification can send missing log entries, truncate divergent entries, or transfer snapshots. These mechanisms introduce additional states and transitions over which invariants must be preserved, increasing the complexity of the proof.

Sol and Astra achieve similar pass@3 scores but exhibit distinct proof-development patterns. On OpenAddressing, Sol persistently strengthens invariants and repairs failed proof obligations until all target properties are proved. In contrast, Astra proves the completion and sortedness properties but terminates with several induction steps unresolved in all three runs, despite remaining token budget. On ZooKeeper, however, Astra constructs a compact invariant abstraction that avoids extensive reasoning about transaction histories and proves leadership properties that Sol leaves unresolved

(§5.5). These results suggest that Sol is more persistent in iterative proof development, whereas Astra can reduce proof complexity by discovering effective invariant abstractions. This ability to construct simpler proofs, together with earlier termination when proof attempts stall, helps explain why Astra achieves nearly the same overall score while using roughly half as many input and output tokens as Sol.

Reasoning Effort and Cost

As shown in Table 3, all models achieve their highest success rates at max effort, while low and high effort can perform similarly. Sol performs slightly better at low than high due to one PirateShip target, while Astra achieves identical success rates at low and high effort.

The cost often depends on whether or not proof succeeds, as shown in Table 4. On Cahill SSI (unproved), Sol uses both more reasoning tokens per request and more model requests as effort increases. In contrast, on FLASH (solved at every effort), high and max effort require roughly half as many requests as low effort while achieving the same pass@3. Despite using more reasoning tokens per request, high effort has the lowest total cost.

SpecSucc. Rate (pass@3)EffortModel RequestsReasoning TokensCost (USD)
Cahill SSI0/1low722070.81
0/1high1964424.32
0/1max2777278.01
FLASH15/15low1,40038936.96
15/15high69149924.92
15/15max78863037.27

Table 4. GPT-6.1 Sol by reasoning effort: total requests and cost over three runs, and mean reasoning tokens per request.

Model pricing makes cost distinct from resource usage. Astra (high) uses fewer input and output tokens and produces shorter proofs than Sol (high), yet costs approximately 3.6 times as much. Across all three effort levels, Sol matches or exceeds Astra’s proof success at lower model cost.

Failure Analysis

Table 5 categorizes failures across three runs. Errors exposed directly by tool feedback, such as invalid counterexamples, syntax or semantic errors, task-preservation violations, and verification timeouts, are relatively rare in final submissions. Stronger models such as Astra and Sol rarely have basic syntax and task-preservation errors.

CategoryAttempts
Incorrect counterexample claims9
Syntax or semantic errors detected by SANY31
Task preservation violations15
Verification timeout21
Undecomposed proof attempts537
Incomplete proofs1,455

Table 5. Failure categories across failed proof tasks (pass@3).

More substantive failures arise from proof construction. In 537 attempts, agents delegate entire target proofs to automated backends without decomposing them into tractable obligations, often after their own proof attempts stall. Most

failures, however, are incomplete proofs: agents fail to discover inductive invariants strong enough to establish the target, or prove helper lemmas without completing the argument connecting them to the target property.

Case Studies

TLAPS-Bench enables the understanding of effective proof development practices and recurring limitations of existing agents, providing insights for designing more capable proof agents. We present three case studies.

ZooKeeper system specification (Astra: ✓; Terra: ✗). The specification has two leadership properties: each epoch has at most one active leader, and leaders recorded at different times within the same epoch must be the same server. Proving these properties is complicated by system state for log synchronization, message queues, and snapshot handling, whose updates span many different actions.

GPT-5.6 Terra (max) attempted both properties by developing a large set of invariants over transaction origins, queued messages, and synchronization state. It exhausted the output-token budget and failed to prove either target, despite generating roughly 13,000 lines of intermediate proofs.

GPT-6 Astra successfully proved both properties. Astra abstracts the state relevant to leadership. Its key invariant treats recorded votes and eligible acknowledgments in transit uniformly as claims of support for a leader. Astra then shows how each protocol action preserves these claims, allowing synchronization and broadcast actions to share a common proof argument. This abstraction proves both leadership properties. The case shows how abstractions can substantially reduce proof complexity.

Cahill’s serializable snapshot isolation (Astra: ✗). Astra fails to prove serializability for Cahill SSI despite developing a promising proof strategy. It reduces serializability to a ranking argument: under conditions on transaction order and conflict flags, a ranking function increases along every dependency edge, ruling out cycles. It successfully proves the supporting lemmas but delegates the entire invariant-preservation argument to a single SMT call (Figure 7).

Figure 7. GPT-6 Astra failed to prove Cahill serializable snapshot isolation due to stalls on undecomposed SMT obligations.

This remaining obligation requires substantial protocol reasoning. Committing a transaction, for example, can force other transactions to abort while updating history, locks, and conflict flags. The proof must show that these updates preserve the conditions required by the ranking argument. Rather than decomposing this reasoning into smaller obligations, Astra repeatedly submits the same unresolved obligation to the backend. The supporting lemmas therefore pass verification, but the target theorem remains unproved. Finding a proof strategy is insufficient without decomposing it into obligations that automated backends can discharge.

Wildfire challenge (all models: ✗). Wildfire is a cache-coherence protocol whose specification must refine the Alpha memory model. The proof must relate each read to its source write or initial memory and establish an ordering of concurrent operations permitted by the memory model, while preserving these relationships across protocol actions.

No evaluated model completed the refinement proof at any effort level. Astra and Sol established basic invariants over request and response records and recognized the need for histories and ordering relations, but failed to construct the invariants connecting protocol executions to the memory model. Luna and Terra made less progress, establishing only basic facts about types and initial states.

In its strongest attempt, Sol proved that protocol actions preserve the structure of request and response records and split the refinement proof into executions with and without requests. The no-request case passed verification, but the general case still required history and ordering invariants connecting returned values and concurrent operations to the Alpha memory model. Thus, the decomposition discharged a special case without simplifying the refinement argument.

Related Work

TLAPS-Bench evaluates AI agents on developing TLA+^{+} proofs for real-world system specifications, end-to-end. We discuss two related lines of work: (1) software verification benchmarks and (2) TLA+^{+} related benchmarks.

Software verification benchmarks. Existing benchmarks often evaluate proof completion tasks, which give parts of the proof structure. NTP4VC (Xu et al., 2026) supplies verification conditions, while DafnyBench (Loughridge et al., [25]) and AutoVerus (Yang et al., [47]) evaluate proving functions. Several benchmarks build on larger verified systems: Selene (Zhang et al., [53]) and FVELer (Lin et al., [24]) extract Isabelle lemmas from seL4, CoqStoq (Thompson et al., [42]) and VeriSoftBench (Xin et al., [45]) extract theorems from verified Rocq and Lean projects, and Laurel (Mugnier et al., [29]), RVBench (Zhong & Si, [54]), and VeruSAGE-Bench’s main setting (Yang et al., [48]) extract functions and lemmas from verified systems.

Differently, TLAPS-Bench evaluates end-to-end proof construction for TLA+^{+} system specifications. Several other benchmarks also require agents to prove from scratch, including Vero proof-only mode (Ye et al., 2026a), VE-RINA (Ye et al., 2026b), and VeruSAGE-Bench (Yang et al., [48]) no-lemma mode. These benchmarks primarily focus on functional properties of individual functions, APIs, or modules. TLAPS-Bench instead targets system-wide properties of concurrent and distributed systems that emerge from interactions among components over time.

TLA+^{+} benchmarks. Most benchmarks evaluate AI agents on generating TLA+^{+} specifications from code (Chen et al., [8]; Cheng et al., [10]) or from natural language descriptions (TLA+Bench, 2026; Bisharat et al., [4]; Cao et al., [6]). For TLA+^{+} proofs, LMGPA (Zhou & Tripakis, [55]) includes a benchmark for proof decomposition; the focus is to evaluate LLMs on discovering subclaims recursively. However, the LMGPA benchmark does not evaluate TLA+^{+} proofs end-to-end, e.g., AI agents are supplied with inductive invariants in LMGPA. TLA-Verus (Strelbytska et al., [38]) also includes a related benchmark. The benchmark is on Verus, where specifications were translated from TLA+^{+}. TLA-Verus had an incorrect understanding of TLAPS, saying TLAPS cannot prove arbitrary temporal logic properties. TLAPS decomposes proofs and dispatches obligations to different backends, including LS4 for propositional temporal reasoning. TLAPS-Bench focuses on TLA+^{+} specifications, instead of translated representations.

Conclusion and Discussion

TLAPS-Bench and TLAPIA provide infrastructure for AI agents to construct formal proofs of TLA+^{+} system specifications. Proof construction discovers inductive invariants and lemmas that explain why systems are correct and can expose unexpected behaviors or weaknesses in the stated properties. Looking forward, we believe abstraction will be key to scaling proofs: rather than reasoning directly over detailed system models, agents can recover high-level designs and establish refinement across successive abstraction layers. With AI greatly lowering the cost of formal proofs, specifications and proofs could become not only verification artifacts, but also durable representations of system design.

AI Usage Disclosure

We used OpenAI Codex with GPT-6 Astra and GPT-6.1 Sol to assist with software development for TLAPS-Bench and its evaluation, as well as paper writing. For software development, we used Codex as the coding agent to help implement TLAPS-Bench and TILAPIA; we also used Codex to write evaluation scripts. For paper writing, we used Codex to polish the text, including grammar, phrasing, and clarity. All AI-assisted code and text were reviewed by the authors before use. We take full responsibility for the correctness, originality, and integrity of the work.

Other TLAPS-Bench Problems

In this paper, our evaluation focused on 12 specifications with 70 proof targets shown in Table 2. In total, TLAPS-Bench includes 95 TLA+^{+} specifications and 265 proof targets.

SpecificationTypeModel SourceSpec LOCTargets
FLASH Cache coherenceProtocolTLA+^{+} Specification Repository62315 (Safety + Liveness)
ZooKeeper protocolProtocolRemix ([32])9949 (Safety)
Cahill’s serializable snapshot isolationProtocolAmazon Snapshot Spec4071 (Safety)
Ivy TLBSystemIvy examples3612 (Safety + Liveness)
OpenAddressingSystemTLA+^{+} Specification Repository3565 (Safety)
etcd RaftSystemSpecula ([9])6018 (Safety)
HashiCorp RaftSystemSpecula ([9])6566 (Safety)
ZooKeeper implementationSystemRemix ([32])1,8409 (Safety)
MongoDB distributed transactionsSystemMongoDB Research7241 (Safety)
CCF RaftSystemMicrosoft CCF ([17])1,1442 (Safety)
PirateShip consensusProtocolPirateShip ([28])58611 (Safety)
Wildfire cache coherence∗^{*}ProtocolWildfire Challenge ([22])1,2511 (Refinement)

Table 2. The problem set of TLAPS-Bench used in the evaluation. ∗^{*}: The original Wildfire Challenge Problem injected a bug in the Wildfire TLA+^{+} specification; the challenge problem is to find the bug. We found the bug using model checking and repaired the specification. In TLAPS-Bench, the task is to prove (or disprove) the repaired specification.

Table A1 shows the remaining problems. Most of the problems in Table A1 are retired after the frontier proved them—they can be used for evaluation, but can no longer challenge frontier models. On the other hand, the proofs of these specifications generated by AI agents are valuable and are shared as public knowledge in our project repository.

SpecificationTypeModel SourceSpec LOCTargets
Atomic BakeryProtocolTLAPS Specification Repository1061 (Safety)
Atomic Bakery (without SMT)ProtocolTLAPS Specification Repository1011 (Safety)
BakeryProtocolTLAPS Specification Repository1231 (Safety)
PetersonProtocolTLAPS Specification Repository762 (Safety + Liveness)
Simple mutexProtocolTLAPS Specification Repository502 (Safety)
BakeryProtocolTLA+^{+} Specification Repository1272 (Safety)
BoulangerieProtocolTLA+^{+} Specification Repository1412 (Safety)
Lamport mutexProtocolTLA+^{+} Specification Repository1062 (Safety)
LockProtocolTLA+^{+} Specification Repository521 (Safety)
LockHSProtocolTLA+^{+} Specification Repository1902 (Safety + Refinement)
Peterson (auxiliary variables)ProtocolTLA+^{+} Specification Repository1222 (Safety + Refinement)
Two-thread mutexSystemAnvil481 (Liveness)
Ticket lockSystemIvy examples702 (Safety + Liveness)
Nested ticket lockSystemIvy examples812 (Safety + Liveness)
AllocatorProtocolTLAPS Specification Repository444 (Safety)
Allocator implementationProtocolTLA+^{+} Specification Repository1861 (Safety)
Scheduling allocatorProtocolTLA+^{+} Specification Repository982 (Safety)
Simple allocatorProtocolTLA+^{+} Specification Repository722 (Safety)
BarriersProtocolTLA+^{+} Specification Repository2155 (Safety + Refinement)
Readers–writersProtocolTLA+^{+} Specification Repository1042 (Safety)
Cigarette smokersProtocolTLA+^{+} Specification Repository452 (Safety)
LLVM libompSystemSpecula5964 (Safety)
Blocking queue (fair)SystemTLA+^{+} Specification Repository1671 (Refinement)
Blocking queue (split)SystemTLA+^{+} Specification Repository1523 (Safety + Refinement)
Blocking queueSystemTLA+^{+} Specification Repository671 (Safety)
Disruptor (MPMC)SystemTLA+^{+} Specification Repository2152 (Safety)
Disruptor (SPMC)SystemTLA+^{+} Specification Repository1872 (Safety)
Split queueSystemIvy examples741 (Liveness)
TLC DiskStateQueueSystemTLA+^{+} tools1,5671 (Safety)
B-treeSystemTLA+^{+} Specification Repository3135 (Safety)
Key-value storeSystemTLA+^{+} Specification Repository1061 (Safety)
German controlProtocolTLA+^{+} Specification Repository1191 (Safety)
German dataProtocolTLA+^{+} Specification Repository2836 (Safety + Refinement)
Paxos: ConsensusProtocolTLAPS Specification Repository241 (Safety)
PaxosProtocolTLAPS Specification Repository1593 (Safety + Refinement)
Paxos (history variable)ProtocolTLAPS Specification Repository1052 (Safety)
Consensus: ConsensusProtocolTLAPS Specification Repository511 (Safety)
Consensus: PaxosProofProtocolTLAPS Specification Repository2083 (Safety + Refinement)
Consensus: VotingProtocolTLAPS Specification Repository1286 (Safety + Refinement)
RecordProtocolTLAPS Specification Repository491 (Refinement)
Paxos: ConsensusProtocolTLA+^{+} Specification Repository302 (Safety + Liveness)
Paxos: VotingProtocolTLA+^{+} Specification Repository832 (Safety + Refinement)
Paxos lecture: ConsensusProtocolTLA+^{+} Specification Repository271 (Safety)
Paxos lecture: VotingProtocolTLA+^{+} Specification Repository1012 (Safety + Refinement)
Paxos lecture: Voting proofProtocolTLA+^{+} Specification Repository783 (Safety)
Tencent PaxosSystemTLA+^{+} Specification Repository1892 (Safety)
Byzantine Paxos: BPConProofProtocolTLA+^{+} Specification Repository4003 (Safety + Refinement)
Byzantine Paxos: ConsensusProtocolTLA+^{+} Specification Repository363 (Safety + Liveness)
Byzantine Paxos: PConProofProtocolTLA+^{+} Specification Repository941 (Safety)
Byzantine Paxos: VoteProofProtocolTLA+^{+} Specification Repository1474 (Safety + Liveness + Refinement)

Table A1. The retired problem set of TLAPS-Bench.

SpecificationTypeModel SourceSpec LOCTargets
Byzantine reliable broadcastProtocolTLA+^{+} Specification Repository1305 (Safety)
Bosco Byzantine consensusProtocolTLA+^{+} Specification Repository1405 (Safety)
Sailfish BFT consensusProtocolTLA+^{+} Specification Repository2003 (Safety)
Nano blockchainSystemTLA+^{+} Specification Repository3901 (Safety)
Hybrid reliable broadcastProtocolIvy examples2243 (Safety + Liveness)
Two-phase handshakeProtocolTLA+^{+} Specification Repository511 (Refinement)
Two-phase handshake (proof)ProtocolTLA+^{+} Specification Repository501 (Refinement)
Paxos commitProtocolTLA+^{+} Specification Repository1851 (Safety)
Transaction commitProtocolTLA+^{+} Specification Repository461 (Safety)
Two-phase commitProtocolTLA+^{+} Specification Repository1122 (Safety)
Walgit WALSystems3-wal-collection5587 (Safety)
SlateDB WALSystems3-wal-collection5464 (Safety)
OSWALD WALSystems3-wal-collection2603 (Safety)
BufferedRandomAccessFileSystemTLA+^{+} Specification Repository33414 (Safety + Refinement)
EWD840 termination detectionProtocolTLAPS Specification Repository731 (Safety)
EWD840ProtocolTLA+^{+} Specification Repository1212 (Safety + Refinement)
EWD840: synchronous detectionProtocolTLA+^{+} Specification Repository573 (Safety + Liveness)
Dijkstra–Scholten (EWD687a)ProtocolTLA+^{+} Specification Repository1323 (Safety)
EWD998: asynchronous detectionProtocolTLA+^{+} Specification Repository713 (Safety + Liveness)
EWD998 (PlusCal)ProtocolTLA+^{+} Specification Repository1722 (Safety + Refinement)
EWD998ProtocolTLA+^{+} Specification Repository1912 (Safety + Refinement)
Termination detectionProtocolTLA+^{+} Specification Repository691 (Safety)
Misra reachability (parallel)ProtocolTLA+^{+} Specification Repository1431 (Refinement)
Misra reachability (sequential)ProtocolTLA+^{+} Specification Repository761 (Safety)
Spanning tree (SpanTree)ProtocolTLA+^{+} Specification Repository481 (Safety)
Spanning tree (spanning)ProtocolTLA+^{+} Specification Repository441 (Safety)
TCPProtocolTLA+^{+} Specification Repository2643 (Safety)
Alternating-bit protocolProtocolIvy examples1322 (Safety + Liveness)
FiniteMonotonic CRDTProtocolTLA+^{+} Specification Repository663 (Safety + Liveness)
Multi-car elevatorProtocolTLA+^{+} Specification Repository2262 (Safety)
Voucher lifecycleSystemTLA+^{+} Specification Repository661 (Safety)
PCR workflows: cleanProtocolTLA+^{+} Specification Repository682 (Safety)
PCR workflows: stagesProtocolTLA+^{+} Specification Repository1061 (Safety)
Total195

Table A1 (continued).

Detailed Benchmark Results

Table A2 shows the proof results for each target and model configuration. Tables A3–A14 report pass@3 success rates and total resource usage across all three runs.

TargetKindGPT-6.1 SolGPT-6 AstraGPT-5.6 TerraGPT-6 Luna
maxhighlowmaxhighlowmaxhighlowmaxhighlow
FLASH cache coherence protocol
TypeOKS✓✓✓✓✓✓✓✓
ReqProgressL✓✓✓✓✓✓
DirProgressL✓✓✓✓✓✓
UniProgressL✓✓✓✓✓✓
InvProgressL✓✓✓✓✓✓✓
RpProgressL✓✓✓✓✓✓✓
WbProgressL✓✓✓✓✓✓✓✓
ShWbProgressL✓✓✓✓✓✓✓✓
NakcProgressL✓✓✓✓✓✓✓✓
CacheDataPropS✓✓✓✓✓✓
MemDataPropS✓✓✓✓✓✓✓
ExCopyPropS✓✓✓✓✓✓✓
FwdGetPendingS✓✓✓✓✓✓✓
FwdGetXPendingS✓✓✓✓✓✓✓
InvalidationAckPropS✓✓✓✓✓✓✓
ZooKeeper protocol (Zab)
Leadership1S✓
Leadership2S
PrefixConsistencyS
IntegrityS
AgreementS
TotalOrderS
LocalPrimaryOrderS
GlobalPrimaryOrderS
PrimaryIntegrityS
Cahill’s serializable snapshot isolation protocol
CahillSerializableS
Ivy TLB
NoErrorS✓✓✓✓✓✓✓✓
NonStarvationL
OpenAddressing
CompleteAsSafetyS✓✓✓✓✓✓✓✓
ConsistentS✓
ContainsS✓
DuplicatesS✓
SortedS✓✓✓✓✓✓✓✓
etcd Raft
LogInvS
CommittedIsDurableInvS
LeaderTermMaxIndexInvS✓
LeaderCompletenessInvS
LogMatchingInvS✓
LeaderUniquenessS✓✓✓✓✓✓
MoreUpToDateCorrectInvS
QuorumLogInvS
HashiCorp Raft
LeaderCompletenessS
StateMachineSafetyS
CommittedEntriesPreservedS

Table A2. Accepted targets of the current problem set for each model and reasoning effort. S, L and R denote safety, liveness and refinement proofs, respectively.

TargetKindGPT-6.1 Sol maxGPT-6.1 Sol highGPT-6.1 Sol lowGPT-6 Astra maxGPT-6 Astra highGPT-6 Astra lowGPT-5.6 Terra maxGPT-5.6 Terra highGPT-5.6 Terra lowGPT-6 Luna maxGPT-6 Luna highGPT-6 Luna low
LogMatchingS
ElectionSafetyS
ConfigurationSafetyS✓✓✓✓✓✓✓
ZooKeeper implementation
Leadership1S✓
Leadership2S✓
PrefixConsistencyS
IntegrityS
AgreementS
TotalOrderS
LocalPrimaryOrderS
GlobalPrimaryOrderS
PrimaryIntegrityS
MongoDB distributed transactions
SnapshotIsolationS
CCF
CommittedLogsAgreeS
CommittedLogsAppendOnlyS✓✓
PirateShip
TypeOKS✓✓✓
IndexBoundsInvS
BranchInvS
AuditBranchInvS
OneLeaderPerViewInvS✓✓✓✓✓✓
WellFormedBranchInvS✓
ViewMonotonicInvS✓✓✓✓✓✓
ViewStabilizationInvS✓✓✓✓✓✓
CommittedBranchAppendOnlyPropS
AuditedBranchAppendOnlyPropS
MonotonicAuditedIndexPropS✓✓✓✓✓✓
Wildfire
RefinementR
Accepted targets3124253024241500700

Table A2 (PDF p. 17).

ModelEffortSuccess Rate (pass@3)Total Tokens (M) InputTotal Tokens (M) OutputTotal Cost (USD)Total Agent Time (min)
GPT-6.1 Solmax100.0% (15/15)161.150.70237.27510.7
GPT-6.1 Solhigh100.0% (15/15)119.170.50924.92338.1
GPT-6.1 Sollow100.0% (15/15)209.830.79836.96665.6
GPT-6 Astramax100.0% (15/15)129.770.557172.75755.3
GPT-6 Astrahigh100.0% (15/15)114.090.426146.29419.5
GPT-6 Astralow100.0% (15/15)125.190.395158.78429.9
GPT-5.6 Terramax73.3% (11/15)2054.576.003555.884890.6
GPT-5.6 Terrahigh0.0% (0/15)12.890.0624.3450.5
GPT-5.6 Terralow0.0% (0/15)3.960.0211.4921.0
GPT-6 Lunamax26.7% (4/15)194.400.8612.64359.5
GPT-6 Lunahigh0.0% (0/15)5.430.0360.0917.9
GPT-6 Lunalow0.0% (0/15)1.140.0050.032.8

Table A3. Results for the FLASH cache coherence protocol.

ModelEffortSuccess Rate (pass@3)Total Tokens (M) InputTotal Tokens (M) OutputTotal Cost (USD)Total Agent Time (min)
GPT-6.1 Solmax0.0% (0/9)13.050.1603.6677.5
GPT-6.1 Solhigh0.0% (0/9)15.490.1403.8394.9
GPT-6.1 Sollow0.0% (0/9)14.650.0893.0453.3
GPT-6 Astramax11.1% (1/9)43.040.38071.11237.2
GPT-6 Astrahigh0.0% (0/9)10.500.08217.4454.4
GPT-6 Astralow0.0% (0/9)9.210.05614.4042.7
GPT-5.6 Terramax0.0% (0/9)2220.786.001580.624415
GPT-5.6 Terrahigh0.0% (0/9)9.530.0463.2035.1
GPT-5.6 Terralow0.0% (0/9)2.640.0181.1617.9
GPT-6 Lunamax0.0% (0/9)105.810.5141.44164.6
GPT-6 Lunahigh0.0% (0/9)4.190.0230.0731.9
GPT-6 Lunalow0.0% (0/9)1.440.0050.034.1

Table A4. Results for the ZooKeeper protocol (Zab).

ModelEffortSuccess Rate (pass@3)Total Tokens (M) InputTotal Tokens (M) OutputTotal Cost (USD)Total Agent Time (min)
GPT-6.1 Solmax0.0% (0/1)36.710.2968.01172.4
GPT-6.1 Solhigh0.0% (0/1)19.410.1364.3282.3
GPT-6.1 Sollow0.0% (0/1)2.400.0230.8114.1
GPT-6 Astramax0.0% (0/1)18.600.14631.5377.6
GPT-6 Astrahigh0.0% (0/1)8.030.05713.2839.0
GPT-6 Astralow0.0% (0/1)1.900.0174.1813.5
GPT-5.6 Terramax0.0% (0/1)2548.605.996644.286256.9
GPT-5.6 Terrahigh0.0% (0/1)6.930.0482.5740.4
GPT-5.6 Terralow0.0% (0/1)3.210.0191.2925.1
GPT-6 Lunamax0.0% (0/1)23.300.1830.3765.6
GPT-6 Lunahigh0.0% (0/1)1.570.0180.048.3
GPT-6 Lunalow0.0% (0/1)0.610.0030.023.0

Table A5. Results for Cahill’s serializable snapshot isolation protocol.

ModelEffortSuccess Rate (pass@3)Total Tokens (M) InputTotal Tokens (M) OutputTotal Cost (USD)Total Agent Time (min)
GPT-6.1 Solmax50.0% (1/2)61.770.40711.98216.3
GPT-6.1 Solhigh50.0% (1/2)62.020.27510.25175.3
GPT-6.1 Sollow50.0% (1/2)45.090.2108.26168.8
GPT-6 Astramax50.0% (1/2)43.320.23860.84139.7
GPT-6 Astrahigh50.0% (1/2)20.140.11629.8493.4
GPT-6 Astralow50.0% (1/2)25.640.12535.53103.6
GPT-5.6 Terramax50.0% (1/2)1922.136.002515.813097.6
GPT-5.6 Terrahigh0.0% (0/2)16.650.0745.1354.3
GPT-5.6 Terralow0.0% (0/2)4.530.0331.7329.9
GPT-6 Lunamax50.0% (1/2)995.783.64913.032475.9
GPT-6 Lunahigh0.0% (0/2)1.860.0190.0418.3
GPT-6 Lunalow0.0% (0/2)1.690.0080.044.1

Table A6. Results for Ivy TLB.

ModelEffortSuccess Rate (pass@3)Total Tokens (M) — InputTotal Tokens (M) — OutputTotal Cost (USD)Total Agent Time (min)
GPT-6.1 Solmax100.0% (5/5)275.381.19456.93846.1
GPT-6.1 Solhigh40.0% (2/5)30.050.1686.0193.6
GPT-6.1 Sollow40.0% (2/5)17.450.0853.3344.0
GPT-6 Astramax40.0% (2/5)40.270.24159.60150.0
GPT-6 Astrahigh40.0% (2/5)18.520.10227.1661.5
GPT-6 Astralow40.0% (2/5)19.320.06926.0053.6
GPT-5.6 Terramax40.0% (2/5)2266.446.005594.606356.0
GPT-5.6 Terrahigh0.0% (0/5)10.950.0603.6232.1
GPT-5.6 Terralow0.0% (0/5)2.850.0201.2115.3
GPT-6 Lunamax40.0% (2/5)702.702.6829.131452.2
GPT-6 Lunahigh0.0% (0/5)4.960.0400.1037.6
GPT-6 Lunalow0.0% (0/5)0.550.0050.011.4

Table A7. Results for OpenAddressing.

ModelEffortSuccess Rate (pass@3)Total Tokens (M) — InputTotal Tokens (M) — OutputTotal Cost (USD)Total Agent Time (min)
GPT-6.1 Solmax37.5% (3/8)189.900.69638.60479.1
GPT-6.1 Solhigh12.5% (1/8)63.500.27210.59265.2
GPT-6.1 Sollow12.5% (1/8)57.870.2869.89199.5
GPT-6 Astramax12.5% (1/8)47.600.24166.92220.8
GPT-6 Astrahigh12.5% (1/8)47.670.17961.27171.3
GPT-6 Astralow12.5% (1/8)27.310.19941.52253.4
GPT-5.6 Terramax0.0% (0/8)2998.186.006750.549107.1
GPT-5.6 Terrahigh0.0% (0/8)5.440.0422.0928.3
GPT-5.6 Terralow0.0% (0/8)2.850.0201.2618.2
GPT-6 Lunamax0.0% (0/8)18.800.1900.3365.1
GPT-6 Lunahigh0.0% (0/8)1.520.0190.047.0
GPT-6 Lunalow0.0% (0/8)0.750.0050.022.0

Table A8. Results for etcd Raft.

ModelEffortSuccess Rate (pass@3)Total Tokens (M) — InputTotal Tokens (M) — OutputTotal Cost (USD)Total Agent Time (min)
GPT-6.1 Solmax16.7% (1/6)29.260.2596.74157.9
GPT-6.1 Solhigh16.7% (1/6)17.870.1213.8166.7
GPT-6.1 Sollow16.7% (1/6)48.530.1958.04164.6
GPT-6 Astramax16.7% (1/6)17.100.13528.0082.0
GPT-6 Astrahigh16.7% (1/6)20.320.11029.4773.3
GPT-6 Astralow16.7% (1/6)18.440.09526.5976.4
GPT-5.6 Terramax16.7% (1/6)1822.034.606476.724625.9
GPT-5.6 Terrahigh0.0% (0/6)9.530.0463.2040.6
GPT-5.6 Terralow0.0% (0/6)2.970.0201.2420.7
GPT-6 Lunamax0.0% (0/6)69.400.3840.98111.4
GPT-6 Lunahigh0.0% (0/6)1.660.0190.0414.8
GPT-6 Lunalow0.0% (0/6)0.760.0040.021.8

Table A9. Results for HashiCorp Raft.

ModelEffortSuccess Rate (pass@3)Total Tokens (M) — InputTotal Tokens (M) — OutputTotal Cost (USD)Total Agent Time (min)
GPT-6.1 Solmax0.0% (0/9)33.220.2667.58131.3
GPT-6.1 Solhigh0.0% (0/9)23.430.2055.57195.6
GPT-6.1 Sollow0.0% (0/9)10.270.0602.2041.6
GPT-6 Astramax22.2% (2/9)122.500.367145.98229.3
GPT-6 Astrahigh0.0% (0/9)17.480.09725.3278.9
GPT-6 Astralow0.0% (0/9)5.430.0288.9221.2
GPT-5.6 Terramax0.0% (0/9)2255.796.002587.395290.9
GPT-5.6 Terrahigh0.0% (0/9)15.980.0524.8256.1
GPT-5.6 Terralow0.0% (0/9)2.050.0160.9814.8
GPT-6 Lunamax0.0% (0/9)23.730.1510.3654.1
GPT-6 Lunahigh0.0% (0/9)3.250.0190.0612.4
GPT-6 Lunalow0.0% (0/9)1.060.0050.022.6

Table A10. Results for the ZooKeeper implementation.

ModelEffortSuccess Rate (pass@3)Total Tokens (M) — InputTotal Tokens (M) — OutputTotal Cost (USD)Total Agent Time (min)
GPT-6.1 Solmax0.0% (0/1)23.330.1835.42109.8
GPT-6.1 Solhigh0.0% (0/1)11.500.0712.4842.2
GPT-6.1 Sollow0.0% (0/1)9.950.0572.0629.9
GPT-6 Astramax0.0% (0/1)15.360.11124.4976.2
GPT-6 Astrahigh0.0% (0/1)6.880.05111.8432.2
GPT-6 Astralow0.0% (0/1)4.810.0257.7917.9
GPT-5.6 Terramax0.0% (0/1)761.252.530207.592349.4
GPT-5.6 Terrahigh0.0% (0/1)11.860.0583.8252.6
GPT-5.6 Terralow0.0% (0/1)1.930.0160.9010.3
GPT-6 Lunamax0.0% (0/1)31.620.2750.5374.1
GPT-6 Lunahigh0.0% (0/1)2.270.0210.0510.0
GPT-6 Lunalow0.0% (0/1)0.700.0060.021.9

Table A11. Results for MongoDB distributed transactions.

ModelEffortSuccess Rate (pass@3)Total Tokens (M) — InputTotal Tokens (M) — OutputTotal Cost (USD)Total Agent Time (min)
GPT-6.1 Solmax50.0% (1/2)513.562.677123.552620.9
GPT-6.1 Solhigh0.0% (0/2)200.271.06249.851029.7
GPT-6.1 Sollow0.0% (0/2)14.680.0652.6258.0
GPT-6 Astramax50.0% (1/2)151.451.054226.181041.4
GPT-6 Astrahigh0.0% (0/2)27.130.11837.51114.2
GPT-6 Astralow0.0% (0/2)9.240.03112.74138.2
GPT-5.6 Terramax0.0% (0/2)1632.574.309423.873353.0
GPT-5.6 Terrahigh0.0% (0/2)11.930.0543.8144.2
GPT-5.6 Terralow0.0% (0/2)3.780.0231.4616.4
GPT-6 Lunamax0.0% (0/2)40.410.2070.56110.2
GPT-6 Lunahigh0.0% (0/2)2.530.0210.0611.0
GPT-6 Lunalow0.0% (0/2)2.510.0100.045.7

Table A12. Results for CCF.

ModelEffortSuccess Rate (pass@3)Total Tokens (M)Total Cost (USD)Total Agent Time (min)
GPT-6.1 Solmax45.5% (5/11)108.280.78826.35538.5
GPT-6.1 Solhigh36.4% (4/11)63.560.28911.00299.2
GPT-6.1 Sollow45.5% (5/11)115.430.35019.73342.1
GPT-6 Astramax54.5% (6/11)131.920.716182.73918.1
GPT-6 Astrahigh36.4% (4/11)55.190.27475.18303.5
GPT-6 Astralow36.4% (4/11)22.320.10130.5884.1
GPT-5.6 Terramax0.0% (0/11)932.622.422246.212495.3
GPT-5.6 Terrahigh0.0% (0/11)9.190.0453.0555.2
GPT-5.6 Terralow0.0% (0/11)3.260.0241.2918.2
GPT-6 Lunamax0.0% (0/11)127.580.4031.64336.5
GPT-6 Lunahigh0.0% (0/11)3.350.0320.0726.3
GPT-6 Lunalow0.0% (0/11)1.740.0100.0314.9

Table A13. Results for PirateShip.

ModelEffortSuccess Rate (pass@3)Total Tokens (M)Total Cost (USD)Total Agent Time (min)
GPT-6.1 Solmax0.0% (0/1)10.530.1032.7856.9
GPT-6.1 Solhigh0.0% (0/1)9.290.0642.1342.3
GPT-6.1 Sollow0.0% (0/1)3.080.0210.8214.3
GPT-6 Astramax0.0% (0/1)9.290.08316.3165.0
GPT-6 Astrahigh0.0% (0/1)7.150.05011.96134.4
GPT-6 Astralow0.0% (0/1)4.050.0196.3827.9
GPT-5.6 Terramax0.0% (0/1)60.910.35218.65243.8
GPT-5.6 Terrahigh0.0% (0/1)5.960.0482.3539.2
GPT-5.6 Terralow0.0% (0/1)1.430.0140.777.1
GPT-6 Lunamax0.0% (0/1)4.630.0870.1116.2
GPT-6 Lunahigh0.0% (0/1)1.380.0160.034.7
GPT-6 Lunalow0.0% (0/1)0.850.0030.021.5

Table A14. Results for Wildfire.

Accepted Proofs, Incomplete Proofs, and Disproved Targets

This appendix shows simplified versions of proofs submitted by agents in the benchmark runs of § 5, including both accepted proofs and incomplete proofs. We also include one disproved target found during task validation (§ 4.3). In TLAPS, a BY clause lists facts and proof hints to justify a proof step. A hint can choose a backend prover or pick a proof strategy: SMTT calls an SMT solver, Isa calls Isabelle, PTL calls the temporal logic prover, ExpandENABLED hints the backend to expand the ENABLED operator. We drop some auxiliary steps to keep the examples short.

Accepted Proofs

FLASH: eventual message delivery. FLASH has eight liveness targets concerning request completion and message delivery. Example 1 shows a proof of WbProgressCorrect, which states that a pending writeback message is eventually delivered under the assumption of weak fairness: if the action remains enabled, it eventually takes a step [20]. The action NI_Wb delivers the message, and the specification FairSpec assumes weak fairness of NI_Wb. Step <1>1 shows that NI_Wb can be taken while the message is pending, using the type invariant TypeOK. Step <1>2 shows that if NI_Wb is taken, the message will be delivered. Step <1>3 extracts the fairness assumption from FairSpec, and step <1>4 shows that TypeOK always holds by reusing the proved target TypeCorrect. The other seven liveness targets follow the same pattern or chain several such steps through helper lemmas.

\* (target and action, from the read-only task files)
WbProgress == (WbMsg.Cmd = "WB_Wb") ~> (WbMsg.Cmd = "WB_None")
NI_Wb ==
    /\ WbMsg.Cmd = "WB_Wb"
    /\ WbMsg' = [Cmd |-> "WB_None", Proc |-> Undefined, Data |-> Undefined]
    /\ ... \* (omitted: directory and memory updates)

THEOREM WbProgressCorrect == FairSpec => WbProgress
<1>1. TypeOK /\ (WbMsg.Cmd # "WB_None") => ENABLED <<NI_Wb>>_vars
    BY SMTT("r30"), ExpandENABLED
    DEF NI_Wb, TypeOK, vars, pendVars, fwdVars, RP_CMD, WB_CMD, SHWB_CMD, NAKC_CMD
<1>2. <<NI_Wb>>_vars => (WbMsg.Cmd = "WB_None")'
    BY SMTT("r10") DEF NI_Wb, vars
<1>3. FairSpec => WF_vars(NI_Wb)
    BY Isa DEF FairSpec, Fairness
<1>4. FairSpec => []TypeOK
    BY TypeCorrect, SMTT("r10") DEF FairSpec, Spec
<1>5. QED BY <1>1, <1>2, <1>3, <1>4, PTL DEF WbProgress

Example 1. Accepted proof of the FLASH liveness target by GPT-6.1 Sol at high effort (simplified).

etcd Raft: leader uniqueness. The target LeaderUniqueness states that two leaders in the same term are the same server. Example 2 shows the accepted proof by GPT-6 Astra at max effort, and Figure 2 shows a simplified version of this task. The auxiliary invariant AgElectionInv treats each granted vote as a ballot <<voter, term, candidate>>, wherever the vote is currently stored: in a pending or delivered vote response, or in the votesGranted set of a candidate or leader. AgAgreement states that a voter’s ballots in one term name at most one candidate. AgPendingBound and AgDurableBound tie each ballot to the voter’s own term and vote. They use durable state for delivered and collected votes, so the invariant still holds after a server crashes and restarts. Given the invariant, the target follows from quorum intersection: two leaders in the same term each hold a quorum of votes, a voter in both quorums has a ballot for each leader, and AgAgreement makes the two leaders equal. The agent proves that every action preserves the invariant with one lemma per action.

\* Vote certificates are retained in pending messages, delivered messages,
\* and the vote sets of active candidates and leaders.
AgVoteMsgs(bag) ==
    {m \in DOMAIN bag : m.mtype = RequestVoteResponse /\ m.mvoteGranted}
AgMsgBallots(bag) == {<<m.msource, m.mterm, m.mdest>> : m \in AgVoteMsgs(bag)}
AgPending == AgMsgBallots(pendingMessages)
AgSent == AgMsgBallots(messages)
AgGranted ==
    UNION {<<v, currentTerm[i], i>> : v \in votesGranted[i] : i \in {j \in Server : AgActive(j)}}
AgBallots == AgPending \cup AgSent \cup AgGranted
\* Pending votes are protected by volatile state. Delivered and collected
\* votes are protected by durable state, so their protection survives a crash.
AgPendingBound == \A b \in AgPending :
    /\ b[2] <= currentTerm[b[1]]
    /\ b[2] = currentTerm[b[1]] => votedFor[b[1]] = b[3]
AgDurableBound == \A b \in AgSent \cup AgGranted :
    /\ b[2] <= durableState[b[1]].currentTerm
    /\ b[2] = durableState[b[1]].currentTerm
        => durableState[b[1]].votedFor = b[3]

\* A voter has at most one candidate among certificates for the same term.
AgAgreement == \A b, c \in AgBallots :
    b[1] = c[1] /\ b[2] = c[2] => b[3] = c[3]
AgElectionInv ==
    /\ AgBasic /\ ... \* (AgBasic includes state[i] = Leader =>
                         \* votesGranted[i] \in Quorum(InitServer))
    /\ AgPendingBound /\ AgDurableBound /\ AgAgreement

LEMMA AgElectionSafetyConsequence == AgElectionInv => LeaderUniqueness
<1>1. ASSUME AgElectionInv, NEW i \in Server, NEW j \in Server,
                  currentTerm[i] = currentTerm[j], state[i] = Leader, state[j] = Leader
      PROVE i = j
<2>1. votesGranted[i] \in Quorum(InitServer)
      /\ votesGranted[j] \in Quorum(InitServer)
      BY <1>1, SMTT("r5") DEF AgElectionInv, AgBasic
<2>2. PICK v \in InitServer :
          v \in votesGranted[i] /\ v \in votesGranted[j]
      BY <2>1, AgQuorumIntersection, FiniteServers
<2>3. <<v, currentTerm[i], i>> \in AgBallots
      /\ <<v, currentTerm[j], j>> \in AgBallots
      BY <1>1, <2>2, SMTT("r5") DEF AgBallots, AgGranted, AgActive
<2>4. QED BY <1>1, <2>3, SMTT("r5") DEF AgElectionInv, AgAgreement
<1>2. QED BY <1>1 DEF LeaderUniqueness

\* (omitted: AgElectionInit and AgElectionStep, the initial-state and step lemmas)
LEMMA AgElectionAlways == Spec => []AgElectionInv
BY AgElectionInit, AgElectionStep, PTL DEF Spec
THEOREM LeaderUniquenessTheorem == Spec => []LeaderUniqueness
BY ONLY AgElectionAlways, AgElectionSafetyConsequence, PTL

Example 2. Accepted proof of the etcd Raft target LeaderUniqueness by GPT-6 Astra at max effort (simplified).

Proof Failures

An accepted proof of a safety target Spec => []P (Example 2) usually requires discovering and proving auxiliary invariants and helper lemmas, and deriving P from these proof facts. Liveness targets (Example 1) additionally require progress lemmas connecting fairness assumptions with intermediate state machine stages. Any missing segment in the proof chain will fail the task.

The two most common failure categories in Table 5 are undecomposed proof attempts and incomplete proofs. In undecomposed attempts, agents submit entire targets directly to backends. Agents may do so before developing a proof strategy or after their own proof attempts stall. We illustrate this with an Ivy TLB example below. Incomplete proofs reveal difficulties in discovering useful invariants, establishing proposed invariants or lemmas, and connecting established results to the target property. We present one example for each of these three cases below.

Undecomposed liveness proof: Ivy TLB. GPT-6 Astra at max effort proved the TLB safety target with an inductive invariant AGInv, and all 30 of its helper lemmas passed verification. For the liveness target NonStarvation, however, the agent submitted a single call to the temporal-logic backend PTL (Example 3), which must derive the target from the definitions of Spec and NonStarvation alone. A liveness proof instead needs progress lemmas showing that, under the fairness assumptions in Spec, the processor’s loops terminate and the locks it waits for are eventually released. The agent did attempt such a proof in scratch modules alongside the safety proof, and checked its finiteness and control-flow steps. However, it could not prove that the actions in the fairness assumptions are enabled, which is required to apply fairness. It kept these attempts out of the submission and ended the session with the one-step proof it had written at the start, which the backend rejects in under a second.

\* (target and fairness assumptions, from the read-only task files)
Spec ==
    /\ SafetySpec \* (Init /\ [][Next]_vars)
    /\ \A p \in Processor : WF_vars(Step(p))
    /\ \A p \in Processor : SF_vars(BootStep(p))
    /\ \A p \in Processor : SF_vars(AcquirePmapLock(p))
    /\ \A p \in Processor : SF_vars(AcquireResponderActionLock(p))
ProcessorMakesProgress(p) == pc[p] \in {MainCheck, ResponderClearActionNeeded}
NonStarvation == \A p \in Processor : TRUE ~> ProcessorMakesProgress(p)

\* (helpers for Safety, all verified; proofs and the per-action lemmas omitted)
AGInv == AGType /\ AGPmap /\ AGAction /\ AGControl /\ AGCoverage
        /\ AGCoherent /\ ~error
LEMMA AGInitial == Init => AGInv
LEMMA AGInduction == AGInv /\ [Next]_vars => AGInv'
LEMMA AGInvariant == SafetySpec => []AGInv

THEOREM Safety == SafetySpec => []NoError
BY AGInvariant, PTL DEF AGInv, NoError

THEOREM Liveness == Spec => NonStarvation
BY PTL DEF Spec, NonStarvation

Example 3. Undecomposed proof of the Ivy TLB liveness target NonStarvation by GPT-6 Astra at max effort (simplified). Safety is accepted; the one-step proof of Liveness fails verification.

Missing invariant for one case: OpenAddressing. In the OpenAddressing model, writers insert fingerprints into a hash table. A writer probes up to L slots, starting from the fingerprint’s home slot idx(f, 0). If it finds neither the fingerprint nor a free slot, it triggers an eviction, which moves table entries into external sorted sequences. GPT-6 Astra at max effort proves two of the five targets and verifies all 50 of its helper lemmas, but leaves Consistent (Example 4) and other proofs incomplete. The proof splits into two cases. In the first case, OAHashScale > 0 and L > 0, so distinct fingerprints have distinct home slots, every insertion succeeds at its first probe, and no eviction occurs. The invariant OADirectInv describes this behavior, and this case is verified. The second case covers hash collisions and evictions, where probing and eviction actually take place. The agent’s comment notes that this case needs a stronger invariant, but the step cites only three existing invariants, and the SMT solver fails to prove it. The proof therefore covers only configurations without collisions or evictions.

\* (when OAHashScale > 0, distinct fingerprints have distinct home slots idx(f, 0))
OAHashScale == (K-1) \div (max(fps)-min(fps))

OADirectInv ==
    /\ ...  \* (omitted: types and control states)
    /\ external = <<>>
    /\ newexternal = <<>>
    /\ evict = FALSE
    /\ index = [w \in Writer |-> 0]
    /\ \A i \in 1..K : table[i] # empty => i = idx(table[i],0)
    /\ ...

THEOREM Spec => []Consistent
  <1>1. OAHashScale > 0 /\ L > 0 => (Spec => []Consistent)
    <2>1. OADirectInv => Consistent BY OADirectSafety
    <2>2. QED BY <2>1, OADirectInv, PTL
  <1>2. OAHashScale = 0 \/ L = 0 => (Spec => []Consistent)
\* The collision case also needs preservation of the table and scan invariant.
BY OAControlInvariant, OATypesInvariant, OASortedInvariant, SMTT("r1")
<1>3. OAHashScale \in Nat /\ L \in Nat
BY OAHashScaleType, OAAssumption, SMTT("r10")
<1>4. QED BY <1>1, <1>2, <1>3, SMTT("r10")

Example 4. Incomplete proof of the OpenAddressing target Consistent by GPT-6 Astra at max effort (simplified). Step <1>2 fails verification.

Missing progress lemmas: Ivy TLB. GPT-6 Astra at high effort proved the TLB safety target with an inductive invariant and verified all 29 of its helper lemmas. Its proof of the liveness target NonStarvation (Example 5) combined this invariant and the specification’s fairness assumptions and tried to prove the liveness goal. However, the agent did not state the progress lemmas needed to show that the locks are eventually released and the processor’s loops terminate. As a result, the final step failed verification, and a comment the agent left in the proof listed these missing steps.

\* (target and fairness assumptions, from the read-only task files)
Spec ==
    /\ SafetySpec  \* (Init /\ [][Next]_vars)
    /\ \A p \in Processor : WF_vars(Step(p))
    /\ \A p \in Processor : SF_vars(BootStep(p))
    /\ \A p \in Processor : SF_vars(AcquirePmapLock(p))
    /\ \A p \in Processor : SF_vars(AcquireResponderActionLock(p))
ProcessorMakesProgress(p) == pc[p] \in {MainCheck, ResponderClearActionNeeded}
NonStarvation == \A p \in Processor : TRUE ~> ProcessorMakesProgress(p)

\* (helpers, all verified; proofs and most conjuncts omitted)
AgentInv == AgentTypes /\ AgentActivity /\ AgentPmapLock /\ ... /\ NoError
LEMMA AgentInitial == Init => AgentInv
LEMMA AgentInductive == AgentInv /\ [Next]_vars => AgentInv'

THEOREM Liveness == Spec => NonStarvation
<1>1. SafetySpec => []AgentInv
    BY AgentInitial, AgentInductive, PTL DEF SafetySpec
<1>2. ASSUME NEW p \in Processor
    PROVE Spec => (TRUE ~> ProcessorMakesProgress(p))
    <2>1. Spec => []AgentInv
        BY <1>1 DEF Spec
    <2>2. Spec => WF_vars(Step(p))
        BY <1>2 DEF Spec
    <2>3. Spec => /\ SF_vars(BootStep(p))
                 /\ SF_vars(AcquirePmapLock(p))
                 /\ SF_vars(AcquireResponderActionLock(p))
        BY <1>2 DEF Spec
    \* Remaining obligation: termination of the two todo loops and
    \* eventual release of the locks on which this processor can wait.
    <2> QED BY <2>1, <2>2, <2>3, PTL DEF ProcessorMakesProgress
<1> QED BY <1>2 DEF NonStarvation

Example 5. Incomplete proof of the Ivy TLB liveness target NonStarvation by GPT-6 Astra at high effort (simplified). Step <2> QED fails verification, as do steps <2>1–<2>3.

Unproved invariant: Cahill SSI. GPT-6 Astra at max effort stated a candidate invariant CSInvariant for SSI and proved that it implies serializability and holds at Init (step <1>1 of Example 6), but it did not prove the inductive step <1>2, which shows that every action preserves the invariant. Instead, the agent tested the invariant with TLC by simulating executions from Init. Passing these tests only shows that CSInvariant holds in the sampled reachable states of a small model, while the proof additionally requires it to be inductive.

CSInvariant ==
    /\ CSStateTypes /\ CSCore /\ CSWaitSafe
    /\ CShistoryConditions(history, inConflict, outConflict)
\* (helpers, both verified; proofs omitted)
LEMMA CSInvariantInitial == Init => CSInvariant
LEMMA CSInvariantSafety == CSInvariant => CahillSerializable(history)

THEOREM CahillSerializableCorrect == Spec => []CahillSerializable(history)
<1>1. Init => CSInvariant BY CSInvariantInitial, SMTT("r5")
<1>2. CSInvariant /\ Next => CSInvariant'
  BY SMTT("r5") DEF CSInvariant, Next
<1>3. CSInvariant /\ UNCHANGED allvars => CSInvariant'
  \* (omitted: proof for stuttering steps)
<1>4. CSInvariant => CahillSerializable(history) BY CSInvariantSafety, SMTT("r5")
<1>5. QED BY <1>1, <1>2, <1>3, <1>4, PTL DEF Spec

\* (the agent's TLC model, scratch/MCCahill.tla and MCCahill.cfg)
MCInv == CSInvariant /\ CahillSerializable(history)
INIT Init
NEXT Next
INVARIANT MCInv

Example 6. Incomplete proof of the Cahill SSI target by GPT-6 Astra at max effort (simplified), with the TLC model it used to test the invariant. Step <1>2 fails verification. The TLC model starts from Init, so it checks the invariant only on reachable states.

Disproved Targets

SlateDB WAL: a counterexample to the target. A task can also end with a counterexample when the target is false (§ 4.1). In a run before the evaluation of § 5, GPT-6 Astra at max effort proved one of the four targets of the original SlateDB WAL model and reported that ConsistentMachineData does not hold and submitted a 58-transition TLC counterexample. Example 7 shows the agent’s summary of the trace. We reproduced the trace, reported it upstream, and revised the model; Appendix § 13 describes the repair, after which Astra proves all four targets.

The essential schedule is:

1. Writer w1 becomes ready with a fence at WAL ID 1.
2. Writer w2 chooses WAL ID 2 as its fence position. Before it claims its epoch,
   w1 appends v1 at ID 2 and v2 at ID 3.
3. w2 claims epoch 2 and passes the boundary check, but delays writing its fence.
4. w3 claims epoch 3, writes its fence at ID 4, validates successfully, and
   starts replaying. Pause it before replaying ID 2.
5. w4 claims epoch 4, writes its fence at ID 5, replays the full log, and commits
   snapshot 5 containing <<v1, v2>>. The latest manifest now has ID 6 and
   replayAfterWalId = 6.
6. The garbage collector deletes the data entry at ID 2, leaving ID 3 present.
7. The delayed w2 writes a fence at the now-vacant ID 2.
8. w3 skips the new fence at ID 2, reads v2 at ID 3, skips its own fence at
   ID 4, and reaches READY with machine data <<v2>>.

The final history is <<[walId |-> 2, value |-> v1], [walId |-> 3, value |-> v2]>>.
Since v1 # v2, PrefixOf(<<v2>>, auxWrittenEntries) is false.
Thus Spec => []ConsistentMachineData is false under the supplied context.

Example 7. Counterexample summary submitted by GPT-6 Astra at max effort for the SlateDB WAL target ConsistentMachineData.

Representative Specification Fixes

Section 4.1 summarizes the issues we found in source specifications during task construction. Table A15 lists representative issues. For each issue, we collect counterexamples and check each repair with model checking. We describe two of these cases in detail below.

SpecificationIssueRepairStatus
OpenAddressingWith a single fingerprint, the divisor max(fps) - min(fps) in the hash rescaling is zero.Require a finite set of at least two fingerprints.Fixed upstream
MongoDBvars omits five of the 25 state variables, so stuttering steps can change them.Add them to vars.Fixed upstream
Walgit WALOverlapping CASE guards allow replay to skip a checkpoint and omit committed data. Reordering the branches exposes a violation hidden by TLC’s default order.Make replay and retry guards mutually exclusive.Reported; no response
MongoDBOne transaction can start at two routers with different read timestamps, violating SnapshotIsolation (§ 4.1).Check all routers before a transaction starts.Fixed upstream
SailfishCorrect nodes accept a Byzantine leader’s proposal without a predecessor reference or a no-vote certificate, violating Agreement.Check the predecessor reference or no-vote certificate before admission.Fixed upstream
SlateDB WALA delayed writer’s fence, written after garbage collection, is skipped during replay, and ConsistentMachineData fails.Validate the writer’s epoch after replay.Reported; no response
B-treeNext has no action for splitting an inner node, so an insertion can deadlock.Not repaired; the five safety targets do not concern insertion progress.Acknowledged upstream
HashiCorp RaftReplication acknowledgments report the follower’s whole log length instead of the replicated prefix.Acknowledge the replicated prefix, as the implementation does.Fixed upstream
etcd RaftLeaderCompletenessInv compares leaders with the term that created an entry instead of the term that committed it.Compare committed prefixes with later elections.Fixed upstream

Table A15. Representative specification issues and their repairs.

etcd Raft: a bug in the theorem. Raft’s leader completeness property says that an entry committed in some term appears in the log of every leader of a later term [31]. The original LeaderCompletenessInv (Example 8) instead compares a leader’s term with the term in which the entry was created. This theorem fails as Raft allows an entry to be committed late. The agent reported a counterexample with 47 transitions. We correct the theorem to talk about the committed term. We use commitHistory to record the term and committed log prefix whenever a server’s commit index advances, and electionHistory to record each leader’s term and log at election time.

-LeaderCompletenessInv ==
-    \A i \in Server :
-        LET committed == Committed(i) IN
-        \A idx \in 1..Len(committed) :
-            LET entry == log[i][idx] IN
-            \A l \in CurrentLeaders :
-                currentTerm[l] > entry.term =>
-                    log[l][idx] = entry
+LeaderCompletenessInv ==
+    \A c \in commitHistory, e \in electionHistory :
+        c.term < e.term => IsPrefix(c.entries, e.entries)

Example 8. Correction of the etcd Raft target LeaderCompletenessInv.

SlateDB WAL: a bug in the model. GPT-6 Astra disproved ConsistentMachineData on the original SlateDB WAL model with a 58-transition TLC counterexample (Example 7). After garbage collection deletes a DATA entry, a delayed writer writes a FENCE at the same position. Another writer replaying from an older snapshot skips the FENCE and enters READY without recovering the deleted data. We reported the trace upstream. Our revision adds a validation step

(Example 9): after replay, the writer reloads the latest log metadata and stops if a newer writer has taken over. The target properties are unchanged. On the revised model, Astra proves all four targets.

ReplayWAL(w) ==
    ...
        CASE id = wNextWalId[w] ->
-           /\ wState' = [wState EXCEPT ![w] = READY]
+           /\ wState' = [wState EXCEPT ![w] = VALIDATE_AFTER_REPLAY]
            /\ wReplayId' = [wReplayId EXCEPT ![w] = 0]
    ...
+ValidateEpochAfterReplay(w) ==
+       /\ wState[w] = VALIDATE_AFTER_REPLAY
+       /\ CASE DoRefresh(w) ->
+              /\ RefreshManifest(w)
+              /\ UNCHANGED wState
+          [] ~DoRefresh(w) /\ (wManifestLoad[w].valid = FALSE
+                              \/ wEpoch[w] < wManifest[w].writerEpoch) ->
+              /\ wState' = [wState EXCEPT ![w] = FENCED]
+              /\ ManifestRefreshed(w)
+          [] ... \* (omitted: a newer local epoch leads to ILLEGAL_STATE)
+          [] ~DoRefresh(w) /\ wManifestLoad[w].valid
+                         /\ wEpoch[w] = wManifest[w].writerEpoch ->
+              /\ wState' = [wState EXCEPT ![w] = READY]
+              /\ ManifestRefreshed(w)
+       /\ UNCHANGED <<storeVars, gcVars, auxVars, wEpoch,
+                     wNextWalId, wReplayId, wMachineData>>
    ...
Next ==
    ...
+       \/ ReplayWAL(w)
+       \/ ValidateEpochAfterReplay(w)

Example 9. Repair of the SlateDB WAL model (abridged diff, line breaks added).

Agent Prompt and Skills

We reproduce the proof construction prompt and the two agent skills supplied with the harness. The prompt is shown for etcd_raft.tla.

Proof Construction Prompt

The following prompt specifies the editable regions, available proof libraries, checker commands, and requirements for an accepted proof.

Proof Construction Prompt

# Task

Prove every target theorem in etcd_raft.tla. This is the only submitted file and represents one complete module task. Every supplied TLA+ context file in the workspace is read-only.

You may create temporary wrappers, configs, traces, and other scratch files for local TLC or Apalache exploration. They are not submitted. Grading reconstructs a clean workspace from etcd_raft.tla and the canonical read-only context, so the final task must not import or depend on scratch files.

Only edit inside the `\* BEGIN AGENT HELPERS` ... `\* END AGENT HELPERS` region and each identified AGENT PROOF region (`\* BEGIN AGENT PROOF <proof-unit-id>` ... `\* END AGENT PROOF <proof-unit-id>`). Do not change the proof-unit IDs on the marker lines. You may choose the proof strategy and reuse any earlier sibling theorem once it is proved.

Put fresh same-module operator definitions, module-level USE DEF or HIDE DEF directives, and fully proved named helper lemmas in AGENT HELPERS. Put each target theorem's proof only in its matching identified proof region.

# Proving and iterating

Audited official proof libraries are available at /opt/proof-libraries/tlapm and $COMMUNITY_LIB. Allowed modules are listed in $TLAPS_PROOF_LIBRARY_CATALOG. Inside AGENT HELPERS you may add LOCAL <alias> == INSTANCE <module> from that catalog, but you must not modify library files or use `WITH`.

You may run:

~~~sh
/opt/tlapm/bin/tlapm -I /opt/proof-libraries/tlapm -I "$COMMUNITY_LIB" etcd_raft.tla
~~~

Keep refining the module until this authoritative check reports PASS:

~~~sh
check_proof_bin etcd_raft.tla --mode proof-from-scratch
~~~

Use this command without overriding `--timeout` or `--check-cpus`; it inherits the run's frozen verification policy. If a check reports a configuration error, follow its `RETRY-COMMAND` and obtain a proof-check result before submitting. Raw TLAPM and

Proof Construction Prompt

--sany-only do not check the complete submission contract.

The checker reports a raw result for every target and every helper theorem used by a target. A raw PASS counts only when all local theorem dependencies are also trusted, so a proof cannot rely on an omitted or circular sibling.

Run the checker in the foreground and wait for that tool execution to finish. For a long-running tool call, use the tool's blocking wait facility rather than repeatedly launching checks or polling files. Each independent self-check has the same module budget as final grading; use --check-session DIR only when intentionally resuming one interrupted check of the unchanged candidate. A NOT_STARTED result means the module budget expired before that unit was checked, not that its proof failed.

For a quick syntax check, run:

check_proof_bin etcd_raft.tla --mode proof-from-scratch --sany-only

If you must stop early, leave your best partial proofs in the module and run the authoritative check on that final file. Fix reported integrity violations, including edits to fixed whitespace, and rerun it after any correction. Independently trusted proof units still receive credit when the submission satisfies the integrity checks.

Constraints

  • Do not change the module header, imports, marker lines, theorem statements, theorem order, or any text outside the editable regions.

  • Do not modify or replace supplied dependency modules, and do not make the final task depend on scratch modules.

  • Do not add EXTENDS, nested modules, CONSTANT, VARIABLE, ASSUME, ASSUMPTION, or AXIOM declarations. INSTANCE is allowed only in the official-library form described above.

  • Every helper LEMMA or THEOREM must be named and fully proved.

  • Never use PROOF OMITTED or bare OMITTED, and never create a circular helper.

  • Bound the SMT/Z3 backend with a deterministic budget SMTT("rN"), capped at SMTT("r30"). Do not use the wall-clock forms SMT or SMTT(n).

  • New operator and lemma names must be fresh. Do not shadow names from the task or its context.

  • Do not browse or fetch external material. Work only from the files in this workspace and your knowledge of TLA+/TLAPS.

Agent Skills

Runs with the harness also receive the two agent skills described in § 3.1, reproduced below.

Skill: tlaps-proof-hints

---
name: tlaps-proof-hints
description: Resolve TLAPS proof failures involving theorem instances from modules with

Skill: tlaps-proof-hints

assumptions. Use when a citation such as BY I!Thm does not close a goal because prefixed and unprefixed imported operators are treated as different symbols.


Use a theorem from an instantiated module

Symptom

A citation such as BY I!Thm, NA does not close the goal even though I!Thm appears to prove it and NA appears to supply the corresponding local assumption.

Cause

When a module with assumptions is instantiated as I == INSTANCE M, the instantiated assumptions become hypotheses of its theorem instances. If an assumption mentions an operator imported through EXTENDS, the instance re-exports that operator under the I! prefix. TLAPS treats the prefixed and unprefixed names as distinct internal symbols, so backends do not automatically relate I!Pos(N) to Pos(N).

Fix

Prove a bridge theorem equating the prefixed operator with its local counterpart and cite it alongside the instantiated theorem:

---- MODULE Lib ----
EXTENDS Integers
Pos(n) == n > 0
====

---- MODULE A ----
EXTENDS Lib
CONSTANT N
ASSUME NA == Pos(N)

THEOREM Thm == N > 0
  BY NA DEF Pos
====

---- MODULE B ----
EXTENDS Lib
CONSTANT N
ASSUME NA == Pos(N)

I == INSTANCE A

THEOREM Bridge == \A n : I!Pos(n) = Pos(n)
  BY DEF I!Pos, Pos

Skill: tlaps-proof-hints

THEOREM Test == N > 0
\* BY I!Thm, NA             \* FAILS
  BY I!Thm, NA, Bridge      \* WORKS
====

Source: tlaplus/tlapm#279

Skill: tla-inductive-invariant-validation

---
name: tla-inductive-invariant-validation
description: Validate candidate inductive invariants for TLA+ safety proofs with Apalache
or TLC. Use when designing or debugging an invariant, especially when TLAPS cannot
discharge initiation, consecution, or safety-implication obligations.
---

Validate a TLA+ inductive invariant

Use a model checker to falsify a candidate invariant before investing in its TLAPS proof. Treat a successful finite check as evidence only: prove the invariant in TLAPS, and finish with the benchmark's authoritative check_proof_bin command.

Run the three Apalache checks

Shape the candidate as IndInv == TypeOK /\ H, where TypeOK contains one finite-domain membership clause for every variable and H contains the additional facts needed for induction. Given a target module Target, a typed wrapper APTarget.tla, and a safety predicate Safety, run:

apalache-mc check --config=APTarget.cfg --init=Init --inv=IndInv --length=0 APTarget.tla
apalache-mc check --config=APTarget.cfg --init=IndInv --inv=IndInv --length=1 APTarget.tla
apalache-mc check --config=APTarget.cfg --init=IndInv --inv=Safety --length=0 APTarget.tla

Interpret these checks as:

  1. Init => IndInv: legitimate initial states satisfy the candidate.

  2. IndInv /\ Next => IndInv': one step preserves the candidate.

  3. IndInv => Safety: the candidate is strong enough to prove the goal.

The checks starting from --init=IndInv require the candidate to assign every variable. A bare safety predicate can instead produce an assignment error such as x' is used before it is assigned. Write the missing TypeOK if the stripped target has none. Bound Nat-typed values to small finite sets, for example num \in [P -> 0..4], and widen a bound before trusting a counterexample that may depend on it.

Skill: tla-inductive-invariant-validation

When a check fails, read the counterexample. Apalache writes violation1.tla in a timestamped directory under _apalache-out/<module>.tla/ unless redirected with --out-dir or --run-dir; the Check the trace in: ... log line gives the exact path.

  • A failure of the first check means the candidate excludes a legitimate initial state.

  • A failure of the second check gives a state satisfying IndInv and a successor violating it. The trailing InvariantViolation formula identifies the broken conjunct and usually exposes the fact missing from H.

  • A failure of the third check means the candidate does not imply the safety goal.

Strengthen or correct the candidate from the trace, then rerun all three checks.

Keep tool-specific annotations out of Target.tla. Re-declare its constants and variables with Apalache types in a separate wrapper, then instantiate the target:

````text

---- MODULE APTarget ----
EXTENDS Naturals
CONSTANT
\* @type: Int;
N
VARIABLE
\* @type: Set(Int);
active
INSTANCE Target
TypeOK == active \in SUBSET (0..N)
H == TRUE
IndInv == TypeOK /\ H
====

````

Match every re-declared name exactly so implicit INSTANCE substitution binds it. Put each \* @type: annotation between the CONSTANT or VARIABLE keyword and the name it annotates, including every name originally declared in a multi-name block. A comment above the keyword is not accepted and leads to Expected a type annotation for VARIABLE <name>.

Define IndInv in the wrapper. Fix finite constants in APTarget.cfg, for example:

````text

INIT Init
NEXT Next

CONSTANT N = 5

````

Skill: tla-inductive-invariant-validation

Alternatively, use --cinit. For an uninterpreted constant, define a finite value operator such as JugVal in the wrapper and substitute it with Jug <- JugVal in the configuration. If a polymorphic helper such as Sum, Range, or ToSet defeats type checking, shadow it in the wrapper with a monomorphic version.

Only if the wrapper cannot be made to typecheck, annotate a private scratch copy:

mkdir -p scratch
cp Target.tla scratch/Candidate.tla

Never make the submitted solution extend or instantiate the wrapper or scratch module. Do not alter the target or any dependency as part of model-checking exploration.

Fall back to TLC

Use TLC when Apalache cannot type the target through a wrapper. Create a separate MCTarget.tla that extends Target and defines TypeOK, H, and IndInv, with MCTarget.cfg beside it. TLC is not on PATH; run:

java -cp /opt/sany/lib/tla2tools.jar tlc2.TLC -deadlock -config MCTarget.cfg MCTarget.tla

Check the inductive step by making the candidate its own initial predicate:

INIT IndInv
NEXT Next
INVARIANT IndInv

This checks IndInv /\ Next => IndInv' because IndInv is an ordinary invariant of the specification started in IndInv. Check Init => IndInv separately on the real specification with SPECIFICATION Spec and INVARIANT IndInv. Include Safety as a conjunct of IndInv to check that the candidate implies it.

Use the same enumerable TypeOK /\ H shape as for Apalache. TLC first builds the states satisfying TypeOK and then filters them with H, so start with the smallest useful model. To reduce enumeration:

  • Move a conjunct of H immediately after the TypeOK clauses that bind the variables it mentions, allowing TLC to prune earlier.

  • Sample large domains with RandomSubset(k, S) from the Randomization module. Rewrite v \subseteq W as v \in SUBSET W and sample it with RandomSetOfSubsets(k, p, W).

Aim for a few dozen initial states. A TLC violation supplies the same useful two-state signal as Apalache. Once random sampling is involved, a run with no violation proves Skill: tla-inductive-invariant-validation

nothing; rerun it about a dozen times and abandon a run whose search depth grows beyond roughly a dozen steps.

See Leslie Lamport's Using TLC to Check Inductive Invariance for the TLC technique.

Never cite an Apalache or TLC verdict as justification for a TLAPS proof step.

References

  1. [2]Beers, R. Pre-RTL Formal Verification: An Intel Experience. In Proceedings of the 45th Annual Design Automation Conference (DAC), June 2008.DOI
  2. [4]Bisharat, A., Spencer, E., Ortiz, B., Bhadauria, K., Nazari, M., Santos, B., Ramos, A., Wang, T., Thiruvathukal, G. K., Läufer, K., and Abuhamad, M. TLA+-Bench: An Execution-Grounded Benchmark and Dataset for Natural-Language-to-TLA+ Specification Generation. arXiv:2607.23425, July 2026b.arxiv.org/abs/2607.23425
  3. [5]Cai, Z. C., Date, N., Gu, J. T., Rivera, C., Chajed, T., Padon, O., Xu, T., and Sun, X. Welder: Compositional Liveness Verification of Cluster Control Planes. In Proceedings of the ACM SIGOPS 32nd Symposium on Operating Systems Principles (SOSP), September 2026.DOI
  4. [6]Cao, J., Lu, Y., Li, M., Ma, H., Li, H., He, M., Wen, C., Sun, L., Zhang, H., Qin, S., Cheung, S.-C., and Tian, C. From Informal to Formal – Incorporating and Evaluating LLMs on Natural Language Requirements to Verifiable Formal Proofs. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (ACL), July 2025.
  5. [7]Chaudhuri, K., Cousineau, D., Doligez, D., Lamport, L., Libal, T., Merz, S., Tristan, J.-B., and Vanzetto, H. TLAPS Library. https://github.com/tlaplus/tlapm/tree/main/library, 2026.
  6. [8]Chen, Z., Cao, J., Wu, J., Xu, C., and Cheung, S.-C. Can Large Language Models Model Programs Formally? arXiv:2604.01851, April 2026.arxiv.org/abs/2604.01851
  7. [9]Cheng, Q., Pial, S. M. R., Tang, R., Su, Y., Ma, E., Hackett, F., Beschastnikh, I., Huang, Y., and Xu, T. Specula: Scaling Formal Specifications for Autonomous Model Checking of System Code. arXiv:2607.25333, July 2026a.arxiv.org/abs/2607.25333
  8. [10]Cheng, Q., Tang, R., Ma, E., Hackett, F., He, P., Su, Y., Beschastnikh, I., Huang, Y., Ma, X., and Xu, T. SysMoBench: Evaluating AI on Formally Modeling Complex Real-World Systems. In Proceedings of the 14th International Conference on Learning Representations (ICLR), April 2026b.arxiv.org/abs/2509.23130
  9. [11]Clarke, E. M., Emerson, E. A., and Sistla, A. P. Automatic Verification of Finite-State Concurrent Systems Using Temporal Logic Specifications. ACM Transactions on Programming Languages and Systems (TOPLAS), April 1986.DOI
  10. [12]Cousineau, D., Doligez, D., Lamport, L., Merz, S., Ricketts, D., and Vanzetto, H. TLA+ Proofs. In Proceedings of the 18th International Symposium on Formal Methods (FM), August 2012.
  11. [13]de Moura, L. and Bjørner, N. Z3: An Efficient SMT Solver. In Proceedings of the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), March 2008.
  12. [14]de Moura, L. and Ullrich, S. The Lean 4 Theorem Prover and Programming Language. In Proceedings of the 28th International Conference on Automated Deduction (CADE), July 2021.
  13. [15]Hackett, F., Rowe, J., and Kuppe, M. A. Understanding Inconsistency in Azure Cosmos DB with TLA+. In Proceedings of the 45th International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP), May 2023.arxiv.org/abs/2210.13661
  14. [16]Hawblitzel, C., Howell, J., Kapritsos, M., Lorch, J. R., Parno, B., Roberts, M. L., Setty, S., and Zill, B. IronFleet: Proving Practical Distributed Systems Correct. In Proceedings of the 25th ACM Symposium on Operating Systems Principles (SOSP), October 2015.DOI
  15. [17]Howard, H., Kuppe, M. A., Ashton, E., Chamayou, A., and Crooks, N. Smart Casual Verification of the Confidential Consortium Framework. In Proceedings of the 22nd USENIX Symposium on Networked Systems Design and Implementation (NSDI), April 2025.arxiv.org/abs/2406.17455
  16. [18]Konnov, I., Kukovec, J., and Tran, T.-H. TLA+ Model Checking Made Symbolic. Proceedings of the ACM on Programming Languages (PACMPL), October 2019.DOI
  17. [19]Kuppe, M. A., Merz, S., Fedoreipp, P. R., Lamport, L., Schultz, W., Fernandes, A., Ryndzionek, M., Konnov, I., Halterman, J., Wayne, H., and Jobsv. TLA+ CommunityModules. https://github.com/tlaplus/CommunityModules, 2026.
  18. [20]Lamport, L. The Temporal Logic of Actions. ACM Transactions on Programming Languages and Systems (TOPLAS), May 1994.DOI
  19. [21]Lamport, L. Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers. Addison-Wesley, July 2002.
  20. [22]Lamport, L., Sharma, M., Tuttle, M., and Yu, Y. The Wild-fire Challenge Problem. https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/The-Wildfire-Challenge-Problem.pdf, January 2001.
  21. [23]Lattuada, A., Hance, T., Bosamiya, J., Brun, M., Cho, C., LeBlanc, H., Srinivasan, P., Ackermann, R., Chajed, T., Hawblitzel, C., Howell, J., Lorch, J. R., Padon, O., and Parno, B. Verus: A Practical Foundation for Systems Verification. In Proceedings of the 30th ACM Symposium on Operating Systems Principles (SOSP), November 2024.DOI
  22. [24]Lin, X., Cao, Q., Huang, Y., Wang, H., Lu, J., Liu, Z., Song, L., and Liang, X. FVEL: Interactive Formal Verification Environment with Large Language Models via Theorem Proving. In Advances in Neural Information Processing Systems (NeurIPS), December 2024.
  23. [25]Loughridge, C., Sun, Q., Ahrenbach, S., Cassano, F., Sun, C., Sheng, Y., Mudide, A., Misu, M. R. H., Amin, N., and Tegmark, M. DafnyBench: A Benchmark for Formal Software Verification. arXiv:2406.08467, June 2024.
  24. [28]Mishra, S., Goncalves, J., Tankuranand, C., Crooks, N., Giridharan, N., Howard, H., and Jensen, C. Pirateship: Append-Only Ledgers for (Mostly) Trusted Execution Environments. In Proceedings of the ACM SIGOPS 32nd Symposium on Operating Systems Principles (SOSP), September 2026.
  25. [29]Mugnier, E., Gonzalez, E. A., Polikarpova, N., Jhala, R., and Zhou, Y. Laurent: Unblocking Automated Verification with Large Language Models. Proceedings of the ACM on Programming Languages (PACMPL), April 2025.
  26. [30]Newcombe, C., Rath, T., Zhang, F., Munteanu, B., Brooker, M., and Deardeuff, M. How Amazon Web Services Uses Formal Methods. Communications of the ACM (CACM), March 2015.
  27. [31]Ongaro, D. and Ousterhout, J. In Search of an Understandable Consensus Algorithm. In Proceedings of the 2014 USENIX Annual Technical Conference (ATC), June 2014.
  28. [32]Ouyang, L., Sun, X., Tang, R., Huang, Y., Jivrajani, M., Ma, X., and Xu, T. Multi-Grained Specifications for Distributed System Model Checking and Verification. In Proceedings of the 20th European Conference on Computer Systems (EuroSys), March 2025.
  29. [33]Paulson, L. C. Isabelle: A Generic Theorem Prover. Springer, July 1994.
  30. [34]Pîrlea, G., Gladshtein, V., Kinsbruner, E., Zhao, Q., and Sergey, I. Veil: A Framework for Automated Interactive Verification of Transition Systems. In Proceedings of the 37th International Conference on Computer Aided Verification (CAV), July 2025.
  31. [35]Pnueli, A. The Temporal Logic of Programs. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS), October 1977.
  32. [36]Schultz, W. and Demirbas, M. Design and Modular Verification of Distributed Transactions in MongoDB. Proceedings of the VLDB Endowment (PVLDB), August 2025.
  33. [37]Song, Y. J. and Renesse, R. Bosco: One-Step Byzantine Asynchronous Consensus. In Proceedings of the 22nd International Symposium on Distributed Computing (DISC), September 2008.DOI
  34. [38]Strelbytska, K., Szilágyi, B., Mészáros, A., and Huszár, F. TLA-Verus: Generating and Solving Temporal Proof Obligations with LLM Agents. arXiv:2610.14923, October 2026.
  35. [39]Suda, M. and Weidenbach, C. A PLTL-Prover Based on Labelled Superposition with Partial Model Guidance. In Proceedings of the 6th International Joint Conference on Automated Reasoning (IJCAR), June 2012.
  36. [40]Sun, X., Ma, W., Gu, J. T., Ma, Z., Chajed, T., Howell, J., Lattuada, A., Padon, O., Suresh, L., Szekeres, A., and Xu, T. Anvil: Verifying Liveness of Cluster Management Controllers. In Proceedings of the 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI), July 2024.
  37. [41]Tang, R., Wang, M., Sun, X., Huang, L., Huang, Y., and Ma, X. Converos: Practical Model Checking for Verifying Rust OS Kernel Concurrency. In Proceedings of the 2025 USENIX Annual Technical Conference (ATC), July 2025.
  38. [42]Thompson, K., Saavedra, N., Carrott, P., Fisher, K., Sanchez-Stern, A., Brun, Y., Ferreira, J. F., Lerner, S., and First, E. Rango: Adaptive Retrieval-Augmented Proving for Automated Software Verification. arXiv:2412.14063, December 2024.
  39. [43]TLA+ Foundation. Industrial Use of TLA+. https://foundation.tlapl.us/industry/index.html, 2026.
  40. [45]Xin, Y., Chen, Q., Durrett, G., and Dillig, I. VeriSoftBench: Repository-Scale Model Verification Benchmarks for Lean. arXiv:2602.18307, February 2026.arxiv.org/abs/2602.18307
  41. [47]Yang, C., Li, X., Misu, M. R. H., Yao, J., Cui, W., Gong, Y., Hawblitzel, C., Lahiri, S., Lorch, J. R., Lu, S., Yang, F., Zhou, Z., and Lu, S. AutoVerus: Automated Proof Generation for Rust Code. Proceedings of the ACM on Programming Languages (PACMPL), October 2025a.DOI
  42. [48]Yang, C., Neamtu, N., Hawblitzel, C., Lorch, J. R., and Lu, S. VeruSAGE: A Study of Agent-Based Verification for Rust Systems. arXiv:2512.18436, December 2025b.
  43. [49]Yao, J., Tao, R., Gu, R., Nieh, J., Jana, S., and Ryan, G. DistAI: Data-Driven Automated Invariant Learning for Distributed Protocols. In Proceedings of the 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI), July 2021.
  44. [53]Zhang, L., Lu, S., and Duan, N. Selene: Pioneering Automated Proof in Software Verification. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (ACL), August 2024.
  45. [54]Zhong, S. C. and Si, X. Towards Repository-Level Program Verification with Large Language Models. In Proceedings of the 1st ACM SIGPLAN International Workshop on Language Models and Programming Languages (LMPL), October 2025.DOI
  46. [55]Zhou, Y. and Tripakis, S. Towards Language Model Guided TLA+ Proof Automation. In Proceedings of the 27th International Symposium on Formal Methods (FM), May 2026.arxiv.org/abs/2512.09758

Paper details

vlnc:W_qym4amyv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6 Astra, GPT-6.1 Sol

View statement
Looking for related papers…
Contents