title: MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via
    Dynamic Sparse Attention
summary: The computational challenges of Large Language Model (LLM) inference remain a
  significant barrier to their widespread deployment, especially as prompt
  lengths continue to increase. Due to the quadratic complexity of the attention
  computation, it takes 30 minutes for an 8B LLM to process a prompt of 1M tokens
  (i.e., the pre-filling stage) on a single A100 GPU. Existing methods for
  speeding up prefilling often fail to maintain acceptable accuracy or efficiency
  when applied to long-context LLMs. To address this gap, we introduce MInference
  (Milliontokens Inference), a sparse calculation method designed to accelerate
  pre-filling of long-sequence processing. Specifically, we identify three unique
  patterns in long-context attention matrices-the A-shape, Vertical-Slash, and
  Block-Sparsethat can be leveraged for efficient sparse computation on GPUs. We
  determine the optimal pattern for each attention head offline and dynamically
  build sparse indices based on the assigned pattern during inference. With the
  pattern and sparse indices, we perform efficient sparse attention calculations
  via our optimized GPU kernels to significantly reduce the latency in the
  pre-filling stage of long-context LLMs. Our proposed technique can be directly
  applied to existing LLMs without any modifications to the pre-training setup or
  additional fine-tuning. By evaluating on a wide range of downstream tasks,
  including InfiniteBench, RULER, PG-19, and Needle In A Haystack, and models
  including LLaMA-3-1M, GLM4-1M, Yi-200K, Phi-3-128K, and Qwen2-128K, we
  demonstrate that MInference effectively reduces inference latency by up to 10x
  for pre-filling on an A100, while maintaining accuracy. Our code is available
  at https://aka.ms/MInference.
paper_authors._id: 6684aff23780e7f96dc29274
paper_authors.name: Huiqiang Jiang
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-07-03T07:37:55.043Z
paper_authors._id: 6278bd42541f3d2dfa77ea70
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/6278bd42541f3d2dfa77ea70/ejn49eapnB3UXQckAYdTd.jpeg
paper_authors.fullname: Huiqiang Jiang
paper_authors.type: user
paper_authors.user: iofu728
paper_authors._id: 6684aff23780e7f96dc29275
paper_authors.name: Yucheng Li
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-07-03T07:41:33.975Z
paper_authors._id: 63d00710645dd8d34ea9bcc6
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/63d00710645dd8d34ea9bcc6/E6YsIsXH57OACL-NZ52fB.jpeg
paper_authors.fullname: Yucheng
paper_authors.type: user
paper_authors.user: liyucheng
paper_authors._id: 6684aff23780e7f96dc29276
paper_authors.name: Chengruidong Zhang
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2024-07-03T08:22:52.134Z
paper_authors._id: 64646896884f2e3e1ced3cd5
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/64646896884f2e3e1ced3cd5/86-t8V8LGMNaPQRXnADiD.png
paper_authors.fullname: Zhang
paper_authors.type: user
paper_authors.user: Chengruidong
paper_authors._id: 6684aff23780e7f96dc29277
paper_authors.name: Qianhui Wu
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2024-07-03T08:22:59.496Z
paper_authors._id: 63ef330b1e695b35aa484e11
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/63ef330b1e695b35aa484e11/bXwpGy0dl8JXeJwJ--ilr.jpeg
paper_authors.fullname: Qianhui WU
paper_authors.type: user
paper_authors.user: qianhuiwu
paper_authors._id: 6684aff23780e7f96dc29278
paper_authors.name: Xufang Luo
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2024-07-03T08:23:06.765Z
paper_authors._id: 64b750a2fdb702b3d8619514
paper_authors.avatarUrl: /avatars/f09181c0825763dff692c4bc65effc4c.svg
paper_authors.fullname: Xufang Luo
paper_authors.type: user
paper_authors.user: luoxufang
paper_authors._id: 6684aff23780e7f96dc29279
paper_authors.name: Surin Ahn
paper_authors._id: 6684aff23780e7f96dc2927a
paper_authors.name: Zhenhua Han
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2024-07-03T08:23:18.553Z
paper_authors._id: 64cc9b96e60d2cddfadca2c8
paper_authors.avatarUrl: /avatars/a07755847ec8d05052221d351a3ae20f.svg
paper_authors.fullname: Zhenhua Han
paper_authors.type: user
paper_authors.user: hzhua
paper_authors._id: 6684aff23780e7f96dc2927b
paper_authors.name: Amir H. Abdi
paper_authors._id: 6684aff23780e7f96dc2927c
paper_authors.name: Dongsheng Li
paper_authors._id: 6684aff23780e7f96dc2927d
paper_authors.name: Chin-Yew Lin
paper_authors._id: 6684aff23780e7f96dc2927e
paper_authors.name: Yuqing Yang
paper_authors._id: 6684aff23780e7f96dc2927f
paper_authors.name: Lili Qiu
paper_title: MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via
    Dynamic Sparse Attention
paper_summary: The computational challenges of Large Language Model (LLM) inference remain a
  significant barrier to their widespread deployment, especially as prompt
  lengths continue to increase. Due to the quadratic complexity of the attention
  computation, it takes 30 minutes for an 8B LLM to process a prompt of 1M tokens
  (i.e., the pre-filling stage) on a single A100 GPU. Existing methods for
  speeding up prefilling often fail to maintain acceptable accuracy or efficiency
  when applied to long-context LLMs. To address this gap, we introduce MInference
  (Milliontokens Inference), a sparse calculation method designed to accelerate
  pre-filling of long-sequence processing. Specifically, we identify three unique
  patterns in long-context attention matrices-the A-shape, Vertical-Slash, and
  Block-Sparsethat can be leveraged for efficient sparse computation on GPUs. We
  determine the optimal pattern for each attention head offline and dynamically
  build sparse indices based on the assigned pattern during inference. With the
  pattern and sparse indices, we perform efficient sparse attention calculations
  via our optimized GPU kernels to significantly reduce the latency in the
  pre-filling stage of long-context LLMs. Our proposed technique can be directly
  applied to existing LLMs without any modifications to the pre-training setup or
  additional fine-tuning. By evaluating on a wide range of downstream tasks,
  including InfiniteBench, RULER, PG-19, and Needle In A Haystack, and models
  including LLaMA-3-1M, GLM4-1M, Yi-200K, Phi-3-128K, and Qwen2-128K, we
  demonstrate that MInference effectively reduces inference latency by up to 10x
  for pre-filling on an A100, while maintaining accuracy. Our code is available
  at https://aka.ms/MInference.
paper_ai_keywords: Large Language Model (LLM) prompt attention computation pre-filling stage Sparse calculation method long-context attention matrices A-shape Vertical-Slash Block-Sparse sparse indices sparse attention calculations GPU kernels InfiniteBench RULER PG-19 Needle In A Haystack LLaMA-3-1M GLM4-1M Yi-200K Phi-3-128K Qwen2-128K