TOPAS: Workflow-Aware Prefix-State Scheduling for Multi-Agent LLM Serving
TOPAS jointly optimizes prefix residency and request scheduling, reducing task JCT by up to 39.8% on synthetic workloads.
Key Findings
Methodology
TOPAS employs a hierarchical search framework integrating task-oriented prefix-aware scheduling. It constructs post-decision GPU states by evaluating candidate prefix sets and request allocations using a utility function that balances expected reduction in remaining service paths, prefix movement costs, and preemption penalties. The core algorithm involves a layered exploration of feasible states, guided by a heuristic based on the longest remaining path (LP) estimate, and incorporates a task aging mechanism to prevent starvation. Implementation within the SGLang platform enables large-scale evaluation on synthetic DAGs and MetaGPT workflows, demonstrating significant performance gains.
Key Results
- On synthetic DAGs (Chain-3, DAG-4, DAG-10-Wide), TOPAS reduces mean/99th percentile JCT by up to 39.8%/49.4%, outperforming all baselines. In MetaGPT workloads, it lowers mean JCT by 9.8% (SOP) and 22.0%/26.6% (TL) at the 99th percentile.
- Experiments show TOPAS effectively balances prefix reuse and workflow progress, reducing prefix migration overhead and improving GPU utilization. Ablation studies confirm that future reuse and aging mechanisms are critical for performance.
- Compared to request-level schedulers like FCFS, LPM, and SPF, TOPAS achieves superior task completion times across diverse workload structures, validating its holistic approach.
Significance
This work addresses a fundamental bottleneck in multi-agent LLM serving—balancing prefix cache management with request scheduling under limited GPU memory. By explicitly modeling prefix residency as a joint decision, TOPAS advances the state-of-the-art in workflow-aware scheduling, enabling faster task completion and more efficient resource utilization. Its innovative framework offers a scalable solution for deploying large-scale multi-agent AI systems in real-world applications such as AI-assisted software development, conversational AI, and autonomous systems, where latency and throughput are critical.
Technical Contribution
TOPAS introduces a novel task-oriented utility function that jointly considers prefix reuse, request admission, and transition costs. Its hierarchical state search algorithm efficiently explores the feasible scheduling space, guided by a heuristic based on the estimated reduction in remaining service paths. The integration of a task aging mechanism ensures fairness, preventing starvation. The framework's modular design allows seamless integration into existing inference systems like SGLang, and its empirical validation demonstrates substantial improvements over traditional request-level schedulers, establishing new benchmarks for multi-agent LLM deployment.
Novelty
This research is the first to treat prefix residency as an explicit, jointly optimized scheduling variable in multi-agent LLM serving. Unlike prior work focusing solely on request ordering or cache management, TOPAS combines these aspects into a unified framework, leveraging a hierarchical search guided by a task-level utility. Its innovative approach effectively resolves the conflict between prefix locality and overall workflow progress, setting a new direction for intelligent resource management in large-scale AI systems.
Limitations
- The current model assumes static task dependencies and known request profiles, which may not hold in dynamic real-world scenarios, potentially affecting scheduling robustness.
- The hierarchical search incurs computational overhead, especially in large agent pools, necessitating further optimization for real-time deployment.
- Evaluation mainly focuses on synthetic DAGs and specific MetaGPT workloads; broader validation across diverse industrial tasks remains future work.
Future Work
Future research will explore adaptive models incorporating dynamic task dependencies and uncertainties, possibly via reinforcement learning. Extending the framework to multi-GPU and heterogeneous resource environments will be crucial for scalability. Additionally, integrating predictive workload modeling and online learning could further enhance scheduling efficiency and robustness in real-world, high-variability settings.
AI Executive Summary
The rapid growth of multi-agent large language models (LLMs) has revolutionized complex task automation, yet resource constraints—particularly GPU memory—pose significant challenges. Traditional request-level schedulers optimize batching and cache management independently, often leading to suboptimal resource utilization and increased latency. This paper introduces TOPAS, a task-oriented, prefix-aware scheduling framework that explicitly models and jointly optimizes prefix residency and request admission decisions.
TOPAS employs a hierarchical search algorithm guided by a utility function that balances the anticipated reduction in remaining service paths against the costs of prefix migration and preemption. By integrating future prefix reuse potential and task aging mechanisms, TOPAS dynamically adapts to evolving workflow states, ensuring fairness and efficiency. Implementation within the SGLang platform demonstrates its scalability and effectiveness across synthetic DAGs and real-world MetaGPT workflows.
Experimental results show that TOPAS outperforms existing baselines, reducing average and tail task completion times by up to 39.8% and 49.4%, respectively, on synthetic workloads, and achieving significant improvements in real software development scenarios. Its ability to balance prefix locality with overall workflow progress marks a substantial advance in multi-agent LLM serving, promising faster, more resource-efficient AI systems.
Despite these successes, challenges remain in handling dynamic task dependencies and large-scale state spaces. Future work aims to incorporate adaptive learning strategies, extend to multi-GPU environments, and validate across broader industrial applications, paving the way for more robust, scalable AI deployment frameworks.
Deep Analysis
Background
多智能体大语言模型（LLM）在自动化、智能交互中的应用不断扩大，早期工作如FastChat、SGLang等主要关注请求批处理和缓存优化。随着模型参数规模的增长，前缀缓存成为提升推理效率的关键技术，但有限的GPU内存限制了缓存容量，导致请求调度与缓存管理之间存在资源冲突。现有调度策略多偏重请求级优化，忽视了工作流依赖和前缀重用的全局影响，造成资源利用率低和延迟增加。近年来，研究开始关注工作流感知调度，但多智能体环境中前缀迁移与请求调度的联合优化仍未充分解决，亟需创新策略以实现资源的最优配置。
Core Problem
在多智能体LLM服务中，GPU内存有限制了前缀缓存的规模，导致请求调度必须在前缀局部性和工作流整体进展之间权衡。传统策略如最长前缀匹配（LPM）和最短剩余时间（SRPT）各有优劣，但都未能同时兼顾前缀重用和任务完成时间。请求调度的决策影响前缀驻留状态、请求批量大小和工作流整体效率。如何在有限缓存预算下，动态决定哪些前缀应驻留、哪些请求应调度，成为提升系统性能的核心难题。
Innovation
本研究提出TOPAS，创新性地将前缀驻留作为显式调度变量，通过层次化搜索结合启发式评分，联合优化请求调度与缓存状态。其核心创新包括：1）引入基于最长剩余路径的预估模型，动态评估请求对任务剩余路径的影响；2）结合未来重用潜力，提前调度可能支持后续工作；3）引入任务老化机制，确保任务公平性，避免饥饿。该框架突破了传统请求优先级单一的限制，实现全局最优调度，有效平衡前缀局部性与工作流整体进展，显著提升多阶段、多智能体环境中的任务完成效率。
Methodology
- �� 采用层次化状态空间搜索，构建后置GPU状态，结合前缀集和请求集。
- �� 利用最长剩余路径（LP）模型，评估每个请求对任务剩余路径的预期减少量。
- �� 设计基于未来重用潜力的启发式评分，结合前缀迁移和抢占成本，动态选择最优状态。
- �� 引入任务老化机制，确保任务公平性，避免饥饿。
- �� 通过在SGLang平台实现，结合合成DAG和MetaGPT工作流进行大规模评估，验证调度策略的有效性。
Experiments
在三种合成DAG（Chain-3、DAG-4、DAG-10-Wide）和两种MetaGPT软件开发工作流中，评估TOPAS的性能。对比基线包括FCFS、LPM、Parrot-FCFS、Autellix-LAS和SPF。指标涵盖平均和第99百分位JCT、请求吞吐量。采用Poisson请求到达模型，调度决策平均耗时在2ms以内。实验结果显示，TOPAS在所有场景中均优于基线，平均JCT提升最高达39.8%，第99百分位提升49.4%。
Results
TOPAS在合成DAG中显著缩短任务完成时间，平均/第99百分位JCT分别比最优基线提升39.8%/49.4%，在MetaGPT场景中也表现优异。消融实验表明，未来重用和任务老化机制是性能提升的关键。整体来看，TOPAS有效平衡了前缀局部性与工作流进展，减少了前缀迁移和抢占开销，提升GPU资源利用率，验证了其在复杂多阶段、多智能体环境中的优越性。
Applications
该调度框架适用于大规模多智能体LLM推理系统，特别是在软件开发、AI推理和多任务协作场景中。通过优化前缀驻留和请求调度，显著缩短任务延迟，提高系统吞吐量。未来可结合多GPU和异构资源管理，推动工业级AI系统的高效部署，满足复杂应用对实时性和效率的双重需求。
Limitations & Outlook
当前模型假设任务依赖关系已知且静态，实际场景中任务动态变化和不确定性可能影响调度效果。搜索策略在大规模状态空间中存在计算瓶颈，需进一步优化。评估主要集中在合成和特定工作流，工业应用中的多样性和复杂性仍待验证。未来需增强模型的鲁棒性和扩展性，降低计算成本。
Plain Language Accessible to non-experts
想象你在管理一个大型厨房，里面有许多厨师（智能体）同时准备不同的菜肴（任务）。每个厨师有自己的食谱（前缀），需要用到一些公共的食材（缓存中的前缀）。厨房的空间有限，不能让所有食材都存放在一起，所以你必须决定哪些食材留在厨房，哪些厨师可以使用这些食材。合理安排厨师使用食材，不仅能让菜肴更快做好，还能减少不断搬动食材的时间。这个调度就像TOPAS，它帮助你在有限空间里，既让厨师用到常用食材，又保证菜肴按时完成。
ELI14 Explained like you're 14
想象你在学校的食堂里，有很多学生（请求）同时想吃饭。每个学生有自己的菜单（任务），而厨房里存放的食材（前缀缓存）有限。为了让所有学生都能快点吃到饭，你需要决定哪些食材放在厨房，哪些学生可以用到这些食材。比如，有的学生经常点同样的菜（同一前缀），把这些菜的食材放在厨房里可以节省时间，但如果放太多不同的菜，厨房就会变得拥挤，不能同时服务太多学生。TOPAS就像一个聪明的食堂管理员，他会根据每个学生的点餐习惯，合理安排食材和学生的顺序，让每个人都能尽快吃到饭，又不让厨房太拥挤。
Glossary
Prefix Cache (前缀缓存)
存储静态前缀的KV对，用于请求的快速重用。技术上为请求共享的静态KV集合，减少重复计算。
论文中描述多智能体LLM请求中静态前缀的存储与重用机制。
Longest Remaining Path (最长剩余路径)
估算任务中剩余服务路径的最长长度，用于衡量任务的剩余工作量。通过反向拓扑排序计算。
作为调度中衡量任务优先级和优化目标的核心指标。
Task-Oriented Prefix-Aware Scheduler (任务导向前缀感知调度器)
结合任务进展和前缀重用的调度策略，动态决策缓存中的前缀与请求调度以最小化任务JCT。
论文提出的TOPAS调度框架的核心思想。
GPU KV Cache (GPU键值缓存)
存放模型静态前缀KV对的有限存储，用于加速推理请求。资源有限，需合理调度。
调度决策的重要资源限制因素。
Workflow DAG (工作流有向无环图)
描述任务依赖关系的有向无环图，定义任务的执行顺序和依赖关系。
用于建模多阶段、多智能体任务的结构。
Open Questions Unanswered questions from this research
- 1 如何在动态变化的任务依赖和不确定请求到达时间下，进一步优化前缀调度策略？
- 2 多GPU环境中，调度策略如何扩展以实现全局资源最优？
- 3 在实际工业场景中，如何应对模型和任务的高动态性与复杂性？
Applications
Immediate Applications
AI推理加速平台
利用TOPAS优化多智能体LLM请求调度，提升推理速度和资源利用率，适用于企业AI服务和云端推理平台。
软件开发自动化
在软件开发中，结合多任务调度和前缀缓存管理，缩短开发流程中的模型推理时间，提高开发效率。
Long-term Vision
智能多任务协作系统
推动多智能体系统在自动驾驶、机器人协作等领域的应用，通过高效调度实现实时响应和大规模部署。
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.