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

arXiv: https://arxiv.org/abs/2609.18820 · HTML: https://mlsanity.com/paper/2609.18820/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Agent threats, guardrails and governance, one of 16 directions in LLM agents and tool use.
- Builds on 12 of its 22 references that are in the map.
- First posted on arXiv 16 Sep 2026.

## Placed in

- LLM agents and tool use / [Agent threats, guardrails and governance](https://mlsanity.com/agents/agent-threats-guardrails-and-governance/)

## Builds on (most cited first, 12 of 12)

- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Llama Guard: LLM-based Input-Output Safeguard for Human-AI Conversations](https://mlsanity.com/paper/2312.06674/) (2023)
- [Why Do Multi-Agent LLM Systems Fail?](https://mlsanity.com/paper/2503.13657/) (2025)
- [NeMo Guardrails: A Toolkit for Controllable and Safe LLM Applications with Programmable Rails](https://mlsanity.com/paper/2310.10501/) (2023)
- [AgentSpec: Customizable Runtime Enforcement for Safe and Reliable LLM Agents](https://mlsanity.com/paper/2503.18666/) (2025)
- [Constitutional Classifiers: Defending against Universal Jailbreaks across Thousands of Hours of Red Teaming](https://mlsanity.com/paper/2501.18837/) (2025)
- [The Flaws of Policies Requiring Human Oversight of Government Algorithms](https://mlsanity.com/paper/2109.05067/) (2021)
- [CIMemories: A Compositional Benchmark for Contextual Integrity of Persistent Memory in LLMs](https://mlsanity.com/paper/2511.14937/) (2025)
- [SafetyDrift: Predicting When AI Agents Cross the Line Before They Actually Do](https://mlsanity.com/paper/2603.27148/) (2026)
- [Semantic Intent Fragmentation: A Single-Shot Compositional Attack on Multi-Agent AI Pipelines](https://mlsanity.com/paper/2604.08608/) (2026)
- [Cross-Session Threats in AI Agents: Benchmark, Evaluation, and Algorithms](https://mlsanity.com/paper/2604.21131/) (2026)
- [When Summaries Distort Decisions: Information Fidelity in LLM-Compressed Financial Analysis](https://mlsanity.com/paper/2606.29251/) (2026)

## Abstract (arXiv)

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.