Service-Induced Congestion in Memory-Constrained LLM Serving
Abstract
In large language model (LLM) serving, each request accumulates persistent graphics processing unit (GPU) memory during service as its key-value cache grows with every generated token. Under high concurrency, aggregate memory usage therefore increases endogenously over time: the service process itself creates future capacity pressure. When memory capacity is exceeded, systems evict active requests, discarding cached state and restarting them later, which wastes computation and reduces throughput. We develop a discrete-time dynamical model of memory-constrained LLM inference that captures admission, memory growth, and eviction under continuous batching. In the saturated-input regime, the system admits both eviction-free fixed points and limit cycles with evictions. For homogeneous workloads, we show that the eviction-free equilibrium is unstable and that, except for a Lebesgue-measure-zero exact-capture set, the system converges to a unique worst-case limit cycle that is asymptotically stable outside this exceptional set, with throughput losses as large as 50%. For heterogeneous workloads, we prove a stability criterion in the two-class common-input setting and explain how the survival-polynomial mechanism generalizes to multiple classes and heterogeneous-input lengths. Under an input-dominated scaling regime, coprime decoding lengths stabilize the eviction-free equilibrium, while non-coprime lengths create synchronized modes that drive instability. These results characterize when workload heterogeneity desynchronizes completions and helps stabilize memory-constrained serving. More broadly, we identify service-induced congestion as a structural instability mechanism and derive scheduling design principles for sustaining high throughput.
Related
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Effective Dissipation and Asymptotic Stability in a Finite-Level Quantum System with Wave-Induced Memory
- Boundary-Level-Constrained Refinement for Suppressing Trimming-Induced High-Frequency Outliers in Explicit Isogeometric Analysis
- Memory-induced blow-up solutions and their dynamical transitions in distributed delay differential equations
- Monotonicity, Uniqueness and Frank--Wolfe Dynamics in Atomic Splittable Congestion Games
BibTeX
@misc{ao2026serviceinduced,
title = {{Service-Induced Congestion in Memory-Constrained LLM Serving}},
author = {Ruicheng Ao and Jing Dong and Gan Luo and David Simchi-Levi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.15555},
eprint = {2606.15555},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.15555},
}
RIS
TY - UNPB
TI - Service-Induced Congestion in Memory-Constrained LLM Serving
AU - Ruicheng Ao
AU - Jing Dong
AU - Gan Luo
AU - David Simchi-Levi
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2606.15555
UR - https://arxiv.org/abs/2606.15555
AB - In large language model (LLM) serving, each request accumulates persistent graphics processing unit (GPU) memory during service as its key-value cache grows with every generated token. Under high concurrency, aggregate memory usage therefore increases endogenously over time: the service process itself creates future capacity pressure. When memory capacity is exceeded, systems evict active requests, discarding cached state and restarting them later, which wastes computation and reduces throughput. We develop a discrete-time dynamical model of memory-constrained LLM inference that captures admission, memory growth, and eviction under continuous batching. In the saturated-input regime, the system admits both eviction-free fixed points and limit cycles with evictions. For homogeneous workloads, we show that the eviction-free equilibrium is unstable and that, except for a Lebesgue-measure-zero exact-capture set, the system converges to a unique worst-case limit cycle that is asymptotically stable outside this exceptional set, with throughput losses as large as 50%. For heterogeneous workloads, we prove a stability criterion in the two-class common-input setting and explain how the survival-polynomial mechanism generalizes to multiple classes and heterogeneous-input lengths. Under an input-dominated scaling regime, coprime decoding lengths stabilize the eviction-free equilibrium, while non-coprime lengths create synchronized modes that drive instability. These results characterize when workload heterogeneity desynchronizes completions and helps stabilize memory-constrained serving. More broadly, we identify service-induced congestion as a structural instability mechanism and derive scheduling design principles for sustaining high throughput.
ER -