Compositional Policy Violations: When Step-Level Compliance Fails In Agentic AI Workflows
Ashwini Kurady, Sri Sai Charith Grandhi, Rajesh Gupta (RunCtrl) and Sumit Mamoria define Compositional Policy Violations, cases where every step of an agentic workflow passes its own check while the full execution violates an organizational policy, and propose runtime checks over complete execution traces.
Ask this paper
Why step checks miss it: Policies such as referral thresholds, authority limits and review requirements are properties of the whole execution, so a predicate over one step cannot evaluate them, however accurate the step-level monitor is.
Four types: The taxonomy covers Authority Creep, Threshold Laundering, Cumulative Sum Violation and Context Collapse.
Repair location: The correct fix for each type is determined by where the guarded quantity changes during the workflow.
Provenance-aware runtime: The proposed architecture evaluates policies over the full trace and recomputes guarded quantities from raw provenance rather than from the pipeline's derived representation.
Abstract
Agentic workflows now make consequential decisions in regulated settings, and the governance placed around them is almost entirely step-scoped: input-output classifiers, per turn rails, and span-level evaluators. The policies organizations actually hold, such as referral thresholds, authority limits, and review requirements, are properties of the whole execution rather than of any one step. This mismatch admits a failure mode we call a Compositional Policy Violation (CPV): every individual step passes its own check while the composed execution violates the governing policy. A predicate over a single step cannot evaluate a property that step does not determine, so no improvement in the accuracy of the step-scoped monitors detects this class. We define CPVs as the failure of step-level compliance to compose, and present a taxonomy of four types: Authority Creep, Threshold Laundering, Cumulative Sum Violation, and Context Collapse. We show that the correct repair for each class is dictated by where the guarded quantity mutates. We then introduce a provenance-aware runtime architecture that evaluates policies over complete execution traces, recomputing guarded quantities from raw provenance rather than the pipeline's derived representation.