The Verification Trilemma

In the AI Story

The result is a distant descendant of the classical impossibility results in computability theory — Turing's halting problem, Rice's theorem — and is in the same family as the no-free-lunch theorems in learning theory. Its novelty is its direct applicability to the verification of AI systems and, by extension, to the code those systems produce. The trilemma is not a claim about what is hard; it is a claim about what is logically impossible within any verification framework satisfying standard soundness conditions.

The practical consequence is that the Dijkstrian standard of provable correctness cannot be fully achieved for the systems that matter most. A builder who verifies her software faces a choice: she can achieve soundness and generality at the cost of tractability (verification takes too long to be practical), soundness and tractability at the cost of generality (verification holds for a restricted class of inputs), or generality and tractability at the cost of soundness (verification is fast and broad but can certify incorrect systems as correct). No combination gives her what Dijkstra demanded.

Dijkstra would have found the result simultaneously vindicating and alarming. Vindicating because it confirms with mathematical rigor that the verification problem is real — there is no free lunch, no path by which generation and verification can both be complete and efficient. Alarming because it means the gap between tested code and verified code cannot be closed, even in principle, for the most complex systems. His framework always insisted that the gap was real; the trilemma proves that the gap has a floor.

The response within the AI safety community has been to pursue managed verification: accepting the trilemma's constraints and making explicit trade-offs. A verification system might achieve soundness and tractability on a restricted class of properties, documenting what it covers and what it does not, and directing human review toward the uncovered space. This is not full Dijkstrian verification, but it is substantially more than testing alone, and it preserves the core principle that the gap between tested and verified must be acknowledged rather than elided.

Origin

The specific 2026 paper "On the Formal Limits of Alignment Verification" is the canonical reference, though the underlying impossibility was anticipated in earlier work on the fundamental limits of neural network verification and in the classical computability-theory results on which it builds. The paper's contribution is the explicit trilemma formulation and the proof that the three properties cannot be jointly satisfied.

Related impossibility results include Arora et al.'s hardness results for neural network verification (2018), the PCP theorem's implications for verification tractability, and the long-standing decidability limits for program analysis.

Key Ideas

Three properties, two at a time. Soundness, generality, and tractability are pairwise achievable but not jointly. Every verification system makes a specific trade-off among them.

Impossibility is formal. The trilemma is a mathematical proof, not a practical observation. Better tools cannot overcome it; they can only pick different trade-offs.

Dijkstra's standard is capped. Full Dijkstrian verification — sound, general, and tractable — is unavailable for sufficiently complex systems. This was suspected; it is now proved.

Managed verification is the response. Accept the constraints, make explicit trade-offs, document what is covered and what is not. This is less than Dijkstra demanded but substantially more than testing alone.

The gap has a floor. The distance between tested code and verified code cannot be closed even in principle for the most complex systems. The gap must be managed, not eliminated.

Debates & Critiques

Critics of the trilemma argue that its applicability to real-world software is narrow: most practical verification targets restricted property classes where tractable sound verification is achievable, and the trilemma's force applies only at the frontier of general-purpose AI reasoning. Proponents counter that the frontier is precisely where the highest-stakes deployments are occurring, and that the trilemma's implications for those deployments are severe. The argument is technical but consequential: it determines how much reliance on AI verification is epistemically warranted for safety-critical applications.