← All papers
First page of Ceci n'est pas une pipe: A semantics of justified reliance for AI systems

Ceci n'est pas une pipe: A semantics of justified reliance for AI systems

Jade Alglave, Patrick Cousot

cs.AI Jul 10, 2026 · v3 cs.PL
Theorem encodings of the justified-reliance semantics are checked in Lean 4.24.0 using only its core library, alongside Z3 checks and an OCaml harness.
An AI agent may keep a successful check in context after an edit has invalidated its evidence. We give a semantics for specifying when a system may rely on a message and act on it. Reliability checks an asserted claim against accepted domain knowledge, sources, and messages in the selected context. Justified reliance additionally checks current evidence, authority, and the proposed world change. Relational component semantics and event traces represent nondeterministic outputs, iteration, and external changes. We characterise when merging claims preserves derivable conclusion classes, then construct the coarsest permitted quotient whose rules preserve the exact statuses of designated concrete claims. Construction is polynomial for unary rules; deciding even one permitted merge is coNP-complete for acyclic binary rules. This applies completeness and strong-preservation methods to the execution of quotiented rules. We also relate transition safeguards to runtime enforcement. Relative to a supplied set of possible worlds, a sound guard accepts an observation only when every matching world passes the checks. Exact acceptance requires observations that distinguish opposite-decision worlds; choosing sufficient services is NP-complete on explicit finite tables. A complete finite passport-renewal instance, Lean theorem encodings, Z3 instance checks, and an OCaml harness exercise the semantics. Domain knowledge, interpretation, source licenses, and policy remain application inputs.

AI agents may rely on messages, such as stale successful checks, whose evidence has been invalidated by later edits. A precise semantics is needed to specify when a system may rely on a message and act on it.

The semantics separates universal, source-derived and effective knowledge bases with four-valued paraconsistent justification. It defines reliable claims and justified reliance, which also checks evidence freshness, authority and world change. Components are modelled with relational semantics and event traces. Quotients of claims that preserve derivable conclusions are characterised, and transition safeguards are related to runtime enforcement over sets of possible worlds.

The coarsest permitted status-preserving quotient is constructible in polynomial time for unary rules, while deciding a single permitted merge is coNP-complete for acyclic binary rules. Choosing sufficient observation services for exact acceptance is NP-complete on explicit finite tables. A passport-renewal instance is validated with Lean theorem encodings, Z3 checks and an OCaml harness.