Efficient LLM Scheduling by Learning to Rank

• FCFS can let a long request block shorter ones, whereas SJF/SRTF minimize average latency but require ordering requests by remaining generation length.The paper identifies unknown generation lengths as the main obstacle to applying these schedules in LLM services.Source: §1 · p. 1, Figure 1 · p. 2
• Relative generation-length ordering is sufficient for approximating SJF/SRTF, so exact output-length prediction is unnecessary.Kendall’s Tau measures similarity between a predicted schedule and the oracle SJF/SRTF schedule, with higher similarity generally associated with lower latency.Source: §1 · pp. 1–2
• Learning to rank trains a small auxiliary model to rank requests before execution and enables on-the-fly scheduling with negligible overhead.The method is designed for both offline batch generation and online latency-sensitive tasks.Source: §1 · pp. 1–2
• The scheduler is simple to integrate into production serving systems and uses predicted rankings to reduce average latency and improve throughput.The implementation is reported as requiring 500 LoC in vLLM.Source: §1 · p. 2
• 2.8× lower p90 latency in chatbot serving and 6.5× higher throughput in batch synthetic data generation result from integrating the method with a state-of-the-art serving system.The reported improvements cover online latency-sensitive serving and offline batch generation.Source: §1 · p. 2

• Orca and vLLM provide important LLM-serving techniques but apply FCFS and remain prone to severe HOL blocking.Other serving optimizations typically assume output length cannot be known before execution.Source: §2 · p. 2
• FastServe uses skip-join MLFQ with priorities based on generated length so far, while Andes uses preemptive scheduling guided by a quality-of-experience objective.These methods differ from predicting the final generation-length ranking before or during scheduling.Source: §2 · p. 2
• SJF and SRTF prioritize jobs with the shortest completion time and provably minimize average latency, although they may suffer from starvation.The paper discusses starvation prevention separately for these scheduling policies.Source: §2 · p. 2
• Existing generation-length methods formulate exact-length prediction as classification or regression, making performance depend on predictive accuracy.Examples include Perception Only, S3, TetriServe, DynamoLLM, Magnus, and concurrent regression-based methods.Source: §2 · pp. 2–3

Kendall Rank Correlation Coefficient

• Kendall’s Tau measures correlation between two rankings, ranging from −1 for reversed rankings to 1 for identical rankings.Source: §3 · p. 3
• The coefficient distinguishes concordant and discordant pairs, with tied pairs counted as neither.Source: §3 · p. 3

Learning to Rank

• Learning to rank applies machine learning to supervised ranking data through pointwise, pairwise, or listwise formulations.Source: §3 · p. 3

ListMLE

• ListMLE minimizes the negative log-likelihood of the ground-truth permutation, encouraging the model to predict a ranking close to the true ranking.Source: §3 · p. 3
• ListMLE’s list-ranking objective aligns with Kendall’s Tau, so minimizing the loss can improve ranking correlation.Source: §3 · p. 4

4.1 Problem Formulation

• The method predicts each request’s generation-length rank rather than its exact length and evaluates predictions with Kendall’s Tau against the oracle ranking.Source: §4.1 · p. 4

4.2 Generation Length Ranking Predictor

• A small OPT-based predictor scores prompts, and the scheduler sorts requests by predicted rankings to form batches under memory or batch-size constraints.Source: §4.2 · p. 4, §4.3 · p. 5
• A linear layer maps the OPT model’s final hidden states to floating-point scores used for ranking prompts.Source: §4.2 · p. 4
• The predictor is trained from full target-LLM generations, whose token lengths are converted into ranking labels; lengths are bucketed in increments of 10 to reduce sampling noise.Source: §4.2 · p. 4
• Listwise ranking focuses on ordering rather than precise bucket classification, improving robustness when output-length buckets are uneven.Source: §4.2 · pp. 4–5

4.3 Request Scheduling with Rankings

• The scheduler prevents starvation by promoting requests whose starvation counts reach a threshold, assigning priority quantum before later demotion.Source: §4.3 · pp. 5–6
• The fairness metric max_waiting_time combines TTFT and TPOT to characterize the longest interval between tokens received after a request is submitted.Source: §4.3 · p. 6

Evaluation Overview

• 2.8× lower latency in chatbot serving and 6.5× higher throughput in synthetic data generation demonstrate state-of-the-art end-to-end performance.The evaluation uses Llama-3 models, ShareGPT and LMSYS-Chat-1M workloads, and latency or throughput metrics appropriate to each task.Source: §5 · p. 6, §5.1 · p. 6

5.2 Chatbot Serving Scheduling

• 6.9× lower mean latency than FCFS at 64 requests/second, and 1.5×–1.9× lower latency than PO, show the ranking method’s chatbot advantage.MLFQ and PO incur Head-Of-Line blocking while obtaining scheduling information, whereas the OPT predictor adds less than 2% overhead.Source: §5.2 · p. 7, Figure 3 · p. 7

5.3 Synthetic Data Generation Scheduling

• 2.4×–6.5× reductions in generation time show that ranking improves synthetic-data throughput by selecting short requests more effectively than classification.Classification can fail to surpass FCFS because of OPT preprocessing cost and weak recognition of short requests; improvements are minor when short generations are not preferred.Source: §5.3 · p. 8

5.4 Comparing Ranking Predictors

• Larger classification buckets improve accuracy but do not necessarily improve Kendall’s Tau, latency, or synthetic-generation time.End-to-end performance is more closely related to ranking quality than classification accuracy, while PO can achieve higher Kendall’s Tau on LMSYS-Chat-1M but incurs substantial HOL overhead.Source: §5.4 · p. 8

5.5 Effectiveness Analysis

• 3.4× lower mean max_waiting_time on LMSYS-Chat-1M and 3.3× lower on ShareGPT result from starvation prevention, with under 10% latency overhead in most cases.The predictor’s overhead is below 2% in all settings, although performance degradation under distribution shifts may require periodic retraining.Source: §5.4 · p. 8, §5.5 · p. 9

• Kendall’s Tau can assign the same score to rankings with substantially different latency, limiting its reliability as an end-to-end performance proxy.A Kendall’s Tau of 0.5 can correspond to a 1.8× latency difference for Llama-8B on ShareGPT when the shortest and longest predictions are shuffled differently.Source: §6 · p. 9
• The proposed scheduler currently supports continuous batching and paged attention, but integration with chunk-prefill and prefill-decode disaggregation remains future work.Source: §6 · p. 9

• 2.8× lower chatbot latency and 6.5× higher synthetic-data-generation throughput are achieved across the evaluated tasks.Source: §7 · p. 10
• The method applies learning to rank to predict generation-length orderings and implements the resulting scheduler on top of vLLM.Source: §7 · p. 10
• The paper argues that the method’s simplicity and low cost could support incorporation into production LLM serving systems.Source: §7 · p. 10

A Implementation of MLFQ

• MLFQ validation uses a burst of 1k requests with a 16-second base quantum, growth rate 2, and at most 256 requests per scheduler step.Source: A Implementation of MLFQ · p. 14, Figure 6 · p. 14
• Priority queues appear as adjacent rectangular blocks whose edge lengths grow exponentially with the quantum growth rate.Source: A Implementation of MLFQ · p. 14, Figure 6 · p. 14
• Requests that finish exhibit linearly increasing output lengths over time, while timeout at a queue quantum causes simultaneous demotion of co-arriving requests.Source: A Implementation of MLFQ · p. 14
• The per-step request limit acts as a sliding window, allowing lower-priority requests to run when higher-priority queues cannot fill it.Source: A Implementation of MLFQ · p. 14

B Dataset Length Distribution

• ShareGPT averages 240 input tokens versus 85 for LMSYS-Chat-1M, with approximately 100 more output tokens.Source: B Dataset Length Distribution · p. 15, Figure 7 · p. 15
• The 70B version of Llama-3 produces approximately 15 more output tokens on average.Source: B Dataset Length Distribution · p. 15
• Kendall’s Tau remains within a narrow range across batch sizes on LMSYS-Chat-1M, indicating limited predictor sensitivity to batch-size variation.Source: C Predictor’s Sensitivity to Batch Size · p. 15, Table 5 · p. 16

• Kendall’s Tau measures ranking similarity through concordant and discordant item pairs, with τ determined by their difference relative to all pairs.The simplified formulation assumes no ties between items.Source: D Relationship Between the ListMLE… · p. 16
• Minimizing ListMLE loss can improve Kendall’s Tau because higher ground-truth ranking likelihood generally increases concordant pairs and reduces discordant pairs.The passage qualifies this as a general tendency rather than a guarantee.Source: D Relationship Between the ListMLE… · p. 16
• A Pearson correlation of -0.9 shows that ListMLE loss and Kendall’s Tau are highly negatively correlated during training.The relationship is illustrated by tracking both quantities throughout training.Source: D Relationship Between the ListMLE… · p. 16, Table 6 · p. 16

E The Performance Gap Between The Proposed Method and Oracle

• The ranking-based method can perform as well as the Oracle on some datasets, while a small gap remains on LMSYS-Chat-1M and ShareGPT.The Oracle uses one sampling seed’s results to guide scheduling for another seed, representing the best performance achievable from one sampling result.Source: E The Performance Gap Between The… · p. 17, Table 7 · p. 17

F Influence of The Predictor Size

• Model size has a minor effect on prediction ability, supporting the use of a smaller predictor when deployment constraints matter.The OPT-350m predictor is selected for compatibility with 8-way tensor parallelism, whereas OPT-125m would leave seven GPUs waiting during prediction.Source: F Influence of The Predictor Size · p. 17

G Consideration of Ignoring The Prompt Length

• In tested real-world traces, prompt prefill accounts for only 5% on Imsys-chat-1M and 8% on ShareGPT of total generation time.The paper therefore treats prompt length as a minor factor in overall latency, while noting that it does not specifically focus on prompts longer than 32k tokens.Source: G Consideration of Ignoring The Prompt… · p. 17

• The scheduler uses preemptive ranking comparisons for new and running requests, but re-predicting already executed requests offers minimal improvement.This finding is reported from experiments summarized in Table 9.Source: H Influence of Correcting… · p. 18, Table 9 · p. 18