REVIEW 4 major objections 5 minor 25 references
Are Optimal Algorithms Still Optimal? Rethinking Sorting in LLM-Based Pairwise Ranking with Batching and Caching
T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Classical sorting-optimality flips when each comparison is a costly LLM inference, so Quicksort with batching beats Heapsort in pairwise ranking.
desk verdict The inference-cost reframing is useful, but the batch-size-2 Quicksort advantage collapses under the paper's own latency and token-cost data. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central mechanism is the packing of independent comparisons into a single LLM inference call. Quicksort's partition compares every element of a subarray to the same pivot, so those comparisons are mutually independent and can be batched: one forward pass of the model can return the winner for many pivot-versus-element pairs at once. Heapsort's comparisons are not independent in a way that allows this—each heap operation depends on the previous one—so its inference count stays equal to its comparison count. Caching is the complementary mechanism for Bubblesort, where the same adjacent pair recurs across passes and the earlier answer can be reused instead of re-queried. Partial Quicksort (a variant that stops early once the top-k elements are known) supplies the top-k extraction needed for reranking.
What would settle it
Run the same 100-document reranking task on a fixed GPU and pricing schedule, and compare total wall-clock time and total dollar cost for Quicksort with batch size 2 (or 128) versus Heapsort without batching; if Heapsort is faster or cheaper at equal nDCG@10, then counting inference calls as uniform units has not captured the real constraint.
Extended reading notes
Core claim
On its own terms, the paper's central claim is that optimality in sorting is not invariant to the cost model: when LLM inferences are the dominant cost and batching/caching are available, algorithms that are optimal by comparison count are no longer optimal, and vice versa. Concretely, Quicksort, whose partition phase compares every element against a single pivot, can submit those independent pairwise judgments as one batched inference; Heapsort's tree-based comparisons are serial and unique, so it gains nothing from batching and still pays one inference per comparison. The paper reports that at batch size 2 Quicksort performs roughly 44% fewer inference calls than Heapsort, at batch 128 about 94% fewer, and in an end-to-end A100 run Quicksort is 5.52× faster at batch 128 with comparable nDCG@10. Caching gives Bubblesort a similar reprieve, cutting inference calls by roughly half because its repeated adjacent comparisons can be reused. In all cases the exact same comparisons are executed, so the final ranking is unchanged; only the number of paid inference calls changes.
Load-bearing premise
The efficiency ranking treats every LLM inference as one uniform cost unit, ignoring token counts, dollar prices, and the actual wall-clock time of a batched call, so if batched calls are not genuinely cheaper or faster than separate calls, the reversal between Quicksort and Heapsort may not hold in practice.
Editorial extensions
If this is right
- At batch size 2, Quicksort is already the cheaper choice for latency-sensitive PRP, and larger batches widen the gap.
- Bubblesort with a small cache becomes a viable algorithm despite its O(n^2) comparison count, cutting inference calls by roughly half.
- The best algorithm for LLM reranking depends on hardware parallelism and batch-size limits, so no single classical 'optimal' sorting algorithm should be hard-coded.
- These gains are ranking-neutral: the same comparisons are made, only fewer inference calls, so switching algorithms does not trade away ranking quality.
- Heapsort's advantage is confined to the no-batching regime, which is rare in LLM serving, so its status as default PRP sorter should be reconsidered.
Reading between the lines
- The same batching logic should transfer to other algorithms whose comparisons share a common reference element, such as tournament constructions or multiway selection, potentially overturning other classical choices.
- If LLM providers price by tokens rather than by call, the uniform-inference-call metric could overstate Quicksort's gain; a token-weighted variant would make the framework robust to pricing.
- Batching against a single pivot may also reduce the effect of intransitive LLM judgments, since all comparisons share one reference document; that is a testable hypothesis the paper does not pursue.
- For very large candidate sets, the crossover batch size at which Quicksort beats Heapsort could be derived analytically and then verified empirically, giving practitioners a hardware-specific decision rule.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a cost model for pairwise ranking prompting (PRP) in which the dominant cost is the number of LLM inference calls rather than the number of pairwise comparisons, and it argues that under this model, with batching (and, for Bubblesort, caching), the classical optimality of Heapsort is overturned. The headline claim is that a batch size of 2 already gives Quicksort 44% fewer inference calls than Heapsort, and that Quicksort is therefore ideal for latency-sensitive applications. The authors validate single-pass batching scaling on three GPUs (A100, RTX 3090, RTX 2080 Ti) with Flan-T5-Large, report full-pipeline A100 runs at batch sizes 2 and 128 over BEIR and TREC datasets with nDCG@10, and report a 5.52x end-to-end speedup for Quicksort over Heapsort at batch size 128.
Significance. The paper identifies a real gap: traditional comparison-count analysis ignores that in PRP the expensive operation is the LLM inference, and it correctly observes that batching and caching change which algorithm looks best. The empirical parts are genuinely useful: single-pass latency scaling curves across three GPU generations, and a full-pipeline A100 comparison at batch sizes 2 and 128, give a falsifiable, hardware-grounded picture. The large-batch result (Quicksort roughly 5.5x faster end-to-end at b=128 on the A100) survives the cost-model critique and is a practical contribution. However, the headline optimality reversal at batch size 2 does not survive the paper's own wall-clock measurements, and the asymmetry of the Heapsort treatment (non-batchable by assumption) makes the central comparison incomplete. The framework's significance currently rests on the large-batch regime and on a more careful statement of what the cost unit does and does not capture.
major comments (4)
- [§4 (Metric), §5, Table 2] The uniform cost unit, defined in §4 as 'each inference—regardless of token count or monetary cost—is treated as a uniform cost unit,' makes the batch-size-2 reversal an artifact of the counting convention. Under the paper's own assumption of uniform document preprocessing, a batch of two comparisons processes twice the tokens of a single comparison, so token cost is proportional to the number of comparisons, not the number of inference calls. Table 2 makes the consequence concrete: for Flan-T5-Large on DBpedia, Quicksort (original, b=2) needs 245.3 comparisons (126.8 batched calls) versus Heapsort's 225.1 single calls, i.e., roughly 9% more token-equivalent work, and the paper's own end-to-end latency is 34.1 s versus 24.8 s, so Quicksort is slower at b=2. The Abstract and §5 claims that Quicksort with b=2 generates 44% fewer inference calls and is 'ideal for latency-sensitive applications' are therefore supported only by the counting convention; the b=128 numbers (e.g., 4.7 s versus 24.8 s on DBpedia) are the evidence that actually supports the batching thesis. I recommend reporting latency- or token-weighted costs for the headline comparisons so that the reversal claim is stated at the batch sizes where the paper's own measurements support it.
- [§3, Table 1, Figure 3] The claim that Heapsort 'cannot be adapted to batching or caching due to its binary tree structure' and that its comparisons are 'inherently sequential and unique,' making it 'impossible to group comparisons into a single inference step,' is asserted without proof and is too strong. During build-heap, sift-downs on disjoint subtrees are independent and could be batched; within a single sift-down, the parent-versus-children comparisons can be issued in one batched call, with the child-versus-child comparison needed only in the case where both children beat the parent. Even partial batching of Heapsort would shrink the reported gap, so the Quicksort-versus-Heapsort comparison in §5 is asymmetric as presented. The authors should either implement and report a batched Heapsort baseline or provide a careful argument for why no Heapsort comparison can ever be batched. Relatedly, Figure 3 is labeled 'Heapsort w/ batch' and shows batch-size-dependent gains; if Heapsort is non-batchable per Table 1, its curve should be flat, and if the curve is batched, Table 1 and §3 are internally inconsistent.
- [§5 (Latency Analysis and Findings), Table 2] The recommendation that 'Quicksort is ideal for latency-sensitive applications with batch sizes ≥ 2' is contradicted by the paper's own measurements at the advertised boundary: at b=2, Quicksort (original) is slower than Heapsort on Flan-T5-Large for DBpedia (34.1 s versus 24.8 s) and Touche2020 (34.9 s versus 26.0 s) in Table 2. The '≥ 2' threshold is therefore not supported by the data; the latency evidence supports the large-batch regime only. Please re-scale the claim to the batch sizes where the reported latencies actually show a Quicksort advantage, or report the b=2 comparison in a way that is consistent with the recommendation.
- [§5 (Ranking Performance), Figure 6, Tables 2 and 3] The statement that ranking performance 'remains relatively stable for a given dataset' understates systematic accuracy losses for Quicksort. On Flan-T5-Large, nDCG@10 drops from Heapsort 0.675 to Quicksort (original) 0.579 on SciFact and from 0.332 to 0.268 on Touche2020 (Table 3); similar drops appear for Flan-T5-XL (SciFact 0.710 versus 0.634). These differences are comparable in size to the dataset-to-dataset variation shown in Figure 6 and should be part of the practical recommendation, which currently presents Quicksort as the preferred choice for latency-sensitive applications without acknowledging the accuracy trade-off seen in the tables.
minor comments (5)
- [§5 (Latency Analysis)] The stated '5.52× faster' figure at b=128 does not match a simple average of the Table 2 ratios (e.g., DBpedia 24.8/4.7≈5.3, SciFact 26.9/4.3≈6.3); please state how the aggregate speedup is computed.
- [Figure 3] The caption's definitions of the 'black number' and 'green number' are hard to follow, and the legend entry 'Heapsort w/ batch' conflicts with Table 1, which marks Heapsort as non-batchable; please clarify the series and the computation of the percentages.
- [§4 (Metric) and §7 (Limitations)] The justification for ignoring token counts ('standard pre-processing ensures uniformity across documents') accounts for equal document lengths but not for the multiplicative token load of batched calls; the Limitations section should explicitly acknowledge this cost-modeling choice and its effect on the batch-size-2 results.
- [§3 and §5] The claim that batching 'preserves the final ranking outcome' assumes deterministic decoding; please state the decoding settings used in the latency experiments so that the equivalence between batched and unbatched comparisons is verifiable.
- [Throughout] There are several typos: 'opimizations' in the §3 heading, 'susbtantial' in §5, 'PPR' for PRP in §3, and 'V oorhees' and 'F ound.' in the reference list; a careful proofread is needed.
Circularity Check
No significant circularity; the inference-call counts are measured directly under an explicitly stated cost model, and no result reduces to its own input by construction.
full rationale
The paper's central derivation is self-contained. It defines the cost metric as the number of LLM inference calls, then algorithmically counts comparisons and inference calls for Quicksort, Heapsort, and Bubblesort under batching and caching, reporting these counts in the appendix. The batching advantage for Quicksort follows from the stated cost model plus the algorithm's structure, rather than from a fitted parameter or a hidden equivalence: the paper explicitly says each inference is treated as a uniform cost unit regardless of token count, and it separately reports both #comparisons and #inferences, so the reduction to roughly half at batch size 2 is transparent. No parameter is fitted to the target result, and no load-bearing self-citation or imported uniqueness theorem appears. The choice to disregard token counts and dollar costs is a stated modeling simplification, not a circular step. The claim that Heapsort cannot be batched is a substantive algorithmic assumption that may be contestable, but it is an input premise, not a derivation from the conclusion. Similarly, the leap from inference-call counts to 'ideal for latency-sensitive applications with batch sizes >= 2' is a validity gap (the paper's own Table 2 shows Quicksort with higher end-to-end latency than Heapsort at batch size 2 on DBpedia), but that is a correctness or generalization concern, not circularity. The independent wall-clock speedup at batch size 128 corroborates the cost model externally, so the derivation chain is not circular.
Assumptions & free parameters
assumptions (5)
- domain assumption Each LLM inference call, regardless of batch size or token count, has uniform cost.
- domain assumption LLM comparisons are deterministic enough that caching and batching preserve the exact same comparison results.
- domain assumption Pairwise relevance judgments are transitive enough for sorting algorithms to produce valid rankings.
- ad hoc to paper Heapsort cannot be adapted to batching or caching.
- domain assumption Quicksort comparisons against a pivot can be grouped into a single batched LLM call.
Cite this review
Pith. "Pith review of Are Optimal Algorithms Still Optimal? Rethinking Sorting in LLM-Based Pairwise Ranking with Batching and Caching." pith.science (2026). https://pith.science/paper/PB42DOZ3
@misc{pith2026250524643,
author = {Pith},
title = {Pith review of: Are Optimal Algorithms Still Optimal? Rethinking Sorting in LLM-Based Pairwise Ranking with Batching and Caching},
year = {2026},
howpublished = {\url{https://pith.science/paper/PB42DOZ3}},
note = {Machine review of arXiv:2505.24643}
}
read the original abstract
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.
Figures
Reference graph
Works this paper leans on
-
[1]
Xingjian Bai and Christian Coester. 2023. http://arxiv.org/abs/2311.00749 Sorting with predictions
work page Pith review arXiv 2023
-
[2]
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin...
arXiv 2020
-
[3]
Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoc V
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Alex Castro-Ros, Marie Pellat, Kevin Robinson, Dasha Valter, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Zhao, Yanping H...
arXiv 2022
-
[4]
Nick Craswell, Bhaskar Mitra, Emine Yilmaz, and Daniel Campos. 2021. http://arxiv.org/abs/2102.07662 Overview of the trec 2020 deep learning track
arXiv 2021
- [5]
-
[6]
Abhimanyu Dubey et al. 2024. http://arxiv.org/abs/2407.21783 The llama 3 herd of models
arXiv 2024
-
[7]
C.A.R. Hoare. 1962. Quicksort. BCS, Computer Journal, 5(1):10--15
work page 1962
-
[8]
Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. 2023. http://arxiv.org/abs/2310.06...
arXiv 2023
Show all 25 references
-
[9]
Jian Luo, Xuanang Chen, Ben He, and Le Sun. 2024. https://doi.org/10.18653/v1/2024.acl-long.313 PRP -graph: Pairwise ranking prompting to LLM s with graph aggregation for effective text re-ranking . In Proceedings of the 62nd Annual Meeting of the Association for Computational...
2024 doi
-
[10]
Xueguang Ma, Xinyu Zhang, Ronak Pradeep, and Jimmy Lin. 2023. http://arxiv.org/abs/2305.02156 Zero-shot listwise document reranking with a large language model
2023 arXiv
-
[11]
Conrado Mart nez. 2004. Partial quicksort. In In Proceedings of the 6th ACMSIAM Workshop on Algorithm Engineering and Experiments and 1st ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics, pages 224--228
2004
-
[12]
Irina Matveeva, Chris Burges, Timo Burkard, Andy Laucius, and Leon Wong. 2006. https://doi.org/10.1145/1148170.1148246 High accuracy retrieval with multiple nested ranker . In Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Info...
2006
-
[13]
Aliaksei Mikhailiuk, Clifford Wilmot, Mar \' a P \' e rez - Ortiz, Dingcheng Yue, and Rafal Mantiuk. 2020. http://arxiv.org/abs/2004.05691 Active sampling for pairwise comparisons via approximate message passing and information gain maximization . CoRR, abs/2004.05691
2020 arXiv
-
[14]
Rodrigo Nogueira, Zhiying Jiang, and Jimmy Lin. 2020. http://arxiv.org/abs/2003.06713 Document ranking with a pretrained sequence-to-sequence model
2020 arXiv
-
[15]
Zhen Qin, Rolf Jagerman, Kai Hui, Honglei Zhuang, Junru Wu, Le Yan, Jiaming Shen, Tianqi Liu, Jialu Liu, Donald Metzler, Xuanhui Wang, and Michael Bendersky. 2024. https://doi.org/10.18653/v1/2024.findings-naacl.97 Large language models are effective text rankers with pairwise...
2024 doi
-
[16]
Robertson and Hugo Zaragoza
Stephen E. Robertson and Hugo Zaragoza. 2009. https://api.semanticscholar.org/CorpusID:207178704 The probabilistic relevance framework: Bm25 and beyond . Found. Trends Inf. Retr., 3:333--389
2009
-
[17]
Robert Sedgewick. 1975. Quicksort. Outstanding Dissertations in the Computer Sciences. Garland Publishing, New York
1975
-
[18]
Weiwei Sun, Lingyong Yan, Xinyu Ma, Shuaiqiang Wang, Pengjie Ren, Zhumin Chen, Dawei Yin, and Zhaochun Ren. 2024. http://arxiv.org/abs/2304.09542 Is chatgpt good at search? investigating large language models as re-ranking agents
2024 arXiv
-
[19]
Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, and Iryna Gurevych. 2021. http://arxiv.org/abs/2104.08663 Beir: A heterogenous benchmark for zero-shot evaluation of information retrieval models
2021 arXiv
-
[20]
Lidan Wang, Jimmy Lin, and Donald Metzler. 2011. https://doi.org/10.1145/2009916.2009934 A cascade ranking model for efficient ranked retrieval . In Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '11, page...
2011
-
[21]
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mari...
2020 arXiv
-
[22]
Honglei Zhuang, Zhen Qin, Rolf Jagerman, Kai Hui, Ji Ma, Jing Lu, Jianmo Ni, Xuanhui Wang, and Michael Bendersky. 2023. https://doi.org/10.1145/3539618.3592047 Rankt5: Fine-tuning t5 for text ranking with ranking losses . In Proceedings of the 46th International ACM SIGIR Conf...
2023
-
[23]
Shengyao Zhuang, Honglei Zhuang, Bevan Koopman, and Guido Zuccon. 2024. https://doi.org/10.1145/3626772.3657813 A setwise approach for effective and highly efficient zero-shot ranking with large language models . In Proceedings of the 47th International ACM SIGIR Conference on...
2024
-
[24]
URL: " 'urlintro :=
ENTRY address author booktitle chapter edition editor howpublished institution journal key month note number organization pages publisher school series title type volume year eprint doi pubmed url lastchecked label extra.label sort.label short.list INTEGERS output.state before...
-
[25]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.