Search papers, labs, and topics across Lattice.
This paper systematically analyzes a multiprobe grid algorithm for approximate nearest neighbor (ANN) search, focusing on its performance relative to dataset size \(N\) and dimensionality \(d\). The authors identify a unique \(d\)-scaling crossover in the GloVe embedding family, where the grid-based approach maintains a stable dimensional scaling exponent, unlike traditional methods that suffer from throughput degradation. Their findings indicate that multiprobe grid search offers near-linear query scaling with lower indexing costs, positioning it as a viable alternative in high-dimensional and rebuild-heavy scenarios.
Multiprobe grid search reveals a surprising dimensional robustness that traditional ANN methods lack, maintaining efficiency even as dimensions increase.
Grid-based approaches to approximate nearest neighbor (ANN) search have been absent from modern scaling analyses. We present a systematic characterization of a multiprobe grid algorithm with respect to dataset size $N$ and dimensionality $d$. Our experiments reveal a previously unreported $d$-scaling crossover on the GloVe embedding family, in which multiprobe grid search maintains an approximately constant dimensional scaling exponent while other graph-, tree-, and partitioning-based methods exhibit degrading throughput. The advantage comes with near-linear query scaling in $N$, but also with lower indexing cost than competing ANN methods. Our results suggest that grid-based methods such as multiprobe grid may be competitive in rebuild-heavy or high-dimensional settings where indexing cost and dimensional robustness dictate performance. More broadly, recent work has formalized self-attention as an ANN operation. Thus, the $N$- and $d$-scaling properties of ANN algorithms may guide cost analysis of efficient transformer architectures. Code is available at: https://github.com/weiz345/MultiProbeANN.
