引言

如果你上过计算机科学算法课程，你就知道那个套路。当被问到“什么是高效的排序算法？”时，答案几乎是条件反射式的“归并排序”、“堆排序”或“快速排序”。为什么？因为大 O 符号 (Big O notation) 。我们被教导说，\(O(n \log n)\) 是基于比较的排序的金标准，而像冒泡排序 (\(O(n^2)\)) 这样的算法则被扔进了“永远不要在生产环境中使用”的垃圾桶。

但是，如果大 O 符号背后的基本假设——即每次比较的成本大致相同且非常便宜——突然错了呢？

这正是我们在使用大型语言模型 (LLM) 进行现代信息检索 (IR) 时面临的情况。当我们使用 LLM 对搜索结果进行重排序 (re-rank) 时，我们不仅仅是在 CPU 寄存器中比较两个整数 (纳秒级操作) 。我们是在将两个文档输入到一个庞大的神经网络中，并要求它生成一个偏好 (这个操作需要毫秒甚至秒级时间) 。

在这篇博文中，我们将深入探讨一篇引人入胜的研究论文，题为 “Are Optimal Algorithms Still Optimal? Rethinking Sorting in LLM-Based Pairwise Ranking with Batching and Caching” (最优算法还是最优吗？重新思考结合批处理与缓存的 LLM 成对排序) 。研究人员挑战了 LLM 背景下排序理论的现状。他们揭示了当比较成本变得昂贵时，“低效”的算法可能会变得出奇地有效，而“最优”的算法实际上可能会拖慢你的速度。

背景: LLM 重排序的兴起

在进入排序算法之前，让我们先建立背景。在现代搜索引擎中，过程通常分两个阶段进行:

  1. 检索 (Retrieval) : 一种快速、廉价的算法 (如 BM25) 找到与查询相关的最前面 100 或 1000 个文档。
  2. 重排序 (Re-ranking) : 一个更强大的模型会查看这些候选文档，并重新排列它们，将绝对最好的文档放在最前面。

最近, 成对排序提示 (Pairwise Ranking Prompting, PRP) 已成为第二阶段的一种强大技术。这个想法很简单: 与其训练一个特定的排序模型，不如直接让一个标准的 LLM (如 GPT-4、Llama 3 或 Flan-T5) 比较两个文档。

“给定查询 Q，以及文档 A 和 B，哪一个更相关？”

LLM 输出“A”或“B”。

这种方法很优雅，因为它不需要训练数据 (零样本) 。然而，它引入了一个巨大的计算瓶颈。如果你有 100 个文档要排序，朴素的方法可能需要将每个文档与其他所有文档进行比较。当每一次比较都需要一次 GPU 推理调用时，这种成本极其高昂。

为了解决这个问题，从业者自然而然地转向经典的排序算法，以尽量减少比较次数。例如，如果你使用堆排序 (Heapsort) , 你可以用 \(O(n \log n)\) 次比较而不是 \(O(n^2)\) 次来对 \(N\) 个项目进行排序。直到现在，该领域一直假设最小化比较的计数是唯一重要的指标。

核心问题: 推理与比较

研究人员认为，经典分析在这种背景下犯了一个致命的错误。它将比较视为原子的、成本统一的操作 。

在 CPU 中，比较 5 < 10 是原子的。但在 LLM 系统中，一次“比较”是一个 API 调用或一次 GPU 前向传播。这种差异解锁了标准大 O 符号所忽略的两个强大的优化:

  1. 批处理 (Batching) : 在基于 GPU 的系统中，检查一对 (A vs B) 所需的时间与同时检查十对 (A vs B, A vs C, A vs D...) 所需的时间几乎相同，只要显存装得下。
  2. 缓存 (Caching) : 如果你的排序算法冗余地多次比较 A vs B，你可以存储结果并在第二次时跳过昂贵的推理。

研究人员提出了一个新的框架: 将成本模型重新集中在 LLM 推理上，而不是比较次数上。

当你通过这个镜头观察排序时，算法的层级发生了巨大的变化。一个执行更多比较但允许更少推理调用 (通过批处理) 的算法成为了更优的选择。

重新审视旧算法

让我们在这个新的“以 LLM 为中心”的成本模型下分析三种经典的排序算法——堆排序、冒泡排序和快速排序。

表 1 总结了适用于每种算法的优化。堆排序既不支持批处理也不支持缓存。冒泡排序支持缓存。快速排序支持批处理。

如上表所示，这些算法的结构特性决定了它们是否能利用现代硬件优化。

1. 堆排序: 理论上“最优”的陷阱

堆排序在 PRP 研究中一直备受青睐。它保证了 \(O(n \log n)\) 的复杂度，并且非常擅长在不对整个列表进行排序的情况下提取“Top-K”项目。

然而，堆排序依赖于二叉树结构。要知道下一次进行哪个比较，你严格需要上一次比较的结果。它本质上是串行的。你不能把 10 个比较打包成一个批次，因为在你一步步遍历树之前，你不知道这 10 个比较会是什么。此外，堆排序很少两次比较同一对，这意味着缓存没有任何好处。

在 LLM 的世界里，堆排序迫使 GPU 像 CPU 一样行动: 一次处理一个小任务，白白浪费了巨大的潜在吞吐量。

2. 冒泡排序: \(O(n^2)\) 的救赎

冒泡排序以低效著称。它扫描列表，如果相邻元素的顺序错误就交换它们。对于一个包含 100 个项目的列表，朴素的冒泡排序是一场灾难。

然而，研究人员注意到了一个独特的属性: 冗余性 (Redundancy) 。 冒泡排序在多次遍历中重复比较相邻元素。在 CPU 环境中，这是浪费工作。在 LLM 环境中，如果我们采用一个简单的缓存 (一个存储 key="DocA_DocB", value="DocA" 的字典) ，那些重复的比较就变成了“免费”的瞬时查找。

图 1: 带缓存的冒泡排序。实线红箭头代表昂贵的非缓存推理。虚线箭头代表廉价的缓存查找。

如图 1 所示，冒泡排序的第二次遍历严重依赖于缓存结果 (虚线箭头) 。虽然冒泡排序不支持批处理 (因为交换依赖于紧接的上一个结果) ，但缓存机制大幅减少了所需的实际 LLM 调用次数。

3. 快速排序: 批处理的强力军

这是该论文做出最大贡献的地方。快速排序通过选择一个“基准 (pivot) ”元素，并将剩余项目分为两组来工作: 比基准“更小” (相关性更低) 的和比基准“更大” (相关性更高) 的。

经典做法是，你将基准与项目 1 比较，然后将基准与项目 2 比较，依此类推。 但是为什么要等待呢？

由于基准在分区步骤期间是固定的，因此比较是独立的。我们可以构建一个单一的提示词:

“这是一个基准文档 P。这是一个候选文档列表 {A, B, C, D}。对于每个候选文档，告诉我它是否比 P 更相关。”

这允许我们要利用批处理 。

图 2: 对比串行推理 (每次调用比较一次) 与批处理推理 (每次调用对比基准进行多次比较) 。

图 2 说明了这种转变。在左侧 (经典分析) ，每对执行一次推理。在右侧 (批处理) ，我们在单个推理步骤中获得了关于多个文档的信息。即使比较的总次数 (数学运算) 保持不变，推理调用的次数 (昂贵的 GPU 操作) 也会急剧下降。

实验与结果

研究人员使用标准的 TREC 和 BEIR 数据集验证了他们的理论，使用了 Flan-T5、Mistral 和 Llama 3 等模型。他们衡量的“效率”不是时间复杂度，而是 LLM 推理调用的原始计数。

批处理对快速排序的影响

快速排序的结果是戏剧性的。当批大小为 1 (标准行为) 时，堆排序确实比快速排序更有效。这符合传统理论。

然而，一旦批大小增加到仅仅 2，情况就发生了反转。

图 3: 随着批大小增加，快速排序的推理计数下降图表。堆排序几乎没有收益，而快速排序效率呈线性提升。

在图 3 中，看看快速排序 (蓝色条) 的急剧下降。在批大小为 2 时，快速排序产生的推理调用比堆排序少 44% 。 在批大小为 128 时，减少量是巨大的——超过 90%。

因为堆排序 (橙色条) 由于其树依赖性而无法有效地批量比较，无论硬件能力如何，其效率都停滞不前。

缓存对冒泡排序的影响

冒泡排序也迎来了复兴。通过实施简单的缓存，该算法避免了重新计算已知的关系。

图 4: 比较有无缓存的冒泡排序的柱状图。缓存使各数据集的推理减少了约 46%。

图 4 显示，缓存将冒泡排序的总推理减少了平均 46% 。 虽然它没有击败批处理快速排序，但这使得冒泡排序成为比以前认为的更可行的候选者，尤其是在批处理可能很困难 (例如显存限制) 但有内存可用于缓存的场景中。

实际延迟

理论推理计数很好，但这能转化为实际运行时间吗？研究人员在 NVIDIA A100、RTX 3090 和 RTX 2080 Ti GPU 上运行了这些算法。

图 5: 加速比与批大小的关系折线图。A100 在批大小达到 8 之前呈现近乎线性的加速，并在达到 128 之前持续提升。

如图 5 所示，“加速”是真实的。在 A100 (蓝线) 上，增加批大小会产生显著的性能增益。这种扩展并不是永远完全线性的——最终你会达到 GPU 的计算极限——但在 2-32 的批大小范围内增益是巨大的。

在 BEIR 基准测试的完整端到端测试中, 快速排序 (批大小 128) 比堆排序快 5.52 倍 , 同时实现了相似的排序质量。

效率会损害排序质量吗？

一个关键问题仍然存在: 通过切换算法或优化速度，我们会降低搜索结果的质量吗？

简短的回答是: 不会。

图 6: 各数据集的 nDCG@10 分数图表。冒泡排序、堆排序和快速排序的线条几乎重合，表明性能稳定。

图 6 展示了 nDCG@10 (排序质量的标准指标) 。不同算法的性能线紧密聚集在一起。这意味着你可以根据可用的硬件和延迟要求选择算法，而不必担心损害用户体验。

为了详细了解确切的数字，我们可以查看 DBPedia 和 FiQA 等数据集的具体结果:

详细表格显示了各种方法的 NDCG 分数、比较次数和推理次数。带批处理的快速排序显示出极低的推理计数。

在表 2 中，注意 #Inf (推理次数) 列。

  • DBPedia 上的 堆排序 : ~225 次推理。
  • DBPedia 上的 快速排序 (Batch=128) : ~13 次推理。

这种差异是一个数量级。两者的排序得分 (NDCG@10) 都保持在 0.41 左右。你以不到 10% 的成本获得了相同的结果。

结论与启示

这项研究强调了现代软件工程的一个重要教训: 上下文改变复杂度。

几十年来被教导为“最优”的算法是为比较是廉价原子操作的世界而设计的。在大型语言模型时代，单次比较就是一次计算繁重的推理，我们必须重写规则手册。

本文的主要收获是:

  1. 停止计算比较次数；开始计算推理次数。 这是 AI 系统的真正瓶颈。
  2. 堆排序对于 LLM 排序来说已经过时了。 其串行特性阻碍了它利用 GPU 的并行处理能力。
  3. 快速排序是王道。 它的分区阶段非常适合批处理，允许我们在单个提示词中将一个文档与几十个其他文档进行比较。
  4. 不要忽视“坏”算法。 即使是冒泡排序也可以通过简单的缓存策略得到救赎，因为 LLM 成本暴露了与 CPU 周期不同的瓶颈。

对于从事 RAG (检索增强生成) 或搜索系统的学生和开发人员来说，这建议了一个立即的实际改变。如果你正在实现一个重排序器，请远离串行成对比较。构建你的提示词以处理批次，并利用像快速排序这样符合硬件并行特性的算法。理论上的“最佳”并不总是实际的赢家。