acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 **T**ool-**A**ware j**O**int 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. Our code is available at https://anonymous.4open.science/r/TAO-330C.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Agentic Service, Request Admission, Scheduling, Optimization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_ZHNvOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary
  1. TAO jointly selects waiting agent sessions for admission and assigns them to inference nodes.
  2. It lexicographically prioritizes decayed cache credit, tool readiness, and context length, using classical dynamic programming under capacity constraints.
  3. Experiments cover multiple models, workloads, and concurrency levels, with task execution, trace replay, and component comparisons.
Critical strengths
  1. Joint admission and placement account for competition over node capacity and can exploit combinations missed by sequential placement.
  2. With valuation held fixed, DP improves throughput by approximately 14.9% and reduces mean TTFT by approximately 21.0% relative to BFD in the reported comparison.
  3. Multi-model experiments and trace replay provide complementary evidence. Component comparisons also support the usefulness of cache and readiness information.
Critical weaknesses
  1. The strict scoring order lacks direct validation. A small advantage in total cache credit overrides any readiness advantage. Existing ablations do not establish this ordering’s advantage over alternative priorities or weighted combinations.
  2. The fixed-valuation DP–BFD serving comparison covers one configuration. Broader system comparisons do not clarify which workload or capacity conditions make exact joint optimization particularly beneficial.
  3. Capacity quantization and search-budget settings are unspecified in the paper. Reported computational overhead excludes exhausted searches and BFD fallback, leaving the complete computational cost unclear.

I tentatively favor acceptance for the substantial implementation and reusable evaluation workflow, pending clarification of the scoring rule and performance gains.

Questions for authors
  1. Why should cache credit strictly precede readiness? Have alternative priority orders or weighted combinations been compared under the same solver?
  2. Which scheduling conditions explain DP’s gains over BFD? Do fixed-valuation comparisons in other tested configurations support these gains?
  3. What quantization and search-budget settings were used? What is the computational overhead including exhausted searches and fallback?
5 comments

Dear Reviewer ZHNv,

Thank you for your careful reading and constructive feedback. We appreciate your understanding and recognition of the key arguments presented in our paper. Below, we respond to your comments with additional explanations and experiments.

W1 & Q1: Lexicographic priorities and weighted alternatives

Our ordering gives cache credit, readiness, and token count distinct roles (Secs. 3.2–3.4 in Original paper):

  • Cache credit prioritizes reusable state and decays with inactivity.
  • Readiness distinguishes sessions with equal rounded cache credit.
  • Token count favors longer programs among remaining ties.

We now compare readiness-first and tokens-first on SWE-Lite with 300 tasks per workload. Here, ki,bk_{i,b}, rir_i, and tit_i denote these three signals; >> denotes priority. TAO rows are historical paper results, while the alternatives are supplementary runs.

Model / ConfigurationObjectiveE2E Mean (s) ↓\downarrowTTFT Mean (s) ↓\downarrowDecode (token/s) ↑\uparrow
DeepSeek-V4 Flash / 64 workersTAO: ki,b>ri>tik_{i,b} > r_i > t_i185.4100.2242021.523
Readiness-first: ri>ki,b>tir_i > k_{i,b} > t_i213.9450.4621619.890
Tokens-first: ti>ki,b>rit_i > k_{i,b} > r_i222.2950.4491669.201
GLM-4.7 / 160 workersTAO: ki,b>ri>tik_{i,b} > r_i > t_i1476.19020.066805.939
Readiness-first: ri>ki,b>tir_i > k_{i,b} > t_i2132.48024.316545.030
Tokens-first: ti>ki,b>rit_i > k_{i,b} > r_i2066.13423.031543.784

We also test four weighted objectives to examine numerical trade-offs. The objective is aki,b/32768+bri+cti/32768a k_{i,b}/32768+b r_i+c t_i/32768, where rir_i is binary and 32,768 is the configured context limit. The table reports coefficients (a,b,c)(a,b,c) in cache–readiness–token order.

ModelObjective / Weights (a,b,c)(a,b,c)E2E Mean (s) ↓\downarrowTTFT Mean (s) ↓\downarrowDecode (token/s) ↑\uparrow
DeepSeek-V4 FlashTAO (Ours): w/ o Weighting185.4100.2242021.523
Equal (1,1,1)(1,1,1)215.1180.3521742.038
Cache-weighted (3,1,1)(3,1,1)211.2240.3631636.912
Readiness-weighted (1,3,1)(1,3,1)221.2350.3831702.496
Tokens-weighted (1,1,3)(1,1,3)221.4280.4751658.730
GLM-4.7TAO (Ours): w/ o weighting1476.19020.066805.939
Equal (1,1,1)(1,1,1)2165.60125.031549.473
Cache-weighted (3,1,1)(3,1,1)2131.28123.772567.822
Readiness-weighted (1,3,1)(1,3,1)1984.94521.970585.173
Tokens-weighted (1,1,3)(1,1,3)2058.74123.623556.723

Taken together, the two tables support explicit priorities without requiring workload-specific weight calibration. The best weighted setting changes across workloads: cache weighting gives DeepSeek's lowest E2E, while readiness weighting leads on GLM. Our original deisgn is better than any other settings.


W2 & Q2: Scheduling conditions and comparisons with BFD

DP helps when limited capacity couples session selection with replica placement. Different footprints and cache locations can make a greedy placement exclude a higher-value combination (Sec. 3.5 and Appendix G in Original paper).

The table presents two more configurations using the model DeepSeek and Qwen with TAO's scoring. Each workload uses SWE-Lite with 300 tasks.

Model / WorkersMethodE2E Mean (s) ↓\downarrowTTFT Mean (s) ↓\downarrowDecode (token/s) ↑\uparrow
DeepSeek / 64BFD204.7640.5231741.218
DP Planner (Ours)185.4100.2242021.523
TAO Rel. Imprv.+9.5%+57.2%+16.1%
Qwen / 128BFD822.1468.6441779.857
DP Planner (Ours)829.3617.9072051.807
TAO Rel. Imprv.−0.9%+8.5%+15.3%

Taken together, these two configurations show lower TTFT and higher decode throughput under TAO. DeepSeek also has lower E2E latency, while Qwen has a 0.9% E2E increase.

W3 & Q3: DP and BFD computational overhead

Thank you for catching this gap in our overhead reporting. We account for DP Planner, with BFD as the final fallback(Appendix I in Revised Paper). The capacity quantum is 1,024 tokens, and the search budget is 50,000 sparse states. Budget exhaustion selects internal LP solving; LP failure or its 150 ms deadline invokes BFD. This preserves the paper's DP planner → BFD organization.

We now show the complete DP Planner cost here:

DeploymentWorkersDP search mean (ms)DP search P95 (ms)DP-search fallback rateBFD mean (ms)BFD P95 (ms)
DeepSeek, 2 replicas6412.5088.845.24%0.0230.032
Qwen, 4 replicas1601.593.688.98%0.0220.032
GLM, 1 replica1603.8514.630.00%0.0330.050

Note that the DP Planner accounting includes internal LP work and exhausted DP searches in the same DP column.

For each snapshot, DP Planner consists of DP search and sparse LP stage, with BFD as the fallback. Async completion additionally retains process management and BFD execution (Tables 5 and 10 in Revised Paper).

ReplicasCandidatesDP Planner mean (ms)DP Planner P95 (ms)BFD Fallback mean (ms)Async mean (ms)Async P95 (ms)
21612.0819.04—15.9123.04
166412.4013.87—14.0816.03
3216020.5322.09—22.4524.23
6412818.9920.69—20.8422.73
12851281.9495.30—84.8898.25

Stage means include zeros for unvisited stages; “—” means BFD was not invoked. Timed-out internal LP intervals retain the 150 ms cutoff. Async completion uses actual wall time. The cutoff does not limit preceding DP work.

Asynchronous execution keeps this solving cost separate from synchronous preparation. Preparation averages 1.48 ms, 0.94 ms, and 2.18 ms for DeepSeek, Qwen, and GLM, or 0.033%, 0.044%, and 0.078% of runtime (Table 4 in Revised Paper).

Dear Reviewer ZHNv,

Thank you for your careful evaluation of our work. With the discussion window closing soon, we would welcome your thoughts on whether our responses and revisions have adequately resolved the issues you raised. Any additional comments or suggestions would be valuable in further strengthening our submission.

Best regards,

The Authors

Reviewer_5t2qOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

TAO schedules LLM agent sessions that alternate between model inference and external tool execution. It combines GPU-specific cache reuse, predicted tool readiness, and context size to select waiting sessions and assign them to model replicas. A dynamic programming algorithm jointly considers competing assignments under capacity constraints, with a heuristic fallback and validation before applying decisions. The evaluation uses multiple models and agent workloads, reporting improvements in task completion latency, time to first token, and throughput. The approach is interesting, but its additional benefit over shared CPU KV caching, session-aware routing, and tool-aware memory tiering remains insufficiently established by the comparisons.

Critical strengths
  1. Addresses a practical problem: coordinating agent sessions whose GPU inference is interrupted by external tool calls.

  2. Jointly considers session admission and GPU placement, accounting for competition over limited capacity.

  3. Includes end-to-end evaluation across multiple models and agent workloads, supported by component ablations.

Critical weaknesses
  1. Evaluate TAO with a shared CPU KV cache. Systems such as LMCache allow cached context to survive GPU eviction and support reuse across replicas. This could reduce the advantage of prioritizing GPU-local cache reuse and provide greater placement flexibility. However, restoration still incurs transfer costs, and memory reclamation depends on the inference engine. Please evaluate TAO and baseline scheduling policies using the same shared-cache backend. Reporting transfer latency, bandwidth consumption, GPU/CPU memory usage, and end-to-end performance would clarify whether TAO’s benefits remain substantial with this infrastructure. LMCache architecture

  2. Compare directly with SMetric to establish the value of joint scheduling. SMetric balances the first request of each session and favors cache reuse for subsequent requests, using a global KV tier to support redistribution. TAO acknowledges this design, but the current evaluation does not show whether joint admission and placement outperform this simpler policy. Please compare both systems under matched hardware, workloads, and cache configurations. The comparison should establish how much additional benefit comes from TAO’s readiness prediction and joint optimization, including their scheduling overhead. SMetric paper

  3. Clarify and evaluate the distinction from MORI. MORI uses recent tool-call behavior to rank session idleness, retain busier sessions in GPU memory, and place more idle sessions in CPU memory, with admission control at both tiers. This overlaps with TAO’s objective of using tool gaps to improve resource utilization. TAO instead predicts near-term readiness and jointly selects session–replica assignments. Please explain when this approach provides an advantage over MORI and evaluate representative workloads under matched resource budgets, including throughput, post-tool response latency, and KV transfer costs.

Questions for authors
  1. How much benefit does TAO retain when both TAO and the baselines use a shared CPU KV cache, including KV restoration costs and matched memory budgets?

  2. How does TAO compare with SMetric under identical serving and cache configurations? Does its more complex joint optimization provide sufficient gains to justify the scheduling overhead?

  3. What advantages does TAO’s readiness prediction and joint placement offer over MORI’s tool-idleness-aware memory management? Can these advantages be demonstrated under matched workloads and resource budgets?

5 comments

Dear Reviewer 5t2q,

Thank you for reviewing our paper. We appreciate your recognition of joint admission and placement for agent serving. Since the only concerns you got are the comparisons of three baselines, we compare and show our advantages through method discussion, experiments, and analysis below.

W1 & Q1: Shared CPU KV cache and placement flexibility

Shared CPU caching, such as LMCache [1], expands reuse, while TAO decides which competing sessions should receive GPU capacity.

  • Feature: LMCache preserves context after GPU eviction and supports cross-replica reuse, including chunk-level management and asynchronous loading.
  • Shortcoming: cache availability alone does not select which competing sessions should occupy GPU capacity.

TAO jointly selects sessions and replicas using cache credit and near-term readiness (Secs. 3.2–3.5 in Original paper).

We evaluate TAO and vLLM Router with shared LMCache under equal configured GPU and CPU KV budgets. Both use eight H100 GPUs and SWE-Lite's 300 tasks. DeepSeek uses TP4×2, 64 workers, 28.163 GiB of GPU KV per rank, and a 256 GiB CPU pool; GLM uses TP8×1, 160 workers, 17.000 GiB per rank, and a 576 GiB CPU pool.

ModelMethod / ResultE2E Mean (s) ↓\downarrowTTFT Mean (s) ↓\downarrowPost-tool Mean (s) ↓\downarrowDecode (token/s) ↑\uparrow
DeepSeek-V4 FlashvLLM Router + LMCache216.1721.0451.0571,438.363
TAO + LMCache221.0800.7100.8051,562.384
TAO Rel. Imprv.-2.27%+32.06%+23.89%+8.62%
GLM-4.7vLLM Router + LMCache3,548.26870.68871.361331.241
TAO + LMCache2,530.76941.47740.261469.285
TAO Rel. Imprv.+28.68%+41.32%+43.58%+41.67%

The performance table shows higher throughput and lower TTFT and post-tool latency for TAO in both configurations, including restoration costs. Throughput improves by 8.62% on DeepSeek and 41.67% on GLM; TTFT falls by 32.06% and 41.32%. GLM's E2E latency falls by 28.68%, while DeepSeek's increases by 2.27%.

ModelMethodGPU peak (GiB)Service PSS peak (GiB)D2H KV (GiB)H2D KV (GiB)H2D DMA mean (ms)H2D bandwidth (GB/s)
DeepSeek-V4 FlashvLLM Router + LMCache631.125292.399320.6681,216.7251.2040.953
TAO + LMCache630.291292.342323.556319.9501.5600.270
GLM-4.7vLLM Router + LMCache550.035614.1971,363.21024,506.9639.8913.048
TAO + LMCache547.410613.8851,861.6071,684.0234.5730.286

In this table, the resource and performance tables show lower H2D traffic alongside higher throughput in both configurations. H2D volume falls from 1,216.725 to 319.950 GiB on DeepSeek and from 24,506.963 to 1,684.023 GiB on GLM. GPU and service-PSS peaks are slightly lower for TAO. D2H volume rises; mean H2D DMA time rises on DeepSeek and falls on GLM.

Taken together, TAO retains throughput and response-latency gains with shared CPU KV storage, matched memory budgets, and restoration included in the serving path. Against the executed Router + LMCache configuration, throughput improves by 8.62–41.67% and post-tool latency falls by 23.89–43.58%. The accompanying memory and transfer measurements show that these gains coexist with similar memory peaks and lower H2D traffic.


Reference:

[1] LMCache: An Efficient KV Cache Layer for Enterprise-Scale LLM Inference

W2 & Q2: SMetric and the value of joint scheduling

Regarding SMetric [2], its session-affinity policy does not explicitly optimize competing admissions according to their predicted return to inference.

  • Feature: SMetric balances first requests and favors cache locality on subsequent turns.
  • Shortcoming: its routing rule does not use predicted tool-completion readiness. Similar cache opportunities can therefore mask different times to the next model invocation.

TAO combines readiness with cache credit and jointly selects session–replica assignments. This helps distinguish equally cache-favorable sessions and avoid individual placements that exclude a better combination.

The matched SMetric comparison shows lower E2E latency, TTFT, and post-tool latency, together with higher decode throughput under TAO. Both policies use the same serving and shared-cache configuration for each model.

ModelMethod / ResultE2E Mean (s) ↓\downarrowTTFT Mean (s) ↓\downarrowPost-tool Mean (s) ↓\downarrowDecode (token/s) ↑\uparrow
DeepSeek-V4 FlashSMetric + LMCache223.3290.9070.9181,472.536
TAO + LMCache221.0800.7100.8051,562.384
TAO Rel. Imprv.+1.01%+21.74%+12.37%+6.10%
GLM-4.7SMetric + LMCache2,807.93850.35250.826428.782
TAO + LMCache2,530.76941.47740.261469.285
TAO Rel. Imprv.+9.87%+17.62%+20.79%+9.45%

These results show that TAO's benefits persist beyond session-affinity routing with shared KV storage. E2E latency falls by 1.01% on DeepSeek and 9.87% on GLM, while throughput rises by 6.10% and 9.45%. TTFT improves by 21.74% and 17.62%, and post-tool latency by 12.37% and 20.79%. These system-level results include scheduling costs. TAO's asynchronous workers average 6.833 ms and 3.897 ms, respectively.

These net gains support the added optimization cost under the deployments, where asynchronous worker execution averages 3.897–6.833 ms.

[2] SMetric: Rethink LLM Scheduling for Serving Agents with Balanced Session-centric Scheduling

W3 & Q3: MoRI and tool-aware memory management

For MoRI[3], recent tool-call idleness does not directly identify when a session will next need inference or jointly resolve its placement across replicas.

  • Feature: MoRI ranks sessions by recent tool behavior, retains busier sessions in GPU memory, and places more idle sessions in CPU memory, with admission control at both tiers.
  • Shortcoming: relative idleness does not directly predict when a tool will return, and tier assignment alone does not jointly select session–replica placements.

TAO predicts near-term readiness and jointly assigns sessions using replica-specific cache credit. This addresses cases where similarly idle sessions return at different times or compete for different resident-cache opportunities.

We now compare TAO and MoRI using SGLang with HiCache[4] and the same configured KV budgets. DeepSeek uses TP4×2 with 64 workers and GLM uses TP8×1 with 160 workers, on eight H100 GPUs and SWE-Lite's 300 tasks. GPU KV budgets are 28.163 GiB per rank for DeepSeek and 17.000 GiB per rank for GLM; CPU KV budgets are 256 GiB and 576 GiB. Both use replica-private HiCache CPU pools.

ModelMethod / ResultE2E Mean (s) ↓\downarrowTTFT Mean (s) ↓\downarrowPost-tool Mean (s) ↓\downarrowDecode (token/s) ↑\uparrow
DeepSeek-V4 FlashMoRI + HiCache333.2730.8270.8231,167.040
TAO + HiCache269.0160.4990.5611,423.344
TAO Rel. Imprv.+19.28%+39.70%+31.85%+21.96%
GLM-4.7MoRI + HiCache3,172.99853.98255.275401.567
TAO + HiCache1,870.93243.15624.989428.971
TAO Rel. Imprv.+41.04%+20.05%+54.79%+6.82%

The completed DeepSeek comparison shows lower E2E, TTFT, and post-tool latency, with higher throughput under TAO. Relative to MoRI, E2E falls by 19.28%, TTFT by 39.70%, and post-tool latency by 31.85%; decode throughput rises by 21.96%.

ModelMethodGPU peak (GiB)Service PSS peak (GiB)D2H KV (GiB)H2D KV (GiB)H2D DMA mean (ms)H2D bandwidth (GB/s)
DeepSeek-V4 FlashMoRI + HiCache628.648289.876431.1390.13622.830<0.001
TAO + HiCache628.471290.259435.5250.000—0.000
GLM-4.7MoRI + HiCache581.703627.1731,605.3394,982.00515.7300.766
TAO + HiCache581.508623.3651,769.6612,266.70020.4390.444

The resource and performance tables together show lower DeepSeek latency and higher throughput with similar sampled memory usage. TAO records 0.000 GiB H2D and 435.525 GiB D2H, compared with 0.136 GiB H2D and 431.139 GiB D2H for MoRI.

TAO improves on MORI under the same workload settings and configured resource budgets. Readiness prediction distinguishes sessions by their expected next model invocation, while joint placement considers their competing cache opportunities across replicas. With both systems using SGLang + HiCache, TAO delivers 21.96% higher throughput, 31.85% lower post-tool latency, and 19.28% lower E2E latency, demonstrating a system-level benefit for this configuration.


Reference:

[3] Idleness is Relative: Exploiting Tool-Call Idle Windows for Offloading in Agentic Systems with MORI

[4] https://docs.sglang.io/docs/advanced_features/hicache_design

Reviewer_3iiROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

TAO jointly selects and places agent sessions using decayed cache credit, predicted tool readiness, and token count. A dynamic program solves a frozen, discretized placement problem. The resulting plan is checked against live state before execution, with fallback behavior when planning cannot finish within its budget.

Critical strengths
  • Considering tool timing alongside cache affinity is well motivated: a cached session is not necessarily ready to execute, and waiting can change the value of a placement. The implementation takes this seriously through asynchronous planning and live-state revalidation.

  • The component ablations show useful improvements, and the paper is careful to limit its optimality claim to the snapshot problem. It does not claim that exact optimization of that snapshot proves optimal online performance. That distinction is necessary given prediction error and changing system state.

Critical weaknesses
  • The objective needs stronger justification. Under the lexicographic ordering, any advantage in rounded cache credit outweighs every readiness difference. If sessions with running tools remain eligible, they can outrank runnable sessions. Please compare with readiness-first ordering and report how often the current rule reserves capacity for work that cannot yet run. This would connect the mathematical objective more directly to latency and utilization.

  • The grouping optimization is underspecified. Section 3.5 groups cache-equivalent nodes into aggregate capacities. Equal cache values alone do not preserve packing feasibility: two capacity-five nodes cannot fit three size-three sessions, although their aggregate capacity is sufficient. What information does the grouped representation retain to ensure valid per-node placement and preserve the claimed snapshot optimality?

  • The planner-cost evidence is incomplete. Appendix I excludes exhausted searches and fallback execution from the reported planner overhead, although fallback reaches 8.98% of submissions. Please include those costs and specify the capacity quantum and state budget. Measurements on two or four replicas are useful, but do not resolve how the dynamic program scales as placement choices grow.

Questions for authors

See Weaknesses

4 comments

Dear Reviewer 3iiR,

Thank you for your thoughtful review. We appreciate your recognition of our core contributions and experimental evaluation. Below, we provide additional explanations and experiments addressing your comments.

W1: Objective justification with readiness-first experiment

We would like to clarify that the two-level priority hierarchy we implement ensures the priority of runnable tasks. TAO first follows a coarse-grained lifecycle-ordering approach, which is omitted in the original paper since it is a common practice in Agentic Serving [1, 2, 3]. We now gives a· detailed explanation (Appendix B in Revised Paper):

  • Coarse-grained Lifecycle priority: established inference-ready sessions (RR) come first, followed by newly arrived inference-ready sessions (NN), then sessions with running tools (AA). Therefore every session has a lifecycle class where R>N>AR > N > A.
  • Fine-grained Triplet (Our contribution): cache credit, predicted readiness, and token count rank assignments within each class (i.e., RR, NN, and AA). They cannot promote a lower-priority lifecycle class above a higher-priority one in the frozen scheduling objective. Therefore, we eliminate the worries that sessions in tool calls may outrank the runnable tasks during scheduling.

The triplet (ki,b,ri,ti)(k_{i,b}, r_i, t_i) orders cache credit, predicted readiness, and token count within a lifecycle class.** We compare it with readiness-first (ri,ki,b,ti)(r_i, k_{i,b}, t_i) and tokens-first (ti,ki,b,ri)(t_i, k_{i,b}, r_i) on SWE-Lite with 300 tasks. In the tables, >> denotes priority, not numerical magnitude.

Model / ConfigurationScoring orderE2E Mean (s) ↓\downarrowTTFT Mean (s) ↓\downarrowDecode (token/s) ↑\uparrow
DeepSeek-V4 Flash / 64 workers / TP4×2TAO (Ours): ki,b>ri>tik_{i,b} > r_i > t_i185.4100.2242021.523
Readiness-first: ri>ki,b>tir_i > k_{i,b} > t_i213.9450.4621619.890
Tokens-first: ti>ki,b>rit_i > k_{i,b} > r_i222.2950.4491669.201
GLM-4.7 / 160 workers / TP8×1TAO (Ours): ki,b>ri>tik_{i,b} > r_i > t_i1476.19020.066805.939
Readiness-first: ri>ki,b>tir_i > k_{i,b} > t_i2132.48024.316545.030
Tokens-first: ti>ki,b>rit_i > k_{i,b} > r_i2066.13423.031543.784

We also report how often early reservations leave executable ready work waiting. The audit checks actual resumes before tool completion:

  • Waiting work: executable ready requests still waiting after the full resume batch, mostly because of limited capacity.
  • Feasible ready alternative: a waiting request that would fit under a per-backend raw admission budget if unfinished-tool admissions were withdrawn.
ConfigurationScoring orderWaiting workFeasible ready alternative (s)
DeepSeek / 64 workersTAO (Ours): ki,b>ri>tik_{i,b} > r_i > t_i40
ri>ki,b>tir_i > k_{i,b} > t_i21
GLM / 160 workersTAO (Ours): ki,b>ri>tik_{i,b} > r_i > t_i11
ri>ki,b>tir_i > k_{i,b} > t_i152
DeepSeek / 32 workers (Sweet Spot)TAO (Ours): ki,b>ri>tik_{i,b} > r_i > t_i00

Taken together, the two tables' result shows lower E2E latency and TTFT, higher decode throughput, and fewer observed feasible-ready-alternative events under TAO than under readiness-first in both workloads. The first table also shows lower latency and higher throughput under TAO than under tokens-first in both workloads.

The second table shows that ready-alternative counts are 0 versus 1 for DeepSeek and 1 versus 2 for GLM. Early reservations therefore need to be assessed alongside ready-work availability: at 32 workers, none of the 47 early reservations left executable ready work waiting. The report here uses actual batch application and raw budgets, and lifecycle priority applies to the frozen snapshot and quantized capacities, which may lead to small bunch of "Events with a feasible ready alternative" in GLM only.

Reference:

[1] ThunderAgent: A Simple, Fast and Program-Aware Agentic Inference System

[2] HexAGenT: Efficient Agentic LLM Serving via Workflow- and Heterogeneity-Aware Scheduling

[3] DVLA: Dynamic VM Lifetime Aware Scheduling for Drifting Lifetime Distributions and Long-Lived VM Placement Debt

W2: Aggregating feasibility and snapshot optimality

Aggregation simplifies assignment values, while individual node capacities are still considered for feasible placement. When decay and rounding make evaluation identical within a group of nodes for a session, we aggregate the nodes to make computational overhead low. We elaborate the aggregation procedure in details:

  • Grouped selection: solve the DP or LP over aggregate group capacities, retaining group membership, individual capacities, session weights, and eligibility.
  • Small DPs within each group: process nodes in descending capacity order. For each node, solve a single-knapsack DP over the remaining selected sessions. The DP calculations are executed in parallel.
  • Bounded completion: impose a total reconstruction budget. If the budget is exhausted, a Sparse LP will step in to give a solution. Sessions still unplaced remain waiting for the next scheduling round.

We also prove the optimality of this aggregation proceduer, under the assumpltion of complete reconstruction. Every feasible per-node placement maps to an aggregate placement with the same value, so the aggregate optimum UU upper-bounds the original optimum V⋆V^\star. If reconstruction places all selected sessions under the same discretized constraints, its value remains UU:

\qquad V(\hat x)=V^\star.$$ But when complete reconstruction is unavailable, the compromise is to **trade solution optimality for planning latency** while preserving feasibility. In the reviewer's example, only two size-three sessions can be placed on two capacity-five nodes. the third remains waiting. The resulting subset is feasible, but it need not be globally optimal because sequential node decisions may exclude a better combination. --- ## W3: Complete planner costs and placement scalability We now report complete asynchronous planning time, including exhausted searches and fallback execution to show our latency and scalability being promising.(Tables 5 and 10 in Revised Paper). The **capacity quantum is 1,024 tokens**, and the **DP state budget is 50,000 states** (Sec. 4.1 in Revised Paper). We now clarify our DP solving process as follows (Appendix I in Original paper): - **DP Planner**: - *DP search*: A cheap lower bound screens provably oversized sparse searches. Residual capacities that cannot fit any remaining candidate share one state. If the search space is within budget, we solve this DP problem asynchronously. - *Sparse LP*: If the DP search exceeds its state budget, we first solve an sparse LP relaxation over assignments with positive cache credit and readiness, then consider those using only token-count features. - **BFD fallback**: LP failure or the 150 ms process deadline invokes Best-Fit-Decreasing (BFD). Complete timing below includes cancellation and BFD. We test 20 snapshots per configuration with sparse-aware DP admission and the 150 ms LP deadline. Stage columns report means, including failed attempts and zeros for unvisited stages. Note that nodes with identical assignment values and eligibility share an aggregate capacity during DP Planner, the process has been provided in `W2`, and the costs are included here. | **Replicas** | **Candidates** | **DP Planner mean (ms)** | **DP Planner P95 (ms)** | **BFD Fallback mean (ms)** | **Async mean (ms)** | **Async P95 (ms)** | |---:|---:|---:|---:|---:|---:|---:| | 2 | 16 | **12.08** | **19.04** | — | **15.91** | **23.04** | | 16 | 64 | **12.40** | **13.87** | — | **14.08** | **16.03** | | 32 | 160 | **20.53** | **22.09** | — | **22.45** | **24.23** | | 64 | 128 | **18.99** | **20.69** | — | **20.84** | **22.73** | | 128 | 512 | **81.94** | **95.30** | — | **84.88** | **98.25** | The results show how the DP Planner and BFD fallback bound planning costs as placement scale grows: - **DP Planner:** - **DP search:** At 2 replicas (16 candidates), all **20/20** trials finish in exact DP, averaging 12.08 ms (15.91 ms async mean, 25.03 ms P99). - **Sparse LP:** Across **16–128 replicas**, the lower bound screens out oversized DP searches in **0.05–0.28 ms**, and all **20/20** trials finish via Sparse LP, keeping total async time within **14.08–84.88 ms**. - **BFD fallback:** Even at an extreme scale of 256 replicas (640 candidates), DP screening takes 0.38 ms and Sparse LP averages 125.81 ms. **Scalability** is guaranteed through the results. As asynchronous execution keeps solving off the synchronous preparation path (Appendix B in Original Paper. Table 4 in Revised Paper), the calculation cost itself is hidden. Furthermore, Synchronous preparation averages **0.94–2.18 ms** (**0.033%–0.078%** of runtime) across DeepSeek, Qwen, and GLM, while asynchronous planning stays **under 100 ms** up to 128 replicas.

I've read the response and I have no further questions. I will keep my score as-is.

Thank you very much for reviewing our response. We greatly appreciate your recognition of the strengths of our work, including the motivation for considering tool timing alongside cache affinity and the improvements demonstrated by our component ablations. We have also provided additional explanations and experiments to address the concerns you raised, and sincerely hope that these clarifications have adequately resolved them.

Given your positive assessment of our work and the clarifications provided, we would be very grateful if you would consider revisiting your score and potentially increasing it. If any remaining concerns prevent you from doing so, we would greatly appreciate your further feedback. Thank you again for your time and consideration.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Rebuttal

Dear Chairs,

We sincerely thank the reviewers for their constructive feedback. We are encouraged that they recognize the novelty of coupling tool-return readiness with cache affinity for agentic serving, the soundness of our joint admission-and-placement formulation, and our thorough evaluation.

Before detailing our revisions, we highlight the context of our ratings (3, 2, 2) and discussion status:

  • Resolved Concerns: Reviewers ZHNv (3) and 3iiR (2) both responded during discussion, confirming that our clarifications and new experiments resolved their questions with no further concerns.
  • Additional Baselines Provided: Reviewer 5t2q (2) requested comparisons against shared CPU KV caching (LMCache), SMetric, and MoRI. We provided complete, matched-budget experiments across multiple models demonstrating clear gains over all three baselines; while Reviewer 5t2q did not have the opportunity to reply before the discussion window closed, all of their questions have been thoroughly addressed.
  • Case for Acceptance: All raised concerns were empirical or presentation-related (with no fundamental flaws) and are now fully resolved. We respectfully hope the Area Chair will consider the complete rebuttal evidence in making the final decision.

Consensus Among Reviewers

  • Practical Motivation & Novelty: 3iiR and 5t2q highlight that coordinating agent sessions across external tool calls—and combining tool timing with cache affinity—addresses an important serving bottleneck.
  • Sound Joint Optimization: ZHNv and 5t2q validate our joint admission and GPU placement under capacity contention, noting TAO captures combinations missed by greedy heuristics while carefully bounding its snapshot optimality claims (3iiR).
  • Strong Empirical Results: All three reviewers recognize TAO's consistent gains across models, workloads, and concurrencies, supported by clear ablations.

Summary of Revisions and Clarifications

We address every concern with new experiments and revisions (highlighted in the revised paper):

  • Shared CPU KV Caching (5t2q W1 & Q1): Under matched GPU/CPU KV budgets (8× H100, 300 SWE-Lite tasks), TAO + LMCache outperforms vLLM Router + LMCache, reducing post-tool latency by 23.89% (DeepSeek-V4 Flash) and 43.58% (GLM-4.7), lowering TTFT by 32.06% and 41.32%, and boosting decode throughput by 8.62% and 41.67% (28.68% lower E2E latency on GLM), while cutting H2D KV transfers by 73.7% and 93.1%.
  • Comparisons with SMetric & MoRI (5t2q W2, W3, Q2 & Q3):
    • SMetric (LMCache): TAO lowers TTFT by 21.74% (DeepSeek) and 17.62% (GLM), cuts post-tool latency by 12.37% and 20.79%, and boosts throughput by 6.10% and 9.45%, offsetting its 3.90–6.83 ms async scheduling cost.
    • MoRI (SGLang + HiCache): Under matched KV budgets, TAO lowers E2E latency by 19.28% (DeepSeek) and 41.04% (GLM), cuts post-tool latency by 31.85% and 54.79%, and boosts throughput by 21.96% and 6.82%, while cutting GLM H2D transfers by 54.5%.
  • Objective Validation & Hierarchy (3iiR W1; ZHNv W1 & Q1): Appendix B clarifies our coarse-grained lifecycle ordering (C1C_1 established ready ≻C2\succ C_2 newly ready ≻C3\succ C_3 running tools) applied before our triplet (cache credit≻readiness≻tokens\text{cache credit} \succ \text{readiness} \succ \text{tokens}), ensuring tool calls never outrank runnable work. On SWE-Lite, TAO outperforms readiness-first, tokens-first, and four weighted variants without weight tuning (185.41s vs. 213.95s readiness-first E2E on DeepSeek; 1,476.19s vs. 2,132.48s on GLM), with zero feasible-ready-alternative delays at 32 and 64 workers on DeepSeek.
  • DP vs. BFD Ablations (ZHNv W2 & Q2): Under identical scoring, replacing BFD with our joint DP Planner boosts throughput by 16.1% (DeepSeek, 64 workers) and 15.3% (Qwen, 128 workers), cutting TTFT by 57.2% and 8.5%.
  • Planner Overhead & Scalability (3iiR W3; ZHNv W3 & Q3): We specified the capacity quantum (1,024 tokens), DP budget (50,000 states), and Sparse LP deadline (150 ms) in Sec. 4.1/Appendix I, reporting full costs including exhausted DP searches, Sparse LP solves, and BFD fallbacks (Tables 5 & 10: 1.59–12.50 ms mean DP Planner; 0.022–0.033 ms BFD). Async planning stays under 100 ms up to 128 replicas (15.91–84.88 ms mean; 125.81 ms at 256 replicas), while synchronous preparation takes 0.94–2.18 ms (0.033%–0.078% of runtime; Table 4).
  • Node Grouping Guarantees (3iiR W2): We detailed our two-stage reconstruction (parallel single-knapsack DPs plus bounded Sparse LP fallback) and proved that complete reconstruction preserves global snapshot optimality (Vagg∗=V∗V_{\text{agg}}^* = V^*) while bounded reconstruction guarantees per-node feasibility.

We believe these comprehensive additions resolve all reviewer concerns and support to accept the paper.

Thank you again for your time and consideration!

Best regards,
Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.