技術要約：高次元におけるグリッドベース近似最近傍探索のスケーリング則

問題提起

近似最近傍（ANN）探索は、従来の検索タスクだけでなく、自己注意機構（Self-Attention）がANN操作として定式化されているトランスフォーマー・アーキテクチャの計算ブロックとしての新たな役割も含め、現代の機械学習における基本的なプリミティブである。経験的なスケーリング則が大規模モデルの設計を導いている一方で、データセットサイズ（$N$）および次元数（$d$）に対するANNアルゴリズムのスケーリング挙動は、極めて重要でありながら、未だ十分に特徴付けられていない研究領域である。

既存の文献では、グラフベース（例：HNSW）、木構造ベース、およびパーティショニングベースの手法が広く分析されてきた。しかし、グリッドベースのアプローチは、初期のANN理論における基礎的な役割にもかかわらず、現代のスケーリング解析からは概ね欠落している。本論文は、マルチプローブ・グリッド・アルゴリズムの性能が $N$ および $d$ に対してどのようにスケールするかを、最先端の競合手法と比較して体系的に調査することで、この空白を埋めるものである。

手法

マルチプローブ・グリッド・アルゴリズム

著者らは、セル選択をフル次元 $d$ から切り離したマルチプローブ・グリッド・アルゴリズムを提案している。ワークフローは以下の通りである：

1. PCA投影: データポイントを $\mathbb{R}^d$ から低次元の部分空間 $\mathbb{R}^m$ （$m \ll d$）へと投影する。
2. グリッド分割: 部分空間を $G^m$ 個の均一なグリッドセルに分割する。
3. マルチプローブ選択: クエリ実行時に、「ホーム」セルを特定し、クエリからの二乗壁距離（squared wall distance, $w_i^2$）に基づいて順序付けられた最大 $2^m - 1$ 個の隣接セルを探索する。
4. 再ランキング: 探索されたセルから収集された候補を、元の高次元空間 $\mathbb{R}^d$ で再ランキングする。

理論モデル

著者らは、クエリコスト（Queries Per Second, QPS）と再現率（Recall, $R$）の間の閉形式の関係を導出している。

• コストモデル: クエリコストは、探索されるセルの数（$n_{probe}$）およびセルあたりの点数（$N/G^m$）に対して線形である。
• 再現率モデル: 一様分布を仮定すると、真の最近傍が探索されたセル内に存在する確率は、壁距離とともに指数関数的に減少する。
• 導出される関係: モデルは、QPSと再現率の間に対数線形関係 $\log(\text{QPS}) \approx \log(\text{const}) - \log(R)$ を予測する。これは、セル間の所属確率の指数関数的減衰と、候補集合サイズの線形増加に起因する。

実証評価

本研究では、主要なANNファミリーを代表する4つのベースラインを用いて、マルチプローブ・グリッドを評価している：

• グラフベース: Voyager, PyNNDescent.
• 木構造ベース: Annoy.
• パーティショニング/量子化: FAISS-IVF.

実験は ann-benchmarks フレームワークを用い、2つのデータセットで実施された：

1. GloVe-200-angular（単語埋め込み、$d=200$, $N \approx 1.18 \times 10^6$）。
2. SIFT-128-euclidean（画像記述子、$d=128$）。

評価は、$N$ に対するスケーリング指数（$\alpha_N$）および $d$ に対するスケーリング指数（$\alpha_d$）、パレートフロント（スループット vs 再現率）、および総コスト分析に焦点を当てた。

主な結果

1. 対数線形なスループット・再現率関係

GloVe-200におけるパレートフロント解析により、理論的予測が裏付けられた：マルチプローブ・グリッドは、再現率が増加するにつれてスループットが対数線形に減少する。この挙動はベースラインとは異なり、グリッドの幾何学的構造と最近傍の所属確率の指数関数的減衰によって駆動されている。

2. $N$ スケーリング：近線形な劣化

マルチプローブ・グリッドは、データセットサイズ（$N$）に対して近線形的にスケールする。

• 再現率@10 = 0.80 において、スケーリング指数は $\alpha_N \approx -0.94$ (GloVe) および $-0.83$ (SIFT) である。
• 対照的に、グラフベースおよび木構造ベースのベースラインは、劣線形的なスケーリング（$\alpha_N$ の範囲は $-0.44$から$-0.59$）を示す。
• 示唆: マルチプローブ・グリッドのスループットは、グラフ手法と比較して $N$ の増大に伴い急速に劣化するが、これはアルゴリズムの設計（候補数が $N$ に比例して増加すること）によるメカニズム的な帰結である。

3. $d$ スケーリング：決定的なクロスオーバー

GloVe埋め込みファミリーにおいて、これまで報告されていなかった$d$ スケーリングのクロスオーバーが観察された。

• ベースライン: 次元 $d$ が増加するにつれ、グラフ、木構造、およびパーティショニング手法のスループットは著しく低下する（急峻な $\alpha_d$）。これは「次元の呪い」と、高次元における幾何学的枝刈りの失敗を反映している。
• マルチプローブ・グリッド: アルゴリズムの $\alpha_d$ は、次元 $d$ が増加しても比較的平坦かつ良好な状態を維持する。
• メカニズム: 低次元のPCA部分空間（$m \ll d$）でセル選択を行い、かつ $d$ と目標再現率に基づいてグリッドパラメータ（$m, G$）を適応させることで、このアルゴリズムはフル次元空間の探索を回避している。再ランキングのコストは候補数に対して線形にしか増大しないため、フル次元空間を横断する手法よりもコストの増大が緩やかである。

4. 総コストとインデックス作成効率

本論文では、総コスト $J(N) = f_I \cdot I(N) + f_C \cdot C(N) + M(N)$ を分析している（ここで $I$ はインデックス作成コスト、$C$ は計算コスト、$M$ はメモリフットプリントである）。

• インデックス作成速度: マルチプローブ・グリッドは、ベースラインよりも大幅に高速に構築できる。$N = 1.18 \times 10^6$ において、Voyagerが1,569秒かかるのに対し、本手法は4〜36秒でインデックスを構築できる。
• クエリレイテンシ: マルチプローブ・グリッドは、1クエリあたりのレイテンシが高い（高再現率においてVoyagerより約120倍遅い）。
• 競争力のある領域: 再構築対クエリ比（$f_I/f_C$）が高い場合に、本手法は競争力を持つ。具体的には、インデックスが約2,600〜20,400回のクエリにつき1回再構築される場合、マルチプローブ・グリッドはより低い総コストを実現する。これは「再構築頻度の高い」シナリオに適している。

意義と主張

本論文は、現代のスケーリング解析において見落とされがちなグリッドベースの手法が、特定の領域において明確かつ競争力のあるトレードオフを提供することを主張している：

1. 次元に対する堅牢性: マルチプローブ・グリッドは、幾何学的枝刈りが機能不全に陥る高次元設定において、グラフや木構造の手法を凌駕する、特有の次元に対する堅牢性を持っている。
2. 低いインデックスオーバーヘッド: データ依存の複雑なグラフ構築を必要とするグラフベースの手法と比較して、ほぼ瞬時のインデックス作成が可能である。
3. トランスフォーマーへの関連性: 自己注意機構がANN操作として定式化されていることを踏まえると、ANNアルゴリズムの $N$ および $d$ スケーリング特性は、トランスフォーマーの効率性に直結する。著者らは、以下の条件下でマルチプローブ・グリッドが有利である可能性を示唆している：
   • コンテキスト長（$N$）またはヘッド次元（$d$）が変動する場合。
   • 逐次更新（例：KVキャッシュの拡張）が頻繁に行われる場合。グリッドへのトークンの追加は、グラフ全体の再構築を必要とせず、単一のセル割り当てのみで済むためである。
4. 総コストの観点: ANN手法の選定は、クエリレイテンシのみに依存すべきではなく、インデックス作成頻度や再構築コストを含む総コスト関数を考慮すべきである。再構築が頻繁なシナリオにおいては、グリッド手法の低いインデックス作成コストが、その高いクエリレイテンシを相殺し得る。

要約すると、本研究は、インデックス作成コスト、再構築頻度、および次元に対する堅牢性が主要な制約となる場合において、グリッドベースの手法を、高次元学習システムにおける実行可能な選択肢として再確立するものである。