Elamur Research⌕
☰
home / papers / 2024 / Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve

Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve

Paper · 2024 · Amey Agrawal, Nitin Kedia, Ashish Panwar et al.

Summary

Serving LLMs online requires both high throughput, to keep costs down, and low latency between generated tokens. Each request has a compute-heavy prefill over the prompt and a memory-bound decode that produces one token per step. Existing schedulers handle this in one of two ways. Decode-first systems such as FasterTransformer protect latency but waste capacity. Prefill-first systems such as Orca and vLLM batch well but cause "generation stalls," where a long incoming prompt freezes ongoing outputs, sometimes for seconds.

Sarathi-Serve is a scheduler that addresses this with two techniques:

  • Chunked-prefills: prompts are split into roughly equal-cost pieces.
  • Stall-free batching: each iteration combines all active decodes with prefill chunks, up to a fixed token budget.

Because every step does a similar amount of work, iteration time stays bounded and pipeline-parallel micro-batches stay balanced. Compared with vLLM under tail-latency SLOs, serving capacity rises by up to 2.6× for Mistral-7B, 3.7× for Yi-34B and 5.6× for Falcon-180B with pipeline parallelism. The code is open source.

Key points

  • Test setups:
    • Mistral-7B on one A100.
    • Yi-34B on two A100s with 2-way tensor parallelism.
    • LLaMA2-70B on eight A40s.
    • Falcon-180B with 2-way pipeline and 4-way tensor parallelism on eight A100s, linked over ordinary ethernet.
  • Capacity gains over vLLM: up to 2.6× (Mistral-7B), 3.7× (Yi-34B) and 5.6× (Falcon-180B, pipeline-parallel).
  • Chunking overhead: prefill cost grows by at most about 25% with the smallest chunk (512 tokens). The overhead is close to zero with a 2048-token budget.
  • Ablation (Yi-34B, 1024-token budget, openchat_sharegpt4 and arxiv_summarization traces):
    • Hybrid batching alone leaves P99 TBT high (0.68 s and 1.38 s).
    • Chunking alone raises median TTFT.
    • Combining both gives the best balance, with P99 TBT of 0.14 s and 0.17 s.
  • Code: released at github.com/microsoft/sarathi-serve.

Interesting ideas

  • I1. Cap work per step, not requests per batch. A fixed token budget makes each iteration's latency nearly independent of how long incoming inputs are. This could help any streaming system where large jobs share hardware with latency-sensitive small ones.
  • I2. Split large jobs into equal-cost slices. Slicing a big job and mixing the slices with small ongoing tasks prevents head-of-line blocking without delaying the big job much. The same trick could apply to batch tokenization or corpus-processing pipelines.
  • I3. Use uniform batches to reduce pipeline idle time. When every micro-batch costs about the same, multi-stage pipelines waste fewer cycles waiting on each other. This makes pipeline parallelism over cheap interconnects more practical for teams without high-end clusters.
  • I4. Evaluate under tail-latency targets. The paper reports capacity as the load sustainable while meeting a P99 constraint, rather than raw throughput. This gives a more honest comparison for interactive services.
  • I5. Ablate components separately and together. Testing each technique alone and in combination showed that each fixes a different metric (TTFT versus TBT). This is a useful habit when a method has interacting parts.

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

🎓Georgia Institute of TechnologyAtlanta · United States152 works · 27,763 citations🏢Microsoft ResearchBengaluru · India15 works · 4,115 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 worksHardware and Architecture · 167 works

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

Cite

Cite as Amey Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S. Gulavani, Alexey Tumanov and Ramachandran Ramjee. 2024. Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve. OSDI 2024.

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

@inproceedings{agrawal2024taming,
  title = {{Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve}},
  author = {Amey Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S. Gulavani, Alexey Tumanov and Ramachandran Ramjee},
  booktitle = {OSDI 2024},
  year = {2024},
  eprint = {2403.02310},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.02310}
}

References

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

  1. Amazon codewhisperer. https://aws.amazon.com/codewhisperer/. ↗
  2. Anthropic claude. https://claude.ai. ↗
  3. arxiv.org e-print archive. https://arxiv.org/. ↗
  4. Bing ai. https://www.bing.com/chat. ↗
  5. Character ai. https://character.ai. ↗
  6. Chatgpt. https://chat.openai.com. ↗
  7. Faster Transformer. https://github.com/NVIDIA/FasterTransformer. ↗
  8. Github copilot. copilot. https://github.com/features/ ↗
  9. Google bard. https://bard.google.com. ↗
  10. Google duet ai. https://workspace.google.com/solutions/ai/. ↗
  11. Komo. https://komo.ai/. ↗
  12. Lightllm: A light and fast inference service for llm. https://github.com/ModelTC/lightllm. ↗
  13. Matrix multiplication background user’s https://docs.nvidia.com/deeplearning/performance/dl-performance-matrix-multiplication/index.html. guide. ↗
  14. Microsoft copilot. https://www.microsoft.com/en-us/microsoft-copilot. ↗
  15. Nvidia collective communications library (nccl). https://developer.nvidia.com/nccl. ↗
  16. Nvidia dgx platform. https://www.nvidia.com/en-us/data-center/dgx-platform/. ↗
  17. NVIDIA Triton Dynamic Batching. https://docs.nvidia.com/deeplearning/triton-inference-server/user-guide/docs/user_guide/model_configuration.html\#dynamic-batcher. ↗
  18. Openai gpt-3: Understanding the architecture. https://www.theaidream.com/post/openai-gpt-3-understanding-the-architecture. ↗
  19. Perplexity ai. https://www.perplexity.ai/. ↗
  20. Replit ghostwriter. ghostwriter. https://replit.com/site/ ↗
  21. Tensorrt-llm: A tensorrt toolbox for optimized large language model inference. https://github.com/NVIDIA/TensorRT-LLM. ↗
  22. Using NVIDIA’s AI/ML Frameworks for Generative AI on VMware vSphere. https://core.vmware.com/blog/using-nvidias-aiml-frameworks-generative-ai-vmware-vsphere. ↗
  23. vllm: Easy, fast, and cheap llm serving for everyone. https://github.com/vllm-project/vllm. ↗
  24. Yi series of large language models trained from scratch by developers at 01.AI. https://huggingface.co/01-ai/Yi-34B-200K. ↗
  25. You.com. https://you.com/. ↗
  26. Reyna Abhyankar, Zijian He, Vikranth Srivatsa, Hao Zhang, and Yiying Zhang. Apiserve: Efficient api support for large-language model inferencing. arXiv preprint arXiv:2402.01869, 2024. find
  27. Abien Fred Agarap. Deep learning using rectified linear units (relu), 2019. find
  28. Amey Agrawal, Nitin Kedia, Jayashree Mohan, Ashish Panwar, Nipun Kwatra, Bhargav S Gulavani, Ramachandran Ramjee, and Alexey Tumanov. Vidur: A large-scale simulation framework for llm inference. Proceedings of The Seventh Annual Conference on Machine Learning and Systems, 2024, Santa Clara, 2024.
  29. Amey Agrawal, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S. Gulavani, and Ramachandran Ramjee. Sarathi: Efficient llm inference by piggybacking decodes with chunked prefills, 2023.
  30. Joshua Ainslie, James Lee-Thorp, Michiel de Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sanghai. Gqa: Training generalized multi-query transformer models from multi-head checkpoints, 2023.
  31. Ebtesam Almazrouei, Hamza Alobeidli, Abdulaziz Alshamsi, Alessandro Cappelli, Ruxandra Cojocaru, Mérouane Debbah, Étienne Goffinet, Daniel Hesslow, Julien Launay, Quentin Malartic, Daniele Mazzotta, Badreddine Noune, Baptiste Pannier, and Guilherme Penedo. The falcon series of open language models,…
  32. Mikel Artetxe, Shruti Bhosale, Naman Goyal, Todor Mihaylov, Myle Ott, Sam Shleifer, Xi Victoria Lin, Jingfei Du, Srinivasan Iyer, Ramakanth Pasunuru, Giri Anantharaman, Xian Li, Shuohui Chen, Halil Akin, Mandeep Baines, Louis Martin, Xing Zhou, Punit Singh Koura, Brian O’Horo, Jeff Wang, Luke Zettle… — Efficient Large Scale Language Modeling with Mixtures of Experts
  33. Sanjith Athlur, Nitika Saran, Muthian Sivathanu, Ramachandran Ramjee, and Nipun Kwatra. Varuna: scalable, low-cost training of massive deep learning models. In Proceedings of the Seventeenth European Conference on Computer Systems, pages 472–487, 2022. find
  34. 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.
  35. Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emi… — PaLM: Scaling Language Modeling with Pathways
  36. Arman Cohan, Franck Dernoncourt, Doo Soon Kim, Trung Bui, Seokhwan Kim, Walter Chang, and Nazli Goharian. A discourse-aware attention model for abstractive summarization of long documents. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Lingui…
  37. 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, 2017. find
  38. Tri Dao. Flashattention-2: Faster attention with better parallelism and work partitioning, 2023.
  39. Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness, 2022. find
  40. Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer. Llm.int8(): 8-bit matrix multiplication for transformers at scale, 2022. find
  41. Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. Qlora: Efficient finetuning of quantized llms, 2023.
  42. Jiarui Fang, Yang Yu, Chengduo Zhao, and Jie Zhou. Turbotransformers: an efficient GPU serving system for transformer models. In PPoPP ’21: 26th ACM SIG-PLAN Symposium on Principles and Practice of Parallel Programming, Virtual Event, Republic of Korea, February 27- March 3, 2021, pages 389–402. ACM… find
  43. Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. Gptq: Accurate post-training quantization for generative pre-trained transformers, 2023. find
  44. Pin Gao, Lingfan Yu, Yongwei Wu, and Jinyang Li. Low latency rnn inference with cellular batching. In Proceedings of the Thirteenth EuroSys Conference, EuroSys ’18, New York, NY, USA, 2018. Association for Computing Machinery. find
  45. 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
  46. Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (gelus), 2023. find
  47. 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 llm inference for mixed downstream workloads. arXiv preprint arXiv:2401.11181, 2024. — [arXiv:2401.11181](https://arxiv.org/abs/2401.11181) find
  48. Haiyang Huang, Newsha Ardalani, Anna Sun, Liu Ke, Hsien-Hsin S. Lee, Anjali Sridhar, Shruti Bhosale, Carole-Jean Wu, and Benjamin Lee. Towards moe deployment: Mitigating inefficiencies in mixture-of-expert (moe) inference, 2023. find
  49. Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Dehao Chen, Mia Chen, HyoukJoong Lee, Jiquan Ngiam, Quoc V Le, Yonghui Wu, et al. Gpipe: Efficient training of giant neural networks using pipeline parallelism. Advances in neural information processing systems, 32, 2019. find
  50. Abhinav Jangda, Jun Huang, Guodong Liu, Amir Hossein Nodehi Sabet, Saeed Maleki, Youshan Miao, Madanlal Musuvathi, Todd Mytkowicz, and Olli Saarikivi. Breaking the computation and communication abstraction barrier in distributed machine learning workloads. In Proceedings of the 27th ACM Internationa… find
  51. Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint arXiv:2310.06825, 2023. find
  52. Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. CoRR, abs/2001.08361, 2020.
  53. 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. SOSP ’23, page 611–626, New York, NY, USA, 2023. Association for Computing Machinery.
  54. Jiamin Li, Yimin Jiang, Yibo Zhu, Cong Wang, and Hong Xu. Accelerating distributed MoE training and inference with lina. In 2023 USENIX Annual Technical Conference (USENIX ATC 23), pages 945–959, Boston, MA, July 2023. USENIX Association.
  55. Deepak Narayanan, Aaron Harlap, Amar Phanishayee, Vivek Seshadri, Nikhil R Devanur, Gregory R Ganger, Phillip B Gibbons, and Matei Zaharia. Pipedream: generalized pipeline parallelism for dnn training. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, pages 1–15, 2019. find
  56. Christopher Olston, Noah Fiedel, Kiril Gorovoy, Jeremiah Harmsen, Li Lao, Fangwei Li, Vinu Rajashekhar, Sukriti Ramesh, and Jordan Soyke. Tensorflow-serving: Flexible, high-performance ml serving, 2017. find
  57. OpenAI. GPT-4 technical report. abs/2303.08774, 2023. CoRR,
  58. Pratyush Patel, Esha Choukse, Chaojie Zhang, Íñigo Goiri, Aashaka Shah, Saeed Maleki, and Ricardo Bianchini. Splitwise: Efficient generative llm inference using phase splitting, 2023.
  59. 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
  60. Markus N. Rabe and Charles Staats. Self-attention does not need o(n 2 ) memory, 2022. find
  61. Noam Shazeer. Fast transformer decoding: One write-head is all you need, 2019. find
  62. Ying Sheng, Shiyi Cao, Dacheng Li, Banghua Zhu, Zhuohan Li, Danyang Zhuo, Joseph E Gonzalez, and Ion Stoica. Fairness in serving large language models. arXiv preprint arXiv:2401.00588, 2023. find
  63. Ying Sheng, Lianmin Zheng, Binhang Yuan, Zhuohan Li, Max Ryabinin, Daniel Y. Fu, Zhiqiang Xie, Beidi Chen, Clark Barrett, Joseph E. Gonzalez, Percy Liang, Christopher Ré, Ion Stoica, and Ce Zhang. Flexgen: High-throughput generative inference of large language models with a single gpu, 2023.
  64. Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. Megatron-lm: Training multi-billion parameter language models using gpu model parallelism. arXiv preprint arXiv:1909.08053, 2019. find
  65. Yutao Sun, Li Dong, Shaohan Huang, Shuming Ma, Yuqing Xia, Jilong Xue, Jianyong Wang, and Furu Wei. Retentive network: A successor to transformer for large language models, 2023.
  66. 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
  67. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing…
  68. Guan Wang, Sijie Cheng, Xianyuan Zhan, Xiangang Li, Sen Song, and Yang Liu. Openchat: Advancing open-source language models with mixed-quality data, 2023.
  69. Shibo Wang, Jinliang Wei, Amit Sabne, Andy Davis, Berkin Ilbeyi, Blake Hechtman, Dehao Chen, Karthik Srinivasa Murthy, Marcello Maggioni, Qiao Zhang, Sameer Kumar, Tongfei Guo, Yuanzhong Xu, and Zongwei Zhou. Overlap communication with dependent computation via decomposition in large deep learning m… find
  70. Xiaohui Wang, Ying Xiong, Yang Wei, Mingxuan Wang, and Lei Li. LightSeq: A high performance inference library for transformers. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies: Industry Papers (NAACL-HL… find
  71. Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. Emergent abilities of large language models. Trans. Mach. Learn. Res.…
  72. Bingyang Wu, Yinmin Zhong, Zili Zhang, Gang Huang, Xuanzhe Liu, and Xin Jin. Fast distributed inference serving for large language models, 2023.
  73. Guangxuan Xiao, Ji Lin, Mickael Seznec, Hao Wu, Julien Demouth, and Song Han. Smoothquant: Accurate and efficient post-training quantization for large language models, 2023. find
  74. Zihao Ye, Lequn Chen, Ruihang Lai, Yilong Zhao, Size Zheng, Junru Shao, Bohan Hou, Hongyi Jin, Yifei Zuo, Liangsheng Yin, Tianqi Chen, and Luis Ceze. Accelerating self-attentions for llm serving with flashinfer, February 2024. find
  75. 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.
  76. Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Tianle Li, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zhuohan Li, Zi Lin, Eric. P Xing, Joseph E. Gonzalez, Ion Stoica, and Hao Zhang. Lmsys-chat-1m: A large-scale real-world llm conversation dataset, 2023.
  77. Yinmin Zhong, Shengyu Liu, Junda Chen, Jianbo Hu, Yibo Zhu, Xuanzhe Liu, Xin Jin, and Hao Zhang. Distserve: Disaggregating prefill and decoding for goodput-optimized large language model serving, 2024.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/agrawal-2024-taming-throughput-latency-tradeoff-llm/