Skip to content

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

Sep 2026 · arXiv.org · Vol abs/2609.18820 · 1 citation · 22 references
Computer Science

TL;DR

A provenance-aware runtime architecture is introduced that evaluates policies over complete execution traces, recomputing guarded quantities from raw provenance rather than the pipeline's derived representation, and shows that the correct repair for each class is dictated by where the guarded quantity mutates.

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.

View source

Similar papers

ActGov: Governing LLM Agent Actions via Policy-Constrained Validation

It is demonstrated that ActGov can enforce fine-grained authorization over dynamic agent executions without relying on the underlying LLM to correctly identify malicious instructions, significantly outperforming existing defenses.

Kai-Yuan Zhang, Yu-Ke Peng, Ke Jiang et al. · 1 citation · ⚡1
#natural language process... Preprint Aug 2026

PolicyGuide: From Guarding One Action to Guiding the Whole Workflow for Policy-Compliant LLM Agents

PolicyGuide compiles each domain policy into a workflow graph and invokes a proactive verifier at user-turn boundaries and finds the lowest observed attack-success rate under adversarial users and the strongest procedural compliance in an author-designed workflow-level validation.

Seongjae Kang, Taehyung Yu, Sung Ju Hwang · 2 citations
#artificial intelligence Preprint Aug 2026

STAGE: Stateful Translation to Agentic Graph Execution with Policy-Scoped Context and Deterministic Control

STAGE, an executable-graph framework that confines model judgment to policy-scoped nodes while placing procedural control in deterministic code, improves task success and repeated-run reliability compared with monolithic full-policy execution.

Mengxi Luo, Changjiao Chen, An Cao et al. · 1 citation
#artificial intelligence Preprint Oct 2026

Multi-Aspect Runtime Verification for Simulation-Based V&V of LLM-Enabled Autonomous Agents

A multi-aspect runtime-verification framework that decomposes a natural-language policy clause into a typed spatial/temporal/semantic triple over one canonical event stream, checks each aspect with its own monitoring specification, and fuses the verdicts through a four-valued algebra that carries provenance.

Nikolaos Kekatos, Dimitrios Nikou, Anastasios Temperekidis et al. · 0 citations
Preprint Aug 2026

A Contract-Centered Architecture for Scalable and Manageable Agentic Runtimes

A contract-bounded runtime architecture, a source-preserving data substrate, and a falsifiable measurement protocol are contributed, which proposes a cluster-period randomized crossover experiment with a four-state verdict: supported, falsified, conditional-engineering, or inconclusive.

Ya-Xiao Liu, Peng Liu, Yi-Wen Liu et al. · 0 citations
Sep 2026

Runtime Authorization Consistency Checking for MCP-based Agentic Workflows

Agentic systems increasingly fulfill user requests through multi-step tool workflows over files, services, and external resources. In these workflows, isolated per-call checks can miss a workflow-level failure: each call may be locally admissible, but the sequence can exceed the authorization boundary established for t...

Ai-Yao Zhang, Xiao-Dong Lee, Zhi-Xian Zhuang et al. · 0 citations

Related blog posts

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.