Must the comparison be paired?

Not every bootstrap test is paired, but shared test cases naturally call for paired treatment.

Is bootstrapping the same as permutation testing?

No. Bootstrap resampling and label or assignment permutation construct reference distributions differently.

Does a bootstrap p-value give the probability that A is better?

No. It is a tail probability under the specified testing approximation.

AI Glossary / Statistics and probability / Advanced

Bootstrap test

Definition

A bootstrap test uses resampling to approximate the reference distribution needed for a statistical hypothesis test. In AI evaluation, a paired bootstrap test often compares two systems on the same test cases while preserving their paired results. The resampling and comparison rule must reflect the null hypothesis; simply counting how often one system wins a resample is not a universal testing recipe.

What it means

Suppose system A scores higher than system B on an evaluation dataset. The observed difference may depend partly on which cases happened to be sampled. A bootstrap test explores that sampling variation and asks whether the difference is sufficiently unusual under a specified null hypothesis.
The test concerns a defined metric, population, and evaluation procedure. It does not establish that A is better for every customer, nor does it show that a statistically detectable difference is large enough to matter operationally.

How it works

Calculate the observed score difference, delta = score(A) minus score(B). For paired resampling, draw test-case indices with replacement and use the same indices for both systems. Recalculate the complete metric and its difference for each resample.
One one-sided procedure described in Speech and Language Processing centers the bootstrap differences around the observed difference. It estimates the null-tail probability by counting resamples for which delta-star minus delta is at least delta, equivalently delta-star at least twice delta. This is a particular approximate procedure for testing whether A has an advantage, not a definition covering every bootstrap test.
Specify the tail direction and tie rule in advance. Suitable resampling units, representative evaluation data, and adequate approximation of the relevant sampling distribution remain important. Clustered or dependent cases require a design that respects their dependence.

Three practical examples

A text-classification team compares two systems on the same labeled documents. Each sampled document carries its label and both predictions into a bootstrap resample.
A translation study compares corpus-level scores. The evaluator resamples paired evaluation units and recomputes the corpus metric rather than assuming that averaging sentence-level score differences gives the same quantity.
A support team compares two assistants on shared tasks. When several tasks belong to one customer, the analyst considers customer-level resampling so the test does not treat related tasks as independent evidence.

Think of it this way

Imagine comparing two runners across the same set of courses. When constructing alternative collections of courses, keep both runners' results for each selected course together. Separating their course lists changes the comparison. The hypothesis test then needs a rule for what would count as a surprising advantage under the proposed baseline.

Worked example

Consider four invented classification cases. A's correctness indicators are 1, 1, 1, and 0; B's are 0, 0, 1, and 1. Their accuracies are 3/4 and 2/4, so the observed difference is 1/4, or 0.25. Paired case-level differences are 1, 1, 0, and -1.
Each bootstrap resample draws four case indices with replacement. There are 4 to the fourth power, or 256, equally likely ordered index sequences. The two cases with difference 1 remain separate observations, so their combined selection probability on any draw is 1/2.
For the centered one-sided procedure above, count bootstrap means of at least 2 times 0.25 = 0.50. Since each resample contains four differences, this is equivalent to a resampled sum of at least 2.
Enumerating all 256 sequences gives 104 that satisfy the condition. The approximate bootstrap p-value is therefore 104/256 = 0.40625. At a prespecified 0.05 threshold, this procedure does not reject the null hypothesis. The four-case dataset is deliberately tiny for transparent arithmetic, not a realistic basis for confident system selection.
The count can also be checked using category probabilities. With no -1 draws, at least two +1 draws qualify. Counting the distinct original case choices gives 24 + 32 + 16 = 72 sequences for two, three, or four +1 draws. With one -1 draw, all three remaining draws must be +1, giving 4 times 2 cubed = 32 sequences. Two or more -1 draws cannot qualify. Thus 72 + 32 = 104.
Using the uncentered condition delta-star at least delta instead would count 160 sequences and produce 0.625, answering a different resampling-tail question. Also, 56 sequences lie exactly at delta-star = 0.50. The explicit greater-than-or-equal convention therefore matters in this discrete example.

Illustrative case study

Fictional company Birch Assist compares two document classifiers. Its initial spreadsheet resamples each classifier's results separately, losing the connection between predictions on the same document. The analyst replaces this with paired resampling and documents the metric, null hypothesis, and tail convention.
The team reports the observed performance difference alongside the test result and relevant uncertainty estimates. It also checks whether the test documents cover the intended operating conditions. When evidence is inconclusive, the report recommends a larger, better-targeted evaluation rather than declaring the systems equivalent. This is an illustrative scenario, not a documented company experiment.

Common misconceptions and mistakes

The fraction of resamples in which A beats B is not automatically a valid p-value for every null hypothesis. The reference distribution and centering must be justified.
Resampling test cases from fixed predictions measures test-sample variation. It does not automatically include variation from retraining models or selecting hyperparameters.
A large p-value does not establish equality. A small p-value does not establish a large practical benefit.
Increasing the number of resamples reduces simulation noise; it cannot correct biased labels, inappropriate independence assumptions, or an unrepresentative test set.

Business use

Use a documented bootstrap testing procedure when comparing systems on metrics whose sampling behavior is difficult to analyze directly. Preserve the evaluation structure, define the decision question, and retain the test specification. Combine statistical evidence with effect size, cost, reliability, and the relevance of the evaluation cases to actual use.

Check your understanding

What is the observed accuracy difference?

Answer: 0.25.

What resampled difference meets the centered test's threshold?

Answer: At least 0.50.

How many ordered resamples meet it?

Answer: 104 of 256, giving 0.40625.

Related terms

Learn next

Compare centered bootstrap and permutation tests using simulations with known null populations. Examine how clustering and model retraining change the uncertainty being measured.

Bootstrap

Sources

Jurafsky and Martin, Speech and Language Processing, August 2026 draft, Section 4.11.1, The Paired Bootstrap Test: https://web.stanford.edu/~jurafsky/slp3/4.pdf . Worked cases and the company scenario are original illustrations; the resampling test is an approximation, not an exact finite-sample guarantee.

Previous: Bootstrap error-adjusted single-sample technique Next: Botnet