RAG 向量检索： Embedding 和 HNSW

在有序数组中找一个整数，二分查找很自然；但如果数据要频繁插入、删除，维护连续数组就不再轻松。跳表给出了一种很实用的折中：底层保留完整的有序链表，上层只保留越来越稀疏的“快速通道”。查找时先在高层大步移动，再逐层下降到精确位置。

这个思路并不只属于整数查找。RAG 的向量检索同样需要避免逐个比较全部向量。HNSW（Hierarchical Navigable Small World）把“分层快速定位”的直觉扩展到了高维空间，不过每一层不再是有序链表，而是由相似向量连接成的图。另一条常见路线 IVFFLAT 则先把向量聚成多个桶，仅在少量桶内搜索。

本文先说明 Embedding 如何把内容映射到向量空间、向量怎样计算相似度，再以一份可运行的 Java 跳表实现建立分层索引的直觉，最后拆解 HNSW 的构建与检索过程、它与跳表的边界，以及 HNSW 与 IVFFLAT 的工程选择。

1. Embedding：把内容变成可计算的语义坐标

Embedding 是模型为文本、图片或其他对象生成的一组浮点数。它不是把词典编号拼在一起，而是在训练中学习一个连续向量空间：语义或任务相关性相近的输入，向量通常更接近；不相关的输入通常更远。

例如，文本 如何申请退款 与 订单退货流程 的字面词并不完全相同，但一个合适的文本 Embedding 模型会尝试把它们映射到相近的位置。向量本身没有可直接解释的“第 37 维代表退款”这类固定含义；语义来自所有维度共同形成的位置关系。

原始内容
  ├─ 文档 Chunk："订单退货流程"
  └─ 用户问题："如何申请退款"
          ↓ 同一个 Embedding 模型
高维向量空间中的两个点
          ↓ 距离或相似度计算
候选上下文与问题的相关程度

1.1 Embedding 怎么训练

训练并不是为每段文本手工标注一个坐标。模型先用语言建模、对比学习或它们的组合学习文本表示；面向检索时，常见目标是让“查询—相关文档”对更近，让“查询—无关文档”对更远。

一批训练样本可以概括为三元组：查询 q、相关文档 d+、负样本 d-。模型分别生成向量 e(q)、e(d+) 与 e(d-)，优化目标会推动下式成立：

similarity(e(q), e(d+)) > similarity(e(q), e(d-))

负样本的质量很关键。随机选一段完全无关的文本通常太容易；检索训练常加入“难负样本”——表面相似、却不真正回答问题的文本——逼迫模型学会更细的区分。实际模型还可能用点击日志、问答对、同义改写、跨语言对齐和人工标注数据继续微调。

这也说明了 RAG 中的一个边界：向量相近并不等价于事实正确。Embedding 优化的是相关性信号，不负责验证文档是否过期、结论是否可靠，也不能替代权限判断。

1.2 向量到底怎么比

向量检索不是比较每一维是否相等，而是根据一个度量计算两点的接近程度。设查询向量为 q = (q₁, …, qₙ)，文档向量为 d = (d₁, …, dₙ)，常见选择如下。

若向量都做了 L2 归一化，即 ||q|| = ||d|| = 1，余弦相似度与内积的排序等价：cos(q, d) = q · d。这不是说两种 API 返回值一定相同，而是对同一批归一化向量，按它们排序会得到相同顺序。

选择度量要服从 Embedding 模型的训练方式与官方建议；建立索引、查询和重排必须使用兼容的度量。以余弦距离建立的索引，却以不兼容的运算符查询，会使结果语义或索引命中出现偏差。

1.3 RAG 场景如何选择 Embedding 模型

这里的“选型”不应简化成在公开排行榜上选择总分最高的模型。RAG 的第一阶段是非对称检索：短查询要从大量、长度和写法各异的 Chunk 中找出相关内容。因此，优先看与自身语言、领域和检索任务匹配的结果，而不是把分类、聚类或语义相似度的总分直接当作检索能力。

可以按下面的顺序收敛候选模型。

公开基准可用于筛掉明显不适合的候选。MTEB 将 Retrieval 单独定义为“查询集合与语料集合之间的非对称匹配”，并提供按任务、语言和领域查看结果的机制；它适合做第一轮参考，但不是业务验收。MTEB 的任务说明也明确了检索评测由语料、查询及其相关性映射组成。

最终选择必须落到自己的评测集。先准备一批真实或人工审核的 query -> 相关 Chunk 对，固定相同的切分策略、Top-K、过滤条件与距离度量；再让候选模型在同一套语料上生成向量，比较 Recall@K、MRR、nDCG、p95 延迟、单次调用成本和向量存储量。若后续会使用 Reranker，也应在完整链路上比较“最终进入上下文的片段质量”，而不只比较第一阶段的向量召回。

公开 Retrieval 基准：筛选候选
        ↓
真实 query - Chunk 标注集：比较召回和排序
        ↓
相同 HNSW / IVFFLAT 参数：比较延迟、内存与成本
        ↓
完整 RAG 链路：验证最终上下文与答案质量

部署方式也需要纳入判断。托管 Embedding API 省去推理服务和扩缩容工作，但会受网络延迟、数据合规和计费模型约束；自部署开源模型更便于数据留在内网，也可以针对领域继续微调，但需要承担 GPU、模型服务、版本发布和容量规划。无论选择哪一类，文档向量与查询向量都必须来自同一模型版本和同一编码配置。切换模型、维度或归一化方式时，旧向量不能与新查询向量混用；稳妥做法是重建索引，或在迁移期并行保留两套向量与索引。

2. 从全量扫描开始：为什么需要索引

假设有一百万个文档向量，用户的问题也被 Embedding 模型转换为向量。最直接的办法是：依次计算查询向量与每个文档向量的距离，取距离最小的 Top-K。

这叫精确最近邻（Exact Nearest Neighbor，ENN）。它不会漏掉真正最近的结果，但每次查询都必须扫描全部数据。向量维度通常为数百到数千维，数据量和并发上来后，计算量、延迟与成本都会迅速增长。

近似最近邻（Approximate Nearest Neighbor，ANN）接受一个明确的工程取舍：不保证每次都返回全局绝对最近的点，而是用可控的召回损失，换取大幅减少比较次数。HNSW 与 IVFFLAT 都属于这一类索引。

无索引：查询向量 ──逐个比较──> 全部 N 个向量

有 ANN 索引：查询向量 ──定位候选区域──> 少量候选向量 ──精排──> Top-K

跳表要解决的问题更简单：在可排序的一维整数中快速找到目标。但它的“先粗定位、再细化”的过程，正是理解 HNSW 的好起点。

3. 跳表：在有序链表之上增加快速通道

给定输入 92 728 2 928 624，最底层必须保存完整有序序列：

Level 0: HEAD -> 2 -> 92 -> 624 -> 728 -> 928 -> null

如果只有这一层，查找 928 必须从头依次经过前面的节点。跳表让一部分节点随机“晋升”到更高层；越高层节点越少。固定随机种子为 42 的示例中，2 可能出现在多层：

Level 3: HEAD -----------------> 2
Level 2: HEAD -----------------> 2
Level 1: HEAD -----------------> 2
Level 0: HEAD -> 2 -> 92 -> 624 -> 728 -> 928

上图不是节点间多了几份数据，而是同一个节点在不同层拥有不同的向前指针。高层不是完整索引，只负责跨过一段低层节点，帮助搜索更快地接近目标区域。

2.1 节点与层高

示例中每个节点保存一个值和一个 forward 指针数组：

static class Node {
    private final int value;
    private final Node[] forward;

    Node(int value, int level) {
        this.value = value;
        this.forward = new Node[level + 1];
    }
}

节点层高由 randomLevel() 决定：初始为第 0 层，每次以 0.5 的概率继续向上一层，直到失败或达到 MAX_LEVEL。因此节点出现在更高层的概率指数递减。绝大多数节点只在底层，少数节点形成稀疏的导航骨架。

随机不是为了“碰运气找得快”，而是为了以较低维护成本得到近似平衡的分层结构。和严格平衡树不同，跳表插入时通常不需要旋转或重构大量节点。

2.2 查找：向右，或向下

查找从当前最高层的 HEAD 开始。只要下一节点严格小于目标值，就在当前层向右；下一节点大于等于目标、或已经到达末尾时，下降一层：

for (int level = currentLevel; level >= 0; level--) {
    while (current.forward[level] != null
            && current.forward[level].value < target) {
        current = current.forward[level];
    }
}

Node candidate = current.forward[0];
boolean found = candidate != null && candidate.value == target;

找 2 时，高层的下一个节点正好是 2。判断条件是“小于目标”，所以算法不向右越过它，而是连续下降，最后在第 0 层检查候选节点：

第 3 层：HEAD 的下一个节点是 2，停止向右，下降
第 2 层：HEAD 的下一个节点是 2，停止向右，下降
第 1 层：HEAD 的下一个节点是 2，停止向右，下降
第 0 层：候选节点为 2，命中目标

这里的精确判断依赖一个关键前提：每层都按值有序。因此“下一个节点已经不小于目标”足以说明继续向右不会更好。

2.3 插入：先记录前驱，再重连指针

插入 624 时，算法也先从高层向下走。每一层把待插入位置之前的最后一个节点记录在 update[level] 中；随后为新节点分配随机层高，并在存在的各层重连指针。

插入前：92 ----------------> 728
插入后：92 -> 624 -> 728

对应的两个赋值顺序不能颠倒：先让新节点接住原后继，再让前驱指向新节点。

newNode.forward[level] = update[level].forward[level];
update[level].forward[level] = newNode;

在概率分布稳定、参数合理的前提下，跳表插入与查找的期望时间复杂度通常为 O(log n)；底层完整链表和上层指针会带来额外空间。它不保证单次操作的最坏情况始终是对数级，但实现简洁、并发版本也相对容易设计，使其在工程中很常见。

4. 从跳表到 HNSW：哪些直觉可以复用

HNSW 的名字里有三个要点：Hierarchical（分层）、Navigable（可导航）与 Small World（小世界）。它的层级思想与跳表相似：节点随机分配最高层，越往上节点越稀疏；检索从最高层开始，逐层下降。

跳表：每层是按数值排序的链表
HNSW：每层是按向量相似性连接的邻接图

共同点：高层粗定位，低层细搜索，节点数量随层数升高而减少

把 HNSW 想成城市道路网络会更直观：顶层像少量高速路入口，适合跨区域接近目标；低层像密集街道，适合在局部区域寻找真正邻居。类比的边界也很重要：HNSW 并没有一条“值小于目标就继续向右”的总排序关系。高维向量空间没有天然的一维单调方向，图上的每一步都要按距离度量选择更接近查询向量的邻居。

5. HNSW 如何构建与检索

5.1 构建：为新向量找到邻居并建立双向连接

插入一个新向量时，HNSW 会为它随机分配最高层。若它的层高超过现有入口点，便成为新的全局入口；否则从当前入口开始，先在新节点不存在的高层做贪心导航，找到更接近新向量的起点。然后逐层下降，在新节点会出现的各层搜索候选邻居，并建立受限数量的双向连接。

新向量 v 到达
  -> 随机分配最高层 lv
  -> 从全局入口在更高层贪心导航
  -> 下降到 lv，在候选范围内搜索近邻
  -> 按选择策略保留最多 M 条边，并建立反向边
  -> 某个旧节点超出连接上限时，裁剪较不合适的边
  -> 逐层下降至第 0 层，完成插入

构建时的搜索范围通常由 ef_construction 控制。它不是最终要连多少条边，而是为了选择好邻居，构建过程愿意保留和探索多少候选。随后，选择策略会从候选中挑出至多 m 个邻居；成熟实现通常不只取距离最近的若干点，还会保留分布更分散的连接，避免图只在一个局部过密、难以跨区域导航。

这比跳表的“只修改前驱和后继”复杂得多。跳表的一层是线性有序链表，插入位置唯一；HNSW 的一层是图，新增节点要选择哪些边留下，直接影响后续检索的可达性、内存占用与召回率。构建顺序也会影响图的具体形状，因此评估索引时应基于固定数据集和参数测量整体指标，而不是观察单个节点的边。

5.2 检索：先贪心下降，再扩大候选集

查询时，HNSW 从顶部入口开始，在当前层反复移动到距离查询向量更近的邻居；当该层再也不能改进时，带着当前位置下降一层。到第 0 层后，不再只保留一个当前节点，而是在受限候选集中继续扩展与比较，最终返回 Top-K。

第 L 层：从入口贪心走到一个更近的区域
   ↓
第 L-1 层：以该位置为起点继续缩小范围
   ↓
第 0 层：扩展候选集，按距离返回 Top-K

这种机制解释了 HNSW 的“近似”属性：图的连接有限、搜索候选集也有限，算法可能未遍历到真正全局最近的节点。不过通过参数增加候选范围，可以提升召回率，同时增加延迟和资源消耗。

5.3 三个常见参数

不同向量库的默认值与名称可能不同，但 HNSW 的调优通常围绕以下三类参数：

• m：单个节点最多保留多少连接。更大通常意味着图更稠密、召回潜力更高，同时索引占用更多内存。
• ef_construction：建索引时为选择邻居保留的候选范围。更大通常改善图质量，但构建更慢。
• ef_search：查询时探索的候选范围。更大通常提高召回率，但会提高查询延迟；它往往是最适合在线评测和调整的参数。

参数不是单独越大越好。应固定 Embedding 模型、距离度量、Top-K 和过滤条件，用业务标注问题分别测量召回率、p95/p99 延迟、内存与最终答案质量，再选择满足目标的组合。

6. IVFFLAT：先分桶，再在桶内精确比较

IVFFLAT（Inverted File Flat）采用另一种缩小候选集的方式。建索引时先用聚类把向量空间划分为 lists 个中心；每个向量被放进与其最近中心对应的倒排桶。查询时先找离查询向量最近的若干桶（probes），仅在这些桶内进行原始向量距离计算。

建索引：所有向量 -> 聚类中心 -> 多个倒排桶

查询：查询向量 -> 选择最近的 probes 个桶 -> 桶内逐个比较 -> Top-K

它的 Flat 表示桶内保留原始向量并做精确距离计算，而非对向量进行乘积量化压缩。近似性来自“只查部分桶”，不是桶内距离计算本身。

lists 决定桶的数量：太少时每个桶很大，查询接近全表扫描；太多时聚类与管理成本增大，且只探测少量桶容易漏召回。probes 决定查询多少个桶：提高它通常能提高召回率，但会让更多向量进入比较。

IVFFLAT 需要先训练聚类中心；当数据分布发生明显变化时，既有中心可能不再能代表数据，索引需要评估是否重建。这与 HNSW 可持续增量插入但需关注图结构和内存健康，形成不同的运维侧重点。

7. HNSW 与 IVFFLAT：不是谁绝对更好

如果业务优先追求低延迟与较高召回，并且内存预算充足，HNSW 往往是优先验证的方案。如果更在意内存、构建速度，且可以接受通过 lists、probes 持续调节召回，IVFFLAT 值得评估。

这个结论不是规模阈值的机械规则。向量维度、Embedding 分布、Top-K、并发、硬件、索引实现、写入模式和元数据过滤都会改变结果。正确的选型方式是把 Flat 精确搜索作为基线，在同一批评测查询上比较候选索引的召回率、延迟和成本。

8. RAG 中常被忽略的三个约束

7.1 距离度量与索引必须匹配

常见度量包括余弦距离、内积和欧氏距离。文本语义检索经常使用余弦距离，因为它关注向量方向；若模型输出已归一化，内积与余弦在排序上通常等价。无论选择哪一种，查询使用的距离度量必须与索引构建时支持的度量一致，否则可能得到不符合预期的排序或无法使用索引。

7.2 过滤条件会改变候选集

RAG 很少只做“最相似的 10 个片段”。实际查询常有租户、权限、文档版本或分类过滤。ANN 索引先得到有限候选、再应用严格过滤时，最后可能不足 Top-K。应通过执行计划和评测确认真实行为，并考虑增大候选范围、按常用条件建立针对性索引，或调整检索流程。

7.3 索引无法弥补上游语义质量

索引只决定如何更快地接近向量空间里的邻居。文档切分不合理、Embedding 模型不适配、查询向量质量差时，即使 ANN 的召回率很高，返回的也可能不是用户真正需要的上下文。检索评测应同时看向量召回、重排效果和最终回答质量。

看完本文后能够回答的问题

• Embedding 如何在训练中把查询和相关文档拉近、与负样本推远？
• 余弦相似度、内积和欧氏距离分别在比较什么？
• 跳表为什么能在不维护严格平衡树的情况下加速有序查找？
• Java 示例中的 update 数组为什么必须记录每层前驱节点？
• HNSW 与跳表共享哪些分层直觉，又为什么不能把它们看成同一种数据结构？
• m、ef_construction、ef_search 分别影响 HNSW 的什么成本与质量？
• HNSW 插入一个新向量时，为什么要搜索候选、建立反向边并裁剪连接？
• IVFFLAT 的 lists、probes 如何控制搜索范围？
• 在 RAG 中，为什么不能只凭“数据量大小”决定选择 HNSW 或 IVFFLAT？

总结

跳表通过随机分层，让查找先走稀疏的快速通道、再回到底层确认；HNSW 将相同的分层导航思想用于高维向量图，但它依据距离选择邻居，而不是利用一维有序关系。IVFFLAT 则通过聚类把全局问题缩成少量桶内比较。

三者背后都是同一个工程目标：避免每次查询从头比较全部数据。跳表依赖排序，HNSW 依赖图的可导航性，IVFFLAT 依赖聚类的局部性。理解这些前提，才能把“索引很快”的泛化印象转化为可验证的召回、延迟、内存与运维决策。

参考资料

• 万字详解 RAG 向量索引算法和向量数据库
• Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
• MTEB Retrieval tasks