cs.AINov 13, 2026

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

Authors: Mike He, Ankush Desai, Sharad Malik, Aarti Gupta

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

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Jun 22, 2026

Toward Safe LLM Agents: A Survey of Specification, Verification, and Enforcement

Large Language Model (LLM) agents take irreversible real-world actions, yet no system gives formally grounded, task-level safety guarantees for their plans. In a PRISMA 2020 systematic review, we searched six databases (20-29 May 2026) for work on LLM agent specification, verification, and enforcement published in 2022-2026. We narratively synthesized 38 studies, assessed risk of bias per study, and graded evidence certainty with GRADE. Three authors independently screened a repeated search to validate the single-reviewer screening (agreement: Fleiss' κ=0.81κ= 0.81). First, specification is the bottleneck: on one benchmark, only 24.8-34.2% of LLM translations from natural language into Planning Domain Definition Language (PDDL) are semantically correct. Second, runtime monitoring is the most mature enforcement strategy; it reduced unsafe actions by 65.37% in one household-agent study, but its guarantees cover only single steps or short horizons. Third, in one ττ-Bench study of transactional tool-use agents, blocking 94% of unsafe actions still left fewer than 5% of tasks completed both safely and correctly in most settings, because agents found other unsafe routes (the verifier tax). Fourth, no approach simultaneously achieves soundness, completeness, scalability, semantic grounding, and utility preservation. For seven of the nine principal claims, GRADE gives the lowest certainty rating (Very Low), meaning further studies are likely to produce substantially different figures; each rests on one or two studies in narrow domains. Two of the open problems we rank highest are translating requirements into formal specifications that keep their meaning and enforcing safety over whole plans rather than single actions. We contribute a three-level taxonomy and an agenda of ten open problems.
Sep 28, 2026

SAGE: Symbolic Action-Gating and Editing for LLM Task Planners

Large language models (LLMs) are now the default cognitive core of embodied household agents, yet the plans they emit are rarely checked against a grounded model of the environment before execution, and the task-success they report is often measured on benchmarks so saturated that no method can be separated from another. We present SAGE (Symbolic Action-Gating and Editing), a single-LLM planner built from two lightweight mechanisms: a domain-agnostic symbolic gate (~250 lines of Python, zero tokens, O(∣π∣)O(|π|)) that blocks precondition-violating actions with typed reasons as a runtime safety monitor, and a local edit that regenerates only the failed sub-goal's suffix, keeping completed and untouched work intact; a hybrid seed+live memory store supports cold-start coverage. We evaluate under a leak-free protocol (leave-one-out retrieval) over five open-weight models and a 75-task AI2-THOR benchmark. On the standard benchmark goal-completeness saturates (52% of instances trivially solved) and SAGE ties strong hierarchical baselines. On a harder, method-agnostic multi-goal composition, SAGE's completeness lead re-emerges large (+0.06 to +0.23 across four models). Under injected mid-execution failures, SAGE recovers as reliably as whole-plan replanners at 2.4-3.3x fewer LLM calls. As a verify-before-execute gate, the symbolic monitor blocks unsafe actions before actuation and raises simulator-reported step-success for every planner tested (up to +0.11), a signal the verifier never sees (non-circular). Because the gate calls no model (0.008 ms/plan), it is a safety layer that runs essentially free on the edge: SAGE planning reproduces its quality on a Jetson AGX Orin, where small-model verification helps most. We release the benchmark, the leak-free protocol, the recovery and safety-gate harnesses, and a verifier-portability study (auto-induced on ALFWorld, 0.89 held-out).
Jul 31, 2026

Tool Specifications Matter: Uncovering and Mitigating Safety Risks in AI Agents

AI agents extend large language models (LLMs) with external tools, enabling them to perform complex tasks and translate model outputs into consequential real-world actions. Yet LLMs often become substantially less safe when deployed as agents, and the source of this degradation remains poorly understood. In this paper, we identify schema-formatted tool specifications as a primary source of agent safety degradation and show, through white-box representation analysis, that they weaken the model's internal refusal signals and contribute to unsafe tool execution. Building on this finding, we propose SafeKeep, an inference-time safeguard that decouples safety judgment from tool execution: it assesses requests using flattened textual tool specifications while retaining the original schema-formatted specifications for execution. Across two representative benchmarks and four LLMs, including both white-box and black-box models, SafeKeep increases the average refusal rate for harmful requests from 23.8% to 70.6% and reduces the average attack success rate under observation-level prompt injection from 25.6% to 2.5%. It also outperforms existing safeguards and preserves task-handling capability. We release the code and data at https://github.com/snowcatsmoking/SafeKeep .