How Many Tasks Are Enough for Agent Benchmark Decisions? A Replay Analysis of Public LLM Agent Benchmarks

Core Question: Can Partial Evaluation Substitute Full Benchmarking?

Public LLM agent benchmarks (e.g., SWE-bench, AppWorld, tau-bench) typically compare agents only after full task execution—but high evaluation cost incentivizes partial runs. This paper demonstrates that reporting only a ‘X% task completion rate’ does not indicate whether the subset supports identical pairwise decisions (e.g., ranking or win/loss) as the full benchmark.

Methodology: Replay Analysis on Real Task-Level Logs

• Replays completed, publicly available task-level execution records from three major benchmarks: SWE-bench (including Verified and Lite variants), AppWorld, and tau-bench;
• Defines ‘sufficient task budget’ as satisfying all three conditions simultaneously:
• Preserves identical pairwise decisions (i.e., same agent ordering or dominance relation) as the full benchmark;
• Covers all required task groups;
• Leaves ≤ target fraction (here: 0%) of pairwise comparisons unresolved;
• Uses a 5-percentage-point budget grid and identifies the first task fraction where all criteria are met under the strict 0% unresolved threshold.

Key Finding: Task Efficiency Varies Sharply—No Universal Compression Ratio

• AppWorld: First meets all targets at 15% task coverage;
• tau-bench: Requires 25%;
• SWE-bench Verified: Requires 90%;
• SWE-bench Lite: Fails to satisfy all targets even at 95%, under the primary coverage rule.

Practical Recommendation: Five Mandatory Elements for Partial-Evaluation Reports

Any partial-evaluation report must explicitly specify:

• Minimum performance gap required for one agent to be declared superior;
• Task selection strategy (e.g., random, stratified, difficulty-weighted);
• Coverage rule applied;
• Decision rule used (e.g., majority vote, statistical significance threshold);
• Maximum allowable number or fraction of unresolved comparisons.