高次元におけるグリッドベース近似最近傍探索のスケーリング則
本研究は、マルチプローブグリッドアルゴリズムを体系的に評価し、GloVe埋め込みにおいて従来手法とは異なる次元スケーリングクロスオーバーを示すことを発見。一定の次元指数、ほぼ線形のクエリスケーリング、低インデックスコストを達成し、高次元設定での競争力を示すとともに、効率的なTransformerアーキテクチャのコスト分析に貢献する。
近年、近似最近傍探索（ANN）は機械学習と人工知能において重要な役割を果たしており、特に効率的なTransformerアーキテクチャの発展に伴い、自己注意機構がANN操作として形式化されています。しかし、グリッドベースの手法は現代のスケーリング分析では長らく見過ごされてきました。Matthew J. Liu氏ら7名の研究者による、2026年7月1日にarXivに投稿された新しい研究は、このギャップを埋めるものです。彼らは、データセットサイズNと次元dに対するマルチプローブグリッドアルゴリズムの振る舞いを体系的に評価しました。
研究チームはGloVe埋め込みファミリーを用いた実験により、これまで報告されていない次元スケーリングクロスオーバーを発見しました。マルチプローブグリッド探索はほぼ一定の次元スケーリング指数を維持する一方、グラフベース（例：HNSW）、ツリーベース（例：KD-tree）、分割ベース（例：IVF）の手法では高次元でスループットが低下します。この利点は、クエリのほぼ線形スケーリングと、競合するANN手法よりも低いインデックスコストに現れています。特に、インデックスの再構築が頻繁な環境や高次元設定では、インデックスコストと次元ロバスト性が性能を左右するため、グリッド手法は競争力を持つ可能性があります。
さらに、自己注意がANN操作として形式化された最近の研究を踏まえると、ANNアルゴリズムのNおよびdスケーリング特性は、効率的なTransformerアーキテクチャのコスト分析に役立つと考えられます。本研究のコードはGitHub（https://github.com/weiz345/MultiProbeANN）で公開されており、コミュニティによる再現と拡張が容易です。この成果は、グリッドベース手法のANN分野における復活を示唆するとともに、次元の呪いのために放棄されてきた単純な手法を再評価する機会を提供します。今後、グリッド手法は大規模・高次元の機械学習システム構築の重要なツールとなるかもしれません。