Cost-Accuracy Frontiers for LLM Agents Are Estimated, Not Observed

Cost-accuracy Pareto frontiers have become the standard way to compare large language model agents, displacing scalar accuracy. The plot has been adopted; the statistics have not. A published frontier is a point estimate of a random set, yet it is drawn and read as though observed, with no interval, no membership probability, and typically a single rollout per task. We formalize frontier reporting as an estimation problem and give an estimator: a bootstrap over the correct resampling unit, membership and dominance probabilities in place of binary flags, a Hausdorff confidence band for the frontier as a curve, and a split-sample correction for selection bias. We validate it against known ground truth across ten generative families, then on real per-task results from 135 agent submissions to SWE-bench Verified (including per-task cost for 38 models under one harness), Terminal-Bench 2.0 (58 submissions, 5 runs/task), and tau^2-Bench (26 submission-domain pairs, 4 runs/task with dollar cost). Four results stand out: (1) Uncertainty quantification changes conclusions: in simulation at five rollouts per task, 17.6% of naive "X dominates Y" claims are false, reduced to 1.3% by certification; on the real frontier, 27% of such claims are not supported at P >= 0.9. (2) The natural two-stage bootstrap over tasks and seeds double-counts within-cell variance and over-covers, with a 1/S signature identifying the cause. (3) Real task suites are clustered: on SWE-bench Verified, respecting repositories widens accuracy intervals 1.94x; task-level resampling covers only 0.654 for generalizing to new repos, while clustering whole repos achieves 0.927. On the leaderboard, only 9 of 105 adjacent rank orderings are supported at P >= 0.9. (4) Neither cost axis is universally valid: mean cost fails under heavy-tailed difficulty, while median cost carries small-seed bias. We release an open implementation that consumes (config, task, seed, success, cost) tuples from any harness.