PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Shuhuai Li, Shengdong Ye, Dongdong Ge, Yinyu Ye, Jianghao Lin

arXiv:2610.37230v1cs.DC

TL;DR

Agentic serving must account for external tool timing as well as GPU inference, while existing systems can overlook readiness and make per-session scheduling decisions. TAO combines readiness, cache credit, and token footprint in joint scheduling of waiting sessions. Across reported settings, it improves latency, TTFT, and decode throughput relative to evaluated state-of-the-art baselines.

  • Problem

    Existing systems evaluate sessions individually and can overlook tool-call latency, while session selection and placement must contend with shared node capacity.

    Source: §1 · p. 1, §2.2 · p. 3

  • Method

    TAO combines near-term tool-return readiness, time-decayed node-specific cache credit, and token footprint to jointly select and place waiting sessions under capacity constraints.

    Source: §1 · p. 2, §3.2 · p. 4, §3.3 · p. 4

  • Results

    Across 12 model–workload–concurrency settings, TAO reduces latency by up to 26.8%, mean TTFT by up to 36.3%, and increases decode throughput by up to 29.5% relative to the state-of-the-art baseline for each metric.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The resulting architecture gives agentic serving an extensible way to translate workload knowledge into coordinated admission and placement.

    Source: §6 · p. 10

Abstract

from arXiv · show

Agentic services alternate between model inference on clustered GPUs and external tools on distributed CPUs. In this scenario, existing systems (1) overlook tool-return readiness in service evaluation, wasting limited resources, and (2) use heuristic strategies to decide admission and placement on GPUs, resulting in suboptimal scheduling decisions. To bridge this gap, we present TAO, a tool-aware joint scheduling framework for LLM-based agentic serving. Its value interface combines near-term tool readiness, node-specific cache credit with time-aware decay, and token footprint; a dynamic program jointly selects and places waiting sessions under capacity constraints. Across the 12 reported model-workload-concurrency settings, TAO reduces latency by up to 26.8%, reduces mean time to first token (TTFT) by up to 36.3%, and increases decode throughput by up to 29.5% relative to the best evaluated state-of-the-art baseline for each metric.

1 INTRODUCTION

Agentic serving must coordinate GPU inference with external tool timing, but existing systems evaluate sessions separately and use heuristic admission and placement. TAO combines tool-aware session evaluation with joint scheduling; across reported settings, it improves latency, TTFT, and decode throughput over evaluated baselines.

1 INTRODUCTION

  • In CGDC serving, external tool calls create delays between LLM requests, making tool timing relevant to inference capacity and session responsiveness.TAO is also described as generalizable to multi-agent orchestration and Looped Agents, and compatible with non-agent chatbot scenarios.Source: §1 · pp. 1–2
  • Existing systems evaluate node features per session and then decide where and when to serve it, while often overlooking tool-call latency and relying on fixed scoring rules or thresholds.This separates the problem into valuing a session’s next model turn and selecting and placing sessions under shared capacity constraints.Source: §1 · p. 1
  • TAO combines near-term tool-return readiness, time-decayed node-specific KV-cache reuse, and token footprint, then jointly selects and places waiting sessions using dynamic programming.The optimizer accounts for how admitting one session affects placements available to others.Source: §1 · p. 2
  • Across 12 model–workload–concurrency settings, TAO reduces latency by up to 26.8%, mean TTFT by up to 36.3%, and increases decode throughput by up to 29.5% relative to the state-of-the-art baseline for each metric.Source: §1 · p. 2

2 BACKGROUND AND PROBLEM DESCRIPTION

Agent sessions alternate between model requests and external tool calls, with GPU resources shared across nodes and tool execution outside the inference service. At tool boundaries, sessions can be interrupted to release node resources, then restarted from a waiting pool using a unified session evaluation.

2.1 AGENT SESSION AND DISTRIBUTED RESOURCES

  • An agent session carries instructions, history, and tool observations across turns, so KV-prefix reuse depends on both session history and the node chosen for its next request.Source: §2.1 · p. 3

2.2 SESSION INTERRUPTION AND SESSION RESTART

  • Preempting active inference requires recomputation, while a session at a tool boundary can release GPU resources safely, although its cached prefix may later be evicted.Repeated recomputation and reconstruction can cause KV-cache thrashing.Source: §2.2 · p. 3
  • At a tool boundary, the scheduler can interrupt model admission and release node resources while the external tool continues, then restart the session on an eligible node when inference is needed.These session-state transitions are decoupled from the underlying inference engine.Source: §2.2 · p. 3
  • Interruption and restarting can use the same session evaluation: interrupted sessions join new arrivals in a waiting pool, where the scheduler orders and places them.Source: §2.2 · p. 3

3 METHOD

TAO separates session evaluation from joint admission and node placement, using cache value, tool-return readiness, and token footprint to value waiting sessions. It applies time-aware cache discounting and a capacity-constrained dynamic program to schedule them.

3.1 FRAMEWORK OVERVIEW

  • TAO maps session and node observations to assignment values, then jointly selects waiting sessions and places them on nodes under residual-capacity constraints.Separating evaluation from decision making allows the evaluation interface to evolve while preserving the scheduling procedure.Source: §3.1 · p. 3

3.2 FORMULATION AND AGENTIC SESSION EVALUATION

  • Session–node values prioritize decayed KV-cache credit, then binary tool-return readiness, then token count when selecting and placing sessions.The fixed lexicographic order gives cache opportunity precedence, readiness a role among plans tied on cache credit, and token footprint a role among plans tied on both.Source: §3.2 · p. 4

3.3 TIME-AWARE CACHE VALUE FOR CLUSTERED GPUS

  • TAO estimates reusable KV state from target-node cache observations and discounts older observations, making cache credit responsive to observation age.The reported two-node DeepSeek-V4 Flash traces show declining binned medians; the scheduler uses a 10-second half-life, distinct from the fitted trace time constant.Source: §3.3 · pp. 4–5, Figure 3 · p. 4

3.4 TOOL-RETURN READINESS IN A DISTRIBUTED CPU

  • Tool-return readiness identifies sessions likely to need GPU inference soon, using tool timing and prediction sources to mark near-term or overdue returns.The signal combines timing hints and historical durations; observed completion takes precedence, and overdue predictions receive temporary probe opportunities.Source: §3.4 · p. 5

3.5 JOINT SCHEDULING WITH DYNAMIC PROGRAMMING

  • A capacity-state dynamic program optimizes session selection and node assignment; it is exact for the frozen, discretized problem, though rounding can exclude previously feasible plans.The planner preprocesses node-specific cache values and revalidates the plan against live state before application.Source: §3.5 · p. 5

4 EXPERIMENTS

TAO is evaluated across models, workloads, and concurrency settings, with results on task latency, TTFT, and decode throughput. The experiments examine its overall performance, component contributions, and ablated variants.

4.1 EXPERIMENT SETUP

  • The evaluation covers DeepSeek-V4 Flash, Qwen3-32B, and GLM-4.7 across SWE-Lite, Terminal-Bench, and SWE-verified, using distinct multi-node and single-node deployments.Reported metrics include end-to-end task latency, TTFT, and decode throughput; task latency includes model inference and tool execution.Source: §4.1 · pp. 6–7

4.2 MAIN RESULTS

  • On SWE-Lite, latency falls 2.4–26.8%, TTFT falls 7.4–36.3%, and decode throughput rises 5.1–29.5% versus the best competing method in each column.On Terminal-Bench, TAO also leads on latency and TTFT at all three concurrency levels.Source: §4.2 · p. 7
  • On SWE-verified, TAO reduces TTFT by 12.9–29.9% and raises decode throughput by 4.0–7.8%; latency is 2.5% higher than ThunderAgent at 128 workers.For Qwen3-32B on SWE-Lite, it has the lowest TTFT at all three worker counts and highest decode throughput at 96, 128, and 160 workers.Source: §4.2 · p. 7
  • On all 500 SWE-verified tasks, GLM-4.7 reduces mean task latency by 16.2–18.9% and client TTFT by 15.7–38.4%, while raising decode throughput by 22.8–24.7% versus ThunderAgent.The one-node TP8 SWE-Lite results at 160 workers improve latency by 15.5%, TTFT by 14.05%, and decode throughput by 20.48%; Table 2 covers this setting.Source: §4.2 · p. 7, Table 2 · p. 7

4.3 IMPROVEMENT BREAKDOWN

  • In a 218-task replay, cache-token ordering raises prefix-cache hit rate by 0.19 percentage points and reduces mean pause wait by 4.5%; adding cache-credit decay raises hit rate by 0.31 percentage points and decode throughput by 1.68%.Figure 5 summarizes cache-aware valuation relative to the ThunderAgent control with DP placement.Source: §4.3 · p. 9, Figure 5 · p. 9
  • Readiness raises decode throughput by 4.03%, reduces tool-end-to-first-token delay by 10.88%, and lowers mean pause wait from 1.067 to 0.972 s.Across 10,967 completed tools, duration predictions have 0.410 s mean absolute error, with 82.9% of errors within 0.5 s; Figure 6 shows readiness and prediction panels.Source: §4.3 · p. 9, Figure 6 · p. 9
  • Joint optimization improves the lexicographic objective in 6 of 23 multi-candidate snapshots (26.1%) and matches the short-first heuristic in the other 17.Across all 35 reconstructable snapshots, DP improves six (17.1%) and matches the heuristic in 29 (82.9%).Source: §4.3 · p. 9

4.4 COMPONENT ABLATIONS

  • The complete TAO configuration has the highest decode throughput and cache-hit rate, and the lowest mean TTFT, post-tool delay, and pause wait among the Table 4 variants.Removing cache credit lowers decode throughput from 1417.97 to 1398.35 tok/s; removing readiness lowers it to 1363.06 tok/s, while replacing DP resumption with BFD yields 1233.72 tok/s.Source: §4.4 · p. 9, Table 4 · p. 10

5 RELATED WORK

Prior work addresses cache locality, workload structure, tool latency, and session scheduling through distinct approaches. TAO combines cache opportunity and tool readiness in a scheduler-level admission and placement objective.

5 RELATED WORK

  • Engine-level KV management and distributed cache schedulers exploit prefix residency and locality, while TAO complements them with scheduler-level admission and placement [Kwon et al., 2023].TAO brings cache opportunity and tool readiness into a joint scheduler-level objective.Source: §5 · p. 10
  • Workflow-aware systems exploit dependencies or execution structure, while Conveyor, Sutradhara, and PASTE reduce exposed tool latency through partial execution, overlap, or speculation [Lin et al., 2024; Wadlom et al., 2026; Pan et al., 2025; Zhang et al., 2026; Xu et al., 2024; Biswas et al., 2026; Sui et al., 2026].TAO instead converts tool timing into near-term model-service opportunities for admission and placement.Source: §5 · p. 10
  • TOPAS jointly considers prefix residency and admission through bounded search and greedy packing, whereas TAO uses an agentic value interface with joint placement and asynchronous revalidation.The passage also situates TAO alongside program-aware, cache-retention, and online optimization approaches.Source: §5 · p. 10

6 CONCLUSION

TAO combines tool-return readiness, decayed cache credit, and token footprint in a joint scheduling objective. The appendix describes a history-based duration heuristic and explicitly limits its calibration claim.

6 CONCLUSION

  • TAO uses cache credit, tool-return readiness, and token footprint in joint dynamic-programming placement under snapshot capacity constraints, with asynchronous revalidation connecting the plan to live execution.Across evaluated DeepSeek-V4 Flash and Qwen3-32B settings, it reports up to 26.8% lower latency, 36.3% lower mean TTFT, and 29.5% higher decode throughput.Source: §6 · p. 10

A HISTORICAL TOOL-DURATION ESTIMATOR

  • For calls without direct timing evidence, the duration heuristic uses completed-call statistics keyed by structured tool name and adds a finite-sample margin to the historical mean.The estimate subtracts elapsed time from the upper estimate; the margin is a scheduling heuristic and does not provide calibrated coverage for an individual call.Source: A HISTORICAL TOOL-DURATION ESTIMATOR · p. 17
  • When both tool-specific and global histories are empty, the implementation uses a five-second duration default and clips the remaining-time estimate at zero.Exposed timing hints take precedence.Source: A HISTORICAL TOOL-DURATION ESTIMATOR · p. 17

B EXTENDED METHOD DETAILS

TAO quantizes session costs and node capacities to run a joint selection-and-placement dynamic program, then revalidates its plan before application. The appendix bounds scheduling-value loss relative to a fresh-snapshot optimum under stated assumptions.

B.1 JOINT SELECTION AND PLACEMENT ALGORITHM

  • The algorithm takes frozen candidates, nodes, capacities, eligibility, and a quantum; session evaluation supplies costs and session–node values for selection and placement.It quantizes costs and capacities, embeds assignment values, and uses dynamic programming to find the best feasible plan, with a BFD fallback if the budget is exceeded.Source: §B.1 · p. 17

B.2 ASYNCHRONOUS EXECUTION

  • Before applying a plan, revalidation checks selected sessions' eligibility and recorded signatures, discards changed plans, and applies only the longest prefix feasible under current capacities.At each scheduling time, session memory demand and remaining node capacity are updated from current observations.Source: §B.2 · pp. 17–18, §B.1 · p. 17
  • The loss bound compares the revalidated plan with the fresh placement optimum on the same realized state; under bounded assignment-value drift, short plan age limits value drift.The bound assumes at most K assignments and per-assignment drift η; readiness jumps require separate allowances, and fallback or quantization can add gaps.Source: §B.2 · p. 18

C ASYNCHRONOUS SNAPSHOT LOSS: PROOF AND SCOPE

TAO’s asynchronous planning analysis bounds loss against fresh-snapshot optima under specified value and feasibility conditions, while additional experiments report low-concurrency fallback behavior and GLM-4.7 traces.

C ASYNCHRONOUS SNAPSHOT LOSS: PROOF AND SCOPE

  • If each plan has at most K assignments and scalar assignment values change by at most ηs,t, then ϵs,t ≤ Kηs,t; with ηs,t ≤ L(t − s), the variation term is 2KL(t − s).Binary readiness requires explicit jump allowances and does not automatically satisfy the time-variation assumption; the bound is against fresh-snapshot optima on realized states, not end-to-end latency or globally optimal online regret.Source: C ASYNCHRONOUS SNAPSHOT LOSS: PROOF… · p. 19

D ADDITIONAL GLM-4.7 SERVING TRACES

E.1 FALLBACK COMPATIBILITY

  • At 4–8 workers, TAO’s mean task latency stays within 2.3% of the best baseline, decode throughput exceeds 92% of the best, and mean TTFT is only 15–20 ms higher.The low-concurrency fallback check uses a single TP8 node and 300 SWE-Lite tasks; the table reports mean task E2E latency, mean client TTFT, and aggregate decode throughput.Source: §E.1 · p. 20, Table 5 · p. 20

E.2 KV-CACHE MANAGEMENT COMPATIBILITY

The TokenCake composition experiments report serving compatibility for TAO, including lower mean task latency and higher decode throughput than consistent-hash routing at 16 and 32 workers.

E.2 KV-CACHE MANAGEMENT COMPATIBILITY

  • At 16 and 32 workers, TAO over TokenCake lowers mean task latency by 3.1% and 2.0% and increases decode throughput by 12.9% and 4.2% versus consistent hashing.At 32 workers, client TTFT rises slightly from 0.220 to 0.223 s; the validated runs show balanced routing, but no program pause, resume, or migration.Source: §E.2 · pp. 20–21, Table 6 · p. 21
  • The combined runs establish lifecycle and serving compatibility under these loads, but do not attribute gains to DP selection or overlapping offload because those mechanisms were not activated.Separate transfer qualifications verify actual GPU–CPU movement.Source: §E.2 · p. 21

F INFERENCEX REPLAY

On the fixed-trace InferenceX replay, TAO has the highest decode throughput at every tested concurrency, while its TTFT advantage is limited to 16 workers.

F INFERENCEX REPLAY

  • Decode throughput improves over the best competing method by 4.2%, 1.8%, and 10.1% at 16, 32, and 64 workers, respectively.TAO has the lowest TTFT at 16 workers, while cache-aware scheduling has lower TTFT at 32 and 64 workers.Source: F INFERENCEX REPLAY · p. 21
  • TAO maintains the highest prefix-cache hit rate throughout the tested worker counts, even as hit rates decrease with concurrency for all four methods.The replay uses two nodes with 4×H100 per node.Source: F INFERENCEX REPLAY · p. 22, Figure 9 · p. 22

G SENSITIVITY TO LONGER TOOL-RETURN DELAYS

In a replay with added tool-return delays, TAO improves over a historical configuration, and readiness affects more placement decisions as delays grow; separate snapshots illustrate joint placement’s cache-credit and admission effects.

G SENSITIVITY TO LONGER TOOL-RETURN DELAYS

  • 20.72%, 16.42%, and 19.28% lower makespan, and 21.57%, 20.57%, and 17.91% lower mean session latency, are reported at delay scales 1, 2, and 4.The added tool-return delays span 1–5 s at scale 1 through 4–20 s at scale 4; comparisons are against the historical configuration, which also disables cached-token decay and shared-token refresh.Source: G SENSITIVITY TO LONGER TOOL-RETURN… · p. 22
  • Removing readiness changes 1.65%, 3.94%, and 7.93% of exact DP plan comparisons at delay multipliers 1, 2, and 4, respectively.These same-state comparisons isolate readiness’s effect on individual placement decisions within the TAO runs.Source: G SENSITIVITY TO LONGER TOOL-RETURN… · p. 22, Table 8 · p. 23
  • Known replay durations reduce mean absolute prediction error by 99.53–99.69%, to 0.025–0.030 s; at scale 2, makespan falls 2.24% and mean session latency falls 0.71% versus TAO.Across all three scales, signed makespan improvements range from −0.10% to +2.24%, and mean session-latency improvements from −0.36% to +0.71%.Source: G SENSITIVITY TO LONGER TOOL-RETURN… · p. 22

H JOINT PLACEMENT CASE STUDIES

  • In one reconstructed snapshot, DP retains 16,791 tokens of cache credit versus 13,624 for short-first, a 23.2% increase with the same safe-token remainder; another shows DP admitting seven sessions versus six.In the latter snapshot, DP admits long-context session 177, which the heuristic defers.Source: H JOINT PLACEMENT CASE STUDIES · p. 23

I SCHEDULER OVERHEAD ANALYSIS

At four replicas and up to 160 workers, measured scheduling work remains below 0.12% of runtime; the related work positions TAO as joint scheduling across cache, readiness, and placement.

I SCHEDULER OVERHEAD ANALYSIS

  • 0.112% of runtime is the measured scheduling work in the four-replica Qwen sweep at 160 workers, where solving averages 1.59 ms.Planning submissions rise from 98 to 1,681 across 96–160 workers; Table 9 defines measured work as state preparation plus completed solves.Source: I SCHEDULER OVERHEAD ANALYSIS · p. 23, Table 9 · p. 25
  • Measured work excludes failed attempts and BFD execution, so work/run is partial accounting, not CPU utilization or request-latency overhead.Fallback occurs in 5.24% of submissions at 64 DeepSeek workers and 3.06–8.98% in the Qwen sweep.Source: I SCHEDULER OVERHEAD ANALYSIS · p. 23, Table 9 · p. 25

J EXTENDED RELATED WORK

  • TAO connects session evaluation to joint admission and node placement using multiple-knapsack machinery and an additive, lexicographic objective.Its asynchronous executor revalidates assignments against live state.Source: J EXTENDED RELATED WORK · pp. 23–25
  • Unlike cache-locality and program-level schedulers, TAO jointly assigns waiting sessions using node-specific cache values and readiness.Prior systems include SMetric’s cache-aware placement and ThunderAgent’s state-aware pausing and elapsed-time discounting.Source: J EXTENDED RELATED WORK · p. 25
  • Workflow and prediction systems guide residency, prefetching, or workflow-aware priority, while TAO uses tool timing for near-term admission opportunities and placement.Its scheduler role also differs from systems that modify the execution timeline through partial tool execution, overlap, or speculation.Source: J EXTENDED RELATED WORK · pp. 25–26
  • In TAO’s CGDC setting, distributed executors manage tool CPU and memory while tool-return timing informs GPU admission capacity.AgentSysBench documents non-LLM latency and deployment-dependent demands; MARS coordinates GPU inference, CPU tool pressure, admission, and KV retention.Source: J EXTENDED RELATED WORK · p. 26

Related papers

Loading 2610.37230v1…