acceptodds
Under review as a conference paper at ICLR 2027

Beyond Scalar Leaderboards: Adaptive Sampling for Pareto Frontier Identification in Multi-Objective LLM Arenas

Abstract

The evaluation of large language models (LLMs) is inherently multi-objective, as different models may offer different tradeoffs across performance dimensions such as math, code, and writing. Because such evaluations are often based on costly and time-consuming human feedback, it is important to draw reliable conclusions using as few comparisons as possible. In this paper, we present \em Vector-Borda Empirical-Gap Elimination (VB-EGE), a fixed-confidence adaptive sampling algorithm for efficiently identifying models on the Pareto frontier in arena-style evaluation, where each comparison evaluates a pair of models on a prompt with respect to a selected performance dimension. VB-EGE progressively eliminates models from an active set once sufficient statistical evidence has been accumulated to certify their Pareto status. Under a multi-objective Bradley–Terry model, we show that VB-EGE returns the correct Pareto frontier with high probability and derive an instance-dependent upper bound on its sample complexity. We further establish a worst-case lower bound showing that VB-EGE is minimax-optimal up to logarithmic factors. Simulations and experiments on three real-world Arena datasets (Arena, SearchArena, and VisionArena) demonstrate VB-EGE's empirical effectiveness.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
LLM evaluation, chatbot Arena, Pareto frontier, adaptive sampling, bandits theory

Reviews

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

This paper studies how to identify Pareto-optimal large language models using pairwise human preference comparisons across multiple objectives. The authors propose Vector-Borda Empirical-Gap Elimination (VB-EGE), an adaptive sampling method that estimates a Borda score for each model and objective and gradually removes models whose Pareto status can be determined. The paper shows that the Borda scores preserve the Pareto frontier under the Bradley–Terry model. It also provides theoretical guarantees on the correctness and sample complexity of the proposed method. Experiments on synthetic problems and three Arena datasets show that VB-EGE requires fewer comparisons than the uniform sampling baselines.

Critical strengths
  1. The paper addresses a useful problem in LLM evaluation. Instead of ranking models using a single score, it identifies the Pareto frontier across different abilities, allowing models with different strengths to be considered.
  2. The paper provides theoretical guarantees for the proposed method. The authors prove that vector-Borda scores preserve the Pareto frontier and establish bounds on the sample complexity of the algorithm.
Critical weaknesses
  1. The paper aims to reduce the cost of LLM evaluation, but it does not compare the proposed approach with direct benchmark evaluation. For tasks such as mathematics and coding, model performance can be measured directly without repeated pairwise comparisons. It is unclear whether the proposed method is more cost-effective in these cases, or when pairwise comparisons would be preferable.
  2. The adaptive sampling strategy is limited. The method samples every active model on every objective and selects opponents uniformly at random. It does not adaptively select the most informative model pairs or objectives, which may require unnecessary comparisons.
  3. The method relies on uniform opponent sampling, even for models that have already been eliminated. Although this keeps the Borda scores consistent, it is unclear how much this affects sampling efficiency.
  4. The paper uses strict Pareto dominance rather than standard Pareto dominance. It is unclear how this choice affects the identified Pareto frontier, particularly when models have similar performance on some objectives.
  5. All three main baselines use uniform sampling. The paper would benefit from comparisons with other adaptive sampling methods to better demonstrate the advantages of VB-EGE.
  6. The real-world experiments sample from existing Arena comparison records rather than collect new human preferences. It is unclear whether the reported improvements would also hold in an online evaluation setting.
Questions for authors
  1. For tasks such as mathematics and coding, model performance can be measured directly using existing benchmarks. How does the evaluation cost of the proposed method compare with direct benchmark evaluation? In what situations would repeated pairwise comparisons be more cost-effective?
  2. The method samples every active model on every objective and selects opponents randomly. Why not adaptively select more informative model pairs and objectives? Could this reduce the number of comparisons?
  3. The paper uses strict Pareto dominance rather than standard Pareto dominance. Have the authors considered epsilon-dominance to handle models with similar performance? How would different dominance definitions affect the identified Pareto frontier?
  4. What is new in VB-EGE compared with existing Empirical-Gap Elimination methods, apart from using Borda scores?
  5. Why are the main experiments limited to uniform sampling baselines? How does VB-EGE compare with other adaptive sampling methods?
  6. The real-world experiments only retain model subsets where every pair has comparison records for every objective. How would the method perform with sparse or incomplete comparison data, which are common in real Arena settings?
3 comments

Response to Reviewer 254S

We thank the reviewer for the questions on evaluation scope, adaptivity, and dominance definitions, and address each point below.

Questions

Q1: Direct benchmarks and pairwise evaluation.

  • Direct benchmarks and preference-based evaluation address complementary objectives. In some mathematics or coding tasks, there exists automated grading systems that can objectively assess the correctness of the output. Human preferences may, however, additionally reflect clarity, helpfulness, and style. Our goal is to design a method to reduce the comparisons needed to identify the preference-defined frontier. Pairwise evaluation is particularly useful when the intended criterion lacks a reliable automated score or when existing human judgments are available. A direct cost comparison with benchmarks is meaningful when both approaches measure the same objective.

Q2: Adaptive selection of pairs and objectives.

  • Thank you for the question. We would like to clarify that VB-EGE does adapt its sampling through model elimination: certified models receive no further focal samples, concentrating effort on unresolved models. Given an active model, uniform opponents keep the Borda means fixed and allow observations to be reused across phases. Although we do not rule out further gains from finer pair or objective selection, our work establishes the first approach to this new setting with minimax-optimal sample complexity up to logarithmic factors. The corresponding lower bound applies to algorithms that select arbitrary comparisons adaptively. Also see our answer to Q5, which describes the adaptive BT baseline already included in Appendix E.

Q3: Strict dominance, standard dominance, and ϵ\epsilon-approximation.

  • Thank you for the suggestion. In our setting, strict dominance matches our conservative screening objective: a model is excluded only when another improves every evaluated capability. If a user values a capability on which models are tied, price or speed may guide the choice; standard dominance can discard such an option. Also, choosing ϵ\epsilon is difficult in practice because a difference in Borda scores does not directly tell users how much model performance they would be willing to sacrifice. We therefore retain exact strict identification as the primary target.

  • Handling standard dominance at coordinate ties would require additional assumptions, while ϵ\epsilon-approximation requires a specified tolerance and revised stopping and correctness proofs. We leave these extensions to future work, as they are not necessary for the Pareto frontier identification problem studied here. Related approximate formulations are considered by Auer et al. (2016) (https://proceedings.mlr.press/v51/auer16.html) and Koné et al. (2023) (https://arxiv.org/abs/2307.00424).


Q4: Novelty beyond existing EGE methods.

  • To our knowledge, this is the first fixed-confidence analysis of exact strict Pareto identification from objective-specific Bradley–Terry comparisons. Building on the EGE framework, we establish two technical contributions:
  1. Fixed-confidence stopping with safe elimination. Certifying a model's Pareto status is not sufficient to remove it: other unresolved models may still need it as a domination witness. Building on EGE's witness-preservation argument, we establish confidence-based elimination conditions that preserve these witnesses while ensuring that each model exits once the confidence radius resolves its classification gap. This yields both correctness and an instance-dependent stopping-time bound.
  2. Lower bounds under coupled BT feedback. Changing one latent coordinate affects every comparison involving that model on the corresponding objective, and each query informs both compared models. We construct frontier-changing BT alternatives and account for this shared information under arbitrary adaptive pair and objective selection. A bounded-horizon change-of-measure argument lower-bounds the stopping-time quantile directly, matching the high-probability criterion of our upper bound. The upper and lower bounds match in the worst case up to logarithmic factors.
  • After exploring MLE, pairwise-LCB, and Borda-based designs during our initial development, we selected VB-EGE for the best balance of theoretical guarantees and empirical performance.

Q5: Comparisons beyond uniform sampling.

  • We would like to clarify that Appendix E already includes an adaptive BT comparison: our heuristic extension of the Track-and-Stop method in Goldberger and Rudi (2026), Optimal Top-kk Identification from Pairwise Comparisons (https://arxiv.org/abs/2607.08979), to the Pareto frontier identification case. Our extension fits BT scores across models for each objective and adaptively selects both model pairs and objectives. VB-EGE achieves a lower capped mean comparison count in 27 of the 28 tested settings; please see Appendix E for details. We have not found other directly applicable adaptive baselines in the literature and would welcome references to relevant methods.

Q6: Sparse or incomplete comparison logs.

  • Thank you for the question. Our current method requires a complete query graph for each objective, and the replay experiments accordingly retain model subsets with complete pair coverage. We note that full pair-query access is also assumed by prior works such as Jamieson et al. (2015) (https://arxiv.org/abs/1502.00133) and Goldberger and Rudi (2026) (https://arxiv.org/abs/2607.08979). Exploiting sparse historical graphs would require graph-aware estimation and sampling. Our present contribution focuses on establishing fixed-confidence Pareto identification under full pair-query access, but this is a natural and interesting direction for future work.

Weaknesses

W1: Missing comparison with direct benchmark evaluation.

  • Answer to Q1 explains the complementary roles of direct grading and preference-based evaluation. Our efficiency claim concerns identifying a frontier defined by human preferences; a benchmark cost comparison requires a common evaluation objective.

W2: Limited adaptivity over pairs and objectives.

  • VB-EGE already concentrates focal sampling on unresolved models. Finer allocation may offer further gains; answer to Q2 explains the design and its worst-case guarantee, and answer to Q5 points to the existing adaptive BT comparison.

W3: Sampling opponents that have already been eliminated.

  • Eliminated models stop receiving focal samples but remain possible opponents. This keeps each active model's Borda mean fixed, allowing it to reuse observations from earlier phases. Within the same phase, sampling only active focal models requires fewer comparisons than continuing to sample all models. Focal Borda uses the same opponent distribution and provides a controlled comparison of the benefit from elimination.

W4: Strict rather than standard Pareto dominance.

  • Answer to Q3 explains why strict dominance matches our intended screening criterion. Standard dominance and ϵ\epsilon-approximation require separate treatment and are left as future extensions.

W5: Uniform-sampling baselines.

  • Appendix E already compares against an adaptive BT heuristic, as detailed in answer to Q5. The Focal Borda baseline separately measures the benefit of our adaptive elimination procedure under the same Borda representation and confidence schedule.

W6: Historical logs rather than fresh human feedback.

  • Table 11 shows substantial savings under matched replay conditions: Focal Borda uses 3.96–16.54 times as many comparisons as VB-EGE. Practical evaluation can build on existing feedback, including the over 82 million human votes accumulated by Arena (https://arena.ai/blog/arena-100m-revenue). Online experiments require fresh human judgments, additional funding, and time; we leave this validation to future work.

We hope our responses address your concerns and encourage a more favorable assessment of our paper.


Thank you for the detailed responses and clarifications. I appreciate the authors' efforts. However, some concerns remain:

Sampling efficiency (W2/W3): The method uses uniform opponent sampling, including previously eliminated models. Although this preserves the Borda score definition, its impact on sampling efficiency remains unclear.

Adaptive baselines (W5): I appreciate the comparison in Appendix E. However, the Pareto-specific adaptive BT heuristic uses an approximate stopping rule without a proven correctness guarantee, making the comparison less conclusive. The authors do not sufficiently explain its poor performance, making the comparison less conclusive.

Real-world evaluation (W6): The experiments rely on repeated sampling from existing Arena records. It remains unclear whether the reported efficiency gains would hold when collecting fresh human preferences in an online setting.

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

The paper provides an adaptive sampling algorithm for identifying models on the Pareto frontier in the setting where pairwise comparisons are observed. The authors characterize sample complexity of this algorithm, providing upper and lower bounds. They also show empirical sample complexity on synthetic and real-world data.

Critical strengths

The paper studies an interesting and practical problem. Given a set of models, which may differ in quality on different dimensions (e.g. coding, math, writing, etc.), how do we most efficiently identify the Pareto frontier? This is extremely applicable to LLM leaderboard settings like Arena, where labels are limited and consumers care about a multi-objective tradeoff function.

The theoretical insight to use Borda scores and reason about Bernoulli means (due to the fact that Borda scores are a monotone transform of the BT scores) is nice. The paper uses this to provide theoretical characterization of sample complexity of the proposed algorithm in a reasonably comprehensive manner.

The empirics demonstrate the usefulness of the proposed algorithm in reducing stopping time on synthetic and real-world datasets.

Critical weaknesses

The main theorem portion (Section 3) is difficult to parse and would benefit from cleaner notation. The description of the algorithm is also notation heavy and hard to interpret. Both sections would benefit from added explanations to better inform the reader on how to interpret and understand the high-level ideas without getting bogged down in a plethora of constants.

In my understanding of the proposed algorithm, the pairwise comparisons only are used to estimate each model's borda score (per objective). This doesn't allow for any joint fitting across models or objectives. In standard BT, the models are jointly fit on the pairwise data. In multi-objective BT, this is essentially fitting a BT model per objective (assuming no correlation of the model's ability across objectives). I'm curious if this joint fitting approach is sample efficient compared to the proposed VB-EGE approach. The empirics compare to uniform sampling BT-MLE, but I would like to see the comparison vs an adaptive sampling BT-MLE baseline. Additionally, one could also add in latent model factors that account for model ability being correlated across objectives, which could further reduce sample complexity.

In general, the empirical results use BT-MLE and Borda score uniform sampling algorithms as the baselines, which seem insufficient to isolate the source of the improvement of VB-EGE. Is it due to the adaptive sampling? Or something about the construction of VB-EGE?

Questions for authors

How would one choose C? The paper uses C = (2,4,4).

Remark 2.1 samples opponents uniformly from the full original set of models. Out of curiosity, is there a way to avoid this? Would Borda scores computed over the current active set also preserve the coordinate-wise BT ordering?

2 comments

Response to Reviewer 55Wd

We thank the reviewer for recognizing the problem's relevance and the theoretical and empirical contributions, and address the questions and concerns below.

Questions

Q1: Choosing C=(2,4,4)C=(2,4,4).

  • The choice C=(Csamp,Cthr,Clog⁡)=(2,4,4)C=(C_{\mathrm{samp}},C_{\mathrm{thr}},C_{\log})=(2,4,4) is justified by our theoretical results to ensure correct identification and upper bounds on sample complexity. We therefore use it as the default option without dataset-specific tuning. he appendix also reports a sensitivity analysis; we will make the roles of these constants explicit alongside the algorithm.

Q2: Does active-set opponent sampling preserve BT ordering?

  • Yes, within any fixed active set. For ∣A∣≥2|A|\ge2 and i∈Ai\in A, uniform opponents from A∖{i}A\setminus\{i\} give bi,rA=∑j∈Aσ(θi,r−θj,r)−1/2∣A∣−1,b^A_{i,r}=\frac{\sum_{j\in A}\sigma(\theta_{i,r}-\theta_{j,r})-1/2}{|A|-1}, which is a common strictly increasing function of the focal score, preserving coordinate-wise BT ordering within AA.

  • The difficulty is that changing AA changes these Borda means: observations from earlier active sets no longer estimate the current coordinates. Retaining the original opponent pool lets us reuse all past focal observations with fixed means. We therefore remove certified models from focal sampling while retaining them as possible opponents. Active-set-only opponents would require an estimator and stopping analysis that account for the changing means. This is an interesting direction for future work.


Weaknesses

W1: Algorithm and theorem presentation.

  • We will refine the presentation by explaining the classification gaps in plain language and describing the sampling, certification, and removal steps before the pseudocode. We will also clarify the roles of the constants, highlight the main sample-complexity scaling, and provide intuition for the proofs.

W2: Joint fitting across models and objectives.

  • Appendix E already compares against adaptive joint BT fitting. Our heuristic Pareto extension of Goldberger and Rudi's (2026) Track-and-Stop method (https://arxiv.org/abs/2607.08979) jointly fits models within each objective and adaptively selects both pairs and objectives. VB-EGE achieves a lower capped mean comparison count in 27 of 28 tested settings. Sharing latent factors across objectives is a promising extension that would require additional structural assumptions.

W3: Baselines and the source of improvement.

  • Focal Borda isolates the benefit of our elimination procedure. It uses the same Borda estimates, phase schedule, and certification rule as VB-EGE, but continues sampling all models without elimination. In Table 11, it requires 16.54, 3.96, and 4.59 times as many comparisons as VB-EGE on Arena, SearchArena, and VisionArena, respectively. Appendix E also provides an adaptive baseline.

We hope our responses address your concerns and encourage a more favorable assessment of our paper.


Thank you for the additional comments and clarifications. I maintain my original assessment.

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

This paper studies fixed-confidence Pareto frontier identification in multi-objective LLM arenas using pairwise comparison feedback. The authors propose VB-EGE, which combines an order-preserving vector-Borda reduction with adaptive empirical-gap elimination. They establish correctness and instance-dependent sample complexity guarantees, together with a matching minimax lower bound up to logarithmic factors. Experiments on synthetic instances and three Arena datasets demonstrate improved sample efficiency over uniform-sampling baselines.

Critical strengths
  1. The paper addresses an important problem in LLM evaluation by identifying Pareto-optimal models rather than relying on scalar leaderboards. The vector-Borda reduction provides a simple way to handle multi-objective pairwise feedback.

  2. The proposed algorithm achieves fixed-confidence identification with instance-dependent sample complexity guarantees and minimax optimality up to logarithmic factors. The experiments demonstrate improvements over the considered uniform-sampling baselines.

Critical weaknesses
  1. The proposed algorithm mainly combines existing Borda-score estimation with empirical-gap elimination. The core techniques closely follow established work on pairwise comparisons and Pareto-set identification, making the independent methodological contribution somewhat limited.

  2. Despite outperforming the baselines, VB-EGE still requires millions or even billions of comparisons in many experiments, raising concerns about its practicality for costly human evaluation. Moreover, the Arena experiments rely on resampling historical comparisons rather than collecting new human feedback.

  3. The algorithm does not fully exploit the Bradley–Terry structure when selecting model pairs. Comparisons with stronger adaptive pair-selection methods would help establish whether the proposed approach is competitive beyond uniform-sampling baselines.

Questions for authors

Q1. What is the main technical novelty of VB-EGE beyond combining the Borda reduction with the empirical-gap elimination framework of Kone et al. (2024)?

Q2. Given the very large number of comparisons required in the experiments, how practical is the proposed method for real human-feedback-based LLM evaluation?

Q3. Could the authors provide a stronger comparison with adaptive methods that directly exploit the Bradley–Terry structure, rather than primarily using uniform-sampling baselines?

3 comments

Response to Reviewer tyvp

We thank the reviewer for the questions about novelty, practical cost, and stronger adaptive comparisons, and address each point below.

Questions

Q1: Technical novelty beyond Borda estimation and EGE.

  • To our knowledge, we set up the first fixed-confidence analysis of Pareto set identification from Bradley–Terry comparisons. Our technical contributions are twofold:
  1. Fixed-confidence stopping with safe elimination. Certifying a model's Pareto status is not sufficient to remove it: other unresolved models may still need it as a domination witness. Building on EGE's witness-preservation argument, we establish confidence-based elimination conditions that preserve these witnesses while ensuring that each model exits once the confidence radius resolves its classification gap. This yields both correctness and an instance-dependent stopping-time bound.
  2. Lower bounds under coupled BT feedback. Changing one latent coordinate affects every comparison involving that model on the corresponding objective, and each query informs both compared models. We construct frontier-changing BT alternatives and account for this shared information under arbitrary adaptive pair and objective selection. A bounded-horizon change-of-measure argument lower-bounds the stopping-time quantile directly, matching the high-probability criterion of our upper bound. The upper and lower bounds match in the worst case up to logarithmic factors.
  • After exploring MLE, pairwise-LCB, and Borda-based designs during our initial development, we selected VB-EGE for the best balance of theoretical guarantees and empirical performance.

Q2: Practicality and comparison costs.

  • The number of observations needed to identify the Pareto frontier strongly depends on the hardness of the problem instance and the choice of confidence level. The performance of a method should therefore be compared against the possible alternatives. As shown in Table 11, VB-EGE achieves substantial comparison savings compared with baselines: Focal Borda requires 16.54, 3.96, and 4.59 times as many comparisons as VB-EGE on Arena, SearchArena, and VisionArena, respectively. For context on the scale of human evaluation in practice, Arena reports over 82 million human votes (https://arena.ai/blog/arena-100m-revenue). We welcome the reviewer's suggestions of other relevant baselines and would love to include the comparisons.

Q3: Adaptive methods that exploit Bradley–Terry structure.

  • We would like to clarify that Appendix E already includes an adaptive BT comparison: our heuristic extension of the Track-and-Stop method in Goldberger and Rudi (2026), Optimal Top-kk Identification from Pairwise Comparisons (https://arxiv.org/abs/2607.08979), to the Pareto frontier identification case. Our extension fits BT scores across models for each objective and adaptively selects both model pairs and objectives. VB-EGE achieves a lower capped mean comparison count in 27 of the 28 tested settings; please see Appendix E for details. We have not found other directly applicable adaptive baselines in the literature and would welcome references to relevant methods.

Weaknesses

W1: Limited independent methodological contribution.

  • Answer to Q1 explains the fixed-confidence stopping analysis with safe elimination and the high-probability lower bound under coupled BT feedback.

W2: Large comparison counts and historical replay.

  • Answer to Q2 reports substantial savings against the matched Focal Borda baseline and explains how existing Arena feedback can reduce the need for new human judgments.

W3: Incomplete exploitation of BT structure.

  • Uniform opponents enable estimation of fixed Borda means. We do not rule out more efficient pair or objective selection for algorithm refinement, but our work establishes the first approach to this new setting. Appendix E additionally evaluates an adaptive BT heuristic that selects both model pairs and objectives; our answer to Q3 summarizes its comparison with VB-EGE.

We hope our responses address your concerns and encourage a more favorable assessment of our paper.


I thank the authors for their detailed response. The explanations of witness-preserving elimination and the lower-bound analysis help clarify the technical contributions. I also appreciate the additional discussion of the adaptive BT baseline in Appendix E.

However, my main concerns remain. The methodological novelty beyond existing Borda and EGE frameworks is still somewhat limited. Moreover, the very large comparison costs and the reliance on resampling historical feedback leave the practical benefits for real human evaluation unclear. Although Appendix E provides an adaptive BT comparison, the heuristic does not have a certified fixed-confidence guarantee.

Overall, the response has clarified the contributions but has not fully resolved my concerns, so I maintain my assessment.

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

The paper studies fixed-confidence identification of the strict Pareto frontier from objective-specific Bradley-Terry pairwise comparisons. VB-EGE reduces latent utilities to vector-Borda scores, preserving coordinate-wise ordering and the Pareto frontier, and adaptively removes models from the active set once their Pareto status has been certified. The paper proves high-probability recovery guarantees and an instance-dependent upper bound on sample complexity. For a fixed bounded score range and positive classification gaps, it also establishes a matching worst-case minimax rate up to logarithmic factors. Synthetic experiments and replay experiments on three Arena logs show fewer samples than uniform-sampling baselines. The logged-data experiments evaluate recovery of a fixed empirical Borda frontier.

Critical strengths

S1. Exact and useful reduction. Lemma 2.1 preserves the ordering along every coordinate and therefore the strict Pareto frontier. Random-opponent comparisons directly estimate the corresponding Bernoulli means without fitting latent scores, providing a simple route from costly pairwise feedback to Pareto-frontier identification.

S2. Substantial theoretical support. The analysis establishes high-probability correctness, an instance-dependent upper bound, and a worst-case lower bound. For fixed B, the upper and lower bounds match in their dependence on the number of models K, the number of objectives d, and the classification gap, up to logarithmic factors. The proof also explicitly addresses how elimination preserves domination witnesses: models used to certify that other models are dominated.

S3. Convincing evidence for the elimination mechanism itself. The Focal Borda baseline uses the same Borda representation and status-certification mechanism but omits adaptive elimination. The reported improvements over this baseline across heterogeneous synthetic settings and all three Arena logs directly support the value of the proposed sampling-allocation strategy.

Critical weaknesses

W1. Real-data replay does not yet establish practical efficiency for human-feedback evaluation. Section 4.2 and Appendix D.3 repeatedly sample a fixed log and recover that log's own empirical frontier. Table 11 reports 86.82 million, 124.34 million, and 8.80 million draws, despite only 73,135, 4,305, and 23,458 retained records, respectively. This conditional experiment is valid, but it neither quantifies uncertainty in the population frontier nor demonstrates feasibility when collecting fresh human judgments. Retaining only a subset of models with complete comparison coverage further limits the applicability of the results.

W2. Comparison with strong adaptive alternatives remains unresolved. The main experimental baselines use uniform sampling, and BT-MLE uses a plug-in heuristic stopping rule. Appendix E adds an adaptive likelihood-based comparator but explicitly states that its screened stopping statistic is not rigorously certified and that the results are provisional. Thus, beyond the well-controlled Focal Borda comparison, the other comparisons do not establish that VB-EGE remains superior under matched fixed-confidence guarantees. The exact stopping-rule verification over the full set of constraints suggested in Appendix E.2 is particularly feasible when the Pareto frontier contains only one model.

W3. Outcome handling materially changes the practical conclusions. The analysis in Appendix D.4 is valuable, but Table 14 shows that directly assigning half credit to non-decisive feedback changes the Arena frontier from three models to four. The target frontier obtained from the fitted Davidson model has a Jaccard similarity of only 0.50 with the decisive-only frontier. Table 15 shows that, under the fitted target, the VisionArena sampling cost increases from 8.80 million to 471.55 million draws. These results indicate limitations in the stability of both the selected models and the claimed evaluation budget.

Questions for authors

Q1. Can you quantify uncertainty in the empirical frontier using independently collected human judgments or resampling of the source logs, rather than only repeated draws conditional on the same fixed log? How should the very large replay counts in Table 11 translate into a realistic budget for fresh human comparisons?

Q2. For settings in which the frontier contains only one model, can you complete the exact stopping-rule verification over the full set of constraints suggested in Appendix E.2 and compare methods using theoretically justified, method-specific stopping rules at the same confidence level? Does VB-EGE retain its advantage under that comparison?

Q3. Given the frontier changes in Table 14 and the VisionArena cost rising to 53.59 times its original value in Table 15, which outcome definition should guide the paper's main practical conclusions? What evidence supports treating the decisive-only frontier and cost as representative of the intended evaluation task?

2 comments

Response to Reviewer 7sv8

We thank the reviewer for the feedback on uncertainty, adaptive baselines, and outcome definitions, and address each point below.

Questions

Q1: Sampling mechanism in real-world experiments and budget comparison.

  • Thank you for the question. To clarify, we do resample logged judgments with replacement, as explained in Appendix D.3. Please let us know if we misunderstood your concern. Using independently collected human judgments requires substantial additional work, such as establishing the platform and recruiting volunteers. This is beyond the scope of our current methodological work and we leave it for the future.

  • The number of observations needed to identify the Pareto frontier strongly depends on the hardness of the problem instance. The performance of a method should therefore be compared against the possible alternatives. As shown in Table 11, VB-EGE achieves substantial comparison savings compared with baselines: Focal Borda requires 16.54, 3.96, and 4.59 times as many comparisons as VB-EGE on Arena, SearchArena, and VisionArena, respectively. For context on the scale of human evaluation in practice, Arena reports over 82 million human votes (https://arena.ai/blog/arena-100m-revenue). We welcome the reviewer's suggestions of other relevant baselines and would love to include the comparisons.


Q2: Comparison with adaptive BT.

  • We would like to clarify that the adaptive BT algorithm described in Appendix E serves a supplementary baseline. To our knowledge, the prior literature does not provide a directly applicable adaptive baseline with theoretical guarantees. Establishing comparable guarantees for adaptive BT would be separate research contribution. We welcome references' suggestions of relevant methods.

  • Per the reviewer's suggestion, we added singleton-frontier experiments with complete stopping checks for adaptive BT. Compared with the screened heuristic in Appendix E, the new variant checks all alternatives before stopping. In the experiment, we evaluate VB-EGE and adaptive BT under two heterogeneous-gap families to study how elimination handles competitors of different difficulty: one family (referred to as One close competitor) has a single competitor close to the best model, while all other models are much worse; the other family (referred to as Ladder gaps) has competitors whose gaps from the best model are evenly spaced from small to large. For each family, we fix d=2d=2 and vary K=8,16,32K=8,16,32 to examine how the comparison changes with model count. Each entry is the mean comparison count over 50 independent runs with the confidence parameter set to δ=0.05\delta=0.05; all runs stopped without observed errors.

Singleton-frontier setting (d=2d=2)VB-EGEAdaptive BT, full checks
One close competitor, K=8K=81,243,054406,687
One close competitor, K=16K=161,574,7402,075,515
One close competitor, K=32K=321,712,08411,334,508
Ladder gaps, K=8K=8423,587424,165
Ladder gaps, K=16K=16932,3992,339,453
Ladder gaps, K=32K=321,975,66211,056,847
  • VB-EGE eliminates easy models early and concentrates subsequent focal sampling on unresolved models. At K=32K=32, it reduces mean comparisons by 84.9% and 82.1% in these two families, respectively.

Q3: Outcome definitions and the practical conclusions.

  • Thank you for raising the concern. We emphasize that our main methodological contribution and empirical conclusions on the real-world data are based on decisive-only feedback. This is consistent with the binary BT model underlying our theoretical guarantees. The half-credit and fitted Davidson experiments in Appendix D.4 are supplementary sensitivity analyses that illustrate how outcome definitions affect frontier membership and comparison costs and the 53.59-fold increase concerns the distinct fitted Davidson target. Our estimation and elimination analysis also applies when ties receive half credit, with guarantees targeting the resulting Borda frontier. When tie propensities vary across model pairs, as allowed in our fitted Davidson extension, this frontier need not coincide with the latent-score frontier. Extending the population latent-frontier guarantee to a model incorporating non-decisive outcomes, however, is future work.

Weaknesses

W1: Practical efficiency and population uncertainty.

  • All methods are evaluated against the same empirical frontier, with every repeated draw counted. This provides a controlled comparison of their sampling costs. Answer to Q1 discusses source-data coverage and the use of existing Arena feedback in practical evaluation.

W2: Comparisons with stronger adaptive alternatives.

  • Answer to Q2 explains the exploratory role of the Appendix E heuristic and the scope of our theoretical contribution. The matched Focal Borda comparison separately evaluates the benefit of the elimination-based procedure.

W3: Sensitivity to outcome handling.

  • Answer to Q3 identifies decisive-only feedback as the basis of our main latent-BT conclusions. The alternative outcome definitions provide supplementary sensitivity analyses and motivate future extensions of the latent-frontier theory.

We hope our responses address your concerns and encourage a more favorable assessment of our paper.


Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary for Chairs and Reviewers (1/2)

Summary for Chairs and Reviewers

Dear Senior Area Chairs, Area Chairs and Reviewers,

Thank you for your careful evaluation. We summarize our contributions, the main concerns raised by the reviewers, and how our responses address them.


Overview of Our Paper

Our paper studies how to identify Pareto optimal models from Arena-type pairwise preferences across multiple capabilities. This retains models with different strengths rather than collapsing their performance into a scalar ranking. To our knowledge, we provide the first fixed-confidence analysis of Pareto set identification from multi-objective Bradley–Terry comparisons.

Our contributions are threefold:

  1. Problem formulation. We formulate fixed-confidence Pareto-set identification under objective-specific Bradley–Terry feedback. An order-preserving vector-Borda reduction connects latent scores to directly estimable win probabilities while preserving the strict Pareto frontier.
  2. Algorithm and theoretical guarantees. We propose VB-EGE, an adaptive algorithm that focuses comparisons on models whose Pareto status remains unresolved. We establish its correctness and an instance-dependent sample-complexity upper bound, together with a matching worst-case lower bound showing minimax optimality up to logarithmic factors.
  3. Empirical effectiveness. Synthetic experiments confirm the predicted scaling and demonstrate VB-EGE's sample efficiency. Experiments on Arena, SearchArena, and VisionArena show substantial gains over uniform baselines. The adaptive BT comparison in Appendix E further supports its competitiveness.

Summary of Reviewers' Concerns

  • Q1. Technical novelty. What is required beyond combining Borda estimation with existing EGE methods? (tyvp, 254S)
  • Q2. Adaptive sampling and baselines. Why use uniform opponents, and how does VB-EGE compare with more adaptive BT methods? (All reviewers)
  • Q3. Comparison costs. Given the large number of comparisons, how practical is VB-EGE for human-feedback-based evaluation? (7sv8, tyvp, 254S)
  • Q4. Modeling choices. Why use strict dominance and require complete pair-query access? (254S)

AuthorsOpenReview ↗

Summary for Chairs and Reviewers (2/2)

How We Addressed These Concerns

A1. A New Setting with Substantive Theoretical Analysis

Our contribution establishes fixed-confidence Pareto identification from objective-specific BT comparisons. The guarantees do not follow from order preservation alone.

  • Safe elimination and stopping. Building on EGE's witness-preservation argument, we establish confidence-based conditions that prevent premature removal of models needed to classify others and ensure removal once their gaps are resolved. Both properties are necessary for correctness and the instance-dependent stopping bound.
  • Optimality under the original query model. Our lower bound accounts for information shared across BT comparisons and permits arbitrary adaptive pair and objective selection. It directly bounds the stopping-time quantile and matches our upper bound in the worst case up to logarithmic factors.

A2. Adaptive Comparisons Are Already Included and Further Strengthened

VB-EGE is adaptive: certified models receive no further focal samples. Uniform opponents keep Borda means fixed so that observations remain reusable across phases. Finer pair selection may improve particular instances, but our lower bound already covers such strategies.

  • Controlled comparison. Focal Borda uses the same estimates and certification mechanism without elimination. It requires 16.54, 3.96, and 4.59 times as many comparisons on Arena, SearchArena, and VisionArena, isolating the benefit of our elimination procedure.
  • Adaptive BT comparison. Appendix E already evaluates joint BT fitting with adaptive pair and objective selection. VB-EGE achieves a lower capped mean comparison count in 27 of 28 settings.
  • Additional complete checks. In response to 7sv8, we added singleton-frontier experiments with complete stopping checks. The six reported configurations include advantages for both methods; VB-EGE saves 84.9% and 82.1% in the two K=32K=32 configurations.

To our knowledge, no directly applicable adaptive baseline with corresponding guarantees is available in the prior literature. Our adaptive BT heuristic is supplementary; developing its full fixed-confidence guarantee is a separate research contribution. We welcome references to relevant alternatives.

A3. Comparison Costs and Practical Evaluation

The number of observations needed to identify the Pareto frontier strongly depends on the hardness of the problem instance and the confidence level. Efficiency should therefore be assessed against relevant alternatives. VB-EGE achieves substantial comparison savings: Focal Borda requires 16.54, 3.96, and 4.59 times as many comparisons on Arena, SearchArena, and VisionArena, respectively.

These experiments resample existing judgments with replacement. Practical evaluation can build on accumulated feedback from platforms such as Arena, which reports over 82 million human votes (https://arena.ai/blog/arena-100m-revenue). Independently collecting fresh judgments requires additional infrastructure, recruitment, and funding; we leave this online validation to future work.

A4. Strict Dominance and Complete Query Access

  • Strict dominance matches our conservative screening objective: a model is excluded only when another improves every evaluated capability. If models are tied on a capability a user values, price or speed may guide the choice. We therefore retain exact strict identification as the primary target.
  • Our current method requires a complete query graph for each objective, as do the prior comparison methods cited in our response. Exploiting sparse historical graphs requires graph-aware estimation and sampling and is a natural direction for future work.

Our paper establishes a new identification setting, a provably efficient solution, and substantial empirical comparison savings. We hope this summary clarifies the contribution and the additional evidence provided in our responses, and we welcome any remaining questions.

Best regards,

The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.