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:
- 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.
- 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.
- 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