Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference
Jiaming Tang, Yilong Zhao, Kan Zhu, Guangxuan Xiao, Baris Kasikci, Song Han
ICML 2024
cs.CL, cs.LG
2024-06-16
Quest为每页记下Key的逐维最小和最大值,用当前Query估注意力上界,只加载Top-K页。32K上下文、预算2048 token时,自注意力比FlashInfer快7.03倍,4-bit权重下端到端快2.23倍。
长上下文解码慢,慢在搬数据。每生成一个 token,都要把历史 Key 和 Value 整段从显存读进注意力。Llama-7B 在 32K 上下文、FP16 下的 KV cache 大约 16GB,RTX 4090 上用 FlashInfer 读一遍至少 11ms,占到解码时间的 53%。提示 16K、回答 512 个 token 时,解码阶段吃掉总时间的 86% 以上。
注意力很稀疏,但稀疏的位置不固定。LongChat-7B 上,除前两层外,丢掉 90% 以上的 token,PG19 困惑度上升仍不到 0.01。这些关键 token 跟着当前 Query 走。提示写成「A is B. C is D. A is」时,某一层某个头里,问到「D」,token「B」几乎没有注意力;问到末尾的「is」,「B」变成必须看的位置。按历史注意力总分做驱逐(H2O),或只留注意力汇点加最近窗口(StreamingLLM),会把以后才用得上的 token 永久删掉。
Quest 留着全部 KV,只决定这一拍读哪些页。缓存按 PageAttention 分页,和 vLLM 同一粒度。每插入一个 token,该页更新两份与 Key 同维的元数据:逐通道最小值和最大值。
打分算的是点积上界。Query 第 i 维为 Qi,这一页第 i 维的 Key 落在 [mi, Mi]。Qi 与该维任意 Key 的乘积不会超过 max(Qi·mi, Qi·Mi),各维相加就是这一页可能出现的最大 Q·K。真实点积不会更高,关键 token 所在的页不容易漏。界松时会多选一些普通页。
选出 Top-K 页后,只对它们做标准稀疏注意力。选中页里的 token 总数叫做 token budget,实验里从几十取到 4096。前两层稀疏度低于 10%,Quest 以及全部基线都跳过这两层,直接走完整 cache。这个选择和「怎么挑页」是分开的。
访存比例约等于 1/页大小 + 选中页数/总页数。元数据每页只读两个向量,真正的注意力只碰预算内的页。按这个式子,页大小 16、序列 64K、budget 4K 个 token,加载量约为全量 KV 的 1/8。序列短于 128K 时,Top-K 筛选只要 5 到 10 微秒。
模型是 LongChat-7B-v1.5-32k 和 Yarn-Llama-2-7B-128k。基线是 H2O、TOVA、StreamingLLM。材料用完整 KV 预填,问题逐 token 喂入,模拟「答案埋得很深、问句最后才到」。
Passkey 是从长文里找回一串密码。
| 设置 | 预算 | Quest | H2O | TOVA | StreamingLLM |
| 10K / LongChat-7B | 32 | 65% | 0% | 0% | 1% |
| 10K / LongChat-7B | 64 | 99% | 1% | 1% | 1% |
| 100K / Yarn-Llama-2-7B | 1024 | 96% | 2% | 2% | 1% |
| 100K / Yarn-Llama-2-7B | 2048 | 100% | 2% | 2% | 2% |
64 个 token 约是 10K 序列的 0.6%,1024 个 token 约是 100K 的 1%。预算加到 512(10K)和 4096(100K)时 Quest 都是 100%,三条驱逐基线仍不超过 10%。密码在问题出现前就被丢掉了;StreamingLLM 只覆盖最近窗口,窗口外的密码直接看不见。
语言建模看 PG19。LongChat-7B、输入拉到 32K、budget 4096(约总长 1/8),Quest 的困惑度贴近全量 cache。正文没有给出和全量之间的精确差值。
LongBench 取了六项:单文档问答 NarrativeQA、Qasper、MultiFieldQA,多文档 HotpotQA,摘要 GovReport,少样本 TriviaQA。各预算下 Quest 都高于三条基线,大约 1K token 就接近全量 cache。把前两层仍用全量 cache 算进去,做到无损的稀疏度是:Qasper、HotpotQA、MultiFieldQA 各 1/6,NarrativeQA 与 GovReport 各 1/5,TriviaQA 1/10。
速度分内核和端到端。内核在 RTX 4090、CUDA 12.2、Llama-2-7B 上测;端到端在 Ada 6000 上测单请求解码,每个点是生成一个 token 的平均延迟,采样不算在内。
| 对比 | 设置 | 加速 |
| 自注意力 vs FlashInfer | 32K,budget 2048 | 7.03× |
| 端到端 vs FlashInfer | 32K,budget 2048,FP16 权重 | 1.74× |
| 端到端 vs FlashInfer | 32K,budget 2048,4-bit AWQ | 2.23× |
同一无损目标下,NarrativeQA 平均上下文约 24K,TOVA 要 14K token,Quest 要 5K。GovReport 上 Quest 比 TOVA 快 3.82 倍,TriviaQA 快 4.54 倍。基线没有内核,这些倍数是按所需 token 数折算的 FlashInfer 延迟,没计历史分数开销;Quest 侧含打分、Top-K 和稀疏注意力。
省的是带宽,容量没少。并发时 KV 仍占着显存。单条长请求、解码占掉绝大部分时间时,每步不再读完整 KV,改为读每页的最小最大向量,再读预算内的页。预算不随序列线性涨,上下文拉到 32K,延迟比 FlashInfer 涨得慢。
和驱逐方法的差别在召回。H2O、TOVA、StreamingLLM 永久删 token 来换容量,以后的 Query 可能用得上的内容已经不在。Quest 把 KV 留住,按当前 Query 挑页。针埋得深、问题最后才出现时,这个交换成立。
不训练,不改权重,和权重量化叠在一起用。页大小和 budget 都是服务端可调的参数,内核接在 FlashInfer 上。
7.03 倍停在自注意力。前两层几乎砍不动,FFN 和采样还在。FP16 下端到端 1.74 倍;权重收到 4-bit,注意力占比升高,端到端才到 2.23 倍。
正文没有单独的局限一节,边界要从设置里看。
精度只覆盖两个 7B 长上下文模型,LongBench 抽了六项。没有 13B 或 70B,没有连续批处理,也没有多请求吞吐。端到端明确是单 batch 解码,而且去掉了采样。
上界是各维极值之和。页内 Key 散得很开时,没有关键 token 的页也会进 Top-K。图 3 里估计贴近理想稀疏,理想稀疏指困惑度允许多 0.01 时还能丢掉的 token,不是逐步的 Top-10 召回。图 4 只给定性结论:Quest 接近全量注意力,明显高于 H2O,没有按预算的精确召回率。
3.82 倍和 4.54 倍来自折算,双方没有在同一套内核里实测。基线没有内核,数字是把无损所需的 token 数代进 FlashInfer。Quest 自己报的 7.03 倍和 2.23 倍才包含全部算子。
100K 的 passkey 上,H2O 的历史分数只从解码阶段累计,预填用了 FlashAttention,收不到完整注意力图。这会额外拉低 H2O。
每页还要存 Key 的 min 和 max。正文说量化和加大页能压缩这块显存,没给字节数。页越大估计越便宜,上界也越松,精度实验没有单独扫页大小。