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

教案 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-Karg,max⁡i;sim(vq,vi)][ \text{Top-K} \operatorname*{arg,max}_i ; sim(\mathbf{v}_q, \mathbf{v}_i) ][Top-Karg,maxi​;sim(vq​,vi​)]常用相似度1️⃣ 余弦相似度[simvq⋅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 等结构失效五、解决方案ANNApproximate 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️⃣ PQProduct Quantization核心思想将向量分块[ v1 | v2 | v3 | v4 ]每块量化用码本表示 压缩存储 快速距离计算优点极大减少内存支持大规模数据九、FAISS工业实现Facebook 提供FAISS IVF PQ HNSW组合方式结构作用IVF减少搜索范围PQ压缩HNSW加速搜索十、完整查询流程工程用户输入 ↓ Embedding模型 ↓ 向量 q ↓ ANN 检索FAISS ↓ 候选 Top-K ↓ 可选BM25 / rerank ↓ 返回结果十一、与传统搜索融合关键现代系统BM25 向量检索两种方式1️⃣ 并行召回BM25 → Top-K1 ANN → Top-K2 合并2️⃣ 重排序rerankBM25 召回 → 用向量排序十二、工程关键指标1️⃣ Recall召回率找到多少真实 Top-K2️⃣ Latency延迟3️⃣ Memory内存 三者必须平衡十三、本质总结严肃表达向量检索通过将数据映射到高维连续空间并利用近似最近邻搜索算法在可控误差范围内高效定位相似向量从而实现语义级别的信息检索其性能依赖于空间划分策略、图结构设计及向量压缩技术。