Skip to content

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

🕒 Published (v1): 2026-07-09 14:55 UTC · Source: Arxiv · link

Why this paper was selected

Session-centric LLM scheduling rethinks serving for agents vs. human request patterns

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

SMetric is a request scheduler for LLM clusters serving agent workloads, where KV cache reuse exceeds 80% of tokens but existing cache-aware schedulers inadvertently create severe load imbalance. It introduces balanced session-centric scheduling: route each session's first request purely for load balance (offloading its cache reuse to the global KV$ tier), and route all follow-up requests cache-aware to local instances, achieving both high TPS and high reuse without overloading the global tier.

Problem

Existing LLM schedulers (e.g., LMetric, BAILIAN's production scheduler) optimise for KV cache (\(\text{KV\$}\)) reuse by routing each request to the instance that already holds its cached KV tensors. In agentic workloads this backfires: first-turn requests across sessions share the same agent framework system prompt, so all get routed to the same few instances that cached it; and since all follow-up requests follow the first turn (intra-session locality), entire sessions are pinned to those already-overloaded instances. The result is that a cluster's aggregate tokens-per-second (TPS) is capped by the bottleneck instances while the rest sit idle, even though the workload's token distribution is inherently balanced. Prior scheduling work targeted per-token latency (TTFT/TPOT) for human chat, not cluster-wide TPS for agents, and was validated on non-agentic traces.

Method

SMetric exploits two structural properties of agentic workloads and a two-tier KV$ store (local GPU memory + global CPU memory linked by RDMA):

  1. Session-turn detection (stateless): The scheduler reads the turn number embedded in each request's metadata (derivable from the request itself without any per-session router state). Turn 1 (session-first) vs. turn ≥ 2 (follow-up) triggers different policies.

  2. Differential routing policy:

  3. First request of each session: routed purely for load balance (least-loaded instance). Its system-prompt KV$ is fetched from the global tier on whichever instance it lands, which is cheap because system-prompt blocks are compact and shared across sessions.

  4. Follow-up requests: routed cache-aware to the instance holding their session's prior-turn KV$ in local GPU memory (traditional prefix-hit routing). Because of intra-session locality (Finding 4: ~90% of reuses occur within ~100 s), this KV$ is almost always still present locally.

  5. Session migration: A tail-case mechanism migrates sessions when prolonged skewness accumulates on a single instance, preventing long-lived heavy sessions from defeating balance.

The router remains stateless: each routing decision is a pure function of the incoming request, with no per-session bookkeeping.

Key Contributions

  • First systematic empirical study of KV$ reuse and scheduling behavior on two large-scale production agentic serving traces (BAILIAN, May 2026, peak hours).
  • Six numbered workload findings: >80% reuse ratio, >65% intra-session locality, system-prompt reuse for first turns, fast reuse recurrence (~90% within ~100 s), skewed session token usage, and despite skewness the workload is inherently balanceable.
  • First analysis of how existing schedulers behave under two-tier KV$ stores in agentic settings, revealing the load-imbalance failure mode.
  • SMetric: a stateless, session-centric scheduler that differentiates first vs. follow-up requests to decouple load balance from cache reuse.
  • Implementation on vLLM + LMCache with evaluation under both PD-colocation and PD-disaggregation architectures.

Results

  • PD colocation with global store: SMetric improves cluster TPS by 10–16% over state-of-the-art schedulers (BAILIAN production, LMetric) while also lowering P50 and P90 TPOT.
  • PD disaggregation: SMetric improves prefill TPS by 2–34% over the best-performing baseline across global-tier provisioning levels, with 37% lower median TTFT.
  • Evaluated on a 32-instance vLLM cluster serving Qwen3-Coder-30B-A3B replaying Trace 1; the global KV$ store is Mooncake + LMCache.
  • Load-balance-only scheduling (no cache awareness) performs worse than SMetric, confirming that preserving local-tier reuse for follow-up requests is necessary.

Limitations

  • Only two serving architectures (PD colocation, PD disaggregation) are studied; inter-cluster scheduling is explicitly out of scope.
  • The global KV$ tier is modelled as two-tier only (GPU + CPU/RDMA); cloud-storage (S3) tier behavior is not modelled.
  • The session-migration mechanism for tail cases is described but not evaluated in detail.
  • Traces are from a single commercial coding-agent product (BAILIAN); generalisability to other agent types (e.g., long-horizon planning agents, RAG agents) is asserted but not measured.
  • SMetric requires that session-turn metadata be available in the LLM API request; providers that do not expose or pass this metadata cannot use it without protocol changes.
  • Evaluation uses only one model family (Qwen3-Coder-30B-A3B); results for larger or different architectures are not reported.

Relevance to Agentic AI / LLM Agents

SMetric directly targets the infrastructure layer that every LLM agent deployment depends on: the serving cluster. It establishes that agentic workloads have fundamentally different scheduling requirements than human chat—higher KV$ reuse ratios, tolerance for relaxed per-token latency, and strong intra-session locality—and that ignoring these properties leaves 10–34% of cluster throughput on the table. For researchers building or deploying LLM agents at scale (e.g., multi-step tool-calling agents, coding agents like Claude Code), these findings quantify the serving overhead and show that session-aware scheduling is a first-class concern alongside model capability and context management. The paper also provides rare empirical characterisation of production agentic traces, making its workload findings (Findings 1–6) valuable reference data for system co-design between agent frameworks and serving infrastructure.