8 位旋转量化：如何将向量压缩 4 倍并提高向量搜索的速度-质量权衡

向量量化是用于压缩向量数据库中的向量的一系列常用技术。通过应用某种形式的量化，通常可以将存储向量的内存占用量减少4倍到32倍，同时加快距离计算速度。

执行向量搜索时，最耗时的操作之一是计算查询向量与数据库/数据集中向量之间的距离（或距离估计）。这些操作经过高度优化，以尽可能减少每字节向量所需的CPU周期数。通过使用压缩率为例如4倍的量化方案压缩向量，同时在吞吐量方面支持与字节衡量的量化码上同样快速的距离估计，从理论上讲，我们能够在相同的时间内执行4倍的距离计算。在实践中，我们确实观察到这种数量级的加速，将SIMD优化的8位整数向量（对应于4倍压缩）的距离估计速度与32位浮点向量进行比较。

使用诸如Weaviate的HNSW索引之类的向量索引执行近似最近邻搜索时，我们可以选择用搜索结果质量的降低来换取搜索速度的提高。简化一下，这种速度-质量权衡背后的主要机制涉及索引智能地限制搜索，以考虑数据集中较少或较多的向量部分来进行距离估计。例如，如果我们考虑数据集的2%进行距离估计，而不是1%，我们通常可以大幅提高召回率（搜索质量）。孤立地看，向量量化会降低与未压缩向量相比的召回率，但如果向量量化方案足够快且精确，我们可以通过搜索数据集的更大一部分来弥补这种召回率下降，最终结果仍然是由于更快的距离估计而提高搜索时间。

🚀🚀🚀

将向量索引与快速精确的向量量化方案相结合，可以同时减少内存使用量、加快向量搜索速度并提高搜索结果质量！

向量量化以减少内存瓶颈和降低云成本

随着向量集合的增长，内存（RAM）通常成为快速近似最近邻搜索的瓶颈。这种限制在基于图的索引结构（如Weaviate的HNSW索引）中尤为突出，后者依赖于对单个向量进行快速随机访问。现代向量嵌入的高维性加剧了这个问题，例如来自OpenAI等嵌入提供商的维度大小通常为1536甚至3072维，从而显著增加了RAM需求。

应用向量量化的一个重要动机是在云环境中降低成本，在云环境中，内存是一种昂贵的资源。在AWS EC2按需实例类型上进行线性回归表明，实例价格与其资源特征之间的关系如下

$$\text{实例价格 0.01\$/小时} \approx 5.1 \cdot \text{vCPU} + 0.48 \cdot \text{GB RAM} + 0.0043 \cdot \text{GB NVMe SSD}$$

考虑到计算、内存和磁盘的相对成本，回归表明1个vCPU在成本上相当于10GB的RAM，而10GB的RAM又相当于1000GB的NVMe SSD。因此，当在内存中存储数百万个未压缩向量并消耗数百GB的RAM时，内存使用量往往会主导成本。另一个有趣的观察是，每GB内存的成本大约比每GB NVMe SSD存储的成本高两个数量级。这也是我们致力于研究如何更好地利用SSD存储进行向量搜索的主要动机——我们也在Weaviate上致力于此，以进一步降低成本。最终，无论我们的向量索引将向量保存在内存中还是磁盘上，或者两者兼而有之，我们都将受益于压缩向量并加快距离计算的量化方案，从而减少资源使用。

根据量化码每输入维度使用的位数，可以将向量量化方案分为低、中和高压缩方案。下表概述了在典型的一百万个OpenAI嵌入数据集上，最先进的向量量化方法可以实现的空间使用量和典型召回率。

压缩率 (每输入维度位数)	空间使用量 一百万个1536维向量	预期召回率 k@k |kNN ∩ 候选集|/ k
未压缩 (32位)	5859 MB	100%
低 4x (8位)	1465 MB	97-99.9%
中等 8x (4位)	732 MB	90-97%
高 32x (1位)	183 MB	70-90%

高压缩率可以带来显著的内存节省，但通常会伴随着搜索质量的明显降低。因此，虽然32倍压缩很有吸引力，但4倍（8位）压缩在各种数据集上提供更高的、更可靠的召回率，同时还支持快速距离计算。

平衡权衡：压缩、速度和向量量化的质量

向量搜索的压缩算法领域在压缩率、编码速度、距离计算的速度和SIMD支持、不同数据集和不同查询的距离估计的稳健性以及量化方法训练的需要等方面提供了不同的权衡，仅举几项最重要的因素。

另一个重要的区别是向量量化算法是针对单次还是批量距离计算进行优化的。后者通常是IVF风格索引的情况，它解锁了SIMD优化的进一步选项，例如FastScan算法。

在Weaviate，我们希望开发一种快速的、未经训练的向量量化技术，该技术适用于我们的HNSW索引（单次距离计算），并且可以在典型的一百万个OpenAI嵌入数据集上支持每秒数万个查询。开发旋转量化时的另一个目标是找到一种8位量化方法，它提供与使用未压缩向量基本相同的稳健性和召回率。

下表显示了旋转量化与Weaviate的其他量化技术相比如何。

(*) 我们正在开发一种提供32倍压缩且性能特征和稳健性与8位RQ相似但召回率略低的1位RQ版本。

我们8位旋转量化的初始实现具有独特的特点，即对于大多数数据集，它比标量量化和未压缩（或无量化）为向量搜索提供了更好的速度-质量权衡。与标量量化相比，它更稳健、提供更高的召回率，并且不需要训练。与未压缩相比，它导入数据速度快近50%，并且召回率非常相似。因此，我们认为8位旋转量化对于大多数Weaviate用户来说是一个更好的默认选择。

结合随机旋转和标量量化

最近，1位量化方法RaBitQ [SIGMOD 2024]及其扩展到B位 [SIGMOD 2025]展示了将随机旋转与二进制/标量量化相结合的力量，从而导致这些技术被行业采用。

受RaBitQ的启发，我们开发了一种简化的、优化的8位旋转量化（RQ）算法，该算法适用于Weaviate的HNSW索引。原始的RaBitQ量化技术主要用于IVF风格的索引，其中数据向量围绕聚类中心，并且可以对距离计算进行批量处理。为了使它们对我们的HNSW索引足够快，我们必须对RaBitQ算法进行一些修改。

我们将首先简要描述 8 位旋转量化，然后提供一些实验结果。接下来，我们将阐述随机旋转在量化中的优势。最后，我们将深入探讨我们如何修改 RaBitQ 算法，以实现我们快速旋转量化。

使用每维 8 位编码旋转向量

如图所示，旋转量化接收一个输入向量 $x \in\mathbb{R}^{d}$，

1. 应用随机旋转矩阵 $r(x) = Rx$，其中 $R \in \mathbb{R}^{d\times d}$，
2. 将 $r(x)$ 标量量化为 $d$ 维的 8 位整数向量 $c(x) \in \{0, 1, \dots, 255\}^d$。

我们通过取 $r(x)$ 中最大值和最小值之间的区间，并将其划分为 256 个等间隔的点（包括端点）来量化旋转向量。然后，将每个条目量化为该区间上的最近点。用数学符号表示为

$$c(x)_i = \left\lfloor \frac{r(x)_i - l_x}{\Delta_x} + 0.5 \right \rfloor \text{where} \\ l_x = \min_i r(x)_i, \quad \Delta_x = \frac{\max_i r(x)_i - \min_i r(x)_i}{255}.$$

值 $l_x$ 是量化区间的下端点，$\Delta_x$ 是由 $c(x)_i.$ 表示的值之间的步长。第 $i$ 个量化向量的条目表示该值

$$\bar{x}_i = l_x + \Delta_x c(x)_i$$

在旋转后的空间中。总结如下：向量的量化表示由 8 位向量 $c(x)$ 和两个标量 $l_x, \Delta_x$ 组成，我们将其存储为 32 位浮点值。此外，我们还存储平方欧几里得范数 $\lVert x \rVert_{2}^{2}$ 作为 32 位浮点数，以便支持欧几里得空间中的距离计算。

与 RaBitQ 编码相比，我们在量化向量之前不会将向量围绕簇中心居中。居中是一种非常有效的提高大多数数据集上量化距离估计准确性的方法，特别是那些自然聚类的数据集。与其量化整个向量，不如量化向量与其最近的簇中心之间的差异，从而减少量化误差。我们的内部测试表明，仅围绕几个 k-means 簇中心居中数据点通常可以将召回率提高高达增加量化码长度 1-2 位。不幸的是，居中会使量化算法复杂化，因为需要学习中心，并且可能会受到数据漂移的影响。

如我们下面的实验所示，即使没有居中，我们也能在使用 8 位码时获得非常高的召回率值，但在更高的压缩率（例如 4 位甚至 1 位码）下，居中在产生良好的召回率方面变得相对重要。

压缩向量之间的内积估计

对于在 距离度量 中最常用于 向量搜索 的上下文，估计向量 $q, x$ 之间的距离归结为估计它们的内积 $\left< q, x \right>$。随机旋转的一个很好的性质是它们保持向量的长度和内积，因此我们有：

$$\left<q, x\right> = \left<r(q), r(x)\right>$$

我们可以专注于使用旋转和量化的向量。为了支持快速 SIMD 优化的单向量距离估计，我们对查询向量和数据向量进行对称的 8 位量化，并估计 $\left< q, x \right>$ 通过计算旋转和量化向量的内积

$$\begin{align*} \hat{\left<q, x\right>} = \left<\bar{q}, \bar{x}\right> &= \sum_i (l_q + \Delta_q c(q)_i)(l_x + \Delta_x c(x)_i) \\ &= d l_q l_x + l_q \Delta_x \sum_i c(x)_i + l_x \Delta_q \sum_i c(q)_i + \Delta_q \Delta_x\sum_i c(q)_i c(x)_i . \end{align*}$$

内部乘积估计器中的前三个项可以使用很少的浮点运算来计算，因为求和 $\sum_i c(x)_i$ 和 $\sum_i c(q)_i$ 可以预先计算并与量化向量一起存储。计算 d 维无符号 8 位整数向量的内积 $\left< c(q), c(x) \right> = \sum_i c(q)_i c(x)_i$ 在上述第四项中是估计距离时最耗时的操作。通过利用针对字节的内积的 SIMD 优化实现，我们能够每秒执行数千万到数亿次的距离估计。

goos: darwin
goarch: arm64
pkg: github.com/weaviate/weaviate/adapters/repos/db/vector/compressionhelpers
cpu: Apple M4 Pro
d64-Uncompressed       6.89  ns/op      145.2  m.ops/sec
d64-8BitRQ             5.49  ns/op      182.2  m.ops/sec
d256-Uncompressed     18.22  ns/op       54.9  m.ops/sec
d256-8BitRQ            8.06  ns/op      124.1  m.ops/sec
d1024-Uncompressed    51.27  ns/op       19.5  m.ops/sec
d1024-8BitRQ          21.02  ns/op       47.6  m.ops/sec
d1536-Uncompressed    73.88  ns/op       13.5  m.ops/sec
d1536-8BitRQ          32.36  ns/op       30.9  m.ops/sec
d3072-Uncompressed   145.90  ns/op        6.9  m.ops/sec
d3072-8BitRQ          60.55  ns/op       16.5  m.ops/sec

基准测试结果表明，与使用 float32 值未压缩向量计算距离相比，使用 8 位旋转量化进行距离估计可实现约 2.3 倍的速度提升。通过显著加快距离估计速度，我们可以在花费更少时间的同时执行更多估计，从而为向量搜索的质量和速度的整体改进铺平道路，前提是我们不会因量化而损失过多的召回率。

上述基准测试是在配备 ARM Neon SIMD 支持的 M4 MacBook 上运行的。Weaviate 支持 Intel 和 AMD 架构的 SIMD，并在支持 ARM 平台（如 Graviton）上的情况下使用更新的 SVE SIMD 指令。要查看您自己的设置中获得的性能，您可以克隆 Weaviate 仓库 并从根目录运行以下命令

 go test -bench=BenchmarkRQDistancer -run=^$ ./adapters/repos/db/vector/compressionhelpers

将我们的 8 位旋转量化方案及其伴随的估计器与 RaBitQ 进行比较，我们的点积估计在理论上并不能保证无偏。我们可以通过使用标量量化中的随机化舍入来使估计器无偏，但我们在实验中发现它会导致召回率略微下降（本质上，它对应于对旋转向量添加噪声）。

实验结果

向量量化算法最终的好坏取决于它提供的召回率水平。我们定义 recallk@m 为包含在搜索返回的前 m 个候选者中的真实 k 个最近邻的比例。对于 8 位旋转量化等相对低压缩技术，我们期望几乎完美的召回率。下表显示了在不同数据集上使用量化代码执行暴力 kNN 搜索时，旋转量化与二进制量化和标量量化在 recall10@10（括号中给出 recall10@20 值）方面的比较。在原始数据集大小超过一百万的情况下，我们已从数据集中随机采样一百万个向量。每行中的最高（最佳）召回率值以粗体标记。

数据集	向量数量	向量维度	1 位二进制量化 recall10@10 (recall10@20)	8 位标量量化 recall10@10 (recall10@20)	8 位旋转量化 recall10@10 (recall10@20)
SIFT	1M	128	0.02 (0.02)	98.46 (100.00)	96.42 (100.00)
GIST	1M	960	0.02 (0.02)	95.66 (100.00)	96.62 (100.00)
GLOVE	1M	200	19.78 (26.74)	93.92 (99.96)	98.82 (100.00)
DBPEDIA	1M	1536	66.32 (84.22)	94.76 (99.98)	99.02 (100.00)
SPHERE	1M	768	45.32 (55.98)	93.98 (99.92)	98.22 (100.00)
MSMARCO	1M	768	60.90 (78.18)	98.74 (100.00)	99.40 (100.00)

结果表明，旋转量化提供良好的 recall10@10 和完美的 recall10@20，在所有数据集上均优于标量量化，除了 SIFT 之外，并且提供二进制量化缺乏的跨数据集一致性。我们在高维向量嵌入数据集（如 MSMARCO (SNOWFLAKE ARCTIC-M-1.5) 和 DBPEDIA (OPENAI ADA-002)）上看到的较高召回率值（>99%）尤其反映了典型的用例。

孤立地查看召回率可以很好地指示量化方法的可行性，但即使是完美的召回率如果没有速度也是无用的！为了评估 8 位旋转量化与 Weaviate 的 HNSW 索引一起使用时的速度-质量权衡，我们以 ANN-Benchmarks 风格绘制了召回率与吞吐量（以每秒查询数 (QPS) 为单位）的关系。

图：使用 Weaviate 的 HNSW 索引在 100 万个 1536 维 OpenAI 嵌入（DBPEDIA (OPENAI ADA-002)）上进行 kNN 搜索时，召回率与吞吐量的关系。未压缩和 8 位 RQ 无重分数的召回率数字为 recall10@10，而 8 位 RQ 有重分数为 recall10@20（对前 20 个候选者进行重分）。

我们比较了使用未压缩向量与使用 100 万个 1536 维 OpenAI 嵌入在余弦相似度下进行旋转量化的性能，并使用了 EF 参数，该参数用于平衡搜索质量和速度。测量是在不同的 EF 值下进行的。

对于 kNN 查询，重分（或超取）意味着我们最初根据量化距离找到前 m 个最佳候选者，然后使用未压缩向量重新计算这些 m 个候选者的距离估计值，以生成最终的 k 个候选者列表。这可以提高召回率，但会付出代价，因为必须从存储中检索未压缩向量，并且我们必须执行 m 次精确距离计算。

将不进行重分数的 8 位旋转量化与使用未压缩向量进行比较，我们看到吞吐量（QPS）提高了 15-50%，而所有测量中的召回率下降小于一个百分点，EF 值相同。对于带有重分数的 8 位旋转量化，我们不会损失任何召回率，与未压缩向量相比，但由于重分，性能会下降。但是，当我们进入高召回率范围，距离计算占搜索过程中花费时间较大比例时，我们看到吞吐量比未压缩向量提高了 5-42%（例如，未压缩向量的召回率为 99.41%，QPS 为 1927，而带有重分数的 RQ 的召回率为 99.41%，QPS 为 2738）。

在吞吐量与召回率的图中考虑每种算法相关的曲线，我们有，位于另一点上方和右方的每个点都代表帕累托改进，因为它提高了吞吐量或召回率或两者。如果我们结合 8 位旋转量化（有和没有重分数）曲线的最佳部分，以便我们在低召回率范围内使用不带重分数的旋转量化，在高召回率范围内使用带重分数的旋转量化，我们看到与使用未压缩向量相比，整体改进。我们能够将向量压缩 4 倍，同时提高吞吐量和召回率！

随机旋转的普遍力量：使每个向量都适合标量量化

如上文实验所示，在向量量化之前对其进行随机旋转往往可以减少量化误差并提高召回率。在这里，我们将尝试提供一些关于为什么会这样直观的解释。

在D维单位球上均匀随机的点，其分布遵循一个由独立同分布的标准正态随机变量构成，并归一化到单位长度的向量。

$$x = \frac{1}{\lVert z \rVert_2 }(z_1, z_2, \dots, z_D), z_i \sim \mathcal{N}(0,1).$$

对一个（单位）向量应用随机旋转后，它将遵循上述精确的分布，因为旋转后它将在球面上均匀随机的位置。请注意，这适用于每个输入向量，无论其条目如何分布。

If we take a closer look at how the entries of the rotated vectors are distributed we note that the normalization term $\lVert z \rVert_{2}$ will be tightly concentrated around $\sqrt{D}$ as $D$ grows. So for $D \geq 64$ we can essentially treat the entries of the rotated vector as being distributed according to $z_i/\sqrt{D}$ where $z_i \sim \mathcal{N}(0,1)$. The normal distribution is tightly distributed with exponentially decaying tails. With probability at least 0.999 we have that $z_i \in [-3.3, 3.3]$. If for example we consider a 1024-dimensional unit vector it could take the form $x = (1, 0, \dots, 0)$ prior to being rotated, but after applying a random rotation it is very unlikely that an entry would have an absolute value larger than approximately 0.15. Also, if we look at the Manhattan (L1) norm of a rotated unit vector (the sum of absolute values of entries) it is guaranteed to be concentrated around $\sqrt{D}$ so in our 1024-dimensional example we have that $\lVert r(x) \rVert_1 \approx 32$ compared to the unrotated vector that has $\lVert x \rVert_1 = 1$. This gives us a lot more mass to scalar quantize which helps improve the accuracy of the quantization.

为了可视化将随机旋转应用于一对64维单位向量 $x, y$ 的效果，请考虑下图

图：64维单位向量 $x, y$ 的条目的散点图，相关性为 $\left<x, y\right> = 0.71$。

向量 $x$ 和 $y$ 具有两个较大的相关条目（左图右上和左下对角线上的条目对），而其余条目是随机噪声。在左图和右图中，网格线表示使用3位量化（8个不同的值）时的标量量化值。

请注意，应用旋转后，量化间隔的长度几乎减半，并且条目分布在间隔的整个长度上（尽管不是均匀分布）。两个向量的曼哈顿范数也增加了，使得使用标量量化更容易捕获它们的相关性信息。

应用随机旋转为标量量化提供了普遍的鲁棒性。随机旋转一个向量后，它将以极高的概率适合于标量量化。这具有普遍性，适用于每个向量，独立于向量的位置或其所属数据集中的任何结构。

如果我们不应用随机旋转，我们就有可能使一个向量不适合于标量量化，从而导致在执行距离估计时产生更大且更可变的误差。例如，如果向量具有大条目和小条目的混合，这会增加量化间隔。

为此鲁棒性付出的代价是，我们有时可能会在旋转和量化向量时丢失信息。例如，如果输入向量已经过量化，那么通过旋转和重新量化我们将丢失一些信息。

总而言之，应用随机旋转具有以下三个相互关联的对量化有益的效果

1. 它使向量中的条目平滑，保证了短的量化间隔。
2. 它保持了欧几里得范数，同时保证了大的曼哈顿范数，这转化为更多的质量进行量化，以及在标量量化中更多的信息。
3. 它随机地将相似性信息重新分布到所有维度，从而提高估计精度。

来自 RaBitQ 到旋转量化：使向量量化足够快

扩展的 RaBitQ 量化算法（论文，博客文章，仓库）通过对向量进行居中和归一化，然后随机旋转它们并对其与位于单位球表面的码点集中最近的邻居进行编码来工作。码本的设计方式非常巧妙，具有多种用途：码点在单位球上分布良好，提供良好的量化属性。码点是 B 位整数的缩放向量，支持快速距离估计。最后，作者提出了一种高效的编码算法，可以使用 $O(2^B D \log D)$ 个操作来查找旋转向量到 D 维向量的最近码点。

我们最初用 Go 创建了一个扩展的 RaBitQ 实现，但我们发现为了使它对我们的用例足够快，我们必须对该算法进行两个主要修改。

1. 用我们自己快速伪随机旋转的实现替换随机旋转。
2. 用简单的 8 位标量量化替换扩展的 RaBitQ 量化。

由于我们对查询和数据向量都使用 8 位编码，因此我们必须在开始导航图并估计距离之前旋转和编码查询向量。为了大致了解我们能够在量化上花费的时间，以便与使用未压缩向量竞争，假设我们希望运行查询的每个线程至少支持每秒 1000 个查询（实际数字略高）。这为我们提供了每个查询 1000 微秒的时间。如果我们将 10% 的时间用于量化查询，那么我们只有 100 微秒的时间来旋转和编码查询向量。

下表概述了对 1536 维 float32 值向量执行不同操作的运行时间。我们看到，我们的 100 µs 预算大致对应于使用 Golang 标准库中的 slices.sort 测量向量排序所需的时间。

操作	1536 维向量的运行时间
量化预算	100 µs
排序	60 µs
随机旋转（矩阵-向量乘法）	1 700 µs
RQ 快速伪随机旋转	7 µs
扩展的 RaBitQ 8 位编码	≥4 000 µs
RQ 8 位编码（标量量化）	2 µs
采样随机旋转矩阵	10 000 000 µs
采样快速伪随机旋转	150 µs

随机旋转对应于将向量乘以旋转矩阵。该操作的复杂度为 $O(D^2)$，而排序的复杂度为 $O(D \log D)$。这种差异在我们的基准测试中也很明显，使用 gonum 进行的密集矩阵-向量乘法耗时 1700 µs。这表明使用真正的随机旋转是不可行的，即使我们可以将其加速 10 倍。随机旋转的另一个缺点是它们既昂贵又难以采样和存储。

通过开发基于 快速沃尔什-哈达玛变换（在下面的部分中更详细地描述）的定制快速伪随机旋转，我们能够将旋转 1536 维向量的时间减少到仅 7 微秒（速度提升 200 倍！），而不会在我们的基准测试中损失任何召回率。

更大的挑战在于扩展的 RaBitQ 编码的复杂性，因为它随编码位的数量呈指数级增长。使用 RaBitQ 算法将旋转后的向量编码为 $B$ 位表示涉及 $2^{B}D/2$ 次插入到优先级队列中。即使高度优化的优先级队列实现也至少需要 ~20ns 的插入时间，因此在 8 位情况下，仅此编码算法的这一方面就需要至少 4000 µs 的 1536 维向量，从而使该方法不可行。

鉴于 RaBitQ 编码算法的这种限制，我们选择使用上面描述的简单标量量化。标量量化可以在对旋转后的向量进行几次扫描后完成，并花费约 2 微秒。

开发快速伪随机旋转

使用矩阵-向量乘法进行真正随机旋转的 $O(D^2)$ 复杂度对于高维嵌入向量来说扩展得太快，无法实现。幸运的是，存在更快的基于 快速沃尔什-哈达玛变换（FWHT）的伪随机旋转，其复杂度为 $O(D \log D)$，在实践中速度很快，并且在我们的用例中与真正的随机旋转一样有效。沃尔什-哈达玛变换的递归定义为

$$H_D = \frac{1}{\sqrt{2}} \begin{bmatrix} H_{D/2} & H_{D/2} \\ H_{D/2} & -H_{D/2} \end{bmatrix} \text{ 其中 } H_1 = \begin{bmatrix} 1\end{bmatrix}.$$

设 $S_D$为一个 $D\times D$对角符号矩阵，其随机条目从 $\{-1, +1\}$均匀抽取。在介绍 快速 Johnson Lindenstrauss 变换的开创性论文中，证明了应用距离保持变换 $H_D S_D$到 D 维向量具有与随机旋转相同的“平滑”属性。为了理解这一点，请注意变换的每一行都采用以下形式 $(H_D S_D)_i,. = (\pm/\sqrt{D}, \pm/\sqrt{D}, \dots, \pm/\sqrt{D})$因此，变换向量中的每个条目是小于等于 $\pm \lVert x \rVert_2 / \sqrt{D}$

通过应用多个这样的变换，例如 $H_D S^{(1)}_D H_D S^{(2)}_D H_D S^{(3)}_Dx$，并使用每次应用时新的随机符号，输出开始看起来像一个随机旋转的向量。这也可以通过中心极限定理的视角来理解：应用一次变换后，向量将被平滑，并且随着后续变换，条目是有限变量的随机和，因此开始类似于正态分布。应用此技术是为了在 FALCONN 库中获得用于局部敏感哈希的快速伪随机投影。

快速沃尔什-哈达玛变换的一个主要缺点是它仅支持维度是 2 的幂次方，即 $D = 2^k$，其中 k 是某个正整数。我们可以通过将输入向量填充到最接近的 2 的幂次方来规避此限制，但这几乎会将维度翻倍，这与我们量化向量以节省内存的目标背道而驰。

为了支持所有输入大小的伪随机旋转，我们开发了以下方法

1. 将输入向量填充为 2 的幂的倍数，例如 32 的倍数。
2. 随机交换输入向量的元素并应用随机符号。
3. 沿向量长度分块地贪婪地应用尽可能长的 FWHT，直到整个向量被变换。
4. 重复上述步骤三次。

随机符号和 FWHT 有助于平滑各个块内的向量条目，同时保持长度和距离。在每个块平滑处理轮次之间，我们随机交换块之间的元素，从而最终获得全局平滑效果，因为质量会在交换条目时随机地在块之间重新分配。

请注意，理论上讲，应用伪随机旋转前后向量之间的距离保持完全相同，但在实践中，我们会在每次旋转轮次中引入一些浮点误差。与 8 位量化引入的误差相比，此误差可以忽略不计，但值得注意的是，每次旋转向量时都会引入一些微小的误差。

图：对 224 维向量进行一轮快速伪随机旋转的说明。

为了进一步加速伪随机旋转，我们将阻塞 FWHT 限制为 256 或 64，并提供这些函数的优化和循环展开实现。

为了了解旋转后单元向量条目的外观，请考虑下图，该图绘制了应用 1-4 轮旋转后 1536 维单元向量 $x = (1, 0, \dots, 0)$ 的条目的直方图。我们看到，在三轮之后，输出看起来基本上呈正态分布，正如预期的那样。

图：应用 1-4 轮伪随机旋转后 1536 维单元向量的条目。

对快速伪随机旋转进行基准测试表明，它足够快，不会成为使用 HNSW 索引进行 ANN 查询的瓶颈。我们使用 3 轮旋转和 8 位旋转量化，因此旋转 1536 维向量需要约 7 µs，如基准测试所示。

goos: darwin
goarch: arm64
pkg: github.com/weaviate/weaviate/adapters/repos/db/vector/compressionhelpers
cpu: Apple M4 Pro
dim128-rounds1             203 ns/op
dim128-rounds3             471 ns/op
dim128-rounds5             741 ns/op
dim512-rounds1             945 ns/op
dim512-rounds3            2322 ns/op
dim512-rounds5            3737 ns/op
dim1024-rounds1           1871 ns/op
dim1024-rounds3           4626 ns/op
dim1024-rounds5           7397 ns/op
dim1536-rounds1           2753 ns/op
dim1536-rounds3           6929 ns/op
dim1536-rounds5          11628 ns/op

结论

我们提出了 8 位旋转量化：我们新的快速 8 位标量量化方法，它利用了随机旋转的力量。该算法受最近的 RaBitQ 和 Extended RaBitQ 量化方法的启发，但不同之处在于它未经训练，并针对 Weaviate 的 HNSW 索引进行了优化。为了使该算法足够快以满足我们的用例，我们必须仔细选择标量量化算法并开发快速伪随机旋转。

将 8 位旋转量化与 Weaviate 的 HNSW 索引结合使用，我们同时改进了内存使用量、搜索速度和搜索质量，表明旋转量化是与使用未压缩向量相比更好的默认选择。

未来工作

我们目前正在开发旋转量化的 1 位版本，该版本将提供 32 倍的压缩率。在高压缩场景中，从中心化向量中获得的相对收益大于低压缩场景。我们正在试验向量化器添加在线中心化支持，以便以稳健的方式提高召回率，而无需用户手动配置量化器的训练步骤。

如何试用旋转量化

最后，我们鼓励您试用 8 位旋转量化（受 Weaviate 1.32 版本及更高版本支持），以期改善您数据的向量搜索的速度-质量权衡。在 Weaviate 中启用旋转量化就像编写几行代码一样简单。在启用 8 位旋转量化后，我们建议 调整 rescoreLimit 参数 和/或 更改 HNSW 索引的 EF 参数 以进一步调整速度-质量权衡，但默认设置在大多数情况下都应该可以很好地工作。

准备开始构建了吗？

请查看 快速入门教程，或使用 Weaviate Cloud (WCD) 的免费试用版构建令人惊叹的应用程序。

GitHub

论坛

Slack

X (Twitter)

不想错过另一篇博文？

注册我们的双周时事通讯以保持更新！

提交后，我同意 服务条款和 隐私政策.