Doing fewer distance calculations can still make an ANN index slower

The result that matters

A new benchmark of approximate-nearest-neighbor graph construction shows why counting distance evaluations is not enough to predict build speed. On the 1.18-million-vector GloVe-100 dataset, FGraft with eight feedback batches performed 27.66 billion distance evaluations, 12% fewer than Vamana’s 31.56 billion. Yet FGraft took 226.3 seconds, versus 145.9 seconds for Vamana: 1.55× slower despite doing less measured work.

The same inversion appeared on the one-million-vector SIFT-128 dataset. FGraft’s selected configuration used 8.03 billion evaluations against Vamana’s 11.06 billion, but needed 89.6 seconds rather than 51.7 seconds. That is 27% less distance work and 1.73× the build time.

Those are not single lucky runs. The authors used ten paired blocks on an otherwise idle 32-core, 64-thread Intel Xeon E7-4809 v3 machine. Each system built once per block in seeded random order; reported ratios use Hodges–Lehmann estimates with exact 95% confidence intervals. The GloVe time ratio was 1.55× [1.55, 1.56], while the SIFT ratio was 1.73× [1.72, 1.75].

Where the time went

The benchmark reports distance work separately from cost per evaluation. FGraft’s cost per distance was 1.77× Vamana’s on GloVe and 2.39× on SIFT. The paper attributes that penalty to adaptive access through a mutating graph substrate: later searches traverse a denser union of the original scaffold and previously harvested rows, increasing pointer-chasing cost.

A throughput experiment makes the systems-level limit clearer. On the full GloVe prefix, Graft processed 0.165 billion distances per second and Vamana 0.216 billion; dense GEMM reached 4.45 billion. The dense kernel was therefore 27.0× faster than Graft and 20.6× faster than Vamana. Even with a 9 MB, 20,000-vector prefix resident in cache, GEMM remained 5.9× and 5.1× faster, respectively.

PiPNN illustrates the alternative. It built GloVe in 10.35 seconds while evaluating 12.56 billion distances. The paper says 93% of those evaluations run inside GEMM-like dense blocks, yielding 1.21 billion evaluations per second. Its advantage is not simply avoiding work; it arranges the work so hardware can execute it efficiently.

How to read this benchmark

The finding does not say every graph builder should become a dense matrix calculation. The authors delimit the “random-access wall” to adaptive evaluation, where each next access depends on previous results, or to black-box distances. Dense blocking requires a decomposable distance and a pair set known in advance.

The practical lesson is narrower and useful: an ANN build benchmark should publish both distance evaluations and wall-clock time. An algorithm can win the work counter and still lose the build because memory access, dependency chains and per-evaluation overhead dominate. Without both measurements, “more efficient” is an incomplete claim.