ParEvalLayer: When Partial LLM-Agent Evaluations Support a Decision
ParEvalLayer combines coverage and bootstrap tests; three benchmarks match full-evaluation decisions after only 15–25% of tasks.
Key Findings
Methodology
ParEvalLayer consumes paired outcomes from two agents and applies a preregistered policy involving threshold δ, task order, group coverage, error targets, and budget. It emits promote, reject, continue, or abstain. The core statistic is the observed mean paired difference, Δ̂_b; bootstrap resampling estimates tail probabilities, while coverage constraints prevent conclusions from a narrow benchmark slice.
Key Results
- Under the primary policy with δ=0 percentage points, α=0.05 decision-error targets, γ=0.05 coverage-failure target, and η=0.25 abstention target, AppWorld, OSWorld-Verified, and tau-bench reach the completed-record decision after only 15–25% of task outcomes.
- Results vary sharply across benchmarks: SWE-bench Verified requires 90% of tasks; SWE-bench Lite remains excessively unresolved at 95%; and the Terminal-Bench wall-clock analysis still leaves too many comparisons unresolved at a 95% time budget.
- The replay sources contain 552 directed comparisons for SWE-bench Lite, 156 for Verified, 306 for AppWorld, 56 for OSWorld-Verified, and 12 for tau-bench. Positive counts decline as the improvement threshold rises from 0 to 5 and 10 percentage points.
Significance
The paper reframes partial evaluation from reporting an early score to asking whether current evidence supports a defensible decision. This addresses expensive API usage, execution time, sandbox resources, and human inspection in agent testing. It also requires reports to expose rules, coverage, budgets, and unresolved rates, reducing selective-sample optimism and the misleading accuracy of policies that decide only easy comparisons.
Technical Contribution
ParEvalLayer combines paired task differences, stratified coverage, and bootstrap tail tests in a traceable reporting layer. Its minimum group count is r_g(b)=max{1,min{n_g,⌊k_b n_g/N⌋}}. After coverage holds, promote requires Δ̂_b>δ and R_promote≤0.05; reject requires Δ̂_b≤δ and R_reject≤0.05. A sufficient budget additionally requires FPR and FRR≤α, coverage failure≤γ, and abstention≤η.
Novelty
Unlike task-subset or rank-preservation methods, ParEvalLayer does not seek a universally minimal benchmark subset. It asks whether an ongoing two-system comparison is reportable under a specified margin. Its explicit continue and abstain actions, plus replay-based evaluation of error, coverage, and unresolved rates, create a reporting-oriented evidence contract.
Limitations
- Replay of completed public records is not the same as live sequential evaluation; repeated looks at the same run would require a time-uniform boundary beyond the bootstrap rule.
- Source filtering, unequal overlaps, configuration differences, and small samples limit generality; tau-bench has only 12 directed comparisons.
- Bootstrap uncertainty does not solve task-order bias, run-to-run variation, or benchmark representativeness.
Future Work
Future work should study confidence sequences, active but fair task selection, joint cost–accuracy budgets, and prospective online validation across versions and scaffolds. Broader benchmarks should expose resource traces and failures, while decision records should incorporate human-review cost, repeated-run variance, and distribution shift.
AI Executive Summary
Evaluating an LLM agent end to end can consume substantial API budget, wall-clock time, sandbox capacity, and human debugging effort. Yet teams often obtain a partial score long before the benchmark finishes. That score is not necessarily evidence of the final conclusion: early tasks may overrepresent one repository, difficulty split, or application domain, while cheap-first ordering can distort the sample. A policy that decides only easy cases may even look highly accurate while leaving most comparisons unresolved.
Wei-Jung Huang and Bonan Shen introduce ParEvalLayer, a decision layer between task execution and benchmark reporting. It reads paired outcomes for two systems and applies a preregistered improvement threshold, group-coverage rule, bootstrap uncertainty test, error target, and resource limit. For each visible subset it computes D_i=Y_i,A−Y_i,B and the partial mean Δ̂_b. It then returns promote, reject, continue, or abstain. Coverage requirements ensure that repositories, difficulty groups, application groups, or domains are not silently omitted.
Completed-record replay shows strong heterogeneity. AppWorld, OSWorld-Verified, and tau-bench reproduce full-evaluation conclusions after only 15–25% of task outcomes under the 0-point threshold. SWE-bench Verified needs 90%; SWE-bench Lite remains too unresolved at 95%; and Terminal-Bench remains unresolved even with 95% elapsed-time budget. The central lesson is not that every benchmark can be shortened, but that every partial report must state its rule, budget, coverage, and unresolved comparisons.
Deep Analysis
Background
Agent evaluation has moved beyond one aggregate score toward task outcomes, cost, reliability, and environment traces. SWE-bench, AppWorld, OSWorld-Verified, and tau-bench provide multi-system records; infrastructure such as HAL improves execution and logging. However, task-subset work mainly asks whether rankings survive compression, not whether an in-progress comparison already supports a thresholded decision.
Core Problem
A partial score can be unstable because early tasks may omit decisive repositories, difficulty levels, applications, or domains. Cheap-first ordering can create systematic selection bias. If unresolved cases are excluded from accuracy calculations, a method can appear reliable by deciding only easy pairs. The reporting problem therefore requires joint control of decision error, coverage, and unresolved rate.
Innovation
The framework contributes five linked ideas: four explicit actions rather than forced binary labels; preregistered thresholds, budgets, and group requirements; bootstrap tails for uncertainty; completed-record replay for empirical validation; and auditable continue/abstain outcomes. Unlike ranking-preserving subsets, it targets the operational question of whether a current comparison is ready to report.
Methodology
- �� Input: task ID, system ID, outcome, group, provenance, and optional cost or time.
- �� Pairing: on the shared usable set T, compute D_i=Y_i,A−Y_i,B and Δ_full=N^{-1}ΣD_i.
- �� Budget: for observed subset S_b, compute Δ̂_b=|S_b|^{-1}ΣD_i.
- �� Coverage: require r_g(b)=max{1,min{n_g,⌊⌈bN⌉n_g/N⌋}} observations in every nonempty group.
- �� Uncertainty: bootstrap observed differences and calculate R_promote=P(Δ̂*_b≤δ), R_reject=P(Δ̂*_b>δ).
- �� Action: insufficient coverage yields continue or abstain; otherwise Δ̂_b, tail probabilities, and the budget determine promote or reject.
Experiments
The authors perform completed-record replay: later outcomes are hidden, the fixed policy is applied at multiple budgets, and promote/reject are compared with the full-record decision. Task-count analyses use SWE-bench Lite, SWE-bench Verified, AppWorld, OSWorld-Verified, and tau-bench; Terminal-Bench is reserved for elapsed-time analysis. Thresholds are 0, 5, and 10 percentage points; the bootstrap cutoff is 0.05, with α=γ=0.05 and η=0.25.
Results
At δ=0, AppWorld, OSWorld-Verified, and tau-bench match completed conclusions at 15–25% task budget. SWE-bench Verified requires 90%; SWE-bench Lite remains too unresolved at 95%; and Terminal-Bench fails the unresolved-rate target at 95% time budget. Thus early stopping depends on task structure, system separation, coverage, and ordering—not on a universal fraction.
Applications
Evaluation services can stream task outcomes into records containing thresholds, coverage status, margins, bootstrap tails, and actions. This supports model-release gates, scaffold A/B tests, software-repair-agent selection, enterprise cost control, and continuous integration. The system can stop when evidence is sufficient, continue when it is not, or explicitly declare abstention.
Limitations & Outlook
Public replay cannot fully represent live repeated looks, failures, retries, changing configurations, or real stopping behavior. Public records also involve filtering, unequal overlaps, and inconsistent group granularity. Future systems should add sequential confidence boundaries, active sampling, run-level variance, resource fairness, and distribution-shift tests, then validate decisions prospectively across broader agent benchmarks.
Plain Language Accessible to non-experts
Imagine comparing two restaurants. You should not taste the first 25 easy dishes and immediately declare a winner, because the menu may still contain seafood, desserts, and regional specialties. ParEvalLayer is a judge who writes the rules before tasting begins. The judge first checks that every important food category has appeared, then measures how much better one restaurant seems, and finally asks whether that gap could simply be luck.
If the evidence is strong, the judge recommends Restaurant A. If A fails to exceed the required advantage, the judge rejects the claim. If too few categories have been tasted, the judge asks for more dishes; if the budget ends, the judge admits that no conclusion is justified. This prevents the judge from selecting only easy dishes to look accurate.
Some benchmark “menus” need only 15–25% of dishes to reproduce the full verdict, while SWE-bench Verified needs 90% and other sources remain undecidable at 95%. The lesson is not always to taste less. It is to report what was tasted, which rules were used, and how many comparisons still lack an answer.
ELI14 Explained like you're 14
Picture two gaming teams competing across many maps. Team A wins the first few rounds, so you may want to announce the champion immediately. But what if those maps are exactly where A is strongest, while the remaining maps favor B? ParEvalLayer is like a referee who writes the rules before the tournament starts.
The referee asks: Have we played every important type of map? Is A’s lead larger than the required margin? Could the lead just be luck? Bootstrap testing repeatedly reshuffles the games already seen to check how stable the result is. Then there are four possible calls: A is better, A is not better, play more rounds, or the tournament ended without enough evidence.
The surprising part is that AppWorld, OSWorld-Verified, and tau-bench can match the full verdict after seeing only 15–25% of tasks. SWE-bench Verified needs 90%, and SWE-bench Lite can still be undecidable at 95%.
So a half-time score is not automatically the final answer. A trustworthy report must also say which maps were played, what rules were used, how much budget was spent, and how many matchups remain unresolved. That is much fairer than showing one impressive number!
Glossary
ParEvalLayer
A decision layer that reads task-level paired outcomes and determines whether a partial comparison is reportable. It returns promote, reject, continue, or abstain.
The paper’s central framework.
Paired difference
The outcome difference between systems A and B on the same task, D_i=Y_i,A−Y_i,B. Pairing controls for task difficulty and directly measures relative improvement.
The basis of all threshold decisions.
Bootstrap tail
A probability estimated by resampling observed differences with replacement and measuring how often the mean crosses a threshold. It avoids assuming a parametric distribution.
Used for promote and reject uncertainty checks.
Task-group coverage
A requirement that every relevant benchmark group contributes a prescribed number of tasks. It prevents a narrow early slice from supporting a global claim.
Final decisions are blocked when coverage fails.
Completed-record replay
A completed public evaluation is treated as if it stopped early by hiding later outcomes. Partial decisions are then compared with the full-record conclusion.
The main experimental protocol.
Open Questions Unanswered questions from this research
- 1 How should bootstrap thresholds become time-uniform sequential guarantees when a live evaluator repeatedly inspects the same run? The paper identifies this issue but does not test a sequential boundary.
- 2 Can active task selection reduce cost without introducing bias when task difficulty and system capability are correlated? This remains unresolved, especially under cheap-first ordering.
- 3 How representative is replay of real failures, retries, cost volatility, and distribution shift? Prospective online deployments are needed.
Applications
Immediate Applications
Agent A/B evaluation
An evaluation platform can stream paired task outcomes, verify group coverage, and compute bootstrap tails. Instead of showing only a partial score, it reports promote, reject, continue, or abstain together with the unresolved rate.
Continuous integration regression testing
After an agent or scaffold update, a fixed δ and budget policy can compare it with the previous version on shared tasks. Stable improvement stops the run early; ambiguous evidence automatically triggers more tasks or an abstention.
Long-term Vision
Auditable benchmark reporting
Benchmark standards could require thresholds, task order, group coverage, resource budgets, error targets, and abstention rates as metadata. This would make early decisions reproducible and comparable across laboratories.
Abstract
LLM-agent evaluations often produce task outcomes long before the full benchmark run is complete. A partial score is tempting to report, but it does not show whether the observed tasks support the same conclusion as the completed evaluation. Early tasks can omit important parts of a benchmark, running cheaper tasks first can distort the observed sample, and a rule that decides only easy pairs can appear accurate while leaving many comparisons unresolved. We introduce ParEvalLayer, a decision layer that reads paired outcomes for two agent systems and a comparison policy chosen in advance. For each partial run, it records whether the tested agent system is better by the required amount, is not better by that amount, needs more evidence, or should abstain. We evaluate ParEvalLayer by replaying completed public benchmark data as if each evaluation had stopped earlier. At each point, ParEvalLayer applies the policy using only the outcomes observed so far; if it reaches one of the two comparison judgments, we check whether that judgment matches the completed data for the same system pair. With the main comparison rule, three of the public benchmarks reach the same decision as the completed evaluation after observing only 15% to 25% of task outcomes. Other benchmarks require more task outcomes. This variation shows why a partial score alone is not enough: reports should also state the decision rule and how many comparisons remain without a decision.