Experiment layering (overlapping experiments)

Deep dive

How it works

In: unit id, layers (salt, bucket count, list of experiments with bucket ranges) · Out: per layer at most one (experiment, arm) · State: none per unit; the layer configuration only · Cost: O(L + E) hash and compare, no I/O.

1. Partition parameters into layers: one layer per surface or subsystem, so an experiment names the parameters it overrides and a parameter lives in exactly one layer.
2. Give each layer a random salt and a bucket count B (a few hundred to a few thousand).
3. At definition time give each experiment a bucket range [lo, hi) in its layer and reject overlap: the exclusivity check runs before launch, not in analysis.
4. At request time compute bucket = hash(unit, salt_layer) mod B per layer.
5. Look up the experiment owning that bucket; the arm comes from the position inside the range (first half control, second half treatment, or finer for multi-arm).
6. Merge the overrides of the chosen arms into the parameter set; parameters in different layers cannot conflict.
7. Log (unit, layer, experiment, arm) at exposure and analyze each experiment as an ordinary A/B test over its own bucket range.

Why independence holds. With salts s1 != s2 the two buckets are close to independent uniform draws, so both arms of an experiment in layer 1 see the same mix of layer-2 treatments. That mix shifts both arms equally and cancels in the difference if effects are additive; variance rises a little, bias does not.

Domains and launch layers (Tang et al., from memory). Traffic is first split into a domain that takes part in the overlapping layers and domains reserved for experiments that cannot overlap. A launch layer carries ramp-ups of decided changes so launches do not queue behind tests.

Interactions. Overlap is the default. Put two experiments in one layer when their effects can interact: same parameter, a parameter the other feature depends on, or a metric that moves only when both are on. To detect hidden interaction, split X's effect by arm of Y and test the difference of differences.

Carry-over and bucket reuse. Units that ran a treatment last month have learned, churned or changed taste. A new experiment on the same range and salt inherits them. Re-salt the layer between experiments so the ranges mix again, or run an A/A period on the reused range first. Re-salting reshuffles every running experiment in the layer: never do it mid-test.

Holdouts. A dedicated layer with its own salt keeps a small range of units (often a few percent) free of launched changes for months, to measure the cumulative effect of everything shipped, which no single test can.

Code

Layers with salts, bucket ranges and definition-time overlap rejection, assign, and asserts for exclusivity, uniform fill, cross-layer independence (2x2 chi-square under the 0.001 critical value 10.83, against a shared-salt control) and re-salting; compiled and run in release mode.

use std::time::Instant;
fn mix(mut x: u64) -> u64 { // SplitMix64 finalizer
    x = x.wrapping_add(0x9E37_79B9_7F4A_7C15);
    x = (x ^ (x >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
    x = (x ^ (x >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
    x ^ (x >> 31)
}
struct Exp { name: &'static str, lo: u32, hi: u32 } // owns buckets [lo, hi)
struct Layer { salt: u64, buckets: u32, exps: Vec<Exp> }

impl Layer {
    fn new(salt: u64, buckets: u32) -> Self { Layer { salt, buckets, exps: vec![] } }
    fn bucket(&self, unit: u64) -> u32 { (mix(unit ^ mix(self.salt)) % self.buckets as u64) as u32 }
    /// Definition-time check: ranges inside one layer may not overlap.
    fn add(&mut self, name: &'static str, lo: u32, hi: u32) -> Result<(), String> {
        if lo >= hi || hi > self.buckets { return Err(format!("{name}: bad range")); }
        if let Some(e) = self.exps.iter().find(|e| lo < e.hi && e.lo < hi) {
            return Err(format!("{name} overlaps {}", e.name));
        }
        self.exps.push(Exp { name, lo, hi });
        Ok(())
    }
    /// (experiment index, arm): first half of the range is control (0), second half treatment (1).
    fn lookup(&self, unit: u64) -> Option<(usize, u8)> {
        let b = self.bucket(unit);
        let i = self.exps.iter().position(|e| (e.lo..e.hi).contains(&b))?;
        let e = &self.exps[i];
        Some((i, ((b - e.lo) * 2 / (e.hi - e.lo)) as u8))
    }
}
/// One (layer, experiment, arm) per layer in which the unit falls into an experiment.
fn assign(layers: &[Layer], unit: u64) -> Vec<(usize, usize, u8)> {
    layers.iter().enumerate().filter_map(|(l, ly)| ly.lookup(unit).map(|(e, a)| (l, e, a))).collect()
}
fn chi2(obs: &[f64], exp: &[f64]) -> f64 { obs.iter().zip(exp).map(|(o, e)| (o - e).powi(2) / e).sum() }
/// Pearson chi-square (1 df) of the arms of two layers over units that are in an experiment in both.
fn dependence(a: &Layer, b: &Layer, n: u64) -> f64 {
    let mut t = [0f64; 4];
    for u in 0..n { if let (Some((_, x)), Some((_, y))) = (a.lookup(u), b.lookup(u)) { t[(2 * x + y) as usize] += 1.0; } }
    let (tot, r, c) = (t.iter().sum::<f64>(), [t[0] + t[1], t[2] + t[3]], [t[0] + t[2], t[1] + t[3]]);
    chi2(&t, &[r[0] * c[0] / tot, r[0] * c[1] / tot, r[1] * c[0] / tot, r[1] * c[1] / tot])
}
fn main() {
    const N: u64 = 200_000;
    let mut a = Layer::new(0xA11CE, 1000);
    a.add("rank-v2", 0, 600).unwrap(); a.add("rank-v3", 600, 800).unwrap();
    assert!(a.add("rank-v4", 700, 900).is_err()); // overlap rejected when defined
    let mut b = Layer::new(0xB0B, 1000);
    b.add("ui-redesign", 0, 1000).unwrap();
    let layers = [a, b];
    for u in 0..N { assert_eq!(assign(&layers, u), assign(&layers, u)); } // stable per unit
    // near-uniform fill: 100 buckets, expected 2000 each, 99 df, critical value 148.2 (p = 0.001)
    let (l100, mut fill) = (Layer::new(7, 100), [0f64; 100]);
    for u in 0..N { fill[l100.bucket(u) as usize] += 1.0; }
    let fill_chi = chi2(&fill, &[2000.0; 100]);
    // independence across layers vs a deliberately shared salt (arms become identical)
    let ind = dependence(&layers[0], &layers[1], N);
    let (mut s1, mut s2) = (Layer::new(5, 1000), Layer::new(5, 1000));
    s1.add("x", 0, 1000).unwrap(); s2.add("y", 0, 1000).unwrap();
    let dep = dependence(&s1, &s2, N);
    // re-salting moves ~(1 - 1/B) of units to a different bucket
    let (old, new) = (Layer::new(1, 1000), Layer::new(2, 1000));
    let moved = (0..N).filter(|&u| old.bucket(u) != new.bucket(u)).count() as f64 / N as f64;
    println!("fill chi2 {fill_chi:.1}, independent chi2 {ind:.2}, shared chi2 {dep:.0}, moved {moved:.4}");
    assert!(fill_chi < 148.2 && ind < 10.83 && dep > 100_000.0 && (moved - 0.999).abs() < 0.002);
    let t = Instant::now();
    let acc: usize = (0..5_000_000u64).map(|u| assign(&layers, std::hint::black_box(u)).len()).sum();
    println!("{:.1} ns per assign, 2 layers ({acc})", t.elapsed().as_nanos() as f64 / 5e6);
}

Measured: bucket-fill chi-square 81.7 (99 df, limit 148.2), cross-layer chi-square 0.07, shared salt 200,000 (arms identical), 0.9990 of units moved by re-salting, 62-126 ns per assign over several runs on a loaded Apple-silicon machine (release). The spread comes from the per-call Vec allocation and the linear scan; both can be removed.

Complexity and constants

• Assignment: one 64-bit mix per layer, one mod, a scan over E ranges; use a [u16; B] bucket-to-experiment table for O(1) lookup.
• State: B * 2 bytes per layer; with B = 1000 and 100 layers, 200 KB, shared by all servers and cacheable.
• The exposure log (layer, experiment, arm per unit) is the real byte cost at scale.
• An experiment sees (hi - lo) / B of its layer's traffic, so sizing is the ordinary A/B one on that share.

Efficiency

• Cost: about 60-130 ns per assign for two layers (measured, includes a heap allocation); one hash is a few ns; the rest of the cost is the exposure row you write.
• Levers:
  • bucket table instead of a scan over ranges — O(1) lookup instead of O(E) (design) — E is large
  • log the (layer, experiment, arm) set once per session — one row instead of one per request (design) — many requests per unit
  • evaluate in the client or edge SDK from cached config — no assignment RPC (design; see feature flags) — latency matters
  • variance reduction per experiment — more power from the same traffic share — a pre-period covariate exists
• Naive → standard → state of the art:
  • one experiment at a time, full traffic · queue of weeks, no throughput
  • disjoint traffic slices per experiment · parallel but each gets a small slice
  • layers with independent salts plus a bucket table, definition-time conflict check, holdout layer · all units in many tests, no slice penalty

Implementation notes

• Salt = random 64-bit constant per layer, stored in the layer config; any mixing hash works, but no two layers share one.
• Hash the stable unit id (user, device, account); a session id splits one person over several arms.
• Ramping 1 % to 10 % to 50 % means widening hi while keeping lo, so earlier units stay put.
• Version the layer config and log the version with each exposure so analysis can reconstruct who was where.
• Run the daily sample-ratio check per experiment; a mismatch often means a shared salt or a mid-flight re-salt.

Pitfalls

• Same salt in two layers (copy-pasted config): arms are identical and effects are confounded; run the chi-square of the code on logged data.
• Dependent parameters in different layers: the interaction shows as an unexplained effect.
• Re-salting during a running experiment: units change arm, the analysis is invalid.
• Bucket count too small: a 0.1 % test needs B >= 1000.
• Weekly peeking at the holdout; see sequential testing.

Variants and alternatives

In production

• Google's experiment system, as described by Tang et al. (KDD 2010): layers, domains, launch layers (from memory of the paper).
• Facebook's PlanOut ships namespaces: units hash to segments, each experiment owns segments (Bakshy, Eckles, Bernstein, WWW 2014; code checked).
• GrowthBook SDKs take a namespace (id, range) per experiment, giving mutual exclusion on a shared hash (SDK listing checked).

Implementations

Sources

• D. Tang, A. Agarwal, D. O'Brien, M. Meyer, Overlapping Experiment Infrastructure: More, Better, Faster Experimentation, KDD 2010, pp. 17-26. paper (citation verified in Crossref; the ACM page refused automated access, so the content above is from memory)
• E. Bakshy, D. Eckles, M. S. Bernstein, Designing and Deploying Online Field Experiments, WWW 2014. paper · code
• R. Kohavi, D. Tang, Y. Xu, Trustworthy Online Controlled Experiments, Cambridge University Press, 2020. book