AI Safety Gains a Database Theory Upgrade

Ensuring that AI agents don't misuse their capabilities is a critical as systems grow more complex. Researchers have formalized this as a problem of tracking which capabilities agents can collectively reach, but the computational tools for this have been limited, often requiring expensive recomputations from scratch with every change. A new study resolves this by proving a tight equivalence: the problem of capability safety is exactly the same as evaluating queries in a simple logical language called propositional Datalog. This connection transfers thirty years of database theory directly to AI safety, offering efficient algorithms and new structural insights that were previously inaccessible.

The key finding is that capability safety can be represented precisely as propositional Datalog evaluation, a fragment of first-order logic used in databases. This means that the safe audit surface—a map showing what capabilities agents can safely acquire—is actually a Datalog view, a derived relation computed by a fixed program. Under this identification, the safe goal map GF(A) becomes a stratified Datalog view, enabling the use of incremental maintenance algorithms like DRed. This structural fact leads to the Locality Gap Theorem, which establishes the first provable separation between global recomputation and local capability updates, showing that incremental maintenance can be significantly more efficient.

Ology involves explicit polynomial-time encodings in both directions between capability hypergraphs and Datalog programs. Each capability is treated as a propositional atom, and each hyperedge (representing conjunctive preconditions) becomes a Horn clause rule. The closure of a capability set corresponds to the least model of the Datalog program, and safety checks align with query evaluation. The equivalence is tight, meaning capability hypergraphs correspond exactly to this fragment, with no expressivity loss or gain, as proven by a parity-query separation showing the fragment cannot be enlarged.

From the paper show concrete algorithmic improvements. The DRed maintenance algorithm costs O(|Δ|·(n+mk)) per update, compared to O(|V|·(n+mk)) for naïve recomputation, with an explicit hard family witnessing an Ω(n) asymptotic gap. An AND-inspection lower bound, proved via indistinguishable instance pairs in an oracle model, shows any correct algorithm must probe all k+1 atoms in an update's precondition set to verify rule activation. Additionally, audit surface containment GF(A) ⊆ GF(A') becomes decidable in polynomial time via Datalog query containment, providing the first decision procedure for this problem.

Are significant for real-world AI deployments. This equivalence gives the capability safety research agenda direct access to thirty years of Datalog , including incremental maintenance, provenance tracking, and learning theory, without requiring new algorithms. For example, derivation certificates are now why-provenance witnesses with a commutative semiring structure, enabling compression and uniform validation. Each open problem from prior work maps to a known open problem in Datalog theory, allowing immediate transfer of partial and tighter bounds for structured systems.

However, the study has limitations. The equivalence holds for propositional, monotone capability systems only, meaning it doesn't directly extend to non-monotone settings like capability revocation, probabilistic capabilities, or higher-order interactions. The lower bound apply within a specific oracle model, and a general-purpose RAM lower bound for full incremental maintenance remains open. Despite this, the work provides a foundational computational lens for agentic safety, settling expressivity questions and opening new avenues for efficient and scalable safety reasoning.