What TLA+ can and can't check
Hillel Wayne examines the theoretical boundaries of TLA+, detailing what properties—such as reachability and hyperproperties—the formal specification language cannot natively express.
read it Essential reading for anyone considering formal verification, mapping out the precise theoretical and practical limits of TLA+.
summary
Recent hype suggests formal verification will fix AI-generated code, but TLA+ has fundamental expressive limits. While it handles safety invariants and liveness properties well via temporal logic, it cannot natively express multi-step properties, reachability, or hyperproperties comparing multiple execution paths. Engineers can use messy hacks like auxiliary variables or self-composition, but these compromise clarity and scale poorly. Ultimately, TLA+ excels at low-hanging fruit but cannot model entire classes of system properties.
key points
- TLA+ relies on universal quantification over all behaviors, making it unable to natively express existential reachability properties.
- Hyperproperties requiring comparisons across multiple behaviors—such as security bounds or statistical guarantees—cannot be checked without complex self-composition hacks.
- While hacks like auxiliary variables simulate multi-step constraints, they degrade model clarity and cause state-space explosion.
who should read it
Software engineers and architects evaluating formal methods and TLA+ for system design.
discussion positive
consensus
Commenters appreciate the realistic take on formal methods, noting additional blind spots like weak-memory concurrency models and difficult syntax.
pushback
One commenter points out a technical counterargument regarding reachability, noting that proving an invariant false via a counterexample indirectly demonstrates existential reachability.
I love this. This is great to read if you are trying to use TLA+ for something.
In a different vein, another thing TLA+ isn't great at is modeling atomics and in particular weak-memory semantics or anything that's not sequentially consistent. If you translate your algorithm to pcal, it will run as if it was sequentially consistent. If you need to model non-sequential-consistency, then that needs to be spelled out with explicit logic to TLA+, which is probably too complicated and error-prone to do by hand. The C/C++/Rust memory models permit a lot of wacky stuff. I imagine you need to add …
It highlights an important blind spot not covered in the post: TLA+'s assumption of sequential consistency and difficulty handling weak-memory models.
Generated by an LLM from the article and thread. Check the sources before relying on it.