Stratified sampling for an eval set

Sampling from real traffic fixes the problem of a set that measures a model's idea of the problem. It does not fix what the sample is of. A random sample — every conversation in the window equally likely to be drawn — reproduces the traffic mix faithfully, which is exactly the property you want when estimating a population average and exactly the wrong one when the behaviour you most need to measure occurs in a fraction of a percent of conversations.

This chapter is about allocating a fixed labelling budget across a population that is not uniform in how much you care about its parts. The technique is stratified sampling: divide the population into strata — subgroups drawn so that the members of each one are alike in the way that matters — and sample each stratum separately, at a rate you choose.

Why a uniform draw misses the rare-and-severe slice#

The arithmetic is unforgiving and takes one line. If an event occurs in 0.3% of conversations, the chance that 200 independent draws contain none of it is 0.997 raised to the 200th power, which is 0.55. A coin flip. Drawing 200 more conversations next month gives another coin flip, and the two months together still leave a 30% chance of never having seen the pattern.

Each step in that line is worth having rather than accepting. An event occurring in 0.3% of conversations means one conversation drawn at random contains it three times in a thousand, so one conversation drawn at random misses it nine hundred and ninety-seven times in a thousand. That miss rate written as a proportion is the 0.997 in the line above. Two draws both miss when the first misses and the second also misses, and the chance of two independent things both happening is the product of their separate chances, so two draws miss with 0.997 times itself. Two hundred draws miss with 0.997 multiplied by itself two hundred times, which is what raising it to the 200th power means. That product is 0.55. The 30% for two months is the same operation once more: 0.55 for the first month times 0.55 for the second.

The word carrying that whole calculation is independent, and it is a condition rather than a decoration. Two hundred conversations pulled from a single Tuesday morning are not two hundred independent draws from the month. They share a promotion, a carrier outage and one shift of support agents, and if the pattern you are hunting rides on any of those, the true chance of seeing none of it is higher or lower than 0.55 with nothing in the number itself to say which. Where a sample is drawn from is a premise of the arithmetic, not a detail of how it was gathered.

Suppose you get lucky and the sample contains one. One case gives a per-pattern rate of 0/1 or 1/1, and neither number can distinguish a bug that fires half the time from one that fires always. To get to five expected instances — still only enough to say something coarse — a uniform draw needs about 1,700 conversations. That figure is a division rather than a simulation: the expected number of instances in a draw of some size is that size multiplied by the rate, because each conversation contributes its own probability to the total and expectations add whether or not the draws are independent. Setting the product to five and solving for the draw size divides five by three-in-a-thousand, which is the 1667 the code prints. Seventeen hundred conversations at six minutes of labelling each is 170 hours of engineer time spent almost entirely on order-status questions you already know the answer to. The cost of learning about the 0.3% by uniform sampling is paid overwhelmingly in labelling the 99.7%.

p_incident = 0.003
n = 200
print(round((1 - p_incident) ** n, 2))       # 0.55  chance of zero instances
print(round(5 / p_incident))                  # 1667  draws for ~5 expected

This is not a new problem and it was solved outside machine learning entirely. Jerzy Neyman's 1934 paper on the representative method set out the case that sampling each stratum separately beats sampling the whole, and that the optimal number of units per stratum is proportional to the stratum's size multiplied by its internal variability and divided by the square root of what it costs to sample there. Survey statisticians have allocated samples that way for ninety years, and the reason a national poll of 1,200 people can report on a demographic that is 2% of the country is that it does not draw those 1,200 uniformly. An eval set is a survey with a labelling budget instead of a phone bank, and the same allocation logic applies with one amendment: severity belongs in the objective too, because you care about a data-exposure slice out of proportion to both its frequency and its variance.

Defining the slices before drawing anything#

A slice is a subpopulation you want to be able to make a statement about, and the definitions come from four places. Intent is the obvious one and the one teams usually stop at. Customer or account segment matters because behaviour differs by context — a business account with forty open orders exercises different retrieval than a consumer with one. Input shape is its own axis: conversation length, message length, language, number of intents in a message, whether an identifier was supplied. And known incident patterns are the fourth, drawn straight from the postmortem file.

Neyman's rule adapts cleanly to this with one addition. His formula gives each stratum a share of the budget proportional to its population size times its internal standard deviation, divided by the square root of the cost of sampling there — so large, noisy, cheap strata get more cases and small, uniform, expensive ones get fewer.

Where that expression comes from is worth a paragraph, because the shape is what you will reuse and the shape is not obvious from the words. Write W for a stratum's share of the population, sigma for how much the outcome varies between conversations inside that stratum, c for what one case there costs to label, and n for the number of cases the plan gives it. The population figure is the stratum figures recombined under the W's, and each stratum's contribution to how uncertain that total is comes to W squared times sigma squared, divided by n. Buying one more case in a stratum shrinks that stratum's term, and it shrinks it by more where W and sigma are large and where n is still small. A budget is being spent well when the last case bought in every stratum reduces the total uncertainty by the same amount per pound spent — if one stratum were returning more than another, you would move a case across and be better off. Setting those marginal returns equal across all the strata is what produces the rule: n proportional to W times sigma, divided by the square root of c.

Said back in plain terms, each factor is doing one job. A stratum where every conversation goes the same way needs almost no cases, because the first case tells you the answer and the second tells you nothing new — that is sigma. A stratum that is a large share of traffic needs more, because being wrong about it is being wrong about more of the total — that is W. And cost sits under a square root rather than beside the others because doubling the price of a case does not halve its worth; it makes cases in that stratum worse value by the square root of two, which is a much gentler penalty than the phrase "expensive to sample" suggests.

For an eval set the objective is not estimating a population mean with minimum variance; it is detecting changes in behaviours whose consequences differ by orders of magnitude. Multiplying each stratum's allocation by a severity factor, and then imposing a floor of six to eight cases on any stratum you want to make a statement about at all, produces the allocation below. The floor usually binds before the formula does, which is why the plan looks hand-made rather than computed.

Multiplying by severity rather than adding it is not a free choice of operator. Neyman is minimising the uncertainty of an estimate, and every stratum's contribution to that quantity is already a product of terms. The quantity you are minimising is different: it is the expected cost of a regression you failed to notice, and a stratum's contribution to that is its chance of hiding a regression multiplied by what a regression there would cost. Severity is that second multiplicand entering the expression where it belongs. It is also the point where the allocation stops being a calculation and becomes a statement about what the organisation cares about, which is why the plan is agreed rather than computed and filed.

The floor is a third kind of constraint again, and confusing it with the formula is common. The formula answers how to spend a budget so that one aggregate number comes out as precise as possible. The floor answers whether a slice can be spoken about at all. A slice with two cases has a rate that can take three values, every one of which is consistent with almost any underlying behaviour, so the slice reports nothing — not badly, but nothing. Six to eight cases is roughly where a slice starts being able to move visibly between releases without the movement being the sort of thing that happens anyway.

Written out for 400,000 conversations of retail support traffic, with a labelling budget of two engineer-days — about 950 minutes of focused work, which at five to eight minutes per case for reading the trace and deciding a verdict comes to roughly 150 cases:

Two things in that table are deliberate and both get argued about. The multi-account slice is sampled at 1 in 80 while the majority intent is sampled at 1 in 10,300, an oversampling factor of about 130 — that is the whole point, and it is what converts an unmeasurable pattern into a slice with 15 cases where a drop from 14/15 to 9/15 is visible. And the largest slice by traffic gets the fewest cases of any intent slice, because twelve cases are enough to catch catastrophic breakage of a path that a thousand other signals also cover, and the marginal thirteenth order-status case tells you nothing you did not know.

Both of those rates are worth reconstructing once, because the table gives the answers and not the working. Three in a thousand of four hundred thousand conversations is about twelve hundred conversations carrying the pattern, and drawing fifteen cases out of twelve hundred is one case in every eighty. The majority intent is 31% of the same four hundred thousand, which is a little over a hundred and twenty thousand conversations, and twelve cases drawn from that is the 1 in 10,300. Dividing the second rate by the first is where the factor of about 130 comes from, and it is the number to quote when somebody calls the plan biased — because biased is exactly what it is, deliberately, and the size of the bias is recorded rather than hidden.

Within a slice, which conversations you keep matters nearly as much as how many. Drawing forty order-status conversations from a single Tuesday morning gives you forty conversations that share a promotion, a carrier outage and a shift of support agents, so they behave more like four conversations than forty. The draw should spread across the whole window, across hours of the day, and across customer segments, and it should reject a second conversation from the same customer, because one customer's phrasing habits repeat and their account state is identical. A cheap version of this is to draw three times the target within a slice, embed them, and keep the most mutually distant subset, which pushes the sample toward the edges of the slice rather than its centre — and the edges are where behaviour flips.

The whole plan belongs in a file, not in a notebook cell. Slice definitions, the filter query for each, the target count, the discard rule, the traffic share measured and the date it was measured on: all of it is metadata the set carries forward, because six months from now somebody will need to draw the same slices again and reproduce the same shares.

Drawing the rare slices is the part that takes engineering rather than statistics, because you need a filter that finds them. A multi-account stratum comes from a query over the account table joined to conversation resolution logs:

-- Candidate multi-account collisions: two accounts, similar names, same postcode,
-- and a conversation where the assistant resolved one of them.
WITH collisions AS (
  SELECT a.id AS account_a, b.id AS account_b, a.postcode
  FROM accounts a
  JOIN accounts b
    ON a.postcode = b.postcode
   AND a.id < b.id
   AND similarity(a.full_name, b.full_name) > 0.6   -- pg_trgm
)
SELECT c.conversation_id, c.resolved_account_id, k.account_a, k.account_b
FROM conversation_resolution c
JOIN collisions k
  ON c.resolved_account_id IN (k.account_a, k.account_b)
WHERE c.started_at >= now() - interval '3 weeks'
ORDER BY random()
LIMIT 40;                                            -- draw 40, label the 15 best

Drawing forty and keeping fifteen is not cheating as long as the discard rule is written down and mechanical — here it was "discard conversations where the customer never asked anything order-specific, because the collision cannot manifest" — and as long as the discard rate is recorded, because the discard rate is what tells you the true prevalence of the pattern if anyone asks later.

What would turn that into cheating is a discard rule that reads the wrong column. The rule used here looks only at the customer's side of the conversation — did they ask anything order-specific — which is a property of the input and was fixed before the assistant did anything at all. A rule that looked at the assistant's answer would be different in kind, even in the mild form of dropping conversations that seem uninteresting, because it selects cases using the outcome the set exists to measure, and a slice assembled that way reports back whatever the person doing the discarding expected to find. The test to apply to any filter in a sampling plan is whether it could have been run before the system under test existed. If it could, it is a sampling decision. If it could not, it is a result.

The one number, and what to refuse#

An executive will ask for one quality percentage, and the set can produce one honestly, as long as it is produced by reweighting rather than by averaging. The raw pass rate over a stratified sample is meaningless as a population figure, because the multi-account slice is 10% of the set and 0.3% of the world. Weighting each slice by its traffic share recovers an estimate of the population rate:

slices = {                       # name: (traffic_share, passes, cases)
    "order_status_id":     (0.31, 12, 12),
    "order_status_no_id":  (0.12,  9, 12),
    "returns_in_window":   (0.14, 10, 10),
    "returns_exception":   (0.04,  7, 12),
    "shipping_exception":  (0.09,  8, 10),
    "account_access":      (0.07,  8,  8),
    "address_change":      (0.03,  6, 10),
    "subscription":        (0.06,  7,  8),
    "multi_intent":        (0.05,  6, 12),
    "mixed_language":      (0.04,  7, 10),
    "long_context":        (0.03,  8, 10),
    "retrieval_empty":     (0.02,  5, 10),
    "multi_account":       (0.003, 4, 15),
}
unweighted = sum(p for _, p, _ in slices.values()) / sum(n for _, _, n in slices.values())
weighted   = sum(w * p / n for w, p, n in slices.values()) / sum(w for w, _, _ in slices.values())
print(round(unweighted, 3), round(weighted, 3))   # 0.698  0.861

Two details of that calculation repay being slow about. The weighted line multiplies each slice's pass rate by that slice's share of traffic and then divides by the total of the shares. The division is there because the shares do not quite come to one — the injection slice is authored rather than sampled and carries no traffic share at all, and rounding accounts for the remainder. Dividing by the actual total is what keeps the result a weighted average of the slice rates rather than an average that has quietly been scaled down by the missing share.

The unweighted number is the more instructive of the two, once you ask what it is a pass rate of. It is the pass rate of the sample, and the sample was constructed to over-represent everything difficult: the multi-account slice is about a tenth of the cases and three thousandths of the world, the returns exceptions about a twelfth of the cases and a twenty-fifth of the world. So the unweighted figure answers a question nobody asked — how the assistant does on a population deliberately designed to be hard — and it sits below the weighted one for that reason alone. The distance between the two numbers is a fact about the sampling plan and carries no information about the assistant.

The weighted figure is the one to hand over, with the sample sizes attached and with the statement that it estimates the population pass rate to within roughly ±0.04. What to refuse is the use of that single number as the release gate on its own, because the multi-account slice moving from 14/15 to 4/15 shifts the weighted number by 0.002 and would not trip any threshold anybody would set.

That last figure is one multiplication and it is worth doing by hand, because it is the entire case for slice-level gates. The slice's rate falls from fourteen of fifteen to four of fifteen, which is ten cases in fifteen, or about two thirds. In the weighted sum, that slice enters multiplied by its traffic share of 0.003. Two thirds of three thousandths is two thousandths, and that is how far the headline moves. Nothing else in the sum changed, so nothing can amplify it and nothing needs to cancel it: the aggregate is behaving exactly as designed and is reporting that a data-exposure bug went from almost never firing to almost always firing as a movement in the third decimal place.

Severe slices need their own gates, with a hard floor a release cannot cross regardless of the aggregate. Reporting per-slice rates as the primary artefact and the weighted aggregate as a footnote keeps that structure visible; reporting the aggregate first invites everyone to optimise it, and the cheapest way to raise a traffic-weighted average is to get better at order-status questions.

Discovery, and the bookkeeping the weights create#

Stratification does not discover failure modes. Every slice in that table came from someone knowing to look — from an incident, from a support lead's complaint, from reading conversations on a Thursday afternoon. A pattern nobody has noticed gets no slice, gets no cases, and stays invisible exactly as it was under a uniform draw. Stratification is a way of measuring known problems reliably, and the discovery work is separate: clustering low-rated conversations, reading escalations, watching new intents appear. A quarterly hour spent reading fifty random conversations with no hypothesis is the cheapest source of new slices there is, and it is the one thing uniform sampling is still good for.

It also introduces a bookkeeping obligation that outlives the people who set it up. The weights are only correct for the traffic mix they were measured on, so a shift in the mix silently biases every weighted number reported afterwards, and slice definitions have to be stored with the set rather than living in the head of whoever drew the sample. That obligation is manageable while the sampling plan is fresh and becomes a serious problem several months later, which is a thread the last chapter of this topic picks up.

What stratification buys is that each thing you care about has enough cases to speak for itself, and that the rate at which you sampled it is recorded rather than implied. The aggregate is then a derived quantity, reconstructed by weighting, and it is the least interesting artefact the set produces: it moves when the majority intent moves and is nearly blind to everything else. The per-slice rates are the instrument, and they exist only because somebody decided in advance which subpopulations had to be measurable and paid for the cases to make them so.

The immediate problem is smaller and more concrete. Having chosen 147 conversations, you have to decide what a row of this set actually contains — because a multi-account case only fails when the retrieved account documents are the ones that were retrieved at the time, and if a row stores nothing but the customer's question, re-running it next month against a rebuilt index will quietly evaluate a different case than the one you labelled.