Lucene 和 Elasticsearch 中的改进二值量化 (BBQ)

嵌入模型输出 float32 向量，通常对于高效处理和实际应用来说太大。Elasticsearch 支持 int8 标量量化以减小向量大小，同时保持性能。其他方法会降低检索质量，并且在实际应用中不切实际。在 Elasticsearch 8.16 和 Lucene 中，我们引入了改进二值量化 (BBQ)，这是一种基于最近技术（由新加坡南洋理工大学的研究人员提出，称为“RaBitQ”）的见解而开发的新方法。

BBQ 是 Lucene 和 Elasticsearch 量化方面的一项重大进步，它将 float32 维度减少到比特，实现了约 95% 的内存减少，同时保持了较高的排名质量。BBQ 在索引速度方面（量化时间减少 20-30 倍）、查询速度方面（查询速度提高 2-5 倍）优于传统的 Product Quantization (PQ) 等方法，并且不会额外损失准确性。

在本博文中，我们将探讨 Lucene 和 Elasticsearch 中的 BBQ，重点关注召回率、高效的按位运算以及针对快速、准确的向量搜索而优化的存储。

“改进”二值量化中的“改进”是什么意思？

在 Elasticsearch 8.16 和 Lucene 中，我们引入了我们所说的“改进二值量化”。朴素的二值量化存在极大的信息损失，要获得足够的召回率，需要收集 10 倍或 100 倍的额外邻居进行重新排序。这显然是不够的。

于是，改进二值量化应运而生！以下是改进二值量化与朴素二值量化之间的一些重要区别

• 所有向量都围绕一个质心进行归一化。这在量化中解锁了一些不错的特性。
• 存储多个错误校正值。其中一些校正值用于质心归一化，一些用于量化。
• 非对称量化。在这里，虽然向量本身存储为单个比特值，但查询仅量化到 int4。这在不增加存储成本的情况下显着提高了搜索质量。
• 用于快速搜索的按位运算。查询向量被量化并以一种允许高效按位运算的方式进行转换。

使用改进二值量化进行索引

索引很简单。请记住，Lucene 构建单独的只读段。当新的段出现向量时，会增量计算质心。然后，一旦段被刷新，每个向量都会围绕质心进行归一化并进行量化。

这是一个简单的示例

当量化到比特级时，8个浮点数被转换为单个8位字节。

然后，每个比特都被打包到一个字节中，并与向量相似度所需的任何纠错值一起存储在段中。

对于每个向量，存储的字节数为dims/8个字节，然后是任何纠错值；欧几里得距离使用2个浮点数，点积使用3个浮点数。

快速讨论一下我们如何处理合并。

当段合并时，我们可以利用之前计算的质心。只需对质心进行加权平均，然后围绕新的质心重新量化向量。

棘手的问题是如何确保HNSW图的质量，并允许使用量化向量构建图。如果仍然需要所有内存来构建索引，那么量化的意义何在？！

除了将向量追加到现有的最大HNSW图之外，我们还需要确保向量评分可以利用非对称量化。HNSW有多个评分步骤：一个用于初始邻居的收集，另一个用于确保仅连接不同的邻居。为了有效地使用非对称量化，我们创建了一个所有向量量化为4位查询向量临时文件。

因此，当向量添加到图中时，我们首先

• 获取存储在临时文件中的已量化查询向量。
• 使用现有的位向量按常规搜索图。
• 一旦我们有了邻居，多样性和反向链接评分就可以使用之前int4量化的值来完成。

合并完成后，临时文件将被删除，只留下位量化向量。

临时文件将每个查询向量存储为一个int4字节数组，占用dims/2个字节，一些浮点纠错值（欧几里得距离为3个，点积为4个），以及一个表示向量维度总和的短整型值。

非对称量化，有趣的部分

我提到了非对称量化以及我们如何为图构建设置查询。但是，向量是如何实际转换的？它是如何工作的？

“非对称”部分很简单。我们将查询向量量化为更高的保真度。因此，文档值是位量化的，查询向量是int4量化的。更有趣的是这些量化向量如何被转换以进行快速查询。

以我们上面提到的示例向量为例，我们可以将其量化为以质心为中心的int4。

有了量化向量，乐趣就开始了。因此，我们可以将向量比较转换为按位点积，位被移位。

也许最好直接可视化正在发生的事情

这里，每个int4量化值将其相对位置位移位到单个字节中。注意所有第一位是如何首先打包在一起的，然后是第二位，依此类推。

但这如何真正转化为点积？请记住，点积是分量积的总和。对于上面的示例，让我们完整地写出来

我们可以看到，它只是存储向量位为1的查询分量的总和。并且由于所有数字都只是位，当使用二进制展开表示时，我们可以稍微移动一些东西来利用按位运算。

在$\&$之后将被翻转的位将是构成点积的数字的各个位。在本例中为15和10。

现在我们可以计算位数，移位并将它们加总在一起。我们可以看到，所有剩下的位都是15和10的位置位。

与直接对维度求和的结果相同。

这是一个简化的 Java 代码示例。

byte[] bits = new byte[]{6};
byte[] queryBits = new byte[]{202, 14, 26, 199};
for (int i = 0; i < 4; i++) {
  sum += Integer.bitCount(bits[0] & queryBits[i] & 0xFF) << i;
}

好的，请展示数字。

我们已经对 Lucene 和 Elasticsearch 中的 BBQ 进行了广泛的测试。以下是一些结果。

Lucene 基准测试

此处的基准测试基于三个数据集：E5-small、CohereV3 和 CohereV2。其中，每个元素表示在 [1, 1.5, 2, 3, 4, 5] 过采样下的 recall@100。

E5-small

这是从 Quora 数据集构建的 500k 个 E5-small 向量。

令人震惊的是，我们仅用一位精度就获得了 74% 的召回率。由于维度较少，BBQ 距离计算速度并没有比我们优化的 int4 快多少。

CohereV3

这是使用 CohereV3 模型的 100 万个 1024 维向量。

在这里，1 位量化和 HNSW 在仅 3 倍过采样下即可获得超过 90% 的召回率。

CohereV2

这是使用 CohereV2 模型和最大内积相似度的 100 万个 768 维向量。

很有意思的是，BBQ 和 int4 在此基准测试中表现出高度的一致性。令人惊喜的是，BBQ 仅用 3 倍过采样就能在内积相似度下获得如此高的召回率。

更大规模的 Elasticsearch 基准测试

如我们的更大规模向量搜索博客中所述，我们有一个用于更大规模向量搜索基准测试的Rally 轨道。

此数据集包含 1.38 亿个 1024 维浮点向量。如果不进行任何量化，使用 HNSW 将需要大约 535 GB 的内存。使用更好的二进制量化，估计值将降至约 19 GB。

对于此测试，我们在 Elastic Cloud 中使用了一个 64GB 的节点，并使用以下轨道参数。

{
        "mapping_type": "vectors-only",
        "vector_index_type": "bbq_hnsw",
        "number_of_shards": 2,
        "initial_indexing_bulk_indexing_clients": 12,
        "standalone_search_clients": 8,
        "aggressive_merge_policy": true,
        "search_ops": [[10, 20, 0], [10, 20, 20], [10, 50, 0], [10, 50, 20], [10, 50, 50], [10, 100, 0], [10, 100, 20], [10, 100, 50], [10, 100, 100], [10, 200, 0], [10, 200, 20], [10, 200, 50], [10, 200, 100], [10, 200, 200], [10, 500, 0], [10, 500, 20], [10, 500, 50],[10, 500, 100],[10, 500, 200],[10, 500, 500],[10, 1000, 0], [10, 1000, 20], [10, 1000, 50], [10, 1000, 100], [10, 1000, 200], [10, 1000, 500], [10, 1000, 1000]]
}

重要提示：如果您想复制此测试，下载所有数据需要大量时间，并且需要超过 4TB 的磁盘空间。需要这么多磁盘空间的原因是，此数据集还包含文本字段，您需要磁盘空间来存储压缩文件及其解压后的数据。

参数如下：

• k 是要搜索的邻居数量。
• num_candidates 是每个分片中用于探索的候选者数量。
• rerank 是要重新排序的候选者数量，因此我们将收集每个分片上的这么多值，收集总的 rerank 大小，然后使用原始 float32 向量对前 k 个值进行重新评分。

索引时间大约需要 12 个小时。这里不展示所有结果，只列出三个比较有趣的结果。

这表明平衡召回率、过采样、重新排序和延迟的重要性。显然，每个参数都需要根据您的具体用例进行调整，但考虑到这在以前是不可能的，现在我们可以在单个节点上拥有 1.38 亿个向量，这真是太棒了。

结论

感谢您抽出时间阅读关于更好的二进制量化 (Better Binary Quantization) 的内容。我来自阿拉巴马州，现在住在南卡罗来纳州，BBQ 一直在我心中占据着特殊的位置。现在，我更有理由热爱 BBQ 了！

我们将在 8.16 版本中以技术预览版发布此功能，或者您现在也可以在无服务器环境中使用。要使用此功能，只需将您的 dense_vector.index_type 设置为 bbq_hnsw 或 bbq_flat 在 Elasticsearch 中。

相关内容

向量数据库Lucene+1

2024年11月18日

更好的二进制量化与乘积量化

我们为什么选择花时间在改进 Lucene 和 Elasticsearch 中的二进制量化而不是乘积量化上。

BT

作者 Benjamin Trent

向量数据库Lucene+1

2024年10月22日

RaBitQ 二进制量化 101

了解 RaBitQ 二进制量化中最关键的组件、其工作原理及其优势。本指南还涵盖了量化背后的数学原理和示例。

JW

作者 John Wagster

Lucene

2024年10月14日

Apache Lucene 10 发布！Lucene 硬件效率改进等

Apache Lucene 10 刚刚发布，重点关注硬件效率！查看主要版本亮点。

AG

作者 Adrien Grand

Lucene

2023年12月7日

Apache Lucene 9.9，有史以来最快的 Lucene 版本

Lucene 9.9 为查询评估带来了重大的速度提升。以下是每晚基准测试中观察到的性能改进和优化资源。

AG

作者 Adrien Grand

向量数据库Lucene

2024年6月26日

Elasticsearch 与 OpenSearch：向量搜索性能比较

Elasticsearch 在向量搜索方面比 OpenSearch 快 2 倍到 12 倍

US

作者 Ugo Sangiorgi