Pith. sign in

REVIEW 3 major objections 4 minor 20 references

Metritocracy: Representative Metrics for Lite Benchmarks

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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.

desk verdict Sound theory for lite-benchmark selection, with a reproducible-data gap and a misleading table; worth refereeing. read the letter →

arxiv 2506.09813 v2 pith:VLVT4AIE submitted 2025-06-11 cs.LG cs.GT

Ariel Procaccia , Benjamin Schiffer , Serena Wang , Shirley Zhang This is my paper · ORCID
classification cs.LGcs.GT
keywords metricsubsetselectionpositionalrepresentationproportionalitylitebenchmarksLLMevaluationsocialchoicetheoryscoringrulesNP-hardness
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Section 5 and Appendix L.1] 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.
  2. [Table 1 and Appendix K] 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.
  3. [Theorem 3.2 and Appendix G] 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.
minor comments (4)
  1. [Section 5.1 and Figures 1–2] 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.
  2. [Appendix L.1, Case Study 1] 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.
  3. [Appendix L.2] 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.
  4. [Definitions 2.1 and 3.1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the representation and proportionality bounds are proven from formal definitions, and no fitted parameter or self-citation carries the central claims.

full rationale

The paper's central results are self-contained mathematical derivations. Definitions 2.1 and 3.1 introduce positional representation and positional proportionality; Theorems 2.2-3.4 are proved directly from these definitions and from standard probabilistic and greedy-set-cover arguments (Hoeffding's inequality, union bounds, set-multicover recurrences). The bounds describe worst-case subset sizes, not fitted quantities: group size g and tolerance epsilon are user-supplied parameters, and no parameter is tuned to the data to force the stated theorem. The greedy algorithm (Algorithm 1) and the integer programs (Appendix A) are evaluated against external public datasets (BIG-bench, HELM, CMS Hospital Compare), and the comparisons with existing deployed subsets are empirical demonstrations, not reverse-engineered predictions. There are no load-bearing self-citations: the acknowledgments mention a discussion with colleagues, but the cited references are standard external works in social choice, concentration inequalities, and set cover. The paper explicitly flags missing-data handling as an open limitation (Section 6) and does not claim the theory covers incomplete rankings; this is a scope limitation, not a circular derivation. Accordingly, no circular step can be exhibited by quotation, and the appropriate score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central theoretical results rely only on standard combinatorics and probability. No free parameters are fitted to data; group size g and tolerance epsilon are inputs. No new physical or empirical entities are postulated.

assumptions (4)
  • domain assumption Each metric produces a total order over all alternatives.
    Definitions 2.1 and 3.1 use C(N,r,a), which requires complete rankings. Missing data is explicitly deferred to future work in Section 6.
  • domain assumption The full metric set N is the ground truth to be represented; no correction is made for bias in N.
    Section 6 states that bias in the overall set is inherited by the subset. The usefulness of the framework is conditional on N itself being the desired target.
  • standard math Standard concentration inequalities (Hoeffding without replacement, Matousek-Vondrak proposition) hold.
    Used in Appendices G and H for the sampling upper bound and the lower bound construction.
  • standard math Standard computational hardness assumptions (P != NP) hold for the NP-hardness reductions.
    Appendix K reduces from set cover and exact cover by 3-sets.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Metritocracy: Representative Metrics for Lite Benchmarks." pith.science (2026). https://pith.science/paper/VLVT4AIE

@misc{pith2026250609813,
  author       = {Pith},
  title        = {Pith review of: Metritocracy: Representative Metrics for Lite Benchmarks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VLVT4AIE}},
  note         = {Machine review of arXiv:2506.09813}
}
read the original abstract

A common problem in LLM evaluation is how to choose a subset of metrics from a full suite of possible metrics. Subset selection is usually done for efficiency or interpretability reasons, and the goal is often to select a ``representative'' subset of metrics. However, ``representative'' is rarely clearly defined. In this work, we use ideas from social choice theory to formalize two notions of representation for the selection of a subset of evaluation metrics. We first introduce positional representation, which guarantees every alternative is sufficiently represented at every position cutoff. We then introduce positional proportionality, which guarantees no alternative is proportionally over- or under-represented by more than a small error at any position. We prove upper and lower bounds on the smallest number of metrics needed to guarantee either of these properties in the worst case. We also study a generalized form of each property that allows for additional input on groups of metrics that must be represented. Finally, we tie theory to practice through real-world case studies on both LLM evaluation and hospital quality evaluation.

Figures

Figures reproduced from arXiv: 2506.09813 by the authors.

Figure 1
Figure 1. Results of running greedy and integer programming algorithms to achieve posi [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
Figure 2
Figure 2. Results of running integer programming algorithms to achieve positional propor [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Table of Patient Safety Honor Roll Measures published by Cal Hospital Com [PITH_FULL_IMAGE:figures/full_fig_p035_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 12 canonical work pages

  1. [1]

    Suppose we have a setKsuch that|K| ≤(α−1)gandKsatisfies positional representation for group sizeg

    Proof by contradiction. Suppose we have a setKsuch that|K| ≤(α−1)gandKsatisfies positional representation for group sizeg. Then there must be a set ofgmetrics not included inK. Denote this set ofgmetrics asG. Because we used every possible subset ofNfor the per- mutations ofa r, br in the first n g positions, there is some position ˆrand some alternative ...

    work page 2015

  2. [2]

    coalition

    terminates in polynomial time and returns a subsetKwith|K| ≤ n g log (|G|)which satisfies generalized representation for group sizeg. 16 proof.The proof of this result follows as in the proof of Theorem 2.3, except that instead of Q0 ≤mαwe have thatQ 0 ≤ |G|α. The rest of the recursion proof follows exactly the same to give the desired bound. Theorem B.2....

    work page 2017

  3. [3]

    ex- isting subset

    Figure 3: Table of Patient Safety Honor Roll Measures published by Cal Hospital Com- pare (https://calhospitalcompare.org/wp-content/uploads/2025/04/FactSheet_ Patient-Safety-Honor-Roll-List_Cal-Hospital-Compare_2025-1.pdf). As our “ex- isting subset”, we consider the set ofk= 12 measures selected from CMS Hospital Compare. Dataset:Data was downloaded as ...

    work page 2025

  4. [5]

    exact cover by 3 sets

    Algorithm 5ConstructingK ′ 1:Input:K 2:K ′ ←K∩[κ] 3:fori∈K\[κ]do 4:u←usuch thati∈G u 5:i ′ ←any element of [κ] such thatu∈C i′ 6:ifi ′ ̸∈K ′ then 7:K ′ ←K ′ ∪ {i′} 8:end if 9:end for 10:ReturnK ′ Note that at the end of this algorithm,|K ′| ≤ |K|because we never add ani′ toK ′ unless there is a correspondingi∈K\[κ] that is not inK ′. Furthermore,K ′ still...

    work page 1995

  5. [6]

    Big-G”, “Big-G sparse

    Algorithm 6ConstructingG 1:Input:S,C={C i}i∈[κ] 2:G s ← {i:s∈C i}for alls∈S 3:i←κ 4:while∃s∈S:|G s|<2κdo 5:i←i+ 1 6:ifthere is exactly ones∈Ssuch that|G s|<2κthen 7:s←s∈Ssuch that|G s|<2κ 8:AdditoG s 9:else 10:s 1, s2 ←two distinct values ofssuch that|G s|<2κ 11:AdditoG s1 12:AdditoG s2 13:end if 14:end while 15:ReturnG={G s}s∈S Note that the counterineve...

    work page 2022

  6. [10]

    Vote'n'Rank: Revision of Benchmarking with Social Choice Theory

    Mark Rofin, Vladislav Mikhailov, Mikhail Florinskiy, Andrey Kravchenko, Elena Tutubalina, Tatiana Shavrina, Daniel Karabekyan, and Ekaterina Artemova. Vote’n’rank: Revision of benchmarking with social choice theory.arXiv preprint arXiv:2210.05769,

    work page Pith review arXiv

  7. [15]

    Finally, we can conclude that there mustexist some rankingσ N such that noKwith size|K| ≤ 1 288ϵ2 log(m) satisfiesϵ-positional proportionality

    Therefore, we have shown that with positive probability, there will be noKwith size|K| ≤ 1 288ϵ2 log(m) that satisfiesϵ-positional proportionality. Finally, we can conclude that there mustexist some rankingσ N such that noKwith size|K| ≤ 1 288ϵ2 log(m) satisfiesϵ-positional proportionality. In the equations above, we used the following inverse of Hoeffdin...

    work page 2001

  8. [18]

    representative

    The list of these tasks is included in the code in the Supplemenary Materials and also available athttps://github.com/google/ BIG-bench/blob/main/bigbench/benchmark_tasks/keywords_to_tasks.md#big-bench-lite. Dataset:Data was accessed using the Big-bench API available athttps://github.com/ google/BIG-bench. Code for processing this data is included with th...

    work page 2022

Show all 20 references
  1. [19]

    Core scenarios

    Full set:The full set of tasks we consider consists of the accuracy metrics forn= 34 scenarios, for which data was posted on the HELM Classic leaderboard. This includes both “Core scenarios” and “Targeted evaluations.” A full list of these scenarios is included with the code i...

    2025

  2. [1973]

    Full proportional justified representa- tion.arXiv preprint arXiv:2501.12015,

    Yusuf Hakan Kalayci, Jiasen Liu, and David Kempe. Full proportional justified representa- tion.arXiv preprint arXiv:2501.12015,

    arXiv

  3. [1975]

    Inherent trade-offs between diversity and stability in multi-task benchmark.arXiv preprint arXiv:2405.01719,

    Guanhua Zhang and Moritz Hardt. Inherent trade-offs between diversity and stability in multi-task benchmark.arXiv preprint arXiv:2405.01719,

    arXiv

  4. [1979]

    What are the best systems? new perspectives on nlp benchmarking.Advances in Neural Information Processing Systems, 35:26915–26932, 2022a

    13 Pierre Colombo, Nathan Noiry, Ekhine Irurozki, and St´ ephan Cl´ emen¸ con. What are the best systems? new perspectives on nlp benchmarking.Advances in Neural Information Processing Systems, 35:26915–26932, 2022a. Pierre Jean A Colombo, Chlo´ e Clavel, and Pablo Piantanida....

    arXiv

  5. [1995]

    Efficient benchmarking of lan- guage models.arXiv preprint arXiv:2308.11696,

    14 Yotam Perlitz, Elron Bandel, Ariel Gera, Ofir Arviv, Liat Ein-Dor, Eyal Shnarch, Noam Slonim, Michal Shmueli-Scheuer, and Leshem Choshen. Efficient benchmarking of lan- guage models.arXiv preprint arXiv:2308.11696,

    arXiv

  6. [2001]

    Proportionally fair clustering revisited

    Evi Micha and Nisarg Shah. Proportionally fair clustering revisited. In47th Interna- tional Colloquium on Automata, Languages, and Programming (ICALP 2020), pages 85–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik,

    2020

  7. [2009]

    Swe-bench: Can language models resolve real-world github issues? arXiv preprint arXiv:2310.06770,

    Carlos E Jimenez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik Narasimhan. Swe-bench: Can language models resolve real-world github issues? arXiv preprint arXiv:2310.06770,

    arXiv

  8. [2015]

    Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.arXiv preprint arXiv:2206.04615,

    Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adri` a Garriga-Alonso, et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.arXiv preprint ...

    arXiv

  9. [2017]

    tinybenchmarks: evaluating llms with fewer examples.arXiv preprint arXiv:2402.14992,

    Felipe Maia Polo, Lucas Weber, Leshem Choshen, Yuekai Sun, Gongjun Xu, and Mikhail Yurochkin. tinybenchmarks: evaluating llms with fewer examples.arXiv preprint arXiv:2402.14992,

    arXiv

  10. [2023]

    Exact algorithms for set multicover and multiset multicover problems

    Qiang-Sheng Hua, Dongxiao Yu, Francis CM Lau, and Yuexuan Wang. Exact algorithms for set multicover and multiset multicover problems. InAlgorithms and Computation: 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18,

    2009

  11. [2024]

    Holistic evaluation of language models.arXiv preprint arXiv:2211.09110,

    Percy Liang, Rishi Bommasani, Tony Lee, Dimitris Tsipras, Dilara Soylu, Michihiro Ya- sunaga, Yian Zhang, Deepak Narayanan, Yuhuai Wu, Ananya Kumar, et al. Holistic evaluation of language models.arXiv preprint arXiv:2211.09110,

    arXiv

  12. [2025]

    Active evaluation acquisition for efficient llm benchmarking.arXiv preprint arXiv:2410.05952,

    Yang Li, Jie Ma, Miguel Ballesteros, Yassine Benajiba, and Graham Horwood. Active evaluation acquisition for efficient llm benchmarking.arXiv preprint arXiv:2410.05952,

    arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.