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.
Figures & tables
Load
Makespan (s) (G/A)
Mean batch (G/A)
Peak batch (G/A)
n=100
1145.5/2086.0
9.3/4.7
15/8
n=150
1639.3/3104.4
10.0/4.8
16/8
n=200
2143.5/4079.1
11.5/5.0
16/7
TABLE I: Under FCFS, heterogeneous prefix co-residency shrinks the running batch, thereby increasing makespan. Slash-separated values are Grouped/Alternating.
Fig. 1: Chain-3 at 0.15 task/s under locality-first LPM, progress-first SRPT, and downstream gating.
Fig. 2: A Gantt chart comparing LPM and SRPT on an A→B→C workflow. GPU memory can hold the KV cache for only one Agent prefix at a time; each request takes four time units, and each prefix setup takes one time unit.
Fig. 3: End-to-end task completion on the synthetic DAG workloads.
Fig. 4: Task completion on the MetaGPT workloads; high-load Autellix-LAS values exceed the displayed MetaGPT-TL range.
Fig. 5: MetaGPT-TL component ablation at 0.0175 task/s.
Large language model inference scheduling allocates requests, batches, compute, and KV-cache memory to balance latency, throughput, and service-level objectives.