Metraipolis › archive › dc_bc16cc5f3aa7
Batched Feedback and the Random-Access Wall in Search-Based Graph Construction — arXiv:2609.30493
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.30493
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T03:34:23.518Z
- SHA-256 of the archived text
02ec6be6c6327a600e76b6c372ea9f23076b6423df0c7eb45ba20ff13029bf99- Stable URL of this page
https://metraipolis.com/documento/dc_bc16cc5f3aa7
How to cite
Batched Feedback and the Random-Access Wall in Search-Based Graph Construction — arXiv:2609.30493 — arXiv (en), https://arxiv.org/abs/2609.30493 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bc16cc5f3aa7 (Metraipolis archive dc_bc16cc5f3aa7, sha256 02ec6be6c6327a600e76b6c372ea9f23076b6423df0c7eb45ba20ff13029bf99)
BibTeX
@misc{dcbc16cc5f3aa7,
title = {Batched Feedback and the Random-Access Wall in Search-Based Graph Construction — arXiv:2609.30493},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.30493},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bc16cc5f3aa7; sha256 02ec6be6c6327a600e76b6c372ea9f23076b6423df0c7eb45ba20ff13029bf99},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.30493. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-28 in cs.DB).
Categorie arXiv: Databases (cs.DB).
Pagina del lavoro: https://arxiv.org/abs/2609.30493 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T03:11:41.429Z dalla pagina https://arxiv.org/catchup/cs.DB/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).