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 Open ML, 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.

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: Use integer programming to solve the combinatorial optimization problem exactly, ensuring balanced representation across all attributes simultaneously.