Soteria verifies an AI agent's plan before any tool call: zero violations across four models, 1.7 times the best baseline's task success
Synopsis
AI agents that make multi-step tool calls must finish the task and obey domain policy, and existing guardrails tend to trade one for the other. Soteria formally verifies the agent's hierarchical plan against tool contracts and policy specifications before any tool is invoked, then a runtime monitor blocks violating calls and the verified plan supplies an alternative path. On 207 tasks across three benchmarks and four backbone models, Soteria reached 100% conformance with zero violations and improved task success by 4.7 to 43.9 percentage points over each model's best baseline, 1.7 times on average.
Interpretation
Soteria puts safety and utility on one execution path: the agent hands over a formally verified plan before acting, and a blocked action can be rerouted through that plan. The two prior guardrail families each cover half the problem. LLM-based guardrails judge each action but are probabilistic and give no formal guarantee; specification-based monitors check preconditions, postconditions or trajectory invariants at runtime but offer no verified recovery plan when a call is blocked. On 207 tasks across three tool-calling benchmarks and four backbone models, Soteria reached 100% conformance with zero violations while baseline conformance topped out at 93%; for each model-benchmark pair, task success was 4.7 to 43.9 percentage points above the best baseline, 1.7 times on average.
Plans are written as guarded transition systems, graphs whose nodes are steps, whose edges are tool calls, and whose every edge carries a Boolean condition, so branching and data dependence become machine-checkable. Plans are composed from reusable sub-plans, each carrying a contract that states what inputs it expects and what result it guarantees, so a parent plan reasons about interfaces instead of re-encoding sub-plan internals. Verification conditions go to the Dafny automated verifier and check three properties: every tool call meets its precondition, the plan cannot get stuck at an intermediate state, and every execution trace satisfies all policy specifications; failed checks return targeted diagnostics and the planner repairs and re-verifies within a budget of 8 retries.
A runtime monitor checks preconditions and all specifications before each tool execution, blocks violating calls, and the executor then looks to the plan's remaining steps for an alternative action. Blocking still holds when verification was incomplete or when the executor deviates from the plan because of its stochastic nature; on a block, the plan is shown as a progressively simplified flowchart of remaining steps and guard conditions for the executor to reroute. On -Airline, the ablation for GPT-5.4-mini and Gemini 3 Flash shows that adding the monitor brings both models to 100% conformance with zero violations, with success equal to raw utility (60% and 62% respectively) because no utility is lost to violations.
Perspective
The demonstrated scope is 207 tasks on three tool-calling benchmarks: 50 in -Airline, 114 in -Retail, and 43 of 108 in Toolathlon, covering terminal interaction, filesystem management and document editing, with four backbone models at temperature 0 and a single attempt per task. Specifications come from semi-automated formalization of policy documents plus manual validation, yielding 24, 33 and 41 formulas for the three domains.
Verification soundness rests on two assumptions: tool contracts faithfully model tool behavior, and runtime postconditions hold; if a postcondition fails, execution aborts because plan-verification results can no longer be trusted. Plans must be acyclic, and plans with back edges are rejected. The automated theorem provers support limited first-order theories and may not complete verification in practice; specifications still need manual validation, and the sub-plan library is generated with LLM assistance and iterative verification.
