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

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

    Jun 22, 2026Pierre Dantas, Lucas Cordeiro, Ehsan Nowroozi +1LLM Agent SafetyLLM Agent Reliability

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

    Sep 28, 2026Trung Minh Bui, JongSul Moon, YoungOuk Kim +3Large Language Model-Based Robot PlanningSymbolic Planning

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

    Jul 31, 2026Minghui Pan, Jiayuxuan Yang, Yuanyuan Yuan +2LLM GuardrailsPrompt Injection Attacks on AI Agents