Large Language Models (LLMs) are everywhere, but serving them is notoriously expensive. While training is a massive one-time cost, inference is an ongoing financial and environmental drain. Current inference systems often treat the process as a "black box," leading to suboptimal scheduling and wasted GPU resources.
In this paper, researchers from EPFL, NUS, and Ceres Technologies argue that we should treat LLM inference more like a database management system (DBMS). By applying classic database principles—like cost modeling, strategic preemption, and smart cache replacement—they demonstrate how to make LLM serving significantly faster and cheaper.
TL;DR
By treating the LLM "KV cache" like a database buffer and implementing a "Shortest-Request First" (SRF) preemption policy, this paper achieves up to a 15% performance boost in real-world systems and identifies theoretical paths to 40% savings. It challenges the conventional wisdom that preemption should always be avoided, proving that strategically "kicking out" short requests can actually clear the way for higher overall throughput.
What Problem Does This Paper Address?
The bottleneck in LLM inference isn't just raw computation; it's the KV cache. To generate text efficiently, models store intermediate mathematical states (Key-Value embeddings) in GPU memory. As more requests arrive, this memory fills up.
When the cache is full, current systems face a dilemma: either stop accepting new requests (increasing wait times) or "preempt" (pause and evict) an existing request. Most current schedulers are "preemption-conservative," meaning they try to avoid pausing requests at all costs because restarting them requires recomputing those intermediate states. However, this often leads to massive delays (high Time-to-First-Token) and underutilized GPUs. The authors identify a lack of adequate resource cost models to navigate this trade-off effectively.
Methods
The authors introduced InferMax, a framework that brings database-style optimization to LLMs through three main components:
- Analytical Cost Models: Instead of relying on "black box" behavior, they built linear models that predict batch execution times based on hardware metrics (GPU bandwidth and FLOPS) and request characteristics.
- Constraint Satisfaction Problem (CSP) Formulation: They were the first to formulate LLM scheduling as a CSP. This allows them to find the mathematically "optimal" schedule for any given workload, providing a benchmark for how much better current systems could be.
- Shortest-Request First (SRF) Policy: Inspired by the "Five-Minute Rule" in databases, they proposed a new cache replacement policy. When memory is full, the system preempts the shortest requests first. This is counter-intuitive but brilliant: short requests are the cheapest to recompute ("refill") later, and clearing them out allows the system to maintain a higher "progress" rate for the workload as a whole.
Datasets
The researchers evaluated their approach using:
- AzureConv: A 1-hour online trace of 19.7K real-world conversation requests from Microsoft Azure.
- LongForm: A dataset of 2K requests focused on long-form text generation.
- Hardware/Models: Evaluations were performed on NVIDIA A100 and H100 GPUs using Llama-2 (7B) and Llama-3 (8B and 70B) models.
Key Insights and Ideas
- Preemption is a Tool, Not a Failure: The most surprising finding is that being too conservative about preemption can slow down a system by 2x. Preempting short requests under high contention actually improves performance because their "restart tax" is low compared to the throughput gains of clearing the queue.
- The Memory Wall is Real: Roofline analysis showed that LLM "attention" mechanisms are almost always memory-bandwidth bound, not compute-bound. This means adding more "compute" (FLOPS) won't help as much as faster memory or smarter cache management.
- The Five-Minute Rule for LLMs: The authors adapted a 1987 database rule to calculate exactly how long a KV cache item should stay in memory before it's cheaper to just recompute it later. They found that longer requests should actually be evicted sooner if they aren't being actively used, as their memory footprint is disproportionately large.
Key Results
- Real-World Speedups: When deployed in the popular
vLLMinference engine, the SRF policy (combined with a histogram-based length predictor) reduced latency by up to 15% without sacrificing fairness or accuracy. - Theoretical Potential: Their CSP analysis showed that in high-contention scenarios, strategic preemption can reduce latency by up to 40% compared to preemption-free schedules.
- Cost Savings: For a service at the scale of ChatGPT, the authors estimate these optimizations could translate to over $3 million in monthly GPU savings.
- Model Accuracy: Their simple linear cost models achieved an average relative error of only 6%, proving that you don't need complex machine learning to predict LLM performance—just good physics-based modeling.
Limitations and Future Work
- CSP Scalability: Solving the scheduling problem as a CSP is computationally heavy (NP-complete). While great for analysis, it's currently too slow to use for real-time scheduling of thousands of requests.
- Independent Requests: The current study assumes requests are independent. Future work is needed to apply these DBMS-inspired policies to "prefix sharing," where multiple users might share the same prompt context (e.g., a shared system prompt).
- Disaggregated Systems: The authors suggest extending this work to "disaggregated" setups where the "prefill" (initial processing) and "decode" (token generation) phases happen on different GPUs.
Summary updated