acceptodds
Under review as a conference paper at ICLR 2027

Which AI Agent Actually Wins? Active Query Generation for High-Confidence Selection

Abstract

Choosing an artificial intelligence (AI) agent for deployment can depend on a small subset of queries that distinguish otherwise similar candidates. These diagnostic queries may be rare and unknown in advance. Evaluating agents on fixed benchmarks or randomly sampled queries can therefore spend much of the evaluation budget on cases that do little to distinguish them. To address this problem, we formulate a framework for selecting the best agent under a limited evaluation budget, by adaptively choosing which queries to evaluate. Within this framework, we propose Diagnostic Agent Selection via Exploration (DASE), which directs evaluation toward distinguishing the most competitive candidates. At each round, DASE identifies the current leader and a challenger, then generates queries likely to distinguish them using previous evaluations. The generator can be adapted to the application, for example by using a large language model conditioned on the evaluation history. DASE selects one of these queries, evaluates all agents on it, and updates its estimates. Theoretically, we provide lower bounds on the number of diagnostic queries selected and the probability of selecting the best agent. Empirically, we evaluate DASE in three settings: simulated agent selection, mathematical reasoning, and clinical decision-making. Across these settings, DASE generally achieves higher best-agent selection accuracy than the tested baselines, particularly at larger evaluation budgets.

Primary area:
foundation or frontier models, including LLMs
Keywords:
AI Agent, Agent Evaluation, Adaptive Query Generation

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_oud4OpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to select the best of K fixed AI agents under a limited evaluation budget, and proposes DASE. In each round, DASE picks a leader and a challenger and generates candidate queries from the evaluation history. It then evaluates all agents on the query with the largest estimated gap plus an uncertainty bonus. The paper gives bounds on diagnostic-query acquisition and correct selection, and runs experiments on a synthetic task, MATH, and clinical decision-making.

Critical strengths
  1. The problem is practical. Agents often differ only on a few rare queries, and the paper formalizes this with pairwise diagnostic regions.
  2. The framework is modular. The theory handles adaptively chosen queries without assuming independence, and the authors state openly that their bounds do not show an advantage over random sampling.
  3. The experiments cover synthetic, math, and real clinical data. The three pool settings (Standard, Small, Restricted) show when generation helps. At larger budgets DASE beats Random by a wide margin (0.484 vs. 0.369 on the clinical task at T=150).
Critical weaknesses
  1. Query generation is never tested on real data. In MATH and the clinical study, “generation” means retrieving items with recorded outcomes from an extra pool, so what it mainly adds is access to more data. Its gains show up mostly in the Restricted Pool, which leaves out the diagnostic region by design. The LLM variant only matches Random (0.340).
  2. The baselines are weak, and the setups favor the method. The paper compares only against Random and a variance-based QBC. Stratified sampling with Neyman allocation, active testing [1], and active model selection for LLMs [2], which the paper itself cites, are all missing. In each study the key difference lines up with one hand-picked feature: Number Theory for the constructed NT-Diagnostic agent, and the pathology label in the clinical features. A simple stratified baseline might recover most of the gain.
  3. The clinical results do not support high-confidence selection. The top two agents differ by 0.0176 on the 500-case reference set, with a paired SE of about 0.022, so which agent is truly best is itself uncertain. The paper also reports no full-information ceiling. Selection accuracy stays below 0.5, and DASE gives no confidence statement for its choice.

References

[1] Active Testing: Sample-Efficient Model Evaluation. [2] Active Model Selection for Large Language Models.

Questions for authors
  1. If a stratified sampler with Neyman allocation used the same features (subject in MATH, pathology in the clinical study), how much of DASE’s gain would remain? Do the results hold without the pathology label and without the constructed NT-Diagnostic agent?
  2. In the clinical study, what accuracy does an oracle reach if it evaluates every admission available for querying? Can the best agent be statistically distinguished from the runner-up on the reference set?
  3. Could you run a small experiment with real generation, such as programmatically generated math problems with checkable answers, and count generation and validation costs in the budget?
1 comment
AuthorsOpenReview ↗

Stratified baselines, oracle ceilings, and real generation

We thank Reviewer oud4 for the concrete experimental questions. We ran all the proposed experiments using the paper's evaluation protocols. The new results appear in blue in the revised manuscript.


Response to Comment oud4-1: Would Stratified+Neyman recover the gain? Do the results hold without the pathology label and without the constructed NT-Diagnostic agent?

Stratified+Neyman. We implemented this baseline using subject metadata on MATH and pathology metadata in the clinical study. Allocations follow nh∝Nhσhn_h \propto N_h \sigma_h, with σh\sigma_h re-estimated from the evaluation history each round. This baseline now appears alongside the other methods in the blue rows of Tables 1-2.

Within-stratum variance is dominated by the many queries on which weak agents disagree. As a result, Neyman allocation does not prioritize the stratum containing the region that separates the leader and challenger. Using the relevant category for stratification therefore does not provide the same benefit as acquisition focused on this pair.

Without the pathology label. In the clinical benchmark, nearly all grouping signal is concentrated in the pathology variable. Removing it leaves the methods with low selection accuracy, typically around 0.3-0.4 at T=150. After removing the pathology indicators, DASE Pool Only achieves 0.505 selection accuracy, exceeding all baselines using this representation. On MATH, we tested both removing the subject indicators and replacing them with text features (revised Appendix D.5). DASE Pool Only reaches 0.928 with the subject indicators removed and 0.878 with text features, compared with 0.860 and 0.850 for Random at T=200. MATH remains informative under these ablations because other feature dimensions retain signal associated with the subject categories. In particular, diagnostic problems concentrate at high difficulty: 27% of Level-5 problems are diagnostic, 3.5 times the Level-1 rate. Difficulty therefore helps locate the diagnostic region even without subject indicators, and DASE Full reaches 0.970 with difficulty as its only feature.

Without the NT-Diagnostic agent (K=4). Selection becomes much easier. The top-2 gap widens from 0.010 to 0.061, the two leading agents differ on over 1,200 problems rather than 168, and every method reaches at least 0.93 at T=200. Random, DASE Pool, and Stratified+Neyman each reach 0.996, while TradQBC reaches 1.000. NT-Diagnostic is designed to create the sparse diagnostic region studied in the paper. When the leading agents differ across many problems, as in this ablation, uniform sampling suffices.


Response to Comment oud4-2: Oracle ceiling and whether the best agent is statistically distinguishable

We computed both quantities using the same clinical evaluation protocol:

Oracle ceiling. An oracle that evaluates all 200 admissions available for querying in a trial reaches 0.491 with the experiments' outcome noise and 0.515 with noiseless lookups. DASE Full reaches 0.484 at T=150, nearly matching the full-query oracle with three quarters of its budget. The oracle result shows that accuracies below 0.5 also occur when every available query is evaluated, reflecting the difficulty of this problem instance. The revised text reports these oracle ceilings alongside the clinical results.

Distinguishability. We now report the calculation raised by the reviewer. On the 500-case reference set, the top two agents differ by 0.018 with a paired SE of 0.022 (z=0.82z=0.82), differing on 119 of the 500 cases. The target k∗k^* is defined by performance on this fixed reference set, so correct selection remains well-defined even when the gap is small relative to noise from sampling subsets. Every method faces the same target under the same noise. The comparison, DASE 0.484 vs. Random 0.369, therefore measures the benefit of acquisition under a common evaluation protocol.


Response to Comment oud4-3: A small experiment with real generation, with generation and validation costs in the budget

We added a real-generation experiment on MATH (revised Appendix D.7). A programmatic generator uses the acquisition's anchors to create problems with automatically verifiable integer answers. We calibrate each template family for difficulty by matching the self-consistency strategy's accuracy on real MATH problems at each level. The GPT-4o-mini strategy agents answer each selected problem live, with each evaluation counting as one unit of the budget TT. We evaluate the calibrated generator over 50 trials, with all baselines replayed on the same seeds. The acquisition steers generation toward the diagnostic region (62% of generated problems are Number Theory), and the calibrated generator matches retrieval, with a +0.200 ± 0.086 paired advantage over Random.

Reviewer_aKkBOpenReview ↗
Rating
3
Confidence
2(+1)
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies best-agent identification among a fixed set of K agents under a budget of T evaluation rounds, with all agents evaluated on a common query each round. It distinguishes an agent's conditional performance on a query from its expected performance under a deployment distribution. The proposed method, DASE, maintains an estimated leader and an uncertainty-adjusted challenger, proposes candidate queries based on their evaluation history, and selects a query using estimated pairwise disagreement plus an uncertainty bonus. The implementation uses a Nadaraya–Watson estimator. The paper analyzes diagnostic-query acquisition and conditions for correct final selection, and evaluates the approach on synthetic sparse-signal data, MATH, and clinical decision-making cases.

Critical strengths
  1. Important and well-motivated problem. Under a limited budget, uniformly sampling deployment queries may be inefficient if differences between competitive agents are concentrated on relatively rare cases. Evaluating all agents on the same query allows direct paired comparisons. The distinction between deployment value and query-level diagnosticity is useful.

  2. A particularly informative synthetic test. The synthetic construction separates large disagreement among weak agents from the smaller region that matters for identifying the best agent. With the Standard Pool at T=500, TradQBC selects 87% of active queries near the two irrelevant outer regions (Appendix D.2) and achieves 0.643 selection accuracy, versus 0.801 for Random and 0.925–0.932 for the three DASE variants (Table 3). This convincingly motivates focusing on a competitive pair rather than maximizing global disagreement.

  3. Promising acquisition strategy and useful ablations. The Pool Only variant is strong when the fixed pool adequately covers informative queries. For example, on MATH with the Standard Pool at T=100, Pool Only reaches 0.826 versus 0.722 for Random and 0.686 for TradQBC (Table 5). The Full/Pool Only/Gen Only comparisons, the restricted-pool settings, and the Union Random baseline help distinguish candidate scoring from candidate access, even if they do not fully isolate all of the claimed benefits of generation.

Critical weaknesses

W1. The selection theory does not fully cover the adaptive algorithm. Theorem 1 allows history-dependent target pairs, but the correct-selection result (Theorem 6) requires an additional estimator-error assumption. The explicit count-to-error argument (Corollary 11) and end-to-end guarantee (Theorem 13) fix the target pair and assume a single diagnostic query type. They therefore do not cover leader–challenger switching for K>2. Proposition 7 bounds NW estimation error under adaptive query locations, but does not establish that DASE outperforms random query sampling. The paper should clarify the scope of its guarantees and whether the conditions are informative at the tested budgets.

W2. Privileged features may make diagnostic retrieval artificially easy. In MATH, NT-Diagnostic is constructed to differ from Self-Consistency only on Number Theory, while retrieval features include problem subject and reference-solution attributes. This provides a strong cue, although it does not reveal the exact diagnostic questions (Table 4). More concerningly, clinical retrieval uses ground-truth pathology labels (Appendix F.5). Cholecystitis drives much of the leading agents' gap, and the generation pool restores access to cases removed from the Restricted Pool. These choices limit how confidently the results generalize to realistic selection without oracle information. Label-free ablations would be valuable.

W3. The independent contribution of generation remains unclear. The pair-focused acquisition rule is promising, but in MATH Standard Pool at T=200, Full (0.900) barely exceeds Pool Only (0.896), and Gen Only (0.844) is close to Random (0.838). Full is not the best DASE variant at any tested Synthetic Standard-Pool budget (Tables 3 and 5). Generation helps in some restricted-pool and clinical settings, but the real-data generator retrieves existing cases rather than creating new ones. Pool exhaustion and candidate access also complicate comparisons, while Gen Only (LLM) matches Random at 0.340 (Table 7). Better-isolated ablations and paired comparisons are needed to establish the additional value of generation.

W4. Presentation could be clearer. Section 4 introduces substantial notation without clearly distinguishing guarantees for changing agent pairs from those relying on fixed-pair or finite-query assumptions. A more direct connection between the theoretical results and the practical algorithm would improve readability.

Questions for authors
  1. For K>2 with a changing leader–challenger pair, which results guarantee correct best-agent selection, and are the stated bounds informative at the experimental budgets?

  2. How do the MATH results change without subject/reference-solution features, and the clinical results without ground-truth pathology labels? Do the generation variants still improve selection in these label-free settings?

  3. Can you report paired uncertainty estimates for Full versus Pool Only and Gen Only versus Random, while accounting for pool exhaustion, extra candidate access, and potentially repeated MATH queries? What improvement is attributable to retrieval or generation rather than the acquisition rule?

1 comment
AuthorsOpenReview ↗

Theory scope, label-free features, and the attribution of generation's contribution

We thank Reviewer aKkB for the careful reading and precise summary of the theory's scope. We address the three questions below using the paper's evaluation protocols. The new results appear in blue in the revised manuscript.


Response to Comment aKkB-1: Which results cover K>2 with a changing pair, and are the bounds informative at the tested budgets?

Theorem 1, Proposition 7, and Theorem 6 allow the leader-challenger pair to change with the evaluation history, including when K>2K>2. Theorem 1 bounds acquisition counts in terms of the coverage and missed-opportunity quantities QBQ_B and LBL_B. Proposition 7 bounds NW estimation error at adaptively selected query locations, and Theorem 6 establishes correct selection under the estimator-error assumption. The fixed-pair results connect these steps: Corollary 11 converts counts to estimation error for finite query types, and Theorem 13 gives an end-to-end guarantee for a single diagnostic type with a Gaussian generator. Corollary 4 provides the fixed-pair count comparison with random sampling. We will state these distinctions at the start of Section 4.

Informativeness at the tested budgets. We evaluated the bounds over 100 synthetic trials at T=500T=500, with B=375B=375 active rounds. Using the paper's constants, the per-round candidate-coverage lower bound is 0.62, compared with a measured coverage of 0.88. The fluctuation term (B/2)log⁡(1/δ)\sqrt{(B/2)\log(1/\delta)} is 23.7, about 6% of the active budget. Substituting the measured QBQ_B and LBL_B into Theorem 1 gives a lower bound of 140 diagnostic queries, compared with 164 observed, reaching about 85% of the measured count. These values show that the bound is informative at the tested budget. A priori control of LBL_B relies on the estimation-error conditions.


Response to Comment aKkB-2: MATH without subject/reference-solution features and clinical without pathology labels. Do the generation variants still improve?

In the clinical benchmark, nearly all grouping signal is concentrated in the pathology variable. Removing it leaves the methods with low selection accuracy, typically around 0.3-0.4 at T=150. After removing the pathology indicators, DASE Pool Only achieves 0.505 selection accuracy, exceeding all baselines using this representation. On MATH, we tested both removing the subject indicators and replacing them with text features (revised Appendix D.5). DASE Pool Only reaches 0.928 with the subject indicators removed and 0.878 with text features, compared with 0.860 and 0.850 for Random at T=200. MATH remains informative under these ablations because other feature dimensions retain signal associated with the subject categories. In particular, diagnostic problems concentrate at high difficulty: 27% of Level-5 problems are diagnostic, 3.5 times the Level-1 rate. Difficulty therefore helps locate the diagnostic region even without subject indicators, and DASE Full reaches 0.970 with difficulty as its only feature.


Response to Comment aKkB-3: Paired uncertainty estimates for Full vs. Pool Only and Gen Only vs. Random

We computed per-seed paired differences on the same trials at the largest tested budgets:

Paired differenceMATH StandardMATH RestrictedClinical StandardClinical SmallClinical Restricted
Full − Pool Only−0.010 ± 0.018+0.128 ± 0.022+0.048 ± 0.018+0.103 ± 0.019+0.094 ± 0.019
Gen Only − Random+0.026 ± 0.020+0.026 ± 0.020+0.052 ± 0.022+0.052 ± 0.022+0.052 ± 0.022
Full − Random+0.048 ± 0.021+0.012 ± 0.021+0.115 ± 0.020+0.082 ± 0.020+0.040 ± 0.021

(Bold: |difference| > 2 paired SEs. Gen Only and Random do not use the fixed pool, so their rows repeat across pool settings.)

These comparisons clarify the contribution of acquisition and generation. On MATH Standard Pool, Full exceeds Random by +0.048, while its difference from Pool Only is close to zero. The gain in this setting is therefore attributable to the acquisition rule. Full also significantly outperforms Pool Only in the small and restricted pool settings shown above, consistent with generation helping when the pool provides limited coverage. Across the reported settings with a positive Full-Pool Only contrast, gains range from +0.048 to +0.128. Union Random does not improve over Random on either benchmark, indicating that wider candidate access alone does not explain the gains (Appendix D.4).

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

The paper looks at how to identify the best agent when the evaluation budget is limited and informative queries are relatively rare. The authors propose DASE, which focuses on comparing the current leading agent with its strongest challenger and uses previous evaluation results to decide which queries to ask next. The paper also provides theoretical analysis of how many diagnostic queries are needed and under what conditions the method can identify the best agent with high confidence. The authors evaluate DASE on synthetic data, MATH, and clinical decision-making tasks, reporting improvements over random sampling and query-by-committee baselines.

Critical strengths

Authors target a practically important setting where diagnostic queries are sparse and costly; frames best-agent selection as an adaptive query generation and acquisition problem centered on a leader-challenger dynamic. I noticed a clean separation of roles, making the method as modular and domain-agnostic. The limitations of the uncertainty proxy are acknowledged well. The evaluations span three diverse domains with a purpose-built synthetic sparse-signal setup, mathematical reasoning , and clinical decision-making.

Critical weaknesses

The main acquisition bound (Theorem 1) depends on exogenous conditional coverage Q_B and missed opportunities L_B; control of these terms hinges on additional assumptions that are only partially instantiated (e.g., a specific Gaussian generator and finite query spaces). The result is insightful but not tight; novelty on the theory side is moderate. The uncertainty proxy is not a calibrated confidence interval.

I find that baselines are limited. Only random sampling and a classic pool-based query-by-committee are included. Missing are stronger pool-based active testing. For example sequential halving, continuously reject, GapE/UCB-E variants tailored to pure exploration, model-based active testing or information-theoretic acquisition. Given the paper’s ambition, broader comparison are required. Also in real-data studies, “generation” is approximated by retrieval from a separate pool with recorded outcomes, which is a practical proxy but stops short of testing actual generative query synthesis quality and downstream validation cost. The small LLM-guided selection ablation is promising but limited.

Questions for authors
  • How sensitive is DASE to the choice of hyperparameters? Could you provide a sensitivity plot or heuristic/default setting guidance, especially for high-dimensional features?
  • In the clinical study, the feature vector includes the ground-truth pathology label. Can you report results for feature sets that exclude this label to reflect realistic pre-evaluation information, and quantify the performance drop.
  • I find comparison against stronger pure-exploration baselines. What challenges arise in adapting them? Some comparison to those suggested example baselines is required to see the effect of DASE.
  • How does DASE behave when the leader–challenger pair changes frequently due to small gaps? Are there mechanisms to stabilize targeting or to avoid oscillations?
1 comment
AuthorsOpenReview ↗

Hyperparameter sensitivity, label-free features, stronger baselines, and pair stability

We thank Reviewer gttL for the detailed review. Below, we address all four questions with new experiments using the paper's evaluation protocols. The new results appear in blue in the revised manuscript.


Response to Comment gttL-1: Sensitivity to hyperparameters and default settings for high-dimensional features

The main hyperparameter is the NW bandwidth hh. We choose its default from the feature geometry. For queries in different categories, the one-hot category blocks contribute a squared distance of 2, giving a kernel weight of exp⁡(−2/(2h2))≈0.02\exp(-2/(2h^2)) \approx 0.02 at h=0.5h=0.5 before accounting for continuous features. In the synthetic study, the default h=0.04h=0.04 matches the width of the diagnostic region. We now report bandwidth sweeps for all three studies (revised Appendix D.6):

StudySweepFinding
Synthetich∈{0.01,...,0.16}h \in \{0.01, ..., 0.16\}, a 16x rangeboth DASE variants exceed Random at every bandwidth at T=500. DASE Full peaks at the default (0.935)
MATHh∈{0.1,...,0.5}h \in \{0.1, ..., 0.5\}the advantage over Random is largest at the default (0.896 vs. 0.838)
Clinicalh∈{0.1,...,0.5}h \in \{0.1, ..., 0.5\}stable over [0.2,0.5][0.2, 0.5]. h=0.2h=0.2 reaches 0.520, above the 0.436 reported in the paper, so the default is conservative

For high-dimensional features, we recommend standardizing them to unit scale before applying the same kernel-weight rule. The remaining constants, c0=0.2c_0=0.2 for the β\beta schedule and δ=0.05\delta=0.05, are shared across all three studies without per-task tuning, with c0c_0 keeping βt\beta_t of order one over the tested budgets and δ\delta setting a nominal 95% confidence level.


Response to Comment gttL-2: Clinical results without the ground-truth pathology label

In the clinical benchmark, nearly all grouping signal is concentrated in the pathology variable. Removing it leaves the methods with low selection accuracy, typically around 0.3-0.4 at T=150. After removing the pathology indicators, DASE Pool Only achieves 0.505 selection accuracy, exceeding all baselines using this representation. On MATH, we tested both removing the subject indicators and replacing them with text features (revised Appendix D.5). DASE Pool Only reaches 0.928 with the subject indicators removed and 0.878 with text features, compared with 0.860 and 0.850 for Random at T=200. MATH remains informative under these ablations because other feature dimensions retain signal associated with the subject categories. In particular, diagnostic problems concentrate at high difficulty: 27% of Level-5 problems are diagnostic, 3.5 times the Level-1 rate. Difficulty therefore helps locate the diagnostic region even without subject indicators, and DASE Full reaches 0.970 with difficulty as its only feature.


Response to Comment gttL-3: Stronger pure-exploration baselines and the challenges in adapting them

We added sequential halving (Karnin et al., 2013) and stratified sampling with Neyman allocation as baselines. Sequential halving uses the same query budget TT, divided across ⌈log⁡2K⌉\lceil \log_2 K \rceil stages, with fresh uniform queries evaluated by the surviving agents at each stage. Stratified sampling uses the same category metadata as the warmup and allocates queries according to the Neyman rule:

Selection accuracySynthetic, T=500MATH, T=200Clinical, T=150
Random0.8010.8380.369
Stratified+Neyman0.7930.8620.394
Sequential halving0.7780.8400.419
DASE (best variant)0.9320.8960.484

DASE achieves higher selection accuracy than both baselines in all three studies. Only the DASE variants exceed Random at every tested budget. Both baselines now appear alongside the other methods in the blue rows of Tables 1-2.


Response to Comment gttL-4: Behavior when the leader-challenger pair changes frequently

We recorded the selected pair at every active round over 100 MATH trials. The true top-2 gap is 0.0094, providing the small-gap setting raised by the reviewer. Pair switching is infrequent and decreases with the budget. For DASE Pool Only, the pair changes at 12% of round transitions at T=100 and 4% at T=200. The fraction of active rounds targeting the true top-2 pair rises from 70% to 86%, and each trial visits an average of only 2.4 of the 10 possible pairs. Two mechanisms support this stability. The challenger is selected using an upper confidence bound with a slowly growing exploration multiplier, and later rounds concentrate on the persistent runner-up. Ties are broken at random. When challengers have similar estimated profiles, the queries that separate them from the leader overlap, so alternating between these pairs loses little information.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.