acceptodds
Under review as a conference paper at ICLR 2027

LLM Benchmark Compression via Maximum Independent Set Prompt Selection on Proximity Graphs

Abstract

Evaluating LLMs across comprehensive benchmarks is expensive, motivating benchmark compression: replacing a full benchmark with a compact subset that is cheaper to run. Whether such a method is usable comes down to fidelity—when does the subset reproduce the full-benchmark LLM ranking, and when does it diverge? We model each benchmark as a prompt proximity graph—nodes are prompts, and an edge joins two prompts whose embeddings are close enough to be treated as semantically redundant—and apply Maximum Independent Set (MIS) solvers to select a maximally diverse, non-redundant subset in which no semantic region is doubly counted. We evaluated four MIS solvers across six embeddings, three distances, six percentile thresholds, and four benchmarks (GPQA, IFEval, MMLU-Pro, Omni-MATH) covering 66 LLMs, spanning 2,558 configurations. Two axes emerge and move almost independently. First, selection is consistent: different random seeds yield near-identical rankings (Kendall's in 84.5% of stochastic configurations; mean ), so the procedure itself is reliable. Second, agreement with the full-benchmark ranking is governed by how aggressively the graph is pruned, giving a controllable efficiency–fidelity trade-off: mild thresholds (–) preserve the full ranking (–) while removing 64–82% of prompts, whereas aggressive pruning (–) trades fidelity for compression (–). Because the axes separate, the grid becomes a recipe: the threshold decides whether a subset stays reliable-and-faithful, and the embedding decides how it fails once it diverges. Divergence concentrates at high thresholds and on the more discretized benchmarks (GPQA, IFEval); when it occurs, a category-level analysis shows MIS redistributes prompt mass toward uniform coverage, which we report descriptively. We recommend ReduMIS with qwen8b embeddings, standardized-Euclidean distance, and a threshold as a strong default operating point.

Primary area:
datasets and benchmarks
Keywords:
benchmark compression, LLM evaluation, maximum independent set, prompt selection, proximity graphs

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_TiCKOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies LLM benchmark compression using prompt embeddings and graph-based subset selection. It constructs proximity graphs and applies exact or heuristic maximum independent set (MIS) solvers to select mutually separated prompts. For a fixed configuration, subset construction requires neither evaluated-model responses nor category labels. The empirical study covers four HELM benchmark subsets, 66 LLMs, and 2,558 configurations spanning embeddings, distances, thresholds, and solvers. The evaluation distinguishes fidelity to full-benchmark rankings from consistency of model rankings across selection seeds, and additionally examines absolute-score error, overlap among top-ranked models, and category redistribution. At p20p_{20}, the paper reports mean Spearman correlation of 0.967 with approximately 74–82% prompt reduction. It recommends ReduMIS with Qwen-8B embeddings and standardized-Euclidean distance, identifying seed consistency and coverage as its main advantages over sampling.

Critical strengths
  • The study provides a useful empirical analysis of benchmark sensitivity to compression and interactions between embeddings and distance measures. Table 9 identifies a useful mild-compression regime and quantifies degradation under aggressive pruning. Reporting random sampling’s stronger aggregate fidelity and lower MAE makes the study informative about the limitations of semantic selection (Tables 16 and 19).
  • The selection procedure does not require a pre-existing matrix of model responses (Section 3 and Appendix B). The independent-set constraint provides an explicit pairwise-separation property in the chosen embedding space, and the resulting subset can be reused for subsequent model evaluations. This is practically attractive when historical model evaluations are unavailable.
Critical weaknesses
  • The reported baseline results contain numerical inconsistencies. Because the graph-selection principle builds on prior work such as SELECTOR (Cenikj et al., 2022), the paper’s contribution depends primarily on the reliability of its empirical findings and practical guidance. The “reliable and faithful” quadrant is defined by ρ≥0.70\rho\ge0.70 and W≥0.90W\ge0.90. Page 18 reports that 44% of stratified configurations occupy this quadrant, whereas Table 13 reports 61.1%. Applying the stated thresholds to Table 16 gives 10/18 = 55.6% for both stratified and uniform-stratified sampling; Table 13 reports 50.0% for the latter. Furthermore, GPQA/p95p_{95}/uniform-stratified is reported as (ρ,W)=(0.685,0.549)(\rho,W)=(0.685,0.549) on p. 18 and (0.743,0.607)(0.743,0.607) in Table 16, placing it in different quadrants. These discrepancies cannot be explained by rounding and affect method-specific rates and conclusions about failure modes. Table 16 still shows higher WW for MIS in the reported comparisons, but these inconsistencies leave the magnitude of this advantage uncertain.
  • The coverage comparison suffers from a separate budget confound. Baseline subset sizes are matched to the average MIS subset size for each threshold–benchmark combination, rather than to the size of the specific MIS subset being evaluated. Specifically, Appendix F, p. 23, acknowledges that Figures 13–15 compare MIS subsets of 116, 284, and 332 prompts with baseline subsets of 82, 204, and 187, respectively. Because category bars are normalized by full-benchmark size, larger bars can reflect the larger retained subset. These figures cannot establish an equal-budget coverage advantage. Figure 1 uses a 2% uniform-reference line when comparing the full-benchmark and subset distributions. This reference is appropriate for the subset, but the corresponding reference for the full benchmark is approximately 7.14%. The figure therefore does not directly show that the subset has a more uniform category distribution. A comparison at the same subset size is needed to substantiate the recommended configuration’s claimed coverage advantage over sampling.
  • The behavioral analysis does not establish that semantically similar prompts provide redundant information about model performance. Figure 5 reports only weak correlations between the difficulty of retained prompts and that of discarded prompts, approximately r=0.16r=0.16–0.290.29. Statistical significance does not establish interchangeability, and prompts with similar average difficulty may still differ in their ability to distinguish between models. Appendix K/Figure 29 finds essentially no relationship between embedding distance and response-vector similarity within the selected neighbor pairs, yet Section 5 treats this as evidence that the threshold identifies evaluative redundancy. A flat relationship within the selected distance range does not establish that the threshold separates redundant from nonredundant pairs. The analysis lacks a suitable control comparison—for example, non-neighbor or random pairs—that accounts for category and marginal difficulty. The authors should either support the mechanistic conclusions with a control analysis using the existing response matrix or narrow those conclusions.
Questions for authors
  1. Which baseline results are authoritative, and how are ties handled when computing WW? Please reconcile the results on p. 18, in Figure 11, and in Tables 13 and 16. Would resolving these discrepancies or applying standard tie corrections change the main findings?
  2. How does the recommended configuration compare with sampling at the same subset size in fidelity, MAE, ranking consistency, and coverage? Please distinguish retained category counts from within-subset proportions.
  3. Do selected neighbor pairs show greater similarity in model predictions than suitable control pairs? A comparison accounting for category and marginal difficulty would clarify whether evaluative redundancy is supported.
  4. What is the prompt-similarity annotation study mentioned in the Ethics Statement? Page 10 refers to a study conducted by the authors’ team, but I could not locate its methods or results. If it supports the reported conclusions, please identify the evidence; otherwise, clarify its role.
4 comments
AuthorsOpenReview ↗

Q1: Authoritative baseline results and tie handling

Question: Which baseline results are authoritative, and how are ties handled when computing WW? Please reconcile the results on p. 18, in Figure 11, and in Tables 13 and 16. Would resolving these discrepancies or applying standard tie corrections change the main findings?

Thank you for identifying the discrepancies. We rechecked the reported values against the experimental results and corrected the discrepancies in the revised manuscript. The discrepancies arose because the script that produced Tables 12–15, Figure 11, and the corresponding text on p. 18 redrew the stratified and uniform-stratified baseline samples with a different random stream from the analysis behind Table 16. Table 16 is authoritative. We regenerated Tables 12–15, Figure 11, and the text from the same draws as Table 16: stratified and uniform-stratified sampling are both reliable-and-faithful in 55.6% of configurations, no baseline configuration is reliable-but-reshaped, and the only baseline configuration below ρ = 0.70 is random sampling on GPQA at p90 (ρ = 0.6999). The GPQA p95 uniform-stratified case described on p. 18 (ρ = 0.685, W = 0.549) came from the redrawn samples; in the final run, this configuration has ρ = 0.743 and W = 0.607. In the same check, we found that Table 5 omitted the standardized-Euclidean configurations because of a naming mismatch; the corrected table changes the mean overlaps by at most 0.04 and leaves the conclusions unchanged.

Ties. Rankings use average ranks for tied scores, and Spearman’s ρ is computed on these ranks. Kendall’s W was computed without tie correction, which slightly underestimates concordance when rankings contain ties (identical rankings with ties give W slightly below 1, e.g. 0.9993). With the standard tie correction, W increases mainly for very small subsets, where many models tie: the share of stochastic MIS configurations with W ≥ 0.90 rises from 84.9% to 89.1% (mean W from 0.950 to 0.967), 54 of the 1,262 configurations move from a seed-unstable to the corresponding seed-stable quadrant, and one baseline configuration changes quadrant (uniform-stratified, GPQA p50: W = 0.898 to 0.903). Because the correction can only increase W, it strengthens rather than changes the concordance results, and the main findings remain unchanged. We now report tie-corrected W alongside the original values.

In the revised manuscript, the definition of Kendall’s W with and without tie correction is given in Section 3, the corrected baseline results are in Appendix G (Tables 16, 17 and 19), and the tie-correction analysis is in Appendix D (Tables 7 and 13).

AuthorsOpenReview ↗

Q2: Recommended configuration vs. same-size sampling

Question: How does the recommended configuration compare with sampling at the same subset size in fidelity, MAE, ranking consistency, and coverage? Please distinguish retained category counts from within-subset proportions.

The results show that at equal size, the recommended configuration is as faithful as sampling and provides more balanced category coverage without using labels. We compared it with 1,000 draws each of random, stratified, and uniform-stratified sampling at exactly its subset size. At p20, ρ is within 0.007 of random and stratified sampling on all four benchmarks (e.g., 0.975 vs. 0.980 on GPQA and 0.996 vs. 0.996 on Omni-MATH). Category coverage, measured on within-subset proportions by normalized entropy (1 = all categories equally represented), is 0.974 vs. 0.936 for random sampling on GPQA, 0.978 vs. 0.969 on MMLU-Pro and 0.810 vs. 0.775 on Omni-MATH; the MIS subset is more balanced than 96%, 92% and over 99% of same-size random subsets, respectively, and more balanced than the median random subset in 17 of 18 benchmark–threshold cells. MAE is higher for MIS (e.g., 4.8 vs. 3.0 points on GPQA) because redistributing coverage also changes the difficulty mix. Kendall’s W is 0.999–1.000 for MIS and 0.964–0.995 for the baselines, which reflects that ReduMIS returns the same subset across seeds rather than higher fidelity. We now report retained counts and within-subset proportions separately for every category: for example, on GPQA the MIS subset contains 32 Physics, 52 Chemistry and 32 Biology prompts (28%, 45% and 28% of the subset), compared with 48.4, 47.4 and 20.3 (42%, 41% and 18%) for random sampling.

In the revised manuscript, this comparison is described in Section 5 (Table 2 and “Category redistribution”) and in Appendix G (Tables 21–23 and Figures 14–16); Table 22 reports retained counts and within-subset proportions separately.

AuthorsOpenReview ↗

Q3: Neighbor pairs vs. matched control pairs

Question: Do selected neighbor pairs show greater similarity in model predictions than suitable control pairs? A comparison accounting for category and marginal difficulty would clarify whether evaluative redundancy is supported.

In the revised manuscript, we report these correlations separately for each embedding model, distance metric, and distance threshold. The results show that the correlations vary between configurations but not systematically. Across all 631 ReduMIS configurations (six embeddings, three distances, six thresholds, and all four benchmarks, now including IFEval), the difficulty correlation between each discarded prompt and its nearest retained prompt is positive in 89% of the configurations and positive on average for every embedding and distance, whereas random prompt pairs show no correlation (r = 0.00). No embedding is consistently strongest across benchmarks, and large decoders and small encoders reach similar values on average (at p20: 0.10–0.23 vs. 0.10–0.21 across the four benchmarks). Standardized Euclidean gives the highest or tied-highest correlation on three of the four benchmarks, and the alignment tends to decrease at aggressive thresholds. The same pattern holds for the benchmarks’ own difficulty annotations, which involve no model evaluations: at p20, the official difficulty ratings of neighbors correlate at r = 0.44 on Omni-MATH, and the question writers’ ratings at r = 0.22 on GPQA. Because no embedding yields markedly stronger alignment, this analysis does not change the recommended pipeline.

We also added the control comparison suggested by the reviewer, accounting for both category and marginal difficulty. For each discarded prompt and its nearest retained neighbor, we constructed a control pair: the same discarded prompt paired with a random prompt from the same category whose difficulty matches that of the retained neighbor (mean absolute difficulty difference 0.004). Comparing the two pairs for the same discarded prompt isolates the effect of embedding proximity, and we ran this comparison for all 469 configurations on the three category-labeled benchmarks. Embedding neighbors share a category far more often than random prompt pairs (at p20: 95% vs. 37% on GPQA, 59% vs. 8% on MMLU-Pro and 60% vs. 23% on Omni-MATH). Once category and difficulty are matched, however, neighbors agree on model outcomes as often as the control pairs: at p20, 58.2% vs. 57.7% on GPQA, 64.2% vs. 64.0% on MMLU-Pro and 62.5% vs. 62.5% on Omni-MATH, with differences within ±1.3 percentage points for every embedding.

The behavioral similarity between embedding neighbors is therefore accounted for by shared category and difficulty, which MIS recovers from the prompt text without labels or model evaluations; the benchmarks’ own difficulty annotations show the same (neighbors’ official Omni-MATH difficulty ratings correlate at r = 0.44). We have narrowed our claims accordingly: we no longer describe MIS as removing evaluative redundancy beyond what category and difficulty explain, but as removing semantic redundancy that captures category and difficulty structure without labels.

In the revised manuscript, this analysis is described in Section 5 (“Does embedding proximity imply evaluative redundancy?”, Table 3) and in Appendix L (“Matched controls”, Tables 38 and 39, and Figure 30b).

AuthorsOpenReview ↗

Q4: The annotation study mentioned in the Ethics Statement

Question: What is the prompt-similarity annotation study mentioned in the Ethics Statement? Page 10 refers to a study conducted by the authors’ team, but I could not locate its methods or results. If it supports the reported conclusions, please identify the evidence; otherwise, clarify its role.

Thank you for flagging this. The Ethics Statement referred to a planned study in which subject-matter experts would annotate prompt similarity. The study is still incomplete, and the original wording incorrectly implied that it had been completed. No data from the study were used in the reported analyses or conclusions. We have removed the reference from the revised Ethics Statement.

The revised Ethics Statement no longer refers to this study.

Reviewer_fQnAOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper addresses the escalating cost of full-benchmark LLM evaluation by proposing a graph-theoretic compression framework. The core idea is to model each benchmark as a prompt proximity graph, where edges connect prompts whose embeddings fall within a percentile-based distance threshold. A Maximum Independent Set (MIS) solver then selects a maximally non-redundant subset, thereby removing semantic duplication without requiring any model evaluations during construction. The authors conduct an extensive empirical campaign across four benchmarks (MMLU-Pro, GPQA, IFEval, Omni-MATH), 66 LLMs, six embedding models, three distance metrics, six thresholds, and four MIS solvers, yielding 2,558 configurations. The central findings are that (i) mild compression thresholds (p10–p20) preserve full-benchmark rankings with Spearman ρ = 0.97-0.98 while removing 64–82% of prompts, (ii) stochastic MIS solvers maintain high seed concordance, and (iii) size-matched baselines (random, stratified, uniform-stratified sampling) achieve comparable or slightly better absolute-accuracy fidelity (MAE) at mild thresholds but collapse into seed instability under aggressive pruning, whereas MIS remains seed-stable and drifts only in rank agreement. The paper recommends ReduMIS with Qwen8b/seuclidean at p20 as a strong default operating point.

Critical strengths

The most consequential strength is the model-agnostic, evaluation-free nature of subset construction. Unlike IRT-based or anchor-point methods that require a pool of model responses to fit item parameters, the MIS pipeline operates purely on prompt embeddings and can be run once, offline, then reused for any future model. The paper explicitly positions this against prior work (Section 2 and Appendix A), citing Perlitz et al. and Polo et al. as representative of response-driven approaches that cannot avoid model interaction. For practitioners facing a rapidly expanding model pool, this is a genuine practical advantage: the subset need not be re-derived each time a new LLM is added to the leaderboard. This directly supports the paper’s claimed contribution of a reusable compression artifact.

The second critical strength is the seed-stability characterization and its diagnostic value. The paper does not merely report average ranking fidelity; it decomposes the compression-fidelity plane into quadrants (Table 1) and shows that MIS’s divergence from the full benchmark predominantly takes the form of rank reshaping under aggressive pruning, whereas baselines diverge through seed instability. This distinction is empirically consequential: a seed-unstable subset (W < 0.90) scrambles the leaderboard head even when ρ remains high, which the top-N Jaccard analysis confirms (Section 5, "Top-N overlap across quadrants"). The finding that ReduMIS sustains W ≥ 0.90 almost everywhere while random and stratified sampling fall to W ≈ 0.65-0.79 at p90-p95 is a robust and practically important result. It reframes the choice between MIS and sampling not as a raw accuracy-fidelity contest but as a stability-versus-simplicity trade-off, and it gives benchmark curators a concrete diagnostic (graph topology, threshold regime) for anticipating which failure mode they will encounter.

Critical weaknesses

The central theoretical vulnerability is that the core assumption is only weakly supported by the paper’s own behavioral validation. In Section 5 (“Does embedding proximity imply evaluative redundancy?”), the authors pair each retained prompt with its nearest discarded neighbor and correlate their difficulties and response-vector similarities across 66 LLMs. The correlations are modest: r ≈ 0.16-0.18 on GPQA and MMLU-Pro, and r ≈ 0.29 on Omni-MATH. The paper frames this as evidence that "a retained prompt probes a comparable difficulty level," but the scatter is substantial, and the response-vector analysis in Appendix K shows that embedding distance does not predict behavioral similarity (|r| ≤ 0.10 within benchmarks). The authors themselves concede that "it is the threshold, not the exact distance, that identifies redundancy." If the embedding geometry is only loosely coupled to model behavior, the justification for treating MIS selection as redundancy removal is weakened. This matters because the paper’s interpretive claims about "coverage redistribution" (e.g., that MIS pulls MMLU-Pro’s math and physics categories toward uniformity) presuppose that embedding-space redundancy maps onto genuine evaluative duplication. The modest behavioral correlations leave open the possibility that MIS is primarily selecting semantically diverse prompts that are not necessarily evaluatively redundant, which would undercut the framing of the method as a principled compression of benchmark coverage.

A second weakness is that the practical advantage over simple baselines is narrower than the paper’s framing suggests. The size-matched random and stratified baselines attain marginally lower MAE at every threshold (Table 19: 1.97 vs. 2.81 at p10; 9.69 vs. 12.21 at p95) and comparable or slightly better Spearman ρ at mild thresholds (Table 16). The paper acknowledges this and pivots to seed stability as MIS’s distinguishing virtue, which is fair. But for a practitioner whose primary objective is to preserve absolute accuracy or ranking fidelity at a fixed budget under a single evaluation run, random sampling is a viable and simpler alternative. The paper’s recommendation of the full MIS pipeline (with a specific embedding, distance metric, and solver) is well-supported for settings where reproducibility across seeds and balanced coverage are paramount, but the decision calculus is not as lopsided as the "recommended operating point" framing might imply. The paper could strengthen its case by explicitly characterizing the regimes, where the seed-stability gap between MIS and random sampling translates into meaningfully different leaderboard conclusions.

Questions for authors
  1. The behavioral correlations (r ≈ 0.16–0.29) are modest. Could the authors report whether these correlations vary systematically by embedding model or distance metric? If a different embedding (e.g., one of the large decoders) yields stronger alignment between embedding distance and response-vector similarity, would that alter the recommended pipeline? Conversely, if the correlation remains weak across embeddings, how should readers interpret the claim that MIS removes "evaluative redundancy" rather than merely semantic diversity?

  2. The seed-stability advantage of MIS is clear in the aggregate, but the paper does not report the cost of achieving it: specifically, the wall-clock time for ReduMIS (up to 600 s on a 1,000-node graph, per Section 4) versus the negligible cost of random sampling. For a benchmark curator deciding whether to invest in MIS preprocessing, a more explicit cost-benefit comparison (including the embedding-generation cost) would be valuable.

  3. The paper restricts to single-turn benchmarks and flags multimodal/agentic transfer as future work. Given that many frontier evaluations increasingly involve multi-turn interaction and tool use, could the authors comment on whether the MIS framework’s assumptions would remain meaningful for agentic benchmarks where prompts are trajectories rather than isolated inputs?

  4. The recommendation of Qwen8b/seuclidean at p20 is derived from the same grid used for evaluation. To guard against overfitting the recommendation to these four benchmarks, could the authors report whether the relative ordering of embeddings (e.g., large decoders outperforming small encoders) is stable when holding out one benchmark entirely? A leave-one-benchmark-out analysis would strengthen confidence that the recipe is not benchmark-specific.

4 comments
AuthorsOpenReview ↗

Q1: Behavioral correlations by embedding model and distance metric

Question: The behavioral correlations (r ≈ 0.16–0.29) are modest. Could the authors report whether these correlations vary systematically by embedding model or distance metric? If a different embedding (e.g., one of the large decoders) yields stronger alignment between embedding distance and response-vector similarity, would that alter the recommended pipeline? Conversely, if the correlation remains weak across embeddings, how should readers interpret the claim that MIS removes "evaluative redundancy" rather than merely semantic diversity?

Thank you for this comment. We agree that the reported correlations (r≈0.16r \approx 0.16–0.290.29) indicate modest alignment between embedding distance and similarity in how models respond to prompts. In the revised manuscript, we report these correlations separately for each embedding model, distance metric, and distance threshold. The results show that the correlations vary between configurations but not systematically. Across all 631 ReduMIS configurations (six embeddings, three distances, six thresholds and all four benchmarks, now including IFEval), the difficulty correlation between each discarded prompt and its nearest retained prompt is positive in 89% of the configurations and positive on average for every embedding and distance, whereas random prompt pairs show no correlation (r = 0.00). No embedding is consistently strongest across benchmarks, and large decoders and small encoders reach similar values on average (at p20: 0.10–0.23 vs. 0.10–0.21 across the four benchmarks). Standardized Euclidean gives the highest or tied-highest correlation on three of the four benchmarks, and the alignment tends to decrease at aggressive thresholds. The same pattern holds for the benchmarks’ own difficulty annotations, which involve no model evaluations: at p20, the official difficulty ratings of neighbors correlate at r = 0.44 on Omni-MATH, and the question writers’ ratings at r = 0.22 on GPQA. Because no embedding yields markedly stronger alignment, this analysis does not change the recommended pipeline.

We have also clarified what we mean by “evaluative redundancy.” MIS selects a subset by excluding prompts that are close to retained prompts in the chosen embedding space. The modest correlations suggest that this proximity is only a weak proxy for similarity in model responses.

In the revised manuscript, this analysis is described in Section 5 (“Does embedding proximity imply evaluative redundancy?”, Table 3 and Figure 5) and in Appendix L (Tables 34–37 and Figure 30).

AuthorsOpenReview ↗

Q2: Cost of MIS preprocessing and when it pays off

Question: The seed-stability advantage of MIS is clear in the aggregate, but the paper does not report the cost of achieving it: specifically, the wall-clock time for ReduMIS (up to 600 s on a 1,000-node graph, per Section 4) versus the negligible cost of random sampling. For a benchmark curator deciding whether to invest in MIS preprocessing, a more explicit cost-benefit comparison (including the embedding-generation cost) would be valuable.

Thank you for raising this point. We added a discussion of when the one-time cost of MIS preprocessing is justified.

Preprocessing cost. MIS requires prompt embedding, proximity graph construction, and solving. Embedding all 2,987 prompts across the four benchmarks with three decoder models, with and without chunking, took 52 min 42 s of wall-clock time on two NVIDIA L40S GPUs (24 embedding runs in total, Appendix M). Graph construction computes pairwise distances among at most 1,000 prompts per benchmark. The 600 s reported in Section 4 is the single-threaded time limit for each ReduMIS job. For the recommended configuration (Qwen8b, standardized Euclidean distance, p20), ReduMIS matched the optimal subset size found by CPLEX on every benchmark and seed. CPLEX took approximately 30–120 s per benchmark. On the same graphs, GREEDY took under one second, selected at most six fewer prompts, and achieved similar agreement with the full ranking (Spearman ρ = 0.974–0.997 for GREEDY and 0.975–0.998 for ReduMIS). Uniform random sampling has negligible selection cost and requires only a target subset size.

Benefits at matched subset sizes. The recommended configuration retains 26–37% of the prompts, reducing the number of prompt evaluations by 63–74% each time a new model is evaluated. A size-matched random subset offers the same reduction in prompt evaluations. The added value of MIS is that it determines the subset size from the proximity graph, guarantees that no two selected prompts are closer than the specified threshold, and yields highly consistent rankings across solver seeds. For size-matched random sampling, the SD of ρ reached 0.008 at p10 and 0.023 at p20. On IFEval, an individual random draw yielded ρ = 0.910. This variability matters when a curator publishes a single reduced benchmark and reuses it for future evaluations.

Practical trade-off. For a one-off evaluation with a predefined prompt budget, random sampling has negligible setup cost and can achieve comparable expected ranking agreement in our experiments. For a benchmark reused across many models or leaderboard updates, the one-time preprocessing cost is spread across evaluations, and a reproducible subset with an explicit redundancy constraint can justify that cost.

In the revised manuscript, this discussion is in Section 6 (“Cost and when MIS pays off”), and the computational details are in Appendix M (Table 40).

AuthorsOpenReview ↗

Q3: Extension to agentic and multi-turn benchmarks

Question: The paper restricts to single-turn benchmarks and flags multimodal/agentic transfer as future work. Given that many frontier evaluations increasingly involve multi-turn interaction and tool use, could the authors comment on whether the MIS framework’s assumptions would remain meaningful for agentic benchmarks where prompts are trajectories rather than isolated inputs?

Thank you for this comment. The MIS framework can be extended to agentic benchmarks by treating each trajectory as a node in the proximity graph. The key requirement is that trajectories can be represented in a common feature space, using meta-features that capture evaluation-relevant aspects of the interaction, such as the sequence of actions, tool calls and their outcomes, and how the task progresses across turns. The distance metric and threshold would then determine which trajectories are considered similar enough to connect.

A practical distinction is whether the benchmark provides fixed trajectories or generates them during evaluation. Fixed trajectories can be represented and selected directly. When trajectories depend on the evaluated agent, selecting tasks before evaluation would require task-level features or trajectories collected from reference agents. In either case, whether proximity in the chosen feature space captures evaluative redundancy is an empirical question. A natural validation would be to test whether the selected subset preserves agent rankings on the full benchmark. We added this clarification in the discussion of the revised manuscript.

In the revised manuscript, this discussion is in Section 6 (“Agentic and multi-turn benchmarks”).

AuthorsOpenReview ↗

Q4: Transfer of the recommended configuration to held-out benchmarks

Question: The recommendation of Qwen8b/seuclidean at p20 is derived from the same grid used for evaluation. To guard against overfitting the recommendation to these four benchmarks, could the authors report whether the relative ordering of embeddings (e.g., large decoders outperforming small encoders) is stable when holding out one benchmark entirely? A leave-one-benchmark-out analysis would strengthen confidence that the recipe is not benchmark-specific.

Thank you for this suggestion. We added a leave-one-benchmark-out analysis to assess how well configuration rankings transfer to a benchmark excluded from the ranking procedure.

How we selected the recommendation in the original submission. We averaged Spearman’s ρ and Kendall’s W across the four benchmarks and both chunking variants for each of the 216 configurations spanning embedding models, distance metrics, thresholds, and two stochastic solvers (Online-MIS and ReduMIS). Qwen8b with standardized Euclidean distance, p20, and ReduMIS ranked third overall and first among p20 configurations (fifth by ρ = 0.984 and fourth by W = 0.9997). The two higher-ranked configurations used the milder p10 threshold, retained more prompts, and improved ρ by at most 0.002. We therefore recommend p20 for its balance between compression and ranking fidelity. With Online-MIS, the same embedding, distance, and threshold achieved similar fidelity (ρ = 0.983), with lower agreement across seeds (W = 0.997, 30th by W).

Transfer to a held-out benchmark (new experiment added in the revised manuscript). We evaluated the 290 stochastic configurations available on all four benchmarks, treating chunked and unchunked variants separately. In each fold, we ranked configurations by mean ρ and mean W on the three retained benchmarks. We then compared each ranking with the corresponding ranking on the held-out benchmark using Kendall’s τ_b. Agreement was positive in every fold (all p < 10⁻²⁹), with τ_b ranging from 0.603 to 0.757 for ρ and from 0.453 to 0.689 for W. Agreement for W was lowest on IFEval.

Performance of the recommended configuration. Across the four folds, the recommended configuration ranked 10th–16th by ρ and 5th–11th by W on the three retained benchmarks. On the held-out benchmarks, it ranked 5th–16th by ρ on IFEval, MMLU-Pro, and Omni-MATH (top 6%), and 36th–37th on GPQA (top 13%). It ranked 1st–17th by W on every held-out benchmark (top 6%). Across all four benchmarks and both chunking variants, its held-out scores were ρ = 0.975–0.998 and W ≥ 0.999.

These results show that configuration rankings transfer across the four benchmarks and that the recommended configuration maintains high ranking fidelity and seed stability in every fold.

In the revised manuscript, this analysis is described in Section 5 (“Recommended configuration”) and in Appendix E (Table 15).

Reviewer_X26jOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies LLM benchmarks compression/efficient evaluation while preserving the full-benchmark model ranking. It models each benchmark as a prompt proximity graph, connecting prompts whose embeddings are close enough to be treated as semantically redundant, and applies Maximum Independent Set (MIS) solvers to select a maximally diverse, non-redundant subset.

Across a large grid of embeddings, distances, thresholds and solvers on four HELM benchmarks, selection is highly consistent across solver seeds, and agreement with the full ranking is governed by the threshold. Mild thresholds preserve the ranking while removing 64–82% of prompts, whereas aggressive pruning trades fidelity for compression. Size-matched random and stratified sampling preserve accuracy comparably but become less stable across seeds under aggressive pruning, which the authors present as MIS's advantage, alongside more uniform category coverage.

Critical strengths

[C1] Thorough and transparent evaluation. The study covers a large grid of embeddings, distances, thresholds and solvers on four benchmarks with 66 LLMs, and it compares MIS with random and stratified baselines of the same size. Both ranking agreement and absolute accuracy error are reported, with per-threshold tables for MIS and the baselines. The code and per-run results are released, so each comparison can be checked.

Critical weaknesses

[W1] MIS reproduces the full-benchmark ranking less well than random sampling of the same size The paper judges a compressed benchmark by its fidelity, i.e., whether it reproduces the full-benchmark ranking of the LLMs. On this criterion, the size-matched random baseline does better. In Table 16 it has a higher mean Spearman ρ than MIS in 23 of the 24 benchmark–threshold cells, the exception being GPQA at p90 (0.700 vs. 0.713). The gap can be large under aggressive pruning, for example 0.776 vs. 0.535 on IFEval and 0.880 vs. 0.748 on MMLU-Pro at p95. Random subsets also have lower MAE at every threshold (Table 19), and the size-matched baselines share more of the top-5 models with the full leaderboard at both p10 (Jaccard 0.75 vs. 0.693) and p95 (0.32 vs. 0.273).

The paper acknowledges that the baselines preserve the ranking better, and instead presents MIS's higher seed stability as its advantage (contribution (iii) and conclusion). Kendall's W, however, only measures how similar the rankings from different solver seeds, or different random draws, are to each other; it does not measure how close they are to the full-benchmark ranking. A subset can give the same ranking for every seed and still be systematically off. If stability matters because a practitioner uses a single subset, the relevant comparison is how far one random draw can fall from the full ranking, and the paper does not report this (see Q2).

[W2] The assumption that nearby prompts are redundant, on which the method rests, is not supported by the paper's own behavioral test. MIS ensures that no two retained prompts are closer than the threshold, on the assumption that prompts this close are redundant for evaluation. The behavioral test in Section 5 checks this by comparing each retained prompt with its nearest discarded neighbor. Their difficulties are correlated weakly on GPQA and MMLU-Pro (r ≈ 0.16–0.18) and somewhat more on Omni-MATH (r ≈ 0.29). Within these pairs, the closer ones are not more similar in behavior: the relation between embedding distance and behavioral similarity is essentially flat (|r| ≤ 0.10; Appendix K).

The authors read this as showing that the threshold, rather than the exact distance, identifies redundancy. That reading needs a comparison with pairs beyond the threshold, for example random prompt pairs from the same benchmark, and none is reported. Without it, the results do not show that retained and discarded neighbors are more alike than two arbitrary prompts. The statement in contribution (iii) that the test confirms the redundancy assumption is therefore not supported. The lower fidelity of MIS compared with random sampling (W1) is consistent with this.

Questions for authors

[Q1] Table 16 gives one MIS value per benchmark and threshold and does not show the recommended configuration separately (ReduMIS with qwen8b embeddings, standardized Euclidean distance and a p20 threshold). How do this configuration, and the best configuration at each threshold, compare with random subsets of exactly the same size in ρ, MAE and top-5 overlap?

[Q2] The paper argues that MIS is preferable because it gives almost the same ranking for every solver seed, while random subsets vary from draw to draw. In practice, however, a practitioner builds one subset and uses it for all models, so what matters is how close that one subset is to the full-benchmark ranking. Random subsets are closer on average (Table 16), but a single draw could be unlucky. Could you report how low ρ gets for individual random draws (for example, the worst of a larger number of draws than the current five), and compare it with the ρ of MIS? If even the worst random draws are closer to the full ranking than MIS, the stability argument does not favour MIS.

[Q3] The baselines are limited to random, stratified and uniform-stratified sampling. How does MIS compare at matched subset sizes with other selectors that use only embeddings, such as SemDeDup (discussed in Appendix A), k-center or k-medoids? The per-prompt results of all 66 LLMs are also available. How large is the gap to response-based methods such as IRT or anchor points when these are fitted on a subset of the models?

6 comments
AuthorsOpenReview ↗

Q1: MIS vs. random subsets of exactly the same size

Question: Table 16 gives one MIS value per benchmark and threshold and does not show the recommended configuration separately (ReduMIS with qwen8b embeddings, standardized Euclidean distance and a p20 threshold). How do this configuration, and the best configuration at each threshold, compare with random subsets of exactly the same size in ρ, MAE and top-5 overlap?

Thank you for this comment. Our recommendation is based on the full experimental results in the anonymized GitHub repository. The original baselines used subset sizes aggregated across configurations at each threshold. The revision compares random sampling at the exact sizes produced by the recommended configuration (Table 24 in the revised manuscript) and by the best configuration for each benchmark and threshold (Table 25).

MIS determines the subset size automatically. The exact solver finds an optimum, and the stochastic solvers typically reach the same objective value. We fix the random baseline’s size a priori using the MIS output, ensuring a matched-size comparison. Standalone random sampling requires an independently specified size or a sensitivity analysis across sizes.

The results show that the recommended configuration preserves the full-benchmark ranking almost as well as random subsets of exactly the same size (1,000 draws per size): at p20 it reaches ρ = 0.975–0.996 while removing 63–74% of the prompts, within 0.007 of the median random draw on all four benchmarks (within 0.012 across p10–p50). Under aggressive compression, it stays above the 5th percentile of random draws in all eight p90/p95 cells and preserves the top-5 models better than random sampling in 12 of 24 benchmark–threshold cells (5 of the 8 p90/p95 cells). Its MAE is higher than that of random subsets because the coverage redistribution also changes the difficulty mix of the subset (e.g., on Omni-MATH the selected problems have a lower mean difficulty rating than random subsets at p80–p95: 4.3–4.6 vs. 4.9). The best configuration in each cell, selected post hoc and therefore an optimistic estimate, is at or above the median random subset in 16 of 24 cells; in the other eight it is below by at most 0.012, and by less than 0.001 in three of them.

In the revised manuscript, this comparison is described in Section 5 (“Comparison to random sampling at the exact subset size produced by MIS configuration”, Table 2) and in Appendix G (Tables 21, 24 and 25).

AuthorsOpenReview ↗

Q2: How low ρ gets for individual random draws

Question: The paper argues that MIS is preferable because it gives almost the same ranking for every solver seed, while random subsets vary from draw to draw. In practice, however, a practitioner builds one subset and uses it for all models, so what matters is how close that one subset is to the full-benchmark ranking. Random subsets are closer on average (Table 16), but a single draw could be unlucky. Could you report how low ρ gets for individual random draws (for example, the worst of a larger number of draws than the current five), and compare it with the ρ of MIS? If even the worst random draws are closer to the full ranking than MIS, the stability argument does not favour MIS.

Thank you for suggesting this comparison. For each of the 2,558 MIS configurations, we sampled 1,000 subsets uniformly at random at the size selected by MIS. We computed Spearman’s ρ between the model ranking on each subset and the full-benchmark ranking, then compared the MIS correlation with the distribution of correlations from the matched random draws.

Across configurations, MIS exceeded the worst observed random draw in 93.2% of cases and the 5th percentile in 69.0%. It matched or exceeded the random median in 15.1% of cases, and its median position was the 15.6th percentile of the matched random distributions (Table 27 in the revised manuscript).

The recommended configuration illustrates how this comparison varies by benchmark and subset size (Table 26 in the revised manuscript). On GPQA with 10 instances, MIS achieved ρ = 0.685. The random median was 0.810, the 5th percentile was 0.623, and the worst observed draw yielded 0.191. Overall, 12% of the matched random draws scored below MIS. On MMLU-Pro with 410 instances, every observed random draw exceeded MIS, with a minimum ρ of 0.989 compared with 0.985 for MIS.

We have revised the manuscript to clarify when the stability of MIS matters in practice. At small and medium subset sizes, a single unlucky random draw can substantially distort the full-benchmark ranking, even when the median random draw achieves higher agreement than MIS. At large subset sizes, the matched random draws generally yielded high and tightly clustered correlations, so the practical benefit of avoiding a low-correlation draw was smaller. The magnitude of this effect varied by benchmark. In practice, random sampling requires the practitioner to specify the subset size before drawing a sample, while MIS determines the size from the structure of the data. We used the size returned by MIS as a fixed input to the random baseline to compare the two selection strategies at the same subset size.

In the revised manuscript, this analysis is described in Section 5 (“Comparison to random sampling at the exact subset size produced by MIS configuration”), in Appendix G (“Single configurations against 1,000 same-size random draws”, Tables 26 and 27) and in Section 6 (“Cost and when MIS pays off”).

AuthorsOpenReview ↗

Q3: Comparison with other embedding-only selectors and response-based methods

Question: The baselines are limited to random, stratified and uniform-stratified sampling. How does MIS compare at matched subset sizes with other selectors that use only embeddings, such as SemDeDup (discussed in Appendix A), k-center or k-medoids? The per-prompt results of all 66 LLMs are also available. How large is the gap to response-based methods such as IRT or anchor points when these are fitted on a subset of the models?

Thank you for suggesting these comparisons. In the revised manuscript, we compare maximal independent set (MIS) selection with clustering and response-based baselines. One clustering baseline determines the subset size from the cluster structure, while the other uses the exact subset size produced by MIS to compare the methods at the same level of compression. The response-based baselines, added as references, are anchor points and item response theory (IRT). In the revised manuscript, these comparisons are described in Section 5 (“Comparison to clustering baseline”, “Comparison to MIS-informed clustering baselines” and “Response-based baselines as references”) and in Appendix N (Tables 41–44). Below, we have added three sub comments to explain the three parts separately.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Rebuttal Summary for the Area Chair — New Experiments, Corrections, and Refined Claims

Dear Area Chair,

As the final summary of the rebuttal discussion, we would like to highlight the substantial new experiments and corrections addressing all three reviews. These are incorporated into the revised manuscript.

A central clarification is that all matched-size sampling and clustering baselines are MIS-informed: their target subset sizes are determined by MIS and supplied to the competing selectors. These experiments isolate selection quality at equal compression; they do not establish that those baselines independently determine an appropriate subset size. We additionally evaluated silhouette-selected clustering, which determines its own size but generally retains substantially more prompts.

Reviewer X26j — Fair comparisons and stronger baselines. We evaluated 1,000 exact-size random subsets for each of 2,558 MIS configurations, reporting ranking fidelity, score MAE, top-5 overlap, and the distribution of individual random-draw outcomes. At p20, the recommended configuration removes 63–74% of prompts while preserving rankings at ρ=0.975\rho = 0.975–0.9960.996, within 0.007 of the random median. We explicitly acknowledge that random sampling generally has higher average fidelity and restrict the stability argument accordingly.

We also implemented matched-size k-center, k-medoids, k-means, and SemDeDup, together with held-out-model anchor-point and IRT experiments. MIS, k-center, and SemDeDup achieve nearly identical mean fidelity at p20 (ρ=0.983\rho = 0.983, 0.9820.982, and 0.9830.983). These results establish that the small fidelity trade-off is shared by diversity-oriented selection, which redistributes benchmark coverage. All other baselines are used with MIS estimated size.

Reviewer fQnA — Interpretation, cost, and generalization. We expanded the behavioral analysis across 631 configurations and independent benchmark difficulty annotations. We report the modest correlations transparently and find no consistently superior embedding. We added measured preprocessing costs, a practical discussion of when benchmark reuse justifies them, and a sub-second GREEDY alternative with similar fidelity.

We also conducted leave-one-benchmark-out validation across 290 configurations. Configuration rankings transfer positively in every fold; the recommendation remains within the top 6% by held-out fidelity on three benchmarks and the top 13% on GPQA. This directly addresses whether the recommendation depends on evaluating the same four benchmarks.

Reviewer TiCK — Corrections, coverage, and controlled evidence. We traced the inconsistent baseline reports to different random streams and regenerated the affected tables, figure, and text from the authoritative draws. We corrected an omitted configuration group and quantified standard tie correction, which strengthens concordance without changing the main findings.

We added exact-size comparisons against random, stratified, and uniform-stratified sampling, distinguishing category counts from within-subset proportions. MIS produces more balanced category coverage than median random sampling in 17 of 18 benchmark–threshold cells, without category labels, while often increasing score MAE.

Crucially, we evaluated 469 configurations against controls matched on category and difficulty. These controls explain the observed behavioral similarity, so we narrowed the claims accordingly: MIS removes semantic redundancy reflecting category and difficulty structure; we no longer claim additional evaluative redundancy. We also removed the reference to an incomplete annotation study, which contributed no evidence to the paper.

The revised submission therefore provides substantially stronger comparisons, explicit corrections, and claims aligned with the new controlled evidence. We respectfully ask that these substantive responses be considered in the assessment.

Area_Chair_YMWSOpenReview ↗

Reminder to Participate in the Discussion

Dear Reviewers,

Thank you for your reviews. Please take a moment to read the authors’ response and the other reviews, and share your thoughts in the discussion. In particular, it would be helpful to clarify whether your main concerns have been addressed and discuss any points of disagreement.

Thank you for your time and contributions!

Best, Area Chair

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.