Prompt Caching & KV Cache Architecture

Without PagedAttention, each request pre-allocates a KV cache sized to the maximum sequence length at request start. A request limited to 2048 tokens allocates memory for 2048 tokens even if it only uses 100 — 95% waste. When many requests are in flight simultaneously, this fragmentation means the GPU can serve only 10-20 concurrent requests despite having enough memory for 100. The result: poor GPU utilization and high queuing latency.

PagedAttention divides the KV cache into fixed-size blocks (typically 16 tokens each). A block table maps each request's logical blocks to physical memory blocks — just like OS virtual memory page tables. Blocks are allocated on-demand as the sequence grows and freed immediately upon completion. This eliminates pre-allocation waste: a 100-token response uses only 7 blocks instead of 128 blocks. GPU utilization jumps from 20-30% to 60-80%.

Many applications prepend the same system prompt (1,000-5,000 tokens) to every user message. Without prefix caching, each request recomputes the KV cache for this shared prefix — wasting computation and memory. Prefix caching stores the KV blocks for shared prefixes and reuses them across requests. For a 4,096-token system prompt, this saves ~60% of the TTFT (time-to-first-token) for every request. Anthropic exposes this as a pricing feature: cached input tokens cost 90% less.

LLM decoding is serial: one token per forward pass of the full model. Speculative decoding parallelizes this: a small draft model (e.g., 1B parameter model) generates K candidate tokens in K forward passes; the large target model verifies all K tokens in a single forward pass using tree attention. If the target model agrees with the draft's top-K tokens, all K are accepted atomically. For highly predictable outputs (code completion, structured responses), speculative decoding achieves 3-5x throughput improvement.

vLLM's scheduler manages the block table and continuous batching together. When a new request arrives, the scheduler checks if there are free blocks for the prompt plus estimated completion. If GPU memory is tight, it can preempt (swap to CPU) low-priority requests. The iteration-level scheduler (run after every token) can add new requests to the batch whenever a sequence completes — maximizing GPU utilization without sacrificing latency for in-progress requests.