Metritocracy: Representative Metrics for Lite Benchmarks
Authors: Ariel D. Procaccia
Benjamin Schiffer
Serena Lutong Wang
Shirley Zhang
Venue: NeurIPS 2025 poster ()
Keywords: Evaluation
benchmarks
social choice
Primary area: social_and_economic_aspects_of_machine_learning

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.

Metritocracy:
Representative Metrics for Lite Benchmarks
Ariel D. Procaccia
Benjamin Schiffer
Serena Wang
Shirley Zhang
Harvard University
Harvard University
Harvard University
Harvard University
Abstract
A common problem in LLM evaluation is how to choose subset of metrics from full suite of possible metrics. Subset selection usually done for efficiency or interpretability reasons, and the goal is often to select "representative" subset of metrics. However, "representative" rarely clearly defined. In this work, we use ideas from social choice theory to formalize two notions of representation for the selection a subset of evaluation metrics. sentation, which guarantees every alternative is sufficiently represented at every position cutoff. We then introduce positional proportionality. which guarantees alternative is proportionally over- under-representeed by more than small eиror at any position. We prove upper and lower bounds on the smallest number metrics needed to guarantee either of these propertics 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, tie theory to practice through real-world case studies on both LLM evaluation and hospital quality evaluation.
first introduce positional repre-
Introduction
The last few years have seen an explosion in metrics to evaluate large language models (LLMss.. While this has improved our ability to understand the capabilities of LLMs, is also increasingly computationally expensive to evaluate all of these measures. This challenge is directly felt by platforms like BIG-bench [Srivastava et al., 2022] and HELM [Liang al., 2022] that aggregate numerous metrics to provide as complete a picture as possible of LLM performance.
A common approach that evaluation platforms take to mitigate these growing computational difficul- ties is to create a "lite" version of the full evaluation suite, which consists of a subset the original measures. For example, BIG-bench Lite contains subset of 24 JSON metrics from the full collection of over 200 metrics, which is "designed to provide a canonical measure of model performance, while being far cheaper to evaluate than the full set." HELM Lite also contains subset of scenarios from HELM Classic (in addition to some others), constructed to have a lighter computational overhead.
The problem of selecting subset of evaluation metrics is actually quite general beyond LLM evaluation, and is also common in public policy and business operations. For example, Cal Hospital Compare awards Patient Safety Honor Roll status hospitals using subset of 12 measures from full set of hundreds of hospital quality measures collected by the Centers for Medicare and Medicaid Services [Cal Hospital Compare, 2025]. This subset is carefully hand-selected, but Cal Hospital Compare still acknowledges that "measurement of patient safety is complex and there no single validated method for measuring the overall safety of care provided in given health setting." Beyond computational considerations, an additional reason for selecting a subset of metrics is understandability for stakcholders.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Across these settings, a recurring theme is that practitioners want to select subset of metrics that is in some sense "representative" of the underlying full set of metrics." However, there is no formal notion of representation that is common across these contexts. To provide the tools to more clearly discuss and achieve representation the selection of subset of evaluation metries, we introduce formal definitions of representation inspired by notions in computational social choice. Our theoretical framework provides the basis for discussing tradcoffss between representation and computational cost or understandability, and allows practitioners to more clearly reason about the consequences of subset selection on downstream decision-making. Our framework also opens the door to algorithmic support for metric selection, which characterize theoretically and empirically.
1.1 Our Contributions
We study the problem of selecting a representative subset from a set of evaluation metrics that each rank m alternatives." 2 We introduce two desirable properties for the subset and provide lower and upper bounds on the number of metrics needed to satisfy each of the two properties.
We start by defining positional representation, which prevents rnder-representatioon Positional representation guarantees that every alternative sufficiently represented every rank. This property is parameterized by group size g. which indicates the granularity of representation. We show upper and lower bounds on the number of metrics necessary to satisfy positional representation in the worst case that are tight up to logarithmic factor. We also provide polynomial-time algorithm which always finds a subset satisfying positional representation with size at most a log(m).
We next introduce positional proportionality, which guarantees that no alternative is under- or over- represented any position in the chosen subset by more than additive factor of e. We give tight (up to constant factors) upper and lower bounds on the number of metrics needed to satisfy positional proportionality in the worst case. We also show that any subset of metrics satisfying positional proportionality can approximate any social choice scoring rule on the original set of metrics.
Finally, generalize both properties to enable preserving information about the original set of metrics which may be external to the rank information. We show that our upper and lower bound extend the general versions of our properties, and prove that finding the smallest set satisfying either general property is NP-hard. Our theoretical results are summarized in Table 1.
Properties
Parameter
Upper Bound
Lower Bound
Complexity
Ω log(m) Tog 3 log(m))
Positional Representation
Group size 0 n log(m)
NP-hard
Positional Proportionality
Accuracy e 0 log(m)) Ω (+ log(m))
NP-hard
Table 1: Summary of theoretical results.
To connect these theoretical results to the above motivating practical examples, evaluated algo- rithms to achieve positional representation and positional proportionality in three case studies with real data: two on LLM evaluation and one on hospital quality evaluation. We show that the outputs of our methods compare favorably with the existing subsets currently deployed in the real world for each of these settings.
1.2 Related Work
There has been a surge of recent work studying benchmarks as voters from the social choice perspec- tive. These works differ from ours in that none study subset selection of metrics. Many of these works study how metrics should be aggregated, particularly to improve robustness [Colombo et al., 2022b,a, Peyrard et al., 2017, Mishra and Arunkumar, 2021, Himmi et al., 2023]. Colombo et al. [2022a] propose using Borda count to aggregate benchmarks as an approximation of the Kemeny Rule and Rofin al. [2022] propose VOTE'N RANK,, which consists of several scoring rules based social choice theory for benchmark aggregation. In a different direction, Zhang and Hardt [2024] give a
Not all "Lite" benchmarks are trying to be representative - SWE-bench Lite [Jimenez et al., 2023] also tries to include casier metrics. In this work we focus on settings where the goal is to be representative. A metric refers to anything that gives a ranking over alternatiess (and not necessarily loss function).

---

form of Arrow's s Impossibility result for the benchmark setting and highlight an inherent tradeoffss between sensitivity and diversity.
In social choice, our properties most closely related to Justified Representation (JR) introduced by Aziz et al. [2017] in the committee selection setting. JR guarantees representation for sufficiently- large "coalitions" of voters that approve the same candidate; it is similar to our notion of positional representation, which guarantees representation for "coalitions" of benchmarks that all rank alternative in the top r. However, our setting has no voters and no notion of approval, which makes direct comparison impossible. See Appendix C for more discussion of the relationship to JR. Also in the approval setting, Skowron and Faliszewski [2015] study the relationship between set cover and proportional representation with approval ballots, similar to our NP-hardness results in Section 4.
Other methods have also been proposed to speed up LLM evaluation through selection of individual prompts from all possible evaluation metrics [Perlitz et al., 2023, Polo et al., 2024, Li et al., 2024]. Our work differs in that we restrict to selecting a subset of full metrics, and not the more granular selection of prompts. This captures more general public policy settings like hospital quality evaluation, where only full metrics are available. Note, however, that the two approaches are complementary and can be used in tandem.
1.3 Model
Let there be a set N = [n]] of metrics and a set A = [m] of alternatives. Each metric i has a ranking o, over alternatives. Let dir be the alternative ranked in position in metric i's ranking, and let o (a) be the rank of alternative in metric i's ranking. The set of all metric rankings forms a preference profile o n o.).. For K S N. define σk (az i K}. We study the following:
How should select small subset of metrics K C N such that K preserves some information from the metrics in N?
We say that metric ranks alternative a at least at position r if (a) is r or better (i.e. ai(a) S r). Similarly, we say that metric ranks alternative above position if (a(a) is strictly better than (i.e. (a) < r). Define C(N, r, a) as the number of metrics in N that rank alternative a in the top r. Likewise, for K S N. C(K, r, a) is the number of metrics in K that rank alternative a in the top r.
2 Positional Representation
Consider some alternative a E A. If a is ranked highly by many metrics in N, then we want to be ranked highly in many metrics in the subset K as otherwiss,,,, would not be getting the representation it deserves in K. Intuitively, it would be undesirable if is ranked in the top 10 positions by the majority of the metrics in N, but does not appear in the top 10 positions for any metric in K. Similarly, it would be undesirable if b is ranked in the top 50 by 90% of metrics in N, but & ranked in the top 50 by less than half of the metrics in K. We therefore begin by introducing positional representation, which guarantees that the subset K gives every alternative representation at every cutoff position. More specifically, positional representation guarantees that for every position cutoff, if is ranked above the cutoff in a sufficiently large number of the original metrics, then that alternative is also ranked above the cutoff in a (close to) proportional number of metrics in K.
A sufficient
Definition 1. A subset K satisfies positional representation for group size g if every E [1 : m], any alternative that is ranked in the first r positions at least é g metries is ranked in the first r positions in at least E metrics in K. Equivalently, for all r E [1 m] and all a E A.
C(N,r,a)
C(Kr,,)) N
(I)
g
Positional representation is parameterized by group size g, which will capture the tradeoff between the granularity of representation and the size of K needed to satisfy positional representation. As gets larger, the minimum necessary |K| decreases, but for each alternative a it takes more high-ranked votes to deserve representation. g = n, for instance, then positional representation guarantees only that every alternative is ranked by some metric in K at least as high as its lowest ranking. By the pigeonhole principle, it will always be possible to satisfy this specific guarantee with |K] = At the other extreme, if 1, then we must have that K N in order to satisfy positional representation.
3

---

As concrete example, suppose that we have n = 100 metrics and g = 10. If alternative a is ranked first by exactly 23 metrics in N, then Definition 1 requires that a ranked first by at least two metries in K. Similarly, if alternative is ranked in one of the top two places by exactly 76 metrics in N, then Definition also requires that alternative a is ranked in the top two by at least metrics K.
2.1 Lower Bound
In this section, we first provide lower bound on the size of K needed satisfy positional represen- tation. We then give an algorithm that returns a solution satisfying positional representation where [K] is at most a logarithmic factor larger than the lower bound.
Observe that any K satisfying positional representation for group size must have size |K] > I. This is because every alternative a must be ranked in the top m by all n metrics, and therefore Definition I requires that a is ranked in the top m by at least _ metrics in K. Naturally, we might hope that for any g and N, we can always find K S such that K satisfies positional representation for group size g and K 2
Unfortunately, we show this is impossible in the following example.
g
b1
b2
bg
b1
W
W
y/
2
y/
2
3/
2
1 11
2
Table 2: Example where positional representation for group size g = 2 is impossible with |K] = n Each metric in {hi, by, b3, bu) has preference ordering among the alternatives (u, U, W, corresponding to that metric's column. Each color needs to be represented in K.
9
In this example. set K satisfies positional representation for group size g 2 if and only if every color appears in K. However, there is no such subset K C {br, b22 b3, b4) where K S 2 " and therefore any K satisfying positional representation for g = 2 must have [] > 3. More generally, we show the following worst-case lower bound on the number of metrics needed to guarantee positional representation.
Theorem (Proof in Appendix F). For every g 2 2, there exists ON such that no subset S N (log(m)
satisfies positional representation for group size g with size |K] Ω
Tor log(m))
Proof Sketch. We will construct a preference profile ON where K must be large to satisfy positional representation. First, enumerate all possible subsets of N of size g as (G1,-.., (G())..,((G)) We then = b, if & G, where a, b,
construct a preference profile ON such that dür a, if i E G, and are distinct alternatives for all E ("). By this construction, for every r (*). a subset K satisfying Equation (2) for alternative a, must include at least one metric from G,.. Therefore, K must include at least one metric from every subset of size g of N, which means K must have size at least n g We then show that n - + satisfies the desired bound.
Although achieving |K| = [n/g] is not always possible, we still want to efficiently find a K that satisfies positional representation for group size g and contains relatively few metries. We next present Algorithm 1, polynomial time greedy algorithm that finds such a K with [K] < g log(m).
2.2 Algorithm
We first give a high-level overview of the algorithm. The algorithm iterates through every element of the preference profile row by row. As it does so, it keeps track of how many times each alternative has shown up. Whenever j has shown up g times, the algorithm colors the last entries of j with a new color and resets the counter for alternative j. Table 2 provides an example of the coloring the end of this procedure. Note that if n/g is not integral, not all of the elements will be colored.
After completing this process, the algorithm greedily selects metrics to include in the subset K based on the number of colored alternatives in each metric's column that are not included a previously selected metric. Specifically, the algorithm will select the first metric from the set of metrics that have

---

the most colored elements. The second metric is selected from the set of metrics that have the most new colors, and so on. This process continues until there are no new colors remaining among the unselected metrics, at which point the algorithm returns the set of selected metrics.
Algorithm 1 Greedy (pseudo-code)
Require: Preference profile n. group size 9
1: while there exist alternatives with at least y uncolored instances do
2: Choose an alternative with at least uncolored instances
3: Color the highest y uncolored instances of with a new color (breaking ties arbitrarily)
4: end while
5: Initialize K 0
6: Let C' be the set of colors used
7: while C' is nonempty do
8: Choose a metric E N \ K that covers the most colors in
9: Add i to K
10: Remove the colors that covers from C
11: end while
12:
return K
The full algorithm is presented in Appendix D. Theorem gives the formal bound for Algorithm 1. Theorem (Proof in Appendix E). For any preference profile ON and any group size g. Algorithu I terminates in polynomial time and returns a subset with [K] I O log(m)) which satisfies positional representation for group size g
Proof sketch. The key idea of the proof is to keep track of the number of distinct colors that K does not yet cover after iteration t of the loop on Line 7 of Algorithm 1. Denote this quantity Q-. By construction, the number of colors at the beginning of the loop is Qo I wn The algorithm terminates at the smallest time where Q; = O. We first show that for each round of the loop, the metric E N that covers the most remaining colors in C' must cover at least Q, colors. Therefore, for all t, we n/g
have Q++1 S Qe (1 - 2) We also know that if Q, S n//g, then Q++1 I Q Combining these two equations, we show the desired result that Q. for t 2 (n/g 1) log(m).
Because any K satisfying positional representation must have size at least [n/ Algorithm selects no more than log(m) factor more metrics than the smallest number needed to satisfy positional representation, For any o.. For a given a N. we can find the minimum number of metrics needed to satisfy positional representation using an integer program (see Appendix A); however this is not guaranteed run in polynomial time.
3 Positional proportionality
While positional representation guarantees that each alternative gets sufficient representation in the subset of metrics chosen for each position cutoff, it does not prevent over-representation. For example, an alternative ranked the top 10 in a exactly times, then in order to satisfy positional representation with parameter g. a must be ranked in the top 10 in o x at least once. However, there's no upper bound on how many times a can be ranked in the top 10 10-it it could be possible to satisfy positional representation for this instance and have ranked in the top 10 by every metric in K.
In this section, we define notion of proportionality which prevents both under-ropresentation and veerreppesennttion. This notion, positional proportionality, especially useful for recovering summary information such as the fraction of metrics which rank an alternative in the top half. We will show that K satisfies positional proportionality for a N, then any positional scoring rule evaluated on K is good approximation for the same scoring rule evaluated on d
Informally, positional proportionality guarantees that for every alternative and position cutoff, K preserves the fraction of times that alternative is ranked above that position cutoff within additive error e. From this guarantee, we can also recover the fraction of times that each alternative is ranked each specific position within additive enror. The formal definition for positional proportionality follows below.
5

---

Definition 4. A subset K satisfies e-positional proportionality for 2 0 ffr every alternatie a E A and every r [m], the fraction of metrics that rank in the top r in N is within of the fraction of metrics that rank a in the top in K. Formally, for all a E A and r E [m].
((N,r,a) C(K, (.K,T,a) |
S.
|
Note that, unlike positional representation, positional proportionality is not parameterized by group size g, but rather by an error e. As in positional representation, the choice of trades off the accuracy guarantee for proportionality with the minimum size of K necessary. As increases, the size |K] decreases, but the error in how well K captures N for each alternative and position cutoff may increase. As a concrete example of positional proportionality, suppose that we have n = 100 metrics and use parameter e L. Further suppose that is ranked first by exactly 20 metrics in N. Then Definition 4 requires that the fraction of metrics in that rank a first is between 4 25 and & Definition 4 further requires that approximate proportionality holds for every alternative at every position cutoff.
25-
While both positional representation and positional proportionality enforce ways that K must be representative of N, neither property implies the other, and neither is weakly easier to satisfy. In particular, positional representation strictly prevents represeepressnntation, while positional propor- tionality approximately prevents both reder-representationn and vver-representation. In the worst-case (and, we expect, in the typical case), the minimum number of metrics needed to satisfy positional representation with parameter g is less than the minimum number of metrics needed to satisfy po- sitional proportionality with e = g However, this is not always the case. For instance, suppose that every metric in N has the exact same ranking over alternatives. Then positional proportionality can be satisfied with K| = for any 2 0 by choosing an arbitrary metric. However, for any g S //2, positional representation cannot be satisfied with less than [K] = 2. Intuitively, this is because positional proportionality gives a fractional guarantee, while positional representation gives an absolute guarantee, which sometimes allows positional proportionality to be more efficient in its information aggregation.
3.1 Upper and Lower Bounds
In this section, we present upper and lower bounds on the number of metrics necessary to guarantee positional proportionality. First, show that for any preference profile n,, there always exists set [K] with size |K| = O ( lo)(m)) that satisfies positional proportionality.
Theorem 5 (Proof in Appendix G). For every preference profile ON and e 2 0, there exists K C N with K| I 1/2 (2g(2m) that satisfies positional proportionality.
We next show that there exist preference profiles O for which there is no K with size less than O L log(m)) that satisfies positional proportionality. Importantly, this shows that the result of Theorem is tight up to constant factors.
Theorem 6 (Proof in Appendix H). For any e S 1/24. there exist ON such that no K C N with |K| 28822 log(m) satisfies e-positional proportionality.
Proof sketch. We prove this result by designing a random n such that with positive probability, there is no K C N with |K| < 28827 log(m) that satisfies e-positional proportionality. We construct the random N as follows. For every metric and every j E [m/2], with probability 1/2 we will have alternative 2j ranked in position 2j and alternative 2j + 1 in alternative 2j + 1, and with probability 1/2 we will have alternative 2j + ranked in position 2 and alternative 2j ranked in position 2j + 1. This is done independently for all metrics i and all j. For each fixed K S N with [K] S 288.2 log(m). we upper bound the probability that K satisfies e-positional proportionality to be exponentially small. Intuitively, K has an exponentially small probability of satisfying e-positional proportionality because the randomly assigned rankings must be approximately evenly distributed for a j E [["] simultaneously, and independence implies this has small probability. We formally show this using an inverse version of Hoeffding's 's Inequality. After bounding the probability of any fixed K satisfying e-positional proportionality, union bound gives that with positive probability, no such K satisties e-positional proportionality. This proves there must exist a profile N such that no K log(m) satisfies e-positional proportionality.
with K < 258,
As with positional representation, we can find the smallest K that satisfies positional proportionality for given instance using an integer program (see Equation (4) in Appendix A).

---

3.2 Approximating Scoring Rules
nice feature of positional proportionality is that it allows us to approximate scoring rules evaluated on n using only σк. Informally, scoring rule such Borda count aggregates multiple rankings into a single ranking by assigning scores to each alternative based on its position in each of the original rankings [Young, 1975]. Because positional proportionality approximates the frequency at which an alternative a is ranked above a cutoff' r up to an additive error, positional proportionality also approximates the frequency which is ranked exactly position r up to 2c additive error. This information in turn allows us to estimate the result of any scoring rule evaluated on o which especially helpful when N is an intermediary of another computation, such as when N being used to decide a single winning alternative or a single meta-ranking.
Formally, scoring rule has an associated score vector 8 IR"", where 81 .... 8m. It is without loss of generality to normalize so that 8 = and 8m = 0. When using a scoring rule to aggregate rankings, each metric awards 8, points to the alternative that ranked in position r, which results in each alternative having an average score of fa xx) == TNT ΣiEN (a) In Theorem 7, we show that given any scoring rule and any K satisfying e-positional proportionality, every alternative has approximately the same average score о as in ON.
Theorem 7 (Proof in Appendix 1). If subset K satisfies e-positional proportionality, then for every scoring rule with score vector s and every alternative a E A, Ifa(a, - fa(a, ok)l
4 Generalizations
In previous sections, our goal has been to choose subset of metrics that preserves rank information from the original set. However, there may be other types of information we would like to preserve instead of or in addition to rank information. For example, perhaps the metrics fall into different categories, and we want to include sufficiently many metrics of each category. It turns out that we can generalize both positional representation and positional proportionality to settings like this.
Formally, suppose we have a collection of 7 groups of metrics g {G:] where G, S N. Our goal is to choose a K that represents every G E G. In the following two definitions, we generalize both positional representation and positional proportionality to this setting.
Definition 8. For given N and collection of groups G. a subset K N satisfies generalized [.,1
representation for group size for every G, E EG. |K 2
g
Definition For a given N and collection of groups 9. a subset K S N satisfies e-generalized
proportionality for 2 0 for every G; E g,
|G,] |N] [
|KnG,]
c.
Note that positional representation (Definition 1) and positional proportionality (Definition 4) are special cases of Definitions 8 and 9 for a specific choice of G that depends σx. Specifically, given ON. we can construct 9 as follows. Let 7 = m² and let G = (Gar} where for each a E A and [m]] we define Gar == {i E N aa(a) < r). In other words, for every E A and r E [m]. there is one group in G that corresponds to all of the metrics that rank in the top r positions. By construction, any subset K that satisfies generalized prrreseetatiooppooorrtoonal for this choice of g will also satisfy positional represenaation/pooorriion
While the groups in Definitions 8 and 9 can be based n. they need not be. Definitions 8 and give us the freedom to define groups in whatever way is useful, which in turn allows us to specify which types of information to preserve. Below are some examples of groups
could define:
Suppose some metrics are in English, some are in Chinese, and some are in Spanish. Then for each language, we could have group in G corresponding to all metries in that language.
Suppose the metrics have a range of difficulty. Then for each difficulty level (c.g. very easy, easy, hard, very hard), we could have group in G corresponding to all metries of that difficulty level.
Suppose we have ten experts who each believe a different subset of metrics are important. Then for each expert, we could have group in G including all metrics that expert supports.
In Appendix B, we show how the lower and upper bounds of Theorems 2-6 can generalized to give bounds for Definitions 8 and 9. In Appendix B, we also discuss the relationship between Definition and set cover. Finally, we show that finding the smallest set that satisfies either Definition 9 or Definition 8 is NP-hard.
7

---

5 Empirical Case Studies
We demonstrate our proposed definitions and algorithms on three real-world case studies that involve selecting subset of metrics for evaluation and decision making. To illustrate the wide potential applicability of our approach, we consider two case studies on evaluating LLM capabilities, and one case study evaluating hospital quality. Each case study includes full set of metries, an existing subset of metrics currently deployed (e.g., an existing LITE benchmark), and a set of alternatives. Our experiments focus on two goals: (i) supplementing our theory by comparing the performance of our algorithms relative to the stated upper and lower bounds on real datasets, and (ūi) demonstrating practical relevance by comparing against existing deployed subsets. An additional consideration is that a practitioner might want to keep an existing curated subset, so we also show that our algorithms can also be used to augment an existing subset. We summarize each case study below, and provide more details and code in the Supplemental Materials.
Case Study 1: BIG-bench [Srivastava et al., 2022]. We consider the problem of selecting a subset of 141 BIG-bench JSON metries to include in "lite" version. The existing BIG-bench Lite includes k = 24 JSON metrics, and was "designed to provide a canonical measure of model performance, while being far cheaper to evaluate than the full set." The alternatives consist of m = 120 LLMSs from three model families.
Case Study 2: HELM [Liang et al., 2022]. We next consider the problem of selecting subset of = 34 scenarios available on HELM Classic for a Lite version. For this case study, we compare against the & = 7 metries from HELM Lite that are from HELM Classic. The alternatives consist of m 67 models that appeared on the HELM Classic leaderboard as of March, 2025.
Case Study 3: Cal Hospital Compare [Cal Hospital Compare, 2025]. Beyond LLMs, we also demonstrate how our methods can apply more widely through case study on hospital quality evaluation. Cal Hospital Compare uses a subset of k = 12 hospital quality metrics selected from full set of metrics collected by the Centers for Medicare and Medicaid Services (CMS). For the purposes of this illustration, we consider the problem of selecting a "representative set of quality metrics from the database. The alternatives consist of m = 282 hospitals in California.
50 existing patient safety metrics available in the CMS Hospital Compare
5.1 Results
We now empirically evaluate the performance of the proposed algorithms for achieving positional representation (PR) and positional proportionality (PP). We evaluate each method by comparing the subset sizes K achieved for each tolerance parameter (group size g for PR, tolerance e for PP). Smaller subsets are better.
Positional Representation. We first evaluate the performance of Algorithm (Greedy) relative to our theoretical upper and lower bounds, as well as the optimal integer programming solution. Figure I shows that in practice, the greedy algorithm performs significantly better than the upper bound, but a gap remains relative to the optimal integer programming solution for small group sizes.
For all case studies, the greedy algorithm finds subset smaller than the existing subset, while guaranteeing positional representation for smaller group size g than the existing subset guarantees (marked by the blue points in the bottom left quadrant). This suggests that if positional representation important to a practitioner, is possible to achieve it more efficiently than the existing subset.
In practice, the existing subset is often carefully curated. Thus, we also evaluate the performance of using our greedy and integer programming algorithms to optimally augment the existing subset for PR. Figure shows that a subset optimally augmented using an integer program can perform better than the greedy algorithm for small group sizes. A computational advantage of augmenting the existing subset is that it reduces the free parameters of the integer programming problem. Thus, augmenting the existing subset could be a computationally practical approach that can beat the greedy algorithm in some cases, and is worth considering by practitioners.
Positional Proportionality. For positional proportionality, we compare the integer programming solutions to the existing subsets. Figure 2 shows that for all datasets, the IP is able to find subsets of a smaller size than the existing subset that can guarantee PP at a lower e tolerance. This again
'The optimal integer program is computationally feasible as our real instances have n < 141 and m < 282. Even when the IP employed, Theorem 3 is directly useful it upper bounds the size of the optimal solution.
8

---

BIG-bench
HELM
Hospiral Compare
149
Groedy
122
ougisentted
Salacteed subaat 45
30
Solleted subset stze JK]
50
1.00
sugmenied
25
50
Sellctad calent
Upperr bound
80-
Lower bound
20
-0
Size of caistan subset
60-
Min for
15-
20-
cxisting subset
20
12
20
40
10
20
25
30
1.0
20
30
40
Group sizee
Geoup size:
Figure I: Results of running greedy and integer programming algorithms to achieve positional representation. The upper and lower bounds are from Theorems 3 and 2. The dashed red line marks the smallest y for which the existing subset guarantees PR.
BIG bench
HELM
Cal Hospital Compare
60
140
122
Upper bound
wagmenied
Solected subout c000 [K]
100-
Tawoer bound
40-
Salected sahret
80-
Min fur
Size of catsting subset
Salucee valuue
25
30-
existin subset
20
60-
15-
20
10-
20-
0.2
0.0
0.2
0.4
0.5
0.0
0.2
0.4
0.8
Telerance
Figure 2: Results of running integer programming algorithms to achieve positional proportionality. The dashed red line marks the smallest for which the existing subset guarantees PP. The upper and lower bounds are from Theorems 5 and 6
suggests that there exist more efficient ways to achieve PP. As with PR, it is also possible to augment the existing subset to achieve PP. This was most apparent with Cal Hospital Compare, where it is possible to achieve a much smaller by adding less than five more metrics.
6 Discussion
We conclude by discussing limitations and future directions. In our work, we introduced two desirable properties that a subset of metrics should have in order to preserve rank information from the original set of metrics. One limitation is that it is not clear whether the subset chosen is good for evaluating new alternatives, especially if there is a distribution shift in the nature of alternatives over time (e.g., major advancements in LLMs). While we expect that the chosen subset of metrics will be reasonable at evaluating new alternatives in the short term, we recommend occasionally recomputing the subset necessary to account for new metries joining the overall set paradigm shifts among the alternatives. As an open question, it would also be interesting to obtain theoretical guarantees about how well a selected subset of metrics generalizes evaluating new alternatives.
Throughout our work, we attempt to curate a subset which is reflective of the overall set. However, if the overall set is biased or some types of metrics are overrepresented, we would expect that bias to be reflected in our subset as well. The purpose of our work is to select a good subset of metrics assuming the overall set captures what the user wants. This means our algorithms are agnostic to how and why the overall set of metrics was selected, which allows for tremendous flexibility, but also puts some onus the user to make sure the overall set achieves the desired objective.
There are several other future directions of note. First, while we provide some case studies in Section 5, it would certainly be interesting to study other practical settings and the best choice of parameters g and e in each. In this work, we largely did not discuss what to when there is missing data, i.e., not all metrics rank all alternatives. While one natural approach is to assume all missing alternatives are tied for last, this is not the only viable approach, and we leave exploration this direction to future work. Finally, certain metrics may have higher costs (e.g., running them may require more computational resources). It would be interesting to explore how to balance cost and usefulness of metrics when selecting representative subset, especially if the user is budget-constrained.

---

References
Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, and Toby Walsh. Justified representation in approval-basee committee voting. Social Choice and Welfare, 48(2):461-485, 2017.
Rémi Bardenet and Odalrie-Ambyym Maillard. Concentration inequalities for sampling without replacement. Bernoulli, 21(3), 2015.
Cal Hospital Compare. Patient safety honor roll. 2025. URL htt.hhtpss/ccallppptaaalcco
org/pr heg/programs/pattiee http:/attiiiettteeeeeeeeeeeeeeee wwwety-hoeee----aeeeaeeea
loannis Caragiannis, Evi Micha, and Nisarg Shah. Proportional faimnsss in non-centroid clustering.
Advances in Neural Information Processing Systems, 37:19139-19166, 2024.
Chandra Chekuri, Kenneth L Clarkson, and Sariel Har-Peled. On the set multicover problem in geometric settings. ACM Transactions Algorithms (TALG), 9(1):1-17, 2012.
Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. Proportionally fair clustering, In International conference machine learning, pages 1032-1041. PMLR, 2019.
Vasek Chvatal, greedy heuristic for the set-covering problem. Mathematics of operations research, 4(3):233-235, 1979.
Pierre Colombo, Nathan Noiry, Ekhine Inurozki, and Stéphan Clémençon. What are the best systems? new perspectives on nlp benchmarking. Advances in Neural Information Processing Systems, 35: 26915-2690 26932, 2022a.
Pierre Jean A Colombo, Chloé Clavel, and Pablo Piantanida. Infolm: A new metric to evaluate summarization data2text generation. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pages 10554-10562, 2022b.
Anas Himmi, Ekhine Irurozki, Nathan Noiry, Stephan Clemencon, and Pierre Colombo. Towards more robust nlp system evaluation: Handling missing scores in benchmarks. arXiv preprint arXiv:2305. 10284, 2023.
Qiang- Hua, Dongxiao Yu, Francis CM Lau, and Yuexuan Wang. Exact algorithms for set multicover and multiset multicover problems. In Algorithums and Computation: 20th International Symposiun, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings 20, pages 34 44. Springer, 2009.
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, 2023.
David S Johnson. Approximation algorithms for combinatorial problems. In Proceedings of the fifth annual ACM symposium on Theory of computing, pages 38-49, 1973.
Yusuf Hakan Kalayci, Jiasen Liu, and David Kempe. Full proportional justified representation. arXiv preprint S.VV:25001.2011:. 2025.
Yang Li, Jie Ma, Miguel Ballesteros, Yassine Benajiba, and Graham Horwood. Active evaluation
acquisition for efficient Umm benchmarking. arXiv preprint arXiv:2410005955, 2024.
Percy Liang, Rishi Bommasani, Tony Lee, Dimitris Tsipras, Dilara Soylu, Michihiro Yasunaga, Yian Zhang, Deepak Narayanan, Yuhuai Wu, Ananya Kumar, et al. Holistic evaluation of language models. arXiv preprint 2rXiv:2211.0000 1.09//0010111.....00000111111111 2022.
Jifí Matoušek and Jan Vondrák. The probabilistic method: lecture notes. Charles Univ., 2001.
Evi Micha and Nisarg Shah. Proportionally fair clustering revisited. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), pages 85-1. Schloss Dagstuhl-Leiihnn Zentrum für Informatik, 2020.
10

---

Swaroop Mishra and Anjana Arunkumar How robust are model rankings: A leaderboard cus- tomization approach for equitable evaluation. In Proceedings of the AAAI conference on Artificial Intelligence, volume 35, pages 13561-13569, 2021.
Balas Kausik Natarajan. Sparse approximate solutions to linear systems. SIAM journal computing, 24(2):22-2334) 1995.
Yotam Perlitz, Elron Bandel, Ariel Gera, Ofir Arviv, Liat Ein-Dor, Eyal Shnarch, Noam Slonim, Michal Shmueli-Scheuce and Leshem Choshen. Efficient benchmarking of language models. arXiv preprint arXiv:2308. 11696, 2023.
Dominik Peters, Grzegorz Pierezyúski, and Piotr Skowron. Proportional participatory budgeting with additive utilities. Advances in Neural Information Processing Systems, 34:12726-12737, 2021.
Maxime Peyrard, Teresa Botschen, and Iryna Gurevych. Learning to score system summaries for better content selection evaluation. In Proceedings of the Workshop on New Frontiers in Summarization, pages 74-44, 2017.
Felipe Maia Polo, Lucas Weber, Leshem Choshen, Yuckai Sun, Gongjun Xu, and Mikhail Yurochkin. tinybenchmarks: evaluating Ilms with fewer examples. arXiv preprint arXi::2402.1499: 2024.
Mark Rofin, Vladislav Mikhailov, Mikhail Florinskiy, Andrey Kravchenko, Elena Tutubalina, Tatiana Shavrina, Daniel Karabekyan, and Ekaterina Artemova. Vote n rankk Revision of benchmarking with social choice theory. arXiv preprint arXiv:22 2022.
Luis Sánchez- Fennädezz Edith Elkind, Martin Lackner, Norberto Fernández, Jesús Fisteus, Pablo Bas- anta Val, and Piotr Skowron. Proportional justified representation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Piotr Skowron and Piotr Faliszewski. Fully proportional representation with approval ballots: Ap- proximating the maxcover problem with bounded frequencies in fitt time. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonss et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. arXiv preprint arXiv:2206.044
04615, 2466:2226... 2022.
H. Young. Social choice scoring functions. SIAM Journal of Applied Mathematics, 28(4):224-838 1975.
Guanhua Zhang and Moritz Hardt. Inherent trade-offs between diversity and stability in multi-task benchmark. arXiv preprint arXiv:2405.01719 2024.

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All of the claims in the abstract and introduction are accurate.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Limitations are discussed throughout and the discussion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
12

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
All formal proofs are included the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Detailed descriptions of experiment setups and parameters included in the Appendix. All algorithms are given in detail in both the paper and in the code.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
13

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Code is provided in the Supplemental Materials to reproduce all experiments. All data used public, and information on downloading data is given in both the paper and code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/ cossincccycyy ooiicy for more details.
http://uuuieeeeooouuusuissssstss Codeeoobiiiiiiinecooo wwrpoomsssssoooolooomooooooo public/ httlcc//g//e///eee
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nwpp. wttpss/ccccpcccccccccccccccccccc wwwpc//ggge/ee/eeeee Cooeeeubeeeeeeeeee ssi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: All dataset setup details are provided, and all parameters for optimizers are included in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
14

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Discussion of stochasticity and statistical significance was included everywhere this was relevant.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All details were provided computation time and machine.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
15

---

Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp::/ httppp/ccc.pp..ccccccccucueeeee.
Question:
Answer: [Yes]
Justification:
The research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discusses both potential positive and negative societal impacts in the experiments and main paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
16

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All datasets were linked and cited. Licenses are referenced and respected. The date of access was given.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
17

---

14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy hnttps://neurre httprr/ppp..ccoooeeee////////220 for what should or should not be described.
18

---

A Integer Programs
In this section, we present integer programs which for given instance ON give the smallest number of metrics necessary to guarantee either positional representation or positional proportionality
First, we define Syo be the of metrics which rank at least high as r, i.. Sre {i e 0,(a) r}
The IP for finding the minimum size set that satisfies positional representation is as follows:
mim
IEN
C(N,r,a)
Σ 24
Vr [m]. e A
g
i
24
{0,1)
Vie
[n]
(3)
The IP for finding the minimum size subset that satisfies positional proportionality is as follows:
min
Σ
((N,r,a
a)
Σ I3 VEN
Vr [m], A
IN
iES.a
Σ
C(N.r,a) +e [N]
Σ VEE
Iz
Ar (m],aa A
kESra
34
(0, 1)
Vie [n]
(4)
B General Versions and Set Cover
B.1 Theoretical Results
Our main theoretical results from the previous two sections generalize to this setting. The main difference is that the log term in the theorem statement will now depend on the size of G. Intuitively, 9 is bigger, then more metrics are needed to guarantee representation for all G E g. We state the generalizations of the upper bounds in Theorems 10 and 11. Note that in the ranking setting, G = m² so Theorems 10 and 11 give a worse upper bound than Theorems 3 and 5. This because for positional representation and positional proportionality, we have better upper bound the total size over all groups.
Theorem 10. For any n,, collection of groups G, and group size g, the generalized greedy algorithm (Algoritium 2) terminates in polynomial time and returns a subset K with |K] < 12 llog (191) which satisfies generalized representation for group size g
proof. The proof of this result follows as in the proof of Theorem except that instead of Qo ma we have that Qo < (a. The rest of the recursion proof follows exactly the same to give the desired bound.
Theorem 11. For any ON, collection of groups G, and e > 0, there exists a subset K with size |K| < 2e log (4[G)) that satisfies generalized proportionality.
proof. The proof follows as in the proof of Theorem 5, except now have union bound over all [g] groups rather than all m² combinations of a and r.
Because positional representation and positional proportionality are special cases of general represen- tation and general proportionality, the lower bounds of Theorems and also directly generalize to the general versions of these properties.
19

---

B.2 Relationship to Set Cover
General representation (Definition 8) is closely related to set cover, but has some key differences. In set cover, the input is set of elements U and a collection of subsets C where C' S U for all C' E C. The goal is to find the smallest number of subsets from C. whose union equal to U. Similarly, in order to satisfy general representation, we need to find a subset of metrics which covers each group sufficiently many times. However, general representation differs from set cover in that in general representation, the number of times each G' (element) needs to be covered depends on the number of metrics that are in G. For example, if [G| < g. then G does not need be covered by K at all. On the other hand, if G = Ey. then G needs to be covered at least E times in K. Note that general representation also differs from the set multi-cover problem (where each element has given number of times it must be covered) because in that problem, the number of times an element must be covered not tied to its frequency [Chekuri et al., 2012, Hua et al., 2009].
More formally, suppose we index g [G. G. Consider the set cover problem with U } and C' = [C...... C, where C. = = hl : Gj}. The goal of set cover for this choice of U and C is to find the smallest K S [N] such that for every u E U. li e K : E C,) 2 1. Using the same notation, the goal of finding the smallest K that satisfies general representation is equivalent HHENN
to finding the smallest K C N such that for every u E U, lii E K a cCH N
It is well-known that there exists an algorithm which achieves [Johnson, 1973, Chvatal, 1979]. We note that Theorem 10 is not subsumed by this result. First, observe that both these theorems guarantee an absolute bound on the number of benchmarks that are needed to satisfy general representation, rather than an approximation to the minimum number of benchmarks needed. In set cover, it is impossible to guarantee an absolute bound better than |C] consider, for instance, the set cover instance where = [fu}= u E U}. Second, as mentioned earlier, general representation differs from set cover by requiring representation for an element based on the frequency that element appears.
-pproxxaoooiiniioonn for set cover
We show that it is NP-hard find the minimum size subset that satisfies either Definition 8 or Definition 9. The proofs of Theorems 12 and 13 can be found in Appendix K.1 and K.2 respectively. Theorem 12. The problem of finding the smallest set K that satisfies generalized representation
(Definition 8) is NP-hard.
Theorem 13. The problem of finding the smallest set K that satisfies generalized proportionality
(Definition 9) is NP-hard.
C Additional Related Works
In the setting of JR, there are n voters and m. candidates, and each voter indicates whether they approve of each candidate. Based on this approval information, the goal to select a committee of size k from the candidates. JR considers every cohesive coalition of voters, which is a group of size least n/k that all approve the same candidate. A committee then satisfies JR if at least one member of every such cohesive coalition approves of some candidate in the committee. Proportional Justified Representation (PJR) introduced by that that larger coalitions with more agreement will have more representation in the committee. Many other variations on justified representation have also been studied, including (but not limited to) Extended Justified Representation [Aziz et al., 2017], Full Justified Representation [Peters et al., 2021], Full Proportional Justified Representation [Kalayci et al., 2025]. Like JR, positional representation guarantees representation for every sufficiently large "coalition" of metrics that all rank an alternative a above a position r, with proportionally more representation for larger coalitions. Unlike in JR, in positional representation there are external voters; rather, the metrics serve as both the voters and the candidates. Furthermore (and also unlike JR), metrics do not indicate whether they approve of other metrics instead, whether representation is deserved is based solely the rankings.
et al. [2017] extends JR by requiring further
There is also a line of work on proportionally fair clustering that uses similar notions of coalitions of size n/k [Chen et al., 2019, Micha and Shah, 2020, Caragiannis al., 2024]. These works differ from our setting in that there is no notion of ranking representation. Another major difference between these works and our setting is that our set of selected metrics must be a subset of all metrics, while clustering algorithms generally able to choose any points as the centers of the cluster.
20

---

D Full Greedy Algorithm
During the algorithm, we assign labels (or "colors") to metrics. We use the set of natural numbers as labels, and let represent the lowest unused natural number. C₁ is the set of labels assigned to metric At any point time, Sj represents the set metrics that have already approved alternative j but have not yet been assigned j-label.
Algorithm 2 Greedy for positional representation
1: Input: Preference profile dN. group size
2: Initialize S <- for all j E [m]] C, <- for all i [n]. and e <-
3: for each r E [m] do
4: for each E [n] do
5: Let j dir
6:
Add to Sj
7:
if s,, = then for each i' E S do
8:
9:
Add Cy end for c+1
10:
11:
12:
5 0
13: end if
14: end for
end for
16: Let C' t [1.2,..., 11,-111,11 1J. K + 0
while C & do
18: Select + arg max; |Cyl
Add K
20: for each C do
for each i' E [n] do
22:
if a E Cr then Remove x from C2
24: end if
25: end for
26: Remove from C'
27: end for
28:
end while
29:
Return K
E Proof of Theorem 3
Proof of Theorem 3. First, map each label unique color. Greedy adds one metric to the in each iteration of the loop on Line 17 and this loop ends once all colors are covered. To bound the number of iterations, we analyze how many colors are not yet covered by K each step.
Let a a= a/g, and let Qt be the number of uncovered colors after iterations of the loop on Line 17 of Algorithm 3. Initially, Qo ml m I m Each color is covered by exactly g metrics and is covered most integer & 2 1, there must exist metric covering at least + uncovered colors. In other words, there are Q, colors remaining after iteration t, then the next metric chosen iteration t must contain at least [Qt/a] distinct colors. This gives the following recurrence:
g by each metric. so if there strictly more than a colors remaining for any
Q++1 SQ [Q:aa < Qe - 1/aa)
Because Qu I m a, this means that
Q. S m a (1 1/a)*.
(5)
Once Q: S a, every metric chosen by the algorithm will still contain at least one new uncovered color, so for Qi S a we have that
Q++1 S Q
This means that once Q S a. the loop will finish in most additional steps.
21

---

Now, we will upper bound the number of steps until Qi S a. By Equation (5), we have that Q: S for any & satisfying
a (1 1/a)² a.
Solving and simplifying this equation gives that Qi S a for any satisfying
t log(m)/ log(a////l/a/a 1)).
Note that
log(a/(a 1)) log((a) log(a (a- 1) = f 1/zde 1/a. a-
Combining the previous two equations, we have that Qt S a for any satisfying
t log(m).
As we argued above, the algorithm will only add at most more metrics once Q: S a, therefore the total number of metries added to K by Greedy is most
+ log(m) O (" log(m)
as desired.
F Proof of Theorem 2
Proof of Theorem 2. Fix any g 2 2. Choose any and n such that
g 2 3 is an integer and such that
m 2
Construct N as follows. First, enumerate all (*) distinct subsets of N of size as {G ..., G(y) We will assign 2 distinct alternatives to each of the first (") ranking places. Let {a,, b, be the alternatives assigned to rank for r E [1 (Q) Let dir or if E G, and oir = b, if & Gr- Therefore, alternative will be ranked r by exactly metrics while alternative 6, will be ranked by exactly g metries. This means that only alternatives {a,, b will be ranked position for any of the metrics.
Now set the rest of the rankings (for positions (7) through m) of the metrics arbitrarily in any valid way. This will not matter for the rest of the proof.
Define a n/g. Next, we will show that group size g in this example with K having size less than (a 1)g + 1. Proof by contradiction. Suppose we have a K such that | < (a 1)g and satisfies positional representation for group size g. Then there must be a set of metrics not included in K. Denote this set of metrics as G. Because we used every possible subset of N for the permutations of a,, by the first (*) positions, there is some position and some alternative aę such that ap is ranked exactly in every metric in G' and such that does not appear ranked in the top ř in any metric not in G. In order for to satisfy positional representation for group size g, at least one of the rankings in G must be included in K, which is contradiction.
of metries can satisfy positional representation for
Therefore, we must have that any K satisfying positional representation for group size must satisfy |K| (a 1)g.
Furthermore,
2 (1) 2²()) < log (2g(2))) = g log(n) + log(2) S 2g log(n).
log(m) = log
9
22

---

The previous equation implies that 2 (m)( any K satisfying positional representation,
Using this on the third line below, we have that for
2 Tlg(n))
| 2 (a
1)g
1 g
nn/g 1) log(m)
21og(n)
2g log(m)
2 log(n)
log(m)
(6)
4 (n)
The last step is to upper bound log(n). By construction,
m
2
20 n/a
Taking the log of both sides,
log(m) 2 1og(2) + n log(a),
which simplifies to Taking log of both sides again gives
S alog log log
log(a)
log(n) < log (<llog(m) 1og(2))
< log((a log(m)) = log n
log(m)
log(a)
Combining this with Equation (6), we have the desired result that for any K satisfying positional representation,
log(m)
K
4 log
2/4 log(m))
G Proof of Theorem 5
We the probabilistic method. Suppose select K by choosing exactly 1 log(2m) random metrics from N one-by-one. Consider any fixed alternative a and position r. Let X X1..., X|Kı be indicator random variables where X₃ is if a is ranked in the top by the ith chosen metric in K. Then we have that E[X,] = C(N.r.) for all We will use the following version Hoeffding's inequality for random variables chosen without Replacement
N
Lemma 14 (Hoeffding's without replacement Bardenet and Maillard [2015]). Let X (x1 IN) be a finite population of N real numbers, and let XI,..., X,, be random sample drawn without replacement from X. Define:
N
a min Ti. b max SSI
ISINN
N
==1
Then, for all 0.
1 12
2ng²
X 4
28
2exp (T - a)²
n
i=1
23

---

Applying Lemma 14, we have that
Pr ( [ N
a)
C(K,r, vr
C(N,r,a)
[K] >
Pr
X;
2E
K
N
i=1
2e
2|
2e -2 20mm
1
2m2
By union bound over all m² combinations of and r, we then have that
C(N,r,a)
C( >
1 2m
Pr
Ba,r:
m²
1/2.
[N|]
K
We can then take the complement of the event above to observe that K satisfies positional pro- portionality with probability at least 1. This probability positive, so there must exist a K with
|K] $ 2 log(2m) that satisfies positional proportionality.
H Proof of Theorem
Proof of Theorem 6. We will prove this using the probabilistic method. We will show that there exists a random generation process for ON such that with non-O probability, no K S N with
|
28322 lmg satisfies e-positional proportionality.
First, we will choose n and m such that m even and n and m are sufficiently large so that the following three equations hold:
log(m) log(n + 1)
Vm
- 1og((2
288c²
60
log(m) log(n 1)
+ log(m) 2nn < - -2og(2)
(8)
288c²
I/E log, (30vm)
Consider the following random generation process for ON. For metric i E [n]. the ranking for metrics will be generated as follows. With probability 1/2, metric i will rank alternative in the first position and alternative 2 in the second position, and with probability 1/2 metric i will rank alternative in the first position and alternative 1 in the second position. Repeat this process for all subsequent pairs of odd/even positions. So for all j [m]] ]. with probability 1/2 metric will rank alternative 2ÿ in the 2ÿ position and alternative 2j + in the 2j + 1 position. and with probability 1 1/2 metric will rank alternative 2j in the 2 position and alternative 2 in the 2j position.
We formalize this process follows. For every [m]] and E [1 n²). let X ~ (ernoulli(O.5). If X.y 0, then metric i ranks alternative 2j in the 2) position and alternative 2j + 1 in the 2j + 1 position. X,, then metric ranks alternative 2 + the 2I position and alternative 2j the 2j + position.
We will now show that with positive probability, no K C N with |K| < 28827 log(m) will satisfy c-positional proportionality for the random a generated as described above.
First, we define an event E, which corresponds to the event that for all j. approximately 1/2 of the metrics rank alternative 2j above alternative 2j and approximately 1 1/2 of the metrics rank alternative 2j + above alternative 2j. Formally, define
Vj
Σ (Xi) - 0.5) Sec
1=1
24

---

By Hoeffding's inequality and a union bound,
Pr(-B) = Pr
3j E m
Σ Xie (Xi)
0.5) >
21
1=1
m/2
Σ /=1
Pr
Σ
(Xig - 0.5) >0)
[Union Bound]
t=1
< me
2nc²
[Hoeffding's ' Inequality]
(10)
Now consider any subset K C N with K < 288:7 log(m)) We will lower bound the probability that this K does not satisfy positional proportionality.
Pr(K does not satisfy e-positional proportionality)
r.)
C(K,r,
Pr
3a E A,
E [m]
>
n
Pr
Aje E [m]
X15
X1
>
K
7
FE
1
[x,, -0.5) 0.5) 2x 22)) [A-ineq.]
Pr
bjj [m)
X
0.5
Se
[=]
K
iEK
24 })
Pr
E
Σ
(Xis
0.5) 2
K
iEK
2 Pr
3/
|
Σ
(Xi= - 0.5)
24
Pr(-E)
[Pr(An 2 Pr(A) Pr(-B))
K
KEK
2 Pr
3j E 1
Σ
(Xi 0.5)
> 26
me 2nd2
[Equation (10))
K
EEK
=1 =1 Pr
Vi (+)
Σ
(X,, 0.5)
2E 2
K
EEK
m/2
1
Pr
(Xu
0.5)
2e
me 2n.2
[lnd. of Xi]
VEK
m/2
21
me
2
[Lemma (15)
30
3m
m/2
>
1
50
2nd
[L+ e
60
Jog(m))
2n1
(1I)
25

---

Using the above equation, we can bound the probability that there exists [K] with size less than log(m) that satisfies positional proportionality as follows:
2882
Pr(a C N s.t. |K|S S
log(m) and K satisfies e-positional proportionality)
288
Σ
Pr(K satisfies e-positional proportionality)
[Union Bound]
KCN,JKIS 20802 (mg(
Σ
Li 00
+ clog(m))20 -2ne?
[Eq. (11)
KCN, 200.7 log(m)
- (n + 1) 289.2 log(m)
+ e (oog(m) 2
loR(mi +1)( 288
m
log(m) -000--2200 2ne"
log(m) log(n + 1)
vm
log(m) log(n +1) log(m) -2nc²
Exp
+ Exp
288c2
60
288c²
< Exp (-)og(2)) + Exp (- log(())
[Eqs (7) and (8))
1/2 1/2 1.
Therefore, we have shown that with positive probability, there will be no K with size |K] I 18827 log(m) that satisfies e-positional proportionality. Finally, we can conclude that there must exist some ranking N such that no K with size [K] S 288.2 log(m) satisfies e-positional proportionality.
In the equations above, we used the following inverse of Hoeffding's inequality.
Lemma 15. Using the notation and setting of the proof of Theorem 6 above, for any K satisfying | S 28822 log(m) and any j [[]]
Σ
(Xu
0.5)
> 2
K
3
iEK
Proof of Lemma 15. We will prove this separately for small | and for large [].
| S 1/e, then
1
Σ
(Xis
0.5)
> 2e
2 Pr
Σ X1y
x1
[e 1/24]
K
K
KEK
iEK
2- Kl
2 2 1/c
Equation (9)
30
/m'm m
which is the desired result.
To prove the desired result when [K] 1/e, we will use the following proposition from Matoušck and Vondrák [2001]:
Proposition 16 (Proposition 7.3.2 of Matoušek and Vondrák [2001]). Let XI,..., X, be independent
Bernoulli random variables with probability 1/2 of being 0 or 1. Let X X1 + ... + X,, Then for any integer E n/8).
Pr(X 2 n/2 1/30e 16t2/M
26

---

We can apply this proposition to our problem in the following way. If K > 1/c, then
Pr
(Xy - 0.5)
> 2e
K
EEK
Pr
Σ
(X 0.5)
> 2) 2/
KEK K
Pr
Σ (Xi 0.5)
> 2/K|c 0.5
KE
Pr
(Xi)
-0.5)
2 3|K|E
[|] 1/el
K
Pr
Σ EEK
X1j 2
+
2
[Prop 16 with K|]
30
1
144/K]22
30
144 28807 log(m))
30
e log(m)/2
30
(12)
30 m
which is the desired result. Note that could apply Proposition 16 because 3| S |K|/8 for S 1/24.
I Proof of Theorem 7
proof. If a subset K satisfies e positional proportionality for set N, then
C(,,r, C(K,r,a)
Sc
Vr, a.
n
K
Consider a scoring rule with scoring vector i.c. that gives score s, to an alternative in position
Define A, = S, 8,41 (where sm+1 0). Then by definition of scoring rule, we have that
fs(a,oN)= =
Sa,(a) n Σ C(Nrr.))
and
1
fs(a,ok)=
Σ Sol(a)
C(K,,,))...
K
ieK
27

---

Combining this with the first equation, we have that V.(a,on) [s(a,ox)) {
m
C(Nrr,))
r(
D
n
A
SSp sr+1
r=1
(81
8m+1)
=6
where the last line follows from the fact that WLOG $1 1.
J General Greedy Algorithm
Algorithm 3 Greedy for General Representation
1: Input: Preference profile dx. collection of groups G. group size
2: Initialize S <- 0, C; @ for all i E [n]] and e +- 1
3: for each G E G do
4: for each [ni] do
5: if E G then
6: Add to S end if
7:
8:
if [S] = then
9:
for each /' E S do
Add to Cy end for
11:
e c+11 13: S 0
end if
15: end for
16: end for
17: Let C' + {1,2,
11, K+ + 0
18: while C + do
19: Select i arg maxy |C₂l
20: Add i to K
21: for each C2 do
22:
for each i' E [n] do
23:
if E Cy then Remove x from C₃²
24:
end if 26: end for
25:
27: Remove from C
28: end for
end while
30:
Return K
28

---

K NP-Hardness Proofs
K.1 Proof Theorem
proof. Suppose we have instance of cover, i.e. collection of C y Ci for which we want to find the smallest set that contains every distinct element in the sets of C. Let U = Ucec C. We want map this to instance of our problem, which consists of N, 9, and for which would like to find the smallest subset that satisfies general representation.
The key idea of the proof is to construct instance of our problem where every group in G has the same size. Every element in U will have corresponding group G, G. We start with each Gu initialized to be the indices of the elements in C that contain However, this results in the G having different sizes. We then add new tasks to that are only contained in a single group G2 until all groups in G have the same size.
Formally, we construct N, 9, and y as follows:
Algorithm 4 Constructing N, N,9.9
Input: U, [Ci]ie(s)
2: Gu f (i: C,} for all U
3: f -max, Gul
4: K
5: for U do
6: while Guul < do
7:
i <- i+1
Add to G 9: end while
8:
end for
11:
Return {G Juev, N [t]. and
By construction, |G,, for all u.
We will now show that the set cover instance (U, C) has solution of size less than equal to k if and only there exists solution of size less than or equal to that satisfies general representation for N, 99 9. Suppose the set cover instance has solution Ć with |C| k. Then this Ć covers every element in U at least once. By construction, this K = {i < k C, E C} is a solution to the general representation problem, because general representation for group size where every group in G has size g requires that [G,, n K| 2 for all groups G2 E G.
For the opposite direction, suppose we have some K C N with | < le that satisfies general representation, Define K' as in Algorithm 5.
Algorithm 5 Constructing K'
Input: K
2: K" t K [x]
3: for E K [K] do
4:
u
such that G., +'+ any element of [s] such that u Cj
5:
6:
if & K' then
7:
K' (1U 8: end if
9: end for
10: Return K"
Note that at the end of this algorithm, JK| < |K| because never add an i' to K' unless there is corresponding E [x] that is not K'. Furthermore, K' still covers every group G., because the i' selected in Line covers the G. that always exists because every u E U is in at least one subset in C.
previously covered by in K. Note that such an i'
Therefore, we have that K' still covers every group in Gy and KK| < K < k. This means that = C=(C, : K'} is solution to the set cover instance with size less than equal k.
D
29

---

K.2 Proof of Theorem 13
proof. We will follow a similar proof structure to the proof of Theorem I in Natarajan [1995] on the NP-hardness of sparse approximate solutions to linear equations. As in Natarajan [1995], will reduce from the problem of "exact cover by 3 sets".
Exact Cover by 3-Sets takes as input a set with |S] and a collection C (C1,..., Cx of subsets of S such that |Ca] 3 for all i S and the goal is to determine whether or not there exists subset of C (denoted C) such that C covers every element in S exactly once.
We will next describe how to map an instance of Exact Cover by 3-Sets to an instance of a decision version of our problem. Specifically, we will consider the problem where we given N and and must decide whether there exists subset K S N of size 7 7/3 3 that satisfies e-general proportionality.
Suppose we have an instance of Exact Cover by 3-Sets (S, C) Let e = & and let = {G.)sEs for G. constructed as follows. We will construct G, so that |G,| = 2x for all É S. We will further maintain that for every C₁, we have E G, for all 8 C2 and that every >> appears at most two groups G.,
We formally construct G in Algorithm 6.
Algorithm 6 Constructing G
Input: S, C {Ciheesl
2: G, f {i:s Ct) for all S
3: i
4: while S:: [G.|
< 2k do
5: i-i+1
6:
if there is exactly
S such that [Gs| 2x then 8 + SEN 5 such that |G,| < 2k
7:
8: Add it
9:
else
two $1 two distinct values of such that [G,] 2x
11: Add to G.,
Add to G., end if
13:
14:
end while
15:
Return G = (G.).Es
Note that the counter i never exceeds kT. To see this, observe that the max value of i is equal
K + E.es (2k fi: f C.)
= K +
TK 2
Σ
Hi:se C.H.
2
x
TK +
Σ
11:8EC.
BES
TK + K [1.5k]]
S тK.
Therefore, we choose = [KT] so that G, C N as required.
By construction, also have that |Gal 2x for all G, G, for all G, gg
G2
2x
N
KT
We now show that the Exact Cover by 3-Sets instance has a solution if and only if there exists a K with ||| S T/3 which satisfies c-general proportionality for our instance. Suppose the Exact Cover by 3-Sets has solution č C. Then ( = r/3. Define the set K == {i C, E č}. This K must cover every e S exactly once, which by construction of G, means this K covers every G, e G
30

---

exactly once. Therefore, we have that |KnG,
1
for all s. This satisfies
[K]
[K]
K
[G
1
[N]
so K satisfics 1/r-general proportionality.
To show the other direction, suppose we have a set K with size |K] 7/3 that satisfies 1/r-general proportionality. Because we chose c _T2 and every G2 satisfies |G,l/N = 2/T, we must have that G. n K| 2 for all 8. However, we also know that by construction, any E N covers at most three groups G.. This implies that we must have | > 7/3. Since by assumption |K| S T/33, we therefore must have that |K| - T/3. Furthermore, the only elements N that cover groups in G the elements
[xc]. Therefore, if K r/3 and K includes at least one of every group in G, we must have that K S [r]. Finally, combining the facts that every element of K covers exactly three groups, [K] = 7 7/3, the number of groups is т, and every group is covered at least once by K, must have that every group is covered exactly once by K.
Therefore, we can conclude that Č = {C; i E K3 must be a solution to the Exact Cover by 3-Sets problem as desired.
L More Details on Empirical Case Studies
Table 3 summarizes the parameters for each case study.
Case study
n m lt for existing subset
BIG-bench HELM
14112 120
24
34 67
Cal Hospital Compare
50 282
12
Table 3: Summary of case study parameters.
L.1 Case Study Descriptions and Datasets We describe each case study in more detail below.
Case Study 1: BIG-bench [Srivastava et al., 2022]. We consider the problem of selecting tasks to include in "Lite" version of BIG-bench. The BIG-bench repository already includes such a subset of tasks called BIG-bench LITE, which includes 24 tasks. BIG-bench in general includes both JSON tasks and programmatic tasks, where JSON tasks are more lightweight evaluate. Their existing LITE benchmark includes only JSON tasks for ease of evaluation. Thus, for the purposes this case study, we consider the problem of selecting subset of the JSON tasks to go in LITE benchmark. Intuitively, one might want to select the LITE tasks to be representative in some sense of the rest of the JSON tasks, since all tasks are included in the published leaderboards.
Alternatives: The BIG-bench repository includes evaluations on its JSON tasks for LLMs different sizes from three model families: "Big-G", "Big-G sparse", and "GPT", For each individual model, they also include 0-shot, 1-shot, 2-shot, and 3-shot evaluations. For simplicity, we treat each model and each shot count a separate alternative be ranked. Thus, we end up with = 120 alternatives.
Full set: The full set of tasks we consider consists of n 141 JSON tasks, after filtering to include only the tasks which were evaluated for all alternatives. We consider only JSON tasks in the full set as the existing BIG-bench LITE only includes JSON tasks for case evaluation. The list of all tasks is included in the code in the Supplementary Materials. The metric used was always the preferred_score field per task.
Existing subset: We compare to the existing BIG-bench LITE (BBL) set of tasks, which includes = 24 JSON tasks as of February, 2025. The list of these tasks is included in the code in the Supplemenary Materials and also available at https: / github.. com/ cww/ htt/goooleeeBee Booogle/BIG-bae BBeIGGBennchhblbh main/bigbench wwwpchhheenhhhaaheeeeeme tasks wwwtkskkkkkkksssseee. toskkss md#big- benggebench-hhh lite.
Datasel: Data was accessed using the Big-bench API available at https:: //t/t//ttttt/ttt com/ g bench Code for processing this data is included with the Supplementary Materials. Usage is in compliance with the Apache License, Version 2.0.
31

---

Case Study 2: HELM [Liang et al., 2022]. HELM Classic is another evaluation platform that ranks LLMs based on multiple scenarios and metries. We consider the problem of selecting a subset of scenarios which is in some sense "representative" of the full set. HELM Lite is an existing variant which includes significantly fewer scenarios than HELM Classic. Note that it is not directly stated that HELM Lite is meant to be representative of HELM Classic (which includes both Core scenarios and other evaluations), but we make this assumption for the purposes of this illustration.
Alternatives: We consider m 67 models that appeared on the HELM Classic leaderboard as of February, 2025.
Full set: The full set of tasks we consider consists of the accuracy metrics for n. = 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 in the Supplementary Materials.
Existing subset: Not all tasks from HELM Lite were included in the HELM Classic leaderboard, and not all models on the HELM Classic leaderboard were evaluated on the HELM Lite leaderboard. Thus, as our existing subset baseline, we selected the subset of HELM Classic scenarios which were also included as HELM Lite scenarios.
This yielded set of k = 7 scenarios, which included: NarrativeQA, NaturalQuestions (open-book), Natural QuestroQQuesions (closed-book) OpenbookQA, MMLU (Massive Multitask Language Understand- ing), MATH, and GSM8K (Grade School Math).
Dataset:
Data was downloaded as HTML tables February, 2025 from the following links:
scenarios
wtt.:/stttaoo...deeeeeeeeee evaluations
//crfm.
http://tt..aaaaaaa/////////////a scenarios
Leaderboard data can also be accessed at accuracy metrics were considered. Code for processing this data is included with the Supplemental Materials. Usage is in compliance with the Apache License, Version 2.0.
cctm//ttaaffrdcrrf//eeeee/eeeeee Only
Case Study 3: Cal Hospital Compare [Cal Hospital Compare, 2025]. Finally, we demonstrate how our methods can apply in evaluation settings beyond LLMs by considering the problem of hospital quality evaluation. Cal Hospital Compare is a platform that awards a "patient safety honor roll" status to hospitals in California that perform particularly well
set of quality measures collected from the Centers for Medicare and Medicaid Services (CMS). The honor roll selection procedure considers 12 hospital quality measures drawn from the CMS Hospital Compare database, which collects hundreds of measures from hospitals throughout the US. A continuing challenge is selecting these 12 quality measures, which Cal Hospital Compare identifies as a "an 18-month, multistakeholder process of rigorously evaluating existing national patient safety measures." n4 For the purposes of this illustration, we consider the problem of selecting a set of quality measures which is "representative" of existing patient safety measures available in the CMS Hospital Compare database. According to the "algorithmic approach," Cal Hospital Compare awards honor roll status to eligible hospitals "wiith two-thirds of their measures above the 50th percentile of good performance (and none below the 10th percentile)."
Alternatives:
We consider m 282 hospitals in California which were eligible for algorithmic evaluation according the criteria specified by Cal Hospital Compare. Specifically, they had scores for least 6 of the currently selected 12 measures.
Full set: We consider a full set of n = 50 patient safety measures available through CMS Hospital Compare. These were selected to include only the measures that were directly related to the categories from which the original 12 measures were selected, so as not to include measures unrelated to patient safety. A full list of these measures is included in the code submission. is possible that some
'nttps: httpp::/cclhooppttalcopprr wwwp:/aaooccmmppooooooooee/ wwtp/spooooeeeettupppooooooooeae Patient- Saantt-Saatty--onntee
List_ Cal Cal-Hospital-
Seasppttal-Cmppreeeeeee Compare 2025-202222112002 1.
32

---

important measures were missed in this illustration, and any real practical application should bring in additional domain expertise carefully tailor the full set precise practical goals.
Existing subset: We compare against the existing k = 12 measures currently used by Cal Hospital Compare for their patient safety honor roll. A full list of these measures is shown in Figure 3.
Domain
Source
Measurement Period 1/1/2023 12/31/2023
Healthcare Associated
CMS Hospital Compare
Infections
(based on unnormalized HAl data)
CLABSI
CAUTI
Colon Surgery
MRSA
CDI
AHRQ PSI 90
CMS Hospital Compare
7/1/2021 - 6/30/2023
Sepsis Management
CMS Hospital Compare
1/1/2023 12/31/2023
Patient Experience HCAHPS
CMS Hospital Compare
1/1/2023 12/31/2023
Score
Nurses always
communicated well
Doctors always
communicated well
Always received help as soon as wanted
Staff always explained about
medicines
Patients understood their when they left the hospital
Hospital Letter Grade
Leapfrog Hospital Safety Grades
Average GPA from the last three reporting periods (Fall 2023, Spring 2024, Fall 2024)
Figure 3: Table of Patient Safety Honor Roll Measures published by Cal Hospital Com- pare attpe://aalhopppaalloopaa Patient- -attt---Saaett-ooo--oollllo
/ttps//2000/////aaattseeet. _allt___llaa_ Seatt_CClHHossite Compare ettpparree222---eee 1. pdf). As our "exist- ing subset", consider the of k 12 measures selected from CMS Hospital Compare.
Datasel: Data was downloaded as CSV files in February, 2025 from the CMS Hospital Compare provider data repository (https://data cms gov/proviidrr-ata// full directory of all avail- able datasets can be found at posttss//dattee cms data- diiirraat.......mmmomooooaaaaarr The specific datasets used were:
data/ dataset//gmm aat:3
HCAHPS-Hospitaal.c
Materrall,Keallth-Hooppttt.
[aiannedHoosptta____ Hossittll_.iiitsss Visits stt.iiiisstt-ttitalllll csv
This data is part of the public domain. Code to aggregate and process these datasets is included with the Supplemental Materials.
L.2 Integer program computation
Integer programs were solved using CPLEX. A maximum solve time of 10 minutes was set for each integer program. Thus. it is possible that the integer programming solutions were suboptimal when this limit was reached. This limit was only reached on BIG-bench.
All experiments were run MacBook Pro with an Intel Core i7.
33


Reviews:
[{"review_id": "YX8cPhkdXa", "reviewer": "Reviewer_8Kid", "summary": "This paper tackles the problem of selecting a representative subset of evaluation metrics from a larger set, particularly in settings like LLM or hospital quality evaluations. The authors formalize two new concepts -- positional representation and positional proportionality-- inspired by social choice theory. They derive tight upper/lower bounds, prove NP-hardness, and propose practical algorithms for subset selection. Their approach is validated via three real-world case studies: BIG-bench, HELM, and Cal Hospital Compare.", "questions": "1. Incorporating metric importance or cost.\n\nHow would the framework extend to settings where metrics have differing levels of importance, quality, or computational cost?\n\n2. Integrating other constraints.\n\nCan fairness, diversity, or cost-sensitive constraints be integrated into the subset selection procedure (e.g., ensuring representation across language groups or domains)?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "## Strengths\n1. Quality: Strong theoretical analysis with tight bounds and clear proofs; algorithms are sound and practically applicable.\n2. Originality: Introduces novel formalizations of metric representativeness based on social choice theory—fresh perspective in benchmarking.\n3. Significance: Addresses a real need in scalable, interpretable benchmark design; applicable to various domains.\n4. Clarity: Generally well-written and organized, with intuitive examples and thoughtful discussion.\n\n## Weaknesses\n1. Bias inheritance from full metric set: The method assumes the full set of metrics is well-balanced. If the original set is biased or overrepresents certain aspects, the selected subset will likely reflect those biases as well.\n2. Limited robustness to distribution shift: While the subset can be efficiently recomputed, it may still fail to generalize well when evaluating substantially different or unseen alternatives. In such cases, user intervention (e.g., choosing new values for g or \\epsilon) may be needed repeatedly.\n3. Scalability of IP: Integer programming guarantees optimal subsets but may become infeasible in large-scale settings with hundreds or thousands of metrics.\n4. Assumption of complete rankings: The framework assumes that all metrics provide complete rankings over alternatives, which is not always true in real-world LLM evaluations where missing data is common.", "was_revised": false, "final_justification": "", "rebuttal": "> *How would the framework extend to settings where metrics have differing levels of importance, quality, or computational cost?*\n\nThis is a great question, and our results can in some cases incorporate these additional aspects. Suppose that instead of caring about the size of the subset of metrics, we instead have a computational cost for each metric, and our goal is to keep the total computational cost below some threshold. In this case, a user could easily modify the integer programs in Appendix A to include weights in the objective function. For a more computationally efficient solution, you could also run the greedy algorithm and select the set that gives the lowest cost per new color (this mimics the greedy algorithm for the weighted set cover problem). This algorithm would run in polynomial time, and give a $\\log(mn/g)$ approximation to the optimal. However, depending on the costs of the benchmarks, there no longer exists a nice guarantee for the total cost of $K$ as in Theorem 3. We are happy to include further discussion of this in the final version of the paper.\n\nIf there is an importance weighting of benchmarks then we functionally have two objectives: minimizing the size of $K$ and maximizing the sum of importance weights. Our results do not directly generalize to this multi-objective setting — this is an interesting question for future work.\n\n> *Can fairness, diversity, or cost-sensitive constraints be integrated into the subset selection procedure (e.g., ensuring representation across language groups or domains)?*\n\nYes! Using the generalized properties defined in Section 4, a user can use our subset selection procedure for any general form of representation. As in your example, we could choose the collection of groups $\\mathcal{G}$ to include groups of different languages, in which case any set $K$ satisfying generalized representation/proportionality will ensure repesentation for every language. Similarly, if we choose $\\mathcal{G}$ to include sets of benchmarks from different domains, then these properties guarantee representation for these groups. See Lines 293-298 for some explicit examples of how we can use these general properties. All of the results from Sections 2 and 3 generalize to this broader setting, which we show rigorously in Appendix B."}, {"review_id": "4HqPos3qkR", "reviewer": "Reviewer_GiFD", "summary": "This paper introduces and studies the problem of finding a small representative set of metrics $K$ from a larger set of metrics $N$ specified by the user. The goal is for $K$ to be a ``good approximation’’ of $N$. Drawing on ideas from computational social choice, the authors formalize two notions of “representativeness” for $K\\subseteq N$. The first notion – positional representation – requires that for every rank cutoff $r$ and alternative $a$, if at least $g\\ell$ of the $n$ metrics rank $a$ in the top $r$, then at least $\\ell$ metrics in $K$ must do so too. The second notion, positional proportionality, extends this to a two-sided requirement. The authors also extend both notions to. The authors also extend both notions to The setting where one has to be representative of different subsets of metrics $G_1, G_2,\\dots\\subseteqq N$.\n\nFor the first notion, the paper shows that a lower bound on the size of the selected set K and an efficient algorithm that matches this size up to a logarithmic factor. For the second notion, the paper provides lower and upper bounds on the size of the select set of metrics required, and matches it where the lower and upper bounds match up to constant factors. \n\nThere seems to be an interesting fundamental problem in social choice theory that has not received much attention, to the best of my knowledge. The authors claim that this also has applications in evaluating LLMs.", "questions": "In the paper, different notions of positional representation typically look at item-wise guarantees. Is it possible to extend the techniques in this work when we require, for instance, pairs of items to be treated similarly by the sub-small subset of metrics selected and the large input subset of metrics? \n\nSince the notions of representation studied in this work assume that the underlying metrics output a ranking, I think they cannot directly be applied to metrics which output scores for individuals, such as Borda. Can the authors comment on extensions to such score-based voting rules?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper introduces an interesting problem in social choice theory and provides clean theoretical results for it.   \n2. The paper is well-written and easy to follow.   \n3. The paper evaluates its proposed solutions using carefully designed empirical studies.\n\nWeaknesses:\n\n1. While the authors chiefly motivate their problem through its applications in LLM evaluation, I think its application is weak. And instead of focusing on the fundamental nature of the problem might make the paper more grounded and interesting.", "was_revised": true, "final_justification": "I keep my initial score as I think the paper studies an interesting question. I still believe that it would be nicer to present the fundamental question directly without delving too much into the connection to LLMs, which seems weak. I thank the authors for answering the questions I raised.", "rebuttal": "> *In the paper, different notions of positional representation typically look at item-wise guarantees. Is it possible to extend the techniques in this work when we require, for instance, pairs of items to be treated similarly by the sub-small subset of metrics selected and the large input subset of metrics?*\n\nThis is an interesting question, and the answer depends on what you mean by \"treated similarly\" for a pair of items. For example, suppose we have alternatives $a$ and $b$ that are 'clones' of each other so they are ranked adjacent to each other in every benchmark. Then positional proporionality immediately guarantees that the fraction of time $a$ and $b$ are ranked at position $r$ in the subset $K$ will be within $2\\epsilon$ for every $r$. The same will approximately hold even if $a$ and $b$ aren't perfect clones of each other and are only approximate clones of each other. Now if we want to guarantee that $a$ and $b$ have a similar representation in $K$ when $a$ and $b$ have very different rankings in $N$, then that becomes much more difficult. In fact, $a$ and $b$ having similar representation in $K$ while having different representation in $N$ would directly contradict our notions of position proportionality and position representation. Therefore, such a guarantee would not be compatible with our notions of fair representation.\n\n> *Since the notions of representation studied in this work assume that the underlying metrics output a ranking, I think they cannot directly be applied to metrics which output scores for individuals, such as Borda. Can the authors comment on extensions to such score-based voting rules?*\n\nAny metric that outputs scores for individuals can be directly converted to a ranking (by score), in which case the notions of representation studied in this work can be directly applied. That being said, doing this effectively \"throws away\" any information in the scores for a metric. Another option is, if a metric involves a Borda count generated from a bunch of submetrics, then we can instead guarantee positional representation/proportionality with respect to the entire set of submetrics.\n\nWe do also have results in our paper for score-based aggregation rules of benchmarks; see Theorem 7, which informally says that if $K$ satisfies position proportionality, then any scoring rule (e.g. Borda) evaluated on $K$ will be a good approximation for the same score-based rule evaluated on $N$."}, {"review_id": "aN8NyBZHBV", "reviewer": "Reviewer_KYHN", "summary": "This paper addresses the problem of selecting a \"representative\" subset of metrics from a full suite for efficient evaluation, particularly in contexts like LLM assessment and hospital quality evaluation, where using all metrics is computationally expensive or hard to interpret. Key contributions include:  \n1. Formalizing two notions of representation: Positional representation ensures every alternative is sufficiently represented at each rank cutoff, parameterized by a group size $ g $; positional proportionality guarantees no alternative is over- or under-represented by more than an additive error $ \\epsilon $ at any position.  \n2. Theoretical bounds: For positional representation, tight (up to logarithmic factors) upper and lower bounds on the minimum number of metrics needed are established, with a polynomial-time greedy algorithm achieving the upper bound. For positional proportionality, tight (up to constants) bounds are provided, and it is shown to approximate social choice scoring rules.  \n3. Generalizations: Extending both properties to handle pre-defined groups of metrics, with proofs that finding the smallest satisfying subset is NP-hard, while bounds from the base cases extend to these generalizations.  \n4. Empirical validation: Case studies on BIG-bench, HELM, and hospital quality evaluation demonstrate that the proposed methods outperform existing \"lite\" subsets in efficiency while maintaining representativeness, and can augment existing subsets to improve performance.", "questions": "1. The paper highlights the lack of a formal definition for \"representativeness\" in metric subset selection, while existing lite benchmarks (e.g., BIG-bench Lite, HELM Lite) rely on manual curation. What specific flaws in representativeness do these existing subsets exhibit? For example, are there systematic under-representations of certain alternatives? Does the paper quantify these flaws using empirical data?  \n2. The paper draws parallels between LLM evaluation and hospital quality assessment as scenarios requiring representative metric subsets. However, LLM metrics and hospital metrics differ significantly in semantics, distribution, and evaluation goals. How does the paper justify generalizing the proposed framework across such diverse domains? Are adjustments to parameters (e.g., $g$ or $\\epsilon$) needed for domain-specific contexts?  \n3. Positional Representation requires that if an alternative $a$ is ranked in the top $r^2$ positions by $\\ell \\cdot g$ metrics in $N$, it must be ranked in the top $r$ positions by at least $\\ell$ metrics in $K$. Why is $r^2$ chosen as the positional mapping? Is this choice theoretically validated or empirically tested? How would switching to a linear relationship $r$ affect the theoretical bounds (upper and lower)?  \n4. The paper claims that Positional Proportionality approximates any social choice scoring rule with an error bounded by $\\epsilon$. However, scoring rules weight ranks differently, Borda assigns higher weights to top positions. How does Positional Proportionality adapt to such weight variations? Are there scoring rules that cannot be effectively approximated?  \n5. The greedy algorithm for Positional Representation Alg 1 uses a \"coloring\" step where every $g$ uncolored instances of an alternative are labeled with the same color. What is the rationale for this coloring strategy? Could alternative strategies, e.g., grouping by rank positions, yield better subsets?  \n6. Positional Proportionality uses an additive error $\\epsilon$, with bounds scaling with $1/\\epsilon^2 \\log(m)$. Why is additive error preferred over multiplicative error? In domains like hospital quality assessment, relative errors in metric proportions may be more critical—does the framework need extension to support multiplicative error?  \n7. The paper notes that Positional Representation and Positional Proportionality are \"mutually non-implied,\" with examples showing Positional Proportionality can be more efficient, e.g., $|K|=1$ when all metrics agree. However, in scenarios with highly conflicting rankings, which property better ensures representativeness? Can experimental data compare their applicability?  \n8. Figure 1 shows \"minimum $g$ for existing subsets\", but the calculation method is unclear. How is the smallest $g$ for which an existing subset satisfies Positional Representation determined? Does this account for biases in manual curation?  \n9. In the hospital quality case study, adding <5 metrics to the existing 12 significantly reduces $\\epsilon$. What criteria guided the selection of these additional metrics? Was domain knowledge incorporated? Would results remain robust if selection were fully algorithmic?", "limitations": "Refer to Questions", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Refer to Questions", "was_revised": true, "final_justification": "Thank you for addressing my concerns, and I will raise my score accordingly.", "rebuttal": "We thank the reviewer for the detailed list of questions. Some of these questions seem to stem from misunderstandings or are already addressed in the paper, as we explain below. \n\n> *1. The paper highlights the lack of a formal definition for \"representativeness\" in metric subset selection, while existing lite benchmarks [...] rely on manual curation. What specific flaws in representativeness do these existing subsets exhibit? For example, are there systematic under-representations of certain alternatives? Does the paper quantify these flaws using empirical data?*\n\nGiven the lack of existing formalism for representation of metrics, our paper serves three purposes: with our new formalism, (1) there now exists a quantitative method to check to what degree existing manually curated metrics are representative, and (2) if not representative enough, an algorithmic intervention to add new metrics to improve representation. Additionally, in domains where existing manually curated “lite” metric subsets don’t exist, (3) our algorithm can propose a subset of metrics from scratch that can serve as a base to seed additional manual curation from domain experts, thus saving human hours.\n\nRegarding existing manually curated metrics: we indeed demonstrate empirically that existing manually curated metrics may not be representative by the definitions we provided, depending on the tolerance for error. The dashed lines in Figures 1 and 2 show the minimum group size $g$ and tolerance $\\epsilon$ for which the manually curated subsets satisfy the representation definition. For any $g$ and $\\epsilon$ lower than that, the manually curated sets would not be representative.\n\nWe also show that it’s possible to significantly improve representation by adding relatively few additional metrics using our proposed algorithms: for example, Figure 2 shows that on the HELM dataset, $\\epsilon$ can be halved by adding four metrics to the existing manually curated lite set.\n\n> *2. The paper draws parallels between LLM evaluation and hospital quality assessment [...]. However, LLM metrics and hospital metrics differ significantly in semantics, distribution, and evaluation goals. How does the paper justify generalizing the proposed framework across such diverse domains? Are adjustments to parameters (e.g.,  or ) needed for domain-specific contexts?*\n\nThe core evaluation goals are actually quite similar between public LLM evaluation platforms and the hospital honor roll: the evaluator wants to reward and encourage good performance, and the evaluator wants the evaluations to be useful in some sense to stakeholders, like users or patients. Of course, how “strict” a notion of representation an evaluator needs absolutely depends on the specific application, and the parameters $g$ or $\\epsilon$ must be chosen by the evaluator to reflect this. It’s possible that stricter representation is more important in the healthcare domain: if $\\epsilon$ is not low enough, a high-performing hospital might not make it onto the honor roll, and a hospital might get on the honor roll that actually doesn’t perform well. Whether one would use PR or PP also depends on the domain: with LLMs leaderboards, PR might be enough to ensure that LLMs that are good across a variety of tasks are ranked highly in the lite benchmark set. On the other hand, PP might be important in healthcare to ensure that one can identify hospitals that perform poorly using the lite metric set. To summarize, our framework and results provide sufficient flexibility to apply to diverse domains. \n\n> *3. Positional Representation requires that if an alternative is ranked in the top $r^2$ positions by $\\ell \\cdot g$ metrics in N, it must be ranked in the top positions by at least  metrics $\\ell$ in $K$. Why is  chosen as the positional mapping? Is this choice theoretically validated or empirically tested? How would switching to a linear relationship affect the theoretical bounds (upper and lower)?*\n\nPositional Representation as defined in Definition 1 says that if an alternative is ranked in the top $r$ positions by $\\ell \\cdot g$ metrics in $N$, then it must be ranked in the top $r$ positions by at least $\\ell$ metrics in $K$. This is already a linear relationship (and we don't believe we use $r^2$ anywhere in the paper). A linear relationship is conceptually natural because it guarantees *proportional* representation for every position. Finally, we prove (Theorems 2 and 3) that the linear relationship is (almost) tight, so in this sense the choice is indeed \"theoretically validated.\" \n\n> *4. The paper claims that Positional Proportionality approximates any social choice scoring rule with an error bounded by $\\epsilon$. However, scoring rules weight ranks differently, Borda assigns higher weights to top positions. How does Positional Proportionality adapt to such weight variations? Are there scoring rules that cannot be effectively approximated?*\n\nTheorem 7 states that positional proportionality guarantees an additive approximation of the scores of every normalized scoring rule. Informally, this means that for any alternative, that alternative's *score* when evaluating the scoring rule on $N$ is within $\\epsilon$ of that alternative's *score* when evaluating the scoring rule on just $K$. Therefore, every normalized scoring rule (including Borda) can be approximated, no matter how the scoring rule  weights the ranks.\n\n\n> *5. The greedy algorithm for Positional Representation Alg 1 uses a \"coloring\" step[...]. What is the rationale for this coloring strategy? Could alternative strategies, e.g., grouping by rank positions, yield better subsets?*\n\nThe greedy algorithm is guaranteed to return a subset $K$ that satisfies positional representation as shown in Theorem 3, and by Theorem 2 this is within a logarithmic factor of being optimal. Therefore, no other algorithm can in the worst-case yield better subsets than Algorithm 1. The coloring approach is motivated by the greedy algorithm for set cover in theoretical computer science, which solves a related problem and gives strong approximation guarantees.\n\n> *6. Positional Proportionality uses an additive error $\\epsilon$,[...]. Why is additive error preferred over multiplicative error? In domains like hospital quality assessment, relative errors in metric proportions may be more critical—does the framework need extension to support multiplicative error?*\n\nIf we were to require a multiplicative factor of approximation, then there exist instances of the problem where no subsets of $N$ except for $N$ itself actually satisfy the property for any $\\epsilon \\le 1$. Formally, suppose we want that $|\\frac{C(N,r,a)}{|N|} - \\frac{C(K,r,a)}{|N|}| \\le \\epsilon \\frac{C(N,r,a)}{|N|}$. Then suppose we have that $n = m$ and that every alternative is ranked first by exactly one benchmark. In order to satisfy the multiplicative property described above, we must have that each alternative is ranked first by at least one benchmark in $K$, which requires that $K = N$. This example shows that a multiplicative form of PP is too strong of a requirement.\n\n> *7. The paper notes that Positional Representation and Positional Proportionality are \"mutually non-implied,\"[...]. However, in scenarios with highly conflicting rankings, which property better ensures representativeness? Can experimental data compare their applicability?*\n\nFor this problem, there is no notion of \"better\" representativeness. Positional representation and positional proportionality are two *different types* of representativeness, each with different interpretations and theoretical guarantees described in the paper. In Figures 1 and 2, we have experimental results on the same data sets for both notions of fairness, but in the end it is up to a user to decide which is the form of representativeness they desire.\n\n> *8. Figure 1 shows \"minimum  for existing subsets\", but the calculation method is unclear. How is the smallest  for which an existing subset satisfies Positional Representation determined? Does this account for biases in manual curation?*\n\nFor a given existing subset of metrics $K$ (e.g. $K =$ the existing BIG-bench Lite metrics), the “minimum $g$ for the existing subset” plotted in Figure 1 is the minimum group size $g$ such that Definition 1 is satisfied. That is, we plot $\\min\\{g : \\forall r \\in [1:m], \\forall a \\in A, C(K,r,a) \\ge \\left \\lfloor \\frac{C(N,r,a)}{g} \\right \\rfloor\\}$. Code for calculating this is included with the code submission, and is simply done by binary search over $g$. Any biases in manual curation will be reflected in the resulting minimum value of $g$: a more “biased” manual curation (relative to the existing PR definition) will end up with a higher minimum value of $g$.\n\n> *9. What criteria guided the selection of [the additional metrics in the hospital quality case study]? Was domain knowledge incorporated? Would results remain robust if selection were fully algorithmic?*\n\nThe additional metrics were selected by solving the following optimization problem: What is the minimal set of additional metrics that can be added to the existing 12 metrics such that PP or PR is satisfied for each given value of $g$ or $\\epsilon$? This is solved using the same algorithms proposed (Algorithm 1 and integer programming).\n\nThe algorithmic selection of these additional metrics can be seen as a hybrid approach that uses our algorithms to augment domain knowledge rather than replace existing human metric selection processes. We emphasize that we *do not* argue that human curation should be replaced, but rather that our algorithm and formalism can be an effective tool to *support* domain experts. A comparison to fully algorithmic selection is also included in Figures 1 and 2, which we show is able to achieve stricter representation using fewer metrics. This fully algorithmic selection can be used to create a starting point for a Lite metric set from which human domain experts can build."}]

Author rebuttal:

Meta-review: This paper focuses on the problem of selecting representative subsets of evaluation metrics from larger suites, with applications in LLM evaluation and hospital quality assessment. It introduces two novel notions—positional representation and positional proportionality—grounded in social choice theory, and provides tight theoretical bounds, efficient algorithms, and validation through real-world case studies on BIG-bench, HELM, and Cal Hospital Compare.

The paper is generally well-executed and offers several notable strengths. 

-  It provides strong theoretical analysis with tight bounds and rigorous proofs. 
-  It introduces novel definitions of representativeness inspired by social choice theory, bringing a fresh perspective to benchmark design. 
-  The proposed methods address a practical need for scalable, interpretable evaluation across domains. 

After the rebuttal, most of the reviewers' concerns were adequately resolved. The authors clarified how the framework can incorporate importance weights, costs, fairness constraints, and generalization across domains, while also addressing reviewer questions about representativeness in existing curated subsets. Reviewers confirmed that their concerns were largely addressed.

Overall, I recommend accept. The paper is technically solid and makes both theoretical and applied contributions. For the final version, the authors should incorporate reviewer suggestions, especially clarifying domain-specific applicability and robustness to potential biases in the full metric set.
Decision: Accept (poster)