Bootstrap confidence intervals for benchmark results

Overview

A benchmark score from one training run is a random draw. A bootstrap interval asks how much that score would move if the runs were repeated. The method resamples the observed scores with replacement, recomputes the statistic on each resample, and reads the interval from the spread of those values 2108.13264 §4.1. The three papers below agree on the idea but differ on what is resampled and what conclusion the interval is meant to support.

The first is the data split. Each replicate draws a new train/validation/test split by bootstrap, and the score is recomputed on it [arxiv:2103.03098 app. Our bootstrap procedure]. The second is the runs themselves. Each replicate redraws the runs for every task, so an aggregate such as a median or interquartile mean gets its own interval 2108.13264 §4.1. The third is the tasks. An agent benchmark fixes a set of tasks and reports a pass rate per configuration. Its interval resamples at the task level, so it reflects how much the rate would move with another set of tasks 2605.16679 tab. 2 2108.13264 app. A.5.

Variants

Percentile bootstrap on paired runs, decide A versus B

For methods A and B run on the same seeds and splits, compute the fraction of paired runs in which A scores higher. Resample the pairs, and take the percentile interval of that fraction 2103.03098 eq. 9 [arxiv:2103.03098 app. Confidence interval]. The paper declares A significant when the lower bound is above 0.5, and meaningful when the upper bound is above γ = 0.75 2103.03098 app. Statistical test with P(A>B). Card: Accounting for Variance in Machine Learning Benchmarks.

Stratified percentile bootstrap over runs

Resample the N runs with replacement, independently for each of the M tasks, so each replicate keeps N runs per task. Apply any aggregate (median, IQM, optimality gap) to each replicate and take the 95% percentile interval 2108.13264 §4.1. The paper reports 50,000 resamples for aggregates and 2,000 for profiles and probability of improvement 2108.13264 app. A.5. Card: Deep Reinforcement Learning at the Edge of the Statistical Precipice.

Bootstrap over tasks as well as runs

Resampling the tasks too asks whether the aggregate would change with another set of tasks. The paper says this gives much wider intervals and is optional in its library, used when there are only one or two runs per task [arxiv:2108.13264 app. A.5]. Choose it when the question is about generalising to new tasks.

BCa and m/n intervals

The paper tested basic, bias-corrected and BCa intervals alongside the percentile method. It reports BCa as less effective when there are few runs 2108.13264 app. A.5. The Atari 100k case study uses an m/n bootstrap for its medians, not the recommended stratified percentile method [arxiv:2108.13264 §3].

Task-level percentile bootstrap for agent pass rates

CHI-Bench runs 30 agent configurations on 75 tasks, three trials per task, and reports pass@1, pass@3 and pass^3 with 95% intervals. The intervals come from a task-level percentile bootstrap 2605.16679 tab. 2 2605.16679 §4.2. The paper does not state the number of resamples, or whether the three trials of a task are also resampled. Several pass^3 intervals are reported as [0.0, 0.0], and the paper does not explain them 2605.16679 tab. 2. Card: CHI-Bench.

When to use which

Implementation sketch

Pseudocode for the core loops. All are written in our own words. Neither 2103.03098 nor 2605.16679 gives the resample count for its interval, so K is a parameter here 2103.03098 app. Confidence interval.

# Percentile bootstrap for P(A > B) over paired runs  [arxiv:2103.03098 eq. 9]
# Input:  scores_a, scores_b (same length N, paired by seed and split)
# Output: (lower, upper) bound of the 95% interval

def paired_bootstrap_ci(scores_a, scores_b, resamples=2000):
    # Number of pairs, paired by index  [arxiv:2103.03098 app. Pairing]
    n = len(scores_a)
    estimates = []
    for _ in range(resamples):  # K is not stated in the paper
        # Resample pair indices with replacement  [arxiv:2103.03098 app. Confidence interval]
        idx = random_integers(n, size=n)
        # Fraction of resampled pairs where A is strictly higher  [arxiv:2103.03098 eq. 9]
        estimates.append(mean(scores_a[i] > scores_b[i] for i in idx))
    # Percentile interval  [arxiv:2108.13264 app. A.5]
    return quantile(estimates, 0.025), quantile(estimates, 0.975)

# Stratified percentile bootstrap for an aggregate  [arxiv:2108.13264 §4.1]
# Input:  scores (N, M) for one method; metric(scores) -> float

def stratified_bootstrap_ci(scores, metric, reps=50000):
    # Shape: runs along the first axis, tasks along the second  [arxiv:2108.13264 §4.1]
    num_runs, num_tasks = scores.shape
    estimates = []
    for _ in range(reps):
        # Resample runs independently for each task  [arxiv:2108.13264 §4.1]
        idx = random_integers(num_runs, size=(num_runs, num_tasks))
        estimates.append(metric(scores[idx, arange(num_tasks)]))
    # 95% percentile interval  [arxiv:2108.13264 app. A.5]
    return quantile(estimates, 0.025), quantile(estimates, 0.975)

Contradictions

• Decision thresholds. The benchmark paper's main text defines significance as P(A>B) minus the lower bound above 0.5, and meaningfulness as P(A>B) plus the upper bound above γ 2103.03098 §4.1. Its appendix tests the lower bound above 0.5 and the upper bound above γ directly [arxiv:2103.03098 app. Statistical test with P(A>B)]. The paper does not reconcile the two forms.
• Significance tests. The RL paper advises against significance tests 2108.13264 §2 remark but gives a significance-style reading of probability of improvement: the probability is above 0.5 with an interval excluding 0.5, or the upper bound is above 0.75 2108.13264 app. A.7. The same 0.75 threshold is used by the benchmark paper for its decision rule 2103.03098 §4.1.
• Origin of the 0.75 threshold. The benchmark paper fits its constants, including γ = 0.75, to five tasks and says generality beyond them is not shown 2103.03098 §4.2. The RL paper cites that paper as the source of the threshold 2108.13264 app. A.7. So the RL paper inherits a value that rests on the first paper's five case studies.
• What is resampled. The benchmark paper resamples data splits and seeds 2103.03098 app. Our bootstrap procedure. The RL paper resamples runs per task 2108.13264 §4.1. CHI-Bench resamples at the task level 2605.16679 tab. 2. All three are called bootstrap, but their intervals answer different questions and are not directly comparable.
• Task resampling: optional or default. The RL paper says resampling tasks as well as runs is optional in its library and is used when there are only one or two runs per task 2108.13264 app. A.5. CHI-Bench resamples tasks with three trials per task 2605.16679 tab. 2 2605.16679 app. F.2. Neither source settles which choice fits agent benchmarks.

Papers

• Accounting for Variance in Machine Learning Benchmarks: percentile bootstrap on paired runs, with a P(A>B) decision rule and a sample-size formula.
• Deep Reinforcement Learning at the Edge of the Statistical Precipice: stratified percentile bootstrap over runs per task, with the interval results for Atari 100k medians.
• CHI-Bench: task-level percentile intervals on pass rates for 30 agent configurations.