Elamur Research⌕
☰
home / papers / 2024 / Llumnix: Dynamic Scheduling for Large Language Model Serving

Llumnix: Dynamic Scheduling for Large Language Model Serving

Paper · 2024 · Biao Sun, Ziming Huang, Hanyu Zhao et al.

Summary

Requests to a served LLM vary widely in prompt length, output length and latency needs. Neither their run time nor their KV-cache memory growth is known in advance. Dispatching each request once, with policies inherited from classic DNN serving, therefore causes preemptions, queuing delays, memory fragmentation across instances and no way to favour urgent traffic. Llumnix, from Alibaba, is a scheduling layer over vLLM that keeps moving running requests between model instances, much as an operating system shifts processes across CPU cores. Its live migration copies a request's KV cache while decoding continues, so downtime stays near zero regardless of sequence length. A distributed scheduler runs a single load-balancing policy over a "virtual usage" of memory, which handles balancing, de-fragmentation, prioritisation and auto-scaling together. On a 16-GPU cluster it cuts tail latencies by up to an order of magnitude versus INFaaS, speeds up high-priority requests by 1.5× and saves up to 36% in cost at similar tail latency. This matters for anyone sharing LLM endpoints across mixed workloads.

Key points

  • Compared with INFaaS on a 16-GPU cluster with realistic workloads, Llumnix reduces P99 latency to the first token by as much as 15× and P99 latency per generated token by as much as 2×.
  • It accelerates high-priority requests by 1.5×. It also delivers about 36% cost savings while keeping tail latencies comparable.
  • The paper illustrates the memory pressure with LLaMA-2-13B:
    • A full 4k-token sequence needs roughly 3.2 GB of KV cache.
    • The model weights alone take 26 GB.
    • Reserving maximum-length memory per request is therefore impractical, and engines such as vLLM (PagedAttention) allocate KV-cache blocks dynamically instead.
  • Migration exploits the append-only nature of the KV cache and is inspired by VM live migration. Most of the transfer overlaps with ongoing token generation.
  • The code is public at github.com/AlibabaPAI/llumnix.

Interesting ideas

  • I1. Rescheduling after dispatch. Instead of trying to make a perfect placement decision when a request arrives, the system corrects placements at runtime. This fits any setting where job size only becomes clear during execution, such as long batch annotation or crawling jobs.
  • I2. Live migration of growing state. The bulk of the state is copied while work continues, and only the small remaining tail is transferred during a brief pause. Because the state is append-only, the cost of moving a job no longer depends on its size, which makes the trick reusable for other incremental caches or logs.
  • I3. "Virtual usage" as one control knob. Several goals are expressed by inflating or deflating a request's apparent memory footprint, and a plain load balancer then acts on those numbers. Examples are reserving headroom for urgent requests and pushing load off instances that are being terminated. Folding many objectives into one adjusted metric keeps the scheduler simple and extensible.
  • I4. The OS analogy as a design lens. Treating the serving cluster like a multi-core OS imports familiar notions such as isolation, priorities and context switching. These give clear vocabulary and well-understood tradeoffs, like packing versus spreading, when designing infrastructure for new workloads.
  • I5. Evaluating with tail latency and cost together. Reporting P99 first-token and per-token latency alongside cost at equal tail latency shows benefits that averages would hide. This is a good template for evaluating any shared inference service.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🏢Alibaba GroupHangzhou · China201 works · 17,172 citations

 Fields, topics and concepts

📚 Shelves 3The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksInformation Systems · 1,730 worksComputer Networks and Communications · 100 works

🧭 Topics 2Research subjects and languages the work is about.Language models & pretraining · 3,894 worksEfficient models & compression · 297 works

Cite

Cite as Biao Sun, Ziming Huang, Hanyu Zhao, Wencong Xiao, Xinyi Zhang, Yong Li and Wei Lin. 2024. Llumnix: Dynamic Scheduling for Large Language Model Serving. OSDI 2024.

The paper itself, not this page. BibTeX from the library's record of the work. arXiv 2406.03243

@inproceedings{sun2024llumnix,
  title = {{Llumnix: Dynamic Scheduling for Large Language Model Serving}},
  author = {Biao Sun, Ziming Huang, Hanyu Zhao, Wencong Xiao, Xinyi Zhang, Yong Li and Wei Lin},
  booktitle = {OSDI 2024},
  year = {2024},
  eprint = {2406.03243},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2406.03243}
}

References

68 references, 16 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Nccl, https://developer.nvidia.com/nccl/. ↗
  2. Chatgpt plus, 2023. chatgpt-plus. https://openai.com/blog/https://github.com/ ↗
  3. Code llama, 2023. facebookresearch/codellama. find
  4. Deepspeed-mii, 2023. https://github.com/microsoft/DeepSpeed-MII. ↗
  5. Gloo collective communication library, 2023. https://github.com/facebookincubator/gloo. ↗
  6. Google bard, 2023. https://bard.google.com/. https://github.com/ ↗
  7. Longllama, 2023. CStanKonrad/long_llama. find
  8. Openai chatgpt, 2023. https://chat.openai.com/. ↗
  9. Ray serve, 2023. https://docs.ray.io/en/latest/serve/index.html. ↗
  10. Sharegpt_gpt4, 2023. https://huggingface.co/datasets/shibing624/sharegpt_gpt4. ↗
  11. vllm. 2023. https://github.com/vllm-project/vllm, ↗
  12. Marcelo Amaral, Jordà Polo, David Carrera, Seetharami Seelam, and Malgorzata Steinder. Topology-aware GPU scheduling for learning workloads in cloud environments. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, page 17, New York, NY, U… find
  13. Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, Binyuan Hui, Luo Ji, Mei Li, Junyang Lin, Runji Lin, Dayiheng Liu, Gao Liu, Chengqiang Lu, Keming Lu, Jianxin Ma, Rui Men, Xingzhang Ren, Xuancheng Ren, Chuanqi Tan, Sinan Tan, Jianhong Tu, P… — Qwen Technical Report
  14. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877–1901, 2020.
  15. Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter,… — Language Models are Few-Shot Learners
  16. Quan Chen, Hailong Yang, Minyi Guo, Ram Srivatsa Kannan, Jason Mars, and Lingjia Tang. Prophet: Precise qos prediction on non-preemptive accelerators to improve utilization in warehouse-scale computers. In Proceedings of the Twenty-Second International Conference on Architectural Support for Program… find
  17. Christopher Clark, Keir Fraser, Steven Hand, Jacob Gorm Hansen, Eric Jul, Christian Limpach, Ian Pratt, and Andrew Warfield. Live migration of virtual machines. In Amin Vahdat and David Wetherall, editors, 2nd Symposium on Networked Systems Design and Implementation (NSDI 2005), May 2-4, 2005, Bosto… find
  18. Eli Cortez, Anand Bonde, Alexandre Muzio, Mark Russinovich, Marcus Fontoura, and Ricardo Bianchini. Resource central: Understanding and predicting workloads for improved resource management in large cloud platforms. In Proceedings of the 26th Symposium on Operating Systems Principles, pages 153–167,… find
  19. Daniel Crankshaw, Xin Wang, Guilio Zhou, Michael J. Franklin, Joseph E. Gonzalez, and Ion Stoica. Clipper: A low-latency online prediction serving system. In 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17), pages 613–627, Boston, MA, March 2017. USENIX Association. find
  20. Weihao Cui, Han Zhao, Quan Chen, Hao Wei, Zirui Li, Deze Zeng, Chao Li, and Minyi Guo. DVABatch: Diversity-aware Multi-Entry Multi-Exit batching for efficient processing of DNN services on GPUs. In 2022 USENIX Annual Technical Conference (USENIX ATC 22), pages 183–198, Carlsbad, CA, July 2022. USENI… find
  21. Tri Dao. Flashattention-2: Faster attention with better parallelism and work partitioning. CoRR, abs/2307.08691, 2023.
  22. Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness, 2022. find
  23. Christina Delimitrou and Christos Kozyrakis. Paragon: QoS-aware scheduling for heterogeneous datacenters. In Proceedings of the Eighteenth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’13, page 77–88, New York, NY, USA, 2013. Association f… find
  24. Christina Delimitrou and Christos Kozyrakis. Quasar: resource-efficient and qos-aware cluster management. In Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’14, page 127–144, New York, NY, USA, 2014. Association for C… find
  25. Jiarui Fang, Yang Yu, Chengduo Zhao, and Jie Zhou. Turbotransformers: An efficient gpu serving system for transformer models. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’21, page 389–402, New York, NY, USA, 2021. Association for Computi… find
  26. Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. OPTQ: Accurate quantization for generative pre-trained transformers. In The Eleventh International Conference on Learning Representations, 2023. find
  27. Panagiotis Garefalakis, Konstantinos Karanasos, Peter Pietzuch, Arun Suresh, and Sriram Rao. Medea: scheduling of long running applications in shared production clusters. In Proceedings of the thirteenth EuroSys conference, pages 1–13, 2018. find
  28. Arpan Gujarati, Reza Karimi, Safya Alzayat, Wei Hao, Antoine Kaufmann, Ymir Vigfusson, and Jonathan Mace. Serving {DNNs} like clockwork: Performance predictability from the bottom up. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 443–462, 2020. find
  29. Arpan Gujarati, Reza Karimi, Safya Alzayat, Wei Hao, Antoine Kaufmann, Ymir Vigfusson, and Jonathan Mace. Serving dnns like clockwork: Performance predictability from the bottom up. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 443–462. USENIX Association,… find
  30. Daya Guo, Qihao Zhu, Dejian Yang, Zhenda Xie, Kai Dong, Wentao Zhang, Guanting Chen, Xiao Bi, Y. Wu, Y.K. Li, Fuli Luo, Yingfei Xiong, and Wenfeng Liang. Deepseek-coder: When the large language model meets programming – the rise of code intelligence, 2024. find
  31. Ori Hadary, Luke Marshall, Ishai Menache, Abhisek Pan, Esaias E Greeff, David Dion, Star Dorminey, Shailesh Joshi, Yang Chen, Mark Russinovich, et al. Protean: VM allocation service at scale. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 845–861, 2020. find
  32. Jaeung Han, Seungheun Jeon, Young-ri Choi, and Jaehyuk Huh. Interference management for distributed parallel applications in consolidated clusters. In Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’16, page 4… find
  33. Mingcong Han, Hanze Zhang, Rong Chen, and Haibo Chen. Microsecond-scale preemption for concurrent GPU-accelerated DNN inferences. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), pages 539–558, Carlsbad, CA, July 2022. USENIX Association. find
  34. 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, SOSP ’23, page 611–626,…
  35. Zhuohan Li, Lianmin Zheng, Yinmin Zhong, Vincent Liu, Ying Sheng, Xin Jin, Yanping Huang, Zhifeng Chen, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. AlpaServe: Statistical multiplexing with model parallelism for deep learning serving. In 17th USENIX Symposium on Operating Systems Design and Implem…
  36. Percy Liang, Rishi Bommasani, Tony Lee, Dimitris Tsipras, Dilara Soylu, Michihiro Yasunaga, Yian Zhang, Deepak Narayanan, Yuhuai Wu, Ananya Kumar, Benjamin Newman, Binhang Yuan, Bobby Yan, Ce Zhang, Christian Cosgrove, Christopher D. Manning, Christopher Ré, Diana Acosta-Navas, Drew A. Hudson, Eric… find
  37. Ji Lin, Jiaming Tang, Haotian Tang, Shang Yang, Wei-Ming Chen, Wei-Chen Wang, Guangxuan Xiao, Xingyu Dang, Chuang Gan, and Song Han. Awq: Activation-aware weight quantization for llm compression and acceleration. In MLSys, 2024. find
  38. Hao Liu, Matei Zaharia, and Pieter Abbeel. Ring attention with blockwise transformers for near-infinite context. CoRR, abs/2310.01889, 2023.
  39. Shuming Ma, Hongyu Wang, Lingxiao Ma, Lei Wang, Wenhui Wang, Shaohan Huang, Li Dong, Ruiping Wang, Jilong Xue, and Furu Wei. The era of 1-bit llms: All large language models are in 1.58 bits, 2024. find
  40. Jason Mars, Lingjia Tang, Robert Hundt, Kevin Skadron, and Mary Lou Soffa. Bubble-up: Increasing utilization in modern warehouse scale computers via sensible colocations. In Proceedings of the 44th annual IEEE/ACM International Symposium on Microarchitecture, pages 248–259, 2011. find
  41. Xupeng Miao, Chunan Shi, Jiangfei Duan, Xiaoli Xi, Dahua Lin, Bin Cui, and Zhihao Jia. Spotserve: Serving generative large language models on preemptible instances, 2023.
  42. Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Eric Liang, Melih Elibol, Zongheng Yang, William Paul, Michael I. Jordan, and Ion Stoica. Ray: A distributed framework for emerging AI applications. In 13th USENIX Symposium on Operating Systems Design and Implementation… find
  43. Avanika Narayan, Ines Chami, Laurel J. Orr, and Christopher Ré. Can foundation models wrangle your data? Proc. VLDB Endow., 16(4):738–746, 2022. find
  44. Deepak Narayanan, Mohammad Shoeybi, Jared Casper, Patrick LeGresley, Mostofa Patwary, Vijay Korthikanti, Dmitri Vainbrand, Prethvi Kashinkunti, Julie Bernauer, Bryan Catanzaro, Amar Phanishayee, and Matei Zaharia. Efficient large-scale language model training on gpu clusters using megatron-lm. In Pr… find
  45. NVIDIA. Using multiple nccl communicators concurrently. https://docs.nvidia.com/deeplearning/nccl/user-guide/docs/usage/communicators.html\#using-multiple-nccl-communicators-concurrently. ↗
  46. NVIDIA. Fastertransformer. https://github.com/NVIDIA/FasterTransformer, 2023. ↗
  47. NVIDIA. Triton inference server. https://github.com/triton-inference-server/server, 2023. ↗
  48. OpenAI. Openai api, 2020. https://openai.com/blog/openai-api. ↗
  49. OpenAI. Gpt-4 technical report, 2023.
  50. OpenAI. Gpt-4 turbo. https://help.openai.com/en/articles/8555510-gpt-4-turbo, 2023. ↗
  51. Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F. Christiano, Jan Leike, and Ryan Lowe. Train… — Training language models to follow instructions with human feedback
  52. Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Anselm Levskaya, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. Efficiently scaling transformer inference, 2022. find
  53. Francisco Romero, Qian Li, Neeraja J Yadwadkar, and Christos Kozyrakis. {INFaaS}: Automated model-less inference serving. In 2021 USENIX Annual Technical Conference (USENIX ATC 21), pages 397–411, 2021. find
  54. Haichen Shen, Lequn Chen, Yuchen Jin, Liangyu Zhao, Bingyu Kong, Matthai Philipose, Arvind Krishnamurthy, and Ravi Sundaram. Nexus: A gpu cluster engine for accelerating dnn-based video analysis. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, SOSP ’19, page 322–337, New Yo… find
  55. Ying Sheng, Shiyi Cao, Dacheng Li, Banghua Zhu, Zhuohan Li, Danyang Zhuo, Joseph E. Gonzalez, and Ion Stoica. Fairness in serving large language models, 2023. find
  56. Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism. arXiv preprint arXiv:1909.08053, 2019. find
  57. Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models, 2023.
  58. Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller,… — Llama 2: Open Foundation and Fine-Tuned Chat Models
  59. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pages 6000–6010, 2017.
  60. Abhishek Verma, Luis Pedrosa, Madhukar Korupolu, David Oppenheimer, Eric Tune, and John Wilkes. Large-scale cluster management at Google with Borg. In Proceedings of the Tenth European Conference on Computer Systems, page 18, New York, NY, USA, 2015. ACM. find
  61. Xiaohui Wang, Ying Xiong, Yang Wei, Mingxuan Wang, and Lei Li. Lightseq: A high performance inference library for transformers. In Young-bum Kim, Yunyao Li, and Owen Rambow, editors, Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Hu… find
  62. Yuxin Wang, Yuhan Chen, Zeyu Li, Zhenheng Tang, Rui Guo, Xin Wang, Qiang Wang, Amelie Chi Zhou, and Xiaowen Chu. Towards efficient and reliable llm serving: A real-world workload study, 2024. find
  63. Bingyang Wu, Yinmin Zhong, Zili Zhang, Gang Huang, Xuanzhe Liu, and Xin Jin. Fast distributed inference serving for large language models, 2023.
  64. Wencong Xiao, Romil Bhardwaj, Ramachandran Ramjee, Muthian Sivathanu, Nipun Kwatra, Zhenhua Han, Pratyush Patel, Xuan Peng, Hanyu Zhao, Quanlu Zhang, Fan Yang, and Lidong Zhou. Gandiva: Introspective cluster scheduling for deep learning. In 13th USENIX Symposium on Operating Systems Design and Imple… find
  65. Wenhan Xiong, Jingyu Liu, Igor Molybog, Hejia Zhang, Prajjwal Bhargava, Rui Hou, Louis Martin, Rashi Rungta, Karthik Abinav Sankararaman, Barlas Oguz, Madian Khabsa, Han Fang, Yashar Mehdad, Sharan Narang, Kshitiz Malik, Angela Fan, Shruti Bhosale, Sergey Edunov, Mike Lewis, Sinong Wang, and Hao Ma.… — Effective Long-Context Scaling of Foundation Models
  66. Hailong Yang, Alex Breslow, Jason Mars, and Lingjia Tang. Bubble-flux: precise online qos management for increased utilization in warehouse scale computers. In Proceedings of the 40th Annual International Symposium on Computer Architecture, ISCA ’13, page 607–618, New York, NY, USA, 2013. Associatio… find
  67. Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung-Gon Chun. Orca: A distributed serving system for Transformer-Based generative models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), pages 521–538, Carlsbad, CA, July 2022. USENIX Association.
  68. Hong Zhang, Yupeng Tang, Anurag Khandelwal, and Ion Stoica. SHEPHERD: Serving DNNs in the wild. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23), pages 787–808, Boston, MA, April 2023. USENIX Association. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/sun-2024-llumnix-dynamic-scheduling-large-language/