---
# System prepended metadata

title: '論文閱讀 : On the Theoretical Limitations of Embedding-Based Retrieval'

---

# 論文閱讀 : On the Theoretical Limitations of Embedding-Based Retrieval
[On the Theoretical Limitations of Embedding-Based Retrieval](https://arxiv.org/abs/2508.21038)
## 摘要

### **論文背景與動機**

向量嵌入（vector embeddings）過去主要用於搜尋與檢索，但近年來被廣泛應用在更多複雜任務，如：

* 推理（reasoning）
* 指令遵循（instruction-following）
* 程式碼理解與生成（coding）
* 通用語意查詢與相關性判定

新型評測基準要求嵌入模型能處理「任意查詢」與「任意形式的相關性」，也就是希望 embeddings 能泛化到所有查詢情境。

---

### **研究問題**

雖然先前研究提出向量嵌入存在理論限制，但普遍存在一種假設：

> **只要查詢不是不合理的（unrealistic），模型就可以透過更大的模型與更好的訓練數據克服限制。**

本研究正式挑戰這個假設。

---

### **核心主張**

作者指出：
嵌入模型的理論限制不是只存在於不合理查詢
即使是「非常簡單、現實的查詢設定」，也會遇到這些根本限制

---

### **理論貢獻**

研究結合學習理論已知結果，證明：

> **一個 embedding 的維度，會限制 query 能返回的不同 Top-k 結果組合（subsets of documents）。**

換句話說：

* 若向量維度有限，模型能分辨與排列的文件組合數量也有限
* 當查詢變多或相關性定義多樣，必然會「撞到天花板」

特別指出：

* 即使將 k 限制成非常小的 **k = 2**
* 即使允許在測試集上直接最佳化參數（不考慮訓練過程）
  仍然會明顯受到維度限制。

---

### **實證研究**
為驗證上述理論：
1. 作者建立了一個名為 **LIMIT** 的資料集
   * 設計目的：讓嵌入模型必須面對 Top-k 子集合限制
   * 情境為「真實且簡單的任務」，不是刻意刁難
2. 實驗結果
   * 即使是目前的頂尖嵌入模型（state-of-the-art）
   * 在 LIMIT 資料集上仍表現失敗
   * 顯示限制確實存在，且並非透過更大模型或更好訓練就能輕易解決

---

### **研究意義**
目前主流「單一向量（single-vector）」嵌入架構存在根本瓶頸
此瓶頸會在真實任務中出現，而非只限於極端或理論案例
嚴重限制向量模型對「多樣查詢」與「多種相關性」的能力模式
需要新的方法或架構來突破這一限制




## Introduction

### 從 Sparse 到 Dense Retrieval**

過去二十年，資訊檢索（IR）從傳統稀疏模型（如 BM25）轉向以神經語言模型為主的架構，尤其是「單向量嵌入（single-vector embeddings）」：

* 模型將整個輸入文本編碼成 **一個向量**
* 也稱為 **dense retrieval**
* 能跨任務、跨資料集泛化
* 已被用於越來越複雜的檢索問題

### **新挑戰：指令型與推理型檢索**

近期，檢索不再只是找相似文，而是要求模型：

* 理解 **任意查詢**
* 配合 **任意定義的相關性**

例如：

| 資料集    | 挑戰型態         | 示例                                      |
| ------ | ------------ | --------------------------------------- |
| QUEST  | 組合邏輯（OR/AND） | 「找與『蛾 OR 昆蟲 OR 瓜地洛普節肢動物』相關文件」           |
| BRIGHT | 推理與任務分解      | 「給一個 Leetcode 題目，找出與其擁有相同子步驟（如 DP）的其他題」 |

這類基準測試象徵一個隱含目標：

> dense retrievers 必須有能力處理**任何可能形式的查詢與相關性定義**

---

### **本研究的核心出發點：從實驗轉向理論**

多數研究關注「能否讓模型做得更好」，透過：

* 更多資料
* 更強模型
* 更複雜訓練技巧

本論文選擇反方向：

> **不是問模型能做到什麼，而是問它根本「做不到什麼」**

因為單向量嵌入運作於幾何空間中，能利用**幾何代數與通訊複雜度理論**來推導其能力上限。

---

### **理論貢獻：嵌入維度的根本限制**

研究證明：

> 對於給定的嵌入維度 ( d )，**存在一群 Top-k 的文件組合，無論輸入什麼查詢，嵌入模型都無法把它們當成結果返回。**

也就是：

* 向量維度會限制模型可區分的「文件組合」數量
* 當文件數量變大時，可能出現某些 Top-k 結果本質上無法表示
* 這是 **數學上的限制**，不是訓練技巧或模型大小能簡單克服

---

### **實證驗證**

為了避免「可能是訓練方法不好」的爭議，作者做了極端且公平的測試設計：

#### 測試方法

* 不使用既有語料或模型
* 直接在測試集上「自由優化 embedding」
* 換句話說：**如果嵌入可以做到，那這個測試就是它的最佳情況**

#### 結果

* 仍然存在明顯分界點：
  當文件量超過某個臨界值，該維度的 embedding **無法表徵所有 Top-k 組合**
* 對不同維度 ( d ) 測試後，發現能用 **多項式函數**描述維度與容量的關係

---

### **LIMIT 資料集**

作者更進一步建構了一個真實語言資料集 **LIMIT**，內容非常簡單：

例：

* Query：`Who likes Apples?`
* Doc：`Jon likes Apples. …`

結果：

* 即使是頂尖的 MTEB 模型（例如 Gemini embedding、Qwen embedding）
* **表現極差，Recall@100 < 20**
* 低維度模型更是「理論上不可能」解決

---

## **研究貢獻整理**
1. **理論貢獻**
   * 提出單向量嵌入在 Top-k 組合表徵上的根本極限
2. **最佳情況驗證（free embedding optimization）**
   * 即使人工直接在測試集最佳化，也仍受維度限制
3. **現實語言資料集（LIMIT）**
   * 任務簡單卻仍難以被最強模型攻克



### Theoretical Bounds

本小節建立三個概念之間的理論關係：

* **Row-wise order-preserving rank** $\rank_{\text{rop}} A$
* **Row-wise thresholdable rank** $\rank_{\text{rt}} A$
* **Globally thresholdable rank** $\rank_{\text{gt}} A$

以及跟**Sign rank**之間的關係。
透過這些理論，可以建立嵌入維度的數學下界。

---

### Proposition 1：

### **對二元 relevance matrix（0/1），row-wise ordering 與 row-wise thresholding 是等價的**

$$
\rank_{\text{rop}} A = \rank_{\text{rt}} A
$$

### 證明想法

1. **如果能用 row-wise thresholding**

   * relevant > τ > irrelevant
   * 所以 relevant 一定比 irrelevant 分數高
     → 一定符合 order-preserving

2. **如果只知道 order-preserving**

   * 同一列中 relevant 的分數全部比 irrelevant 高
   * 所以一定可以找到一個 τ

     * 例如兩者中間值
       → 可轉成 row-wise thresholding

因此兩者 rank 完全相等

---

### 接下來引入 Sign Rank

### **Sign rank** 定義：

對一個只含 -1 / +1 的 matrix $M$

$$
\rank_\pm(M) = \text{最小的矩陣 } B \text{ 的 rank，使得 } \sign(B_{ij}) = M_{ij}
$$

意思是：

> B 的正負號分布與 M 完全一致
> 不管數值大小，只在意正負

---

### Proposition 2：

建立四種 rank 之間的上下界關係

---

### Step 0：將 binary A 轉成 ±1 matrix

$$
2A - \mathbf{1}_{m \times n}
$$


所以 $2A - \mathbf{1}$ 是一個 (-1, +1) 的矩陣，可以用 sign rank 來分析。

---

### Main result（非常重要）：

$$
\rank_\pm(2A - \mathbf{1}) - 1
\ \le\
\rank_{\text{rop}} A = \rank_{\text{rt}} A
\ \le\
\rank_{\text{gt}} A
\ \le\
\rank_\pm(2A - \mathbf{1})
$$

---

### 每個不等式

### **(1) $\rank_{\text{rop}} A = \rank_{\text{rt}} A$**

這就是前一個 Proposition 得到的結論。

---

### **(2) $\rank_{\text{rt}} A \le \rank_{\text{gt}} A$**

合理：
若存在一個「全球一致的門檻」能分出所有查詢的 relevant/irrelevant，
那當然也能用「每列一個門檻」。

**global threshold** 是最強限制 → 通常需要更大維度
**row threshold** 更寬鬆 → 維度不會更大

---

### **(3) $\rank_{\text{gt}} A \le \rank_\pm(2A - 1)$**

若 B 與 $2A-1$ 的正負號一致：

* B>0 → A=1
* B<0 → A=0
  所以只要 $\tau = 0$ 就能當作一致門檻

因此 sign rank 給了 **global threshold** 上界

---

### **(4) $\rank_\pm(2A-1) \le \rank_{\text{rt}} A + 1$**

這是一個技術性但很重要的界限：

* (B) 若能 row-wise threshold：

  * $B_{ij} > \tau_i$ (relevant)
  * $B_{ij} < \tau_i$ (irrelevant)
* 做一個轉換 $B - \tau \mathbf{1}_n^T$

  * 每列減掉自己的門檻
  * 讓所有 relevant 正、irrelevant 負
  * → 與 sign matrix 一致

但減去一個 rank-1 矩陣
只會讓 rank 最多增加 1

因此 sign rank ≤ row-wise threshold rank + 1




### Consequences（推論與意義）

前面一連串的證明，總結出**對向量嵌入模型而言**：

> 若要完全正確地表示某個檢索任務（用正確排序或門檻分開 relevant / irrelevant），
> 嵌入維度 (d) 必須介於以下界線：

$$
\rank_\pm(2A - \mathbf{1}) - 1
\le d \le
\rank_\pm(2A - \mathbf{1})
$$

這告訴我們：

**Sign rank 幾乎直接決定最小需要的 embedding 維度**
最多差 1（下界和上界差距最大 1 維）

---

### 實際代表什麼？

#### 結論 1：永遠會有太難的檢索任務

> **只要 embedding 維度固定為 (d)，就一定存在某個檢索任務，永遠無法用 (d)-維向量表示。**

原因：

* sign-rank 可以非常大（甚至隨文件變多而爆炸）
* 若 $\rank_\pm(2A-1) > d$，就算你想再怎麼訓練 embedding，也不可能成功

**表示嵌入模型有理論上無法跨越的天花板**

---

#### 結論 2：什麼 qrels 會很難？

> sign-rank 越高 → 表示查詢與文件之間的相關性組合越複雜 → 需要更高維度 embedding 來表示

例如：

* 查詢越多
* 文件越多
* 不同查詢對文件的排序關係越不一致

→ sign-rank 就越高
→ embedding 必須更高維

這正是 LIMIT 資料集後面會做的事情：
設計高 sign-rank 的 relevance matrix → 測試現有模型能否扛住

---

#### 結論 3：如何實際估計 sign-rank？

論文說：

> 如果你用 (d)-維 embedding 成功訓練出 row-wise 正確排序，
> 那就代表：
> $$
> \rank_\pm(2A - 1) \le d+1
> $$

也就是—
透過實際訓練（gradient descent），
就能估計某個 relevance matrix 大概需要的維度




## 5. Empirical Connection: Best Case Optimization

前面理論上已經證明：
**嵌入模型的能力受限於 sign-rank，維度不夠就永遠無法表示某些檢索任務。**

本節要回答：

> 這只是理論嗎？現實中會發生嗎？

作者用一種最極端、最偏向模型的設定，來檢驗理論是否真的成立。

---

### 核心方法：Free Embedding Optimization

目標是打造**嵌入模型的「最佳可能情況」**：

| 普通 embedding | Free embedding（本研究）         |
| ------------ | --------------------------- |
| 受到語言模型架構限制   | 完全自由，每個 query/doc 是可直接訓練的向量 |
| 受訓練資料分布影響    | 直接在測試集上最佳化（不管泛化）            |
| 儲存語言語意       | 不需要語意，只要能滿足 relevance 排序    |

> **若 free embedding 都解不了，那任何現實 embedding 模型都不可能解。**

因為它沒有任何語言或模型結構的限制
甚至直接在測試集上過擬合
若仍達不到 100% 正確 → 是硬限制，而不是訓練問題

---

### 實驗設定

1. 建一組隨機文件向量（大小 (n)）
2. 建所有 top-(k) 文件子集合作為查詢
   * 若 (k=2)，查詢數量 = (\binom{n}{2})
   * 每個查詢標記哪些文件是 relevant
3. 使用 Adam 直接訓練查詢向量與文件向量
4. Loss：**InfoNCE**（效果最好）
5. 所有文件都當 in-batch negatives
6. 向量每次更新後都正規化（符合真正 embedding 慣例）
7. 若 1000 step 沒進步 → early stop
8. 對每個 embedding 維度 (d)，逐漸增加文件數量 (n)，直到訓練**無法達到 100% 正確**

這個「模型無法再完成所有排序需求」的最大 (n)，稱為：

> **critical-n**

意思是：
某個維度 (d) 最多能分辨多少文件的所有 top-(k) 組合
---

### 實驗結果

實驗畫出：
「embedding 維度 (d)」 vs 「可容納的最大文件數 critical-n」

結果：

取前幾個小 d 進行測試
擬合出 3 次多項式：

$$
y = -10.5322 + 4.0309d + 0.0520d^2 + 0.0037d^3
\quad (r^2 = 0.999)
$$

其中 (y) = critical-n

代表關係非常吻合。

---

### 外推到常見 embedding 維度

| embedding 維度 (d) | critical-n（模型最多能處理的文件數） |
| ---------------- | ----------------------- |
| 512              | 500,000                 |
| 768              | 1,700,000               |
| 1024             | 4,000,000               |
| 3072             | 107,000,000             |
| 4096             | 250,000,000             |

---

### 重要啟示

即使在「作弊設定」：

* 自由 embedding（不是語言模型）
* 直接訓練在測試集
* 全批次訓練
* 最佳 loss、最佳優化器

仍然出現「維度不夠就無法解決」的 critical-n 界限。

這意味著：

> **embedding 不是怎麼訓練都能變強的，它受數學限制。**

尤其在 **web-scale search**（數百萬到數十億文件）：

* 512 / 768 / 1024 維根本不夠容納所有可能的 top-k 組合
* 即使 4096 維（已是極大型 embedding），仍遠遠不足處理真實網路規模


## 6. Empirical Connection: Real-World Datasets

前面做的「free embedding」實驗證明：
**嵌入維度存在實際且可觀察到的能力上限**

但那畢竟是理論化、抽象的設定。
本節要回答兩件事：

1. 這對現實世界的 embedding 模型有什麼影響？
2. 是否真的能做出一個「看起來很簡單但實際上 embedding 無法解」的任務？

---

### 6.1 現有資料集的問題：太少 query → 看不到限制

大部分 IR（Information Retrieval）資料集：

* 採用固定的 evaluation set
* query 數量通常很少
* 原因：人工標註 relevance 很貴

**這代表什麼？**

> 評估資料集只測試了整體可能查詢空間的一小小小部分

---

### 用 QUEST 做例子

* 文件數：325,000
* 每個查詢有 20 個相關文件
* 只有 3,357 個查詢

但從理論角度看：

> 所有可能的 top-20 文件集合數量是：

$$
\binom{325,000}{20} \approx 7.1 \times 10^{91}
$$

這數字：

大於整個可觀測宇宙的原子數量（約 (10^{82})）

也就是：

* 現在測的 3,357 個 queries
* 和可能存在的 query space 比起來微乎其微
* 完全不足以暴露 embedding 模型的能力天花板

---

### 為什麼資料集會這麼少 query？

不是因為「沒有更多可能查詢」
而是：

* 人工標 relevance 成本太高
* 算 recall / ranking 太花計算資源

換句話說：

> **現有 benchmark 沒有測到 embedding 會失敗的地方，只是因為沒人去測**

不是因為 embedding 沒有限制。

---

### 真正的使用者會做什麼？

使用者可任意組合條件，例如：

| 查詢類型  | 例子                                       |
| ----- | ---------------------------------------- |
| OR 問題 | "Novels from 1849 OR George Sand novels" |
| 多條件組合 | BrowseComp 中一條 query 有 5+ 條件，還有範圍運算      |

只要文件內容夠豐富，就能形成任意 top-(k) 組合。
因此：

使用者會觸發複雜組合
但 benchmark 通常只測一小部分
所以 embedding 的 failure zone 被隱藏了

---

### 作者的策略：反其道而行

既然大規模資料集無法枚舉所有組合，那就換方向：

選 **少量文件**
產生 **所有 top-k 子集合**
不用複雜語意，不用邏輯運算

> 單純看 embedding 能否表示所有可能的 relevant 組合

因為：

* 若 embedding 理論上無法表示所有組合
* 即使 query、語言、資料再簡單
* 模型仍會失敗

這正是 LIMIT 的設計哲學：

> 文件和查詢可以非常簡單，但「組合複雜度」會壓垮 embedding




### 6.2 The LIMIT Dataset

本節目標：

1. 把「高 sign-rank、組合爆炸」的 qrel matrix，做成真實的自然語言檢索任務
2. 測試真正的 SOTA embedding models
3. 證明：**不是語言困難，而是嵌入維度受限**

---

### Dataset Construction

#### 目標

希望 query 和 document 都是自然語言，
但底層邏輯仍是「所有 top-k 組合要求都要被模型區分」。

因此挑選了一種非常簡單、自然的表達方式：

文件 = 一個人的名字 + 他喜歡的東西
查詢 = “Who likes X?”
例：

| Document | Text                                         |
| -------- | -------------------------------------------- |
| D1       | “Jon likes Hawaiian pizza, sushi, Ferraris…” |
| D2       | “Maria likes Marvel movies, cats, tacos…”    |

| Query | Text                        |
| ----- | --------------------------- |
| Q     | “Who likes Hawaiian pizza?” |

→ Relevant = 所有喜歡 Hawaiian pizza 的人 → 2 個
→ 非 relevant = 其他所有人

這種設定非常直覺、語言簡單、零推理、零邏輯難度。

---

#### 建立屬性清單

* 用 LLM (Gemini 2.5 Pro) 生成大量「人可以喜歡的東西」
* 之後不斷清理：

  * 移除重複、同義、過大概念
  * 用 BM25 檢查語意重複
* 最終得到 1,850 個可使用的「喜好項目」

---

#### 文件與查詢量

* **50,000 documents**
* 每個人喜歡 ≤ 50 個東西（保持文件短小、自然）
* **1,000 queries**
* 每一個 query 都有 **2 個 relevant 文件**（k=2）
* 與前面理論一致：希望檢驗所有 top-2 組合

---

#### 重要：如何選 qrel matrix？

研究者希望：

* qrel matrix 要包含**最多的不同 top-2 文件組合**
* 形成難度最大的 sign-rank

組合數 = (\binom{n}{2})

因此選：

* n = 46
* (\binom{46}{2} = 1035)（> 1000 queries）

這代表：

每個 query 對應一個 top-2 文件組合
1,000+ 個組合全部要被模型分開
sign-rank 高、維度需求高
embedding 模型將暴露其能力上限

---

#### 怎麼讓語言化成立？

1. 對 1,000 個 queries，每個 query 取一個自然語言屬性（X）
2. 找兩個文件，把屬性 X 加進去 → 它們成為 relevant
3. 每份 document 都會有一些隨機屬性
4. 為避免不公平，每個文件都補到相同屬性數量
5. 多數文件對所有 query 都是 non-relevant（很像真實世界）

最後還做了一個「small version」：

* 只保留 46 個 relevant documents
* 測試模型在非常小的語料庫是否也會失敗

---

### 模型測試 (Models)

測 SOTA embedding models
（Embedding 維度約 1024–4096）

* GritLM
* Qwen3 Embeddings
* Promptriever
* Gemini Embeddings
* Snowflake Arctic
* E5-Mistral

也測 **非單向量模型**：

* BM25（稀疏、詞袋法、超高維度）
* gte-ModernColBERT（multi-vector 模型）
* Token-wise TF-IDF（保證 100%）

也測縮小維度（MRL truncation）來看維度影響。

---

### 結果
![image](https://hackmd.io/_uploads/Byq-HsJxZg.png)

#### Full LIMIT dataset（50k docs）
* 多數 embedding 模型：Recall@100 < 20%
* 幾乎完全失敗
* Multi-vector（ColBERT）好一點，但遠遠不夠
* BM25 幾乎接近完美（因為稀疏表示維度極高）
語言簡單
只有「喜歡吃什麼／喜歡什麼東西」
沒有推理、沒有邏輯、沒有歧義
仍然放倒 SOTA Embeddings

---

#### Small LIMIT（46 docs）
![image](https://hackmd.io/_uploads/HJG7HsJxWl.png)

* 只剩 46 文件，幾乎玩具級資料集
* 但 embedding 模型依然做不好
* 即使 Recall@20（找前 20 個答案），仍無法保證全部 relevant 文件被找出

➡ **即使是 46 個文件，向量維度仍不夠把所有 top-2 組合分開**

---

#### 越高維度 → 越好

* 隨著 embedding dimension 增加，表現慢慢變好
* 但沒有任何單向量 embedding 能真正「解決任務」
* 多向量模型做得比較好（因為本質上維度更高）
* 稀疏模型（BM25）最好，因為 token space 非常大（極高維隱向量空間）


### 6.3 Is this Domain Shift?（是否只是領域差異造成的）

LIMIT 的結果很震撼：
語言簡單、邏輯簡單、文件短小、查詢直白
但 SOTA embedding 模型仍然崩潰。

研究者提出一個可能的疑問：

> 會不會不是 embedding 本身能力不足，而是「模型沒看過這種語料」？
> （也就是 **domain shift**）

如果是 domain shift：

用 LIMIT 的訓練資料微調模型
→ 應該會顯著改善

但如果是 embedding 的內在限制：

就算用同領域資料訓練
→ 表現仍然非常差
→ 唯有直接對 test set 過擬合才成功

---

### 實驗方法

挑一個現成 embedding 模型：

* `lightonai/modernbert-embed-large`

在三種情況下微調：

| 微調方式                     | 預期結果                      |
| ------------------------ | ------------------------- |
| 用 LIMIT 的 training set | 若是 domain shift → 應該會大幅提升 |
| 用 LIMIT 的 test set     | 若是維度限制 → 只能靠過擬合才成功        |
| 用不同維度                  | 看 embedding 維度是否影響結果      |

訓練細節：

* 采用 SentenceTransformers
* 全批次 in-batch negatives（排除正樣本）
* 把最後隱層投影到指定 embedding dimension（而非用 MRL）

---

### 結果

![image](https://hackmd.io/_uploads/H1QGUoylbx.png)


#### fine-tune 在 training set

* 模型**幾乎沒有變好**
* recall@10 從 ≈0 → 最多 2.8
* 遠遠不夠解決任務

➡ **證據：失敗不是因為 domain shift**
➡ 模型即使看到同類型語言，也無法學會所有 top-2 組合

---

#### fine-tune 在 test set

* 模型**立刻學會任務，成功過擬合**
* 意味著：

  * 知道答案時，它可以硬記
  * 但無法泛化

這與前面 free embedding 一樣：

* 若直接對 test set 最佳化，低維也能記住
* 但若要真正學會「所有可能組合」，維度不夠 → 無解

---

#### 關鍵觀察：真實模型比 free embeddings 更弱

在 free embedding 實驗中：

* (N = 46) 文件版本
* 只需要 **12 維** 就能過擬合

但用真正的 transformer-based embedding：

* 甚至 **64 維** 都無法完全解決

➡ 真實模型受更多限制：

* 語言建模結構
* tokenization
* 訓練方式
* 表示分配不均
* 非線性約束

這證明：

> 現實中的 embedding 比「自由向量」還弱
> 嵌入限制更嚴重
> sign-rank 導致的瓶頸甚至更快出現



### 6.4 Effects of Qrel Patterns（Qrel 組合模式的影響）

作者前面已經強調：**LIMIT 的困難來自於它測試了大量 top-k 組合**，使 qrel matrix 高度稠密、組合爆炸。

這一節要做驗證：

> 如果我們把 qrel 的組合減少，會不會變得容易？

#### 實驗設置

保持所有條件與 LIMIT 一樣：

* 50,000 documents
* 1,000 queries
* top-2
* 自然語言建構相同

唯一改變：**qrel 組合模式**

| 模式 | 說明 |
| ------------------ | -------------------------------------------- |
| **1. random** | 從所有組合中隨機取樣 top-2 檔案集合 |
| **2. cycle** | 每個 query 的兩個 relevant 文件與前一個 query 有連接（依序輪替） |
| **3. disjoint** | 每個 query 都用不同新檔案 → 組合互不重疊 |
| **4. dense（主要版本）** | 使用最多組合、所有 (\binom{n}{2}) 覆蓋 |

#### 結果
![image](https://hackmd.io/_uploads/B1BDDsygbg.png)

* random / cycle / disjoint：表現相對相似、沒有太難
* **dense：表現崩壞**

例子：

| 模型 | 非 dense 版本 recall@100 | dense recall@100 |
| ---------- | --------------------- | ------------------------------ |
| GritLM | 高很多 | **掉 50 個 absolute recall@100** |
| E5-Mistral | 40.4 | **4.8（幾乎 10 倍下降）** |

證明 LIMIT 的難不是語言難
是因為它涵蓋了最多的 top-k 組合，導致嵌入維度不夠區分

---

### 6.5 Correlation with MTEB（與 MTEB 的關係）

人們常說 embedding 模型「過度擬合 BEIR/MTEB”
→ 那麼，LIMIT 做不好是否說明模型只是不擅長新資料集？

作者檢驗：

* 把模型在 LIMIT 與 BEIR 的分數做散點圖（Figure ~\ref{fig:mteb_vs_limit}）

### 結果
![image](https://hackmd.io/_uploads/SyB9Pj1x-e.png)

* **幾乎沒有相關性**
* 在 BEIR 很好 → 不代表在 LIMIT 也好
* 在 LIMIT 很差 → 不代表 BEIR 差
* 小 embedding 的模型（如 Arctic）在兩邊都弱（因為維度小＋知識少）

➡ LIMIT 不只是 “不同領域”
➡ 它測的是 **維度容量限制**，不是領域差異

---

### 6.6 Alternatives to Embedding Models（替代方案）

核心發現：

> 單向量 embedding 無法表示所有 top-k 組合
> 即使維度增到 4096，也遠遠不夠涵蓋真實世界規模

所以必須考慮其他架構。

---

#### A. Cross-Encoders（重排模型 / rerankers）

特點：

* 讀入 query 和 document 完整文本
* 不是向量點積，而是直接模型判斷匹配度
* 表達能力遠大於 embedding
* **但計算昂貴**，無法做大規模 first-stage retrieval

#### 實驗（small LIMIT）

給 Gemini-2.5-Pro：

* 全部 46 documents
* 全部 1000 queries
* 一次 forward pass 直接輸出所有答案

100% 正確
完全解決 LIMIT
但計算開銷龐大，不適合百億文件的第一階段檢索

---

### B. Multi-vector Models（如 ColBERT）

* 每個 document 是多個向量，而不是一個
* 用 MaxSim 聚合匹配
* 表達能力更強

結果：

* 在 LIMIT 上明顯優於單向量模型
* 但仍離百分百很遠
* 且尚不確定能否遷移到推理 / 指令跟隨型任務

---

### C. Sparse Models（如 BM25、TF-IDF）

* 可看成「稀疏但超高維 embedding」
* 隨著詞表大小，上萬~上百萬維
* 因為維度極大，所以能表示大量組合
* 在 LIMIT 中幾乎滿分

弱點：

* 依賴字面重疊（lexical match）
* 無法處理語意、推理、同義詞或複雜任務
* 難接到指令/推理型 IR



## **6. 結論（Conclusion）**

本研究提出 LIMIT 資料集，用來揭示 **單向量嵌入模型（embedding models）** 在理論與實務上的根本侷限。

### 主要貢獻

1. **理論貢獻**

   * 透過 sign-rank 與矩陣階數的關係，我們證明：

     > *嵌入模型若維度不夠，就無法表示所有 top-𝑘 文件組合。*
   * 換句話說，若查詢的相關文件組合過於多樣、相互交錯，其關聯無法被有限維度的向量空間完整表達。

2. **經驗驗證**

   * 我們直接對查詢與文件向量做「最佳情況」的自由優化（free embedding）
   * 即便如此，仍出現明確臨界點（critical-n）——當文件數超過某門檻，即使直接訓練向量也無法達到 100% 正確率
   * 验證理論限制真實存在

3. **實務連結**

   * 我們提出 LIMIT：一個語言極度簡單、無推理需求、純粹測試組合能力的自然語言資料集
   * 最先進的 SOTA 嵌入模型（即便 embeddings 維度大、受過指令類訓練）仍無法解出此任務
   * 即使文件只有 46 個，模型仍做不到完美召回

**核心結論：**

> 嵌入模型可以處理很多組合，但無法處理「所有」組合。
> 隨著 instruction-based retrieval 興起，這個限制會越來越明顯。

---

## **研究限制與未來方向**

### 1. 理論目前主要適用於「單向量」嵌入模型

* 我們的結論目前最適用於單向量 dense embeddings
* 多向量模型（如 ColBERT）與稀疏模型（如 BM25）表現更好
* 但其理論界限仍待未來研究擴展

### 2. 尚未處理「允許部分錯誤的情況」

* 本研究探討的是「必須完美區分所有 top-𝑘 組合」
* 如果允許模型只需涵蓋大部分組合、或允許小比例錯誤
  → 仍沒有明確的理論界線
* 該方向留待後續研究（作者亦提到 Ben-David 等人 2002 的相關工作）

### 3. 無法事先預測「哪一類任務必定會失敗」

* 雖然理論證明 *一定存在* 無法被表示的任務
* 但目前無法事先指出哪些任務一定失敗
* 代表：

  * 有些推理或指令檢索可能仍能完美解決
  * 但也一定存在永遠無法處理的任務
