重审排序算法效率，发现大模型推理成本改变最优策略。
Are Optimal Algorithms Still Optimal? Rethinking Sorting in LLM-Based Pairwise Ranking with Batching and Caching
- 以大模型推理次数为代价核心，重构排序评估框架。
- 经典最优算法在批量与缓存优化下可能失效。
- 适合关注LLM推理开销的提示工程研究者。
我们提出一种新框架，用于分析基于大语言模型的成对排序提示（Pairwise Ranking Prompting, PRP）中的排序算法，将成本模型从传统的比较次数转向大语言模型（LLM）推理次数。传统以比较次数为指标的效率评估方法在实际中被高成本的LLM推理所颠覆；因此，本框架倡导采用批量处理（batching）和缓存（caching）等策略以降低推理开销。我们证明，在某些优化条件下，经典排序算法虽在传统意义上最优，但因LLM推理成本占主导而失去效率优势。
原文摘要 · Abstract (English)
We introduce a novel framework for analyzing sorting algorithms in pairwise ranking prompting (PRP), re-centering the cost model around LLM inferences rather than traditional pairwise comparisons. While classical metrics based on comparison counts have traditionally been used to gauge efficiency, our analysis reveals that expensive LLM inferences overturn these predictions; accordingly, our framework encourages strategies such as batching and caching to mitigate inference costs. We show that algorithms optimal in the classical setting can lose efficiency when LLM inferences dominate the cost under certain optimizations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。