二进制量化 - 向量搜索，速度提升 40 倍

Nirant Kasliwal

2023 年 9 月 18 日

Binary Quantization - Vector Search, 40x Faster

使用二进制量化优化高维向量

Qdrant 旨在应对常见的扩展挑战：高吞吐量、低延迟和高效索引。二进制量化（BQ）是我们在帮助客户实现高效扩展方面做出的最新尝试。此功能对于具有大向量长度和大量点的集合尤其出色。

我们的结果引人注目：使用 BQ 可减少内存消耗，并将检索速度提高多达 40 倍。

与其他量化方法一样，这些优势是以召回率下降为代价的。然而，我们的实现允许您在搜索时而非索引创建时权衡速度和召回准确性。

本文的其余部分将涵盖

二进制量化的重要性
使用我们的 Python 客户端进行基本实现
基准分析和使用建议

什么是二进制量化？

二进制量化（BQ）将浮点数的任何向量嵌入转换为二进制或布尔值向量。此功能是我们过去关于标量量化工作的扩展，在该工作中，我们将 float32 转换为 uint8，然后利用特定的 SIMD CPU 指令执行快速向量比较。

What is binary quantization

这个二值化函数是我们如何将范围转换为二进制值的方法。所有大于零的数字标记为 1。如果小于等于零，则变为 0。

将向量嵌入减少到二进制值的优势在于布尔运算非常快，并且需要的 CPU 指令显著减少。通过将 32 位嵌入减少到 1 位嵌入，我们可以看到检索速度提升高达 40 倍！

向量搜索在高压缩率下仍然有效的原因之一是，这些大向量对于检索来说参数过多。这是因为它们是为排名、聚类和类似用例设计的，这些用例通常需要在向量中编码更多信息。

例如，1536 维的 OpenAI 嵌入在检索和排名方面不如 384 维的开源对应模型。具体来说，在同一个嵌入检索基准上，它的得分为 49.25，而开源的 bge-small 得分为 51.82。这 2.57 分的差距很快就会累积起来。

我们的量化实现很好地平衡了排名时的完整大向量和搜索检索时的二进制向量。它还允许您根据自己的用例调整这种平衡。

更快的搜索和检索

与乘积量化不同，二进制量化不依赖于减少每个探针的搜索空间。相反，我们构建了一个二进制索引，帮助我们大幅提高搜索速度。

Speed by quantization method

HNSW 是一种近似最近邻搜索。这意味着随着我们检查索引以获取更多相似候选，我们的准确性会在达到收益递减点之前得到提高。在二进制量化的上下文中，这被称为过采样率（oversampling rate）。

例如，如果 oversampling=2.0 且 limit=100，则将首先使用量化索引选择 200 个向量。对于这 200 个向量，将使用完整的 32 位向量及其 HNSW 索引生成更准确的 100 项结果集。与进行完整的 HNSW 搜索不同，我们对初步搜索进行过采样，然后仅对这个小得多的向量集进行完整搜索。

提高存储效率

下图显示了二值化函数，通过它我们将 32 位存储减少到 1 位信息。

文本嵌入可以是超过 1024 个元素的 32 位浮点数。例如，请记住 OpenAI 嵌入是 1536 维向量。这意味着每个向量仅存储本身就需要 6kB。

Improved storage efficiency

除了存储向量，我们还需要维护索引以实现更快的搜索和检索。Qdrant 估计总内存消耗的公式是

memory_size = 1.5 * 向量数量 * 向量维度 * 4 字节

对于 10 万个 OpenAI 嵌入 (ada-002) 向量，我们将需要 900MB 的 RAM 和磁盘空间。随着您创建多个集合或向数据库添加更多项目，这种消耗会迅速累积。

使用二进制量化，同样的 10 万个 OpenAI 向量仅需 128MB RAM。 我们使用与我们的标量量化内存估计中介绍的方法类似的方法对这一结果进行了基准测试。

RAM 使用量的这种减少是通过二进制转换中的压缩实现的。HNSW 和量化向量将存储在 RAM 中以实现快速访问，而原始向量则仅可卸载到磁盘。对于搜索，量化 HNSW 将提供过采样的候选，然后使用存储在磁盘上的原始向量对其进行重新评估，以优化最终结果。这一切都在底层进行，无需您进行任何额外干预。

何时不应使用 BQ？

由于此方法利用了嵌入的参数过多特性，对于小型嵌入（即小于 1024 维）来说，效果会较差。元素数量较少时，二进制向量中保留的信息不足以获得良好结果。

您仍然会获得更快的布尔运算和更低的 RAM 使用量，但准确性下降可能过高。

示例实现

既然我们已经向您介绍了二进制量化，接下来尝试一个基本实现。在本例中，我们将使用 OpenAI 和 Cohere 与 Qdrant。

创建启用二进制量化的集合

创建集合时，您在索引时应执行以下操作

我们将所有“完整”向量存储在磁盘上。
然后我们将二进制嵌入设置为驻留在 RAM 中。

默认情况下，完整向量和 BQ 都存储在 RAM 中。我们将完整向量移动到磁盘，因为这样可以节省内存，并允许我们在 RAM 中存储更多向量。通过这样做，我们通过设置 always_ram=True 明确地将二进制向量移动到内存中。

from qdrant_client import QdrantClient

#collect to our Qdrant Server
client = QdrantClient(
    url="http://localhost:6333",
    prefer_grpc=True,
)

#Create the collection to hold our embeddings
# on_disk=True and the quantization_config are the areas to focus on
collection_name = "binary-quantization"
if not client.collection_exists(collection_name):
    client.create_collection(
        collection_name=f"{collection_name}",
        vectors_config=models.VectorParams(
            size=1536,
            distance=models.Distance.DOT,
            on_disk=True,
        ),
        optimizers_config=models.OptimizersConfigDiff(
            default_segment_number=5,
        ),
        hnsw_config=models.HnswConfigDiff(
        m=0,
        ),
        quantization_config=models.BinaryQuantization(
            binary=models.BinaryQuantizationConfig(always_ram=True),
        ),
    )

HnswConfig 中发生了什么？

我们将 m 设置为 0，即禁用 HNSW 图的构建。这允许更快地上传向量和负载。一旦所有数据加载完毕，我们将在下面重新启用它。

接下来，我们将向量上传到此处，然后启用图构建

batch_size = 10000
client.upload_collection(
    collection_name=collection_name,
    ids=range(len(dataset)),
    vectors=dataset["openai"],
    payload=[
        {"text": x} for x in dataset["text"]
    ],
    parallel=10, # based on the machine
)

再次启用 HNSW 图构建

client.update_collection(
    collection_name=f"{collection_name}",
    hnsw_config=models.HnswConfigDiff(
        m=16,
    ,
)

配置搜索参数

设置搜索参数时，我们指定要使用 oversampling 和 rescore。这是一个示例代码片段

client.search(
    collection_name="{collection_name}",
    query_vector=[0.2, 0.1, 0.9, 0.7, ...],
    search_params=models.SearchParams(
        quantization=models.QuantizationSearchParams(
            ignore=False,
            rescore=True,
            oversampling=2.0,
        )
    )
)

Qdrant 拉取过采样的向量集后，完整的向量（例如 OpenAI 的 1536 维向量）将从磁盘中拉取上来。Qdrant 计算与查询向量的最近邻，并返回准确、重新排序的结果。此方法产生更准确的结果。我们通过设置 rescore=True 启用了此功能。

这两个参数是您平衡速度与准确性的方式。过采样的大小越大，您需要从磁盘读取的项目越多，并且您必须使用相对较慢的完整向量索引搜索的元素也越多。另一方面，这样做会产生更准确的结果。

如果您的准确性要求较低，甚至可以尝试进行小规模过采样而不进行重新评分。或者，对于您的数据集以及您对准确性与速度的要求，您可以只搜索二进制索引而不进行重新评分，即在搜索查询中省略这两个参数。

基准测试结果

我们使用 DBPedia OpenAI 1M 向量数据集，获取了关于 limit 和 oversampling 之间关系的一些早期结果。我们在一个 Qdrant 实例上运行了所有这些实验，其中索引了 10 万个向量，并使用了 100 个随机查询。

我们改变了影响查询时间和准确性的 3 个参数：limit、rescore 和 oversampling。我们将这些作为对这个新功能的初步探索。强烈鼓励您使用自己的数据集重复这些实验。

补充：由于这是向量数据库领域的一项新创新，我们非常希望听到反馈和结果。加入我们的 Discord 服务器进行进一步讨论！

过采样： 在下图中，我们说明了召回率和候选数量之间的关系

Correct vs candidates

我们看到，“正确”结果，即召回率，随着潜在“候选”数量（limit x oversampling）的增加而增加。为了突出改变 limit 的影响，不同的 limit 值被分解成不同的曲线。例如，我们看到 limit 50 的最低召回率约为 94 个正确结果，对应 100 个候选。这也意味着我们使用了 2.0 的过采样率。

随着过采样率的增加，我们看到结果普遍有所改善——但这并非适用于所有情况。

重新评分：正如预期的那样，重新评分会增加返回查询所需的时间。我们还重复了过采样实验，但这次我们关注了重新评分如何影响结果准确性。

Relationship between limit and rescore on correct

Limit：我们实验了从 Top 1 到 Top 50 的 limit，在包含 10 万个向量的索引中，当 limit 为 50 并设置 rescore=True 时，我们能够达到 100% 的召回率。

建议

量化允许您与其他参数进行权衡：维度数量/嵌入大小吞吐量和延迟要求召回率要求

如果您使用 OpenAI 或 Cohere 嵌入，我们推荐以下过采样设置

方法	维度	测试数据集	召回率	过采样
OpenAI text-embedding-3-large	3072	DBpedia 1M	0.9966	3 倍
OpenAI text-embedding-3-small	1536	DBpedia 100K	0.9847	3 倍
OpenAI text-embedding-3-large	1536	DBpedia 1M	0.9826	3 倍
OpenAI text-embedding-ada-002	1536	DbPedia 1M	0.98	4 倍
Gemini	768	无公开数据	0.9563	3 倍
Mistral Embed	768	无公开数据	0.9445	3 倍

如果您确定二进制量化适用于您的数据集和查询，我们建议如下

二进制量化并设置 always_ram=True
向量存储在磁盘上
过采样率 = 2.0（或更高）
重新评分 = True

接下来是什么？

如果您需要在高召回率预期下处理大量数据，二进制量化将是您的不二之选。您可以通过在本地启动Qdrant 容器镜像或通过我们的云托管服务免费注册账号来尝试此功能。

本文提供了一些可以用于入门的数据集和配置示例。我们的文档涵盖了如何将大型数据集添加到 Qdrant 实例以及更多量化方法。

如果您有任何反馈，请在 Twitter 或 LinkedIn 上给我们留言，告诉我们您的结果。加入我们活跃的 Discord 服务器，与志同道合的人讨论 BQ！

学习

学习