Soteria: Formally Verified Planning and Runtime Enforcement for Safe LLM Agents
Soteria: Formally Verified Planning with Runtime Enforcement for Safe LLM Agents
The authors propose SOTERIA: first formally verify hierarchical plans, then have SpecMonitor intercept violating tool calls at runtime; on 207 tasks and 4 models, they report 100% compliance and zero violations.
The victim system is an LLM agent that executes multi-step tool calls (in domains such as airline, retail, and terminal/file). The risk comes from the agent itself producing calls that violate domain policies or tool contracts (e.g., canceling an order without checking the flown status), rather than from an external attacker; the defense statically verifies the plan before execution, and at runtime SpecMonitor intercepts violating calls.
- When LLM agents execute multi-step tool calls, they must simultaneously complete tasks (utility) and comply with domain policies and tool contracts (safety), and there is tension between the two: after intercepting an unsafe call, agents often have no principled recovery path, and existing methods can only address one side.
- SOTERIA represents plans as guarded transition systems (GTS), composes hierarchical plans from reusable pre-verified subplans, and uses Dafny to statically verify tool contracts, progress and policy compliance; at runtime, SpecMonitor checks each call and intercepts violating calls, and when intercepted, the verified plan guides recovery.
- On 207 tasks across τ²-Airline, τ²-Retail and Toolathlon with 4 models, the authors report that SOTERIA achieves 100% compliance and zero violations, with success rates 4.7–43.9 percentage points higher than the best baseline for each model-benchmark pair; ablations show SpecMonitor is key to the compliance guarantee, and subplans raise the verification pass rate from 38/60 to 65/68.
- The authors note: specifications require semi-automatic formalization plus manual validation; verification assumes tool contracts are faithful and that runtime postconditions hold; the first-order theories supported by the theorem prover are limited and may not suffice to complete verification. The ablation is done only on two models on τ²-Airline, and the repeated-run experiments cover only τ²-Airline + GPT-5.4-mini.
- Evaluated models
- 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)
- Benchmarks
- τ²-Airlineτ²-RetailToolathlon
- Metrics
- UtilitySuccess rateConformance#ViolationsCost
The Soteria framework lets LLM agents balance safety and task utility through formally verified hierarchical planning and runtime enforcement. Before calling tools, the agent generates a structured plan and formally verifies it against specifications; during execution it both constrains the trajectory to comply with the specifications and provides recovery guidance when unsafe actions are blocked. On multiple tool-use benchmarks, Soteria's average task success rate reaches 1.7 times that of the best baseline, with no policy specification violations.
Paper analysis
What problem does this paper attempt to solve?
Enable LLM agents to guarantee that tool calls comply with domain policies and tool contracts without sacrificing task success rate.
Core question: how can an LLM agent executing multi-step tool calls simultaneously satisfy task completion (utility) and policy/contract compliance (safety), rather than sacrificing one for the other.
- Scenario and importance: the authors note that agents are being deployed in software engineering, customer service, enterprise automation, and other domains, where the real-world consequences of tool calls are hard to undo; for example, an airline agent canceling a booking without verifying passenger eligibility violates a policy specification, and a retail agent passing fabricated data to a downstream tool without first checking the order violates a tool data-flow specification.
- Shortcomings of existing methods (per the paper): LLM-based guardrails use a second model to judge actions one by one; they are easy to deploy but probabilistic and offer no formal safety guarantee; specification-based monitors check pre/postconditions or trace invariants at runtime, giving stronger guarantees, but after a call is intercepted there is no verified recovery plan, and earlier actions may already have left the agent in an unrecoverable state, so recovery harms utility.
- Core observation: the authors' key insight is that the agent can first construct a verified, specification-compliant plan before any tool is called, so that safety need not be traded for utility; the verified plan can also provide recovery guidance when a call is intercepted.
- Proposed approach: the SOTERIA framework—generate policy specifications, tool contracts, and subplans once from natural-language policy documents and tool definitions (LLM-assisted generation followed by manual validation); the planner composes reusable subplans into hierarchical plans and statically verifies them; at runtime SpecMonitor enforces interception of violating calls, and the plan serves as an execution roadmap and recovery guide.
- Threat model:
- Victim system: an agent driven by a backbone LLM that reads and writes the external environment (databases, files, messages, etc.) through tool APIs.
- Source of risk: the paper does not posit an external attacker; the risk is that the agent itself, due to randomness or planning errors, produces calls that violate policy specifications or tool contracts.
- Defender capabilities: the defender has access to domain policy documents and tool definitions, can verify plans before execution, and can intercept and check before each tool execution.
- Success criterion: execution must both bring the environment to the task's expected state (utility) and have all calls satisfy contracts and all policy specifications hold on the trace (conformance).
What related research exists?
Related work falls into three categories: LLM agent planning, runtime guardrails, and structured agent frameworks; the authors state that SOTERIA's combination did not exist previously.
Planning for LLM agents
- LLM+P (Liu et al., 2023)—delegates planning to a classical PDDL planner, yielding sound plans; the paper notes that it is limited to predicate states, lacks rich data types, and has no runtime enforcement.
- VeriPlan (Lee et al., 2025)—uses the PRISM model checker to check LLM-generated schedules against LTL constraints; the paper notes that its plans are flat linear step sequences without branching or conditional logic, and that there is no runtime enforcement or monitoring of the translated specifications.
- Plan-and-Solve (Wang et al., 2023) and Plan-and-Act (Erdogan et al., 2025)—separate planning from execution; the paper notes that they lack formal plan semantics and verification.
Runtime guardrails for LLM agents
- AgentSpec (Wang et al., 2025) and ProbGuard (Wang et al., 2026)—monitor tool calls with trigger-predicate rules, with ProbGuard additionally adding Markov-chain-based violation prediction.
- Agent-C (Kamath et al., 2025) supports temporal and data-flow constraints; Agent Behavioral Contracts (Bhardwaj, 2026) draws on design-by-contract, including preconditions, invariants, and governance constraints.
- NeMo Guardrails (Rebedea et al., 2023) and GuardAgent (Xiang et al., 2025)—use a second LLM for compliance checking; the paper notes that they inherit probabilistic failure modes. The paper overall notes that these methods monitor execution at runtime, do not statically verify structured plans before execution, and do not use such plans to guide recovery.
Structured agent frameworks
- ReAct (Yao et al., 2022) and Chain-of-Thought (Wei et al., 2023)—structured LLM reasoning; the paper notes that they do not produce externally verifiable artifacts.
- VeriMAP (Xu et al., 2025)—attaches LLM-generated assertions to a subtask DAG; the paper notes that its checks occur after execution and offer no formal guarantee.
- StateFlow (Wu et al., 2024) and LangGraph (LangChain, 2025)—organize agent workflows with state machines; the paper notes that they have no formal semantics usable for formal verification.
Baselines and benchmarks: the experiments compare four baselines—No Guardrail, NeMo Guardrails (Colang input rail with per-action LLM judging), AgentSpec (action-trigger-predicate rule monitoring), and ABC (behavioral contract runtime checking); the benchmarks are τ²-Airline, τ²-Retail (the τ²-bench suite), and Toolathlon.
Positioning: the authors state that SOTERIA combines a verifiable plan representation, static verification, and runtime enforcement, a combination that does not exist in prior work.
How does the paper address this problem?
Plans are represented as guarded transition systems and statically verified; at runtime, SpecMonitor intercepts violating calls and plan-guided recovery is used.
Overall approach: SOTERIA combines "hierarchical plans verified before execution" with "runtime specification enforcement"—the plan is formally verified before any tool call, serves both as a roadmap and as a recovery guide during execution, and SpecMonitor provides a backstop to guarantee compliance.
Specifications and formalization process
- Two kinds of specifications: tool contracts (precondition Pa and postcondition Qa for each tool, constraining a single call) and policy specifications (first-order logic formulas constraining tool call sequences, including temporal predicates ≺ and value-flow predicates ⇝; see Table 1 for examples).
- Formalization process: first use an LLM-based auto-formalizer to generate contracts and specifications from natural-language policies and tool definitions, then manually validate them item by item; the manual step performs a coverage check—every state-change rule that can be enforced on tool call traces maps to at least one specification. Validated specifications are reused across tasks in the same domain.
- Criteria for successful execution: utility (the environment reflects the task's expected outcome) plus conformance (all calls satisfy contracts, and all policy specifications hold on the trace).
Hierarchical plans and GTS representation
- Subplans: each standard procedure in the domain policy (e.g., cancel, refund, book) maps to a subplan with a contract, stating what inputs it expects and what it guarantees (the request is completed or safely rejected); subplans can be invoked like tools, and the planner only generates the top-level composition.
- GTS representation: plans are represented as Guarded Transition Systems—nodes are process stages, edges are tool calls, and each edge is gated by a guard (a Boolean condition over data collected during execution), making branching, ordering, and data dependencies explicit and machine-checkable.
- Plan DSL: the planner must write plans in the paper's DSL: declare typed plan variables, states marked with @state, transitions with at most one action per state, if/else guards, and terminal states divided into accepting (task complete) and halting (cannot safely continue); it also supports subplan invoke and llm_eval, which delegates unstructured reasoning to the LLM (Appendix A.2 gives the full grammar).
Static plan verification
- Three checks: tool contract satisfaction (each call satisfies preconditions), progress (the plan does not get stuck in intermediate states), and policy compliance (every possible execution trace satisfies all policy specifications); these are encoded as verification conditions (VCs) and given to Dafny for automatic verification.
- Symbolic state propagation: at each state s, maintain a symbolic state Σ(s) summarizing all values reachable from the initial state; for a transition from s to s′ with guard g, the propagation formula is Σs→ s′(s′) = δ(Σ(s) ∧ g), where δ conjoins the constraints introduced by the transition's action (assignments contribute v′ = e, tool calls contribute the tool's postcondition).
- Progress split into two: reachability (Σ(s) is satisfiable for every non-terminal state) and guard feasibility (for every non-terminal state, the disjunction of the guards on its outgoing edges is valid under Σ(s)).
- Policy compliance encoding: maintain ghost state—a monotonic step counter, a per-action call log, and a provenance map tracking the source of variable values; quantifiers are reduced to call-log indices, ≺ becomes a step-count comparison, ⇝ becomes a provenance membership check, and assertions are placed at every terminal state, holding for all paths.
- Modular verification: when verifying a parent plan containing subplan calls, treat subplans as tool calls with only contracts, without looking at internal logic.
- Repair and fallback: verification failure produces targeted diagnostics, and the planner repairs and re-verifies within a fixed retry budget (8 in the experiments); when full verification is impossible, it falls back to the strongest partially verified plan, with unverified specifications written as explicit warnings into the executor prompt.
Runtime enforcement
- SpecMonitor: before each tool execution, check preconditions, then concretely evaluate all relevant policy specifications on the current trace prefix plus the proposed call, and intercept before execution if violated; after the call executes, check postconditions and abort on failure (meaning the tool contract is unreliable). Specifications are indexed by category—safety (checked before execution)/liveness (checked at task completion)/irrelevant—and at runtime only concrete trace evaluation is done, without calling an SMT solver.
- Plan as guidance: the plan is presented to the executor as a worklist—a flowchart that simplifies step by step as tool results arrive, showing only remaining steps and guard conditions; the executor retains full autonomy in choosing tools. When intercepted, the executor uses the worklist to find an alternative branch, and falls back to its own reasoning when there is none.
- Strict mode: a PGAS strict plan enforcement mode is also supported, allowing only transitions whose guards and preconditions are satisfied, suitable for high-risk procedures where deviation is not allowed (Appendix A.4).
What experiments did the paper conduct?
207 tasks × 4 models: SOTERIA reports 100% compliance with zero violations, and a success rate 4.7–43.9 percentage points higher than the best baseline.
Experimental setup
- Models tested: GPT-5.4-mini, Gemini 3 Flash, Claude Haiku 4.5, Claude Opus 4.6, temperature 0.0, pass@1 (a single attempt per task), reasoning effort low (where applicable).
- Benchmarks and scale: τ²-Airline (50 tasks), τ²-Retail (114 tasks), Toolathlon (43 selected from 108 tasks, limited to the terminal interaction, file management, and document editing domains, evaluated via a local MCP server), 207 tasks in total.
- Baselines: No Guardrail, NeMo Guardrails, AgentSpec, ABC, all using the same backbone models, tools, and domain policy documents.
- Metrics: Utility (task completion rate as judged by the benchmark evaluator, not counting violations), Success (completed with no violations throughout), Conformance (proportion of tasks with zero violations), #Viol. (total number of violations), Cost (average API cost per task, USD).
- Evaluation protocol: the two τ² benchmarks are evaluated as multi-turn dialogue per the τ²-bench protocol, with the user simulator and the agent using the same model; Toolathlon is single-turn; at most 100 steps per task; SOTERIA's planning retry budget is 8.
- Specification scale: 24, 33, and 41 specifications are formalized for the three benchmarks respectively (98 in total), taking several hours per benchmark, mainly for reading policies and checking generated results (Appendix C.2).
Main results
Per Table 2 (each cell is Util.→Succ. / Conf. / #Viol.; for SOTERIA the two rates are equal, so only Succ. is listed):
Swipe horizontally to read the table
Model Method τ²-Airline τ²-Retail Toolathlon GPT-5.4-mini No Guardrail 48.0→34.0 / 64.0 / 29 27.2→20.2 / 86.0 / 25 11.6→2.3 / 41.9 / 42 GPT-5.4-mini Best baseline (ABC) 54.0→48.0 / 90.0 / 5 27.2→20.2 (No Guardrail) / 86.0 / 25 11.6→2.3 (No Guardrail/ABC) / 41.9 / 42 GPT-5.4-mini SOTERIA 60.0 / 100.0 / 0 35.1 / 100.0 / 0 11.6 / 100.0 / 0 Gemini 3 Flash Best baseline (ABC) 50.0→26.0 / 54.0 / 23 42.1→38.6 / 93.0 / 8 16.3→0.0 / 60.5 / 34 Gemini 3 Flash SOTERIA 62.0 / 100.0 / 0 45.6 / 100.0 / 0 16.3 / 100.0 / 0 Claude Haiku 4.5 Best baseline (No Guardrail) 58.0→30.0 / 58.0 / 28 38.6→31.6 / 88.6 / 16 16.3→4.7 / 55.8 / 33 Claude Haiku 4.5 SOTERIA 70.0 / 100.0 / 0 56.1 / 100.0 / 0 9.3 / 100.0 / 0 Claude Opus 4.6 Best baseline (NeMo) 70.0→54.0 / 82.0 / 11 53.5→46.5 (No Guardrail) / 87.7 / 17 30.2→11.6 (No Guardrail) / 55.8 / 34 Claude Opus 4.6 SOTERIA 88.0 / 100.0 / 0 90.4 / 100.0 / 0 18.6 / 100.0 / 0 Note: "best baseline" is selected by the highest Succ. for each model-benchmark pair, with the method name in parentheses; full numbers for NeMo and AgentSpec are in Table 2 and omitted here.
- Compliance: the authors report that SOTERIA achieves 100% compliance and zero violations on all model × benchmark combinations; the highest baseline is 93.0% for ABC + Gemini on τ²-Retail (still with 8 violations), and baseline violation counts on τ²-Retail range from 8 to 28.
- Success rate: the authors report that SOTERIA has the highest success rate on every model-benchmark pair, 4.7–43.9 percentage points above the best baseline for each pair (10–40 points higher on τ²-Airline, 7.0–43.9 points higher on τ²-Retail); the abstract and introduction summarize this as 1.7× on average.
- Exceptions: on Toolathlon, SOTERIA's success rate is only 9.3–18.6%, and Haiku 4.5's 9.3% is lower than GPT-5.4-mini's and Gemini's 11.6%/16.3%; high compliance does not equal high completion—all Gemini baselines on τ²-Retail have compliance above 90.0%, but success rates below 40.0%.
Component ablation (Table 3, τ²-Airline, 8 retries)
- What was tested: starting from a flat plan base, incrementally adding verification, subplans, and SpecMonitor, with GPT-5.4-mini and Gemini 3 Flash as models.
- Results: the flat plan already has 44% (GPT)/32% (Gemini) success rate, but with 13/27 violations; adding verification reduces violations to 10/24, with success rates of 46%/32%; adding subplans narrows GPT's utility-success gap (54→50), and Gemini's raw utility rises from 56% to 62%; adding SpecMonitor gives both models 100% compliance and zero violations, with success rate equal to raw utility (60%/62%).
- Authors' interpretation: SpecMonitor fully closes the gap between utility and success, because there is no longer any loss from violations.
Subplan ablation (Figure 6, τ²-Airline, GPT-5.4-mini)
- What was tested: the full system (subplan library) versus a variant that generates a single monolithic plan each round.
- Results: subplans reduce the median number of states per plan from 11 to 8; planning rounds that pass verification rise from 38/60 to 65/68, and the proportion passing verification on the first attempt rises from 23.3% to 48.5%; without subplans, failures are mainly specification failures and persist across retries, whereas with subplans, residual failures are mostly parsing and compilation errors.
- Authors' interpretation: decomposing policies into independently verified subplans reduces the planner's burden, enabling 95.6% of plans to pass verification within the retry budget.
Repeated runs and cost
- Repeated runs (Table 7, Appendix B.2): τ²-Airline + GPT-5.4-mini run 5 times, with SOTERIA using 3 retries (not the 8 of the main experiments): conformance-gated utility 50.8±3.6%, compliance 100.0±0.0, violations 0; its 95% confidence interval is above NeMo and No Guardrail and overlaps with AgentSpec (48.0±2.0%).
- Cost (Table 2, Table 8): SOTERIA's per-task cost on τ²-Airline/Retail is higher than all baselines (e.g., Opus on Airline is 0.796 USD vs. 0.318–0.344 for baselines), which the authors explain as generating a new plan each dialogue round; on single-turn Toolathlon, SOTERIA can be cheaper (e.g., GPT-5.4-mini 0.033 USD vs. ABC 0.324).
- SpecMonitor overhead (Figure 10, τ²-Airline, GPT-5.4-mini): the authors report that the median time per step with SpecMonitor is about 1s, lower than about 2.5s without it, with a shorter tail (longest about 9s vs. about 15s); the authors state that early interception reduces extra LLM calls caused by erroneous action sequences.
Other ablations and analyses
- Liveness enforcement: the authors state that NeMo can intercept write operations lacking a prior read, but cannot guarantee a final read-back verification after the write; SOTERIA verifies subsequent required actions on every accepting path and checks pending obligations at task completion (§4.1).
- Baseline failure modes (Appendix B.5): three types—completing the task but violating policies (No Guardrail accumulates 29 violations across 50 airline tasks); excessive caution and handoff to humans (Opus invokes only 57% of required write actions on retail tasks, with 23 tasks handed off to humans; SOTERIA reports 100% of write actions completed); writing files without verification (Gemini baseline 281 writes/685 reads, SOTERIA 62 writes/658 reads).
What are some points that can be further explored?
The authors list limitations including specification formalization, contract assumptions and prover capability; the coverage of ablations and repeated experiments is narrow.
Limitations and future directions noted by the authors
- Specifications depend on humans (Conclusion): SOTERIA requires a set of formal specifications as input, currently obtained through a semi-automated process of LLM auto-formalization plus human verification; the authors plan to study how to use auto-formalization (e.g., An et al., 2026) to reduce manual effort.
- Contract faithfulness assumption (Conclusion): Plan verification assumes that tool contracts faithfully model tool behavior and that postconditions hold at runtime (Appendix A.3.5 also lists this as a soundness assumption).
- Limited prover capability (Conclusion): The automated theorem provers used (Dafny/Z3) support limited first-order theories, and in practice verification may not complete.
- Subplan library construction (Conclusion): Subplans are currently generated with LLM assistance and iteratively verified; the authors say automatically extracting and evolving subplan libraries and specifications from policy documents and agent experience is a promising direction.
- Planning overhead (Conclusion): The authors say reducing planning token overhead through plan caching and reuse across similar tasks could further improve practicality.
Experimental coverage
- The models tested are GPT-5.4-mini, Gemini 3 Flash, Claude Haiku 4.5 and Claude Opus 4.6, 4 in total; the benchmarks are τ²-Airline (50), τ²-Retail (114) and Toolathlon (43 selected from 108), 207 tasks in total (§4).
- Main results are pass@1 single attempt; repeated experiments are run 5 times only on τ²-Airline + GPT-5.4-mini, with the retry budget reduced to 3 (Appendix B.2).
- Component ablations are only on τ²-Airline with two models, GPT-5.4-mini and Gemini 3 Flash (Table 3); the subplan ablation uses only GPT-5.4-mini (§4.3).
- The defense baselines compared are No Guardrail, NeMo Guardrails, AgentSpec and ABC, 4 in total (§4).
- The paper does not report agent performance under adversarial inputs (such as prompt injection); the threat model targets the agent's own violating calls, with specifications formalized by the defender from policy documents (§2.1).
Summarize the main content of the paper
SOTERIA uses verified hierarchical plans plus runtime interception, and reports 100% compliance with success rates not dropping but rising on 207 tasks.
SOTERIA is a safety framework for LLM tool-calling agents, with the goal of enabling agents to both complete tasks and comply with domain policies and tool contracts, rather than choosing between safety and utility.
- Problem: Runtime guardrails are either probabilistic without guarantees (LLM judges), or can intercept violating calls but provide no recovery path, so agents blocked are prone to getting stuck or losing utility.
- Method: Policy documents are formalized into first-order logic specifications and tool contracts; the planner composes pre-verified subplans into hierarchical plans, represented as guarded transition systems, and uses Dafny to statically verify contract satisfaction, progress and policy compliance (retry budget 8 times, with fallback to partially verified plans on failure); at runtime, SpecMonitor concretely evaluates the specifications before each tool execution and intercepts violating calls, and when intercepted, the verified plan guides recovery in worklist form.
- Main results (Table 2): On 207 tasks across τ²-Airline, τ²-Retail and Toolathlon with 4 models, the authors report that SOTERIA achieves 100% compliance and zero violations, while the highest baseline compliance is 93.0% (ABC + Gemini, τ²-Retail); success rates are 4.7–43.9 percentage points higher than the best baseline for each model-benchmark pair, which the authors summarize as an average of 1.7×.
- Representative numbers: Claude Opus 4.6 achieves 88.0% success on τ²-Airline (best baseline 54.0%) and 90.4% on τ²-Retail (best baseline 46.5%); on Toolathlon all methods have low success rates, with SOTERIA at 9.3–18.6% but zero violations.
- Ablations (Table 3, Figure 6): The compliance guarantee mainly comes from SpecMonitor (adding it gives both models 100% compliance and zero violations); subplans raise the number of verification-passing rounds from 38/60 to 65/68 and the first-pass verification rate from 23.3% to 48.5%.
- Authors' conclusion: The authors argue that verified plans provide two capabilities that runtime monitoring alone lacks: global lookahead (checking before execution a sequence that includes future required actions) and recovery guidance, and that safety and utility need not be traded off against each other; the cost is higher per-task API cost than baselines on conversational benchmarks, and specification formalization currently requires human verification.