🤖 AI

Effect-Transparent Governance for AI Workflow Architectures: Semantic Preservation, Expressive Minimality, and Decidability Boundaries

This paper presents a machine-checked formalization in Rocq demonstrating that effect-transparent governance for AI workflows can strictly constrain external effects and enforce safety predicates without compromising internal computational expressivity or semantic transparency.

Original authors: Alan L. McCann

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Alan L. McCann

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a brilliant, hyper-capable AI assistant. It can write code, remember things, call outside tools, and even chat with other AI models to solve complex problems. But you're worried: what if it decides to do something dangerous, like delete your files or call a service it shouldn't?

Traditionally, people thought you had to choose between safety and capability. You could either let the AI do whatever it wants (risky) or put heavy restrictions on it that might stop it from doing its job correctly (stupid).

This paper introduces a new way to build AI systems that proves you don't have to make that trade-off. It shows you can put a "governance" layer around the AI that stops bad actions without changing how the AI thinks or solves problems.

Here is the breakdown using simple analogies:

1. The Core Idea: The "Bouncer" vs. The "Editor"

Most current safety methods act like an Editor. The AI does its work, writes a story, and then the Editor reads it. If the story has a bad word, the Editor cuts it out or rewrites the sentence.

The Problem: The Editor changes the story. The AI's original thought process is altered, and the final result might be different from what the AI intended.

This paper proposes a Bouncer approach (called "Effect-Transparent Governance").

How it works: The AI is in a room. Before it can open a door (like accessing memory, calling a tool, or asking an LLM), it has to show its ID to the Bouncer.
The Magic: If the Bouncer says "Go ahead," the AI walks through the door and does exactly what it planned. The Bouncer didn't change the AI's thought process; they just checked the ID.
The Result: If the AI is allowed to proceed, the outcome is exactly the same as if the Bouncer wasn't there at all. The AI's "brain" remains untouched.

2. The "Interaction Tree" (The Blueprint)

The authors built a mathematical model of AI workflows using something they call "Interaction Trees."

Analogy: Think of an AI workflow as a tree. The trunk is the AI's logic. The branches are the things it wants to do (like "Call a database" or "Ask a question").
The "Governance" is a wrapper around the tips of the branches. It checks every single branch before it grows. If a branch is unauthorized, the tree stops growing there (it "diverges" or spins in place). If it's authorized, the branch grows exactly as the AI designed it.

3. Seven Key Discoveries (The "Seven Pillars")

The authors used a computer to mathematically prove seven things about this system:

P1 & P2: It's Still Super Smart. Even with the Bouncer checking IDs, the AI can still do anything a normal computer can do (Turing Complete) and can still use advanced tools like LLMs. The safety net didn't make the AI "dumber."
P3: The "Decidability Boundary" (The Line in the Sand). The Bouncer is good at checking structural rules (e.g., "Is this a memory request?" "Does this user have a Level 5 badge?"). These are easy to check instantly. However, the Bouncer cannot predict if the AI will get stuck in a loop forever or if a complex math problem will ever finish. The paper proves the Bouncer stays in its lane: it checks rules, not deep philosophical questions about the AI's future behavior.
P4: Goal Preservation. If the AI is allowed to run, it will achieve its goal. If it was supposed to calculate 2+2, it will still calculate 4. The safety check didn't change the math.
P5: Expressive Minimality. The system uses a specific set of tools (Compute, Memory, Reasoning, Calling Tools, Observing). The authors proved that if you remove any one of these tools, the AI loses a specific type of power. You can't simplify the system further without breaking its ability to do complex work.
P6: The "Bouncer" is Stronger than the "Editor". The paper proves that checking the action (structural governance) is strictly better than just filtering the output (content governance). A Bouncer can stop a bad action before it happens. An Editor can only try to fix a bad result after it happens, which is less reliable.
P7: Semantic Transparency (The "Ghost" Effect). This is the most important part. On every single run where the AI is allowed to work, the result is observationally equivalent to an ungoverned run. To an outside observer, it's as if the governance layer was invisible (a ghost), except for the fact that it successfully stopped the bad stuff.

4. The "Artifact" (The Proof)

The authors didn't just write this down; they built it inside a proof assistant called Rocq (a tool for verifying math).

They wrote 12,000 lines of code.
They proved 454 theorems.
They admitted zero errors (0 admitted lemmas).
This means the computer has double-checked their logic and confirmed it is 100% mathematically sound.

Summary

This paper argues that we can build AI systems with a "safety wrapper" that acts like a strict gatekeeper. This gatekeeper stops unauthorized actions (like hacking or unauthorized calls) but, crucially, does not interfere with the AI's thinking process when the action is allowed.

It proves that Safety and Intelligence are not enemies. You can have a system that is fully governed and safe, yet retains its full ability to compute, reason, and act, provided the actions are authorized. The governance layer is transparent to the AI's success, acting only as a shield against unauthorized effects.

Technical Summary: Effect-Transparent Governance for AI Workflow Architectures

Problem Statement

As AI workflow systems increasingly act in the world—querying Large Language Models (LLMs), managing state, and invoking external tools—there is a growing need for governance mechanisms to prevent unsafe or unauthorized behavior. A prevailing assumption in the field is that governance inevitably trades off against capability: restrictions intended to increase safety are believed to reduce the space of behaviors a system can exhibit. This paper challenges that assumption by formalizing an architectural alternative where governance is imposed at the effect boundary rather than by modifying internal computation or post-processing outputs. The central semantic question addressed is whether governance changes what permitted programs compute.

Methodology

The authors present a machine-checked formalization of structurally governed AI workflow architectures using Interaction Trees within the Rocq 8.19 proof assistant (formerly Coq). The development consists of 36 modules, 12,000 lines of code, and 454 theorems, with zero admitted lemmas.

Core Formalism

Interaction Trees (ITrees): Programs are modeled as coinductive trees over an event type $E$ , defined as Ret(v), Tau(t), or Vis(e, k). This allows for the representation of recursive and impure programs.
Directive Event Type: The system defines a DirectiveE type containing constructors for primitive capabilities: computation morphisms, memory operations, oracle (LLM) calls, external tool calls, and observability events.
Governance Operator ( $G$ ): Governance is implemented as a wrapper over effect interpretation, following the tradition of algebraic effect handlers. The operator $G(h)$ mediates every directive issued by a base handler $h$ . It performs pre-checks (trust, permission, phase validation) and post-instrumentation (provenance, observability). If a check fails, execution diverges via ITree.spin; if it passes, the directive is delegated to the underlying handler.
Safety Predicate: Safety is defined via a coinductive predicate gov_safe using parameterized coinduction (paco). This predicate distinguishes between governance-only events (which are always permitted) and real I/O events (which require explicit authorization).

Key Contributions and Results

The paper establishes seven primary properties (P1–P7) proving that governance and computational expressivity are orthogonal dimensions.

1. Semantic Transparency (The Core Theorem)

The central contribution is a machine-checked theorem proving semantic transparency. For all executions where governance checks succeed, the governed interpretation is observationally equivalent (modulo governance-only events) to the ungoverned interpretation.

Implication: Permitted programs compute the exact same partial function and produce the same reachable return values as they would without governance. Governance constrains the boundary of effects without altering the internal computation of allowed paths.

2. Governed Expressivity (P1 & P2)

The authors prove that the governance wrapper does not reduce computational power:

Governed Turing Completeness: The system remains Turing-complete under governance. Register machine programs can be translated into governed interaction trees without loss of expressivity.
Governed Oracle Expressivity: The architecture supports oracle extensions (LLM queries) under governance, maintaining the ability to model complex reasoning workflows.

3. Decidability Boundary (P3)

The paper formalizes a strict boundary between what governance can decide and what it cannot:

Governance Predicates: These are structural, syntactic, total, and closed under Boolean composition (AND, OR, NOT). They can decide properties like trust levels and capability classes.
Semantic Properties: Program properties such as halting remain non-trivial and undecidable by governance. The paper proves that governance cannot decide halting, as two programs may share identical directive structures (and thus pass governance checks) but differ in global termination behavior. This aligns with Rice's Theorem applied to the structural boundary.

4. Expressive Minimality (P5)

The authors prove that the set of primitive capabilities (compute, memory, reasoning, external call, observability) is minimally necessary.

Strict Hierarchy: The capabilities form a strict chain: code < code + memory < code + memory + reason < code + memory + reason + call.
Necessity: Removing any single primitive capability strictly reduces the system's expressive power. For instance, memory directives are structurally necessary for Turing completeness, and LLMCall directives are necessary for oracle extensions.

5. Subsumption Asymmetry (P6)

The paper establishes a strict separation between structural governance and content-level filtering:

Structural Subsumes Content: Structural governance strictly subsumes content filtering. By mediating effects at the interpretation boundary, structural governance prevents unauthorized I/O events from occurring.
Content Does Not Subsume Structural: Content filters (e.g., output rewriting) may alter values but cannot prevent the occurrence of an unauthorized effect step. Therefore, content filtering alone does not imply effect safety.

6. Goal Preservation (P4)

On all executions where governance permits, the system preserves the goals of the program. If a program is designed to reach a specific return value $v$ , and the governance checks pass, the governed execution will reach $v$ .

7. Safety via Denial (Liveness vs. Safety)

When a governance check fails, the system trades liveness for safety. The execution diverges (spin) rather than producing an incorrect result. The system guarantees that no unauthorized effect ever occurs, and no "unsafe" return value is ever produced.

Significance and Scope

The paper claims to demonstrate that governance and computational expressivity are orthogonal. Governance can be imposed to constrain the effect boundary of programs without reducing their internal computational expressivity or altering their semantics on permitted traces.

Trust Boundary: The guarantees hold relative to a Trusted Computing Base (TCB) consisting of the Rocq kernel, the Interaction Trees library, and the runtime implementation of the $G$ operator. The paper draws a parallel to verified compilers (CompCert) and OS kernels (seL4), noting that the gap between the formal model and deployed runtime is bridged by testing (validated against 70,000+ generated sequences).
Limitations: The transparency theorem applies only to permitted executions; denied executions diverge. The model abstracts away resource exhaustion, scheduling, and probabilistic model behaviors. The theorems apply to the abstract architecture and interpreter, not end-to-end guarantees on compiled binaries.

This work extends prior mechanized developments (McCann [2026b, 2026e]) by adding semantic transparency, expressive minimality, and a formal decidability boundary, providing a rigorous foundation for "effect-transparent governance" in AI systems.