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

arXiv: https://arxiv.org/abs/2605.04595 · HTML: https://mlsanity.com/paper/2605.04595/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Serving systems and request scheduling, one of 12 directions in Efficient LLM inference and serving.
- Builds on 24 of its 42 references that are in the map.
- First posted on arXiv 6 May 2026.

## Placed in

- Efficient LLM inference and serving / [Serving systems and request scheduling](https://mlsanity.com/inference/serving-systems-and-request-scheduling/)

## Builds on (most cited first, 24 of 24)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Efficiently Scaling Transformer Inference](https://mlsanity.com/paper/2211.05102/) (2022)
- [Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve](https://mlsanity.com/paper/2403.02310/) (2024)
- [LongBench v2: Towards Deeper Understanding and Reasoning on Realistic Long-context Multitasks](https://mlsanity.com/paper/2412.15204/) (2024)
- [SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills](https://mlsanity.com/paper/2308.16369/) (2023)
- [Fast Distributed Inference Serving for Large Language Models](https://mlsanity.com/paper/2305.05920/) (2023)
- [ORLM: A Customizable Framework in Training Large Models for Automated Optimization Modeling](https://mlsanity.com/paper/2405.17743/) (2024)
- [Long-Context Language Modeling with Parallel Context Encoding](https://mlsanity.com/paper/2402.16617/) (2024)
- [Parallel Context Windows for Large Language Models](https://mlsanity.com/paper/2212.10947/) (2022)
- [Training-Free Long-Context Scaling of Large Language Models](https://mlsanity.com/paper/2402.17463/) (2024)
- [Online Scheduling for LLM Inference with KV Cache Constraints](https://mlsanity.com/paper/2502.07115/) (2025)
- [Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints](https://mlsanity.com/paper/2504.11320/) (2025)
- [Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents](https://mlsanity.com/paper/2504.07347/) (2025)
- [A Queueing Theoretic Perspective on Low-Latency LLM Inference with Variable Token Length](https://mlsanity.com/paper/2407.05347/) (2024)
- [Adaptively Robust LLM Inference Optimization under Prediction Uncertainty](https://mlsanity.com/paper/2508.14544/) (2025)
- [Multi-Bin Batching for Increasing LLM Inference Throughput](https://mlsanity.com/paper/2412.04504/) (2024)
- [A Universal Load Balancing Principle and Its Application to Large Language Model Serving](https://mlsanity.com/paper/2601.17855/) (2026)
- [LLM Serving Optimization with Variable Prefill and Decode Lengths](https://mlsanity.com/paper/2508.06133/) (2025)
- [Queueing, Predictions, and LLMs: Challenges and Open Problems](https://mlsanity.com/paper/2503.07545/) (2025)

## Built on by (most cited first, 2 of 2)

- [Anatomy of a Quantized Agent: VRAM Stability and Forecasting in Code-Synthesis Agentic Workloads](https://mlsanity.com/paper/2608.15117/) (2026)
- [Analytical Power-Aware Provisioning for Prefill-Decode Disaggregated AI Inference](https://mlsanity.com/paper/2609.24639/) (2026)

## Abstract (arXiv)

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