Conceptio › Archive › arXiv CS

arXiv CSopen access

SAGE: A Service Agent Graph-guided Evaluation Benchmark

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

artificialintelligence knowledgerepresentation reasoning

artificial intelligence, reasoning, knowledge representation

arXiv:2604.09285v1 [cs.AI] 10 Apr 2026

SAGE: A Service Agent Graph-guided Evaluation Benchmark Ling Shi∗

Yuqin Dai∗

Ziyin Wang

Tianjin University Tianjin, China

Tsinghua University Beijing, China

Tianjin University Tianjin, China

Ning Gao

Wei Zhang

Chaozheng Wang

Beihang University Beijing, China

Beijing University of Posts and Telecommunications Beijing, China

The Chinese University of Hong Kong Hong Kong, China

Yujie Wang

Wei He

Jinpeng Wang

Independent Researcher Beijing, China

Deyi Xiong† Tianjin University Tianjin, China

Abstract

CCS Concepts

The development of Large Language Models (LLMs) has catalyzed automation in customer service, yet benchmarking their performance remains challenging. Existing benchmarks predominantly rely on static paradigms and single-dimensional metrics, failing to account for diverse user behaviors or the strict adherence to structured Standard Operating Procedures (SOPs) required in realworld deployments. To bridge this gap, we propose SAGE (Service Agent Graph-guided Evaluation), a universal multi-agent benchmark for automated, dual-axis assessment. SAGE formalizes unstructured SOPs into Dynamic Dialogue Graphs, enabling precise verification of logical compliance and comprehensive path coverage. We introduce an Adversarial Intent Taxonomy and a modular Extension Mechanism, enabling low-cost deployment across domains and facilitating automated dialogue data synthesis. Evaluation is conducted via a framework where Judge Agents and a Rule Engine analyze interactions between User and Service Agents to generate deterministic ground truth. Extensive experiments on 27 LLMs across 6 industrial scenarios reveal a significant “Execution Gap” where models accurately classify intents but fail to derive correct subsequent actions. We also observe “Empathy Resilience”, a phenomenon where models maintain polite conversational facades despite underlying logical failures under high adversarial intensity. Code and resources are available at https: //anonymous.4open.science/r/SAGE-Bench-4CD3/.

• Computing methodologies → Multi-agent planning; Discourse, dialogue and pragmatics.

∗ Both authors contributed equally to this research. † Corresponding Author

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. KDD ’26, Jeju Island, Republic of Korea © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-XXXX-X/2018/06 https://doi.org/XXXXXXX.XXXXXXX

Keywords Service Agent, Graph-guided Evaluation, Multi-agent Interaction ACM Reference Format: Ling Shi, Yuqin Dai, Ziyin Wang, Ning Gao, Wei Zhang, Chaozheng Wang, Yujie Wang, Wei He, Jinpeng Wang, and Deyi Xiong. 2026. SAGE: A Service Agent Graph-guided Evaluation Benchmark. In Proceedings of The 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD ’26). ACM, New York, NY, USA, 18 pages. https://doi.org/XXXXXXX.XXXXXXX

Introduction

The rapid advancement of Large Language Models (LLMs) has significantly accelerated the automation process across various industrial sectors [2, 42, 46]. Among these, the domain of intelligent customer service has emerged as a pioneer in adopting these technologies to enhance operational efficiency and user experience [7, 28, 43]. By leveraging the robust generative capabilities and context understanding of LLMs, enterprises are striving to transition from traditional, rigid rule-based systems to highly adaptive intelligent service agents [44, 47] capable of handling complex interactions [36, 53], thereby addressing a broader range of customer needs while reducing labor costs. Consequently, benchmarking models on their strict adherence to Standard Operating Procedures (SOPs) for correct workflow transitions, a process requiring the generation of structured responses that align with predefined logic as shown in Figure 1, has become a priority for enterprises. However, existing service benchmarks face three fundamental limitations. First, insufficient evaluation dimensions: Current benchmarks typically assess either task completion [20, 25, 31] or dialogue quality [41, 59] in isolation. Realworld scenarios, however, demand both strict logical compliance with SOPs and appropriate communication skills. This metric insufficiency causes evaluation bias and hinders precise error localization.

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea 1 Input Context Extraction

2 Standard Operating Procedures

Penalty

OrderId

PackageStatus

…… Change

Dialogue History Hello, I placed the wrong ……

…… I want to change my package ……

y Enquir

Sorry to hear that let me check …

Stage3: View Penalty

lm Ca

ChangeOrder

!=0

Stage2: View ConsumptionType Stage5: View PackageStatus

tent Discon TrasnferHuman Stage4: View EmotionTag

Chat

…

Data/Voice Reject/Hesitate Stage6: View Stage7: View ConsumptionProfile ApplicationTendency

4 Replying to User Your order has not been shipped……

• We uncover critical phenomena such as the “Execution Gap” and “Empathy Resilience”, providing granular diagnostics for agentic capabilities, through extensive experiments on 27 LLMs across 6 distinct scenarios. • We design a modular Extension Mechanism for low-cost adaptation to new scenarios, which also facilitates the automated synthesis of large-scale dialogue datasets for customer service.

Cancel Contr acted

Stage1: Classification

System Information

Ling Shi et al.

Goodbye

3 Service Agent Structured Response Chat: × ……

Classification Fields: ……

Path: [stage1, stage2, stage3,stage4’]

Action: TransferHuman

Figure 1: Service Agent SOP Example (Telecom Scenario).

Second, static interaction paradigms: Relying on fixed datasets like scripts [5, 34, 58], traditional methods fail to test error recovery or cover diverse user behaviors, ranging from cooperative inquiries to adversarial conflicts. Consequently, these static evaluations are incomplete and struggle to reflect real-world performance. Finally, limited scalability: Benchmarks often depend on costly manual annotation [22, 33] and are frequently over-fitted to the SOPs of a single domain, making it prohibitively expensive to adapt to diverse, multi-branch business scenarios. To address these challenges, we propose SAGE (Service Agent Graph-guided Evaluation). SAGE integrates three core contributions: (1) Dynamic Multi-Turn Dialogue Graph Modeling, which formalizes SOPs into directed graphs (as shown in Figure 1) to enable dynamic verification of logical compliance and ensure comprehensive path coverage; (2) a Multi-Agent multi-dimensional Evaluation utilizes Judge Agents and a Rule Engine to analyze the interaction between User and Service Agents, generating deterministic ground truth for a rigorous, multi-dimensional assessment of logical compliance and chat quality; and (3) a Scenario Extension Mechanism, which enabled the rapid deployment of six industrial scenarios in our study, demonstrating its practical feasibility. To validate SAGE, we evaluated 27 mainstream LLMs across 6 industrial scenarios. Our experiments reveal: (1) The gap between open-source and closed-source models is narrowing, with DeepSeek-V3.2 surpassing several GPT-4 class models; (2) A significant “Execution Gap” in complex scenarios, where high classification accuracy does not guarantee correct action execution, highlighting the challenge of procedural reasoning; (3) Performance degradation in multi-turn dialogues due to context fatigue; and (4) “Empathy Resilience” under high adversarial intensity, where models maintain polite conversational facades despite underlying logical failures. In summary, our contributions are: • We propose SAGE, the first graph-guided multi-agent evaluation benchmark that transforms unstructured SOPs into directed graphs to enable automated, dual-axis assessment of logical compliance and conversational quality. • We introduce dynamic graph modeling and an Adversarial Intent Taxonomy, bridging the gap between static testing and dynamic reality through diverse user behavior simulations.

2 Related Works 2.1 Evaluation for Large Language Models Large language model evaluation has evolved from basic instructionfollowing [60] to complex multi-constraint scenarios. Early benchmarks assessed format compliance [38, 48], while recent work evaluates real-world complexity through Multi-IF [15], FollowBench [16], and InfoBench [32]. Guidebench [8] introduces domain-specific conditions, and Collie [52] systematically constructs constrained generation tasks. Domain-specific evaluation spans business process management [4, 12–14, 17, 18, 35], finance [49, 50], and procedural compliance. SOPBench [22] and SOP-Bench [27] evaluate tool-calling sequences but primarily focus on external manipulation rather than deep logical reasoning. Broader agent frameworks include AgentBench [25], WebArena [61], and WorkArena [9]. Complementing mathematical tasks, textual logical reasoning, and reading comprehension are assessed through LogiQA [24] for deductive reasoning, DROP [10] for discrete reasoning over paragraphs, and HotpotQA [51] for multi-hop reasoning, which are more closely aligned with the context understanding required in service scenarios. Agent training advances include AGILE [30], ReAct [53], Reflexion [36], Agent-Pro [57], AgentTuning [54], Self-Refine [26], Self-Instruct [45], and human feedback training [29]. Unlike prior benchmarks limited by static datasets and single-dimensional metrics, SAGE introduces a graph-guided multi-agent framework to dynamically evaluate both the logical compliance and conversational quality of service agents.

2.2

Benchmarks for Service Dialogue Systems

Service dialogue evaluation addresses customer-facing applications through DialogBench [28] for human-like conversation, EComBench [43] for customer support resolution. Multi-turn complexity is captured by MG-ShopDial [3], Wizard of Shopping [21], and Parrot [37]. Customer support dialogue is studied through evaluation frameworks [62], real-world conversation data [58], and recommendation as instruction following [56]. Existing benchmarks often rely rigidly on scenario-specific Standard Operating Procedures (SOPs), limiting their adaptability. SAGE addresses this with a modular, intent-based extension mechanism that enables rapid, code-free adaptation to new domains.

Methodology

To address the complexity of evaluating customer service LLMs, we propose SAGE, a graph-guided multi-agent framework. As shown in Figure 2, the workflow integrates three key stages: (1) Dynamic Multi-Turn Dialogue Graph Modeling formalizes SOPs into directed graphs to enable dynamic verification of logical compliance against correct paths while ensuring comprehensive coverage of

SAGE: A Service Agent Graph-guided Evaluation Benchmark

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Scenario Config

Intent Distribution Prompt Template

Zero Weak Strong Adversarial User Intents

SOP Design

Graph Modeling Rule Engine

Dual-axis Results

Intent Persona ……

User Agent

…

Service Agent

…

Voting & Scoring "CoreGoal": "Exchange", "ChatQualityScore": S3

Judge Agent 1

"CoreGoal": "Return",❌

Judge Agent 2

" ChatQualityScore ": S2

Multi-Turn Dialogue Simulator

…

Dynamic Evaluator

User Config

Graph-Guided Multi-Agent Evaluation

"CoreGoal": "Exchange", " ChatQualityScore ": S1

Right Label Classification Rule Engine

Action Path

Judge Agent 3 Metrics

Avg(S1,S2,S3)

ChatScore

Classification_Acc Action_Acc

Path_Acc

LogicScore

Figure 2: Overview of SAGE evaluation framework. all potential scenarios; (2) Graph-Guided Multi-Agent Evaluation rigorously assesses these trajectories; and (3) an Scenario Extension Mechanism that leverages both user intents and SOPs to enable rapid adaptation to arbitrary scenarios through modular configuration. We begin by detailing the graph formalization process.

as the navigation map for the Service Agent and the evaluation standard for the Rule Engine. Crucially, System Information S is consistently propagated throughout the process: it is used to shape the User Agent’s persona, utilized by the Service Agent for decision-making, and finally employed by the Rule Engine to generate process ground truth. This consistency ensures the fairness and determinism of the evaluation.

3.1

3.1.2 User-Agent Multi-turn Interaction. To overcome the limitations of traditional benchmarks, we generate dialogue trajectories through dynamic interaction between user agents and service agents. User Agent generates user responses based on personas and dialogue context:

Dynamic Multi-Turn Dialogue Graph Modeling

Aiming at a systematic evaluation of LLMs applied in service agent, we transform SOPs into computable graphs to underpin our framework, thereby allowing for automated logical verification and comprehensive scenario traversal. 3.1.1 Procedure Graph Formalization. Customer service Standard Operating Procedures (SOPs) typically exist as natural language documents containing numerous conditional branches as shown in Figure 1. Using such unstructured descriptions directly for automated evaluation is prone to ambiguity. Therefore, we formalize SOPs as directed graphs 𝐺 = (𝑉 , 𝐸). The node set 𝑉 consists of three types: (1) Start/End Nodes; (2) Decision Nodes, which branch the flow based on specific conditions; and (3) Action Nodes, representing concrete operations. The edges 𝐸 define the transition logic, where transitions are triggered by the values of specific Classification Fields F (e.g., Order Type) and System Information S. This graph structure serves as the backbone of SAGE. It functions both

𝑎𝑡 = UserAgent(ℎ <𝑡 , 𝑠𝑡 , S, I, P).

(1)

The user agent’s role is to provide dynamic adversarial testing for the service agent. The generated message 𝑎𝑡 comprehensively considers five factors: (1) dialogue history ℎ <𝑡 , which references previous exchanges; specifically, when history is empty, a dedicated initialization function is triggered to generate the opening utterance to populate ℎ <𝑡 ; (2) agent state 𝑠𝑡 , utilized to align the user’s response with the agent’s current status, including handling opening protocols and detecting dialogue termination conditions; (3) system information S, which grounds the user’s knowledge in reality (e.g., knowing their own payment status) to prevent hallucinations and ensure logical consistency; and crucially, (4) user

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Ling Shi et al.

intent I and (5) user persona P. As further detailed in Section 3.3, I determines the user’s fundamental goal (e.g., refund vs. inquiry), while P characterizes the user persona (encompassing traits such as emotional state, communication style, and cooperativeness). Both are dynamically instantiated to simulate diverse adversarial intensities. Service Agent is the evaluation target tasked with navigating the SOP graph to generate a structured response. The output at turn 𝑡, denoted as 𝑏𝑡 , comprises four distinct components: 𝑏𝑡 = ServiceAgent(S, ℎ <𝑡 , 𝑎𝑡 , 𝐺) = {𝑝𝑡 , action𝑡 , F𝑡 , chat𝑡 }.

(2)

Here, 𝐺 represents the SOP graph described by text. The components of 𝑏𝑡 are defined as follows: (1) 𝑝𝑡 denotes the path, representing the nodes the agent intends to traverse in the current turn; (2) action𝑡 is the executed action, selected from the allowable action set A defined by the current node; (3) F𝑡 represents the classification fields, capturing the agent’s categorical judgment of specific classification fields (e.g., user emotion type); and (4) chat𝑡 is the natural language chat response generated to interact with the user. The agent’s core objective is to accurately identify the classification field F𝑡 , which dictates the subsequent transition path 𝑝𝑡 and the mandated action action𝑡 within graph 𝐺, ultimately conditioning the generation of the response chat𝑡 . Consequently, the User Agent acts as an environment, presenting a specific service scenario to the Service Agent. The Service Agent must then navigate multi-turn interactions to achieve specific goals while strictly adhering to the SOP. We evaluate these generated dialogue trajectories in the subsequent sections.

3.2

Graph-Guided Multi-Agent Evaluation

Upon the completion of dialogue trajectory generation, SAGE executes a systematic evaluation through a graph-guided, multi-agent collaborative mechanism. To ensure that all potential business scenarios and logical branches are rigorously tested, we enforce Path Coverage as the first component, verifying that the generated trajectories span the entire state space of the formalized SOP graph. Following this structural validation, SAGE performs a granular assessment of individual interactions. In this architecture, each node and its corresponding edge are evaluated through a hybrid mechanism: a Judge Agent extracts categorical labels and linguistic nuances from the dialogue, while a Rule Engine cross-validates these outputs against the graph-defined logic. This dual-layered approach allows SAGE to simultaneously assess Logical Compliance and Chat Quality, ensuring that agents are both procedurally correct and contextually appropriate. 3.2.1 Path Coverage. To guarantee full logic coverage, we predefine all valid trajectories P based on the SOP graph. This involves a two-stage process consisting of initial intent-balanced sampling followed by targeted supplementation for under-covered paths. For rare branches, we use an inverse configuration mechanism to deterministically synthesize the required user intents and system states. This ensures every logical path, including edge cases, is tested frequently, establishing a robust reference standard for the subsequent evaluation. With testing comprehensiveness secured, we next detail the methodology for evaluating each trajectory.

3.2.2 Judge Agent. The Judge Agent is designed to handle the semantic understanding of natural language interactions. For each turn 𝑡, it analyzes the system information S, dialogue history ℎ <𝑡 , user message 𝑎𝑡 , and the service agent’s natural language response chat𝑡 (excluding internal reasoning steps). The judge outputs the classification ground truth F𝑡∗ (e.g., user’s emotion type and user’s goal) and a conversational quality score 𝑠 chat : (F𝑡∗, 𝑠 chat ) = JudgeAgent(S, ℎ <𝑡 , 𝑎𝑡 , chat𝑡 ).

(3)

To ensure robustness against individual model bias, we employ an ensemble of three Judge Agents. We apply majority voting to determine the consensus ground truth F𝑡∗ of classification fields, while the quality score 𝑠 chat is derived from the average rating. The classification ground truth F𝑡∗ serves as the input for the Rule Engine, while 𝑠 chat directly quantifies the conversational quality. 3.2.3 Rule Engine. The Rule Engine functions as a deterministic generator for procedural logic ground truth. It receives the consensus classification ground truth F𝑡∗ (derived from the Judge Agent), system information S, and the SOP graph 𝐺 as inputs. By performing a deterministic search on the graph, it calculates the unique, theoretically correct execution path and action: (𝑝𝑡∗, action𝑡∗ ) = RuleEngine(F𝑡∗, S, 𝐺).

(4)

Here, 𝑝𝑡∗ represents the reference path and action𝑡∗ denotes the reference action. These outputs serve as the rigid standard for evaluating the service agent’s logical reasoning capabilities, specifically its path planning and action selection accuracy. 3.2.4 Dual-Axis Evaluation Metrics. With the ground truth established, we conduct a dual-axis evaluation comparing the service agent’s output against these standards. This composite design facilitates the precise localization of model defects to specific granular dimensions. Logical Compliance Evaluation. We assess logical adherence across three dimensions, with weights 𝑤 1 = 0.4, 𝑤 2 = 0.4, 𝑤 3 = 0.2: (1) Classification Accuracy measures the alignment between the agent’s predicted field F𝑡 and the ground truth label determined by the Judge Agent. Specifically, it quantifies the agent’s proficiency in correctly identifying the state-specific attributes that trigger graph transitions. A high Logic score indicates the agent correctly identifies intent and follows the SOP graph. ∑︁ Acccls = |F | −1 I[F𝑡 (𝑓 ) = F𝑡∗ (𝑓 )]. (5) 𝑓 ∈F

(2) Path Correctness measures the overlap between the agent’s planned path and the Rule Engine’s reference path: Simpath =

|𝑝𝑡 ∩ 𝑝𝑡∗ | . |𝑝𝑡∗ |

(6)

(3) Action Correctness verifies if the agent’s final executed action matches the Rule Engine’s reference action: Accaction = I[action𝑡 = action𝑡∗ ].

(7)

Chat Quality Evaluation. This metric assesses the linguistic and interactive performance of the service agent. To ensure a multidimensional evaluation, the Judge Agents evaluate each response across five key dimensions: Linguistic Quality, Anthropomorphism,

SAGE: A Service Agent Graph-guided Evaluation Benchmark

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Content Utility, User Satisfaction, and Instruction Compliance. The final score for this metric is derived through a two-step aggregation: first, for each individual judge, a weighted sum is calculated based on these five dimensions to reflect their relative importance; second, the scores from the three independent Judge Agents are averaged to mitigate subjective bias and ensure the reliability of the evaluation.

Scorequality =

! 5 3 1 ∑︁ ∑︁ 𝑠 𝑗,𝑘 . 3 𝑗=1

(8)

𝑘=1

Overall Assessment Score. The final overall score for a turn integrates both axes: Scoreoverall = 0.8 × Scorelogic + 0.2 × Scorequality .

(9)

For multi-turn dialogues, we adopt a turn-level evaluation strategy (assessing turns 1, 5, 10, 15, and the final turn) to measure performance across different conversation depths. This weighted integration prioritizes procedural rigor while accounting for user experience, facilitating the precise diagnosis of model defects across specific dimensions. Beyond robust evaluation, SAGE is engineered for scalability. We next detail how its modular design supports rapid adaptation to arbitrary scenarios.

3.3

Scenario Extension Mechanism

Intent-based Adversarial Scenario Taxonomy. To guarantee a comprehensive simulation of realistic user behaviors, we establish a taxonomy based on two critical dimensions: goal alignment (the extent to which user demands match agent capabilities) and emotional state (the intensity of user aggression or urgency): Zeroadversarial Intents reflect cooperative interactions where user goals align with agent services (e.g., standard payment inquiries). Characterized by clear requests and friendly attitudes, these scenarios primarily test the agent’s basic procedural execution. Weakadversarial Intents introduce procedural friction or rational criticism. Here, users present complex constraints (e.g., unpaid bills) or ambiguous needs, requiring agents to resolve contextual conflicts without facing direct hostility. Strong-adversarial Intents represent high-stakes conflicts driven by emotional dissatisfaction or emergencies (e.g., safety hazards). Users employ aggressive strategies to demand immediate resolutions, rigorously testing the agent’s negotiation, de-escalation, and risk control capabilities. Extension Mechanism. We implement this taxonomy via prompt engineering, integrating user intent I and persona P into the User Agent to generate diverse, high-fidelity scenarios (details in Appendix B). Consequently, SAGE facilitates rapid scenario extension through a streamlined two-step process: formalizing the SOP graph and defining the user persona profile. This modular, “fill-in-theblank” approach decouples scenario configuration from the core evaluation engine, significantly lowering the technical barrier for deployment. Beyond evaluation, this high-scalability architecture can be further extended to automated dialogue data synthesis, enabling the large-scale generation of high-quality training corpora for customer service LLMs.

4 Experiments 4.1 LLM Configuration To ensure a comprehensive assessment of the current landscape, we select 27 representative Large Language Models (LLMs), categorized into closed-source and open-source families, covering a wide spectrum of parameter scales and architectures. Closed-Source Models. We evaluate state-of-the-art proprietary systems accessed via official APIs. This includes the Claude series (Sonnet-4.5, Opus-4.5), known for strong reasoning capabilities; the GPT series (GPT-4.1) [1], serving as a standard baseline; and the Gemini series (2.5-Pro, 3-Pro/Flash) [39], representing multimodal-native architectures. We also include leading Chinese proprietary models such as Qwen-Max [2] and the Doubao series, which are widely optimized for Chinese application scenarios. Open-Source Models. We cover models ranging from lightweight (3B) to massive scale (1T) to analyze the impact of model size. Our selection features the Qwen2.5 and Qwen3 families [2], which provide a granular range of sizes (3B to 235B); the DeepSeek series (V3, V3.2, R1) [23], representing advanced Mixture-of-Experts (MoE) architectures; and the Llama-3 series [11]. Additionally, we evaluate high-performing models from other providers, including GLM-4.7 [55], Kimi-K2.5 [40], and MiniMax-M2.1 [6]. All open-source models are deployed locally using vLLM [19] to ensure consistent inference efficiency, while closed-source models are evaluated using their respective stable API endpoints.

4.2

Scenario Configuration

To evaluate the generalization capability of service agents across diverse industrial domains, we constructed six distinct customer service scenarios (detailed in Appendix B.1.2). These scenarios range from standardized inquiries to complex, high-stakes disputes, covering varying levels of SOP complexity. • Ecommerce Refund (ER): The most complex scenario, featuring a deep decision tree based on product status and credit levels. Agents must navigate multi-branch logic and negotiate terms with varied user temperaments. • Logistics Delivery (LD): Centered on supply chain exceptions (e.g., lost or delayed parcels), requiring proficiency in status tracking and insurance claim processing. • Telecom Package (TP): A standardized scenario focusing on linear SOP execution for billing and plan upgrades, evaluating instruction-following and upselling protocols. • Property Service (PS): Emphasizes community coordination and emotional management (e.g., repair schedules or noise complaints) within offline service contexts. • Airline Refund (AR): A high-complexity scenario governed by rigid, time-sensitive policies. It tests the agent’s precision in calculating dynamic cancellation fees and de-escalating passenger anxiety. • Online Education (OE): Focuses on long-term contract disputes and rigorous risk control. Agents must identify potential malicious refunders and strictly adhere to intricate refund formulas. These scenarios collectively cover the spectrum from simple procedural execution to complex adversarial negotiation, ensuring a robust assessment of agentic capabilities.

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Ling Shi et al.

Table 1: Main results across 6 scenarios (0-100 Scale). OA: Overall Assessment Score; Logic: Logical Compliance Score; Chat: Conversational Quality Score. The superscripts indicate the ranking within Closed-Source and Open-Source groups, respectively. Format Error: Percentage of outputs failing JSON parsing. Chat Length: Average character count of the response field. Model Name

AVG Score Params

1T+ 230B -

71.562

3B 7B 14B 32B 72B 4B 8B 14B 32B 235B 671B 671B 671B 355B 1T 229B 8B 70B

56.1617

Logic

OA on 6 Scenarios Chat

Format

Chat

Error

Length

67.30 71.25 62.69 64.92 68.05 67.10 64.03 46.98 64.01

66.52 70.12 63.68 60.71 64.45 62.40 63.85 47.37 62.19

74.24 75.22 71.69 70.28 82.15 75.62 74.75 63.04 65.49

0.75 % 0.94 % 0.04 % 0.00 % 0.00 % 8.92 % 0.00 % 0.49 % 0.04 %

93.42 43.49 18.59 53.33 48.60 50.16 27.55 18.83 26.79

46.01 47.24 54.24 62.99 63.16 44.36 47.77 56.13 58.79 64.77 70.87 60.08 65.75 66.50 65.74 68.54 28.26 60.27

59.65 60.88 62.96 60.25 59.83 56.47 57.67 63.78 61.66 62.37 65.84 61.58 64.03 60.82 64.45 66.37 38.14 62.93

52.70 67.35 59.11 66.20 68.76 62.31 66.08 66.74 67.56 68.02 78.17 68.77 69.40 72.36 71.15 72.55 16.30 63.71

0.02 % 0.00 % 0.00 % 0.00 % 0.00 % 0.04 % 0.00 % 0.43 % 1.48 % 1.34 % 0.00 % 0.00 % 0.97 % 1.46 % 0.52 % 0.82 % 44.33 % 0.03 %

26.76 19.44 27.23 21.18 44.67 24.12 19.93 25.54 24.15 32.85 27.48 18.50 38.08 17.58 34.17 61.27 44.70 13.79

Closed-Source Large Language Models Claude-Sonnet-4.5 Claude-Opus-4.5 GPT-4.1 Gemini-2.5-Pro Gemini-3-Pro-Preview Gemini-3-Flash-Preview Qwen-Max Doubao-Seed-1.6-Flash Doubao-Seed-1.8

72.621 66.796 66.905 71.403 68.284 66.547 51.759 66.148

70.103 72.101 68.314 65.698 71.272 68.165 67.576 51.089 65.787

77.381 74.682 60.708 71.734 71.893 68.755 62.447 54.439 67.626

71.21 72.73 70.32 69.46 70.99 67.56 66.81 54.18 70.25

75.03 73.12 66.90 66.42 69.09 65.36 65.47 51.59 65.89

75.07 73.25 65.46 69.60 73.65 71.62 64.36 47.34 69.03

Open-Source Large Language Models Qwen2.5-3B-Instruct Qwen2.5-7B-Instruct Qwen2.5-14B-Instruct Qwen2.5-32B-Instruct Qwen2.5-72B-Instruct Qwen3-4B Qwen3-8B Qwen3-14B Qwen3-32B Qwen3-235B-A22B Deepseek-V3.2 Deepseek-V3 Deepseek-R1 GLM-4.7 Kimi-K2.5 MiniMax-M2.1 Llama-3.1-8B-Instruct Llama-3.3-70B-Instruct

4.3

61.2213 60.9014 65.347 65.278 57.8615 56.7116 63.8812 64.6910 64.729 71.291 66.546 68.393 67.255 68.712 68.334 37.6218 64.0211

55.1617 60.8013 60.6714 66.497 65.5111 58.5615 57.6516 65.5710 65.979 64.8712 72.081 67.905 70.002 68.684 69.163 66.596 37.3618 66.068

60.1512 62.866 61.808 60.7411 64.304 55.0516 52.9317 57.1114 59.5813 64.135 68.112 61.1110 61.947 61.529 66.933 75.291 38.6418 55.8515

Model Performance Across Scenarios

In addition to the primary metrics (Logical Compliance Score, Chat Quality Score and Overall Assessment Score), we report two auxiliary indicators to provide a more nuanced analysis of model behavior: Format Error Rate and Average Chat Length. The former quantifies the frequency of JSON parsing failures to reflect the model’s instruction-following stability, while the latter measures response verbosity to identify potential issues with redundant generation or lack of conciseness. We evaluated 27 mainstream Large Language Models (LLMs), covering both closed-source (e.g., GPT-4, Claude-3.5) and open-source (e.g., Qwen2.5, Llama-3) families. Table 1 presents the comprehensive performance across six diverse customer service scenarios. Superiority of Closed-Source Models and the Rising OpenSource Challengers. Closed-source models continue to define the performance frontier, with Claude-Opus-4.5 securing the highest

68.92 69.05 67.64 72.07 64.90 64.71 51.88 63.79 67.94 66.73 71.51 69.62 70.16 68.14 69.69 68.33 49.58 68.60

55.16 62.58 63.33 68.27 69.16 62.72 62.80 68.01 65.48 64.97 70.61 71.60 70.39 66.02 69.41 70.12 55.83 64.74

54.53 60.19 58.12 62.26 65.78 56.57 54.03 64.81 66.71 61.47 70.71 67.57 70.58 69.64 71.84 64.07 37.58 63.87

Overall Assessment (OA) score (72.621 ), underpinned by its toptier logical reasoning (72.101 ) and impressive chat quality score (74.682 ). However, the performance gap between proprietary and open-weight models is remarkably narrow. DeepSeek-V3.2 (671B) emerges as a formidable competitor, achieving an OA of 71.291 among open-source models—surpassing established closed-source giants like GPT-4.1 and Gemini-3-Pro-Preview. This indicates that state-of-the-art open-source architectures have reached a level of maturity capable of handling complex, graph-guided service logic previously reserved for proprietary systems. Decoupling Logical Compliance and Conversational Quality. Our results reveal a nuanced trade-off between procedural rigor and linguistic flair. While Claude-Opus-4.5 leads in logic, its sibling Claude-Sonnet-4.5 dominates the Chat Quality category (77.381 ), suggesting a more empathetic persona. A notable outlier is MiniMax-M2.1, which, despite a moderate Logic score (66.596 ),

Figure 3: Logic performance gap analysis across six scenarios.

63 62

36 35

33.3

32.9

62 1

Turn

0.6

Score

0.8

0.6 0.4

Cross-Scenario Difficulty Analysis

SAGE provides a standardized framework to quantify scenario complexity. As illustrated in Figure 3, we analyze three subdimension of logic performance across six domains. We define scenario difficulty by the “Execution Gap”—the disparity between the nested bars, which reveal two distinct failure modes in LLM reasoning. First, in high-complexity scenarios such as ER, AR, LD, and OE, we observe a significant gap between Classification_Acc (Light Gray) and Action_Acc (Dark Blue). This disparity highlights a Logic Deduction Barrier: even when models correctly identify the classification fields (F𝑡 ), they frequently fail to derive the correct subsequent action. This suggests that for complex SOPs, correct semantic classification does not naturally guarantee successful procedural execution due to intricate conditional dependencies. Second, in more standardized scenarios like PS and TP, an interesting phenomenon occurs where Path_Acc (Light Blue) exceeds

0.0 Weak

Strong

Zero

Chat Quality 1.0

Turn

0.08

0.4

Turn

0.06 0.04 0.02

0.0

Strong

0.10

0.6

0.2

Weak

JSON Error Rate

0.12

0.8

0.4 0.2

0.0 Zero

Figure 4: Performance evolution across dialogue turns in six scenarios.

achieves a stellar Chat score (75.291 ), the highest among opensource models. This suggests that certain models are specifically optimized for human-like interaction, which can occasionally compensate for minor procedural deviations in terms of overall user perception. In contrast, DeepSeek-R1 and GPT-4.1 lean heavily toward logic-first strategies, often at the expense of conversational warmth. The Dynamics of Response Verbosity and Stability. We observe that response length is a significant indicator of service quality, but only up to a threshold. Top-tier performers like ClaudeSonnet-4.5 (93.42 chars) and MiniMax-M2.1 (61.27 chars) tend to provide more elaborate guidance and empathetic de-escalation, which are crucial in high-complexity scenarios like ER and AR. Conversely, the failure of smaller models is often catastrophic rather than gradual; for instance, Llama-3.1-8B suffers from an extreme Format Error rate (44.33%), failing even the basic instructionfollowing required to output a valid JSON. Interestingly, Gemini-3Flash-Preview maintains a competitive OA despite a higher-thanaverage error rate (8.92%), indicating that when it does follow the format, its reasoning is remarkably efficient.

4.4

0.8

Score

1.0

0.2

Score

Score AR

66 65

68 67

Logic Ability

1.0

0.0

Overall Score

Chat Length

0.2

0.4

0.6

Chat Score

Score

0.8

Logic Score

OA Score

Classification Acc Path Acc Action Acc

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Score

1.0

Score

SAGE: A Service Agent Graph-guided Evaluation Benchmark

Zero

Weak

Strong

0.00

Adversarial Intensity

Zero

Weak

Strong

Adversarial Intensity

Figure 5: Performance distribution across 3-level Adversarial intensities.

Classification_Acc (Light Gray). This stems from the metric’s definition: Path Accuracy is calculated as the intersection length of the predicted and ground-truth paths divided by the total ground-truth length. Because this metric accounts for the successful traversal of early, simpler steps, models can achieve relatively high path scores by following partial correct fields, even if they stumble on specific complex classifications. This confirms that Path_Acc serves as a more lenient dimension, whereas the gap between classification and action acts as a more rigorous stress test for deep procedural reasoning.

4.5

Multi-turn Robustness Analysis

To evaluate model stability over extended interactions, we analyze performance variations across different dialogue depths (Turn 1, 5, 10, 15). Figure 4 illustrates the evolution of OA, Logic, and Chat scores across six scenarios. A distinct performance trend “InvertedU” Trajectory is observed across most scenarios (e.g., AR, ER, PS, TP): scores typically peak at Turn 5 and decline significantly by Turn 15. This phenomenon can be attributed to two phases. (1) Information Gain Phase (Turn 1 → 5): Performance generally improves from the first turn to the fifth (e.g., ER OA rises from ∼67 to ∼68). In the initial turn (Cold Start), agents lack sufficient context. By Turn 5, through multi-turn interaction, agents gather critical user information (e.g., order IDs, specific complaints), enabling more accurate intent classification and SOP navigation. (2) Context Fatigue Phase (Turn 10 → 15): As the dialogue extends beyond Turn 10, performance exhibits a marked decline (e.g., PS OA drops from ∼63 to ∼57). This degradation highlights the limitations of current LLMs in handling long-context dependencies. The accumulation of historical information introduces noise, leading to the “Lost in the Middle” phenomenon where models hallucinate or lose track of the current state within the SOP graph.

4.6

Impact of Adversarial Intensity

To validate the effectiveness of our Adversarial Scenario Taxonomy, we analyze model performance across three intensity levels:

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Ling Shi et al.

Sub-dimension Score (0-10)

6 Sub-dimensions(CI=90%) Linguistic Quality (R²=0.917) Anthropomorphism (R²=0.955) Content Utility (R²=0.970) User Satisfaction (R²=0.963) Instruction Compliance (R²=0.905)

Chat Quality Score (0-100)

Figure 6: Correlation analysis between the Chat Quality Score and its five sub-dimensions. The deviations from the regression lines (e.g., Doubao-Seed-1.8’s high Linguistic vs. low Instruction scores) highlight specific model characteristics. Zero-, Weak-, and Strong-Adversarial. Figure 5 presents the distribution of four key metrics—Overall Score (OA), Logic Score, Chat Quality, and Format Error Rate—via box plots. Logic Degradation and Error Escalation. As adversarial intensity increases, we observe a consistent decline in Logical Compliance (Logic Score). This trend confirms that adversarial user behaviors (e.g., concealing information, emotional aggression) successfully introduce logical friction, making it harder for agents to adhere to SOPs. Concurrently, the Format Error Rate rises significantly in Strong-Adversarial scenarios. This suggests that under high cognitive load or emotional pressure, models are more prone to instruction drift, failing to maintain the structured JSON output format required by the system. The Stability in Chat Quality. The distribution of Chat Quality scores remains stable across varying adversarial intensities. This “Empathy Resilience” reveals a decoupling between dialogue and logic: models maintain polite, de-escalating facades even when increased user aggression impairs their logical compliance. Such consistency underscores the need for dual-axis evaluation to distinguish surface fluency from procedural robustness. Increased Discriminative Power. Crucially, the score distribution becomes significantly more dispersed (larger interquartile range and more outliers) as intensity increases. In Zero-Adversarial settings, most models perform comparably well. However, StrongAdversarial scenarios widen the gap between top-tier and lower-tier models. This proves that high-intensity scenarios serve as a more effective filter for distinguishing robust agentic capabilities.

4.7

Correlation Analysis of Sub-Metrics

To validate the internal consistency of our evaluation framework and diagnose fine-grained model capabilities, we analyze the correlation between the aggregated Chat Quality Score (X-axis, scaled to 0-1) and its five constituent Sub-dimension Scores (Y-axis, scaled 0-10). As illustrated in Figure 6, the regression analysis yields several key insights. High Metric Consistency. We observe an extremely strong linear correlation across all five dimensions—Linguistic Quality,

Anthropomorphism, Content Utility, User Satisfaction, and Instruction Compliance—with coefficient of determination (𝑅 2 ) values consistently exceeding 0.9. This statistical coherence confirms the validity of our metric design. In complex multi-agent evaluation, a high 𝑅 2 indicates that each dimension provides a consistent and reliable contribution to the aggregated Chat Quality Score. If a specific dimension (e.g., User Satisfaction) exhibited a non-linear correlation—such as an S-shaped curve—or significant noise, it would suggest potential flaws in the scoring rubrics or latent hallucinations and inconsistencies in the LLM-as-judge. The absence of such anomalies in our results confirms that the SAGE evaluation framework effectively encapsulates the multi-faceted nature of conversational ability, maintaining high interpretability and minimal bias across all predefined dimensions. Capability Profiling via Variance. While the general trend is linear, the vertical variance (residuals) from the regression lines serves as a fingerprint for specific model strengths and weaknesses. A point significantly deviating from the mean regression line indicates that a model’s capability in that specific dimension is disproportionate to its overall performance. Points located significantly above the green regression line (Linguistic Quality) represent models with exceptional fluency and expression. Specifically, DoubaoSeed-1.8 and DeepSeek-R1 exhibit positive residuals in this dimension, indicating that their linguistic generation capabilities are superior to the average level expected for their score range. Points falling below the purple regression line (Instruction Compliance) reveal deficits in following specific constraints. Notably, despite reasonable overall scores, Doubao-Seed-1.8 and Qwen3-8B appear significantly below the trend line for Instruction Compliance. This suggests a capability imbalance: these models are highly articulate (high Linguistic score) but prone to ignoring specific formatting or constraint instructions (low Instruction score). This granular analysis proves that SAGE can diagnose subtle trade-offs in model alignment, distinguishing between models that are merely chatty and those that are strictly compliant.

Conclusion

In this paper, we addressed the limitations of existing customer service benchmarks—specifically their single-dimensional metrics, static interactions, and limited scalability—by proposing SAGE, a graph-guided multi-agent evaluation benchmark. By formalizing Standard Operating Procedures (SOPs) into dynamic graph structures and incorporating adversarial user simulation with a dual-axis evaluation mechanism, SAGE achieves a comprehensive assessment of service agents in complex business logic and multi-turn interactions. Our extensive experiments not only validated SAGE’s effectiveness in distinguishing model capabilities but also revealed critical insights, such as the “Inverted-U” performance degradation in long contexts and logical fragility under high adversarial intensity. Furthermore, SAGE’s modular design ensures rapid extensibility to diverse vertical domains via simple configuration. We envision SAGE as a standardized metric tool to drive the evolution of intelligent customer service from simple chatbots to expert-level agents. Future work will explore more complex graph structures (e.g., nested subgraphs) and multimodal interaction scenarios.

SAGE: A Service Agent Graph-guided Evaluation Benchmark

References [1] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. 2023. Gpt-4 technical report. arXiv preprint arXiv:2303.08774 (2023). [2] Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, et al. 2023. Qwen technical report. arXiv preprint arXiv:2309.16609 (2023). [3] Nolwenn Bernard and Krisztian Balog. 2023. MG-ShopDial: A multi-goal conversational dataset for E-commerce. In Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2775– 2785. [4] Alessandro Berti, Humam Kourani, and Wil MP van der Aalst. 2024. PM-LLMBenchmark: Evaluating large language models on process mining tasks. In International Conference on Process Mining. Springer, 610–623. [5] Paweł Budzianowski, Tsung-Hsien Wen, Bo-Hsiang Tseng, Iñigo Casanueva, Stefan Ultes, Osman Ramadan, and Milica Gašić. 2018. Multiwoz–a large-scale multi-domain wizard-of-oz dataset for task-oriented dialogue modelling. arXiv preprint arXiv:1810.00278 (2018). [6] Aili Chen, Aonian Li, Bangwei Gong, Binyang Jiang, Bo Fei, Bo Yang, Boji Shan, Changqing Yu, Chao Wang, Cheng Zhu, et al. 2025. MiniMax-M1: Scaling Test-Time Compute Efficiently with Lightning Attention. arXiv preprint arXiv:2506.13585 (2025). [7] Lei Cui, Shaohan Huang, Furu Wei, Chuanqi Tan, Chaoqun Duan, and Ming Zhou. 2017. Superagent: A customer service chatbot for e-commerce websites. In Proceedings of ACL 2017, system demonstrations. 97–102. [8] Lingxiao Diao, Xinyue Xu, Wanxuan Sun, Cheng Yang, and Zhuosheng Zhang. 2025. GuideBench: Benchmarking Domain-Oriented Guideline Following for LLM Agents. arXiv preprint arXiv:2505.11368 (2025). [9] Alexandre Drouin, Maxime Gasse, Massimo Caccia, Issam H Laradji, Manuel Del Verme, Tom Marty, Léo Boisvert, Megh Thakkar, Quentin Cappart, David Vazquez, et al. 2024. Workarena: How capable are web agents at solving common knowledge work tasks? arXiv preprint arXiv:2403.07718 (2024). [10] Dheeru Dua, Yizhong Wang, Pradeep Dasigi, Gabriel Stanovsky, Sameer Singh, and Matt Gardner. 2019. DROP: A reading comprehension benchmark requiring discrete reasoning over paragraphs. arXiv preprint arXiv:1903.00161 (2019). [11] Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. 2024. The llama 3 herd of models. arXiv e-prints (2024), arXiv–2407. [12] Dirk Fahland, Fabiana Fournier, Lior Limonad, Inna Skarbovsky, and Ava JE Swevels. 2024. How well can large language models explain business processes? arXiv preprint arXiv:2401.12846 (2024). [13] Fabiana Fournier, Lior Limonad, and Inna Skarbovsky. 2024. Towards a Benchmark for Causal Business Process Reasoning with LLMs. In International Conference on Business Process Management. Springer, 233–246. [14] Michael Grohs, Luka Abb, Nourhan Elsayed, and Jana-Rebecca Rehse. 2023. Large language models can accomplish business process management tasks. In International conference on business process management. Springer, 453–465. [15] Yun He, Di Jin, Chaoqi Wang, Chloe Bi, Karishma Mandyam, Hejia Zhang, Chen Zhu, Ning Li, Tengyu Xu, Hongjiang Lv, et al. 2024. Multi-if: Benchmarking llms on multi-turn and multilingual instructions following. arXiv preprint arXiv:2410.15553 (2024). [16] Yuxin Jiang, Yufei Wang, Xingshan Zeng, Wanjun Zhong, Liangyou Li, Fei Mi, Lifeng Shang, Xin Jiang, Qun Liu, and Wei Wang. 2024. Followbench: A multilevel fine-grained constraints following benchmark for large language models. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 4667–4688. [17] Humam Kourani, Alessandro Berti, Jasmin Hennrich, Wolfgang Kratsch, Robin Weidlich, Chiao-Yun Li, Ahmad Arslan, Wil MP van der Aalst, and Daniel Schuster. 2025. Leveraging large language models for enhanced process model comprehension. Decision Support Systems (2025), 114563. [18] Humam Kourani, Alessandro Berti, Daniel Schuster, and Wil MP van der Aalst. 2025. Evaluating large language models on business process modeling: framework, benchmark, and self-improvement analysis: H. Kourani et al. Software and Systems Modeling (2025), 1–36. [19] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. 2023. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th symposium on operating systems principles. 611–626. [20] Minghao Li, Yingxiu Zhao, Bowen Yu, Feifan Song, Hangyu Li, Haiyang Yu, Zhoujun Li, Fei Huang, and Yongbin Li. 2023. Api-bank: A comprehensive benchmark for tool-augmented llms. arXiv preprint arXiv:2304.08244 (2023). [21] Xiangci Li, Zhiyu Chen, Jason Ingyu Choi, Nikhita Vedula, Besnik Fetahu, Oleg Rokhlenko, and Shervin Malmasi. 2025. Wizard of shopping: Target-oriented e-commerce dialogue generation with decision tree branching. arXiv preprint arXiv:2502.00969 (2025).

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

[22] Zekun Li, Shinda Huang, Jiangtian Wang, Nathan Zhang, Antonis Antoniades, Wenyue Hua, Kaijie Zhu, Sirui Zeng, Chi Wang, William Yang Wang, et al. 2025. Sopbench: Evaluating language agents at following standard operating procedures and constraints. arXiv preprint arXiv:2503.08669 (2025). [23] Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, et al. 2024. Deepseek-v3 technical report. arXiv preprint arXiv:2412.19437 (2024). [24] Jian Liu, Leyang Cui, Hanmeng Liu, Dandan Huang, Yile Wang, and Yue Zhang. 2020. Logiqa: A challenge dataset for machine reading comprehension with logical reasoning. arXiv preprint arXiv:2007.08124 (2020). [25] Xiao Liu, Hao Yu, Hanchen Zhang, Yifan Xu, Xuanyu Lei, Hanyu Lai, Yu Gu, Hangliang Ding, Kaiwen Men, Kejuan Yang, et al. 2023. Agentbench: Evaluating llms as agents. arXiv preprint arXiv:2308.03688 (2023). [26] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. 2023. Self-refine: Iterative refinement with self-feedback. Advances in Neural Information Processing Systems 36 (2023), 46534–46594. [27] Subhrangshu Nandi, Arghya Datta, Nikhil Vichare, Indranil Bhattacharya, Huzefa Raja, Jing Xu, Shayan Ray, Giuseppe Carenini, Abhi Srivastava, Aaron Chan, et al. 2025. SOP-Bench: Complex Industrial SOPs for Evaluating LLM Agents. arXiv preprint arXiv:2506.08119 (2025). [28] Jiao Ou, Junda Lu, Che Liu, Yihong Tang, Fuzheng Zhang, Di Zhang, and Kun Gai. 2024. Dialogbench: Evaluating llms as human-like dialogue systems. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 6137–6170. [29] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022. Training language models to follow instructions with human feedback. Advances in neural information processing systems 35 (2022), 27730–27744. [30] Feng Peiyuan, Yichen He, Guanhua Huang, Yuan Lin, Hanchong Zhang, Yuchen Zhang, and Hang Li. 2024. Agile: A novel reinforcement learning framework of llm agents. Advances in Neural Information Processing Systems 37 (2024), 5244–5284. [31] Yujia Qin, Shihao Liang, Yining Ye, Kunlun Zhu, Lan Yan, Yaxi Lu, Yankai Lin, Xin Cong, Xiangru Tang, Bill Qian, et al. 2023. Toolllm: Facilitating large language models to master 16000+ real-world apis. arXiv preprint arXiv:2307.16789 (2023). [32] Yiwei Qin, Kaiqiang Song, Yebowen Hu, Wenlin Yao, Sangwoo Cho, Xiaoyang Wang, Xuansheng Wu, Fei Liu, Pengfei Liu, and Dong Yu. 2024. Infobench: Evaluating instruction following ability in large language models. arXiv preprint arXiv:2401.03601 (2024). [33] Jun Quan, Shian Zhang, Qian Cao, Zizhong Li, and Deyi Xiong. 2020. RiSAWOZ: A large-scale multi-domain Wizard-of-Oz dataset with rich semantic annotations for task-oriented dialogue modeling. arXiv preprint arXiv:2010.08738 (2020). [34] Abhinav Rastogi, Xiaoxue Zang, Srinivas Sunkara, Raghav Gupta, and Pranav Khaitan. 2020. Towards scalable multi-domain conversational agents: The schemaguided dialogue dataset. In Proceedings of the AAAI conference on artificial intelligence, Vol. 34. 8689–8696. [35] Adrian Rebmann, Fabian David Schmidt, Goran Glavaš, and Han van Der Aa. 2024. Evaluating the ability of llms to solve semantics-aware process mining tasks. In 2024 6th International Conference on Process Mining (ICPM). IEEE, 9–16. [36] Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. 2023. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems 36 (2023), 8634–8652. [37] Yuchong Sun, Che Liu, Kun Zhou, Jinwen Huang, Ruihua Song, Wayne Xin Zhao, Fuzheng Zhang, Di Zhang, and Kun Gai. 2024. Parrot: Enhancing multi-turn instruction following for large language models. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 9729–9750. [38] Xiangru Tang, Yiming Zong, Jason Phang, Yilun Zhao, Wangchunshu Zhou, Arman Cohan, and Mark Gerstein. 2024. STRUC-BENCH: Are Large Language Models Good at Generating Complex Structured Tabular Data?. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 2: Short Papers). 12–34. [39] Gemini Team, Rohan Anil, Sebastian Borgeaud, Jean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, Katie Millican, et al. 2023. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11805 (2023). [40] Kimi Team, Yifan Bai, Yiping Bao, Guanduo Chen, Jiahao Chen, Ningxin Chen, Ruijue Chen, Yanru Chen, Yuankun Chen, Yutian Chen, et al. 2025. Kimi k2: Open agentic intelligence. arXiv preprint arXiv:2507.20534 (2025). [41] Vicuna Team. 2023. Vicuna: An open-source chatbot impressing gpt-4 with 90% chatgpt quality. Vicuna: An open-source chatbot impressing gpt-4 with 90 (2023). [42] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288 (2023).

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

[43] Haoxin Wang, Xianhan Peng, Huang Cheng, Yizhe Huang, Ming Gong, Chenghan Yang, Yang Liu, and Jiang Lin. 2025. ECom-Bench: Can LLM Agent Resolve Real-World E-commerce Customer Support Issues?. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing: Industry Track. 276–284. [44] Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, et al. 2024. A survey on large language model based autonomous agents. Frontiers of Computer Science 18, 6 (2024), 186345. [45] Yizhong Wang, Yeganeh Kordi, Swaroop Mishra, Alisa Liu, Noah A Smith, Daniel Khashabi, and Hannaneh Hajishirzi. 2023. Self-instruct: Aligning language models with self-generated instructions. In Proceedings of the 61st annual meeting of the association for computational linguistics (volume 1: long papers). 13484–13508. [46] Walter F Wiggins and Ali S Tejani. 2022. On the opportunities and risks of foundation models for natural language processing in radiology. Radiology: Artificial Intelligence 4, 4 (2022), e220119. [47] Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, et al. 2025. The rise and potential of large language model based agents: A survey. arXiv 2023. arXiv preprint arXiv:2309.07864 10 (2025). [48] Congying Xia, Chen Xing, Jiangshu Du, Xinyi Yang, Yihao Feng, Ran Xu, Wenpeng Yin, and Caiming Xiong. 2024. FOFO: A Benchmark to Evaluate LLMs’ Format-Following Capability. arXiv preprint arXiv:2402.18667 (2024). [49] Qianqian Xie, Weiguang Han, Zhengyu Chen, Ruoyu Xiang, Xiao Zhang, Yueru He, Mengxi Xiao, Dong Li, Yongfu Dai, Duanyu Feng, et al. 2024. Finben: A holistic financial benchmark for large language models. Advances in Neural Information Processing Systems 37 (2024). [50] Qianqian Xie, Weiguang Han, Xiao Zhang, Yanzhao Lai, Min Peng, Alejandro Lopez-Lira, and Jimin Huang. 2023. Pixiu: A large language model, instruction data and evaluation benchmark for finance. arXiv preprint arXiv:2306.05443 (2023). [51] Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D Manning. 2018. HotpotQA: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 conference on empirical methods in natural language processing. 2369–2380. [52] Shunyu Yao, Howard Chen, Austin W Hanjie, Runzhe Yang, and Karthik Narasimhan. 2023. Collie: Systematic construction of constrained text generation tasks. arXiv preprint arXiv:2307.08689 (2023). [53] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. 2022. React: Synergizing reasoning and acting in language models. In The eleventh international conference on learning representations. [54] Aohan Zeng, Mingdao Liu, Rui Lu, Bowen Wang, Xiao Liu, Yuxiao Dong, and Jie Tang. 2024. Agenttuning: Enabling generalized agent abilities for llms. In Findings of the Association for Computational Linguistics: ACL 2024. 3053–3077. [55] Aohan Zeng, Xiao Liu, Zhengxiao Du, Zihan Wang, Hanyu Lai, Ming Ding, Zhuoyi Yang, Yifan Xu, Wendi Zheng, Xiao Xia, et al. 2022. Glm-130b: An open bilingual pre-trained model. arXiv preprint arXiv:2210.02414 (2022). [56] Junjie Zhang, Ruobing Xie, Yupeng Hou, Xin Zhao, Leyu Lin, and Ji-Rong Wen. 2025. Recommendation as instruction following: A large language model empowered recommendation approach. ACM Transactions on Information Systems 43, 5 (2025), 1–37. [57] Wenqi Zhang, Ke Tang, Hai Wu, Mengna Wang, Yongliang Shen, Guiyang Hou, Zeqi Tan, Peng Li, Yueting Zhuang, and Weiming Lu. 2024. Agent-pro: Learning to evolve via policy-level reflection and optimization. arXiv preprint arXiv:2402.17574 (2024). [58] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Tianle Li, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zhuohan Li, Zi Lin, Eric P Xing, et al. 2023. Lmsyschat-1m: A large-scale real-world llm conversation dataset. arXiv preprint arXiv:2309.11998 (2023). [59] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, et al. 2023. Judging llm-as-a-judge with mt-bench and chatbot arena. Advances in neural information processing systems 36 (2023), 46595–46623. [60] Jeffrey Zhou, Tianjian Lu, Swaroop Mishra, Siddhartha Brahma, Sujoy Basu, Yi Luan, Denny Zhou, and Le Hou. 2023. Instruction-following evaluation for large language models. arXiv preprint arXiv:2311.07911 (2023). [61] Shuyan Zhou, Frank F Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, et al. 2023. Webarena: A realistic web environment for building autonomous agents. arXiv preprint arXiv:2307.13854 (2023). [62] Jie Zhu, Huaixia Dou, Junhui Li, Lifan Guo, Feng Chen, Chi Zhang, and Fang Kong. 2025. Evaluating, Synthesizing, and Enhancing for Customer Support Conversation. arXiv preprint arXiv:2508.04423 (2025).

Ling Shi et al.

Experiment Results Supplementary

This appendix provides supplementary data substantiating our main findings. We first validate our multi-agent ensemble via a SingleJudge Bias ablation study. Next, we present granular turn-level analysis to detail multi-turn robustness, followed by a breakdown of performance shifts under varying adversarial intensities. Finally, we decompose Logic and Chat scores into sub-metrics, quantifying the “Execution Gap” and capability imbalances.

A.1

Impact of Single-Judge Bias

To validate the robustness of our evaluation mechanism, we conducted an ablation study to investigate the bias inherent in using a single Large Language Model (LLM) as a judge. Specifically, we selected a subset of models (from the Qwen2.5 and Qwen3 families) to act as both "Service Agents" and "Judge Agents" in a round-robin evaluation setup. The results are visualized in three heatmaps: Overall Average Score (Figure 7), Chat Quality (Figure 8), and Logic Ability (Figure 9). In these plots, the Y-axis represents the Judge Model and the X-axis represents the Evaluated Agent. This experiment reveals two critical limitations of single-judge frameworks: 1. Egocentric Bias (Self-Preference). A distinct "diagonal dominance" is observable, particularly in Figure 8 (Chat Quality). Models tend to assign higher scores to their own outputs (or outputs from the same model family) compared to external evaluators. For instance, the diagonal cells in Figure 8 often exhibit deeper colors than the off-diagonal cells in the same column, indicating that a model favors response styles similar to its own training distribution. 2. Systematic Scoring Bias. Significant horizontal variations exist across all three heatmaps, especially in Figure 9 (Logic Ability). This indicates that different judges possess different strictness standards. Some judges (represented by rows with consistently lighter colors) act as "strict graders," systematically assigning lower scores across all agents, while others (darker rows) are more "lenient." For example, Qwen3-8B as a judge might exhibit a different scoring distribution compared to Qwen2.5-32B. Justification for Multi-Agent Ensemble. These findings demonstrate that relying on a single judge introduces significant variance and bias, where the evaluation outcome is heavily contingent on the specific evaluator’s preferences rather than the intrinsic quality of the service agent. To mitigate this, SAGE employs an Ensemble of Three Judge Agents (using majority voting for classification and average scoring for quality). This collaborative approach effectively smooths out individual model biases, cancels out extreme scoring tendencies, and ensures a more objective and robust evaluation standard, as reflected in our main experimental results.

A.2

Supplementary Analysis of Turn

This chapter supplements the content of Section 4.5. Table 2 provides a granular view of model performance evolution across dialogue turns (T1, T5, T10, T15). Consistent with the “Inverted-U” trajectory discussed in the main text, most scenarios (e.g., AirlineRefund, PropertyService) exhibit a performance peak around Turn 5, followed by a decline at Turn 15.

SAGE: A Service Agent Graph-guided Evaluation Benchmark

Chat Quality

qwen3-14B

qwen3-32B

qwen3-8B

qwen3-14B

qwen3-32B

Figure 7: Overall Average Score (OA) Heatmap. Rows represent Judge models, columns represent Agent models.

70 60

qwen2.5-32B

qwen3-8B

qwen3-14B

qwen3-32B

Supplementary Analysis of Adversarial Intensity

Supplementary Analysis of Correlation Analysis of Sub-Metrics

This chapter supplements the content of Section 4.7. Table 4 breaks down the Logic and Chat scores into their constituent sub-dimensions. • The Execution Gap: A significant disparity exists between Classification Accuracy (Avg: 72.9) and Action Correctness

90 80 70 60 50

-32 en 3

-14

-8B

en 3 qw

B qw

Figure 8: Chat Quality Heatmap. Darker diagonals indicate self-preference bias.

This chapter supplements the content of Section 4.5. Table 3 details the impact of adversarial intensity on model performance. • Logic Degradation: As expected, Logic Scores generally decrease as intensity rises from Zero to Strong (e.g., LogisticsDelivery: 84.0 to 54.5), confirming that adversarial user behaviors successfully challenge the agent’s reasoning capabilities. • Format Error Escalation: The JSON Error rate consistently increases with intensity (Average: 1.2% to 3.7%), indicating that high-pressure scenarios induce “instruction drift,” causing models to violate output formatting constraints. • Scenario Specifics: In some scenarios like AirlineRefund, performance actually improves from Zero to Weak, likely because the “Zero” setting involves trivial queries that some powerful models might over-complicate, whereas “Weak” scenarios provide clearer task structures.

A.4

Agent Model

• Context Accumulation (T1 to T5): The initial improvement in Logic Score (e.g., TelecomPackage: 68.0 to 68.5) indicates that models effectively gather user information in early turns to clarify intent. • Context Fatigue (T10 to T15): The subsequent drop (e.g., PropertyService Logic: 58.6 to 55.5) highlights the difficulty of maintaining logical consistency over long contexts. • Chat Stability: Interestingly, Chat Scores often remain stable or decline less than Logic Scores (e.g., EcommerceRefund Chat: 66.5 to 66.2), suggesting that models maintain linguistic fluency even when their procedural reasoning falters.

A.3

en 3

B 14

.5en 2

.5-

en 2

Agent Model

-32 en 3

-14

-8B

en 3 qw

B qw

en 3

32 .5-

en 2 qw

.5en 2

en 2

.5-

100

-32

qwen2.5-32B

qwen2.5-14B

en 3

qwen3-8B

-8B

-14

en 3

Score

qwen2.5-7B

en 3

qwen2.5-14B

100

qwen2.5-32B

.5-

en 2

Logic Ability

Score

qwen2.5-7B

qwen2.5-14B

100

.5-

en 2

Judge Model

Score

qwen2.5-7B

Judge Model

Overall

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Agent Model

Figure 9: Logic Ability Heatmap. Horizontal variances indicate differing judge strictness.

(Avg: 41.7). This gap is most pronounced in EcommerceRefund (88.0 vs. 29.5), proving that while models are adept at understanding intent, they struggle to execute the correct sequence of actions in complex SOPs. • Chat Quality Imbalance: Within Chat Quality, Linguistic Quality (Avg: 69.7) and Instruction Compliance (Avg: 71.8) are high, whereas Anthropomorphism (Avg: 57.3) is notably lower. This suggests that current LLMs are polite and compliant but lack the “human touch” or empathy required for high-quality customer service.

B Scenario Extending B.1 Scenario Configuration Template Our benchmark includes six customer service scenarios. Each scenario follows a unified configuration structure: B.1.1 General Structure. Each scenario configuration contains the following components: • Scenario Metadata: – scenario_id: Unique identifier for the scenario – scenario_name: Human-readable name – description: Brief description of the scenario • Classification Fields: Task-specific fields that the agent must classify based on dialogue context and system information. Each field has: – field_name: Name of the classification field – data_type: Data type (boolean, string, enum, etc.) – options: List of valid values – description: Detailed description of the field • System Variables: Backend information available to the agent (e.g., user credit level, package status, order status) • Actions: Possible actions the agent can take. Each action has: – action_name: Name of the action – description: What the action does • SOP (Standard Operating Procedure): A decision tree that defines: – Stage sequence (e.g., stage1, stage2, ...)

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Ling Shi et al.

Table 2: Turn-by-Turn Performance Analysis by Scenario. (0-100 Scale). OA Score

Logic Score

Chat Score

Chat Length

Scenario

T10

T15

T10

T15

T10

T15

T10

T15

AirlineRefund EcommerceRefund LogisticsDelivery OnlineEducation PropertyService TelecomPackage

61.1 66.9 59.5 67.0 64.1 65.9

61.9 67.9 60.5 69.4 64.7 66.4

59.8 68.1 60.7 71.5 59.8 64.1

57.2 66.5 60.8 73.1 56.9 62.1

60.7 67.5 58.9 67.5 63.9 68.0

61.4 68.5 59.9 69.9 64.6 68.5

58.7 68.5 60.0 72.6 58.6 65.0

55.7 66.6 60.7 75.0 55.5 62.9

63.1 64.6 62.0 65.1 64.6 57.8

64.1 65.5 63.1 67.3 65.4 58.3

64.3 66.5 63.3 67.3 64.4 60.3

63.2 66.2 61.4 65.5 62.8 58.9

37 37 40 35 30 33

36 34 39 35 30 33

35 38 40 34 32 33

34 36 45 36 35 33

Table 3: Adversarial Intensity Analysis: Average Performance Across All Models (0-100 Scale).

Zero

Overall Weak Strong

Zero

Logic Weak Strong

Chat Quality Zero Weak Strong

JSON Error (%) Zero Weak Strong

AirlineRefund E-commerceRefund LogisticsDelivery OnlineEducation PropertyService TelecomPackage

49.7 73.1 78.2 75.7 65.1 66.2

63.2 68.8 59.9 74.4 61.4 69.5

60.9 58.9 56.4 62.6 67.0 54.8

46.3 74.8 84.0 78.1 64.4 67.7

63.2 69.7 59.5 76.7 60.3 72.6

60.3 58.1 54.5 62.0 68.8 55.2

63.3 66.2 55.2 66.1 67.9 60.1

63.0 65.2 61.6 65.1 65.9 57.1

63.4 62.0 63.6 64.9 60.0 53.3

1.6 1.0 0.6 2.3 0.9 1.0

1.8 1.5 2.0 2.9 1.0 1.6

3.4 3.9 3.8 4.5 3.1 3.1

Average

68.0

66.2

60.1

69.2

67.0

59.8

63.1

63.0

61.2

1.2

1.8

3.7

Scenario

Table 4: Sub-dimension Analysis: Average Performance Across All Models. Path: Path Correctness; Finals: Finals Correctness; Class.: Classification Accuracy; Ling.: Linguistic Quality; Anth.: Anthropomorphism; Cont.: Content Utility; Satis.: User Satisfaction; Instr.: Instruction Compliance (0-100 Scale).

Scenario

Logic Ability Path Action Class.

Ling.

Chat Quality Anth. Cont. Satis.

Instr.

AirlineRefund E-commerceRefund LogisticsDelivery OnlineEducation PropertyService TelecomPackage

64.4 66.0 64.3 67.0 67.2 74.6

29.4 29.5 32.3 43.0 57.1 58.7

72.5 88.0 66.9 80.2 64.0 65.9

68.3 70.1 68.9 71.6 71.3 67.9

56.2 58.8 55.5 62.3 58.3 52.8

60.6 62.1 58.6 60.0 60.8 52.1

62.0 64.0 60.0 61.7 62.1 53.9

73.1 71.4 71.6 73.0 75.0 66.3

Average

67.3

41.7

72.9

69.7

57.3

59.0

60.6

71.8

– Branching conditions based on classification fields and system variables – Terminal actions at leaf nodes • Evaluation Metrics: – Path Accuracy: Whether the agent follows the correct SOP path – Action Accuracy: Whether the agent selects the correct final action – Classification Accuracy: Accuracy of classifying dialogue fields – Chat Quality: LLM-judged quality of agent responses (5 dimensions) – JSON Error Rate: Whether the agent outputs valid JSON B.1.2

Six Scenarios Overview.

(1) Online Education: Student inquiry handling, complaint resolution, and refund negotiation (2) E-commerce Refund: Refund processing, order issue handling, and logistics anomalies (3) Telecom Package: Package subscription, modification, billing inquiry, and complaints (4) Property Service: Fee consultation, complaint handling, and maintenance services (5) Logistics Delivery: Package tracking, delivery issues, loss compensation, and returns (6) Airline Refund: Flight rebooking/refund, complaints, and flight information inquiry All six scenarios follow the same configuration structure but differ in their specific fields, actions, and SOP logic.

SAGE: A Service Agent Graph-guided Evaluation Benchmark

B.2

User Simulator Configuration Template

To simulate realistic customer interactions, we configure user simulators with: B.2.1

User Profile Components.

• User Intent: The user’s goal in the conversation (e.g., "inquiry", "complaint", "refund request") • Adversarial level of intent: Three levels to control conversation difficulty: – Zero Adversarial Intensity: Cooperative users who accept recommendations – Weak Adversarial Intensity: Users with mild concerns or questions – Strong Adversarial Intensity: Demanding or dissatisfied users requiring negotiation • Personality Traits: Defines user’s communication style (e.g., "friendly", "impatient", "detail-oriented") • Initial System State: Backend information about the user (e.g., order history, account status) B.2.2 Interaction Guidelines. User simulators follow these behavioral guidelines: Positive Behaviors (What users should do): • Use natural language consistent with their personality • Gradually disclose information over multiple turns • Stay focused on their intent • Respond appropriately to agent’s actions • Maintain consistent emotion and adversarial level Negative Behaviors (What users should NOT do): • Do not switch intents mid-conversation • Do not reveal all information at once • Do not end the conversation prematurely • Do not break character or mention being simulated

B.3

Example: Telecom Package Scenario

This subsection provides a complete example using the Telecom Package scenario to illustrate the configuration, prompts, and decision paths. B.3.1 Scenario Configuration. Scenario: Telecom Package Subscription and Management Description: Handling customer inquiries about package subscription, package modification, billing inquiries, and complaint processing. Classification Fields: • ConsumptionType: User’s dialogue intention (Options: Enquiry, Change, Cancel) • ApplicationTendency: Whether user tends to subscribe to recommended package (Options: Agree, Reject, Hesitate) • ConsumptionProfile: Type of package user prefers (Options: Data, Voice) • EmotionTag: User’s emotion in dialogue (Options: Calm, Discontent) System Variables: • PackageStatus: User’s current package status (Contracted/NoContract)

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

• Penalty: Penalty fee if user cancels contracted package (integer) Actions: • ChangeOrder: Process package change for user • GoodBye: Politely end the conversation • TransHuman: Transfer to human agent SOP Stages: (1) stage1: Field Classification - Classify 4 fields based on dialogue (2) stage2: User Consumption Intention Judgment - Branch by ConsumptionType (3) stage3: User Consumption Profile Judgment - Branch by ConsumptionProfile (4) stage4: User Package Status Judgment - Branch by PackageStatus (5) stage5: Contract Penalty Situation - Branch by Penalty amount (6) stage6: User Application Tendency Judgment - Branch by ApplicationTendency (7) stage7: User Emotion Judgment - Branch by EmotionTag B.3.2

Prompts.

(1) Customer Service Agent Prompt Agent Prompt You are a professional intelligent customer service representative handling [telecommunications package subscriptions]. You must process user enquiries regarding package subscriptions according to the following Standard Operating Procedure (SOP) and system variables, outputting a complete response in JSON format. [System Variables Introduction] PackageStatus: User package status (Contracted/NoContract) Penalty: Penalty fee user needs to pay (int) [SOP Flow Introduction] 1. Field Classification (stage1): Classify the following 4 fields based on the given dialogue history, then jump to stage2. - ConsumptionType: User dialogue intent (Enquiry/Change/Cancel) - ApplicationTendency: Whether user tends to apply for recommended package (Agree/Reject/Hesitate) - ConsumptionProfile: Package type user prefers (Data/Voice) - EmotionTag: User emotion in dialogue (Calm/Discontent) 2. User Consumption Intent Judgment (stage2): Jump based on [ConsumptionType] field. - Jump Logic: Based on the value of [ConsumptionType], Enquiry→stage3; Change→stage4; Cancel→stage5. 3. User Consumption Profile Judgment (stage3): Jump based on [ConsumptionProfile] field. - Jump Logic: Based on the value of [ConsumptionProfile], jump to stage6. 4. User Package Status Judgment (stage4): Jump based on system variable [PackageStatus]. - Jump Logic: Based on the value of system variable [PackageStatus], Contracted→stage5; NoContract→ACTION=ChangeOrder→END.

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Ling Shi et al.

5. Contract Penalty Situation (stage5): Jump based on system variable [Penalty]. - Jump Logic: Based on the value of system variable [Penalty], Penalty=0→ACTION=ChangeOrder→END; Penalty≠0→stage7. 6. User Application Tendency Judgment (stage6): Jump based on [ApplicationTendency] field. - Jump Logic: Based on [ApplicationTendency] field, Agree→stage4; Reject/Hesitate→ACTION=GoodBye→END. 7. User Emotion Judgment (stage7): Jump based on [EmotionTag] field. - Jump Logic: Based on [EmotionTag] field, Calm→ACTION=ChangeOrder→END; Discontent→ACTION=TransHuman→END. [Action Descriptions] - ChangeOrder: Change package - GoodBye: Politely end the conversation - TransHuman: Transfer to human agent [Output Format Requirements] You must output in the following JSON format (do not include any other text): { "classification_output": { "ConsumptionType": "Enquiry"/"Change"/"Cancel", "ApplicationTendency": "Agree"/"Reject"/"Hesitate", "ConsumptionProfile": "Data"/"Voice", "EmotionTag": "Calm"/"Discontent" }, "cot": "Briefly explain your classification reasoning and SOP flow jump logic", "now_path": ["stage1", "stage2", "stage3", ...], "finals": { "Action": "ChangeOrder/GoodBye/TransHuman" }, "chat": "Your friendly, professional response to the user based on Action" } [Key Requirements - Must Follow] 1. Output pure JSON only, do not include any other content (such as explanations, notes, etc.). 2. JSON must contain the following fields: - classification_output (object) - cot (string) - now_path (array) - finals (object) - chat (string) 3. now_path must start from "stage1" and list the stages passed in order (e.g., ["stage1", "stage2", ...]). 4. The chat field must be limited to 40 words. It is a complete, concise user reply. The language must be consistent with the user’s language. The content must be enclosed in double quotes, and must not contain unescaped double quotes ("), backslashes (\), square brackets ([]), etc.; if you need to quote code or special content, please describe it in text instead of directly including code. 5. The complete JSON should be: { ... } (The outermost layer must have one and only one pair of curly braces).

You are role-playing as a telecom operator customer, preparing to consult with customer service or handle package-related services. [Your Identity] - User ID: {user_id} - Current Package: {current_package} - User Intent: {user_intent} - Adversarial level: {adversarial_intensity_description} - Your Personality: {personality} [Interaction Requirements] * What you should do: - Use natural language for communication. Preferably choose English, occasionally you can choose Chinese or other languages, but once you choose a language, you must remain consistent throughout the conversation - Respond accordingly based on the customer service representative’s reply and gradually advance the conversation - Strictly focus on your current intent ({user_intent}), do not deviate to other irrelevant topics - Avoid revealing all information at once, gradually disclose details to keep the conversation going for multiple rounds - Keep each reply concise and natural (5-15 words), simulating the rhythm of a real user’s conversation - When customer service asks for information, provide it gradually according to your personality and background, do not rush to end the conversation - When the problem is not fully resolved, continue to ask for details, confirm processes, or express concerns - If satisfied, express thanks and confirm follow-up steps; if not satisfied, continue to express your demands * What you should NOT do: - Do not cross intent boundaries: If your intent is "package inquiry", do not suddenly switch to "complaint" or "query other services" - Do not end the conversation too early: Do not easily say "OK thank you" and end before the problem is solved, ask for details in multiple rounds - Do not switch languages during the conversation: If you start with English, use English throughout; if you use Chinese, use Chinese throughout - Do not provide all information at once: Simulate real users’ gradual information disclosure - Do not deviate from role settings: Strictly act according to your personality and adversarial intensity - Do not mention that you are AI or simulating: Be fully immersed in the user role [Important Notes] - Maintain role consistency, strictly follow your intent boundaries - Adopt corresponding attitudes according to your adversarial intensity - Insist on your position when necessary - Let the conversation continue naturally, increase interaction rounds by asking, confirming, expressing emotions, etc.

(2) User Simulator Prompt Template

(3) Judge Prompt Template We use LLM-as-a-judge to evaluate chat quality. The judge evaluates five dimensions: Chat Quality Dimensions:

User Simulator Prompt

SAGE: A Service Agent Graph-guided Evaluation Benchmark

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

(a) Linguistic Quality (20%): Grammar, fluency, and professional language (b) Anthropomorphism & Emotion (25%): Natural human-like responses with appropriate emotional tone (c) Content Utility (25%): Accuracy and relevance of information provided (d) User Satisfaction (15%): Whether the response addresses user’s needs (e) Instruction Compliance (15%): Following SOP requirements and action descriptions Each dimension is scored on a 3-level scale (3/6/9 points), and the weighted sum yields a score from 0-100.

}, "classification_reasoning": "Explanation for classification decisions", "chat_quality_reasoning": "Explanation for each dimension’s score (e.g., 9 points means..., 6 points means..., 3 points means...)" } [Requirements] 1. Only output valid JSON 2. Scores must be exactly 3, 6, or 9 for each dimension 3. Provide clear reasoning for both classification and quality evaluation

Judge Prompt Template You are an expert evaluator assessing the quality of customer service agent responses in a telecom package scenario. [Your Task] Evaluate the agent’s response based on dialogue history, user message, and agent’s reply. Provide: 1. Classification of dialogue fields (ConsumptionType, ApplicationTendency, ConsumptionProfile, EmotionTag) 2. Chat quality evaluation across five dimensions [Chat Quality Dimensions] Each dimension is scored on a 3-level scale: 1. Linguistic Quality (Weight: 20%) - 9 points: Fluent, professional, grammatically perfect - 6 points: Generally clear with minor issues - 3 points: Poor grammar, unclear expression 2. Anthropomorphism & Emotion (Weight: 25%) - 9 points: Natural, empathetic, human-like interaction - 6 points: Somewhat robotic but appropriate tone - 3 points: Completely mechanical, inappropriate emotion 3. Content Utility (Weight: 25%) - 9 points: Accurate, comprehensive, directly addresses user needs - 6 points: Partially relevant, some information missing - 3 points: Irrelevant or incorrect information 4. User Satisfaction (Weight: 15%) - 9 points: Fully resolves user concerns, polite and helpful - 6 points: Partially addresses concerns - 3 points: Fails to address user needs, potentially frustrating 5. Instruction Compliance (Weight: 15%) - 9 points: Perfectly follows SOP and action requirements - 6 points: Minor deviations from instructions - 3 points: Significant violations of instructions [Output Format] { "classification": { "ConsumptionType": "Enquiry/Change/Cancel", "ApplicationTendency": "Agree/Reject/Hesitate", "ConsumptionProfile": "Data/Voice", "EmotionTag": "Calm/Discontent" }, "chat_quality_dimensions": { "linguistic_quality": 3 or 6 or 9, "anthropomorphism_emotion": 3 or 6 or 9, "content_utility": 3 or 6 or 9, "user_satisfaction": 3 or 6 or 9, "instruction_compliance": 3 or 6 or 9

B.3.3 Decision Paths (PathList). The PathList enumerates all valid SOP decision paths for the scenario. Each path specifies: • Classification Items: Values of classification fields • System Variables: Backend state (e.g., PackageStatus, Penalty) • Expected Path: Sequence of SOP stages • Final Output: Terminal action B.3.4 Example Paths. Below are three representative paths from the Telecom Package scenario: Path 1: Enquiry + Agree + Data + NoContract → ChangeOrder { "Classification_items": ["Enquiry", "Agree", "Data", "Calm"], "system_variables": {"PackageStatus": "NoContract", "Penalty": 0}, "expected_path": ["stage1", "stage2", "stage3", "stage6", "stage4"], "final_output": {"Action": "ChangeOrder"} } Path 2: Change + Contracted + Penalty>0 + Discontent → TransHuman { "Classification_items": ["Change", "Agree", "Data", "Discontent"], "system_variables": {"PackageStatus": "Contracted", "Penalty": 100}, "expected_path": ["stage1", "stage2", "stage4", "stage5", "stage7"], "final_output": {"Action": "TransHuman"} } Path 3: Enquiry + Reject + Voice → GoodBye { "Classification_items": ["Enquiry", "Reject", "Voice", "Calm"], "system_variables": {"PackageStatus": "NoContract", "Penalty": 0}, "expected_path": ["stage1", "stage2", "stage3", "stage6"], "final_output": {"Action": "GoodBye"} }

Note: The complete Telecom Package scenario has 36 valid paths in total. The other five scenarios have similar PathList structures with varying numbers of paths based on their complexity.

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

SOP Graph of 6 Scenarios in Our Evaluation

In this section, we visualize the Standard Operating Procedures (SOPs) formalized as directed graphs for the six industrial scenarios evaluated in SAGE. These graphs define the explicit logical constraints, state transitions, and action spaces that serve as the ground truth for our Rule Engine evaluation. 1. Ecommerce Refund (ER): As illustrated in Figure 10d, this is the most complex scenario in our benchmark. The graph features a deep decision tree with intricate branching based on ShippingStatus (Shipped/Unshipped/Signed) and Responsibility attribution. Crucially, it incorporates dynamic checks on user CreditLevel to determine immediate refund eligibility. The agent must navigate this multi-branch logic to verify eligibility and negotiate terms, validating its capability in handling high-complexity disputes. 2. Logistics Delivery (LD): Shown in Figure 10a, this scenario centers on supply chain exception handling. The SOP graph requires the agent to track package status and process insurance claims based on ComplaintValidity. Key logic nodes include RiskStatus (intercepting risky orders) and EmergencyLevel (prioritizing urgent registrations), testing the agent’s proficiency in managing urgency and strictly following insurance protocols. 3. Telecom Package (TP): Depicted in Figure 10c, this is a standardized scenario with relatively linear logic. The flow focuses on billing inquiries and plan upgrades, guided by ConsumptionType (Enquiry/Change/Cancel). The agent must check PackageStatus

Ling Shi et al.

and Contracted states before executing changes. The graph primarily evaluates the agent’s accuracy in instruction-following and executing upselling protocols within a structured framework. 4. Property Service (PS): As seen in Figure 10e, this scenario emphasizes community coordination. The graph divides flows into Payment, Complaint, and Repair, requiring checks on HouseStatus (Occupied/Vacant) and FeePaymentStatus. The logic is designed to test the agent’s ability to coordinate offline services (e.g., scheduling repairs) while managing resident emotions in noise complaint subbranches. 5. Airline Refund (AR): Illustrated in Figure 10f, this is a highcomplexity, high-pressure scenario governed by rigid policies. The graph enforces strict validation of ChangeReason (Personal vs. Airline/Weather) and memberLevel (VIP/Regular). The agent must precisely calculate dynamic cancellation fees based on these variables. This structure rigorously tests the agent’s precision in policy adherence and its ability to de-escalate passenger anxiety under time constraints. 6. Online Education (OE): Shown in Figure 10b, this scenario focuses on rigorous Risk Control. The graph explicitly includes a isRiskUser check to identify potential malicious refunders based on historical records. The agent must strictly adhere to complex refund formulas and select specific PLAN options (A-F) based on the user’s learning dependency. This design serves as a stress test for logical reasoning and compliance with anti-fraud protocols.

SAGE: A Service Agent Graph-guided Evaluation Benchmark

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

(a) Logistics Delivery (LD) SOP

(b) Online Education (OE) SOP

(d) E-commerce Refund (ER) SOP

Figure 10: Standard Operating Procedures (SOPs) for Six Industrial Scenarios evaluated in SAGE. These directed graphs define the logical constraints and action spaces for each domain.(continued)

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Ling Shi et al.

(e) Property Service (PS) SOP

(f) Airline Refund (AR) SOP

Figure 10: Standard Operating Procedures (SOPs) for Six Industrial Scenarios.

Record · ID 6015 · SHA-256 1eb8bea70ded9bc6
Conceptio Open Knowledge Archive — every document is proof-bundled with source, license, and retrieval metadata.