Safety is Non-Compositional: A Formal Framework for Capability-Based AI Systems
Open accessAbstract
This paper contains the first formal proof that safety is non-compositional in the presence of conjunctive capability dependencies: two agents each individually inca- pable of reaching any forbidden capability can, when combined, collectively reach a forbidden goal through an emergent conjunctive dependency.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Heterogeneous attacks that decompose malicious tasks across individually safe models are non-local by construction and shared elements such as RAGs or other shared memory, making per-component certification structurally insufficient.
“Heterogeneous attacks that decompose malicious tasks across individually safe models are non-local by construction (Jones et al., 2024) and shared elements such as RAGs (Lewis et al., 2020) or other shared memory, making per-component certification structurally insufficient (Spera, 2026;Ghosh et al., 2025).”
From Open Challenges in Multi-Agent Security: Towards Secure Systems of Interacting AI Agents (2025) · cites this paper as Spera, 2026
Individually safe components compose into unsafe systems.
“Compositionality.Individually safe components compose into unsafe systems Ghosh et al. (2025); Spera (2026).”
From Open Challenges in Multi-Agent Security: Towards Secure Systems of Interacting AI Agents (2025) · cites this paper as Spera (2026)
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 27
- Sebastian S. Bauer, Rolf Hennicker, Maciej Janicki, and Martin Wirsing. Interface theories for concurrency and data. Theoretical Computer Science, 412(28):3101-3121, 2012.
- Albert Benveniste, Benoît Caillaud, Dejan Nickovic, et al. Contracts for system design. Founda- tions and Trends in Electronic Design Automation, 12(2-3):124-400, 2018.
- Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4):929-965, 1989.
- Blai Bonet and Héctor Geffner. Planning as heuristic search. Artificial Intelligence, 129(1-2):5- 33, 2001.
- Luca de Alfaro and Thomas A. Henzinger. Interface automata. In Proceedings of ESEC/FSE 2001, pages 109-120, 2001.
- Thomas Eiter and Georg Gottlob. Identifying the minimal transversals of a hypergraph and related problems. SIAM Journal on Computing, 24(6):1278-1304, 1995.
- Kutluhan Erol, James Hendler, and Dana S. Nau. HTN planning: Complexity and expressivity. In AAAI-94, pages 1123-1128, 1994.
- Satoru Fujishige. Submodular Functions and Optimization. Elsevier, 2nd edition, 2005.
- Giorgio Gallo, Giustino Longo, Stefano Pallottino, and Sang Nguyen. Directed hypergraphs and applications. Discrete Applied Mathematics, 42(2-3):177-201, 1993.
- Bernhard Ganter and Rudolf Wille. Formal Concept Analysis: Mathematical Foundations. Springer, 1999.
- Leslie M. Goldschlager. The monotone and planar circuit value problems are log space complete for P. ACM SIGACT News, 9(2):25-29, 1977.
- Cliff B. Jones. Tentative steps toward a development method for interfering programs. ACM Transactions on Programming Languages and Systems, 5(4):596-619, 1983.
- Stuart Kauffman. Investigations. Oxford University Press, 2000.
- Richard E. Ladner. The circuit value problem is log space complete for P. ACM SIGACT News, 7(1):18-20, 1975.
- Tadao Murata. Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 77(4):541-580, 1989.
- George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approxima- tions for maximizing submodular set functions. Mathematical Programming, 14(1):265-294, 1978.
- Carl Adam Petri. Kommunikation mit Automaten. PhD thesis, Universität Hamburg, 1962.
- Yujia Qin, Shihao Liang, Yining Ye, et al. ToolLLM: Facilitating large language models to master 16,000+ real-world APIs. In ICLR 2024 (Spotlight), 2023.
- Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. Pearson, 4th edition, 2021.
- Alberto Sangiovanni-Vincentelli, Werner Damm, and Roberto Passerone. Taming Dr. Franken- stein: Contract-based design for cyber-physical systems. European Journal of Control, 18(3):217-238, 2012.
- Yongliang Shen et al. TaskBench: Benchmarking large language models for task automation. arXiv:2311.18760, 2023. · arXiv
- Cosimo Spera. From workflow automation to capability closure: A formal framework for safe and revenue-aware customer service AI. arXiv preprint, arXiv:2603.15978, March 2026. · arXiv
- Maarten H. van Emden and Robert A. Kowalski. The semantics of predicate logic as a program- ming language. Journal of the ACM, 23(4):733-742, 1976.
- Xiao Liu, Hao Yu, Hanchen Zhang, et al. AgentBench: Evaluating LLMs as agents. arXiv preprint, arXiv:2308.03688, 2023. · arXiv
- Shishir G. Patil, Tianjun Zhang, Xin Wang, and Joseph E. Gonzalez. Gorilla: Large language model connected with massive APIs. arXiv preprint, arXiv:2305.15334, 2023. · arXiv
- J. Richard Landis and Gary G. Koch. The measurement of observer agreement for categorical data. Biometrics, 33(1):159-174, 1977.
- Shunyu Yao, Jeffrey Zhao, Dian Yu, et al. ReAct: Synergizing reasoning and acting in language models. In ICLR 2023, 2023.
Cited by
Sorted by citations
Open Challenges in Multi-Agent Security: Towards Secure Systems of Interacting AI Agents
de Witt, C. S., Krawiecka, K., Krawczuk, I., Hagag, B., Anderson, W. L., Belcak, P., Bucknall, B., Cai, X., Chopra, A., Cohen, D., et al. (2025) · arXiv · doi:10.48550/arxiv.2505.02077 · Cited by 2 · see citing works
- Authors
- Spera, C.
- Affiliations
- Los Angeles LGBT Center (US)
- Corresponding author
- Spera, Cosimo
- ORCID
- Spera, Cosimo
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2026
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2603.15973
- OpenAlex
- W7138919616
- Cited by
- 0
- References
- 0
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- arXiv (Cornell University) (submittedVersion, cc-by)
- arXiv (Cornell University) (cc-by)
- Topics
- Social Sciences › Sociology and Political Science › Access Control and Trust
- Physical Sciences › Engineering › Safety, Risk, Reliability and Quality › Safety Systems Engineering in Autonomy
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Formal Methods in Verification
- Keywords
- emergent capabilities, multi-agent systems, formal proof, AI safety
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
