WorksComputer Science
Turbocharging PiPNN for Proximity and -NN Graph Building
Abstract
Graph-based Approximate Nearest Neighbor Search (ANNS) indexes such as HNSW and Vamana deliver state-of-the-art query performance at the cost of large indexing times. The recently introduced PiPNN method drastically accelerated index construction by way of a partitioning-based algorithm leveraging dense matrix multiplication and top- aggregation kernels. In this paper, we unlock the full potential of PiPNN's hardware-friendly algorithm design. We introduce PiPNN II, which optimizes multiple steps of the PiPNN recipe, giving up to speedups for graph-based ANNS index construction. In addition, we present GPiPNN, a GPU implementation which builds comparable ANNS indices up to faster than Jasper and up to faster than CAGRA. We also extend PiPNN II and GPiPNN to compute high-quality -NN graphs directly, which unlocks massive speedups over methods used in many existing systems for clustering, anomaly detection, and more. For 10-NN graph building at recall, we obtain up to a speedup on CPUs and on GPUs as compared to the prior best methods. PiPNN II can build a billion-scale 10-NN graph in under 16 minutes. Common to both PiPNN II and GPiPNN is the use of quantization to reduce memory traffic and leverage fast low-precision matrix operations. Top- emerges as a new bottleneck, which we optimize with specialized code for specific , and by fusing with the matrix kernel to avoid materializing the distance matrix to memory. On CPUs, we demonstrate further performance improvements by leveraging our matrix kernels in the RobustPrune procedure proposed in Vamana and used in PiPNN. On GPUs, we flatten recursive partitioning into segmented batches, use one fused top- abstraction for partitioning and leaf scoring, and prune with already-witnessed direct edges rather than new candidate-to-candidate scoring passes.
Figure 1. Index-build speedup of PiPNN II and GPiPNN over well-optimized baselines. Left: CPU speedup of PiPNN II over unquantized Vamana. Right: GPU speedup of GPiPNN over CAGRA.
Introduction
Vector embeddings power modern search, recommendation, entity resolution, and retrieval-augmented generation systems [22, 36, 37, 45, 55, 65, 69]. These systems rely on approximate nearest-neighbor search (ANNS) because exact search is prohibitively expensive and small errors are tolerable. Graph-based indexes such as HNSW, Vamana (DiskANN), and NSG have become the standard for high-recall, low-latency ANNS [17, 30, 40]. Unfortunately, their excellent query performance has come at the cost of slow index construction: building a high-quality search graph (also termed “proximity graph”) over a large dataset has historically required many hours or even days of compute on powerful multi-core machines [41].
Fast index construction is not merely a convenience: build time is often a major factor in the total cost of the system. Indexes must be rebuilt as data drifts, parameters need to be tuned across datasets, and ANNS appears as an inner loop in fundamental tasks including accelerated -means [60], hierarchical clustering [12, 67], minimum spanning trees, and single-linkage clustering [1, 3, 5, 7]. Small modifications to graph-index construction also yield high-quality -NN graphs [8], a primitive that we directly target in this paper. An indexing method that takes hours or days is simply unusable in many modern workflows.
The recently introduced Pick-in-Partitions Nearest Neighbors (PiPNN) method significantly speeds up high-quality index construction by replacing build-time graph search with regular partition-local scoring work [56]. It recursively partitions the input vectors into small collecting collections (termed “leaves”), generates candidate edges through batched all-pairs distance comparisons and top- aggregation inside each leaf, and streams those candidates through an online history-independent pruning procedure (HASHPRUNE) to retain sparsity. The bulk of PiPNN’s construction is comprised of all-to-all comparisons over small, cache-resident sets of vectors; an operation far more amenable to modern hardware than the irregular pointer-chasing of incremental graph construction [17, 30, 40]. The payoff of this approach is that the existing version of PiPNN is up to 11.6× faster than the ParlayANN implementation of Vamana on CPU and produces indexes with equivalent QPS-recall performance [56].
Despite these significant improvements in build times, the first version of PiPNN fails to leverage modern hardware to its full potential. For instance, it keeps vectors in full-precision float32 form to perform GEMM (General Matrix Multiply) and materializes the full distance matrices to memory to perform per-row top- reduction. In this paper we significantly optimize the entire approach from first principles. We start by leveraging quantization to replace the full-precision vectors with compact integer codes that are cheaper to compare [14, 27, 32, 35, 41, 61]. Quantizing the vectors not only speeds up memory accesses, but it also enables low-precision multiply-accumulate instructions. Decoding cost may seem concerning at first glance, but is easily amortized over many distance computations. Lastly, we fuse the GEMM kernel with top- reduction in register, to avoid materializing an distance matrix to memory. While fused distance computation and in-register -selection are established in GPU similarity search [14, 32], our contribution is a family of compressed-domain kernels specialized to PiPNN’s leader-assignment and leaf-processing shapes and instantiated across CPUs and GPUs.
The aforementioned opportunity and challenge carries over to hardware acceleration using GPUs. Compared to existing GPU ANNS systems [42, 50] which struggle to leverage the full potential of the hardware due to relying on either beam search or iterative refinement on graphs, PiPNN’s batched many-to-many structure is an ideal fit for tensor cores. However, implementing PiPNN on GPUs presents non-trivial challenges: PiPNN’s recursive partitioning produces irregularly-sized subproblems whose control flow is not handled well by the GPU scheduler and must be flattened into uniform passes; the vectors needed for each local comparison are scattered in device memory and must be gathered into dense batches; and the HashPrune reservoirs for each point must be maintained without the use of locks.
In this paper we realize the full potential of PiPNN by carefully restructuring PiPNN’s construction pipeline around fused quantized batched top- kernels. We instantiate this design on both shared memory CPU systems (PiPNN II1) as well as GPUs (GPiPNN), thus cashing in on the promise for hardware-accelerated ANNS builds within the PiPNN framework. Our results show that our GEMM kernels take full advantage of the hardware: the CPU score-and-select kernels run near instruction throughput roofline, whereas the corresponding GPU kernels are memory bound for high-dimensional vectors typical of modern embeddings.
On GPUs, PiPNN flattens the recursion used in PiPNN’s partitioning routines by refactoring them as radix sorts over leader-assignment keys. In addition, it processes multiple collections of points in a single kernel using a segmented top- primitive, which ameliorates workload imbalances. Finally, it avoids a costly final prune, by way of a novel DirectEdgePrune over the cached distances in the HashPrune structure.
Our extensive experimental study establishes PiPNN II and GPiPNN as the new state of the art for proximity-graph index construction on CPUs and GPUs, delivering large speedups over the strongest prior methods while preserving high-recall query performance. On CPUs, PiPNN II builds indexes up to 8 faster than PiPNN and substantially outperforms all prior graph-based ANNS builders on the datasets we evaluate. On GPUs, GPiPNN achieves speedups of up to 43.7 over Jasper and 50 over CAGRA across a diverse benchmark of text, image, and text-to-image datasets, while matching or exceeding their query throughput at high recall. On CPU, we show that our new methods enable the construction of billion-point graph indexes on a single machine in under 10 minutes, as opposed to hours for prior best methods.
Beyond proximity-graph construction, we show that the same methods produce high-quality -NN graphs (a connection between partitioning-based construction and -NN graphs also briefly noted in prior work [25]), making PiPNN II and GPiPNN state-of-the-art for -NN graph construction as well. At recall10@10 , PiPNN II is up to 13 faster than the best prior CPU -NN builder (Vamana-Q), and GPiPNN is up to 6.6 faster than the best prior GPU -NN builder (cuVS NN-DESCENT).
In summary, the main contributions of this paper are:
Highly optimized quantized GEMM fused with top- kernels.
PiPNN II, a shared-memory CPU implementation leveraging quantization and our new fused kernels to achieve state-of-the-art index construction and -NN graph building performance.
GPiPNN, a GPU implementation of the same method which redesigns the PiPNN framework for excellent performance on modern accelerators.
An extensive experimental evaluation spanning twelve datasets across text, image, and text-to-image modalities at scales up to one billion points (one hundred million on GPU), including direct -NN graph construction results, that establishes PiPNN II and GPiPNN as state of the art for fast high-quality ANNS index construction on modern CPUs and GPUs.
Preliminaries and Prior Work
Approximate Nearest Neighbor Search (ANNS). Let be a collection of vectors and let denote a dissimilarity measure on (e.g. Euclidean distance or the negative of an inner product).
Definition 1. (k-nearest neighbor search) Given a query , the -nearest neighbor set of in is the set of size containing the points of smallest dissimilarity to :
We assume is unique. In ANNS, the goal is to return a set that approximates as efficiently as possible.
Definition 2. (@k' recall) Let be the exact -nearest neighbor set of query and let be a returned set of size . The k@k' recall of is .
We focus on 10@10 recall and use recall to denote this quantity; the recall of a query set is the mean recall over all queries in .
Graph-based ANNS. Graph-based ANNS methods build a sparse proximity graph over the points, with outgoing edges to a small set of nearby neighbors. The graph need not exactly equal the -NN graph; it must only be navigable enough that a local search can locate the nearest neighbors. HNSW and Vamana are canonical examples, both constructed via greedy graph traversal [30, 40]. A long line of work has refined proximity-graph constructions [13, 15, 16, 17, 28, 29, 39, 43, 46, 64, 66, 70], developed parallel or disk-resident variants [35, 41, 59], accelerated query-time search [10, 20, 26], and ported graph indexes to GPUs [34, 42, 50].
Beam search. The standard graph-query procedure is beam search. It maintains a beam of the best points seen so far; at each step it expands the best unvisited point in , inserting its neighbors into and truncating back to size . The search terminates when every point in has been expanded, and the final beam is returned or used as candidates for reranking (see code in Appendix § 11, Algorithm 5).
The “search bottleneck”. Prior to the introduction of PiPNN, the highest-quality graph indexes were built by searching during construction: HNSW and Vamana insert points incrementally, traversing the partial index to find candidate neighbors for each point, then pruning for sparsity [30, 40]. This produces excellent graphs but creates a search bottleneck: beam search is rife with random memory accesses and cache misses, so traversal dominates construction time. PiPNN’s partitioning approach breaks altogether from prior solutions which used distance-comparison-skipping heuristics and cheap graph-initialization. It builds indexes up to 11.6× faster than the efficient ParlayANN implementation of Vamana [41].
Quantization
Quantization is a lossy compression technique that maps high-precision vectors to a smaller, discrete set of representative points. Broadly speaking, three types of quantization methods are widely-used in the ANNS literature: scalar uniform quantization, which independently maps each vector coordinate to an -bit integer; product quantization, which partitions a vector into subvectors and performs lookups in learned codebooks [23, 31]; and rotation-based quantizers, which apply a random rotation and leverage distributional properties of the rotated vectors, including RaBitQ [18, 19, 21], DRIVE/EDEN [6, 62, 63], and TurboQuant [68]. In this paper, we consider two quantization methods: RSQ8 (rotated scalar quantization with 8 bits per coordinate) and TQ4, a 4-bit variant of TurboQuant, which we outline next.
TurboQuant. TurboQuant is a scalar quantizer with non-uniform codebook. It first applies a random rotation and then quantizes each post-rotation coordinate independently with a scalar Lloyd–Max codebook trained against the post-rotation marginal [68]. This achieves near-optimal distortion across bit widths and dimensions, but the resulting inner-product estimator is biased because the MSE-optimal codebook is not matched to the inner-product objective. The original TurboQuant addresses this with a two-stage estimator that applies a 1-bit JL quantizer to the residual to recover an unbiased dot product.
TurboQuant variant. We adopt TurboQuant’s rotation-plus-scalar-quantizer structure but replace the QJL residual with an extra codebook bit and a per-vector rescaling factor . We first normalize the vector before quantization, so to get the correct dot product, is the ratio of the original norm to the quantized norm. The estimator multiplies the dot product from the decoded vectors by the two scaling factors and (for the query and database vectors, respectively). The rotation is done with a Fast Walsh–Hadamard Transform composed with a small random orthogonal matrix, so encoding runs in and is data-oblivious. Post-rotation quantization is done by independently mapping each coordinate to its nearest codebook entry. With TQ-4 we use an int8 version of the codebook scaled to . For further details, we refer to the original paper. For the remainder of this paper, the important part is that we can quickly decode vectors from 4-bit to int8 with a 16-entry codebook, in-register using the vpshufb shuffle instruction.
A goal of this paper is to develop fast kernels in which the distance computation relies on an integer inner product plus a small per-vector correction. Related quantizers such as RaBitQ, DRIVE, EDEN, [6, 62, 63] all fit this template and could be used instead. We use the TurboQuant variant because it has fast encoding time, and after decoding, maps cleanly onto integer dot-product instructions on CPUs (VNNI) and GPUs (WGMMA); any quantization fitting the template plugs into the same kernels.
PiPNN
PiPNN (Pick-in-Partitions Nearest Neighbors, KDD’26) is a recent graph construction algorithm designed to circumvent the build-side search bottleneck of most existing graph-based construction methods [56]. Instead of performing expensive global beam searches to find neighbors, PiPNN localizes the search by partitioning the dataset and generating graph edges within each partition. Alg. 1 gives high-level pseudocode for PiPNN [56], which proceeds in three phases:
Partition. We build an overlapping partition of via recursive randomized ball carving until each leaf cluster satisfies .
Pick. For each leaf, we compute the within-leaf -NN graph for a very small and bi-direct it. Because points participate in multiple overlapping leaves, they accumulate a diverse set of candidate edges overall, despite the small local .
Prune. Candidates from different leaves are streamed into a per-point reservoir of size using HashPrune to ensure directional diversity, followed by a final RobustPrune pass for sparsification.
Algorithm 1: PiPNN
Input: 𝒳 a collection of points with dissimilarity measure,
BP a collection of hyper-parameters
Output: 𝒢 = (V, E) a graph over 𝒳
1 𝒢 ← (𝒳, ∅);
2 ℬ ← Partition(𝒳, BP);
3 for bᵢ ∈ ℬ do in parallel
4 new_edges ← Pick(bᵢ, BP);
5 𝒢.Prune_And_Add_Edges(new_edges);
6 for x ∈ 𝒳 do in parallel
7 PruneNode(x);
8 return 𝒢;
Accelerating PiPNN is the primary goal of this paper. In total there are four pieces that dominate the runtime: AssignLeaders during Partition, ProcessLeafTop2 during Pick, HashPrune, and RobustPrune. The main cost in the first two is many-to-many top- computations over small collections of vectors.
The AssignLeaders Kernel. PiPNN partitions via Randomized Ball Carving (RBC): given a subproblem , RBC samples a subset of points as leaders. Each point in is assigned to its nearest leaders. This multi-assignment creates the overlap between subproblems. To control the growth of subproblems, decays geometrically per level (typically from 10 down to 3, and finally 1). RBC recurses on any subproblem exceeding size . The dominant cost of partitioning is the distance comparisons to score each point against all leaders and retain the top leaders (AssignLeaders kernel).
The ProcessLeafTop2 Kernel. Within each leaf , we compute all pairwise distances and extract the top-2 neighbors per point. Each point participates in multiple leaves (typically 30), so a small per-leaf is sufficient to deliver a diverse set of candidate neighbors [56]. Because each pairwise comparison can symmetrically update the top-2 of both endpoints, bi-directing these edges yields on average 4 candidates per point per leaf. ProcessLeafTop2 is typically the bottleneck in PiPNN.
HashPrune. HashPrune is an online procedure that pre-filters the set of candidate edges generated for each index point. For each point , the goal is to keep neighbors that are spread out in different directions. To achieve this, for each point we maintain a reservoir of capacity indexed by an -bit hash. For a candidate , we define its hash for random hyperplanes , where denotes the concatenation of bits to form an -bit signature. Mathematically, this projects the direction of the residual vector onto hyperplanes, partitioning the space around into angular cones (sectors). Two candidates fall into the same cone (collide) with probability , where is the angle between and . The reservoir retains only the single nearest candidate that falls into each cone. Crucially, the final state of the reservoir depends only on the set of candidates and not their arrival order. The PiPNN graph is deterministic, despite streaming candidates in parallel. Pseudocode is in Sec. B.
RobustPrune. RobustPrune selects a sparse out-neighbor set from a candidate list via a greedy occlusion rule [30]: it repeatedly picks the nearest remaining candidate , adds it as a neighbor, then discards any candidate satisfying —meaning already “occludes” from . The parameter controls pruning aggressiveness; larger retains more edges and yields denser, more navigable graphs. PiPNN applies a RobustPrune pass over each reservoir to impose the DiskANN -rule. Because each reservoir is already small ( entries), this pass is relatively cheap compared to graph-based builders that invoke RobustPrune on much larger candidate lists [56].
Building -NN Graphs with PiPNN. A by-product of the partitioning phase is that each point already accumulates a pool of nearby candidates within its leaves, which we can use to produce a -NN graph directly. Many prior graph-based approaches to building -NN graphs take a build-then-search approach: they first construct a full navigable index over and then issue a beam-search query for each base point, doubling the work and making the query pass dominant. In this paper, we study using PiPNN to retain the top- neighbors per point directly from its leaves and skip the search pass entirely. We show in Sec. 6 that this strategy matches the recall of build-and-search at a fraction of the cost, and surpasses NN-DESCENT which is the most popular method for direct -NN construction.
Quantized and Fused Top- CPU Kernels
The primary bottleneck of PiPNN is computing distances between query points and data points during top- assignments (either leaders during partitioning, or leafmates during leaf processing). Naively, this could be done by materializing a large distance matrix, which is costly due to writing and subsequently re-reading to post-process the distances, e.g., reducing to the top- neighbors.
To eliminate this bottleneck, PiPNN II fuses the distance computation with the downstream reduction. Registers with computed distances for a subset of the neighbors in the distance matrix are immediately consumed instead of being written out to an explicit distance matrix. In this section we describe the matrix-multiplication structure (Sec. 4.1), then the reduction kernels for partitioning (Sec. 4.2), and finally leaf processing (Sec. 4.3).
Vectorized Quantized MatMul Structure
Overview. In this subsection we describe our core matrix multiplication primitive. Before diving into the technical details, we give a high level overview. Our goal is to enable PiPNN II to work directly over the quantized data. The inputs to the kernel are TQ coordinates, which we decode on-the-fly with an i8 codebook. The loop structure of the matrix multiplication iterates over queries in the outer loop, database points in the middle loop and reduces on dimensionality in the inner loop to obtain the dot product between query and database point.
For efficiency, we use SIMD vector instructions to compute partial dot products. A SIMD vector register consists of multiple lanes, where each lane corresponds to one data item, e.g., a 512-bit AVX register holds 16 i32 lanes which can be processed in parallel with a single instruction. The performance driver of our code is a dot-product instruction from VNNI (Vector Neural Network Instructions) which requires us to make some adaptations to the data layout. We give a detailed description of our approach next.
The Dot Product Instruction. We leverage the u8 × i8 quad dot product instruction vdpbusd (AVX-512 VNNI). For concreteness, the instruction computes:
where , , , and iterates over the 16 lanes in a 512-bit register. Given two 64-byte registers of u8 and i8, it computes 16 parallel 4-dimensional dot products in a single instruction. We use Highway’s SumOfMulQuadAccumulate function, which uses vdpbusd when available and emulates it via widen + pairwise-add instructions (vpmaddubsw) on earlier targets (AVX2) [24]. We note that unfortunately there is no equivalent i8 × i8 instruction.
Multiplying Signed Bytes. Because the vdpbusd instruction only supports multiplying unsigned bytes (u8) by signed bytes (i8), we cannot directly multiply the signed codes for both the query and data points. We resolve this by shifting database codes by +128 to make them unsigned, multiplying unsigned codes by signed codes, then subtracting the error from the accumulated inner products.
Specifically, let be the original signed database byte, be the signed query byte, and be the shifted unsigned database byte. We recover the true signed inner product by evaluating .
Data Layout for Vectorization. The quad instruction computes 16 independent 4-dimensional dot products, one per i32 lane, so scoring 16 database points at once requires each lane to hold a different point. A row-major layout stores each point’s coordinates contiguously, which spreads a single point across the lanes rather than 16 distinct points, forcing a costly horizontal reduction per point and one point per instruction. We instead interleave the database into contiguous blocks called panels: a panel groups database points and a panel tile stores one 4-dimension (quad) coordinate group from each, so 64 consecutive bytes hold the same 4 dimensions across all 16 points (Figure 2). A panel tile is then scored against a broadcasted query quad in a single instruction, yielding 16 partial dot products, one per lane.

Figure 2. 16 quads in a panel of the CPU GEMM kernel (AVX-512, ). ① The database side is first decoded from TurboQuant to u8 using 𝑖8 + 128 codebook, then transposed to a u8 tile. ② The query side stays row-major and decoded to i8; the matching 4-byte word of one query is broadcast into all lanes, then recast to i8. ③ One vpdpbusd multiplies the two tiles one lane by lane, folding 4 i8 byte products into i32 lanes. After processing all dimensions, lane 0 recovers the true signed dot product 243 for datapoint 0 from the unsigned-by-signed value 883 via the 128 byte-sum correction (lane 15 gives −279); the epilogue then rescales by and .
Loop Structure. We want to perform the inner reduce on the dimensions so that we materialize a finalized dot product after the loop. Hence, we do not have to spill partial dot products to memory before down-stream consumption in the top- aggregation. This motivates our loop structure to process queries in the outer loop, database points in the middle, and dimensions in the inner loop, as shown in Algorithm 2. We omit cache tiling as it slightly hurts performance: the inputs are small enough to remain L2-resident. Note that the pseudocode shows the process for computing negative dot products as the distance. When we use L2 distance, we precompute the squared norms of the datapoints to compute L2 from dot product.
Unrolling. Unrolling over queries at a time amortizes the cost of streaming over the database points repeatedly and exposes instruction-level parallelism; we found to perform best. Unrolling over multiple panels at a time (we found four to perform best) amortizes the cost of loading and broadcasting the 4 query dimensions: because all four panels share the same broadcast of four query bytes, one broadcast instruction serves four vpdpbusd instructions instead of one. In the inner loop we thus perform vpdpbusd instructions per iteration. For simplicity, unrolling is not shown in Alg. 2.
The kernels described next share this GEMM core but differ in the epilogue: Sec. 4.2 fuses an asymmetric top- reduction, while Sec. 4.3 exploits score symmetry to halve the work. The same GEMM core is reused for the final RobustPrune pass, evaluated in Sec. 6.3.
AssignLeaders Kernels
During each level of partitioning, each point must be assigned to its nearest leader(s)—a batched nearest-neighbor query that the AssignLeaders step performs as an asymmetric GEMM with per-query top- filtering. The database side (the leaders) is small, so we can pretranspose the leaders once and amortize the cost over many queries. Moreover we can simply parallelize over cache-sized chunks of queries and call the single-threaded GEMM kernel.
We inherit the fanout recipe from PiP NN: the number of leaders each point is assigned to is on the first level, 3 on the second, and 1 on deeper levels. This enables us to specialize the top- aggregation to these specific values.
Algorithm 2: Simplified Fused GEMM Loop
Input: Queries , Transposed Panels , Scaling factors
Output: Fused update to Top- state
for to do
;
;
for to do
for to do
Top-1 ArgMin. For , we use a vector-of-indices approach to ArgMin, which operates in a single pass over the scores of a query without spilling to memory. A score accumulator holds the scores of one query for database points in its lanes. We track the per-lane minimum score and database index in registers. Given the score accumulator for the next panel, we compare lane-wise to obtain a mask and blend (IfThenElse) the new scores and indices into the running tracker. After all panels, we perform a horizontal reduction across lanes to obtain the actual minimum.
Displacement sort (). For and we generalize the ArgMin approach to a displacement sort (Alg. 3). The key idea is to track the top- per lane independently, deferring the expensive horizontal merge until all panels are processed; this is faster than vectorized QuickSelect for small . We maintain a displacement register , initialized with the incoming scores. In each of iterations, a lane-wise comparison of with the current top- entry produces a mask, where is the current iteration. Four conditional blends per iteration swap scores and indices between the tracker and the displacement register. If the incoming score beats the -th best, the displaced entry is carried in into iteration , where it may in turn displace the -th best. After iterations, holds the element that was pushed out of the top-. With query unrolling, this still fits in registers for , but for the tracker state spills to L1; this is acceptable since the L1 round-trip is negligible relative to the GEMM work and is called for queries, whereas is called for queries.
After the loop over all panels, each of the tracker registers holds independent per-lane candidates. We dump the scores to a stack buffer and resolve to a per-query top- with scalar insertion sort. The scalar work is minimal compared to the GEMM and SIMD top- work.
Algorithm 3: SIMD Displacement Sort Insertion
Input: Score vector
Index vector
Data: Tracker score registers for (updated in place)
Tracker index registers for (updated in place)
for to do
mask // per-lane comparison
The Leaf Kernel
The leaf processing step computes a self-join: every point in a leaf serves as both query and database entry, and the kernel finds the top-2 nearest neighbors for each point. Because the similarity relation is symmetric, computing both and is redundant. To halve the distance computations, we restrict our GEMM to the lower triangle of the score matrix and update the top-2 trackers of both points symmetrically. Concretely, for a query batch of consecutive points starting at index , the kernel only sweeps panels . For each computed score , we scatter updates to the top-2 states of both query and database point .
Let denote the vector of rescaled distances between query and the database points in panel , occupying positions where . We process in three stages.
Masking. To enforce the lower-triangular computation and exclude out-of-bounds entries, we set for every lane satisfying (eliminating self-distances and pairs already accounted for when served as a query) or (padding lanes beyond the point set). After masking, each finite entry corresponds to a unique unordered pair with .
Symmetric scatter. We exploit the symmetry by updating two independent top-2 trackers with the same score vector. The query-side tracker stores scores in registers and their database-point indices in ; it tracks the two smallest scores for query and resides entirely in SIMD registers throughout the panel loop, incurring no memory traffic. The database-side tracker maintains the analogous state for the database points in panel . As it is shared across query batches, it is loaded from memory once per panel, updated in-register by all queries in the current batch, and stored back once the batch completes. The unrolling optimization for GEMM benefits the memory traffic here as well. Both trackers are updated via the branchless two-comparison cascade described next. Note that uses one lane per database point, updated with the same query id, whereas uses lanes for one query point updated with database points.
Lane-parallel top-2 insertion. Given the tracker registers and for the running top-2, and an incoming score vector and index vector , the insertion proceeds independently per lane. We first compute two Boolean masks: (indicating new global bests) and (indicating new second-bests). The second-best registers are updated first: if the incoming score beats the current best (), the old best is demoted to second; if it beats only the second-best (), it replaces the second directly:
followed by the first-best registers:
Note that eq. (1) must precede eq. (2): when is true, the old must be demoted into before being overwritten. All four assignments are branchless IfThenElse blend operations executing in parallel across all lanes without cross-lane communication. Note that this uses six blend instructions: two less than the generic top-2.
Cross-lane reduction. After the final panel, the lanes of hold independent top-2 pairs. We extract all score–index candidates and move them into the database-side tracker using scalar top-2 insertion. The database-side tracker serves as the output.
Accelerating PiPNN on GPUs
Overview. GPUs are highly effective on tasks where many threads can operate on dense data with regular, contiguous memory access patterns. They provide high throughput for tiled matrix products, bulk copies, reductions, and global sorts. On the other hand, they do poorly on workloads of widely varying size, on recursive calls, and on lock-heavy data structures.
As on the CPU, the dominant cost for our GPU implementation of PiPNN II ought to be top- computation. GPUs can perform bulk top- very efficiently, but the rest of the work performed in PiPNN II — recursive partitioning, HashPrune reservoirs with locks, and the final RobustPrune — are difficult to implement performantly. GPU background. GPUs are built from many streaming multiprocessors (SMs), the general-purpose cores that run threads. Each SM has a register file (64K 32-bit registers on the H100 we use). It also has a small shared-memory scratchpad, shared by a group of cooperating threads, that we use to stage data that is read frequently. For matrix multiplication, the SM provides tensor cores, units that multiply and accumulate a small tile in a single instruction. Two asynchronous copy engines move data into shared memory without occupying the SM’s compute units so that copies overlap with computation: cp.async performs ordinary per-thread copies from global memory, whereas the Tensor Memory Accelerator (TMA) copies a whole tile characterized by a copy descriptor containing the base address, shape, stride, and swizzle to be performed. Software groups threads at three levels: a warp is 32 threads that execute in lockstep, the GPU analogue of a SIMD register; a warpgroup is four warps (128 threads) that together issue one tensor-core instruction, wgmma; and a thread block is one or more warps scheduled onto a single SM, sharing its registers and shared memory. We call threads operating within a warp lanes.
With this in mind, we change a number of PiPNN’s algorithmic and implementation details to map it onto the GPU.
We flatten the recursion into a fixed number of assignment-and-sort rounds (§ 6).
We regularize bucket sizes during partitioning and leaf building into fixed-size work units called score tiles (§ 6.1). Each scores a group of queries against a block of database points and maps one-to-one onto a thread block.
We compute every distance through a single top- primitive that scores directly over the vectors without ever materializing a score matrix (§ 6.2). This is segmented, in the sense that it is one kernel that computes a top- over many independent subproblems of varying size at once.
We replace the lock-based HashPrune with sort-and-merge accumulation (§ 6.3). This requires a transient buffer bounded by the per-batch slab cap rather than by the full candidate set (Sec. E.9).
We replace RobustPrune with a relaxation, Direct-EdgePrune, that reuses already-witnessed distances rather than recomputing them (§ 6.4). While DirectEdgePrune produces denser graphs than RobustPrune (Table 7), we find that this does not affect index quality.
| Dataset | avg. out-degree | AUC () | ||
| recomp. | direct | recomp. | direct | |
| DEEP-10M (L2, ) | 28.7 | 37.3 | 167.8 | 182.5 |
| Wiki-all-10M (IP, ) | 17.6 | 27.7 | 20.4 | 20.1 |
| OpenAI-2M (L2, ) | 21.4 | 30.6 | 9.0 | 9.1 |
| DBpedia (L2, ) | 18.6 | 27.6 | 9.0 | 10.4 |
Table 7. GPU final prune: direct-edge reuse vs. candidate-distance recompute (GPiPNN-TQ4, § 6.4). Average out-degree of the built graph and the area under the GPU QPS-vs-recall curve above recall 0.9 (AUC, in QPS·recall; higher is better). Both modes use the identical build recipe and HashPrune pass and differ only in the final pruning rule. The direct-edge rule yields 30–58% denser graphs of comparable quality in the high recall regime.
Flattening Recursion
PiPNN partitions points by recursively assigning each point to one or more leader points. Because recursion is a poor fit for GPUs, we replace the explicit recursion with a fixed number of assignment passes. In each pass, we assign points to their nearest leaders within a given subproblem, then sort by the induced keys. This gives us the same partitioning structure without explicit recursion.
More formally, we first sample top-level leaders, assign every point to its nearest leaders, then sort the memberships by leader so that each top-level bucket is a contiguous run. Second, within each top-level bucket, we sample bucket-local sub-leaders, assign each member to its nearest sub-leaders, and sort again to expose the second-level buckets as contiguous runs. We set the GPiPNN fanout to at the top level and at the second, so each point appears in up to leaf memberships, comparable to the roughly 30 in PiPNN II (§ 4.2). Each round costs a device-wide sort. Additional assign-then-sort rounds are possible, but two were adequate to achieve high recall. Figure 9 reports the effect of recursion depth on index quality.

Figure 9. Effect of maximum recursion depth on PiPNN index quality. On four different datasets, increasing recursion depth cap beyond 3 has little to no impact on query performance.
Regularizing Bucket Sizes
Flattening eliminates recursion from GPiPNN but does not address skew in subproblem sizes: some top-level buckets are large, some second-level buckets exceed the maximum leaf size, and some leaves are nearly empty. Because a GPU runs thousands of thread blocks concurrently and a launch completes only when its slowest block finishes, a kernel whose per-block work tracks this long tail would let a few oversized buckets dominate the launch while many near-empty leaves leave their SMs idle, so utilization collapses toward the worst-case bucket rather than the average. We reshape the uneven buckets into nearly-uniformly-sized leaves, which we process within fixed-size score tiles (§ 6.2).
Reshaping buckets. We reshape both the partitioning buckets and the final leaves the same way. We radix-sort points by bucket id, run-length-encode to recover each bucket’s size, then split oversized buckets and merge undersized ones to a target size (≈ 1024), mirroring the leaf-balancing step of PiPNN [[56]. Because the sizes are normalized, one fixed-tile kernel handles every leaf, so we never specialize or relaunch per bucket size. We score each leaf as one segment and launch the leaf kernel on batches of these segments, which keeps the tensor cores occupied and amortizes launch overhead.
A Single Fused Segmented Top- Primitive
Overview. We serve every batched top- with one primitive that scores over the decoded i8 codes and keeps the top- entirely in registers. RSQ8 codes are already i8 and used as-is, while TQ4’s packed 4-bit codes are expanded once through a 16-entry codebook into i8, so the kernel sees a uniform i8 representation for both (Sec. E.3). We describe that kernel here.
The tensor-core instruction. We use the warpgroup matrix-multiply instruction wgmma on Hopper tensor cores. Recall that a warpgroup (128 threads) issues one wgmma cooperatively. On the i8 codes of a quantized dataset, a single wgmma instruction operates on a tile of query rows, database-point columns, and contraction width bytes, computing
i.e. multiplying an tile of query bytes by a tile of data bytes and accumulating an block of i32 results. The instruction fixes , while the width is our tiling choice. The accumulator lives in registers distributed across the warpgroup. Each lane owns a fixed set of cells, and the four lanes that own one output row sit at consecutive lanes of a warp.
Launch interface. At each launch we pass to the segmented top- kernel the decoded base vectors of the dataset, the per-vector scales and squared norms, a single dense slab holding the database-point rows of every segment in the launch, and the list of segment descriptors. A descriptor is the tuple consisting of the global ids of its query rows, the first row and count of its database-point window inside the slab, and the output offset at which we write its top- results. Packing all database-point rows into one slab allows faster TMA tile copies from global to shared memory. Because that descriptor covers the whole slab, each segment accesses its rows by offset, and we never rebuild a descriptor per leaf.
Score tiles. We expand the segment sizes on the host into a list of score tiles. A tile pairs segment with a block of query rows starting at . A multi-warpgroup variant doubles this to (Sec. E.4). Each thread block executes one tile: a single warpgroup of 128 threads issues the wgmmas, each computing multiply-accumulates over one 32-byte stripe. Because the tile size is fixed, work is assigned to thread blocks statically and evenly, no matter how segment sizes are distributed. A segment is one independent scoring subproblem: a set of queries scored against a contiguous window of database points. A single launch scores many segments at once—one per leaf—for a batch of leaves sized to fill the slab, which is thousands of leaves per launch.
Fused scoring loop. Each thread block sweeps its segment’s database-point window in tiles of rows. Within a tile we reduce over the vector dimension in -byte stripes: we stage the next stripe of database-point bytes (and, at high dimension, query bytes) into shared memory while the tensor cores multiply the current one, keeping a single wgmma group in flight so copies and math overlap. We move bytes into shared memory with asynchronous copies (cp.async) or with the TMA engine, neither of which ties up the warps’ registers; we use TMA for the database-point slab in our warp-specialized pipeline and cp.async otherwise (Sec. E.4). When the database-point tile is exhausted, the warpgroup drains the accumulator and runs the epilogue. We never write the score block to global memory. Each finished dot product is consumed in registers by the top- reduction, as shown in Alg. 4.
**Register top-K mirrors the CPU displacement sort (Sec. 4.2): each lane runs a private top-K tournament in registers, and we defer the cross-lane merge to the very end. We keep each lane’s running top-K for a query row in registers, sorted so the best candidate sits in slot 0 and the -th in slot (pseudocode in Alg. 7). To insert a candidate we first compare it against slot , which rejects anything worse than the current -th best. Otherwise an unrolled compare-swap chain shifts it into place, carrying the displaced entry off the end. Registers cannot be indexed by a value computed at run time, so the top- array must live at compile-time-constant slots. If any access were data-dependent, the compiler would spill the array to local memory—slower per-thread storage backed by global memory. In our measurements that spill moved the bottleneck off the matrix product and onto the epilogue, so we fully unroll the insertion to keep every slot access constant. Once the database-point window is consumed, the four lanes that own one output row hold four independent top- lists, and we merge them with a two-step butterfly: a warp shuffle exchanges each lane’s entries with its partner across lane masks 1 and 2, and we insert the partner’s entries into the local list. The base lane then writes the results in sorted order. A leaf is scored as a self-join, so its score block is symmetric. We nonetheless compute it in full, because the tensor cores need dense rectangular tiles and both edge directions are emitted for accumulation regardless.
Modes and precision. A single kernel family—not a separate kernel per precision—serves every configuration. We run it in two interchangeable pipeline modes—a single-warpgroup mode and a warp-specialized mode that splits loads from compute—and the same kernel serves the quantized i8 builds (TQ4 and RSQ8) and the unquantized fp16/tf32 configurations we evaluate as a supplement (Sec. E.3). We provide more details in Sec. E.3 and E.4, and report kernel measurements in Tab. 8 and 9.
From Online HashPrune to Sort-and-Merge
Recall that HashPrune keeps, for each point, a bounded reservoir of nearby candidates with diverse residual directions. On the CPU we implement it by simply protecting the structure using a lock. Unfortunately on GPU this leads to significantly worse contention
Algorithm 4: Segmented fused top-K scoring
Input: Tile $T=(i,m_0)$; segments/slab; scales/norms; $K$
Output: Per-query sorted top-$K$ (distance, id)
Data: $M \in \{64,128\}$; $N=128$; $W=32$ bytes
1 seg $\leftarrow$ segment $i$; $Q \leftarrow \operatorname{seg}.Q[m_0:m_0+M)$
2 initialize a register top-$K$ list for each owned query row
3 stage all $W$-byte stripes of $Q$ into shared memory
4 for $n_0=0$ to seg.count in steps of $N$ do
5 $N_{\mathrm{valid}} \leftarrow \min(N,\operatorname{seg.count}-n_0)$
6 stage database-point ids, scales, and squared norms for rows $[n_0,n_0+N_{\mathrm{valid}})$; pad the remainder tile entries
7 $C \leftarrow 0$
8 for each stripe $r$ do
9 stage $S[n_0:n_0+N_{\mathrm{valid}},r]$ into an $N$-row shared-memory tile; pad the remainder
10 $C \mathrel{+}= \operatorname{wgmma}(Q[:,r],S_{\mathrm{tile}}[:,r])$
11 for each accumulator cell $(m,n)$ owned by this lane with $n<N_{\mathrm{valid}}$ do
12 $s \leftarrow \sigma_q[m]\sigma_d[n]C[m,n]$
13 if the metric is squared $L2$ then
14 $\operatorname{score} \leftarrow \lVert q_m\rVert^2+\lVert p_n\rVert^2-2s$
15 else
16 $\operatorname{score} \leftarrow -s$
17 if $\operatorname{id}(n)\ne\operatorname{id}(m)$ then insert $(\operatorname{score},\operatorname{id}(n))$ into row $m$’s top-$K$
18 merge the four owner lanes of each row with a shuffle butterfly
19 write each row’s $K$ results in sorted order
and thus degrades performance meaningfully. We therefore replace the synchronized update with a sort. This sort-and-merge runs once per batch of leaves during leaf scoring, and each batch’s candidates merge into a global HashPrune datastructure that the final prune sparsifies into the graph. For every candidate neighbor we emit two fixed-size records, one per direction, each carrying a short sketch of the residual direction from source to target, and we radix-sort the records by owner row and distance. The sort operates on a transient buffer of two records per candidate edge, bounded by a memory parameter (the per-batch slab cap, ≈ 6 GB in our runs) and reused across batches—it does not grow with the full candidate set. After the sort, every owner’s candidates are contiguous, so we update each row’s bounded accumulator in a single sequential pass with no concurrent writes: we de-duplicate repeated targets. For colliding hashes, we keep the nearer candidate. We describe the sketch construction and record layout in more detail in Sec. E.9.
Pruning Without Candidate Recompute
ANN builds need a final sparsification step after candidate accumulation. Exact RobustPrune tests whether an accepted neighbor occludes a candidate for source . This test needs the distance . Recomputing such distances for every row would add a new irregular candidate-to-candidate scoring stage.
We instead use an approximation we call DirectEdgePrune. When we prune the neighbors of point , we check whether the accepted neighbor already has in its own neighbor-list. If that edge exists then we use the stored distance as the witnessed value for and apply the usual -prune test; if the edge was not witnessed then we proceed to the next neighbor. All rows consult a read-only snapshot of the completed candidate accumulator. Each row writes its accepted neighbors to separate scratch storage; after all pruning decisions finish, a second pass compacts these outputs into the final graph.
This relaxation of RobustPrune has one-sided error: it can miss a domination that exact RobustPrune would have found, because the needed candidate pair may be absent from the accumulator. It never prunes an edge that would have been retained by RobustPrune. The effect on degree and query quality is measured in Tab. 7: DirectEdgePrune yields denser graphs of quality comparable to those produced by a final RobustPrune.
Experimental Evaluation
Our experiments are organized around three goals: (1) quantifying the speedups we achieve for index building and -NN graph construction (Secs. 6.1 and 6.2), (2) demonstrating that the quantization and algorithmic changes employed by PiPNN II and GPiPNN preserve high index quality (Secs. 6.2 and 6.3), and (3) explaining which components in the implementations are responsible for the observed speedups (Secs. 6.3 and 6.4). In particular, we find that:
On CPU, PiPNN II is the fastest method for both the ANNS-index and -NN tasks: on average for ANNS-index build it beats the strongest quantized Vamana baseline by 5.9× and unquantized Vamana by 40.7×. For -NN building it beats quantized Vamana by 10.3× and PyNNDescent by 5.9× at equivalent recall (Sec. 6.1).
On GPU, GPiPNN is also the fastest method: on the ANNS-index task it beats Jasper by 8.1× on average (13.3× with quantization) and unquantized CAGRA by 16× (27× with quantization). On the -NN task it beats Jasper, NN-Descent, CAGRA, and IVF-PQ8 by geometric means of 7.1×, 2.9×, 9.8×, and 49.8× respectively (Sec. 6.2).
Using quantization in the build keeps query performance essentially unchanged: PiPNN-TQ and PiPNN-RSQ8 match PiPNN-FP32’s QPS at any given recall within geometric-mean ratios of 0.98 and 0.99 (Sec. 6.3).
We trace the speedups to our highly-optimized kernels: we show that our leaf-2-NN kernel achieves a 12.4× speedup over PiPNN’s prior approach. It runs at near-peak instruction throughput on CPU, and it is bandwidth-bound at high dimension on GPU, reaching 82–95% of memory throughput at (Sec. 6.3 and 6.4).
Machines. We use a Google Cloud c4-highmem-288 (288 vCPUs, 2.2 TB DRAM, Intel Granite Rapids) for billion-point datasets, and a c3-highmem-192 (192 vCPUs, 1.5 TB DRAM, Intel Sapphire Rapids) for smaller datasets. For GPU measurements we use an a3-highgpu-1g instance: one NVIDIA H100 80 GB HBM3 SXM5 (cc 9.0, 132 SMs, 3.35 TB/s HBM3) on a 26-vCPU Sapphire Rapids host with 234 GB DDR5, CUDA 12 with driver 580. GPiPNN is compiled for Hopper SM90a and run as a single-H100 builder. Datasets that exceed the 80 GB device memory are reported on CPU only.
“High-quality” indexes. We measure quality in terms of query throughput and recall. Specifically, we consider an index high-quality when its QPS-vs-recall curve is comparable to that of an unquantized ParlayANN-Vamana graph. The first version of PiPNN was shown to produce high-quality indexes, and we show in this paper that it continues to do so for quantized points.
CPU Methods. Our primary baseline is Vamana [30] as implemented in the ParlayANN library [41]. To the best of our knowledge, this is the most performant shared-memory graph-based ANNS index publicly available. We restrict our comparison to Vamana because previous work [56] already showed that it builds indexes faster and of equivalent or better quality than HCN NG [46], HNSW [40], MIRAGE [64], and FastKCNA [66].
We also consider an unpublished version of ParlayANN’s Vamana [51] that uses 8-bit scalar quantization (SQ8) for distance computations and reranks a smaller set with float precision. For dimensionalities it further uses a filtering technique based on precomputed Johnson-Lindenstrauss (JL) sketches [33] that further speeds up beam search. Quantization and filtering offers significantly faster builds and queries than unquantized Vamana while producing indexes of identical quality. Hence, we use this version when computing QPS-vs-recall curves on CPUs. For -NN graph construction, we additionally compare with a parallel implementation of NN-descent PyNNDescent [43] also in the ParlayANN library [41] that uses SQ8. The per-dataset build parameter configurations for CPU methods are detailed in Sec. G (Tab. 16 and 17).
GPU Methods. We compare GPiPNN against the two leading GPU-native graph ANNS systems: CAGRA [50] and Jasper [42]. The original CAGRA paper considered FP16 coordinates, but the library implementation supports generating the initial -NN graph via product quantization (PQ) coupled with IVF, which we evaluate here (to our knowledge) for the first time. Unquantized CAGRA does not run on unnormalized MIPS datasets, as the NN-descent implementation is specialized to L2. cuVS [48] supports MIPS graphs for CAGRA only through its IVF-PQ build path, not the NN-Descent build path that unquantized CAGRA uses.
Jasper [42] ports Vamana to GPU, leverages RaBitQ quantization [18] for search, and optimizes the greedy search kernel for latency hiding. We use Jasper's query code for our index quality studies (Figure 5 and Figure 12). This permits us to assess the quality of the indexes without the confounding issue of query performance. It was previously shown that Jasper's query routines are at least as good as CAGRA's [42]. The per-dataset build parameter configurations for GPU methods are detailed in Sec. F (Table 13 and 14).

Figure 5. GPU QPS vs. recall for DEEP-10M () and DBpedia-3072 (); all datasets in Figure 12.
| Dataset | GPiPNN (all modes) | GPiPNN (all modes) | GPiPNN (all modes) | Jasper | Jasper | Jasper reord. | CAGRA deg. | CAGRA inter. |
| DEEP-10M | 1.1 | 64 | 512 | 64 | 1.05 | Y | 64 | 128 |
| MS-Turing-10M | 1.1 | 64 | 512 | 64 | 1.1 | Y | 64 | 128 |
| DEEP-100M | 1.1 | 32 | 512 | 64 | 1.05 | Y | 64 | 128 |
| MS-Turing-100M | 1.1 | 32 | 512 | 64 | 1.1 | Y | 64 | 128 |
| DBpedia-1536 | 1.0 | 32 | 512 | 32 | 1.05 | Y | 32 | 128 |
| DBpedia-3072 | 1.0 | 32 | 512 | 32 | 1.1 | N | 32 | 192 |
| Wiki-Qwen-500K | 0.95 | 32 | 512 | 32 | 1.0 | Y | 32 | 192 |
| OpenAI-2M | 1.05 | 64 | 1024 | 64 | 1.1 | Y | 32 | 192 |
| Wiki-all-1M | 0.95 | 32 | 512 | 32 | 1.0 | Y | 32 | 128 |
| Wiki-all-10M | 0.95 | 32 | 512 | 32 | 0.95 | Y | 32 | 128 |
| MS-MARCO-10M | 0.9 | 32 | 512 | 32 | 0.9 | Y | 32 | 128 |
| DataCompDr-10M | 1.05 | 32 | 1024 | 32 | 1.1 | Y | 32 | 192 |
| Wiki-Cohere-10M | 0.95 | 32 | 512 | 32 | 0.95 | Y | 32 | 128 |
| Text2Image-10M | 0.9 | 64 | 512 | 64 | 0.9 | Y | 64 | 128 |
| MS-Arctic-1M | 0.9 | 32 | 512 | 32 | 0.9 | Y | 32 | 128 |
Table 13. Per-dataset ANNS-index build parameters (cf. Table 4). : degree; : leaf size; reord.: JASPER reorder; deg./inter.: CAGRA graph / intermediate degree.
Figure 12. Full GPU query throughput vs. recall grid for all thirteen datasets (top-right is best); the body (Figure 5) shows the DEEP-10M and DBpedia-3072 panels. Queries use Jasper’s GPU search kernel. The DataCompDr-10M, Wiki-Cohere-10M, Text2Image-10M, and MS-MARCO-10M panels use ground truth computed for the 10M crops, and the MS-Arctic-1M panel ground truth for the 1M slice; on the unnormalized MIPS sets only the CAGRA-PQ (IVF-PQ) variant is available.
Datasets. We evaluate on a diverse suite of datasets summarized in Table 1: three billion-scale datasets (DEEP [4], MS-Turing [58], Text2Image [58]) and two hundred-million-scale text datasets (MSMARCO [57] and MSMARCO-Arctic [11, 44]) obtained through the BigANN Benchmarks framework [57, 58]; Wiki-Qwen-500K (4096-d) embeddings [38]; two DBpedia datasets at 1536-d and 3072-d [52, 53]; the 12.78M image–text DataCompDr embeddings [2]; and Wiki-Cohere [54], OpenAI-ArXiv [47], and wiki-all [49]. We use a subset of these for our GPU experiments, the full collection can be seen in Table 4. For DEEP and MS-Turing we use both 10M and 100M slices; for Text2Image, DataCompDr, Wiki-Cohere, and MSMARCO we use 10M slices, and for MSMARCO-Arctic a 1M slice, as the GPU baselines (Jasper, CAGRA) do not complete at full scale on a single 80 GB H100.
| Name | Type | Dim | Size | Q | DType | Dist. | Src. |
| DBpedia1536 | Text | 1536 | 999k | 1k | f32 | L2 | [52] |
| DBpedia3072 | Text | 3072 | 999k | 1k | f32 | L2 | [53] |
| DataCompDr | T2I | 1536 | 12.78M | 1k | bf16 | L2 | [2] |
| MSMARCO-Arctic | Text | 1024 | 113.52M | 10k | f32 | MIPS | [11, 44] |
| MSMARCO | Text | 768 | 101.07M | 9376 | f32 | IP | [57] |
| Wiki-Cohere | Text | 768 | 35M | 5k | f32 | IP | [54] |
| OpenAI-ArXiv | Text | 1536 | 2.32M | 20k | f32 | L2 | [47] |
| wiki-all | Text | 768 | 88M | 10k | f32 | MIPS | [49] |
| Wiki-Qwen-500K | Text | 4096 | 500k | 100k | float | MIPS | [38] |
| DEEP | Image | 96 | 1B | 10k | f32 | L2 | [4] |
| MS-Turing | Text | 100 | 1B | 100k | f32 | L2 | [58] |
| Text2Image | T2I | 200 | 1B | 100k | f32 | MIPS | [58] |
Table 1. Summary of datasets used in our experiments.
| Dataset | gPiPNN-TQ4 | gPiPNN-RSQ8 | gPiPNN-FP16 | gPiPNN-TF32 | JASPER | CAGRA | CAGRA-FP16 | CAGRA-PQ4 | CAGRA-PQ8 |
| DEEP-10M | 2.31 | 2.32 | 2.57 | 2.73 | 8.78 | 115 | 192 | 298 | 266 |
| MS-Turing-10M | 2.63 | 2.64 | 2.88 | 3.07 | 18.1 | 116 | 124 | 176 | 193 |
| DEEP-100M | 19.4 | 19.6 | 22.3 | – | 105 | 3940 | 5391 | 3706 | 3907 |
| MS-Turing-100M | 20.1 | 20.3 | 23.2 | – | 166 | – | – | – | – |
| DBpedia-1536 | 0.54 | 0.57 | 1.08 | 1.62 | 11.9 | 11.1 | 11.3 | 45.9 | 51.8 |
| DBpedia-3072 | 0.86 | 0.90 | 1.99 | 3.03 | 39.4 | 18.5 | 18.2 | 97.9 | 124 |
| Wiki-Qwen-500K | 0.57 | 0.61 | 1.30 | 1.96 | 7.81 | 10.9 | 10.6 | 64.9 | 73.4 |
| OpenAI-2M | 1.22 | 1.29 | 2.66 | 4.12 | 26.0 | 34.6 | 34.6 | 133 | 149 |
| Wiki-all-1M | 0.39 | 0.44 | 0.64 | 0.91 | 2.17 | – | – | 26.9 | 29.4 |
| Wiki-all-10M | 3.41 | 3.53 | 6.78 | 11.0 | 32.2 | – | – | 381 | 456 |
| MS-MARCO-10M | 3.38 | 3.50 | 6.58 | 10.5 | 88.3 | – | – | 370 | 446 |
| DataCompDr-10M | 5.81 | 6.08 | – | – | 79.3 | – | – | 625 | 790 |
| Wiki-Cohere-10M | 3.41 | 3.59 | 6.70 | 10.8 | 64.5 | – | – | 345 | 415 |
| Text2Image-10M | 2.35 | 2.39 | 2.96 | 3.47 | 90.2 | – | – | 231 | 250 |
| MS-Arctic-1M | 0.46 | 0.55 | 0.81 | 1.18 | 3.75 | – | – | 34.2 | 37.6 |
Table 4. Full GPU ANNS-index native build times (s) across all GPiPNN modes (TQ4/RSQ8, unquantized FP16/TF32) and CAGRA variants; cf. the headline Table 3. Colored as in § 8. “–” marks a run that did not complete or exceeded the 80 GB H100 budget; the unquantized FP16/TF32 modes carry a 2–4× larger decoded-row footprint and so miss the largest cells (TF32 at 100M, and both on DataCompDr-10M), and plain CAGRA runs only on the L2 datasets (its cuVS NN-Descent build is L2-only). The 100M-scale rows (DEEP-100M, MS-Turing-100M) are shown for completeness but excluded from the main-text tables and the aggregate speedups of Table 6; the CAGRA DEEP-100M outlier is discussed in Sec. D.
Speedup Results on CPU
ANNS Index Build. We build PiPNN and Vamana indexes and subsequently query them under varying beam size to measure the throughput vs recall tradeoff. Representative QPS-recall curves on two datasets are shown in Figure 3; for the full set of results over all 12 datasets, refer to Figure 10 in the appendix. The methods have similar query performance across the datasets. The index build times are shown in § 8 and also included in the legends of each plot. Quantization speeds up Vamana construction by 3–15× and PiPNN by 2–8×, while showing no impact on index quality. The effects on Vamana are more pronounced on high dimensional datasets due to JL. However, even with these speedups, full precision PiPNN remains faster to build on most datasets. PiPNN II is up to 8× faster than PiPNN. Against quantized and unquantized Vamana, its geometric-mean speedups are 5.9× and 40.7×, respectively.
Figure 3. Index Quality (CPU). QPS vs. recall on two representative datasets, with per-method build times in the legends. PiPNN-FP32, PiPNN-TQ4, and PiPNN-RSQ8 trace nearly identical curves; the full set of twelve datasets is in Figure 10 (Sec. C).

Figure 10. Index Quality (CPU). QPS vs. recall on all datasets from Table 1, with per-method build times in the legends. PiPNN-FP32, PiPNN-TQ4, and PiPNN-RSQ8 trace nearly identical curves.
-NN Graph Build. To build a -NN graph with Vamana we build an ANNS index and then perform a -NN query for each point. While PiPNN could use the same approach, we find the neighbors of a point directly from its leaves [25]. We also include PyNNDescent, which is designed for direct -NN graph construction.
From a large parameter sweep, we select the fastest builds spanning different recall levels, forming a Pareto frontier for each method. Figure 4 shows two representative datasets; the full set is in Figure 11 (Sec. C). All three methods are able to produce -NN graphs of reasonably-high recall. However, thanks to PiPNN II's low construction time combined with its ability to avoid materializing a complete index, it is able to build 4–10× faster than PyNNDescent and 5–20× faster than Vamana for graphs of equivalent recall (geometric means 5.9× over PyNNDescent, and 10.3× over quantized Vamana). § 8 reports absolute build times for both tasks across our CPU datasets, alongside the unquantized baselines. PyNNDescent is omitted from the billion-scale datasets and MSMARCO because it exceeded the available memory.
Figure 4. -NN graph build time vs. recall on two representative datasets, zoomed to recall in [0.8, 1.0]. Results on the full set of datasets are shown in Figure 11 (Sec. C).

Figure 11. Full set of -NN-graph recall vs. build time results on CPUs. We note that the optimized version of pyNNDescent in ParlayANN runs out of memory on MSMARCO-101M, Deep-1B, MSTuring-1B, and Text2Image-1B.
Speedup Results on GPU
ANNS Index Build. In Table 3 we report ANNS index build time for GPiPNN-RSQ8 and FP16, as well as Jasper and CAGRA. GPiPNN-RSQ8 is fastest on every dataset. Taking the geometric mean, GPiPNN-RSQ8 builds 13.3× faster than JASPER and 27× faster than CAGRA. The largest single-dataset gaps are 43.7× over JASPER (DBpedia-3072) and 50× over CAGRA (DEEP-10M). Without quantization, GPiPNN-FP16 is on average 8.1× faster than JASPER and 16.3× faster than CAGRA. Full per-dataset build times are reported in Table 4. On the unnormalized MIPS datasets, we omit results for unquantized CAGRA, since it does not support MIPS as mentioned before. In the appendix, we show additional results with a variant that builds the index through IVF-PQ that does support it.
Table 3: GPU build times (s): ANNS index (left) and fastest -NN graph at recall (right); build-then-search includes self-search. RSQ8/FP16: quantized/unquantized GPiPNN modes; NN-Desc: NN-Descent. Coloring follows Sec. 6.1; full results in Table 4 and 5.
| Dataset | ANNS index | -NN @ R | ||||||
| RSQ8 | FP16 | Jasper | CAGRA | RSQ8 | FP16 | NN-Desc | Jasper | |
| DEEP-10M | 2.32 | 2.57 | 8.78 | 115 | 4.43 | 4.65 | 29.1 | 10.8 |
| MS-Turing-10M | 2.64 | 2.88 | 18.1 | 116 | 15.9 | 16.3 | 32.3 | 19.1 |
| DBP1536 | 0.57 | 1.08 | 11.9 | 11.1 | 1.84 | 2.24 | 4.78 | 11.3 |
| DBP3072 | 0.90 | 1.99 | 39.4 | 18.5 | 3.00 | 4.00 | 6.40 | 21.8 |
| Wiki-Qwen-500K | 0.61 | 1.30 | 7.81 | 10.9 | 2.38 | 3.11 | 3.60 | 13.1 |
| OpenAI | 1.29 | 2.66 | 26.0 | 34.6 | 2.46 | 3.55 | 12.7 | 24.4 |
| WikiAll-1M | 0.44 | 0.64 | 2.17 | – | 1.78 | 2.03 | 4.03 | 4.60 |
| WikiAll-10M | 3.53 | 6.78 | 32.2 | – | 8.50 | 11.3 | 39.2 | 82.6 |
| MS-MARCO-10M | 3.50 | 6.58 | 88.3 | – | 30.1 | 37.0 | 39.4 | 410 |
| DataComp-10M | 6.08 | – | 79.3 | – | 15.7 | – | – | 129 |
| WikiCohere-10M | 3.59 | 6.70 | 64.5 | – | 31.1 | 38.7 | 49.4 | 217 |
| Text2Image-10M | 2.39 | 2.96 | 90.2 | – | 5.00 | 5.47 | 31.1 | 106 |
| MS-Arctic-1M | 0.55 | 0.81 | 3.75 | – | 0.96 | 1.19 | 4.45 | 39.0 |
Table 3.
Table 2: CPU build times (seconds). Left: ANNS index build, best high-recall configuration of each method (QPS-vs-recall curves appear in Figure 10). Right: -NN graph build, fastest swept configuration achieving recall . Each half is colored independently: per-row fastest method bolded and cells shaded by log-slowdown vs the row min (green = fastest, red = slowest); “–” indicates method did not achieve recall cutoff. VF32 is unquantized Vamana; VQ is Vamana with quantization and optional filtering; NNDQ is PyNNDescent with SQ8.
| Dataset | ANNS index | -NN @ R | |||||
| PiPNN II | PiPNN | VF32 | VQ | PiPNN II | VQ | NNDQ | |
| Wiki-Qwen-500K | 3.6 | 18 | 117 | 8.0 | 2.4 | 32 | 12 |
| DBP1536 | 1.9 | 15 | 122 | 9.3 | 1.7 | 37 | 13 |
| DBP3072 | 4.7 | 28 | 228 | 15 | 4.2 | 57 | 19 |
| OpenAI | 4.4 | 36 | 342 | 31 | 4.2 | 61 | 32 |
| DataComp | 35 | 245 | 1918 | 208 | 58 | 506 | 421 |
| WikiCohere | 56 | 352 | 4317 | 491 | 212 | 5303 | 1442 |
| WikiAll | 146 | 892 | 11780 | 1492 | 576 | 3137 | 1903 |
| MSMARCO | 175 | 1107 | 13510 | 1743 | 1015 | 9751 | – |
| MS-Arctic | 249 | 1298 | 14440 | 2568 | 230 | 2157 | 1599 |
| DEEP | 564 | 1484 | 8178 | 3142 | 1605 | 6251 | – |
| MS-Turing | 567 | 1480 | 5719 | 2772 | 1051 | 4630 | – |
| Text2Image | 730 | 2027 | 8605 | 3784 | 935 | 12108 | – |
Table 2.
Build speed does not come at the cost of query quality. Figure 5 plots GPiPNN’s query throughput against recall for a low-dimensional (, DEEP-10M) and a high-dimensional (, DBpedia-3072) dataset. Across the recall range, GPiPNN’s QPS is equal or higher than that of JASPER and the CAGRA variants. The same conclusion holds on the full benchmark set, shown in Figure 12.
-NN Graph Build. Next, we evaluate -NN graph building. We consider additional methods from cuVS, namely NN-Descent and IVF-PQ. For each method and dataset, we sweep a variety of build-time parameters and retain the fastest configuration whose resulting graph achieves recall (Table 3); the full per-method, per-dataset build parameters and software versions are given in Sec. F. Entries where no configuration meets the recall target are marked “–”. For GPiPNN-RSQ8 and cuVS NN-Descent we show the direct -NN graph build time; for JASPER, IVF-PQ, and CAGRA it is the index-build time plus the time to query all points against the built index.
GPiPNN-RSQ8 is the fastest-building method on all thirteen datasets, including MS-MARCO-10M (MIPS, ), where it builds in 30.1 s against 39.4 s for the next-fastest NN-Descent. Aggregated as a geometric mean, GPiPNN-RSQ8 is 7.12 faster than JASPER, 2.91 faster than NN-DESCENT, 9.84 faster than CAGRA, and 49.80 faster than IVF-PQ8. CAGRA and IVF-PQ8 are reported in the full comparison in Table 5. CAGRA’s ANNS construction works only on Euclidean data.
| Dataset | gPiPNN-TQ4 | gPiPNN-RSQ8 | gPiPNN-FP16 | gPiPNN-TF32 | JASPER | NN-Descent | NN-Descent-FP16 | IVF-PQ8 | CAGRA |
| DEEP-10M | – | 4.43 | 4.65 | 4.84 | 10.8 | 29.1 | 30.0 | 49.9 | 106 |
| MS-Turing-10M | – | 15.9 | 16.3 | 17.4 | 19.1 | 32.3 | 30.3 | – | 106 |
| DBpedia-1536 | 1.81 | 1.84 | 2.24 | 2.92 | 11.3 | 4.78 | 4.78 | 64.1 | 14.9 |
| DBpedia-3072 | 2.94 | 3.00 | 4.00 | 5.52 | 21.8 | 6.40 | 6.41 | 143 | 23.3 |
| Wiki-Qwen-500K | 2.35 | 2.38 | 3.11 | 4.29 | 13.1 | 3.60 | 3.60 | 93.5 | 14.6 |
| OpenAI-2M | 6.15 | 2.46 | 3.55 | 4.89 | 24.4 | 12.7 | 12.7 | 186 | 36.6 |
| Wiki-all-1M | 1.77 | 1.78 | 2.03 | 2.46 | 4.60 | 4.03 | 4.02 | 40.1 | – |
| Wiki-all-10M | 27.0 | 8.50 | 11.3 | 15.7 | 82.6 | 39.2 | 39.5 | 1721 | – |
| MS-MARCO-10M | – | 30.1 | 37.0 | 51.9 | 410 | 39.4 | 39.5 | – | – |
| DataCompDr-10M | 50.6 | 15.7 | – | – | 129 | – | – | – | – |
| Wiki-Cohere-10M | – | 31.1 | 38.7 | 54.8 | 217 | 49.4 | 49.5 | 3127 | – |
| Text2Image-10M | – | 5.00 | 5.47 | 5.95 | 106 | 31.1 | 31.1 | – | – |
| MS-Arctic-1M | 0.90 | 0.96 | 1.19 | 1.51 | 39.0 | 4.45 | 4.45 | 70.9 | – |
Table 5. Full -NN-graph native build times (s), fastest configuration of each method reaching graph-fidelity recall ≥ 0.9; cf. the headline Table 3. GPiPNN is shown in TQ4/RSQ8 plus unquantized FP16/TF32 supplement modes; IVF-PQ4 is omitted (it met the floor on no dataset). Colored as in § 8. “–” marks cells where no configuration met the floor, the build ran out of memory, or the metric is unsupported. The 4-bit TQ4 mode is too lossy to reach 0.9 on the harder cells, while the FP16/TF32 modes clear the floor wherever they fit; cuVS CAGRA (NN-Descent build) is L2-only, so it is absent on the MIPS datasets.
CPU Ablations
Leaf 2-NN kernel. We evaluate the leaf 2-NN kernel described in Sec. 4.3 on a single core of an Intelake CPU by scoring a leaf of 800 points gathered from a dataset of 1M 768-dimensional points. Figure 6 divides runtime into three components: prepare, the dot-product GEMM, and top-2 filtering. Prepare covers work done before the inner loop runs: decoding and packing the database vectors into the transposed panel layout, and zero-initializing the top-2 trackers. The original PiPNN [56], which scores the leaf with Eigen’s float32 GEMM and extracts top-2 with Highway’s VQSort, runs in 12.90 ms. Our final optimized kernel runs in 1.04 ms, a 12.4 improvement.
Figure 6. ProcessLeafTop2 ablation: runtime breakdown and effective throughput across cumulative optimizations. Throughput counts operations although Lower Triangle computes 1.96× fewer.
We walk through the optimizations in Figure 6 in order. As we apply each optimization, the dominant cost increasingly shifts to the top-2 filtering step, until SIMD Scatter addresses that bottleneck. TQ Flat replaces the float32 GEMM with an int8 dot product using vdpbusd over the baseline’s data layout (rows=points, columns=dimensions). Processing 4 times more elements per SIMD instruction yields a 1.92 speedup over the baseline. The block-transposed panel layout (TQ Transposed) regresses against TQ Flat prior to query unrolling. Query Unrolling subsequently allows the transposed layout to come out ahead of flat by enabling better instruction-level parallelism. Transpose furthermore unlocks Panel Unrolling, which yields another 1.58 improvement by keeping the query broadcasts in registers across four database panels.
Lower Triangle roughly halves the GEMM work (1.96), exposing filtering as the new bottleneck at 58% of the total time. Vectorizing the scatter (SIMD Scatter, described in § 4.3) is the largest single jump, 2.1×, and shrinks filtering back to roughly 10%.
In a standalone benchmark we were able to sustain 342 GMAC/s when issuing vpdpbusd from registers (279 with memory loads). The GEMM part of our kernel runs at GMAC/s, where 0.69 is the fraction of time spent in GEMM. This indicates that the GEMM runs at peak performance. This also matches the theoretical expectation of 332.8 GMAC/s on a 2.6 GHz base clock core leveraging two execution ports, if we account for turboboost.
Pruning kernel. Recall that PiPNN II uses the RobustPrune procedure from DiskANN [30]. With the leaf and partitioning kernels accelerated, RobustPrune becomes a non-negligible part of the runtime. We compare three implementations which differ in how they compute distances between RobustPrune candidates. The baseline “Naive TQ (vectorized)” computes the distances between a candidate and all prior survivors using one-to-many TurboQuant. “Distmat (panel-based)” precomputes the full candidate–candidate distance matrix in a single GEMM pass using the techniques from § 4.1, then prunes using those distances. Note that this approach is not able to exit early when a candidate gets pruned. “Fused (panel-based)” is a variant where we store only survivors and the next query batch (size 6) in the panel layout. We then compute distances from the next query batch against the survivors and itself. After pruning, we copy over the survivors from this batch. Compared to Distmat, this eliminates redundant work by only comparing with pruned candidates in the same query batch. Compared to the naive version, however, a query still does not exit early if pruned.
As can be seen in Figure 7, both panel-based strategies provide significant speedup over the Naive method (Distmat gets a 2.1× improvement on average over Naive). Additionally, leveraging the Fused version gives a 1.08× improvement over Distmat.
Figure 7. RobustPrune implementations absolute time in seconds (annotated above bar) and slowdown vs. fastest.
GPU Ablations
Figure 8 in Appendix § 15.§ 10 shows per-stage and per-kernel runtime breakdowns on GPU. Leaf processing dominates the runtime on GPU as well, though less than on CPU. We perform a Speed of Light (SOL) analysis to identify the % of system utilization with respect to the theoretical hardware peak.
Figure 8. Build component breakdown of GPiPNN-RSQ8 by pipeline stage (left) and by kernel (right), as a percentage of the native build time (absolute build time above each bar). Datasets are ordered by dimension. No single kernel dominates, and the bottleneck shifts from the prune and sub-leader scan at low dimension to the leaf score and edge-hash at high dimension.
Leaf2-NN kernel. The performance bottleneck of the kernel on the H100 GPU shifts depending on the vector dimension. At higher dimensions (, e.g., openai-2M and dbpedia-3072), data streaming for candidate comparisons saturates the L2 cache bandwidth. Unified memory throughput reaches 82–95%, indicating that L2 is the limiting tier rather than DRAM, which remains at 37–52%. Meanwhile, the SM pipelines hold steady at 46–49%, falling below Nsight Compute’s (NCU) 60% threshold for a compute-bound state. For intermediate dimensions (, e.g., wiki-all-10M), neither the compute nor memory pipelines saturate: the SM sits at 50% and the memory hierarchy at 41%. Here, NCU attributes the performance gap to latency rather than throughput. The kernel achieves only 26–28% occupancy, tightly constrained by its 28% theoretical limit due to high shared-memory pressure and an allocation of 96 registers per thread. This occupancy limitation persists at the lowest dimensions (, e.g., e5-100M; Table 9). The working set resides entirely within cache which drops DRAM traffic to 4% and leaves the kernel strictly occupancy-bound.
| Dataset () | mode | SM% | Mem% | DRAM% | L1% | Occ% | regime |
| WikiAll-10M (768) | RSQ8 | 50.1 | 40.6 | 13.9 | 40.1 | 27.7 | occupancy |
| WikiAll-10M (768) | TQ4 | 50.1 | 40.8 | 14.0 | 40.1 | 27.6 | occupancy |
| WikiAll-10M (768) | FP16 | 37.3 | 98.0 | 30.3 | 52.8 | 22.4 | L2-bound |
| WikiAll-10M (768) | TF32 | 30.2 | 97.9 | 45.8 | 53.6 | 22.5 | L2-bound |
| OpenAI (1536) | RSQ8 | 48.7 | 81.8 | 36.6 | 43.6 | 27.6 | L2-bound |
| OpenAI (1536) | TQ4 | 49.0 | 78.3 | 35.0 | 43.7 | 27.6 | L2-bound |
| OpenAI (1536) | FP16 | 31.2 | 97.6 | 43.9 | 53.8 | 22.5 | L2-bound |
| OpenAI (1536) | TF32 | 27.9 | 97.8 | 55.8 | 56.5 | 22.2 | L2-bound |
| DBP3072 (3072) | RSQ8 | 45.6 | 94.8 | 51.9 | 51.0 | 27.7 | L2-bound |
| DBP3072 (3072) | TQ4 | 46.0 | 90.4 | 50.9 | 51.1 | 27.7 | L2-bound |
| DBP3072 (3072) | FP16 | 27.7 | 97.7 | 54.1 | 56.4 | 22.2 | L2-bound |
| DBP3072 (3072) | TF32 | 26.2 | 97.2 | 64.0 | 54.4 | 22.5 | L2-bound |
| DEEP (96) | RSQ8 | 49.4 | 23.1 | 4.4 | 23.1 | 26.3 | occupancy |
| DEEP (96) | TQ4 | 49.4 | 23.1 | 4.4 | 23.1 | 26.3 | occupancy |
| DEEP (96) | FP16 | 46.5 | 26.1 | 7.0 | 26.1 | 24.9 | occupancy |
| DEEP (96) | TF32 | 46.8 | 42.0 | 12.4 | 31.4 | 24.9 | occupancy |
Table 9. Leaf 2-NN kernel speed-of-light utilization across build precision and dimension (single H100, GPiPNN; columns as in Tab. 8). The fp16/tf32 rows are the unquantized supplement; “occupancy” marks the latency/occupancy-bound regime where neither the SM nor the memory pipe reaches 60% of peak.
Index Quality. Figure 5 shows QPS vs recall on a low- and a high-dimensional dataset. Across the recall range PiPNN’s curves sit on or above those of JASPER and CAGRA, and the same holds on the full benchmark set (Figure 12).
Using DirectEdgePrune produces 30–58% denser graphs, since the method does not prune some edges that RobustPrune would. Still, index quality is comparable between the two pruning methods (Table 7). DirectEdgePrune cuts GPU build time by up to 1.4× on the high-dimensional datasets. While DirectEdgePrune could increase memory footprint, the maximum degree between the two pruning methods is identical, so in the Jasper query implementation there is no difference in terms of allocated memory.
Discussion & Conclusion
PiPNN introduced a fast, hardware-friendly route to high-quality proximity-graph construction, but its original implementation left substantial performance on the table. In this paper we fully realize PiPNN’s potential by accelerating the GEMM and top- steps, via quantization, fusing GEMM with per-query top- selection into a single in-register pass, as well as vectorizing and tailoring the top- selection to the specific . Instantiating this design on shared-memory CPUs as PiPNN II and on GPUs as GPiPNN yields large speedups over the strongest prior state-of-the-art methods on both platforms while preserving equivalent query performance.
In future work we plan to scale beyond a single machine and port the design to other accelerators. PiPNN’s structure is well-suited to the distributed setting: partitioning creates independent subproblems, leaves can be processed independently, and HashPrune merges candidate sets without coordinating on global state.
Beam Search Pseudocode
For completeness, we provide pseudocode for the standard beam-search graph-query procedure described in § 2. Given a navigation graph over points , a beam search is a greedy search with intermediate storage (called the beam). Given a source node in the graph and a query point , a beam search with beam width works as follows. We maintain two sets: a set containing up to encountered points that are closest to (often called the “beam”), and the set of all points visited. Visiting a point adds all its unseen neighbors to the beam, then adds to the visited set. The algorithm begins by initializing the beam with only the source and an empty visited set. We then visit the unvisited node in the beam closest to , repeating until every node in the beam has been visited. Because the distance of the points in the beam to the target decreases monotonically, this process converges, at which point we return the final state of the beam.
Algorithm 5: BeamSearch
Input: a graph over , an entry point, a query point, and a beam width
Output: containing the closest points to encountered during the search
;
;
while do
;
;
;
if then
the points in with smallest distance to ;
return ;
HashPrune Pseudocode
Here we document and give pseudocode for the HashPrune online pruning procedure used by PiPNN (§ 3). The algorithm is reproduced verbatim from [56].
Motivation. Pruning ensures that each vertex connects to neighbors in many different directions, so that greedy search can route quickly from any point to any other. HashPrune achieves this with locality-sensitive hashing (LSH) [9]: it discards candidate edges that are directionally similar to edges already kept. Working with relatively low dimensional hashes () also lets the procedure operate on low-dimensional sketches rather than full vectors, so pruning avoids fetching high-dimensional data.
Residualized hashing. HashPrune draws a fixed set of random hyperplanes through the origin. For each point it derives an individualized hash that hashes the residual of a candidate : the -th bit records which side of the -th hyperplane the residual falls on. Two candidates collide under with probability , where is the angle between and and is the number of hyperplanes [9]. Hashing the residual thus draws probabilistic cones centered on , and the number of hyperplanes controls how finely those cones partition direction space.
Insertion. To prune the candidate stream for a point , HashPrune maintains a reservoir of size at most keyed by hash value. For each candidate it computes . If the bucket is already occupied, it keeps whichever of the two candidates lies closer to . Otherwise it inserts , and when the reservoir is full it evicts the candidate farthest from . The reservoir therefore retains the nearest point in each cone while never exceeding entries, which bounds memory up front and lets it be allocated in a single contiguous block rather than grown dynamically.
History independence. The final reservoir depends only on the candidate set, not on the order candidates arrive in: dropping the size limit leaves exactly the nearest point in each bucket, and the size limit only ever evicts the farthest retained candidate. History independence lets candidates be merged in arbitrary order, partition by partition, without fragmenting the graph, and makes PiPNN’s partitioning-based construction deterministic.
Algorithm 6: HashPrune
Input: a stream of candidate points, fitted with dissimilarity measure , point , size limit
Output: A set of size at most
an empty key-value store mapping hashes to points;
for do
if then
if then
;
else
if then
;
else
;
if then
;
;
return ;
Additional Experiments
This appendix presents the full per-dataset query-throughput and -NN-graph recall results, together with supporting ablations, for the datasets listed in Table 1. For datasets that we report at multiple scales (DEEP, MS-Turing, Text2Image, MSMARCO), we show the largest slice.
Full GPU Build-Time Tables
For completeness, Table 4 and Table 5 report the GPU build-time comparisons of Sec. 6.2 across the full set of GPiPNN and baseline variants—adding GPiPNN-TQ4, the fp16/tf32 unquantized modes, the four CAGRA variants, and NN-Descent-FP16. The table in the main part (Table 3) contains a subset of these configurations. The build parameters behind these tables, the tuning protocol, and the software environment are reported in Sec. F.
Aggregate speedups. Table 6 summarizes the per-dataset build times of Tab. 3 as the geometric-mean and maximum build-time speedup of GPiPNN-RSQ8 over each GPU baseline, taken over the datasets that baseline completes. On proximity-graph (ANNS index) construction GPiPNN-RSQ8 is the fastest builder on every dataset, a geometric-mean 13.3× over JASPER and 27× over unquantized CAGRA, peaking at 43.7× (DBpedia-3072) and 50× (DEEP-10M). On -NN-graph construction it is a geometric-mean 7.12×, 2.91×, and 9.84× faster than JASPER, NN-Descent, and CAGRA respectively, and is the fastest builder on every cell. These ANNS-index aggregates are taken over the ≤10M-scale datasets; the two 100M-scale rows of Table 4 are excluded, for the reason discussed next.
| Build | Baseline | Geo. mean | Max | |
| ANNS index | Jasper | 13 | 13.3× | 43.7× |
| ANNS index | CAGRA | 6 | 27× | 50× |
| -NN graph | Jasper | 13 | 7.12× | 40.7× |
| -NN graph | NN-Descent | 12 | 2.91× | 6.56× |
| -NN graph | CAGRA | 6 | 9.84× | 23.8× |
Table 6. Build-time speedup of GPiPNN-RSQ8 over each GPU baseline, reported as the geometric mean and maximum over the datasets that baseline completes (computed from Table 3 and the full Table 5); is the number of such datasets. The ANNS-index rows exclude the two 100M-scale datasets, whose CAGRA build is an outlier (see Sec. D).
The 100M-scale CAGRA build is an outlier. Table 4 also reports the two 100M-scale datasets (DEEP-100M, MS-Turing-100M). We exclude these from the aggregate speedups above and from the main-text tables because the CAGRA DEEP-100M build is anomalous. At 3940 s it is ≈4.7× slower than the 825.6 s that Jasper report for CAGRA on the same dataset and graph degree [42]—measured there on a slower A100. We reproduced the figure (3868 s on our H100) and traced it to the cuVS 25.04 large-scale CAGRA graph-build path rather than to an intrinsic property of the dataset: it is insensitive to memory-pool, device-residency, and batching settings. GPiPNN itself builds both 100M graphs in ≈20 s (5.4× and 8.2× faster than Jasper on DEEP-100M and MS-Turing-100M, respectively), so its scaling is unaffected; we omit the 100M cells from the headline averages only to avoid reporting speedups against an unreliable CAGRA baseline.
GPiPNN Kernel Details
This appendix collects implementation detail deferred from § 5.
Flattened routing keys
Sec. 5.1 flattens PiPNN’s recursion into two scoring assignment passes joined by radix sorts. The current implementation has no third assignment or refinement pass: after the second-level assignments, oversized second-level buckets are split by the bin-packing walk described below.
Pass 1: top-level leaders. Every point scores against the sampled top-level leader set and keeps its best leaders (default ). The kernel emits pairs with key , and a radix sort makes each top-level bucket a contiguous run. The point array is also permuted by each point’s best top-level leader; all later graph work uses this permuted row space until the final export remap.
Pass 2: sub-leaders. Inside each top-level bucket, the host samples a bucket-local sub-leader candidate set. Each bucket member scores against only that bucket’s sub-leader candidates and keeps its best (default ). The pass emits pairs keyed by the group-local sub-leader label ; sorting and run-length encoding these keys exposes the second-level buckets. With the default fanout, a point can therefore appear in up to leaf memberships.
Bin packing. The second-level buckets are then packed into leaf-sized work units. This step does not introduce new leaders or new geometric assignments. It only splits oversized buckets and merges small adjacent buckets within the same parent range so the leaf scorer sees regular batch sizes. The implementation uses a count/assign/broadcast walk over the sorted bucket runs: first count the bins each parent range will produce, then assign compact leaf ids to runs, then broadcast those ids back to the membership array. The broadcast keys are monotone, so no second post-pack sort is needed. Sub-leader sampling is keyed by the global top-level bucket id, so changing the number of streamed leader groups changes memory use but not the sampled partition.
Partitioning-pass operand staging
As discussed in § 6, the assignment passes are expressed as segmented top- scoring. Here we provide more details on how the slabs of segments work.
Top-level leader slab. The top-level pass samples leaders (auto-tuned up to 4096) and gathers those rows once into a dense leader slab. The single segment then scores all points against that slab and emits synthetic leader labels per point. The synthetic labels avoid self-skip behavior in the shared scoring primitive, since a sampled leader must be allowed to assign to itself.
Sub-leader slabs. For each streamed range of top-level buckets, the host samples sub-leaders inside each bucket and resolves them to permuted row ids. All sub-leaders for the group are gathered into one dense slab, and the launch contains one score segment per nonempty top-level bucket. Each segment points to its bucket’s contiguous sub-leader slice with an offset and count. This lets one scoring launch handle buckets with different candidate counts while keeping the operand layout dense.
Decoded rows across precisions
The host-side TurboQuant encoder stores TQ4 and RSQ8 in their packed code formats, but the GPU pipeline expands them before the assignment and leaf scoring stages. TQ4 is decoded through its 16-entry codebook into signed INT8 rows, RSQ8 is copied into the same signed-byte decoded layout, and padding beyond the true dimension is zeroed in the decoded domain. The segmented top- primitive therefore sees the same decoded INT8 row contract for both TQ modes.
The unquantized supplement uses the same decoded-base interface. The loader reads float32 rows, normalizes each row to unit length, records the original norm, and the device decode converts the normalized base to fp16 or tf32 rows. The scoring primitive then switches operand traits while the surrounding gather, accumulation, canonicalization, pruning, and export stages remain the same. The TQ paths are validated by bitwise-equality tests against a reference decode; the unquantized fp16 and tf32 supplement paths, which are not bit-exact, are validated by recall-threshold tests.
Scoring pipeline modes
The segmented top- primitive of § 6.2 runs in two pipeline modes behind one interface. In the unified mode a single warpgroup performs both the copies and the matrix products, synchronizing on shared memory once per stripe; we use it for small segments, where it is the simplest and fastest path. In the warp-specialized mode a dedicated producer warp issues the TMA and gather copies while the consumer warpgroups compute, so loads and matrix products run on separate warps. The two modes produce identical results. In either mode two consumer warpgroups can share a thread block to score a 128-row query tile () against one shared-memory ring of database-point rows, so each row is loaded once and reused across both 64-row halves. We use this variant for the small- builds (). We stage the query operands into shared memory once and reuse them when a 64-row query tile fits—up to 768 bytes of decoded operand per row—and stream them alongside the database points above that width. The same kernel serves the quantized i8 builds and the unquantized fp16/tf32 modes, which differ only in the operand type and accumulator (Sec. E.3).
Register top- epilogue
The scoring epilogue of § 6.2 keeps each query row’s top- in registers and, once the candidate sweep finishes, merges the four lanes that own a row with a butterfly shuffle (Alg. 7).
Algorithm 7: Register top- insertion and four-lane butterfly merge
Data: Per-lane registers d[0:], i[0:], sorted ascending in canonical order (d[0] best, ties broken by smaller id)
Insert candidate (c, j) into the sorted top-
if then return worse than -th best: one compare
for to do
if then
Merge the four lanes that own one output row
for do
snapshot the partner first
foreach of do insert it as above
Leaf kernel across precision and dimension
Tab. 8 reports the RSQ8 leaf kernel on the high-dimensional datasets; Tab. 9 gives the full sweep across the four build precisions (RSQ8, TQ4, and the unquantized fp16/tf32 supplement) and all four datasets. Wider operands push the kernel into the memory hierarchy: at a fixed dimension the unquantized fp16/tf32 paths load 2–4× the bytes per coordinate, so they saturate L2 (≈ 98% of unified memory throughput) even at , where the INT8 paths are still occupancy-bound. Dimension has the same effect: the
| Dataset () | 2-NN% | SM% | Mem% | DRAM% | L1% | Occ% | regime |
| WikiAll-10M (768) | 24.1% | 50.1 | 40.6 | 13.9 | 40.1 | 27.7 | occupancy |
| OpenAI (1536) | 20.6% | 48.7 | 81.8 | 36.6 | 43.6 | 27.6 | L2-bound |
| DBP3072 (3072) | 25.5% | 45.6 | 94.8 | 51.9 | 51.0 | 27.7 | L2-bound |
Table 8. Leaf 2-NN kernel SOL analysis for GPiPNN-RSQ8 (full precision sweep in Tab. 9). Columns: “2-NN%” is the leaf kernel’s share of the build time. “SM%”/“Mem%” are NCU compute- and memory-pipe throughput; “Occ%” is achieved occupancy (28% ceiling, set by 96 registers/thread and SMEM); “regime” names the binding resource.
INT8 leaf is L2-bound at but occupancy-bound at . Only low-dimensional deep-10M () stays occupancy-bound in every precision: its working set is small enough that neither pipe saturates regardless of operand width. Achieved occupancy is 22–28% throughout, set by the kernel’s 96 registers per thread and shared-memory footprint.
All major build kernels across the speed-of-light
Tab. 8 and 9 characterize the leaf 2-NN kernel; here we apply the same speed-of-light methodology to every major build kernel. Tab. 10 gives the RSQ8 picture across dimension, and Tab. 11 and 12 sweep all four build precisions. The comparable-cost kernels sit in different speed-of-light regimes, so no single kernel dominates the build:
The leaf 2-NN and sub-leader scans share the score_topk primitive and the same regime shift—L2-bound at , latency/occupancy-bound at —at ≈ 28% achieved occupancy.
The top-leader scan () is capped at ≈ 19% occupancy by register pressure: latency-bound at low dimension, reaching the L2 ceiling only at . It is individually small and folds into the cluster stage (hence no %build entry).
| Kernel | Dataset () | %build | SM% | Mem% | DRAM% | L1% | Occ% | regime |
| top-leader scan | WikiAll-10M (768) | – | 50.3 | 29.5 | 2.5 | 20.6 | 18.7 | occupancy |
| top-leader scan | OpenAI (1536) | – | 46.2 | 63.5 | 10.6 | 34.2 | 18.7 | L2-bound |
| top-leader scan | DBP3072 (3072) | – | 42.0 | 83.3 | 32.6 | 49.5 | 18.6 | L2-bound |
| top-leader scan | DEEP (96) | – | 63.1 | 9.6 | 0.6 | 9.6 | 18.7 | SM-bound |
| sub-leader scan | WikiAll-10M (768) | 19.0% | 49.0 | 55.0 | 2.5 | 51.7 | 28.0 | occupancy |
| sub-leader scan | OpenAI (1536) | 15.6% | 44.8 | 78.4 | 37.1 | 54.4 | 28.0 | L2-bound |
| sub-leader scan | DBP3072 (3072) | 7.2% | 42.8 | 88.3 | 44.7 | 62.1 | 27.9 | L2-bound |
| sub-leader scan | DEEP (96) | 20.2% | 49.1 | 28.6 | 0.9 | 28.5 | 27.7 | occupancy |
| leaf 2-NN | WikiAll-10M (768) | 24.1% | 50.1 | 40.6 | 13.9 | 40.1 | 27.7 | occupancy |
| leaf 2-NN | OpenAI (1536) | 20.6% | 48.7 | 81.8 | 36.6 | 43.6 | 27.6 | L2-bound |
| leaf 2-NN | DBP3072 (3072) | 25.5% | 45.6 | 94.8 | 51.9 | 51.0 | 27.7 | L2-bound |
| leaf 2-NN | DEEP (96) | 15.6% | 49.4 | 23.1 | 4.4 | 23.1 | 26.3 | occupancy |
| edge-hash | WikiAll-10M (768) | 14.7% | 87.1 | 31.1 | 6.0 | 31.1 | 93.9 | SM-bound |
| edge-hash | OpenAI (1536) | 20.9% | 88.5 | 29.3 | 5.4 | 29.3 | 94.9 | SM-bound |
| edge-hash | DBP3072 (3072) | 24.7% | 89.2 | 28.4 | 4.4 | 28.3 | 95.6 | SM-bound |
| edge-hash | DEEP (96) | 5.1% | 78.9 | 41.8 | 3.6 | 41.8 | 86.9 | SM-bound |
| direct-edge prune | WikiAll-10M (768) | 12.7% | 67.9 | 21.1 | 3.2 | 21.1 | 53.6 | SM-bound |
| direct-edge prune | OpenAI (1536) | 7.5% | 69.9 | 22.1 | 3.0 | 22.1 | 55.5 | SM-bound |
| direct-edge prune | DBP3072 (3072) | 3.9% | 73.9 | 24.1 | 3.9 | 24.2 | 60.5 | SM-bound |
| direct-edge prune | DEEP (96) | 23.7% | 76.1 | 22.4 | 5.3 | 22.4 | 65.4 | SM-bound |
Table 10. Per-kernel speed-of-light utilization on a single H100 (GPiPNN-RSQ8; , max_cand, leaf target 1024, fanout 8,4; columns as in Tab. 8). “%build” is the kernel’s share of the native GPU build from –diag; the top-leader scan is not separable from the cluster stage (“–”). The leaf and sub-leader sub-timers run on two overlapped streams, so their shares are taken against the native build and need not sum within a stage.
| Dataset () | mode | SM% | Mem% | DRAM% | L1% | Occ% | regime |
| WikiAll-10M (768) | RSQ8 | 50.3 | 29.5 | 2.5 | 20.6 | 18.7 | occupancy |
| WikiAll-10M (768) | TQ4 | 50.5 | 29.1 | 2.5 | 20.7 | 18.7 | occupancy |
| WikiAll-10M (768) | FP16 | 42.7 | 60.5 | 10.2 | 33.5 | 18.7 | L2-bound |
| WikiAll-10M (768) | TF32 | 40.0 | 83.5 | 32.4 | 47.5 | 18.7 | L2-bound |
| OpenAI (1536) | RSQ8 | 46.2 | 63.5 | 10.6 | 34.2 | 18.7 | L2-bound |
| OpenAI (1536) | TQ4 | 46.6 | 60.9 | 10.2 | 34.1 | 18.7 | L2-bound |
| OpenAI (1536) | FP16 | 40.5 | 80.5 | 31.2 | 47.9 | 18.7 | L2-bound |
| OpenAI (1536) | TF32 | 37.4 | 88.3 | 34.9 | 54.6 | 18.7 | L2-bound |
| DBP3072 (3072) | RSQ8 | 42.0 | 83.3 | 32.6 | 49.5 | 18.6 | L2-bound |
| DBP3072 (3072) | TQ4 | 42.0 | 83.2 | 32.5 | 49.6 | 18.6 | L2-bound |
| DBP3072 (3072) | FP16 | 37.5 | 90.0 | 35.5 | 54.6 | 18.6 | L2-bound |
| DBP3072 (3072) | TF32 | 35.5 | 92.7 | 37.4 | 56.5 | 18.6 | L2-bound |
| DEEP (96) | RSQ8 | 63.1 | 9.6 | 0.6 | 9.6 | 18.7 | SM-bound |
| DEEP (96) | TQ4 | 63.2 | 9.6 | 0.6 | 9.6 | 18.7 | SM-bound |
| DEEP (96) | FP16 | 62.7 | 11.9 | 1.0 | 11.9 | 18.7 | SM-bound |
| DEEP (96) | TF32 | 61.2 | 15.9 | 1.6 | 16.0 | 18.7 | SM-bound |
| WikiAll-10M (768) | RSQ8 | 49.0 | 55.0 | 2.5 | 51.7 | 28.0 | occupancy |
| WikiAll-10M (768) | TQ4 | 49.1 | 55.0 | 2.5 | 51.7 | 28.0 | occupancy |
| WikiAll-10M (768) | FP16 | 39.1 | 97.7 | 20.6 | 52.5 | 23.3 | L2-bound |
| WikiAll-10M (768) | TF32 | 30.2 | 98.7 | 39.3 | 52.4 | 23.4 | L2-bound |
| OpenAI (1536) | RSQ8 | 44.8 | 78.4 | 37.1 | 54.4 | 28.0 | L2-bound |
| OpenAI (1536) | TQ4 | 44.8 | 78.6 | 37.2 | 54.4 | 28.0 | L2-bound |
| OpenAI (1536) | FP16 | 31.2 | 98.2 | 38.9 | 52.5 | 23.3 | L2-bound |
| OpenAI (1536) | TF32 | 27.0 | 98.3 | 40.5 | 56.6 | 23.3 | L2-bound |
| DBP3072 (3072) | RSQ8 | 42.8 | 88.3 | 44.7 | 62.1 | 27.9 | L2-bound |
| DBP3072 (3072) | TQ4 | 43.0 | 86.8 | 44.0 | 62.0 | 27.9 | L2-bound |
| DBP3072 (3072) | FP16 | 28.6 | 96.1 | 38.2 | 55.8 | 23.2 | L2-bound |
| DBP3072 (3072) | TF32 | 25.9 | 97.2 | 40.0 | 56.4 | 23.3 | L2-bound |
| DEEP (96) | RSQ8 | 49.1 | 28.6 | 0.9 | 28.5 | 27.7 | occupancy |
| DEEP (96) | TQ4 | 49.1 | 28.6 | 0.9 | 28.6 | 27.7 | occupancy |
| DEEP (96) | FP16 | 39.2 | 17.9 | 1.0 | 17.9 | 23.1 | occupancy |
| DEEP (96) | TF32 | 40.2 | 28.4 | 1.6 | 22.9 | 23.2 | occupancy |
Table 11. Score-family kernels (top-leader , sub-leader ) speed-of-light across the four build precisions (single H100, GPiPNN; columns as in Tab. 9). Both track the leaf: L2-bound at and under the wider fp16/tf32 operands, latency/occupancy-bound otherwise.
The edge-hash kernel is firmly SM-bound (87–89% of SM throughput at ≈ 95% occupancy): each warp folds a 32-lane SimHash off the operand load it already performs, with no operand re-streaming.
The direct-edge prune is SM-bound (68–76%) and precision- and dimension-invariant: because it reuses stored direct-edge witnesses instead of recomputing candidate distances, its utilization is identical across RSQ8/TQ4/FP16/TF32 (Tab. 12) and its share of the build shrinks as grows (23.7% at down to 3.9% at , as the -dependent score and hash kernels grow around it).
The unquantized fp16/tf32 paths push the score-family kernels deeper into the L2 (wider operands, ≈ 98% unified memory throughput) but leave the SM-bound edge-hash and prune essentially unchanged.
Build component breakdown
Figure 8 breaks the native GPU build time down by component on the four ablation datasets, both by pipeline stage and by kernel (RSQ8, —the same configuration as Tab. 8). The dominant component shifts with dimension: at (deep) the direct-edge prune (24%) and the sub-leader scan (20%) are the largest kernels; at (dbpedia) the leaf score (25%) and edge-hash (25%) take over while the prune falls to 4%. The leaf–other and cluster–other slices collect the per-stage remainder—gather, sort, merge, emit, and the top-leader assignment—after subtracting the named sub-timers; because the leaf runs two overlapped streams these are stage wall time minus the measured sub-timers, not separately profiled kernels.
HashPrune sketch construction
HashPrune on GPiPNN (Sec. 5.5) sketches each edge by folding the per-coordinate sign of the residual into a 12-bit SimHash,
the reverse sketch rides the same operand load, packed into the other half of a 32-bit word.2 One warp takes one edge and its 32 lanes coalesce the contraction-axis loads. The emit kernel writes a fixed forward and reverse candidate record for each witnessed edge. The sort key is , and the payload stores the target id together with the 12-bit sketch. Thus each owner row sees candidates in distance order before the deterministic merge applies duplicate-target and same-sketch rules. Because the emit buffer holds only the current batch’s records, its size is bounded by the per-batch slab cap and does not scale with the graph.
Direct KNN-graph mode and build-time scaling
We also use the same pipeline to build direct KNN graphs. In KNN mode we set the leaf top- and accumulator capacity to the requested , disable same-sketch HashPrune filtering, and deduplicate only repeated target ids, keeping the nearer copy. We then skip the final prune and export the canonicalized accumulator as a directed graph; this avoids the build-then-search pattern that graph-index baselines use for KNN construction (Table 3 and 5).
For harder KNN cells we run several rounds. Round 0 creates the permuted row space; later rounds resample the top-level partition with new seeds but keep the row order fixed, so their witnesses merge into the same accumulator and export through the same id map, changing the candidate set without creating incompatible row spaces. We plan the remaining scaling choices before allocation: a memory planner chooses how many top-level bucket ranges to stream and bounds the leaf and accumulation buffers, keeping output-neutral choices (such as the number of streamed ranges) separate from quality-coupled ones (such as candidate capacity). The full build-time tables are in Table 4 and 6.
GPU Build Parameter Configurations
This section reports the exact per-(method, dataset) build parameters behind the GPU build-time results (Table 3 to 5), how they were selected, and the software and hardware environment. All runs were driven by a single comparison harness that builds each method from source and records the invocation. GPiPNN here is the H100 port; its four modes—TQ4, RSQ8, FP16, and TF32 (CLI --tq 4, --tq 8, and --unquant fp16|tf32)—change only the score-kernel precision, so the graph-topology parameters in Table 13 and 14 are shared across all four modes.
Tuning protocol
For each (method, dataset) pair we ran a parameter sweep and kept a single configuration. For the ANNS index we kept the fastest build whose index is high-quality—its QPS-versus-recall curve comparable to an unquantized ParlayANN-Vamana graph (Sec. 6)—scored by the area under that curve. For the -NN graph we kept the fastest build reaching graph-fidelity recall (sampling 5,000 seeded points against the brute-force top-10); a “−” in Table 5 marks a method×dataset cell where no swept configuration cleared the floor. The swept space were: GPiPNN , leaf size , prune degree and prune-candidate cap , and for -NN, leaders and fanout; JASPER (same grid), use_rabbitq, use_reorder; CAGRA graph degree and intermediate degree . Methods otherwise run at library defaults. The default is distance-aware (0.9 for MIPS, 1.1 for L2) for both GPiPNN and JASPER; RabiTQ was not used during queries for any method.
ANNS-index build parameters
GPiPNN always builds with GPU HashPrune and the direct-edge final prune, both enabled by default. Table 13 lists the tuned parameters per dataset: GPiPNN angular slack , prune degree , and leaf size (prune-candidate cap , reduced to 32 at 100M to fit the accumulators); JASPER degree , , and reorder flag (, throughout, 0.004 at 100M to avoid an illegal access at nodes); and CAGRA graph / intermediate degree. Unquantized CAGRA and CAGRA-FP16 build the initial graph with NN-Descent (L2 only) and therefore do not run on the MIPS sets (Wiki-all, MS-MARCO, MSMARCO-Artic, Wiki-Cohere, Text2Image) except for Wiki-Qwen-500K, which is L2-normalized; only CAGRA-PQ4/PQ8 (IVF-PQ path) do, sharing the listed degrees and differing only in PQ bit-width. On the L2 DataCompDr-10M set the unquantized
| Dataset () | mode | SM% | Mem% | DRAM% | L1% | Occ% | regime |
| edge-hash | |||||||
| WikiAll-10M (768) | RSQ8 | 87.1 | 31.1 | 6.0 | 31.1 | 93.9 | SM-bound |
| WikiAll-10M (768) | TQ4 | 87.1 | 31.1 | 6.2 | 31.1 | 93.8 | SM-bound |
| WikiAll-10M (768) | FP16 | 75.4 | 33.6 | 15.6 | 33.6 | 93.0 | SM-bound |
| WikiAll-10M (768) | TF32 | 78.4 | 50.6 | 37.3 | 35.0 | 92.4 | SM-bound |
| OpenAI (1536) | RSQ8 | 88.5 | 29.3 | 5.4 | 29.3 | 94.9 | SM-bound |
| OpenAI (1536) | TQ4 | 88.5 | 29.3 | 5.4 | 29.3 | 95.0 | SM-bound |
| OpenAI (1536) | FP16 | 78.8 | 36.2 | 15.3 | 32.0 | 94.5 | SM-bound |
| OpenAI (1536) | TF32 | 82.4 | 57.9 | 39.0 | 33.5 | 94.1 | SM-bound |
| DBP3072 (3072) | RSQ8 | 89.2 | 28.4 | 4.4 | 28.3 | 95.6 | SM-bound |
| DBP3072 (3072) | TQ4 | 89.2 | 28.2 | 4.4 | 28.3 | 95.7 | SM-bound |
| DBP3072 (3072) | FP16 | 80.8 | 37.2 | 14.8 | 31.2 | 95.3 | SM-bound |
| DBP3072 (3072) | TF32 | 84.2 | 62.0 | 41.0 | 32.5 | 95.2 | SM-bound |
| DEEP (96) | RSQ8 | 78.9 | 41.8 | 3.6 | 41.8 | 86.9 | SM-bound |
| DEEP (96) | TQ4 | 78.8 | 41.8 | 3.6 | 41.8 | 87.0 | SM-bound |
| DEEP (96) | FP16 | 71.8 | 41.6 | 5.4 | 41.6 | 85.6 | SM-bound |
| DEEP (96) | TF32 | 70.7 | 41.3 | 11.0 | 41.3 | 85.3 | SM-bound |
| direct-edge prune | |||||||
| WikiAll-10M (768) | RSQ8 | 67.9 | 21.1 | 3.2 | 21.1 | 53.6 | SM-bound |
| WikiAll-10M (768) | TQ4 | 67.9 | 21.1 | 3.2 | 21.1 | 53.7 | SM-bound |
| WikiAll-10M (768) | FP16 | 67.9 | 21.1 | 3.2 | 21.1 | 53.6 | SM-bound |
| WikiAll-10M (768) | TF32 | 67.8 | 21.1 | 3.2 | 21.1 | 53.6 | SM-bound |
| OpenAI (1536) | RSQ8 | 69.9 | 22.1 | 3.0 | 22.1 | 55.5 | SM-bound |
| OpenAI (1536) | TQ4 | 70.2 | 22.1 | 3.0 | 22.1 | 55.7 | SM-bound |
| OpenAI (1536) | FP16 | 70.0 | 22.1 | 3.0 | 22.1 | 55.5 | SM-bound |
| OpenAI (1536) | TF32 | 70.0 | 22.1 | 3.0 | 22.1 | 55.5 | SM-bound |
| DBP3072 (3072) | RSQ8 | 73.9 | 24.1 | 3.9 | 24.2 | 60.5 | SM-bound |
| DBP3072 (3072) | TQ4 | 74.0 | 24.1 | 3.9 | 24.2 | 60.5 | SM-bound |
| DBP3072 (3072) | FP16 | 73.9 | 24.1 | 3.9 | 24.2 | 60.5 | SM-bound |
| DBP3072 (3072) | TF32 | 73.9 | 24.1 | 3.9 | 24.2 | 60.5 | SM-bound |
| DEEP (96) | RSQ8 | 76.1 | 22.4 | 5.3 | 22.4 | 65.4 | SM-bound |
| DEEP (96) | TQ4 | 76.3 | 22.4 | 5.4 | 22.5 | 65.8 | SM-bound |
| DEEP (96) | FP16 | 76.2 | 22.4 | 5.3 | 22.4 | 65.4 | SM-bound |
| DEEP (96) | TF32 | 76.2 | 22.4 | 5.2 | 22.4 | 65.4 | SM-bound |
Table 12. Support kernels (edge-hash, direct-edge prune) speed-of-light across the four build precisions. Both are SM-bound; the prune is precision-invariant because it reuses stored witnesses rather than reloading operands.
CAGRA build did not complete. GPiPNN-TF32 exceeds the 80 GB budget at 100M, and both GPiPNN-FP16 and TF32 exceed it on DataCompDr-10M ().
-NN-graph build parameters
Tab. 14 lists the -NN build parameters (). GPiPNN (published as RSQ8) is set by leaders, leaf size , fanout (, ), and rounds. TQ4 is too lossy to reach the recall floor on DEEP-10M, MS-Turing-10M, MS-MARCO-10M, Wiki-Cohere-10M, and Text2Image-10M. For some datasets it requires significantly higher fanout than RSQ8 and is thus slower. FP16/TF32 exceed the 80 GB budget on DataCompDr-10M. JASPER uses , , , RaBitQ and reorder off, with and beam size as shown. NN-Descent (and its FP16 variant) is set by intermediate degree / iterations; IVF-PQ8 by probe count (list count and PQ dimension auto); cuVS CAGRA uses graph / intermediate degree 32/128 on every dataset. At 100M (DEEP, MS-Turing; not in Tab. 5) GPiPNN scales leaders to 4096, with leaf 2048/4096 and fanout (8, 8)/(8, 10) respectively.
Software and hardware
Tab. 15 gives the full version manifest abbreviated in Sec. 6. GPiPNN is compiled for Hopper SM90a with fused multiply-add disabled
(-fmad=false device, -ffp-contract=off host) for deterministic builds. All builds run on a single H100, device-resident where the dataset fits the 80 GB budget; the DEEP-100M CAGRA outlier (Tab. 4) stems from the cuVS 25.04 large-scale host-input build path.
CPU Build Parameter Configurations
This section reports the per-(method, dataset) build parameters behind the CPU results: the build times in Sec. 6.1 and the QPS-vs-recall curves in Figure 10. PiPNN appears in three modes (TQ4, RSQ8, and FP32) that differ only in build precision. They share the build parameters below, so its columns cover all three, but the differing precision yields different graphs; all three are queried identically. For the ANNS index we fixed the graph degree and build beam and tuned the slack per dataset (Sec. G.1). For the -NN graph we swept the per-method knobs of Tab. 17 and kept the fastest build reaching recall .
ANNS-index build parameters
Tab. 16 lists the tuned parameters per dataset. The parameter is the only knob that was varied for both methods, as it directly controls the density of the produced graph.
Tuning . For each dataset we set PiPNN’s so that its graph’s average degree falls within of the Vamana’s average degree. We note that varying does not meaningfully change the construction time for PiPNN II, and this tuning was done to produce an apples-to-apples comparison between the quality of the graphs produced by the two methods (Fig. 10).
-NN-graph build parameters
Tab. 17 lists the retained -NN configuration per method: the fastest swept build reaching recall . PyNNDescent is omitted on MS-MARCO, DEEP, MS-Turing, and Text2Image since it runs out of memory.
| Dataset | GPiPNN (all modes) leaders | GPiPNN (all modes) | GPiPNN (all modes) | GPiPNN (all modes) rounds | Jasper | Jasper beam | NN-Descent deg./iter. | IVF-PQ8 |
| DEEP-10M | 512 | 1024 | (8,4) | 1 | 0.95 | 64 | 64/15 | 32 |
| MS-Turing-10M | 512 | 4096 | (8,10) | 1 | 1.05 | 64 | 48/15 | 64 |
| DBpedia-1536 | 512 | 512 | (8,8) | 1 | 0.95 | 128 | 48/20 | 32 |
| DBpedia-3072 | 512 | 512 | (8,8) | 1 | 0.95 | 128 | 48/30 | 32 |
| Wiki-Qwen-500K | 512 | 512 | (8,10) | 1 | 0.95 | 128 | 48/30 | 32 |
| OpenAI-2M | 512 | 512 | (8,4) | 1 | 0.95 | 128 | 48/15 | 32 |
| Wiki-all-1M | 512 | 2048 | (8,10) | 1 | 1.0 | 64 | 48/15 | 32 |
| Wiki-all-10M | 512 | 2048 | (8,4) | 1 | 0.95 | 64 | 48/15 | 64 |
| MS-MARCO-10M | 512 | 2048 | (8,4) | 4 | 0.9 | 128 | 48/15 | 64 |
| DataCompDr-10M | 512 | 4096 | (8,4) | 1 | 1.05 | 128 | – | – |
| Wiki-Cohere-10M | 512 | 2048 | (8,4) | 4 | 0.95 | 128 | 48/20 | 128 |
| Text2Image-10M | 512 | 1024 | (8,4) | 1 | 0.9 | 64 | 48/20 | – |
| MS-Arctic-1M | 512 | 4096 | (8,4) | 1 | 0.9 | 512 | 48/20 | 32 |
Table 14. Per-dataset -NN-graph build parameters (cf. Table 5). Values are the swept configuration retained per method; “–” in Tab. 5 marks cells where no configuration reached recall . deg./iter.: NN-Descent intermediate degree / iterations.
| Component | Version |
| GPU | NVIDIA H100 80 GB HBM3 SXM5 (cc 9.0) |
| Host / instance | GCP a3-highgpu-1g, 26-vCPU Sapphire Rapids, 234 GB DDR5 |
| GPU driver | 580.126.09 |
| CUDA toolkit | 12.9 (compiled sm_80/89/90; run as SM90a) |
| OS | Ubuntu 24.04.4 LTS |
| GPiPNN libs | CuTe/CUTLASS 3.7.0, RaBitQ, Eigen 3.4.0, Abseil 20250512.0, mimalloc 2.2.2 |
| Compiler | gcc/g++ 13, C++17, CMake |
| Jasper | git 1f03773 (CUDA , cc ) |
| cuVS / RAFT / RMM | 25.04 (cuvs-bench 25.04, Python 3.12) |
| Harness | Python 3.10, NumPy |
Table 15. Software and hardware environment for the GPU experiments.
| Dataset | fanout | |||||
| Wiki-Qwen-500K | (10,1) | 2 | 16 | 225 | 40 | 5 |
| DBP1536 | (10,1) | 2 | 32 | 12 | 40 | 5 |
| DBP3072 | (10,1) | 3 | 16 | 500 | 40 | 5 |
| OpenAI | (10,1) | 2 | 16 | 160 | 40 | 5 |
| DataComp | (10,2,1) | 2 | 32 | 120 | 40 | 5 |
| WikiCohere | (10,3,1) | 3 | 64 | 500 | 40 | 5 |
| WikiAll | (10,3,1) | 3 | 32 | 300 | 40 | 5 |
| MSMARCO | (10,3,1) | 5 | 64 | 160 | – | – |
| MS-Arctic | (10,2,1) | 1 | 32 | 34 | 40 | 5 |
| DEEP | (10,3,1) | 3 | 64 | 30 | – | – |
| MS-Turing | (10,3,1) | 2 | 32 | 140 | – | – |
| Text2Image | (10,2,1) | 2 | 32 | 200 | – | – |
Table 17. Per-dataset CPU -NN-graph build parameters: the fastest swept configuration reaching recall (the configurations timed in the right half of § 8). PiPNN is set by its leaf fanout scheme and cluster count at fixed leaf size , per-leaf top-10, heap size , and TQ8 scoring. Vamana sweeps (build beam ) and is read out at query beam , with SQ8 or JL+SQ8 as in Table 16. PyNNDescent runs one fixed configuration (, , leaf 100, , SQ8). “–” marks where PyNNDescent exceeded memory (MSMARCO and the billion-scale sets).
| Dataset | quant. | ||||||
| Wiki-Qwen-500K | 0.75 | 64 | 1024 | 64 | 128 | 1.0 | JL+SQ8 |
| DBP1536 | 1.25 | 64 | 1024 | 64 | 128 | 1.0 | JL+SQ8 |
| DBP3072 | 1.25 | 64 | 1024 | 64 | 128 | 1.0 | JL+SQ8 |
| OpenAI | 1.25 | 64 | 1024 | 64 | 128 | 1.04 | JL+SQ8 |
| DataComp | 1.25 | 64 | 1024 | 64 | 128 | 1.1 | JL+SQ8 |
| WikiCohere | 0.98 | 64 | 1024 | 64 | 128 | 0.99 | JL+SQ8 |
| WikiAll | 0.9 | 64 | 1024 | 64 | 128 | 0.93 | JL+SQ8 |
| MSMARCO | 0.985 | 64 | 1024 | 64 | 128 | 1.0 | JL+SQ8 |
| MS-Arctic | 0.95 | 64 | 1024 | 64 | 128 | 0.95 | JL+SQ8 |
| DEEP | 1.15 | 64 | 1024 | 64 | 128 | 1.025 | SQ8 |
| MS-Turing | 1.07 | 64 | 1024 | 64 | 128 | 1.01 | SQ8 |
| Text2Image | 0.95 | 64 | 1024 | 64 | 128 | 1.0 | SQ8 |
Table 16. Per-dataset CPU ANNS-index build parameters (cf. § 8 and Figure 10). : graph degree; : PiPNN leaf/cluster size; : Vamana build beam. PiPNN runs a single cluster tree () with LSH table size (dropped to 64 on the billion-scale sets in FP32 mode to fit memory); its TQ4, RSQ8, and FP32 modes differ only in build precision and so produce different graphs from these shared parameters, all queried identically. Vamana quant.: SQ8 is 8-bit scalar quantization, JL+SQ8 adds a Johnson-Lindenstrauss filter; the unquantized VF32 baseline uses the same , , and .
References
- [1]Andrej Androni and Hengjie Zhang. 2023. Sub-quadratic (1+ε)-approximate Euclidean Spanners, with Applications. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 98–112.
- [2]Apple. 2024. DataCompDR-12M-bf16. https://huggingface.co/datasets/apple/DataCompDR-12M-bf16.
- [3]Amir Azarmehr, Soheil Behnezhad, Rajesh Jayaram, Jakub Łącki, Vahab Mirrokni, and Peilin Zhong. 2025. Massively parallel minimum spanning tree in general metric spaces. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 143–174.arxiv.org/abs/2408.06455
- [4]Artem Babenkо and Victor Lempitsky. 2015. Efficient indexing of billion-scale datasets of deep descriptors. In Proceedings of the IEEE conference on computer vision and pattern recognition. 2055–2063.DOI
- [5]MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajaghayi, Raimondas Kiveris, Silvio Lattanzi, and Vahab Mirrokni. 2017. Affinity clustering: Hierarchical clustering at scale. Advances in Neural Information Processing Systems 30 (2017).
- [6]Ran Ben-Basat, Yaniv Ben-Itzhak, Gal Mendelson, Michael Mitzenmacher, Amit Protopopov, and Shay Vargaftik. 2026. A Note on TurboQuant and the Earlier DRIVE/EDEN Line of Work. arXiv preprint arXiv:2604.18555 (2026).arxiv.org/abs/2604.18555
- [7]Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram, and Erik Waingarten. 2025. Approximating High-Dimensional Earth Mover’s Distance as Fast as Closest Pair. arXiv preprint arXiv:2508.06774 (2025).arxiv.org/abs/2508.06774
- [8]CJ Carey, Jonathan Halcrow, Rajesh Jayaram, Vahab Mirrokni, Warren Schudy, and Peilin Zhong. 2022. Stars: Tera-Scale Graph Building for Clustering and Learning. Advances in Neural Information Processing Systems 35 (2022), 21470–21481.
- [9]Moses Charikar. 2002. Similarity estimation techniques from rounding algorithms. In Proceedings of 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada. ACM, 380–388.
- [10]Patrick H. Chen, Wei-Cheng Chang, Jyunn-Yi Jiang, Hsiang-Fu Yu, Inderjit S. Dhillon, and Cho-Jui Hsieh. 2023. FINGER: Fast inference for graph-based approximate nearest neighbor search. In Proceedings of the ACM Web Conference (WWW). 3225–3235. https://doi.org/10.1145/3543507.3538318
- [11]Nick Craswell, Bhaskar Mitra, Emine Yilmaz, Daniel Campos, and Ellen M. Voorhees. 2021. Overview of the TREC 2020 Deep Learning Track. In TREC.
- [12]Laxman Dhulipala, Jakub Łącki, Jason Lee, and Vahab Mirrokni. 2023. Terahash: Hierarchical agglomerative clustering of trillion-edge graphs. Proceedings of the ACM on Management of Data 1, 3 (2023), 1–27.arxiv.org/abs/2308.03578
- [13]Wei Dong, Moses Charikar, and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th International Conference on World Wide Web (WWW). 577–586. https://doi.org/10.1145/1963405.1963487
- [14]Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazare, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2024. The Faiss library. (2024). arXiv:2401.08281 [cs.LG]arxiv.org/abs/2401.08281
- [15]Cong Fu and Deng Cai. 2016. EFANNA: An extremely fast approximate nearest neighbor search algorithm based on kNN graph. arXiv preprint arXiv:1609.07228 (2016).arxiv.org/abs/1609.07228
- [16]Cong Fu, Changxu Wang, and Deng Cai. 2021. High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility. IEEE Transactions on Pattern Analysis and Machine Intelligence 44, 8 (2021), 4139–4150.DOI
- [17]Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph. Proceedings of the VLDB Endowment 12, 5 (2019), 461–474. https://doi.org/10.14778/3303753.3303754
- [18]Jianyang Gao, Yutong Gou, Yuexuan Xu, Jifan Shi, Zhonghao Yang, and Cheng Long. 2025. The RaBitQ Library. In The 1st Workshop on Vector Databases (VecDB), co-located with ICML 2025. https://openreview.net/forum?id=OeZHhOsFir
- [19]Jianyang Gao, Yutong Gou, Yuexuan Xu, Yongyi Yang, Cheng Long, and Raymond Chi-Wing Wong. 2025. Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search. In Proceedings of the ACM on Management of Data (SIGMOD).arxiv.org/abs/2409.09913
- [20]Jianyang Gao and Cheng Long. 2023. High-dimensional approximate nearest neighbor search with reliable and efficient distance comparison operations. Proceedings of the ACM on Management of Data (PACMMOD) 1, 2, Article 137 (2023), 27 pages. https://doi.org/10.1145/3589282
- [21]Jianyang Gao and Cheng Long. 2024. RaBitQ: Quantizing high-dimensional vectors with a theoretical error bound for approximate nearest neighbor search. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–27.arxiv.org/abs/2405.12497
- [22]Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jilin Liu, Pan Yu, Yixin Dai, Jiawei Sun, Haofen Wang, and Haofen Wang. 2023. Retrieval-augmented generation for large language models: A survey. arXiv preprint arXiv:2312.10997 (2023).arxiv.org/abs/2312.10997
- [23]Thijs Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized product quantization. IEEE transactions on pattern analysis and machine intelligence 36, 4 (2013), 744–755.
- [24]Google. 2026. Highway: Performance-portable SIMD. https://github.com/google/highway
- [25]Lars Gottśbüren, Laxman Dhulipala, Rajesh Jayaram, and Jakub Łącki. 2025. Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search. Proc. VLDB Endow. 18, 6 (2025), 1649–1662.arxiv.org/abs/2403.01797
- [26]Yutong Gou, Jianyang Gao, Yuexuan Xu, and Cheng Long. 2025. SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search. In Proceedings of the ACM on Management of Data (SIGMOD).arxiv.org/abs/2411.12229
- [27]Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating Large-Scale Inference with Anisotropic Vector Quantization. In International Conference on Machine Learning. https://arxiv.org/abs/1908.10396
- [28]Ben Harwood and Tom Drummond. 2016. FANNG: Fast approximate nearest neighbour graphs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 5713–5722.DOI
- [29]Masajiro Iwasaki and Daisuke Miyazaki. 2018. Optimization of indexing based k-nearest neighbor graph for proximity search in high-dimensional data. arXiv preprint arXiv:1810.07355 (2018).arxiv.org/abs/1810.07355
- [30]Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. Diskann: Fast accurate billion-point nearest neighbor search on a single node. Advances in neural information processing systems 32 (2019).
- [31]Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 33, 1 (2010), 117–128.DOI
- [32]Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data 7, 3 (2019), 535–547.arxiv.org/abs/1702.08734
- [33]William B. Johnson and Joram Lindenstrauss. 1984. Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics 26 (1984), 189–206.
- [34]Saim Khan, Somesh Singh, Harsha Vardhan Simhadri, Jyothi Vedurada, et al. 2024. Bang: Billion-scale approximate nearest neighbor search using a single gpu. arXiv preprint arXiv:2401.11324 (2024).arxiv.org/abs/2401.11324
- [35]Ravishankar Krishnaswamy, Magdalen Dobson Manohar, and Harsha Vardhan Simhadri. 2024. The DiskANN library: Graph-Based Indices for Fast, Fresh and Filtered Vector Search. IEEE Data Eng. Bull. (2024).
- [36]Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020. Retrieval-augmented generation for knowledge-intensive nlp tasks. Advances in Neural Information Processing Systems 33 (2020), 9459–9474.arxiv.org/abs/2005.11401
- [37]Yuliang Li, Jinfeng Li, Yoshihiko Suhara, AnHai Doan, and Wang-Chiew Tan. 2020. Deep entity matching with pre-trained language models. Proc. VLDB Endow. 14, 1 (2020), 50–60.DOI
- [38]Maknee. 2024. wikipedia_qwen_8b. https://huggingface.co/datasets/maknee/wikipedia_qwen_8b.
- [39]Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. 2014. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems 45 (2014), 61–68.DOI
- [40]Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence 42, 4 (2018), 824–836.DOI
- [41]Magdalen Dobson Manohar, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2024. Parlayann: Scalable and deterministic parallel graph-based approximate nearest neighbor search algorithms. In Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming. 270–285.arxiv.org/abs/2305.04359
- [42]Hunter McCoy, Zikun Wang, and Prashant Pandey. 2026. Jasper: ANNS Quantized for Speed, Built for Change on GPU. arXiv preprint arXiv:2601.07048 (2026).arxiv.org/abs/2601.07048
- [43]Leland McInnes. 2020. PyNNDescent for Fast Approximate Nearest Neighbors. Webpage. Retrieved December 15, 2022 from https://pynndescent.readthedocs.io/en/latest/
- [44]Luke Merrick, Danmei Xu, Gaurav Nuti, and Daniel Campos. 2024. Arctic-Embed: Scalable, Efficient, and Accurate Text Embedding Models. (2024). arXiv:2405.05374arxiv.org/abs/2405.05374
- [45]Bhasakar Mitra, Nick Craswell, et al. 2018. An introduction to neural information retrieval. Foundations and Trends® in Information Retrieval 13, 1 (2018), 1–126.
- [46]Javier Vargas Munoz, Marcos A Gonçalves, Zanoni Dias, and Ricardo da S Torres. 2019. Hierarchical clustering-based graphs for large scale approximate nearest neighbor search. Pattern Recognition 96 (2019), 106970.DOI
- [47]Arvind Neelakantan, Tao Xu, Raul Parel, Alec Radford, Jesse Michael Han, Jerry Tworek, Qiming Yuan, Nikolas Tezak, Jong Wook Kim, Chris H alacy, et al. 2022. Test and code embeddings by contrastive pre-training. arXiv preprint arXiv:2201.10005 (2022).arxiv.org/abs/2201.10005
- [48]NVIDIA RAPIDS. 2024. cuVS: GPU-accelerated Vector Search and Clustering. https://github.com/rapidsai/cuvs.
- [49]NVIDIA RAPIDS. 2024. wiki-all: a vector-search benchmark dataset. https://data.rapids.ai/raft/datasets/.
- [50]Hiroyuki Ootomo, Akira Naruse, Corey Nolet, Ray Wang, Tamas Feher, and Yong Wang. 2024. Cagra: Highly parallel graph construction and approximate nearest neighbor search for gpus. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 4236–4247.arxiv.org/abs/2308.15136
- [51]ParlayANN contributors. 2024. ParlayANN: A library of algorithms for approximate nearest neighbor search. https://github.com/cmuparlay/ParlayANN.
- [52]Qdrant. 2024. dbpedia-entities-openai3-text-embedding-3-large-1536-1M. https://huggingface.co/datasets/Qdrant/dbpedia-entities-openai3-text-embedding-3-large-1536-1M.
- [53]Qdrant. 2024. dbpedia-entities-openai3-text-embedding-3-large-3072-1M. https://huggingface.co/datasets/Qdrant/dbpedia-entities-openai3-text-embedding-3-large-3072-1M.
- [54]Nils Reimers. 2022. Cohere/wikipedia-22-12-en-embeddings. https://huggingface.co/datasets/Cohere/wikipedia-22-12-en-embeddings.
- [55]Deepjyoti Roy and Mala Dutta. 2022. A systematic review and research perspective on recommender systems. Journal of Big Data 9, 1 (2022), 59.DOI
- [56]Tobias Rubel, Richard Wen, Laxman Dhulipala, Lars Gottsebüren, Rajesh Jayaram, and Jakub Łącki. 2026. PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing. arXiv preprint arXiv:2602.21247 (2026).arxiv.org/abs/2602.21247
- [57]Harsha Vardhan Simhadri, Martin Aumüller, Amir Ingber, Matthijs Douze, George Williams, Magdalen Dobson Manohar, Dmitry Baranchuk, Edo Liberty, Frank Liu, Ben Landrum, et al. 2024. Results of the Big ANN: NeurIPS’23 competition. arXiv preprint arXiv:2409.17424 (2024).arxiv.org/abs/2409.17424
- [58]Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamy, Gopal Srinivasa, et al. 2022. Results of the NeurIPS’21 challenge on billion-scale approximate nearest neighbor search. In NeurIPS 2021 Competitions and Demonstrations Track. PMLR, 177–189.arxiv.org/abs/2205.03763
- [59]Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. 2021. Freshdiskann: A fast and accurate graph-based ann index for streaming similarity search. arXiv preprint arXiv:2105.09613 (2021).arxiv.org/abs/2105.09613
- [60]Jack Spalding-Jamieson, Eliot Wong Robson, and Da Wei Zheng. 2025. Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search. arXiv preprint arXiv:2502.06163 (2025).arxiv.org/abs/2502.06163
- [61]Philip Sun, David Simcha, Dave Dopson, Ruiqi Guo, and Sanjiv Kumar. 2023. SOAR: Improved Indexing for Approximate Nearest Neighbor Search. In Neural Information Processing Systems. https://arxiv.org/abs/2404.00774
- [62]Shay Vargaftik, Ran Ben-Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben-Itzhak, and Michael Mitzenmacher. 2021. DRIVE: Onе-bit distributed mean estimation. In Advances in Neural Information Processing Systems (NeurIPS).
- [63]Shay Vargaftik, Ran Ben-Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben-Itzhak, and Michael Mitzenmacher. 2022. EDEN: Communication-efficient and robust distributed mean estimation for federated learning. In International Conference on Machine Learning (ICML).arxiv.org/abs/2108.08842
- [64]Sairaj Voruganti and M. Tamer Özsu. 2025. MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 3, Article 188 (June 2025), 27 pages. https://doi.org/10.1145/3725325
- [65]Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul N. Bennett, Junaid Ahmed, and Arnold Overwijk. 2021. Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval. In International Conference on Learning Representations, ICLR.
- [66]Shuo Yang, Jiadong Xie, Yingfan Liu, Jeffrey Xu Yu, Xiyue Gao, Qianru Wang, Yanguo Peng, and Jiagtao Cui. 2024. Revisiting the index construction of proximity graph-based approximate nearest neighbor search. arXiv preprint arXiv:2410.01231 (2024).arxiv.org/abs/2410.01231
- [67]Shangdi Yu, Joshua Engels, Yihao Huang, and Julian Shun. 2025. Pecann: Parallel efficient clustering with graph-based approximate nearest neighbor search. In 2025 Proceedings of the Conference on Applied and Computational Discrete Algorithms (ACDA). SIAM, 1–17.
- [68]Amir Zandieh, Majid Daliri, Majid Hadian, and Vahab Mirrokni. 2025. Turboquant: Online vector quantization with near-optimal distortion rate. arXiv preprint arXiv:2504.19874 (2025).arxiv.org/abs/2504.19874
- [69]Alexandros Zeakis, George Papadakis, Dimitrios Skoutas, and Manolis Koubarakis. 2023. Pre-Trained Embeddings for Entity Resolution: An Experimental Analysis. Proc. VLDB Endow. 16, 9 (2023), 2225–2238.DOI
- [70]Xi Zhao, Yao Tian, Kai Huang, Bolong Zheng, and Xiaofang Zhou. 2023. Towards efficient index construction and approximate nearest neighbor search in high-dimensional spaces. Proceedings of the VLDB Endowment 16, 8 (2023), 1979–1991.DOI






