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 ≥ 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.