| # TODO: SPRT Early Stopping for AgentArena Evaluation |
|
|
| **Origin:** Gemini research suggestion β replace fixed k=3 pass@k with Sequential Probability Ratio Test (SPRT) for cost-aware early stopping. |
|
|
| **Status:** Research/Design β not yet scheduled for implementation. |
|
|
| --- |
|
|
| ## What is SPRT |
|
|
| SPRT (Sequential Probability Ratio Test) is a statistical decision procedure by Abraham Wald (1945). Instead of collecting a fixed sample size and then testing, SPRT tests after each new observation and makes one of three decisions: |
|
|
| 1. **Accept H0** (null hypothesis) β stop, evidence is clear enough that agent fails |
| 2. **Accept H1** (alternative hypothesis) β stop, evidence is clear enough that agent passes |
| 3. **Continue** β not yet enough evidence, run another trial |
|
|
| The test maintains a **likelihood ratio** Ξ that accumulates evidence: |
|
|
| ``` |
| Ξ_n = product of [ P(x_i | H1) / P(x_i | H0) ] for i=1..n |
| ``` |
|
|
| For binary pass/fail outcomes with pass probability p0 (null, agent is bad) and p1 (alternative, agent is good): |
|
|
| ``` |
| # After each run with outcome x_i in {0, 1}: |
| Ξ *= (p1 ** x_i * (1-p1) ** (1-x_i)) / (p0 ** x_i * (1-p0) ** (1-x_i)) |
| |
| if Ξ >= B: β Accept H1 (agent passes), stop |
| if Ξ <= A: β Accept H0 (agent fails), stop |
| else: β Run another trial |
| ``` |
|
|
| The decision boundaries A and B are derived from the acceptable error rates: |
|
|
| ``` |
| A = beta / (1 - alpha) # lower boundary (accept H0) |
| B = (1 - beta) / alpha # upper boundary (accept H1) |
| ``` |
|
|
| Where alpha = Type I error rate (false positive: calling a bad agent good) and beta = Type II error rate (false negative: calling a good agent bad). Typical values: alpha=0.05, beta=0.10. |
|
|
| Wald proved SPRT is optimal β it reaches a decision with the minimum expected number of samples given the error constraints. |
|
|
| --- |
|
|
| ## Why It Matters for AgentArena |
|
|
| Current state in `core/runner.py`, `run_pass_at_k`: |
|
|
| ```python |
| async def run_pass_at_k(self, db, task, agent, k=3) -> list[Run]: |
| group_id = str(uuid.uuid4())[:8] |
| results = await asyncio.gather(*[_single(i) for i in range(k)]) |
| ... |
| ``` |
|
|
| All k=3 runs are fired in **parallel** via `asyncio.gather`. There is no mechanism to skip the third run even if the first two are unambiguous. Every agent-task pair always costs exactly 3x whatever a single run costs. |
|
|
| Concrete waste scenarios: |
|
|
| - **Clear failure:** Agent fails runs 1 and 2. If p_fail is very high, run 3 is paying ~$0.30-0.50 (typical Claude Code run) to confirm what is already statistically obvious. |
| - **Clear pass:** Agent passes runs 1 and 2. Same problem in reverse. pass@k with k=3 needs at least one pass to confirm capability β but if both pass, the marginal value of a third pass is low for ranking purposes. |
| - **Edge cases (1/2 split):** Here k=3 is most valuable and SPRT would correctly continue. |
| |
| At 84 runs across 7 experiments (from eval dashboard), we are not yet at a scale where this pain is acute. But once we run comparative benchmarks across 5+ agents on 10+ tasks, the cost compounds fast. 50 tasks x 5 agents x 3 runs = 750 runs. SPRT might cut that to ~600. |
| |
| --- |
| |
| ## How It Works β Decision Boundaries |
| |
| For AgentArena, sensible defaults: |
| |
| ``` |
| p0 = 0.3 # null: agent solves the task less than 30% of the time β "bad" |
| p1 = 0.7 # alt: agent solves the task more than 70% of the time β "good" |
| alpha = 0.05 # tolerate 5% false positives (bad agent called good) |
| beta = 0.10 # tolerate 10% false negatives (good agent called bad) |
| |
| A = beta / (1 - alpha) = 0.10 / 0.95 β 0.105 # stop β reject H1 |
| B = (1 - beta) / alpha = 0.90 / 0.05 = 18.0 # stop β accept H1 |
| ``` |
| |
| Walk through example β agent that passes 2/3 runs (sequence: pass, fail, pass): |
| |
| ``` |
| Start: Ξ = 1.0 |
| |
| Run 1 β pass (x=1): |
| Ξ *= (0.7 / 0.3) = 2.333 β Ξ = 2.333 (between A and B β continue) |
| |
| Run 2 β fail (x=0): |
| Ξ *= (0.3 / 0.7) = 0.429 β Ξ = 1.000 (between A and B β continue) |
| |
| Run 3 β pass (x=1): |
| Ξ *= (0.7 / 0.3) = 2.333 β Ξ = 2.333 (between A and B β continue, but k=3 reached) |
| ``` |
| |
| Here SPRT does not help β mixed results require all 3 runs. That is correct behavior. |
| |
| Example β clear failure (0/2 runs): |
| |
| ``` |
| Run 1 β fail: Ξ = 0.429 (above A=0.105 β continue) |
| Run 2 β fail: Ξ = 0.184 (above A=0.105 β continue) |
| Run 3 β fail: Ξ = 0.079 (below A=0.105 β accept H0, stop) |
| ``` |
| |
| With these thresholds, even 3 consecutive failures barely cross the boundary. To stop after 2 failures we would need tighter p0/p1 or higher beta. This is a parameter tuning problem. |
| |
| Example with tighter priors (p0=0.2, p1=0.8, alpha=0.1, beta=0.2, Aβ0.22, B=9.0): |
| |
| ``` |
| Run 1 β fail: Ξ = (0.2/0.8) = 0.25 (above A=0.22 β continue) |
| Run 2 β fail: Ξ = 0.25*0.25 = 0.0625 (below A=0.22 β STOP after 2 runs) |
| ``` |
| |
| Tighter priors = earlier stopping = less data per decision. This is the core tradeoff. |
| |
| --- |
| |
| ## Implementation Sketch |
| |
| The fundamental obstacle is that the current implementation uses `asyncio.gather` for parallelism. SPRT is inherently sequential β it cannot decide after run 2 if runs 1, 2, 3 all started simultaneously. |
| |
| Two implementation paths: |
| |
| ### Option A: Sequential SPRT (true early stopping, loses parallelism) |
| |
| Replace the gather loop with a sequential loop that checks SPRT after each run: |
| |
| ```python |
| # In runner.py β new method alongside run_pass_at_k |
|
|
| async def run_sprt( |
| self, |
| db: Session, |
| task: Task, |
| agent: Agent, |
| k_max: int = 5, |
| p0: float = 0.3, # null hypothesis pass rate |
| p1: float = 0.7, # alternative hypothesis pass rate |
| alpha: float = 0.05, |
| beta: float = 0.10, |
| ) -> tuple[list[Run], str]: |
| """ |
| Run agent sequentially, stopping early when SPRT reaches a decision. |
| Returns (runs, decision) where decision is 'h0_reject', 'h1_accept', or 'inconclusive'. |
| """ |
| A = beta / (1 - alpha) # lower boundary β accept H0 |
| B = (1 - beta) / alpha # upper boundary β accept H1 |
| lambda_ratio = 1.0 |
| runs = [] |
| group_id = str(uuid.uuid4())[:8] |
| |
| for i in range(k_max): |
| run = await self._run_single_for_k(db, task, agent, group_id) |
| runs.append(run) |
| |
| x = 1 if run.status == RunStatus.success else 0 |
| lambda_ratio *= (p1 ** x * (1 - p1) ** (1 - x)) / \ |
| (p0 ** x * (1 - p0) ** (1 - x)) |
| |
| logger.info( |
| "SPRT run %d/%d: status=%s, Ξ=%.4f (A=%.4f, B=%.4f)", |
| i + 1, k_max, run.status.value, lambda_ratio, A, B |
| ) |
| |
| if lambda_ratio <= A: |
| return runs, "h0_reject" # agent fails, stop early |
| if lambda_ratio >= B: |
| return runs, "h1_accept" # agent passes, stop early |
| |
| return runs, "inconclusive" |
| ``` |
| |
| Caller in the API endpoint or experiment orchestrator: |
|
|
| ```python |
| runs, decision = await runner.run_sprt(db, task, agent, k_max=5) |
| # Store decision alongside runs for analysis |
| ``` |
|
|
| Tradeoff: loses wall-clock parallelism. If each run takes 90s, 3 sequential runs = 270s vs 90s parallel. For cost-optimized batch evaluation this is acceptable; for live benchmarks it is not. |
|
|
| ### Option B: Hybrid β Parallel batch with SPRT gate |
|
|
| Run 2 runs in parallel first. Check SPRT. If inconclusive, run 1 more (or a second batch of 2). This preserves some parallelism while still saving cost on clear cases. |
|
|
| ```python |
| async def run_sprt_batched( |
| self, db, task, agent, |
| batch_sizes: list[int] = [2, 1, 1, 1], # run 2 first, then 1 at a time |
| p0=0.3, p1=0.7, alpha=0.05, beta=0.10 |
| ) -> tuple[list[Run], str]: |
| A = beta / (1 - alpha) |
| B = (1 - beta) / alpha |
| lambda_ratio = 1.0 |
| all_runs = [] |
| group_id = str(uuid.uuid4())[:8] |
| |
| for batch_size in batch_sizes: |
| # Run batch in parallel |
| batch = await asyncio.gather( |
| *[self._run_single_for_k(db, task, agent, group_id) |
| for _ in range(batch_size)], |
| return_exceptions=True |
| ) |
| # Filter exceptions, update lambda |
| for run in batch: |
| if isinstance(run, Exception): |
| continue |
| all_runs.append(run) |
| x = 1 if run.status == RunStatus.success else 0 |
| lambda_ratio *= (p1**x * (1-p1)**(1-x)) / (p0**x * (1-p0)**(1-x)) |
| |
| if lambda_ratio <= A: |
| return all_runs, "h0_reject" |
| if lambda_ratio >= B: |
| return all_runs, "h1_accept" |
| |
| return all_runs, "inconclusive" |
| ``` |
|
|
| This is probably the right design for AgentArena: run 2 in parallel (quick), check, run a third if uncertain. Best of both worlds. |
|
|
| ### Where to add it |
|
|
| File: `/home/smlflg/Projekte/AgentArena/core/runner.py` |
|
|
| - Add `run_sprt` and/or `run_sprt_batched` as new methods on `Runner` |
| - Keep `run_pass_at_k` unchanged (backward compat) |
| - Add a `sprt_decision` column to the `Run` model or store it in `metrics_json` |
| - The API endpoint that triggers evaluation (wherever `run_pass_at_k` is called) gets a flag: `early_stopping: bool = False` |
|
|
| --- |
|
|
| ## Expected Cost Savings |
|
|
| Assumptions: |
| - Average run cost: $0.40 (Claude Code, mid-complexity task) |
| - k=3 baseline cost per agent-task: $1.20 |
| - Typical outcome distribution at current scale: 40% clearly pass (β₯2/3), 30% clearly fail (β€1/3), 30% mixed |
|
|
| With SPRT batched (2+1 scheme): |
| - Clear pass after 2 runs (call it 30% of cases): saves 1 run = $0.40 |
| - Clear fail after 2 runs (call it 25% of cases): saves 1 run = $0.40 |
| - Inconclusive (45%): runs all 3, no savings |
|
|
| Expected savings per agent-task pair: |
| ``` |
| 0.30 * $0.40 + 0.25 * $0.40 = $0.22 saved per agent-task (out of $1.20) |
| β 18% cost reduction |
| ``` |
|
|
| At scale (50 tasks x 6 agents = 300 agent-task pairs): |
| ``` |
| Baseline: 300 * $1.20 = $360 |
| With SPRT: 300 * $0.98 = $294 |
| Savings: ~$66 per full benchmark round |
| ``` |
|
|
| These numbers are rough. The actual savings depend heavily on the real pass-rate distribution. If most agents are mediocre (lots of mixed 1/3, 2/3 results), SPRT saves little. If agents polarize (clearly good or clearly bad), savings are higher. |
|
|
| The 18% figure in the briefing request assumes a generous distribution. A conservative estimate is 10-12%. |
|
|
| --- |
|
|
| ## Risks |
|
|
| **Reduced statistical power.** SPRT with tight boundaries makes decisions faster but with higher error rates in edge cases. An agent that truly passes 50% of the time (neither clearly good nor clearly bad) might get mislabeled. |
|
|
| **Bias toward early evidence.** If run infrastructure has systematic variance (cold-start latency, model version drift, time-of-day effects), the first 2 runs may not be representative. SPRT assumes i.i.d. observations. AgentArena runs are not perfectly i.i.d. β there can be sandbox setup jitter, API rate limit effects, etc. |
|
|
| **Parameter sensitivity.** The p0/p1 thresholds encode an opinion about what "good" and "bad" means. Wrong priors = wrong decisions. These need to be calibrated empirically from existing run data before deploying. |
|
|
| **Loss of parallelism (Option A only).** Sequential SPRT triples wall-clock time for most cases. For interactive benchmarking this is unusable. Option B (batched) avoids most of this. |
|
|
| **Audit trail complexity.** Experiments with different numbers of runs per agent are harder to compare. Pass@k requires knowing k. If k varies per agent, the formula `pass@k = 1 - C(n-c, k)/C(n,k)` needs adjustment. SPRT outcomes need their own metric column, not overloading pass@k. |
|
|
| **Inconclusive results are a new failure mode.** The current system always produces a definitive pass/fail count. SPRT introduces a third state. The dashboard and ranking logic need to handle this. |
|
|
| --- |
|
|
| ## Decision: Is It Worth Implementing Now? |
|
|
| **Current scale:** 84 runs across 7 experiments. At $0.40/run that is ~$34 total. SPRT would have saved maybe $6. Not meaningful. |
|
|
| **Recommendation: Defer to milestone.** |
|
|
| Implement SPRT when we hit one of these triggers: |
| 1. A single benchmark round (one full agent x task matrix) costs more than $50 |
| 2. We run more than 5 agents against more than 10 tasks |
| 3. We want to add a "fast screening" mode that does a cheap 2-run sanity check before committing to a full k=3 evaluation |
|
|
| Until then, k=3 fixed parallel is simpler, faster wall-clock, easier to reason about statistically, and the cost savings are not worth the added complexity. |
|
|
| **When we do implement:** start with Option B (batched 2+1) as a separate method `run_sprt_batched`. Keep `run_pass_at_k` unchanged. Add a feature flag in the experiment config. Calibrate p0/p1 from existing run data first. |
|
|
| --- |
|
|
| ## References |
|
|
| - Wald, A. (1945). *Sequential Tests of Statistical Hypotheses.* Annals of Mathematical Statistics, 16(2), 117β186. https://doi.org/10.1214/aoms/1177731118 |
| - Wald, A. (1947). *Sequential Analysis.* Wiley. (The textbook β Chapter 3 has the boundary derivation.) |
| - Wikipedia overview (good starting point): https://en.wikipedia.org/wiki/Sequential_probability_ratio_test |
| - MLflow / Statsig implementation references for A/B testing context: https://www.statsig.com/blog/sequential-testing-on-statsig |
| - Python implementation (scipy-compatible): https://github.com/dmarx/sprt β small, readable, MIT license |
| - OpenAI Evals discussion on sequential testing: https://github.com/openai/evals/discussions/780 (community thread, not official) |
| - Chen et al. (2021) HumanEval pass@k formula: https://arxiv.org/abs/2107.03374 β relevant because AgentArena's pass@k is modeled on this; SPRT interacts with how k is defined here |
| |
| --- |
| |
| *Written: 2026-03-19. Revisit when benchmark scale crosses the thresholds above.* |
| |
