Managing KV Cache for Coordinated Waiting and Execution Time in LLM Serving

Abstract

Large Language Model (LLM) serving systems face a KV-cache (KVC) bottleneck. In this paper, our experimental study shows that block-based allocation increases Time-Between-Tokens (TBT) due to preemptions, while prediction-based allocation increases Time-to-First-Token (TTFT) and TBT due to allocated but unused KVC and inaccurate predictions. To address the problems to satisfy users' TTFT and TBT SLOs, we propose a system for Managing KV Cache for Coordinated TTFT and TBT (MC2). First, instead of using a constant padding in output length estimation, MC2 dynamically determines padding to bound prediction deviations with high probability and adjusts it based on request arrival rates to balance TTFT and TBT. Second, it allocates a block to requests requiring execution in the next iteration to meet their TTFT and TBT SLOs, and then distributes the remaining KVC to batched requests based on their SLOs and remaining iterations. Third, it proactively allocates KVC before depletion and reserves KVC globally to prevent preemptions. Experiments show that MC2 achieves up to 3.29× and 2.83× lower tail TBT and tail TTFT, 47% and 53% higher TTFT and TBT SLO attainments, and supports up to 1.58× higher request arrival rate than the state-of-the-art.