{"ID":5675618,"CreatedAt":"2026-07-03T01:40:09.565152011Z","UpdatedAt":"2026-07-04T08:33:09.063375117Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.01283","arxiv_id":"2607.01283","title":"Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions","abstract":"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.","short_abstract":"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 G...","url_abs":"https://arxiv.org/abs/2607.01283","url_pdf":"https://arxiv.org/pdf/2607.01283v1","authors":"[\"Matthew J Liu\",\"Wei Hang Zheng\",\"Vidhan Purohit\",\"Siqi Xie\",\"Chieh-En Li\",\"Jerry Li\",\"Noah Flynn\"]","published":"2026-07-01T08:42:38Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"cs.AI\"]","methods":"[\"Transformer\"]","has_code":false,"code_links":[{"ID":613905,"CreatedAt":"2026-07-03T01:40:09.565152011Z","UpdatedAt":"2026-07-03T01:40:09.565152011Z","DeletedAt":null,"paper_id":5675618,"paper_url":"https://arxiv.org/abs/2607.01283","paper_title":"Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions","repo_url":"https://github.com/weiz345/MultiProbeANN","is_official":false,"mentioned_in_paper":false,"mentioned_in_github":true,"github_stars":0}]}