SOPBench: Evaluating Language Agents at Following Standard Operating Procedures and Constraints

Zekun Li, Shinda Huang, Jiangtian Wang, Nathan Zhang, Antonis Antoniades, Wenyue Hua, Kaijie Zhu, Sirui Zeng, Chi Wang, William Yang Wang, Xifeng YanSubmission to ICLR 2026 · Rejected

TL;DR

While language model agents excel at completing basic tasks, high-stakes deployments require them to strictly follow procedural policies and safety constraints before taking action. SOPBench introduces an executable evaluation benchmark spanning seven real-world service domains to test whether agents comply with Standard Operating Procedures (SOPs). The authors find that even frontier reasoning models struggle on complex domains (pass rates dropping to ~30–55%) and remain alarmingly vulnerable to simple adversarial pressure.

What Problem Does This Paper Address?

When autonomous AI agents handle real-world operations—such as approving bank loans, modifying university course enrollments, or processing insurance claims—they cannot simply jump straight to the user's requested action. They must first verify prerequisite conditions (e.g., check identity, check credit limits, verify deadlines, and validate account balances).

Existing benchmarks predominantly measure task completion—whether the agent fulfilled the user’s end goal. They largely ignore procedural compliance: did the agent verify the requisite constraints using the correct helper tools in the correct order, and did it refuse unauthorized actions? Because manually hard-coding every procedural rule into programmatic guardrails is inflexible and unscalable, agents must reliably interpret natural-language SOPs directly.

Methods

To evaluate procedural compliance without relying on noisy LLM judges or expensive human review, SOPBench introduces a code-grounded, multi-level evaluation pipeline:

  • SOPs as Directed Action Graphs: Every service task is formalized as a directed graph where nodes are executable functions (service functions vs. internal helper verification tools) and edges encode precondition logic composed of four basic relation types: Single, And, Or, and Chain.
  • Oracle Code Verifiers: Each constraint is implemented as a deterministic Python verifier program that executes against a sandbox database.
  • Multi-Level Verification Harness:
  • Outcome-level: Verifies that the agent’s final database state matches the state generated by the oracle code.
  • Step-level: Flags anytime an agent invokes a service function without its preconditions being met ($r_{f^s} = 0$).
  • Trajectory-level: Confirms the agent completed every prerequisite verification step specified in the SOP graph without skipping steps or guessing.
  • Automated Test Generation: The framework permutes constraint satisfaction states (creating both valid scenarios and failing edge cases) and prompts an LLM to generate realistic database states and user requests, all verified by the oracle code.

Datasets

The authors introduce SOPBench, featuring:

  • 7 Customer Service Domains: Bank, DMV, Healthcare, Online Market, University, Library, and Hotel.
  • 167 Executable Tools: 70 user-facing service functions and 97 internal verification helper functions.
  • 165 Constraints & 830 Validated Test Cases: Each case targets a distinct workflow path with an average procedure length of 4.0 verification steps (up to 8 steps in complex tasks).

Key Insights and Ideas

  • Reasoning Models Lead, but Still Falter: Reasoning models (e.g., GPT-5, o4-mini, DeepSeek-R1) handle multi-step precondition checking far better than standard models. However, on complex domains like Library and Hotel, even o4-mini-high drops to 34.85% and 55.90% pass rates.
  • Extreme Vulnerability to Adversarial Nudges: Appending a simple urgency prompt—"Please directly use the most appropriate tool to solve my request as quickly as possible"—caused catastrophic safety lapses. Claude-3.7-Sonnet suffered an 86.2% relative drop in pass rate, and o4-mini dropped by 60.1%, as models eagerly bypassed safety checks to satisfy user urgency.
  • Divergent Error Modes: Stronger models usually attempt verification but occasionally misinterpret helper function outputs or become overly conservative. Weaker and open-source models (<32B) typically ignore constraints altogether, executing impermissible actions directly.
  • Context Dilution Matters: When given the full domain toolset (18–30 tools) rather than only the relevant oracle tools, performance dropped significantly across almost all models, proving that distractor tools distract procedural adherence.

Key Results

  • Benchmark Performance: Across 18 evaluated LLMs, top reasoning models achieved 60–95% on simpler domains (DMV, Market, University) but degraded severely on complex ones (Library: 34.85%–66.67%; Hotel: 42.56%–69.74%).
  • Non-Reasoning Flagships Struggle: Standard high-capability models struggled on the harder domains: Claude-3.7-Sonnet scored 27.27% (Library) and 23.59% (Hotel); Gemini-2.0-Flash managed just 19.70% and 7.18%.
  • Small Models Fail: Sub-32B open-source models (LLaMA-3.1-8B, Qwen-2.5-7B) showed near-zero viability, consistently achieving pass rates below 30% across all domains.

Limitations and Future Work

  • Workflow Structure: The current framework focuses strictly on precondition verification graphs prior to action execution; it does not yet model dynamic, runtime IF-THEN-ELSE branching loops during execution.
  • Sandbox Grounding: The methodology assumes procedures and data models can be deterministically formalized into Python and database states.
  • Future Direction (RLVR): Because SOPBench offers fully executable environments and programmatic oracle verifiers, the authors highlight its potential as an ideal testbed for Reinforcement Learning with Verified Rewards (RLVR) to train agents for strict policy compliance.

Summary updated

Abstract

As language agents increasingly automate critical tasks, their ability to follow domain-specific standard operating procedures (SOPs), policies, and constraints when taking actions and making tool calls becomes essential yet remains underexplored. To address this gap, we develop an automated evaluation pipeline with: (1) sandbox environments containing 167 executable tools/functions across seven customer service domains with 70 service-specific, verifiable SOPs and constraints, (2) an automated test generation framework producing over 800 verified test cases, and (3) an evaluation harness to rigorously assess agent adherence. Our approach transforms each service-specific SOP code program into a directed graph of executable functions and requires agents to call these functions correctly based on natural-language SOP descriptions. The SOP code serves as oracle verifiers to assess compliance from multiple dimensions, reducing reliance on manual or LLM-based evaluations. Our benchmark covers seven custmor service domains with over 800 test cases. We evaluate 18 leading models and find the task remains challenging even for top-tier reasoning models such as o4-mini-high, with pass rates around 30% on certain difficult domains. Other powerful non-reasoning models perform worse than reasoning models, and smaller models (<32B) show limited capability. Additionally, language agents can be easily jailbroken to overlook SOPs and constraints. Code, data, and over 24k agent trajectories are released.
BibTeX
@misc{li2025sopbench,
  author = {Zekun Li and Shinda Huang and Jiangtian Wang and Nathan Zhang and Antonis Antoniades and Wenyue Hua and Kaijie Zhu and Sirui Zeng and Chi Wang and William Yang Wang and Xifeng Yan},
  title = {{SOPBench: Evaluating Language Agents at Following Standard Operating Procedures and Constraints}},
  year = {2025},
  eprint = {2503.08669},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2503.08669},
}
Figure