突破性进展：在 Elasticsearch 和 Lucene 中应用更好的二进制量化 (BBQ) 实现高效向量搜索

更好的二进制量化 (BBQ) 在 Elasticsearch 和 Lucene 中的应用

嵌入模型输出的 float32 向量通常过大，不利于高效处理和实际应用。Elasticsearch 支持 int8 标量量化以减小向量大小，同时保持性能。其他方法会降低检索质量，不适合实际使用。在 Elasticsearch 8.16 和 Lucene 中，我们引入了更好的二进制量化 (Better Binary Quantization, BBQ)，这是一种新方法，基于新加坡南洋理工大学研究人员提出的“RaBitQ”技术的见解开发。

BBQ 在 Lucene 和 Elasticsearch 中实现了量化的重大突破，将 float32 维度减少到比特，内存减小约 95%，同时保持高排名质量。BBQ 在索引速度（量化时间减少 20-30 倍）、查询速度（查询速度提高 2-5 倍）上优于传统方法如产品量化 (PQ)，且准确性无额外损失。

在这篇博客中，我们将探讨 BBQ 在 Lucene 和 Elasticsearch 中的应用，重点关注召回率、高效的按位操作和优化存储，以实现快速、准确的向量搜索。

什么是“更好的”二进制量化？

在 Elasticsearch 8.16 和 Lucene 中，我们引入了所谓的“更好的二进制量化”。传统的二进制量化 损失非常大，要达到足够的召回率，需要收集 10 倍或 100 倍的额外邻居进行重新排序，这样的效果显然不理想。

于是我们推出了更好的二进制量化！以下是更好的二进制量化与传统二进制量化之间的一些显著差异：

• 所有向量都围绕一个质心进行归一化，这为量化解锁了一些良好特性。
• 存储多个误差校正值。这些校正部分用于质心归一化，部分用于量化。
• 非对称量化。虽然向量本身存储为单比特值，但查询仅量化到 int4。这显著提高了搜索质量，同时不会增加存储成本。
• 按位操作实现快速搜索。查询向量被量化并转换为允许高效按位操作的方式。

使用更好的二进制量化进行索引

索引过程很简单。请记住，Lucene 构建单独的只读段。当新段中有向量时，质心会逐步计算。段刷新后，每个向量围绕质心进行归一化并量化。

以下是一个小例子：

v1 = [0.56, 0.85, 0.53, 0.25, 0.46, 0.01, 0.63, 0.73]
c = [0.65, 0.65, 0.52, 0.35, 0.69, 0.30, 0.60, 0.76]
vc1' = v1 - c = [-0.09, 0.19, 0.01, -0.10, -0.23, -0.38, -0.05, -0.03]
bin(vc1') = {1 if x > 0 else 0 for x in vc1'}
bin(vc1') = [0, 1, 1, 0, 0, 0, 0, 0]
0b00000110 = 6

Going bit

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

然后，每个比特都被打包成一个字节，并与所选向量相似度所需的任何误差校正值一起存储在段中。

Bit vector layout

对于每个向量，存储的字节数为 dims/8 字节，然后是误差校正值；欧几里得距离为 2 个浮点值，点积为 3 个浮点值。

关于合并处理的一段小插曲

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

确保 HNSW 图的质量并允许图使用量化向量进行构建是个挑战。如果仍然需要所有内存来构建索引，那么量化就没有意义了！

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

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

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

合并完成后，临时文件会被删除，只保留比特量化向量。

Query vector layout

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

非对称量化，有趣的部分

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

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

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

vc1' = v1 - c = [-0.09, 0.19, 0.01, -0.10, -0.23, -0.38, -0.05, -0.03]
max(vc1') = max(vc1') = 0.19
min(vc1') = min(vc1') = -0.38
Q(xs) = {(x - min(vc1')) * 15 / (max(vc1') - min(vc1')) : x ∈ xs}
Q(vc1') = {(x - (-0.38)) * 15 / (0.19 - (-0.38)) : x ∈ vc1'}
Q(vc1') = {(x + 0.38) * 26.32 : x ∈ vc1'}
Q(vc1') = [8, 15, 10, 7, 4, 0, 9, 9]

有了量化向量，这才是乐趣的开始。为了将向量比较转换为按位点积，需要对比特进行移位。

最好直观地展示一下发生了什么：

Bit pack int4

这里，每个 int4 量化值的相对位置比特被移位到单个字节。注意，所有第一个比特首先被打包在一起，然后是第二个比特，以此类推。

但这实际上如何转换为点积呢？记住，点积是分量积的总和。对于上面的示例，让我们完整地写出来：

bin(vc1') ⋅ Q(vc1') = [0, 1, 1, 0, 0, 0, 0, 0] ⋅ [8, 15, 10, 7, 4, 0, 9, 9] = [0×8 + 1×15 + 1×10 + 0×7 + 0×4 + 0×0 + 0×9 + 0×9] = 15 + 10 = 25

我们可以看到，它只是查询分量的总和，其中存储的向量比特为 1。由于所有数字都是比特，当用二进制扩展表示时，我们可以稍微移动一些东西以利用按位操作。

这些比特在 && 后将被翻转，成为对点积有贡献的数字的单个比特。在这种情况下是 15 和 10。

记住我们最初存储的向量
storedVecBits = bin(vc1') = [0, 1, 1, 0, 0, 0, 0, 0]
我们旋转并组合比特，得到
storedVectBits = 0b11000000
查询向量，int4 量化
Q(vc1') = [8, 15, 10, 7, 4, 0, 9, 9]
每个维度的二进制值
bits(Q(vc1')) = [0b1000, 0b1111, 0b1010, 0b0117, 0b0100, 0b0000, 0b1001, 0b1001]
我们移位比特并对齐，如上图所示
qVecBits = align(bits(Q(vc1'))) = [0b11001010, 0b00001110, 0b00011010, 0b11000111]
qVecBits & storedVectBits = {qVecBits & bits : bits ∈ storedVectBits} = [0b00000010, 0b00000110, 0b00000010, 0b00000010]

现在我们可以计算比特数，移位并重新求和。可以看到，所有剩下的比特都是 15 和 10 的位置比特。

(bitCount(0b00000010) << 0) + (bitCount(0b00000110) << 1) + (bitCount(0b00000010) << 2) + (bitCount(0b00000010) << 3)
= (1 << 0) + (2 << 1) + (1 << 2) + (2 << 3) = 25

结果与直接求和分量一致。

以下是示例的简化 Java 代码：

byte[] bits = new byte[]{6};
byte[] queryBits = new byte[]{202, 14, 26, 199};
int sum = 0;
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 的 oversampling 的 recall@100。

E5-small

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

e5small bit 500k

令人惊叹的是，我们只用单比特精度就能达到 74% 的召回率。由于维度较少，BBQ 距离计算速度并没有比优化的 int4 快多少。

CohereV3

这是 1M 个 1024 维向量，使用 CohereV3 模型。

cohere v3 bit 1M

这里，1bit 量化和 HNSW 在仅 3 倍 oversampling 的情况下，召回率超过 90%。

CohereV2

这是 1M 个 768 维向量，使用 CohereV2 模型和最大内积相似度。

Cohere V2 bit 1M

很有趣的是，BBQ 和 int4 在这个基准测试中步调一致。BBQ 仅用 3 倍 oversampling 就能在内积相似度下获得如此高的召回率。

大规模 Elasticsearch 基准测试

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

此数据集包含 138M 个 1024 维的浮点向量。如果不进行任何量化，这需要大约 535 GB 的内存和 HNSW。使用更好的二进制量化，估计内存需求下降到大约 19GB。

对于这次测试，我们在 Elastic 云中使用了一个 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 是每个分片中 HNSW 用于探索的候选数量
• rerank 是要重新排序的候选数量，因此我们将从每个分片收集该数量的值，收集总 rerank 大小，然后使用原始 float32 向量重新打分前 k 值。

索引时间大约为 12 小时。以下是三个有趣的结果：

这显示了平衡召回率、过采样、重新排序和延迟的重要性。显然，每个参数都需要针对您的具体用例进行调整，但考虑到这在以前是不可能的，现在我们在单个节点上有 138M 个向量，这非常酷。

结论

感谢您花时间阅读关于更好的二进制量化的内容。作为一个来自阿拉巴马州，现在居住在南卡罗来纳州的人，BBQ 在我的生活中已经占有特殊的位置。现在，我有更多理由喜欢 BBQ！

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

Elasticsearch 装载了许多新功能，帮助您为您的用例构建最佳搜索解决方案。深入了解我们的 示例笔记本，开始 免费云试用，或者现在就在您的 本地机器 上试试 Elastic 吧。