acceptodds
Under review as a conference paper at ICLR 2027

Certified Selective Automation of LLM Agent Evaluation

Abstract

Evaluating LLM agents still ends with a human reading trajectories, because the automatic judges that could replace this reading come with no guarantee on how often they are wrong. We ask the operational question directly: what fraction of agent-trajectory evaluation can be handed to a judge, with a certificate that the error rate among auto-decided trajectories stays below a budget ? Answering it on agent corpora runs into a structural obstacle: one task is attempted by many agents, so trajectories arrive in correlated clusters, and the i.i.d. certificates used by existing selective-judging methods can overstate what is safe: on one of our corpora a naive certificate claims 98% automation while its realized error exceeds the budget in 17.5% of task resamples. We introduce a task-level bootstrap certificate that is valid in every regime we test, synthetic and real, while matching the naive certificate's coverage, and we show that the finite-sample cluster-valid alternatives certify nothing at realistic task counts. With the certificate fixed, we study the judge: a 4B logprob judge, fine-tuned and then trained with reject-weighted GRPO, certifies 0.30-0.59 of evaluation on tool-use and web corpora at , is the only judge (among strongly elicited frontier models) that certifies on both headline corpora, and costs two orders of magnitude less per decision than the one frontier configuration that beats it. Certified coverage turns out to be predictable before training from base-rate and discrimination alone (leave-one-corpus-out ), which tells practitioners when certification is achievable and when reinforcement learning will help. Finally, the certificate does double duty as a self-training filter: harvesting pseudo-labels only inside certified regions bounds their contamination by by construction (realized: 0.000-0.041 across six harvests), lets a judge enter an unseen domain with zero target-domain training labels at in-domain strength, and improves the strongest corpus beyond its best supervised judge.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
LLM agents, agent evaluation, LLM-as-a-judge, selective prediction, distribution-free certificates, cluster bootstrap, risk control, conformal prediction, self-training, reinforcement learning

Reviews

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

The paper asks an operational question: what fraction of agent-trajectory evaluation can be handed to an LLM judge with a certificate that the error rate among auto-decided trajectories stays below α? It shows that i.i.d. selective-judging certificates are anti-conservative in the multi-rollout regime agent evaluation actually produces, that finite-sample cluster-valid alternatives certify nothing at realistic task counts, and proposes TASKBOOT, a task-level bootstrap certificate occupying the working regime between invalid and vacuous. Around it: a 4B logprob judge (SFT + reject-weighted GRPO) that is the only judge certifying on both headline corpora at ~100× lower cost than the frontier configuration that beats it on one; a two-parameter ex-ante predictability result; and the certificate reused as a self-training filter with contamination bounded by α.

Critical strengths
  1. Moving judge evaluation from agreement to a certified automation fraction is the language deployment teams need.
  2. Experimental discipline. Task-level splits, CAL-only selection, a single TEST read, failed corpora kept in the main text, and all audits reported.
Critical weaknesses
  1. TASKBOOT's validity is asymptotic: the paper calls it an approximation, not a finite-sample theorem. The small-G violation rate is therefore simulation-backed — twelve task-effect cells plus three adversarial designs, all within the authors' parametric family. The only real-data check at G=32 is a single CAL→TEST audit, and the 17.5% motivating audit has no matched control on TASKBOOT's own threshold; neither can estimate a rate. For cluster structures outside that family, nothing bounds the G≈20–32 rate, so "uniformly safe" is an empirical claim, not a guarantee.
Questions for authors
  1. Can the bridge between population-validity in simulation and audit failure on WEB-M be made quantitative (e.g., relating audit violation rate to DEFF or resampling variance) rather than narrative?
  2. Were frontier judges given any prompt optimization (few-shot, trajectory-aware) before concluding they do not transfer? And unparsed responses are excluded rather than counted against the judge — how sensitive is Table 3 to this choice?
3 comments
AuthorsOpenReview ↗

Gentle follow-up before the discussion closes

Dear Reviewer bN5P,

Thank you again for your positive and constructive review. Before the discussion closes on November 18, we wanted to check whether our response answers your questions. In brief: (W1) TaskBoot's violation rate is now measured on 11 real cluster structures with naive CP as the matched control (TaskBoot worst 3.5% from 50 tasks; naive CP up to 19%), a new lower bound explains why no procedure can be both uniformly valid and useful below about 29 tasks, and a sweep of 104 adversarial settings built on that bound, run this week, keeps the revised certificate within δ in every setting (worst 4.1%; naive CP up to 29.7%; Appendix E); (Q1) the design-effect model predicts naive CP's failure quantitatively (Web-M: observed 0.191, predicted 0.189; Table 8); (Q2) a few-shot, rubric-guided frontier judge with every response parsed still certifies 0 on Tool, so Table 3's conclusion does not depend on how unparsed rows are treated.

If these strengthen your assessment, we would be grateful if you would consider reflecting that in your rating. We are happy to answer any further questions.

Thanks authors for the rebuttal. The revision addresses most of my concerns, and I maintain my weak accept rating.

Dear Reviewer bN5P,

Thank you for reading the revision and for your continued support. Your questions led directly to several of its main additions: the real-data validity study with naive CP as the matched control, the design-effect model of naive CP’s failures (Table 8), and the prompt-optimised frontier baseline with every response parsed. Thank you again for your time and your constructive review.

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

The paper proposes task-level bootstrap calibration to determine how much agent-trajectory judging can be automated at a selective error budget. It combines a 4B SFT/GRPO judge with this procedure, models coverage from base rate and base AUROC, and uses certified regions for pseudo-label harvesting.

Critical strengths
  1. The selective-error formulation and task-level protocol directly address the amount of human work a judge can replace while respecting clustered trajectories.
  2. The empirical study reports substantial SFT gains and useful negative results, including WEB-A second-round self-training degradation.
Critical weaknesses
  1. The strong deployment and contamination guarantees exceed what the approximate bootstrap establishes (p. 3, Eq. 2; p. 5, Algorithm 1; pp. 7-9, including Algorithm 2). At 20 independent task clusters and ICC 0.8, let activation probability be 0.105/0.821, active labels be Bernoulli(0.821), inactive labels be zero, and continuous scores be independent of labels. Population error in every score-selected region is 0.105. With probability (1 - 0.105/0.821)^20 = 0.06477, all calibration tasks are inactive and the bootstrap returns a zero upper error quantile, exceeding the delta=0.05 failure budget at alpha=0.1. This is a limitation on a general finite-task claim, not a reproduction or refutation of the authors' simulations. Appendix D's fixed-threshold realized-error resampling is also distinct from the repeated-calibration population-risk target.
  2. The selected GRPO improvements over SFT are 0.004 on TOOL and 0.025 on WEB-A, with one seed and no paired task-level uncertainty. TOOL's selected arm is symmetric accuracy reward; 0.321 reject-weighted coverage is test-oracle. Reward directions tie on WEB-A, limiting support for the proposed reward direction (p. 6, Table 2; p. 16, Appendix E; p. 18, Appendix H).
Questions for authors
  1. What assumptions exclude the zero-error construction, or what modification prevents certification there? Which claims are asymptotic or empirical, including Algorithm 2's population-risk versus realized-pool statement?
  2. How is confidence maintained when CAL selects a judge and its threshold while Algorithm 1 corrects only across that judge's 40 thresholds? Specify independent certification data or correction across judges, the real-data bootstrap count, and extreme-quantile sensitivity.
  3. Can paired task-level uncertainty be reported for the existing selected-arm comparisons, keeping oracle results separate, to establish whether the reject-weighted reward adds value beyond symmetric RL?
2 comments
AuthorsOpenReview ↗

Follow-up before the discussion closes, with one further check of your construction

Dear Reviewer Sopn,

Thank you again for your detailed review; your construction led to the main theoretical addition of the revision. As the discussion period closes on November 18, we would be grateful if you could check whether our response answers your three questions. In brief:

  • Q1 and W1. We ran your construction exactly: the submitted procedure certifies in 51.4% of trials at G = 20, more than the 6.48% all-inactive event. It is an instance of a new lower bound (Proposition 1, proof in Appendix D). TaskBoot now carries an evidence switch fixed before any real data was examined (worst failure 3.0% over your design and ours), its asymptotic assumptions are stated (Appendix C), its validity under your repeated-calibration population-risk target is measured on 11 real pools (Appendix F), and Algorithm 2 separates population from realized contamination.
  • Q2. TEST certificates are computed on TEST alone; a δ/(40K) correction across arms changes no TEST certificate; every certificate converges by B = 3×10⁴ (Table 14).
  • Q3. No: the reject-weighted reward adds nothing beyond symmetric RL (+.011 [−.017, .020] on Tool at α = 0.1), neither beats SFT, and we withdrew that contribution. The test-oracle .321 is no longer cited.

One further check, run this week (now in Appendix E of the revised PDF). Your construction and the two-point design are two points of one family: a task is active with probability a, an active task's trajectories are errors with probability q, and scores are independent of labels, so every region has error e = a·q and, with e > α, any certification is a failure. We swept the family to test the evidence switch beyond the two designs it was chosen on: q ∈ {0.15, 0.25, 0.5, 0.821, 1} (from errors spread over many tasks to errors concentrated in few), e − α ∈ {0.005, 0.02, 0.05}, α ∈ {0.1, 0.2}, G ∈ {20, 32, 50, 84}, 16 attempts per task; 104 settings, 5,000 trials each, B = 3×10⁴. Worst failure rate over all settings at each G:

G20325084
naive CP29.7%23.2%22.9%22.2%
submitted TaskBoot (no switch)51.5%36.3%23.1%10.8%
revised TaskBoot (switch, k_min = 3)4.1%3.7%3.5%2.8%

The revised procedure exceeds δ in none of the 104 settings. Its worst setting is not the concentrated one the switch targets but q = 0.25, where errors spread over about 8 tasks at G = 20 and the bootstrap itself is used.

We also counted the evidence behind each real certificate. In your design at G = 20 the whole sample holds 2.6 error-bearing tasks in expectation. The certified regions of our trained judges on TEST hold 11 to 18 on Tool at α = 0.1 (23 to 31 at α = 0.2), 6 to 10 on Web-A at α = 0.2, 3 to 6 on the two 32-task corpora, and 3 to 4 on Web-A at α = 0.1, the evidence floor stated in Appendix I.

If these changes address your concerns, we would appreciate it if you would consider updating your soundness and overall ratings. If anything remains open, we will answer promptly before the deadline.

AuthorsOpenReview ↗

Construction, observed on real data at scale

Dear Reviewer Sopn,

A brief addition to our follow-up; details are in the general comment "A pre-registered test on a new corpus" and in Appendix V of the revised PDF.

We ran a test, with predictions and criteria fixed before scoring, on a corpus we had never certified on: SWE-rebench OpenHands rollouts, a 2,500-task population with 10.6 attempts per task. The judges there are weak (AUROC 0.64 to 0.73), so no region is truly certifiable at α = 0.1, and inside the small low-score regions a calibration sample can select, the errors sit in few tasks: a real instance of your construction. Under repeated calibration with the error read on the whole population (2,000 draws per cell), the submitted TaskBoot certifies a region whose error exceeds α in up to 43.4% of calibrations at G = 20 and 18.7% at G = 50. The revised TaskBoot, whose evidence switch was selected before any real data, does so in at most 2.5% of calibrations in every one of 96 cells, from G = 20 to 300.

We also report two predictions that failed: the exact betting certificate certifies nothing on this corpus even at 2,500 tasks, and our certifiability model over-predicted it. Both are stated in the paper.

We would be grateful if you would take this into account in your final assessment.

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

The paper studies selective automation of agent-trajectory evaluation under task-level clustering. It proposes a task-bootstrap procedure for selecting rejection thresholds, trains a small judge using SFT and GRPO, and uses the selected regions to harvest pseudo-labels for self-training.

Critical strengths

The framework is useful: coverage at a specified error budget is more useful for deployment than overall judge accuracy alone. Considering for dependence among trajectories from the same task is also well motivated. I appreciate the task-disjoint splits and the reporting of negative results.

Critical weaknesses

The certification claims exceed the evidence. TASKBOOT is a bootstrap approximation without a finite-sample guarantee. Simulations and held-out audits are good, but do not justify the repeated claims of guaranteed or provable risk control.

The GRPO contribution is weakly supported. Gains over SFT are small, particularly on TOOL (0.293 → 0.297), and reported with one seed and no uncertainty estimates. Simpler alternatives, such as class-weighted SFT, are missing.

Questions for authors

na

2 comments
AuthorsOpenReview ↗

Gentle follow-up before the discussion closes

Dear Reviewer BaiN,

Thank you again for your review. As the discussion period closes on November 18, we would be grateful if you could take a moment to check whether our response resolves your two concerns. In brief:

  • W1, claims beyond the evidence. "Guaranteed", "provable" and "by construction" no longer describe our method anywhere in the revised PDF, and every statement is labelled exact, asymptotic or empirical (new Table 5; the wording before and after is listed in our supplementary comment 1/2). A new lower bound (Proposition 1) shows that no certificate can be both uniformly valid and useful below about 29 tasks, and TaskBoot's validity is measured on 11 real cluster structures: worst violation 3.5% from 50 tasks, against 19% for naive CP.
  • W2, the GRPO contribution. With three seeds, class-weighted SFT and paired task-level intervals, the GRPO gain is indistinguishable from zero (+.005 [−.015, .028] on Tool), so we withdrew GRPO as a contribution and report it as a negative result.
  • One further check, run this week (now in Appendix E of the revised PDF). Across 104 adversarial settings built on the lower bound (errors spread over many tasks to concentrated in few, G from 20 to 84, α ∈ {0.1, 0.2}), the revised certificate exceeds δ in none (worst 4.1%), while the submitted procedure reaches 51.5% and naive CP 29.7%.

If these changes address your concerns, we would appreciate it if you would consider updating your soundness and overall ratings. If anything remains unclear, we will answer promptly before the deadline.

AuthorsOpenReview ↗

One further pre-registered check

Dear Reviewer BaiN,

A brief addition to our follow-up; details are in the general comment "A pre-registered test on a new corpus" and in Appendix V of the revised PDF.

Your first concern was that the certification claims exceed the evidence. The revision states TaskBoot's validity as asymptotic and measures it empirically, so we tested that empirical claim once more, on a corpus we had never certified on, with predictions and pass criteria fixed before scoring. On a 2,500-task population with weak judges, the revised TaskBoot stays within its 5% budget in all 96 cells (worst 2.5%, G from 20 to 300), where the submitted procedure reaches 43.4%. The same test shows what a finite-sample guarantee costs: the exact betting certificate certifies nothing on this corpus even at 2,500 tasks. We report that, and a miss of our certifiability model, in the paper.

We would be grateful if you would consider this in your final assessment.

Comments on the paper

2 comments
AuthorsOpenReview ↗

A pre-registered test on a new corpus (Appendix V of the revised PDF)

To test our empirical claims on data we had never certified on, we wrote down four predictions and one prediction of the certifiability model, with their pass criteria and the analysis protocol, before scoring a new corpus, and ran the test on November 16. We report all five outcomes, including the ones that failed. Appendix V of the revised PDF gives the details.

Corpus. Code-R is the SWE-rebench release of OpenHands rollouts: 67,074 trajectories over 6,306 repository tasks, 10.6 attempts per task on average (up to 34), success rate 0.48, and 72% of tasks with the same outcome in every attempt. Before this test we had only scored 400 of its trajectories with the base judge (AUROC 0.64, the band mentioned in Section 6); no certificate had been computed on it and no judge trained on it. One task split: 1,200 tasks to train the SFT judge (the paper's recipe, seeds 42 to 44), 400 tasks for calibration, and 2,500 tasks (26,522 trajectories, every attempt) as the population. The judges are weak here (AUROC on the population 0.639 base, 0.726 to 0.731 after SFT), which is the regime of Proposition 1 and of Reviewer Sopn's construction.

Validity under repeated calibration on the 2,500-task population: draw G tasks, calibrate, read the selected threshold's error on the whole population; 2,000 draws per cell. Worst violation rate over the 16 cells of each column (4 judges, α ∈ {0.1, 0.2}, two sampling designs):

G20325084150300
naive CP7.0%8.1%7.4%7.6%7.2%8.2%
submitted TaskBoot (no switch)43.4%30.1%18.7%7.8%2.8%1.7%
revised TaskBoot (switch, k_min = 3)1.1%2.5%2.1%1.8%1.1%0.7%
  1. TaskBoot within 5% from G = 50 and within 7% at G = 20 and 32. Holds: worst cell 2.5% over all 96 cells.
  2. Naive CP exceeds δ in some cell, at a rate tracking 1 − Φ(z/√DEFF). The first part holds (31 of 96 cells above 5%, up to 8.2%), and so does the second at α = 0.2 for the trained judges (observed 0.51 to 1.05 times the prediction). At α = 0.1 naive CP almost never certifies here, so the ratio part does not hold there.
  3. The exact betting certificate certifies on the whole population wherever TaskBoot certifies at least 0.05. Fails. At α = 0.2 TaskBoot certifies 0.10 to 0.13 of the population for the SFT judges (realized error 0.15 to 0.16); the betting certificate certifies nothing at 2,500 tasks, nor in any draw of 300 to 1,200 tasks. With a weak judge and regions whose error sits close to α, an exact guarantee needs more than 2,500 tasks, so the figure of about 300 tasks we gave from Tool is not general; Appendix U now says so.
  4. A threshold calibrated on the 400 calibration tasks stays within α on the population. Not testable: no judge calibrates a threshold there at either budget.
  5. Certifiability model, recorded before any SFT score: predicted 0.10 at α = 0.1, observed 0 for every judge, a miss under our criterion. The gates of Section 6 classify this corpus as judge-blind (base AUROC 0.64) and so anticipate no useful certificate; the linear fit over-predicts at its low end. The test also corrects one sentence of Section 6: training lifts a code judge to AUROC 0.73 here, above the 0.53 to 0.65 band we stated, though not far enough to certify at α = 0.1.

What this adds on soundness: on a corpus analysed by a protocol fixed in advance, where the judge is weak enough that the right answer is mostly to refuse, the submitted procedure over-certifies in up to 43.4% of calibrations at G = 20 and the revised one in at most 2.5% at every G from 20 to 300. Section 6, Appendix U and Table 5 are updated accordingly.

AuthorsOpenReview ↗

Summary for the Area Chair before the reviewer-AC discussion

Dear Area Chair,

As the author-reviewer discussion closes, we summarize the reviews, what the revision changed, and where the discussion stands, so that the reviewer-AC discussion can rest on the revised paper (latest PDF of November 17; main text still 9 pages).

Where the discussion stands. Reviewer bN5P (weak accept) replied on November 18 that "the revision addresses most of my concerns" and kept the rating. Reviewers BaiN and Sopn (both 2, soundness 1) have not yet responded to our responses of November 9 or to the follow-ups of November 16 and 17. Both soundness ratings rest on the same two concerns; we list where the revised PDF answers them.

  1. The certification claims exceed what an approximate bootstrap establishes (BaiN W1, Sopn W1 and Q1, bN5P W1).
  • Wording. "Guaranteed", "provable" and "by construction" no longer describe our method anywhere; every statement is labelled exact, asymptotic or empirical (Table 5), and the asymptotic assumptions are stated (Appendix C).
  • Sopn's construction is correct. Run exactly, the submitted procedure certifies in 51.4% of trials at G = 20. We proved it is an instance of a general lower bound (Proposition 1, Appendix D): no procedure is both uniformly valid and useful below about 29 tasks, so any useful certificate at small G must assume something about how errors spread across tasks.
  • The fix. TaskBoot now carries an evidence switch (exact task-level bound when fewer than 3 tasks carry an error), selected by a rule fixed before any real data was examined. Worst failure 3.0% on both adversarial designs (Table 6), and at most 4.1% over 104 settings of the construction's whole family, where the submitted procedure reaches 51.5% and naive CP 29.7% (Appendix E).
  • Validity measured where it can fail, under the repeated-calibration target Sopn asked for: on 11 real cluster structures, 6,000 calibrations per cell, worst violation 3.5% from 50 tasks and 5.1% at 32, against 19% for naive CP (Appendices F and U).
  • A pre-registered out-of-sample test (Appendix V): on a new 2,500-task corpus whose weak judges make it a real instance of Sopn's construction, the revised TaskBoot's worst violation is 2.5% over 96 cells from G = 20 to 300; the submitted procedure reaches 43.4%. Two of the registered predictions failed, and we report them.
  • The price of a finite-sample guarantee. An exact betting certificate with the same target (Appendix U) certifies nothing on any of our test sets; it needs about 300 to 900 tasks on Tool and does not certify at 2,500 tasks on the new corpus. This is why the paper offers an asymptotic certificate with measured validity at the task counts benchmarks provide.
  1. The GRPO contribution is weakly supported (BaiN W2, Sopn W2 and Q3).
  • With three seeds, class-weighted SFT, and paired task-level intervals, GRPO minus SFT is +.005 [−.015, .028] on Tool, and reject-weighted minus symmetric reward is +.011 [−.017, .020]. We withdrew GRPO and the reward direction as contributions and report the RL stage as a negative result (Appendix G). SFT on all labels gains +.040 [.005, .076] and is the recommended recipe.
  • We explain why: with a one-word verdict the GRPO gradient vanishes where the judge is confidently wrong, so GRPO sharpens scores without reordering them, and the certificate sees only the order. Seven further RL configurations aimed at this cause, screened by a rule fixed in advance, do not change the conclusion (Appendix H).
  1. Other questions. Sopn Q2: TEST certificates are independent of CAL selection, a δ/(40K) correction changes no TEST certificate, and every certificate converges by B = 3×10⁴ (Table 14). bN5P Q1: a design-effect model predicts naive CP's failures (Web-M observed 0.191, predicted 0.189; Table 8). bN5P Q2: a prompt-optimised frontier judge with every response parsed still certifies 0 on Tool.

Corrections we found ourselves are reported in the general responses: one table row whose GRPO arm had been chosen on TEST (now CAL-selected), three base-judge certificates withdrawn by the switch, and two CertHarvest claims withdrawn.

What the paper now claims: a certificate for clustered agent evaluation, with a lower bound that explains why small-G validity must be measured and with that validity measured on real and pre-registered data; judges compared by one certified number; a reproducible negative result for RL on one-word judges, with its mechanism; and the certificate as a safe self-training filter. The TL;DR field could not be edited during the rebuttal and still says "provably"; the abstract and PDF no longer do.

We understand that reviewer time is limited. Since both soundness ratings of 1 concern points that the revision answers with completed experiments, we would be grateful if the reviewer-AC discussion could take the revised PDF and our responses into account. Thank you for your time and for handling the paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.