推荐语
电商推荐系统如何平衡精度与成本？ScaNN索引以1/16内存占用实现高吞吐，是IVFPQ的优化升级版。核心内容： 1. ScaNN索引的技术原理与IVFPQ的对比优势 2. 在电商推荐等中等精度场景的实际性能表现 3. 内存占用与查询效率的量化数据对比
杨芳贤
53AI创始人/腾讯云(TVP)最具价值专家
在日常解答Milvus社区中各种用户提问的时候，一个最常见的问题是：
Milvus索引这么多，我到底要怎么选？
对于常见场景，我们可以参考这两张图
但肯定也有用户发现了，Milvus中，还有ScaNN这么一个索引类型怎么没有放进来，这个索引究竟要怎么用？适合什么场景用？
先一句话解答，它框架上和IVFPQ非常相似，优点在于改善了PQ编码的一些细节，以及使用了高效的SIMD实现。主要适用于一些中等精度（召回率要求不高，比如推荐系统）、高吞吐、内存成本敏感的场合，以更低的内存占用（1/16 倍原始数据）取得亮眼的QPS。
01 IVFPQ 技术解读
（本章节为技术解读，可跳过快进至03章节，查看效果解读）
ScaNN在2020年由Google提出，在论文中使用的glove数据集上取得了对于HNSW有3倍以上的性能优势。
ScaNN的paper在这里，https://arxiv.org/pdf/1908.10396.pdf，其代码也是开源的，https://github.com/google-research/google-research/tree/master/scann。
不过在介绍ScaNN之前，我们需要先简单地介绍下IVFPQ算法的原理，因为ScaNN算法的基础是IVFPQ。
IVF这一层利用聚类做分桶，聚类个数为nlist，查询的时候通过控制访问的分桶个数（nprobe）来做recall和性能之间的trade-off。
然后对每个分桶中的向量做PQ编码，将一个D维的向量分成m个subvector，每个subvector的维度为D/m。再对每个subvector做量化编码，所谓量化，其实就是把这些subvector做聚类，每个向量选择最近的聚类中心作为quantized subvector。如果这个聚类个数是256，那么quantized subvector可以用一个uint8的ID来表示。
最终的距离计算可以转化为如下表达式
D(q, X) = D(q, u0) + D(q, u1) + D(q, u2) + ... + D(q, un)
= L(q, id1) + L(q, id2) + L(q, id3) + ... + L(q, idn)
其中，L代表Lookup table，在一个query查询的时候，一开始会去构建Lookup table，记录的是每个query和每个quantized vector的距离。接下来的距离计算会全部转化为查表然后做加和计算。
我们可以看一个例子，128维的向量数据，可以分成32个4维的subvector，然后每个subvector会量化成一个聚类中心，用uint8表示。所以向量数据的大小从128 * 4byte => 32 * 8bit，大小变为原来的1/16。
02
ScaNN基于IVFPQ的优化
（本章节为技术解读，可跳过快进至03章节，查看效果解读）
先一句话概括，ScaNN针对IVFPQ两点做了优化
（1）Score-aware quantization loss
ScaNN采用了一种和传统PQ不同的量化思路，也就是前面第二张图的过程和PQ不同。
传统PQ在量化的时候，需要给每个向量assign量化中心，其实就是计算不同量化中心取距离最小的点，其目的其实是在最小化将量化成带来的量化误差：。
而ScaNN对这个过程进行了修改，首先它提出了loss的概念。loss和上面的量化误差略有不同，这个loss指的是两个向量的实际距离和使用量化方法计算的近似距离之间的误差，ScaNN主要针对的是IP距离，IP距离的误差和查询向量的分布可以用公式描述
如果查询向量q是各向同性，那么有，其中为单位矩阵。因此损失函数可以化简为
ScaNN认为这个loss function并不是最好的。因为对于一个query来说，其实离query点比较近的数据的重要性更大，把这些数据的量化误差降下去对于结果更加重要，于是提出了一种score-aware quantization loss，，这里的w就表示weight。
但现在有一个问题是这个weight是query aware的，相当于我们知道query以后才能算出这个loss。
所以需要做一些假设和合理转化把这个q给消掉，帮助我们在离线阶段去构建索引。
论文中把误差分解成与平行的分量以及垂直分量，并且应该给平行分量施以更大的penalty。Loss用下式表示，
为什么要给平行分量施以更大的penalty呢？首先这里假设x是q1的近邻的话，那么x和q1的方向是接近的，所以x的平行分量可以近似认为和q1也是平行的，那么这个平行分量会让误差增大。
由于基于IP这个metric来分析，ScaNN把量化误差分成平行分量和垂直分量以后，由于只有平行分量会对结果产生影响，所以应该施以更大的惩罚项，最后的loss function转化成如下
下图是一个二维空间下的例子，说明平行分量带来的误差是更大的，会导致最后近邻结果的错误，所以应该施以更严厉的惩罚项。
左图的量化效果不佳，因为平行偏移影响了最终结果，右图的量化效果更好
4bit PQ FastScan
首先回顾下PQ的计算过程，查询时预计算query和subvector的聚类中心，构建Lookup table，计算距离时通过查表拿到分段距离做加和。
但是频繁的读内存操作还是不够高效，如果可以把Lookup table做到足够小，小到可以在寄存器里放得下，就可以把读内存的操作变成cpu高效的SIMD指令。
首先每个subvector聚成16个类，这样就可以用4bit代表一个聚类中心，这也是4bit PQ名字的来源。然后将一般用float表示的距离进一步使用SQ转化成uint8，如此一来，一个subvector的Lookup table就可以使用16 * 8 = 128bit存到寄存器里。
最后来看下寄存器的存储布局（AVX2指令集为例），将32个向量的subvector放在一个128bit的寄存器里，搭配上Lookup table，然后就可以使用SIMD shuffle一个cpu指令高效完成“查表”操作。
寄存器布局
simdshuffle做查表
最后分享一点有趣的事情，ScaNN paper完全focus在第一点的优化上，应该说这也没什么问题，因为可以认为这是一个算法paper，着重于讲一些数学推导上。但是最后paper展示出来的实验结果实在是太惊艳了，
ScaNN paper展示的实验结果
直觉上对于loss的优化不应该产生这么大的效果，也有国外的博客说明了这个问题，其实真正有用的是4bit PQ FastScan的部分
https://medium.com/@kumon/similarity-search-scann-and-4-bit-pq-ab98766b32bd。
03
实验结果
我们使用向量数据库benchmark工具简单做了一下测试
GitHub - zilliztech/VectorDBBench: A Benchmark Tool for VectorDB
最终结果显示，ScaNN的性能优势相比于传统的 IVFFLAT 和 IVF_PQ 还是很明显的，集成到 Milvus 以后，在 Cohere1M 数据集上，相同召回率，QPS可以达到 IVFFLAT 的5倍，IVF_PQ 的6倍。
不过 QPS 比 HNSW 这类图索引低一些，对于性能优先的场景，不是第一选择。
但是对于一些召回率要求不高的场景（比如推荐系统），使用不加载原始数据的 ScaNN 索引，可以在极低的内存占用下（1/16 倍原始数据）取得亮眼的QPS，是一个很不错的索引选择。
Agent的本地数据管理？都来学Claude Code！附深度拆解" data-itemshowtype="0" linktype="text" data-linktype="2">不会做RAG、agent的本地数据管理？都来学Claude Code！附深度拆解
粤ICP备14082021号
免费POC，
零成本试错
