Reasonable AI Builds Pipeline to Convert 16,000+ TLA+ Specs into Machine-Checked Verus Proofs

Reasonable AI has developed an agentic pipeline that translates TLA+ specifications into machine-checked proofs in Verus, aiming to bridge the gap between formal modeling and software verification. The work responds to growing interest in using formal methods for AI agents, sparked by recent viral examples of using LLMs like Opus 5.5 to model agent behaviors.

From Specifications to Proofs

TLA+ is a temporal logic language used to describe system behaviors and properties, widely adopted by companies like AWS, MongoDB, and Datadog. However, TLA+ model checking (via TLC) is limited to finite instances and does not verify the actual implementation code. To address this, Reasonable AI leverages Verus, a Rust-based verification tool that allows specifications, proofs, and implementation to coexist, enabling refinement proofs that ensure the code matches the model.

Agentic Verification Pipeline

The team built a system to automate the translation and proof generation process:

• Transpilation: An algorithmic transpiler converts TLA+ specs to Verus, compared against an agentic alternative where one LLM translates and another reviews.
• Prover-Reviewer Loop: One agent generates the proof, while a second reviews it. A separate "gatekeeper" agent ensures the specification hasn't been altered and checks for cheating shortcuts like assume(false).
• Dataset Creation: Starting from 16,459 real-world TLA+ specification/property pairs, the pipeline produced more than 3,000 machine-checked safety and liveness proofs.
• Evaluation: A 40-task evaluation set was constructed to test current closed and open-weight frontier models on their ability to complete these temporal proofs.

Future Directions

The project highlights the potential for AI to handle the repetitive aspects of formal verification, such as tracking invariants and splitting over actions. Future work aims to expand this to refinement proofs (proving Rust code refines the TLA+ model), program synthesis (generating code and proofs together), and protocol search where the verifier acts as an objective function for generating correct-by-design protocols.