Fathom：基于卸载KV缓存的稀疏解码的逐查询读取深度

# Fathom：针对卸载KV缓存的稀疏解码逐查询读取深度  
来源：https://arxiv.org/html/2609.17652  

###### 摘要  
当智能体会话达到百万token规模且多个会话同时驻留时，KV缓存及其索引位于主机内存中，而扫描所有键以进行Top-k步骤的排序过程成为限制解码速度的通信瓶颈。我们提出Fathom——一种键扫描方法，其中每个查询决定读取每个键通道的位数。4位K缓存以通道优先的比特平面形式存储，因此平面的前t位精确对应通道的t位量化器，查询通过对其通道方差加权重要性进行逆向水填充来分配其位预算。在Qwen3-8B模型处理百万token时，Fathom的解码步骤在GPU时间上比Double Sparsity、Loki和SparQ（r=32）的136位扫描快1.67倍；在相同GPU时间内，与SparQ的68位读取（r=16）相比，Fathom减少了18%的字节传输量，且在7种模型与上下文配置中有6种注意力误差更低。在RULER风格的任务中，每个token的扫描均与精确Top-k解码匹配；在实际编码智能体会话中，Fathom在92位读取量下达到了最精确136位扫描的步骤一致性。其存储形式即量化服务栈已持有的4位K副本，且当索引驻留在GPU内存中时该方法并无加速效果。  

## 1 引言  
编码或浏览智能体会携带数十万token的上下文持续数小时，其中大部分为缓存内容而非新生成内容，服务器同时托管多个此类会话。其KV缓存无法与模型权重一起放入GPU内存，因而驻留在主机内存或较慢的存储层，导致解码步骤受限于跨互联传输的数据量。解码过程本身已是带宽受限的——每个生成token需读取一次模型权重，而在长上下文下还需每层读取一次完整KV缓存。卸载使缓存读取成为主导开销。分组查询注意力（GQA）和2至4位KV量化缩小了缓存规模。Top-k稀疏注意力则缩减了*读取量*，仅获取注意力分数最高的k个键值对。由于分数在读取前未知，所有此类方法首先扫描所有n个键的廉价表示以进行排序。扫描过程是一系列n条小记录的流，其开销以每位token的比特数衡量，随n增长而增加，而获胜键的获取量则不随之增长。以Qwen3-8B（36层，8个KV头各含128通道，每个KV头对应4个查询头）在32k token下的数据为例说明分配：密集注意力读取完整的bf16 KV缓存，每步4.8 GB。Top-k（每查询头k=512）获取四个头获胜键的并集，每个KV头最多2048行，在我们的运行中每步约200 MB——此开销不随上下文长度增长。而Loki、Double Sparsity或SparQ（r=32）的扫描每键读取32个坐标的4位数据加块缩放因子，每层头对的每token开销136位，32k下每对557 KB，每步总计160 MB。该项随上下文线性增长，百万token下可达5.1 GB，而获胜行数保持在200 MB左右。本文所有比特数均为每token每KV头每层，遵循§4的约定。  

降低扫描开销有两个杠杆：一是减少扫描对象（如页、块或地标），二是减少每键读取位数。现有token扫描方法预先固定位数。Loki读取每键的r个主成分坐标；Double Sparsity从离线4位标签缓存中选择c个通道读取；SparQ允许查询选择组内查询头求和|q|最大的r个通道并以全深度读取；缩略图扫描则以2位读取所有通道。这些方法中，每个通道的读取深度均相同。本文允许按查询和通道决定读取深度，基于两个观察：  

1. 量化误差随位数每增加1位下降4倍。若键的通道j已读取t_j位深度，增加一位将使剩余分数误差按与g_j·4^{-t_j}成比例的量降低（g_j为该通道对本次查询分数方差的贡献）。重要通道的第一位价值远高于第四位，而重要通道的第四位可能不如次要通道的第一位。按边际价值分配位数即为逆向水填充，且存在闭式解。  
2. 若4位K缓存以通道优先的比特平面存储，通道的前t个平面*本身*即为该通道的t位升半量化器（共享相同块缩放因子），因此前缀读取是精确且连续的，无需低精度副本。  

两者结合将4位键副本转化为多分辨率索引，每个查询可按需读取深度。我们在7种模型与上下文配置、32k与128k的RULER风格任务，以及方法设计与非设计硬件场景下，将Fathom与Loki、Double Sparsity、SparQ、2位缩略图及块地标索引进行对比评估。字节节省在所有设置中均成立；当扫描字节需通过PCIe传输时，该节省转化为时间节省——§7分析了具体条件。  

#### 贡献。  
- 在驱动本研究的场景中获得实测结果：当KV缓存及其索引位于主机内存时，解码步骤在256k token下GPU时间加速1.37倍，1M token下加速1.67倍，精度等于或优于Double Sparsity和Loki；相比SparQ的68位读取，在相同GPU时间内减少18%字节传输量，且精度提升1.1–5.3倍（§5.1，§5.2）。  
- 提出比特平面键存储（前缀读取即为精确低精度量化器），并为每个通道提供基于逆向水填充的逐查询读取深度规则，可选每层预算校准机制（§3）。  
- 在7种最高128k token的设置中，相比Double Sparsity的136位扫描实现1.8–2.9倍等误差字节节省；在RULER风格任务中与精确Top-k预知结果持平；在实际编码智能体会话中，以92位读取量达到最精确136位扫描的步骤一致性（§5.3，§5.5，§5.6）。  
- 基底规则：对具有QK范数（查询与键归一化，如Qwen3）的模型使用原始通道，对其他模型（Llama-3.1，Qwen2.5）使用键的Karhunen-Loève变换（KLT）平面（§3.5）。  
- 针对HBM驻留场景的分析：当索引位于GPU高带宽内存（HBM）时该方法无加速效果，并通过每字节算术分析说明原因（§7），同时包含所有设计选择的消融实验（§6，附录D）。  

#### 实测结果摘要。  
Fathom专为单一场景构建：当KV缓存和扫描索引位于主机内存时的稀疏解码。表1总结了该场景及方法无效场景下的测量结果。  

表1：不同场景下的实测结果（A100 GPU，Qwen3-8B，k=512）。每解码步骤的GPU时间；136位扫描指Double Sparsity、Loki和SparQ（r=32）。  

## 2 背景与相关工作  
#### Top-k解码。  
给定查询q∈R^D和键K∈R^{n×D}，精确注意力权重为softmax(qK^⊤/√D)。注意力质量集中于少数键，因此H2O和StreamingLLM采用驱逐策略，而Loki、Double Sparsity、SparQ和Quest保留完整缓存并在解码时通过近似分数选择。我们在统一协议下评估所有方法：前4个token和最后32个token始终保留（遵循StreamingLLM和H2O），其余k-36个键为各查询头下该方法评分最高的键；各方法通过其选择集合上的精确注意力输出衡量。SparQ将未选注意力质量重新分配至均值的方法未应用于任何其他方法。  

#### Loki。  
Loki将键旋转至校准键的主成分（PCA）基底，并通过前r个坐标（保持模型精度）对查询评分；原始方法不存储键副本，其r=32读取为每token 512位。为与4位扫描逐字节对比，我们使用与其他方法相同的块缩放因子将r个坐标量化为4位（r=32时为136位），并按校准分数方差排序基底（此排序对Loki有利）。其精度受秩限制：在Qwen3-8B上，32坐标基底在32k时遗漏后期层方向，fp16坐标无法修复（§6）。  

#### Double Sparsity。  
Double Sparsity保留离线选择的每头c个通道标签缓存（基于分数贡献的校准统计），并以4位扫描。我们根据校准文本上每头的|q|均值与|k|均值的乘积选择通道，取c=32（通道总数的1/4）；论文默认值为1/16（8通道），亦报告1/2和全通道结果。c=32时，标签缓存读取每token 136位（fp16块缩放因子），与其他固定深度扫描相同，且每token存储17字节（紧邻K缓存）。该方法是Qwen3模型上最强的离线基线；在其他三种模型上Loki更强。  

#### SparQ。  
SparQ让每个查询选择|q_j|最大的r个通道，并从通道优先的K存储中读取。在分组查询注意力下，其公开规则在Top-r前对共享KV头的查询头求和|q|，因此每个KV头读取一组r通道。SparQ原始存储为fp16（r=32时为512位）；采用我们赋予各扫描的4位编码（§4），r=16时为68位，r=32时为136位。我们实现了该规则。更强的变体允许每个查询头独立选择通道并读取选择的并集，此非SparQ方法；我们仅在消融实验中报告一次（§6）。SparQ还在Top-k前对组内近似分数求和；我们对所有方法均不采用此策略，始终按查询头独立选择Top-k。  

#### 块与地标选择。  
Quest按通道最小最大键对16-token页评分；ShadowKV按平均键对8-token块评分，在GPU保留低秩K缓存并卸载V；InfLLM按代表性token对块评分。此为“减少扫描对象”的杠杆，与我们的方法正交。我们的地标基线遵循ShadowKV：每个8-token块的fp16平均键，每token 256位，按论文的k值而非这些系统使用的块预算运行。两个系统均将地标索引置于GPU内存；§5.1的主机内存设置属于我们的方法而非他们的。  

#### 缩略图扫描。  
FFD将K分为2位缩略图和8位残差，通过分数阈值选择，并在单个内核中融合扫描与注意力。我们的2位缩略图基线读取所有128通道的两个平面（每token 288位），并在选择集合上通过精确注意力选择Top-k——比FFD自身的评分更宽松；比特平面存储使其成为我们均匀深度方法的特例。  

#### KV量化。  
KIVI（2位，逐通道键与逐token值）、KVQuant（非均匀，预RoPE，稠密与稀疏）和TurboQuant（随机旋转，Lloyd-Max标量量化器加1位残差）压缩缓存本身；Any-Precision LLM将权重量化为比特平面使前缀构成低精度模型。我们的布局将比特平面思想应用于K缓存，并逐查询逐通道读取前缀。  

#### 卸载检索。  
MagicPIG在CPU上使用局部敏感哈希（LSH）表采样；RetroInfer和RetrievalAttention在主机内存保留向量索引；InfiniGen从主机缓存预取推测性数据。此为扫描字节决定时间的场景，也是我们测量增益的场景。  

## 3 方法  
### 3.1 成本模型  
设N为同时解码的序列数，每序列上下文n token（即驻留Nn token），b为每token每KV头的扫描比特数，H为KV头数，L为层数，G为每KV头查询头数，k_∪≤Gk为组内选择并集后每KV头的不重复获胜行数，R为完整K+V行的字节数。解码步骤读取字节数≈W+NLH(bn/8+k_∪R) （公式1），其中W为每步读取一次的权重。扫描项随驻留token数Nn增长；行项仅随N增长（因每序列每头最多获取k_∪行）。减少b恰好在bn/8为三项中最大时起效——这正是本文针对的长上下文多会话场景。  

### 3.2 比特平面K缓存  
键以逐通道均匀对称码量化至4位，每64-token块一个fp16缩放因子。均匀性使比特平面的前缀成为精确的粗量化器；非均匀码不具备此特性。对块β和通道j，令a_{β,j}=max_{i∈β}|k_{i,j}|为块最大值，s_{β,j}=a_{β,j}/8为单元宽度；编码为c_{i,j}=clip(⌊k_{i,j}/s_{β,j}⌋, -8, 7)+8∈[0,16)，即码8为零，最高有效位为符号位。块β通道j的64个码的第p位（p=0为最高位）打包为64位字P_{β,j,p}（即平面）。平面以通道优先存储，故字P_·