向量索引：精确搜索、HNSW 与 IVF
向量检索把问题和文档表示成向量，再找出与问题最接近的文档。语料变大后，每次都比较全部向量会越来越贵。近似最近邻搜索（Approximate Nearest Neighbor，ANN）减少比较次数，但可能漏掉本应进入前几名的向量。
嵌入、重排器与分类器解释向量从哪里来；检索流水线解释候选怎样变成证据。索引位于两者之间：它决定这次搜索会访问哪些向量。要判断索引是否值得用，先固定“接近”的含义，再比较它比精确搜索省了多少、漏了多少。
先固定度量和归一化
常见选择是欧氏距离（L2）、内积和余弦相似度。Faiss 的度量文档说明：L2 返回平方距离，越小越近；内积越大越相似，但没有归一化的内积并不等于余弦相似度。
对非零向量，余弦相似度只比较方向。把查询和库中向量都除以各自的长度后，内积就是余弦相似度；单位向量还满足：
因此，对单位向量，按 L2 从小到大排序与按内积从大到小排序等价。零向量无法这样归一化，应在进入索引前单独处理。
一个二维例子能看出度量怎样改变结果。设查询为 q = (1, 0)，比较下面两个向量；小数保留三位：
原始内积把 b 排在前面；余弦和这里的原始 L2 把 a 排在前面。先按嵌入模型的检索约定选择度量；归一化会去掉长度信息，不能把它当成对所有模型都无害的预处理。否则，即使索引完全找对了近邻，也可能找的是另一种“接近”。
精确搜索是基线
Faiss 索引文档把 IndexFlatL2 和 IndexFlatIP 列为穷举搜索：保存未压缩的向量，逐一比较，再选 top-k。这里的“精确”指在给定向量、度量和数值精度下找到真正的 top-k，不代表文档一定相关。
设库中有 N 个 d 维向量。一次朴素全扫描的距离计算量随 N × d 增长，选出 top-k 还需额外工作。例如，100 万个 768 维 float32 向量有 768,000,000 个坐标，仅向量本身就占 1,000,000 × 768 × 4 = 3,072,000,000 字节，即 3.072 GB（十进制）。一次查询要比较这些坐标；并发查询又增加总工作量。
批处理、向量化和加速硬件可以降低耗时，因此规模本身不足以决定要用 ANN。先测全扫描在目标硬件和查询负载下的延迟。数据较少、查询较少或必须保留全部近邻时，建复杂索引未必划算。
HNSW：沿多层图寻找近邻
HNSW 原始论文的第 4 节和算法 1、2、5 给出了构建与搜索过程。HNSW（Hierarchical Navigable Small World）把向量作为图节点：底层包含全部节点，越高层节点越稀疏。
插入时，新节点的最高层按指数衰减的概率随机选取。算法从已有图的顶层向下搜索，在新节点参与的层寻找候选、选择邻居并建立双向连接；已有节点连接过多时会裁剪。邻居选择启发式会考虑候选之间的距离，保留较多方向的连接，而不只是连接最近的一团节点。
查询从顶层入口开始，贪心地移动到更近的邻居，再把当前位置作为下一层的入口。底层会保留一组当前较好的结果，优先扩展近的待查节点；当最近的待查候选已比结果集合中最远的节点更远时，搜索停止。最终从已找到的节点中取 k 个，未访问的节点仍可能更近。
Faiss 的 HNSW 参数说明列出了三个控制不同成本的参数：M 控制连接规模；efConstruction 控制插入时保留的候选集合宽度；efSearch 控制查询时的宽度，应至少容纳 k 个结果。这些宽度不是实际距离计算次数。更大的构建预算可能改善图，更多查询探索通常提高召回，但不能给每个查询保证精确结果。
IVF：先选分区，再比较分区内的向量
IVF（Inverted File）把向量分配到 nlist 个倒排列表。Faiss 的分区搜索说明描述了常见的 L2 方案：用 k-means 得到中心，把每个向量放进最近中心的列表；查询先选出 nprobe 个列表，再扫描其中的向量。内积索引则按最大内积选择中心，不能直接套用 L2 的分区边界，见 Faiss 的内积聚类说明。
假如真正的近邻在未选中的列表里，它就不会进入候选。nprobe / nlist 只能粗略估计被扫描的比例，列表不等长时不能用它当实际工作量。增加 nprobe 会扩大候选范围，也增加扫描。
IndexIVFFlat 在选中的列表内仍使用未压缩向量计算距离，近似主要来自跳过列表。按 Faiss 的精度排查说明，设 nprobe = nlist 可扫描全部列表；使用精确的中心选择、相同度量和数值精度，且没有额外扫描上限时，IVFFlat 可恢复全扫描的结果（并列距离的顺序可能不同）。IndexIVFPQ 还用乘积量化（PQ）压缩向量，会再引入距离近似；只增加 nprobe 不能消除压缩误差。
一个漏掉边界近邻的完整例子
设有六个虚构的一维向量，查询为 q = 4，要找两个近邻。给定中心为 0 和 10：小于 5 的点归入列表 0，大于 5 的点归入列表 1；等于 5 时按较小的列表编号归入列表 0。中心是人为给定的，用来单独观察候选选择，不运行 k-means。
查询到两个中心的平方距离为 16 和 36，所以只查一个列表时选列表 0。精确 top-2 是 C、D；列表 0 中最好的两个却是 C、B。D 比 B 更近，但所在列表没被访问。
下面的 Python 3 程序只用标准库，完整执行分配、全扫描、分区扫描和召回计算。相同距离按 ID 排序，中心距离并列时按列表编号排序；本例的 top-2 边界没有并列。程序要求中心非空，k 为整数且满足 1 <= k <= len(points)，不满足时抛出 ValueError。
points = {"A": 0, "B": 1, "C": 3, "D": 6, "E": 8, "F": 10}
centers = [0, 10]
query, k = 4, 2
if not centers:
raise ValueError("centers must not be empty")
if type(k) is not int or not 1 <= k <= len(points):
raise ValueError("k must be an integer between 1 and len(points)")
def distance2(a, b):
return (a - b) ** 2
def rank(ids):
return sorted(ids, key=lambda i: (distance2(query, points[i]), i))
lists = {j: [] for j in range(len(centers))}
for i, x in points.items():
j = min(lists, key=lambda j: (distance2(x, centers[j]), j))
lists[j].append(i)
exact = rank(points)[:k]
print("lists:", lists)
print("distances:", [(i, distance2(query, points[i])) for i in rank(points)])
print("exact:", exact)
for nprobe in (1, 2):
selected = sorted(lists, key=lambda j: (distance2(query, centers[j]), j))[:nprobe]
candidates = [i for j in selected for i in lists[j]]
found = rank(candidates)[:k]
recall = len(set(found) & set(exact)) / k
print(f"nprobe={nprobe}: lists={selected}, scanned={len(candidates)}, "
f"found={found}, ANN recall@{k}={recall:.3f}")
输出：
lists: {0: ['A', 'B', 'C'], 1: ['D', 'E', 'F']}
distances: [('C', 1), ('D', 4), ('B', 9), ('A', 16), ('E', 16), ('F', 36)]
exact: ['C', 'D']
nprobe=1: lists=[0], scanned=3, found=['C', 'B'], ANN recall@2=0.500
nprobe=2: lists=[0, 1], scanned=6, found=['C', 'D'], ANN recall@2=1.000
只查一个列表，扫描的库向量从 6 个降到 3 个，找回一个精确近邻；查两个列表则找回两个。选择中心还需要两次距离计算，所以这个小例子分别需要 5 次和 8 次查询距离计算，全扫描只需 6 次。它说明遗漏的机制，不能据此推算真实索引的加速倍数。
建库、内存、更新和删除
索引把一部分查询工作提前到建库时完成。Faiss 的选型指南区分了无需训练的 Flat、HNSW，与需要先聚类的 IVF；聚类应使用有代表性的向量样本。下面比较未压缩向量的版本，内存按 Faiss 索引表所列存储项理解：
这些存储项不等于进程总内存：文档正文、元数据、分配器和查询临时空间还要另算。HNSW 和 IVF 也不互斥，IVF 可以用 HNSW 搜索中心。
删除与改写要查具体实现。Faiss 的特殊操作文档说明，Flat 删除后后续顺序编号会移动，IVF 存储显式 ID，删除不改变其他 ID。IVF 的按 ID 访问和更新涉及 DirectMap；Array 模式不支持删除，Hashtable 配合 IDSelectorArray 可避免删除时全库扫描。不要把文档 ID 直接绑定到可移动的顺序位置。
Faiss HNSW 不支持直接删除向量。若应用采用标记失效、过滤结果、定期重建，需把这些作为额外维护机制设计：过滤可能使返回结果不足 k 个，标记失效也不回收向量与图的存储。文本改写后，旧向量必须失效，新向量必须进入可搜索的索引；换嵌入模型或归一化约定时，库和查询应一起迁移。增量添加后，重新测召回和列表分布，判断是否需要重建。若要重新训练 IVF 中心，应训练新索引并重新分配全部有效向量；Faiss 不支持对已填入向量的索引直接重新训练。
对照精确近邻测量 ANN recall
对一个查询，令精确 top-k 的 ID 集合为 E，ANN 返回的 top-k 集合为 A，定义：
这对应 Faiss 的 IntersectionCriterion 实现中的集合交集式 R-recall@R，不要与同一文件中“第一近邻是否进入前 R 个结果”的 1-recall@R 混用。调参文档列出了这两种评测标准。这里假定 k 为正整数，且至少有 k 个合格向量；A 只包含实际返回的近邻 ID，结果不足时填充的 -1不算近邻。有距离并列时，应固定同一排序规则，或事先约定并列可接受的评分方式。
实际测量可以按以下顺序做：
- 固定语料快照、嵌入、归一化、度量、k 和过滤条件。精确基线在相同的合格语料上计算。
- 用贴近实际使用的查询计算精确 top-k，再运行 ANN，逐个查询计算交集召回，报告平均值并查看低召回查询。
- 保持索引不变，调整 HNSW 的
efSearch或 IVF 的nprobe，同时记录召回、延迟分布、吞吐量和内存。固定硬件、批量大小、并发量和缓存条件。 - 若加大查询预算仍达不到目标，检查图构建、中心训练、过滤方式和向量压缩；在独立查询集上确认调参后的表现。把建库时间、峰值内存和更新成本也纳入选择。
不要直接把搜索预算设成最大值：选择达到所需召回、又满足延迟和资源预算的设置。只有一个查询的 recall 为 1.0，不能说明整个语料上的搜索都是精确的。
近邻召回、证据相关性和答案正确性
三种判断需要不同参照：
即使 ANN recall 为 1.0，精确近邻也可能只是话题相似的旧说明。反过来，漏掉一个向量近邻时，另一个段落仍可能提供足够证据。检索与生成评测给出了后两类评测；重排只能调整已经进入候选池的段落。
使用 zvec-grep 这类语义搜索工具时，可以据此区分“索引没找到向量近邻”和“向量近邻没有回答问题”。具体工具采用哪种索引、暴露哪些参数，要看它自己的实现；仍需打开返回的源文件确认内容。