【干货】HNSW算法详解：从基础到进阶，掌握大模型向量搜索核心技术！
简介
本文详细介绍了HNSW算法，一种用于高维空间中最近邻搜索的高效索引方法。文章从基础概念开始，逐步解释了可导航图和NSW算法的工作原理、构建与搜索过程，以及其局限性。随后介绍了跳表数据结构，并详细阐述了HNSW的多层级构建和搜索机制。通过比较HNSW与NSW的搜索效率，展示了HNSW在减少跳数和提高搜索准确性方面的优势，为在大模型应用中实现高效的向量相似性搜索提供了技术基础。
HNSW（Hierarchical Navigable Small World）可能是专为高维空间中的最近邻搜索而设计的最有效、最高效的索引方法之一。其核心思想是构建一个图结构，其中每个节点代表一个数据向量，边根据节点的相似性进行连接。HNSW 以这样一种方式组织图表，通过有效地浏览图表来找到近似的最近邻居，从而促进快速搜索操作。但在我们理解 HNSW 之前，必须先理解NSW（可导航小世界算法），它是 HNSW 算法的基础。
什么是可导航图
如果我们将这些向量表示为图的顶点，则彼此靠近的顶点（即相似度高的向量）应该作为邻居连接。也就是说，即使两个节点没有直接连接，也应该可以通过遍历其他顶点到达它们。这意味着我们必须创建一个可导航的图（Navigable Graph）。更正式地说，为了使图可导航，每个顶点都必须有邻居；否则，就无法到达某些顶点。
此外，虽然拥有邻居有利于遍历，但同时，我们希望避免每个节点都有太多邻居的情况。理想情况下，我们希望有一个类似于小世界网络的可导航图，其中每个顶点只有有限数量的连接，并且两个随机选择的顶点之间的平均边遍历次数较低。
这种类型的图表对于大型数据集中的相似性搜索非常有效。
如果这一点清楚了，我们就能理解可导航小世界（Navigable Small World，NSW）算法是如何工作的。
这在搜索期间的内存、存储和计算复杂性方面可能会造成很大的成本。
NSW
NSW的构建
NSW 的第一步是图的构建，我们称之为G。这是通过随机打乱向量并以随机顺序插入顶点来构建图形来完成**的。**当向图G中添加新顶点V时，它会与图G中距离它最近的K 个现有顶点共享一条边。为了演示方便，这里假设 K=3。首先，我们插入第一个顶点A。由于此时图中没有其他顶点，因此A保持未连接状态。
接下来，我们添加顶点B，并将其连接到A ，因为A是唯一存在的顶点，并且无论如何它都会位于最接近的K个顶点之一。现在该图有两个顶点{A, B}。
接下来，当顶点C被插入时，它会同时连接到A和B。对于顶点，同样的过程也会发生D。
现在，当顶点E插入图中时，它仅连接到最近的K=3个顶点，在本例中是A、B和D。
这个顺序插入过程持续进行，逐步构建 NSW 图。好消息是，随着越来越多的顶点被添加，在图构建的早期阶段形成的连接可能会成为更长距离的链接，这使得通过很少的跳跃即可导航长距离。
一直在更新，更多的大模型学习和面试资料已经上传带到ZEEKLOG的官方了，有需要的朋友可以扫描下方二维码免费领取【保证100%免费】👇👇
NSW的搜索
在上面构建的NSW图G中，搜索过程采用简单的贪婪搜索方法进行，该方法在每一步都依赖于局部信息。假设我们想要找到下图中黄色节点的最近邻居：
为了开始搜索，会随机选择一个入口点，这也是该算法的精妙之处。换句话说，NSW 的一个关键优势在于可以从图中的任何顶点发起搜索G。假设我们选择节点A作为入口点：
在选定初始点之后，算法会迭代地寻找距离查询向量Q最近的邻居（即连通的顶点）。例如，在本例中，顶点A有邻居B,C,D,E。因此，我们将计算这些邻居与查询向量Q的距离（或相似度，无论你选择什么作为度量标准）。在这种情况下，节点C最近，因此我们从节点A移动到节点C。
节点C的未评估邻居仅为H，其结果更接近查询向量，因此我们现在移动到节点 H。
重复此过程，直到找不到更接近查询向量的邻居，这为我们提供了图中查询向量的最近邻居。基于 NSW 的搜索仍然是近似的，不能保证我们总能找到最近的邻居，并且它可能会返回非常次优的结果。
NSW的局限性
例如，考虑下面的图，其中节点A是入口点，黄色节点是我们需要最近邻的向量：
按照上述最近邻搜索的程序，我们将评估节点A的邻居: B和 C。显然，两个节点都比节点A距离查询向量更远。因此，该算法返回节点A作为最终的最近邻居。这个结果举例最优解显然还有很明显的距离。
为了避免这种情况，建议使用多个入口点重复搜索过程，这当然会消耗更多时间。
跳表（Skip List）
跳表的基本原理
在理解 HNSW 之前，我们需要先理解一下跳表（Skip List）
跳过列表，即跳表，是一种数据结构，可以高效地搜索已排序列表中的元素。它类似于链表，但增加了一层“跳过指针”，从而可以更快地遍历。
链表如下所示：
在跳过列表中，每个元素（或节点）包含一个值和一组前向指针，可以“跳过”列表中的多个元素。
这些前向指针在列表内创建了多个层，例如上图的 Layer 0， Layer 1， Layer 2。每个级别代表不同的“跳过距离”。一般情况下，使用概率方法决定每层必须保留的节点。基本思想是，节点以递减的概率包含在较高层中，从而导致较高级别的节点较少，而底层始终包含所有节点。更具体地说，在构建跳过列表之前，每个节点都会被随机分配一个整数L，该整数表示该节点在跳过列表数据结构中可以存在的最大层数。具体操作如下：
uniform(0,1)生成 0 到 1 之间的随机数。floor()将结果向下舍入为最接近的整数。
是一个层乘数常数，用于调整层之间的重叠。增加此参数会导致更多重叠。例如，如果一个节点的 L=2，这意味着它必须存在于 Layer 0， Layer 1， Layer 2中。
跳表举例
现在，让我解释一下跳过列表如何加速搜索过程。假设我们想在这个列表中找到元素50。
如果我们使用典型的链表，我们将从第一个元素开始，然后逐个扫描每个节点以查看并检查它是否与50匹配。看看跳过列表如何帮助我们优化这个搜索过程。我们从顶层Layer 2开始，检查同一层中下一个节点对应的值，即65。
由于65>50, 它是一个单向链表，我们必须向下一级Layer 1进行查询，我们检查同一层中下一个节点对应的值，即36。
由于50>36和，移动到与值36相对应的节点是明智的。现在再次在Layer 1中检查同一层中下一个节点对应的值，即65。
由于65>50, 它是一个单向链表，我们必须向下一级。我们到达了Layer 0，可以按照平常的方式跳跃。如果我们在不构建跳跃表的情况下遍历链表，我们就会进行5跳跃：
但是使用跳过列表，我们可以在3跳跃中完成相同的搜索：
虽然在这个例子中，将跳数从减少5到3听起来可能不是一个很大的改进，但值得注意的是典型的矢量数据库有数百万个节点。因此，此类改进可以快速扩展并带来运行时优势。
HNSW
同样的，我们使用随机算法构建多层级的HNFW，一般情况下，先使用 与 NSW相同的构图算法构建 Layer 0，然后以一定的概率丢掉一些节点，得到 Layer 1，类似的，可以得到Layer 2, Layer 3等。为了方便我们以图例进行解释。假设我们通过这个步骤得到了以下HNSW 图：
让我们了解近似最近邻搜索的工作原理。假设我们想要找到下图中黄色向量的最近邻：
我们从顶层的入口点开始搜索Layer 2：
我们探索A的连通邻居，看看哪个节点与黄色节点最近。在这一层中，最近的节点是C。该算法贪婪地探索一层中顶点的邻域。在此过程中，我们始终朝着查询向量移动。当在某一层中找不到更接近查询向量的节点时，我们移动到下一层，同时将最近邻居（在本例中为C）视为下一层的入口点：
邻域探索的过程再次重复。我们探索C 的邻居并贪婪地移动到最接近查询向量的特定邻居：
同样，由于在Layer 1 中不存在更接近查询向量的节点，我们移动到下一层，同时将最近邻居（在本例中为F）视为下一层的入口点。但这次，我们达到了Layer 0。因此，在这种情况下将返回近似最近邻。当我们移至Layer 0并开始探索其邻域时，我们注意到它没有更接近查询向量的邻居：
因此，与节点 F 对应的向量作为近似最近邻返回，巧合的是，这也恰好是真正的最近邻。
HNSW 和 NSW的比较
在上述搜索过程中，仅经过2跳数即可返回查询向量的最近邻居。
让我们看看找到 NSW 的最近邻需要多少跳。为了简单起见，我们假设由 NSW 构建的图就是HNSW Layer 0 所表示的图：
我们之前以节点A作为入口点， 为了方便对比，我们也在这里同样选择 A。我们从节点A开始，探索其邻居，然后移动到E最接近查询向量的节点：
从节点E，我们移动到节点B，它比节点E更接近查询向量。
接下来，我们探索节点B的邻居，并注意到节点I最接近查询向量，因此我们现在跳到该节点：
由于节点I无法找到与其相连且比自身更近的任何其他节点，因此该算法返回该节点I作为最近邻居。
该算法不仅需要更多跳数（这里是 3）来返回最近邻，而且还返回了不太理想的最近邻。
相比之下，HNSW 经过的跳数更少，并返回了更准确、更优化的最近邻。
如何系统的学习大模型 AI ？
由于新岗位的生产效率，要优于被取代岗位的生产效率，所以实际上整个社会的生产效率是提升的。
但是具体到个人，只能说是：
“最先掌握AI的人，将会比较晚掌握AI的人有竞争优势”。
这句话，放在计算机、互联网、移动互联网的开局时期，都是一样的道理。
我在一线互联网企业工作十余年里，指导过不少同行后辈。帮助很多人得到了学习和成长。
我意识到有很多经验和知识值得分享给大家，也可以通过我们的能力和经验解答大家在人工智能学习中的很多困惑，所以在工作繁忙的情况下还是坚持各种整理和分享。但苦于知识传播途径有限，很多互联网行业朋友无法获得正确的资料得到学习提升，故此将并将重要的AI大模型资料包括AI大模型入门学习思维导图、精品AI大模型学习书籍手册、视频教程、实战学习等录播视频免费分享出来。
一直在更新，更多的大模型学习和面试资料已经上传带到ZEEKLOG的官方了，有需要的朋友可以扫描下方二维码免费领取【保证100%免费】👇👇
01.大模型风口已至：月薪30K+的AI岗正在批量诞生
2025年大模型应用呈现爆发式增长，根据工信部最新数据：
国内大模型相关岗位缺口达47万
初级工程师平均薪资28K（数据来源：BOSS直聘报告）
70%企业存在"能用模型不会调优"的痛点
真实案例：某二本机械专业学员，通过4个月系统学习，成功拿到某AI医疗公司大模型优化岗offer，薪资直接翻3倍！
02.大模型 AI 学习和面试资料
1️⃣ 提示词工程：把ChatGPT从玩具变成生产工具
2️⃣ RAG系统：让大模型精准输出行业知识
3️⃣ 智能体开发：用AutoGPT打造24小时数字员工
📦熬了三个大夜整理的《AI进化工具包》送你：
✔️ 大厂内部LLM落地手册（含58个真实案例）
✔️ 提示词设计模板库（覆盖12大应用场景）
✔️ 私藏学习路径图（0基础到项目实战仅需90天）
第一阶段（10天）：初阶应用
该阶段让大家对大模型 AI有一个最前沿的认识，对大模型 AI 的理解超过 95% 的人，可以在相关讨论时发表高级、不跟风、又接地气的见解，别人只会和 AI 聊天，而你能调教 AI，并能用代码将大模型和业务衔接。
- 大模型 AI 能干什么？
- 大模型是怎样获得「智能」的？
- 用好 AI 的核心心法
- 大模型应用业务架构
- 大模型应用技术架构
- 代码示例：向 GPT-3.5 灌入新知识
- 提示工程的意义和核心思想
- Prompt 典型构成
- 指令调优方法论
- 思维链和思维树
- Prompt 攻击和防范
- …
第二阶段（30天）：高阶应用
该阶段我们正式进入大模型 AI 进阶实战学习，学会构造私有知识库，扩展 AI 的能力。快速开发一个完整的基于 agent 对话机器人。掌握功能最强的大模型开发框架，抓住最新的技术进展，适合 Python 和 JavaScript 程序员。
- 为什么要做 RAG
- 搭建一个简单的 ChatPDF
- 检索的基础概念
- 什么是向量表示（Embeddings）
- 向量数据库与向量检索
- 基于向量检索的 RAG
- 搭建 RAG 系统的扩展知识
- 混合检索与 RAG-Fusion 简介
- 向量模型本地部署
- …
第三阶段（30天）：模型训练
恭喜你，如果学到这里，你基本可以找到一份大模型 AI相关的工作，自己也能训练 GPT 了！通过微调，训练自己的垂直大模型，能独立训练开源多模态大模型，掌握更多技术方案。
到此为止，大概2个月的时间。你已经成为了一名“AI小子”。那么你还想往下探索吗？
- 为什么要做 RAG
- 什么是模型
- 什么是模型训练
- 求解器 & 损失函数简介
- 小实验2：手写一个简单的神经网络并训练它
- 什么是训练/预训练/微调/轻量化微调
- Transformer结构简介
- 轻量化微调
- 实验数据集的构建
- …
第四阶段（20天）：商业闭环
对全球大模型从性能、吞吐量、成本等方面有一定的认知，可以在云端和本地等多种环境下部署大模型，找到适合自己的项目/创业方向，做一名被 AI 武装的产品经理。
- 硬件选型
- 带你了解全球大模型
- 使用国产大模型服务
- 搭建 OpenAI 代理
- 热身：基于阿里云 PAI 部署 Stable Diffusion
- 在本地计算机运行大模型
- 大模型的私有化部署
- 基于 vLLM 部署大模型
- 案例：如何优雅地在阿里云私有部署开源大模型
- 部署一套开源 LLM 项目
- 内容安全
- 互联网信息服务算法备案
- …
学习是一个过程，只要学习就会有挑战。天道酬勤，你越努力，就会成为越优秀的自己。
如果你能在15天内完成所有的任务，那你堪称天才。然而，如果你能完成 60-70% 的内容，你就已经开始具备成为一名大模型 AI 的正确特征了。
