Bursts That Outlast Themselves: Persistent Degradation in Prefix-Cached Agent Serving

Wen Huang, Jack Liu
36 minread4.40scoreNo. 111-12 Infra issue
Contents · 7 sections1Same arrivals, a 5-minute burst apart: an hour later one server is healthy and one has collapsed2With prefix caching off, there is only work to catch up on3The loop: a bit slower, a few more sessions, prefixes no longer fit, slower still4Throttling new sessions leaves the ones inside recomputing every turn5The budgeter keeps a token ledger6Parking recovers 7/7 within 5 minutes; throttling new sessions, 2/87Parking has a cost, and it cannot create capacity
Rel 5Nov 4Prac 4Evid 4Time 5

This paper shows that agent serving with prefix caching has two steady states: a burst of a few minutes can push a server into a state where nearly every turn is recomputed and the backlog keeps growing, and it stays there after the load falls back. Throttling new sessions rarely brings it back, while parking some already-admitted sessions at turn boundaries recovers it faster and more reliably.

A coding agent session is a closed loop: the model emits a tool call, the tool runs, its output is appended to the conversation, and the grown context goes back to the model in full, tens to hundreds of times per task. An inference engine can serve this traffic cheaply because of prefix caching: if the previous turn's KV cache is still in GPU memory, this turn only needs a prefill over the thousand or so newly appended tokens. On the authors' MI300X with Qwen3-8B, a mid-session turn with a 21.6K-token context costs about 0.15 s of prefill on a hit and about 2 s on a miss, when the whole context is recomputed.

The difficulty is that whether the cache fits depends on how fast the service is. The GPU memory that holds the KV cache (the KV pool below) is shared: running requests take part of it, the prefixes left by idle sessions take the rest, and LRU evicts when it is full. A closed-loop session sends its next turn only after the reply arrives, so the slower the service, the more sessions are in the system at once. All of their prefixes want to stay in the pool, and the pool has a fixed size.

A running example makes this concrete (illustrative). One GPU's KV pool holds 400K tokens; with an average session context of 22K tokens, the pool fits the prefixes of about 18 sessions. Normally there are about 10 sessions in the system: 10 × 22K = 220K tokens, every prefix stays, and each turn takes 0.15 s. Then a burst arrives and there are suddenly 30 sessions in the system: 30 × 22K = 660K tokens, more than half again the pool. During the few seconds each session spends thinking or waiting for a tool, its prefix is pushed out by other sessions, so its next turn must be recomputed.

An intuitive response is to throttle new sessions: they queue at the gateway and are let in once the system recovers. The closest existing methods are recent agent-serving schedulers such as KAIROS (admission by context occupancy) and CONCUR (cache-aware concurrency control). They aim to keep the system out of this loop; they do not measure how to get out once it is in. Back in the example, throttling stops session 31, but each of the 30 sessions already inside still has a dozen or so turns to run. Every one of those turns is recomputed, so service stays slow and the population does not fall. The paper asks two questions: does the server leave this state on its own, and what control action pulls it out.

Same arrivals, a 5-minute burst apart: an hour later one server is healthy and one has collapsed

The authors isolate the effect of history with paired runs. Both runs of a pair share one base arrival stream: every base session arrives at the same time with the same length and number of turns. The only difference is that at minute 15 the burst run receives 5 minutes of extra sessions, at 2.5 times the usual arrival rate. After the burst both runs face the same base load, and each runs for 90 minutes.

The base load is λ=0.035 sessions/s, about 70% of the 0.05 sessions/s this machine sustains with a warm cache. Synthetic sessions start at 6K tokens and grow to 37K over 25 turns; tokens are random, so reuse comes only from a session's exact prefix and the shared system prompt.

Paired runs: same base arrivals; the red run adds a burst from minute 15 to 20 (shaded), after which its hit ratio drops to about 0.1, its throughput stays below the no-burst run, and its sessions in the system climb past 100; the blue run stays healthy
Paired runs: same base arrivals; the red run adds a burst from minute 15 to 20 (shaded), after which its hit ratio drops to about 0.1, its throughput stays below the no-burst run, and its sessions in the system climb past 100; the blue run stays healthy

At the end of 90 minutes, the pair in the figure (seed 501) has a hit ratio of 0.95 and 8 sessions in the system without the burst, and 0.12 with 109 sessions with the burst. Of 12 pairs, in 9 only the burst run degraded persistently, in 0 only the no-burst run did, 2 degraded in both and 1 in neither. This shows that degradation follows the 5 minutes of history rather than being set by the load level itself.

In the 2 pairs where both degraded, the no-burst run slid in on its own after twenty to thirty minutes and did not come back out either. A trigger makes entering far more likely; nothing made leaving easier.

With prefix caching off, there is only work to catch up on

A natural suspicion is that this is ordinary overload with a backlog not yet worked off. The authors rule that out with three controls.

The first turns prefix caching off and injects the same roughly 16 extra sessions at about 80% of the no-cache engine's capacity. The backlog rises to 17–43 sessions and then falls, shrinking in every run over the last 30 minutes. The second looks at the burst itself: in 7 of 11 degraded burst runs all injected sessions had finished, yet the hit ratio stayed at 0.10–0.12. The third adds a session cap that keeps active sessions within the pool, and the same bursts caused persistent degradation in 0 of 10 runs. Together these show that the second steady state comes from the cache; without a cache, a burst is just work to catch up on.

Bursts are not the only trigger: flushing the cache and preempting running requests (what a replica restart or weight update does) left 1 of 5 runs persistently degraded without any extra load. With Qwen3-32B replaying SWE-bench agent trace shapes the phenomenon also appears, but the authors call this evidence weaker, because a longer no-burst run later degraded on its own. SGLang absorbs the small bursts that collapse vLLM, yet larger bursts collapsed it in all 6 runs. So engine design moves the threshold; the failure is still there.

The loop: a bit slower, a few more sessions, prefixes no longer fit, slower still

The numbers in the example let us work out the loop. In a closed loop, the steady-state number of sessions in the system follows Little's law: . Here λ is the session arrival rate, T the number of turns per session, Z the think and tool time between turns, and R the per-turn response time. Illustrative mental arithmetic: with λ=0.035, T=25 and Z=5 s, if R is 6 s then N≈0.035×25×11≈10; if R becomes 40 s, N≈39, far above the 18 the pool can hold.

The formula explains why the loop sustains itself. The authors break it into three properties. First, backlog is working set: a larger R means more prefixes must stay resident. Second, the miss penalty grows with session age, because a miss recomputes the whole context. Third, running requests and the cache share one pool, so the more requests run, the less room is left for idle prefixes.

In the degraded regime the engine is busy, not stalled. Over the last 10 minutes, 99.6–100% of turns had less than half their prompt cached, and the 0.10–0.12 hit ratio is just the shared system prompt. Meanwhile 16–32 requests run concurrently and preemptions are rare. Throughput is 0.35–0.46 turns/s, the same as 0.33–0.43 turns/s with caching disabled. This shows the lost throughput goes entirely to recomputation: the engine has fallen back to its no-cache level.

The loop in seed 501: the burst pushes resident demand past the KV pool (dotted line), after which recomputed tokens per second rise and the hit ratio collapses, while demand keeps climbing to more than four times the pool; the no-burst run never crosses the pool
The loop in seed 501: the burst pushes resident demand past the KV pool (dotted line), after which recomputed tokens per second rise and the hit ratio collapses, while demand keeps climbing to more than four times the pool; the no-burst run never crosses the pool

Resident demand in the figure is the number of sessions in the system times their mean context. It is about 0.6 of the pool before the burst, 1.4 times at minute 25 and 4.8 times over the last 5 minutes; the no-burst twin peaks at 0.83 and never crosses. One caveat: that prefixes are evicted between turns is the authors' inference, because the engine does not export per-block eviction events.

Whether the degraded regime can drain on its own comes down to a simple balance. If every turn misses, serving one session costs S engine-seconds. The authors calibrate the per-turn recompute cost separately on cache-disabled runs and get S≈78 s, so the arrival rate must stay below 1/S≈0.013 sessions/s for the backlog to drain. The experimental load of 0.035 is more than twice that, so the degraded regime only accumulates more work. When the authors collapse the server and then lower the arrival rate, the observed break-even lies at 0.010–0.014, bracketing 0.013. This is only a necessary condition: it says the server cannot get out unless load falls this low, and it does not predict when a collapse happens.

Throttling new sessions leaves the ones inside recomputing every turn

Since what stalls the server is too many sessions wanting the cache at once, the direct fix is to reduce their number. Throttling new sessions does reduce it, only slowly. Illustrative: 40 sessions in the system, each with 15 turns left, all misses at 2 s per turn, need 40×15×2 = 1200 engine-seconds, about 20 minutes, just to finish. During those 20 minutes the hit ratio does not come back and new sessions keep piling up outside.

The authors instead park some admitted sessions at the gateway. A parked session issues no further turn once it reaches a turn boundary, and its prefix may be evicted; the remaining sessions' prefixes fit in the pool, they start hitting again, throughput returns, and only then does the queue drain. Parking happens only at the boundary just after a session completes a turn, so no running request is interrupted. Parked sessions wait in a FIFO queue, are re-admitted before new sessions, and usually pay one miss when they return.

For a fair comparison, the authors implement all controllers on the same gateway actuator; they differ only in how the limit is set. These five appear in the results table:

ControllerHow the limit is setParks admitted sessions?
No controlNoneNo
Admission-only capNew sessions wait while 16 sessions are activeNo
Latency AIMD + parkLimit adjusted every 10 s, halved when median turn latency exceeds 15 s, otherwise increased slowly; a simplified proxy in the spirit of CONCURYes
Session cap + park14 sessions, set from per-session demand measured on the healthy load; park above 17Yes
budgeter + parkResident demand of active sessions counted in tokens, compared with the pool sizeYes

The budgeter keeps a token ledger

The budgeter is the authors' controller, and it is Denning's classic load control (the authors say plainly this part is not new). For each admitted session it records a demand: the current context plus the output budget for this turn; summed over all sessions this gives the resident demand D. C is the KV pool size, which the engine reports at startup. The rule is a hysteresis band: waiting sessions are admitted while D≤0.75C, and a session that has just reached a turn boundary is parked when D>0.95C.

This ledger is the gateway's core intermediate product at every turn boundary. Illustrative, with C=400K tokens, an admit line of 300K and a park line of 380K:

Hoot saysHow a token ledger decides parking and re-admissionClose ✕
Before re-admitting the head of the queue, check whether adding it crosses the line. D below the admit line is not enough; D plus that session's demand must stay within it.
Four steps: A updates its demand; D=390K; compared with the 380K park line; A is parked and D becomes 360K.A finishes a turndemand 29.7K+0.3K=30KLedger D390KD > 380K?yesPark AD = 390K − 30K = 360K
Four steps: A updates its demand; D=390K; compared with the 380K park line; A is parked and D becomes 360K.A finishes a turndemand 29.7K+0.3K=30KLedger D390KD > 380K?yesPark AD = 390K − 30K = 360K
1/4 · t1: A reaches a turn boundaryAfter A's demand updates to 30K, D=390K is above the 380K park line; A is parked and queued, and D drops to 360K.
Four steps: B leaves, minus 35K; D=325K; between 300K and 380K; no action.B leaves−35KLedger D325K300K < D ≤ 380Kinside the bandNo actionA keeps waiting
Four steps: B leaves, minus 35K; D=325K; between 300K and 380K; no action.B leaves−35KLedger D325K300K < D ≤ 380Kinside the bandNo actionA keeps waiting
2/4 · t2: B leavesD=325K lies between the lines: nobody is admitted or parked; the gap leaves room for sessions to keep growing.
Four steps: C leaves, minus 30K; D=295K; check whether 295K+30K=325K stays within 300K; it does not, so A waits.Only C leaves−30K (illustrative)Ledger D295K < 300KD + A's demand295K + 30K = 325KAbove 300KA still waits
Four steps: C leaves, minus 30K; D=295K; check whether 295K+30K=325K stays within 300K; it does not, so A waits.Only C leaves−30K (illustrative)Ledger D295K < 300KD + A's demand295K + 30K = 325KAbove 300KA still waits
3/4 · What if only C left (illustrative)Illustrative: minus only 30K gives D=295K, already below the 300K admit line, but re-admitting A first adds A's 30K back: 295K + 30K = 325K > 300K, so A still waits.
Four steps: C and E leave, minus 65K; D=260K; 260K+30K=290K is within 300K; A is re-admitted.C and E leave−65KLedger D260KD + A's demand260K + 30K = 290K ≤ 300KRe-admit AD = 290K
Four steps: C and E leave, minus 65K; D=260K; 260K+30K=290K is within 300K; A is re-admitted.C and E leave−65KLedger D260KD + A's demand260K + 30K = 290K ≤ 300KRe-admit AD = 290K
4/4 · t3: C and E leaveD=260K; adding A's 30K gives 290K, within 300K, so A is re-admitted from the head of the queue and D becomes 290K.
1/4

Illustrative numbers, C=400K tokens, admit line 300K, park line 380K. The ledger is a conservative proxy, not the cache's actual occupancy: for 10 sessions (illustrative) sharing the 2K system prompt it counts 10 × 2K = 20K, while the cache stores one copy; it is also updated only at turn boundaries.

Sourcepaper §5 algorithm: demand updated at turn boundaries; park the session at its boundary when D>0.95C; admit while D+d_s≤0.75C, parked before new; D double-counts shared prefixes and updates only at boundaries; §3 shared 2K system prompt
TimeEventD on the ledgerDecision
t1Session A completes a turn; its demand updates to 29.7K context plus 0.3K output budget, 30K in total390KAbove 380K: park A, D falls to 360K
t2Session B finishes its last turn and leaves, minus 35K325KBetween 300K and 380K: neither admit nor park
t3Sessions C and E leave, minus 65K in total260K260K + 30K = 290K, not above 300K: re-admit A from the head of the queue, D becomes 290K

Why two lines and not one? Sessions keep growing between boundaries; with a single line, a just-admitted session would cross it after one more turn, and the gateway would flip back and forth between admitting and parking. The gap between the lines leaves room for that growth. Both lines were fixed before the experiments and not tuned per load; switching to a lower or higher pair changed neither the outcome nor the timing of the 8B recovery runs, which shows this controller does not depend on tuning.

Why count tokens rather than sessions? A session-count limit is really a token limit divided by an assumed per-session demand, and agent sessions differ by an order of magnitude in length. Illustrative arithmetic: with a 400K-token pool, a cap of 22 is loose if sessions start at 3K; the same 22 sessions starting at 22K already total about 480K tokens at the outset, more than the pool. D is also only a conservative proxy: it counts the shared system prompt once for every session and is updated only at turn boundaries, so it bounds the active working set rather than what is physically resident in the cache.

Parking recovers 7/7 within 5 minutes; throttling new sessions, 2/8

The recovery experiment first collapses the server: Qwen3-8B, λ=0.04, a 2× burst for 4 minutes from minute 10, controllers switched on at minute 20, run to minute 60. All arms of a seed share the same arrivals. The table counts only runs already collapsed at minute 20, so denominators differ.

Control (from minute 20)RecoveredTime to recover (min)Hit ratio at endShare of sessions arriving in the next 20 min that completed
No control0/8–0.12–0.130%
Admission-only cap2/821–230.07–0.930–92%
Latency AIMD + park5/714–250.84–0.8950–100%
Session cap + park7/7≤60.95100%
budgeter + park7/7<50.93–0.95100%

The table shows that the difference lies in whether admitted sessions are parked and whether the limit is set against the pool's capacity. Both controllers that park against the pool's capacity recovered every run within minutes; the admission-only cap, even when it recovered, took over twenty minutes, and 4 runs stayed below a 0.1 hit ratio to the end. Latency AIMD (additive increase, multiplicative decrease of the concurrency limit driven by latency) also parks, but it watches latency rather than whether the pool can hold the sessions, so its recovery is slower and less reliable.

Same seed, same arrivals, different controllers switched on at minute 20 (dotted line): the budgeter and the session cap bring the hit ratio back above 0.9 within minutes and sessions in the system fall; with the admission-only cap and no control, sessions keep rising
Same seed, same arrivals, different controllers switched on at minute 20 (dotted line): the budgeter and the session cap bring the hit ratio back above 0.9 within minutes and sessions in the system fall; with the admission-only cap and no control, sessions keep rising

Restricting to the 7 seeds collapsed in every arm, which start from matched states, the conclusion holds: the budgeter and the session cap each recover 7 of 7, the admission-only cap 1 of 7 (exact paired test p=0.031). So the gap comes from the control action, not from different starting points. Across all recovery experiments, the budgeter recovered all 17 of 17 collapsed runs.

On homogeneous synthetic sessions the budgeter and a tuned session cap perform alike; the difference is that the cap had to be tuned. On 32B trace shapes with uneven session lengths, a session cap set from a lighter load recovered none of 3 seeds, while the budgeter recovered all of them within 5 minutes.

The session-mix experiment shows the fixed cap's dilemma more directly. For the first 30 minutes, short sessions starting at 3K arrive; after that, long sessions starting at 22K, with no burst. Caps of 22 or 34 are too loose for the long sessions and collapse anyway; caps of 10 or 14 prevent collapse but make first turns of the short-session phase queue at the gateway, with a p90 of up to 13 minutes. The budgeter avoids both, because its ledger is kept in tokens.

Parking has a cost, and it cannot create capacity

Parking trades some sessions' waiting for everyone's throughput. On the 7 matched seeds, sessions arriving after control began took a median of 11.6 minutes from arrival to completion with the budgeter, versus 3.8 minutes in never-collapsed uncontrolled runs. This means users still wait longer after recovery, but sessions do finish; with the admission-only cap, 317 of 349 sessions had not finished by the end.

What the controllers restore is cache efficiency; they cannot create capacity the machine does not have. After 32B was collapsed by a strong burst, the budgeter brought the hit ratio back to 0.92–0.97, yet the queue kept growing slowly, because this trace mix arrives slightly faster over the long run than the cache-warm engine completes it. Likewise, adding a CPU KV offload tier only delays the collapse from minutes 20–25 to minutes 40–60, and in the paired design 4 of 6 burst runs still degraded persistently.

The limits of the evidence belong here too: synthetic sessions use random tokens, and the experiments use one GPU type and a single replica, with no routing, autoscaling or production data. Production contexts are longer, so the same pool holds fewer sessions.

For the server at the start that 30 sessions overwhelmed, throttling only stops session 31, and even when it recovers it takes over twenty minutes; pausing a dozen or so of those sessions so that the rest keep their prefixes in the pool recovers it faster and more reliably. The authors' advice to operators is concrete: when GPU utilization is high and latency alarms fire, first check the prefix hit ratio of agent traffic, then whether the number of sessions in the system exceeds what the KV pool can hold. Restarts and weight updates are triggers in their own right, and ramping admission while the cache rebuilds avoids the collapse.

How did this read for you?

One tap, no sign-in; tap again to undo. Only anonymous counts are kept, never who you are.

Related papersMore from Paper Daily

  1. Infra · 2026-11-10Inside the Trap: A Renewal Law for Prefix-Cache Collapse in LLM Agent ServingMulti-turn LLM agents rely on prefix caching to skip repeated work, but this paper finds a trap. After a sudden burst of sessions, an engine can fall into a state where every turn misses the cache and the backlog never drains, even at a load it handled before. In paired tests on two serving engines, two GPUs and two models, a burst of 200 sessions left the engine stuck to the end in all 30 runs,…
  2. Infra · 2026-11-03HiState: Hierarchical Prefix Cache Management for Hybrid LLM Serving in Agentic WorkloadsThe recurrent layers of a hybrid model compress the whole prefix into a fixed-size snapshot, and it cannot be cut back to an earlier position. So even when the KV is still cached, if the snapshot at the match point was never saved or has already been evicted, a long stretch must be recomputed from an earlier snapshot, or from scratch. HiState exploits an asymmetry: a cache hit reads every matchin…
  3. Infra · 2026-11-13Evolving Infra: Agent-Adaptive LLM Serving at ScaleAgent workloads pose two problems for inference clusters. Some agents are prefill-heavy and others decode-heavy, and the mix drifts over time, so any fixed ratio of prefill to decode nodes loses out in some periods. Context compaction and sub-agents also change which KV is worth keeping: when a sub-agent returns after several minutes, almost the whole prompt can reuse earlier KV, while a request…
  4. Infra · 2026-11-04When Cache Pressure Becomes a Trap: Metastability in Agent ServingA ten-minute traffic surge can leave an agent serving engine with prefill and decode disaggregated unable to recover. After the surge ends and traffic returns to a level the engine handled before, goodput on SGLang stays about 88% lower over the following hour, and utilization and queue length give almost no warning beforehand. Behind it is a loop: too little cache causes recomputation, calls slo…
  5. Infra · 2026-10-28HiLO: Towards Product-Level Graceful Degradation with a Quality-Aware, Load-Aware Control FrameworkDuring traffic spikes, each service degrades on its own, so every service survives while the product's quality can collapse. Microsoft's HiLO moves degradation from the service level to the product level. It predefines a few validated product states. Each state sets a level for every service, such as dropping some features, reducing fan-out or using a cheaper model. At runtime services report loa…

Discussion

Add experiment details, reproduction notes or a different take. Requires a GitHub sign-in.

Loading the discussion…