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

Problem Statement

The rapid proliferation of Large Language Models (LLMs) has created significant challenges for efficient large-scale inference. Unlike traditional workloads, LLM inference is constrained by a dual bottleneck: computational power and memory requirements driven by Key-Value (KV) caching. While KV caching accelerates decoding by reusing representations of previously generated tokens, it consumes substantial GPU memory and often becomes the primary capacity constraint.

Existing queueing models for LLM inference typically focus on computational limits or treat memory as a static constraint, thereby failing to capture the dynamic interplay between computation and memory growth during the inference process. Specifically, the memory requirement of a request evolves linearly as it progresses through the prompt phase (Prefill) and the token generation phase (Decode). When the arrival rate of requests exceeds the system's effective service rate—determined jointly by GPU computational power and available KV-cache memory—queues grow unbounded, leading to system instability, unacceptable latency, and degraded user experience. There is a lack of rigorous theoretical frameworks that explicitly incorporate these dynamic memory constraints to determine stability conditions and guide GPU provisioning.

Methodology

The authors propose a novel queueing-theoretic framework that models LLM inference as a discrete-time, work-conserving queueing system subject to a hard KV-cache memory constraint ($M$).

1. System Model

• Request Structure: Each request $i$ consists of a prompt of size $s_i$ and an output of length $o_i$, drawn from a joint distribution $F_{in-out}$.
• Processing Phases:
  • Prompt Phase: Prompts are processed in fixed-size blocks ($\hat{s}$). The memory requirement for the $j$-th block of a prompt grows linearly ($j \times \hat{s}$).
  • Decode Phase: As tokens are generated sequentially, the memory requirement increases by the KV-cache of one token per step. The total memory requirement of a request reaches $s_i + o_i$ upon completion.
• Memory Constraint: The system must satisfy the condition $\sum_{i \in S(t)} (c_i^{(t)}\hat{s} + d_i^{(t)}) \le M$ at all times $t$, where $S(t)$ is the set of active requests, $c_i^{(t)}$ is the index of the processed prompt block, and $d_i^{(t)}$ is the index of the processed output token.
• Scheduling: The framework assumes Continuous Batching and work-conserving strategies (e.g., First-Come-First-Served), where the server processes the next prioritized prompt as soon as capacity becomes available.

2. Theoretical Derivation

The authors define the cumulative memory requirement over the lifetime $g(s, o)$ for a single request, representing the entire "area" of memory consumed over the full service time of a request.
$$g(s, o) := \sum_{k=1}^{s/\hat{s}} k\hat{s} + \sum_{j=1}^{o} (s+j)$$
Based on this, they derive the maximum stable service rate $\mu$:
$$\mu = \frac{M}{\bar{b} \mathbb{E}_{s,o \sim p(s,o)}[g(s, o)]}$$
where $\bar{b}$ is the normalized batch processing time.

3. Stability Analysis

Using a Lyapunov drift argument adapted to the piecewise linear memory dynamics of LLMs, the work establishes two central theorems:

• Instability: If the arrival rate $\lambda > \mu$, the system is overloaded, and the number of requests grows to infinity.
• Stability: If $\lambda < \mu(1 - \delta)$, where $\delta = \frac{\text{ess sup}(s+o)}{M} \ll 1$ represents the memory buffer required to accommodate the largest single request, the system is stable (positive recurrent Markov chain).

Main Contributions

1. Novel Modeling: The work presents the first queueing model for LLM inference that explicitly integrates both computational requirements and dynamic GPU memory constraints governed by KV caching. It generalizes previous models by introducing memory awareness and refining scheduling setups with chunked prefill phases.
2. Rigorous Stability Conditions: The authors derive closed-form stability and instability conditions. These results provide a principled foundation for determining the maximum sustainable throughput of an LLM service system under stochastic workloads.
3. Empirical Validation: Theoretical predictions were validated through extensive experiments in real-world GPU production environments (NVIDIA A100), covering both single-GPU and multi-GPU configurations (data parallel).

Experimental Results

The authors conducted experiments using the Meta-Llama-3-8B model on an 8-GPU testbed with the vLLM inference engine.

• Accuracy: The theoretical service rate $\mu_{theory}$ closely matches the empirically measured rate $\mu_{gpu}$. Across various prompt-to-decode ratios (P/D) (1:1, 2:1, 1:2) and a real-world dataset (LongBench v2), the prediction error (Gap Absolute Percentage) remained within 10% (specifically ranging from 2.25% to 8.38%).
• Multi-GPU Scalability: In an 8-GPU cluster setup, the theoretical model scaled linearly, achieving a deviation of only 3.38% between predicted and observed rates.
• Stability Dynamics: Experiments confirmed that when $\lambda < \mu$, queue lengths remained bounded (e.g., $\le 5$ for a single GPU), whereas $\lambda > \mu$ led to linear, unbounded queue growth.

Significance and Claims

The work claims to provide a powerful tool for system deployment and resource provisioning. By combining an estimated request arrival rate with the derived stable service rate, operators can calculate the required cluster size to:

• Avoid costly over-provisioning (idle GPUs).
• Prevent performance-violating under-provisioning (unbounded queues and latency spikes).

The authors emphasize that their framework offers a "principled foundation" for capacity planning, enabling practitioners to quantitatively balance capacity and demand. They note that while their current focus is on data-parallel deployments, the framework can be extended to tensor parallelism by adjusting effective memory and batch time parameters, while pipeline parallelism and disaggregation require further investigation. The results confirm that incorporating memory dynamics into queueing models is essential for accurate stability analysis in modern LLM service systems.