G-STAR: Graph-based Scheduling with Trace-driven Adaptive Routing for Industrial LLM-based Multi-Agent Systems

Abstract

Large Language Model-based Multi-Agent Systems (LLM-MAS) have shown exceptional promise for complex tasks, including retrieval-augmented generation and autonomous data analytics. However, their deployment in resource-constrained industrial environments faces critical challenges, such as unpredictable end-to-end latency, low task success rates, and expensive operational costs. Existing orchestration strategies for LLM-MAS mainly rely on static heuristics, implicit LLM-based routing, or reinforcement learning, which suffer from brittleness under workload drift, prohibitive online exploration costs, and inherent governance risks. To address these issues, we propose G-STAR, a general graph-based scheduling framework that formalizes complex MAS pipelines as attributed Directed Acyclic Graphs (DAGs). Specifically, G-STAR decouples its learning pipeline into three critical stages to ensure both system stability and execution efficiency. First, we build a data layer that logs fine-grained signals for agent node (e.g., execution latency, token I/O, model IDs, resource metrics) and task-grounded outcomes (e.g., accuracy, cost, SLA), yielding a trace-driven dataset. Second, we train an offline GNN model to predict optimal dynamic routing decisions, including agent activation, concurrency-constrained Top-K selection, and execution ordering, conditioned on the evolving graph state. Finally, a lightweight dispatcher deploys the pre-trained GNN model for single-forward-pass routing with negligible computational overhead. Extensive experiments on two public benchmarks and our real-world production workload confirm G-STAR's superiority over static and LLM-driven baselines. It maintains competitive task quality while reducing latency variability and consistently improving end-to-end latency. Furthermore, we develop an industry-grade orchestration stack with asynchronous execution, resilient serving, and audit-friendly artifacts, offering a practical solution for optimizing web-scale deployments of complex MAS pipelines.