SAGA: Workflow-Atomic Scheduling for AI Agent Inference on GPU Clusters

• URL: http://arxiv.org/abs/2605.00528v1
• Date: Fri, 01 May 2026 09:05:28 GMT
• Title: SAGA: Workflow-Atomic Scheduling for AI Agent Inference on GPU Clusters
• Abstract summary: We propose a shift to program-level scheduling for compound AI workloads.<n>We present SAGA, a distributed scheduler that implements this abstraction through three mechanisms.
• Score: 13.891522069967507
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: AI agents execute tens to hundreds of chained LLM calls per task, yet GPU schedulers treat each call as independent, discarding gigabytes of intermediate state between steps and inflating end-to-end latency by 3-8x. We argue that this request-level abstraction is fundamentally mismatched to compound AI workloads, and propose a shift to program-level scheduling: treating the entire agent workflow (not individual inference calls) as the first-class schedulable unit. We present SAGA, a distributed scheduler that implements this abstraction through three mechanisms: (1) Agent Execution Graphs that capture workflow structure to predict KV cache reuse across tool-call boundaries, achieving within 1.31x of Bélády's optimal offline policy; (2) session-affinity batching with work stealing that co-locates correlated requests while maintaining global load balance; and (3) Agent Fair Share, a task-completion-time fairness metric with provable bounded-deviation guarantees. On a 64-GPU cluster serving SWE-bench coding agents and WebArena browser tasks, SAGA reduces task completion time by 1.64x (geometric mean, p < 0.001) over vLLM v0.15.1 with prefix caching and affinity routing, while improving GPU memory utilization by 1.22x and achieving 99.2% SLO attainment under multi-tenant interference. These latency gains come at a quantified cost: approximately 30% lower peak throughput than throughput-optimal batch scheduling, a tradeoff appropriate for the latency-sensitive interactive deployments that dominate compound AI usage. Our results demonstrate that workflow-aware scheduling is essential for efficient compound AI serving.

Related papers

• A-MADiff: Attention-Guided Multi-Agent DRL with Diffusion Policies for Memory-Aware Task Orchestration in Mobile AIGC Networks [12.516277671699525]
  Mobile AIGC networks host GenAI models on edge-located AIGC Service Providers (ASPs) to deliver low-latency and personalized AIGC services for mobile users.<n>Existing studies on AIGC task orchestration have largely overlooked GPU memory feasibility constraints.<n>We propose an underlineAttention-guided underlineMulti-underlineAgent deep reinforcement learning algorithm with underlineDiffusion policies (A-MADiff)<n> Numerical results demonstrate that A-MADiff significantly improves the cumulative reward over the state-of-the
  arXiv  Detail & Related papers  (2026-08-29T13:19:44Z)
• TOPAS: Workflow-Aware Prefix-State Scheduling for Multi-Agent LLM Serving [8.123227365399869]
  We propose TOPAS, a Task-Oriented Prefix-Aware Scheduler.<n> TOPAS scores candidate post-decision states by trading off the expected reduction in each task's longest remaining service path.<n>Compared with the best performing baseline for each workload and metric, TOPAS reduces the mean/p99 JCT by up to 39.8%.
  arXiv  Detail & Related papers  (2026-08-26T08:33:10Z)
• OSDAG: Online Scheduling for Efficient Multi-Robot Collaboration [2.2726869886741383]
  This paper presents OSDAG, a novel framework that integrates LLM-based task reasoning with Directed Acyclic Graph representation and constraint-aware online scheduling.<n> Experiments across five benchmark scenarios demonstrate that OSDAG achieves 5-15x faster reasoning time compared to dialogue-based methods, reduces makespan by up to 38% over sequential baselines, and maintains competitive success rates.
  arXiv  Detail & Related papers  (2026-06-13T11:22:34Z)
• Speculative Interaction Agents: Building Real-Time Agents with Asynchronous I/O and Speculative Tool Calling [64.40340291543971]
  We propose Speculative Interaction Agents to enable real-time interaction with small edge-scale models.<n>We also present a clock-based training methodology that adapts the model to handle streaming inputs and asynchronous responses.<n>This approach provides 1.6-2.2$times$ speedups with the Qwen2.5-3B-Instruct and Llama-3.2-3B-Instruct models across multiple tool calling benchmarks.
  arXiv  Detail & Related papers  (2026-05-13T11:20:52Z)
• A1: A Fully Transparent Open-Source, Adaptive and Efficient Truncated Vision-Language-Action Model [112.9420001646428]
  Vision-Language-Action (VLA) models have emerged as a powerful paradigm for open-world robot manipulation, but their practical deployment is often constrained by cost.<n>We present A1, a fully open-source and transparent VLA framework designed for low-cost, high- throughput inference.<n>A1 achieves state-of-the-art success rates while significantly reducing inference cost.
  arXiv  Detail & Related papers  (2026-04-07T10:18:40Z)
• Chimera: Latency- and Performance-Aware Multi-agent Serving for Heterogeneous LLMs [62.17306142810532]
  We present Chimera, a predictive scheduling system for multi-agent workflow serving on heterogeneous LLM clusters.<n>Chime traces the best latency, reducing end-to-end latency by 1.2--2.4$times$ and improving task performance by 8.0-9.5 percentage points on average over competitive baselines.
  arXiv  Detail & Related papers  (2026-03-23T17:01:42Z)
• RollArt: Scaling Agentic RL Training via Disaggregated Infrastructure [49.88201789074532]
  Agentic Reinforcement Learning (RL) enables Large Language Models (LLMs) to perform autonomous decision-making and long-term planning.<n>We present RollArc, a distributed system designed to maximize throughput for multi-task agentic RL on disaggregated infrastructure.
  arXiv  Detail & Related papers  (2025-12-27T11:14:23Z)
• Efficient Mixture-of-Agents Serving via Tree-Structured Routing, Adaptive Pruning, and Dependency-Aware Prefill-Decode Overlap [15.352230356342366]
  Mixture-of-Agents (MoA) inference can suffer from dense inter-agent communication and low hardware utilization.<n>We present a serving design that targets these bottlenecks through an algorithm-system co-design.
  arXiv  Detail & Related papers  (2025-12-19T23:06:58Z)
• Astraea: A State-Aware Scheduling Engine for LLM-Powered Agents [12.884297990127985]
  Astraea is a service engine designed to shift the optimization from local segments to the global request lifecycle.<n>It employs a state-aware, hierarchical scheduling algorithm that integrates a request's historical state with future predictions.<n>Astraea reduces average JCT by up to 25.5% compared to baseline methods.
  arXiv  Detail & Related papers  (2025-12-16T06:55:10Z)
• Agent.xpu: Efficient Scheduling of Agentic LLM Workloads on Heterogeneous SoC [11.82567747365518]
  This paper introduces Agent.xpu, an efficient serving system for agentic LLM workloads on memory-unified heterogeneous SOCs.<n>With dedicated offline profiling, Agent.xpu first constructs a heterogeneous execution graph, which fuses and chunks model kernels for affinity-guided, elastic accelerator mapping.<n>At runtime, its online scheduler enables fine-grained, kernel-level preemption to guarantee the responsiveness of reactive tasks.
  arXiv  Detail & Related papers  (2025-06-30T16:50:48Z)
• FusionLLM: A Decentralized LLM Training System on Geo-distributed GPUs with Adaptive Compression [55.992528247880685]
  Decentralized training faces significant challenges regarding system design and efficiency. We present FusionLLM, a decentralized training system designed and implemented for training large deep neural networks (DNNs) We show that our system and method can achieve 1.45 - 9.39x speedup compared to baseline methods while ensuring convergence.
  arXiv  Detail & Related papers  (2024-10-16T16:13:19Z)
• DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
  We consider a setting in which $N$ agents aim to speedup a common Approximation problem by acting in parallel and communicating with a central server. To mitigate the effect of delays and stragglers, we propose textttDASA, a Delay-Adaptive algorithm for multi-agent Approximation.
  arXiv  Detail & Related papers  (2024-03-25T22:49:56Z)
• Multi-user Co-inference with Batch Processing Capable Edge Server [26.813145949399427]
  We focus on novel scenarios that the energy-constrained mobile devices offload inference tasks to an edge server with GPU. The inference task is partitioned into sub-tasks for a finer granularity of offloading and scheduling. It is proven that optimizing the offloading policy of each user independently and aggregating all the same sub-tasks in one batch is optimal. Experiments show that IP-SSA reduces up to 94.9% user energy consumption in the offline setting.
  arXiv  Detail & Related papers  (2022-06-03T15:40:32Z)
• Communication Contention Aware Scheduling of Multiple Deep Learning Training Jobs [17.45154289084637]
  We establish a new DDL job scheduling framework which organizes DDL jobs as Directed Acyclic Graphs (DAGs) We then propose an efficient algorithm, LWF-$kappa$, to balance the GPU utilization and consolidate the allocated GPU for each job. We show that LWF-$kappa$ achieves up to $1.59times$ improvement over the classical first-fit algorithms.
  arXiv  Detail & Related papers  (2020-02-24T07:50:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.