Building Navigable Graphs Without Search in Three Composable Stages

1. Introduction

• On PiPNN’s candidate pool, the proposed ending uses 3–14% fewer distance evaluations than PiPNN’s ending at equal recall, for 8–16% more build time.The ending combines a bounded heap, occlusion pruning with per-corpus slack, and prune-then-symmetrize ordering.Source: §1 · pp. 2–3
• Search-based builders’ dependent random-access distance evaluations can underuse dense arithmetic, while prior work had not separated which construction decisions set graph quality.The paper fixes candidate pairs before evaluating them and separates the pool, ending, and spine into stages.Source: §1 · pp. 2–3
• On GIST, every tested pool is within 4% of the exact-kNN ceiling, while local kNN-graph clustering predicts which pairs block covers miss.The zero-clustering fraction orders corpora by difficulty, grows with n, and is within 4% of an oracle’s membership allocation when memberships are uniform.Source: §1 · p. 3
• The half-space-proximal spine routes monotonically to every sampled point and replaces a spanning tree at 1/10–1/500 of its distance-evaluation cost.It uses edges over a random sample and is exempt from the prune.Source: §1 · pp. 2–3
• On six corpora at k = 10 and k = 100, the composed build matches or beats a full dense construction in 0.51–0.86× its build time.The configuration uses PiPNN’s partition with the proposed ending and spine.Source: §1 · pp. 2–3

2.1. Three stages

• The three stages are a possibly overlapping block pool, an ending that prunes candidate lists and appends reverse edges, and a spine that guarantees reachability.The pool evaluates all within-block pairs; the spine is unioned after pruning and is exempt from it.Source: §2.1 · pp. 4–5

2.2. The dense instance and its kernel

• The dense candidate stage evaluates every unordered pair once using a register-tiled symmetric scan scheduled in round-robin tournament order.On the 64-thread Xeon, it reaches 2.36 G pair-evaluations per second, or 53% of the machine’s SGEMM rate.Source: §2.2 · p. 6

2.3. Determinism

• With fixed data, seed, and parameters, the Dense graph is independent of thread count and tile execution order.The proof fixes memberships and heap offers through deterministic ordering, then applies a per-vertex prune and a pure-function HSP spine.Source: §2.3 · p. 6

2.4. Protocol

• The protocol measures d@r as distance evaluations per query needed by ParlayANN’s beam to reach recall r, grading every graph with that same searcher.Pool comparisons use the identical 200-nearest ending; changing that rule previously reversed a shared-neighbor pool comparison on GIST.Source: §2.4 · pp. 6–7

3. The composed build against dense, Vamana, PiPNN and HNSW

• 25%: on GloVe, the composed build with PiPNN’s default 30 leaves trails Dense; at 120 leaves it beats Dense at recall 0.95 and 0.99 in 0.87× its build time.The section attributes the recovery to adding memberships, with GloVe’s heavy zero-clustering tail requiring more of them.Source: §3 · p. 7, Table 3 · p. 9
• 0.51–0.86× the dense build’s time: with 60–120 leaves per point, the composed build matches or beats Dense on all six corpora at k=10 and k=100.Table 1 reports d@0.95 for k=10 and k=100; Table 2 gives build times for those runs.Source: §3 · p. 7, Table 1 · p. 8, Table 2 · p. 8
• On Deep-100M, 60 leaves beat Dense by 2%, 9%, and 2% at recall 0.95, recall 0.99, and k=100, respectively, in 0.52× its time.At 120 leaves, the margins are 6%, 13%, and 6% in 0.60× the dense build’s time; Wikipedia’s 120-leaf build also beats Dense at both k values.Source: §3 · pp. 8–9
• At k=10, the composed build matches or beats Dense on Wikipedia and SIFT in one-quarter to one-fifth of Dense’s time, while GIST is within 4% in 0.29× its time.These build-time comparisons are reported for the composed build on Wikipedia and SIFT and for GIST, respectively.Source: §3 · p. 9

4. The ending

• 8–43%: the ending’s prune–symmetrize order and slack each affect quality on identical candidates, while the complete ending improves PiPNN’s graphs on every measured corpus.Pruning each list before appending reverse edges and re-pruning only overfull lists avoids the reported loss from pruning the union once; slack compensates for candidates a search may have missed.Source: §4 · p. 9, §4.1 · p. 10

4.1. Order and slack

• 8% and 10%: on GloVe, pruning the union once costs that much at recall 0.95 and 0.97, respectively, versus pruning each list first and re-pruning only overfull lists.The reported prune stages take 21.6 seconds versus 10.4 seconds.Source: §4.1 · p. 10

4.2. The ending composes with PiPNN

• 3–14%: on PiPNN’s own pool, some slack setting for the ending beats PiPNN’s ending on every corpus measured.The best slack is pool-dependent: α=1 wins on rich pools, while the best setting on thin pools varies by corpus.Source: §4.2 · pp. 10–11

4.3. A deterministic composed build

• The ending is deterministic, but the composed build is not deterministic with stock PiPNN; the authors identified and removed three sources of nondeterminism behind a flag.The causes include a random-device partition seed, hash-based bucket merging with variable output order, and scheduling-dependent sketch-hash generation.Source: §4.3 · p. 11

5.1. What a spine must guarantee

• On 800 Gaussian clusters, pruning can remove every cross-cluster candidate and leave a disconnected graph with recall 0.002, so connectivity repairs must be added after pruning and exempted from it.More pool does not help in this example because cross-leaf candidates are generated and then pruned.Source: §5.1 · p. 12
• A spine is an edge set added after pruning that makes each target reachable from the entry; it is monotone when greedy routing strictly reduces distance to each target at every step.Construction distance evaluations and added degree are the two costs identified for a spine.Source: §5.1 · p. 12

5.2. Instances

• Leader graphs reach leaf medoids but miss within-leaf cluster disconnections; the SAT reaches all vertices but costs 985 M distances on GloVe and 1,678 M on GIST.The SAT root has out-degree 483 on GloVe and 1,133 on GIST; on GIST it needs 5% more evaluations than no spine at recall 0.95.Source: §5.2 · pp. 12–13, Table 6 · p. 13
• HSP edges are formed by scanning each sampled point’s neighbors in distance order and keeping a point unless an already-kept neighbor is closer to it.The resulting edges route monotonically to every sampled point.Source: §5.2 · p. 13, Figure 2 · p. 14
• The HSP guarantee covers sampled targets, not queries or vertices outside the sample; with 1,000 samples, about 29% of clusters are unhit and recall is 0.531.At 10,000 samples every cluster is hit and recall is 0.993, above the tree’s 0.987; construction costs |S|^2 distance evaluations.Source: §5.2 · p. 13

5.3. The HSP spine in practice

• Uncapped HSP degree grows with sample size, but a cap of 8 or 16 keeps quality within about 1% of no spine through 30k samples; cap 16 retains 0.968 recall at 10k.At cap 8, recall falls to 0.66 at 10k because dropped neighbors break the monotonicity guarantee.Source: §5.3 · p. 14, Table 7 · p. 15, Table 8 · p. 15
• The sample-size rule starts at max(1024, √n) and doubles until fewer than n/10^4 additional vertices become reachable; the selected real-corpus samples range from 1,024 to 3,162.Orphans with no in-edge receive an in-edge from their nearest kept out-neighbor without extra distance evaluations; the HSP–SAT recall gap on GIST remains unexplained.Source: §5.3 · pp. 14–15
• Never more than 1.1% worse than the tree, the HSP spine is 2–5% better on four corpora; on Deep-100M, build time falls from 4:13 to 3:49 hours and peak memory from 327 to 267 GB.With the HSP spine, the construction has no adaptive stage.Source: Table 9 · p. 15, §5.3 · p. 15

6.1. Where the partition is good, the pool is not the lever

• Every GIST pool lands from 4% below to 2% above the exact-kNN ceiling, while GloVe’s k-means pool is 5% worse than its ceiling.On GIST, beyond about 0.8 pool recall the ending cannot use more candidates.Source: Table 10 · p. 16, §6.1 · p. 16

6.2. The cost of a pool is a property of the kNN graph

• Covering the kNN graph with blocks is an edge-clique-cover problem: a true pair is covered when both points share a block, and the cost is the evaluated pairs.The measurements use a symmetric k-means cover with cells of 1,400 and memberships needed for a fraction of true 10-NN pairs.Source: §6.2 · pp. 16–17
• Across corpora, local clustering predicts pair coverage point by point, and the fraction of zero-clustering points orders corpora by difficulty better than mean clustering.On GloVe at m = 2, the least-clustered quarter has 0.32 coverage versus 0.86 for the most-clustered quarter.Source: Table 11 · p. 17, §6.2 · p. 17
• On one corpus, the zero-clustering fraction rises from 1.1% to 8.1% across three decades of n, while memberships needed grow approximately as 0.4 ln L.Full Wikipedia was the most clustered corpus measured, with mean clustering 0.206 and 2.4% of points at zero.Source: Table 12 · p. 17, §6.2 · p. 17
• Nonuniform membership policies save at most 3–4% of pairs on GloVe and nothing on GIST at the uniform-m = 5 budget, with end-to-end results within ±3%.The tested policies use exact clustering as an oracle or build-time proxies; 22% more pairs bought nothing.Source: §6.2 · p. 18
• The proposed lower bound on pair cost as a function of the kNN clustering distribution is a conjecture supported by correlations across six corpora and three n values, not a proof.Source: §6.2 · p. 18

• Search-based indexes use beams to acquire candidates, including HNSW, NSG, Vamana, ParlayANN, and Graft; beam evaluations involve dependent random accesses [7].The paper frames fixed candidate pairs before evaluation as an alternative.Source: §7 · p. 18
• Partition-then-brute-force builders include recursive Lanczos bisection, HCNNG, PiPNN [1], and GPU builders such as CAGRA and FAISS [28].The paper says its contribution is separating construction stages and measuring each, not inventing this construction family.Source: §7 · p. 18
• NN-descent, EFANNA [30], SPTAG, and RNN-Descent refine graphs through batched rounds; Yang et al. discuss candidate acquisition and RNG pruning.Source: §7 · p. 18
• The occlusion rule descends from relative neighborhood graphs, while the paper uses HSP and SAT structures as spines.Quantisers act as lossless filters inside a pool in the reported measurements and do not change its quality.Source: §7 · p. 19

• The kernels require distances that decompose into inner products, limiting the stated construction scope to vector settings.Source: §8 · p. 19
• The clustering findings are correlational across six corpora and three n values, and no graph is built beyond 10^8 points.A localiser over 2 · 10^7 random leaders was run at 10^9, but no graph was built there.Source: §8 · p. 19
• Membership studies use one run per PiPNN configuration except two at 10^8, while stock PiPNN varies by up to ±3%.The deterministic variant removes that variance at about 3% of PiPNN’s build time.Source: §8 · p. 19
• Distance counts are the reported cost metric, but Vamana’s graphs run faster at equal distance counts; hnswlib is evaluated only as a level-0 flat graph.Source: §8 · p. 19
• At 10^8, Dense heaps require 160 GB, PiPNN’s 400-entry reservoir 320 GB, and the deterministic 120-leaf build peaks at 679 GB.Source: §8 · p. 19
• Bitwise determinism is reported across thread counts at 10^6, but at 10^8 two runs differ in 38 of 3.8 · 10^10 candidates and 528 of 4.1 · 10^9 edges.The source of those differences is not identified.Source: §8 · p. 19

9. Conclusion

• The ending is the least costly stage and the one that decides graph quality in a deterministic, search-free construction of three separable stages.The stages are the pool, ending, and spine.Source: §9 · p. 20
• With enough memberships per point, the construction matches or beats a full dense construction at 106 to 108 points, for k = 10 and k = 100, in half to nine tenths of the time.Source: §9 · p. 20
• The half-space-proximal spine over a sample routes monotonically to every sampled point and costs |S|^2 distances.It is defined by the reachability it guarantees, not by a particular construction.Source: §9 · p. 20
• The memberships a corpus needs are tied to the growing tail of its kNN graph where neighbors do not know each other, while uniform spending is as good as targeted spending.The conclusion states that the relevant tail grows with n.Source: §9 · p. 20

Reproducibility

• The construction, patches, scripts, logs, and findings are publicly available in the fg binary and the fgraft-experiments repository.The passage lists the branch and command-line flags for the construction and the PiPNN patch.Source: Reproducibility · p. 20
• Every Dense graph is checked by an adjacency hash and distance count at 1 and 64 threads.Source: Reproducibility · p. 20
• Every graph is graded using ParlayANN’s searcher.Source: Reproducibility · p. 20

Appendix A. The dense kernel

• Four changes account for the candidate stage’s 3.4× improvement, and each ladder step produced a byte-identical GloVe graph.Changes include bit-mask deduplication, vectorized tile reduction, an exact SIMD prefilter, and a symmetric scan with a lock-scheduled tournament order.Source: Appendix A · pp. 20–21, Table A.13 · p. 21
• At d = 960, the tile reaches only 1/7.7 of OpenBLAS at the same dimension, leaving the largest remaining engineering headroom.Eight rows of 960 floats overflow L1, and the implementation does not block over the dimension.Source: Appendix A · p. 21
• With FAISS knn_gpu on a 6 GB laptop card, the GloVe build takes 54.2 s versus Vamana’s 640 s on that laptop, at Vamana parity on its searcher.The GPU k-means path is not bitwise reproducible because its scatter-add accumulates in unspecified order.Source: Appendix A · p. 21
• On GloVe with x = 50, a float query against 2-bit data recovers 0.960 of the true 10-NN in its top 500; inside measured pools, the proxy reaches the exact ceiling within one or two points.The quantized scan would reduce operand size by 16× without changing measured pool quality.Source: Appendix A · pp. 21–22

Appendix B. The spine in full

• On real data, the degree cap removes the spine’s price at every tested sample size; on the clustered set, it removes coverage at 8 but retains it at 16 from |S| = 10k.On GIST, the automatic rule with orphan repair stops at |S| = 2,048 after one doubling; without repair, it runs to its cap.Source: Appendix B · pp. 22–23

Appendix C. Adaptive memberships

• At the uniform m = 5 pair budget, the best two-level membership policy saves 3–4% of pairs on GloVe and nothing on GIST; aggressive policies lose because extra leaves enlarge blocks for every member.The tested policies allocate mhi to the hardest fraction and mlo to the rest; the table reports cover and pair-count comparisons.Source: Appendix C · p. 23, Table C.16 · p. 23

Appendix D. Throughput

• On GIST, Vamana yields 3.3k QPS at 5,281 evaluations versus the dense graph’s 2.1k at 4,268; the authors did not measure the cause.The throughput table reports QPS at recall 0.95 and k = 10.Source: Appendix D · p. 23, Table D.17 · p. 24