# Consistent and Distinctive: LLM Benchmark Efficiency via Maximum Independent Set Prompt Selection on Similarity Graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 37 references that are in the map.
- First posted on arXiv 31 May 2026.

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

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [Qwen3 Embedding: Advancing Text Embedding and Reranking Through Foundation Models](https://mlsanity.com/paper/2506.05176/) (2025)
- [Text Embeddings by Weakly-Supervised Contrastive Pre-training](https://mlsanity.com/paper/2212.03533/) (2022)
- [Instruction-Following Evaluation for Large Language Models](https://mlsanity.com/paper/2311.07911/) (2023)
- [Annotation Artifacts in Natural Language Inference Data](https://mlsanity.com/paper/1803.02324/) (2018)
- [C-Pack: Packed Resources For General Chinese Embeddings](https://mlsanity.com/paper/2309.07597/) (2023)
- [State of What Art? A Call for Multi-Prompt LLM Evaluation](https://mlsanity.com/paper/2401.00595/) (2023)
- [tinyBenchmarks: evaluating LLMs with fewer examples](https://mlsanity.com/paper/2402.14992/) (2024)
- [Omni-MATH: A Universal Olympiad Level Mathematic Benchmark For Large Language Models](https://mlsanity.com/paper/2410.07985/) (2024)
- [Anchor Points: Benchmarking Models with Much Fewer Examples](https://mlsanity.com/paper/2309.08638/) (2023)
- [Efficient Benchmarking of Language Models](https://mlsanity.com/paper/2308.11696/) (2023)
- [Llama-Embed-Nemotron-8B: A Universal Text Embedding Model for Multilingual and Cross-Lingual Tasks](https://mlsanity.com/paper/2511.07025/) (2025)
- [Lost in Benchmarks? Rethinking Large Language Model Benchmarking with Item Response Theory](https://mlsanity.com/paper/2505.15055/) (2025)
- [GISTEmbed: Guided In-sample Selection of Training Negatives for Text Embedding Fine-tuning](https://mlsanity.com/paper/2402.16829/) (2024)
- [Finding Near-Optimal Independent Sets at Scale](https://mlsanity.com/paper/1509.00764/) (2015)
- [Reliable and Efficient Amortized Model-based Evaluation](https://mlsanity.com/paper/2503.13335/) (2025)
- [How Benchmark Prediction from Fewer Data Misses the Mark](https://mlsanity.com/paper/2506.07673/) (2025)
- [SELECTOR: Selecting a Representative Benchmark Suite for Reproducible Statistical Comparison](https://mlsanity.com/paper/2204.11527/) (2022)
- [Learning Compact Representations of LLM Abilities via Item Response Theory](https://mlsanity.com/paper/2510.00844/) (2025)
- [Accelerating Local Search for the Maximum Independent Set Problem](https://mlsanity.com/paper/1602.01659/) (2016)
- [PS-AAS: Portfolio Selection for Automated Algorithm Selection in Black-Box Optimization](https://mlsanity.com/paper/2310.10685/) (2023)

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

- [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)

Evaluating large language models (LLMs) across comprehensive benchmarks is expensive and time-consuming. We propose a graph-based prompt selection framework that models each benchmark as a similarity graph -- nodes are prompts connected if their embedding-space distance falls above a configurable threshold -- and applies Maximum Independent Set (MIS) algorithms to select a maximally diverse, non-redundant subset. We evaluate four MIS solvers (CPLEX, GREEDY, Online-MIS, ReduMIS) across six embedding models, three distance measures, six percentile thresholds, and four benchmarks (GPQA, IFEval, MMLU-Pro, Omni-MATH) covering 66 LLMs. Our central hypothesis -- that repeated selection under different random seeds yields consistent LLM rankings that may also differ from the full-benchmark baseline -- is strongly confirmed: Kendall's W ≥ 0.90 in 99.2% of stochastic configurations (mean W = 0.997 ± 0.008), while at higher percentile thresholds selected subsets achieve 25--48% prompt reduction on average. Ranking divergence from the full benchmark (ρ < 0.95) occurs in only 15.95% of configurations, concentrated at low thresholds (p10--p20) and benchmarks (GPQA, IFEval), identifying overly dense graphs as the primary failure mode.