AgentQoSBench: Evaluating Quality-of-Service Awareness in Agents under Complex Tool Dependencies

Agents increasingly handle tasks with complex tool dependencies. Beyond correct completion, users have service-quality requirements or preferences. Quality of service (QoS), rooted in networking and service computing, describes latency, cost, and reliability. We evaluate agents' QoS awareness by extending QoS-aware service composition to autonomous planning with tool-call graphs, jointly assessing tool selection, dependencies, and whole-graph optimization. We introduce QoSGen (Quality-of-Service-Aware Benchmark Generation), a construction and validation pipeline that produces AgentQoSBench: 600 synthetic tasks across consumer and workplace scenarios with multiple valid plans and exact optima under explicit service models grounded in tool characteristics and composition mechanisms. For 49.7% of functionally valid tool-call plans produced by mainstream models, we verify a complete alternative with strictly better QoS. Using failure diagnosis and reasoning traces, we analyze agents' graph-search behavior, showing how local choices can overlook sharing and parallelism or create cross-branch conflicts. These findings motivate training-free search prompting and prompt-guided graph-search assistance. Prompting improves optimization within valid plans for GLM and DeepSeek, while tool assistance highlights the importance of preserving task requirements during candidate integration. Together, these approaches offer practical directions for improving QoS awareness through whole-graph comparison and agent-tool collaboration.