Safety is Non-Compositional: A Formal Framework for Capability-Based AI Systems

Cosimo Spera

cs.AIMar 16, 2026

Safety is Non-Compositional: A Formal Framework for Capability-Based AI Systems

Authors: Cosimo Spera

Organizations: Minerva CQ, Los Gatos, CA 95032

Abstract

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.

Figures & tables

ID	Capability	Description
$c_{1}$	ParseIntent	Extract destination, dates, preferences
$c_{2}$	UserProfile	Retrieve loyalty tier, past trips, payment methods
$c_{3}$	FlightSearch	Query available flights
$c_{4}$	HotelSearch	Query available hotels
$c_{5}$	PriceOptimise	Compute best fare/rate combination
$c_{6}$	VisaCheck	Determine visa requirements

Table 1: Capabilities for the Paris booking task.

Arc	Tail $S$ $\to$ Head $T$	Semantics
$h_{1}$	$\{c_{1}\}\to\{c_{3},c_{4},c_{6}\}$	Parse intent unlocks three searches
$h_{2}$	$\{c_{2},c_{3},c_{4}\}\to\{c_{5}\}$	All three jointly enable price optimisation
$h_{3}$	$\{c_{5},c_{6}\}\to\{c_{7}\}$	Price + visa clearance enable flight booking
$h_{4}$	$\{c_{5}\}\to\{c_{8}\}$	Price optimisation enables hotel booking
$h_{5}$	$\{c_{7},c_{8}\}\to\{c_{9}\}$	Both bookings jointly enable the itinerary
$h_{6}$	$\{c_{7}\}\to\{c_{10}\}$	Flight booking enables insurance quote

Table 2: Hyperedges for the Paris booking task.

Step	Fired arc	$C_{i}$ after firing
$C_{0}$	—	$\{c_{1},c_{2}\}$
$C_{1}$	$h_{1}$ : $\{c_{1}\}\subseteq C_{0}$	$\{c_{1},c_{2},c_{3},c_{4},c_{6}\}$
$C_{2}$	$h_{2}$ : $\{c_{2},c_{3},c_{4}\}\subseteq C_{1}$	$\{c_{1},\ldots,c_{6}\}$
$C_{3}$	$h_{3}$ , $h_{4}$ fire	$\{c_{1},\ldots,c_{8}\}$
$C_{4}$	$h_{5}$ , $h_{6}$ , $h_{7}$ fire	$\{c_{1},\ldots,c_{11}\}$
$C_{5}$	$h_{8}$ : $\{c_{7},c_{8},c_{10}\}\subseteq C_{4}$	$\{c_{1},\ldots,c_{12}\}$

Table 3: Fixed-point closure from

A=\{c_{1},c_{2}\}

Dataset	Rate	95% Wilson CI	H1 ( $>30\%$ )	Annotation basis
ToolBench G3	47.4%	$[43.1\%,\;51.8\%]$	✓	Programmatic + $\kappa=0.81$
TaskBench DAG	36.5%	$[31.9\%,\;41.3\%]$	✓	Task-graph labels (GT)
AgentBench	pending	—	—	Task-spec preconditions (GT)
Gorilla / APIBench	pending	—	—	Team dependency annotations
Current overall	42.6%	$[39.4\%,\;45.8\%]$	✓	Two datasets (rows 1–2)

Table 4: H1: Conjunctive dependency prevalence across four datasets. ToolBench G3 and TaskBench DAG: current study. AgentBench and Gorilla: pending replication run. The annotation basis column specifies the ground truth source for annotation quality measurement.

Planner	Synthetic rate	Async rate	95% CI (async)	H2
Workflow	35.0%	38.2%	$[33.4\%,\;43.1\%]$	✓
Capability graph	0.0%	21.4%	$[17.3\%,\;26.1\%]$	✓
Hypergraph	0.0%	0.0%	n/a (proved zero)	✓ (spec check † )

Table 5: H2: AND-violation rates on 383 conjunctive instances. Async subset: 280 ToolBench G3 trajectories with

\Delta t>50

ms inter-branch latency. † The hypergraph planner’s zero violation rate is a proved theorem (Theorem 6.2 ), not an experimental finding; the experiment verifies implementation correctness.

Explore similar work

Tracking Capabilities for Safer Agents
Mar 1, 2026Martin Odersky, Yaoyu Zhao, Yichen Xu +2AI Agent Safety Tool Access Control for LLM Agents
EPFL Lausanne, Switzerland
From Workflow Automation to Capability Closure: A Formal Framework for Safe and Revenue-Aware Customer Service AI
Mar 16, 2026Cosimo SperaAI Agent Safety Customer Support Automation
Minerva CQ, 114 Lester Ln, Los Gatos, CA 95032
ChainCaps: Composition-Safe Tool-Using Agents via Monotonic Capability Attenuation
May 26, 2026Xiaochong Jiang, Shiqi Yang, Ziwei Li +3LLM Agent Security Capability-Based Security
Independent Researcher, Seattle, WA, USA · Independent Researcher, New York City, NY, USA · King Abdullah University of Science and Technology, Saudi Arabia

Mar 1, 2026J/K move · Enter open · S save

Tracking Capabilities for Safer Agents

Martin Odersky, Yaoyu Zhao, Yichen Xu, Oliver Bračevac+1

EPFL Lausanne, Switzerland

AI Agent Safety Tool Access Control for LLM Agents LLM Agent Harnesses Capability-Based Security Information Flow Control

Open paper AskPDF arXiv

AI agents that interact with the real world through tool calls pose fundamental safety challenges: agents might leak private information, cause unintended side effects, or be manipulated through prompt injection. To address these challenges, we propose to put the agent in a programming-language-based "safety harness": instead of calling tools directly, agents express their intentions as code in a capability-safe language: Scala 3 with capture checking. Capabilities are program variables that regulate access to effects and resources of interest. Scala's type system tracks capabilities statically, providing fine-grained control over what an agent can do. In particular, it enables local purity, the ability to enforce that sub-computations are side-effect-free, preventing information leakage when agents process classified data. We demonstrate that extensible agent safety harnesses can be built by leveraging a strong type system with tracked capabilities. Our experiments show that agents can generate capability-safe code with no significant loss in task performance, while the type system reliably prevents unsafe behaviors such as information leakage and malicious side effects.

Abstract

Explore similar work

Tracking Capabilities for Safer Agents

From Workflow Automation to Capability Closure: A Formal Framework for Safe and Revenue-Aware Customer Service AI

ChainCaps: Composition-Safe Tool-Using Agents via Monotonic Capability Attenuation