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

1. TL;DR #

Agent tasks fire 10–100 chained LLM calls, but request-level GPU schedulers discard each session's KV cache across tool calls, inflating latency 3–8×. SAGA makes the whole agent workflow the schedulable unit: workflow-aware eviction (within 1.31× of Bélády), session-affinity batching with work stealing, and a Lyapunov-bounded fairness metric. Result: 1.64× lower task-completion time vs vLLM+APC, 99.2% SLO, at ~30% throughput cost.

2. Q1 / Q2 / Q3 #

Q1 — 痛点 (what breaks). Modern serving stacks (vLLM, SGLang, Orca) optimize request-level metrics (TTFT, throughput) and assume requests are (a) independent and (b) arrive memorylessly. Agent workloads violate both. A ReAct loop's step i+1 depends on step i's output plus a tool observation; between steps the agent idles for a tool call ranging 50 ms → 30+ s. During that idle, current systems evict the session's KV cache (2–12 GB for a 70B GQA model at 32K context), then must re-prefill on resume. Instrumentation on a 32-GPU SWE-bench cluster shows 38% of wall-time spent regenerating discarded cache, 42% average memory utilization, and 6.0× higher end-to-end latency than the sum of individual inference times.

Q2 — 方法 (the fix). Elevate the agent program (not the inference call) to the first-class schedulable unit. SAGA surfaces workflow structure as an Agent Execution Graph (AEG) $G=(V,E,P,\phi)$ and uses it in three coordinating mechanisms: (1) WA-LRU eviction that scores sessions by predicted future reuse from the AEG, plus tool-call-aware TTL; (2) session-affinity batching that co-locates a task's steps on one worker, with randomized work stealing to rebalance; (3) Agent Fair Share (AFS), a completion-time fairness metric with a Lyapunov-drift bound.

核心技术壁垒 (the single hardest-to-replicate insight): the AEG-driven reuse predictor overlap(s,u) (Eq. 4–5) that converts observable workflow structure into a per-session eviction score good enough to land online cache management within 1.31× of Bélády's offline-optimal oracle on production traces. The scientific claim of the paper is precisely this quantified upper bound on what an online scheduler can achieve once the workflow DAG is observable — the first such empirical bound for agent inference. The barrier is not the LRU machinery but the calibrated prefix_est(u) estimate combined with tool-type-specific observation-length EMAs.

Q3 — 结果. On a 64-GPU A100 cluster: 1.73× (SWE-bench) / 1.55× (WebArena) TCT reduction over vLLM+APC v0.15.1, geomean 1.64× ($p<0.001$); up to 3.01× vs vanilla vLLM; 1.22× memory-utilization gain; 99.2% SLO attainment under multi-tenant interference. Cost: ~30% lower peak throughput than throughput-optimal batching.

Agent scope #

• Task class: open-ended — long-horizon coding (SWE-bench, mean 37 / max 150 steps) and browser automation (WebArena, mean 18 steps). Not single-turn RAG.
• Interaction pattern: multi-turn ReAct loops with external tool invocations interleaved between LLM calls.
• Autonomy: fully autonomous per task; SAGA sits below the agent frameworks (LangChain / AutoGen / CrewAI) as a serving-layer scheduler, requiring no changes to agent code.

3. 架构 / 方法图 #

SAGA is a three-layer distributed scheduler. Layer 1 (Agent Interface) captures workflows as AEGs from framework hints or infers them from request streams. Layer 2 (Global Scheduler) routes each AEG as one unit through three engines — Affinity Router, AFS Engine, Work Stealer — sharing a Cluster State (worker loads, KV-cache map, fairness counters). Layer 3 (Worker Pool) runs extended vLLM workers under WA-LRU eviction.

Paper's Figure 2, verbatim (caption: "SAGA architecture. Layer 1 captures workflows from LangChain, AutoGen, and CrewAI as Agent Execution Graphs (AEGs)... Layer 2 routes each AEG as a single schedulable unit through three coordinating engines that share a Cluster State... Layer 3 runs extended vLLM workers under workflow-aware LRU eviction (WA-LRU)...").

This figure is the load-bearing system diagram: notice the dashed state-traffic arrows into Cluster State (bounded staleness = one 100 ms epoch) and the color-coded per-session KV slots in Layer 3, which visualize the cache-continuity property that request-level schedulers lose across tool-call boundaries.

The AEG itself is the pivot abstraction. For a concrete SWE-bench coding agent it is a mostly-linear chain with retry back-edges and per-step tool annotations.

Paper's Figure 3, verbatim (caption: "Concrete AEG for a SWE-bench coding agent. Nodes are LLM inference steps; forward (teal) edges carry transition probabilities, backward (coral) edges encode retry loops... idle durations span 53× (45 ms for read_file versus 2.4 s for run_test), which is precisely the regime where workflow-aware TTL prediction beats fixed-TTL or eager-eviction policies.").

The reader should notice the 53× spread in tool-idle durations across a single task: this variance is exactly why a single fixed TTL fails and why per-tool-type TTL prediction is needed. The teal brace ($v_0$–$v_3$) marks the 12K-token cache span SAGA preserves during idle rather than recomputing on resumption.

The agent loop as SAGA sees it #

• Memory model: short-term = the session KV cache pinned across tool idle by WA-LRU + TTL; there is no long-term vector store — "memory" here is the accumulated LLM context (2–4K → 16–128K tokens) whose KV cache is the scheduled resource. Episodic = historical traces feed transition-probability estimation for pattern inference.
• Tool invocation: each ReAct iteration = one LLM call then one tool execution; tool result (observation) appended to context.
• Error recovery: on AEG misprediction the system detects the mismatch when the actual next request arrives and corrects routing for subsequent steps (errors do not cascade); on TTL expiry the session falls back to a fresh prefill (graceful degradation to standard LRU per Eq. 6).

Planning & reasoning #

• Planning style: the agent's reasoning is ReAct (think-then-act) or tree-of-thought; SAGA does not plan the agent, it observes the resulting AEG. The scheduler's own "planning" is a per-100ms-epoch capacity allocation.
• Decomposition: top-down — the workflow DAG is admitted whole (workflow-atomic dispatch), then decomposed into per-node prefill/decode work estimates.
• Budget: TTL_max = 300 s; tasks span up to 150 steps; work-stealing migration bounded to ~2.3 events/task (max 5 observed).
• Backtracking: retry back-edges in the AEG are modeled as branching probabilities; the scheduler does not undo tool side effects.

4. 作者证明 #

The paper carries two formal results (§6.3 fairness bound, §7.1 competitive ratio; note both are labeled "Theorem 2" — numbering resets per section). This is not purely empirical, so the notation table + checks below apply.

Notation table #

方程物理意义 (load-bearing equations) #

• Eq. 1 — $P_{evict}(s)=\alpha\hat{R}(s)+\beta(1-P_{reuse}(s))+\gamma\hat{S}(s)$: linear weighted eviction priority; the $\beta$ term (workflow-predicted non-reuse) dominates recency, which is the whole departure from LRU.
• Eq. 4 — $P_{reuse}(s)=\sum_{u\in succ(v_s)}P(v_s\rightarrow u)\cdot overlap(s,u)$: expected reusable-cache fraction over the successor distribution, i.e. the AEG turned into a scalar retention signal.
• Eq. 5 — $overlap(s,u)=\frac{|prefix(s)\cap prefix_{est}(u)|}{|prefix(s)|}$; for linear ReAct chains simplifies to $n_{current}/(n_{current}+\hat{n}_{obs})$ with $\hat{n}_{obs}$ from tool-type EMAs.
• Eq. 8 — $AFS_i=\sum_{t\in\mathcal{T}_i}\frac{work_{remain}(t)}{deadline(t)-t_{now}}$: sum of urgency; higher AFS → higher priority.
• Eq. 10 — $Pr[TCT_i\leq(1+\epsilon)\mathbb{E}[TCT_i]]\geq 1-\delta$ with $\epsilon=O(\rho\sqrt{\log(N/\delta)/n})$: TCT concentrates within $(1+\epsilon)$ of expectation, tightening as $1/\sqrt{n}$.
• Eq. 16 — $CR_{empirical}(\text{WA-LRU})\leq 1+\epsilon\cdot k_{max}+O(\sigma_{tool}/TTL_{adaptive})$: overhead = misprediction cost + long-tail TTL underestimate.

6 minimum checks #

1. Dimensional check (Eq. 1): all three terms are dimensionless (normalized to $[0,1]$) and weights sum to 1.0 (0.3+0.5+0.2) — the score is a convex combination, so $P_{evict}\in[0,1]$. ✓
2. Limit check (Eq. 5): if the successor's prompt is entirely the current context ($\hat{n}_{obs}\to 0$), overlap → 1 (full reuse); if the observation dwarfs context ($\hat{n}_{obs}\to\infty$), overlap → 0 (nothing reusable). Behaves correctly at both ends. ✓
3. Sign / drift check (Eq. 12): $\mathbb{E}[(a_i(t+1)-\mu_i)e_i(t)]\leq-\eta e_i(t)^2$ with $\eta>0$ — the drift is strictly restoring; an underserved tenant ($e_i<0$) gets $\mathbb{E}[a_i]>\mu_i$. Sign is consistent with self-correction. ✓
4. Asymptotic check (Eq. 10): $\epsilon\to 0$ as epochs $n\to\infty$ — the fairness bound is only meaningful for long-running multi-tenant load, consistent with the empirical result that AFS matters under contention, not in single-benchmark runs. ✓
5. Complexity check (Observation 1): worst-case naive regeneration $\sum_{j=1}^k jc = O(k^2 c)$ vs workflow-aware $O(c)$; the quadratic-vs-constant gap is what motivates retention and is monotone in step count $k$. ✓
6. Tightness / honesty check (Eq. 16): with $\epsilon=0.13$, $k_{max}=150$ the analytic bound is $1+\epsilon k_{max}\approx 20.5$, but measured CR is 1.31× because $k_{avg}=37$ dominates — the authors explicitly flag the ~16× slack, and label Eq. 16 an expected-case (not worst-case adversarial) ratio. The worst-case remains open. ✓

Success-rate / sweep model: the fairness guarantee (Eq. 10) is validated by the SLO sweep across tenant classes (Table 6); monotonicity holds — light tenants (most starvation-prone) gain most (43.2% → 98.7%). The competitive-ratio claim is validated by a policy sweep (Table 2). Latency budget per turn: coordinator cycle 12.3 ms mean / 28.7 ms P95; AEG construction 45.2 ms; migration 230 ms mean — all small vs 203.4 s mean SWE-bench TCT, so the "interactive" claim holds. Failure modes: the paper names three failure axes — workflow observability, tool-latency tail, and task-duration estimation for novel agents; the dominant one is observability, and WA-LRU plus pattern inference directly target it.

5. 实验与数据 #

The headline end-to-end table drives every downstream claim: SAGA lands lowest TCT and highest memory utilization on both benchmarks against six baselines.



Paper's Table 3, verbatim (caption: "End-to-end performance on agent benchmarks. TCT = Task Completion Time (seconds). Mem = GPU memory utilization (%)... Significance: * p<0.001 ..."). SAGA reaches 203.4 s SWE-bench TCT (vs 352.1 s for the strongest baseline vLLM+APC) at 71.3% memory utilization; the reader should note the strongest baseline is vLLM+KVFlow (298.4 s), so the 1.47× margin over it isolates the value of SAGA's distributed + fairness additions beyond workflow-aware caching alone.

The central scientific result — that observable workflow structure closes most of the gap to the offline oracle — is Table 2.



Paper's Table 2, verbatim (caption: "Competitive ratio of eviction policies against Bélády's optimal offline algorithm on production traces. Lower is better (1.0 = optimal)."). WA-LRU hits 1.30× mean vs 2.48× for standard LRU and 1.86× for prefix caching. This is the number the abstract foregrounds and the one that upper-bounds achievable online performance given AEG observability.

The ablation reveals which lever actually carries the win, and it is not the marquee one.



Paper's Table 4, verbatim (caption: "Ablation study on SWE-bench. Each row removes one component from full system."). Removing session affinity costs +96% TCT — nearly double the +54% from removing workflow-aware eviction. The load-bearing insight for practitioners: co-location dominates, and AFS fairness contributes only +8% here (its value surfaces only under multi-tenant load, below).

Fairness is where the AFS theorem earns its keep — single-benchmark runs hide it, multi-tenant interference exposes it.



Paper's Table 6, verbatim (caption: "SLO attainment (% of tasks meeting deadline) by tenant type."). SAGA holds 98.7–99.4% across heavy/medium/light tenants while vLLM starves light tenants to 43.2% — this is the empirical face of Theorem 2's bounded-deviation guarantee.

The motivation figure quantifies the three inefficiencies the whole design targets.



Paper's Figure 1, verbatim (caption: "Inefficiencies in serving agent workloads with request-level scheduling. (a) Time breakdown: vLLM v0.6.0 spends 38% of execution time regenerating KV cache between agent steps; SAGA reduces this to 8% (−30 pp)... (c) End-to-end latency normalized to inference-only baseline (log scale): vLLM is 6.0×, +APC is 3.5×, SAGA is 1.5× ..."). Panel (c) is the elevator pitch: SAGA gets 4.0× closer to the inference-only ideal than vanilla vLLM.

Where SAGA loses (honest downside rows): in the BFS/DFS strategy comparison, Pure BFS achieves higher throughput (12.4 vs 8.7 tasks/min) — SAGA trades ~30% throughput for its TCT win. And under extreme tool-latency variance (CV=3.0), TCT degrades +53% as TTL-prediction accuracy falls to 71%; production CV is 1.0–1.5, inside the safe band.

6. 论证链 #

Step	Claim (paper-internal)	Support
1	Agent workloads violate the independence + memorylessness assumptions of request-level schedulers (sequential dependency, KV continuity, bursty correlated arrivals).	§1.1 three characteristics; §2.3 two broken assumptions
2	Under those violations, discarding KV cache across tool calls wastes 38% of wall-time and holds memory to 42%, inflating latency 6.0×.	§1.1 instrumentation; Fig 1
3	Making the workflow the schedulable unit, surfaced as an AEG, lets an online policy predict cross-step reuse.	§3.2 AEG definition; Eq. 4–5
4	With that prediction, WA-LRU eviction reaches within 1.31× of Bélády's offline optimum (Eq. 16 bound; Table 2 empirics).	§7.1 Theorem; Table 2
5	Co-locating a task's steps via session affinity + work stealing preserves the retained cache while keeping the cluster balanced (util 23–94% → 68–79%).	§5.1–5.2; §9.5
6	Allocating capacity by urgency (AFS) yields a Lyapunov-drift bound on completion-time deviation, giving 99.2% SLO under multi-tenant load.	§6.3 Theorem 2; Table 6
7	Together these reduce TCT 1.64× geomean vs the strongest baseline, at ~30% throughput cost — the right trade for interactive deployments.	§9.2 Table 3; §9.8 Table 8

7. 实现 cross-reference #

The artifact is described but the code is [实现未公开] — no repository or file:line references are given in the source. Implementation facts from §8:

• ~8.5K lines Python + 1.2K lines C++/CUDA, extending vLLM v0.6.0 (V1 engine), four components: Workflow Analyzer, Distributed Scheduler (on Ray + gRPC, P99 worker↔coordinator < 5 ms), KV Cache Manager (extends PagedAttention with WA-LRU + TTL + speculative prefetch on separate CUDA streams), and Fairness Module.
• Runs as a standalone interception service — no agent-code modifications required; framework annotations are optional and only improve inference accuracy.

核心技术壁垒 (elaboration). The hardest part to reproduce is not the WA-LRU scoring arithmetic but the calibration of overlap(s,u) / prefix_est(u): getting the expected-observation-length estimate $\hat{n}_{obs}$ right per tool type (via EMAs) is what makes $P_{reuse}$ predictive enough to hit 1.31× of Bélády. A naive reimplementation with a fixed observation-length prior would push the competitive ratio back toward the 1.86× prefix-caching regime. This calibration is the single insight that upper-bounds online performance under AEG observability, and it lives entirely in the (unpublished) tool-latency/observation profiling code.

关键实现细节 (easy-to-miss tricks).

1. Fairness preemption preserves cache predictions: when AFS preempts a task, the migrating task carries its WA-LRU/TTL state via Llumnix migration metadata, so the destination worker continues retaining the migrated cache rather than treating it as a fresh entry — without this, fairness and caching would fight each other.
2. Anti-thrashing gating: because the steal trigger $T_{idle}=100$ ms is shorter than mean migration latency (230 ms), work stealing needs three guards — the $R_{max}=2.0\times$ load-ratio guard, post-migration affinity re-pinning (prevents a second migration of the same session), and asynchronous source-side migration with stale-request rejection at acceptance time. Miss any one and the cluster oscillates.