Cutting LLM Evaluation Costs with SySRs: A Bandit Algorithm That Provably Exploits Model Similarity

Large Language Models are typically benchmarked by evaluating every model on every test query. For practitioners seeking the best model to deploy, this is often wasteful: if a model clearly performs worse than others, there is no need to precisely estimate its performance. Best-arm identification algorithms can be naturally applied to drastically reduce costs by adaptively allocating evaluation budget. Further, language models often respond similarly to the same prompt—a property previous work has tried to leverage with mixed success in different use cases. We propose Synchronized Successive Rejects (SySRs), augmenting the classical Successive Reject algorithm with paired comparisons. Unlike prior attempts to leverage model similarity in best-model identification, our approach is hyperparameter-free and enjoys performance guarantees that improve with the degree of similarity between evaluated models. Empirically, our method outperforms all baselines in terms of average error rate across 15 standard benchmarks, and in terms of worst-case budget for reliably identifying the best model.

Large language models can solve many relevant tasks. However, figuring out which model to use for a given application often involves asking many models many questions and checking correctness for each answer, which can quickly get very expensive. Our method reduces the cost of finding the best language model for a task by making sure evaluation effort is only spent on models that have a realistic shot at being the best. Our method is designed to further exploit a useful fact: Different language models often give very similar answers to the same question. Similar to how student performance is easier to compare when everyone takes the same exam, we ensure that all models are tested on the same questions. We mathematically prove that combined with model similarity, this makes it easier to tell apart good models from bad ones. Our experiments show that our approach can reduce the cost of finding the best language model by a factor of three, making it much easier to select language models on a budget.