KV Cache & PagedAttention

An internal coding assistant receives a repository question with system instructions, file excerpts, a failing test, and earlier tool results. When it emits its next token, it still needs to attend to that history. Recomputing every old attention state at every step would turn one response into repeated replay.

Request A keeps each attention layer's Key (K) and Value (V) vectors after their first computation. A decode step processes one token, appends its K/V state, and reads the cached history to predict the next token. That running state is the KV cache (Key-Value cache). Grouped-Query Attention (GQA) and Multi-Query Attention (MQA) already shrink each token's footprint.

The remaining problem is placement. The cache grows with every token and concurrent request, so variable-length traffic can strand expensive GPU memory. PagedAttention, introduced with vLLM, borrows operating-system paging so live request state sits in small reusable blocks instead of one oversized contiguous reservation per request.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

The examples use full causal attention: each position reads all earlier positions and itself. Sliding-window attention, hybrid architectures, and compressed caches have different storage contracts. Start with A's ordinary full-attention cache, where both its contents and its allocation are easy to inspect.

Why the KV cache exists

Request A relies on two ideas from earlier lessons. Transformer self-attention computes Query, Key, and Value vectors so the current token can weigh earlier tokens.^{[2]Reference 2Attention Is All You Need.https://arxiv.org/abs/1706.03762} Autoregressive generation then produces one token at a time, with each new token able to attend to everything that came before it.

Autoregressive generation

Call the assistant's first request A. Suppose it has already processed $t-1$ tokens. What must the next step carry forward? Without a KV cache, it would re-run the Key and Value projections for every earlier token. With a cache, A writes $k_t$ and $v_t$ once, then later queries read those stored vectors.

For full causal attention, processing token $t$ uses positions 1 through $t$ to predict token $t+1$.^{[2]Reference 2Attention Is All You Need.https://arxiv.org/abs/1706.03762} At one layer and attention head:

$\text{Attention}(q_t, K_{1:t}, V_{1:t}) = \text{softmax}\left(\frac{q_t K_{1:t}^T}{\sqrt{d_k}}\right) V_{1:t}$

The current token's query $q_t$ is scored against every key in $K_{1:t}$ (dot product, scaled by $\sqrt{d_k}$). Softmax turns those scores into weights, and $V_{1:t}$ is blended with those weights. $K_{1:t}$ and $V_{1:t}$ are the Key and Value matrices for tokens 1 through $t$.

Without a cache, replaying the prefix recomputes Key and Value vectors for every earlier position. Across $T$ one-token steps, that's $1+2+\cdots+T$ position-wise K/V projections rather than $T$. Caching removes that repeated projection work, but attention still has to read the growing history. Prompt prefill computes many positions together; it isn't a loop of single-token decode calls.

KV cache: cache K, V from previous steps

At step $t$, compute $q_t, k_t, v_t$ for the new token and append $k_t, v_t$ to the cache. Request A's first five tokens look like this:

With the KV cache, the decode phase (generating one new token at a time) still scales linearly per step in sequence length because each new token attends over all cached tokens. As cache reads grow, long-context decode can become sensitive to memory bandwidth even after caching.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

Those five tokens already show the next problem: even a tiny request writes a growing tensor into GPU memory. Real serving multiplies that cost by layers, KV heads, and concurrent requests.

KV cache memory analysis

Before writing a general formula, compare three concrete tensor shapes. Llama 3 8B and 70B use GQA with 8 KV heads; GPT-3 175B uses full multi-head attention (MHA).^{[3]Reference 3The Llama 3 Herd of Models.https://arxiv.org/abs/2407.21783[4]Reference 4Language Models are Few-Shot Learners.https://arxiv.org/abs/2005.14165}

Memory footprint examples (FP16)

Here 4K means 4,096 tokens and 32K means 32,768. These are full-retention payload extrapolations, not supported-context claims: original GPT-3 trained with a 2,048-token context and alternated dense and locally banded sparse attention layers; the initial Llama 3 releases had 8K contexts. The table counts every cached position in every layer. A sparse runtime that retains fewer positions has a different bill.^{[4]Reference 4Language Models are Few-Shot Learners.https://arxiv.org/abs/2005.14165[3]Reference 3The Llama 3 Herd of Models.https://arxiv.org/abs/2407.21783}

For Llama 3 70B, one 4K-context request already consumes 1.25 GiB of KV cache. A batch of 128 such requests would need 160 GiB of High Bandwidth Memory (HBM), before weights and runtime buffers.

That's beyond a single 80 GB-class accelerator. Memory capacity can cap throughput before raw FLOPs do.

Llama 3 70B has 64 query heads but only 8 KV heads.^{[3]Reference 3The Llama 3 Herd of Models.https://arxiv.org/abs/2407.21783} If it stored a KV head per query head, the cache would be 2.5 MiB per token in FP16. GQA-8 drops that to 320 KiB per token.

At 4K context, that's 10 GiB versus 1.25 GiB for a single request. The architecture has already bought an 8× reduction before the allocator makes any decision.

Each token stores a Key vector and a Value vector across every layer and KV head:

For each token, store Key and Value (the $2$) across every layer and KV head. Each vector has $d_{\text{head}}$ dimensions, and $P_{\text{bytes}}$ is the stored precision. In MHA, $n_{\text{kv-heads}} = n_{\text{heads}}$. GQA and MQA use fewer KV heads, which shrinks the cache directly.^{[5]Reference 5GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints.https://arxiv.org/abs/2305.13245[6]Reference 6Fast Transformer Decoding: One Write-Head is All You Need.https://arxiv.org/abs/1911.02150}

This is the tensor-payload calculation. A deployed engine may also reserve quantization scales, block tables, temporary workspaces, communication buffers, graph memory, and allocator headroom. Use the formula to reason about slopes, then profile the runtime before setting admission limits.

def cache_gib(layers: int, kv_heads: int, head_dim: int, bytes_per_value: int, tokens: int) -> float:
    if any(type(value) is not int or value <= 0 for value in (layers, kv_heads, head_dim, bytes_per_value)):
        raise ValueError("cache dimensions and bytes per value must be positive integers")
    if type(tokens) is not int or tokens < 0:
        raise ValueError("tokens must be a nonnegative integer")
    bytes_per_token = 2 * layers * kv_heads * head_dim * bytes_per_value
    return bytes_per_token * tokens / (1024 ** 3)

for label, heads in [("MHA-64", 64), ("GQA-8", 8), ("MQA-1", 1)]:
    size = cache_gib(layers=80, kv_heads=heads, head_dim=128, bytes_per_value=2, tokens=4096)
    print(f"{label}: {size:.2f} GiB at 4K tokens")

MHA-64: 10.00 GiB at 4K tokens
GQA-8: 1.25 GiB at 4K tokens
MQA-1: 0.16 GiB at 4K tokens

GQA shrinks bytes per token. It doesn't stop a naive allocator from reserving far more than those bytes. That's the next failure.

The memory fragmentation problem

In a naive serving system, each request gets one contiguous KV buffer. You might wonder why the engine can't simply grow each buffer token by token, the way a dynamic array does on a CPU.

Growing a contiguous allocation can require allocating a larger region and copying the existing tensor. Repeating that operation wastes work. But maximum-length reservation isn't forced by CUDA: runtimes can reuse memory pools, use stream-ordered allocation, or commit virtual pages dynamically. NVIDIA's cudaMallocAsync and cudaFreeAsync provide a pool-based alternative to globally synchronizing allocation operations. Their lifetimes still require correct ordering across every stream that accesses the allocation.^{[7]Reference 7Using the NVIDIA CUDA Stream-Ordered Memory Allocator, Part 1https://developer.nvidia.com/blog/using-cuda-stream-ordered-memory-allocator-part-1/}

To avoid mid-generation reallocation, naive engines made a blunt compromise: reserve a single contiguous buffer sized for the configured maximum sequence length (such as 8,192 tokens) up front as soon as a request arrives.

Suppose Request A currently has 600 cached tokens. What can Request B use from A's untouched reservation? Nothing while A owns it. If A finishes at token 600, the reservation finally frees up, but that empty tail remained locked and unusable throughout A's entire execution.

Types of memory waste

That static contiguous reservation wastes memory in three distinct ways identified by the vLLM team:^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

1. Internal fragmentation: Request A reserves 8,192 slots but finishes generating at token 600. The 7,592 slots it never used remain trapped inside A's reservation, unavailable to any other request until A finishes.
2. External fragmentation: As requests with variable lengths finish at different times, the allocator frees variable-sized chunks, leaving scattered holes across VRAM. Even if total free memory across all holes is plenty for a new request, no single contiguous region is large enough to satisfy a new max-length reservation.
3. Reservation waste: Even slots that A will eventually use in later decode steps (such as token 3,000 in a 4,000-token sequence) are reserved from the very first step. That memory sits idle for hundreds of decode cycles, locked away from concurrent work.

The vLLM team's 2023 introduction reported 60% to 80% waste in the systems it studied.^{[8]Reference 8vLLM: Easy, Fast, and Cheap LLM Serving with PagedAttentionhttps://vllm.ai/blog/2023-06-20-vllm} The paper's serving experiments synthesized workloads from ShareGPT/Alpaca token-length distributions and Poisson arrivals, rather than replaying production timing traces. Those historical results show a real packing problem; they don't establish today's waste fraction for every runtime.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

bytes_per_token = 320 * 1024
max_tokens = 8192
live_tokens = [600, 1250, 4000, 128]

reserved = len(live_tokens) * max_tokens * bytes_per_token
live = sum(live_tokens) * bytes_per_token
waste_fraction = 1 - live / reserved

print(f"reserved: {reserved / 1024**3:.2f} GiB")
print(f"live state: {live / 1024**3:.2f} GiB")
print(f"unused reservation: {waste_fraction:.1%}")

reserved: 10.00 GiB
live state: 1.82 GiB
unused reservation: 81.8%

If max-length reservations waste most of the pool, the next question is how to allocate only live tokens without needing one huge contiguous region.

PagedAttention (vLLM)

Virtual memory for KV cache

Operating systems solved physical memory fragmentation decades ago using virtual memory paging. Rather than demanding a single contiguous region of physical RAM for every process, the OS divides virtual memory into fixed-size pages (such as 4 KiB) and maps them via a page table to arbitrary physical frames scattered across DRAM. A process perceives a smooth, contiguous address space, while the underlying memory manager allocates uniform physical frames on demand.

PagedAttention borrows the logical-to-physical mapping idea. Its software block table is not the operating system's hardware page table:^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

• Logical blocks: Divide a request's token positions into groups of $B$. Block 0 covers positions $0$ through $B-1$; block 1 covers $B$ through $2B-1$.
• Physical blocks: Reusable slots in GPU cache storage. A token-block ID can index corresponding storage in multiple layer tensors. It needn't describe one contiguous chunk containing every layer and head.
• Block table: Mapping metadata maintained by the memory manager and supplied to the GPU kernel, so each logical block resolves to the correct physical storage.

Physical blocks don't need to sit next to each other in VRAM. The engine assigns blocks as needed. Reuse requires that no running request or in-flight kernel still depends on the old contents. With prefix caching, an unreferenced block can remain cached and reusable until the pool evicts it.^{[9]Reference 9Automatic Prefix Cachinghttps://docs.vllm.ai/en/stable/design/prefix_caching/}

What paging saves, and what it doesn't

Within a uniform pool, a free block doesn't need a neighboring free block to serve a one-block allocation. That removes the variable-sized-hole problem at this boundary. It doesn't prove that every byte of GPU memory is usable by every cache group.

For basic full-attention storage with no extra reservations, a request wastes at most $B-1$ slots in its last block. With $B=16$, one live token uses sixteen slots: 93.75% of those slots are unused. At 120 tokens, eight blocks reserve 128 slots: 6.25% are unused. Long aligned requests can have no tail waste. Count occupied slots and state the denominator before quoting a percentage.

The 2023 paper reported 2–4× throughput, not a universal concurrency multiplier. Its comparisons used particular models, A100 deployments, workloads, and reimplemented Orca reservation policies. Paging preserves the intended attention operation, but changing a GPU kernel can still change floating-point rounding.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

Block size involves a clear trade-off:

• Smaller blocks (such as 8 or 16 tokens): Minimize tail waste and allow finer-grained memory sharing, but require larger block tables and slightly less regular memory access.
• Larger blocks (such as 32 or 64 tokens): Reduce table entries and can improve a kernel's access efficiency, but coarsen sharing and leave larger partial tails. The paper's best range was 16–128 for ShareGPT and 16/32 for Alpaca. Modern backend constraints and workloads need their own check.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

Reading attention through a block table

How does a GPU compute attention when Key and Value tensors are scattered across non-contiguous physical blocks?

A kernel could gather K/V into a contiguous temporary tensor, but that adds copying and workspace. A paged-KV-aware kernel can instead read through the table. Its basic addressing contract is:

1. Resolve the logical position: For sequence position $i$, compute: $\text{logical\_block} = \lfloor i / B \rfloor, \quad \text{slot\_offset} = i \pmod B$
2. Look up the physical block: Read the device-accessible table for this request: $\text{physical\_block\_id} = \text{block\_table}[\text{logical\_block}]$
3. Load the correct vectors: Combine the physical ID and slot with the actual tensor layout, KV-head selection, and strides. K and V can have different packed layouts; a two-stride formula doesn't describe every backend.
4. Apply validity and attention: Exclude unfilled positions and respect the model's attention mask. Compute scaled scores, softmax, and the weighted value result using the selected kernel's reduction strategy.

Paging doesn't prescribe one warp per head, a particular load instruction, or FlashAttention's online-softmax implementation. vLLM's historical kernel walkthrough describes warps processing KV blocks and an intermediate logits array in shared memory; it explicitly warns that it no longer describes the current code. Use it as a worked historical implementation, not a contract for every modern attention backend.^{[10]Reference 10Paged Attention: Historical Kernel Walkthroughhttps://docs.vllm.ai/en/latest/design/paged_attention/}

Direct reads avoid a mandatory whole-cache gather copy before each attention call. They don't eliminate cache writes, copy-on-write block copies, or transfers between devices.

Paging changes the kernel contract

Non-contiguous physical blocks recover stranded HBM, but the attention kernel must follow the block table and gather K/V from those addresses. PagedAttention therefore needs paged-attention kernels; a contiguous-cache kernel isn't a drop-in consumer.

The original vLLM microbenchmark measured 20-26% higher attention-kernel latency than FasterTransformer's contiguous kernel, from block-table walks, extra branches, and variable lengths.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180} That's a kernel-only comparison. End-to-end throughput still rose dramatically in the paper's A100 experiments because recovered HBM admitted larger batches, so measure allocator capacity and kernel speed together.

vAttention is a counter-design. It reserves a contiguous virtual-address range for each KV cache and backs virtual pages with physical GPU memory on demand through CUDA virtual-memory APIs.^{[11]Reference 11vAttention: Dynamic Memory Management for Serving LLMs without PagedAttentionhttps://arxiv.org/abs/2405.04437} The kernel still sees contiguous virtual addresses, so existing contiguous attention kernels can run without a paged-KV interface. Complexity moves into virtual-memory mapping, page commitment, and platform support.

Neither layout wins by definition. PagedAttention has broad serving-engine adoption and explicit block-sharing. A contiguous-virtual design may reuse more existing kernels but depends on the runtime, driver, page granularity, and workload. Compare end-to-end throughput, latency, memory utilization, and implementation constraints on the target stack.

def allocated_tokens(live_tokens: int, block_size: int) -> int:
    if type(live_tokens) is not int or live_tokens < 0 or type(block_size) is not int or block_size <= 0:
        raise ValueError("live tokens must be nonnegative and block size positive integers")
    return ((live_tokens + block_size - 1) // block_size) * block_size

lengths = [1, 120, 505, 1000, 4096]
block_size = 16
for length in lengths:
    allocated = allocated_tokens(length, block_size)
    unused = allocated - length
    print(f"{length} live tokens -> {allocated} slots, {unused} unused ({unused / allocated:.2%})")

assert max(allocated_tokens(length, block_size) - length for length in lengths) < block_size

1 live tokens -> 16 slots, 15 unused (93.75%)
120 live tokens -> 128 slots, 8 unused (6.25%)
505 live tokens -> 512 slots, 7 unused (1.37%)
1000 live tokens -> 1008 slots, 8 unused (0.79%)
4096 live tokens -> 4096 slots, 0 unused (0.00%)

Implementation sketch

The manager below is a CPU-side sketch of the block table. vLLM coordinates allocation on the host and provides mapping metadata to CUDA kernels that read K and V. This class doesn't allocate GPU tensors, run a scheduler, share blocks, or implement prefix caching.

PagedKVCacheManager starts with a stack of free physical IDs, highest first, so the first pop() returns 19 in a 20-block pool. allocate hands request A one block. Each append_slot returns the physical block index and slot offset for the new token. When A later needs a fifth token with block_size = 4, the manager pops block 18.

class PagedKVCacheManager:
    """
    Manages the mapping between logical pages and physical GPU blocks.
    Doesn't store the actual tensors (that happens in GPU memory).
    """

    def __init__(self, num_blocks: int, block_size: int):
        if any(type(value) is not int or value <= 0 for value in (num_blocks, block_size)):
            raise ValueError("num_blocks and block_size must be positive integers")
        self.block_size = block_size
        # Stack of free physical block indices
        self.free_blocks: list[int] = list(range(num_blocks))

        # Maps request_id -> list of physical block indices
        # Example: { "A": [19, 18] }
        self.block_tables: dict[str, list[int]] = {}

        # Maps request_id -> number of processed tokens, including prompt tokens
        self.seq_lens: dict[str, int] = {}

    def allocate(self, request_id: str) -> None:
        """Initialize a new request with one empty block."""
        if not isinstance(request_id, str) or not request_id.strip():
            raise ValueError("request ID must be nonempty text")
        if request_id in self.block_tables:
            raise ValueError(f"request already allocated: {request_id}")
        if not self.free_blocks:
            raise MemoryError("toy KV block pool exhausted")

        first_block = self.free_blocks.pop()
        self.block_tables[request_id] = [first_block]
        self.seq_lens[request_id] = 0

    def append_slot(self, request_id: str) -> tuple[int, int]:
        """
        Reserves the cache position for one token being processed.
        Allocates a new block if the current last block is full.
        Returns (physical_block_index, slot_offset_within_block).
        """
        if request_id not in self.block_tables:
            raise KeyError(f"unknown request: {request_id}")
        current_blocks = self.block_tables[request_id]

        token_idx = self.seq_lens[request_id]

        # Allocate a fresh block when the previous one is full.
        if token_idx > 0 and token_idx % self.block_size == 0:
            if not self.free_blocks:
                raise MemoryError("toy KV block pool exhausted")
            new_block = self.free_blocks.pop()
            current_blocks.append(new_block)

        block_id = current_blocks[-1]
        slot_offset = token_idx % self.block_size
        self.seq_lens[request_id] = token_idx + 1
        return block_id, slot_offset

    def free(self, request_id: str) -> None:
        """Release all blocks associated with a request back to the pool."""
        if request_id in self.block_tables:
            blocks = self.block_tables.pop(request_id)
            self.free_blocks.extend(blocks)
            del self.seq_lens[request_id]

manager = PagedKVCacheManager(num_blocks=20, block_size=4)
manager.allocate("A")
for _ in range(5):
    print("A", manager.append_slot("A"))

manager.allocate("B")
print("B", manager.append_slot("B"))

manager.free("A")
print("free blocks:", len(manager.free_blocks))

A (19, 0)
A (19, 1)
A (19, 2)
A (19, 3)
A (18, 0)
B (17, 0)
free blocks: 19

allocate grabs one block. append_slot pulls the next block only when the current one is full. free returns every block A held, so B can keep running while those IDs go back on the stack. This toy pool has no variable-sized holes; a production runtime still has weights, kernels, and allocator state outside the KV block pool.

Tracing a small example

The manager uses block_size = 4 and num_blocks = 20. Free IDs form a stack, so pop() yields 19, then 18, then 17.

First, Request A arrives. allocate("A") pops physical block 19, giving the table {"A": [19]} and sequence length 0.

After four processed tokens, block 19 holds offsets 0 through 3, and seq_lens["A"] = 4. Prompt tokens count too; the allocator doesn't distinguish prefill from decode.

At token five, token_idx = 4 and 4 % 4 == 0, so block 19 is full. append_slot("A") pops 18, writes at offset 0, and leaves the table as {"A": [19, 18]}, matching A (18, 0) in the output.

Next, Request B arrives. allocate("B") pops block 17, so the tables are {"A": [19, 18], "B": [17]}.

Finally, A finishes. free("A") returns 19 and 18; B still holds 17, leaving 19 free IDs in the 20-block pool.

Blocks are grabbed one at a time and returned when the request completes. Real engines add a reference count per physical block (for shared prefixes) and copy-on-write when a sequence writes into a shared block.

PagedAttention changes storage rather than the intended attention math. It reduces long reservation tails; it doesn't remove the final partial block. Recovered capacity can improve throughput when the scheduler and kernels turn it into useful work.

block_size = 4
block_table = [19, 18]
sequence_length = 5

def resolve(token_position: int) -> tuple[int, int]:
    if type(token_position) is not int or not 0 <= token_position < sequence_length:
        raise ValueError("position must name a processed token")
    logical_block, slot = divmod(token_position, block_size)
    return block_table[logical_block], slot

for position in [0, 3, 4]:
    print(f"token {position}: physical block, slot = {resolve(position)}")

assert resolve(0) == (19, 0)
assert resolve(4) == (18, 0)

token 0: physical block, slot = (19, 0)
token 3: physical block, slot = (19, 3)
token 4: physical block, slot = (18, 0)

Read actual values through the table

An address trace isn't enough to check attention. Continue in the same Python session, but use a fresh four-block pool with two slots per block. A and B interleave allocations, so A's table becomes [3, 1]. Each slot below stores one two-dimensional key and value for one head at one layer. The numbers are fixed test data, not projections from a trained model.

Predict what happens if the read includes A's unfilled last slot. It contains a deliberately extreme sentinel, so an incorrect length bound should change the answer substantially.

import math

pool = PagedKVCacheManager(num_blocks=4, block_size=2)
sentinel = ((1000.0, 1000.0), (999.0, 999.0))
storage = [[sentinel for _ in range(2)] for _ in range(4)]
pairs = [
    ((1.0, 0.0), (2.0, 1.0)),
    ((0.0, 1.0), (0.0, 3.0)),
    ((1.0, 1.0), (4.0, 2.0)),
]

def write(request, pair):
    block, offset = pool.append_slot(request)
    storage[block][offset] = pair

def read(request):
    return [storage[pool.block_tables[request][position // 2]][position % 2]
            for position in range(pool.seq_lens[request])]

def attend(query, kv_pairs):
    scores = [sum(q * k for q, k in zip(query, key)) / math.sqrt(2)
              for key, _ in kv_pairs]
    weights = [math.exp(score - max(scores)) for score in scores]
    denominator = sum(weights)
    return tuple(sum(weight * pair[1][dim] for weight, pair in zip(weights, kv_pairs))
                 / denominator for dim in range(2))

pool.allocate("A")
write("A", pairs[0])
pool.allocate("B")
write("B", ((-1.0, 0.0), (-5.0, -5.0)))
write("A", pairs[1])
write("A", pairs[2])

query = (1.0, 0.5)
expected = attend(query, pairs)
actual = attend(query, read("A"))
assert pool.block_tables["A"] == [3, 1]
assert read("A") == pairs  # Check position order too; attention sums are permutation-invariant.
assert all(math.isclose(a, b, abs_tol=1e-12) for a, b in zip(actual, expected))
assert attend(query, read("A") + [sentinel]) != expected
wrong_mapping = storage[3] + [storage[2][0]]  # Reads B instead of A's third token.
assert attend(query, wrong_mapping) != expected
print("A block table:", pool.block_tables["A"])
print("attention output:", tuple(round(value, 6) for value in actual))
print("paged == contiguous; wrong mapping and unfilled-tail controls differ")

A block table: [3, 1]
attention output: (2.461842, 1.90474)
paged == contiguous; wrong mapping and unfilled-tail controls differ

This checks K/V gathering, logical order, and the valid sequence-length boundary on CPU. It doesn't implement a paged GPU kernel, a complete Transformer, or a speed benchmark. The class also reserves one empty block at allocate, so a zero-token request temporarily uses a block; the earlier ceiling formula describes occupied token storage, not that toy API convention.

Packing live blocks raises the admission ceiling. Now push Request A until it needs one more block and the pool has none. The scheduler still has to decide how A gives up its place and gets it back.

Preemption when the pool is empty

vLLM pairs PagedAttention with a scheduler. Memory is a shared pool, so an exhausted pool turns allocation into a scheduling decision: delay A, evict another request, or recover A's cache later.

In a heavily loaded multi-tenant system, the GPU block pool can still become exhausted. Current vLLM V1's default recovery releases the preempted request's block ownership, reschedules it, and recomputes missing cache state later. Shared or retained prefix blocks needn't all be erased. The optimization guide warns that preemption can hurt end-to-end latency.^{[12]Reference 12Optimization and Tuning.https://docs.vllm.ai/en/latest/configuration/optimization.html[9]Reference 9Automatic Prefix Cachinghttps://docs.vllm.ai/en/stable/design/prefix_caching/}

The original vLLM paper and legacy V0 runtime also evaluated CPU swapping. Keeping both designs separate makes the tradeoff clear:^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

1. Recomputing (default current vLLM V1): Release the request's blocks and rerun missing prior work when it resumes. This spends extra FLOPs rather than transferring the missing cache over Peripheral Component Interconnect Express (PCIe).
2. Swapping (original paper and legacy V0): Move KV blocks from GPU HBM to CPU RAM, then swap them back in later. This preserves previous work but consumes transfer bandwidth. This isn't the default V1 preemption path described by the current optimization guide.^{[12]Reference 12Optimization and Tuning.https://docs.vllm.ai/en/latest/configuration/optimization.html}

Recompute spends extra FLOPs; swap spends PCIe bandwidth. Both paths make A pay before it can resume, so frequent preemption belongs in the capacity plan rather than in the happy-path throughput estimate.

Default preemption isn't the whole offload story. Current vLLM also documents optional KV-offloading connectors that move reusable KV state between GPU and CPU memory. Enabling one changes the transfer path; it doesn't make legacy V0 swapping the default V1 scheduler behavior.^{[13]Reference 13KV Offloading Usage Guidehttps://docs.vllm.ai/en/latest/features/kv_offloading_usage/}

Once GPU space opens up, the request can resume after obtaining the needed cache state. Other runtimes may expose offload or swap designs. Recovery costs belong in the latency budget; packing alone doesn't prevent frequent preemption.

Suppose a two-rank deployment serves Llama 3 70B (80 layers, 8 KV heads, head dimension 128, FP16 cache) with an 8K context window. That cache adds 320 KiB per token, or 2.5 GiB per full request across the model. If its eight KV heads are evenly sharded over two ranks, each rank stores 1.25 GiB. With 16-token blocks, 8,192 tokens fill exactly 512 blocks: tail waste is zero, not 4%. The paper's measured average isn't a universal overhead multiplier.

Don't derive an admission limit from advertised HBM minus model weights alone. Profile how much per-rank memory remains after weights, kernels, communication buffers, graphs, and safety headroom. With an assumed 8 GiB usable KV payload budget per rank, six fully occupied 8K requests fit. The seventh needs more blocks than remain. This is arithmetic under a stated budget, not measured serving capacity.

bytes_per_token = 2 * 80 * 8 * 128 * 2
context_tokens = 8192
tp_ranks = 2
block_size = 16
kv_budget_per_rank_bytes = 8 * 1024**3

bytes_per_rank_block = bytes_per_token // tp_ranks * block_size
available_blocks = kv_budget_per_rank_bytes // bytes_per_rank_block
blocks_per_request = (context_tokens + block_size - 1) // block_size
capacity = available_blocks // blocks_per_request

print(f"per request per rank: {blocks_per_request * bytes_per_rank_block / 1024**3:.2f} GiB")
print(f"available blocks: {available_blocks}; blocks per request: {blocks_per_request}")
print(f"payload ceiling: {capacity} full 8K requests; {available_blocks % blocks_per_request} blocks remain")

per request per rank: 1.25 GiB
available blocks: 3276; blocks per request: 512
payload ceiling: 6 full 8K requests; 204 blocks remain

Packing live blocks raises how many requests fit. It doesn't keep the GPU busy when one long decode holds a static batch hostage. To see the second bottleneck, keep the same Request A and compare its finish time with a longer Request B.

Continuous batching (iteration-level batching)

PagedAttention pairs especially well with continuous batching (also called iteration-level scheduling). The dedicated continuous batching lesson owns the scheduler. This lesson stays on the memory interaction.

Static batching limitations

A needs 20 decode iterations while B needs 200. In traditional static batching, the system waits for $N$ requests, bundles them, and processes that batch until all requests finish. A completes early, but its slot remains tied to B's long tail, so the shorter request contributes no useful work for the remaining iterations.

The continuous batching approach

Continuous batching, made explicit in systems like Orca, schedules at iteration granularity.^{[14]Reference 14Orca: A Distributed Serving System for Transformer-Based Generative Models.https://www.usenix.org/conference/osdi22/presentation/yu} After A emits an End-of-Sequence (EOS) token or reaches another stopping condition, the scheduler can retire it and admit waiting work at a later scheduling boundary. Unshared blocks become reusable after pending GPU accesses finish; a prefix policy may retain their contents.

That replacement can keep a batch slot productive instead of waiting for B. Continuous batching supplies opportunities to change the live batch; paged allocation makes freed capacity easy to reuse. Neither guarantees that the next request meets its deadline.

Orca's historical GPT-3 175B evaluation reported up to 36.9× throughput over FasterTransformer at the same latency level. Its system combined iteration-level scheduling with selective batching of model operations. The comparison doesn't isolate one feature's speedup or establish modern serving performance.^{[14]Reference 14Orca: A Distributed Serving System for Transformer-Based Generative Models.https://www.usenix.org/conference/osdi22/presentation/yu}

A dynamic batch needs an effective memory-management policy. Paging is one approach; vAttention's virtual-memory design shows that iteration-level scheduling doesn't require PagedAttention specifically.^{[11]Reference 11vAttention: Dynamic Memory Management for Serving LLMs without PagedAttentionhttps://arxiv.org/abs/2405.04437}

from math import ceil

block_size = 16
live_tokens = {"A": 48, "B": 5}

def blocks(tokens: int) -> int:
    return ceil(tokens / block_size)

before = sum(blocks(tokens) for tokens in live_tokens.values())
del live_tokens["A"]  # A emits EOS; scheduler retires it before next iteration.
live_tokens["C"] = 30
after = sum(blocks(tokens) for tokens in live_tokens.values())

print(f"blocks before retire/admit: {before}")
print(f"blocks after retire A and admit C: {after}")
assert after <= before

blocks before retire/admit: 4
blocks after retire A and admit C: 3

Iteration-level admission creates and frees live sequences constantly. Block tables also make a different trick possible: sharing physical blocks. That sharing has two very different policies.

How serving engines build on PagedAttention

Memory sharing: parallel sampling, beam search, and copy-on-write

Many LLM serving patterns produce multiple output sequences from a single prompt:

• Parallel sampling: Generating $N$ candidate responses from one prompt (such as $N = 4$ for temperature sampling, Best-of-N reranking in reasoning tasks, or parallel drafting in speculative decoding).
• Beam search: Maintaining the top $K$ candidate hypotheses, where candidates share identical history for early tokens and branch later.

A system that stores a separate prompt cache for each branch duplicates that payload. For a 4,096-token prompt on Llama 3 70B, four private copies require $4 \times 1.25 = 5.0\text{ GiB}$. Sharing the prompt can reduce occupied cache slots; fixed GPU pool storage itself may remain allocated.

Reference-counted Copy-on-Write (CoW) permits safe branch sharing:^{[8]Reference 8vLLM: Easy, Fast, and Cheap LLM Serving with PagedAttentionhttps://vllm.ai/blog/2023-06-20-vllm}

1. Fork: Each branch's table can reference the same valid prompt blocks. Reference counts track their owners.
2. Read: Shared contents needn't be duplicated for attention. Readers still compete for bandwidth and kernel resources; safe sharing isn't zero hardware contention.
3. Append: After a full shared block, allocate a new block. To append inside a shared partial block, first copy its valid contents into private storage and update ownership. This is necessary even if two branches happen to produce identical next tokens.
4. Retire: Release the branch's references. A block can become reusable only after other owners and pending GPU accesses no longer require it. A prefix-cache policy can retain unreferenced contents for future hits.

Try the dangerous case: A and B share three valid slots in a four-slot block. Both branches will write their fourth position. A write into the shared empty slot doesn't change B's three-token prefix, but B's later write would overwrite A's fourth K/V pair. A reference count protects ownership only if the append path obeys it.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

This separate CPU fixture stores scalar stand-ins for K/V pairs. First observe the aliasing bug, then copy the valid prefix before either branch appends. The earlier manager doesn't implement this sharing path.

storage = [[10, 20, 30, None], [None] * 4]
tail_blocks = {"A": 0, "B": 0}
references = {0: 2, 1: 0}
free_blocks = [1]

storage[tail_blocks["A"]][3] = 90
storage[tail_blocks["B"]][3] = 80
assert storage[tail_blocks["A"]][3] == 80  # B corrupted A's appended state.
print("without copying, A's fourth value:", storage[tail_blocks["A"]][3])
storage[0][3] = None  # Reset the fixture before the safe writes.

def append_fourth(branch, value):
    old_block = tail_blocks[branch]
    assert storage[old_block][3] is None
    if references[old_block] > 1:
        if not free_blocks:
            raise MemoryError("no block available for copy-on-write")
        new_block = free_blocks.pop()
        storage[new_block] = storage[old_block][:3] + [None]
        tail_blocks[branch] = new_block
        references[old_block] -= 1
        references[new_block] = 1
    storage[tail_blocks[branch]][3] = value

append_fourth("A", 90)
assert storage[tail_blocks["B"]] == [10, 20, 30, None]
append_fourth("B", 80)  # Now B is the only owner of the original block.
assert references == {0: 1, 1: 1} and not free_blocks
assert storage[tail_blocks["A"]] == [10, 20, 30, 90]
assert storage[tail_blocks["B"]] == [10, 20, 30, 80]
print("with copy-on-write:", {branch: storage[block] for branch, block in tail_blocks.items()})

without copying, A's fourth value: 80
with copy-on-write: {'A': [10, 20, 30, 90], 'B': [10, 20, 30, 80]}

Only A copies the three valid entries; B can write the original block after its reference count falls to one. A full shared block would instead stay shared while each branch allocates its next block. In a GPU implementation, order the copy before the destination write and preserve the source until all readers finish. The fixture checks branch isolation, not CUDA stream synchronization.^{[7]Reference 7Using the NVIDIA CUDA Stream-Ordered Memory Allocator, Part 1https://developer.nvidia.com/blog/using-cuda-stream-ordered-memory-allocator-part-1/}

Prefix caching across independent requests

Copy-on-write safely shares blocks across branches forked within the same request. Reusing state across separate, independently arriving requests requires an additional prefix cache policy: retain completed prefix blocks in memory after a request finishes, match incoming prompts against cached token sequences, verify security isolation keys, and only then map the new request's block table to the existing physical blocks. vLLM documents this feature as Automatic Prefix Caching (APC).^{[9]Reference 9Automatic Prefix Cachinghttps://docs.vllm.ai/en/stable/design/prefix_caching/}

Suppose 100 independent requests share a compatible 1,000-token prompt, a warm available cache, and 16-token blocks. vLLM's prefix cache reuses complete blocks. In this full-attention snapshot, 992 tokens form 62 reused blocks and the remaining 8 occupy a private partial block per request:^{[9]Reference 9Automatic Prefix Cachinghttps://docs.vllm.ai/en/stable/design/prefix_caching/}

• Without prefix caching: 100 × 63 = 6300 occupied blocks cover those prefix tokens.
• With compatible prefix caching: 62 + (100 × 1) = 162 blocks cover the shared full prefix and private tails.

That's a 97.4% reduction in occupied prefix blocks for this snapshot. It frees capacity for other work, not necessarily CUDA allocations back to the driver. Evicted prefixes, a cold cache, different model state, or different isolation keys change the result.

Now make the prompt exactly 1,008 tokens, filling 63 blocks. Can current vLLM skip the entire prompt? No: it recomputes the last token to obtain next-token logits. Its block-aligned hit limit can therefore require recomputing the whole last block. This behavior is present in v0.28.0 and the current source checked October 10, 2026.^{[15]Reference 15vLLM v0.28.0: KV Cache Managerhttps://github.com/vllm-project/vllm/blob/v0.28.0/vllm/v1/core/kv_cache_manager.py} Its V1 append-only block tables can also retain duplicate full blocks until a request is freed; full blocks aren't automatically deduplicated during every step.^{[9]Reference 9Automatic Prefix Cachinghttps://docs.vllm.ai/en/stable/design/prefix_caching/}

requests = 100
prefix_tokens = 1000
block_size = 16
full_blocks = (prefix_tokens - 1) // block_size  # Leave work to obtain next-token logits.
tail_tokens = prefix_tokens - full_blocks * block_size
private_tail_blocks = (tail_tokens + block_size - 1) // block_size

without_cache = requests * (full_blocks + private_tail_blocks)
with_compatible_cache = full_blocks + requests * private_tail_blocks
saved_fraction = 1 - with_compatible_cache / without_cache

print(f"shared full blocks: {full_blocks}; private tail tokens per request: {tail_tokens}")
print(f"occupied prefix blocks: {without_cache} without reuse -> {with_compatible_cache} with reuse")
print(f"saved occupied prefix slots: {saved_fraction:.1%}")
assert (without_cache, with_compatible_cache) == (6300, 162)

shared full blocks: 62; private tail tokens per request: 8
occupied prefix blocks: 6300 without reuse -> 162 with reuse
saved occupied prefix slots: 97.4%

RadixAttention (SGLang)

SGLang's RadixAttention organizes reusable token prefixes in a radix tree, a tree whose edges can store sequences rather than one token each. Its original design evicts unused leaf prefixes under an LRU policy when space is needed.^{[16]Reference 16SGLang: Efficient Execution of Structured Language Model Programshttps://arxiv.org/abs/2312.07104} A hit skips computation for the compatible cached prefix; the unmatched suffix still needs prefill. A full miss recomputes the prompt. It doesn't promise to retain every request forever.

That makes it particularly effective for multi-turn chat and agentic workloads where long prompt prefixes repeat across calls.^{[16]Reference 16SGLang: Efficient Execution of Structured Language Model Programshttps://arxiv.org/abs/2312.07104}

FlashInfer and kernel optimization

FlashInfer supplies attention kernels and APIs for serving workloads, including paged KV caches and variable-length sequences.^{[17]Reference 17FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving.https://arxiv.org/abs/2501.01005} It doesn't replace the memory manager. Whether a particular backend improves decode performance depends on its supported shapes, hardware, and workload.

PagedAttention vs. FlashAttention

These names are easy to mix up, but they solve different problems.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180[18]Reference 18FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness.https://arxiv.org/abs/2205.14135}

• PagedAttention: A KV-cache layout and allocation strategy. It places cached K/V tensors in blocks and supports block sharing; a prefix-cache policy decides cross-request reuse.
• FlashAttention: An IO-aware attention kernel. It tiles attention so the GPU does less wasteful movement between HBM and on-chip memory, especially during full attention computation.^{[18]Reference 18FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness.https://arxiv.org/abs/2205.14135}

Modern serving stacks often use both or close variants together.^{[17]Reference 17FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving.https://arxiv.org/abs/2501.01005} PagedAttention makes the cache fit and stay shareable. FlashAttention-style kernels make attention itself faster once those tensors are in place.

Reducing KV cache at the architecture level

Return to Request A's per-token bill. PagedAttention can pack those bytes, but it can't make the tensor payload smaller. That requires changing how much K/V state the model produces in the first place.

Grouped-Query Attention (GQA) shrinks the baseline cache. Instead of a Key and Value head per query head, GQA groups query heads so they share KV heads. Ainslie et al. found intermediate group counts recovered much of MHA quality while keeping MQA-like inference benefits after uptraining; other models still need their own quality evaluation.^{[5]Reference 5GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints.https://arxiv.org/abs/2305.13245}

Llama 3 70B is the worked example: 64 query heads, 8 KV heads, so each token's cache is 8× smaller than full MHA with those query heads.^{[3]Reference 3The Llama 3 Herd of Models.https://arxiv.org/abs/2407.21783}

Multi-Head Latent Attention (MLA) takes a different architectural route: it jointly compresses keys and values into a learned low-rank latent representation, so its cache contract isn't just a smaller n_kv_heads value.^{[19]Reference 19DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Modelhttps://arxiv.org/abs/2405.04434} MLA can shrink the cache further, but it needs an MLA-aware model and execution path. It isn't a serving switch for a GQA checkpoint.

GQA reduces the size of the problem, while PagedAttention solves the allocation of the problem. They are complementary when the selected model architecture and serving runtime support both.

Practical considerations

Start capacity planning with two separate ledgers: model weights and request state. A typical GPU-resident deployment shares fixed weights across requests while its occupied KV state grows with the live workload. Weight offloading and prefix sharing change the accounting. Sizing only for weights can still leave too little space for long conversations.

1. The prefill vs. decode bottleneck

LLM inference still has two useful workload categories:^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180[20]Reference 20DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving.https://arxiv.org/abs/2401.09670}

• Prefill: Processing the input prompt. For sufficiently large prompt batches, dense matrix multiplications often make this phase compute-heavy and highly parallelizable.
• Decode: Generating tokens one by one. At common serving batch sizes, repeatedly loading weights and growing KV state often makes this phase memory-bandwidth-sensitive.

PagedAttention manages both prompt and generated-token storage. Current vLLM V1 can mix decode work and chunks of prefill under an iteration token budget. Chunking limits prompt work in a batch, but a chunk can still interfere with running decodes; measure the result.^{[12]Reference 12Optimization and Tuning.https://docs.vllm.ai/en/latest/configuration/optimization.html[21]Reference 21SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefillshttps://arxiv.org/abs/2308.16369} At larger scale, disaggregated serving separates pools to tune time to first token (TTFT) and inter-token latency independently, adding state-transfer and coordination costs.^{[20]Reference 20DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving.https://arxiv.org/abs/2401.09670}

These synthetic timings only flag which measurements to inspect next. TTFT includes queueing and transport as well as prefill; inter-token delay can also include scheduler or network stalls. Neither number identifies a cause by itself. Check both, since a request can breach both thresholds.

import math

traces = [
    {"prompt_tokens": 8000, "ttft_ms": 780, "inter_token_ms": 22},
    {"prompt_tokens": 200, "ttft_ms": 48, "inter_token_ms": 23},
    {"prompt_tokens": 220, "ttft_ms": 51, "inter_token_ms": 61},
    {"prompt_tokens": 8000, "ttft_ms": 900, "inter_token_ms": 75},
]

def inspect_signals(trace):
    if any(not math.isfinite(trace[key]) or trace[key] < 0 for key in ("ttft_ms", "inter_token_ms")):
        raise ValueError("latencies must be finite and nonnegative")
    flags = []
    if trace["ttft_ms"] > 500:
        flags.append("inspect queueing, prefill, and transport")
    if trace["inter_token_ms"] > 50:
        flags.append("inspect decode, scheduling, and transport")
    return flags or ["within sample thresholds"]

for trace in traces:
    print(f"{trace['prompt_tokens']} prompt tokens: {'; '.join(inspect_signals(trace))}")

8000 prompt tokens: inspect queueing, prefill, and transport
200 prompt tokens: within sample thresholds
220 prompt tokens: inspect decode, scheduling, and transport
8000 prompt tokens: inspect queueing, prefill, and transport; inspect decode, scheduling, and transport

2. Context window limits

Even with PagedAttention, the KV cache still grows linearly with context length. A Llama 3 70B-shaped GQA cache at 128K tokens needs 40 GiB in FP16. At that scale, KV memory can rival or exceed the room left after loading weights, so long-context serving may need distribution, KV-cache quantization, explicit compression, or smaller admitted contexts.

• Compression / eviction: Research systems such as SnapKV^{[22]Reference 22SnapKV: LLM Knows What You are Looking for Before Generationhttps://arxiv.org/abs/2404.14469} and H2O^{[23]Reference 23H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Modelshttps://arxiv.org/abs/2306.14048} retain selected KV positions instead of the complete history. Selection is approximate and can remove evidence a later token needs, so memory savings require quality checks.
• Quantization: FP8 halves raw bytes per value relative to FP16. Scales, workspaces, replication, and kernel support still affect actual capacity; this doesn't promise twice the serving throughput.

The right lever depends on where Request A's bytes are stuck. Ask which boundary is limiting before choosing a technique.

KIVI's local 2-bit path uses per-channel quantization for keys and per-token quantization for values: its experiments found persistent high-magnitude key channels, but no matching fixed pattern in values. It also keeps a recent-token residual in full precision.^{[24]Reference 24KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cachehttps://arxiv.org/abs/2402.02750} That changes the representation and bytes stored for K/V; it isn't a drop-in two-bit setting for any block allocator. Check kernel support, residual-buffer overhead, dequantization cost, and task quality on the deployed model.

SnapKV and H2O change which tokens remain in a runtime cache. CacheGen addresses transfer: it encodes precomputed KV into compact, bandwidth-adaptive bitstreams, streams chunks, and decodes them back into regular KV tensors before attention.^{[25]Reference 25CacheGen: KV Cache Compression and Streaming for Fast Large Language Model Servinghttps://arxiv.org/abs/2310.07240} That reduces stored and transferred bytes, not necessarily the steady-state local tensor footprint after reconstruction. Lossy reconstruction still needs quality evaluation.

Mooncake separates prefill and decode, pools CPU/DRAM/SSD resources with GPU workers, and transfers KV state over RDMA when reuse justifies movement.^{[26]Reference 26Mooncake: A KVCache-centric Disaggregated Architecture for LLM Serving.https://arxiv.org/abs/2407.00079} Distribution changes location and scheduling, but doesn't itself shrink each cached value. Measure time to first token, inter-token latency, throughput, and network traffic under the target workload.

Compare these as separate interventions with the same model, hardware, precision, prompt/output distribution, concurrency, and correctness target before changing a capacity or latency promise.

3. Distributed inference

In tensor parallelism (TP), a runtime may shard KV heads across ranks when the model layout permits it. TP splits a layer's weights (and often its KV heads) across GPUs so each rank holds a slice. If the number or grouping of KV heads doesn't divide cleanly across ranks, a runtime may replicate some KV state instead. Capacity planning must use the actual deployed layout, not assume ideal division.

Paged allocation still happens per rank, but logical block growth has to stay aligned across ranks so token positions 0-15, 16-31, and so on map to the correct local KV blocks on every worker.

The physical block IDs don't have to match across GPUs. Consistent logical bookkeeping is the invariant: each rank must know which local block corresponds to each logical block for its shard of the cache.

Exact coordination is runtime-specific. Capacity planning needs a safer rule: profile each rank's local KV allocation after sharding or replication instead of assuming the global tensor-payload bytes divide perfectly by TP degree.

The helper below budgets only two explicitly chosen layouts: equal head sharding or full replication. Divisibility is necessary for the first calculation, not proof that the model and runtime support that TP configuration. An unverified layout should stop the estimate rather than silently invent a supported deployment.

def local_kv_heads(kv_heads: int, tp_ranks: int, layout: str) -> int:
    if any(type(value) is not int or value <= 0 for value in (kv_heads, tp_ranks)):
        raise ValueError("head and rank counts must be positive integers")
    if layout == "replicated":
        return kv_heads
    if layout == "head-sharded" and kv_heads % tp_ranks == 0:
        return kv_heads // tp_ranks
    raise ValueError("unknown layout or indivisible head sharding")

for kv_heads, ranks, layout in [(8, 2, "head-sharded"), (8, 2, "replicated"), (1, 4, "replicated")]:
    heads = local_kv_heads(kv_heads, ranks, layout)
    print(f"{kv_heads} KV heads on TP={ranks}, {layout}: {heads} local heads")

8 KV heads on TP=2, head-sharded: 4 local heads
8 KV heads on TP=2, replicated: 8 local heads
1 KV heads on TP=4, replicated: 1 local heads

Make the pool run out

Use PagedKVCacheManager(num_blocks=2, block_size=4) in a fresh session. Allocate A and B, then append four slots to A. Before running a fifth append, predict the free list, A's length, and both block tables after the failure.

The free list is empty. A must remain at length four with table [1]; B still owns [0], even though it hasn't processed a token. The failed append must change none of that state. Free B, retry A's append, and it should return (0, 0). Repeatedly freeing B must not insert block zero twice. These checks catch ownership errors that a successful five-token trace misses.

Continue after defining the manager, with a fresh tiny pool. The snapshot below protects the failure boundary rather than merely checking the successful trace.

tiny = PagedKVCacheManager(num_blocks=2, block_size=4)
tiny.allocate("A")
tiny.allocate("B")
for _ in range(4):
    tiny.append_slot("A")

def snapshot():
    return (tuple(tiny.free_blocks),
            {name: tuple(ids) for name, ids in tiny.block_tables.items()},
            dict(tiny.seq_lens))

before = snapshot()
try:
    tiny.append_slot("A")
except MemoryError as error:
    print("blocked:", error)
else:
    raise AssertionError("the full pool must reject another block")
assert snapshot() == before
print("failed append preserved state:", snapshot() == before)

tiny.free("B")
tiny.free("B")  # A repeated release must not create another free copy.
assert tiny.free_blocks == [0]
retry = tiny.append_slot("A")
assert retry == (0, 0)
assert tiny.seq_lens == {"A": 5}
assert tiny.block_tables == {"A": [1, 0]} and not tiny.free_blocks
print("retry after freeing B:", retry)

blocked: toy KV block pool exhausted
failed append preserved state: True
retry after freeing B: (0, 0)

Next compare 1,000, 1,008, and 1,009-token prompts. Assume all compatible full-attention prefix blocks are available and apply vLLM's inspected block-aligned limit for obtaining logits. Predict the uncomputed tokens before running: why does the aligned 1,008-token prompt still need sixteen?

block_size = 16
requests = 100
for prompt_tokens in [1000, 1008, 1009]:
    hit_tokens = ((prompt_tokens - 1) // block_size) * block_size
    remaining = prompt_tokens - hit_tokens
    shared_blocks = hit_tokens // block_size
    private_blocks = (remaining + block_size - 1) // block_size
    occupied = shared_blocks + requests * private_blocks
    assert 0 < remaining <= block_size
    print(f"{prompt_tokens} prompt tokens: {hit_tokens} reused, {remaining} recomputed; "
          f"{occupied} occupied prefix blocks for {requests} requests")

1000 prompt tokens: 992 reused, 8 recomputed; 162 occupied prefix blocks for 100 requests
1008 prompt tokens: 992 reused, 16 recomputed; 162 occupied prefix blocks for 100 requests
1009 prompt tokens: 1008 reused, 1 recomputed; 163 occupied prefix blocks for 100 requests

These occupied-block snapshots exclude unreferenced cached blocks, continuation tokens, hybrid cache groups, and other reservations. Prefix capacity is an implementation-dependent accounting question, not a universal 99% saving at an aligned boundary.

On a GPU system, follow these correctness checks with a real serving benchmark: compare outputs, actual allocated bytes, preemption counts, TTFT, and inter-token latency under the same model and request trace. The CPU examples establish address and arithmetic invariants only. They don't measure CUDA-kernel speed, concurrency, numerical behavior in reduced precision, or production admission limits.