Batched feedback improves graph construction but hits a random-access speed limit
Batched Feedback and the Random-Access Wall in Search-Based Graph Construction
Databases
Summary
Building graphs to quickly find nearest neighbors in data can be done step-by-step (incrementally) or all at once (in batch). The authors find that batching with feedback can reduce work but still takes longer because of slower data access. They uncover a fundamental speed limit caused by how distance checks depend on prior results and require random memory access. Their analysis shows this limit grows with data complexity and explains why some newer methods are faster by avoiding these random accesses.
What this means in practice
- •For machine learning engineers: Optimize nearest-neighbor graph building by choosing batch sizes to balance work and speed, improving large-scale data search efficiency.
- •For database developers: Design graph-based index structures with awareness of memory access costs to avoid random-access bottlenecks during query preprocessing.
Authors
Édgar Chávez
Abstract
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.