Compositional Policy Violations: When Step-Level Compliance Fails in Agentic AI Workflows

It defines a Compositional Policy Violation (CPV): every individual step satisfies the policy applied to it, yet the composed execution violates the workflow-level policy, with no specification breached and no component containing a bug. Existing guardrail systems (Llama Guard, NeMo Guardrails, Constitutional Classifiers, AgentSpec) enforce constraints over prompts, responses, turns, or individual actions; prior compositional-failure studies assume an adversarial actor deliberately fragmenting behavior, whereas this work studies non-adversarial compositional failures produced by independently scoped components in ordinary execution. Primarily conceptual and formal argumentation, illustrated with underwriting and purchasing examples (e.g., four exceptions reduced to one through normalization, deduplication, and materiality classification, so a three-exception escalation threshold is not triggered); no empirical evaluation or dataset is reported.

It presents a four-part taxonomy: Authority Creep, Threshold Laundering, Cumulative Sum Violation, and Context Collapse, which share the CPV structure rather than a common mechanism. The taxonomy is organized by the aspect of execution that becomes unsafe through composition: Authority Creep concerns who is entitled to decide; Threshold Laundering and Cumulative Sum Violation concern an accumulated quantity (the first has a gate placed too early, the second has no gate at the aggregate scope at all); Context Collapse concerns the representation on which the decision is made. Supported by step-by-step tabulated examples: in Threshold Laundering, $210K passes a $250K referral gate and a later in-window $75K claim brings the committed value to $285K; in a Cumulative Sum Violation, three $90 purchases each satisfy a $100 per-action limit while their $270 total exceeds a $250 daily limit; in Context Collapse, per-hop drift of 0.06, 0.08, and 0.07 accumulates to 0.19 and flips the decision from refer to accept.

It argues that the correct repair topology is dictated by where the guarded quantity mutates over the workflow, not chosen by design. Each class demands a different repair: Authority Creep requires tracing backward once from the decision point; Threshold Laundering requires re-evaluating the existing predicate on the committed state; Cumulative Sum Violation requires introducing a predicate at the aggregate's own scope that no step currently holds; Context Collapse requires reconstructing against the original submission rather than the intermediate summaries. Illustrated with a risk example: a single gate at step 1 sees risk = 0.79 and passes, then step 3 adds exposure the gate never observes and the value crosses 0.80, showing the gate enforced a point-in-time predicate while the governing policy specifies an invariant on the committed state.

It proposes a provenance-aware runtime detection architecture with four core stages and two design invariants. The stages are Provenance Ingestion and Normalization, State Reconstruction, Policy Evaluation, and Compositional Detection; the invariants are history-completeness (no violation verdict from a truncated or windowed view when policy semantics require the full trajectory) and recount-from-raw-provenance (composition gates must recompute guarded quantities from raw provenance under the policy's own semantic definition, never from the pipeline's transformed or derived representation). An architectural proposal, including a Sequence Analyzer whose checks follow each class's repair topology and a Violation Detector that maps findings to the CPV taxonomy; the authors also enumerate detector failure modes, including provenance loss, oracle dependence for subjective predicates, extraction error, partial and asynchronous observability, entity resolution, hidden state, and cost.

The work addresses organizations running agentic workflows in regulated settings, particularly those holding policies that are properties of a whole execution such as referral thresholds, authority limits, and review requirements; its taxonomy and repair topologies apply to purely sequential, correctly designed workflows with every local check in place, and the detection architecture assumes an ordered event log per workflow instance with raw provenance retained. It opens directions for further work, including standardized policy languages and semantic mappings between governance intent and workflow provenance, simulation testbeds and benchmarked datasets analogous to those in fairness and interpretability, efficient trajectory analysis and real-time provenance capture, and domain-specific instantiation and validation in regulated workflows.

A careful reader would still watch several open questions: recomputation of subjective predicates (such as whether an exception is material) requires an interpretation oracle, and if that oracle and the pipeline component that produced the violation are both language models reasoning from similar priors, they may reach the same judgement and the detector may see no discrepancy; provenance retention is a precondition rather than an implementation detail, since a transform that deletes suppressed evidence rather than marking it makes the violation undetectable in principle; extraction error, clock skew and out-of-order delivery in distributed execution, entity resolution errors, and hidden state not surfaced as events all weaken verdicts; and on cost, retaining raw provenance and recomputing guarded quantities at commit time scales with trace length and the number of gated quantities, with Context Collapse in particular approaching the cost of the un-automated decision itself. In addition, this is a fast parse in which figures (Figures 1 through 6) and tables (Tables 1 and 2) appear as textual descriptions, so readers needing the exact graphical detail should consult the original figures and tables.