acceptodds
Under review as a conference paper at ICLR 2027

Sample-Efficient LLM Evaluation via Pure Exploration under Task Heterogeneity

Abstract

We study sample-efficient LLM evaluation from preference feedback under task heterogeneity, where LLM comparisons are actively collected across diverse tasks to identify the best-performing model overall. We formulate this problem as fixed-confidence pure exploration under a contextual multinomial logit model with task-dependent model features, inducing heterogeneous preferences coupled through a shared latent parameter. Using a change-of-measure argument and a local quadratic approximation, we derive a Fisher-geometric separation criterion that characterizes the identification difficulty. A tractable relaxation of this criterion admits an explicit directional-variance representation, suggesting that comparisons should be allocated to reduce the worst uncertainty over decision-changing alternatives. Building on this principle, we develop Multi-FW, a global Frank–Wolfe procedure that coordinates task-conditioned comparison allocations. Theoretically, combining estimator concentration and consistency with our proposed task-aware tracking, we establish asymptotically optimal separation growth despite exogenous task arrivals. For any fixed , suitably tuning forced exploration yields an sample-complexity upper bound for Multi-FW, approaching the lower bound's logarithmic confidence dependence. Finally, we evaluate Multi-FW in a semi-real environment constructed from the Arena Human Preference 140K dataset, using logged human preferences and real LLM responses. Multi-FW achieves faster separation growth than task-agnostic Elo-style, uniform-random, and dueling-style baselines, with at least a -percentage-point gain in trajectory-averaged identification accuracy and more than a reduction in the comparison budget needed for stable accuracy.

Primary area:
learning theory
Keywords:
Large language model evaluation, bandit pure exploration, preference feedback, task heterogeneity, contextual multinomial logit, best arm identification

Reviews

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

This paper proposes MULTI-FW, a task-aware active evaluation algorithm for identifying the best-performing LLM under heterogeneous task distributions. It models winner-only preference feedback with a contextual multinomial logit model, uses Fisher information to measure uncertainty along decision-relevant directions, and applies a Frank-Wolfe allocation strategy to select informative model comparisons across tasks. Experiments in an Arena-derived semi-real environment show that MULTI-FW identifies the task-averaged best model more accurately and with fewer comparisons than several baselines. However, the evaluation relies on aggregated MiniLM response embeddings and a shared MNL parameter fitted from the same Arena data used to construct the simulated environment, so the results mainly demonstrate effectiveness under a well-specified synthetic model and provide limited evidence for robustness to real query-level and user-level preference heterogeneity.

Critical strengths
  1. The paper formulates an important and practically relevant problem. Efficiently allocating expensive human preference comparisons across heterogeneous tasks is valuable for LLM evaluation, and the fixed-confidence best-model identification objective is clearly defined.

  2. The algorithm and theoretical analysis are well structured. The Fisher-geometric separation criterion and the task-aware Frank-Wolfe allocation strategy provide a principled way to focus comparisons on decision-relevant uncertainty rather than using uniform sampling. The paper also includes consistency and sample-complexity guarantees under its modeling assumptions.

Critical weaknesses
  1. The experimental environment is constructed from a strong closed-loop modeling assumption. The task-dependent features xj,ix_{j,i} are obtained from aggregated MiniLM embeddings, while the shared preference parameter θ∗\theta^* is fitted using a contextual MNL model on Arena data. New feedback is then sampled from this same fitted MNL model. Consequently, the experiments are largely well specified by construction and do not establish that the proposed representation or shared parameter adequately captures real query-level and user-level preference heterogeneity.
  2. The response features are aggregated at the task-model level, so each incoming query effectively contributes only a sample from a fixed task-level preference distribution. This setting removes much of the query-level variability and evaluation noise that make real LLM comparison expensive. As a result, the reported gains may primarily reflect efficient identification in the constructed MNL simulator rather than robust sample efficiency in real-world human preference evaluation.
Questions for authors
  1. Can the authors evaluate MULTI-FW in a more realistic evaluation setting with fresh human judgments or at least held-out, query-level preference data? The current experiments generate feedback from a contextual MNL model fitted on the same Arena data used to construct the task features. It would be important to test whether the method remains effective when each query has its own response features and preference noise, rather than being sampled from a fixed task-level distribution.
  2. How sensitive is MULTI-FW to the construction of xj,ix_{j,i} and the shared preference parameter θ∗\theta^*? In particular, can the authors compare the proposed aggregated MiniLM features against alternative representations, such as query-level embeddings, reward-model scores, or learned response-quality features, and evaluate whether the allocation and identification results remain consistent under different feature constructions and preference models?
3 comments
AuthorsOpenReview ↗

Robustness to feedback misspecification, query-level variation, and task heterogeneity

1. Robustness and multitask evaluation of Multi-FW

Thank you for highlighting the limitations of task-level aggregation and fitted-model feedback. We acknowledge that the original semi-real experiments do not establish that aggregated features and a shared parameter fully capture real query- and user-level preferences. We have added Appendix F, which evaluates Multi-FW under empirical feedback, latent variation in response features and preference weights, and richer task structures. Multi-FW retains its identification advantage across these settings, each evaluated over 100 paired replications at T=1000T=1000.

Empirical preference feedback (F.1). We replace the fitted MNL feedback generator with empirical preference frequencies to assess Multi-FW's robustness to departures from the fitted contextual MNL model. The mean absolute win-probability change is 6.92 percentage points. The empirical Borda-optimal model agrees with the fitted-utility target. Multi-FW achieves a checkpoint AUC of 0.865, exceeding the strongest baseline by 15.7 percentage points. Thus, its advantage persists when feedback no longer comes from the fitted MNL generator.

Latent query-level response variation (F.2). Aggregating response embeddings within each task–model cell leaves variation across individual queries unrepresented. We introduce Gaussian perturbations around the aggregated features, independently across rounds and models, and generate feedback from these latent features. The perturbations remain hidden, while Multi-FW continues to use the task-level averages. At σ=0.05\sigma=0.05, marginal win probabilities change by 4.56 percentage points on average in absolute value, and the reference-best model's task-weighted win probability against the reference runner-up falls from 58.97% to 55.72%. Despite weaker identification signals, Multi-FW's checkpoint AUC exceeds the strongest baseline by approximately 13.0 percentage points; its terminal accuracy is 90%, versus a baseline maximum of 74%.

Latent query-level preference heterogeneity (F.3). The shared parameter leaves variation in preference weights unrepresented. We introduce independent Gaussian perturbations around the fitted parameter across rounds, with all models sharing the same latent parameter within a round. The perturbations remain hidden, and Multi-FW continues to estimate a single shared parameter. At a per-coordinate noise standard deviation of τ=25\tau=25, the mean absolute change in marginal win probabilities is 6.61 percentage points, and the same reference top-two win probability falls to 55.06%. Multi-FW retains the highest checkpoint AUC and terminal accuracy, exceeding the strongest baseline in AUC by approximately 16.1 percentage points. Its terminal accuracy is 77%, versus a baseline maximum of 62%. Both perturbations weaken comparison signals and slow identification; Multi-FW's absolute performance declines, but its advantage over the baselines remains substantial.

Multitask evaluation (F.4–F.5). We expand Arena to five and ten tasks by splitting its original tasks into synthetic children whose perturbed features are observed and fixed across replications. Preference reversals increase from 10 of 105 model pairs to 70 and 54; arrival-weighted mean absolute child–parent win-probability changes are 8.61 and 6.18 percentage points. Multi-FW's checkpoint AUC exceeds the strongest baseline by 9.5 and 10.6 percentage points. In a separate fully synthetic instance with five tasks and ten models, 42 of 45 pairs reverse their preference direction across tasks, and the tasks have four distinct optimal models; Multi-FW's AUC advantage is approximately 13.3 percentage points. These results show that Multi-FW's identification advantage persists across distinct task constructions with substantially increased preference heterogeneity.

2. Held-out validation and alternative representations

Held-out evaluation. We agree that fresh human judgments or held-out query-level data provide important complementary validation. The empirical-feedback experiment reuses Arena data, and the Gaussian experiments model hidden variation synthetically. These controlled benchmarks let us compare allocation efficiency against a specified identification target while varying feedback and task structure; they do not establish out-of-sample validity on real queries.

Alternative representations. Our framework accepts task-dependent features and does not require MiniLM specifically; Section 3 allows response embeddings, rubric-based features, or evaluator-model features. However, the present perturbation tests do not compare query-level embeddings, reward-model scores, or learned response-quality features. Such comparisons remain an important next step.

I thank the authors for their detailed response. It addresses my concern about the task-model-level aggregation of response features and the resulting lack of query-level variability. I will keep my score unchanged.

Thank you again for your careful reading and constructive feedback. Your comments helped us strengthen the evaluation. We are glad that our response and additional experiments address your concern about query-level variability.

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

This work studies how to identify the best LLM, i.e., the model with the highest score averaged over tasks, efficiently using preference feedback across heterogeneous tasks. By assuming that the preference over the best model in a given set follows a contextual multinomial logit model, the authors propose a Frank-Wolfe algorithm. To do so, they leverage a local quadratic approximation of the KL information. This allows them to optimize which sets of model to compare on each task. The authors then provide theoretical guarantees and apply their method on LMArena data with two tasks. Their method achieves better accuracy with less comparisons compared to baselines (uniform allocation, task-agnostic Elo, dueling bandits).

Critical strengths

The problem of reducing LLM evaluation costs is relevant and would be of interest to the ICLR community. I find the underlying approach reasonable and the empirical results are also encouraging.

Critical weaknesses

I find the paper difficult to follow, starting from the paper's abstract. Although the underlying approach seems relatively intuitive to me, I find the presentation does it a disservice. It is hard to track all the notation, some terms are introduced without careful description (e.g., what are exogenous tasks?), and the theoretical guarantees are hard to parse. In particular, I am not sure what the main results rely on and how they relate to the proposed algorithm. Lastly, the experimental results are not particularly useful since they authors only test two tasks. However, the LMArena dataset has other categorizations which exhibit lots of heterogeneity, e.g., math vs writing vs instruction following vs coding. If real data is hard to obtain, I think synthetic tasks would be extremely beneficial!

Questions for authors

Since the experiments generate preference feedback using a fitted MNL model, I am curious about the performance of your method without such an assumption.

Also, I think the baselines are not well suited, please correct me if I'm wrong! I don't think Elo, for example, recovers the model with the highest utility averaged over tasks (your decision problem). It instead fits a ranking under a different preference model. However, I cannot think of a fair baseline as I am unfamiliar with this area.

4 comments
AuthorsOpenReview ↗

Clarifications and expanded multitask and robustness evaluation

1. Clarifying the problem, algorithm, and guarantees

Thank you for highlighting the presentation issues. We acknowledge that the setup and the connection between the algorithm and its guarantees should be clearer. Our goal is to identify the model with the highest utility averaged over a specified task mixture. "Exogenous tasks" means that tasks arrive outside the algorithm's control. For example, in an Arena-style evaluation, users bring coding or writing queries; the algorithm chooses which models to compare on each arriving query. Each comparison provides information within one task, but its value depends on how it helps identify the overall best model. Multi-FW pools feedback across tasks to estimate shared preference weights, then coordinates comparisons within each task toward this common objective. Cross-task information allocation is the core idea; Frank–Wolfe provides an efficient way to compute it.

The guarantees assume the contextual MNL model and the regularity conditions in Section 6, including identifiability, a unique overall best model, and independent task arrivals from a known mixture. They link reliable parameter estimation and task-wise tracking to evidence accumulation, with confidence bounds providing valid stopping and sample-complexity guarantees. The allocation analysis uses optimal targets; the practical algorithm approximates these targets numerically using FW.

2. Expanded multitask and robustness evaluation

We have added Appendix F, including synthetic multitask instances as suggested. Each setting uses 100 paired replications at T=1000T=1000.

Synthetic multitask (F.4). Following your suggestion, we added a fully synthetic instance with five equally likely tasks and ten models. Raw features and the shared parameter are drawn from Gaussian distributions. Of the 45 model pairs, 42 reverse their preference direction across tasks, and the five tasks have four distinct optimal models. This reflects substantial cross-task preference heterogeneity. Nevertheless, Multi-FW's checkpoint AUC exceeds the strongest baseline by approximately 13.3 percentage points. At t=600t=600, its accuracy is 93%, compared with 80% for Random.

Arena-anchored multitask (F.5). We expand the two-task Arena environment to five and ten tasks by splitting its original tasks into synthetic child tasks with perturbed features. Preference reversals increase from 10 of 105 model pairs to 70 and 54; arrival-weighted mean absolute child–parent win-probability changes are 8.61 and 6.18 percentage points. These changes reflect substantially increased preference heterogeneity across tasks. Multi-FW exceeds the strongest baseline in checkpoint AUC by 9.5 and 10.6 percentage points. Its accuracy at t=600t=600 is 94% and 96%, compared with baseline maxima of 85% and 86%, respectively.

Empirical preference feedback (F.1). We replace the fitted MNL feedback generator with empirical preference frequencies to assess Multi-FW's robustness to departures from the fitted contextual MNL model. The mean absolute win-probability change is 6.92 percentage points. This introduces a departure from the fitted model while preserving most pairwise preference directions. The empirical Borda-optimal model agrees with the fitted-utility target. Multi-FW achieves a checkpoint AUC of 0.865, exceeding the strongest baseline by 15.7 percentage points. Thus, its advantage persists when feedback no longer comes from the fitted MNL generator.

Latent query-level variation (F.2–F.3). In separate experiments, independent Gaussian perturbations to aggregated response features (F.2) and the fitted preference parameter (F.3) model latent query-level feature and preference heterogeneity. Multi-FW still uses aggregated task-level features and estimates a single shared parameter. Despite weakened comparison signals, its checkpoint AUC exceeds the strongest baseline by approximately 13.0 and 16.1 percentage points, respectively.

3. Baseline choice and comparison target

We agree that a task-agnostic Elo-style score need not recover the task-averaged utility optimum. Mis1H-FW and MisTTB serve as task-agnostic reference methods. Our matched allocation control is Random: it uses the same task-dependent features, contextual estimator, update schedule, exploration rule, and identification target as Multi-FW (Appendix D.2). Multi-FW achieves a checkpoint AUC of 0.844 versus 0.688 for Random in the main experiment, isolating the benefit of active allocation.

Appendix E.5 additionally compares Multi-FW with SDP-R, a variant that numerically solves the restricted allocation SDP for the same identification objective. Over 100 completed paired Arena runs, SDP-R's checkpoint AUC is only 1.40 percentage points higher, but its mean allocation optimization time is about 202 times that of Multi-FW.

Thanks for the clarification! For the new multitask experiments, why did you split the original tasks into synthetic child tasks when the Arena data itself provides categorizations like prompt language or prompt type (math, coding, instruction following, ...)?

Looking at the rebuttals and the paper again, my concern is that the method as presented in the paper does not have novel technical insights. At the same time, the method seems to me a bit convoluted which would limit its adoption.

I do believe this is a useful setup, but I am not confident this work explains the method and the experimental setup well, and as such, cannot recommend its acceptance at this time.

AuthorsOpenReview ↗

Additional prompt-based multitask evaluation on Arena

Thank you again for encouraging evaluation beyond the original two-task setting. We have added prompt-based multitask experiments on Arena (Appendix F.6), complementing the two multitask settings in our earlier response: fully synthetic and Arena-anchored. The new tasks are derived directly from real Arena user prompts by clustering their embeddings, with response features reaggregated within the resulting task–model cells. Compared with the original two-task environment, these settings introduce finer task distinctions, different arrival proportions, more preference reversals, and higher effective dimensions. Multi-FW nevertheless reaches high identification accuracy with fewer comparisons than the baselines in both settings.

Task construction. We retain the same 9,895 comparisons and 15 models as the main experiment. Using only embeddings of the full user prompts, including all user turns, we apply clustering in two ways:

  • Five tasks (1+4): retain code and cluster non-code prompts into four tasks.
  • Six tasks (joint): cluster all prompts into six tasks without imposing the code/non-code partition.

Both partitions retain every comparison and cover all 15 models and all 105 model pairs in every task. We average existing final-response embeddings within the new task–model cells, retain all 384 coordinates, and refit a contextual MNL model for feedback generation. Task-arrival probabilities equal observed task proportions.

Task composition and heterogeneity. The table compares the task-arrival distributions across partitions. Code is listed first in the two- and five-task settings.

EnvironmentTask-arrival probabilities (%)
Original two-task(33.623, 66.377)
Five tasks (1+4)(33.623, 22.688, 11.652, 14.270, 17.767)
Six tasks (joint)(18.828, 11.935, 30.915, 20.101, 12.612, 5.609)

Among the 105 model pairs, 30 and 31 reverse their fitted preference direction across tasks, respectively, compared with 10 originally; all task-specific rankings are distinct within each environment. Effective dimensions increase from 28 to 70 and 84. Thus, the new environments require coordinating comparisons across more tasks with unequal arrival rates and differing preference rankings, while estimating a higher-dimensional parameter.

Identification performance. Each environment is fixed across 100 paired replications at T=1000, using the original four methods and update schedules. The table reports empirical accuracy at 600 comparisons, checkpoint AUC, the first round reaching 80% accuracy, and the first round from which accuracy remains at least 90% through T=1000. Checkpoint AUC averages accuracy at t=50,100,...,1000.

TasksMethodAccuracy at 600Checkpoint AUCFirst 80%Stable 90%
FiveMulti-FW0.9800.860280390
FiveRandom0.8100.729430>1000
FiveMis1H-FW0.8000.653580>1000
FiveMisTTB0.0700.086>1000>1000
SixMulti-FW0.9500.821340450
SixRandom0.7400.694690>1000
SixMis1H-FW0.7900.666610>1000
SixMisTTB0.1500.158>1000>1000

Multi-FW exceeds the strongest baseline in checkpoint AUC by 13.1 and 12.7 percentage points. Only Multi-FW satisfies the stable-90% criterion within the budget, from 390 and 450 comparisons onward. Relative to the fastest baseline, comparison-budget savings are 34.9% and 44.3% at 80% accuracy, and at least 61% and 55% for stable 90%, for five and six tasks, respectively. Its advantage persists at T=1000: accuracies are 99% and 97%, compared with baseline maxima of 87% and 86%. Multi-FW therefore retains its identification advantage across both prompt-based partitions despite finer task distinctions, changed arrival proportions, and increased preference heterogeneity.

In the revised manuscript, we provide the full protocol, diagnostics, and accuracy curves in Appendix F.6. Moreover, we have updated the supplementary code to include the frozen task assignments and environments, construction pipeline, and scripts for reproducing and analyzing these experiments.

AuthorsOpenReview ↗

Clarifications on multitask evaluation and technical contributions

Thank you for revisiting our paper and explaining your remaining concerns. We agree that Arena’s richer semantic annotations provide a valuable, more interpretable basis for defining tasks. Our synthetic child tasks serve as controlled tests of task heterogeneity. Appendix F.6 complements these tests with five- and six-task environments constructed by clustering real user prompt embeddings and reaggregating response features within the resulting task–model cells. In particular, the joint six-task partition clusters all retained prompts without a code/non-code split. Multi-FW retains its identification advantage across these partitions, which introduce different arrival proportions and preference rankings. Evaluation using the existing semantic labels remains an important complementary test that our current experiments do not cover.

We also appreciate the need to articulate the technical contribution more clearly. Two contributions are central. First, we connect task-local feedback to global identification: the separation criterion and its tractable directional-variance surrogate coordinate comparisons across tasks to identify the task-averaged best model. Second, we implement this joint allocation under exogenous task arrivals: task-aware tracking and forced exploration translate the coupled designs into feasible online comparisons, with separation-growth, stopping-correctness, and sample-complexity guarantees under the stated conditions. These components address the linked difficulties of deciding which local comparisons support the global decision and realizing that design when the learner cannot choose the arriving task.

We would be grateful if you could take these clarifications and the additional prompt-based multitask evidence into account in your final assessment.

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

This paper investigates the problem of sample-efficient preference-based large language model evaluation under task heterogeneity, with the goal of identifying the model with optimal task-averaged performance with high confidence using as few pairwise comparisons as possible. The paper formulates this problem as a fixed-confidence pure exploration problem under a contextual multinomial logit (MNL) model equipped with a shared latent preference parameter and task-dependent features. It proposes a Fisher-geometric separation criterion to characterize the difficulty of identifying the optimal model, and develops the MULTI-FW active allocation algorithm that enables efficient sampling via global Frank-Wolfe optimal design, online deficit tracking and a forced exploration mechanism. Semi-real experiments conducted on the Arena 140K dataset show that the proposed method significantly outperforms various baseline methods.

Critical strengths

1.The research problem is interesting. The paper focuses on how to identify the overall best-performing model with the fewest possible pairwise comparisons when large language models exhibit heterogeneous preferences across different tasks, which aligns well with the dual demands for efficiency and reliability in current LLM evaluation practice.

2.This paper presents a relatively complete framework of algorithm design and theoretical analysis. The authors propose the MULTI-FW algorithm, which incorporates task-aware allocation and tracking mechanisms. Meanwhile, the paper conducts theoretical analysis covering parameter estimation, allocation convergence, and sample complexity, providing considerable theoretical support for understanding the algorithm's operating mechanism and performance properties.

Critical weaknesses

1.The theoretical optimality argument requires further refinement. The paper derives the information-theoretic lower bound based on a local quadratic approximation, and constructs a computationally tractable surrogate optimization objective by relaxing the set of alternative parameters. However, the optimality correspondence between this surrogate objective and the original constrained objective has not been fully established. As a result, the existing theoretical results are insufficient to rigorously demonstrate that the algorithm achieves the information-theoretically optimal sample complexity for the original problem.

2.The empirical validation is inadequate. The current experiments are conducted in a semi-realistic environment built upon a fitted MNL model, and only involve two task categories: coding and non-coding. While the results show the method’s advantages under this specific setting, its performance under different task distributions, varying degrees of task heterogeneity, and preference model misspecification has not been systematically examined. Hence, the effectiveness of the method in more complex task scenarios and the robustness of its performance advantages cannot be fully verified.

Questions for authors

1.This paper constructs a surrogate optimization objective based on an unconstrained set of alternative parameters, based on which the MULTI-FW algorithm is designed. Could the authors clarify the magnitude of the optimality gap between this surrogate objective and the original constrained separation objective? Under what conditions can the algorithm achieve or approach the information-theoretic lower bound on sample complexity of the original problem?

2.This paper derives the information-theoretic lower bound using a local quadratic approximation of KL divergence. Could the authors elaborate on the applicable conditions of this approximation, and whether the approximation error compromises the validity of the corresponding separation criterion and sample complexity results?

  1. Experiments are limited to a semi-realistic environment consisting of only two task categories. Is this setting sufficient to fully verify the effectiveness of active allocation under task heterogeneity?

4.The experiments do not validate the paper’s central claim of fixed-confidence stopping. The core theoretical objective is to stop once a prescribed confidence level is reached, while guaranteeing that the probability of selecting the wrong model is at mostδ. However, the experiments instead fix the number of comparisons and measure average identification accuracy. These are fundamentally different evaluation criteria.

4 comments
AuthorsOpenReview ↗

Losses and benefits of the unrestricted surrogate, and robustness and multitask evaluation

1. Limited cost and computational benefits of the unrestricted surrogate

Thank you for highlighting the potential gap between the restricted objective and its unrestricted relaxation. We would like to clarify that Section 6 provides sample-complexity upper bounds for both formulations, and the restricted bound retains the characteristic-time dependence of the local quadratic lower bound. However, we acknowledge that Multi-FW uses the unrestricted surrogate and need not attain the restricted optimum. Thus, new Appendix E examines the costs and benefits of this relaxation through an online comparison, theoretical loss analysis, and simulations.

  • Computational tradeoff (E.5). We implement SDP-R, a Multi-FW variant that numerically solves the restricted allocation SDP instead of using FW updates. Over 100 completed paired Arena runs, its checkpoint AUC is only 1.40 percentage points higher than Multi-FW's, but its mean allocation optimization time is about 202 times that of Multi-FW, demonstrating our surrogate's computational benefit.

  • Theory (E.1). We provide a simple sufficient condition for lossless relaxation: at a restricted optimum, an unrestricted worst-case alternative lies in the known parameter domain. This yields two explicit sufficient thresholds for the known norm bound, based on the Fisher matrix's condition number and on separation. In addition, both separation and allocation losses vanish as the known norm bound grows, with the instance fixed.

  • Simulations (E.2–E.4). We construct 800 random configurations across isotropic, correlated, anisotropic, and taskwise low-rank instance families and vary the known norm bound to numerically evaluate separation and allocation losses. When the known norm bound is twice the true parameter norm, both losses are at most 0.1% in 98.5% of configurations, and both empirical means are below 0.0183%.

2. Robustness and multitask evaluation of Multi-FW: New Appendix F

Empirical preference feedback (F.1). Replacing fitted contextual MNL feedback with empirical preference frequencies tests Multi-FW's robustness to departures from that model. The mean absolute win-probability change is 6.92 percentage points. Multi-FW's checkpoint AUC is 0.865, exceeding the strongest baseline by 15.7 percentage points.

Synthetic multitask (F.4). In a fully synthetic instance with five heterogeneous tasks and ten models, 42 of 45 model pairs reverse their preference direction across tasks, and the tasks have four distinct optimal models. Multi-FW's checkpoint AUC exceeds the strongest baseline by approximately 13.3 percentage points.

Arena-anchored multitask (F.5). We expand the two-task Arena environment to five and ten tasks by splitting its original tasks into synthetic child tasks with perturbed features. Preference reversals increase from 10 of 105 model pairs to 70 and 54; arrival-weighted mean absolute child–parent win-probability changes are 8.61 and 6.18 percentage points. These changes reflect substantially increased preference heterogeneity across tasks. Multi-FW exceeds the strongest baseline in checkpoint AUC by 9.5 and 10.6 percentage points.

Latent query-level variation (F.2–F.3). In separate experiments, independent Gaussian perturbations to aggregated response features (F.2) and the fitted preference parameter (F.3) model latent query-level feature and preference heterogeneity. Multi-FW still uses aggregated task-level features and estimates a single shared parameter. Despite weakened comparison signals, its checkpoint AUC exceeds the strongest baseline by approximately 13.0 and 16.1 percentage points, respectively.

3. Fisher approximation and fixed-confidence evaluation

Fisher approximation. We acknowledge that the Fisher criterion is a local quadratic approximation to KL. Our new KL–Fisher comparison lemma (Appendix C.1.2) explicitly bounds its error uniformly over allocations via Hessian comparison. The approximation enables our tractable allocation objective, and experiments support its practical usefulness.

Fixed-confidence evaluation. We acknowledge that the experiments do not directly assess the stopping rule's error calibration or stopping-time efficiency; our fixed-confidence guarantees are established theoretically. We view the fixed-confidence formulation as a guide to sample-efficient allocation. Our common-horizon experiments assess this efficiency through accuracy at equal budgets and comparisons needed to reach equal empirical accuracy.

  1. Comparability. A common budget permits comparison across methods without requiring each to have a fixed-confidence stopping rule or guarantee.

  2. Allocation and certification. Constants in concentration bounds can make stopping thresholds conservative. However, Section 6 establishes asymptotically optimal separation growth under its assumptions; fixed-budget results assess the practical identification benefit of our allocation.

Reviewer_bAq5OpenReview ↗

To authors

Thank you for the detailed response and additional experiments. The new multitask and robustness experiments address some of my concerns about the scope of the evaluation, and the supplementary analysis clarifies the computational benefits and limitations of the unconstrained surrogate. The experiments primarily use fixed budgets, so the empirical error rate and sample cost of the fixed-confidence stopping rule still need direct evaluation. I therefore maintain my original rating (Weak Reject).

AuthorsOpenReview ↗

Additional prompt-based multitask evaluation on Arena

Thank you again for encouraging evaluation beyond the original two-task setting. We have added prompt-based multitask experiments on Arena (Appendix F.6), complementing the two multitask settings in our earlier response: fully synthetic and Arena-anchored. The new tasks are derived directly from real Arena user prompts by clustering their embeddings, with response features reaggregated within the resulting task–model cells. Compared with the original two-task environment, these settings introduce finer task distinctions, different arrival proportions, more preference reversals, and higher effective dimensions. Multi-FW nevertheless reaches high identification accuracy with fewer comparisons than the baselines in both settings.

Task construction. We retain the same 9,895 comparisons and 15 models as the main experiment. Using only embeddings of the full user prompts, including all user turns, we apply clustering in two ways:

  • Five tasks (1+4): retain code and cluster non-code prompts into four tasks.
  • Six tasks (joint): cluster all prompts into six tasks without imposing the code/non-code partition.

Both partitions retain every comparison and cover all 15 models and all 105 model pairs in every task. We average existing final-response embeddings within the new task–model cells, retain all 384 coordinates, and refit a contextual MNL model for feedback generation. Task-arrival probabilities equal observed task proportions.

Task composition and heterogeneity. The table compares the task-arrival distributions across partitions. Code is listed first in the two- and five-task settings.

EnvironmentTask-arrival probabilities (%)
Original two-task(33.623, 66.377)
Five tasks (1+4)(33.623, 22.688, 11.652, 14.270, 17.767)
Six tasks (joint)(18.828, 11.935, 30.915, 20.101, 12.612, 5.609)

Among the 105 model pairs, 30 and 31 reverse their fitted preference direction across tasks, respectively, compared with 10 originally; all task-specific rankings are distinct within each environment. Effective dimensions increase from 28 to 70 and 84. Thus, the new environments require coordinating comparisons across more tasks with unequal arrival rates and differing preference rankings, while estimating a higher-dimensional parameter.

Identification performance. Each environment is fixed across 100 paired replications at T=1000, using the original four methods and update schedules. The table reports empirical accuracy at 600 comparisons, checkpoint AUC, the first round reaching 80% accuracy, and the first round from which accuracy remains at least 90% through T=1000. Checkpoint AUC averages accuracy at t=50,100,...,1000.

TasksMethodAccuracy at 600Checkpoint AUCFirst 80%Stable 90%
FiveMulti-FW0.9800.860280390
FiveRandom0.8100.729430>1000
FiveMis1H-FW0.8000.653580>1000
FiveMisTTB0.0700.086>1000>1000
SixMulti-FW0.9500.821340450
SixRandom0.7400.694690>1000
SixMis1H-FW0.7900.666610>1000
SixMisTTB0.1500.158>1000>1000

Multi-FW exceeds the strongest baseline in checkpoint AUC by 13.1 and 12.7 percentage points. Only Multi-FW satisfies the stable-90% criterion within the budget, from 390 and 450 comparisons onward. Relative to the fastest baseline, comparison-budget savings are 34.9% and 44.3% at 80% accuracy, and at least 61% and 55% for stable 90%, for five and six tasks, respectively. Its advantage persists at T=1000: accuracies are 99% and 97%, compared with baseline maxima of 87% and 86%. Multi-FW therefore retains its identification advantage across both prompt-based partitions despite finer task distinctions, changed arrival proportions, and increased preference heterogeneity.

In the revised manuscript, we provide the full protocol, diagnostics, and accuracy curves in Appendix F.6. Moreover, we have updated the supplementary code to include the frozen task assignments and environments, construction pipeline, and scripts for reproducing and analyzing these experiments.

AuthorsOpenReview ↗

Additional empirical evaluation of fixed-confidence identification

Thank you for emphasizing the need to evaluate stopping reliability and sample cost directly. In response, we have added Appendix G: Empirical Evaluation of Stopping Rules, complementing the horizon-wise accuracy curves with an evaluation of the fixed-confidence identification objective. We adopt practical thresholds in place of the theoretical thresholds to assess the finite-sample trade-off between stopping reliability and comparison cost. Below, we first present online stopping experiments (Appendix G.2), followed by retrospective replay (Appendix G.1). Both show more correct stops, higher accuracy conditional on stopping, and lower observed comparison cost for Multi-FW.

1. Online evaluation of practical stopping rules (Appendix G.2)

We run 100 paired online replications in the six-task joint-prompt Arena environment of Appendix F.6. Multi-FW, Random, and Mis1H-FW require a unique estimated best model and use practical separation and minimum-eigenvalue thresholds C = 1 and η = 0.001. Estimates are updated and stopping is checked every 50 comparisons, with a safety cap of 2,000. MisTTB completes its native scan without a cap, using δ = 0.20 and ε = 0.25; we additionally evaluate ε = 0.375, chosen to yield approximately 2,000 comparisons. Its ε controls both batch length and the replacement criterion.

Accuracy at stopping is conditional on having stopped. Mean comparisons average min(τ, 2000) over all runs for the three capped methods; unstopped runs remain censored. The MisTTB rows report complete native scans.

MethodCorrect stopsIncorrect stopsNot stoppedAccuracy at stopping (%)Mean comparisons ± SE
Multi-FW981199.0509.5 ± 24.1
Random6023896.81396.5 ± 58.8
Mis1H-FW5863690.61079.5 ± 74.6
MisTTB (ε = 0.25)5842058.04494.0 ± 0.0
MisTTB (ε = 0.375)3565035.02002.0 ± 0.0

Within the same 2,000-comparison limit, Multi-FW correctly stops in 98 runs, compared with 60 for Random and 58 for Mis1H-FW. Its accuracy among stopped runs is also higher: 99.0%, versus 96.8% and 90.6%. Its mean capped cost of 509.5 comparisons is 52.8% lower than Mis1H-FW's 1079.5 and 63.5% lower than Random's 1396.5. The two MisTTB configurations attain 58% accuracy after 4,494 comparisons and 35% after 2,002, illustrating their accuracy–cost trade-off under the evaluated parameter settings.

2. Retrospective evaluation on stored trajectories (Appendix G.1)

We also replay 100 previously collected paired trajectories in the same environment, each observed through 1,000 comparisons. We record the first checkpoint with a unique estimated best model and separation exceeding C = 1, without imposing the theoretical minimum-eigenvalue condition. The outcome columns follow the same definitions; mean capped cost now averages min(τ, 1000) over all 100 runs, with unstopped runs contributing 1,000 and remaining censored.

MethodCorrect stopsIncorrect stopsNot stoppedAccuracy at stopping (%)Mean capped cost
Multi-FW942497.9460.9
Random3036790.9867.9
Mis1H-FW66112385.7569.2

Within the same comparison limit, Multi-FW successfully completes identification in 94 runs, compared with 30 for Random and 66 for Mis1H-FW. Its accuracy among stopped runs is also higher: 97.9%, versus 90.9% and 85.7%, respectively. Its mean capped cost of 460.9 comparisons is 19.0% lower than the lowest-cost baseline, Mis1H-FW (569.2), and 46.9% lower than Random (867.9).

3. Scope and closing remarks

We acknowledge that C = 1 was selected through an exploratory threshold sweep and then held fixed for the online evaluation, and that these results do not certify the theoretical δ-correctness guarantee. Nevertheless, both evaluations provide direct evidence of Multi-FW's practical advantages: more correct stops, higher accuracy conditional on stopping, and lower observed comparison cost. We hope this additional evidence helps address your remaining concern about stopping reliability and sample cost, and we would be grateful if you could take it into account in your final assessment.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.