附加讲 A3 · 检索增强生成与向量检索：RAG、IVF、PQ、HNSW · Retrieval-Augmented Generation and Vector Search

对应 Maps to：CMU 11-868 / 11-968 Large Language Model Systems（Spring 2026，Lei Li）课表末尾列出、本学期未排课的两个主题 Retrieval-augmented Language Models 与 Nearest Vector Search for Embeddings（HNSW）。这两个主题没有公开 slides。 阅读材料：Lewis et al. (2020) Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks（NeurIPS）；Malkov & Yashunin (2018) Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs（IEEE TPAMI）。 依据说明：因为没有 slides，本讲按两篇阅读材料组织。RAG 论文：检索器（DPR 的双编码器，两个 BERT-base）+ 生成器（BART-large，4 亿参数）；知识库是 2018 年 12 月的维基百科，切成 100 词一段，共 2100 万段，用 FAISS 的 HNSW 索引做最大内积检索；RAG-Sequence 与 RAG-Token 两种边缘化；开放域问答的结果、换索引就能更新知识（“index hot-swapping”）、检索篇数的影响、索引占约 100 GB 内存（压缩后 36 GB）。HNSW 论文：从 NSW 到分层、层数的几何分布（mL = 1/ln M，对应跳表的 p = 1/M）、搜索与插入算法、启发式选邻居、参数（M 取 5–48，第 0 层最多 2M 条边，ef_construction 要大到建图时的召回接近 1）、分层在低维数据上的巨大加速。IVF 与乘积量化（PQ）按 Jégou et al. (2011) 与 FAISS 的通行做法讲解。本讲义的知识库与”读者”实验、维度灾难的演示、四种检索方法的距离计数、HNSW 的各项拆解实验，都是本讲义自己设计的；小规模上的数字只说明机制，规模化的结论以论文为准。 配套代码 Code：code/appendixA3/（3 个脚本 + vecsearch.py、rag.py；读者模型复用第 27 讲的”记录世界”，时间模型复用第 26 讲） 预计阅读时间：2.5 小时（含运行代码）

0. 本讲导航 · How to read this lecture

0.1 学习目标 Learning goals

1. 说出 RAG 要解决的问题（知识过时、长尾、无从溯源）与它的结构（检索器 + 读者），解释 RAG-Sequence 与 RAG-Token 的区别。
2. 说出一次 RAG 请求的时间花在哪里，以及”检索几篇、按什么顺序放”为什么会影响质量。
3. 解释维度灾难，说出暴力检索、IVF、PQ、HNSW 各自的思想，以及”算多少次距离 / 占多少内存 / 建索引要多久 / 召回多少”之间的取舍。
4. 讲清 HNSW 的三个设计：小世界图上的贪心搜索、跳表式的分层、启发式选邻居——各自解决了什么问题。

0.2 先修与本讲范围

0.3 本讲地图

§1  为什么要检索：把知识放在参数之外                                       ← 代码 01
§2  RAG 的流程与系统开销                                                    ← 代码 01
§3  最近邻检索：精确 vs 近似，维度灾难                                      ← 代码 02
§4  IVF 与 PQ：先分簇、再压缩                                               ← 代码 02
§5  HNSW：在分层的近邻图上走                                                ← 代码 03（+ 02）
§6  汇总：怎么选，在 RAG 里意味着什么                                       ← 代码 02、01
§7  小结   §8 常见误区   §9 练习   §10 延伸阅读   §11 下一讲预告

0.4 本讲的小知识库

01 号脚本需要一个”必须靠检索才能回答”的场景。rag.py 造了一个 2000 篇文档的知识库：每篇文档是 4 条”键 值”记录（像”职位 → 人名”），同一个键在不同文档里的值不同（不同公司的同名职位）；每篇文档有一个随机的”主题嵌入”（32 维单位向量）。一个问题 = (某篇文档, 它的一个键)，问题的嵌入 = 文档的嵌入 + 噪声（噪声代表”问题的措辞和文档不完全一样”，噪声越大越难检索）。读者是第 27 讲为 CacheBlend 训练的”记录世界”小模型：它会在上下文里找到键、复制后面的值。读者的参数里不可能有答案（每篇文档的映射都是随机的），所以它只能靠检索。

1. 为什么要检索 · Why retrieval

1.1 直觉：开卷考试

闭卷考试，你只能靠记忆；开卷考试，你可以翻书。LLM 默认是闭卷的：所有知识都压在参数里。RAG（检索增强生成）让它开卷——先从一个外部的知识库里找出和问题相关的几段文字，再”读着这几段”回答。

1.2 背景：参数里的知识有三个问题

1. 会过时：参数是训练时那一刻的世界。要更新知识，就要再训练（或微调），贵而且慢。
2. 长尾记不住：训练数据里只出现过几次的事实（某个小公司的 CEO、某份内部文档的条款），模型很难记牢；模型越小越明显。
3. 无从溯源：模型说出一个事实，你不知道它来自哪里，也就无法判断它是不是编的（幻觉）。

把知识放在参数之外的一个可以检索的库里，这三个问题都有了解法：换库就能更新知识；库里有就能查到，不管它多冷门；回答可以附上出处。RAG 论文把参数叫”参数化记忆”（parametric memory），把知识库叫”非参数化记忆”（non-parametric memory）。

那为什么不干脆把所有资料都塞进上下文？上下文再长也有上限，而且每多一个 token，预填充就多一份计算、KV 缓存就多一份显存（第 22、24 讲）；附加讲 A2 里 Kimi 的用户把整本书扔进上下文，Mooncake 要专门建一个分布式 KV 缓存池来扛。检索是另一条路：只取出相关的几段，上下文短、便宜。两条路并不互斥——第 27 讲的 CacheBlend 就是为”检索到的多段文字的 KV 能否复用”设计的。

1.3 动机与做法：RAG 论文

RAG 论文的系统由两部分组成：

• 检索器 p_η(z | x)：DPR 的双编码器。文档 z 和问题 x 各用一个 BERT-base 编码成向量 d(z)、q(x)，相关度 = 内积 d(z)ᵀ q(x)。找相关度最高的 k 篇文档 = 最大内积检索（MIPS）。知识库是 2018 年 12 月的维基百科，切成 100 词一段，共 2100 万段；用 FAISS 的 HNSW 索引（§5）在亚线性时间里近似地找。
• 生成器 p_θ(y_i | x, z, y_{<i})：BART-large（4 亿参数），把问题和检索到的文档拼在一起作为输入。

为什么这样分工？ 检索器只负责”找”，可以离线把 2100 万段文字一次编码好、建好索引；生成器只负责”读和写”。训练时不告诉模型该检索哪篇，而是把检索到的文档当作隐变量，对它们求和（边缘化），直接最大化答案的似然；文档编码器和索引固定不动（每次更新都要重新编码 2100 万段、重建索引，太贵），只微调问题编码器和 BART。

1.4 效果

• 开放域问答（Natural Questions，精确匹配）：RAG-Sequence 44.5、RAG-Token 44.1；只靠参数的 T5-11B 是 34.5，参数量最接近 RAG 的 T5-large（7.7 亿）是 28.9。RAG 可训练的参数只有约 6.3 亿。
• 即使检索到的文档里都没有答案，RAG 仍有 11.8% 的问题答对（抽取式的方法只能是 0）——生成器参数里的知识也在起作用。
• 换索引就能更新知识：82 个在 2016 到 2018 年间换了人的国家领导人职位，用 2016 年的索引问 2016 年的领导人答对 70%，用 2018 年的索引问 2018 年的领导人 68%；索引和年份不匹配时只有 12% 和 4%。不用重新训练。

1.5 在小知识库上（01 号脚本第 1 部分）

不检索时读者只能瞎猜（12 个可能的值，约 1/12）。给对了文档就全对——这个读者的能力不是瓶颈，检索才是。下一节看检索不完美时会发生什么。

2. RAG 的流程与系统开销 · The RAG pipeline

2.1 两条路径

离线（建库）：  原始文档 → 切块（几百个 token 一块）→ 嵌入模型编码 → 建向量索引（§3–§5）
在线（每个请求）：问题 → 嵌入模型编码（几毫秒）→ 向量检索 top-k（几毫秒）→ [重排序] → 拼成提示 → LLM 预填充 + 解码

附加讲 A1 的应用栈里，“嵌入模型 + 向量数据库 + 编排”就是这条流水线。离线部分决定了检索的质量上限（切块的粒度、嵌入模型的好坏）；在线部分决定了延迟。

2.2 检索几篇？

直觉：多检索几篇，正确的文档更可能在里面（召回率上升）；但多出来的文档也可能误导读者。

01 号脚本第 1 部分：

噪声小（检索容易）时，检索 1 篇召回率就有 97%，多检索只会带来干扰：检索 4 篇时，38% 的情况下别的文档里有”同一个键的不同值”，准确率从 97% 掉到 82%。噪声大（检索难）时，多检索把召回率从 59% 提到 82%，端到端先升后降（66% → 71% → 70%）——召回率的收益和干扰的代价在拉锯。（噪声 1.4、检索 1 篇时准确率 65.7% 比召回率 59.3% 还高，是因为检索错了时读者偶尔也能蒙对。）

真实的 RAG 也会被多余的段落干扰。RAG 论文里，RAG-Token 在检索 10 篇时最好，再多反而下降；RAG-Sequence 每篇文档单独生成、不会互相干扰，检索越多越好（论文问答的测试用了 50 篇）。“迷失在中间”（Liu et al. 2023）发现长上下文中间的段落容易被模型忽略。此外，每多一篇文档，提示就更长、预填充更慢（§2.5）。

2.3 按什么顺序放？

01 号脚本第 2 部分（检索 4 篇）：最相关的放最前面 82.3%，放最后（紧挨着问题）75.3%。这个读者遇到”同一个键两个值”时更倾向于复制前面的那个——它训练时同一个键的值从不改变，从没学过”以哪个为准”。具体偏向哪边是这个小模型的训练方式决定的，不代表真实 LLM；但”顺序有影响”是普遍的：真实模型常常对开头和结尾的段落记得更好。所以生产系统会对检索结果重排序（reranker）、去重，在提示里说明”以哪一段为准”。

2.4 RAG-Sequence vs RAG-Token

检索到 k 篇文档后，答案 y 的概率要对文档求和。RAG 论文给了两种求和方式：

RAG-Sequence:  p(y|x) ≈ Σ_z p(z|x) · Π_i p(y_i | x, z, y_<i)       整段回答依据同一篇文档
RAG-Token:     p(y|x) ≈ Π_i Σ_z p(z|x) · p(y_i | x, z, y_<i)       每个 token 都可以依据不同的文档

01 号脚本第 4 部分的数值例子：两篇文档，p(z1) = 0.6、p(z2) = 0.4；生成器在 z1 下倾向说”A D”，在 z2 下倾向说”B C”。

RAG-Sequence 下，“A C”（把两篇文档的说法拼在一起）的概率较低；RAG-Token 下它从 0.18 升到 0.30，几乎和”A D”一样高。RAG-Token 能综合多篇文档的信息（一个答案的不同部分来自不同的文档），也更容易拼出”每一半都有出处、合起来却不对”的回答。

系统上的差别：RAG-Token 每一步的转移概率是对文档求和后的分布，可以直接用普通的束搜索；RAG-Sequence 不能拆成逐 token 的概率，要对每篇文档各做一次束搜索，再对候选答案重新打分——成本正比于检索的篇数。今天的 LLM 应用大多用更简单的做法：把 k 篇文档拼进一个提示，让模型自己在注意力里”边缘化”（2.2、2.3 节就是这种做法）。

2.5 一次请求的时间花在哪里

01 号脚本第 5 部分（LLaMA-3-8B，1 张 H100，第 26 讲的”纸面 GPU”模型；每篇检索结果 512 个 token，问题 50 个 token，回答 200 个 token）：

嵌入问题、向量检索都只要几毫秒；真正随检索篇数增长的是预填充——检索 10 篇时是不检索的 19 倍。解码每一步也要读检索结果的 KV，但 8B 模型用 GQA，KV 很小，批大小为 1 时生成只多了 4%；批大了以后，KV 的读取会成为主要开销（第 24 讲）。

于是 RAG 的系统优化集中在两头：

• 检索端：近似最近邻（§3–§5）让检索在十亿级的库上也只要几毫秒；压缩（PQ）让库放得进内存。
• 生成端：同一篇热门文档会被很多请求检索到，它的 KV 值得缓存。第 22 讲的前缀缓存只能复用第一篇（后面的文档前缀不同）；第 27 讲的 CacheBlend 能复用每一篇，只重算少数 token 来补上跨文档的注意力。

3. 最近邻检索：精确 vs 近似 · Exact vs approximate nearest neighbors

3.1 问题的定义

给定 N 个 d 维向量和一个查询 q，找出离 q 最近的 k 个（k-NN）。“近”可以是欧氏距离、内积或余弦相似度。对单位向量，‖q − x‖² = 2 − 2 qᵀx，三者给出相同的排序；不是单位向量时，最大内积检索可以通过给每个向量加一维转化成欧氏距离的检索。本讲的代码全部用平方欧氏距离。

暴力检索（flat）：和所有 N 个向量算距离，取最小的 k 个。精确，但每个查询要读完整个库。N = 2100 万、768 维、float32 时，一个查询要读约 65 GB——即使内存带宽有 200 GB/s，也要 0.3 秒；N = 十亿时是 15 秒。所以要近似：只看其中一小部分，换来”偶尔漏掉一个真正的近邻”。衡量近似的指标是 recall@k：找到的 k 个里，有多少是真正的 k 个最近邻之一。

3.2 维度灾难：为什么”找最近的”在高维很难

直觉：二维平面上撒一把点，离你最近的点和最远的点距离差别很大。到了 512 维，每个点和你的距离几乎一样——“最近邻”几乎失去意义。

为什么：两个随机点的平方距离是 d 个独立项之和，均值正比于 d，标准差只正比于 √d；相对的波动 ∝ 1/√d，维度越高，所有距离越集中在平均值附近（测度集中）。

02 号脚本第 1 部分（2000 个点，20 个查询的平均）：

512 维的随机点，平均距离只比最近的距离大 10%：任何近似方法稍有误差就会排错，也没法靠”排除远处的一大片”来省计算。

那近似最近邻为什么还能用？ 因为真实的嵌入不是均匀随机的：同一主题的文字挤在一起（成簇），“内在维度”远低于名义维度。表的最后一行：同样是 64 维，有簇结构的数据里最近邻比平均近 3.6 倍。近似检索靠的就是这种结构。这也解释了 01 号脚本第 3 部分的一个现象：那里的文档嵌入是 32 维的随机单位向量，是近似检索最难的情形，HNSW 的参数要给得更大才够准（§6.2）。

3.3 该比什么

02 号脚本用 20,000 个 64 维、有簇结构的单位向量，200 个查询，看 recall@10。暴力检索每个查询算 20,000 次距离，每个向量占 256 字节（64 × 4）。

比较的是”算了多少次距离”，不是 Python 的运行时间：暴力检索用 NumPy 一次算完 200 个查询（82 ms），HNSW 用纯 Python 一个点一个点地走，Python 的开销会颠倒算法的优劣。真实的库（FAISS、hnswlib）都是 C++ / SIMD 实现，那时距离计算的次数（以及读了多少字节）才是主要的成本。

4. IVF 与 PQ：先分簇、再压缩 · Inverted file and product quantization

4.1 IVF：只查最近的几个簇

直觉：图书馆按学科分区。找一本书，先看它属于哪个区，再只在这个区（和相邻的几个区）里找。

机制：用 k-means 把 N 个向量分成 nlist 个簇，每个簇一个”倒排列表”（inverted list，存簇里向量的编号）。查询时先和 nlist 个中心算距离，挑最近的 nprobe 个簇，只和这些簇里的向量算距离。距离计算 ≈ nlist + nprobe × N / nlist。nlist 常取 √N 量级：簇太多，光是和中心比就很贵；簇太少，每个簇太大。

为什么会漏：查询靠近簇的边界时，真正的近邻有一部分在隔壁的簇里。nprobe 就是”准”与”快”的旋钮。

02 号脚本第 3 部分（nlist = 141）：

只查 1 个簇时漏掉三分之一；查 4 个簇就有 98.9%，只算了暴力的 4.2%。k-means 只要 0.12 秒。IVF 简单、建得快、内存几乎不增加（每个向量多一个 4 字节的编号），而且查一个簇就是一次小矩阵乘，很适合 GPU 批量算——这是 FAISS 的主力。缺点是成本随 N 线性增长（簇数固定时，每个簇随 N 变大）。

4.2 PQ：每个向量压成几个字节

动机：十亿个 768 维的 float32 向量是 3 TB——一台机器的内存放不下，暴力扫描一遍也太慢。能不能把每个向量压到几十个字节？

直觉：直接对整个向量做 k-means 量化，要表达得精细需要天文数字个中心。乘积量化（product quantization）把向量切成 M 段，每段各自做 k-means（256 个中心）：每段用 1 个字节的中心编号表示，整个向量只要 M 个字节，却能表达 256^M 种组合。M = 8 时，64 维的向量从 256 字节压到 8 字节（32 倍）。

查询（ADC，非对称距离计算）：查询本身不量化。对每一段，先算查询的这一段到 256 个中心的距离，得到一张 M × 256 的表；某个库向量的近似距离 = 按它的 M 个编号查表、相加。M 次查表加法代替 d 次乘加，扫描的是 N × M 字节的编码而不是 N × d × 4 字节的原始向量。

4.3 为什么要精确重排

02 号脚本第 4 部分：

只看近似距离，recall@10 只有 15%（M = 8）！原因是量化误差比近邻之间的差距还大：M = 8 时 ‖x − 解码(编码(x))‖² 平均 0.083，而第 1 个与第 10 个近邻的平方距离只差 0.026。近似距离能把”近的一群”从 N 个里粗筛出来，却排不对这一群内部的先后。所以要重排：按近似距离取前几百个候选，再用原始向量（放在内存或 SSD 里）算精确距离。重排 200 个就回到 86.5%（M = 8）/ 98.4%（M = 16）。

4.4 IVF-PQ

生产系统常把两者组合：先用 IVF 选出几个簇，只扫描这些簇里的 PQ 编码，再精确重排（FAISS 的 IVFADC / IVF-PQ）。RAG 论文的索引就用了 FAISS：未压缩时约占 100 GB 内存，用 FAISS 的压缩工具降到 36 GB。

5. HNSW：在分层的近邻图上走 · Hierarchical Navigable Small World graphs

5.1 直觉：小世界与贪心路由

“六度分隔”：任何两个人之间平均只隔几个熟人。一个社交网络里，大多数关系是”近”的（同事、邻居），少数是”远”的（远方的朋友）；靠这些远关系，几步就能到达任何人。

把向量当作人、把”离得近”当作”认识”，建一张近邻图。查询时从某个入口点出发，贪心地走：每一步看当前点的所有邻居，走到离查询最近的那个；走不动了，当前点就是（近似的）最近邻。为了少走弯路，维护一个大小为 ef 的”目前最好的 ef 个点”的列表，做最佳优先搜索（ef 越大越准、越慢）。

NSW（可导航小世界图，Malkov et al. 2014）就是这样建的：点一个个插入，每个新点用同样的搜索找到最近的 M 个点、连边。早插入的点连边时图里还没几个点，它们的边就是”长边”——自然形成了远关系。

5.2 分层：像跳表一样

NSW 的问题：长边和短边混在同一层，搜索要先一跳一跳地沿着长边靠近目标，再在短边上精细定位；HNSW 论文指出 NSW 的总复杂度是多对数（polylog）的，在低维数据上尤其慢。

HNSW 的做法是借鉴跳表（skip list）：每个点随机分配一个最高层 l = ⌊−ln(U) · mL⌋（U 是 (0, 1) 上的均匀随机数，mL = 1/ln M）。于是第 l 层大约有 N · M^(−l) 个点——越往上越稀疏。每一层都是一张近邻图：上层的点稀疏、边长；下层的点密集、边短。查询从顶层的入口点出发，在每个上层做 ef = 1 的贪心搜索，把找到的点当作下一层的入口；到第 0 层再做宽度为 ef 的搜索。

03 号脚本第 1 部分（16,000 个 64 维向量，M = 16）：

一次查询（ef = 40）从顶层走到第 0 层：

上层一共只算了 65 次距离（这次查询的 17%），就把距离从 1.532 缩到 0.404；第 0 层的 328 次距离用来在目标附近精细搜索。上层负责”跨越空间”，下层负责”精细定位”——和跳表一样，每次查询只看 O(log N) 量级的区域。

5.3 搜索算法

search(q, k, ef):
    ep = 入口点（顶层）
    for 层 l = 顶层 … 1:   ep = search_layer(q, ep, ef=1, l)        # 贪心：一直走向更近的邻居
    W = search_layer(q, ep, ef, 0)                                   # 第 0 层：宽度为 ef 的最佳优先搜索
    return W 中最近的 k 个

search_layer(q, 入口, ef, l):
    candidates = 小顶堆（待扩展的点，按距离）     results = 大顶堆（目前最好的 ef 个点）
    while candidates 非空:
        c = candidates 中最近的点
        if c 比 results 中最远的还远 且 results 已满 ef 个:  停止
        for c 在第 l 层的每个未访问过的邻居 n:
            若 n 比 results 中最远的近（或 results 不满 ef 个）:  加入 candidates 和 results（results 只保留 ef 个）

vecsearch.py 的 HNSW._search_layer 就是这段伪代码的直接实现（用 heapq；Python 只有小顶堆，把距离取负就成了大顶堆）。

5.4 插入与启发式选邻居

插入一个新点：先抽它的最高层 l；从顶层贪心地走到第 l + 1 层；从第 l 层到第 0 层，每层用宽度为 ef_construction 的搜索找到候选，从候选里选 M 个当邻居，连双向边；某个邻居的边超过上限（上层 M、第 0 层 2M）时，重新为它挑选、剪掉多余的边。

最直接的选法是”取最近的 M 个”。HNSW 用的是启发式：从近到远检查候选，一个候选只有在它离新点比离任何已选邻居都近时才被选中。效果是：同一个方向上只留一条边，省下来的边数指向别的方向——包括通往别的簇的”桥”。

为什么重要：有簇的数据上，一个点最近的 M 个邻居全在自己的簇里；只连最近的，簇与簇之间就断了，搜索困在入口所在的簇里。HNSW 论文：只连最近的邻居时，HNSW 在高度成簇的数据上”达不到高召回，因为搜索卡在簇的边界”。

03 号脚本第 4 部分（100 个很紧的簇，8 维，8,000 个点，M = 8）：

一个出乎意料的细节：简单选法下跨簇的边反而更多，但它们挤在相邻的簇之间，同一对簇之间平均 11 条，多是同一个方向上的重复边；更要命的是，有 1,440 个点所在的小团体，指向它们的边全来自团体内部——从入口出发根本走不进去。启发式的跨簇边只有一半，却连起了更多的簇对，所有点都走得到。图的”连通”不在边多，而在方向分散。HNSW 论文的总结：启发式在低维数据、中等维度的高召回要求、以及高度成簇的数据上效果最显著；在均匀的高维数据上两种选法差别不大（这时启发式选出的几乎就是最近的那些）。

5.5 分层到底有什么用

03 号脚本第 3 部分把 HNSW 和”所有点都在第 0 层”的 NSW 对比（均匀随机点，M = 6，查询 ef = 10）：

2 维时，N 涨 16 倍，NSW 的距离计算涨了 3.07 倍，HNSW 只涨 1.36 倍；N = 16,000 时 NSW 多算 3.4 倍（两者的 recall 都是 100%）。低维空间里”从一处走到另一处”要很多跳，NSW 只能一跳一跳地走。8 维时两者几乎一样：维度高时图的直径本来就小，早期插入的长边已经够用。HNSW 论文的结论一致：把 mL 从 0（NSW）调到 1/ln M，在 1000 万个 4 维随机点上带来巨大的加速；在 1024 维的随机点上也有可测量、但小得多的提升。分层的好处主要在低维、有局部结构的数据上——而真实的嵌入往往有很低的内在维度。

5.6 规模与参数

随 N 的增长（03 号脚本第 2 部分，同一个索引边建边测，ef = 40）：

N 涨 16 倍，HNSW 的距离计算只涨 1.21 倍。前几行甚至不升反降：N 小时，ef = 40 的搜索已经覆盖了图的一大块（N = 1,000 时看了 30% 的点）。N 每涨 M 倍才多一层，每层只走固定的几步——数据越多，HNSW 相对暴力检索的优势越大。

搜索宽度 ef（02 号脚本第 5 部分，20,000 个点，M = 16）：ef = 10 时 270 次距离、recall 90.4%；ef = 40 时 445 次、99.6%；ef = 160 时 599 次、100%。ef 加 16 倍，距离计算只涨 2.2 倍——走到正确的区域之后，加宽搜索主要是在同一片邻居里多看几眼。

建图的代价：每插入一个点平均算 3,276 次距离（约等于 7 次 ef = 40 的查询）；第 0 层平均每个点 25 条边，每个向量多占 104 字节。纯 Python 建 20,000 个点要 38 秒——真实的库是 C++ 多线程，但”建图比 IVF 贵得多”的结论不变。

M 与 ef_construction（03 号脚本第 5 部分，换成簇大量重叠的 64 维数据，查询 ef = 10；在簇很清楚的数据上几乎任何参数都有 99% 以上，看不出差别）：

M 太小时图不够”通”，搜索卡在局部；M 越大越准，但建图、内存、每一步要看的邻居都随 M 增长。HNSW 论文建议 M 取 5–48：低维、低召回要求时小一些，高维、高召回要求时大一些；内存与 M 成正比。ef_construction 只影响建图：太小（10）时选邻居只看 10 个候选，边的质量差；够大以后再加没有帮助（400 比 100 还略低，在随机波动之内）。论文的建议是让它大到建图时的搜索召回接近 1（0.95 对多数情况够用）。

6. 汇总：怎么选，在 RAG 里意味着什么 · Putting it together

6.1 四种做法的对比

02 号脚本第 6 部分：要达到同样的 recall@10，每个查询最少要算多少次距离（20,000 个向量）：

外推到十亿个 768 维向量（内存带宽假设为 200 GB/s）：

三者的取舍是计算、内存、建索引的时间：

• HNSW：同样的召回率算的距离最少，延迟最低；但整张图要放在内存里随机访问，建图贵，内存比原始向量还多一截；删除和更新也麻烦。
• IVF：建得快、内存几乎不增加、适合 GPU 批量算；成本随 N 线性增长。
• PQ / IVF-PQ：内存小几十倍，十亿级的库能放进一台机器；近似距离不准，要精确重排。
• 规模再大，或者内存不够时：把图放在 SSD 上（DiskANN 专门为 SSD 重新设计了图的结构与访问方式）、多机分片。

6.2 近似检索对端到端的影响

01 号脚本第 3 部分把 RAG 的精确检索换成 HNSW（M = 16，检索 2 篇，噪声 1.0）：

ef = 16 时只算了精确检索的 1/5.2，端到端几乎没有损失；ef = 4 时检索漏掉的近邻直接变成了答错的问题。这里只有 2000 篇文档，省下的计算只有几倍；十亿级时省的是几十万倍。端到端的上限 = 检索的召回率 × 读者的准确率——检索要按端到端的质量来调参，而不只是看”和精确检索一致的比例”。

还有一层：recall@k 衡量的是”和精确最近邻一致的比例”，可精确最近邻也不一定包含答案——嵌入模型的质量、切块的方式决定了”语义上最近”是否等于”真正相关”。RAG 论文的消融实验里，词重叠的 BM25 检索器在 FEVER（事实核查，问题里有很多实体名）上反而最好，在开放域问答上稠密检索好得多。生产系统常把两者结合，再用重排序模型精排。

7. 小结 · Summary

1. RAG 把知识放在参数之外：检索器从知识库里取出相关的几段文字，读者读着它们回答。知识可以随时更新（换索引）、长尾也能查到、回答可以溯源。RAG 论文用 DPR + BART + 2100 万段维基百科，在开放域问答上超过了参数多十几倍的闭卷模型。
2. 检索得越多，召回率越高，但干扰也越多，预填充也越慢；检索结果的顺序也影响回答。RAG-Sequence 整段回答依据一篇文档，RAG-Token 每个 token 可以依据不同的文档。
3. 一次 RAG 请求里，嵌入与检索只占几毫秒，预填充随检索篇数线性增长；复用检索结果的 KV（前缀缓存、CacheBlend）是生成端的主要优化。
4. 高维空间里随机点之间的距离几乎相同（维度灾难）；近似最近邻能用，是因为真实的嵌入成簇、内在维度低。
5. IVF 只查最近的几个簇；PQ 把向量压成几个字节、查表算近似距离，再精确重排；HNSW 在分层的近邻图上贪心地走，距离计算随 N 只对数增长。
6. HNSW 的三个设计：小世界图上的贪心搜索（找得到）、跳表式的分层（走得快，低维时尤其重要）、启发式选邻居（有簇的数据上不断开）。

8. 常见误区 · Common pitfalls

1. “检索得越多越好。” 多出来的文档可能和答案冲突、分散注意力，还让预填充变慢。检索篇数要按端到端的质量来选，并配合重排序与去重。
2. “向量检索的 recall 就是 RAG 的准确率。” recall@k 是”和精确最近邻一致的比例”；精确最近邻不一定包含答案（嵌入的质量），包含了读者也不一定答对（干扰、位置）。端到端的上限是两者的乘积。
3. “维度越高，嵌入越好，检索越准。” 名义维度高不等于信息多；对随机的高维数据，近似检索最难。真正决定检索难度的是数据的结构与内在维度。
4. “PQ 的近似距离够用了。” 量化误差可能比近邻之间的差距还大（02 号脚本：0.083 vs 0.026），不重排时 recall@10 只有 15%。PQ 负责粗筛，精确距离负责排序。
5. “HNSW 总是最好的。” 它的查询最快，但内存比原始向量还大、建图贵、删除难、不适合 GPU 批量算。十亿级的库常用 IVF-PQ 或基于 SSD 的图索引。
6. “选邻居时连最近的 M 个就行。” 在有簇的数据上，这会让图断成孤岛（03 号脚本：1,440 个点从入口根本走不到）。HNSW 的启发式让边指向不同的方向。
7. “RAG 只是检索的事，和推理系统无关。” 检索结果占了提示的大部分 token，预填充和 KV 缓存的开销都随它增长；第 22 讲的前缀缓存、第 27 讲的 CacheBlend、附加讲 A2 的 KV 缓存池都和 RAG 直接相关。

9. 练习 · Exercises

1. 在 0.4 节的知识库里，读者不检索时的准确率为什么约为 1/12？如果知识库里同一个键在所有文档里的值都相同，检索 4 篇时准确率还会下降吗？
2. 用 2.4 节的数值例子计算”B D”在 RAG-Sequence 与 RAG-Token 下的概率。
3. 一个 IVF 索引有 N = 100 万个向量。若 nprobe = 1，nlist 取多少时每个查询的距离计算最少？最少是多少？若 nlist = 1000、nprobe = 8 呢？
4. 十亿个 768 维的向量用 PQ 压缩，M = 96、每段 256 个中心。编码一共占多少内存？码本占多少？一个查询的距离表要算多少次乘加？
5. 一个 HNSW 索引有 N = 10 亿个点，M = 16。期望有多少层？第 1 层（及以上）大约有多少个点？第 0 层每个点最多 2M 条边、每条边 4 字节，边一共占多少内存？
6. 解释为什么两个随机高斯向量之间的平方距离，其相对波动（标准差 / 均值）随维度 d 按 1/√d 下降。
7. 用 2.5 节的表：检索 10 篇时预填充 133 ms。若 10 篇文档的 KV 都已缓存，CacheBlend 只需重算约 15% 的 token（忽略加载时间），预填充的计算大约降到多少？若只用前缀缓存呢？
8. HNSW 的启发式选邻居：“候选 c 只有离新点比离任何已选邻居都近时才被选中”。在一维数据（数轴上的点）上，这个规则会为每个点选出哪些邻居？
9. 为什么 HNSW 的 ef_construction 太小会伤害查询的召回率，即使查询时的 ef 很大？

参考答案

1. 读者的参数里没有任何文档的映射，只能在 12 个可能的值里猜，期望约 1/12 ≈ 8%（实测 10.7%，因为模型的猜测并不均匀）。如果所有文档里同一个键的值都相同，检索到的其他文档就不构成冲突，反而是”多一份同样的证据”，准确率不会因为多检索而下降。
2. RAG-Sequence：0.6 × 0.1 × 0.8 + 0.4 × 0.8 × 0.1 = 0.048 + 0.032 = 0.080。RAG-Token：p(B) = 0.6 × 0.1 + 0.4 × 0.8 = 0.38，p(D) = 0.6 × 0.8 + 0.4 × 0.1 = 0.52，乘积 0.1976。RAG-Token 下”B D”（B 来自 z2、D 来自 z1）的概率是 RAG-Sequence 下的 2.5 倍。
3. 距离计算 = nlist + N / nlist，在 nlist = √N = 1000 时最小，为 2000。nlist = 1000、nprobe = 8：1000 + 8 × 1000 = 9000。
4. 编码：10⁹ × 96 字节 = 96 GB。码本：96 段 × 256 个中心 × 8 维 × 4 字节 = 768 KiB（可以忽略）。距离表：96 × 256 × 8 = 196,608 次乘加，相当于 256 次全维距离计算——和扫描 10⁹ 个编码（960 亿次查表加法）相比微不足道。
5. 期望的最高层约为 log₁₆(10⁹) ≈ 7.5，所以约 8 层（第 0–7 层）。第 1 层及以上约 10⁹ / 16 ≈ 6250 万个点。第 0 层的边最多 10⁹ × 32 × 4 字节 = 128 GB（实际平均边数少于上限，02 号脚本里第 0 层平均 25 条）。
6. 平方距离 = Σ_{i=1}^{d} (x_i − y_i)²，各项独立同分布，均值 μ、方差 σ²。和的均值是 dμ，方差是 dσ²，标准差是 √d · σ。相对波动 = √d · σ / (dμ) = (σ/μ) / √d。
7. 预填充的计算约与重算的 token 数成正比（长度不太长时注意力的平方项占比不大）：0.15 × 133 ≈ 20 ms，再加上问题本身的 50 个 token。只用前缀缓存时，只有第一篇文档（约 512 个 token）能复用，其余 9 篇仍要全部预填充，约 133 − 133 × 512 / 5170 ≈ 120 ms，几乎没有省。
8. 一维时，对一个点来说，候选按距离从近到远：左边最近的点和右边最近的点会被选中；同一侧更远的点离已选的同侧邻居更近，会被拒绝。所以每个点只连左右两个直接相邻的点——正好是一维的 Delaunay 图（HNSW 论文据此把它和一维跳表联系起来），加上剪枝后用最近的候选补齐的边。
9. ef_construction 决定建图时为每个点”看了多少候选”。太小时，候选本身就不包含真正的近邻，选出的边质量差、有的区域连不上；图建坏了，查询时 ef 再大也只能在这张坏图上搜索——就像地图画错了，走得再仔细也到不了。

10. 延伸阅读 · Further reading

• RAG：Lewis et al. (2020)；DPR：Karpukhin et al. (2020)，稠密段落检索；REALM：Guu et al. (2020)，预训练时就带检索；RETRO：Borgeaud et al. (2022)，用 2 万亿 token 的检索库让小模型追上大模型。
• Lost in the Middle：Liu et al. (2023)——长上下文中间的信息容易被忽略。
• HNSW：Malkov & Yashunin (2018)；实现 hnswlib；前身 NSW：Malkov et al. (2014)。
• PQ：Jégou, Douze & Schmid (2011) Product Quantization for Nearest Neighbor Search；FAISS：Johnson, Douze & Jégou (2019) Billion-scale similarity search with GPUs。
• DiskANN：Subramanya et al. (2019)——在 SSD 上服务十亿级向量的图索引；ScaNN：Guo et al. (2020)——各向异性量化。
• 基准：ann-benchmarks（不同 ANN 库的 recall–吞吐曲线）。

11. 下一讲预告 · Next

RAG 让模型”读得更准”，靠的是只把相关的几段放进上下文。可有些应用的上下文本身就是无穷无尽的：一个持续几天的对话、一路流进来的日志。附加讲 A4 讲两件事：StreamingLLM——为什么只保留最近的窗口会让模型崩溃，而多保留开头的几个”注意力汇聚”token 就能稳定地生成几百万个 token；以及多模态 LLM——图像怎样变成 token（Flamingo 的重采样器与门控交叉注意力、LLaVA 的投影层），一张图要占多少 token 和 KV 缓存。