TAO: Tool-Aware Joint Scheduling for LLM-Based Agentic Serving

TAO jointly evaluates tool-return readiness, time-decayed KV-cache credit, and token footprint, then uses dynamic programming to select and place waiting agent sessions on GPU nodes.

Agentic services alternate between clustered GPU inference and distributed CPU tools, so a session’s GPU demand is interrupted by tool calls. Existing systems overlook tool-call latency when evaluating sessions and use heuristic admission and placement. This can waste limited resources and produce myopic or suboptimal scheduling decisions.

TAO follows an evaluate-then-decide framework. Each session–node pair receives a lexicographic value triplet of decayed KV-cache credit, binary tool-return readiness, and token count. Cache credit is discounted exponentially with a 10-second half-life. Readiness uses observed completion, timing hints, parsed sleep commands, and historical tool durations, falling back to a five-second default and using a one-second horizon. A capacity-state dynamic program jointly selects and places sessions under residual capacity constraints; it is exact for the frozen, discretized problem, runs asynchronously, and revalidates before application.

• Across 12 reported model–workload–concurrency settings, TAO reduces latency by up to 26.8%, reduces mean TTFT by up to 36.3%, and increases decode throughput by up to 29.5% relative to the best evaluated baseline for each metric. §Abstract
• On DeepSeek-V4 Flash SWE-Lite at 64 workers, TAO reports 185.410 s latency, 0.224 s TTFT, and 2021.523 tok/s decode. §4
• Complete TAO reaches 1417.97 tok/s decode; removing cache credit lowers it to 1398.35 tok/s, removing readiness to 1363.06 tok/s, and replacing DP resumption with BFD yields 1233.72 tok/s. §4.4
• At 4–8 workers, TAO’s mean task latency stays within 2.3% of the best baseline, retains over 92% of the best baseline’s decode throughput, and its mean TTFT is 15–20 ms above the best baseline. §E.1
• In one reconstructed snapshot, DP retains 16,791 cache-credit tokens versus 13,624 for short-first placement, a 23.2% increase. §H
• At 160 workers, completed assignment solving averages 1.59 ms with P95 3.68 ms; measured scheduler work is 0.112% of the run and below 0.12% at four replicas. §I

• The joint DP is exact for the frozen, discretized problem; the paper states that rounding can exclude plans feasible before discretization.
• The finite-sample margin in the historical tool-duration estimator is a scheduling heuristic and does not provide calibrated coverage for an individual call, as stated in Appendix A.
• Scheduler overhead accounting covers state preparation and completed solves; exhausted searches and fallback execution are untimed, so work per run is a partial accounting rather than a measure of CPU utilization or request-latency overhead, as stated in Appendix I.
• In the TokenCake composition, the paper states that attributing results to DP selection or overlapping offload would require runs that activate those mechanisms; the evidence establishes lifecycle and serving compatibility under those loads.

• The paper defines CGDC as clustered GPUs for shared inference capacity and distributed CPUs for external tool calls, which create delays between LLM requests. §1
• Session interruption can release GPU resources during tool execution, and interrupted sessions join new arrivals in a waiting pool for restart scheduling. §2.2
• TAO assigns each session–node pair a lexicographic value v=(k,r,t) and maximizes the aggregate value under eligibility and capacity constraints. §3.2
• Cache credit decays as k_i,b(t)=k0 2^{-tau/h} with h=10 seconds, and the resulting credit is rounded for valuation. §3.3
• Readiness uses H=1 second and valid prediction timestamps refreshed within 30 seconds; the fallback duration is five seconds. §3.4
• The DP uses a capacity quantum and O(nm) preprocessing for node-specific cache observations; cache-equivalent nodes can be grouped into g≤m aggregate capacity dimensions. §3.5
• Experiments use DeepSeek-V4 Flash on 2 nodes with 4× H100 per node and Qwen3-32B on 4 nodes with 2× H100 per node. §4.1
• With TokenCake enabled, TAO completes 300-task SWE-Lite runs and increases decode throughput from 785.159 to 886.772 tok/s and from 1292.584 to 1347.373 tok/s at 16 and 32 workers. §E.2