从 dense 到高效
dense attention 撞上算力与显存两道墙，高效注意力沿三条机制族路线绕开
核心要点：
- dense attention 有两道墙：算力 $O(n^2)$、KV 显存 $O(n)$
- 优化按"图什么"分三方向：降算力 / 降 KV / 换结构
- 实现卷按"怎么偏离 dense"分三机制族：稀疏化 / 压缩化 / 换算子
- 多数技术横跨多个优化目标，但偏离方式唯一
- 读实现卷前需懂 dense 多头 + RoPE + KV cache
本篇是注意力机制章实现卷的入口：承接基础卷讲完的 dense 多头（05-多头注意力），引出"dense 为什么不够、怎么优化、实现卷怎么编排"。机制族与各技术的主词条归属见 01-总览 的「机制族与 SSOT 归属」段，本篇不重复归属表，只讲分类背后的逻辑。
dense attention 撞上哪两道墙？
dense attention 让每个 query 看全序列，这带来算力和显存两道随序列长度恶化的墙。两道墙出现在推理的不同阶段，成因不同。
- 算力墙（prefill 阶段）：attention 要算每个 query 与每个 key 的内积，共 $n^2$ 对，复杂度 $O(n^2 d)$。序列长度翻倍，attention 算力涨 4 倍。长上下文 prefill 时它主导延迟。
- 显存墙（decode 阶段）：decode 逐 token 生成，须缓存历史所有 token 的 K/V（KV cache）避免重算，缓存量 $O(n)$ 线性增长。长序列下 KV cache 占满显存，且每步 decode 都要把它从显存读一遍，受带宽限制。
对比：算力墙是计算量问题（prefill，compute-bound）；显存墙是容量 + 带宽问题（decode，memory-bound）。两道墙要分别治，没有单一手段同时拆掉。
dense 的根因是"每个 query 看全序列"这条 all-pairs 假设。高效注意力全都在动这条假设——要么少看（稀疏），要么把"全序列"压短（压缩），要么换一种不做两两内积的算子（线性 / SSM）。
绕开两道墙有哪三个优化方向？
按"图解决哪道墙"，优化分降算力、降 KV、换结构三个方向。这是从读者需求出发的分类——先想清要解决什么，再去找对应技术。
- 降算力：减少参与计算的 query-key 对。query 只看局部窗口或只看选中的少数 key，把 $O(n^2)$ 压到 $O(n \cdot w)$（$w$ 为窗口或选中数）。
- 降 KV：减少需要缓存的 KV entry 数量或维度。把多个 token 压成一个 entry（序列压缩），或把每 token 的 KV 压到低维 latent（维度压缩）。
- 换结构：放弃 softmax attention 本身，用线性递推的隐状态代替全 attention，KV cache 退化成固定大小的状态矩阵，与序列长无关。
这三个方向不是互斥的——一个技术常同时图多个目标。压缩注意力既降 KV（少存 entry）又降算力（少算对）；SSM 三个目标全占。这正是下一节要解决的编排难题。
为什么实现卷按机制族而不是优化目标编排？
因为多数技术横跨多个优化目标，按目标分组会把一个技术劈开；而"怎么偏离 dense"对每个技术是唯一的。优化目标是"图什么"（主观归因），机制族是"怎么算"（客观属性）——实现卷讲的是怎么算，所以按机制族编排。
实现卷分三个机制族，每族对应一种偏离 dense 的方式：
稀疏化是"保留 softmax，减少 query-key 对"。
- 怎么偏离：仍做标准 softmax attention，但每个 query 只对一部分 key 计算，而非全序列。
- 两种选 key 方式：固定局部窗口（SWA）或动态选最相关的 top-k（NSA / DSA）。
- 详见实现卷 07 滑窗与固定稀疏、08 动态稀疏选择两篇。
压缩化是"保留 softmax，减少 KV entry 数或维度"。
- 怎么偏离：softmax attention 不变，但把"全序列的 KV"先压短再算。
- 两个压缩方向：序列方向（每若干 token 压成一个 entry，如 CSA / HCA）、维度方向（每 token 的 KV 压到低维 latent，如 MLA）。
- 详见实现卷 09 序列压缩、10 维度压缩（MLA）两篇。
换算子是"放弃 softmax dot-product"。
- 怎么偏离：不再做两两内积 + softmax，改用核函数重排或递归隐状态，把序列写成前缀状态递推。
- 代表：线性注意力、Mamba / SSM。
- 详见实现卷 11 线性注意力与 SSM 篇。
| 机制族 | 偏离方式 | 主治哪道墙 | 代表技术 |
|---|---|---|---|
| 稀疏化 | 减少 query-key 对 | 算力墙为主 | SWA / Longformer / NSA / DSA / MoBA |
| 压缩化 | 减少 KV entry 数 / 维度 | 显存墙为主，兼降算力 | CSA / HCA / MLA |
| 换算子 | 放弃 softmax dot-product | 两墙同治（状态固定） | 线性注意力 / Mamba / SSD |
@tbl-attn-d2e-family 三条机制族路线对照
陷阱：别用"优化目标"给技术分类。CSA 同时压缩（降 KV）和稀疏选择（降算力），Mamba 三个目标全占——按目标分组它们会被劈成两半。机制族是唯一归宿：CSA 的核心偏离是压缩，稀疏是其上叠加；Mamba 的核心偏离是换算子。
读实现卷前要先懂什么？
实现卷假设读者已过基础卷，并掌握 RoPE 与 KV cache——这些前置在别处已有，先补齐再读 07/08/09。前沿注意力（如 DSA 的 lightning indexer、CSA 的 compressor）建立在这些机制上，缺前置会卡在机制细节。
前置门槛：
- dense 多头注意力 → 05-多头注意力（基础卷终点）
- RoPE 位置编码 → 03-文本如何变成数字 / 位置编码
- KV cache 推理管理 → 08-推理 / KV cache
- Flash Attention（IO-aware kernel 融合）→ 待补；当前先参考外部资料[1]
实现卷各篇的"为什么需要"动机，与 03-长上下文 / 注意力机制变体 的优化方向导览互为镜像：03 讲长上下文为什么需要这些优化，本卷讲它们怎么实现。
Takeaway
| 知识点 | 核心结论 |
|---|---|
| 两道墙 | dense 有算力墙 $O(n^2)$（prefill）和显存墙 $O(n)$（decode），成因不同需分治 |
| 三个优化方向 | 降算力 / 降 KV / 换结构，按"图什么"分，供读者按需求找技术 |
| 三个机制族 | 稀疏化 / 压缩化 / 换算子，按"怎么偏离 dense"分，实现卷据此编排 |
| 为何按机制族 | 多数技术横跨多目标，按目标会劈开技术；偏离方式才是唯一归宿 |
| 前置门槛 | 读实现卷前须懂 dense 多头 + RoPE + KV cache |
@tbl-attn-d2e-takeaway 从 dense 到高效核心知识点
参考资料
- Dao et al., FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness, NeurIPS 2022. https://arxiv.org/abs/2205.14135