Mitigating KV Cache Competition to Enhance User Experience in LLM Inference

Haiying Shen, Tanmoy Sen, Masahiro Tanaka · 2025

Read Mitigating KV Cache Competition to Enhance User Experience in LLM Inference by Haiying Shen, Tanmoy Sen, Masahiro Tanaka (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-13773.txt.

Introduction

Chatbots remember the conversation in a key-value cache, and when many users compete for that memory, answers slow to a crawl. Shen, Sen, and Tanaka present CacheOPT, a serving system that eases this cache competition. It first guesses each request's answer length, holding the guess within a stated error bound that shifts with traffic.

The system hands out cache by estimate, lets requests borrow idle shares, and reserves memory ahead of need so jobs are not thrown out mid-answer. When a swap is unavoidable, it picks the victim whose delay hurts least and the cheapest restart route. Tests show tail delays cut by up to about threefold.

Catalog record

CREATORHaiying Shen, Tanmoy Sen, Masahiro Tanaka
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-13773

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Mitigating KV Cache Competition to Enhance User Experience in LLM Inference Haiying Shen, Tanmoy Sen, Masahiro Tanaka Abstract In Large Language Model (LLM) serving, the KV-cache (KVC) bottleneck causes high tail Time-to-First-Token (TTFT) and Time-Between-Tokens (TBT), impairing user experience, particularly in time-sensitive applications. However, satisfying both TTFT and TBT service-level objectives (SLOs) is challenging. To address this, we propose a system, named CacheOPT for mitigating KV Cache competition, based on key insights from our measurements, incorporating novel components. First, it estimates a request’s output length, bounding the deviation with a high specified probability, adjusted based on the request arrival rate. Second, it allocates the estimated KVC demand to a request, and reuses other requests’ allocated KVC to avoid preemptions while reducing waiting time. Third, it proactively allocates KVC before instead of at the time a request exhausts its allocation and reserves KVC globally to prevent preemptions. Fourth, it chooses a request that has long TBT SLO, long job remaining time and short preemption time to preempt. Fifth, it selects the shortest-latency strategy between swapping and recomputation for preemptions. Experiments show that CacheOPT achieves up to 3.29 × \times and 2.83 × \times lower tail TBT and tail TTFT, 47% and 53% higher TTFT and TBT SLO attainments, and supports up to 1.58 × \times higher request arrival rate than the state-of-the-art methods. 1 Introduction The Large Language Model (LLM) models have found widespread applications across various domains, including automated customer support, chatting, and real-time translation. However, deploying LLMs in real-world applications often comes with high tail Time-to-First-Token (TTFT) or Time-Between-Tokens (TBT) [ 1 , 2 , 3 ] , which can impair user experience, especially in time-sensitive tasks. Reducing TTFT and TBT is crucial for ensuring seamless user interactions and satisfied user experience. It also enables the broader adoption of LLMs in different applications. Due to limited GPU memory and the large volume of KV-cache (KVC) values, KVC becomes a bottleneck, significantly impacting both TTFT and TBT. The first iteration-level scheduler Orca [ 4 ] pre-allocates KVC for the maximum sequence length for each request. However, this approach wastes memory [ 5 ] , limits the batch size and hence GPU utilization (e.g., 0.4% [ 5 ] ) and throughput. To address this problem, vLLM [ 6 ] uses block-based KVC allocation approach, in which, a block, consisting of a fixed number of tokens, is allocated to a request each time. To form a batch in each iteration, the requests from the waiting queue are added to the batch until the whole KVC is allocated. While this approach significantly reduces KVC reserved waste, a running request may experience block allocation failure when it exhausts its allocation. In this case, the last arrived running request is selected to preempt based on the first-in-first-serve (FCFS) policy. Both approaches introduce delays, increasing TBT. Another method allocates KVC to a request equal to the response length predicted by an LLM model [ 7 , 8 ] . Compared to the block-based allocation approach, it reduces the chances of KVC allocation failures but still leads to certain reserved waste since allocated KVC is not used instantly and generates KVC allocation failures with underestimation. [ 7 ] proposes to add a constant padding (e.g., 100 tokens) to the predicted value to avoid underprovisioning, indicates that overprovision is not as important as underprovision. Different LLM applications and users often have varying SLOs for TTFT and TBT. For example, real-time translation applications prioritize ultra-low TTFT to deliver the first token as quickly as possible, enabling smoother conversation flow. In contrast, document summarization may tolerate higher TTFT in exchange for lower TBT. Moreover, users’ reading speeds influence their tolerance for TBT. A fast reader using a summarization tool may prefer shorter TBT to maintain a seamless reading experience, while a slower reader may be less sensitive to longer TBT but require low TTFT for responsiveness. The diverse demands necessitate adaptable LLM systems capable of meeting varying TTFT and TBT SLOs. In this paper, we aim to mitigate KV cache competition while enhancing user experience by satisfying the diverse TTFT and TBT SLOs through studying three problems: (1) How to determine the padding size to ensure that the KVC demand is satisfied with a high specified probability? (2) How to allocate KVC to a request initially and during token generation process? (3) How to choose requests to preempt? (4) How to choose a preemption strategy between swapping and recomputation to reduce the preemption time (defined as the time that a request is halted)? To achieve this goal, we conducted an experiments based on real traces and made the following observations (Os): (1) Block-based KVC allocation increases preemptions and TBT, while prediction-based allocation raises TTFT. A new method is needed to balance both. (2) Previous prediction-based methods often cause underprovisioning (increasing TBT) and overprovisioning (increasing TTFT). The padding size must be carefully determined, considering the request arrival rate, to balance TTFT and TBT. (3) FCFS-based preemption results in more preemptions than approaches that account for remaining time and KVC usage. (4) For sequences exceeding the sweet spot length, swapping results in shorter times compared to recomputation. Leveraging these observations, we propose a system, that optimizes the cache operations for mitigating KV cache competition ( CacheOPT ). We name this CacheOPT to reflect the system’s focus on efficient cache usage. CacheOPT consists of the following components. (1) Confidence-based Padding. We modify an LLM model to predict output length and deviation direction for adding or subtracting padding. Using Hoeffding’s inequality theory [ 9 , 10 ] , we determine the padding needed to ensure a request’s KVC demand is satisfied with a high specified probability and adjust it based on arrival rate to balance TTFT and TBT. (O2) (2) SLO-aware Batching and KVC Allocation. We reuse allocated but unused KVC and select waiting and returned requests that must run to satisfy their TTFT and TBT SLOs. The remaining unallocated KVC is distributed among the selected requests to maximize throughput. Additionally, it proactively allocates KVC before instead of at the time a request exhausts its allocation and reserves KVC globally to prevent preemptions. (O1) (3) Preemption Policy. We order requests for preemption based on their latency SLO, remaining completion time and KVC occupancy in order to avoid SLO violation and preemptions, and reduce preemption time. (O3) (4) Preemption Strategy Selection. When the KVC size exceeds the observed sweet spot sequence length, we opt for swapping; otherwise, we choose recomputation. (O4) Experimental results show that CacheOPT achieves up to a 3.29 \times and 2.83 \times lower tail TBT and TTFT and 47% and 53% higher TTFT and TBT SLO attainments than the state-of-the-art methods, respectively. We will distribute CacheOPT ’s source code after the paper is accepted. 2 Experimental Analysis 2.1 Experiment Settings Machine settings. We used an AWS p4d.24xlarge instance, which features 8 NVIDIA A100 GPUs. Each GPU has 80GB of memory. The GPUs are interconnected via a 600 GB/s NVSwitch. We executed the OPT-13B model [ 11 ] on a single GPU, and the OPT-175B model, partitioning the model across 8 GPUs with both model and tensor parallelism degree of 2 as in [ 4 ] . Request settings. We used the Alpaca

Read the complete text