Variance Reduction Below the Randomization Grain

Sergio Camelo, Caitlin Kearns, Matias Cersosimo, and Tilman Drerup

As artificial intelligence increases the velocity of engineering and science teams, experimental throughput is set to become a bottleneck for many product decisions. Many companies can now build faster than they can experiment, with queues of good ideas running the risk of not being tested because of lack of experimental capacity.

This problem is particularly severe in marketplaces, where the presence of spillover and cannibalization effects between experimental units requires cluster-level randomization techniques. That randomization, in turn, has the unfortunate tendency to substantially reduce statistical power and slow down experimentation. In this post, we show that the predictability of outcomes at fine grains can be exploited to reduce the variance of aggregate metrics, even when experiments themselves are run at a coarse level. Since statistical power depends on metric variability, this yields considerable reductions in experimentation time.

The Interference Problem

In marketplace settings, behavior and outcomes for individual participants are inherently intertwined. In a delivery marketplace like Instacart, for example, the dispatch system solves a bipartite matching problem between shoppers and customer orders. Since assignments are global and interdependent, matching an order to one shopper means that the same order cannot be matched to another shopper. As a result, changing the handling for a single order creates ripples that affect the orders around it. If an experimenter were to assign a treatment intervention to one of these orders while leaving neighboring orders as controls, the latter would evidently be contaminated.

A common response to this problem is to randomize treatments at the level of a cluster, chosen so that interference can stay within it. In food and grocery delivery, that cluster is typically a geographical region. Since every order within a region sees the same treatment, contamination is contained at the regional boundary rather than leaking between treatment and control. The drawback of such region-level designs is that they give us far fewer units of randomization than unit-level designs, and fewer units lead to less statistical power.

One way to recover some of that power is a switchback design. With a switchback design, each region is re-randomized between the treatment and control group every fixed window (typically one day). The unit of analysis then becomes the region-day rather than the region, and the effective sample size grows with the duration of the experiment. This, of course, relies on the assumption that a window’s treatment effect is realized within that same window and does not spill into the next. Still, even with this adjusted design, the effective sample size typically remains small, and power remains an issue. At Instacart, running powered experiments may take months, and for very noisy metrics, may even be entirely infeasible in any reasonable timeframe.

Enter CUPED

One way to recover some of the lost power is CUPED (Deng, Xu, Kohavi, and Walker [2013]), layered on top of a switchback design. The intuition behind CUPED is that if the outcome metric has a component that can be predicted from pre-treatment features, then subtracting that predictable component removes noise without removing the treatment effect, thus making the effect easier to detect. Let’s make this concrete.

Throughout, subscript k indexes a region-day observation. Suppose we run a switchback experiment and we observe an outcome metric Yₖ for region-day k. Let Zₖ be a vector of pre-treatment features for that region-day, and let Xₖ = f(Zₖ) be a prediction of Yₖ built from those features, where f is fit on pre-treatment data. We form the CUPED-adjusted outcome:

This adjusted outcome has the same expectation as Yₖ, so it can be used to estimate the treatment effect without introducing bias, while its variance is reduced by a factor of 1 − ρ², where ρ is the correlation between Yₖ and Xₖ. The better Xₖ predicts the outcome, the larger the variance reduction, and therefore the shorter the experiment needed to detect a given effect size.

This naturally leads to the following question: How good can this predictor get? A key limitation of CUPED under interference is that the predictor Xₖ must be built at the coarsest level of randomization. At the region-day level, the features available — day of week, average basket size, shopper supply, weather — all capture broad patterns but miss the specific mix of orders that land in a region on a given day. However, for a metric like late-delivery percentage, most of the variation comes from order-level characteristics, e.g., where each delivery is going, what is in the cart, what window the customer chose. Averaging those away before building the predictor discards the signal that would make it useful. In many experiments, we have found that standard CUPED constrained to region-day predictors can cut variance by up to 10% after controlling for geo- and day-fixed effects. That is a good start, but not enough to meaningfully shorten experiment duration.

Order-Level CUPED

While we cannot experiment at the order level, we still have access to plenty of order-specific information that we know drives our metrics. If order-level outcomes are what we ultimately aggregate into our metrics, why not predict at that level and aggregate the predictions the same way? This keeps the structure of CUPED intact and allows us to take into account order-specific covariates by training a suitably-chosen machine learning model.

Concretely, our methodology works in two steps: First, we train an order-level model g that predicts each order’s outcome, ŷᵢ = g(zᵢ), using only features zᵢ available before the fulfillment system acts on the order. Second, we aggregate this model’s predictions up to the region-day grain using the same aggregation the metric itself uses (e.g., a mean, for a metric like late-delivery percentage):

The aggregated prediction Ŷₖ then becomes Xₖ in the CUPED adjustment from the previous section: it is a pre-treatment prediction of Yₖ, now informed by order-level detail that a region-day feature could not capture.

A Word of Caution

Before we go to the results, one word of caution is necessary to ensure that the expected variance reduction does not come with an increase in bias for the treatment effect. When estimating the first step regression, every feature used by the order-level model must be unaffected by the treatment. In predicting an order’s lateness, features like items in the cart, chosen delivery option, store location, time of day, and weather are safe because they are fixed before any fulfillment algorithm acts on the order. Features like the shopper assigned to the order or how many orders that shopper handles on the same trip are off the table because they are downstream of the treatment. The distinction matters because some of the forbidden features may be the best predictors of the outcome, and therefore the most tempting to add.

This assumption is essential, and we can test it. To do so, we run a mean difference test on Ŷₖ, the prediction built from pre-treatment features, in place of the real outcome Yₖ. Since Ŷₖ depends only on pre-treatment features, its estimated treatment effect should be statistically indistinguishable from zero. If it is not, something in the feature set is being moved by the treatment, and the variance-reduced estimate cannot be trusted for that experiment.

The plot below illustrates this in three experiments, reporting for each the variance reduction from order-level CUPED alongside the placebo test that flags feature contamination. In our marketplace, for example, we experiment with improved versions of the models that predict the ETA of an order, which affects the ETA shown to users before they place an order, so they can make an informed decision. This shifts the distribution of orders placed, and the placebo test correctly flags this as contamination.

Results: Experimentation Speed-Up

We tested the method across 10 experiments aimed at reducing order lateness, one of Instacart’s highest priorities. For each experiment, we trained a Gradient Boosted Tree to predict whether an order would be late. Our models fit the data fairly well, with expected features doing the heavy lifting in the prediction, including weather and basket size.

We then did a side-by-side comparison of standard CUPED with region-day features and order-level CUPED with order-level features. The gap is stark. Order-level CUPED cuts variance by 18 to 40%, more than 3 times the 5 to 10% reduction we get from only applying region-day CUPED.

These reductions in variance have immediate and notable effects on experimentation velocity, allowing us to cut experimental runtimes by about a third on average. This added velocity allows us to run more experiments per quarter and rapidly identify improvements in the algorithms that power our marketplace, including the models that ensure that customers get their groceries on time.

Wrapping Up

When the unit of randomization is coarser than the unit of observation, small effective sample sizes tend to slow down experimentation. In this post, we showed how building predictions at finer grains, in our case order-level, and aggregating them up can recover variance that standard region-day CUPED leaves on the table. The move is counterintuitive at first, since interference is exactly why we randomize coarsely and avoid order-level outcomes in the first place. The crux of our solution is that the predictions only ever enter through a pre-treatment covariate, leaving the estimates unbiased. As our results above show, this change can have meaningful effects on experimental power and velocity.

Importantly, the presented approach is not specific to the delivery context. In settings where interference forces randomization into coarse clusters (like with graph clusters in social networks, keyword groups in ad auctions, or geographic markets from lodging to dating), outcomes are still observed on a much finer unit than the one being randomized. That gap is exactly what the proposed method exploits, and its underlying idea should be directly applicable.