近似最近傍（ANN）探索は、推薦システム、セマンティック検索、検索拡張生成など、現代の機械学習システムにおける基盤コンポーネントです。長らく研究コミュニティはグラフベース、木ベース、分割ベースの手法に注目してきました。しかし、最近arXivに投稿された論文「Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions」は、現代のスケーリング分析から欠けていたグリッドベースの手法に焦点を当てています。
Matthew J Liuら7名の著者によるこの研究は、マルチプローブグリッドアルゴリズムをデータセットサイズNと次元dの変化に対して系統的に特徴づけています。実験により、GloVe埋め込みファミリー上でこれまで報告されていなかった次元スケーリングのクロスオーバーが明らかになりました。具体的には、次元が増加するにつれて、マルチプローブグリッド探索はほぼ一定の次元スケーリング指数を維持する一方、グラフ・木・分割ベースの他の手法はスループットが低下します。これは、高次元設定においてグリッド手法が従来手法よりも堅牢である可能性を示唆しています。
次元上の優位性に加えて、マルチプローブグリッドはNに対してほぼ線形のクエリ複雑度を持ち、競合するANN手法よりもインデックス構築コストが低いという特徴があります。この特性により、グリッド手法は再構築が頻繁な環境や高次元環境で競争力を持つ可能性があります。これらの設定では、インデックスコストと次元の堅牢性が性能を決定する重要な要素となるからです。
著者らはさらに広い意義を指摘しています。最近の研究では、自己注意メカニズムがANN操作として形式化されています。したがって、ANNアルゴリズムのNおよびdに関するスケーリング特性は、効率的なTransformerアーキテクチャのコスト分析を導く可能性があります。言い換えれば、グリッドANNのスケーリング則を理解することで、Transformerモデルの計算複雑度をよりよく理解できるかもしれません。
論文のコードはGitHubで公開されており（https://github.com/weiz345/MultiProbeANN）、コミュニティによる再現とさらなる研究が可能です。この研究は機械学習（cs.LG）および人工知能（cs.AI）に分類され、2026年7月1日に投稿されました。