LLM Serving: Continuous Batching, PagedAttention and Prefill-Decode Disaggregation

Why it was needed: the bottleneck is 'how requests queue,' not the model

In model serving (running a trained model so it responds to real requests), large language models (LLMs) behave differently from ordinary web servers. Each request has a different answer length, and answers are built autoregressively, one token appended at a time. Even among requests on the same GPU, some finish after 10 tokens and others only after 2,000.

Inference has two stages. First, prefill reads the entire prompt at once and stores the intermediate results it produces, the KV cache (the Key and Value values that attention reuses). Next, decode reads this KV cache and produces tokens one at a time. Prefill involves many large matrix multiplications, so compute is the bottleneck; decode must read all the weights and the entire KV cache from memory for every token, so memory bandwidth is the bottleneck.

The older approach, static batching, grouped several requests and ran them together, accepting the next group only after the longest request in the group finished. Short requests finished early but could not free their slots, and the KV cache was reserved up front at the 'maximum length,' wasting GPU memory (VRAM). This is why latency was high and throughput (tokens/second) was low.

Serving techniques therefore developed around three questions: when to add and remove requests (continuous batching), how to fit the KV cache into memory (PagedAttention), and whether two stages with different characteristics should run on the same GPU (prefill-decode disaggregation).

Core ideas: an elevator, parking spaces and a kitchen with divided labor

Pinning each of the three techniques to an analogy makes them quicker to grasp. Continuous batching is like an elevator. Static batching is an elevator that does not return to the ground floor until every passenger has gotten off; continuous batching stops at every floor to let people off and take people on. Here a 'floor' is one step that produces a single token.

PagedAttention is closer to dividing a parking lot into spaces. Instead of reserving a long empty stretch at maximum length for each request, it hands out small spaces (blocks) one at a time as needed. The idea comes from how operating systems manage virtual memory in pages. Even if a request's KV cache is physically scattered, a block table lets it be read in sequence.

Prefill-decode disaggregation is the division of labor in a restaurant kitchen. Prep (prefill) means processing a large amount quickly all at once, while cooking (decode) means steady, small amounts of work for each plate. If one cook alternates between the two, cooking stops every time prep work comes in. Giving them to separate teams stops them from interfering with each other, but adds a new cost of carrying the prepped ingredients (the KV cache) to the cooking station.

To sum up the trade-offs: continuous batching gave up simplicity and accepted a scheduling cost at every step. PagedAttention gives up contiguous memory layout and accepts indirect lookups through the block table. Disaggregation removes interference between stages at the price of network transfer.

How it works

First, when a request arrives, the scheduler checks the queue. Continuous batching inserts and removes requests at the token level, so after each step 'remove finished requests, add new ones' takes place. A continuous batching scheduling study paper describes this as interleaving requests at the token level as sequences arrive and finish. Chunked prefill, which splits prefill into pieces, is also commonly used alongside it to keep a long prompt arriving all at once from stalling requests that are decoding. The simulator in the QBA study paper models serving-engine behavior including decode-first batching, chunked prefill, token budgets and admission after checking KV cache headroom.

Second, when a new request's prefill produces a KV cache, a PagedAttention-style memory manager hands out fixed-size blocks. Because management is per block, requests that share the same prefix (e.g., the same system prompt) can share those blocks, and when memory runs short, blocks can be evicted or offloaded to a lower tier individually. Most of the KV cache research covered later uses this 'block' as its basic unit.

Third, under disaggregation, the KV cache produced by the prefill GPU is sent to the decode GPU. The optical KV cache network study paper points out that for every request the KV cache must move from the prefill GPU to the decode GPU before the response can begin, and that a single turn of a coding agent often means moving the KV cache for an entire long context. On a network short on bandwidth, this transfer adds directly to TTFT (time to first token).

Fourth, the decode GPU reads the KV cache by following the block table and produces tokens one at a time, while the scheduler rebuilds the batch at each step. Blocks from requests that have finished answering are freed or kept in the cache for reuse in the next turn.

How it evolved: shrinking, reusing and moving the KV cache

Once block-level management became established, the research focus shifted to 'how sparingly the KV cache can be used.' One line of work is reuse. CacheTune paper treats the TTFT caused by prefill in long contexts as the biggest bottleneck and targets a limitation of existing prefix caching: it works only when the beginning is exactly the same. Reusing KV from non-prefix positions as is breaks the attention relationships between chunks and lowers quality, so it recomputes only the tokens important for recovering attention and reuses the rest.

Another line is shrinking and eviction. EVICPRESS paper points out that as users grow, the KV cache easily exceeds GPU memory, yet prior work did only one of either evicting to a lower tier or compressing. It therefore jointly optimizes compression and eviction decisions for all contexts under a single utility function. KV block joint encoding paper merges similar blocks across requests and input chunks into a single shared representation while leaving the standard cache structure unchanged. It reports up to 4.38x compression with almost no accuracy loss and about 40% higher token throughput on a single-machine vLLM benchmark.

What to evict was also reconsidered. Recency-frequency adaptive KV caching paper points out that under the common LRU (evict the least recently used first) policy, unrelated workloads push out each other's cache. By dynamically splitting space between recently used and frequently used blocks, it raised cache hit rate by up to 10.8% and cut TTFT by up to 12.6% compared with vLLM on a synthetic document question-answering workload. On real conversation workloads, however, the gains were only 2.1% and 2.0%, respectively.

Agents and disaggregation added new pressure. TokenCake paper addresses the problem of an agent's KV cache sitting idle in GPU memory while it waits on external function calls. By offloading the cache ahead of time during a function call and predicting when the call will return so it can load it back, it reduced end-to-end latency by up to 47.06% compared with vLLM in memory-constrained settings and raised effective GPU utilization by 16.9 percentage points. On the disaggregation side, SpectrumKV paper recast KV transfer from a binary 'send / don't send' decision into a problem of assigning different precision to each token, and the optical KV cache network paper replaced the transfer path itself with optical circuit switches.

Where it is heading

The first trend is offloading the KV cache further away from the GPU. KVStream paper argues that in agent, coding and document workloads, the KV cache for reusable prefixes now exceeds GPU and host memory, putting storage I/O on the critical path of inference. Starting from the observation that a single node-local NVMe drive handles every read while an already-mounted parallel file system sits nearly idle, it replicates chunks across all tiers and lets whichever tier is free fetch the next chunk. Evaluated on up to 128 GPUs with LMCache, it read data within 5% of the theoretical bandwidth limit, delivered up to 1.49x the offline throughput of LMCache, and cut mean TTFT under request bursts by up to 6.1x.

The second trend is revisiting scheduling policy. A continuous batching scheduling study paper examined whether changing only lightweight policies, without touching model architecture or kernels, shifts the balance between latency and throughput. Running eight policies 1,152 times across six models on L40S, A100 and H100 GPUs, it found that throughput, TTFT and tail latency varied with the scheduler choice even with the same model, GPU, workload, batch size and prefill budget. In many settings, 'shortest prompt first' with aging was the strongest practical baseline. Even an ideal scheduler that knows the remaining length in advance was not enough, because batching and hardware effects jointly determine performance.

QBA paper looks at the same problem from the angle of fairness. Serving requests predicted to have short answers first lowers average latency but pushes long requests far back. Yet promoting long-waiting requests without limit over-favors long requests under congestion. QBA promotes long requests that have waited a long time but caps how far with quota and 'debt' rules, sharply reducing tail latency for long requests while keeping much of the average-latency gain.

Limitations and open issues

Prefill-decode disaggregation is not free. As SpectrumKV paper puts it, disaggregation turns the KV cache into a load that has to be sent over the network. When KV is quantized to cut transfer volume, models differ in how well they tolerate it. In this study, Qwen2.5-7B degraded badly under INT4 KV quantization while Mistral-7B and Gemma-2-9B stayed stable. So at deployment time, a short probe experiment is run to decide whether to use INT4. On WikiText-2 with a normalized KV budget of 50%, SpectrumKV's perplexity change across the three models was +1.97%, -0.06% and -0.44%, compared with +25.85%, +22.07% and +35.63% for the baseline method PDTrim.

Network cost is also at issue. The optical KV cache network paper holds that behind a bandwidth-constrained packet network, transfer increases TTFT, and it hides the reconfiguration delay of mechanical switches by reserving optical circuits in advance while prefill is being computed. In simulations using real serving traces, it matched the performance of a 400G packet network at 0.55–0.78x the cost of a 2:1 network, and tolerated the 50 ms reconfiguration delay of a 384-port mechanical switch. These are simulation results, however, and should be read as such.

Offloading the KV cache to lower tiers also depends on conditions. KVStream's paper performance model predicts that the TTFT gain grows with load, but disappears when the reusable portion is already in cache thanks to host memory or request arrival order. Compression methods are lossy, so their effect on quality must be checked per workload. EVICPRESS paper bundles quality and latency into a single utility function precisely because the two trade off against each other.

Scheduling comes with fairness problems. 'Shortest first' improves the average but can starve long requests paper, and ideal policies from the lab do not carry over as is to real hardware paper. Choosing a policy by the single number of average latency leads to failures in tail latency.

Practical guidance: what to use when

Continuous batching and PagedAttention-style block management are close to defaults in today's inference engines (vLLM, SGLang, TensorRT-LLM and others). Rather than treating them as choices, assume they are on and spend your time tuning knobs such as block size, maximum batch size and prefill budget for your workload. The metrics to watch are not average latency but TTFT, tail latency (P90, P99) and KV cache hit rate.

Prefill-decode disaggregation is worth considering when long prompts and long outputs are mixed and interfere heavily with each other, and when bandwidth between GPUs is sufficient. With short prompts and light traffic, transfer cost and operational complexity can easily outweigh the gains. If you quantize KV before sending it under disaggregation, test each model first. Even at the same INT4, some models break down paper.

Agent workloads need separate consideration. The KV cache holds onto GPU memory while waiting on tool calls paper, and reusable prefixes are large enough that storage I/O becomes the bottleneck paper. For such workloads, look first at KV cache offloading and prefetching and at multi-tier storage. If different workloads share one cache, check the hit rate to see whether LRU is making them push out each other's cache paper.

There are three common mistakes: assuming the scheduler does not matter because the GPU and model are the same; expecting improvements measured on synthetic workloads to carry over unchanged to real conversation workloads (in paper, 10.8% shrank to 2.1%); and checking only the compression ratio while skipping quality checks.

Further reading

If you want the big picture of serving first, start with the continuous batching scheduling study paper. It shows through experiments what continuous batching is and how the scheduler changes throughput, TTFT and tail latency. Reading QBA paper next helps you understand the tug-of-war between short-request priority and fairness.

For KV cache management, a natural order is to learn the basics of eviction policies with recency- and frequency-adaptive caching paper, see how compression and eviction are handled together in EVICPRESS paper and KV block joint encoding paper, and then extend reuse to non-prefix positions with CacheTune paper.

For prefill-decode disaggregation, reading SpectrumKV paper together with the optical KV cache network paper lets you see both sides: 'what to send' and 'how to send it.' If you are interested in agent serving, follow with TokenCake paper and KVStream paper.