# Prepacking: A Simple Method for Fast Prefilling and Increased Throughput in Large Language Models

arXiv: https://arxiv.org/abs/2404.09529 · HTML: https://mlsanity.com/paper/2404.09529/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 35 references that are in the map.
- First posted on arXiv 15 Apr 2024.

## Builds on (most cited first, 25 of 25)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models](https://mlsanity.com/paper/2211.10438/) (2022)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [Aligning AI With Shared Human Values](https://mlsanity.com/paper/2008.02275/) (2020)
- [DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving](https://mlsanity.com/paper/2401.09670/) (2024)
- [FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPU](https://mlsanity.com/paper/2303.06865/) (2023)
- [SAMSum Corpus: A Human-annotated Dialogue Dataset for Abstractive Summarization](https://mlsanity.com/paper/1911.12237/) (2019)
- [Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve](https://mlsanity.com/paper/2403.02310/) (2024)
- [Intriguing Properties of Vision Transformers](https://mlsanity.com/paper/2105.10497/) (2021)
- [Sheared LLaMA: Accelerating Language Model Pre-training via Structured Pruning](https://mlsanity.com/paper/2310.06694/) (2023)
- [DeepSpeed Inference: Enabling Efficient Inference of Transformer Models at Unprecedented Scale](https://mlsanity.com/paper/2207.00032/) (2022)
- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [GPTs are GPTs: An Early Look at the Labor Market Impact Potential of Large Language Models](https://mlsanity.com/paper/2303.10130/) (2023)
- [Towards Efficient Generative Large Language Model Serving: A Survey from Algorithms to Systems](https://mlsanity.com/paper/2312.15234/) (2023)
- [Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline](https://mlsanity.com/paper/2305.13144/) (2023)
- [Analysing The Impact of Sequence Composition on Language Model Pre-Training](https://mlsanity.com/paper/2402.13991/) (2024)
- [The CoRa Tensor Compiler: Compilation for Ragged Tensors with Minimal Padding](https://mlsanity.com/paper/2110.10221/) (2021)

## Built on by (most cited first, 10 of 10)

- [KVCOMM: Online Cross-context KV-cache Communication for Efficient LLM-based Multi-agent Systems](https://mlsanity.com/paper/2510.12872/) (2025)
- [A Declarative System for Optimizing AI Workloads](https://mlsanity.com/paper/2405.14696/) (2024)
- [Prefill-level Jailbreak: A Black-Box Risk Analysis of Large Language Models](https://mlsanity.com/paper/2504.21038/) (2025)
- [SwiftSpec: Ultra-Low Latency LLM Decoding by Scaling Asynchronous Speculative Decoding](https://mlsanity.com/paper/2506.11309/) (2025)
- [Enabling Autoregressive Models to Fill In Masked Tokens](https://mlsanity.com/paper/2502.06901/) (2025)
- [Thousand-GPU Large-Scale Training and Optimization Recipe for AI-Native Cloud Embodied Intelligence Infrastructure](https://mlsanity.com/paper/2603.11101/) (2026)
- [OverFill: Two-Stage Models for Efficient Language Model Decoding](https://mlsanity.com/paper/2508.08446/) (2025)
- [AccLLM: Accelerating Long-Context LLM Inference Via Algorithm-Hardware Co-Design](https://mlsanity.com/paper/2505.03745/) (2025)
- [AI Compute Architecture and Evolution Trends](https://mlsanity.com/paper/2508.21394/) (2025)
- [PackInfer: Compute- and I/O-Efficient Attention for Batched LLM Inference](https://mlsanity.com/paper/2602.06072/) (2026)

## Abstract (arXiv)

During inference for transformer-based large language models (LLM), prefilling is the computation of the key-value (KV) cache for input tokens in the prompt prior to autoregressive generation. For longer input prompt lengths, prefilling will incur a significant overhead on decoding time. In this work, we highlight the following pitfall of prefilling: for batches containing high-varying prompt lengths, significant computation is wasted by the standard practice of padding sequences to the maximum length. As LLMs increasingly support longer context lengths, potentially up to 10 million tokens, variations in prompt lengths within a batch become more pronounced. To address this, we propose Prepacking, a simple yet effective method to optimize prefilling computation. To avoid redundant computation on pad tokens, prepacking combines prompts of varying lengths into a sequence and packs multiple sequences into a compact batch using a bin-packing algorithm. It then modifies the attention mask and positional encoding to compute multiple prefilled KV-caches for multiple prompts within a single sequence. On standard curated dataset containing prompts with varying lengths, we obtain a significant speed and memory efficiency improvements as compared to the default padding-based prefilling computation within Huggingface across a range of base model configurations and inference serving scenarios.