One-sentence Summary

Researchers from Shanghai Jiao Tong University and Stanford University propose TAO, a tool-aware joint scheduling framework for LLM-based agentic serving that combines near-term tool readiness, node-specific cache credit with time-aware decay, and token footprint in a dynamic program to jointly select and place waiting sessions under capacity constraints, achieving across the 12 reported model-workload-concurrency settings up to $26.8\%$26.8% lower latency, up to $36.3\%$36.3% lower mean time to first token, and up to $29.5\%$29.5% higher decode throughput relative to the best evaluated state-of-the-art baseline for each metric.

Key Contributions

• TAO is a tool-aware joint scheduling framework for LLM-based agentic serving that combines near-term tool readiness, node-specific cache credit with time-aware decay, and token footprint into a unified session value interface.
• A dynamic program jointly selects and places waiting agent sessions under snapshot capacity constraints, while session interruption and asynchronous revalidation connect the resulting admission and placement plan to live execution.
• Across 12 reported model-workload-concurrency settings, TAO reduces latency by up to 26.8%, mean time to first token by up to 36.3%, and decode throughput by up to 29.5% relative to the best evaluated state-of-the-art baseline for each metric.

Introduction

The authors study LLM-based agent serving in a Clustered-GPUs with Distributed-CPUs (CGDC) scenario, where external tool calls create variable gaps between inference requests and make GPU demand interruptible. This matters because tool execution now contributes substantial latency, so scheduling must account for both inference capacity and when sessions will need GPU resources again. Prior systems typically use evaluate-then-decide heuristics that value sessions individually and treat tool timing mainly as a surrogate for KV-cache reuse or token count, leading to myopic and suboptimal placement when sessions compete for shared capacity. The authors propose TAO, a tool-aware joint scheduling framework that introduces tool-return readiness into session evaluation and uses dynamic programming to jointly optimize admission and placement across the waiting pool, improving latency, TTFT, and decode throughput over state-of-the-art baselines.

Method

The authors present TAO, a framework that combines agentic session evaluation with decision making via dynamic programming for joint selection and placement. The pipeline separates session evaluation from decision making, allowing the evaluation interface to evolve while preserving the scheduling procedure. As shown in the figure below:

At each restart scheduling decision, the waiting pool $P$P contains agent sessions awaiting inference admission, including interrupted sessions and new arrivals. Let $B$B be the nodes in the frozen snapshot. Each agent session $i$i has an admission cost $w_i$wi​, and each node $b$b has residual capacity $C_b$Cb​. Let $E \subseteq P \times B$E⊆P×B denote eligible assignments, and let $x_{i,b} \in \{0, 1\}$xi,b​∈{0,1} indicate whether session $i$i is admitted to node $b$b. The feasible set is defined as:

$$\mathcal{X} = \left\{x: \sum_{b \in B} x_{i, b} \leq 1, \quad \sum_{i \in P} w_{i} x_{i, b} \leq C_{b}, \quad x_{i, b} = 0 \text{ if } (i, b) \notin E \right\}.$$X={x:b∈B∑​xi,b​≤1,i∈P∑​wi​xi,b​≤Cb​,xi,b​=0 if (i,b)∈/E}.

TAO assigns each agent session-node pair a lexicographic value triplet:

$$\boldsymbol{v}_{i, b} = (k_{i, b}, r_{i}, t_{i}),$$vi,b​=(ki,b​,ri​,ti​),

where $k_{i,b}$ki,b​ is the decayed cache credit, $r_i$ri​ is the binary readiness signal, and $t_i$ti​ is the token count. The system jointly selects and places sessions to maximize their aggregate value:

$$x^{\star} \in \arg \operatorname{lexmax}_{x \in \mathcal{X}} \sum_{i \in P} \sum_{b \in B} x_{i, b} \boldsymbol{v}_{i, b}.$$x⋆∈arglexmaxx∈X​i∈P∑​b∈B∑​xi,b​vi,b​.

The evaluation triplet order remains fixed while its values evolve over time. KV-Cache credit takes precedence because prefix reuse directly avoids repeated prefill. As unrefreshed credit decays, tool-return readiness distinguishes agent sessions nearing a return from those still far from their next model turn. Finally, token footprint favors larger accumulated contexts among plans tied on cache credit and readiness.

To estimate reusable KV state, TAO uses an observed cached-token count or estimates it from observed token volume and cache rate. The decline in cache-token retention over time motivates discounting older observations, as illustrated in the figure below:

Older observations receive less credit according to the time-aware decay formula:

$$\begin{array}{l} k_{i, b}(t) = k_{i, b}^{0} 2^{-\tau_{i, b} / h}, \\ \tau_{i, b} = \max(0, t - t_{i, b}^{\mathrm{obs}}). \end{array}$$ki,b​(t)=ki,b0​2−τi,b​/h,τi,b​=max(0,t−ti,bobs​).​

Here $k_{i, b}^{0}$ki,b0​ is the observed cache credit and $h$h is its decay half-life, set to 10 seconds. This discount makes the admission value responsive to observation age.

For tool-return readiness, the predictor combines hints from parsed sleep commands and historical tool durations. For a call with elapsed time $e_i(t)$ei​(t), the historical estimate $\widehat{D}_f$Df​ gives:

$$\widehat{d}_{i}(t) = \max\{0, \widehat{D}_{f} - e_{i}(t)\}.$$di​(t)=max{0,Df​−ei​(t)}.

Binary readiness is defined as:

$$r_{i}(t) = \left\{ \begin{array}{l l} 1, & o_{i}(t) = 1, \\ a_{i}(t) b_{i}(t), & o_{i}(t) = 0, z_{i}(t) \leq t, \\ a_{i}(t) g_{i}(t) \mathbf{1}[z_{i}(t) \leq t + H], & \text{otherwise}. \end{array} \right.$$ri​(t)=⎩⎨⎧​1,ai​(t)bi​(t),ai​(t)gi​(t)1[zi​(t)≤t+H],​oi​(t)=1,oi​(t)=0,zi​(t)≤t,otherwise.​

Here $o_i(t)$oi​(t) indicates observed tool completion, $a_i(t)$ai​(t) indicates an established tool execution candidate, and $g_i(t)$gi​(t) indicates valid prediction timestamps. $z_i(t)$zi​(t) is the predicted completion or exposed return deadline, and $H$H is the horizon set to 1 second. Observed completion takes precedence over prediction checks.

The optimizer is a capacity-state dynamic program for the multiple-knapsack and generalized assignment structure. Let $\Delta$Δ be the capacity quantum, $\bar{w}_i = \lceil w_i / \Delta \rceil$wˉi​=⌈wi​/Δ⌉, and $\bar{C}_b = \lfloor C_b / \Delta \rfloor$Cˉb​=⌊Cb​/Δ⌋. For candidate $j$j, let $D_j(\boldsymbol{s})$Dj​(s) be the best objective attainable from the first $j$j candidates at the used capacity $\boldsymbol{s}$s, and let $\boldsymbol{u}_{j,b}$uj,b​ embed the value and count for assigning $j$j to node $b$b:

$$D_{j}(\boldsymbol{s}) = \text{lexmax} \left\{D_{j-1}(\boldsymbol{s}), \max_{b \text{ eligible}}^{\text{lex}} \left[ D_{j-1}(\boldsymbol{s} - \bar{w}_{j} \boldsymbol{e}_{b}) + \boldsymbol{u}_{j, b} \right] \right\}.$$Dj​(s)=lexmax{Dj−1​(s),b eligiblemaxlex​[Dj−1​(s−wˉj​eb​)+uj,b​]}.

Only nonnegative states within $\bar{C}$Cˉ are allowed. Skipping or assigning each candidate exhausts the feasible choices, providing exactness for the frozen, discretized problem. Node-specific cache observations are decayed and folded into assignment values during preprocessing, and cache-equivalent nodes can be grouped into aggregate capacity dimensions. The planner runs in an isolated asynchronous worker and revalidates before application.

Experiment

The experiments evaluate TAO against vLLM round-robin and cache-aware schedulers, Dynamo, and ThunderAgent across DeepSeek-V4 Flash, Qwen3-32B, and GLM-4.7 on agentic workloads including SWE-bench Lite, SWE-verified, and Terminal-Bench 2.0. Across models, concurrency levels, and topologies, TAO consistently achieves the strongest overall tradeoff among task latency, time to first token, and decode throughput. Component breakdowns show that cache-aware valuation, tool readiness signals, and joint scheduling each improve cache reuse, reduce pause wait, and accelerate model responses after tool completion. Ablations further confirm that removing any of these components reduces throughput, cache hit rate, and responsiveness, validating the combined design.

TAO is the strongest overall choice across the tested models, concurrency levels, and topologies, combining consistently low latency and TTFT with higher decode throughput. On DeepSeek-V4 Flash, it improves latency, TTFT, and decode throughput on SWE-Lite and leads latency and TTFT on Terminal-Bench. On Qwen3-32B, it leads TTFT and decode throughput at higher worker counts, with latency reductions on most SWE-verified settings. TAO improves latency, TTFT, and decode throughput on DeepSeek-V4 Flash SWE-Lite relative to the best competing method at each worker count shown. On Qwen3-32B SWE-verified, TAO has the lowest TTFT and highest decode throughput across worker counts and reduces latency at most evaluated settings.

In a high-concurrency GLM-4.7 setting on one node with eight H100s, TAO outperforms ThunderAgent and other vLLM-based schedulers on SWE-Lite, with the largest relative gains at 160 workers. The pattern includes lower mean latency and client TTFT alongside higher decode throughput. On the full SWE-verified set, TAO similarly reduces latency and TTFT while increasing decode throughput compared with ThunderAgent. TAO achieves lower latency, lower TTFT, and higher decode throughput than ThunderAgent across all reported SWE-Lite worker counts, with the strongest improvements at 160 workers. Compared with Dynamo and vLLM scheduler variants, TAO cuts latency and TTFT by large margins at every concurrency level in the GLM-4.7 SWE-Lite run. In the larger GLM-4.7 evaluation, TAO reduces SWE-verified mean task latency and client TTFT while raising decode throughput relative to ThunderAgent.

On the mixed Terminal-Bench and SWE-Lite workload, TAO achieves the lowest latency and highest decode throughput across 32, 64, and 128 workers relative to Dynamo, vLLM scheduler variants, and ThunderAgent. Its TTFT is lowest at 64 and 128 workers and only slightly behind the best result at 32 workers. TAO records the lowest latency at every evaluated worker count. Decode throughput under TAO is higher than all listed baselines at every evaluated worker count. TAO has the lowest TTFT at 64 and 128 workers, while at 32 workers it is close to the best observed TTFT. At 128 workers, TAO shows a notable latency and TTFT advantage over ThunderAgent while maintaining higher decode throughput.

The full TAO configuration delivers the strongest overall efficiency on SWE-Lite, with the highest decode throughput and cache-hit rate and the lowest mean TTFT, tool-end-to-first-token delay, and pause wait. Removing cache value or readiness modestly reduces throughput and responsiveness, with readiness loss having a larger effect than cache value loss. The largest regression occurs when decision making is replaced by best-fit-decreasing, which yields the lowest decode throughput and the slowest latency metrics. The complete TAO configuration outperforms all variants in decode throughput, cache-hit rate, mean TTFT, tool-end-to-first-token delay, and mean pause wait. Ablating readiness reduces decode throughput more than removing cache value, while cache-hit rate remains relatively stable across variants. Replacing DP resumption with best-fit-decreasing causes the largest performance drop, cutting decode throughput and producing the highest mean and P90 latency timings.

The experiments evaluate TAO across multiple model configurations, benchmarks, and concurrency levels, including DeepSeek-V4 Flash, Qwen3-32B, GLM-4.7, SWE-Lite, SWE-verified, Terminal-Bench, and mixed workloads, comparing it with ThunderAgent, Dynamo, and vLLM-based schedulers. TAO consistently achieves lower latency and time-to-first-token while maintaining higher decode throughput, with the largest gains in high-concurrency GLM-4.7 runs and mixed workloads. Ablation studies confirm that the full TAO configuration is important for efficiency and responsiveness, where removing readiness or cache value causes modest regressions and replacing decision making with best-fit-decreasing produces the largest drop.