On the Theoretical Limitations of Embedding-Based Retrieval

hillbig 情報検索で埋め込みベクトルによる検索が普及しているが、理論的な限界があることが示された。それは、クエリと文書ベクトルの次元数dで表現できる、文書組み合わせの数に限界があり、「絶対表現できない検索タスク」が存在することを示す。

この限界は文書・クエリ間の内積行列の自由度が、sign-rankという数学的概念で表され、dをかなり大きくしないと得られない。例えば、4k次元の埋め込みでは数億程度の文書集合は表現できない（検索対象は数十億〜数百億文書が多い）。

また、現実的で自由度が高い仮想的な問題設定のLIMITデータセットを設計。これは誰が何が好きかという文書と、「誰がリンゴが好きか」というクエリからなり、すべてのtop-k組み合わせを網羅している。最新の埋め込みでもrecallはほとんどあげられなかった。

一方、埋め込みでは難しかったが、クロスエンコーダー（クエリと文書の両方を同時に符号化しスコアか）やそれを使ったリラングでは解くことができるし、マルチベクトル、スパースモデルも解くことができる。

今の学術ベンチマークはクエリ空間のほんの一部分しか測っておらず、過学習のおそれもある（上記のように本質的には解けない問題も含んでいる）

===

情報検索ではキーワード検索や全文検索から、埋め込みベクトルの万能性が広く使われるようになっているが、上記のように限界がある。近傍探索を有限d次元のベクトル空間に押し込んでいるため限界がある（2次元地図に複雑な交通網を押し込めない）

一方で、このd次元のベクトル空間という非常に制限がある中でも理論的に示されている有効な検索ができていること自体の方になぜそうなっているのかを意味するのが必要かもしれない。実際の検索におけるクエリ空間の局所性や、人間の言語や意味空間における冗長性や構造などを捉えるきっかけになるかもしれない