推薦システム、検索、検索拡張生成(RAG)の中心には、最大内積検索(MIPS)がある。クエリベクトルが与えられると、MIPSシステムは数百万の候補鍵ベクトルの中からクエリに最も適合するものを見つけ出す。そして、その最適合鍵に対応する元のデータポイントがクエリの処理に使われる。RAGでは、質問に答えるのに最適な文書がクエリの先頭に付加されるのが典型的だ。鍵の数が数百万に達し、ベクトル次元が数千に及ぶと、クエリを全鍵と網羅的に比較する計算コストは急激に増大する。
精度と速度のトレードオフを取るために、クラスタリングや量子化を用いた多数の近似手法が提案されてきた。これらのベースライン手法は鍵集合の性質に注目して巧妙なインデックス構造を構築するが、その幾何学的な議論ではクエリ集合自体が鍵と似ていると漠然と仮定するか、クエリの形状に関する考察を省略している。これは特にRAGの場合に問題となる。クエリはユーザーが生成する短い質問であるのに対し、鍵は長く情報量の多い厳選されたテキストであり、両者は大きく異なる。さらに、本番環境のMIPSの多くのユースケースは安定した既知のクエリ分布を持つ既存ユーザー基盤を対象としており、汎用的なクエリ非依存手法はこの信号を活用していない。現代の機械学習の中心的な原則は、あらゆる可能な入力で良好な性能を目指すのではなく、想定される入力源に最適化した手法を設計することで、計算資源をより効率的に配分できる。
ICML 2026で発表された論文「Amortizing Maximum Inner Product Search with Learned Support Functions」で、Appleの研究者らは、固定された鍵データベースに対して一度オフラインで小型ニューラルネットワークを訓練し、クエリを最適なマッチに迅速にルーティングする方法を学習させた。このアプローチは、典型的なクエリがどのようにマッチングされるかを理解するための事前の償却コストを支払う代わりに、推論時にこれらの小型ネットワークを通じてより高速で正確な検索を実現する。
MIPSの基本原理は、鍵集合の幾何学を活用して検索を高速化することである。典型的なMIPSシステムは鍵をk個のクラスタに分割し(kは通常、鍵の総数nよりはるかに小さい)、各クラスタの代表的な重心を追跡する。新しいクエリを受け取ると、システムはそれをk個の重心と比較し、最も近い重心のクラスタにクエリをルーティングし、そのクラスタ内のすべての鍵と網羅的に比較する。データベースにn個の鍵があり、k個のクラスタが均等に分布している場合、2番目のステップで考慮される鍵の実効数はn/k程度となり、単純な網羅的アプローチのn回の比較と比べてk倍の高速化が得られる。しかし、このルーティングメカニズムは重心ルーティングが正確でないため、エラーを引き起こす可能性がある(図1参照)。最近傍が自身の最近重心に関連付けられていないために見逃されるのである。
機械学習の観点からMIPSが興味深いのは、これまでほとんど見過ごされてきた数学的構造に基づいている点だ。クエリを集合内の任意の鍵との最大内積に写像する関数は、その集合のサポート関数であり、凸解析でよく研究されている対象である。この関数には2つの重要な性質がある。第一に凸であるため、凸関数専用に設計されたニューラルネットワークである入力凸ニューラルネットワーク(ICNN)で近似できる。第二に、任意のクエリにおけるこのサポート関数の勾配は、最適な鍵そのものを返す。
この研究の基本的なアイデアは、はるかに低い計算コストで真のサポート関数(またはその勾配)を模倣できるニューラルネットワークを学習することだ。これは回帰として知られる古典的な機械学習手法で実現できる。つまり、入力ベクトル(ユーザークエリ)をサンプリングし、MIPSによって生成された関連する出力信号(最適スコアまたは最適鍵ベクトルそのもの)とペアにして多数の訓練例を事前計算し、適切にパラメータ化されたニューラルネットワークを訓練して入力から出力への写像を再現する。
回帰問題が数学的に完全に解ければ、サポート関数を模倣するように訓練された同じニューラルネットワークが、自動微分を通じてその勾配を評価することで最適な鍵を出力できる。しかし実際には、これら2つのタスクそれぞれに特化した別々のネットワークを訓練するのが最善であることが観察された。
SupportNetは、(緩く制約された)ICNNを用いてサポート関数を直接学習するアーキテクチャだ。このアプローチは数学的に原理的であり、問題の凸構造と整合する。データクラスタごとに1つのサポート関数を計算してルーティング品質を向上させる場合に特に威力を発揮する。
KeyNetは、クエリを入力として最適な鍵ベクトルを直接出力することを学習する。斉次関数に関するオイラーの定理から導かれる一貫性損失により、凸性を明示的に強制していなくても、その予測は基礎となるサポート関数に幾何学的に根拠づけられる。
両モデルは、関連するクエリ分布から抽出された例で訓練される。各サンプリングされたクエリについて、真の最適マッチを網羅的検索で一度計算して保存し、実際に重要なクエリ分布に対するMIPS解のランドスケープを捉えた教師ありデータセットを構築する。
図1に示すように、大規模化に対処する最も簡単な方法は、鍵をクラスタに分割し、クエリを各クラスタの重心と比較し、これらのk個のスコアに基づいて最も有望なクラスタにクエリをルーティングすることだ。これは安価だが粗いルールであり、重心だけではクラスタの広がりを考慮できないため、誤りやすい。実際、クラスタには自身の重心から遠いがクエリには近い鍵が含まれることがあり、クエリがそのような外れ値の近くにある場合、重心ルーティングはそのクラスタを低く評価してスキップし、真の最適マッチを見逃す。
各クラスタのサポート関数にアクセスできれば、正確なルーティングが可能になる。各サポート関数は、そのクラスタ内の任意の鍵がクエリとどれだけ高いスコアでマッチできるかを正確に定量化するからだ。図2は、埋め込み空間内でクエリが変化するときの4つのクラスタそれぞれのサポート関数を示している。この理論的洞察に基づき、研究者らはk個のサポート関数を訓練されたSupportNetと共同で学習し、一度にk個のスコアを出力することを提案する。そして、これらk個のスコアの最大値を使って新しいクエリをルーティングする。SupportNetは単純な重心比較よりも有用な問いに答えることができる。「このクエリに対して、このクラスタ内の最良の鍵はどれほど良いか?」SupportNetは、回帰として知られる古典的な機械学習の方法で訓練される。クエリ分布(通常はテキストクエリの埋め込み)からサンプルクエリを生成し、それらのクエリでの真のサポート関数値を計算し、ニューラルネットワークを訓練してこれらの値を再現する。
研究者らは、Natural Questionsデータセットを128クラスタに分割し、さまざまなサイズのSupportNet(XS、S、M、L → データベースサイズの1%、5%、10%、20%)を訓練した。Natural Questionsは、常識的な質問と大規模文書データベースからのパッセージをペアにする検索ベンチマークで、この設定では約260万のユニークなパッセージを含む。
図4は、さまざまなコスト指標に対する検索性能(再現率)を示している。ルーティング再現率は、真のパーティション(正確な最適鍵を含むクラスタ)がルーターの選択した探索対象クラスタに含まれるクエリの割合である。両方のプロットで、クエリとマッチした上位s個のクラスタで網羅的検索が行われる。sは2の累乗(1, 2, 4, 8, …, 128)で増加する。当然ながら、128クラスタすべてを調査するとすべての手法が再現率1に達する。
最初のタブは、固定された検索性能に対して、学習済みルーターが質心ルーティングよりも低い遅延で目標を達成することを示している。小型SupportNetモデルは95%のルーティング再現率を質心ルーティングより約1.9倍高速に達成し(1.74 ms vs 3.36 ms)、大型モデルではさらに改善され、1.74 msで97%に達する。このプロットは、単純な重心比較ではなく小型ニューラルネットワークを実行する追加の計算コストを明示的に考慮している。
2番目のタブは、ニューラルネットワークの実行に伴うオーバーヘッドを無視して、ルーティング品質のみに焦点を当てている。固定された探索クラスタ予算の下で、学習済みルーターは正しいパーティションをより頻繁に見つける。データベースのわずか5%をスキャンするだけで、学習済みルーターは真のパーティションを約90〜93%の確率で回復する(中型モデルMでは最大92.6%)。一方、質心ベースラインは87.5%である。
SupportNetルーティングは、既存の転置ファイルインデックス(IVF)システムにおける単純な質心ベースのルーティングを置き換える。KeyNetの場合、IVFシステムをそのまま維持し、変更されたクエリを入力するだけでよい。このシナリオでは、KeyNetは標準的な近似検索インデックスの前段で「クエリリライター」として自然に機能する。最適マッチが埋め込み空間のどこにありそうかを予測し、元のクエリから開始する代わりに、その場所を既存のIVFシステムに探索させる。IVFインデックスは高度に最適化されているため、KeyNetの支援を受けるとより高速に結果を見つけられる。KeyNetも回帰で訓練される。サンプルクエリを真の最適鍵とマッチさせ、その関連を再現するようにニューラルネットワークを訓練する。
研究者らはさまざまなサイズのKeyNet(XS、S、M、L → データベースサイズの1%、5%、10%、20%)を評価し、図6でこれらのサイズの再現率とコストのトレードオフを示している。最初のタブでは、検索予算は実時間の遅延である。最大のモデルを使用すると、99%の再現率に達するまでの時間が最大約8倍短縮される(0.23 ms vs 元のクエリの1.8 ms)。前と同様に、2番目のタブは、元のクエリをKeyNetの出力で置き換えることによってもたらされる「品質」の向上のみに焦点を当てている。