MetaMetaMeta / TODO_SPRT_EVALUATION.md

Initial public upload from Projekte/MetaMetaMeta

3bc7cb3 verified about 1 month ago

13.5 kB

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:

Accept H0 (null hypothesis) — stop, evidence is clear enough that agent fails
Accept H1 (alternative hypothesis) — stop, evidence is clear enough that agent passes
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:

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:

# 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:

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.

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:

A single benchmark round (one full agent x task matrix) costs more than $50
We run more than 5 agents against more than 10 tasks
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.