What is paged attention, and why did it make such a difference?

I have memory left, yet another request cannot start. The catch is ownership: each running request has reserved enough contiguous space for its longest possible answer. Empty slots inside those reservations are internal fragmentation; unusable gaps between them are external fragmentation.

Llama 3 70B in BF16 keeps 320 KiB per tokenOne token, worked out2 vectors × 80 layers × 8 KV heads × 128 entries × 2 bytes = 327,680 bytes327,680 ÷ 1,024 = 320 KiBLogical payload across the model, before sharding and allocator overhead.. The film first reserves that payload badly, then follows actual toy keys and values through scattered blocks. The ten-token layout stores the full stop as input text; the decode calculation follows the pilot and stops before processing it.

They will ask What is paged attention, and why did it make such a difference?
The 30-second version I split each sequence's cache into fixed blocks and map logical blocks to physical blocks with a table. Allocating blocks as the sequence grows avoids reserving its maximum length, leaving at most one partly filled block in this layout. The attention kernel follows that table to read the right keys and values. The same indirection also supports sharing, eviction and moving blocks between memory tiers.

For request lengths 179, 402, 155 and 293, reserving 512 each gives 0.671 GB reserved, 0.337 GB used, 0.334 GB wastedThe reservation, worked outReserved: 4 × 512 × 327,680 = 671,088,640 bytesUsed: (179 + 402 + 155 + 293) × 327,680 = 337,182,720 bytesWasted: 671,088,640 − 337,182,720 = 333,905,920 bytesDivide bytes by one billion for decimal GB.. The PagedAttention paper measured 20.4 to 38.2 percent useful cache memory in its comparison systems, and reported under four percent waste with two to four times throughput at the same latency. Those are benchmark results, not universal multipliers.

How do the table and shared prefix work?

For a token at position j, I divide by the block size to find its logical block and use the remainder as its offset:

\[\text{physical block}=\text{table}[\lfloor j/b\rfloor],\qquad \text{offset}=j\bmod b\]

The toy’s table is [6, 1, 9]. With four slots per block, position 5 is in physical block 1, offset 1: “song”. The rows are unchanged. Finding them requires indirection, which is why paged attention needs a compatible kernel as well as an allocator.

Two requests can point at the same immutable prefix. In the film’s generic fork, both tables start [6, 1]; before their partial tails diverge, one tail is copied to physical block 4. The tables become [6, 1] and [6, 4]. That is copy-on-write. Current vLLM V1 prefix caching reuses full blocks, so the partial-tail fork illustrates the general mechanism, not its automatic prefix caching path.

\[\text{saved bytes}=(u-1)pc\]

Read that as redundant copies times shared prefix tokens times bytes per token. Twenty requests sharing 4,096 tokens save 25.50 GBShared prefix, worked out(20 − 1) × 4,096 × 327,680 = 25,501,368,320 bytesOne prefix remains; private suffixes are additional.. Exact reuse needs matching preceding context, positions and model state. I put stable prompt content first and variable content last.

With sixteen-token blocks, each block holds 5 MiB, with at most 4.6875 MiB unused per sequenceBlock and tail, worked out16 × 327,680 = 5,242,880 bytes = 5 MiB15 × 327,680 = 4,915,200 bytes = 4.6875 MiBAt most fifteen empty slots in the last allocated block. Block size depends on the implementation.. The engine can preallocate its pool; it need not reserve a maximum-length slab for every request.

What happens when the pool fills?

I first reclaim cached prefixes that no running request uses. If that is insufficient, a request is preempted. Recompute keeps token ids and rebuilds state later; swap keeps the state in host memory. vLLM V1 defaults to recompute and removed its old swap preemption path.

\[t_{\text{swap}}=2Tc/r,\qquad t_{\text{recompute}}\approx2PT/F\]

The first counts two trips for T tokens of c bytes at link rate r. The second divides approximate forward work, twice parameters P times tokens, by compute rate F.

For 4,096 tokens, the references are 41.94 ms to swap and 584.37 ms to recomputeTwo resource clocksCache: 4,096 × 327,680 = 1,342,177,280 bytesSwap: 2 × 1,342,177,280 ÷ (64 × 10⁹) ≈ 0.04194 secondsRecompute: 2 × 70.55 × 10⁹ × 4,096 ÷ (989 × 10¹²) ≈ 0.58437 secondsIdeal link time versus one H100-equivalent at peak, omitting attention. These are not measured latencies for the sharded model.. Recompute can spend otherwise available arithmetic and fit into chunked batches; swap consumes a shared link and host buffers. The isolated estimates do not settle the server’s policy.

Where can the state go, and which engine manages it?

A reusable prefix can outlive one GPU allocation. LMCache spans GPU, CPU, disk and remote stores. Dynamo has four corresponding tiers; TensorRT-LLM exposes host cache capacity and eviction priorities. Mooncake builds around a shared CPU and SSD cache pool. I care whether retrieving a prefix beats rebuilding it, not merely whether another tier exists.

Separating prefill and decode also requires a transfer. A 32k prompt, meaning 32,768 tokens, carries 10.74 GBThe handoff payload32,768 × 327,680 = 10,737,418,240 bytesWhole-model payload across all shards; decimal GB.. Time is payload divided by effective bandwidth: 23.86 ms over directional NVLink, 214.75 ms at 400 Gb/s, or 858.99 ms at 100 Gb/sIdeal serialized transfer timesNVLink: 10,737,418,240 ÷ (450 × 10⁹) ≈ 0.02386 seconds400 Gb/s ÷ 8 = 50 GB/s: payload ÷ (50 × 10⁹) ≈ 0.21475 seconds100 Gb/s ÷ 8 = 12.5 GB/s: payload ÷ (12.5 × 10⁹) ≈ 0.85899 secondsOne effective path, no contention or overhead. Sharding can spread transfers across paths.. NVIDIA’s 900 GB/s NVLink specification is bidirectional: I use half for one direction. At low load, coordination can outweigh separation’s benefit.

All three engines page, batch continuously, reuse prefixes and support FP8 cache. vLLM V1 hashes blocks with their preceding prefix and enables prefix caching by default. SGLang’s radix tree combines reuse with cache-aware scheduling and LRU leaf eviction. TensorRT-LLM’s default backend has been PyTorch since 1.0. NIXL connects disaggregated workers in vLLM, Dynamo and llm-d; SGLang also supports Mooncake’s transport.

Chunked prefill, introduced by Sarathi-Serve, splits a prompt among batches already decoding. Current vLLM documentation says enabled by default whenever possible. Smaller interruptions help existing users, while the prompt takes more scheduling steps. The workload decides the trade.

Rapid fire: can you do these from memory?

  1. Distinguish internal and external fragmentation. Which reservation does paging remove?
  2. Find token position 5 through [6, 1, 9] with four-token blocks.
  3. Why does a divergent partial tail need copy-on-write, and how does V1 prefix caching differ?
  4. Compare recompute and swap by resource, not just milliseconds.
  5. What does a 32k cache handoff cost, and why is 900 GB/s the wrong directional rate?