KV Cache 与 Prefill/Decode 推理路径

本课假设你已经知道 self-attention 中 Q、K、V 的来源，并理解 causal mask 禁止当前位置读取未来 token。

它回答一个很实用的问题：对话生成到一半后，如果用户回头修改提示词，服务端需要把整段 KV Cache 全部丢掉吗？

答案不是简单的“全丢”或“全留”，而是沿修改位置形成一条精确边界。

本课先在数学上推导这条边界，后续课程再把它连接到公共前缀复用、Radix Tree 与缓存替换策略。

设原提示词 token 序列为

用户只把第 $m$ 个 token 改成 $x'_m$，其余 token ID 不变。

直观结论是：

“后面的 token 自身没有改”不等于“后面的表示不变”。

因为后方 token 会读取第 $m$ 个位置，而那个位置的内容已经改变。

一层中的 Q、K、V 投影可写成

矩阵乘法对 token 行是独立的：输出第 $i$ 行只依赖输入第 $i$ 行和共享权重。

因此在第一层输入处，若只有 $x_m$ 改变，则

只有 $q_m,k_m,v_m$ 会直接变化。

这里必须纠正字幕中的一个易混点：KV Cache 保存的是 K 与 V，不保存 Q。

所以第一层缓存的直接变化项是 $k_m,v_m$，不是所谓“Q3 的 KV Cache”。

因果注意力分数为

而 $j>i$ 的位置被 mask 成不可见。

第 $m$ 个 query 变化，会改变第 $m$ 行可见区域。

第 $m$ 个 key 变化，会改变所有允许读取 $m$ 的查询行。

在 causal mask 下，只有 $i\ge m$ 的查询能够读取第 $m$ 个 key。

因此：

只要一行中某个合法分数改变，按行 Softmax 的归一化分母就会改变。

于是该行所有注意力权重都可能重新分配，而不只是第 $m$ 列的权重变化。

注意力输出为

对 $i<m$，合法的 $a_{ij}$ 与 $v_j$ 都没变，所以 $o_i$ 不变。

对 $i\ge m$，权重或 $v_m$ 至少有一项变化，所以输出通常会变化。

这正是“前缀稳定、后缀失效”的数学来源。

第一层输入 embedding 中只有位置 $m$ 改变，所以第一层只有 $K_m,V_m$ 需要直接更新。

但第一层输出从位置 $m$ 开始已经整体改变。

这些输出经过输出投影、残差连接与 FFN 后，作为第二层输入。

于是从第二层开始，所有 $i\ge m$ 的输入行都可能不同。

相应地，更深层的

都要重新计算。

这给出工程上的失效策略：保留所有层在 $m$ 之前的 KV，截断从 $m$ 开始的后缀，再对新后缀做增量 prefill。

若取消 causal mask，每个位置都能读取位置 $m$。

那么 $k_m$ 或 $v_m$ 的变化会进入所有查询行，包括 $m$ 之前的位置。

第一层输出的所有位置都可能改变；进入第二层后，所有位置的 K、V 也都可能改变。

因此对标准 BERT 式全序列编码而言，单点编辑通常要求整段重算。

这不是因为矩阵乘法突然失去逐行独立性，而是因为双向注意力把所有位置连在了一起。

上一课已经推导：decoder-only 模型修改第 $m$ 个 token 后，第 $m$ 个位置之前的缓存仍然稳定，而后缀需要重算。

本课把这个结论上升为一个更一般的问题：KV Cache 为什么能够存在？

常见回答是“GPT 自回归、BERT 不是自回归”。

这句话方向没错，但没有指出真正的数学条件。

决定性条件是：相同公共前缀在两次前向计算中，必须产生相同的逐层 K、V。

GPT 式 decoder-only 模型使用 causal mask，每个位置只能读取自己和过去。

BERT 式 encoder-only 模型使用双向 self-attention，每个位置都能读取整段输入。

因此生成新 token 时，GPT 既不需要也不允许让历史位置读取未来 token。

已经算好的历史 K、V 可以留在缓存中，新 token 只需追加自己的 K、V。

BERT 的典型任务则是对一段完整输入做一次编码，没有逐 token 生成循环。

但“任务形式不同”仍不是最深层原因；真正的区别要看输入变化是否会反向污染公共前缀。

假设第 $m$ 个输入向量改变。

线性投影仍然逐行独立：

第一步只有 $q_m,k_m,v_m$ 直接变化。

注意力分数矩阵中，$q_m$ 影响第 $m$ 行，$k_m$ 影响第 $m$ 列。

到这里，GPT 和 BERT 的局部代数完全相同。

分歧发生在 mask：哪些查询行实际包含第 $m$ 列？

对 causal attention，第 $i$ 行只能访问 $j\le i$ 的 key。

如果 $i<m$，这一行根本看不到第 $m$ 个 key。

因此公共前缀位置的注意力分数、Softmax 权重和加权结果都不变。

可以用依赖关系表述为

而不是依赖完整序列 $x_{1:T}$。

只要两个请求的前 $r$ 个 token 及相关位置条件相同，就有

于是由这些 hidden state 投影得到的 $K_i^{(\ell)},V_i^{(\ell)}$ 也相同。

这就是前缀缓存可以跨请求复用的根基。

BERT 没有 causal mask，第 $m$ 个 key 对所有 query 行都可见。

当 $k_m$ 改变时，每一行至少有一个分数可能改变。

Softmax 按行归一化，因此每一行的权重分布都可能变化。

再考虑 $v_m$ 也变化，所有位置的加权和都可能改变。

第一层输出整体变化后，第二层的 Q、K、V 也整体变化。

因此对标准 BERT 全序列编码，哪怕只修改中间一个 token 或在末尾追加一个 token，旧序列的上下文化表示也不能假定仍然有效。

这说明“BERT 没有 KV Cache”的准确语境是：它通常没有像自回归 decode 那样可逐步追加并长期复用的 self-attention KV Cache。

课程最后把两条输入画在一起，例如

与

它们的公共前缀是 a a b。

若模型满足因果依赖，则公共前缀在每层得到相同 K、V，后续分支可以从同一缓存节点继续。

因此更一般的判据是：

文字看起来相同还不够。

至少还要保证：

这些属于编者补充的工程边界，用来避免把“公共字符串”误当成“公共缓存”。

课程讨论的是 self-attention 的增量 KV Cache。

在其他系统中仍可能缓存 tokenizer 结果、embedding、完整句向量、检索结果，或 encoder-decoder cross-attention 所需的 encoder K/V。

这些缓存的复用条件和生命周期与自回归前缀 KV Cache 不同。

所以应说“标准 BERT 编码过程缺少稳定的增量 self-attention 前缀缓存”，而不是“任何使用 BERT 的系统都不能缓存任何东西”。

前两课已经得到两个结论：因果模型的公共前缀能够产生相同 KV；修改点之前的前缀可以保留，之后的缓存需要重算。

当服务端同时维护大量请求时，可复用前缀会越来越多。

但 GPU 显存是有限的，缓存不可能无限增长。

所以问题从“能不能复用”进一步变成“哪些值得继续留在显存里”。

课程以 SGLang 的前缀缓存场景为例，用 LRU、LFU 等策略说明这一选择。

具体实现和默认策略可能随版本变化，本课重点是替换问题的结构，而不是绑定某一版接口。

LRU 是 Least Recently Used，即最近最少使用。

可以为缓存块维护新旧度：访问一次就把它标记得更“新”，长期未访问的块会变“旧”。

当容量不足必须腾出空间时，LRU 优先驱逐最近最久没有被访问的对象。

它背后的经验假设是时间局部性：刚被访问的内容，短期内更可能再次被访问。

LFU 则关注访问频率，倾向保留长期高频对象。

两者回答的都是同一个资源分配问题，只是对“未来价值”的估计方式不同。

一句公共前缀不是只对应一个 K 和一个 V。

对每个 token、每个 Transformer 层、每个 KV head，都有相应的张量切片。

可用一个简化形状表示每层缓存：

若共有 $L$ 层，K 与 V 合计元素数近似为

因此一个被共享很多次的长前缀可能很有复用价值，同时也会占据可观显存。

替换策略需要在“节省未来计算”和“释放当前内存”之间做权衡。

假设两个用户的请求分别以“你好”开头，随后走向不同后缀。

只要前缀 token、位置和模型配置兼容，公共部分的逐层 KV 可以只生成一次。

这里的共享不意味着用户的完整会话数据互相可见。

共享的是数值相同的前缀计算结果；权限隔离、请求归属与后续分支仍由服务系统管理。

工程上还必须遵守隐私与租户隔离策略，不能只凭数值可复用就跨越安全边界。

课程强调的是计算图层面的可复用性。

多个 SubAgent 可能都需要同一段系统提示、工具说明或背景知识。

如果每个 Agent 都从头 prefill 这段背景，会重复生成完全相同的前缀 KV。

更合理的上下文布局是：

这种布局既减少重复 prefill，也让公共前缀成为高价值缓存对象。

同一用户先发送一句提示词，随后回头修改其中一个 token。

从推理引擎的 token 路径看，这与两个请求共享一段前缀再走向不同后缀没有本质差别。

修改点之前的缓存保持有效。

修改点及其后方的缓存需要重新生成。

原 AI 字幕在这一段出现“后面的不需要重新生成”的否定错位；完整上下文和画面明确表达的是“后面的必须重新生成”。

这也是本课唯一需要显式说明的字幕纠错。

当显存装不下所有缓存时，系统面对的不是抽象的单个文本，而是带有共享关系的前缀节点和分支。

若一段背景知识刚被多个请求频繁命中，把它驱逐会让后续请求重复付出很大的 prefill 成本。

若另一条长分支长期没有访问，保留它的机会成本可能更高。

因此可以用 LRU、LFU 或成本感知策略给候选对象排序。

在树结构中还要考虑父子关系：删除父前缀可能影响挂在其下的多个可复用分支。

具体驱逐粒度取决于实现，可能是 token 块、页、节点或一组关联块；课程板书表达的是通用决策逻辑。

LRU 只依据最近访问时间，无法直接感知：

因此 LRU 是容易理解、维护成本低的基线，并不保证所有工作负载下最优。

LFU、成本加权、优先级或混合策略可以补充它，但也会增加元数据和调度复杂度。

上一课已经看到，跨任务是公共前缀复用的典型来源。

本课把镜头收窄到多 Agent：父 Agent 给多个 SubAgent 相同的背景知识，再分配不同任务时，为什么不必把公共部分重复 prefill 多次？

讨论假设服务端具备跨请求前缀缓存能力，并能用类似 Radix Tree 的结构维护 token 路径。

若后端没有开启前缀缓存、请求配置不兼容，或安全策略禁止跨请求共享，则这里只能作为计算图上的可能性，不能自动变成实际命中。

给每个 SubAgent 独立上下文，目的是让它专注自己的任务，避免其他分支的中间过程造成干扰。

但独立不意味着所有内容都必须重复。

可以把上下文拆成两部分：

SharedPrefix 包含所有子任务都必须知道的系统约束、工具说明或背景材料。

TaskSuffix_i 只包含第 $i$ 个 SubAgent 的角色、目标和专属输入。

这样既保持分支干净，又为公共前缀制造复用机会。

课程以 SGLang 的 Radix Tree 思路说明：多个请求的 token 序列可以共享树上的前缀路径。

若两个请求具有相同的前 $r$ 个 token，它们可共同指向前缀节点，再从第 $r+1$ 个 token 开始分叉。

每个共享节点关联相应的 KV Cache 块或映射。

课程把推理服务称为“无状态”，需要加上引号理解。

这里不是说服务端真的不维护任何状态；恰恰相反，前缀缓存、请求队列和块表都属于状态。

更准确的意思是：KV 数值主要由 token、位置与模型条件决定，而不是由“张三还是李四”这个身份标签决定。

设用户 A 发送：

用户 B 发送：

两条序列在某个 token 处分叉。

从缓存树视角看，这与用户 A 先发送第一句、随后回头修改成第二句具有相同结构：共同走过一段 token 路径，再进入不同后缀。

因此缓存命中不应仅按会话 ID 判断，而要检查可复用前缀本身。

当然，计算上可共享不等于策略上允许共享。

多租户系统仍需执行权限、隐私、加密域和侧信道防护等安全规则。

假设父 Agent 要启动两个 SubAgent：

两者都需要同一份项目背景和输出规范。

适合缓存的排列是：

如果把每个 SubAgent 的不同角色描述放在最前面，token 路径会过早分叉，后面即使出现相同背景也难以作为“前缀”直接命中。

所以前缀缓存优化不仅是推理引擎问题，也会反过来影响上下文编排顺序。

对同一个模型和完全相同的前缀，第 $\ell$ 层前缀 hidden state 相同，因此

若为两个 SubAgent 各存一份相同缓存，只会重复占用显存和 prefill 计算。

共享后，两条请求都从公共前缀末端继续，只为各自不同后缀计算新的 K、V。

收益可粗略理解为：公共前缀越长、复用次数越多，避免的重复 prefill 越多。

但实际收益还受缓存命中、调度、块粒度、数据搬运和并发批处理影响。

至少需要检查：

“文本看起来一样”并不是充分条件，因为 tokenizer 或模板差异可能改变 token 序列。

“同一个父 Agent 创建”也不是必要条件，因为不同请求只要满足以上条件，同样可能命中相同前缀。

共享公共前缀不意味着多个 SubAgent 共享完整对话历史。

每个分支的任务后缀、工具结果和中间推理应保持独立，除非工作流明确需要同步。

因此比较稳妥的设计是“共享只读背景，隔离动态后缀”。

这既减少重复计算，也降低分支间信息污染。

前面的课程已经说明 KV Cache 如何复用历史 K、V。

本课进一步看这种复用如何改变计算形态。

prefill 一次处理提示词中的多个 token；单请求 decode 每轮只新增一个 token。

同一个权重矩阵面对不同的 token 维长度，会从“大矩阵乘大矩阵”退化成“单行乘权重矩阵”。

这就是 GEMM 与 GEMV 差异的来源，而不是模型在 decode 时换了一套参数。

设隐藏维度为 $d$，提示词长度为 $T$，线性层权重为

prefill 输入为

所以计算

是矩阵乘矩阵，即 GEMM。

单请求 decode 每轮只有一个新 token：

于是

可视作向量乘矩阵，即 GEMV，或实现层面的 $M=1$ 瘦 GEMM。

课程把两者简称为 GEMM 与 GEMV，是为了突出 token 维从 $T$ 收缩为 1。

整段提示词的 hidden states 已经同时给出，因此可一次计算

三者都保留 $T$ 行，每行对应一个 token。

不同 token 的投影互相独立，GPU 可以用高并行度的矩阵核处理。

课程示例省略 batch、head 和多层维度，目的是让 token 维最醒目。

真实实现通常会把 batch、token、head 等维度重排或融合，但不会改变“同时处理多行”的本质。

得到 Q、K 后，注意力分数为

加上缩放与 causal mask，再按行做 Softmax：

随后

也是矩阵乘矩阵。

FlashAttention 会分块并在线维护 Softmax 统计量，但最终数学结果仍对应这两次矩阵收缩。

注意力输出还会经过输出投影、残差与 FFN。

FFN 的上投影和下投影同样对 $T$ 行一起执行。

一层完成后，整段输出再作为下一层的整段输入。

所以 prefill 的并行性是：同一层内的 token 维可并行，层与层仍有前后依赖。

当最后一层得到 $T$ 个位置的 hidden state 时，prefill 完成，并为每一层留下提示词的 K、V。

teacher forcing 训练时，多个位置都可以投影到词表并计算下一 token 损失。

例如第 $i$ 个位置预测第 $i+1$ 个 token。

推理 prefill 结束时，生成下一 token 只需要最后一个有效位置的 logits。

前面位置的 logits 即使能够算出，也不需要用于这一步采样。

选出新 token 后，把它的 token ID 做 embedding，得到下一轮 decode 的单行输入。

这一步把计算从 $T$ 行切换为 1 行。

新 token 的 hidden state 分别乘 $W_Q,W_K,W_V$，得到

$k_t,v_t$ 追加到当前层 KV Cache。

新 query 与历史 key 做

再用权重读取

这些都是一行参与的矩阵运算，单请求视角下具有 GEMV 或瘦 GEMM 特征。

新 hidden state 逐层推进，直到输出下一 token，然后循环。

历史位置的 query 已经在它们生成时完成了查询。

未来 token 出现后，因果模型也不会回头更新历史位置的输出。

因此下一轮只需要新 $q_t$ 去读取全部历史 K、V。

旧 Q 没有后续用途，通常不会进入 KV Cache。

这同时解释了两个常见问题：

prefill 的矩阵较大，权重加载后可参与大量乘加，算术强度通常较高，因此常表现为 compute-bound。

单请求 decode 每步只有一行输入，却仍要读取大量模型权重和越来越长的 KV Cache，数据搬运相对乘加更多，因此常表现为 memory-bound。

但这不是只看阶段名称就能下的绝对结论。

以下因素会改变算术强度：

当多个请求被批成多行，decode 的线性层也可再次使用 GEMM。

因此更准确的表述是：单序列、单 token decode 的 $M$ 很小，常接近 GEMV，并更容易受内存带宽限制。

建议先理解 causal self-attention 中 query、key、value 的来源，并知道 Transformer block 必须逐层执行。

本课位于“KV Cache 的生命周期与内存管理”单元。它回答“缓存怎么长”，后续还要回答“缓存占多少显存”“如何分页”“何时复用或淘汰”。

课程用一个三维堆叠图表示 layer、token 与 K/V。

图中的“堆一面”“加一条”是为了说明计算依赖，并不要求显存中的地址真的连续。

PagedAttention 会把逻辑连续的 token 映射到若干物理块；RadixAttention 还会围绕前缀复用组织缓存。

所以读图时应分开两件事：

只要映射表正确，物理不连续不影响注意力访问。

假设 prompt 有 $T$ 个 token。

在第一层，所有位置的输入 embedding 已知，因此 Q/K/V 投影可以对 $T$ 个位置并行计算。

虽然 causal attention 会屏蔽未来位置，但这个 mask 不妨碍矩阵形式的一次并行计算。

得到第一层全部 token 的 K/V 后，才能生成第一层输出并送入第二层。

因此课程把每层整段 token 的 K/V 画成一个“面”：

这里容易忽略一个细节：同一个 token 在不同层虽然都可标成 $K_t,V_t$，数值并不相同。

原因是每层输入 hidden state 和投影矩阵都不同：

所以缓存必须按层保存，不能把第一层的 K/V 直接给第二层使用。

课程用“训练约等于 prefill”帮助理解并行结构。

相似之处是：teacher forcing 已经给出完整目标序列，因此训练时可以在 causal mask 下同时计算多个位置的预测。

训练不需要先采样第一个预测 token，再把它喂回去才能算第二个位置。

但这个类比有三个边界：

所以更准确的说法是：训练与 prefill 都能沿 token 维并行；不能据此认为二者的内存生命周期完全相同。

prefill 完成后，模型已有 prompt 的缓存。

第一个 decode 轮次只拿最新 token 的 hidden state 进入第一层，计算该 token 在第一层的 $K_{T+1}^{(1)},V_{T+1}^{(1)}$。

它的 query 会读取该层已有的所有 key/value：

第一层算完后，新的 hidden state 才能进入第二层；因此同一个新 token 仍要逐层向前传播。

当它穿过全部 $L$ 层后，每一层都新增了一个时间位置的 K/V。

课程把这个过程画成逐层增加的“条”。从整个模型看，一轮 decode 最终会在所有层各追加一个 token 位置；从执行时序看，这些追加随新 token 逐层发生。

最后一层得到新位置的 hidden state $h_{T+1}^{(L)}$ 后，模型把它投影到词表：

经过 softmax 与采样/选取，模型得到真实的下一个 token。

这个 token 再作为下一轮输入，于是形成循环：

decode 不能像 prefill 那样一次并行算出未来多个 token，根本原因不是 K/V 的存储格式，而是未来 token 尚未生成。

若每层缓存形状近似为

那么 K 与 V 合计的元素数约为

若每个元素占 $s$ 字节，显存量约为

prefill 会把 $T$ 从 0 一次推进到 prompt 长度；之后每轮 decode 让 $T$ 增加 1。

这说明“面”和“条”只是视觉比喻，真正决定显存斜率的是层数、KV head 数、head 维度、批量和当前上下文长度。

上一课已经从计算形态看过 prefill 与 decode。

本课把注意力内部的 head 维单独展开。

最容易混淆的一句话是“多个 query 共享 K、V”。

这里的“多个”指多个 query head，不是多个 token。

每个 token 仍有自己的 K、V；只是同一 token 在 K/V 侧使用的 head 数少于 Q 侧。

设序列长度为 $T$，query head 数为 $H_q$，KV head 数为 $H_{kv}$，每头维度为 $D_h$。

投影和分头后，可以把张量写成

token 轴长度仍是 $T$。

GQA 缩小的是 $H_{kv}$，不是 $T$。

因此“共享 token”这个说法会把两个完全不同的轴混在一起。

输入矩阵中的每一行对应一个 token。

它们分别经过 $W_Q$、$W_K$、$W_V$：

同一 token 会得到自己的 Q、K、V 表示。

不同 token 不会因为使用 GQA 就共用同一条 K 或 V。

变化只发生在投影输出的宽度与分头方式上。

看一个最小例子：

分组比例为

也就是每两个 query head 共用一个 KV head。

一种常见映射是

这里“共用”只表示选择同一个 KV head。

每个 query head 的 query 向量仍不同。

为了让计算图的 head 数对齐，可以把两个 KV head 想象成逻辑扩展到四份。

但高效实现不会为了对齐就把 KV Cache 真复制一遍。

kernel 可以通过索引计算 KV head：

也可以用 view、expand 或专用 grouped-query attention kernel 表达同一关系。

所以“图上画出四份”不等于“显存里存了四份”。

对第 $h_q$ 个 query head，仍然独立计算

然后按行 Softmax：

再读取对应的 V：

即使两个 query head 读取同一 K/V，它们的 Q 不同，得到的分数和权重通常也不同。

示例中四个 query head 会产生四个输出 head。

这些输出最后沿 head 维拼接，再经过输出投影。

因此 GQA 压缩的是 K/V 侧，并没有把最终输出 head 数也压成两个。

忽略 batch、层和字节数时，KV Cache 元素量与下式成正比：

其中 2 代表 K 和 V 两份。

若从 MHA 的 $H_{kv}=H_q=32$ 改为 GQA 的 $H_{kv}=8$，KV Cache 理论元素量降为原来的四分之一。

token 数 $T$ 没有减少。

省下的是每个 token、每一层需要保存的 KV head 数。

GQA 在注意力表达能力、KV Cache 容量和读取带宽之间取折中。

因果注意力要求位置 $i$ 只能读取位置 $j\le i$。

教科书常画一个完整的 $T\times T$ 分数矩阵，再把上三角设为负无穷。

这张图用于表达数学约束，却不代表高效 kernel 真会把整个矩阵算出来并存到显存。

本课分别从 prefill 和 decode 看“跳过”在物理执行层意味着什么。

注意力 logits 为

其中

Softmax 后，未来位置的权重为 0。

关键问题不是“最终权重是否为 0”，而是“能否提前知道整片区域无效，从而连乘法和数据搬运都不做”。

prefill 同时有 $T$ 行 Q 与 $T$ 行 K。

第 $i$ 行输出为

$j>i$ 的 V 不应贡献给 $o_i$。

若先算完整 $QK^{\mathsf T}$ 再掩码，数学正确，但浪费了上三角乘加与中间存储。

FlashAttention 不把完整分数矩阵写回 HBM。

它把 Q、K、V 划分为较小的 tile，装入 GPU 片上存储，再在线维护 Softmax 所需统计量。

对于一个 Q tile，kernel 能根据 tile 的行列范围判断某个 K/V tile 是否完全位于未来区域。

若整个 tile 都满足 $j>i$，就可以：

因此“跳过”首先是一种块级调度与数据搬运优化。

设 Q tile 覆盖行 $[r_0,r_1)$，K tile 覆盖列 $[c_0,c_1)$。

若

整个 K tile 都在这些 query 的未来，可以整块跳过。

但穿过主对角线的 tile 同时包含合法元素和未来元素。

这类 tile 必须先计算合法部分，并在块内对未来元素施加 causal mask。

所以正确表述是：

对每个 query 行，Softmax 可以分块更新最大值与归一化和。

若当前块 logits 为 $s^{(b)}$，维护运行最大值 $m$ 与指数和 $\ell$。

新块到来时先更新

再缩放旧统计量并加入新块贡献。

这使得 kernel 可以边读 tile、边更新输出，不需要保存完整 $T\times T$ 的 A。

因果 tile 剪枝与在线 Softmax 共同减少计算和显存流量。

在第 $t$ 步 decode，当前只有一个新 query：

KV Cache 中只有已经生成的

于是分数只有一行：

未来的 $k_{t+1},k_{t+2},\ldots$ 尚未生成，也没有存入缓存。

因此 decode 不是“先构造一行含未来列的数据再掩码”，而是根本没有这些列。

单 token decode 对所有已存在 K 都是因果合法的。

但若一次验证多个候选 token，或采用 speculative decoding 的多 token chunk，chunk 内部仍会重新出现因果边界。

这时执行形态更像一小块增量 prefill，而不是纯单行 decode。

所以“decode 无需 causal mask”应限定在每步单 token、未来 K 不存在的常规情形。

把所有步骤画在一起，可以得到一个下三角矩阵。

但真实执行是：

这张逻辑图用于推理依赖关系，不应被误当作实际内存布局。

KV Cache 会随请求逐 token 增长。

若每条请求都要求一整段连续显存，并提前为最大长度预留，服务端很快会遇到碎片与浪费。

PagedAttention 借用了虚拟内存分页的核心思想：

逻辑序列保持连续，物理显存允许离散，再用映射表把两者连接起来。

服务端通常不知道一条请求最后会生成多少 token。

若按最大长度一次性申请连续 KV 空间，请求提前遇到 EOS 时，后半段预留永远不会使用。

设最大生成长度为 $T_{max}$，实际生成长度为 $T$，每 token 的逐层 KV 大小为 $C$。

单请求预留浪费可粗略写成

并发请求越多，这种“为了可能的未来而占住显存”的成本越大。

内部碎片指已经分配给某个请求的连续区域内部，有一部分没有被实际 token 使用。

外部碎片指多个已分配区域之间出现空洞；空闲总量可能足够，却找不到一段足够长的连续区间。

例如三个空洞分别有 2、3、4 个单位，总空闲是 9。

若新请求必须连续申请 6 个单位，仍会失败。

问题不在总量不足，而在连续性约束。

PagedAttention 将一条请求的 token 序列按固定 token 数分块。

若 block size 为 $B_s$，逻辑 token $t$ 所在逻辑块为

块内偏移为

逻辑块 0、1、2 仍按 token 顺序排列。

这层连续性属于请求视角，不要求物理地址也连续。

显存池被划分成同样大小的物理块。

逻辑块 0 可以落在物理块 3，逻辑块 1 可以落在物理块 11。

只要运行时知道映射关系，注意力读取时仍能按照逻辑 token 顺序访问 K、V。

这与“把分散数据重新复制成连续大数组”不同。

分页的价值恰恰是避免这种大规模整理与搬迁。

每个请求维护自己的 block table。

它记录

访问 token $t$ 时：

因此 block table 是顺序语义与离散显存之间的桥梁。

当前物理块未写满时，新 token 继续写入该块。

写满后，分配器从全局空闲池取任意一个物理块，并把新映射追加到 block table。

不需要提前申请完整最大长度，也不需要新块紧挨着旧块。

这把分配粒度从“整条可能很长的序列”缩小为“一个固定块”。

分页带来三项主要收益：

它没有减少模型数学上需要保存的有效 KV 元素。

它减少的是分配策略造成的额外浪费。

若 block size 为 $B_s$，请求长度不是 $B_s$ 的整数倍，最后一个块会有空槽。

对单条活跃序列，尾部最多浪费 $B_s-1$ 个 token 槽位。

因此 block size 有权衡：

PagedAttention 是把不可控的大段浪费约束成有限的块尾浪费，不是让碎片严格归零。

注意力公式仍是

分页改变 K、V 的物理寻址方式，不改变逻辑 token 顺序或注意力结果。

高效 kernel 会按 block table 收集需要的物理块并完成计算。

所以 PagedAttention 更接近“KV Cache 内存管理与配套 kernel”，而不是一种新的注意力概率定义。

前面的课程已经说明 decode 为什么缓存 K、V，以及 GQA 如何减少 KV head 数。

现在把这些 shape 乘起来，就能估算服务端最重要的动态显存之一。

先记结论：

真正重要的不是背公式，而是能把每一项在张量中找到。

单层中，每个 token 都有 K 和 V。

先只看 K，它的典型形状可以写成

长度是 token 数 $T$，另外两个方向组成每个 token 的 KV 宽度。

再复制一份给 V，于是出现最前面的系数 2。

每一层都有自己的 K、V，不能跨层混用。

所以乘 Transformer 层数 $L$。

并发 batch 中每条请求也有独立缓存，所以再乘请求数 $B$。

若所有请求都补齐到同一长度 $T$，元素总数为

张量元素必须乘每个元素占用的字节 $s$：

常见取值包括：

实际系统还可能有 scale、元数据、对齐和分配器开销；基础公式只计算 KV 主体。

MHA 中 $H_{kv}=H_q$，所以有些旧公式直接写 attention head 数。

但 GQA 与 MQA 中 K/V head 更少。

正确公式应使用模型配置里的 num_key_value_heads。

若误用 num_attention_heads，会把 GQA/MQA 的缓存显著高估。

Llama2-7B 使用 MHA，$H_{kv}=H_q=32$，所以示例中写 32 没有冲突。

BF16 每个元素占 16 bit，也就是 2 byte。

注意公式开头和结尾的两个“2”来源不同：

漏掉任何一个，结果都会差一倍。

视频示例取：

代入得到

把每项写成 2 的幂：

视频板书写 128 GB，是工程口语中的常见写法。

严格区分单位时：

所以该二进制计算结果应称 128 GiB，约等于 137.44 GB。

连续 batching 中，各请求长度可能分别为 $T_1,T_2,\ldots,T_B$。

有效 KV 主体更准确地写成

若系统把请求 padding 到统一 $T$，才直接使用 $BT$。

PagedAttention 会按块分配，实际占用还需把每条长度向上取整到 block size，并加入 block table 等元数据。

单条请求每新增一个 token，会在每层新增一份 K 和一份 V：

这条增量公式适合估算 decode 中缓存增长速度。

若 batch 中同时有 $B$ 条请求各生成一个 token，则乘 $B$。

它也解释了为什么长上下文、深层数和大 KV head 数会迅速推高显存。

单轮生成的流程很熟悉：提示词先做 prefill，随后逐 token decode。

多轮对话多了一步：模型回复结束后，用户又提交一段包含多个 token 的新 prompt。

这段新 prompt 不应让旧上下文从头重算。

系统会保留旧 KV Cache，只对新增 prompt 做 incremental prefill，再继续 decode。

设首轮用户 prompt 有 $T_0$ 个 token，模型回复生成 $D_0$ 个 token，下一轮用户 prompt 有 $T_1$ 个 token。

时间顺序是：

“增量”表示旧前缀不重算，只处理新来的 $T_1$ 个 token。

首轮 prefill 会为每层一次产生 $T_0$ 行 K 和 V。

常规单 token decode 每步只产生 1 行新 K 和 V。

下一轮 incremental prefill 则一次产生 $T_1$ 行 K 和 V。

所以三阶段使用同一组 Transformer 权重，主要差别是新 token 块的行数。

对首轮输入 $X_{1:T_0}$，每层计算

注意力使用 causal mask，完成所有提示词位置的隐藏状态。

该层结束时，把 $K_{old},V_{old}$ 保存到缓存。

$Q_{old}$ 不保存，因为这些 query 已经完成了自己的读取任务。

第一个回复 token 到来时，当前层只计算

新 query 读取旧缓存和当前新 key：

随后把 $k_t,v_t$ 追加到缓存尾部。

下一步 decode 会看到更长一行的 K/V。

这种追加在每一层分别发生。

设模型已完成回复，此时旧缓存长度为

新用户 prompt 有 $T_1$ 行 hidden states。

增量 prefill 为这些新行计算

逻辑缓存直接扩展为

这里的分号表示沿 token 轴拼接。

若使用 PagedAttention，物理块不必连续；“拼接”仍是逻辑顺序。

新 prompt 中第 $i$ 个 token 的 query 可以读取：

若新块长度为 $T_1$，其注意力分数形状为

左侧旧前缀矩形区域全部可见，右侧新块区域只有下三角可见。

同一批新 prompt token 是并行投影出来的。

若不在新块内部加 causal mask，较早 token 会读取较晚 token，造成未来信息泄漏。

掩码可以写成

具体索引是否从 0 开始会改变边界写法，但语义不变：新 token 只能看旧前缀和新块中不晚于自己的位置。

decode 时 $T_1=1$。

缓存中只有过去 K 和当前 K，未来 K 尚不存在。

因此唯一一行 query 的所有现存列都合法，因果边界由“只存已生成 token”隐式保证。

当一次处理多个 token 时，未来列重新出现在同一计算块里，所以要显式掩码。

把多轮过程的所有 query 行按时间堆起来，会看到阶梯形有效区域。

这张阶梯图表达逻辑依赖，不代表完整注意力矩阵会被长期存入显存。

真实聊天系统会把 system、user、assistant 分隔符都编码成 token。

若下一轮重新序列化后的旧前缀与缓存创建时不完全相同，不能盲目追加。

可靠实现必须确认 token 级前缀匹配，再从匹配边界开始 incremental prefill。

这也是 prefix cache、chat template 与 KV Cache 正确性之间的连接点。

前面的课程已经说明：只有完全相同的 token 前缀才能安全复用逐层 KV。

PagedAttention 又说明：逻辑连续的缓存不必放在连续物理显存中。

SGLang 的可视化把这两个视角叠到一起：

假设两条请求都以同一个系统提示词开始：

系统提示词 token 完全相同，因此两条请求先沿同一条主干前进。

遇到不同用户输入后，token 序列分叉。

树上的公共路径就是可复用前缀，分支是各请求独有的后缀。

因果 Transformer 中，位置 $i$ 的逐层表示只依赖 token 0 到 $i$。

若两条请求的前 $m$ 个 token 完全相同，并且模型、位置编码与推理配置一致，那么公共前缀上对应的逐层 K/V 相同。

第二条请求无需为这段系统提示词重新 prefill。

它可以引用已经存在的 KV Cache，再从自己的第一个新 token 开始增量计算。

这同时减少重复计算与重复缓存。

前缀复用依据 token ID 序列的一致性，不是句子意思相近。

下面这些变化都可能让 token 序列不同：

所以缓存命中必须做精确前缀匹配，不能用语义相似度替代。

板书把 token 下方画成一串小 KV 块。

这不是说一个 token 只有一对 K/V 向量。

对包含 $L$ 层的模型，每个 token 在每一层都有 K 和 V：

若使用 GQA，每层的 K/V 还包含 $H_{kv}$ 个 head。

因此树上的“一个 token 节点”代表一组逐层缓存记录。

设两条序列分别为

和

且 $a_m\ne b_m$。

位置 $0$ 到 $m-1$ 可以共享。

从位置 $m$ 开始，两条请求的 hidden state 不同，后续逐层 K/V 也通常不同。

因此共享边界是最长公共 token 前缀的末端。

多个活跃请求可以同时引用同一公共前缀。

系统需要记录哪些缓存块仍被请求引用。

只有当引用该前缀的请求都结束或缓存策略决定淘汰时，公共块才可回收到空闲池。

这解释了为什么前缀缓存不只是“查到就用”，还涉及生命周期、引用和淘汰策略。

前缀树回答：

分页映射回答：

同一条逻辑路径上的相邻 token 不必位于相邻显存地址。

运行时通过块表或内存池元数据找到对应物理位置。

不要把树边误解成物理指针必须连续。

视频用 16 token 一块来说明分页。

若 block size 为 $B_s=16$，长度 18 的前缀需要

个物理块。

第二块只用 2 个 token 槽位，剩余 14 个槽位暂时空闲。

具体系统和配置的 block/page size 可能不同，16 不是 SGLang 在所有场景中的固定常数。

固定块让物理分配和复用更容易，但最后一个块可能未填满。

若前缀在块中间分叉，两个分支是否能共享部分块，取决于实现的页粒度、缓存索引和 copy-on-write 策略。

因此有两个不同粒度：

不能只看树形图就假设显存会按 token 无限细粒度共享。

新请求到来时，可以按以下顺序理解：

这一流程把“前缀复用”和“分页增长”连接成完整系统视角。

考虑同一个 decoder-only Transformer 接收两条序列：

前 $L$ 个 token ID 完全相同，之后可以不同，甚至两条序列总长度也可以不同。

我们要证明：在满足相同模型状态、相同位置编号与相同因果掩码等条件时，每一层公共前缀位置的 K/V 相同，因此可以复用同一份 KV Cache。

证明不是从“字符串看起来相同”直接跳到“缓存相同”，而是逐层追踪隐藏状态如何计算。

对某层输入矩阵

线性投影对每一行应用相同权重：

第 $i$ 行只由 $H_i$ 决定：

逐元素激活、RMSNorm/LayerNorm（沿单个 token 的特征维归一化）和标准 FFN 同样不跨 token 行混合。

真正把不同序列位置汇聚到一起的是 self-attention。

假设首个不同位置是 $L+1$。

在嵌入层，公共前缀使用相同 token ID 和相同 position ID，因此

首个差异及之后的位置可能不同。

视频例中前两个 token 是公共前缀，第三个 token 首次不同。

即使第四个 token 的 token ID 恰好再次相同，它的隐藏状态也未必相同，因为它已经读取了不同的第三个 token。

所以“公共前缀”必须是从序列起点连续相同的一段，不能把差异之后偶然相同的 token 也算进去。

由逐位置线性投影可知，对 $i\le L$：

后续不同位置的 Q/K/V 可以不同，但它们是否会影响公共前缀，还要看 causal mask。

位置 $i$ 的注意力分数是

标准因果掩码满足

因此公共前缀中的位置 $i\le L$ 只能读取 $j\le i$ 的 K/V。

这些历史位置也全部处在公共前缀内，两个序列的 Q、K、V 对应行相同。

故公共前缀位置的合法分数、softmax 权重和注意力输出逐项相同。

如果去掉 causal mask，前缀位置可能看到后面的差异，结论一般不再成立。

首个不同 token 能改变自己及后续 token 的注意力分数与 value 加权和。

所以从首个差异位置开始，隐藏状态通常都会分叉。

而公共前缀行看不到未来差异，保持相同。

后接的输出投影、残差连接、归一化与 FFN 都是逐位置操作，因此不会把后缀差异重新混回前缀行。

归纳假设：第 $\ell$ 层输入的公共前缀隐藏状态相同：

则有：

所以

由嵌入层的基础情形出发，结论对所有 Transformer 层成立。

每一层缓存的公共前缀 K/V 因而相同。

RoPE 对位置 $i$ 的 Q/K 应用由 position ID 决定的旋转：

若两条序列的公共前缀使用相同 position ID，则相同 Q/K 乘上同一个旋转矩阵，结果仍相同。

注意力内积还可写为

其中相对旋转只依赖相同的位置差 $j-i$。

因此 RoPE 本身不会破坏公共前缀缓存相等性。

但如果同一 token 前缀被放到不同绝对 position ID，旋转后的 K 通常不同，不能直接按字节复用。

多头注意力只是对各头分别应用相同论证。

每个头的公共前缀 Q/K/V 和注意力输出相同，拼接后再经 $W_O$ 的结果也相同。

两条序列的总长度不同不影响已经计算的公共前缀，因为因果位置看不到未来追加的 token。

这正是 prefix caching 能让多个请求共享相同提示词前缀缓存的数学基础。

语义上的相同 K/V 至少需要：

浮点 kernel、设备和归约顺序不同还可能造成末位数值差异。

所以工程缓存通常以“请求条件完全匹配并复用已算出的同一缓存块”为准，而不是分别重算后要求文件哈希绝对相同。

以下情况不能直接套用：

判断能否复用缓存，必须检查真实计算图，而不是只比较字符串前缀。

完整因果注意力在生成位置 $t$ 可以读取从 1 到 $t$ 的所有历史 K/V。

KV Cache 因而随序列长度线性增长。

滑动窗口注意力把可见范围限制在最近 $W$ 个位置。

按本课约定，当前位置也计入窗口：位置 $t$ 可读取

若模型永远不会再次读取窗口外的 K/V，就没有必要继续保存它们。

环形缓存用固定 $W$ 个物理槽位反复承载最近窗口，从而把单层单头的时间轴容量固定在 $O(W)$。

假设窗口大小 $W=4$。

生成前三个 token 后，缓存里依次保存

这时容量还没用满，物理顺序与逻辑时间顺序一致。

第 4 个 token 到来时，把 $(K_4,V_4)$ 写入最后一个空槽，缓存第一次填满。

第 4 个 token 的隐藏状态投影出 $Q_4,K_4,V_4$。

$Q_4$ 与窗口内 K 做点积：

经过 softmax 得到长度为 4 的权重向量 $a_4$，再计算