@inproceedings{wisznia-etal-2025-optimal,
    title = "Are Optimal Algorithms Still Optimal? Rethinking Sorting in {LLM}-Based Pairwise Ranking with Batching and Caching",
    author = "Wisznia, Juan  and
      Bola{\~n}os, Cecilia  and
      Tollo, Juan  and
      Marraffini, Giovanni Franco Gabriel  and
      Gianolini, Agust{\'i}n Andr{\'e}s  and
      Hsueh, Noe Fabian  and
      Corro, Luciano Del",
    editor = "Che, Wanxiang  and
      Nabende, Joyce  and
      Shutova, Ekaterina  and
      Pilehvar, Mohammad Taher",
    booktitle = "Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)",
    month = jul,
    year = "2025",
    address = "Vienna, Austria",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/landing_page/2025.acl-short.83/",
    pages = "1064--1072",
    ISBN = "979-8-89176-252-7",
    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."
}