Effect-Transparent Governance for AI Workflow Architectures: Semantic Preservation, Expressive Minimality, and Decidability Boundaries
Effect-Transparent Governance for AI Workflow Architectures: Semantic Preservation, Expressive Minimality, and Decidability Boundaries
AI 工作流架构的效应透明治理：语义保持、表达极小性与可判定性边界
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.
摘要： 我们提出了一种经机器验证的结构化治理 AI 工作流架构形式化方法，并证明了可以在不降低内部计算表达能力的前提下实施效应级治理。利用 Rocq 8.19 中的交互树（Interaction Trees），我们定义了一个治理算子 G，用于调解所有效应指令，包括内存访问、外部调用和预言机（LLM）查询。
Our development compiles with 0 admitted lemmas and consists of 36 modules, ~12,000 lines of Rocq, and 454 theorems. We establish seven 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.
我们的开发成果在零公理假设（admitted lemmas）下编译通过，包含 36 个模块、约 12,000 行 Rocq 代码和 454 条定理。我们确立了七项属性：(P1) 受治理的图灵完备性；(P2) 受治理的预言机表达能力；(P3) 可判定性边界，即治理谓词是全域的且在布尔组合下封闭，同时语义程序属性保持非平凡且无法通过治理判定；(P4) 许可执行下的目标保持；(P5) 原始能力（计算、内存、推理、外部调用、可观测性）的表达极小性；(P6) 包含不对称性，表明结构化治理严格包含内容级过滤；以及 (P7) 语义透明性：在所有治理允许的执行中，受治理的解释与未受治理的解释在观测上是等价的（仅差治理产生的事件）。
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.
总之，这些结果表明，治理与计算表达能力是正交的维度：治理限制了程序的效应边界，同时对内部计算保持语义透明。