JointRank：基于重叠分块与PageRank进行单次并行重排序
仅用于站内搜索，没有排版格式，具体信息请跳转上方微信公众号内链接
在当今的信息检索系统中，无论是网络搜索、推荐系统还是检索增强生成（RAG），从海量候选池中高效筛选出相关项都是一个核心挑战。
传统的列表式重排序器虽然能够通过同时考虑多个候选项目来提高相关性，但在处理大型数据集时常常受限于模型输入大小或导致质量下降。
JointRank:RankLargeSetwithSinglePass
https ://arxiv. org/pdf/2506. 22262
为了解决这一难题，来自JetBrains的研究员EvgenyDedov提出了一种名为JointRank的新型模型无关方法，旨在以单次通过（singlepass）的方式实现对大型数据集的高效重排序。
现有方法在处理大量候选项目时主要面临以下挑战：
模型输入大小限制：大多数列表式重排序模型都有输入长度限制，难以一次性处理成百上千的候选项目。
计算成本与延迟：即便模型支持较长的上下文，处理超长序列也会带来巨大的计算成本，导致显著的推理延迟。
多步迭代的低效性：诸如滑动窗口排序、集合式堆排序等迭代方法虽然减少了单次模型调用的负担，但仍需多次顺序调用重排序模型，这在实时应用中会累积产生高延迟，影响用户体验。
排序（Ranking）是指根据给定查询对文档集合进行排列，目标是输出一个按与查询相关性排序的Top-k文档子集。
PointwiseModels（点对点模型）：独立地为每个（查询，文档）对分配一个相关性分数。
特点：易于并行化，常用于第一阶段检索。
局限性：缺乏上下文信息，每个文档独立打分可能导致排序偏差。
PairwiseModels（两两比较模型）：给定查询，直接比较两个文档的相关性，例如（查询，文档1，文档2）。
ListwiseModels（列表式模型）：同时对一组文档进行排序，例如（查询，文档1，文档2，…，文档n）。
特点：由于能够对候选集进行整体性考量，通常能产生最准确的排序结果。
局限性：计算成本高昂，且通常受限于输入大小，处理大型候选集时准确性和效率会显著下降。
SetwiseModels（集合式模型）：从给定集合中选择单个最相关的文档，例如（查询，文档1，文档2，…，文档n）。
尽管列表式和集合式模型能提供更准确的排序，但它们在处理大规模数据集时面临严重的可伸缩性问题和效率瓶颈。
论文回顾了当前利用大型语言模型（LLM）进行排序的趋势，并详细分析了现有处理大型文档集的几种方法。
LLMs在信息检索等任务中表现出色，但其计算和时间成本高昂。研究人员探索了多种零样本（zero-shot）排序方法：
Pointwise：二进制分类或细粒度评分。
Pairwise：通过提示词进行两两比较。
Listwise：列表式排序技术。
此外，也有针对LLM排序的微调（fine-tuning）方法。
Calibration（校准）：
思路：通过微调列表式模型，使其输出的分数在不同批次间可比较，从而可以独立处理批次并聚合排名。
局限性：这种方法需要模型微调，不适用于JointRank所追求的零样本、模型无关的重排序。
Sorting（排序）：
思路：传统排序算法（如快速排序、归并排序）理论上有效，但依赖大量的顺序调用排序模型（次），导致计算成本过高。
并行化尝试：虽然排序可以高度并行化（如PRP-AllPair同步比较所有可能对），但对于大型候选集，这可能因资源限制而不可行。
Top-k关注：排名并非纯粹的排序问题，通常更关注识别Top-k项而非对整个集合排序。
优化方法：[8]提出了结合列表式/集合式重排序器和动态剪枝的优化排序方法，但仍然涉及重复的重排序器推理。JointRank将主要与Setwise. heapsort进行比较。
TournamentApproaches（锦标赛方法）：
思路：将元素分成组，组内排序，然后选出Top-m元素进入下一阶段，重复此过程。多个锦标赛可并行运行，聚合分数。
局限性：顺序调用的次数和跨度时间取决于选择阶段的数量，仍存在多次顺序调用的问题。
Sliding-windowListwiseRanking（滑动窗口列表式排序）：
思路：固定大小的窗口从列表底部向上移动，迭代地提升高相关性文档。
局限性：需要大约次顺序调用，仍是顺序性的。
Top-downPartitioning（自顶向下分区）：
思路：首先用基础模型对N个候选进行粗排，然后重排序前个元素，选择第个元素作为枢轴，将其他候选分成批次，并与枢轴一起并行重排序。低于枢轴的元素被视为不相关，高于枢轴的则与前个元素比较，重复此过程。
特点：结合动态剪枝，减少计算开销，增加了并行化。
局限性：尽管效率更高，但仍然需要顺序的重排序器调用。
在信息检索的实时应用中，如大型语言模型助手中的RAG、代码补全工具或交互式问答系统，延迟（Latency）是决定用户体验和系统可用性的关键因素。传统上，基于LLM的重排序方法往往需要多次顺序调用模型，这导致累积延迟过高，难以满足实时需求。
JointRank的核心思想可以概括为以下几个步骤（如图1所示）：
分块构建：JointRank精心设计了文档批次，称之为“块（blocks）”。这些块被设计成充分重叠。这意味着一个文档可能会出现在多个块中。
并行排序：每个构建好的块都足够小，可以被一个列表式排序模型（如LLM）高效处理。最关键的是，所有这些块的排序任务都是并行执行的。这意味着只需要一次大规模的并行推理，而不是多次顺序调用。
隐式两两比较：从每个并行处理的块内部排序结果中，JointRank能够生成大量的隐式两两比较。例如，如果文档A在某个块中排在文档B之前，则可以推断A优于B。
构建竞技图：块之间的故意重叠是至关重要的，它确保了所有文档之间的全局连通性。这些隐式比较构成了竞技图（tournamentgraph），反映了文档之间的相对优劣关系。
全局排名重建：最后，利用成熟的排名聚合算法（如EloRating、PageRank、Winrate、RankCentrality等），从这个竞技图中重建出一个完整的全局排名。
JointRank在块构建中借鉴了实验设计（experimentaldesign）的原理，特别是“分块（blocking）”的核心思想——将初始集合分离成多个子集。同时，它还融入了随机化（随机元素和随机顺序）、复制（每个项目出现在多个块中）和平衡（恒定块大小、每对项目在块中出现次数、每个项目复制次数）等原则。对于排序问题，设计必须是连通的，以允许估计至少部分顺序。尽管连通性本身可能不足以保证恢复完整的线性顺序，但它比覆盖设计所需的块要少得多。考虑到ML系统预测的两两比较可能不完全一致（即不具备完美的传递性和反对称性），最终得到的图应被视为竞技图而非简单的比较图。
理想情况下，为了最小化排序估计误差，设计应是覆盖的、平衡的、随机的且冗余的。然而，考虑到ML系统排序的计算成本，论文建议放宽这些要求，推荐使用连通的等复制设计（EBD）或连通的PBIBD。在研究中，作者对比了随机设计、EBD、PBIBD和滑动窗口设计。
为了全面验证JointRank的有效性，研究团队进行了两个阶段的评估：首先是合成数据实验，旨在优化超参数并深入理解算法性能；随后是真实信息检索数据集上的评估，以衡量其在实际场景中的表现。
设定：创建一个包含v个元素的列表，并赋予指数级相关性值（从21到2v）。然后将列表随机打乱，目标是使用一个“神谕（Oracle）”列表式重排序器来恢复其正确的全局顺序。
聚合算法：采用包括PageRank、EloRating、Winrate、RankCentrality等在内的多种竞技图聚合算法进行全局排名重建。
实验首先评估了不同块设计（TriangularPBIBD,Latin-SquarePBIBD,Equi-Replicate,SlidingWindow,Random）和排名聚合算法的组合性能。
聚合方法的选择也很重要：表3和表5强调了排名聚合方法的重要性。PageRank在设计均衡的块上表现最佳。然而，对于滑动窗口和随机块设计等不平衡的块，简单的平均胜率（AverageWinrate）方法反而表现更优。
推荐策略：综合来看，PBIBD表现最佳。但由于其构建上的复杂性和参数限制，当无法构建PBIBD时，Equi-ReplicateBlockDesign(EBD)是一个极佳的替代方案，性能仅略微下降。
论文进一步的实验探索了块数量和块大小对最终排名质量的影响：
块数量：增加块数量能提升排名质量，但在使用良好构建的块设计时，即使是简单的平均胜率方法也能取得接近PageRank的结果（图2），这表明块设计的良好性可以弥补聚合方法的简单性。
块大小：实验结果（图3和图4）揭示，块大小对排名准确性的影响显著强于块数量。这是因为每个块贡献的比较次数与块大小的平方成正比(k(k−1)/2)，而与块数量成线性关系。因此，要用较小块大小对长序列进行有效重排序，需要非常大量的块，甚至可能超过候选池本身的大小。
论文还通过多种统计数据（直接比较覆盖率、二阶比较覆盖率、平均/最小/最大节点度、共现率和连通率）评估了不同设计的覆盖能力（表6和表7）。
在合成实验验证了算法原理和优化了超参数之后，JointRank在真实的TRECDL-2019数据集上进行了严格评估，并与一系列现有SOTA方法进行了对比。
公平对比：所有LLM推理的最大处理候选数（窗口大小）统一为20。JointRank使用Equi-ReplicateBlockDesign和PageRank聚合。
评估指标：nDCG@10，以及非功能指标（推理次数、输入/生成token数、延迟）。还引入了“Oraclereranker”作为理论性能上限。
模型：Mistral-7Bv0. 3和Mistral-24B-2501。
为了进一步评估大上下文模型在处理无序、大量输入时的能力，实验将BM25检索到的Top-1000文档随机打乱，然后传递给重排序算法。这次允许除了FullContextListwise外的所有算法一次处理100个项目。模型选用gpt-4. 1-mini。
#学习大模型&讨论Kaggle#
△长按添加竞赛小助手
每天大模型、算法竞赛、干货资讯
与36000+来自竞赛爱好者一起交流~
