Inside FAISS: Billion-Scale Similarity Search 深度解读

背景

在现代人工智能（AI）应用中，计算机并不像人类一样通过“猫”或“交响乐”这样的语义概念来理解图像、文本或音频。相反，这些数据被转换为称为**嵌入（Embeddings）或向量（Vectors）**的数字列表。

这些向量存在于高维几何空间中。其核心逻辑非常简单：语义相似的项目在该空间中被放置在一起。例如，“猫”与“狗”在空间中距离较近，而与“汽车”距离较远。我们通常使用欧几里得距离（Euclidean）或余弦相似度（Cosine）来衡量这种距离。

然而，当数据规模达到十亿级别时，传统的精确最近邻搜索（Exact Nearest-Neighbor Search）面临巨大挑战。对于像 Web 规模检索或实时 LLM 记忆这样的系统，暴力计算所有距离在时间和内存上都是不可接受的。例如，存储十亿个 SIFT 描述符（每个 4 字节）需要 512 GB 的 RAM，且每次搜索需进行十亿次距离评估。

为了解决这一瓶颈，FAISS（Facebook AI Similarity Search）引入了近似搜索方法。通过牺牲极少量的准确性（例如找到第二好的匹配而非第一好），FAISS 能够将搜索速度提高几个数量级。其核心策略结合了两种技术：分区（Partitioning）和压缩（Compression）。

核心内容

FAISS 主要通过两种索引策略来优化大规模向量搜索：Flat（暴力搜索）、**IVF（倒排文件）**以及 Product Quantization（乘积量化，PQ）。

1. 暴力搜索与 IVF 分区

Flat Index 是基准的暴力搜索方法，虽然准确但速度慢。

IVF (Inverted File Index) 则引入了分区概念，其工作原理类似于图书馆的分类系统。与其查找每一本书，不如先定位到“科幻小说”区域。

• 数学原理：IVF 使用 K-Means 聚类算法将向量空间划分为 Voronoi 单元（Voronoi cells）。
• 搜索流程：
  1. 首先，使用“粗量化器（coarse quantizer）”确定查询向量落入哪个 Voronoi 单元。
  2. 然后，仅在该单元（以及可能的几个相邻单元）内计算向量间的距离。
  3. 这样，系统可以跳过数据库中绝大部分不相关的向量，从而大幅加速搜索。

2. 乘积量化（Product Quantization, PQ）

虽然 IVF 通过跳过大部分数据库实现了快速搜索，但它并未压缩向量本身。十亿个 SIFT 描述符仍需 512 GB 内存。PQ 由 Jégou、Douze 和 Schmid 于 2011 年提出，是 FAISS 用于压缩向量的核心技术。

• 目标：将每个向量压缩至 8 字节，同时保持距离估计的有效性。
• 类比理解：
  • GIF 图像压缩：24-bit RGB 像素有 1670 万种颜色可能。GIF 通过选择 256 色的调色板（Codebook），将每个像素替换为调色板中的索引（8-bit）。存储量减少 3 倍，但图像看起来依然相似。
  • 向量压缩：128 维的 SIFT 描述符就像是一个“长像素”。PQ 的目标是找到一组代表性的向量（调色板），用其最近邻的调色板索引来替换原始描述符。

3. 为什么不能直接使用单一平铺 Codebook？

若要将 128 维 SIFT 描述符压缩为 64 位代码（即 0.5 位/维度，压缩比 64x），理论上需要 $2^{64}$ 个质心（Centroids）。这是一个天文数字（约 18 百亿亿），面临三大障碍：

1. 存储障碍：每个质心包含 128 个浮点数（512 字节）。$2^{64}$ 个质心的总存储量约为 9.4 Zettabytes，远超 2025 年全球云存储总量，无法持久化存储。
2. 训练数据障碍：Lloyd 算法（K-Means 的一种）需要每个质心至少有数十个样本才能收敛。所需的训练向量数量远超任何现有数据集的规模。
3. 查询成本障碍：编码一个描述符需要将其与所有质心计算距离。每向量 18 百亿亿次距离计算带来的延迟是无法接受的。

4. 乘积量化的“因式分解”技巧

为了解决上述问题，PQ 采用了“因式分解”策略，类似于将图像切成 8 个图块，每个图块拥有自己的 256 色调色板。

• 具体操作：
  1. 将 128 维向量分割成 $M$ 个子向量（Sub-vectors）。在参考设置中，$M=8$，每个子向量包含 16 维。
  2. 为每个子向量块学习一个小型的子量化器（Sub-quantizer）。
  3. 每个子量化器拥有 $K$ 个质心。
• 效果：
  • 虽然有效词汇表（组合数）仍为 $K^M$（与平铺情况同量级），但实际存储的质心向量仅为 $M \times K$ 个。
  • 以 $M=8, K=256$ 为例，代码本大小仅为 $8 \times 256$ 个向量，足以放入 L2 缓存。
  • 每个编码后的向量仅需 $M$ 字节（每块索引 1 字节），即 8 字节。
  • 结果：内存占用从 512 字节降至 8 字节，实现了 64 倍的压缩，且代码本完全可存储在机器内存中。

关键要点

• 向量本质：AI 将非结构化数据（图像、文本）转化为高维空间中的数值向量，语义相似度转化为空间中的几何距离。
• 规模挑战：十亿级向量的精确搜索（Brute Force）在实时系统中不可行，因为内存占用巨大（如 512 GB RAM）且计算开销过高。
• FAISS 策略：FAISS 通过近似搜索（Approximate Search）在精度和速度之间取得平衡，主要依赖 IVF 分区和 PQ 压缩。
• IVF 机制：利用 K-Means 聚类将空间划分为 Voronoi 单元，搜索时仅检查查询向量所在的单元及其邻近单元，跳过无关数据。
• PQ 原理：
  • 将高维向量分割为多个子向量块。
  • 为每个块训练独立的量化器（Codebook）。
  • 用子向量在各自 Codebook 中的索引（整数）替换原始向量数据。
• 压缩效率：PQ 可将 128 维 SIFT 描述符从 512 字节压缩至 8 字节（64x 压缩比），同时保持距离度量的有效性。
• 技术可行性：直接构建包含 $2^{64}$ 质心的平铺 Codebook 因存储、训练数据和查询延迟三大障碍而不可行；PQ 通过分块量化解决了这一难题，使代码本大小适应机器内存。

意义与影响

FAISS 及其背后的 IVF 和 PQ 技术，解决了大规模向量数据库落地的核心瓶颈：内存效率与查询速度。

1. 赋能大规模 AI 应用：使得在有限硬件资源（如单台服务器或小型集群）上运行包含数十亿向量的检索系统成为可能。这对于推荐系统、搜索引擎以及大型语言模型（LLM）的长期记忆模块至关重要。
2. 平衡精度与性能