Variance Reduction by Pairing, Interleaving, and Blocking

Two benchmark runs of the same unchanged program rarely produce the same number, and the variation between them is usually larger than the change being evaluated. The response of running each version more times attacks the problem from the wrong side: it divides a variance that has a structure the design can remove outright. Pairing, blocking, and interleaving remove specific components of that structure, and the amount removed determines how many runs the comparison actually needs.

The variance has two components, and only one of them averages down

Consider a comparison in which each version is measured in one long session, and several sessions are run for each version on different days or under different machine states. Each observation can be decomposed into a session-level component, common to every run in that session, and a run-level component within the session. The frequency governor’s state, the memory layout the loader chooses, other tenants on the host, and the temperature of the package are session-level. Interrupt timing, page placement within a run, and scheduling jitter are run-level.

For an unpaired comparison of means with $n$ observations per arm, the variance of the difference is

$$\operatorname{Var}(\bar{B} - \bar{A}) = \frac{2(\sigma_b^2 + \sigma_w^2)}{n}$$

where $\sigma_b^2$ is the between-session variance and $\sigma_w^2$ the within-session variance, assuming balanced sessions. The session component enters with the same weight as the run component, so making sessions more numerous and shorter shrinks both. Making the sessions coincident, by running both versions inside one session, removes $\sigma_b^2$ from the difference entirely, leaving

$$\operatorname{Var}(\bar{B} - \bar{A})_{\text{paired}} = \frac{2\sigma_w^2}{m}$$

over $m$ paired runs. When the session component dominates, which is the common case for anything measured across more than a few minutes, the paired design needs dramatically fewer runs for the same detectable effect.

As arithmetic illustration, take $\sigma_b = 3$ percent and $\sigma_w = 1$ percent of the measured value. The unpaired variance per run is proportional to $2(9+1) = 20$, the paired variance to $2 \times 1 = 2$, so the paired design reaches the same standard error with roughly a tenth of the runs. The figures are illustrative of the structure, not of any particular machine; the general rule is that pairing multiplies the effective sample size by the ratio of total variance to within-session variance.

Why alternation cancels drift but not carryover

The pairing argument requires that the pair’s two measurements be exposed to the same session state. Strict alternation approximates this well when the state changes slowly: a frequency governor drifting over seconds, a background process with a minute-scale schedule, and thermal accumulation all move slowly enough that an A/B/A/B schedule sees nearly the same conditions for both members of each pair.

Slow drift is not the only state that matters. The A run leaves the caches, the branch predictor, the memory allocator, and the operating system’s page state in a condition that the immediately following B run inherits. That carryover is not removed by pairing; it is introduced by it. When A and B share most of their code and data, the carryover favours whoever runs second, so strict alternation converts a random nuisance into a systematic offset.

The standard countermeasures are symmetric scheduling and a settling interval. ABBA scheduling gives each version one run immediately after the other and one run after a gap, so the carryover advantage averages out over the block, and reversing the order on alternate blocks makes it average out in the opposite direction as well. A settling interval between runs, or a fixed amount of untimed work to reach a comparable state, reduces the magnitude of the carryover in exchange for wall-clock time.

def abba_blocks(a, b, blocks):
    """Run order for each block: ABBA on even blocks, BAAB on odd ones."""
    forward = [a, b, b, a]
    return [forward if k % 2 == 0 else forward[::-1] for k in range(blocks)]

Carryover also interacts with the estimator. The per-pair difference is only an unbiased estimate of the version difference if the carryover effect is the same in both directions; the ABBA average removes a first-order effect but not one that scales differently for the two versions, which happens when the versions have different working-set sizes and therefore different residual cache state. The diagnostic is to examine the four cells of the ABBA block separately. A consistent pattern by position rather than by version indicates carryover.

Layout, environment, and other invisible confounds

A version difference can be produced by something no one changed deliberately. The classic demonstration is memory layout: the size of the environment block passed to a process shifts where the stack and heap land, which changes which addresses collide in the cache, and the resulting difference in measured time can be comparable to the effect a benchmark is trying to detect. Link order and the resulting placement of code in the address space produce the same class of effect.

This is a confound in the sense that it is random with respect to the change being evaluated, so repeating the experiment with a randomised layout converts the confound from a bias into part of the variance. That is the design used by measurement environments that randomise heap and stack placement across runs, and the reporting requirement is that the number of randomisations be part of the result. Without randomisation, a single measurement of each version is a single draw from a layout distribution that happens to be fixed by build and environment, and a difference attributed to the code may be a property of where it landed.

The general principle extends to every state variable the harness does not control: the number of environment variables, the size of the command line, the alignment of the loaded binary, the cores the scheduler chooses. Each is a dimension of the experiment’s noise, and each is either randomised or held fixed, sometimes deliberately so that the comparison isolates the code change. Both choices are defensible; leaving the dimension uncontrolled and unmentioned is not.

Blocking with covariates and the use of ratios

Blocking in the statistical sense is the design decision that observations within a block are more alike than observations between blocks, and that comparisons are made within blocks. Sessions are blocks, and pairing is the smallest block. Larger blocks permit covariate adjustment: if each block records its own baseline for a reference workload, the block’s baseline can be used to normalise the version measurements and to estimate the block effect.

The ratio estimator is the practical form of this. Each block measures version A against a reference workload and version B against the same reference, and the reported quantity is the ratio of ratios. The reference absorbs the session-level state, and the estimand becomes the change in the ratio rather than the change in absolute time. This is why benchmark suites normalise to a reference machine and why the published rules for those suites forbid changes to the reference measurement procedure: the reference is carrying the calibration, and losing it costs the comparison its validity.

The estimator’s cost is that a ratio of noisy quantities is biased upward in magnitude, an effect that grows as the denominator’s relative error grows. With a reference whose block-level error is a few percent, the bias is small; with a reference measured once per block and noisy, it is not. A sound implementation reports the block-level reference values so the bias can be assessed rather than asserting that normalisation fixed the problem.

What the design can and cannot fix

The design removes variance that has structure. It does not remove a bias that is present in every run: a harness that always runs version A first and reads a warmed cache during A’s run has a bias that no number of repetitions and no pairing arrangement can average away, because the arrangement is the same in every block. Removing that requires changing the arrangement, which is exactly the ABBA and randomised-order machinery.

It also does not fix a difference in the measurement apparatus. If the two versions are run by different harnesses, or with different clock sources, the comparison includes the apparatus difference. Holding the harness fixed, and running both versions through the same code path, is a precondition for the interval on the difference to mean anything.

The practical consequence is that the effort spent on design pays back in runs not taken. A comparison that narrows the detectable effect by a factor of two through pairing and randomisation costs the same machine time as doubling the run count, and it also removes a bias instead of averaging it, which no amount of repetition achieves. The interval formed on the resulting differences is computed as described in Confidence Intervals for the Difference Between Two Benchmark Runtimes, and the power implied by the reduced variance follows the arithmetic in Power, the Minimum Detectable Effect, and the Cost of Repeated Looks.