HexAGenT — Workflow- & Heterogeneity-Aware Agentic LLM Serving #

1. TL;DR #

Agentic requests are multi-call DAGs revealed online; users feel end-to-end workflow latency, not per-call latency. HexAGenT maintains a per-workflow standalone horizon $H_w(t)$, ranks ready calls by projected scaled-SLO risk, and jointly picks prefill/decode placement + queue priority on heterogeneous A100/H100/H200 P-D clusters. It cuts the SLO scale for timely completion by 13–24% on average.

2. Q1 / Q2 / Q3 #

Q1 — 痛点 (Pain point) #

The scheduling unit for LLM serving has shifted. A single user request now expands into a workflow of many dependent LLM calls (planning → tool use → branching → refinement → synthesis), and the user experiences the end-to-end workflow completion time, not any single call's latency. Three coupled difficulties make this hard on a prefill-decode (P-D) disaggregated, heterogeneous cluster:

1. Online-revealed structure. The workflow is a DAG in which only source nodes are visible at arrival; a child becomes schedulable only after all parents complete or tools return. The scheduler must act under partial information.
2. Heterogeneity coupled to structure. Calls in the same workflow differ in prompt length, output length, and KV demand; prefill and decode instances differ in compute speed, memory capacity, and cross-hardware transfer cost.
3. Local objectives conflict with global structure. Per-call policies (FCFS, queue-length balancing) reduce local waiting yet delay a workflow's critical path, hurting end-to-end SLO attainment.

Existing execution substrates (vLLM, SGLang), disaggregation systems (DistServe, Splitwise), and program-aware schedulers (Parrot, Autellix, Continuum) each supply building blocks, but none jointly handle online-revealed DAGs, heterogeneous P-D placement, decode-capacity constraints, stage coupling, and non-blocking runtime overhead.

Q2 — 方法 (Method) #

HexAGenT abstracts each request as an online-revealed DAG $G_w(t)$ and maintains a running standalone completion horizon $H_w(t)$: the makespan of the revealed subgraph if it were run alone on the same cluster. This horizon is the workflow's live SLO target. For each ready call it computes a projected ratio $R_s(c,t)$ (§5) that normalizes projected completion pressure by $H_w(t)$, ranks calls by that risk, greedily picks the most urgent, and jointly chooses (i) the prefill/decode instance pair and (ii) stage-local queue priority — while respecting decode KV capacity and KV-transfer latency. Planning is asynchronous: at most one plan is in flight, serving never blocks, and late plans apply only to calls still waiting.

核心技术壁垒 (hardest-to-replicate insight): the joint, decode-anchored prefill placement. HexAGenT does not just rank which call is urgent — for the urgent call it selects the prefill/decode pair that minimizes the projected normalized decode-finish time, pre-committing the downstream decode instance before prefill even completes so the KV transfer target is fixed. This couples urgency signal, heterogeneous per-instance service times, and cross-hardware transfer bandwidth into one greedy decision that self-corrects via recomputation after each assignment. Reproducing it requires a faithful roofline estimator plus the exact "plan-then-lock" runtime semantics; a naive urgency-only scheduler misses most of the tail gain.

Q3 — 结果 (Results) #

• Characterization (§3, Table 1): workflow-FCFS beats per-call FCFS by 31.4% Req95 / 23.3% Req99 avg; HexAGenT beats workflow-FCFS by a further 26.9% Req95 / 42.6% Req99.
• Heterogeneous main (Table 2): avg reduction 13.0% Req95 / 24.5% Req99 vs the strongest per-trace baseline; even weakest case (Llama Hetero-2) still 6.1% / 13.9%.
• Largest tail win: Qwen Hetero-1 Mixed, Req99 8.96 → 3.94 (56.0%).
• Homogeneous (Table 4): Llama H200 24.8% / 36.8%; Qwen A100 23.1% / 33.9% — gains do not depend on hardware heterogeneity.
• Robustness (Table 5): ≤1.5% Req99 degradation for Llama even at 30% estimate error.
• Overhead (Table 6): 7.1–14.7 ms/invocation avg, worst per-invocation average 23.7 ms, fully hidden by async planning.

3. 架构 / 方法图 #

The online-revealed workflow #

Only source calls are known at arrival; the DAG grows as parents and tools complete.



Paper's Figure 1 (caption: "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."). The figure shows how nested agent-tool-agent chains, bounded self-refinement, and parallel sibling branches all map to one DAG whose runnable frontier is the scheduler's true decision surface — every scheduling invocation acts only over currently revealed, dependency-satisfied calls.

System architecture and scheduler placement #



Paper's Figure 2 (caption: "System architecture and scheduler placement of HexAGenT. 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."). Note the four scheduler modules: State Collector (snapshots prefill/decode queues, KV usage, transfer state, workflow progress), Estimator (roofline-style prefill/decode/transfer time + KV demand), Joint Planner (picks P-D pair + local priority), Plan Dispatcher (pushes placement/priority updates to workers). The feedback loop makes re-scheduling event-driven rather than periodic.

The agent turn loop #

Each call travels one full lifecycle; runtime events (arrival, prefill-done, transfer-done, decode-done) drive re-scheduling. Once a call starts prefill or decode, its placement is locked.

stateDiagram-v2 [*] --> Revealed: workflow arrival / parent completes Revealed --> WaitPrefill: enter global waiting set WaitPrefill --> Prefill: scheduler assigns P-D pair + priority Prefill --> Transfer: prefill done (placement locked) Transfer --> WaitDecode: KV moved to planned decode instance WaitDecode --> Decode: capacity-feasible admission Decode --> Complete: decode done -> update workflow state Complete --> Revealed: reveal newly unblocked children Complete --> [*]: workflow fully complete WaitPrefill --> Fallback: plan in flight -> safe fallback policy Fallback --> WaitPrefill: async plan applied if still waiting

The fallback edge is the error-recovery path: if a solve is in flight when a new call arrives, the call temporarily follows a safe policy; the late plan is applied only if service has not yet started, otherwise runtime state is authoritative and the plan is ignored for that stage.

4. 作者证明 #

无形式化作者证明 — 仅实证. The paper frames an online workflow scheduling problem but gives no convergence, competitive-ratio, or optimality guarantee for the greedy algorithm; all support is empirical. What could have been bounded: the competitive ratio of greedy projected-risk ordering against the offline optimal makespan, or a regret bound on horizon mis-estimation. Neither is attempted.

The formal content is definitional. Notation table:

Symbol	Meaning
$\pi$	scheduling policy
$\alpha$	SLO scale factor (minimized)
$\mathcal{W},\,	\mathcal{W}	$	set of workflows and its cardinality
$C_w^{\pi}$	end-to-end completion time of $w$ under $\pi$
$H_w(t),\,H_w$	online / final standalone horizon of $w$
$\tau$	target attainment level (0.95 or 0.99)
$a_w$	workflow arrival time
$R_s(c,t)$	projected ratio for call $c$ at stage $s$, time $t$
$\Delta_s(c,t)$	projected elapsed time to finish $c$ at stage $s\in\{\text{Prefill},\text{Decode}\}$
$m(c)$	decode KV demand of call $c$ (tokens)
$L_{\mathrm{in}}(c),\,\widehat{L}_{\mathrm{out}}(c)$	input length, predicted output length
$\mathrm{Cap}(d)$	decode KV capacity of instance $d$

Objective (Eq. 1):

$$\min_{\pi}\;\alpha\quad\text{s.t.}\quad\frac{1}{|\mathcal{W}|}\sum_{w\in\mathcal{W}}\mathbbm{1}\!\left[C_{w}^{\pi}\leq\alpha H_{w}\right]\geq\tau.$$

Physical meaning: minimize the multiplicative SLO slack $\alpha$ such that at least a $\tau$-fraction of workflows finish within $\alpha H_w$. This targets tail attainment (Req95/Req99), deliberately not average latency.

Projected ratio (Eq. 2):

$$R_{s}(c,t)=\frac{(t-a_{w})+\Delta_{s}(c,t)}{H_{w}(t)}.$$

Physical meaning: normalized completion pressure — (elapsed + projected-remaining) over the current horizon. Larger $R_s$ ⇒ the workflow is projected closer to (or past) its target ⇒ more urgent. Dividing by $H_w(t)$ makes urgency comparable across workflows of different sizes.

Decode demand and feasibility (Eqs. 3–4):

$$m(c)=L_{\mathrm{in}}(c)+\widehat{L}_{\mathrm{out}}(c),\qquad m(c)\leq\mathrm{Cap}(d).$$

Physical meaning: KV footprint is approximated as prompt + proxy-predicted generation length; a call is admissible on decode instance $d$ only if that footprint fits $d$'s KV capacity. This makes decode memory a first-class capacity constraint, not an afterthought.

6 minimum checks:

1. Eq. 1 well-posed? Yes — for finite $C_w^{\pi}$ and $H_w>0$ there always exists a large enough $\alpha$ satisfying any $\tau\le 1$, so the min is attained.
2. Eq. 2 dimensionless? Yes — numerator and denominator are both times, so $R_s$ is unitless, consistent with cross-workflow comparison.
3. Monotonicity of urgency: $R_s$ increases with elapsed time $(t-a_w)$ and with $\Delta_s$, decreases with a larger horizon $H_w(t)$ — matches the stated "closer to target ⇒ more urgent."
4. Eq. 3 unit consistency: $m(c)$ in tokens = tokens + tokens; Eq. 4 compares tokens to capacity in tokens. Consistent.
5. Horizon growth direction: revealing a call can only add work to $G_w(t)$, so $H_w(t)$ is non-decreasing until true service times correct it — consistent with "SLO target grows accordingly."
6. Greedy self-consistency (Alg. 1 lines 13–21): recomputing $R_s$ after each assignment (updating simulated state $\hat S$) is necessary because the best pair for the next call depends on prior assignments in the same solve — the loop reflects this dependency.

5. 实验与数据 #

Characterization: two axes are both necessary #



Paper's Table 1 (Req95/Req99, lower is better). The two-step ladder is the load-bearing motivation: per-call FCFS → workflow-FCFS isolates Insight 1 (workflow ordering matters: e.g. Qwen-BFCL Req95 21.11 → 9.64), and workflow-FCFS → HexAGenT isolates Insight 2 (heterogeneous placement on top: Qwen-Mixed Req95 10.30 → 3.48). Each cell moving strictly down-and-right confirms the axes are complementary, not redundant.

End-to-end heterogeneous SLO curves #



Paper's Figure 3 (x = SLO scale $\alpha$, y = fraction of workflows with $C_w\le\alpha H_w$; higher-left is better). HexAGenT's curve sits left of all baselines, most dramatically on Qwen and Mixed/LATS traces — meaning it reaches high attainment at a tighter SLO than the strongest baseline can.

Averaged and detailed heterogeneous results #



Paper's Table 2. Averaged over ShareGPT/BFCL-v3/LATS/Mixed against the per-trace strongest baseline; reductions grow with model cost (Qwen Hetero-1: 21.1% / 33.1%), showing the benefit is largest when workflow pressure meets expensive execution.



Paper's Table 3. The per-trace breakdown localizes the gain: Mixed drives the headline (Req99 56.0%), while BFCL-v3 Req95 is only 5.7% because Workflow-LLF already captures most urgency for short tasks — yet HexAGenT still wins the tail (Req99 23.0%) via better P-D placement.

The gain source is explicit: Workflow-LLF captures urgency but does not evaluate which P-D pair minimizes projected normalized completion after accounting for heterogeneous service and transfer-induced decode-ready times; Autellix-ATLAS tracks attained service, which is not the same as risk of exceeding a workflow-specific horizon.

Homogeneous check (no heterogeneity to exploit) #



Paper's Table 4. Even with identical instances (Llama H200, Qwen A100), workflow-aware ordering alone yields 23–37% reductions — the method is not purely a heterogeneity trick.

Robustness to estimation error #



Paper's Table 5 (% degradation vs 0% error). Llama stays within 1.5% Req99 even at 30% error. Two surprises: Qwen Req99 degradation is non-monotonic (largest 9.5% at only 10% error, dropping to 5.4% at 30%), and several Qwen Req95 entries are negative (noisy estimate → slightly better greedy order); the authors treat these as near-ties, evidence that the scheduler is driven by workflow priorities rather than exact per-call durations.

6. 论证链 #

#	Step	Support (paper-internal)
1	Users experience end-to-end workflow latency, so the scheduling unit must be the workflow, not the call.	§1 framing; §2 request-centric limitation
2	Per-call FCFS therefore leaves large SLO scales on tail workflows; switching to workflow-level ordering already cuts Req95/Req99 substantially.	§3 Insight 1, Table 1 (Qwen-BFCL 21.11→9.64)
3	Workflow ordering alone is insufficient because calls and hardware are heterogeneous; adding heterogeneity-aware P-D placement cuts the scale again.	§3 Insight 2, Table 1 (Qwen-Mixed 10.30→3.48)
4	To do both jointly, formalize a per-workflow horizon $H_w(t)$ and rank ready calls by the normalized projected ratio $R_s(c,t)$ (Eq. 2).	§5.1 Eqs. 1–2
5	Greedily pick argmax $R_s$, assign the P-D pair with earliest projected decode finish, recompute after each assignment, respect decode KV capacity (Eqs. 3–4), and apply the plan asynchronously.	§5.2 Alg. 1; §5.3–§5.4
6	The resulting system lowers tail SLO scales across heterogeneous and homogeneous clusters, is robust to estimate error, and its planning cost is hidden by async application.	§7.4–§7.7, Tables 2–6

7. 实现 cross-reference #

Built on SGLang v0.5.9 using its P-D disaggregated serving feature; scheduling policy is kept outside GPU kernels and the hot decode loop, integrated into the gateway/worker path (§6). Router-side changes: workflow metadata parsing, stage-state construction, async plan application, revision checks for safe queue mutation, bootstrap metadata injection, completion feedback accounting. Worker-side: expose P-D snapshots, accept priority/reassignment updates for still-waiting requests, report completion telemetry. A standalone Python event-driven simulator (~4.6K LoC across runtime, scheduler, runners) acts as the resource estimator, modeling the full call lifecycle and computing $H_w$ and the projected ratios via a roofline-style latency model.

[实现未公开] — no code repository URL is exposed in the source; the above is the paper's own implementation description.

核心技术壁垒 (elaboration): the joint plan-then-lock semantics. HexAGenT commits a planned decode instance during prefill scheduling so the KV-transfer target is known before prefill completes (§5.3), and once prefill or decode starts, placement is immovable (§5.2). Getting this right requires the async solver to reconcile a "plan in flight" against runtime authority (Alg. 1 lines 5–8, 23) — the hardest engineering surface to replicate, and the one that converts an offline greedy ranking into a non-blocking online scheduler.

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

1. Adaptive greedy vs one-pass fallback: for small stage queues HexAGenT does recomputing greedy (re-rank after each assignment); for large queues it degrades to a single-pass ordering by the same risk score to keep per-invocation overhead bounded (§5.3–§5.4). This queue-size switch is what keeps the 7–15 ms/invocation cost stable under load.
2. Decode instance locks vs free calls: a call locked to a decode instance during prefill can be reordered within that instance but cannot migrate across decode instances; only unlocked calls are freely placeable (§5.4). Missing this distinction breaks the KV-transfer contract.