Research map / Large language models / Reasoning and chain of thought
KV-Runahead: Scalable Causal LLM Inference by Parallel Key-Value Cache Generation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes KV-Runahead, a parallel prefill scheme that reuses the KV-cache interface to pass keys/values point-to-point between processes with context-level load balancing, reducing time-to-first-token for causal LLMs.
Problem
Time-to-first-token (prompt/prefill phase) of long-context causal LLM inference is compute-bound, and existing tensor/sequence parallelism wastes computation and communication by ignoring causality and relying on all-gather.
Approach
Dual-purpose the KV-cache so that each process computes Q/K/V for an unevenly sized context chunk and passes its growing KV-cache to the next process via point-to-point send/recv, exploiting causality; partition sizes are chosen by hierarchical grid search and interpolated from a lookup table.
Key results
- KVR-S achieves 1.42x speedup over TSP for Llama 7B at 16k context on 4 GPUs with 300GB/s network (Table: 1.76s vs 1.24s).
- Under 10GB/s bandwidth, KVR-E/KVR-S reach 1.55x (4 GPUs, 8k) and 1.79x (4 GPUs, 12k) over TSP for Llama 7B.
- Falcon 7B KVR-S reaches up to 1.63x speedup over TSP; KVR communication volume is about half of TSP's in theory ((p-1)/2 C vs (p-1) C).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use KV-Runahead with searched context partitioning instead of TSP | Llama 7B · Contexts 1k–16k, 4 and 8 GPUs | TTFT speedup: 1.11 to 1.42; 1.14 to 1.41 | Helped |
| Use KV-Runahead with searched context partitioning instead of TSP | Falcon 7B · Contexts 1k–8k, 4 and 8 GPUs | TTFT speedup: 1.12 to 1.46; 1.20 to 1.63 | Helped |
| Use KV-Runahead with searched context partitioning instead of TSP | Llama 13B · Contexts 1k–16k, 4 and 8 GPUs | TTFT | Helped |
| Use KV-Runahead with searched context partitioning instead of TSP | Falcon 1B · Contexts 1k–8k, 4 and 8 GPUs | TTFT | Helped |
| Use KV-Runahead with searched context partitioning instead of TSP | Llama 30B · Contexts 1k–2k, 4 and 8 GPUs | TTFT | Helped |
| Use even context partitioning rather than searched context partitioning (ablation) | KV-Runahead · Falcon 7B, 4k context | TTFT | Hurt |
| Use searched context partitioning instead of even context partitioning (ablation) | KV-Runahead · Falcon 7B, 4k context, 4 GPUs | TTFT speedup: +1.30 speedup over TSP | Helped |
| Use predicted/interpolated context partitions instead of searched partitions (ablation) | KV-Runahead · Llama 7B, 10k and 12k contexts | TTFT: within 1.3% | No clear effect |
| Use MQA instead of MHA (ablation) | Llama 7B with KV-Runahead · 16k context, 8 GPUs | TTFT speedup over TSP: 1.41x -> 1.48x | Helped |
| Use GQA8 instead of MHA (ablation) | Llama 7B with KV-Runahead · 16k context, 8 GPUs | TTFT speedup over TSP: 1.41x -> 1.46x | Helped |
| Use KVR point-to-point communication instead of TSP all-gather | KV-Runahead · 8k, 12k, and 16k contexts with non-uniform bandwidth | TTFT degradation: over 10% -> up to 3.7% | Helped |
| Use 4 GPUs instead of 2 GPUs | Parallel inference on Llama 7B · 2k context, 10GB/s | TTFT: 0.16sec -> 0.19sec | Hurt |
Surprising findings
- Parallel inference is only beneficial when bandwidth is high enough or context is long enough; with 2K context at 10GB/s, 4 GPUs is slower than 2 GPUs (0.19s vs 0.16s).
- For short contexts the benefit of KVR-E is canceled by KV-cache waiting time and unbalanced compute.
Limitations
- Speedups shrink for short contexts and for high GPU counts where non-parallelizable parts dominate (e.g., 8 GPUs).
- Partition lookup table requires costly offline grid search (estimated ~33 hours per entry), though interpolation is used at inference.
- Requires contiguous KV-cache memory during prefill, which conflicts with fragmented KV-cache management such as vLLM without changes.
Experimental setup
Metrics: time-to-first-token (TTFT) speedup over TSP
Baselines: TSP (tensor/sequence parallelism) KVR-E TTFT lower bound TTFT*(p)
Builds on: tensor parallelism sequence parallelism (ring attention) KV-cache
Closest papers by meaning
- ShadowKV: KV Cache in Shadows for High-Throughput Long-Context LLM Inference (ICML 2025 · similarity 0.91)
- Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference (NeurIPS 2025 · similarity 0.90)
- RocketKV: Accelerating Long-Context LLM Inference via Two-Stage KV Cache Compression (ICML 2025 · similarity 0.90)
- SqueezeAttention: 2D Management of KV-Cache in LLM Inference via Layer-wise Optimal Budget (ICLR 2025 · similarity 0.90)
- Inference-Time Hyper-Scaling with KV Cache Compression (NeurIPS 2025 · similarity 0.90)
- SpeCache: Speculative Key-Value Caching for Efficient Generation of LLMs (ICML 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.