LLM Inference Compute Bottlenecks and KV Cache Scheduling: A Complete Guide
This article explains why compute and memory, not just model size, cap the scale of LLM serving. It breaks down autoregressive decoding into the compute-bound Prefill stage and the bandwidth-bound Decode stage, shows how the KV cache trades memory for compute (with a per-token size formula and estimation example), and covers the three core memory-management strategies of eviction, offload, and recompute. It then introduces continuous/in-flight batching, PagedAttention, and chunked prefill, and finishes with capacity planning, elastic autoscaling, tiered service with rate limiting, and a practical scheduling code example plus an FAQ on common bottlenecks and failure risks.
1. Why Inference Compute Is the Hard Constraint on Scaling
When a large model serves many users as a conversational service, what caps scale is usually not the parameter count itself but the inference compute (GPU) available per unit time, together with memory bandwidth and KV cache management, which directly determine concurrent throughput. To see why, it helps to look at how a single generation actually runs at the low level.
Large-model text generation is an autoregressive process: each time a token is generated, it is appended back to the context, and the next token is predicted, looping until an end token is reached. This means the GPU must produce tokens continuously and intensively. From a resource perspective, there is an upper bound on the number of active sessions a single card can maintain at any given moment, and this bound is determined collectively by memory capacity, memory bandwidth, and compute units.
From this comes a simple corollary: for a given pool of GPUs, there is a peak concurrency ceiling. Beyond it, requests can only queue, showing up as longer time-to-first-token, slower generation, and even rate limiting. When a service provider says “compute is tight, pausing new capacity,” it usually means the current GPU pool is approaching this peak and can only control intake to protect existing users’ service quality, but this is an observed conclusion; the specific cause still needs to be judged against memory-level and bandwidth metrics.
2. Prefill vs. Decode: One Compute-Bound, One Bandwidth-Bound
To get the resource accounting right, you need to distinguish the two phases of inference:
- Prefill: processes the user’s input prompt in parallel all at once, encoding the entire text into the model. It is matrix-multiply intensive with high arithmetic intensity, and is compute-bound.
- Decode: generates the output token by token. Each step processes only one new token, yet must read all of the model’s weights plus the cache corresponding to the historical context, making it memory-bandwidth-bound.
The key insight is that although Decode “does little math,” the GPU spends a large portion of its time moving weights and cache from HBM to the compute units, so the fraction actually spent computing is not high, which is why it is often described as “starving the compute units.”
This conclusion, however, has boundaries and should not be over-generalized: at small batch sizes, decode is bandwidth-bound, but as the batch grows, the arithmetic intensity of the linear layers rises and it gradually shifts toward compute-bound. Mixing Prefill and Decode in the same batch, or a particularly long prompt, will also change the ratio between the two. In practice, you should rely on roofline analysis or measured data. The one thing we can say for certain is that decode’s bottleneck comes mainly from data movement rather than raw compute, and whether you can serve more users depends on how many sessions you can maintain in parallel given a fixed GPU budget.
3. What Is the KV Cache? Why Trade Memory for Compute
If the attention Keys and Values for all previous tokens were recomputed from scratch each time a token was generated, it would produce a large amount of redundant computation, since without caching, the total attention computation over an entire generation grows quadratically with sequence length. The KV cache approach is to store the already-computed K and V for every layer and every attention head, so that afterward you only compute the K/V for the new token and append it, reducing each step from a “full recompute” to an “incremental computation.”
The cost is memory usage, which grows linearly with sequence length and concurrent batch size. Estimation rule (per token):
KV bytes per token ≈ 2 × num_layers × num_kv_heads × head_dim × bytes_per_element# 2 = one copy each for Key and Value; FP16 counts 2 bytes per element# Example: 32 layers, 8 KV heads, head_dim 128, FP162 × 32 × 8 × 128 × 2 = 131072 B ≈ 128 KB / token# 4096-token context → about 512 MB / session; 32 concurrent → about 16 GB
This value is a theoretical lower bound that does not account for memory fragmentation, activations, or framework overhead; structures like GQA/MQA significantly reduce the number of KV heads, and KV quantization (INT8/FP8) can halve it again. Use this as a quantitative basis for the capacity planning in a later section.
# Simplified flow of autoregressive decodingkv_cache = {}# Prefill: process the prompt all at once and build the initial KV cachelogits = model.prefill(input_tokens, kv_cache)# Decode: reuse the KV cache, computing and appending only the new token each step# Note: single-step attention still reads all historical K/V, so time grows linearly with contextfor step in range(max_new_tokens):next_token = sample(logits)logits = model.decode_step(next_token, kv_cache)if next_token == EOS:break
4. When Memory Runs Short: Evict, Offload, or Recompute?
Session reuse rates depend on the scenario: for single-turn Q&A or transient requests, session reuse is low and the probability of a quick return visit is small; multi-turn chat products, by contrast, often need to reuse the same context across requests (these scenarios benefit more from prefix-caching systems that reuse system prompts and shared prefixes). When memory cannot hold all active sessions, you can mix and trade off among three strategies:
- Eviction: best suited to low-reuse sessions. Discard the KV cache of long-idle sessions to free memory for tasks that are waiting or generating; this is the most direct way to raise instantaneous concurrency, at the cost of losing that session’s context.
- Offload: move the cache of inactive sessions from GPU memory to host memory or even SSD. Compared with outright discarding, a returning session can be restored faster, at the cost of the PCIe bandwidth overhead of swapping in and out.
- Recompute: suited to scenarios that have the complete history and can re-run Prefill. When a cache that has been offloaded to host memory or SSD needs to be restored, you can either swap it back into GPU memory or re-run Prefill against the complete history. These are two different recovery methods: recompute noticeably lengthens that request’s TTFT, but under the assumption that most sessions will not be reused, this occasionally incurred cost is usually acceptable.
A pragmatic scheduling principle overall is: sacrifice cache continuity for the few sessions that probably won’t return, in exchange for the service admitting more users at once. Using offload or recompute to gain higher throughput pays off only depending on the session reuse probability and the tolerable recovery latency.
def schedule(running, waiting, memory_budget):# When memory is over budget, prioritize freeing idle sessions' cacheswhile kv_memory_used() > memory_budget:if not running:break # No idle sessions to reclaim; exit to avoid an infinite loopidle = pick_idle_session(running) # pick the longest-idle sessionoffload_or_drop(idle) # offload to memory/SSD or drop outrightrunning.remove(idle)# Final check: still over budget means the active load itself cannot fitif kv_memory_used() > memory_budget:reject_or_limit(waiting) # stop admitting / trigger rate limiting to protect existing requests' TTFTreturnbatch = running + dequeue(waiting) # form a batch combined with dynamic batchingrun_decode_step(batch)
Two safeguards are critical: the loop must have a “no more to reclaim, so exit” branch, and after the loop you must re-check the memory level and decide whether to rate-limit. Otherwise, once empty sessions are exhausted the loop hangs, or new requests are admitted without checking memory and get killed by OOM.
5. How to Raise Concurrent Throughput: Continuous Batching and Paging
Beyond cache juggling, two more general techniques can serve more users on the same compute:
| Technique | Typical implementations | Problem it solves | Costs and cautions |
|---|---|---|---|
| Continuous / dynamic batching | vLLM and TGI’s continuous batching; TensorRT-LLM and Triton’s inflight batching | Frees a slot as soon as a request finishes, so short requests are no longer held back by long ones | More complex scheduling logic; long prompts eat into decode’s compute budget |
| Paged memory management | vLLM’s PagedAttention (introduced with vLLM in 2023) | Borrowing from OS virtual memory, manages the KV cache in fixed-size blocks to reduce fragmentation and improve packing | Block tables and indirection add a small addressing overhead |
| Chunked prefill | vLLM’s chunked prefill, SARATHI, DeepSpeed-FastGen’s dynamic SplitFuse | Splits long prompts into chunks and mixes them with decode to flatten TTFT/TPOT jitter | A long prompt’s TTFT may rise slightly; chunk size needs scenario-specific tuning |
The names, default values, and default behavior of these switches change with framework versions, so before deploying, refer to the official documentation of the version you use and run A/B tests on your own workloads.
6. Capacity Planning and Elastic Scheduling
- Define the core metrics: time-to-first-token (TTFT), time-per-output-token (TPOT), and overall throughput, plus queue length and drop rate. The observability surface should also cover the KV memory level, swap-in/out volume, and latency percentiles, with threshold-based alerts.
- Calculate the memory budget: use the section-3 formula to work backward from the target context length and concurrency to the required KV memory, then add weights, activations, and a fragmentation reserve to get an upper bound on the sessions a single card can host.
- Scale elastically by peak and trough: on a container platform, auto-scale based on concurrency and utilization, adding instances at peak and removing them at trough, to avoid reserving idle compute for extreme peaks over the long term.
- Tiered service and rate limiting: assign priorities to requests of different SLA levels, combined with entry-level rate limiting and queuing, so that when compute is tight, higher-priority tasks are protected first and sudden traffic spikes don’t break through.
- The cost perspective: since decode is bandwidth-bound, simply adding more cards is not economical; fully using cache scheduling, batching, and offload/recompute often improves effective concurrency per unit of compute more than linearly scaling out GPUs.
7. Summary
Autoregressive decoding is inherently a resource-intensive workload: decode’s memory-bandwidth bottleneck keeps GPUs running closer to “against the ceiling,” while the total available GPUs set the peak concurrency ceiling. What truly determines service elasticity is doing fine-grained scheduling under limited memory and compute, combining the eviction, offload, and recompute of the KV cache with continuous batching and paged memory management, then backing it with monitoring-driven autoscaling and tiered rate limiting, so compute is spent on “the conversations happening right now” without noticeably sacrificing the experience.
8. FAQ
Q: Why is compute never fully utilized during Decode? Each step processes only one new token but must move all the weights and historical cache, so the bottleneck is HBM bandwidth. As the batch grows it gradually shifts toward compute-bound; rely on roofline analysis or measurements for specifics.
Q: How do I choose a strategy when memory runs short? For low-reuse transient sessions, evict first; when a session may return but you want to preserve continuity, offload it, provided your PCIe/SSD bandwidth can keep up; when the complete history is available and you can tolerate TTFT jitter, use recompute.
Q: What are the risks? Offload adds swap-in/out bandwidth overhead and latency jitter; eviction loses context and hurts the multi-turn experience; recompute can multiply that request’s TTFT by several times; and poorly tuned mixing or chunked prefill can raise the time-to-first-token of long prompts. Before going live, it’s recommended to validate on shadow traffic first.
Q: Does cost jump abruptly as context grows longer? Single-step attention time grows linearly with context length, so this portion’s share rises under long contexts; KV quantization and GQA/MQA can significantly ease the memory pressure.
