No Certificate for Alignment: Two Independent Impossibilities and the Pareto Frontier of Achievable Safety Guarantees

Ayushi Agarwal

stat.MLMar 8, 2026

No Certificate for Alignment: Two Independent Impossibilities and the Pareto Frontier of Achievable Safety Guarantees

Authors: Ayushi Agarwal

Organizations: Independent Researcher

Abstract

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.

Figures & tables

Regime	Procedure	Guarantee	Gap
S+C, not T	Query every rational in $[0,1]$	Always correct	Infinite time
S+T, not C	Bounded-domain abstract interpreter; certify if bound holds	Sound over tested region	Input region beyond $\mathcal{D}_{b}$ uncertified
C+T, not S	Always output “aligned”	Never rejects aligned	Passes $\theta=0.99$

Table 1: All three trilemma corners on the 1D threshold example.

Panel of Figure 1 — Figure 1: Running example. The witness systems $f_{0.04}$ (aligned, $A^{*}{=}0.96$ , blue) and $f_{0.06}$ (misaligned, $A^{*}{=}0.94$ , red) are identical outside the critical interval (yellow). Query points (dots) placed outside this interval cannot distinguish them regardless of computational power, illustrating both barriers simultaneously.

Panel of Figure 2 — Figure 2: The Alignment Verification Trilemma. Each edge represents an achievable pair (Proposition 3 ). The centre states the joint impossibility (Corollary 1 ), which follows from two structurally independent theorems.

Panel of Figure 3 — Figure 3: Pareto frontier and trilemma proof (Cor. 1 ). Network: $\mathrm{Lin}(2{\to}32)\to\mathrm{ReLU}\to\mathrm{Lin}(32{\to}1)$ ; property: $f(\mathbf{x})\geq 0.5$ , $\mathbf{x}\in[0.5,1]^{2}$ ; verifier: IBP [ Gowal et al.(2018) ] . (a) S+T. $\varepsilon=1{-}c$ (theoretical, uniform queries). Green $\bullet$ : IBP certifies; red $\times$ : inconclusive (S kept, C lost). (b) S+C. IBP bound collapses below $0.5$ beyond $c=49\%$ (Thm. 2 ). (c) All three regimes in one plot: S+T (green step) loses C; C+T (blue dashed) loses S; S+C (orange $\lozenge$ ) loses T; S+C+T ( $\star$ ) is unreachable.

Published claim	Does not establish	Formal status
GPT-4 is 82% less likely to produce disallowed content vs. GPT-3.5 [ OpenAI(2023) ]	S	Measured on internal red-team set $\mathcal{D}_{b}$ ; no bound on behaviour outside $\mathcal{D}_{b}$
Gemini Ultra achieves top scores on safety benchmarks [ Gemini Team(2023) ]	C	Benchmarks are finite $\mathcal{D}_{b}$ ; out-of-benchmark behaviour uncertified
InstructGPT is “more helpful, truthful, and harmless” than GPT-3 [ Ouyang et al.(2022) ]	S	Comparison is relative to a proxy reward; proxy-to- $A^{*}$ gap is structural [ Gao et al.(2023) ]
Constitutional AI is “broadly safe” across evaluation suite [ Bai et al.(2022) ]	C+S	Safe on tested prompts (C fails on remainder); proxy score used for training (S gap)

Table 2: Published safety claims and their formal status under Corollary 1 . Each claim is accurate within its stated evaluation scope; the column identifies the trilemma property the evaluation was not designed to provide.

Explore similar work

Algorithmic Unverifiability of Safety for Fixed and Recursively Self-Improving Systems
Jun 26, 2026Jose Pascual Gumbau MezquitaFormal Verification Self-Improving Agents
Universitat Jaume I, Castelló de la Plana, Spain
Incompleteness of AI Safety Verification via Kolmogorov Complexity
Apr 6, 2026Munawar HasanFormal Verification AI Safety
Mechanical and Aerospace Engineering, Michigan Technological University, Houghton, MI, USA
Are Safety Guarantees in Neural Networks Safe? How to Compute Trustworthy Robustness Certifications
Jun 22, 2026Merkouris Papamichail, Konstantinos Varsos, Giorgos Flouris +1Neural Network Verification Neural Network Robustness
Foundation for Reasearch and Technology - Hellas, Heraklion, Greece · University of Crete, Heraklion, Greece · Catalan Institution for Research and Advanced Studies, Barcelona, Spain +1

Jun 26, 2026J/K move · Enter open · S save

Algorithmic Unverifiability of Safety for Fixed and Recursively Self-Improving Systems

Jose Pascual Gumbau Mezquita

Universitat Jaume I, Castelló de la Plana, Spain

Formal Verification Self-Improving Agents AI Safety Recursive Self-Improvement

Open paper AskPDF arXiv

Existing impossibility results for AI verification concern a fixed system. Self-modifying systems (agents that rewrite their own code, recursive self-improvement loops) raise a different question: can a safety property that holds now be certified, in advance, to keep holding after the system rewrites itself? We model one step of self-modification as a total computable transformation of code, and preservation as 'safe now and safe after the step'. If the transformation depends only on behaviour, preservation is Rice's theorem one level up; if it reads the code, as self-modification does, preservation is no longer semantic, yet at least as hard as the halting problem, by the same s-m-n reduction carried out inside a class of behaviourally identical programs. One step is never harder than the property; persistence along the whole trajectory can be one arithmetical level higher. No tower of supervisors lowers the problem; every total supervisor errs on a set of systems it cannot locate. Every faithful scheme certifying on finite behavioural evidence admits, for properties not settled by any finite set of inputs, an evolution trace it certifies at every stage while the property is violated. Statically, we record the classical limits (Rice, Goedel, Trakhtenbrot) and add the resource face: over succinctly described finite environments, verifying a policy against an adversary is coNP-complete and synthesising one PSPACE-complete. These limits do not say self-modifying systems are unsafe; they locate where algorithmic guarantees break, at the expressivity a general system needs: Turing-completeness and unrestricted self-modification. What survives is exact: a monitor detects the first violation of a safety property, and no sound procedure certifies all safe systems; certification requires restricting rewrites by design; and a frozen reference keeps the question well posed.

Abstract

Explore similar work

Algorithmic Unverifiability of Safety for Fixed and Recursively Self-Improving Systems

Incompleteness of AI Safety Verification via Kolmogorov Complexity

Are Safety Guarantees in Neural Networks Safe? How to Compute Trustworthy Robustness Certifications