A Task-Oriented Prefix-Aware Scheduler that jointly decides which agent prefixes to keep in the cache and which requests to schedule for execution and scores candidate post-decision states by trading off the expected reduction in each task's longest remaining service path against the near-term benefit of downstream prefix reuse.
Abstract
Prefix caching introduces a fundamental tradeoff in multi-agent large language model (LLM) serving: retaining a long system-prompt key-value (KV) cache for an agent accelerates future calls, yet it reduces the GPU memory available for batching concurrent requests. In multi-stage workflows, existing schedulers tend to prioritize either immediate prefix locality or overall workflow progress. However, under a shared KV cache budget, optimizing either objective in isolation can prolong tasklevel job completion time (JCT) through downstream delays or frequent prefix replacement. To strike a balance, we here propose TOPAS, a Task-Oriented Prefix-Aware Scheduler that jointly decides which agent prefixes to keep in the cache and which requests to schedule for execution. TOPAS scores candidate post-decision states by trading off the expected reduction in each task's longest remaining service path against the near-term benefit of downstream prefix reuse, accounting for the costs of prefix movement and preemption. A task-level aging mechanism is also incorporated to prevent starvation. We implement TOPAS within the SGLang framework and assess its performance on three synthetic DAGs and two MetaGPT software-development workflows. Compared with the best performing baseline for each workload and metric, TOPAS reduces the mean/p99 JCT by up to 39.8%/49.4% on the synthetic workloads, while lowering mean JCT by 9.8% on MetaGPT-SOP and mean/p99 JCT by 22.0%/26.6% on MetaGPT-TL.
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, Hai-Ying Shen· International Conference on...· 0 citations
Concurrent multi-agent workflows expose future dependencies and serving-state requirements while running on heterogeneous GPU pools with time-varying load, model residency, and resource availability. The logical workflow defines the required computation, whereas its physical scheduling units, model-lifecycle actions, resource ordering, and placement must be selected according to the observed pool state. We present a prediction-guided runtime that uses workflow forecasts to construct and optimize a physical execution graph. Predictor estimates device-specific activation latency, peak memory, and model-loading cost, then propagates these predictions through workflow dependencies to forecast activation readiness and future model demand. Constructor builds semantics-preserving fusion and model-lifecycle alternatives, while Scheduler jointly optimizes their selection, placement, and execution order based on the live pool state. Across a workload spanning three workflow scenarios on a heterogeneous GPU pool, our system reduces end-to-end makespan and overall p95 completion latency under burst arrivals by up to 36.8% and 25.9%, respectively, over state-of-the-art workflow schedulers. It also saves up to 24.63 GPU-s per completed session.
Jing-Hao Wang, Yi-Feng Zhang, Xiao Zhou et al.· 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.
Public LLM services serve diverse multi-agent applications with varying workflow dependencies and performance requirements. Requests generated by these applications often exhibit commonality and interdependence, yet current systems largely ignore such application-level structure. As a result, at the LLM engine cluster level, assigning requests to engines with the shortest queue can cause inefficient KV-cache transfers across GPUs. Using three representative multi-agent applications, we show that current scheduling methods miss opportunities to (a) improve performance through KV-cache reuse and reduced data transfer, and (b) increase goodput via batch management informed by workflow dependencies. Motivated by these observations, we propose a Workflow-Aware Scheduling system for Multi-Agent LLM systems (WaSMa) that incorporates cluster-and engine-level scheduling to optimize LLM request execution across GPU resources. Experimental results show that WaSMa reduces the P95 tail latency by up to 48% and improves goodput by up to 107% compared to existing methods.
Uttam Rao, Ali Zafar Sadiq, Hai-Ying Shen et al.· International Conference on...· 0 citations
ProgRouter is presented, 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 and reduces the operating cost relative to key baselines while maintaining strong task-solving performance.
Songyuan Li, Ahmed M. Abdelmoniem, Shi-Qiang Wang· 0 citations
An epoch-level planner, PrefixPlace, which assigns prefix-complete targets under memory budgets and profiled demand, compute, and transfer costs, and solves a 50,000-node, 16-worker placement in 12.3 s on one processor, enabling timely replanning.
Zhiyu Wang, Rajkummar Buyya· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
