H EX AG EN T: Efficient Agentic LLM Serving via Workflowand Heterogeneity-Aware Scheduling You Peng1∗ , Youhe Jiang1∗ , Wenshuang Li1 , Xu Xu1 , Ke Zhou2 , Jiawei Jiang3 , Chen Wang4 , Binhang Yuan1
arXiv:2605.16637v1 [cs.DC] 15 May 2026
1
HKUST, 2 Webank, 3 Wuhan University, 4 Tsinghua University ∗
Equal contribution
Abstract Agentic LLM applications increasingly execute user requests as multi-step workflows involving planning, tool use, branching, refinement, and synthesis. In such settings, users experience the end-to-end latency of an entire workflow, not the latency of any single LLM call. In this paper, we study how to schedule online agentic workflows across heterogeneous prefill-decode disaggregated LLM serving clusters to efficiently meet workflow-level latency objectives. The problem is challenging because workflow dependencies are revealed incrementally at runtime, calls have heterogeneous prompts, outputs, and KV-cache requirements, and the prefill and decode stages impose different compute, memory, and transfer constraints across heterogeneous GPUs. To solve this problem, we present H EX AG EN T, a workflow-aware scheduler for a heterogeneous prefill-decode inference service. H EX AG EN T models each request as an online-revealed DAG, maintains a running estimate of the workflow’s standalone completion horizon, prioritizes ready calls by projected risk of missing that horizon, and jointly selects prefill placement, decode placement, and local queue priority while accounting for KV-cache capacity and cross-stage transfer latency. Across representative agentic workloads and heterogeneous A100/H100/H200 clusters, H EX AG EN T reduces the SLO scale required for timely workflow completion by an average of 20.1% at 95% attainment and 33.0% at 99% attainment, with maximum reductions of 45.0% and 80.5%, respectively.
1
Introduction
Large language models are increasingly deployed not as isolated single-turn services, but as components inside agentic workflows: multi-step executions in which an agent plans [49, 50], invokes tools [37, 50], refines intermediate outputs [27], branches into parallel sub-tasks [3, 49], and eventually synthesizes a final response. For example, ReAct-style [50] agents interleave reasoning with external actions, LATS-style [56] agents introduce tree-search structure, and function-calling benchmarks such as BFCL [32] make clear that tool use and multi-step execution are now central to practical LLM applications. As a result, a single user request often expands into a multi-call workflow whose latency is determined by interactions among many dependent LLM calls rather than by any single call in isolation. This shift changes the fundamental unit of serving. Users do not experience the latency of an individual LLM call in isolation—they experience the end-to-end completion time of the entire workflow. In this paper, we explore how we should schedule agentic workflows over one state-of-the-art economic LLM serving infrastructure (i.e., prefill-decode disaggregated deployment over heterogeneous compute resources) so that the entire workflow, rather than its individual calls, completes within an optimal end-to-end latency target.
1
Addressing this problem directly benefits various agentic LLM workflows by improving performance and economic efficiency. First, agentic AI is rapidly moving into production settings: McKinsey’s 2025 survey [29] reports that 23% of organizations are already scaling at least one agentic AI system and another 39% are experimenting with them, while the broader economic potential of generative AI is measured in the trillions of dollars annually. Second, heterogeneous deployment is economically attractive: in modern LLM serving, prefill and decode stress different hardware resources: prefill is compute-intensive, while decode is memory- and KV-cache-intensive. Prefill–decode disaggregation [31, 55] therefore creates an opportunity to specialize resources, improve utilization, and reduce the cost of serving. This opportunity is particularly important in heterogeneous deployments, where providers may combine multiple GPU generations, e.g., A100, H100, and H200, to reuse existing accelerator fleets while selectively exploiting newer, more capable hardware. If scheduled well, such heterogeneous deployments can improve the economics of agentic serving by delivering workflow-level SLOs without requiring every request to run on the newest or fastest accelerator. However, agentic workflow serving is difficult because the scheduler must reason simultaneously about online uncertainty, heterogeneous resources, and workflow structure. First, the workflow is revealed online with uncertainty: imagining LLM call dependence as a direct acyclic graph (DAG), only source calls are visible at arrival, and downstream calls appear only after their parents complete or tools return, so the scheduler must act under partial information. Second, workflow structure is coupled with resource heterogeneity: calls within the same workflow can have very different prompt lengths, output lengths, and KV-cache demands, while prefill and decode instances may differ substantially in compute speed, memory capacity, and transfer cost. Third, local call-level scheduling objectives can conflict with end-to-end workflow structure—naive call-level policies optimize the wrong target. A policy such as FCFS [21, 51] or queue-length balancing [2] can reduce local waiting time for individual calls, yet still delay the critical path of a workflow and harm end-to-end SLO attainment. As a result, existing LLM-serving systems cannot support agentic workflow serving efficiently and economically. Systems such as vLLM [21] and SGLang [54] provide efficient execution substrates through batching and KV-cache management, but they are primarily designed around individual requests or calls rather than workflow-level SLO objectives. Prefill–decode disaggregated systems such as DistServe [55] and Splitwise [31] improve phase specialization, but they do not directly solve the problem of scheduling dependency-constrained, online-revealed agentic workflows across heterogeneous Prefill–Decode pools. Program-aware systems such as Parrot [24], Hermes [25], Autellix [26], and Continuum [22] move toward application-level scheduling, but existing approaches do not jointly handle online-revealed workflow DAGs, heterogeneous prefill/decode placement, decode-capacity constraints, stage-coupled planning, and asynchronous runtime overheads. Thus, prior work provides important building blocks, but not a scheduler that is simultaneously workflow-aware, heterogeneity-aware, and tightly coupled to disaggregated serving dynamics. We present H EX AG EN T, a workflow-aware scheduler for agentic LLM serving on heterogeneous prefill–decode clusters. H EX AG EN T abstracts each request as an online-revealed DAG and maintains, for every workflow, a running estimate of the standalone completion time implied by the revealed subgraph; this estimate serves as the current planning horizon for the workflow. Ready calls are then prioritized by their projected risk of violating that horizon. To turn this signal into concrete actions, H EX AG EN T jointly chooses prefill placement, decode placement, and local queue priority, while accounting for decode KV-capacity constraints, cross-stage transfer latency, and asynchronous runtime semantics. Concretely, we make the following contributions: • We present a representative case study of agentic workflows to identify the system bottlenecks. We characterize why per-call serving policies are insufficient for agentic workloads and show that workflowlevel ordering and heterogeneous placement are both necessary for tight end-to-end SLO attainment. • We design a workflow- & heterogeneity-aware scheduling algorithm, where we formulate agentic serving as an online workflow scheduling problem over heterogeneous resources and design H EX AG EN T, which combines online workflow horizons, projected-risk prioritization, joint prefill–decode placement, decode-capacity-aware scheduling, and asynchronous plan application. • We show the performance boost of H EX AG EN T through an empirical study across representative agentic workloads and heterogeneous clusters. Across heterogeneous A100/H100/H200 settings, H EX AG EN T 2
lowers the SLO scale required to complete workflows on time relative to the strongest baselines, with especially large gains on mixed and tail-heavy workloads. The current manuscript’s headline result reports average reductions of 20.1% for 95% workflow attainment and 33.0% for 99% workflow attainment, with maximum reductions of 45.0% and 80.5%.
2
Preliminaries and Related Work
LLM serving systems. Modern LLM serving systems are primarily designed around individual inference requests as the basic scheduling unit. Their main optimizations focus on memory-efficient KV-cache management, continuous batching, and high-throughput execution on shared accelerators. Representative systems such as ORCA [51], vLLM [21], SGLang [54], Sarathi-Serve [1], Llumnix [41], and ServerlessLLM [7] have demonstrated that careful runtime design can substantially improve throughput and tail latency for conventional single-request or multi-tenant inference workloads. Nevertheless, these systems largely assume that requests are independent, or at least that queueing decisions can be made at the granularity of individual calls. This request-centric design is well aligned with chatbot-style workloads, but it becomes insufficient for agentic applications. In agentic execution, multiple LLM calls belong to the same end-to-end user task, and their value depends on workflow context rather than on standalone completion time. As a result, scheduling policies that are effective for independent LLM calls may still perform poorly once user requests expand into dependency-constrained multi-call workflows. Prefill–decode disaggregation. Prefill–decode (P-D) disaggregation has emerged as an important architecture for large-scale LLM serving [1, 20, 55]. The motivation is that the two phases of autoregressive inference stress different resources: prefill is compute-intensive and benefits from high-throughput execution, whereas decode is memory- and KV-cache-intensive and is often bottlenecked by capacity and admission decisions. Separating these two phases onto dedicated instance pools can therefore improve hardware specialization and resource utilization. At the same time, P-D disaggregation makes scheduling more difficult. A single LLM call is no longer mapped to one monolithic worker; instead, the system must decide which prefill instance should process the prompt, which decode instance should continue generation, and when the call should enter each local queue. The serving path also includes an explicit transfer stage between prefill and decode. Even when transfer is not itself scheduled as a separate shared bottleneck, it still contributes non-negligible latency and affects when decode becomes ready. Thus, disaggregation transforms serving into a multi-stage scheduling problem with stage coupling. Program-aware and agentic serving. Recent work has begun to recognize that many LLM applications are better viewed as programs rather than as bags of independent requests. Systems and schedulers such as Parrot [24], Hermes [25], Autellix [26], and Continuum [22] explicitly elevate the scheduling abstraction from an individual request to a larger program, application, or multi-turn agent execution. Program-aware schedulers, such as program-level FCFS and the attained-service-based PLAS/ATLAS family, treat the whole program or workflow as the primary object of fairness and progress accounting. This line of work is especially relevant for agentic workloads, where a user request may execute as a chain, tree, or DAG of dependent LLM calls. However, existing program-aware schedulers do not fully match the setting studied in this paper. Our target system combines three properties simultaneously: (i) workflows are revealed online rather than fully known in advance, (ii) serving is P-D disaggregated with heterogeneous prefill and decode instances, and (iii) the scheduler must operate under realistic runtime overhead constraints and therefore cannot block the serving path. These differences motivate a scheduler that is both workflow-aware and tightly coupled to the dynamics of P-D disaggregated execution. Call-Level scheduling for LLM inference. Another related line of work studies call-level scheduling policies for LLM serving, including preemptive queueing, shortest-job-first variants, deadline- or slack-aware policies, attained-service policies, and output-length-prediction-based scheduling. FastServe [45] applies iteration-level preemptive scheduling and multi-level feedback queues to reduce head-of-line blocking. QLM [33] studies queue management for SLO-oriented LLM serving. SSJF [36] uses proxy-model-based sequence length prediction for speculative shortest-job-first scheduling, while LTR-based scheduling [8] and embedding-based scheduling [39] use learned signals to improve prioritization. BlendServe [53] further explores resource-aware 3
batching for autoregressive inference. These methods improve per-request latency under contention and provide useful building blocks for practical serving systems. However, these policies remain blind to workflow structure. When multiple calls belong to the same agentic request, optimizing them independently can still produce poor end-to-end behavior. A scheduler may reduce the latency of isolated calls while delaying a workflow’s critical path or starving large but important workflows. Classical scheduling and DAG scheduling. Our work is also related to classical disciplines such as shortestjob-first, shortest-remaining-processing-time, least-slack-time-first, and least-attained-service scheduling [6, 38]. These policies provide useful principles for prioritization, fairness, and deadline awareness, and they inspire several of our baselines. We are also informed by the broader literature on workflow and DAG-style execution in agentic systems, including ReAct-style tool-using agents [50], tree-structured reasoning agents such as LATS [56], and agentic tool-use benchmarks such as BFCL [32]. Agentic LLM serving combines several properties that are uncommon in classical settings: workflow structure is revealed online, call durations are only estimated, decode memory is a first-class capacity constraint, and resource choice is phase-disaggregated. These differences motivate a scheduler specialized for agentic workflows rather than a direct reuse of generic job scheduling methods. Heterogeneous LLM serving. Heterogeneous LLM serving has become increasingly important as production clusters often combine different GPU generations, memory capacities, network bandwidths, cloud regions, and pricing models. Several recent systems [14, 16, 28] exploit such heterogeneity to improve throughput, latency, availability, or cost efficiency. For instance, HexGen [12] serves LLMs over heterogeneous GPUs and networks through asymmetric tensor/pipeline partitioning and constrained scheduling. Splitwise [31] exploits the distinct resource characteristics of prompt processing and token generation by splitting them across phase-specialized machines, including heterogeneous cluster designs. These systems demonstrate the importance of heterogeneity in LLM serving, but they primarily optimize placement or request scheduling at the serving-system level. In contrast, our work treats heterogeneity as part of the workflow scheduling problem: the scheduler reasons not only about which call is urgent, but also about which prefill/decode placement best reduces the workflow’s projected scaled-SLO risk under heterogeneous service times.
3
Workload Characterization
This characterization section motivates why serving agentic workflows on heterogeneous P-D clusters requires more than per-call level scheduling. We conduct a small ablation study to answer two questions: (i) whether end-to-end workflow awareness is necessary for agentic serving, and (ii) whether workflow awareness alone is sufficient without any heterogeneous workload/GPU-aware placement. This section is meant to isolate the design motivations behind H EX AG EN T, and we will comprehensively compare all workflow-level schedulers in Section 7. Experiment setting. We evaluate on two models: L LAMA 3.1-70B and Q WEN 3-235B-A22B. The experiments use a heterogeneous P-D cluster with 8 prefill instances and 8 decode instances. Each pool is composed of 2 A100, 3 H100, and 3 H200 model instances. The workloads include ShareGPT-style conversational chains, BFCL-v3 function-calling workflows, and LATS-style tree/search workflows. Metrics. We use the scaled-SLO metric for evaluation. For each workflow w, we first estimate its standalone execution horizon Hw on the same serving cluster. Given a scale factor α, the workflow is counted as satisfying its SLO if its completion time Cw satisfies Cw ≤ αHw . We report Req95 and Req99, which denote the minimum scale factor α required for 95% and 99% workflow SLO attainment, respectively. Lower Req95/Req99 indicates that the same serving system can meet workflow SLOs under tighter latency targets. Baseline system configuration. We begin with a representative LLM serving system as the baseline: SGLang with per-call FCFS as default scheduling policy. This baseline treats each revealed LLM call as an independent request. It does not account for the fact that multiple calls belong to the same end-to-end workflow, and it does not use heterogeneous per-instance latency estimates when deciding where a call should run. As shown in Table 1, this baseline often requires large SLO scales to satisfy tail workflows. For example, on Qwen-BFCL, 4
Table 1 Characterization ablation on heterogeneous P-D deployments. Each cell reports Req95/Req99. The table progressively adds workflow-level ordering and then H EX AG EN T’s heterogeneous workload/GPU-aware scheduling. Lower is better. Model Llama Llama Llama Qwen Qwen Qwen
Trace ShareGPT BFCL-v3 LATS BFCL-v3 LATS Mixed
Per-call FCFS 5.85 / 7.43 13.81 / 17.23 3.21 / 3.29 21.11 / 26.89 4.55 / 4.78 11.15 / 15.84
Workflow-FCFS 4.50 / 6.22 7.23 / 9.80 2.37 / 3.03 9.64 / 11.67 3.21 / 4.27 10.30 / 15.01
H EX AG EN T 2.50 / 2.60 6.21 / 6.34 2.19 / 2.24 8.39 / 8.57 2.71 / 2.74 3.48 / 3.94
it requires a Req95 of 21.11 and a Req99 of 26.89; on Llama-BFCL, it requires a Req95 of 13.81 and a Req99 of 17.23. Approach 1: Adding workflow-level awareness. The first improvement is to replace per-call FCFS with workflow-level FCFS. Instead of ordering all calls purely by reveal time, this policy preserves the ordering of the workflow. This simple change already improves end-to-end behavior because it prevents calls from the same workflow from being arbitrarily interleaved behind calls from unrelated workflows. Across the six cases in Table 1, Workflow-FCFS reduces Req95 by 31.4% on average and Req99 by 23.3% on average compared with per-call FCFS. The improvement is especially large on BFCL: for Qwen-BFCL, Req95 drops from 21.11 to 9.64, and Req99 drops from 26.89 to 11.67. Insight 1. Agentic workflow serving must optimize for end-to-end workflow progress, not only per-call queue order. Even a simple workflow-level FCFS policy substantially improves tail SLO scales over per-call FCFS because it preserves workflow-level execution continuity.
Approach 2: Adding heterogeneity awareness. Adding workflow-level ordering is not sufficient. Agentic workflows contain calls with different input lengths and output lengths. Some calls are more prefill-heavy, while others create larger decode/KV pressure (i.e., workload heterogeneity [55]). In a heterogeneous P-D cluster, different model instances also incur different prefill/decode service latencies (i.e., hardware heterogeneity [16]). Therefore, after deciding which workflow is urgent, the scheduler must also choose an appropriate prefill/decode pair for each revealed call. H EX AG EN T adds this second dimension. It uses the current workflow SLO target to prioritize ready calls and then evaluates candidate prefill/decode placements using estimated per-instance service latencies and current queue states. Compared with Workflow-FCFS, H EX AG EN T further reduces Req95 by 26.9% on average and Req99 by 42.6% on average across the six characterization cases. The largest improvement appears on Qwen-Mixed, where Req95 drops from 10.30 to 3.48 and Req99 drops from 15.01 to 3.94. This shows that workflow-level ordering alone cannot fully exploit heterogeneous resources; the scheduler must also reason about which model instance can serve each call most effectively. Insight 2. End-to-end workflow awareness must be combined with heterogeneous placement. A scheduler should not only know which workflow is urgent, but also account for the workload pattern of each LLM call and the expected service time on each prefill/decode instance.
The two insights together motivate the design of H EX AG EN T. It treats agentic LLM serving as a joint workflow scheduling and heterogeneous placement problem. It first reasons about each workflow’s current progress toward its end-to-end SLO target, and then assigns each ready call to the prefill/decode instances that best reduce the workflow’s projected scaled-SLO pressure. This design improves the cost efficiency of agentic workflow serving: under the same heterogeneous P-D deployment, the system can reach the same workflowlevel SLO attainment at a much smaller SLO scale. We next present the system design in Section 4 and the scheduling algorithm in Section 5.
5
4
System Overview
This section presents the architecture of H EX AG EN T and clarifies the scheduler’s role during serving. The key idea is to treat an agentic request as an online-revealed workflow while serving it in a P-D disaggregated runtime.
4.1
Agentic Workflow Abstraction as an Online DAG
We first define how H EX AG EN T represents an agentic workflow as a DAG, and then explain why this DAG should be treated as an online-revealed structure. Workflow DAG abstraction. H EX AG EN T abstracts each agentic workflow as a DAG G = (V, E) whose nodes are LLM calls and whose edges encode execution dependencies. This abstraction captures the common control-flow patterns of agentic applications. A nested agent-toolagent interaction appears as a short chain; a bounded self-refinement process can be unfolded into a finite chain or subtree; and parallel sub-calls appear as sibling branches that become runnable simultaneously after a common parent finishes. Online reveal and runnable frontier. The key property of this abstraction is that the DAG is revealed online. At workflow arrival, only source nodes are visible to the scheduler. A child node becomes schedulable only after all of its parents are complete. Therefore, the scheduler never plans the full workflow graph upfront. Instead, the system maintains a runnable frontier, and it repeatedly makes decisions over the currently revealed frontier of runnable calls. This online-reveal semantics matches how real agentic applications execute and is also the abstraction used by our scheduler. Figure 1 presents examples of this revealing process.
Currently revealed
Future node
Dependency
a Nested Agent-Tool-Agent Online chain
User Req
Agent
Tool
Agent
Output
Runnable frontier b Bounded Self-Refinement Unfolded chain
Max K iteration Draft
c
Critique Revise
Critique Revise (2)
(2)
Finalize
Runnable frontier Parallel Fan-out and Join Online fan-out Agent
Sub-call A Sub-call B Sub-call C Runnable frontier
Agent (Synthesis)
Figure 1 Example of an agentic LLM application workflow. Only source calls are known at arrival. As parent calls and tool calls complete, new LLM calls are revealed, and the workflow DAG grows online.
4.2 Serving Architecture and Scheduler Placement We first describe the major system components, then explain the internal modules of the scheduler, and finally specify the heterogeneous resources that the scheduler models when making placement and queuing decisions. System components. Figure 2 presents the architecture of our system. H EX AG EN T is organized around four logical components: a workflow front-end, a global scheduler, a P-D serving cluster, and external services. The workflow front-end receives agentic requests, tracks workflow state, and maintains the online DAG reveal process. The global scheduler observes the live system state and determines how waiting calls should be assigned and ordered. The P-D serving cluster contains a prefill pool and a decode pool built from heterogeneous hardware instances. Finally, external services include LLMs and tools that can be called in the workflow. Scheduler internals. The scheduler is not merely a routing policy. It acts as a live assignment and queuecontrol policy supported by four internal modules. The State Collector gathers cross-stage runtime snapshots, including prefill queues, decode queues, running calls, decode KV usage, bandwidth-related transfer state, and workflow progress. The Estimator converts these snapshots and per-call input and output length into runtime estimates using a roofline-style model [4, 44], including prefill time, decode time, KV-transfer latency, and decode memory demand. The Joint Planner then computes the scheduling plan by jointly deciding (i) the prefill/decode pair that should serve each waiting call and (ii) the local queue priority that the call
6
Workflow Front-End User Req
Global Scheduler New Calls
Estimator Cost, bandwidth, latency
Workflow Manager
Workflow State Store
State Collector Observe crossstage states
Call End Events
Disaggregated P-D Serving Cluster Sched. Plans
Prefill Instances
(call, priority)
Joint Planner Placement, queue priority
State Updates Plan Dispatcher (eventSend scheduling driven) plan
KV Transfer Network
Decode Instances
Bandwidth -Aware Latency
External Services LLM Weights
Tools
Monitoring & Metrics: Latency, throughput, KV usage, queue length, SLO
Figure 2 System architecture and scheduler placement of H EX AG EN T. The workflow front-end releases ready calls from online agent workflows, while the global scheduler collects cross-stage state, estimates prefill, KV-transfer, and decode latencies, and jointly decides instance placement and queue priority. The P-D disaggregated cluster executes calls across prefill and decode stages, with runtime metrics fed back for event-driven re-scheduling. H EX AG EN T frames agent serving as a joint placement-and-queueing problem over heterogeneous GPU resources to support PD disaggregated deployment.
should receive on the chosen instances. Finally, the Plan Dispatcher executes the scheduling decisions by sending placement and priority updates to the corresponding prefill and decode workers. This distinction is important because queue order, not just the choice of model instance, strongly affects workflow tail latency in disaggregated serving. Heterogeneous resource modelling. H EX AG EN T explicitly models the heterogeneous resources in a P-D disaggregated serving cluster. Each prefill instance behaves as a single-server execution engine with a local waiting queue, while each decode instance performs batched decoding subject to a KV-cache capacity constraint. The serving path also includes an explicit KV-transfer stage between prefill and decode. We compute the transfer latency from the KV size and the measured effective bandwidth between the corresponding GPU classes; in heterogeneous clusters, cross-hardware transfers therefore naturally incur higher latency when the available bandwidth is lower. The scheduler reasons over prefill queues, decode queues, decode KV capacity, and transfer-induced decode-ready times when making placement and ordering decisions.
4.3
End-to-End Request Lifecycle
We first introduce how LLM calls are revealed and scheduled, then specify when the scheduling is triggered and how the scheduled plan is applied. Workflow arrival reveals the initial runnable calls. An end-to-end agentic request begins when the workflow front-end receives a new user request and instantiates its workflow state. Only source LLM calls are revealed upon workflow arrival. These LLM calls are inserted into the global waiting set for prefill scheduling. Before invoking the scheduler, the front-end gathers a live snapshot of the system state, including current prefill and decode queues, running calls, decode capacities, and workflow-level progress metadata. Scheduler assigns instance and queue priorities. The scheduler then produces a plan for the currently waiting calls. For each call, the plan includes a chosen prefill instance, a chosen decode instance, and stage-local priorities. The call is dispatched to the selected prefill instance, enters a short bootstrap process with the chosen decode instance, and then joins that prefill instance’s local waiting queue. Once prefill starts, the call is no longer movable across prefill instances. After the prefill finishes, the system performs KV transfer to the selected decode instance. When the transfer completes, the call becomes decode-ready and enters the decode-side waiting structures of the chosen decode instance. Decode then begins subject to memory capacity and local queue order. When decode finishes, the call is marked complete, the workflow state is updated, and
7
any newly unblocked child calls are revealed. Runtime events drive subsequent schedulings. This lifecycle is event-driven. The main events are workflow arrival, prefill completion, transfer completion, and decode completion. Each of these events changes the runtime state. Workflow arrival adds newly runnable source calls. Prefill completion releases a prefill slot and initiates transfer. Transfer completion makes a call eligible for decode admission. Decode completion releases decode capacity and may reveal additional child calls. In the current implementation, scheduler invocations are triggered when new work enters a serving stage—workflow arrival, newly revealed prefill work, and transfer completion into decode. Asynchronous planning avoids blocking. Asynchronous scheduling is integrated into this lifecycle. While a new scheduling solve is in flight, serving does not stop. Newly arrived waiting calls that still have no assignment may temporarily follow a safe fallback policy. If the asynchronous plan returns before such a call starts service, the waiting call can still be updated to the new plan. If service has already started, the runtime state becomes authoritative, and the late plan is ignored for that serving stage. In short, H EX AG EN T plans continuously in the background while the foreground serving path keeps making progress.
5
Scheduling Framework
This section formalizes the scheduling objective of H EX AG EN T and then describes the online scheduling algorithm used in our framework. We first state the end-to-end scaled-SLO objective and then explain how H EX AG EN T makes stage-level decisions under online DAG revelation and P-D disaggregated serving.
5.1
Problem Formulation
Define online workflow horizon. We consider a stream of agentic workflows W = {w1 , w2 , . . . } arriving over time. Each workflow w is an online-revealed DAG. Let Gw (t) denote the subgraph of workflow w that has been revealed by time t. H EX AG EN T assigns each workflow a workflow-specific horizon Hw (t), which serves as the current end-to-end serving target during online scheduling. Concretely, Hw (t) is the standalone completion time of Gw (t) on the evaluated P-D cluster: the time needed to execute the revealed workflow subgraph if it were served in isolation using the same serving cluster. When the workflow is fully revealed, the final horizon Hw becomes the standalone completion time of the entire workflow. π Optimizing for scaled-SLO objective. Let Cw denote the end-to-end completion time of workflow w under scheduling policy π. Our goal is to maximize end-to-end SLO attainment across workflows. Equivalently, for a target attainment level τ ∈ {0.95, 0.99}, we formulate the objective as finding the smallest scale factor α such that at least a τ fraction of workflows complete within αHw :
min α π
s.t.
1 X 1[Cwπ ≤ αHw ] ≥ τ. |W|
(1)
w∈W
This formulation directly captures the goal of completing more workflows within tighter scaled SLOs, rather than merely reducing average call latency. Refine the horizon progressively. Hw is not known when a workflow first arrives. Since the workflow DAG is revealed online, the scheduler only observes Gw (t) at time t. H EX AG EN T therefore maintains an online planning horizon Hw (t) and recomputes it whenever new calls are revealed. If a newly revealed call changes the isolated makespan of the revealed subgraph, then the workflow’s SLO target grows accordingly. When true service times become available, the horizon can also be corrected by replacing estimates with observed serving latencies. Thus, Hw (t) is a progressively refined estimate of the final workflow-specific target. Introduce the projected ratio as an surrogate. Since Hw need to be progressively refined, the scheduler does not optimize Equation (1) directly at every event. Instead, at each scheduling invocation it estimates how scheduling a ready call would affect the workflow’s SLO violation risk. For a ready call c from workflow 8
w at time t, let ∆s (c, t) denote the projected elapsed time from now until the call finishes at stage s ∈ {Prefill, Decode}. For prefill scheduling, this projection includes waiting time, prefill time, and KV-transfer latency. For decode scheduling, it includes waiting for decode capacity and decode execution on a candidate decode instance. H EX AG EN T defines the projected ratio as Rs (c, t) =
(t − aw ) + ∆s (c, t) , Hw (t)
(2)
where aw is the workflow arrival time, and the term (t − aw ) represents the workflow’s elapsed time. A larger Rs (c, t) indicates that serving c is more urgent because the workflow is projected to be closer to, or further beyond, its current serving target.
5.2
Global Scheduling Loop
The scheduling loop of H EX AG EN T is event-driven. The runtime state changes on workflow arrival, prefill completion, transfer completion, and decode completion. By design, the scheduler is triggered on the following events: when a workflow arrives and reveals source calls, when decode completion reveals new child calls for prefill, and when transfer completion makes a call ready for decode. Other events still update the runtime state, but they do not necessarily invoke a new scheduling. Workflow-aware scheduling. The scheduling is stage-aware and workflow-aware. A prefill invocation considers all calls currently waiting for prefill; a decode invocation considers all calls currently waiting for decode. In both cases, H EX AG EN T observes the workflow horizon Hw (t), the workflow’s current completion progress, and the live state of the corresponding stage. Scheduling is asynchronous: at most one plan is in flight, serving continues while a plan is being computed, and late plans are applied only to calls that are still waiting. Once a call starts prefill or decode, its prefill and decode placement are fixed, and the call is no longer movable by the scheduler. This workflow-aware design reflects the first motivation of H EX AG EN T: scheduling decisions should be made with workflow-level awareness, because the serving objective is end-to-end SLO attainment rather than the latency of isolated LLM calls. Event-driven scheduling. Algorithm 1 summarizes the event-driven scheduling loop in H EX AG EN T. At a high level, each scheduling invocation ranks waiting calls by projected scaled-SLO risk, greedily selects the most urgent call, updates a simulated resource state, and finally applies the resulting plan asynchronously to calls that are still waiting. The detailed scheduling logic is described in §5.3 and §5.4.
5.3
Prefill Scheduler
Projected-risk prefill ranking. The prefill scheduler ranks waiting calls by projected scaled-SLO risk. For each call, it enumerates candidate prefill instances and candidate decode instances, estimates the prefill finish time, adds transfer latency, and projects the earliest decode finish using current decode availability hints. This gives RP (c, t) in Equation (2). Calls with larger projected ratios are treated as more urgent. This enumeration reflects the second motivation of H EX AG EN T: serving must be heterogeneity-aware, since the same LLM call can have different prefill and decode latencies on different model instances. Adaptive greedy prefill assignment. For small queues, H EX AG EN T uses a greedy procedure. It repeatedly selects the most urgent pending call, assigns it to the prefill–decode pair with the earliest projected decode finish, updates the simulated prefill and decode availability, and then recomputes priorities for the remaining calls. This recomputation is important because the best choice for the next call depends on assignments already made in the same planning invocation. For larger queues, H EX AG EN T uses a one-pass ordering by the same risk score to keep overhead bounded. Joint prefill–decode planning. The prefill scheduler performs joint prefill–decode planning. Its decision for a call contains both the assigned prefill instance and a planned decode instance. The latter is used to establish the downstream decode relation before prefill completes, so that the runtime knows where the KV state should be transferred. In heterogeneous settings, this joint decision also accounts for the smaller bandwidth across 9
Algorithm 1 Event-driven scheduling in H EX AG EN T Require: event e, time t, runtime state S(t) 1: Update queues, running calls, KV state using e 2: Update affected workflow horizons Hw (t) 3: T ← triggered stages from e 4: for all stage s ∈ T do 5: if planner for s is in flight then 6: Apply fallback plan if needed 7: continue 8: end if 9: Qs ← waiting calls at stage s 10: Sb ← S(t) 11: Πs ← ∅ 12: while Qs ̸= ∅ do 13: for all c ∈ Qs do 14: Project best feasible placement for c 15: Obtain projected elapsed time ∆s (c, t) 16: Rs (c, t) ← ((t − aw(c) ) + ∆s (c, t))/Hw(c) (t) 17: end for 18: c⋆ ← arg maxc∈Qs Rs (c, t) 19: Add placement and rank of c⋆ to Πs 20: Update simulated state Sb 21: Qs ← Qs \ {c⋆ } 22: end while 23: Asynchronously apply Πs to still-waiting calls 24: end for
▷ T ⊆ {P, D}
different hardware types, which will discourage prefill-decode pairs with expensive KV movement unless their service-time benefit justifies it.
5.4
Decode Scheduler
Decode scheduling with instance locks. The decode scheduler operates on calls that have completed transfer and are waiting for decode admission. It uses the same projected-ratio score for ranking, while its feasibility model additionally respects decode KV capacity. A call may be locked to a planned decode instance selected during prefill scheduling; locked calls can be reordered within that instance but cannot migrate across decode instances. On the other hand, free calls can be placed on any feasible decode instance. Decode KV-capacity feasibility check. Feasibility is determined by decode memory demand. Let Lin (c) b out (c) denote its predicted output length. We use denote the input prompt length of call c in tokens, and let L b out (c) from the model input prompt and proxy model-based sequence length prediction [35] to estimate L model identity. The decode demand of a call is approximated as b out (c), m(c) = Lin (c) + L
(3)
and a call is feasible on decode instance d only if m(c) ≤ Cap(d),
(4)
where Cap(d) is the decode KV capacity of instance d. Adaptive greedy decode assignment. For small decode queues, H EX AG EN T again uses recomputing greedy scheduling. It repeatedly selects the most urgent call, finds the earliest capacity-feasible start time on each legal decode instance, assigns the call to the instance with the earliest projected finish, and updates the simulated decode intervals. For larger or special-case queues, it falls back to the lightweight ordering described above. 10
Together, the prefill and decode schedulers realize the core design of H EX AG EN T: workflow-aware projectedrisk priority, heterogeneous prefill–decode matching, decode-capacity-aware placement, and asynchronous online refinement.
6
Implementation
We implement H EX AG EN T on top of SGLang v0.5.9 [54], using SGLang’s P-D disaggregated serving feature as the substrate. The implementation keeps the scheduling policy outside GPU kernels and the hot decode loop, and instead integrates H EX AG EN T into the gateway and worker path. The implementation mainly uses Python, with JSON configuration files for deployment metadata. The main changes include router-side workflow metadata parsing, stage-state construction, asynchronous schedule plan application, revision checks for safe queue mutation, bootstrap metadata injection, and completion feedback accounting. Worker-side changes expose P-D snapshots, accept priority/reassignment updates for still-waiting requests, and report completion telemetry back to the router. We also implement a standalone event-driven simulator as a resource estimator that supports scheduler decisions. The simulator is implemented in Python and contains about 4.6K lines across the runtime, scheduler, and runners. It models the full lifecycle of each LLM call, including waiting prefill, prefill, KV transfer, waiting decode, decode, and completion. The simulator maintains prefill instance availability, decode token-capacity intervals, workflow DAG dependencies, asynchronous scheduling events, and workflow-level SLO state. For each scheduling event, it estimates projected prefill and decode completion times for candidate placements, computes the standalone execution horizon Hw used as the workflow-level SLO target, and provides the projected ratios used by the scheduler to rank ready calls. Service times are obtained from a roofline-style latency model [4, 44].
7
Evaluation
This section evaluates the performance of H EX AG EN T under P-D disaggregated serving of agentic workflows. We begin by asking the following questions: • (Q1) How does the end-to-end SLO attainment of H EX AG EN T compare to that of the state-of-the-art LLM serving systems on heterogeneous clusters? • (Q2) How does the end-to-end SLO attainment of H EX AG EN T compare to that of the state-of-the-art LLM serving systems on homogeneous clusters? • (Q3) How robust is H EX AG EN T to the estimation error of serving latencies? • (Q4) What scheduling overhead does H EX AG EN T introduce?
7.1
Experimental Setup
Workloads. We evaluate H EX AG EN T over four representative agentic workloads with multiple LLM calls. Each trace is represented as an online-revealed workflow DAG whose nodes are LLM calls annotated with input length, output length, parent dependencies, and workflow identity. Analogous to Autellix [26], we construct traces from the following representative agentic sources: • ShareGPT. This trace contains 100 conversational-chain workflows arriving at 10 workflows/s, based on ShareGPT-style conversations used by Vicuna [5]. It primarily stresses sequential workflow progress and accumulated end-to-end chain latency. • BFCL-v3. This trace contains 400 function-calling workflows arriving at 40 workflows/s, based on BFCL-v3 [32]. It represents tool-heavy workloads with frequent online call revelation. • LATS. This trace contains 100 tree/search-style workflows arriving at 40 workflows/s. It is derived by running LATS-style Monte Carlo tree search [56] on HotpotQA [48], and stresses reasoning workflows with bursty fan-out, where completing one parent call may reveal multiple downstream calls. 11
• Mixed. This trace interleaves ShareGPT, BFCL-v3, and LATS workflows, with 100 workflows arriving at 10 workflows/s. It evaluates scheduler robustness when different agentic workflows share the same P-D serving cluster. Models. We evaluate on L LAMA 3.1-70B and Q WEN 3-235B-A22B. The L LAMA 3.1-70B experiments use tensor parallelism degree 4 for A100, H100, and H200 GPUs. The Q WEN 3-235B-A22B experiments use tensor parallelism degree 8 for A100 and H100, and tensor parallelism degree 4 for H200. Heterogeneous runtime. Our main experiments use heterogeneous A100/H100/H200 P-D clusters. We evaluate two heterogeneous configurations: • Hetero-1: This setup contains 8 prefill instances and 8 decode instances, with each pool composed of 2 A100, 3 H100, and 3 H200 model instances. • Hetero-2: This setup contains 10 prefill instances and 10 decode instances, with each pool composed of 3 A100, 4 H100, and 3 H200 model instances. Homogeneous runtime. To isolate the benefit of workflow-aware scheduling without hardware heterogeneity, we report a single homogeneous 4P+4D setting for each model family. The Llama homogeneous experiment uses four H200 TP4 prefill instances and four H200 TP4 decode instances. The Qwen homogeneous experiment uses four A100 TP8 prefill instances and four A100 TP8 decode instances.
7.2
Baselines
We compare H EX AG EN T against three strong baselines. • SGLang-FCFS. SGLang [54] combines continuous batching with RadixAttention to efficiently manage KV cache across requests. Its default scheduling policy is FCFS. We implement a workflow-level FCFS scheduler with load-balanced dispatching. • SGLang-LLF. On top of SGLang, we implement a workflow-level least-laxity-first scheduler [40] that prioritizes workflows with smaller remaining slack relative to deadlines. • Autellix-ATLAS. An adaptation of ATLAS from Autellix [26], representing a state-of-the-art programaware attained-service baseline.
7.3
Evaluation Metrics
SLO scaling metrics. Following standard practice in LLM serving evaluations [23, 55], we evaluate system performance based on workflow-level SLO attainment. For each workflow, we first collect its standalone execution horizon Hw in an exclusive environment on the same serving cluster. During evaluation, we set the SLO by multiplying this standalone horizon with a scale factor α, i.e., the workflow will be violating SLO if Cw ≥ αHw . Smaller α corresponds to a tighter SLO. We report two tail metrics: Req95 and Req99, which represent the minimum SLO scale α such that at least 95% and 99% of workflows complete within αHw , respectively. Lower Req95 and Req99 mean that the scheduler can satisfy the same workflow-level attainment target under tighter end-to-end SLOs. We also visualize full SLO-attainment curves by sweeping α. Scheduler overhead. We report total scheduler time and average scheduler time per invocation. Since scheduling is asynchronous, this overhead affects quality indirectly: a slower scheduler leaves more calls executing under fallback plans or stale assignments.
7.4
End-to-End Evaluation with Heterogeneity (Q1)
Overall comparison. Table 2 summarizes the heterogeneous results. Each row averages over the four workload traces, and the baseline column reports the strongest baseline for each trace before averaging. Across all heterogeneous model/cluster settings, H EX AG EN T reduces the scale factor required to finish 95% of workflows by 13.0% on average and the scale factor required to finish 99% of workflows by 24.5% on average.
12
4 Z H Q 3 ' : R U N I O R Z V
4 Z H Q 3 ' : R U N I O R Z V
/ O D P D 3 ' : R U N I O R Z V
/ O D P D 3 ' : R U N I O R Z V
) & ) 6
6 K D U H * 3 7
6 F D O H G 6 / 2 [
/ / )
$ 7 / $ 6
% ) & /
6 F D O H G 6 / 2 [
2 X U V
/ $ 7 6
6 F D O H G 6 / 2 [
0 L [ H G 6 F D O H G 6 / 2 [
Figure 3 SLO-attainment curves on heterogeneous A100/H100/H200 clusters. Each subplot sweeps the SLO scale α and reports the fraction of workflows satisfying Cw ≤ αHw . Higher curves to the left indicate stronger performance. H EX AG EN T consistently reaches high attainment at smaller SLO scales, especially on Qwen and mixed/LATS-style workloads. Table 2 End-to-end results on heterogeneous A100/H100/H200 clusters. Values are averaged across ShareGPT, BFCL-v3, LATS, and Mixed. Each cell reports Req95/Req99. Each baseline column uses the strongest baseline for the corresponding trace. Lower is better.
Model Llama Llama Qwen Qwen
Cluster Hetero-1 Hetero-2 Hetero-1 Hetero-2
H EX AG EN T 3.54 / 3.71 2.95 / 3.11 4.48 / 4.69 3.87 / 3.98
Best baseline 4.00 / 4.75 3.12 / 3.65 5.60 / 7.22 4.42 / 6.11
Reduction 11.2% / 18.2% 6.1% / 13.9% 21.1% / 33.1% 13.5% / 32.7%
The improvement is consistent across both models and both cluster sizes: even in the weakest averaged case, Llama on Hetero-2, H EX AG EN T still reduces Req95 by 6.1% and Req99 by 13.9% over the strongest baseline. The largest average gains appear on Qwen, where the heterogeneous deployment creates a stronger placement problem. On Qwen Hetero-1, H EX AG EN T lowers the average Req95 from 5.60 to 4.48 and Req99 from 7.22 to 4.69, corresponding to 21.1% and 33.1% reductions. On Qwen Hetero-2, H EX AG EN T lowers the average Req95 from 4.42 to 3.87 and Req99 from 6.11 to 3.98, corresponding to 13.5% and 32.7% reductions. These results indicate that the benefit of H EX AG EN T becomes more pronounced when workflow-level pressure interacts with expensive model execution and heterogeneous prefill/decode assignment decisions. Where does the gain come from? Figure 3 shows the full SLO-attainment curves and Table 3 shows the per-trace results for Qwen on Hetero-1, the heterogeneous Qwen setting where H EX AG EN T obtains the strongest average improvement. H EX AG EN T improves Req95 and Req99 on all traces. The most significant tail-latency reduction appears on Mixed: H EX AG EN T reduces Req99 from 8.96 to 3.94, a 56.0% reduction over Workflow-LLF. It also reduces Req99 on ShareGPT from 5.45 to 3.50, a 35.9% reduction over Workflow-LLF, and reduces Req99 on BFCL-v3 from 11.13 to 8.57, a 23.0% reduction over Workflow-LLF. LATS also benefits: 13
Table 3 Detailed heterogeneous results for Qwen on Hetero-1. Each cell reports Req95/Req99. This setting illustrates H EX AG EN T’s behavior under strong heterogeneous queueing pressure. Lower is better.
Trace ShareGPT BFCL-v3 LATS Mixed
H EX AG EN T 3.36 / 3.50 8.39 / 8.57 2.71 / 2.74 3.48 / 3.94
Best baseline 4.58 / 5.45 (Workflow-LLF) 8.90 / 11.13 (Workflow-LLF) 3.06 / 3.33 (Workflow-LLF) 5.85 / 8.96 (Workflow-LLF)
) & ) 6
4 Z H Q 3 ' : R U N I O R Z V
/ O D P D 3 ' : R U N I O R Z V
6 K D U H * 3 7
/ / )
$ 7 / $ 6
% ) & /
Reduction 26.7% / 35.9% 5.7% / 23.0% 11.3% / 17.7% 40.6% / 56.0%
2 X U V / $ 7 6
0 L [ H G
6 F D O H G 6 / 2 [ 6 F D O H G 6 / 2 [ 6 F D O H G 6 / 2 [ 6 F D O H G 6 / 2 [
Figure 4 SLO-attainment curves on homogeneous 4P+4D clusters. Each subplot sweeps the SLO scale α and reports the fraction of workflows satisfying Cw ≤ αHw . Even without heterogeneous placement choices, H EX AG EN T reaches high attainment at smaller scales by improving workflow-aware queue ordering.
H EX AG EN T reduces Req95 from 3.06 to 2.71 and Req99 from 3.33 to 2.74, corresponding to 11.3% and 17.7% reductions. The Mixed and ShareGPT results illustrate that workflow-aware placement matters. Mixed workloads combine chain-like, function-calling, and tree-search workflows, creating non-uniform queueing pressure across both P and D stages. ShareGPT workflows are more sequential, so delaying one revealed call can directly delay the entire workflow. Workflow-FCFS preserves arrival order but cannot distinguish workflows whose revealed frontier is close to violating its scaled SLO. Workflow-LLF captures urgency, but it does not jointly evaluate which prefill/decode pair will minimize the projected normalized completion after accounting for heterogeneous service latencies and transfer-induced decode-ready times. Autellix-ATLAS tracks attained service at the program level, which helps fairness, but attained service is not the same as the remaining risk of exceeding a workflow-specific horizon. In contrast, H EX AG EN T directly estimates the consequence of scheduling each ready call on a concrete prefill/decode pair and prioritizes calls that most threaten workflow-level completion. This explains why the largest gains appear on Mixed and ShareGPT traces, where workflow-level queueing pressure and heterogeneous placement sensitivity are both pronounced. The BFCL-v3 and LATS rows provide complementary context. BFCL-v3 consists of many short functioncalling tasks, and Workflow-LLF already approximates much of the urgency signal, so the remaining room for improvement is smaller at Req95. Nevertheless, H EX AG EN T still reduces Req99 by 23.0%, showing that workflow-aware prefill/decode placement improves the tail even when the average scheduling problem is relatively easy for strong urgency-based baselines. LATS has tree/search-style online revelation, and H EX AG EN T improves both Req95 and Req99 by avoiding placements that create downstream queueing pressure after new branches are revealed.
14
Table 4 Homogeneous 4P+4D results. Values are averaged across ShareGPT, BFCL-v3, LATS, and Mixed. Each cell reports Req95/Req99. Lower is better.
Model Llama Qwen
Cluster H200 4P+4D A100 4P+4D
H EX AG EN T 4.99 / 5.19 5.48 / 5.62
Best baseline 6.52 / 8.37 6.89 / 8.33
Red. 24.8% / 36.8% 23.1% / 33.9%
Table 5 Robustness to estimation error on Hetero-1. Entries report the average percentage degradation relative to the 0% error case across four traces. Lower is better.
Model Llama Llama Llama Qwen Qwen Qwen
7.5
Error 10% 20% 30% 10% 20% 30%
Req95 deg. 0.9% -0.5% 0.7% -1.9% -1.1% -1.4%
Req99 deg. 1.5% 0.8% 1.5% 9.5% 7.0% 5.4%
Evaluation on Homogeneous Clusters (Q2)
Homogeneous results. Figure 4 shows the SLO-attainment curves for the homogeneous setting, and Table 4 summarizes the corresponding tail metrics. H EX AG EN T improves Req95 and Req99 for both model families. These results show that H EX AG EN T reduces Req95 by 24.8% and Req99 by 36.8% on the Llama model executed on the H200 GPU, and reduces Req95 by 23.1% and Req99 by 33.9% on the Qwen model executed on the A100 GPUs. The homogeneous results show that H EX AG EN T does not rely solely on hardware heterogeneity. Even when all instances in a cluster share the same model configuration, workflow-aware scheduling still reduces tail SLO scales by prioritizing workflows that are closest to their current SLO target and by avoiding poor local queue ordering. In particular, the homogeneous curves in Figure 4 show that H EX AG EN T moves the attainment curve left on sequential and mixed workloads, where delaying one call can directly delay the entire workflow. The relative gains are smaller on short structured workloads such as BFCL-v3, where the strongest baselines already keep small tasks moving.
7.6
Robustness to Estimation Error (Q3)
Setup. We evaluate robustness on the main heterogeneous Hetero-1 setting by injecting deterministic multiplicative error into the scheduler-visible prefill and decode estimates. The actual service durations are unchanged. We sweep estimation error levels of 0%, 10%, 20%, and 30% for both Llama and Qwen experiments. Results. Table 5 reports the average degradation in Req95 and Req99 relative to the no-error case. H EX AG EN T is robust to moderate prediction errors. For Llama, the average Req99 degradation remains within 1.5% even at 30% estimation error. Qwen shows larger Req99 sensitivity, especially at 10% noise, but the average degradation remains bounded and non-monotonic because the scheduler is still driven by workflow-level priorities rather than exact per-call durations. The small degradation indicates that H EX AG EN T does not require exact service-time prediction to be useful. Estimation error can change the chosen prefill/decode pair for some calls, but the ordering signal is smoothed at the workflow level: the scheduler prioritizes workflows by normalized completion pressure rather than by a single noisy call duration. The negative degradation values in some rows mean that a noisy estimate happened to produce a slightly better greedy ordering than the no-error estimate for that trace; we treat these as near-ties rather than meaningful improvements. Overall, even with 30% multiplicative estimation error, the scheduler remains stable enough for the workflow-level benefits observed in the main experiments.
15
Table 6 Scheduler overhead in heterogeneous settings. Values are averaged across traces for H EX AG EN T. Ms/inv represents the overhead (ms) per scheduler invocation
Model Llama Llama Qwen Qwen
7.7
Cluster Hetero-1 Hetero-2 Hetero-1 Hetero-2
Ms/inv 10.2 7.1 14.7 11.5
Total overhead (s) 25.7 19.4 28.8 23.2
Scheduler Overhead Study (Q4)
Asynchronous overhead. H EX AG EN T performs more planning than the workflow-level baselines because it evaluates candidate prefill/decode placements and recomputes priorities for ready calls. However, the asynchronous runtime prevents scheduling from directly blocking already running service. In our heterogeneous overhead screen, H EX AG EN T requires only millisecond-scale planning: the average scheduling time per invocation is 10.2 ms for Llama Hetero-1, 7.1 ms for Llama Hetero-2, 14.7 ms for Qwen Hetero-1, and 11.5 ms for Qwen Hetero-2. The worst per-invocation average across traces is 23.7 ms. These numbers indicate that the additional workflow-aware planning cost is small relative to end-to-end workflow execution time. Impact on serving quality. The overhead results should be interpreted together with the end-to-end tables. A purely greedy local policy is cheaper, but it can leave workflows with much larger tail SLO scales. H EX AG EN T spends a few to tens of milliseconds to evaluate the consequences of placement and ordering decisions, and the asynchronous plan-application rule ensures that this planning cost does not stall calls already in service. Thus, the scheduler trades a small amount of CPU-side planning work for substantially tighter workflow-level SLO scaling, especially in heterogeneous settings where a wrong decode placement or a stale local queue order can dominate the tail.
8
Conclusion
We present H EX AG EN T, a workflow- & heterogeneity-aware scheduler for serving agentic LLM requests on the P-D disaggregated paradigm. H EX AG EN T targets end-to-end workflow SLO attainment by maintaining an online planning horizon for each partially revealed workflow and jointly plans prefill and decode assignment, accounts for heterogeneous serving latencies. Our evaluation shows that H EX AG EN T improves tail scaled-SLO attainment over program-aware baselines in the heterogeneous setting, and that the benefit also carries over to homogeneous H200 clusters. These results suggest that workflow-level objectives should become first-class scheduling targets as LLM applications evolve from isolated requests into structured, multi-step agentic systems.
References [1] Amey Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S. Gulavani, Alexey Tumanov, and Ramachandran Ramjee. Taming throughput-latency trade-off in LLM inference with Sarathi-Serve. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), Santa Clara, CA, July 2024. USENIX Association. ISBN 978-1-939133-40-3. URL https://www.usenix.org/conference/osdi24/presentatio n/agrawal. [2] Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. Balanced allocations. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pages 593–602, New York, NY, USA, 1994. Association for Computing Machinery. doi: 10.1145/195058.195412. [3] Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler. Graph of thoughts: Solving elaborate problems with large language models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38. AAAI Press, 2024. [4] Shiyi Cao, Shu Liu, Tyler Griggs, Peter Schafhalter, Xiaoxuan Liu, Ying Sheng, Joseph E. Gonzalez, Matei Zaharia, and Ion Stoica. MoE-Lightning: High-throughput MoE inference on memory-constrained GPUs. In Proceedings of the
16
30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1, pages 715–730. ACM, 2025. doi: 10.1145/3669940.3707267. URL https://doi.org/10.1145/366994 0.3707267. [5] Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E. Gonzalez, Ion Stoica, and Eric P. Xing. Vicuna: An open-source chatbot impressing GPT-4 with 90%* ChatGPT quality. LMSYS Blog, March 2023. URL https://lmsys.org/blog/2023-03-30-vicuna/. [6] Robert I. Davis, Ken W. Tindell, and Alan Burns. Scheduling slack time in fixed priority pre-emptive systems. In Proceedings of the 14th IEEE Real-Time Systems Symposium, pages 222–231, Washington, DC, USA, 1993. IEEE Computer Society. doi: 10.1109/REAL.1993.393505. [7] Yao Fu, Leyang Xue, Yeqi Huang, Andrei-Octavian Brabete, Dmitrii Ustiugov, Yuvraj Patel, and Luo Mai. ServerlessLLM: Low-latency serverless inference for large language models. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), pages 135–153, Santa Clara, CA, July 2024. USENIX Association. ISBN 978-1-939133-40-3. URL https://www.usenix.org/conference/osdi24/presentation/fu. [8] Yichao Fu, Siqi Zhu, Runlong Su, Aurick Qiao, Ion Stoica, and Hao Zhang. Efficient LLM scheduling by learning to rank, 2024. [9] Guoliang He, Youhe Jiang, Wencong Xiao, Jiang Kaihua, Shuguang Wang, Jun Wang, Du Zixian, Zhuo Jiang, Xinlei Zhang, Binhang Yuan, et al. Efficient pre-training of llms via topology-aware communication alignment on more than 9600 gpus. Advances in Neural Information Processing Systems, 38:147100–147126, 2026. [10] Wenhao He, Youhe Jiang, Penghao Zhao, Quanqing Xu, Eiko Yoneki, Bin Cui, and Fangcheng Fu. Efficient multi-round llm inference over disaggregated serving. arXiv preprint arXiv:2602.14516, 2026. [11] Youhe Jiang, Fangcheng Fu, Xupeng Miao, Xiaonan Nie, and Bin Cui. Osdp: Optimal sharded data parallel for distributed deep learning. arXiv preprint arXiv:2209.13258, 2022. [12] Youhe Jiang, Ran Yan, Xiaozhe Yao, Yang Zhou, Beidi Chen, and Binhang Yuan. Hexgen: Generative inference of large language model over heterogeneous environment. arXiv preprint arXiv:2311.11514, 2023. [13] Youhe Jiang, Fangcheng Fu, Xiaozhe Yao, Guoliang He, Xupeng Miao, Ana Klimovic, Bin Cui, Binhang Yuan, and Eiko Yoneki. Demystifying cost-efficiency in llm serving over heterogeneous gpus. arXiv preprint arXiv:2502.00722, 2025. [14] Youhe Jiang, Fangcheng Fu, Xiaozhe Yao, Taiyi Wang, Bin Cui, Ana Klimovic, and Eiko Yoneki. Thunderserve: High-performance and cost-efficient llm serving in cloud environments. Proceedings of Machine Learning and Systems, 7, 2025. [15] Youhe Jiang, Fangcheng Fu, Wanru Zhao, Stephan Rabanser, Jintao Zhang, Nicholas D Lane, and Binhang Yuan. Cascadia: An efficient cascade serving system for large language models. arXiv preprint arXiv:2506.04203, 2025. [16] Youhe Jiang, Ran Yan, and Binhang Yuan. Hexgen-2: Disaggregated generative inference of llms in heterogeneous environment. arXiv preprint arXiv:2502.07903, 2025. [17] Youhe Jiang, Fangcheng Fu, Taiyi Wang, Guoliang He, and Eiko Yoneki. Oserve: Accelerating llm serving via spatial-temporal workload orchestration. arXiv preprint arXiv:2602.12151, 2026. [18] Youhe Jiang, Fangcheng Fu, and Eiko Yoneki. Boute: Cost-efficient llm serving with heterogeneous llms and gpus via multi-objective bayesian optimization. arXiv preprint arXiv:2602.10729, 2026. [19] Youhe Jiang, Ran Yan, You Peng, Wenshuang Li, Taiyi Wang, Fangcheng Fu, and Binhang Yuan. Autopoiesis: A self-evolving system paradigm for llm serving under runtime dynamics. arXiv preprint arXiv:2604.07144, 2026. [20] Yibo Jin, Tao Wang, Huimin Lin, Mingyang Song, Peiyang Li, Yipeng Ma, Yicheng Shan, Zhengfan Yuan, Cailong Li, Yajing Sun, Tiandeng Wu, Xing Chu, Ruizhi Huan, Li Ma, Xiao You, Wenting Zhou, Yunpeng Ye, Wen Liu, Xiangkun Xu, Yongsheng Zhang, Tiantian Dong, Jiawei Zhu, Zhe Wang, Xijian Ju, Jianxun Song, Haoliang Cheng, Xiaojing Li, Jiandong Ding, Hefei Guo, and Zhengyong Zhang. P/D-Serve: Serving disaggregated large language model at scale, 2024. [21] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with PagedAttention. In Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, pages 611–626, New York, NY, USA, 2023. Association for Computing Machinery. doi: 10.1145/3600006.3613165.
17
[22] Hanchen Li, Qiuyang Mang, Runyuan He, Qizheng Zhang, Huanzhi Mao, Xiaokun Chen, Alvin Cheung, Joseph E. Gonzalez, and Ion Stoica. Continuum: Efficient and robust multi-turn LLM agent scheduling with KV cache time-to-live, 2025. [23] Zhuohan Li, Lianmin Zheng, Yinmin Zhong, Vincent Liu, Ying Sheng, Xin Jin, Yanping Huang, Zhifeng Chen, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. AlpaServe: Statistical multiplexing with model parallelism for deep learning serving. In 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23), pages 663–679, Boston, MA, July 2023. USENIX Association. ISBN 978-1-939133-34-2. URL https://www.usenix.org/c onference/osdi23/presentation/li-zhouhan. [24] Chaofan Lin, Zhenhua Han, Chengruidong Zhang, Yuqing Yang, Fan Yang, Chen Chen, and Lili Qiu. Parrot: Efficient serving of LLM-based applications with semantic variable. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), pages 929–945, Santa Clara, CA, July 2024. USENIX Association. ISBN 978-1-939133-40-3. URL https://www.usenix.org/conference/osdi24/presentation/lin-chaofan. [25] Yifei Liu, Zuo Gan, Zhenghao Gan, Weiye Wang, Chen Chen, Yizhou Shan, Xusheng Chen, Zhenhua Han, Yifei Zhu, Shixuan Sun, and Minyi Guo. Hermes: Efficient serving of LLM applications with probabilistic demand modeling. ACM Transactions on Architecture and Code Optimization, 2026. doi: 10.1145/3803390. [26] Michael Luo, Xiaoxiang Shi, Colin Cai, Tianjun Zhang, Justin Wong, Yichuan Wang, Chi Wang, Yanping Huang, Zhifeng Chen, Joseph E. Gonzalez, and Ion Stoica. Autellix: An efficient serving engine for LLM agents as general programs, 2025. [27] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self-feedback. In Advances in Neural Information Processing Systems, volume 36. Curran Associates, Inc., 2023. [28] Ziming Mao, Tian Xia, Zhanghao Wu, Wei-Lin Chiang, Tyler Griggs, Romil Bhardwaj, Zongheng Yang, Scott Shenker, and Ion Stoica. Skyserve: Serving ai models across regions and clouds with spot instances. In Proceedings of the Twentieth European Conference on Computer Systems, pages 159–175, 2025. [29] McKinsey & Company. The state of AI in 2025. McKinsey Global Survey, 2025. URL https://www.mckinsey.com/c apabilities/quantumblack/our-insights/the-state-of-ai. [30] Xupeng Miao, Yujie Wang, Youhe Jiang, Chunan Shi, Xiaonan Nie, Hailin Zhang, and Bin Cui. Galvatron: Efficient transformer training over multiple gpus using automatic parallelism. arXiv preprint arXiv:2211.13878, 2022. [31] Pratyush Patel, Esha Choukse, Chaojie Zhang, Aashaka Shah, Íñigo Goiri, Saeed Maleki, and Ricardo Bianchini. Splitwise: Efficient generative llm inference using phase splitting. In 2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA), pages 118–132. IEEE, 2024. [32] Shishir G. Patil, Huanzhi Mao, Fanjia Yan, Charlie Cheng-Jie Ji, Vishnu Suresh, Ion Stoica, and Joseph E. Gonzalez. The berkeley function calling leaderboard (BFCL): From tool use to agentic evaluation of large language models. In Forty-second International Conference on Machine Learning, 2025. URL https://icml.cc/virtual/2025/poste r/46593. [33] Archit Patke, Dhemath Reddy, Saurabh Jha, Haoran Qiu, Christian Pinto, Chandra Narayanaswami, Zbigniew T. Kalbarczyk, and Ravishankar K. Iyer. Queue management for SLO-oriented large language model serving. In Proceedings of the 2024 ACM Symposium on Cloud Computing, pages 18–35, New York, NY, USA, 2024. Association for Computing Machinery. doi: 10.1145/3698038.3698523. [34] You Peng, Youhe Jiang, Wenqi Jiang, Chen Wang, and Binhang Yuan. Hexgen-flow: Optimizing llm inference request scheduling for agentic text-to-sql. arXiv preprint arXiv:2505.05286, 2025. [35] Haoran Qiu, Weichao Mao, Archit Patke, Shengkun Cui, Saurabh Jha, Chen Wang, Hubertus Franke, Zbigniew T. Kalbarczyk, Tamer Basar, and Ravishankar K. Iyer. Efficient interactive llm serving with proxy model-based sequence length prediction. In Proceedings of the 5th International Workshop on Cloud Intelligence / AIOps at ASPLOS 2024 (AIOps 2024), pages 1–7, San Diego, CA, USA, 2024. Association for Computing Machinery. [36] Haoran Qiu, Weichao Mao, Archit Patke, Shengkun Cui, Saurabh Jha, Chen Wang, Hubertus Franke, Zbigniew T. Kalbarczyk, Tamer Basa̧r, and Ravishankar K. Iyer. Efficient interactive LLM serving with proxy model-based sequence length prediction. In Proceedings of the 5th International Workshop on Cloud Intelligence / AIOps at ASPLOS 2024, New York, NY, USA, 2024. Association for Computing Machinery. URL https://haoran-qiu.com/publication/a splos-2024/.
18
[37] Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. In Advances in Neural Information Processing Systems, volume 36. Curran Associates, Inc., 2023. [38] Linus Schrage. A proof of the optimality of the shortest remaining processing time discipline. Operations Research, 16(3):687–690, 1968. [39] Rana Shahout, Eran Malach, Chunwei Liu, Weifan Jiang, Minlan Yu, and Michael Mitzenmacher. Don’t stop me now: Embedding based scheduling for LLMs, 2024. [40] John A. Stankovic, Marco Spuri, Krithi Ramamritham, and Giorgio C. Buttazzo. Scheduling in Real-Time Systems. Springer, Boston, MA, USA, 1998. [41] Biao Sun, Ziming Huang, Hanyu Zhao, Wencong Xiao, Xinyi Zhang, Yong Li, and Wei Lin. Llumnix: Dynamic scheduling for large language model serving. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), pages 173–191, Santa Clara, CA, July 2024. USENIX Association. ISBN 978-1-93913340-3. URL https://www.usenix.org/conference/osdi24/presentation/sun-biao. [42] Chris Tong, Youhe Jiang, Gufeng Chen, Tianyi Zhao, Sibian Lu, Wenjie Qu, Eric Yang, Lynn Ai, and Binhang Yuan. Parallax: Efficient llm inference service over decentralized environment. arXiv preprint arXiv:2509.26182, 2025. [43] Yujie Wang, Youhe Jiang, Xupeng Miao, Fangcheng Fu, Shenhan Zhu, Xiaonan Nie, Yaofeng Tu, and Bin Cui. Improving automatic parallel training via balanced memory workload optimization. IEEE Transactions on Knowledge and Data Engineering, 36(8):3906–3920, 2024. [44] Samuel Williams, Andrew Waterman, and David A. Patterson. Roofline: An insightful visual performance model for multicore architectures. Communications of the ACM, 52(4):65–76, 2009. doi: 10.1145/1498765.1498785. URL https://doi.org/10.1145/1498765.1498785. [45] Bingyang Wu, Yinmin Zhong, Zili Zhang, Gang Huang, Xuanzhe Liu, and Xin Jin. Fast distributed inference serving for large language models, 2023. [46] Ran Yan, Youhe Jiang, Zhuoming Chen, Haohui Mai, Beidi Chen, and Binhang Yuan. Fsa: An alternative efficient implementation of native sparse attention kernel. arXiv preprint arXiv:2508.18224, 2025. [47] Ran Yan, Youhe Jiang, Tianyuan Wu, Jiaxuan Gao, Zhiyu Mei, Wei Fu, Haohui Mai, Wei Wang, Yi Wu, and Binhang Yuan. Areal-hex: Accommodating asynchronous rl training over heterogeneous gpus. arXiv preprint arXiv:2511.00796, 2025. [48] Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. HotpotQA: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 2369–2380. Association for Computational Linguistics, 2018. doi: 10.18653/v1/D18-1259. URL https://aclanthology.org/D18-1259/. [49] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Advances in Neural Information Processing Systems, volume 36. Curran Associates, Inc., 2023. [50] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R. Narasimhan, and Yuan Cao. ReAct: Synergizing reasoning and acting in language models. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=WE_vluYUL-X. [51] Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung-Gon Chun. Orca: A distributed serving system for transformer-based generative models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), pages 521–538, Carlsbad, CA, July 2022. USENIX Association. ISBN 978-1-939133-28-1. URL https://www.usenix.org/conference/osdi22/presentation/yu. [52] Li Zhang, Youhe Jiang, Guoliang He, Xin Chen, Han Lv, Qian Yao, Fangcheng Fu, and Kai Chen. Efficient mixedprecision large language model inference with turbomind. arXiv preprint arXiv:2508.15601, 2025. [53] Yilong Zhao, Shuo Yang, Kan Zhu, Lianmin Zheng, Baris Kasikci, Yang Zhou, Jiarong Xing, and Ion Stoica. Blendserve: Optimizing offline inference for auto-regressive large models with resource-aware batching, 2024. [54] Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E. Gonzalez, Clark W. Barrett, and Ying Sheng. SGLang: Efficient execution of structured language model programs. In Advances in Neural Information Processing Systems, volume 37, Red Hook, NY, USA, 2024.
19
Curran Associates, Inc. URL https://papers.nips.cc/paper_files/paper/2024/hash/724be4472168f31ba1c9a c630f15dec8-Abstract-Conference.html. [55] Yinmin Zhong, Shengyu Liu, Junda Chen, Jianbo Hu, Yibo Zhu, Xuanzhe Liu, Xin Jin, and Hao Zhang. Distserve: Disaggregating prefill and decoding for goodput-optimized large language model serving. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), pages 193–210, Santa Clara, CA, July 2024. USENIX Association. ISBN 978-1-939133-40-3. URL https://www.usenix.org/conference/osdi24/presentation/zhon g-yinmin. [56] Andy Zhou, Kai Yan, Michal Shlapentokh-Rothman, Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning, acting, and planning in language models. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 62138–62160. PMLR, 2024. URL https://proceedings.mlr.press/v235/zhou24r.html.
20