ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT
ColBERT：通过 BERT 上的语境化后期交互实现高效和有效的通道搜索

Figure 3 depicts the general architecture of ColBERT, which comprises: (a) a query encoder $f_{Q}$, (b) a document encoder $f_{D}$, and (c) the late interaction mechanism. Given a query $q$ and document $d$, $f_{Q}$ encodes $q$ into a bag of fixed-size embeddings $E_{q}$ while $f_{D}$ encodes $d$ into another bag $E_{d}$. Crucially, each embeddings in $E_{q}$ and $E_{d}$ is contextualized based on the other terms in $q$ or $d$, respectively. We describe our BERT-based encoders in §3.2.
图 3 描述了 ColBERT 的总体架构，其中包括：(a) 查询编码器 $f_{Q}$ ；(b) 文档编码器 $f_{D}$ ；(c) 后期交互机制。给定查询 $q$ 和文档 $d$ ， $f_{Q}$ 将 $q$ 编码为固定大小的嵌入包 $E_{q}$ ，而 $f_{D}$ 将 $d$ 编码为另一个包 $E_{d}$ 。重要的是， $E_{q}$ 和 $E_{d}$ 中的每个嵌入词都分别根据 $q$ 或 $d$ 中的其他术语进行了上下文化。我们将在第 3.2 节中介绍基于 BERT 的编码器。

Using $E_{q}$ and $E_{d}$, ColBERT computes the relevance score between $q$ and $d$ via late interaction, which we define as a summation of maximum similarity (MaxSim) operators. In particular, we find the maximum cosine similarity of each $v\in E_{q}$ with vectors in $E_{d}$, and combine the outputs via summation. Besides cosine, we also evaluate squared L2 distance as a measure of vector similarity. Intuitively, this interaction mechanism softly searches for each query term $t_{q}$—in a manner that reflects its context in the query—against the document’s embeddings, quantifying the strength of the “match” via the largest similarity score between $t_{q}$ and a document term $t_{d}$. Given these term scores, it then estimates the document relevance by summing the matching evidence across all query terms.
利用 $E_{q}$ 和 $E_{d}$ ，ColBERT 通过后期交互计算 $q$ 和 $d$ 之间的相关性得分，我们将其定义为最大相似性 (MaxSim) 运算符的求和。具体来说，我们会找出每个 $v\in E_{q}$ 与 $E_{d}$ 中向量的最大余弦相似度，并通过求和将输出合并。除了余弦值，我们还将 L2 距离平方值作为向量相似性的衡量标准。直观地说，这种交互机制软搜索每个查询术语 $t_{q}$ --以反映其在查询中的上下文的方式--与文档的嵌入相对应，通过 $t_{q}$ 与文档术语 $t_{d}$ 之间最大的相似性得分来量化 "匹配 "的强度。有了这些术语得分，它就可以通过对所有查询术语的匹配证据求和来估计文档相关性。

While more sophisticated matching is possible with other choices such as deep convolution and attention layers (i.e., as in typical interaction-focused models), a summation of maximum similarity computations has two distinctive characteristics. First, it stands out as a particularly cheap interaction mechanism, as we examine its FLOPs in §4.2. Second, and more importantly, it is amenable to highly-efficient pruning for top-$k$ retrieval, as we evaluate in §4.3. This enables using vector-similarity algorithms for skipping documents without materializing the full interaction matrix or even considering each document in isolation. Other cheap choices (e.g., a summation of average similarity scores, instead of maximum) are possible; however, many are less amenable to pruning. In §4.4, we conduct an extensive ablation study that empirically verifies the advantage of our MaxSim-based late interaction against alternatives.
虽然深度卷积和注意力层（即典型的以交互为重点的模型）等其他选择可以实现更复杂的匹配，但最大相似性计算的求和有两个显著特点。首先，它是一种特别便宜的交互机制，我们将在第 4.2 节中研究它的 FLOPs。其次，更重要的是，正如我们在第 4.3 节中所评估的那样，它可用于高效剪枝，以实现 $k$ 顶级检索。这使得我们可以使用向量相似性算法来跳过文档，而无需将整个交互矩阵具体化，甚至无需单独考虑每个文档。其他廉价的选择（例如，平均相似性得分的求和，而不是最大值）也是可能的；但是，许多选择都不太适合剪枝。在第 4.4 节中，我们进行了广泛的消减研究，通过经验验证了我们基于 MaxSim 的后期交互与其他方法相比的优势。

Prior to late interaction, ColBERT encodes each query or document into a bag of embeddings, employing BERT-based encoders. We share a single BERT model among our query and document encoders but distinguish input sequences that correspond to queries and documents by prepending a special token [Q] to queries and another token [D] to documents.
在后期交互之前，ColBERT 采用基于 BERT 的编码器，将每个查询或文档编码成嵌入包。我们的查询和文档编码器共用一个 BERT 模型，但通过在查询前添加一个特殊标记 [Q]，在文档前添加另一个标记 [D] 来区分查询和文档对应的输入序列。

Query Encoder. Given a textual query $q$, we tokenize it into its BERT-based WordPiece (Wu et al., 2016) tokens $q_{1}q_{2}...q_{l}$. We prepend the token [Q] to the query. We place this token right after BERT’s sequence-start token [CLS]. If the query has fewer than a pre-defined number of tokens $N_{q}$, we pad it with BERT’s special [mask] tokens up to length $N_{q}$ (otherwise, we truncate it to the first $N_{q}$ tokens). This padded sequence of input tokens is then passed into BERT’s deep transformer architecture, which computes a contextualized representation of each token.
查询编码器。给定一个文本查询 $q$ ，我们将其标记化为基于 BERT 的 WordPiece（Wu 等人，2016 年）标记 $q_{1}q_{2}...q_{l}$ 。我们在查询前加上标记 [Q]。我们将该标记放在 BERT 的序列起始标记 [CLS] 之后。如果查询的标记数 $N_{q}$ 少于预定义的标记数，我们就用 BERT 的特殊 [mask] 标记来填充，长度不超过 $N_{q}$ （否则，我们会将其截断到第一个标记 $N_{q}$ ）。然后，经过填充的输入标记序列会被传入 BERT 的深度 transformer 架构，该架构会计算每个标记的上下文化表示。

We denote the padding with masked tokens as query augmentation, a step that allows BERT to produce query-based embeddings at the positions corresponding to these masks. Query augmentation is intended to serve as a soft, differentiable mechanism for learning to expand queries with new terms or to re-weigh existing terms based on their importance for matching the query. As we show in §4.4, this operation is essential for ColBERT’s effectiveness.
我们将使用屏蔽标记进行的填充称为查询增强（query augmentation），这一步骤允许 BERT 在这些屏蔽对应的位置生成基于查询的嵌入。查询增强的目的是作为一种软性的、可区分的机制，用于学习使用新术语扩展查询，或根据现有术语对匹配查询的重要性对其进行重新权衡。正如我们在第4.4节中所展示的，这一操作对ColBERT的有效性至关重要。

Given BERT’s representation of each token, our encoder passes the contextualized output representations through a linear layer with no activations. This layer serves to control the dimension of ColBERT’s embeddings, producing $m$-dimensional embeddings for the layer’s output size $m$. As we discuss later in more detail, we typically fix $m$ to be much smaller than BERT’s fixed hidden dimension.
根据 BERT 对每个标记的表示，我们的编码器将上下文化的输出表示通过一个没有激活的线性层。该层的作用是控制 ColBERT 嵌入的维度，为该层的输出大小 $m$ 生成 $m$ 维的嵌入。正如我们稍后详细讨论的那样，我们通常会将 $m$ 固定为比 BERT 的固定隐藏维度小得多。

While ColBERT’s embedding dimension has limited impact on the efficiency of query encoding, this step is crucial for controlling the space footprint of documents, as we show in §4.5. In addition, it can have a significant impact on query execution time, particularly the time taken for transferring the document representations onto the GPU from system memory (where they reside before processing a query). In fact, as we show in §4.2, gathering, stacking, and transferring the embeddings from CPU to GPU can be the most expensive step in re-ranking with ColBERT. Finally, the output embeddings are normalized so each has L2 norm equal to one. The result is that the dot-product of any two embeddings becomes equivalent to their cosine similarity, falling in the $[-1,1]$ range.
虽然ColBERT的嵌入维度对查询编码的效率影响有限，但正如我们在第4.5节中所展示的，这一步对控制文档的空间占用至关重要。此外，它还会对查询执行时间产生重大影响，尤其是将文档表示从系统内存（处理查询前的内存）传输到GPU上所花费的时间。事实上，正如我们在第4.2节中所展示的，在使用ColBERT重新排序的过程中，收集、堆叠和将嵌入式从CPU传输到GPU是最昂贵的步骤。最后，对输出嵌入进行归一化处理，使每个嵌入的 L2 准则都等于 1。这样，任意两个嵌入式的点积就等同于它们的余弦相似度，在 $[-1,1]$ 范围内。

Document Encoder. Our document encoder has a very similar architecture. We first segment a document $d$ into its constituent tokens $d_{1}d_{2}...d_{m}$, to which we prepend BERT’s start token [CLS] followed by our special token [D] that indicates a document sequence. Unlike queries, we do not append [mask] tokens to documents. After passing this input sequence through BERT and the subsequent linear layer, the document encoder filters out the embeddings corresponding to punctuation symbols, determined via a pre-defined list. This filtering is meant to reduce the number of embeddings per document, as we hypothesize that (even contextualized) embeddings of punctuation are unnecessary for effectiveness.
文档编码器。我们的文档编码器具有非常相似的结构。我们首先将文档 $d$ 分割成其组成标记 $d_{1}d_{2}...d_{m}$ ，然后将 BERT 的起始标记 [CLS] 和表示文档序列的特殊标记 [D] 加入其中。与查询不同，我们不会在文档中添加 [mask] 标记。将输入序列通过 BERT 和随后的线性层后，文档编码器会过滤掉与标点符号相对应的嵌入，这些嵌入是通过预定义列表确定的。这种过滤的目的是为了减少每份文档的嵌入数量，因为我们认为，标点符号的嵌入（即使是上下文化的）也没有必要，因为这样做才会有效。

In summary, given $q=q_{0}q_{1}...q_{l}$ and $d=d_{0}d_{1}...d_{n}$, we compute the bags of embeddings $E_{q}$ and $E_{d}$ in the following manner, where $\#$ refers to the [mask] tokens:
总之，在给定 $q=q_{0}q_{1}...q_{l}$ 和 $d=d_{0}d_{1}...d_{n}$ 的情况下，我们按以下方式计算嵌入包 $E_{q}$ 和 $E_{d}$ ，其中 $\#$ 指的是 [掩码] 标记：

Given the representation of a query $q$ and a document $d$, the relevance score of $d$ to $q$, denoted as $S_{q,d}$, is estimated via late interaction between their bags of contextualized embeddings. As mentioned before, this is conducted as a sum of maximum similarity computations, namely cosine similarity (implemented as dot-products due to the embedding normalization) or squared L2 distance.
鉴于查询 $q$ 和文档 $d$ 的表示形式， $d$ 与 $q$ 的相关性得分（表示为 $S_{q,d}$ ）是通过它们的上下文嵌入包之间的后期交互来估算的。如前所述，这是最大相似性计算的总和，即余弦相似性（由于嵌入归一化，以点积的形式实现）或 L2 距离的平方。

ColBERT is differentiable end-to-end. We fine-tune the BERT encoders and train from scratch the additional parameters (i.e., the linear layer and the [Q] and [D] markers’ embeddings) using the Adam (Kingma and Ba, 2014) optimizer. Notice that our interaction mechanism has no trainable parameters. Given a triple $\langle q,d^{+},d^{-}\rangle$ with query $q$, positive document $d^{+}$ and negative document $d^{-}$, ColBERT is used to produce a score for each document individually and is optimized via pairwise softmax cross-entropy loss over the computed scores of $d^{+}$ and $d^{-}$.
ColBERT 是端到端可微分的。我们使用 Adam（Kingma 和 Ba，2014 年）优化器对 BERT 编码器进行微调，并从头开始训练附加参数（即线性层以及 [Q] 和 [D] 标记的嵌入）。请注意，我们的交互机制没有可训练的参数。给定一个包含查询 $q$ 、正面文档 $d^{+}$ 和负面文档 $d^{-}$ 的三重 $\langle q,d^{+},d^{-}\rangle$ ，ColBERT 用于为每个文档单独生成一个分数，并通过对 $d^{+}$ 和 $d^{-}$ 的计算分数进行成对 softmax 交叉熵损失进行优化。

By design, ColBERT isolates almost all of the computations between queries and documents, largely to enable pre-computing document representations offline. At a high level, our indexing procedure is straight-forward: we proceed over the documents in the collection in batches, running our document encoder $f_{D}$ on each batch and storing the output embeddings per document. Although indexing a set of documents is an offline process, we incorporate a few simple optimizations for enhancing the throughput of indexing. As we show in §4.5, these optimizations can considerably reduce the offline cost of indexing.
根据设计，ColBERT 将查询和文档之间的几乎所有计算隔离开来，这在很大程度上是为了实现离线预计算文档表示。在高层次上，我们的索引编制程序非常简单：我们分批处理文档集中的文档，在每批文档上运行我们的文档编码器 $f_{D}$ ，并存储每个文档的输出嵌入。虽然为文档集编制索引是一个离线过程，但我们还是采用了一些简单的优化方法来提高索引的吞吐量。正如我们在第 4.5 节中所展示的，这些优化可以大大降低索引的离线成本。

To begin with, we exploit multiple GPUs, if available, for faster encoding of batches of documents in parallel. When batching, we pad all documents to the maximum length of a document within the batch.³³3The public BERT implementations we saw simply pad to a pre-defined length.
我们看到的公共 BERT 实现只是简单地填充到预定义的长度。
首先，我们会利用多个 GPU（如果有的话）来更快地对成批文档进行并行编码。批处理时，我们会将所有文档填充到批处理中文档的最大长度。 ³ To make capping the sequence length on a per-batch basis more effective, our indexer proceeds through documents in groups of $B$ (e.g., $B=$ 100,000) documents. It sorts these documents by length and then feeds batches of $b$ (e.g., $b=$ 128) documents of comparable length through our encoder. This length-based bucketing is sometimes refered to as a BucketIterator in some libraries (e.g., allenNLP). Lastly, while most computations occur on the GPU, we found that a non-trivial portion of the indexing time is spent on pre-processing the text sequences, primarily BERT’s WordPiece tokenization. Exploiting that these operations are independent across documents in a batch, we parallelize the pre-processing across the available CPU cores.
为了更有效地按批次设置序列长度上限，我们的索引器以 $B$ （例如， $B=$ 100,000 个）文档为一组对文档进行处理。它按长度对这些文档进行排序，然后将长度相当的 $b$ （例如， $b=$ 128）文档批次送入我们的编码器。在某些库（如 allenNLP）中，这种基于长度的分级有时被称为 BucketIterator。最后，虽然大部分计算都是在 GPU 上进行的，但我们发现索引时间的很大一部分都花在了文本序列的预处理上，主要是 BERT 的 WordPiece 标记化。利用这些操作在批次文档中的独立性，我们在可用的 CPU 内核上对预处理进行了并行化处理。

Once the document representations are produced, they are saved to disk using 32-bit or 16-bit values to represent each dimension. As we describe in §3.5 and 3.6, these representations are either simply loaded from disk for ranking or are subsequently indexed for vector-similarity search, respectively.
文档表示法制作完成后，会使用 32 位或 16 位值将其保存到磁盘中，以表示每个维度。正如我们在第 3.5 节和第 3.6 节中所描述的那样，这些表示法要么被简单地从磁盘加载以进行排序，要么随后被索引以进行向量相似性搜索。

Recall that ColBERT can be used for re-ranking the output of another retrieval model, typically a term-based model, or directly for end-to-end retrieval from a document collection. In this section, we discuss how we use ColBERT for ranking a small set of $k$ (e.g., $k=1000$) documents given a query $q$. Since $k$ is small, we rely on batch computations to exhaustively score each document (unlike our approach in §3.6). To begin with, our query serving sub-system loads the indexed documents representations into memory, representing each document as a matrix of embeddings.
回顾一下，ColBERT 可用于对另一个检索模型（通常是基于术语的模型）的输出结果进行重新排序，也可直接用于从文档集合中进行端到端检索。在本节中，我们将讨论如何使用 ColBERT 对给定查询 $q$ 的一小部分 $k$ （例如 $k=1000$ ）文档进行排序。由于 $k$ 较小，因此我们依靠批量计算对每个文档进行详尽的评分（与第 3.6 节中的方法不同）。首先，我们的查询服务子系统会将索引文档表示载入内存，将每个文档表示为嵌入矩阵。

Given a query $q$, we compute its bag of contextualized embeddings $E_{q}$ (Equation 1) and, concurrently, gather the document representations into a 3-dimensional tensor $D$ consisting of $k$ document matrices. We pad the $k$ documents to their maximum length to facilitate batched operations, and move the tensor $D$ to the GPU’s memory. On the GPU, we compute a batch dot-product of $E_{q}$ and $D$, possibly over multiple mini-batches. The output materializes a 3-dimensional tensor that is a collection of cross-match matrices between $q$ and each document. To compute the score of each document, we reduce its matrix across document terms via a max-pool (i.e., representing an exhaustive implementation of our MaxSim computation) and reduce across query terms via a summation. Finally, we sort the $k$ documents by their total scores.
给定查询 $q$ ，我们计算其上下文嵌入包 $E_{q}$ （等式 1），同时将文档表示收集到由 $k$ 文档矩阵组成的三维张量 $D$ 中。我们将 $k$ 文档填充到最大长度，以方便分批操作，并将张量 $D$ 移到 GPU 的内存中。在 GPU 上，我们计算 $E_{q}$ 和 $D$ 的批量点积，可能需要多个迷你批次。输出结果是一个三维张量，它是 $q$ 和每个文档之间交叉匹配矩阵的集合。为了计算每个文档的得分，我们通过最大池（即代表我们的 MaxSim 计算的穷举实现）对其矩阵进行跨文档术语还原，并通过求和对查询术语进行还原。最后，我们按总分对 $k$ 文档进行排序。

Relative to existing neural rankers (especially, but not exclusively, BERT-based ones), this computation is very cheap that, in fact, its cost is dominated by the cost of gathering and transferring the pre-computed embeddings. To illustrate, ranking $k$ documents via typical BERT rankers requires feeding BERT $k$ different inputs each of length $l=|q|+|d_{i}|$ for query $q$ and documents $d_{i}$, where attention has quadratic cost in the length of the sequence. In contrast, ColBERT feeds BERT only a single, much shorter sequence of length $l=|q|$. Consequently, ColBERT is not only cheaper, it also scales much better with $k$ as we examine in §4.2.
相对于现有的神经排序器（尤其是但不限于基于 BERT 的排序器），这种计算方法的成本非常低廉，事实上，其成本主要来自于收集和传输预计算嵌入的成本。举例来说，通过典型的 BERT 排序器对 $k$ 文档进行排序，需要向 BERT 提供 $k$ 不同的输入，每个输入长度为 $l=|q|+|d_{i}|$ 查询 $q$ 和文档 $d_{i}$ ，其中注意力的成本与序列的长度成二次方关系。相比之下，ColBERT 只向 BERT 提供一个长度为 $l=|q|$ 的更短的单一序列。因此，ColBERT 不仅成本更低，而且随着 $k$ 的增加，其扩展性也会大大提高，这一点我们将在第 4.2 节中进行探讨。

As mentioned before, ColBERT’s late-interaction operator is specifically designed to enable end-to-end retrieval from a large collection, largely to improve recall relative to term-based retrieval approaches. This section is concerned with cases where the number of documents to be ranked is too large for exhaustive evaluation of each possible candidate document, particularly when we are only interested in the highest scoring ones. Concretely, we focus here on retrieving the top-$k$ results directly from a large document collection with $N$ (e.g., $N=10,000,000$) documents, where $k\ll N$.
如前所述，ColBERT的后期交互运算符是专门为从大量文档中进行端到端检索而设计的，其主要目的是相对于基于术语的检索方法而言提高召回率。本节将讨论这样一种情况，即需要排序的文档数量过多，无法对每个可能的候选文档进行详尽的评估，尤其是当我们只对得分最高的文档感兴趣时。具体来说，我们在此关注的是直接从一个包含 $N$ （例如 $N=10,000,000$ ）文档的大型文档集中检索出得分最高的 $k$ 结果，其中 $k\ll N$ .

To do so, we leverage the pruning-friendly nature of the MaxSim operations at the backbone of late interaction. Instead of applying MaxSim between one of the query embeddings and all of one document’s embeddings, we can use fast vector-similarity data structures to efficiently conduct this search between the query embedding and all document embeddings across the full collection. For this, we employ an off-the-shelf library for large-scale vector-similarity search, namely faiss (Johnson et al., 2017) from Facebook.⁴⁴4https://github.com/facebookresearch/faiss
为此，我们利用了后期交互中的 MaxSim 操作的剪枝友好性。我们可以使用快速的向量相似性数据结构在查询嵌入和整个集合中的所有文档嵌入之间高效地进行搜索，而不是在一个查询嵌入和所有文档嵌入之间应用 MaxSim。为此，我们使用了一个用于大规模矢量相似性搜索的现成库，即 Facebook 的 faiss（Johnson 等人，2017 年）。 ⁴ In particular, at the end of offline indexing (§3.4), we maintain a mapping from each embedding to its document of origin and then index all document embeddings into faiss.
特别是，在离线索引（第 3.4 节）结束时，我们会维护每个嵌入到其来源文档的映射，然后将所有文档嵌入索引到 faiss 中。

Subsequently, when serving queries, we use a two-stage procedure to retrieve the top-$k$ documents from the entire collection. Both stages rely on ColBERT’s scoring: the first is an approximate stage aimed at filtering while the second is a refinement stage. For the first stage, we concurrently issue $N_{q}$ vector-similarity queries (corresponding to each of the embeddings in $E_{q}$) onto our faiss index. This retrieves the top-$k^{\prime}$ (e.g., $k^{\prime}=k/2$) matches for that vector over all document embeddings. We map each of those to its document of origin, producing $N_{q}\times k^{\prime}$ document IDs, only $K\leq N_{q}\times k^{\prime}$ of which are unique. These $K$ documents likely contain one or more embeddings that are highly similar to the query embeddings. For the second stage, we refine this set by exhaustively re-ranking only those $K$ documents in the usual manner described in §3.5.
随后，在提供查询时，我们会使用一个两阶段的程序，从整个文档集中检索出排名前 $k$ 的文档。这两个阶段都依赖于 ColBERT 的评分：第一个阶段是近似阶段，目的是过滤，而第二个阶段是细化阶段。在第一阶段，我们同时向我们的 faiss 索引发出 $N_{q}$ 向量相似性查询（与 $E_{q}$ 中的每个嵌入相对应）。这将检索出该向量在所有文档嵌入式中匹配度最高的 $k^{\prime}$ （例如， $k^{\prime}=k/2$ ）。我们将每个匹配项映射到其源文件，从而生成 $N_{q}\times k^{\prime}$ 文档 ID，其中只有 $K\leq N_{q}\times k^{\prime}$ 是唯一的。这些 $K$ 文档可能包含一个或多个与查询嵌入式高度相似的嵌入式。在第二阶段，我们将按照第 3.5 节中描述的常规方法，仅对 $K$ 文档进行详尽的重新排序，从而完善这个集合。

In our faiss-based implementation, we use an IVFPQ index (“inverted file with product quantization”). This index partitions the embedding space into $P$ (e.g., $P=1000$) cells based on $k$-means clustering and then assigns each document embedding to its nearest cell based on the selected vector-similarity metric. For serving queries, when searching for the top-$k^{\prime}$ matches for a single query embedding, only the nearest $p$ (e.g., $p=10$) partitions are searched. To improve memory efficiency, every embedding is divided into $s$ (e.g., $s=16$) sub-vectors, each represented using one byte. Moreover, the index conducts the similarity computations in this compressed domain, leading to cheaper computations and thus faster search.
在基于 faiss 的实现中，我们使用了 IVFPQ 索引（"带乘积量化的反转文件"）。该索引根据 $k$ 均值聚类将嵌入空间划分为 $P$ （例如 $P=1000$ ）单元格，然后根据所选的向量相似度量将每个文档嵌入分配到其最近的单元格。对于服务查询，在搜索单个查询嵌入的顶部 $k^{\prime}$ 匹配项时，只搜索最近的 $p$ （例如 $p=10$ ）分区。为了提高内存效率，每个嵌入都被分为 $s$ （例如， $s=16$ ）子向量，每个子向量用一个字节表示。此外，索引会在这个压缩域中进行相似性计算，从而降低计算成本，加快搜索速度。

In this section, we examine ColBERT’s efficiency and effectiveness at re-ranking the top-$k$ results extracted by a bag-of-words retrieval model, which is the most typical setting for testing and deploying neural ranking models. We begin with the MS MARCO dataset. We compare against KNRM, Duet, and fastText+ConvKNRM, a representative set of neural matching models that have been previously tested on MS MARCO. In addition, we compare against the natural adaptation of BERT for ranking by Nogueira and Cho (Nogueira and Cho, 2019), in particular, BERT${}_{\textnormal{base}}$ and its deeper counterpart BERT${}_{\textnormal{large}}$. We also report results for “BERT${}_{\textnormal{base}}$ (our training)”, which is based on Nogueira and Cho’s base model (including hyperparameters) but is trained with the same loss function as ColBERT (§3.3) for 200k iterations, allowing for a more direct comparison of the results.
在本节中，我们将检验 ColBERT 在对词袋检索模型提取的顶部 $k$ 结果进行重新排序时的效率和有效性，这也是测试和部署神经排序模型的最典型环境。我们从 MS MARCO 数据集开始。我们将其与 KNRM、Duet 和 fastText+ConvKNRM 进行比较，这是一组具有代表性的神经匹配模型，之前已在 MS MARCO 上进行过测试。此外，我们还与 Nogueira 和 Cho（Nogueira 和 Cho，2019 年）对 BERT 进行的自然适应排序进行了比较，特别是 BERT ${}_{\textnormal{base}}$ 及其更深入的对应模型 BERT ${}_{\textnormal{large}}$ 。我们还报告了 "BERT ${}_{\textnormal{base}}$ （我们的训练）"的结果，它基于 Nogueira 和 Cho 的基础模型（包括超参数），但使用与 ColBERT 相同的损失函数（第 3.3 节）进行了 200k 次迭代训练，从而可以对结果进行更直接的比较。

We report the competition’s official metric, namely MRR@10, on the validation set (Dev) and the evaluation set (Eval). We also report the re-ranking latency, which we measure using a single Tesla V100 GPU, and the FLOPs per query for each neural ranking model. For ColBERT, our reported latency subsumes the entire computation from gathering the document representations, moving them to the GPU, tokenizing then encoding the query, and applying late interaction to compute document scores. For the baselines, we measure the scoring computations on the GPU and exclude the CPU-based text preprocessing (similar to (Hofstätter and Hanbury, 2019)). In principle, the baselines can pre-compute the majority of this preprocessing (e.g., document tokenization) offline and parallelize the rest across documents online, leaving only a negligible cost. We estimate the FLOPs per query of each model using the torchprofile⁶⁶6https://github.com/mit-han-lab/torchprofile
我们报告了比赛的官方指标，即验证集（Dev）和评估集（Eval）上的 MRR@10。我们还报告了重新排序的延迟（我们使用单个 Tesla V100 GPU 进行测量），以及每个神经排序模型每次查询的 FLOPs。对于 ColBERT，我们报告的延迟包含了从收集文档表示、将其移动到 GPU、标记化然后编码查询，以及应用后期交互计算文档分数的整个计算过程。对于基线，我们测量的是 GPU 上的评分计算，不包括基于 CPU 的文本预处理（类似于（Hofstätter and Hanbury, 2019））。原则上，基线可以离线预处理大部分预处理（如文档标记化），并在线并行处理文档中的其余部分，因此成本可以忽略不计。我们使用 torchprofile ⁶ 来估算每个模型每次查询的 FLOPs。 library. 图书馆

We now proceed to study the results, which are reported in Table 1. To begin with, we notice the fast progress from KNRM in 2017 to the BERT-based models in 2019, manifesting itself in over 16% increase in MRR@10. As described in §1, the simultaneous increase in computational cost is difficult to miss. Judging by their rather monotonic pattern of increasingly larger cost and higher effectiveness, these results appear to paint a picture where expensive models are necessary for high-quality ranking.
现在我们开始研究表 1 中报告的结果。首先，我们注意到从 2017 年的 KNRM 到 2019 年基于 BERT 的模型的快速进步，表现为 MRR@10 增加了 16% 以上。如第 1 节所述，计算成本的同时增加是难以忽视的。从成本越来越高、效率越来越高的单调模式来看，这些结果似乎描绘了一幅图景：要想获得高质量的排名，就必须使用昂贵的模型。

In contrast with this trend, ColBERT (which employs late interaction over BERT${}_{\textnormal{base}}$) performs no worse than the original adaptation of BERT${}_{\textnormal{base}}$ for ranking by Nogueira and Cho (Nogueira and Cho, 2019; Nogueira et al., 2019b) and is only marginally less effective than BERT${}_{\textnormal{large}}$ and our training of BERT${}_{\textnormal{base}}$ (described above). While highly competitive in effectiveness, ColBERT is orders of magnitude cheaper than BERT${}_{\textnormal{base}}$, in particular, by over 170$\times$ in latency and 13,900$\times$ in FLOPs. This highlights the expressiveness of our proposed late interaction mechanism, particularly when coupled with a powerful pre-trained LM like BERT. While ColBERT’s re-ranking latency is slightly higher than the non-BERT re-ranking models shown (i.e., by 10s of milliseconds), this difference is explained by the time it takes to gather, stack, and transfer the document embeddings to the GPU. In particular, the query encoding and interaction in ColBERT consume only 13 milliseconds of its total execution time. We note that ColBERT’s latency and FLOPs can be considerably reduced by padding queries to a shorter length, using smaller vector dimensions (the MRR@10 of which is tested in §4.5), employing quantization of the document vectors, and storing the embeddings on GPU if sufficient memory exists. We leave these directions for future work.
与这一趋势相反，ColBERT（它在 BERT ${}_{\textnormal{base}}$ 上采用了后期交互）的性能并不比 Nogueira 和 Cho（Nogueira 和 Cho，2019 年；Nogueira 等人，2019b）对 BERT ${}_{\textnormal{base}}$ 进行排名的原始调整差，而且仅略低于 BERT ${}_{\textnormal{large}}$ 和我们对 BERT ${}_{\textnormal{base}}$ 的训练（如上所述）。虽然 ColBERT 在有效性方面极具竞争力，但其成本却比 BERT ${}_{\textnormal{base}}$ 低几个数量级，尤其是在延迟和 FLOPs 方面分别低 170 $\times$ 和 13,900 $\times$ 个数量级。这凸显了我们提出的后期交互机制的表现力，尤其是在与 BERT 这样强大的预训练 LM 相结合时。虽然 ColBERT 的重新排序延迟略高于所示的非 BERT 重新排序模型（即 10 毫秒），但这一差异是由于收集、堆叠文档嵌入并将其传输到 GPU 所花费的时间造成的。特别是，ColBERT 的查询编码和交互仅耗费其总执行时间的 13 毫秒。我们注意到，ColBERT的延迟和FLOPs可以通过将查询填充到更短的长度、使用更小的矢量维度（第4.5节测试了其MRR@10）、对文档矢量进行量化，以及在有足够内存的情况下在GPU上存储嵌入来大大减少。我们将这些方向留给未来的工作。

Diving deeper into the quality–cost tradeoff between BERT and ColBERT, Figure 4 demonstrates the relationships between FLOPs and effectiveness (MRR@10) as a function of the re-ranking depth $k$ when re-ranking the top-$k$ results by BM25, comparing ColBERT and BERT${}_{\textnormal{base}}$ (our training). We conduct this experiment on MS MARCO (Dev). We note here that as the official top-1000 ranking does not provide the BM25 order (and also lacks documents beyond the top-1000 per query), the models in this experiment re-rank the Anserini (Yang et al., 2018) toolkit’s BM25 output. Consequently, both MRR@10 values at $k=1000$ are slightly higher from those reported in Table 1.
深入探讨 BERT 和 ColBERT 之间的质量成本权衡，图 4 展示了在通过 BM25 对排名最高的 $k$ 结果进行重新排序时，FLOP 与效率（MRR@10）之间的关系，即重新排序深度 $k$ 与 ColBERT 和 BERT ${}_{\textnormal{base}}$ （我们的训练）之间的函数关系。我们在 MS MARCO (Dev) 上进行了这一实验。我们在此注意到，由于官方的前 1000 名排名不提供 BM25 排序（而且每次查询也缺少前 1000 名以外的文档），因此本实验中的模型对 Anserini（Yang 等人，2018 年）工具包的 BM25 输出进行了重新排序。因此， $k=1000$ 处的两个 MRR@10 值都比表 1 中报告的值略高。

Studying the results in Figure 4, we notice that not only is ColBERT much cheaper than BERT for the same model size (i.e., 12-layer “base” transformer encoder), it also scales better with the number of ranked documents. In part, this is because ColBERT only needs to process the query once, irrespective of the number of documents evaluated. For instance, at $k=10$, BERT requires nearly 180$\times$ more FLOPs than ColBERT; at $k=1000$, BERT’s overhead jumps to 13,900$\times$. It then reaches 23,000$\times$ at $k=2000$. In fact, our informal experimentation shows that this orders-of-magnitude gap in FLOPs makes it practical to run ColBERT entirely on the CPU, although CPU-based re-ranking lies outside our scope.
通过研究图 4 中的结果，我们注意到在相同模型大小（即 12 层 "基础"transformer编码器）的情况下，ColBERT 不仅比 BERT 便宜得多，而且随着排序文档数量的增加，其扩展性也更好。部分原因是 ColBERT 只需要处理一次查询，而与评估的文档数量无关。例如，在 $k=10$ 时，BERT 需要比 ColBERT 多近 180 个 $\times$ FLOP；在 $k=1000$ 时，BERT 的开销跃升至 13,900 个 $\times$ 。然后在 $k=2000$ 时达到 23,000 $\times$ 。事实上，我们的非正式实验表明，尽管基于 CPU 的重新排序不在我们的研究范围之内，但 FLOPs 上的这种数量级差距使得完全在 CPU 上运行 ColBERT 变得切实可行。

Having studied our results on MS MARCO, we now consider TREC CAR, whose official metric is MAP. Results are summarized in Table 3, which includes a number of important baselines (BM25, doc2query, and DeepCT) in addition to re-ranking baselines that have been tested on this dataset. These results directly mirror those with MS MARCO.
在研究了我们在 MS MARCO 数据集上的结果后，我们现在来研究 TREC CAR 数据集，其官方指标是 MAP。表 3 总结了结果，其中包括一些重要的基线（BM25、doc2query 和 DeepCT），以及在该数据集上测试过的重新排序基线。这些结果直接反映了 MS MARCO 的结果。

Beyond cheap re-ranking, ColBERT is amenable to top-$k$ retrieval directly from a full collection. Table 2 considers full retrieval, wherein each model retrieves the top-1000 documents directly from MS MARCO’s 8.8M documents per query. In addition to MRR@10 and latency in milliseconds, the table reports Recall@50, Recall@200, and Recall@1000, important metrics for a full-retrieval model that essentially filters down a large collection on a per-query basis.
除了廉价的重新排序之外，ColBERT 还可以直接从完整的文档库中检索出排名前 $k$ 的文档。表 2 列出了全部检索结果，其中每个模型每次查询都能直接从 MS MARCO 的 880 万个文档中检索出前 1000 个文档。除了以毫秒为单位的 MRR@10 和延迟外，该表还报告了 Recall@50、Recall@200 和 Recall@1000，这些都是全检索模型的重要指标，因为全检索模型基本上是按每次查询过滤大量文档。

We compare against BM25, in particular MS MARCO’s official BM25 ranking as well as a well-tuned baseline based on the Anserini toolkit.⁷⁷7http://anserini.io/
我们与 BM25 进行了比较，特别是 MS MARCO 的官方 BM25 排名以及基于 Anserini 工具包的经过良好调整的基线。 ⁷ While many other traditional models exist, we are not aware of any that substantially outperform Anserini’s BM25 implementation (e.g., see RM3 in (Nogueira et al., 2019c), LMDir in (Dai and Callan, 2019a), or Microsoft’s proprietary feature-based RankSVM on the leaderboard).
虽然存在许多其他传统模型，但我们还没有发现任何模型的性能大大优于 Anserini 的 BM25 实现（例如，请参见 (Nogueira et al., 2019c) 中的 RM3、(Dai and Callan, 2019a) 中的 LMDir 或排行榜上的微软专有的基于特征的 RankSVM）。

We also compare against doc2query, DeepCT, and docTTTTTquery. All three rely on a traditional bag-of-words model (primarily BM25) for retrieval. Crucially, however, they re-weigh the frequency of terms per document and/or expand the set of terms in each document before building the BM25 index. In particular, doc2query expands each document with a pre-defined number of synthetic queries generated by a seq2seq transformer model (which docTTTTquery replaced with a pre-trained language model, T5 (Raffel et al., 2019)). In contrast, DeepCT uses BERT to produce the term frequency component of BM25 in a context-aware manner.
我们还与 doc2query、DeepCT 和 docTTTTTquery 进行了比较。所有这三种方法都依赖于传统的词袋模型（主要是 BM25）进行检索。但重要的是，它们在建立 BM25 索引之前，会重新权衡每篇文档的术语频率和/或扩展每篇文档中的术语集。特别是，doc2query 使用由 seq2seq transformer 模型生成的预定义数量的合成查询（docTTTTquery 使用预先训练的语言模型 T5（Raffel et al.）相比之下，DeepCT 使用 BERT 以上下文感知的方式生成 BM25 的词频成分。

For the latency of Anserini’s BM25, doc2query, and docTTTTquery, we use the authors’ (Nogueira et al., 2019c, a) Anserini-based implementation. While this implementation supports multi-threading, it only utilizes parallelism across different queries. We thus report single-threaded latency for these models, noting that simply parallelizing their computation over shards of the index can substantially decrease their already-low latency. For DeepCT, we only estimate its latency using that of BM25 (as denoted by (est.) in the table), since DeepCT re-weighs BM25’s term frequency without modifying the index otherwise.⁸⁸8In practice, a myriad of reasons could still cause DeepCT’s latency to differ slightly from BM25’s. For instance, the top-$k$ pruning strategy employed, if any, could interact differently with a changed distribution of scores.
在实践中，各种原因仍可能导致 DeepCT 的延迟与 BM25 的延迟略有不同。例如，所采用的顶部 $k$ 剪枝策略（如果有的话）可能会与变化的分数分布产生不同的相互作用。
关于 Anserini 的 BM25、doc2query 和 docTTTTquery 的延迟，我们使用了作者（Nogueira 等人，2019c，a）基于 Anserini 的实现。虽然该实现支持多线程，但它只利用了不同查询之间的并行性。因此，我们报告了这些模型的单线程延迟，同时指出，只需在索引分片上并行计算，就能大幅降低它们本已很低的延迟。对于 DeepCT，我们仅使用 BM25 的延迟来估算其延迟（表中用 (est.) 表示），因为 DeepCT 重新权衡了 BM25 的术语频率，而没有对索引进行其他修改。 ⁸ As discussed in §4.1, we use ColBERT${}_{\textnormal{L2}}$ for end-to-end retrieval, which employs negative squared L2 distance as its vector-similarity function. For its latency, we measure the time for faiss-based candidate filtering and the subsequent re-ranking. In this experiment, faiss uses all available CPU cores.
如第 4.1 节所述，我们使用 ColBERT ${}_{\textnormal{L2}}$ 进行端到端检索，它采用负平方 L2 距离作为向量相似度函数。在延迟方面，我们测量的是基于 faiss 的候选过滤和后续重新排序所需的时间。在本实验中，faiss 使用了所有可用的 CPU 内核。

Looking at Table 2, we first see Anserini’s BM25 baseline at 18.7 MRR@10, noticing its very low latency as implemented in Anserini (which extends the well-known Lucene system), owing to both very cheap operations and decades of bag-of-words top-$k$ retrieval optimizations. The three subsequent baselines, namely doc2query, DeepCT, and docTTTTquery, each brings a decisive enhancement to effectiveness. These improvements come at negligible overheads in latency, since these baselines ultimately rely on BM25-based retrieval. The most effective among these three, docTTTTquery, demonstrates a massive 9% gain over vanilla BM25 by fine-tuning the recent language model T5.
查看表 2，我们首先看到 Anserini 的 BM25 基线为 18.7 MRR@10，注意到其在 Anserini（扩展了著名的 Lucene 系统）中实现的极低延迟，这得益于非常便宜的操作和数十年的词袋顶级 $k$ 检索优化。随后的三个基线，即 doc2query、DeepCT 和 docTTTTquery，每个都带来了决定性的效果提升。由于这些基线最终都依赖于基于 BM25 的检索，因此这些改进在延迟方面的开销可以忽略不计。这三个基线中最有效的是 docTTTTquery，它通过微调最新的语言模型 T5，比传统的 BM25 提高了 9%。

Shifting our attention to ColBERT’s end-to-end retrieval effectiveness, we see its major gains in MRR@10 over all of these end-to-end models. In fact, using ColBERT in the end-to-end setup is superior in terms of MRR@10 to re-ranking with the same model due to the improved recall. Moving beyond MRR@10, we also see large gains in Recall@$k$ for $k$ equals to 50, 200, and 1000. For instance, its Recall@50 actually exceeds the official BM25’s Recall@1000 and even all but docTTTTTquery’s Recall@200, emphasizing the value of end-to-end retrieval (instead of just re-ranking) with ColBERT.
将注意力转移到ColBERT的端到端检索效果上，我们发现它的MRR@10比所有这些端到端模型都要高。事实上，由于召回率的提高，在端到端设置中使用 ColBERT 的 MRR@10 优于使用相同模型的重新排序。除了 MRR@10 之外，我们还发现在 $k$ 等于 50、200 和 1000 时，Recall@ $k$ 的收益也很大。例如，它的 Recall@50 实际上超过了官方 BM25 的 Recall@1000，甚至超过了除 docTTTTTquery 之外的所有其他 Recall@200，强调了 ColBERT 端到端检索（而不仅仅是重新排序）的价值。

The results from §4.2 indicate that ColBERT is highly effective despite the low cost and simplicity of its late interaction mechanism. To better understand the source of this effectiveness, we examine a number of important details in ColBERT’s interaction and encoder architecture. For this ablation, we report MRR@10 on the validation set of MS MARCO in Figure 5, which shows our main re-ranking ColBERT model [E], with MRR@10 of 34.9%.
第4.2节的结果表明，尽管ColBERT的后期交互机制成本低、操作简单，但却非常有效。为了更好地理解这种有效性的来源，我们研究了 ColBERT 交互和编码器架构中的一些重要细节。对于这种消减，我们在图 5 中报告了 MS MARCO 验证集上的 MRR@10，图 5 显示了我们的主要重排 ColBERT 模型 [E]，MRR@10 为 34.9%。

Due to the cost of training all models, we train a copy of our main model that retains only the first 5 layers of BERT out of 12 (i.e., model [D]) and similarly train all our ablation models for 200k iterations with five BERT layers. To begin with, we ask if the fine-granular interaction in late interaction is necessary. Model [A] tackles this question: it uses BERT to produce a single embedding vector for the query and another for the document, extracted from BERT’s [CLS] contextualized embedding and expanded through a linear layer to dimension 4096 (which equals $N_{q}\times 128=32\times 128$). Relevance is estimated as the inner product of the query’s and the document’s embeddings, which we found to perform better than cosine similarity for single-vector re-ranking. As the results show, this model is considerably less effective than ColBERT, reinforcing the importance of late interaction.
由于训练所有模型的成本较高，我们训练了主模型的一个副本，该副本只保留了 12 个 BERT 层中的前 5 层（即模型 [D]），并以 5 个 BERT 层对所有消融模型进行了类似的 20 万次迭代训练。首先，我们要问后期相互作用中的细粒相互作用是否必要。模型 [A] 解决了这个问题：它使用 BERT 为查询和文档分别生成一个嵌入向量，该向量从 BERT 的 [CLS] 上下文嵌入中提取，并通过线性层扩展到 4096 维（等于 $N_{q}\times 128=32\times 128$ ）。相关性是通过查询和文档嵌入的内积来估算的，我们发现在单矢量重新排序时，这个内积比余弦相似度更好。结果表明，该模型的效果大大低于 ColBERT，这也加强了后期交互的重要性。

Subsequently, we ask if our MaxSim-based late interaction is better than other simple alternatives. We test a model [B] that replaces ColBERT’s maximum similarity with average similarity. The results suggest the importance of individual terms in the query paying special attention to particular terms in the document. Similarly, the figure emphasizes the importance of our query augmentation mechanism: without query augmentation [C], ColBERT has a noticeably lower MRR@10. Lastly, we see the impact of end-to-end retrieval not only on recall but also on MRR@10. By retrieving directly from the full collection, ColBERT is able to retrieve to the top-10 documents missed entirely from BM25’s top-1000.
随后，我们询问基于 MaxSim 的后期交互是否优于其他简单的替代方案。我们测试了用平均相似度取代 ColBERT 最大相似度的模型 [B]。结果表明，查询中的单个术语非常重要，要特别注意文档中的特定术语。同样，该图强调了我们的查询增强机制的重要性：如果没有查询增强[C]，ColBERT 的 MRR@10 会明显降低。最后，我们看到端到端检索不仅对召回率有影响，而且对 MRR@10 也有影响。通过直接从全集中检索，ColBERT 能够检索到 BM25 的前 1000 名中完全遗漏的前 10 名文档。

Lastly, we examine the indexing throughput and space footprint of ColBERT. Figure 6 reports indexing throughput on MS MARCO documents with ColBERT and four other ablation settings, which individually enable optimizations described in §3.4 on top of basic batched indexing. Based on these throughputs, ColBERT can index MS MARCO in about three hours. Note that any BERT-based model must incur the computational cost of processing each document at least once. While ColBERT encodes each document with BERT exactly once, existing BERT-based rankers would repeat similar computations on possibly hundreds of documents for each query.
最后，我们检查了 ColBERT 的索引吞吐量和空间占用。图 6 报告了使用 ColBERT 和其他四种消融设置对 MS MARCO 文档进行索引的吞吐量，这四种设置在基本的分批索引基础上分别实现了第 3.4 节所述的优化。根据这些吞吐量，ColBERT 可以在大约三小时内完成 MS MARCO 索引。需要注意的是，任何基于 BERT 的模型都必须承担对每个文档至少处理一次的计算成本。ColBERT 对每份文档都进行了一次精确的 BERT 编码，而现有的基于 BERT 的排序器可能会对每次查询的数百份文档重复类似的计算。

Table 4 reports the space footprint of ColBERT under various settings as we reduce the embeddings dimension and/or the bytes per dimension. Interestingly, the most space-efficient setting, that is, re-ranking with cosine similarity with 24-dimensional vectors stored as 2-byte floats, is only 1% worse in MRR@10 than the most space-consuming one, while the former requires only 27 GiBs to represent the MS MARCO collection.
表 4 报告了 ColBERT 在不同设置下的空间占用情况，我们减少了嵌入维度和/或每个维度的字节数。有趣的是，最节省空间的设置，即用余弦相似度重新排序，24 维向量存储为 2 字节浮点数，在 MRR@10 中只比最耗费空间的设置差 1%，而前者只需要 27 GiB 就能表示 MS MARCO 数据集。