KV Cache 与批处理 — 概念

KV Cache 原理

Transformer 自回归生成时，每个新 token 只依赖于之前所有 token 的 K/V：

关键优势：每个 decode step 只需计算 1 个 token 的 Q/K/V，之前的 K/V 从 cache 读取。

内存布局

KV Cache 在内存中按层组织：

Layer 0: [K_cache(n_kv_max, n_embd), V_cache(n_kv_max, n_embd)]
Layer 1: [K_cache(n_kv_max, n_embd), V_cache(n_kv_max, n_embd)]
...
Layer N: [K_cache(n_kv_max, n_embd), V_cache(n_kv_max, n_embd)]

n_kv_max = 最大 cache 容量（通常等于上下文长度）
n_embd = KV 的 head 维度 × KV head 数
层数使用 hparams.n_layer_all（包含 SWA/MTP 等额外层），区别于 hparams.n_layer（仅标准 Transformer 层）

Batch 处理

llama.cpp 的 batch 允许同时处理多个 token（来自同一或不同序列）：

// include/llama.h —— 真实字段顺序（n_tokens 在前）
struct llama_batch {
    int32_t         n_tokens;   // 总 token 数
    llama_token   * token;      // token IDs（与 embd 二选一）
    float         * embd;       // （可选）直接传入 embedding
    llama_pos     * pos;        // 每个 token 的位置
    int32_t       * n_seq_id;   // 每个 token 所属序列数
    llama_seq_id ** seq_id;     // 每个 token 的序列 ID 列表
    int8_t        * logits;     // 哪些位置需要输出 logits（源码 TODO 拟重命名为 output）
};

Prefill vs Decode

特性	Prefill	Decode
每次 token 数	N（整个 prompt）	1
计算类型	矩阵 × 矩阵	矩阵 × 向量
并行度	高	低
用途	处理输入 prompt	逐个生成 token

Cache 淘汰

当 cache 满时，策略包括：

Rolling — 保留最近的 token，淘汰最旧的
Session — 保存/恢复 cache 状态
Swa — Sliding Window Attention，只缓存窗口内的 token

SWA 优化：保存 checkpoint 时，仅写入未被 mask 的 cell，跳过 padding/masked 位置，减少磁盘 I/O。

设备端状态 (On-Device State)

使用 LLAMA_STATE_SEQ_FLAGS_ON_DEVICE 标志保存序列状态时，每个序列只能保存一个状态。保存新状态会使之前保存的状态失效。这是设备端存储的限制。

MTP 推测解码与 KV Cache

在 MTP (Multi-Token Prediction) 推测解码中，draft token 使用自己的 cache 类型 (ctk)，这会影响 KV Cache 的结构。Draft token 的 KV 需要独立管理，验证后可能被丢弃。

Tensor Parallel 量化 KV Cache

在多 GPU Tensor Parallel 推理中，KV cache 现在支持量化格式：

正确处理跨设备的部分缓冲区视图（partial buffer views）
CUDA 后端在启动时预分配量化工作空间
减少多 GPU 场景下的显存占用

共享 KV Cells（消除拷贝）

当一个 KV cache 需要与另一个 cache 共享 cells（[TAG_KV_CACHE_SHARE_CELLS]）时，原先会把整个 v_cells 向量逐个拷贝过去。正在重构为零拷贝（shared_ptr 所有权共享已就位，部分路径仍标记为 TODO）：

cpp

// 之前：每次共享都拷贝整个向量
std::vector<llama_kv_cells> v_cells;

// 现在：共享所有权 + 引用，避免拷贝
std::shared_ptr<llama_kv_cells_vec> v_cells_impl;
llama_kv_cells_vec & v_cells;          // 指向 v_cells_impl

配套改动：

跟随源 cache 大小 — 共享 cells 时沿用源 cache 的容量（follow the source cache size），不再各自维护独立容量
该重构服务于多 cache 共享同一份 cell 元数据的场景（如推测解码 / 多分支），显著减少内存与拷贝开销

DeepSeek V3.2 DSA KV Cache

DeepSeek V3.2 使用专用 KV cache 类型 llama_kv_cache_dsa：

在标准 KV cache 基础上附加 lightning indexer 缓存
当 n_embd_head_k_full == indexer_head_size 时自动创建 Hadamard 旋转张量

DeepSeek V4 (dsv4) KV Cache

DeepSeek V4（LLM_ARCH_DEEPSEEK4）引入了全新的专用 KV cache 类型 llama_kv_cache_dsv4，实现集中在新增的 src/llama-kv-cache-dsv4.cpp/.h（约 1800 行，是本仓库最大的单文件之一）：

内建 save-load 状态，支持 checkpoint 保存与恢复
集成 Sinkhorn eps 纠正与 rope 处理，保证 dsv4 注意力的数值正确性
支持 pro 模型变体；并调整了交错滑动窗口注意力 cache（llama-kv-cache-iswa.cpp）以配合

稀疏注意力的 indexer 缓存（MSA / DSA / QSA）

使用稀疏注意力的架构在 K/V 之外还需要一条 indexer 缓存，其组织方式本窗口发生重要变化：

MiniMax-M3（MSA） — indexer 不再内嵌在 llama_kv_cache 里（get_k_idx() / cpy_k_idx() / msa_strict_slots 已从基类移除）。新顶层类 llama_kv_cache_msa（src/llama-kv-cache-msa.h，67d5978bb）组合两个 llama_kv_cache 实例——一个装 K/V 张量、一个装 indexer 张量——并保持两者槽位同步；模型图经 llama_kv_cache_msa_context::get_cells() 在位置空间做 MSA block 选择，图侧输入类为 llm_graph_input_attn_kv_msa
DeepSeek V3.2（DSA） — llama_kv_cache_dsa 附加 lightning indexer 缓存；另有新的组合类型 llama_kv_cache_dsa_iswa（DSA 全注意力层 + 普通缓存管 SWA 层，dots3note 使用）
qwen4exp（QSA） — llama_memory_hybrid_idx（src/llama-memory-hybrid-idx.cpp）在 hybrid 注意力/循环记忆之外挂第三条 indexer key cache（indexer 与注意力 cell 1:1 镜像），状态恢复经镜像 cache 直接写回同一批 cell（state_read_sinfo）

Token ID 进驻 KV cell（本窗口）

llama_kv_cell_ext 新增 llama_token tok 字段（925e11799，#27762）——来自多模态 / embedding 输入的 cell 记为 LLAMA_TOKEN_NULL。配套：

seq_pos[s] 从 std::map<pos,int>（引用计数）改为 std::set<pair<pos, cell>>，支持 O(log n) 的「最近 cell」查询（seq_pos_tok_le）
llama_kv_cache::get_prev_tokens(ubatch, n, res) 返回每个 ubatch token 前面的 n 个 token（供 n-gram 输入嵌入使用）
cell_ext（含 token id）纳入状态保存/恢复——状态文件格式变化（LLAMA_STATE_SEQ_VERSION 2 → 3）

KV Cache「家族」

KV cache 现已是一组类型，按架构选择，统一经 llama_memory 接口暴露：

类型	文件	用途
`llama_kv_cache`（基类）	`src/llama-kv-cache.cpp/.h`	通用 KV cache（共享 cells、token 追踪）
`llama_kv_cache_msa`	`src/llama-kv-cache-msa.cpp/.h`	MSA 组合体：K/V + indexer 两个 cache 实例（新）
`llama_kv_cache_dsv4`	`src/llama-kv-cache-dsv4.cpp/.h`	DeepSeek V4（~2250 行，save-load / Sinkhorn / rope，本窗口支持稀疏 FA 与 DFlash2）
`llama_kv_cache_dsa`	`src/llama-kv-cache-dsa.cpp/.h`	DeepSeek Sparse Attention（lightning indexer）
`llama_kv_cache_dsa_iswa`	`src/llama-kv-cache-dsa-iswa.cpp/.h`	DSA + 交错滑窗组合（新）
`llama_kv_cache_iswa`	`src/llama-kv-cache-iswa.cpp/.h`	交错滑动窗口注意力（Interleaved SWA）
`llama_memory_hybrid_idx`	`src/llama-memory-hybrid-idx.cpp/.h`	hybrid 注意力/循环 + 第三条 indexer cache（qwen4exp，新）

注意：不存在 src/llama-kv-cache-unified.cpp——该前缀早在 #15467 即被去除，统一 cache 全部位于 src/llama-kv-cache.cpp/.h。基类构造函数现带 name_tag 参数（一个模型持多个 cache 时保证张量名唯一）。

recurrent 模型的批切分

llama_batch 的 split_equal（等分拆批）现支持 n_keep_tail：为循环 / 混合记忆类型（recurrent / iswa）保留尾部 token，使跨批的循环状态正确衔接（230ea9d21，#25278）。

循环态回滚（recurrent rollback，本窗口）

循环 / 混合架构的推测解码需要「回滚到被拒 draft 之前」的状态快照：

ggml_ssm_scan 新增 K 参数：结果张量在最终态之外多带 K−1 份回滚快照
llama_memory_recurrent 把状态张量加宽为 (1 + n_rs_seq) 组，由 llama_context_params::n_rs_seq 控制
图侧 llm_graph_input_rs 新增 state_restore_* / state_snapshot_* 索引张量；Kimi K3 的 conv1d 每头写 n_rs_seq+1 份卷积状态快照

状态恢复性能（本窗口）

非连续 cell 的状态恢复按连续段批量拷贝（原先约 140 万次微小拷贝，CUDA 上 4 万 token 快照需 25–63 s，2d8d612e4）。

Context 位移与设备校验

main_gpu 校验放宽 — 当没有任何可用设备时跳过 main_gpu 校验，避免纯 CPU 或无 GPU 环境下的误报
n_discard 修复 — context shifting（上下文压缩）时，非绑定（non-bound）的 n_discard 值得到正确处理，避免丢弃数量错误导致 cache 状态不一致

KV Cache 与批处理 — 概念 ​

KV Cache 原理 ​

内存布局 ​

Batch 处理 ​

Prefill vs Decode ​

Cache 淘汰 ​

设备端状态 (On-Device State) ​

MTP 推测解码与 KV Cache ​

Tensor Parallel 量化 KV Cache ​

共享 KV Cells（消除拷贝） ​

DeepSeek V3.2 DSA KV Cache ​

DeepSeek V4 (dsv4) KV Cache ​

稀疏注意力的 indexer 缓存（MSA / DSA / QSA） ​

Token ID 进驻 KV cell（本窗口） ​

KV Cache「家族」 ​

recurrent 模型的批切分 ​

循环态回滚（recurrent rollback，本窗口） ​

状态恢复性能（本窗口） ​

Context 位移与设备校验 ​

相关概念 ​