---
# System prepended metadata

title: "論文閱讀 :ColBERT: E\x80icient and E\x80ective Passage Search via Contextualized Late Interaction over BERT"

---

# 論文閱讀 : ColBERT: E€icient and E€ective Passage Search via Contextualized Late Interaction over BERT

## 摘要
### **1. 研究背景（Background）**

* 近期 **自然語言理解（NLU）** 的進展，帶動了 **資訊檢索（IR）** 的快速發展。
* 最主要的突破來自於 **使用深度語言模型（LMs，例如 BERT）微調用於文件排序（document ranking）**。
* 雖然效果非常好，但 **BERT-based ranking 模型的計算成本極高**：

  * 每一筆 *query–document pair* 都必須經過一次大型神經網路
  * 這讓效能較傳統 IR 模型高，但成本高出 **數個數量級（orders of magnitude）**

---

### **2. 問題（Problem）**

* 雖然 BERT 排序模型精準，但它無法效率地處理大量文件：

  * 每個文件都要與 query 一起輸入模型 → **無法預先計算文件向量**
  * 導致 **延遲高、成本高、不可擴展**

---

### **3. 研究貢獻：ColBERT（方法核心）**

論文提出 **ColBERT**，一種專門為「高效檢索」設計的 ranking 模型。

#### **(1) Late Interaction 架構**
* ColBERT 將 **query** 與 **document** 分開、獨立地用 BERT 編碼（encode）
* 之後才做一個 **廉價但強大的 late interaction 步驟**
  * 用於捕捉 query 與 document 的 **細粒度（fine-grained）相似度**

#### **(2) 關鍵優勢：延遲但保留細粒度交互**

* 雖然互動步驟延後（late interaction），但仍保留：

  * token-level granularity（比向量平均更細）
  * 深度模型表徵能力（expressiveness）

#### **(3) 預先計算（pre-computation）能力**

* 因為文件不需要與 query 一起進模型：

  * document embeddings 可以 **離線預先計算**
  * 查詢階段只需：

    1. 計算 query representation
    2. 做輕量交互

→ **顯著提升查詢速度**

---

### **4. 更多優勢（Efficiency Contributions）**

#### **(1) 節省 re-ranking 成本**

* 比起傳統 BERT re-ranker
* ColBERT 的 inference 成本低得多
  （原因：document embeddings 可離線、interaction 成本更低）

#### **(2) 支援 end-to-end 檢索**

* ColBERT 的 interaction 是 **可修剪（pruning-friendly）** 的
* 使其可以直接配合 **向量相似度索引（vector-similarity index）**
* 不需要 BM25/passage retrieval，再 rerank
  → **可以直接從大型資料庫做端到端檢索**

---

### **5. 實驗結果（Evaluation）**
* 使用兩個最新的 passage search datasets 評估
* 結果顯示：

#### **(1) 效果（Effectiveness）**
ˇ
* ColBERT 的效果：

  * **與現有 BERT-based 排序模型相當**
  * **優於所有非 BERT baseline**

#### **(2) 效率（Efficiency）**

* 查詢速度：快 **兩個數量級（100×）**
* 需要的 FLOPs：少 **四個數量級（10000×）**



## Introduction
![image](https://hackmd.io/_uploads/rJaeRRYlbl.png)
![image](https://hackmd.io/_uploads/BJwUACKxWg.png)

### 1. **背景：神經排序模型的崛起**

近年來，資訊檢索（IR）領域出現大量神經排序模型，例如：

* DRMM
* KNRM
* Duet 系列

這些模型的特色是：

* 不依賴手工特徵（hand-crafted features）
* 使用 **embedding-based 表示法** 來建模 query 與 document
* 能直接捕捉 **local interactions（詞彙層級的細粒度關聯）**

進一步地，研究界開始將 **深度語言模型（ELMo、BERT 等）微調**來評估查詢與文件的相關性，提供：

* 深度上下文化的語意表示
* 解決 query-document 的 vocabulary mismatch 問題
  （如使用者查詢用的詞與文件使用的詞不同）

這類基於 BERT 的 ranking 模型迅速達到 SOTA，並已被 Google 與 Bing 部署。

---

### 2. **問題：BERT 雖強大，代價十分昂貴**

雖然 BERT 在檢索效果上大幅領先，但其計算成本極高：

* 與傳統方法相比，**昂貴 100 到 1000 倍**
* 必須把 **每個 query–document pair** 都傳入 BERT 模型
* 基於 transformer 的互動式架構需要大量計算

論文引用測試（MS MARCO Ranking）顯示：

* BERT 讓 MRR@10 提升約 **7%**
* 但讓 query latency 增加到 **數萬毫秒（tens of thousands ms）**

這對搜尋引擎是嚴重問題：

* query latency 增加 100ms 就會影響 user experience 與收入

---

### 3. **現有嘗試：NLU + 傳統模型（BM25）**

為降低 BERT 成本，有些研究用 NLU 技術輔助 BM25，例如：

* doc2query：用生成模型擴增文件
* 用 NLU 預測 term importance 取代傳統 TF

這些方法確實降低 latency，但 **精準度比 BERT 弱許多**。

---

### 4. **提出方法：ColBERT = contextualized late interaction over BERT**

論文提出 **ColBERT**，核心理念是：

> 結合「細粒度互動式模型」的強大語意能力
> 與「表示式模型」的高效率
> 透過 **延遲互動（late interaction）** 同時達成效果與效率

#### **Late Interaction 概念**

1. Query（q）與 Document（d）**分開**由 BERT 編碼
2. 得到各自的一組 contextual embeddings（token-level 表徵）
3. 之後再以 **低成本且能 pruning 的互動運算** 計算關聯性

這樣可以：

* 保留細粒度 token-level matching 的優點
* 又能讓 document embeddings **離線預計算**

---

### 5. **與既有架構的比較：四種 Neural Matching Paradigms**

論文用 Figure X 對照四類模型：

#### (a) Representation-focused（向量化、整體式）

* q、d 各編碼為單一向量
* relevance = similarity(q, d)
* 好處：文件可離線編碼 → 快
* 壞處：失去細粒度語意互動能力

#### (b) Interaction-focused（互動式）

* 基於詞彙互動矩陣（interaction matrix）
* 交由 CNN / MLP / kernels 計算
* 細粒度高 → 成效較好
* 但要即時處理 q×d 全對映 → 成本高

#### (c) Deep interaction（transformer-based，如 BERT cross-encoder）

* 最強的互動能力
* 完整建模 q、d 內與跨句子 token interactions
* 但需每個 pair 都跑一次 BERT → 最昂貴

#### (d) ColBERT（Late Interaction）

* q embeddings 與 d embeddings 互動
* 用 **MaxSim**（逐 token 最大相似度）運算
* 互動延遲 → 可先編 d
* 維持大量細粒度 signal、便於加速與修剪

ColBERT 結合：

| 屬性                        | 又有                     |
| ------------------------- | ---------------------- |
| Representation-based 的高效率 | ✓ 文件可預先編碼              |
| Interaction-based 的高精準度   | ✓ token-level matching |

---

### 6. **Late Interaction 的能力：支援向量搜尋（vector similarity index）**

ColBERT 的 MaxSim 互動方式：

* 是「可修剪」、「高效率」的
* 能直接配合向量相似度索引庫（例如 FAISS 類似索引）

→ 能直接從數百萬文件中做 **end-to-end retrieval**

這比只做 re-ranking 的模型更能提高 recall。

---

### 7. **效能 & 實用性（從 Figure tradeoff）**

ColBERT 的效能表現：

* 查詢延遲在 **幾十到幾百毫秒**
* re-ranking 模式下：

  * **170×** 速度提升
  * **14,000×** 減少 FLOPs
* 文件編碼 9M passages：

  * 在單機 4 GPU，僅需 **3 小時**
* 空間成本只需要數十 GiBs
* 維持 BERT-level effectiveness

---

### 8. **大量 ablation study 的結果**

研究發現：

* **late interaction 設計本身**
* **MaxSim 運算**
* **BERT 編碼器的特定設計選項**

都是 ColBERT effectiveness 的關鍵。

---

### 9. **主要貢獻（Contributions）**

1. **提出 Late Interaction paradigm**
   用於高效且有效的 neural ranking。

2. **提出 ColBERT 模型**
   使用 BERT-based query/document encoders
   完整實作 late interaction。

3. **示範兩種使用方式**

   * 作為 re-ranker（搭配 BM25 等傳統檢索）
   * 作為 end-to-end vector retrieval（直接查整個庫）

4. **在 MS MARCO 與 TREC CAR 上完成全面實驗**
   展示 ColBERT 的速度與效果優勢。


## method

---

### **1. ColBERT 的核心目的**

ColBERT（Contextualized Late Interaction over BERT）是一個在「效果」與「效率」間取得平衡的 IR 模型。其核心思想：

* **延遲（delay） query–document interaction**
* 使文件向量可以 **離線預算（pre-compute）**
* 查詢階段執行「便宜又可修剪」的互動運算
  → 可支援 **高效 re-ranking**
  → 也可支援 **大規模端到端向量檢索**

重點是：
即使 delay interaction，仍能保留類似 BERT cross-encoder 的細粒度效果。

---

### **2. 架構概述（Architecture）**

ColBERT 的整體架構（Figure: ColBERT-Framework-MaxSim）包含三個部件：

1. **Query encoder**：$f_Q$
2. **Document encoder**：$f_D$
3. **Late interaction module**（MaxSim-based relevance）

給定 query $q$ 與 document $d$，ColBERT 會：

* 用 $f_Q(q)$ 將 query 編成 **embedding bag**：
  $$
  E_q = { e_{q1}, e_{q2}, \dots }
  $$
* 用 $f_D(d)$ 將文件編成另一 embedding bag：
  $$
  E_d = { e_{d1}, e_{d2}, \dots }
  $$

這些 embeddings 都是 **contextualized**（透過 BERT encoder）。

---

# **3. Late Interaction（MaxSim）機制**

ColBERT 的 relevance score 基於：

### **對每個 query token embedding $v \in E_q$**

* 在整個文件 embedding bag $E_d$ 中找：
  $$
  \max_{u \in E_d} , \text{cosine}(v, u)
  $$

### **最後將所有 query token 的最大相似度加總：**

$$
\text{score}(q,d) =
\sum_{v \in E_q}
\max_{u \in E_d} \text{cosine}(v, u)
$$

研究也評估了 **L2 distance** 作為替代（但 cosine 是主要）。

直觀理解：

* 每個 query token $t_q$ 會「搜尋」文件中最相關的 token embedding
* 最大相似度代表「最強匹配 evidence」
* 全部 query tokens 的匹配 evidence 加總 → 文件的最終分數

### **特性：**

1. **非常便宜（cheap）** 的互動運算（比 CNN、attention 等輕很多）
2. **高度可 pruning（適合向量搜尋）**
   因為不需要完整 q×d interaction matrix

---

# **4. 比其他互動方法的優勢**

雖然更複雜的互動方式（CNN、attention）可用，但 MaxSim 有兩大優點：

* 計算成本很低（FLOPs 小）
* 更容易透過 vector-similarity indexes 做 **top-k pruning**
  （不需逐個計算每份文件的完整互動矩陣）

論文的 ablation（在後面的實驗節）驗證：

* MaxSim-based late interaction 的確明顯優於其他替代設計

---

# **5. Query & Document Encoders**

ColBERT 使用同一個 **BERT 模型**，但用不同的特殊 token 來區分：

* Query： **[Q]**
* Document： **[D]**

免去多模型訓練的負擔，但仍讓模型意識到不同種類的輸入。

---

## **5.1 Query Encoder**

### **(1) Tokenization**

* 將 query 拆成 WordPiece tokens：
  $$
  q_1, q_2, \dots, q_l
  $$
* 在 BERT 的 [CLS] 後面插入 [Q] token
* 若長度不足 $$N_q$$，填充 **[mask] tokens**
* 若超過 $$N_q$$，截斷

### **(2) Query augmentation**

* 透過 [mask] padding，讓 BERT 為填充位置產生 contextual embeddings
* 這提供了一種 **可微、可學習的 query expansion 或 term weighting 機制**

論文指出：
→ Query augmentation 是 ColBERT effectiveness 的關鍵。

### **(3) 線性壓縮層（dimension reduction）**

* 將 BERT hidden size（768）壓縮成較小維度 (m)
* 無 activation
* 目的：

  * **控制文件向量的空間成本**
  * 減少從 CPU → GPU 的傳輸成本

### **(4) Normalization**

* 將輸出 embeddings 做 L2 normalize
  → dot-product = cosine similarity，範圍 [-1, 1]

---

## **5.2 Document Encoder**

Document encoder 與 query encoder 類似，但有以下差異：

1. 文件前置 token：

   * [CLS]
   * [D]

2. 文件 **不使用 [mask] 填充**（避免不必要擴增）

3. 文件 embeddings 會經過 **punctuation filtering**

   * 刪除標點符號的 embeddings
   * 目標是減少 document embedding 數量
   * 論文假設 punctuation embeddings 對排序無效

---

# **6. Encoder 總結（公式）**

給定：

* Query tokens：$q_0, q_1, ..., q_l$（含 [Q]）
* Document tokens：$d_0, d_1, ..., d_n$（含 [D]）
* # 表示 [mask] tokens

ColBERT 的 encoder 表示如下：

### Query embedding bag:

$$
E_q := \texttt{Normalize}(
\texttt{CNN}(
\texttt{BERT}([Q] ~ q_0 ~ q_1 ~ \ldots ~ q_l ~  \ldots)
)
)
$$

### Document embedding bag:

$$
E_d := \texttt{Filter}(
\texttt{Normalize}(
\texttt{CNN}(
\texttt{BERT}("[D] ~ d_0 ~ d_1 ~ \ldots ~ d_n)
)
)
)
$$

（備註：公式中的 CNN 其實是線性層 + normalization 的統稱，並非 convolution）




## ColBERT：Late Interaction

---

### **1. Late Interaction（延遲互動）**

給定：

* Query 的 contextualized embeddings：$E_q$
* Document 的 contextualized embeddings：$E_d$

ColBERT 定義 relevance score $S_{q,d}$ 為：

$$
S_{q,d} := \sum_{i \in [|E_q|]} \max_{j \in [|E_d|]} E_{q_i} \cdot E_{d_j}^{T}
$$

特點如下：

#### **(1) interaction = MaxSim（最大相似度）**

* 每個 query token embedding 與全文件 embeddings 做相似度比較
* 取最大 cosine similarity（因為 embeddings 已 L2 normalize）
* 對所有 query tokens 加總

#### **(2) 沒有 trainable parameters**

* MaxSim 本身不是可學的層（non-parametric）
* 整個互動機制是昂貴 BERT cross-encoder 的高效替代

---

### **2. Training（訓練方式）**

ColBERT 是 **端到端可微分（differentiable end-to-end）** 的。

#### **(1) 參數更新的部分**

訓練時會更新：

* BERT encoder（fine-tuning）
* 線性降維層（linear layer）
* 特殊 tokens 的 embedding：

  * [Q]
  * [D]

注意：

* Late Interaction（MaxSim）沒有參數，不需學習。

---

#### **(2) Loss：Pairwise softmax cross-entropy**

給定訓練三元組 ：

$$
\langle q, d^+, d^- \rangle
$$

對正樣本與負樣本分別計算 score：

* $S_{q,d^+}$
* $S_{q,d^-}$

再以 **pairwise softmax cross-entropy** 最小化：

* 使模型偏好 $d^+$
* 排斥 $d^-$

這種做法跟 RankNet / pairwise ranking 類似。

---

### **3. Offline Indexing：文件向量的離線編碼**

ColBERT 的設計讓：

* 幾乎所有 document encoder 計算都可 **離線完成**
* 查詢階段只需：

  * 編 query
  * 用 MaxSim 做快速比對

#### Offline indexing 流程：

#### **(1) 文件批次處理**

* 將文件分批（利用 GPU）
* 對每一批跑 document encoder $f_D$
* 輸出 document embedding matrices

#### **(2) Padding 調整與 sequence length 限制**

* 在一個 batch 內，只 pad 到「該 batch 中最長文件」
  → 避免全 corpus 用固定長度 pad 造成浪費
  → 比 public BERT implementation 更有效率

#### **(3) Bucketing（依文件長度排序）**

* 將文件分成群組（例如 B=100,000）
* 每群組內排序文件長度
* 再分成小批次（例如 b=128）送入 GPU
  → 減少 padding 浪費，提高 throughput

#### **(4) CPU 前處理並行化**

WordPiece tokenization 非常耗時
→ ColBERT 將其分散到多個 CPU core 並行加速

#### **(5) Embeddings 儲存格式**

* embeddings 可用 float32 或 float16 儲存
* 儲存後即可：

  * 直接重新載入 re-ranking
  * 或給 vector-similarity index（如 FAISS）使用

---

### **4. Top-k Re-ranking（小規模 re-ranking）**

適用於：

* 有一小批候選文件（如 BM25 top-1000）
* 需高品質 re-ranking

流程如下：

#### **(1) 預載文件 embeddings**

* 將離線 index 的文件 embeddings 載入記憶體
* 每份文件為 matrix（大小：#tokens × embedding_dim）

#### **(2) 构建 3D tensor**

* 給定 query q，計算：
  $$
  E_q
  $$
* 同時把 k 份候選文件整理為 3D tensor (D)：

$$
D \in \mathbb{R}^{k \times L \times m}
$$

（L = 文件 padding 後長度，m = embedding dimension）

並傳到 GPU。

#### **(3) GPU 上做 batch dot-product**

對所有文件和 query embeddings 做矩陣比對（批次運算）：

* 大幅快於逐份文件跑 BERT
* 得到 cross-match 矩陣（query tokens × doc tokens）

#### **(4) MaxSim + summation**

對每份文件：

1. 對 document token 維度做 max-pool（MaxSim）
2. 對 query token 維度加總（sum）

得到每份文件的 score。

#### **(5) 排序取前 k**

依 score 排序即可。

#### **為何超省？**

BERT cross-encoder 會：

* 將每份 (q, d) 拼接後投入 BERT
* Attention 成本 ≈ O$(|q|+|d|)^2$

ColBERT：

* 只跑一次 BERT（query encoder）
* 文件已離線編碼
* GPU 上只做 dot-product

→ 速度快許多、scale 到更大 k

---

### **5. End-to-end Top-k Retrieval（大型語料庫搜索）**

適用於：

* 文件量非常大（如 10M documents）
* 不能逐個文件做 MaxSim

ColBERT 的關鍵在於：

#### **MaxSim 是 pruning-friendly**

允許透過向量搜尋取代暴力全文件比對。

---

### **End-to-end Retrieval 流程**

#### **(1) 離線建索引：把所有文件 embeddings index 進 FAISS**

每個 document embedding 都會：

* 存成一條向量
* 維持 mapping：embedding → document ID
* 用 FAISS 建立大型向量索引（IVFPQ）

---

### **(2) Query search：兩階段 retrieval**

#### **Stage 1 — approximate filtering（近似過濾）**

對 query embeddings $E_q$ 中的每個 embedding：

* 在 FAISS 中做 vector similarity search
* 取得 top-(k') 相似的 document embeddings

例如：

* (k = 1000)
* (k' = 500)（每個 query token 找 500 個）

再將這些結果：

* 映射到對應 document IDs
* 合併、去重，得到最多 (N_q \times k') 個候選文件

這些文件 **高機率** 與 query 匹配良好。

---

#### **Stage 2 — Exhaustive refinement（精確 re-ranking）**

只針對 Stage 1 過濾出的 (K) 份文件：

* 執行 Section 4 的「Top-k re-ranking」流程
* 完整算 MaxSim score
* 排序取 k

---

## **FAISS 索引細節**

ColBERT 使用：

#### **IVFPQ（Inverted File with Product Quantization）**

* 空間分成 $P$ 個 cell（例如 1000 個）
* 每個 embedding 依 k-means 查找最近 cell
* 查詢時只搜索前 $p$ 個最接近的 cell（例如 10 個）

#### **PQ 壓縮**

* 每個 embedding 被切成 (s) 個子向量（例如 16）
* 每部分量化為 1 byte
* 相似度計算可在壓縮後空間進行
  → 速度快、記憶體需求更低



## Experimental Evaluation

---

### **1. 實驗欲回答的四個研究問題（RQs）**

論文透過實驗回答四個核心問題：

#### **RQ1 — Re-ranking 效果與效能平衡**

> 在典型的 re-ranking 設定下，ColBERT 是否能兼具高效率與高準確？

（對應 Section 5.1）

---

#### **RQ2 — End-to-end Retrieval 的可行性**

> ColBERT 是否能在巨量文件庫（數百萬級）上直接做端到端檢索？

（對應 Section 5.2）

---

#### **RQ3 — 模型各組件的貢獻**

> Late Interaction、Query Augmentation 等組件對效果的貢獻為何？

（對應 Section 5.3）

---

#### **RQ4 — Indexing 成本**

> ColBERT 的離線文件編碼成本、時間與記憶體需求為何？

（對應 Section 5.4）

---

---

### **2. Re-ranking 實驗結果（MS MARCO）**

（來自 Table 1）

#### **2.1. 結論摘要**

| 方法                | MRR@10                | Latency(ms)          | FLOPs              |
| ----------------- | --------------------- | -------------------- | ------------------ |
| BERT (Base/Large) | **效果最好**              | **10,700–32,900 ms** | **97T–340T FLOPs** |
| 傳統神經模型（KNRM、Duet） | 中等                    | 3–28 ms              | 百萬～百億 FLOPs        |
| **ColBERT**       | **介於 BERT 與傳統神經模型之間** | **61 ms**            | **7B FLOPs**       |

#### **重點：**

* ColBERT 效果 **接近 BERT Base**（34.9 vs BERT Base 36.0）
* 速度 **快 170×**（61ms vs 10,700ms）
* FLOPs reduced **~14,000×**

→ 完美落在「高效能 × 高效率」交集區。

---

### **3. End-to-end Retrieval（直接查整個 880 萬文件庫）**

（Table 2）

#### **3.1. 結論摘要**

| 方法                     | Recall@1000  | Latency        |
| ---------------------- | ------------ | -------------- |
| BM25                   | 81.4         | 62–87ms（取決於版本） |
| docTTTTTquery          | 94.7         | 87ms           |
| **ColBERT end-to-end** | **96.8（最高）** | 458ms          |

#### **重點：**

* ColBERT（end-to-end）比所有基線的 **Recall** 都還高
* 雖然比 BM25 慢（458ms vs 62ms），但 Recall 提升巨大（96.8 vs 81.4）
* 適合需要高 recall 的應用（如 RAG, QA, 全文檢索）

---

### **4. Methodology（實驗方法）**

---

#### **4.1 Datasets & Metrics**

#### **MS MARCO（主要使用的 dataset）**

* 8.8M passages
* 1M real-world Bing queries
* 每個 query 只有 sparse relevant docs（通常 1 筆）
* 評估指標：**MRR@10**

#### 用到三個 query set：

1. 官方 dev set（~7k）
2. 官方 eval set（~7k，結果須提交給官方）
3. 額外 55k validation queries

   * 作者取其中隨機 5k 當 local evaluation set

Local set 用於：

* 測 end-to-end retrieval 的效果
* 避免大量提交到 MS MARCO 官方 Leaderboard

---

#### **TREC CAR**

* Wikipedia-based synthetic dataset
* 29M passages
* ~3M queries（由 title + section heading 組成）
* Relevance = 屬於該 section 的 passages
* 評估使用官方 TREC 2017 CAR test set（2,254 queries）

---

### **4.2 Implementation（實作細節）**

#### **框架**

* Python 3
* PyTorch 1.x
* Transformers（HuggingFace）

#### **訓練設定**

* LR = **3e-6**
* Batch size = **32**
* Query embeddings per query = **N_q = 32**
* ColBERT embedding dim = **128**

#### **模型初始化**

* MS MARCO：使用 Google 官方 BERT-Base

* 訓練 200k iterations

* TREC CAR：使用 Nogueira & Cho 特製的 BERT-Large
  （避免 Wiki 預訓練資料污染測試集）

* 訓練 125k iterations（較慢）

---

### **4.3 Similarity function**

* Re-ranking：使用 **cosine similarity**（因為 dot-product = cosine）
* End-to-end：使用 **L2 distance**（FAISS 在 L2 domain 更快）

---

### **4.4 FAISS Index Setting**

* Partitions (P = 2000)
* 搜索 p=10 個 partitions
* 每個 embedding 切成 16 個 sub-vectors（PQ 量化）
* 每 sub-vector 1 byte
* 二階段 ranking 的第二階段 index 用 16-bit 浮點值

---

### **4.5 硬體與延遲測量**

#### Re-ranking（GPU 密集）

* Tesla V100 (32GB) ×1
* CPU：Dual Xeon Gold 6132（28 cores / 48 threads）
* RAM：469GB

#### End-to-end & Indexing（CPU & multi-GPU 同時使用）

* 一台相同 CPU/RAM 的機器
* 4 × Titan V（12GB）
* 索引時最多可使用四張 GPU
* 查詢時每個 query 僅用一張 GPU（公平比較）



## ColBERT 實驗：品質–成本權衡（Top-k Re-ranking）

本節分析 ColBERT 在最常見的應用場景：
**re-ranking BM25 的前 k 個候選文件**時的效率與效果。

---

### **1. 實驗目的**

在 re-ranking 上比較 ColBERT 與多種模型：

#### **傳統神經匹配模型**

* KNRM
* Duet
* fastText + ConvKNRM

#### **BERT-based 模型（跨編碼器 cross-encoder）**

* BERT Base
* BERT Large
* BERT Base（論文作者依 ColBERT 訓練流程自行重訓版本）

比較項目：

* MRR@10（驗證集與官方評測）
* re-ranking latency（Tesla V100）
* FLOPs/query

---

### **2. 實驗方式與測量方式**

#### **2.1 MRR@10 衡量效果**

使用 MS MARCO 官方 Metric。

#### **2.2 Latency 測量**

* ColBERT：計入

  * gather doc embeddings
  * GPU transfer
  * query tokenization
  * query encoding
  * late interaction scoring
* Baselines：只計 GPU scoring，不計 CPU preprocessing
  （與 prior work 保持一致）

#### **2.3 FLOPs 計算**

使用 torchprofile 工具。

---

### **3. 主要結果（Table 1）**

表格顯示：

#### **(1) 神經排序的演進：KNRM → BERT**

* 從 2017~2019，MRR@10 提升超過 **16%**
* 但 BERT 代價極高（10,700ms ~ 32,900ms）

#### **(2) ColBERT 打破「越貴越準」的趨勢**
![image](https://hackmd.io/_uploads/SysRhJ9e-l.png)


| 模型                         | MRR@10    | Latency       | FLOPs    |
| -------------------------- | --------- | ------------- | -------- |
| BERT Base                  | 34.7–36.0 | **10,700 ms** | **97T**  |
| BERT Large                 | 36.5      | **32,900 ms** | **340T** |
| **ColBERT (Base encoder)** | **34.9**  | **61 ms**     | **7B**   |

#### 關鍵結論：

* **ColBERT 效果接近 BERT Base（甚至優於原論文中的 BERT Base）**
* **比 BERT Base 快 170×**
* **FLOPs 少 13,900×**

**ColBERT 做到「幾乎同樣效果」但「不到 1% 成本」。**

---

### **4. ColBERT 為何如此便宜？**

文中強調 ColBERT 的時間主要花在：

* gather / stack document embeddings
* 把 embeddings 傳到 GPU

真正的神經運算（包含 query encoding + MaxSim interaction）只花：

→ **13 ms**

而非幾十秒級的 cross-encoder。

#### 提到的可再優化方向（未在本論文做）：

* 減少 query padding 長度
* 更小的 embedding dimension
* 向量量化（quantization）
* 若 GPU 記憶體足夠 → document embeddings 直接存 GPU

---

### **5. k 對成本與成效的影響（Figure 4）**
![image](https://hackmd.io/_uploads/ryrg6kclWl.png)

實驗：依 BM25 的 top-k 做 re-ranking，觀察：

* FLOPs（成本）
* MRR@10（效果）

比較 BERT Base（作者訓練版） vs ColBERT。

### **觀察：**

#### **(1) ColBERT 隨 k 增加的成本成長非常緩慢**

因為：

* **ColBERT 的 BERT 只跑一次（query）**
* 文件向量皆已離線算好

結果：

* k = 10 → BERT FLOPs = ColBERT 的 180×
* k = 1000 → BERT FLOPs = ColBERT 的 13,900×
* k = 2000 → BERT FLOPs = ColBERT 的 23,000×

#### **(2) ColBERT 在大 k 時仍能維持接近 BERT 的 MRR**

→ 成本與成效的差距愈拉愈大。

文中指出：
此巨幅 FLOPs 差異甚至讓 **CPU-only ColBERT re-ranking** 變得可行（雖未正式研究）。

---

### **6. TREC CAR 結果（Table 3）**

TREC CAR 使用 MAP 作為主要指標。

| 方法                 | MAP      | MRR@10   |
| ------------------ | -------- | -------- |
| BM25               | 15.3     | —        |
| doc2query          | 18.1     | —        |
| DeepCT             | 24.6     | 33.2     |
| BM25 + BERT Base   | 31.0     | —        |
| BM25 + BERT Large  | 33.5     | —        |
| **BM25 + ColBERT** | **31.3** | **44.3** |

#### **結論：**

* 在 TREC CAR 中，ColBERT 的 MAP 與 BERT Base 接近（31.3 vs 31.0）
* 顯著優於 doc2query、DeepCT
* 同樣達到「BERT 級別效果 + 遠低成本」的結論

---

### 總整理

#### **1. ColBERT 幾乎達到 BERT 的 re-ranking 效果**

* MS MARCO：34.9 vs BERT Base 36.0
* TREC CAR：31.3 vs BERT Base 31.0

#### **2. 速度壓倒性勝利**

* 170× faster than BERT Base
* 13,900× fewer FLOPs

#### **3. 更能擴展到高 k（大規模 re-ranking）**

* 成本成長遠小於 BERT
* 效果幾乎不減

#### **4. 成果顯示 Late Interaction 能保留 BERT 的語意能力**

* MaxSim + contextualized embeddings 的架構具高表達力
* 成為 cross-encoder 的高效替代



### ColBERT 實驗

#### End-to-end Retrieval、Ablation、Indexing（詳細整理）

---

### **1. End-to-end Top-k Retrieval（從整個 880 萬文件庫直接檢索）**

本節探討：
ColBERT 是否能「直接」在全 MS MARCO（8.8M docs）上取得前 1000 筆結果，而不是只 re-rank top-1000。

對應結果見 Table 2。

---

### **1.1 比較對象**

#### **Bag-of-Words 檢索（BM25）**

* MS MARCO 官方 BM25
* Anserini BM25（最佳公開基準之一）

#### **三種增強型 BM25 方法：**

1. **doc2query**
   用 seq2seq 模型產生 synthetic queries 擴充文件內容

2. **DeepCT**
   用 BERT 產生「語意校正後的 term frequency」

3. **docTTTTTquery**
   用 T5 產生更高品質 synthetic queries 擴充文件

這三種方法本質仍是 **BM25 retrieval**，只是先修改文件（或其 term weight）。

---

### **1.2 Latency 的細節**

* 基於 Anserini 的模型使用多執行緒，但僅在「不同查詢之間」平行
* 測試 latency 時使用單執行緒（公平比較）
* DeepCT latency 以 BM25 latency 估計，因為其修改僅限 term weights

#### ColBERT end-to-end latency：

* 包含 FAISS filtering + 之後的 re-ranking
* FAISS 使用所有 CPU cores

---

### **1.3 主要觀察（Table 2）**

#### **(1) Anserini BM25**

* MRR@10 = 18.7（基線）
* Latency ≈ 62 ms（非常快）

#### **(2) document-expansion 方法的效果**

* doc2query → 顯著提升效果
* docTTTTTquery → 提升最明顯（增加 9% 以上 MRR@10）

且 latency 幾乎不增加，因為本質仍是 BM25。

#### **(3) ColBERT end-to-end 的效果**

* MRR@10 = **36.7（所有方法中最高）**
* Recall@50 = **82.9**

  > 甚至超過 BM25 的 Recall@1000（81.4）
* Recall@200 = 92.3
* Recall@1000 = 96.8（接近完美）

#### **重點：**

> ColBERT 直接搜尋整個集合的效果 **比 BM25→ColBERT re-ranking 還更好**
> 因為 recall 大幅提升（找不到的文件就無法 re-rank）。

---

### **2. Ablation Studies（消融實驗）**

（Figure ablation.pdf）

目的：
了解 ColBERT 的效果來源，哪些組件最有貢獻。

---

#### **2.1 實驗設定**

* 主模型（E）MRR@10 = 34.9（12-layer BERT Base）
* 為降低成本，訓練一組只用前 **5 層 BERT** 的模型（D）
* 所有 ablation 模型也使用 5 層 BERT、訓練 200k iterations

---

### **2.2 消融項目與發現**

#### **(A) 移除 Late Interaction → 單向量表示**

* 用 BERT [CLS] 產生 query/document 單向量
* 用內積算 score
* 表現顯著低於 ColBERT
  → **證明 Late Interaction（token-level matching）至關重要**

---

#### **(B) 將 MaxSim 換成 Average similarity**

* performance 明顯下降
  → **證明「每個 query token 應慎選最佳匹配 token」的重要性**
  → MaxSim 保留了「重要 token 對齊」的能力

---

#### **(C) 移除 Query Augmentation（不使用 mask padding）**

* 效果下降
  → 此特性對 query expansion / term reweighting 很重要

---

#### **(D) 使用少層 BERT（5 layers）**

* 效果比 12 layer 略降
* 但仍能顯示 trends
  → 用於 ablation 的有效替代模型

---

#### **(E) End-to-end retrieval 的改善**

* End-to-end retrieval 把 BM25 完全繞開
* 可以找出 BM25 top-1000 之外的 relevant documents
  → **MRR@10 也獲益（因為找到了 BM25 不會拍進前 1000 的 relevant docs）**

---

### **3. Indexing Throughput 與 Footprint（編碼速度與儲存空間）**

本節衡量：

* offline indexing 的速度
* document embeddings 占用的空間

---

### **3.1 Indexing Throughput（Figure throughput.pdf）**

透過以下優化，ColBERT indexing 能大幅加速：

* batching
* bucket sorting（按文件長度分桶）
* multi-GPU
* CPU 並行 tokenization

結果：

* **MS MARCO 全 8.8M documents 可在約 3 小時內完成 encoding**
* 相較 BERT cross-encoder，ColBERT 只需編一次文件
  （cross-encoder 每個 query 都要重新編百份文件）

---

### **3.2 Storage Footprint（Table footprint）**

比較不同設定的 memory usage 與效果：

| Setting         | Emb Dim | Bytes/Dim | Space   | MRR@10 |
| --------------- | ------- | --------- | ------- | ------ |
| Re-rank, Cosine | 128     | 4         | 286 GiB | 34.9   |
| End-to-end L2   | 128     | 2         | 154 GiB | 36.0   |
| Re-rank L2      | 128     | 2         | 143 GiB | 34.8   |
| Cosine          | 48      | 4         | 54 GiB  | 34.4   |
| Cosine          | 24      | 2         | 27 GiB  | 33.9   |

---

### **3.3 關鍵觀察**

#### **(1) 容量可大幅縮減**

* 286 GiB → 27 GiB（縮小 10×）

#### **(2) 效果下降極小**

* 從 MRR@10 = 34.9
* 到 MRR@10 = 33.9（僅下降 1%）

#### **(3) embedding dim 與 bytes/element 是最主要的空間成本來源**

結論：

> ColBERT 可在「保留高效果」的前提下，大幅調整 embedding 大小，使其更適合大型檢索系統的部署。


## Conclusions）

### **1. 研究貢獻總結**

論文提出 **ColBERT**，一種基於深度語言模型（尤其是 BERT）且具備 **contextualized late interaction** 的新型排序模型。

核心優點：

#### **(1) Query 與 Document 可獨立編碼**

* 使用 BERT 將 query / document 各自編成 **細粒度 contextual embeddings**
* 不需要像 cross-encoder 那樣將 query + document 同時餵入 BERT
  → 大幅降低運算成本

#### **(2) Late Interaction（延遲互動）**

* 使用 **便宜** 且 **pruning-friendly** 的 MaxSim 操作
* 只需 token-level 的點積與 max-pool
  → 可在大規模 corpus 中快速比對

#### **(3) 在保持語意表達力的同時極大地提升速度**

* 保留 BERT 的 contextual representation（效果佳）
* 但互動計算非常輕量（效能佳）

---

### **2. 支援 End-to-end 檢索**

因為文件 embeddings 可離線預先計算：

* ColBERT 可以直接從大型文本庫做 **端到端 neural retrieval**
* 不需 BM25 → neural re-ranking 的兩階段流程

這使其成為真正「大規模可用」的神經檢索系統。

---

### **3. 效能與效率（主要結果）**

實驗顯示：

#### **比 BERT-based cross-encoder models 快 170×**

* latency 顯著降低

#### **FLOPs 減少 14,000×**

* computation 成本極度下降

#### **品質影響非常小**

* 效果僅比 BERT Base 稍弱
* 但遠勝所有非 BERT baseline models

**→ ColBERT 成功達成高效能 × 高效率的最佳平衡。**