每天学一个算法--向量检索

📘 教案 28：向量检索（Embedding + ANN · 工程级）

一、问题模型（从 BM25 的局限出发）

BM25 本质是：

基于“词”的匹配

问题：

• 同义词无法匹配
• 语义无法理解
• 句子级关系缺失

目标升级

给定：

• 查询 ( q )
• 文档集合 ( D )

希望找到：

语义上最相似的文档

数学化表达

将文本映射为向量：

[q→vq∈Rd][ q \rightarrow \mathbf{v}_q \in \mathbb{R}^d ][q→vq​∈Rd]

[di→vi∈Rd][ d_i \rightarrow \mathbf{v}_i \in \mathbb{R}^d ][di​→vi​∈Rd]

目标：

[Top-K=arg,max⁡i;sim(vq,vi)][ \text{Top-K} = \operatorname*{arg,max}_i ; sim(\mathbf{v}_q, \mathbf{v}_i) ][Top-K=arg,maxi​;sim(vq​,vi​)]

常用相似度

1️⃣ 余弦相似度

[sim=vq⋅vi∣∣vq∣∣,∣∣vi∣∣][ sim = \frac{\mathbf{v}_q \cdot \mathbf{v}_i}{||\mathbf{v}_q|| , ||\mathbf{v}_i||} ][sim=∣∣vq​∣∣,∣∣vi​∣∣vq​⋅vi​​]

2️⃣ 欧氏距离

[∣∣vq−vi∣∣][ ||\mathbf{v}_q - \mathbf{v}_i|| ][∣∣vq​−vi​∣∣]

二、暴力方法（不可用）

直接计算：

[O(n⋅d)][ O(n \cdot d) ][O(n⋅d)]

如果：

n = 10^8 d = 768

👉 完全不可行

三、问题本质

在高维空间中寻找“最近邻”

这类问题称为：

[Nearest Neighbor Search (NN)][ \text{Nearest Neighbor Search (NN)} ][Nearest Neighbor Search (NN)]

四、核心难点

高维空间问题

随着维度增加：

距离失去区分度

👉 KD-Tree 等结构失效

五、解决方案：ANN（Approximate Nearest Neighbor）

允许：

近似解（但很接近）

目标：

• 大幅减少计算量
• 牺牲极少精度

六、主流算法体系

1️⃣ 基于图：HNSW（最重要）

核心思想

构建多层图：

上层：稀疏（快速定位） 下层：密集（精确搜索）

搜索过程

Step 1：从顶层开始

随机进入一个点

Step 2：贪心搜索

不断走向“更近的邻居”

Step 3：逐层下降

越来越精细

Step 4：底层 Top-K

复杂度

[O(log⁡n)][ O(\log n) ][O(logn)]

本质

用“图结构”近似高维空间

七、2️⃣ IVF（倒排文件索引）

核心思想

Step 1：聚类（K-Means）

数据分成 K 个中心

Step 2：查询时

只搜索最近的几个簇

优点

• 快
• 可控

缺点

• 精度依赖聚类质量

八、3️⃣ PQ（Product Quantization）

核心思想

将向量分块：

[ v1 | v2 | v3 | v4 ]

每块量化：

用码本表示

👉 压缩存储 + 快速距离计算

优点

• 极大减少内存
• 支持大规模数据

九、FAISS（工业实现）

Facebook 提供：

FAISS = IVF + PQ + HNSW

组合方式：

十、完整查询流程（工程）

用户输入 ↓ Embedding（模型） ↓ 向量 q ↓ ANN 检索（FAISS） ↓ 候选 Top-K ↓ （可选）BM25 / rerank ↓ 返回结果

十一、与传统搜索融合（关键）

现代系统：

BM25 + 向量检索

两种方式：

1️⃣ 并行召回

BM25 → Top-K1 ANN → Top-K2 合并

2️⃣ 重排序（rerank）

BM25 召回 → 用向量排序

十二、工程关键指标

1️⃣ Recall（召回率）

找到多少真实 Top-K

2️⃣ Latency（延迟）

3️⃣ Memory（内存）

👉 三者必须平衡

十三、本质总结（严肃表达）

向量检索通过将数据映射到高维连续空间，并利用近似最近邻搜索算法在可控误差范围内高效定位相似向量，从而实现语义级别的信息检索，其性能依赖于空间划分策略、图结构设计及向量压缩技术。