Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper formalizes policy compliance in AI systems as a verification problem using Kolmogorov complexity to analyze information-theoretic limits. It proves that any sound, computably enumerable verifier has an inherent incompleteness: it cannot certify all true policy-compliant instances beyond a certain complexity threshold. This reveals a fundamental limitation of AI safety verification that is independent of computational resources.
AI safety verification hits an unfixable information-theoretic wall: no matter how much compute you throw at it, there will always be complex, safe policies that a verifier can't certify.
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.