Execute What Teaches: Uncertainty-Split Mutant Selection for Budgeted Mutation Testing

Mutation testing grades a test suite by planting many small artificial bugs ("mutants") in the code and checking how many of them the tests catch ("kill"). The grade is trustworthy, but it is expensive: every mutant means another run of the test suite. Predictive mutation testing replaces those runs with a classifier that guesses each mutant's outcome from static features. Predictors are cheap but make mistakes, and the mistakes grow when the model faces an unfamiliar project. The practical middle ground is to run the tests on a small budget of mutants and predict the rest. The open question is which mutants to spend the budget on. This proposal answers it by splitting the predictor's uncertainty into two parts. Aleatoric uncertainty covers mutants that the features cannot resolve even in principle. Epistemic uncertainty covers mutants the model has simply not seen enough of. We argue that the standard active-learning rule of skipping aleatoric points and chasing epistemic ones is wrong for this problem, and we propose the rule that fits it instead.

The reason is specific to software. Running the tests on a mutant is a perfect oracle for that mutant, because it reveals the true kill outcome however ambiguous the static features were. A run therefore pays off in two ways. It resolves that mutant directly, and this gain is proportional to its total uncertainty, whatever the source. It can also teach the model about similar mutants that remain unexecuted, and this gain comes only from the epistemic part. We propose an acquisition rule that adds these two values together. It runs on the fast tree ensembles already used by lightweight predictors, so it adds almost no cost. It is paired with a weighting correction so that the final mutation score stays unbiased even though the mutants were chosen on purpose rather than at random.

Core Claim

Given an execution budget of $B$ mutants out of $N$, a cheap tree-ensemble predictor can do three things. It chooses mutants by the sum of direct resolution value and epistemic spillover value. It retrains after each batch of test runs. It reports an inverse-probability-weighted mutation score. Together these should give lower mutation-score error and higher recall of surviving mutants than two alternatives: random sampling with the same predictor used as a correction term, and selection by total confidence alone. We expect the gap to be largest in cross-project and new-version settings, where epistemic uncertainty dominates.

Two falsifiable consequences follow. First, pure epistemic acquisition, which is what the BALD approach from active learning prescribes, should lose to our rule, because it wastes the direct-resolution value of ambiguous mutants. Second, total-uncertainty acquisition should close the gap with our rule on same-project data. If neither pattern appears, the decomposition is not earning its place.

Why the Existing Tools Leave This Open

Three lines of work predict mutant outcomes without running tests.

Predictive Mutation Testing trains feature-based classifiers across 163 projects and reports AUC above 0.80 on most of them. Contextual Predictive Mutation Testing (MutationBERT) encodes each code change with CodeBERT, a pretrained model of source code. It calls a mutant detected when any test reaches 25% predicted confidence. WITNESS uses Random Forest and LightGBM on 21 handcrafted features and runs up to 1,722.8x faster than MutationBERT.

All three are one-shot. They either predict every mutant or apply a fixed threshold, and none decides which mutants deserve a real run. Each collapses confidence into a single number, so a mutant that is inherently hard to call looks the same as one from an unfamiliar codebase.

Cerebro selects "subsuming" mutants statically; these are mutants whose kill implies the kill of many others. Its selection is high-precision (0.85), and it notes that its labels are noisy because some mutants labelled "equivalent" (behaviourally identical to the original) may really be "stubborn", meaning killable but missed by the available tests. That observation motivates separating the two uncertainty sources. It also sharpens what "aleatoric" means here.

For the question "does this suite kill this mutant", the label is exact apart from flaky tests. The irreducible part therefore lives in the static features, not in the label. So execution removes it for that one mutant, even though more training data would not.

The method we reuse is the information-theoretic split from BALD, introduced in Cold-start Active Learning with Robust Ordinal Matrix Factorization for recommender systems. BALD queries only epistemic uncertainty, because in its setting a query adds value only by improving the model. We keep the split but change the objective, because in our setting a query also yields a final answer for the queried item.

Three constraints from the uncertainty literature shape the design:

  • Contextual Similarity Distillation documents the inference cost of sampling-based uncertainty.
  • WITNESS shows that deep predictors already cost more than they save in continuous integration (CI) pipelines.
  • CLEAR shows the two uncertainty components need separate calibration when label noise and distribution shift coexist.

For these reasons we decompose uncertainty inside tree ensembles rather than deep ensembles, and we calibrate both components on held-out executed mutants.

Research Program

The predictor is a WITNESS-style random forest over its 21 features. Features that require coverage (knowing which lines each test runs) come from a single coverage run of the original program. That run is needed anyway and is charged to every method equally.

For mutant $m$, let $p_t(m)$ be tree $t$'s leaf estimate of the kill probability and $\bar p(m)$ the average over $T$ trees. Writing $H$ for binary entropy, the split is:

$$ U_{\text{tot}}(m)=H(\bar p(m)),\quad U_{\text{ale}}(m)=\tfrac{1}{T}\textstyle\sum_t H(p_t(m)),\quad U_{\text{epi}}(m)=U_{\text{tot}}(m)-U_{\text{ale}}(m). $$

The epistemic term is the mutual information between the prediction and the choice of tree, which is the tree-ensemble analogue of BALD. The acquisition score of an unexecuted mutant is:

$$ a(m)=U_{\text{tot}}(m)+\lambda\,U_{\text{epi}}(m)\sum_{m'\in\mathcal{U}}s(m,m')\,U_{\text{epi}}(m'). $$

Here $\mathcal{U}$ is the set of unexecuted mutants, and $s(m,m')$ is random-forest proximity, the fraction of trees in which $m$ and $m'$ land in the same leaf. The first term is the direct-resolution value. The second approximates how much epistemic uncertainty among neighbours a run of $m$ would remove. $\lambda$ is tuned once on training projects and then frozen.

Mutants are sampled in batches, with probability $\pi_m$ proportional to $a(m)$ and a floor on $\pi_m$ to keep variance bounded. After each batch the forest is retrained on the newly executed mutants.

The reported mutation score is a difference estimator, with $y_m\in\{0,1\}$ the executed outcome and $\mathcal{S}$ the executed set:

$$ \hat S=\frac{1}{N}\Big[\sum_{m=1}^{N}\bar p(m)+\sum_{m\in\mathcal{S}}\frac{y_m-\bar p(m)}{\pi_m}\Big]. $$

This estimate is unbiased for any predictor, by standard Horvitz–Thompson reasoning: weighting each sampled mutant's correction by $1/\pi_m$ cancels the selection bias. Its variance shrinks as the predictor's errors fall on high-$\pi$ mutants. This gives a confidence interval, which one-shot predictors cannot report.

We will also run a diagnostic study to check that the two components mean what we claim:

  • The aleatoric component should be high on mutants that later prove equivalent or stubborn. We will use Cerebro's Java benchmark, where these labels are available, and on flaky test pairs.
  • The epistemic component should rise across projects and on the roughly 25% of mutants outside method bodies that WITNESS highlights.

Baselines

The naive reference points are full execution, which gives the ground-truth score at full cost, and pure static prediction with WITNESS, which costs no test runs and reports $\frac{1}{N}\sum\bar p(m)$. Every budgeted method must land between these two.

The strongest simple competitor is uniform random sampling of $B$ mutants combined with the same forest in the difference estimator. It is unbiased, has no selection overhead, and already benefits from the predictor. Beating it means lower root-mean-square score error, or narrower intervals at equal coverage, at the same $B$.

The strongest existing predictors are MutationBERT and WITNESS. For MutationBERT we use its 25% threshold as published and give it the same budget, spent on the mutants nearest that threshold. For context, MutationBERT reports test-suite-level F1 of 0.79 same-project and 0.58 cross-project on Defects4J, per Contextual Predictive Mutation Testing.

We found no reported result on Lacuna for budgeted mutation-score estimation error on Defects4J. The error of random sampling on our splits will therefore serve as the reference number.

Two ablations isolate the key ingredient:

  • Total uncertainty only ($\lambda=0$, with retraining), which is the calibrated-confidence strategy a reviewer would suggest.
  • Pure epistemic acquisition, which is BALD.

A third ablation removes retraining, to separate the gain from choosing mutants from the gain from learning.

All methods share the same mutant sets, the same coverage run, the same forest hyperparameters tuned on training projects only, the same budgets, and wall-clock accounting that includes model inference and retraining.

Why not just…?

Why not just threshold a calibrated classifier and run the low-confidence mutants? This is the $\lambda=0$ ablation, and it is a real threat. Our analysis predicts it captures nearly all of the direct-resolution value, so on same-project splits it may match our method. The evidence that it falls short elsewhere is indirect. MutationBERT's thresholded predictor drops from F1 0.79 to 0.58 across projects, which is exactly the regime where spillover should matter. If $\lambda=0$ matches the full method on cross-project splits too, we will conclude the decomposition adds nothing for this task and report that result.

Why not just sample mutants at random? Random sampling with a predictor-based correction is unbiased and hard to beat when predictor errors are spread evenly. Cerebro's comparison against random selection concerns choosing which mutants to write tests against, not estimating a score, so it does not settle this question. Our variance comparison at equal budget settles it directly. If the forest's errors turn out to be uncorrelated with its uncertainty, random sampling wins, and the diagnostic study will show why.

Why not just use BALD, since it is the principled acquisition rule? BALD assumes a query helps only by improving the model. Here a run also answers the question for that mutant. BALD would therefore skip exactly the ambiguous mutants whose runs are most informative for the score. The pure-epistemic ablation tests this claim, and we predict it underperforms the total-uncertainty rule at small budgets.

Why not just skip the uncertainty modelling, since it costs more than it saves? That is true for deep ensembles and for MutationBERT on CPU, which falls to 12 pairs per second. Tree-level decomposition reads values the WITNESS forest already computes, and proximity comes from leaf indices. We will report wall-clock time per 1,000 mutants against the cost of the test runs saved. The method fails the test if its overhead exceeds 5% of the execution time it avoids.

Proposed Experiments

The main benchmark is Defects4J, using the 31 versions across 6 projects on which WITNESS was evaluated. We test three settings:

  • Cross-version: train on earlier versions and test on later ones.
  • Cross-project: leave one project out.
  • Commit-scoped: evaluate only mutants touching each version's changed code, following the commit-relevance framing of Ojdanic et al..

Budgets are 1%, 5%, 10% and 20% of mutants. The metrics are:

  • absolute and root-mean-square error of $\hat S$ against the fully executed score;
  • empirical coverage of 90% intervals;
  • recall of surviving mutants within the executed set, which matters because surviving mutants are what developers act on;
  • total wall-clock time.

Cerebro's Java benchmark supplies equivalent and stubborn labels for the diagnostic that validates the aleatoric component. We will measure how well $U_{\text{ale}}$ ranks those mutants (AUC), compared with how well $U_{\text{epi}}$ does.

The decisive check has two parts. First, on cross-project splits at a 5% budget, the full method must reduce score error relative to random-plus-correction and relative to $\lambda=0$. Second, the pure-epistemic ablation must do worse than total-uncertainty selection. If both hold, the two-part value argument is supported. If only the first holds, the gain comes from the direct-resolution term, the decomposition is unnecessary, and the simpler thresholded strategy is the practical recommendation.