Service-Induced Congestion in Memory-Constrained LLM Serving

arXiv:2606.15555 · math.OC, cs.AI, cs.LG, stat.ML · Submitted 2026-06-14 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: We're looking at the paper: "Service-Induced Congestion in Memory-Constrained LLM Serving".

Jane: Here's the gist of the paper. The original text (A) provides the high-level system description, motivation, and proposed solutions in terms of service dynamics, while the second text (B) delves into the rigorous mathematical proofs underpinning these claims concerning stability criteria based on decoding lengths.

Tom: Here is a long and detailed synthesis of the paper: Comprehensive Research Summary: Service-Induced Congestion in Memory-Constrained LLM Serving This research addresses a critical, emergent problem in large language model (LLM) serving infrastructure: service-induced congestion arising from the progressive, endogenous accumulation of GPU memory usage during continuous request processing.

Jane: As each request generates tokens and its key–value cache grows, the aggregate memory footprint of the service process increases over time.

Tom: When this usage exceeds physical capacity, the system is forced to evict active requests—discarding their cached state and requiring a costly restart later—which directly degrades throughput.

Paper summary: Tom: So we’re looking at this paper called "Service-Induced Congestion in Memory-Constrained LLM Serving." It seems to be about how memory usage in an AI service keeps growing over time just because requests are running continuously.

Jane: Right, so the main idea here is that as each request generates tokens, its key value cache grows with every step of generation. That means the total GPU memory used by the service process increases steadily as more requests are active at once.

Tom: Exactly, and when that usage hits a limit, you have to start evicting active requests. This means throwing away their cached state and having to restart them later, which just wastes computation time and cuts down on how much work we can get done in a given period.

Lu: What’s really interesting here is the model they use—it’s a discrete-time dynamical model that tries to capture the interaction between admitting new jobs, the memory growth itself, and when those evictions happen under continuous batching.

Meng: From where I stand at a startup, I see this as something that breaks my production systems. We worry about what happens at scale and how it actually runs in a real environment.

Lalam: Lalam sees this paper focusing on the saturated-input regime, which is when the system is running at its maximum possible input capacity. In that regime, they admit both scenarios: a steady state where no evictions happen and limit cycles where evictions do occur.

Jane: That’s a really concrete starting point. So, for simple cases—homogeneous workloads—what does this model tell us about stability? Is it stable without evictions?

Tom: The paper shows that for homogeneous workloads, the eviction-free equilibrium is unstable under standard batching dynamics. This means you can't just assume everything stays perfectly smooth and stable.

Lu: Instead, they find that the system converges to a unique worst-case limit cycle where evictions are happening regularly, and this happens outside of a set of measure zero. It’s not perfectly stable in the ideal sense.

Jane: A limit cycle with evictions means things keep oscillating—memory fills up, we evict, then it fills up again—and that oscillation is persistent unless something specific changes.

Meng: That sounds like exactly what happens when you try to deploy a model without accounting for this kind of resource pressure. If we don't fix the admission control, we’re just going to see throughput drop by whatever amount that limit cycle dictates.

Tom: And it gets more complex when you move into heterogeneous workloads, which is where the math gets really specific about decoding lengths.

Lu: For those heterogeneous workloads, they establish a stability criterion in the two-class common-input setting. The eviction-free equilibrium is stable if and only if the two decoding lengths are coprime.

Jane: Coprime decoding lengths mean their greatest common divisor is one, which essentially means their completion phases drift away from each other over time instead of lining up perfectly.

Paper summary: Tom: That’s the mechanism they pinpoint for stability here: synchronization drives instability when those lengths share a common divisor greater than one. Shared divisors cause completion events to align periodically, creating those oscillatory modes we talked about earlier.

Meng: So if my input requests all have decoding lengths that are not coprime, I’m looking at a system that is structurally prone to evictions regardless of how much memory I allocate initially. That's a real headache for deployment planning.

Lalam: Lalam confirms that this synchronization issue is what drives the instability, and it suggests how workload heterogeneity can actually be used to stabilize serving environments by desynchronizing those completion phases.

Jane: So if we want stability in a heterogeneous system, the authors suggest two things: either we need to ensure our lengths are coprime, or we need to actively manage them.

Tom: And the paper proposes concrete operational policies for that management. They suggest rate-limited admission control when they see those common divisors causing instability. This stops the memory pressure from escalating by controlling how fast new requests get in while still trying to keep throughput high.

Lu: And for systems where you have non-coprime lengths, they suggest request mixing as another way to stabilize things. Mixing different classes of requests can effectively reduce that GCD down toward one, breaking up the synchronized modes that cause the instability.

Meng: Request mixing sounds complicated to set up in a production pipeline, but if it genuinely helps prevent those fifty percent throughput losses they mentioned, I’d look into it. That number for loss is pretty significant when you're shipping models.

Jane: It really puts things into perspective that this isn't just an academic curiosity about memory usage; it’s a structural problem in how we design the service itself when dealing with AI inference at scale.

Tom: To wrap up, the paper "Service-Induced Congestion in Memory-Constrained LLM Serving" is essentially diagnosing why memory pressure causes throughput collapses by looking at the discrete-time dynamics of admission and eviction under continuous batching.

Lu: The core finding is that for homogeneous workloads, the ideal state isn't stable; it’s a limit cycle with evictions unless you change something about the input structure.

Jane: And for heterogeneous workloads, stability depends entirely on whether those decoding lengths are coprime to each other. That number theoretic relationship is the key to keeping things running smoothly.

Meng: For anyone building these services, it means you need to think about request patterns and not just raw memory limits when you design your queuing and admission controls.

Lalam: Lalam says the implication is that we can use knowledge about the workload's arithmetic structure—the GCD of the decoding lengths—as a diagnostic tool to predict eviction risk before it actually happens.

Tom: So, for anyone listening, this paper gives us a mathematical way to understand why service-induced congestion happens and how specific scheduling designs can sustain high throughput even under memory constraints.

Conclusion: Tom: So we’ve been looking at this paper titled "Service-Induced Congestion in Memory-Constrained LLM Serving."

Jane: It’s about how the memory needed for an AI service actually grows over time because of continuous requests, and that growth eventually causes problems.

Tom: Right. The authors are focusing on a discrete-time dynamical model to show exactly how that memory pressure leads to system instability under continuous batching.

Jane: What they found is that this isn't just a slow leak; it’s a structural problem where the service process itself creates its own capacity pressure, and when it hits the wall, you get evictions.

Tom: They spend a lot of time on the mathematical proofs showing that this behavior can be predicted based on things like decoding lengths, which is really interesting for me as an engineer.

Jane: And they show that whether the system stays stable or goes into a cycle depends heavily on whether those decoding lengths are coprime to each other.

Tom: That’s a big takeaway because it means we have a concrete way to diagnose when our request patterns are going to cause problems before the actual evictions start happening.

Jane: Exactly. It moves the conversation from just managing memory limits, which is reactive, to understanding the underlying number theory of how jobs finish and how that affects system stability.

Tom: Yeah, it suggests that if we can monitor those GCD values—the greatest common divisor of active requests—we can proactively design scheduling policies to keep things running efficiently.

Jane: So we’re looking at a paper here that essentially gives us the blueprint for designing robust AI serving infrastructure by making the arithmetic structure of our workload a key part of our stability analysis.

Tom: And it sets up a really clear path for future work, I think, focusing on how these ideas translate into actual production scheduling decisions.

Ruicheng Ao, Jing Dong, Gan Luo, David Simchi-Levi

Massachusetts Institute of Technology · Columbia University · Peking University

math.OC, cs.AI, cs.LG, stat.ML

Submitted: 2026-06-14

Updated: 2026-10-20

Comments: 100 pages. v2: adds GPU experiments with benchmark workloads (Appendix D.4) and revises the figures

Code: https://github.com/NVIDIA/TensorRT-LLM

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 88/100

The gist: The original text (A) provides the high-level system description, motivation, and proposed solutions in terms of service dynamics, while the second text (B) delves into the rigorous mathematical

Key concepts

Service-Induced Congestion: This is instability caused when the GPU memory used by ongoing LLM requests grows over time. As requests generate tokens, their cache increases, eventually exceeding physical capacity. This forces the system to evict active requests, causing costly restarts and reducing overall service speed.
Decoding Lengths: These are the lengths of text generated for individual LLM requests. The paper uses these lengths to determine if memory release events will align or desynchronize. Their mathematical relationship (specifically their greatest common divisor) dictates whether the system remains stable or enters a cycle of evictions.
Limit Cycles: These are persistent, repeating patterns in the system's behavior when it is unstable. In this context, a limit cycle means the service repeatedly enters a state where memory usage grows and then triggers an eviction, leading to predictable but poor performance and throughput loss.

Terminology

Continuous Batching — 1× in this paper · explained in 2 episodes
Fixed Point — 1× in this paper · explained in 2 episodes
Large Language Model (LLM) — 1× in this paper · explained in 3 episodes
Limit Cycles — 1× in this paper · explained in 3 episodes

Summary

The original text (A) provides the high-level system description, motivation, and proposed solutions in terms of service dynamics, while the second text (B) delves into the rigorous mathematical proofs underpinning these claims concerning stability criteria based on decoding lengths.

Here is a long and detailed synthesis of the paper:

Comprehensive Research Summary: Service-Induced Congestion in Memory-Constrained LLM Serving

This research addresses a critical, emergent problem in large language model (LLM) serving infrastructure: service-induced congestion arising from the progressive, endogenous accumulation of GPU memory usage during continuous request processing. As each request generates tokens and its key–value cache grows, the aggregate memory footprint of the service process increases over time. When this usage exceeds physical capacity, the system is forced to evict active requests—discarding their cached state and requiring a costly restart later—which directly degrades throughput. This progressive resource consumption creates a self-reinforcing cycle: the service process's future capacity pressure dictates its current eviction policy, leading to instability and performance degradation.

The paper develops a discrete-time dynamical model to formally capture the complex interactions among three key system components: admission control, memory growth, and eviction dynamics under continuous batching.

Core Findings on System Stability and Congestion Mechanism

The central contribution of the work lies in establishing sharp, mathematically rigorous criteria that dictate whether a memory-constrained system will remain stable (i.e., maintain high throughput without excessive eviction) or enter a state of persistent instability driven by service congestion. This stability hinges critically on the arithmetic structure of decoding lengths associated with different requests.

Homogeneous Workloads (Fixed Job Sizes):

The analysis demonstrates that under standard batching dynamics, the eviction-free equilibrium (a state where no evictions occur) is inherently unstable.
Instead, the system converges to a unique worst-case limit cycle that is asymptotically stable outside of a set of measure zero. This limit cycle represents persistent oscillations in memory usage and eviction patterns, resulting in throughput losses potentially as high as 50%.

Heterogeneous Workloads (Varying Job Sizes):

The stability criterion becomes highly dependent on the relationship between the decoding lengths of different request classes.
A sharp stability criterion is established in the two-class common-input setting: The eviction-free equilibrium is asymptotically stable if and only if the two decoding lengths are coprime (i.e., their greatest common divisor, GCD, is 1).
The underlying mechanism for this stability under heterogeneity is synchronization. When decoding lengths share a common divisor (GCD > 1), completion events align periodically. This periodic alignment drives persistent oscillatory modes that destabilize the system. Conversely, when the decoding lengths are coprime (GCD = 1), their completion phases drift relative to one another, effectively desynchronizing memory release and damping perturbations, thus maintaining stability.

Proposed Mitigation Policies

To counteract this structural instability mechanism—service-induced congestion—the authors propose two distinct operational policies:

Rate-Limited Admission Control: When the system detects that the eviction-free equilibrium is unstable (i.e., when decoding lengths share a common divisor), the proposed policy is to rate-limit admission. This prevents memory pressure from escalating by controlling the rate at which new requests are admitted, effectively preventing evictions entirely over a simulated horizon while sustaining high throughput.
Request Mixing for Heterogeneous Systems: For systems exhibiting synchronization issues (non-coprime lengths), the paper advocates for request mixing. By strategically mixing different request classes, the effective GCD of the system can be reduced toward 1, thereby desynchronizing completion phases and mitigating the periodic eviction cycles that drive instability.

Mathematical Rigor and Underlying Mechanisms

The mathematical foundation supporting these operational insights is exceptionally robust. The analysis utilizes advanced techniques from dynamical systems theory:

Characteristic Polynomial Analysis: The stability of the system is directly linked to the roots of a characteristic polynomial derived from the system's dynamics. When GCD = 1, all relevant roots lie strictly inside the unit circle, guaranteeing global convergence to a stable state. When GCD > 1, certain roots drift outside this disk, leading to spectral instability.
Synchronization as Instability Driver: The paper precisely identifies that shared divisors cause periodic alignment of completion events, which manifests as persistent oscillatory modes—the mathematical signature of the service-induced congestion.
Diagnostic Tool: The authors conclude by proposing a practical diagnostic: monitoring the effective greatest common divisor (GCD) of active workloads can serve as a model-informed structural indicator for assessing immediate eviction risk.

In essence, this work moves beyond merely describing memory pressure; it provides a structural diagnosis rooted in number theory and dynamical systems, explaining why congestion occurs and offering precise, mathematically validated strategies—rate limiting or mixing—to engineer stability and maximize throughput in real-world LLM serving environments.

Improvements for AI systems

Adaptive admission control can be implemented by capping aggregate admission at an eviction-free equilibrium rate (x star). This prevents admission pulses that drive instability while maintaining high throughput when demand is below capacity, mitigating eviction cascades.
Request mixing for heterogeneous systems should be used to route requests so that the greatest common divisor of their decoding lengths equals one. This reduces the synchronization of completion events, which dampens memory release bursts and stabilizes the system against eviction cycles.
A structural diagnostic tool can monitor the effective greatest common divisor of active workloads on a GPU to predict eviction risk. When this GCD is greater than one, it signals that completion times share a common period, indicating an increased risk of synchronized memory-release bursts and subsequent instability.
System design should incorporate mild heterogeneity in decoding lengths by adjusting them slightly to ensure they are coprime when routing similar request classes together. This breaks the arithmetic synchronization that drives eviction-induced instability in the input-dominated regime.
Operational practices should use persistent eviction as an early warning signal for system failure rather than treating it as a gradual degradation. A transition from zero eviction to persistent eviction indicates that the system has moved beyond the region of stability predicted by memory constraints and requires admission regulation.