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

This paper introduces Kareto, an adaptive multi-objective optimizer that efficiently navigates the complex configuration space of tiered KV cache storage to dynamically balance cost, throughput, and latency, significantly outperforming static strategies in LLM inference services.

The Gist

Imagine you are running a massive, super-smart library (a Large Language Model, or LLM) that helps people write stories, code, and answers. To work fast, this library keeps a "cheat sheet" of the most recent words it has read in its immediate memory (the GPU's HBM). This is called the KV Cache.

However, there's a problem: The cheat sheet gets huge. If too many people ask questions at once, or if the questions are very long, the cheat sheet runs out of space on the expensive, high-speed memory.

The Old Way: Buying Too Much or Too Little

Traditionally, library managers had to guess how much extra storage to buy.

• The "Over-Prepared" Manager: Buys a massive, expensive warehouse (DRAM) just in case. It's fast, but it costs a fortune, and often sits half-empty.
• The "Under-Prepared" Manager: Saves money by buying a tiny warehouse. When the cheat sheet gets too big, they have to throw things away and re-calculate everything from scratch. This makes the library slow and frustrating for users.
• The "One-Size-Fits-All" Rule: They use a simple rule like "Keep everything for 5 minutes." But some words are used again and again (like "the" or "hello"), while others are one-time only. Keeping the one-time words wastes space, and deleting the popular words too soon hurts speed.

The New Solution: Kareto (The Smart Librarian)

The paper introduces Kareto, a smart system that acts like an adaptive, data-driven librarian. Instead of guessing, Kareto figures out the perfect balance between speed, cost, and capacity automatically.

Here is how Kareto works, broken down into three simple concepts:

1. The "Crystal Ball" Simulator

Before making any changes, Kareto uses a high-fidelity simulator. Think of this as a "flight simulator" for the library.

• It takes real historical data (what people actually asked yesterday and last week).
• It runs thousands of "what-if" scenarios in a computer: "What if we have 500GB of fast memory and 2TB of slow disk? What if we keep things for 10 minutes vs. 1 hour?"
• It predicts exactly how fast the library would be and how much it would cost in each scenario.

2. Finding the "Sweet Spot" (The Pareto Frontier)

Kareto knows you can't have everything. If you want the fastest speed, it costs more. If you want the cheapest cost, it might be slower.

• Kareto draws a map of all possible options.
• It finds the Pareto Frontier: This is the "Goldilocks Zone" of configurations. These are the setups where you cannot get faster without paying more, and you cannot get cheaper without slowing down.
• It gives the library manager a menu of these perfect options, so they can choose based on their current needs (e.g., "We need speed today" vs. "We need to save money today").

3. The "Smart Filing System" (Group TTL)

This is Kareto's secret sauce. Instead of treating every piece of information the same, Kareto looks at patterns.

• The Problem: Imagine a filing cabinet where you throw out a file after 5 minutes. If a file is used 100 times an hour, throwing it out is a disaster. If a file is never used again, keeping it is a waste.
• The Kareto Fix: Kareto groups files by their "family" (prefixes).
  • Example: In a chatbot, the phrase "Once upon a time" is used in thousands of stories. Kareto sees this pattern and says, "Keep this specific family of files forever!"
  • Meanwhile, for a unique, one-time question, it says, "Throw this away immediately."
• This "Group TTL" (Time-To-Live) ensures the storage is filled with the right things, not just random things.

The Results: Why It Matters

When the researchers tested Kareto with real-world data, the results were impressive:

• Speed: It made the library 58% faster in some cases by keeping the right things in the fast memory.
• Cost: It saved 20% on costs by avoiding the purchase of unnecessary expensive memory.
• Throughput: It handled 9% more requests per second.

The Big Picture

Think of Kareto as the difference between a static, rigid robot and a flexible, intelligent human.

• Old Systems: "We have 1TB of memory. That's it. Deal with it."
• Kareto: "I see you have a rush hour on Mondays and a quiet Tuesday. I'll rent a cheap, slow warehouse for the slow days and upgrade to a fast, expensive one for the rush. Plus, I'll only keep the popular books on the front shelf and the rare ones in the basement."

Kareto turns the complex math of memory management into an automatic, self-adjusting system that saves money and makes AI faster for everyone.

Technical Summary

Here is a detailed technical summary of the paper "Adaptive Multi-Objective Tiered Storage Configuration for KV Cache in LLM Service" (Kareto).

1. Problem Statement

Large Language Model (LLM) inference services rely on KV caching (storing Key-Value vectors of previous tokens) to avoid redundant computations during autoregressive generation. However, as concurrent requests and sequence lengths increase, the memory footprint of the KV cache often exceeds the capacity of expensive GPU High-Bandwidth Memory (HBM).

To address this, systems use tiered storage (offloading to host DRAM or disk). While this expands capacity, it introduces a complex optimization challenge:

• Static Provisioning: Existing systems (e.g., vLLM, SGLang) typically use fixed storage allocations (e.g., 1TB DRAM per 8 GPUs). This leads to over-provisioning (high cost) or under-provisioning (poor performance) as workloads fluctuate dynamically.
• Multi-Objective Trade-offs: Optimizing for one metric (e.g., latency) often degrades others (e.g., cost or throughput). The relationship between storage configuration, workload patterns, and performance is non-linear and non-convex.
• Lack of Adaptability: Current solutions lack intelligent mechanisms to dynamically adjust storage size and distribution across heterogeneous tiers (HBM, DRAM, Disk) based on real-time workload characteristics and prefix reuse patterns.

2. Methodology: The Kareto Framework

The authors propose Kareto, an adaptive framework that shifts from static provisioning to elastic, workload-aware orchestration. The system consists of three main components:

A. High-Fidelity End-to-End Simulator

Since the optimization landscape is non-analytic and involves complex variable coupling, Kareto uses a simulator rather than closed-form mathematical models.

• Function: It replays historical production traces to simulate the full LLM serving pipeline, including prefill/decode phases, cache hit/miss logic, and I/O bottlenecks.
• Modeling: It captures non-linearities such as cloud pricing cliffs (e.g., AWS EBS IOPS thresholds), bandwidth saturation, and the interplay between cache hit rates and GPU utilization.
• Validation: The simulator was validated against real GPU servers, showing deviations of <19.2% for latency and <6.5% for throughput, making it a reliable proxy for optimization.

B. Adaptive Pareto Search

To navigate the massive configuration space (DRAM capacity, Disk capacity, TTL policies) efficiently, Kareto employs a diminishing-return-guided pruning strategy.

• Coarse-to-Fine Grid: It starts with a coarse grid to cover the space.
• Pruning: It monitors marginal performance gains. If increasing capacity yields diminishing returns (entering the "long-tail" regime), the search along that dimension is terminated.
• Refinement: It iteratively refines regions with high curvature or sharp trade-offs to accurately approximate the Pareto Frontier (the set of optimal configurations where no objective can be improved without worsening another).

C. ROI-Aware Group TTL (Time-to-Live)

Instead of applying a uniform TTL to all KV blocks, Kareto introduces a fine-grained adaptive tuner.

• Prefix Tree Analysis: It analyzes the reuse patterns of KV blocks grouped by their prefix subtrees.
• Group-Specific TTL: It identifies that a small fraction of subtrees accounts for the majority of reuse. It assigns specific TTLs to these groups based on their Return on Investment (ROI) (Reuse Count vs. Storage Cost).
• Optimization: It solves a constrained non-convex optimization problem (using SLSQP) to maximize total hits within a storage budget by adjusting TTLs for different block groups.

3. Key Contributions

1. Formalization of Multi-Objective Optimization: The paper formalizes the KV cache configuration problem as a Pareto optimization across Latency, Throughput, and Cost, demonstrating that closed-form solutions are infeasible due to non-linear state coupling and discontinuities.
2. Simulation-Driven Optimization: Development of a high-fidelity simulator that accurately models the interplay between workload patterns, storage tiers, and cloud pricing structures.
3. Adaptive Search Algorithm: Introduction of a search strategy that prunes low-value configurations based on diminishing returns, significantly reducing search time while maintaining Pareto frontier quality.
4. Fine-Grained Cache Management: Proposal of a Group TTL mechanism that assigns distinct retention policies to different prefix subtrees, significantly improving cache efficiency compared to "one-size-fits-all" strategies.
5. Empirical Validation: Comprehensive evaluation using real-world production traces (interactive chat, API calls, agent workflows) across different cluster scales.

4. Experimental Results

The authors evaluated Kareto using real-world traces (Trace A: Chatbot, Trace B: API, Trace C: Agent) against a baseline of 1024 GB fixed DRAM.

• Throughput: Under compute-constrained scenarios (1 instance), Kareto improved throughput by up to 9.3% by optimizing storage to reduce I/O stalls.
• Latency: Kareto reduced mean Time-To-First-Token (TTFT) by up to 58.3% by identifying configurations that minimize I/O bottlenecks.
• Cost: Kareto reduced operational costs by up to 20.2% by right-sizing storage (avoiding over-provisioning of expensive DRAM) and selecting cost-effective disk tiers.
• Ablation Studies:
  • Adaptive Search: Achieved Pareto frontier coverage comparable to exhaustive grid search but with significantly fewer simulation points (avoiding the "long tail").
  • Group TTL: Showed substantial improvements in reuse ratios and performance for workloads with structured reuse patterns (API and Agent traces), though gains were marginal for highly stochastic chat workloads.

5. Significance

This work addresses a critical bottleneck in the production deployment of LLMs: the cost-performance-efficiency triangle.

• Autonomous Management: It moves the industry away from manual, static capacity planning toward autonomous, adaptive storage management.
• Economic Efficiency: By explicitly modeling cloud pricing and storage tier economics, Kareto enables operators to achieve significant cost savings without sacrificing user experience.
• Scalability: The framework is designed to handle the dynamic nature of real-world workloads (diurnal patterns, varying concurrency), making it essential for large-scale LLM serving infrastructure.

In summary, Kareto provides a robust, simulation-driven approach to automatically configure tiered storage for LLMs, proving that dynamic, multi-objective optimization can outperform static, expert-tuned baselines in both performance and cost.