AI对齐无法在无限输入上完全验证,存在根本性限制。
No Certificate for Alignment: Two Independent Impossibilities and the Pareto Frontier of Achievable Safety Guarantees
- 从语义与统计两方面证明:对齐验证在无限输入下不可能同时保证准确、完整和高效。
- 任何验证方法都无法在多项式时间内覆盖所有可能输入,存在不可逾越的覆盖率缺口。
- 研究为安全验证设定了可实现的边界,适合关注AI安全理论的学者参考。
我们认为,在计算复杂性和学习理论的标准假设下,对开放或无界输入域的AI对齐进行形式化认证是不可能的,并刻画了仍可实现的范围。两个结构上独立的不可能性定理支持这一观点:语义障碍(定理1)表明,对前馈网络而言,判断系统是否满足任意非平凡对齐属性在全输入域上是NP难的;对图灵完备架构则是不可判定的——这源于神经网络验证的复杂性及Rice定理。统计障碍(定理2)指出,任何既可靠又可高效运行的验证程序,都无法在全输入域上满足完备性——这是由有限观测无法证明无限域属性所导致。这两个定理共同构成三难困境:不存在能同时满足可靠性(不误认证非对齐系统)、完备性(不拒绝对齐系统)和可计算性(多项式时间)的验证过程。任意两者可共存,三者不可兼得。本文将两类障碍整合为统一框架,证明其独立性,并通过构造性覆盖率下界定量刻画了可达成的帕累托前沿。
原文摘要 · Abstract (English)
We argue that formal certification of AI alignment over open-ended or unbounded input domains is impossible under standard assumptions in computational complexity and learning theory, and characterise what remains achievable. Two structurally independent impossibility theorems support this position. The semantic barrier (Theorem 1): deciding whether a system satisfies any non-trivial alignment property over the full input domain is NP-hard for feedforward networks and undecidable for Turing-complete architectures -- a direct consequence of neural-network verification complexity and Rice's Theorem. The statistical barrier (Theorem 2): any verification procedure that is both sound and tractable cannot satisfy Completeness over the full input domain -- a direct consequence of the impossibility of certifying infinite-domain properties from finite observations. These two theorems jointly entail a trilemma: no procedure can simultaneously satisfy soundness (no misaligned system is certified), completeness (no aligned system is rejected), and tractability (polynomial runtime). Each pair is simultaneously achievable; all three are not. We combine these results as a joint framework of two structurally independent barriers, prove their independence, and characterise the achievable Pareto frontier quantitatively via a constructive coverage-gap lower bound.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。