Paper deep dive

PolicyGuide: From Guarding One Action to Guiding the Whole Workflow for Policy-Compliant LLM Agents

Seongjae Kang, Taehyung Yu, Sung Ju Hwang

Year: 2026Venue: arXiv preprintArea: cs.AIType: PreprintEmbeddings: 107

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%

Last extracted: 8/21/2026, 3:46:34 AM

Summary

PolicyGuide is an external runtime safeguard for LLM agents that compiles domain policies into workflow graphs to ensure policy compliance. Unlike action-local guards, it proactively verifies multi-step procedures at user-turn boundaries, guiding agents through required steps and preventing policy violations. Evaluated on the τ²-bench across airline, retail, and telecom domains, it significantly improves compliance rates (Pass⁴) compared to unguided agents and other baselines like PolicyGuard.

Entities (10)

PolicyGuide · system · 100%Airline · domain · 95%Retail · domain · 95%Telecom · domain · 95%τ-bench · benchmark · 95%Claude Sonnet 4.6 · model · 90%Gemini 2.5 Pro · model · 90%GPT-5.4 · model · 90%PolicyGuard · system · 90%CRAFT · benchmarkmethod · 85%

Relation Signals (8)

PolicyGuide → improvescomplianceon → τ-bench

confidence 95% · PolicyGuide raises mean Pass⁴ from 0.42 to 0.62 across the τ²-bench domains.

PolicyGuide → supportsagents → GPT-5.4

confidence 95% · with a GPT-5.4 agent and verifier

PolicyGuide → usesmethod → workflow_graph

confidence 95% · PolicyGuide instead compiles each domain policy into a workflow graph

PolicyGuide → outperforms → PolicyGuard

confidence 90% · PolicyGuide raises mean Pass⁴... PolicyGuard... Pass⁴ 0.360 (Retail) vs PolicyGuide 0.614

Telecom → showslargestgain → PolicyGuide

confidence 90% · largest gain on telecom (0.19 to 0.61), the most workflow-structured domain.

PolicyGuide → supportsagents → Gemini 2.5 Pro

confidence 90% · The same workflows transfer to... Gemini 2.5 Pro agents.

PolicyGuide → supportsagents → Claude Sonnet 4.6

confidence 90% · The same workflows transfer to Claude Sonnet 4.6

PolicyGuide → evaluatedwith → CRAFT

confidence 85% · Complementary evaluations find the lowest observed attack-success rate under adversarial users... CRAFT red-teaming

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:Customer-service LLM agents must follow organizational policy when acting on a user's behalf. Compliance failures arise from either forbidden actions, such as granting an ineligible change, or omitted procedural requirements, such as identification or confirmation. Runtime safeguards can intervene on risky actions, but action-local checks do not guide an agent through a multi-step procedure. Workflow-following systems support prescribed process execution, but primarily target workflow completion rather than safeguarding agent behavior. PolicyGuide instead compiles each domain policy into a workflow graph and invokes a proactive verifier at user-turn boundaries. From persisted graph state, the verifier reconciles open requests and returns step-specific remediation along a policy-compliant path. Across the $\tau^2$-bench airline, retail, and telecom domains with a GPT-5.4 agent and verifier, PolicyGuide raises mean $\mathrm{Pass}^4$ from $0.42$ to $0.62$, with the largest gain on telecom ($0.19$ to $0.61$), the most workflow-structured domain. The same workflows transfer to Claude Sonnet 4.6 and Gemini 2.5 Pro agents. Complementary evaluations find the lowest observed attack-success rate under adversarial users and the strongest procedural compliance in an author-designed workflow-level validation.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

103,451 characters extracted from source content.

Expand or collapse full text

PolicyGuide: From Guarding One Action to Guiding the Whole Workflow for Policy-Compliant LLM Agents Seongjae Kang Affiliation: KAIST Taehyung Yu Affiliation: KAIST Sung Ju Hwang Affiliation: KAIST Affiliation: DeepAuto.aitjdwo2744, taehyung.yu, sjhwang@kaist.ac.kr Abstract Customer-service LLM agents must follow organizational policy when acting on a user’s behalf. Compliance failures arise from either forbidden actions, such as granting an ineligible change, or omitted procedural requirements, such as identification or confirmation. Runtime safeguards can intervene on risky actions, but action-local checks do not guide an agent through a multi-step procedure. Workflow-following systems support prescribed process execution, but primarily target workflow completion rather than safeguarding agent behavior. PolicyGuide instead compiles each domain policy into a workflow graph and invokes a proactive verifier at user-turn boundaries. From persisted graph state, the verifier reconciles open requests and returns step-specific remediation along a policy-compliant path. Across the τ2τ^2-bench airline, retail, and telecom domains with a GPT 5.4 agent and verifier, PolicyGuide raises mean Pass4 Pass^4 from 0.420.42 to 0.620.62, with the largest gain on telecom (0.190.19 to 0.610.61), the most workflow-structured domain. The same workflows transfer to Claude Sonnet 4.6 and Gemini 2.5 Pro agents. Complementary evaluations find the lowest observed attack-success rate under adversarial users and the strongest procedural compliance in an author-designed workflow-level validation. 1 Introduction Unguided agentBase agentNeither guides norexternally safeguardsAction verifiersPolicyGuard, ToolGuardExternally check and gatethe proposed actionWorkflow / SOP agentsSOP-Agent, StateFlow, FlowAgentFollow a prescribedprocedurePolicyGuide (ours)External workflow safeguardGuides required stepsand gates actionsExternal safeguarding — Monitors agent behaviorWorkflow enforcement — Guides the required procedure Figure 1: Workflow systems execute prescribed procedures, while external safeguards monitor agent behavior. PolicyGuide combines both roles. (a) Action guard: one pass/block at the final call User: change my flight to HAT228 Agent: skips identify, eligibility, confirmation update_ res._flights (...) Agent: re-derives procedure from the error loops / wrong recovery guard Inactive: skipped steps are not evaluated BLOCK at the final call: unmet prerequisites are reported only after the procedure has failed (b) Workflow / SOP agent: workflow execution is part of the agent User: change my flight to HAT228 Agent: follows the prescribed workflow Agent: completes the required checks update_ res._flights (...) procedure completed (agent-integrated) Workflow control is implemented within the agent runtime Its checks support faithful workflow execution within that runtime (c) PolicyGuide (ours): guide generation at user-turn boundaries, walking the policy graph User: change my flight to HAT228 Agent: asks for the user id Agent: get_user_ details ✓ Agent: checks eligibility, presents summary User: confirms “yes” update_res._ flights(...) ✓ task completed in policy guide (user turns; workflow safeguards) ① User turn: identify the user first ② User turn: load the record, verify eligibility, present the change, and request confirmation ③ User confirms: prerequisites met; mutation recommended with grounded arguments Figure 2: One task under three enforcement regimes. (a) An action guard checks only the final mutating call, so skipped procedure is discovered late and returned as a block. (b) A workflow/SOP agent drives the procedure, but its checks are designed for faithful workflow execution rather than as a safeguard against policy-violating behavior by a general-purpose agent. (c) PolicyGuide runs as an external, advisory guide: at user-turn boundaries it tracks graph position across turns and stops at the first unsatisfied node. If the agent attempts a mutating tool call before completing the workflow, the runtime returns remediation for the unmet step. It recommends the mutation only after the required workflow steps are grounded. LLM agents are beginning to support customer-service work, including booking flights, modifying orders, and changing account plans through tools on user accounts. These systems typically pair a general-purpose reasoning-and-acting loop (34) with a frontier model such as GPT 5.4, Claude Sonnet 4.6, or Gemini 2.5 Pro (19; 2; 7). Because these models are large and closed-weight, domain-specific fine-tuning is often unavailable or impractical; runtime safeguards offer an integration point that does not require retraining. τ-bench (33) and τ2τ^2-bench (4) evaluate this setting against natural-language policies in Airline, Retail, and Telecom. Policy compliance depends on both the selected action and the procedure used to reach it. An agent may grant an ineligible change, or it may skip or misorder identification, eligibility checks, and confirmation. Such procedural failures can produce a forbidden outcome or leave an otherwise permissible action unsupported. Our source-policy analysis (Appendices B and B.5) finds that procedural requirements are pervasive (67.4%67.4\% in airline, ∼100% 100\% in retail, and 98.0%98.0\% in telecom), whereas ordered workflow requirements concentrate in telecom (54.0%54.0\%, versus 4.7%4.7\% in airline and 3.6%3.6\% in retail). Flat prerequisites can often be checked when the agent proposes a guarded action, such as a mutating tool call. Ordered requirements also constrain earlier dialogue and tool-use actions. For example, telecom troubleshooting follows diagnose–instruct–verify sequences that may contain no agent-side mutation for an action guard to intercept. These two failure modes motivate complementary capabilities (Figure 1). Safeguarding monitors agent behavior and intervenes on risky actions (37; 6; 31), whereas workflow enforcement steers execution through required steps (35; 30; 25). The two literatures thus target different primary objectives: safe agent behavior and faithful workflow completion. PolicyGuard (11) provides the closest connection by incorporating procedural remediation into a mutating-call safeguard, but remains action-triggered and cannot cover earlier deviations outside its guarded action class. We propose PolicyGuide, an external runtime guide for policy-compliant agents (Figure 2). PolicyGuide compiles each domain policy into a workflow graph. At user-turn boundaries, a proactive verifier traverses the graph from its persisted position, reconciles all open requests, and returns focused remediation for the first unmet step. Persisted state lets the verifier apply workflow safeguards throughout the interaction while coordinating multiple requests. The result is an agent-agnostic external overlay that pairs the same procedural representation with different agents. Across the τ2τ^2-bench airline, retail, and telecom domains with a GPT 5.4 agent and verifier, PolicyGuide raises mean Pass4 Pass^4 across domains from 0.420.42 (unguided) to 0.620.62 (§4.2), with the largest gain on telecom (0.190.19 to 0.610.61), the domain whose policy is most workflow-structured. We additionally evaluate diagnostic workflow variants and a matched FlowAgent workflow-controller baseline on telecom (§4.3–4.4). The same workflows transfer to Claude Sonnet 4.6 and Gemini 2.5 Pro agents (§4.5). We further evaluate adversarial robustness with CRAFT red-teaming and workflow compliance with an author-designed Telecom trace audit (§4.6 and §4.7). Contributions. • We characterize policy compliance as a joint safeguarding and workflow-enforcement problem: agents must avoid impermissible actions while completing required procedural steps, including those occurring before or outside a guarded action class. • We introduce PolicyGuide, an external proactive verifier that compiles policies into workflow graphs, tracks multiple open requests across turns, and guides the agent through the required steps. • We demonstrate 20-point mean Pass4 Pass^4 gains and cross-agent transfer. Complementary analyses show robustness to CRAFT red-team attacks and stronger workflow compliance. 2 Background and Related Work PolicyGuide connects runtime safeguards, which monitor agent behavior, with workflow-guided systems, which execute prescribed procedures. It gives persisted workflow state a safeguarding role over agent behavior rather than making workflow control the agent architecture; separating verifier from actor additionally enables reuse across agent runtimes (Figure 1). 2.1 τ2τ^2-bench and policy-adherent agents τ2τ^2-bench (4), building on τ-bench (33), benchmarks policy-adherent LLM agents in customer-service domains with a natural-language policy, read-only tools, and mutating tools. We use the airline, retail, and telecom domains: each task is either policy-violation (the agent must refuse) or mutation (the agent must act correctly), and success requires both the final database state and the natural-language assertions to hold. Telecom adds dual control, where some required actions are user-side tools the agent cannot call, making workflow order especially visible. Nearby benchmarks target complementary questions: CRMArena-Pro studies confidentiality compliance rather than ordered procedures (10); IntellAgent generates diagnostic tests from policy graphs (13); Near-Miss audits failures post hoc (21); AgentRewardBench evaluates trajectory judges (15); and CRAFT supplies adversarial users rather than a benign workflow-completion benchmark (18). A. Offline workflow authoringPolicy + toolsraw policy texttool registryPlan request typestaxonomyshared proceduresGeneratemain graph+ subflowsRepairschema andcross-flow issuesValidatecoverage, tools,reachabilityWorkflow bundlemain + subflowsnode criteriaB. Online policy-guided runtimeRuntime inputs History and state at verifier fire User “Change flight to HAT228.” Guide (previous) Load the reservation first. Tool result Fare class: Basic Economy User (latest) “Can you change it now?” Saved request change flight; check_eligibility Workflow bundle (from A) criteria, transitions, tool gates Proactive verifier Reconcile every open request, traverse from its saved node, and gate policy-sensitive actions 1. Reconcile track open requests 2. Traverse test grounded evidence 3. Decide stop, advance, or authorize workflow identify load eligible? confirm authorize verify ✓ identify_user.load_profile✓ modify_flow.load_reservation✗ modify_flow.check_eligibilitySATSATSTOP First unmet requirement: the fare is ineligible for modification. Keep the request at check_eligibility; do not authorize the mutation. Runtime outputs Result returned to the runtime Remediation Refuse the change and cite the Basic Economy restriction. Next agent turn Apply the remediation; no mutating tool is exposed. Updated request state node: check_eligibility status: open Mutation gate closed persist for the next user turn Figure 3: PolicyGuide separates offline policy authoring from online enforcement. Offline, the policy and tool registry are compiled, repaired, and validated into a reusable workflow bundle. Online, each verifier call consumes the conversation, grounded tool results, persisted request state, and workflow bundle; it reconciles requests, traverses the graph to the first unmet requirement, and returns remediation, updated state, and mutation-gate status for the next agent turn. 2.2 Runtime safeguards: action verification Runtime safeguards are usually action-scoped. ToolGuard compiles tool-level guards, and Solver-Aided checks call constraints with solver support (29); both see only the call under check, so process-level requirements are unreachable. PCAS monitors event traces (20), while ShieldAgent wraps agents with structural safety checks (6); both track order but reduce dialogue semantics to predicates or keyword matching. GuardAgent is a single-turn admission controller (31), ToolSafe classifies unsafe tool use (17), and AgentSpec specifies tool-agent safety properties (27); these target broader tool-risk settings rather than multi-turn business procedures. AGrail adapts checks online (16), Conseca synthesizes just-in-time policies (26), and Progent enforces least privilege over tool arguments (24), but still act locally around risky actions. PolicyGuard (11) is the closest action-guard baseline: it reads the full conversation, checks a mutating call against a per-tool checklist, and returns pass/block with remediation. This makes it much more dialogue-aware than argument-only guards, but it remains action-scoped: it does not persist position in a policy workflow or proactively guide the agent through the missing steps before a mutating call is attempted. PolicyGuide instead verifies workflow state across turns. 2.3 Workflow- and SOP-guided agents A parallel line encodes procedures as traversable graphs or state machines. SOP-Agent (35) compiles a standard operating procedure into a decision graph that restricts actions at each node. StateFlow (30) represents a task as a finite-state machine whose states hold prompts and tool calls. SMoT maintains explicit task state (14); MetaGPT and ProAgent organize agents around procedural roles or plans (9; 36). JourneyBench studies dynamic prompting in our domain (3); FLAP enforces flows through constrained decoding (22); and FlowBench finds that even strong models struggle to follow supplied workflows reliably (32). These systems primarily study faithful workflow execution rather than safeguarding against policy-violating agent behavior. FlowAgent is the closest qualification (25): its pre- and post-decision controllers guide execution and can reject invalid transitions. Its focus, however, is compliant and flexible workflow execution under out-of-workflow requests; it is not framed or evaluated as a safeguard against policy-violating agent behavior. PolicyGuide instead gives persisted workflow state a safeguarding role: a separate verifier monitors the interaction, returns remediation for unmet steps, and is evaluated with both benign and manipulative users. This separation also permits the same workflow to pair with different agents, a practical benefit rather than the main conceptual distinction. 3 Method PolicyGuide combines an offline policy workflow with an external runtime verifier that guides a general-purpose LLM agent (Figure 3). The workflow represents the procedures required by a domain policy, while code persists the verifier’s workflow state and delivers next-step remediation to the agent. Conceptually, PolicyGuide is a reference-monitor-inspired runtime safeguard (1; 23): it observes the interaction and can intervene before policy-sensitive actions, but the evaluated configuration steers execution rather than claiming classical mandatory enforcement. Its repeated judgment over a growing interaction trace is related to runtime verification (12; 5), while its explicit request state is related to dialogue-state tracking (28; 8). 3.1 Theoretical motivation An action-triggered verifier mediates only the actions that invoke it, such as proposed mutating tool calls. This is sufficient only when every reachable first deviation occurs at such an action. Policy workflows, however, can constrain other agent actions, including evidence gathering, user-facing instructions, branch selection, and completion decisions. These deviations matter even when the eventual mutation is permissible, because a later action check cannot undo an already-committed procedural violation. Appendix A formalizes this distinction through intervention coverage. Theorem 1 shows that an ideal binding verifier preserves procedural validity exactly when its firing schedule covers every reachable first deviation. Corollary 1 shows that an ideal workflow-level schedule satisfies this condition, whereas an action-triggered schedule does so only when every first deviation itself triggers the check. 3.2 Policy workflow representation A workflow is the graph of the policy-compliant interaction. In the three generated domains, the main graph begins with a shared intake, identification, and classification path, then enters a request-specific subflow. Nodes name actors and actions; edges name transitions. Shared procedures such as identification are reused across subflows, while domain-specific subflows express decision gates or diagnostic chains. Node types are entry/exit (structure), agent_action (non-tool agent action), user_input (user response), tool_call (read-only tool), tool_authorization (mutating-tool authorization), decision (branch), and subflow (subflow invocation). Each node specification names its actor and expected action and states an explicit satisfying condition that the runtime verifier judges against the interaction (§3.4); subflows are inlined at load time, so the runtime traverses one flat graph per domain. A mutating tool call is enabled at its authorization node and verified from the corresponding tool result. 3.3 Offline workflow generation The workflows are generated offline by a multi-stage pipeline and frozen once per domain for all workflow-based conditions (Figure 3, top). Stage 1 extracts tool specifications and mutating tools, excluding user-device actions. Stage 2 derives request types, shared procedures, ordered subflows, and a coverage audit; Stage 3 reviews the plan. Stage 4 generates and schema-validates subflows (one repair retry and branch review), and Stage 5 connects the intake spine, classifier, and subflows. Stage 6 validates schema conformance, tool inventory, mutating-tool authorization coverage, graph composition, edge arity, and reachability; reviews policy-to-graph mappings; and prunes unused subflows. Appendix G reproduces the prompts, Appendix H shows examples, and Appendix E specifies these checks and reports the remaining semantic-audit scope. Airline (50) Retail (114) Telecom (114) System Verifier Overall PV Mut Overall PV Mut Overall PV Mut Pass1 Pass^1 ReAct — 0.640 0.865 0.433 0.800 0.900 0.791 0.384 0.721 0.180 ToolGuard static code 0.575 0.969 0.212 — — — — — — PolicyGuard GPT 5.4 0.710 1.000 0.442 0.645 0.975 0.613 0.406 0.733 0.208 PolicyGuide GPT 5.4 0.775 0.979 0.587 0.809 0.975 0.793 0.866 0.895 0.849 Pass4 Pass^4 ReAct — 0.460 0.750 0.192 0.596 0.700 0.587 0.193 0.442 0.042 ToolGuard static code 0.520 0.875 0.192 — — — — — — PolicyGuard GPT 5.4 0.580 1.000 0.192 0.360 0.900 0.308 0.202 0.488 0.028 PolicyGuide GPT 5.4 0.620 0.917 0.346 0.614 0.900 0.587 0.614 0.721 0.549 Table 1: Main results on the base splits (GPT 5.4 agent, n=4n=4; airline 50, retail/telecom 114 tasks). Cells report Pass1 and Pass4 overall and on the PV/Mut slices. The verifier is absent for ReAct, static code for ToolGuard, and GPT 5.4 for PolicyGuard and PolicyGuide. P1 P^1P2 P^2P3 P^3P4 P^40.20.20.30.30.40.40.50.50.60.60.70.70.80.80.90.9Passk Pass^kAirlineP1 P^1P2 P^2P3 P^3P4 P^4RetailP1 P^1P2 P^2P3 P^3P4 P^4Telecom 4 Figure 4: Passk vs. k (reliability; higher is better) on the base split of each domain, GPT 5.4, all cells n=4n=4. 3.4 Online policy-guided runtime Input : policy π, tools T, workflow G, history H, and state S ℛ^← R← requests in H reconciled with the tracked requests in S foreach open request r∈ℛ^r∈ R do p←p← entry of G if r is new; otherwise its position in S while p is nonterminal do if the requirement at p is not satisfied by H then break p←p← successor along the outgoing edge in G that matches H if p is terminal then dr←∅d_r← else dr←d_r← action required at p d←d← merge dr:r∈ℛ^\d_r:r∈ R\ return (d,ℛ^)(d, R) Algorithm 1 PolicyGuide verifier Algorithm 1 summarizes the runtime (Figure 3, bottom). Each firing is a single verifier generation Vϕ(π,,G,H,S)=(d,ℛ^),V_φ(π,T,G,H,S)=(d, R), where VϕV_φ is the verifier LLM; π, T, G, H, and S are the raw policy, tool specifications, frozen workflow graph, interaction history, and code-owned request state; and d and ℛ R are the merged remediation and the updated request records the runtime persists. Firing and interface. The verifier fires before the agent responds to each user turn, and once more after a mutating tool call not authorized by the current workflow state is intercepted; skipped tool-result turns are folded into the next firing’s conversation delta, so each call judges the complete trajectory. Its prompt is a cached static prefix (π, T, the rendered graph, judging rules, and output contract) plus the conversation and the latest state record; it returns a free-text audit and one structured record per open request—node walk with cited evidence, position, status, mutating-tool authorization, selection memory, and remediation—plus a global transfer flag (Appendices D.3 and G). It runs at temperature 0, model-paired with the agent. Reconcile and traverse. The verifier reconciles the open requests against S (continuing requests keep their recorded positions; new ones open at the graph entry; abandoned or duplicate ones are dropped or merged), then walks each from its recorded node, judging every node’s satisfying condition against H: facts and eligibility count only when confirmed by tool results, while the user’s own choices and consent count from their messages. The walk stops at the first unsatisfied node, whose required action becomes the remediation; one generation can advance several nodes, and terminal nodes mark a request done. State and delivery. Code, rather than the model’s conversational memory, owns state persistence. It rejects unknown node IDs, filters authorization outputs against the enumerated mutating-tool inventory, reconstructs the currently enabled tool set, and persists each request’s position and memory. The merged remediation is injected as a guidance message before the agent acts. Intervention. In the evaluated advisory mode, the first mutating tool call not authorized by the current workflow state within each user-turn region is intercepted before execution and triggers a corrective verifier firing. The one-shot gate then disarms for an immediate retry, preventing the advisory mechanism from deadlocking execution. Other workflow-governed actions are steered through remediation rather than hard-gated. 3.5 Variants and ablations PolicyGuide rests on two separable ingredients: what the policy is compiled into (the graph versus the raw policy text) and who tracks progress (an external verifier versus the acting agent). Each variant strips one. PolicyGuide-Raw keeps the verifier model, firing schedule, carried state, and remediation channel but substitutes the raw policy for G, so no graph position persists—isolating the compiled graph. PolicyGuide-Self places the frozen graph in the actor’s system prompt but removes the external verifier, code-owned state, per-turn remediation, and corrective intercept—isolating external tracking (§4.3). 4 Experiments 4.1 Setup We evaluate on the τ2τ^2-bench Airline (50 tasks; 24 PV / 26 Mut), Retail (114; 10 PV / 104 Mut), and Telecom (114; 43 PV / 71 Mut) base splits. PV tasks require the agent to prevent a policy-violating mutation; Mut tasks require it to complete a permitted mutation under the policy prerequisites. Diagnostic variants and FlowAgent use the benchmark-provided held-out test splits for Retail (40; 4 PV / 36 Mut) and Telecom (40; 21 PV / 19 Mut): the fixed IDs come from split_tasks.json, not author sampling. Telecom test is more PV-heavy than base (52.5% versus 37.7%), so we report both slices. We evaluate model-paired actor–verifier configurations using GPT 5.4, Claude Sonnet 4.6, and Gemini 2.5 Pro, with the verifier drawn from the actor’s model family; the frozen user simulator is GPT 4.1. The domain-wide comparison uses GPT 5.4. To keep policy representation consistent, we use GPT 5.4 to author one workflow per domain and reuse each frozen workflow across systems and agent families. This isolates runtime and executor differences from workflow re-authoring. The main comparison contrasts ReAct (no guard), PolicyGuard, and PolicyGuide on the same task IDs and GPT 5.4 substrate; ToolGuard is included on Airline, where its released code guards apply. All main cells use n=4n=4. We report Pass1 and Pass4; unless explicitly labeled Pass1, PV and Mut denote Pass4 on the corresponding task slice. For a task with c successful trials, Passk=(ck)/(nk)Pass^k= ck/ nk, averaged across tasks. We also include FlowAgent (25) as a matched workflow-controller baseline on Telecom (§4.4). The benchmark’s standard evaluators score final database state and natural-language task assertions rather than complete temporal conformance of intermediate actions. Passk therefore measures reliable policy-constrained task outcomes, not direct trace-level procedural validity. We supplement it with an author-designed Telecom event-order rubric (§4.7) and report the guard-derived Call-NMR audit separately (Appendix F). Domain Metric ReAct PolicyGuide Self PolicyGuide Raw PolicyGuide Airline Overall 0.460 0.480 0.520 0.620 PV 0.750 0.833 0.875 0.917 Mut 0.192 0.154 0.192 0.346 Retail Overall 0.575 0.350 0.575 0.725 PV 0.750 0.750 0.750 1.000 Mut 0.556 0.306 0.556 0.694 Telecom Overall 0.250 0.325 0.350 0.675 PV 0.429 0.571 0.619 0.667 Mut 0.053 0.053 0.053 0.684 Table 2: Workflow ablations (GPT 5.4 agent; Airline base split, Retail and Telecom benchmark test splits of 40 tasks). All cells report Pass4. System Runtime control Pass4 ReAct actor only 0.250 PolicyGuard action-local check 0.325 FlowAgent PDL + API control 0.350 PolicyGuide external graph verifier 0.675 Table 3: Matched workflow-controller comparison on the 40-task Telecom benchmark test split. All values are Pass4. Agent Metric ReAct PolicyGuard PolicyGuide GPT 5.4 Overall 0.460 0.580 0.620 PV 0.750 1.000 0.917 Mut 0.192 0.192 0.346 Claude Sonnet 4.6 Overall 0.720 0.780 0.780 PV 0.958 1.000 1.000 Mut 0.500 0.577 0.577 Gemini 2.5 Pro Overall 0.480 0.600 0.680 PV 0.750 1.000 0.917 Mut 0.231 0.231 0.462 Table 4: Agent-family generalization on Airline (50 tasks, n=4n=4; verifier model paired to the agent). All metrics are Pass4. The GPT 5.4-authored workflow graph is reused without re-authoring. P1 P^1P2 P^2P3 P^3P4 P^40.50.50.60.60.70.70.80.80.90.9Claude Sonnet 4.6P1 P^1P2 P^2P3 P^3P4 P^4Gemini 2.5 Pro 5 Figure 5: Passk for Claude Sonnet 4.6 and Gemini 2.5 Pro agents on airline (verifier == agent), with n=4n=4 for every system. 4.2 Main results PolicyGuide achieves the highest overall Pass4 in all three domains (Table 1; Figure 4); the lead persists as k increases, and pooled paired tests favor it over both baselines (Appendix C). Gains are largest on Telecom’s long diagnose–instruct–verify chains, consistent with persisted graph position mattering most for ordered procedures rather than one final action. The improvement spans both PV and Mut, rather than trading completion for stricter blocking. Retail separates guidance from blocking: PolicyGuide preserves ReAct’s Mut performance while improving PV, whereas PolicyGuard’s PV gain coincides with lower Mut. The overall difference is not significant. 4.3 Diagnostic workflow variants Actor-only workflow access. PolicyGuide-Self gives the frozen graph to the actor but removes the external verifier, persisted state, remediation, and mutation intercept. Its Mut Pass4 does not exceed ReAct in any domain, showing that access to the workflow does not by itself ensure reliable execution. Because several runtime components are removed together, this comparison tests the external stack as a bundle rather than isolating state persistence alone. Compiled structure under external tracking. PolicyGuide-Raw retains the verifier schedule and remediation channel but replaces the graph with raw policy text. Relative to this matched guide, PolicyGuide improves overall Pass4 by 0.1000.100, 0.1500.150, and 0.3250.325 on Airline, Retail, and Telecom. The larger Telecom gap is consistent with explicit graph position helping the verifier resume long, ordered diagnostic chains. These ablations are therefore diagnostic rather than a complete factorial decomposition. 4.4 Matched workflow-controller comparison Table 3 adds the closest workflow-aware runtime comparison. For representation matching, we deterministically compile the same frozen graph into PDL, with no LLM authoring. FlowAgent places the raw policy and PDL inside the actor and applies its released API-dependency and duplicate-call controllers; PolicyGuide instead tracks graph state in an external persisted verifier. ReAct and PolicyGuard provide actor-only and action-local references. 4.5 Generalization across agent families The GPT 5.4-authored Airline graph is reused unchanged with Claude Sonnet 4.6 and Gemini 2.5 Pro (Table 4; Figure 5), separating executor transfer from workflow re-authoring. The gains over unguided execution support executor-side transfer across all three model families. For Gemini 2.5 Pro, PolicyGuide improves Mut Pass4 from 0.2310.231 under either baseline to 0.4620.462, while its lower PV than PolicyGuard (0.9170.917 versus 1.0001.000) indicates a completion benefit rather than stricter final-action checking. Transfer across workflow-author models remains untested. 4.6 Adversarial robustness k=1k=1k=2k=2k=3k=3k=4k=40.050.050.10.10.150.150.20.20.250.25CRAFT ASR@k (↓ safer) 6 Figure 6: CRAFT red-team attack-success rate on airline (20 attack tasks, GPT 5.4, n=4n=4); lower is safer. Under CRAFT (18), persuasive users inject false eligibility premises to induce forbidden mutations. PolicyGuide has the lowest ASR@k at every k (Figure 6); its per-trial ASR is 0.0870.087, versus 0.1250.125 for PolicyGuard and 0.2000.200 for ReAct, preventing 91.3%91.3\% of tested attacks while improving benign completion. These results show that PolicyGuide is robust to CRAFT red-team attacks. Its lower ASR is consistent with requiring tool-derived evidence, so unsupported user claims cannot satisfy workflow prerequisites. 4.7 Procedural trace compliance System Step-TCR Trace-TCR Process-valid rate ReAct 86.4 35.4 17.5 PolicyGuard 85.7 23.9 13.1 PolicyGuide 94.5 63.4 56.2 Table 5: Author-designed Telecom ordered trace compliance (%; n=4n=4). Step- and Trace-TCR condition on outcome-passing traces. Because final-state Pass ignores intermediate order, the authors manually designed a task-conditioned Telecom rubric from the raw policy and support manual. It checks identification, diagnosis before intervention, consent, correction order, and final verification. On outcome-passing traces, Step-TCR is the fraction of applicable checks satisfied and Trace-TCR the fraction satisfying all checks. The process-valid rate is the fraction of all task–run pairs passing both the Tau2 outcome and the rubric, pooled across four runs; it is our sole end-to-end measure, not a Passk statistic. This best-effort workflow-level extension of prerequisite analysis is distinct from Call-NMR (21; 11), whose Telecom adaptation appears in Appendix F. PolicyGuide attains the highest process-valid rate (56.2%, versus 17.5% for ReAct and 13.1% for PolicyGuard; Table 5) and leads both conditional diagnostics. We report the latter only to characterize successful traces. 5 Conclusion PolicyGuide replaces action-local checks with an external guide that traverses a compiled policy graph, persists progress, and returns targeted remediation. Across three τ2τ^2-bench domains it achieves the best overall Pass4, transfers across agent families, and performs strongest on procedural Telecom. Ablations and an author-designed ordered-trace audit support external graph tracking and treating the procedure—not only the final action—as the unit of policy adherence. Limitations Evaluation scope. We evaluate three English τ2τ^2-bench customer-service domains (4) with a frozen user simulator and four trials per multi-trial cell. These domains vary in procedural structure, but do not represent other policy regimes, languages, or live users. Retail has only 10 PV tasks and the overall gain over ReAct is not significant. The ToolGuard runtime baseline is Airline-only because its released guards target that domain (37); our generated Telecom guards are used only as a frozen NMR oracle. Paired tests are limited to systems with per-task outputs. Because τ2τ^2-bench does not supply a general ordered-trace oracle, our Telecom trace metric is an exploratory, author-designed operationalization of selected task-relevant requirements observable in serialized traces. It uses deterministic event ordering and text matching, is conditioned by gold task actions, and has no second-annotator agreement estimate; it therefore does not establish exhaustive natural-language policy compliance. Call-NMR partially audits prior reads in Airline and Retail, while its adapted Telecom oracle saturates and is reported only as a non-identification result (Appendix F). Benchmark coverage. Adjacent benchmarks test related but different questions. CRMArena-Pro (10) emphasizes business-task capability and confidentiality awareness; IntellAgent (13) generates diagnostic conversations; Near-Miss (21) audits completed trajectories; and AgentRewardBench (15) evaluates trajectory judges. CRAFT (18) supplies adversarial users for our robustness audit, not the benign workflow-completion distribution. We report only its clean, release-aligned 20-task Airline split. Although the CRAFT paper also evaluates Retail, the released Retail task lists, cached strategies, and evaluator in our checkout do not reproduce one consistent paper-faithful 30-task set; no official Telecom set exists. Our result therefore shows that PolicyGuide prevents most tested persuasive Airline attacks, which is sufficient to check that its completion gains do not sacrifice resistance, but does not establish cross-domain or adaptive-attack robustness. None is therefore a drop-in test of online workflow guidance, and transfer would require new workflows and task-specific outcome measures. Workflow generation and faithfulness. Using one frozen GPT 5.4-authored workflow per domain is a deliberate control: every system and agent family receives the same policy representation, so the comparison isolates runtime and executor differences rather than re-authoring. This achieves the study’s fair-comparison objective, but does not establish author-side generalization across models or seeds. We address workflow faithfulness separately by manually verifying each frozen graph against its source policy and tool specifications (Appendix E). Trigger and cost. The reported runtime fires at user-turn boundaries and after its one-shot corrective intercept, rather than before every policy-relevant agent action. Corollary 2 characterizes the corresponding coverage condition and shows why deviations between these intervention points remain outside the unconditional guarantee. Broader intervention coverage would require more verifier calls. Guide calls cost approximately $0.40\$0.40 per conversation; smaller models and sparser invocation can reduce, but not eliminate, this overhead. Probabilistic enforcement. Like other LLM-based agent safeguards (6; 31; 11), each node judgment is probabilistic, so compliance is empirical rather than guaranteed. Theorem 1 assumes a faithful workflow, an ideal binding verifier, and coverage before every reachable first deviation (Appendix A); the advisory runtime does not satisfy these conditions unconditionally. Verifier exceptions are fail-open, so deployments requiring hard guarantees need an additional deterministic monitor for the formally expressible policy subset. Ethics Statement PolicyGuide is a probabilistic aid for policy adherence, not a guarantee, and should not be the sole control for high-stakes actions. Because the verifier reads the conversation, tool results, and persisted workflow state, privacy, access control, retention, and auditing requirements must extend to verifier calls and logs. All experiments use synthetic τ2τ^2-bench tasks and simulated users (4); no real customer data or external actions are involved. Generated workflows may reproduce source-policy errors or introduce unsupported restrictions, so deployment requires review by policy owners, monitoring, and a safe fallback. We will release the prompts, workflow schemas, and analysis artifacts needed for reproducibility. References Anderson (1972) J. P. Anderson Computer security technology planning study. Technical Report Technical Report ESD-TR-73-51, Vol. I, Electronic Systems Division, Air Force Systems Command, Hanscom AFB, Bedford, MA. Note: DTIC accession no. AD-758206 Cited by: §3. Anthropic (2026) Anthropic Claude sonnet 4.6 system card. Note: Anthropic, https://anthropic.com/claude-sonnet-4-6-system-card. Cited by: §1. Balaji et al. (2026) S. Balaji, P. Mishra, A. Sachdeva, and S. Agrawal Beyond ivr: benchmarking customer support llm agents for business-adherence. arXiv preprint arXiv:2601.00596. External Links: 2601.00596 Cited by: §2.3. Barres et al. (2025) V. Barres, H. Dong, S. Ray, X. Si, and K. Narasimhan τ2τ^2-Bench: evaluating conversational agents in a dual-control environment. arXiv preprint arXiv:2506.07982. Cited by: §1, §2.1, Evaluation scope., Ethics Statement. Bauer et al. (2011) A. Bauer, M. Leucker, and C. Schallhart Runtime verification for LTL and TLTL. ACM Transactions on Software Engineering and Methodology 20 (4), p. 14:1–14:64. External Links: Document Cited by: §3. Chen et al. (2025) Z. Chen, M. Kang, and B. Li ShieldAgent: shielding agents via verifiable safety policy reasoning. In Proceedings of the 42nd International Conference on Machine Learning (ICML), External Links: 2503.22738 Cited by: §1, §2.2, Probabilistic enforcement.. Comanici et al. (2025) G. Comanici, E. Bieber, M. Schaekermann, I. Pasupat, N. Sachdeva, et al. Gemini 2.5: pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities. arXiv preprint arXiv:2507.06261. Cited by: §1. Henderson et al. (2014) M. Henderson, B. Thomson, and S. Young Word-based dialog state tracking with recurrent neural networks. In Proceedings of the 15th Annual Meeting of the Special Interest Group on Discourse and Dialogue (SIGDIAL), p. 292–299. External Links: Link Cited by: §3. Hong et al. (2024) S. Hong, M. Zhuge, J. Chen, X. Zheng, Y. Cheng, C. Zhang, J. Wang, Z. Wang, S. K. S. Yau, Z. Lin, L. Zhou, C. Ran, L. Xiao, C. Wu, and J. Schmidhuber MetaGPT: meta programming for a multi-agent collaborative framework. In The Twelfth International Conference on Learning Representations (ICLR), External Links: 2308.00352 Cited by: §2.3. Huang et al. (2025) K. Huang, A. Prabhakar, O. Thorat, D. Agarwal, P. K. Choubey, Y. Mao, S. Savarese, C. Xiong, and C. Wu CRMArena-pro: holistic assessment of llm agents across diverse business scenarios and interactions. arXiv preprint arXiv:2505.18878. Note: Also published in Transactions on Machine Learning Research (TMLR), 2026 External Links: 2505.18878 Cited by: §2.1, Benchmark coverage.. Kang et al. (2026) S. Kang, T. Yu, and S. J. Hwang PolicyGuard: a dialogue-grounded sub-agent verifier for policy adherence in llm agents. arXiv preprint arXiv:2606.29225. Cited by: §B.1, §B.2, Appendix F, §1, §2.2, §4.7, Probabilistic enforcement.. Leucker and Schallhart (2009) M. Leucker and C. Schallhart A brief account of runtime verification. Journal of Logic and Algebraic Programming 78 (5), p. 293–303. External Links: Document Cited by: §3. Levi and Kadar (2025) E. Levi and I. Kadar IntellAgent: a multi-agent framework for evaluating conversational ai systems. arXiv preprint arXiv:2501.11067. External Links: 2501.11067 Cited by: §2.1, Benchmark coverage.. Liu et al. (2023) J. Liu, J. Shuai, and X. Li State machine of thoughts: leveraging past reasoning trajectories for enhancing problem solving. arXiv preprint arXiv:2312.17445. External Links: 2312.17445 Cited by: §2.3. Lù et al. (2025) X. H. Lù, A. Kazemnejad, N. Meade, A. Patel, D. Shin, A. Zambrano, K. Stańczak, P. Shaw, C. J. Pal, and S. Reddy AgentRewardBench: evaluating automatic evaluations of web agent trajectories. arXiv preprint arXiv:2504.08942. External Links: 2504.08942 Cited by: §2.1, Benchmark coverage.. Luo et al. (2025) W. Luo, S. Dai, X. Liu, S. Banerjee, H. Sun, M. Chen, and C. Xiao AGrail: a lifelong agent guardrail with effective and adaptive safety detection. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Vienna, Austria, p. 8104–8139. External Links: 2502.11448 Cited by: §2.2. Mou et al. (2026) Y. Mou, Z. Xue, L. Li, P. Liu, S. Zhang, W. Ye, and J. Shao ToolSafe: enhancing tool invocation safety of llm-based agents via proactive step-level guardrail and feedback. Note: arXiv preprint arXiv:2601.10156 External Links: 2601.10156 Cited by: §2.2. Nakash et al. (2025) I. Nakash, G. Kour, K. Lazar, M. Vetzler, G. Uziel, and A. Anaby-Tavor Effective red-teaming of policy-adherent agents. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, Suzhou, China, p. 2250–2268. Cited by: §2.1, §4.6, Benchmark coverage.. OpenAI (2026) OpenAI Introducing GPT-5.4. Note: OpenAI Blog, https://openai.com/index/introducing-gpt-5-4/. Released March 5, 2026. Cited by: §1. Palumbo et al. (2026) N. Palumbo, S. Choudhary, J. Choi, P. Chalasani, and S. Jha Policy compiler for secure agentic systems. Note: arXiv preprint arXiv:2602.16708 External Links: 2602.16708 Cited by: §2.2. Rabinovich et al. (2026) E. Rabinovich, D. Boaz, N. Zwerdling, and A. Anaby-Tavor Near-miss: latent policy failure detection in agentic workflows. arXiv preprint arXiv:2603.29665. External Links: 2603.29665 Cited by: Appendix F, §2.1, §4.7, Benchmark coverage.. Roy et al. (2024) S. Roy, S. Sengupta, D. Bonadiman, S. Mansour, and A. Gupta FLAP: flow-adhering planning with constrained decoding in LLMs. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), Mexico City, Mexico, p. 517–539. External Links: Link, 2403.05766 Cited by: §2.3. Schneider (2000) F. B. Schneider Enforceable security policies. ACM Transactions on Information and System Security 3 (1), p. 30–50. External Links: Document Cited by: §3. Shi et al. (2025a) T. Shi, J. He, Z. Wang, H. Li, L. Wu, W. Guo, and D. Song Progent: securing ai agents with privilege control. arXiv preprint arXiv:2504.11703. External Links: 2504.11703 Cited by: §2.2. Shi et al. (2025b) Y. Shi, S. Cai, Z. Xu, Y. Qin, G. Li, H. Shao, J. Chen, D. Yang, K. Li, and X. Sun FlowAgent: achieving compliance and flexibility for workflow agents. arXiv preprint arXiv:2502.14345. External Links: 2502.14345 Cited by: §1, §2.3, §4.1. Tsai and Bagdasarian (2025) L. Tsai and E. Bagdasarian Contextual agent security: a policy for every purpose. In Proceedings of the 20th Workshop on Hot Topics in Operating Systems (HotOS 2025), External Links: 2501.17070 Cited by: §2.2. Wang et al. (2026) H. Wang, C. M. Poskitt, and J. Sun AgentSpec: customizable runtime enforcement for safe and reliable llm agents. In Proceedings of the 2026 IEEE/ACM 48th International Conference on Software Engineering (ICSE ’26), External Links: 2503.18666 Cited by: §2.2. Williams et al. (2013) J. D. Williams, A. Raux, D. Ramachandran, and A. W. Black The dialog state tracking challenge. In Proceedings of the SIGDIAL 2013 Conference, p. 404–413. External Links: Link Cited by: §3. Winston et al. (2026) C. Winston, C. Winston, and R. Just Solver-aided verification of policy compliance in tool-augmented llm agents. arXiv preprint arXiv:2603.20449. External Links: 2603.20449 Cited by: §2.2. Wu et al. (2024) Y. Wu, T. Yue, S. Zhang, C. Wang, and Q. Wu StateFlow: enhancing llm task-solving through state-driven workflows. In Conference on Language Modeling (COLM), External Links: 2403.11322 Cited by: §1, §2.3. Xiang et al. (2025) Z. Xiang, L. Zheng, Y. Li, J. Hong, Q. Li, H. Xie, J. Zhang, Z. Xiong, C. Xie, C. Yang, D. Song, and B. Li GuardAgent: safeguard llm agents via knowledge-enabled reasoning. arXiv preprint arXiv:2406.09187. External Links: 2406.09187 Cited by: §1, §2.2, Probabilistic enforcement.. Xiao et al. (2024) R. Xiao, W. Ma, K. Wang, Y. Wu, J. Zhao, H. Wang, F. Huang, and Y. Li FlowBench: revisiting and benchmarking workflow-guided planning for llm-based agents. In Findings of the Association for Computational Linguistics: EMNLP 2024, p. 10883–10900. External Links: 2406.14884 Cited by: §2.3. Yao et al. (2024) S. Yao, N. Shinn, P. Razavi, and K. Narasimhan τ-Bench: a benchmark for tool-agent-user interaction in real-world domains. arXiv preprint arXiv:2406.12045. Cited by: §1, §2.1. Yao et al. (2023) S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao ReAct: synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR), Cited by: §1. Ye et al. (2025) A. Ye, Q. Ma, J. Chen, M. Li, T. Li, F. Liu, S. Mai, M. Lu, H. Bao, and Y. You SOP-agent: empower general purpose ai agent with domain-specific sops. arXiv preprint arXiv:2501.09316. External Links: 2501.09316 Cited by: §1, §2.3. Ye et al. (2023) Y. Ye, X. Cong, S. Tian, J. Cao, H. Wang, Y. Qin, Y. Lu, H. Yu, H. Wang, Y. Lin, Z. Liu, and M. Sun ProAgent: from robotic process automation to agentic process automation. arXiv preprint arXiv:2311.10751. External Links: 2311.10751 Cited by: §2.3. Zwerdling et al. (2025) N. Zwerdling, D. Boaz, E. Rabinovich, G. Uziel, D. Amid, and A. Anaby-Tavor Towards enforcing company policy adherence in agentic workflows. arXiv preprint arXiv:2507.16459. External Links: 2507.16459 Cited by: §1, Evaluation scope.. Appendix A Theoretical Analysis Policy workflows constrain a broader set of agent actions than the class mediated by an action-triggered verifier. We formalize when a firing schedule can preserve procedural validity over this broader workflow. A.1 Intervention coverage We represent each interaction as a sequence of policy-relevant events. A workflow G defines a nonempty language ℒ⁡(G)L(G) of compliant complete sequences. We call a partial sequence valid when it can still be completed to such a sequence, and write PG=Pref(ℒ(G))=τ∣∃ρ:τρ∈ℒ(G).P_G=Pref(L(G))=\τ ∃ρ:τρ (G)\. (1) Let Σag _ag denote policy-relevant agent actions, including user-facing messages, instructions, and tool calls, and let A⊆ΣagA _ag be the designated action class mediated by an action-triggered verifier. For mutating-call guards, A is the set of agent-issued mutating tool calls. A reachable first deviation is a pair (τ,e)(τ,e) where τ∈PGτ∈ P_G can arise during an interaction, e∈Σage∈ _ag can be the next agent event, and τe∉PGτ e∉ P_G. Let DGD_G be the set of such deviations. A firing schedule S covers (τ,e)∈DG(τ,e)∈ D_G if it invokes the verifier after observing τ and before e is committed; let CS(G)⊆DGC_S(G) D_G denote its intervention coverage. We compare: • the action-triggered schedule SAS_A, which fires exactly when the proposed event belongs to A; and • the ideal workflow-level schedule SwfS_wf, which fires before every policy-relevant agent action is committed. The theorem compares these schedules under the same ideal verifier: when consulted, it permits an event if and only if the resulting trace remains in PGP_G, and a rejected event cannot commit. User responses and tool results may update the trace, but do not themselves violate an agent obligation. An uncovered agent event may commit without a verifier verdict. Theorem 1 (Complete intervention coverage). Under the assumptions above, a firing schedule S preserves procedural validity (PGP_G membership) throughout every execution if and only if CS(G)=DG.C_S(G)=D_G. (2) That is, the verifier must cover every reachable first deviation. Proof. For sufficiency, start from the empty valid prefix. If the next observation is not an agent event, it preserves PGP_G by assumption. If the agent proposes an event that stays in PGP_G, committing it preserves validity. Otherwise the proposal is in DGD_G and belongs to CS(G)C_S(G) by Equation 2; the ideal verifier rejects it before it commits. Induction over the interaction therefore keeps every prefix in PGP_G. For necessity, suppose (τ,e)∈DG(τ,e)∈ D_G is not in CS(G)C_S(G). The valid prefix τ can arise during an interaction, and the ideal verifier permits all covered events that lead to it. At (τ,e)(τ,e) the schedule does not fire, so e can commit and produce τe∉PGτ e∉ P_G. Thus S cannot guarantee procedural validity throughout every execution. ∎ Corollary 1 (Workflow-level versus action-triggered coverage). The workflow-level schedule covers every member of DGD_G. The action-triggered schedule covers exactly those members whose action e belongs to A. Therefore workflow-level firing preserves procedural validity for every workflow, whereas action-triggered firing does so if and only if every reachable first deviation belongs to A. If DGD_G contains a point with e∉Ae∉ A, workflow-level firing provides a guarantee that action-triggered firing cannot provide, even when both use the same ideal verifier. Proof. The workflow-level schedule fires before every agent-controlled action, so it covers all of DGD_G. The action-triggered schedule fires exactly for actions in A. The claims then follow directly from Theorem 1. ∎ Corollary 2 (Evaluated boundary schedule). Let SevalS_eval fire after every user turn and after the runtime intercepts an unauthorized mutating call. Let BG⊆DGB_G D_G contain the reachable first deviations (τ,e)(τ,e) for which one of these firings occurs after the valid prefix τ and before the next agent event e is committed. Under the same ideal, binding-verifier assumptions as Theorem 1, SevalS_eval preserves procedural validity if and only if BG=DGB_G=D_G. In particular, if a first deviation can occur after an intervening agent event and before the next scheduled firing, the evaluated schedule does not provide an unconditional guarantee. Proof. By construction, CSeval(G)=BGC_S_eval(G)=B_G. The claim follows directly from Theorem 1. ∎ Corollary 2 characterizes the coverage condition for the evaluated cadence; it does not assert that the deployed guide satisfies the theorem’s binding-verifier assumption. Its non-mutating remediation is advisory, and the corrective mutation gate is one-shot, so the experiments measure risk reduction under this practical schedule rather than a formal guarantee. The timing in Theorem 1 is essential. Because PGP_G is prefix-closed, once τe∉PGτ e∉ P_G, no later extension can make τeτ e a valid prefix: if some τeρτ eρ belonged to PGP_G, then its prefix τeτ e would also belong to PGP_G. A later action-triggered verifier may block a subsequent guarded action after reading the history, but it cannot prevent or undo the earlier procedural violation. Appendix B Policy structure analysis This appendix supports the paper’s central claim: workflow enforcement matters most when the policy is itself a workflow, as in telecom. We extend PolicyGuard’s argument-/process-level classification with a third, workflow-level class, apply it to every atomic requirement of all three source policies, and examine how both process- and workflow-level requirements relate to the observed gains. Process-level requirements motivate context-aware guidance generally, whereas workflow-level requirements create a particular need for ordered graph traversal and persistent progress tracking. Line references refer to the policy documents released with τ2τ^2-bench: the 136-line retail policy and, for telecom, the 158-line account policy and the 205-line technical-support manual. B.1 Operational definitions Following PolicyGuard (11), we classify the source policy document, not any generated artefact of the systems under test. A requirement is argument-level (A) if verifiable from the mutating call’s arguments plus deterministic computation—the class precompiled guards express natively—and process-level (P) if verification must read the user–agent dialogue (D) and/or a prior read-only tool result (T). We split PolicyGuard’s process-level class by adding workflow-level (W): a requirement that additionally mandates an action ordered after the outcome of another required action (a state effect, a user response to a prior step, or a post-act verification), so discharging it out of order is itself a violation. The three classes are mutually exclusive: W rows read dialogue and tool results like P rows, but P is reserved for the flat remainder, dischargeable at the action point from evidence gathered in any order (status checks, elicit–confirm–act chains). A and P+W therefore remain comparable with PolicyGuard. Requirements are extracted by hand and grouped by each document’s own section headers; descriptive sentences and API meta-rules are excluded. Table 6 gives the partition; the catalogs follow. Domain A P W Total % P+W % W Airline 14 27 2 43 67.4% 4.7% Retail 0 27 1 28 ∼100% 100\% 3.6% Telecom (main) 1 21 7 29 96.6% 24.1% Telecom (manual) 0 1 20 21 100% 95.2% Telecom (both) 1 22 27 50 98.0% 54.0% Table 6: Argument- (A), process- (P), and workflow-level (W) partition of the source policies (W splits PolicyGuard’s process-level class; P+W equals it). ID Line Requirement (paraphrased) Type Global rules G1 10 Authenticate identity by locating the user id via email or name+zip—even when the user already provides the id P (D+T) G2 14 One user per conversation; deny any request about another user P (D) G3 16 List action details + obtain explicit “yes” before any DB-updating action P (D) G4 18 No fabricated information/knowledge/procedures; no subjective recommendations P (D) G5 20 At most one tool call per turn (not paired with a user-facing reply) P (D) G6 22 Deny user requests that are against the policy P (D) G7 24 Transfer iff unhandleable: call transfer_to_human_agents, then the literal handoff message W (D) Generic action rules N1 82 Act only on orders with status pending or delivered P (T) N2 84 Exchange / modify-items tools callable only once per order P (T) N3 84 Collect all items to change into one list before making the call P (D) Cancel pending order C1 88 Order status must be pending; check it before taking the action P (T) C2 90 User confirms order id + reason ∈ ‘no longer needed’, ‘ordered by mistake’; no other reason P (D) Modify pending order M1 96 Order status must be pending; check it before taking the action P (T) M2 98 Only shipping address, payment method, or item options may be modified—nothing else P (D) M3 102 New payment = a single method, different from the original P (T) M4 104 If the new payment is a gift card, its balance must cover the total amount P (T) M5 110 Modify-items is one-shot (order becomes unmodifiable): remind + confirm all items first P (D) M6 112 Each new item must be available P (T) M7 112 New item = same product, different option (no product-type change) P (T) M8 114 User provides a payment method for the price difference P (D) M9 114 If that payment is a gift card, its balance must cover the price difference P (T) Return delivered order R1 118 Order status must be delivered; check it before taking the action P (T) R2 120 User confirms order id + the list of items to be returned P (D) R3 122–124 Refund method provided; must be the original payment method or an existing gift card P (T) Exchange delivered order E1 130 Order status must be delivered; check it before taking the action P (T) E2 130 Remind + confirm the user has provided all items to exchange (one-shot) P (D) E3 132 Each new item = same product, different option, and available P (T) E4 134 Payment for the price difference; if a gift card, balance must cover the difference P (T) Table 7: Hand-classified atomic requirements of the τ2τ^2-bench Retail policy document (28 requirements, 00 A / 2727 P / 11 W; subtypes D-only 1313, T-only 1414, D+T 11). Line refers to retail/policy.md as released with τ2τ^2-bench; Type A = argument-level, P = process-level (flat), W = workflow-level (order-bound; Appendix B.1), with D = dialogue-dependent, T = requires a prior read-only tool call. ID Line Requirement (paraphrased) Type Global rules G1 7 No fabricated information/knowledge/procedures; no subjective recommendations P (D) G2 9 At most one tool call per turn (not paired with a user-facing reply) P (D) G3 11 Deny user requests that are against the policy P (D) G4 13 Transfer iff unhandleable: call transfer_to_human_agents, then the literal handoff message W (D) G5 15 Try your best to resolve the issue before transferring W (D) Customer lookup L1 94–97 Identify the customer via phone number, customer ID, or full name + date of birth P (D+T) L2 99 For name lookup, date of birth is required for verification P (D) Overdue bill payment (ordered procedure) O1 105, 117 -0.4pt 1⃝Check the bill status is Overdue before acting (the API does not check it) P (T) O2 106 -0.4pt 2⃝Check the bill amount due P (T) O3 107–108 -0.4pt 3⃝Send the payment request (→ AWAITING PAYMENT); gated on O1 P (T) O4 109–110 -0.4pt 4⃝Inform the user to check their payment requests W (D) O5 111 -0.4pt 5⃝Only after the user accepts, call make_payment W (D+T) O6 113 -0.4pt 6⃝Always verify the bill became PAID before telling the user W (T) O7 116 At most one bill in AWAITING PAYMENT at a time P (T) Line suspension S1 125 Lift a suspension only after all overdue bills are paid W (T) S2 126 Do not lift if the contract end date is past—even if all bills are paid P (T) S3 128 After resuming, instruct the user to reboot the device W (D) Data refueling (ordered procedure) F1 134 Refuel amount ≤2≤ 2 GB A F2 136 -0.4pt 1⃝Ask how much data the user wants to refuel P (D) F3 137 -0.4pt 2⃝Confirm the price P (D) F4 138 -0.4pt 3⃝Apply the refuel to the line associated with the user’s phone number P (D+T) Change plan (ordered procedure) P1 144 -0.4pt 1⃝Establish which line the plan change is for P (D) P2 145 -0.4pt 2⃝Gather the available plans P (T) P3 146 -0.4pt 3⃝Ask the user to select one P (D) P4 147 -0.4pt 4⃝Calculate the price of the new plan P (T) P5 148 -0.4pt 5⃝Confirm the price P (D) P6 149 -0.4pt 6⃝Apply the plan to the line associated with the user’s phone number P (D+T) Data roaming RM1 155 If the user is travelling abroad, check whether the line is roaming-enabled P (T) RM2 155 If not enabled, enable it at no cost P (T) Table 8: Hand-classified atomic requirements of the τ2τ^2-bench Telecom main_policy.md (29 requirements, 11 A / 2121 P / 77 W). Line refers to the document as released with τ2τ^2-bench; -0.4pt $n$⃝ marks a step in an ordered procedure (“To do so you need to follow these steps”). Types as in Table 7. ID Line Requirement (diagnose → conditional fix → verify) Type Cellular service (l. 55–99) TSS1 69–72 Diagnose service via check_status_bar P (T) TSS2 74–78 If Airplane Mode ON → guide toggle_airplane_mode OFF W (D+T) TSS3 79–87 Check SIM: Missing → reseat; Locked → escalate; Active → ok (three-way branch) W (D+T) TSS4 88–92 If APN incorrect → guide reset_apn_settings, then reboot_device W (D+T) TSS5 93–99 If line suspended → handle per main policy, then verify service restored W (T) Mobile data (l. 100–163) TSD0 106–108 Prerequisite: the user must first have cellular service W (T) TSD1 122–127 Diagnose via run_speed_test W (T) TSD2 129–131 Airplane Mode (as in the Service chapter) W (D+T) TSD3 132–135 If mobile data disabled → guide toggle_data ON W (D+T) TSD4 136–141 If roaming abroad & data off → guide toggle_roaming + verify the line is roaming-enabled W (D+T) TSD5 142–145 If Data Saver ON → guide toggle_data_saver_mode OFF W (D+T) TSD6 146–150 If VPN ON & performance poor → guide disconnect_vpn W (D+T) TSD7 151–158 If usage exceeds the plan limit → offer change-plan or refuel W (T) TSD8 159–163 If network mode 2G/3G → guide set_network_mode_preference W (D+T) MMS (l. 164–205) TSM0 170–173 Prerequisite: the user must have cellular service and mobile data W (T) TSM1 181–183 Diagnose via can_send_mms W (T) TSM2 185–188 Ensure basic service + data connectivity first W (T) TSM3 189–193 If on 2G → guide set_network_mode_preference to 3G+ W (D+T) TSM4 194–199 If MMSC URL unset → guide reset_apn_settings, then reboot_device W (D+T) TSM5 200–203 If Wi-Fi Calling ON → guide toggle_wifi_calling OFF W (D+T) TSM6 204–205 If the messaging app lacks storage/SMS permissions → guide grant_app_permission W (D+T) Table 9: Hand-classified atomic requirements of the τ2τ^2-bench Telecom tech_support_manual.md (21 requirements, 11 P / 2020 W). Line refers to the document as released with τ2τ^2-bench. Every rule is a diagnostic-gated (T) user-guidance (D) step; the three chapters form the prerequisite chain Service ⊂ Data ⊂ MMS; every row except TSS1 (the entry diagnostic) is workflow-level. B.2 Airline catalog (summary) The airline classification is inherited from PolicyGuard (11) (full catalog there); we add the workflow-level split. The 167-line policy yields 43 requirements, 1414 A / 2727 P / 22 W. Argument-level mass sits in booking and modification schema rules (cabin uniformity, passenger limits, payment-method counts); process-level mass splits between dialogue obligations (explicit confirmation, the insurance offer) and tool-read eligibility gates (baggage allowances, flown-segment checks, the disjunctive cancellation and compensation conditions). The two W rows are the transfer pair and the delayed-flight certificate mandated after a change or cancellation—otherwise airline is flat gates discharged at the mutation. B.3 Retail catalog The 28 retail requirements (Table 7) partition as 00 A / 2727 P / 11 W (13 D, 14 T, 1 D+T). Every candidate A-row ranges over environment state rather than argument values: the status gates read the order-status enum only get_order_details surfaces, the balance and variant constraints compare against profile and catalog reads, and identity must be re-derived even when the user supplies an id. The contrast with airline is mechanical: airline’s book_reservation passes the whole reservation as call arguments, so schema constraints are argument-checkable, whereas retail and telecom mutations are thin id-referencing calls whose constrained values are surfaced only by read calls. Structurally, however, retail is the flattest domain: each mutation is guarded by an order-free conjunction—status ∧ content ∧ payment ∧ confirmation—with prerequisite depth 1, no branching, and no verify-after-act; its only W row is the transfer pair. This is exactly the regime a conversation-aware pass/block verifier already covers, and why retail is where PolicyGuide’s graph adds the least. B.4 Telecom catalog The 29 account-policy requirements (Table 8) partition as 11 A / 2121 P / 77 W; the lone A row is the refuel-amount bound. The W rows concentrate in the overdue-payment sequence: send the payment request only for a confirmed-Overdue bill, call make_payment only after the user accepts the request it created, and always verify the bill became PAID—prerequisite chaining that ends in a verify-after-act obligation a pre-execution verifier structurally cannot enforce. Suspension adds cross-procedure dependence (lift only after the overdue bills are paid, unless the contract has ended) and a post-act duty only the user can perform (reboot the device). The 205-line technical-support manual is a troubleshooting manual rather than a rulebook: 21 requirements (Table 9), 11 P / 2020 W. Its defining property is dual control: fixes execute on the user’s device, so the agent must instruct the user, await their report, and re-verify. Every rule instantiates diagnose → conditional fix → re-verify, and the chapters impose the prerequisite chain Service ⊂ Data ⊂ MMS—a literal decision tree with mandated traversal order, on which a task may contain no agent-side mutating call to intercept at all. B.5 Policy structure and observed gains Every domain is majority process-level, consistent with the benefit of context-aware guidance over naive acting. Yet retail—the most process-level domain—gains least, indicating that the P+W fraction alone does not explain the cross-domain variation. Workflow-level requirements are much more concentrated in telecom: 2/432/43 on airline and 1/281/28 on retail versus 27/5027/50 on telecom, including 20/2120/21 in the manual alone (Table 6). The rule is applied uniformly: telecom’s refuel and change-plan recipes are elicit–confirm–apply chains and remain P, the same shallow shape as retail; its W mass lives in the overdue-payment state machine, the suspension procedure, and above all the diagnostic manual. PolicyGuide tracks position in a workflow graph across turns, so it has the most to exploit exactly where W requirements concentrate. Consistent with this account, the compiled-graph gain over the matched raw-policy guide is larger on telecom (+0.325+0.325) than on airline (+0.100+0.100) or retail (+0.150+0.150; §4.3). Thus process-level requirements help explain the general value of context-aware guidance, while the concentration of workflow-level requirements helps explain why PolicyGuide’s explicit graph and state tracking are especially useful in telecom. Appendix C Reliability and significance Passk breakdown. Table 10 gives the exact values underlying Figure 4. Table 11 reports Pass1 separately for each trial. These tables use the same base splits as Table 1: Airline base-50 and Retail/Telecom base-114. Domain System P1P^1 P2P^2 P3P^3 P4P^4 P4/P1P^4/P^1 Airline ReAct 0.640 0.530 0.485 0.460 0.72 ToolGuard 0.575 0.553 0.535 0.520 0.90 PolicyGuard 0.710 0.630 0.595 0.580 0.82 PolicyGuide 0.775 0.707 0.660 0.620 0.80 Retail ReAct 0.800 0.700 0.638 0.596 0.75 PolicyGuard 0.645 0.506 0.421 0.360 0.56 PolicyGuide 0.809 0.715 0.654 0.614 0.76 Telecom ReAct 0.384 0.273 0.226 0.193 0.50 PolicyGuard 0.406 0.292 0.237 0.202 0.50 PolicyGuide 0.866 0.763 0.682 0.614 0.71 Table 10: Passk breakdown for the base-split results in Table 1 and Figure 4 (GPT 5.4, n=4n=4). P4/P1P^4/P^1 is the consistency ratio. Domain System T1 T2 T3 T4 pstd Airline ReAct 0.620 0.620 0.640 0.680 0.024 ToolGuard 0.560 0.580 0.580 0.580 0.009 PolicyGuard 0.700 0.740 0.700 0.700 0.017 PolicyGuide 0.800 0.720 0.820 0.760 0.038 Retail ReAct 0.807 0.746 0.842 0.807 0.035 PolicyGuard 0.649 0.623 0.632 0.675 0.020 PolicyGuide 0.816 0.798 0.789 0.833 0.017 Telecom ReAct 0.342 0.377 0.404 0.412 0.027 PolicyGuard 0.465 0.386 0.360 0.412 0.039 PolicyGuide 0.860 0.860 0.842 0.904 0.023 Table 11: Pass1 in each of the four trials on the base splits. pstd is the population standard deviation across trial-level values. Paired significance. For each task, Pass4 is one iff all four trials succeed. We compare systems on common tasks and obtain 95%95\% confidence intervals by paired bootstrap (10,000 task-level resamples). Across domain strata, we use Z=∑dad−∑dbd∑dad+∑dbd,Z= _da_d- _db_d _da_d+ _db_d, where ada_d counts PolicyGuide-only Pass4 successes and bdb_d the reverse. Table 12 shows that PolicyGuide improves pooled Pass4 over ReAct (p<10−8p<10^-8) and PolicyGuard (p<10−12p<10^-12), pooling all three domains. Domain-level effect sizes and intervals appear in Table 13. Because ΔP4 ^4 is a signed difference rather than a probability, negative limits are valid; an interval crossing zero indicates that the domain-level difference is not statistically distinguishable from zero. Opponent D ∑aΣ a ∑bΣ b ndiscn_ disc Z p ReAct 3 77 19 96 +5.92+5.92 <10−8<10^-8 PolicyGuard 3 97 19 116 +7.24+7.24 <10−12<10^-12 Table 12: Pooled stratified McNemar tests on per-task Pass4. D is the number of domain strata; a counts PolicyGuide-only passes and b the reverse, summed across strata. Domain Opponent n ΔP4 ^4 [95% CI] Airline ReAct 50 +0.160+0.160 [+0.020+0.020, +0.300+0.300] ToolGuard 50 +0.100+0.100 [−0.040-0.040, +0.260+0.260] PolicyGuard 50 +0.040+0.040 [−0.080-0.080, +0.160+0.160] Retail ReAct 114 +0.018+0.018 [−0.070-0.070, +0.105+0.105] PolicyGuard 114 +0.254+0.254 [+0.149+0.149, +0.360+0.360] Telecom ReAct 114 +0.421+0.421 [+0.316+0.316, +0.526+0.526] PolicyGuard 114 +0.412+0.412 [+0.298+0.298, +0.526+0.526] Table 13: Per-domain paired-bootstrap differences in Pass4 on the base splits (10,000 task-level resamples). Positive values favor PolicyGuide. Appendix D Cost analysis PolicyGuide adds verifier inference to the underlying agent. We therefore report guide-side model usage separately from the actor and user simulator, and examine how prompt caching and the firing policy limit this overhead. D.1 Guide-side usage Table 14 summarizes the GPT 5.4 configuration. The guide costs $0.34–$0.56 per task and fires 7.4–11.5 times per task; Telecom is higher because its diagnostic workflows require longer interactions. Although 85.8–88.1% of prompt tokens are cached, each call generates about 2.2–2.5k output tokens for workflow traversal, evidence checks, and remediation. Output generation consequently accounts for an estimated 67.5–71.0% of guide spend. Domain Calls/ task Prompt tok./call Cached input Output tok./call Guide total $ Guide $/task Airline 7.56 32,360 88.1% 2,478 20.10 0.40 Retail 7.42 22,803 85.8% 2,179 13.67 0.34 Telecom 11.47 28,518 86.5% 2,186 22.29 0.56 Table 14: Guide-side model usage for the GPT 5.4 configuration (50 Airline and 40 Retail/Telecom tasks). Costs exclude the actor and user simulator. Thus, caching substantially reduces repeated input processing, but does not eliminate the marginal cost of the verifier: its structured audit is much longer than a binary policy verdict. Reducing guide output length is therefore the main remaining cost-optimization opportunity. D.2 Wall-clock time Table 15 reports mean end-to-end task time. PolicyGuide requires 5.455.45–5.78×5.78× the observed wall-clock time of ReAct, reflecting the additional verifier generations at successive turns. Domain ReAct (s/task) PolicyGuide (s/task) Ratio Airline 36.4 210.1 5.78×5.78× Retail 34.6 193.6 5.60×5.60× Telecom 45.5 247.6 5.45×5.45× Table 15: Mean end-to-end wall-clock time per task. The measurement covers the complete simulated conversation, including actor, verifier, user-simulator, and tool execution, rather than isolated verifier latency. D.3 Cost-aware execution The verifier prompt places the policy, workflow graph, tool specifications, judging rules, and output contract in a byte-stable prefix. Only the evolving conversation and latest request state vary across calls, allowing the repeated enforcement context to benefit from prefix caching. Each firing uses one verifier generation for all open requests and may advance across several satisfied workflow nodes. The verifier fires before responses to user turns, while intervening tool results are incorporated at the next firing; an intercepted unauthorized action triggers an additional check. Consequently, the number of guide calls scales with relevant agent turns rather than with individual workflow nodes or tool observations. Appendix E Workflow verification After generation, the authors manually verified each frozen workflow against the source policy and tool specifications. We reviewed the represented request types, the ordering of policy prerequisites, the authorization and subsequent verification of mutating actions, and the policy or tool-contract basis of graph constraints. This was a verification step: we did not manually edit the generated workflows used in the experiments. Programmatic validation is also integrated into workflow generation. Each generated file is schema-validated, and the assembled graph is checked for subflow composition, valid tool references and decision branches, reachability, and mutating-action authorization coverage. The resulting findings are supplied to the pipeline’s automated review stage. We reran these checks on the exact frozen workflows; Table 16 reports the results. Domain Nodes Auth. nodes Validator flags Airline 158 11 0 Retail 104 7 0 Telecom 127 5 1 Table 16: Programmatic validation rerun on the frozen workflow graphs. The Telecom flag concerns disable_roaming, which is exposed by the environment but has no authorizing workflow path. Manual review confirmed that the source policy specifies enabling roaming but does not authorize the agent to disable it. Its absence therefore does not omit a source-policy procedure; the workflow correctly leaves this action outside its authorized policy scope. Appendix F Call-level near-miss audit Call-NMR (%; ↓ ) Airline Retail Telecom† ReAct 25.4 47.6 0.0 PolicyGuard 32.5 34.8 0.0 PolicyGuide 15.6 34.7 0.0 Table 17: Call-NMR on passing Mut trajectories (n=4n=4): percentage of successfully executed agent mutations missing a frozen guard-derived read prerequisite. †Telecom is an adapted, agent-side diagnostic whose read oracle saturates; its zeros do not establish equal procedural quality. A near miss (21) is a mutation in an outcome-passing task that lacks a policy prerequisite. Following the runtime-view convention used by PolicyGuard, Call-NMR (21; 11) is the fraction of successfully executed mutating calls in passing Mut trajectories that lack at least one earlier read required by a frozen ToolGuard guard. Blocked attempts, tool errors, and calls without a successful response are excluded. The same domain oracle is applied to every system. On Airline, PolicyGuide has the lowest observed rate (15.6%, versus 25.4% for ReAct and 32.5% for PolicyGuard). On Retail, PolicyGuide and PolicyGuard are effectively tied (34.7% and 34.8%); PolicyGuide nevertheless supports more outcome-passing Mut trajectories (116 versus 80). Thus Call-NMR audits prior-read coverage conditional on success, not task coverage or complete procedural validity. Telecom adaptation. The original guard-derived audit is not defined for Telecom. We adapt its call-level convention using a frozen GPT 5.4 guard tree generated from the tagged concatenation of Telecom’s raw agent policy and technical-support manual. Argument- and response-aware matching requires reads to resolve the same customer, line, or bill as the mutation. Because Telecom is dual-control, the denominator covers only agent-side carrier mutations; user/device actions such as toggling data, resetting APN settings, and rebooting are outside the agent-call oracle. The adapted read oracle yields 0.0% for all three primary systems (Table 17). This is a ceiling effect, not evidence that they are procedurally equivalent: the oracle cannot express conversational evidence such as travel status, selected refuel amount, and price confirmation, nor ordering among user/device actions. This non-identification motivates our workflow-level expansion of prerequisite analysis in Section 4.7. Appendix G Prompts This appendix reproduces the load-bearing prompts of both halves of the system as prompt-card figures: the runtime guide prompt (Figures 7–9, teal cards) and the workflow-generation pipeline prompts (Figures 10–11, slate cards). Unicode punctuation is transliterated to ASCII, and the verifier’s next-step instruction is named remediation consistently; otherwise the text is verbatim. In these prompt excerpts, “turn” names a verifier invocation and the hard-gate language states the template’s authorization contract. The reported advisory configuration invokes the verifier at user-turn boundaries, intercepts the first unauthorized mutating call after a user message, and then permits an immediate retry after corrective guidance (§3.4). The guide’s system message is assembled once per domain by substituting three placeholders—policy_doc (the raw policy), graph_doc (the composed graph rendered as a topology section plus per-node specs), and tools_doc (the mutating/read-only tool partition plus the domain’s closed value vocabularies)—into a fixed template, with the per-turn task instruction appended at the end so the whole thing is one cached static prefix (Appendix D.3). Figure 7 shows the protocol, per-turn trigger, and output contract; Figures 8 and 9 the judging rules referenced by the main text’s verifier description (§3.4). The generation pipeline’s shared system prompt carries the schema contract (the eight node types with required fields, edge semantics, id rules) plus the authoring essentials of Figure 10; the plan and adversarial-review stage prompts are in Figure 11. The remaining stages (plan review, per-subflow generation, subflow path review, main wiring) restate subsets of the same contract scoped to their output file. Appendix H Example workflow graphs This appendix visualizes one generated-schema workflow per domain, composed flat as the guide’s cached prefix renders it. Subflow composition prefixes node ids (identify_user.load_profile, book_flow.authorize_book), so the guide addresses every node of every inlined subflow by a stable path-like id. The three figures illustrate the intended schema: every depicted solid edge carries the same label (when: satisfied), depicted mutating tools use a tool_authorization node (trapezoid) with stated prerequisites upstream, and an authorize→ pair represents the post-call success check. These visualizations do not establish complete mutating-tool coverage for every frozen artifact; Appendix E reports the manual verification and programmatic checks. Node colors match the main-text node vocabulary: entry/exit, agent_action, user_input, tool_call, tool_authorization, decision, and subflow. Airline (Figure 12). The shared main spine (intake → identify → classify) and the full transactional book_reservation path: trip and passenger collection, a mandatory search whose TOOL_RESULT grounds the flight arguments, the insurance disclosure, and the shared summary-and-confirm exchange, all upstream of the gate. The classifier routes each reconciled request into its request-type subflow; general and transfer are terminal branches, not subflows. Retail (Figure 13). The main spine performs intake and shared identification before the classifier dispatches each request to cancellation, modification, return, exchange, account, or terminal handling. The expanded cancel_pending_order branch is the canonical flat gate conjunction of Appendix B.3: locate the order, verify its status is exactly pending, obtain the closed-set cancellation reason, confirm, act, and verify. Telecom (Figure 14). After intake and shared customer identification, the classifier dispatches requests to billing, line, plan, roaming, and troubleshooting subflows. The expanded overdue-bill branch invokes pay_overdue_bill, whose eligibility gates precede confirmation and authorization of send_payment_request. The expanded MMS branch invokes troubleshoot_mms, an ordered traversal of service and data prerequisites followed by the documented MMS causes and a closing resolve-or-transfer decision (Appendix B.4). H.1 Turn-by-turn guide example For the airline task “Book me on HAT136 JFK→ , Nov 15,” the agent jumps straight to book_reservation; the guide walks it back through the policy path, one remediation step per turn. Turn 1 stops at identify_user.ask_user_id and asks for the user id; turn 2 directs get_user_details; subsequent turns walk through trip collection, flight search, rule validation, payment, baggage/insurance computation, and summary-and-confirm. Only after the upstream nodes are satisfied does book_flow.authorize_book_reservation set authorize_tool; the following turn verifies the successful TOOL_RESULT and closes the request. Guide system prompt · protocol ⬇ You are the policy guide for a customer-service agent. You do NOT talk to the user; you read the policy and the conversation and tell the agent what to do next by tracking where each of the user’s requests sits in the workflow graph. ## How this works (read carefully) We work through a single ongoing chat, one message per agent turn. I (the runtime) keep the authoritative state in code; each turn I append the new conversation and the current tracked state, and you return the COMPLETE updated state plus each blocked request’s remediation. You have the entire workflow graph below, so you traverse it yourself in your own reasoning -- there is no per-node back-and-forth. Each turn you do two steps: 1. RECONCILE the open requests (intents): start a NEW request at the graph entry node, keep a CONTINUING request at its recorded node/status/authorization, DROP a request the user abandoned, and MERGE two entries that are the same request into one. 2. TRAVERSE each open intent from its current node: evaluate that node against its expectation and satisfying condition (ground truth = tool results); if satisfied, step to the next node and evaluate again; STOP at the FIRST unsatisfied node -- that becomes the intent’s current node and you write its remediation; at a decision node follow the branch that matches the request; authorize a WRITE tool only when its policy prerequisites are all met; mark an intent that reaches a terminal node done. Do the work as REASONING you write out step by step, and only AFTER the reasoning emit the final state as JSON. Reason first, commit second -- never write the JSON cold. Your final JSON is the memory you are guaranteed to carry forward, so every fact you will need next turn must live in it. Guide system prompt · per-turn trigger (cached) ⬇ Update the state machine for this agent turn. FIRST reason in plain text -- reconcile the open requests, then traverse the graph for each open intent node-by-node, and for every node quote its satisfying criterion, cite the evidence, and decide SATISFIED / NOT SATISFIED (stop at the first unsatisfied node). THEN, after the reasoning, emit the final state as the single fenced json block as the last thing in your message. Guide system prompt · output contract (JSON) ⬇ "reconcile": "reasoning": "<one line: which requests are open now, and what you added / closed / merged this turn>", "intents": ["id": "<short stable id>", "request": "<one-line description with the concrete target>", "intent": "<classifier branch label>"] , "traverse": [ "id": "<intent id>", "plan": "<this intent’s whole arc in one line: the end outcome or WRITE it drives toward, the sub-steps that get there, and which are already done>", "walk": [ "node": "<node id>", "reasoning": "<the SATISFIED/NOT-SATISFIED judgement>", "satisfied": true, "node": "<next node id>", "reasoning": "<...>", "satisfied": false ], "node": "<the node you stopped at>", "status": "open | done", "authorize_tool": "<WRITE tool to open at its authorization node, or null>", "selection": "target": "<the specific record(s) this intent acts on>", "ruled_out": ["<each candidate examined and rejected, with the reason>"], "grounded_values": "<arg>": "value": "<copied verbatim from the result that established it>", "source": "<which tool result + record, or ’user message’>", "remediation": "<the exact next action for the agent if blocked; empty if done>" ], "transfer": false, "summary": "<compact running recap of the working context the structured fields do not already capture>" Figure 7: Guide system prompt, part 1 of 3. Left: the protocol block (reconcile-then-traverse, one generation per fired turn) and the per-turn trigger, which is folded into the cached static prefix rather than re-sent. Right: the Part-2 output contract—the single fenced JSON block the runtime parses into code-owned state. Judging rules · ground truth ⬇ - Ground truth = tool results. A fact, eligibility condition, or completed action counts as established ONLY when a TOOL_RESULT in the conversation confirms it (directly or by your reasoning over tool results) -- NOT because the user asserted it, told you to assume it, or stated it as a given, and NOT because the agent merely said it; a value the agent computes from already-established inputs is itself established -- but a decision or argument that turns on a numeric or temporal computation must be worked out step by step in your reasoning and taken from those steps, never asserted as a conclusion; the user’s own choices, consent, and preferences are established by the user’s message, but a factual or eligibility condition the policy gates on is never established by the user’s word -- when the user supplies or assumes one, delegate the read-only tool that verifies it and judge the condition from that result before relying on it, and a tool result that contradicts the user’s claim governs. Judging rules · authorization ⬇ - Authorization. A WRITE (mutating) tool may be authorized ONLY when every policy prerequisite for that specific tool is met from tool-confirmed facts (plus the user’s own consent where the policy asks for it) -- apply exactly the prerequisites the policy states for that tool, adding none it does not state, so once all of them are met you authorize rather than withholding for a condition you inferred. When you authorize, the runtime opens that tool’s gate so the agent can call it; until then the runtime hard-blocks the call. Whenever your remediation instructs the agent to call a WRITE tool you have judged its prerequisites met, so set that intent’s authorize_tool to that tool the same turn -- never instruct a WRITE call while leaving authorize_tool null. The authorizing remediation must state the exact arguments the agent must pass -- every id and value from grounded results, with any amounts, counts, or derived figures computed from the state the requested changes produce rather than from the prior state, so they reconcile with the tool’s requirements -- and cover every change the user requested, so the agent does not guess, miscompute, or omit a step. To change specific fields of an existing record, reuse the record’s current values for the fields the user is not changing rather than searching for or re-collecting new ones; and never withhold authorization to first establish a value the write tool itself computes or returns -- such an output is not a prerequisite. When the tool applies to several records, draw each call’s arguments from that record’s own grounded data and confirm the pairing before authorizing -- a value belonging to one record must never cross into another, since the call cannot be undone. Figure 8: Guide system prompt, part 2 of 3: judging rules (i)—evidence grounding and mutating-tool authorization. Judging rules · sourcing, transfer, fixes, reads ⬇ - Source every write argument. Before authorizing a WRITE, record in grounded_values where each argument’s value came from -- the tool result and record it was copied from, or ’user message’. A value whose source is the user’s word for a field a record owns is not grounded: read it from that record and use the record’s value. - Transfer. Signal transfer only when a request cannot be handled within policy at all (e.g. an action the policy reserves for a human, or the user insisting on a policy-violating action). Transfer ends the whole conversation, so signal it only when no open request can still be advanced within policy; when one request is blocked but others remain handleable, refuse only the blocked one and keep completing the rest rather than transferring. Never transfer an action the policy actually permits. transfer_to_human_agents is that signal, not an ordinary tool to authorize: whenever your remediation instructs the agent to call it you have judged the whole remaining task unhandleable, so set the top-level transfer to true the same turn -- the runtime opens that call only when transfer is true, so a remediation to transfer while transfer stays false contradicts itself and is blocked. - Carry out the fix, not just name it. When resolving an open request requires a corrective action the graph gates inside another intent’s subflow, open that action as an additional active intent and traverse its subflow so its tool can be authorized; the original request is resolved only once every corrective action its situation requires has been carried out, not when the cause is merely identified. - Delegate READ tools to obtain facts. Establish any detail a READ/lookup tool can supply, or that a prior tool result already holds, from that result -- delegate the lookup or read the loaded data -- rather than asking the user. When advancing a request needs an identifier, record, or argument value the user has not supplied, do not ask for it -- direct the agent to enumerate the candidate records the READ tools return and select every one whose contents match the request’s described attributes or the criterion the user stated, deriving each argument from that loaded data; a request that describes its target by attributes rather than by id is satisfied only once every matching record has been handled, not after the first. Judging rules · the remediation contract ⬇ - Remediation. A remediation is the exact next action for the agent: which tool to call with which arguments, or the value the user asked for computed from the tool results and stated back to them, or which detail to ask the user for (ask the user ONLY for things no tool can supply), or that the agent must refuse and the precise policy reason. A request for a value is resolved only once the agent has stated that value, not when a related action is done. When a node is not satisfied, the remediation must name the specific prerequisite that is missing and the concrete action that would obtain or satisfy it, never a generic statement that the conditions are unmet. Keep it concrete and grounded in the policy and the conversation. When the next steps along the intent’s path are agent-side and already fully determined -- none needing a reply from the user and none whose arguments depend on a tool result you do not yet have -- write one remediation listing those ordered steps to carry out in a single stretch rather than one step per turn, splitting only at the first step that needs the user or a result you do not yet have. When the user has stated a selection or optimization criterion, first enumerate every candidate in the space the criterion ranges over from the tool results, then identify the single winning option by comparing that criterion across all of them and pinning the winning option’s exact arguments -- never select from a partial candidate set, offer an unranked list, or ask the user to choose among candidates the criterion already decides. Every identifier you place in a remediation must appear verbatim in the specific tool result you are selecting it from -- never carry an identifier over from a different record (such as the one already on file) or introduce one not present in that result. Figure 9: Guide system prompt, part 3 of 3: judging rules (i)—argument sourcing, transfer scoping, corrective-fix traversal, read-tool delegation (left) and the remediation contract (right). Generation system prompt · runtime contract ⬇ A proactive verifier reads the WHOLE graph plus the full conversation each turn, tracks where each open request sits, and writes the agent’s next-step remediation. Two things the graph must make enforceable: - Mutating tools are gated. A tool_authorization node is the choke point for one WRITE tool: the agent may call that tool ONLY after the guide authorizes it (its upstream prerequisites met) and the runtime confirms success at the following verify node. So every prerequisite/eligibility/confirmation a mutation requires must sit UPSTREAM of its authorization node. - Faithfulness. The guide can only enforce what the graph encodes. The graph must reflect the policy and the domain’s tool/task properties exactly. Generation system prompt · authoring essentials 1–3 ⬇ The bottom line: the graph must (A) reflect the policy faithfully, (B) reflect the domain’s tool/task properties, and (C) be valid + minimal. 1. Cover every WRITE tool. Each mutating tool is reachable through some intent and ends in an authorize_<short> (tool_authorization) -> verify_<tool> (agent_action) pair -- the authorization choke point and the post-call success check (the tool can fail, so the verify node confirms a successful TOOL_RESULT and, on error, directs a correctable retry). Place everything the policy requires before a mutation UPSTREAM of its authorization. A value the mutating tool itself computes or returns is an output, not a prerequisite. 2. Gates are outcome-framed. An eligibility/permissibility gate is SATISFIED only if the permitting condition actually HOLDS -- never "has the agent checked X?" (that flips true the moment the check runs, even when it concludes ineligible). When the condition fails, the gate stays NOT_SATISFIED and its remediation REFUSES. Keep gates as agent_action nodes on the main path -- do not model refusal as a branch to a dead-end exit. 3. Ground facts in tools; quote the policy exactly. A fact/eligibility condition counts only when established by a tool result -- not a user assertion. The user’s own consent/preference is established by the user’s message. Where the environment gates on an exact status/enum literal, quote it and require exact equality (a qualified variant is a different value), and name whose field. Quote limits/prices/amounts/time-windows verbatim, identically across expectation/evaluation_prompt/remediation_template. Encode only conditions the policy states -- never invent a check no tool/data can establish. Generation system prompt · authoring essentials 4–7 ⬇ 4. Classifier completeness. The main classify decision has one branch per intent + general (anything unsupported -> a non-transfer refusal exit) + transfer (must go to a human). Operations the policy forbids outright get NO subflow -- they route to general. 5. Right tool side. tool_call/tool_authorization may name ONLY tools from the AGENT inventory. An action the END USER performs on their own device is an agent_action that instructs the user and judges their reported outcome -- never a tool node (which could never be satisfied). 6. Minimal + faithful. Author the fewest nodes that enforce the policy. Fold a validation/disclosure into the node that collects its data; merge related collection steps rather than one node per policy sentence. Every normative policy statement must be enforced by some node (or be genuinely out of graph scope). When the policy enumerates the possible causes of a problem, the flow that resolves it must check every documented cause; a cause whose remedy is a mutating tool must be its OWN checkpoint that reaches that tool’s authorization. 7. Main spine + shared subflows. main: entry -> intake (greet + open question) -> identify (shared identification subflow) -> classify -> intent subflow anchors -> exits ["exit_normal","exit_general","exit_transfer"]. Any procedure shared by 2+ intents may be its own subflow. When the domain has user-owned records that requests target, the identification subflow ends with a tool_call that loads the authenticated user’s full account record. Figure 10: Workflow-generation system prompt: the runtime contract the graph must satisfy, and the authoring-essentials contract every stage must follow. Stage 2 · plan requirements ⬇ 1. Cover every WRITE tool. Each mutating tool is reachable through at least one intent subflow ending in its authorize -> verify pair. 2. Intents from the policy, not just the tools. Include advisory/no-tool intents the policy describes and procedure-driven intents from any troubleshooting manual. Unify all policy documents into ONE flat intent taxonomy. 3. Two archetypes. Transactional (mutate a record): load the target -> gate eligibility -> confirm -> execute. Troubleshooting (diagnose a symptom against a manual): an ordered checklist -- check a documented cause -> apply its fix -> re-test -> continue; resolve on a passing re-test, escalate after all causes exhausted. An agent WRITE-tool fix routes into that tool’s mutating subflow; a user-device fix is an agent_action instructing the user. 4. Shared subflows. Plan the identification subflow and a present_summary_and_confirm subflow. 5. Per-subflow skeletons: ordered steps, id/type/tool/gist citing the policy line(s). Order: load target (tool_call) -> eligibility gate(s) -> collect details/disclosures -> summary_and_confirm -> authorize -> verify -> exit. 6. Coverage audit. Walk the policy section by section; assign every normative statement to a step, or list it as excluded (with a reason). 7. Lean. Fewest subflows and nodes that enforce the policy. Stage 6 · adversarial review checklist ⬇ 1. Policy completeness. Walk the policy line by line. Every normative statement must be enforced by some node’s criteria (or be genuinely out of graph scope). Fix any missing rule, wrong number, or weakened condition. 2. Cause coverage (enumerate explicitly). Wherever the policy enumerates the possible causes/conditions of a problem, list every one and name the node whose criterion handles it. If any cause has no node, add it. 3. Essentials compliance. Gates outcome-framed; environment-gated enums quoted with exact equality and whose-field named; facts grounded in tool results; every WRITE tool has its authorize -> verify pair with everything the policy requires upstream. Tool nodes name only agent-inventory tools. 4. Graph sanity. Entry reaches every node; every node reaches an exit; decision branch labels/targets consistent; classifier covers all intents + general + transfer. 5. Over-restriction sweep. A node whose criterion cannot be satisfied from the available tools/data is a transfer machine -- relax it to the policy’s actual condition. If nothing needs changing, output exactly: NO_CHANGES Figure 11: Workflow-generation stage prompts: the plan stage’s requirements (left) and the adversarial reviewer’s checklist (right). Figures 12–14 use the following shared node notation. agent_action user_input tool_call (read) tool_authorization (authorize mutation) decision entry/exit subflow anchor identify_user subflow (shared) present_summary_and_confirm subflow (shared) book_reservation subflow (composed as book_flow.*) start entry intake agent_action ask_user_id user_input load_profile tool_call: get_user_details classify decision exit_general exit exit_transfer exit other request-type subflows (modify, cancel, refund, …) generaltransfer… collect_trip agent_action search_flights tool_call: search_*_flight collect_ passengers agent_action collect_payment agent_action offer_insurance agent_action collect_baggage agent_action present_summary agent_action explicit_ confirmation user_input authorize_book tool_authorization: book_reservation verify_book_ reservation agent_action booked exit book flight Figure 12: Airline: the composed workflow graph—the shared spine (start, intake, the identify_user subflow, classify) and the full transactional book_reservation request path. Solid edges fire only when: satisfied; dashed edges are classifier branches. The mutating tool is represented downstream of its tool_authorization node (trapezoid), immediately followed by the verify node that demands a successful TOOL_RESULT. cancel_pending_order subflow start entry intake agent_action identify_user shared subflow classify decision refuse_general agent_action transfer_case tool_call other request subflows (modify, return, exchange, account) generaltransferother intents locate subflow: locate_order verify_status_ pending agent_action (gate) obtain_reason agent_action summary_and_ confirm subflow (shared) authorize_cancel tool_authorization: cancel_pending_order verify_cancel_ pending_order agent_action cancelled exit cancel pending order Figure 13: Retail: the shared entry–intake–identification spine and classifier dispatch into request-specific subflows, with cancel_pending_order expanded. Its status and reason gates, shared summary-and-confirm step, authorization, and post-call verification form the complete cancellation path. The gray box marks the expanded cancellation subflow; the dotted box summarizes the other classifier branches. pay_overdue_bill subflow (authorizes send_payment_request) troubleshoot_mms subflow (prerequisites Service ⊂ Data ⊂ MMS) start entry intake agent_action identify_customer shared subflow classify decision exit_general exit transfer_to_human subflow other request subflows (line, plan, roaming, data, cellular) generaltransferother intents obtain_bill_id agent_action load_bill tool_call: get_bill verify_status_ overdue agent_action (gate) verify_no_ awaiting_payment agent_action (gate) summary_and_ confirm subflow (shared) authorize_send_ payment_request tool_authorization verify_send_ payment_request agent_action sent exit pay overdue bill confirm_mms_ issue agent_action verify_service agent_action (prereq) verify_mobile_ data agent_action (prereq) check_network_ tech agent_action check_wifi_ calling agent_action check_app_ permissions agent_action check_apn_mmsc agent_action decide_ outcome decision resolved exit transfer_node agent_action transferred exit MMS issueresolvedtransfer Figure 14: Telecom: the shared entry–intake–identification spine and classifier dispatch, with two request branches expanded. The overdue-bill branch invokes pay_overdue_bill, which gates send_payment_request; the MMS branch invokes troubleshoot_mms, which checks service and data prerequisites before the documented MMS causes and closes by resolving or transferring. The dotted box summarizes the remaining classifier branches. Appendix I The Use of LLMs We used LLMs solely for light editing, such as correcting grammatical errors and polishing wording. They did not contribute to research ideation, experiments, analysis, or substantive writing.

Instant research discovery