Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 2 Background 2.1 Large Language Models 2.1 Large Language Models 2.2 Fragmentation and PagedAttention 2.2 Fragmentation and PagedAttention 3 Issues with the PagedAttention Model and 3.1 Requires re-writing the attention kernel 3 Issues with the PagedAttention Model and 3.1 Requires re-writing the attention kernel 3.2 Adds redundancy in the serving framework and 3.3 Performance Overhead 3.2 Adds redundancy in the serving framework and 3.3 Performance Overhead 4 Insights into LLM Serving Systems 4 Insights into LLM Serving Systems 5 vAttention: System Design and 5.1 Design Overview 5 vAttention: System Design and 5.1 Design Overview 5.2 Leveraging Low-level CUDA Support 5.2 Leveraging Low-level CUDA Support 5.3 Serving LLMs with vAttention 5.3 Serving LLMs with vAttention 6 vAttention: Optimizations and 6.1 Mitigating internal fragmentation 6 vAttention: Optimizations and 6.1 Mitigating internal fragmentation 6.2 Hiding memory allocation latency 6.2 Hiding memory allocation latency 7 Evaluation 7 Evaluation 7.1 Portability and Performance for Prefills 7.1 Portability and Performance for Prefills 7.2 Portability and Performance for Decodes 7.2 Portability and Performance for Decodes 7.3 Efficacy of Physical Memory Allocation 7.3 Efficacy of Physical Memory Allocation 7.4 Analysis of Memory Fragmentation 7.4 Analysis of Memory Fragmentation 8 Related Work 8 Related Work 9 Conclusion and References 9 Conclusion and References 9 Conclusion PagedAttention has emerged as the de facto standard for dynamic memory allocation in LLM inference. PagedAttention eliminates the need to reserve GPU memory ahead-of-time and therefore boosts serving throughput by fitting a larger batch size in GPU memory. While PagedAttention effectively tackles memory fragmentation, we argue that its approach of storing KV-cache in non-contiguous virtual memory introduces software complexity as well as portability and efficiency challenges. Instead, we show that using low-level system support for demand paging can avoid the pitfalls of PagedAttention. Our proposed system vAttention adds support for dynamic physical memory allocation to existing attention kernels, eliminating the need to re-write GPU code or write a memory manager in the serving framework. We show that vAttention reduces software complexity while improving portability and performance. References [1] [n. d.]. Amazon CodeWhisperer. https://aws.amazon.com/ codewhisperer/. [2] [n. d.]. Anthropic Claude. https://claude.ai. [3] [n. d.]. Bing AI. https://www.bing.com/chat. [4] [n. d.]. Faster Transformer Kernels. https://github.com/NVIDIA/ FasterTransformer/tree/main/src/fastertransformer/kernels/ decoder_masked_multihead_attention. [5] [n. d.]. Github Copilot. https://github.com/features/copilot. [6] [n. d.]. Google Bard. https://bard.google.com. [7] [n. d.]. Replit Ghostwriter. https://replit.com/site/ghostwriter. [8] [n. d.]. Text Generation Inference. https://huggingface.co/textgeneration-inference. [9] 2022. FlashAttention. https://github.com/Dao-AILab/flash-attention. [10] 2023. Flash-Decoding for long-context inference. https://crfm.stanford. edu/2023/10/12/flashdecoding.html. [11] 2023. FlashInfer: Kernel Library for LLM Serving. https://github.com/ flashinfer-ai/flashinfer. [12] 2023. LightLLM: A Light and Fast Inference Service for LLM. https: //github.com/ModelTC/lightllm. [13] 2023. Performance decay when using paged attention. https://github. com/NVIDIA/TensorRT-LLM/issues/75. [14] 2023. TensorRT-LLM: A TensorRT Toolbox for Optimized Large Language Model Inference. https://github.com/NVIDIA/TensorRT-LLM. [15] 2023. Use optimized kernels for MQA/GQA. https://github.com/vllmproject/vllm/issues/1880. [16] 2024. Add support for small page sizes. https://github.com/DaoAILab/flash-attention/pull/824. [17] 2024. CUDA Toolkit Documentation: Virtual Memory Management. https://docs.nvidia.com/cuda/cuda-driver-api/group__CUDA_ _VA.html. [18] 2024. Faster Transformer. https://github.com/NVIDIA/ FasterTransformer. [19] 2024. Fix eager mode performance. https://github.com/vllm-project/ vllm/pull/2377. [20] 2024. Implement Page KV Cache. https://github.com/Dao-AILab/flashattention/commit/54e80a3829c6d2337570d01e78ebd9529c02d342. [21] 2024. Refactor Attention Take 2. https://github.com/vllm-project/ vllm/pull/3462. [22] 2024. Separate attention backends. https://github.com/vllm-project/ vllm/pull/3005/. [23] 2024. Support KV Partition for BatchPrefill kernel for Paged and Ragged KV-Cache. https://github.com/flashinfer-ai/flashinfer/pull/75. [24] 2024. Use FlashInfer for Decoding. https://github.com/vllm-project/ vllm/pull/4353. [25] 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. arXiv:2403.02310 [cs.LG] [26] Amey Agrawal, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S. Gulavani, and Ramachandran Ramjee. 2023. SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills. arXiv:2308.16369 [cs.LG] [27] Joshua Ainslie, James Lee-Thorp, Michiel de Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sanghai. 2023. GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints. arXiv:2305.13245 [cs.CL] [28] Pratheek B, Neha Jawalkar, and Arkaprava Basu. 2023. Designing Virtual Memory System of MCM GPUs. In Proceedings of the 55th Annual IEEE/ACM International Symposium on Microarchitecture (, Chicago, Illinois, USA, ) (MICRO ’22). IEEE Press, 404–422. https://doi.org/10.1109/MICRO56248.2022.00036 [29] Iz Beltagy, Matthew E. Peters, and Arman Cohan. 2020. Longformer: The Long-Document Transformer. arXiv:2004.05150 [cs.CL] [30] Ganesh Bikshandi and Jay Shah. 2023. A Case Study in CUDA Kernel Fusion: Implementing FlashAttention-2 on NVIDIA Hopper Architecture using the CUTLASS Library. arXiv:2312.11918 [cs.LG] [31] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. 2019. Generating Long Sequences with Sparse Transformers. arXiv:1904.10509 [cs.LG] [32] 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, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowycz, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. 2022. PaLM: Scaling Language Modeling with Pathways. CoRR abs/2204.02311 (2022). https://doi.org/10.48550/arXiv.2204.02311 arXiv:2204.02311 [33] Tri Dao. 2023. FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning. arXiv:2307.08691 [cs.LG] [34] Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. 2022. FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness. arXiv:2205.14135 [cs.LG] [35] Cong Guo, Rui Zhang, Jiale Xu, Jingwen Leng, Zihan Liu, Ziyu Huang, Minyi Guo, Hao Wu, Shouren Zhao, Junping Zhao, and Ke Zhang. 2024. GMLake: Efficient and Transparent GPU Memory Defragmentation for Large-scale DNN Training with Virtual Memory Stitching. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (, La Jolla, CA, USA, ) (ASPLOS ’24). Association for Computing Machinery, New York, NY, USA, 450–466. https: //doi.org/10.1145/3620665.3640423 [36] Connor Holmes, Masahiro Tanaka, Michael Wyatt, Ammar Ahmad Awan, Jeff Rasley, Samyam Rajbhandari, Reza Yazdani Aminabadi, Heyang Qin, Arash Bakhtiari, Lev Kurilenko, and Yuxiong He. 2024. DeepSpeed-FastGen: High-throughput Text Generation for LLMs via MII and DeepSpeed-Inference. arXiv:2401.08671 [cs.PF] [37] Ke Hong, Guohao Dai, Jiaming Xu, Qiuli Mao, Xiuhong Li, Jun Liu, Kangdi Chen, Yuhan Dong, and Yu Wang. 2024. FlashDecoding++: Faster Large Language Model Inference on GPUs. arXiv:2311.01282 [cs.LG] [38] Cunchen Hu, Heyang Huang, Liangliang Xu, Xusheng Chen, Jiang Xu, Shuang Chen, Hao Feng, Chenxi Wang, Sa Wang, Yungang Bao, et al. 2024. Inference without Interference: Disaggregate LLM Inference for Mixed Downstream Workloads. arXiv preprint arXiv:2401.11181 (2024). [39] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. 2023. Efficient Memory Management for Large Language Model Serving with PagedAttention (SOSP ’23). Association for Computing Machinery, New York, NY, USA, 611–626. https://doi.org/10.1145/3600006. 3613165 [40] OpenAI. 2023. GPT-4 Technical Report. CoRR abs/2303.08774 (2023). https://doi.org/10.48550/arXiv.2303.08774 arXiv:2303.08774 [41] Pratyush Patel, Esha Choukse, Chaojie Zhang, Íñigo Goiri, Aashaka Shah, Saeed Maleki, and Ricardo Bianchini. 2023. Splitwise: Efficient generative LLM inference using phase splitting. arXiv:2311.18677 [cs.AR] [42] Noam Shazeer. 2019. Fast Transformer Decoding: One Write-Head is All You Need. arXiv:1911.02150 [cs.NE] [43] 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. 2023. FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPU. arXiv:2303.06865 [cs.LG] [44] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017. Attention is All you Need. In Advances in Neural Information Processing Systems, I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc. https://proceedings.neurips.cc/paper_files/paper/2017/ file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf [45] Bingyang Wu, Yinmin Zhong, Zili Zhang, Gang Huang, Xuanzhe Liu, and Xin Jin. 2023. Fast Distributed Inference Serving for Large Language Models. arXiv:2305.05920 [cs.LG] [46] 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. 2024. Accelerating Self-Attentions for LLM Serving with FlashInfer. https://flashinfer.ai/2024/02/02/introduce-flashinfer.html [47] Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung-Gon Chun. 2022. Orca: A Distributed Serving System for Transformer-Based Generative Models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22). USENIX Association, Carlsbad, CA, 521–538. https://www.usenix.org/conference/ osdi22/presentation/yu [48] Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, Zhangyang Wang, and Beidi Chen. 2023. H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models. arXiv:2306.14048 [cs.LG] [49] Yinmin Zhong, Shengyu Liu, Junda Chen, Jianbo Hu, Yibo Zhu, Xuanzhe Liu, Xin Jin, and Hao Zhang. 2024. DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving. arXiv:2401.09670 [cs.DC] This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv Authors: (1) Ramya Prabhu, Microsoft Research India; (2) Ajay Nayak, Indian Institute of Science and Contributed to this work as an intern at Microsoft Research India; (3) Jayashree Mohan, Microsoft Research India; (4) Ramachandran Ramjee, Microsoft Research India; (5) Ashish Panwar, Microsoft Research India. Authors: Authors: (1) Ramya Prabhu, Microsoft Research India; (2) Ajay Nayak, Indian Institute of Science and Contributed to this work as an intern at Microsoft Research India; (3) Jayashree Mohan, Microsoft Research India; (4) Ramachandran Ramjee, Microsoft Research India; (5) Ashish Panwar, Microsoft Research India.
