LM ETRIC* : Simple is Better – Multiplication May Be All You Need for LLM Request Scheduling Dingyan Zhang†1 ,
Jinbo Han†1 ,
Kaixi Zhang†1 ,
Wenyuan Yu2 , 1
Xingda Wei
Jingren Zhou2 ,
arXiv:2603.15202v2 [cs.DC] 25 Mar 2026
,
Sijie Shen2 ,
Chenguang Fang2 ,
Rong Chen1
Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University
Abstract
2
Alibaba Group
of instances for serving where each cluster contains a global scheduler that routes incoming requests to the instances it manages [32, 42, 43, 19, 27, 4, 37]. Upon receiving a request, the instance generates result tokens in two phases: The prefill (P) phase generates the first result token, and the serving quality is measured by time-to-first-token (TTFT). The decode (D) phase then generates the remaining tokens in a streaming manner, and its serving quality is measured by time-per-output-token (TPOT). Providing an effective scheduling policy is crucial for cluster-level LLM serving because, similar to traditional request routing [12, 45, 17], better placement significantly reduces overall request latency (lower TTFT and TPOT) thanks to factors like better load balancing across instances. Lowlatency serving is especially critical for current interactive applications such as ChatGPT [29] and copilots [16], as it is key to meeting user expectations [7, 46, 15]. Moreover, recent agentic workloads consume tokens rapidly through computational programs [6, 18, 28]. Achieving a good LLM-specific scheduling policy is nontrivial: First, considering only load balancing between different instances—which is adopted by a recent state-of-the-art serving system vLLM [37] and traditional request routing is insufficient. This is because the computation required to process each request is different across instances due to KV$, the intermediate context of the processed tokens (§4.2). Specifically, if an incoming request’s (partial) input tokens hit the KV$ cached on an instance, the instance can skip generating the corresponding KV$ for the hit tokens, thereby accelerating the subsequent prefill and decode stages. However, incorporating only KV$-aware indicators into scheduling decisions (e.g., the KV$ hit ratio if routing a request to an instance) is also insufficient, because it biases requests towards instances with KV$ hits and hurts load balancing across instances (§4.3). To balance the two objectives—KV$-awareness and load balancing, three different combination strategies exist today. First, linear combination strategies (i.e., weighted sum) [23, 27] combine the indicators for each objective into a single score for scheduling (§4.4). It is the simplest strategy yet a popular choice adopted by current works and one of the world’s top LLM service providers (BAILIAN). However, linear combination requires complex workload-specific hyperparameter tuning to achieve both objectives. Moreover,
High-quality LLM request scheduling requires achieving two key objectives: whether the routed instance has KV$ to accelerate the request execution and whether the workload is balanced across instances. Achieving both objectives is challenging because pursuing one objective may compromise the other. Current approaches adopt various combinators (e.g., linear combinations) to compute a scheduling score combining indicators for the two objectives, which are complex in that they either require significant workload-specific hyperparameter tuning or model-hardware-aware simulator development, and could still lead to suboptimal performance. In this paper, we show that using a simple multiplication of two carefully chosen indicators—one for KV$-aware (new prefill tokens if routed to an instance) and one for load balancing-aware (current batch size of the instance)—as the scheduling score can simultaneously achieve both objectives well without any hyperparameter tuning. The key idea is that the multiplied score considers both objectives in a manner similar to a linear combination, with a nice property that the original hyperparameters are canceled out during comparison so we don’t need tuning to find the best parameters. The two indicators are chosen based on our analysis of LLM characteristics, and our extensive experiments show that this simple approach can reduce TTFT by 92% and 52%, and TPOT by 21% and 20%, compared to vLLM-v1 and a production scheduler on real-world workloads covering chatbots, API calls, and coding agents. We also mathematically derive the conditions under which multiplication may fail, and find that such conditions are extremely rare in practice and can be detected (and mitigated) beforehand.
1
1
Introduction
This paper studies how to efficiently route LLM requests to a cluster of serving instances—the minimal model deployment unit. Serving LLMs has become a key building block in modern society, and LLM providers typically deploy clusters * The name LM ETRIC stands for Large Model metric, and also pays homage
to Lyapunov, whose stability theory partly inspired the multiplicative scoring approach, and to Markov, for his foundational contributions to queueing theory. † Most work done when intern at Alibaba Group. Xingda Wei is the corresponding author ([email protected]).
1
a statically tuned hyperparameter is suboptimal due to the possibly dynamically changing workloads (§4.4). Second, filter-based strategies first filter out instances that are suspected to suffer from imbalanced workloads, and then select the instance with the most KV$ hits among the remaining instances [3]. It still requires non-trivial workload-specific tuning to determine the filtering threshold. Worse still, its scheduling is biased towards load balancing and thus cannot fully utilize the KV$ cache (§4.5). Finally, simulation-based strategies [32, 19, 47, 10] first use a simulator to predict the expected latency of routing a request to each instance, and then use the latency as the scheduling score. The simulator estimates the latency based on its current indicators, e.g., KV$ content and queued requests, so it can be viewed as a high-order combination of indicators used by other strategies. However, the effectiveness of the strategy highly relies on the accuracy of the simulator, which requires complex per-model, per-hardware, and per-deployment development. Otherwise, an inaccurate simulation can lead to poor scheduling performance (§4.6). Even with an accurate simulator, it may still fail to achieve comparable performance with other candidates in some cases. In this paper, we show that multiplying one indicator for KV$-awareness and one indicator for load balancing as the scheduling score can effectively combine the two objectives without complex hyperparameter tuning or any simulator. The key idea is that by using multiplication to replace the addition operation in a linear combination, the hyperparameters are canceled out during the score comparison among different instances. As a result, the score preserves a trend similar to that of a linear combination without requiring any hyperparameter tuning (§5). To make the simple multiplication work well in practice, we found that careful indicator selection is important (§5.1). For example, using the number of new prefill tokens when routing a request to an instance considering KV$ hits as the KV$-aware indicator is better than KV$ hit ratio. Additionally, using the current batch size of the instance as the load-balancing indicator is better than using the number of total tokens (including the decode context tokens) queued on the instance. Finally, the multiplication can fail in some rare cases; so we mathematically derive the approximate conditions for these cases. Based on the formulated conditions, we found such conditions are extremely rare in practice and can be detected with our two-phase approach (§5.2). Upon detection, we can further fall back to a load-balancing-only policy to mitigate the issue. We have compared our method with state-of-the-art methods, including vLLM [37], AI-Dynamo [27], LLM-D [19] and the one used in BAILIAN—one of the world’s largest LLM providers—on real LLM serving workloads covering chatbots, API calling, and coding agents (§4.1). Evaluation on popular models covering both dense and MoE architectures confirms the benefits of our approach on an H20 cluster with
Request: How to submit to OSDI’26?
KVCache($)
…
… https:
1
TTFT The prefill phase
//osdi26. 2
TPOP usenix. The decode phase
Figure 1: An illustration of generating output tokens using an LLM and the two performance metrics: time to first token (TTFT) and time per output token (TPOT).
up to 16 GPUs. TTFT We will open-source our code, including all benchmarking tools and the open-source traces, upon publication. Discussion: PD-colocation vs. PD disaggregation. We assume that both prefill and decode requests are served on the same instance—a setup termed PD-colocation. While there also exist deployments where prefill and decode requests are served on different instances (PD-disaggregation) [30, 46], PD-colocated serving is still adopted in practice [42] because it is easier to maintain (no instance role management) and does not rely on fast networking between instances. Although BAILIAN largely deploys PD-disaggregated serving, some services still rely on PD-colocated deployments. Efficient scheduling for PD-disaggregated serving is beyond the scope of this paper.
2
LLM Serving and Scheduling
2.1
trim LLM = 0.25cm Background: Scheduling requests in aYY.Ycm Cluster
XX.Xcm 0.25cm, clip Serving requests with an LLM (Figure 1). LLMs generate tokens in an auto-regressive manner through two steps: ➀: In the prefill phase, the input tokens are fed into the model, and the model processes these tokens to produce the first output token. The LLM then enters the decode phase (➁) to generate the subsequent tokens one-by-one. Each generation requires the context of all previously generated tokens and the input tokens. To accelerate generation, the processed context is materialized as tensors stored in GPU memory, typically termed key-value cache (KV$). As a result, the computation in the decode phase is significantly smaller than that in the prefill phase because no input token KV$ needs to be generated. From an LLM service provider’s perspective, two key performance metrics related to the serving quality are: time-tofirst-token (TTFT) and time-per-output-token (TPOT). TTFT is important because it directly determines the LLM service’s responsiveness to user requests, while TPOT not only affects the subsequent responsiveness but also the overall request completion time. Serving instance and KV$ cache (Figure 2). In an LLM serving system, an instance is the minimum unit that serves requests and hosts one complete copy of the LLM parameters. The instance can contain multiple GPUs if the LLM is too 2
1
An LLM Request
Total BS
Queued BS (Q-BS)
#tokens
Prefill Decode Decode
The LMetric Global Scheduler
#New prefill tokens (P-tokens)
Scheduling w/ our DSL
3
1 1 score = 4 * Q-BS.update(req) + 1 * R-BS 2 sched_to = instances .filter(...) # e.g., OOM 3 .select_min(score) # or max 4
2
Running BS (R-BS)
Device memory e.g., (HBM)
KV$
（Detailed in Figure 3)
Decode time (one token)
… Total Decode Time (for a request)
Q-BS|R-BS|...
3
Q-BS|R-BS|...
...
...
2
…
Completion queue
executes a scheduling policy to determine the destination instance for each request, and this policy is our focus. Note that the provider may deploy multiple clusters for the same model to enhance reliability and geo-affinity, and routing trim = 0.25cm YY.Ycm requests between clusters is out of the scope of this paper. XX.Xcm 0.25cm, clip At a high level, all existing scheduling policies can be viewed as a three-step process: The router first (optionally) filters out some instances, then scores them according to a preference order, and finally routes the request to the bestscoring instance. The score is based on the indicators collected from each instance, and we will describe them in detail in our analysis (§4).
… Prefill time
Q-BS|R-BS|...
2
Figure 4: The system architecture of the LM ETRIC metric factory and its programming model for scheduling algorithms.
LLM Requests
(b)
1
Serving instances that could execute requests
Global scheduler
Instances in a cluster
SysIndicators
Work queue
Figure 2: The system view of how an LLM serving instance serves requests and some direct system indicators that can be collected by the global scheduler. The detailed meaning of each Running indicator will be batch described upon the first usage. BS is the abbreviation for size batch size.
(a)
LLM request (req) InstanceId
Request route time
Figure 3: (a) System view of a cluster LLM serving system, and (b) comparison of per-request serving time and routing cost.
3
The Analysis Framework
To systematically analyze different scheduling policies in large to fit into a single GPU’s memory. Regardless of singlean apples-to-apples manner, we implement a flexible LLM or-multiple GPU instances, the overall serving flow is the scheduling analysis framework—LM ETRIC. The key drivers same: when it receives a request, the request is pushed into a for LM ETRIC are twofold: (1) Existing policies are buried in queue containing requests (either prefill or decode) waiting to concrete (both open-source and closed-source) implementabe executed on this instance (❶). Once the GPU(s) become tions of different serving systems, making it hard to compare trim = 0.25cm YY.Ycm available, all queued requests are formed into a batch, and them in an apples-to-apples manner. For example, the Go the batch is executedtrim on GPU(s) efficiently with chunked clip XX.Xcm 0.25cm, implementation of vLLM’s policy on AIBrix [3] is 6.2 × = 0.25cm YY.Ycm prefill [2] (❷). AfterXX.Xcm the execution, the instance faster than vLLM’s Python implementation [37] due to a later 0.25cm, clip examines whether the current requests need further decoding; if so, the confirmed performance bug [38]. Meanwhile, our Rust-based requests are re-enqueued (❸). implementation achieves a further 1.2 × speedup over AIBrix One notable feature is that the serving is stateful: the rewith the same vLLM policy. (2) A unified framework simpliquest’s KV$ is retained in GPU or CPU memory even after fies implementing new policies for comparison: Though comthe request finishes its generation (KV$ cache [32, 14, 39]). plex, all existing policies boil down to computing scheduling The benefit is that if a future request is routed to an instance scores based on the indicators of the instances. By providing and there is a prefix match with a previously cached KV$, a unified indicator factory, our framework allows exploring the instance can skip the computation for the matched prefix policies with a few lines of code (described below). tokens and thus significantly reduce the computation cost. In Indicator factory. LM ETRIC is a standalone inference router our example in Figure 2, tokens that are colored blue can skip implemented in Rust that can collaborate with any LLM servthe computation if they have a KV$ hit. ing engine. Its key component—as shown in Figure 4—is an Request scheduling in a cluster (Figure 3). To handle indicator factory that automatically collects and computes large volumes of requests, LLM service providers typically the indicators (if necessary) required for different scheduling deploy clusters of instances to serve a model, where each policies. Choosing Rust enables LM ETRIC to be extremely cluster has a dedicated global scheduler to route requests to efficient and robust. For high scalability, indicator collection the instances managed by it, as shown in (a). The scheduler is piggybacked on the receipt of responses from the instances. 3
Llm-cl
API
ChatBot Coder ToolAgent
API
Coder
ToolAgent
ChatBot
Figure 5: Our studied traces that cover major scenarios in powering LLM services.
For example, LM ETRIC maintains a long-lived connection Workloads. We conduct analyses on real-world LLM servto each vLLM instance, and when vLLM sends a response ing traces, both open-source and collected from BAILIAN, back, LM ETRIC extracts the required indicators from the Running reand cover common LLM applications: ChatBot (Qwen) and size sponse header and updates the corresponding indicatorsbatch in Agent (Qwen) [9] are open-sourced traces from Alibaba the factory. Cloud that collect requests sent from a chatbot service similar to ChatGPT and an LLM API calling agent service [6, 18, 28], Programming model. LM ETRIC provides a simple API respectively. Coder collects requests issued by coding copilot to implement different scheduling policies. Specifically, all services to a dedicated cluster in BAILIAN on a single day policies essentially first compute a score for each instance in November 2025, and ToolAgent (Kimi) [26] is another and then route the request to the instance with the best (e.g., open-sourced trace from Kimi that also collects requests from minimum or maximum) score. Our API allows developers to an agent service. For traces except ToolAgent (Kimi), they define score functions over per-instance symbolic indicators are all collected from a single cluster routed by one global supported by our factory with a few lines of expressions. Line router. ToolAgent (Kimi) does not mention how the trace is 1 in Figure 4 shows a concrete policy adopted by vLLM [37]: collected. it computes the score as a weighted sum of Q-BS (queued Our analyzed workloads are representative—not only bebatch size—the number of queued requests in an instance’s cause of the breadth of application scenarios chosen, but also queue) and R-BS (the number of running requests on the inbecause each selected trace preserves the essential characterstance). With the defined score function, when deciding where istics for evaluating LLM scheduling policies. Specifically, to route a new request (line 4), LM ETRIC first retrieves and all requests in our traces contain the (hashed) content and computes the concrete indicator values from the indicator facthe timestamp of the request issuance, which are critical for tory in parallel, then derives the scores for all instances, and evaluating the impact of KV$-aware scheduling on global finally routes the request to the instance with the minimum scheduling (see §4.2). Other popular datasets like AzureLLMscore. Trace [8] or BurstGPT [41] do not provide such content. Note that with traces containing hashed content, we can still re4 Characterizing LLM Request Scheduling play it with behavior that exactly matches the original one by reconstructing inputs according to the hash value, and each 4.1 Characterization Methodology instance executes the same number of decodes as in the traces Testbed and instance used. Without explicit mention, regardless of the EOS token [40]. we conduct all our experiments on a testbed containing 16 Figure 5 visualizes key features of our evaluated traces, NVIDIA H20 GPUs—hardware similar to that used for hostincluding their request arrival rates, input and output token ing LLM services at BAILIAN. Each GPU has 96 GB HBM, numbers, and the KV$ hit rates assuming an infinite KV$ which is sufficient for hosting common models available on cache space. Note that the request arrival rate is normalized the market [42]. The router is deployed on a high-end CPU due to confidentiality considerations required for the Coder server with 160 Intel Xeon cores and 1 TB of DRAM. Our trace. For all these traces, we observe that over a given serving instance runs the latest vLLM-v1 (vLLM) [37]—the stateinterval (e.g., 1 hour), the request arrival and KV$ hit rates are of-the-art LLM serving engine with the latest optimizations, relatively stable, with a few short-term fluctuations. Besides, such as chunked prefill [2] and fast GPU kernels [13]. though the input and output token numbers vary across traces, Models. We chose LLM models that are representative of they are typically not so large except for a few outliers. different architectures and popular choices on the market, including dense (Qwen2-7B) and mixture-of-experts (MoE) Trace scaling. Since the traces are collected from clusmodels (Qwen3-30B) [42]. ters with different scales than our testbed, we scale the
trim = 0.25cm YY.Ycm XX.Xcm 0.25cm, clip
4
Cache Hit Ratio
(a) vLLM
1
req = receive()
2 3 4 5
## one score per instance score = 4 * Q-BS + 1 * R-BS sched_to = instances .select_min(score) req.forward(sched_to) req = receive()
2 3 4 5 6
kv_hit = KV$.match(req) score = 𝜆 * (1-kv_hit) + (1-𝜆) * norm(BS) sched_to = instances Range [0,1] .select_min(score)
Cache Hit Ratio
req.forward(sched_to)
20s
Time
40s
0.5 0.0
0
25
50
Time (ms)
75
200
400 600 800 Time (seconds)
1000
1200
=0.4
=0.55
=0.7
=0.9
0.5 0.0 0
50
100 150 200 250 300 350 400
Time (seconds)
Figure 9: A comparison of the KV$ hit ratio by changing the weight of KV$-awareness in the policy described in Figure 6 (b) on ChatBot Trace with Qwen3-30B model.
100
trimof=the 0.25cm YY.Ycm Figure 7: A comparison performance of vLLM and KV XX.Xcm 0.25cm, clip cache-aware scheduling on ChatBot Trace with Qwen3-30B model. Other workloads and models are similar.
traces according to our testbed capability similar to prior work [25, 5, 20, 44, 34]. Without explicit mention, we scale the average request arrival rate to half of the maximum rate of our testbed obtained via offline profiling. This approximates the serving configurations in BAILIAN because if the arrival rate approaches the serving capacity, a common practice in BAILIAN is to reroute the requests to another underloaded cluster, or simply reject them in non-critical cases (like ChatAPP) [32]. Otherwise, the service-level objectives (SLOs) of many requests cannot be met due to queuing [31]. Our endto-end analysis in §6 further measures the impact of different request arrival rates on scheduling performance, and shows consistent results. 4.2
1.0
Prefill time |Ins.1 - Ins.2| (sec/10sec)
0.0 0ms
TPOT CDF
TTFT CDF
1.0
vLLM + $hit ratio vLLM
0.0 0
vLLM (avg: 0.173)
Figure 8: A KV$ hit ratio comparison of vLLM vs. KV$-aware scheduling on ChatBot Trace with Qwen3-30B model. Other workloads and models are similar.
Figure 6: (a) The scheduling score of vLLM and (b) adding KV$awareness to its score for LLM scheduling. Note that the linear combination of two indicators has only one degree of freedom (the weight λ).
0.5
0.5
(b) vLLM + KV$-awareness (e.g., Bailian-like)
1
1.0
vLLM + $hit ratio (avg: 0.378)
1.0
5.0 2.5 0.00
=0.7
=0.9
vllm-kvcache.
100
200
Time (seconds)
300
400
Figure 10: A profile of the workload imbalance between two instances when running with two different weights in a linear combination on the ChatBot Trace using the Qwen3-30B model. The reported metric is the absolute served prefill time in each 10-second window between the two instances (Inst.).
substantially reduces request latency. Figure 6 (b) shows a simple extension of vLLM adopted by BAILIAN and others [27, 4] to make request scheduling KV$-aware: it adds a KV$ indicator to the score function—a ratio that estimates the KV$ hit ratio if the request is routed to that instance. Note that KV is the symbolic value representing the per-instance KV$ hash map. There are two points to note here: (1) the load balance indicator (batch size) needs to be normalized to [0, 1] to match the scale of the hit ratio because otherwise they cannot simply be added together; (2) the analysis in this section assumes the linear combination coefficients (λ) are fixed, and the next section discusses the rationale for setting them. As shown in Figure 7, adding KV$-awareness to a loadbalancing-only policy improves the average TTFT by 84% and the average TPOT by 17%, which is as expected because it increases the KV$ hit ratio as profiled in Figure 8. Interestingly, although the improved KV$ hit ratio—at a first glance—is only beneficial to the prefill, we found it is also helpful to the decode time because it reduces the computation required for each instance, allowing the instance to dedicate more GPU time to the decode phase.
Load-balancing Alone is Insufficient for LLM
A starting case: the vLLM policy [37]. Our study starts with the default global scheduling policy adopted by vLLM [37]—a popular open-source LLM serving engine widely used in both industry and academia. Figure 6 (a) shows its scheduling method, which uses the batch size of each instance as the indicator for the routing score. It is essentially a variant of the classic load-balancing-centric join-the-shortestqueue (JSQ) policy with an extension for LLM: at each instance, the batch size includes both the requests running on the instance (R-BS) and those queued in the instance’s queue (Q-BS). Retrofitting vLLM with KV$-awareness (BAILIAN). While JSQ tries to balance the workload across instances, it is unaware of the KV$ state of the incoming requests. That is, routing requests to instances with a higher KV$ hit rate 5
Diverse
Diverse
𝜆 described in Figure 6 (b)
Best
𝜆 described in Figure 6 (b)
Figure 11: An analysis of how the performance varies with different hyperparameters on four traces with linear-combination-based method. The model used is Qwen3-30B.
4.3
KV$-awareness vs. Load balancing: The Trade-off
ChatBot trace. The prefill time refers to the number of seconds the instance spends on prefill within each 10-second While intuitive, integrating KV$-awareness into the system is window. This is a good measure of workload assigned to each non-trivial. The root cause is that considering KV$-awareness instance because intuitively, most tokens are generated during may interfere with load balancing. Specifically, when defining the decode phase. Therefore, if the prefill time dominates scores with a linear combination as described previously, the processing time𝜆 on an instance, that instance generates described in Figure 6(b) the priority of the considered objective is controlled by the fewer tokens than others. For each profiled setup, we select weight assigned to each indicator in the scoring function two instances (from a total of 16 instances) with the highest (λ = 0.4) in Figure 6 (b): if we assign a larger weight to the standard deviation of prefill time for ease of presentation. We KV$ component, the router will prioritize routing requests observe that for setups with a higher KV$ priority (λ = 0.9), to instances with higher KV$ hit ratios, even though other the total prefill time differs significantly between the two intrim = 0.25cm YY.Ycm instances may have a much lower load. This, on the other stances. In comparison, a balanced setup (λ = 0.7) exhibits hand, may lead to load imbalance across instances. XX.Xcm 0.25cm, clipsimilar prefill times, and during this period, the average prefill Figure 11 illustrates this trade-off by presenting the overall time is also similar. Specifically, with λ = 0.7, the average TTFT and TPOT of using a linear combination of described in prefill time is 3.43s vs. 3.40s for the two instances, whereas the previous section (Figure 6 (b)) with various weights on the with λ = 0.9, it is 3.57s vs. 2.17s. KV$-awareness component. We can see that when increasing the weight from 0.4 to 0.9, the TTFT first gradually decreases 4.4 The Case of Linear Combination and then increases except for the API trace, which has less Based on the trade-offs explored previously, using a linear impact due to its short input length. combination to achieve both KV$-awareness and load balTo demystify the trend observed with the trade-off, Figure 9 ancing leads to two issues: further shows the KV$ hit ratio when changing the weight of KV$-awareness on the ChatBot trace. Other traces show Cons #1. Requires workload-specific hyperparameter tunsimilar trends. We can clearly see that when increasing the ing. The importance of KV$ and its impact on load imbalKV$ weight, the overall KV$ hit ratio increases accordingly. ance is workload-dependent. For example, Figure 11 presents This explains the reduced TTFT when increasing the weight the tuning results for different traces when running a Qwen3from 0.4 to 0.7. 30B model. We can see that the evaluated optimal weight for Despite the increased KV$ hit ratio, there is a knee point each workload varies: in ChatBot the optimal weight is 0.7, in the weight (e.g., 0.7 for the ChatBot), beyond which the while in API it is 0.55, even though both workloads have a overall latency starts to increase. This is due to load imbalsimilar KV$ access pattern. Note that we cannot afford to ance across instances and we have profiled this phenomenon sweep all possible configurations, as replaying each trace on in Figure 10, which plots the prefill work assigned to two the testbed consumes a substantial amount of GPU time. As instances using different linear combined weights (0.7 vs. a result, the performance of the linear combination requires 0.9) for serving the same 400-second burst period using the workload-specific hyperparameter tuning that is non-trivial in 6
TPOP (ms)
TPOP (ms)
TPOP (ms)
TPOP (ms)
ChatBot P99 80 79 83 82 75 63 40 0 8 12 16 20 BL API P99 100 86 92 100109 68 50 0 4 8 12 16 BL Coder P99 80 73 70 65 66 45 40 0 4 8 12 16 BL AgentTool P99 400 327340358356 154 200 0 2 4 6 8 BL
TPOP (ms)
TPOP (ms)
TPOP (ms)
ChatBot P90 60 58 58 54 54 50 30 0 8 12 16 20 BL API P90 40 37 37 37 38 30 20 0 4 8 12 16 BL Coder P90 50 51 42 39 39 32 25 0 4 8 12 16 BL AgentTool P90 66 58 59 64 60 30 30 0 2 4 6 8 BL
TPOP (ms)
TPOP (ms) TPOP (ms)
TPOP (ms)
TPOP (ms)
ChatBot P50 30 27 27 27 27 24 15 0 8 12 16 20 BL API P50 16 14 14 14 14 13 8 0 4 8 12 16 BL Coder P50 33 30 29 28 30 25 15 0 4 8 12 16 BL AgentTool P50 16 17 16 15 16 13 8 0 2 4 6 8 BL
TTFT (s)
TTFT (s)
TTFT (s)
ChatBot P99 10 9.3 5 4.7 5.2 2.8 1.6 0 8 12 16 20 BL API P99 2 1.5 1.7 1.9 2.0 1.3 1 0 4 8 12 16 BL Coder P99 16 16.4 8 2.7 2.7 2.6 1.7 0 4 8 12 16 BL AgentTool P99 40 37.140.039.140.134.6 20 0 2 4 6 8 BL
TTFT (s)
TTFT (s)
TTFT (ms)
TTFT (ms)
ChatBot P90 882 800 821 784740555 400 0 8 12 16 20 BL API P90 500 384422463 338 289 250 0 4 8 12 16 BL Coder P90 2 2.0 1.2 1.2 1.10.98 1 0 4 8 12 16 BL AgentTool P90 8.8 8 6.3 6.5 7.3 4.3 4 0 2 4 6 8 BL
TTFT (s)
TTFT (ms)
TTFT (ms)
TTFT (ms)
TTFT (ms)
ChatBot P50 111 100 108105104 92 50 0 8 12 16 20 BL API P50 80 69 70 71 72 63 40 0 4 8 12 16 BL Coder P50 400 412264 238227183 200 0 4 8 12 16 BL AgentTool P50 338 269 300 279278 179 150 0 2 4 6 8 BL
Figure 12: An analysis of how performance varies with different hyperparameters on four traces using a filter-based combination method. BL denotes the linear-combination-based method for comparison, tuned with the best hyperparameter. The numbers (2,4,6,8) are the range described in Figure 13. The model used is Qwen3-30B. 1 2 3
req = receive()
Filter-based method
(BS.max() - BS.min()) exceeds a threshold (line 3). If so, the router abandons KV$-awareness and simply routes the request to the instance with the smallest batch size for load balancing (lines 4–5). Otherwise, the router uses the KV$ hit ratio as an indicator to route requests to instances (lines 6–9) for KV$-awareness.
(e.g., Aibrix-KV$) kv_hit = KV$.match(req) if BS.max()– BS.min() > Range: # Load balance 4 sched_to = instances 5 .select_min(BS) 6 else: # KV$-awareness 7 sched_to = instances 8 .select_max(kv_hit) 9 .select_min(bs) 10 req.forward(sched_to)
Cons #1. Still require workload-specific hyperparameter tuning. Similar to linear combination, filter-based methods also require hyperparameter tuning because the threshold for determining load imbalance (Range) is workload-dependent. As shown in Figure 12, the optimal threshold of a typical filter-based method [3] varies across workloads: for example, in Coder, increasing the threshold from 4 to 16 improves the P50 TTFT and TPOT by 44% and 15%, respectively. On the other hand, for the API trace 16 is a better choice than 4.
Figure 13: The pseudocode of filter-based combination of KV$awareness and load balancing in LLM scheduling, simplified from prefix-cache policy of AIBrix [3].
practice due to the diversity of workloads [39]. Con #2. Sub-optimal performance. During the evaluation in §6, we found that a statically tuned weight cannot always achieve competitive performance compared to other baselines. We hypothesize that this is because the optimal weight may vary over time; for example, the KV$ hit pattern of different requests may change over time (see the second row of Figure 5). However, to the best of our knowledge, all existing trim = 0.25cm YY.Ycm work uses a fixed tuned weight for the entire serving duration. XX.Xcm 0.25cm, clip While it is possible to design strategies to adaptively tune the weight over time, doing so would subsequently add system complexity. 4.5
Cons #2. Sub-optimal performance. Besides hyperparameter tuning, filter-based combination is slower compared to linear combination with properly tuned weights, as shown in Figure 12, because it biases towards load balancing and may forgo the benefits of KV$-awareness. Specifically, when a load imbalance is detected, it completely ignores KV$awareness, even though routing requests to instances with a higher KV$ hit ratio could still be beneficial if theaibrix-kvcache-v amount of reduced computation is significant (as it helps reduce the load). With linear combination, this is possible as long as the weight assigned to the KV$ hit ratio is not too small. This is not possible in filter-based methods.
The Case of Filter-based Combination
Methodology. Figure 13 shows how a typical filter-based combination works for integrating KV$-awareness and load balancing in typical LLM scheduling systems like AIBrix [3]. First, the router checks whether the current cluster has an imbalanced load—i.e., the range between the maximum and minimum batch sizes across instances
4.6
The Case of Simulation-based Combination
Methodology. Finally, simulation-based methods [32, 19, 47, 10] use the simulated serving time of a request when routing it to a specific instance as the routing score. This is 7
1 2 3 4
req = receive()
implemented specifically for Qwen3-30B. Figure 16 measures the TTFT deviation when using two simulators to serve a Qwen3-30B model compared with using vLLM. We can see that a well-tuned simulator achieves much higher accuracy than an untuned one. With a more accurate simulator, the TTFT and TPOT tail latency improve by 75.6% and 79.7%, respectively. While it is possible to develop simulators for each model for high scheduling performance, doing so incurs nontrivial development complexity because the simulations highly depend on the model architecture—which is evolving rapidly with new modules (e.g., linear attention [33] and Engram [11]). Meanwhile, for the same model, the hyperparameters of the simulator need to be tuned according to the hardware characteristics, leading to further development efforts.
Latency-Based
TTFT = Simulatormodel.sim(req, BS, KV$, ...) sched_to = instances.select_min(TTFT) req.forward(sched_to)
Figure 14: The pseudocode of simulation-based method for combining KV$-awareness and load balancing in LLM scheduling.
based on the observation that the execution of LLM requests is quite structured, so it can be simulated accurately. Figure 14 shows the pseudocode of a typical simulation-based method [19]: after receiving a request, the router first estimates the TTFT of routing the request to each instance via a simulator (e.g., VIDUR [1]) (line 2), and then routes the request to the instance with the lowest estimated TTFT (lines 3–4). Note that simulation-based approaches typically estimate the TTFT instead of the end-to-end latency because the end-to-end latency depends on the number of output tokens, which is unpredictable. Simulation-based solutions can be viewed as a higherorder combination of indicators that achieve KV$-awareness and load-balancing. This is because the simulator must use the KV$ state and batch size of each instance as input fea= 0.25cm tures to accuratelytrim simulate the TTFT.YY.Ycm Here, we chose a XX.Xcm 0.25cm, simulation-based implementation similarclip to llm-d [19] but with a retrofitted simulator from VIDUR [1]—the state-ofthe-art LLM instance simulator. Our retrofitting consists of two parts: (1) we extend the simulator to consider KV$-aware execution by modeling the prefill phase with cache hits, and (2) we re-implement it in Rust and enable parallel simulation to scale the online simulation to multiple instances. Without KV$-awareness, the simulation-based solution cannot outperform other counterparts, similar to the observations we made in §4.2. Without Rust, the original Python-based implementation has considerable scheduling latency and is not suitable for online scheduling. We also have several optimizations to scale the simulator to hundreds of instances and we will leave the details to another paper as it is not the focus of this work. We studied a state-of-the-art method and found that it outperforms the linear-combination-based method in some traces, as also shown in Figure 14. Despite the improved performance, simulation-based methods still have two issues due to their complexity:
Cons #2. Still sub-optimal performance. Simulation-based methods still suffer from suboptimal performance, especially for TPOT. As shown in Figure 15, on the AgentTool trace, the TPOT tail latency is 71.1% slower than that of the best linear-combination-based method. We hypothesize that this is because some mispredictions of the simulator lead to load imbalance. For example, in Figure 16, we can see that even with a well-tuned simulator, there are still about 10% of requests with more than 20% prediction error. Such errors mainly come from two sources: request reordering at the vLLM API server, and inaccuracies in latency prediction.
5
Simple Multiplication May Be All You Need
The methodology (Figure 17). Our method is simple: we only need to multiply two carefully chosen indicators to compute the scheduling score, one for KV$-awareness and the other for load balancing, and then route the request to the instance with the minimal score. The basic idea is based on the observation that, if a linear combination of two indicators works, then multiplication can also work in a similar manner, with the benefit of avoiding the need for hyperparameter tuning, as shown in (a). The choice of the two indicators— P-token—the number of new prefill tokens if the request is routed to an instance considering KV$ hits, and BS—the batch size of the instance, is based on our careful analysis in §5.1. To see why routing to the instance with the minimal (PTokens × BS) score considers both objectives well, consider two instances i and j: if routing the request to instance i results in more KV$ hits than routing it to instance j, then instance i will have a lower P-token value unless there are many queued prefill requests in instance i (indicating work imbalance). Meanwhile, the BS captures the decode workload of each instance, so if instance i has a significantly larger batch size than instance j, the multiplication will likely favor instance j for load balancing. We should acknowledge that there do exist cases where
Cons #1. Development complexity due to per-model development and per-hardware tuning. The performance of simulation-based methods is dependent on the accuracy of the simulator, which is non-trivial to achieve in practice because we need to consider both the model architecture and the hardware characteristics. To quantify the impact of simulator accuracy on scheduling performance, Figure 15 presents the performance of using well-tuned vs. non-tuned simulators on four traces when serving a Qwen3-30B model. The poorly tuned simulator is one originally used for another model—Qwen2-7B, while a well-tuned simulator is the one 8
vllm-kv
168 178 183
300 150 0
Coder P50
160 80 0
TTFT (ms)
51
1000 500 0
AgentTool P50
500 250 0
1.6 0.8 0.0
10 5 0
179
1.2 1.3
API P90 156 188
1.2 0.6 0.0
1.3
0.54 0.71
1.7 1.4 1.4
1.6 0.8 0.0
4.3
27
24
0
16 8 0
14
30
27
API P50 15
13
Coder P50 27
25
61.4
0
16 8 0
34.6
Linear (Best tuned) ChatBot P90 50 25 0
54
40 20 0
33
40
35
55
80 40 0
30
80 40 0
74
50 25 0
49
API P90 38
Coder P90 35
32
0
AgentTool P50 12
17
13
AgentTool P90 200 100 0
216
28
ChatBot P99
50
20
15
AgentTool P99 60 30 15.0 0
26
15
Coder P99
978
11.3
1.6
30
API P99
289
Coder P90
807 833
1.6
TPOT (ms)
555
AgentTool P90
545
132
362 381
TPOT (ms)
63
TTFT (ms)
API P50 48
60 30 0
500 250 0
TPOT (ms)
92
85
83
TPOT (ms)
TTFT (ms)
ChatBot P50
TTFT (ms)
80 40 0
Simulation (Well tuned) Simulation (Poorly tuned) ChatBot P90 ChatBot P99 ChatBot P50
30
76
68
63
API P99 82
68
Coder P99 49
45
AgentTool P99 500 250 0
532
108
154
Figure 15: An analysis of how performance varies with different simulator accuracy across four traces using a Qwen3-30B model.
1.0
(a)
Well-tuned Poorly-tuned
CDF
0.5 0.0 0.0
0.2
0.4
0.6
Error ratio
0.8
0.99
Tail TTFT
1.0 (b)
Figure 16: A comparison of a well-tuned simulator vs. a non-tuned one on ChatBot Trace with Qwen3-30B model.
(a)
e.g., KV$ hit ratio
(c)
e.g., batch size
λ KV𝑖 + (1 − 𝜆) 𝐿𝑂𝐴𝐷𝑖 Scorei = λ KV𝑖 × (1 − 𝜆) 𝐿𝑂𝐴𝐷𝑖
(Linear) (Multiplication)
Scorei < Scorej => KV𝑖 × 𝐿𝑂𝐴𝐷𝑖 < KVj × 𝐿𝑂𝐴𝐷𝑗 1
req = receive()
2 3
# += len(prompt) - KV$.hitted(req.prompt) new_tokens = P_tokens.update(req.prompt) work = BS.update(1) # += 1
4 5
(b)
Figure 18: (a) A comparison of using new prefill tokens (P-Tkn) vs. 1-KV$ hit ratio (1-KVhit ) as the KV$-awareness indicator (A) in A × BS scheduling, (b) the KV$ hit ratio analysis, and (c) the queued prefill tokens analysis. The analysis is done on the Qwen330B model with ChatBot(Qwen) trace.
sched_to = instances .select_min(new_tokens * work) req.forward(sched_to) One per instance
5.1
The Choice of the Indicators
KV$-awareness indicator (P-token). Besides P-token, another natural choice for the KV$-awareness indicator is 0.25cm the 1-KV$ hit ratio,trim i.e., the=KV$ hit ratio ifYY.Ycm the request is 0.25cm, routed to an instance.XX.Xcm It is adopted by works likeclip Preble [36] and AIGW [4]. Note that the one minus is because a higher KV$ hit ratio should yield a lower score to align with the λ KV𝑖 × new 𝑖prefill tokens indicator. We do not consider TTFT as it multiplication may fail due to extremely skewed KV$ ac-(1 − 𝜆) 𝐿𝑂𝐴𝐷 requires the development of a simulator, which is not always cesses, i.e., a set of instances is always chosen due to high applicable. KV$ hits (low P-token), and the increased batch size (BS) trim = 0.25cm YY.Ycm on these instances XX.Xcm cannot compensate for the low P-token Our empirical analysis shows that using P-token yields bet0.25cm, clip values. Such cases—as we will analyze in §5.2—are rare in ter performance than using 1-KV$ hit ratio. From Figure 18 practice and can be detected (and thus mitigated) beforehand. (a), it can be observed that using P-token results in a 14.4% Figure 17: (a) An illustration of how multiplication avoids hyperparameters in combining two indicators as would be needed in linear combination, and (b) the pseudocode of our scheduling method.
9
Metho
5.2
(a)
0.99
Benign and Failure Cases Analysis of Multiplicationbased Scheduling Score
Overview. At a high level, as long as there is no load imbalance, i.e., one instance is overloaded while others are idle, routing requests to instances with high KV$ hit rates (i.e., low P-token) is always beneficial. Thus, the multiplication fails if a load imbalance is about to occur on a set of instances, but the increase in BS on these instances cannot offset the decrease in P-token due to high KV$ hit rates on the about-to-be overloaded instances, leading requests to be continuously routed to them and causing the imbalance. This can happen under extreme KV$ skewness: when a small set of requests repeatedly accesses the same prefix on a set of instances—which we term KV$ hotspots without considering others. We found such hotspots are rare in practice—at least not present in all our evaluated traces and, more importantly, as their patterns are clear, we can design a detector to catch them beforehand. Therefore, to analyze the failure cases of our multiplication method, we need to derive the condition under which KV$ hotspots occur and the increased batch size cannot offset the high KV$ hit rate given a workload pattern. For each workload, we first group requests by their KV$ prefixes and partition instances according to KV$ hit rates. Afterward, for each request class, we can specifically analyze the relationship between the workload pattern, the P-token indicator given the KV$ hit rate, and the batch size indicator.
0.99
(b)
Figure 19: (a) A comparison of using batch size (BS) vs. total tokens (#Tokens) as the load balance indicator (B) in P -Tokens ×B scheduling. (b) The relationship between batch size and total tokens profiled. The analysis is done on the Qwen3-30B model with ChatBot(Qwen) trace.
lower P50 TTFT and a 42.8% lower P95 TTFT compared to using 1-KV$ hit ratio. For a fair comparison, we fix the load-balancing indicator to BS in both cases. Note that due to space limitations, we only report the results for one workload here; however, the trend is consistent across all evaluated workloads. To understand the cause of this difference, Figure 18 further breaks down the KV$ hit ratios of different approaches in (b) trim = in0.25cm YY.Ycm and the load balancing status (c). We can see that the two XX.Xcm clip methods achieve similar KV$ 0.25cm, hit ratios, so both approaches are KV$-aware in a similar manner. The key difference lies in the fact that using P-token achieves better load balancing, as it additionally considers the queued prefill tokens in each instance. As a result, when making scheduling decisions, the router bypasses those instances containing many queued prefill requests, even if they have a high KV$ hit ratio.
Prelude: request grouping and instance partitioning. First, we partition all requests into a set of classes C, where each c ∈ C corresponds to a group of requests that share the same KV$ prefix. In practice, a class roughly matches an application or a user: their requests share the same system prompt and often a similar conversation history [39]. For a fixed class c, we consider an accumulation time window (t, t + window) and denote by x the fraction of all requests arriving at the cluster that belong to class c within this window; the remaining fraction is x̄ = 1 − x. For each class c, we partition the cluster into two sets of instances: M and M̄ . M contains instances whose cache currently holds the prefix of class c, i.e., with KV$ hits, while M̄ contains all other instances.
Load-balancing indicator (BS). Besides BS, another common choice is the total tokens (#Tokens) on each instance, as adopted by works like ai-Dynamo [27], AIGW [4]. The rationale is that the total computation cost of a request is proportional to the number of tokens in its context. However, we found using BS yields better performance, as shown in Figure 19 (a) due to two reasons. First, workloads can be categorized into prefill and decode loads, where the former is considered in our P-Tokens indicator. Thus, we only need an indicator for the decode workload, which is exactly what BS captures (note that we have also tried using decode batch size, and the results are similar since the BS is dominated by the decode requests). Moreover, BS is a better indicator for the (decode) work assigned to an instance because the decode time is more stable across different batch sizes, i.e., a larger batch size leads to a longer decode time, but a larger decode token may not necessarily lead to a longer decode time if there is small batch thanks to the KV$ [46]. This is illustrated in Figure 19 (b), in which we profile the relationship of the batch size and total tokens during serving a ChatBot(Qwen) workload with Qwen3-30B.
Impact of a request class on batch size. Let QPS be the total query rate of the cluster, and let t be the time when the suspected class-c requests arrive that may lead to imbalance. We denote the average batch size per instance in a balanced state prior to t as BS0 . We also denote the expected batch sizes of instances in M and M̄ by BSt and BS t during the period (t, t + window). We assume in the extreme case where all class-c requests are routed to M due to high KV$ hits, because otherwise the hotspot is mitigated by routing some requests to M . As a result, we can establish an approximate expression for the ratio between a potentially overloaded instance’s batch size and a non-overloaded instance’s batch size as follows: 10
Ratio Ratio
10
M/M
ChatBot
does not hold, i.e.,
x/x API
00 5 10 Coder
10
15
5 0 5 10 10 0 ToolAgent
00
10
15
00
5
Time (min)
5
10
Time (min)
x |M | > x̄ |M |
15 15
, then there is a potential for KV$ hotspots to cause load imbalance that may break our multiplication method. This gives a clear indication of the failure cases detector based purely on the workload pattern and KV$ states, so we can develop a detector before we make a scheduling decision to catch potential failure cases. Specifically, for each request class, we profile the two terms |M | x x̄ and |M | in real time, and if we observe that Equation 2 does not hold, we raise an alarm and filter out the suspected instances (M ) from the routing targets. To avoid the overhead of tracking too many request classes, we only track the requests with the highest KV$ hit rates. One problem of the single-phase detector described above is that even if Equation 2 does not hold, it may still be beneficial to route requests to the suspected instances with high KV$ hit rates, as long as we do not route too many requests to the hotspots. Therefore, we further augment the detector with a second phase by delaying the filtering until a consecutive number of requests are routed to hotspots, as consecutive routing decisions may imply that the increase in the batch size of the suspected instances cannot offset the high KV$ hit rates.
Figure 20: Empirical observations of the factors in the multiplicative | score across different traces. If x̄x ≤ |M , no KV$ hotspot can cause |M | load imbalance, so our multiplication method can effectively balance the load with KV$-awareness.
BSt BS0 + (x · QPS) /|M | · t = . BS t BS0 + (x̄ · QPS) /|M | · t
(1)
The main term (x · QPS) /|M | · t corresponds to the number of requests of class c routed to the instances that cache its prefix, while (x̄ · QPS) /|M | · t is the routing of all other requests to the remaining instances. Analysis: the benign cases, and are they common? As long as the batch size of the suspected hotspot instances is not larger than the others, we are sure that it is beneficial to route requests to these instances, because such a routing decision can improve KV$ hit rates without causing load imbalance. Since our multiplication faithfully does so, these are benign cases for our method. The remaining question is whether such cases are common in practice. Fortunately, based on our established workload–batch size relationship in Equation 1, we can empirically analyze their prevalence by tracking the | two terms xx̄ and |M across traces, which samples the request |M | classes within a time window (1 minute) with the highest KV$ hits. x |M | ≤ x̄ |M |
P-tokenm × BSm ≤ P-tokenm̄ × BSm̄
Specifically, after the first phase raises an alarm, we further track the new prefill tokens of the requests in this class, and if we observe that more than 2 × M consecutive requests in the class have a smaller multiplicative score (Equation 4) on a suspected hotspot instance (m) than on the rest of the instances (m̄), then we raise a second alarm that filters out the suspected instances from the routing targets.
6
(2)
End-to-end Evaluation
We conclude our study of efficient LLM scheduling by comparing LM ETRIC with the multiplication method described in §5 and state-of-the-art schedulers on end-to-end LLM serving performance.
Figure 20 shows that all traces—representative of LLM serving and studied in this work—are benign to our method, because the expected batch size of the suspected hotspot instances is not larger than that of the others. This can be interpreted as follows. Based on Figure 20, we have the following observation summarized in Equation 2 for all traces. x x̄ ≤ |M | |M |
(4)
Baselines. We compare LM ETRIC against both open-source schedulers and the current production scheduler used in BAILIAN. As some implementations suffer from poor performance due to router implementation issues, e.g., vLLM exhibits low processing throughput with its Python-based router [38], we re-implement their policies within our highly optimized Rust router framework described in §3. For an apples-to-apples comparison, we compare policies under our framework, and we have carefully verified that our re-implementations are no slower than their original implementations. The detailed descriptions of the baselines are as follows:
(3)
By rearranging the equation, we obtain Equation 3. Substituting into Equation 1, we get the expected batch size of the KV$ hotspot instances is smaller than the others. Analysis: the failure cases, and our two-phase detector. Based on our previous analysis, we can see that if Equation 2 11
Tail TTFT
Tail TPOT
0.99
0.99
TTFT and TPOT CDFs of LM ETRIC and other baselines on four traces. All experiments are conducted on a 16-GPU testbed with 16 instances, and the trace is scaled to half of the maximum load that the testbed can handle. Due to space constraints, we report results for a representative subset: the Qwen3 MoE model on ChatBot, Coder, and Agent workloads, and the Qwen2 model on the API workload. We observe consistent performance trends across all model–trace combinations. LM ETRIC outperforms all baselines across all traces. On the ChatBot workload, it reduces the mean TTFT by 92% and the mean TPOT by 24% compared to vLLM, and it reduces the P99 TPOT by 13% compared to llm-d—the second best policy—with a similar TTFT. The improved performance mainly comes from being KV$-aware without sacrificing load balancing. To delve into the behavior of LM ETRIC, Figure 23 plots the KV$ hit ratio for different systems on the ChatBot workload. We can see that LM ETRIC consistently achieves a KV$ hit ratio comparable to other KV$-aware policies, and its ratio is significantly higher than that of the KV$-unaware policy (vLLM). Meanwhile, Figure 24 further analyzes the imbalance following the analysis conducted in §4.3. For ease of presentation, we only compare LM ETRIC with llm-d—the second-best approach on the ChatBot trace. We can see that LM ETRIC achieves a better-balanced load compared to llm-d.
(a) Qwen3-30B on ChatBot (Qwen) workload.
Tail TTFT
Tail TPOT
0.99
0.99 Running batch size
(b) Qwen2-7B on Agent (Qwen) workload.
Tail TTFT 0.99
Tail TPOT 0.99 Running batch size
(c) Qwen3-30B on Coder workload.
Tail TTFT
Tail TPOT
0.99
0.99 Running batch size
(d) Qwen3-30B on Agent (Kimi) workload. Figure 21: End-to-end TTFT and TPOT CDFs of LM ETRIC and baselines on four workloads.
Performance under different request rates. Figure 22 further shows how the LM ETRIC performs under different request arrival rates. The results are largely consistent with • BAILIAN is the production scheduler used in BAIL those under a fixed request rate setting: LM ETRIC outperIAN ’s LLM serving system. It adopts a similar linearforms other baselines across different traces and request rates, Running combination-based approach as the one shown batch size in Figure 6 except for the ToolAgent trace, where LM ETRIC exhibits a (b). We have carefullytrim tuned its hyperparameters each = 0.25cmforYY.Ycm slightly higher (10%) mean TTFT than llm-d but achieves workload to achieve the best performance. XX.Xcm 0.25cm, clip a 30% lower TPOT. This may be because a simulator-based approach can better estimate the prefill workload than our sim• vLLM [37] is a widely used LLM serving system that ple P-token indicator. Nevertheless, LM ETRIC still achieves adopts a load-balance only design described in Figure 6 the lowest TPOT without relying on a complex simulator, (a). as it considers both KV$ management and (decode) load • Dynamo [27] is a popular serving framework released balancing. The performance gap between different baselines trim = 0.25cm YY.Ycm by NVIDIA. It also adopts a linear-combination-based widens as the request rate increases, because under high load, 0.25cm, clip a more balanced and KV$-aware scheduling strategy can betapproach but with XX.Xcm a different choice of indicators than BAILIAN’s. The two indicators chosen are the ter improve the overall system throughput, leading to faster number of prefill tokens (the same as our P-token) for consumption of queued requests under high load. KV$-awareness and the total tokens in the instance for load-balancing awareness. The router routes requests to 0.25cm YY.Ycm7 Related Work the instance with thetrim minimal = regulated and weighted sum of the two indicators. Similar to BAILIAN, we also XX.Xcm 0.25cm, clip LLM requests global scheduling. LM ETRIC continues tune its hyperparameters for each workload for optimal the line of research on scheduling LLM requests in a clusperformance. ter [23, 21, 36, 32, 47, 19]. To the best of our knowledge, all these methods attempt to achieve both KV$-awareness • llm-d [19] adopts a latency-based scheduling policy: It and load-balancing through three approaches in combining estimates the TTFT and routes requests to the instance = 0.25cmapproach YY.Ycmdifferent indicators for each objective, as we have extensively with the lowest TTFTtrim using the simulator-based in §4. LM ETRIC builds on these works to reuse described in §4.6. XX.Xcm 0.25cm, clip discussed their indicators but further proposes a new and simple multiOverall performance. Figure 21 shows the end-to-end plication combinator, and our extensive evaluations confirm 12
LMetric Chatbot (Qwen) Time
20secs 15secs 10secs 5secs 0ms
TTFT Mean
.5 40.0 42.5 35.0 37TTFT Mean
120secs 90secs 60secs 30secs 0ms
vLLM-v1
Dynamo
llm-d
TTFT P99
60ms 45ms 30ms 15ms 0ms
TPOT Mean
.5 40.0 42.5 35.0 37TTFT P99
ToolAgent (Kimi) Time
Agent (Qwen) Time
Coder Time
30secs 120secs 20secs 80secs 10secs 4secs 500ms 2secs 250ms 0ms 0ms 12.0 13.5 15.0 16.5 12.0 13.5 15.0 16.5 TTFT Mean TTFT P99 2secs 240ms 1.5secs 160ms 1secs 80ms 500ms 0ms 0ms 135 150 165 180 135 150 165 180 TTFT Mean TTFT P99 32secs 2secs 24secs 1.5secs 16secs 1secs 8secs 500ms 0ms 2 0ms 2 7. 8.0 8.8 9.6 10.4 7. 8.0 8.8 9.6 10.4 Rate (reqs/sec) Rate (reqs/sec)
45ms
35.0 37.5 40.0 42.5 TPOT Mean
30ms 15ms 0ms 12.0 13.5 15.0 16.5 TPOT Mean 100ms 75ms 50ms 25ms 0ms 135 150 165 180 TPOT Mean 32ms 24ms 16ms 8ms 0ms 2 7. 8.0 8.8 9.6 10.4 Rate (reqs/sec)
Bailian 100ms 75ms 50ms 25ms 0ms
TPOT P99
35.0 37.5 40.0 42.5 TPOT P99 100ms 75ms 50ms 25ms 0ms 12.0 13.5 15.0 16.5 TPOT P99 400ms 300ms 200ms 100ms 0ms 135 150 165 180 TPOT P99 320ms 240ms 160ms 80ms 0ms 2 7. 8.0 8.8 9.6 10.4 Rate (reqs/sec)
Cache Hit Ratio
Figure 22: End-to-end performance under different request rates. Except the second row that uses a Qwen2-7B model, all other rows use a Qwen3-30B model.
LMetric vLLM-v1
1.0
Dynamo
llm-d
Bailian
LLM requests scheduling within an instance. Besides global scheduling across instances, a line of work focuses on local scheduling optimizations within an instance. SarathiServe [2] introduces chunked prefill, which splits long prefill requests into smaller chunks to reduce stall time for co-located decode requests. VTC [35] adopts a token-based admission control mechanism to achieve fairness. FairBatching [24] uses a linear-time analytical model to prioritize prefill versus decode tokens and dynamically form batches. These works are orthogonal to our global scheduling, and a good global scheduler can further enhance local scheduling effectiveness, e.g., by reducing the frequency of overloading that is nontrivial to handle with local scheduling alone.
0.5 0.0 0
50
100 150 200 250 300 350 400
Time (seconds)
Prefill time |Ins.1 - Ins.2| (sec/10sec)
Figure 23: KVCache hit ratio comparison of policies of the Qwen330B model on the ChatBot (Qwen) workload.
llm-d
5.0
LMetric
2.5 0.00
100
200
Time (seconds)
300
400 Optimizing LLM serving. Besides scheduling, a variety of techniques have been proposed to optimize LLM serving performance. These include methods to improve KV$ hit rates [32, 39], to provide elasticity for model serving [44, 42], and to optimize GPU execution efficiency [23, 22], to name a few. To the best of our knowledge, all these techniques coexist with scheduling optimizations, so they can be combined with LM ETRIC to further improve overall performance.
Figure 24: A profile of the workload imbalance between two instances under LM ETRIC and llm-d on serving a ChatBot (Qwen) workload with the Qwen3-30B model. The reported metric is the absolute served prefill time in each 10-second window between the two instances (Inst.).
the effectiveness of our approach. 13
8
Conclusion
[12] D ELIMITROU , C., AND KOZYRAKIS , C. Quasar: resourceefficient and qos-aware cluster management. In Architectural Support for Programming Languages and Operating Systems, ASPLOS 2014, Salt Lake City, UT, USA, March 1-5, 2014 (2014), R. Balasubramonian, A. Davis, and S. V. Adve, Eds., ACM, pp. 127–144.
We contribute the first multiplication-based combinator to achieve high-quality LLM request scheduling by achieving both KV$-awareness and load balancing in a hyperparameterfree manner. Evaluations on real-world workloads covering chatbots, API calls, and coding agents confirm the benefits of our approach over state-of-the-art methods including vLLM [37], ai-Dynamo [27], llm-d [19] and a production scheduler used in BAILIAN.
[13] FlashInfer: Kernel Library for LLM Serving. https:// github.com/flashinfer-ai/flashinfer, 2025. [14] G AO , B., H E , Z., S HARMA , P., K ANG , Q., J EVDJIC , D., D ENG , J., YANG , X., Y U , Z., AND Z UO , P. Cost-Efficient large language model serving for multi-turn conversations with CachedAttention. In 2024 USENIX Annual Technical Conference (USENIX ATC 24) (Santa Clara, CA, July 2024), USENIX Association, pp. 111–126.
References [1] AGRAWAL , A., K EDIA , N., M OHAN , J., PANWAR , A., K WA TRA , N., G ULAVANI , B. S., R AMJEE , R., AND T UMANOV, A. VIDUR: A large-scale simulation framework for LLM inference. In Proceedings of the Seventh Annual Conference on Machine Learning and Systems, MLSys 2024, Santa Clara, CA, USA, May 13-16, 2024 (2024), P. B. Gibbons, G. Pekhimenko, and C. D. Sa, Eds., mlsys.org.
[15] GIGASPACES. Amazon found every 100ms of latency cost them 1% in sales. https://www.gigaspaces. com/blog/amazon-found-every-100ms-oflatency-cost-them-1-in-sales, 2024. [16] G IT H UB. Accelerate your development speed with copilot. https://copilot.github.com, 2024.
[2] AGRAWAL , A., K EDIA , N., PANWAR , A., M OHAN , J., K WA TRA , N., G ULAVANI , B., T UMANOV, A., AND R AMJEE , R. Taming Throughput-Latency tradeoff in LLM inference with Sarathi-Serve. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24) (Santa Clara, CA, July 2024), USENIX Association, pp. 117–134.
[17] G OG , I., S CHWARZKOPF, M., G LEAVE , A., WATSON , R. N. M., AND H AND , S. Firmament: Fast, centralized cluster scheduling at scale. In 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2-4, 2016 (2016), K. Keeton and T. Roscoe, Eds., USENIX Association, pp. 99–115.
[3] Aibrix. https://github.com/vllm-project/ aibrix, 2025.
[18] G OOGLE. Gemini api. https://ai.google.dev/api, 2025.
[4] Aigw. https://github.com/aigw-project/aigw, 2025.
[19] G OOGLE. llm-d. https://github.com/llm-d/llmd, 2025.
[5] A LI , A., P INCIROLI , R., YAN , F., AND S MIRNI , E. Optimizing inference serving on serverless platforms. Proc. VLDB Endow. 15, 10 (2022), 2071–2084.
[20] G UJARATI , A., K ARIMI , R., A LZAYAT, S., H AO , W., K AUF MANN , A., V IGFUSSON , Y., AND M ACE , J. Serving dnns like clockwork: Performance predictability from the bottom up. In 14th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2020, Virtual Event, November 4-6, 2020 (2020), USENIX Association, pp. 443–462.
[6] A NTHROPIC. Claude api. https://www.anthropic. com/api, 2025. [7] A RAPAKIS , I., BAI , X., AND C AMBAZOGLU , B. B. Impact of response latency on user behavior in web search. In The 37th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’14, Gold Coast , QLD, Australia - July 06 - 11, 2014 (2014), S. Geva, A. Trotman, P. Bruza, C. L. A. Clarke, and K. Järvelin, Eds., ACM, pp. 103–112.
[21] H U , X., Z ENG , T., Y UAN , X., S ONG , L., Z HANG , G., AND H E , B. Bestserve: Serving strategies with optimal goodput in collocation and disaggregation architectures. CoRR abs/2506.05871 (2025). [22] K AMATH , A. K., P RABHU , R., M OHAN , J., P ETER , S., R AM JEE , R., AND PANWAR , A. Pod-attention: Unlocking full prefill-decode overlap for faster LLM inference. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2, ASPLOS 2025, Rotterdam, Netherlands, 30 March 2025 - 3 April 2025 (2025), L. Eeckhout, G. Smaragdakis, K. Liang, A. Sampson, M. A. Kim, and C. J. Rossbach, Eds., ACM, pp. 897–912.
[8] A ZURE. Azure llm inference traces. https://github. com/Azure/AzurePublicDataset/blob/master/ AzureLLMInferenceDataset2024.md, 2024. [9] Qwen-bailian anonymous dataset. https://github. com/alibaba-edu/qwen-bailian-usagetracesanon, 2025. [10] C HEN , S., J IA , Z., K HAN , S., K RISHNAMURTHY, A., AND G IBBONS , P. B. Slos-serve: Optimized serving of multi-slo llms. CoRR abs/2504.08784 (2025).
[23] K WON , W., L I , Z., Z HUANG , S., S HENG , Y., Z HENG , L., Y U , C. H., G ONZALEZ , J., Z HANG , H., AND S TOICA , I. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, SOSP 2023, Koblenz, Germany, October 23-26, 2023 (2023), J. Flinn, M. I. Seltzer, P. Druschel, A. Kaufmann, and J. Mace, Eds., ACM, pp. 611–626.
[11] C HENG , X., Z ENG , W., DAI , D., C HEN , Q., WANG , B., X IE , Z., H UANG , K., Y U , X., H AO , Z., L I , Y., Z HANG , H., Z HANG , H., Z HAO , D., AND L IANG , W. Conditional memory via scalable lookup: A new axis of sparsity for large language models, 2026.
14
[24] LYU , H., L IU , B., W U , M., AND C HEN , H. Fairbatching: Fairness-aware batch formation for LLM inference. CoRR abs/2510.14392 (2025).
[38] [bugfix]: Avoid unnecessary coordination for non-moe data parallel. https://github.com/vllm-project/vllm/ issues/24461, 2026.
[25] M IAO , X., S HI , C., D UAN , J., X I , X., L IN , D., C UI , B., AND J IA , Z. Spotserve: Serving generative large language models on preemptible instances. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2, ASPLOS 2024, La Jolla, CA, USA, 27 April 2024- 1 May 2024 (2024), R. Gupta, N. B. Abu-Ghazaleh, M. Musuvathi, and D. Tsafrir, Eds., ACM, pp. 1112–1127.
[39] WANG , J., H AN , J., W EI , X., S HEN , S., Z HANG , D., FANG , C., C HEN , R., Y U , W., AND C HEN , H. Kvcache cache in the wild: characterizing and optimizing kvcache cache at a large cloud provider. In Proceedings of the 2025 USENIX Conference on Usenix Annual Technical Conference (USA, 2025), USENIX ATC ’25, USENIX Association. [40] WANG , J., H AN , J., W EI , X., S HEN , S., Z HANG , D., FANG , C., C HEN , R., Y U , W., AND C HEN , H. Kvcache cache in the wild: Characterizing and optimizing kvcache cache at a large cloud provider. In 2025 USENIX Annual Technical Conference (USENIX ATC 25) (July 2025), USENIX Association.
[26] Mooncake trace. https://github.com/kvcacheai/Mooncake/blob/main/FAST25-release/ traces/toolagent_trace.jsonl, 2025. [27] NVIDIA. ai-dynamo. dynamo/dynamo, 2025.
https://github.com/ai-
[41] WANG , Y., C HEN , Y., L I , Z., K ANG , X., FANG , Y., Z HOU , Y., Z HENG , Y., TANG , Z., H E , X., G UO , R., ET AL . Burstgpt: A real-world workload dataset to optimize llm serving systems. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2 (2025), pp. 5831–5841.
[28] O PENAI. Openai developer platform. https:// platform.openai.com/docs/overview. [29] O PENAI. Chatgpt. https://chatgpt.com, 2025. [30] PATEL , P., C HOUKSE , E., Z HANG , C., S HAH , A., G OIRI , Í., M ALEKI , S., AND B IANCHINI , R. Splitwise: Efficient generative LLM inference using phase splitting. In 51st ACM/IEEE Annual International Symposium on Computer Architecture, ISCA 2024, Buenos Aires, Argentina, June 29 - July 3, 2024 (2024), IEEE, pp. 118–132.
[42] X IANG , Y., L I , X., Q IAN , K., YANG , Y., Z HU , D., Y U , W., Z HAI , E., L IU , X., J IN , X., AND Z HOU , J. Aegaeon: Effective GPU pooling for concurrent LLM serving on the market. In Proceedings of the ACM SIGOPS 31st Symposium on Operating Systems Principles, SOSP 2025, Lotte Hotel World, Seoul, Republic of Korea, October 13-16, 2025 (2025), Y. Won, Y. Kwon, D. Yuan, and R. Isaacs, Eds., ACM, pp. 1030– 1045.
[31] Pollaczek–khinchine formula. https://en.wikipedia. org/wiki/PollaczekâĂŞKhinchine_formula# cite_note-2, 2025.
[43] X IANG , Y., L I , X., Q IAN , K., Y U , W., Z HAI , E., AND J IN , X. Servegen: Workload characterization and generation of large language model serving in production. CoRR abs/2505.09999 (2025).
[32] Q IN , R., L I , Z., H E , W., C UI , J., R EN , F., Z HANG , M., W U , Y., Z HENG , W., AND X U , X. Mooncake: Trading more storage for less computation — a KVCache-centric architecture for serving LLM chatbot. In 23rd USENIX Conference on File and Storage Technologies (FAST 25) (Santa Clara, CA, Feb. 2025), USENIX Association, pp. 155–170.
[44] Z HANG , D., WANG , H., L IU , Y., W EI , X., S HAN , Y., C HEN , R., AND C HEN , H. Blitzscale: Fast and live large model autoscaling with O(1) host caching. In 19th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2025, Boston, MA, USA, July 7-9, 2025 (2025), L. Zhou and Y. Zhou, Eds., USENIX Association, pp. 275–293.
[33] Qwen3-next. https://qwen.ai/blog?id= 4074cca80393150c248e508aa62983f9cb7d27cd& from=research.latest-advancements-list, 2026.
[45] Z HANG , X., T UNE , E., H AGMANN , R., J NAGAL , R., G OKHALE , V., AND W ILKES , J. Cpi2 : CPU performance isolation for shared compute clusters. In Eighth Eurosys Conference 2013, EuroSys ’13, Prague, Czech Republic, April 14-17, 2013 (2013), Z. Hanzálek, H. Härtig, M. Castro, and M. F. Kaashoek, Eds., ACM, pp. 379–391.
[34] S AJAL , S. M., Z HU , T., U RGAONKAR , B., AND S EN , S. Traceupscaler: Upscaling traces to evaluate systems at high load. In Proceedings of the Nineteenth European Conference on Computer Systems, EuroSys 2024, Athens, Greece, April 22-25, 2024 (2024), ACM, pp. 942–961. [35] S HENG , Y., C AO , S., L I , D., Z HU , B., L I , Z., Z HUO , D., G ONZALEZ , J. E., AND S TOICA , I. Fairness in serving large language models. In 18th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2024, Santa Clara, CA, USA, July 10-12, 2024 (2024), A. Gavrilovska and D. B. Terry, Eds., USENIX Association, pp. 965–988.
[46] Z HONG , Y., L IU , S., C HEN , J., H U , J., Z HU , Y., L IU , X., J IN , X., AND Z HANG , H. Distserve: Disaggregating prefill and decoding for goodput-optimized large language model serving. In 18th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2024, Santa Clara, CA, USA, July 10-12, 2024 (2024), A. Gavrilovska and D. B. Terry, Eds., USENIX Association, pp. 193–210.
[36] S RIVATSA , V., H E , Z., A BHYANKAR , R., L I , D., AND Z HANG , Y. Preble: Efficient distributed prompt scheduling for LLM serving. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025 (2025), OpenReview.net.
[47] Z HU , K., S HI , H., X U , L., S HAN , J., K RISHNAMURTHY, A., K ASIKCI , B., AND X IE , L. Polyserve: Efficient multi-slo serving at scale. CoRR abs/2507.17769 (2025).
[37] vllm v0.12.0 release. https://github.com/vllmproject/vllm/releases/tag/v0.12.0, 2025.
15