Source-linked AI summary
Compositional Policy Violations: When Step-Level Compliance Fails In Agentic AI Workflows
Ashwini Kurady, Sri Sai Charith Grandhi, Rajesh Gupta, Sumit Kumar
TL;DR
Step-scoped checks can miss policy violations that arise only across a composed workflow. The paper formalizes CPVs, relates repairs to where guarded quantities mutate, and concludes that point-in-time checkpoint enforcement is structurally insufficient.
Problem
Step-level policies can be locally satisfied even when the composed workflow violates its governing policy, because the defect lies in how local specifications compose.
Source: §3 · p. 2Method
The paper formalizes CPVs, characterizes four violation mechanisms, derives repair topology from where guarded quantities mutate, and proposes reconstructing policy semantics from raw provenance.
Source: §3 · p. 2, §4 · p. 7, §7 · p. 10Results
Point-in-time checkpoint enforcement is structurally insufficient for compositional policy violations.
Source: §7 · p. 10Takeaways & Limitations
Repairs should target where the guarded quantity mutates rather than assume a single checkpoint placement fits every violation.
Source: §4 · p. 7For subjective predicates, sound recomputation requires an interpretation oracle independent of the pipeline and anchored to policy text.
Source: §5.6 · p. 9
Abstract
from arXiv · showhide
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.
1 Introduction
Regulated agentic workflows make decisions through sequences of specialized agents, but governance largely checks individual steps while organizational policies often depend on the complete execution. The paper defines this mismatch as a Compositional Policy Violation and distinguishes its structural nature from monitor inaccuracy.
1 Introduction
- Production workflows accumulate permissions, context, and prior determinations across specialized-agent hand-offs, so final routing depends on the full sequence.The paper describes deployed pipelines that ingest requests, enrich information, analyze it, and route decisions with designated human review.Source: §1 · p. 1
- Existing input-output classifiers, turn-level rails, and span-level evaluators check actions using only the state visible at each step.These mechanisms apply step-scoped predicates to prompts, responses, turns, or spans.Source: §1 · p. 1
- Referral thresholds, authority limits, and review requirements depend on workflow traces, so a locally compliant sequence can still violate policy without any component failing.A trace is the complete ordered record of workflow steps and the state each step produced.Source: §1 · p. 1
- A Compositional Policy Violation (CPV) is structural: even perfectly accurate step-level monitors cannot detect a violation whose evidence exists only in the composed execution.The issue is not imperfect calibration or insufficient monitor capability.Source: §1 · p. 1
- The paper identifies four CPV types and proposes repairs based on where the guarded quantity mutates, alongside a provenance-aware runtime architecture for detection.Trace-level monitoring itself is not presented as novel; the contribution is identifying this governance failure mode, characterizing its forms, and operationalizing detection.Source: §1 · p. 1
2 Related Work
Prior work addresses local safeguards, execution observability, process evaluation, and human oversight, but the paper describes a gap in governance over complete workflow trajectories.
2 Related Work
- Guardrail systems enforce constraints on prompts, responses, turns, or individual actions, rather than evaluating complete execution trajectories against workflow-level policies.The cited systems include Llama Guard, NeMo Guardrails, Constitutional Classifiers, and AgentSpec [4] [5] [8] [9].Source: §2 · p. 2
- Earlier compositional-failure studies examine adversarially fragmented behavior, whereas this paper studies ordinary execution by independently scoped components [10] [11] [12] [13].Those studies show orchestrated subtasks can pass individual classifiers while the combined plan violates security constraints [10].Source: §2 · p. 2
- Trace observability platforms reconstruct spans and runs but evaluate individual units, while process supervision and failure taxonomies analyze intermediate reasoning or failed executions [14].The paper distinguishes CPVs as workflows that complete successfully yet violate policy defined over the accumulated trajectory.Source: §2 · p. 2
- Human oversight is a common fallback in high-risk workflows, but cited studies report reviewer over-reliance on automated recommendations and declining effectiveness as automation increases [16].The paper motivates runtime mechanisms that reason over complete execution histories.Source: §2 · p. 2
3 Taxonomy
A Compositional Policy Violation occurs when every step passes its local check but the workflow violates a policy defined over the complete trace. The four types differ in what becomes unsafe through composition and therefore in what evidence a detector must retain.
3 Taxonomy
- CPVs are sequential workflows whose locally compliant steps collectively violate a workflow-level policy, with the decisive evidence absent from any single step.They are distinct from bugs, race conditions, or stale-state errors: no individual specification need be breached.Source: §3 · p. 2
3.1 Authority Creep Violation
- Authority Creep occurs when distributed judgment calls remove exceptions until the router receives a count that changes the required escalation decision.Correcting an objectively duplicated record is not Authority Creep; the key mechanism is discretionary interpretations that make exceptions disappear.Source: §3.1 · p. 3
Structural Preconditions
- A valid instance requires local compliance, a routing gate over a transformed representation, and displacement that no single transform causes by itself.The transform that crosses the threshold can depend on execution order, so the condition does not identify one culpable component.Source: Structural Preconditions · pp. 3–4
3.2 Threshold Laundering
- Threshold Laundering occurs when a gate correctly checks a quantity before later changes carry it past the limit without another check.Repair it by recomputing the committed total and applying the existing rule before binding; a late gate may not cover quantities finalized at different steps.Source: §3.2 · pp. 4–5
3.3 Cumulative Sum Violation
- A Cumulative Sum Violation occurs when individually compliant actions cross a policy threshold in aggregate, despite no gate evaluating that aggregate.Unlike Threshold Laundering, this pattern requires introducing an aggregate-scope predicate; the accumulated state may also combine heterogeneous signals.Source: §3.3 · pp. 5–6
3.4 Context Collapse Violation
- Context Collapse occurs when faithful hand-offs cumulatively lose decision-relevant information, so the reviewer sees a file that supports a different decision than the original submission.The proposed remedy is to retain the original submission and re-derive the decision from it before binding.Source: §3.4 · p. 6
4 Repair Topology is Dictated by Violation Structure
Repair topology follows where the guarded quantity mutates, and the detector must evaluate policy semantics over the complete trace and committed state. The paper illustrates this with threshold laundering and class-specific repairs, alongside an example where cumulative context drift flips a decision.
4 Repair Topology is Dictated by Violation Structure
- The correct number and placement of policy gates depend on where the guarded quantity changes, while detection requires evaluating the complete trace against the committed state.A collection of single-point checkpoints cannot reconstruct full policy semantics.Source: §4 · pp. 6–7
- 0.19 accumulated drift relative to the submission flips the decision from refer to accept, although each hop stays within the materiality tolerance.The table illustrates Context Collapse.Source: Table 2 · p. 7
- 0.79 risk passes the step-1 gate, but step-3 exposure pushes risk past 0.80; re-evaluate the existing predicate on the committed state.The governing policy is risk < 0.80 on the committed state, rather than at the earlier gate.Source: §4 · p. 7, Figure 5 · p. 7
- Authority Creep calls for backward tracing, Cumulative Sum Violation for an aggregate-scope gate, and Context Collapse for reconstruction against the original submission.Threshold Laundering instead requires re-evaluating the existing predicate on the committed state.Source: §4 · p. 7
5 CPV Detection Architecture
The detector evaluates policy over complete workflow traces through four detection stages, governed by history-completeness and recount-from-raw-provenance invariants. Its verdicts depend on retained provenance and have limits involving subjective predicates, extraction, observability, entity resolution, hidden state, and cost.
5.1 Stage 1: Provenance Ingestion and Normalization
- Runtime events are normalized into a canonical, timestamped trace while preserving provenance links and the complete execution history.The collector and normalizer retain events such as tool calls, approvals, retries, and handoffs.Source: §5.1 · p. 8
5.2 Stage 2: State Reconstruction
- The State Store preserves workflow state and raw provenance, while the Policy Knowledge Base supplies versioned policy semantics for reconstruction.Together, they enable the detector to reconstruct what policy requires at each decision point.Source: §5.2 · p. 8
5.3 Stage 3: Policy Evaluation
- Policy Evaluation checks both local step policies and trace-level policies, producing facts about locally compliant steps and policies violated by the complete trace.Its checks cover declarative policies, authority constraints, and separation-of-duty rules.Source: §5.3 · p. 8
5.4 Stage 4: Compositional Detection
- The Sequence Analyzer examines complete trajectories and applies class-specific checks to identify and classify violations that emerge across steps.Checks trace authority inputs, reevaluate guarded quantities on committed state, aggregate quantities across the trace, and re-derive decisions from retained submissions.Source: §5.4 · pp. 8–9
5.5 Operational Components
- Explainability, audit logging, and dashboards support review and governance workflows but do not contribute to CPV identification.The detector maps findings to CPV types, severity, and responsible workflow segments.Source: §5.5 · p. 9, §5.4 · p. 9
5 CPV Detection Architecture
- The four-stage detector preserves complete workflow history and recomputes guarded quantities from raw provenance, rather than relying on intermediate representations.History-completeness rules out verdicts from truncated views when policy semantics require the full trajectory.Source: §5 · p. 8, §5.5 · p. 9
5.6 Detector Failure Modes
- The detector cannot recover suppressed evidence absent from the trace; subjective predicates also require an independent interpretation oracle anchored to policy text.If pipeline and oracle models share similar priors, they may concur without detecting a discrepancy.Source: §5.6 · p. 9
- Full provenance does not eliminate extraction error, and incomplete observability, fragmented identities, hidden state, and recomputation costs constrain detection.Distributed execution, missing telemetry, or policy-relevant state carried outside surfaced events can weaken the reconstructed trajectory; cost scales with trace length and gated quantities.Source: §5.6 · p. 9
6 Future Research
Future work must address deployment costs and open questions about generalization, trust, and standardized policy-to-provenance mappings. The paper calls for benchmarks, efficient trajectory analysis, and domain-specific validation.
6 Future Research
- Production deployment requires trade-offs among storage, latency, and accuracy tailored to workflow volume and SLA requirements.Suggested approaches include tiered storage, batch versus streaming evaluation, and incremental state reconstruction.Source: §6 · p. 10
- Standardized governance frameworks remain absent, and transfer of the detector to lending, hiring, moderation, and other high-stakes domains is unclear.Remediation, accountability, and defenses against audit-trail obfuscation also remain open questions.Source: §6 · p. 10
- The research agenda includes standardized policy languages, simulation testbeds and benchmarks, more efficient trajectory analysis, and validation in regulated workflows.The stated aims include transparent detection across domains and bringing detection costs within operational feasibility.Source: §6 · p. 10
7 Conclusion
The conclusion frames CPVs as governance failures in which locally compliant steps compose into violations, and argues that checkpoint enforcement is structurally insufficient. It presents full-trace policy enforcement as foundational to detecting such violations in increasingly autonomous and compositional AI workflows.
7 Conclusion
- Compositional policy violations are a distinct governance failure: locally compliant steps can compose into trajectories that violate organizational, regulatory, or business policies.The paper formalizes four mechanisms, derives their repair topologies, and proposes a detector architecture based on reconstructing policy semantics from raw provenance.Source: §7 · p. 10