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

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\ge 0.90$ in 99.2% of stochastic configurations (mean $W=0.997\pm 0.008$), while at higher percentile thresholds selected subsets achieve 25–48% prompt reduction on average. Ranking divergence from the full benchmark ($\rho <0.95$) occurs in only 15.95% of configurations, concentrated at low thresholds ($p_{10}$–$p_{20}$) and benchmarks (GPQA, IFEval), identifying overly dense graphs as the primary failure mode.