TOPAS: Workflow-Aware Prefix-State Scheduling for Multi-Agent LLM Serving — L2 #

1. TL;DR #

Multi-agent serving faces a hard tradeoff: keeping an agent's long system-prompt KV resident speeds future calls but shrinks the batch. TOPAS scores post-decision GPU states $(R',Q')$ — jointly picking resident prefixes and admitted requests — by expected longest-remaining-path reduction plus one-hop reuse minus move/redo/revoke costs, cutting task JCT up to 39.8%/49.4%.

2. Q1 / Q2 / Q3 #

Q1 — 痛点 (problem) #

Under a shared KV budget, prefix residency and request admission are coupled but existing schedulers decide them separately. Two diagnostics isolate the failure. First, heterogeneous prefix co-residency shrinks the running batch: alternating between two agents' long prefixes divides KV capacity across both, halving mean batch size and inflating makespan 1.8–1.9× versus grouping (Table I). Second, the two natural fixes fail in complementary ways: locality-first (LPM) reactively keeps service pinned near the workflow entrance and starves downstream stages, while progress-first (SRPT) chases the shortest remaining work and thrashes prefixes with repeated setup costs. Formally, the objective is to minimize average task-level JCT:

$$C(J_i) = \max_{v \in V} C_{i,v}, \qquad \mathrm{JCT}(J_i) = C(J_i) - \tau_i,$$

subject to the joint prefix–request KV constraint $\sum_{a \in R'} \ell_a + \sum_{r \in Q'} d_r(t) \leq B_t$, where static prefix cost $\ell_a$ is paid once per agent (the reuse benefit) and $d_r(t)$ is each request's dynamic footprint.

Q2 — 方法 (method) #

TOPAS treats prefix residency as an explicit workflow-level decision, jointly optimized with admission rather than left as a byproduct of request ordering and cache eviction. At each scheduling event it constructs candidate post-decision states $S'=(R',Q')$ and commits the arg-max of a transition Score (Eq. 13) combining: (i) age-weighted expected reduction in each task's longest remaining LLM-service path, (ii) a one-hop reuse bonus for prefixes about to serve soon-ready downstream stages, minus (iii) prefix-movement, redo (re-decode), and revoke (credit-clawback) costs. A hierarchical search (GREEDYPACK for request allocation + prefix-set enumeration/bounded greedy) makes the combinatorial joint decision tractable.

核心技术壁垒: the load-bearing insight is valuing an admitted request not by its own service time but by the expected reduction of its task's longest remaining service path, with the expectation placed outside the longest-path operator $\mathbb{E}_{Z_i(H,t)}[\mathrm{LP}(G, Z_i(H,t))]$ (Eq. 5). This lets the DAG critical path change across residual realizations rather than being fixed by mean stage durations, so non-bottleneck-branch work correctly scores zero progress. Reproducing TOPAS's numbers hinges on computing this path-marginal — not the modular scoring skeleton — correctly under empirical ReAct residual distributions.

Q3 — 结果 (results) #

Implemented in SGLang v0.5.3 on one A100-80GB with Qwen2.5-32B-Instruct. Against the best baseline per workload and metric: synthetic DAGs cut mean/p99 JCT by 27.5%/31.7% (Chain-3), 39.8%/49.4% (DAG-4), 27.7%/30.8% (DAG-10-Wide); MetaGPT-SOP mean −9.8% (p99 −4.5%); MetaGPT-TL mean/p99 −22.0%/−26.6%. Scheduling overhead is 1.9 ms/decision, 0.31% of wall time. Ablation: the full policy beats TOPAS-base by 60.5%/53.6% mean/p99 on MetaGPT-TL.

3. 架构 / 方法图 #

TOPAS's mechanism is best seen in the motivating Gantt chart, which shows why neither pure policy is sufficient on an A→B→C chain when GPU memory holds only one prefix at a time.

Paper's Figure 2 (caption: "A Gantt chart comparing LPM and SRPT on an A →B →C workflow. GPU memory can hold the KV cache for only one Agent prefix at a time; each request takes four time units, and each prefix setup takes one time unit.").

Each request is 4 time units and each prefix setup is 1. SRPT pushes one task to the exit but pays a setup on every stage transition (mean JCT 21.5); LPM batches same-prefix requests to amortize setup but holds service upstream and delays completion (mean JCT 24). Notably the toy favors SRPT on mean JCT — the paper's point is not that SRPT is uniformly worse but that both extremes leave value on the table, which motivates scoring both progress and reuse in one decision.

The mechanism generalizes into a per-event pipeline: enumerate/greedily grow a resident-prefix set $R'$, pack compatible requests $Q'$ under the KV budget, score the transition, and commit the best feasible state.

4. 作者证明 #

TOPAS has no formal convergence/optimality theorem — it is a heuristic online policy. Its rigor lives in the utility construction, which I verify against the 6 minimum checks plus the algorithm-specific asks below.

Notation table

方程物理意义 (loss/utility decomposition) — the maximized Score is a sum of four physically distinct terms, all in seconds:

$$\mathrm{Score}(S' \mid S_t) = J^{\text{age}}_{\text{admit}} - J_{\text{move}} - J_{\text{redo}} - J_{\text{revoke}} + V_{\text{reuse}}.$$

1. $J^{\text{age}}_{\text{admit}}=\sum_{r\in A} g_{\text{task}(r)}(t)\,\Delta_{\text{task}}(r\mid A^{task progress — reward for advancing the critical path, boosted for old tasks.
2. $J_{\text{move}}=T_{\text{move}}\,|T_{\text{in}}|$ with $T_{\text{move}}=\frac{\mu}{B_{\text{swap}}}(\sum_{R_{\text{out}}}\ell_a+\sum_{R_{\text{in}}}\ell_a)$ charges prefix-swap delay, once per waiting task.
3. $J_{\text{redo}}=\sum_{r\in P} T_{\text{decode}}\,y_r(t)$ charges re-decode of preempted tokens.
4. $J_{\text{revoke}}=\sum_{r\in P}\lambda_r$ claws back admission credit so an unfinished attempt can't repeatedly collect value.
5. $V_{\text{reuse}}=\beta\sum_{a\in R'} n_a(t)\frac{\mu\ell_a}{B_{\text{swap}}}$ rewards retaining an expensive prefix about to be reused by $n_a$ soon-ready stages.

6 minimum checks

1. Dimensional consistency — every term reduces to seconds: $\Delta_{\text{task}}$ is a path-length in service seconds; $\mu/B_{\text{swap}}$ converts prefix tokens (bytes) to transfer seconds; $T_{\text{decode}}\,y_r$ is seconds. ✓
2. Boundary behavior — a stage that is completed contributes residual zero; an unstarted stage contributes its full $X_{i,v}$; non-bottleneck branch gives $\Delta_{\text{task}}=0$ (Eq. 6). Consistent limits. ✓
3. No double counting — sequential residual updates via $A^{
4. Cost/benefit sign convention — benefits ($J_{\text{admit}}, V_{\text{reuse}}$) enter with $+$, transition costs with $-$; maximizing Score maximizes net second-savings. ✓
5. Feasibility preserved — GREEDYPACK admits only under the Eq. (2) constraint and reserves capacity for each uncovered prefix, so every candidate in $\hat{C}_t$ is feasible by construction. ✓
6. Reduction to known case — on a chain, $\hat{L}_i$ collapses to the current stage's residual, so $\Delta_{\text{task}}$ becomes expected residual reduction and the policy degenerates toward SRPT-with-setup-awareness. ✓

Algorithm-specific structure (objective, residual model, complexity, proof sketch)

• Objective (exact) — minimize average $\mathrm{JCT}(J_i)=\max_v C_{i,v}-\tau_i$ (Eq. 1); the policy's per-event surrogate is Score (Eq. 13). No closed-form reward beyond this.
• Residual model / assumptions — Eq. (4) $Z_{i,v}(t)\overset{d}{=}X_{i,v}-e_{i,v}(t)\mid X_{i,v}>e_{i,v}(t)$ conditions repeated ReAct rounds on observed service without assuming a fixed round count. Key assumption: unfinished-stage residuals are modeled independently conditioned on history (Eq. 5). This breaks when ReAct rounds within an agent are correlated (e.g. a hard sub-task inflates every stage of one agent) — flagged in the paper's own surprise list, not rebutted.
• Complexity bound — hierarchical search is $O(|A_t|^2)$ prefix-set evaluations for large pools (bounded greedy with pair-repair), and full $\mathcal{P}(A_t)$ enumeration only when $|A_t|\le M$. This is a runtime bound, not a sample-complexity bound.
• Proof sketch (progress additivity) — because LP is evaluated in reverse topological order and residuals are updated sequentially after each hypothetical completion, the telescoping $\sum_r [\hat{L}_i(A^{
• Desirable-but-absent guarantee — no bound on JCT competitive ratio vs the offline optimum; given online arrivals and unknown ReAct rounds, even a $O(\log)$-competitive guarantee would strengthen the claim but is not attempted.

5. 实验与数据 #

Diagnostic 1 (Table I) — the empirical anchor for the whole motivation. GROUPED (serve one agent's requests together) vs ALTERNATING (A,B,A,B…) under FCFS, same requests and KV budget:

Load	Makespan (s) G/A	Mean batch G/A	Peak batch G/A
$n=100$	1145.5 / 2086.0	9.3 / 4.7	15 / 8
$n=150$	1639.3 / 3104.4	10.0 / 4.8	16 / 8
$n=200$	2143.5 / 4079.1	11.5 / 5.0	16 / 7

Grouping roughly doubles mean batch size and nearly halves makespan — a resident prefix supports a bigger batch, whereas two co-resident long prefixes starve dynamic/decode KV.



Paper's Figure 1 (caption: "Chain-3 at 0.15 task/s under locality-first LPM, progress-first SRPT, and downstream gating.").

Across the four panels (mean JCT, p99 JCT, first-task completion, throughput), the coarse downstream-gated "Strawman" beats both pure LPM and pure SRPT on mean JCT — direct evidence that active residency control, not either extreme, is what pays off.



Paper's Figure 3 (caption: "End-to-end task completion on the synthetic DAG workloads.").

Six panels sweep arrival rate for Chain-3 / DAG-4 / DAG-10-Wide (mean and p99). TOPAS (the load-bearing result) sits below all six baselines — FCFS, Autellix-LAS, LPM, SPF/SRPT, Parrot-FCFS — with the largest margin on DAG-4 (fork/join), where prefix-state pressure is highest and explicit residency control has the most room.



Paper's Figure 4 (caption: "Task completion on the MetaGPT workloads; high-load Autellix-LAS values exceed the displayed MetaGPT-TL range.").

On real MetaGPT prompts, gains are workload-topology dependent: SOP (one-pass five-role pipeline) yields only −9.8% mean, and TOPAS is not best on SOP p99 (LPM wins) or throughput (Autellix-LAS wins) — an honestly reported loss. TL (recurrent TeamLeader central prefix) yields −22.0%/−26.6%, because repeatedly returning to a central agent creates more residency-control opportunities.



Paper's Figure 5 (caption: "MetaGPT-TL component ablation at 0.0175 task/s.").

Four bars (TOPAS-base, w/o reuse, w/o aging, full) show the full policy beats base by 60.5%/53.6% mean/p99, and each single-component variant still trails the full policy by 44.2–51.0%. Both the reuse lookahead (IV-C) and aging (IV-D) carry weight — surprisingly large for components described as add-ons.

6. 论证链 #

Step	Claim	Paper-internal support
1	Under a shared KV budget, heterogeneous prefix co-residency shrinks the running batch and inflates makespan 1.8–1.9×.	Table I (Diagnostic 1): GROUPED mean batch ≈2× ALTERNATING.
2	Therefore a reactive locality-first policy (LPM) that just chases resident prefixes stalls downstream stages; a progress-first policy (SRPT) that chases shortest remaining work thrashes prefixes.	Fig. 1 (Strawman beats both on mean JCT); Fig. 2 Gantt (setup cost per SRPT transition; LPM holds upstream).
3	Hence prefix residency must be an explicit, jointly-scheduled decision; formalize state $S'=(R',Q')$ and score it by expected longest-remaining-path reduction (Eq. 5–6) plus reuse (Eq. 11) minus transition costs (Eq. 8–10).	§III constraint (Eq. 2) + §IV Score (Eq. 13); GREEDYPACK + $O(	A_t	^2)$ search keep it feasible and cheap.
4	The resulting event-level arg-max policy (Eq. 14) reduces task-level JCT over the best per-metric baseline, most on high-residency-pressure topologies.	Fig. 3 (−39.8%/−49.4% on DAG-4), Fig. 4 (−22.0%/−26.6% on MetaGPT-TL).
5	Both non-base components are necessary, not decorative.	Fig. 5 ablation: full vs base −60.5%/−53.6%; each single-component variant trails by 44.2–51.0%.

7. 实现 cross-reference #

Implemented as a scheduling module in SGLang v0.5.3 (§V-A); the paper does not release a public repository, so exact source lines are [实现未公开]. The design binds tightly to SGLang mechanisms that a re-implementer must respect:

• Radix-tree prefix cache (§I): resident-prefix set $R'$ maps to static paths in SGLang's radix tree; the "static prefix cost paid once per agent" (Eq. 2) is exactly radix-tree sharing.
• Preemption = autoregressive reconstruction (§IV-B para 8): SGLang rebuilds a preempted request's generated-token KV by re-decoding, which is why $J_{\text{redo}}=\sum_{r\in P}T_{\text{decode}}\,y_r(t)$ charges per-token decode, not a flat recompute.

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

1. Aging weights only the benefit, never the costs — $g_i(t)=1+\rho\log(1+\frac{t-\tau_i}{H_{\text{age}}})$ scales $J_{\text{admit}}$ but $J_{\text{move}}/J_{\text{redo}}/J_{\text{revoke}}$ stay un-aged (§IV-D). A naive implementation that multiplies the whole Score by $g_i$ would distort the seconds-denominated cost balance and break the anti-starvation intent.
2. Stored credit uses the admission-time weight — $\lambda_r=\Delta_{\text{task}}(r\mid A^{