Soteria — Pre-verified plans vs per-action guardrails — What does it mean?
The news. On November 13, 2026, Mike He, Ankush Desai, Sharad Malik and Aarti Gupta posted Soteria: Formally Verified Planning with Runtime Enforcement for Safe LLM Agents to arXiv, where it is listed as a NeurIPS 2026 oral. On 207 tasks from τ²-Airline, τ²-Retail and Toolathlon, run with four backbone models, Soteria finished with zero policy violations in every model–benchmark pair, while baseline conformance reached at most 93%. It also reports 1.7 times the average task success rate of the best baselines. Read the paper →
Picture a train that must reach a station without breaking any railway rule. One way to keep it safe is to put a signal at every junction: when the train tries an unsafe move, the signal turns red. That works, but a red signal with no route map leaves the train standing on the track. The signal knows the move is wrong; it does not know which track the train should take instead. This is the gap in per-action guardrails: they can stop a bad tool call, but they do not give the agent a verified sequence of calls to follow instead. The paper sorts existing guardrails into two kinds. An LLM judge rates each proposed action, which is easy to deploy but gives no formal guarantee. A specification monitor checks rules on each call, which gives a stronger guarantee but no verified way forward after a block. Both are forms of the policy-enforcement gate, and both run into the trade-off in fail-safe vs fail-open: blocking the call keeps the system safe, but leaves the task unfinished.
Soteria adds the dispatcher. Before the agent calls any tool, it writes the whole route as a plan, and a verifier proves that plan safe. The plan is not free text. It is written in a small domain-specific language as a guarded transition system: states joined by tool calls, with an if/else guard on each branch. For the request "cancel reservation RES123", the plan looks up the reservation, computes the hours since booking, and branches either to the cancel call or to a "not permitted" stop. Soteria turns three checks into verification conditions for Dafny: every call meets its tool's precondition (the same idea as a tool schema, made checkable), the plan can never reach a state with no enabled branch, and every possible path satisfies the policy specifications. In the paper's own example, the first draft of that plan skips the required "no flights already flown" check. The verifier rejects it before anything runs, and the diagnostic goes back to the planner. The planner gets up to 8 retries; if no draft verifies fully, Soteria keeps the strongest partially verified plan and shows the unproven rules to the executor as warnings.
The signals stay up even on a checked route. At runtime a SpecMonitor checks every proposed call against the calls already made, so a call that would break a formalized rule is blocked before it executes, even if the plan was only partly verified or the agent wanders off it. The check is cheap because it pattern-matches the concrete trace instead of running a solver. On τ²-Airline with GPT-5.4-mini, the median step took about 1 s with the monitor versus about 2.5 s without, because early blocks cut off wasted recovery attempts. The difference from a plain monitor is what happens next. The executor sees the plan as a worklist: a flowchart that drops each branch as soon as a tool result decides its guard. After a block, the worklist shows the remaining plan, so the agent can usually pick an alternative branch the verified route already contains; if no planned branch fits, it falls back to its own reasoning, informed by the plan and the reason for the block. A stricter mode can also refuse any call the plan does not contain, for workflows where any deviation is unacceptable.
Checking the route ahead also catches a kind of rule that a per-call check cannot see. Toolathlon includes a verify-after-write rule: after writing a file, the agent must read it back. A per-action judge can block a write, but it has no way to make the agent perform a read that has not happened yet. Because Soteria checks every path to the finish, a plan that leaves out a required later step fails verification before execution, and any obligation still open is checked again when the task completes. This makes the plan a defense-in-depth layer that looks forward along the route, not only at the call in front of it.
Writing a whole verified route sounds expensive for long tasks, and the paper's answer is reuse. Each standard procedure in the policy, such as cancel, refund or book, becomes a sub-plan with its own contract. It is verified once and then called like a tool, so the planner only writes the top-level composition. On τ²-Airline with GPT-5.4-mini, sub-plans cut the median plan from 11 states to 8 and raised the planning turns that verified from 38 of 60 to 65 of 68. The remaining failures also changed kind: without sub-plans they were specification errors that needed a redesign; with sub-plans they were mostly parse and compile errors that the retry loop can address.
| Approach | What it checks | Conformance | Violations | Success | Source |
|---|---|---|---|---|---|
| No guardrail | policy in the prompt only | 64% | 29 | 34% | Table 2 |
| NeMo Guardrails | LLM judge on each action | 76% | 23 | 40% | Table 2 |
| AgentSpec | rule monitor on each action | 84% | 8 | 50% | Table 2 |
| ABC | behavioral contracts at runtime | 90% | 5 | 48% | Table 2 |
| Soteria | verified plan + SpecMonitor | 100% | 0 | 60% | Table 2 |
| τ²-Airline, 50 tasks, GPT-5.4-mini, one attempt per task. Success counts only tasks completed with no violation. | |||||
Hold the model (GPT-5.4-mini) and the benchmark (τ²-Airline, 50 tasks) fixed, and follow the counts in the table. Without a guardrail the agent completes 48% of tasks, which is 24, but only 34%, which is 17, finish with no violation. So 7 tasks were "completed" by breaking a rule. The best baseline in this cell, AgentSpec, raises clean finishes to 50%, or 25 tasks, and still allows 8 violations. Soteria completes 60%, 30 tasks, and all 30 are clean: 30 clean finishes against 25 for the best baseline and 17 for no guardrail. The gain is not free. In the same cell Soteria spends about $0.125 per task against $0.031 without a guardrail, roughly 4×, because it generates a new plan at every turn of the dialogue. On single-turn Toolathlon tasks, where one plan is enough, the paper reports that it can cost less than the baselines.
The guarantee is only as good as the written rules. The specifications come from an LLM auto-formalizer and are then checked by hand, clause by clause. The authors report a few hours of this work per benchmark, and they corrected mis-encoded specifications and added missing ones while auditing results. A rule nobody formalized is a rule the verifier cannot enforce. A tool whose result breaks its own postcondition aborts the run, because the plan's proof assumed that contract. Within those limits, the utility gain is large on the conversational domains: Claude Opus 4.6 reached 88.0% on τ²-Airline and 90.4% on τ²-Retail, against 56.0% and 46.5% for the best baselines. Long-horizon Toolathlon stays hard, at 9.3–18.6% success across the four models, though now with zero violations.
Goes deeper in: Agent Engineering → Layered Guardrails → Policy Enforcement
Related explainers
- Planning-as-Routing and the plan declaration–execution gap — the same move from a plan as text to a plan as control flow, aimed at plan fidelity rather than policy
- Fail-open vs fail-closed agent guardrails — why a per-action model judge is a weak gate on its own
- Evidence-grounded verification with Vera — checking what an agent actually did, after the run