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

• URL: http://arxiv.org/abs/2605.04595v1
• Date: Wed, 06 May 2026 07:42:26 GMT
• Title: A Queueing-Theoretic Framework for Stability Analysis of LLM Inference with KV Cache Memory Constraints
• Abstract summary: We introduce the first queueing-theoretic framework that explicitly incorporates both computation and GPU memory constraints.<n>We derive rigorous stability and instability conditions that determine whether an LLM inference service can sustain incoming demand without unbounded queue growth.<n>Our results show that the predicted stability conditions are highly accurate, with deviations typically within 10%.
• Score: 4.636275494777427
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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%.

Related papers

• LLM Inference in a Flash! [66.43896490006965]
  Large Language Models (LLMs) have shown impressive capabilities across a range of natural language processing tasks.<n>We present an end-to-end integer-only quantization approach to eliminate expensive floating-point computations.
  arXiv  Detail & Related papers  (2026-09-14T18:04:30Z)
• OScaR: The Occam's Razor for Extreme KV Cache Quantization in LLMs and Beyond [50.440302567029654]
  Multi-modal intelligence has made the Key-Value cache a dominant memory bottleneck for efficient deployment.<n>In this work, we revisit the inherent limitations of the per-channel quantization paradigm.<n>We propose OScaR, an accurate and lightweight KV cache compression framework for X-LLMs.
  arXiv  Detail & Related papers  (2026-05-19T10:53:03Z)
• $\ abla$-Reasoner: LLM Reasoning via Test-Time Gradient Descent in Latent Space [71.23672814629448]
  $nabla$-Reasoner is an iterative generation framework that integrates differentiable optimization over token logits into the decoding loop.<n>$nabla$-Reasoner achieves over 20% accuracy improvement on a challenging mathematical reasoning benchmark.
  arXiv  Detail & Related papers  (2026-03-05T08:42:54Z)
• Fast KVzip: Efficient and Accurate LLM Inference with Gated KV Eviction [50.99402504483692]
  We propose a novel gating-based KV cache eviction method for frozen-weight language models.<n>Our approach integrates seamlessly into both the prefill and decoding stages.<n>Experiments show that our method maintains near-lossless performance while evicting up to 70% of the KV cache.
  arXiv  Detail & Related papers  (2026-01-25T03:07:54Z)
• Toward Robust and Efficient ML-Based GPU Caching for Modern Inference [28.13206649836587]
  We present textscLCR, a framework for learning-based GPU caching.<n>Its core algorithm, textscLARU, enhances textscLRU with machine-learned predictions and dynamically adapts to prediction accuracy through online error estimation.<n>Experiments show it improves throughput by up to 24.2% and reduces P99 TTFT by up to 28.3%, outperforming widely used inference systems.
  arXiv  Detail & Related papers  (2025-09-25T10:23:50Z)
• READER: Retrieval-Assisted Drafter for Efficient LLM Inference [0.0386965802948046]
  Autoregressive Language Models instantiate a factorized likelihood over token sequences, yet their strictly sequential decoding process imposes an intrinsic lower bound on latency inference.<n>This bottleneck has emerged as a central obstacle to the scalable deployment of large-scale generative models.<n>We present READER, a speculative decoding framework that bypasses the training of the auxiliary draft model.
  arXiv  Detail & Related papers  (2025-08-12T16:47:48Z)
• Beyond Homogeneous Attention: Memory-Efficient LLMs via Fourier-Approximated KV Cache [67.47789629197857]
  We propose a training-free framework that exploits the heterogeneous roles of transformer head dimensions.<n>By projecting the long-context-insensitive dimensions onto Fourier bases, FourierAttention approximates their temporal evolution with fixed-length spectral coefficients.<n>We show that FourierAttention achieves the best long-context accuracy on LongBench and Needle-In-A-Haystack.
  arXiv  Detail & Related papers  (2025-06-13T15:35:54Z)
• The Larger the Merrier? Efficient Large AI Model Inference in Wireless Edge Networks [56.37880529653111]
  The demand for large computation model (LAIM) services is driving a paradigm shift from traditional cloud-based inference to edge-based inference for low-latency, privacy-preserving applications.<n>In this paper, we investigate the LAIM-inference scheme, where a pre-trained LAIM is pruned and partitioned into on-device and on-server sub-models for deployment.
  arXiv  Detail & Related papers  (2025-05-14T08:18:55Z)
• Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints [14.341123057506827]
  Large Language Models (LLMs) are indispensable in today's applications, but their inference procedure demands significant computational resources.<n>This paper formulates LLM inference optimization as a multi-stage online scheduling problem.<n>We develop a fluid dynamics approximation to provide a tractable benchmark that guides algorithm design.
  arXiv  Detail & Related papers  (2025-04-15T16:00:21Z)
• Online Scheduling for LLM Inference with KV Cache Constraints [22.133592174540052]
  Large Language Model (LLM) inference is an intensive process requiring efficient scheduling to optimize latency and resource utilization.<n>We propose a novel and theoretically scheduling algorithm that minimizes inference latency while effectively managing the KV cache's memory.
  arXiv  Detail & Related papers  (2025-02-10T23:11:44Z)
• SqueezeLLM: Dense-and-Sparse Quantization [80.32162537942138]
  Main bottleneck for generative inference with LLMs is memory bandwidth, rather than compute, for single batch inference. We introduce SqueezeLLM, a post-training quantization framework that enables lossless compression to ultra-low precisions of up to 3-bit. Our framework incorporates two novel ideas: (i) sensitivity-based non-uniform quantization, which searches for the optimal bit precision assignment based on second-order information; and (ii) the Dense-and-Sparse decomposition that stores outliers and sensitive weight values in an efficient sparse format.
  arXiv  Detail & Related papers  (2023-06-13T08:57:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.