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

arXiv:2606.01400v1 Announce Type: cross Abstract: 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 geq 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.

Source: arXiv cs.AI | 2026-06-02