概述：本文是对 WhalePaper 向量检索领域第一次直播活动内容的文字版，会对向量检索这个 ChatGPT 和 new bing 都离不开的技术进行介绍，结合了 ChatGPT 以及 new bing 的应用场景进行讲解，相信被标题骗进来的你还真能有所收获的（手动狗头）！本期内容入门友好，对课件进行了一些注解，图文结合在一起全是干货，长文预警！

脉络

本次分享的主题是：基于图索引的多向量检索及其GPU加速。

主讲人：浙江大学在读博士王梦召。

将从以下几个方面进行:

背景介绍：包含 ChatGPT 的工作原理，向量检索的发展现状，什么是向量索引。

多向量检索：会介绍什么是多向量，为什么需要多向量检索，如何进行多向量检索。

如何通过GPU加速图索引的多向量检索：这部分内容讲解了如何基于图索引进行多向量检索，如何用GPU来加速图索引搜索。

对未来的思考：主要说明了一些王博士未来研究的一个方向。

背景介绍

我们每个人每天都会接触大量的非结构化数据，比如视频、语音、文本等等，根据IDC（国际数据公司）的统计，当前我们世界上所有的数据中有百分之八十是非结构化数据。目前主流的处理非结构化数据的方式是通过深度神经网络把非结构化数据转变为高维的稠密向量，再对这些向量进行分析处理。那么这些跟 ChatGPT 和 new bing 有什么关系呢？先来简单介绍一下这两者的工作方式。

ChatGPT 直接根据用户提供的上文，直接生成回应。那这个是怎么生成的呢？是靠用户给出上文提示，它才能返回下文。但是自然语言的上下文，机器并不能看懂，所以要把自然语言编码为向量的形式，回复时同样是把向量解码为一段文字。

new bing 是先用 bing 搜索找到一些参考，然后使用 GPT 模型进行归纳总结。整体工作流程分为两个部分。首先是检索，就是根据用户的搜索，先找到可靠的依赖信息。之后就是归纳总结，把搜索来的知识（网页信息）归纳为一段精炼的文字。这个过程就类似向量检索，根据 query（查询的向量）把相似向量检索到，然后使用这些向量完成下游任务，例如：归纳总结，推荐。

从两者的工作原理可以看出向量数据的重要性，AI应用离不开向量数据，而只要在搜索过程中涉及到对向量的处理，便离不开向量检索。那么什么是向量检索？

什么是向量检索?

还记得中学时期计算向量间的距离吗？这其实就是向量检索的本质。还是举个例子帮助我们更好的理解。

上图为一个二维空间，里面存放着由非结构化数据转变成的向量，我们给定一个查询（图中小绿点），即我们要搜索的事物，然后把查询也转变成向量，通过计算向量间的距离，将距离最小的几个向量（连线小红点）作为结果返回，即召回离它最近的一些结果，这就是一个比较简单的向量检索的过程。

向量检索的分类

向量检索的索引技术可以分为四个流派，分别是Tree（树索引）、Hashing（哈希索引）、Quantization（量化索引）和PG（图索引），四种方法各有各的优势。其中基于图的这种方式在效率和精度上有一个比较好的均衡，所以目前受到了大家更多的关注，也是我们这次分享的重点，后面会具体进行说明。

对另外三种索引方式感兴趣的朋友可以自行上网搜索，或者关注我们整理的相关论文：Unstructured-Data-Community/ANN-Papers，有已经根据分类整理好的技术论文供大家阅读，帮助大家节省搜寻的时间。

多向量检索

什么是多向量

这个问题比较简单，顾名思义，就是多个向量。我们以描述一个书本为例。

一本书里面每一章都包含数字、符号、文字、表格或图片，其中的数字和符号就是标量，文字、表格和图片就是向量，每一章的内容都由很多的向量及标量构成，而整本书由数个章节构成，则是所有向量的集合。所以说我们利用多个向量来描述真实世界中的事物是比较靠谱的。

这一点在人脸中格外直观。人脸是一个立体的图形，一个人的脸就需要不同角度的照片进行描述，将不同角度的照片中的信息编码成向量之后就可以更好地描述这个人的脸部信息，也就是前面提到的更好地描述一个现实世界的事物。这些也点出了我们为什么需要多向量检索。

为什么我们需要多向量检索

又是一个例子（爱板栗星人狂喜）。

大家应该都用过以图搜图的功能，假设现在有个用户想要搜出一张在夜晚且图中没有人的埃菲尔铁塔图片，但是他手头只有一张白天且人很多的埃菲尔铁塔图片作为原图。如果他用传统的搜索引擎以图搜图的方式去搜索，肯定会搜出与原图相似的图片，但是有可能没法满足他的要求。这个时候，多向量检索就派上用场了。

所谓多向量检索，就是可以用多个向量去检索一个向量，其中，用于检索的多个向量可以是不同形式的。在上述场景中，该用户就可以用“无人且转变成晚上”这句话来描述他所需要更改的信息，多向量检索技术就将这句话编码成文字向量，原图编码成图片向量，结合两个向量一起去检索，得出和他描述的最近似的图片。

从上述的例子可以看出，多向量检索可以让用户更好地表达自己的意图，从而提高搜索系统的可用性和准确性。

下面所展示的电商检索场景也是一个道理。

现在我们在搜索商品的时候，更多还是一个文字描述，并且最后算法推荐的结果还不一定可以满足我们的需要。假如我们可以在搜索出来的结果上再进行一次筛选，那么范围就会进一步缩小，不仅更接近我们的需要，而且还可以节约时间。

相信你已经猜出来我要说什么了，没错，我们可以在第一次检索的基础上再提供一些文字描述，利用多向量检索进行多次筛选，通过输入的文字和召回的结果这两个信息去迭代，不断地优化检索的结果，最终获取我们想要的商品。

怎么进行多向量检索

说了这么一串向量有好使，也该介绍一些怎么进行多向量检索了。

目前主要有两个解决方案，一个是分离，另一个是联合。

分离方案是指每种模态的信息都给独立转变成向量，然后独立执行向量搜索，最后将每种信息检索结果进行合并。

联合方案是指把多种信息通过一个融合模型联合成一个向量，然后通过当前这个单独的向量去检索。

分离的方案在DB社区用的比较多一些，主要的挑战在检索过程中；联合的方案在CV领域用的比较多，主要的挑战在如何利用模型将不同模态的信息放进一个向量中。但是不管那种方案，都是需要一个向量检索的过程的。

基于图索引的多向量检索及其GPU加速

讲了半天，终于到主菜了。在讲GPU加速之前，我们要如何用我们前面提到的基于图（PG）索引的方式来执行多向量检索呢？

基于图索引进行多向量检索

首先，他需要根据向量之间的相似性对向量的集合建立一个图索引，也就是将向量汇集在一个图层中。之后在给定一个查询时，会在这个图层下随机或固定生成一个入口点（图中黑色点），去不断地访问点附近的邻居（1234点），计算邻居与这个查询向量的距离，然后选择离查询点最近的邻居向量（图中4）的邻居向量计算和查询向量的距离，选取最近的点，不断地重复以上的过程，迭代得到和查询点最近的向量集合，最后获取召回过程。

在这个过程中，有两个比较关键的操作，一个是向量距离的计算，还有一个是计算机对向量搜索过程中数据结构的维护。数据结构包含三个，

结果集：用于放查询召回的结果，也就是当前搜索到的邻居中距离目前最近的点；

候选集：用于存放检索过程中当前的一个邻居搜索结果，也就是即将和查询向量进行距离计算的点的集合，是动态变化的；

访问记录：用于存放已经访问过的点，以防重复地计算同一个向量。

这个过程比较复杂，具体展示一下加强理解。

上图中我们要召回和黑点 q 近似的结果，一共会召回四个结果，也就是离 q 最近的结果。我们将 v1 这个点作为入口进入，首先把入口点 v1 放入候选集 C 和访问记录 H 中，进行初始化；然后我们到向量点的集合中找到和 v1 点连线的点，也就是 v1 的邻居 v2、v3、v5、v7、v8 放入 C和 H中来和 q 进行距离计算，并进行距离长度的对比，将最近的点 v8 从 C 中删除并放进结果集 N ，然后将 v8 的邻居 v7、v10 放进 C 中，进行新一轮的计算，因为其他点的距离在第一轮已经计算过，所以此时只计算 q 与 v10 之间的距离，并与之前计算过的其他点的距离进行比较，得出结果 v10 后，将 v10 从C中删除放入 N ，如此循环，N 中有了4个点后有新的点要进来还需要对比 N 中的点和新点的谁的距离更近，把最近的4个放进去，远的抛弃，直到遍历完所有点都没法找出比 N 中的点更近的点了就结束这个迭代的过程。

这个过程总结起来就是三步，

候选定位：从 C 里面定位一个点；

距离计算：计算这个点的邻居和查询点的距离；

更新三个集：根据计算结果迭代三个集中的内容。

其中距离计算是占用的时间最多，几乎占了90%的查询时间，所以我们就要考虑如何利用 GPU 这个并行能力去加速具体计算的过程。

GPU加速图索引搜索

GPU 加速的核心就是并行运算。

还是图索引那个例子，现在我们在原有的基础上进行优化，用一个线程来维护三个数据结构。图中左下角是GPU的内存层次结构，使用 GPU 进行加速的搜索过程中，会把这三个结构放到线程的局部内存当中，便于维护上述的候选定位以及更新三个集的操作。

图中右下角就是图索引的例子，在使用GPU加速之前，是直接计算一对向量的距离，但是在GPU加速的情况下，我们会将一个向量分成很多子向量，然后每个线程进行单独的距离计算，最后再合并起来。

这样就可以实现并行计算，大大节省距离计算需要消耗的时间，在数据结构维护的操作消耗时间不变的情况下，让距离计算的时间从原先的占比90%降低到10%。

GPU 并行计算的这个特点除了加速距离计算过程之外，还可以加速数据结构维护的操作。

这里补充两个概念方便后续的理解，

访问点：一个点如果已经被访问了，也就是这个点已经和查询的点进行过距离计算了，称为访问点；

探索点：一个点如果已经被探索了，也就是这个点的邻居已经和查询的点进行过距离计算了，称为探索点。

GPU 加速过后的图索引与传统的图索引最大的区别就在于数据结构的不同，由于 GPU 并行计算的快速性，删去历史记录结构虽然会有一些少量的重复计算过程，但是反而为节约数据结构维护上的时间开销带来很大的收益，但是如果不对探索点进行一个记录，可能会陷入到一个恶性循环，也就是会不停地访问一个点相同的邻居。所以 GPU 采用了一个 Lazy Check 的策略，删除了历史记录结构，允许一些冗余计算的存在，但是又不会陷入恶性循环，后面会具体说明 Lazy Check 的原理。

我们来一起看一下 GPU 删去历史记录结构后的数据结构维护过程。

GPU 的两个数据结构分别是合集 N 和合集 T。其中，合集 N 用于储存当前计算出最近的结果，集合 T 用于存放即将计算向量距离的邻居，两者都存放在 GPU 的线程当中。

首先，在线程块里面有很多线程，通过多线程并行的方式去探测当前还没有被探测过的点，比如下图中，在集合 N 定位到第一个没被探索过的顶点 v 。

接着，在全局内存把 v 的邻居读取到集合 T 当中，集合 N 和集合 T 都在一个线程块的共享内存里。

现在我们要开始计算向量间的距离，需要去全局内存将这个邻居的原始向量读取进来，用和前面提到的一样的方式，将一个向量拆解成多个子向量进行距离计算后再合并。

计算完向量间的距离，我们进行一个Lazy Check的操作，也就是利用并行二分搜索将集合 T 里面的每一个点和集合 N 里的点进行对比，来看看有哪些点是已经被探测过的，如果已经被探测过了就会被做一个特殊的标记，被标记的点就不会再进行计算了。也就是说 Lazy Check允许多次计算的存在，但是不允许计算陷入循环。

接下来，通过双调排序的方法针对合集 T 中没被标记的点进行一个并行排序。依旧是利用双调排序，将合集 T 中的有序序列合并到合集 N 当中。

对未来的思考

这个部分主要是王博士基于这个技术对于未来工作方向上的思考。

首先，目前 PG（图索引）在向量搜索的时候还没有理论保证，所以在这一方面做一个探索是比较值得的。

其次，刚才介绍到的多向量索引和搜索的策略分为分离和联合两种，但是我们可以针对多向量的这种特征去专门设计一个索引和搜索的策略。

再次，我们或许可以尝试通过异构硬件去存储或者加速图的搜索过程，因为图索引以及它对原始数据的依赖导致它的存储开销还是非常大的，这是个可以改进的点。

最后，可以进行一些优化，探索如何将 PG 的维护操作做的更好，以及如何与 AI 或是向量数据库集成。

Q：不同模态的数据通过融合数据模型联合投影到同一个向量空间，是否会存在不同模态转变的向量之间距离较远从而影响到检索速度的情况？例如通过融合数据模型同时将图片、文字、视频转换成对应向量然后存储到同一个向量空间中，视频向量在 A 区域，图片向量在 B 区域，文字向量在 C 区域，且三个区域距离较远，从而导致检索速度较慢。

A：会存在这种情况，不同模态的数据转换成向量之后，向量的分布会存在很大的差异，存在聚类现象。但是现在 CV社区更多地使用多模态融合的模型进行训练，就会减少这种情况的存在。

Q：目前多模态搜索的技术压力似乎都落在融合模型上，那对于向量搜索有什么技术挑战吗？

A：确实目前做了很多对模型的改进，但是当前融合模型还是将联合与分离两种方式结合在一起使用来进行优缺点的互补，还不存在一个特别完美的融合模型。如果单单依靠融合模型能将向量处理的非常好，那么向量搜索就不会有任何挑战；但如果单单依靠融合模型并不能做的很好，那么我们可以考虑在检索层面做一些搜索策略的优化，来弥补融合模型的不足，这样对于向量检索层面就存在一个挑战。

Q：如果遇到特别大的数据量，例如10亿级，无法放入 GPU 的显存中，只能放到 SSD 里，在处理的时候就会多一个 PCIE 的通路进行数据传输，有没有可能数据传输带来的时间开销会导致 GPU 加速变得没有意义？

A：目前已有的技术论文中对于这一块的实验结果显示，虽然面对特别大的数据量存在 PCIE 的过程，但是 GPU 加速可以抵消传输增加的时间开销。