Appearance
kv cache 及相关优化技术
kv cache
推理的流程中,prefill阶段,并行处理prompt,正常情况下,一个token是一个vector,prefill可以把prompt的token拼成一个
但是prefill后如何生成首token呢?
答:prefill阶段结束后,得到prompt的隐藏层特征。根据最后一个token的隐藏层特征,经过模型头得到首token。
因为首token要产生需要对prompt全量计算,所以首token的计算量是比后续的token的计算量更大的,也就是prefill阶段是计算密集型。后续的token计算依赖于KV cache,需要从显存中频繁搬运数据,所以decode阶段是访存密集型。
得到首token后,后续的token进行的是一个“接字”游戏。首token在embedding后,和WQ,WK, WV相乘得到q,k,v。k和v会拼接到之前的k和v上成为一个包含有之前和当前token信息的更大的K和V矩阵。再使用
这里的问题是:K和V矩阵会在推理的过程中越变越大。
所以针对K V矩阵,有很多优化技术。但是理解这些技术的前提需要理解kv cache。
kv cache。cache的作用,存放计算的中间结果(避免重复计算);存放常用数据,减少数据搬运损耗。推理中的kv cache的作用是避免重复计算。
当前token计算出的k、v会拼接到上一步的K、V上,而上一步的K、V又是由更早的token以同样的方式递归构成的。理解了这个递归,要缓存的东西就很清晰了,就是这个K和V矩阵(所以这个东西叫KV cache)。
为什么没有Q的cache?decode过程中其实只关心当前token的q。prefill阶段计算出之前的Q后,之前的Q就用不到了。
可以实际计算一下有了kv cache之后能省多少计算量:
有没有kv cache的区别
设定 batch size 为 1,序列长度为
推理本质上是一个自回归的"接字"过程。记第
无 KV cache 时,每生成一个 token 都要把当前全部前缀重新送入模型。第
对
有 KV cache 时,每步只需输入当前 1 个 token,历史 K、V 由缓存复用,故每步的计算量恒为
整个序列的计算量为
两者之比为
即计算量降为原来的
kv cache的显存占比估计
确定一个模型、拿到一个硬件环境,来预估能跑多少并发是一个经典的场景问题。
模型的权重占多少显存很好估计:fp16 下,直接参数量
KV cache 的显存则和序列长度直接相关,一个 token 的 KV cache 大小由模型自身结构决定。设:
- 隐藏层维度
(MHA 下 head 数不影响,各 head 拼起来仍是 ) - decoder 层数
- 序列长度
,batch size 为 - 每个元素占
字节(fp16 时 )
K、V 各存一份,则 KV cache 的显存占用为
若用于 KV cache 的可用显存为
生产场景中序列长度存在一个均值
PagedAttention
os中是对内存有一套完善的管理策略的,但是GPU上并没有有一个GPU OS来管理,其内存的分配方式是传统的开发者手动分配。手动分配的问题就复现了早期os内存管理的问题:内存碎片化。 具体的,模型有固定的最大上下文,prompt+response大部分情况是填充不满上下文窗口的,但是传统的显存分配方式必然还是要按照max window来申请,就导致了大部分的显存是空置的。
浪费的显存会导致很多问题:可并发的请求数减小。
PagedAttention借鉴的是os的虚拟内存管理的方式,开发者申请内存是连续的虚拟内存地址,但是页表映射后,内存页是分散在物理内存中的,可以有效避免内存碎片化的问题。 具体的
- PagedAttention把显存划分成block(也就是page),每个block容纳16个token(仅vllm)的k和v
- block是逻辑上连续,但是实际的物理地址不连续,同样有页表(这里应该叫块表)来记录映射关系
- 按需分配。模型每处理16个token,才会申请新的block。不需要提前申请一大块显存
block table
举例来说,如果有输入100个token(prefill阶段),那么会被分配 physical_block_number和physical_block_offset就能读到历史的KV。
意外收获
使用分页机制来管理显存后,结合LLM的业务特征,反而出现了意外之喜。模型对话时,其实有着大量相同的context,既然是相同的,那么完全可以共享一份,也就是多个请求可以共享一个物理块(逻辑块还是独立的)
- 共享前缀。多个请求的sys prompt相同(实际上这个场景很常见),它们的前缀kv完全相同,就可以只存一份
- 共享的请求后续发生了fork怎么办?只读共享时,指向同一块,通过引用计数记录请求个数。如果一个请求发生了fork,在首次写入时这个block就复制出一份这个请求的private block(仍然是从经典的os中衍生)
抢占与恢复
显存的利用率最多只能逼近100%,如果实在不够用,又该如何处理? 这时候又可以在经典知识中寻求答案了。os中如果内存不够会怎么办?会释放部分内存到swap中(如果没有设置swap,就会oom了)。 vllm也会把部分block换到host memory中,资源充足时再换回。 但是对于LLM这种单一的场景,还有一种办法就是重新计算KV cache。 但是无论如何,一旦出现了”抢占”(日志中高频出现preemption相关告警),其实已经说明资源不足了,这时候应该做的是扩容。
Prefix Cache
PagedAttention的意外收获一节观察到了共享前缀的可能,prefix cache就是把这个观察系统化:跨请求复用相同前缀的KV。
理论基础来自K和V的计算公式,
将kv cache切分成block后,前一个请求计算完成的kv block不会立即释放,如果后来的请求匹配上了前缀,就直接复用这个block。
共享前缀的直接收益是大幅降低了TTFT,变相增加了可服务的并发数。
vLLM的automatic prefix caching
如何快速判断kv block是一个请求的前缀?
vLLM的做法是给每个填满token的block计算一个hash
- 父块的哈希(前面所有的前缀块的哈希)
- 本块的token序列
- 额外标识
计算包含父块的哈希,就能保证从sequence开头到当前的block的前缀都是一致的。
匹配与复用流程
有新请求时,vLLM逐块计算前缀哈希,并在hash table中检索。
- 命中:直接把请求的块表指向它,增加引用计数,跳过这部分的prefill
- 未命中:正常prefill计算,计算完毕后把新块的哈希登记进缓存
缓存的淘汰
vLLM结合了引用计数和LRU
- 正在使用的block不能淘汰(引用计数>0)
- 空闲块按照LRU淘汰
vLLM释放块时,是把请求按逆序放进空闲队列尾部。一个请求的最后一个块前缀最长,最不容易被复用。
SGLang RadixAttention
agent时代放大了prefix cache的收益:多轮对话、树状采样下,请求间的共享关系是树状的。
vLLM的匹配是块对齐的,且是线性匹配前缀的,难以表达这种树状的共享关系
RadixAttention用radix tree来管理kv cache的复用。
- 树的每条边代表一段token序列,从根到某节点的路径就是一段前缀,对应缓存的KV
- 新请求到来时,沿树做最长前缀匹配,匹配到的路径部分直接复用KV,只对分叉之后的新内容做计算
- 分叉天然对应”共同前缀+不同后续”,非常契合多轮对话(同一段历史派生多轮)和并行采样(同一prompt采样多个回答)
FlashAttention
前面的PagedAttention和prefix cache优化的都是KV cache的存储与管理,flashattention优化的则是attention的计算范式(就像排序中有耗时的冒泡排序,也有性能高的快排)
attention的计算过程:
- 先计算
- 进行softmax
- 再和
相乘
再补充一些硬件的基础知识
- HBM→SRAM,搬运Q的一行向量和K的一列向量,计算出一个中间结果,SRAM→HBM写回中间结果
- 重复过程1,直到把
和 的矩阵乘计算完毕 - 进行softmax计算,同样也是按照向量进行计算,最终再进行汇总
- 进行过程3的最终结果和V的矩阵乘,重复过程1,直到计算完毕
可以发现,Q, K, V矩阵都是完整的存在HBM中的(
这个过程中充斥大量的SRAM和HBM的数据搬运,它们之间的带宽差了一个数量级,如果搬运次数过多,计算过程就是HBM的带宽受限了。
所以能不能优化掉HBM存的这几个矩阵或者减少搬运次数?哪个矩阵是必须的?(只考虑prefill阶段)
Q:虽然这个矩阵只用到了一次,但是也要完整的存在HBM中。
K:同样只和Q计算一次。但是也要存在HBM中。
中间矩阵
V: 和
那么看起来HBM中需要存4个矩阵,而且都优化不掉?
其实softmax可以进行算法优化,它要计算必须要一整行的值。flashattention使用的不是softmax而是online softmax。区别是它维护了两个全局变量(局部最大值和指数和),在KV块迭代时,不断对临时的O进行修正,最终得到的O和完整的softmax结果是一致的(数学可证明)。
总结来看,flashattention的性能优化其实是削减了中间矩阵
MHA MQA GQA MLA
MHA(multi head attention)就是标准的多头注意力,每个头都有自己的kv cache。整体的规模在
MQA(multi query attention),所有的Q可以共享一组K和V,如果有h个头的情况下,K和V的规模就缩减到了原来的
- 为什么保留了Q而共享一组KV?实验表明,多组KV中,信息是有大量的冗余的。也就是可以使用一组KV来代表所有KV,代价是语义的轻度损失。而Q本身有着查询维度的含义,再进行压缩就退化成了单头注意力了。
GQA(Grouped query attention)。GQA是MHA和MQA的折中方案。将h个头分为g个组,每组共享一组KV。这样,有g组KV,cache的体积缩减为原来的
MLA(multi latent attention)。DeepSeek-V2 提出了 MLA(Multi-Latent Attention),代表了另一种压缩 KV Cache 的思路。MLA的核心思想是,将kv cache压缩进低维潜在空间,只缓存这个低维空间的表示,真正进行推理时再把低维空间的表示还原到高维。这个思路上像是一种用时间换空间或者用算力换带宽的做法。(事实上都没有额外的算力,高低维的转换矩阵直接吸收进了attention的计算公式中)