# Incompleteness of AI Safety Verification via Kolmogorov Complexity

arXiv: https://arxiv.org/abs/2604.04876 · HTML: https://mlsanity.com/paper/2604.04876/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 15 references that are in the map.
- First posted on arXiv 6 Apr 2026.

## Builds on (most cited first, 6 of 6)

- [Concrete Problems in AI Safety](https://mlsanity.com/paper/1606.06565/) (2016)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Safety Verification of Deep Neural Networks](https://mlsanity.com/paper/1610.06940/) (2016)
- [Robust AI Security and Alignment: A Sisyphean Endeavor?](https://mlsanity.com/paper/2512.10100/) (2025)
- [Hermes Seal: Zero-Knowledge Assurance for Autonomous Vehicle Communications](https://mlsanity.com/paper/2603.26343/) (2026)

## Built on by (most cited first, 2 of 2)

- [Bounded Behavioral Indistinguishability for Black-Box LLM Distillation](https://mlsanity.com/paper/2605.30448/) (2026)
- [If Agents Were Angels, No Governance Would Be Necessary: Out-of-Band Policy Enforcement at a Trusted Tool Boundary](https://mlsanity.com/paper/2608.27646/) (2026)

## Abstract (arXiv)

Ensuring that artificial intelligence (AI) systems satisfy formal safety and policy constraints is a central challenge in safety-critical domains. While limitations of verification are often attributed to combinatorial complexity and model expressiveness, we show that they arise from intrinsic information-theoretic limits. We formalize policy compliance as a verification problem over encoded system behaviors and analyze it using Kolmogorov complexity. We prove an incompleteness result: for any fixed sound computably enumerable verifier, there exists a threshold beyond which true policy-compliant instances cannot be certified once their complexity exceeds that threshold. Consequently, no finite formal verifier can certify all policy-compliant instances of arbitrarily high complexity. This reveals a fundamental limitation of AI safety verification independent of computational resources, and motivates proof-carrying approaches that provide instance-level correctness guarantees.