# Capability Safety as Datalog: A Foundational Equivalence

arXiv: https://arxiv.org/abs/2603.26725 · HTML: https://mlsanity.com/paper/2603.26725/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 25 references that are in the map.
- First posted on arXiv 20 Mar 2026.

## Builds on (most cited first, 4 of 4)

- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [TaskBench: Benchmarking Large Language Models for Task Automation](https://mlsanity.com/paper/2311.18760/) (2023)
- [AI Safety Gridworlds](https://mlsanity.com/paper/1711.09883/) (2017)
- [Safety is Non-Compositional: A Formal Framework for Capability-Based AI Systems](https://mlsanity.com/paper/2603.15973/) (2026)

## Built on by (most cited first, 2 of 2)

- [Safety as Computation: Certified Answer Reuse via Capability Closure in Task-Oriented Dialogue](https://mlsanity.com/paper/2603.21448/) (2026)
- [From ambiguous utterances to governed reuse classes: canonicalization, quotient invariance, and conditional decidability](https://mlsanity.com/paper/2607.10069/) (2026)

## Abstract (arXiv)

We prove that capability safety admits an exact representation as propositional Datalog evaluation (Datalogprop: the monadic, ground, function-free fragment of first-order logic), enabling the transfer of algorithmic and structural results unavailable in the native formulation. This addresses two structural limitations of the capability hypergraph framework of Spera [2026]: the absence of efficient incremental maintenance, and the absence of a decision procedure for audit surface containment. The equivalence is tight: capability hypergraphs correspond to exactly this fragment, no more.