Soteria: Formally Verified Planning with Runtime Enforcement for Safe LLM Agents

Mike He, Ankush Desai, Sharad Malik, Aarti GuptaarXiv 2026 · arXiv

This paper, presented at NeurIPS 2026, introduces SOTERIA, a framework designed to solve the "safety vs. utility" trade-off in Large Language Model (LLM) agents. By combining formal verification with runtime enforcement, SOTERIA ensures that agents follow complex domain policies without getting stuck when an unsafe action is blocked.

TL;DR

SOTERIA reconciles agent safety and task success by verifying structured, hierarchical plans against formal specifications before execution. During runtime, these verified plans act as both a guardrail and a recovery guide, achieving 100% policy conformance and a 1.7x improvement in success rates over state-of-the-art baselines.

What Problem Does This Paper Address?

As LLM agents are deployed for high-stakes tasks like enterprise automation or scientific discovery, they must navigate two conflicting goals: utility (completing the user's request) and safety (conforming to domain policies and tool contracts).

Current solutions usually fall into two camps, both of which are flawed:

  1. LLM-based guardrails: These use a secondary model to judge actions. They are easy to set up but probabilistic and offer no formal guarantees.
  2. Runtime monitors: These block unsafe actions based on hard rules. However, once an action is blocked, the agent is often left "stranded" in a non-recoverable state with no principled way to finish the task.

SOTERIA addresses the "stranded agent" problem by ensuring that if a path is blocked, the agent already has a pre-verified alternative path to follow.

Methods

SOTERIA's architecture consists of a one-time setup phase followed by a per-task planning and execution loop.

Figure 1: Overview of SOTERIA

1. Formalization and Sub-plans

SOTERIA uses an LLM-based auto-formalizer to turn natural-language policy documents into Formal Specifications (first-order logic) and Tool Contracts (pre/post-conditions). It also creates a library of Reusable Sub-plans—pre-verified snippets for common procedures like "cancel reservation" or "process refund."

2. Verified Hierarchical Planning

Instead of generating a raw sequence of actions, the SOTERIA Planner composes a Guarded Transition System (GTS). This is a directed graph where nodes are states and edges are tool calls gated by Boolean conditions (guards).

Figure 2: A parent plan composing the CANCEL and REFUND sub-plans. The planner generates the top-level plan; each sub-plan encapsulates one procedure and is reused across tasks.

Before any tool is called, the plan is sent to a Plan Verifier (using the Dafny automated theorem prover). The verifier checks three things:

  • Tool Contracts: Does every call satisfy its preconditions?
  • Progress: Can the plan get stuck in a dead end?
  • Policy Compliance: Does every possible path through the graph satisfy the domain rules?

3. Runtime Enforcement (SpecMonitor)

During execution, a SpecMonitor intercepts every proposed tool call. If the call violates a specification, it is blocked. Crucially, because the agent is following a verified plan, the executor can consult the plan's "worklist" to find an alternative, safe branch to recover and complete the task.

Datasets

The authors evaluated SOTERIA on 207 tasks across three challenging benchmarks:

  • $\tau^2$-Airline: 50 tasks involving airline reservation management and complex cancellation/modification policies.
  • $\tau^2$-Retail: 114 tasks focused on retail order handling, returns, and exchanges.
  • Toolathlon: 43 tasks testing long-horizon tool use in terminal environments, filesystem management, and document editing.

The framework was tested across four backbone LLMs: GPT-5.4-mini, Gemini 3 Flash, Claude Haiku 4.5, and Claude Opus 4.6.

Key Insights and Ideas

  • Global Foresight: Unlike runtime-only monitors that look one step ahead, SOTERIA’s static verification checks for "liveness" obligations—actions that must happen in the future (e.g., "if you write to a file, you must eventually read it back to verify").
  • The Power of Hierarchy: By using sub-plans, SOTERIA reduces the complexity of the planning task. Instead of the LLM trying to get a 20-step plan right all at once, it only needs to compose a few high-level, pre-verified blocks. This nearly doubled the number of plans that passed verification on the first attempt.
  • Safety as a Utility Driver: Traditionally, safety is seen as a "tax" on performance. SOTERIA shows that formal safety can actually improve utility by preventing agents from wandering into "hallucinated" or illegal states from which they cannot recover.

Key Results

SOTERIA dominated the baselines (No Guardrail, NeMo Guardrails, AgentSpec, and ABC) across all metrics:

  • 100% Conformance: SOTERIA achieved zero specification violations across all 207 tasks and all four models. Baselines reached at most 93% conformance.
  • 1.7x Success Rate: On average, SOTERIA was 70% more successful at completing tasks than the best-performing baseline.
  • Efficiency: While planning takes more time upfront, SOTERIA often reduced total execution time by preventing the agent from taking erroneous, time-consuming paths that would eventually be blocked.
Table 2: Utility, success rate, conformance, specification violations, and cost across benchmarks and backbone LLMs. Best success rates, conformance, violation counts, and costs per model– benchmark group are bolded.

Limitations and Future Work

  • Manual Validation: While the formalization is LLM-assisted, it still requires a human-in-the-loop to validate the generated specifications against the original policy.
  • Contract Fidelity: The system's safety is only as good as its tool contracts. If a tool's actual behavior deviates from its formal contract, the verification guarantees may fail.
  • Token Overhead: Generating and iterating on formal plans consumes more tokens than simple reactive prompting, though the authors argue this is offset by higher task success and fewer execution retries.
  • Future Directions: The authors suggest automating the extraction of sub-plans from agent experience and improving plan caching to reduce per-task overhead.

Summary updated

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.
BibTeX
@misc{he2026soteria,
  author = {Mike He and Ankush Desai and Sharad Malik and Aarti Gupta},
  title = {{Soteria: Formally Verified Planning with Runtime Enforcement for Safe LLM Agents}},
  year = {2026},
  eprint = {2611.17880},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17880},
}
Figure