Paged Attention

文章目的仅供自己回忆或记录用，因此不会写得太详细

What

Paged Attention是一种vllm采用的技术，我的理解是提高内存利用率一种方法

Problem

kv cache需要的内存不是恒定的，decode时kv cache会越来越长，以前采取的做法是按最大序列预分配，用于存储kv cache

这样的问题是：
1.预留太大的序列通常会有一部分用不上，无疑是一种浪费
2.固定的内存需要在物理地址上保持连续，如果只有分散的几块地址，并且每一块都小于kv cache所需的地址长度，那么就算空闲的地址加起来是足够的，也没办法被使用
3.如果有多个请求面向相同的prompt，那么序列靠前生成的kv cache可能会有相同的，但依然会存储多个，这也是一种浪费

Solution

Paged Attention将kv cache分成很多块，使用查找表进行访问。
首先问题1被解决：在分块的时候随着kv cache增大，一个块被填满后就新增一个块，因此内存不再需要是原来那样一整块一整块固定的形式，让内存的浪费可以减少非常多
问题2同样因此被解决，因为不再需要物理内存上的kv cache保持连续：可以将每一块放在物理地址的不同地方，在虚拟内存里用查找表分别对应，仍然可以保证在虚拟内存中是连续的
因为块的划分让物理地址不需要强制保持连续，所以可以使得存储相同内容的块只保留一个，进行块级内存共享，从而解决kv cache存储重复的问题

不过在不同的decode阶段具体实现（例如Beam search，Parallel Sampling）还需要看具体情况