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

Researchers propose a graph-based framework using Maximum Independent Set algorithms to efficiently benchmark large language models by selecting diverse, non-redundant prompt subsets. Testing across 66 LLMs and four major benchmarks demonstrates consistent rankings with 25-48% prompt reduction while maintaining reliability, offering significant computational savings for LLM evaluation.

The research addresses a critical operational challenge in AI development: LLM evaluation has become prohibitively expensive as models and benchmarks grow larger. Traditional comprehensive benchmarking requires evaluating models against thousands of prompts, consuming substantial computational resources. This work introduces a methodologically sound approach to reduce evaluation scope without sacrificing ranking consistency or comparative validity.

The study's findings carry important implications for the AI development pipeline. By modeling benchmarks as similarity graphs and applying MIS algorithms, the researchers achieve a 25-48% reduction in required prompts while maintaining Kendall's W correlation above 0.90 in 99.2% of configurations. This consistency suggests that carefully selected subsets preserve the discriminative power of full benchmarks. The work validates that redundancy in benchmark prompts—where semantically similar questions produce correlated model responses—can be systematically eliminated without degrading evaluation quality.

For AI developers and researchers, this framework directly impacts resource allocation and development velocity. Faster, cheaper benchmarking enables more frequent model iteration and broader comparative analysis across variants. The identification of failure modes—particularly at lower percentile thresholds and in denser benchmarks like GPQA—provides practical guidance for implementation, allowing practitioners to select appropriate thresholds for their specific evaluation needs.

Looking forward, the framework's scalability to emerging benchmarks and integration with automated model development pipelines warrants investigation. The research suggests future work should explore threshold optimization strategies tailored to specific benchmark characteristics and investigate whether selected subsets generalize across different model architectures or training paradigms.

• →Maximum Independent Set algorithms enable 25-48% prompt reduction while maintaining consistent LLM rankings (Kendall's W ≥ 0.90)
• →Selected prompt subsets diverge from full benchmarks in only 15.95% of configurations, concentrated at lower density thresholds
• →Framework models benchmarks as similarity graphs where nodes represent prompts and edges indicate semantic redundancy above threshold
• →Evaluation across 66 LLMs and four benchmarks (GPQA, IFEval, MMLU-Pro, Omni-MATH) demonstrates broad applicability and robustness
• →Dense graphs at low percentile thresholds identified as primary failure mode, offering clear guidance for practical implementation