Research map / Large language models / Reasoning and chain of thought
Efficient LLM Scheduling by Learning to Rank
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes learning-to-rank predictors (OPT backbone trained with ListMLE) to rank LLM requests by expected output length, enabling approximate SJF/SRTF scheduling in vLLM that reduces chatbot latency and boosts synthetic data generation throughput.
Problem
LLM serving systems use FCFS scheduling, causing head-of-line blocking because output lengths are assumed unknown in advance; prior length-prediction methods target exact lengths, which is hard and brittle.
Approach
Instead of predicting exact generation lengths, train a small OPT-based scorer with a listwise ListMLE ranking loss to predict the relative ordering of output lengths, and use it for iteration-level SJF/SRTF-like scheduling with starvation prevention inside vLLM.
Key results
- Ranking scheduler reduces mean latency up to 6.9x vs FCFS and 1.5-1.9x vs Perception Only at 64 req/s, with 2.8x lower P90 latency than PO under 2K bursts.
- On synthetic data generation, generates 1k requests 2.4x-6.5x faster than FCFS and increases samples generated in 5 minutes by up to 3.2x.
- Ranking predictor achieves Kendall's Tau of 0.54 (ShareGPT) and 0.62 (LMSYS-Chat-1M) for Llama-3-70B, outperforming classification variants on ranking metrics; predictor overhead is under 2% of prefill-related time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Ranking-based scheduling (learning-to-rank OPT predictor) instead of FCFS | chatbot serving, Llama-3-8B · LMSYS-Chat-1M burst of 2K requests | P90 latency (s/token): 4.86 -> 0.52 | Helped |
| Ranking-based scheduling instead of FCFS | chatbot serving, Llama-3-70B · ShareGPT burst of 2K requests | Mean latency (s/token): 1.44 -> 0.78 | Helped |
| Ranking-based scheduling instead of FCFS | synthetic data generation, Llama-3-70B · ShareGPT, samples generated in 5 min | Samples generated: 670 -> 1299 | Helped |
| Ranking-based scheduling instead of FCFS | synthetic data generation, Llama-3-8B · LMSYS-Chat-1M, time to generate 1k samples | Time (s): 197.38 -> 30.48 | Helped |
| Classification predictor (10 buckets) instead of ranking (ablation) | synthetic data generation, Llama-3-70B · ShareGPT, samples generated in 5 min | Samples generated: 670 -> 479 (vs FCFS) | Hurt |
| Learning-to-rank (ListMLE) predictor instead of classification with 10 buckets (ablation) | OPT predictor, Llama-3-70B · ShareGPT Kendall's Tau | Kendall's Tau: 0.24 -> 0.54 | Helped |
| Classification with larger bucket size (100) instead of 10 buckets (ablation) | OPT predictor, Llama-3-70B · ShareGPT Kendall's Tau | Kendall's Tau: 0.24 -> 0.49 | Helped |
| Classification accuracy increases with bucket size but Kendall's Tau does not track it (ablation) | OPT classification predictor · ShareGPT and LMSYS-Chat-1M | Accuracy vs Kendall's Tau | Mixed |
| Ranking predictor vs PO on LMSYS-Chat-1M Kendall's Tau | OPT ranking predictor vs Perception Only · LMSYS-Chat-1M Kendall's Tau | Kendall's Tau: 0.62 vs 0.67 (PO higher) | Hurt |
| Starvation prevention (max TPOT-based promotion with quantum) (ablation) | ranking scheduler · LMSYS-Chat-1M and ShareGPT, mean max-TPOT fairness metric | Mean max TPOT: reduced by up to 3.4x (LMSYS) and 3.3x (ShareGPT) | Helped |
| Starvation prevention added to ranking scheduler (ablation) | ranking scheduler latency · serving latency | Mean latency overhead: <10% overhead in most cases, <30% in all cases | Hurt |
| Re-predicting scores for already running requests (dynamic correction of mispredictions) (ablation) | ranking scheduler, Llama-3-8B · ShareGPT and LMSYS-Chat-1M latency | Latency (s/token): 0.43 vs 0.44 (ShareGPT); 0.64 vs 0.64 (LMSYS) | No clear effect |
Surprising findings
- Classification-based length predictors (S3-style) fail to beat FCFS in synthetic data generation due to preprocessing overhead and poor short-request recognition.
- Re-predicting scores for already-running requests yields minimal latency improvement.
Limitations
- Kendall's Tau does not fully reflect end-to-end latency; the same tau can yield different latencies depending on where mis-ordering occurs.
- Performance degrades under distribution shift between datasets (e.g., Tau 0.54 to 0.45 or 0.62 to 0.40).
- Integration with chunked prefill and prefill-decode disaggregation not yet studied.
Experimental setup
Datasets: ShareGPT LMSYS-Chat-1M
Benchmarks: ShareGPT LMSYS-Chat-1M Alpaca
Metrics: Kendall's Tau mean per-token latency p90 per-token latency throughput (requests/s) time to generate 1k samples classification accuracy max TPOT fairness
Baselines: FCFS MLFQ Perception Only Classification (S3-style)
Builds on: vLLM ListMLE S3 Perception Only FastServe
Closest papers by meaning
- Fast Inference for Augmented Large Language Models (NeurIPS 2025 · similarity 0.90)
- Beyond Prediction: Tail-Aware Scheduling for LLM Inference (ICML 2026 · similarity 0.90)
- LLM Query Scheduling with Prefix Reuse and Latency Constraints (NeurIPS 2025 · similarity 0.90)
- DON’T STOP ME NOW: EMBEDDING BASED SCHEDULING FOR LLMS (ICLR 2025 · similarity 0.90)
- Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practice (NeurIPS 2026 · similarity 0.89)
- SparQ Attention: Bandwidth-Efficient LLM Inference (ICML 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.