LinePG’s 44.76× SIFT throughput gain comes with better recall—not an equal-recall shortcut

The result that matters

LinePG reports 613.11 queries per second at 99.58% Recall@10 on the full 1-million-vector SIFT dataset. The strongest tested direct-search configuration over the original HNSW graph reaches 13.70 QPS at 98.93% recall. That is a 44.76× throughput advantage while also improving recall, rather than a speedup interpolated at an identical quality point.

The distinction matters because line nearest-neighbor search is not ordinary point search. Each query is an infinite line defined by two endpoints; points close to that line can sit in regions that are far apart from one another. A graph built only around point-to-point proximity can therefore settle into one region and miss another. LinePG keeps HNSW’s total degree limit at 32 but reserves up to four selected “pair edges” per point to bridge those separated regions.

What was actually tested

The paper evaluates six full datasets: YaleB (15,624 vectors, 252 queries), CelebA (60,000, 1,000), FFHQ (70,000, 1,000), Multi-PIE (246,012, 6,474), SIFT (1 million, 10,000) and GIST (1 million, 10,000). It compares LinePG with direct line-distance search on HNSW, a quadratic-dimension lifting method, brute-force scanning and—on 512-vector subsets only—a theoretical line-search implementation.

At recall of at least 99%, LinePG’s full-dataset QPS gain over direct search ranges from 1.55× to 4.23× for top-10 retrieval on the four datasets where both methods crossed that threshold. Direct search did not reach 99% on full SIFT or GIST for top-10 within the tested range. For top-100, where all six comparisons clear 99%, the reported gain ranges from 1.44× to 2.44×.

The index-cost result is less dramatic but operationally useful. Across the full datasets, LinePG occupies 1.000× to 1.046× the storage of direct HNSW. On GIST, it adds 255.680 seconds of enhancement work to a 2,271.748-second HNSW build, producing a 2,527.428-second total.

The boundary on the claim

This is a single-paper evaluation on one CentOS server with an Intel Xeon Silver 4215, 128GB of memory, C++17 and single-threaded search. SIFT and GIST line queries are synthetically formed by pairing released point queries; they are not observed production line-query logs. The arXiv record links the paper but no public code repository, so the results are not yet independently reproducible from a packaged artifact.

The strongest conclusion is therefore narrower than “vector search is 44× faster.” Pair-edge augmentation appears to repair a specific failure mode of ordinary proximity graphs for line queries, and it does so without relaxing the degree bound. Independent code and non-image workloads are the next evidence needed.