Source-linked AI summary
Beyond IVR: Benchmarking Customer Support LLM Agents for Business-Adherence
Sumanth Balaji, Piyush Mishra, Aashraya Sachdeva, Suraj Agrawal
TL;DR
JourneyBench addresses the challenge of evaluating whether customer-support agents follow business policies and procedural requirements. It represents SOPs as graphs, generates diverse user journeys, and measures adherence with UJCS; across 703 conversations in three domains, structured workflow orchestration outperformed prompt-based approaches, with smaller models exceeding larger ones in policy compliance.
Problem
Evaluating whether customer-support agents follow business policies and procedural requirements remains a core challenge, including adherence to required steps, validations, and exception handling.
Method
JourneyBench represents SOPs as directed acyclic graphs, generates diverse user journeys through those workflows, and uses the User Journey Coverage Score to measure adherence to required action sequences.
Results
Across 703 conversations in three domains, Dynamic-Prompt-Agent orchestration significantly outperformed Static-Prompt-Agent approaches, enabling smaller models to exceed larger ones in policy compliance.
Takeaways & Limitations
The findings demonstrate the value of structured workflow orchestration for policy-aware customer-support agents beyond rigid IVR systems.
Takeaways & Limitations
The Dynamic-Prompt-Agent depends on precise business-logic modeling, while simulation-based evaluation may not capture all nuances of real-world user behavior.
Abstract
from arXiv · showhide
Traditional customer support systems, such as Interactive Voice Response (IVR), rely on rigid scripts and lack the flexibility required for handling complex, policy-driven tasks. While large language model (LLM) agents offer a promising alternative, evaluating their ability to act in accordance with business rules and real-world support workflows remains an open challenge. Existing benchmarks primarily focus on tool usage or task completion, overlooking an agent's capacity to adhere to multi-step policies, navigate task dependencies, and remain robust to unpredictable user or environment behavior. In this work, we introduce JourneyBench, a benchmark designed to assess policy-aware agents in customer support. JourneyBench leverages graph representations to generate diverse, realistic support scenarios and proposes the User Journey Coverage Score, a novel metric to measure policy adherence. We evaluate multiple state-of-the-art LLMs using two agent designs: a Static-Prompt Agent (SPA) and a Dynamic-Prompt Agent (DPA) that explicitly models policy control. Across 703 conversations in three domains, we show that DPA significantly boosts policy adherence, even allowing smaller models like GPT-4o-mini to outperform more capable ones like GPT-4o. Our findings demonstrate the importance of structured orchestration and establish JourneyBench as a critical resource to advance AI-driven customer support beyond IVR-era limitations.
1 Introduction
JourneyBench addresses the gap between customer-support agents’ conversational flexibility and their need to follow multi-step business policies. It introduces graph-based policy evaluation and shows the value of structured workflow control.
- Traditional IVR systems enforce compliance through rigid decision trees but often provide inflexible, frustrating user experiences.
- Existing benchmarks assess tool selection and state transitions but inadequately evaluate complete task sequences with complex inter-task dependencies.
- JourneyBench represents standard operating procedures as graphs to generate diverse customer-support scenarios involving branching logic, missing inputs, and tool failures.
- The User Journey Coverage Score measures whether agents follow the required sequence of SOP-defined actions.
- A Dynamic-Prompt Agent guided by workflow structure performs more reliably than a Static-Prompt Agent, highlighting the value of structured control in business settings.
2 JourneyBench Framework
JourneyBench models business workflows as graph-structured SOPs and derives reproducible conversational scenarios from their paths. Its framework combines explicit workflow representations, simulated interactions, and varied conditions for testing policy adherence.
- JourneyBench comprises SOP graphs, task nodes, user journeys, and scenarios that test agent robustness under varied conditions.
- SOPs are modeled as directed acyclic graphs whose nodes represent tasks and whose edges encode valid transitions, decision points, and policy constraints.
- Each node specifies a natural-language task description, available tools, parameters, and conditional pathways that determine the next node at runtime.
- Validated SOP graphs generate user journeys through Breadth-First Search, after which multiple scenarios vary inputs and tool behavior while preserving expected outcomes.
- 703 datapoints average 10.91 turns and 3.34 tool calls per conversation across a 41-tool benchmark.
3 Evaluation Metrics
The evaluation measures strict adherence to expected tool-call journeys and parameter execution through the User Journey Coverage Score (UJCS).
- Tool Trace Alignment compares predicted and expected tool-call sequences, treating missing, extra, or misordered calls as SOP violations.
- For each tool call, the score accounts for the number of correctly supplied parameters relative to the expected parameters.
- The expected trace length is L = |Texp|, and conversation-level performance is represented by Sconv.
- UJCS aggregates adherence across N simulated conversations for an SOP graph.
4 Experimentation
The experiments compare static prompting with dynamic workflow-state control across controlled scenarios, robustness disturbances, and production deployment. Results favor DPA for policy adherence and robustness, including for a smaller model.
- Agent designs: DPA processes one SOP node at a time and updates orchestration after each tool execution, whereas SPA places the entire SOP in one static prompt.
- Agent designs: The study excludes explicit planning approaches because their latency is considered unsuitable for real-time customer support, using a custom runtime-state framework instead.
- Experimental setup: Experiments use a 40-turn limit and a GPT-4o simulated user following predefined journeys without information leakage.
- Experimental setup: JourneyBench generates failed-function and missing-parameter scenarios from correct-context journeys to test robustness.
- Deployment: Production DPA-based systems handle 6,000+ daily calls while applying the evaluated text-based workflow logic to voice interactions.
- Results: GPT-4o with DPA achieves a UJCS of 0.717 versus 0.564 for SPA, while DPA maintains stable coverage under failed functions and missing parameters.
- Results: GPT-4o-mini with DPA scores 0.649, exceeding GPT-4o with SPA at 0.564 and showing that structured orchestration can benefit smaller models.
- Error analysis: Error analysis identifies dependency violations, parameter hallucination, and user-simulator failures as distinct error classes.
5 Related Work
Prior benchmarks advance tool-use and stateful execution evaluation but generally do not measure fidelity to complex, prescribed journeys or robustness to disturbances. JourneyBench targets these gaps while decoupling workflow evaluation from tool implementations.
- Tau Bench, Tau2-Bench, ToolSandBox, and AppWorld evaluate multi-turn tool use, dual-control environments, stateful execution, or world-state tracking.
- These frameworks primarily measure tool selection or state changes rather than fidelity to prescribed multi-step journeys with complex dependencies.
- JourneyBench additionally evaluates policy adherence, task dependencies, and robustness to conversational disturbances and dynamic tool failures.
- JourneyBench separates workflow evaluation from tool internals by treating tools as modular components with defined interfaces and evolving implementations.
6 Conclusion
JourneyBench evaluates policy-aware customer-support agents with graph-based workflows and UJCS, finding that structured DPA orchestration outperforms SPA across broad testing and deployment settings.
- JourneyBench addresses the need to combine conversational flexibility with strict policy adherence beyond rigid IVR systems.
- Across 703 conversations in three domains, DPA significantly outperforms SPA and enables smaller models to exceed larger ones in policy compliance.
- DPA-based production systems reliably handle 6,000+ daily customer interactions while meeting real-time and policy-adherence requirements.
7 Limitations and Future Work
The framework’s effectiveness is bounded by the quality of business-logic modeling, simulation realism, and evaluation cost. Future work targets automated graph construction, richer dependencies, and cheaper evaluation.
- DPA success depends on precise business-logic modeling, which is difficult in dynamic or poorly documented fields.
- Simulation-based evaluation may not capture all nuances of real-world user behavior.
- $388.88 in evaluation cost constrained the range of tested models.
- Future research could explore semi-automated graph generation, more cost-effective evaluation, and complex dependency structures.
8 Ethical Considerations
JourneyBench’s synthetic workflows and conversations introduce risks related to bias and evaluation validity, while automation may affect workforce composition. The paper recommends expert validation, human assessment, real-world bias checks, and responsible transition planning.
- Synthetic workflows and conversations may inherit LLM biases, motivating domain-expert validation and real-world bias checks.
- LLM-generated evaluation data can introduce circularity, so JourneyBench should be paired with human assessment and production-behavior alignment.
- The paper suggests customer-support automation may shift work toward higher-complexity tasks rather than directly displacing staff.
- Organizations should plan responsible workforce transitions and training as customer-support automation is deployed.
G.1 Missing Parameters
The missing-parameter examples contrast an SPA that proceeds without required customer information with a DPA that preserves verification requirements and halts when necessary inputs or tools are unavailable.
- The SPA proceeds to other tasks after the user lacks a Customer ID, rather than preserving the verification dependency.
- The DPA states that verification cannot proceed without the Customer ID because it is essential for account verification.
- When an internal server issue prevents verification, the DPA says it cannot complete the verification at that moment.
- After the verification issue, the user redirects the conversation toward checking a Downtown service outage.
- The SPA responds that an outage affects Downtown and offers further assistance.
H Hallucinations in Parameter Values
The example shows parameter hallucination: the agent uses a tool-description example value instead of the user-provided credit score. Both agent types exhibit this error.
- Both Dynamic-Prompt-Agent and Static-Prompt-Agent examples are presented in the parameter-hallucination discussion.
- The agent should use the user-provided credit score of 720 but instead uses the example value 700 from the parameter description.The resulting analysis reports a score of 700 as good.
- The parameter definition identifies creditScore as an integer extracted from the report when the credit report is available.
- In the Dynamic-Prompt-Agent conversation, the user supplies a credit score of 720 before the tool analyzes the value as 700.
I User Input Hallucination Example
The examples illustrate two user-agent failures: a simulated user supplies information absent from its seed, and another conversation ends before completing the prescribed journey.
- User Input Hallucination Example: The simulated user provides a payment method even though no payment method was included in the user seed.The conversation therefore should not have proceeded.
- User Input Hallucination Example: The agent asks the user to choose among Credit Card, PayPal, and Bank Transfer, after which the user answers Credit Card.
- User Input Hallucination Example: The full journey requires Service Calls Analysis after Billing Info Retrieval, but the agent ends the conversation after retrieving billing information.
- K Human Validation Protocol: Human validation reviews graphs for logical structure, coherence, and complexity, accepting only graphs that all five annotators unanimously pass.
L Realism Validation Summary
Synthetic conversations are evaluated against production-oriented quality criteria and achieve averages comparable to production QA bands. The examples also show that Dynamic-Prompt-Agent can handle a user correction within a workflow node.
- L Realism Validation Summary: The realism rubric evaluates conversational proficiency through questions about tone, empathy, friendliness, concision, and clarity.
- L Realism Validation Summary: Goal Attainment evaluates whether the agent identifies the caller’s intent and resolves or properly escalates the primary request.
- L Realism Validation Summary: Synthetic conversations achieve 84.37% overall, with 82.33% Conversational Proficiency and 87.78% Goal Attainment.Scores average binary rubric responses across conversations.
- L Realism Validation Summary: Grouping dependent tools within a node lets the Dynamic-Prompt-Agent incorporate a user correction without restarting the process.The example updates the income category from Salaried to Self-Employed and recollects the income details.