FAOPs: Normal Forms and an Algebra for AI Agent Workflows
A research paper posted to arXiv titled “FAOPs: Normal Forms and an Algebra for AI Agent Workflows” proposes a formal theory that gives AI agent workflows database‑grade discipline, an issue that matters because regulated sectors require operational procedures to be traceable, auditable, reproducible, access‑controlled, and bounded in time and cost.
The paper explains that organizations increasingly encode operational procedures as multi‑step agent skills, called Agent Operating Procedures (AOPs). In practice, AOPs are kept as coarse‑grained files where steps bundle actions, copied procedures drift apart, any step may reach any tool, and refactoring goes unchecked. The authors argue that these shortcomings conflict with the compliance requirements of regulated industries.
The authors introduce Functional Agent Operating Procedures (FAOP), a theory that recasts each workflow as a typed function over scoped state and subjects an entire library to four progressive normal forms. The first normal form, Decomposed (FNF‑1), splits a workflow into atomic steps. The second, Typed (FNF‑2), makes data flow explicit and type‑checked. The third, Factored (FNF‑3), gives each shared procedure a single canonical definition so a change propagates instead of drifting. The fourth, Scoped (FNF‑4), confines every step to least‑privilege tool access. Once normalized, each atomic step becomes a separate entity with a declared contract that can be type‑checked, scope‑confined, bounded, tested, traced, and audited on its own.
The paper also defines a FAOP algebra of provably sound equalities that turn refactoring and parallelization into compiler rewrites. Orthogonal extensions add verified termination (+V), optimization (+O), and time and cost bounds (+B). An architectural‑level classifier (0–3) determines whether a workflow needs AI at all. The authors implement the theory in SkillBase, an AOP management system likened to PostgreSQL for data, together with a separate executor that enforces the guarantees at run time. A worked financial workflow demonstrates the approach end to end.
The system consists of three concrete components: the FAOP formalism, the SkillBase repository, and the executor. A developer writes an AOP as a file; SkillBase stores it and applies the four normal‑form transformations, producing a library of atomic, typed, factored, and scoped steps. During transformation, the system checks that each step’s input and output types match the declared signatures (Typed) and that each step’s declared tool permissions satisfy the least‑privilege rule (Scoped). The canonical definition created in Factored ensures that any modification to a shared sub‑procedure updates all references, eliminating drift. The executor then runs the normalized steps, relying on the contracts established at compile time; because the steps are already type‑checked and scope‑confined, the executor’s role is limited to enforcing runtime bounds rather than performing additional validation.
The design decision to require full normalization before execution trades upfront modeling effort for compile‑time guarantees. By moving integrity, isolation, typing, termination, cost, and optimization concerns to the compile stage, the system reduces the need for runtime monitoring and audit overhead, which benefits organizations that must demonstrate compliance. However, developers must invest in defining atomic steps, explicit types, and scope contracts, which can slow initial development and raise the learning curve for teams unfamiliar with the formalism. The executor’s reliance on the compile‑time contracts means that any omission in the normal‑form process could surface only as a runtime failure, placing responsibility for correctness on the modeling phase.
The paper leaves open whether the FAOP approach can handle the full diversity of real‑world agent workflows, especially those that involve dynamic tool discovery or unpredictable environmental feedback, without sacrificing the static guarantees it provides.