基于稀疏模型的前向索引在神经排序中的高效应用

266使用前向索引的高效神经排序JurekLeonhardtL3S研究中心德国汉诺威leonhardt@L3S.deKoustavRudra印度理工学院（印度矿业学院），印度丹koustav@iitism.ac.inMeghaKhoslaL3S研究中心德国汉诺威khosla@L3S.de摘要AbhijitAnandL3S研究中心德国汉诺威aanand@L3S.deAvishekAnandL3S研究中心德国汉诺威anand@L3S.de1介绍神经文档排序方法，特别是Transformer模型，在排序性能方面取得了令人印象深刻的进步。然而，使用这种过度参数化模型的查询处理是资源和时间密集型的。在本文中，我们提出了FAST-FORWARD索引-一个前向索引依赖于高效的稀疏模型进行检索，并且仅在恒定时间内查找文档和段落的预先计算的基于密集变换的向量表示，以在查询处理期间进行快速的基于CPU的语义相似性计算 我们提出了索引修剪和理论上接地早期停止技术，以提高查询处理吞吐量。 我们在TREC-DL数据集上进行了广泛的大规模实验，并显示出仅使用CPU的混合索引在性能和查询处理效率方面的改进。由于词汇和语义相似性的互补优势，FAST-FORWARD索引可以使用插值提供CCS概念• 信息系统→检索模型和排名。关键词检索，稠密，稀疏，排序，插值ACM参考格式：Jurek Leonhardt，Koustav Rudra，Megha Khosla，Abhijit Anand，andAvishek Anand.2022 年 使 用 前 向 索 引 的 高 效 神 经 排 名 在 ACM WebConference 2022（WWW '22）的会议记录中，2022年4月25日至29日，虚拟活 动 ， 法 国 里 昂 。 ACM ， 美 国 纽 约 州 纽 约 市 ， 11 页 。https://doi.org/10.1145/3485447.3511955主要开展了L3S研究中心的研究。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上版权的组成部分，这项工作所拥有的其他人比ACM必须尊重。允许使用学分进行摘要 以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。请求权限请发邮件至permissions@acm.org。WWW©2022计算机协会。ACM ISBN 978-1-4503-9096-5/22/04。. . 十五块https://doi.org/10.1145/3485447.3511955标准的方法为ad-hoc文件排名采用检索阶段的快速，高召回候选人的选择和更昂贵的重新排名阶段。最近的方法主要集中在基于神经变换器的模型上，用于检索[6，18，24]和重新排序[1，4，12，14，22，29]。然而，有限的工作已经做了高效的端到端的解决方案，排名长文件的背景下。长文档的检索和重新排序都存在挑战检索阶段的主要策略是基于术语或词汇匹配。为了实现高效的检索，倒排索引，称为稀疏索引，已被用作传统信息检索中的工作马，利用术语空间中的稀疏性来修剪掉大量的不相关文档。众所周知，稀疏索引会受到词汇不匹配问题的困扰，导致它们将语义相似的文档排在较低的位置。为了缓解这一问题，最近在段落检索的背景下提出了密集索引然而，我们发现检索较长的文档时，即每个文档有多个向量例如，在一种情况下，使用密集索引检索1000个文档的召回率为0.58，而稀疏索引为0.70（参见表2）。对于重新排序阶段，交叉注意模型是优选的，因为它们能够估计语义相似性，但是这些模型在计算上是昂贵的。因此，为了保持总体端到端排名成本可控，在重新排名阶段考虑较少数量的文档，或者使用具有较少参数的更精简的模型，从而降低排名性能。本文的目的是提出一种有效的端到端的方法，在不影响效率的情况下对长文档进行排名。首先，我们观察到双编码器模型可以用于有效地计算给定查询的文档的语义相似度（参见。 表1）。 基于这一观察，我们提出了一种前向索引方法，该方法基于插值对文档进行排名，使用关于查询的语义相似性得分（来自重新排名阶段）和词汇匹配得分（来自检索阶段）的线性组合对文档进行评分[1]。我们提出的文档的向量前向索引，称为Fast-Forward索引，包含对应于其组成段落的每个文档的预先计算的向量的列表。使用FAST-FORWARD索引的查询处理需要使用稀疏索引检索文档，计算语义相似度WWWJurek Leonhardt，Koustav Rudra，Megha Khosla，Abhijit Anand，and AvishekAnand267通过一系列的索引查找和点积和插值的分数检索的文件。因此，FAST-FORWARD索引结合了稀疏模型和密集模型的优点，同时消除了对昂贵的最近邻搜索（如密集检索中使用的）或上下文的GPU加速重新排名的需要因此，我们的工作是复杂的，可以与其他旨在改善检索的技术相结合，例如CLEAR [11]或cT5qeR y [35]。此外，这允许我们对每个查询重新排序更多数量的文档，从而缓解稀疏检索器的上述词汇我们的第二个观察是，在重新排名阶段的查询处理成本是由点积计算之间的查询和通道向量占主导地位。 为此，我们提出了两种技术，以提高效率，在查询处理中使用快速向前索引-顺序合并和提前停止。在顺序合并中，我们通过组合对应于相邻但相似的段落的表示来大幅减少每个文档的向量数量这不仅提高了查询处理效率，而且减少了索引的内存占用。早期停止利用稀疏分数的自然排序，通过保持密集分数的最大分数估计来避免不必要的索引查找。我们进行了广泛的实验评估，以显示性能的好处，前向索引和我们的查询处理技术。 我们发现，使用双编码器模型的插值始终比使用相同模型的标准重新排序产生更好的性能。此外，在插值之前增加稀疏检索深度提高了最终排名。最后，我们展示了如何优化的FAST-FORWARD索引加速排名，大大减少了查询处理时间相比，混合检索，同时保持相当的性能。总而言之，我们做出了以下贡献：我们提出了一个有效的方法，为特设的文件排名任务的快速向前索引。我们提出了新的查询处理算法我们进行了广泛的实验评估，以建立强大的效率收益，由于我们的前向索引和查询处理技术。2相关工作经典的排名方法，如BM 25或查询可能性模型[20]，依赖于倒排索引进行有效的第一阶段检索，存储术语级统计数据，如术语频率，逆文档频率和位置信息。我们将这种检索方式称为稀疏检索，因为它假设稀疏文档表示。最近，Dai和Callan[6，7]提出了DEEP-CT，其存储用于段落和文档检索的反转索引中的术语的上下文化分数类似地，DeepImpA ct [31]使用扩展术语丰富文档集合，以学习改进的术语影响。Spl AD e [8]旨在使用经过训练的上下文Transformer模型和术语权重的稀疏正则化来丰富稀疏文档表示。TILDE [43]使用深度查询和文档似然模型在这项工作中，我们使用香草倒排索引与标准的长期统计的第一阶段检索。另一种设计策略是使用双编码器来学习使用上下文模型的段落或文档的密集向量表示[10，17，18]。然后在离线阶段[16]对密集向量进行索引，其中检索类似于在给定向量化查询的情况下执行近似最近邻（ANN）搜索因此，已经有大量的后续工作通过改进预训练[2]，优化技术[11]和负采样[36，41]来提高双编码器模型的性能在这项工作中，我们使用双编码器来计算查询和段落之间的语义相似度一些方法还提出了通过在查询和段落嵌入之间进行轻量级聚合来对双编码器模型进行架构修改[3，12，15，25，26，41，42]，这表明基于标准术语的检索策略具有。Nogueira等人[35]提出了一个简单的文档扩展模型。请注意，这些方法是对我们工作的补充，因为它们可以与FAST-FORWARD索引相结合。语义相似性模型 虽然词汇匹配模型通常在第一阶段检索中使用，并且已知可以实现高召回率，但准确确定语义相似性的能力在后续更复杂且计算成本更高的重新排序阶段中至关重要，以缓解词汇不匹配问题[5，7，28，30，34]。在IR中使用平滑方法[19]、主题模型[40]、嵌入[33]、个性化模型[27]和其他技术对给定查询的文档的语义相似度进行了大量研究。 在这些经典的方法中，排名是通过插值的语义相似度得分与词汇匹配得分从第一阶段的检索。最近的方法主要由主要用于重新排序的过度参数化上下文模型所主导[1，4，12，14，22，29]。与密集检索中使用的双编码器模型不同，上述排名模型中的大多数都将查询和文档的串联作为输入。由于每个文档都必须与查询字符串结合处理，因此这种组合输入导致大检索深度的查询处理时间更长使用上下文模型进行文档排序的另一个关键限制是Transformer模型的最大可接受输入标记 一些策略通过文档截断[29]和分块到段落[4，37]来解决这种长度限制。然而，基于组块的策略的性能取决于组块的属性，即。通道长度或连续通道之间的重叠[38]。 最近的建议包括两个阶段的方法，其中通过选择文档的相关部分生成特定于查询的摘要，然后对查询和摘要文档进行重新排序策略[13，23]。基于插值的秩。与经典方法不同，其中分数插值是规范，使用上下文模型的语义相似性不一致地与匹配分数相结合最近，Wang et al.[39]表明，基于BERT的检索器和稀疏检索方法的插值可以提高性能。此外，他们分析了插值在基于BERT的密集检索策略（ANCE，RepBERT）中的作用，发现仅密集检索是不够的，但有必要使用BM 25分数进行插值···使用前向索引的高效神经排序WWW268（）下一页（）（）S（）下一页SD（）（）K K3基于插值 重新排名在本节中，我们正式介绍重新排序的问题我们进一步比较标准和插值为基础的重新排名。3.1问题陈述给定查询的文档或段落的检索通常分两个阶段进行：博士'19博士'20Passa ge'19重新排序（稀疏）检索方法从大型语料库中检索一组文档。在第二阶段，另一个模型，这通常是更昂贵的计算，重新排序检索文档再次。重新排名的步骤被认为是非常重要的，对于小检索深度需要高性能的任务例如问答。在稀疏检索中，我们表示检索到的前k个S文档从查询q的稀疏索引作为Kq。稀疏的分数表1：在检索深度kS=1000处重新排序与内插之间的性能比较（nDCG@10）。证实了词汇分数确实持有互补的相关信号相比，语义分数。我们还观察查询-文档对q，d表示为bSy= q，d。对于重新排序部分，我们在这项工作中专注于自我注意力模型（如这些模型通过创建查询和文档的（内部）高维密集表示来操作，重点关注它们的语义结构。 我们将这些模型的输出称为密集或语义得分，并将其表示为D q，d。由于自我注意的二次时间复杂度w.r.t. 文档长度，长文档通常被分成段落，然后将文档的分数计算为其最大值。通过分数：双编码器方法具有更好的重排序性能。4有效插值如第3节所述，基于插值的重新排序已知在应用于第一阶段（稀疏）检索步骤的结果时提高性能。然而，计算的candid（cf.等式（2））可能非常慢，其中交叉注意模型[4，37]比基于双编码器的排名策略[2，26]更昂贵。在本节中，我们提出了几种更有效地实现基于插值的重新排序的方法。q，d =maxDq，pi（1）pi∈d4.1混合检索混合检索类似于标准的基于插值的重新排序这种方法被称为maxP [4]。q（cf. 第3节）。关键的区别在于，密集分数是D（q，d）查询q的检索方法从检索KS开始从稀疏索引。对于每个检索到的文档d∈Kq，并不是针对所有查询-文档对计算相反，这种方法是在假设CXD是密集检索的情况下操作的计算相应的密集得分RND（q，d）这个密集的分数模型，该模型检索文档di和它们的分数dqq，dius，在给定查询q的情况下执行最近邻搜索。一只混血寻回犬然后可以用于对检索到的集合重新排序以获得最终排序。然而，最近的研究表明，将稀疏检索器和密集检索器的检索集稀疏检索器（sparseretriever），也可以有益于重新排序[1]。对于查询q，我们检索两组文档，Kq和Kq，使用稀疏和密集的检索，检索。注意twDo处的thS为此，采用插值方法，其中查询-文档对的最终得分计算如下：（q，d）=α·检索到的集合通常不相等。[ 26 ]中提出的一种策略将所有文档按q q排序，近似缺失的分数。在我们的实验中，我们发现，只有考虑到docu-从Kq中抽取部分进行最终排序，并丢弃其余部分设置α=0恢复标准的重新排序程序。由于稀疏模型检索到的文档集是好.因此，最终的S得分计算如下：.<$D（q，d）d∈Kq通常较大（例如，k S = 1000），计算每个查询-文档对的密集分数在计算上可能非常昂贵。在<$（q，d）=α·<$S（q，d）+（1−α）·DS（q，d）dgKq（三）本文主要研究基于插值的重排序算法的有效实现，特别是稠密分数的计算。混合检索中的重新排序步骤本质上是对插值分数的排序操作，与标准重新排序相比，所需时间可以忽略不计3.2重新排名与插值4.2FasT-前向索引为了比较传统的重新排序与插值（cf.第3.1节），我们从稀疏BM 25索引中检索k S = 1000个文档，并使用密集方法计算每个查询-文档对的相应语义得分然后，我们重新排名的文件和没有插值。结果（cf。表1）清楚地表明，插值在文档和段落重新排序中均优于纯语义评分。这第4.1节中描述的混合方法有两个明显的缺点。首先，为了检索KDq，必须执行（近似）最近邻搜索，这是耗时的。其次，一些查询文档分数被遗漏，导致不完整的插值。在本节中，我们提出了一种快速向前索引，作为计算已知文档的密集分数的有效方法，TCT-ColBERT0.6850.6170.694BERT-CLS0.5200.5220.578In terpoL aTionTCT-ColBERT0.6960.6370.708BERT-CLS0.6120.6260.617WWWJurek Leonhardt，Koustav Rudra，Megha Khosla，Abhijit Anand，and AvishekAnand269检索匹配语义文档得分相似度前一名提前停止当前top-k（）下一页D（）下一页一AA一一一一一索引查找嵌入空间(a) maxP索引的顺序合并。est. 最佳语义得分(b) 插补期间提前停止图1：可以应用于Fast-Forward索引的优化技术顺序合并将相似的连续通道的表示组合为它们的平均值。请注意，p3和p5没有合并，因为它们不是连续的通道。提前停止通过计算密集分数的近似上界来减少插值步骤的数量这个例子描述了最极端的情况，其中只需要top-1文档。上述问题。具体来说，FAST-FORWARD索引建立在两塔密集检索模型之上，该模型将查询-文档对的得分计算为点积D（q，d）=这类模型的例子是ANCE [41]和TCT-ColBERT [26]。由于查询和文档表示对于双塔模型是独立的，因此我们可以预先计算文档表示，对于语料库中的每个文档d，然后，这些文档表示被存储在一个高效的哈希映射中，允许在恒定的时间内进行查找创建索引后，查询-文档对的得分可以计算为其中上标FF指示在FAST-FORWARD索引中对预先计算的文档表示在检索时，每个查询只需要计算一次blog q由于查询通常很短，这可以在CPU上完成。4.3通过Seq.聚结一般情况下，密集索引和密集检索的一个主要缺点是最终索引的大小。这是由两个因素造成的：首先，与稀疏索引相比，高维密集表示不能像稀疏向量那样有效地存储其次，密集编码器通常是基于变换器的，由于其相对于输入的二次时间复杂度，对它们的输入长度施加（软）限制因此，长文档在索引之前被分成段落（maxP索引）。因为索引大小的增加对检索有负面影响延迟，对于最近邻搜索和我们的方法所使用的Fast-Forward索引，我们利用顺序合并方法作为在maxP索引中动态组合单个文档内的连续段落的表示的方式。其思想是减少单个文档索引中段落表示的数量。这是通过利用文档固有的主题局部性来实现的[21]。例如，单个文档可能包含关于多个topic的信息;由于人类读者自然摄取信息的方式，我们期望文档被创作为显示单个主题。算法1：通过顺序合并压缩密集maxP索引输入：文档的通道向量列表P（原始顺序），距离阈值δ输出：合并的通道矢量P′1P′←空列表2A←3 对于P中的每个 v，4如果第一次迭代，则//什么都不5else ifcosine_distance（v，A）≥δthen6将A附加到P′7A←8将V加到A9A ←平均值（A）10端部11 将A附加到P′12 返回P′大多数是在连续的段落中，而不是在整个文件中传播。我们的方法旨在将编码相似信息的连续通行证表示相结合。为此，我们采用余弦距离函数和控制聚结程度的阈值参数δ。在单个文档中，我们以原始顺序遍历其通道向量，并保持一个集合，其中包含已处理通道的表示，并连续计算所有向量的平均值。对于每个新的通道向量v，我们计算它的余弦距离。如果它超过距离阈值δ，则将中的当前通道组合为它们的平均表示。之后，从中移除组合通道并重新计算。该方法在算法1中示出。图1a显示了合并后的索引示例。据我们所知，到目前为止还没有其他的前向索引压缩技术使用前向索引的高效神经排序WWW270（）下一页≤（）下一页（·）（·）、（）下一页2N≤（）下一页（）下一页（）下一页（·）（·）算法2：提前停止的插值输入：查询q，稀疏检索深度kS，截断深度k，插值参数α输出：近似的前k个得分Q1Q←大小为k2 sD← −∞3 smin← −∞4 对于稀疏q中的每个d，kSdo5如果Q是满的，6smin←从Q7sbest←α·S（q，d）+（1−α）·sD8ifsbestsmin然后//提前停止9将smin代入Q10个断裂// approximate max.稠密分数11sD←max（qD（q，d），sD）12s←α·<$S（q，d）+（1−α）·<$D（q，d）13将max（s，smin）放入Q14的端15 返回Q4.4提前停止法快速插补如第3节所述，通过对稀疏和密集检索模型的分数进行密集表示是预先计算的，并且可以在检索时在Fast-Forward索引中查找此外，增加稀疏检索深度kS，使得kS>k，其中k是最终该方法在算法2和图1b中示出。 由于密集分数ε D通常是非归一化的，因此上限ε D在实践中是未知的。因此，我们通过使用在任何给定步骤中观察到的最高稠密分数来近似它4.1理论分析 我们首先表明，早期停止的标准，当使用真正的最大值的密集分数，是足以获得前k分数。4.1. 让sD，如算法2中所使用的，是密集分数的真正最大值。那么返回的分数就是实际的top-k分数。P屋顶。首先，注意稀疏分数，dSq，di，已经针对给定查询以降序通过构造，优先级队列Q总是包含对应于到目前为止解析的列表假设在解析k个分数之后，Q是满的。现在，使用在递减序列中接下来找到的稀疏分数和所有密集分数的最大值sD来计算可能的最佳分数sbest（cf.第7行）。如果sbest小于Q中的最小值，则Q已经包含了前k个分数。 要看到这一点，请注意sbest的第一个分量是所有看不见的稀疏分数中最大的（因为列表是排序的），并且s D是我们假设的密集分数的最大值。 □接下来，我们表明，可以通过使用样本最大值来实现前k个分数的良好近似。 为了证明我们的主张，我们使用Dvoretzky-Kiefer-Wolfowitz（DKW）不等式[32]。让我们来看看4.2. 设X1，X2，.，Xn是n个实值独立同分布的随机变量，其累积分布函数为F.设Fn表示经验累积分布函数，即1 .一、nni=1导致索引查找次数的增加在本节中，我们提出了一个扩展到Fast-Forward索引，允许提前停止，即。避免了一些非-根据DKW不等式，以下估计成立：Pr.sup（Fn（x）− F（x））> εε≤ e−2nε 2εε ≥1ln 2.（九）必要的查找，对于kS>k的情况，通过近似最大可能的密集分数。早期停止方法需要文档是按其稀疏性排序的，x∈R下面我们证明，如果sD2N被选为最大值scores≤S q，d.由于检索到的文档的数量kS是有限的，因此对于相应的密集的分数使得<$D（q，d）≤sD<$d∈Kq.由于检索到的文件-S从稠密分数集中抽取的大随机样本的概率，则从稠密分数中独立且均匀随机选择的任何给定稠密分数大于sD的概率项Kq在样本量上是指数级的小S按稀疏分数排序，我们可以同时通过在文档的有序列表上迭代来执行内插和重新排序：令di是稀疏检索器排序的第i个最高文档回想一下，我们计算最终得分如下：<$（q，di）=α·<$S（q，di）+（1−α）·<$D（q，di）（6）4.3. 设x1，x2，.， xn是从具有累积分布函数F的密集分数的分布中抽取的实值独立且同分布的随机样本。令z=max（x1，x2，...，xn）。然后，对于每一个ε>ε1 ln 2，我们得到：如果i>k，我们可以通过利用上述排序来计算k q，di的上界sbest=α·S （ q ， di−1 ） + （ 1−α ） ·sD（7）反过来，这允许我们停止插值和重新排序，如果sbestsmin，其中smin表示第k个文档的得分，当前排名（即，当前排名最低的文档）。实际上，这意味着一旦最高可能的内插得分fl（q，di）太低而不能产生差异，我们就停止计算。Pr（F（z）<1 − n）≤ e−2n <$2。（十）P屋顶。设Fn表示如上所述的经验累积分布函数。具体来说，Fn x等于小于或等于x的变量的分数。我们有Fn z=1。根据引理4.2，我们推断Pr（Fn（z）− F（z）> n）≤ e−2n <$2。 （十一）代入Fn（z）= 1，我们得到等式（10）。□文件数量，提高性能。这样做的一个缺点是，检索到的文档数量的增加也Fn（ x）=1{Xi≤x}，x ∈ R.（八）WWWJurek Leonhardt，Koustav Rudra，Megha Khosla，Abhijit Anand，and AvishekAnand271DD这意味着从稠密分数集合中随机选择的任何随机变量X小于或等于sD的概率都以高概率大于或等于1−D，即。Pr（P（X≤s）≥ 1−n）≥ 1−e−2n <$2，（12）其中PD表示密集分数的概率分布。这意味着，随着我们的样本量增加，直到达到k，近似值会提高。请注意，在我们的情况下，密集分数被排序（通过相应的稀疏分数），因此i.i.d.假设不能保证。然而，我们观察到密集分数与稀疏分数正相关。 我们认为，由于这种相关性，我们可以很好地近似最大分数。5评估设置我们考虑以下基线：词法或稀疏检索器依赖于查询和文档之间基于术语的匹配。我们考虑使用基于术语的检索信号的BM 25和类似于BM 25的DEEP-CT [ 6 ]，但是术语权重是以上下文化的方式学习的。语义的或密集的检索器检索的文档是se-extensive的。在公共嵌入空间中与查询类似。我们考虑TCT-ColBERT [26]和ANCE [41]。这两种方法都基于BERT编码器。大型文档在索引之前被分成段落（maxP）。这些密集检索器使用精确（蛮力）最近邻搜索，而不是近似最近邻（ANN）搜索.混合检索插值稀疏和密集检索分数。我们考虑CLEAR [11]，一个检索模型，补充词汇模型与语义匹配。此外，我们考虑将第4.1节中描述的混合策略作为基线，使用上面的密集猎犬上下文密集重排序器对文档进行重排序，被一只稀疏的寻回犬（BM 25）捕获 每个查询-文档对都被输入到重新排序器中，重新排序器输出相应的分数。在本文中，我们使用BERT-CLS重排序器，其中对应于分类标记的输出被用作分数。请注意，重新排序是使用完整的文档（即，文件不分成段落）。如果输入超过512个标记，则会被截断。数据集和超参数。 我们对TREC深度学习跟踪的三个数据集（Doc '19，Doc'20和Passage'19）进行了实验，以评估MSMARCO集合上检索和重新排名策略的有效性和效率。每个测试集总共有200个查询。 我们使用Py S e RI n I工具包[25]进行检索实验，并使用MS MARCO开发集确定α= 0。2对于TCT-ColBERT，α=0。5，对于ANCE和α = 0。7个BERT-CLS。延迟计算为评分、插值和排序成本之和令牌化成本被忽略。 我们报告测试集中每个查询的平均处理时间。在适用的情况下，密集模型使用256的批量。更多详情见附录A.1。6实验结果在本节中，我们进行了大规模的实验，以显示所提出的快速向前索引的有效性和效率。RQ 1.与其他方法相比，使用双编码器的基于插值的重新排序方法如何？ 在表2中，我们报告了稀疏、密集和混合检索器、重排序器和插值的性能。首先，我们观察到密集检索策略在nDCG方面比稀疏检索策略表现得更好，但除了在PASSA ge'19上之外，召回率都很差。DEEP-CT学习的上下文权重优于基于tf-idf的检索（BM 25），但低于密集语义检索策略（TCT-ColBERT和ANCE）。然而，检索到的文档之间的重叠是相当低的，反映了密集检索不能很好地匹配查询和文档术语。第二，基于双编码器的（TCT-ColBERT和ANCE）比上下文（BERT-CLS）重排序器更好地执行在此设置中，我们首先使用稀疏检索器检索kS=1000个文档，并对它们进行重新排序。该方法利用第一阶段的高召回率，并通过密集语义重排序器将相关文档提升到列表的顶部然而，重新排序通常是耗时的，并且需要GPU加速。TCT-ColBERT和ANCE相对于BERT-CLS的改进也表明基于双编码器的重排序策略优于基于交叉交互的方法。然而，这种差异也可以归因于BERT-CLS不遵循maxP方法（参见第3.1节）。最后，基于插值的重新排序，它结合了稀疏和密集的分数的好处，显着优于BERT-CLS重新排序和密集检索。回想一下，密集重排序器仅基于密集分数操作，并且丢弃查询-文档对的稀疏BM 25分数。最近的研究[2，3，10，11]的证据也支持基于插值的方法的优越性。RQ 2. FA sT-ForwA rd索引是否允许在更高的检索深度进行有效的插值 表3和表4分别显示了对文档和段落数据集进行重新排序、混合检索和插值的结果。度量计算两个稀疏检索深度，KS=1000和KS=5000。我们观察到，在分数计算中考虑稀疏分量（如通过插值和混合方法所做特别是，一些查询收到了相当大的召回提升，捕获更相关的文档与大检索深度。与其他方法相比，基于FAST-FORWARD索引的插值实现了显著更低的延迟。预计算文档表示允许在检索时间期间快速查找由于只有查询需要通过密集模型进行编码，因此检索和重新排名都可以在CPU上执行，同时仍然在查询处理时间上提供相当大的改进。请注意，对于BERT-CLS，输入长度是有限的，导致文档被截断，类似于firstP方法。因此，延迟要低得多，但反过来性能也会受到影响。这里需要注意的是，原则上，FAST-FORWARD指数也可以与firstP模型结合使用。如4.1节所述，混合检索策略显示表现不错。然而，由于密集索引需要最近邻搜索来进行检索，因此查询处理延迟比使用前向索引的插值高得多。最后，密集重排序器不能从增加的稀疏检索深度中可靠地获益;相反，性能下降使用前向索引的高效神经排序WWW272DocAP1kR1knDCG10AP1kR1knDCG10AP1kR1knDCG10SparseReT rievaLBM250.331零六九七0。519 1−30.4040.8090。527 1−30.3010.7500。5061−3深CT--0.544-0.4220.7560.551高密度树脂TCT-ColBERT0.2790.5760. 612 1 0.3720.7280. 586 1，20.3910.792 0.670安斯0.2540.5100. 633 1 0.4010.6330.3710.755 0.645HybridRET rievaL透明--0.5110.8120.699重新排序TCT-ColBERT0.3700.6970.6850.4140.8090.6170.4230.750 0.694安斯0.3360.6970.6540.4260.8090.6300.3890.750 0.679BERT-CLS0.283零六九七0。520 1−30.3290.8090。522 1−30.3530.7500。578 1、2In terpoL aT ionTCT-ColBERT 10.4060.6970.6960.4690.8090.6370.4380.750 0.708表2：检索性能。检索器使用深度kS=1000（稀疏）和kD=10000（密集）。密集检索器检索段落并为文档执行maxP聚合。CLEAR和DEEP-CT的评分取自相应的论文[10，11]。 上标表示使用具有符号的双配对检验的统计学显著改善。 95%[9]。HybridRETrievaL毫秒每个查询博士kS=1000kS=5000kS=1000kS=5000AP1kR1knDCG20AP1kR1knDCG20AP1kR1knDCG20AP1kR1knDCG20表3：文件检索性能。在CPU和GPU上报告kS=5000的延迟。合并后的FAST-FORWARD索引被压缩到其原始大小的大约25%混合回收器使用kD=1000的密集回收深度。上标表示使用具有符号的双配对检验的统计学显著改善 95%[9]。在某些情况下。 这种趋势对于具有较高kS值的文档检索数据集更为明显。 我们假设密集排名只关注语义匹配，对主题漂移很敏感，导致他们将不相关的文档排在前5000名。RQ 3. 是否可以通过使用顺序合并来减少Fast-ForwArd索引的大小来提高重新排序的效率为了评估这种方法，我们首先采用MS MARCO语料库的预训练的TCT-ColBERT密集索引，应用具有不同δ值的顺序合并，并评估每个结果压缩ANCE20.3870.6970.6730.4900.8090.6550.4170.7500.680BERT-CLS30.3650.6970.6120.4600.8090.6260.3780.7500.617BM25，TCT-ColBERT5820.3940.6970.6550.3850.7290.6450.4630.8090.6150.4690.8520.621BM25，安斯5820.3790.6970.6330.3730.7270.6280.4790.8090.6240.4880.8460.632重 新 排 序TCT-ColBERTANCE1189 +1189 +220.3700.3360.6970.6970.6320.6140.3340.3040.7030.6470。60910.6070.4140.4260.8090.8090。58710。5953 0.4050.4220.7940.7610。5851、3、40.604BERT-CLS185 +20.2830.6970。4941−50.1590.5590.2890.3290.8090。5121−50.2210.7270。3751−5In terpoL aT ionTCT-ColBERT1一千一百八十九+十四0.4060.6970.6550.4110.7450.6530.4690.8090.6210.4780.8380.626FAST-向前2530.4060.6970.6550.4110.7450.6530.4690.8090.6210.4780.8380.626合并2ANCE3109一千一百八十九+十四0.3790.3870.6970.6970.6300.6380.3790.3930.7320.7320.6250.6390.4400.4900.8090.8090。59410.6300.4470.5020.8370.8280.6070.640WWWJurek Leonhardt，Koustav Rudra，Megha Khosla，Abhijit Anand，and AvishekAnand273HybridRETrievaLBM25，TCT-ColBERT毫秒每个查询307kS=1000kS=5000AP1k RR10AP1kRR100.4340.8940.454零点九零二BM25，安斯3070.4100.8560.4220.864重新排序In terpoL aT ion表4：PassaGE'19的回收性能 延迟是报告为kS = 5000的CPU和GPU上。 混合回收器使用k D = 1000的密集回收深度。图2：应用于Doc'19的顺序合并。该图显示了索引大小减少的数量的通道和相应的度量值的FasT-前插与TCT-CoIBERT。使用Doc'19测试集进行索引结果如图2所示。 很明显，通过组合段落表示，在最极端的情况下，索引中的向量数量可以减少80%以上，其中每个文档只剩下一个向量。同时，性能与表示的粒度相关。然而，下降幅度相对较小。例如，对于δ = 0。025，索 引 大 小 减少了 一半以 上 ， 而 nDCG 大约 减 少 了 0 。 015（3%）。此外，表3显示了文档数据集上的合并后向前我们选择了对应于δ= 0的指数。035（TCT-ColBERT）δ = 0。003（ANCE），两者都被压缩到约-体积是原来的25%。这反映在查询处理延迟上，减少了一半以上。正如预期的那样，总体性能在一定程度上下降，但是，除了一种情况外，这些下降在所有情况下都不具有统计学意义。延迟（索引大小）和性能之间的权衡可以通过改变阈值δ来控制。图3：对于在PassaGE'19上使用ANCE在不同截止深度k处提前停止的插值，每个查询的平均FasT-前向索引查找RQ 4.是否可以通过限制FA sT-ForwA rd查找的次数来提高重新排序的效率？ 我们首先在Passage'19数据集上评估4.4节中描述的早期停止方法的效用。 图3示出了在插值期间在Fast-Forward索引中执行的查找的平均次数。截止深度k。我们观察到，对于k = 100，早停止已经导致查找次数减少近20%。减小k进一步导致查找的显著减少，从而导致改进的查询处理延迟。由于较低的截止深度（即k100）通常用于下游任务，例如问题回答，对于k的低值的早期停止方法被证明是特别有帮助的。<表4显示了应用于传代数据集的早期停止，以检索前10个传代并计算倒数排名。 很明显，即使该算法近似于最大密集分数（cf. 第4.4节），所得到的性能是相同的，这意味着近似在两种情况下都是准确的，并且没有引起任何性能损失。此外，与标准插值相比，查询处理时间减少了一半。请注意，提前停止取决于α的值，因此TCT-ColBERT和ANCE之间的延迟不同。7结论在本文中，我们提出了FAST-FORWARD索引，一个简单而有效的和高效的基于查找的插值方法，结合文档检索和重新排序。前向索引基于密集的双编码器模型，利用文档表示可以被预处理和存储的事实，在恒定的时间内提供高效的访问。使用插值，我们观察到增加的性能相比，混合检索。此外，由于我们的优化技术，顺序合并和早期停止，我们在内存占用和查询处理延迟方面实现了高达75%的改进。同时，我们的方法只需要CPU计算，完全消除了昂贵的GPU加速重新排名的需要致谢该项目的部分资金由欧盟地平线2020号拨款提供。 871042（ SoBigData++ ） 和 832921 （ MIRROR ） 以 及 BMBF 批 准 号01DD20003（LeibnizKILabor）。TCT-ColBERTANCEBERT-CLS186+ 20.4260.8270.4390.842186+ 20.3890.8360.3920.857185+ 20.3530.7150.2750.576TCT-ColBERTFAST-向前提前停止ANCEFAST-向前提前停止BERT-CLS186+ 140.4380.8940.460零点九零二1140.4380.8940.460零点九零二72