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

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 36 references that are in the map.
- First posted on arXiv 5 Jun 2026.

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

- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Do ImageNet Classifiers Generalize to ImageNet?](https://mlsanity.com/paper/1902.10811/) (2019)
- [Quantifying Language Models' Sensitivity to Spurious Features in Prompt Design or: How I learned to start worrying about prompt formatting](https://mlsanity.com/paper/2310.11324/) (2023)
- [tinyBenchmarks: evaluating LLMs with fewer examples](https://mlsanity.com/paper/2402.14992/) (2024)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Accuracy on the Line: On the Strong Correlation Between Out-of-Distribution and In-Distribution Generalization](https://mlsanity.com/paper/2107.04649/) (2021)
- [LLMs instead of Human Judges? A Large Scale Empirical Study across 20 NLP Evaluation Tasks](https://mlsanity.com/paper/2406.18403/) (2024)
- [Observational Scaling Laws and the Predictability of Language Model Performance](https://mlsanity.com/paper/2405.10938/) (2024)
- [Anchor Points: Benchmarking Models with Much Fewer Examples](https://mlsanity.com/paper/2309.08638/) (2023)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Great Models Think Alike and this Undermines AI Oversight](https://mlsanity.com/paper/2502.04313/) (2025)
- [Limits to scalable evaluation at the frontier: LLM as Judge won't beat twice the data](https://mlsanity.com/paper/2410.13341/) (2024)
- [Correlated Errors in Large Language Models](https://mlsanity.com/paper/2506.07962/) (2025)
- [metabench -- A Sparse Benchmark of Reasoning and Knowledge in Large Language Models](https://mlsanity.com/paper/2407.12844/) (2024)
- [Model Similarity Mitigates Test Set Overuse](https://mlsanity.com/paper/1905.12580/) (2019)
- [Multi-Armed Bandits with Correlated Arms](https://mlsanity.com/paper/1911.03959/) (2019)
- [How Benchmark Prediction from Fewer Data Misses the Mark](https://mlsanity.com/paper/2506.07673/) (2025)
- [Why do classifier accuracies show linear trends under distribution shift?](https://mlsanity.com/paper/2012.15483/) (2020)
- [Open Problem: Optimal Best Arm Identification with Fixed Budget](https://mlsanity.com/paper/2303.00950/) (2023)
- [Policy Choice and Best Arm Identification: Asymptotic Analysis of Exploration Sampling](https://mlsanity.com/paper/2109.08229/) (2021)
- [On Speeding Up Language Model Evaluation](https://mlsanity.com/paper/2407.06172/) (2024)
- [How Reliable is Language Model Micro-Benchmarking?](https://mlsanity.com/paper/2510.08730/) (2025)
- [Best-Arm Identification in Correlated Multi-Armed Bandits](https://mlsanity.com/paper/2109.04941/) (2021)
- [Position: Stop Evaluating AI with Human Tests, Develop Principled, AI-specific Tests instead](https://mlsanity.com/paper/2507.23009/) (2025)
- [Correlated Multi-armed Bandits with a Latent Random Source](https://mlsanity.com/paper/1808.05904/) (2018)

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

- [Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices](https://mlsanity.com/paper/2609.25645/) (2026)
- [Are We Testing Too Much? A Survey of Benchmark Compression for Efficient Evaluation of Large Language Models](https://mlsanity.com/paper/2610.18248/) (2026)

## Abstract (arXiv)

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. We propose Synchronized Successive Rejects (SySRs), augmenting the classical Successive Rejects 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.