{"id":"bc066666-d7c2-466b-a5e3-2cacd666cf17","arxiv_id":"2506.09813","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Defines positional representation and positional proportionality for metric subset selection, with nearly tight worst-case bounds, greedy algorithms, and case studies on LLM and hospital benchmarks.","lead":"This paper formalizes what it means for a small set of evaluation metrics to represent a larger set, and proves how many metrics are needed in the worst case. The results give benchmark builders a principled way to construct lighter evaluation suites that provably preserve ranking information.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The framework assumes each metric ranks every alternative; real data in the Cal Hospital Compare and HELM case studies contain missing scores, so the empirical claims and practical guarantees rest on unstated missing-data handling.","rationale":"Agreement with reader: the reader's weakest assumption is exactly the complete-ranking requirement, and I agree this is the main soft spot. The core theorems are carefully proved and, within the stated model, the bounds are tight up to constants and logarithmic factors; Theorem 3.4's scoring-rule approximation is correct. The missing-data issue does not invalidate those theorems, but it is load-bearing for the paper's practical claims: the abstract promises 'real-world case studies on both LLM evaluation and hospital quality evaluation,' and the algorithms cannot be applied to the raw datasets without a ranking-completion rule. The HELM and Cal Hospital Compare sections do not specify such a rule, and Section 6 concedes this is future work. A secondary presentation defect is Table 1's 'NP-hard' entries: the hardness proofs (Theorems B.3 and B.4) target the generalized definitions, not the original positional properties, so the table overclaims unless the reductions can be specialized. I would keep the reader's CONDITIONAL verdict: the theory is solid, but the empirical sections should state and test a missing-data policy before the practical claims are accepted.","tokens_in":22717,"tokens_out":15565,"duration_ms":154921,"concrete_test":"Re-run the Cal Hospital Compare case study (Section L.1) under two explicit missing-data policies: (a) drop any hospital with a missing score on any of the 50 measures, and (b) impute missing scores as tied for last, then recompute Figures 1–2 and the IP/greedy subset sizes. If the selected subset sizes or the claimed improvement over the existing 12-measure subset differ materially between (a) and (b), the case study conclusions depend on the unstated missing-data handling.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Definitions 2.1 and 3.1 define C(N,r,a) as the number of metrics in N that rank alternative a in the top r; this quantity is undefined when some metrics do not rank all m alternatives. The theoretical results (Theorems 2.2–3.4) and the greedy/IP algorithms all take a complete preference profile σ_N as input. In the case studies, only BIG-bench explicitly filters to tasks evaluated on all alternatives (Section L.1); the HELM and Cal Hospital Compare descriptions do not state how missing model/hospital scores are converted into rankings. For Cal Hospital Compare, alternatives are hospitals with scores for at least 6 of the 12 currently selected measures, but the full set of 50 measures likely has many missing entries; no imputation or exclusion rule is reported. Section 6 explicitly defers missing-data handling to future work. Without a specified missing-data policy, the empirical results in Figures 1–2 are not reproducible, and the claim that a practitioner can always find a subset of the stated size with the representation guarantee does not yet extend to real datasets where complete rankings are unavailable.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper formalizes subset selection of evaluation metrics as a problem in computational social choice. Each metric is a voter that ranks all alternatives, and the goal is to choose a small subset K of metrics that preserves positional information about the full set N. Two properties are introduced: positional representation, which guarantees that any alternative ranked in the top r by at least g metrics of N is ranked in the top r by at least one metric of K (with the general form requiring floor(C(N,r,a)/g) metrics), and positional proportionality, which requires the fraction of metrics ranking an alternative in the top r to match between N and K up to additive error epsilon. The paper proves worst-case upper and lower bounds on |K| for both properties, gives a polynomial-time greedy algorithm for positional representation, shows a sampling-based upper bound for proportionality, proves that any epsilon-proportional subset approximates all positional scoring rules, and generalizes both properties to user-specified groups of metrics. It also reports three case studies (BIG-bench, HELM, Cal Hospital Compare) comparing the proposed algorithms with existing deployed subsets.","tokens_in":22944,"tokens_out":11607,"duration_ms":129594,"significance":"The theoretical core is valuable and largely self-contained: the bounds in Theorems 2.2, 2.3, 3.2, 3.3, and 3.4 are proved against the paper's own definitions with no fitted parameters, and the proofs in Appendices E, G, H, and I check out on inspection. The connection to scoring rules is a clean and useful consequence of positional proportionality, and the generalized definitions extend the framework to realistic constraints such as metric categories. The empirical sections demonstrate that the algorithms can produce smaller subsets than existing 'lite' benchmarks while satisfying representation guarantees, and the code and data links are a strength. However, the case studies rely on complete rankings, and the paper does not specify how missing data are handled for HELM and Cal Hospital Compare; this currently limits the reproducibility and practical reach of the empirical claims. The NP-hardness entry in Table 1 is also overstated relative to the actual proofs.","major_comments":[{"comment":"Definitions 2.1 and 3.1, and all theorems in Sections 2–4, assume a complete preference profile sigma_N in which each metric ranks every alternative. The empirical case studies do not always provide such a profile. For Cal Hospital Compare (Section L.1, Case Study 3), the alternatives are hospitals with scores for at least 6 of the 12 currently selected measures, while the full set contains 50 measures; the text does not state how missing scores for the other measures are converted into rankings, imputed, or excluded. The HELM case study (Section L.1, Case Study 2) similarly does not specify how missing model-scenario entries on the leaderboard are treated. Without an explicit missing-data policy, the results in Figures 1 and 2 are not reproducible, and the guarantee stated in the theorems does not automatically apply to these datasets. Section 6 explicitly defers missing-data handling to future work, but the Section 5 claims that the algorithms 'perform significantly better' and that a practitioner can always find a subset of the stated size require a working missing-data rule for these real instances. Please specify the exact handling for each dataset, or clearly restrict the empirical claims to the complete-ranking subset of the data.","section":"Section 5 and Appendix L.1"},{"comment":"Table 1 lists NP-hard in the Complexity column for both 'Positional Representation' and 'Positional Proportionality'. The NP-hardness proofs in Appendix K (Theorems B.3 and B.4) are for the generalized versions (Definitions 4.1 and 4.2) with arbitrary groups of metrics. Since the positional properties are a special case of the generalized definitions, NP-hardness of the generalized problem does not imply NP-hardness of the positional special case. As written, the table overstates the contribution: either provide a reduction from set cover or exact cover to the positional settings themselves, or amend Table 1 to indicate that NP-hardness holds for the generalized versions and not for the original positional rows.","section":"Table 1 and Appendix K"},{"comment":"The proof of Theorem 3.2 chooses exactly 1/epsilon^2 log(2m) metrics uniformly without replacement. When this quantity exceeds n, the sampling procedure is undefined. The theorem remains true because taking K = N gives |K| = n <= 1/epsilon^2 log(2m) in that regime, and K trivially satisfies epsilon-positional proportionality, but the proof as written does not cover this case. Please handle k > n explicitly, e.g., by sampling min(n, 1/epsilon^2 log(2m)) metrics or by splitting into cases.","section":"Theorem 3.2 and Appendix G"}],"minor_comments":[{"comment":"The plots overlay curves labeled 'Upper bound' and 'Lower bound' on the same axes as per-instance integer-programming results. The lower bound of Theorem 2.2 and Theorem 3.3 is a worst-case bound over all profiles, not a bound for the specific dataset plotted. The caption should state that these curves are worst-case existential bounds to avoid implying that the IP solutions are close to a per-instance information-theoretic limit.","section":"Section 5.1 and Figures 1–2"},{"comment":"For BIG-bench, the 'preferred score' field may contain ties, yet the model requires strict rankings sigma_i. If ties are broken arbitrarily, this should be stated explicitly, since different tie-breaking rules can change C(N,r,a) and hence the computed subsets.","section":"Appendix L.1, Case Study 1"},{"comment":"The text notes that CPLEX was run with a 10-minute time limit and that the limit was reached on BIG-bench. Section 5.1 refers to the 'optimal integer programming solution' in Figure 1; for completeness, the caption or text should note that the BIG-bench IP points may be suboptimal when the time limit was reached.","section":"Appendix L.2"},{"comment":"The notation 'r in [1:m]' and 'r in [m]' is used inconsistently across the paper; for a reader the distinction between cumulative top-r counts and exact ranks is clear, but the notation should be unified.","section":"Definitions 2.1 and 3.1"}],"recommendation":"major_revision","confidential_remarks":"The core theoretical results are sound and the paper is likely to be a useful contribution once the missing-data handling and the NP-hardness table entry are corrected. The missing-data issue is substantive because two of the three case studies are presented as practical evidence for the framework, and the current text does not specify how the ranked profile was constructed from real-world data with missing entries. The NP-hardness overclaim in Table 1 is a correctness issue in the presentation, though the underlying general-version proofs are fine. I would be happy to see a revised version that resolves these two points."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. The core theory is solid and genuinely useful: the paper defines two clean notions of representative subset for metric suites, proves tight worst-case bounds (Theta((1/epsilon^2) log m) for positional proportionality), and shows any subset satisfying that property approximates every scoring rule within epsilon. The greedy algorithm for positional representation is correct and runs in polynomial time. This is a real contribution to benchmark selection.\n\nThe soft spots are contained. First, Table 1 lists NP-hard for positional representation and positional proportionality, but the NP-hardness proofs are for the generalized versions in Section 4 (Definitions 4.1 and 4.2). The text is accurate; the table overclaims. Second, the empirical case studies do not say how missing scores are converted to rankings, and Section 6 explicitly defers missing data to future work. The definitions need a complete ranking profile, so the HELM and Cal Hospital Compare figures are not reproducible without a stated imputation or exclusion rule. BIG-bench filters to tasks evaluated on all alternatives; the others do not. That is a real gap in the empirical story, though it does not touch the main theorems.\n\nI checked the key proofs: the coloring argument for the greedy algorithm works, the Hoeffding-without-replacement upper bound is standard, and the inverse-Hoeffding lower bound checks out. The scoring-rule approximation is a neat telescoping sum. No fitted parameters, no circularity; the bounds are worst-case and user-driven.\n\nThis paper deserves a serious referee. Anyone building a lite benchmark or thinking about committee selection with ranked data gets a useful toolkit. The empirical sections are illustrative, not definitive. I would accept after minor revision: fix Table 1, add a clear missing-data policy to the case studies (or restrict the datasets to complete rankings), and I'd be satisfied.","headline":"Sound theory for lite-benchmark selection, with a reproducible-data gap and a misleading table; worth refereeing.","tokens_in":23418,"tokens_out":4637,"would_cite":true,"duration_ms":47950,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that any set of metric rankings over m alternatives contains a subset of size Θ((1/ε²) log m) satisfying ε-positional proportionality, and matching lower bounds show this is worst-case optimal.","keywords":["metric subset selection","positional representation","positional proportionality","lite benchmarks","LLM evaluation","social choice theory","scoring rules","NP-hardness"],"falsifier":"On a small adversarial instance built from the lower-bound construction, solve the exact integer program for the minimum subset size and check whether any $K$ below the claimed lower bound satisfies the relevant property; finding one would falsify the corresponding theorem. For proportionality, generate the random paired-swap profile used in the proof and test whether any $K$ of size below $(1/(288\\epsilon^2))\\log m$ passes the $\\epsilon$-difference check for all alternatives and cutoffs; existence of such a $K$ would contradict Theorem 3.3.","tokens_in":22553,"feed_emoji":"⚖️","tokens_out":12907,"duration_ms":135461,"temperature":0.7,"pith_summary":"This paper gives a formal answer to a practical question: when a suite of evaluation metrics is too expensive to run in full, how many metrics must a \"lite\" subset contain to stand in for the whole? Treating each metric as a ranking over alternatives, the authors define positional representation (every alternative ranked highly by a large-enough block of metrics must appear proportionally often in the subset) and positional proportionality (for every alternative and every position cutoff, the subset's share of metrics ranking it above that cutoff differs from the full set's share by at most $\\epsilon$). They prove worst-case bounds: positional proportionality is achievable with $\\Theta((1/\\epsilon^2)\\log m)$ metrics and sometimes requires that many, while a polynomial-time greedy algorithm always finds a positional-representation subset of size $O((n/g)\\log m)$. They also show that any proportionally representative subset approximates the outcome of any scoring rule on the full metric set to error $\\epsilon$, and that the generalized versions of both properties lead to NP-hard selection problems. If correct, benchmark designers can choose a subset with a provable representation guarantee rather than relying on hand-curated lite suites.","feed_headline":"Proportional benchmark subsets need only O(ε^{-2} log m) metrics","feed_subtitle":"Matching worst-case bounds give benchmark designers a provable guarantee for lite evaluation suites.","key_machinery":"The carrying object is the count function $C(N,r,a)=\\#\\{i\\in N:\\sigma_i(a)\\le r\\}$, the number of full-set metrics that put alternative $a$ in the top $r$ positions; every guarantee is a bound on how far $\\frac{C(K,r,a)}{|K|}$ is from $\\frac{C(N,r,a)}{|N|}$. The upper bounds ride on concentration of sampling without replacement, the lower bound on an inverse Hoeffding estimate for independent paired comparisons, and the representation algorithm on a greedy covering argument in which each \"color\" marks $g$ metrics that rank an alternative at a common position, so selecting metrics that cover the most uncovered colors yields the $O((n/g)\\log m)$ bound. For scoring rules the identity $f_s(a,\\sigma_N)=\\sum_{r=1}^m C(N,r,a)(s_r-s_{r+1})$ converts cumulative-count approximation into score approximation.","core_discovery":"The central discovery is that small, provably representative benchmark subsets exist and are characterized by two social-choice-style properties. For $\\epsilon$-positional proportionality, a subset $K$ of size at most $(1/\\epsilon^2)\\log(2m)$ guarantees that for every alternative $a$ and every cutoff $r$, $\\left|\\frac{C(N,r,a)}{|N|}-\\frac{C(K,r,a)}{|K|}\\right|\\le\\epsilon$; a matching lower bound shows some profiles force any such $K$ to have size $\\Omega((1/\\epsilon^2)\\log m)$. For positional representation with group size $g$, a greedy algorithm returns $K$ of size $O((n/g)\\log m)$ satisfying $C(K,r,a)\\ge\\lfloor C(N,r,a)/g\\rfloor$, and a lower bound shows this is optimal up to a logarithmic factor. Because $\\epsilon$-positional proportionality preserves the frequency with which each alternative appears in each position up to a small additive error, any scoring rule evaluated on the subset approximates its value on the full suite within $\\epsilon$. The same guarantees extend to externally specified groups of metrics, and finding the smallest subset satisfying either generalized property is NP-hard.","pith_inferences":["Editorial extension: The worst-case lower-bound profiles use only pairwise swaps of adjacent alternatives, so real benchmark profiles with correlated rankings may admit far smaller representative subsets; a numerical comparison on random and deployed profiles would quantify how far practice is from worst case.","Editorial extension: Because the framework treats the full metric set as fixed and unbiased, a skewed or redundant full suite will pass its skew into the subset; weighting metrics by cost or diversity is a natural extension not tested here.","Editorial extension: Missing evaluations, which the paper explicitly defers, could be absorbed into the model by treating absent alternatives as tied for last, making $C(N,r,a)$ defined everywhere at the price of a conservative position bias.","Editorial extension: The generalized group setting reduces to set cover when every group must be covered once, so approximation algorithms for set cover provide a benchmark for practical near-optimal selection."],"forward_implications":["A lite subset satisfying $\\epsilon$-positional proportionality can replace the full suite in any scoring-rule computation: every alternative's aggregate score stays within $\\epsilon$ of its full-suite score.","The greedy algorithm constructs a positional-representation subset of size $O((n/g)\\log m)$ in polynomial time, so no exact solver is needed to obtain a guaranteed subset.","The $\\Omega((1/\\epsilon^2)\\log m)$ lower bound means no worst-case method can guarantee $\\epsilon$-positional proportionality with asymptotically fewer metrics, independent of the profile.","Generalized representation and proportionality over arbitrary groups of metrics inherit the same logarithmic upper bounds, but exact minimization is NP-hard, so practitioners would need integer programming or approximation.","In the three real-world case studies, the algorithms find subsets that are smaller than the deployed hand-curated lite suites while guaranteeing representation at a finer granularity, and augmenting an existing curated subset is also effective."],"supporting_citations":[{"why":"Supplies the sampling-without-replacement Hoeffding bound used in the proof of the positional-proportionality upper bound.","marker":"Bardenet and Maillard (2015)"},{"why":"Supplies the inverse Hoeffding proposition used in the lower-bound construction for positional proportionality.","marker":"Matoušek and Vondrák (2001)"},{"why":"Defines scoring rules and the score decomposition used to show that proportional subsets approximate full-suite scoring-rule values.","marker":"Young (1975)"},{"why":"Provides the full metric set and existing lite subset for the first LLM evaluation case study.","marker":"Srivastava et al., 2022"},{"why":"Provides the scenario metrics and lite comparison subset for the second LLM evaluation case study.","marker":"Liang et al., 2022"},{"why":"Provides the hospital-quality measures and the existing twelve-measure subset for the hospital case study.","marker":"Cal Hospital Compare (2025)"},{"why":"Provides the reduction template used to prove NP-hardness of finding the smallest generalized proportional subset.","marker":"Natarajan (1995)"}],"fun_headline_variants":["Social choice math pins down minimal representative metric subset sizes","For lite benchmarks, social choice proves how few metrics suffice","Matching bounds show how many metrics a lite benchmark really needs","Provable metric subsets: social choice gives tight size bounds","Representative benchmark metrics: social choice fixes the size"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The framework requires that every metric rank every alternative; if a metric does not evaluate some alternative, the count $C(N,r,a)$ that all definitions and theorems rely on has no defined value.","fun_headline_variants_meta":{"raw":{"variants":["Social choice math pins down minimal representative metric subset sizes","For lite benchmarks, social choice proves how few metrics suffice","Matching bounds show how many metrics a lite benchmark really needs","Provable metric subsets: social choice gives tight size bounds","Representative benchmark metrics: social choice fixes the size"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001494,"raw_usage":{"total_tokens":6006,"prompt_tokens":966,"completion_tokens":5040,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":582,"completion_tokens_details":{"reasoning_tokens":4958}},"tokens_in":582,"tokens_out":5040,"duration_ms":42544,"temperature":1.0,"reasoning_tokens":4958,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:41:38.981443+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a small adversarial instance built from the lower-bound construction, solve the exact integer program for the minimum subset size and check whether any $K$ below the claimed lower bound satisfies the relevant property; finding one would falsify the corresponding theorem. For proportionality, generate the random paired-swap profile used in the proof and test whether any $K$ of size below $(1/(288\\epsilon^2))\\log m$ passes the $\\epsilon$-difference check for all alternatives and cutoffs; existence of such a $K$ would contradict Theorem 3.3.","supporting_citations":[{"cited_title":"ex- isting subset","cited_arxiv_id":null,"evidence_quote":"Provides the hospital-quality measures and the existing twelve-measure subset for the hospital case study."}],"review_version":1}