近似近邻索引：图、分区与量化

先建立精确比较的基线复制锚点链接

对 $N$ 个 $d$ 维向量逐项做内积，计算量与 $Nd$ 成正比，还需读取向量并选择前 $k$ 项。是否满足延迟预算，取决于数据规模、硬件、批处理、并发和存储位置；数据规模本身没有给出统一的可接受阈值。

近似近邻索引减少访问或简化距离计算，允许返回集合偏离同一度量下的精确前 $k$ 项。误差可以来自没访问某个向量，也可以来自压缩后距离排序改变。近似索引可以返回精确前 $k$ 项，也可能遗漏，一般不提供任意查询都与精确结果相同的保证。测试需要保留精确基线、语料版本和度量，另行评价结果对任务是否相关。

HNSW 用分层图导航复制锚点链接

HNSW 为向量建立近邻图：节点是向量，边保存可继续访问的节点。每个节点随机取得一个最高层，进入高层的概率逐渐降低；一个出现在高层的节点也存在于更低层，第 0 层包含全部节点。上层较稀疏，用于较大范围的导航，下层包含更多局部候选。

查询从最高层入口开始，比较当前节点与其邻居，向距离查询更近的节点移动。该层不再找到更近节点时，把当前节点作为下一层的入口。到第 0 层后保留一组候选继续扩展，获得最后的近邻结果。Malkov 与 Yashunin 的 HNSW 原论文，§4 算法 1—5定义了构建、单层搜索和分层查询。

单层搜索需要区分待扩展候选、已发现的较好结果和已访问集合。每次取一个较近的待扩展节点，读取它的邻居；新邻居如果足够接近，加入候选和结果，结果集超过宽度时移除较远项。搜索按其终止规则结束，再从保留结果中取前 $k$ 项。宽度限制影响继续探索哪些路径，不能将它理解为恰好计算固定次数的距离。

构建时也借助已有图为新节点找候选，再选择邻居并建立连接。只连接最接近的节点可能把边集中在同一方向；邻居选择启发式还考虑候选之间的距离，保留较有区分的导航路径。既有节点连接超限时需要裁剪。插入顺序、数据分布、选择规则和随机层级都会影响图。

这些旋钮的拼写、默认值、底层度数和删除支持属于具体实现。hnswlib 参数说明与 Faiss 索引说明提供不同实现的操作边界。内存除向量载荷外还包含多层邻接、标签和管理结构，不能把某实现的近似字节公式推广成所有 HNSW 的大小。

较大的搜索宽度通常增加获得良好结果的机会，效果需要在给定图上测量。没有访问到真实近邻的路径、候选裁剪或图结构变化都可能造成遗漏。构建质量、搜索预算与查询分布应共同解释召回和延迟。

IVF 先选择区域，再扫描区域内容复制锚点链接

IVF（Inverted File）把向量空间划分为若干区域，每个区域保存被分配到这里的向量列表。常见构建用训练样本做 k-means，得到 nlist 个中心；每个库向量分配到一个中心对应的列表。

查询先比较各中心，选择较近的 nprobe 个列表，再在其中计算距离并取前 $k$ 项。真实近邻如果落在未探查列表中，会被漏掉。它在几何上很近，也可能因分区边界而属于查询未选的区域。Faiss 的 Cell-probe methods说明了分配、探查与扫描关系。

nlist 决定分区粒度和中心比较成本，nprobe 决定一次查询覆盖多少区域。列表长度不均衡时，访问比例不等于 nprobe/nlist，热点区域会同时影响尾部延迟与覆盖。训练样本不代表现有数据、数据分布变化或列表过度集中时，需要检查中心和重建条件。

IVFFlat 在选中的列表里保留原始向量并计算对应精度的距离。若探查全部列表、没有额外扫描限制并保留完整向量，它会恢复该表示和度量下的全扫描结果。IVF-PQ 在列表内使用压缩表示；探查全部列表只消除区域遗漏，量化误差仍存在。

PQ 用多个小码本表示向量复制锚点链接

乘积量化（Product Quantization，PQ）把向量分成 $m$ 个子向量，在每个子空间分别训练码本。每个库向量的子向量替换为最近码本中心的编号，整条向量只存一串编号。

若每个子码本有 256 个中心，编号占 8 位，$m$ 个子空间的代码占 $m$ 字节。构造示例里，1024 维 float32 向量的纯载荷是 4096 字节，32 个子空间的 8 位代码是 32 字节，纯代码载荷缩小 128 倍。这个比值没有包含共享码本、ID、索引、原始向量备份和其他管理开销，不能据此声称整个系统节省同样比例的内存。

查询可以保留未量化的向量，对每个查询子向量计算到对应码本各中心的距离，形成查找表。随后按候选的编号取值相加，近似平方欧氏距离为：

$$\hat D(q,x)=\sum_{j=1}^{m}\|q^{(j)}-c_{j,a_j(x)}\|^2$$

$q^{(j)}$ 是查询的第 $j$ 个子向量，$a_j(x)$ 是候选保存的码字编号，$c_{j,a_j(x)}$ 是该编号对应的中心。这样比较候选时读短代码并查表，无需恢复全部原始坐标；查询与库向量采用不同精度，称为非对称距离计算。Jégou 等人的 Product Quantization 论文摘要说明子空间量化和非对称距离，Faiss 的 PQ 索引说明给出代码结构与实现。

IVF-PQ 可以先用粗中心定位列表，再对库向量与粗中心之间的残差做 PQ。查询访问某个列表时，也相对该中心计算残差并建立相应查表。粗分区减少候选范围，PQ 减少向量载荷和评分成本，两层的误差需要分开检查。

量化把多个原始位置映射到同一码字，近似距离可能改变细小差别和排序。增加码字精度、改变分区或保留更多候选可以调整代价；保留原始向量后对候选重新算距离，可以纠正候选内部的量化排序。真实近邻已被候选选择排除时，这一步无法找回它。码本训练、维度分组、距离度量和数据分布都影响误差。

磁盘图索引把存储访问纳入设计复制锚点链接

当完整图和向量的内存成本较高时，可以把部分数据放在 SSD，保留较小的内存表示用于导航。原始 DiskANN 设计将图邻接和完整向量存到 SSD，在内存保留压缩向量；一次节点读取同时取得邻居和完整坐标，压缩距离帮助挑选下一批要读的节点。

其 Vamana 图构建使用有界出度和可调剪枝。候选边中距离与方向相近的连接可被裁掉，参数 $\alpha$ 调整剪枝条件，在给定度数下改变保留的局部和较远连接。原论文采用两轮构建，首轮 $\alpha=1$，随后以更大的参数调整图，以减少搜索需要的访问轮数。

查询的束搜索同时读取一批较有希望的节点，利用并行 I/O 减少逐个等待；候选列表宽度决定保留多少搜索可能，束宽决定一轮并行访问多少节点。把入口附近或常访问节点缓存在内存，可减少重复盘读。读得更多会增加带宽与计算，也可能减少搜索轮数，尾部延迟还受并发负载和缓存状态影响。

DiskANN 原论文 §2—3给出了 Vamana、SSD 布局、束搜索和完整向量重排。以上解释对应原始设计；具体服务还要检查更新、删除、恢复与过滤的实现。论文的特定图像向量数据、硬件和吞吐数值不构成所有文本索引的规模分界。

过滤顺序改变候选覆盖复制锚点链接

设全局最近的 10 项中只有 2 项符合当前类别或访问条件。先取这 10 项再过滤，只剩 2 项，即使允许集合里有更多有用结果。提高全局候选数、继续扫描、按类别建立索引，或先确定允许集合再精确搜索，是不同方案。

过滤感知的图搜索也需明确：不允许返回的节点能否在服务内部作为导航桥梁，怎样保证最终输出只含允许节点，以及怎样处理查询和缓存。直接从图中排除所有不匹配节点，可能破坏导航连通性。过滤效率与结果可见性分别需要证据，客户端过滤无法收回已经下发的数据。

pgvector 的过滤及迭代扫描说明给出一种具体行为：近似索引扫描后应用条件，迭代扫描在需要时继续查找，直到取得足够结果或达到扫描上限。扫描更多不保证找到允许集合中的精确前 $k$ 项；排序是否严格、扫描上限及版本支持均需按实现核对。

评价过滤后的 ANN 时，精确基线应使用同一允许集合与同一度量。全局近邻覆盖、过滤后返回条数、允许集合中的近邻覆盖分别回答不同问题，应同时记录过滤选择率和参数。