PaperlayerView exact revision on arXiv

Source-linked AI summary

Certified Selective Automation of LLM Agent Evaluation

Chengguang Gan, Yunhao Liang, Qinghao Zhang, Shiwen Ni

arXiv:2609.34320v1cs.CL

TL;DR

Agent evaluation still depends on human trajectory review, and agreement rates do not establish how much work a judge can safely take over under an error budget. The paper introduces a task-level bootstrap certificate for clustered trajectories and uses it to assess judge coverage. A 4B logprob judge certifies on both headline corpora, and the certificate also gates self-training with bounded contamination.

  • Problem

    Agent judges lack a guarantee on the error rate among auto-decided trajectories, and repeated attempts on the same tasks violate the exchangeability assumed by i.i.d. certificates.

    Source: §1 · p. 1

  • Method

    TASKBOOT applies a task-level bootstrap test over a pre-declared threshold grid with Bonferroni accounting to certify selective automation under task clustering.

    Source: §1 · p. 2, §3 · p. 3

  • Results

    At α=0.1, the 4B logprob judge certifies 0.297 on tool-use and 0.585 on web, and is the only strongly elicited frontier-model comparison judge certifying on both headline corpora.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Certified regions also provide a self-training filter whose pseudo-label contamination is bounded by α, including for entry into an unseen domain with zero target-domain training labels.

    Source: §1 · p. 2

    TASKBOOT's guarantee is asymptotic in the number of task clusters, not a finite-sample theorem, and the empirical protocol does not quantify run-to-run training variance.

    Source: §4 · p. 4, Limitations · p. 9

Abstract

from arXiv · show

Evaluating LLM agents still ends with a human reading trajectories, because automatic judges carry no guarantee on how often they are wrong. We ask the operational question: what fraction of agent evaluation can a judge take over, with a certificate that the error rate among auto-decided trajectories stays below a budget alpha? Agent corpora resist the standard answer: many agents attempt the same tasks, so trajectories arrive in correlated clusters, and the i.i.d. certificates of existing selective-judging methods can overstate what is safe: a naive certificate can claim 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 while matching the naive certificate's coverage; finite-sample cluster-valid alternatives certify nothing at realistic task counts. Under this certificate, a 4B logprob judge trained with SFT and reject-weighted GRPO certifies 0.30-0.59 of evaluation on tool-use and web corpora at alpha=0.1, the only judge, among strongly elicited frontier models, certifying on both headline corpora. Certified coverage is predictable before training from base rate and discrimination alone (leave-one-corpus-out R^2=0.96). Finally, the certificate doubles as a self-training filter: pseudo-labels harvested inside certified regions have contamination bounded by alpha by construction (realized 0.000-0.041 across six harvests), letting a judge enter an unseen domain at in-domain strength with zero target training labels.

1 Introduction

The paper asks how much agent evaluation a judge can safely automate, since agreement with humans does not establish how much work it can take over under a bounded error rate. It introduces a task-level bootstrap certificate and studies judge performance, predictable coverage, and certificate-gated self-training.

1 Introduction

  • Agent evaluation still relies on people reading trajectories because programmatic checkers can mislabel live-website outcomes, while human annotation takes minutes per trajectory.Agreement with humans does not answer how much of the evaluation queue a judge can take over while staying within an error budget.Source: §1 · p. 1
  • The paper defines certified coverage as the largest fraction of trajectories auto-decided while bounding their error rate by α with confidence 1−δ.Auto-decided trajectories can be rejected as failures or released as successes.Source: §1 · p. 1
  • When agents make repeated attempts on shared tasks, correlated outcomes can make an i.i.d. certificate unsafe and finite-sample cluster-valid alternatives certify essentially nothing at realistic task counts.On the most heavily clustered corpus, a naive certificate claimed 98% automation while realized error exceeded budget in 17.5% of task resamples.Source: §1 · p. 1
  • TASKBOOT uses a task-level bootstrap over a pre-declared threshold grid with Bonferroni accounting, matching naive coverage while remaining valid in the tested regimes.The paper reports guarantee violations in at most 1% of synthetic trials down to 20 task clusters, and certification of 0.30–0.84 on real corpora where finite-sample cluster-valid alternatives certified 0.Source: §1 · p. 2
  • At α=0.1, the 4B logprob judge certifies 0.297 on tool-use and 0.585 on web, the only strongly elicited frontier-model comparison judge certifying on both headline corpora.The paper also reports that certified coverage is predictable before training and that the certificate can filter self-training data.Source: §1 · p. 2
  • Across seven corpora, the study reports predictable certified coverage and uses certified regions to harvest pseudo-labels with contamination bounded by α, including in an unseen domain without target-domain training labels.The paper notes that some settings remain uncertifiable, including cases with only thirteen test tasks.Source: §1 · p. 2

2 Related work

Prior work evaluates agent judges mainly through agreement with human labels and develops risk-control guarantees largely for exchangeable instances. This paper focuses on task-clustered agent trajectories and connects certified decisions to judge comparison and self-training.

Judging agent trajectories

  • Existing agent-evaluation remedies improve or prompt evaluators but generally report agreement with human labels; this work instead certifies how much evaluation work a judge can absorb.The cited evaluator approaches include trajectory judges, agentic judges, and process reward models.Source: §2 · p. 2

Selective prediction with guarantees

  • Selective-judging methods for chatbot responses assume exchangeable instances, while agent corpora contain clustered multi-rollout tasks that can make the i.i.d. certificate anticonservative.Finite-sample cluster-aware constructions can collapse to zero coverage at realistic task counts; this paper targets per-trajectory decisions rather than aggregate metrics.Source: §2 · p. 2

Training judges, and judges that train themselves

  • The paper's GRPO stage changes the objective rather than the optimizer, using asymmetric reward aimed at certified coverage and ablating its direction.Prior self-improving systems use heuristic training-data gates, while this work closes a loop in which a deployment certificate gates harvesting, training, and re-certification.Source: §2 · pp. 2–3
  • A certificate-gated self-training loop harvests pseudo-labels with contamination bounded by α, distinguishing the approach from prior heuristic gates and one-shot autolabeling with FDR control.The paper also frames its frontier comparison as sharpening observations about small in-domain judges and post-RLHF frontier-logprob miscalibration.Source: §2 · p. 3

3 Certified selective automation, and why clustering breaks it

The section defines selective automation as thresholding judge scores to route some trajectories to automatic decisions and the rest to humans. Because outcomes cluster by task, the standard trajectory-i.i.d. certificate can overstate safe coverage.

3 Certified selective automation, and why clustering breaks it

  • A selective automation rule uses a reject threshold and a release threshold, sending low scores to auto-rejection, high scores to auto-release, and intermediate scores to a human.The two automated decisions have separate risks: discarded successes on rejection and shipped failures on release.Source: §3 · p. 3
  • Certified coverage is the largest certifiable fraction of evaluation work removed at error budget α and confidence 1−δ; the reject side is the main reported object because it has non-trivial certificates in these corpora.The protocol uses δ=0.05 and α∈{0.1, 0.2}.Source: §3 · p. 3
  • The study covers seven task-split corpora, with calibration data used for hyperparameter selection and a single test read per configuration.Trajectories omit reward and oracle signals so judges must infer outcomes from what agents saw and did.Source: §3 · p. 3
  • Within-task outcome correlations range from ρ=0.25 to 0.81, so resampling trajectories independently can misrepresent uncertainty when many attempts share a task.Table 1 describes corpus-level n, G, success rate π, intra-task correlation ρ, design effect, and effective sample size.Source: §3 · p. 3, Table 1 · p. 4
  • At α=0.2, the i.i.d. certificate covers 98% of WEB-M trajectories but exceeds the error budget in 17.5% of task resamples.WEB-M has ρ=0.80, 32 task clusters, and eight rollouts per task; the procedure's failure is concentrated in the high-correlation, few-task, many-rollout regime.Source: §3 · p. 4

4 TASKBOOT: a task-level bootstrap certificate

TASKBOOT uses task-level resampling to certify selective error while retaining useful coverage on clustered corpora. Its approximate guarantee is assessed through simulations and task-disjoint audits.

4 TASKBOOT: a task-level bootstrap certificate

  • TASKBOOT tests each threshold’s task-resampled selective error over a pre-declared 40-quantile grid, then selects maximal coverage under α with Bonferroni correction δ/|Θ|.It calibrates on grouped task data and uses the bootstrap upper quantile to decide whether a threshold meets the error budget.Source: §4 · p. 4, Figure 3 · p. 5
  • Because bootstrap validity is asymptotic in task count, the authors assess the approximation with known-ground-truth simulations and task-disjoint audits, which all pass.Audits calibrate the selected threshold on CAL tasks and measure realized selective error once on disjoint TEST tasks.Source: §4 · pp. 4–5
  • In 300-trial simulations, TASKBOOT violates its guarantee in at most 1% of trials across tested cells, including 20 tasks, while matching naive coverage within a point.The tested designs varied task correlation and task count; the authors could not construct a regime where TASKBOOT failed.Source: §4 · p. 5
  • On real corpora, TASKBOOT certifies 0.30–0.84 wherever a usable judge exists, while every finite-sample cluster-valid alternative certifies 0.The alternatives certify zero across all seven corpora, with task counts ranging from 7 to 382.Source: §4 · p. 5

5 Judges under the certificate

The paper evaluates judges by certified reject coverage: the fraction of review removed while controlling error. Under TASKBOOT, the trained 4B judge improves coverage on TOOL and WEB-A, while frontier judges and other corpora show important limits.

Judge and training

  • The 4B judge uses a normalized SUCCESS-versus-FAIL next-token probability and is trained with verdict-labeled SFT followed by an asymmetric GRPO reward.The reject-weighted reward penalizes discarding successes more than shipping failures, targeting the reject tail used by the certificate.Source: §5 · p. 6

Scope and practical impact

  • On CODE-O the outcome is absent from the trajectory, WEB-M/WEB-F are already near-perfect, and TERM/CODE-S lack enough tasks to resolve improvements.The authors report roughly 30 reviewer-hours removed per thousand TOOL trajectories and 59 per thousand WEB-A trajectories at six minutes of review each, with error ≤0.1 guaranteed on the removed portion.Source: §5 · pp. 6–7

Reward direction

  • On TOOL, reject-weighted GRPO certifies .321, versus .297 for accuracy and .293 for release-weighted GRPO; on WEB-A, all three arms reach .585.The reject-weighted direction matters most on TOOL, while the strong SFT start on WEB-A leaves the arms at the same plateau.Source: §5 · p. 6

Frontier judges

  • Only the trained 4B judge certifies on both headline corpora among the tested frontier configurations; the strongest reasoning model reaches .704 versus .585 on WEB-A at roughly 100× the inference cost.That model certifies zero on TOOL, and four of six frontier configurations certify nothing anywhere; rank invariance means recalibration cannot repair these failures.Source: §5 · pp. 6–7, Table 3 · p. 7

Main result

  • TOOL coverage rises from 0 to .293 with SFT and .297 with CAL-selected GRPO; WEB-A rises from .510 to .560 to .585, with GRPO > SFT > base on both.The test-oracle TOOL arm reaches .321; CAL independently selects the WEB-A arm the oracle would.Source: §5 · p. 6, Table 2 · p. 7

6 Certified coverage is predictable before training

The section relates certified coverage to a pre-training index combining success rate and base-judge discrimination. It also describes conditions that distinguish settings where training can help from those limited by judgeability, saturation, or sample size.

Index components

  • The index combines (1 −π), the reject side’s raw material, with (2A0 −1), which rescales base discrimination; both factors contribute to prediction.Dropping (1−π) reduces LOOCV R^2 to 0.38, while AUROC alone reaches 0.47.Source: §6 · p. 7

Ex-ante prediction

  • The index (1 −π)(2A0 −1) predicts best certified coverage with leave-one-corpus-out R^2 = 0.96 and mean absolute error 0.039 across seven corpora.The fitted relation uses a=1.08 and b=−0.05; the authors caution that it is an empirical model based on seven points and one seed.Source: §6 · p. 7

When training helps

  • Training gains require judgeable outcomes, room to improve the base judge, and enough effective sample; CODE-O, WEB-M/WEB-F, and TERM/CODE-S fail these conditions, respectively.CODE-O outcomes are in a held-out test suite rather than trajectories; WEB-M/WEB-F have base AUROC 0.983; TERM and CODE-S have neff 30 and 21.Source: §6 · pp. 7–8

7 The certificate as a self-training filter

CERTHARVEST uses certified regions to filter pseudo-labels, bounding their contamination by α while keeping re-certification on untouched human-labeled tasks. It supports transfer without target training labels, but additional rounds can reduce coverage even when contamination remains within budget.

Certified harvesting

  • Across six harvests, realized contamination was 0.041/0.008/0.024/0.000/0.003/0.002, never exceeding the 0.10 budget.Pools contained 914–2,200 trajectories; the certificate bounds contamination by construction.Source: §7 · p. 8

Entering a domain with zero training labels

  • 0.560 certified coverage on WEB-A rose to the in-domain GRPO ceiling of 0.585 after one CERTHARVEST round, with zero WEB-A training labels.On WEB-M, the same judge certified 0.830, matching that in-domain ceiling outright.Source: §7 · p. 8

Certified harvesting

  • CERTHARVEST refuses to harvest when no certificate is available.The process calibrates a certified reject region, labels its contents as failures, retrains, and re-certifies using human-labeled CAL/TEST tasks untouched by pseudo-labels.Source: §7 · p. 8

In-domain growth, and where iteration ends

  • On TOOL, certified harvesting lifted coverage to 0.343 after one round and 0.347 after two, above the best supervised GRPO arm at 0.321.This started from the in-domain SFT judge and used no labels beyond SFT’s.Source: §7 · p. 8
  • On WEB-A, a second round reduced coverage from 0.585 to 0.465 despite contamination staying within budget at 0.024.The authors attribute the decline to selection bias amplified by a small one-sided pool; the α-bound controls error rate, not distribution skew.Source: §7 · p. 8
  • On TOOL, transfer was weak at AUROC 0.794, and CERTHARVEST declined to harvest without a certificate.The authors recommend one round for transfer starts and small pools, iteration only in-domain on large pools; on saturated WEB-M, a round was useless.Source: §7 · p. 8

8 Conclusion

The paper concludes that agent-evaluation judges should be assessed by certified workload reduction, with guarantees that remain valid under task clustering.

8 Conclusion

  • A task-clustering-valid certificate measures how much evaluation work a judge can provably take over, beyond an agreement rate.Source: §8 · p. 8

Limitations

The paper’s evidence has boundaries: its results come from one pre-registered run, and TASKBOOT is asymptotic rather than a finite-sample theorem. The certificate is rank-based, so monotone score recalibration does not change its outcome.

Limitations

  • Every reported number comes from one pre-registered run, so the task bootstrap measures sampling uncertainty over tasks, not training randomness.The protocol fixes task splits by one seed, selects hyperparameters on calibration data, and reads each test set once.Source: Limitations · p. 9
  • TASKBOOT is asymptotic in the number of task clusters, validated by simulation down to 20 clusters but not established as a finite-sample theorem.The certifiability model is fit on seven corpora; naive-certificate anti-conservativeness is demonstrated on one real high-clustering multi-rollout corpus, not universally.Source: Limitations · p. 9
  • Certified release decisions rarely occur at practical budgets in these corpora, so the guarantee mostly removes review of failures.The authors recommend one-round certified self-training; iterating on small one-sided pools reduced coverage despite the contamination bound remaining intact.Source: Limitations · p. 9

A Rank invariance of the certificate

  • Strictly increasing score transformations leave the certificate unchanged because its thresholds, counts, bootstrap ratios, and selected coverage depend only on score comparisons.This applies to the naive and DEFF-corrected certificates as well as TASKBOOT.Source: A Rank invariance of the certificate · p. 12
  • Post-hoc calibration cannot repair frontier judges whose score orderings are wrong; certification needs failures ranked below successes, not calibrated probabilities.SFT and GRPO improve that ranking.Source: A Rank invariance of the certificate · p. 12

B Synthetic validity study

The synthetic study tests certificate validity across task counts and clustered-data regimes, while real-corpus comparisons show that finite-sample cluster-valid alternatives can be too conservative to certify any trajectories.

B Synthetic validity study

  • Each synthetic trial used calibration tasks to select a threshold, then evaluated true selective error on a fresh draw of 150,000 trajectories.The study ran 300 trials per task-count setting across five procedures.Source: B Synthetic validity study · p. 12
  • 0.000 violation rate for TASKBOOT in each of three adversarial designs, with equal coverage to the naive certificate; naive violation rates were 0.003, 0.000, and 0.000.The designs included near-perfect discrimination with low base rate, size–outcome correlation, and heavy-tailed cluster sizes.Source: B Synthetic validity study · p. 12
  • The naive certificate was population-valid in every synthetic regime constructed honestly; its demonstrated failure was the task-resampling audit on real high-ρ data.These findings concern different quantities: the audit measures realized-error dispersion on deployment-like corpora.Source: B Synthetic validity study · p. 12
  • With 300 trials, a true violation rate of 0.05 has standard error approximately 0.013, so TASKBOOT estimates at or below 0.01 are consistent with a true rate at or below budget in every cell.Source: B Synthetic validity study · p. 12

C Cluster-valid baselines on the real corpora

D Certificate audits

Task resampling exposes when the naive i.i.d. certificate exceeds its promised error budget, while TASKBOOT’s task-disjoint audits remain within budget across the reported configurations.

D Certificate audits

  • In WEB-M SFT, task resampling finds budget exceedance in .069 of trials at α=.1 and .175 at α=.2; the naive certificate claims .98 coverage at α=.2 in the high-correlation regime.Other listed corpus–judge pairs exceed δ=.05 at most .032 of the time.Source: D Certificate audits · p. 12
  • Table 6 compares five procedures, including one-per-task and task-Hoeffding tests; the latter estimates task-weighted error, with Bonferroni δ/40 throughout.The passage identifies the comparison setup but does not provide the table’s cell values.Source: Table 6 · p. 13
  • At α=0.1, TASKBOOT’s task-disjoint TEST audits have realized errors of .008–.037 across the listed configurations; at α=0.2, all audits pass, with a maximum of .116.Every deployed threshold in the paper comes from this CAL-to-TEST protocol.Source: D Certificate audits · p. 13

E Full result tables

The reported tables compare certified reject-side coverage across judges and corpora, alongside transfer, harvesting, model-validation, and review-cost analyses. The results also show limits on release-side certification and adaptive harvest stopping.

E Full result tables

  • At α=.2, reject-side coverage reaches .735 on WEB-A with GRPOµ1 and .424 on TOOL with GRPOµ1 (CAL pick); WEB-A frontier CoT reaches .784.Release-side certification is far lower: no corpus certifies at α=.1, and only TOOL SFT has nonzero coverage (.27) at α=.2.Source: E Full result tables · p. 13

F Corpora

  • Task-disjoint corpora combine benchmark-checked tool dialogues, expert-labeled live-web trajectories, reward-labeled MiniWoB++, and SWE-bench-style code-repair data.The rendered trajectories omit rewards, evaluator output, and environment verdicts.Source: F Corpora · p. 14

G Judge prompt

  • The same prompt is used for base scoring, SFT supervision, GRPO rollouts, and trained-judge scoring; the score reads the next-token distribution after VERDICT:.Frontier CoT instead elicits step-by-step reasoning ending in P_SUCCESS=<integer 0-100>.Source: G Judge prompt · p. 14

H Training details

  • The judge is Qwen3.5-4B, LoRA-tuned with SFT and then GRPO; RSI rounds reuse the SFT recipe on source data plus harvested pseudo-labels.Training and scoring disable reasoning; runs use seed 42.Source: H Training details · p. 14

I Leave-one-corpus-out transfer

  • With zero web exposure, WEB-A transfer certifies .560 coverage (AUROC .902); τ2-held-out transfer certifies .045 (AUROC .794).The first result uses a judge trained without any web corpora; the second shows substantially lower transfer to τ2.Source: I Leave-one-corpus-out transfer · p. 15

J CERTHARVEST protocols and the stopping-rule negative

  • On WEB-A, CAL coverage is .514/.389/.486 across rounds 0/1/2, while TEST coverage is .575/.585/.465; the authors recommend a fixed policy over adaptive stopping.CERTHARVEST calibrates the harvest region on half of CAL, trains on source data plus harvested pseudo-labels, then certifies on the other half and TEST.Source: J CERTHARVEST protocols and the… · p. 15, L Cost accounting · p. 16

K Certifiability model: validation

  • The base-rate factor is load-bearing; saturation adds nothing after K is tuned and hurts when fixed, with validation limited to seven corpora.The zero-coverage corpus anchors the low end of the fit.Source: K Certifiability model: validation · p. 15

L Cost accounting

  • At six minutes of review per trajectory, certified coverage saves 29.7 reviewer-hours per thousand TOOL trajectories and 58.5 for WEB-A.The conversion is linear in review time and certified coverage; residual risk on the removed portion is bounded by α.Source: L Cost accounting · p. 15

Related papers

Loading 2609.34320v1…