Pith. sign in

REVIEW 3 major objections 1 cited by

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

T0 review · 3 major / 0 minor · reviewed 2026-07-15 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Formal certificates of AI alignment over open-ended domains are impossible: soundness, completeness, and tractability cannot hold at once.

desk verdict Clean packaging of two classical impossibilities into an alignment trilemma with independence witnesses and a coverage-gap bound; solid enough to send to referees. read the letter →

arxiv 2603.08761 v2 pith:NZQO4A6F submitted 2026-03-08 stat.ML cs.LG

Ayushi Agarwal This is my paper
classification stat.MLcs.LG MSC 68T0568Q1703D35
keywords AIalignmentformalverificationimpossibilitytheoremstrilemmaneuralnetworkRice'stheoremPAClearningParetofrontier
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether any procedure can certify that an AI system is aligned over every possible input, with the force of a mathematical guarantee rather than a score on tests. It answers no, under standard complexity and learning assumptions, by naming two independent barriers. The semantic barrier says that deciding any non-trivial alignment property for the whole input domain is already NP-hard for ordinary networks and undecidable for Turing-complete models. The statistical barrier says that any procedure that runs in polynomial time can inspect only finitely many inputs, so it cannot certify a property that must hold everywhere. Together they produce a trilemma: no verifier can be sound (never certifies a misaligned system), complete (never rejects an aligned one over the full domain), and tractable at once. Each pair is achievable with known tools; all three are not. The paper then maps the remaining space of partial guarantees and gives a concrete lower bound on the coverage gap any sound, fast verifier must leave.

What carries the argument

The Alignment Verification Trilemma (Corollary 1): no procedure can satisfy Soundness (S), Completeness (C), and Tractability (T) at once. It is forced by two independent theorems (semantic and statistical barriers) and is accompanied by a constructive coverage-gap lower bound on any sound, tractable verifier.

What would settle it

Exhibit a single verification procedure that is sound, complete over the full open-ended domain X, and runs in time polynomial in the system size, for a non-trivial alignment property on the model classes considered; or redefine alignment so that it is fully decided by a fixed finite evaluation set and show the trilemma no longer applies.

Watch

Extended reading notes

Core claim

Under the paper's assumptions, no verification procedure can simultaneously satisfy soundness, completeness over the full input domain, and polynomial-time tractability. Two independent barriers force this: a semantic barrier from neural-network verification hardness and Rice's theorem, and a statistical barrier from the impossibility of certifying infinite-domain properties from finite observations. Each pair of properties is achievable; the joint triple is not. The paper proves the barriers are independent and quantifies the unavoidable coverage gap.

Load-bearing premise

Alignment is defined over the entire unbounded input domain, so that any finite set of test points always leaves room for an aligned system and a misaligned system that look identical on those points.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 0 minor

Summary. The paper argues that formal certification of AI alignment over open-ended/unbounded input domains is impossible, via two barriers: a semantic barrier (Theorem 1: S+C verification is NP-hard for ReLU networks and undecidable for Turing-complete architectures, from Katz et al. and Rice) and a statistical barrier (Theorem 2: S+T cannot yield Completeness over full X, from finite-sample/PAC limits). These yield a trilemma (Corollary 1): Soundness, Completeness, and Tractability cannot hold simultaneously; each pair is achievable (Proposition 3). The authors prove structural independence (Proposition 1), give a constructive coverage-gap lower bound on a 1D threshold model class (Proposition 2), sketch a Pareto frontier, and illustrate with an IBP sweep on a small trained ReLU net. Practical implications for RLHF-style methods, bounded verification, and safety claims are discussed.

Significance. If the results hold as stated, the paper supplies a clean, usable map of what alignment certification can and cannot deliver: a two-cause trilemma, pairwise regimes with named tools, and a quantitative gap bound for a canonical class. The joint framing, explicit independence witnesses, hand-checkable running example, and constructive coverage-gap bound (Proposition 2) are genuine contributions beyond restating Katz/Rice/Valiant. The empirical IBP check and Table 2 mapping of published claims are useful for practice. These strengths matter for alignment theory and for how safety claims should be scoped. The contribution is primarily organizational and clarifying rather than a new complexity theorem; that is still valuable if the formal claims are tight.

major comments (3)
  1. Theorem 2 and its proof adopt an unstated query/black-box model that is not fixed in Definition 4. Definition 4 lets V take f_ heta (hence parameters) as input; white-box procedures need not 'issue queries.' Step 2 of the Theorem 2 proof ('identical behaviour forces identical verdicts') and the appeal to Goldreich-style query bounds therefore fail for white-box V. Concretely, on the running example F_ au the white-box rule V( heta)=aligned iff heta≤0.05 is simultaneously sound, complete, and tractable, contradicting the theorem as stated. Theorem 2 should be scoped to black-box/query or finite-sample procedures, or rewritten so the information-theoretic claim is explicit.
  2. Proposition 1(i) is load-bearing for 'structural independence' but inherits the same gap. It claims that if P=NP (semantic barrier dissolves) then Completeness still fails by Theorem 2. Under white-box access, P=NP would make the NP-complete ReLU verification problem poly-time, yielding S+C+T for feedforward nets and collapsing the trilemma in that regime. The stated witness (NP-oracle still cannot separate f_0.04 from f_0.06 without a critical-interval query) assumes the verifier cannot read heta. Either restrict independence to black-box verifiers or supply a correct white-box argument; as written the independence claim overreaches.
  3. Figure 3 and the Pareto discussion mix two distinct incompleteness mechanisms. Proposition 2 / panel (a) lower-bound ε=1-c is for n-query verifiers; the IBP experiment is white-box interval bound propagation, whose incompleteness comes from over-approximation and domain restriction, not from finite input queries. Presenting IBP points on the query-model curve and treating both as confirmation of the same 'statistical barrier' blurs the contribution. Separate the black-box coverage-gap bound from white-box bounded/approximate verification, and state which barrier each plot illustrates.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: impossibilities rest on external classical theorems (Rice, Katz NP-completeness, Valiant PAC) plus self-contained geometric witnesses; nothing reduces by construction to a fitted input or self-definition.

full rationale

The derivation chain is Theorem 1 (semantic barrier) from Katz et al. NP-completeness of ReLU verification plus Rice’s Theorem applied to non-trivial semantic A*, Theorem 2 (statistical barrier) from the elementary finite-query pigeonhole construction under Assumption 2, Corollary 1 as their direct conjunction, Proposition 1 independence via explicit running-example witnesses, and Proposition 2 coverage-gap lower bound by midpoint placement inside the largest unqueried interval. All load-bearing steps cite external, independently established results or perform elementary constructions on the 1D threshold family; no parameter is fitted to data and then re-presented as a prediction, no equation equates a claimed result to a quantity defined in terms of itself, and the single author has no prior self-citations that carry the argument. The IBP experiment is purely illustrative confirmation of the already-proved S+T regime and does not enter the formal claims. The paper is therefore self-contained against its external benchmarks and exhibits zero circular reduction.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The impossibility rests on two domain assumptions about model expressivity and full-domain alignment objectives, plus the standard background theorems of complexity and learning theory. No free parameters are fitted; the only numeric constants (δ, n) are free choices of the verifier or tolerance, not fitted to data. No new physical or computational entities are postulated.

assumptions (5)
  • domain assumption Assumption 1: F contains feedforward ReLU nets expressive enough for any computable function on bounded inputs, and (for undecidability) transformers in a Turing-complete regime.
    Invoked for both parts of Theorem 1; without sufficient expressivity the NP-hardness and Rice applications fail.
  • domain assumption Assumption 2: A* is defined over the full unbounded domain X so that any finite sample S admits systems that agree on S yet differ in A*.
    Load-bearing for Theorem 2 and the trilemma; Remark 1 notes that finite-set definitions fall outside the theorems.
  • standard math P ≠ NP (for the feedforward hardness claim).
    Standard complexity assumption used in Theorem 1(i) via Katz et al.
  • standard math Rice’s Theorem applies to non-trivial semantic properties of Turing-complete transformer regimes.
    Used in Theorem 1(ii); scoped by Remark 2 to architectures shown Turing-complete in the cited works.
  • standard math PAC/finite-sample impossibility: infinite-domain properties cannot be certified from finite observations.
    Grounds Theorem 2 via Valiant and Blumer et al.

how reviews work

0 comments
Cite this review

Pith. "Pith review of No Certificate for Alignment: Two Independent Impossibilities and the Pareto Frontier of Achievable Safety Guarantees." pith.science (2026). https://pith.science/paper/NZQO4A6F

@misc{pith2026260308761,
  author       = {Pith},
  title        = {Pith review of: No Certificate for Alignment: Two Independent Impossibilities and the Pareto Frontier of Achievable Safety Guarantees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NZQO4A6F}},
  note         = {Machine review of arXiv:2603.08761}
}
read the original 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.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. The Unverifiability of Artificial General Intelligence (AGI) Alignment, Static and Dynamic: From Trakhtenbrot's Wall to the Safety-Generality Tension

    cs.LO 2026-06 unverdicted novelty 6.5 of 10

    Persistent algorithmic safety certification of a Turing-complete self-modifying AGI is impossible; only systems that have stopped evolving semantically can be certified to remain safe.

Reference graph

Works this paper leans on

26 extracted references · 5 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Constitutional AI: Harmlessness from AI feedback

    [Bai et al.(2022)] Bai, Y ., Kadavath, S., Kundu, S., et al. Constitutional AI: Harmlessness from AI feedback. arXiv preprint arXiv:2212.08073,

    arXiv 2022

  2. [2]

    Interpreting blackbox models via model extraction

    [Bastani et al.(2016)] Bastani, O., Kim, C., and Bastani, H. Interpreting blackbox models via model extraction. arXiv preprint arXiv:1705.08504,

    arXiv 2016

  3. [3]

    On the computational power of transformers and its implications in sequence modelling

    [Bhattamishra et al.(2020)] Bhattamishra, S., Ahuja, K., and Goyal, N. On the computational power of transformers and its implications in sequence modelling. InProceed- ings of CoNLL, pp. 455–475,

    2020

  4. [4]

    [Blumer et al.(1989)] Blumer, A., Ehrenfeucht, A., Haus- sler, D., and Warmuth, M. K. Learnability and the Vapnik-Chervonenkis dimension.Journal of the ACM, 36(4):929–965,

    1989

  5. [5]

    F., Leike, J., Brown, T., et al

    [Christiano et al.(2017)] Christiano, P. F., Leike, J., Brown, T., et al. Deep reinforcement learning from human preferences. InAdvances in NeurIPS,

    2017

  6. [6]

    Scal- ing laws for reward model overoptimisation

    [Gao et al.(2023)] Gao, L., Schulman, J., and Hilton, J. Scal- ing laws for reward model overoptimisation. InPro- ceedings of ICML,

    2023

  7. [7]

    Cambridge University Press,

    [Goldreich(2017)] Goldreich, O.Introduction to Property Testing. Cambridge University Press,

    2017

  8. [8]

    Safety verification of deep neural networks

    [Huang et al.(2017)] Huang, X., Kwiatkowska, M., Wang, S., and Wu, M. Safety verification of deep neural networks. InComputer Aided Verification, pp. 3–29. Springer,

    2017

Show all 26 references
  1. [9]

    L., et al

    [Katz et al.(2017)] Katz, G., Barrett, C., Dill, D. L., et al. Reluplex: An efficient SMT solver for verifying deep neural networks. InComputer Aided Verification (CAV), pp. 631–649. Springer,

    2017

  2. [10]

    Catastrophic Goodhart: Regularizing RLHF with KL divergence does not mitigate heavy-tailed re- ward misspecification

    [Kwa et al.(2024)] Kwa, T., Thomas, D., and Garriga- Alonso, A. Catastrophic Goodhart: Regularizing RLHF with KL divergence does not mitigate heavy-tailed re- ward misspecification. InAdvances in NeurIPS,

    2024

  3. [11]

    and Wang, Y

    [Li & Wang(2025)] Li, Q. and Wang, Y . Constant bit-size transformers are Turing complete.arXiv preprint arXiv:2506.12027,

    2025

  4. [12]

    and Sabharwal, A

    [Merrill & Sabharwal(2024)] Merrill, W. and Sabharwal, A. The expressive power of transformers with chain of thought. InICLR,

    2024

  5. [13]

    F., Pascanu, R., Cho, K., and Bengio, Y

    [Montufar et al.(2014)] Montufar, G. F., Pascanu, R., Cho, K., and Bengio, Y . On the number of linear regions of deep neural networks. InAdvances in NeurIPS, pp. 2924–2932,

    2014

  6. [14]

    Training language models to follow instructions with human feedback

    [Ouyang et al.(2022)] Ouyang, L., Wu, J., Jiang, X., et al. Training language models to follow instructions with human feedback. InAdvances in NeurIPS,

    2022

  7. [15]

    Attention is Turing-complete.JMLR, 22(75):1–35,

    [P´erez et al.(2021)] P´erez, J., Barcel ´o, P., and Marinkovic, J. Attention is Turing-complete.JMLR, 22(75):1–35,

    2021

  8. [16]

    Direct preference optimisation: Your lan- guage model is secretly a reward model

    [Rafailov et al.(2023)] Rafailov, R., Sharma, A., Mitchell, E., et al. Direct preference optimisation: Your lan- guage model is secretly a reward model. InAdvances in NeurIPS,

    2023

  9. [17]

    [Rice(1953)] Rice, H. G. Classes of recursively enumerable sets and their decision problems.Transactions of the American Mathematical Society, 74(2):358–366,

    1953

  10. [18]

    Defining and characterising reward hacking

    [Skalse et al.(2022)] Skalse, J., Howe, N., Krasheninnikov, D., and Krueger, D. Defining and characterising reward hacking. InAdvances in NeurIPS,

    2022

  11. [19]

    [Valiant(1984)] Valiant, L. G. A theory of the learnable. Communications of the ACM, 27(11):1134–1142,

    1984

  12. [20]

    Beta- CROWN: Efficient bound propagation with per-neuron split constraints for complete and incomplete neural network verification

    [Wang et al.(2021)] Wang, S., Zhang, H., Xu, K., et al. Beta- CROWN: Efficient bound propagation with per-neuron split constraints for complete and incomplete neural network verification. InAdvances in NeurIPS,

    2021

  13. [21]

    GPT-4 technical report.arXiv preprint arXiv:2303.08774,

    [OpenAI(2023)] OpenAI. GPT-4 technical report.arXiv preprint arXiv:2303.08774,

    2023 arXiv

  14. [22]

    Gemini: A family of highly capable multimodal models.arXiv preprint arXiv:2312.11805,

    [Gemini Team(2023)] Gemini Team, Google. Gemini: A family of highly capable multimodal models.arXiv preprint arXiv:2312.11805,

    2023 arXiv

  15. [23]

    and Lynch, N

    [Gilbert & Lynch(2002)] Gilbert, S. and Lynch, N. Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services.ACM SIGACT News, 33(2):51–59,

    2002

  16. [24]

    Cambridge University Press,

    [Baader et al.(2003)] Baader, F., Calvanese, D., McGuin- ness, D., Nardi, D., and Patel-Schneider, P.The De- scription Logic Handbook. Cambridge University Press,

    2003

  17. [25]

    and Cousot, R

    [Cousot & Cousot(1977)] Cousot, P. and Cousot, R. Ab- stract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. InProceedings of POPL, pp. 238–252,

    1977

  18. [26]

    On the effectiveness of interval bound propagation for training verifiably robust models.arXiv preprint arXiv:1810.12715, 2018

    [Gowal et al.(2018)] Gowal, S., Dvijotham, K., Stanforth, R., Bunel, R., Qin, C., Uesato, J., Mann, T., and Kohli, P. On the effectiveness of interval bound propagation for training verifiably robust models.arXiv preprint arXiv:1810.12715, 2018

    2018 arXiv

Pith tools

Reviewed July 15, 2026 · model on record in the stance chip above.