# Are Optimal Algorithms Still Optimal? Rethinking Sorting in LLM-Based Pairwise Ranking with Batching and Caching

arXiv: https://arxiv.org/abs/2505.24643 · HTML: https://mlsanity.com/paper/2505.24643/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 13 of its 23 references that are in the map.
- First posted on arXiv 30 May 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 13 of 13)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [Scaling Instruction-Finetuned Language Models](https://mlsanity.com/paper/2210.11416/) (2022)
- [HuggingFace's Transformers: State-of-the-art Natural Language Processing](https://mlsanity.com/paper/1910.03771/) (2019)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [Document Ranking with a Pretrained Sequence-to-Sequence Model](https://mlsanity.com/paper/2003.06713/) (2020)
- [Is ChatGPT Good at Search? Investigating Large Language Models as Re-Ranking Agents](https://mlsanity.com/paper/2304.09542/) (2023)
- [Overview of the TREC 2019 deep learning track](https://mlsanity.com/paper/2003.07820/) (2020)
- [Overview of the TREC 2020 deep learning track](https://mlsanity.com/paper/2102.07662/) (2021)
- [Zero-Shot Listwise Document Reranking with a Large Language Model](https://mlsanity.com/paper/2305.02156/) (2023)
- [Active Sampling for Pairwise Comparisons via Approximate Message Passing and Information Gain Maximization](https://mlsanity.com/paper/2004.05691/) (2020)
- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)

## Built on by (most cited first, 2 of 2)

- [GroupRank: A Groupwise Paradigm for Effective and Efficient Passage Reranking with LLMs](https://mlsanity.com/paper/2511.11653/) (2025)
- [Active Learners as Efficient PRP Rerankers](https://mlsanity.com/paper/2605.14236/) (2026)

## Abstract (arXiv)

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.