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

## Abstract

Abstract As language agents progressively automate critical tasks across domains, their ability to operate within operational constraints and safety protocols becomes essential. While extensive research has demonstrated these agents’ effectiveness in downstream task completion, their reliability in following operational procedures and constraints remains largely unexplored.
To this end, we present AgentOrca, a dual-system framework for evaluating language agents’ compliance with operational constraints and routines. Our framework encodes action constraints and routines through both natural language prompts for agents and corresponding executable code serving as ground truth for automated verification. Through an automated pipeline of test case generation and evaluation across five real-world domains, we quantitatively assess current language agents’ adherence to operational constraints. Our findings reveal notable performance gaps among state-of-the-art models, with large reasoning models like o1 demonstrating superior compliance while others show significantly lower performance, particularly when encountering complex constraints or user persuasion attempts. 1 1 1 Code: https://github.com/Leezekun/AgentOrca

## 1 Introduction

The rapid advancement of Large Language Models (LLMs) (OpenAI, 2024; Team, 2024; Anthropic, 2024a; Dubey et al., 2024; Qwen Team, 2024; Liu et al., 2024) has showcased their remarkable reasoning and planning capabilities. By equipping these LLMs with tools to interact with environments, these models are increasingly deployed as autonomous agents, revolutionizing the automation landscape. Language agents (LLM-based agents) have demonstrated impressive performance across a wide range of tasks, including software engineering (Wang et al., 2024; Yang et al., 2024), web browsing (Zheng et al., 2024; Deng et al., 2024), computer usage (Anthropic, 2024b; Tan et al., 2024), scientific discovery (Bran et al., 2023), etc. However, since these systems are entrusted with critical operations in production environments, their ability to reliably follow operational routines, constraints, safety protocols, and procedural safeguards becomes essential (Hua et al., 2024).

While existing benchmarks evaluate language agents’ ability to use external tools (Jimenez et al., 2023; Liu et al., 2023; Qin et al., 2023) and plan tasks (Xie et al., 2024), a fundamental gap exists in understanding their reliability in following operational constraints and procedures. Additionally, although research has explored LLMs’ content safety (Chao et al., 2024), adherence to system messages (Qin et al., 2024), complex instructions (Wen et al., 2024), rules, and constraints (Mu et al., 2023; Sun et al., 2024; Zhou et al., 2024; Madmoni et al., 2024) in response generation, much less attention has been paid to the behavioral safety of language agents and their ability to comply with constraints and procedures when taking actions. This gap is particularly concerning, as the reliability of these systems in high-stakes environments depends on their capacity to operate safely within the defined operational boundaries.
To address this critical gap, we introduce AgentOrca, a novel dual-system framework that enables automated evaluation of Language Agents’ Operational Routine and Constraint Adherence.

Figure: Figure 1: Overview of the AgentOrca evaluation framework, which evaluates language agents through two parallel systems that share the same environment (tools, databases) but differ in constraint handling: (1) the “Program System” that implements constraints and routines as executable code, used as oracle, and (2) the “Prompt System” where agents rely solely on natural language prompt that specifies same constraints. By comparing their execution trajectories and database states, we measure whether agents adhere to constraints and routines in their prompt.
Refer to caption: /html/2503.08669/assets/x1.png

Automated Verification.
AgentOrca enables language agents to operate through two parallel systems that share the same environment simultaneously: (1) a “Program System” that implements constraint and routine checking in code to serve as ground truth, and (2) a “Prompt System” where agents must follow constraints and interpret routines purely from natural language descriptions in their prompts. By comparing execution trajectories and database states between these systems, we can automatically verify agents’ compliance with constraints and correct execution of routines using a directed action graph (DAG) checking algorithm.

Automated Test Case Generation.
Our evaluation spans five real-world assistant domains: banking, DMV (Department of Motor Vehicles), healthcare, library, and online market. Each domain features essential services with associated constraints and routines. We categorize constraint compositions into four types: single condition (Single), conjunctive (And), disjunctive (Or), and sequential chain (Chain). By permuting these constraints, AgentOrca uses LLMs to automatically create comprehensive test cases that cover operational scenarios with varying levels of complexity.

Results.
Our evaluation results on 663 tasks reveal significant gaps in constraint adherence and routine execution among current language agents. Even state-of-the-art LLMs display notable performance gaps, though large reasoning models like OpenAI’s o1 and Gemini-2.0-Flash-Thinking perform significantly better, achieving high pass rates. However, other models that support function calling show substantially lower performance (30–50% pass rates), except GPT-4o. Performance further degrades as constraints become more complex or when users attempt to persuade the agent to overlook constraints and perform prohibited actions, dropping to as low as 25% in the healthcare domain for Claude-3.5-Sonnet.

Our task requires two key capabilities: the ability to identify relevant constraints from context and select correct actions for constraint checking, and strong reasoning capabilities to determine correct action routines and action constrain satisfaction. Our framework provides an automated pipeline that enables scalable testing of language agents’ constraint and routine adherence. Moreover, it can be extended into an environment for online reinforcement learning, providing stepwise rewards to agents in real time, which we leave for future work.

## 2 Related Work

As shown in Table [1](#S2.T1), we discuss three key research areas related to our work in this section.

### 2.1 Language Agents and Tool Use

Language agents are language models equipped with tools to interact with environments (Schick et al., 2023; Patil et al., 2023; Shen et al., 2024; Tang et al., 2023). Several benchmarks have been developed to evaluate agents’ tool use, planning, and task-solving capabilities, in generating correct function calls (Yan et al., 2024) and using tools to solve user requests (Qin et al., 2023; Liu et al., 2023). However, these benchmarks primarily evaluate task completion while overlooking agents’ adherence to operational routines during tool usage and action execution. Although $\tau$-Bench (Yao et al., 2024) incorporates domain policy, the benchmark creation process is labor-intensive, limited in scope, and inflexible in adjustment, whereas our approach enables automated and scalable evaluation.

**Table 1: Comparison of different benchmarks and framework. Program Evals refers to automated, rigorous assessments conducted by programs without relying on LLMs. Executable refers to whether the tools can be executed. *Our approach enables the generation of an arbitrary number of task and test cases.**
| Benchmark/Framework | Evaluation Focus | Program Evals | Automated Gen | Executable | # Domains | # Tasks |
| --- | --- | --- | --- | --- | --- | --- |
| SysBench (Qin et al., 2024) | System Prompt Following Response Generation | ✗ | ✗ | - | - | 500 |
| ComplexBench Wen et al. (2024) | Constraint Following Response Generation | ✗ | ✗ | - | - | 1,150 |
| RuleArena Zhou et al. (2024) | Rule-Following Reasoning | ✗ | ✗ | - | 3 | 816 |
| $\tau$-Bench (Yao et al., 2024) | Agent Action Policy Following | ✓ | ✗ | ✓ | 2 | 165 |
| ToolEmu Ruan et al. (2023) | Agent Action Safety | ✗ | ✓ | ✗ | - | 311 |
| AgentOrca (Ours) | Agent Action Routine and Constraint Following | ✓ | ✓ | ✓ | 5 | 663* |

### 2.2 Instruction and Rule Following

Following instructions and rules is a critical capability for instruction-tuned LLMs. Recent work has examined models’ adherence to various types of instructions in prompts. SysBench (Qin et al., 2024) evaluates chat-tuned LLMs’ compliance with system messages that control generation behavior. IFEval (Zhou et al., 2023) assesses models’ ability to follow simple, verifiable instructions like writing style and length constraints. WizardLM (Xu et al., 2023) and ComplexBench (Wen et al., 2024) introduce more challenging text generation tasks with composite requirements. RuleBench (Sun et al., 2024), RuleArena (Zhou et al., 2024), and IDEA (He et al., 2024b) evaluate models’ adherence to complex rules in real-world scenarios. However, these studies primarily focus on constraints in text generation rather than tool use and action execution in agentic tasks.

### 2.3 Language Agent Safety

The content safety of LLMs has become a critical concern, attracting significant research attention (Bengio et al., 2024; Mazeika et al., 2024; Zhang et al., 2023; Zou et al., 2023; Chao et al., 2024; Greshake et al., 2023; Li et al., 2024). As LLMs transition into interactive agents, safety issues now extend beyond text generation to include action execution in dynamic environments (He et al., 2024a). For example, AgentDojo (Debenedetti et al., 2024) and InjecAgent (Zhan et al., 2024) explore indirect prompt injection via tool calls on untrusted data, while ToolSword (Ye et al., 2024) investigates broader challenges in tool learning—from harmful queries to risky tools. PrivacyLens (Shao et al., 2024) evaluates privacy leakage in agent actions, and ToolEmu (Ruan et al., 2023) leverages LLMs to emulate tool execution and identify unsafe behaviors, addressing the complexity of manual tool design. In contrast to these approaches which focus on behavioral safety and environmental harm, our work examines operational compliance, evaluating whether agents adhere to defined routines and constraints during execution.

Figure: Figure 2: Workflow of AgentOrca. The environments and action constraints are manually designed while the task data are generated using LLMs. language agents interact with the environment following prompt-specified constraints. The execution is evaluated on three criteria: (1) constraint compliance, verified by the program system which checks if each action’s constraints are met; (2) database state matching between the Program and Prompt systems; and (3) adherence to the directed action graph routine.
Refer to caption: /html/2503.08669/assets/x2.png

## 3 AgentOrca Foundations

### 3.1 Language Agent Formulation

Language agents are tool-augmented LLMs that can directly interact with external environments for task execution. Given a user instruction $u\in\mathcal{U}$ (e.g., “*Help me schedule a driving test*”) or a sequence of instructions throughout the interaction process, an agent executes a sequence of actions to accomplish the task.
At each step $n$, the agent selects and executes an action $a_{n}\in\mathcal{A}$ by calling an available tool $f_{n}\in\mathcal{F}$ with appropriate input arguments.
Each action then produces an observation $o_{n}\in\mathcal{O}$ from the environment and triggers a state transition.
The environment state $s\in\mathcal{S}$ transitions according to the function $T:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{S}\times\mathcal{O}$, where $s_{0}$ denotes the initial state. In our framework, the state primarily comprises the database state $\mathcal{S}^{db}$, maintaining the system’s persistent information.

**Table 2: The four basic action constraint composition types in AgentOrca. Examples are from the DMV domain. The target service action is highlighted in red, while the constraints are highlighted in blue.**
| Type | Description | Example |
| --- | --- | --- |
| Single | Only one constraint that must be satisfied before executing the action. | To renew the vehicle, please verify the vehicle has valid insurance. |
| And | Multiple constraints that must all be simultaneously satisfied. | To schedule a driving test, please verify that the user is at least 16 years old AND has passed the knowledge test. |
| Or | A set of constraints where satisfying any one is sufficient to enable the action. | To verify the identification at the DMV, the user must provide either correct account password OR social security number. |
| Chain | A sequence of constraints that all must be satisfied and verified in a specific order. | To renew vehicle insurance, please first verify that the user has a registered vehicle, THEN verify that the vehicle currently has insurance. |

### 3.2 Action-Constraint Mappings

Real-world tasks frequently demand that certain prerequisites be met before a critical operation is performed. In AgentOrca, we label the primary action that resolves the user’s request as a *service action* (*e.g.*, transferring funds, renewing a vehicle) and the necessary requirements as *constraints*, each verified through *verification actions* (*e.g.*, authenticating a user’s identity).

Basic Concepts.
In our design, each test case consists of a user request $u$ corresponding to a *service action* $a^{s}$ which uses exactly one tool, denoted as $f^{s}\in\mathcal{F}$, to fulfill this request. Each $a^{s}$ is associated with a constraint composition $C_{a^{s}}$, which is a composition of one or more constraints $\{c_{1}^{s},..,c_{n}^{s}\}\subseteq\mathcal{C}$, where $\mathcal{C}$ represent the set of all basic (non-compositional) constraints, such as *“the transfer amount must not exceed the available balance”*. Each individual constraint $c_{i}\in\mathcal{C}$ specifies a single condition that must be verified before some service action can be executed. A constraint $c_{i}$ requires one verification action $a^{v}$, which employs a tool $f^{v}\in\mathcal{F}$. Specifically, every constraint $c_{i}$ is associated with a set of permissible verification tools, denoted as $\mathcal{F}^{v}_{c_{i}}\subseteq\mathcal{F}^{v}$. In every domain, we denote the set of tools that are leveraged in all verification action $a^{v}$s to be $\mathcal{F}^{v}\subseteq\mathcal{F}$ and the set of tools that are leveraged in all service actions $a^{s}$s to be $\mathcal{F}^{s}\subseteq\mathcal{F}$.

Action-Constraint Mappings.
We formalize these relationships through two key mappings: (1) *service action to constraint mapping* $M^{s}:a^{s}\rightarrow C_{a^{s}}$, which associates one service action with its constraint composition, and (2) *constraint to verification action mapping*: $M^{v}:c_{i}\rightarrow\mathcal{F}^{v}_{c_{i}}$, that associates each constraint $c_{i}$ with the set of verification functions $\mathcal{F}^{v}_{c_{i}}$ required to check it.

### 3.3 Verification Action Routine

Given these mappings, when a service action is invoked for user instruction $u$, the agent must first call necessary verification actions to confirm constraint satisfaction. These verifications may also have their own constraints requiring prerequisite actions. The agent’s trajectory $\tau_{N}=(f_{1},\ldots,f_{N})$ thus forms a coherent action routine, ensuring proper verification before service actions.

### 3.4 Constraint Verification Outcome

Constraint Composition Types.
An action constraint composition $\mathcal{C}_{a^{s}}$ consists of one or more constraints with specific composition relationships. As shown in Table [2](#S3.T2), we consider four basic composition types in AgentOrca: Single, And, Or, and Chain. These basic types may be nested to construct more complex compositions.

Combined Verification Outcome.
The verification of each constraint $c_{i}$ yields a binary outcome $r_{c_{i}}=R(c_{i},\tau_{n})$, indicating whether the constraint is satisfied under the current agent trajectory $\tau_{n}$ using a verifier $R$.
For service action $a^{s}$ with constraint composition $\mathcal{C}_{a^{s}}$ consisting of $\{c_{1},c_{2},\cdots,c_{M}\}$, the combined verification outcome governing whether it can be executed is determined by:

$$ $r_{a^{s}}=\phi(r_{c_{1}},r_{c_{2}},\cdots,r_{c_{M}}),\phi:\{0,1\}^{M}\rightarrow\{0,1\},$ $$

where $\phi$ combines the $M$ individual constraint results based on their composition relations.

Figure: Figure 3: Illustration of test case generation. By permuting satisfaction states of constraints in composition $C_{a}$ for a service action $a$, we generate diverse test cases with controlled outcomes using LLMs (prompt shown right).
Refer to caption: /html/2503.08669/assets/x3.png

## 4 AgentOrca Evaluation Framework

Building upon the conceptual foundations of constrained language agent interactions (Section [3](#S3)), we now introduce our framework for evaluating agents’ operational constraints and routines adherence. The evaluation targets two principal capabilities: (1) executing verification actions in the correct order (i.e., following the prescribed routine) to validate constraint satisfaction, and (2) making correct decisions about whether to execute the action based on verification results of each constraint. While these can be assessed manually (by human or LLMs), such an approach is labor-intensive, prone to inconsistency, and limits both the speed and scope of testing. To address this, AgentOrca employs a dual-system approach that enables automated, scalable, and rigorous evaluation.

### 4.1 Dual-System Verification

To rigorously evaluate constraint adherence, we introduce a dual-system environment. The “Prompt System” $\mathcal{E}$ allows agents to freely execute actions based on constraints specified in natural language prompts. In parallel, we implement a “Program System” $\mathcal{E}^{\prime}$ that serves as an oracle by enforcing explicit programmatic constraint checks before executing any action. Both systems share the same toolset $\mathcal{F}$ and database state $S^{db}$.
We leverage this dual-system architecture to evaluate language agents through three distinct verification methods.

Action Constraint Verification.
During agent interaction, the Program System $\mathcal{E}^{\prime}$ monitors each service action $a^{s}$, producing a binary outcome $r^{\prime}{a^{s}}\in{0,1}$ that indicates constraint satisfaction. When the agent invokes an action $a^{s}$ while $r^{\prime}_{a^{s}}=0$, we record this as a constraint violation.

Database State Matching.
The agent’s actions affect the environment state, which is essentially the database state $S^{db}$ in AgentOrca. To ensure final outcomes are consistent, we compare the oracle database state obtained from the Program System, denoted $s^{\prime}_{N}$, with the final database state $s_{N}$ produced by the agent in the prompt system. If the agent has correctly followed verification protocols and executed only allowable actions, then $s_{N}$ should match $s^{\prime}_{N}$.

Directed Action Graph Verification.
While the agents may correctly decide whether to invoke service actions, they might bypass the required procedures through guessing. To ensure both final and intermediate states follow the proper causal sequence, we construct a directed action graph based upon mappings $M^{s}$ and $M^{v}$. In this graph, nodes represent actions and edges indicate verification prerequisites. We compare the agent’s execution trajectory $\tau_{N}$ against this graph to ensure each service action is preceded by all required verifications.

Overall Pass Rate.
In summary, the language agents interact with both systems in parallel, with the Program System monitoring each action for constraint violations and producing the oracle database state for comparison. A directed graph verifies the action sequence to prevent constraint bypassing by guessing. A case passes only when it satisfies all three verification methods, ensuring constraint adherence through explicit verification.

**Table 3: Statistics of the test data, regarding the number of service actions ($\mathcal{F}^{s}$), verification actions ($\mathcal{F}^{v}$), unique constraints ($\mathcal{C}$), average constraints per action, and total tasks for each domain.**
| Domain | $\left|\mathcal{F}^{s}\right|$ | $\left|\mathcal{F}^{v}\right|$ | $\left|\mathcal{C}\right|$ | Avg. Constr Per Action | #Tasks |
| --- | --- | --- | --- | --- | --- |
| Bank | 21 | 5 | 21 | 2.67 | 153 |
| DMV | 18 | 12 | 13 | 2.78 | 115 |
| Library | 14 | 16 | 10 | 2.07 | 78 |
| Healthcare | 11 | 7 | 22 | 3.09 | 130 |
| Market | 14 | 5 | 26 | 2.71 | 187 |
| Total | 78 | 45 | 92 | 2.65 | 663 |

**Table 4: Pass Rate of Models Across Five Domains. Overall score is averaged across all tasks from five domains. Large reasoning models are highlighted, which were evaluated only on the healthcare domain due to high costs.**
| Model | Bank | DMV | Library | Healthcare | Market | Overall |
| --- | --- | --- | --- | --- | --- | --- |
| GPT-4o (FC) | 64.71 | 80.87 | 65.38 | 73.85 | 63.64 | 69.08 |
| GPT-4o-mini (FC) | 34.64 | 70.43 | 46.15 | 26.15 | 45.99 | 43.74 |
| Claude-3-5-Sonnet (FC) | 71.90 | 50.43 | 33.33 | 39.23 | 43.32 | 49.17 |
| Gemini-2.0-Flash (FC) | 56.86 | 54.78 | 26.92 | 23.08 | 40.11 | 41.63 |
| Gemini-1.5-Pro (FC) | 54.25 | 60.00 | 26.92 | 18.46 | 34.22 | 39.37 |
| Qwen2.5-72B-Instruct (FC) | 36.60 | 45.22 | 30.77 | 28.46 | 22.99 | 31.98 |
| Llama3.1-70B-Instruct (FC) | 38.56 | 41.74 | 37.18 | 25.38 | 19.79 | 31.07 |
| o1 (FC) | - | - | - | 91.54 | - | - |
| Gemini-2.0-Flash-Thinking (ReAct) | - | - | - | 83.08 | - | - |
| Deepseek-R1 (ReAct) | - | - | - | 54.69 | - | - |

## 5 AgentOrca Benchmark Construction

We evaluate language agents using our framework across five real-world domains, as shown in Table [3](#S4.T3): Bank, DMV, Library, Healthcare, and Online Market (hereafter Market for brevity). This section describes our benchmark construction process, including the design of domain environments (tools and databases) and test case generation.

### 5.1 Domain Environment Design

For each domain scenario, we implement a Python-based environment that serves as a sandbox for agent simulation and evaluation. This environment consists of two core components: a toolset $\mathcal{F}=\mathcal{F}^{s}\cup\mathcal{F}^{v}$ (tools used in service and verification actions), and a database. We manually define each tool’s name, arguments, description, and implementation, along with the constraint set $\mathcal{C}$. Each constraint $c_{i}$ is specified with its natural language description $d_{i}$ and verification actions ($M^{v}$), and each action is mapped to its constraint composition ($M^{s}$). We also design a database template to structure the data for subsequent LM-assisted generation.
Additionally, we implement a constraint-checking module for the Program System $\mathcal{E}^{\prime}$ that handles state tracking and verification function identification.

### 5.2 LM-assisted Test Case Generation

Each test case in our evaluation targets a specific service action and assesses whether the agent correctly executes the verification routine, verifying all associated constraints and determining whether the target action should be executed.
Each test case requires two key components: a user instruction $u$ and an initial database state $s_{0}$. Together, these determine whether each constraint is satisfied and influence the final outcome. As manually creating such test cases is labor-intensive, AgentOrca leverages LLMs for automated generation.

Constraint Permutation.
We generate diverse test scenarios by systematically permuting constraint requirements for each target service action type, producing different outcomes. The LLM then generates appropriate user instructions $u$ and initial database states $s_{0}$ based on three inputs: descriptions of each constraint, whether each constraint should be satisfied, and the database template. To ensure quality, we verify the generated test cases using a rule-based format checker and validate their expected outcomes by execution in our testing environment, as illustrated in Figure [3](#S3.F3).
We use GPT-4o to generate the test cases, with an average cost of $0.014 per test case.

## 6 Experiments

### 6.1 Experimental Setup

Models.
We conduct evaluation on a comprehensive set of state-of-the-art proprietary and open-source LLMs, including large reasoning models. The proprietary models include OpenAI’s GPT-4o and large reasoning model o3-mini; Google’s Gemini-1.5-Pro and Gemini-2.0-Flash, and their large reasoning model Gemini-2.0-Flash-Thinking-Exp; and Anthropic’s Claude-3.5-Sonnet. The open-source models in our evaluation comprise Meta’s LLaMA-3.1-70B-instruct, Alibaba’s Qwen-2.5-75B-instruct, and DeepSeek’s large reasoning model DeepSeek-R1. We excluded smaller models (7B-32B parameters) due to their consistently limited performance, with pass rates lower than 20%. The results are provided in Table [4](#S4.T4).

Tool Use Methods.
We primarily focus on models that natively support function calling (FC) for tool use. For models without native FC support, we utilize ReAct (Yao et al., 2022). For comparison, we also evaluate Act-Only, a simpler approach that directly executes tool use without reasoning. Corresponding results are shown in Figure [5](#S6.F5).

Figure: Figure 4: Overall Pass Rate with Full and Oracle Tool Sets. The Full setting provides all domain actions (tools) and constraints, while Oracle provides only the user-requested action and their corresponding verification actions.
Refer to caption: /html/2503.08669/assets/x4.png

Figure: Figure 5: Performance with various tool use methods.
Refer to caption: /html/2503.08669/assets/x5.png

Available Tool Set.
As shown in Table [3](#S4.T3), each domain contains between 18 and 30 functions. By default, we provide the complete set of tools and their associated constraints to the model when handling user requests within each domain, requiring the model to independently retrieve and select appropriate tools and refer to their specified constraints. We also evaluate a simplified Oracle setting, where we provide only the tested tools and their corresponding verification tools for each case. This setting is less challenging, as it explicitly provides agents with the correct action space, eliminating the need for tool retrieval and constraint extraction. Results can be found in Figure [4](#S6.F4).

Adversarial User Simulation.
By default, user task instructions are passed as a natural language prompt to the agent, being put at the start of the interaction without further user input, focusing on the agent’s ability to follow constraints and routines independently. We also evaluate a more realistic and challenging scenario where an adversarial user agent (GPT-4o) interacts with the assistant agent, with the system instruction to persistently pursue task completion through various persuasion techniques. The results can be found in Table [5](#S6.T5).

### 6.2 Main Results

Table [4](#S4.T4) presents the performance of seven LLMs with native function calling support and three large reasoning models. Due to API costs, we evaluated large reasoning models only in the most challenging healthcare domain with 130 tasks.

Notable Gap Among FC LLMs.
From the table, GPT-4o demonstrates superior performance compared to other FC models, maintaining consistency above 60% across all domains with an overall pass rate of nearly 70%. Other models show a notable performance gap, all achieving below 50% pass rates. The two open-source models achieve only around 30% overall pass rates.

Large Reasoning Models’ Advantage.
The advanced large reasoning models (o1 and Gemini-2.0-Flash-Thinking) achieve notably high pass rates, attributed to their comprehensive planning before action execution. This indicates our tasks require strong reasoning capabilities for both constraint consideration and execution routines. However, Deepseek-R1’s lower pass rate might stem from inconsistent adherence to the specified ReAct output format, often generating extensive reasoning without properly formatted action outputs.

**Table 5: Influence of adversarial user interaction.**
| Models | w/o Adv User | w/ Adv User | $\Delta$ (%) |
| --- | --- | --- | --- |
| GPT-4o | 81.71 | 53.01 | -35.1 |
| GPT-4o-mini | 28.05 | 17.07 | -39.1 |
| Claude-3.5-Sonnet | 51.22 | 25.61 | -50.0 |

Method Comparison.
Figure [5](#S6.F5) compares performance across different tool-use methods: native FC, ReAct, and Act-only. Native FC consistently outperforms customized prompting approaches, with the gap most pronounced in Claude-3.5-Sonnet. The difference between ReAct and Act-only highlights the importance of reasoning before execution. These results, along with large reasoning models’ strong performance, emphasize the critical role of reasoning capabilities in understanding execution routines.

Figure: Figure 6: Frequencies of different error types across all tasks
Refer to caption: /html/2503.08669/assets/x6.png

Figure: Figure 7: Overall pass rate of models on task groups with different numbers of action constraints.
Refer to caption: /html/2503.08669/assets/x7.png

Influence of Provided Tool Set.
Figure [4](#S6.F4) compares model performance under two conditions: with the complete domain tool set and with only oracle tools (the requested service actions and their corresponding verification tools to check their constraints) for each test case. In the oracle scenario, where all provided tools and their constraints are relevant, LLMs achieve higher accuracy. However, when presented with the complete tool set with also extensive additional irrelevant information, requiring identification of relevant tools from a longer context, all models except GPT-4o show significant performance degradation. This demonstrates GPT-4o’s superior capability in extracting relevant information from extended contexts. These results highlight that our task requires both strong long-context processing to identify relevant action constraints and strong reasoning capabilities to infer correct execution routines.

Vulnerability to Adversarial User.
Table [5](#S6.T5) shows the model performance with standard user instructions and an adversarial user agent that persistently attempts to persuade the model to perform unauthorized tasks. The results of the healthcare domain reveal that all models, including GPT-4o, show poor performance when faced with persuasive attempts to perform unauthorized tasks. These findings highlight a critical vulnerability in current language agents against user persuasion and jailbreaking attempts, emphasizing the need for enhanced safety mechanisms.

### 6.3 Result Analysis

Performance w.r.t. Constraint Quantity.
We analyzed model performance by categorizing tasks according to the number of constraints associated with their target actions, as illustrated in Figure [7](#S6.F7). All models except GPT-4o demonstrate declining pass rates as the number of constraints increases, reflecting the growing complexity of tasks and execution routines. In contrast, GPT-4o maintains robust performance, exhibiting consistent pass rate even as constraint quantities increase. Notably, while the number of constraints serves as one dimension of task complexity, the overall challenge level is also influenced by the nature of the constraints, the characteristics of the actions, and the specific domain context.

Error Type Analysis.
Our framework assesses three distinct aspects of model performance: (1) database state matching, (2) constraint adherence and verification, and (3) routine adherence with directed action graphs. Figure [6](#S6.F6) presents the frequency distribution of these error types across all evaluated tasks, including incorrect tool usage frequency. The results reveal that while models demonstrate high accuracy in tool/function calling with minimal errors, they encounter significant challenges across the three primary error categories. Routine violations emerge as the most frequent error type, occurring when models fail to execute needed actions in incorrect routines. The second most common error involves incorrect judgment of whether the action can be taken, while database state mismatches represent the third most frequent error type, partially due to the fact that not all actions modify the database state.

## 7 Conclusion and Future Work

We present AgentOrca, a dual-system framework with automated pipeline for controllable test case generation and evaluation of language agents on the adherence to operational constraints and routines. Through comprehensive evaluation across five domains with 663 tasks, we reveal significant performance gaps among current language agents, with large reasoning models show strong performance while the start-of-the-art models that natively support function calling show much less performance except GPT-4o. We also observe agents’ vulnerability to user persuasion attempts.
In this work, we conduct a quantitative evaluation of language agents using the AgentOrca framework. For future work, we plan to extend our framework to more domains and leverage it as an environment for online reinforcement learning with real-time stepwise action rewards.

## Limitations

While much of our framework pipeline is automated, designing domain environments and validating LLM-generated data still require human efforts. In future work, we plan to further reduce manual intervention by integrating autonomous coding agent workflows into both data generation and system design. Our framework currently mainly focuses on propositional constraints for action that can be implemented and tracked by programs, though we acknowledge that there might involve more different constraint types and some of them may be more challenging to program in real-world scenarios. Nonetheless, we believe our framework and evaluation provide valuable insights into the current capabilities of language agents for adhering to operational constraints and routines.

## References

- Anthropic (2024a)
Anthropic. 2024a.
[The claude 3 model family: Opus, sonnet, haiku](https://docs.anthropic.com/en/docs/resources/model-card).
*Claude-3 Model Card*.
- Anthropic (2024b)
Anthropic. 2024b.
[Introducing computer use, a new claude 3.5 sonnet, and claude 3.5 haiku](https://www.anthropic.com/news/3-5-models-and-computer-use).
- Bengio et al. (2024)
Yoshua Bengio, Geoffrey Hinton, Andrew Yao, Dawn Song, Pieter Abbeel, Trevor Darrell, Yuval Noah Harari, Ya-Qin Zhang, Lan Xue, Shai Shalev-Shwartz, et al. 2024.
Managing extreme ai risks amid rapid progress.
*Science*, 384(6698):842–845.
- Bran et al. (2023)
Andres M Bran, Sam Cox, Oliver Schilter, Carlo Baldassari, Andrew D White, and Philippe Schwaller. 2023.
Chemcrow: Augmenting large-language models with chemistry tools.
*arXiv preprint arXiv:2304.05376*.
- Chao et al. (2024)
Patrick Chao, Edoardo Debenedetti, Alexander Robey, Maksym Andriushchenko, Francesco Croce, Vikash Sehwag, Edgar Dobriban, Nicolas Flammarion, George J Pappas, Florian Tramer, et al. 2024.
Jailbreakbench: An open robustness benchmark for jailbreaking large language models.
*arXiv preprint arXiv:2404.01318*.
- Debenedetti et al. (2024)
Edoardo Debenedetti, Jie Zhang, Mislav Balunovic, Luca Beurer-Kellner, Marc Fischer, and Florian Tramèr. 2024.
Agentdojo: A dynamic environment to evaluate prompt injection attacks and defenses for llm agents.
In *The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track*.
- Deng et al. (2024)
Xiang Deng, Yu Gu, Boyuan Zheng, Shijie Chen, Sam Stevens, Boshi Wang, Huan Sun, and Yu Su. 2024.
Mind2web: Towards a generalist agent for the web.
*Advances in Neural Information Processing Systems*, 36.
- dreampuf (2018)
dreampuf. 2018.
[Graphvizonline](https://github.com/dreampuf/GraphvizOnline).
- Dubey et al. (2024)
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshorn, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Arthur Hinsvark, Arun Rao, Aston Zhang, Aurélien Rodriguez, Austen Gregerson, Ava Spataru, Baptiste Rozière, Bethany Biron, Binh Tang, Bobbie Chern, Charlotte Caucheteux, Chaya Nayak, Chloe Bi, Chris Marra, Chris McConnell, Christian Keller, Christophe Touret, Chunyang Wu, Corinne Wong, Cristian Canton Ferrer, Cyrus Nikolaidis, Damien Allonsius, Daniel Song, Danielle Pintz, Danny Livshits, David Esiobu, Dhruv Choudhary, Dhruv Mahajan, Diego Garcia-Olano, Diego Perino, Dieuwke Hupkes, Egor Lakomkin, Ehab AlBadawy, Elina Lobanova, Emily Dinan, Eric Michael Smith, Filip Radenovic, Frank Zhang, Gabriel Synnaeve, Gabrielle Lee, Georgia Lewis Anderson, Graeme Nail, Grégoire Mialon, Guan Pang, Guillem Cucurell, Hailey Nguyen, Hannah Korevaar, Hu Xu, Hugo
Touvron, Iliyan Zarov, Imanol Arrieta Ibarra, Isabel M. Kloumann, Ishan Misra, Ivan Evtimov, Jade Copet, Jaewon Lee, Jan Geffert, Jana Vranes, Jason Park, Jay Mahadeokar, Jeet Shah, Jelmer van der Linde, Jennifer Billock, Jenny Hong, Jenya Lee, Jeremy Fu, Jianfeng Chi, Jianyu Huang, Jiawen Liu, Jie Wang, Jiecao Yu, Joanna Bitton, Joe Spisak, Jongsoo Park, Joseph Rocca, Joshua Johnstun, Joshua Saxe, Junteng Jia, Kalyan Vasuden Alwala, Kartikeya Upasani, Kate Plawiak, Ke Li, Kenneth Heafield, Kevin Stone, and et al. 2024.
[The llama 3 herd of models](https://arxiv.org/abs/2407.21783).
*arXiv preprint arXiv:2407.21783*.
- Greshake et al. (2023)
Kai Greshake, Sahar Abdelnabi, Shailesh Mishra, Christoph Endres, Thorsten Holz, and Mario Fritz. 2023.
Not what you’ve signed up for: Compromising real-world llm-integrated applications with indirect prompt injection.
In *Proceedings of the 16th ACM Workshop on Artificial Intelligence and Security*, pages 79–90.
- He et al. (2024a)
Feng He, Tianqing Zhu, Dayong Ye, Bo Liu, Wanlei Zhou, and Philip S Yu. 2024a.
The emerged security and privacy of llm agent: A survey with case studies.
*arXiv preprint arXiv:2407.19354*.
- He et al. (2024b)
Kaiyu He, Mian Zhang, Shuo Yan, Peilin Wu, and Zhiyu Zoey Chen. 2024b.
Idea: Enhancing the rule learning ability of large language model agent through induction, deduction, and abduction.
*arXiv preprint arXiv:2408.10455*.
- Hua et al. (2024)
Wenyue Hua, Xianjun Yang, Mingyu Jin, Zelong Li, Wei Cheng, Ruixiang Tang, and Yongfeng Zhang. 2024.
Trustagent: Towards safe and trustworthy llm-based agents.
In *Findings of the Association for Computational Linguistics: EMNLP 2024*, pages 10000–10016.
- Jimenez et al. (2023)
Carlos E Jimenez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik Narasimhan. 2023.
Swe-bench: Can language models resolve real-world github issues?
*arXiv preprint arXiv:2310.06770*.
- Li et al. (2024)
Zekun Li, Baolin Peng, Pengcheng He, and Xifeng Yan. 2024.
Evaluating the instruction-following robustness of large language models to prompt injection.
In *Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing*, pages 557–568.
- Liu et al. (2024)
Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, et al. 2024.
Deepseek-v3 technical report.
*arXiv preprint arXiv:2412.19437*.
- Liu et al. (2023)
Xiao Liu, Hao Yu, Hanchen Zhang, Yifan Xu, Xuanyu Lei, Hanyu Lai, Yu Gu, Hangliang Ding, Kaiwen Men, Kejuan Yang, et al. 2023.
Agentbench: Evaluating llms as agents.
*arXiv preprint arXiv:2308.03688*.
- Madmoni et al. (2024)
Lior Madmoni, Amir Zait, Ilia Labzovsky, and Danny Karmon. 2024.
The ability of large language models to evaluate constraint-satisfaction in agent responses to open-ended requests.
*arXiv preprint arXiv:2409.14371*.
- Mazeika et al. (2024)
Mantas Mazeika, Long Phan, Xuwang Yin, Andy Zou, Zifan Wang, Norman Mu, Elham Sakhaee, Nathaniel Li, Steven Basart, Bo Li, et al. 2024.
Harmbench: A standardized evaluation framework for automated red teaming and robust refusal.
*arXiv preprint arXiv:2402.04249*.
- Mu et al. (2023)
Norman Mu, Sarah Chen, Zifan Wang, Sizhe Chen, David Karamardian, Lulwa Aljeraisy, Dan Hendrycks, and David A. Wagner. 2023.
[Can llms follow simple rules?](https://arxiv.org/abs/2311.04235)
*arXiv preprint arXiv:2311.04235*.
- OpenAI (2024)
OpenAI. 2024.
[Hello gpt-4o](https://openai.com/index/hello-gpt-4o).
*OpenAI Blogs*.
- Patil et al. (2023)
Shishir G Patil, Tianjun Zhang, Xin Wang, and Joseph E Gonzalez. 2023.
Gorilla: Large language model connected with massive apis.
*arXiv preprint arXiv:2305.15334*.
- Qin et al. (2024)
Yanzhao Qin, Tao Zhang, Yanjun Shen, Wenjing Luo, Haoze Sun, Yan Zhang, Yujing Qiao, Weipeng Chen, Zenan Zhou, Wentao Zhang, et al. 2024.
Sysbench: Can large language models follow system messages?
*arXiv preprint arXiv:2408.10943*.
- Qin et al. (2023)
Yujia Qin, Shihao Liang, Yining Ye, Kunlun Zhu, Lan Yan, Yaxi Lu, Yankai Lin, Xin Cong, Xiangru Tang, Bill Qian, et al. 2023.
Toolllm: Facilitating large language models to master 16000+ real-world apis.
*arXiv preprint arXiv:2307.16789*.
- Qwen Team (2024)
Qwen Team. 2024.
[Qwen2.5: A party of foundation models](https://qwenlm.github.io/blog/qwen2.5/).
- Ruan et al. (2023)
Yangjun Ruan, Honghua Dong, Andrew Wang, Silviu Pitis, Yongchao Zhou, Jimmy Ba, Yann Dubois, Chris J Maddison, and Tatsunori Hashimoto. 2023.
Identifying the risks of lm agents with an lm-emulated sandbox.
*arXiv preprint arXiv:2309.15817*.
- Schick et al. (2023)
Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. 2023.
Toolformer: Language models can teach themselves to use tools.
*Advances in Neural Information Processing Systems*, 36:68539–68551.
- Shao et al. (2024)
Yijia Shao, Tianshi Li, Weiyan Shi, Yanchen Liu, and Diyi Yang. 2024.
Privacylens: Evaluating privacy norm awareness of language models in action.
*arXiv preprint arXiv:2409.00138*.
- Shen et al. (2024)
Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang. 2024.
Hugginggpt: Solving ai tasks with chatgpt and its friends in hugging face.
*Advances in Neural Information Processing Systems*, 36.
- Sun et al. (2024)
Wangtao Sun, Chenxiang Zhang, Xueyou Zhang, Ziyang Huang, Haotian Xu, Pei Chen, Shizhu He, Jun Zhao, and Kang Liu. 2024.
[Beyond instruction following: Evaluating rule following of large language models](https://arxiv.org/abs/2407.08440).
*arXiv preprint arXiv:2407.08440*.
- Tan et al. (2024)
Weihao Tan, Wentao Zhang, Xinrun Xu, Haochong Xia, Gang Ding, Boyu Li, Bohan Zhou, Junpeng Yue, Jiechuan Jiang, Yewen Li, et al. 2024.
Cradle: Empowering foundation agents towards general computer control.
In *NeurIPS 2024 Workshop on Open-World Agents*.
- Tang et al. (2023)
Qiaoyu Tang, Ziliang Deng, Hongyu Lin, Xianpei Han, Qiao Liang, Boxi Cao, and Le Sun. 2023.
Toolalpaca: Generalized tool learning for language models with 3000 simulated cases.
*arXiv preprint arXiv:2306.05301*.
- Team (2024)
Google Gemini Team. 2024.
[Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://arxiv.org/abs/2403.05530).
*arXiv preprint arXiv:2403.05530*.
- Wang et al. (2024)
Xingyao Wang, Boxuan Li, Yufan Song, Frank F Xu, Xiangru Tang, Mingchen Zhuge, Jiayi Pan, Yueqi Song, Bowen Li, Jaskirat Singh, et al. 2024.
Opendevin: An open platform for ai software developers as generalist agents.
*arXiv preprint arXiv:2407.16741*.
- Wen et al. (2024)
Bosi Wen, Pei Ke, Xiaotao Gu, Lindong Wu, Hao Huang, Jinfeng Zhou, Wenchuang Li, Binxin Hu, Wendy Gao, Jiaxin Xu, Yiming Liu, Jie Tang, Hongning Wang, and Minlie Huang. 2024.
[Benchmarking complex instruction-following with multiple constraints composition](https://arxiv.org/abs/2407.03978).
*arXiv preprint arXiv:2407.03978*.
- Xie et al. (2024)
Jian Xie, Kai Zhang, Jiangjie Chen, Tinghui Zhu, Renze Lou, Yuandong Tian, Yanghua Xiao, and Yu Su. 2024.
[Travelplanner: A benchmark for real-world planning with language agents](https://arxiv.org/abs/2402.01622).
In *Proceedings of the 41st International Conference on Machine Learning (ICML)*.
- Xu et al. (2023)
Can Xu, Qingfeng Sun, Kai Zheng, Xiubo Geng, Pu Zhao, Jiazhan Feng, Chongyang Tao, and Daxin Jiang. 2023.
[Wizardlm: Empowering large language models to follow complex instructions](https://arxiv.org/abs/2304.12244).
*arXiv preprint arXiv:2304.12244*.
- Yan et al. (2024)
Fanjia Yan, Huanzhi Mao, Charlie Cheng-Jie Ji, Tianjun Zhang, Shishir G. Patil, Ion Stoica, and Joseph E. Gonzalez. 2024.
Berkeley function calling leaderboard.
[https://gorilla.cs.berkeley.edu/blogs/8_berkeley_function_calling_leaderboard.html](https://gorilla.cs.berkeley.edu/blogs/8_berkeley_function_calling_leaderboard.html).
- Yang et al. (2024)
John Yang, Carlos E Jimenez, Alexander Wettig, Kilian Lieret, Shunyu Yao, Karthik Narasimhan, and Ofir Press. 2024.
Swe-agent: Agent-computer interfaces enable automated software engineering.
*arXiv preprint arXiv:2405.15793*.
- Yao et al. (2024)
Shunyu Yao, Noah Shinn, Pedram Razavi, and Karthik Narasimhan. 2024.
$\tau$-bench: A benchmark for tool-agent-user interaction in real-world domains.
*arXiv preprint arXiv:2406.12045*.
- Yao et al. (2022)
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. 2022.
React: Synergizing reasoning and acting in language models.
*arXiv preprint arXiv:2210.03629*.
- Ye et al. (2024)
Junjie Ye, Sixian Li, Guanyu Li, Caishuang Huang, Songyang Gao, Yilong Wu, Qi Zhang, Tao Gui, and Xuanjing Huang. 2024.
Toolsword: Unveiling safety issues of large language models in tool learning across three stages.
*arXiv preprint arXiv:2402.10753*.
- Zhan et al. (2024)
Qiusi Zhan, Zhixiang Liang, Zifan Ying, and Daniel Kang. 2024.
Injecagent: Benchmarking indirect prompt injections in tool-integrated large language model agents.
*arXiv preprint arXiv:2403.02691*.
- Zhang et al. (2023)
Zhexin Zhang, Leqi Lei, Lindong Wu, Rui Sun, Yongkang Huang, Chong Long, Xiao Liu, Xuanyu Lei, Jie Tang, and Minlie Huang. 2023.
Safetybench: Evaluating the safety of large language models with multiple choice questions.
*arXiv preprint arXiv:2309.07045*.
- Zheng et al. (2024)
Boyuan Zheng, Boyu Gou, Jihyung Kil, Huan Sun, and Yu Su. 2024.
Gpt-4v (ision) is a generalist web agent, if grounded.
*arXiv preprint arXiv:2401.01614*.
- Zhou et al. (2023)
Jeffrey Zhou, Tianjian Lu, Swaroop Mishra, Siddhartha Brahma, Sujoy Basu, Yi Luan, Denny Zhou, and Le Hou. 2023.
Instruction-following evaluation for large language models.
*arXiv preprint arXiv:2311.07911*.
- Zhou et al. (2024)
Ruiwen Zhou, Wenyue Hua, Liangming Pan, Sitao Cheng, Xiaobao Wu, En Yu, and William Yang Wang. 2024.
Rulearena: A benchmark for rule-guided reasoning with llms in real-world scenarios.
*arXiv preprint arXiv:2412.08972*.
- Zou et al. (2023)
Andy Zou, Zifan Wang, Nicholas Carlini, Milad Nasr, J Zico Kolter, and Matt Fredrikson. 2023.
Universal and transferable adversarial attacks on aligned language models.
*arXiv preprint arXiv:2307.15043*.

## Table of Contents

- •
[Appendix A](#A1): Broader Impact and Ethical Considerations
- •
[Appendix B](#A2): Data License
- •
[Appendix C](#A3): Extended Experimental Setup and Results
- •
[Appendix D](#A4): Overview of Domain Design
- •
[Appendix E](#A5): Representative Test Cases
- •
[Appendix F](#A6): Directional Action Graph Visualizations
- •
[Appendix G](#A7): Prompts and Instructions

## Appendix A Broader Impact and Ethical Considerations

This paper introduces a dual-system framework for evaluating LLM assistants. While our research advances the field, we acknowledge its potential societal implications:
Our work focuses on improving agent evaluation without direct risks of harm. We prohibit any applications that infringe on fundamental rights, including privacy, security, and freedom of belief. While AgentOrca primarily serves evaluation purposes, it could potentially be misused to investigate agent vulnerabilities. We encourage responsible use of this framework for improving agent safety and reliability rather than exploiting weaknesses. We only used the AI assistant in polishing the paper.

## Appendix B Data License

The dataset will be hosted on GitHub, offering reliable and secure access. We commit to maintaining the repository with regular updates, security patches, and user support to ensure the data’s integrity and usability over time. Licensing terms will be clearly communicated to users, adhering to the appropriate data licenses to promote proper usage and distribution.
The data is licensed under the CC BY 4.0 License, which permits sharing and adaptation with proper attribution.

## Appendix C Extended Experimental Details

**Table 6: API versions of the evaluated proprietary models in our experiments.**
| Model | API version |
| --- | --- |
| o1 | o1-2024-12-17 |
| GPT-4o | gpt-4o-2024-08-06 |
| GPT-4o-mini | gpt-4o-mini-2024-07-18 |
| Claude-3.5-Sonnet | claude-3-5-sonnet-20241022 |
| Gemini-2.0-Flash | gemini-2.0-flash-001 |
| Gemini-1.5-Pro | gemini-1.5-pro |
| Gemini-2.0-Flash-Thinking | gemini-2.0-flash-thinking-exp |

### C.1 Inference Details

The specific API versions of evaluated proprietary models are shown in Table  [6](#A3.T6). For inference, we set temperature to 0.0 and top_p to 0.01 and conduct a single run. For the adversarial user agent, we set both temperature and top_p to 1.0 to encourage diverse persuasion attempts.

### C.2 Extended Experimental Results

Table [7](#A3.T7) presents the domain-specific performance for different tool sets (overall pass rates shown in Figure  [4](#S6.F4)). Figure  [8](#A3.F8) shows the domain-specific performance for different tool use methods (overall pass rates shown in Figure  [5](#S6.F5)).

**Table 7: Breakdown of model performance across different domains with different provided tool list.**
| Models | Tool List | Bank | DMV | Library | Healthcare | Market | Overall |
| --- | --- | --- | --- | --- | --- | --- | --- |
| GPT-4o (FC) | Full | 64.71 | 80.87 | 65.38 | 73.85 | 63.64 | 69.08 |
| GPT-4o-mini (FC) | Full | 34.64 | 70.43 | 46.15 | 26.15 | 45.99 | 43.74 |
| Claude-3.5-sonnet (FC) | Full | 71.90 | 50.43 | 33.33 | 39.23 | 43.32 | 49.17 |
| Gemini-2.0-Flash (FC) | Full | 56.86 | 54.78 | 26.92 | 23.08 | 40.11 | 41.63 |
| Gemini-1.5-Pro (FC) | Full | 54.25 | 60.00 | 26.92 | 18.46 | 34.22 | 39.37 |
| Qwen2.5-72B-Instruct (FC) | Full | 36.60 | 45.22 | 30.77 | 28.46 | 22.99 | 31.98 |
| Llama3.1-70B-Instruct (FC) | Full | 38.56 | 41.74 | 37.18 | 25.38 | 19.79 | 31.07 |
| GPT-4o (FC) | Oracle | 81.05 | 85.22 | 65.38 | 76.15 | 80.21 | 78.73 |
| GPT-4o-mini (FC) | Oracle | 52.29 | 81.74 | 73.08 | 78.46 | 68.98 | 69.68 |
| Claude-3.5-sonnet (FC) | Oracle | 79.74 | 78.26 | 58.97 | 80.77 | 65.78 | 73.30 |
| Gemini-2.0-Flash (FC) | Oracle | 73.20 | 73.91 | 66.67 | 61.54 | 65.78 | 68.17 |
| Gemini-1.5-Pro (FC) | Oracle | 74.51 | 76.52 | 56.41 | 63.85 | 62.03 | 67.12 |
| Qwen2.5-72B-Instruct (FC) | Oracle | 72.54 | 80.87 | 60.26 | 63.08 | 60.43 | 67.27 |
| Llama3.1-70B-Instruct (FC) | Oracle | 60.78 | 61.74 | 50.00 | 53.08 | 41.71 | 52.79 |

Figure: Figure 8: Model Performance with different tool use approaches.
Refer to caption: /html/2503.08669/assets/x8.png

## Appendix D Domain Actions and Constraints

We describe the domains explored in AgentOrca, including their actions and constraints. Actions are categorized into: Service Actions, which provide user services, and Verification Actions, which verify or retrieve information. Actions with the prefix "internal" are reserved for assistant use only. Each action has a default constraint composition that must be followed, and each constraint has an associated verification actions for verification.
Note that not all constraints require action verification. For example, comparing the data time can be done through reasoning alone.

### D.1 Bank

Our Bank domain emulates typical banking operations and constraints, focusing on account balance management, account operations, and associated permissions. Refer to:

- •
Bank Action Descriptions: Table  [8](#A4.T8)
- •
Bank Action Constraint Compositions: Table  [9](#A4.T9)
- •
Bank Constraint Descriptions: Table  [10](#A4.T10)
- •
Bank Constraint to Verification Action Mapping: Table  [11](#A4.T11)

### D.2 DMV

Our DMV domain simulates Department of Motor Vehicles operations, focusing on vehicle registration, license processing, and test scheduling with their associated verification requirements. Refer to:

- •
DMV Action Descriptions: Table  [12](#A4.T12)
- •
DMV Action Constraint Compositions: Table  [13](#A4.T13)
- •
DMV Constraint Description: Table  [14](#A4.T14)
- •
DMV Constraint to Verification Action Mapping: Table  [15](#A4.T15)

### D.3 Healthcare

Our Healthcare domain simulates health insurance operations, focusing on policy management, claims processing, and provider interactions, with strict adherence to policy limits and eligibility requirements. Refer to:

- •
Healthcare Action Descriptions: Table  [16](#A4.T16)
- •
Healthcare Action Constraint Compositions: Table  [17](#A4.T17)
- •
Healthcare Constraint Descriptions: Table  [18](#A4.T18)
- •
Healthcare Constraint to Verification Action Mapping: Table  [19](#A4.T19)

### D.4 Library

Our Library domain models library operations, focusing on book services, financial transactions, and facility management, with constraints on membership, borrowing limits, and resource availability. Refer to:

- •
Library Action Descriptions: Table  [20](#A4.T20)
- •
Library Action Constraint Compositions: Table  [21](#A4.T21)
- •
Library Constraint Descriptions: Table  [22](#A4.T22)
- •
Library Constraint to Verification Action Mapping: Table  [23](#A4.T23)

### D.5 Online Market

Our Online Market domain models e-commerce operations, focusing on order management, product transactions, and customer service, with constraints on inventory, promotions, and return policies. Refer to:

- •
Online Market Action Descriptions: Table  [24](#A4.T24)
- •
Online Market Action Constraint Compositions: Table  [25](#A4.T25)
- •
Online Market Constraint Descriptions: Table  [26](#A4.T26)
- •
Online Constraint to Verification Action Mapping: Table  [27](#A4.T27)

Table: Table 8: Bank Action Descriptions

Table: Table 9: Bank Action Constraint Compositions

Table: Table 10: Bank Constraint Descriptions

Table: Table 11: Bank Constraint to Verification Action Mapping

Table: Table 12: DMV Action Descriptions

Table: Table 13: DMV Action Constraint Compositions

Table: Table 14: DMV Constraint Descriptions

Table: Table 15: DMV Constraint to Verification Action Mapping

Table: Table 16: Healthcare Action Descriptions

Table: Table 17: Healthcare Action Constraint Compositions

Table: Table 18: Healthcare Constraint Descriptions

Table: Table 19: Healthcare Constraint to Verification Action Mapping

Table: Table 20: Library Action Descriptions

Table: Table 21: Library Action Constraint Compositions

Table: Table 22: Library Constraint Descriptions

Table: Table 23: Library Constraint to Verification Action Mapping

Table: Table 24: Online Market Action Descriptions

Table: Table 25: Online Market Action Constraint Compositions

Table: Table 26: Online Market Constraint Descriptions

Table: Table 27: Online Market Constraint to Verification Action Mapping

## Appendix E Representative Cases

We present examples from our dataset, each of which we demonstrate the three components: task setup, interaction simulation, and evaluation results.

### E.1 Task Setup

The task setup illustrates the necessary components for evaluation, including initial database state, user information, and constraint compositions. Some components, such as the user prompt, are used to prompt the user simulator. Others, such as the directed action graph, are used for evaluating whether the assistant properly verifies constraints. Given the initial task setup information, the task determines whether task execution should succeed or not.

### E.2 Agent Trajectory

The agent trajectory displays the interaction. The full prompt used to prompt the assistant is omitted, included later in Appendix section  [G](#A7). Our main experimental setup involves prompting the assistant with all the necessary information, then allowing the assistant to call tools one after another. The final database from the interaction is saved for later evaluation.

### E.3 Evaluation Results

We demonstrate our evaluation metrics, which focuses on three key aspects: constraint adherence, database state consistency, and action graph compliance. We also track tool usage errors and action call correctness.

### E.4 Full Examples

In this section, we demonstrate full examples of our experiment, from task setup to interaction simulation to evaluation. We also offer brief summaries of the task setup and interaction, as well as a short explanation of the evaluation result.

- •
Example where the assistant (GPT-4o) checked the constraints correctly and called the appropriate functions: Listing  [9](#A5.F9)
- •
Example where the assistant (Claude 3.5 Sonnet) did not check the constraints correctly: Listing  [10](#A5.F10)
- •
Example where the assistant (Claude 3.5 Sonnet) checked the constraints, and proceeded correctly: Listing  [11](#A5.F11)
- •
Example where the assistant (Gemini 2.0 Flash) failed because it did not call the target service action: Listing  [12](#A5.F12)
- •
Example where the assistant (o1) successfully finds that claim is not within the coverage amount: Listing  [13](#A5.F13)
- •
Example where the assistant (Gemini-2.0-Flash-Thinking) calls the action incorrectly despite extensive analysis: Listing  [14](#A5.F14)
- •
Example where the assistant (Gemini-2.0-Flash) does not check constraint before executing the action: Listing  [15](#A5.F15)

Figure: Example where the assistant (GPT-4o) checked the constraints correctly and called the appropriate functions. The assistant successfully logged in the user, authenticated the admin password, and ensured the user had sufficient funds before transferring the requested amount. The assistant succeeded in every aspect of our evaluation. The directed action graph is visualized at Figure [16](#A6.F16)

Figure: Example where the assistant (Claude 3.5 Sonnet) did not check the constraints correctly. The assistant failed to check the user’s membership status after verifying that the book was restricted. The assistant should not lend a restricted book to a user without membership.

Figure: Example where the assistant (Claude 3.5 Sonnet) correctly checked the user’s membership after finding the book to be restricted.

Figure: Example where the assistant (Gemini 2.0 Flash) checked the constraints and did not reach the target action. The assistant was overly careful and reached the interaction limits before processing the scheduling request, though it processed intermediate steps properly.

Figure: Example where the assistant (o1) successfully reasoned that the user had exceeded the maximum claim coverage amount and denied the user’s request to update policy.

Figure: Example where the assistant (Gemini 2.0 Flash Thinking) accurately analyzed the complex dependencies; however, it erroneously proceeded with executing the action despite the reasoning.

Figure: Example where the assistant (Gemini 2.0 Flash) does not check the constraint before executing the action, missing the error that there is insufficient stock for a product exchange.

## Appendix F Direction Action Graph Visualization

In this section, we visualize examples of directed action graphs of various actions spread across our five domains using GraphViz dreampuf (2018). The more complex actions have larger graphs. Refer to:

- •
Bank Domain transfer_funds Action: Figure  [16](#A6.F16)
- •
DMV Domain renew_dl Action: Figure  [17](#A6.F17)
- •
Healthcare Domain submit_claim Action: Figure  [18](#A6.F18)
- •
Library Domain borrow_book Action: Figure  [19](#A6.F19)
- •
Online Market Domain exchange_product Action: Figure  [20](#A6.F20)

Figure: Figure 16: Bank Domain transfer_funds Action, same one from the representative case Listing [9](#A5.F9)
Refer to caption: /html/2503.08669/assets/pics/apdx_bank_transferfunds.png

Figure: Figure 17: DMV Domain renew_dl Action
Refer to caption: /html/2503.08669/assets/pics/apdx_dmv_transfertitle.png

Figure: Figure 18: Healthcare Domain submit_claim Action
Refer to caption: /html/2503.08669/assets/pics/apdx_healthcare_submitclaim.png

Figure: Figure 19: Library Domain borrow_book Action
Refer to caption: /html/2503.08669/assets/pics/apdx_library_borrowbook.png

Figure: Figure 20: Online Market Domain exchange_product Action
Refer to caption: /html/2503.08669/assets/pics/apdx_onlinemarket_exchangeproduct.png

## Appendix G Prompts

In this section, we present system prompts containing action constraint descriptions used to instruct agents across various domains. We’ve included a sample prompt for task generation, the ReAct format prompt, and the prompt for simulating adversarial users.

Here are our prompts:

- •
Bank Assistant Prompt: Listing  [21](#A7.F21)
- •
DMV Assistant Prompt: Listing  [22](#A7.F22)
- •
Healthcare Assistant Prompt: Listing  [23](#A7.F23)
- •
Library Assistant Prompt: Listing  [24](#A7.F24)
- •
Online Market Assistant Prompt: Listing  [25](#A7.F25)
- •
Task Generation Prompt: Listing  [26](#A7.F26)
- •
ReAct Prompt: Listing  [27](#A7.F27)
- •
Adversarial User Prompt: Listing  [28](#A7.F28)

Figure: Bank Assistant Prompt

Figure: DMV Assistant Prompt

Figure: Healthcare Assistant Prompt

Figure: Library Assistant Prompt

Figure: Online Market Assistant Prompt

Figure: Task Generation Prompt

Figure: ReAct Prompt

Figure: Adversarial User Prompt

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: - Can the current pipeline be scaled to some real scenarios with a large amount of rules and complex dependency between functions?

- The test cases are structured based on the tools and constraints, but how were the free-text user inputs generated? In addition, can the user inputs include “outlier” intents that involve constraints outside the predefined tool and constraint space?
soundness: 3
strengths: - The benchmark is large-scale and diverse, covering 167 executable tool functions, and 830 test cases from 7 customer-service domains. The authors also evaluate the benchmark with 18 leading models.

- The paper highlights that even current leading models struggle with some tasks and domains, which indicates that SOP control remains challenging, and the benchmark is both relevant and impactful.

- The paper also shows the vulnerabilities of current models to malicious jailbreaking, and found that easy jailbreaking can success on overlooking SOPs and constraints, which inspire safety studies using this benchmark.

- The work formalizes SOPs as directed action graphs and proposes a three-level evaluation methodology, which can provide multiple perspectives for evaluation to following studies; and the code-based verifiers provide the foundation for future work in RLVR.

- The extensive experiments regarding different metrics on different domains, models, adversarial attacks, tool use methods, and service tasks, further demonstrates the diversity of the benchmark, which can benefit various research in the community.

- The paper is well-written and well-organized, with intuitive figures and helpful examples that make it straightforward to understand.
summary: Since the research about the current language agent system perform on complying standard operating procedures (SOPs), policies, and constraints is limited, this paper aims to address the underexplored problem and introduces an automated evaluation pipeline, SOPBench. This pipeline measures procedural compliance across multi-step tool-use tasks. It constructs a benchmark consists of sandboxed environments, automated test generation, and evaluation mechanism. The authors conduct extensive experiments to evaluate the benchmarks with leading models and provide valuable insights. The release of this benchmark can benefit future research.
weaknesses: - The domains can be more diverse to include some industry domains with more complex and messier SOPs and constraints, i.e., requiring larger amounts of service/helper functions and constraints.

- It could be better to categorize these tasks into different levels of difficulty.

- It may be beneficial to also show the statistics of average or deepest constraint dependency across domains, and provide additional analysis regarding how the constraint complexity impacts.

---

confidence: 4
contribution: 2
initial_rating: 4
presentation: 2
questions: - How is evaluation done with temp = 0 when models like GPT-5 do not support temperature? 
- Since the constraints can be translated into a code program, how is the performance if the LLM is asked to generate code for constraint verification?
soundness: 3
strengths: - Benchmark tackles an important problem of SOP following, which is required for agents to be useful in the real-world  
- Scalable and reproducible methodology for automatically generating and validating test cases 
- Comprehensive and reliable evaluation using oracle code programs
- Experimental results demonstrate the benchmark complexity and room for future research
- Performance degradation with a simple jailbreaking approach highlights the brittleness of modern LLMs on this task
summary: The paper presents SOPBENCH, a benchmark for evaluating LLM agents on following.standard operating procedures and constraints. The benchmark is created by first manually defining an environment sandbox for seven domains. The sandbox consists of a set of constraints, 70 service functions and 97 helper functions that can be used to complete the tasks and verify constraints, a database schema containing the necessary information for constraint verification. Based on the environment sandbox, 830 test cases are generated using LLMs and verified using rule-based verifiers. Evaluation is conducted based on three criteria that can be measured using oracle code programs, namely outcome-level verification that verifies the final database state, step-level verification that verifies the constraint permissibility of each function called by the agent, and trajectory-level verification that verifies whether all the verification steps are completed in the correct order. Experimental results show that even SOTA models such as o4-mini-high struggle particularly on more challenging domains like hotel.
weaknesses: - At its core, the task seems similar to structured tool calling. It is unclear as to what differentiates this benchmark from tool calling benchmarks, such as Berkley Function Calling Leaderboard that also conduct state-based evaluation and check whether the model’s function call trajectory includes the minimum necessary path. So, the core novelty of this benchmark, at least in the current scope of composition types, is limited.
- There is some inconsistency between Figures 7 and 11. For example, "show_available_rooms" has almost 0 success rate as per Figure 7 but Figure 11 shows high success for this service task.
- Limited error analysis. While the paper shows the model performance breakdown by evaluation criteria in Figure 8, and one example erroneous trajectory in the Appendix, it is still unclear why leading models fail. Also, what makes domains like Hotel more challenging?

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 3
questions: My major question is if a task is governed by a well-defined SOP or protocol, is it necessary—or even optimal—to use a Large Language Model (LLM) to perform it, rather than simply encoding the SOP directly in code? Take the minor declaration task shown in Fig. 2 as an example, would the task be solved more easily by creating a functionality in the university admin website which can let the students just select the minor they want to declare, and do all those checks in the backend database? IMHO, creating this functionality by coding with the assistance of LLM could be more efficient and straightforward than going through the LLM agent. 

My other minor questions are
Can you elaborate on the criteria used to select SOPs and domains for inclusion in SOPBench?

How does SOPBench handle ambiguous or conflicting SOPs in real-world scenarios?

How does SOPBench compare to existing agent evaluation benchmarks in terms of coverage and difficulty?
soundness: 3
strengths: Originality: The focus on SOP adherence is novel and underexplored in existing benchmarks.
Quality: The automated, rule-based evaluation framework is robust and scalable.
Clarity: The methodology and results are clearly presented.
Relevance: The benchmark and findings are highly relevant for the development and deployment of reliable language agents.
summary: This paper introduces SOPBench, an automated evaluation pipeline designed to assess language agents' ability to follow domain-specific standard operating procedures (SOPs), policies, and constraints. SOPBench features executable environments with 167 tools/functions across seven customer service domains, an automated test generation framework with over 900 verified test cases, and a rigorous evaluation framework. The approach transforms SOP code into directed graphs of executable functions, requiring agents to act based on natural language SOP descriptions. The original code serves as oracle rule-based verifiers, reducing reliance on manual annotation. The authors evaluate 18 leading models, finding that even top-tier models struggle with SOP adherence, and that agents are susceptible to jailbreaking. The dataset and code are released for further research.
weaknesses: The paper could provide more analysis on why certain models fail specific SOPs and constraints.

Limited discussion on the generalizability of SOPBench to domains beyond customer service.

The susceptibility to jailbreaking is noted, but mitigation strategies are not explored in depth.

Some experimental details (e.g., SOP selection criteria, test case diversity) could be expanded.

---

confidence: 4
contribution: 2
initial_rating: 4
presentation: 3
questions: See weaknesses.
soundness: 3
strengths: 1. The development of a novel evaluation pipeline using executable SOP code as oracle verifiers enhances the reliability and objectivity of assessing agent compliance, reducing dependence on subjective human or LLM-based judgments. This approach ensures consistent and scalable evaluation across diverse scenarios, making it a robust tool for future research.  

2. The inclusion of 167 executable tools and 70 service-specific SOPs across seven customer service domains provides a comprehensive and realistic testing ground, covering areas like banking and healthcare. This breadth allows for a thorough assessment of agent capabilities, revealing domain-specific challenges and opportunities for improvement.  

3. The multi-level verification process, including outcome, step, and trajectory-level checks, offers a detailed analysis of agent adherence to SOPs, capturing both final results and procedural accuracy. This granularity provides valuable insights into agent decision-making, aiding in the identification of specific weaknesses.  

4. The release of code, data, and over 24k agent trajectories fosters transparency and enables the research community to replicate and build upon the findings. This open-access strategy promotes collaboration and accelerates advancements in language agent development.
summary: The paper introduces SOPBench, a benchmark designed to evaluate the ability of language agents to follow standard operating procedures (SOPs) and constraints in customer service domains. It addresses the growing need for agents to adhere to domain-specific procedural guidelines, a capability underexplored in existing evaluations. The approach includes sandbox environments with 167 executable tools across seven domains, an automated test generation framework creating over 800 test cases, and a multi-level evaluation harness using oracle code as verifiers. The study finds that even top-tier models like o4-mini-high struggle, with pass rates around 30% in challenging domains, and highlights vulnerabilities to jailbreaking, emphasizing the need for improved adherence in high-stakes environments.
weaknesses: 1. The reliance on manually implemented sandbox environments and SOPs across seven domains may introduce potential biases or inconsistencies, as human design could overlook certain real-world complexities. This limitation might affect the generalizability of the results to less structured or more dynamic settings.  

2. The benchmark's focus on customer service domains, while comprehensive, may not fully represent the diversity of tasks in other critical areas like healthcare diagnostics or legal processes, potentially limiting its applicability. This narrow scope could miss unique procedural challenges in those fields.  

3. The finding that top-tier models achieve pass rates below 70% in challenging domains indicates that the benchmark's difficulty may exceed current model capabilities, potentially discouraging progress rather than guiding it. This high difficulty could lead to frustration rather than constructive development.  

4. The lack of detailed analysis on the impact of different tool-calling methods (e.g., ReAct vs. Act-Only) beyond basic comparisons limits insights into optimizing agent performance, leaving a gap in understanding how methodological choices affect SOP adherence. This omission could hinder tailored improvements for specific models.


Decision: Reject