Appleの研究者は、従来の幾何学的検索を小型の学習済みニューラルネットワークに置き換えることで、Retrieval-Augmented Generation(RAG)の計算コストを大幅に削減する手法を開発しました。データベースの「サポート関数」を予測するようにモデルを訓練することで、システムは標準的なセントロイド(重心)ベースの手法よりも正確にクエリを正しいデータクラスターにルーティングでき、高再現性の結果において最大8倍高速な検索を実現しました。

幾何学的検索の限界

Maximum Inner Product Search(MIPS)は、推薦システムやRAGの背後にあるエンジンであり、システムは与えられたクエリに対して最適な一致を示す「キー」ベクトルを見つけなければなりません。データベースが数百万のキーに成長し、次元が数千に達するにつれ、網羅的な比較は計算上困難になります。

現在の近似手法は、キーをセントロイドの周囲にグループ化するクラスタリングを頻繁に使用します。しかし、これらの手法はクエリがキーに類似していることを前提としています。RAGにおいては、これは多くの場合事実に反します。ユーザーのクエリは通常短く、キーは長くキュレートされたテキストであるため、最良の一致がクラスターの中心から遠い位置にあるためにスキップされるというルーティングエラーが発生します。

幾何学的検索がセントロイドベースの分割により最近傍を見つけられないことを示す図。
図1は、従来の幾何学的アプローチが、セントロイドへの距離に基づく空間分割に依存しているために最近傍を見逃す可能性があることを示しています。machinelearning.apple.com

この画像は、クエリがセントロイドから遠いために誤ったクラスターにルーティングされる可能性があるという、幾何学的検索の根本的な限界を説明しています。

「SupportNetモデルは、単純なセントロイドとの比較よりも有用な質問に答えることができます。それは『このクラスター内の最良のキーは、このクエリに対してどれほど優れているか?』という問いです。」

— Faster Retrieval for Better, More Efficient RAG

SupportNetとKeyNetのアーキテクチャ

研究者たちは、MIPSの価値関数が凸解析における「サポート関数」であることを特定しました。彼らはこれを利用するために、SupportNetとKeyNetという2つの専門的なモデルを開発しました。SupportNetは、各クラスターのサポート関数を近似するように訓練された入力凸ニューラルネットワークであり、「このクラスター内の最良のキーは、このクエリに対してどれほど優れているか?」という問いに答えます。

クラスタールーティングにおけるセントロイドベースの割り当てとサポート関数ベースの割り当ての比較。
図2は、セントロイドへの距離に依存することが誤解を招く可能性がある一方で、クラスターのサポート関数を使用することでより正確な割り当てが可能になることを示しています。machinelearning.apple.com

この視覚資料は、クラスター内の最良のキーを考慮するSupportNetアプローチへの移行をサポートします。

SupportNetがサポート関数を近似し、最良の一致に基づいてクエリをクラスターに割り当てる視覚化。
図3は、SupportNetが単なるセントロイドではなく、クラスター内の任意のキーとの最良の一致に基づいてクエリを割り当てるために、どのようにサポート関数を近似するかを示しています。machinelearning.apple.com

この画像は、アーキテクチャセクションで説明されているSupportNetのメカニズムを例証しています。

KeyNetモデルは、最良の一致するキーベクトルを直接出力することを学習します。オイラーの定理から導出された一貫性損失を使用することで、これらのモデルは明示的な凸制約がなくても幾何学的な根拠を維持します。両方のモデルは、Natural Questionsベンチマークで見られるような、実際に重要なクエリの特定の分布で訓練されます。

パフォーマンスの向上とトレードオフ

テストにおいて、SupportNetモデルは従来のセントロイドルーティングよりも約1.9倍速く、95%のルーティング再現性を達成しました。最大のモデルを使用した場合、システムは1.74ミリ秒で97%の再現性を達成し、小型のニューラルネットワークが独自の推論オーバーヘッドを考慮しても幾何学的ベースラインを上回ることができることを示しました。

様々なサイズのSupportNetにおけるルーティングパフォーマンス再現性とレイテンシを示すチャート。
図4は、異なるサイズとスキャン割合のSupportNetにおけるルーティングパフォーマンスとレイテンシのトレードオフを表示しています。machinelearning.apple.com

このチャートは、記事の最終セクションで議論されているパフォーマンスの向上とトレードオフに関する実証的な証拠を提供します。

SupportNetのパフォーマンス vs. Centroid Routing: Centroid Routing 3.36 ms; Small SupportNet 1.74 ms
SupportNetのパフォーマンス vs. Centroid Routingmachinelearning.apple.com

HN Digestによる図(machinelearning.apple.comの報告数値に基づく)。数値はソースの表記通り。

KeyNetは、クエリ書き換えとして機能することで異なる利点を提供します。生のクエリをターゲットのキーに非常に近いベクトルに変換することで、99%の再現性に到達するためにインデックスがスキャンする必要があるキーの数を最大11倍削減できます。これらのモデルは、固定されたデータベースで訓練するための事前のコストを必要としますが、安定したクエリ分布を持つプロダクションシステムにとって、より効率的な経路を提供します。

「Matchbox Twentyとは何ですか?」という質問に対する、生のクエリとKeyNetでマッピングされたクエリのトップ3ヒットの比較。
図7は、KeyNetが生のクエリをデータベースのキュレートされたキーにより密接に整合するベクトルにマッピングすることで、どのように検索を改善するかを示しています。machinelearning.apple.com

この例は、パフォーマンスセクションで言及されているKeyNetモデルの「クエリ書き換え」機能を実証しています。