LLM, RAG 背后的支持技术

免费体验阿里云高性能向量检索服务：https://www.aliyun.com/product/ai/dashvector

本文主要说明了向量相似性搜索的必要性、经典的ANN算法、当前业界的解决方案，和前沿的ANN算法。

1 为什么需要向量相似性搜索？

1.1 向量数据的来源

为了使计算机能够理解和处理非结构化数据（如文本，图片，视频），通常使用嵌入模型(Embedding)将非结构化数据编码为向量，可以理解为，向量就是非结构化数据的压缩。因此，在对非结构化数据进行相似性搜索、最近邻搜索(NNS, Nearest Neighbor Search)时，可以使用向量的近似度来表征非结构化数据的语意近似度。

一个常见的向量相似性的度量是，欧式距离（向量空间中两点之间的直线距离）。另外，其他常见的向量相似性的度量还有余弦相似度、点积。

1.2 向量相似性搜索应用场景

有哪些应用场景需要对向量进行相似性搜索？

通常可以用于推荐系统，信息检索等领域。例如，在推荐系统中，通过计算商品图片及文本信息的相似性，可以实现相似商品的推荐； 在自然语言处理中，通过计算word embeddings 之间的相似性，可以实现文本相似性比较、情感分析等任务。

另外，向量数据还可以作为大型语言模型 (LLM) 的知识库，使用检索增强生成（RAG, Retrieval Augmented Generation）为 LLM 提供训练数据之外信息，以及更多私域知识；在无需重新训练 LLM 模型的前提下缓解其幻觉问题。

1.3 向量索引，为什么使用近似的最近邻搜索 (ANN)？

有了向量相似度的定义之后，我们如何快速搜索找到相似的非结构化数据呢？

现有的向量的相似性搜索研究更加关注 ANN (Approximate Nearest Neighbor) 近似最近邻搜索算法。各种 ANN 方法将构建高维向量的索引结构，通过牺牲精度（即搜索结果的召回率Recall）来提高查找效率。

2 向量相似性搜索的4类算法

现有的ANN算法主要可以分为四种类型：基于树的算法；基于哈希的算法；基于量化的算法；以及基于图的算法。最近的研究以 graph-based 为主。

2.1 Tree-based (KD-tree, R-tree)

核心思想：通过构建一个树状的数据结构，将向量按照某种规则进行划分和组织，从而实现对向量的高效检索。

KD-tree

KD-tree，即针对 K dimension 的树结构，递归地将K维空间切分为两个子空间。

• 索引构建
  根节点开始递归地构建KD-Tree，每个节点都代表了一个K维空间的超矩形区域。非叶节点存储切分维度和切分点的信息，而叶节点存储点的数据。递归地将K维空间切分为两个子空间（即树的两个节点），直到满足特定的终止条件，如节点中的向量数小于某个阈值。在每一步切分时，它选择一个切分维度和一个切分点；例如，选择方差最大的维度作为切分维度，选择该维度上的中位数点作为切分点。
  

• 查询
  从根节点开始，递归地向下搜索，直到找到包含查询点的叶节点。然后，算法回溯到父节点，检查另一侧的子树是否有更近的点。
• 优势和局限

• 优势：KD-Tree在处理低维数据（如二维、三维空间中的点）时非常有效。
• 局限：随着维度的增加，KD-Tree的效率会因为“维度的诅咒”而显著降低。这使得KD-Tree在高维数据上的性能不如一些专门为高维设计的算法，如基于哈希的方法（LSH）或基于图的方法（如HNSW）。
  

R-tree

R-tree，即表矩形 (rectangle) 区域的树结构。R-tree将空间划分成嵌套的矩形区域，以便于快速查询；每个节点代表了一个“矩形”区域，这个区域可能包含更小的矩形区域（子节点）或实际的空间对象（即向量）。

• 索引构建
  对于每个要插入的空间对象，从根节点开始，递归地向下搜索树，以找到最适合插入新对象的叶节点。这个选择基于最小化区域扩张的原则，即选择这个插入操作会导致其边界矩形扩张最小的节点。如果某个节点因为插入新对象而超出容量，就需要将该节点分裂成两个节点。分裂策略旨在最小化重叠区域、边界矩形的面积以及平衡树的深度。分裂可以递归向上进行，直到根节点。
  

• 查询
  从根节点开始，算法选择与查询 query 距离最近的矩形区域进行进一步搜索，直到达到叶节点。
• 优势和局限

• 优势：R-tree通过空间划分和层次结构，使得范围查询和最近邻搜索变得非常高效。R-tree支持插入和删除操作，适用于动态变化的空间数据集。
• 局限：随着维度的增加，R-tree的性能会下降，因为矩形重叠会降低查询性能。虽然R-tree支持动态更新，但频繁的插入和删除可能会导致树的结构失衡，需要通过复杂的重构操作来优化。
  

2.2 Hash-based (LSH)

LSH 局部敏感哈希

LSH是一种用于高维向量数据的哈希技术，旨在在保持相似性的同时，将相似的数据映射到相同的哈希桶（bucket）中，以支持高效的近似搜索。

• 索引构建

LSH 使用多个哈希函数（hash function）来生成多个哈希值，然后将向量映射到由这些哈希值组成的多维空间中。

LSH 原理示意图

• 查询
  查询向量，query vector，被哈希到特定的哈希桶中，然后与同一桶中的其他向量进行比较以找到最接近的匹配。 这种方法比搜索整个数据集要快得多，因为查询时只在少量的桶中搜索，这比整个空间中的向量少得多。
• 优势和局限

• 优势：索引构建快、查询结果准确性的有理论保证。
• 局限：（1）近似查找的质量取决于哈希函数的特性。哈希函数数量越多，近似查找的质量越高；但大量哈希函数增加了计算开销，同时不适用于大数据集。（2）哈希边界问题、哈希冲突。

2.3 Quantization-based (PQ, IVF-PQ)

PQ

乘积量化(Product Quantization，PQ) 将高维空间中的向量分割成若干个子向量（子空间），然后对每个子向量独立进行量化。这样做既可以显著减少存储空间，又能快速计算向量之间的相似性。

1. 向量分割：首先，将每个高维向量分割成B(B=4)个子向量。假设原始向量的维度为D(256维)，那么每个子向量的维度为D/B(64维)。这样，原始的高维空间就被划分成了B个子空间。
2. 量化：在每个子空间中，独立地对子向量进行量化。量化的过程是指将连续的向量空间映射到有限的码本（codebook）上。每个码本由K个中心（或称为码字）组成，这些中心是通过某种聚类算法（如K-means）在训练阶段从数据中学习得到的。因此，每个子向量都被映射到其所在子空间的某个中心上，这个过程相当于对子向量进行了近似表示。
3. 编码：量化之后，每个子向量的信息就被一个小的索引（通常是中心的索引）所代表。因此，原始的高维向量就可以通过B个索引来表示，例如图中第一行被量化后的向量：[23, 47, 176, 98]，这显著减少了存储需求。

IVF-PQ

IVF PQ（Inverted File Product Quantization）结合了倒排索引（Inverted File）和乘积量化（Product Quantization, PQ）的技术，旨在提高大规模高维数据。

• 索引构建

1. 聚类：使用K-means等聚类算法在数据集上找到V个聚类中心，这些中心构成了倒排索引的“词汇表”。
2. 倒排索引构建：根据每个数据向量与聚类中心的距离，将数据向量分配到最近的聚类中心，形成V个子集。每个子集对应倒排索引中的一个条目。
3. 乘积量化：在每个子集内部，进一步使用乘积量化技术对数据向量进行压缩，以减少存储需求并加速距离计算。

• 查询

5. 查询向量量化：将查询向量按照同样的方法分配到最近的聚类中心。
6. 候选子集选择：选择多个与查询向量最近的聚类中心对应的子集作为候选集。
7. 在候选集中搜索：使用乘积量化的方法计算查询向量与候选集中数据向量的距离，找出最相似的向量。

• 优势和局限
• 优势：（1）通过将数据集划分为较小的子集，IVF PQ显著减少了需要直接比较的数据量，从而提高了查询效率。（2）乘积量化在子集内部保持较高的近似精度，使得整体搜索结果更加准确。
• 局限：聚类中心的数量、乘积量化的细粒度等参数的选择会显著影响索引的构建和查询性能，需要仔细调优。

2.4 Graph-based（基础图搜索算法，HNSW）

基础图搜索算法

在各种类型的ANN方法中，实验结果表明在常见的欧式空间中，基于图的方法显示出了更好的搜索性能。这因为，LSH和PQ等方法不能像基于图的方法一样较好地表达邻居关系。基于图的索引算法核心思想是：构建向量的近似邻近图（Approximate Proximity Graph）；然后通过greedy-search去查找邻居向量。

• 索引构建
  图中的顶点对应原始数据集的点，通过评估点之间的距离将接近的两点进行连边。图的构建基于几个经典的图：DG (Delaunay Graph), RNG (Relative Neighborhood Graph), KNNG (K-Nearest Neighbor Graph), MST (Minimum Spanning Tree)。
• 查询

尽管这些基于图的方法有非常不同的索引结构，但它们的搜索算法是非常相似的。

（1）在每一步中，优先队列中距离查询点最近的点被选中（如优先队列长度为 L=3，从点 A开始搜索）。

（2）然后，访问所有与其相连的邻居（如A的邻居是 B, D, H），并计算它们到查询点的确切距离。如果找到更靠近查询的点（如点H, D），则更新优先队列。

（3）当没有新的点可以加入优先队列时，搜索终止。最后，返回优先队列。

• 优势和局限

• 优势：查询效率以及查询的准确率较高。
• 局限：（1）邻近图的构建较为耗时。（2）图难以更新，难以增删向量数据点。

HNSW

HNSW（Hierarchical Navigable Small World）借鉴了1维跳跃列表的思想，在NSW的图方法的基础上进行了分层化。

• 索引构建

通过在逐个插入数据点时限制元素邻居数量，构建分层的图索引结构。分层的图结构具体来说，是在上层图中维护更长的边，而在下层图中维护更短的边。底层包含所有的数据点。

在构建HNSW分层结构时，为了选择邻近(proximity graph)图的连接，作者使用了一种启发式方法考虑了候选元素之间的距离来创建多样化的连接，而不仅仅是选择最近的邻居。具体来说，该启发式方法从距离插入元素最近的候选元素开始搜索，并仅在候选元素比已连接的任何候选元素更接近插入元素时才创建连接。

• 查询
  在搜索过程中，首先从顶层的入口点(entry point)进入，在每一层中都像在NSW方法一样遍历边和邻居，移动到与查询最相似的邻居，并切换到下一层。重复这个过程，直到找到底层（layer=0）的局部最小值。图中的红色箭头展示了从顶层入口点到绿色查询点的搜索方向。
• 优势：

（1）HNSW算法能够在大规模高维数据集中实现快速的近似最近邻搜索，特别是在搜索效率和准确度之间保持了良好的平衡。

（2）HNSW支持动态添加数据点，这使得它非常适合于数据不断更新的场景。

• 局限：

（1）为了实现高效的搜索性能，HNSW构建的图结构可能会占用较多的内存。

（2）有实验表明，当数据维度大于32维时，HNSW分层结构的优势会发生退化。

3 向量的内存索引与磁盘索引

上述提到的ANN算法都是基于内存的，因此，对数据集的大小仍有限制。

DiskANN

为了解决内存存储索引对数据集大小的限制，提出DiskANN，将全精度向量存储在磁盘上，将使用PQ压缩后的向量缓存在内存。

DiskANN 在单个工作站上使用64GB RAM和固态硬盘实现了索引、存储billion-scale的数据库。DiskANN构建的索引满足大规模ANN的多方面要求：高召回率、低查询延迟和高密度（每个节点索引的点数）。在高召回率的情况下，与基于图的方法如HNSW 和NSG 相比，DiskANN在每个节点上可以索引5-10倍的数据量。

Spann

SPANN使用倒排索引和内外存来支持Billion-scale ANN；使用层次化聚类算法，在内存中存放聚类中心点，在外存中存放向量。SPTAG是微软亚洲研究院（Microsoft Research Asia，MSRA）于2019年开源的一个项目，并应用于Bing中。

了解更多阿里云向量检索服务DashVector的使用方法，请点击：

https://help.aliyun.com/product/2510217.html?spm=a2c4g.2510217.0.0.54fe155eLs1wkT