AI安全验证存在根本性局限，无法完全证明高复杂度行为的安全性。
Incompleteness of AI Safety Verification via Kolmogorov Complexity
- 用柯尔莫哥洛夫复杂度分析系统行为编码，形式化安全验证问题。
- 证明任何有限验证器都无法认证超过阈值复杂度的合规实例。
- 揭示安全验证的理论极限，适合研究可信AI与形式化验证者参考。
确保人工智能系统满足形式化安全与策略约束是关键挑战。尽管通常将验证局限归因于组合复杂性和模型表达能力，我们指出其根源在于内在的信息论限制。我们将策略合规性形式化为对编码系统行为的验证问题，并使用柯尔莫哥洛夫复杂度进行分析。证明了一个不完备性结果：对于任意固定的、可计算枚举的可靠验证器，总存在一个阈值，一旦行为复杂度超过该阈值，真实合规实例便无法被认证。因此，没有任何有限形式验证器能够认证所有任意高复杂度的合规实例。这一发现揭示了独立于计算资源的AI安全验证根本局限，并推动了提供实例级正确性保证的带证明方法的发展。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。