# KV-Runahead: Scalable Causal LLM Inference by Parallel Key-Value Cache Generation

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving.
- Builds on 21 of its 29 references that are in the map.
- First posted on arXiv 8 May 2024.

## Placed in

- Efficient LLM inference and serving / [KV cache optimization](https://mlsanity.com/inference/kv-cache-optimization/)

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers](https://mlsanity.com/paper/2210.17323/) (2022)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration](https://mlsanity.com/paper/2306.00978/) (2023)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM](https://mlsanity.com/paper/2104.04473/) (2021)
- [Splitwise: Efficient generative LLM inference using phase splitting](https://mlsanity.com/paper/2311.18677/) (2023)
- [Benchmarking Large Language Models for News Summarization](https://mlsanity.com/paper/2301.13848/) (2023)
- [LLM-QAT: Data-Free Quantization Aware Training for Large Language Models](https://mlsanity.com/paper/2305.17888/) (2023)
- [SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills](https://mlsanity.com/paper/2308.16369/) (2023)
- [Memory-Efficient Pipeline-Parallel DNN Training](https://mlsanity.com/paper/2006.09503/) (2020)
- [A Survey of Controllable Text Generation using Transformer-based Pre-trained Language Models](https://mlsanity.com/paper/2201.05337/) (2022)
- [Sequence Parallelism: Long Sequence Training from System Perspective](https://mlsanity.com/paper/2105.13120/) (2021)
- [eDKM: An Efficient and Accurate Train-time Weight Clustering for Large Language Models](https://mlsanity.com/paper/2309.00964/) (2023)

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

- [Context Parallelism for Scalable Million-Token Inference](https://mlsanity.com/paper/2411.01783/) (2024)
- [Compactor: Calibrated Query-Agnostic KV Cache Compression with Approximate Leverage Scores](https://mlsanity.com/paper/2507.08143/) (2025)
- [SPD: Sync-Point Drop for Efficient Tensor Parallelism of Large Language Models](https://mlsanity.com/paper/2502.20727/) (2025)
- [Equinox: Holistic Fair Scheduling in Serving Large Language Models](https://mlsanity.com/paper/2508.16646/) (2025)
- [MAS-Attention: Memory-Aware Stream Processing for Attention Acceleration on Resource-Constrained Edge Devices](https://mlsanity.com/paper/2411.17720/) (2024)
- [OLED-MoE: Accelerating MoE-Based dLLM Inference via Inter-Iteration Locality-Aware Expert Offloading](https://mlsanity.com/paper/2609.33385/) (2026)

## Abstract (arXiv)

Large Language Model or LLM inference has two phases, the prompt (or prefill) phase to output the first token and the extension (or decoding) phase to the generate subsequent tokens. In this work, we propose an efficient parallelization scheme, KV-Runahead to accelerate the prompt phase. The key observation is that the extension phase generates tokens faster than the prompt phase because of key-value cache (KV-cache). Hence, KV-Runahead parallelizes the prompt phase by orchestrating multiple processes to populate the KV-cache and minimizes the time-to-first-token (TTFT). Dual-purposing the KV-cache scheme has two main benefits. First, since KV-cache is designed to leverage the causal attention map, we minimize computation and computation automatically. Second, since it already exists for the extension phase, KV-Runahead is easy to implement. We further propose context-level load-balancing to handle uneven KV-cache generation (due to the causal attention) and to optimize TTFT. Compared with an existing parallelization scheme such as tensor or sequential parallelization where keys and values are locally generated and exchanged via all-gather collectives, our experimental results demonstrate that KV-Runahead can offer over 1.4x and 1.6x speedups for Llama 7B and Falcon 7B respectively.