sagagpu-schedulingai-agentscompound-aikv-cachevllmllm-servingtutorial

SAGA Guide: Workflow-Atomic GPU Scheduling for AI Agents

October 17, 2026

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

The Problem: The Request-Level Mismatch in AI Agent GPU Clusters

In enterprise software engineering, automated desktop workflows, and complex research agents orchestrated by AI Fetchly, autonomous intelligence has shifted from isolated, single-turn prompts toward compound AI systems. Agents do not simply emit one answer; they execute iterative Thought-Action-Observation loops (such as ReAct loops or tree-search rollouts) that invoke tens to hundreds of chained Large Language Model (LLM) inference calls interleaved with external tool executions.

Whether an autonomous coding agent is running tests across an iterative debugging loop or a browser agent is executing autonomous web scraping pipelines alongside real-time data fetching, agents alternate continuously between GPU-bound model inference and external I/O-bound tool invocations.

However, modern GPU serving infrastructure—spearheaded by engines like vLLM, SGLang, and TensorRT-LLM—was architected around a fundamentally different paradigm: request-level scheduling. Current serving engines treat every HTTP inference call as an independent, isolated, memoryless request.

When applied to multi-step agent workloads, this request-level abstraction creates catastrophic inefficiencies across production GPU clusters.

The Request-Level Scheduling Breakdown in Compound AI:
Agent Task: Iterative Code Refactoring & Testing
┌────────────────────────────────────────────────────────────────────────┐
│ Step 1: LLM Inference (Generate code patch)                            │
│ ├── Input: System prompt + repo context (24k tokens)                   │
│ └── GPU allocates ~8GB KV Cache in High-Bandwidth Memory (HBM)         │
├────────────────────────────────────────────────────────────────────────┤
│ Tool Call: Execute Compiler & Test Suite (Takes 2.4 seconds)           │
│ ❌ Standard vLLM Scheduler: Sees no active GPU queries                 │
│ ❌ Request-Level LRU Eviction: Deallocates or evicts session KV cache!  │
├────────────────────────────────────────────────────────────────────────┤
│ Step 2: LLM Inference (Inspect compiler error & fix bug)               │
│ ├── Input: Accumulated history + error log (28k tokens)                │
│ ❌ Cache Miss! GPU must recompute all 24k prior tokens from scratch!   │
│ ❌ Severe Prefill Overhead: Wastes 1,200ms re-running identical GEMMs  │
└────────────────────────────────────────────────────────────────────────┘
Result: 38% of total cluster execution time is wasted regenerating cache!

1. The High Cost of Discarded Intermediate KV Cache

During autoregressive generation, a 70B-parameter model running Grouped-Query Attention (GQA) accumulates between 2GB and 12GB of Key-Value (KV) cache per active stream across 32k to 128k context windows.

Under standard request-level serving:

The inference engine terminates the session context the moment the model outputs a tool-call token (e.g., execute_bash("pytest")).
During the subsequent 200ms to 30-second tool execution window, the GPU treats the session memory as dead weight.
When the agent sends the tool output back into the cluster for Step 2, the scheduler treats it as a brand-new incoming query, forcing the GPU to recompute the entire prompt prefix from scratch.

Measurements across 32-GPU clusters serving real-world agent workloads (such as SWE-bench) reveal that agents spend 38% of their total execution time purely regenerating KV cache that was discarded during tool calls.

2. GPU High-Bandwidth Memory (HBM) Underutilization

Because current schedulers cannot anticipate when an external tool will complete, they manage GPU High-Bandwidth Memory (HBM) conservatively.

To prevent sudden Out-Of-Memory (OOM) crashes caused by unpredictable concurrent prefills, serving engines maintain massive safety headroom buffers:

Fragmented Allocations: In standard vLLM clusters serving agent workloads, GPU memory utilization averages only 42%. Over half of available High-Bandwidth Memory sits idle, yet the scheduler refuses to accept new workflows.
Prefix Caching Limitations: While techniques like Automatic Prefix Caching (APC in vLLM) or RadixAttention in SGLang retain static prompt prefixes, their eviction policies rely on recency (LRU). They routinely evict paused agent sessions (which will resume in 500ms) to accommodate transient background requests, creating pervasive cache thrashing.

3. Tail Latency Explosion and Scheduling Starvation

AI agent workloads violate the two foundational assumptions of GPU serving:

Assumption of Independence: Requests within an agent session share deep causal dependencies; delaying step 3 stalls the entire end-to-end task.
Assumption of Poisson Arrivals: Tool invocations exhibit heavy-tailed latency distributions. Local file edits complete in 45ms, while web API calls or test suites take over 30 seconds.

Under standard FIFO or continuous batching, short interactive queries get trapped behind massive, multi-iteration agent loops, while multi-step agents suffer from unbounded tail latency (Time-to-Task-Completion).

To dismantle these compounding bottlenecks, researchers from The University of Hong Kong and industry collaborators introduced SAGA (arXiv:2605.00528, presented at HPDC 2026).

The Solution: SAGA and Workflow-Atomic GPU Scheduling

SAGA introduces a fundamental architectural paradigm shift: Program-as-Unit Scheduling.

Instead of treating individual LLM queries as independent, disposable requests, SAGA elevates the entire agent workflow to the first-class schedulable unit across the distributed GPU cluster.

The SAGA Workflow-Atomic Scheduling Paradigm:
┌────────────────────────────────────────────────────────────────────────┐
│ SAGA: Workflow-Atomic Cluster Architecture                             │
├────────────────────────────────────────────────────────────────────────┤
│ [Incoming Agent Workflow] (LangChain, AutoGen, CrewAI, Custom Agents)  │
│        │                                                               │
│        ▼                                                               │
│ ┌────────────────────────────────────────────────────────────────────┐ │
│ │ LAYER 1: AGENT INTERFACE LAYER                                     │ │
│ │ • Parses multi-step logic into Agent Execution Graphs (AEGs)       │ │
│ │ • Models transition probabilities & tool-call duration profiles    │ │
│ └─────────────────────────────────┬──────────────────────────────────┘ │
│                                   │ Atomic AEG Task Descriptor         │
│                                   ▼                                    │
│ ┌────────────────────────────────────────────────────────────────────┐ │
│ │ LAYER 2: GLOBAL SCHEDULER                                          │ │
│ │ • Session-Affinity Router: Co-locates steps to retain cache locality│ │
│ │ • Work Stealing Engine: Eliminates stragglers without cache thrash │ │
│ │ • Agent Fair Share (AFS): Enforces task-completion-time fairness   │ │
│ └─────────────────────────────────┬──────────────────────────────────┘ │
│                                   │ Coordinated Dispatch               │
│                                   ▼                                    │
│ ┌────────────────────────────────────────────────────────────────────┐ │
│ │ LAYER 3: EXTENDED GPU WORKER POOL                                  │ │
│ │ • Workflow-Aware LRU (WA-LRU): Retains cache across tool idle gaps │ │
│ │ • Tool-Call-Aware TTL: Bounded retention matching tool percentiles │ │
│ │ • Speculative Prefetching: Pre-loads next-step KV before tool ends │ │
│ └────────────────────────────────────────────────────────────────────┘ │
│        │                                                               │
│        ▼                                                               │
│ [Quantified Systems Payoff]:                                           │
│ ✔ Task Completion Time: 1.64x faster (vs vLLM+APC) / 3.01x (vs vLLM)  │
│ ✔ Cache Regeneration Time: Slashed from 38% down to 8%                 │
│ ✔ GPU Memory Utilization: Elevated from 42% up to 71%                  │
│ ✔ Multi-Tenant SLO Attainment: 99.2% under heavy cluster contention    │
└────────────────────────────────────────────────────────────────────────┘

SAGA addresses the compound AI serving bottleneck through four foundational systems innovations:

Agent Execution Graphs (AEGs): Models agent execution as directed dependency graphs, projecting future KV cache reuse across variable-duration tool boundaries.
Workflow-Aware LRU (WA-LRU): An eviction policy that proves to operate within 1.31x of Bélády’s optimal offline cache policy, preserving active session states during tool execution.
Session-Affinity Batching with Work Stealing: Routes sequential steps of an agent to the same GPU worker to maximize cache hits, while using randomized work stealing to balance cluster-wide load.
Agent Fair Share (AFS): A task-completion-time fairness scheduler backed by Lyapunov drift analysis, providing provable bounded-delay guarantees across multi-tenant clusters.

Architecture: The Three Pillars of SAGA

The SAGA architecture coordinates distributed serving across three tightly integrated layers: the Agent Interface Layer, the Global Coordinator, and the Extended Worker Pool.

Detailed SAGA System Topology:
┌──────────────────────────────────────────────────────────────────────────────┐
│ PILLAR 1: AGENT EXECUTION GRAPHS (AEG) & WA-LRU CACHE MANAGEMENT             │
│ • Graph Nodes: LLM inference iterations v_i                                  │
│ • Directed Edges: Transition probabilities P(v_i -> v_j)                     │
│ • Tool Metadata: Tool type φ(v) and historical latency distributions         │
│ • WA-LRU Eviction Score:                                                     │
│     P_evict(s) = α * R_norm(s) + β * (1 - P_reuse(s)) + γ * S_norm(s)       │
│ • Cache Preservation: Retains 12k-64k token context across tool boundaries   │
└──────────────────────────────────────┬───────────────────────────────────────┘
                                       │
                                       ▼
┌──────────────────────────────────────────────────────────────────────────────┐
│ PILLAR 2: SESSION-AFFINITY BATCHING & RANDOMIZED WORK STEALING               │
│ • Affinity Routing: Maps session hash h(session_id) to primary GPU worker    │
│ • Soft Memory Threshold (θ_low = 0.7): Retains idle sessions in HBM          │
│ • Hard Memory Threshold (θ_high = 0.9): Evicts lowest P_reuse sessions       │
│ • Work Stealing: Idle worker steals pending steps when queue is empty,        │
│   migrating KV metadata via zero-copy NVLink transfers                       │
└──────────────────────────────────────┬───────────────────────────────────────┘
                                       │
                                       ▼
┌──────────────────────────────────────────────────────────────────────────────┐
│ PILLAR 3: AGENT FAIR SHARE (AFS) MULTI-TENANT ARBITRATION                   │
│ • Evaluates expected task completion time (TCT) across compound agents       │
│ • Priority Deficit Metric: D_k(t) = TCT_actual(k) - TCT_fair_target(k)       │
│ • Lyapunov Drift Optimization: Minimizes global completion delay variance    │
│ • Preemption Safeguard: Migrating sessions carry workflow-aware TTL tags     │
└──────────────────────────────────────────────────────────────────────────────┘

Pillar 1: Agent Execution Graphs and Workflow-Aware Eviction (WA-LRU)

The core scientific breakthrough of SAGA is demonstrating that surfacing workflow structure to the GPU scheduler brings online cache management within 1.31x of the offline-optimal Bélády policy.

Defining the Agent Execution Graph (AEG) An agent workflow is formalized as a directed graph $G = (V, E, P, \phi)$:

$V$: Set of nodes representing distinct LLM inference steps.
$E \subseteq V \times V$: Directed edges representing execution transitions.
$P: E \to [0, 1]$: Transition probabilities between steps.
$\phi: V \to \mathcal{T}$: Mapping of each step to its corresponding tool invocation (e.g., code execution, web fetch, SQL query).

For standard ReAct agents, the AEG forms an iterative chain with forward transition probability $P(v_i \to v_{i+1}) \approx 1 - p_{\text{term}}$. For tree-of-thought or multi-agent planning frameworks, the AEG captures branching and retry loops.

Concrete AEG for an Iterative Autonomous Coding Agent:
[v0: Read File] ──(P=0.95, 45ms)──► [v1: Edit Code] ──(P=0.85, 180ms)──► [v2: Run Test Suite]
      ▲                                                                          │
      │                                                                   (P=0.40, 2.4s)
      └───────────────────────── [Retry Loop: Fix Bug] ◄─────────────────────────┘
                                         │ (P=0.60)
                                         ▼
                                   [v3: Commit & Finish] (Terminal)
[SAGA Action]: Preserves 24k token KV cache across the 2.4s test execution window!

The WA-LRU Eviction Metric Standard LRU eviction only tracks recency $t_{\text{now}} - t_{\text{last}}$, which mistakenly evicts a paused agent waiting for a test suite to run in favor of a completed session.

SAGA introduces Workflow-Aware LRU (WA-LRU), which calculates an eviction score $P_{\text{evict}}(s)$ for each session $s$:

$$P_{\text{evict}}(s) = \alpha \cdot \hat{R}(s) + \beta \cdot (1 - P_{\text{reuse}}(s)) + \gamma \cdot \hat{S}(s)$$

Where:

$\hat{R}(s) = \frac{t_{\text{now}} - t_{\text{last}}(s)}{\tau_{\text{max}}}$ is normalized recency.
$\hat{S}(s) = \frac{\text{size}(s)}{\text{size}_{\text{max}}}$ is normalized memory footprint.
$P_{\text{reuse}}(s)$ is the predicted reuse probability calculated from the AEG:

$$P_{\text{reuse}}(s) = \sum_{u \in \text{succ}(v_s)} P(v_s \to u) \cdot \text{overlap}(s, u)$$

The overlap function estimates prefix token intersection between the current cache and the expected input of successor step $u$:

$$\text{overlap}(s, u) = \frac{|\text{prefix}(s) \cap \text{prefix}_{\text{est}}(u)|}{|\text{prefix}(s)|}$$

By prioritizing eviction of sessions with low $P_{\text{reuse}}$, SAGA retains high-value intermediate states across heavy-tailed tool pauses.

Pillar 2: Tool-Call-Aware TTL and Speculative Prefetching

Tool executions introduce variable idle intervals. As established in production traces:

File operations: $P_{50} = 45\text{ms}, P_{99} = 1,200\text{ms}$.
Local code compilation: $P_{50} = 180\text{ms}, P_{99} = 28,000\text{ms}$.
External web/API calls: $P_{50} = 850\text{ms}, P_{99} = 45,000\text{ms}$.

Rather than relying on fixed expiration timers, SAGA assigns a dynamic Time-To-Live (TTL) horizon to each paused session:

$$\text{TTL}(s) = \min\left( \text{CDF}{\text{tool}}^{-1}(0.95), , \text{TTL}{\text{max}} \right)$$

If the GPU memory pressure remains below a soft threshold ($\theta_{\text{low}} = 0.70$), the session cache is preserved indefinitely. If memory pressure crosses $\theta_{\text{low}}$, sessions exceeding their predicted tool $P_{95}$ latency are evicted first.

Furthermore, SAGA implements Speculative Prefetching: when a long-running tool call (e.g., web scraping) approaches its expected completion time, SAGA begins prefetching the predicted tool prompt prefix from host DRAM into GPU HBM, masking prefill latency entirely.

In distributed GPU clusters, routing consecutive steps of the same agent to different physical nodes destroys cache locality. SAGA’s global coordinator enforces:

Session-Affinity Routing: Hashes session identifiers to anchor an agent’s execution to a designated GPU worker node. Subsequent iterations automatically route to the worker already hosting the resident KV cache.
Work Stealing with Locality Thresholds: If a worker becomes idle while neighboring nodes experience request spikes, the idle worker initiates randomized work stealing. Stealing is gated by both an idle-time threshold ($T_{\text{idle}} = 100\text{ms}$) and a load-ratio threshold ($R_{\text{max}} = 2.0$), preventing thrashing between load balancing and cache locality.
Agent Fair Share (AFS): Traditional cluster schedulers guarantee fairness at the individual token or request level. In compound AI, this penalizes multi-step agents. SAGA defines fairness based on normalized task completion time (TCT), using Lyapunov drift queues to ensure that complex 50-step workflows receive fair cluster allocation without starving short interactive requests.

End-to-End Implementation: Building a Workflow-Atomic Scheduler

Below is a self-contained, production-grade Python implementation of SAGA’s core scheduling components: the Agent Execution Graph, the WA-LRU Cache Manager, and the Session-Affinity Batching Engine.

Step 1: Defining the Agent Execution Graph and Memory Slot Schemas

#!/usr/bin/env python3
"""
SAGA: Workflow-Atomic Scheduler for AI Agent Inference
Implements Agent Execution Graphs (AEGs), Workflow-Aware LRU (WA-LRU),
tool-call-aware TTL prediction, and session-affinity dispatch.
"""

from enum import Enum
from typing import Dict, List, Set, Tuple, Optional
import time
import math
from pydantic import BaseModel, Field

class ToolType(str, Enum):
    FILE_IO = "file_io"
    CODE_EXEC = "code_exec"
    WEB_API = "web_api"
    DB_QUERY = "db_query"

class ToolLatencyProfile:
    # Empirical latency distributions in seconds: (P50, P95, P99)
    PROFILES = {
        ToolType.FILE_IO: (0.045, 0.320, 1.200),
        ToolType.CODE_EXEC: (0.180, 2.400, 28.00),
        ToolType.WEB_API: (0.850, 4.500, 45.00),
        ToolType.DB_QUERY: (0.120, 0.890, 3.500),
    }

    @classmethod
    def get_p95_ttl(cls, tool: ToolType) -> float:
        return cls.PROFILES[tool][1]

class Node(BaseModel):
    step_id: int
    name: str
    tool_type: Optional[ToolType] = None
    expected_tokens: int = 2048

class Edge(BaseModel):
    source_id: int
    target_id: int
    transition_prob: float = 1.0
    prefix_overlap: float = 0.85

class AgentExecutionGraph(BaseModel):
    workflow_id: str
    nodes: Dict[int, Node] = Field(default_factory=dict)
    edges: List[Edge] = Field(default_factory=list)

    def get_successors(self, node_id: int) -> List[Tuple[Node, float, float]]:
        successors = []
        for e in self.edges:
            if e.source_id == node_id and e.target_id in self.nodes:
                successors.append((self.nodes[e.target_id], e.transition_prob, e.prefix_overlap))
        return successors

    def calculate_reuse_probability(self, current_node_id: int) -> float:
        successors = self.get_successors(current_node_id)
        if not successors:
            return 0.0
        # P_reuse = sum(P(v -> u) * overlap(v, u))
        return sum(prob * overlap for _, prob, overlap in successors)

Step 2: The Workflow-Aware LRU (WA-LRU) Cache Manager

class CacheSlot(BaseModel):
    session_id: str
    workflow_id: str
    current_node_id: int
    cached_tokens: int
    allocated_bytes: int
    last_accessed: float
    is_paused: bool = False
    paused_at: float = 0.0
    expected_ttl: float = 5.0

class WALRUCacheManager:
    def __init__(
        self,
        total_gpu_memory_bytes: int = 80 * (1024 ** 3),  # 80 GB A100 HBM
        alpha: float = 0.3,   # Recency weight
        beta: float = 0.5,    # Reuse probability weight
        gamma: float = 0.2,   # Size weight
        soft_threshold: float = 0.70,
        hard_threshold: float = 0.90
    ):
        self.total_bytes = total_gpu_memory_bytes
        self.used_bytes = 0
        self.slots: Dict[str, CacheSlot] = {}
        self.aeg_registry: Dict[str, AgentExecutionGraph] = {}
        self.alpha = alpha
        self.beta = beta
        self.gamma = gamma
        self.soft_threshold = soft_threshold
        self.hard_threshold = hard_threshold

    def register_aeg(self, aeg: AgentExecutionGraph) -> None:
        self.aeg_registry[aeg.workflow_id] = aeg

    def allocate(self, session_id: str, workflow_id: str, node_id: int, tokens: int) -> bool:
        bytes_needed = tokens * 128 * 2 * 2  # Approx 512 bytes per token in FP16 GQA

        # Check if eviction is necessary
        while (self.used_bytes + bytes_needed) > (self.total_bytes * self.hard_threshold):
            evicted = self._evict_one_slot()
            if not evicted:
                return False  # Cache completely saturated with pinned requests

        slot = CacheSlot(
            session_id=session_id,
            workflow_id=workflow_id,
            current_node_id=node_id,
            cached_tokens=tokens,
            allocated_bytes=bytes_needed,
            last_accessed=time.time()
        )
        self.slots[session_id] = slot
        self.used_bytes += bytes_needed
        return True

    def mark_tool_pause(self, session_id: str, tool_type: ToolType) -> None:
        """Marks session as waiting on an external tool and assigns bounded TTL."""
        if session_id in self.slots:
            slot = self.slots[session_id]
            slot.is_paused = True
            slot.paused_at = time.time()
            slot.expected_ttl = ToolLatencyProfile.get_p95_ttl(tool_type)

    def mark_resumed(self, session_id: str, next_node_id: int) -> None:
        """Restores active status when tool completes."""
        if session_id in self.slots:
            slot = self.slots[session_id]
            slot.is_paused = False
            slot.current_node_id = next_node_id
            slot.last_accessed = time.time()

    def _evict_one_slot(self) -> bool:
        """Evaluates WA-LRU scores and evicts the lowest-priority session."""
        if not self.slots:
            return False

        now = time.time()
        max_idle = max((now - s.last_accessed for s in self.slots.values()), default=1.0)
        max_size = max((s.allocated_bytes for s in self.slots.values()), default=1.0)

        best_candidate: Optional[str] = None
        highest_eviction_score = -1.0

        for sid, slot in self.slots.items():
            # If session is paused on a tool, check if it exceeded predicted TTL
            if slot.is_paused:
                idle_duration = now - slot.paused_at
                # Heavily penalize eviction if tool call is still within its P95 window
                if idle_duration < slot.expected_ttl:
                    continue

            # Calculate normalized terms
            r_norm = (now - slot.last_accessed) / max(1.0, max_idle)
            s_norm = slot.allocated_bytes / max(1.0, max_size)

            # Retrieve reuse probability from AEG
            aeg = self.aeg_registry.get(slot.workflow_id)
            p_reuse = aeg.calculate_reuse_probability(slot.current_node_id) if aeg else 0.1

            # WA-LRU Eviction Score Formula:
            # P_evict = α * R_norm + β * (1 - P_reuse) + γ * S_norm
            score = (self.alpha * r_norm) + (self.beta * (1.0 - p_reuse)) + (self.gamma * s_norm)

            if score > highest_eviction_score:
                highest_eviction_score = score
                best_candidate = sid

        if best_candidate:
            evicted_slot = self.slots.pop(best_candidate)
            self.used_bytes -= evicted_slot.allocated_bytes
            print(f"[WA-LRU EVICT] Session '{best_candidate}' evicted | Freed {evicted_slot.allocated_bytes / (1024**2):.1f} MB")
            return True

        return False

Step 3: Session-Affinity Cluster Coordinator and Simulation

class SAGAClusterCoordinator:
    def __init__(self, num_gpu_workers: int = 4):
        # Initialize worker cache managers (representing 4x 80GB A100 GPUs)
        self.workers = [WALRUCacheManager() for _ in range(num_gpu_workers)]
        self.session_to_worker: Dict[str, int] = {}

    def route_request(self, session_id: str, workflow_id: str, node_id: int, tokens: int) -> int:
        """Session-affinity routing: Anchors session to the same GPU worker."""
        if session_id in self.session_to_worker:
            worker_id = self.session_to_worker[session_id]
        else:
            # Hash-based affinity initial assignment
            worker_id = hash(session_id) % len(self.workers)
            self.session_to_worker[session_id] = worker_id

        worker = self.workers[worker_id]
        success = worker.allocate(session_id, workflow_id, node_id, tokens)

        # Work-stealing fallback if primary worker is saturated
        if not success:
            print(f"[WORK STEAL] Worker {worker_id} saturated. Stealing session {session_id}...")
            for alt_id, alt_worker in enumerate(self.workers):
                if alt_worker.allocate(session_id, workflow_id, node_id, tokens):
                    self.session_to_worker[session_id] = alt_id
                    return alt_id
            raise RuntimeError("Cluster GPU memory completely exhausted!")

        return worker_id

def run_saga_simulation():
    print("=== Initializing SAGA Cluster Simulation ===")
    coordinator = SAGAClusterCoordinator(num_gpu_workers=2)

    # 1. Build an Agent Execution Graph (AEG) for a Coding Agent
    aeg = AgentExecutionGraph(workflow_id="swe_coding_agent")
    aeg.nodes = {
        0: Node(step_id=0, name="Analyze Issue", expected_tokens=8192),
        1: Node(step_id=1, name="Read Repo Files", tool_type=ToolType.FILE_IO, expected_tokens=16384),
        2: Node(step_id=2, name="Generate Patch", tool_type=ToolType.CODE_EXEC, expected_tokens=24576),
        3: Node(step_id=3, name="Run Pytest Suite", tool_type=ToolType.CODE_EXEC, expected_tokens=28672),
        4: Node(step_id=4, name="Commit Changes", expected_tokens=32768)
    }
    aeg.edges = [
        Edge(source_id=0, target_id=1, transition_prob=0.98, prefix_overlap=0.90),
        Edge(source_id=1, target_id=2, transition_prob=0.92, prefix_overlap=0.88),
        Edge(source_id=2, target_id=3, transition_prob=0.85, prefix_overlap=0.95),
        Edge(source_id=3, target_id=4, transition_prob=0.70, prefix_overlap=0.92),
    ]

    for w in coordinator.workers:
        w.register_aeg(aeg)

    # 2. Simulate Step 1: Initial Prompt and Patch Generation
    session_id = "agent_session_101"
    assigned_worker = coordinator.route_request(session_id, "swe_coding_agent", node_id=2, tokens=24576)
    print(f"[STEP 1] Session {session_id} scheduled on GPU Worker {assigned_worker}")

    # 3. Simulate Tool Execution: Running Test Suite (2.4s pause)
    worker = coordinator.workers[assigned_worker]
    worker.mark_tool_pause(session_id, ToolType.CODE_EXEC)
    print(f"[TOOL PAUSE] Session waiting for Pytest suite (Tool TTL: {ToolLatencyProfile.get_p95_ttl(ToolType.CODE_EXEC)}s)")
    time.sleep(0.5)

    # 4. Simulate Step 2: Session Resumption
    worker.mark_resumed(session_id, next_node_id=3)
    same_worker = coordinator.route_request(session_id, "swe_coding_agent", node_id=3, tokens=28672)
    print(f"[STEP 2] Session resumed on Worker {same_worker} | Cache hit preserved!")
    print(f"[STATUS] Task completed without regenerating 24k tokens of prior context!")

if __name__ == "__main__":
    run_saga_simulation()

Benchmark Comparison: SAGA vs. SOTA Serving Frameworks

SAGA was evaluated on an 8-node cluster equipped with 64 NVIDIA A100-80GB GPUs (connected via NVLink intra-node and 200Gbps InfiniBand inter-node), running two major compound AI workloads: SWE-bench (500 real-world software engineering tasks) and WebArena (812 interactive multi-website browsing tasks).

Below is the comparative performance breakdown contrasting SAGA against frontier serving runtimes:

1. End-to-End Task Completion Time (TCT) Acceleration

Serving Framework	Scheduling Unit	Cache Management Strategy	SWE-bench Speedup	WebArena Speedup	Geometric Mean Speedup
Vanilla vLLM (v0.6.0)	Request-Level	Baseline PagedAttention	Baseline (1.00x)	Baseline (1.00x)	1.00x
vLLM + APC (v0.15.1)	Request-Level	Automatic Prefix Caching (LRU)	1.74x	1.40x	1.56x
SGLang (v0.4.0)	Request-Level	RadixAttention Prefix Tree	1.58x	1.28x	1.42x
Llumnix (OSDI ‘24)	Request-Level	Reactive KV Cache Migration	1.23x	1.14x	1.18x
TensorRT-LLM	Request-Level	Static Chunked Caching	1.88x	1.50x	1.68x
KVFlow (NeurIPS ‘25)	Step-Level	Workflow Step-Aware Eviction	2.05x	1.64x	1.83x
SAGA (Ours vs. vLLM+APC)	Workflow-Atomic	WA-LRU + Tool TTL + Affinity	1.73x ± 0.11	1.55x ± 0.09	1.64x (p \< 0.001)
SAGA (Ours vs. Vanilla vLLM)	Workflow-Atomic	WA-LRU + Tool TTL + Affinity	3.01x ± 0.18	2.17x ± 0.14	2.56x

Against the strongest modern baseline—vLLM v0.15.1 with Automatic Prefix Caching—SAGA reduces task completion time by 1.73x on SWE-bench and 1.55x on WebArena (geometric mean: 1.64x, $p \< 0.001$). Against vanilla vLLM without workflow awareness, SAGA achieves a 3.01x speedup.

2. Cache Eviction Competitive Ratio vs. Offline-Optimal Bélády

To measure caching efficiency, the authors compared eviction policies against the theoretical upper bound—Bélády’s optimal offline algorithm (which possesses perfect future knowledge of all token accesses):

Eviction Policy	SWE-bench Competitive Ratio	WebArena Competitive Ratio	Cluster Mean Ratio ($\downarrow$)
Standard Request LRU	2.84x	2.12x	2.48x
LRU + Prefix (vLLM)	1.97x	1.74x	1.86x
WA-LRU (SAGA)	1.31x	1.28x	1.30x

While standard LRU deviates from optimal performance by 2.48x, SAGA’s WA-LRU operates within 1.30x of Bélády’s optimal ceiling, proving that predicting workflow structure from Agent Execution Graphs is sufficient to achieve near-optimal cache retention.

3. Multi-Tenant SLO Attainment Under Cluster Contention

In multi-tenant environments where heavy agent workflows run alongside lightweight interactive queries:

Cluster Serving Engine	Heavy Agents SLO	Medium Agents SLO	Light Interactive SLO	Overall SLO Attainment
vLLM	89.4%	72.1%	43.2%	67.3%
SGLang	91.2%	78.6%	51.4%	73.4%
Llumnix	92.8%	81.3%	58.9%	77.2%
SAGA (AFS Scheduling)	99.1%	99.4%	98.7%	99.2%

By incorporating Agent Fair Share (AFS), SAGA guarantees 99.2% overall SLO attainment, preventing long-running agents from starving interactive users.

Production Deployment: Integrating SAGA with Agent Infrastructure

Deploying SAGA across enterprise clusters serving autonomous agents (such as Agent S2 or UI-TARS) requires integrating workflow hooks into agent orchestration frameworks.

Production SAGA Cluster Topology:
┌────────────────────────────────────────────────────────────────────────┐
│ Enterprise Agent Orchestration Layer                                  │
│ ┌────────────────────────────────────────────────────────────────────┐ │
│ │ Agent Frameworks (LangChain, AutoGen, CrewAI, Custom Clients)      │ │
│ │ • Exposes workflow DAG hints via OpenTelemetry HTTP headers:       │ │
│ │   X-SAGA-Workflow-ID: "swe_v3" | X-SAGA-Step: 4 | X-SAGA-Tool: "io"│ │
│ └─────────────────────────────────┬──────────────────────────────────┘ │
│                                   │                                    │
│                                   ▼                                    │
│ ┌────────────────────────────────────────────────────────────────────┐ │
│ │ SAGA Global Coordinator Daemon (Kubernetes Control Plane)          │ │
│ │ • Tracks real-time HBM memory pressure via NVML telemetry          │ │
│ │ • Maintains cluster-wide session routing table                     │ │
│ │ • Dispatches Prometheus metrics for SLO monitoring                 │ │
│ └─────────────────────────────────┬──────────────────────────────────┘ │
│                                   │ gRPC Session Dispatch              │
│                                   ▼                                    │
│ ┌────────────────────────────────────────────────────────────────────┐ │
│ │ Distributed vLLM / SGLang Worker Nodes                             │ │
│ │ • Extended with WA-LRU engine inside PagedAttention block manager  │ │
│ │ • Intra-Node: NVLink zero-copy peer memory transfers               │ │
│ │ • Inter-Node: RDMA over Converged Ethernet (RoCE v2) / InfiniBand  │ │
│ └────────────────────────────────────────────────────────────────────┘ │
└────────────────────────────────────────────────────────────────────────┘

1. Instrumenting Agent Frameworks with AEG Hints

SAGA achieves maximum performance when orchestration frameworks pass lightweight workflow metadata:

Framework Callbacks: In LangChain or AutoGen, register an on_tool_start callback that emits the expected tool type (code_exec, web_api, file_io).
Pattern Inference Fallback: If third-party commercial agents cannot pass explicit hints, SAGA’s pattern inference module reconstructs the AEG online from observed request sequences, achieving 87% accuracy with only a 15.6% latency penalty.

2. Throughput vs. Latency Trade-Off Considerations

Systems engineers must recognize that SAGA is engineered specifically for latency-sensitive interactive agent deployments:

The Trade-Off: Because SAGA retains KV cache across tool pauses to slash end-to-end task completion time, it achieves approximately 30% lower raw token throughput than an unconstrained throughput-maximizing batch scheduler that ruthlessly evicts idle sessions.
When to Deploy SAGA: Ideal for interactive coding copilots, real-time desktop GUI agents, and multi-step data extraction pipelines where human developers or downstream services are waiting for task completion.

Similar to how SGLang RadixAttention revolutionizes prefix caching within single requests, SAGA expands structural memory awareness to the entire distributed cluster lifecycle.

Summary and Key Takeaways

The explosive growth of compound AI systems has rendered request-level GPU scheduling obsolete. By treating multi-step agent programs as atomic schedulable units, SAGA bridges the gap between high-level reasoning and physical hardware execution:

Program-as-Unit Abstraction: Eliminates the mismatch between multi-step agent loops and stateless GPU inference engines.
Near-Optimal Cache Eviction: Uses Agent Execution Graphs (AEGs) to achieve within 1.30x of Bélády’s theoretical offline-optimal cache policy.
Drastic Latency Reduction: Reduces end-to-end task completion time by 1.64x over vLLM with Automatic Prefix Caching, slashing cache regeneration overhead from 38% to 8%.
Massive Memory Efficiency: Drives GPU memory utilization from 42% to 71%, unlocking higher cluster density.
Guaranteed Multi-Tenant Fairness: Implements Agent Fair Share (AFS) to deliver 99.2% SLO attainment across heterogeneous workloads.

As AI agents continue to automate complex digital workflows across industry, workflow-atomic systems like SAGA represent the indispensable infrastructure foundation for scalable, high-performance agentic computing.