Efficient LLM Scheduling by Learning to Rank
Authors: Yichao Fu
Siqi Zhu
Runlong Su
Aurick Qiao
Ion Stoica
Hao Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: Large Language Models
Primary area: infrastructure

Abstract: In Large Language Model (LLM) inference, the output length of an LLM request is typically regarded as not known a priori. Consequently, most LLM serving systems employ a simple First-come-first-serve (FCFS) scheduling strategy, leading to Head-Of-Line (HOL) blocking and reduced throughput and service quality. 
In this paper, we reexamine this assumption -- we show that, although predicting the exact generation length of each request is infeasible, it is possible to predict the relative ranks of output lengths in a batch of requests, using learning to rank. The ranking information offers valuable guidance for scheduling requests. Building on this insight, we develop a novel scheduler for LLM inference and serving that can approximate the shortest-job-first (SJF) schedule better than existing approaches. We integrate this scheduler with the state-of-the-art LLM serving system and show significant performance improvement in several important applications: 2.8x lower latency in chatbot serving and 6.5x higher throughput in synthetic data generation. Our code is available at https://github.com/hao-ai-lab/vllm-ltr.git

Efficient LLM Scheduling by Learning to Rank
Yichao Fu'
Siqi Zhu?
Runlong Su
Aurick Qiao
Ion Stoica" UC Berkeley
Hao Zhang'
UCCD
"Tsinghua University
Snnowflake
Abstract
In Large Language Model (LLM) inference, the output length of an LLM request is typically regarded as not known priori. Consequently, most LLM serving systems employ a simple Head-Of-Line (HOL) blocking and reduced throughput and service quality. In this paper, we reexamine this assumption we show that, although predicting the exact generation length of each request infeasible, it is possible predict the relative ranks of output lengths in a batch of requests, using learning to rank. The ranking information offers valuable guidance for scheduling requests. Building on this insight, we develop novel scheduler for LLM inference and serving that can approximate the shortest-job-fits (SJF) schedule better than existing approaches. We integrate this scheduler with the state-of-the-att LLM serving system and show significant performance improvement several important applications: 2.8x lower latency in chatbot serving and 6.5x higher throughput in synthetic data generation. Our code available at at/https: thub. com hom/hao-a ai waalllllllli wwwlmlmmm........ .iittiit
(FCFS) scheduling strategy, leading to
1
Introduction
Large language models (LLMMs) are increasingly becoming the backbone of many today's Internet services and applications that serve millions of users [] Due to the surge in demand, efficient scheduling for LLM serving is crucial ensure high-quality service amidst numerous concurrent users competing for computing resources. For popular interactive applications such as chatbots, this means minimizing the latency that each user perceives while maximizing the overall system throughput to possible.
accommodate many
Under high load, LLM services that implement a ceae--oom-fiissssereeeeee (FCFS) scheduling strategy inevitably face significant Head-Of- Liee (HOL) blocking, as many requests must wait for others to execute. Figure [ Jillustrates typical example of how long request can block shorter ones in FCFS scheduling, leading to significant HOL blocking. In such scenarios, it is well-established that the shortest-job-fin (SJF) and reeaiiit-remaining.. -tmme-fiistttt (SRTF) scheduling algorithms minimize the average latency experienced across all requests. However, SJF/SRTF are seldom implemented in LLM services because they require requests to be ordered by their remaining generation lengths, which is traditionally assumed to be difficult or impossible to know ahead of time in existing systems (2]
In this paper, we contend that, although accurately knowing the generation length of requests may be difficult, it is actually not needed. Rather, just knowing the relative ordering between request lengths is sufficient for SJF/SRTF scheduling. To this end, we propose use the Kendall rank correlation coefficient (Kendall's 's Tau) [4] to measure the similarity between a predicted schedule and the SJF/SRTF schedule based on groundtruth generation lengths (i.e. oracle). We demonstrate that schedules with higher similarities (measured by Kendal's 's Tau) to the oracle generally translate to lower latencies real-world performance (Figure.)
Based on this insight, we propose to optimize the request scheduling in LLM serving via learning rank. We show that small auxiliary model (e.g., OPT-125M (5)) be trained to accurately rank
Hao Zhang is the corresponding author
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

Requests: RO 10 tokens
RR1 2 tokens
R2 1 token
System throughput: token/s
FCFS:
RO
R1
R2
Latency: RO 1s/tok| R1 6s/tok R2 13s/tok
SRTF:
R2
RO
Time
Latency: RO 1.3s /tok R1 1.5s/tok| | R2 1s/tok
Figure 1: A long request can block short requests and introduce severe HOL blocking and high latency, We assume there is no prefill time, and the system takes I second to generate token. With a First-come- first-serve (FCFS) schedule, the long request RO, which arrives first and takes 10 seconds to generate 10 tokens, will block subsequent shorter requesss R/ and R2 for 10 seconds. Hence the latencies of RO, RI, and R2 are with an average latency of (1 (1+6+13)/3 token. By contrast, prioritizing shortest requests yields an average latency of (1.3+1.++1/33 1.27 s token a 5.3x reduction in average latency.
= 13 s/ token, respectively, perceived by users,
LLM requests by their generation lengths, prior to execution, virtually no cost. For both offline batch generation and online latency-sensitive tasks, by scheduling requests on-the-fly based on the predicted rankings, we can approximate the SRTF/SJF schedule, hence reduce average latency and improve throughput, respectively.
Compared existing work which attempts to directly predict the generation lengths of LLM responses 66, 77. we show that our Barming-to-rame approach is both more robust in approximating SRTF/SJF, hence translating to lower latency and higher throughput, but also simpler, which can be easily integrated into production serving systems (i.e., 500 LoC in vLLM).
Our contributions summarized as follows:
We show that knowing the relative orderings of generation lengths provides valuable guidance for optimizing the scheduling of LLM serving.
We apply Kendall's 's Tau effective measure of the similarity between LLM schedule and the ideal SJF/SRTF schedule, and show a higher similiary indicated by Kendall's Tau usually translates to lower latency and high throughput in practice.
We employ learning-to-runk ( to optimize the schedule and show that our method is simple and enables on-the-fly scheduling at a per-iteration basis with negligible overhead.
Our method, when integrated with state-of-the serving system, significantly improves the performance on important LLM serving tasks, reducing the p90 latency of chatbot serving by 2.8x and increasing the throughput of batch synthetic data generation by 6.5x.
2
Related Work
LLM Serving Systems. Orca [3] introduces iteration-level scheduling and vLLM [2] applies PagedAttention, which are two key techniques for LLM serving. However, they both apply the FCFS schedule and are prone to severe HOL blocking. Scheduling for LLM serving is a relatively less
explored topic. Although many LLM serving optimizations (9] I0] 12 [3] have been developed recently, all these works typically assume the output length of an LLM request cannot be known before execution. FastServe [14] applies skip-join MLFQ in LLM serving. It sets up the priority of requests according to their generated length so far. Andes [1S]] introduces a novel quality of experience (QoE) metric for online text services, which measures human satisfaction during the whole token delivery. employs an online preemptive scheduling method that determines which requests to execute based on scheduling objectives (c.g., average QoE) for the upcoming timeframe. Our method differs from these by predicting generation length rankings to achieve lower latency.
Scheduling in General. Scheduling is critical in computer systems. First-come- ciirt-com--irst-seveee (FCFS) schedules requests according to their arrival time. Shortest-job-iit first (SJJ) and its preemptive variant, sireiinngttm---iie time-first (SRTF), prioritize jobs with the shortest time to finish, which provably yield the lowest average latency, but may suffer from starvation problems. We discuss how to prevent www.leeell--ebba------e
starvation in $4.3
(MLFQ) maintains multiple priority queues to balance fairness and latency, but introduces substantial complexity batch and interactive L.LM workloads. Our work addresses this complexity by leveraging simpler, prediction baaded scheduling strategy.

---

Latency (s/token)
1.2
Norn Waiting Time (4tollon)
0.5
1.0
0.5X
0.2
0.6
0.4
rcrs
OURS
SRTT
Kendall's Tau
(b)
Figure (a): HOL blocking was evaluated by comparing FCFS and SRTF scheduling policies across IK requests, (b): Analysis revealed that higher Kendall's Tau correlation coefficients were associated with reduced latency. This finding was validated using the ShareGPT dataset with the Llama-3-88 model.
work several recent works that predict the (exact) generation length of L.MSs in order to enhance resource utilization (e.g.. memory). Perception Only (PO) 77) methods let LLMs output the generation length via prompting. S3 (6]. TetriServe [II and DynamoLLM [16] use a predictor model (i.c, DistilBert [17] and OPT (5]) to predict generation length. These methods formulate the length prediction classification problem, whose success hinges on high predictive accuracy. Magnus [8] utilizes language-agnosti BERT sentence embedding, a compression component, and random forest regressor to predict generation length. Other concurrent works [19 20 both propose regression based method for length prediction, fine-tuning BERT model on the Lmsys-Chin Chat- 1M dataset with an L1 regression loss predict the exact generation length. They tested models ranging from 300M to 3B and applied various batching policies, including no batching, dynamic batching, and continuous batching, significantly improving latency and throughput under these settings. Additionally, it supports multi-round I. LLM conversations. In contrast, our proposed method is built on vLLM with paged attention and uses ranking loss to optimize the predictor model. We designed preemptive scheduling method with starvation prevention to optimize the end-to-end performance of real-world LLM serving systems.
LLM Generation Length Prediction. Closest
3 Background
In this section, we introduce several background concepts in learning to rank, which are essential for understanding methodology.
Kendall Rank Correlation Coefficient. Kendall's Tau coefficient 4 specifically the Tau-b variant we use, measures the correlation between two rankings. Its value ranges from -1 to 1, where 1 indicates perfect agreement between two rankings, - indicates complete disagreement (reversed rankings), and () indicates no correlation. The formulation of Kendall's Tau is given as follows:
N
V (No-NN)((N,
where N. and Na the number of concordant and discordant pairs, respectively, in the rankings.
No = (0=nnn nnn-nnnnnn 1),2, where n is the total number of items. N₁ and N2 consider tied values in each ranking: Ni (t, 1)/2 and N₂ N2=E, (u,- 1))/,, where t; is the number of tied values in the tth group of ties for the first ranking and u, is the number of tied values in the jth group of ties for the second ranking (4) It's important to note that tied pairs are considered neither concordant nor discordant in this calculation.
Learning to Rank. Learning to rank g is a machine learning approach applied to supervised ranking data. It is widely used in recommendation systems [21], search engine [ and other
research areas [3] Learning to rank typically takes one of three forms: pointwise, pairwise, and
listwise. Pointwise turns the ranking problem into regression 24 classification [55 26 or ordinal
regression 277 Pairwise 28
32 (k method learns the relative ranking for each pair of
items. Listwise 34
35
36
37 38
Icars the ranking of lists of samples in a dataset.

---

ListMLE. ListMLE [7 is a listwise ranking loss used in this paper. It minimizes the likelihood
function defined (gg(r),)) -oogP(y) (vyl w>:g)) where
exp(s(=v(s)) P(y x:g) = -II kk= exp exp(g(<g(x))
Here, P(y (::)) represents the probability of the permutation y given the input and the scoring function Fy(1) denotes the element in rr that corresponds to the i-th position in the permutation y. The idea is to maximize the likelihood of the corecit y by using the scoring function g to predict the ranking of the input z. The loss function (gg ()).)) minimizes the negative log- lokelikeldhood of this probability, encouraging the model to predict a ranking close to the true ranking. ListMLEE's focus on list ranking aligns with Kendall's s Tau, which measures the correlation between two rankings. This ensures that minimizing the loss can help improve Kendall's Tau.
In the following section, we will introduce how we apply these learning to rank concepts to LLM scheduling. building upon the foundation laid here.
4 Method
4.1
Problem Formulation
For a given batch of requests, we define the ground truth generation length as I, where 4 is the generation length of the i-th request in the batch. From this length list, we can obtain a ranking list where is the rank of I, within the whole batch I.
Our goal is approximate true SJF/SRTF scheduling using these rankings alleviate HOL blocking (Fig. aaa and obtain a relatively low latency in LLM serving. Different from the previous methods which target to predict the real generation length we make predictions on the ranking list r. The prediction of the ranking list is defined as p (generated by a predictor P). We compute the ranking metric Kendall's Tau 4 measure the correlation between p and A Kendall's ' Tau of 1 means the prediction p perfectly aligns with the ground truth r, hence we can use it to achieve perfect SJF/SRTF execution order. Conversely, A Kendall's Tau of suggests no correlation between p and r. An example is FCFS: the execution order (i.e., by arrival time) is not correlated with the generation length.
A higher Kendall's Tau reflects more accurate rank prediction against the oracle (i.e., SJF/SRTF), which empirically translates into higher end-to-end performance, as evidenced in Fig. 2b. Hence, our goal is optimize the predictor model P generate predictions with larger Kendall's 's Tau, which more correlated to the ground truth. However, Kendall's tau is inherently non-continuous and difficult to optimize directly. To overcome this, we apply listwise ranking loss ListMLE to optimize the predictor P. ListMLE considers the entire list of items simultaneously and treats items at all positions with equal importance, providing a more holistic evaluation of the ranking order compared to other alternatives such as pairwise and pointwise losses.
4.2 Generation Length Ranking Predictor
For our predictor P, we utilize a small OPT model as the backbone, capable of processing natural language prompts input and generating score for ranking. While previous methods 7 6 I use classification (with bucketing) to generate accurate output length predictions, we find this approach both challenging and unnecessary. Instead, the relative ranking suffices. Based on this insight, we apply learning to rank to train the OPT model. This section explains how we train the OPT model as the predictor P to rank prompts by their expected generation length.
Predictor Structure. The original OPT model can not directly output score. To address this, we append a linear layer to map the hidden states of the last layer to a floating-poin number, which serves as the ranking score.
We aim to train the OPT model to rank prompts according to their expected generation length when processed by target LLM (e.g.. Llaama3-70BB. To achieve this, we first obtain full generations by feeding prompts into the target LLM and recording the number of generated tokens. When generating model outputs, we sample tokens with temperature of 1.0, consistent with our evaluation methodology ($5.1). The following is an example of the training data structure.
Training Data.
"prompt"; "Divide 10 by 4 and remove the remainder. An"

---

"output": "\nAnswer: 2 with remainder of 0." 12
After obtaining the generation lengths, we convert them to labels representing the ranking. The simplest way would be to rank the generation lengths directly within the entire training batch and use these rankings as labels. However, recognizing that LLM generation involves some randomness due to sampling in real-world serving, we introduce more robust approach. We bucket the generation lengths in increments of 10 tokens, then rank these processed lengths to create our training labels.
Training. We train the OPT on 10k samples with a batch size of 32 for 5 epochs. We employ the ListMLE loss and the Adam optimizer with constant learning rate of 2e 2e-5,, 5, 5, 0.9, and &2 = 0.999. To accommodate OPT's context length limitations, we truncate prompts to maximum of 2,048 tokens.
The use of ranking loss offers several advantages. First, ranking loss focuses on correct ordering rather than precise classification, making it more robust when dealing with batches of requests where the output length distribution for each bucket is uneven. In contrast, classification loss typically relies on bucket labels for training, which can lead to poor predictive performance for minority buckets in imbalanced datasets. Second, ranking loss ensures more reasonable bucket size, while classification loss attempts to make the predicted labels as close to the actual labels as possible. This naturally leads to the pursuit of larger bucket sizes, which not beneficial for scheduling. Finally, ranking loss can reduce the risk of overfitting. Classification loss forces the model to minimize classification errors on the training requests, which may not generalize well to requests with covariate shifts and can cause the model to be highly sensitive to bucket size (see our study in Tab. 3
4.3 Request Scheduling with Rankings
We propose a simple but effective algorithm, for scheduling requests using ranking information, as detailed in Algorithm [ The core idea is to iteratively run the predictor model P to score new requests, then sort all requests according to their predicted generation length rankings. We form a running batch based on this sorted order, subject to memory or batch size constraints. To prevent the starvation of long requests, we' ve incorporated additional mechanisms, which we'll explain shortly. This ranking-basse based scheduling algorithm operates the iteration level, making it compatible with established LLM serving techniques such as continuous batching [3] and PagedAttention (2].
Starvation Prevention. While SJF/STTF scheduling can improve overall latency, it may lead to starvation for long requests, causing users to wait excessively for responses. Different from previous fairess- design [39]. which focuses on the fairess between different clients, we propose a max_ moi__wattin___m time fairness metric to evaluate the fairness at per-request level (hence reflecting per-user satisfaction). We define max_ waiting time fairness by considering both Time To First Token (TTFT) and Time Per Outpul Token (TPOT) in LLM serving as follows:
max waiting time- max- max(TT)))
Intuitively, max_ foo__aitiing_aeee time characterizes the maximum time interval a user experiences between receiving two tokens after sending a request to the server. A larger max_ _oait_aattnn__a time indicates a longer waiting time for the user to obtain response, signifying more severe starvation.
To mitigate starvation, our algorithm implements the following mechanism: For each scheduling if is not executed. 2) When
step, we increment request's starvation count (Storvation hrrsholll we will promote request's 's starvation count reaches pre- threshold (StarvationI hreshold), this request's 's priority by allocating "quantum" of execution time. 3) The request maintains this elevated priority until it exhausts its allocated quantum (PriorityQuanttun This simple yet effective method prevents starvation at the request level, improves max_ waiting_timm and ensures user satisfaction, as demonstrated in our experiments (555).
Evaluation
In this section, we evaluate our proposed method against several baselines and assess the effectiveness of each component. Our results demonstrate that our method achieves state-of-the-art performance in terms of both Kendall's Tau and end-to-end serving performance metrics: latency and throughput. Notably, we achieved a 2.8x lower latency in chatbot serving and 6.5x higher throughput in synthetic data generation.
5

---

Algorithm 1 Ranking Scheduler
1: Input: request queue Q, predictor model P. LLM M, hyp.r- Slarvation I hhrehhodd
prevents request's ss starvation, hyper-paaee perem--eretter PriorityQuantum limits request's priority time
2: while True do
3: Receive batch of new requests
4: for in N do
5: r.Score= P(r) (Batch Run Predictor)
6: end for
7: Append N request into Q upon arrival
8:
S =Soot(Q) according to the pair (r. Tr.Priority,rScom (User-defined sort function)
9:
B [B is running batch of the current step)
10:
for r' in S do
11:
is not full then ++ B.append(r)
12:
13:
r.Starvation Connttononntoo (Reset StareationCount when scheduled] rf Prioriiy then
14:
15:
r.Quantir uuantum==r.Qunuuue
16:
end if else
17:
18:
19:
end if end for
20:
21:
for r in do
if .SStarvationConnt StarvationI' then
23:
Promote(r.Priorit) (Promoter's r's priority and assign quantum
r.StaroationCountt-)
25:
>.Quantum= Priiii-rroooorrrnttttttt
else if Priority and r. r. then
27:
Demote(r.Prioritty)
28:
end if end for
29:
30:
Execute with
31:
Remove finished requests from Q and output
32:
end while
5.1
Evaluation Setup
Testbed. Our end-to-end evaluation testbed consists DGX server with NVIDIA A100 40GB GPUs, 256 vCPUs, and ITB host memory. The GPUs are interconnected via NVLink.
Serving Models. We utilize the latest Meta Llama-3 models in two sizes: 8B and 70B 40 All experiments use FP16/BF16 precision, which is the most common setting in LLM deployment. The 8B model runs on single GPU, while the 70B model runs on 8 GPUs with tensor parallelism 41
Workloads.
We evaluate using the ShareGPT 42 and LMSYS-Chan I comprise open-ended, real-world converstion with proprietary LLM chatbots such ChatGPT [ and Claude, as well as 25 other open-source I.LMs. For each dataset and model pair, we sample 10k non-overlapping prompts for serving and another 10k for training the ranking predictor. The length distributions of the datasets are provided in Appendix B Model generations are conducted using random sampling with a temperature of 1.0, ensuring consistency during predictor training and serving evaluation. It's worth noting that our framework is insensitive to the sampling parameters.
43 datasets, which
Evaluation metrics. For chatbot serving, the per-request latency divided by the output length. For offline synthetic generation tasks, we use throughput (requests/second) indicate request generation speed.
average and p90 per-token latency, which is
Scheduler Settings. We compare our method (i.e., ranking predictor) with four baselines implemented top of vLLM v0.4.1:

---

FCES: A Caae--Coeee--------- scheduler that supports executing prefill and decode in the same step. For each scheduling step, selects requests by earliest arrival time.
MLFQ: We implement Multi-Level Feedback Queue in I 1.2k lines of Python code on vLLM. This scheduler leverages chunked prefill from vLLM to run prefill and decode in the same step. The implementation' 's correctness validated in Appendix A
as described FastServe [4].
Perception Only (PO): We implement Perception Only to self-predict its token generation length. The implementation consists of two phases: First, we configure the LLM generate 15 tokens (half of the maximum token count used in (44) following FCFS policy, using this output to determine the predicted generation length. Second, after obtaining these predictions, we schedule subsequent requests based solely on the predicted lengths.
vLL.M, enabling the LLM 44
Classification: We train a classifier using an OPT model as backbone. For Llama-3-8B. we use the OPT-125m model, and for Llama-3-70B, we use OPT-350m, which can be supported by 8-way tensor parallelism. Following the setting in S3 [6] we use 10 buckets with a bucket size of (max context length number of buckets) for high classification accuracy. We map the hidden states of the OPT model to the number of buckets with linear layer and use the same training settings as in $4.2 but with a cross-entropy loss.
Ranking (Ours): We implement our ranking scheduler (described in $4.3) with the ranking predictor and training configuration detailed in $4.2 The implementation uses an OPT model of identical size to that used in the classification method.
5.2 Chatbot Serving Scheduling
FCFS
-
MLFQ + FO
Classfficttin
Ranking (Ours)
LLaMA-3-88, 1GPU, LMSY5-Chat-1M
LLaMA-3-8B, 1GPU, ShareGPT
Latency (sitoken)
Latency (s/taken) ken)
4
3
2-
0.0
10
30
50
10
20
40
60
Request rate (rea/s)
Request rate (reg/s)
LLaMA-3-70B, 8GPU, LMSYS-Chat-1M
LaMA-33708, 8GPU, ShareGPT
Latency (s/token)
Latency (s/token)
3-
2-
2
10
30
50
10
20
30
40
60
Request rate (req/s)
Request rate (req/s)
Figure 3: Mean latency of different schedulers with Llama-3 models on real workloads.
Fig. compares the latency of our proposed ranking method with four baseline methods on ShareGPT and LMSYS-Chat- 1M datasets with increasing arrival rates 2 12] Under a rate of requests/sec- ond, our method improves mean latency by up to 6.9x compared to FCFS and 1 1.5x-1. 99 compared to PO. MLFQ and PO still face severe HOL blockings as they must run all requests for a certain time to obtain information for scheduling. PO must execute all arriving requests with the LLM to generate a length prediction. MLFQ must run all arriving requests before they enter the next priority level. The classification method optimizes for accuracy instead of ranking, missing optimization opportunities. While classification and our method still need to process all the requests first to obtain a prediction, using an OPT model takes less than 2% of the time (as shown in 5.5) thus greatly reducing HOL blocking.
Handling buristiness. We evaluate our method's performance under bursty workloads, where users suddenly submit many requests to the LLM server 45
46 Tab. [ the latency of our method against baselines with burst of 2k requests. Our proposed ranking method significantly improves latency, achieving up to 2.0x lower mean latency improve and 2.8 lower P90 latency compared to PO.
7

---

Table 1: Latency (s/token) with Burst of 2K requests
Mean Latency (stoken)
P901 Latency (shaken)
Model
Dataset
FCFS
MLFQ
PO
Class.
Ours
PCFS
MLFQ
PO
Class.
Ours
Llama 3-8B
ShareGPT
1.15
1.07
1.35
1.13
0.56
1.60
1.57
1.67
1.51
0.67
Llama-3-8B
LMSYS-Chat--I
1.73
0.80
0.75
1.77
0.38
4.86
1.36
1.47
4,98
0.52
Llama-3-708
SharoGPT
1.44
1.04
1.26
0.78
2.01
1.89
1.35
0.96
Llama-3-70B
LMSYS-Chat-IM
2.17
1,00
0.95
2.23
0.54
5.54
1.91
1.72
5.72
0.82
5.3 Synthetic Data Generation Scheduling
Synthetic data generation (SDG) emerging as an important inference workload due to the data-hungry nature of LLMs. In SDG, shorter responses are often preferred for several practical reasons: First, generating concise conversations is more cost-effective given the large volume and diversity of samples required (47) in SDG. Second, longer generations can introduce evaluation metric bias [48] 49 50]. Consequently, samples with shorter generation lengths are often preferred for model training in specific applications.
Our proposed method can improve generation throughput in these scenarios by prioritizing shorter responses. We conducted two experiments to validate this approach: 1) We established a quantity threshold (i.e., 1 requests) and measure how long the schedulers need to generate such samples given 10k prompts. 2) We set a time constraint (5 minutes) and evaluated the number of samples each scheduler could generate from the same prompt pool. The results are presented in Tab. The classification method underperformed compared to FCFS due to the overhead of preprocessing 1k prompts with the OPT model and its limited ability to identify shorter requests. contrast, our proposed method effectively prioritized shorter requests, achieving a 2.4x-6.5x reduction in generation time for 1k requests and up 3.2x improvement in throughput within the 5-minute window. However, it's important note that in scenarios where shorter generations are not preferred, the throughput improvements would be minor.
Table 2: Throughput Improvement with Proposed Ranking Method
Time (s) To Generate Ik Samples
Generated tkamples within Smin
Model
Dalasel
FCFS
Classification
Ranking (Ours)
FCFS
Clussilication
Ranking (Ours)
Llama-3-8B
ShareGPT
343,29
421.92
143.18
655
1706
Llama-3- 3-8B
LMSYS-Chat-IM
197.38
237.40
30.48
1348
1644
4434
Llama-3-708
SharsGPT
440.71
512.84
231.59
479
Llama-3-70B
LMSYS-Chat-IM
253.68
338.83
59.67
1167
895
3710
5.4 Comparing Ranking Predictors
We show that the accuracy of the targeted classification method is suboptimal for LLM scheduling. Tab. 3 compares the prediction ability of the classification method with different bucket sizes. We evaluate the classification metric (i.c., accuracy) for the classification method and the ranking metric (i.e., Kendall's ' Tau) for all methods on the same randomly sampled test set. A larger bucket size shows better accuracy but does not necessarily indicate a higher Kendall's Tau.
We also evaluate the end-to-end performance of these methods. The "Lat." column shows the mean latency to process 2k bursts of requests as in $5.2 The "Time" column shows the time to generate Ik synthetic data as in $5.3 A method with higher Kendall's Tau correlates with lower latency, as proposed in 3 The time to generate k synthetic data is less related to Kendall's ' Tau, as a high Tau with a large bucket size does not necessarily mean the predictor can correctly select the shortest requests.
PO achieves higher Kendall's Tau on the LMSYS -hatt- LM dataset. However, it needs to use the LLM itself to process all requests and generate few tokens first for prediction, which introduces very large HOL overhead compared to light predictor predictor-based methods, despite its good performance terms of Kendall's 's Tau. In all other settings, proposed ranking method outperforms all other methods in terms of ranking metrics and end-to-end performance.
Generalization Ability across Distribution Shifts. data distribution shifts by using the LMSYS-Chat-1 M dataset to test the predictor trained on ShareGPT, and vice versa. The predictor trained on ShareGPT achieves Kendall's Tau of 0.54 on ShareGPT but
We evaluate the predictor's performance under

---

FOPS
Raniing
Ranking Stanvation Provention
(a) LLa LA-3-7077 SGPUs, LMSYS-Chat-1MM
(b) LLaMA-3-708, SGPUs, ShareGPT
Max-TPOT (5)
200
Max-TPOT
150
100
15
20
25
10
15
20
25
Request (ree/s)
Request rate (reg/s)
Figure 4: Average max_ waiting time across all requests with different scheduling method
LMSYS-Chat-1M
LLaMA-3-708 ShareGPT
Latency (5.token)
Latency (sttoken)
1.5
1.5
1.0
1.0
10
30
Request (reats)
Request (reqis)
Figure 5: Influence of starvation prevention on latency
drops to 0.45 when tested on LMSYS-Chat-IIE Chat-IM. Conversely, the predictor trained on LMSYS- Chat- IM achieves Kendall's Tau of 0.62 on LMSYS-CMa IM but decreases to 0.40 when tested on ShareGPT.
Although the predictor experiences performance degradation, it still retains predictive capability, demonstrating a certain level of generalization ability. In real- wolld scenarios, we can mitigate the impact of distribution shifts by periodically retraining the model with historical data to maintain good ranking prediction performance.
Table 3: Ranking prediction ability with different classification (Class. in table) settings (i.c., different bucket sizes) for Llama-3-70B. Lat. column shows the mean latency processing burst of 2k requests for chatbot serving. Time column shows the time to generate k requests for synthetic data generation. Op- timal Prediction is using the generation length of one random seed to predict the length of another seed. Note that the p-values of Kendall's Tau are below a given significance level (i.e., le-3) in all settings.
SharGPPT
LMSYS-Chut-In
Method
(9)
Tau (f)
(shok.)
Time
Acc. (%)
(t)
Lat. (shok.)
Time
Optimal Prediction
102.04
Ranking (Ours)
0.54
0.78
231.59
0.62
0.54
$9.67
Class. (#Buckets=10)
85.1%
512.84
96.8%
Class. (Bucket 10ze=100)
28.1%
0.49
0.84
265.91
43.4%
0.58
0:77
101 61
(Bucket Size 10)
272.13
Class. (Bucket Sizcml)
1.0%
0,32
1,00
341.63
7.3%
0.50
0.68
92.93
PO
0.51
1.04
>600
0.67
0.95
322.13
5.5 Effectiveness Analysis
Effectiveness of Starvation Prevention. We show that our proposed starvation prevention method ($43 greatly reduces starvation. as measured by max waiting time. Fig. shows that mean max waiting time is reduced by up to 3.4x on LMSYS-Chat-IM and up to 3.3x on ShareGPT compared to not using starvation prevention. Fig. Fig.55illuste illlustrate that starvation prevention has minimal side effects on latency, with less than 10% overhead in most cases and less than 30% in all cases, which an acceptable trade-off.
Overhead of Predictor Model. Tab, illustrates the overhead of the ranking predictor in responsing kk requests. "Prefill Time" measured by only processing the prompts with the original LLM. The overhead of the ranking models (only processing the prompts) is less than 2% in all settings. The overhead on the ShareGPT dataset is slightly higher (i.e.. 1. % and 1.69%) because the prompt length of ShareGPT is longer, shown in Appendix B The execution time of OPT is 10%-15% of the execution time the original L.L.M in processing the prompts, largely alleviating the HOL blocking cost in length prediction compared to PO in chatbot servings.

---

Table 4: Overhead of Predictor Model
Model
Dataset
Overall Time (6)
Prefill Time (s)
Predictor Time (5)
Overhead (%)
Llama-3-8B
ShareGPT
254,23
22.34
2.81
1.11
Llama-3-8B
LMSYS-Chat-IN
127.82
1.03
Llama- 3-70B
ShareGPT
419.74
46.06
7.09
1.69
I.aama 3: 70B
LMSYS Chat IM
211.30
15.44
2.46
1.16
Limitations
Limitation of the Ranking Metric. Although Kendall's Tau is a widely used ranking metric, it has limi- tations when it comes to reflecting end-to-end performance. For example, consider a ranking prediction that accurately reflects generation length. If we randomly shuffle the predictions within the shortest 70% of requests and separately shuffle those within the longest 70%, the Kendall's Tau score will still be 0.5 for both. However, this leads significant latency difference, with the Llama-8B -8B model the ShareGPT dataset showing a 1.8x increase in latency. contrast, when the ranking is uniformly shuf- fled across the entire list, Kendall's Tau exhibits stronger correlation with latency, as shown in Fig.
Limitations of the Proposed Ranking Scheduler. The proposed ranking scheduler designed to work with standard LLM serving techniques, such continuous batching and paged attention. However, it has not yet been fully tested with newer optimizations like chunk-prefill [13] and prefill-ecodde disaggregation [12). Future work will focus integrating the scheduler with these advanced techniques to assess their combined performance benefits.
Conclusion
In this paper, we propose method to train predictor that learns to rank the generation length of LLM responses based on the given prompts using a learning-to-run approach. We implement a rank-based scheduler on top of vLLM, demonstrating significant improvements across various tasks. Specifically, our method reduces latency by 2.8x in chatbot serving and increases throughput by 6.5x in symthetic data generation. Given the simplicity and effectiveness of our approach, believe it can be easily integrated into production-level LLM serving systems, reducing serving latencies while enhancing service quality.
Acknowledgments and Disclosure of F Funding
We extend our gratitude to Junda Chen, Yinmin Zhong, and Zhuohan Li for their valuable feedback. We also thank the anonymous reviewers for their insightful and constructive comments.
10

---

References
[1] OpenAl. Introducing chatgpt. https://openaa.coo///nnexeaaaaap November 2022.
[2] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, pages 61 1-626, 2023.
[3] Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung-Gon Chun. Orca: distributed serving system for [Transformer Based) generative models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), pages 521-538, 2022.
[4] Wikipedia contributors. Kendall rank correlation coefficient -eifiiient-Wikippdiiia 2024. [Online; accessed 18 10-M4y.2024).
Wikipedia, the free encyclopedia,
[5] Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.01068, 2022.
[6] Yunho Jin, Chun-Feng Wu, David Brooks, and Gu- Yeon Wei. غ²: Increasing gpu utilization during generative inference for higher throughput. Advances in Neural Information Processing Systems, 36, 2024.
[7] Zangwei Zheng, Xiaozhe Ren, Fuzhao Xue, Yang Luo, Xin Jiang, and Yang You. Response length perception and sequence scheduling: An llm -in-weeeeeeeed Ilm inference pipeline. In A. Oh, Naumann, Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 65517 55517-65530. Curran Associates, Inc., 2023,
[8] Tie- Yan Liu al. Learning to rank for information retrieval. Foundations and Trends@ in Information Retrieval, 333):225-331, 2009.
[9] Pratyush Patel, Esha Choukse, Chaojie Zhang, fñigo Goiri, Aashaka Shah, Saeed Maleki, and Ricardo Bianchini. Splitwise: Efficient generative Ilm inference using phase splitting. arXiv preprint 2x
[10] Foteini Strati, Sara Mcallister, Amar Phanishayee, Jakub Tamawski, and Ana Klimovic. D ej Kv-cache streaming for fast, fault-tolerant generative Ilm serving. arXiv preprins 2003v22403.01876 2024.
[11] Cunchen Hu, Heyang Huang, Liangliang Xu, Xusheng Chen, Jiang Xu, Shuang Chen, Hao Feng, Chenxi Wang, Sa Wang, Yungang Bao, et al. Inference without interference: Disaggregate Ilm inference for mixed downstream workloads. arXiv preprint arXiv:2401.
2024.
[12] Yimmin Zhong, Shengyu Liu, Junda Chen, Jianbo Hu, Yibo Zhu, Xuanzhe Liu, Xin Jin, and Hao Zhang. Distserve: Disaggregating prefill and decoding for model serving. arXiv preprint arXiv:2401.09661 2024.
large language
[13] Amey Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav Gulavani, Alexey Tumanov, and Ramachandran Ramjee. Taming wooughhut-latennee tradeoff in Ilm inference with sarathi-serve. arXiv preprint 2403.22003.0231 2024.
[14] Bingyang Wu, Yinmin Zhong, Zili Zhang, Gang Huang, Xuanzhe Liu, and Xin Jin. Fast distributed inference serving for large language models. arXiv preprint arXiv:2305.0592 2023.
[15] Jiachen Liu, Zhiyu Wu, Jae- Won Chung. Fan Lai, Myungjin Lee, and Mosharaf Chowdhury. Andes: Defining and enhancing preprint arXiv:2404.12220 2024.
in Ilm-based text streaming services. arXiv
[16] Jovan Stojkovic, Chaojie Zhang, iñigo Goiri, Josep Torrellas, and Esha Choukse. Dynamollm: Designing Il inference clusters for performance and energy efficiency. arXiv preprint 20X04:2408.00744, 2024.
11

---

[17] Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint arXiv:1910.01 108, 2019.
[18] Ke Cheng, Wen Hu, Zhi Wang, Peng Du, Jianguo Li, and Sheng Zhang. Enabling efficient batch serving for Imaas via generation length prediction. arXiv preprint wrX.v:2406.0478355. 2024.
[19] Haoran Qiu, Weichao Mao, Archit Parke, Shengkun Cui, Saurabh Jha, Chen Wang, Hubertus Franke, Zbigniew T Kalbarczyk, Tamer Başar, and Ravishankar K Iyer. Efficient interactive I1m serving with proxy model-based sequence length prediction. arXiv preprint W4Xiv:2404008000 2024.
[20] Haoran Qiu, Weichao Mao, Archit Parke, Shengkun Cui, Saurabh Jha, Chen Wang, Hubertus Franke, Zbigniew Kalbarczyk, Tamer Başar, and Ravishankar K Iyer. Power-aware deep learning model serving with [μ-Serve]. In 2024 USENIX Annual Technical Conference (USENIX ATC 24), pages 75-93, 2024.
[21]
Alexandros Karatzoglou, Linas Baltrunas, and Yue Shi. Learning to rank for recommender sys- tems. In Proceedings of the 7th ACM Conference on Recommender Systems,, pages 493-494, 2013.
[22] Tianqi Chen, Lianmin Zheng, Eddie Yan, Ziheng Jiang, Thierry Moreau, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. Learning to optimize tensor programs. Advances in Neural Information Processing Systems, 31, 2018.
[23] Xingguang Chen, Rong Zhu, Bolin Ding, Sibo Wang, and Jingren Zhou. Lero: applying learning-to-ranke in query optimizer. The VLDB Journal, pages 1-25, 2024.
[24] David Cossock and Tong Zhang. Subset ranking using regression. In Learning Theory: 19th Annual Conference on Learning Theory, COLT 2006. Pitssurgh, PA, USA, June 22-25, 2006. Proceedings 19, pages 605-619. Springer. 2006.
[25] Ping Li, Qiang Wu, and Christopher Burges. Mcrank: Learning to rank using multiple classi- fication and gradient boosting. Advances in neural information processing systems, 20, 2007.
[26] Dawei Yin, Yuening Hu, Jiliang Tang, Tim Daly, Mianwei Zhou, Hua Ouyang, Jianhui Chen, Changsung Kang, Hongbo Deng, Chikashi Nobata, et al. Ranking relevance in yahoo search. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 323-332, 2016.
[27] Koby Crammer and Yoram Singer. Pranking with ranking. Advances in neural information processing systems, 14, 2001.
[28] Yoav Freund, Raj Iyer, Robert E Schapire, and Yoram Singer. An efficient boosting algorithm for combining preferences. Journal of machine learning research, 4(Nov):933 1993-996,,200 2003.
[29] Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. Learning to rank using gradient descent. In Proceedings of the 22nd international conference on Machine learning, pages 89-96, 2005.
[30] Zhaohui Zheng, Keke Chen, Gordon Sun, and Hongyuan Zha. A regression framework for learning ranking functions using relative relevance judgments. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 287-294, 2007.
[31] Christopher Burges, Robert Ragno, and Quoe Le. Learning to rank with nonsmooth cost functions. Advances in neural information processing systems, 19, 2006.
[32] Qiang Wu, Christopher JC Burges, Krysta M Svore, and Jianfeng Gao. Adapting boosting for information retrieval measures. Information Retrieval, 13:254-270, 2010.
[33] Christopher JC Burges. From ranknet to lambdarank to lambdamart: An overview. Learning, (1(23581)):81, 2010.
[34] Jun Xu and Hang Li. Adarank: a boosting algorithm for information retrieval. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 391-398, 2007.
12

---

[35] Michael Taylor, John Guiver, Stephen Robertson, and Tom Minka. Softrank: optimizing non-smin non-smooth rank metries. Proceedings of the 2008 International Conference on Web Search and Data Mining, pages 77-86, 2008
[36] Zhe Cao, Tao Qin, Tie- Yan Liu, Ming-Feng Tsai, and Hang Li. Learning to rank: from pairwise approach to listwise approach. In Proceedings of the 24th international conference on Machine learning, pages 129-136, 2007.
[37] Fen Xia, Tie- Yan Liu, Jue Wang, Wensheng Zhang, and Hang Li. Listwise approach to learning to rank: theory and algorithm. In Proceedings of the 25th international conference on Machine learning, pages 1 112-1119) 2008.
[38] Przemyslaw Pobrotyn and Radostaw Biatobrzeski. Neuralndeg: Direct optimisation of ranking metric via differentiable relaxation of sorting. arXiv preprint arX1v:2/00.0783)/
[39] Ying Sheng, Shiyi Cao, Dacheng Li, Banghua Zhu, Zhuohan Li, Danyang Zhuo, Joseph E Gonzalez, and lon Stoica. Fairness in serving large language models. arXiv preprint arXiv:2401.00588 2023.
[40] Meta. Introducing meta Ilama 3: The most capable openly available Ilm to date. Meta Al, 2024.
[41] Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. Megatron-Im: Training multi-billion parameter language models using model parallelism. arXiv preprini 190i 2019.
[42] ShareGPT Team. https//shareept.com// 2023.
[43] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Tianle Li, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zhuohan Li, Zi Lin, Eric Xing, al. Lmsys-chat-Ime Im: A large-scale real-world Ilm conversation dataset. arXiv preprint arXiv:2309.1199) 2023.
[44] Zangwei Zheng, Xiaozhe Ren, Fuzhao Xue, Yang Luo, Xin Jiang, and Yang You. Response length perception and sequence scheduling: An lmmwewpwereed Ilm inference pipeline. Advances in Neural Information Processing Systems, 36, 2024.
[45] Cade Daniel, Chen Shen, Eric Liang, and Richard Liaw. How continuous batching enables 23x throughput in Ilm inference while reducing p50 latency.
leabbinn--Im--ifereneee June 2023.
[46] Yuxin Wang, Yuhan Chen, Zeyu Li, Zhenheng Tang, Rui Guo, Xin Wang, Qiang Wang, Amelie Chi Zhou, and Xiaowen Chu. Towards efficient and reliable Ilm serving: A real-world workload study. arXiv preprint arXiv:2401. 22401.176444 /7644, 2024.
[47] Loubna Ben Allal, Anton Lozhkov, Guilherme Penedo, Thomas Wolf, and Leandro von Werra. Cosmopedia, February 2024.
[48] Yann Dubois, Chen Xuechen Li, Rohan Taori, Tianyi Zhang, Ishaan Gulrajani, Jimmy Ba, Carlos Guestrin, Percy $ Liang, and Tatsunori B Hashimoto. Alpacafarm: A simulation framework for methods that learn from human feedback. Advances in Neural Information Processing Systems, 36, 2024.
[49] Prasann Singhal, Tanya Goyal, Jiacheng Xu, and Greg Durrett, long way to go: Investigating length correlations in rlhf. arXiv preprint arXivv2310.03711 2023.
[50] Yann Dubois, Balázs Galambosi, Percy Liang, and Tatsunori B Hashimoto. Length-controlled alpacaeval: simple way to debias automatic evaluators. arXiv preprint arX44:2404.04445, 2024.
[51] Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Stanford alpaca: An instruction-followin llama model. https: /// thub. commtootsstteeeeeee ttttttttsuuuaaa peatsu-lab/aaa lab/stanf st//stanfoo _aaacc 2023.
13

---

A Implementation of MLFQ
We validating the correctness of MLFQ implementation by presenting the relationship of finish time and ouipul length of requests as shown in Fig. 6 This presents burst of 1k requests with an MLFQ base quantum of 16 seconds, the quantum growth rate of 2, and requests limitation of 256 for each step in the vLLM scheduler.
These rectangular blocks, whose edge lengths grow exponentially with the quantum growth rate, represent requests that are completed queues of varying priorities. When requests from higher priority fail to fill the entire sliding window, those from lower priority begin be processed, resulting different blocks being adjacent to one another.
The max request limitation for each step is like sliding window on all requests. According to the property of MLFQ, requests within the sliding window have two ways out 1) Finish and pop out marked by linear increase in output lengths over time; 2) Timeoul and demole, occurring when the finish time reaches a multiple of the quantum for the current queue, a batch requests that arrive at the same time will be demoted simultancously. With short quantum for the priority queue, most requests are likely to demoted rather than completed within the quantum, which explains the clear line trend for the first block shown in the figure. When the finish time reaches multiples of the base quantum (16 seconds in this figure), a new linear growth line appears caused by batch timeout demotions.
Relationship between Output Lengths and Finish Time
500
400
100
Finish Time
300
100
0
200
400
600
800
1000
Output Lengths
Figure 6: Finish Time Requests with MLFQ Scheduler.
14

---

B Dataset Length Distribution
We randomly sample 10k samples and present the dataset distribution in Fig. We compute the input length by appending the chat template onto the prompts. We have mean value of 85 input tokens for LMSYS-Chat- IM and than LMSYS- MMISYS-Chatt 1M dataset. On average, the 70B version of Llama-3 has slightly longer output length (i.c., around 15 tokens).
value of 240 input tokens for ShareGPT, which is 3x longer IM. The output length of the ShareGPT dataset is 100 tokens more than the
Figure 7: Dataset Length Distribution
Llama3-88 LMSYS-Chat-IM
Llama3-708 LMSYS-Chat-1M
3.5
3.5
Input (mean: 85)
Input (mean: 85)
3.0
Output (mean: 293)
3.0
Output (mean: 307)
2.5
2.5
Density (1e-2)
Density (1e-2)
2.0
2.0
1.5
1.5
1.0
1.0
0.5
0.5
0.0
0.0
500
1000
1500
2000
0
500
1000 # Tokens
1500
2000
# Tokens
Llama3-8B ShareGPT
Llama3-70B ShareGPT
1.5
1.5
Input (mean: 240)
Input (mean: 240)
Output (mean: 412)
Output (mean: 429)
1.2
1.2
Density (1e-2)
Density (1e-2)
0.9
0.9
0.6
0.3
0.3
0.0
0.0
0
500
1000 Tokens
1500
2000
0
500
1000
1500
2000
Tokens
C
Predictor's Sensitivity to Batch Size
The ranking scheduler is insensitive to batch size variations. We assess the predictor's 's sensitivity to batch size the L.MSYS-Cht-IIM dataset, detailed in Tab. We use the predictor to calculate Kendall's 's Tau for various batch sizes and derive the mean and variance across the entire dataset. This experiment shows that Kendall's Tau remains within a narrow range across different batch sizes. Additionally, our method addresses severe HOL problems when there are numerous requests, in which case, the batch size is often sufficiently large for the predictor to be effective and robust.
15

---

Table 5: Predictor's Sensitivity to Batch Size
Batch Size
Kendall's Tau Mean
Kemdall's Tau Variance
8
0.619
0.04
16
0.625
0.02
32
0.624
0.008
64
0.625
0.0007
128
0.619
0.001
D Relationship Between the ListMLE Loss and the Kendall's Tau
The ListMLE loss defines a parameterized exponential probability distribution over all scores (as given by the model) and formulates the loss function the negative log likelihood of the ground truth ranking y. Meanwhile, Kendall's Tau measures the ordinal association between the scores (as given by the model) and the ground truth ranking y. Is challenging accurately describe the relationship between the likelihood and ordinal association. However, we provide an analysis demonstrating that minimizing the ListMLE loss can help improve Kendall's Tau.
To simplify the problem, we assume there are no ties between any two items, mcaning each pair should be either concordant or discordant, this case, Kendall's s Tau is defined -= Ne -a 11/22 where N and Na are the number of concordant and discordant pairs in two rankings, and n is the total number of items. As N₂ increases, N₂ decreases because the sum of N₂ and Na is fixed. Consequently, 4AN have AT z1|n-1j+ where increases when No increases.
ListMLE loss is defined as ((g(x) (()(()))))))) -log P(yl w:g). where P(y (::)) represents the likelihood of the ground truth ranking As the likelihood of the ground truth ranking increases, the loss decreases. Although the increase of (yl (zgg) does not guarantee that N₂ increases, the increase in the likelihood of the ground truth ranking should generally lead to greater agreement between the ground truth ranking and the scores given by the model, which implies increase in the number of concordant pairs (or No) and decrease in the number of discordant pairs (or Na) between the scores and the ground truth. Thus, minimizing the loss can help improve Kendall's Tau.
We further illustrate this relationship by tracking Tau and loss throughout the training process, as shown in Tab. 6 The Pearson correlation coefficient between Tau and loss is -0.9, which means that ListMLE loss and Kendal's Tau coefficient are highly negatively correlated.
Table 6: Relationship Between the ListMLE Loss and the Kendall's Tau
Step
Kendall's
20
0.44
77.79
40
0.51
75.73
60
0.53
72.61
80
100
0.55
70.59
140
0.56
67.01
160
0.59
69.94
180
0.59
70.88
200
0.57
68.84
240
0.61
66.90
280
0.56
68.71
16

---

E
The Performance Gap Between The Proposed Method and Oracle
Due noise and randomness the sampling process, in this section define the Oracle utilizing sampling results from one seed to guide the scheduling of another sampling, which represents the best performance achievable given one sampling result. The performance gap between the ranking-based method (ours) and the Oracle varies depending on the evaluation dataset. On certain datasets, our proposed method can perform as well as the Oracle. For instance, when tested on the Alpaca [51] dataset with the Llama-8B model, our proposed method closely approximates the Oracle in terms of Kendall's Tau and end-to-end latency for burst of 2K requests, as depicted in Tab. These tests were conducted on single A100 80GB GPU.
On datasets such LMSYS S-Cat-- 1M and ShareGPT, there remains small gap between the proposed ranking-bass method and the Oracle. The comparison between the ranking- -baedd method (indicated "Ranking (Ours)") and the Oracle (indicated as "Optimal Prediction") is presented in Tab.
Table 7: Relationship Between ListMLE Loss and Kendall's Tau
Kendall's Tau
Latency (shtoken)
Ours
0.73
0.28
Oracle
0.72
0.24
FCFS
F Influence of The Predictor Size
Our results show that the model size has a minor effect on the prediction ability, as indicated in the following Tab. 8
The choice considerations. The OPT-350m model, with 16 attention heads, can be easily deployed using 8-way tensor parallelism, which is also the requirement for the Llama-70B model. In contrast, OPT- 12mm model with 12 attention heads cannot be deployed across 8 GPUs, as discussed in $ We deploy the OPT-125m predictor solely on I GPU, necessitating the other GPUs wait when executing the predictor. This configuration results in waste of resources and may lead to performance degradation.
OPT-350m model for Llama-70B model is primarily driven by deployment
Table 8: Relationship Between ListMLE Loss and Kendall's Tau
Kendall's Tau
350m-OPT
ShareGPT
0.55
LMSYS-Chat-IM
0.64
0.62
G Consideration of Ignoring The Prompt Length
In practice. we have found that focusing solely on the generated length both simple and sufficiently effective.
First, our observations from the Imsys-chat-I M and ShareGPT traces, which represent real-world see- narios, indicate that prompt length not a critical factor in generation time. Specifically, the prefill time constitutes only 5% on Imsys-chat- 1M and 8% ShareGPT, respectively, of the entire generation time, indicating that they have minor impact on overall latency. Note that there are already long prompts in the workloads we tested. For example, 1 % of prompts the ShareGPT dataset exceed 900 tokens.
Second, although this paper does not particularly focus on long contexts (e.g., prompt length > 32k tokens). argue that handling long prompts is relatively straightforward. Since prompt lengths are always known priori, it is casy to accurately approximate the latency of the prefill phase through profiling. We can also map the relative ranking of generation length into length estimation based on the dataset distribution. By simply adding the prefill time estimation to the current framework, can provide end-to-end generation time approximation for scheduling.
17

---

H Influence of Correcting Mispredictions Dynamically
We have implemented preemptive scheduling, where at each decoding step, compare the generation rankings of new-incoming requests with those of the currently running requests and preempt those with lower rankings (as detailed in Algorithm T.. However, we do not re-predict the scores for requests that have already been executed during the generation process. Our findings, presented in Tab, g indicate that re- preddccctionn offers minimal improvement. These experiments were conducted using a Llama-3- 3-----BBBBBB 8B model on a single 80GB A100 GPU.
Table 9: Influence of Correcting Mispredictions
Latency (shokenn
ShareGPT
0.43
0.44
LMSYS-Chat-IM
0.64
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section 6: Limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach.
For example, facial recognition algorithm may perform poorly when image resolution is low or images taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
outcome might be that reviewers
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
19

---

Justification:
The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and ross-refere.eed.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proof' can either appear the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proof' provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims conclusion of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have included the information reproduce the experiments in the Evaluation and Method sections.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of fosed-source models, it may be that access to the model is limited in some way (e-g., registered users), but it should possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
20

---

Answer: [Yes]
Justification:
The implementation is publicly available at https://githu: com/
hao- aai-lab/vllng 1tr
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https
for more details.
While we encourage the release of code and data, understand that this might not be pos- sible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central the contribution (e.g., for
open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines ss asionPolicy for more details.
(https://nips. httpaiippp.cpppppieipeppepp wttp://ccpccccguideeeeeeeeeeeeee http:///wapp..ccoiiii/////ee//ee httee/guieseeecSuiieeeeeeeeeeeee
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperpa- rameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We have specified the experimental details in Section 4.2: Generation Length Ranking Predictor, and Section 5.1: Evaluation Setup.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: This paper does not include error bars, confidence intervals, statistical significance tests due to very high computational cost running all experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
21

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: This paper indicates the type of compute workers CPU and GPU in the evaluation section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't ' make it into the paper).
9. Code Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consideration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does address societal impact.
Examples negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
22

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recogmize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We cite the original paper that produced the code package dataset.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
23

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The code is publicly available at htttp:://githbb.. hwtp:ttth........aaaaaaeeeeece
vilm-1tr
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
24


Reviews:
[{"review_id": "ZKJWazxLKR", "reviewer": "Reviewer_RLWW", "summary": "The paper addresses the inefficiencies in scheduling LLM inference requests, which often use a first-come-first-serve (FCFS) strategy, leading to Head-Of-Line (HOL) blocking and reduced throughput. The authors propose a novel scheduling method based on predicting the relative ranks of output lengths in a batch of requests, rather than attempting to predict exact generation lengths. This prediction helps in approximating the shortest-job-first (SJF) schedule, which is known to minimize average latency.", "questions": "1. Why is the improvement on dataset Sharegpt and lmsys different, as shown in table3.", "limitations": "See weakness.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper employs a straightforward but effective scheduling algorithm that approximates the shortest job first (SJF) strategies. This approach effectively reduces response latency and improves throughput. The authors have tackled the challenge of accurately approximating SJF. The empirical results demonstrate significant improvements in both latency and throughput, highlighting the effectiveness of their approach. The paper introduces interesting metrics to determine the relative range of output lengths. \n\nThe paper addresses a crucial issue in LLM workload scheduling. By focusing on reducing response latency and enhancing throughput, it tackles a significant problem that is highly relevant to the efficiency and performance of LLM servingsystems.", "weaknesses": "- The current scheduling approach only considers output length. Would you also consider other dimensions, such as prompt length? Longer prompt lengths can consume more memory and increase token latency, impacting overall response latency and throughput. Additionally, would you consider implementing preemptive scheduling to correct any mispredictions dynamically?\n\n- Your predictor is trained using 10k traces from ShareGPT and LM-SYS. However, these traces are primarily from GPT-4 and other models. Have you considered that different models Llama3 might behave differently, with varying verbosity and output lengths even for the same prompts? If the predictor cannot be reused across different models, you might need to account for the overhead of retraining the model to maintain accuracy.\n\n- You should discuss Andes [1], which also propose a request scheduling strategy to improve quality of experience. \n[1] Andes: Defining and Enhancing Quality-of-Experience in LLM-Based Text Streaming Services \n\n- SJF scheduling inherently risks starving requests with longer response length, as these jobs can be indefinitely delayed. How do you address this issue to ensure that longer requests are also processed in a timely manner?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful and helpful feedback! We would like to address your questions in the below response.\n\n**Q1.1: The current scheduling approach only considers output length. Would you also consider other dimensions, such as prompt length? Longer prompt lengths can consume more memory and increase token latency, impacting overall response latency and throughput.**\n\n**A1.1:** Considering prompt length is indeed a nice suggestion, which we have previously considered, but we found that in practice, focusing only on generated length is simple yet sufficiently effective.\n\nFirst, we observe from lmsys-chat-1m and ShareGPT – two traces that represent real-world scenarios – that prompt length is not crucial in generation time. Specifically, the prefill time accounts for only 5% on lmsys-chat-1M and 8% on ShareGPT, respectively, of the entire generation time, indicating they have a minor impact on overall latency. Note that there are already long prompts in the workloads we tested. For example, 1% of all prompts in the ShareGPT dataset exceed 900 tokens.\n\nSecond, although this paper does not particularly focus on long context (e.g., prompt length > 32k tokens), we argue it is relatively straightforward to handle long prompts. Since prompt lengths are always known a priori – it is easy to accurately approximate the latency of the prefill phase via profiling. We can also map the relative ranking of generation length into a length estimation according to the dataset distribution. Then, simply adding prefill time estimation to the current framework together provides an end-to-end generation time approximation for scheduling. \n\n**Q1.2: Additionally, would you consider implementing preemptive scheduling to correct any mispredictions dynamically?**\n\n**A1.2:** We’ve already employed preemptive scheduling. In each decoding step, we compare the generation rankings of new-coming requests and the running requests and preempt the requests with low rankings (Algorithm 1).  However, we will not re-predict the score for an executed request during the generation process. We found that re-prediction yields little improvement, as shown in the following table. We conducted the experiments using a llama-3-7b model with a single 80GB A100 GPU. \n\n|  Latency(s/token)   | ours  | re-predict |\n|  ----  | ----  | ----  |\n| lmsys  | 0.43 | 0.44 |\n| ShareGPT  | 0.64 | 0.64 |\n\n**Q2: Your predictor is trained using 10k traces from ShareGPT and LM-SYS. However, these traces are primarily from GPT-4 and other models. Have you considered that different models Llama3 might behave differently, with varying verbosity and output lengths even for the same prompts? If the predictor cannot be reused across different models, you might need to account for the overhead of retraining the model to maintain accuracy.**\n\n**A2:**  We would like to clarify that we do not use the outputs from GPT-4 or other models. The prompts are collected from human users, and answers are generated by the target model (e.g.,  llama3), as stated in section 4.2. We only need to train predictors for each dataset-model pair. The cost of training is negligible: It takes ~10 minutes on a single A100 GPU to train a predictor per long-standing serving job.\n\n**Q3: You should discuss Andes [1], which also propose a request scheduling strategy to improve quality of experience. [1] Andes: Defining and Enhancing Quality-of-Experience in LLM-Based Text Streaming Services**\n\n**A3:** Andes and our proposed method focus on different aspects of LLM serving. Andes introduces a novel quality of experience (QoE) metric for text streaming services, which measures human satisfaction during the entire end-to-end token delivery process. Andes employs an online preemptive scheduling method. At the beginning of each time quantum, it decides which requests to run based on the scheduling objectives (e.g., average QoE) for the upcoming time frame. However, our proposed method primarily aims to optimize latency by executing the requests with the lowest estimated generation length (as predicted by the predictor) to approximate SJF/SRTF at the start of each decoding step. We will discuss Andes in the related work section in the revised version.\n\n**Q4: SJF scheduling inherently risks starving requests with longer response length, as these jobs can be indefinitely delayed. How do you address this issue to ensure that longer requests are also processed in a timely manner?**\n\n\n**A4:** We have discussed starvation prevention in section 4.3 and presented the results in section 5.5. Specifically, we defined max_waiting_time fairness to measure whether a request suffers from starvation. Our starvation counter (in Algorithm 1) prevents users from waiting too long for responses. The results in section 5.5 (Figures 4 and 5) demonstrate that our method can significantly alleviate starvation.\n\n**Q5: Why is the improvement on dataset Sharegpt and lmsys different, as shown in table3.**\n\n**A5:** Different datasets exhibit varying prompt/generation length distributions (Appendix B) and data distributions. For instance, some problems can be answered fixedly, resulting in LLMs producing similar generation lengths across different trials. However, other problems may be addressed in various ways, leading to LLMs generating very different lengths in different trials. The latter pattern is unpredictable and ShareGPT encompasses more of these unpredictable problem types. Line *Optimal Prediction* in Table 3 employs the generation length of one random seed to predict the length using another seed. It shows that predicting the generation length of the ShareGPT dataset is more challenging. Consequently, our predictor performs less effectively on the ShareGPT dataset.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YsfJfUAGp3", "reviewer": "Reviewer_GoTD", "summary": "This paper reveals the Head-of-Line (HOL) blocking problems caused by the first-come-first-serve (FCFS) scheduling strategy in LLM services. To alleviate these problems, the authors train an OPT model to generate scores for evaluating the relative text length of given prompts. Based on these scores, the authors develop a novel scheduler for LLM inference and serving. Experimental results demonstrate the effectiveness of the proposed method, significantly outperforming the baseline method.", "questions": "1. Could you give a more detailed analysis of the relationship between ListMLE loss and Kendall’s Tau coefficient?\n2. Are all the last hidden states of the OPT model used to map to a score, or are only specific hidden states of a token used? Using a decoder-only model to extract features of a text seems unusual.", "limitations": "See weaknesses and Questions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method is efficient and effective. Training a small language model (i.e., a 125M OPT model) is cheap, and the resulting latency gains are substantial.\n2. This paper is novel. Unlike traditional methods that predict the real generation length, predicting the relative ordering between request lengths is sufficient for ranking.", "weaknesses": "1. Since the request queue Q is re-ranked after each batch of data is scored, the ranking scheduler may be sensitive to the batch size.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful and helpful feedback! We address all your questions and concerns below.\n\n**Q1: Since the request queue Q is re-ranked after each batch of data is scored, the ranking scheduler may be sensitive to the batch size.**\n\n**A1:** The ranking scheduler is not sensitive to the batch size. We compare the sensitivity of the scheduler to the batch size as follows. We use the predictor to compute tau with different batch sizes and obtain the mean and variance across the entire test set.\n\n| Batch size  | Kendall's Tau mean | Kendall's Tau variance | \n|  ----  | ----  | ----  |\n| 8 | 0.619 | 0.04 |\n| 16 | 0.625 | 0.02 | \n| 32 | 0.624 | 0.008 | \n| 64 | 0.625 | 0.0007 |\n| 128 | 0.619 | 0.001 |\n\nWith different batch sizes, Kendall’s Tau maintains a small range. Additionally, our method addresses severe head-of-line (HOL) problems when there are numerous requests, in which case, the batch size is often sufficiently large for the predictor to be effective and robust.\n\n**Q2: Could you give a more detailed analysis of the relationship between ListMLE loss and Kendall’s Tau coefficient?**\n\n**A2:** ListMLE loss and Kendall’s Tau coefficient are highly negatively correlated. We demonstrate this relationship by recording Tau and loss during the training process. The Pearson correlation coefficient is -0.9:\n\n| Step  | Tau  | Loss  |\n|  ----  | ----  | ----  |\n| 20 | 0.44 | 77.79 |\n| 40 | 0.51 | 75.73 |\n| 60 | 0.53 | 72.61 |\n| 80 | 0.54 | 70.14 |\n| 100 | 0.55 | 70.59 |\n| 120 | 0.53 | 70.09 |\n| 140 | 0.56 | 67.01 |\n| 160 | 0.59 | 69.94 |\n| 180 | 0.59 | 70.88 |\n| 200 | 0.57 | 68.84 |\n| 220 | 0.59 | 68.67 |\n| 240 | 0.61 | 66.90 |\n| 260 | 0.58 | 67.23 |\n| 280 | 0.56 | 68.71 |\n \n\n**Q3: Are all the last hidden states of the OPT model used to map to a score, or are only specific hidden states of a token used? Using a decoder-only model to extract features of a text seems unusual.**\n\n**A3:** We use the last token’s hidden states of the OPT model for two reasons. \n\nFirst, the OPT model provides similar performance compared to the encoder model DistilBert, as shown in the following evaluation:\n\n| Kendall’s Tau (↑) | OPT | DistilBert |\n|  ----  | ----  | ----  |\n| ShareGPT | 0.54 | 0.52 |\n| Lmsys | 0.62 | 0.62 |\n \nSecond, the hidden states of the last token of a decoder model have been previously shown to be predictive of text features. For example, Representation Engineering [1] demonstrates that we can extract attributes such as honesty, emotions, fairness, and more from the hidden states of the last token of the decoder model.\n\n\n\n[1] Zou, Andy, et al. \"Representation engineering: A top-down approach to ai transparency.\" arXiv preprint arXiv:2310.01405 (2023).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "negzB006px", "reviewer": "Reviewer_GSuM", "summary": "This paper proposes an approach for optimizing scheduling in LLM  serving by learning a generated token length ranking model. The authors demonstrate that understanding the relative order of generation lengths can effectively guide the scheduling process, specifically through the use of SJF/ SRTF scheduling strategies.", "questions": "This paper only considers the generated length, which may affect the execution time for each query. However, prompt length also influences execution time. Wouldn't it be more reasonable to also take prompt length into consideration?", "limitations": "see weakness above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written, making the methodology and results clear and easy to understand.\n2. The experiments are well-designed and convincingly demonstrate the benefits of the proposed approach.\n3. The proposed method has shown practical improvements when integrated with current serving techniques.", "weaknesses": "1. While the approach is effective, it builds upon existing work that has already identified the benefits of SJF/SRTF scheduling for LLMs[1][2]. The novelty is somewhat limited to the application of ranking loss instead of classification loss.\n2. If we directly predict the token length, it could potentially offer advantages such as improved memory allocation and cache strategy adjustments, which are also crucial for optimizing LLM serving. In contrast, using relative order may not provide these benefits.\n3. The paper lacks a thorough discussion of some related work,  such as [1][2]\n\n[1] Efficient Interactive LLM Serving with Proxy Model-based Sequence Length Prediction\n\n[2] Power-aware Deep Learning Model Serving with µ-Serve", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the very insightful and helpful comments! We would like to address your questions in the below response.\n\n**Q1: While the approach is effective, it builds upon existing work that has already identified the benefits of SJF/SRTF scheduling for LLMs[1][2]. The novelty is somewhat limited to the application of ranking loss instead of classification loss.**\n\nWe argue that our work presents the following novelties:\n\nFirst, recognizing the importance of relative length ranking instead of accurate token length after the introduction of paged memory allocation (proposed by [3]) is novel.\n\nSecond, employing learning-to-rank to optimize the prediction is novel and outperforms previous methods.\n\nThird, the consideration of the fairness metric in LLM serving and starvation prevention is novel.\n\n**Q2: If we directly predict the token length, it could potentially offer advantages such as improved memory allocation and cache strategy adjustments, which are also crucial for optimizing LLM serving. In contrast, using relative order may not provide these benefits.**\n\nPredicting the number of output tokens may aid in more precise memory allocation, but we observe that in the presence of paged memory allocation (as proposed by vllm[3] and populated in all current LLM serving systems), the benefit diminishes, as paged attention reduces memory waste to as low as 5%.\nDespite memory allocation, knowing the exact number of output tokens in advance may reduce the likelihood of preemptions caused by kv-cache overrun. However, we found that this preemption cost can largely be mitigated (e.g., see FastServe[4]). Therefore, we pursue relative ranking prediction, which is a simpler task but suffices for approximating optimal scheduling.\n\n**Q3: The paper lacks a thorough discussion of some related work, such as [1][2]**\n\nWe will include discussions with [1][2] in the related work section in a revised version. [1][2] are both concurrent works that use predictors to approximate SJF/SRTF. Both [1][2] propose a regression-based method for length prediction, fine-tuning a Bert model on the Lmsys-Chat-1M dataset with a regression L1 loss to predict the exact generation length. They tested models ranging from 300M to 3b and applied various batching policies (i.e., no batching, dynamic batching, continuous batching). The proposed method significantly improves latency and throughput under these settings. Additionally, it supports multi-round LLM conversations. Unlike this method, our proposed method is built on vLLM with paged attention and uses ranking loss to optimize the predictor model. We designed a preemptive scheduling method with starvation prevention to optimize the end-to-end performance of real-world LLM serving systems.\n\n**Q4: This paper only considers the generated length, which may affect the execution time for each query. However, prompt length also influences execution time. Wouldn't it be more reasonable to also take prompt length into consideration?**\n\nConsidering prompt length is indeed a nice suggestion, which we have previously considered, but we found that in practice, focusing only on generated length is simple yet sufficiently effective.\n\nFirst, we observe from lmsys-chat-1m and ShareGPT – two traces that represent real-world scenarios – that prompt length is not crucial in generation time. Specifically, the prefill time accounts for only 5% on lmsys-chat-1M and 8% on ShareGPT, respectively, of the entire generation time, indicating they have a minor impact on overall latency. Note that there are already long prompts in the workloads we tested. For example, 1% of all prompts in the ShareGPT dataset exceed 900 tokens.\n\nSecond, although this paper does not particularly focus on long context (e.g., prompt length > 32k tokens), we argue it is relatively straightforward to handle long prompts. Since prompt lengths are always known a priori – it is easy to accurately approximate the latency of the prefill phase via profiling. We can also map the relative ranking of generation length into a length estimation according to the dataset distribution. Then, simply adding prefill time estimation to the current framework together provides an end-to-end generation time approximation for scheduling. \n\n\n[1] Qiu, Haoran, et al. \"Efficient interactive LLM serving with proxy model-based sequence length prediction.\" arXiv preprint arXiv:2404.08509 (2024).\n\n[2] Qiu, Haoran, et al. \"Power-aware Deep Learning Model Serving with μ-Serve.\" 2024 USENIX Annual Technical Conference (USENIX ATC 24). 2024.\n\n[3] Kwon, Woosuk, et al. \"Efficient memory management for large language model serving with pagedattention.\" Proceedings of the 29th Symposium on Operating Systems Principles. 2023.\n\n[4] Wu, Bingyang, et al. \"Fast distributed inference serving for large language models.\" arXiv preprint arXiv:2305.05920 (2023).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vdPGmOC8b7", "reviewer": "Reviewer_JCjf", "summary": "This paper proposes a learning-based rank predictor for scheduling LLM inference to reduce Head-of-Line (HoL) blocking issues, which significantly outperforms state-of-the-art LLM serving systems.", "questions": "Please see the weaknesses above.", "limitations": "Please see the weaknesses above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper addresses an important question in LLM serving.\n2. This paper is easy to follow with a good presentation.\n3. The evaluation results are comprehensive and solid.", "weaknesses": "1. One potential issue with preemptive scheduling for LLM inference is the accumulated unused KV cache. How do you handle them when the GPU reaches the maximum memory limit? \n\n2. How much does the ranking model (OPT) size affect the prediction and throughput performance? For example, what if I use a smaller auxiliary model (OPT-125M) for a larger LLM (LLaMA-70B)?\n\n3. How much is the performance gap between the ranking-based method and Oracle? It would be better if the authors could add such results to provide a performance upper bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive and detailed suggestions. We appreciate your generous comments!\n\n**Q1: One potential issue with preemptive scheduling for LLM inference is the accumulated unused KV cache. How do you handle them when the GPU reaches the maximum memory limit?**\n\nTo address the issue of an increasing size of KV Cache, we will swap the requests to host memory (as vLLM [1] does) if the requests are not in the current step’s running batch (i.e., B in Algorithm 1) and cannot fit in the GPU memory. However, our experiments handling a burst of 2000 requests with a single llama-3-8b model on a 40GB A100 GPU and with a llama-3-70b model on 8 A100 GPUs resulted in almost no swapping using both FCFS and our scheduling, with vLLM’s default setting of a max batch size of 256 requests running simultaneously. This indicates that our method will not incur more preemptions than FCFS. This is because both our method and FCFS have a fixed execution order for all arriving requests at the beginning. However, our baseline MLFQ will adjust the execution order and call thousands of swaps with the same workload.\n\n**Q2: How much does the ranking model (OPT) size affect the prediction and throughput performance? For example, what if I use a smaller auxiliary model (OPT-125M) for a larger LLM (LLaMA-70B)?**\n\nOur results show that the model size has a minor effect on the prediction ability, as indicated in the following table:\n \t\t                                  \n| Kendall’s Tau (↑) | 125m-OPT | 350m-OPT |\n|  ----  | ----  | ---- | \n| ShareGPT | 0.55 | 0.54 |      \n| Lmsys | 0.64 | 0.62 |       \n\nUsing an OPT-350m is more for deployment considerations. The OPT-350m model with 16 attention heads is easy to deploy with 8-way tensor parallelism, as the llama-70b model requires 8-way tensor parallelism, while an opt-125m with 12 attention heads cannot be deployed on 8 GPUs, as discussed in Section 5.1. We deploy the opt-125m predictor only on 1 GPU, requiring the other 7 GPUs to wait when executing the predictor, which is a waste of resources and may lead to performance degradation.\n\n**Q3: How much is the performance gap between the ranking-based method and Oracle? It would be better if the authors could add such results to provide a performance upper bound.**\n\nThe performance gap between the ranking-based method and the Oracle depends on the evaluation dataset. On some datasets, our proposed method can be as good as the Oracle. Due to noise and randomness in the sampling process, we define the Oracle as using sampling results with one seed to guide the schedule of another sampling, which is the best we can achieve knowing one sampling result.\nFor example, tested on the Alpaca dataset and llama3-7b model, our proposed method can be very close to the Oracle regarding Kendall’s Tau and end-to-end latency of a burst of 2K requests. We tested the end-to-end performance on a single A100 80G GPU.\n                    \n| | Tau |  Latency (s/token)\n|  ----  | ----  | ----  |\n| Ours | 0.73 | 0.28 |\n| Oracle | 0.72 | 0.24 |       \n| FCFS | / | 1.36 |\n\nOn datasets like lmsys-chat-1m and ShareGPT, there is still a small gap between the proposed ranking-based method and the Oracle. We present in Table 3 the comparison between the ranking-based method (line Ranking (Ours)) and the Oracle (line Optimal Prediction).\n\n[1] Kwon, Woosuk, et al. \"Efficient memory management for large language model serving with pagedattention.\" Proceedings of the 29th Symposium on Operating Systems Principles. 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper discusses the problem of scheduling different jobs for LLMs, describing a policy to make it more efficient.
Reviewers found the proposed method effective, the problem important, and the paper clear. Concerns regarding overhead, novelty, and sensitivity to the batch size were largely addressed during the rebuttal.
Decision: Accept (poster)