Efficient LLM Scheduling by Learning to Rank

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.

Strengths

1. This paper addresses an important question in LLM serving. 2. This paper is easy to follow with a good presentation. 3. 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? 2. 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)? 3. 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.

Questions

Please see the weaknesses above.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Please see the weaknesses above.

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.

Strengths

1. The paper is well-written, making the methodology and results clear and easy to understand. 2. The experiments are well-designed and convincingly demonstrate the benefits of the proposed approach. 3. 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. 2. 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. 3. The paper lacks a thorough discussion of some related work, such as [1][2] [1] Efficient Interactive LLM Serving with Proxy Model-based Sequence Length Prediction [2] Power-aware Deep Learning Model Serving with µ-Serve

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?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

see weakness above.

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.

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. 2. 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.

Questions

1. Could you give a more detailed analysis of the relationship between ListMLE loss and Kendall’s Tau coefficient? 2. 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.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

See weaknesses and Questions.

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.

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. The 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? - 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. - 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 - 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?

Questions

1. Why is the improvement on dataset Sharegpt and lmsys different, as shown in table3.

Rating

4

Confidence

4

Soundness

2

Presentation

3

Contribution

2

Limitations

See weakness.