Building Fair Evaluation Sets Is a Combinatorial Problem

Overall accuracy is a weighted average — and the weights are whatever your evaluation set happens to contain. If your eval set is 90% group A and 10% group B, a model scoring 95% on A but only 60% on B still reports a comfortable 91.5% overall:

The failure is sitting in plain sight, absorbed into a healthy-looking headline number. And checking group B’s number on the same skewed set doesn’t rescue you: it rests on a handful of rows, so its estimate is far noisier than group A’s. This is not hypothetical — commercial face-analysis systems shipped with error rates roughly 10× higher for dark-skinned women than for light-skinned men, and the gap went unnoticed for years because the benchmarks were overwhelmingly light-skinned and male. The model and the measuring instrument shared the same blind spot.

The fix is an evaluation set where every group has equal statistical footing. Now, one precondition before anything else — because it decides whether you need this post at all. If your entire pool is already labeled and evaluation is free, you don’t need a subset: evaluate on everything and report per-group numbers. But real evaluation is rarely free. Human review, expert annotation, judge-model API calls, latency budgets, suites that must re-run on every checkpoint — in most modern pipelines, especially LLM ones, evaluation capacity is the binding constraint. The operating assumption of this post is exactly that: you can afford K evaluations, and the question is which K rows to spend them on. Choose them randomly and the skew above is what you get; no weighting scheme applied afterwards can create evidence you never collected.

Building a subset that is balanced across several attributes at the same time turns out to be a genuinely hard combinatorial problem that most teams solve with duct tape. Let me show you the problem, what the honest alternatives are, and a small open-source package that solves it exactly.

The problem: your dataset is imbalanced in several ways at once

Take the classic Adult census dataset (also on OpenML, which is what the code below loads. CC BY 4.0 license): 48,842 rows. Two-thirds male. 85% White. 76% low-income. Age bunched between 25 and 45.

One honest framing note: Adult ships fully labeled, so treat it here as a stand-in for a budget-constrained pool — pretend each row you evaluate still costs you something, as it would in a human-eval or judge-based pipeline. (For a case where the budget constraint is real rather than simulated, see the LLM eval-suite notebook: 15K instruction prompts, of which you can afford to run 500 through evaluation.)

Suppose your budget is 1,000 evaluations, and you want that eval set to be simultaneously:

• 50/50 on sex,

• equal across all five race categories,

• 50/50 on income class,

• flat across the age range.

Balancing any one of these is trivial — group by the attribute, sample equally per group. But every row you pick counts toward four histograms at once. A row that helps your sex balance might wreck your age balance. Stratifying on the cross-product of all four attributes doesn’t work either: 2 sexes × 5 races × 2 incomes × 10 age bins = 200 strata, most of which are nearly empty in the original data (how many rows do you think there are of high-income Amer-Indian-Eskimo women over 70?).

Greedy selection — iteratively picking whichever row locally improves balance — has no guarantee at all. It routinely paints itself into corners where every remaining candidate makes some marginal worse.

This is a combinatorial optimization problem. So let’s treat it like one.

Selection as integer programming

The whole pipeline fits in one picture:

The formulation is almost embarrassingly clean. For each row k, introduce a binary variable x_k ∈ {0, 1}: keep it or not. Then:

• one constraint fixes the subset size: Σ x_k = 1000;

• for every (attribute, bin) cell, a slack variable measures how far the selected count in that cell deviates from its target count;

• the objective minimizes the total slack (plus, optionally, a term that suppresses cross-attribute correlations in the selected subset).

Minimize deviation from all target histograms jointly, over all possible 1,000-row subsets. A mixed integer linear programming (MILP) solver either proves it found the optimal subset or, given a time budget, returns the best one found with a quality bound. One precision on the word “exactly”: the optimization is exact with respect to this objective — total L1 deviation on the marginals. That objective is a modeling choice (a different deviation measure would prefer different subsets), and I’ll come back to what that does and doesn’t buy you.

I published this formulation back in 2016 (ICIP paper); we used it to curate balanced face datasets. The fairness conversation has since made the problem mainstream, so I’ve modernized the implementation and packaged it in an open source Python library: datacarve. The name means what it does: to carve is to undersample — select a subset of your real rows and drop the rest, so that what remains has exactly the shape you asked for.

Three seconds later

Here’s the entire Adult example. Categorical columns are label-encoded and flagged; 'uniform' means “equal counts per category” for categorical attributes and “flat histogram” for numeric ones:

import numpy as npfrom datacarve import undersample_dataset# age, sex_codes, race_codes, income_codes: label-encoded columns of your DataFrame dfdata = np.column_stack([age, sex_codes, race_codes, income_codes])mask = undersample_dataset(    data=data,    data_to_keep=1000,    target_distribution="uniform",    categorical_dims=[1, 2, 3], # sex, race, income)balanced = df[mask] # the mask indexes the original rows

On my laptop this solves in under three seconds, over 48,842 binary decisions. The result:

Carving is pure undersampling: every row in the subset is a real census record — nothing synthesized, duplicated, or reweighted. And the payoff under our budget assumption is immediate: a random 1,000-row eval set gives the smallest racial groups about 8 rows each, so their accuracy estimates swing by whole percentage points on a couple of lucky predictions. The carved set gives every group the same 200-row evidence base.

Why evaluation specifically, and not just training on a balanced subset?Because training and evaluation have opposite economics. In training, more data generally helps — models tolerate imbalance, loss weighting exists, and throwing rows away usually costs accuracy. Evaluation is a measurement instrument: it’s small by necessity, which means per-group sample sizes collapse fast, and a skewed instrument gives readings dominated by the majority no matter how good the model is. You can compare groups with unequal n — standard two-proportion tests handle it — but the comparison inherits the precision of the worst-measured group; equalizing the evidence makes per-group estimates comparably precise, which is the property you actually want from an instrument. And under a fixed evaluation budget, carving costs you nothing you could have afforded to keep anyway.

How large should each group’s count be? Balance alone won’t save you here: 200 rows per group still carries binomial noise. A quick rule of thumb at accuracies around 90%: with n rows per group, gaps smaller than roughly 6 / sqrt(n/200) percentage points won’t reliably clear a two-group significance test (at n=200 that’s gaps below ~6 points; quadruple the group size to halve it, and add margin if you’ll compare many groups at once). Decide the smallest gap you care about first, then size K — datacarve controls the composition; the power arithmetic is still yours to do.

Targets don’t have to be uniform, and each attribute can get its own. Want to keep a realistic 3:1 income ratio while balancing everything else, and shape age like a gaussian? One list:

target_distribution=["gaussian", "uniform", "uniform", [3, 1]]

The solver hit that 3:1 ratio at exactly 750/250.

“Why not just…?”

The alternatives all solve a neighboring problem — and two of them deserve more credit than a dismissal:

• Macro-averaging (equal weight per group, computed on the skewed set) is the most tempting shortcut, and for a single categorical attribute on a fully labeled pool it’s legitimately fine. But the weighting was never the hard part. Under an evaluation budget of K rows, your smallest groups still contribute a handful of noisy rows — and equal weighting amplifiesthat noise rather than hiding it. It also composes poorly across several attributes (per-attribute averages confound each other), and at the end you still have nothing to hand over: a benchmark release or a human-eval panel needs actual rows, and macro-averaging is a reporting convention. In one line: reweighting changes how you average the evidence; carving changes which evidence you collect.

• Balanced sampling — the cube method (Deville & Tillé 2004) — is the strongest alternative and the right tool when statistical inference is your priority. It draws probability samples that satisfy balance constraints, with known inclusion probabilities, so classical survey estimators and confidence intervals remain valid — something carving cannot offer (see the limitations below). The trade: it balances totals of auxiliary variables approximately (its “landing phase” relaxes constraints that can’t be met exactly) rather than shaping full per-attribute histograms to arbitrary targets, and it has no notion of suppressing cross-attribute correlation. If you need design-based inference more than exact composition, use the cube method; if you need a fixed-size set with a guaranteed, documented shape, carve.

• Matching methods from causal inference are closer relatives than they first appear: cardinality matching with fine balance (Zubizarreta and colleagues) is also an integer program constraining marginal distributions, and template matching can even target an external template rather than another sample. datacarve differs in being target-first and general-purpose: any parametric or custom target shape per attribute, mixed numeric/categorical dimensions, an explicit correlation-minimization objective, and a pip-installable API rather than a study design.

• Stratified sampling balances one attribute; the multi-attribute cross-product explodes into empty strata.

• Class balancing tools (undersampling/SMOTE in imbalanced-learn) handle a single label, and SMOTE fabricates synthetic points — fine for training, unacceptable for evaluation data.

• Coreset selection optimizes a model’s training loss, with no interpretable guarantees on per-attribute histograms.

The niche datacarve fills: jointly multi-attribute, distribution-targeted selection of real datapoints, optimal with respect to an explicit and auditable objective.

What carving does not give you

Four limitations, in plain language, each with what to do about it.

1. The rows picked from each group aren’t “typical” of that group — unless you randomize. The solver doesn’t choose 200 typical White rows; it chooses 200 White rows that also help flatten the age, sex and income histograms. Concretely: if elderly diabetic men are scarce in a hospital pool, the solver fills its age and diabetes quotas with elderly diabetic women — so “the women in your subset” end up older and sicker than women in your pool. Every row is real, but the mix within each group is tilted by the balancing itself. There’s a second, sneakier effect: many different subsets satisfy the constraints equally well, and by default the solver picks one essentially by accident of your file’s row order.

What to do: use the randomize parameter (any seed). The solver still decides how many rows come from each group-combination; a coin flip decides which rows — so you get balance on the dimensions you chose, randomness on everything else you left alone. The balance is unchanged, and when we measured it, the accident-of-row-order wander collapsed to a tight spread centered on the pool’s true values. Two things it can’t do: undo the tilt that the balancing itself requires (report per-group numbers as “on our balanced set” rather than “for women in general”), and replace proper survey sampling when a statistician needs textbook confidence intervals — for that, see the cube method above, which is the mirror image: random first, balanced only approximately.

2. Balancing each column doesn’t balance the combinations. You can have exactly 500 men / 500 women and exactly 500 high-income / 500 low-income — and still have most of the high-income rows be men. Each column’s histogram is perfect; the pairing is lopsided. If your model then struggles with low-income people, it will look like it struggles with women.

What to do: after carving, print the cross-table for the attribute pairs you care about — one line of pandas. If a combination matters, balance it directly: make it its own column (e.g. gender_x_income with 4 values) and mark it categorical. That works whenever your pool actually has enough rows in every combination — and if it doesn’t, no selection method can fix that (see point 4).

3. The knobs you set shape the answer more than it appears. “Uniform over age in 10 bins” and “uniform over age in 20 bins” are different requests with different optimal subsets. And a uniform target over a long-tailed attribute quietly over-weights the rare extremes: ask for a flat histogram over incomes up to $10M and the handful of millionaires in your pool all get drafted. “Provably optimal” always means “optimal for the question exactly as you posed it.”

What to do: transform long-tailed columns before carving (log income, log text length); pick bin edges that mean something in your domain rather than defaults; and remember uniform isn’t sacred — if you want your eval set to mirror production, set the target to the production mix instead.

4. Carving can’t create data you never collected. If your pool contains 35 recordings of women over 65, no selection method on earth turns them into 200. The face-analysis failures mentioned at the top were ultimately fixed by collecting a new dataset — no amount of clever selection could have produced rows that were never there.

What to do: let carving be your early-warning system. When the pool can’t support your target, the result says so explicitly — an infeasible run or a visibly missed quota is a quantified statement of exactly which groups are short and by how much. That’s the difference between discovering a coverage hole while curating the eval set and discovering it in an incident report.

How far does it scale — and how exactly does it break?

“One binary variable per row” sounds like it should die at modest sizes. I assumed so too, so I measured it. On a laptop (CBC backend, 4–6 attributes, uniform targets, keeping ~10% of rows):

A million rows, solved to proven optimality, in half a minute. There’s a principled reason this isn’t as surprising as it looks: each attribute’s bin-count constraints have a simple, nearly network-like structure, and LP relaxations of such structures tend to land on solutions that are already close to integral — leaving branch-and-bound very little work. The same lens predicts the pathological case.

The catch is the structure of the data. Look at the red X in the plot: an 11,000-row dataset — 90× smaller than the million-row instance — that still isn’t solved optimally after 60 seconds. What makes it pathological is a dimension that’s a near-linear combination of two others: it couples constraint blocks that were previously independent, the relaxation stops being informative, and the solver has to actually search. Difficulty grows with:

• correlated or duplicated attributes (the killer, as above);

• targets that demand mass where the data barely has any — asking for 100 rows in a bin that contains 103 candidates leaves the solver no slack;

• more attributes and finer bins (more coupled constraints);

• keep-ratios near the feasibility edge.

And here is the important part: “breaking” is graceful. The solver never crashes or returns garbage — it returns the best subset found within the time budget and tells you so via its status: optimal means proven best, feasiblemeans “best found so far, ran out of time”. In practice feasible solutions from a 60-second budget are already excellent; the time limit mostly costs you the proof of optimality, and very little subset quality. The escalation path when you see feasible: raise the time budget, and switch the solver parameter to 'SAT' (on that pathological dataset, at the same 60-second budget, CP-SAT returned a better subset than both CBC and SCIP).

So when should a researcher reach for datacarve? Whenever the deliverable is a subset of hundreds to tens of thousands of rows drawn from a pool of up to about a million — evaluation sets, quota samples, matched cohorts, scenario suites. That covers nearly every curation task I’ve encountered; you rarely want a balanced eval set with ten million rows.

If your pool really is tens of millions of rows, don’t reach for a naive random subsample — random sampling preserves the skew you’re trying to fix and can annihilate rare groups entirely (a 0.1% category has ~100 rows in 100K samples… and 0 slack to spare). datacarve ships the correct pre-reduction built in:

mask = undersample_dataset(huge_data, data_to_keep=1000, prereduce="auto")

It groups rows by their joint bin signature — rows sharing a signature are interchangeable with respect to every histogram constraint — then keeps rare cells in full and randomly downsamples only the overcrowded ones, with the cap chosen adaptively. The pre-reduction does the cheap volume work; the MILP does the precise joint shaping that the pre-reduction can’t.

Measured end-to-end: 10,000,000 rows → a perfectly balanced 1,000-row subset (100 per bin on every attribute, proven optimal) in about 10 secondson a laptop.

This is a Responsible AI tool, not just a sampling trick

One property of the MILP approach deserves emphasis in the current regulatory climate: the result is auditable by construction. Model cards, datasheets, and bias audits expect evidence about how evaluation data was composed. With heuristic sampling, the composition of your eval set is a post-hoc observation (“it happened to come out roughly balanced”). With datacarve, it’s a documented guarantee: the constraints are explicit, the solver reports whether they were met optimally, and you can state “exactly 200 rows per group” in a datasheet and mean it.

One nuance worth being precise about, because there is genuine tension here: regulation such as the EU AI Act (Article 10) asks for datasets that are “relevant” and “sufficiently representative” of the intended deployment context — and a uniformly balanced set is deliberately not representative of a skewed deployment population. These answer different questions: the representative set estimates aggregate performance in production; the balanced set makes per-group comparisons equally precise. A defensible evaluation practice ships both, with disaggregated reporting — and note that carving builds the representative one too: set the target distribution to the deployment distribution instead of uniform. Either way, the underlying principle stays the same: the composition of an evaluation set should be chosen and documented, never inherited by accident.

Where this fits in the LLM era

Modern LLM work is largely data curation under a budget — which is exactly this problem. The key realization: attributes don’t need to be raw columns. Task labels, topic clusters from embeddings, difficulty scores, length buckets, or safety categories all work as dimensions to balance over.

• Balanced benchmark & eval suites. Carve an evaluation set balanced across task type × domain × difficulty × prompt length, so a model’s headline score isn’t dominated by whichever category the benchmark over-collected — and small enough to run on every checkpoint. (Worked notebook: a 500-prompt suite carved from dolly-15k, balanced across task category × derived topic cluster × prompt length.)

• Fine-tuning mixtures (SFT). Instruction datasets skew heavily by source, topic and length. Carve a training subset that hits an exact target mixture (30% coding, 30% reasoning, 20% writing, 20% multilingual, with a target length distribution) instead of eyeballing sampling ratios.

• Safety & red-teaming sets. Balance adversarial prompts across harm categories × attack styles × targeted demographics, so safety metrics cover the space instead of over-testing the most common attack type.

• Human evaluation & preference data. Annotator time is the scarcest resource in RLHF pipelines; carve the candidate pool so every scenario type gets equal annotation coverage.

Beyond machine learning

The same one-call recipe covers any “pick K items matching target distributions” problem:

• Survey quota sampling: carve a respondent sample hitting census age/gender/region quotas exactly (there’s a fully worked notebook — gender 750/750, region shares exact). For probability-sample quotas with valid inference, see the cube method above.

• Cohort matching in observational studies: covariate distributions matched to a treatment group, or to any reference population.

• Compound library selection in cheminformatics: desired property distributions, minimal redundancy between correlated properties.

• Test scenario selection: a representative, affordable subset of simulation conditions (weather × traffic × speed).

Try it

• PyPI: https://pypi.org/project/datacarve/

• Repo: https://github.com/bbonik/datacarve

• Fairness notebook: balanced_evaluation_sets.ipynb

• Solvers: three free, bundled backends (CBC, SCIP, CP-SAT) with guidance on when to use which — no license fees, nothing extra to install.

If you use it in research, the repo has a “Cite this repository” button (papers: IEEE TMM 2017, ICIP 2016).

I’d genuinely like to hear what you point it at — issues and PRs welcome.

If you use datacarve in research, please cite the papers behind it: Shaping Datasets: Optimal Data Selection for Specific Target Distributions (ICIP 2016) and A Probabilistic Approach to People-Centric Photo Selection and Sequencing (IEEE TMM 2017).

All images in this article were generated by the author.