上一篇算過，Llama-3.2-1B 的 bf16 GQA KV Cache，每個 token 約需要 32 KiB。

如果只有一條固定長度的 sequence，照順序把 K、V 放進一塊連續記憶體就好。問題是 serving 同時面對很多 requests，而且每條輸出會多長，事前並不知道。

這時真正麻煩的不只是 KV Cache 很大，而是：

要怎麼分配一塊會持續長大、又隨時可能被釋放的記憶體？

連續配置為什麼浪費？

最直覺的做法，是替每個 request 預留一段連續空間，例如直接保留到 max_seq_len。

但一條 request 可能只產生 120 tokens，另一條可能產生 2,000 tokens。若兩者都先保留最大長度，就會出現大量尚未使用、甚至永遠不會使用的空間。

Request A：[已使用][................預留但未使用................]
Request B：[已使用已使用][..........預留但未使用..............]
Request C：[已使用][....預留....]

而當 requests 不斷進入與結束，GPU memory 中還會留下大小不同的洞。總空間可能足夠，卻找不到一塊夠大的連續區域。

這就是 memory fragmentation。

PagedAttention 的核心想法

PagedAttention 借用了作業系統的 virtual memory：不要要求一條 sequence 的 KV Cache 在實體記憶體中連續，而是切成固定大小的 KV blocks。

可以這樣類比：

對 request 來說，token 位置仍然是連續的；實際存放它們的 physical blocks，則可以散落在 GPU memory 中。

Logical blocks：   [0] [1] [2]
                     |   |   |
Block table：       [7] [1] [3]
                     |   |   |
Physical blocks： ...[1]...[3].......[7]...

Attention 的公式沒有改變。差別是 kernel 會先查 block table，再到 physical block 7、1、3 讀取這條 sequence 的 K、V。

手動畫一次 block table

假設每個 block 可以放 4 tokens，一條 prompt 目前有 7 tokens：

Logical block 0：token 0  1  2  3  → Physical block 7
Logical block 1：token 4  5  6  _  → Physical block 1

Block table = [7, 1]

Decode 產生第 8 個 token 時，直接填入 physical block 1 的最後一格，不需要新配置。

Logical block 1：token 4  5  6  7  → Physical block 1

再產生第 9 個 token 時，上一個 block 已滿，memory manager 才取出一個空的 physical block，例如 block 3：

Logical block 2：token 8  _  _  _  → Physical block 3

Block table = [7, 1, 3]

request 結束後，7、1、3 便能歸還給 block pool，立刻給其他 requests 使用。

因此不必一開始猜完整輸出長度，也不必在 sequence 變長時搬動整份 KV Cache。

它解決了什麼？

固定大小、按需配置的 blocks 帶來三個直接效果：

1. 不用預留最大長度：sequence 長大時才增加 block。
2. 減少 fragmentation：所有 physical blocks 大小相同；單條 sequence 的浪費主要留在最後一個尚未填滿的 block。
3. 更容易共享：多條 sequences 若共用同一段 prompt，可以讓 logical blocks 指向相同的 physical blocks；要分岔寫入時，再用 copy-on-write 複製需要修改的 block。

這讓更多 requests 能同時留在 GPU memory 中，也讓 continuous batching 有更大的 batch 空間。

不是完全沒有代價

PagedAttention 多了一層 logical-to-physical mapping，attention kernel 也必須支援非連續的 KV Cache。

block size 本身也有取捨：

Block 太小：block table 較大，管理與存取更零碎
Block 太大：最後一個 block 浪費較多，也較不容易共享

所以 PagedAttention 並不是「免費省記憶體」，而是用少量管理與 kernel 複雜度，換取更高的 KV Cache 使用率。

Reference

• Efficient Memory Management for Large Language Model Serving with PagedAttention
• vLLM — Paged Attention design document
• vLLM — Automatic Prefix Caching