RAG 原理ANN 近似最近邻搜索与聚类索引本节解决一个核心问题当知识库中存在百万甚至千万级向量时如何在可接受的时间内找到与查询最相似的 Top K 向量。一、从最近邻搜索说起在 RAG 中文档块与用户问题都会被 Embedding 模型转换为向量。检索阶段需要在向量库中寻找与查询向量最接近的若干向量这就是最近邻搜索Nearest Neighbor Search。常见距离度量包括欧氏距离L2距离越小向量越接近余弦相似度夹角越小相似度越高内积Inner Product经常用于已归一化的向量。如果逐个计算查询向量与全部向量的距离可以得到精确结果但其计算复杂度约为O(N×d) O(N \times d)O(N×d)其中NNN是向量数量ddd是向量维度。数据规模扩大后暴力搜索的延迟会迅速上升。二、KNN 与 ANN 的区别方式核心思想优点局限精确 KNN比较查询向量与全部向量结果精确、召回率高大数据量下计算成本高ANN只搜索最可能包含近邻的候选区域检索快、适合大规模数据结果是近似值可能漏召回**ANNApproximate Nearest Neighbor近似最近邻**并不是某一种固定算法而是一类搜索方法。它用少量精度损失换取显著的速度提升。工程上没有“速度最快且结果绝对精确”的免费方案ANN 的本质是在检索速度、召回率、内存和建索引成本之间取平衡。三、聚类索引的基本思路暴力搜索慢是因为搜索范围等于整个向量库。聚类索引的优化思路是先缩小范围再在候选范围内精细搜索。1. 构建索引使用 K-Means 等算法训练若干聚类中心Centroid将每个数据库向量分配给距离最近的聚类中心为每个簇保存对应的向量列表也称倒排列表Inverted List。全部向量 │ ├── 簇 C1v1、v5、v9 ... ├── 簇 C2v2、v4、v8 ... └── 簇 C3v3、v6、v7 ...2. 执行查询查询向量 q ↓ 计算 q 与各聚类中心的距离 ↓ 选择最近的若干个簇 ↓ 仅在这些簇中计算精确距离 ↓ 返回 Top K 结果如果总共有NNN个向量而候选簇中只有MMM个向量那么精细搜索的范围就从NNN缩小到了MMM。四、为什么会出现漏召回只搜索一个最近簇时查询向量可能位于两个簇的边界查询向量距离蓝色簇中心更近因此被分配到蓝色簇但它真正的最近邻可能位于旁边的黄色簇如果只搜索蓝色簇就会漏掉正确结果。解决方法是同时探测多个相邻簇。在 IVF 索引中这个数量通常由nprobe控制nprobe较小扫描的簇少速度快但可能漏召回nprobe较大扫描的簇多召回率更高但延迟随之增加当扫描范围接近全量数据时ANN 的速度优势会逐渐消失。五、局部敏感哈希 LSH普通哈希函数希望尽量减少碰撞而 **局部敏感哈希Locality Sensitive HashingLSH**恰好利用碰撞向量越相似被映射到同一个桶Bucket的概率越高。查询时先计算查询向量的哈希值再到对应桶或相邻桶中搜索从而减少需要比较的向量数量。对比项普通哈希LSH目标尽量避免碰撞让相似数据更容易碰撞数据组织哈希表键值定位相似向量分桶查询结果精确定位近似候选集合聚类索引和 LSH 的共同点都是先把海量向量划分到较小的候选区域再执行更细粒度的比较。六、FAISS 聚类索引示例下面使用IndexIVFFlat演示“训练聚类中心 → 添加向量 → 搜索多个簇”的过程。pipinstallfaiss-cpu numpyimportfaissimportnumpyasnp rngnp.random.default_rng(42)dimension128database_size100_000query_size5top_k5nlist256database_vectorsrng.random((database_size,dimension),dtypenp.float32)query_vectorsrng.random((query_size,dimension),dtypenp.float32)# 1. 使用 L2 距离创建粗量化器quantizerfaiss.IndexFlatL2(dimension)# 2. 创建 IVF_FLAT 索引indexfaiss.IndexIVFFlat(quantizer,dimension,nlist,faiss.METRIC_L2,)# 3. IVF 索引必须先训练聚类中心index.train(database_vectors)# 4. 将数据库向量分配到各个倒排列表index.add(database_vectors)# 5. 查询时探测的簇数量index.nprobe8distances,idsindex.search(query_vectors,top_k)print(近邻 ID)print(ids)print(L2 距离)print(distances)关键参数dimension向量维度nlist聚类中心数量也就是倒排列表数量nprobe每次查询探测的簇数量top_k最终返回的近邻数量。nlist不是越大越好。簇数增加会缩小单簇搜索范围但也会增加训练、维护及选择聚类中心的成本。七、如何评估 ANNANN 不能只看查询耗时还要与精确搜索结果对比。常用指标为RecallKRecallK∣ANN TopK∩Exact TopK∣K RecallK \frac{|ANN\ TopK \cap Exact\ TopK|}{K}RecallKK∣ANNTopK∩ExactTopK∣建议同时观察RecallK正确近邻被召回的比例Latency单次查询延迟QPS每秒可处理的查询数Memory索引与原始向量的内存占用Build Time索引训练和构建耗时。一种实用调参方式是先使用精确 KNN 生成测试集的标准答案再逐步调整nlist、nprobe等参数找到满足业务召回率要求的最低延迟配置。八、常见 ANN 路线路线代表方法特点基于聚类IVF、IVF_FLAT候选范围直观参数易理解基于哈希LSH通过相似碰撞实现分桶基于图HNSW查询速度快、召回率高但图索引占用内存基于量化PQ、IVF_PQ压缩向量降低内存和距离计算成本本节重点是聚类索引和 LSHPQ 与 HNSW 属于其他常见优化路线。九、实践建议小数据集优先使用精确搜索系统更简单且结果稳定数据量增大后再引入 ANN不要为了“高级”而提前增加复杂度Embedding 模型、归一化方式与距离度量必须保持一致调参应以真实业务查询集为准不能只看随机向量测试对高召回要求的场景可先通过 ANN 召回较大的候选集再使用精确距离或重排序模型进行二次排序新数据持续写入时需要关注索引增量更新、重建和数据分布漂移。十、小结ANN 的核心不是“算得更准”而是“少算一些”。聚类索引先用聚类中心确定候选区域再在少量候选向量中执行距离计算LSH 则利用相似向量更容易碰撞的特性进行分桶。它们都通过缩小搜索范围以可控的召回损失换取更低延迟。在 RAG 中正确的工程目标不是盲目追求某个索引算法而是在真实数据与查询负载下找到召回率、速度、内存和成本的最佳平衡点。 RAG原理-ANN近似最近邻搜索和聚类索引
RAG 原理ANN 近似最近邻搜索与聚类索引本节解决一个核心问题当知识库中存在百万甚至千万级向量时如何在可接受的时间内找到与查询最相似的 Top K 向量。一、从最近邻搜索说起在 RAG 中文档块与用户问题都会被 Embedding 模型转换为向量。检索阶段需要在向量库中寻找与查询向量最接近的若干向量这就是最近邻搜索Nearest Neighbor Search。常见距离度量包括欧氏距离L2距离越小向量越接近余弦相似度夹角越小相似度越高内积Inner Product经常用于已归一化的向量。如果逐个计算查询向量与全部向量的距离可以得到精确结果但其计算复杂度约为O(N×d) O(N \times d)O(N×d)其中NNN是向量数量ddd是向量维度。数据规模扩大后暴力搜索的延迟会迅速上升。二、KNN 与 ANN 的区别方式核心思想优点局限精确 KNN比较查询向量与全部向量结果精确、召回率高大数据量下计算成本高ANN只搜索最可能包含近邻的候选区域检索快、适合大规模数据结果是近似值可能漏召回**ANNApproximate Nearest Neighbor近似最近邻**并不是某一种固定算法而是一类搜索方法。它用少量精度损失换取显著的速度提升。工程上没有“速度最快且结果绝对精确”的免费方案ANN 的本质是在检索速度、召回率、内存和建索引成本之间取平衡。三、聚类索引的基本思路暴力搜索慢是因为搜索范围等于整个向量库。聚类索引的优化思路是先缩小范围再在候选范围内精细搜索。1. 构建索引使用 K-Means 等算法训练若干聚类中心Centroid将每个数据库向量分配给距离最近的聚类中心为每个簇保存对应的向量列表也称倒排列表Inverted List。全部向量 │ ├── 簇 C1v1、v5、v9 ... ├── 簇 C2v2、v4、v8 ... └── 簇 C3v3、v6、v7 ...2. 执行查询查询向量 q ↓ 计算 q 与各聚类中心的距离 ↓ 选择最近的若干个簇 ↓ 仅在这些簇中计算精确距离 ↓ 返回 Top K 结果如果总共有NNN个向量而候选簇中只有MMM个向量那么精细搜索的范围就从NNN缩小到了MMM。四、为什么会出现漏召回只搜索一个最近簇时查询向量可能位于两个簇的边界查询向量距离蓝色簇中心更近因此被分配到蓝色簇但它真正的最近邻可能位于旁边的黄色簇如果只搜索蓝色簇就会漏掉正确结果。解决方法是同时探测多个相邻簇。在 IVF 索引中这个数量通常由nprobe控制nprobe较小扫描的簇少速度快但可能漏召回nprobe较大扫描的簇多召回率更高但延迟随之增加当扫描范围接近全量数据时ANN 的速度优势会逐渐消失。五、局部敏感哈希 LSH普通哈希函数希望尽量减少碰撞而 **局部敏感哈希Locality Sensitive HashingLSH**恰好利用碰撞向量越相似被映射到同一个桶Bucket的概率越高。查询时先计算查询向量的哈希值再到对应桶或相邻桶中搜索从而减少需要比较的向量数量。对比项普通哈希LSH目标尽量避免碰撞让相似数据更容易碰撞数据组织哈希表键值定位相似向量分桶查询结果精确定位近似候选集合聚类索引和 LSH 的共同点都是先把海量向量划分到较小的候选区域再执行更细粒度的比较。六、FAISS 聚类索引示例下面使用IndexIVFFlat演示“训练聚类中心 → 添加向量 → 搜索多个簇”的过程。pipinstallfaiss-cpu numpyimportfaissimportnumpyasnp rngnp.random.default_rng(42)dimension128database_size100_000query_size5top_k5nlist256database_vectorsrng.random((database_size,dimension),dtypenp.float32)query_vectorsrng.random((query_size,dimension),dtypenp.float32)# 1. 使用 L2 距离创建粗量化器quantizerfaiss.IndexFlatL2(dimension)# 2. 创建 IVF_FLAT 索引indexfaiss.IndexIVFFlat(quantizer,dimension,nlist,faiss.METRIC_L2,)# 3. IVF 索引必须先训练聚类中心index.train(database_vectors)# 4. 将数据库向量分配到各个倒排列表index.add(database_vectors)# 5. 查询时探测的簇数量index.nprobe8distances,idsindex.search(query_vectors,top_k)print(近邻 ID)print(ids)print(L2 距离)print(distances)关键参数dimension向量维度nlist聚类中心数量也就是倒排列表数量nprobe每次查询探测的簇数量top_k最终返回的近邻数量。nlist不是越大越好。簇数增加会缩小单簇搜索范围但也会增加训练、维护及选择聚类中心的成本。七、如何评估 ANNANN 不能只看查询耗时还要与精确搜索结果对比。常用指标为RecallKRecallK∣ANN TopK∩Exact TopK∣K RecallK \frac{|ANN\ TopK \cap Exact\ TopK|}{K}RecallKK∣ANNTopK∩ExactTopK∣建议同时观察RecallK正确近邻被召回的比例Latency单次查询延迟QPS每秒可处理的查询数Memory索引与原始向量的内存占用Build Time索引训练和构建耗时。一种实用调参方式是先使用精确 KNN 生成测试集的标准答案再逐步调整nlist、nprobe等参数找到满足业务召回率要求的最低延迟配置。八、常见 ANN 路线路线代表方法特点基于聚类IVF、IVF_FLAT候选范围直观参数易理解基于哈希LSH通过相似碰撞实现分桶基于图HNSW查询速度快、召回率高但图索引占用内存基于量化PQ、IVF_PQ压缩向量降低内存和距离计算成本本节重点是聚类索引和 LSHPQ 与 HNSW 属于其他常见优化路线。九、实践建议小数据集优先使用精确搜索系统更简单且结果稳定数据量增大后再引入 ANN不要为了“高级”而提前增加复杂度Embedding 模型、归一化方式与距离度量必须保持一致调参应以真实业务查询集为准不能只看随机向量测试对高召回要求的场景可先通过 ANN 召回较大的候选集再使用精确距离或重排序模型进行二次排序新数据持续写入时需要关注索引增量更新、重建和数据分布漂移。十、小结ANN 的核心不是“算得更准”而是“少算一些”。聚类索引先用聚类中心确定候选区域再在少量候选向量中执行距离计算LSH 则利用相似向量更容易碰撞的特性进行分桶。它们都通过缩小搜索范围以可控的召回损失换取更低延迟。在 RAG 中正确的工程目标不是盲目追求某个索引算法而是在真实数据与查询负载下找到召回率、速度、内存和成本的最佳平衡点。