Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions

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.

한 줄 요약

Grid 기반 ANN 알고리즘의 N 및 d 스케일링 특성을 체계적으로 분석하여, GloVe 데이터셋에서 기존 방법 대비 우수한 성능을 보임.

핵심 기여도

Multiprobe grid 알고리즘이 GloVe 데이터셋에서 d-스케일링 측정에서 다른 ANN 방법들보다 일정한 성능을 유지함.
Query 처리 시간이 N에 대해 거의 선형적으로 증가하며, indexing 비용이 경쟁 알고리즘 대비 낮음.
Grid 기반 방법이 rebuild-heavy 및 고차원 환경에서 경쟁력이 있음을 제시함.
Self-attention과 ANN 간 연관성을 통해 Transformer 아키텍처의 효율성 분석에 기여함.

핵심 아이디어

기존 ANN 연구에서 Grid 기반 방법은 주목받지 못했으나, 본 연구는 Multiprobe Grid 알고리즘의 N과 d에 대한 스케일링 특성을 체계적으로 분석함. 핵심 아이디어는 PCA-감소된 하위 공간에서 셀 선택(cell selection)을 수행하고, ℝ^d 공간에서 후보 재정렬(re-ranking)을 통해 차원 증가에 따른 성능 저하를 완화하는 점이다. 이는 기존 그래프, 트리, 파티셔닝 기반 방법들이 고차원에서 성능이 악화되는 것과 대조된다.

기술적 접근법

**Multiprobe Grid 알고리즘** 사용: PCA-감소된 ℝ^m 공간에서 셀 선택, ℝ^d 공간에서 후보 재정렬.
**GloVe 데이터셋**을 대상으로 실험 수행.
**Query 처리 시간**이 N에 대해 거의 선형적 (near-linear).
**Indexing 비용**이 경쟁 ANN 방법들 대비 낮음.
**d-스케일링 측정**에서 일정한 성능 유지.

주요 결과

GloVe 데이터셋에서 multiprobe grid는 다른 ANN 방법들 대비 일정한 d-스케일링 지수를 유지함.
Query 처리 시간이 N에 대해 near-linear로 증가.
Indexing 비용이 경쟁 알고리즘 대비 낮음.
Rebuild-heavy 및 고차원 환경에서 Grid 기반 방법이 우수한 성능 보임.

의의 및 한계

본 연구는 Grid 기반 ANN 방법이 고차원 및 빈번한 인덱스 재구성 환경에서 경쟁력이 있음을 입증함. 특히, Self-attention이 ANN 연산으로 정식화된 맥락에서, ANN 알고리즘의 N 및 d 스케일링 특성은 Transformer 아키텍처의 효율성 분석에 중요한 지표가 될 수 있다. 그러나, multiprobe grid의 성능은 데이터셋의 분포와 PCA 감소 차원(m)에 따라 달라질 수 있으며, 이는 한계로 작용할 수 있다.

실용적 활용

Grid 기반 ANN은 고차원 벡터 검색이 필요한 NLP, 추천 시스템, 이미지 검색 등에서 활용 가능하다. 특히, 인덱스 재구성이 빈번한 실시간 시스템에서 multiprobe grid의 낮은 indexing 비용과 차원에 대한 안정성은 실용적 이점을 제공한다.