Aug 2026· Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2· 0 citations· 11 references
TL;DR
G-STAR is a general graph-based scheduling framework that formalizes complex MAS pipelines as attributed Directed Acyclic Graphs (DAGs) and develops 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.
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.
This survey presents a systematic taxonomy and technical review of dynamic orchestration strategies designed to address communication overhead, KV cache management challenges, and increased token consumption within large Language Model-based Multi-Agent Systems.
Heet Nagoriya, H. Raithatha· International Journal of Kno...· 0 citations
Results provide initial evidence that multi-round CNP refinement is the principal protocol-level gain, with LLM assistance adding value for qualitative and uncertain runtime context.
Cloud-edge-end collaborative Artificial Intelligence (AI) computing requires schedulers that allocate heterogeneous resources for Directed Acyclic Graph (DAG)-structured workflows across network tiers. Cross-tier data transfers create ripple effects where a single placement decision propagates delays to downstream tasks, degrading end-to-end completion rates. This paper presents DREAM, a Dynamic Ripple-Effect-Aware Meta-scheduling scheme in which Critical Path Lookahead Scheduling (CPLS) performs bounded-depth trajectory planning with soft reservations for critical tasks, while Opportunity-Cost-Aware Placement (OCAP) evaluates non-critical tasks through a four-component cost covering immediate efficiency, ripple effect, load stability, and opportunity cost. Extensive simulations demonstrate that under the heavy load of 600 tasks, DREAM sustains a task completion rate of ~66%, exceeding classical heuristics by over 10 percentage points. At the extreme load of 1000 tasks, the system utility score improves by 47% over HEFT. Robustness experiments verify competitive performance across multiple DAG topologies and estimation-noise levels.
Chenlu Wang, Yuhuai Peng, Lei Liu et al.· IEEE Transactions on Cogniti...· 0 citations
Multi-agent large language model (LLM) workflows have emerged as a powerful paradigm for solving complex, open-ended tasks through collaborative reasoning among specialized LLM agents, but they incur substantial operating costs due to repeated LLM invocations and long-horizon context accumulation. Existing cascade routing methods make one-shot, query-level decisions and cannot adapt to the dynamic, state-dependent nature of multi-step workflows, in which the right LLM at each step depends on evolving task progress, remaining task difficulty, and cost-efficiency requirements. We present ProgRouter, an online progress-guided routing framework that adaptively selects LLM agents across workflow steps to preserve task-solving quality while adhering to time and cost budgets. ProgRouter introduces a multi-view task progress scorer that combines coarse workflow outcome regimes with fine-grained signals on subtask completion, progress trends, and workflow state quality. Then, a dual-path task progress predictor and an adaptive meta-gating mechanism estimate the progress gain for each candidate routed LLM. ProgRouter makes online step-wise routing decisions that balance progress gain, task time budgets, and long-term operating cost efficiency. Experiments on HumanEval Plus, MBPP, MATH-500, and ASQA, spanning agentic code generation, mathematical reasoning, and retrieval-augmented long-form question answering, demonstrate that ProgRouter reduces the operating cost relative to key baselines while maintaining strong task-solving performance.
Somgyuan Li, Ahmed M. Abdelmoniem, Shi-Qiang Wang· 0 citations
Multi-agent applications increasingly rely on shared large language model backends in the public cloud, where bursty workloads cause requests from different agents to contend for the same LLM instances, leading to long queues, memory imbalance, and severe tail-latency inflation. Existing approaches typically prioritize requests using coarse workflow positions or static execution heuristics, which fail to adapt to short-term overload dynamics. We present FlowGuard, a workflow-aware overload controller for multi-agent LLM serving. Its key insight is that under sustained overload, GPU cycles spent on requests whose execution service-level-objectives (SLOs) are already violated are wasted. FlowGuard continuously recomputes per-request slack and prioritizes requests with the greatest remaining time before their deadlines, thereby maximizing on-time completions. In addition, a resource-aware dispatcher jointly accounts for KV-cache memory pressure and in-flight queue depth to reduce preemption across shared instances. Evaluated on a deliberately over-subscribed two-GPU backend, where all policies exhibit high absolute miss rates (i.e., the percentage of workflows that miss their deadlines), FlowGuard reduces the miss rate by 14–28% points over workflow-oblivious and static-priority baselines under BurstGPT-driven load, and by 34–38% points under co-located mixed-agent workloads.
Ali Zafar Sadiq, Haiying Shen· International Conference on...· 0 citations
Deploying Large Language Models (LLMs) over the edge-cloud continuum faces severe stability challenges due to the conflict between stochastic network topology and complex workflow dependencies. Existing schedulers, relying either on computationally prohibitive Graph Neural Networks (GNNs) or topology-agnostic heuristics, fail to reconcile this tension. To bridge these gaps, we propose STEM, a service-level and topology-aware orchestration framework that formulates distributed LLM serving as a workflow-aware routing problem over a monitored service overlay, in which heterogeneous service instances act as specialized experts. At the core of STEM lies the STAR-PPO algorithm, utilizing a lightweight graph-free perception mechanism. By leveraging Squeeze-and-Excitation attention, it extracts critical bottleneck features from raw telemetry with linear complexity, bypassing the scalability limits of message-passing paradigms. To further achieve Pareto-efficient trade-offs, we develop a Dynamic Weight Adaptation (DWA) mechanism that autonomously recalibrates optimization preferences based on entropy-regularized metric drift. Extensive experiments on real-world datasets spanning 2,000 nodes demonstrate that our framework significantly outperforms state-of-the-art baselines. Specifically, STAR-PPO reduces network transmission costs by 96.8% and improves comprehensive inference efficiency by 24.4%, while sustaining robust zero-shot generalization across regions, with average latency within $1.09\times $ of a target-domain-retrained reference under a strict cross-region protocol. Code and data are available at https://github.com/gymorsiback/STARPPO
Yan Gao, Shaoyuan Huang, Yonghui Ye et al.· IEEE Transactions on Cogniti...· 0 citations