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

arXiv: https://arxiv.org/abs/2605.00528 · HTML: https://mlsanity.com/paper/2605.00528/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in Software engineering coding agents, one of 16 directions in LLM agents and tool use.
- Builds on 34 of its 83 references that are in the map.
- First posted on arXiv 1 May 2026.

## Placed in

- LLM agents and tool use / [Software engineering coding agents](https://mlsanity.com/agents/software-engineering-coding-agents/)

## Builds on (most cited first, 30 of 34)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [AutoGen: Enabling Next-Gen LLM Applications via Multi-Agent Conversation](https://mlsanity.com/paper/2308.08155/) (2023)
- [GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints](https://mlsanity.com/paper/2305.13245/) (2023)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving](https://mlsanity.com/paper/2401.09670/) (2024)
- [FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPU](https://mlsanity.com/paper/2303.06865/) (2023)
- [Splitwise: Efficient generative LLM inference using phase splitting](https://mlsanity.com/paper/2311.18677/) (2023)
- [Identifying the Risks of LM Agents with an LM-Emulated Sandbox](https://mlsanity.com/paper/2309.15817/) (2023)
- [Ray: A Distributed Framework for Emerging AI Applications](https://mlsanity.com/paper/1712.05889/) (2017)
- [Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve](https://mlsanity.com/paper/2403.02310/) (2024)
- [Prompt Cache: Modular Attention Reuse for Low-Latency Inference](https://mlsanity.com/paper/2311.04934/) (2023)
- [AI Agents That Matter](https://mlsanity.com/paper/2407.01502/) (2024)
- [CacheGen: KV Cache Compression and Streaming for Fast Large Language Model Serving](https://mlsanity.com/paper/2310.07240/) (2023)
- [Llumnix: Dynamic Scheduling for Large Language Model Serving](https://mlsanity.com/paper/2406.03243/) (2024)
- [DynamoLLM: Designing LLM Inference Clusters for Performance and Energy Efficiency](https://mlsanity.com/paper/2408.00741/) (2024)
- [Parrot: Efficient Serving of LLM-based Applications with Semantic Variable](https://mlsanity.com/paper/2405.19888/) (2024)
- [BurstGPT: A Real-world Workload Dataset to Optimize LLM Serving Systems](https://mlsanity.com/paper/2401.17644/) (2024)
- [Efficient LLM Scheduling by Learning to Rank](https://mlsanity.com/paper/2408.15792/) (2024)
- [ServerlessLLM: Low-Latency Serverless Inference for Large Language Models](https://mlsanity.com/paper/2401.14351/) (2024)
- [Fairness in Serving Large Language Models](https://mlsanity.com/paper/2401.00588/) (2023)
- [Autellix: An Efficient Serving Engine for LLM Agents as General Programs](https://mlsanity.com/paper/2502.13965/) (2025)
- [KVFlow: Efficient Prefix Caching for Accelerating LLM-Based Multi-Agent Workflows](https://mlsanity.com/paper/2507.07400/) (2025)
- [Themis: Fair and Efficient GPU Cluster Scheduling](https://mlsanity.com/paper/1907.01484/) (2019)
- [Online Scheduling for LLM Inference with KV Cache Constraints](https://mlsanity.com/paper/2502.07115/) (2025)

## Built on by (most cited first, 6 of 6)

- [Agentic Coding in the Wild: Characterizing GitHub Copilot Traces at Production Scale](https://mlsanity.com/paper/2608.00101/) (2026)
- [AgentServeSim: Serving-System Simulation and Policy Search for LLM Agent Programs](https://mlsanity.com/paper/2606.09613/) (2026)
- [Agents in the Large: Perception-Centered Architecture for Persistent Agents](https://mlsanity.com/paper/2608.30478/) (2026)
- [Ready Cohorts: Bounding GPU Opportunity and Avoiding Host Round Trips in LLM-Agent Control](https://mlsanity.com/paper/2608.12123/) (2026)
- [Towards Agentic Cloud Engineering: Graph and Loop Engineering with a Zero-Trust Agent Harness](https://mlsanity.com/paper/2609.00050/) (2026)
- [Exact Memory-Time Optimization for Prefix-Cached Language Model Serving](https://mlsanity.com/paper/2610.02766/) (2026)

## Abstract (arXiv)

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'el'ady'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.