ベクトルへの埋め込みを使った検索システムの理論的な限界と、実験と、現実的な例についての論文(DeepMindのインターンシップの成果らしい)。

https://arxiv.org/abs/2508.21038

理論的な限界について: n個のドキュメントとm個のクエリが与えられたとする。このとき、クエリを行としてドキュメントを列とした行列を考えて、各要素はドキュメントがクエリにマッチすべきであれば1, そうでなければ-1とする。どのようなドキュメントとクエリの組み合わせに対してもこの行列の通りに検索できるシステムをベクトル検索で作る場合、ベクトルの次元はこの行列のランク-1以上である必要がある。一方、この行列のランクだけあれば十分である。

実験1: テスト用のランダムな行列に対して、それを再現する埋め込みベクトルを各ドキュメントとクエリに割り当てるようなモデルをAdam最適化器で求め、再現に成功する次元数の最低値を求めた。するとドキュメント数に対して3次式で近似できるような値となった(クエリ数はドキュメント数の2乗というかnC2で増やしてるので3乗となる)。4096次元だと2億5千万ドキュメントが上限となる。

実験2: では、そのようなランダムな行列は現実的なのかという問題がある(AI関連の問題は見掛け上の次元は高くて解けなそうに見えても、実質的な次元は非常に低いので解けるというような場合がよくある)。その答えとして、次のようなドキュメントとクエリを考える。n人の人がいたとして、ドキュメントは各人が好きなものが書かれているとする。一方、クエリは「○○が好きな人はだれですか」というものである。ドキュメントとクエリの内容を調整することで任意の行列が現れる。実際、埋め込みが難しいであろう行列を用意してそれに対するドキュメントとクエリを作成して、既存の埋め込みモデルをテストしたところ、総ドキュメント数50万, 各クエリにマッチすべきドキュメント数2という条件で再現率は非常に低い結果となった(一方、キーワードによる単純な検索システムは当然高い値が出る)。