Variance Reduction with CUPED and Stratification

Users differ enormously from each other and only slightly because of your feature. A heavy user spends twenty times what a light user spends, in treatment and in control alike. That between-user variation is noise for the purpose of estimating a treatment effect, and it dominates the standard error. Removing the predictable part of it is free sensitivity: the same traffic detects a smaller effect.

CUPED, controlled experiment using pre-experiment data, does this by subtracting a covariate measured before the experiment began (Deng, Xu, Kohavi and Walker, 2013, Improving the Sensitivity of Online Controlled Experiments by Utilizing Pre-Experiment Data, WSDM).

The estimator and where the gain comes from

Let \(Y\) be the metric and \(X\) a pre-experiment covariate, typically the same metric measured over a prior window. Define

Because \(X\) is measured before assignment, it cannot be affected by treatment, so its mean is equal across arms in expectation and subtracting it leaves the treatment effect unbiased. The variance becomes

where \(\rho\) is the correlation between \(Y\) and \(X\). Everything follows from that one term. At \(\rho = 0.7\) variance falls by 51%, equivalent to roughly doubling the sample. At \(\rho = 0.3\) it falls by 9%, which is barely worth the pipeline. On Bing's system the reported variance reduction was around 50%.

The single most important design choice is therefore the covariate. The same metric over the same-length window immediately preceding the experiment is usually the strongest predictor available, and lengthening that window raises \(\rho\) up to a point. Multiple covariates generalise the estimator to a regression adjustment, where \(1-\rho^2\) becomes \(1-R^2\).

Stratification, and how it relates

Stratified sampling assigns treatment within blocks defined by a pre-experiment variable (country, platform, usage decile), guaranteeing balance on that variable rather than leaving it to chance. Post-stratification does the same adjustment after the fact.

The relationship to CUPED is close: both remove variance explained by pre-experiment information, and for a single categorical covariate post-stratification and CUPED with dummy indicators give nearly identical results. Stratifying at assignment additionally removes the chance imbalance itself, which matters most in small experiments where random imbalance on a strong covariate is likely.

When it breaks

The covariate must be pre-treatment, without exception. Using any variable measured during the experiment, however weakly related to the feature, reintroduces the post-treatment conditioning problem and biases the estimate. "The user's session count during the test" is not a CUPED covariate.

New users have no pre-period. A large fraction of traffic on acquisition surfaces has no history, so \(X\) is missing or zero for them and \(\rho\) collapses in exactly the segment that often matters most. Segmenting the adjustment, applying CUPED to returning users and nothing to new ones, is the usual accommodation.

\(\theta\) estimated from the experiment data introduces a small bias. It is \(O(1/n)\) and negligible at typical scale, and it is not negligible in small experiments, where estimating \(\theta\) on pooled data or from a prior period is safer.

Variance reduction does not fix a bad metric. Halving the variance of a metric that does not reflect user value makes it easier to detect changes in something that does not matter. Sensitivity is only as useful as the metric's construct validity.

Ratio metrics need the delta method. Metrics like clicks-per-session have a random denominator, so the variance is not the naive one and CUPED must be applied to the linearised form. Applying it to the ratio directly gives incorrect standard errors, which is a common and quiet implementation error.