2026-11-01 01:31:01 网络安全文章来源：ZONE.CI 全球网 0 阅读模式

论文解读 | PiPNN：用分区与在线剪枝，加速十亿级向量图索引构建

杨皓岚
杨皓岚

北邮 GAMMA Lab

2026年10月30日 10:54
北京

去阅读

一、简介

在向量检索系统中，HNSW、Vamana 等图索引已经能够提供很好的查询性能。但当数据量达到数亿乃至十亿规模，建索引本身就成了一项昂贵的工作：一次构建可能需要数小时，调参和周期性重建还会进一步放大这部分开销。

来自马里兰大学与 Google Research 的研究团队在 PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing 中，将优化重点放在图索引的构建阶段。论文提出 PiPNN（Pick-in-Partitions Nearest Neighbors），通过重叠分区生成候选邻居，再用在线剪枝方法 HashPrune 控制边的数量与方向分布，将大量随机访存转化为更适合批量执行的计算。

在论文评测中，PiPNN 相对 Vamana 的索引构建加速最高为 11.6 倍，相对 HNSW 最高为 12.9 倍，在单台多核机器上以低于 20 分钟构建十亿级索引。下面从构建瓶颈出发，介绍这套方法的设计与实验结果。

论文标题：PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing
研究机构：University of Maryland、Google Research
发表会议：KDD 2026

二、动机：PiPNN 解决什么问题

近似最近邻搜索（Approximate Nearest Neighbor Search，ANNS）的目标，是在允许一定误差的条件下，从大规模向量集合中快速找到与查询向量相近的对象。图索引把每个向量表示为一个节点，通过适当选边，让查询能够沿着图逐步接近目标区域。

构建这类图时，需要同时考虑两个因素：邻居应当足够近，边也应当覆盖不同方向。如果一个节点连接的邻居都集中在同一方向，即便这些邻居很近，也可能不利于搜索导航。

HNSW、Vamana 等方法通常采用增量构建：将新点加入当前索引，先在已有图上执行 beam search，找到候选邻居，再剪去冗余边。这种方式能够产生质量较高的导航图，但搜索过程包含大量随机内存访问，容易产生缓存未命中，限制指令流水线和并行计算的效率。

论文将其概括为 search bottleneck，即构建过程中的搜索瓶颈。PiPNN 希望直接通过数据分区找到候选邻居，省去构建阶段反复搜索已有图的过程。索引建好之后，查询仍然沿用图上的 beam search。

把数据分成许多小块，在每个块内寻找邻居，是一种比较自然的思路。小块中的数据可以集中加载，距离也可以批量计算。

但高维空间中的近邻可能落在分区边界两侧，因此通常需要重叠分区，让同一个点出现在多个局部子问题中。随之而来的问题是：不同分区会不断送来候选边，如何在有限内存中把它们合并成一张稀疏、易于导航的图？

如果先存下所有候选，再统一剪枝，中间存储和剪枝计算都会膨胀。若逐批套用传统剪枝，又可能受处理顺序影响：某条边早先因为另一个候选而被删除，后者却在后续批次中被删掉，前面的剪枝依据也就不再成立。

PiPNN 的关键组件 HashPrune，正是为这种持续到来的候选流设计的。

三、方法：重叠分区与在线剪枝

PiPNN 的整体流程可以概括为：重叠分区、叶子内批量计算距离、选择稀疏候选边、HashPrune 在线合并，以及可选的最终剪枝。下面先介绍在线剪枝，再说明候选如何产生。

3.1 HashPrune：按方向哈希，保留更近的邻居

对于源点 p 和候选邻居 c，HashPrune 对残差向量 c - p 做随机超平面哈希。每个超平面产生一个比特，将 m 个比特拼起来，就得到候选相对于 p 的哈希值。

这里使用残差，是因为需要比较候选相对于源点的方向。对于两个候选、，设其残差的夹角为，论文给出的哈希碰撞概率为：

方向越接近，候选越容易落入同一个桶。HashPrune 在同一桶中只保留距离 p 更近的候选，由此压缩方向相似的边，同时保留来自不同方向的连接。

如Figure 2所示，阴影表示不同哈希位数下的碰撞概率：较粗分辨率下，新候选与较远的碰撞并将其替换；较细分辨率下，两条边都可以保留。

3.2 容量受限的候选容器

每个点维护一个容量上限为 l_max 的候选容器（reservoir）。新候选到来时，按以下规则处理：

已有相同哈希值：只保留离源点更近的候选。
没有相同哈希值，且容器未满：直接插入。
没有相同哈希值，且容器已满：只有当新候选比容器中最远的点更近时，才将其替换。

论文定理 3.1 给出 HashPrune 的历史无关性：给定哈希函数、候选集合和容器容量，最终邻接表不依赖候选的插入顺序。因此，各个分区产生的候选可以分批进入同一个容器，候选存储量受容量上限约束。

实现上，每个候选槽位使用 8 字节，分别存储 4 字节点编号、2 字节哈希值和 2 字节 bf16 距离。为了避免剪枝时反复读取完整高维向量，作者预先计算各点在随机超平面上的低维投影，再由投影差的符号生成残差哈希。实验默认使用 12 个哈希比特。

这种设计也有自己的计算成本。论文指出，容器未满时，插入所需的比较次数可以做到 O(log l)；容器已满且新候选不发生碰撞时，可能需要 O(l_max) 时间更新最远候选。实际剖析中，维护容器通常占总构建时间的比例不超过 5%。

3.3 随机球划分与多层 fanout

HashPrune 解决了候选边如何合并的问题，PiPNN 的另一部分工作，是高效地产生这些候选。

PiPNN 采用随机球划分（Randomized Ball Carving，RBC）：在当前子问题中随机选取一些代表点（leaders），根据与代表点的距离将数据分组，再递归处理过大的分组，直到得到足够小的叶子分区。

单次不重叠的划分容易漏掉跨边界近邻。为此，PiPNN 使用 fanout，让一个点进入多个相近代表点对应的子问题。相比多次完整重复划分，这样可以复用上层的距离计算。

作者进一步把 fanout 分散到多个递归层级。例如，第一层进入 10 个子问题，第二层再分别进入 3 个。把一部分展开工作推迟到更小的子问题中，可以改善缓存利用，并减少上层聚合与分组的开销。

如Figure 3所示，图中比较完整重复划分、单层 fanout 与多层 fanout；随着组合 fanout 增加，多层 fanout 的构建时间优势更加明显。叶子分区的最大规模通常设置为 1024–2048 个点。对于过小的分区，算法还会在不超过最大规模的前提下做合并，保证局部候选数量。

3.4 叶子构建与批量距离计算

得到小分区后，PiPNN 在叶子内部计算两两距离。由于每次处理的数据规模有限，距离矩阵更适合留在缓存中，也可以调用经过优化的矩阵乘法内核。

以平方欧氏距离为例，距离计算可以写成：

其中一批向量的内积可以组织为矩阵乘法。论文实现使用 Eigen 计算距离矩阵，并使用 Highway 的向量化部分排序实现选择近邻。在论文的叶子构建优化实验中，这些优化合计带来约 27 倍的叶子构建阶段加速；这一数字不代表整个索引的构建加速。

PiPNN 不会把叶子内所有边都送入 HashPrune，而是先构建局部 k-NN 图，再将边双向化，以此选出稀疏候选。不同叶子产生的候选随后进入各点的 HashPrune 容器。

3.5 最终剪枝

HashPrune 本身已经可以得到较高质量的图。PiPNN 还允许对最终候选列表执行一次 RobustPrune，进一步调整稀疏程度，改善查询吞吐。

这一步处理的是 HashPrune 已经压缩过的小候选列表，成本相对有限。它也说明，PiPNN 在候选收集与最终图优化两个环节采用了不同粒度的剪枝策略。

四、实验结果

4.1 数据集与实验设置

论文主实验使用四个十亿级数据集，以及两个高维数据集。表1按原论文 Table 1 整理；其中 1B、35M、2M 分别对应十亿、3500 万、200 万条向量，MIPS 表示最大内积搜索。详见Table 1。

主实验使用 10@10 recall，即返回的 10 个结果中包含多少真实前 10 近邻，再对所有查询取平均。比较查询性能时，需要同时观察召回率与 QPS，不能脱离召回率只比较吞吐量。

十亿级与下游 k-NN 构图实验运行在 Google Cloud c4-highmem-288 上，配置为 288 vCPU、2.2 TB DRAM；其他实验使用四路 Intel Xeon Platinum 8160、1.5 TB DRAM 服务器。论文保证同一图表中的结果来自同一台机器。

对比方法包括 HNSW、Vamana、HCNNG、MIRAGE、FastKCNA 等。其中 Vamana 使用 ParlayANN 实现。除 HCNNG 允许最大度数为 90 外，论文将其他方法的最大图度数限制为 64。

4.2 构建时间与查询质量

如Figure 5 所示，横轴为召回率，纵轴为 QPS，图例中的括号数值为构建时间，单位为秒。同时图中展示了两种值得区分的配置：单副本 PiPNN 的查询质量总体接近单遍 Vamana；增加一个独立副本后，PiPNN 能进一步改善查询表现，整体上接近双遍 Vamana。多个副本产生的候选仍通过容量受限的 HashPrune 合并，因此可以用更多构建计算换取更好的邻居覆盖。

4.3 数据局部性分析

同时在Table 4的硬件计数器实验显示，PiPNN 在构建阶段消耗更少的 CPU 周期和末级缓存未命中，支持了作者关于数据局部性的解释。该实验还专门注明，对 Vamana 关闭了预取，因此应在这一实验设置下理解计数器结果。

从算法流程看，分区使计算集中在局部数据块中，矩阵乘法与向量化排序提高了批量计算效率，而 HashPrune 则限制了跨分区候选的累计存储。几部分相互配合，才形成最终的构建加速。

4.4 下游 k-NN 图构建

导航索引与最终的 k-NN 图是不同的对象。论文还评测了一项下游任务：先构建 ANN 索引，再对所有点执行查询，输出 k = 10、边召回率至少为 95% 的 k-NN 图。

如Figure 6所示，结果包含索引构建与全量查询，柱高表示相对于最快方法的时间倍数。PiPNN 相对 hnswlib 的端到端加速为 2.2–6.9 倍，相对 ParlayANN Vamana 为 1.4–1.7 倍。由于所有点都需要查询，而高质量图索引的查询耗时相近，这项任务的整体加速小于单独构建索引时的加速。

五、消融实验与分析

论文进一步分析了分区方式、叶子计算优化、哈希参数与最终剪枝的作用。消融实验使用 BigANN、MS-SPACEV 的 100M 子集，以及 OpenAI-ArXiv 和 Wikipedia-Cohere。

如Figure 8所示，配套质量实验中，三种策略的查询表现没有一致性的优劣差异。

如Figure 9所示，相对完整重复划分，单层 fanout 的分区阶段平均加速为 1.47 倍，多层 fanout 为 3.35 倍；因此，多层 fanout 能够在维持候选覆盖效果的同时，减少上层重复计算。

如Figure 12所示，附录 A.4 将预计算距离矩阵、使用 Eigen 以及向量化排序等优化逐步加入叶子构建过程。最终优化版本相对朴素实现，局部 k-NN 叶子构建的平均加速为 27.03 倍，进一步说明了批量距离计算的作用。

对于 HashPrune，如Figure13所示，作者测试了 6、8、10、12、14、16 个哈希比特。在所展示的无最终剪枝参数实验中，8–16 比特表现较稳定，6 比特出现性能下降，因此最终默认选择 12 比特。作者还比较了容量为 64、128、192 的候选容器与不限制中间度数的配置。在使用双向局部 k-NN 候选、并最终剪枝到最大度数 64 的设置下，这些容量变化对高召回查询所需的距离计算次数影响较小。这一结论依赖所测试的候选生成与最终剪枝配置。