Are Optimal Algorithms Still Optimal? Rethinking Sorting in LLM-Based Pairwise Ranking with Batching and Caching
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915313646305280 |
|---|---|
| author | Wisznia, Juan Bolaños, Cecilia Tollo, Juan Marraffini, Giovanni Gianolini, Agustín Hsueh, Noe Del Corro, Luciano |
| author_facet | Wisznia, Juan Bolaños, Cecilia Tollo, Juan Marraffini, Giovanni Gianolini, Agustín Hsueh, Noe Del Corro, Luciano |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_24643 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Are Optimal Algorithms Still Optimal? Rethinking Sorting in LLM-Based Pairwise Ranking with Batching and Caching Wisznia, Juan Bolaños, Cecilia Tollo, Juan Marraffini, Giovanni Gianolini, Agustín Hsueh, Noe Del Corro, Luciano Computation and Language 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. |
| title | Are Optimal Algorithms Still Optimal? Rethinking Sorting in LLM-Based Pairwise Ranking with Batching and Caching |
| topic | Computation and Language |
| url | https://arxiv.org/abs/2505.24643 |