Soteria: Formally Verified Planning with Runtime Enforcement for Safe LLM Agents
Organizations: Princeton University · Snowflake
Abstract
LLM agents that execute multi-step tool calls must satisfy two objectives simultaneously: completing the user's task (utility) and conforming to domain policies and correctness constraints (safety). These objectives are in tension -- blocking an unsafe action prevents a violation but can leave the agent stranded with no principled way to recover. Existing approaches sacrifice one objective for the other. We introduce Soteria, a framework that reconciles safety and utility through verified hierarchical planning and runtime enforcement of specifications. Before execution, the agent generates a structured plan that is formally verified against the specifications prior to any tool invocation. During execution, the verified plan serves dual roles: it ensures that the agent takes specification-conformant trajectories and provides guidance when unsafe actions are blocked. Across multiple benchmarks covering a diverse range of tool-use tasks, Soteria achieves 1.7 times the average task success rate of the best baselines, with no violations of policy specifications, demonstrating that safety and utility need not be traded off.
Figures & tables
| Policy Rule | Formalized Specification |
|---|---|
| Check flown status before cancelling. | |
| Refund must derive from reservation. |
| -Airline | -Retail | Toolathlon | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Model | Method | Util. Succ. | Conf. | #Viol. | Cost | Util. Succ. | Conf. | #Viol. | Cost | Util. Succ. | Conf. | #Viol. | Cost |
| GPT 5.4-mini | No Guardrail | 48.0 34.0 | 64.0 | 29 | 0.031 | 27.2 20.2 | 86.0 | 25 | 0.036 | 11.6 2.3 | 41.9 | 42 | 0.045 |
| NeMo | 46.0 40.0 | 76.0 | 23 | 0.036 | 28.1 18.4 | 87.7 | 28 | 0.038 | 4.7 0.0 | 86.0 | 16 | 0.026 | |
| AgentSpec | 60.0 50.0 | 84.0 | 8 | 0.032 | 23.7 19.3 | 85.1 | 17 | 0.035 | 2.3 0.0 | 93.0 | 8 | 0.027 | |
| ABC | 54.0 48.0 | 90.0 | 5 | 0.033 | 19.3 15.8 | 85.1 | 17 | 0.037 | 11.6 2.3 | 86.0 | 16 | 0.324 | |
| Soteria (ours) | 60.0 | 100.0 | 0 | 0.125 | 35.1 | 100.0 | 0 | 0.154 | 11.6 | 100.0 | 0 | 0.033 | |
| Components | GPT 5.4-mini | Gemini 3 Flash | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Configuration | Verif. | Guard | Util. Succ. | Conf. | #Viol. | Cost | Util. Succ. | Conf. | #Viol. | Cost |
| Base (flat plan) | ✗ | ✗ | 54.0 44.0 | 74.0 | 13 | 0.102 | 58.0 32.0 | 54.0 | 27 | 0.112 |
| + Verification | ✓ | ✗ | 56.0 46.0 | 80.0 | 10 | 0.150 | 56.0 32.0 | 56.0 | 24 | 0.150 |
| + Sub-plans | ✓ | ✗ | 54.0 50.0 | 80.0 | 12 | 0.149 | 62.0 38.0 | 58.0 | 22 | 0.120 |
| Soteria (+ SpecMonitor) | ✓ | ✓ | 60.0 | 100.0 | 0 | 0.125 | 62.0 | 100.0 | 0 | 0.134 |
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
| Rule | Condition | Effect |
| Call | ; approved; executes; post holds | Execute tool, update , advance state |
| Call-Rejected | ; approval denied | Clear ; feed rejection reason back |
| Post-Fail | ; executes; post violated | (abort — unsound contract) |
| Exec-Fail | ; execution error | Clear ; feed error back; LLM retries |
| Drop | ; ; LLM calls a tool | Suppress the call silently |
| Step | ; LLM output has no tool call | Consume input; append to |
| Step | Rule | State | LLM action | Result / Effect | Next state |
| 1 | Invoke | lookup | Get-Resv("RES123") | lookup | |
| 2 | Call | lookup | (pending) | check_flown | |
| 3 | Inv-Guard | check_flown | Cancel-Resv("RES123", "other") | blocked ; error fed back | check_flown |
| 4–5 | Invoke + Call | check_flown | No-Flown("RES123") | check_age | |
| 6–7 | Invoke + Call | check_age | Hours-Diff(...) | check_rules | |
| 8 | (guard) | check_rules | — | do_cancel |
| Model | API Identifier |
|---|---|
| GPT-5.4-mini | openai/gpt-5.4-mini |
| Gemini 3 Flash | openrouter/google/gemini-3-flash-preview |
| Claude Haiku 4.5 | anthropic/claude-haiku-4-5 |
| Claude Opus 4.6 | anthropic/claude-opus-4-6 |
| Method | Conformance-gated Utility (%) | 95% CI | Conformance (%) | #Viol. |
|---|---|---|---|---|
| Soteria | ||||
| AgentSpec | ||||
| NeMo | ||||
| No Guardrail |
| Model | Planner cost/turn ( $) | Executor cost/turn ( $) | Planner time/turn (s) | Executor time/turn (s) | ||||
|---|---|---|---|---|---|---|---|---|
| P50 | P75 | P99 | P50 | P75 | P99 | |||
| GPT-5.4-mini | 0.53 | 1.44 | 7.95 | 0.93 | 1.15 | 2.12 | ||
| Gemini 3 Flash | 0.42 | 0.88 | 4.67 | 0.87 | 1.13 | 2.24 | ||
| Haiku 4.5 | 1.83 | 3.03 | 7.02 | 0.62 | 1.32 | 1.81 | ||
| Opus 4.6 | 2.67 | 5.04 | 7.84 | 1.56 | 2.07 | 2.34 | ||
| Domain | Category | # | Example |
| -Airline (24 total) | Cancellation | 2 | Allowed only if within 24 hrs, airline-cancelled, business, or insured |
| Modification | 5 | Basic economy cannot be modified; cannot remove bags | |
| Booking | 7 | All payments must come from user profile; 3 gift cards | |
| Compensation | 4 | Amount must be \times50 passengers (delayed) | |
| Data flow | 3 | Reservation ID passed to cancel or modify must match prior lookup | |
| Transfer | 3 | Must verify flown status before transferring to human agent |
LLM Agent Safety
Large language model agent safety studies how to keep tool-using, persistent, and multi-agent systems aligned with user intent and authorized limits.
See all 358 papers