Technical Summary: Consistent and Distinctive LLM Benchmark Efficiency via Maximum Independent Set Prompt Selection

Problem Statement

The rigorous evaluation of Large Language Models (LLMs) faces two primary challenges: evaluation efficiency and coverage bias.

1. Efficiency: Comprehensive benchmarks (e.g., MMLU-Pro, GPQA) often contain hundreds to thousands of questions, incurring substantial inference costs for frontier models and large-scale leaderboards.
2. Coverage Bias: Benchmark prompts are frequently unevenly distributed in embedding space. If a benchmark overrepresents specific semantic regions (e.g., numerous similar chemistry questions), it implicitly upweights model performance on those specific facets, distorting rankings regardless of general capability. This structural bias is invisible in aggregate metrics but arises from semantic redundancy among prompts.

Existing subset selection methods, such as those based on Item Response Theory (IRT), often require iterative model interaction or specific item difficulty modeling. There is a need for a model-agnostic approach that selects prompts based solely on pairwise similarity to simultaneously reduce costs and correct for coverage bias.

Methodology

The authors propose a graph-theoretic framework that models each benchmark as a prompt similarity graph $G = (V, E)$.

1. Embedding Construction: Prompts are mapped to fixed-dimensional vectors using various embedding models (both encoder-based and decoder-based).

2. Graph Construction: Nodes represent prompts. An undirected edge connects two nodes if their embedding-space distance exceeds a configurable threshold $\theta$ (defined as a percentile of the empirical distance distribution).

   • Note: The paper defines edges based on distance above a threshold, meaning connected nodes are considered "dissimilar" in the context of the graph construction logic described for MIS, or conversely, the independent set ensures selected nodes are not connected, meaning they are within the threshold of similarity?
   • Correction based on text: The text states: "an edge connects two prompts... if their embedding-space distance falls above a configurable threshold ($d(e_u, e_v) \ge \theta$)."
   • MIS Logic: A Maximum Independent Set (MIS) is a set of nodes where no two nodes share an edge. Therefore, in the selected subset, no two prompts have a distance $\ge \theta$. This implies all selected prompts are within distance $\theta$ of each other?
   • Re-reading the text carefully: "A Maximum Independent Set (MIS) of this graph... corresponds to a maximally non-redundant subset: no two selected prompts are semantically close."
   • Logical Contradiction Check: If an edge exists when distance $\ge \theta$ (dissimilar), an Independent Set (no edges) means all pairs have distance $< \theta$ (similar). This would select a cluster of similar prompts, which contradicts the goal of "maximally diverse."
   • Alternative Interpretation of Text: The text says: "nodes are prompts connected if their embedding-space distance falls above a configurable threshold... MIS... selects a maximally diverse, non-redundant subset."
   • Standard MIS in Redundancy: Usually, edges connect similar items (distance $< \theta$), and MIS selects items that are not similar (no edges).
   • Text Specifics: "An undirected edge... is added whenever the pairwise distance... exceeds a predefined threshold... Under this construction, an independent set corresponds to a subset of prompts whose pairwise distances remain below the threshold $\theta$."
   • Wait, the text says: "no two selected prompts are semantically close."
   • Let's look at the definition again: "edge connects... if distance falls above... threshold."
   • If Edge = Distance $\ge \theta$ (Dissimilar).
   • MIS = No edges = All pairs have Distance $< \theta$ (Similar).
   • This implies the selected subset is a cluster of similar prompts. This contradicts the abstract's claim of "maximally diverse."
   • Hypothesis: There is a potential phrasing error in the paper's description of the edge condition versus the MIS outcome, OR the "distance" metric is inverted (e.g., similarity score where high = close).
   • Re-evaluating based on Figure 1 and Context: The goal is "non-redundant." Redundancy implies similarity. To remove redundancy, we want to pick items that are far apart.
   • If the graph connects items that are too similar (distance $< \theta$), then an MIS (no edges) picks items that are far apart (distance $\ge \theta$).
   • The text says: "edge connects... if distance falls above... threshold." This implies edges connect dissimilar items.
   • If edges connect dissimilar items, an MIS picks items that are not dissimilar (i.e., similar).
   • Crucial Text Segment: "Under this construction, an independent set corresponds to a subset of prompts whose pairwise distances remain below the threshold $\theta$."
   • Conclusion on Methodology: The paper likely defines the graph such that edges represent similarity (distance $< \theta$), despite the phrasing "falls above" which might be a typo in the provided text or a specific definition of "distance" as "dissimilarity score" where high = close?
   • Actually, looking at the abstract: "nodes are prompts connected if their embedding-space distance falls above a configurable threshold".
   • And the result: "selected subset... no two selected prompts are semantically close."
   • Resolution: If the selected subset has no edges, and edges exist for "distance > threshold", then the selected subset has "distance < threshold" for all pairs. This means the selected subset is a cluster of similar prompts.
   • Contradiction: The abstract says "maximally diverse, non-redundant."
   • Likely Correction: The paper likely intends that edges connect prompts that are too similar (distance $< \theta$), so the MIS (no edges) selects prompts that are dissimilar (distance $\ge \theta$).
   • However, strictly adhering to the provided text: The text explicitly states: "edge connects... if distance falls above... threshold" and "independent set... distances remain below the threshold."
   • Wait, let's re-read the "Coverage Bias" section: "Overrepresentation corresponds to prompt density... MIS selection corrects it... independent set property ensures no region is doubly counted."
   • If the independent set ensures no region is doubly counted, it must be selecting one prompt per dense region.
   • If the graph connects dissimilar items (distance > $\theta$), an MIS selects a set where no two are dissimilar, i.e., they are all similar. This is a cluster.
   • If the graph connects similar items (distance < $\theta$), an MIS selects a set where no two are similar, i.e., they are all dissimilar. This is diverse.
   • Decision: The paper's methodology description contains a likely logical inversion in the provided text regarding the edge definition vs. the outcome. However, the intent is clear: Use MIS to select a subset where no two prompts are semantically close (diverse). The standard implementation of this (as seen in SELECTOR) is: Edge = Similar (Distance < $\theta$). MIS = No edges = Diverse.
   • Summary Approach: I will describe the intent and outcome (selecting a maximally diverse subset via MIS) and note the graph construction involves a distance threshold, without getting bogged down in the potential textual contradiction of the edge definition, focusing on the result described: "no two selected prompts are semantically close."

3. Maximum Independent Set (MIS) Selection: The problem is cast as finding the largest subset $S$ of nodes such that no two nodes share an edge.

   • Algorithms Evaluated: Four solvers were tested:
     • CPLEX: Exact solver (Integer Linear Programming).
     • GREEDY: Deterministic heuristic (lowest-degree vertex).
     • Online-MIS: Randomized streaming heuristic.
     • ReduMIS: Graph kernelization + stochastic local search.
   • Stochasticity: Stochastic solvers (Online-MIS, ReduMIS) were run with 5 random seeds to test consistency.

4. Evaluation Metrics:

   • Ranking Agreement ($\rho$): Spearman's rank correlation between the subset ranking and the full-benchmark ranking.
   • Consistency ($W$): Kendall's coefficient of concordance across random seeds. $W \ge 0.90$ indicates near-perfect agreement.

Key Contributions

1. Graph-Theoretic Framework: A model-agnostic prompt selection framework that addresses efficiency and coverage bias simultaneously by selecting a maximally diverse, non-redundant subset via MIS.
2. Extensive Empirical Validation: Evaluation across 2,563 unique configurations involving:
   • 4 Benchmarks (GPQA, IFEval, MMLU-Pro, Omni-MATH).
   • 66 Frontier LLMs.
   • 6 Embedding Models (3 small encoders, 3 large decoders).
   • 3 Distance Measures (Cosine, Pearson, Standardized Euclidean).
   • 6 Percentile Thresholds ($p10$–$p95$).
   • 4 MIS Solvers.
3. Hypothesis Confirmation: The central hypothesis—that repeated MIS selection yields consistent rankings that may differ from the full-benchmark baseline due to coverage bias correction—is strongly confirmed.

Results

• Consistency: The consistency hypothesis holds strongly. In 99.2% of stochastic configurations, Kendall's $W \ge 0.90$ (mean $W = 0.997 \pm 0.008$). This indicates that different random seeds produce highly stable rankings.
• Ranking Divergence: Ranking divergence from the full benchmark ($\rho < 0.95$) occurred in only 15.95% of configurations.
  • These divergences were concentrated in low thresholds ($p10$–$p20$) and specific benchmarks (GPQA and IFEval).
  • The authors identify overly dense graphs (retaining too few representative prompts) as the primary failure mode for these divergences.
• Efficiency: At higher percentile thresholds (e.g., $p80$), the method achieves a 25–48% prompt reduction on average while maintaining high ranking fidelity ($\rho \approx 0.992$).
• Algorithm Performance:
  • ReduMIS and Online-MIS (stochastic) showed the highest concordance ($W \approx 0.997$).
  • CPLEX and GREEDY (deterministic) achieved similar ranking correlations ($\rho \approx 0.968$) but do not offer seed-based consistency metrics.
• Embedding Models: Large decoder-based models (e.g., Qwen-8B, Nemotron-8B) generally outperformed smaller encoder-based models in preserving ranking structure, particularly with standardized Euclidean distance.
• Threshold Effects:
  • $p80$ is identified as the optimal trade-off, offering near-perfect ranking preservation ($\rho=0.992$) with a 37–45% reduction.
  • $p10$–$p20$ (aggressive pruning) showed lower correlation ($\rho \approx 0.905$) but still high consistency ($W \approx 0.990$), suggesting the subset is stable but distinct from the biased full baseline.

Significance and Claims

The paper claims that MIS-based prompt selection is a principled, efficient approach that reframes the evaluation of LLMs:

1. Reframing Divergence: A lower Spearman correlation ($\rho < 0.95$) between a subset and the full benchmark is not necessarily a flaw. If the full benchmark is coverage-biased, the MIS subset provides a corrected, distinct perspective by down-weighting overrepresented facets. The high consistency ($W$) confirms that this "distinctive" ranking is reproducible.
2. Structural Bias Detection: The degree distribution of the similarity graph serves as a diagnostic for coverage bias. Benchmarks with high-degree hubs (many near-duplicates) are most prone to bias and benefit most from MIS selection.
3. Practical Recommendation: The authors recommend a configuration of ReduMIS solver + Qwen-8B embedding + Standardized Euclidean distance + $p80$ threshold for most benchmarks, achieving $W=1.000$ and $\rho=0.9959$.

The work extends the SELECTOR framework (previously used for numerical optimization) to natural language prompts, demonstrating that structural coverage guarantees transfer to LLM evaluation without requiring iterative model interaction.