Elamur Research⌕
☰
home / papers / 2023 / Fast Distributed Inference Serving for Large Language Models

Fast Distributed Inference Serving for Large Language Models

Paper · 2023 · Bingyang Wu, Yinmin Zhong, Zili Zhang et al.

Summary

FastServe, from Peking University, is a distributed serving system for large language models that targets the latency of interactive applications. The authors observe that current LLM servers such as Orca and vLLM run each job to completion in arrival order. Because real-world output lengths have a long tail, long jobs hold up short ones. On ShareGPT and Alpaca traces, queuing delay can make up about 90% of end-to-end latency.

FastServe uses the token-by-token nature of generation to allow preemption after any output token. Its scheduler is a skip-join Multi-Level Feedback Queue. Prompt length is known even though output length is not, so the cost of the first (initialization) iteration can be estimated. Each new job is placed directly into the queue that matches this cost. To hold the key-value caches of paused jobs, the system proactively moves them between GPU and host memory. It also supports tensor and pipeline parallelism across GPUs.

Serving OPT-175B on 16 A100 GPUs, FastServe raises throughput over vLLM by up to 31.4× under equal average latency and 17.9× under equal tail latency.

Key points

  • The baselines are Orca (iteration-level scheduling) and vLLM (PagedAttention). Both rely on FCFS run-to-completion, which causes head-of-line blocking. FastServe also implements PagedAttention internally.
  • Workloads come from the ShareGPT and Alpaca datasets, plus fixed-length synthetic jobs. With equal-length jobs, queuing delay stays near zero even at full load. On the skewed real-world traces, it dominates latency.
  • In ablations, skip-join MLFQ beats FCFS by up to 8.9×, naive MLFQ by up to 1.87×, and a Fixed Priority policy by up to 13.9×.
  • Proactive key-value cache swapping was tested on OPT-13B with ShareGPT. It outperforms discarding and recomputing caches by 2.7× and on-demand (reactive) swapping by 1.7×.
  • The main end-to-end experiment serves OPT-175B on 16 NVIDIA A100 GPUs. Against vLLM, throughput improves up to 31.4× at matched average latency and 17.9× at matched tail latency.

Interesting ideas

  • I1. Semi information-agnostic scheduling. The output length is unknown, but the known prompt length still predicts part of the cost, so the scheduler uses it. Partial cost signals like this could guide job placement in other systems where total runtime is uncertain.
  • I2. Skip-join entry into priority queues. A job enters at the priority level that fits its estimated first-step cost instead of always starting at the top. This avoids pointless demotions and could apply to any multi-level queue where the cost of the first stage is predictable.
  • I3. Preemption at natural step boundaries. Generation already proceeds one token at a time, so each token boundary is a cheap point to switch jobs. Other iterative workloads could expose their own step boundaries for fine-grained scheduling.
  • I4. Proactive rather than reactive state swapping. Caches of low-priority jobs are moved out before memory runs out, and caches of soon-to-run jobs are moved back in ahead of time. This overlaps transfers with computation and fits any memory-limited pipeline whose next consumers can be anticipated.
  • I5. Measuring latency as a breakdown. Splitting total latency into queuing delay and execution time showed that faster kernels alone would barely help. Similar breakdowns are worth doing before optimizing any serving stack.

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

🎓Peking UniversityBeijing · China315 works · 43,268 citations

 Fields, topics and concepts

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

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

Cite

Cite as Bingyang Wu, Yinmin Zhong, Zili Zhang, Shengyu Liu, Fangyue Liu, Yuanhang Sun, Gang Huang, Xuanzhe Liu and Xin Jin. 2023. Fast Distributed Inference Serving for Large Language Models. arXiv 2023.

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

@misc{wu2023fast,
  title = {{Fast Distributed Inference Serving for Large Language Models}},
  author = {Bingyang Wu, Yinmin Zhong, Zili Zhang, Shengyu Liu, Fangyue Liu, Yuanhang Sun, Gang Huang, Xuanzhe Liu and Xin Jin},
  year = {2023},
  eprint = {2305.05920},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.05920}
}

References

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

  1. “Introducing ChatGPT.” https://openai.com/blog/chatgpt, 2022. ↗
  2. “ChatGPT sets record for fastest-growing user base.” https://www.reuters.com/technology/chatgpt-sets-record-fastest-growing-user-base-analyst-note-2023-02-01/, 2023. ↗
  3. “Reinventing search with a new ai-powered bing and edge, your copilot for the web.” https://news.microsoft.com/the-new-Bing/, 2023. ↗
  4. Google, “Our next-generation model: Gemini 1.5.” https://blog.google/technology/ai/google-gemini-next-generation-model-february-2024/, 2024. ↗
  5. Anthropic, “Introducing the next generation of Claude.” https://www.anthropic.com/news/claude-3-family, 2024. ↗
  6. “Introducing Qwen.” https://qwenlm.github.io/blog/qwen/, 2023. ↗
  7. K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in IEEE Conference on Computer Vision and Pattern Recognition, 2016.
  8. A. Gujarati, R. Karimi, S. Alzayat, W. Hao, A. Kaufmann, Y. Vigfusson, and J. Mace, “Serving DNNs like clockwork: Performance predictability from the bottom up,” in USENIX OSDI, 2020. find
  9. H. Zhang, Y. Tang, A. Khandelwal, and I. Stoica, “Shepherd: Serving dnns in the wild,” in USENIX NSDI, 2023. find
  10. G.-I. Yu, J. S. Jeong, G.-W. Kim, S. Kim, and B.-G. Chun, “Orca: A distributed serving system for Transformer-Based generative models,” in USENIX OSDI, 2022.
  11. W. Kwon, Z. Li, S. Zhuang, Y. Sheng, L. Zheng, C. H. Yu, J. E. Gonzalez, H. Zhang, and I. Stoica, “Efficient memory management for large language model serving with pagedattention,” in ACM SOSP, 2023.
  12. K. Kaffes, T. Chong, J. T. Humphries, A. Belay, D. Maz-ières, and C. Kozyrakis, “Shinjuku: Preemptive scheduling for µsecond-scale tail latency,” in USENIX NSDI, 2019. find
  13. “Sharegpt teams.” https://sharegpt.com/, 2023. ↗
  14. R. Taori, I. Gulrajani, T. Zhang, Y. Dubois, X. Li, C. Guestrin, P. Liang, and T. B. Hashimoto, “Stanford alpaca: An instruction-following llama model.” https://github.com/tatsu-lab/stanford_alpaca, 2023. ↗
  15. W. Bai, L. Chen, K. Chen, D. Han, C. Tian, and H. Wang, “Information-agnostic flow scheduling for commodity data centers,” in USENIX OSDI, 2015. find
  16. M. Shoeybi, M. Patwary, R. Puri, P. LeGresley, J. Casper, and B. Catanzaro, “Megatron-lm: Training multi-billion parameter language models using model parallelism,” arXiv, 2020. find
  17. Y. Huang, Y. Cheng, A. Bapna, O. Firat, M. X. Chen, D. Chen, H. Lee, J. Ngiam, Q. V. Le, Y. Wu, and Z. Chen, “Gpipe: Efficient training of giant neural networks using pipeline parallelism,” Neural Information Processing Systems, 2019. find
  18. S. Zhang, S. Roller, N. Goyal, M. Artetxe, M. Chen, S. Chen, C. Dewan, M. Diab, X. Li, X. V. Lin, T. Mihaylov, M. Ott, S. Shleifer, K. Shuster, D. Simig, P. S. Koura, A. Sridhar, T. Wang, and L. Zettlemoyer, “Opt: Open pre-trained transformer language models,” arXiv, 2022.
  19. T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Ber… — Language Models are Few-Shot Learners
  20. H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, A. Rodriguez, A. Joulin, E. Grave, and G. Lample, “Llama: Open and efficient foundation language models,” arXiv, 2023.
  21. A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” Neural Information Processing Systems, 2017.
  22. C. Olston, N. Fiedel, K. Gorovoy, J. Harmsen, L. Lao, F. Li, V. Rajashekhar, S. Ramesh, and J. Soyke, “Tensorflow-serving: Flexible, high-performance ml serving,” arXiv, 2017. find
  23. N. Corporation, “Triton inference server: An optimized cloud and edge inferencing solution.,” 2019. find
  24. M. Ott, S. Edunov, A. Baevski, A. Fan, S. Gross, N. Ng, D. Grangier, and M. Auli, “fairseq: A fast, extensible toolkit for sequence modeling,” arXiv, 2019.
  25. T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, J. Davison, S. Shleifer, P. von Platen, C. Ma, Y. Jernite, J. Plu, C. Xu, T. L. Scao, S. Gugger, M. Drame, Q. Lhoest, and A. M. Rush, “Huggingface’s transformers: State-of-the-art natural langua… — Transformers: State-of-the-Art Natural Language Processing
  26. N. Corporation, “Fastertransformer,” 2019. find
  27. L. Schrage, “A proof of the optimality of the shortest remaining processing time discipline,” Operations Research, 1968. find
  28. N. Shazeer, “Fast transformer decoding: One write-head is all you need,” arXiv, 2019. find
  29. J. Ainslie, J. Lee-Thorp, M. de Jong, Y. Zemlyanskiy, F. Lebrón, and S. Sanghai, “Gqa: Training generalized multi-query transformer models from multi-head checkpoints,” arXiv, 2023.
  30. D. Li*, R. Shao*, A. Xie, Y. Sheng, L. Zheng, J. E. Gonzalez, I. Stoica, X. Ma, and H. Zhang, “How long can open-source llms truly promise on context length?,” 2023. find
  31. C.-Y. Hong, M. Caesar, and P. B. Godfrey, “Finishing flows quickly with preemptive scheduling,” in ACM SIGCOMM, 2012. find
  32. M. Alizadeh, S. Yang, M. Sharif, S. Katti, N. McKeown, B. Prabhakar, and S. Shenker, “pfabric: Minimal near-optimal datacenter transport,” SIGCOMM CCR, 2013. find
  33. M. Chowdhury and I. Stoica, “Efficient coflow scheduling without prior knowledge,” SIGCOMM CCR, 2015. find
  34. J. Gu, M. Chowdhury, K. G. Shin, Y. Zhu, M. Jeon, J. Qian, H. H. Liu, and C. Guo, “Tiresias: A gpu cluster manager for distributed deep learning.,” in USENIX NSDI, 2019. find
  35. Z. Li, L. Zheng, Y. Zhong, V. Liu, Y. Sheng, X. Jin, Y. Huang, Z. Chen, H. Zhang, J. E. Gonzalez, et al., “AlpaServe: Statistical multiplexing with model parallelism for deep learning serving,” in USENIX OSDI, 2023.
  36. J. Kaplan, S. McCandlish, T. Henighan, T. B. Brown, B. Chess, R. Child, S. Gray, A. Radford, J. Wu, and D. Amodei, “Scaling laws for neural language models,” arXiv, 2020.
  37. D. Narayanan, M. Shoeybi, J. Casper, P. LeGresley, M. Patwary, V. A. Korthikanti, D. Vainbrand, P. Kashinkunti, J. Bernauer, B. Catanzaro, A. Phanishayee, and M. Zaharia, “Efficient large-scale language model training on gpu clusters using megatron-lm,” arXiv, 2021. find
  38. D. Narayanan, A. Harlap, A. Phanishayee, V. Seshadri, N. R. Devanur, G. R. Ganger, P. B. Gibbons, and M. Zaharia, “Pipedream: Generalized pipeline parallelism for dnn training,” in ACM SOSP, 2019. find
  39. P. Moritz, R. Nishihara, S. Wang, A. Tumanov, R. Liaw, E. Liang, M. Elibol, Z. Yang, W. Paul, M. I. Jordan, and I. Stoica, “Ray: A distributed framework for emerging AI applications,” in USENIX OSDI, 2018. find
  40. G. Prekas, M. Kogias, and E. Bugnion, “Zygos: Achieving low tail latency for microsecond-scale networked tasks,” in ACM SOSP, 2017. find
  41. Y. Zhong, S. Liu, J. Chen, J. Hu, Y. Zhu, X. Liu, X. Jin, and H. Zhang, “Distserve: Disaggregating prefill and decoding for goodput-optimized large language model serving,” in USENIX OSDI, 2024.
  42. B. Wu, S. Liu, Y. Zhong, P. Sun, X. Liu, and X. Jin, “Loongserve: Efficiently serving long-context large language models with elastic sequence parallelism,” arXiv, 2024.
  43. M. Chowdhury, Y. Zhong, and I. Stoica, “Efficient coflow scheduling with varys,” in ACM SIGCOMM, 2014. find
  44. K. Kaffes, T. Chong, J. T. Humphries, A. Belay, D. Maz-ières, and C. Kozyrakis, “Shinjuku: Preemptive scheduling for µsecond-scale tail latency,” in USENIX NSDI, 2019. find
  45. A. Ousterhout, J. Fried, J. Behrens, A. Belay, and H. Balakrishnan, “Shenango: Achieving high cpu efficiency for latency-sensitive datacenter workloads.,” in USENIX NSDI, 2019. find
  46. J. Fried, Z. Ruan, A. Ousterhout, and A. Belay, “Caladan: Mitigating interference at microsecond timescales,” in USENIX OSDI, 2020. find
  47. Z. Bai, Z. Zhang, Y. Zhu, and X. Jin, “Pipeswitch: Fast pipelined context switching for deep learning applications,” in USENIX OSDI, 2020. find
  48. M. Han, H. Zhang, R. Chen, and H. Chen, “Microsecond-scale preemption for concurrent GPU-accelerated DNN inferences,” in USENIX OSDI, 2022. find
  49. D. Crankshaw, X. Wang, G. Zhou, M. J. Franklin, J. E. Gonzalez, and I. Stoica, “Clipper: A low-latency online prediction serving system.,” in USENIX NSDI, 2017. find
  50. J. Fang, Y. Yu, C. Zhao, and J. Zhou, “Turbotransformers: an efficient gpu serving system for transformer models,” in ACM PPoPP, 2021. find
  51. D. Li, R. Shao, H. Wang, H. Guo, E. P. Xing, and H. Zhang, “Mpcformer: fast, performant and private transformer inference with mpc,” arXiv, 2023. find
  52. Y. Sheng, S. Cao, D. Li, B. Zhu, Z. Li, D. Zhuo, J. E. Gonzalez, and I. Stoica, “Fairness in serving large language models,” in USENIX OSDI, 2024. find
  53. P. Patel, E. Choukse, C. Zhang, A. Shah, Íñigo Goiri, S. Maleki, and R. Bianchini, “Splitwise: Efficient generative llm inference using phase splitting,” in ACM/IEEE ISCA, 2024.
  54. Y. Bai, C. Li, Q. Zhou, J. Yi, P. Gong, F. Yan, R. Chen, and Y. Xu, “Gradient compression supercharged high-performance data parallel dnn training,” in ACM SOSP, 2021. find
  55. J. Wang, B. Yuan, L. Rimanic, Y. He, T. Dao, B. Chen, C. Re, and C. Zhang, “Fine-tuning language models over slow networks using activation quantization with guarantees,” Neural Information Processing Systems, 2022. find
  56. Z. Li, E. Wallace, S. Shen, K. Lin, K. Keutzer, D. Klein, and J. Gonzalez, “Train big, then compress: Rethinking model size for efficient training and inference of transformers,” in International Conference on Machine Learning (ICML), 2020. find
  57. G. Xiao, J. Lin, M. Seznec, J. Demouth, and S. Han, “Smoothquant: Accurate and efficient post-training quantization for large language models,” International Conference on Machine Learning, 2022. find
  58. E. Frantar, S. Ashkboos, T. Hoefler, and D. Alistarh, “Gptq: Accurate post-training quantization for generative pre-trained transformers,” arXiv, 2022. find
  59. T. Dettmers, M. Lewis, Y. Belkada, and L. Zettlemoyer, “Llm. int8 (): 8-bit matrix multiplication for transformers at scale,” arXiv, 2022. find
  60. N. Zheng, B. Lin, Q. Zhang, L. Ma, Y. Yang, F. Yang, Y. Wang, M. Yang, and L. Zhou, “SparTA: Deep-Learning model sparsity via Tensor-with-Sparsity-Attribute,” in USENIX OSDI, 2022. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/wu-2023-fast-distributed-inference-serving-large/