# On the Theoretical Limitations of Embedding-Based Retrieval

[paper link](https://arxiv.org/abs/2508.21038)
[github](https://github.com/google-deepmind/limit)

## Intro

- 在 LLM 出現後的時代，我們常常直接拿 LLM 來將 query 以及 document 轉換成 embedding，然後計算兩者之間的相似度，以此來得知兩者之間的關係遠近，這個架構又叫做Bi-encoder
- 我們也普遍認為，只要使用足夠巨大的模型以及足夠好的訓練資料，他就會能夠處理巨量的 document，就像是假設這個模型可以輸入無限的 document 一樣
- 但是這個認知基本上並沒有足夠的理論基礎，本作的目的就是在探索單一且固定維度的 embedding 是否真的能 embed 無限的 document? 難道沒有其限制嗎? 那如果有的話，他在數學上的限制又是什麼?
- 本作的實驗方法是將模型回傳 top-k result 的這個流程轉換為一個相關性矩陣的形式，計算出理論上的限制
- 以 top-2 的方式來驗證這個理論上的限制的存在
- 最後他們設計一個符合現實場景的自然語言問答資料集 LIMIT 來證明即使是最先進的模型，在單一且固定維度的架構下仍然會失敗


## Representational Capacity of Vector Embeddings
假設有 m 個 query 和 n 個document，兩者的相關性所形成的矩陣 A 是 ground-truth relevance matrix
- $A_{ij}=1$代表document j 與 query i 相關，0則是無關

query embedding 儲存在矩陣 $U$，而 document embedding 儲存在矩陣 $V$，目標是找到能實現 $B=U^TV$ 的 $B$ 的最小維度是多少 (可以想見這個 $B$ 的維度會比 $A$ 小)


接下來作者定義了三個概念來表示衡量這個最小維度的限制
1. row-wise order-preserving rank : $rank_{rop}A$
- embedding model 最少需要多少維度，才能保證對每個query，相關文件都排在不相關文件之前，也就是能"排對順序"的能力
2. row-wise thresholdable rank: $rank_{rt}A$
- 對每個 query，可以找到一個"個別的"分數門檻，把相關與不相關文件分開，也就是能"分類"的能力
3. globally thresholdable rank: $rank_{gt}A$
- 所有 query 都用"同一個"分數門檻，把相關與不相關文件分開。這比row-wise thresholdable rank 的要求更嚴格

然後他們利用三一律證明了 $rank_{rop}A = rank_{rt}A$，也就是對二元標籤來說，「只要能排對順序，就一定能找到每一個query的閾值」；反過來，「只要能對每一個query設閾值，就一定能保證排序正確」。所以兩個概念其實是一樣的。
- 三一律 (trichotomy property): For any two real numbers A and B, only one of three relationships can be true (this is called the trichotomy property): A>B, A<B, A=B

透過定義一個只有{-1, +1}的矩陣M，$\operatorname{rank}_{\pm}M$ 我們一定能找到一個 rank d 的矩陣 B 使得 A 跟 B 的 sign pattern相同

最後是建立不等式
$$
\operatorname{rank}_{\pm}(2A - 1_{m \times n}) - 1
\;\leq\; \operatorname{rank}_{rop} A
= \operatorname{rank}_{rt} A
\;\leq\; \operatorname{rank}_{gt} A
\;\leq\; \operatorname{rank}_{\pm}(2A - 1_{m \times n})$$
其中 $A$ 是一個只有 {0, 1} 的 binary matrix -> $2A-1$ 代表把 {0, 1} 映射為 {-1, 1}，也就是把threshold變成0
1. 首先從剛剛證明過的 $rank_{rop}A = rank_{rt}A$，由於 $rank_{gt}A$ 的要求更嚴格，所以他的rank會大於等於其他兩個
2. 再來是右邊的 $rank_{gt}A <= \operatorname{rank}_{\pm}(2A - 1_{m \times n})$，讓 sign(B) = 2A-1 就會自然讓 B 成為一個 threshold = 0 的 gt 矩陣，而任何與矩陣B同sign rank的都能滿足這個條件。
3. 最後是左邊的 $rank(2A-1)-1 <= rank_{rt}A$，假設 B 能達成 row-threshold rank，就存在一個每一個 row 的最小 threshold 𝜏 使得當 $B_{ij}$ > $𝜏_i$ 的時候代表 $A_{ij}$ = 1，而 $B_{ij}$ < $𝜏_i$ 的時候代表 $A_{ij}$ = 0。然後你把 B 減去這個 threshold $B-𝜏1^T_n$，就等於是重新把0當成 threshold。
- 這個矩陣的sign會跟2A-1一樣，而$\operatorname{rank}_{\pm}(2A-1)$ 就是實現這個矩陣的最小所需rank，因此他會 <= $rank(B-𝜏1^T_n)$
- $rank(B-𝜏1^T_n)$ 必定 <= $rank(B)+rank(𝜏1^T_n)$ = $\operatorname{rank}_{rt}A + 1$，因為我們一開始假設了B能達成row-rank threshold，此時把1移動到左邊就可以得證

### Conclusion of Representational Capacity
最終的不等式其實是提供了一個vector embedding model的上下界，對任何的一個binary relevance matrix A，我們最少需要 $\operatorname{rank}_{\pm}(2A - 1_{m \times n}) - 1$的維度來建構關係，最多則需要 $\operatorname{rank}_{\pm}(2A - 1_{m \times n})$的維度

所以如果你的embedding model維度太低，是會有可能無法解決複雜的 retrieval問題的，他有一個數學限制在

## Empirical Connection: Best Case Optimization
知道了這個限制之後，要如何用實驗去證明他呢?

- 他們建立了一個隨機的 document matrix 和一個隨機的 query matrix 以及對應的 top-k sets (k=2)，也就是每一個 query 會有兩個正確的相關document，然後用adam + early stop + full dataset batch-size + InfoNCE loss 去訓練，就是每一次訓練的時候只有兩個文件是positive，其他都是negative，而**這裡訓練的是embedding本身，不是模型**

透過漸漸地增加文件數量 n，就可以知道每一個embedding 維度 d 會在甚麼樣的文件數量下無法對每一個 query 都算出 top-2 文件 (因為組合爆炸)，他稱這個n維 Critical n，以此畫出下圖的每一個點，在去連接點畫出這個趨勢線

for d in embedding_dimensions:
    for n in number_of_documents:
        # Create n documents and C(n,2) queries
        # Train until convergence or early stopping
        if accuracy < 100%:
            critical_n = n-1  # The limit for this dimension
            break

從圖中可知，在top-2 retrieval下，embedding 維度 d 與能處理的文件數量 n 存在某種多項式關係
多項式: $(y = −10.5322 + 4.0309d + 0.0520d^2 + 0.0037d^3)$
- 從這個多項式就可以推估出一個 embedding size=4096 的大模型只能處理2.5億個文件，而 size=1024 的小模型更是只能處理 4百萬的文件的組合

## Empirical Connection: Real-World Datasets
為了在現實世界中的問題證明這個理論，他們把組合數量轉化為自然語言，建立LIMIT資料集，這個資料集的文件中描述了每一個人喜歡什麼屬性，圖中的例子就是在問誰喜歡短尾矮袋鼠，小的版本有46個文件，如果取top-2為答案就會有 $\binom{46}{2} = 1035$ 個query，大的版本有50k個文件
- corpus: {"_id": "Geneva Durben", "title": "", "text": "Geneva Durben likes Quokkas, River Otters, Tapirs, Asymmetry, Snow Leopards, Hydrangeas, Crocheting, Symphonies, Bassoons, Pangolins, Limes, Mosaic, Creativity, Licorice, Spinach, Chairs, Horror Literature, Scuba Diving, Glaciers, Cartography, Alternative Rock, Oceanic Trenches, Barley, Cheerios, Sapphires, Parakeets, The Aztec Empire, Traveling, Candle Making, Shasta Daisies, Patterns, Disco Music, White Pepper, Slide Rules, Halibut, Giant Isopods, Praying Mantises, Fables, Alligators, Caracals, Joshua Trees, Pansies, Soy Sauce, Cards Against Humanity and Elm Trees."}
- query: {"_id": "query_0", "text": "Who likes Joshua Trees?"}
- qrels: {"query-id": "query_0", "corpus-id": "Geneva Durben", "score": 1}

短尾矮袋鼠 (Quokkas)

結果在這麼簡單的問題上，每一種模型的表現都很差
- GTE-ModernColBERT是一個多向量模型，超越了所有其他模型但還是差BM25非常遠
- 星號的模型是用單一個embedding維度去訓練的 (除了E5-Mistral 7B、GritLM 7B跟Promptriever Llama3 8B以外的模型的某些維度)

但如果不依賴在單一向量上的話就可以得到很大的提升 (尤其Promptriever是訓練在更多的embedding維度差異就更明顯)

## Experiments
### Is this Domain Shift?
有沒有可能這些模型只是沒訓練在這種類型的問題上，因此表現很差?

答案是無關，即使他們拿LIMIT資料集來訓練這些模型，他們只會直接overfit，recall@10從近乎0變成0.28

### Effects of Qrel Patterns
為了證明LIMIT資料集的相關性矩陣的密集度會影響任務的困難度，他們用四種不同的方法來建立LIMIT資料集
- random是從所有組合中抽樣
- cycle是每個新的 query 的 relevant 文件包含「上一個 query 的其中一個文件 + 下一個新文件」
- disjoint 是每個 query 的 relevant 文件和之前的 query 都 完全不重疊
- dense 就是他們的baseline，每一個query都會涵蓋到最多可能的文件組合


### Correlation with MTEB
MTEB是資訊檢索領域常見的benchmark，圖中可以發現MTEB的分數高低跟他們在LIMIT上的表現無關，這表示傳統benchmark是沒辦法測試到組合表現能力的

## Conclusion
1. 未來的benchmark應該測試模型的組合表現能力
2. 好的檢索系統需要用多種方法，而不是只依賴在一個單一向量的embedding能力上，例如 Cross-Encoder 或是 Multi-vector models (ModernBERT)，不過你也得考慮這種方法會讓模型的計算成本增加
3. 稀疏模型 (如BM25) 可以被想成一種高維度的單一向量模型，但他的組合表現能力遠超神經網路模型，只是我們該如何把它用在instruction-following和reasoning-based的任務上還是個未知問題，屬於future work

## Discussion
本篇論文真的證明了在所有embedding retrieval的案例上，模型都有一個極限在嗎?

答案是**否定的**，實際上這篇論文沒有發現任何新事物，他想闡明的只是**假設你的document跟query沒有結構性關係時，那你的模型就無法沒有極限的去model他們**，而且他們還算出了這個極限。但會有這個極限的原因是所有機器學習模型都是一種資訊壓縮的方法，你本就需要讓資料有結構性關係才能做出好的資訊壓縮，我們本來就是為了獲得更好的泛化能力以及更精簡的表現方式而放棄了原本能夠表現出任何組合的能力才會使用機器學習模型。

至於LIMIT資料集這種物件與特性之間完全隨機的組合並沒有很好的結構性關係，而且完全隨機的資料就是最困難的任務，模型在處理這種任務的時候當然是會有一個極限在的。而BM-25這種能對所有做出索引，他沒有經過資訊的壓縮，所以能在這樣的任務上表現很好。