Adaptive Multi-Objective Tiered Storage Configuration for KV Cache in LLM Service

Xianzhe Zheng, Zhengheng Wang, Ruiyan Ma, Rui Wang, Xiyu Wang, Rui Chen, Peng Zhang, Sicheng Pan, Zhangheng Huang, Chuan Wu, Yi Zhang, Bo Cai, Kan Liu, Teng Ma, Yin Du, Dong Deng, Sai Wu, Guoyun Zhu, Wei Zhang, Feifei Li

TL;DR

Kareto is an automated framework designed to solve the "memory-for-computation" bottleneck in Large Language Model (LLM) serving. By using a high-fidelity simulator and a diminishing-return-guided search, it identifies the optimal balance between cost, throughput, and latency across tiered storage (GPU memory, DRAM, and Disk), outperforming static industry-standard configurations by up to 58% in latency or 20% in cost.

What Problem Does This Paper Address?

In LLM inference, KV caching is essential—it stores the mathematical "history" of a conversation so the model doesn't have to recompute every previous word for every new one generated. However, these caches are massive. While GPU High-Bandwidth Memory (HBM) is fast, it is incredibly expensive and limited in capacity.

To scale, engineers offload these caches to cheaper tiers like host DRAM or SSDs. The challenge is configuration: How much DRAM should you provision? When should you move data to disk? Most systems use "one-size-fits-all" rules (e.g., "1TB of DRAM per 8 GPUs"), which leads to either wasted money (over-provisioning) or sluggish performance (under-provisioning). Because cloud pricing is non-linear and workload patterns (like chatbot vs. batch API) vary wildly, finding the "sweet spot" is a complex multi-objective optimization problem that humans are bad at solving manually.

Methods

The authors introduce Kareto (KV-cache Adaptive REsource managemenT Optimizer), which consists of three main pillars:

  1. High-Fidelity Simulator: Since the relationship between storage and performance is non-linear and full of "cliffs" (like cloud pricing tiers), the authors built a simulator that replays real-world traces to predict how a specific hardware setup will perform without actually buying the hardware.
  2. Adaptive Pareto Search: Instead of testing every possible combination of DRAM and Disk (which would take days), Kareto uses a pruning strategy. It identifies regions of "diminishing returns"—where adding more memory barely helps performance but keeps increasing cost—and stops searching those areas to find the Pareto frontier (the set of most efficient trade-offs) quickly.
  3. ROI-Aware Group TTL: Not all KV blocks are equal. A "system prompt" (e.g., "You are a helpful assistant...") is reused constantly, while a random user query might never be seen again. Kareto uses a prefix-tree analysis to group cache blocks and assign them different Time-To-Live (TTL) values. This ensures high-value data stays in the cache while low-value data is evicted to save space.

Datasets

The researchers evaluated Kareto using three distinct types of production-style workloads:

  • Trace A (Interactive Chatbot): Characterized by multi-turn dialogues with high temporal locality.
  • Trace B (Programmatic API): Batch document processing with high prefix sharing (many requests starting with the same instructions).
  • Trace C (Agent-based): Stochastic reuse intervals where the cache is affected by the time an "agent" takes to use a tool.
  • Source: These were derived from open-source datasets (like BurstGPT) and internal Alibaba cluster traces.

Key Insights and Ideas

  • The "Pricing Cliff": Cloud providers like AWS don't scale costs linearly. Moving from one storage tier to another can cause a 13x jump in cost for a marginal gain in IOPS. Kareto’s simulator-driven approach is specifically designed to navigate these economic discontinuities.
  • Workload Density Dictates Strategy: In "low-density" workloads (few requests), the system is usually idle, so throughput is already at its max; here, Kareto focuses on minimizing latency. In "high-density" workloads, cache size scales throughput almost linearly by preventing recomputation.
  • The Power of Skew: The authors found that in some workloads, just 0.67% of KV blocks account for 90% of all cache hits. By identifying these "VIP" blocks via prefix-tree analysis, Kareto can achieve massive performance gains with very little memory.

Key Results

Compared to a standard fixed configuration (1024 GB DRAM):

  • Throughput: Improved by up to 9.3% in compute-constrained scenarios.
  • Latency: Reduced Mean Time-To-First-Token (TTFT) by up to 58.3%.
  • Cost: Lowered total operational expenditure (OPEX) by up to 20.2%.
  • Fidelity: The simulator was remarkably accurate, with only a 2.0% error rate in predicting cache hit rates compared to real-world GPU server measurements.

Limitations and Future Work

  • Periodicity Assumption: Kareto relies on the idea that "Mondays look like Mondays"—it uses historical traces from a previous window to predict the next. If a workload changes radically and suddenly (a "black swan" event), the optimization might be temporarily sub-optimal.
  • Tier Complexity: While the paper covers HBM, DRAM, and SSD, it does not deeply explore "far memory" or distributed caching across multiple nodes in a network, which is an emerging trend in massive-scale LLM clusters.
  • Future Direction: The authors suggest extending this to "serverless" LLM environments where resources need to be scaled up and down in seconds rather than hours.

Summary updated

Abstract

The memory-for-computation paradigm of KV caching is essential for accelerating large language model (LLM) inference service, but limited GPU high-bandwidth memory (HBM) capacity motivates offloading the KV cache to cheaper external storage tiers. While this expands capacity, it introduces the challenge of dynamically managing heterogeneous storage resources to balance cost, throughput, and latency under varying workloads. We formulate this as a multi-objective optimization problem: identifying the Pareto frontier across these metrics within the storage configuration space. Using a high-fidelity end-to-end simulator, we observe that the objective functions are non-analytic and exhibit complex variable coupling, making the Pareto frontier difficult to approximate analytically. To obtain the frontier, we introduce Kareto, a KV-cache Adaptive REsource managemenT Optimizer. Kareto leverages a diminishing-return-guided pruning method to efficiently navigate the large configuration space and approximate the Pareto frontier. Additionally, it incorporates a fine-grained adaptive tuner that uses eviction policies in tier storage and KV block access patterns for group-specific cache management, improving cache efficiency. Experiments on real-world traces show that Kareto adapts to workload and can identify configurations of better cost efficiency, covering static strategies. Compared to the fixed setup with 1024 GB DRAM, Kareto can improve throughput by up to 9.3%, or reduce latency by up to 58.3%, or lower cost by up to 20.2% under respective optimization objectives.
BibTeX
@misc{zheng2026adaptive,
  author = {Xianzhe Zheng and Zhengheng Wang and Ruiyan Ma and Rui Wang and Xiyu Wang and Rui Chen and Peng Zhang and Sicheng Pan and Zhangheng Huang and Chuan Wu and Yi Zhang and Bo Cai and Kan Liu and Teng Ma and Yin Du and Dong Deng and Sai Wu and Guoyun Zhu and Wei Zhang and Feifei Li},
  title = {{Adaptive Multi-Objective Tiered Storage Configuration for KV Cache in LLM Service}},
  year = {2026},
  eprint = {2603.08739},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.08739},
}

Loading related content...

Figure