Source-linked AI summary
Batched Feedback and the Random-Access Wall in Search-Based Graph Construction
Édgar Chávez
TL;DR
Batch graph construction is deterministic and parallel but slower than incremental construction, and the paper measures where that time goes. It finds that batched feedback reduces distance work, while adaptive random accesses impose a separate wall that search-based builders do not cross.
Problem
Batch construction offers determinism and parallelism but costs more build time, motivating an account of where that time goes.
Source: §1 · p. 2Method
Results
Search-based builders run 20–27× below dense GEMM at d ≈100, while batched feedback uses 0.88× Vamana’s distance work but takes 1.55× its build time.
Source: §1 · pp. 2–3Takeaways & Limitations
The wall binds when distances are black boxes or evaluation order is data-dependent; vector systems cross it by fixing pair sets before evaluation.
Source: §1 · p. 3, §8 · p. 13Reaching dense construction from Graft-like designs requires a new construction with distance-based clustering and a separate adaptive pass for long-range edges, which is outside this paper.
Source: §5.5 · p. 11
Abstract
from arXiv · showhide
Navigable graphs for nearest-neighbor search are built either incrementally, each inserted point searching a graph that mutates as construction proceeds, or in batch over a fixed substrate, which buys determinism and parallelism at a price in build time. We measure that price and find where it comes from. Instrumenting a tuned Vamana and PiPNN and building every system repeatedly in a paired design on one 64-thread machine, we separate build time into work (distance evaluations) and cost per evaluation. Letting the batch builder's substrate mutate in $B$ synchronous blocks recovers the feedback loop of incremental construction while the graph stays a function of (data, seed, parameters, $B$): eight trees with batched feedback match thirty-two frozen trees, and the build does $0.88\times$ Vamana's distance work. Yet it takes $1.55\times$ Vamana's wall-clock, because the mutating substrate costs more per evaluation. Pushing further, we find a wall that no search-based builder crosses. Every one of them, incremental or batched, evaluates distances adaptively, one dependent random access at a time, and runs $20$-$27\times$ below a dense kernel on the same machine at $d \approx 100$, five to six times of it with the data resident in cache. The gap is not a low-dimension artifact: an adaptive evaluation costs $d^{1.04}$ and a blocked one $d^{0.63}$, so the wall grows as $d^{0.4}$ and is twice as high at $d = 960$ as at $d = 128$. PiPNN's order-of-magnitude build advantage is that kernel: it evaluates as many distances per point, but as fixed-in-advance dense blocks. We show the beam cannot be batched after the fact (the useful density of a lockstep block is 2-3%), state the wall as a two-ceiling roofline, and delimit it: it binds whenever the distance is a black box or the evaluation order is data-dependent.
1. Introduction
The introduction separates the cost of frozen-substrate construction into a feedback-related build penalty and an architectural limit on adaptive search. Batched feedback reduces distance work, but search-based builders remain far slower than dense kernels because their evaluations are dependent random accesses.
1. Introduction
- Graft removes mutation by building a fixed scaffold from spatial-approximation trees, then searches that scaffold in parallel for each point.The paper asks why this deterministic, parallel approach builds more slowly than tuned Vamana.Source: §1 · p. 2
- 0.88× Vamana’s distance work is achieved by batched feedback, yet FGraft takes 1.55× Vamana’s build time because its mutating substrate raises cost per evaluation.Eight trees with batched feedback match the quality of thirty-two frozen trees; the introduction attributes the remaining time gap to the denser substrate.Source: §1 · p. 2
- At d ≈100, search-based builders run 20–27× below dense GEMM, with five to six times that gap already present in cache.PiPNN [5] evaluates as many distances per point as the beam, but computes fixed-in-advance pair sets as dense blocks.Source: §1 · p. 3
- The wall binds when distances are black boxes or evaluation order is data-dependent; it is absent when vector inner products have a pair set known in advance.Counting distance evaluations can mismeasure the vector case by a factor of twenty.Source: §1 · p. 3
2. Setting and protocol
The evaluation compares graph builders on two nearest-neighbor datasets using a paired, repeated-build protocol. It reports both distance-evaluation work and build time, alongside matched-recall quality.
2. Setting and protocol
- Graft, FGraft, Vamana, PiPNN [5], and hnswlib are evaluated on GloVe-100 and SIFT-128 against a shared brute-force answer key.The datasets contain 1.18M GloVe vectors and SIFT-128 vectors; GloVe is L2-normalized so systems solve the same Euclidean problem.Source: §2 · p. 3
- Builds run on an otherwise idle 64-thread, four-socket Xeon E7-4809 v3 machine, with ten repetitions showing build-time IQR ≤0.5%.The machine has 32 cores, AVX2, and 1.5 TB RAM.Source: §2 · p. 3
- Ten paired blocks use seeded random build order; work counts distance evaluations, time uses each system’s build timer, and quality is distances per query at matched recall.Time ratios use Hodges–Lehmann estimates with exact 95% confidence intervals and exact Wilcoxon signed-rank tests; d@r is interpolated between adjacent beam widths.Source: §2 · p. 4
3. Batched feedback
FGraft restores substrate feedback through synchronous batches while preserving deterministic construction. It keeps a redundant scaffold separate from the sparse output graph and updates the substrate between blocks.
3. Batched feedback
- Each block’s points search the current substrate, write their own adjacency rows, and add the resulting edges to the substrate for the next block.The initial substrate is the symmetrized union of T spatial-approximation trees; harvesting uses beam search followed by occlusion pruning.Source: §3 · p. 4
- The method unions edges rather than replacing the scaffold, and rebuilds the substrate B times instead of after every point.The scaffold retains redundancy for routing, while the harvested output is symmetrized and re-pruned for sparsity; replacing the scaffold with the pruned graph collapses quality.Source: §3 · p. 4
- With keyed randomness, disjoint writes, canonical merges, and point-identifier-based blocks, FGraft’s adjacency is bitwise identical across thread counts and schedules.The schedule-independence proposition makes the graph a function of the data, dimension, parameters, seed, and B.Source: §3 · pp. 4–5
4. Results: work, time, and the cost of an evaluation
FGraft reduces distance work relative to Vamana but remains slower in wall-clock time because its mutating substrate raises the cost of each evaluation. Eight feedback blocks suffice for the quality gain, while finer batching adds cost.
4. Results: work, time, and the cost of an evaluation
- On GloVe, T=8 with B=8 reaches completeness 0.570 and d@0.97 within 2% of the frozen T=32 profile, at 0.43× its distance work and 0.58× its build time.On SIFT, two trees with feedback reach the quality of sixteen frozen trees and parity with Vamana within 1% at both recall targets.Source: §4 · pp. 5–6
- 0.88× (GloVe) and 0.73× (SIFT) Vamana’s distance evaluations still take 1.55× and 1.73× its build time, respectively.The mutating substrate costs 1.8–2.4× per evaluation, versus 1.3–2.2× for the frozen scaffold, because later blocks search a denser graph.Source: §4 · p. 6
- B=8 and B=32 are within 1% in quality on both datasets, but B=32 is 27–28% slower.Eight substrate rebuilds suffice; each additional rebuild densifies the graph searched by the remaining points.Source: §4 · p. 6
- Mutation helps most where the frozen scaffold is expensive: on GloVe it reduces work, but its higher per-evaluation cost takes back half the gain.On SIFT, where the scaffold is already cheap, mutation removes little cost and instead buys quality; the batched design lands just outside the preset ≤1.5× Vamana time threshold with parity quality.Source: §4 · p. 6
5. The random-access wall
The paper separates graph-build work from evaluation throughput and finds that adaptive distance evaluation imposes a random-access wall. That wall widens with dimension, while lockstep batching of existing search beams has too little overlap to reach dense-kernel efficiency.
5.1. PiPNN’s advantage, decomposed
- PiPNN builds 14× faster than Vamana on GloVe and 5.9× on SIFT, while using 0.40× and 0.89× Vamana’s distance evaluations, respectively.93% of PiPNN’s evaluations occur inside GEMMs, while its GloVe distances per query trail Vamana by 41–45%.Source: §5.1 · pp. 6–7, Table 3 · p. 7
5.2. Throughput versus working set
- At d=100, search builders run 20–27× below GEMM at every tested working set; the gap is already 5–6× with data in cache.At full n, Vamana reaches 65% and Graft 49% of the dependent-random-read bandwidth ceiling.Source: §5.2 · pp. 7–8, Figure 1 · p. 8
5.3. The model
- Adaptive evaluations are bounded by random-access throughput, min(BW /4d, fclk/cadapt), while only decomposable distances on a pair set fixed in advance are bounded by arithmetic.The model attributes the adaptive ceiling to dependent loads, per-evaluation bookkeeping, and random-access bandwidth.Source: §5.3 · pp. 8–9
5.4. The wall against dimension
- W(960)/W(128)=1.96 at matched degree, and measured gaps reach 37.5× for tuned Vamana and 83× for the authors’ beam on higher-dimensional corpora.The adaptive side scales as d^1.04 and the dense side as d^0.63, yielding W(d) ∝ d^0.4.Source: §5.4 · pp. 9–10, Table 5 · p. 10
5.5. Can the beam be batched after the fact?
- Lockstep beam batching has only 2–3% density in every configuration, below the 3.7% break-even threshold; dense construction instead requires a pair set fixed before evaluation.The paper says that route would require distance-based clustering leaves plus a separate adaptive pass for long-range edges.Source: §5.5 · pp. 10–11
6. Negative result: the scaffold’s degree
Capping scaffold degree reduces harvest work, but the tested caps degrade quality; at matched build cost, lowering ef_h performs better than capping. The results locate FGraft’s gain in substrate staleness rather than size.
6. Negative result: the scaffold’s degree
- 36% less build work came from capping the scaffold at K=32, but d@0.97 degraded monotonically as K fell.The sweep used GloVe, T32/ef_h600, and distance counts.Source: §6 · pp. 11–12
- At K=64, d@0.97 worsened 3%; at K=32, it worsened 24%, while completeness fell from 0.590 to 0.543.Source: §6 · pp. 11–12
- At matched build cost, lowering ef_h beat capping at every sweep point; 50.3 G at ef_h400 yielded d@0.97 14,047 versus 14,419 at 52.6 G with K=64.The comparison attributes the §4 gain to substrate staleness, not substrate size.Source: §6 · p. 12
7. Related work
Related work divides into search-based builders that adaptively traverse a changing or fixed graph and construction methods that fix pair sets before evaluation. The paper positions its contribution in measuring both distance counts and evaluation cost, including the random-access limits of adaptive search.
7. Related work
- Incremental builders such as HNSW, NSG, and Vamana/DiskANN search and mutate the graph as points are inserted, coupling feedback with serial dependencies.ParlayANN batches insertions into rounds; FGraft batches feedback over a forest-union substrate frozen within each block.Source: §7 · p. 12
- NN-descent, EFANNA [20], SPTAG, HCNNG, PiPNN [5], and GPU k-NN construction fix candidate pairs before evaluation, enabling arithmetic-rate distance computation.These approaches require distances to decompose into inner products or quantized table lookups.Source: §7 · p. 12
- Graft derives from spatial approximation trees and half-space proximal graphs, where distance is a black box and evaluation count is the cost model.For vectors, the paper says this cost model misses evaluation cost by an order of magnitude.Source: §7 · pp. 12–13
- Prior construction work had not applied the roofline or memory-wall models to index building, while this paper also uses Hong and Kung’s I/O bound to frame reuse.Existing benchmarks commonly focus on query throughput and local intrinsic dimensionality.Source: §7 · p. 13
8. Conclusion
Batching feedback recovers much of incremental construction’s benefit while retaining a deterministic input-to-graph mapping, but costs more wall-clock time than Vamana. The broader result is that adaptive distance evaluation imposes a random-access wall that search-based builders cannot eliminate by batching after the fact.
8. Conclusion
- Eight-block feedback recovers the quality of four times as many frozen trees and uses less distance work than Vamana, while taking 1.55× its build time on GloVe and 1.73× on SIFT.The graph remains a pure function of its inputs.Source: §8 · p. 13
- Search-based builders evaluate distances as dependent random accesses, run an order of magnitude below dense arithmetic, and face a gap that widens as d^0.4.The measured gap is 37.5× rather than 19× for 384–1536-dimensional embeddings.Source: §8 · p. 13
- PiPNN’s build advantage comes from fixing pair sets before evaluation, not from evaluating fewer distances; batching the adaptive beam after the fact does not cross the wall.For black-box metrics, distance count remains the appropriate cost measure; for vectors, the wall reflects throughput.Source: §8 · p. 13
Reproducibility
The reproducibility materials include the patched builders, paired driver, analysis scripts, manifests, and logs. Fixed seeds yielded identical distance counts and completeness across all ten Graft-family blocks.
Reproducibility
- The public graft-ann repository includes mutation, logging, and counter patches, alongside patches for ParlayANN and PiPNN.Source: Reproducibility · p. 13
- The paired driver, sweep and density scripts, manifests, and logs behind the tables are included in the materials.Source: Reproducibility · p. 13
- With fixed seeds, every Graft-family arm produced identical distance counts and completeness in all ten blocks.Source: Reproducibility · p. 13