KV-Cache Ballooning: Why Paged Attention Isn't Enough

Paged attention solved the wrong half of the problem. It stops KV-cache fragmentation, but it does nothing about growth. A long agent run still allocates KV memory proportional to context length times concurrent sequences, and that number does not care how neatly the pages are packed.

Teams typically discover this the hard way. A single-agent workload looks fine. Then someone wires up a planner that spawns five sub-agents, each holding a long tool transcript, and the inference server OOMs mid-run. The paged allocator was working exactly as designed. The workload outgrew the budget.

Why does KV cache grow even with paged attention?

KV cache size is a product, not a sum. For each sequence you pay two tensors per layer per head, scaled by the number of tokens already generated. Multiply by batch size and you get the resident set.

# rough KV bytes per sequence
kv_bytes = 2 * layers * kv_heads * head_dim * dtype_bytes * seq_len
# total resident = kv_bytes * concurrent_sequences

The paged allocator hands out fixed-size blocks on demand. That removes internal fragmentation and lets sequences share prefix blocks. It does not cap seq_len, and it does not cap concurrent_sequences. An agent that appends a tool result every turn grows seq_len monotonically. Nothing in the paged design pushes back.

A common pattern is a server that runs comfortably at short context and falls over at long context with the same batch size. The allocator is not leaking. The workload simply crossed a threshold the operator never modeled.

What makes agent workloads different from chat?

Chat turns are bounded. A user types, the model answers, the sequence ends. Agent runs are unbounded by construction: the loop continues until a stop condition fires, and every tool call appends tokens that must stay in context for the next decision.

Three properties compound:

• Monotonic context growth. Tool outputs, observations, and scratchpads accumulate. Truncation is a policy decision, not a default.
• Fan-out concurrency. A planner spawning N workers multiplies resident KV by N at the same wall-clock moment.
• Bursty arrival. Sub-agents start together after a planning step, so the allocator sees a spike rather than a smooth ramp.

Each is manageable alone. Together they turn a paged allocator into a memory amplifier with no governor.

Where does the memory actually go?

Before changing anything, instrument the allocator. Most inference servers expose block usage, free blocks, and per-sequence token counts. Pull those into a time series and correlate with request lifecycle events.

The question to answer is simple: is memory growing because sequences are long, or because there are many of them? The fixes diverge sharply.

metric: kv_blocks_in_use
labels: model, sequence_id, phase
metric: kv_blocks_free
metric: seq_tokens{sequence_id}

If kv_blocks_in_use climbs while sequence count is flat, you have a long-context problem. If it climbs with sequence count, you have an admission problem. Most agent stacks have both, and operators who skip this step tune the wrong knob.

Which lever fixes which failure mode?

Match the lever to the diagnosis. Applying all four at once hides which one worked.

• Eviction and compaction. Drop or summarize old turns when a sequence crosses a token budget. This caps seq_len directly. It costs quality, so make it explicit and logged.
• Prefix sharing. Agent runs often replay the same system prompt and tool schema. Block-level prefix reuse cuts resident KV for the shared portion across all sequences.
• Offload to host memory. Move cold blocks to CPU and page them back on demand. This trades latency for headroom and is the right call when sequences are long but mostly idle.
• Admission control. Cap concurrent sequences per model and queue the rest. This is the only lever that bounds worst-case memory under fan-out.

A practical default: enforce a per-sequence token ceiling, enable prefix sharing, and set a hard concurrency limit sized to your block budget. Add offload only after the first three are in place.

How do you size the concurrency limit?

Work backwards from the block budget. Compute blocks per sequence at your token ceiling, then divide available blocks by that number. Leave headroom for the allocator's own metadata and for transient spikes during prefill.

blocks_per_seq = ceil(max_tokens / block_size)
max_concurrent = floor(available_blocks * safety_factor / blocks_per_seq)

Set safety_factor below one. Prefill of a long prompt can allocate many blocks at once, and a burst of simultaneous prefills is exactly the fan-out case that triggers OOM. The limit must survive the worst simultaneous arrival, not the average.

Check this number against your actual agent topology. If a planner spawns five workers, max_concurrent must be at least the planner plus five, or the run deadlocks waiting on admission. Size the topology and the limit together.

What should the agent runtime do differently?

The inference server cannot fix a runtime that ignores its own memory budget. Push context management into the agent loop.

• Summarize tool outputs before appending them, not after the context is full.
• Cap sub-agent fan-out explicitly and reuse a shared prefix for their system prompts.
• Treat context length as a resource the planner must request, the same way it requests a tool.

This is the part teams skip. They tune the server and leave the runtime unbounded, then wonder why the same OOM returns under a new workload shape.

Start by logging per-sequence token counts for one week of real agent runs. Find the p95 context length and the peak concurrent sequence count. Those two numbers tell you which lever to pull first.

If you run long agent loops, what is your current per-sequence token ceiling, and who enforces it: the server or the runtime?