Skip to content

Did the distribution move? (optimal transport)

A canary shows mean latency down, and the usual rollout rule would ship it. But latency is a whole distribution, not one number: a change can lower the mean while making the slowest requests (the p99, which service-level objectives are written on) much worse. This page explains how the library compares two whole distributions with one number, the 2-Wasserstein distance, what the related catalog theorem about optimal-transport maps says, and why in one dimension the library's gate is really a distance budget you choose.

It assumes you know what a quantile is. Symbols are collected in How to read these pages.

The question and the product situation

A team canaries a new request-routing policy against control, 500 requests per arm. Two candidates:

  • Canary A makes every request about 3 ms faster.
  • Canary B makes most requests faster but sends some to an overloaded backend: the mean drops by about 19 ms and the p99 gets worse.

A mean-only rule ships both. The question the helper compare_outcome_laws answers is narrower and stricter: did the outcome distribution move by less than a budget you set? If yes, the two distributions are close enough that the mean is an honest summary of the change. If no, someone should look at the quantiles before shipping.

Intuition: the 2-Wasserstein distance in one dimension

Sort both samples. Pair the fastest control request with the fastest canary request, the median with the median, the p99 with the p99, and so on. The 2-Wasserstein distance \(W_2\) is the root-mean-square size of the gaps between those matched pairs, in the same units as the data (here milliseconds).

flowchart LR
    C["control, sorted<br/>q1 q2 ... q99"] -- "match quantile to quantile" --> K["canary, sorted<br/>q1 q2 ... q99"]
    K --> W["W2 = sqrt(mean of squared gaps)"]

Two consequences you can check by hand:

  • A pure shift by \(\delta\) ms (every request \(\delta\) ms faster) gives \(W_2 = \delta\) exactly.
  • A change in shape (wider spread, a heavier tail) adds to \(W_2\) even when the mean barely moves.

Small examples, from uv run python -c "from grounded_decision.compare import w2_1d; ...":

Samples \(W_2\) Why
[0, 1, 2] vs [0, 1, 2.1] 0.0577 one gap of 0.1 out of three: \(\sqrt{0.01/3}\)
[0, 1, 2, 3] vs [0, 3] 0.7071 unequal sizes: each point of the short sample covers half the mass, gaps 0, 1, 1, 0

Worked example

uv run grounded-decision examples outcome_shift

Control is 500 draws from a normal distribution with mean 100 ms and standard deviation 10 ms. Canary A is the same sample shifted 3 ms faster with 0.2 ms of jitter; canary B has mean 85 ms and standard deviation 30 ms. The budget uses tolerance \(\tau = 0.5\) and scale = 50 ms, so the allowed \(W_2\) is \(50 \times 0.5^3 = 6.25\) ms.

Arm Mean p99 \(W_2\) vs control Allowed maps_comparable
control 99.5 ms 124.6 ms
canary A 96.5 ms 121.4 ms 3.00 ms 6.25 ms True
canary B 80.9 ms 146.5 ms 27.29 ms 6.25 ms False

Canary A slid left without changing shape, so the mean-based rollout rule may decide. Canary B lowered the mean but changed shape (its p99 is 22 ms worse), so the automatic rollout is blocked and the quantiles go to a person.

The same gate also blocks a change that is strictly better: shifting the control sample 7 ms faster gives \(W_2 = 7.0 > 6.25\) and maps_comparable=False (compare_outcome_laws(c, c - 7.0, tau=0.5, scale=50.0) on the example's control sample). The gate measures how far the distribution moved, not in which direction. A large uniform speed-up is "not comparable" too; read that verdict as "look before shipping", not "worse".

The precise statement

The catalog theorem is about optimal-transport maps. Fix a source distribution \(\rho\) (here, uniform on a compact convex body with nonempty interior in \(\mathbb{R}^d\)). For a target distribution \(\mu\), the Brenier map \(T_\mu\) is the unique map that pushes \(\rho\) onto \(\mu\) at least total squared displacement. The stability question is: if two targets \(\mu\) and \(\nu\) are close in \(W_2\), how close are their maps? The statement is a Hölder bound

\[ \lVert T_\mu - T_\nu \rVert_{L^2(\rho)} \;\le\; C\, W_2(\mu,\nu)^{1/3}, \]

for all targets supported in one fixed compact set, with \(C\) uniform over them, in every dimension \(d \ge 2\); and the exponent \(1/3\) cannot be improved (three-atom targets on a cube defeat every larger exponent, including the conjectured \(1/2\)).

Read as a budget: to keep the map error at most \(\tau\) you need \(W_2 \le (\tau / C)^3\). The library writes that as \(W_2 \le \texttt{scale}\cdot\tau^3\), with scale standing in for the unknown constant and the units.

Where this result stands

In the wider literature: Hölder stability of Brenier maps with some positive exponent is published (for example work of Mérigot, Delalande and Chazal, and of Delalande and Mérigot, giving exponents such as \(1/6\) and \(1/2\) under various conditions on source and targets). Whether \(1/3\) is the sharp uniform exponent in this setting is, to our knowledge, not settled in the published literature; a square-root rate had been conjectured (Letrouit).

In this project's math catalog (catalog result 374): the one-third bound for \(d \ge 2\) and its sharpness, including a disproof of the square-root conjecture, checked by a Lean statement in the companion math catalog (kept outside this repository).

What this library relies on: only the shape of the budget, \(\tau^3\). See the next section for why, in one dimension, even that is a choice rather than a consequence. Status of every result: Where each result stands.

How the exponent sets the budget

If map error is at most \(C\,W_2^{p}\), keeping it below \(\tau\) needs \(W_2 \le (\tau/C)^{1/p}\). With \(C\) folded into scale, the allowance is \(\texttt{scale}\cdot\tau^{1/p}\). At \(\tau = 0.5\) and scale = 50:

Stability exponent \(p\) Allowance Canary A (3.00) Canary B (27.29)
\(1/3\) (catalog) \(50 \times 0.125 = 6.25\) comparable not comparable
\(1/2\) (square root) \(50 \times 0.25 = 12.5\) comparable not comparable
\(1\) (Lipschitz) \(50 \times 0.5 = 25\) comparable not comparable

A weaker exponent means a smaller allowance for \(\tau < 1\): the \(1/3\) budget is the strictest of the three. On this example all three agree; they would differ for a canary with \(W_2\) between 6.25 and 25 ms.

What the code does, and how it differs from the theorem

grounded_decision.compare.ot_stability:

  • w2_1d(a, b) computes the exact \(W_2\) between two empirical 1-D distributions of any sizes by matching quantiles. With sizes \(n\) and \(m\) it integrates the squared quantile gap over the merged breakpoints \(k/n\) and \(j/m\), so every sample counts. Empty input returns 0. Multi-dimensional input is flattened with ravel(), which is the wrong geometry: pass one scalar outcome.
  • map_tolerance(tau, scale) returns \(\texttt{scale}\cdot\tau^3\).
  • compare_outcome_laws(a, b, tau=..., scale=...) returns w2, tau, allowed_w2_for_map_error, maps_comparable (true iff \(W_2\) is at most the allowance), exponent = 1/3, the catalog pin (lean), and a note.

How this differs from the theorem:

  • In one dimension the theorem has nothing to add. On the real line the optimal map from a fixed reference is the quantile function, and the \(L^2\) distance between two quantile functions is \(W_2\). So the map error equals \(W_2\) exactly; the one-third phenomenon only appears in dimension 2 and higher. The 1-D gate "map error \(\le \tau\)" therefore reduces to "\(W_2 \le \texttt{scale}\cdot\tau^3\)", a distance budget you set by hand. Here it is "\(W_2 \le 6.25\) ms".
  • No map is computed, no constant \(C\) is estimated, and no multi-dimensional \(W_2\) is available.
  • Direction-blind. A large improvement fails the gate just as a regression does (the 7 ms shift above).

Limits and when it matters in practice

Choose the budget in the units of your outcome, directly: "we accept an automatic rollout if the latency distribution moved by at most 6 ms root-mean-square". Then pick scale and tau so that \(\texttt{scale}\cdot\tau^3\) equals that number (for instance tau=1, scale=6.25). Setting a budget is covered in Choose parameters.

For a human reviewer, the interpretable 1-D equivalent is a table of quantile differences (p50, p90, p99, p99.9) between the arms. \(W_2\) summarizes those gaps in one number; the table says which part of the distribution moved and in which direction. When the gate says "not comparable", show that table.

The helper is not part of the decision kernel. If a ship/hold decision should wait when distributions are not comparable, combine the two yourself, as described in Compare outcomes.