AI 工程基础体系 · 第 88/100 篇。内容覆盖机器学习、深度学习与生成式 AI；模型、数据、评测、权限和成本会作为同一生产系统处理。

向量 ANN 索引：HNSW、IVF、PQ、召回率、内存和构建成本

在 RAG（Retrieval-Augmented Generation）系统中，向量索引负责从候选文档中找到与查询向量相近的向量。它通常位于下面的数据流中：

flowchart LR
    Q[用户问题] --> E1[查询向量模型]
    E1 --> S[向量检索]
    S --> F[权限与元数据过滤]
    F --> R[可选精排/重排]
    R --> C[上下文拼接]
    C --> L[生成模型]
    D[文档] --> CH[切分]
    CH --> E2[文档向量模型]
    E2 --> I[ANN 索引]
    I --> S

RAG 论文将“检索器”和“生成器”组合起来：生成模型不必只依赖参数记忆，而是在生成时读取外部文档。向量 ANN（Approximate Nearest Neighbor，近似最近邻）索引解决的是检索器中的一个具体问题：在大量向量中，以低于穷举搜索的成本找到足够接近查询的候选。它不负责判断文本是否真实、是否有权限被用户读取，也不保证生成答案正确。

OpenAI 的 Retrieval 指南同样把向量存储、语义搜索、文件内容和过滤条件作为检索系统的一部分。生产系统应把嵌入模型、索引、元数据、权限、评测和生成模型视为一个整体，而不是只比较某个索引的 QPS。

1. 从精确最近邻到 ANN

设数据库中有 $N$ 个 $d$ 维向量：

$$X=\{x_1,x_2,\ldots,x_N\},\quad x_i\in\mathbb{R}^{d}$$

给定查询向量 $q$，距离函数为 $D(q,x)$。精确最近邻搜索返回距离最小的 $k$ 个向量：

$$\operatorname{TopK}(q)=\operatorname{arg\,topk}_{x_i\in X} -D(q,x_i)$$

如果使用余弦相似度：

$$\operatorname{cos}(q,x)= \frac{q\cdot x}{\|q\|\|x\|}$$

当所有向量都经过 L2 归一化时：

$$\|q\|=\|x\|=1$$

于是：

$$\|q-x\|_2^2 = \|q\|^2+\|x\|^2-2q\cdot x =2-2q\cdot x$$

因此，最大内积、最大余弦相似度和最小平方欧氏距离给出相同的排序。这个等价关系只在归一化条件成立时有效；如果向量未归一化，不能随意把内积检索改写成余弦检索。

精确搜索通常需要计算查询与所有 $N$ 个向量的距离，时间复杂度近似为：

$$O(Nd)$$

例如 $N=10^7$、$d=1536$ 时，即使单次距离计算很简单，也要处理约 153.6 亿个浮点乘加。ANN 的目标不是改变“相似度定义”，而是减少真正参与距离计算的向量数量，或使用压缩表示降低每次距离计算的成本。

1.1 “近似”究竟近似什么

ANN 通常近似的是搜索过程，而不一定近似向量本身：

• HNSW 使用图上的有限步搜索，可能没有访问真正的最近邻；
• IVF 只访问部分倒排列表，最近邻可能位于未访问的列表中；
• PQ 用码字近似原始向量，距离计算本身存在量化误差；
• IVF-PQ 同时有“候选分区遗漏”和“向量压缩误差”。

因此必须区分：

1. 精确 Top-$k$：以全库扫描结果作为真值；
2. ANN Top-$k$：索引返回的结果；
3. 召回率：ANN 结果包含多少精确结果；
4. 答案质量：生成答案是否使用了正确且足够的证据。

ANN 召回率高，不等于 RAG 答案一定正确；反过来，答案偶尔正确，也不能证明索引召回率高，因为生成模型可能凭参数记忆补全了缺失证据。

2. 召回率：必须先定义分母和评测层级

对一个查询，设精确搜索得到的 Top-$k$ 集合为 $G_k(q)$，ANN 返回的 Top-$k$ 集合为 $A_k(q)$。常用的 Recall@$k$ 为：

$$\operatorname{Recall@k}(q) = \frac{|A_k(q)\cap G_k(q)|}{k}$$

整个测试集上的召回率通常取所有查询的平均值：

$$\operatorname{Recall@k} = \frac{1}{|Q|} \sum_{q\in Q} \operatorname{Recall@k}(q)$$

例如，精确 Top-5 是：

$$G_5=\{a,b,c,d,e\}$$

ANN 返回：

$$A_5=\{a,c,e,x,y\}$$

交集为 $\{a,c,e\}$，因此：

$$\operatorname{Recall@5}=\frac{3}{5}=60\%$$

如果 ANN 返回 100 个候选，之后只把前 5 个交给重排器，则应分别报告：

• ANN 的 Recall@100；
• 重排后的 Recall@5；
• 最终上下文中是否包含标注证据；
• 端到端答案的正确率或引用准确率。

把“召回 100 个候选”和“最终返回 5 个结果”混为一个召回率，会掩盖重排器和过滤器的影响。

2.1 ANN 召回率不等于信息检索召回率

在实际 RAG 中，还存在文档级、段落级和证据级召回：

• 向量级召回：是否找到了精确 Top-$k$ 向量；
• 段落级召回：是否找到包含答案的 chunk；
• 文档级召回：是否找到正确文档；
• 证据级召回：返回的上下文是否足以支持答案。

如果一个长文档被切成多个 chunk，精确 Top-$k$ 只以向量距离定义“真值”，但业务标注可能认为同一文档的任意一个相关 chunk 都是正确结果。因此评测前必须定义等价集合，而不能盲目使用向量 ID 的集合交集。

2.2 召回率与延迟的关系

ANN 一般暴露一个搜索预算参数：

• HNSW 常见为 efSearch；
• IVF 常见为 nprobe；
• IVF-PQ 还可能有候选数、重构数或精排数；
• 不同实现的参数名称和默认值可能不同。

预算增大通常会访问更多节点、倒排列表或候选向量，因此召回率上升、延迟和 CPU 消耗也上升，但不保证线性或单调地改善 p99。缓存、线程调度、过滤选择性和数据分布都会影响实际结果。

正确做法是固定数据集、查询集、硬件、线程数和过滤条件，测量如下曲线：

$$(\text{Recall@k},\ p50,\ p95,\ p99,\ \text{QPS},\ \text{内存})$$

只报告“索引支持某个参数”而不测这条曲线，不能说明生产效果。

3. HNSW：把向量搜索转成图上的导航

HNSW（Hierarchical Navigable Small World）维护一个多层近邻图。每个向量是一个节点，边连接到若干其他向量；上层图节点较少、边较稀疏，下层图包含更多节点。搜索从高层的入口点开始，先快速接近查询区域，再在底层进行更细的搜索。

一个简化的搜索过程如下：

1. 从最高层入口节点开始；
2. 计算当前节点与查询的距离；
3. 如果某个邻居更近，就移动到该邻居；
4. 当前节点没有更近邻居时，下降一层；
5. 在底层维护一个候选集合，继续探索若干节点；
6. 返回距离最小的 $k$ 个节点。

上层的贪心导航减少了空间范围，底层的候选队列用于弥补单一路径可能走错的问题。

3.1 HNSW 的关键参数

不同库的参数命名可能不同，但含义通常接近：

• $M$：每个节点最多保留的邻接边数量；
• efConstruction：建图时维护的候选搜索宽度；
• efSearch：查询时维护的候选搜索宽度；
• k：最终返回数量。

efSearch 通常必须不小于 $k$，否则搜索候选空间可能小于最终需要的结果数。efConstruction 越大，建图时通常能找到质量更高的邻居，但构建时间和临时内存也会增加。增大 $M$ 会提高图的连通性和搜索质量，同时显著增加常驻内存。

这些是常见实现的行为，不是所有 HNSW 实现都保证完全相同的内存布局或参数语义。

3.2 HNSW 插入的状态变化

插入一个向量 $x$ 时，典型流程是：

1. 根据随机层级分布决定 $x$ 的最高层；
2. 从当前全局最高层入口开始；
3. 在高于 $x$ 最高层的层级执行较窄的贪心搜索；
4. 在 $x$ 所在的每一层执行宽度为 efConstruction 的搜索；
5. 选择若干候选节点与 $x$ 建立边；
6. 如果邻居节点的边数超限，执行邻居裁剪；
7. 更新入口点或最高层状态。

因此，HNSW 不是“先排序再建索引”，而是一个增量图构建过程。在线插入会修改多个已有节点的邻接表，常见实现需要处理锁、并发读写、删除标记和后台重建。

3.3 HNSW 的内存估算

原始向量使用 float32 时，向量本身约占：

$$M_{\text{vector}}\approx 4Nd$$

HNSW 还需要存储邻接边。若平均每个节点有 $L$ 条边，每个邻居 ID 使用 4 字节，则边索引的理论下界约为：

$$M_{\text{edge}}\approx 4NL$$

实际内存还包括：

• 多层图中的额外边；
• 邻接表长度和容量；
• 节点 ID、删除标记、层级信息；
• 内存对齐；
• 分片和运行时对象开销；
• 可能保留的原始向量、副本或量化向量。

例如，$N=10^7$、$d=1536$ 时，仅 float32 原始向量就约为：

$$10^7\times1536\times4 =61.44\text{ GB}$$

若每个节点平均存储 32 条 4 字节边，理论边 ID 还需要：

$$10^7\times32\times4 =1.28\text{ GB}$$

这不是完整 HNSW 内存，而是说明为什么 HNSW 往往比“只存一个压缩码”更占内存。实际部署必须用目标库的索引构建后内存或 RSS 测量校验公式。

3.4 HNSW 的优点与边界

HNSW 常见优势是：

• 不需要先训练聚类中心；
• 增量插入相对自然；
• 在内存充足时可以取得很好的延迟—召回率曲线；
• 对中等规模、低延迟检索很常见。

其边界包括：

• 高维大规模数据可能需要大量内存；
• 删除通常是逻辑删除，长期删除会造成“墓碑”节点和搜索浪费；
• 大量更新可能导致图质量和空间布局变化，最终需要重建；
• 过滤条件很严格时，图搜索访问到的很多节点可能都不满足过滤条件；
• 分片后全局 Top-$k$ 需要各分片返回候选，再进行合并，分片召回会影响全局召回。

一个重要反例是“图距离近但业务过滤不可用”：查询附近的 100 个节点中，99 个属于用户无权访问的租户。如果实现先做 ANN、再取前 10 个可见结果，而只请求 10 个 ANN 候选，那么最终可能不足 10 个结果；如果实现把过滤约束融入搜索，又可能因可见子图不连通而降低召回。

4. IVF：先分区，再只搜索部分分区

IVF（Inverted File，倒排文件）将向量空间划分为若干个簇。其核心组件是：

1. 粗量化器（coarse quantizer）：通常由 $K$ 个聚类中心组成；
2. 倒排列表（inverted lists）：每个中心对应一个列表，保存分配到该中心的向量 ID，以及可选的向量或压缩码；
3. 查询阶段的分区选择：先找离查询最近的若干中心，只扫描这些列表。

设聚类中心为：

$$C=\{c_1,\ldots,c_K\}$$

建库时，每个向量分配给最近中心：

$$a(x)=\operatorname{argmin}_{j\in[1,K]}D(x,c_j)$$

查询时，先计算 $q$ 到所有中心的距离，选出最近的 $nprobe$ 个中心。只有这些中心对应的列表会被扫描。

这里的 nlist 通常表示 $K$，nprobe 表示查询时访问的列表数量。与 HNSW 参数一样，名称和实现细节依赖具体库，但“分区数量”和“查询分区预算”是 IVF 的基本概念。

4.1 IVF 的完整小例子

考虑一维向量，数据库为：

$$X=\{0.1,0.2,0.3,4.8,5.0,5.2,9.8,10.0\}$$

设 nlist=3，训练得到粗中心：

$$c_1=0.2,\quad c_2=5.0,\quad c_3=9.9$$

查询 $q=5.1$ 时：

$$|q-c_1|=4.9,\quad |q-c_2|=0.1,\quad |q-c_3|=4.8$$

如果 nprobe=1，只扫描中心 $c_2$ 的列表：

$$\{4.8,5.0,5.2\}$$

此时精确最近邻也在该列表中，召回率可能为 100%。

但若查询 $q=7.4$，精确最近邻是 5.2 还是 9.8 要看全库距离：

$$|7.4-5.2|=2.2,\quad |7.4-9.8|=2.4$$

精确最近邻是 5.2，虽然查询更接近中心 $c_3=9.9$ 还是 $c_2=5.0$：

$$|7.4-5.0|=2.4,\quad |7.4-9.9|=2.5$$

此时 nprobe=1 选择 $c_2$，仍然找到 5.2；但对 $q=7.6$：

$$|7.6-5.2|=2.4,\quad |7.6-9.8|=2.2$$

精确最近邻变成 9.8，而查询到两个中心的距离为：

$$|7.6-5.0|=2.6,\quad |7.6-9.9|=2.3$$

这次也会选择 $c_3$。在更高维空间中，粗中心距离与真实最近邻的关系更不稳定：一个向量可能因为位于簇边界附近，被分到另一个中心；当 nprobe=1 时，真实邻居所在的列表可能直接不被访问。

把 nprobe 增大到 2，相当于访问两个最接近的簇，通常能减少边界遗漏，但会扫描更多向量。

4.2 IVF 的训练状态

IVF 的构建不是完全无状态的写入过程。典型生命周期为：

1. 收集代表性训练样本；
2. 用 K-means 或其他聚类方法训练 $K$ 个粗中心；
3. 固定或版本化粗量化器；
4. 将每个向量分配到倒排列表；
5. 查询时使用同一个粗量化器选择列表；
6. 新增数据按旧中心分配，或周期性重新训练并重建。

如果训练样本不能代表线上数据分布，簇会失衡：

• 某些列表过大，导致查询扫描成本高；
• 某些列表过小或为空，造成聚类中心浪费；
• 查询分布漂移后，原有中心不再适合；
• 新旧嵌入模型混用时，距离空间不一致，训练中心失效。

因此 IVF 的索引版本必须绑定嵌入模型版本、距离度量、归一化方式和训练数据分布。

5. PQ：用短码近似高维向量

PQ（Product Quantization，乘积量化）不是简单地把每个浮点数四舍五入为低精度，而是把向量拆成多个子空间，分别为每个子空间训练码本。

设原始向量维度为 $d$，拆成 $m$ 个子向量：

$$x=[x^{(1)},x^{(2)},\ldots,x^{(m)}]$$

若每个子向量维度为 $d/m$，每个子空间有 $2^b$ 个码字，则第 $j$ 个子空间有码本：

$$C^{(j)}=\{c^{(j)}_1,\ldots,c^{(j)}_{2^b}\}$$

量化后的向量由每个子空间最近的码字组成：

$$\hat{x} = [c^{(1)}_{i_1},\ldots,c^{(m)}_{i_m}]$$

每个子空间只需保存 $b$ 位索引，所以每个向量的编码大小为：

$$\frac{mb}{8}\text{ bytes}$$

例如：

• $d=128$；
• $m=16$；
• $b=8$。

则每个向量只需要：

$$16\times8/8=16\text{ bytes}$$

而 float32 原始向量需要：

$$128\times4=512\text{ bytes}$$

理论压缩比为 32 倍，但索引仍需存储 ID、列表结构、码本和可能的原始向量，因此实际压缩比会低于这个数。

5.1 PQ 的距离计算：ADC

以欧氏距离为例：

$$\|q-\hat{x}\|_2^2 = \sum_{j=1}^{m} \|q^{(j)}-c^{(j)}_{i_j}\|_2^2$$

查询时，先为每个子空间建立距离表：

$$T_j[i]=\|q^{(j)}-c^{(j)}_i\|_2^2$$

然后一个 PQ 编码 $(i_1,\ldots,i_m)$ 的近似距离只需查表并求和：

$$\tilde{D}(q,x)=\sum_{j=1}^{m}T_j[i_j]$$

这称为 ADC（Asymmetric Distance Computation）：查询 $q$ 保持原始精度，数据库向量使用 PQ 码。它避免了为每个候选完整重构向量再计算距离。

PQ 的误差来源是：

$$x=\hat{x}+\epsilon$$

其中 $\epsilon$ 是量化误差。误差越大，排序越可能改变。PQ 不是“内存压缩但召回率不变”；压缩码减少内存访问，却会改变距离近似。

5.2 残差 PQ 和 IVF-PQ

直接对原始向量做 PQ，子空间内的变化可能较大。IVF-PQ 通常先将向量分配到粗中心 $c$，再量化残差：

$$r=x-c$$

对 $r$ 做 PQ：

$$\hat{x}=c+\hat{r}$$

因为同一倒排列表中的向量通常围绕同一个中心，残差范围更小，PQ 更容易表示。查询时也可对：

$$q-c$$

与残差码进行近似距离计算。

IVF-PQ 的两个主要损失可以分开理解：

1. 粗分区损失：真实近邻所在的列表没有被 nprobe 访问；
2. 残差量化损失：访问了正确列表，但 PQ 近似距离排序错误。

增加 nprobe 主要缓解第一类损失；增加 PQ 码长度、优化码本或使用重排主要缓解第二类损失。只调 nprobe 不能修复严重的量化误差。

5.3 PQ 的反例

设查询为二维向量：

$$q=(0,0)$$

数据库中有：

$$x_1=(0.1,0.1),\quad x_2=(0.0,0.3)$$

真实欧氏距离为：

$$D(q,x_1)=\sqrt{0.02}\approx0.141$$

$$D(q,x_2)=0.3$$

所以 $x_1$ 更近。

如果 PQ 将第一维和第二维分别使用很粗的码本，使：

$$\hat{x}_1=(0,0),\quad \hat{x}_2=(0,0.25)$$

则：

$$D(q,\hat{x}_1)=0,\quad D(q,\hat{x}_2)=0.25$$

排序仍正确。但如果码本边界导致：

$$\hat{x}_1=(0.2,0.2),\quad \hat{x}_2=(0,0.25)$$

则：

$$D(q,\hat{x}_1)\approx0.283,\quad D(q,\hat{x}_2)=0.25$$

近似排序会把原本更远的 $x_2$ 排在前面。这说明 PQ 误差不是固定的缩放误差，而可能改变近邻次序，尤其影响距离非常接近的候选。

生产中常见的补救是：

1. 用 PQ 快速筛选较大的候选集；
2. 从存储中读取候选的原始向量或更高精度编码；
3. 用精确距离重新排序；
4. 只将重排后的 Top-$k$ 交给 RAG。

6. 一个可运行的 IVF 原理示例

下面代码只使用 NumPy，演示 IVF 的“训练中心、分配列表、选择 nprobe、局部扫描”过程。它没有实现 PQ，也没有处理并发、持久化或过滤，适合验证算法关系。

import numpy as np

rng = np.random.default_rng(7)

# 生成 3 个二维簇，每个簇 100 个向量
x = np.vstack([
    rng.normal(loc=(0.0, 0.0), scale=0.35, size=(100, 2)),
    rng.normal(loc=(5.0, 0.0), scale=0.35, size=(100, 2)),
    rng.normal(loc=(0.0, 5.0), scale=0.35, size=(100, 2)),
]).astype(np.float32)

# 一个测试查询
q = np.array([4.7, 0.2], dtype=np.float32)
k = 5
nlist = 3
nprobe = 1

def squared_l2(a, b):
    # 返回 a 的每一行到 b 的平方距离
    return np.sum((a - b) ** 2, axis=1)

# 为了让示例可复现，这里直接使用已知的粗中心。
# 真实系统中通常用 K-means 在训练样本上学习中心。
centers = np.array([
    [0.0, 0.0],
    [5.0, 0.0],
    [0.0, 5.0],
], dtype=np.float32)

# 建库：每个向量放入最近的倒排列表
assignments = np.array([
    np.argmin(squared_l2(centers, v))
    for v in x
])

lists = [[] for _ in range(nlist)]
for vector_id, list_id in enumerate(assignments):
    lists[list_id].append(vector_id)

# 精确搜索，作为评测真值
exact_dist = squared_l2(x, q)
exact_ids = np.argsort(exact_dist)[:k]

# IVF 查询：先找最近的 nprobe 个中心
center_dist = squared_l2(centers, q)
probe_lists = np.argsort(center_dist)[:nprobe]

candidate_ids = []
for list_id in probe_lists:
    candidate_ids.extend(lists[list_id])

# 只在被选中的列表中做精确距离计算
candidate_ids = np.asarray(candidate_ids, dtype=np.int64)
ivf_dist = squared_l2(x[candidate_ids], q)
order = np.argsort(ivf_dist)[:k]
ivf_ids = candidate_ids[order]

recall = len(set(exact_ids) & set(ivf_ids)) / k

print("selected lists:", probe_lists.tolist())
print("exact ids:", exact_ids.tolist())
print("ivf ids:", ivf_ids.tolist())
print(f"Recall@{k}: {recall:.2f}")

预期现象是 nprobe=1 只扫描一个簇；对于本例中的查询，该簇通常正好包含最近邻，因此召回率可能为 1.00。将查询改为两个簇之间的边界位置，或把 nprobe 改为 2，可以观察候选范围和召回率变化。

代码中的“先选列表、再扫描列表”是 IVF 的因果核心。即使列表内部使用精确距离，若最近邻所在列表没有被选中，也不可能找回该向量。相反，如果 nprobe=nlist，IVF 会扫描所有列表，候选召回率恢复为精确搜索，但失去分区带来的搜索加速。

7. HNSW、IVF、PQ 的组合关系

这三个术语不是同一层面的互斥选项：

• HNSW 是图索引；
• IVF 是空间分区和倒排结构；
• PQ 是向量编码和距离近似方法。

常见组合包括：

7.1 HNSW + 原始向量

图边用于缩小访问范围，候选距离用原始 float16 或 float32 向量计算。特点是距离精度高、构建逻辑直接，但内存通常较大。

7.2 IVF + 原始向量

先选少量倒排列表，再对列表中的原始向量做精确距离。PQ 误差不存在，但列表内扫描成本和向量内存仍然存在。

7.3 IVF-PQ

先通过 IVF 缩小候选范围，再用 PQ 码压缩向量并做 ADC。它通常适合内存受限的大规模库，但需要在 nprobe、码长和重排候选数之间调节。

7.4 IVF-PQ + 精确重排

流程为：

$$\text{粗分区} \rightarrow \text{PQ 扫描} \rightarrow \text{取较大候选集} \rightarrow \text{原始向量精确重排} \rightarrow \text{Top-}k$$

例如最终需要 Top-10，可以先用 PQ 取 Top-200，再读取这 200 个候选的原始向量重排。这样不能消除“正确列表未被访问”的损失，但可以减少 PQ 排序误差。

有些系统还会使用 HNSW 作为 IVF 的粗量化器或在每个分区内建立局部结构，但这属于具体实现的组合，不应把“HNSW、IVF、PQ”理解成一个固定算法。

8. 内存：不仅是向量字节数

估算索引内存时，至少要拆成以下部分：

$$M_{\text{total}} = M_{\text{vector/code}} + M_{\text{graph/list}} + M_{\text{codebook}} + M_{\text{metadata}} + M_{\text{runtime}}$$

8.1 原始向量

对于 $N$ 个 $d$ 维向量：

• float32：$4Nd$ 字节；
• float16：$2Nd$ 字节；
• int8：约 $Nd$ 字节，但需要考虑缩放参数和距离精度。

降低存储精度不等于自动保持检索质量。float16 往往比 PQ 更接近原始向量，但占用仍可能很大；int8 是否可行取决于嵌入分布、归一化和具体量化方法。

8.2 PQ 编码

PQ 码的理论大小为：

$$Nmb/8$$

若 m=96、每个子空间 8 bit，则每向量为 96 字节。还要加上：

• 向量 ID；
• 倒排列表偏移；
• 码本大小 $m\times2^b\times(d/m)$；
• 对齐和管理结构；
• 可能的残差中心或原始向量副本。

8.3 HNSW 图

HNSW 的内存通常受 $M$ 和层级边数影响。不能只用“每个节点 $M$ 条边”得到精确值，因为：

• 某些实现对底层允许的边数与上层不同；
• 边可能是有向存储；
• 邻接表可能预留容量；
• 节点可能出现在多层；
• ID 可能是 32 位或 64 位；
• 库可能额外存储标签映射。

因此公式适合做数量级估算，最终应在目标版本、目标数据量和目标参数下实测。

8.4 副本和峰值内存

构建时峰值内存经常高于上线后常驻内存：

• 训练 IVF 的样本和聚类临时数组；
• HNSW 构建时的候选队列；
• PQ 训练的码本和中间矩阵；
• 批量导入时同时存在原始数据、索引和待写入批次；
• 在线切换时新旧索引同时驻留；
• 多进程构建可能复制内存。

如果机器只按最终索引大小购买内存，构建阶段可能 OOM，或者触发交换导致构建时间急剧增加。

9. 构建成本：训练、分配、建图和重建

9.1 HNSW 构建成本

HNSW 的每次插入需要在图中搜索候选并更新邻接关系。简化地说，成本受以下因素影响：

• 向量数量 $N$；
• 维度 $d$；
• efConstruction；
• $M$；
• 距离函数；
• 并发写入方式；
• 是否需要保存原始向量。

它通常不是严格的简单 $O(N\log N)$ 保证，因为图搜索质量、数据分布和实现策略都会改变实际成本。efConstruction 增大通常提高图质量，但构建时间可能明显上升。

批量构建和逐条在线插入也不能直接等价：

• 批量导入便于控制线程、内存和索引切换；
• 在线插入可以降低新数据延迟，但会产生并发写入和图维护开销；
• 在大量数据导入后再构建，通常比一边导入一边高质量维护图更容易获得可预测的构建成本。

9.2 IVF 构建成本

IVF 至少包括两部分：

1. 训练粗量化器；
2. 将所有向量分配到最近中心。

若用 K-means，训练成本与训练样本数 $S$、簇数 $K$、维度 $d$ 和迭代次数 $T$ 相关，粗略可写为：

$$O(STKd)$$

实际通常只在采样数据上训练，而不是拿全部 $N$ 个向量反复训练。训练完成后，将 $N$ 个向量分配到中心，成本大致与 $NKd$ 相关；高效实现会使用批量矩阵运算或其他加速方法。

nlist 太小会使每个列表很大，查询扫描成本高；nlist 太大则会增加训练、中心存储和查询阶段的中心选择成本，并可能产生许多小列表。

9.3 PQ 构建成本

PQ 需要对每个子空间训练码本。若每个子空间有 $2^b$ 个码字，训练成本受样本数、子空间维度、码字数和迭代次数影响。b=8 意味着每个子空间有 256 个码字；增大 bit 数会增加码本训练和编码成本，也会增加存储大小。

IVF-PQ 的构建还要先训练粗量化器，再计算残差，再训练 PQ 码本，最后编码所有向量。因此它的构建流程通常比单独 IVF 更复杂，但上线常驻内存可能小得多。

9.4 增量更新和全量重建的取舍

索引更新可分为：

• 新增；
• 删除；
• 向量替换；
• 元数据变化；
• 嵌入模型变化；
• 分区或码本重训练。

如果文档内容变化但 ID 不变，不能只更新元数据而保留旧向量，否则检索结果与文本内容不一致。嵌入模型变化时，新旧向量通常不应混在同一索引中，因为它们未必处于同一个可比较空间。

常见的生产状态是：

1. 活跃索引接收查询；
2. 新数据进入增量区或新索引；
3. 后台构建下一版本；
4. 对新版本执行离线召回和权限测试；
5. 原子切换读流量；
6. 保留旧版本用于回滚；
7. 新版本稳定后回收旧版本。

切换期间如果没有双读验证或版本标记，可能出现“索引已经更新，但文档存储仍返回旧内容”的一致性问题。

10. 过滤、权限和分片会改变 ANN 结论

向量距离只表达语义相似度，不表达访问权限。设用户 $u$ 可访问的集合为：

$$V_u\subseteq X$$

正确的检索目标应是：

$$\operatorname{TopK}(q,V_u)$$

而不是先在全库求 $\operatorname{TopK}(q,X)$，再简单删除无权限结果。后过滤可能造成：

• 返回数量不足；
• 相关可见向量未进入初始候选；
• 不同租户之间的信息泄露风险；
• 召回率随租户规模和过滤选择性变化。

如果过滤字段能用于分区、位图或索引内约束，通常可以减少无效候选；但过滤过于稀疏时，HNSW 的邻接图可能在“可见节点”上不连通，IVF 的每个可见列表可能很小，系统需要增加候选预算或采用分区级索引。

分片检索也有类似问题。若数据分成 $s$ 个分片，每个分片只返回本地 Top-$k$，协调器再合并，那么全局 Top-$k$ 理论上可以从各分片的本地 Top-$k$ 中产生；但若每个分片内部使用 ANN 且本地召回不足，全局结果仍会丢失。为降低这个风险，可以：

• 提高每分片候选数；
• 使用分片级路由减少不相关分片；
• 监控按分片、租户和过滤条件拆分的召回率；
• 对热点租户或极小过滤集合使用专用索引。

11. 常见误解和失败表现

11.1 “把 efSearch 或 nprobe 调大就一定解决问题”

不一定。

• HNSW 的图本身如果构建质量差、数据删除过多或分片不合理，增大搜索宽度只能部分补救；
• IVF 的 nprobe 增大只能减少未访问列表造成的遗漏；
• PQ 的编码误差仍然会改变候选排序；
• 权限后过滤导致候选不足时，还需要增加初始候选数或改变过滤策略。

诊断时应分别测：

1. 不过滤、原始向量的 IVF 召回；
2. 加入 PQ 后的召回；
3. 加入过滤后的召回；
4. 加入重排后的召回。

这样才能知道损失发生在分区、量化还是权限阶段。

11.2 “压缩后内存越小越好”

过度压缩可能让语义相近的 chunk 排序不稳定，尤其在大量候选距离接近时。RAG 通常还需要考虑 chunk 的冗余、文档覆盖、重排器成本和生成上下文长度。较小的索引可以降低内存成本，却可能迫使系统取更多候选或依赖更贵的重排。

11.3 “ANN 召回率 99% 就代表系统可用”

还需要知道：

• 是 Recall@10 还是 Recall@100；
• 真值是否按向量级或文档级定义；
• 是否包含权限过滤；
• 查询是否覆盖长尾、拼写错误和多语言；
• 数据是否经过当前嵌入模型；
• p99 延迟和峰值并发是否满足要求；
• 召回结果是否真的包含回答所需的证据。

同一个 ANN 参数，在没有过滤的公开基准集上表现很好，到了多租户、强过滤和持续更新的 RAG 系统中可能完全不同。

12. 选择索引时的推理路径

可以按约束逐步判断，而不是先指定某个算法：

第一步：确定距离和向量空间

确认嵌入模型输出、是否归一化、使用余弦还是内积或欧氏距离。索引的训练和搜索必须使用一致的距离定义。

第二步：建立精确基线

在可承受的数据子集或离线评测集上执行精确搜索，保存 Top-$k$ 真值、距离和相关文档标注。没有真值，就无法判断 ANN 参数是否真的提高了召回。

第三步：判断主要瓶颈

• 如果内存足够、低延迟优先、更新较多，可先评估 HNSW；
• 如果数据规模大、可接受离线训练和批量构建，可评估 IVF；
• 如果原始向量内存成为主要成本，再评估 PQ 或 IVF-PQ；
• 如果 PQ 影响排序，可增加码长或采用候选重排，而不是只盲目增加 nprobe。

第四步：用业务约束重测

固定过滤条件、租户分布、并发和查询长度，分别测 Recall@$k$、p50/p95/p99、QPS、内存和构建耗时。索引参数是一个联合优化问题：

$$\max \operatorname{Recall@k}$$

约束为：

$$\text{p99 latency}\le L,\quad \text{memory}\le M,\quad \text{build time}\le B$$

其中 $L$、$M$、$B$ 是业务允许的延迟、内存和构建窗口。

13. 一个可操作的比较表

结构	主要机制	常驻内存	构建特征	召回损失来源	更新特征
HNSW	多层近邻图	通常较高	增量建图，受 efConstruction 影响	搜索预算、图质量、过滤和删除	增量较自然，长期维护可能需重建
IVF	粗量化分区 + 倒排列表	中等，取决于是否保留原向量	需要训练中心和分配向量	nprobe 未访问列表	可按旧中心增量写入，分布漂移需重训
PQ	子空间码本压缩	很低到中等	需要训练码本并编码	量化误差	更新需要重新编码
IVF-PQ	分区 + 残差 PQ	通常较低	粗量化和 PQ 训练均需完成	未访问列表 + PQ 误差	批量构建更容易控制，重训成本更高

表中的“通常”是工程经验，不是所有实现的规范保证。具体结果取决于数据分布、距离函数、库版本、硬件和参数。

14. 最终应如何解释一次 ANN 调优结果

一个可信的调优报告至少应包含：

• 嵌入模型及其版本；
• 向量维度、数据量和归一化方式；
• 距离函数；
• HNSW 的 $M$、efConstruction、efSearch，或 IVF 的 nlist、nprobe；
• PQ 的子空间数 $m$、bit 数 $b$、是否使用残差；
• 是否保留原始向量并重排；
• 过滤条件和权限执行位置；
• 精确真值的构造方式；
• Recall@$k$、延迟分位数、QPS、内存；
• 构建耗时、峰值内存和更新延迟。

例如，“将 IVF-PQ 的 nprobe 从 8 调到 32，Recall@10 从 91% 提升到 96%，p99 从 35 ms 增加到 72 ms；加入原始向量重排后 Recall@10 达到 98%，但候选读取和存储成本上升”比“调大参数后效果更好”有用得多，因为它明确指出了成本和收益发生在哪一层。

HNSW、IVF 和 PQ 的本质差异可以归纳为三种不同的近似方式：HNSW 限制图搜索路径，IVF 限制被访问的空间分区，PQ 限制向量表示和距离精度。召回率、内存和构建成本不是三个孤立指标，而是由这些近似位置共同决定的系统结果。只有以精确搜索为基线，并把过滤、更新、权限、重排和生成答案纳入评测，ANN 索引参数才有明确的工程含义。

---

系列导航与关联阅读

• 系列入口：AI 工程完整学习路线：从机器学习与 Transformer 到 RAG、Agent 和生产治理
• 上一篇：Embedding 模型选型：维度、语言、归一化、领域与评测
• 下一篇：混合检索：BM25、向量、过滤、融合排序和权重调优

官方资料

• Retrieval-Augmented Generation Paper
• OpenAI Retrieval Guide

本文依据研究论文、标准组织与主流框架官方文档重新梳理；正文、示例与工程清单由 WR BLOG 编写。