Research map / Large language models / Reasoning and chain of thought

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

ICML 2026 · Large language models › Reasoning and chain of thought · approach: Efficient LLM serving · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Derives a queueing-theoretic stability condition for LLM inference on a KV-cache-memory-constrained GPU (service rate mu = M / (b̄ E[g(s,o)])) and validates it against vLLM runs on A100s with Llama-3-8B, reporting gaps mostly under 10%.

Problem

Predicting when an LLM inference service with a KV cache memory limit remains stable (bounded queue) under stochastic request arrivals, which is needed for GPU provisioning; existing queueing models ignore memory constraints.

Approach

Model the GPU as a discrete-time queue with a memory budget M; collapse each request's lifetime KV memory usage into g(s,o) and define the service rate as M divided by the mean lifetime memory times batch time, proving overload if lambda > mu and Foster-Lyapunov stability if lambda < mu(1-delta).

Key results

• Single-GPU Llama-3-8B theoretical service rate matches measured rate with GAP 2.25% to 8.38% across 1:1, 2:1, 1:2 PD ratios.
• LongBench v2 workload: mu_theory 0.561 vs mu_gpu 0.610, GAP 8.03%.
• 8-GPU round-robin deployment: mu_theory x8 = 25.808 vs measured 26.710, GAP 3.38%.

Surprising findings

• Under an 8:1 PD ratio with heavy-tailed batch times, the mean and median are poor estimators of batch time, requiring trimmed means (GAP 7.2% to 9.0%).

Limitations

• Assumes near-constant batch processing time, justified only in the near-capacity regime and empirically for some workloads.
• Analysis covers only single-GPU worker and data-parallel replicas; tensor parallelism, pipeline parallelism and prefill-decode disaggregation are not analyzed.
• Assumes the Markov chain is irreducible and treats delta as small; the paper is evaluated on one model (Llama-3-8B) and a small set of workloads.

Experimental setup

Datasets: LongBench v2 synthetic uniform prefill/decode length workloads

Benchmarks: LongBench v2 request-length workload synthetic PD-ratio workloads on single and 8-GPU A100 testbed

Metrics: service rate mu GAP (absolute percentage error) queue length over time waiting-time CDF

Baselines: Best-Fit scheduling

Builds on: vLLM SARATHI chunked prefill Foster-Lyapunov criterion stochastic bin packing

Closest papers by meaning

• Demystifying Cost-Efficiency in LLM Serving over Heterogeneous GPUs (ICML 2025 · similarity 0.89)
• Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practice (NeurIPS 2026 · similarity 0.88)
• Taming the Fragility of KV Cache Eviction in LLM Inference (ICLR 2026 · similarity 0.88)
• SpeCache: Speculative Key-Value Caching for Efficient Generation of LLMs (ICML 2025 · similarity 0.88)
• Practical Offloading for Fine-Tuning LLM on Commodity GPU via Learned Sparse Projectors (AAAI 2025 · similarity 0.88)
• Beyond Prediction: Tail-Aware Scheduling for LLM Inference (ICML 2026 · similarity 0.88)