The limits of what TLA+ can verify

I'm seeing a lot of euphoria about how Opus 5.5 is good at TLA+, and this means that all software will soon be formally verified. As a person who loves TLA+ so much he wrote a book on it, I want to throw a particular cold shower on people's enthusiasm by talking about the limits of what you can actually verified with it.

The high level simplification is that TLA+ sees a system as a set of "behaviors", or possible sequences of states. For example, the pseudocode "pick a random number from 1-3 and decrement it to 1" has three behaviors: `{3 -> 2 -> 1, 2 -> 1, 1}`. From here, there are two basic kinds of TLA+ properties:

• `[]P` means that `P` is true in all states of every behavior.
• `<>P` means that `P` is true in at least one state of every behavior.

`[]P` is immediately useful as an invariant, or something that always be true of your system. This is things like "your data is never corrupt" or "there's always at least one server online." `<>P` is a little more abstract, but for technical math reasons I won't get into here, can be stacked with `[]` to create really complex and useful properties. `<>[]P` represents things like "the algorithm eventually converges on the right answer", `[]<>P` things like "if two data stores desync, they will eventually resync", and `[](P => <>Q)` things like "If a message is put on the queue, it's eventually processed by a worker".

Really cool stuff!

These primitives were chosen to make a wide array of properties useful. And if we're clever, we can do all sorts of more complex properties, like bounded time constraints and history properties. But we're always constrained to 1) define a logical formula 2) over individual behaviors, and 3) check that all behaviors satisfy that formula.

So some things that we cannot express in TLA+:

• Possibility and reachability properties: that it's always possible to make P true, even if you don't actually decide to. Things like "I can always shut down the computer" or "A user can always change their password". These can't be expressed with `<>P` because that's "for all behaviors, P happens at least once", we actually want "for all behavior prefixes, there is at least one behavior where P happens at least once".
• Hyperproperties: properties that are defined over two or more traces. These are things like "painting a car red doesn't make it faster" or "users cannot infer secret data by observing public data". We can't do these because TLA+ only looks at one behavior at a time.
• Statistical properties: 95% latency is 1ms. Impossible because most of these are hyperproperties.
• Properties about if a system is robust against code changes. Impossible because, uh, you have new behaviors now.

Some of these are solvable in different logical formalisms. CTL can do reachability, PRISM can do statistical properties, etc. Those have their own tradeoffs and limitations, though, and no system can do everything. Others are solvable with a lot of cleverness tailored to the specific spec, like lifting a model into a hypermodel. But these are insanely inefficient and make your "clever spec" diverge significantly from the real world system, so introduce a lot more opportunity for things to go wrong.

The core problem, though, is (1): properties are logical formula. If we don't know how to express a system property as a logical formula, we can't verify it. 99% of the properties we care about fall under this. The information on the site is easy for a user to find. Our LLMs behave as we expect them to. Our application can't be used to break the law. TLA+ (and Quint and Lean and Rocq) are near-useless here, no matter how clever you are.

Don't get me wrong: `[]P` and `<>P` represent a huge range of useful properties and TLA+ is incredible at finding awful concurrency bugs. But there's a lot it fundamentally can't do and we shouldn't believe that it will solve all our worries about software bugs. And the same goes for all other formal verification languages, too.