When short and long requests share an inference service, VRAM allocation matters alongside computation. PagedAttention stores KV cache in blocks: a context stays logically consecutive while its blocks can occupy separate physical locations. It addresses allocation and reuse; it does not make each token’s keys and values smaller.

中文版 / Chinese version

Why divide the KV cache into blocks?

The KV cache memory estimate asks how much storage is needed. Allocation raises a different question: before generation finishes, how much should a request reserve?

If every request reserves a contiguous region for its maximum length, a short answer holds space it does not yet use. Repeated allocations and releases of different sizes may also leave hard-to-use gaps. Equal-sized blocks let a request acquire capacity as it grows and let other requests use free blocks.

The comparison is with a maximum-length reservation scheme, not a claim about every inference framework. Paging still leaves overhead from unused tail slots, block tables, and engine reservations.

A block table maps logical order to physical storage

Suppose each block holds KV data for four tokens. Ten cached positions need three blocks: two full blocks and one with two occupied slots. A block table [5, 1, 7] maps logical blocks 0, 1, and 2 to physical blocks 5, 1, and 7.

For a zero-based position t and block size b, the logical block is t // b and the offset is t % b. Position 9 maps to logical block 2, offset 1, then physical block 7, offset 1. The attention kernel must understand this layout; splitting a tensor does not automatically make an ordinary kernel compatible.

The name borrows from operating-system paging. It does not mean automatic disk offloading or reading only the last block. Full causal attention still covers the visible history; paging changes where data lives and how it is accessed.

How many tail slots remain unused?

For one unshared sequence with T cached positions and b slots per block, the block count is ceil(T / b), and unused slots equal ceil(T / b) × b − T. An empty sequence allocates no blocks. For a positive integer T, the unused count is between 0 and b − 1.

This counts token slots only. Bytes also depend on layer count, KV heads, head dimension, precision, and alignment. Smaller blocks generally leave fewer tail slots but require finer-grained tables and management. The formula cannot identify a universally best block size.

def block_layout(tokens, block_size):
    if tokens < 0 or block_size <= 0:
        raise ValueError('invalid size')
    blocks = (tokens + block_size - 1) // block_size
    return blocks, blocks * block_size - tokens

assert block_layout(0, 4) == (0, 0)
assert block_layout(8, 4) == (2, 0)
assert block_layout(10, 4) == (3, 2)
for n in range(100):
    b, unused = block_layout(n, 4)
    assert b * 4 >= n and 0 <= unused < 4
block_table = [5, 1, 7]
position = 9
logical, offset = divmod(position, 4)
assert (block_table[logical], offset) == (7, 1)
print('10 tokens:', block_layout(10, 4))
print('token 9 -> physical block', block_table[logical], 'offset', offset)

The pure Python example was executed, covering empty, full, and partial blocks and checking the tail bound for token counts 0 through 99:

10 tokens: (3, 2)
token 9 -> physical block 7 offset 1

It validates capacity arithmetic and address mapping. It does not perform attention or implement vLLM’s allocator, and it says nothing about GPU speedup.

Shared prefixes need matching computation

Paging provides a basis for block-level reuse. Generation branches with the same computed prefix can point to the same physical blocks, using copy-on-write when shared data must change. Which blocks can be shared depends on the engine, cache keys, and boundary handling.

The same word is not enough. KV states depend on the model and preceding context; the same token in another context cannot simply reuse the cache. Prefix caching must distinguish input conditions that affect the computation.

Throughput results depend on request shapes

The original paper appeared in 2023 and was published at SOSP 2023. This is a mechanism explanation, not current news. Its authors reported throughput improvements over FasterTransformer and Orca under specified models and workloads. Those experiments are not a promise for arbitrary hardware and software today.

Record the model, precision, engine version, input and output length distributions, concurrency, and GPU, together with time to first token, per-token latency, and throughput. Higher aggregate token throughput does not automatically improve interactive response time. Serving more requests and returning each user’s answer sooner are different metrics.

If cache capacity is the bottleneck, examine block management. Compute, bandwidth, and queueing bottlenecks still require kernel and scheduling analysis. The earlier deployment article (Chinese) covers other budget items.

References

• Original PagedAttention paper, publicly posted in September 2023, with SOSP 2023 and a formal DOI listed.
• vLLM introduction, a first-party explanation of blocks, sharing, and copy-on-write.
• vLLM v0.18.0 Paged Attention design, a version-specific kernel description rather than a guarantee of current interfaces.

English edition added on October 7, 2026, after the Chinese edition. The article date matches the Chinese edition; it is not the actual time this English edition became public.