Balance Only What Survives the Search: Statistically Certified Group Discovery for Annotation-Free Robust Training

Image and text classifiers often learn shortcuts. A bird classifier may decide "water bird" from the water in the background. The standard fix is to rebalance training data so that rare combinations, such as a water bird on land, count as much as common ones. Rebalancing needs to know which examples belong to those rare groups, and real datasets almost never come with that information. Recent methods therefore infer the groups automatically. Typically they train a deliberately shortcut-prone model and treat the examples it gets wrong as the rare group. This inference step is a search over many possible groups, and the exploratory data analysis literature has shown that unpenalized searches of this kind mostly find coincidences. One synthesis reports that over 60% of conclusions from unconstrained exploration can be false positives (Designing for Interactive Exploratory Data Analysis Requires Theories of Graphical Inference). A balancing pipeline that upweights coincidental groups adds distortion to the data instead of removing it.

We propose to put a statistical gate between "find candidate groups" and "rebalance on them." Each example gets a shortcut-failure signal from a biased model. We then describe where that failure concentrates using a subgroup list: a short, ordered set of human-readable rules, such as "class = corgi AND background = snow," selected by a compression criterion that automatically charges for the size of the search. Only groups that survive this penalty are used, both for rebalancing and for choosing the final model checkpoint without human group labels. The bet is that certification matters most where current methods break: noisy labels, where misclassified points are partly just noise, and many-to-many shortcuts, where the spurious structure is a combination of attributes and not a single one.

Core Claim

Group-inference methods for robust training fail in a predictable way. They treat every high-loss example, or every discovered cluster, as a real subpopulation. A global, search-penalized subgroup description of shortcut failures corrects this, and it does so in three respects. It rejects isolated noisy examples, because they do not compress into a coherent rule. It finds the higher-order attribute combinations that define many-to-many shortcuts, without balancing over every possible combination. And it supplies validation groups for checkpoint selection that were fixed before the validation data was examined, so selection incurs no multiplicity cost.

The specific prediction follows from that. Under clean labels and simple one-attribute shortcuts, certified groups should roughly match simple upweighting of errors. Under 20–40% label noise, and on the many-to-many splits of Spawrious, they should beat it by a clear margin.

Where This Sits

The method comes from the subgroup-discovery side of the file. Robust subgroup discovery introduces SSD++. It selects a non-redundant, ordered list of rules under the minimum description length (MDL) principle, which prefers whichever description lets you encode the data in the fewest bits. It also shows that each greedy step's compression gain is equivalent to a Bayesian test with an implicit penalty for search-space size. That equivalence gives a stopping rule without user-set thresholds, which is why we reuse it.

Oversearching constrains the design. It shows that widening a rule search can raise out-of-sample error, so the search depth for conjunctions cannot be left unbounded. Online error-control systems motivate the framing but are not reused directly. Controlling False Discoveries During Interactive Data Exploration and the α-investing approach of Servan-Schreiber et al. treat every exploratory query as a hypothesis test. Our searches are batch, not interactive, so MDL fits better than an online budget.

Context-Aware Testing (SMART) shows that semantic priors on feature names cut false slices to near zero. It is restricted to tabular data with meaningful column names. We address that restriction by testing the same pipeline with named attributes and with anonymous embedding clusters.

On the robust-training side, the closest existing systems all infer groups without certifying them. For Robust Worst-Group Accuracy, Ignore Group Annotations (RAD-UW) upweights every example misclassified by a sparse, shortcut-prone linear probe. It is robust to noise in human group labels, but its pseudo-groups absorb label noise and outliers. Unsupervised Concept Discovery Mitigates Spurious Correlations (CoBalT) balances over vector-quantized slot-attention concepts and uses them to escape the dependence on validation group labels. It does not penalize the large concept space, and it needs spatially separable concepts. Diversity-Driven Learning (FedDiverse) picks federated clients whose estimated biases cancel. Its bias estimates are untested for small-sample flukes. Elastic Representation (ElRep) regularizes representation rank and never names what it suppresses. We differ from all four in the same way: no group influences training or model selection until it has passed a search-size-aware test.

Two papers set the stakes. Simple data balancing achieves competitive worst-group-accuracy shows that plain subsampling or reweighting of known groups matches complex methods. It also shows that much of what looks like algorithmic gain is really access to clean validation group labels for checkpoint selection. Good inferred groups are therefore the main bottleneck, not the loss function.

On the Limitations of Dataset Balancing appears to contradict us. Its XOR argument says that balancing single features leaves combinations imbalanced, and balancing all combinations erases the signal. We accept the argument and take a narrower aim. We balance only on the few combinations that a shortcut-prone model demonstrably exploits and that survive the penalty, and we leave the remaining correlations untouched. This includes the benign regularities that paper warns against erasing. Whether this narrower aim is enough is an empirical question, and the Spawrious many-to-many experiments test it.

Research Program

The pipeline has four stages.

The first stage builds a biased model. Following RAD, it is an ℓ1-regularized linear probe on frozen last-layer features. Each training example gets a failure signal $y_i$: the probe's loss on example $i$, or a binary misclassification indicator.

The second stage gives each example a discrete description. We test two description languages. The named language assigns tags from a vision-language model's zero-shot scores over a fixed vocabulary of background, object, color and texture words, plus the class label; the RaVL codebase (Stanford-AIMI/RaVL) is a starting point. The anonymous language uses k-means cluster ids of the embeddings, plus the class label. It deliberately removes semantics, to see whether certification works where SMART-style priors cannot.

The third stage runs SSD++ with $y_i$ as the target and a conjunction depth of at most three. For a numeric target we use its dispersion-aware Gaussian model. A rule $s$ is appended to the list only if it shortens the total encoding:

$$\Delta L(s) = L(\text{data} \mid \text{list}) - L(\text{data} \mid \text{list} + s) - L(s) > 0,$$

where $L(\cdot)$ is a code length in bits. $L(s)$ grows with the number of candidate rules of that size, and this term is the search penalty. Isolated noisy examples cannot pay for their own rule, so they stay in the default rule.

The fourth stage uses the list twice. For training, each example falls into the first rule covering it, and these cells, crossed with class, are reweighted or subsampled to equal mass. For checkpoint selection, the same frozen rules are applied to the validation set, and we choose the checkpoint with the best worst-cell accuracy.

The rules are found on training data only and applied to validation data without any further search. The validation selection is therefore a single pre-registered comparison, not a scan. This is the statistical answer to the validation trap identified by Idrissi et al..

Following Position: Measure Dataset Diversity, Don't Just Claim It, we do not use downstream accuracy as evidence that groups are correct. On benchmarks with ground-truth attributes we report group-discovery precision and recall directly. A discovered group counts as true if it has at least 80% overlap with a real class × spurious-attribute cell.

Baselines

The naive reference points are ERM and class-balanced ERM on the same backbone. Elastic Representation reports ERM worst-group accuracy (WGA) of 70.0% on Waterbirds and 45.0% on CelebA. Spawrious reports 47.02% for ResNet18 ERM on M2M-Hard, despite exact class balance. Beating these is necessary but uninformative.

The strongest annotation-free competitor on our specific question is RAD-UW (For Robust Worst-Group Accuracy, Ignore Group Annotations). It uses the same biased probe as our first stage and simply upweights all of its errors during last-layer retraining. That makes it the cleanest test of whether certification adds anything. It reports about 83.5% WGA on CelebA that stays flat as group-label noise increases, while annotation-reliant methods fall from 86% to below 79% at 20% noise.

The strongest group-inference method on images is CoBalT (Unsupervised Concept Discovery Mitigates Spurious Correlations). It reports about 89–90.6% WGA on Waterbirds, 89.2% on CelebA with fully unsupervised validation, and 80.0% on UrbanCars. ElRep added to GroupDRO reaches 91.4% on CelebA, but it uses group labels, so we report it only as a reference above the annotation-free regime. On Spawrious M2M-Hard the reported ceiling is that no ResNet50 method exceeds 70%, with CORAL and CausIRL at about 67–68%. For MultiNLI and CivilComments-WILDS, no reported result was found on Lacuna for these methods, so we will run all baselines ourselves.

The upper reference is group subsampling with oracle group labels on both training and validation data (Idrissi et al.).

Every method uses the same frozen backbone and the same biased-probe features where one is needed, and gets the same tuning budget of 20 configurations. In the headline comparison, each method selects checkpoints only by its own label-free criterion. Oracle-selected numbers are reported separately.

Two ablations isolate the key ingredient, and both use our exact pipeline. The first removes the penalty by taking the top-k highest-error conjunctions, with k matched to our list length. The second replaces MDL with sample splitting: top-k candidates are found on half the training data and confirmed on the other half with a Bonferroni-corrected test.

Beating RAD-UW means a WGA gain larger than three seeds' standard deviation at 20% and 40% injected class-label noise and on M2M-Hard, with no loss on clean Waterbirds.

Why not just…?

Why not just upweight everything the biased model gets wrong, as RAD-UW does? Under clean labels this may be as good as our method, and we expect roughly equal results on clean Waterbirds. Under class-label noise, mislabeled points are exactly the ones a biased probe misclassifies. Upweighting them amplifies noise, and RAD's own design has no step that separates noise from a coherent minority. The noise sweep settles this. If RAD-UW's WGA does not degrade relative to ours at 40% noise, our central claim is wrong.

Why not just confirm top-k slices on a held-out split with a Bonferroni correction? This is the real threat. It provides much of the same protection against flukes with textbook tools. We include it as an ablation, not as a strawman. MDL's claimed extra benefit is that its list is non-redundant: overlapping top-k slices would double-count weight on the same examples. Splitting also halves the data available for discovery, which hurts small minority cells, a power problem that SMART's authors also flag. If the split-and-confirm variant matches ours, we will report that certification is the ingredient and the MDL list is a convenience.

Why not just balance every attribute pair, or train a bigger model? Exhaustive pairwise balancing is exactly the regime where the XOR argument predicts signal loss (On the Limitations of Dataset Balancing). We run it on Spawrious, where the attribute set is small enough to enumerate, and expect higher variance and lower average accuracy. Scale does not appear to be the remedy. The Effect of Model Size on Worst-Group Generalization finds that worst-group gains from model size plateau on CelebA, and Spawrious reports that larger backbones do not solve many-to-many splits.

Why not just use CoBalT's learned concepts? CoBalT's concepts can be fed into our gate as a third description language. If certifying CoBalT's concept groups improves CoBalT itself on CelebA, where spatially entangled attributes create many spurious concepts, that is a positive result for our thesis.

Proposed Experiments

The datasets are Waterbirds, CelebA, UrbanCars, MultiNLI and CivilComments-WILDS, plus all Spawrious O2O and M2M splits. On the image sets we inject class-label noise at 0%, 20% and 40%. Following SMART, we also add random junk attributes to the description language, so that we can count fluke groups directly. The metrics are WGA, average accuracy, group-discovery precision and recall against ground-truth attributes, and the rank correlation between the label-free validation criterion and true validation WGA across checkpoints.

Three results would be decisive.

First, on junk-augmented descriptions, the unpenalized top-k ablation should select junk attributes at a substantial rate while ours selects almost none. If both select junk at similar rates, the gate is doing nothing.

Second, on Spawrious M2M-Hard, certified conjunction groups should push WGA above the reported 70% ceiling without oracle labels. They should also recover the true class × background combinations at depth two, which single-attribute methods cannot represent.

Third, worst-cell validation accuracy on frozen rules should track true WGA more closely than CoBalT's inferred validation groups and the biased-probe error rate. If it does, it would show that the validation trap can be escaped by a criterion fixed in advance, without spatial concept segmentation.

The anonymous-cluster description tests whether the gate keeps its benefit without semantic names. If it does not, the result marks the limit of the method: certification needs a meaningful description language, which is the same restriction SMART faces.