A Queueing-Theoretic Framework for Stability Analysis of LLM Inference with KV Cache Memory Constraints

The rapid adoption of large language models (LLMs) has created significant challenges for efficient inference at scale. Unlike traditional workloads, LLM inference is constrained by both computation and the memory overhead of key–value (KV) caching, which accelerates decoding but quickly exhausts GPU memory. In this paper, we introduce the first queueing-theoretic framework that explicitly incorporates both computation and GPU memory constraints into the analysis of LLM inference. Based on this framework, we derive rigorous stability and instability conditions that determine whether an LLM inference service can sustain incoming demand without unbounded queue growth. This result offers a powerful tool for system deployment, potentially addressing the core challenge of GPU provisioning. By combining an estimated request arrival rate with our derived stable service rate, operators can calculate the necessary cluster size to avoid both costly over-purchasing and performance-violating under-provisioning. We further validate our theoretical predictions through extensive experiments in real GPU production environments. Our results show that the predicted stability conditions are highly accurate, with deviations typically within 10%.

Companies worldwide rely on large language models (like ChatGPT) to power AI applications, but running these systems is extremely expensive — they require many specialized computer chips (GPUs) working around the clock. Buying too many GPUs wastes money and energy; buying too few causes the system to slow down and fail under heavy use. Currently, engineers often rely on trial-and-error or rough guesswork to decide how many GPUs they need. We developed a mathematical formula that tells operators exactly how many GPUs are required to keep an AI service running smoothly, given the expected volume and type of user requests. Our approach accounts for a key technical challenge: as the AI generates longer responses, it uses more and more memory on each GPU, limiting how many requests can be handled at once. By modeling this memory usage mathematically, we can predict the maximum number of requests a GPU can handle per second. We tested our formula on real GPU hardware and found that its predictions are accurate to within 10%. This gives AI service providers a reliable planning tool to right-size their GPU purchases — reducing both wasted resources and poor user experiences at scale.