A Policy Algebra for Trust-Preserving Agentic AI Execution

Bhaskar Tripathi; Anurag Kumar; Ramendra Kumar; Bhavesh Gadhe

cs.AIAug 17, 2026

A Policy Algebra for Trust-Preserving Agentic AI Execution

Authors: Bhaskar Tripathi, Anurag Kumar, Ramendra Kumar, Bhavesh Gadhe

Organizations: Volkswagen Digital Services · Scania CV AB

Abstract

Large language model-based agentic frameworks primarily optimize capability: whether an agent can reason, retrieve information, call tools, delegate work, and complete a goal. Enterprise execution requires a stronger property. A successful result is not reliable if it was produced through unauthorized data access, widened delegated authority, unapproved side effects, unrecoverable budget consumption, or incomplete evidence. This paper defines reliable capability as a path property: an agent is reliably capable only when it completes a task through action events that remain admissible under identity, profile, tool, data, memory, budget, artifact, approval, and audit constraints. We propose a policy algebra that defines the reliability envelope within which agent capability may be exercised. Security profiles and runtime obligations compose through joins, intersections, budget narrowing, approval inheritance, and evidence accumulation; the resulting composition is both trust-preserving and the least restrictive state satisfying all governing inputs. The algebra also propagates restrictions across multi-agent calls and introduces cost-aware artifact materialization, which redirects open-ended execution toward a recoverable outcome as budget exposure grows. The evaluation is interpreted as a reliability-capability trade-off rather than a capability benchmark: the policy-algebra runtime intervenes on 94.8% of policy-violating events while retaining an 86.9% task-completion rate, eliminates the observed profile-monotonicity and zero-artifact-exhaustion violations, and increases audit completeness to 98.6%. The method provides researchers and practitioners with formal correctness conditions, executable decision semantics, and trace evidence for building agents that are not only capable, but reliably capable.

Figures & tables

Panel of Figure 1 — Figure 1: From output safety to action-path reliability. A chatbot-style assessment can focus on the final answer, but an agentic system must govern each reasoning-to-action transition. The proposed policy algebra admits actions only when identity, role, profile, data, memory, tool, budget, outcome, human-approval, and audit predicates jointly hold, thereby preventing unsafe actions and zero-outcome budget exhaustion.

No.	Work or standard	Main focus and contribution	Gap addressed by this paper
1	OWASP AISVS [ 1 ]	AI security verification through testable control categories and levels	Action-level enforcement inside an agent loop
2	NIST AI RMF and GenAI profile [ 2 , 3 ]	AI risk governance through the Govern, Map, Measure, and Manage cycle	Runtime semantics for the risk cycle
3	MAESTRO [ 4 ]	Agentic threat modeling through layered analysis of agentic systems	Translation from layer finding to policy gate
4	MITRE ATLAS [ 5 ]	AI adversary tactics and techniques for AI systems	Runtime use of tactics as control requirements
5	Agentic Security Hub [ 6 ]	Aggregated standards, threats, components, architectures, and mappings	Compilation into executable runtime constraints
6	Agent and multi-agent systems foundations [ 19 , 20 , 21 , 22 ]	Autonomy, interaction, coordination, and multi-agent system design	Runtime security semantics for tool-using agentic systems

Table 1: Related work and gap addressed by this paper.

Panel of Figure 2 — Figure 2: Policy-algebra principles and runtime effects. The algebra maps governance principles to monotone operators over profile, tool authority, memory scope, budget, artifact materialization, approval, and evidence obligations, yielding runtime effects that preserve trust before each reasoning-to-action transition.

Panel of Figure 3 — Figure 3: Runtime enforcement flow for the policy algebra. Standards, threat findings, enterprise context, and runtime metadata are compiled into a monotone policy state. Each proposed action is admitted only when the identity, role, profile, data, memory, tool, budget, artifact-materialization, approval, and audit predicates jointly hold; denials, approvals, redirects, and executions all emit trace evidence for repair and regression testing.

No.	Profile	Models/tools	Memory/data	Approval	Audit/budget
1	Low	Safe defaults; built-in tools	Short-lived memory; no sensitive RAG	None by default	Basic logs
2	Medium	Approved models/tools; limited connectors	Retention, redaction, classified RAG	Destructive actions	Tool parameters, costs, per-run budget
3	High	Whitelisted tools/connectors	Limited memory; vector decay; strict classes	External side effects and writes	Step traces, rate limits, anomaly detection
4	VeryHigh	Deterministic tools for regulated actions	Sanitized knowledge only; strict retention	All regulated/external actions	Immutable evidence, fixed budgets, alerts

Table 2: Security profile semantics used by the runtime.

No.	Component	Implementation status
1	Security profiles and cascade	Implemented in configuration and UI; formal semantics defined in ( 15 )
2	Policy-intersected tool authorization	Implemented in permission gate and executor paths
3	Trust boundary propagation	Implemented for profile and depth; formal verification remains future work
4	Human approval inheritance	Implemented for core paths; asynchronous workflow queues under development
5	RAG and memory governance	Classification and access checks exist; advanced cross-session retention remains partial
6	Publication profile freezing	Implemented using publication snapshots and review triggers

Table 3: Reference implementation status.

No.	Threat	Layers	AISVS categories	Components	Runtime controls	Audit evidence
1	Memory poisoning	Data, framework, observability	C8, C12	Memory, RAG, tools	Save/publish/run validation; retrieval audit; classification; retention limits	Source ID, classifier result, retrieval hash, action result
2	Tool misuse	Tools, runtime	C5, C9, C12	Tool integration, runtime	Intersected permission; sandbox; schema validation; HITL	Tool, params hash, policy predicates, approver, cost
3	Privilege compromise	Framework, ecosystem	C5, C9, C10	Orchestration, runtime	RBAC; cascade; monotone trust; depth limits	Caller, callee, profile join, denied/escalated reason
4	Resource overload	Runtime, observability	C12	Runtime	Token/cost budgets; rate limits; loop controls	Budget before/after, rate decision, loop counter
5	Overwhelming HITL	Framework, ecosystem	C13	Orchestration	Risk-adaptive approval; batching; deterministic tools	Approval queue state, decision latency, approver
6	Unexpected RCE	Tools, runtime	C4, C5, C9	Tool integration, runtime	Sandbox; command allowlist; network blocking	Command hash, sandbox ID, network policy, result

Table 4: Threat-to-control mapping with explicit runtime controls and audit evidence.

Panel of Figure 4 — Figure 4: Conformance evaluation and repair protocol for governed agents. The evaluation maps security artifacts to executable controls, exercises conformance traces, measures decisions and evidence, and converts failed traces into stronger gates and regression cases. Event-level details such as trace identifier, decision, failed predicate, profile, tool or service, approval state, budget, and latency are recorded in the trace rather than crowded into the diagram.

Research question	Hypothesis	Metric, equation, or evidence	Evaluation location
RQ1	H1: Coverage	$\mathrm{Coverage}(F,C)$ in Eq. ( 34 ); design-coverage matrix	Section 9
RQ2	H2: Compilation	$\mathrm{mapped}(f_{i})$ in Eq. ( 33 ); runtime predicate, gate, audit-field, profile-floor, or regression-test mapping	Section 9
RQ3	H3: Tool control	Unsafe intervention rate and false intervention rate in Eq. ( 35 ) and Eq. ( 36 ); governed tool-call protocol	Section 10 ; Section 11
RQ4	H4: Delegation	Trust violation rate in Eq. ( 37 ); profile-monotonicity violations	Section 10 ; Section 11
RQ5	H5: Evidence	Audit completeness in Eq. ( 38 ); trace reconstruction fields	Section 11
RQ6	H6: Artifact materialization	Zero-artifact exhaustion rate; materialization redirects and artifact-state evidence	Section 10 ; Section 11

Table 5: Mapping from research questions and hypotheses to evaluation evidence.

No.	Artifact family	Coverage criterion	Runtime control path
1	AISVS categories	Each category maps to an enforcement or audit surface	Profile rules, input validation, output filtering, memory policy, tool gate, audit schema
2	NIST AI RMF functions	Each function maps to a lifecycle or runtime mechanism	Governance cascade, asset mapping, monitoring, policy repair
3	MAESTRO layers	Each layer maps to one or more runtime controls	Model gateway, RAG gate, tool gate, sandbox, observability, trust chain
4	T1–T15 threat classes	Each threat maps to a control, evidence field, and test case	Threat-to-control matrix, profile floor, HITL, monitoring, trace field
5	KC1–KC6 components	Each component maps to scoped runtime constraints	Model, orchestration, memory, tool, and operational policies
6	Agent architecture patterns	Each pattern maps to profile floors and delegation constraints	Sequential, hierarchical, swarm, reactive, and RAG agent policies

Table 6: Preliminary design coverage of security artifacts by runtime controls.

No.	Invariant	Formal condition	Runtime mechanism
1	Profile monotonicity	$p_{i}\preceq p_{i\rightarrow j}$ for delegated execution	Profile cascade and profile join
2	Tool authorization	$\mathsf{Permit}(\tau,\theta,c)=1$ before execution	Intersected permission gate
3	HITL inheritance	$H_{i\rightarrow j}(a)=H_{i}(a)\lor H_{j}(a)$	Approval propagation over the call chain
4	Budget narrowing	$B_{i\rightarrow j}\leq B_{i}$	Budget attribution and sub-budget allocation
5	Artifact materialization	$\mathsf{Materialize}(\xi_{t},C_{t},B_{p_{0}},Q_{t})=1$	Cost-governance and artifact-state gate
6	Publication freeze	$p_{\mathrm{publication}}$ participates in $p_{\mathrm{eff}}$ until review	Published service profile snapshot

Table 7: Preliminary evaluation of policy-algebra invariants.

No.	Scenario	Targeted rule	Expected decision	Evidence field
1	Prompt injection calls blocked tool	Eq. ( 16 )	Deny	Failed predicate
2	Medium agent invokes Very High service	Eq. ( 15 ); Eq. ( 19 )	Deny or run at stricter profile	Effective profile
3	Sub-agent widens tools	Algorithm 3	Deny	Delegated tool set
4	External app calls unpublished service	$\sigma$ in Eq. ( 16 )	Deny	Service status
5	Sensitive data enters RAG context	Eq. ( 17 )	Deny retrieval	Data class and clearance
6	Memory poisoning attempt	Eq. ( 18 )	Deny write	Provenance and redaction

Table 8: Runtime evaluation protocol and expected outcome.

Panel of Figure 5 — Figure 5: Composition of the runtime-evaluation workload. Each horizontal bar partitions the action events in a workload family into unsafe and safe events; the annotation at the right reports the number of multi-step traces from which those events were obtained.

Workload family	Traces	Events	Unsafe events	Safe events
Prompt-injection and tool-misuse tasks	154	491	245	246
RAG and memory-governance tasks	137	438	202	236
Multi-agent delegation tasks	121	386	162	224
Publication and service-invocation tasks	88	281	108	173
Budget, artifact-materialization, HITL, and sandbox tasks	112	340	125	215
Total	612	1,936	842	1,094

Table 9: Runtime-evaluation workload.

Panel of Figure 6 — Figure 6: Security, utility, and runtime trade-offs between the RBAC-and-allowlist comparator and the policy-algebra runtime. Panel (a) compares percentage outcomes, Panel (b) shows the two residual governance-failure counts, and Panel (c) reports median and P95 authorization latency. Separate panels preserve the units and directionality of the underlying measures.

Metric	RBAC + allowlist	Policy algebra	Difference	Target direction
Unsafe intervention rate	67.1%	94.8%	+27.7 pp	Higher is better
False intervention rate	2.1%	4.2%	+2.1 pp	Lower is better
Profile monotonicity violations	31/188	0/188	-31	Lower is better
Zero-artifact budget exhaustions	18/44	0/44	-18	Lower is better
Audit completeness	71.9%	98.6%	+26.7 pp	Higher is better
Task completion rate	90.7%	86.9%	-3.8 pp	Higher is better

Table 10: Runtime-enforcement results.

Panel of Figure 7 — Figure 7: Unsafe-action intervention profile by scenario. Blue segments show the share of unsafe events denied, escalated, restricted, or redirected by the proposed runtime, while red segments show residual unrestricted allows. Parentheses report the intervened and unsafe event counts used to compute each rate.

Scenario	Unsafe events	Intervened	Intervention rate	Main residual failure mode
Prompt injection triggers blocked tool	133	126	94.7%	Ambiguous tool intent
Unauthorized tool execution	112	104	92.9%	Incomplete tool metadata
RAG over-access	116	111	95.7%	Misclassified document label
Memory poisoning write	86	79	91.9%	Semantic poisoning not caught by exact filter
Profile laundering through sub-agent	104	104	100.0%	None observed
External side effect without HITL	128	121	94.5%	Missing action-risk tag

Table 11: Unsafe-action intervention by scenario type for the proposed runtime.

No.	Failed case	Repair action	Regression case
1	Unsafe tool allowed	Add tool profile floor and HITL rule	Re-run blocked tool-call test
2	Profile downgrade in delegation	Enforce profile join on call chain	Re-run delegation test
3	Unauthorized document retrieved	Restrict RAG source and add classification check	Re-run RAG access test
4	Missing audit field	Add required field to audit schema	Re-run audit completeness test
5	Published service changed profile	Require re-approval before invocation	Re-run publication-freeze test
6	Budget exhausted without artifact	Lower materialization threshold and require checkpoint	Re-run artifact-materialization test

Table 12: Policy repair actions after failed evaluation cases.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
$G$	Set of agents.
$T$	Set of tools.
$D$	Set of data sources or data objects.
$V$	Set of published services.
$\mathcal{P}$	Set of security profiles.
$p\vee q$ or $p\sqcup q$	Profile join, equal to the stricter profile under the profile order.

Appendix

Table A1: Summary of notation used in the paper and appendices.

Dimension	Low	Medium	High	Very High
Models	Approved general models	Approved models with logging	Restricted models	Restricted models; deterministic tools for regulated action
Tools	Built-in low-risk tools	Approved tools	Tool calls require stricter validation	Deterministic or schema-bound tools
Memory	Short-lived	Scoped with retention	Scoped, redacted, audited	Minimal retention; strong isolation
RAG	Public or low-risk sources	Approved internal sources	Classified sources with provenance	Sanitized sources only; stronger review
HITL	None by default	Destructive actions	External side effects and high-risk writes	Most external actions
Budget	Basic run limit	User/team budget	Strict budget and rate limit	Fixed budget and approval for increase

Appendix

Table A2: Profile dimensions and representative runtime interpretation.

No.	Artifact	Example category	Runtime effect	Evidence
1	AISVS	Access control	RBAC predicate, data-source access check, service invocation check	Role, resource, decision
2	AISVS	Agentic action security	Tool authorization, HITL, sandbox, schema validation	Tool, parameters, decision
3	AISVS	Memory/vector security	$\mathsf{Read}_{p}$ , $\mathsf{Write}_{p}$ , retention, redaction, isolation	Source, memory key, class
4	AISVS	Monitoring	Trace completeness, anomaly detection, alerts	Trace ID, metric
5	NIST	Govern; accountability	Owner, reviewer, profile floor, approval path	Owner, approver
6	NIST	Map; context and assets	Agent inventory, tool list, data classification map	Asset ID

Appendix

Table A3: Detailed crosswalk from external security artifacts to executable runtime effects and evidence.

AI Agent Reliability

AI agent reliability studies whether tool-using systems act correctly, consistently, safely, and recoverably across changing tasks and environments.

See all 339 papers

Apr 18, 2026

Beyond Task Success: An Evidence-Synthesis Framework for Evaluating, Governing, and Orchestrating Agentic AI

Agentic AI systems plan, use tools, maintain state, and act across multi-step workflows with external effects, meaning trustworthy deployment can no longer be judged by task completion alone. The current literature remains fragmented across benchmark-centered evaluation, standards-based governance, orchestration architectures, and runtime assurance mechanisms. This paper contributes a bounded evidence synthesis across a manually coded corpus of twenty-four recent sources. The core finding is a governance-to-action closure gap: evaluation tells us whether outcomes were good, governance defines what should be allowed, but neither identifies where obligations bind to concrete actions or how compliance can later be proven. To close that gap, the paper introduces three linked artifacts: (1) a four-layer framework spanning evaluation, governance, orchestration, and assurance; (2) an ODTA runtime-placement test based on observability, decidability, timeliness, and attestability; and (3) a minimum action-evidence bundle for state-changing actions. Across sources, evaluation papers identify safety, robustness, and trajectory-level measurement as open gaps; governance frameworks define obligations but omit execution-time control logic; orchestration research positions the control plane as the locus of policy mediation, identity, and telemetry; runtime-governance work shows path-dependent behavior cannot be governed through prompts or static permissions alone; and action-safety studies show text alignment does not reliably transfer to tool actions. A worked enterprise procurement-agent scenario illustrates how these artifacts consolidate existing evidence without introducing new experimental data.

Christopher Koch, Joshua Andreas Wellbrock

Independent Researcher

LLM Agent Orchestration AI Agent Evaluation AI Agent Safety AI Agent Governance

Ask PDF

Sep 9, 2026

AgentAudit: An Open, Extensible Framework for Full-Lifecycle Trust Evaluation of AI Agents

Existing evaluation frameworks mostly assess only one part of AI agents, such as task completion (AgentBench) or security robustness (AgentDojo, ASB), rather than the complete pipeline of planning, tool selection, tool execution, memory and reasoning. Failures can occur at any stage, yet existing benchmarks rarely identify their precise source. AgentAudit evaluates the entire execution trace across ten capability, grounding, security and behavioural dimensions, namely instruction integrity, planner, memory, tool selection, tool invocation, tool correctness, alignment, tool faithfulness, security and execution integrity, combined with behavioural classification and failure attribution to pinpoint the exact stage responsible for an observed failure. AgentAudit can evaluate any LLM-based AI agent, since it attaches to the agent instead of replacing it. It reads only the recorded execution trace and does not interfere with how the agent runs, so it places no constraint on the agent's internal implementation. We evaluate five language models (OpenAI GPT-5, Claude Sonnet 5, Sarvam 105B, Llama 3.3 70B and Gemini 2.5 Flash) across nine capability and adversarial tasks. Claude Sonnet 5 and GPT-5 obtain the highest mean Composite Trust Scores (95.1 and 80.6 out of 100, respectively), while Sarvam 105B, Llama 3.3 70B and Gemini 2.5 Flash trail substantially (57.6, 45.7 and 22.6). All traces were scored by a single fixed judge model, which was itself one of the evaluated models, a limitation discussed in Section VII.E. More importantly, models with similar task-completion behaviour can diverge sharply in trustworthiness, as several non-frontier models are repeatedly classified Unsafe_Compliance on adversarial tasks rather than merely failing them, a distinction that pass/fail benchmarks cannot surface.

Shrey Nag, Sachita, Abhishek Kumar Singh +2

TIET · IGDTUW · GTBIT +1

AI Agent Reliability AI Agent Auditing AI Agent Evaluation AI Agent Security

Ask PDF

Mar 18, 2026

A Trace-Based Assurance Framework for Agentic AI Orchestration: Contracts, Testing, and Governance

In Agentic AI, Large Language Models (LLMs) are increasingly used in the orchestration layer to coordinate multiple agents and to interact with external services, retrieval components, and shared memory. In this setting, failures are not limited to incorrect final outputs. They also arise from long-horizon interaction, stochastic decisions, and external side effects (such as API calls, database writes, and message sends). Common failures include non-termination, role drift, propagation of unsupported claims, and attacks via untrusted context or external channels. This paper presents an assurance framework for such Agentic AI systems. Executions are instrumented as Message-Action Traces (MAT) with explicit step and trace contracts. Contracts provide machine-checkable verdicts, localize the first violating step, and support deterministic replay. The framework includes stress testing, formulated as a budgeted counterexample search over bounded perturbations. It also supports structured fault injection at service, retrieval, and memory boundaries to assess containment under realistic operational faults and degraded conditions. Finally, governance is treated as a runtime component, enforcing per-agent capability limits and action mediation (allow, rewrite, block) at the language-to-action boundary. To support comparative evaluations across stochastic seeds, models, and orchestration configurations, the paper defines trace-based metrics for task success, termination reliability, contract compliance, factuality indicators, containment rate, and governance outcome distributions. More broadly, the framework is intended as a common abstraction to support testing and evaluation of multi-agent LLM systems, and to facilitate reproducible comparison across orchestration designs and configurations.

Ciprian Paduraru, Petru-Liviu Bouruc, Alin Stefanescu

University of Bucharest Romania · University of Bucharest & Institute for Logic and Data Science Romania

AI Agent Reliability LLM Agent Orchestration AI Agent Evaluation AI Agent Governance Runtime Enforcement for AI Agents Runtime Verification

Ask PDF

Abstract

AI Agent Reliability

Explore similar work

Beyond Task Success: An Evidence-Synthesis Framework for Evaluating, Governing, and Orchestrating Agentic AI

AgentAudit: An Open, Extensible Framework for Full-Lifecycle Trust Evaluation of AI Agents

A Trace-Based Assurance Framework for Agentic AI Orchestration: Contracts, Testing, and Governance