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

• URL: http://arxiv.org/abs/2605.01030v2
• Date: Tue, 05 May 2026 10:41:41 GMT
• Title: Effect-Transparent Governance for AI Workflow Architectures: Semantic Preservation, Expressive Minimality, and Decidability Boundaries
• Abstract summary: We present a machine-checked formalization of structurally governed AI workflow architectures.<n>We prove that effect-level governance can be imposed without reducing internal computational expressivity.
• Score: 0.0
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We present a machine-checked formalization of structurally governed AI workflow architectures and prove that effect-level governance can be imposed without reducing internal computational expressivity. Using Interaction Trees in Rocq 8.19, we define a governance operator G that mediates all effectful directives, including memory access, external calls, and oracle (LLM) queries. Our development compiles with 0 admitted lemmas and consists of 36 modules, ~12,000 lines of Rocq, and 454 theorems. We establishseven properties: (P1) governed Turing completeness, (P2) governed oracle expressivity, (P3) a decidability boundary in which governance predicates are total and closed under Boolean composition while semantic program properties remain non-trivial and undecidable by governance, (P4) goal preservation for permitted executions, (P5) expressive minimality of primitive capabilities (compute, memory, reasoning, external call, observability), (P6) subsumption asymmetry showing structural governance strictly subsumes content-level filtering, and (P7) semantic transparency: on all executions where governance permits, the governed interpretation is observationally equivalent (modulo governance-only events) to the ungoverned interpretation. Together, these results show that governance and computational expressivity are orthogonal dimensions: governance constrains the effect boundary of programs while remaining semantically transparent to internal computation.

Related papers

• Algebraic Semantics of Governed Execution: Monoidal Categories, Effect Algebras, and Coterminous Boundaries [0.0]
  We present a framework for governed execution in which governance is axiomatized, compositional, and coterminous with expressibility.<n>A three-axiom GovernanceAlgebra record induces a symmetric monoidal category with verified pentagon, triangle, and hexagon coherence.<n>A dual guarantee theorem establishes that within_caps and gov_safe hold simultaneously under all composition operators.
  arXiv  Detail & Related papers  (2026-05-01T18:59:01Z)
• The Two Boundaries: Why Behavioral AI Governance Fails Structurally [0.0]
  We focus on the governance of effects, actions that AI systems perform in the world.<n>Rice's theorem proves the gap is undecidable in the general case for Turing-complete architecture.<n>We propose coterminous governance as the testable criterion for any AI governance system.
  arXiv  Detail & Related papers  (2026-04-30T01:12:32Z)
• Mechanized Foundations of Structural Governance: Machine-Checked Proofs for Governed Intelligence [0.0]
  We present five results in the theory of structural governance for cognitive workflow systems.<n>Three are in Coq 8.19 using the Interaction Trees library with mechanizedized coinduction; two are proved on paper with explicit reductions.<n>A sixth contribution connects the abstract model to the deployed runtime: the Verified Interpreter Specification.
  arXiv  Detail & Related papers  (2026-04-30T01:03:15Z)
• PolicyBank: Evolving Policy Understanding for LLM Agents [51.86716874651299]
  PolicyBank maintains structured, tool-level policy insights and iteratively refines them.<n>PolicyBank closes up to 82% of the gap toward a human oracle.
  arXiv  Detail & Related papers  (2026-04-16T20:29:30Z)
• Governed Memory: A Production Architecture for Multi-Agent Workflows [0.0]
  Enterprise AI deploys dozens of autonomous agent nodes across, each acting on the same entities with no shared memory governance.<n>We identify five structural challenges arising from this memory governance gap.<n>We present Governed Memory, a shared memory and governance layer addressing this gap through four mechanisms.
  arXiv  Detail & Related papers  (2026-03-18T14:49:31Z)
• OOWM: Structuring Embodied Reasoning and Planning via Object-Oriented Programmatic World Modeling [62.3458279176813]
  We propose Object-Oriented World Modeling (OOWM), a novel framework that structures embodied reasoning through the lens of software engineering formalism.<n>OOWM employs Class Diagrams to ground visual perception into rigorous object hierarchies, and Activity Diagrams to operationalize planning into executable control flows.
  arXiv  Detail & Related papers  (2026-02-25T16:01:07Z)
• Towards a Science of Scaling Agent Systems [79.64446272302287]
  We formalize a definition for agent evaluation and characterize scaling laws as the interplay between agent quantity, coordination structure, modelic, and task properties.<n>We derive a predictive model using coordination metrics, that cross-validated R2=0, enabling prediction on unseen task domains.<n>We identify three effects: (1) a tool-coordination trade-off: under fixed computational budgets, tool-heavy tasks suffer disproportionately from multi-agent overhead, and (2) a capability saturation: coordination yields diminishing or negative returns once single-agent baselines exceed 45%.
  arXiv  Detail & Related papers  (2025-12-09T06:52:21Z)
• BRIDGE: Building Representations In Domain Guided Program Verification [67.36686119518441]
  BRIDGE decomposes verification into three interconnected domains: Code, Specifications, and Proofs.<n>We show that this approach substantially improves both accuracy and efficiency beyond standard error feedback methods.
  arXiv  Detail & Related papers  (2025-11-26T06:39:19Z)
• Explainable Rule Application via Structured Prompting: A Neural-Symbolic Approach [0.0]
  Large Language Models (LLMs) excel in complex reasoning tasks but struggle with consistent rule application, exception handling, and explainability.<n>This paper introduces a structured prompting framework that decomposes reasoning into three verifiable steps: entity identification, property extraction, and symbolic rule application.
  arXiv  Detail & Related papers  (2025-06-19T14:14:01Z)
• SOPBench: Evaluating Language Agents at Following Standard Operating Procedures and Constraints [59.645885492637845]
  SOPBench is an evaluation pipeline that transforms each service-specific SOP code program into a directed graph of executable functions.<n>Our approach transforms each service-specific SOP code program into a directed graph of executable functions and requires agents to call these functions based on natural language SOP descriptions.<n>We evaluate 18 leading models, and results show the task is challenging even for top-tier models.
  arXiv  Detail & Related papers  (2025-03-11T17:53:02Z)
• An Information Bottleneck Approach for Controlling Conciseness in Rationale Extraction [84.49035467829819]
  We show that it is possible to better manage this trade-off by optimizing a bound on the Information Bottleneck (IB) objective. Our fully unsupervised approach jointly learns an explainer that predicts sparse binary masks over sentences, and an end-task predictor that considers only the extracted rationale.
  arXiv  Detail & Related papers  (2020-05-01T23:26:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.