KV Cache in Serving Engines: PagedAttention, Continuous Batching, and Prefix Caching

Status: Draft (2026-10-13), partially measured. The papers and official documentation were directly opened and verified on 2026-10-13. Measurements re-cite the values measured with a single 8GB-class GPU, Qwen3-1.7B, and vLLM 0.31.0 from Part 14 of "Toss ML/AI Infra Preparation" on the same site. Values for larger models and multiple GPUs are unmeasured. Writing rules: Measured data is the default, unmeasured items are marked as "Unmeasured", and unverified items are marked as "Unverified".

Table of Contents

• 1. Throughput is Ultimately a Matter of Batch Size
• 2. PagedAttention: Dividing KV into Blocks
  • Waste in Old Methods
  • Blocks and Block Tables
  • Sharing Blocks
  • Results
• 3. Continuous Batching: Filling Empty Slots at Every Step
  • New Problem: Long Prefills Pause Decoding
• 4. Prefix Caching: Computing the Same Prefix Only Once
• 5. When KV Space is Insufficient
• 6. Summary: And the Wall of GPU Memory
• References

1. Throughput is Ultimately a Matter of Batch Size

Re-stating the conclusion of Part 1. Every time decoding generates a single token, it must read the entire set of weights from memory, so running only a single request leaves most of the GPU's calculators idle. If multiple requests are decoded together when reading the weights once, multiple tokens can be created with the same read. Therefore, increasing the batch size increases throughput.

Each request in a batch must keep its own KV in GPU memory. Since the KV is shared using the memory left over after loading the weights, how densely the KV is packed into the same memory determines the batch size, and thus the throughput. Most KV management techniques in serving engines are designed for this single sentence.

2. PagedAttention: Dividing KV into Blocks

Waste in Old Methods

Serving systems prior to vLLM allocated KV space as a single chunk for each request up to the maximum output length in advance. Since it is unknown how many tokens the output will be, it is inevitably allocated generously. The vLLM paper (Kwon et al., SOSP 2023) divides the waste arising here into three categories.

• Reservation: Pre-allocating space that might be used in the future
• Internal fragmentation: Space where a request finished without ever being used
• External fragmentation: Gaps left between chunks that cannot be used by anyone

In the paper's measurements, existing systems used only 20.4~38.2% of KV memory for actual token storage. According to a figure in the same paper, when serving a 13B model on an A100, about 65% of the memory is weights and nearly 30% is KV. The KV share is originally small, and more than two-thirds of it is wasted.

Blocks and Block Tables

PagedAttention solves this like virtual memory in operating systems. It divides KV into fixed-size blocks(default 16 tokens) and maintains a block tableof "logical block → physical block" for each request. Blocks are placed anywhere in free GPU memory, and when tokens completely fill one block, a new block is allocated at that time.

• Since there are no chunks, external fragmentation disappears.
• Since there is no pre-reservation, there is no reservation waste either.
• The remaining waste is only the empty space in the last blockof each request (less than 16 tokens).

The attention kernel follows the block table to read K and V from scattered blocks. Computation remains the same even if they are not a contiguous array.

Sharing Blocks

Managing in block units allows multiple requests to point to the same block. In parallel sampling or beam search, where multiple answers are generated from a single prompt, the KV for the prompt portion is identical, so reference counts are kept on the blocks and they are shared. They are copied only when someone needs to append to that block (copy-on-write). The KV memory saved by this in the paper's measurements is as follows.

Results

The paper reports that throughput at the same latency level is 2–4x higher than FasterTransformer and Orca (OPT-13B/66B/175B and LLaMA-13B, 1 to 8 A100 40GB/80GB GPUs). Under the ShareGPT workload, the request rate handled was up to 22x higher than FasterTransformer. Since the multiplier varies greatly depending on the comparison target and workload, "2–4x" can be read as a representative value.

3. Continuous Batching: Filling Empty Slots at Every Step

Even if memory is saved, slots are wasted if the batching method is poor. This is because output lengths vary by request. Static batchinggroups a few requests to start and does not accept new requests until all of them finish . Even if a 10-token answer finishes early, its slot remains idle until the 500-token answer finishes.

Orca (Yu et al., OSDI 2022) changed scheduling to the unit of a model iteration. At the end of each step, finished requests are returned immediately, and waiting requests are included starting from the next step. This is continuous batching, which most engines use today. The paper reports that for a GPT-3 175B-class model (16 A100 40GB GPUs), when the median per-token latency was set to 190ms, FasterTransformer processed 0.185 requests per second and Orca processed 6.81 requests (36.9x). The baseline for this comparison is static batching, and this difference includes not only continuous batching but also Orca's other designs.

Continuous batching and PagedAttention need each other. For requests to enter and leave at every step, KV space must be allocated and freed on the fly, but chunk-based reservation only increases gaps. Block-level allocation made this possible.

New Problem: Long Prefills Pause Decoding

Continuous batching leaves the problem shown in Figure (b). When a new request comes in, its prefill must be done in a single step, and if the prompt is long, that step takes a long time, during which other requests in the batch cannot receive their next tokens. The Sarathi-Serve paper (Agrawal et al., OSDI 2024) calls this generation stall and reports that under Yi-34B and 2 A100 GPU conditions, such pauses can last up to several seconds.

The solution, as shown in Figure (c), is to cut long prefills into chunks, distribute them across multiple steps, and interleave them with decoding tokens at every step(chunked prefill). In Table 4 of the same paper (Yi-34B, 2 A100 GPUs, single-step token budget 1,024), the P99 token interval was 0.68 seconds with interleaving alone, and 0.14 seconds when using chunks and "fill decode first" together. Under tail latency constraints, the workload handled was 2.6x higher for Mistral-7B (1 A100 GPU) and up to 3.7x higher for Yi-34B (2 A100 GPUs) compared to vLLM (paper abstract).

Our Measurements. While a single request decoding 3,000 tokens on an 8GB-class GPU with Qwen3-1.7B was running, 3 inputs of 3,500 tokens each were inserted, and the token intervals in the inserted section were measured while changing the number of input tokens put into a single step (--max-num-batched-tokens).

• The maximum token interval was nearly proportional to the chunk size. This matches the time for a single chunk calculated from this GPU's input processing speed (about 8,200 tokens/sec): about 62ms for 512 tokens and about 250ms for 2,048 tokens.
• Making chunks smaller delayed the first token of long inputs by 3~5%, but made decoding less interrupted. Small chunks suit services where tokens must be generated evenly, like chat or voice, while large chunks suit tasks processing long documents all at once.

Chunked prefill reduces intervals but cannot eliminate them. As long as prefill and decoding share the same GPU, they interfere with each other. Disaggregated serving in Part 4 solves this problem in a different way.

4. Prefix Caching: Computing the Same Prefix Only Once

There are many identical prefixes across requests as well. This is true for system prompts attached to all conversations, RAG where multiple queries refer to the same document, and multi-turn conversations that resend the previous turn as-is. As seen in Part 1, if the prefix is the same, its KV is also the same. Therefore, finding blocks already in the GPU and reusing them skips that much prefill.

vLLM's automatic prefix caching (design doc, viewed 2026-10-13) creates a key for each block.

• Key = Hash(key of previous block, token IDs of this block, additional info)
• Additional info includes LoRA adapters, hashes of multimodal inputs, and cache salts separating users.
• Since the key of the previous block is included, a single key represents the entire prefix from the beginning up to that block. Even with the same 16 tokens, if the preceding part differs, the key is different.
• Only full blocks are cached.
• When a request ends, blocks are not immediately deleted but placed in an "empty but content remains" queue, and when space is needed, the oldest ones are evicted (LRU). Blocks of finished requests are placed in the queue from the back so that tails with lower probability of reuse are evicted first.
• The hash function defaults to sha256 starting from v0.11.

Our Measurements. We attached a different 32-token tail per request to a common prefix of 3,000 tokens and sent them one by one.

When hit, it skipped the 3,000-token prefill, making the first token 14x faster. Conversely, under a load with completely non-overlapping prefixes (2,048 input, concurrency 32), the cost of turning it on was about 1.2% in throughput and about 8% in median time-to-first-token (estimated to be hash calculation overhead, not broken down).

Pitfalls in measurement. If you measure performance by repeating the same sentence, the prefix cache will hit, yielding speeds that a GPU cannot normally achieve. Performance test inputs must vary per request, and a common prefix should be intentionally created only when you want to observe cache effects.

5. When KV Space Falls Short

The fact that the upper limit of the batch size is determined by KV is also evident in numbers. In the same actual measurement environment, the KV space was 22,048 tokens, and for a request of 512 input + 128 output = 640 tokens, about 34 requests can fit.

When increasing concurrency from 32 to 64, throughput actually decreased and the first token became 8.6x slower. Requests that lack space wait in the queue. If there is even less space, requests already running evict their KV and get kicked out (preemption), then have their prefill recomputed from scratch. At an input of 2,048 and concurrency of 32, preemption occurred 7 times, and at 1,500 input, 256 output, and concurrency of 64, it occurred 22 times, with median time-to-first-token being 12.5s and 35.4s, respectively. Because the same KV is computed twice, throughput does not increase and only latency increases.

The KV capacity varied between 22,048 and 27,504 tokens depending on each server boot, and near the limit like at concurrency 64, that 20% difference changed the first token time by 2.7x. In operations, it is recommended to record GPU KV cache size in server logs and tune the concurrency upper limit to around "the number of requests the KV can hold given the average request length".

6. Conclusion: And the Wall of GPU Memory

All of these techniques operate inside GPU memory . If GPU space runs short, the prefix cache deletes the oldest blocks first, and recalculates from scratch if the deleted prefix appears again. If there are multiple engine instances, each caches separately, meaning a neighboring instance cannot reuse a KV it has already computed. Part 3 covers LMCache, which places KV outside the GPU (CPU memory, disk, or other servers).

A word from Titi. If you rent out a ping-pong table to "one team for the whole day," many tables sit empty. If you break it down into 30-minute slots, assign the next team right as a slot ends, and let members of the same club share a table, far more people can play in the same gym. PagedAttention and continuous batching do that job.

References

• Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention (SOSP 2023): https://arxiv.org/abs/2309.06180 (Sections 1, 3.1, 4.3, 6.2, 6.3, 7.2, Table 1)
• Yu et al., Orca: A Distributed Serving System for Transformer-Based Generative Models (OSDI 2022): https://www.usenix.org/conference/osdi22/presentation/yu (Section 6.2, Figure 10b)
• Agrawal et al., Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve (OSDI 2024): https://arxiv.org/abs/2403.02310 (Abstract, Sections 3.2, 4, Table 4)
• vLLM Automatic Prefix Cache Design: https://docs.vllm.ai/en/latest/design/prefix_caching.html (Developer documentation, accessed October 13, 2026)
• Measurement Citation: Same site, "Toss ML/AI Infra Preparation" Part 14 (8GB-class GPU, Qwen3-1.7B, vLLM 0.31.0)